trie1.cpp

#include <iostream>
#include <boost/metaparse.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/insert.hpp>
#include <boost/mpl/char.hpp>
#include <boost/mpl/accumulate.hpp>
#include <boost/mpl/has_key.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/pop_front.hpp>

template <typename...P>
struct trie {
    using type = boost::mpl::map<P...>;
};


template <char K, typename V>
using trie_val = boost::mpl::pair<
    boost::mpl::char_<K>, V>;


template <typename T, typename P>
struct insert {
    using type = typename boost::mpl::insert<
        typename T::type,
        P>::type;
};



template <class S>
struct peek_front : std::false_type {};

template <char C, char... Cs>
struct peek_front<boost::metaparse::v1::string<C, Cs...>>
{
    static constexpr char value = C;
};

template <typename T, typename S>
struct trie_build;

template <typename T>
struct trie_build<T, std::false_type> {
    using type = T;
};

template <typename T, typename S>
struct trie_build {
    using type = boost::mpl::if_<
        boost::mpl::has_key<
            typename T::type,
            boost::mpl::char_<
                peek_front<S>::value
            >
        >
        , trie_build<
            boost::mpl::at<
                typename T::type,
                boost::mpl::char_<
                    peek_front<S>::value
                >
            >
            , boost::mpl::pop_front<S>
        >
        , insert<
            T,
            trie_val<
                peek_front<S>::value,
                trie<>
            >
        >
    >;
};


int main(int, char**)
{
    using root = trie<>;
    using s1 = BOOST_METAPARSE_STRING("casa");
    using s2 = BOOST_METAPARSE_STRING("carro");
    using T1 = trie_build<root, s1>::type;
    using T2 = trie_build<T1, s2>::type;

}