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

template <template <auto...> class> struct functor_wrapper;

namespace detail {
	template <typename T>
	struct identity { using type = T; };
	
	template <typename Pack>
	struct simple_pack : identity<Pack> {};
	
	template <typename T, template <typename U, U...> class Z, T... Is>
	struct simple_pack<Z<T, Is...>> {
		template <T...> struct Q;
		using type = Q<Is...>;
	};
	
   	template <typename... Packs>
   	struct sequence_traits;

   	template <typename T, template <T...> class Z, T... Is>
   	struct sequence_traits<Z<Is...>> {
		using value_type = T;
		using template_empty = Z<>;
	};

   	template <typename T, template <typename U, U...> class Z, T... Is>
   	struct sequence_traits<Z<T, Is...>> {
    	using value_type = T;
		using template_empty = Z<T>;
	};
	
	template <typename First, typename... Rest>
	struct sequence_traits<First, Rest...> : sequence_traits<First> {};

	template <template <auto...> class F, typename Second, typename... Rest>
	struct sequence_traits<functor_wrapper<F>, Second, Rest...> : sequence_traits<Second> {};

	template <typename Pack> struct is_empty : std::false_type {};

	template <template <typename...> class P, typename... Ts>
	struct is_empty<P<Ts...>> : std::bool_constant<(sizeof...(Ts) == 0)> {};  // Empty pack of types.

	template <template <auto...> class Z, auto... Is>  // 'auto' (C++17) needed else the type T would need to be made explicit as an extra template parameter.
	struct is_empty<Z<Is...>> : std::bool_constant<(sizeof...(Is) == 0)> {};  // Empty sequence.

	template <typename T, template <typename U, U...> class Z, T... Is>
	struct is_empty<Z<T, Is...>> : std::bool_constant<(sizeof...(Is) == 0)> {};  // e.g. std::integer_sequence<int> shall be considered empty.
	
	template <typename Pack> struct first_element;
	
	template <typename T, template <T...> class Z, T First, T... Rest>
	struct first_element<Z<First, Rest...>> : std::integral_constant<T, First> {};

	template <typename T, template <typename U, U...> class Z, T First, T... Rest>
	struct first_element<Z<T, First, Rest...>> : std::integral_constant<T, First> {};
	
	template <typename...> struct last;
	
	template <typename First, typename... Rest>
	struct last<First, Rest...> : last<Rest...> {};
	
	template <typename Last>
	struct last<Last> : identity<Last> {};

	// The rest needed for Transform and TransformToEnd
	template <typename... Packs> struct empty_pack;
	
	template <template <auto...> class Z, auto... Is, typename... Packs>
	struct empty_pack<Z<Is...>, Packs...> {
		using type = Z<>;	
	};

	template <std::size_t N, typename Pack, typename = void> struct get_element;
	
	template <std::size_t N, typename T, template <T...> class Z, T... Is>
	struct get_element<N, Z<Is...>, std::enable_if_t<(N < sizeof...(Is))>> {
		static constexpr T a[sizeof...(Is)] = {Is...};
		static constexpr T value = a[N];
	};
	
	// If N is greater than or equal to sizeof...(Is), then it shall output value T{} (which is zero if T is an integral type).
	template <std::size_t N, typename T, template <T...> class Z, T... Is>
	struct get_element<N, Z<Is...>, std::enable_if_t<(N >= sizeof...(Is))>> : std::integral_constant<T, T{}> {};
	
	template <typename Pack, auto V> struct append;
	
	template <template <auto...> class Z, auto... Is, auto V>
	struct append<Z<Is...>, V> {
		using type = Z<Is..., V>;
	};
	
	template <typename Sequence> struct sequence_size;
	
	template <template <auto...> class Z, auto... Is>
	struct sequence_size<Z<Is...>> : std::integral_constant<std::size_t, sizeof...(Is)> {};
	
	template <template <auto, auto> class Comparator, auto...> struct extreme_value;
	
	template <template <auto, auto> class Comparator, auto A, auto B>
	struct extreme_value<Comparator, A,B> : std::integral_constant<decltype(A), Comparator<A,B>::value ? A : B> {};

	template <template <auto, auto> class Comparator, auto First, auto Second, auto... Rest>
	struct extreme_value<Comparator, First, Second, Rest...> : extreme_value<Comparator, First, extreme_value<Comparator, Second, Rest...>::value> {};
}

template <typename EmptyContainer, auto... Is> struct output;  // 'auto' (C++17) used else the type T would need to be made explicit as an extra template parameter.

template <template <auto...> class Z, auto... Is>
struct output<Z<>, Is...> {
	using type = Z<Is...>;
};

template <typename T, template <typename U, U...> class Z, T... Is>
struct output<Z<T>, Is...> {
	using type = Z<T, Is...>;
};

template <typename EmptyContainer, typename Output> struct output_h;

template <typename EmptyContainer, template <auto...> class Z, auto... Is>
struct output_h<EmptyContainer, Z<Is...>> : output<EmptyContainer, Is...> {};

enum CombineType {Merge, FirstFromEach, Interlace, Transform, TransformToEnd};

template <CombineType, typename EmptyPack, typename... Packs> struct combine_packs_h;

// Merge
template <typename EmptyPack, typename T, template <T...> class Z, T... Is>
struct combine_packs_h<Merge, EmptyPack, Z<Is...>> : output<EmptyPack, Is...> {};

template <typename EmptyPack, typename T, template <T...> class Z, T... Is, template <T...> class Q, T... Js>
struct combine_packs_h<Merge, EmptyPack, Z<Is...>, Q<Js...>> : output<EmptyPack, Is..., Js...> {};  // Note that using 'Z<Is...>, Z<Js...>' is not good enough since simple_pack<Pack1>::type does not have the same template as simple_pack<Pack2>::type.

template <typename EmptyPack, typename First, typename... Rest>
struct combine_packs_h<Merge, EmptyPack, First, Rest...> : combine_packs_h<Merge, EmptyPack, First, typename combine_packs_h<Merge, typename detail::sequence_traits<Rest...>::template_empty, Rest...>::type> {};
// Note that using EmptyPack instead of typename detail::sequence_traits<Rest...>::template_empty is incorrect because EmptyPack might not be the proper empty pack type for the first pack in Rest...

// FirstFromEach
template <typename EmptyPack, typename... Packs>
struct combine_packs_h<FirstFromEach, EmptyPack, Packs...> : output<EmptyPack, detail::first_element<Packs>::value...> {};

// Interlace
template <typename Output, typename... Packs> struct interlace;

template <typename T, template <T...> class Q, T... Is>
struct interlace<Q<Is...>> : detail::identity<Q<Is...>> {};

template <typename T, template <T...> class Q, T... Output, template <T...> class Z, T First, T... Rest, typename... Packs>
struct interlace<Q<Output...>, Z<First, Rest...>, Packs...> : interlace<Q<Output..., First>, Packs..., Z<Rest...>> {};

template <typename T, template <T...> class Q, T... Output, template <T...> class Z, typename... Packs>
struct interlace<Q<Output...>, Z<>, Packs...> : interlace<Q<Output...>, Packs...> {};

template <typename EmptyPack, typename... Packs>
struct combine_packs_h<Interlace, EmptyPack, Packs...> : output_h<EmptyPack, typename interlace<typename detail::simple_pack<EmptyPack>::type, Packs...>::type> {};

// Transform and TransformToEnd (adapted from transform_generalized.cpp)
template <auto A, auto B>
struct less_than : std::bool_constant<(A < B)> {};

template <auto A, auto B>
struct greater_than : std::bool_constant<(A > B)> {};

template <template <auto...> class F, std::size_t N, std::size_t End, typename Output, typename... Packs>
struct transform_h : transform_h<F, N+1, End, typename detail::append<Output, F<detail::get_element<N, Packs>::value...>::value>::type, Packs...> {};

template <template <auto...> class F, std::size_t End, typename Output, typename... Packs>
struct transform_h<F, End, End, Output, Packs...> : detail::identity<Output> {};

template <typename EmptyPack, template <auto, auto> class Comparator, template <auto...> class F, typename... Packs>
using do_transform = output_h<EmptyPack, typename transform_h<F, 0, detail::extreme_value<Comparator, detail::sequence_size<Packs>::value...>::value, typename detail::empty_pack<Packs...>::type, Packs...>::type>;

template <typename EmptyPack, template <auto...> class F, typename... Packs>
struct combine_packs_h<Transform, EmptyPack, functor_wrapper<F>, Packs...> : do_transform<EmptyPack, less_than, F, Packs...> {};

template <typename EmptyPack, template <auto...> class F, typename... Packs>
struct combine_packs_h<TransformToEnd, EmptyPack, functor_wrapper<F>, Packs...> : do_transform<EmptyPack, greater_than, F, Packs...> {};

// combine_packs
template <typename Pack> struct remove_last;

template <CombineType C, template <CombineType, typename...> class P, typename EmptyPack, typename... Ts>
struct remove_last<P<C, EmptyPack, Ts...>> {
	template <std::size_t... Is>
	static auto execute (const std::index_sequence<Is...>&) -> P<C, EmptyPack, std::tuple_element_t<Is, std::tuple<Ts...>>...>;

	using type = decltype(execute(std::make_index_sequence<sizeof...(Ts) - 1>{}));
};

template <CombineType C, typename... Packs>  // The first pack P in Packs... could be functor_wrapper<F> if CombineType is Transform or TransformToEnd, in which simple_pack<P>::type is simply P due to the use of detail::identity.
struct combine_packs {
	using Last = typename detail::last<Packs...>::type;  // Use split_last, so that Last is obtained, as well as all the packs except Last.
	static constexpr bool LastPackIsEmpty = detail::is_empty<Last>::value;
	using EmptyPack = std::conditional_t<LastPackIsEmpty, Last, typename detail::sequence_traits<Packs...>::template_empty>;  // Change this if first pack is a Functor
	using pack = combine_packs_h<C, EmptyPack, typename detail::simple_pack<Packs>::type...>;
	using meta = std::conditional_t<LastPackIsEmpty, typename remove_last<pack>::type, pack>;
	using type = typename meta::type;
//	using type = typename combine_packs_h<C, EmptyPack, typename detail::simple_pack<Packs>::type...>::type;  // This original line of mine is incorrect.  We must remove the last pack from Packs... if detail::is_empty<Last>::value == true (since that last pack is empty).
 };

// The following (original) syntax for combine_packs is awkward, because the EmptyPack must always be given even if we want the default no change in container template.
//template <CombineType C, typename EmptyPack, typename... Packs>  // The first pack P in Packs... could be a meta-function struct if CombineType is Transform, in which simple_pack<P>::type is simply P.
//struct combine_packs : combine_packs_h<C, EmptyPack, typename detail::simple_pack<Packs>::type...> {};

// Testing
#include <iostream>

template <int...> struct Z {};
template <int...> struct Q;
template <int...> struct R;
template <std::size_t...> struct I;

template <int A, int B, int C>
struct foo : std::integral_constant<int, A + 2*B + 3*C> {};

int main() {
	std::cout << std::boolalpha << std::is_same<
		combine_packs<Merge, Z<0,1,2,3>, Q<4,5,6>, R<>>::type,
		R<0,1,2,3,4,5,6>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Merge, Z<0,1,2,3>, Z<4,5,6>>::type,
		Z<0,1,2,3,4,5,6>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Merge, Z<0,1,2,3>, Q<4,5,6>, R<7,8>>::type,
		Z<0,1,2,3,4,5,6,7,8>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Merge, std::index_sequence<0,1,2,3>>::type,
		std::index_sequence<0,1,2,3>
	>::value << '\n';  // true
	
	std::cout << std::is_same<
		combine_packs<Merge, std::index_sequence<0,1,2,3>, std::index_sequence<4,5,6>>::type,
		std::index_sequence<0,1,2,3,4,5,6>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Merge, std::index_sequence<0,1,2,3>, std::index_sequence<4,5,6>, std::index_sequence<7,8>, I<>>::type,
		I<0,1,2,3,4,5,6,7,8>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Merge, std::index_sequence<0,1,2,3>, I<4,5,6>, std::index_sequence<7,8>, std::integer_sequence<std::size_t>>::type,
		std::integer_sequence<std::size_t, 0,1,2,3,4,5,6,7,8>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Merge, std::index_sequence<0,1,2,3>, I<4,5,6>, I<7,8>, std::index_sequence<9>>::type,
		std::index_sequence<0,1,2,3,4,5,6,7,8,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Merge, std::make_index_sequence<4>, std::index_sequence<4,5,6>, std::index_sequence<7,8>, std::index_sequence<9>, I<>>::type,
		I<0,1,2,3,4,5,6,7,8,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Merge, I<0,1,2,3>, I<4,5,6>, I<7,8>, I<9>, std::integer_sequence<std::size_t>>::type,
		std::index_sequence<0,1,2,3,4,5,6,7,8,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<FirstFromEach, Z<0,1,2,3>, Z<4,5,6>, Z<7,8>, Z<9>>::type,
		Z<0,4,7,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<FirstFromEach, Z<0,1,2,3>, Q<4,5,6>, Z<7,8>, R<9>>::type,
		Z<0,4,7,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<FirstFromEach, std::make_index_sequence<10>, std::index_sequence<4,5,6>, I<7,8>, std::index_sequence<9>>::type,
		std::index_sequence<0,4,7,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<FirstFromEach, Z<0,1,2,3>, Z<4,5,6>, Z<7,8>, Z<9>, Q<>>::type,
		Q<0,4,7,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<FirstFromEach, std::make_index_sequence<10>, I<4,5,6>, Z<7,8>, std::index_sequence<9>, I<>>::type,
		I<0,4,7,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<FirstFromEach, std::make_index_sequence<10>, R<4,5,6>, Z<7,8>, I<9>, std::integer_sequence<std::size_t>>::type,
		std::index_sequence<0,4,7,9>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Interlace, Z<0,1,2>, Z<3,4,5>, Z<6,7,8>>::type,
		Z<0,3,6,1,4,7,2,5,8>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Interlace, Z<0,1,2>, Q<3,4>, R<5,6,7,8,9,10>>::type,
		Z<0,3,5,1,4,6,2,7,8,9,10>
	>::value << '\n';  // true
	
	std::cout << std::is_same<
		combine_packs<Interlace, std::index_sequence<0,1,2>, I<3,4>, std::index_sequence<5,6,7,8,9,10>>::type,
		std::index_sequence<0,3,5,1,4,6,2,7,8,9,10>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Interlace, std::index_sequence<0,1,2>, std::index_sequence<3,4>, std::index_sequence<5,6,7,8,9,10>, I<>>::type,
		I<0,3,5,1,4,6,2,7,8,9,10>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Transform, functor_wrapper<foo>, Z<2,4,-2,6,2,2,2>, Z<5,10,-5,15>, Z<1,2,-1,3,1>>::type,
		Z<15,30,-15,45>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<TransformToEnd, functor_wrapper<foo>, Z<2,4,-2,6,2,2,2>, Z<5,10,-5,15>, Z<1,2,-1,3,1>>::type,
		Z<15,30,-15,45,5,2,2>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Transform, functor_wrapper<foo>, Q<2,4,-2,6,2,2,2>, Z<5,10,-5,15>, R<1,2,-1,3,1>>::type,
		Q<15,30,-15,45>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<TransformToEnd, functor_wrapper<foo>, Z<2,4,-2,6,2,2,2>, Q<5,10,-5,15>, R<1,2,-1,3,1>, R<>>::type,
		R<15,30,-15,45,5,2,2>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<Transform, functor_wrapper<foo>, std::index_sequence<2,4,-2,6,2,2,2>, std::index_sequence<5,10,-5,15>, std::index_sequence<1,2,-1,3,1>>::type,
		std::index_sequence<15,30,-15,45>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<TransformToEnd, functor_wrapper<foo>, std::index_sequence<2,4,-2,6,2,2,2>, I<5,10,-5,15>, std::index_sequence<1,2,-1,3,1>, I<>>::type,
		I<15,30,-15,45,5,2,2>
	>::value << '\n';  // true

	std::cout << std::is_same<
		combine_packs<TransformToEnd, functor_wrapper<foo>, I<2,4,-2,6,2,2,2>, I<5,10,-5,15>, std::index_sequence<1,2,-1,3,1>, std::integer_sequence<std::size_t>>::type,
		std::index_sequence<15,30,-15,45,5,2,2>
	>::value << '\n';  // true

	std::cin.get();
}