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

Multi-dimensional Array Iterators VIGRA

General iterators for arrays of arbitrary dimension.

The Multidimensional Iterator concept allows navigation on arrays of arbitrary dimension. It provides two modes of iteration: direct traversal, 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<K>() 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.

General Requirements for MultiIterator

Local Types Meaning
MultiIterator::value_typethe underlying arrays's pixel type
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.
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.
MultiIterator::iterator_category the iterator tag (vigra::multi_dimensional_traverser_tag)
Operation Result Semantics
MultiIterator k;default constructor
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

Local Types Meaning
MultiIterator::multi_difference_type the iterator's multi-dimensional difference type (TinyVector<MultiArrayIndex, N>)
Operation Result Semantics
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<K>()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):
        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
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 vigra::ImageIterator where differencing is allowed).

Requirements for Hierarchical Traversal

Local Types Meaning
MultiIterator::difference_type the iterator's difference type (MultiArrayIndex)
MultiIterator::next_typetype of the next iterator (referring to the next lower dimension) in the hierarchy
Operation Result Semantics
++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 pointing 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:
    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
            }
        }
    }
i.end()next_type create the hierarchical iterator pointing 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.
i, j are of type MultiIterator
d is of type MultiIterator::difference_type

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.9.0 (Tue Nov 6 2012)