module nxt.combinations;

/** Given non-negative integers $(D m) and $(D n), generate all size $(D m)
   combinations of the integers from 0 to $(D n)-1 in sorted order (each
   combination is sorted and the entire table is sorted).

   For example, 3 comb 5 is
   0 1 2
   0 1 3
   0 1 4
   0 2 3
   0 2 4
   0 3 4
   1 2 3
   1 2 4
   1 3 4
   2 3 4

   See_Also: http://rosettacode.org/wiki/Combinations
*/
struct Combinations(T, bool copy = true, bool useArray = true)
{
    import std.container: Array;
    import std.traits: Unqual;

    static if (useArray)
        alias Indices = Array!size_t;
    else
        alias Indices = size_t[];

    Unqual!T[] pool, front;
    size_t r, n;
    bool empty = false;

    Indices indices;

    size_t len;
    bool lenComputed = false;

    this(T[] pool_, in size_t r_) // pure nothrow @safe
    {
        this.pool = pool_.dup;
        this.r = r_;
        this.n = pool.length;
        if (r > n)
            empty = true;

        indices.length = r;

        size_t i;

        i = 0;
        foreach (ref ini; indices[])
            ini = i++;

        front.length = r;

        i = 0;
        foreach (immutable idx; indices[])
            front[i++] = pool[idx];
    }

    @property size_t length() /*logic_const*/ // pure nothrow @nogc
    {
        static size_t binomial(size_t n, size_t k) // pure nothrow @safe @nogc
        in
        {
            assert(n > 0, "binomial: n must be > 0.");
        }
        do
        {
            if (k < 0 || k > n)
                return 0;
            if (k > (n / 2))
                k = n - k;
            size_t result = 1;
            foreach (size_t d; 1 .. k + 1) {
                result *= n;
                n--;
                result /= d;
            }
            return result;
        }

        if (!lenComputed)
        {
            // Set cache.
            len = binomial(n, r);
            lenComputed = true;
        }
        return len;
    }

    void popFront() // pure nothrow @safe
    {
        if (!empty)
        {
            bool broken = false;
            size_t pos = 0;
            foreach_reverse (immutable i; 0 .. r)
            {
                pos = i;
                if (indices[i] != i + n - r)
                {
                    broken = true;
                    break;
                }
            }
            if (!broken)
            {
                empty = true;
                return;
            }
            indices[pos]++;
            foreach (immutable j; pos + 1 .. r)
                indices[j] = indices[j - 1] + 1;
            static if (copy)
                front = new Unqual!T[front.length];

            size_t i = 0;
            foreach (immutable idx; indices[])
            {
                front[i] = pool[idx];
                i++;
            }
        }
    }
}

auto combinations(bool copy = true, T, bool useArray = false)(T[] items, in size_t k)
in(items.length)
	=> Combinations!(T, copy, useArray)(items, k);

unittest
{
    import std.algorithm: equal, map;
    // assert(equal([1, 2, 3, 4].combinations!false(2), [[3, 4], [3, 4], [3, 4], [3, 4], [3, 4], [3, 4]]));
    enum solution = [[1, 2],
                     [1, 3],
                     [1, 4],
                     [2, 3],
                     [2, 4],
                     [3, 4]];
    assert(equal([1, 2, 3, 4].combinations!true(2), solution));
    assert(equal([1, 2, 3, 4].combinations(2).map!(x => x), solution));
}

import std.range.primitives : isInputRange;

/** All Unordered Element Pairs (2-Element Subsets) of a $(D Range).

    TODO: Add template parameter to decide if .array should be used internally.

    See_Also: http://forum.dlang.org/thread/iqkybajwdzcvdytakgvw@forum.dlang.org#post-vhufbwsqbssyqwfxxbuu:40forum.dlang.org
    See_Also: https://issues.dlang.org/show_bug.cgi?id=6788
    See_Also: https://issues.dlang.org/show_bug.cgi?id=7128
*/
auto pairwise(R)(R r)
if (isInputRange!R)
{
    struct Pairwise(R)
    {
        import core.internal.traits : Unqual;
        import std.traits : ForeachType;
        import std.typecons: Tuple;

        alias UR = Unqual!R;
        alias E = ForeachType!UR;
        alias Pair = Tuple!(E, E);

        import std.range.primitives : isRandomAccessRange, hasLength;
        import std.traits : isNarrowString;

        static if (isRandomAccessRange!R &&
                   hasLength!R &&
                   !isNarrowString!R)
        {

            this(R r_)
            {
                this._input = r_;
                j = 1;
            }
            @property bool empty() => j >= _input.length;
            @property Pair front() => typeof(return)(_input[i], _input[j]);
            void popFront()
            {
                if (j >= _input.length - 1)
                {
                    i++;
                    j = i + 1;
                }
                else
                    j++;
            }
            private size_t i, j;
        }
        else // isInputRange!UR
        {
            import std.range : dropOne;
            this(R r_)
            {
                this._input = r_;
                i = r_;
                if (!i.empty)
                    j = i.dropOne;
                else
                    j = UR.init;
            }
            @property bool empty() => j.empty;
            @property Pair front() => typeof(return)(i.front, j.front);
            void popFront()
            {
                j.popFront();
                if (j.empty)
                {
                    i.popFront();
                    j = i.dropOne;
                }
            }
            private UR i, j; // temporary copies of $(D _input)
        }

    private:
        UR _input;
    }

    return Pairwise!R(r);
}

/// test RandomAccessRange input
unittest
{
    import std.algorithm: equal, filter;
    import std.typecons: Tuple;

    assert((new int[0]).pairwise.empty);
    assert([1].pairwise.empty);

    alias T = Tuple!(int, int);
    assert(equal([1, 2].pairwise,
                 [T(1, 2)]));
    assert(equal([1, 2, 3].pairwise,
                 [T(1, 2), T(1, 3), T(2, 3)]));
    assert(equal([1, 2, 3, 4].pairwise,
                 [T(1, 2), T(1, 3), T(1, 4),
                  T(2, 3), T(2, 4), T(3, 4)]));
}

/// test ForwardRange input
unittest
{
    import std.algorithm: equal, filter;
    import std.array : array;

    auto p = [1].filter!"a < 4".pairwise;
    assert(p.empty);

    assert(equal(p.array,
                 [1].pairwise.array));

    assert(equal([1, 2, 3, 4].filter!"a < 4".pairwise,
                 [1, 2, 3].pairwise));
}