public
Created

  • Download Gist
buffered_input_range.d
D
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
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);
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.