RFC on range design for D2

[Andrei Alexandrescu]

Fawzi Mohamed wrote:
> 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;
>  }
> 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 am getting seriously confused by this subthread. So are you saying 
that atSamePlace is your primitive and that you implement the other 
range operations all in linear time? If I did not misunderstand and 
that's your design, then you may want to revise that design right now. 
It will never work. I guarantee it.

> the only new thing is bidirectional iterator: an iterator that can go in 
> both directions as extra iterator type (your bidirectional range is 
> something different).

A bidirectional range is simply a range that you can shrink from either 
end.

> I think it is useful and I don't see the need to shoehorn it into a 
> range. For me an iterator is an object that can generate a sequence by 
> itself, so a range is an example of iterator, but I don't see the need 
> to make each iterator a range.

I have put forth reasons for doing away with iterators entirely in the 
range doc. What are your counter-reasons for bringing back iterators?

> As I said before a range also has a total ordering of the objects that 
> can be easily checked, this is a special king of iterator for me, not 
> the most general. Take two ranges of two linked lists, you cannot easily 
> build your intersections because you don't know their relative order, 
> and checking it is inefficient.

Correct. The range intersection primitives are Achille's heel of the 
range-based design. Checking subrange reachability is O(n), so the range 
intersection primitives take the user by faith. But iterators have that 
Achille's heel problem too, plus a few arrows in their back :o). The 
document clarifies this disadvantage by saying that range intersection 
primitives are undefined if certain conditions are not met.

In short, this is an endemic problem of an iteration based on either 
ranges or individual iterators. An objection to that should 
automatically come with a constructive proof, i.e. a better design.

>>> So this is what "my" iterator/range would look like :)
>>
>> I encourage you to realize your design. Before long you'll find 
>> probably even more issues with it than I mentioned above, but you'll 
>> be gained in being better equipped to find proper solutions.
> 
> I hope we converge toward a good solution ;)

Well I haven't seen much code yet.


Andrei