Konwersja sekwencję mpl sekwencji w trie

Question

Problem wygląda dość proste, w zasadzie mam kolejność sekwencji, coś takiego:

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; 

Co chciałbym zrobić, to przekształcić to do trie, końcowy wynik to coś w rodzaju:

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

Pytanie brzmi, czy to możliwe (myślę, że tak nie jest)? Jeśli to możliwe, które ciemne zaklęcia przeoczyłem?

EDYCJA: W przypadku, gdy powyższa transformacja z sekwencji sekwencji do trie nie jest jasna, zobaczmy, czy mogę ją podać w prostym języku angielskim (często trudniejszym). Zasadniczo każda sekwencja w głównej sekwencji składa się z niektórych typy (_1, _2 itd.) Wersja przekształcona to trie, w której wspólne przedrostki są zwinięte. Może być załączony rysunek pomaga ..

EDIT2: Dzięki @Yakk, mam nadzieję, że teraz jest pytanie jaśniejsze ...

Answer 1

Nie idziesz:

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 to rekurencyjny metafunkcji że wstawienie sekwencji do istniejącej trie za pomocą iteratorów. insertInTrie akceptuje sekwencję i wywołania insertInTrie_impl. constructTrie dotyczy insertInTrie dla wszystkich sekwencji w podanej kolejności, zaczynając od pustego trie.

W pseudo-kodu, to brzmi jak następuje:

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

Wreszcie zastosowanie próbkowania:

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

Więc odpowiedź brzmi "tak, to jest możliwe".

Napisz add_to_trie. Zajmuje prawdopodobnie pusty trie i element (sekwencję typów) i zwraca trie z dodanym elementem.

Testuj add_to_trie na pustym trie i niektórych sekwencjach, a także na kilku innych ręcznie wykonanych skrzynkach. Wspólny prefiks: ("A") ("A", "B"), bez wspólnego przedrostka: ("A", "A") ("B", "A"), krótszy brak wspólnego przedrostka: ("A" , "B") ("B"), dwie kopie tego samego: ("A") ("A"), itp.

Napisz kumulować. Wymaga wartości i binarnego funktora oraz sekwencji. Jeśli stosuje wartość = funktor (wartość, s) na każdym elemencie s sekwencji, a następnie zwraca wartość.

Test kumulować, dodając od 1 do 5 i drukować wynik.

Skomponuj dwa.

Może to spowodować rozdarcie stosu rekursji szablonów, a każdy krok nie jest trywialny, aby pisać poprawnie, ale zadziała.

Może pomóc najpierw napisać powyższą operację na łańcuchach znaków. Następnie wykonaj funkcje funkcjonalne. Następnie przetłumacz do działania na typy.

Założę się nawet o pieniądze, które boost ma już napisane odpowiednie accumulate.