• Andrei Alexandrescu (6/6) Nov 09 2009 I consider changing a bit D's range model following the better
• Lutger (25/35) Nov 10 2009 I thoroughly enjoyed the article, thank you in particular for making thi...
• Steven Schveighoffer (30/35) Nov 10 2009 Very good article.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

I consider changing a bit D's range model following the better 
understanding reflected in this article:

http://erdani.com/publications/on-iteration.html

If you have any thoughts and if you can help with the implementation, 
please let us know.


Andrei

Lutger <lutger.blijdestijn gmail.com> writes:

Andrei Alexandrescu wrote:

 I consider changing a bit D's range model following the better
 understanding reflected in this article:
 
 http://erdani.com/publications/on-iteration.html
 
 If you have any thoughts and if you can help with the implementation,
 please let us know.
 
 
 Andrei

I thoroughly enjoyed the article, thank you in particular for making this 
material accessible to non computer scientists like myself. 

More questions than thoughts if I may, do feel free to ignore them, these 
are just things I wonder about:

- how to do ranges over a tree?
My first thought was that a tree would define preorder / inorder / postorder 
ranges, and then perhaps visitors for more complex algorithms. But in the 
'iterators must go' keynote you mentioned implementing traversal over trees 
by popFront() taking a parameter indicating the branch to go to. Can you or 
anybody else shed more light on how this will work out? What about graphs?

- ranges over immutable data structures
I tried making an immutable linked list and stack (not as simple as I 
thought) with range support. Ranges must be mutable though. So I take it 
that ranges are not usually supposed to be shared, rather they be 
consumable, local views into immutable data structures instead? 

This leads to a broader question: is it possible to model some support for 
concurrency in ranges? So that algorithms can possibly choose a particular 
implementation based on the concurrent properties of a range? Perhaps this 
relates to the separation between iteration and access as well.

- why is a UTF-string iterator bidirectional and why is that unexpected?

- Is there already a standard way to implement a default range for a 
container? 

I have tons more questions, but I'll try to work them out for myself first 
or post them in .learn.

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

On Mon, 09 Nov 2009 20:53:01 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 I consider changing a bit D's range model following the better  
 understanding reflected in this article:

 http://erdani.com/publications/on-iteration.html

 If you have any thoughts and if you can help with the implementation,  
 please let us know.

Very good article.

I think the idea of separating access from traversal is a very good one.   
I still don't like the idea of having a "save" method vs. just assignment  
but I don't have a better idea right now.

One note:  As you know I think iterators are still useful for keeping  
pointers to individual elements.  One other drawback from storing  
1-element ranges as a substitute is that they may not remain one-element  
ranges.

For instance, if you had a sorted map, stored as a RB-tree, a one element  
range would undoubtedly consist of a begin element and an end element,  
which would be the next largest element.  If you inserted an element that  
was between those two, suddenly your 1-element range becomes a 2-element  
range.  Although you can simply say that all ranges are invalidated when  
the underlying container is modified, an iterator-based solution can say  
that iterators always remain valid when the container is added to.  That  
allows certain types of logic that wouldn't be as efficient with ranges.

What about adding a "marker" type that has the ability to reference the  
data but not to traverse to another element (except by assignment)?  
Basically a rebindable reference.  You can always get a marker to a  
copyable range's front element, and then a container can use 2 markers to  
make a traversable range, or use it as the primitive for functions like  
remove or insert (as an insert location), and 3-legged functions that  
don't map easily into 2-range functions.

I'm thinking this is how I'm going to implement ranges in dcollections.   
Currently I support cursors, which are akin to C++ iterators (my Iterator  
objects are akin to Java iterators, and support only foreach).  But what I  
might do is change them into markers, and make ranges out of 2 of them.

-Steve