Чтобы сделать обход предзаказов вложенной пачки типов (т.е. дерево типов), а затем выполнить действие на каждом листе, я уже разработал алгоритм (и протестирован для правильной работы):
template <typename T>
struct HasChildren : std::false_type {};
template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};
template <typename, typename> struct Merge;
template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
using type = P1<Ts..., Us...>;
};
template <typename, typename> struct Visit;
template <typename, typename, bool> struct VisitHelper;
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct Visit<P1<First, Rest...>, P2<Visited...>> :
VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};
template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
struct Visit<P1<>, P2<Visited...>> { // End of recursion. Every leaf in the tree visited.
using result = P2<Visited...>;
};
template <typename, typename> struct LeafAction;
// As a simple example, the leaf action is appending its type to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {}; // Having visited First, now visit Rest...
// Here First has children, so visit its children, after which visit Rest...
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> : Visit<typename Merge<First, P1<Rest...>>::type, P2<Visited...>> {};
// Here First has no children, so the "leaf action" is carried out.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};
Мое "действие листа" здесь просто хранит тип каждого посещенного листа, как показывает мой тест:
template <typename...> struct Pack {};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};
int main() {
std::cout << std::boolalpha << std::is_same<
Visit<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>, Pack<>>::type,
Pack<int, Object, double, bool, char, int, double, char, char, long, short, int, Object, char, double, long>
>::value << std::endl; // true
}
Но теперь моя проблема заключается в следующем: что делать, если есть действие, выполняемое на каждом нелисте, и такое "действие без листьев" выполняется ПОСЛЕ посещения детей? Как помнить не-лист?
Вот пример задачи, которая потребует этого:
Обратившись к моей программе Visit
выше, после посещения каждого дочернего элемента node (но не раньше) добавьте первый тип в пакет без листа в пакет P<Visited...>
. Если лист посещен, добавьте его в пакет P<Visited...>
, как в исходной программе. В связи с этим конкретным порядком, Visit<Pack<Types...>>::type
будет иметь определенный порядок. Решите это, и исходный вопрос будет решен.
Вот простое решение, если это нелистовое действие выполняется перед посещением его детей:
#include <iostream>
#include <type_traits>
#include <typeinfo>
template <typename T>
struct HasChildren : std::false_type {};
template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};
template <typename, typename> struct Merge;
template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
using type = P1<Ts..., Us...>;
};
template <typename> struct FirstType;
template <template <typename...> class P, typename First, typename... Rest>
struct FirstType<P<First, Rest...>> {
using type = First;
};
template <typename, typename> struct Visit;
template <typename, typename, bool> struct VisitHelper;
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct Visit<P1<First, Rest...>, P2<Visited...>> :
VisitHelper<P1<First, Rest...>, P2<Visited...>, HasChildren<First>::value> {};
template <template <typename...> class P1, template <typename...> class P2, typename... Visited>
struct Visit<P1<>, P2<Visited...>> { // End of recursion. Every leaf in the tree visited.
using result = P2<Visited...>;
};
template <typename, typename> struct LeafAction;
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct LeafAction<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., First>> {};
template <typename, typename> struct NonLeafActionPrevisit;
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPrevisit<P1<First, Rest...>, P2<Visited...>> :
Visit<typename Merge<First, P1<Rest...>>::type, P2<Visited..., typename FirstType<First>::type>> {};
// Here First has children, so visit its children, after which visit Rest..., but before doing so carry out the non-leaf action in the inherited struct.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> :
NonLeafActionPrevisit<P1<First, Rest...>, P2<Visited...>> {}; // *** The simple solution here.
// Here First has no children, so the "leaf action" is carried out. In this case, it is appended to P<Visited...> as a simple example.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> : LeafAction<P1<First, Rest...>, P2<Visited...>> {};
template <typename> struct VisitTree;
template <template <typename...> class P, typename... Types>
struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>> {};
// ---------------------------- Testing ----------------------------
template <typename...> struct Pack {};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};
int main() {
std::cout << std::boolalpha << std::is_same<
VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>::result,
Pack<int, int, Object, double, bool, char, char, int, int, double, char, char, char, char, long, short, int, Object, char, double, long>
>::value << std::endl; // true
}
Теперь, каково решение, если это нелистовое действие должно выполняться ПОСЛЕ посещения детей? В этом случае выход будет отличаться, а именно:
Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, int, char, char, double, long>
Идея: Получить последнего ребенка с первого. Сохраните этот последний ребенок и сначала где-нибудь (но где???). Когда этот последний ребенок будет посещен, выполните одностороннее действие на первом. Что-то вроде:
template <typename, typename, typename> struct Visit;
template <typename, typename, typename, bool> struct VisitHelper;
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct Visit<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>> :
VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, HasChildren<First>::value> {};
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename... ChildAndParent, typename... Visited>
struct Visit<P1<>, P2<ChildAndParent...>, P3<Visited...>> { // End of recursion. Every leaf in the tree visited.
using type = P3<Visited...>;
};
// Here First has children, so visit its children, after which visit Rest...
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, true> :
Visit<typename Merge<First, P2<Rest...>>::type, P2<ChildAndParent...,
typename LastType<First>::type, First>, P3<Visited...>> {};
// Idea: Get the last child from First. Store that last child and First here. When that last child is visited, carry out the non-leaf action on First.
// Here First has no children, so the "leaf action" is carried out. In this case, it is appended to P<Visited...> as a simple example.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... ChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<ChildAndParent...>, P3<Visited...>, false> :
Visit<P1<Rest...>, P2<ChildAndParent...>, P3<Visited..., First>> {};
Теперь жесткой частью было бы использовать P2<ChildAndParent...>
правильно, предполагая, что идея будет работать вообще.
Обновление (через 12 часов): Хорошо, я старался изо всех сил. Вот то, что я придумал, компилирует, но это ускользает от меня, почему я все равно получаю неправильный результат. Возможно, кто-то может пролить свет на это.
#include <iostream>
#include <type_traits>
#include <typeinfo>
template <typename T>
struct HasChildren : std::false_type {};
template <template <typename...> class P, typename... Types>
struct HasChildren<P<Types...>> : std::true_type {};
template <typename, typename> struct Merge;
template <template <typename...> class P1, template <typename...> class P2, typename... Ts, typename... Us>
struct Merge<P1<Ts...>, P2<Us...>> {
using type = P1<Ts..., Us...>;
};
template <typename> struct FirstType;
template <template <typename...> class P, typename First, typename... Rest>
struct FirstType<P<First, Rest...>> {
using type = First;
};
template <typename> struct LastType;
template <template <typename...> class P, typename Last>
struct LastType<P<Last>> {
using type = Last;
};
template <template <typename...> class P, typename First, typename... Rest>
struct LastType<P<First, Rest...>> : LastType<P<Rest...>> {};
template <typename, typename...> struct ExistsInPack;
template <typename T, typename First, typename... Rest>
struct ExistsInPack<T, First, Rest...> : ExistsInPack<T, Rest...> {};
template <typename T, typename... Rest>
struct ExistsInPack<T, T, Rest...> : std::true_type {};
template <typename T>
struct ExistsInPack<T> : std::false_type {};
template <typename Child, typename First, typename Second, typename... Rest>
struct GetParent : GetParent<Child, Rest...> {};
template <typename Child, typename Parent, typename... Rest>
struct GetParent<Child, Child, Parent, Rest...> {
using type = Parent;
};
template <typename, typename, typename> struct RemoveChildAndParentHelper;
template <template <typename...> class P, typename Child, typename First, typename Second, typename... Rest, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<First, Second, Rest...>, P<Accumulated...>> : RemoveChildAndParentHelper<Child, P<Rest...>, P<Accumulated..., First, Second>> {};
template <template <typename...> class P, typename Child, typename Parent, typename... Rest, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<Child, Parent, Rest...>, P<Accumulated...>> {
using type = P<Accumulated..., Rest...>;
};
template <template <typename...> class P, typename Child, typename... Accumulated>
struct RemoveChildAndParentHelper<Child, P<>, P<Accumulated...>> {
using type = P<Accumulated...>;
};
template <typename, typename> struct RemoveChildAndParent;
template <template <typename...> class P, typename Child, typename... LastChildAndParent>
struct RemoveChildAndParent<Child, P<LastChildAndParent...>> : RemoveChildAndParentHelper<Child, P<LastChildAndParent...>, P<>> {};
template <typename, typename, typename> struct Visit;
template <typename, typename, typename, bool> struct VisitHelper;
template <typename, typename, typename, bool> struct CheckIfLastChild;
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct Visit<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>> :
VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, HasChildren<First>::value> {};
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename... LastChildAndParent, typename... Visited>
struct Visit<P1<>, P2<LastChildAndParent...>, P3<Visited...>> { // End of recursion. Every leaf in the tree visited.
using result = P3<Visited...>;
using storage = P2<LastChildAndParent...>; // just for checking (remove later)
};
// Here First has children, so visit its children, after which visit Rest...
// Get the last child from First. Store that last child and First here. When that last child is visited later on, carry out the non-leaf action on First.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, true> :
Visit<typename Merge<First, P2<Rest...>>::type, P2<LastChildAndParent..., typename LastType<First>::type, First>, P3<Visited...>> {};
// Here First has no children, so the "leaf action" is carried out. In this case, it is appended to P<Visited...>.
// Check if First is a last child. If so the non-leaf action of its parent is to be carried out immediately after First action is carried out.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, false> :
CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, ExistsInPack<First, LastChildAndParent...>::value> {};
// First is a last child (and is a leaf), so append First to P3<Visited...> (the leaf action), and then append the first type of its parent to P3<Visited...> after it (the non-leaf action).
// First and its parent must be removed from P2<LastChildAndParent...> at this point.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, true> :
Visit<P1<Rest...>, typename RemoveChildAndParent<First, P2<LastChildAndParent...>>::type, P3<Visited..., First, typename FirstType<typename GetParent<First, LastChildAndParent...>::type>::type>> {};
// First is not a last child (but is a leaf), so append First to P3<Visited...> (the leaf action) and proceed with visiting the next type in P1<Rest...>.
template <template <typename...> class P1, template <typename...> class P2, template <typename...> class P3, typename First, typename... Rest, typename... LastChildAndParent, typename... Visited>
struct CheckIfLastChild<P1<First, Rest...>, P2<LastChildAndParent...>, P3<Visited...>, false> : Visit<P1<Rest...>, P2<LastChildAndParent...>, P3<Visited..., First>> {};
template <typename> struct VisitTree;
template <template <typename...> class P, typename... Types>
struct VisitTree<P<Types...>> : Visit<P<Types...>, P<>, P<>> {};
// ---------------------------- Testing ----------------------------
template <typename...> struct Pack;
template <typename Last>
struct Pack<Last> {
static void print() {std::cout << typeid(Last).name() << std::endl;}
};
template <typename First, typename... Rest>
struct Pack<First, Rest...> {
static void print() {std::cout << typeid(First).name() << ' '; Pack<Rest...>::print();}
};
template <>
struct Pack<> {
static void print() {std::cout << "empty" << std::endl;}
};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};
int main() {
using Tree = VisitTree<Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>>;
Tree::result::print(); // int Object double int bool char int double char char int char long short int Object char char double long
Tree::storage::print(); // empty
std::cout << std::boolalpha << std::is_same<
Tree::result,
Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, char, char, int, char, double, long>
>::value << std::endl; // false
}
В случае, если вам интересно, вот моя мотивация для этого: Рассмотрим этот цикл (который, очевидно, выполняется во время выполнения):
template <int N>
void Graph<N>::topologicalSortHelper (int v, std::array<bool, N>& visited, std::stack<int>& stack) {
visited[v] = true; // Mark the current node as visited.
for (int x : adjacentVertices[v]) // Repeat for all the vertices adjacent to this vertex.
if (!visited[x])
topologicalSortHelper (x, visited, stack);
stack.push(v); // Push current vertex to 'stack' which stores the result.
}
Здесь есть 2 "нелистовых действия". visited[v] = true;
выполняется перед посещением детей, так что это не проблема (просто сделайте изменение в наследовании), но реальная проблема - stack.push(v);
, которая выполняется после посещения детей. В конечном итоге, я хочу, чтобы Graph<6, 5,2, 5,0, 4,0, 4,1, 2,3, 3,1>::topological_sort
был результатом времени компиляции index_sequence<5,4,2,3,1,0>
, где 6 - число вершин, а 5,2, 5,0, 4,0, 4,1, 2,3, 3,1
описывает ребра графа. Это настоящий проект, над которым я работаю, и я почти закончил. Решите вышеуказанную общую проблему, и я разрешу эту проблему решить.
Обновление: Я заметил ошибку в моей логике. Строка:
Visit<typename Merge<First, P2<Rest...>>::type, P2<LastChildAndParent..., typename LastType<First>::type, First>, P3<Visited...>>
не однозначно определяет, где находится последний ребенок, потому что в дереве могут быть другие листья, имеющие тип First
. Это предполагает, что либо:
-
Исходное дерево должно быть переработано с уникальными серийными номерами для каждого node (последнее средство, поскольку это заставляет клиентский код меняться) или
-
Алгоритм должен назначать уникальные последовательные идентификаторы для каждого node в дереве по мере его прохождения. Эта вторая идея идеальна, поскольку исходное дерево не нуждается в перепроектировании, но это намного сложнее. Например, какой будет идентификационный номер для ребенка, который, как известно, существует, но еще не был посещен в обход? Похоже, что номера ветвей должны будут соответствовать идентификатору каждого node.
Кстати, мне удалось решить мою оригинальную проблему топологического сортирования времени компиляции для графика: http://ideone.com/9DKh4s
Он использует шаблон, который разрабатывается в этом потоке, и мне повезло, что каждая вершина имеет уникальные значения node. Но я все же хочу знать общее решение в том случае, если узлы дерева не имеют уникальных значений, не прилагая уникальных последовательных идентификаторов к каждому node исходного дерева (что серьезно угадывает дизайн исходного дерева), т.е. выполнить решение № 2, описанное выше, или что-то подобное).
Обновить (после нескольких дней мысли). Теперь работа над новой идеей, которая может вдохновить любого, кто интересуется этой проблемой:
template <typename, typename, typename> struct NonLeafActionPostvisit;
// As a simple example, the postvisit non-leaf action is appending the first type of the pack to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename ChildrenVisits, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPostvisit<ChildrenVisits, P1<First, Rest...>, P2<Visited...>> :
Visit<P1<Rest...>, P2<Visited..., typename FirstType<First>::type>> {};
// Postvisit:
// Here First has children, so visit its children, after which carry out the postvisit non-leaf action, and then visit Rest...
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, true> :
NonLeafActionPostvisit<Visit<First, P2<Visited...>>, P1<First, Rest...>, P2<Visited...>> {};
// Here First has no children, so the "leaf action" is carried out. In this case, it is appended to P<Visited...> as a simple example.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct VisitHelper<P1<First, Rest...>, P2<Visited...>, false> :
LeafAction<P1<First, Rest...>, P2<Visited...>> {};
Пока он не дает правильных результатов, но если он работает в конце, он кажется намного более элегантным, чем идеи, которые я уже набросал.