nested_loop_iterator.hpp 12.6 KB
Newer Older
1
2
3
4
5
6
#ifndef MLN_CORE_IMAGE_INTERNAL_NESTED_LOOP_ITERATOR_HPP
# define MLN_CORE_IMAGE_INTERNAL_NESTED_LOOP_ITERATOR_HPP

# include <type_traits>
# include <utility>

7
# include <mln/core/iterator/iterator_base.hpp>
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# include <boost/any.hpp>

namespace mln
{

  namespace internal
  {


    struct iterator_core_access
    {
      template <typename S, typename R = decltype( std::declval<S>().get_value() ) >
      struct get_value_helper
      {
        typedef R type;
        static R get_value(S& v) { return v.get_value(); }
      };

      template <typename S>
      struct get_value_helper<S, void>
      {
        typedef boost::any type;
        static boost::any get_value(S&) { return boost::any (); }
      };

    protected:
      template <typename S>
      auto get_point(S& v) -> decltype(v.get_point()) { return v.get_point(); }

37
38
39
      template <typename S>
      auto get_point(const S& v) const -> decltype(v.get_point()) { return v.get_point(); }

40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
      template <typename S>
      typename get_value_helper<S>::type
      get_value(S& v) {
        return get_value_helper<S>::get_value(v);
      }

      template <typename S, typename T>
      bool equal(const S& v, const T& other) const { return v.equal(other); }
    };


    /// \defgroup _nested_loop_iterator Nested loop iterator facilities
    /// \{

    /// \brief Implement an iterator that has the semantic:
    ///
    /// \code
edwin.carlinet's avatar
edwin.carlinet committed
57
58
    /// for (p.init<0>(), v.init<0>(); p.finished(); p.inc<0>(), v.inc<0>())
    ///   for (p.init<1>(), v.init<1>(); p.finished(); p.inc<1>(), v.inc<1>())
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
    ///    .
    ///      .
    ///        yield
    /// \endcode
    ///
    /// \tparam PointVisitor
    template <typename PointVisitor, typename ValueVisitor,
	      typename InternalStruct, typename DereferencePolicy>
    struct nested_loop_iterator;


    /// \defgroup _deref_policy_ Dereference policies
    /// A dereference policy \p Deref provides:
    /// * `Deref::type<S>`  The return type of the object after dereferenciation
    /// * `Deref::type<S> Deref::dereference(const S&)` Dereferenciation operator
    /// \{
    struct deref_return_structure_policy;
    struct deref_return_value_policy;
    struct deref_return_point_policy;
    /// \}


    /// \defgroup _point_visitor_ Point Visitor
    /// A PointVisitor is a policy that provides behaviors about
    /// the way of handling the point
    /// The point is the object that guides the iteration.
    /// The point visitor \p PVis provides:
    /// * `PVis::point_type`
edwin.carlinet's avatar
edwin.carlinet committed
87
88
89
90
    /// * `PVis::initialize(P&)`
    /// * `PVis::init<n>(P&)`
    /// * `PVis::next<n>(P&)`
    /// * `PVis::finished<n>(P&)`
91
    /// \{
92
93
94
95
96
97
98
99
100
101
102
    template <typename Point> struct origin_point_visitor_forward;
    template <typename Point> struct origin_point_visitor_backward;
    template <typename Point> struct domain_point_visitor_forward;
    template <typename Point> struct domain_point_visitor_backward;
    //template <typename Point> struct strided_domain_point_visitor;

    template <typename P> origin_point_visitor_forward<P> make_point_visitor_forward(const P& pmax);
    template <typename P> origin_point_visitor_backward<P> make_point_visitor_backward(const P& pmax);
    template <typename P> domain_point_visitor_forward<P> make_point_visitor_forward(const P& pmin, const P& pmax);
    template <typename P> domain_point_visitor_backward<P> make_point_visitor_backward(const P& pmin, const P& pmax);
    //template <typename P> strided_domain_point_visitor<P> make_point_visitor(const P& pmin, const P& pmax, const P& strides);
103
104
105
106
107
108
109
110
    /// \}


    /// \defgroup _value_visitor_ Value Visitor
    /// A value visitor is a policy that provides bahviours
    /// about the way to iterate over values.
    /// The point visitor \p VVis provides:
    /// * `VVis::arg` : Type of argument
edwin.carlinet's avatar
edwin.carlinet committed
111
112
113
    /// * `VVis::initialize(VVis::arg)`
    /// * `VVis::init<n>(VVis::arg)`
    /// * `VVis::next<n>(VVis::arg)`
114
115
    /// The type of `s.get_value()` must be convertible to `VVis::arg`
    /// \{
116
    template <size_t dim, bool forward> struct strided_pointer_value_visitor;
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
    struct no_op_value_visitor;
    /// \}


    /// \}

    /********************/
    /** Implementation **/
    /********************/

    // Dereference Policies

    struct deref_return_structure_policy {
      template <typename S>
      using value_type = const S;

      template <typename S>
      using reference = const S&;

      template <typename S>
      static const S& dereference(const S& s_) {
	return s_;
      }
    };

    struct deref_return_value_policy {
      template <typename S>
      using value_type = typename S::value_type;

      template <typename S>
      using reference = typename S::reference;

      template <typename S>
      static reference<S> dereference(const S& s_) {
	return s_.val();
      }
    };

    struct deref_return_point_policy {
      template <typename S>
      using value_type = typename S::point_type;

      template <typename S>
      using reference = const typename S::point_type &;

      template <typename S>
      static reference<S> dereference(const S& s_) {
	return s_.point();
      }
    };


edwin.carlinet's avatar
edwin.carlinet committed
169
    //// Point Visitors
170
    template <typename P>
edwin.carlinet's avatar
edwin.carlinet committed
171
    struct origin_point_visitor_forward
172
173
174
    {
      typedef P point_type;

edwin.carlinet's avatar
edwin.carlinet committed
175
176
177
      origin_point_visitor_forward() : pmax_ () {}
      origin_point_visitor_forward(const P& pmax) : pmax_ (pmax) {}

Edwin Carlinet's avatar
Edwin Carlinet committed
178
      void initialize(P& point) const { point = (P){{0,}}; }
edwin.carlinet's avatar
edwin.carlinet committed
179
180
181
182
183
184
185
186
187
188
189
      template <size_t n> void  init(P& point) const { point[n] = 0; }
      template <size_t n> void  next(P& point) const  { ++point[n]; }
      template <size_t n> bool  finished(const P& point) const { return point[n] >= pmax_[n]; }
    private:
      P pmax_;
    };

    template <typename P>
    struct origin_point_visitor_backward
    {
      typedef P point_type;
190

edwin.carlinet's avatar
edwin.carlinet committed
191
192
      origin_point_visitor_backward() : pmax_ () {}
      origin_point_visitor_backward(const P& pmax) : pmax_ (pmax) {}
193

194
      void  initialize(P& point) const { point = pmax_; point -= 1; }
edwin.carlinet's avatar
edwin.carlinet committed
195
196
      template <size_t n> void  init(P& point) const { point[n] = pmax_[n] - 1; }
      template <size_t n> void  next(P& point) const { --point[n]; }
197
      template <size_t n> bool  finished(const P& point) const { return point[n] < 0; }
198
199
200
201
202

    private:
      P pmax_;
    };

edwin.carlinet's avatar
edwin.carlinet committed
203

204
    template <typename P>
edwin.carlinet's avatar
edwin.carlinet committed
205
    struct domain_point_visitor_backward
206
207
208
    {
      typedef P point_type;

edwin.carlinet's avatar
edwin.carlinet committed
209
210
211
      domain_point_visitor_backward(): pmin_ (), pmax_ () {}
      domain_point_visitor_backward(const P& pmin, const P& pmax) : pmin_ (pmin), pmax_ (pmax) {}

212
      void  initialize(P& point) const { point = pmax_; point -= 1; }
edwin.carlinet's avatar
edwin.carlinet committed
213
214
215
216
217
218
219
220
      template <size_t n> void  init(P& point) const { point[n] = pmax_[n] - 1; }
      template <size_t n> void  next(P& point) const { --point[n]; }
      template <size_t n> bool  finished(P& point) const { return point[n] < pmin_[n]; }

    private:
      P pmin_;
      P pmax_;
    };
221

edwin.carlinet's avatar
edwin.carlinet committed
222
223
224
225
    template <typename P>
    struct domain_point_visitor_forward
    {
      typedef P point_type;
226

edwin.carlinet's avatar
edwin.carlinet committed
227
228
      domain_point_visitor_forward(): pmin_ (), pmax_ () {}
      domain_point_visitor_forward(const P& pmin, const P& pmax) : pmin_ (pmin), pmax_ (pmax) {}
229

edwin.carlinet's avatar
edwin.carlinet committed
230
231
232
233
      void  initialize(P& point) const                  { point = pmin_; }
      template <size_t n> void  init(P& point) const    { point[n] = pmin_[n]; }
      template <size_t n> void  next(P& point) const    { ++point[n]; }
      template <size_t n> bool  finished(const P& point) const { return point[n] >= pmax_[n]; }
234
235
236
237
238
239
    private:
      P pmin_;
      P pmax_;
    };


edwin.carlinet's avatar
edwin.carlinet committed
240
241


242
243
    template <typename P>
    inline
edwin.carlinet's avatar
edwin.carlinet committed
244
245
    origin_point_visitor_forward<P>
    make_point_visitor_forward(const P& pmax)
246
    {
edwin.carlinet's avatar
edwin.carlinet committed
247
      return origin_point_visitor_forward<P>(pmax);
248
249
250
    }

    template <typename P>
edwin.carlinet's avatar
edwin.carlinet committed
251
252
253
    inline
    origin_point_visitor_backward<P>
    make_point_visitor_backward(const P& pmax)
254
    {
edwin.carlinet's avatar
edwin.carlinet committed
255
      return origin_point_visitor_backward<P>(pmax);
256
257
    }

edwin.carlinet's avatar
edwin.carlinet committed
258
259
260
261
262
263
    template <typename P>
    domain_point_visitor_forward<P>
    make_point_visitor_forward(const P& pmin, const P& pmax)
    {
      return domain_point_visitor_forward<P>(pmin, pmax);
    }
264

edwin.carlinet's avatar
edwin.carlinet committed
265
266
267
268
269
270
    template <typename P>
    domain_point_visitor_backward<P>
    make_point_visitor_backward(const P& pmin, const P& pmax)
    {
      return domain_point_visitor_backward<P>(pmin, pmax);
    }
271
272


edwin.carlinet's avatar
edwin.carlinet committed
273
    // Value visitor
274
    template <size_t dim, bool forward>
edwin.carlinet's avatar
edwin.carlinet committed
275
276
    struct strided_pointer_value_visitor
    {
277
      typedef char* byte_ptr_t;
edwin.carlinet's avatar
edwin.carlinet committed
278
      enum { ndim = dim };
279

edwin.carlinet's avatar
edwin.carlinet committed
280
281
282
      strided_pointer_value_visitor()
      {
      }
283

284
      strided_pointer_value_visitor(byte_ptr_t start, const size_t* strides)
edwin.carlinet's avatar
edwin.carlinet committed
285
        : start_ (start)
286
287
288
289
       {
	 std::copy(strides, strides + ndim, strides_.begin());
       }

edwin.carlinet's avatar
edwin.carlinet committed
290
      void
291
      initialize(byte_ptr_t& ptr)
edwin.carlinet's avatar
edwin.carlinet committed
292
293
294
295
      {
        ptr = start_;
        stack_.fill(start_);
      }
296
297


edwin.carlinet's avatar
edwin.carlinet committed
298
299
      template <size_t n>
      typename std::enable_if<(n < ndim-1)>::type
300
      init (byte_ptr_t& )
edwin.carlinet's avatar
edwin.carlinet committed
301
302
303
304
      {
        static_assert(n > 0, "");
        stack_[n] = stack_[n-1];
      }
305

edwin.carlinet's avatar
edwin.carlinet committed
306
307
      template <size_t n>
      typename std::enable_if<(n == ndim-1)>::type
308
      init(byte_ptr_t& ptr)
edwin.carlinet's avatar
edwin.carlinet committed
309
310
311
312
      {
        static_assert(n > 0, "");
        ptr = stack_[n] = stack_[n-1];
      }
313

edwin.carlinet's avatar
edwin.carlinet committed
314
    template <size_t n>
315
316
    typename std::enable_if<(!forward and n < dim-1)>::type
    next (char* &)
edwin.carlinet's avatar
edwin.carlinet committed
317
318
319
    {
      stack_[n] -= strides_[n];
    }
320

edwin.carlinet's avatar
edwin.carlinet committed
321
    template <size_t n>
322
323
    typename std::enable_if<(forward and n < dim-1)>::type
    next (char* &)
edwin.carlinet's avatar
edwin.carlinet committed
324
325
326
    {
      stack_[n] += strides_[n];
    }
327

edwin.carlinet's avatar
edwin.carlinet committed
328
    template <size_t n>
329
330
    typename std::enable_if<(!forward and n == dim-1)>::type
    next (char*& ptr)
edwin.carlinet's avatar
edwin.carlinet committed
331
332
333
    {
      ptr = (stack_[n] -= strides_[n]);
    }
334

edwin.carlinet's avatar
edwin.carlinet committed
335
    template <size_t n>
336
337
    typename std::enable_if<(forward and n == dim-1)>::type
    next (char*& ptr)
338
    {
edwin.carlinet's avatar
edwin.carlinet committed
339
      ptr = (stack_[n] += strides_[n]);
340
341
    }

edwin.carlinet's avatar
edwin.carlinet committed
342

343
344
345
346
347
    private:
      char* start_;
      std::array<size_t, ndim> strides_;
      std::array<char*, ndim> stack_;
    };
edwin.carlinet's avatar
edwin.carlinet committed
348

349
350
    struct no_op_value_visitor
    {
edwin.carlinet's avatar
edwin.carlinet committed
351
352
353
      void initialize(const boost::any& ) {}
      template <size_t n> void init (const boost::any& ) {}
      template <size_t n> void next (const boost::any& ) {}
354
355
356
    };


edwin.carlinet's avatar
edwin.carlinet committed
357

358
359
360
    template <typename PointVisitor, typename ValueVisitor,
	      typename InternalStruct, typename DereferencePolicy>
    struct nested_loop_iterator :
edwin.carlinet's avatar
edwin.carlinet committed
361
362
363
      iterator_base< nested_loop_iterator<PointVisitor, ValueVisitor, InternalStruct, DereferencePolicy>,
                     typename DereferencePolicy::template value_type<InternalStruct>,
                     typename DereferencePolicy::template reference<InternalStruct> >,
364
365
      public internal::iterator_core_access
    {
edwin.carlinet's avatar
edwin.carlinet committed
366
367
      typedef typename DereferencePolicy::template reference<InternalStruct> reference;

368
369
370
371
      nested_loop_iterator()
      {
      }

edwin.carlinet's avatar
edwin.carlinet committed
372

373
374
375
376
377
      nested_loop_iterator(const InternalStruct s, const PointVisitor& pv, const ValueVisitor& vv)
        : s_ (s), p_ (pv), v_ (vv)
      {
      }

Edwin Carlinet's avatar
Edwin Carlinet committed
378
379
380
381
382
383
384
385
386
      template <typename PointVisitor2, typename ValueVisitor2, typename InternalStruct2>
      nested_loop_iterator(const nested_loop_iterator<PointVisitor2, ValueVisitor2, InternalStruct2, DereferencePolicy>& other,
			   typename std::enable_if< std::is_convertible<PointVisitor, PointVisitor2>::value and
			   std::is_convertible<ValueVisitor2, ValueVisitor>::value and
			   std::is_convertible<InternalStruct2, InternalStruct>::value>::type* = NULL)
	: s_ (other.s_), p_ (other.p_), v_ (other.v_)
      {
      }

edwin.carlinet's avatar
edwin.carlinet committed
387
388

      void init()
389
      {
390
391
        p_.initialize(get_point(s_));
        v_.initialize(get_value(s_));
392
393
      }

edwin.carlinet's avatar
edwin.carlinet committed
394
395
396
397
      void next()
      {
        this->next_<ndim-1>();
      }
398

399
      bool finished() const
edwin.carlinet's avatar
edwin.carlinet committed
400
      {
401
        return p_.template finished<0>(get_point(s_));
edwin.carlinet's avatar
edwin.carlinet committed
402
      }
403

edwin.carlinet's avatar
edwin.carlinet committed
404
405
406
407
408
      reference
      dereference() const
      {
        return DereferencePolicy::dereference(s_);
      }
409
410


edwin.carlinet's avatar
edwin.carlinet committed
411
412
  private:
      template <typename, typename, typename, typename>
Edwin Carlinet's avatar
Edwin Carlinet committed
413
      friend struct nested_loop_iterator;
414

edwin.carlinet's avatar
edwin.carlinet committed
415
      enum { ndim = PointVisitor::point_type::ndim };
416
417


edwin.carlinet's avatar
edwin.carlinet committed
418
419
420
      template <size_t n>
      typename std::enable_if<(n > 0), void>::type
      next_()
421
      {
edwin.carlinet's avatar
edwin.carlinet committed
422
423
424
425
426
427
428
        mln_precondition(not this->finished());
        p_.template next<n>(iterator_core_access::get_point(s_));
        if (not p_.template finished<n>(iterator_core_access::get_point(s_)))
          {
            v_.template next<n>(get_value(s_));
            return;
          }
429
        this->next_<n-1>();
edwin.carlinet's avatar
edwin.carlinet committed
430
431
        p_.template init<n>(get_point(s_));
        v_.template init<n>(get_value(s_));
432
433
      }

edwin.carlinet's avatar
edwin.carlinet committed
434
435
436
437
438
439
440
441
      template <size_t n>
      typename std::enable_if<n == 0, void>::type
      next_()
      {
        mln_precondition(not this->finished());
        p_.template next<0>(get_point(s_));
        v_.template next<0>(get_value(s_));
      }
442
443
444
445
446
447
448
449
450
451
452
453

    private:
      InternalStruct s_;
      PointVisitor p_;
      ValueVisitor v_;
    };

  }

}

#endif // ! MLN_CORE_IMAGE_INTERNAL_NESTED_LOOP_ITERATOR_HPP