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?

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

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.

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