[Issue 5451] New: Three ideas for RedBlackTree

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=5451

           Summary: Three ideas for RedBlackTree
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2011-01-13 15:55:50 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------