Iterator—Notes on implementation

Transposer and Indexer are implemented in such a way that a partial template specialization is provided for each possible RANK (up to 11), and the corresponding code is automatically generated by the Boost.Preprocessor library. This can be seen in utils/include/details/IndexerImplementations(Specializations).h. To actually see what code is generated by them, they need to be preprocessed. Issue the following command from the root directory of the distribution:

g++ -P -E -Iutils/include/ utils/include/details/IndexerImplementations.h | tail -n286

To store and manipulate the heterogenous collection of slicing indeces like 0,a,2,a,4,5,a,a,8,a,10 above, the boost::fusion::vector class of the Boost.Fusion library is used.

Iterator is implemented in terms of the above two helper classes. Each Iterator involves a transpose() at its construction, and—if RANK is larger than mpl::size<V>::value—an index() is invoked at the point of its dereferencing, when the actual slicing occurs.

Iterator is a forward iterator, implemented with the help of boost::forward_iterator_helper from Boost.Operator. For this to work, we need to define only 3 operations:

1. Comparison for equality
2. Prefix increment
3. Dereferencing

A special implementation is needed when the size of the compile-time vector V equals RANK because in this case actually no slicing takes place, only transposition. For this, as at several other places in the framework, we apply conditional inheritance: Iterator inherits from either of two classes (IteratorBase or IteratorBaseSpecial), the decision being made at compile time with the help of mpl::if_c.

The iteration over dummy indeces is implemented with the help of MultiIndexIterator.

A metaprogramming example

In the following we analyse a metaprogramming example typical for the framework: how the compile-time vector 0,3,2,6,4,5,1,9,8,7,10 for the self-transposition above is prepared.

This is done by the following snippet in utils/include/impl/BlitzArraySliceIterator.tcc:

namespace blitzplusplus {

namespace basi {

namespace namehider {

using namespace boost::mpl;
namespace mpl=boost::mpl;
using namespace tmptools;

template<int RANK, typename V>
struct Algorithm 
  : fold<Ordinals<RANK>,
	 pair<vector_c<int>,typename boost::mpl::begin<V>::type>,
	 pair<push_back<first<mpl::_1>,
			if_<numerical_contains<V,mpl::_2>,
			    deref<second<mpl::_1> >,
			    mpl::_2
			    >
			>,
	      if_<numerical_contains<V,mpl::_2>,
		  next<second<mpl::_1> >,
		  second<mpl::_1>
		  >
	      >
	 >
{};

} // namehider


template<int RANK, typename V>
struct TransposerMeta : boost::mpl::first<typename namehider::Algorithm<RANK,V>::type>
{};

} // basi

} // blitzplusplus

Line 13:

We are using the fold metaalgorithm from Boost.MPL. It iterates over the sequence of ordinals between 0 and RANK-1.

Line 14:

The initial state for the fold algorithm is an empty compile-time vector of integers and the iterator pointing to the first element of the compile-time vector V. These two are “zipped” into a compile-time pair. At the end, the first element of this pair will hold the result.

Lines 15-25

express the forward operation of the fold algorithm in the form of a compile-time lambda expression. After each step, the new state will again be a pair composed of

1. (Lines 15-20:) the vector is augmented either by the current element in V pointed to by the iterator (Line 17), or the current ordinal (Line 18), depending on whether V numerical_contains this ordinal.
2. (Lines 21-24:) the iterator is advanced (Line 22) if the same numerical containment criterion is met, otherwise it is left untouched for the same element to be considered again (Line 23).

(Note that in TMP, “calling” numerical_contains<V,mpl::_2> twice is no waste because the second time no further template instantiations are needed, the compiler will use the ones already instantiated the first time.)

Lines 32-34: the first element of the resulting pair of the above algorithm is picked. As it is easy to verify, TransposerMeta<11,tmptools::Vector<3,6,1,9,7> >::type will be an mpl::vector_c<int,0,3,2,6,4,5,1,9,8,7,10>.