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

vigra/multi_iterator.hxx VIGRA

00001 /************************************************************************/
00002 /*                                                                      */
00003 /*     Copyright 2003-2008 by Gunnar Kedenburg and Ullrich Koethe       */
00004 /*                                                                      */
00005 /*    This file is part of the VIGRA computer vision library.           */
00006 /*    ( Version 1.3.0, Sep 10 2004 )                                    */
00007 /*    The VIGRA Website is                                              */
00008 /*        http://hci.iwr.uni-heidelberg.de/vigra/                       */
00009 /*    Please direct questions, bug reports, and contributions to        */
00010 /*        ullrich.koethe@iwr.uni-heidelberg.de    or                    */
00011 /*        vigra@informatik.uni-hamburg.de                               */
00012 /*                                                                      */
00013 /*    Permission is hereby granted, free of charge, to any person       */
00014 /*    obtaining a copy of this software and associated documentation    */
00015 /*    files (the "Software"), to deal in the Software without           */
00016 /*    restriction, including without limitation the rights to use,      */
00017 /*    copy, modify, merge, publish, distribute, sublicense, and/or      */
00018 /*    sell copies of the Software, and to permit persons to whom the    */
00019 /*    Software is furnished to do so, subject to the following          */
00020 /*    conditions:                                                       */
00021 /*                                                                      */
00022 /*    The above copyright notice and this permission notice shall be    */
00023 /*    included in all copies or substantial portions of the             */
00024 /*    Software.                                                         */
00025 /*                                                                      */
00026 /*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND    */
00027 /*    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES   */
00028 /*    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND          */
00029 /*    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT       */
00030 /*    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,      */
00031 /*    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      */
00032 /*    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR     */
00033 /*    OTHER DEALINGS IN THE SOFTWARE.                                   */                
00034 /*                                                                      */
00035 /************************************************************************/
00036 
00037 
00038 #ifndef VIGRA_MULTI_ITERATOR_HXX
00039 #define VIGRA_MULTI_ITERATOR_HXX
00040 
00041 #include <sys/types.h>
00042 #include "tinyvector.hxx"
00043 #include "iteratortags.hxx"
00044 
00045 namespace vigra {
00046 
00047 
00048 template <unsigned int N, class T, 
00049           class REFERENCE = T &, class POINTER = T *> class MultiIterator;
00050 template <unsigned int N, class T, 
00051           class REFERENCE = T &, class POINTER = T *> class StridedMultiIterator;
00052 
00053 /** \page MultiIteratorPage  Multi-dimensional Array Iterators
00054 
00055     General iterators for arrays of arbitrary dimension.
00056 
00057 
00058 <p>
00059 <UL style="list-style-image:url(documents/bullet.gif)">
00060 <LI> \ref vigra::MultiArrayShape
00061      <BR>&nbsp;&nbsp;&nbsp;<em>Difference type for \ref vigra::MultiArrayView or \ref vigra::MultiIterator</em>
00062 <LI> \ref vigra::MultiIterator
00063      <BR>&nbsp;&nbsp;&nbsp;<em>Iterator for unstrided \ref vigra::MultiArrayView</em>
00064 <LI> \ref vigra::StridedMultiIterator
00065      <BR>&nbsp;&nbsp;&nbsp;<em>Iterator for strided \ref vigra::MultiArrayView</em>
00066 <LI> \ref vigra::StridedScanOrderIterator
00067      <BR>&nbsp;&nbsp;&nbsp;<em>STL-compatible random access iterator for \ref vigra::MultiArrayView</em>
00068 <LI> \ref vigra::CoupledScanOrderIterator
00069      <BR>&nbsp;&nbsp;&nbsp;<em>Iterate over multiple images simultaneously in scan order</em>
00070 </UL>
00071 </p>
00072 
00073 <p>
00074     The Multidimensional Iterator concept allows navigation on arrays
00075     of arbitrary dimension. It provides two modes of iteration: 
00076     <em>direct traversal</em>, and <em>hierarchical traversal</em>.
00077     In general, hierarchical traversal will be faster, while only 
00078     direct traversal allows for true random access in all dimensions.
00079     Via the <tt>dim<K>()</tt> function, operations applying to a particular
00080     dimension can be used in the direct traversal mode. In contrast,
00081     direct traversal functions should not be used in the hierarchical mode
00082     because the hierarchical functions are only well-defined if the
00083     iterator points to element 0 in all dimensions below its current dimension.
00084     The current dimension of a <tt>MultiIterator<N, ...></tt> is <tt>N-1</tt>.
00085 </p>
00086 <h3>General Requirements for MultiIterator</h3>
00087 <p>
00088 <table border=2 cellspacing=0 cellpadding=2 width="100%">
00089 <tr><th colspan=2>
00090     Local Types
00091     </th><th>
00092     Meaning
00093     </th>
00094 </tr>
00095 <tr><td colspan=2>
00096     <tt>MultiIterator::value_type</tt></td><td>the underlying arrays's pixel type</td>
00097 </tr>
00098 <tr><td colspan=2>
00099     <tt>MultiIterator::reference</tt></td>
00100     <td>the iterator's reference type (return type of <TT>*iter</TT>). Will be
00101     <tt>value_type &</tt> for a mutable iterator, and convertible to
00102     <tt>value_type const &</tt> for a const iterator.</td>
00103 </tr>
00104 <tr><td colspan=2>
00105     <tt>MultiIterator::pointer</tt></td>
00106     <td>the iterator's pointer type (return type of <TT>iter.operator->()</TT>). Will be
00107     <tt>value_type *</tt> for a mutable iterator, and convertible to
00108     <tt>value_type const *</tt> for a const iterator.</td>
00109 </tr>
00110 <tr><td colspan=2>
00111     <tt>MultiIterator::iterator_category</tt></td>
00112     <td>the iterator tag (<tt>vigra::multi_dimensional_traverser_tag</tt>)</td>
00113 </tr>
00114 <tr><th>
00115     Operation
00116     </th><th>
00117     Result
00118     </th><th>
00119     Semantics
00120     </th>
00121 </tr>
00122 <tr><td colspan=2>
00123     <tt>MultiIterator k;</tt></td><td>default constructor</td>
00124 </tr>
00125 <tr><td colspan=2>
00126     <tt>MultiIterator k(i);</tt></td><td>copy constructor</td>
00127 </tr>
00128 <tr>
00129     <td><tt>k = i</tt></td>
00130     <td><tt>MultiIterator &</tt></td><td>assignment</td>
00131 </tr>
00132 <tr>
00133     <td><tt>i == j</tt></td><td><tt>bool</tt></td>
00134     <td>equality (iterators point to the same element)</td>
00135 </tr>
00136 <tr>
00137     <td><tt>i != j</tt></td><td><tt>bool</tt></td>
00138     <td>inequality (iterators don't point to the same element)</td>
00139 </tr>
00140 <tr>
00141     <td><tt>*i</tt></td><td><tt>MultiIterator::reference</tt></td>
00142     <td>access the current element</td>
00143 </tr>
00144 <tr>
00145     <td><tt>i->member()</tt></td><td>depends on operation</td>
00146     <td>call member function of underlying pixel type via <tt>operator-></tt> of iterator</td>
00147 </tr>
00148 </table>
00149 </p>
00150 <h3>Requirements for Direct Traversal</h3>
00151 <p>
00152 <table border=2 cellspacing=0 cellpadding=2 width="100%">
00153 <tr><th colspan=2>
00154     Local Types
00155     </th><th>
00156     Meaning
00157     </th>
00158 </tr>
00159 <tr><td colspan=2>
00160     <tt>MultiIterator::multi_difference_type</tt></td>
00161     <td>the iterator's multi-dimensional difference type (<TT>TinyVector<MultiArrayIndex, N></TT>)</td>
00162 </tr>
00163 <tr><th>
00164     Operation
00165     </th><th>
00166     Result
00167     </th><th>
00168     Semantics
00169     </th>
00170 </tr>
00171 <tr>
00172     <td><tt>i += diff</tt></td><td><tt>MultiIterator &</tt></td>
00173     <td>add offset to current position</td>
00174 </tr>
00175 <tr>
00176     <td><tt>i -= diff</tt></td><td><tt>MultiIterator &</tt></td>
00177     <td>subtract offset from current position</td>
00178 </tr>
00179 <tr>
00180     <td><tt>i + diff</tt></td><td><tt>MultiIterator</tt></td>
00181     <td>create traverser by adding offset</td>
00182 </tr>
00183 <tr>
00184     <td><tt>i - diff</tt></td><td><tt>MultiIterator</tt></td>
00185     <td>create traverser by subtracting offset</td>
00186 </tr>
00187 <tr>
00188     <td><tt>i[diff]</tt></td><td><tt>MultiIterator::reference</tt></td>
00189     <td>access element at offset <tt>diff</tt></td>
00190 </tr>
00191 <tr>
00192     <td><tt>i.dim<K>()</tt></td><td><tt>MultiIterator<K+1, T, ...></tt></td>
00193     <td>Access the traverser with the current dimension set to K. Typically used to call
00194         navigation functions referring to a particular dimension.<br>
00195         Example (assuming <tt>i, j</tt> are 3-dimensional):<br>
00196         \code
00197         i.dim<0>()++;   // increment dimension 0 
00198         i.dim<1>()++;   // increment dimension 1 
00199         i.dim<2>()++;   // increment dimension 2 
00200         
00201         j += MultiIterator::multi_difference_type(1,1,1);    // same effect
00202         \endcode
00203     </td>
00204 </tr>
00205 <tr><td colspan=3>
00206        <tt>i, j</tt> are of type <tt>MultiIterator</tt><br>
00207        <tt>diff</tt> is of type <tt>MultiIterator::multi_difference_type</tt><br>
00208        <tt>K</tt> is an integer compile-time constant
00209     </td>
00210 </tr>
00211 </table>
00212 </p>
00213 <p>
00214 Note that it is impossible to support an <tt>operator-</tt> between two iterators which returns
00215 a <tt>MultiIterator::multi_difference_type</tt> because it is impossible to decide to which
00216 dimension a difference applies. Consider for example, a 2-dimensional iterator <tt>i</tt>, and
00217 let <tt>j = i + multi_difference_type(width, 0)</tt>, <tt>k = i + multi_difference_type(0,1)</tt>, 
00218 where <tt>width</tt> is the array's total width. In general, <tt>j</tt> and <tt>k</tt> point to 
00219 the same memory location, so that the two cases cannot easily be distinguished (it is possible,
00220 but iterator performance will suffer significantly, as is experienced with 
00221 \ref vigra::ImageIterator where differencing is allowed).
00222 </p>
00223 
00224 <h3>Requirements for Hierarchical Traversal</h3>
00225 <p>
00226 <table border=2 cellspacing=0 cellpadding=2 width="100%">
00227 <tr><th colspan=2>
00228     Local Types
00229     </th><th>
00230     Meaning
00231     </th>
00232 </tr>
00233 <tr><td colspan=2>
00234     <tt>MultiIterator::difference_type</tt></td>
00235     <td>the iterator's difference type (<TT>MultiArrayIndex</TT>)</td>
00236 </tr>
00237 <tr><td colspan=2>
00238     <tt>MultiIterator::next_type</tt></td><td>type of the next iterator
00239        (referring to the next lower dimension) in the hierarchy</td>
00240 </tr>
00241 <tr><th>
00242     Operation
00243     </th><th>
00244     Result
00245     </th><th>
00246     Semantics
00247     </th>
00248 </tr>
00249 <tr>
00250     <td><tt>++i</tt></td><td><tt>MultiIterator &</tt></td>
00251     <td>pre-increment iterator in its current dimension</td>
00252 </tr>
00253 <tr>
00254     <td><tt>i++</tt></td><td><tt>MultiIterator</tt></td>
00255     <td>post-increment iterator in its current dimension</td>
00256 </tr>
00257 <tr>
00258     <td><tt>--i</tt></td><td><tt>MultiIterator &</tt></td>
00259     <td>pre-decrement iterator in its current dimension</td>
00260 </tr>
00261 <tr>
00262     <td><tt>i--</tt></td><td><tt>MultiIterator</tt></td>
00263     <td>post-decrement iterator in its current dimension</td>
00264 </tr>
00265 <tr>
00266     <td><tt>i += d</tt></td><td><tt>MultiIterator &</tt></td>
00267     <td>add <tt>d</tt> in current dimension</td>
00268 </tr>
00269 <tr>
00270     <td><tt>i -= d</tt></td><td><tt>MultiIterator &</tt></td>
00271     <td>subtract <tt>d</tt> in from dimension</td>
00272 </tr>
00273 <tr>
00274     <td><tt>i + d</tt></td><td><tt>MultiIterator</tt></td>
00275     <td>create new iterator by adding <tt>d</tt> in current dimension</td>
00276 </tr>
00277 <tr>
00278     <td><tt>i - d</tt></td><td><tt>MultiIterator</tt></td>
00279     <td>create new iterator by subtracting <tt>d</tt> in current dimension</td>
00280 </tr>
00281 <tr>
00282     <td><tt>i - j</tt></td><td><tt>difference_type</tt></td>
00283     <td>difference of <tt>i</tt> and <tt>j</tt> in the current dimension<br>
00284     <em>Note:</em> The result of this operation is undefined if the iterator
00285     doesn't point to element 0 in all dimensions below its current dimension.</td>
00286 </tr>
00287 <tr>
00288     <td><tt>i < j</tt></td><td><tt>bool</tt></td>
00289     <td><tt>i - j < 0</tt><br>
00290     <em>Note:</em> The result of this operation is undefined if the iterator
00291     doesn't point to element 0 in all dimensions below its current dimension.</td>
00292 </tr>
00293 <tr>
00294     <td><tt>i[d]</tt></td><td><tt>MultiIterator::reference</tt></td>
00295     <td>access element by adding offset <tt>d</tt> in current dimension</td>
00296 </tr>
00297 <tr>
00298     <td><tt>i.begin()</tt></td><td><tt>next_type</tt></td>
00299     <td>create the hierarchical iterator pointing to the first element in the 
00300     next lower dimension.<br>
00301     <em>Note:</em> The result of this operation is undefined if the iterator
00302     doesn't point to element 0 in all dimensions below its current dimension.<br>
00303     Usage:<br>
00304     \code
00305     MultiIterator<3, int> i3 = ..., end3 = ...;
00306     for(; i3 != end3; ++i3)
00307     {
00308         MultiIterator<3, int>::next_type i2 = i3.begin(), end2 = i3.end();
00309         for(; i2 != end2; ++i2)
00310         {
00311             MultiIterator<3, int>::next_type::next_type i1 = i2.begin(), end1 = i2.end();
00312             for(; i1 != end1; ++i1)
00313             {
00314                 ... // do something with the current element
00315             }
00316         }
00317     }
00318     
00319     \endcode
00320     </td>
00321 </tr>
00322 <tr>
00323     <td><tt>i.end()</tt></td><td><tt>next_type</tt></td>
00324     <td>create the hierarchical iterator pointing to the past-the-end location in the 
00325     next lower dimension.<br>
00326     <em>Note:</em> The result of this operation is undefined if the iterator
00327     doesn't point to element 0 in all dimensions below its current dimension.</td>
00328 </tr>
00329 <tr><td colspan=3>
00330        <tt>i, j</tt> are of type <tt>MultiIterator</tt><br>
00331        <tt>d</tt> is of type <tt>MultiIterator::difference_type</tt>
00332     </td>
00333 </tr>
00334 </table>
00335 </p>
00336 
00337 */
00338 
00339 /** \addtogroup MultiIteratorGroup  Multi-dimensional Array Iterators
00340 
00341     \brief General iterators for arrays of arbitrary dimension.
00342 */
00343 //@{
00344 
00345     /** Index type for a single dimension of a MultiArrayView or
00346         MultiArray.
00347     */
00348 typedef std::ptrdiff_t MultiArrayIndex;
00349 
00350     /** Traits class for the difference type of all MultiIterator, MultiArrayView, and
00351         MultiArray variants.
00352     */
00353 template <unsigned int N>
00354 class MultiArrayShape
00355 {
00356   public:
00357         /** The difference type of all MultiIterator, MultiArrayView, and
00358             MultiArray variants.
00359         */
00360     typedef TinyVector<MultiArrayIndex, N> type;
00361 };
00362 
00363 typedef MultiArrayShape<1>::type Shape1; ///< shape type for MultiArray<1, T>
00364 typedef MultiArrayShape<2>::type Shape2; ///< shape type for MultiArray<2, T>
00365 typedef MultiArrayShape<3>::type Shape3; ///< shape type for MultiArray<3, T>
00366 typedef MultiArrayShape<4>::type Shape4; ///< shape type for MultiArray<4, T>
00367 typedef MultiArrayShape<5>::type Shape5; ///< shape type for MultiArray<5, T>
00368 
00369 template <class POINTER>
00370 struct MultiIteratorStrideTraits
00371 {
00372     typedef MultiArrayIndex    stride_type;
00373     typedef const stride_type* stride_array_type;
00374     typedef stride_array_type  shape_array_type;
00375     static stride_array_type shift(stride_array_type s, unsigned d)
00376     {
00377         return s + d;
00378     }
00379 };
00380 
00381 
00382 /********************************************************/
00383 /*                                                      */
00384 /*                      MultiIterator                   */
00385 /*                                                      */
00386 /********************************************************/
00387 
00388 template <unsigned int N, class T, class REFERENCE, class POINTER>
00389 class MultiIterator;
00390 
00391 /********************************************************/
00392 /*                                                      */
00393 /*                   MultiIterator<1>                   */
00394 /*                                                      */
00395 /********************************************************/
00396 
00397 //
00398 template <class T, class REFERENCE, class POINTER>
00399 class MultiIterator<1, T, REFERENCE, POINTER>
00400 {
00401   public:
00402     enum { level = 0 };
00403     typedef T value_type;
00404     typedef REFERENCE reference;
00405     typedef const value_type &const_reference;
00406     typedef POINTER pointer;
00407     typedef const value_type *const_pointer;
00408     typedef typename MultiArrayShape<1>::type multi_difference_type;
00409     typedef MultiIteratorStrideTraits<POINTER> stride_traits;
00410     typedef typename stride_traits::stride_type difference_type;
00411     typedef typename stride_traits::stride_array_type difference_array_type;
00412     typedef typename stride_traits::shape_array_type shape_array_type;
00413     typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
00414     typedef std::random_access_iterator_tag iterator_category;
00415 
00416   protected:
00417     pointer m_ptr;
00418 
00419   public:
00420     MultiIterator ()
00421         : m_ptr (0)
00422     {}
00423 
00424     MultiIterator (pointer ptr,
00425           const difference_array_type &,
00426           const shape_array_type &)
00427         : m_ptr (ptr)
00428     {}
00429 
00430     void operator++ ()
00431     {
00432         ++m_ptr;
00433     }
00434 
00435     void operator-- ()
00436     {
00437         --m_ptr;
00438     }
00439 
00440     MultiIterator operator++ (int)
00441     {
00442         MultiIterator ret = *this;
00443         ++(*this);
00444         return ret;
00445     }
00446 
00447     MultiIterator operator-- (int)
00448     {
00449         MultiIterator ret = *this;
00450         --(*this);
00451         return ret;
00452     }
00453 
00454     MultiIterator &operator+= (difference_type n)
00455     {
00456         m_ptr += n;
00457         return *this;
00458     }
00459 
00460     MultiIterator & operator+= (multi_difference_type const & d)
00461     {
00462         m_ptr += d[level];
00463         return *this;
00464     }
00465 
00466     MultiIterator &operator-= (difference_type n)
00467     {
00468         m_ptr -= n;
00469         return *this;
00470     }
00471 
00472     MultiIterator & operator-= (multi_difference_type const & d)
00473     {
00474         m_ptr -= d[level];
00475         return *this;
00476     }
00477 
00478     MultiIterator operator+ (difference_type n) const
00479     {
00480         MultiIterator ret = *this;
00481         ret += n;
00482         return ret;
00483     }
00484 
00485     MultiIterator operator+ (multi_difference_type const & d) const
00486     {
00487         MultiIterator ret = *this;
00488         ret += d;
00489         return ret;
00490     }
00491 
00492     difference_type operator- (MultiIterator const & d) const
00493     {
00494         return (m_ptr - d.m_ptr);
00495     }
00496 
00497     MultiIterator operator- (difference_type n) const
00498     {
00499         MultiIterator ret = *this;
00500         ret -= n;
00501         return ret;
00502     }
00503 
00504     MultiIterator operator- (multi_difference_type const & d) const
00505     {
00506         MultiIterator ret = *this;
00507         ret -= d;
00508         return ret;
00509     }
00510 
00511     reference operator[] (difference_type n) const
00512     {
00513         return m_ptr [n];
00514     }
00515 
00516     reference operator[] (multi_difference_type const & d) const
00517     {
00518         return m_ptr [d[level]];
00519     }
00520 
00521     reference operator* () const
00522     {
00523         return *m_ptr;
00524     }
00525 
00526     pointer get () const
00527     {
00528         return m_ptr;
00529     }
00530 
00531     pointer operator->() const
00532     {
00533         return &(operator*());
00534     }
00535 
00536     bool operator!= (const MultiIterator &rhs) const
00537     {
00538         return m_ptr != rhs.m_ptr;
00539     }
00540 
00541     bool operator== (const MultiIterator &rhs) const
00542     {
00543         return m_ptr == rhs.m_ptr;
00544     }
00545 
00546     bool operator< (const MultiIterator &rhs) const
00547     {
00548         return m_ptr < rhs.m_ptr;
00549     }
00550 
00551     bool operator<= (const MultiIterator &rhs) const
00552     {
00553         return m_ptr <= rhs.m_ptr;
00554     }
00555 
00556     bool operator> (const MultiIterator &rhs) const
00557     {
00558         return m_ptr > rhs.m_ptr;
00559     }
00560 
00561     bool operator>= (const MultiIterator &rhs) const
00562     {
00563         return m_ptr >= rhs.m_ptr;
00564     }
00565 
00566     iterator iteratorForDimension(unsigned int d) const
00567     {
00568         vigra_precondition(d == 0,
00569             "MultiIterator<1>::iteratorForDimension(d): d == 0 required");
00570         const difference_type stride = 1;
00571         return iterator(m_ptr, &stride, 0);
00572     }
00573 
00574     template <unsigned int K>
00575     MultiIterator<K+1, T, REFERENCE, POINTER> &
00576     dim()
00577     {
00578         return *this;
00579     }
00580 
00581     MultiIterator<1, T, REFERENCE, POINTER> &
00582     dim0() { return *this; }
00583 
00584   protected:
00585 
00586     difference_type 
00587     total_stride(typename multi_difference_type::const_iterator d) const
00588     {
00589         return d[level];
00590     }
00591 };
00592 
00593 /********************************************************/
00594 /*                                                      */
00595 /*                   MultiIterator<2>                   */
00596 /*                                                      */
00597 /********************************************************/
00598 
00599 //
00600 template <class T, class REFERENCE, class POINTER>
00601 class MultiIterator<2, T, REFERENCE, POINTER>
00602 #ifndef DOXYGEN  // doxygen doesn't understand this inheritance
00603 : public MultiIterator<1, T, REFERENCE, POINTER>
00604 #endif
00605 {
00606   public:
00607 
00608     typedef MultiIterator<1, T, REFERENCE, POINTER> base_type;
00609     enum { level = 1 };
00610     typedef T value_type;
00611     typedef REFERENCE reference;
00612     typedef const value_type &const_reference;
00613     typedef POINTER pointer;
00614     typedef const value_type *const_pointer;
00615     typedef typename MultiArrayShape<2>::type multi_difference_type;
00616     typedef MultiIteratorStrideTraits<POINTER> stride_traits;
00617     typedef typename stride_traits::stride_type difference_type;
00618     typedef typename stride_traits::stride_array_type difference_array_type;
00619     typedef typename stride_traits::shape_array_type shape_array_type;
00620     typedef base_type next_type;
00621     typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
00622     typedef multi_dimensional_traverser_tag iterator_category;
00623 
00624   protected:
00625     difference_array_type m_stride;
00626     shape_array_type      m_shape;
00627 
00628   public:
00629     /* use default copy constructor and assignment operator */
00630 
00631     MultiIterator ()
00632         : base_type (),
00633           m_stride (0), m_shape (0)
00634     {}
00635 
00636     MultiIterator (pointer ptr,
00637           const difference_array_type & stride,
00638           const shape_array_type & shape)
00639         : base_type (ptr, stride, shape),
00640           m_stride (stride), m_shape (shape)
00641     {}
00642 
00643     void operator++ ()
00644     {
00645         this->m_ptr += m_stride [level];
00646     }
00647 
00648     void operator-- ()
00649     {
00650         this->m_ptr -= m_stride [level];
00651     }
00652 
00653     MultiIterator operator++ (int)
00654     {
00655         MultiIterator ret = *this;
00656         ++(*this);
00657         return ret;
00658     }
00659 
00660     MultiIterator operator-- (int)
00661     {
00662         MultiIterator ret = *this;
00663         --(*this);
00664         return ret;
00665     }
00666 
00667     MultiIterator & operator+= (difference_type n)
00668     {
00669         this->m_ptr += n * m_stride [level];
00670         return *this;
00671     }
00672 
00673     MultiIterator & operator+= (multi_difference_type const & d)
00674     {
00675         this->m_ptr += total_stride(d.begin());
00676         return *this;
00677     }
00678 
00679     MultiIterator  &operator-= (difference_type n)
00680     {
00681         this->m_ptr -= n * m_stride [level];
00682         return *this;
00683     }
00684 
00685     MultiIterator & operator-= (multi_difference_type const & d)
00686     {
00687         this->m_ptr -= total_stride(d.begin());
00688         return *this;
00689     }
00690 
00691     MultiIterator operator+ (difference_type n) const
00692     {
00693         MultiIterator ret = *this;
00694         ret += n;
00695         return ret;
00696     }
00697 
00698     MultiIterator operator+ (multi_difference_type const & d) const
00699     {
00700         MultiIterator ret = *this;
00701         ret += d;
00702         return ret;
00703     }
00704 
00705     difference_type operator- (MultiIterator const & d) const
00706     {
00707         return (this->m_ptr - d.m_ptr) / this->m_stride[level];
00708     }
00709 
00710     MultiIterator operator- (difference_type n) const
00711     {
00712         MultiIterator ret = *this;
00713         ret -= n;
00714         return ret;
00715     }
00716 
00717     MultiIterator operator- (multi_difference_type const & d) const
00718     {
00719         MultiIterator ret = *this;
00720         ret -= d;
00721         return ret;
00722     }
00723 
00724     reference operator[] (difference_type n) const
00725     {
00726         return this->m_ptr [n*m_stride [level]];
00727     }
00728 
00729     reference operator[] (multi_difference_type const & d) const
00730     {
00731         return this->m_ptr [total_stride(d.begin())];
00732     }
00733 
00734     next_type begin () const
00735     {
00736         return *this;
00737     }
00738 
00739     next_type end () const
00740     {
00741         next_type ret = *this;
00742         ret += m_shape [level-1];
00743         return ret;
00744     }
00745 
00746     iterator iteratorForDimension(unsigned int d) const
00747     {
00748         vigra_precondition(d <= level,
00749             "MultiIterator<N>::iteratorForDimension(d): d < N required");
00750         return iterator(this->m_ptr, stride_traits::shift(m_stride, d), 0);
00751     }
00752 
00753     template <unsigned int K>
00754     MultiIterator<K+1, T, REFERENCE, POINTER> &
00755     dim()
00756     {
00757         return *this;
00758     }
00759 
00760     MultiIterator<1, T, REFERENCE, POINTER> &
00761     dim0() { return *this; }
00762     MultiIterator<2, T, REFERENCE, POINTER> &
00763     dim1() { return *this; }
00764 
00765   protected:
00766 
00767     difference_type 
00768     total_stride(typename multi_difference_type::const_iterator d) const
00769     {
00770         return d[level]*m_stride[level] + base_type::total_stride(d);
00771     }
00772 };
00773 
00774 /********************************************************/
00775 /*                                                      */
00776 /*                   MultiIterator<N>                   */
00777 /*                                                      */
00778 /********************************************************/
00779 
00780 /** \brief A multi-dimensional hierarchical iterator to be used with 
00781            \ref vigra::MultiArrayView if it is not strided.
00782 
00783      See \ref MultiIteratorPage for further documentation.
00784 
00785 <b>\#include</b> <vigra/multi_iterator.hxx>
00786 
00787 Namespace: vigra
00788 */
00789 template <unsigned int N, class T, class REFERENCE, class POINTER>
00790 class MultiIterator 
00791 #ifndef DOXYGEN  // doxygen doesn't understand this inheritance
00792 : public MultiIterator<N-1, T, REFERENCE, POINTER>
00793 #endif
00794 {
00795 public:
00796 
00797         /** the type of the parent in the inheritance hierarchy.
00798          */
00799     typedef MultiIterator<N-1, T, REFERENCE, POINTER> base_type;
00800         
00801         /** the iterator's level in the dimension hierarchy
00802          */
00803     enum { level = N-1 };
00804 
00805         /** the iterator's value type
00806          */
00807     typedef T value_type;
00808 
00809         /** reference type (result of operator[])
00810          */
00811     typedef REFERENCE reference;
00812 
00813         /** const reference type (result of operator[] const)
00814          */
00815     typedef const value_type &const_reference;
00816 
00817         /** pointer type
00818          */
00819     typedef POINTER pointer;
00820 
00821         /** const pointer type
00822          */
00823     typedef const value_type *const_pointer;
00824 
00825         /** multi difference type 
00826             (used for offsetting along all axes simultaneously)
00827          */
00828     typedef typename MultiArrayShape<N>::type multi_difference_type;
00829     
00830         /** difference type (used for offsetting)
00831          */
00832 #ifndef DOXYGEN
00833     typedef MultiIteratorStrideTraits<POINTER> stride_traits;
00834     typedef typename stride_traits::stride_type difference_type;
00835     typedef typename stride_traits::stride_array_type difference_array_type;
00836     typedef typename stride_traits::shape_array_type shape_array_type;
00837 #else
00838     typedef MultiArrayIndex difference_type;
00839 #endif
00840 
00841         /** the MultiIterator for the next lower dimension.
00842          */
00843     typedef base_type next_type;
00844 
00845         /** the 1-dimensional iterator for this iterator hierarchy
00846             (result of iteratorForDimension()).
00847         */
00848     typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
00849 
00850         /** the iterator tag (image traverser)
00851         */
00852     typedef multi_dimensional_traverser_tag iterator_category;
00853             
00854     /* use default copy constructor and assignment operator */
00855 
00856         /** default constructor.
00857         */
00858     MultiIterator ()
00859     {}
00860 
00861         /** construct from pointer, strides (offset of a sample to the
00862             next) for every dimension, and the shape.
00863         */
00864     MultiIterator (pointer ptr,
00865                    const difference_array_type & stride,
00866                    const shape_array_type & shape)
00867         : base_type (ptr, stride, shape)
00868     {}
00869 
00870 
00871         /** prefix-increment the iterator in its current dimension
00872          */
00873     void operator++ ()
00874     {
00875         this->m_ptr += this->m_stride [level];
00876     }
00877 
00878         /** prefix-decrement the iterator in its current dimension
00879          */
00880     void operator-- ()
00881     {
00882         this->m_ptr -= this->m_stride [level];
00883     }
00884 
00885         /** postfix-increment the iterator in its current dimension
00886          */
00887     MultiIterator operator++ (int)
00888     {
00889         MultiIterator ret = *this;
00890         ++(*this);
00891         return ret;
00892     }
00893 
00894         /** postfix-decrement the iterator in its current dimension
00895          */
00896     MultiIterator operator-- (int)
00897     {
00898         MultiIterator ret = *this;
00899         --(*this);
00900         return ret;
00901     }
00902 
00903         /** increment the iterator in its current dimension
00904             by the given value.
00905         */
00906     MultiIterator & operator+= (difference_type n)
00907     {
00908         this->m_ptr += n * this->m_stride [level];
00909         return *this;
00910     }
00911 
00912         /** increment the iterator in all dimensions
00913             by the given offset.
00914         */
00915     MultiIterator & operator+= (multi_difference_type const & d)
00916     {
00917         this->m_ptr += total_stride(d.begin());
00918         return *this;
00919     }
00920 
00921         /** decrement the iterator in its current dimension
00922             by the given value.
00923         */
00924     MultiIterator & operator-= (difference_type n)
00925     {
00926         this->m_ptr -= n * this->m_stride [level];
00927         return *this;
00928     }
00929 
00930         /** decrement the iterator in all dimensions
00931             by the given offset.
00932         */
00933     MultiIterator & operator-= (multi_difference_type const & d)
00934     {
00935         this->m_ptr -= total_stride(d.begin());
00936         return *this;
00937     }
00938 
00939         /** addition within current dimension
00940          */
00941     MultiIterator operator+ (difference_type n) const
00942     {
00943         MultiIterator ret = *this;
00944         ret += n;
00945         return ret;
00946     }
00947 
00948         /** addition along all dimensions
00949          */
00950     MultiIterator operator+ (multi_difference_type const & d) const
00951     {
00952         MultiIterator ret = *this;
00953         ret += d;
00954         return ret;
00955     }
00956 
00957         /** difference of two iterators in the current dimension.
00958             The result of this operation is undefined if the iterator
00959             doesn't point to element 0 in all dimensions below its current dimension.
00960         */
00961     difference_type operator- (MultiIterator const & d) const
00962     {
00963         return (this->m_ptr - d.m_ptr) / this->m_stride[level];
00964     }
00965 
00966         /** subtraction within current dimension
00967          */
00968     MultiIterator operator- (difference_type n) const
00969     {
00970         MultiIterator ret = *this;
00971         ret -= n;
00972         return ret;
00973     }
00974 
00975         /** subtraction along all dimensions
00976          */
00977     MultiIterator operator- (multi_difference_type const & d) const
00978     {
00979         MultiIterator ret = *this;
00980         ret -= d;
00981         return ret;
00982     }
00983 
00984 #ifdef DOXYGEN /* documentation only: operators *, ->, ==, !=, <, <=, >, >= are inherited */
00985         /** derefenrence item
00986          */
00987     reference operator* () const;
00988 
00989         /** get address of current item
00990          */
00991     pointer get () const;
00992 
00993         /** call method of current item
00994          */
00995     pointer operator->() const;
00996 
00997         /** inequality. True if iterators reference different items.
00998          */
00999     bool operator!= (const MultiIterator &rhs) const;
01000 
01001         /** equality. True if iterators reference the same items.
01002          */
01003     bool operator== (const MultiIterator &rhs) const;
01004 
01005         /** less than.
01006          */
01007     bool operator< (const MultiIterator &rhs) const;
01008 
01009         /** less or equal.
01010          */
01011     bool operator<= (const MultiIterator &rhs) const;
01012 
01013         /** greater than.
01014          */
01015     bool operator> (const MultiIterator &rhs) const;
01016     
01017         /** greater or equal.
01018          */
01019     bool operator>= (const MultiIterator &rhs) const;
01020 #endif
01021 
01022         /** access the array element at the given offset in 
01023         the current dimension.
01024         */
01025     reference operator[] (difference_type n) const
01026     {
01027         return this->m_ptr [n* this->m_stride [level]];
01028     }
01029 
01030         /** access the array element at the given offset.
01031         */
01032     reference operator[] (multi_difference_type const & d) const
01033     {
01034         return this->m_ptr [total_stride(d.begin())];
01035     }
01036 
01037         /** Return the (N-1)-dimensional multi-iterator that points to 
01038             the first (N-1)-dimensional subarray of the 
01039             N-dimensional array this iterator is referring to.
01040             The result is only valid if this iterator refers to location
01041             0 in <em>all</em> dimensions below its current dimension N,
01042             otherwise it is undefined. Usage:
01043 
01044             \code
01045 
01046             MultiIterator<2, int> outer = ...;  // this iterator
01047 
01048             MultiIterator<2, int>::next_type inner = outer.begin();
01049             for(; inner != outer.end(); ++inner)
01050             {
01051                 // manipulate current 1D subimage
01052             }
01053             \endcode
01054         */
01055     next_type begin () const
01056     {
01057         return *this;
01058     }
01059 
01060         /** Return the (N-1)-dimensional multi-iterator that points beyond 
01061             the last (N-1)-dimensional subarray of the 
01062             N-dimensional array this iterator is referring to.
01063             The result is only valid if this iterator refers to location
01064             0 in <em>all</em> dimensions below its current dimension N,
01065             otherwise it is undefined.
01066         */
01067     next_type end () const
01068     {
01069         next_type ret = *this;
01070         ret += this->m_shape [level-1];
01071         return ret;
01072     }
01073 
01074         /** Get a 1-dimensional, STL-compatible iterator for the
01075             given dimension, pointing to the current element of <TT>this</TT>.
01076             Usage:
01077 
01078             \code
01079 
01080             MultiIterator<3, int> outer = ...;  // this iterator
01081 
01082             MultiIterator<3, int>::iterator i = outer.iteratorForDimension(1);
01083             MultiIterator<3, int>::iterator end = i + height;
01084             for(; i != end; ++i)
01085             {
01086                 // go down the current column starting at the location of 'outer'
01087             }
01088             \endcode            
01089         */
01090     iterator iteratorForDimension(unsigned int d) const
01091     {
01092         vigra_precondition(d <= level,
01093             "MultiIterator<N>::iteratorForDimension(d): d < N required");
01094         return iterator(this->m_ptr, stride_traits::shift(this->m_stride, d),0);
01095     }
01096         /** Return the multi-iterator that operates on dimension K in order
01097             to manipulate this dimension directly. Usage:
01098                
01099             \code
01100                 
01101             MultiIterator<3, int> i3 = ...;
01102                 
01103             i3.template dim<2>()++;  // increment outer dimension
01104             i3.template dim<0>()++;  // increment inner dimension
01105             \endcode
01106             
01107             For convenience, the same functionality is also available
01108             as <tt>dim0()</tt>, <tt>dim1()</tt> etc. up to <tt>dim4()</tt>:
01109             
01110             \code
01111                 
01112             MultiIterator<3, int> i3 = ...;
01113                 
01114             i3.dim2()++;  // increment outer dimension
01115             i3.dim0()++;  // increment inner dimension
01116             \endcode            
01117         */
01118     template <unsigned int K>
01119     MultiIterator<K+1, T, REFERENCE, POINTER> &
01120     dim()
01121     {
01122         return *this;
01123     }
01124 
01125     MultiIterator<1, T, REFERENCE, POINTER> &
01126     dim0() { return *this; }
01127     MultiIterator<2, T, REFERENCE, POINTER> &
01128     dim1() { return *this; }
01129     MultiIterator<3, T, REFERENCE, POINTER> &
01130     dim2() { return *this; }
01131     MultiIterator<4, T, REFERENCE, POINTER> &
01132     dim3() { return *this; }
01133     MultiIterator<5, T, REFERENCE, POINTER> &
01134     dim4() { return *this; }
01135 
01136   protected:
01137 
01138     difference_type 
01139     total_stride(typename multi_difference_type::const_iterator d) const
01140     {
01141         return d[level]*this->m_stride[level] + base_type::total_stride(d);
01142     }
01143 
01144 };
01145 
01146 /********************************************************/
01147 /*                                                      */
01148 /*                      StridedMultiIterator            */
01149 /*                                                      */
01150 /********************************************************/
01151 
01152 template <unsigned int N, class T, class REFERENCE, class POINTER>
01153 class StridedMultiIterator;
01154 
01155 /********************************************************/
01156 /*                                                      */
01157 /*                   StridedMultiIterator<1>            */
01158 /*                                                      */
01159 /********************************************************/
01160 
01161 //
01162 template <class T, class REFERENCE, class POINTER>
01163 class StridedMultiIterator<1, T, REFERENCE, POINTER>
01164 {
01165   public:
01166     enum { level = 0 };
01167     typedef T value_type;
01168     typedef REFERENCE reference;
01169     typedef const value_type &const_reference;
01170     typedef POINTER pointer;
01171     typedef const value_type *const_pointer;
01172     typedef typename MultiArrayShape<1>::type multi_difference_type;
01173     typedef MultiIteratorStrideTraits<POINTER> stride_traits;
01174     typedef typename stride_traits::stride_type difference_type;
01175     typedef typename stride_traits::stride_array_type difference_array_type;
01176     typedef typename stride_traits::shape_array_type shape_array_type;
01177     typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
01178     typedef std::random_access_iterator_tag iterator_category;
01179 
01180   protected:
01181     pointer m_ptr;
01182     difference_type m_stride;
01183 
01184     /* use default copy constructor and assignment operator */
01185 
01186   public:
01187     StridedMultiIterator ()
01188         : m_ptr (0), m_stride (0)
01189     {}
01190 
01191     StridedMultiIterator (pointer ptr,
01192           const difference_array_type & stride,
01193           const shape_array_type &)
01194         : m_ptr (ptr), m_stride (stride [level])
01195     {}
01196 
01197     void operator++ ()
01198     {
01199         m_ptr += m_stride;
01200     }
01201 
01202     void operator-- ()
01203     {
01204         m_ptr -= m_stride;
01205     }
01206 
01207     StridedMultiIterator operator++ (int)
01208     {
01209         StridedMultiIterator ret = *this;
01210         ++(*this);
01211         return ret;
01212     }
01213 
01214     StridedMultiIterator operator-- (int)
01215     {
01216         StridedMultiIterator ret = *this;
01217         --(*this);
01218         return ret;
01219     }
01220 
01221     StridedMultiIterator &operator+= (difference_type n)
01222     {
01223         m_ptr += n * m_stride;
01224         return *this;
01225     }
01226 
01227     StridedMultiIterator & operator+= (multi_difference_type const & d)
01228     {
01229         m_ptr += d[level] * m_stride;
01230         return *this;
01231     }
01232 
01233     StridedMultiIterator &operator-= (difference_type n)
01234     {
01235         m_ptr -= n * m_stride;
01236         return *this;
01237     }
01238 
01239     StridedMultiIterator & operator-= (multi_difference_type const & d)
01240     {
01241         m_ptr -= d[level] * m_stride;
01242         return *this;
01243     }
01244 
01245     StridedMultiIterator operator+ (difference_type n) const
01246     {
01247         StridedMultiIterator ret = *this;
01248         ret += n;
01249         return ret;
01250     }
01251 
01252     StridedMultiIterator operator+ (multi_difference_type const & d) const
01253     {
01254         StridedMultiIterator ret = *this;
01255         ret += d;
01256         return ret;
01257     }
01258 
01259     difference_type operator- (StridedMultiIterator const & d) const
01260     {
01261         return (m_ptr - d.m_ptr) / m_stride;
01262     }
01263 
01264     StridedMultiIterator operator- (difference_type n) const
01265     {
01266         StridedMultiIterator ret = *this;
01267         ret -= n;
01268         return ret;
01269     }
01270 
01271     StridedMultiIterator operator- (multi_difference_type const & d) const
01272     {
01273         StridedMultiIterator ret = *this;
01274         ret -= d;
01275         return ret;
01276     }
01277 
01278     reference operator[] (difference_type n) const
01279     {
01280         return m_ptr [n*m_stride];
01281     }
01282 
01283     reference operator[] (multi_difference_type const & d) const
01284     {
01285         return m_ptr [d[level]*m_stride];
01286     }
01287 
01288     reference operator* () const
01289     {
01290         return *m_ptr;
01291     }
01292 
01293     pointer get () const
01294     {
01295         return m_ptr;
01296     }
01297 
01298     pointer operator->() const
01299     {
01300         return &(operator*());
01301     }
01302 
01303     bool operator!= (const StridedMultiIterator &rhs) const
01304     {
01305         return m_ptr != rhs.m_ptr;
01306     }
01307 
01308     bool operator== (const StridedMultiIterator &rhs) const
01309     {
01310         return m_ptr == rhs.m_ptr;
01311     }
01312 
01313     bool operator< (const StridedMultiIterator &rhs) const
01314     {
01315         return m_ptr < rhs.m_ptr;
01316     }
01317 
01318     bool operator<= (const StridedMultiIterator &rhs) const
01319     {
01320         return m_ptr <= rhs.m_ptr;
01321     }
01322 
01323     bool operator> (const StridedMultiIterator &rhs) const
01324     {
01325         return m_ptr > rhs.m_ptr;
01326     }
01327 
01328     bool operator>= (const StridedMultiIterator &rhs) const
01329     {
01330         return m_ptr >= rhs.m_ptr;
01331     }
01332 
01333     iterator iteratorForDimension(unsigned int d) const
01334     {
01335         vigra_precondition(d == 0,
01336             "StridedMultiIterator<1>::iteratorForDimension(d): d == 0 required");
01337         const difference_type stride = 1;
01338         return iterator(m_ptr, &stride, 0);
01339     }
01340 
01341     template <unsigned int K>
01342     StridedMultiIterator<K+1, T, REFERENCE, POINTER> &
01343     dim()
01344     {
01345         return *this;
01346     }
01347 
01348     StridedMultiIterator<1, T, REFERENCE, POINTER> &
01349     dim0() { return *this; }
01350 
01351   protected:
01352 
01353     difference_type 
01354     total_stride(typename multi_difference_type::const_iterator d) const
01355     {
01356         return d[level] * m_stride;
01357     }
01358 };
01359 
01360 /********************************************************/
01361 /*                                                      */
01362 /*                   StridedMultiIterator<2>            */
01363 /*                                                      */
01364 /********************************************************/
01365 
01366 //
01367 template <class T, class REFERENCE, class POINTER>
01368 class StridedMultiIterator<2, T, REFERENCE, POINTER>
01369 #ifndef DOXYGEN  // doxygen doesn't understand this inheritance
01370 : public StridedMultiIterator<1, T, REFERENCE, POINTER>
01371 #endif
01372 {
01373   public:
01374 
01375     typedef StridedMultiIterator<1, T, REFERENCE, POINTER> base_type;
01376     enum { level = 1 };
01377     typedef T value_type;
01378     typedef REFERENCE reference;
01379     typedef const value_type &const_reference;
01380     typedef POINTER pointer;
01381     typedef const value_type *const_pointer;
01382     typedef typename MultiArrayShape<2>::type multi_difference_type;
01383     typedef MultiIteratorStrideTraits<POINTER> stride_traits;
01384     typedef typename stride_traits::stride_type difference_type;
01385     typedef typename stride_traits::stride_array_type difference_array_type;
01386     typedef typename stride_traits::shape_array_type shape_array_type;
01387     typedef base_type next_type;
01388     typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
01389     typedef multi_dimensional_traverser_tag iterator_category;
01390 
01391   protected:
01392     difference_array_type m_stride;
01393     shape_array_type m_shape;
01394 
01395   public:
01396     /* use default copy constructor and assignment operator */
01397 
01398     StridedMultiIterator ()
01399         : base_type (),
01400           m_stride (0), m_shape (0)
01401     {}
01402 
01403     StridedMultiIterator (pointer ptr,
01404           const difference_array_type & stride,
01405           const shape_array_type & shape)
01406         : base_type (ptr, stride, shape),
01407           m_stride (stride), m_shape (shape)
01408     {}
01409 
01410     void operator++ ()
01411     {
01412         this->m_ptr += m_stride [level];
01413     }
01414 
01415     void operator-- ()
01416     {
01417         this->m_ptr -= m_stride [level];
01418     }
01419 
01420     StridedMultiIterator operator++ (int)
01421     {
01422         StridedMultiIterator ret = *this;
01423         ++(*this);
01424         return ret;
01425     }
01426 
01427     StridedMultiIterator operator-- (int)
01428     {
01429         StridedMultiIterator ret = *this;
01430         --(*this);
01431         return ret;
01432     }
01433 
01434     StridedMultiIterator & operator+= (difference_type n)
01435     {
01436         this->m_ptr += n * m_stride [level];
01437         return *this;
01438     }
01439 
01440     StridedMultiIterator & operator+= (multi_difference_type const & d)
01441     {
01442         this->m_ptr += total_stride(d.begin());
01443         return *this;
01444     }
01445 
01446     StridedMultiIterator  &operator-= (difference_type n)
01447     {
01448         this->m_ptr -= n * m_stride [level];
01449         return *this;
01450     }
01451 
01452     StridedMultiIterator & operator-= (multi_difference_type const & d)
01453     {
01454         this->m_ptr -= total_stride(d.begin());
01455         return *this;
01456     }
01457 
01458     StridedMultiIterator operator+ (difference_type n) const
01459     {
01460         StridedMultiIterator ret = *this;
01461         ret += n;
01462         return ret;
01463     }
01464 
01465     StridedMultiIterator operator+ (multi_difference_type const & d) const
01466     {
01467         StridedMultiIterator ret = *this;
01468         ret += d;
01469         return ret;
01470     }
01471 
01472     difference_type operator- (StridedMultiIterator const & d) const
01473     {
01474         return (this->m_ptr - d.m_ptr) / this->m_stride[level];
01475     }
01476 
01477     StridedMultiIterator operator- (difference_type n) const
01478     {
01479         StridedMultiIterator ret = *this;
01480         ret -= n;
01481         return ret;
01482     }
01483 
01484     StridedMultiIterator operator- (multi_difference_type const & d) const
01485     {
01486         StridedMultiIterator ret = *this;
01487         ret -= d;
01488         return ret;
01489     }
01490 
01491     reference operator[] (difference_type n) const
01492     {
01493         return this->m_ptr [n*m_stride [level]];
01494     }
01495 
01496     reference operator[] (multi_difference_type const & d) const
01497     {
01498         return this->m_ptr [total_stride(d.begin())];
01499     }
01500 
01501     next_type begin () const
01502     {
01503         return *this;
01504     }
01505 
01506     next_type end () const
01507     {
01508         next_type ret = *this;
01509         ret += m_shape [level-1];
01510         return ret;
01511     }
01512 
01513     iterator iteratorForDimension(unsigned int d) const
01514     {
01515         vigra_precondition(d <= level,
01516             "StridedMultiIterator<N>::iteratorForDimension(d): d < N required");
01517         return iterator(this->m_ptr, stride_traits::shift(m_stride, d), 0);
01518     }
01519 
01520     template <unsigned int K>
01521     StridedMultiIterator<K+1, T, REFERENCE, POINTER> &
01522     dim()
01523     {
01524         return *this;
01525     }
01526 
01527     StridedMultiIterator<1, T, REFERENCE, POINTER> &
01528     dim0() { return *this; }
01529     StridedMultiIterator<2, T, REFERENCE, POINTER> &
01530     dim1() { return *this; }
01531 
01532   protected:
01533 
01534     difference_type 
01535     total_stride(typename multi_difference_type::const_iterator d) const
01536     {
01537         return d[level]*m_stride[level] + base_type::total_stride(d);
01538     }
01539 };
01540 
01541 /********************************************************/
01542 /*                                                      */
01543 /*                   StridedMultiIterator<N>            */
01544 /*                                                      */
01545 /********************************************************/
01546 
01547 /** \brief A multi-dimensional hierarchical iterator to be used with 
01548            \ref vigra::MultiArrayView if it is not strided.
01549 
01550      See \ref MultiIteratorPage for further documentation.
01551 
01552 <b>\#include</b> <vigra/multi_iterator.hxx>
01553 
01554 Namespace: vigra
01555 */
01556 template <unsigned int N, class T, class REFERENCE, class POINTER>
01557 class StridedMultiIterator 
01558 #ifndef DOXYGEN  // doxygen doesn't understand this inheritance
01559 : public StridedMultiIterator<N-1, T, REFERENCE, POINTER>
01560 #endif
01561 {
01562 public:
01563 
01564         /** the type of the parent in the inheritance hierarchy.
01565          */
01566     typedef StridedMultiIterator<N-1, T, REFERENCE, POINTER> base_type;
01567         
01568         /** the iterator's level in the dimension hierarchy
01569          */
01570     enum { level = N-1 };
01571 
01572         /** the iterator's value type
01573          */
01574     typedef T value_type;
01575 
01576         /** reference type (result of operator[])
01577          */
01578     typedef REFERENCE reference;
01579 
01580         /** const reference type (result of operator[] const)
01581          */
01582     typedef const value_type &const_reference;
01583 
01584         /** pointer type
01585          */
01586     typedef POINTER pointer;
01587 
01588         /** const pointer type
01589          */
01590     typedef const value_type *const_pointer;
01591 
01592         /** multi difference type 
01593             (used for offsetting along all axes simultaneously)
01594          */
01595     typedef typename MultiArrayShape<N>::type multi_difference_type;
01596 
01597         /** difference type (used for offsetting)
01598          */
01599 #ifndef DOXYGEN
01600     typedef MultiIteratorStrideTraits<POINTER> stride_traits;
01601     typedef typename stride_traits::stride_type difference_type;
01602     typedef typename stride_traits::stride_array_type difference_array_type;
01603 #else
01604     typedef MultiArrayIndex difference_type;
01605 #endif
01606     
01607         /** the StridedMultiIterator for the next lower dimension.
01608          */
01609     typedef base_type next_type;
01610 
01611         /** the 1-dimensional iterator for this iterator hierarchy
01612             (result of iteratorForDimension()).
01613         */
01614     typedef StridedMultiIterator<1, T, REFERENCE, POINTER> iterator;
01615 
01616         /** the iterator tag (image traverser)
01617         */
01618     typedef multi_dimensional_traverser_tag iterator_category;
01619             
01620     /* use default copy constructor and assignment operator */
01621 
01622         /** default constructor.
01623         */
01624     StridedMultiIterator ()
01625     {}
01626 
01627         /** construct from pointer, strides (offset of a sample to the
01628             next) for every dimension, and the shape.
01629         */
01630     StridedMultiIterator (pointer ptr,
01631                    const difference_array_type & stride,
01632                    const difference_array_type & shape)
01633         : base_type (ptr, stride, shape)
01634     {}
01635 
01636 
01637         /** prefix-increment the iterator in its current dimension
01638          */
01639     void operator++ ()
01640     {
01641         this->m_ptr += this->m_stride [level];
01642     }
01643 
01644         /** prefix-decrement the iterator in its current dimension
01645          */
01646     void operator-- ()
01647     {
01648         this->m_ptr -= this->m_stride [level];
01649     }
01650 
01651         /** postfix-increment the iterator in its current dimension
01652          */
01653     StridedMultiIterator operator++ (int)
01654     {
01655         StridedMultiIterator ret = *this;
01656         ++(*this);
01657         return ret;
01658     }
01659 
01660         /** postfix-decrement the iterator in its current dimension
01661          */
01662     StridedMultiIterator operator-- (int)
01663     {
01664         StridedMultiIterator ret = *this;
01665         --(*this);
01666         return ret;
01667     }
01668 
01669         /** increment the iterator in its current dimension
01670             by the given value.
01671         */
01672     StridedMultiIterator & operator+= (difference_type n)
01673     {
01674         this->m_ptr += n * this->m_stride [level];
01675         return *this;
01676     }
01677 
01678         /** increment the iterator in all dimensions
01679             by the given offset.
01680         */
01681     StridedMultiIterator & operator+= (multi_difference_type const & d)
01682     {
01683         this->m_ptr += total_stride(d.begin());
01684         return *this;
01685     }
01686 
01687         /** decrement the iterator in its current dimension
01688             by the given value.
01689         */
01690     StridedMultiIterator & operator-= (difference_type n)
01691     {
01692         this->m_ptr -= n * this->m_stride [level];
01693         return *this;
01694     }
01695 
01696         /** decrement the iterator in all dimensions
01697             by the given offset.
01698         */
01699     StridedMultiIterator & operator-= (multi_difference_type const & d)
01700     {
01701         this->m_ptr -= total_stride(d.begin());
01702         return *this;
01703     }
01704 
01705         /** addition within current dimension
01706          */
01707     StridedMultiIterator operator+ (difference_type n) const
01708     {
01709         StridedMultiIterator ret = *this;
01710         ret += n;
01711         return ret;
01712     }
01713 
01714         /** addition along all dimensions
01715          */
01716     StridedMultiIterator operator+ (multi_difference_type const & d) const
01717     {
01718         StridedMultiIterator ret = *this;
01719         ret += d;
01720         return ret;
01721     }
01722 
01723         /** difference of two iterators in the current dimension.
01724             The result of this operation is undefined if the iterator
01725             doesn't point to element 0 in all dimensions below its current dimension.
01726         */
01727     difference_type operator- (StridedMultiIterator const & d) const
01728     {
01729         return (this->m_ptr - d.m_ptr) / this->m_stride[level];
01730     }
01731 
01732         /** subtraction within current dimension
01733          */
01734     StridedMultiIterator operator- (difference_type n) const
01735     {
01736         StridedMultiIterator ret = *this;
01737         ret -= n;
01738         return ret;
01739     }
01740 
01741         /** subtraction along all dimensions
01742          */
01743     StridedMultiIterator operator- (multi_difference_type const & d) const
01744     {
01745         StridedMultiIterator ret = *this;
01746         ret -= d;
01747         return ret;
01748     }
01749 
01750 #ifdef DOXYGEN /* documentation only: operators *, ->, ==, !=, <, <=, >, >= are inherited */
01751         /** derefenrence item
01752          */
01753     reference operator* () const;
01754 
01755         /** get address of current item
01756          */
01757     pointer get () const;
01758 
01759         /** call method of current item
01760          */
01761     pointer operator->() const;
01762 
01763         /** inequality. True if iterators reference different items.
01764          */
01765     bool operator!= (const StridedMultiIterator &rhs) const;
01766 
01767         /** equality. True if iterators reference the same items.
01768          */
01769     bool operator== (const StridedMultiIterator &rhs) const;
01770 
01771         /** less than.
01772          */
01773     bool operator< (const StridedMultiIterator &rhs) const;
01774 
01775         /** less or equal.
01776          */
01777     bool operator<= (const StridedMultiIterator &rhs) const;
01778 
01779         /** greater than.
01780          */
01781     bool operator> (const StridedMultiIterator &rhs) const;
01782     
01783         /** greater or equal.
01784          */
01785     bool operator>= (const StridedMultiIterator &rhs) const;
01786 #endif
01787 
01788         /** access the array element at the given offset in 
01789         the current dimension.
01790         */
01791     reference operator[] (difference_type n) const
01792     {
01793         return this->m_ptr [n* this->m_stride [level]];
01794     }
01795 
01796         /** access the array element at the given offset.
01797         */
01798     reference operator[] (multi_difference_type const & d) const
01799     {
01800         return this->m_ptr [total_stride(d.begin())];
01801     }
01802 
01803         /** Return the (N-1)-dimensional multi-iterator that points to 
01804             the first (N-1)-dimensional subarray of the 
01805             N-dimensional array this iterator is referring to.
01806             The result is only valid if this iterator refers to location
01807             0 in <em>all</em> dimensions below its current dimension N,
01808             otherwise it is undefined. Usage:
01809 
01810             \code
01811 
01812             StridedMultiIterator<2, int> outer = ...;  // this iterator
01813 
01814             StridedMultiIterator<2, int>::next_type inner = outer.begin();
01815             for(; inner != outer.end(); ++inner)
01816             {
01817                 // manipulate current 1D subimage
01818             }
01819             \endcode
01820         */
01821     next_type begin () const
01822     {
01823         return *this;
01824     }
01825 
01826         /** Return the (N-1)-dimensional multi-iterator that points beyond 
01827             the last (N-1)-dimensional subarray of the 
01828             N-dimensional array this iterator is referring to.
01829             The result is only valid if this iterator refers to location
01830             0 in <em>all</em> dimensions below its current dimension N,
01831             otherwise it is undefined.
01832         */
01833     next_type end () const
01834     {
01835         next_type ret = *this;
01836         ret += this->m_shape [level-1];
01837         return ret;
01838     }
01839 
01840         /** Get a 1-dimensional, STL-compatible iterator for the
01841             given dimension, pointing to the current element of <TT>this</TT>.
01842             Usage:
01843 
01844             \code
01845 
01846             StridedMultiIterator<3, int> outer = ...;  // this iterator
01847 
01848             StridedMultiIterator<3, int>::iterator i = outer.iteratorForDimension(1);
01849             StridedMultiIterator<3, int>::iterator end = i + height;
01850             for(; i != end; ++i)
01851             {
01852                 // go down the current column starting at the location of 'outer'
01853             }
01854             \endcode            
01855         */
01856     iterator iteratorForDimension(unsigned int d) const
01857     {
01858         vigra_precondition(d <= level,
01859             "StridedMultiIterator<N>::iteratorForDimension(d): d < N required");
01860         return iterator(this->m_ptr, stride_traits::shift(this->m_stride, d),0);
01861     }
01862         /** Return the multi-iterator that operates on dimension K in order
01863             to manipulate this dimension directly. Usage:
01864                
01865             \code
01866                 
01867             StridedMultiIterator<3, int> i3 = ...;
01868                 
01869             i3.template dim<2>()++;  // increment outer dimension
01870             i3.template dim<0>()++;  // increment inner dimension
01871             \endcode
01872             
01873             For convenience, the same functionality is also available
01874             as <tt>dim0()</tt>, <tt>dim1()</tt> etc. up to <tt>dim4()</tt>:
01875             
01876             \code
01877                 
01878             StridedMultiIterator<3, int> i3 = ...;
01879                 
01880             i3.dim2()++;  // increment outer dimension
01881             i3.dim0()++;  // increment inner dimension
01882             \endcode            
01883         */
01884     template <unsigned int K>
01885     StridedMultiIterator<K+1, T, REFERENCE, POINTER> &
01886     dim()
01887     {
01888         return *this;
01889     }
01890 
01891     StridedMultiIterator<1, T, REFERENCE, POINTER> &
01892     dim0() { return *this; }
01893     StridedMultiIterator<2, T, REFERENCE, POINTER> &
01894     dim1() { return *this; }
01895     StridedMultiIterator<3, T, REFERENCE, POINTER> &
01896     dim2() { return *this; }
01897     StridedMultiIterator<4, T, REFERENCE, POINTER> &
01898     dim3() { return *this; }
01899     StridedMultiIterator<5, T, REFERENCE, POINTER> &
01900     dim4() { return *this; }
01901 
01902   protected:
01903 
01904     difference_type 
01905     total_stride(typename multi_difference_type::const_iterator d) const
01906     {
01907         return d[level]*this->m_stride[level] + base_type::total_stride(d);
01908     }
01909 
01910 };
01911 
01912 namespace detail {
01913 
01914 
01915 template <int K>
01916 struct CoordinateToScanOrder
01917 {
01918     template <int N>
01919     static MultiArrayIndex
01920     exec(const TinyVector <MultiArrayIndex, N> &shape,
01921          const TinyVector <MultiArrayIndex, N> & coordinate)
01922     {
01923         return coordinate[N-K] + shape[N-K] * CoordinateToScanOrder<K-1>::exec(shape, coordinate);
01924     }
01925 };
01926 
01927 template <>
01928 struct CoordinateToScanOrder<1>
01929 {
01930     template <int N>
01931     static MultiArrayIndex
01932     exec(const TinyVector <MultiArrayIndex, N> & /*shape*/,
01933          const TinyVector <MultiArrayIndex, N> & coordinate)
01934     {
01935         return coordinate[N-1];
01936     }
01937 };
01938 
01939 
01940 template <unsigned int M>
01941 struct MoveToScanOrderIndex
01942 {
01943     template <class Shape, class Ptr>
01944     static void 
01945     exec(MultiArrayIndex newIndex, Shape const & shape,
01946          Shape & point, Ptr & p, Shape const & strides)
01947     {
01948         enum { N = Shape::static_size };
01949         MultiArrayIndex newPos = newIndex % shape[N-1-M];
01950         p += (newPos - point[N-1-M]) * strides[N-1-M];
01951         point[N-1-M] = newPos;
01952         MoveToScanOrderIndex<M-1>::exec(newIndex / shape[N-1-M], shape, point, p, strides);
01953     }
01954     
01955     template <class Shape, class Ptr1, class Ptr2>
01956     static void 
01957     exec(MultiArrayIndex newIndex, Shape const & shape, Shape & point, 
01958          Ptr1 & p1, Shape const & strides1, Ptr2 & p2, Shape const & strides2)
01959     {
01960         enum { N = Shape::static_size };
01961         MultiArrayIndex newPos = newIndex % shape[N-1-M];
01962         p1 += (newPos - point[N-1-M]) * strides1[N-1-M];
01963         p2 += (newPos - point[N-1-M]) * strides2[N-1-M];
01964         point[N-1-M] = newPos;
01965         MoveToScanOrderIndex<M-1>::exec(newIndex / shape[N-1-M], shape, point, 
01966                                          p1, strides1, p2, strides2);
01967     }
01968 };
01969 
01970 template <>
01971 struct MoveToScanOrderIndex<0>
01972 {
01973     template <class Shape, class Ptr>
01974     static void 
01975     exec(MultiArrayIndex newIndex, Shape const & shape,
01976          Shape & point, Ptr & p, Shape const & strides)
01977     {
01978         enum { N = Shape::static_size }; 
01979         MultiArrayIndex newPos = std::min(newIndex, shape[N-1]);
01980         p += (newPos - point[N-1]) * strides[N-1];
01981         point[N-1] = newPos;
01982     }
01983     
01984     template <class Shape, class Ptr1, class Ptr2>
01985     static void 
01986     exec(MultiArrayIndex newIndex, Shape const & shape, Shape & point, 
01987          Ptr1 & p1, Shape const & strides1, Ptr2 & p2, Shape const & strides2)
01988     {
01989         enum { N = Shape::static_size }; 
01990         MultiArrayIndex newPos = std::min(newIndex, shape[N-1]);
01991         p1 += (newPos - point[N-1]) * strides1[N-1];
01992         p2 += (newPos - point[N-1]) * strides2[N-1];
01993         point[N-1] = newPos;
01994     }
01995 };
01996 
01997 #if 0 // alternative implementation, may be faster on some machines
01998 template <unsigned int M>
01999 struct MoveToScanOrderIndex
02000 {
02001     template <class Shape, class Ptr>
02002     static void 
02003     exec(MultiArrayIndex & newIndex, Shape const & shape,
02004          Shape & point, Ptr & p, Shape const & strides, MultiArrayIndex shapeStride = 1)
02005     {
02006         enum { N = Shape::static_size };
02007         MoveToScanOrderIndex<M-1>::exec(newIndex, shape, point, p, strides, shapeStride*shape[N-1-M]);
02008         MultiArrayIndex newPos = newIndex / shapeStride;
02009         p += (newPos - point[N-1-M]) * strides[N-1-M];
02010         point[N-1-M] = newPos;
02011         newIndex %= shapeStride;
02012     }
02013     
02014     template <class Shape, class Ptr1, class Ptr2>
02015     static void 
02016     exec(MultiArrayIndex & newIndex, Shape const & shape, Shape & point, 
02017          Ptr1 & p1, Shape const & strides1, Ptr2 & p2, Shape const & strides2, 
02018          MultiArrayIndex shapeStride = 1)
02019     {
02020         enum { N = Shape::static_size };
02021         MoveToScanOrderIndex<M-1>::exec(newIndex, shape, point, 
02022                                          p1, strides1, p2, strides2, shapeStride*shape[N-1-M]);
02023         MultiArrayIndex newPos = newIndex / shapeStride;
02024         p1 += (newPos - point[N-1-M]) * strides1[N-1-M];
02025         p2 += (newPos - point[N-1-M]) * strides2[N-1-M];
02026         point[N-1-M] = newPos;
02027         newIndex %= shapeStride;
02028     }
02029 };
02030 
02031 template <>
02032 struct MoveToScanOrderIndex<0>
02033 {
02034     template <class Shape, class Ptr>
02035     static void 
02036     exec(MultiArrayIndex & newIndex, Shape const & shape,
02037          Shape & point, Ptr & p, Shape const & strides, MultiArrayIndex shapeStride)
02038     {
02039         enum { N = Shape::static_size }; 
02040         MultiArrayIndex newPos = newIndex / shapeStride;
02041         p += (newPos - point[N-1]) * strides[N-1];
02042         point[N-1] = newPos;
02043         newIndex %= shapeStride;
02044     }
02045     
02046     template <class Shape, class Ptr1, class Ptr2>
02047     static void 
02048     exec(MultiArrayIndex & newIndex, Shape const & shape, Shape & point, 
02049          Ptr1 & p1, Shape const & strides1, Ptr2 & p2, Shape const & strides2, 
02050          MultiArrayIndex shapeStride)
02051     {
02052         enum { N = Shape::static_size }; 
02053         MultiArrayIndex newPos = newIndex / shapeStride;
02054         p1 += (newPos - point[N-1]) * strides1[N-1];
02055         p2 += (newPos - point[N-1]) * strides2[N-1];
02056         point[N-1] = newPos;
02057         newIndex %= shapeStride;
02058     }
02059 };
02060 #endif
02061 
02062 }
02063 
02064     /** \brief Sequential iterator for MultiArrayView.
02065         
02066         This iterator provides STL-compatible random access iterator functionality for arbitrary 
02067         \ref MultiArrayView instances, regardless of their shapes and strides. The
02068         class uses an implementation that minimizes speed penalties that could result from 
02069         non-trivial strides. The <i>scan-order</i> is defined such that dimensions are iterated 
02070         from front to back (first to last).
02071         
02072         You normally construct instances of this class by calling \ref MultiArrayView::begin() 
02073         and \ref MultiArrayView::end(). 
02074         
02075         The iterator supports all functions listed in the STL documentation for 
02076         <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random Access Iterators</a>.
02077     */
02078 template <unsigned int N, class T, class REFERENCE, class POINTER, unsigned int M = N>
02079 class StridedScanOrderIterator
02080 #ifndef DOXYGEN  // doxygen doesn't understand this inheritance
02081 : protected StridedScanOrderIterator<N, T, REFERENCE, POINTER, M-1>
02082 #endif
02083 {
02084     typedef StridedScanOrderIterator<N, T, REFERENCE, POINTER, M-1> base_type;
02085     enum { level = M-1 };
02086 
02087   public:
02088 
02089     typedef typename base_type::value_type value_type;
02090     typedef typename base_type::pointer pointer;
02091     typedef typename base_type::reference reference;
02092     typedef typename base_type::const_reference const_reference;
02093     typedef typename base_type::shape_type shape_type;
02094     typedef MultiIteratorStrideTraits<POINTER> stride_traits;
02095     typedef typename stride_traits::stride_type difference_type;
02096     typedef typename stride_traits::stride_array_type difference_array_type;
02097     typedef StridedScanOrderIterator iterator;
02098     typedef std::random_access_iterator_tag iterator_category;
02099     
02100     StridedScanOrderIterator()
02101     {}
02102     
02103     StridedScanOrderIterator(pointer i, 
02104                              shape_type const & shape, shape_type const & strides)
02105     : base_type(i, shape, strides)
02106     {}
02107 
02108     StridedScanOrderIterator & operator++()
02109     {
02110         base_type::operator++();
02111         if(this->point_[level-1] == this->shape_[level-1]) 
02112         {
02113             base_type::reset();
02114             this->i_ += this->strides_[level];
02115             ++this->point_[level];
02116         }
02117         return *this;
02118     }
02119 
02120     StridedScanOrderIterator operator++(int)
02121     {
02122         StridedScanOrderIterator res(*this);
02123         ++*this;
02124         return res;
02125     }
02126 
02127     StridedScanOrderIterator & operator+=(MultiArrayIndex i)
02128     {
02129         this->moveToScanOrderIndex(this->index_+i);
02130         return *this;
02131     }
02132 
02133     //! overload to add a coord-tuple:
02134     // it should be cheaper because the modulo-divisions are avoided
02135     StridedScanOrderIterator & operator+=(const shape_type &coordOffset)
02136     {
02137         this->moveRelative(dot(coordOffset,this->strides_),
02138                detail::CoordinateToScanOrder<N>::exec(this->shape_, coordOffset),
02139                coordOffset);
02140         return *this;
02141     }
02142     StridedScanOrderIterator & operator-=(const shape_type &coordOffset)
02143     {
02144     return operator+=(-coordOffset);
02145     }
02146 
02147     StridedScanOrderIterator & operator--()
02148     {
02149         base_type::operator--();
02150         if(this->point_[level-1] == -1) 
02151         {
02152             base_type::inverseReset();
02153             this->i_ -= this->strides_[level];
02154             --this->point_[level];
02155         }
02156         return *this;
02157     }
02158 
02159     StridedScanOrderIterator operator--(int)
02160     {
02161         StridedScanOrderIterator res(*this);
02162         --*this;
02163         return res;
02164     }
02165 
02166     StridedScanOrderIterator & operator-=(MultiArrayIndex i)
02167     {
02168         return operator+=(-i);
02169     }
02170 
02171     StridedScanOrderIterator getEndIterator() const
02172     {
02173         StridedScanOrderIterator res(*this);
02174         res.moveToScanOrderIndex(prod(this->shape_));
02175         return res;
02176     }
02177 
02178     bool atBorder() const
02179     {
02180         return base_type::atBorder() || 
02181                 this->point_[level] == 0 || 
02182                 this->point_[level] == this->shape_[level] - 1;
02183     }
02184     
02185     unsigned int neighborhoodType() const
02186     {
02187         unsigned int res = base_type::neighborhoodType();
02188         if(this->point_[level] == 0)
02189             res |= (1 << 2*level);
02190         if(this->point_[level] == this->shape_[level]-1)
02191             res |= (2 << 2*level);
02192         return res;
02193     }
02194     
02195     StridedScanOrderIterator operator+(MultiArrayIndex d) const
02196     {
02197         return StridedScanOrderIterator(*this) += d;
02198     }
02199 
02200     StridedScanOrderIterator operator-(MultiArrayIndex d) const
02201     {
02202         return StridedScanOrderIterator(*this) -= d;
02203     }
02204 
02205 
02206     StridedScanOrderIterator operator+(const shape_type &coordOffset) const
02207     {
02208         return StridedScanOrderIterator(*this) += coordOffset;
02209     }
02210 
02211     StridedScanOrderIterator operator-(const shape_type &coordOffset) const
02212     {
02213         return StridedScanOrderIterator(*this) -= coordOffset;
02214     }
02215 
02216 
02217     
02218     MultiArrayIndex operator-(StridedScanOrderIterator const & r) const
02219     {
02220         return base_type::operator-(r);
02221     }
02222 
02223     bool operator==(StridedScanOrderIterator const & r)
02224     {
02225         return base_type::operator==(r);
02226     }
02227 
02228     bool operator!=(StridedScanOrderIterator const & r) const
02229     {
02230         return base_type::operator!=(r);
02231     }
02232 
02233     bool operator<(StridedScanOrderIterator const & r) const
02234     {
02235         return base_type::operator<(r);
02236     }
02237 
02238     bool operator<=(StridedScanOrderIterator const & r) const
02239     {
02240         return base_type::operator<=(r);
02241     }
02242 
02243     bool operator>(StridedScanOrderIterator const & r) const
02244     {
02245         return base_type::operator>(r);
02246     }
02247 
02248     bool operator>=(StridedScanOrderIterator const & r) const
02249     {
02250         return base_type::operator>=(r);
02251     }
02252 
02253     using base_type::point;
02254     using base_type::shape;
02255     using base_type::strides;
02256     using base_type::ptr;
02257     using base_type::index;
02258     using base_type::operator*;
02259     using base_type::operator->;
02260     using base_type::operator[];
02261 
02262   protected:
02263     void reset()
02264     {
02265         this->i_ -= this->shape_[level]*this->strides_[level];
02266         this->point_[level] = 0;
02267     }
02268 
02269     void inverseReset()
02270     {
02271         this->i_ += this->shape_[level]*this->strides_[level];
02272         this->point_[level] = this->shape_[level]-1;
02273     }
02274     
02275     template <class Ptr>
02276     void increment(Ptr & p2, shape_type const & strides2)
02277     {
02278         base_type::increment(p2, strides2);
02279         if(this->point_[level-1] == this->shape_[level-1]) 
02280         {
02281             base_type::reset();
02282             this->i_ += this->strides_[level];
02283             p2 += strides2[level] - this->shape_[level-1]*strides2[level-1];
02284             ++this->point_[level];
02285         }
02286     }
02287     
02288     template <class Ptr>
02289     void decrement(Ptr & p2, shape_type const & strides2)
02290     {
02291         base_type::decrement(p2, strides2);
02292         if(this->point_[level-1] == -1) 
02293         {
02294             base_type::inverseReset();
02295             this->i_ -= this->strides_[level];
02296             p2 -= strides2[level] - this->shape_[level-1]*strides2[level-1];
02297             --this->point_[level];
02298         }
02299     }
02300     StridedScanOrderIterator & moveRelative(const MultiArrayIndex &pointerOffset,
02301                                             const MultiArrayIndex &indexOffset,
02302                                             const shape_type &coordOffset)
02303     {
02304         base_type::moveRelative(pointerOffset, indexOffset, coordOffset);
02305         this->point_[level] += coordOffset[level];
02306         return *this;
02307     }
02308 };
02309 
02310 template <unsigned int N, class T, class REFERENCE, class POINTER>
02311 class StridedScanOrderIterator<N, T, REFERENCE, POINTER, 1>
02312 {
02313     enum { level = 0 };
02314 
02315   public:
02316 
02317     typedef T value_type;
02318     typedef POINTER pointer;
02319     typedef T const * const_pointer;
02320     typedef REFERENCE reference;
02321     typedef T const & const_reference;
02322     typedef typename MultiArrayShape<N>::type shape_type;
02323     typedef MultiIteratorStrideTraits<POINTER> stride_traits;
02324     typedef typename stride_traits::stride_type difference_type;
02325     typedef typename stride_traits::stride_array_type difference_array_type;
02326     typedef StridedScanOrderIterator iterator;
02327     typedef std::random_access_iterator_tag iterator_category;
02328 
02329     StridedScanOrderIterator()
02330     : i_((pointer)0),
02331       index_(0)
02332     {}
02333     
02334     StridedScanOrderIterator(pointer i, 
02335                              shape_type const & shape, shape_type const & strides)
02336     : i_(i),
02337       shape_(shape),
02338       strides_(strides),
02339       index_(0)
02340     {}
02341 
02342     StridedScanOrderIterator & operator++()
02343     {
02344         i_ += strides_[level];
02345         ++point_[level];
02346         ++index_;
02347         return *this;
02348     }
02349 
02350     StridedScanOrderIterator operator++(int)
02351     {
02352         StridedScanOrderIterator res(*this);
02353         ++*this;
02354         return res;
02355     }
02356 
02357     StridedScanOrderIterator & operator+=(MultiArrayIndex i)
02358     {
02359         this->moveToScanOrderIndex(index_+i);
02360         return *this;
02361     }
02362     
02363     //! overload to add a coord-tuple:
02364     StridedScanOrderIterator & operator+=(const shape_type &coordOffset)
02365     {
02366         this->moveRelative(dot(coordOffset,strides_), 
02367                detail::CoordinateToScanOrder<N>::exec(shape_, coordOffset),
02368                coordOffset);
02369         return *this;
02370     }
02371 
02372     StridedScanOrderIterator & operator-=(const shape_type &coordOffset)
02373     {
02374         return operator+=(-coordOffset);
02375     }
02376 
02377     StridedScanOrderIterator & operator--()
02378     {
02379         i_ -= strides_[level];
02380         --point_[level];
02381         --index_;
02382         return *this;
02383     }
02384 
02385     StridedScanOrderIterator operator--(int)
02386     {
02387         StridedScanOrderIterator res(*this);
02388         --this;
02389         return res;
02390     }
02391 
02392     StridedScanOrderIterator & operator-=(MultiArrayIndex i)
02393     {
02394         return operator+=(-i);
02395     }
02396     
02397     reference operator*()
02398     {
02399         return *i_;
02400     }
02401 
02402     const_reference operator*() const
02403     {
02404         return *i_;
02405     }
02406     
02407     pointer operator->()
02408     {
02409         return i_;
02410     }
02411 
02412     const_pointer operator->() const
02413     {
02414         return i_;
02415     }
02416 
02417     pointer ptr()
02418     {
02419         return i_;
02420     }
02421 
02422     const_pointer ptr() const
02423     {
02424         return i_;
02425     }
02426 
02427     reference operator[](MultiArrayIndex i)
02428     {
02429         StridedScanOrderIterator t(*this);
02430         t.moveToScanOrderIndex(index_+i);
02431         return *t;
02432     }
02433 
02434     const_reference operator[](MultiArrayIndex i) const
02435     {
02436         StridedScanOrderIterator t(*this);
02437         t.moveToScanOrderIndex(index_+i);
02438         return *t;
02439     }
02440 
02441     StridedScanOrderIterator
02442     operator+(MultiArrayIndex d) const
02443     {
02444         return StridedScanOrderIterator(*this) += d;
02445     }
02446 
02447     StridedScanOrderIterator
02448     operator-(MultiArrayIndex d) const
02449     {
02450         return StridedScanOrderIterator(*this) -= d;
02451     }
02452 
02453     StridedScanOrderIterator operator+(const shape_type &coordOffset) const
02454     {
02455         return StridedScanOrderIterator(*this) += coordOffset;
02456     }
02457 
02458     StridedScanOrderIterator operator-(const shape_type &coordOffset) const
02459     {
02460         return StridedScanOrderIterator(*this) -= coordOffset;
02461     }
02462     
02463     MultiArrayIndex
02464     operator-(StridedScanOrderIterator const & r) const
02465     {
02466         return index() - r.index();
02467     }
02468 
02469     bool
02470     operator==(StridedScanOrderIterator const & r)
02471     {
02472         return index() == r.index();
02473     }
02474 
02475     bool
02476     operator!=(StridedScanOrderIterator const & r) const
02477     {
02478         return index() != r.index();
02479     }
02480 
02481     bool
02482     operator<(StridedScanOrderIterator const & r) const
02483     {
02484         return index() < r.index();
02485     }
02486 
02487     bool
02488     operator<=(StridedScanOrderIterator const & r) const
02489     {
02490         return index() <= r.index();
02491     }
02492 
02493     bool
02494     operator>(StridedScanOrderIterator const & r) const
02495     {
02496         return index() > r.index();
02497     }
02498 
02499     bool
02500     operator>=(StridedScanOrderIterator const & r) const
02501     {
02502         return index() >= r.index();
02503     }
02504 
02505 
02506     bool atBorder() const
02507     {
02508         return point_[level] == 0 || point_[level] == shape_[level] - 1;
02509     }
02510     
02511     MultiArrayIndex index() const
02512     {
02513         return index_;
02514     }
02515     
02516     shape_type const & point() const
02517     {
02518         return point_;
02519     }
02520     
02521     shape_type const & shape() const
02522     {
02523         return shape_;
02524     }
02525     
02526     shape_type const & strides() const
02527     {
02528         return strides_;
02529     }
02530     
02531     StridedScanOrderIterator getEndIterator() const
02532     {
02533         StridedScanOrderIterator res(*this);
02534         res.moveToScanOrderIndex(prod(shape_));
02535         return res;
02536     }
02537     
02538     unsigned int neighborhoodType() const
02539     {
02540         unsigned int res = 0;
02541         if(this->point_[level] == 0)
02542             res |= 1;
02543         if(this->point_[level] == this->shape_[level]-1)
02544             res |= 2;
02545         return res;
02546     }
02547 
02548   protected:
02549     void reset()
02550     {
02551         i_ -= shape_[level]*strides_[level];
02552         point_[level] = 0;
02553     }
02554     
02555     void inverseReset()
02556     {
02557         i_ += shape_[level]*strides_[level];
02558         point_[level] = shape_[level] - 1;
02559     }
02560     
02561     void moveToScanOrderIndex(MultiArrayIndex newIndex)
02562     {
02563         index_ = newIndex;
02564         detail::MoveToScanOrderIndex<N-1>::exec(newIndex, shape_, point_, i_, strides_);
02565     }
02566     
02567     template <class Ptr>
02568     void increment(Ptr & p2, shape_type const & strides2)
02569     {
02570         operator++();
02571         p2 += strides2[level];
02572     }
02573     
02574     template <class Ptr>
02575     void decrement(Ptr & p2, shape_type const & strides2)
02576     {
02577         operator--();
02578         p2 -= strides2[level];
02579     }
02580     
02581     template <class Ptr>
02582     void moveToScanOrderIndex(MultiArrayIndex newIndex, Ptr & p2, shape_type const & strides2)
02583     {
02584         index_ = newIndex;
02585         detail::MoveToScanOrderIndex<N-1>::exec(newIndex, shape_, point_, i_, strides_, p2, strides2);
02586     }
02587 
02588     StridedScanOrderIterator & moveRelative(const MultiArrayIndex &pointerOffset,
02589                                             const MultiArrayIndex &indexOffset,
02590                                             const shape_type &coordOffset)
02591     {
02592         point_[level] += coordOffset[level];
02593 
02594         index_+= indexOffset;
02595         i_ += pointerOffset;
02596         
02597         return *this;
02598     }
02599 
02600     pointer i_;
02601     shape_type point_, shape_, strides_;
02602     MultiArrayIndex index_;
02603 };
02604 
02605 
02606 //@}
02607 
02608 } // namespace vigra
02609 
02610 #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.9.0 (Tue Nov 6 2012)