Ellery Newcomer Wrote:

> On 05/19/2010 03:07 PM, Steven Schveighoffer wrote:
> > I haven't the slightest what a bimap is :)  I am not an expert in collections or data structures, I just reimplement things I have understood.  My implementations are basically copied from my algorithm book, and refined as much as I can do.
> 
> I think boost.bimap is where I saw it, though I don't don't use c++.
> 
> I think it's a map, with values->keys is also a map

That sounds interesting, it might be doable like this:

interface Bimap(K, V) : Map(K, V), Map(V, K)

I'll have a look at it some time.

> 
> I have a simple child/sibling tree implementation which I could probably dust off and polish up if you want it. The method for visiting the elements is kind of weird, though. And I don't know that it exactly fits the mold of a reference container. Maybe with cursors.

With opApply, you should have few restrictions on iteration.  Technically, cursors are optional since they are part of the concrete class, but it probably wouldn't make it into dcollections proper without them.

> 
> Ugh, I just noticed LinkList doesn't work with interfaces.

You mean

interface I {}
auto list = new LinkList!I;

??
Please file a ticket w/ test case, it should work.

-Steve

On 05/19/2010 03:55 PM, Steven Schveighoffer wrote:
> Ellery Newcomer Wrote:
>>
>> I have a simple child/sibling tree implementation which I could probably
>> dust off and polish up if you want it. The method for visiting the
>> elements is kind of weird, though. And I don't know that it exactly fits
>> the mold of a reference container. Maybe with cursors.
>
> With opApply, you should have few restrictions on iteration.  Technically, cursors are optional since they are part of the concrete class, but it probably wouldn't make it into dcollections proper without them.
>

When I was using it, it was usually more than an iteration that I found I needed. I think I had preorder traversals and postorder traversals with the ability to define actions at parent -> child, child -> sibling, and child -> parent transitions, access to the stack and some of the history of what had been visited. On the whole, it required heavy exposure of the structure of the tree. A wrapper around the tree nodes doesn't make a lot of sense, and if you don't have a wrapper, cursors don't really make a lot of sense either.

Random thought: wouldn't a child/sibling tree be a good base for implementing tries?

>>
>> Ugh, I just noticed LinkList doesn't work with interfaces.
>
> You mean
>
> interface I {}
> auto list = new LinkList!I;
>
> ??
> Please file a ticket w/ test case, it should work.
>
> -Steve

indeed it should, but D doesn't like you :)

http://www.dsource.org/projects/dcollections/ticket/4