www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - tango iterators and related questions

reply MLT <none anon.com> writes:
D is really great. I am trying to implement a medium sized project to get to
know it.
For this I need a sorted data structure, with cheap search, and somewhat cheap
forward and backward traversing.

I thought I should use tango (though it is a bit confusing that there is so
much overlap between tango and phobos...)
I wanted to use SortedMap. However, I can not figure out how to use the
Iterators of SortedMap. 

When I place the Iterator somewhere, how do I find the element (key+value)
where it's at?
I see how to get the next key and value (using i.next(k,v)), but I can not see
how to get the current one, and how to go up and down the keys. I need to find
a certain place, and then look at the key & value above and below that
location....

I saw that dcollections does provide this ability, with its cursor.

So new I'm wondering if to use tango+dcollections, phobos+dcollections, or just
pick and choose.

I would also really like to stay as standard as possible.

What do you usually use?
Apr 21 2009
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 21 Apr 2009 08:46:18 -0400, MLT <none anon.com> wrote:


 D is really great. I am trying to implement a medium sized project to  
 get to know it.
 For this I need a sorted data structure, with cheap search, and somewhat  
 cheap forward and backward traversing.

 I thought I should use tango (though it is a bit confusing that there is  
 so much overlap between tango and phobos...)
 I wanted to use SortedMap. However, I can not figure out how to use the  
 Iterators of SortedMap.

 When I place the Iterator somewhere, how do I find the element  
 (key+value) where it's at?
 I see how to get the next key and value (using i.next(k,v)), but I can  
 not see how to get the current one, and how to go up and down the keys.  
 I need to find a certain place, and then look at the key & value above  
 and below that location....

 I saw that dcollections does provide this ability, with its cursor.

 So new I'm wondering if to use tango+dcollections, phobos+dcollections,  
 or just pick and choose.

 I would also really like to stay as standard as possible.

 What do you usually use?


dcollections+tango should do the trick for you.  It is incidentally what I  
use (of course I wrote dcollections, so big surprise there ;)

You can submit an enhancement request to Tango to see if there is interest  
in adding bi-directional iterator functionality to the SortedMap.  I know  
there is some bidirectional support in e.g. circular lists.

-Steve
Apr 21 2009
parent reply MLT <none anon.com> writes:
Steven Schveighoffer Wrote:


 On Tue, 21 Apr 2009 08:46:18 -0400, MLT <none anon.com> wrote:



 dcollections+tango should do the trick for you.  It is incidentally what I  
 use (of course I wrote dcollections, so big surprise there ;)
 


Good! I just managed to compile my first program using 0.02
BTW: the svn version gave me errors like:
/usr/local/include/d/dcollections/TreeMap.d(96): Error: undefined identifier
DefaultCompare
Maybe it has something to do with D2? I'm not sure.
0.02 worked, except that I had to manually ranlib the resulting library.


 You can submit an enhancement request to Tango to see if there is interest  
 in adding bi-directional iterator functionality to the SortedMap.  I know  
 there is some bidirectional support in e.g. circular lists.
 


Yes. But the problem isn't so much the bi-directionality, and more just
accessing where I currently am. Though of course with bi-directional iterators,
I could go next, then prev, and see what I have where I am. Because next and
prev are O(logN) this isn't SO cheap though.
Apr 21 2009
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 21 Apr 2009 10:08:03 -0400, MLT <none anon.com> wrote:


 Steven Schveighoffer Wrote:


 On Tue, 21 Apr 2009 08:46:18 -0400, MLT <none anon.com> wrote:



 dcollections+tango should do the trick for you.  It is incidentally  
 what I
 use (of course I wrote dcollections, so big surprise there ;)


 Good! I just managed to compile my first program using 0.02
 BTW: the svn version gave me errors like:  
 /usr/local/include/d/dcollections/TreeMap.d(96): Error: undefined  
 identifier DefaultCompare
 Maybe it has something to do with D2? I'm not sure.
 0.02 worked, except that I had to manually ranlib the resulting library.


No, I was in the middle of reorganizing the interface hierarchy (among  
other things) when I discovered a blocker bug:  
http://d.puremagic.com/issues/show_bug.cgi?id=2061

I stopped working on it in hopes the bug would be fixed, but it hasn't  
been :(  If you are a member of digitalmars's bug tracker, vote for the  
issue, maybe it will get more attention!


 You can submit an enhancement request to Tango to see if there is  
 interest
 in adding bi-directional iterator functionality to the SortedMap.  I  
 know
 there is some bidirectional support in e.g. circular lists.


 Yes. But the problem isn't so much the bi-directionality, and more just  
 accessing where I currently am. Though of course with bi-directional  
 iterators, I could go next, then prev, and see what I have where I am.  
 Because next and prev are O(logN) this isn't SO cheap though.


Tango iterators tie the "move next" and "get" operations together, similar  
to Java's.  I don't know how open Kris would be to changing that, but you  
can always submit an enhancement request to see if it is accepted.  That  
would be my recommendation.

And O(logN) is very very cheap ;)  Especially to be able to have a sorted  
dictionary.  If you don't need O(logN) insertion and deletion (i.e. if you  
are not going to continually update the dictionary), you could consider  
having a sorted array (binary search for lookup).

-Steve
Apr 21 2009