/** Various stuff for working with generic tuples.

A replacement for $(STDMODULE typetuple).

The following symbols from $(D std.typetuple) are publicly imported:
$(UL
	$(LI $(STDREF typetuple, staticIndexOf))
	$(LI $(STDREF typetuple, NoDuplicates))
	$(LI $(STDREF typetuple, MostDerived))
	$(LI $(STDREF typetuple, DerivedToFront))
)
The following symbols from $(D std.typetuple) are superseded:
$(UL
	$(LI $(STDREF typetuple, Reverse), use $(MREF RetroTuple) instead)
	$(LI $(STDREF typetuple, EraseAll), use $(MREF FilterTuple) instead)
	$(LI $(STDREF typetuple, ReplaceAll), use $(MREF MapTuple) instead)
	$(LI $(STDREF typetuple, staticMap), use $(MREF MapTuple) instead)
	$(LI $(STDREF typetuple, anySatisfy), use $(MREF anyTuple) instead)
	$(LI $(STDREF typetuple, allSatisfy), use $(MREF allTuple) instead)
)
The following symbols from $(D std.typetuple) are considered useless:
$(UL
	$(LI $(STDREF typetuple, Erase))
	$(LI $(STDREF typetuple, Replace))
)
$(BOOKTABLE Generic tuple manipulation functions,
	$(TR $(TH Category) $(TH Functions))
	$(TR $(TD Searching)
		$(TD
			$(BTREF anyTuple)
			$(BTREF allTuple)
		)
	)
	$(TR $(TD Creation)
		$(TD
			$(BTREF RetroTuple)
			$(BTREF StrideTuple)
			$(BTREF ChainTuple)
			$(BTREF RoundRobinTuple)
			$(BTREF RadialTuple)
			$(BTREF RepeatTuple)
			$(BTREF ZipTuple)
			$(BTREF iotaTuple)
			$(BTREF IndexedTuple)
			$(BTREF ChunksTuple)
		)
	)
	$(TR $(TD Comparison)
		$(TD
			$(BTREF cmpTuple)
			$(BTREF equalTuple)
		)
	)
	$(TR $(TD Iteration)
		$(TD
			$(BTREF FilterTuple)
			$(BTREF groupTuple)
			$(BTREF JoinTuple)
			$(BTREF MapTuple)
			$(BTREF ReduceTuple)
			$(BTREF UniqTuple)
		)
	)
)

Macros:
BTREF = $(MREF $0)  

Copyright: Denis Shelomovskij 2011-2012

License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).

Authors: Denis Shelomovskij
*/
module unstd.generictuple;


public import std.typetuple:
	staticIndexOf,
	NoDuplicates,
	MostDerived, DerivedToFront;

import std.ascii: isDigit;
import std.algorithm: min, max;
import std.range: StoppingPolicy;
import unstd.traits;
import unstd.templates;


// Note: unittests often can't be used as examples in this module as
// there is no way to place such examples before "Analog..." comment.

/**
Creates a generic tuple out of a sequence of zero or more types, expressions, or aliases.
*/
alias GenericTuple(Args...) = Args;

///
unittest
{
	alias MyTemplate(T) = T[];

	alias MyTuple = GenericTuple!(int, 5, "a string", MyTemplate);

	MyTuple[0] myVar = MyTuple[1]; // same as `int myVar = 5;`
	auto str = MyTuple[2]; // same as `auto str = "a string";`

	alias Template = MyTuple[3];
	static assert(is(Template!int == int[]));
}

/**
Creates a packed generic tuple out of a sequence of zero or more types, expressions, or aliases.

Packed version doesn't alias itself to its content, i.e. it doesn't auto-unpack.
*/
template PackedGenericTuple(Args...)
{
	/// Use this member of to access its content as a generic tuple.
	alias Tuple = Args;

	version(D_Ddoc)
	{
		/**
		Use this member of to access its content as a typetuple.
		Defined if $(D Args) is a typetuple.
		*/
		alias Types = Args;

		/**
		Use this member of to access its content as an expression tuple.
		Defined if $(D Args) is an expression tuple.
		*/
		alias expressions = Args;
	}
	else
	{
		static if(isTypeTuple!Args)
			alias Types = Args;
		else static if(isExpressionTuple!Args)
			alias expressions = Args;
	}

	/// Its content length.
	enum length = Tuple.length;

	/// Detect whether it's empty.
	enum empty = !length;

	/// Convenient equality check template. Same as $(MREF equalTuple).
	enum equals(A...) = equalTuple!(PackedGenericTuple!Args, PackedGenericTuple!A);

	/// Convenient comparison template. Same as $(MREF cmpTuple).
	enum cmp(A...) = cmpTuple!(PackedGenericTuple!Args, PackedGenericTuple!A);
}

///
unittest
{
	alias MyPackedTuple = PackedGenericTuple!(long, 3);

	MyPackedTuple.Tuple[0] myVar = MyPackedTuple.Tuple[1]; // same as `long myVar = 3;`

	alias MyTemplate(alias packed) = packed.Tuple[0][];

	// It is passed as a single template alias parameter:
	static assert(is(MyTemplate!MyPackedTuple == long[]));
}

unittest
{
	static assert(isPackedTuple!(PackedGenericTuple!()));

	static assert(is(PackedGenericTuple!int.Types == TypeTuple!int));
	static assert(PackedGenericTuple!3.expressions[0] == 3);
}


/**
Creates a typetuple out of a sequence of zero or more types.
Same as $(D GenericTuple), except it contains only types.
*/
template TypeTuple(Types...) if(isTypeTuple!Types)
{
	alias TypeTuple = Types;
}

///
unittest
{
	alias IntDouble = TypeTuple!(int, double);

	int foo(IntDouble args)  // same as `int foo(int, double)`
	{
		return args[0] + cast(int) args[1];
	}

	alias IntDoubleChar = TypeTuple!(int, double, char);
	static assert(is(TypeTuple!(IntDouble, char) == IntDoubleChar));
	static assert(is(IntDoubleChar[0 .. 2] == IntDouble));


	version(none)
	alias BadTypeTuple = TypeTuple!(int, 5); // error: not a type tuple
}

unittest
{
	static assert(TypeTuple!().length == 0);
	static assert(!__traits(compiles, TypeTuple!(int, 5)));

	static assert(is(TypeTuple!(int, TypeTuple!()) == TypeTuple!int));
	static assert(is(TypeTuple!(int, TypeTuple!char) == TypeTuple!(int, char)));
	static assert(is(TypeTuple!(int, TypeTuple!(char, bool)) == TypeTuple!(int, char, bool)));
}


/**
Creates a packed typetuple out of a sequence of zero or more types.
Same as $(D PackedGenericTuple), except it contains only types.
*/
template PackedTypeTuple(T...) if(isTypeTuple!T)
{
	alias PackedTypeTuple = PackedGenericTuple!T;
}

unittest
{
	static assert(isPackedTuple!(PackedTypeTuple!()));
	static assert(is(PackedTypeTuple!int.Types == TypeTuple!int));
}


/**
Creates an expression tuple out of a sequence of zero or more expressions.
Same as $(D GenericTuple), except it contains only expressions.
*/
template expressionTuple(expressions...) if(isExpressionTuple!expressions)
{
	alias expressionTuple = expressions;
}

///
unittest
{
	alias expressions = expressionTuple!(5, 'c', "str");

	typeof(expressions[0]) myVar = expressions[1]; // same as `int myVar = 5;`
	auto str = expressions[2]; // same as `auto str = "a string";`

	void foo(out typeof(expressions[0 .. 2]) args)  // same as `int foo(out int, out char)`
	{
		args[0] = expressions[0] * 2; // same as `5 * 2`
		args[1] = expressions[1] + 1; // same as `'c' + 1`
	}

	void main()
	{
		int i;
		char c;
		foo(i, c);
		assert(i == 10 && c == 'd');
	}

	version(none)
	alias badExpressionTuple = expressionTuple!(int, 5); // error: not an expression tuple
}

unittest
{
	static assert(expressionTuple!().length == 0);
	static assert(expressionTuple!(5, 'c', "str") == expressionTuple!(5, 'c', "str"));
	static assert(!__traits(compiles, expressionTuple!(int, 5)));
	static assert(!__traits(compiles, expressionTuple!void));
}


/**
Creates a packed expression tuple out of a sequence of zero or more expressions.
Same as $(D PackedGenericTuple), except it contains only expressions.
*/
template packedExpressionTuple(expr...) if(isExpressionTuple!expr)
{
	alias packedExpressionTuple = PackedGenericTuple!expr;
}

unittest
{
	static assert(isPackedTuple!(packedExpressionTuple!()));
	static assert(packedExpressionTuple!3.expressions[0] == 3);
}


/**
Creates a generic tuple comprised of elemetns of $(D A) in reverse order.

Applying RetroTuple twice to the same generic tuple equals to
the original generic tuple.

Example:
---
static assert(is(RetroTuple!(int, bool, long) == TypeTuple!(long, bool, int)));
static assert(PackedGenericTuple!(RetroTuple!(1, bool, "x")).equals!("x", bool, 1));
---

Analog of $(STDREF range, retro) for generic tuples.
*/
template RetroTuple(A...)
{
	static if (A.length == 0)
		alias RetroTuple = GenericTuple!();
	else
		alias RetroTuple = GenericTuple!(.RetroTuple!(A[1 .. $]), A[0]);
}

unittest
{
	static assert(is(RetroTuple!() == GenericTuple!()));
	static assert(is(RetroTuple!int == TypeTuple!int));
	static assert(is(RetroTuple!(int, bool, long) == TypeTuple!(long, bool, int)));
	static assert(PackedGenericTuple!(RetroTuple!(1, bool, "x")).equals!("x", bool, 1));
}


/**
Creates a generic tuple comprised of elemetns of $(D A) taken with stride $(D n).

Applying StrideTuple twice to the same generic tuple equals to applying
StrideTuple with a step that is the product of the two applications.

Example:
---
static assert(is(StrideTuple!(2, ubyte, byte, uint, int, ulong, long) == TypeTuple!(ubyte, uint, ulong)));
static assert(StrideTuple!(3, iota) == expressionTuple!(1, 4, 7, 10));
---

Analog of $(STDREF range, stride) for generic tuples
except $(D n) is the first argument.
*/
template StrideTuple(size_t n, A...)
	if(n > 0)
{
	static if(A.length)
		alias StrideTuple = GenericTuple!(A[0], StrideTuple!(n, A[min(n, $) .. $]));
	else
		alias StrideTuple = GenericTuple!();
}

unittest
{
	static assert(is(StrideTuple!1 == GenericTuple!()));
	static assert(is(StrideTuple!(2, ubyte, byte, uint, int, ulong, long) == TypeTuple!(ubyte, uint, ulong)));
	alias iota = iotaTuple!(1, 11);
	static assert(StrideTuple!(1, iota) == iota);
	static assert(StrideTuple!(2, iota) == expressionTuple!(1, 3, 5, 7, 9));
	static assert(StrideTuple!(3, iota) == expressionTuple!(1, 4, 7, 10));
	static assert(StrideTuple!(4, iota) == expressionTuple!(1, 5, 9));
}


/**
Creates a generic tuple comprised of all elemetns of packed generic tuples
$(D packedTuples) in sequence.

Example:
---
alias chain = ChainTuple!(packedExpressionTuple!(1, 2, 3), packedExpressionTuple!(4, 5));
static assert(chain == expressionTuple!(1, 2, 3, 4, 5));
---

Analog of $(STDREF range, chain) for generic tuples.
*/
template ChainTuple(packedTuples...)
	if(packedTuples.length && allTuple!(isPackedTuple, packedTuples))
{
	// Can't use UnaryTemplate!`A.Tuple` because of Issue 9017
	alias Func(alias packedTuple) = packedTuple.Tuple;
	alias ChainTuple = MapTuple!(Func, packedTuples);
}

unittest
{
	alias chain = ChainTuple!(packedExpressionTuple!(1, 2, 3, 4), packedExpressionTuple!(5, 6), packedExpressionTuple!(), packedExpressionTuple!7);
	static assert(chain == expressionTuple!(1, 2, 3, 4, 5, 6, 7));
}


/**
Creates a generic tuple comprised of all elemetns of packed generic tuples
$(D packedTuples) in an order by analogy with
$(HTTP en.wikipedia.org/wiki/Round-robin_scheduling, Round-robin scheduling).

Example:
---
alias roundRobin = RoundRobinTuple!(packedExpressionTuple!(1, 2, 3), packedExpressionTuple!(10, 20, 30, 40));
static assert(roundRobin == expressionTuple!(1, 10, 2, 20, 3, 30, 40));
---

Analog of $(STDREF range, roundRobin) for generic tuples.
*/
template RoundRobinTuple(packedTuples...)
	if(packedTuples.length && allTuple!(isPackedTuple, packedTuples))
{
	struct _Empty;
	enum pred(alias A) = !is(A == _Empty);
	alias RoundRobinTuple = FilterTuple!(pred, ChainTuple!(ZipTuple!(StoppingPolicy.longest, GenericTuple!_Empty, packedTuples)));
}

unittest
{
	alias roundRobin = RoundRobinTuple!(packedExpressionTuple!(1, 2, 3), packedExpressionTuple!(10, 20, 30, 40));
	static assert(roundRobin == expressionTuple!(1, 10, 2, 20, 3, 30, 40));
}


/**
Creates a generic tuple comprised of all elemetns of $(D A) which are teken
starting from a given point and progressively extending left and right
from that point. If $(D RadialTupleMiddle) is used or $(D startingIndex)
is $(D -1) it is assumed that no initial point is given and iteration
starts from the middle of $(D A).

Example:
---
static assert(RadialTuple!(-1, 1, 2, 3, 4, 5) == expressionTuple!(3, 4, 2, 5, 1));
static assert(RadialTuple!( 1, 1, 2, 3, 4, 5) == expressionTuple!(2, 3, 1, 4, 5));
---

Analog of $(STDREF range, radial) for generic tuples
except $(D startingIndex) is the first argument and
there is no overload without it.
*/
template RadialTuple(size_t startingIndex, A...)
{
	enum i = (startingIndex == -1 ? (A.length - !!A.length) / 2 : startingIndex) + !!A.length;
	alias RadialTuple = RoundRobinTuple!(PackedGenericTuple!(RetroTuple!(A[0 .. i])), PackedGenericTuple!(A[i .. $]));
}

/// ditto
alias RadialTupleMiddle(A...) = RadialTuple!(-1, A);

unittest
{
	static assert(RadialTupleMiddle!(1) == expressionTuple!1);
	static assert(RadialTupleMiddle!(1, 2) == expressionTuple!(1, 2));
	static assert(RadialTupleMiddle!(1, 2, 3) == expressionTuple!(2, 3, 1));
	static assert(RadialTupleMiddle!(1, 2, 3, 4) == expressionTuple!(2, 3, 1, 4));
	static assert(RadialTupleMiddle!(1, 2, 3, 4, 5) == expressionTuple!(3, 4, 2, 5, 1));
	static assert(RadialTupleMiddle!(1, 2, 3, 4, 5, 6) == expressionTuple!(3, 4, 2, 5, 1, 6));
	static assert(RadialTuple!(1, 1, 2, 3, 4, 5) == expressionTuple!(2, 3, 1, 4, 5));
}


/**
Repeats $(D A) $(D n) times.

Example:
---
static assert(is(RepeatTuple!(2, int) == TypeTuple!(int, int)));
static assert(RepeatTuple!(4, 5) == expressionTuple!(5, 5, 5, 5));
---

Analog of $(STDREF array, replicate) and $(STDREF range, repeat) for generic tuples
except $(D n) is the first argument and there is no overload
without it as tuples can't be infinite.
Also it repeats a generic tuple, not only one value.
*/
template RepeatTuple(size_t n, A...)
{
	static if(n)
		alias RepeatTuple = GenericTuple!(A, RepeatTuple!(n - 1, A));
	else
		alias RepeatTuple = GenericTuple!();
}

unittest
{
	static assert(is(RepeatTuple!(2, int) == TypeTuple!(int, int)));
	static assert(RepeatTuple!(4, 5) == expressionTuple!(5, 5, 5, 5));
}


/**
Creates a generic tuple comprised of packed generic tuples comprised of
elemetns of packed generic tuples $(D packedTuples) taken in lockstep.

If $(D stoppingPolicy) is $(D StoppingPolicy.longest) and a tuple is finished
in a lockstep iteration then $(D empty) will be taken.

Example:
---
alias packed1 = packedExpressionTuple!(1, 2, 3);
alias packed2 = PackedTypeTuple!(short, int, long);
alias zip = ZipTuple!(packed1, packed2);

static assert(zip[0].equals!(1, short));
static assert(zip[1].equals!(2, int));
static assert(zip[2].equals!(3, long))
---

Analog of $(STDREF range, zip) for generic tuples
except $(D empty) value must be explicitly specified
for $(D StoppingPolicy.longest).
*/
template ZipTuple(StoppingPolicy stoppingPolicy : StoppingPolicy.longest, alias empty, packedTuples...)
{
	alias ZipTuple = ZipTupleImpl!(stoppingPolicy, PackedGenericTuple!empty, packedTuples);
}

/// ditto
template ZipTuple(StoppingPolicy stoppingPolicy : StoppingPolicy.longest, empty, packedTuples...)
{
	alias ZipTuple = ZipTupleImpl!(stoppingPolicy, PackedGenericTuple!empty, packedTuples);
}

/// ditto
template ZipTuple(StoppingPolicy stoppingPolicy, packedTuples...)
	if(stoppingPolicy != StoppingPolicy.longest) // probably a compiler @@@BUG@@@ workaround
{
	alias ZipTuple = ZipTupleImpl!(stoppingPolicy, PackedGenericTuple!void, packedTuples);
}

/// ditto
template ZipTuple(packedTuples...)
	if(packedTuples.length && allTuple!(isPackedTuple, packedTuples)) // probably a compiler @@@BUG@@@ workaround
{
	alias ZipTuple = ZipTuple!(StoppingPolicy.shortest, packedTuples);
}

private template ZipTupleImpl(StoppingPolicy stoppingPolicy, alias default_, packedTuples...)
	if(packedTuples.length && allTuple!(isPackedTuple, default_, packedTuples) && default_.length == 1)
{
	alias lengths = MapTuple!(`A.length`, packedTuples);

	static if(stoppingPolicy == StoppingPolicy.requireSameLength)
		static assert(allTuple!(BindTemplate!(isSame, lengths[0], arg!0), lengths),
			"Inequal-length packed tuples passed to ZipTuple(StoppingPolicy.requireSameLength, ...)");

	template Impl(size_t n, packedTuples...)
	{
		static if(n)
		{
			template tupleFrontOrDefault(alias packedTuple)
			{
				static if(!packedTuple.empty)
					alias tupleFrontOrDefault = packedTuple.Tuple[0 .. 1];
				else
					alias tupleFrontOrDefault = default_.Tuple;
			}
			alias Impl = GenericTuple!(PackedGenericTuple!(MapTuple!(tupleFrontOrDefault, packedTuples)),
				Impl!(n - 1, MapTuple!(`PackedGenericTuple!(A.Tuple[!A.empty .. $])`, packedTuples)));
		}
		else
			alias Impl = GenericTuple!();
	}
	static if(packedTuples.length == 1 || stoppingPolicy == StoppingPolicy.requireSameLength)
		enum length = lengths[0];
	else
		enum length = GenericTuple!(min, max)
			[stoppingPolicy == StoppingPolicy.longest](lengths);

	alias ZipTupleImpl = Impl!(length, packedTuples);
}

unittest
{
	alias packed1 = packedExpressionTuple!(1, 2, 3);
	alias packed2 = PackedTypeTuple!(short, int, long);
	alias zip = ZipTuple!(packed1, packed2);

	static assert(zip[0].equals!(1, short));
	static assert(zip[1].equals!(2, int));
	static assert(zip[2].equals!(3, long));
}

unittest
{
	alias packedIota5 = packedExpressionTuple!(iotaTuple!5);
	alias packedIota16 = packedExpressionTuple!(iotaTuple!(1, 6));
	alias packedIota14 = packedExpressionTuple!(iotaTuple!(1, 4));
	alias packedIota18 = packedExpressionTuple!(iotaTuple!(1, 8));

	void test(size_t length, size_t filledLength, size_t longerIdx, zip...)()
	{
		static assert(zip.length == length);
		foreach (i, e; zip)
			static assert(e.Tuple[0] == (i < filledLength || longerIdx == 0 ? i : -2) &&
				e.Tuple[1] == (i < filledLength || longerIdx == 1 ? i + 1 : -3));
	}

	with(StoppingPolicy) foreach(stoppingPolicy; expressionTuple!(shortest, longest, requireSameLength))
	{
		static if(stoppingPolicy == longest)
			alias def = void;
		else
			alias def = expressionTuple!();

		alias zip = ZipTuple!(stoppingPolicy, def, packedIota5, packedIota16);
		test!(5, 5, -1, zip)();
	}

	static assert(!__traits(compiles, ZipTuple!(StoppingPolicy.requireSameLength, packedIota5, packedIota14)));
	static assert(!__traits(compiles, ZipTuple!(StoppingPolicy.requireSameLength, packedIota5, packedIota18)));

	test!(3, 3, -1, ZipTuple!(packedIota5, packedIota14))();
	test!(5, 5, -1, ZipTuple!(packedIota5, packedIota18))();

	test!(5, 3, 0, ZipTuple!(StoppingPolicy.longest, -3, packedIota5, packedIota14))();
	test!(7, 5, 1, ZipTuple!(StoppingPolicy.longest, -2, packedIota5, packedIota18))();
}


/**
Returns expression tuple with elements going through the numbers $(D begin), $(D begin +
step), $(D begin + 2 * step), $(D ...), up to and excluding $(D end).
The two-arguments version has $(D step = 1).
The one-argument version also has $(D begin = 0).
If $(D begin < end && step < 0) or $(D begin > end && step > 0) or $(D begin == end),
then an empty tuple is returned.

Example:
---
int res;
foreach(i; iotaTuple!5) // same as res += foo!1(); res += foo!3();
	static if(i & 1)
		res += foo!i();
---

Tip:
This is a convenient way to create a CT analog of
$(HTTP dlang.org/statement.html#ForeachRangeStatement, Foreach Range Statement).

Analog of $(STDREF range, iota) for generic tuples.
*/
alias iotaTuple(alias begin, alias end, alias step) =
	iotaTupleImpl!(CommonType!(typeof(begin), typeof(end), typeof(step)), begin, end, step);

/// ditto
alias iotaTuple(alias begin, alias end) =
	iotaTupleImpl!(CommonType!(typeof(begin), typeof(end)), begin, end, 1);

/// ditto
alias iotaTuple(alias end) =
	iotaTupleImpl!(typeof(end), 0, end, 1);

private template iotaTupleImpl(T, T begin, T end, T step)
	if(isIntegral!T || isFloatingPoint!T && step)
{
	static if(begin < end && step < 0 || begin > end && step > 0 || begin == end)
		alias iotaTupleImpl = expressionTuple!();
	else static if(step)
		alias iotaTupleImpl = expressionTuple!(begin, iotaTupleImpl!(T, begin + step, end, step));
	else
		static assert(0, "iotaTuple: `step` can't be zero for nonequal `begin` and `end`");
}

unittest
{
	static assert(iotaTuple!0.length == 0);
	static assert(iotaTuple!(10, 1).length == 0);
	static assert(iotaTuple!(1, 10, -1).length == 0);
	static assert(iotaTuple!(2, 2, 0).length == 0);
	static assert(!__traits(compiles, iotaTuple!(1, 2, 0)));

	static assert(iotaTuple!1 == expressionTuple!0);
	static assert(iotaTuple!3 == expressionTuple!(0, 1, 2));
	static assert(iotaTuple!(1.0, 3) == expressionTuple!(1.0, 2.0));
	static assert(iotaTuple!(1, 3.1f) == expressionTuple!(1.0, 2.0, 3.0));
	static assert(iotaTuple!(3, 0, -1) == expressionTuple!(3, 2, 1));
	static assert(iotaTuple!(3, 2, -.5) == expressionTuple!(3.0, 2.5));
}


/**
Creates a generic tuple comprised of elemetns of packed generic tuple
$(D packedSourceTuple) reordered according to packed expression tuple
$(D packedIndicesTuple). $(D packedIndicesTuple) may include only a subset
of the elements of $(D packedSourceTuple) and may also repeat elements.

Example:
---
alias indexed = IndexedTuple!(PackedTypeTuple!(short, int, long, double),
                              packedExpressionTuple!(1, 0, 2, 2));
static assert(is(indexed == TypeTuple!(int, short, long, long)));
---

Analog of $(STDREF range, indexed) for generic tuples.
*/
template IndexedTuple(alias packedSourceTuple, alias packedIndicesTuple)
	if(isPackedTuple!packedSourceTuple && isPackedTuple!packedIndicesTuple)
{
	template Func(A...) if(A.length == 1)
	{ alias Func = packedSourceTuple.Tuple[A[0] .. A[0] + 1]; }
	alias IndexedTuple = MapTuple!(Func, packedIndicesTuple.Tuple);
}

unittest
{
	alias indexed = IndexedTuple!(PackedTypeTuple!(short, int, long, double), packedExpressionTuple!(1, 0, 2, 2));
	static assert(is(indexed == TypeTuple!(int, short, long, long)));

	alias indexed2 = IndexedTuple!(packedExpressionTuple!(1, 2, 3, 4, 5), packedExpressionTuple!(4, 3, 1, 2, 0, 4));
	static assert(indexed2 == expressionTuple!(5, 4, 2, 3, 1, 5));
}


/**
Creates a generic tuple comprised of packed generic tuples comprised of
fixed-sized chunks of size $(D chunkSize) of $(D A).

If $(D A.length) is not evenly divisible by $(D chunkSize), the last
packed generic tuple will contain fewer than $(D chunkSize) elements.

Example:
---
alias chunks = ChunksTuple!(4,  1, 2, 3, 4, 5, 6, byte, short, int, long);
static assert(chunks[0].equals!(1, 2, 3, 4));
static assert(chunks[1].equals!(5, 6, byte, short));
static assert(chunks[2].equals!(int, long));
---

Analog of $(STDREF range, chunks) for generic tuples
except $(D chunkSize) is the first argument.
*/
template ChunksTuple(size_t chunkSize, A...)
{
	static if(A.length > chunkSize)
		alias ChunksTuple = GenericTuple!(PackedGenericTuple!(A[0 .. chunkSize]),
			ChunksTuple!(chunkSize, A[chunkSize .. $]));
	else
		alias ChunksTuple = GenericTuple!(PackedGenericTuple!A);
}

unittest
{
	alias chunks = ChunksTuple!(4,  1, 2, 3, 4, 5, 6, byte, short, int, long);
	static assert(chunks[0].equals!(1, 2, 3, 4));
	static assert(chunks[1].equals!(5, 6, byte, short));
	static assert(chunks[2].equals!(int, long));
}


/**
Performs $(HTTP en.wikipedia.org/wiki/Three-way_comparison, three-way
lexicographical comparison) on two packed generic tuples
according to predicate $(D pred).

Iterating $(D packedTuple1) and $(D packedTuple2) in lockstep, cmpTuple
compares each element $(D A1) of $(D packedTuple1) with the corresponding
element $(D A2) in $(D packedTuple2).
If $(D Inst!(binaryPred!pred, A1, A2)), $(D cmp) returns a negative value.
If $(D Inst!(binaryPred!pred, A2, A1)), $(D cmp) returns a positive value.
If one of the tuples has been finished, $(D cmp) returns a negative value
if $(D packedTuple1) has fewer elements than $(D packedTuple2), a positive
value if $(D packedTuple1) has more elements than $(D packedTuple2), and
$(D 0) if the tuples have the same number of elements.

Example:
---
static assert(cmpTuple!(packedExpressionTuple!0, packedExpressionTuple!0) == 0);
static assert(cmpTuple!(packedExpressionTuple!"a", packedExpressionTuple!"ab") < 0);
static assert(cmpTuple!(`T.sizeof < U.sizeof`, PackedTypeTuple!int, PackedTypeTuple!long) < 0);
---

Analog of $(STDREF algorithm, cmp) for generic tuples.
*/
template cmpTuple(alias pred, alias packedTuple1, alias packedTuple2)
	if(isPackedTuple!packedTuple1 && isPackedTuple!packedTuple2)
{
	alias predTemplate = binaryPred!pred;

	static if (packedTuple1.empty)
		enum cmpTuple = -cast(int) !packedTuple2.empty;
	else static if (packedTuple2.empty)
		enum cmpTuple = cast(int) !packedTuple1.empty;
	else static if (predTemplate!(packedTuple1.Tuple[0], packedTuple2.Tuple[0]))
		enum cmpTuple = -1;
	else static if (predTemplate!(packedTuple2.Tuple[0], packedTuple1.Tuple[0]))
		enum cmpTuple = 1;
	else
		enum cmpTuple = cmpTuple!(predTemplate, PackedGenericTuple!(packedTuple1.Tuple[1 .. $]), PackedGenericTuple!(packedTuple2.Tuple[1 .. $]));
}

/// ditto
enum cmpTuple(alias packedTuple1, alias packedTuple2) =
	cmpTuple!(`a < b`, packedTuple1, packedTuple2);

unittest
{
	static assert(cmpTuple!(PackedGenericTuple!(), PackedGenericTuple!()) == 0);
	static assert(cmpTuple!(packedExpressionTuple!0, packedExpressionTuple!0) == 0);
	static assert(cmpTuple!(packedExpressionTuple!0, packedExpressionTuple!1) < 0);
	static assert(cmpTuple!(packedExpressionTuple!0, packedExpressionTuple!(0, 0)) < 0);
	static assert(cmpTuple!(packedExpressionTuple!(0, 0), packedExpressionTuple!0) > 0);
	static assert(cmpTuple!(packedExpressionTuple!1, packedExpressionTuple!(0, 0)) > 0);

	static assert(cmpTuple!(packedExpressionTuple!"a", packedExpressionTuple!"a") == 0);
	static assert(cmpTuple!(packedExpressionTuple!"a", packedExpressionTuple!"ab") < 0);
	static assert(cmpTuple!(packedExpressionTuple!"b", packedExpressionTuple!"ab") > 0);

	static assert(cmpTuple!(`T.sizeof < U.sizeof`, PackedTypeTuple!int, PackedTypeTuple!long) < 0);
}


/**
Detect whether two packed generic tuples $(D packedTuple1) and $(D packedTuple2)
elements are equal according to binary predicate $(D pred).

$(D isSame) is used if no predicacte specified.

Example:
---
static assert( equalTuple!(packedExpressionTuple!(0, 1), packedExpressionTuple!(iotaTuple!2)));
static assert( equalTuple!(PackedGenericTuple!(int, "a"), PackedGenericTuple!(int, "a")));

static assert( equalTuple!(`true`, packedExpressionTuple!1, PackedTypeTuple!int));
static assert(!equalTuple!(`true`, packedExpressionTuple!1, packedExpressionTuple!()));
---

Analog of $(STDREF algorithm, equal) for generic tuples.
*/
template equalTuple(alias pred, alias packedTuple1, alias packedTuple2)
	if(isPackedTuple!packedTuple1 && isPackedTuple!packedTuple2)
{
	alias predTemplate = binaryPred!pred;

	template instForPackedTuple(alias packedTuple)
		if(isPackedTuple!packedTuple && packedTuple.length == 2)
	{
		enum instForPackedTuple = predTemplate!(packedTuple.Tuple);
	}

	static if(packedTuple1.length == packedTuple2.length)
		enum equalTuple = allTuple!(instForPackedTuple, ZipTuple!(packedTuple1, packedTuple2));
	else
		enum equalTuple = false;
}

/// ditto
enum equalTuple(alias packedTuple1, alias packedTuple2) =
	equalTuple!(isSame, packedTuple1, packedTuple2);

unittest
{
	static assert( equalTuple!(PackedGenericTuple!(), PackedGenericTuple!()));
	static assert( equalTuple!(packedExpressionTuple!0, packedExpressionTuple!0));
	static assert(!equalTuple!(packedExpressionTuple!0, PackedTypeTuple!int));
	static assert(!equalTuple!(packedExpressionTuple!0, packedExpressionTuple!(0, 1)));
	static assert( equalTuple!(packedExpressionTuple!(0, 1), packedExpressionTuple!(iotaTuple!2)));
	static assert( equalTuple!(PackedGenericTuple!(int, "a"), PackedGenericTuple!(int, "a")));

	static assert(!equalTuple!(`true`, packedExpressionTuple!1, packedExpressionTuple!()));
	static assert( equalTuple!(`true`, packedExpressionTuple!1, PackedTypeTuple!int));
}


/**
Creates a generic tuple comprised of elemetns of $(D A) for which a unary
predicate $(D pred) is $(D true).

Example:
----
import std.traits;

static assert(is(FilterTuple!(isNumeric, int, void, immutable short, char) ==
              TypeTuple!(int, immutable short)));

static assert(is(FilterTuple!(`__traits(isUnsigned, T)`, int, size_t, void, ushort, char) ==
              TypeTuple!(size_t, ushort, char)));
----

Analog of $(STDREF algorithm, filter) for generic tuples.
*/
template FilterTuple(alias pred, A...)
{
	alias PredTemplate = UnaryTemplate!pred;

	template func(A...) if(A.length == 1)
	{ alias func = A[0 .. PredTemplate!(A[0])]; }

	alias FilterTuple = MapTuple!(func, A);
}

unittest
{
	import std.traits;

	static assert(is(FilterTuple!(isNumeric, int, size_t, void, immutable short, char) ==
		TypeTuple!(int, size_t, immutable short)));

	static assert(is(FilterTuple!(`__traits(isUnsigned, T)`, int, size_t, void, immutable ushort, char) ==
		TypeTuple!(size_t, immutable ushort, char)));
}


/**
Similarly to $(MREF UniqTuple), creates a generic tuple comprised of packed generic tuples comprised of unique
consecutive elemetns of $(D A) and counts of equivalent elements seen.

Equivalence of elements is assessed by using a binary predicate $(D pred).

Example:
----
alias tuple = GenericTuple!(1, 2, 2, 2, "x", "x", int, 1, 1);

alias group = groupTuple!(isSame, tuple);
static assert(group.length == 5);
static assert(group[0].equals!(1, 1));
static assert(group[1].equals!(2, 3));
static assert(group[2].equals!("x", 2));
static assert(group[3].equals!(int, 1));
static assert(group[4].equals!(1, 2));

alias group2 = groupTuple!(notTemplate!isSame, tuple);
static assert(group2.length == 3);
static assert(group2[0].equals!(1, 7));
static assert(group2[1].equals!(1, 1));
static assert(group2[2].equals!(1, 1));
----

Analog of $(STDREF algorithm, group) for generic tuples
except $(D pred) must be explicitly specified.
*/
template groupTuple(alias pred, A...)
{
	alias predTemplate = binaryPred!pred;

	template impl(size_t count, A...) if(A.length >= 1)
	{
		static if(A.length == 1 || !predTemplate!(A[0], A[1]))
		{
			alias curr = PackedGenericTuple!(A[0], count);

			static if(A.length == 1)
				alias impl = GenericTuple!(curr);
			else
				alias impl = GenericTuple!(curr, impl!(1, A[1], A[2 .. $]));
		}
		else
			alias impl = impl!(count + 1, A[0], A[2 .. $]);
	}

	static if(A.length)
		alias groupTuple = impl!(1, A);
	else
		alias groupTuple = GenericTuple!();
}

unittest
{
	static assert(groupTuple!isSame.length == 0);

	alias tuple = GenericTuple!(1, 2, 2, 2, "x", "x", int, 1, 1);

	alias group = groupTuple!(isSame, tuple);
	static assert(group.length == 5);
	static assert(group[0].equals!(1, 1));
	static assert(group[1].equals!(2, 3));
	static assert(group[2].equals!("x", 2));
	static assert(group[3].equals!(int, 1));
	static assert(group[4].equals!(1, 2));

	alias group2 = groupTuple!(notTemplate!isSame, tuple);
	static assert(group2.length == 3);
	static assert(group2[0].equals!(1, 7));
	static assert(group2[1].equals!(1, 1));
	static assert(group2[2].equals!(1, 1));
}


/**
Creates a generic tuple comprised of packed generic tuples $(D packedTuples)
generic tuples joined together using packed generic tuple $(D packedSeparatorTuple)
as a separator.

Example:
----
alias sep = packedExpressionTuple!"+";
alias part1 = PackedTypeTuple!(void, int);
alias part2 = packedExpressionTuple!0;
static assert(PackedGenericTuple!(JoinTuple!(sep, part1, part2)).equals!(void, int, "+", 0));
----

Analog of $(STDREF array, join) and $(STDREF algorithm, joiner) for generic tuples.
*/
template JoinTuple(alias packedSeparatorTuple, packedTuples...)
	if(allTuple!(isPackedTuple, packedSeparatorTuple, packedTuples))
{
	alias Prefix(alias packedTuple) = ChainTuple!(packedSeparatorTuple, packedTuple);

	static if(packedTuples.length)
		alias JoinTuple = GenericTuple!(packedTuples[0].Tuple, MapTuple!(Prefix, packedTuples[1 .. $]));
	else
		alias JoinTuple = GenericTuple!();
}

unittest
{
	alias sep = packedExpressionTuple!"+";
	alias part1 = PackedTypeTuple!(void, int);
	alias part2 = packedExpressionTuple!0;

	static assert(JoinTuple!sep.length == 0);
	static assert(is(JoinTuple!(sep, part1) == TypeTuple!(void, int)));
	static assert(PackedGenericTuple!(JoinTuple!(sep, part1, part2)).equals!(void, int, "+", 0));
}


/**
Creates a generic tuple comprised of results of applying unary
template $(D Func) to elemetns of $(D A) consecutively.

Example:
---
alias squares = MapTuple!(`a * a`, iotaTuple!4);
static assert(squares == expressionTuple!(0, 1, 4, 9));

static assert(is(MapTuple!(`T[]`, int, long) == TypeTuple!(int[], long[])));
---

Analog of $(STDREF algorithm, map) for generic tuples
except $(D Func) can return any count of elements.
*/
template MapTuple(alias Func, A...)
{
	alias FuncTemplate = UnaryTemplate!Func;

	static if (A.length)
		alias MapTuple = GenericTuple!(FuncTemplate!(A[0]), MapTuple!(FuncTemplate, A[1 .. $]));
	else
		alias MapTuple = GenericTuple!();
}

unittest
{
	static assert(MapTuple!`1`.length == 0);
	static assert(MapTuple!(`1`, const int) == expressionTuple!1);
	static assert(is(MapTuple!(Unqual, int, immutable int) == TypeTuple!(int, int)));
	static assert(is(MapTuple!(`T[]`, int, long) == TypeTuple!(int[], long[])));
	alias squares = MapTuple!(`a * a`, iotaTuple!4);
	static assert(squares == expressionTuple!(0, 1, 4, 9));
}


/**
The instantiation of $(D ReduceTuple!(Func, init, A)) first lets $(D result)
be $(D init). Then, for each element $(D x) in $(D A) sequentially, it lets $(D result)
be $(D Inst!(BinaryTemplate!Func, result, x)). Finally, $(D result) is returned.

Example:
----
static assert(ReduceTuple!(`a + U.sizeof`, 0, bool, short, int) == 1 + 2 + 4);
static assert(is(ReduceTuple!(`Select!(T.sizeof > U.sizeof, T, U)`, void, bool, long, int) == long));
----

Analog of $(STDREF algorithm, reduce) for generic tuples
except there is no overload with multiple functions.
*/
template ReduceTuple(alias Func, alias init, A...)
{
	alias Init = init;
	mixin ReduceTupleImpl;
	alias ReduceTuple = Res;
}

template ReduceTuple(alias Func, Init, A...)
{
	mixin ReduceTupleImpl;
	alias ReduceTuple = Res;
}

private mixin template ReduceTupleImpl()
{
	alias FuncTemplate = BinaryTemplate!Func;

	static if(A.length)
		alias Res = .ReduceTuple!(FuncTemplate, FuncTemplate!(Init, A[0]), A[1 .. $]);
	else
		alias Res = Init;
}

unittest
{
	static assert(is(ReduceTuple!(`true`, void) == void));
	static assert(ReduceTuple!(`true`, 0) == 0);
	static assert(ReduceTuple!(`true`, void, int) == true);
	static assert(ReduceTuple!(`a + U.sizeof`, 0, bool, short, int) == 1 + 2 + 4);
	static assert(is(ReduceTuple!(`Select!(T.sizeof > U.sizeof, T, U)`, void, bool, long, int) == long));
}


/**
Creates a generic tuple comprised of unique consecutive elemetns of $(D A).

Equivalence of elements is assessed by using a binary predicate $(D pred).

Example:
----
alias expr = expressionTuple!(1, 2, 2, 2, 3, 3, 4, 1, 1);
static assert(UniqTuple!(`a == b`, expr) == expressionTuple!(1, 2, 3, 4, 1));
static assert(UniqTuple!(`a != b`, expr) == expressionTuple!(1, 1, 1));
----

Analog of $(STDREF algorithm, uniq) for generic tuples
except $(D pred) must be explicitly specified.
*/
template UniqTuple(alias pred, A...)
{
	alias predTemplate = binaryPred!pred;

	template Impl(A...) if(A.length >= 1)
	{
		static if(A.length >= 2)
		{
			static if(predTemplate!(A[0], A[1]))
				alias Impl = Impl!(A[0], A[2 .. $]);
			else
				alias Impl = GenericTuple!(A[1], Impl!(A[1], A[2 .. $]));
		}
		else
			alias Impl = A[1 .. $];
	}

	static if(A.length <= 1)
		alias UniqTuple = A;
	else
		alias UniqTuple = GenericTuple!(A[0], Impl!(A[0], A[1 .. $]));
}

unittest
{
	alias expr = expressionTuple!(1, 2, 2, 2, 3, 3, 4, 1, 1);
	static assert(UniqTuple!(`a == b`, expr) == expressionTuple!(1, 2, 3, 4, 1));
	static assert(UniqTuple!(`a != b`, expr) == expressionTuple!(1, 1, 1));
}


/**
Detect whether a generic tuple $(D A) contains an element
satisfying the predicate $(D pred).

Example:
----
static assert(!anyTuple!(`true`));
static assert( anyTuple!(`isIntegral!T`, float, int));
static assert(!anyTuple!(`a < 2`, 2, 3));
----

Analog of $(STDREF algorithm, any) for generic tuples
except $(D pred) must be explicitly specified.
*/
template anyTuple(alias pred, A...)
{
	alias predTemplate = unaryPred!pred;

	static if(A.length == 0)
		enum anyTuple = false;
	else static if(!predTemplate!(A[0]))
		enum anyTuple = anyTuple!(pred, A[1 .. $]);
	else
		enum anyTuple = true;
}

unittest
{
	static assert(!anyTuple!(`true`));
	static assert( anyTuple!(`isIntegral!T`, float, int));
	static assert( anyTuple!(`a < 2`, 1, 2));
	static assert(!anyTuple!(`a < 2`, 2, 3));
}


/**
Detect whether all elements of a generic tuple $(D A)
satisfy the predicate $(D pred).

Returns true for an empty tuple.

Example:
----
static assert( allTuple!(`false`));
static assert( allTuple!(`isIntegral!T`, byte, int));
static assert(!allTuple!("a & 1", 1, 2, 3));
----

Analog of $(STDREF algorithm, all) for generic tuples
except $(D pred) must be explicitly specified.
*/
template allTuple(alias pred, A...)
{
	alias predTemplate = unaryPred!pred;

	static if(A.length == 0)
		enum allTuple = true;
	else static if(predTemplate!(A[0]))
		enum allTuple = allTuple!(pred, A[1 .. $]);
	else
		enum allTuple = false;
}

unittest
{
	static assert( allTuple!(`false`));
	static assert(!allTuple!(`false`, 1));
	static assert( allTuple!(`isIntegral!T`, byte, int));
	static assert( allTuple!(`a < 2`, -1, 1));
	static assert(!allTuple!(`a < 2`, -1, 2));
    static assert( allTuple!("a & 1", 1, 3, 5, 7, 9));
    static assert(!allTuple!("a & 1", 1, 2, 3, 5, 7, 9));
}

//  internal templates from std.typetuple:

private template isSame(ab...)
	if (ab.length == 2)
{
	static if (__traits(compiles, expectType!(ab[0]),
	                              expectType!(ab[1])))
	{
		enum isSame = is(ab[0] == ab[1]);
	}
	else static if (!__traits(compiles, expectType!(ab[0])) &&
	                !__traits(compiles, expectType!(ab[1])) &&
	                 __traits(compiles, expectBool!(ab[0] == ab[1])))
	{
		static if (!__traits(compiles, &ab[0]) ||
		           !__traits(compiles, &ab[1]))
			enum isSame = (ab[0] == ab[1]);
		else
			enum isSame = __traits(isSame, ab[0], ab[1]);
	}
	else
	{
		enum isSame = __traits(isSame, ab[0], ab[1]);
	}
}
private template expectType(T) {}
private template expectBool(bool b) {}