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

details vigra/multi_iterator.hxx VIGRA

00001 /************************************************************************/
00002 /*                                                                      */
00003 /*               Copyright 2003 by Gunnar Kedenburg                     */
00004 /*       Cognitive Systems Group, University of Hamburg, Germany        */
00005 /*                                                                      */
00006 /*    This file is part of the VIGRA computer vision library.           */
00007 /*    ( Version 1.3.2, Jan 27 2005 )                                    */
00008 /*    ( Version 1.3.0, Sep 10 2004 )                                    */
00009 /*    You may use, modify, and distribute this software according       */
00010 /*    to the terms stated in the LICENSE file included in               */
00011 /*    the VIGRA distribution.                                           */
00012 /*                                                                      */
00013 /*    The VIGRA Website is                                              */
00014 /*        http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/      */
00015 /*    Please direct questions, bug reports, and contributions to        */
00016 /*        koethe@informatik.uni-hamburg.de                              */
00017 /*                                                                      */
00018 /*  THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR          */
00019 /*  IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED      */
00020 /*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. */
00021 /*                                                                      */
00022 /************************************************************************/
00023 
00024 
00025 #ifndef VIGRA_MULTI_ITERATOR_HXX
00026 #define VIGRA_MULTI_ITERATOR_HXX
00027 
00028 #include <sys/types.h>
00029 #include "vigra/tinyvector.hxx"
00030 #include "vigra/iteratortags.hxx"
00031 
00032 namespace vigra {
00033 
00034 
00035 template <unsigned int N, class T, 
00036           class REFERENCE = T &, class POINTER = T *> class MultiIterator;
00037 template <unsigned int N, class T, 
00038           class REFERENCE = T &, class POINTER = T *> class StridedMultiIterator;
00039 
00040 /** \page MultiIteratorPage  Multi-dimensional Array Iterators
00041 
00042     General iterators for arrays of arbitrary dimension.
00043 
00044 
00045 <p>
00046 <DL>
00047 <DT>
00048     <IMG BORDER=0 ALT="-" SRC="documents/bullet.gif">
00049     \ref vigra::MultiIterator
00050     <DD> <em>Iterator for unstrided \ref vigra::MultiArrayView</em>
00051 <DT>
00052     <IMG BORDER=0 ALT="-" SRC="documents/bullet.gif"> 
00053     \ref vigra::MultiIteratorBase::type
00054     <DD> <em>Inner class implementing most of the functionality of \ref vigra::MultiIterator</em>
00055 <DT>
00056     <IMG BORDER=0 ALT="-" SRC="documents/bullet.gif">
00057     \ref vigra::StridedMultiIterator
00058     <DD> <em>Iterator for strided \ref vigra::MultiArrayView</em>
00059 <DT>
00060     <IMG BORDER=0 ALT="-" SRC="documents/bullet.gif">
00061     \ref vigra::StridedMultiIteratorBase::type
00062     <DD> <em>Inner class implementing most of the functionality of \ref vigra::StridedMultiIterator</em>
00063 </DL>
00064 </p>
00065 
00066 <p>
00067     The Multidimensional Iterator concept allows navigation on arrays
00068     of arbitrary dimension. It provides two modes of iteration: 
00069     <em>direct traveral</em>, and <em>hierarchical traversal</em>.
00070     In general, hierarchical traversal will be faster, while only 
00071     direct traversal allows for true random access in all dimensions.
00072     Via the <tt>dim<K>()</tt> function, operations applying to a particular
00073     dimension can be used in the direct traversal mode. In contrast,
00074     direct traversal functions should not be used in the hierarchical mode
00075     because the hierarchical functions are only well-defined if the
00076     iterator points to element 0 in all dimensions below its current dimension.
00077     The current dimension of a <tt>MultiIterator&lt;N, ..&gt;</tt> is <tt>N-1</tt>.
00078 </p>
00079 <h3>Gerneral Requirements for MultiIterator</h3>
00080 <p>
00081 <table border=2 cellspacing=0 cellpadding=2 width="100%">
00082 <tr><td>
00083     \htmlonly
00084     <th colspan=2>
00085     \endhtmlonly
00086     Local Types
00087     \htmlonly
00088     </th><th>
00089     \endhtmlonly
00090     Meaning
00091     \htmlonly
00092     </th>
00093     \endhtmlonly
00094 </td></tr>
00095 <tr><td>
00096     \htmlonly
00097     <td colspan=2>
00098     \endhtmlonly
00099     <tt>MultiIterator::value_type</tt></td><td>the underlying arrays's pixel type</td>
00100 </tr>
00101 <tr>
00102     <td>
00103     \htmlonly
00104     <td colspan=2>
00105     \endhtmlonly
00106     <tt>MultiIterator::reference</tt></td>
00107     <td>the iterator's reference type (return type of <TT>*iter</TT>). Will be
00108     <tt>value_type &</tt> for a mutable iterator, and convertible to
00109     <tt>value_type const &</tt> for a const iterator.</td>
00110 </tr>
00111 <tr>
00112     <td>
00113     \htmlonly
00114     <td colspan=2>
00115     \endhtmlonly
00116     <tt>MultiIterator::pointer</tt></td>
00117     <td>the iterator's pointer type (return type of <TT>iter.operator->()</TT>). Will be
00118     <tt>value_type *</tt> for a mutable iterator, and convertible to
00119     <tt>value_type const *</tt> for a const iterator.</td>
00120 </tr>
00121 <tr>
00122     <td>
00123     \htmlonly
00124     <td colspan=2>
00125     \endhtmlonly
00126     <tt>MultiIterator::iterator_category</tt></td>
00127     <td>the iterator tag (<tt>vigra::multi_dimensional_traverser_tag</tt>)</td>
00128 </tr>
00129 <tr><td>
00130     \htmlonly
00131     <th>
00132     \endhtmlonly
00133     Operation
00134     \htmlonly
00135     </th><th>
00136     \endhtmlonly
00137     Result
00138     \htmlonly
00139     </th><th>
00140     \endhtmlonly
00141     Semantics
00142     \htmlonly
00143     </th>
00144     \endhtmlonly
00145 </td></tr>
00146 <tr><td>
00147     \htmlonly
00148     <td colspan=2>
00149     \endhtmlonly
00150     <tt>MultiIterator k;</tt></td><td>default constructor</td>
00151 </tr>
00152 <tr><td>
00153     \htmlonly
00154     <td colspan=2>
00155     \endhtmlonly
00156     <tt>MultiIterator k(i);</tt></td><td>copy constructor</td>
00157 </tr>
00158 <tr>
00159     <td><tt>k = i</tt></td>
00160     <td><tt>MultiIterator &</tt></td><td>assignment</td>
00161 </tr>
00162 <tr>
00163     <td><tt>i == j</tt></td><td><tt>bool</tt></td>
00164     <td>equality (iterators point to the same element)</td>
00165 </tr>
00166 <tr>
00167     <td><tt>i != j</tt></td><td><tt>bool</tt></td>
00168     <td>inequality (iterators don't point to the same element)</td>
00169 </tr>
00170 <tr>
00171     <td><tt>*i</tt></td><td><tt>MultiIterator::reference</tt></td>
00172     <td>access the current element</td>
00173 </tr>
00174 <tr>
00175     <td><tt>i->member()</tt></td><td>depends on operation</td>
00176     <td>call member function of underlying pixel type via <tt>operator-></tt> of iterator</td>
00177 </tr>
00178 </table>
00179 </p>
00180 <h3>Requirements for Direct Traversal</h3>
00181 <p>
00182 <table border=2 cellspacing=0 cellpadding=2 width="100%">
00183 <tr><td>
00184     \htmlonly
00185     <th colspan=2>
00186     \endhtmlonly
00187     Local Types
00188     \htmlonly
00189     </th><th>
00190     \endhtmlonly
00191     Meaning
00192     \htmlonly
00193     </th>
00194     \endhtmlonly
00195 </td></tr>
00196 <tr><td>
00197     \htmlonly
00198     <td colspan=2>
00199     \endhtmlonly
00200     <tt>MultiIterator::multi_difference_type</tt></td>
00201     <td>the iterator's multi-dimensional difference type (<TT>TinyVector&lt;ptrdiff_t, N&gt;</TT>)</td>
00202 </tr>
00203 <tr><td>
00204     \htmlonly
00205     <th>
00206     \endhtmlonly
00207     Operation
00208     \htmlonly
00209     </th><th>
00210     \endhtmlonly
00211     Result
00212     \htmlonly
00213     </th><th>
00214     \endhtmlonly
00215     Semantics
00216     \htmlonly
00217     </th>
00218     \endhtmlonly
00219 </td></tr>
00220 <tr>
00221     <td><tt>i += diff</tt></td><td><tt>MultiIterator &</tt></td>
00222     <td>add offset to current position</td>
00223 </tr>
00224 <tr>
00225     <td><tt>i -= diff</tt></td><td><tt>MultiIterator &</tt></td>
00226     <td>subtract offset from current position</td>
00227 </tr>
00228 <tr>
00229     <td><tt>i + diff</tt></td><td><tt>MultiIterator</tt></td>
00230     <td>create traverser by adding offset</td>
00231 </tr>
00232 <tr>
00233     <td><tt>i - diff</tt></td><td><tt>MultiIterator</tt></td>
00234     <td>create traverser by subtracting offset</td>
00235 </tr>
00236 <tr>
00237     <td><tt>i[diff]</tt></td><td><tt>MultiIterator::reference</tt></td>
00238     <td>access element at offset <tt>diff</tt></td>
00239 </tr>
00240 <tr>
00241     <td><tt>i.dim<K>()</tt></td><td><tt>MultiIterator&lt;K+1, T, ...&gt;</tt></td>
00242     <td>Access the traverser with the current dimension set to K. Typically used to call
00243         navigation functions referring to a particular dimension.<br>
00244         Example (assuming <tt>i, j</tt> are 3-dimensional):<br>
00245         \code
00246         i.dim<0>()++;   // increment dimension 0 
00247         i.dim<1>()++;   // increment dimension 1 
00248         i.dim<2>()++;   // increment dimension 2 
00249         
00250         j += MultiIterator::multi_difference_type(1,1,1);    // same effect
00251         \endcode
00252     </td>
00253 </tr>
00254 <tr><td>
00255     \htmlonly
00256     <td colspan=3>
00257     \endhtmlonly
00258        <tt>i, j</tt> are of type <tt>MultiIterator</tt><br>
00259        <tt>diff</tt> is of type <tt>MultiIterator::multi_difference_type</tt><br>
00260        <tt>K</tt> is an integer compile-time constant
00261     </td>
00262 </tr>
00263 </table>
00264 </p>
00265 <p>
00266 Note that it is impossible to support an <tt>operator-</tt> between two iterators which returns
00267 a <tt>MultiIterator::multi_difference_type</tt> because it is impossible to decide to which
00268 dimension a difference applies. Consider for example, a 2-dimensional iterator <tt>i</tt>, and
00269 let <tt>j = i + multi_difference_type(width, 0)</tt>, <tt>k = i + multi_difference_type(0,1)</tt>, 
00270 where <tt>width</tt> is the array's total width. In general, <tt>j</tt> and <tt>k</tt> point to 
00271 the same memory location, so that the two cases cannot easily be distinguished (it is possible,
00272 but iterator performance will suffer significantly, as is experienced with 
00273 \ref vigra::ImageIterator where differencing is allowed).
00274 </p>
00275 
00276 <h3>Requirements for Hierarchical Traversal</h3>
00277 <p>
00278 <table border=2 cellspacing=0 cellpadding=2 width="100%">
00279 <tr><td>
00280     \htmlonly
00281     <th colspan=2>
00282     \endhtmlonly
00283     Local Types
00284     \htmlonly
00285     </th><th>
00286     \endhtmlonly
00287     Meaning
00288     \htmlonly
00289     </th>
00290     \endhtmlonly
00291 </td></tr>
00292 <tr>
00293     <td>
00294     \htmlonly
00295     <td colspan=2>
00296     \endhtmlonly
00297     <tt>MultiIterator::difference_type</tt></td>
00298     <td>the iterator's difference type (<TT>ptrdiff_t</TT>)</td>
00299 </tr>
00300 <tr>
00301     <td>
00302     \htmlonly
00303     <td colspan=2>
00304     \endhtmlonly
00305     <tt>MultiIterator::next_type</tt></td><td>type of the next iterator
00306        (referring to the next lower dimension) in the hierarchy</td>
00307 </tr>
00308 <tr><td>
00309     \htmlonly
00310     <th>
00311     \endhtmlonly
00312     Operation
00313     \htmlonly
00314     </th><th>
00315     \endhtmlonly
00316     Result
00317     \htmlonly
00318     </th><th>
00319     \endhtmlonly
00320     Semantics
00321     \htmlonly
00322     </th>
00323     \endhtmlonly
00324 </td></tr>
00325 <tr>
00326     <td><tt>++i</tt></td><td><tt>MultiIterator &</tt></td>
00327     <td>pre-increment iterator in its current dimension</td>
00328 </tr>
00329 <tr>
00330     <td><tt>i++</tt></td><td><tt>MultiIterator</tt></td>
00331     <td>post-increment iterator in its current dimension</td>
00332 </tr>
00333 <tr>
00334     <td><tt>--i</tt></td><td><tt>MultiIterator &</tt></td>
00335     <td>pre-decrement iterator in its current dimension</td>
00336 </tr>
00337 <tr>
00338     <td><tt>i--</tt></td><td><tt>MultiIterator</tt></td>
00339     <td>post-decrement iterator in its current dimension</td>
00340 </tr>
00341 <tr>
00342     <td><tt>i += d</tt></td><td><tt>MultiIterator &</tt></td>
00343     <td>add <tt>d</tt> in current dimension</td>
00344 </tr>
00345 <tr>
00346     <td><tt>i -= d</tt></td><td><tt>MultiIterator &</tt></td>
00347     <td>subtract <tt>d</tt> in from dimension</td>
00348 </tr>
00349 <tr>
00350     <td><tt>i + d</tt></td><td><tt>MultiIterator</tt></td>
00351     <td>create new iterator by adding <tt>d</tt> in current dimension</td>
00352 </tr>
00353 <tr>
00354     <td><tt>i - d</tt></td><td><tt>MultiIterator</tt></td>
00355     <td>create new iterator by subtracting <tt>d</tt> in current dimension</td>
00356 </tr>
00357 <tr>
00358     <td><tt>i - j</tt></td><td><tt>difference_type</tt></td>
00359     <td>difference of <tt>i</tt> and <tt>j</tt> in the current dimension<br>
00360     <em>Note:</em> The result of this operation is undefined if the iterator
00361     doesn't point to element 0 in all dimensions below its current dimension.</td>
00362 </tr>
00363 <tr>
00364     <td><tt>i < j</tt></td><td><tt>bool</tt></td>
00365     <td><tt>i - j < 0</tt><br>
00366     <em>Note:</em> The result of this operation is undefined if the iterator
00367     doesn't point to element 0 in all dimensions below its current dimension.</td>
00368 </tr>
00369 <tr>
00370     <td><tt>i[d]</tt></td><td><tt>MultiIterator::reference</tt></td>
00371     <td>access element by adding offset <tt>d</tt> in current dimension</td>
00372 </tr>
00373 <tr>
00374     <td><tt>i.begin()</tt></td><td><tt>next_type</tt></td>
00375     <td>create the hierarchical iterator poiting to the first element in the 
00376     next lower dimension.<br>
00377     <em>Note:</em> The result of this operation is undefined if the iterator
00378     doesn't point to element 0 in all dimensions below its current dimension.<br>
00379     Usage:<br>
00380     \code
00381     MultiIterator<3, int> i3 = ..., end3 = ...;
00382     for(; i3 != end3; ++i3)
00383     {
00384         MultiIterator<3, int>::next_type i2 = i3.begin(), end2 = i3.end();
00385         for(; i2 != end2; ++i2)
00386         {
00387             MultiIterator<3, int>::next_type::next_type i1 = i2.begin(), end1 = i2.end();
00388             for(; i1 != end1; ++i1)
00389             {
00390                 ... // do something with the current element
00391             }
00392         }
00393     }
00394     
00395     \endcode
00396     </td>
00397 </tr>
00398 <tr>
00399     <td><tt>i.end()</tt></td><td><tt>next_type</tt></td>
00400     <td>create the hierarchical iterator poiting to the past-the-end location in the 
00401     next lower dimension.<br>
00402     <em>Note:</em> The result of this operation is undefined if the iterator
00403     doesn't point to element 0 in all dimensions below its current dimension.</td>
00404 </tr>
00405 <tr>
00406     <td>
00407     \htmlonly
00408     <td colspan=3>
00409     \endhtmlonly
00410        <tt>i, j</tt> are of type <tt>MultiIterator</tt><br>
00411        <tt>d</tt> is of type <tt>MultiIterator::difference_type</tt>
00412     </td>
00413 </tr>
00414 </table>
00415 </p>
00416 
00417 */
00418 
00419 /** \addtogroup MultiIteratorGroup  Multi-dimensional Array Iterators
00420 
00421     \brief General iterators for arrays of arbitrary dimension.
00422 */
00423 //@{
00424 
00425 
00426 /********************************************************/
00427 /*                                                      */
00428 /*                    MultiIteratorBase                 */
00429 /*                                                      */
00430 /********************************************************/
00431 
00432 /** \brief Enclosing class for \ref vigra::MultiIterator base classes.
00433 
00434 This design is necessary for compilers that do not support partial
00435 specialization (otherwise, MultiIterator could be specialized directly).
00436 
00437 <b>\#include</b> "<a href="multi__iterator_8hxx-source.html">vigra/multi_iterator.hxx</a>"
00438 
00439 Namespace: vigra
00440 */
00441 template <unsigned int N>
00442 class MultiIteratorBase
00443 {
00444   public:
00445         /** \brief Base class for \ref vigra::MultiIterator.
00446 
00447         This class implements the multi-iterator by means of the enclosed template 
00448         class <tt>type</tt>. This design is necessary for compilers that do not support partial
00449         specialization (otherwise, MultiIterator could be specialized directly).
00450 
00451         <b>\#include</b> "<a href="multi__iterator_8hxx-source.html">vigra/multi_iterator.hxx</a>"
00452 
00453         Namespace: vigra
00454         */
00455     template <class T, class REFERENCE, class POINTER>
00456     class type : public MultiIterator <N-1, T, REFERENCE, POINTER>
00457     {
00458     public:
00459             /** the type of the parent in the inheritance hierarchy.
00460              */
00461         typedef MultiIterator <N-1, T, REFERENCE, POINTER> base_type;
00462 
00463     public:
00464         
00465             /** the iterator's level in the dimension hierarchy
00466              */
00467         enum { level = N-1 };
00468 
00469             /** the iterator's value type
00470              */
00471         typedef T value_type;
00472 
00473             /** reference type (result of operator[] and operator*())
00474              */
00475         typedef REFERENCE reference;
00476 
00477             /** pointer type (result of operator->())
00478              */
00479         typedef POINTER pointer;
00480 
00481             /** difference type (used for offsetting along one axis)
00482              */
00483         typedef ptrdiff_t difference_type;
00484 
00485             /** multi difference type 
00486                 (used for offsetting along all axes simultaneously)
00487              */
00488         typedef TinyVector<difference_type, N> multi_difference_type;
00489 
00490             /** the next type, this is a non-standard typedef denoting the
00491                 type of the multi-iterator with the next-lower dimension.
00492             */
00493         typedef MultiIterator <level, T, REFERENCE, POINTER> next_type;
00494 
00495             /** the 1-dimensional iterator for this iterator hierarchy
00496                 (result of iteratorForDimension()).
00497             */
00498         typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator;
00499 
00500             /** the iterator tag (image traverser)
00501             */
00502         typedef multi_dimensional_traverser_tag iterator_category;
00503 
00504             
00505         /* use default copy constructor and assignment operator */
00506             
00507             /** default constructor.
00508             */
00509         type ()
00510         {}
00511 
00512             /** construct from pointer, strides (offset of a sample to the
00513                 next) for every dimension, and the shape.
00514             */
00515         type (pointer ptr,
00516               const difference_type *stride,
00517               const difference_type *shape)
00518             : base_type (ptr, stride, shape)
00519         {}
00520 
00521             /** prefix-increment the iterator in it's current dimension
00522              */
00523         void operator++ ()
00524         {
00525             type::m_ptr += type::m_stride [level];
00526         }
00527 
00528             /** prefix-decrement the iterator in it's current dimension
00529              */
00530         void operator-- ()
00531         {
00532             type::m_ptr -= type::m_stride [level];
00533         }
00534 
00535             /** postfix-increment the iterator in it's current dimension
00536              */
00537         type operator++ (int)
00538         {
00539             type ret = *this;
00540             ++(*this);
00541             return ret;
00542         }
00543 
00544             /** postfix-decrement the iterator in it's current dimension
00545              */
00546         type operator-- (int)
00547         {
00548             type ret = *this;
00549             --(*this);
00550             return ret;
00551         }
00552 
00553             /** increment the iterator in it's current dimension
00554                 by the given value.
00555             */
00556         type & operator+= (difference_type n)
00557         {
00558             type::m_ptr += n * type::m_stride [level];
00559             return *this;
00560         }
00561         
00562             /** increment the iterator in all dimensions
00563                 by the given offset.
00564             */
00565         type & operator+= (multi_difference_type const & d)
00566         {
00567             type::m_ptr += total_stride(d.begin());
00568             return *this;
00569         }
00570 
00571             /** decrement the iterator in it's current dimension
00572                 by the given value.
00573             */
00574         type & operator-= (difference_type n)
00575         {
00576             type::m_ptr -= n * type::m_stride [level];
00577             return *this;
00578         }
00579         
00580             /** decrement the iterator in all dimensions
00581                 by the given offset.
00582             */
00583         type & operator-= (multi_difference_type const & d)
00584         {
00585             type::m_ptr -= total_stride(d.begin());
00586             return *this;
00587         }
00588         
00589             /** difference of two iterators in the current dimension.
00590                 The result of this operation is undefined if the iterator
00591                 doesn't point to element 0 in all dimensions below its current dimension.
00592             */
00593         difference_type operator- (type const & d) const
00594         {
00595             return (type::m_ptr - d.m_ptr) / type::m_stride[level];
00596         }
00597 
00598         /* operators *, ->, ==, !=, < inherited */
00599 
00600             /** access the array element at the given offset in 
00601             the current dimension.
00602             */
00603         reference operator[] (difference_type n) const
00604         {
00605             return type::m_ptr [n* type::m_stride [level]];
00606         }
00607 
00608             /** access the array element at the given offset.
00609             */
00610         reference operator[] (multi_difference_type const & d) const
00611         {
00612             return type::m_ptr [total_stride(d.begin())];
00613         }
00614 
00615             /** Return the (N-1)-dimensional multi-iterator that points to 
00616                 the first (N-1)-dimensional subarray of the 
00617                 N-dimensional array this iterator is referring to.
00618                 The result is only valid if this iterator refers to location
00619                 0 in <em>all</em> dimensions below its current dimension N,
00620                 otherwise it is undefined. Usage:
00621                 
00622                 \code
00623                 
00624                 MultiIterator<2, int> outer = ...;  // this iterator
00625                 
00626                 MultiIterator<2, int>::next_type inner = outer.begin();
00627                 for(; inner != outer.end(); ++inner)
00628                 {
00629                     // manipulate current 1D subimage
00630                 }
00631                 \endcode
00632             */
00633         next_type begin () const
00634         {
00635             return *this;
00636         }
00637 
00638             /** Return the (N-1)-dimensional multi-iterator that points beyond 
00639                 the last (N-1)-dimensional subarray of the 
00640                 N-dimensional array this iterator is referring to.
00641                 The result is only valid if this iterator refers to location
00642                 0 in <em>all</em> dimensions below its current dimension N,
00643                 otherwise it is undefined.
00644             */
00645         next_type end () const
00646         {
00647             next_type ret = *this;
00648             ret += type::m_shape [level-1];
00649             return ret;
00650         }
00651 
00652             /** Get a 1-dimensional, STL-compatible iterator for the
00653                 given dimension, pointing to the current element of <TT>this</TT>.
00654                 Usage:
00655                 
00656                 \code
00657                 
00658                 MultiIterator<3, int> outer = ...;  // this iterator
00659                 
00660                 MultiIterator<3, int>::iterator i = outer.iteratorForDimension(1);
00661                 MultiIterator<3, int>::iterator end = i + height;
00662                 for(; i != end; ++i)
00663                 {
00664                     // go down the current column starting at the location of 'outer'
00665                 }
00666                 \endcode            
00667             */
00668         iterator iteratorForDimension(unsigned int d) const
00669         {
00670             vigra_precondition(d <= level,
00671                 "MultiIterator<N>::iteratorForDimension(d): d < N required");
00672             return iterator(type::m_ptr, &type::m_stride [d], 0);
00673         }
00674         
00675       protected:
00676       
00677         difference_type 
00678         total_stride(typename multi_difference_type::const_iterator d) const
00679         {
00680             return d[level]*type::m_stride[level] + base_type::total_stride(d);
00681         }
00682     };
00683 };
00684 
00685 /********************************************************/
00686 /*                                                      */
00687 /*                      MultiIteratorBase <2>           */
00688 /*                                                      */
00689 /********************************************************/
00690 
00691 //
00692 template <>
00693 class MultiIteratorBase <2>
00694 {
00695   public:
00696     template <class T, class REFERENCE, class POINTER>
00697     class type : public MultiIterator <1, T, REFERENCE, POINTER>
00698     {
00699 
00700     public:
00701 
00702         enum { level = 1 };
00703         typedef MultiIterator <1, T, REFERENCE, POINTER> base_type;
00704         typedef T value_type;
00705         typedef REFERENCE reference;
00706         typedef const value_type &const_reference;
00707         typedef POINTER pointer;
00708         typedef const value_type *const_pointer;
00709         typedef ptrdiff_t difference_type;
00710         typedef MultiIterator <1, T, REFERENCE, POINTER> next_type;
00711         typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator;
00712         typedef TinyVector<difference_type, 2> multi_difference_type;
00713         typedef std::random_access_iterator_tag iterator_category;
00714 
00715         const difference_type *m_stride;
00716         const difference_type *m_shape;
00717             
00718         /* use default copy constructor and assignment operator */
00719             
00720         type ()
00721             : base_type (),
00722               m_stride (0), m_shape (0)
00723         {}
00724 
00725         type (pointer ptr,
00726               const difference_type *stride,
00727               const difference_type *shape)
00728             : base_type (ptr, stride, shape),
00729               m_stride (stride), m_shape (shape)
00730         {}
00731 
00732         void operator++ ()
00733         {
00734             type::m_ptr += m_stride [level];
00735         }
00736 
00737         void operator-- ()
00738         {
00739             type::m_ptr -= m_stride [level];
00740         }
00741 
00742         type operator++ (int)
00743         {
00744             type ret = *this;
00745             ++(*this);
00746             return ret;
00747         }
00748 
00749         type operator-- (int)
00750         {
00751             type ret = *this;
00752             --(*this);
00753             return ret;
00754         }
00755 
00756         type & operator+= (difference_type n)
00757         {
00758             type::m_ptr += n * m_stride [level];
00759             return *this;
00760         }
00761         
00762         type & operator+= (multi_difference_type const & d)
00763         {
00764             type::m_ptr += total_stride(d.begin());
00765             return *this;
00766         }
00767 
00768         type  &operator-= (difference_type n)
00769         {
00770             type::m_ptr -= n * m_stride [level];
00771             return *this;
00772         }
00773         
00774         type & operator-= (multi_difference_type const & d)
00775         {
00776             type::m_ptr -= total_stride(d.begin());
00777             return *this;
00778         }
00779         
00780         difference_type operator- (type const & d) const
00781         {
00782             return (type::m_ptr - d.m_ptr) / m_stride[level];
00783         }
00784 
00785         reference operator[] (difference_type n) const
00786         {
00787             return type::m_ptr [n*m_stride [level]];
00788         }
00789 
00790         reference operator[] (multi_difference_type const & d) const
00791         {
00792             return type::m_ptr [total_stride(d.begin())];
00793         }
00794 
00795         next_type begin () const
00796         {
00797             return *this;
00798         }
00799 
00800         next_type end () const
00801         {
00802             next_type ret = *this;
00803             ret += m_shape [level-1];
00804             return ret;
00805         }
00806         
00807         iterator iteratorForDimension(unsigned int d) const
00808         {
00809             vigra_precondition(d <= level,
00810                 "MultiIterator<N>::iteratorForDimension(d): d < N required");
00811             return iterator(type::m_ptr, &m_stride [d], 0);
00812         }
00813         
00814       protected:
00815       
00816         difference_type 
00817         total_stride(typename multi_difference_type::const_iterator d) const
00818         {
00819             return d[level]*m_stride[level] + base_type::total_stride(d);
00820         }
00821     };
00822 };
00823 
00824 /********************************************************/
00825 /*                                                      */
00826 /*                   MultiIteratorBase <1>              */
00827 /*                                                      */
00828 /********************************************************/
00829 
00830 //
00831 template <>
00832 class MultiIteratorBase <1>
00833 {
00834   public:
00835     template <class T, class REFERENCE, class POINTER>
00836     class type
00837     {
00838       public:
00839         enum { level = 0 };
00840         typedef T value_type;
00841         typedef REFERENCE reference;
00842         typedef const value_type &const_reference;
00843         typedef POINTER pointer;
00844         typedef const value_type *const_pointer;
00845         typedef ptrdiff_t difference_type;
00846         typedef void next_type;
00847         typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator;
00848         typedef TinyVector<difference_type, 1> multi_difference_type;
00849         typedef multi_dimensional_traverser_tag iterator_category;
00850 
00851         pointer m_ptr;
00852 
00853             
00854         /* use default copy constructor and assignment operator */
00855             
00856         type ()
00857             : m_ptr (0)
00858         {}
00859         
00860         type (pointer ptr,
00861               const difference_type *,
00862               const difference_type *)
00863             : m_ptr (ptr)
00864         {}
00865 
00866         void operator++ ()
00867         {
00868             ++m_ptr;
00869         }
00870 
00871         void operator-- ()
00872         {
00873             --m_ptr;
00874         }
00875 
00876         type operator++ (int)
00877         {
00878             type ret = *this;
00879             ++(*this);
00880             return ret;
00881         }
00882 
00883         type operator-- (int)
00884         {
00885             type ret = *this;
00886             --(*this);
00887             return ret;
00888         }
00889 
00890         type &operator+= (difference_type n)
00891         {
00892             m_ptr += n;
00893             return *this;
00894         }
00895 
00896         type & operator+= (multi_difference_type const & d)
00897         {
00898             m_ptr += d[level];
00899             return *this;
00900         }
00901 
00902         type &operator-= (difference_type n)
00903         {
00904             m_ptr -= n;
00905             return *this;
00906         }
00907 
00908         type & operator-= (multi_difference_type const & d)
00909         {
00910             m_ptr -= d[level];
00911             return *this;
00912         }
00913 
00914         reference operator* () const
00915         {
00916             return *m_ptr;
00917         }
00918 
00919         pointer get () const
00920         {
00921             return m_ptr;
00922         }
00923 
00924         pointer operator->() const
00925         {
00926             return &(operator*());
00927         }
00928 
00929         reference operator[] (difference_type n) const
00930         {
00931             return m_ptr [n];
00932         }
00933 
00934         reference operator[] (multi_difference_type const & d) const
00935         {
00936             return m_ptr [d[level]];
00937         }
00938         
00939         difference_type operator- (type const & d) const
00940         {
00941             return (m_ptr - d.m_ptr);
00942         }
00943 
00944         bool operator!= (const type &rhs) const
00945         {
00946             return m_ptr != rhs.m_ptr;
00947         }
00948 
00949         bool operator== (const type &rhs) const
00950         {
00951             return m_ptr == rhs.m_ptr;
00952         }
00953 
00954         bool operator< (const type &rhs) const
00955         {
00956             return m_ptr < rhs.m_ptr;
00957         }
00958 
00959         bool operator<= (const type &rhs) const
00960         {
00961             return m_ptr <= rhs.m_ptr;
00962         }
00963 
00964         iterator iteratorForDimension(unsigned int d) const
00965         {
00966             vigra_precondition(d == 0,
00967                 "MultiIterator<1>::iteratorForDimension(d): d == 0 required");
00968             const difference_type stride = 1;
00969             return iterator(m_ptr, &stride, 0);
00970         }
00971         
00972       protected:
00973       
00974         difference_type 
00975         total_stride(typename multi_difference_type::const_iterator d) const
00976         {
00977             return d[level];
00978         }
00979     };
00980 };
00981 
00982 
00983 /********************************************************/
00984 /*                                                      */
00985 /*                      MultiIterator                   */
00986 /*                                                      */
00987 /********************************************************/
00988 
00989 /** \brief A multi-dimensional hierarchical iterator to be used with 
00990            \ref vigra::MultiArrayView if it is not strided.
00991 
00992 This class wraps the MultiIteratorBase in a template of arity two.
00993 
00994 <b>\#include</b> "<a href="multi__iterator_8hxx-source.html">vigra/multi_iterator.hxx</a>"
00995 
00996 Namespace: vigra
00997 */
00998 template <unsigned int N, class T, class REFERENCE, class POINTER>
00999 class MultiIterator 
01000 : public MultiIteratorBase <N>::template type <T, REFERENCE, POINTER>
01001 {
01002 public:
01003 
01004         /** the type of the parent in the inheritance hierarchy.
01005          */
01006     typedef typename MultiIteratorBase <N>::template type <T, REFERENCE, POINTER> base_type;
01007 
01008         /** the iterator's value type
01009          */
01010     typedef T value_type;
01011 
01012         /** reference type (result of operator[])
01013          */
01014     typedef REFERENCE reference;
01015 
01016         /** const reference type (result of operator[] const)
01017          */
01018     typedef const value_type &const_reference;
01019 
01020         /** pointer type
01021          */
01022     typedef POINTER pointer;
01023 
01024         /** const pointer type
01025          */
01026     typedef const value_type *const_pointer;
01027 
01028         /** difference type (used for offsetting)
01029          */
01030     typedef ptrdiff_t difference_type;
01031 
01032         /** multi difference type 
01033             (used for offsetting along all axes simultaneously)
01034          */
01035     typedef TinyVector<difference_type, N> multi_difference_type;
01036     
01037         /** the MultiIterator for the next lower dimension.
01038          */
01039     typedef typename base_type::next_type next_type;
01040 
01041         /** the 1-dimensional iterator for this iterator hierarchy
01042             (result of iteratorForDimension()).
01043         */
01044     typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator;
01045 
01046         /** the iterator tag (image traverser)
01047         */
01048     typedef typename base_type::iterator_category iterator_category;
01049             
01050     /* use default copy constructor and assignment operator */
01051 
01052         /** default constructor.
01053         */
01054     MultiIterator ()
01055     {}
01056 
01057         /** construct from pointer, strides (offset of a sample to the
01058             next) for every dimension, and the shape.
01059         */
01060     MultiIterator (pointer ptr,
01061                    const difference_type *stride,
01062                    const difference_type *shape)
01063         : base_type (ptr, stride, shape)
01064     {}
01065 
01066         /** addition within current dimension
01067          */
01068     MultiIterator operator+ (difference_type n) const
01069     {
01070         MultiIterator ret = *this;
01071         ret += n;
01072         return ret;
01073     }
01074 
01075         /** addition along all dimensions
01076          */
01077     MultiIterator operator+ (multi_difference_type const & d) const
01078     {
01079         MultiIterator ret = *this;
01080         ret += d;
01081         return ret;
01082     }
01083 
01084         /** difference of two iterators in the current dimension.
01085             The result of this operation is undefined if the iterator
01086             doesn't point to element 0 in all dimensions below its current dimension.
01087         */
01088     difference_type operator- (MultiIterator const & d) const
01089     {
01090         return base_type::operator-(d);
01091     }
01092 
01093         /** subtraction within current dimension
01094          */
01095     MultiIterator operator- (difference_type n) const
01096     {
01097         MultiIterator ret = *this;
01098         ret -= n;
01099         return ret;
01100     }
01101 
01102         /** subtraction along all dimensions
01103          */
01104     MultiIterator operator- (multi_difference_type const & d) const
01105     {
01106         MultiIterator ret = *this;
01107         ret -= d;
01108         return ret;
01109     }
01110 
01111         /** Return the multi-iterator that operates on dimension K in order
01112             to manipulate this dimension directly. Usage:
01113                
01114             \code
01115                 
01116             MultiIterator<3, int> i3 = ...;
01117                 
01118             i3.template dim<2>()++;  // increment outer dimension
01119             i3.template dim<0>()++;  // increment inner dimension
01120             \endcode
01121             
01122             For convenience, the same functionality is also available
01123             as <tt>dim0()</tt>, <tt>dim1()</tt> etc. up to <tt>dim4()</tt>:
01124             
01125             \code
01126                 
01127             MultiIterator<3, int> i3 = ...;
01128                 
01129             i3.dim2()++;  // increment outer dimension
01130             i3.dim0()++;  // increment inner dimension
01131             \endcode            
01132         */
01133     template <unsigned int K>
01134     MultiIterator<K+1, T, REFERENCE, POINTER> &
01135     dim()
01136     {
01137         return *this;
01138     }
01139 
01140     MultiIterator<1, T, REFERENCE, POINTER> &
01141     dim0() { return *this; }
01142     MultiIterator<2, T, REFERENCE, POINTER> &
01143     dim1() { return *this; }
01144     MultiIterator<3, T, REFERENCE, POINTER> &
01145     dim2() { return *this; }
01146     MultiIterator<4, T, REFERENCE, POINTER> &
01147     dim3() { return *this; }
01148     MultiIterator<5, T, REFERENCE, POINTER> &
01149     dim4() { return *this; }
01150 };
01151 
01152 /********************************************************/
01153 /*                                                      */
01154 /*               StridedMultiIteratorBase               */
01155 /*                                                      */
01156 /********************************************************/
01157 
01158 /** \brief Encloses the base class for \ref vigra::StridedMultiIterator.
01159 
01160 This design is necessary for compilers that do not support partial
01161 specialization (otherwise, StridedMultiIterator could be specialized directly).
01162 
01163 <b>\#include</b> "<a href="multi__iterator_8hxx-source.html">vigra/multi_iterator.hxx</a>"
01164 
01165 Namespace: vigra
01166 */
01167 template <unsigned int N>
01168 class StridedMultiIteratorBase
01169 {
01170   public:
01171         /** \brief Base class for \ref vigra::StridedMultiIterator.
01172 
01173         This class implements the multi-iterator for strided arrays
01174         by means of the enclosed template 
01175         class <tt>type</tt>. This design is necessary for compilers that do not support partial
01176         specialization (otherwise, MultiIterator could be specialized directly).
01177 
01178         <b>\#include</b> "<a href="multi__iterator_8hxx-source.html">vigra/multi_iterator.hxx</a>"
01179 
01180         Namespace: vigra
01181         */
01182     template <class T, class REFERENCE, class POINTER>
01183     class type : public StridedMultiIterator <N-1, T, REFERENCE, POINTER>
01184     {
01185     public:
01186 
01187             /** the type of the parent in the inheritance hierarchy.
01188              */
01189         typedef StridedMultiIterator <N-1, T, REFERENCE, POINTER> base_type;
01190 
01191     public:
01192         
01193             /** the iterator's level in the dimension hierarchy
01194              */
01195         enum { level = N-1 };
01196 
01197             /** the iterator's value type
01198              */
01199         typedef T value_type;
01200 
01201             /** reference type (result of operator[])
01202              */
01203         typedef REFERENCE reference;
01204 
01205             /** const reference type (result of operator[] const)
01206              */
01207         typedef const value_type &const_reference;
01208 
01209             /** pointer type
01210              */
01211         typedef POINTER pointer;
01212 
01213             /** const pointer type
01214              */
01215         typedef const value_type *const_pointer;
01216 
01217             /** difference type (used for offsetting)
01218              */
01219         typedef ptrdiff_t difference_type;
01220 
01221             /** multi difference type 
01222                 (used for offsetting along all axes simultaneously)
01223              */
01224         typedef TinyVector<difference_type, N> multi_difference_type;
01225 
01226             /** the next type, this is a non-standard typedef denoting the
01227                 type of the multi-iterator with the next-lower dimension.
01228             */
01229         typedef StridedMultiIterator <level, T, REFERENCE, POINTER> next_type;
01230 
01231             /** the 1-dimensional iterator for this iterator hierarchy
01232                 (result of iteratorForDimension()).
01233             */
01234         typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator;
01235 
01236             /** the iterator tag (image traverser)
01237             */
01238         typedef multi_dimensional_traverser_tag iterator_category;
01239             
01240         /* use default copy constructor and assignment operator */
01241             
01242             /** default constructor.
01243             */
01244         type ()
01245         {}
01246 
01247             /** construct from pointer, strides (offset of a sample to the
01248                 next) for every dimension, and the shape.
01249             */
01250         type (pointer ptr,
01251               const difference_type *stride,
01252               const difference_type *shape)
01253             : base_type (ptr, stride, shape)
01254         {}
01255 
01256             /** prefix-increment the iterator in it's current dimension
01257              */
01258         void operator++ ()
01259         {
01260             type::m_ptr += type::m_stride [level];
01261         }
01262 
01263             /** prefix-decrement the iterator in it's current dimension
01264              */
01265         void operator-- ()
01266         {
01267             type::m_ptr -= type::m_stride [level];
01268         }
01269 
01270             /** postfix-increment the iterator in it's current dimension
01271              */
01272         type operator++ (int)
01273         {
01274             type ret = *this;
01275             ++(*this);
01276             return ret;
01277         }
01278 
01279             /** postfix-decrement the iterator in it's current dimension
01280              */
01281         type operator-- (int)
01282         {
01283             type ret = *this;
01284             --(*this);
01285             return ret;
01286         }
01287 
01288             /** increment the iterator in it's current dimension
01289                 by the given value.
01290             */
01291         type &operator+= (difference_type n)
01292         {
01293             type::m_ptr += n * type::m_stride [level];
01294             return *this;
01295         }
01296 
01297             /** increment the iterator in all dimensions
01298                 by the given offset.
01299             */
01300         type & operator+= (multi_difference_type const & d)
01301         {
01302             type::m_ptr += total_stride(d.begin());
01303             return *this;
01304         }
01305 
01306             /** decrement the iterator in it's current dimension
01307                 by the given value.
01308             */
01309         type &operator-= (difference_type n)
01310         {
01311             type::m_ptr -= n * type::m_stride [level];
01312             return *this;
01313         }
01314 
01315             /** decrement the iterator in all dimensions
01316                 by the given offset.
01317             */
01318         type & operator-= (multi_difference_type const & d)
01319         {
01320             type::m_ptr -= total_stride(d.begin());
01321             return *this;
01322         }
01323         
01324             /** difference of two iterators in the current dimension.
01325                 The result of this operation is undefined if the iterator
01326                 doesn't point to element 0 in all dimensions below its current dimension.
01327             */
01328         difference_type operator- (type const & d) const
01329         {
01330             return (type::m_ptr - d.m_ptr) / type::m_stride[level];
01331         }
01332 
01333         /* operators *, ->, ==, !=, < inherited */
01334 
01335             /** access the array element at the given offset
01336                 in the iterator's current dimension.
01337             */
01338         reference operator[] (difference_type n) const
01339         {
01340             return type::m_ptr [n* type::m_stride [level]];
01341         }
01342 
01343             /** access the array element at the given offset.
01344             */
01345         reference operator[] (multi_difference_type const & d) const
01346         {
01347             return type::m_ptr [total_stride(d.begin())];
01348         }
01349         
01350             /** Return the (N-1)-dimensional multi-iterator that points to 
01351                 the first (N-1)-dimensional subarray of the 
01352                 N-dimensional array this iterator is referring to.
01353                 The result is only valid if this iterator refers to location
01354                 0 in <em>all</em> dimensions below its current dimension N,
01355                 otherwise it is undefined. Usage:
01356                 
01357                 \code
01358                 
01359                 MultiIterator<2, int> outer = ...;  // this iterator
01360                 
01361                 MultiIterator<2, int>::next_type inner = outer.begin();
01362                 for(; inner != outer.end(); ++inner)
01363                 {
01364                     // manipulate current 1D subimage
01365                 }
01366                 \endcode
01367             */
01368         next_type begin () const
01369         {
01370             return *this;
01371         }
01372 
01373             /** Return the (N-1)-dimensional multi-iterator that points beyond 
01374                 the last (N-1)-dimensional subarray of the 
01375                 N-dimensional array this iterator is referring to.
01376                 The result is only valid if this iterator refers to location
01377                 0 in <em>all</em> dimensions below its current dimension N,
01378                 otherwise it is undefined. Usage:
01379             */
01380         next_type end () const
01381         {
01382             next_type ret = *this;
01383             ret += type::m_shape [level-1];
01384             return ret;
01385         }
01386         
01387             /** Get a 1-dimensional, STL-compatible iterator for the
01388                 given dimension, pointing to the current element of <TT>this</TT>.
01389                 Usage:
01390                 
01391                 \code
01392                 
01393                 StridedMultiIterator<3, int> outer = ...;  // this iterator
01394                 
01395                 StridedMultiIterator<3, int>::iterator i = outer.iteratorForDimension(1);
01396                 StridedMultiIterator<3, int>::iterator end = i + height;
01397                 for(; i != end; ++i)
01398                 {
01399                     // go down the current column starting at the location of 'outer'
01400                 }
01401                 \endcode            
01402             */
01403         iterator iteratorForDimension(unsigned int d) const
01404         {
01405             vigra_precondition(d <= N,
01406                 "StridedMultiIterator<N>::iteratorForDimension(d): d <= N required");
01407             return iterator(type::m_ptr, &type::m_stride [d], 0);
01408         }
01409 
01410       protected:
01411       
01412         difference_type 
01413         total_stride(typename multi_difference_type::const_iterator d) const
01414         {
01415             return d[level]*type::m_stride[level] + base_type::total_stride(d);
01416         }
01417     };
01418 };
01419 
01420 /********************************************************/
01421 /*                                                      */
01422 /*              StridedMultiIteratorBase <2>            */
01423 /*                                                      */
01424 /********************************************************/
01425 
01426 //
01427 template <>
01428 class StridedMultiIteratorBase <2>
01429 {
01430   public:
01431     template <class T, class REFERENCE, class POINTER>
01432     class type : public StridedMultiIterator <1, T, REFERENCE, POINTER>
01433     {
01434     public:
01435         enum { level = 1 };
01436         typedef StridedMultiIterator <1, T, REFERENCE, POINTER> base_type;
01437         typedef T value_type;
01438         typedef REFERENCE reference;
01439         typedef const value_type &const_reference;
01440         typedef POINTER pointer;
01441         typedef const value_type *const_pointer;
01442         typedef ptrdiff_t difference_type;
01443         typedef TinyVector<difference_type, 2>      multi_difference_type;
01444         typedef StridedMultiIterator <1, T, REFERENCE, POINTER> next_type;
01445         typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator;
01446         typedef multi_dimensional_traverser_tag iterator_category;
01447 
01448         const difference_type *m_stride;
01449         const difference_type *m_shape;
01450             
01451         /* use default copy constructor and assignment operator */
01452             
01453         type ()
01454             : base_type (),
01455               m_stride (0), m_shape (0)
01456         {}
01457 
01458         type (pointer ptr,
01459               const difference_type *stride,
01460               const difference_type *shape)
01461             : base_type (ptr, stride, shape),
01462               m_stride (stride), m_shape (shape)
01463         {}
01464 
01465         void operator++ ()
01466         {
01467             type::m_ptr += m_stride [level];
01468         }
01469 
01470         void operator-- ()
01471         {
01472             type::m_ptr -= m_stride [level];
01473         }
01474 
01475         type operator++ (int)
01476         {
01477             type ret = *this;
01478             ++(*this);
01479             return ret;
01480         }
01481 
01482         type operator-- (int)
01483         {
01484             type ret = *this;
01485             --(*this);
01486             return ret;
01487         }
01488 
01489         type &operator+= (int n)
01490         {
01491             type::m_ptr += n * m_stride [level];
01492             return *this;
01493         }
01494 
01495         type & operator+= (multi_difference_type const & d)
01496         {
01497             type::m_ptr += total_stride(d.begin());
01498             return *this;
01499         }
01500 
01501         type  &operator-= (difference_type n)
01502         {
01503             type::m_ptr -= n * m_stride [level];
01504             return *this;
01505         }
01506         
01507         type & operator-= (multi_difference_type const & d)
01508         {
01509             type::m_ptr -= total_stride(d.begin());
01510             return *this;
01511         }
01512 
01513         reference operator[] (difference_type n) const
01514         {
01515             return type::m_ptr [n*m_stride [level]];
01516         }
01517         
01518         difference_type operator- (type const & d) const
01519         {
01520             return (type::m_ptr - d.m_ptr) / m_stride[level];
01521         }
01522 
01523         reference operator[] (multi_difference_type const & d) const
01524         {
01525             return type::m_ptr [total_stride(d.begin())];
01526         }
01527 
01528         next_type begin () const
01529         {
01530             return *this;
01531         }
01532 
01533         next_type end () const
01534         {
01535             next_type ret = *this;
01536             ret += m_shape [level-1];
01537             return ret;
01538         }
01539         
01540         iterator iteratorForDimension(unsigned int d) const
01541         {
01542             vigra_precondition(d <= type::N,
01543                 "StridedMultiIterator<N>::iteratorForDimension(d): d <= N required");
01544             return iterator(type::m_ptr, &m_stride [d], 0);
01545         }
01546 
01547       protected:
01548       
01549         difference_type 
01550         total_stride(typename multi_difference_type::const_iterator d) const
01551         {
01552             return d[level]*m_stride[level] + base_type::total_stride(d);
01553         }
01554     };
01555 };
01556 
01557 /********************************************************/
01558 /*                                                      */
01559 /*               StridedMultiIteratorBase <1>           */
01560 /*                                                      */
01561 /********************************************************/
01562 
01563 //
01564 template <>
01565 class StridedMultiIteratorBase <1>
01566 {
01567   public:
01568     template <class T, class REFERENCE, class POINTER>
01569     class type
01570     {
01571     public:
01572 
01573         enum { level = 0 };
01574         typedef T value_type;
01575         typedef REFERENCE reference;
01576         typedef const value_type &const_reference;
01577         typedef POINTER pointer;
01578         typedef const value_type *const_pointer;
01579         typedef ptrdiff_t difference_type;
01580         typedef TinyVector<difference_type, 1> multi_difference_type;
01581         typedef void next_type;
01582         typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator;
01583         typedef std::random_access_iterator_tag iterator_category;
01584         
01585         pointer m_ptr;
01586         difference_type m_stride;
01587             
01588         /* use default copy constructor and assignment operator */
01589             
01590         type ()
01591             : m_ptr (0), m_stride (0)
01592         {}
01593 
01594         type (pointer ptr,
01595               const difference_type *stride,
01596               const difference_type *)
01597             : m_ptr (ptr), m_stride (stride [level])
01598         {}
01599 
01600         reference operator* () const
01601         {
01602             return *m_ptr;
01603         }
01604 
01605         pointer get () const
01606         {
01607             return m_ptr;
01608         }
01609 
01610         pointer operator-> () const
01611         {
01612             return &(operator*());
01613         }
01614 
01615         void operator++ ()
01616         {
01617             m_ptr += m_stride;
01618         }
01619 
01620         void operator-- ()
01621         {
01622             m_ptr -= m_stride;
01623         }
01624 
01625         type operator++ (int)
01626         {
01627             type ret = *this;
01628             ++(*this);
01629             return ret;
01630         }
01631 
01632         type operator-- (int)
01633         {
01634             type ret = *this;
01635             --(*this);
01636             return ret;
01637         }
01638 
01639         type &operator+= (difference_type n)
01640         {
01641             m_ptr += n * m_stride;
01642             return *this;
01643         }
01644 
01645         type & operator+= (multi_difference_type const & d)
01646         {
01647             m_ptr += d[level] * m_stride;
01648             return *this;
01649         }
01650 
01651         type &operator-= (difference_type n)
01652         {
01653             m_ptr -= n * m_stride;
01654             return *this;
01655         }
01656         
01657         type & operator-= (multi_difference_type const & d)
01658         {
01659             m_ptr -= d[level] * m_stride;
01660             return *this;
01661         }
01662         
01663         difference_type operator- (type const & d) const
01664         {
01665             return (m_ptr - d.m_ptr) / m_stride;
01666         }
01667 
01668         reference operator[] (difference_type n) const
01669         {
01670             return m_ptr [n*m_stride];
01671         }
01672 
01673         reference operator[] (multi_difference_type const & d) const
01674         {
01675             return m_ptr [d[level]*m_stride];
01676         }
01677 
01678         bool operator!= (const type &rhs) const
01679         {
01680             return m_ptr != rhs.m_ptr;
01681         }
01682 
01683         bool operator== (const type &rhs) const
01684         {
01685             return m_ptr == rhs.m_ptr;
01686         }
01687 
01688         bool operator< (const type &rhs) const
01689         {
01690             return m_ptr < rhs.m_ptr;
01691         }
01692 
01693         bool operator<= (const type &rhs) const
01694         {
01695             return m_ptr <= rhs.m_ptr;
01696         }
01697         
01698         iterator iteratorForDimension(unsigned int d) const
01699         {
01700             vigra_precondition(d == 0,
01701                 "StridedMultiIterator<1>::iteratorForDimension(d): d == 0 required");
01702             return *this;
01703         }
01704 
01705       protected:
01706       
01707         difference_type 
01708         total_stride(typename multi_difference_type::const_iterator d) const
01709         {
01710             return d[level]*m_stride;
01711         }
01712     };
01713 };
01714 
01715 /********************************************************/
01716 /*                                                      */
01717 /*                 StridedMultiIterator                 */
01718 /*                                                      */
01719 /********************************************************/
01720 
01721 /** \brief A multi-dimensional hierarchical iterator to be used with 
01722            \ref vigra::MultiArrayView is it is strided.
01723 
01724 This class wraps the StridedMultiIteratorBase in a template of arity two.
01725 
01726 <b>\#include</b> "<a href="multi__iterator_8hxx-source.html">vigra/multi_iterator.hxx</a>"
01727 
01728 Namespace: vigra
01729 */
01730 template <unsigned int N, class T, class REFERENCE, class POINTER>
01731 class StridedMultiIterator
01732     : public StridedMultiIteratorBase <N>::template type <T, REFERENCE, POINTER>
01733 {
01734 public:
01735 
01736         /** the type of the parent in the inheritance hierarchy.
01737          */
01738     typedef typename StridedMultiIteratorBase <
01739         N>::template type <T, REFERENCE, POINTER> base_type;
01740 
01741         /** the iterator's value type
01742          */
01743     typedef T value_type;
01744 
01745         /** reference type (result of operator[])
01746          */
01747     typedef REFERENCE reference;
01748 
01749         /** const reference type (result of operator[] const)
01750          */
01751     typedef const value_type &const_reference;
01752 
01753         /** pointer type
01754          */
01755     typedef POINTER pointer;
01756 
01757         /** const pointer type
01758          */
01759     typedef const value_type *const_pointer;
01760 
01761         /** difference type (used for offsetting)
01762          */
01763     typedef ptrdiff_t difference_type;
01764 
01765         /** multi difference type 
01766             (used for offsetting along all axes simultaneously)
01767          */
01768     typedef TinyVector<difference_type, N> multi_difference_type;
01769     
01770         /** the StridedMultiIterator for the next lower dimension.
01771          */
01772     typedef typename base_type::next_type next_type;
01773 
01774         /** the 1-dimensional iterator for this iterator hierarchy
01775             (result of iteratorForDimension()).
01776         */
01777     typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator;
01778 
01779         /** the iterator tag (image traverser)
01780         */
01781     typedef typename base_type::iterator_category iterator_category;
01782             
01783     /* use default copy constructor and assignment operator */
01784 
01785         /** default constructor.
01786         */
01787     StridedMultiIterator ()
01788     {}
01789 
01790         /** construct from pointer, strides (offset of a sample to the
01791             next) for every dimension, and the shape.
01792         */
01793     StridedMultiIterator (pointer ptr,
01794                           const difference_type *stride,
01795                           const difference_type *shape)
01796         : base_type (ptr, stride, shape)
01797     {}
01798 
01799         /** addition within current dimension
01800          */
01801     StridedMultiIterator operator+ (difference_type n) const
01802     {
01803         StridedMultiIterator ret = *this;
01804         ret += n;
01805         return ret;
01806     }
01807 
01808         /** addition along all dimensions
01809          */
01810     StridedMultiIterator operator+ (multi_difference_type const & d) const
01811     {
01812         StridedMultiIterator ret = *this;
01813         ret += d;
01814         return ret;
01815     }
01816 
01817         /** difference of two iterators in the current dimension.
01818             The result of this operation is undefined if the iterator
01819             doesn't point to element 0 in all dimensions below its current dimension.
01820         */
01821     difference_type operator- (StridedMultiIterator const & d) const
01822     {
01823         return base_type::operator-(d);
01824     }
01825     
01826         /** subtraction within current dimension
01827          */
01828     StridedMultiIterator operator- (difference_type n) const
01829     {
01830         StridedMultiIterator ret = *this;
01831         ret -= n;
01832         return ret;
01833     }
01834 
01835         /** subtraction along all dimensions
01836          */
01837     StridedMultiIterator operator- (multi_difference_type const & d) const
01838     {
01839         StridedMultiIterator ret = *this;
01840         ret -= d;
01841         return ret;
01842     }
01843 
01844         /** Return the multi-iterator that operates on dimension K in order
01845             to manipulate this dimension directly. Usage:
01846                 
01847             \code
01848             
01849             StridedMultiIterator<3, int> i3 = ...;
01850                 
01851             i3.template dim<2>()++;  // increment outer dimension
01852             i3.template dim<0>()++;  // increment inner dimension
01853             \endcode
01854             
01855             For convenience, the same functionality is also available
01856             as <tt>dim0()</tt>, <tt>dim1()</tt> etc. up to <tt>dim4()</tt>:
01857             
01858             \code
01859                 
01860             StridedMultiIterator<3, int> i3 = ...;
01861                 
01862             i3.dim2()++;  // increment outer dimension
01863             i3.dim0()++;  // increment inner dimension
01864             \endcode
01865         */
01866     template <unsigned int K>
01867     StridedMultiIterator<K+1, T, REFERENCE, POINTER> &
01868     dim()
01869     {
01870         return *this;
01871     }
01872 
01873     StridedMultiIterator<1, T, REFERENCE, POINTER> &
01874     dim0() { return *this; }
01875     StridedMultiIterator<2, T, REFERENCE, POINTER> &
01876     dim1() { return *this; }
01877     StridedMultiIterator<3, T, REFERENCE, POINTER> &
01878     dim2() { return *this; }
01879     StridedMultiIterator<4, T, REFERENCE, POINTER> &
01880     dim3() { return *this; }
01881     StridedMultiIterator<5, T, REFERENCE, POINTER> &
01882     dim4() { return *this; }
01883 };
01884 
01885 
01886 //@}
01887 
01888 } // namespace vigra
01889 
01890 #endif // VIGRA_MULTI_ITERATOR_HXX

© Ullrich Köthe (koethe@informatik.uni-hamburg.de)
Cognitive Systems Group, University of Hamburg, Germany

html generated using doxygen and Python
VIGRA 1.3.2 (27 Jan 2005)