• =?UTF-8?B?QWxpIMOHZWhyZWxp?= (202/202) Dec 29 2010 After my recent experiments with ranges and bearophile's thread "Phobos

=?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:

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