About std.container.RedBlackTree

[Steven Schveighoffer]

On Mon, 10 Jan 2011 18:14:31 -0500, bearophile <bearophileHUGS at lycos.com>  
wrote:

> I've had to use a search tree, so RedBlackTree was the right data  
> structure. It seems to do what I need, so thank you for this useful data  
> structure. Some of the things I write here are questions or things that  
> show my ignorance about this implementation.
>
> ---------------------
>
> Please add some usage examples to this page, this is important and helps  
> people reduce a lot the number of experiments to do to use this tree:
> http://www.digitalmars.com/d/2.0/phobos/std_container.html#

I will do this, when I have some free time.  If you want to submit some  
examples, I would gladly include them.

>
> ---------------------
>
> This doesn't seem to work, it gives a forward reference error:
>
> import std.container: RedBlackTree;
> RedBlackTree!int t;
> void main() {
>     t = RedBlackTree!int(1);
> }

Grrr... I had issues with forward references (you can see from this  
comment:  
http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L4071),  
I thought by reordering the functions I had fixed it, but apparently, it  
resurfaces under certain conditions.

Please vote for that bug.   
http://d.puremagic.com/issues/show_bug.cgi?id=2810

I don't really know what to do about fixing it.  Most likely any 'fix' I  
try will result in some other situation not compiling.  I probably should  
just avoid using auto, not being able to declare a red black tree as a  
global variable is a huge limitation.

> ---------------------
>
> I need to create an empty tree and add items to it later (where I  
> declare a fixed-sized array of trees I don't know the items to add). How  
> do you do it?
> This code doesn't work:
>
>
> import std.container: RedBlackTree;
> void main() {
>     auto t = RedBlackTree!int();
>     t.insert(1);
> }

RedBlackTree must be initialized with a constructor.  Otherwise, your root  
node is null.  I chose this path instead of checking for null on every  
function.

I realize the mistake -- you cannot create an empty tree, because you  
cannot have a default constructor.

I have another function that I use to help create trees during unit tests  
because IFTI can be weird.  I will make this function public and always  
present, then you can create an empty tree like this:

auto t = RedBlackTree!int.create();

If Andrei decides eventually that containers should be classes, then this  
problem goes away.

Please bugzillize this

>
> ---------------------
>
> Is the tree insert() method documented in the HTML docs?

I thought this would do it, but apparently it doesn't:

http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L4457

I will try to make those docs show up.

> ---------------------
>
> A tree is a kind of set, so instead of "insert()" I'd like a name like  
> "add()".
> (But maybe this is not standard in D).

The function names must be consistent across containers, because the point  
is that complexity and semantic requirements are attached to the function  
name.  The function names were decided long ago by Andrei, and I don't  
think insert is a bad name (I believe std::set and std::map in C++ STL  
uses insert).

> ---------------------
>
> In theory an helper redBlackTree() function allows to write just this,  
> with no need to write types:
>
> redBlackTree(1, 2, 3)

Yes, this should be done.  Please make a bugzilla report.  In fact, this  
can extend to all std.container types.

> ---------------------
>
> I have tried to use printTree(), but I have failed. I don't know what to  
> give to it and the docs don't say that it requires -unittest
>
> If it's a private debug function then there's no need to give it a ddoc  
> comment.

It is a private debug function, only enabled when version = doRBChecks is  
enabled.  When developing the red black node, the red-black algorithms to  
fix the tree are very complex and error prone to write.  This function  
basically printed the tree layout in a horribly ugly fashion when the  
red-black properties were not preserved.  It helped me find bugs, but is  
mostly no-longer needed unless I try some more optimizations.

Please ignore the function.  I will make sure the comment is not ddoc'd.

>
> ---------------------
>
> I've seen that the tree doesn't seem to contain a length. Using  
> walkLength is an option, but a possible idea is to replace:
> struct RedBlackTree(T,alias less = "a < b",bool allowDuplicates = false)
>
> With:
> struct RedBlackTree(T, alias less="a < b", bool allowDuplicates=false,  
> bool withLength=false)

The reason for this is to keep it a reference-type (pImpl style), but I  
realize that I can easily fix this (I can just make the root node contain  
a length field).  Please file a bugzilla to add length.

> ---------------------
>
> If you need to add many value nodes quickly to the tree a memory pool  
> may speed up mass allocation. This has some disadvantages too.

I have done this in dcollections, and it helps immensely in node-based  
containers.  It is not clear to me how std.container will incorporate  
these types of things, so Andrei and I decided to just defer it for now.   
RedBlackTree is easily modified to use an allocator, all allocation and  
de-allocations are done via a centralized function.  In fact, the same  
RBNode is used in dcollections.

The allocator I created in dcollections is also the default allocator in  
Tango containers too.  I anticipate that something like it will eventually  
make its way into phobos.

> ---------------------
>
> If I have to create a set of epsilon-approximate floating point numbers,  
> what's the most efficient way to use a RedBlackTree to see if it  
> contains a value x (or values very close to x), and othrwise add x to  
> the tree?
>
> I was thinking about something like this, but it doesn't look very good  
> because it performs three lookups (this function returns the number of  
> items added):
>
>
> int approxInsert(RedBlackTree!double set, double x, double epsilon) {
>     if (x in set) {
>         return 0;
>     } else {
>         auto nextOnes = set.upperBound(x);
>         if (!nextOnes.empty() && (nextOnes.front - x) < epsilon) {
>             return 0;
>         }
>         auto precedentOnes = set.lowerBound(x);
>         if (!precedentOnes.empty() && (x - precedentOnes.back) <  
> epsilon) {
>             return 0;
>         } else {
>             set.insert(x);
>             return 1;
>         }
>     }
> }

What about changing the predicate?  I know it will likely violate the  
requirements of a strict ordering, but it should probably work.

> ---------------------
>
> This code runs with no errors, is this correct? The two Foos have the  
> same x but different y:
>
>
> import std.container: RedBlackTree;
> struct Foo {
>     int x, y;
> }
> void main() {
>     auto t = RedBlackTree!(Foo, "a.x < b.x")(Foo(1,1));
>     assert(Foo(1,2) in t);
> }
>
> (In practice this looks like a tree map instead of a tree set.)
> If this is correct then I suggest to add this example to the  
> std_container.html page.

Yes, the intention is that you can create a map type in this fashion.  If  
you define a predicate, then it is up to you to ensure the predicate makes  
sense for you.

I'm unsure whether a map type could actually be implemented using  
RedBlackTree, but if it's not possible, I will make it possible.

> ---------------------
>
> Bye and thank you,
> bearophile

Thank you for your detailed analysis!  I will hope to fix all the problems  
soon.

-Steve