About std.container.RedBlackTree

[bearophile]

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#

---------------------

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);
}



This gives a similar error:

import std.container: RedBlackTree;
struct Foo {
    RedBlackTree!int t;
    void initialize() {
        t = RedBlackTree!int(1);
    }
}
void main() {}

---------------------

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);
}

---------------------

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

---------------------

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

---------------------

In theory an helper redBlackTree() function allows to write just this, with no need to write types:

redBlackTree(1, 2, 3)

---------------------

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.

---------------------

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)

---------------------

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.

---------------------

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;
        }
    }
}

---------------------

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.

---------------------

Bye and thank you,
bearophile