clayasaurus wrote:
> I'd also like to add, that if you do give me the heads up that you would like to see this to phobos, give me time to...

I'd like to:

1) change RedBlackTree to take two type arguments: Key and Value types. The user needn't see the Node type at all.

2) enough unittest cases so that running it with -cov gives 100% coverage.

3) the following iterators: opApply (forward), opApplyReverse (reverse).

Walter Bright wrote:
> clayasaurus wrote:
>> I'd also like to add, that if you do give me the heads up that you would like to see this to phobos, give me time to...
> 
> I'd like to:
> 
> 1) change RedBlackTree to take two type arguments: Key and Value types. The user needn't see the Node type at all.

I don't know, wouldn't adding an explicit value type waste space when it's not needed?
You can always easily fake Key/Value by specializing T for a 'struct Tuple(Key, Value)' with comparison operators forwarded to the key, can't you?
Though you could also allow Value to be void and specialize the node type for that so it doesn't contain a Value in that case. Maybe even make void the default type for Value?

Frits van Bommel wrote:
> Walter Bright wrote:
>> clayasaurus wrote:
>>> I'd also like to add, that if you do give me the heads up that you would like to see this to phobos, give me time to...
>>
>> I'd like to:
>>
>> 1) change RedBlackTree to take two type arguments: Key and Value types. The user needn't see the Node type at all.
> 
> I don't know, wouldn't adding an explicit value type waste space when it's not needed?

It's almost always needed, it's there in the C++ std::map<>, and it eliminates the need for the user to have to know anything about the .Node class.

> You can always easily fake Key/Value by specializing T for a 'struct Tuple(Key, Value)' with comparison operators forwarded to the key, can't you?

Yes, but that's more work for the user.

> Though you could also allow Value to be void and specialize the node type for that so it doesn't contain a Value in that case. Maybe even make void the default type for Value?

Walter Bright wrote:
> Frits van Bommel wrote:
>> Walter Bright wrote:
>>> clayasaurus wrote:
>>>> I'd also like to add, that if you do give me the heads up that you would like to see this to phobos, give me time to...
>>>
>>> I'd like to:
>>>
>>> 1) change RedBlackTree to take two type arguments: Key and Value types. The user needn't see the Node type at all.
>>
>> I don't know, wouldn't adding an explicit value type waste space when it's not needed?
> 
> It's almost always needed, it's there in the C++ std::map<>, and it eliminates the need for the user to have to know anything about the .Node class.

Yeah, but it's also there in std::set<> (at least in GNU's implementation IIRC) wasting space.

>> You can always easily fake Key/Value by specializing T for a 'struct Tuple(Key, Value)' with comparison operators forwarded to the key, can't you?
> 
> Yes, but that's more work for the user.


Well, I suppose the user is likely to be some library class anyway:

struct Tuple(Key, Value) { ... }

class Map(Key, Value) : RedBlackTree!(Tuple(Key, Value)) {
	// Some extra methods
}



Will you at least consider something like this:

>> Though you could also allow Value to be void and specialize the node type for that so it doesn't contain a Value in that case. Maybe even make void the default type for Value?

Frits van Bommel wrote:
> Well, I suppose the user is likely to be some library class anyway:
> 
> struct Tuple(Key, Value) { ... }
> 
> class Map(Key, Value) : RedBlackTree!(Tuple(Key, Value)) {
>     // Some extra methods
> }

I use associative arrays, and I never use them like that <g>. They always have a key/value. Shouldn't rbtrees be simply an alternate container that has the same interface, but has different operating characteristics?

> Will you at least consider something like this:
> 
>>> Though you could also allow Value to be void and specialize the node type for that so it doesn't contain a Value in that case. Maybe even make void the default type for Value?

You could do that, though I'd call the result something else (like the Set type you mentioned).

Walter Bright wrote:
> Frits van Bommel wrote:
>> Well, I suppose the user is likely to be some library class anyway:
>>
>> struct Tuple(Key, Value) { ... }
>>
>> class Map(Key, Value) : RedBlackTree!(Tuple(Key, Value)) {
>>     // Some extra methods
>> }
> 
> I use associative arrays, and I never use them like that <g>.

Well, that's not ideal code obviously, but it was shorter to type into my newsreader :P. You get the idea, you can use RedBlackTrees with a special value type to implement maps.

> They
> always have a key/value. Shouldn't rbtrees be simply an alternate container that has the same interface, but has different operating characteristics?

I myself never considered RedBlackTrees as associative arrays, just as a data structure that can be used to implement them. But also to implement sets (or bags (multisets) and multimaps if you allow duplicates).

>> Will you at least consider something like this:
>>
>>>> Though you could also allow Value to be void and specialize the node type for that so it doesn't contain a Value in that case. Maybe even make void the default type for Value?
> 
> You could do that, though I'd call the result something else (like the Set type you mentioned).

But I think it should be possible to implement a Set using a RedBlackTree without wasting space in the nodes.

And I think the code wouldn't be so much different, so a few 'static if(is(Value == void))' would likely avoid quite a bit of code duplication.

Walter Bright wrote:
> Red black trees are one of those basic collection types that should be available. Anyone want to write one for D for placement into Phobos?

Out of curiosity, what is wrong with the red-black tree Ben Hinkle published as a part of MinTL some 2 years ago?

/Oskar

clayasaurus wrote:

> clayasaurus wrote:
> 
>> Walter Bright wrote:
>>
>>> clayasaurus wrote:
>>>
>>>> Walter Bright wrote:
>>>>
>>>>> clayasaurus wrote:
>>>>>
>>>>>> clayasaurus wrote:
>>>>>>
>>>>>>> My templated red black tree version: http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/templates/redblacktree.d 
>>>>>>>
>>>>>>>
>>>>>>> I've have only done minimal testing with it, but it hasn't broken on me yet.
>>>>>>>
>>>>>>> ~ Clay
>>>>>>>
>>>>>>
>>>>>> RBTree is public domain.
>>>>>
>>>>>
>>>>> But the redblacktree.d code says it's copyrighted.
>>>>
>>>>
>>>> I just explicitly put it under public domain. :)
>>>
>>>
>>> I hate to be pedantic about this, but this is very important.
>>>
>>> If this is based on "Original code and author" at http://eternallyconfuzzled.com/tuts/redblack.html then that needs to be public domain, too. The page, at the bottom, says it's copyrighted.
>>
>>
>> I emailed the author about it, and the author said to me...
>>
>> "All of the code is PD unless otherwise stated. I believe each tutorial mentions this at the start, and including it in the code snippets would be redundant and waste space."
>>
>> His email is ' happyfrosty at hotmail.com ' if you want to double check.  I told him that the words public domain never appear on the red black tree page and that he should add it.
>>
>> ~ Clay
>>
> 
> I'd also like to add, that if you do give me the heads up that you would like to see this to phobos, give me time to...
> 
> 0) Touch up code, fix up indenting.
> 
> 1) Change 'merge' name to 'union', add 'intersect' function, and add any other standard tree functions that are missing

union is a keyword so I don't think this would work.

-David

Oskar Linde wrote:
> Walter Bright wrote:
>> Red black trees are one of those basic collection types that should be available. Anyone want to write one for D for placement into Phobos?
> 
> Out of curiosity, what is wrong with the red-black tree Ben Hinkle published as a part of MinTL some 2 years ago?
> 
> /Oskar

Probably nothing except my ignorance of it. Is it public domain? Does it work? Where can I see the code?

~ Clay

Oskar Linde wrote:
> Out of curiosity, what is wrong with the red-black tree Ben Hinkle published as a part of MinTL some 2 years ago?

Nothing except my ignorance of it.