buffered input

[Ellery Newcomer]

On 02/04/2011 11:46 PM, Andrei Alexandrescu wrote:
> I've had the opportunity today to put some solid hours of thinking into
> the relationship (better said the relatedness) of what would be called
> "buffered streams" and ranges. They have some commonalities and some
> differences, but it's been difficult to capture them. I think now I have
> a clear view, caused by a few recent discussions. One was the CSV reader
> discussed on the Phobos list; another was the discussion on defining the
> "right" std.xml.
>
> First, let's start with the humblest abstraction of all - an input
> range, which only defines the troika empty/front/popFront with the known
> semantics.
>
> An input range consumes input destructively and has a one-element
> horizon. It may as well considered a buffered stream with the buffer
> length exactly one.
>
> Going from there, we may say that certain streaming can be done by using
> an input range of ubyte (or dchar for text). That would be the
> UTFpowered equivalent of getchar(). The readf function operates that way
> - it only needs to look one character ahead. Incidentally, the CSV
> format also requires lookahead of 1, so it also can operate on a range
> of dchar.
>
> At this point we need to ask ourselves an essential question. Since we
> have this "input range" abstraction for a 1-element buffer, what would
> its n-elements buffer representation look like? How do we go from "input
> range of T" (which really is "unbuffered input range of T" to "buffered
> input range of T"?
>
> Honestly, the answer was extremely unclear to me for the longest time. I
> thought that such a range would be an extension of the unbuffered one,
> e.g. a range that still offers T from front() but also offers some
> additional functions - e.g. a lookahead in the form of a random-access
> operator. I still think something can be defined along those lines, but
> today I came together with a design that is considerably simpler both
> for the client and the designer of the range.
>
> I hereby suggest we define "buffered input range of T" any range R that
> satisfies the following conditions:
>
> 1. R is an input range of T[]
>
> 2. R defines a primitive shiftFront(size_t n). The semantics of the
> primitive is that, if r.front.length >= n, then shiftFront(n) discards
> the first n elements in r.front. Subsequently r.front will return a
> slice of the remaining elements.

Does shiftFront literally move element n to index 0 and so on? It seems 
to me that if you do, its going to have horrid performance, and if you 
don't, then you will eventually run into situations where appendToFront 
will require a wrap around, which loses you your contiguity, or a 
reallocation of the buffer.