Red black trees

[Frits van Bommel]

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.