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.

Kyle Furlong 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?
> 
> Did anyone else read this and go "WTH"?
<snip>

Yes.

And to all the rest:

http://en.wikipedia.org/wiki/Red-black_tree

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:-@ C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

Sounds like you have plenty of good candidates.  However, I have written a C++ template that has been used and tested extensively.  It is quite simple so it could be ported very quickly if necessary.

It uses the "AA tree" algorithm.  An AA tree a simplified red-black tree that is much easier to code.  The drawback is that it is supposed to be a little slower than a full red-black tree implementation.  But for some reason all my benchmarks show that it is faster than Microsoft's std::set implementation.

Anyway, I could do it in D if you are intereseted but I won't bother if you already have a solution.

-Craig

Walter Bright wrote:

> John Demme wrote:
>> Thoughts?
> 
> Mango is obviously a well thought out and excellent library. If you and Kris are game, I am.

Wow.  Yes- I am game, but I can't speak for Kris whom I have not heard from in awhile.  I sent him an email Saturday night, but haven't heard back from him yet.  Does anyone know if he is away- roadtripping the country again or something?

I'll start putting some of my thoughts together, but would rather not propose anything until I talk to some of the other people involved.

Thanks for that big burst of hope, Walter!

-- 
~John Demme
me@teqdruid.com
http://www.teqdruid.com/

John Demme wrote:
> Walter Bright wrote:
> 
>> John Demme wrote:
>>> Thoughts?
>> Mango is obviously a well thought out and excellent library. If you and
>> Kris are game, I am.
> 
> Wow.  Yes- I am game, but I can't speak for Kris whom I have not heard from
> in awhile.  I sent him an email Saturday night, but haven't heard back from
> him yet.  Does anyone know if he is away- roadtripping the country again or
> something?

Yes, he is :-)


Sean

Craig Black wrote:
> Sounds like you have plenty of good candidates.  However, I have written a C++ template that has been used and tested extensively.  It is quite simple so it could be ported very quickly if necessary.
> 
> It uses the "AA tree" algorithm.  An AA tree a simplified red-black tree that is much easier to code.  The drawback is that it is supposed to be a little slower than a full red-black tree implementation.  But for some reason all my benchmarks show that it is faster than Microsoft's std::set implementation.
> 
> Anyway, I could do it in D if you are intereseted but I won't bother if you already have a solution.
> 
> -Craig 
> 

I'd be interested in the algorithm, and I'm quite capable of porting as well :)

~ Clay

Craig Black wrote:
> Sounds like you have plenty of good candidates.  However, I have written a C++ template that has been used and tested extensively.  It is quite simple so it could be ported very quickly if necessary.
> 
> It uses the "AA tree" algorithm.  An AA tree a simplified red-black tree that is much easier to code.  The drawback is that it is supposed to be a little slower than a full red-black tree implementation.  But for some reason all my benchmarks show that it is faster than Microsoft's std::set implementation.

If you're testing against VS 2005 that may be somewhat related to checked iterators, depending on how you're doing the testing.  The checking occurs even in release builds.


Sean

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

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.

> If you're testing against VS 2005 that may be somewhat related to checked iterators, depending on how you're doing the testing.  The checking occurs even in release builds.

Is there an option to turn it off?

-Craig