inputrange.d

/*
 * Implementation of a few algorithms around a `fetchNext` API.
 */

import std.array : empty;
import std.traits : lvalueOf, rvalueOf;
import core.lifetime : move;
import std.stdio : File, writeln;
import std.typecons : Flag, Yes, No;

// Sigh...
mixin template YesIAmReallyNonCopyableThankYouVeryMuch()
{
    @disable this(ref typeof(this)); // this should be enough...
    @disable this(this);
}

template ElementType(R)
{
    static if (is(R.ElementType))
        alias ElementType = R.ElementType;
    else
        static assert(false);
}

enum bool isInputRange(R) =
    is(ElementType!R) &&
    is(typeof(lvalueOf!R.fetchNext(lvalueOf!(ElementType!R))) == bool);

size_t count(alias pred = "a == b", Range, Needle)(Range haystack, auto ref const Needle needle)
if (isInputRange!Range)
{
    import std.functional : binaryFun, partial, reverseArgs;
    alias cmp = partial!(reverseArgs!(binaryFun!pred), needle);
    version (none)
    {
        // Alternative implementation - less efficient,
        // at least until we get language moves
        return move(haystack).count!cmp;
    }
    else
    {
        size_t result;
        ElementType!Range tmp = ElementType!Range.init;
        while (haystack.fetchNext(tmp))
            result += !!cmp(tmp);
        return result;
    }
}

size_t count(alias pred, Range)(Range haystack)
if (isInputRange!Range)
{
    size_t result;
    import std.functional : unaryFun;
    alias cmp = unaryFun!pred;
    version (none)
    {
        // Alternative implementation - less efficient,
        // at least until we get language moves
        move(haystack).each!((e) { result += !!cmp(e); });
        return result;
    }
    else
    {
        ElementType!Range tmp = ElementType!Range.init;
        while (haystack.fetchNext(tmp))
            result += !!cmp(tmp);
    }
    return result;
}

auto map(alias func = "a", Range)(Range range)
if (isInputRange!Range)
{
    import std.functional : unaryFun;
    alias f = unaryFun!func;

    alias E = ElementType!Range;
    alias M = typeof(f(E.init));
    static struct Result
    {
        private Range src;

        this(Range src)
        {
            this.src = move(src);
        }

        // https://issues.dlang.org/show_bug.cgi?id=20965
        mixin YesIAmReallyNonCopyableThankYouVeryMuch!();

        alias ElementType = M;

        bool fetchNext(ref M e)
        {
            bool result;
            E tmp = E.init;
            if (src.fetchNext(tmp))
            {
                M x = f(move(tmp));
                move(x, e);
                result = true;
            }
            return result;
        }
    }
    return Result(move(range));
}

auto filter(alias pred = "a == true", Range)(Range range)
if (isInputRange!Range)
{
    import std.functional : unaryFun;
    static struct Result
    {
        private Range src;
        private alias cmp = unaryFun!pred;

        alias ElementType = .ElementType!Range;

        this(Range src)
        {
            this.src = move(src);
        }
        
        // https://issues.dlang.org/show_bug.cgi?id=20965
        mixin YesIAmReallyNonCopyableThankYouVeryMuch!();        
        
        bool fetchNext(ref ElementType e)
        {
            bool result;
            ElementType tmp = ElementType.init;
            while (src.fetchNext(tmp))
            {
                if (cmp(tmp))
                {
                    move(tmp, e);
                    result = true;
                    break;
                }
            }
            return result;
        }
    }
    return Result(move(range));
}

/*
    `find` becomes weird: it's supposed to return a range
    that starts with needle, but it can no longer keep
    the type of input range. Result would have to be,
    in principle, a chain of needle and remainder of the input.
    Which can be realized either as an actual chain(),
    a `fetchNext` range with an extra test, or a traditional "buffered"
    input range.
    This example implementation realizes a `fetchNext` API.
*/
private struct FindResult(R)
{
    alias ElementType = .ElementType!R;

    private R src = R.init;
    private bool _front = false;
    private ElementType e = ElementType.init;

    this(R src, ElementType e)
    {
        this.src = move(src);
        this.e = move(e);
        _front = true;
    }

    // https://issues.dlang.org/show_bug.cgi?id=20965
    mixin YesIAmReallyNonCopyableThankYouVeryMuch!();

    bool fetchNext(ref ElementType e)
    {
        bool result;
        version (none)
        {
            /*
                This would be a wrong implementation:
                We should not stomp over the buffered
                element before caller has a chance to consume it.
                E.g. a `byLine` would be yielding slices from a reused
                buffer, so calling src.fetchNext immediately would corrupt
                result returned to the caller.
            */
            if (_front)
            {
                move(this.e, e);
                _front = !src.fetchNext(this.e);
                result = true;
            }
        }
        else
        {
            if (!_front)
            {
                result = src.fetchNext(e);
            }
            else
            {
                move(this.e, e);
                _front = false;
                result = true;
            }
        }
        return result;
    }
}

auto find(alias pred = "a == b", Range, Needle)(Range haystack, auto ref const Needle needle)
if (isInputRange!Range)
{
    import std.functional : binaryFun, partial, reverseArgs;
    alias cmp = partial!(reverseArgs!(binaryFun!pred), needle);
    version (none)
    {
        // Alternative implementation - less efficient,
        // at least until we get language moves
        return move(haystack).find!cmp;
    }
    else
    {
        static if (is(Range == FindResult!Other, Other))
            alias Result = Range;
        else
            alias Result = FindResult!Range;

        ElementType!Range tmp = ElementType!Range.init;
        while (haystack.fetchNext(tmp))
        {
            if (cmp(tmp))
                return Result(move(haystack), move(tmp));
        }
        return Result.init;
    }
}

auto find(alias pred, Range)(Range haystack)
if (isInputRange!Range)
{
    static if (is(Range == FindResult!Other, Other))
        alias Result = Range;
    else
        alias Result = FindResult!Range;

    import std.functional : unaryFun;
    alias cmp = unaryFun!pred;
    ElementType!Range tmp = ElementType!Range.init;
    while (haystack.fetchNext(tmp))
    {
        if (cmp(tmp))
            return Result(move(haystack), move(tmp));
    }
    return Result.init;
}

/*
    Different than the eponymous algorithm for forward ranges:
    this one cannot leave `haystack` untouched, so it simply returns
    the remainder of `haystack` after `needle`, or an empty range
    if no `needle` was found.
    Perhaps it could also return a flag so the caller need not
    arduously try the `fetchNext` only to find out there's nothing there.
 */
Range findSkip(alias pred = "a == b", Range, Needle)(Range haystack, auto ref const Needle needle)
if (isInputRange!Range)
{
    import std.functional : binaryFun, partial, reverseArgs;
    alias cmp = partial!(reverseArgs!(binaryFun!pred), needle);
    version (none)
    {
        // Alternative implementation - less efficient,
        // at least until we get language moves
        return move(haystack).findSkip!cmp;
    }
    else
    {
        ElementType!Range tmp = ElementType!Range.init;
        while (haystack.fetchNext(tmp) && !cmp(tmp)) {}
        return move(haystack);
    }
}

Range findSkip(alias pred, Range, Needle)(Range haystack)
if (isInputRange!Range)
{
    import std.functional : unaryFun;
    alias cmp = unaryFun!pred;
    ElementType!Range tmp = ElementType!Range.init;
    while (haystack.fetchNext(tmp) && !cmp(tmp)) {}
    return move(haystack);
}

template reduce(funcs...) if (funcs.length >= 1)
{
    auto reduce(Range, Seeds...)(Range range, auto ref Seeds seeds)
    if (isInputRange!Range &&
        (!Seeds.length || Seeds.length == funcs.length))
    {
        import std.functional : binaryFun;
        import std.meta : AliasSeq, Repeat, staticMap;
        import std.traits : ReturnType;

        alias fs = staticMap!(binaryFun, funcs);

        // deduce reduce!
        // that is, deduce return types for each function
        static if (funcs.length == 1)
        {
            static if (!Seeds.length)
                alias Result = typeof(fs[0](lvalueOf!(ElementType!Range), lvalueOf!(ElementType!Range)));
            else
                alias Result = typeof(fs[0](lvalueOf!(Seeds), lvalueOf!(ElementType!Range)));
        }
        else
        {
            static if (!Seeds.length)
                alias ActualSeeds = Repeat!(funcs.length, ElementType!Range);
            else
                alias ActualSeeds = Seeds;

            template deduce(size_t i = 0)
            {
                static if (i == fs.length)
                    alias deduce = AliasSeq!();
                else
                {
                    alias func = fs[i];
                    alias deduce = AliasSeq!(typeof(func(lvalueOf!(ActualSeeds[i]), lvalueOf!(ElementType!Range))), deduce!(i + 1));
                }
            }

            static struct Result
            {
                deduce!() items;
                alias items this;
            }
        }

        // No seeds given - use first element of the range
        // The element type would have to be copyable in this case.
        static if (!Seeds.length)
        {
            import core.lifetime : emplace;
            Result result = void;
            {
                ElementType!Range tmp = ElementType!Range.init;
                if (range.fetchNext(tmp))
                    emplace(&result, Repeat!(funcs.length, tmp));
                else
                    throw new Exception("empty range");
            }
        }
        else
        {
            import core.lifetime : forward;
            auto result = Result(forward!seeds);
        }

        ElementType!Range tmp = ElementType!Range.init;
        while (range.fetchNext(tmp))
        {
            static if (funcs.length == 1)
            {
                auto x = fs[0](result, tmp);
                move(x, result);
            }
            else
            {
                foreach (i, f; fs)
                {
                    auto x = f(result.items[i], tmp);
                    move(x, result.items[i]);
                }
            }
        }
        return result;
    }
}

private struct ByLineImpl(Char, Terminator)
{
    private File file;
    Terminator term;
    Flag!"keepTerminator" keepTerm;
    private Char[] buffer;

    this(File f, Terminator term, Flag!"keepTerminator" keepTerm)
    {
        this.file = f;
        this.term = term;
        this.keepTerm = keepTerm;
    }

    // https://issues.dlang.org/show_bug.cgi?id=20965
    mixin YesIAmReallyNonCopyableThankYouVeryMuch!();

    alias ElementType = const(Char)[];

    bool fetchNext(ref const(Char)[] s)
    {
        bool result;
        if (file.isOpen)
        {
            auto line = buffer;
            file.readln(line, term);
            if (!line.empty)
            {
                if (line.length > buffer.length)
                    buffer = line;

                if (keepTerm == No.keepTerminator)
                {
                    static if (is(typeof(term.length)))
                    {
                        const tlen = term.length;
                        if (line[$ - tlen .. $] == term)
                            line = line[0 .. $ - tlen];
                    }
                    else
                    {
                        if (line[$-1] == term)
                            line = line[0 .. $-1];
                    }
                }
                s = line;
                result = true;
            }
            else
            {
                line = null;
                buffer = null;
            }
        }
        return result;
    }
}

auto byLine2(Terminator = char, Char = Terminator)(File f, Terminator term = '\n', Flag!"keepTerminator" keepTerm = No.keepTerminator)
{
    return ByLineImpl!(Char, Terminator)(move(f), term, keepTerm);
}

auto array(Range)(Range range)
if (isInputRange!Range)
{
    import std.array : appender;
    alias E = ElementType!Range;
    auto builder = appender!(E[]);
    {
        E tmp = E.init;
        while (range.fetchNext(tmp))
            builder.put(move(tmp));
    }
    return builder[];
}

// the below comment is just for testing `find` on a `byLine`
// NEEDLE

/*
    `each` is different: if early stopping is possible,
    it'll return both the flag and the remainder of the range.
 */
auto each(alias func = "a", Range)(Range range)
if (isInputRange!Range)
{
    import std.functional : unaryFun;
    alias f = unaryFun!func;
    ElementType!Range tmp;
    static if (is(typeof(f(move(tmp))) == Flag!"each"))
        Flag!"each" result = Yes.each;
    while (range.fetchNext(tmp))
    {
        static if (is(typeof(f(move(tmp))) == Flag!"each"))
        {
            result = f(move(tmp));
            if (result == No.each)
                break;
        }
        else
            f(move(tmp));
    }
    static if (is(typeof(f(move(tmp))) == Flag!"each"))
    {
        // Due to https://issues.dlang.org/show_bug.cgi?id=20966
        // construct our own return type
        version (none)
        {
            import std.typecons : tuple;
            return tuple!("each", "remainder")(result, move(range));
        }
        else
        {
            static struct Result
            {
                Flag!"each" each;
                Range remainder;
            }
            return Result(result, move(range));
        }
    }
}

// Returns a foreach wrapper for a `fetchNext` input range
auto munch(Range)(auto ref Range range)
if (isInputRange!Range)
{
    static struct Result
    {
        static if (__traits(isRef, range))
        {
            Range* range;
            this(return ref Range range)
            {
                this.range = ⦥
            }
        }
        else
        {
            Range range;
            this(Range range)
            {
                this.range = move(range);           
            }
        }

        mixin YesIAmReallyNonCopyableThankYouVeryMuch;

        // TODO: more overloads. Lots and lots more overloads.
        int opApply(int delegate(ref ElementType!Range) dg)
        {
            int result;
            ElementType!Range tmp = ElementType!Range.init;
            while (range.fetchNext(tmp))
            {
                result = dg(tmp);
                if (result)
                    break;
            }
            return result;
        }

        int opApply(int delegate(size_t, ref ElementType!Range) dg)
        {
            int result;
            size_t index;
            ElementType!Range tmp = ElementType!Range.init;
            while (range.fetchNext(tmp))
            {
                result = dg(index++, tmp);
                if (result)
                    break;
            }
            return result;
        }
    }
    import core.lifetime : forward;
    return Result(forward!range);
}