buffered input

[Andrei Alexandrescu]

On 2/6/11 0:01 EST, Nick Sabalausky wrote:
> "Andrei Alexandrescu"<SeeWebsiteForEmail at erdani.org>  wrote in message
> news:iil64l$1f6s$1 at digitalmars.com...
>> On 2/5/11 7:28 PM, Don wrote:
>>>
>>> Circular buffers don't seem like an 'optional' use case to me. Most real
>>> I/O works that way.
>>> I think if the abstraction can't handle it, the abstraction is a failure.
>>
>> The abstraction does handle it implicitly, except that it doesn't fix the
>> buffer size. If you ask for appendToFront() with large numbers without
>> calling shiftFront() too, the size of the buffer will ultimately increase
>> to accommodate the entire input. That's the infinite in infinite
>> lookahead.
>>
>
> But what about when the window straddles the border? Ex: The circular
> buffer's internal size is 1000, the current starting point is 900 and the
> window (ie, front()) is 200. I guess that could work fine if front() is a
> random-access range, but if it's an array (which I think is what you
> proposed unless I misunderstood), then front() would have to return a new
> allocation: buf[900..$]~buf[0..100].

Say the buffer has 1000 elements of which the last 100 contain data (and 
the other 900 are past data that's not used). Then say this request comes:

stream.appendToFront(150);

At this point the stream may go two ways:

1. Append to the internal in-memory buffer, making it larger:

_buf.length += 150;
... read into _buf[$ - 150 .. $] ...

Now we have a buffer that has 1100 elements, of which the last 250 are used.

2. Move the data to the beginning of the buffer and then read 150 more 
elements starting at position 100:

_buf[0 .. 100] = _buf[$ - 100 .. $];
... read into _buf[100 .. 250] ...

Now _buf has still 1000 elements, of which the first 250 contain data.

How does the stream decide between 1 and 2? Clearly it's undesirable to 
grow the buffer too much and it's also undesirable to copy too much 
data. A simple approach is to establish a bound on losses, for example 
copy data only if size to copy is < 5% of the entire buffer.


Andrei