Skip to content

@MartinNowak /buffered_input_range.d
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.