Using Boost MPL to Linearize Indices

Question

I'm working on a larger project to generalize template instantations and am struggling to cleanly linearize some indices using Boost MPL with C++03. It's easiest to show my problem with an example (pardon my poor pseudo code).

I have N vectors of arbitrary length. Say N is 3, and say they look like:

v0 = {1,2,3};
v1 = {4,5,6,7,8};
v2 = {9,10};

For each of those, I have an index stored in a separate vector, like:

vectorOfIndices = {0,4,1};

I want to convert those to an overall index by doing:

0*sizeof(v1)*sizeof(v2) + 4*sizeof(v2) + 1;

The meta function/class I'm looking for help defining is a generalization of this which should take in two template parameters, both of type mpl::vector (containing mpl::int_ entries). The first vector will contain a sequence of indices (vectorOfIndices above, but of length N) and the second vector will contain a list of lengths (lengths of v0, v1, v2...vN above). The result type should be an mpl::int_ that contains the overall index.

user1777820 user1777820 · Accepted Answer · 2016-03-25T18:33:30

Took me a while (lots of reading...lots...meta programming has a steep learning curve it turns out), but I finally have a working solution. It's not the prettiest, but it's mine :p. If anyone has suggestions to improve it, or sees any issues, I would love to hear from you.

/* 
 * Computes and absolute index from a sequence of indices and vectors lengths.
 * Example:
 * 
 * Vectors:
 * v0 = {1, 2, 3}
 * v1 = {2}
 * v2 = {4, 5, 6, 7}
 * 
 * Inputs:
 * lengthsOfVectors = {3, 1, 4}
 * indexSequence = {2, 0, 3}
 * 
 * Result:
 * type = 2*(1*4) + 0*(4) + 3
 * 
 */
struct ComputeAbsoluteIndex
{
    template <typename lengthsOfVectors, typename indexSequence> struct apply
    {
        // Number of indices in sequence.
        typedef typename mpl::size<indexSequence>::type numberOfIndicesInSequence;

        // Forward sequence to iterate over number of indices in sequence.
        typedef typename mpl::range_c<int, 0, numberOfIndicesInSequence::value>::type indexSequenceRange;

        // Forward iterator that points to start of lengths of vectors. 
        // Add one since offset contributions are computed by multiplying the current index, from the index sequence, by the lengths subsequent vectors.
        typedef typename mpl::next<typename mpl::begin<lengthsOfVectors>::type >::type lengthsOfVectorsStart;

        // Forward iterator that points to the end of lengths of vectors.
        typedef typename mpl::end<lengthsOfVectors>::type lengthsOfVectorsEnd;

        typedef typename mpl::lambda // Helper metafunction class to multiply lengths.
        <
            mpl::fold // Loop over lengths to multiply.
            <
                mpl::_1, // Sequence of lengths to multiply.
                mpl::int_<1>, // Initial multiplier of one.
                typename mpl::lambda // Wrap multiply in lambda such that place holders (_1 and _2) are replaced properly.
                <
                    mpl::multiplies<mpl::_1, mpl::_2 >
                >::type
            >
        >::type multiplySequence;

        typedef typename mpl::fold // Loop over each index in index sequence.
        <
            indexSequenceRange, // Forward Sequence to iterate over number of indices in index sequence.
            mpl::int_<0>, // Initial total index of zero.
            mpl::plus // Add offsets.
            <
                mpl::_1, // Initial state to start (zero), then result of previous addition for each following iteration.
                mpl::multiplies // Multiply current index from index sequence by remaining lengths.
                <
                    mpl::at<indexSequence, mpl::_2 >, // Get current index from index sequence.
                    multiplySequence::apply // Invoke helper metafunction class to multiply lengths.
                    <
                        mpl::iterator_range // Create Forward Sequence that iterates over lengths to multiply.
                        <
                            mpl::advance<lengthsOfVectorsStart, mpl::_2>, // Advance iterator start to multiply proper lengths.
                            lengthsOfVectorsEnd
                        > 
                    >
                >
            >
        >::type type;
    };
};

Using Boost MPL to Linearize Indices

1 Answers