CODEWITHSUNDEEP
c++c++11tuplesvariadic-templatestemplate-meta-programming
prestokeys
prestokeys

Reputation: 4849

Compile-time rearrangement of types in a tuple

Define a typedef of template <typename...> struct order; with the following example:

order<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>::type

is to be

std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O>

because the original types are arranged in a binary tree row by row, from left to right, as in the following diagram:

             A
         /       \
        /         \
       B           C
    /    \       /    \
   D      E     F      G
  / \    / \   / \    / \
 H   I  J   K L   M  N   O

A type that is left of a certain type shall precede that type in the ordering. A type that is right of a certain type shall follow that type in the ordering. So we can see that H is listed first and O is listed last. The resulting type is std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O> as already stated.

How to build this ordering during compile-time (for any length of the tuple, even if the last row is not finished)? Any help would be appreciated.

The latest idea I have is to use recursion: D,H,I is ordered as H,D,I. E,J,K is ordered as J,E,K. Then B,D,E,H,I,J,K is ordered as H,D,I, B, J,E,K, i.e. we use the previous two orderings to build the ordering of the tree that is one generation bigger, placing the "root" B in the middle. Then we can do that for the right subtree of A, and then the entire tree in the example can be concatenated similarly (with A in the middle). Something like that, but now figuring out how to translate that into code is the problem. Something along the lines of (before refinements and generalizations):

template <typename... Packs> struct concat;

template <template <typename...> class P, typename... Ts, typename... Us>
struct concat<P<Ts...>, P<Us...>> {
    using type = P<Ts..., Us...>;
};

template <typename Pack1, typename Pack2, typename... Packs>
struct concat<Pack1, Pack2, Packs...> : concat<Pack1, typename concat<Pack2, Packs...>::type> {};

template <typename...> struct order;

template <typename T>
struct order<T> {
    using type = std::tuple<T>;
};

template <typename A, typename B, typename C>
struct order<A,B,C> :
    concat<typename order<B>::type, std::tuple<A>, typename order<C>::type> {};

template <typename A, typename B, typename C, typename D, typename E, typename F, typename G>
struct order<A,B,C,D,E,F,G> :
    concat<typename order<B,D,E>::type, std::tuple<A>, typename order<C,F,G>::type> {};

Upvotes: 2

Views: 610

Answers (2)

prestokeys
prestokeys

Reputation: 4849

Here is T.C.'s solution generalized to any type of traversal of an N-ary tree, where reorder<std::tuple, 2, 1, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O> is the special case of the original problem (binary tree inorder traversal), as the 2 indicates a binary tree, and the 1 indicates action after recursion with the first child. The 2 and 1 can take on any other values.

#include <type_traits>
#include <utility>
#include <tuple>

// Concatenating std::index_sequences.
template <typename... Packs> struct concat;

template <typename Pack>
struct concat<Pack> {
    using type = Pack;
};

template <std::size_t... Is, std::size_t... Js>
struct concat<std::index_sequence<Is...>, std::index_sequence<Js...>> {
    using type = std::index_sequence<Is..., Js...>;
};

template <typename Pack1, typename Pack2, typename... Packs>
struct concat<Pack1, Pack2, Packs...> : concat<Pack1, typename concat<Pack2, Packs...>::type> {};

// In-order traversal for a complete binary tree whose level-order traversal is 0,1,2, ..., max-1.
template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename = void>
struct traversal {
    using type = std::index_sequence<>;  // So that concatenating changes nothing and ends the recursion.
};

// General recursion.
template <std::size_t Count, std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename Pack, bool ActionJustTookPlace = false>
struct concat_traversals_impl : concat_traversals_impl<Count + 1, NumChildren, ActionPoint, Start, Max,
        typename concat<Pack, typename traversal<NumChildren, ActionPoint, NumChildren * Start + Count + 1, Max>::type>::type> {};

//             0
//         /   |   \
//        /    |    \
//       1     2     3
//    /  |  \
//   4   5  6
// Above we see that the three children of node K is 3*K+1, 3*K+2, 3*K+3.  In general, it is N*K+1, N*K+2, ..., N*K+N, where N is the number of children. 

// If Count == ActionPoint (and ActionJustTookPlace == false), then concat the action, which is std::index_sequence<Start> in this case, but then let ActionJustTookPlace == true so that this does not happen infinitely (as Count still remains equal to ActionPoint) on the next template instantiation, and the primary template is used instead.
template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename Pack>
struct concat_traversals_impl<ActionPoint, NumChildren, ActionPoint, Start, Max, Pack, false> : concat_traversals_impl<ActionPoint, NumChildren, ActionPoint, Start, Max,
        typename concat<Pack, std::index_sequence<Start>>::type, true> {};

// End the recursion when Count == NumChildren. 
template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename Pack>
struct concat_traversals_impl<NumChildren, NumChildren, ActionPoint, Start, Max, Pack> {
    using type = Pack;
};

// Special case of when Count == NumChildren and ActionPoint == NumChildren as well (this partial specialization is needed else there will be ambiguity compilng error).
template <std::size_t ActionPoint, std::size_t Start, std::size_t Max, typename Pack>
struct concat_traversals_impl<ActionPoint, ActionPoint, ActionPoint, Start, Max, Pack, false> : concat<Pack, std::index_sequence<Start>> {};

template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max>
using concat_traversals = typename concat_traversals_impl<0, NumChildren, ActionPoint, Start, Max, std::index_sequence<>>::type;

template <std::size_t NumChildren, std::size_t ActionPoint, std::size_t Start, std::size_t Max>  // Recursive call.
struct traversal<NumChildren, ActionPoint, Start, Max, std::enable_if_t<(Start < Max)>> {
    using type = concat_traversals<NumChildren, ActionPoint, Start, Max>;
};

// Now the actual reordering.
template <typename Pack, typename Sequence> struct reorder_helper;

template <template <typename...> class P, typename... Ts, std::size_t... Is>
struct reorder_helper<P<Ts...>, std::index_sequence<Is...>> {
    using type = P<std::tuple_element_t<Is, std::tuple<Ts...>>...>;
};

template <template <typename...> class P, std::size_t NumChildren, std::size_t ActionPoint, typename... Ts>
using reorder = typename reorder_helper<P<Ts...>, typename traversal<NumChildren, ActionPoint, 0, sizeof...(Ts)>::type>::type;

// Special syntax for reordering a pack.
template <std::size_t NumChildren, std::size_t ActionPoint, typename Pack> struct reorder_pack;

template <std::size_t NumChildren, std::size_t ActionPoint, template <typename...> class P, typename... Ts>
struct reorder_pack<NumChildren, ActionPoint, P<Ts...>> {
    using type = reorder<P, NumChildren, ActionPoint, Ts...>;
};

// Testing
struct A{};  struct B{};  struct C{};  struct D{};  struct E{};  struct F{};  struct G{};  struct H{};
struct I{};  struct J{};  struct K{};  struct L{};  struct M{};  struct N{};  struct O{};

int main() {
    static_assert (std::is_same<
        reorder<std::tuple, 2, 1, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>,  // 2 means it is a binary tree, 1 means that we do left traversal, then the node action, then right traversal (i.e. inorder traversal).
        std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O>
    >::value, "");

    static_assert (std::is_same<
        reorder<std::tuple, 2, 0, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>,  // 2 means it is a binary tree, 0 means that we do the node action, then left traversal, and then right traversal (i.e. preorder traversal).
        std::tuple<A,B,D,H,I,E,J,K,C,F,L,M,G,N,O>
    >::value, "");

    static_assert (std::is_same<
        reorder<std::tuple, 2, 2, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>,  // 2 means it is a binary tree, 2 means that we do left traversal, then right traversal, then the node action (i.e. postorder traversal).
        std::tuple<H,I,D,J,K,E,B,L,M,F,N,O,G,C,A>
    >::value, "");

    static_assert (std::is_same<    
        reorder_pack<3, 2, std::tuple<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>>::type,  // 3 children per node.  Do first child, second child, then node action, then do third child recursively. 
        std::tuple<N,O,E,F,B,G,H,I,C,J,A,K,L,D,M>
    >::value, "");      
}

Upvotes: 0

T.C.
T.C.

Reputation: 137315

Concatenate three std::index_sequences (trivial to generalize, but I just need exactly three here):

template<size_t... Seq1, size_t... Seq2, size_t... Seq3>
auto concat3_impl(std::index_sequence<Seq1...>, 
                  std::index_sequence<Seq2...>,
                  std::index_sequence<Seq3...>)
  -> std::index_sequence<Seq1..., Seq2..., Seq3...>;

template<class...Ts>
using concat3 = decltype(concat3_impl(Ts{}...));

In-order traversal for a complete binary tree whose level-order traversal is 0, 1, ..., (max - 1):

template<size_t start, size_t max, bool = (start < max) >
struct in_order;

template<size_t start, size_t max>
using in_order_t = typename in_order<start, max>::type;

template<size_t start, size_t max, bool >
struct in_order {
    using type = concat3<in_order_t<2*start + 1, max>, 
                         std::index_sequence<start>,
                         in_order_t<2*start + 2, max>>;
};

template<size_t start, size_t max >
struct in_order<start, max, false> {
    using type = std::index_sequence<>;
};

Reorder a tuple according to a list of indices:

template<class Tuple, size_t...Is>
auto reorder_by_index_impl(std::index_sequence<Is...>)
    -> std::tuple<std::tuple_element_t<Is, Tuple>...>;

template<class Tuple, class Index>
using reorder_by_index = decltype(reorder_by_index_impl<Tuple>(Index{}));

Finally:

template<class Tuple>
using reorder_tuple = reorder_by_index<Tuple, in_order_t<0, std::tuple_size<Tuple>{}>>;

Demo:

struct A{}; struct B{}; struct C{}; struct D{}; struct E{};
struct F{}; struct G{}; struct H{}; struct I{}; struct J{};
struct K{}; struct L{}; struct M{}; struct N{}; struct O{};

using t = reorder_tuple<std::tuple<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O>>;
using t = std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O>; // OK, same type.

Upvotes: 4

Related Questions