asForwardRange, a ForwardRange based on an InputRange
Ali Çehreli
acehreli at yahoo.com
Wed Dec 29 12:20:19 PST 2010
After my recent experiments with ranges and bearophile's thread "Phobos
usability with text files" I decided to try a ForwardRange based on an
InputRange.
Of course it's pretty trivial: the elements that are read from the
original range are cached. The elements that have all been consumed by
all the "views" are dropped from the beginning of the cache and
eventually freed by the GC.
I decided to represent each view as a pointer into the cached elements.
The pointers need adjustment if the cached array is relocated by the GC.
The test program creates files /tmp/deleteme_* and copies each
ForwardRange's view into those files. (That is commented out in the
included program.)
// --- 8< ---------- as_forward_range.d ---------- >8 ---
module as_forward_range;
import std.range : isInputRange, ElementType;
/**
* A ForwardRange based on an InputRange
*
* Consumes the original InputRange lazily
*/
class ForwardRangeLazyCache(Range)
if (isInputRange!Range)
{
alias ElementType!Range E;
Range range; /* The original range */
immutable(E)[] cache; /* Cached elements from the original
range */
immutable(E)*[] viewPtrs; /* Views into the cached elements */
immutable(E)* endPtr; /* One-past-the-end pointer of the
cache */
this(Range range)
{
this.range = range;
this.endPtr = cache.ptr + cache.length;
}
/**
* Register a new view (i.e. a ForwardRange) as a user of this cache
*/
AsForwardRange!Range newView(immutable(E) * ptr)
{
viewPtrs ~= ptr;
return new AsForwardRange!Range(this, viewPtrs.length - 1);
}
/**
* Whether the specified view has seen all elements from the cache
*/
bool viewIsEmpty(size_t id)
{
return viewPtrs[id] == endPtr;
}
/**
* Whether the specified view is empty
*/
@property bool empty(size_t id)
{
return range.empty && viewIsEmpty(id);
}
/**
* Ensure that the element at the specified address is read
*/
void ensureRead(immutable(E) * ptr)
in
{
/* Since we are iterating, only one more than what is actually
read is
* acceptable */
assert(ptr <= endPtr);
}
body
{
if (ptr == endPtr) {
immutable oldPtr = cache.ptr;
cache ~= range.front.idup;
range.popFront();
if (cache.ptr != oldPtr) {
/* The cache has been relocated */
adjustPtrs(oldPtr, cache.ptr);
} else {
++endPtr;
}
}
}
/**
* The front element of the specified view
*/
@property immutable(E) front(size_t id)
{
ensureRead(viewPtrs[id]);
return *(viewPtrs[id]);
}
/**
* Pop the front element of the specified view
*/
void popFront(size_t id)
{
++(viewPtrs[id]);
}
/**
* Make a copy of the specified view
*/
AsForwardRange!Range save(size_t id)
{
return newView(viewPtrs[id]);
}
/**
* Adjust the view pointers into the newly relocated cache
*/
void adjustPtrs(immutable(E) * oldPtr,
immutable(E) * newPtr)
{
endPtr = cache.ptr + cache.length;
immutable(E) * minPtr = endPtr;
foreach (i, ref ptr; viewPtrs) {
ptr = newPtr + (ptr - oldPtr);
if (ptr < minPtr) {
minPtr = ptr;
}
}
/* Nobody is using the first part of the cache anymore */
cache = cache[(minPtr - cache.ptr) .. $];
}
}
/**
* A thin layer as a view (i.e. a ForwardRange) into the cached
elements of a
* ForwardRangeLazyCache
*/
class AsForwardRange(Range)
{
ForwardRangeLazyCache!Range lazyCache;
size_t myId;
this(ForwardRangeLazyCache!Range lazyCache, size_t myId)
{
this.lazyCache = lazyCache;
this.myId = myId;
}
@property bool empty()
{
return lazyCache.empty(myId);
}
@property auto front()
{
return lazyCache.front(myId);
}
@property void popFront()
{
lazyCache.popFront(myId);
}
AsForwardRange!Range save()
{
return lazyCache.save(myId);
}
}
/**
* A convenience function to make a new view (i.e. a ForwardRange) from an
* InputRange
*/
AsForwardRange!Range asForwardRange(Range)(Range range)
{
auto lazyCache = new ForwardRangeLazyCache!Range(range);
return lazyCache.newView(lazyCache.cache.ptr);
}
// --- 8<---------- The test program ---------- >8 ---
import std.stdio;
import std.range;
import std.random;
import as_forward_range;
import std.conv;
void main()
{
auto range = asForwardRange(stdin.byLine());
typeof(range)[] ranges;
ranges ~= range;
File[] files;
files ~= File("/tmp/deleteme_" ~ to!string(files.length), "w");
string line;
while (!allIsDone(ranges)) {
if ((ranges.length < 10) && (uniform(0, ranges.length) == 0)) {
ranges ~= ranges.front.save();
files ~= File("/tmp/deleteme_" ~ to!string(files.length), "w");
}
foreach (i, r; ranges) {
if (!r.empty) {
auto popCount = uniform(1, 10);
for ( ; popCount && !r.empty; --popCount, r.popFront) {
// files[i].writeln(r.front);
line = r.front;
}
}
}
}
}
bool allIsDone(Range)(Range[] ranges)
{
foreach (range; ranges) {
if (!range.empty) {
return false;
}
}
return true;
}
Ali
More information about the Digitalmars-d
mailing list