/************************************************************************/ /* */ /* Copyright 2003 by Gunnar Kedenburg */ /* Cognitive Systems Group, University of Hamburg, Germany */ /* */ /* This file is part of the VIGRA computer vision library. */ /* ( Version 1.3.0, Sep 10 2004 ) */ /* The VIGRA Website is */ /* http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/ */ /* Please direct questions, bug reports, and contributions to */ /* koethe@informatik.uni-hamburg.de or */ /* vigra@kogs1.informatik.uni-hamburg.de */ /* */ /* Permission is hereby granted, free of charge, to any person */ /* obtaining a copy of this software and associated documentation */ /* files (the "Software"), to deal in the Software without */ /* restriction, including without limitation the rights to use, */ /* copy, modify, merge, publish, distribute, sublicense, and/or */ /* sell copies of the Software, and to permit persons to whom the */ /* Software is furnished to do so, subject to the following */ /* conditions: */ /* */ /* The above copyright notice and this permission notice shall be */ /* included in all copies or substantial portions of the */ /* Software. */ /* */ /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */ /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */ /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */ /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */ /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */ /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */ /* OTHER DEALINGS IN THE SOFTWARE. */ /* */ /************************************************************************/ #ifndef VIGRA_MULTI_ITERATOR_HXX #define VIGRA_MULTI_ITERATOR_HXX #include #include "vigra/tinyvector.hxx" #include "vigra/iteratortags.hxx" namespace vigra { template class MultiIterator; template class StridedMultiIterator; /** \page MultiIteratorPage Multi-dimensional Array Iterators General iterators for arrays of arbitrary dimension.

- \ref vigra::MultiIterator
Iterator for unstrided \ref vigra::MultiArrayView
- \ref vigra::MultiIteratorBase::type
Inner class implementing most of the functionality of \ref vigra::MultiIterator
- \ref vigra::StridedMultiIterator
Iterator for strided \ref vigra::MultiArrayView
- \ref vigra::StridedMultiIteratorBase::type
Inner class implementing most of the functionality of \ref vigra::StridedMultiIterator

The Multidimensional Iterator concept allows navigation on arrays of arbitrary dimension. It provides two modes of iteration: direct traveral, and hierarchical traversal. In general, hierarchical traversal will be faster, while only direct traversal allows for true random access in all dimensions. Via the dim() function, operations applying to a particular dimension can be used in the direct traversal mode. In contrast, direct traversal functions should not be used in the hierarchical mode because the hierarchical functions are only well-defined if the iterator points to element 0 in all dimensions below its current dimension. The current dimension of a MultiIterator<N, ..> is N-1.

Gerneral Requirements for MultiIterator

\endhtmlonly \endhtmlonly
\htmlonly \endhtmlonly Local Types \htmlonly \endhtmlonly Meaning \htmlonly
\htmlonly \endhtmlonly MultiIterator::value_typethe underlying arrays's pixel type
\htmlonly \endhtmlonly MultiIterator::reference the iterator's reference type (return type of *iter). Will be value_type & for a mutable iterator, and convertible to value_type const & for a const iterator.
\htmlonly \endhtmlonly MultiIterator::pointer the iterator's pointer type (return type of iter.operator->()). Will be value_type * for a mutable iterator, and convertible to value_type const * for a const iterator.
\htmlonly \endhtmlonly MultiIterator::iterator_category the iterator tag (vigra::multi_dimensional_traverser_tag)
\htmlonly \endhtmlonly Operation \htmlonly \endhtmlonly Result \htmlonly \endhtmlonly Semantics \htmlonly
\htmlonly \endhtmlonly MultiIterator k;default constructor
\htmlonly \endhtmlonly MultiIterator k(i);copy constructor
k = i MultiIterator &assignment
i == jbool equality (iterators point to the same element)
i != jbool inequality (iterators don't point to the same element)
*iMultiIterator::reference access the current element
i->member()depends on operation call member function of underlying pixel type via operator-> of iterator

Requirements for Direct Traversal

\endhtmlonly \endhtmlonly
\htmlonly \endhtmlonly Local Types \htmlonly \endhtmlonly Meaning \htmlonly
\htmlonly \endhtmlonly MultiIterator::multi_difference_type the iterator's multi-dimensional difference type (TinyVector<ptrdiff_t, N>)
\htmlonly \endhtmlonly Operation \htmlonly \endhtmlonly Result \htmlonly \endhtmlonly Semantics \htmlonly
i += diffMultiIterator & add offset to current position
i -= diffMultiIterator & subtract offset from current position
i + diffMultiIterator create traverser by adding offset
i - diffMultiIterator create traverser by subtracting offset
i[diff]MultiIterator::reference access element at offset diff
i.dim()MultiIterator<K+1, T, ...> Access the traverser with the current dimension set to K. Typically used to call navigation functions referring to a particular dimension.
Example (assuming i, j are 3-dimensional):
\code i.dim<0>()++; // increment dimension 0 i.dim<1>()++; // increment dimension 1 i.dim<2>()++; // increment dimension 2 j += MultiIterator::multi_difference_type(1,1,1); // same effect \endcode
\htmlonly \endhtmlonly i, j are of type MultiIterator
diff is of type MultiIterator::multi_difference_type
K is an integer compile-time constant

Note that it is impossible to support an operator- between two iterators which returns a MultiIterator::multi_difference_type because it is impossible to decide to which dimension a difference applies. Consider for example, a 2-dimensional iterator i, and let j = i + multi_difference_type(width, 0), k = i + multi_difference_type(0,1), where width is the array's total width. In general, j and k point to the same memory location, so that the two cases cannot easily be distinguished (it is possible, but iterator performance will suffer significantly, as is experienced with \ref vigra::ImageIterator where differencing is allowed).

Requirements for Hierarchical Traversal

\endhtmlonly \endhtmlonly
\htmlonly \endhtmlonly Local Types \htmlonly \endhtmlonly Meaning \htmlonly
\htmlonly \endhtmlonly MultiIterator::difference_type the iterator's difference type (ptrdiff_t)
\htmlonly \endhtmlonly MultiIterator::next_typetype of the next iterator (referring to the next lower dimension) in the hierarchy
\htmlonly \endhtmlonly Operation \htmlonly \endhtmlonly Result \htmlonly \endhtmlonly Semantics \htmlonly
++iMultiIterator & pre-increment iterator in its current dimension
i++MultiIterator post-increment iterator in its current dimension
--iMultiIterator & pre-decrement iterator in its current dimension
i--MultiIterator post-decrement iterator in its current dimension
i += dMultiIterator & add d in current dimension
i -= dMultiIterator & subtract d in from dimension
i + dMultiIterator create new iterator by adding d in current dimension
i - dMultiIterator create new iterator by subtracting d in current dimension
i - jdifference_type difference of i and j in the current dimension
Note: The result of this operation is undefined if the iterator doesn't point to element 0 in all dimensions below its current dimension.
i < jbool i - j < 0
Note: The result of this operation is undefined if the iterator doesn't point to element 0 in all dimensions below its current dimension.
i[d]MultiIterator::reference access element by adding offset d in current dimension
i.begin()next_type create the hierarchical iterator poiting to the first element in the next lower dimension.
Note: The result of this operation is undefined if the iterator doesn't point to element 0 in all dimensions below its current dimension.
Usage:
\code MultiIterator<3, int> i3 = ..., end3 = ...; for(; i3 != end3; ++i3) { MultiIterator<3, int>::next_type i2 = i3.begin(), end2 = i3.end(); for(; i2 != end2; ++i2) { MultiIterator<3, int>::next_type::next_type i1 = i2.begin(), end1 = i2.end(); for(; i1 != end1; ++i1) { ... // do something with the current element } } } \endcode
i.end()next_type create the hierarchical iterator poiting to the past-the-end location in the next lower dimension.
Note: The result of this operation is undefined if the iterator doesn't point to element 0 in all dimensions below its current dimension.
\htmlonly \endhtmlonly i, j are of type MultiIterator
d is of type MultiIterator::difference_type

*/ /** \addtogroup MultiIteratorGroup Multi-dimensional Array Iterators \brief General iterators for arrays of arbitrary dimension. */ //@{ /********************************************************/ /* */ /* MultiIteratorBase */ /* */ /********************************************************/ /** \brief Enclosing class for \ref vigra::MultiIterator base classes. This design is necessary for compilers that do not support partial specialization (otherwise, MultiIterator could be specialized directly). \#include "vigra/multi_iterator.hxx" Namespace: vigra */ template class MultiIteratorBase { public: /** \brief Base class for \ref vigra::MultiIterator. This class implements the multi-iterator by means of the enclosed template class type. This design is necessary for compilers that do not support partial specialization (otherwise, MultiIterator could be specialized directly). \#include "vigra/multi_iterator.hxx" Namespace: vigra */ template class type : public MultiIterator { public: /** the type of the parent in the inheritance hierarchy. */ typedef MultiIterator base_type; public: /** the iterator's level in the dimension hierarchy */ enum { level = N-1 }; /** the iterator's value type */ typedef T value_type; /** reference type (result of operator[] and operator*()) */ typedef REFERENCE reference; /** pointer type (result of operator->()) */ typedef POINTER pointer; /** difference type (used for offsetting along one axis) */ typedef ptrdiff_t difference_type; /** multi difference type (used for offsetting along all axes simultaneously) */ typedef TinyVector multi_difference_type; /** the next type, this is a non-standard typedef denoting the type of the multi-iterator with the next-lower dimension. */ typedef MultiIterator next_type; /** the 1-dimensional iterator for this iterator hierarchy (result of iteratorForDimension()). */ typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator; /** the iterator tag (image traverser) */ typedef multi_dimensional_traverser_tag iterator_category; /* use default copy constructor and assignment operator */ /** default constructor. */ type () {} /** construct from pointer, strides (offset of a sample to the next) for every dimension, and the shape. */ type (pointer ptr, const difference_type *stride, const difference_type *shape) : base_type (ptr, stride, shape) {} /** prefix-increment the iterator in it's current dimension */ void operator++ () { type::m_ptr += type::m_stride [level]; } /** prefix-decrement the iterator in it's current dimension */ void operator-- () { type::m_ptr -= type::m_stride [level]; } /** postfix-increment the iterator in it's current dimension */ type operator++ (int) { type ret = *this; ++(*this); return ret; } /** postfix-decrement the iterator in it's current dimension */ type operator-- (int) { type ret = *this; --(*this); return ret; } /** increment the iterator in it's current dimension by the given value. */ type & operator+= (difference_type n) { type::m_ptr += n * type::m_stride [level]; return *this; } /** increment the iterator in all dimensions by the given offset. */ type & operator+= (multi_difference_type const & d) { type::m_ptr += total_stride(d.begin()); return *this; } /** decrement the iterator in it's current dimension by the given value. */ type & operator-= (difference_type n) { type::m_ptr -= n * type::m_stride [level]; return *this; } /** decrement the iterator in all dimensions by the given offset. */ type & operator-= (multi_difference_type const & d) { type::m_ptr -= total_stride(d.begin()); return *this; } /** difference of two iterators in the current dimension. The result of this operation is undefined if the iterator doesn't point to element 0 in all dimensions below its current dimension. */ difference_type operator- (type const & d) const { return (type::m_ptr - d.m_ptr) / type::m_stride[level]; } /* operators *, ->, ==, !=, < inherited */ /** access the array element at the given offset in the current dimension. */ reference operator[] (difference_type n) const { return type::m_ptr [n* type::m_stride [level]]; } /** access the array element at the given offset. */ reference operator[] (multi_difference_type const & d) const { return type::m_ptr [total_stride(d.begin())]; } /** Return the (N-1)-dimensional multi-iterator that points to the first (N-1)-dimensional subarray of the N-dimensional array this iterator is referring to. The result is only valid if this iterator refers to location 0 in all dimensions below its current dimension N, otherwise it is undefined. Usage: \code MultiIterator<2, int> outer = ...; // this iterator MultiIterator<2, int>::next_type inner = outer.begin(); for(; inner != outer.end(); ++inner) { // manipulate current 1D subimage } \endcode */ next_type begin () const { return *this; } /** Return the (N-1)-dimensional multi-iterator that points beyond the last (N-1)-dimensional subarray of the N-dimensional array this iterator is referring to. The result is only valid if this iterator refers to location 0 in all dimensions below its current dimension N, otherwise it is undefined. */ next_type end () const { next_type ret = *this; ret += type::m_shape [level-1]; return ret; } /** Get a 1-dimensional, STL-compatible iterator for the given dimension, pointing to the current element of this. Usage: \code MultiIterator<3, int> outer = ...; // this iterator MultiIterator<3, int>::iterator i = outer.iteratorForDimension(1); MultiIterator<3, int>::iterator end = i + height; for(; i != end; ++i) { // go down the current column starting at the location of 'outer' } \endcode */ iterator iteratorForDimension(unsigned int d) const { vigra_precondition(d <= level, "MultiIterator::iteratorForDimension(d): d < N required"); return iterator(type::m_ptr, &type::m_stride [d], 0); } protected: difference_type total_stride(typename multi_difference_type::const_iterator d) const { return d[level]*type::m_stride[level] + base_type::total_stride(d); } }; }; /********************************************************/ /* */ /* MultiIteratorBase <2> */ /* */ /********************************************************/ // template <> class MultiIteratorBase <2> { public: template class type : public MultiIterator <1, T, REFERENCE, POINTER> { public: enum { level = 1 }; typedef MultiIterator <1, T, REFERENCE, POINTER> base_type; typedef T value_type; typedef REFERENCE reference; typedef const value_type &const_reference; typedef POINTER pointer; typedef const value_type *const_pointer; typedef ptrdiff_t difference_type; typedef MultiIterator <1, T, REFERENCE, POINTER> next_type; typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator; typedef TinyVector multi_difference_type; typedef std::random_access_iterator_tag iterator_category; const difference_type *m_stride; const difference_type *m_shape; /* use default copy constructor and assignment operator */ type () : base_type (), m_stride (0), m_shape (0) {} type (pointer ptr, const difference_type *stride, const difference_type *shape) : base_type (ptr, stride, shape), m_stride (stride), m_shape (shape) {} void operator++ () { type::m_ptr += m_stride [level]; } void operator-- () { type::m_ptr -= m_stride [level]; } type operator++ (int) { type ret = *this; ++(*this); return ret; } type operator-- (int) { type ret = *this; --(*this); return ret; } type & operator+= (difference_type n) { type::m_ptr += n * m_stride [level]; return *this; } type & operator+= (multi_difference_type const & d) { type::m_ptr += total_stride(d.begin()); return *this; } type &operator-= (difference_type n) { type::m_ptr -= n * m_stride [level]; return *this; } type & operator-= (multi_difference_type const & d) { type::m_ptr -= total_stride(d.begin()); return *this; } difference_type operator- (type const & d) const { return (type::m_ptr - d.m_ptr) / m_stride[level]; } reference operator[] (difference_type n) const { return type::m_ptr [n*m_stride [level]]; } reference operator[] (multi_difference_type const & d) const { return type::m_ptr [total_stride(d.begin())]; } next_type begin () const { return *this; } next_type end () const { next_type ret = *this; ret += m_shape [level-1]; return ret; } iterator iteratorForDimension(unsigned int d) const { vigra_precondition(d <= level, "MultiIterator::iteratorForDimension(d): d < N required"); return iterator(type::m_ptr, &m_stride [d], 0); } protected: difference_type total_stride(typename multi_difference_type::const_iterator d) const { return d[level]*m_stride[level] + base_type::total_stride(d); } }; }; /********************************************************/ /* */ /* MultiIteratorBase <1> */ /* */ /********************************************************/ // template <> class MultiIteratorBase <1> { public: template class type { public: enum { level = 0 }; typedef T value_type; typedef REFERENCE reference; typedef const value_type &const_reference; typedef POINTER pointer; typedef const value_type *const_pointer; typedef ptrdiff_t difference_type; typedef void next_type; typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator; typedef TinyVector multi_difference_type; typedef multi_dimensional_traverser_tag iterator_category; pointer m_ptr; /* use default copy constructor and assignment operator */ type () : m_ptr (0) {} type (pointer ptr, const difference_type *, const difference_type *) : m_ptr (ptr) {} void operator++ () { ++m_ptr; } void operator-- () { --m_ptr; } type operator++ (int) { type ret = *this; ++(*this); return ret; } type operator-- (int) { type ret = *this; --(*this); return ret; } type &operator+= (difference_type n) { m_ptr += n; return *this; } type & operator+= (multi_difference_type const & d) { m_ptr += d[level]; return *this; } type &operator-= (difference_type n) { m_ptr -= n; return *this; } type & operator-= (multi_difference_type const & d) { m_ptr -= d[level]; return *this; } reference operator* () const { return *m_ptr; } pointer get () const { return m_ptr; } pointer operator->() const { return &(operator*()); } reference operator[] (difference_type n) const { return m_ptr [n]; } reference operator[] (multi_difference_type const & d) const { return m_ptr [d[level]]; } difference_type operator- (type const & d) const { return (m_ptr - d.m_ptr); } bool operator!= (const type &rhs) const { return m_ptr != rhs.m_ptr; } bool operator== (const type &rhs) const { return m_ptr == rhs.m_ptr; } bool operator< (const type &rhs) const { return m_ptr < rhs.m_ptr; } bool operator<= (const type &rhs) const { return m_ptr <= rhs.m_ptr; } iterator iteratorForDimension(unsigned int d) const { vigra_precondition(d == 0, "MultiIterator<1>::iteratorForDimension(d): d == 0 required"); const difference_type stride = 1; return iterator(m_ptr, &stride, 0); } protected: difference_type total_stride(typename multi_difference_type::const_iterator d) const { return d[level]; } }; }; /********************************************************/ /* */ /* MultiIterator */ /* */ /********************************************************/ /** \brief A multi-dimensional hierarchical iterator to be used with \ref vigra::MultiArrayView if it is not strided. This class wraps the MultiIteratorBase in a template of arity two. \#include "vigra/multi_iterator.hxx" Namespace: vigra */ template class MultiIterator : public MultiIteratorBase ::template type { public: /** the type of the parent in the inheritance hierarchy. */ typedef typename MultiIteratorBase ::template type base_type; /** the iterator's value type */ typedef T value_type; /** reference type (result of operator[]) */ typedef REFERENCE reference; /** const reference type (result of operator[] const) */ typedef const value_type &const_reference; /** pointer type */ typedef POINTER pointer; /** const pointer type */ typedef const value_type *const_pointer; /** difference type (used for offsetting) */ typedef ptrdiff_t difference_type; /** multi difference type (used for offsetting along all axes simultaneously) */ typedef TinyVector multi_difference_type; /** the MultiIterator for the next lower dimension. */ typedef typename base_type::next_type next_type; /** the 1-dimensional iterator for this iterator hierarchy (result of iteratorForDimension()). */ typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator; /** the iterator tag (image traverser) */ typedef typename base_type::iterator_category iterator_category; /* use default copy constructor and assignment operator */ /** default constructor. */ MultiIterator () {} /** construct from pointer, strides (offset of a sample to the next) for every dimension, and the shape. */ MultiIterator (pointer ptr, const difference_type *stride, const difference_type *shape) : base_type (ptr, stride, shape) {} /** addition within current dimension */ MultiIterator operator+ (difference_type n) const { MultiIterator ret = *this; ret += n; return ret; } /** addition along all dimensions */ MultiIterator operator+ (multi_difference_type const & d) const { MultiIterator ret = *this; ret += d; return ret; } /** difference of two iterators in the current dimension. The result of this operation is undefined if the iterator doesn't point to element 0 in all dimensions below its current dimension. */ difference_type operator- (MultiIterator const & d) const { return base_type::operator-(d); } /** subtraction within current dimension */ MultiIterator operator- (difference_type n) const { MultiIterator ret = *this; ret -= n; return ret; } /** subtraction along all dimensions */ MultiIterator operator- (multi_difference_type const & d) const { MultiIterator ret = *this; ret -= d; return ret; } /** Return the multi-iterator that operates on dimension K in order to manipulate this dimension directly. Usage: \code MultiIterator<3, int> i3 = ...; i3.template dim<2>()++; // increment outer dimension i3.template dim<0>()++; // increment inner dimension \endcode For convenience, the same functionality is also available as dim0(), dim1() etc. up to dim4(): \code MultiIterator<3, int> i3 = ...; i3.dim2()++; // increment outer dimension i3.dim0()++; // increment inner dimension \endcode */ template MultiIterator & dim() { return *this; } MultiIterator<1, T, REFERENCE, POINTER> & dim0() { return *this; } MultiIterator<2, T, REFERENCE, POINTER> & dim1() { return *this; } MultiIterator<3, T, REFERENCE, POINTER> & dim2() { return *this; } MultiIterator<4, T, REFERENCE, POINTER> & dim3() { return *this; } MultiIterator<5, T, REFERENCE, POINTER> & dim4() { return *this; } }; /********************************************************/ /* */ /* StridedMultiIteratorBase */ /* */ /********************************************************/ /** \brief Encloses the base class for \ref vigra::StridedMultiIterator. This design is necessary for compilers that do not support partial specialization (otherwise, StridedMultiIterator could be specialized directly). \#include "vigra/multi_iterator.hxx" Namespace: vigra */ template class StridedMultiIteratorBase { public: /** \brief Base class for \ref vigra::StridedMultiIterator. This class implements the multi-iterator for strided arrays by means of the enclosed template class type. This design is necessary for compilers that do not support partial specialization (otherwise, MultiIterator could be specialized directly). \#include "vigra/multi_iterator.hxx" Namespace: vigra */ template class type : public StridedMultiIterator { public: /** the type of the parent in the inheritance hierarchy. */ typedef StridedMultiIterator base_type; public: /** the iterator's level in the dimension hierarchy */ enum { level = N-1 }; /** the iterator's value type */ typedef T value_type; /** reference type (result of operator[]) */ typedef REFERENCE reference; /** const reference type (result of operator[] const) */ typedef const value_type &const_reference; /** pointer type */ typedef POINTER pointer; /** const pointer type */ typedef const value_type *const_pointer; /** difference type (used for offsetting) */ typedef ptrdiff_t difference_type; /** multi difference type (used for offsetting along all axes simultaneously) */ typedef TinyVector multi_difference_type; /** the next type, this is a non-standard typedef denoting the type of the multi-iterator with the next-lower dimension. */ typedef StridedMultiIterator next_type; /** the 1-dimensional iterator for this iterator hierarchy (result of iteratorForDimension()). */ typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator; /** the iterator tag (image traverser) */ typedef multi_dimensional_traverser_tag iterator_category; /* use default copy constructor and assignment operator */ /** default constructor. */ type () {} /** construct from pointer, strides (offset of a sample to the next) for every dimension, and the shape. */ type (pointer ptr, const difference_type *stride, const difference_type *shape) : base_type (ptr, stride, shape) {} /** prefix-increment the iterator in it's current dimension */ void operator++ () { type::m_ptr += type::m_stride [level]; } /** prefix-decrement the iterator in it's current dimension */ void operator-- () { type::m_ptr -= type::m_stride [level]; } /** postfix-increment the iterator in it's current dimension */ type operator++ (int) { type ret = *this; ++(*this); return ret; } /** postfix-decrement the iterator in it's current dimension */ type operator-- (int) { type ret = *this; --(*this); return ret; } /** increment the iterator in it's current dimension by the given value. */ type &operator+= (difference_type n) { type::m_ptr += n * type::m_stride [level]; return *this; } /** increment the iterator in all dimensions by the given offset. */ type & operator+= (multi_difference_type const & d) { type::m_ptr += total_stride(d.begin()); return *this; } /** decrement the iterator in it's current dimension by the given value. */ type &operator-= (difference_type n) { type::m_ptr -= n * type::m_stride [level]; return *this; } /** decrement the iterator in all dimensions by the given offset. */ type & operator-= (multi_difference_type const & d) { type::m_ptr -= total_stride(d.begin()); return *this; } /** difference of two iterators in the current dimension. The result of this operation is undefined if the iterator doesn't point to element 0 in all dimensions below its current dimension. */ difference_type operator- (type const & d) const { return (type::m_ptr - d.m_ptr) / type::m_stride[level]; } /* operators *, ->, ==, !=, < inherited */ /** access the array element at the given offset in the iterator's current dimension. */ reference operator[] (difference_type n) const { return type::m_ptr [n* type::m_stride [level]]; } /** access the array element at the given offset. */ reference operator[] (multi_difference_type const & d) const { return type::m_ptr [total_stride(d.begin())]; } /** Return the (N-1)-dimensional multi-iterator that points to the first (N-1)-dimensional subarray of the N-dimensional array this iterator is referring to. The result is only valid if this iterator refers to location 0 in all dimensions below its current dimension N, otherwise it is undefined. Usage: \code MultiIterator<2, int> outer = ...; // this iterator MultiIterator<2, int>::next_type inner = outer.begin(); for(; inner != outer.end(); ++inner) { // manipulate current 1D subimage } \endcode */ next_type begin () const { return *this; } /** Return the (N-1)-dimensional multi-iterator that points beyond the last (N-1)-dimensional subarray of the N-dimensional array this iterator is referring to. The result is only valid if this iterator refers to location 0 in all dimensions below its current dimension N, otherwise it is undefined. Usage: */ next_type end () const { next_type ret = *this; ret += type::m_shape [level-1]; return ret; } /** Get a 1-dimensional, STL-compatible iterator for the given dimension, pointing to the current element of this. Usage: \code StridedMultiIterator<3, int> outer = ...; // this iterator StridedMultiIterator<3, int>::iterator i = outer.iteratorForDimension(1); StridedMultiIterator<3, int>::iterator end = i + height; for(; i != end; ++i) { // go down the current column starting at the location of 'outer' } \endcode */ iterator iteratorForDimension(unsigned int d) const { vigra_precondition(d <= N, "StridedMultiIterator::iteratorForDimension(d): d <= N required"); return iterator(type::m_ptr, &type::m_stride [d], 0); } protected: difference_type total_stride(typename multi_difference_type::const_iterator d) const { return d[level]*type::m_stride[level] + base_type::total_stride(d); } }; }; /********************************************************/ /* */ /* StridedMultiIteratorBase <2> */ /* */ /********************************************************/ // template <> class StridedMultiIteratorBase <2> { public: template class type : public StridedMultiIterator <1, T, REFERENCE, POINTER> { public: enum { level = 1 }; typedef StridedMultiIterator <1, T, REFERENCE, POINTER> base_type; typedef T value_type; typedef REFERENCE reference; typedef const value_type &const_reference; typedef POINTER pointer; typedef const value_type *const_pointer; typedef ptrdiff_t difference_type; typedef TinyVector multi_difference_type; typedef StridedMultiIterator <1, T, REFERENCE, POINTER> next_type; typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator; typedef multi_dimensional_traverser_tag iterator_category; const difference_type *m_stride; const difference_type *m_shape; /* use default copy constructor and assignment operator */ type () : base_type (), m_stride (0), m_shape (0) {} type (pointer ptr, const difference_type *stride, const difference_type *shape) : base_type (ptr, stride, shape), m_stride (stride), m_shape (shape) {} void operator++ () { type::m_ptr += m_stride [level]; } void operator-- () { type::m_ptr -= m_stride [level]; } type operator++ (int) { type ret = *this; ++(*this); return ret; } type operator-- (int) { type ret = *this; --(*this); return ret; } type &operator+= (int n) { type::m_ptr += n * m_stride [level]; return *this; } type & operator+= (multi_difference_type const & d) { type::m_ptr += total_stride(d.begin()); return *this; } type &operator-= (difference_type n) { type::m_ptr -= n * m_stride [level]; return *this; } type & operator-= (multi_difference_type const & d) { type::m_ptr -= total_stride(d.begin()); return *this; } reference operator[] (difference_type n) const { return type::m_ptr [n*m_stride [level]]; } difference_type operator- (type const & d) const { return (type::m_ptr - d.m_ptr) / m_stride[level]; } reference operator[] (multi_difference_type const & d) const { return type::m_ptr [total_stride(d.begin())]; } next_type begin () const { return *this; } next_type end () const { next_type ret = *this; ret += m_shape [level-1]; return ret; } iterator iteratorForDimension(unsigned int d) const { vigra_precondition(d <= type::N, "StridedMultiIterator::iteratorForDimension(d): d <= N required"); return iterator(type::m_ptr, &m_stride [d], 0); } protected: difference_type total_stride(typename multi_difference_type::const_iterator d) const { return d[level]*m_stride[level] + base_type::total_stride(d); } }; }; /********************************************************/ /* */ /* StridedMultiIteratorBase <1> */ /* */ /********************************************************/ // template <> class StridedMultiIteratorBase <1> { public: template class type { public: enum { level = 0 }; typedef T value_type; typedef REFERENCE reference; typedef const value_type &const_reference; typedef POINTER pointer; typedef const value_type *const_pointer; typedef ptrdiff_t difference_type; typedef TinyVector multi_difference_type; typedef void next_type; typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator; typedef std::random_access_iterator_tag iterator_category; pointer m_ptr; difference_type m_stride; /* use default copy constructor and assignment operator */ type () : m_ptr (0), m_stride (0) {} type (pointer ptr, const difference_type *stride, const difference_type *) : m_ptr (ptr), m_stride (stride [level]) {} reference operator* () const { return *m_ptr; } pointer get () const { return m_ptr; } pointer operator-> () const { return &(operator*()); } void operator++ () { m_ptr += m_stride; } void operator-- () { m_ptr -= m_stride; } type operator++ (int) { type ret = *this; ++(*this); return ret; } type operator-- (int) { type ret = *this; --(*this); return ret; } type &operator+= (difference_type n) { m_ptr += n * m_stride; return *this; } type & operator+= (multi_difference_type const & d) { m_ptr += d[level] * m_stride; return *this; } type &operator-= (difference_type n) { m_ptr -= n * m_stride; return *this; } type & operator-= (multi_difference_type const & d) { m_ptr -= d[level] * m_stride; return *this; } difference_type operator- (type const & d) const { return (m_ptr - d.m_ptr) / m_stride; } reference operator[] (difference_type n) const { return m_ptr [n*m_stride]; } reference operator[] (multi_difference_type const & d) const { return m_ptr [d[level]*m_stride]; } bool operator!= (const type &rhs) const { return m_ptr != rhs.m_ptr; } bool operator== (const type &rhs) const { return m_ptr == rhs.m_ptr; } bool operator< (const type &rhs) const { return m_ptr < rhs.m_ptr; } bool operator<= (const type &rhs) const { return m_ptr <= rhs.m_ptr; } iterator iteratorForDimension(unsigned int d) const { vigra_precondition(d == 0, "StridedMultiIterator<1>::iteratorForDimension(d): d == 0 required"); return *this; } protected: difference_type total_stride(typename multi_difference_type::const_iterator d) const { return d[level]*m_stride; } }; }; /********************************************************/ /* */ /* StridedMultiIterator */ /* */ /********************************************************/ /** \brief A multi-dimensional hierarchical iterator to be used with \ref vigra::MultiArrayView if it is strided. This class wraps the StridedMultiIteratorBase in a template of arity two. \#include "vigra/multi_iterator.hxx" Namespace: vigra */ template class StridedMultiIterator : public StridedMultiIteratorBase ::template type { public: /** the type of the parent in the inheritance hierarchy. */ typedef typename StridedMultiIteratorBase < N>::template type base_type; /** the iterator's value type */ typedef T value_type; /** reference type (result of operator[]) */ typedef REFERENCE reference; /** const reference type (result of operator[] const) */ typedef const value_type &const_reference; /** pointer type */ typedef POINTER pointer; /** const pointer type */ typedef const value_type *const_pointer; /** difference type (used for offsetting) */ typedef ptrdiff_t difference_type; /** multi difference type (used for offsetting along all axes simultaneously) */ typedef TinyVector multi_difference_type; /** the StridedMultiIterator for the next lower dimension. */ typedef typename base_type::next_type next_type; /** the 1-dimensional iterator for this iterator hierarchy (result of iteratorForDimension()). */ typedef StridedMultiIterator <1, T, REFERENCE, POINTER> iterator; /** the iterator tag (image traverser) */ typedef typename base_type::iterator_category iterator_category; /* use default copy constructor and assignment operator */ /** default constructor. */ StridedMultiIterator () {} /** construct from pointer, strides (offset of a sample to the next) for every dimension, and the shape. */ StridedMultiIterator (pointer ptr, const difference_type *stride, const difference_type *shape) : base_type (ptr, stride, shape) {} /** addition within current dimension */ StridedMultiIterator operator+ (difference_type n) const { StridedMultiIterator ret = *this; ret += n; return ret; } /** addition along all dimensions */ StridedMultiIterator operator+ (multi_difference_type const & d) const { StridedMultiIterator ret = *this; ret += d; return ret; } /** difference of two iterators in the current dimension. The result of this operation is undefined if the iterator doesn't point to element 0 in all dimensions below its current dimension. */ difference_type operator- (StridedMultiIterator const & d) const { return base_type::operator-(d); } /** subtraction within current dimension */ StridedMultiIterator operator- (difference_type n) const { StridedMultiIterator ret = *this; ret -= n; return ret; } /** subtraction along all dimensions */ StridedMultiIterator operator- (multi_difference_type const & d) const { StridedMultiIterator ret = *this; ret -= d; return ret; } /** Return the multi-iterator that operates on dimension K in order to manipulate this dimension directly. Usage: \code StridedMultiIterator<3, int> i3 = ...; i3.template dim<2>()++; // increment outer dimension i3.template dim<0>()++; // increment inner dimension \endcode For convenience, the same functionality is also available as dim0(), dim1() etc. up to dim4(): \code StridedMultiIterator<3, int> i3 = ...; i3.dim2()++; // increment outer dimension i3.dim0()++; // increment inner dimension \endcode */ template StridedMultiIterator & dim() { return *this; } StridedMultiIterator<1, T, REFERENCE, POINTER> & dim0() { return *this; } StridedMultiIterator<2, T, REFERENCE, POINTER> & dim1() { return *this; } StridedMultiIterator<3, T, REFERENCE, POINTER> & dim2() { return *this; } StridedMultiIterator<4, T, REFERENCE, POINTER> & dim3() { return *this; } StridedMultiIterator<5, T, REFERENCE, POINTER> & dim4() { return *this; } }; //@} } // namespace vigra #endif // VIGRA_MULTI_ITERATOR_HXX