Преобразование последовательности последовательностей mpl в три

Проблема выглядит достаточно просто, в основном у меня есть последовательность последовательностей, что-то вроде:

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, надеюсь, теперь вопрос стал яснее …

5

Решение

Там вы идете:

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

Другие решения

Так что ответ «да, это возможно».

Напишите add_to_trie. Он принимает, возможно, пустое дерево и элемент (последовательность типов) и возвращает дерево с этим элементом.

Протестируйте add_to_trie на пустом дереве и некоторой последовательности, а также на нескольких других случаях, созданных вручную. Общий префикс: («A») («A», «B»), без общего префикса: («A», «A») («B», «A»), более короткий без общего префикса: («A» , «B») («B»), две копии одного и того же: («A») («A») и т. Д.

Пиши накапливай. Он принимает значение, двоичный функтор и последовательность. Если применяется значение = функтор (значение, с) к каждому элементу последовательности, то возвращается значение.

Тест накапливается путем суммирования от 1 до 5 и печати результата.

Составьте два.

Это может взорвать ваш стек рекурсии шаблона, и каждый шаг нетривиален, чтобы написать правильно, но это будет работать.

Это может помочь сначала написать вышеупомянутые операции над строками символов. Затем сделайте функции функциональными. Затем переведите на работу с типами.

Я бы поспорил даже деньги, которые boost имеет соответствующий accumulate уже написано.

1

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector