Variadic templates: Interlacing multiple packs

Question

Given any number of packs, take the first type from each pack, put them together. Then the second type from each pack, put them together, etc... Then merge them all. Any leftoevers will repeat the process among themselves. For example, using integers to represent different types for better readability,

InterlacePacks<Pack<1 2 3 4>, Pack<5 6 7>, Pack<8 9 10 11 12>>::type

will give

Pack<1 5 8 2 6 9 3 7 10 4 11 12>

The following code works if all the packs are the same sizes only. I'm now totally stuck dealing with the "left-overs" when the packs are different sizes. Here is my code so far. I explain each phase so that you know what my plan was:

#include <iostream>

// First a helper to remove the first N types from a pack:
template <int, typename> struct RemoveHead;

template <typename Pack>
struct RemoveHead<0, Pack> { using type = Pack; };

template <template <typename...> class P, typename First, typename... Rest>
struct RemoveHead<0, P<First, Rest...>> { using type = P<First, Rest...>; };

template <int N, template <typename...> class P, typename First, typename... Rest>
struct RemoveHead<N, P<First, Rest...>> : RemoveHead<N-1, P<Rest...>> {};

// Now a helper to merge multiple packs:
template <typename...> struct MergePacks;

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

// Final Pack type shall be the first one listed, if there are different pack types.
template <template <typename...> class P1, template <typename...> class P2, typename... Types1, typename... Types2, typename... Packs>
struct MergePacks<P1<Types1...>, P2<Types2...>, Packs...> : MergePacks<P1<Types1..., Types2...>, Packs...> {};

// First collect the first type from each pack:
template <typename, typename...> struct InterlacePacksHelper1;

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

template <template <typename...> class P, template <typename...> class FirstPack, typename... Ts, typename First, typename... Rest, typename... Packs>
struct InterlacePacksHelper1<P<Ts...>, FirstPack<First, Rest...>, Packs...> : InterlacePacksHelper1<P<Ts..., First>, Packs...> {};

// Now remove the first type from each pack and repeat the process.  Use a parameter N as a counter, where N will start as the minimum size of the packs.
template <int, typename, typename...> struct InterlacePacksHelper;

template <template <typename...> class P, typename... Ts, typename... Packs>
struct InterlacePacksHelper<0, P<Ts...>, Packs...> { using type = P<Ts...>; };

template <int N, template <typename...> class P, typename... Ts, typename... Packs>
struct InterlacePacksHelper<N, P<Ts...>, Packs...> : InterlacePacksHelper<N-1,
    typename MergePacks<P<Ts...>, typename InterlacePacksHelper1<P<>, Packs...>::type>::type,
    typename RemoveHead<1, Packs>::type...> {};

// Now obtain the smallest pack size, given a list of packs.
template <int N, typename...> struct MinPackSize;

template <int N>
struct MinPackSize<N> : std::integral_constant<int, N> {};

template <int N, template <typename...> class P, typename... Types, typename... Packs>
struct MinPackSize<N, P<Types...>, Packs...> : std::integral_constant<int,
    (sizeof...(Types) < N) ? sizeof...(Types) : N> {}; 

// Finally, InterlacePacks itself.
template <typename...> struct InterlacePacks;

template <template <typename...> class P, typename... Ts, typename... Packs>
struct InterlacePacks<P<Ts...>, Packs...> : InterlacePacksHelper<MinPackSize<sizeof...(Ts), Packs...>::value, P<>, P<Ts...>, Packs...> {};

// test ----------------------------------------------------------------
template <typename...> struct Pack {};
template <typename...> struct Group {};
template <typename...> struct Wrap {};
struct Object {};  struct Blob {};

int main() {
    using TestPack1 = Pack<int, double, Object>;  // 3 types
    using TestPack2 = Group<double, std::string, int, short, long>;  // 5 types
    using TestPack3 = Wrap<char, short, Blob, std::string>;  // 4 types
    InterlacePacks<TestPack1, TestPack2, TestPack3>::type interlacedPack;
    std::cout << std::boolalpha << std::is_same< decltype(interlacedPack),
        Pack<int, double, char, double, std::string, short, Object, int, Blob> >::value << std::endl;  // true
//  Want it to be Pack<int, double, char, double, std::string, short, Object, int, Blob, short, std::string, long>
}

So how to fix the code so that the desired output

Pack<int, double, char, double, std::string, short, Object, int, Blob, short, std::string, long>

results instead?

Note: I tried using MaxPackSize intead of MinPackSize, and as expected that would not compile. One idea is to discard the empty packs after MinPackSize iterations and continue the process until MaxPackSize iterations are done (removing new empty packs each time). That's in theory though (haven't tried that yet):

template <typename, typename...> struct RemoveAllEmptyPacksHelper;

template <template <typename...> class P, typename... Packs> 
struct RemoveAllEmptyPacksHelper<P<Packs...>> : Identity<P<Packs...>> {};

template <template <typename...> class P, typename... CurrentPacks, template <typename...> class FirstPack, typename... Types, typename... Packs> 
struct RemoveAllEmptyPacksHelper<P<CurrentPacks...>, FirstPack<Types...>, Packs...> : 
    std::conditional<(sizeof...(Types) == 0),
    RemoveAllEmptyPacksHelper<P<CurrentPacks...>, Packs...>,
    RemoveAllEmptyPacksHelper<P<CurrentPacks..., FirstPack<Types...>>, Packs...>
    >::type {};

template <typename> struct RemoveAllEmptyPacks;

template <template <typename...> class P, typename... Packs> 
struct RemoveAllEmptyPacks<P<Packs...>> : RemoveAllEmptyPacksHelper<P<>, Packs...> {};

Answer 1

This is my shortest C++11-attempt so far:

template <class T, class...> struct interlace_ {using type = T;};
template <class... R,  template<class...> class T, class f, class... t, class... P>
struct interlace_<std::tuple<R...>, T<f, t...>, P...>
    : interlace_<std::tuple<R..., f>, P..., T<t...>> {};
template <class... R, template<class...> class T, class f, class... P>
struct interlace_<std::tuple<R...>, T<f>, P...>
    : interlace_<std::tuple<R..., f>, P...> {};

template <class... packs>
using interlace = interlace_<std::tuple<>, packs...>;

Demo. P stands for the packs, R is the (current) result pack, f is the first type and t is the tail of the pack that is currently observed. T is the template that holds the packs.

Answer 2

The following may help, it use an helper class and aggregate the result in the first template argument:

template <typename...> struct InterlacePacksHelper;

// general case: take first parameter and en-queue the Pack for further computation
template <template <typename...> class PRes, typename... Ts,
          template <typename...> class P, typename U, typename... Us,
          typename... Packs>
struct InterlacePacksHelper<PRes<Ts...>, P<U, Us...>, Packs...>
{
    using type = typename InterlacePacksHelper<PRes<Ts..., U>, Packs..., P<Us...>>::type;
};

// final case
template <template <typename...> class PRes, typename... Ts>
struct InterlacePacksHelper<PRes<Ts...>>
{
    using type = PRes<Ts...>;
};

// Remove empty Pack.
template <template <typename...> class PRes, typename... Ts,
          template <typename...> class P,
          typename... Packs>
struct InterlacePacksHelper<PRes<Ts...>, P<>, Packs...>
{
    using type = typename InterlacePacksHelper<PRes<Ts...>, Packs...>::type;
};


// Finally, InterlacePacks itself.
template <typename...> struct InterlacePacks;

template <template <typename...> class P, typename... Ts, typename... Packs>
struct InterlacePacks<P<Ts...>, Packs...> : InterlacePacksHelper<P<>, P<Ts...>, Packs...>::type
{
    using type = typename InterlacePacksHelper<P<>, P<Ts...>, Packs...>::type;
};

Live demo