buffered_input_range.d

import std.algorithm, std.range, std.stdio;
import core.bitop;

enum PAGESIZE = 4096;

struct BufferedInputRange(R) if(isInputRange!R)
{
    alias ElementType!R E;

    this(R input)
    {
        _input = input;
        static if (E.sizeof >= PAGESIZE)
            immutable cnt = 1;
        else
            immutable cnt = 1 << bsr((PAGESIZE + E.sizeof - 1) / E.sizeof);
        _buffer = new E[](cnt);
        fill(); // prime
    }

    @property bool empty() const
    {
        return _ridx == _widx && _input.empty;
    }

    @property E front()
    {
        return _buffer[_ridx & mask];
    }

    void popFront()
    {
        if (++_ridx == _widx)
            fill();
    }

    /// peek
    int opApply(scope int delegate(ref E) dg)
    {
        return opApply((size_t i, ref E e) => dg(e));
    }

    /// ditto
    int opApply(scope int delegate(size_t i, ref E) dg)
    {
        size_t i;
        int res;
        while (!res)
        {
            if (_ridx + i == _widx)
            {
                if (_input.empty)
                    break;

                immutable ridx = _ridx & mask;
                immutable widx = _widx & mask;
                if (ridx == widx)
                {
                    // no capacity => grow buffer
                    if (ridx)
                    {
                        bringToFront(_buffer[0 .. ridx], _buffer[ridx .. $]);
                        _ridx = 0;
                        _widx = _buffer.length;
                    }
                    _buffer.length *= 2;
                }
                fill();
            }

            res = dg(i, _buffer[_ridx + i++ & mask]);
        }
        return res;
    }


private:
    void fill()
    {
        immutable m = mask;
        immutable widx = _widx & m;
        immutable ridx = _ridx & m;
        immutable cnt = ridx > widx ? ridx - widx : _buffer.length - widx + ridx;

        size_t i;
        for (; i < cnt && !_input.empty; ++i, _input.popFront)
            _buffer[_widx + i & m] = _input.front;
        _widx += i;
    }

    @property size_t mask() const
    {
        return _buffer.length - 1;
    }

    E[] _buffer;
    size_t _ridx, _widx;
    R _input;
}

BufferedInputRange!R bufferedInputRange(R)(R input)
{
    return typeof(return)(input);
}

struct InputRange
{
    this(int length)
    {
        _val = new int;
        _end = length;
    }

    int front() { return *_val; }
    bool empty() const { return *_val == _end; }
    void popFront() { ++*_val; }

    int* _val;
    int _end;
}

struct ForwardRange
{
    this(int length)
    {
        _end = length;
    }

    int front() { return _val; }
    bool empty() const { return _val == _end; }
    void popFront() { ++_val; }

    int _val;
    int _end;
}

void main()
{
    auto br = bufferedInputRange(InputRange(5));
    auto fr = ForwardRange(5);
    br.popFront;
    fr.popFront;
    writeln("foreach-loop BufferedInputRange");
    foreach(e; br)
        writeln(e);
    assert(!br.empty);
    writeln("foreach-loop ForwardRange");
    foreach(e; fr)
        writeln(e);
    assert(!fr.empty);

    writeln("for-loop BufferedInputRange");
    for (; !br.empty; br.popFront)
        writeln(br.front);
    assert(br.empty);

    writeln("for-loop ForwardRange");
    for (; !fr.empty; fr.popFront)
        writeln(fr.front);
    assert(fr.empty);
}