module combiner;

import std.range;
import std.typecons;
import std.traits;
import std.algorithm;

/**
Iterate the combinatorial result of several ranges. The element type
is a elementTuple tuple that allows accessing the current element in the
$(D n)th range by using $(D e.at!(n)).

Example:
----
int[] a = [ 1, 2 ];
string[] b = [ "a", "b" ];
// prints 1:a 1:b 2:a 2:c
foreach (e; combine(a, b))
{
    write(e.at!(0), ':', e.at!(1), ' ');
}
----

$(D Combine) offers the lowest range facilities of all components, e.g.
it offers random access iff all ranges offer random access, and also
offers mutation and swapping if all ranges offer it.
 */
struct Combine(R...)
{
private:
	Tuple!R savedRanges;
	alias Tuple!(staticMap!(ElementType, R)) elementTuple;
public:
	Tuple!R ranges;
/**
Builds an object. Usually this is invoked indirectly by using the
$(XREF combiner,combine) function.
 */
	this(R args)
	{
		foreach (i, Unused; R)
		{
			ranges.field[i] = args[i];
			savedRanges.field[i] = args[i];
		}
	}
/**
Returns $(D true) if the range is at end. 
 */
	bool empty()
	{
		foreach ( i, Unused; R ) {
			if ( savedRanges.field[i].length == 0 ) {
				return true;
			}
		}
		return ranges.field[0].empty;
	}
/**
Returns a elementTuple for the current iterated element.
 */
    elementTuple front()
	{
        elementTuple result;
        foreach (i, Unused; R)
		{
			result.field[i] = ranges.field[i].front;
        }
        return result;
    }
/**
Advances the front of the range, looping back to the start for any
range whose next range is empty.
 */
	void popFront()
	{
		void popFrontImpl( int i )( ref typeof(this) that ) // Weird hack, I know.
		{
			that.ranges.field[i].popFront;
			static if ( i >= 1 )
			{
				if ( that.ranges.field[i].empty )
				{
					that.ranges.field[i] = that.savedRanges.field[i];
					popFrontImpl!( i-1 )(that);
				}
			}
		}
		popFrontImpl!(R.length-1)(this);
	}
/**
Returns the length of this range. Defined only if all ranges define
$(D length).
 */
static if (allSatisfy!(hasLength, R))
	size_t length()
	{
		auto result = ranges.field[0].length;
		foreach( i, unused; R[1..$] )
		{
			result *= savedRanges.field[i+1].length - 1;
			result += ranges.field[i+1].length;
		}
		return result;
	}
}

/// Ditto
Combine!R combine(R...)(R ranges)
{
	return Combine!(R)(ranges);
}

unittest {
	assert(equal(combine([1,2],[3,4]), [tuple(1,3), tuple(1,4), tuple(2,3), tuple(2,4)]));
	assert(equal(combine([1,2],["a","b"]), [tuple(1,"a"), tuple(1,"b"), tuple(2,"a"), tuple(2,"b")]));
	assert(!equal(combine([1],["a","b"]), [tuple(1,"a"), tuple(1,"b"), tuple(2,"a"), tuple(2,"b")]));
}