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@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@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: -------

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



--- Comment #1 from bearophile_hugs@eml.cc 2011-01-13 16:06:38 PST ---
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.

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

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


Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |schveiguy@yahoo.com
         AssignedTo|nobody@puremagic.com        |schveiguy@yahoo.com


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

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


Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jmdavisProg@gmx.com


--- Comment #2 from Steven Schveighoffer <schveiguy@yahoo.com> 2011-02-16 06:20:45 PST ---
*** Issue 5586 has been marked as a duplicate of this issue. ***

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

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



--- Comment #3 from Jonathan M Davis <jmdavisProg@gmx.com> 2011-02-16 23:54:25 PST ---
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.

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

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


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tbolsh@gmail.com


--- Comment #4 from bearophile_hugs@eml.cc 2011-03-21 13:17:39 PDT ---
*** Issue 5764 has been marked as a duplicate of this issue. ***

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

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


Jonathan M Davis <jmdavisProg@gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


--- Comment #5 from Jonathan M Davis <jmdavisProg@gmx.com> 2011-03-21 22:50:58 PDT ---
Fixed:

https://github.com/D-Programming-Language/phobos/pull/10 https://github.com/D-Programming-Language/phobos/commit/ef67f4ecd5100614b8361513ccdc4c507f620ed4 https://github.com/D-Programming-Language/phobos/commit/c6874cb1b07122936c4b86ea4aa7254fef4b71e7

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