www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Red black trees

reply Walter Bright <newshound digitalmars.com> writes:
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?
Oct 20 2006
next sibling parent reply Kyle Furlong <kylefurlong gmail.com> writes:
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"? Wouldn't it be better to actually bless a community based standard library effort, than take submissions piecemeal whenever you feel like it? Sure red black trees are a basic collection that most people will need at some point, but why isn't it being made part of a larger templated collections portion of the library? I know for a fact that there is a group of people who would gladly take up the standard library torch and run with it, people who would be accountable to you and the community, with open source, documentation, and a roadmap for development. Its this kind of lack of vision which I think will retard D's evolution into a production language, so that it forever remains at the level of hobbyist hackery.
Oct 20 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
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"? Wouldn't it be better to actually bless a community based standard library effort, than take submissions piecemeal whenever you feel like it? Sure red black trees are a basic collection that most people will need at some point, but why isn't it being made part of a larger templated collections portion of the library? I know for a fact that there is a group of people who would gladly take up the standard library torch and run with it, people who would be accountable to you and the community, with open source, documentation, and a roadmap for development. Its this kind of lack of vision which I think will retard D's evolution into a production language, so that it forever remains at the level of hobbyist hackery.

I would welcome it if you (or anyone else) makes a proposal for a set of to-be-implemented collection classes.
Oct 20 2006
next sibling parent Kyle Furlong <kylefurlong gmail.com> writes:
Walter Bright wrote:
 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"? Wouldn't it be better to actually bless a community based standard library effort, than take submissions piecemeal whenever you feel like it? Sure red black trees are a basic collection that most people will need at some point, but why isn't it being made part of a larger templated collections portion of the library? I know for a fact that there is a group of people who would gladly take up the standard library torch and run with it, people who would be accountable to you and the community, with open source, documentation, and a roadmap for development. Its this kind of lack of vision which I think will retard D's evolution into a production language, so that it forever remains at the level of hobbyist hackery.

I would welcome it if you (or anyone else) makes a proposal for a set of to-be-implemented collection classes.

I don't have the expertise to design them but Doug Lea does: http://g.oswego.edu/dl/classes/collections/ Perhaps his collection design could form the basis for a D collections library, templated of course.
Oct 20 2006
prev sibling parent reply John Demme <me teqdruid.com> writes:
Walter Bright wrote:

 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"? Wouldn't it be better to actually bless a community based standard library effort, than take submissions piecemeal whenever you feel like it? Sure red black trees are a basic collection that most people will need at some point, but why isn't it being made part of a larger templated collections portion of the library? I know for a fact that there is a group of people who would gladly take up the standard library torch and run with it, people who would be accountable to you and the community, with open source, documentation, and a roadmap for development. Its this kind of lack of vision which I think will retard D's evolution into a production language, so that it forever remains at the level of hobbyist hackery.

I would welcome it if you (or anyone else) makes a proposal for a set of to-be-implemented collection classes.

Walter, please take a look at mango.containers in Mango's SVN: http://dsource.org/projects/mango/browser/trunk/mango/containers It's meant to be a standard containers library similar to the Java collections, but in more of a D style. It uses mango.locks to implement some thread-safe containers, so it's integrated into mango, but I feel it will be appropriate as a generic library. It's not done yet, however. There are still signifigant efforts yet to go in documentation, container implementations, and algorithms (I've only got array quicksort and reverse). There's some demo code I use for unittesting at: http://dsource.org/projects/mango/browser/trunk/mango/test/containers.d I'd also like to mention (as long as I have your ear...err.. eyes) that most of Mango would do well in the standard library, and I think you should consider releasing Mango along with the compiler, as it is a very well put-together and cohesive library. It's got very efficient class-based IO support with integrated encoding conversion, a SAX parser (beta- my work), soon to have a decent DOM parser (my work- built on top of SAX parser), a logging framework, semaphore classes, http client, and other things. I would love to see large portions of Mango replace large parts of Phobos, and the rest of it to become the javax of Phobos (and optional, extended part of the standard library) since not everyone needs an http server or servlet support. I think we need to include a standard library such as Mango in order to attract modern users used to the likes of Java and C# libraries. <End Mango plug> Thoughts? -- ~John Demme me teqdruid.com http://www.teqdruid.com/
Oct 21 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
John Demme wrote:
 Thoughts?

Mango is obviously a well thought out and excellent library. If you and Kris are game, I am.
Oct 21 2006
next sibling parent Kyle Furlong <kylefurlong gmail.com> writes:
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.

The plot thickens.
Oct 21 2006
prev sibling parent reply John Demme <me teqdruid.com> writes:
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/
Oct 23 2006
parent Sean Kelly <sean f4.ca> writes:
John Demme wrote:
 Walter Bright wrote:
 
 John Demme wrote:
 Thoughts?

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
Oct 23 2006
prev sibling next sibling parent reply "Frank Benoit (keinfarbton)" <benoit tionex.removethispart.de> writes:
 Did anyone else read this and go "WTH"? 

No, I though: "yes, excellent." Motivating some ppl to contribute, is surely not a wrong thing.
Oct 20 2006
parent Kyle Furlong <kylefurlong gmail.com> writes:
Frank Benoit (keinfarbton) wrote:
 Did anyone else read this and go "WTH"? 

No, I though: "yes, excellent." Motivating some ppl to contribute, is surely not a wrong thing.

Maybe I did come across as a little harsh, I do believe that in absence of a community driven, roadmap based development effort, this is better than a closed, Walter-written std lib.
Oct 20 2006
prev sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
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"?

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.
Oct 22 2006
prev sibling next sibling parent reply clayasaurus <clayasaurus gmail.com> writes:
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. ~ Clay S.
Oct 21 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
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/tem lates/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.
Oct 21 2006
parent reply clayasaurus <clayasaurus gmail.com> writes:
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/tem lates/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
Oct 24 2006
parent reply clayasaurus <clayasaurus gmail.com> writes:
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/tem lates/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/temp ates/redblacktree.d I've have only done minimal testing with it, but it hasn't broken on me yet. ~ Clay

RBTree is public domain.
Oct 25 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
clayasaurus wrote:
 clayasaurus wrote:
 My templated red black tree version: 
 http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/temp
ates/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.
Oct 26 2006
parent reply clayasaurus <clayasaurus gmail.com> writes:
Walter Bright wrote:
 clayasaurus wrote:
 clayasaurus wrote:
 My templated red black tree version: 
 http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/temp
ates/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. :)
Oct 26 2006
next sibling parent Walter Bright <newshound digitalmars.com> writes:
clayasaurus wrote:
 Walter Bright wrote:
 clayasaurus wrote:
 clayasaurus wrote:
 My templated red black tree version: 
 http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/temp
ates/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. :)

Thank you!
Oct 26 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
clayasaurus wrote:
 Walter Bright wrote:
 clayasaurus wrote:
 clayasaurus wrote:
 My templated red black tree version: 
 http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/temp
ates/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.
Oct 26 2006
parent reply clayasaurus <clayasaurus gmail.com> writes:
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/temp
ates/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
Oct 26 2006
next sibling parent reply clayasaurus <clayasaurus gmail.com> writes:
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/temp
ates/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
Oct 26 2006
next sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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...
 
 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)

Better to just add nodes. opEquals may not test all the data in the type, and even if it does object identity may still matter.
 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)

Maybe also non-modifiable versions or adaptors?
 4) Heavy testing

Always a good idea.
 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.

Some other things you may want to think about: 'D-ify' the code some more * in/out contracts * invariant { assert(isValid()); } (or is this ever invalid when a public member is called internally?) * Some ints --> bools (at least Node.red, isRed(), isValid(), some parameters). The original code was in C which doesn't have bools, but D does, so you might as well use them. Actually, on a quick search through the code, it looks like almost all ints are used as bools. size, getSize() and assertNode() seem to be the only exceptions. Also: * It looks like your createCopy does an in-order traversal and adds copies of nodes to the tree. Doesn't this incur a lot of balancing overhead that's totally unnecessary since the tree being copied is balanced already? I'd just add a Node constructor that copies a given node (and recurses on its non-null children). --- Wait, createCopy is also used for merge(). In that case, just keep it for that (maybe rename it addAll?) but duplicate() can be done more efficiently, I think. * Doesn't opIn_r typically return a T*? I think it at least does for AAs. Might be something to think about since you've already looked up that data anyway and the user might want it (and if not, no big deal). * Overload some Object functions? opEquals at least, and maybe override toString and toHash as well.
Oct 26 2006
prev sibling next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
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).
Oct 26 2006
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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?
Oct 26 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
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?

Oct 26 2006
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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?


Oct 26 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
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).
Oct 26 2006
parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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.
Oct 26 2006
prev sibling parent David Medlock <noone nowhere.com> writes:
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/temp
ates/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
Oct 27 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
clayasaurus wrote:
 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."

That's a little frustrating, because the page itself says it's copyrighted, so it's a tad ambiguous. I could assume from his email that the code is pd and the copyright only refers to the text, but I'd really rather have an *explicit* statement that the code on that page is pd.
 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.

Yes. This merry-go-round is important, otherwise at some arbitrary future date we could get the rug pulled out from under us.
Oct 26 2006
parent Walter Bright <newshound digitalmars.com> writes:
Walter Bright wrote:
 Yes. This merry-go-round is important, otherwise at some arbitrary 
 future date we could get the rug pulled out from under us.

I've dealt with lawyers, judges, and contract disputes before. Nothing works better than EXPLICIT and DIRECT statements about the status. Any ambiguousness winds up costing one plenty in legal fees. Something like: I, <your name here>, am the author of this and I place it into the Public Domain. is pretty hard to argue with.
Oct 26 2006
prev sibling next sibling parent reply "Craig Black" <cblack ara.com> writes:
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 
Oct 23 2006
next sibling parent clayasaurus <clayasaurus gmail.com> writes:
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
Oct 23 2006
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
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
Oct 24 2006
parent reply "Craig Black" <cblack ara.com> writes:
 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
Oct 25 2006
parent Sean Kelly <sean f4.ca> writes:
Craig Black wrote:
 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?

Not that I know of. MS wanted the checking in no matter what, and Dinkumware complied. But it's worth checking the headers to be sure. Sean
Oct 25 2006
prev sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
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
Oct 27 2006
next sibling parent clayasaurus <clayasaurus gmail.com> writes:
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
Oct 27 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
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.
Oct 29 2006