Comment #0 by bearophile_hugs — 2011-01-13T15:55:50Z
In this issue I collect three enhancement requests for std.container.RedBlackTree.
---------------------
1) Sometimes where I define a RedBlack tree variable I don't know what items I will have to add to the tree. But currently it's not possible to create an empty tree, this doesn't work:
import std.container: RedBlackTree;
void main() {
auto t = RedBlackTree!int();
t.insert(1);
}
A possible solution:
import std.container: RedBlackTree;
void main() {
auto t = RedBlackTree!int.create();
t.insert(1);
}
---------------------
2) A handy wrapper for the constructor is useful, it avoids to specify the type:
import std.container: RedBlackTree;
void main() {
auto t = redBlackTree(1, 2, 3)
}
---------------------
3) The tree doesn't seem to contain a length. Using walkLength is an option, but a possible idea to allow a O(1) length 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=true)
Where the root node contains a length field.
The withLength template argument plus some static ifs allow to have zero overhead (in both runtime and memory used) for people that don't need the O(1) length. I think withLength is better true on default, because removing the O(1) length is an optimization.
Comment #1 by bearophile_hugs — 2011-01-13T16:06:38Z
Two more ideas:
4) If this code is meant as correct (the two Foos have the same x but different y), they you may add this example to the std_container.html page.
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.
---------------------
5) Built-in AAs can't work with approximate items (like floating point numbers) but a search tree is usable to create such set. So I suggest to add to the std.collections module a free templated function approxInsert(), its arguments are a tree, an item, and an approximate equality predicate.
Comment #2 by schveiguy — 2011-02-16T06:20:45Z
*** Issue 5586 has been marked as a duplicate of this issue. ***
Comment #3 by issues.dlang — 2011-02-16T23:54:25Z
The default constructor problem should be easily solvable once RedBlackTree becomes a class, as it appears that it soon will, since Andrei has decided to make the containers in std.container classes instead of structs.
Comment #4 by bearophile_hugs — 2011-03-21T13:17:39Z
*** Issue 5764 has been marked as a duplicate of this issue. ***