Generating a template pack

Generate<P<3>, P<5,0>, P<4,0,0>, P<3,0,1>>::type is to be

Pack< A<0>, A<0,0>, A<0,0,0>, A<0,0,1>, A<0,0,2>, A<0,0,3>, A<0,1>, A<0,1,0>, A<0,1,1>, A<0,1,2>, A<0,2>, A<0,3>, A<0,4>, A<1>, A<2> >

because P<3> means that P<n> exists for n = 0,1,2; P<5,0> means that A<0,n> exists for n = 0,1,2,3,4; P<4,0,0> means that A<0,0,n> exists for n = 0,1,2,3; and P<3,0,1> means that A<0,1,n> exists for n = 0,1,2. In terms of ordering, A<n1,n2,n3,...,nk,x,...> will always precede A<n1,n2,n3,...,nk,y,...> if x < y and A<n1,n2,n3,...,nk> will always precede A<n1,n2,n3,...,nk, ...>, where the second elipses ... is non-empty. So I need to write out the implementation of Generate<Packs...>.

Motivation for this: If template <int... Is> class Object has certain possibilities for its Is... pack, defined by constants like the 3, 5, 4, and 3 above, then a pack of all of its possible types will allow generation of specific Object<Is...> instances by iterating through the pack.

Here is what I have so far:

#include <iostream>
#include <type_traits>

template <int...> class A;
template <typename...> struct Pack;
template <int...> struct P;

template <int N, int Count, typename Front, typename Output> struct GenerateHelper;

template <int N, int Count, int... Is, typename... As>
struct GenerateHelper<N, Count, P<Is...>, Pack<As...>> :
    GenerateHelper<N, Count + 1, P<Is...>, Pack<As..., A<Is..., Count>>> {};

template <int N, int... Is, typename... As>
struct GenerateHelper<N, N, P<Is...>, Pack<As...>> {
    using type = Pack<As...>;
};

template <typename...> struct Generate;

// Simple special case just to start off.  Generate has only one pack to deal with.
template <int N, int... Is>
struct Generate<P<N, Is...>> : GenerateHelper<N, 0, P<Is...>, Pack<>> {};

int main() {
    using T = Generate<P<3,0,0>>::type;
    std::cout << std::is_same<T, Pack<A<0,0,0>, A<0,0,1>, A<0,0,2>>>::value << '\n'; // true
}

But now I'm stuck with the case of just 2 packs in Generate. Can anyone help me continue?

Idea: For 2 packs, just generate separately, merge the two Packs, and then sort after? But then the sorting will be the hardest part I think.

Solution

The trick is realizing that the sequence you get from each "generation" procedure is already sorted, and the problem reduces to merging several sorted lists.

For simplicity, I made A, Pack and P empty structs.

template <int...> class A {};
template <typename...> struct Pack {};
template <int...> struct P {};

Generate a pack of As from one P:

template<int I, int... Tail>
auto do_sequence_for(P<I, Tail...>) -> std::make_integer_sequence<int, I>;

template<class PP>
using sequence_for = decltype(do_sequence_for(PP()));

template<int I, int... Front, int... Tail>
auto do_generate_single(P<I, Front...>, std::integer_sequence<int, Tail...>)
     -> Pack<A<Front..., Tail>...>;

template<class PP>
using generate_single = decltype(do_generate_single(PP(), sequence_for<PP>()));

Lexicographical comparison of two As:

template<class A1, class A2>
struct compare; // returns A1 < A2

template<int I, int J, int...Is, int...Js>
struct compare<A<I, Is...>, A<J, Js...>> : std::integral_constant<bool, I < J> {};

template<int I, int...Is, int...Js>
struct compare<A<I, Is...>, A<I, Js...>> : compare<A<Is...>, A<Js...>> {};

template<int...Is>
struct compare<A<Is...>, A<>> : std::false_type {};

template<int J, int...Js>
struct compare<A<>, A<J, Js...>> : std::true_type {};

Merging two sorted packs of As:

template<class Pack1, class Pack2, class Result=Pack<>>
struct merge2;

template<class A1, class...A1s, class A2, class...A2s, class...R>
struct merge2<Pack<A1, A1s...>, Pack<A2, A2s...>, Pack<R...>>
    : std::conditional_t<compare<A1, A2>::value,
                         merge2<Pack<A1s...>, Pack<A2, A2s...>, Pack<R..., A1>>,
                         merge2<Pack<A1, A1s...>, Pack<A2s...>, Pack<R..., A2>>>
{};

template<class...A1s, class...R>
struct merge2<Pack<A1s...>, Pack<>, Pack<R...>>
{
    using type = Pack<R..., A1s...>;
};

template<class A2, class...A2s, class...R>
struct merge2<Pack<>, Pack<A2, A2s...>, Pack<R...>>
{
    using type = Pack<R..., A2, A2s...>;
};

Merge many sorted packs of As:

template<class... Packs>
struct merge;

template<class P1>
struct merge<P1> {
    using type = P1;
};

template<class P1, class P2, class... Ps>
struct merge<P1, P2, Ps...> : merge<typename merge2<P1, P2>::type, Ps...> {};

Bringing it all together:

template<class...Ps>
struct Generate{
    using type = typename merge<generate_single<Ps>...>::type;
};

Demo.