Kompilierzeit-Umlagerung von Arten in einem Tupel

Question

Definieren eines typedef von template <typename...> struct order; mit dem folgenden Beispiel:

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

ist

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

werden, da die Originaltypen in einem Binärbaum Reihe angeordnet sind, für Zeile, von links nach rechts, wie in folgendem Schema:

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

Ein Typ, der übrig Ein bestimmter Typ muss diesem Typ in der Reihenfolge vorausgehen. Ein Typ, der einem bestimmten Typ entspricht, muss diesem Typ bei der Bestellung folgen. So können wir sehen, dass H zuerst aufgeführt ist und O zuletzt aufgeführt ist. Der resultierende Typ ist std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O> wie bereits erwähnt.

Wie erstellt man diese Reihenfolge während der Kompilierzeit (für eine beliebige Länge des Tupels, auch wenn die letzte Zeile nicht fertig ist)? Jede Hilfe wäre willkommen.

Die neueste Idee, die ich habe, ist Rekursion zu verwenden:D,H,I als H,D,I bestellt wird. E,J,K ist bestellt als J,E,K. Dann wird B,D,E,H,I,J,K als H,D,I,B,J,E,K, bestellt, d. H. Wir verwenden die vorherigen zwei Ordnungen, um die Ordnung des Baumes zu erstellen, der eine Generation größer ist, wobei die "Wurzel" B in der Mitte platziert wird. Dann können wir das für den rechten Teilbaum von A tun, und dann kann der gesamte Baum im Beispiel ähnlich verkettet werden (mit A in der Mitte). So etwas, aber jetzt herauszufinden, wie man das in Code übersetzt, ist das Problem. Etwas nach dem Vorbild von (vor Verfeinerungen und Verallgemeinerungen):

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

Answer 1

Concatenate drei std::index_sequence s (trivial zu verallgemeinern, aber ich brauche nur genau drei hier):

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 für ein vollständiger binärer Baum, dessen Pegel Ordnung Traversierung ist 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<>; 
}; 

ein Tupel Neuanordnen entsprechend einer Liste von Indizes:

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

Schließlich:

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. 

Answer 2

ist hier TC-Lösung auf jede Art von Traversierung eines N-ären Baum verallgemeinert, wo reorder<std::tuple, 2, 1, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O> Das besondere ist, Fall des ursprünglichen Problems (binärer Baum in order traversal), da die 2 einen binären Baum anzeigt und die 1 eine Aktion nach Rekursion mit dem ersten Kind anzeigt. Die 2 und 1 können beliebige andere Werte annehmen.

#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, "");  
}