On Mon, 19 Jul 2010 12:21:36 -0400, Andrei Alexandrescu
<[email protected]> wrote:
By the way, I'm still eagerly waiting for your red-black tree
implementation.
Sorry for the delay, I've been very busy at work, and I wanted to slip in
a couple druntime fixes for array appending.
All that is left really is the unit testing, and making the docs more
phobos-ish.
I think it would be pure awesomeness if you massaged the red/black bit
inside one of the pointers. I figured out a way of doing that without
throwing off the garbage collector:
Yes, that works (BTW, you don't need the union, I hate unions :), just
substitute _bits for _left everywhere, I think it would even work with a
moving GC).
But I don't know how important it is to save that extra 4 bytes/node. A
redblack node already has 3 pointers in it, the flag puts it to 16 bytes
instead of overhead instead of 12. It certainly can be an implementation
choice.
I can look at left-leaning trees (I've had it on my todo list for
dcollections too).
-Steve
