www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 5451] New: Three ideas for RedBlackTree

reply d-bugmail puremagic.com writes:
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



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: -------
Jan 13 2011
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5451




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: -------
Jan 13 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jan 20 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5451


Steven Schveighoffer <schveiguy yahoo.com> changed:

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



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: -------
Feb 16 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5451




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: -------
Feb 16 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5451


bearophile_hugs eml.cc changed:

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



*** 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: -------
Mar 21 2011
prev sibling parent d-bugmail puremagic.com writes:
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



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: -------
Mar 21 2011