[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

multi_iterator.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2003-2012 by Gunnar Kedenburg and Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* ( Version 1.3.0, Sep 10 2004 ) */
7 /* The VIGRA Website is */
8 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
9 /* Please direct questions, bug reports, and contributions to */
10 /* ullrich.koethe@iwr.uni-heidelberg.de or */
11 /* vigra@informatik.uni-hamburg.de */
12 /* */
13 /* Permission is hereby granted, free of charge, to any person */
14 /* obtaining a copy of this software and associated documentation */
15 /* files (the "Software"), to deal in the Software without */
16 /* restriction, including without limitation the rights to use, */
17 /* copy, modify, merge, publish, distribute, sublicense, and/or */
18 /* sell copies of the Software, and to permit persons to whom the */
19 /* Software is furnished to do so, subject to the following */
20 /* conditions: */
21 /* */
22 /* The above copyright notice and this permission notice shall be */
23 /* included in all copies or substantial portions of the */
24 /* Software. */
25 /* */
26 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
27 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
28 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
29 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
30 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
31 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
32 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
33 /* OTHER DEALINGS IN THE SOFTWARE. */
34 /* */
35 /************************************************************************/
36 
37 #ifndef VIGRA_MULTI_ITERATOR_HXX
38 #define VIGRA_MULTI_ITERATOR_HXX
39 
40 #include <sys/types.h>
41 #include "multi_fwd.hxx"
42 #include "iteratortags.hxx"
43 #include "multi_iterator_coupled.hxx"
44 
45 namespace vigra {
46 
47 /** \addtogroup MultiIteratorGroup
48 */
49 //@{
50 
51  /** \brief Iterate over a virtual array where each element contains its coordinate.
52 
53  MultiCoordinateIterator behaves like a read-only random access iterator.
54  It moves accross the given region of interest in scan-order (with the first
55  index changing most rapidly), and dereferencing the iterator returns the
56  coordinate (i.e. multi-dimensional index) of the current array element.
57  The functionality is thus similar to a meshgrid in Matlab or numpy.
58 
59  Internally, it is just a wrapper of a \ref CoupledScanOrderIterator that
60  has been created without any array and whose reference type is not a
61  \ref CoupledHandle, but the coordinate itself.
62 
63  The iterator supports all functions listed in the STL documentation for
64  <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random Access Iterators</a>.
65 
66  <b>Usage:</b>
67 
68  <b>\#include</b> <vigra/multi_iterator.hxx><br/>
69  Namespace: vigra
70 
71  \code
72  MultiCoordinateIterator<3> i(Shape3(3,2,1)), end = i.getEndIterator();
73 
74  for(; i != end; ++i)
75  std::cout << *i << "\n";
76 
77  // Output:
78  // (0, 0, 0)
79  // (1, 0, 0)
80  // (2, 0, 0)
81  // (0, 1, 0)
82  // (1, 1, 0)
83  // (2, 1, 0)
84  \endcode
85  */
86 template<unsigned int N>
87 class MultiCoordinateIterator
88  : public CoupledScanOrderIterator<N>
89 {
90  public:
91  typedef CoupledScanOrderIterator<N> base_type;
92 
93  typedef typename base_type::shape_type shape_type;
94  typedef typename base_type::difference_type difference_type;
95  typedef MultiCoordinateIterator iterator;
96  typedef std::random_access_iterator_tag iterator_category;
97 
98  typedef typename base_type::value_type handle_type;
99  typedef typename handle_type::value_type value_type;
100  typedef typename handle_type::reference reference;
101  typedef typename handle_type::const_reference const_reference;
102  typedef typename handle_type::pointer pointer;
103  typedef typename handle_type::const_pointer const_pointer;
104 
105  MultiCoordinateIterator()
106  : base_type(handle_type())
107  {}
108 
109  explicit MultiCoordinateIterator(shape_type const & shape)
110  : base_type(handle_type(shape))
111  {}
112 
113  explicit MultiCoordinateIterator(shape_type const & start, shape_type const & end)
114  : base_type(handle_type(end))
115  {
116  this->restrictToSubarray(start, end);
117  }
118 
119  template<class DirectedTag>
120  explicit MultiCoordinateIterator(GridGraph<N, DirectedTag> const & g)
121  : base_type(handle_type(g.shape()))
122  {}
123 
124  // dereferencing the iterator yields the coordinate object
125  // (used as vertex_descriptor)
126  reference operator*()
127  {
128  return this->template get<0>();
129  }
130 
131  const_reference operator*() const
132  {
133  return this->template get<0>();
134  }
135 
136  operator value_type() const
137  {
138  return *(*this);
139  }
140 
141  pointer operator->()
142  {
143  return &this->template get<0>();
144  }
145 
146  const_pointer operator->() const
147  {
148  return &this->template get<0>();
149  }
150 
151  value_type operator[](MultiArrayIndex i) const
152  {
153  return *(MultiCoordinateIterator(*this) += i);
154  }
155 
156  MultiCoordinateIterator & operator++()
157  {
158  base_type::operator++();
159  return *this;
160  }
161 
162  MultiCoordinateIterator operator++(int)
163  {
164  MultiCoordinateIterator res(*this);
165  ++*this;
166  return res;
167  }
168 
169  MultiCoordinateIterator & operator+=(MultiArrayIndex i)
170  {
171  base_type::operator+=(i);
172  return *this;
173  }
174 
175  MultiCoordinateIterator & operator+=(const shape_type &coordOffset)
176  {
177  base_type::operator+=(coordOffset);
178  return *this;
179  }
180 
181  MultiCoordinateIterator & operator--()
182  {
183  base_type::operator--();
184  return *this;
185  }
186 
187  MultiCoordinateIterator operator--(int)
188  {
189  MultiCoordinateIterator res(*this);
190  --*this;
191  return res;
192  }
193 
194  MultiCoordinateIterator & operator-=(MultiArrayIndex i)
195  {
196  return operator+=(-i);
197  }
198 
199  MultiCoordinateIterator & operator-=(const shape_type &coordOffset)
200  {
201  return operator+=(-coordOffset);
202  }
203 
204  MultiCoordinateIterator getEndIterator() const
205  {
206  return MultiCoordinateIterator(base_type::getEndIterator());
207  }
208 
209  MultiCoordinateIterator operator+(MultiArrayIndex d) const
210  {
211  return MultiCoordinateIterator(*this) += d;
212  }
213 
214  MultiCoordinateIterator operator-(MultiArrayIndex d) const
215  {
216  return MultiCoordinateIterator(*this) -= d;
217  }
218 
219  MultiCoordinateIterator operator+(const shape_type &coordOffset) const
220  {
221  return MultiCoordinateIterator(*this) += coordOffset;
222  }
223 
224  MultiCoordinateIterator operator-(const shape_type &coordOffset) const
225  {
226  return MultiCoordinateIterator(*this) -= coordOffset;
227  }
228 
229  MultiArrayIndex operator-(const MultiCoordinateIterator & other) const
230  {
231  return base_type::operator-(other);
232  }
233 
234  protected:
235  MultiCoordinateIterator(base_type const & base)
236  : base_type(base)
237  {}
238 };
239 
240  /** \brief Sequential iterator for MultiArrayView.
241 
242  This iterator provides STL-compatible random access iterator functionality for arbitrary
243  \ref MultiArrayView instances, regardless of their shapes and strides. The
244  class uses an implementation that minimizes speed penalties that could result from
245  non-trivial strides. The <i>scan-order</i> is defined such that dimensions are iterated
246  from front to back (first to last).
247 
248  You normally construct instances of this class by calling \ref MultiArrayView::begin()
249  and \ref MultiArrayView::end().
250 
251  The iterator supports all functions listed in the STL documentation for
252  <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random Access Iterators</a>.
253 
254  <b>\#include</b> <vigra/multi_iterator.hxx><br/>
255  Namespace: vigra
256  */
257 template <unsigned int N, class V, class REFERENCE, class POINTER>
258 class StridedScanOrderIterator
259  : public CoupledIteratorType<N, V>::type
260 {
261  public:
262  typedef typename CoupledIteratorType<N, V>::type base_type;
263  typedef typename base_type::value_type handle_type;
264 
265  typedef typename base_type::shape_type shape_type;
266  typedef typename base_type::difference_type difference_type;
267  typedef StridedScanOrderIterator iterator;
268  typedef std::random_access_iterator_tag iterator_category;
269 
270  typedef typename detail::ResolveChunkedMemory<V>::type T;
271  typedef T value_type;
272  typedef REFERENCE reference;
273  typedef T const & const_reference;
274  typedef POINTER pointer;
275  typedef T const * const_pointer;
276 
277  StridedScanOrderIterator()
278  : base_type()
279  {}
280 
281  template <class S>
282  explicit StridedScanOrderIterator(MultiArrayView<N, T, S> const & view)
283  : base_type(createCoupledIterator(view))
284  {}
285 
286  StridedScanOrderIterator(POINTER p, shape_type const & shape, shape_type const & strides)
287  : base_type(createCoupledIterator(MultiArrayView<N, T, StridedArrayTag>(shape, strides, const_cast<T *>(p))))
288  {}
289 
290  StridedScanOrderIterator(handle_type const & handle)
291  : base_type(handle)
292  {}
293 
294  reference operator*()
295  {
296  return this->template get<1>();
297  }
298 
299  const_reference operator*() const
300  {
301  return this->template get<1>();
302  }
303 
304  pointer operator->()
305  {
306  return &this->template get<1>();
307  }
308 
309  const_pointer operator->() const
310  {
311  return &this->template get<1>();
312  }
313 
314  reference operator[](MultiArrayIndex i)
315  {
316  return *(StridedScanOrderIterator(*this) += i);
317  }
318 
319  const_reference operator[](MultiArrayIndex i) const
320  {
321  return *(StridedScanOrderIterator(*this) += i);
322  }
323 
324  reference operator[](const shape_type& coordOffset)
325  {
326  return *(StridedScanOrderIterator(*this) += coordOffset);
327  }
328 
329  const_reference operator[](const shape_type& coordOffset) const
330  {
331  return *(StridedScanOrderIterator(*this) += coordOffset);
332  }
333 
334  StridedScanOrderIterator & operator++()
335  {
336  base_type::operator++();
337  return *this;
338  }
339 
340  StridedScanOrderIterator operator++(int)
341  {
342  StridedScanOrderIterator res(*this);
343  ++*this;
344  return res;
345  }
346 
347  StridedScanOrderIterator & operator+=(MultiArrayIndex i)
348  {
350  return *this;
351  }
352 
353  StridedScanOrderIterator & operator+=(const shape_type &coordOffset)
354  {
355  base_type::operator+=(coordOffset);
356  return *this;
357  }
358 
359  StridedScanOrderIterator & operator--()
360  {
361  base_type::operator--();
362  return *this;
363  }
364 
365  StridedScanOrderIterator operator--(int)
366  {
367  StridedScanOrderIterator res(*this);
368  --*this;
369  return res;
370  }
371 
372  StridedScanOrderIterator & operator-=(MultiArrayIndex i)
373  {
374  return operator+=(-i);
375  }
376 
377  StridedScanOrderIterator & operator-=(const shape_type &coordOffset)
378  {
379  return operator+=(-coordOffset);
380  }
381 
382  StridedScanOrderIterator getEndIterator() const
383  {
384  return StridedScanOrderIterator(base_type::getEndIterator());
385  }
386 
387  StridedScanOrderIterator operator+(MultiArrayIndex d) const
388  {
389  return StridedScanOrderIterator(*this) += d;
390  }
391 
392  StridedScanOrderIterator operator-(MultiArrayIndex d) const
393  {
394  return StridedScanOrderIterator(*this) -= d;
395  }
396 
397  MultiArrayIndex operator-(StridedScanOrderIterator const & other) const
398  {
399  return base_type::operator-(other);
400  }
401 
402  StridedScanOrderIterator operator+(const shape_type &coordOffset) const
403  {
404  return StridedScanOrderIterator(*this) += coordOffset;
405  }
406 
407  StridedScanOrderIterator operator-(const shape_type &coordOffset) const
408  {
409  return StridedScanOrderIterator(*this) -= coordOffset;
410  }
411 
412  MultiArrayIndex index() const
413  {
414  return this->scanOrderIndex();
415  }
416 
417  StridedScanOrderIterator &
418  restrictToSubarray(shape_type const & start, shape_type const & stop)
419  {
420  base_type::restrictToSubarray(start, stop);
421  return *this;
422  }
423 
424  protected:
425  StridedScanOrderIterator(base_type const & base)
426  : base_type(base)
427  {}
428 };
429 
430 //@}
431 
432 /** \page MultiIteratorPage Multi-dimensional Array Iterators
433 
434 General iterators for arrays of arbitrary dimension.
435 
436 <p>
437 <UL style="list-style-image:url(documents/bullet.gif)">
438 <LI> \ref vigra::MultiArrayShape
439  <BR>&nbsp;&nbsp;&nbsp;<em>Difference type for \ref vigra::MultiArrayView or \ref vigra::MultiIterator</em>
440 <LI> \ref vigra::MultiIterator
441  <BR>&nbsp;&nbsp;&nbsp;<em>Iterator for unstrided \ref vigra::MultiArrayView</em>
442 <LI> \ref vigra::StridedMultiIterator
443  <BR>&nbsp;&nbsp;&nbsp;<em>Iterator for strided \ref vigra::MultiArrayView</em>
444 <LI> \ref vigra::StridedScanOrderIterator
445  <BR>&nbsp;&nbsp;&nbsp;<em>STL-compatible random access iterator for \ref vigra::MultiArrayView</em>
446 <LI> \ref vigra::CoupledScanOrderIterator
447  <BR>&nbsp;&nbsp;&nbsp;<em>Iterate over multiple images simultaneously in scan order</em>
448 </UL>
449 </p>
450 
451 <p>
452  The Multidimensional Iterator concept allows navigation on arrays
453  of arbitrary dimension. It provides two modes of iteration:
454  <em>direct traversal</em>, and <em>hierarchical traversal</em>.
455  In general, hierarchical traversal will be faster, while only
456  direct traversal allows for true random access in all dimensions.
457  Via the <tt>dim<K>()</tt> function, operations applying to a particular
458  dimension can be used in the direct traversal mode. In contrast,
459  direct traversal functions should not be used in the hierarchical mode
460  because the hierarchical functions are only well-defined if the
461  iterator points to element 0 in all dimensions below its current dimension.
462  The current dimension of a <tt>MultiIterator<N, ...></tt> is <tt>N-1</tt>.
463 </p>
464 <h3>General Requirements for MultiIterator</h3>
465 <p>
466 <table border=2 cellspacing=0 cellpadding=2 width="100%">
467 <tr><th colspan=2>
468  Local Types
469  </th><th>
470  Meaning
471  </th>
472 </tr>
473 <tr><td colspan=2>
474  <tt>MultiIterator::value_type</tt></td><td>the underlying arrays's pixel type</td>
475 </tr>
476 <tr><td colspan=2>
477  <tt>MultiIterator::reference</tt></td>
478  <td>the iterator's reference type (return type of <TT>*iter</TT>). Will be
479  <tt>value_type &</tt> for a mutable iterator, and convertible to
480  <tt>value_type const &</tt> for a const iterator.</td>
481 </tr>
482 <tr><td colspan=2>
483  <tt>MultiIterator::pointer</tt></td>
484  <td>the iterator's pointer type (return type of <TT>iter.operator->()</TT>). Will be
485  <tt>value_type *</tt> for a mutable iterator, and convertible to
486  <tt>value_type const *</tt> for a const iterator.</td>
487 </tr>
488 <tr><td colspan=2>
489  <tt>MultiIterator::iterator_category</tt></td>
490  <td>the iterator tag (<tt>vigra::multi_dimensional_traverser_tag</tt>)</td>
491 </tr>
492 <tr><th>
493  Operation
494  </th><th>
495  Result
496  </th><th>
497  Semantics
498  </th>
499 </tr>
500 <tr><td colspan=2>
501  <tt>MultiIterator k;</tt></td><td>default constructor</td>
502 </tr>
503 <tr><td colspan=2>
504  <tt>MultiIterator k(i);</tt></td><td>copy constructor</td>
505 </tr>
506 <tr>
507  <td><tt>k = i</tt></td>
508  <td><tt>MultiIterator &</tt></td><td>assignment</td>
509 </tr>
510 <tr>
511  <td><tt>i == j</tt></td><td><tt>bool</tt></td>
512  <td>equality (iterators point to the same element)</td>
513 </tr>
514 <tr>
515  <td><tt>i != j</tt></td><td><tt>bool</tt></td>
516  <td>inequality (iterators don't point to the same element)</td>
517 </tr>
518 <tr>
519  <td><tt>*i</tt></td><td><tt>MultiIterator::reference</tt></td>
520  <td>access the current element</td>
521 </tr>
522 <tr>
523  <td><tt>i->member()</tt></td><td>depends on operation</td>
524  <td>call member function of underlying pixel type via <tt>operator-></tt> of iterator</td>
525 </tr>
526 </table>
527 </p>
528 <h3>Requirements for Direct Traversal</h3>
529 <p>
530 <table border=2 cellspacing=0 cellpadding=2 width="100%">
531 <tr><th colspan=2>
532  Local Types
533  </th><th>
534  Meaning
535  </th>
536 </tr>
537 <tr><td colspan=2>
538  <tt>MultiIterator::multi_difference_type</tt></td>
539  <td>the iterator's multi-dimensional difference type (<TT>TinyVector<MultiArrayIndex, N></TT>)</td>
540 </tr>
541 <tr><th>
542  Operation
543  </th><th>
544  Result
545  </th><th>
546  Semantics
547  </th>
548 </tr>
549 <tr>
550  <td><tt>i += diff</tt></td><td><tt>MultiIterator &</tt></td>
551  <td>add offset to current position</td>
552 </tr>
553 <tr>
554  <td><tt>i -= diff</tt></td><td><tt>MultiIterator &</tt></td>
555  <td>subtract offset from current position</td>
556 </tr>
557 <tr>
558  <td><tt>i + diff</tt></td><td><tt>MultiIterator</tt></td>
559  <td>create traverser by adding offset</td>
560 </tr>
561 <tr>
562  <td><tt>i - diff</tt></td><td><tt>MultiIterator</tt></td>
563  <td>create traverser by subtracting offset</td>
564 </tr>
565 <tr>
566  <td><tt>i[diff]</tt></td><td><tt>MultiIterator::reference</tt></td>
567  <td>access element at offset <tt>diff</tt></td>
568 </tr>
569 <tr>
570  <td><tt>i.dim<K>()</tt></td><td><tt>MultiIterator<K+1, T, ...></tt></td>
571  <td>Access the traverser with the current dimension set to K. Typically used to call
572  navigation functions referring to a particular dimension.<br>
573  Example (assuming <tt>i, j</tt> are 3-dimensional):<br>
574  \code
575  i.dim<0>()++; // increment dimension 0
576  i.dim<1>()++; // increment dimension 1
577  i.dim<2>()++; // increment dimension 2
578 
579  j += MultiIterator::multi_difference_type(1,1,1); // same effect
580  \endcode
581  </td>
582 </tr>
583 <tr><td colspan=3>
584  <tt>i, j</tt> are of type <tt>MultiIterator</tt><br>
585  <tt>diff</tt> is of type <tt>MultiIterator::multi_difference_type</tt><br>
586  <tt>K</tt> is an integer compile-time constant
587  </td>
588 </tr>
589 </table>
590 </p>
591 <p>
592 Note that it is impossible to support an <tt>operator-</tt> between two iterators which returns
593 a <tt>MultiIterator::multi_difference_type</tt> because it is impossible to decide to which
594 dimension a difference applies. Consider for example, a 2-dimensional iterator <tt>i</tt>, and
595 let <tt>j = i + multi_difference_type(width, 0)</tt>, <tt>k = i + multi_difference_type(0,1)</tt>,
596 where <tt>width</tt> is the array's total width. In general, <tt>j</tt> and <tt>k</tt> point to
597 the same memory location, so that the two cases cannot easily be distinguished (it is possible,
598 but iterator performance will suffer significantly, as is experienced with
599 \ref vigra::ImageIterator where differencing is allowed).
600 </p>
601 
602 <h3>Requirements for Hierarchical Traversal</h3>
603 <p>
604 <table border=2 cellspacing=0 cellpadding=2 width="100%">
605 <tr><th colspan=2>
606  Local Types
607  </th><th>
608  Meaning
609  </th>
610 </tr>
611 <tr><td colspan=2>
612  <tt>MultiIterator::difference_type</tt></td>
613  <td>the iterator's difference type (<TT>MultiArrayIndex</TT>)</td>
614 </tr>
615 <tr><td colspan=2>
616  <tt>MultiIterator::next_type</tt></td><td>type of the next iterator
617  (referring to the next lower dimension) in the hierarchy</td>
618 </tr>
619 <tr><th>
620  Operation
621  </th><th>
622  Result
623  </th><th>
624  Semantics
625  </th>
626 </tr>
627 <tr>
628  <td><tt>++i</tt></td><td><tt>MultiIterator &</tt></td>
629  <td>pre-increment iterator in its current dimension</td>
630 </tr>
631 <tr>
632  <td><tt>i++</tt></td><td><tt>MultiIterator</tt></td>
633  <td>post-increment iterator in its current dimension</td>
634 </tr>
635 <tr>
636  <td><tt>--i</tt></td><td><tt>MultiIterator &</tt></td>
637  <td>pre-decrement iterator in its current dimension</td>
638 </tr>
639 <tr>
640  <td><tt>i--</tt></td><td><tt>MultiIterator</tt></td>
641  <td>post-decrement iterator in its current dimension</td>
642 </tr>
643 <tr>
644  <td><tt>i += d</tt></td><td><tt>MultiIterator &</tt></td>
645  <td>add <tt>d</tt> in current dimension</td>
646 </tr>
647 <tr>
648  <td><tt>i -= d</tt></td><td><tt>MultiIterator &</tt></td>
649  <td>subtract <tt>d</tt> in from dimension</td>
650 </tr>
651 <tr>
652  <td><tt>i + d</tt></td><td><tt>MultiIterator</tt></td>
653  <td>create new iterator by adding <tt>d</tt> in current dimension</td>
654 </tr>
655 <tr>
656  <td><tt>i - d</tt></td><td><tt>MultiIterator</tt></td>
657  <td>create new iterator by subtracting <tt>d</tt> in current dimension</td>
658 </tr>
659 <tr>
660  <td><tt>i - j</tt></td><td><tt>difference_type</tt></td>
661  <td>difference of <tt>i</tt> and <tt>j</tt> in the current dimension<br>
662  <em>Note:</em> The result of this operation is undefined if the iterator
663  doesn't point to element 0 in all dimensions below its current dimension.</td>
664 </tr>
665 <tr>
666  <td><tt>i < j</tt></td><td><tt>bool</tt></td>
667  <td><tt>i - j < 0</tt><br>
668  <em>Note:</em> The result of this operation is undefined if the iterator
669  doesn't point to element 0 in all dimensions below its current dimension.</td>
670 </tr>
671 <tr>
672  <td><tt>i[d]</tt></td><td><tt>MultiIterator::reference</tt></td>
673  <td>access element by adding offset <tt>d</tt> in current dimension</td>
674 </tr>
675 <tr>
676  <td><tt>i.begin()</tt></td><td><tt>next_type</tt></td>
677  <td>create the hierarchical iterator pointing to the first element in the
678  next lower dimension.<br>
679  <em>Note:</em> The result of this operation is undefined if the iterator
680  doesn't point to element 0 in all dimensions below its current dimension.<br>
681  Usage:<br>
682  \code
683  MultiIterator<3, int> i3 = ..., end3 = ...;
684  for(; i3 != end3; ++i3)
685  {
686  MultiIterator<3, int>::next_type i2 = i3.begin(), end2 = i3.end();
687  for(; i2 != end2; ++i2)
688  {
689  MultiIterator<3, int>::next_type::next_type i1 = i2.begin(), end1 = i2.end();
690  for(; i1 != end1; ++i1)
691  {
692  ... // do something with the current element
693  }
694  }
695  }
696 
697  \endcode
698  </td>
699 </tr>
700 <tr>
701  <td><tt>i.end()</tt></td><td><tt>next_type</tt></td>
702  <td>create the hierarchical iterator pointing to the past-the-end location in the
703  next lower dimension.<br>
704  <em>Note:</em> The result of this operation is undefined if the iterator
705  doesn't point to element 0 in all dimensions below its current dimension.</td>
706 </tr>
707 <tr><td colspan=3>
708  <tt>i, j</tt> are of type <tt>MultiIterator</tt><br>
709  <tt>d</tt> is of type <tt>MultiIterator::difference_type</tt>
710  </td>
711 </tr>
712 </table>
713 </p>
714 
715 */
716 
717 /** \addtogroup MultiIteratorGroup
718 */
719 //@{
720 
721 template <class POINTER>
722 struct MultiIteratorStrideTraits
723 {
724  typedef MultiArrayIndex stride_type;
725  typedef const stride_type* stride_array_type;
726  typedef stride_array_type shape_array_type;
727  static stride_array_type shift(stride_array_type s, unsigned d)
728  {
729  return s + d;
730  }
731 };
732 
733 /********************************************************/
734 /* */
735 /* MultiIterator */
736 /* */
737 /********************************************************/
738 
739 /********************************************************/
740 /* */
741 /* MultiIterator<1> */
742 /* */
743 /********************************************************/
744 
745 //
746 template <class T, class REFERENCE, class POINTER>
747 class MultiIterator<1, T, REFERENCE, POINTER>
748 {
749  public:
750  enum { level = 0 };
751  typedef T value_type;
752  typedef REFERENCE reference;
753  typedef const value_type &const_reference;
754  typedef POINTER pointer;
755  typedef const value_type *const_pointer;
756  typedef typename MultiArrayShape<1>::type multi_difference_type;
757  typedef MultiIteratorStrideTraits<POINTER> stride_traits;
758  typedef typename stride_traits::stride_type difference_type;
759  typedef typename stride_traits::stride_array_type difference_array_type;
760  typedef typename stride_traits::shape_array_type shape_array_type;
761  typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
762  typedef std::random_access_iterator_tag iterator_category;
763 
764  protected:
765  pointer m_ptr;
766 
767  public:
768  MultiIterator ()
769  : m_ptr (0)
770  {}
771 
772  MultiIterator (pointer ptr,
773  const difference_array_type &,
774  const shape_array_type &)
775  : m_ptr (ptr)
776  {}
777 
778  void operator++ ()
779  {
780  ++m_ptr;
781  }
782 
783  void operator-- ()
784  {
785  --m_ptr;
786  }
787 
788  MultiIterator operator++ (int)
789  {
790  MultiIterator ret = *this;
791  ++(*this);
792  return ret;
793  }
794 
795  MultiIterator operator-- (int)
796  {
797  MultiIterator ret = *this;
798  --(*this);
799  return ret;
800  }
801 
802  MultiIterator &operator+= (difference_type n)
803  {
804  m_ptr += n;
805  return *this;
806  }
807 
808  MultiIterator & operator+= (multi_difference_type const & d)
809  {
810  m_ptr += d[level];
811  return *this;
812  }
813 
814  MultiIterator &operator-= (difference_type n)
815  {
816  m_ptr -= n;
817  return *this;
818  }
819 
820  MultiIterator & operator-= (multi_difference_type const & d)
821  {
822  m_ptr -= d[level];
823  return *this;
824  }
825 
826  MultiIterator operator+ (difference_type n) const
827  {
828  MultiIterator ret = *this;
829  ret += n;
830  return ret;
831  }
832 
833  MultiIterator operator+ (multi_difference_type const & d) const
834  {
835  MultiIterator ret = *this;
836  ret += d;
837  return ret;
838  }
839 
840  difference_type operator- (MultiIterator const & d) const
841  {
842  return (m_ptr - d.m_ptr);
843  }
844 
845  MultiIterator operator- (difference_type n) const
846  {
847  MultiIterator ret = *this;
848  ret -= n;
849  return ret;
850  }
851 
852  MultiIterator operator- (multi_difference_type const & d) const
853  {
854  MultiIterator ret = *this;
855  ret -= d;
856  return ret;
857  }
858 
859  reference operator[] (difference_type n) const
860  {
861  return m_ptr [n];
862  }
863 
864  reference operator[] (multi_difference_type const & d) const
865  {
866  return m_ptr [d[level]];
867  }
868 
869  reference operator* () const
870  {
871  return *m_ptr;
872  }
873 
874  pointer get () const
875  {
876  return m_ptr;
877  }
878 
879  pointer operator->() const
880  {
881  return &(operator*());
882  }
883 
884  bool operator!= (const MultiIterator &rhs) const
885  {
886  return m_ptr != rhs.m_ptr;
887  }
888 
889  bool operator== (const MultiIterator &rhs) const
890  {
891  return m_ptr == rhs.m_ptr;
892  }
893 
894  bool operator< (const MultiIterator &rhs) const
895  {
896  return m_ptr < rhs.m_ptr;
897  }
898 
899  bool operator<= (const MultiIterator &rhs) const
900  {
901  return m_ptr <= rhs.m_ptr;
902  }
903 
904  bool operator> (const MultiIterator &rhs) const
905  {
906  return m_ptr > rhs.m_ptr;
907  }
908 
909  bool operator>= (const MultiIterator &rhs) const
910  {
911  return m_ptr >= rhs.m_ptr;
912  }
913 
914  iterator iteratorForDimension(unsigned int d) const
915  {
916  vigra_precondition(d == 0,
917  "MultiIterator<1>::iteratorForDimension(d): d == 0 required");
918  const difference_type stride = 1;
919  return iterator(m_ptr, &stride, 0);
920  }
921 
922  template <unsigned int K>
923  MultiIterator<K+1, T, REFERENCE, POINTER> &
924  dim()
925  {
926  return *this;
927  }
928 
929  MultiIterator<1, T, REFERENCE, POINTER> &
930  dim0() { return *this; }
931 
932  protected:
933 
934  difference_type
935  total_stride(typename multi_difference_type::const_iterator d) const
936  {
937  return d[level];
938  }
939 };
940 
941 /********************************************************/
942 /* */
943 /* MultiIterator<2> */
944 /* */
945 /********************************************************/
946 
947 //
948 template <class T, class REFERENCE, class POINTER>
949 class MultiIterator<2, T, REFERENCE, POINTER>
950 #ifndef DOXYGEN // doxygen doesn't understand this inheritance
951 : public MultiIterator<1, T, REFERENCE, POINTER>
952 #endif
953 {
954  public:
955 
956  typedef MultiIterator<1, T, REFERENCE, POINTER> base_type;
957  enum { level = 1 };
958  typedef T value_type;
959  typedef REFERENCE reference;
960  typedef const value_type &const_reference;
961  typedef POINTER pointer;
962  typedef const value_type *const_pointer;
964  typedef MultiIteratorStrideTraits<POINTER> stride_traits;
965  typedef typename stride_traits::stride_type difference_type;
966  typedef typename stride_traits::stride_array_type difference_array_type;
967  typedef typename stride_traits::shape_array_type shape_array_type;
968  typedef base_type next_type;
969  typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
970  typedef multi_dimensional_traverser_tag iterator_category;
971 
972  protected:
973  difference_array_type m_stride;
974  shape_array_type m_shape;
975 
976  public:
977  /* use default copy constructor and assignment operator */
978 
979  MultiIterator ()
980  : base_type (),
981  m_stride (0), m_shape (0)
982  {}
983 
984  MultiIterator (pointer ptr,
985  const difference_array_type & stride,
986  const shape_array_type & shape)
987  : base_type (ptr, stride, shape),
988  m_stride (stride), m_shape (shape)
989  {}
990 
991  void operator++ ()
992  {
993  this->m_ptr += m_stride [level];
994  }
995 
996  void operator-- ()
997  {
998  this->m_ptr -= m_stride [level];
999  }
1000 
1002  {
1003  MultiIterator ret = *this;
1004  ++(*this);
1005  return ret;
1006  }
1007 
1009  {
1010  MultiIterator ret = *this;
1011  --(*this);
1012  return ret;
1013  }
1014 
1015  MultiIterator & operator+= (difference_type n)
1016  {
1017  this->m_ptr += n * m_stride [level];
1018  return *this;
1019  }
1020 
1021  MultiIterator & operator+= (multi_difference_type const & d)
1022  {
1023  this->m_ptr += total_stride(d.begin());
1024  return *this;
1025  }
1026 
1027  MultiIterator &operator-= (difference_type n)
1028  {
1029  this->m_ptr -= n * m_stride [level];
1030  return *this;
1031  }
1032 
1033  MultiIterator & operator-= (multi_difference_type const & d)
1034  {
1035  this->m_ptr -= total_stride(d.begin());
1036  return *this;
1037  }
1038 
1039  MultiIterator operator+ (difference_type n) const
1040  {
1041  MultiIterator ret = *this;
1042  ret += n;
1043  return ret;
1044  }
1045 
1046  MultiIterator operator+ (multi_difference_type const & d) const
1047  {
1048  MultiIterator ret = *this;
1049  ret += d;
1050  return ret;
1051  }
1052 
1053  difference_type operator- (MultiIterator const & d) const
1054  {
1055  return (this->m_ptr - d.m_ptr) / this->m_stride[level];
1056  }
1057 
1058  MultiIterator operator- (difference_type n) const
1059  {
1060  MultiIterator ret = *this;
1061  ret -= n;
1062  return ret;
1063  }
1064 
1065  MultiIterator operator- (multi_difference_type const & d) const
1066  {
1067  MultiIterator ret = *this;
1068  ret -= d;
1069  return ret;
1070  }
1071 
1072  reference operator[] (difference_type n) const
1073  {
1074  return this->m_ptr [n*m_stride [level]];
1075  }
1076 
1077  reference operator[] (multi_difference_type const & d) const
1078  {
1079  return this->m_ptr [total_stride(d.begin())];
1080  }
1081 
1082  next_type begin () const
1083  {
1084  return *this;
1085  }
1086 
1087  next_type end () const
1088  {
1089  next_type ret = *this;
1090  ret += m_shape [level-1];
1091  return ret;
1092  }
1093 
1094  iterator iteratorForDimension(unsigned int d) const
1095  {
1096  vigra_precondition(d <= level,
1097  "MultiIterator<N>::iteratorForDimension(d): d < N required");
1098  return iterator(this->m_ptr, stride_traits::shift(m_stride, d), 0);
1099  }
1100 
1101  template <unsigned int K>
1102  MultiIterator<K+1, T, REFERENCE, POINTER> &
1103  dim()
1104  {
1105  return *this;
1106  }
1107 
1108  MultiIterator<1, T, REFERENCE, POINTER> &
1109  dim0() { return *this; }
1110  MultiIterator<2, T, REFERENCE, POINTER> &
1111  dim1() { return *this; }
1112 
1113  protected:
1114 
1115  difference_type
1116  total_stride(typename multi_difference_type::const_iterator d) const
1117  {
1118  return d[level]*m_stride[level] + base_type::total_stride(d);
1119  }
1120 };
1121 
1122 /********************************************************/
1123 /* */
1124 /* MultiIterator<N> */
1125 /* */
1126 /********************************************************/
1127 
1128 /** \brief A multi-dimensional hierarchical iterator to be used with
1129  \ref vigra::MultiArrayView if it is not strided.
1130 
1131  See \ref MultiIteratorPage for further documentation.
1132 
1133  <b>\#include</b> <vigra/multi_iterator.hxx> <br>
1134  Namespace: vigra
1135 */
1136 template <unsigned int N, class T, class REFERENCE, class POINTER>
1137 class MultiIterator
1138 #ifndef DOXYGEN // doxygen doesn't understand this inheritance
1139 : public MultiIterator<N-1, T, REFERENCE, POINTER>
1140 #endif
1141 {
1142 public:
1143 
1144  /** the type of the parent in the inheritance hierarchy.
1145  */
1146  typedef MultiIterator<N-1, T, REFERENCE, POINTER> base_type;
1147 
1148  /** the iterator's level in the dimension hierarchy
1149  */
1150  enum { level = N-1 };
1151 
1152  /** the iterator's value type
1153  */
1154  typedef T value_type;
1155 
1156  /** reference type (result of operator[])
1157  */
1158  typedef REFERENCE reference;
1159 
1160  /** const reference type (result of operator[] const)
1161  */
1162  typedef const value_type &const_reference;
1163 
1164  /** pointer type
1165  */
1166  typedef POINTER pointer;
1167 
1168  /** const pointer type
1169  */
1170  typedef const value_type *const_pointer;
1171 
1172  /** multi difference type
1173  (used for offsetting along all axes simultaneously)
1174  */
1176 
1177  /** difference type (used for offsetting)
1178  */
1179 #ifndef DOXYGEN
1180  typedef MultiIteratorStrideTraits<POINTER> stride_traits;
1181  typedef typename stride_traits::stride_type difference_type;
1182  typedef typename stride_traits::stride_array_type difference_array_type;
1183  typedef typename stride_traits::shape_array_type shape_array_type;
1184 #else
1186 #endif
1187 
1188  /** the MultiIterator for the next lower dimension.
1189  */
1190  typedef base_type next_type;
1191 
1192  /** the 1-dimensional iterator for this iterator hierarchy
1193  (result of iteratorForDimension()).
1194  */
1196 
1197  /** the iterator tag (image traverser)
1198  */
1199  typedef multi_dimensional_traverser_tag iterator_category;
1200 
1201  /* use default copy constructor and assignment operator */
1202 
1203  /** default constructor.
1204  */
1206  {}
1207 
1208  /** construct from pointer, strides (offset of a sample to the
1209  next) for every dimension, and the shape.
1210  */
1211  MultiIterator (pointer ptr,
1212  const difference_array_type & stride,
1213  const shape_array_type & shape)
1214  : base_type (ptr, stride, shape)
1215  {}
1216 
1217 
1218  /** prefix-increment the iterator in its current dimension
1219  */
1221  {
1222  this->m_ptr += this->m_stride [level];
1223  }
1224 
1225  /** prefix-decrement the iterator in its current dimension
1226  */
1228  {
1229  this->m_ptr -= this->m_stride [level];
1230  }
1231 
1232  /** postfix-increment the iterator in its current dimension
1233  */
1235  {
1236  MultiIterator ret = *this;
1237  ++(*this);
1238  return ret;
1239  }
1240 
1241  /** postfix-decrement the iterator in its current dimension
1242  */
1244  {
1245  MultiIterator ret = *this;
1246  --(*this);
1247  return ret;
1248  }
1249 
1250  /** increment the iterator in its current dimension
1251  by the given value.
1252  */
1253  MultiIterator & operator+= (difference_type n)
1254  {
1255  this->m_ptr += n * this->m_stride [level];
1256  return *this;
1257  }
1258 
1259  /** increment the iterator in all dimensions
1260  by the given offset.
1261  */
1262  MultiIterator & operator+= (multi_difference_type const & d)
1263  {
1264  this->m_ptr += total_stride(d.begin());
1265  return *this;
1266  }
1267 
1268  /** decrement the iterator in its current dimension
1269  by the given value.
1270  */
1271  MultiIterator & operator-= (difference_type n)
1272  {
1273  this->m_ptr -= n * this->m_stride [level];
1274  return *this;
1275  }
1276 
1277  /** decrement the iterator in all dimensions
1278  by the given offset.
1279  */
1280  MultiIterator & operator-= (multi_difference_type const & d)
1281  {
1282  this->m_ptr -= total_stride(d.begin());
1283  return *this;
1284  }
1285 
1286  /** addition within current dimension
1287  */
1288  MultiIterator operator+ (difference_type n) const
1289  {
1290  MultiIterator ret = *this;
1291  ret += n;
1292  return ret;
1293  }
1294 
1295  /** addition along all dimensions
1296  */
1297  MultiIterator operator+ (multi_difference_type const & d) const
1298  {
1299  MultiIterator ret = *this;
1300  ret += d;
1301  return ret;
1302  }
1303 
1304  /** difference of two iterators in the current dimension.
1305  The result of this operation is undefined if the iterator
1306  doesn't point to element 0 in all dimensions below its current dimension.
1307  */
1308  difference_type operator- (MultiIterator const & d) const
1309  {
1310  return (this->m_ptr - d.m_ptr) / this->m_stride[level];
1311  }
1312 
1313  /** subtraction within current dimension
1314  */
1315  MultiIterator operator- (difference_type n) const
1316  {
1317  MultiIterator ret = *this;
1318  ret -= n;
1319  return ret;
1320  }
1321 
1322  /** subtraction along all dimensions
1323  */
1324  MultiIterator operator- (multi_difference_type const & d) const
1325  {
1326  MultiIterator ret = *this;
1327  ret -= d;
1328  return ret;
1329  }
1330 
1331 #ifdef DOXYGEN /* documentation only: operators *, ->, ==, !=, <, <=, >, >= are inherited */
1332  /** derefenrence item
1333  */
1334  reference operator* () const;
1335 
1336  /** get address of current item
1337  */
1338  pointer get () const;
1339 
1340  /** call method of current item
1341  */
1342  pointer operator->() const;
1343 
1344  /** inequality. True if iterators reference different items.
1345  */
1346  bool operator!= (const MultiIterator &rhs) const;
1347 
1348  /** equality. True if iterators reference the same items.
1349  */
1350  bool operator== (const MultiIterator &rhs) const;
1351 
1352  /** less than.
1353  */
1354  bool operator< (const MultiIterator &rhs) const;
1355 
1356  /** less or equal.
1357  */
1358  bool operator<= (const MultiIterator &rhs) const;
1359 
1360  /** greater than.
1361  */
1362  bool operator> (const MultiIterator &rhs) const;
1363 
1364  /** greater or equal.
1365  */
1366  bool operator>= (const MultiIterator &rhs) const;
1367 #endif
1368 
1369  /** access the array element at the given offset in
1370  the current dimension.
1371  */
1372  reference operator[] (difference_type n) const
1373  {
1374  return this->m_ptr [n* this->m_stride [level]];
1375  }
1376 
1377  /** access the array element at the given offset.
1378  */
1379  reference operator[] (multi_difference_type const & d) const
1380  {
1381  return this->m_ptr [total_stride(d.begin())];
1382  }
1383 
1384  /** Return the (N-1)-dimensional multi-iterator that points to
1385  the first (N-1)-dimensional subarray of the
1386  N-dimensional array this iterator is referring to.
1387  The result is only valid if this iterator refers to location
1388  0 in <em>all</em> dimensions below its current dimension N,
1389  otherwise it is undefined. Usage:
1390 
1391  \code
1392 
1393  MultiIterator<2, int> outer = ...; // this iterator
1394 
1395  MultiIterator<2, int>::next_type inner = outer.begin();
1396  for(; inner != outer.end(); ++inner)
1397  {
1398  // manipulate current 1D subimage
1399  }
1400  \endcode
1401  */
1402  next_type begin () const
1403  {
1404  return *this;
1405  }
1406 
1407  /** Return the (N-1)-dimensional multi-iterator that points beyond
1408  the last (N-1)-dimensional subarray of the
1409  N-dimensional array this iterator is referring to.
1410  The result is only valid if this iterator refers to location
1411  0 in <em>all</em> dimensions below its current dimension N,
1412  otherwise it is undefined.
1413  */
1414  next_type end () const
1415  {
1416  next_type ret = *this;
1417  ret += this->m_shape [level-1];
1418  return ret;
1419  }
1420 
1421  /** Get a 1-dimensional, STL-compatible iterator for the
1422  given dimension, pointing to the current element of <TT>this</TT>.
1423  Usage:
1424 
1425  \code
1426 
1427  MultiIterator<3, int> outer = ...; // this iterator
1428 
1429  MultiIterator<3, int>::iterator i = outer.iteratorForDimension(1);
1430  MultiIterator<3, int>::iterator end = i + height;
1431  for(; i != end; ++i)
1432  {
1433  // go down the current column starting at the location of 'outer'
1434  }
1435  \endcode
1436  */
1437  iterator iteratorForDimension(unsigned int d) const
1438  {
1439  vigra_precondition(d <= level,
1440  "MultiIterator<N>::iteratorForDimension(d): d < N required");
1441  return iterator(this->m_ptr, stride_traits::shift(this->m_stride, d),0);
1442  }
1443  /** Return the multi-iterator that operates on dimension K in order
1444  to manipulate this dimension directly. Usage:
1445 
1446  \code
1447 
1448  MultiIterator<3, int> i3 = ...;
1449 
1450  i3.template dim<2>()++; // increment outer dimension
1451  i3.template dim<0>()++; // increment inner dimension
1452  \endcode
1453 
1454  For convenience, the same functionality is also available
1455  as <tt>dim0()</tt>, <tt>dim1()</tt> etc. up to <tt>dim4()</tt>:
1456 
1457  \code
1458 
1459  MultiIterator<3, int> i3 = ...;
1460 
1461  i3.dim2()++; // increment outer dimension
1462  i3.dim0()++; // increment inner dimension
1463  \endcode
1464  */
1465  template <unsigned int K>
1468  {
1469  return *this;
1470  }
1471 
1473  dim0() { return *this; }
1474  MultiIterator<2, T, REFERENCE, POINTER> &
1475  dim1() { return *this; }
1476  MultiIterator<3, T, REFERENCE, POINTER> &
1477  dim2() { return *this; }
1478  MultiIterator<4, T, REFERENCE, POINTER> &
1479  dim3() { return *this; }
1480  MultiIterator<5, T, REFERENCE, POINTER> &
1481  dim4() { return *this; }
1482 
1483  protected:
1484 
1485  difference_type
1486  total_stride(typename multi_difference_type::const_iterator d) const
1487  {
1488  return d[level]*this->m_stride[level] + base_type::total_stride(d);
1489  }
1490 
1491 };
1492 
1493 /********************************************************/
1494 /* */
1495 /* StridedMultiIterator */
1496 /* */
1497 /********************************************************/
1498 
1499 /********************************************************/
1500 /* */
1501 /* StridedMultiIterator<1> */
1502 /* */
1503 /********************************************************/
1504 
1505 //
1506 template <class T, class REFERENCE, class POINTER>
1507 class StridedMultiIterator<1, T, REFERENCE, POINTER>
1508 {
1509  public:
1510  enum { level = 0 };
1511  typedef T value_type;
1512  typedef REFERENCE reference;
1513  typedef const value_type &const_reference;
1514  typedef POINTER pointer;
1515  typedef const value_type *const_pointer;
1516  typedef typename MultiArrayShape<1>::type multi_difference_type;
1517  typedef MultiIteratorStrideTraits<POINTER> stride_traits;
1518  typedef typename stride_traits::stride_type difference_type;
1519  typedef typename stride_traits::stride_array_type difference_array_type;
1520  typedef typename stride_traits::shape_array_type shape_array_type;
1521  typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
1522  typedef std::random_access_iterator_tag iterator_category;
1523 
1524  protected:
1525  pointer m_ptr;
1526  difference_type m_stride;
1527 
1528  /* use default copy constructor and assignment operator */
1529 
1530  public:
1532  : m_ptr (0), m_stride (0)
1533  {}
1534 
1535  StridedMultiIterator (pointer ptr,
1536  const difference_array_type & stride,
1537  const shape_array_type &)
1538  : m_ptr (ptr), m_stride (stride [level])
1539  {}
1540 
1541  void operator++ ()
1542  {
1543  m_ptr += m_stride;
1544  }
1545 
1546  void operator-- ()
1547  {
1548  m_ptr -= m_stride;
1549  }
1550 
1552  {
1553  StridedMultiIterator ret = *this;
1554  ++(*this);
1555  return ret;
1556  }
1557 
1559  {
1560  StridedMultiIterator ret = *this;
1561  --(*this);
1562  return ret;
1563  }
1564 
1565  StridedMultiIterator &operator+= (difference_type n)
1566  {
1567  m_ptr += n * m_stride;
1568  return *this;
1569  }
1570 
1571  StridedMultiIterator & operator+= (multi_difference_type const & d)
1572  {
1573  m_ptr += d[level] * m_stride;
1574  return *this;
1575  }
1576 
1577  StridedMultiIterator &operator-= (difference_type n)
1578  {
1579  m_ptr -= n * m_stride;
1580  return *this;
1581  }
1582 
1583  StridedMultiIterator & operator-= (multi_difference_type const & d)
1584  {
1585  m_ptr -= d[level] * m_stride;
1586  return *this;
1587  }
1588 
1589  StridedMultiIterator operator+ (difference_type n) const
1590  {
1591  StridedMultiIterator ret = *this;
1592  ret += n;
1593  return ret;
1594  }
1595 
1596  StridedMultiIterator operator+ (multi_difference_type const & d) const
1597  {
1598  StridedMultiIterator ret = *this;
1599  ret += d;
1600  return ret;
1601  }
1602 
1603  difference_type operator- (StridedMultiIterator const & d) const
1604  {
1605  return (m_ptr - d.m_ptr) / m_stride;
1606  }
1607 
1608  StridedMultiIterator operator- (difference_type n) const
1609  {
1610  StridedMultiIterator ret = *this;
1611  ret -= n;
1612  return ret;
1613  }
1614 
1615  StridedMultiIterator operator- (multi_difference_type const & d) const
1616  {
1617  StridedMultiIterator ret = *this;
1618  ret -= d;
1619  return ret;
1620  }
1621 
1622  reference operator[] (difference_type n) const
1623  {
1624  return m_ptr [n*m_stride];
1625  }
1626 
1627  reference operator[] (multi_difference_type const & d) const
1628  {
1629  return m_ptr [d[level]*m_stride];
1630  }
1631 
1632  reference operator* () const
1633  {
1634  return *m_ptr;
1635  }
1636 
1637  pointer get () const
1638  {
1639  return m_ptr;
1640  }
1641 
1642  pointer operator->() const
1643  {
1644  return &(operator*());
1645  }
1646 
1647  bool operator!= (const StridedMultiIterator &rhs) const
1648  {
1649  return m_ptr != rhs.m_ptr;
1650  }
1651 
1652  bool operator== (const StridedMultiIterator &rhs) const
1653  {
1654  return m_ptr == rhs.m_ptr;
1655  }
1656 
1657  bool operator< (const StridedMultiIterator &rhs) const
1658  {
1659  return m_ptr < rhs.m_ptr;
1660  }
1661 
1662  bool operator<= (const StridedMultiIterator &rhs) const
1663  {
1664  return m_ptr <= rhs.m_ptr;
1665  }
1666 
1667  bool operator> (const StridedMultiIterator &rhs) const
1668  {
1669  return m_ptr > rhs.m_ptr;
1670  }
1671 
1672  bool operator>= (const StridedMultiIterator &rhs) const
1673  {
1674  return m_ptr >= rhs.m_ptr;
1675  }
1676 
1677  iterator iteratorForDimension(unsigned int d) const
1678  {
1679  vigra_precondition(d == 0,
1680  "StridedMultiIterator<1>::iteratorForDimension(d): d == 0 required");
1681  const difference_type stride = 1;
1682  return iterator(m_ptr, &stride, 0);
1683  }
1684 
1685  template <unsigned int K>
1686  StridedMultiIterator<K+1, T, REFERENCE, POINTER> &
1687  dim()
1688  {
1689  return *this;
1690  }
1691 
1692  StridedMultiIterator<1, T, REFERENCE, POINTER> &
1693  dim0() { return *this; }
1694 
1695  protected:
1696 
1697  difference_type
1698  total_stride(typename multi_difference_type::const_iterator d) const
1699  {
1700  return d[level] * m_stride;
1701  }
1702 };
1703 
1704 /********************************************************/
1705 /* */
1706 /* StridedMultiIterator<2> */
1707 /* */
1708 /********************************************************/
1709 
1710 //
1711 template <class T, class REFERENCE, class POINTER>
1712 class StridedMultiIterator<2, T, REFERENCE, POINTER>
1713 #ifndef DOXYGEN // doxygen doesn't understand this inheritance
1714 : public StridedMultiIterator<1, T, REFERENCE, POINTER>
1715 #endif
1716 {
1717  public:
1718 
1719  typedef StridedMultiIterator<1, T, REFERENCE, POINTER> base_type;
1720  enum { level = 1 };
1721  typedef T value_type;
1722  typedef REFERENCE reference;
1723  typedef const value_type &const_reference;
1724  typedef POINTER pointer;
1725  typedef const value_type *const_pointer;
1727  typedef MultiIteratorStrideTraits<POINTER> stride_traits;
1728  typedef typename stride_traits::stride_type difference_type;
1729  typedef typename stride_traits::stride_array_type difference_array_type;
1730  typedef typename stride_traits::shape_array_type shape_array_type;
1731  typedef base_type next_type;
1732  typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
1733  typedef multi_dimensional_traverser_tag iterator_category;
1734 
1735  protected:
1736  difference_array_type m_stride;
1737  shape_array_type m_shape;
1738 
1739  public:
1740  /* use default copy constructor and assignment operator */
1741 
1743  : base_type (),
1744  m_stride (0), m_shape (0)
1745  {}
1746 
1747  StridedMultiIterator (pointer ptr,
1748  const difference_array_type & stride,
1749  const shape_array_type & shape)
1750  : base_type (ptr, stride, shape),
1751  m_stride (stride), m_shape (shape)
1752  {}
1753 
1754  void operator++ ()
1755  {
1756  this->m_ptr += m_stride [level];
1757  }
1758 
1759  void operator-- ()
1760  {
1761  this->m_ptr -= m_stride [level];
1762  }
1763 
1765  {
1766  StridedMultiIterator ret = *this;
1767  ++(*this);
1768  return ret;
1769  }
1770 
1772  {
1773  StridedMultiIterator ret = *this;
1774  --(*this);
1775  return ret;
1776  }
1777 
1778  StridedMultiIterator & operator+= (difference_type n)
1779  {
1780  this->m_ptr += n * m_stride [level];
1781  return *this;
1782  }
1783 
1784  StridedMultiIterator & operator+= (multi_difference_type const & d)
1785  {
1786  this->m_ptr += total_stride(d.begin());
1787  return *this;
1788  }
1789 
1790  StridedMultiIterator &operator-= (difference_type n)
1791  {
1792  this->m_ptr -= n * m_stride [level];
1793  return *this;
1794  }
1795 
1796  StridedMultiIterator & operator-= (multi_difference_type const & d)
1797  {
1798  this->m_ptr -= total_stride(d.begin());
1799  return *this;
1800  }
1801 
1802  StridedMultiIterator operator+ (difference_type n) const
1803  {
1804  StridedMultiIterator ret = *this;
1805  ret += n;
1806  return ret;
1807  }
1808 
1809  StridedMultiIterator operator+ (multi_difference_type const & d) const
1810  {
1811  StridedMultiIterator ret = *this;
1812  ret += d;
1813  return ret;
1814  }
1815 
1816  difference_type operator- (StridedMultiIterator const & d) const
1817  {
1818  return (this->m_ptr - d.m_ptr) / this->m_stride[level];
1819  }
1820 
1821  StridedMultiIterator operator- (difference_type n) const
1822  {
1823  StridedMultiIterator ret = *this;
1824  ret -= n;
1825  return ret;
1826  }
1827 
1828  StridedMultiIterator operator- (multi_difference_type const & d) const
1829  {
1830  StridedMultiIterator ret = *this;
1831  ret -= d;
1832  return ret;
1833  }
1834 
1835  reference operator[] (difference_type n) const
1836  {
1837  return this->m_ptr [n*m_stride [level]];
1838  }
1839 
1840  reference operator[] (multi_difference_type const & d) const
1841  {
1842  return this->m_ptr [total_stride(d.begin())];
1843  }
1844 
1845  next_type begin () const
1846  {
1847  return *this;
1848  }
1849 
1850  next_type end () const
1851  {
1852  next_type ret = *this;
1853  ret += m_shape [level-1];
1854  return ret;
1855  }
1856 
1857  iterator iteratorForDimension(unsigned int d) const
1858  {
1859  vigra_precondition(d <= level,
1860  "StridedMultiIterator<N>::iteratorForDimension(d): d < N required");
1861  return iterator(this->m_ptr, stride_traits::shift(m_stride, d), 0);
1862  }
1863 
1864  template <unsigned int K>
1865  StridedMultiIterator<K+1, T, REFERENCE, POINTER> &
1866  dim()
1867  {
1868  return *this;
1869  }
1870 
1871  StridedMultiIterator<1, T, REFERENCE, POINTER> &
1872  dim0() { return *this; }
1873  StridedMultiIterator<2, T, REFERENCE, POINTER> &
1874  dim1() { return *this; }
1875 
1876  protected:
1877 
1878  difference_type
1879  total_stride(typename multi_difference_type::const_iterator d) const
1880  {
1881  return d[level]*m_stride[level] + base_type::total_stride(d);
1882  }
1883 };
1884 
1885 /********************************************************/
1886 /* */
1887 /* StridedMultiIterator<N> */
1888 /* */
1889 /********************************************************/
1890 
1891 /** \brief A multi-dimensional hierarchical iterator to be used with
1892  \ref vigra::MultiArrayView if it is not strided.
1893 
1894  See \ref MultiIteratorPage for further documentation.
1895 
1896  <b>\#include</b> <vigra/multi_iterator.hxx> <br>
1897  Namespace: vigra
1898 */
1899 template <unsigned int N, class T, class REFERENCE, class POINTER>
1900 class StridedMultiIterator
1901 #ifndef DOXYGEN // doxygen doesn't understand this inheritance
1902 : public StridedMultiIterator<N-1, T, REFERENCE, POINTER>
1903 #endif
1904 {
1905 public:
1906 
1907  /** the type of the parent in the inheritance hierarchy.
1908  */
1909  typedef StridedMultiIterator<N-1, T, REFERENCE, POINTER> base_type;
1910 
1911  /** the iterator's level in the dimension hierarchy
1912  */
1913  enum { level = N-1 };
1914 
1915  /** the iterator's value type
1916  */
1917  typedef T value_type;
1918 
1919  /** reference type (result of operator[])
1920  */
1921  typedef REFERENCE reference;
1922 
1923  /** const reference type (result of operator[] const)
1924  */
1925  typedef const value_type &const_reference;
1926 
1927  /** pointer type
1928  */
1929  typedef POINTER pointer;
1930 
1931  /** const pointer type
1932  */
1933  typedef const value_type *const_pointer;
1934 
1935  /** multi difference type
1936  (used for offsetting along all axes simultaneously)
1937  */
1939 
1940  /** difference type (used for offsetting)
1941  */
1942 #ifndef DOXYGEN
1943  typedef MultiIteratorStrideTraits<POINTER> stride_traits;
1944  typedef typename stride_traits::stride_type difference_type;
1945  typedef typename stride_traits::stride_array_type difference_array_type;
1946 #else
1948 #endif
1949 
1950  /** the StridedMultiIterator for the next lower dimension.
1951  */
1952  typedef base_type next_type;
1953 
1954  /** the 1-dimensional iterator for this iterator hierarchy
1955  (result of iteratorForDimension()).
1956  */
1958 
1959  /** the iterator tag (image traverser)
1960  */
1961  typedef multi_dimensional_traverser_tag iterator_category;
1962 
1963  /* use default copy constructor and assignment operator */
1964 
1965  /** default constructor.
1966  */
1968  {}
1969 
1970  /** construct from pointer, strides (offset of a sample to the
1971  next) for every dimension, and the shape.
1972  */
1973  StridedMultiIterator (pointer ptr,
1974  const difference_array_type & stride,
1975  const difference_array_type & shape)
1976  : base_type (ptr, stride, shape)
1977  {}
1978 
1979 
1980  /** prefix-increment the iterator in its current dimension
1981  */
1983  {
1984  this->m_ptr += this->m_stride [level];
1985  }
1986 
1987  /** prefix-decrement the iterator in its current dimension
1988  */
1990  {
1991  this->m_ptr -= this->m_stride [level];
1992  }
1993 
1994  /** postfix-increment the iterator in its current dimension
1995  */
1997  {
1998  StridedMultiIterator ret = *this;
1999  ++(*this);
2000  return ret;
2001  }
2002 
2003  /** postfix-decrement the iterator in its current dimension
2004  */
2006  {
2007  StridedMultiIterator ret = *this;
2008  --(*this);
2009  return ret;
2010  }
2011 
2012  /** increment the iterator in its current dimension
2013  by the given value.
2014  */
2015  StridedMultiIterator & operator+= (difference_type n)
2016  {
2017  this->m_ptr += n * this->m_stride [level];
2018  return *this;
2019  }
2020 
2021  /** increment the iterator in all dimensions
2022  by the given offset.
2023  */
2024  StridedMultiIterator & operator+= (multi_difference_type const & d)
2025  {
2026  this->m_ptr += total_stride(d.begin());
2027  return *this;
2028  }
2029 
2030  /** decrement the iterator in its current dimension
2031  by the given value.
2032  */
2033  StridedMultiIterator & operator-= (difference_type n)
2034  {
2035  this->m_ptr -= n * this->m_stride [level];
2036  return *this;
2037  }
2038 
2039  /** decrement the iterator in all dimensions
2040  by the given offset.
2041  */
2042  StridedMultiIterator & operator-= (multi_difference_type const & d)
2043  {
2044  this->m_ptr -= total_stride(d.begin());
2045  return *this;
2046  }
2047 
2048  /** addition within current dimension
2049  */
2050  StridedMultiIterator operator+ (difference_type n) const
2051  {
2052  StridedMultiIterator ret = *this;
2053  ret += n;
2054  return ret;
2055  }
2056 
2057  /** addition along all dimensions
2058  */
2059  StridedMultiIterator operator+ (multi_difference_type const & d) const
2060  {
2061  StridedMultiIterator ret = *this;
2062  ret += d;
2063  return ret;
2064  }
2065 
2066  /** difference of two iterators in the current dimension.
2067  The result of this operation is undefined if the iterator
2068  doesn't point to element 0 in all dimensions below its current dimension.
2069  */
2070  difference_type operator- (StridedMultiIterator const & d) const
2071  {
2072  return (this->m_ptr - d.m_ptr) / this->m_stride[level];
2073  }
2074 
2075  /** subtraction within current dimension
2076  */
2077  StridedMultiIterator operator- (difference_type n) const
2078  {
2079  StridedMultiIterator ret = *this;
2080  ret -= n;
2081  return ret;
2082  }
2083 
2084  /** subtraction along all dimensions
2085  */
2086  StridedMultiIterator operator- (multi_difference_type const & d) const
2087  {
2088  StridedMultiIterator ret = *this;
2089  ret -= d;
2090  return ret;
2091  }
2092 
2093 #ifdef DOXYGEN /* documentation only: operators *, ->, ==, !=, <, <=, >, >= are inherited */
2094  /** derefenrence item
2095  */
2096  reference operator* () const;
2097 
2098  /** get address of current item
2099  */
2100  pointer get () const;
2101 
2102  /** call method of current item
2103  */
2104  pointer operator->() const;
2105 
2106  /** inequality. True if iterators reference different items.
2107  */
2108  bool operator!= (const StridedMultiIterator &rhs) const;
2109 
2110  /** equality. True if iterators reference the same items.
2111  */
2112  bool operator== (const StridedMultiIterator &rhs) const;
2113 
2114  /** less than.
2115  */
2116  bool operator< (const StridedMultiIterator &rhs) const;
2117 
2118  /** less or equal.
2119  */
2120  bool operator<= (const StridedMultiIterator &rhs) const;
2121 
2122  /** greater than.
2123  */
2124  bool operator> (const StridedMultiIterator &rhs) const;
2125 
2126  /** greater or equal.
2127  */
2128  bool operator>= (const StridedMultiIterator &rhs) const;
2129 #endif
2130 
2131  /** access the array element at the given offset in
2132  the current dimension.
2133  */
2134  reference operator[] (difference_type n) const
2135  {
2136  return this->m_ptr [n* this->m_stride [level]];
2137  }
2138 
2139  /** access the array element at the given offset.
2140  */
2141  reference operator[] (multi_difference_type const & d) const
2142  {
2143  return this->m_ptr [total_stride(d.begin())];
2144  }
2145 
2146  /** Return the (N-1)-dimensional multi-iterator that points to
2147  the first (N-1)-dimensional subarray of the
2148  N-dimensional array this iterator is referring to.
2149  The result is only valid if this iterator refers to location
2150  0 in <em>all</em> dimensions below its current dimension N,
2151  otherwise it is undefined. Usage:
2152 
2153  \code
2154 
2155  StridedMultiIterator<2, int> outer = ...; // this iterator
2156 
2157  StridedMultiIterator<2, int>::next_type inner = outer.begin();
2158  for(; inner != outer.end(); ++inner)
2159  {
2160  // manipulate current 1D subimage
2161  }
2162  \endcode
2163  */
2164  next_type begin () const
2165  {
2166  return *this;
2167  }
2168 
2169  /** Return the (N-1)-dimensional multi-iterator that points beyond
2170  the last (N-1)-dimensional subarray of the
2171  N-dimensional array this iterator is referring to.
2172  The result is only valid if this iterator refers to location
2173  0 in <em>all</em> dimensions below its current dimension N,
2174  otherwise it is undefined.
2175  */
2176  next_type end () const
2177  {
2178  next_type ret = *this;
2179  ret += this->m_shape [level-1];
2180  return ret;
2181  }
2182 
2183  /** Get a 1-dimensional, STL-compatible iterator for the
2184  given dimension, pointing to the current element of <TT>this</TT>.
2185  Usage:
2186 
2187  \code
2188 
2189  StridedMultiIterator<3, int> outer = ...; // this iterator
2190 
2191  StridedMultiIterator<3, int>::iterator i = outer.iteratorForDimension(1);
2192  StridedMultiIterator<3, int>::iterator end = i + height;
2193  for(; i != end; ++i)
2194  {
2195  // go down the current column starting at the location of 'outer'
2196  }
2197  \endcode
2198  */
2199  iterator iteratorForDimension(unsigned int d) const
2200  {
2201  vigra_precondition(d <= level,
2202  "StridedMultiIterator<N>::iteratorForDimension(d): d < N required");
2203  return iterator(this->m_ptr, stride_traits::shift(this->m_stride, d),0);
2204  }
2205  /** Return the multi-iterator that operates on dimension K in order
2206  to manipulate this dimension directly. Usage:
2207 
2208  \code
2209 
2210  StridedMultiIterator<3, int> i3 = ...;
2211 
2212  i3.template dim<2>()++; // increment outer dimension
2213  i3.template dim<0>()++; // increment inner dimension
2214  \endcode
2215 
2216  For convenience, the same functionality is also available
2217  as <tt>dim0()</tt>, <tt>dim1()</tt> etc. up to <tt>dim4()</tt>:
2218 
2219  \code
2220 
2221  StridedMultiIterator<3, int> i3 = ...;
2222 
2223  i3.dim2()++; // increment outer dimension
2224  i3.dim0()++; // increment inner dimension
2225  \endcode
2226  */
2227  template <unsigned int K>
2230  {
2231  return *this;
2232  }
2233 
2235  dim0() { return *this; }
2236  StridedMultiIterator<2, T, REFERENCE, POINTER> &
2237  dim1() { return *this; }
2238  StridedMultiIterator<3, T, REFERENCE, POINTER> &
2239  dim2() { return *this; }
2240  StridedMultiIterator<4, T, REFERENCE, POINTER> &
2241  dim3() { return *this; }
2242  StridedMultiIterator<5, T, REFERENCE, POINTER> &
2243  dim4() { return *this; }
2244 
2245  protected:
2246 
2247  difference_type
2248  total_stride(typename multi_difference_type::const_iterator d) const
2249  {
2250  return d[level]*this->m_stride[level] + base_type::total_stride(d);
2251  }
2252 
2253 };
2254 
2255 //@}
2256 
2257 } // namespace vigra
2258 
2259 namespace std {
2260 
2261 template <unsigned int N, class T, class REFERENCE, class POINTER>
2262 ostream & operator<<(ostream & o, vigra::StridedScanOrderIterator<N, T, REFERENCE, POINTER> const & i)
2263 {
2264  o << *i;
2265  return o;
2266 }
2267 
2268 } // namespace std
2269 
2270 #endif // VIGRA_MULTI_ITERATOR_HXX

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.10.0 (Thu Jan 8 2015)