vigra - vigra/multi_iterator.hxx Source File

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

vigra/multi_iterator.hxx |

    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)