एक Trie

Question

समस्या काफी सरल लग रहा है में दृश्यों का एक एमपीएल अनुक्रम कन्वर्ट, मूल रूप से मैं दृश्यों के एक दृश्य की तरह कुछ है:

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; 

मैं करना चाहते हैं क्या एक Trie को यह बदलने के लिए है, अंतिम परिणाम कुछ ऐसा है:

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

तो सवाल यह है कि यह संभव है (मुझे लगता है कि यह नहीं है)? यदि यह संभव है, तो मुझे किस अंधेरे मंत्र याद आए हैं?

संपादित करें: यदि अनुक्रमों के अनुक्रम से उपरोक्त परिवर्तन एक त्रिभुज में स्पष्ट नहीं है, तो मुझे देखने दो कि क्या मैं इसे सादे अंग्रेजी (अक्सर अधिक कठिन) में बता सकता हूं। मूल रूप से मुख्य अनुक्रम में प्रत्येक अनुक्रम कुछ से बना है प्रकार (_1, _2 इत्यादि) परिवर्तित संस्करण त्रिभुज है जहां आम उपसर्ग ध्वस्त हो जाते हैं। हो सकता है संलग्न चित्र में मदद करता है ..

EDIT2: धन्यवाद @Yakk करने के लिए, उम्मीद है कि अब सवाल स्पष्ट है ...

Answer 1

ये लीजिए:

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 एक पुनरावर्ती metafunction कि एक मौजूदा trie में एक दृश्य सम्मिलित करता है, iterators का उपयोग कर रहा है। insertInTrie एक अनुक्रम को insertInTrie_impl पर कॉल करता है। constructTrie खाली ट्रे के साथ शुरू होने वाले अनुक्रम में सभी अनुक्रमों के लिए insertInTrie लागू होता है।

छद्म कोड में, यह इस प्रकार लिखा है:

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

अंत में, एक नमूना उपयोग:

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

तो उत्तर "हां, यह संभव है"।

add_to_trie लिखें। यह संभवतः खाली त्रिभुज और एक तत्व (प्रकारों का अनुक्रम) लेता है और उस तत्व के साथ एक त्रिभुज देता है।

एक खाली ट्राई और कुछ अनुक्रम पर, और कुछ अन्य हाथों पर तैयार किए गए मामलों पर add_to_trie परीक्षण करें। सामान्य उपसर्ग: ("ए") ("ए", "बी"), कोई सामान्य उपसर्ग नहीं: ("ए", "ए") ("बी", "ए"), कम कोई सामान्य उपसर्ग नहीं: ("ए" , "बी") ("बी"), एक ही चीज़ की दो प्रतियां: ("ए") ("ए"), आदि

जमा लिखें। यह एक मूल्य और एक बाइनरी मजेदार और एक अनुक्रम लेता है। यदि अनुक्रम के प्रत्येक तत्व पर मान = मज़ेदार (मान, एस) लागू होता है, तो मान देता है।

परीक्षण 1 से 5 जोड़कर और परिणाम प्रिंट करके जमा हो जाता है।

दोनों लिखें।

यह आपके टेम्पलेट रिकर्सन स्टैक को उड़ा सकता है, और प्रत्येक चरण सही लिखने के लिए तुच्छ नहीं है, लेकिन यह काम करेगा।

इससे पहले वर्णों के तारों पर उपर्युक्त ऑपरेटिंग लिखने में मदद मिल सकती है। फिर कार्यों को कार्यात्मक बनाओ। फिर प्रकारों पर परिचालन करने के लिए अनुवाद करें।

मैं भी पैसे खर्च करूंगा कि boost में पहले से लिखा गया उचित accumulate है।