RFC on range design for D2

[Fawzi Mohamed]

On 2008-09-10 14:35:29 +0200, "Bill Baxter" <wbaxter at gmail.com> said:

> 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.

yes you are right this operation on the simplest iterators cannot be 
preformed recursevely without overhead (you can do it once, but then 
you need to store i1 & i2 in the new iterator, to do it again will add 
more and more overhead.
Range union... can be used efficiently and safely only if the iterator 
has an order that can be easily checked, this is a useful abstraction, 
but not the basic one.

> 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.

well if you don't have a total order that you can easily check then 
this might be very unsafe
think to i1.begin..i2.begin if i2.begin<i1.begin, you might miss that 
it is empty, and iterate forever...

Fawzi