buffered input

[Michel Fortin]

On 2011-02-06 03:22:08 -0500, Jonathan M Davis <jmdavisProg at gmx.com> said:

> So, maybe I'm still misunderstanding or missing something here, but what _I_
> want to see for I/O streams is a _forward_ range which is buffered and which
> reads in the file or whatever the data comes from in a lazy manner. The more I
> think about it, the less I like input ranges. They're just so painfully
> restrictive. They may be necessary at times, but I'd _much_ prefer to deal with
> forward ranges.

It's true that forward ranges are much easier to deal with. That said, 
if the underlying abstraction does not support saving a position to 
return to it later (think of a network stream), implementing them is 
rather impractical, even though it might be possible with buffering.

But still, let's let's see how we could implement a forward range on 
top of the buffered range abstraction could be done:

1. Wrap the buffered range in a data structure that keeps track of the 
absolute offset for the first element in the range and contains a 
sorted list of offsets representing all the forward ranges iterating on 
it.

2. Make is so that each time the smallest offset in the list is 
advanced you call shiftFront to to remove from the buffer the no longer 
referenced elements; and each time an offset goes beyond what's 
available in the buffer you call appendToFront to make elements up to 
that index available in the buffer. This ensures the buffer always 
cover all of the offsets in the list. To make this efficient, the list 
must be kept sorted at all times.

3. Then you can create forward ranges as reference to that data 
structure: all they have to do is maintain their offset in the list. 
Creating a new range would just create another offset in the list and 
ensures the buffer is preserved. When the range advances or gets 
destroyed it updates or destroy its offset in the list accordingly. 
This way the buffer always covers all forward ranges.

While it is indeed possible to do what you want, it's hardly a good 
abstraction to build an efficient parsing algorithm. There's just too 
much bookkeeping to do. And you must be sure saved ranges get destroyed 
as soon as possible to avoid the buffer from growing too much, 
something you usually don't have to care about with forward ranges.


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/