RFC on range design for D2

[Fawzi Mohamed]

On 2008-09-10 01:02:00 +0200, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

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

It desn't seem to difficult to me, just look at the code, they are 
iterations on subranges of iterators i1 and i2, actually they are the 
only kind of range combination that can be performed safely on general 
iterators.
The range combinations you propose are cumbersome rarely used and in 
general unsafe, I think that it is a bad idea add them to the object 
that is needed to get some foreach magic, and the most generic iterator.

atSamePlace returns true if two iterators have .left (or however you 
call it) at the same place (and in general this might not mean that 
they have the same address) can be implemented for almost all iterators 
in constant time (at the moment I cannot think of a counter example), 
and with it (as the code just above shows) you can define some 
subranges.

In the case in which you have a easily checkable total ordering between 
the elements then yes you do have all the all that it is needed to have 
a real range, and for this range object your subrange operations are 
safe, and I am not against them, just don't force them on every person 
that wants just to iterate on something.

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

That is exactly what I said it the sentence before, but in this 
sentence I am speaking about a bidirectional *iterator* that for me is 
an iterator that can move both back and forth.

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

they are simpler and describe a larger range of useful constructs 
ranges on liked list as I said are unsafe, which does not meant that 
ranges are not useful, just that there is a place also for simple 
iterators.

Iterators can be perfectly safe it is just the C++ idea of un-bundling 
the end from the iterator that makes it unsafe (an also more cumbersome 
to use).
If iterator for you for you is too connected with C++ view of it call 
them generators: a self containde object that can generate a sequence.

bidirectional iterators are a natural step in the progression of 
iterators also they can be implemented safely.

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

using atSamePlace you can do it safely on any kind of ranges, I think 
that the operation available should only be safe, and they can be safe, 
in general using atSamePlace, and if there is a quickly checkable total 
ordering (as in arrays for example) by never letting a range be larger 
than the union of two ranges.
One can then discuss if segment it (and the result would be an iterator 
but not a range) or choose only one side (keep it a range) if the two 
ranges are disjoint and have a hole between them.

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

I have written quite some code in my multidimensional array library ( 
http://github.com/fawzi/narray ) and I thought a lot about iterators, 
not only in D, but in the several languages that I know.
As with everybody I don't think to really see all implications of the 
interface, but I think that I understand them enough to participate 
meaningfully to this discussion.
Actually the moment I am really busy, but I am trying to say something 
because I think this discussion is important for the future of D, and I 
care about it.
I will try to give some real code, but I thought that my contribution 
was not so difficult to understand, but it is always like this to 
yourself one always seems clear ;)

Fawzi