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

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