RFC on range design for D2

[Bill Baxter]

On Wed, Sep 10, 2008 at 7:47 AM, Fawzi Mohamed <fmohamed at mac.com> wrote:

>>> 2) All the methods with intersection of iterator in my opinion are
>>> difficult to memorize, and rarely used, I would scrap them.
>>> Instead I would add the comparison operation .atSamePlace(iterator!(T)y)
>>> that would say if two iterators are at the same place. With it one gets back
>>> all the power of pointers, and with a syntax and use that are
>>> understandable.
>>
>> But that comparison operation is not enough to implement anything of
>> substance. Try your hand at a few classic algorithms and you'll see.
>
> are you sure? then a range is *exactly* equivalent to a STL iterator, only
> that it cannot go out of bounds:
> // left1-left2:
> while((!i1.isEmpty) && (!i1.atSamePlace(i2))){
>  i1.next;
> }
> // left2-left1:
> while((!i2.isEmpty) && (!i1.atSamePlace(i2))){
>  i1.next;
> }
> // union 1-2
> while((!i1.isEmpty) && (!(i1.atSamePlace(i2))){
>  i1.next;
> }
> while(!i2.isEmpty){
>  i2.next;
> }
> // union 2-1
> ...
> // lower triangle
> i1=c.all;
> while(!i1.isEmpty){
>  i2=c.all;
>  while(!i2.isEmpty && !i2.atSamePlace(i1)){
>   i2.next;
>  }

Your code shows that you can successfully iterate over the same
elements described by Andrei's various unions and differences, but
they do not show how you would, say, pass that new range another
function to do that job.  Such as you would want to do in say, a
recursive sort.  Since in this design you can't set or access the
individual iterator-like components of a range directly, being able to
copy the begin or end iterator from one range over to another is
necessary, I think.

But I think you and I are in agreement that it would be easier and
more natural to think of ranges as iterators augmented with
information about bounds, as opposed to a contiguous block of things
from A to B.

> well these are the operations that you can do on basically all iterators
> (and with wich you can define new iterators).
> The one you propose need an underlying total order that can be efficiently
> checked, for example iterators on trees do not have necessarily this
> property, and then getting your kind of intersection can be difficult (and
> not faster than the operation using atSamePlace.

I don't think that's correct.  Andrei's system does not need a total
order any more than yours does.  The unions and diffs just create new
ranges by combining the components of existing ranges.  They don't
need to know anything about what happens in between those points or
how you get from one to the other.  Just take the "begin" of this guy
and put it together with the "end" of that guy, for example.  It
doesn't require knowing how to get from anywhere to anywhere to create
that new range.

--bb