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

Multi-dimensional Array Iterators

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 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<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.

Gerneral Requirements for MultiIterator

Local Types

Meaning

MultiIterator::value_type

the 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 == j

bool

equality (iterators point to the same element)

i != j

bool

inequality (iterators don't point to the same element)

*i

MultiIterator::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 += diff

MultiIterator &

add offset to current position

i -= diff

MultiIterator &

subtract offset from current position

i + diff

MultiIterator

create traverser by adding offset

i - diff

MultiIterator

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_type

type of the next iterator (referring to the next lower dimension) in the hierarchy

Operation

Result

Semantics

++i

MultiIterator &

pre-increment iterator in its current dimension

i++

MultiIterator

post-increment iterator in its current dimension

--i

MultiIterator &

pre-decrement iterator in its current dimension

i--

MultiIterator

post-decrement iterator in its current dimension

i += d

MultiIterator &

add d in current dimension

i -= d

MultiIterator &

subtract d in from dimension

i + d

MultiIterator

create new iterator by adding d in current dimension

i - d

MultiIterator

create new iterator by subtracting d in current dimension

i - j

difference_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 < j

bool

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:

    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 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.

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.6.0 (5 Nov 2009)