Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

Traversing a tree during compile time, with visiting actions

Tags:

c++

c++11

templates

To make a preorder traversal of a nested pack of types (i.e. a tree of types), and then carry out an action at each leaf, I've worked out an algorithm already (and tested to work correctly):

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...>> {};

My "leaf action" here is simply storing the type of each leaf visited, as my test shows:

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
}

But my problem now is: What if there is to be an action carried out at each non-leaf, and such "non-leaf action" is carried out AFTER the children are visited? How to remember the non-leaf?

Here is an example task which would require this: Referring to my Visit program above, after each child of a node is visited (but not before), append the first type in the non-leaf pack to the P<Visited...> pack. If a leaf is visited, append its type to the P<Visited...> pack, as in the original program. Due to this specific order, Visit<Pack<Types...>>::type will have a specific order as well. Solve this, and the original question is solved.

Here is the simple solution if that non-leaf action is carried out BEFORE visiting its children:

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

Now what is the solution if that non-leaf action is to be carried out AFTER visiting the children? In this case, the output would be different, namely:

Pack<int, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, int, char, char, double, long>

Idea: Get the last child from First. Store that last child and First somewhere (but where???). When that last child is visited, carry out the non-leaf action on First. Something like:

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

Now the tough part would be to make use of P2<ChildAndParent...> properly, assuming the idea will work at all.

Update (12 hours later): Well, I tried my best. Here's what I came up with, which compiles, but it escapes me why I still get the wrong result. Perhaps someone can shed some light on this.

#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's 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
}

In case you are wondering, here is my motivation for this: Consider this loop (which is obviously carried out during run-time):

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

There are 2 "non-leaf actions" here. visited[v] = true; is carried out before visiting the children, so that is no problem (just make the change in the inheritance), but the real problem is stack.push(v);, which is carried out after the children are visited. Ultimately, in the end, I want Graph<6, 5,2, 5,0, 4,0, 4,1, 2,3, 3,1>::topological_sort to be the compile-time result index_sequence<5,4,2,3,1,0>, where 6 is the number of vertices, and 5,2, 5,0, 4,0, 4,1, 2,3, 3,1 describe the edges of the graph. That's the real project I'm working on, which I'm almost finished. Solve the above generic problem, and I will have this problem solved.

Update: I spotted the error in my logic. The line:

Visit<typename Merge<First, P2<Rest...>>::type, P2<LastChildAndParent..., typename LastType<First>::type, First>, P3<Visited...>>

does not uniquely identify where the last child is because there may be other leaves in the tree that are of type First. This suggests that either:

  1. The original tree must be redesigned with unique serial numbers for each node (the last resort, since that forces the client code to change), or

  2. The algorithm should assign unique serial IDs to each node in the tree as it traverses it. This second idea is ideal since the original tree needs not be redesigned, but it is a lot more challenging. For example, what will be the ID number for a child that is known to exist but has not been visited in the traversal yet? It looks like branch numbers will have to serve to ID each node.

Incidentally, I managed to solve my original problem of a compile-time topological sort for a graph: http://ideone.com/9DKh4s

It uses the pattern being worked out in this thread, and I'm lucky that every vertex has unique node values. But I still want to know the general solution in the event that the nodes of the tree do not have unique values, without adjoining unique serial IDs to each node of the original tree (which seriously uglifies the design of the original tree), i.e. carry out solution #2 described above, or something like that).

Update (after some days of thought). Now working on a new idea, which may inspire anyone who is interested in this problem:

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...>> {};

It doesn't give the correct results yet though, but if it works in the end, it seems much more elegant than the ideas I've sketched already.

like image 201
prestokeys Avatar asked Apr 04 '15 22:04

prestokeys

1 Answers

Done!

#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> 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 <typename, typename> struct LeafAction;
template <typename, typename> struct NonLeafActionPostVisit;

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 node in the tree visited.
    using result = P2<Visited...>;
};

// Here First has children, so visit its children now, then carry out the "post-visit 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<P1<First, Rest...>, typename Visit<First, P2<Visited...>>::result> {};
// *** The key!  Pass typename Visit<First, P2<Visited...>>::result into NonLeafActionPostVisit.

// 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...>> {};

// As a simple example, the leaf action shall simply be 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>> {};

// As a simple example, the post-visit non-leaf action shall be appending the first type of the pack to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPostVisit<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., typename FirstType<First>::type>> {};

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 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 <typename...> struct Group;
template <typename...> struct Wrap;
struct Object {};

int main() {
    VisitTree<
        Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>
    >::result::print();  // i Object d i b c i d c c l s c i Object c c i d c l

    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, Object, double, int, bool, char, int, double, char, char, long, short, char, int, Object, char, char, int, double, char, long>
    >::value << std::endl;  // true
}

Good amount of thinking practice I got here. Other solutions are welcomed of course (the bounty is still available to anyone giving an alternate solution).

This solution also made me realize that Merge is not even needed anymore. So I now revise my solutions to the other cases even better:

Visit actions at the leaves only:

#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 Visit;
template <typename, typename, bool> struct VisitHelper;
template <typename, typename> struct LeafAction;

// Here the role of P2<Visited...> is simply to allow LeafAction to carry out its function.  It is not native to the tree structure itself.
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 node in the tree visited.
    using result = P2<Visited...>;
};

// 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<P1<Rest...>, typename Visit<First, P2<Visited...>>::result> {};  // Visit the "subtree" First, and then after that visit Rest...  Need to use ::result so that when visiting Rest..., the latest value of the P2<Visited...> pack is used.

// 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...>> {};

// As a simple example, the leaf action shall simply be 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...

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 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 <typename...> struct Group;
template <typename...> struct Wrap;
struct Object {};

int main() {
    VisitTree<
        Pack<Pack<int, Object, double>, bool, Pack<char, Pack<int, double, Pack<char, Pack<char, long, short>, int, Object>, char>, double>, long>
    >::result::print();  // int Object double bool char int double char char long short int Object char double long

    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, Object, double, bool, char, int, double, char, char, long, short, int, Object, char, double, long>
    >::value << std::endl;  // true
}

Visit actions at the nodes before visiting the children of the nodes:

#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> 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 <typename, typename> struct LeafAction;
template <typename, typename> struct NonLeafActionPreVisit;

// Here the role of P2<Visited...> is simply to allow LeafAction to carry out its function.  It is not native to the tree structure itself.
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 node in the tree visited.
    using result = P2<Visited...>;
};

// Here First has children, so carry out the "non-leaf pre-visit action", then visit the children, 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> : NonLeafActionPreVisit<P1<First, Rest...>, 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...>> {};

// As a simple example, the leaf action shall simply be 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>> {};

// As a simple example, the non-leaf pre-visit action shall simply be appending the first type of the pack to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPreVisit<P1<First, Rest...>, P2<Visited...>> :
    Visit<P1<Rest...>, typename Visit<First, P2<Visited..., typename FirstType<First>::type>>::result> {};  // typename FirstType<First>::type is appended to P2<Visited...> (the non-leaf pre-visit action), then Visit<First, P2<Visited..., typename FirstType<First>::type>> is carried out (which is visiting all the children), and then Rest... is visited using ::result of that visiting of the children. 

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
}

And finally, we close this chapter with all three actions together.

Actions at the leaves, at the nodes before visiting the children, and at the nodes after visiting the children:

#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> 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 <typename, typename> struct LeafAction;
template <typename, typename> struct NonLeafActionPreVisit;
template <typename, typename> struct NonLeafActionPostVisit;

// Here the role of P2<Visited...> is simply to allow LeafAction, NonLeafActionPreVisit, and NonLeafActionPostVisit to carry out their functions.  It is not native to the tree structure itself.
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 node in the tree visited.
    using result = P2<Visited...>;
};

// Here First has children, so carry out the pre-visit non-leaf action, then visit its children, then carry out the post-visit 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> :
    NonLeafActionPreVisit<P1<First, Rest...>, 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...>> {};

// As a simple example, the leaf action shall simply be 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>> {};

// As a simple example, the pre-visit non-leaf action shall be appending the first type of the pack to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPreVisit<P1<First, Rest...>, P2<Visited...>> :
    NonLeafActionPostVisit<P1<First, Rest...>, typename Visit<First, P2<Visited..., typename FirstType<First>::type>>::result> {};

// As a simple example, the post-visit non-leaf action shall be appending the first type of the pack to P<Visited...>.
template <template <typename...> class P1, template <typename...> class P2, typename First, typename... Rest, typename... Visited>
struct NonLeafActionPostVisit<P1<First, Rest...>, P2<Visited...>> : Visit<P1<Rest...>, P2<Visited..., typename FirstType<First>::type>> {};

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 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 <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};

int main() {
    VisitTree<
        Pack<Wrap<int, Object, double>, bool, Group<char, Pack<int, double, Pack<char, Wrap<char, long, short>, int, Object>, char>, double>, long>
    >::result::print();  // i i Object d i b c c i i d c c c c l s c i Object c c i d c l

    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, int, bool, char, char, int, int, double, char, char, char, char, long, short, char, int, Object, char, char, int, double, char, long>
    >::value << std::endl;  // true
}

Lastly, I would like to share my solution to the original problem of getting a compile-time topological sort of a directed acyclic graph using this new method (which is what motivated all this in the first place): http://ideone.com/U1bbRM

like image 188
prestokeys Avatar answered Nov 11 '22 14:11

prestokeys
Sign in to Comment

Related questions

How do I generate a random number between two variables that I have stored? [duplicate]
Fill a vector with random numbers c++
Does java really have pointers or not? [closed]
How to execute a piece of code only once?
Objects that can be initialized but not assigned
What are some tricks I can use with macros? [closed]
C++ const keyword - use liberally?
Adding the ! operator and sqrt(), pow(), etc. to a calculator example application
What does it mean for an object to exist in C++?
Is std::swap(x, x) guaranteed to leave x unchanged?
How to register C++ React Native module in Android
Why does this code compile with gcc but not with clang
Why is DFS slower in one tree and faster in the other?
Why is my hand-tuned, SSE-enabled code so slow?
Must template argument functions be treated as potentially constexpr?
Lock-free Reference counting and C++ smart pointers
Passing a C++ object to Python
Symptoms and alternatives to overused OOP
ctags in sublime text
Separating C++ Class Code into Multiple Files, what are the rules?

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!