Convert an mpl sequence of sequences into a trie

Question

The problem looks simple enough, basically I have a sequence of sequences, something like:

typedef mpl::vector<
  mpl::vector<mpl::_1, mpl::_2>,
  mpl::vector<mpl::_1, mpl::_2, mpl::_3>,
  mpl::vector<mpl::_2, mpl::_1>,
  mpl::vector<mpl::_2, mpl::_2>,
  mpl::vector<mpl::_2, mpl::_2, mpl::_3>
> seq;

What I would like to do is to transform this to a trie, the end result being something like:

mpl::map<
  mpl::pair<mpl::_1, 
    mpl::map<
      mpl::pair<mpl::_2,
        mpl::map<
          mpl::pair<TERMINAL, T>,
          mpl::pair<mpl::_3,
            mpl::map<
              mpl::pair<TERMINAL, T>
            >
          >
        >
      >
    >
  >
  mpl::pair<mpl::_2, 
    mpl::map<
      mpl::pair<mpl::_1,
        mpl::map<
          mpl::pair<TERMINAL, T>
        >
      >,
      mpl::pair<mpl::_2,
        mpl::map<
          mpl::pair<TERMINAL, T>,
          mpl::pair<mpl::_3,
            mpl::map<
              mpl::pair<TERMINAL, T>
            >
          >
        >
      >
    >
  >
>

So, the question is, is this possible (I'm thinking it's not)? If it is possible, which dark spells have I missed?

EDIT: In case the above transformation from sequence of sequences to a trie is not clear, let me see if I can state it in plain English (often more difficult.) Basically each sequence within the main sequence is composed of some types (_1, _2 etc.) The transformed version is trie where common prefixes are collapsed. May be the attached picture helps..

EDIT2: Thanks to @Yakk, hopefully now the question is clearer...

Answer 1

There you go:

struct Terminal;

template < typename Trie, typename First, typename Last,
           typename Enable = void >
struct insertInTrie_impl
{
    typedef typename
        mpl::deref<First>::type key;

    typedef typename 
        mpl::at<
            Trie,
            key
        >::type subTrieOrVoid; // would be easier if "at" supported Default

    typedef typename
        mpl::if_<
            boost::is_same< subTrieOrVoid, mpl::void_ >,
            mpl::map<>,
            subTrieOrVoid
        >::type subTrie;

    typedef typename
        mpl::insert<
            Trie,
            mpl::pair<
                key, typename
                insertInTrie_impl<
                    subTrie, typename
                    mpl::next<First>::type,
                    Last
                >::type
            >
        >::type type;
};

template < typename Trie, typename First, typename Last >
struct insertInTrie_impl< Trie, First, Last, typename 
    boost::enable_if< boost::is_same<First, Last> >::type >
    : mpl::insert<
        Trie,
        mpl::pair< Terminal, Terminal >
        // I'm not sure what you want in your terminal node
    >
{};

template < typename Trie, typename Seq >
struct insertInTrie
    : insertInTrie_impl< 
        Trie, typename 
        mpl::begin<Seq>::type, typename 
        mpl::end<Seq>::type
    >
{};


template < typename SeqOfSeq >
struct constructTrie
    : mpl::fold< 
        SeqOfSeq,
        mpl::map<>,
        insertInTrie< mpl::_1, mpl::_2 >
    >
{};

insertInTrie_impl is a recursive metafunction that inserts a sequence into an existing trie, using iterators. insertInTrie accepts a sequence an calls insertInTrie_impl. constructTrie applies insertInTrie to all sequences in the given sequence, starting with an empty trie.

In pseudo-code, this reads as follow:

Trie insertInTrie_impl(trie, first, last)
{
    if (first == last)
    {
        trie.insert(Terminal, Terminal);
        return trie;
    }

    key = *first;

    subTrie = trie[key];
    if (subTrie = void) // key not found
    {
        subTrie = emptyTrie;
    }

    trie.insert(key, insertInTrie_impl(subTrie, ++first, last))

    return trie;
}

Trie insertInTrie(trie, seq)
{
    return insertInTrie_impl(trie, seq.begin(), seq.end();
}

Trie constructTrie(seqOfSeq)
{
    return fold(seqOfSeq, emptyTrie, insertInTrie);
}

Finally, a sample use:

int main()
{
    typedef mpl::vector<
        mpl::vector<mpl::_1, mpl::_2>,
        mpl::vector<mpl::_1, mpl::_2, mpl::_3>,
        mpl::vector<mpl::_2, mpl::_1>,
        mpl::vector<mpl::_2, mpl::_2>,
        mpl::vector<mpl::_2, mpl::_2, mpl::_3>
    > seqOfSeq;

    typedef constructTrie< seqOfSeq >::type bigTrie;

    BOOST_MPL_ASSERT(( 
        mpl::has_key<
            mpl::at< 
                mpl::at< 
                    bigTrie, 
                    mpl::_1
                >::type, 
                mpl::_2
            >::type, 
            Terminal
        > ));
    BOOST_MPL_ASSERT(( 
        mpl::has_key<
            mpl::at< 
                mpl::at< 
                    mpl::at< 
                        bigTrie, 
                        mpl::_1
                    >::type,
                    mpl::_2
                >::type, 
                mpl::_3
            >::type, 
            Terminal
        > ));
    BOOST_MPL_ASSERT(( 
        mpl::has_key<
            mpl::at< 
                mpl::at< 
                    bigTrie, 
                    mpl::_2
                >::type,
                mpl::_2
            >::type, 
            Terminal
        > ));
}

Answer 2

So the answer is "yes, this is possible".

Write add_to_trie. It takes a possibly empty trie and an element (a sequence of types) and returns a trie with that element added.

Test add_to_trie on an empty trie and some sequence, and on a few other hand crafted cases. Common prefix: ("A")("A","B"), no common prefix: ("A","A")("B","A"), shorter no common prefix: ("A","B")("B"), two copies of the same thing: ("A")("A"), etc

Write accumulate. It takes a value and a binary functor and a sequence. If applies value = functor(value, s) on each element s of a sequence, then returns value.

Test accumulate by adding up 1 through 5 and printing the result.

Compose the two.

This may blow your template recursion stack, and each step is non trivial to write right, but it will work.

It may help to first write the above operating on strings of characters. Then make the functions functional. Then translate to operating on types.

I'd bet even money that boost has an appropriate accumulate already written.