Konvertieren eine mpl Folge von Sequenzen in einen Trie

Question

Das Problem einfach genug sieht, im Grunde habe ich eine Folge von Sequenzen, so etwas wie:

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; 

Was ich zu tun ist, möchte dies zu einer Trie zu verwandeln, Das Endergebnis ist etwas wie:

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 ist die Frage, ist das möglich (ich denke, es ist nicht)? Wenn es möglich ist, welche dunklen Zauber habe ich verpasst?

EDIT: Für den Fall, dass die obige Transformation von Sequenz von Sequenzen zu einem Trie nicht klar ist, lassen Sie mich sehen, wenn ich es in einfachem Englisch (oft schwieriger.) Grundsätzlich jede Sequenz innerhalb der Hauptreihe besteht aus einigen Typen (_1, _2 usw.) Die transformierte Version ist Trie, wo gemeinsame Präfixe zusammengebrochen sind. Mai wird das beigefügte Bild hilft ..

EDIT2: Dank @Yakk, hoffentlich jetzt die Frage klarer ...

Answer 1

Dort gehen Sie:

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 eine rekursive metafunction ist, die eine Sequenz in eine bestehende Trie einfügt, mit Iteratoren. insertInTrie akzeptiert eine Sequenz und ruft insertInTrie_impl. constructTrie gilt insertInTrie für alle Sequenzen in der angegebenen Sequenz, beginnend mit einem leeren Trie.

In Pseudo-Code, der dies liest, wie folgt:

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); 
} 

schließlich eine Probe Verwendung:

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 ist die Antwort "Ja, das ist möglich".

Schreiben add_to_trie. Es nimmt einen möglicherweise leeren Trie und ein Element (eine Folge von Typen) und gibt einen Trie mit dem hinzugefügten Element zurück.

Testen Sie add_to_trie auf einem leeren Trie und einer Sequenz und auf einigen anderen handgefertigten Fällen. Gemeinsames Präfix: ("A") ("A", "B"), kein gemeinsames Präfix: ("A", "A") ("B", "A"), kürzer kein gemeinsames Präfix: ("A") , "B") ("B"), zwei Kopien desselben Objekts: ("A") ("A"), usw.

Schreiben akkumulieren. Es braucht einen Wert und einen binären Funktor und eine Sequenz. Wenn für jedes Element s einer Sequenz value = functor (value, s) gilt, wird der Wert zurückgegeben.

Test akkumulieren, indem 1 bis 5 addiert und das Ergebnis gedruckt wird.

Komponieren Sie die beiden.

Dies kann Ihre Vorlage Rekursionsstapel blasen, und jeder Schritt ist nicht trivial, um richtig zu schreiben, aber es wird funktionieren.

Es kann helfen, zuerst die oben genannten Zeichenfolgen zu schreiben. Dann machen Sie die Funktionen funktional. Übersetzen Sie dann in die Arbeit mit Typen.

Ich würde sogar wetten, dass boost eine entsprechende accumulate bereits geschrieben hat.