AllPermutedPacks<Pack<Types...>>::type is to be the pack of packs consisting of all permutations of Types.... For example, AllPermutedPacks<Pack<int, char, double>>::type is to be:
Pack<Pack<int, char, double>, Pack<int, double, char>, Pack<char, int, double>, Pack<char, double, int>, Pack<double, int, char>, Pack<double, char, int>>
Here's a sketch of my idea:
Let's assume three types A,B,C in the pack. AllPermutedPacks ABC will come from A + AllPermutedPacks BC, B + AllPermutedPacks AC, C + AllPermutedPacks AB, where AllPermutedPacks BC will come from B + AllPermutedPacks C, C + AllPermutedPacks B, and similarly for the others.
So when we are down to just one type T left AllPermutedPacks will just give Pack<Pack<T>>. But how to get BC from ABC?
We must use a helper RemoveFirstTypeFound that removes A from the pack ABC. Similarly, for AC and AB. The + operation described above is from another helper Prepend. But prepending must be done for all the permuted types in the recursion, so PrependToEachPack must be defined too. Also we must merge the accumulated pack of packs to the newly generated pack of packs each time, so Merge must also be defined.
Perhaps this plan of mine is more complicated than it needs to be, which is why I'm seeking a better (and shorter) solution. Here is my full solution using the above plan:
#include <iostream>
#include <type_traits>
template <typename, typename, typename...> struct RemoveFirstTypeFound;
template <typename T> struct Identity { using type = T; };
template <typename RemoveMe, template<typename...> class P, typename First, typename... Rest, typename... Types>
struct RemoveFirstTypeFound<RemoveMe, P<First, Rest...>, Types...> : std::conditional<std::is_same<RemoveMe, First>::value,
Identity<P<Types..., Rest...>>,
RemoveFirstTypeFound<RemoveMe, P<Rest...>, Types..., First>
>::type {};
template <typename, typename> struct Prepend;
template <typename T, template <typename...> class P, typename... Types>
struct Prepend<T, P<Types...>> {
using type = P<T, Types...>;
};
template <typename, typename> struct PrependToEachPack;
template <typename T, template <typename...> class P, typename... Packs>
struct PrependToEachPack<T, P<Packs...>> {
using type = P<typename Prepend<T, Packs>::type...>;
};
template <typename, typename> struct Merge;
template <template <typename...> class P, typename... Types1, typename... Types2>
struct Merge<P<Types1...>, P<Types2...>> {
using type = P<Types1..., Types2...>;
};
template <typename, typename, typename> struct AllPermutedPacksHelper;
template <template<typename...> class P, typename Pack, typename... AccumulatedPacks>
struct AllPermutedPacksHelper<Pack, P<>, P<AccumulatedPacks...>> {
using type = P<AccumulatedPacks...>;
};
template <template<typename...> class P, typename... Types, typename Last>
struct AllPermutedPacksHelper<P<Types...>, P<Last>, P<>> {
using type = P<P<Last>>;
};
template <template<typename...> class P, typename First, typename Pack1, typename Pack2, typename Pack3, typename Pack4>
using AllPermutedPacksHelperAlias = AllPermutedPacksHelper<Pack1, Pack2, typename Merge<Pack3,
typename PrependToEachPack<First, typename AllPermutedPacksHelper<Pack4, Pack4, P<>>::type>::type>::type>;
template <template<typename...> class P, typename... Types, typename... AccumulatedPacks, typename First, typename... Rest>
struct AllPermutedPacksHelper<P<Types...>, P<First, Rest...>, P<AccumulatedPacks...>> :
AllPermutedPacksHelperAlias<P, First, P<Types...>, P<Rest...>, P<AccumulatedPacks...>, typename RemoveFirstTypeFound<First, P<Types...>>::type> {};
template <typename> struct AllPermutedPacks;
template <template<typename...> class P, typename... Types>
struct AllPermutedPacks<P<Types...>> : AllPermutedPacksHelper<P<Types...>, P<Types...>, P<>> {};
// -----------------------------------------------------------------------------------------------------------------------------------------------
// Testing
template <typename...> struct Pack {};
int main() {
std::cout << std::boolalpha << std::is_same< AllPermutedPacks<Pack<>>::type,
Pack<>
>::value << std::endl; // true
std::cout << std::is_same< AllPermutedPacks<Pack<int>>::type,
Pack<Pack<int>>
>::value << std::endl; // true
std::cout << std::is_same< AllPermutedPacks<Pack<int, char>>::type,
Pack<Pack<int, char>, Pack<char, int>>
>::value << std::endl; // true
std::cout << std::is_same< AllPermutedPacks<Pack<int, char, double>>::type,
Pack<Pack<int, char, double>, Pack<int, double, char>, Pack<char, int, double>, Pack<char, double, int>, Pack<double, int, char>, Pack<double, char, int>>
>::value << std::endl; // true
}
Can someone suggest a shorter method? I know that RemoveFirstTypeFound<First, P<Types...>>::type is being computed twice so another helper can be used to use it just once, but apart from that?
Update: I shortened my original solution slightly by taking care of the repetition I just mentioned (though now it is perhaps harder to read). But I know there is a shorter and more elegant solution than this. I tried all day to think of a better way, but can't. This question is not insanely hard, so the solution should not be so long.
