std.container: RedBlackTree questions

[monarch_dodra]

On Thursday, 1 August 2013 at 12:27:51 UTC, Ivan Kazmenko wrote:
> Hi!
>
> The key points of this lengthy letter are:
>
> (0) I find RedBlackTree hard to use, and below is one story of 
> trying to get it to work.
>
> (1) Perhaps I did something wrong a few times.  Please show me 
> a better way to go.
>
> (2) Perhaps the library code could be improved as well to make 
> the process more intuitive.
>
> -----
>
> I am trying to use RedBlackTree container to maintain a set of 
> Elems, Elem being a non-trivial struct.  The problem is that I 
> find the container hard to use.
>
> First, I have to note that, instead of storing Elems directly 
> in the RedBlackTree, I have a dynamic array of Elems and a 
> RedBlackTree of integers pointing to that array to improve 
> performance.  In my case, the latter proved to be a few times 
> faster than the former because RedBlackTree moves the values 
> around quite a bit.  Please comment if there is a common way to 
> achieve a similar performance gain without decoupling.
>
> Anyway, instead of storing say "data[a]" and "data[b]" in the 
> tree, I store their indices "a" and "b" and compare these 
> integers like "data[a] < data[b]".  Below is the story of my 
> few steps to making this work.  I'll appreciate any comments on 
> how I could improve or take a better direction on any of the 
> steps.
>
> The compiler is DMD 2.063.2, no compile options.  Struct Elem 
> is replaced by an alias to long for simplicity.
>
>
> 1. The first try is to specify the comparison directly:
> -----
> import std.container;
> alias Elem = long;
> Elem [] data;
> RedBlackTree !(int, "data[a] < data[b]") tree;
> void main () { }
> -----
>
> This gives the following error:
> rbt1.d(7): Error: template instance RedBlackTree!(int, "data[a] 
> < data[b]")
> does not match template declaration RedBlackTree(T, alias less 
> = "a < b",
> bool allowDuplicates = false) if 
> (is(typeof(binaryFun!(less)(T.init, T.init))))
>
> OK, that was predictable.  I never got to getting this to work 
> beyond a simple "a < b" or "a + 1 > b + 1" or the like.  Is 
> that even possible?
>
>
> 2. Let us try a lambda:
> -----
> import std.container;
> alias Elem = long;
> Elem [] data;
> RedBlackTree !(int, (a, b) => data[a] < data[b]) tree;
> void main ()
> {
> 	tree = redBlackTree !((a, b) => data[a] < data[b]) (new int 
> [0]);
> }
> -----
>
> Fine with the declaration, but later, an error again:
> rbt2.d(11): Error: cannot implicitly convert expression 
> (redBlackTree(new
> int[](0u))) of type rbt2.main.RedBlackTree!(int, 
> __lambda6).RedBlackTree to
> rbt2.RedBlackTree!(int, __lambda3).RedBlackTree
>
> I see.  The compiler cannot tell that the lambdas are the same.
>  Oh well.
>
>
> 3. An ordinary function then:
> -----
> import std.container;
> alias Elem = long;
> Elem [] data;
> bool less_data (int a, int b) {return data[a] < data[b];}
> RedBlackTree !(int, less_data) tree;
> void main ()
> {
> 	tree = redBlackTree !(less_data) (new int [0]);
> }
> -----
>
> Aaaaaaand:
> phobos\std\container.d(6553): Error: less_data (int a, int b) 
> is not callable using argument types ()
> phobos\std\range.d(611): Error: static assert "Cannot put a 
> char[] into a Appender!(string)"
> phobos\std\format.d(1433): instantiated from here: 
> put!(Appender!(string), char[])
> phobos\std\format.d(1335): instantiated from here: 
> formatUnsigned!(Appender!(string), char)
> phobos\std\format.d(1309): instantiated from here: 
> formatIntegral!(Appender!(string), ulong, char)
> phobos\std\format.d(2950): ... (4 instantiations, -v to show) 
> ...
> phobos\std\container.d(5541): instantiated from here: 
> Tuple!(bool, "added", RBNode!(int)*, "n")
> rbt3.d(12): instantiated from here: RedBlackTree!(int, 
> less_data)
>
> Ouch.  What?  That does not look like a user-friendly message 
> at all.  Am I doing something very wrong?..
>
>
> 4. After a bit of guessing, I got this working by adding an 
> empty template argument to the function.  Here it goes:
> -----
> import std.container;
> alias Elem = long;
> Elem [] data;
> bool less_data () (int a, int b) {return data[a] < data[b];}
> RedBlackTree !(int, less_data) tree;
> void main ()
> {
> 	tree = redBlackTree !(less_data) (new int [0]);
> 	data = [4, 3, 5];
> 	tree.insert (0);
> 	tree.insert (1);
> 	tree.insert (2);
> }
> -----
>
> This compiles and runs fine.  Or does it?  Adding "-unittest" 
> compiler option produces another bunch of errors:
> phobos\std\container.d(5672): Error: void has no value
> phobos\std\container.d(5672): Error: incompatible types for 
> ((less_data()(int a, int b)) == ("a < b")): 'void' and 'string'
> phobos\std\container.d(5946): Error: void has no value
> phobos\std\container.d(5946): Error: incompatible types for 
> ((less_data()(int a, int b)) == ("a < b")): 'void' and 'string'
> phobos\std\container.d(6021): Error: void has no value
> phobos\std\container.d(6021): Error: incompatible types for 
> ((less_data()(int a, int b)) == ("a < b")): 'void' and 'string'
> phobos\std\container.d(6067): Error: void has no value
> phobos\std\container.d(6067): Error: incompatible types for 
> ((less_data()(int a, int b)) == ("a < b")): 'void' and 'string'
> phobos\std\container.d(6108): Error: void has no value
> phobos\std\container.d(6108): Error: incompatible types for 
> ((less_data()(int a, int b)) == ("a < b")): 'void' and 'string'
> phobos\std\container.d(6229): Error: void has no value
> phobos\std\container.d(6229): Error: incompatible types for 
> ((less_data()(int a, int b)) == ("a < b")): 'void' and 'string'
> phobos\std\container.d(6328): Error: void has no value
> phobos\std\container.d(6328): Error: incompatible types for 
> ((less_data()(int a, int b)) == ("a < b")): 'void' and 'string'
>
> So, now I have a working program unless I want to run a 
> unittest, in which case, it does not compile.  I wonder what's 
> so wrong with the examples 3 and 4, and how do I get them to 
> compile regardless of compiler options?
>
> On a relevant note, I find the unittests of RedBlackTree a bit 
> excessive even when they compile successfully.  They seem to 
> test the integrity of the whole tree every time a tree 
> operation takes place, and that makes the unittests version of 
> my local code run too slowly.  Is there a way to turn unittests 
> on only for user code and turn them off for the standard 
> library?
>
> Ivan Kazmenko.

N°4 is clearly a bug in the implementation.
N°3, I'm not sure what is going on with the "put" bugs, but it 
seems to be fixed in head.

In both case, one of the problems is that 
"redBlackTree!less_data" seems to be taking the wrong overload, 
which explains some of your problems. I'd use an explicit:

tree = new RedBlackTree!(int, less_data)(); //No surprises

In any case, yes, it is buggy.