Проблема выглядит достаточно просто, в основном у меня есть последовательность последовательностей, что-то вроде:
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;
То, что я хотел бы сделать, это преобразовать это в три, конечный результат что-то вроде:
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, надеюсь, теперь вопрос стал яснее …
Там вы идете:
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
является рекурсивной мета-функцией, которая вставляет последовательность в существующее дерево с использованием итераторов. 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
> ));
}
Так что ответ «да, это возможно».
Напишите add_to_trie. Он принимает, возможно, пустое дерево и элемент (последовательность типов) и возвращает дерево с этим элементом.
Протестируйте add_to_trie на пустом дереве и некоторой последовательности, а также на нескольких других случаях, созданных вручную. Общий префикс: («A») («A», «B»), без общего префикса: («A», «A») («B», «A»), более короткий без общего префикса: («A» , «B») («B»), две копии одного и того же: («A») («A») и т. Д.
Пиши накапливай. Он принимает значение, двоичный функтор и последовательность. Если применяется значение = функтор (значение, с) к каждому элементу последовательности, то возвращается значение.
Тест накапливается путем суммирования от 1 до 5 и печати результата.
Составьте два.
Это может взорвать ваш стек рекурсии шаблона, и каждый шаг нетривиален, чтобы написать правильно, но это будет работать.
Это может помочь сначала написать вышеупомянутые операции над строками символов. Затем сделайте функции функциональными. Затем переведите на работу с типами.
Я бы поспорил даже деньги, которые boost
имеет соответствующий accumulate
уже написано.