Red black trees

[clayasaurus]

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

2) Add option to allow duplicate data in tree (thinking a simple counter 
to count how many of the same type there are in a node)

3) Create another version that will allow the user to specify the key 
type to sort by (could try to match STL set/map naming scheme, or use 
RedBlackTree and RedBlackTreeKey or RBTree RBTreeKey)

4) Heavy testing

5) Have members of the community review and test it for themselves (only 
those that want to ;) )

I wouldn't want anything 'rushed' into phobos.

~ Clay