Sorry for being so late with my answer. I am busy for some days. Steven Schveighoffer:
>I don't really know what to do about fixing it. It's not your fault. The forward reference errors I've found with RedBlackTree are so bad that in the end I've created a different algorithm that doesn't use a search tree. >I probably should just avoid using auto, Good. >not being able to declare a red black tree as a global variable is a huge >limitation.< Also as instance variable for a struct. > 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. This is OK, given your original design choice of using PIMPL. > auto t = RedBlackTree!int.create(); > Please bugzillize this OK. > 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). Python set uses "add", I prefer it for a set :-) But "insert" is acceptable. >> redBlackTree(1, 2, 3) > Yes, this should be done. Please make a bugzilla report. In fact, this > can extend to all std.container types. OK. I will create a single bugzilla report for RedBlackTree. > 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. Please hide it, but don't remove it from the module :-) >> 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. OK. The withLength template argument plus some static ifs allow to have zero overhead for people that don't need the O(1) length. I think withLength is better true on default, because removing the length is an optimization... > I have done this in dcollections, and it helps immensely in node-based > containers. I agree, I have seen similar things (D1 programs that become twice faster, etc), that's why I have suggested it. > 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. A template trait... > What about changing the predicate? I know it will likely violate the > requirements of a strict ordering, but it should probably work. I am not sure it will work, but in the end I have used a very different solution. Implementing an approximate (floating point) hash with a search tree is a common enough need, so you may add something like that approxInsert() as an free templated function in the std.collections module :-) > 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. OK. Then probably this important explanation (and example too, if you want) must be added to the RedBlackTree docs. > Thank you for your detailed analysis! You are welcome. And thank you for implementing this important collection. Bye, bearophile
