#!/home/andrei/bin/rdmd --shebang -unittest

import std.algorithm, std.contracts, std.range, std.stdio, std.typecons;

struct Combiner(R1, R2)
{
private:
    R1 r1Orig, r1;
    R2 r2Orig, r2;
    enum State { done, walkR1, walkR2 }
    State state;
    ulong globalOffset;
    ulong walkOffset;

    this(R1 _r1, R2 _r2)
    {
        r1Orig = _r1.save;
        r2Orig = _r2.save;
        r1 = _r1;
        r2 = _r2;

        if (!_r1.empty && !_r2.empty) state = State.walkR1;
    }

    @property bool empty() const
    {
        return state == State.done;
    }

    @property Tuple!(ElementType!R1, ElementType!R2) front()
    {
        return tuple(r1.front, r2.front);
    }

    private void startNextEpoch()
    {
        assert(!empty && !r1.empty && !r2.empty);
        // We also assume that r1 and r2 are both positioned in the
        // outermost corner

        // Global offset increment marks the new epoch
        ++globalOffset;
        walkOffset = 0;

        // Upon the new epoch we try to walk r1 first, r2 second
        r2.popFront();
        if (r2.empty)
        {
            // We can't walk r1, but there may be still some juice
            // left in r1, so try to walk r2
            r1.popFront();
            if (r1.empty)
            {
                state = State.done;
            }
            else
            {
                r2 = r2Orig.save;
                assert(!r2.empty);
                state = State.walkR2;
            }
        }
        else
        {
            // Walk r1 now
            r1 = r1Orig.save;
            state = State.walkR1;
        }
    }

    void popFront()
    {
        enforce(!empty);
        assert(!r1.empty && !r2.empty);
        if (state == State.walkR1)
        {
            if (walkOffset == globalOffset)
            {
                // Special case: first corner entails no walk of r2
                if (!globalOffset)
                {
                    startNextEpoch();
                }
                else
                {
                    // We're straight in the far corner, now walk r2
                    r2 = r2Orig.save;
                    state = State.walkR2;
                    walkOffset = 0;
                }
            }
            else
            {
                // Still a ways to walk r1
                r1.popFront();
                if (r1.empty)
                {
                    // r2 outlasts r1
                    r2.popFront();
                    if (r2.empty)
                    {
                        state = State.done;
                    }
                    else
                    {
                        r1 = r1Orig.save;
                        ++globalOffset;
                        walkOffset = 0;
                        assert(state == State.walkR1);
                    }
                }
                else
                {
                    ++walkOffset;
                }
            }
        }
        else // state == State.walkR2
        {
            assert(state == State.walkR2);
            assert(walkOffset <= globalOffset);
            r2.popFront();
            if (r2.empty)
            {
                // Continue walking r2
                r1.popFront();
                if (r1.empty)
                {
                    state = State.done;
                }
                else
                {
                    r2 = r2Orig.save;
                    ++globalOffset;
                    walkOffset = 0;
                    assert(state == State.walkR2);
                }
            }
            else if (++walkOffset >= globalOffset)
            {
                // We're in the outermost corner, start new epoch
                startNextEpoch();
            }
        }
    }
}

auto xproduct(R1, R2)(R1 r1, R2 r2)
{
    return Combiner!(R1, R2)(r1, r2);
}

void main()
{
    auto c = xproduct(iota(3), iota(5));
    uint i;
    foreach (e; c)
    {
        writeln(i++, '\t', e);
    }
}