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

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?


 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
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"?


<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.
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