Red black trees

[clayasaurus]

clayasaurus wrote:
> Walter Bright wrote:
>> clayasaurus 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?
>>>
>>> I've been trying to write one based off of a C++ version over the the 
>>> code project (actual link is in the code file).
>>>
>>> http://www.dsource.org/projects/arcgames/browser/trunk/physics/d/binarytree.d 
>>>
>>>
>>> However, after I add the third node, I get an access violation. I 
>>> haven't had much time to really sit down and debug it, all I know is 
>>> that somehow I am trying to access a null object which causes an 
>>> access violation. Eventually I'll get it to work, just a matter of time.
>>>
>>> ---
>>>
>>> I also have a doubly linked list with a mergesort (I wrote the list 
>>> but I did not write the merge sort implemtation, again the link where 
>>> I got it from is in there). It seems to work well
>>> http://dsource.org/projects/freeuniverse/browser/trunk/freeuniverse/arc/templates/dlinkedlist.d 
>>>
>>>
>>> Then again, I'm sure the it would need some fixing up and heavy 
>>> testing, plus making sure that the places I got some of the code from 
>>> would allow it to be licensed under public domain before even 
>>> thinking about putting it in a std lib. Just thought I'd mention them 
>>> in case anyone finds it useful.
>>
>> That is great! But the license is critical.
> 
> I found out that the merge sort algorithm in my doubly linked list is 
> under the MIT license ( 
> http://www.opensource.org/licenses/mit-license.php ).
> 
> Since I was having problems with the other red black tree algorithms 
> presented, I finally found a nice resource for the algorithms ( 
> http://eternallyconfuzzled.com/tuts/redblack.html ).
> 
> The only problem is, on the page, it doesn't explicitly say whether the 
> code is public domain or not. I sent an email to the author about it. My 
> best guess is that it is public domain, since the author releases all 
> his libraries on his site as such.
> 
> 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.