RFC on range design for D2

[Andrei Alexandrescu]

Bill Baxter wrote:
> On Wed, Sep 10, 2008 at 4:52 PM, Don <nospam at nospam.com.au> wrote:
>> Andrei Alexandrescu wrote:
>>> In most slice-based D programming, using bare pointers is not necessary.
>>> Could then there be a way to use _only_ ranges and eliminate iterators
>>> altogether? A container/range design would be much simpler than one also
>>> exposing iterators.
>>> http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html
>> I like this a lot. You've mentioned safety and simplicity, but it also seems
>> to be a more powerful abstraction than STL-style iterators.
>>
>> Consider a depth-first-search over a tree. You have a start point, an end
>> point, and some internal state (in this case, some kind of stack). The
>> interesting thing is that the required internal state _may depend on the
>> values of the start & end points_.
> 
> Or you can think of it as a current point and an stopping criterion.

My design intently supports forward iteration with sentinel (e.g. a 
singly-linked list iterator that only has one node pointer and knows 
it's done when it hits null) and also forward iteration that holds both 
limits (e.g. a singly-linked list iterator that holds TWO node pointers 
and knows it's done when they are equal). That's why forward iterators 
never support a subrange "up to the beginning of some other range" 
because that would rule out sentinel-terminated iterators.

It intently does not support things like zero-terminated strings as 
random iterators. Why? Because there's no safe way of implementing indexing.

I am glad you noticed all this. It's quite subtle.

>> STL iterators don't model this very well, since they require a symmetry
>> between iterators. Which creates the difficulty of where the internal state
>> should be stored.
> 
> This is also why I argued in my other post on digitalmars.D that we
> shouldn't be trying to force the start and end parts of a range to be
> named with complete symmetry.  They have different purposes.  There
> will generally be one current point that is relatively active and one
> stopping criterion that is relatively fixed.

They do have different purposes and they are asymmetric. But as far as I 
could tell in reimplementing std.algorithm that asymmetry does not need 
to spill into the interface.

There is one imperfection: there are forward iterators that can 
implement subranges "up to the beginnig of some other range". They are 
not categorized in my design.

> I would like to take back one thing, though.  In another post I said I
> didn't think using * for getting the current value was a good idea
> because it would be too hard to grep for.  I hadn't been considering
> the RandomAccess ranges at that time.  I can't imagine *not* using
> operators for the random access ranges -- it just makes too much
> sense.  So if it's ok for random access then it should be ok for
> forward and bidir to use operators too.   BUT, just as with the random
> access ranges, I don't think there should be any synonyms.  Just use *
> as the only way to get the current element of a range.
> 
> I think the desire to have a special "*" shortcut is as clear an
> indication as any that Andrei in his heart of hearts agrees that the
> two parts of a range are not really symmetric and should not be
> treated as such.

Walter doesn't like "*" :o(.


Andrei