Feature #2348

RBTree Should be Added to the Standard Library

Added by James Gray over 4 years ago. Updated 3 months ago.

[ruby-core:26635]
Status:Assigned
Priority:Normal
Assignee:Yukihiro Matsumoto
Category:lib
Target version:next minor

Description

=begin
The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602

RBTree has now been fixed to run on Ruby 1.9:

http://github.com/skade/rbtree

I think we should now give serious consideration to bringing it into the standard library.
=end

History

#1 Updated by Florian Gilcher over 4 years ago

=begin

On Nov 8, 2009, at 6:11 PM, James Gray wrote:

Feature #2348: RBTree Should be Added to the Standard Library
http://redmine.ruby-lang.org/issues/show/2348

Author: James Gray
Status: Open, Priority: Normal
Category: lib, Target version: 1.9.2

The merits of this library have been discussed on Ruby core, with

the strengths best summarized by this post:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602

RBTree has now been fixed to run on Ruby 1.9:

http://github.com/skade/rbtree

I think we should now give serious consideration to bringing it into

the standard library.

To add to that: I also contacted the maintainer of RBTree to
inform him of my patches and to ask for his thoughts. As the
library is of good-quality and fitted with a good test suite,
I would also volunteer to maintain it, but I want to wait
for an answer first.

Regards,
Florian Gilcher

=end

#2 Updated by Nobuyoshi Nakada over 4 years ago

=begin
Hi,

At Mon, 9 Nov 2009 06:41:57 +0900,
James Gray wrote in :

RBTree has now been fixed to run on Ruby 1.9:

http://github.com/skade/rbtree

It can't compile with non-gcc, or with gcc and $DEBUG.

diff --git a/extconf.rb b/extconf.rb
index 272790b..02f2e8e 100644
--- a/extconf.rb
+++ b/extconf.rb
@@ -2,5 +2,7 @@ require 'mkmf'

if $DEBUG
- $CFLAGS << ' -std=c89 -pedantic -Wall -Wno-long-long'
+ if CONFIG['GCC'] == 'yes'
+ $CFLAGS << ' -std=c89 -pedantic -Wno-long-long'
+ end
$defs << ' -Dinline=__inline'
else
@@ -8,4 +10,4 @@ else
end

-havefunc('rbenumeratorize')
+havefunc('rbexecrecursive', 'ruby.h')
create
makefile('rbtree')
diff --git a/rbtree.c b/rbtree.c
index 9f19613..08bde65 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -12,8 +12,15 @@
#define HASHPROCDEFAULT FL_USER2

-#ifndef HAVERBENUMERATORIZE
+#ifndef RETURNENUMERATOR
#define RETURN
ENUMERATOR(obj, argc, argv) ((void)0)
#endif

+#ifndef RHASHTBL
+#define RHASH
TBL(h) RHASH(h)->tbl
+#endif
+#ifndef RHASHIFNONE
+#define RHASH
IFNONE(h) RHASH(h)->ifnone
+#endif
+
VALUE RBTree;
VALUE MultiRBTree;
@@ -428,5 +435,5 @@ static int
valueeq(const void* key1, const void* key2)
{
- return rb
equal((VALUE)key1, (VALUE)key2);
+ return rb_equal((VALUE)key1, (VALUE)key2) != 0;
}

@@ -1077,5 +1084,5 @@ rbtreetohash(VALUE self)
hash = rbhashnew();
rbtreeforeach(self, tohashi, (void)hash);
- RHASH(hash)->ifnone = IFNONE(self);
+ RHASHIFNONE(hash) = IFNONE(self);
if (FL
TEST(self, RBTREEPROCDEFAULT))
FLSET(hash, HASHPROCDEFAULT);
@@ -1097,7 +1104,6 @@ rbtree
begin_inspect(VALUE self)
{
const char
c = rbclass2name(CLASSOF(self));
- char str [strlen(c) + 5];
- sprintf(str, "#<%s: ", c);
- VALUE rbstr = rbstrnew2(str);
+ VALUE rb
str = rbstrnew(0, strlen(c) + 4);
+ sprintf(RSTRINGPTR(rbstr), "#<%s: ", c);
return rbstr;
}
@@ -1109,4 +1115,5 @@ to
s_rbtree(VALUE self, VALUE nil)
}

+#ifdef HAVERBEXECRECURSIVE
VALUE
rbtree
tosrecursive(VALUE self, VALUE arg, int recursive)
@@ -1116,4 +1123,5 @@ rbtreetosrecursive(VALUE self, VALUE arg, int recursive)
return to
s_rbtree(self, Qnil);
}
+#endif

/*
@@ -1123,8 +1131,11 @@ VALUE
rbtreetos(VALUE self)
{
+#ifdef HAVERBEXECRECURSIVE
return rb
execrecursive(rbtreetosrecursive, self, Qnil);
- //if (rbinspectingp(self))
- // return rbstrcat2(rbtreebegininspect(self), "...>");
- //return rbprotectinspect(tosrbtree, self, Qnil);
+#else
+ if (rbinspectingp(self))
+ return rbstrcat2(rbtreebegininspect(self), "...>");
+ return rbprotectinspect(tosrbtree, self, Qnil);
+#endif
}

@@ -1194,8 +1205,12 @@ VALUE
rbtreeinspect(VALUE self)
{
- /*VALUE str = rbtree
begininspect(self);
- if (rb
inspectingp(self))
- return rb
strcat2(str, "...>");*/
+#ifdef HAVE
RBEXECRECURSIVE
return rbexecrecursive(rbtreeinspectrecursive, self, Qnil);
+#else
+ VALUE str = rbtreebegininspect(self);
+ if (rbinspectingp(self))
+ return rbstrcat2(str, "...>");
+ return rbprotectinspect(inspect_rbtree, self, str);
+#endif
}

diff --git a/test.rb b/test.rb
index 8c533b8..32fdd25 100644
--- a/test.rb
+++ b/test.rb
@@ -136,5 +136,5 @@ class RBTreeTest < Test::Unit::TestCase
assert_raises(ArgumentError) { rbtree.default("e", "f") }

  • rbtree = RBTree.new {|rbtree, key| @rbtree[key || "c"] }
  • rbtree = RBTree.new {|tree, key| @rbtree[key || "c"] } assertequal("C", rbtree.default(nil)) assertequal("B", rbtree.default("b")) @@ -182,5 +182,5 @@ class RBTreeTest < Test::Unit::TestCase a = RBTree.new b = RBTree.new
  • a.readjust {|a, b| a <=> b }
  • a.readjust {|x, y| x <=> y } assertnotequal(a, b) b.readjust(a.cmpproc) @@ -198,5 +198,14 @@ class RBTreeTest < Test::Unit::TestCase assertequal("E", @rbtree.fetch("e", "E")) assert_equal("E", @rbtree.fetch("e") { "E" })
  • class << (stderr = "")
  • alias write <<
  • end
  • $stderr, stderr, $VERBOSE, verbose = stderr, $stderr, false, $VERBOSE
  • begin assert_equal("E", @rbtree.fetch("e", "F") { "E" })
  • ensure
  • $stderr, stderr, $VERBOSE, verbose = stderr, $stderr, false, $VERBOSE
  • end
  • assert_match(/warning: block supersedes default value argument/, stderr)

    assertraises(ArgumentError) { @rbtree.fetch }
    @@ -535,5 +544,5 @@ class RBTreeTest < Test::Unit::TestCase
    assert
    equal(%({"a"=>"A", "b"=>"B", "c"=>"C", "d"=>"D"}), tree)
    assert_equal(%("e"), default)

  • assertmatch(/#Proc:w+(@test.rb:d+)?/, cmpproc)

  • assertmatch(/#<Proc:\w+(@#{FILE}:\d+)?>/o, cmpproc)

    rbtree = RBTree.new

    Nobu Nakada

=end

#3 Updated by Florian Gilcher over 4 years ago

=begin
Hi,

thanks for the patch, I applied it with a minor addition (also matching on HAVERBEXEC_RECURSIVE in pp functions to use the "old" behaviour instead).

I expect that the compiler problems are only because of the flags in extconf.rb or are there other thing I missed?

Concerning HAVERBEXECRECURSIVE: i looked it up and rbinspectingp is gone since March 2005. Are there considerable chances of a modern ruby version still in support that does not have rbexec_recursive? (1.8.6 perhaps?)

Both questions are more out of curiosity, as I said, I'm not that into Ruby internals and/or consider myself a good C developer ;).

Regards,
Florian
=end

#4 Updated by Nobuyoshi Nakada over 4 years ago

=begin
Hi,

At Tue, 10 Nov 2009 00:21:45 +0900,
Florian Gilcher wrote in :

thanks for the patch, I applied it with a minor addition
(also matching on HAVERBEXEC_RECURSIVE in pp functions to
use the "old" behaviour instead).

Indentation seems broken in rbtreetos().

I expect that the compiler problems are only because of the
flags in extconf.rb or are there other thing I missed?

And syntax errors in rbtreebegininspect():

 char str [strlen(c) + 5];
 sprintf(str, "#<%s: ", c);
 VALUE rb_str = rb_str_new2(str);

Dynamic size array and local variable definition after
executable statements are C99 features but not allowed in C89.

Also C++ style one-line comment in rbtreetos():
//if (rbinspectingp(self))

Concerning HAVERBEXECRECURSIVE: i looked it up and
rb
inspectingp is gone since March 2005. Are there
considerable chances of a modern ruby version still in
support that does not have rb
exec_recursive? (1.8.6
perhaps?)

Since there was the code using rbinspectingp(). I don't like
comment-out for such case.

--
Nobu Nakada

=end

#5 Updated by ujihisa . over 4 years ago

  • Status changed from Open to Assigned
  • Assignee set to Yukihiro Matsumoto

=begin

=end

#6 Updated by James Gray about 4 years ago

=begin
Is there any chance we could get this incorporated before the 1.9.2 feature freeze?
=end

#7 Updated by Yui NARUSE about 4 years ago

=begin
This ticket doesn't have:
* Who maintain it
* Sufficient reason to bundle

If someone maintain it, the problem is, Is this worth to bundle?
So you should persuade, like:

#8 Updated by Yusuke Endoh about 4 years ago

=begin
Hi,

2010/3/22 James Gray redmine@ruby-lang.org:

Is there any chance we could get this incorporated before the 1.9.2 feature freeze?

This ticket is not simple since this feature seems to be against "Large
Class Principle". We need matz's approval.

My current personal opinion is that it is appropriate for the feature to
be just a part of set.rb as a back-end, instead of a first class library.

Is there case where we want to use RBTree directly, instead of set.rb?

--
Yusuke ENDOH mame@tsg.ne.jp

=end

#9 Updated by B Kelly about 4 years ago

=begin
Hi,

Yusuke ENDOH wrote:

Is there case where we want to use RBTree directly, instead of set.rb?

I'm sorry if I've misunderstood - but it would not have occurred
to me to use 'set' to access RBTree's functionality.

RBTree and MultiRBTree (both provided by require 'rbtree') are
akin to std::map and std::multimap in C++ STL.

It has long been a mystery to me that a Sorted Pair Associative
Container with O(log N) insert, search, and delete complexity
has not been a part of ruby's stdlib.

RBTree and MultiRBTree provide functionality which, with its
worst-case O(log N) search, insert, and delete complexity for
a sorted pair associative container can't be readily duplicated
with Array, Hash, or Set. (As far as I know.)

RBTree and MultiRBTree are very useful container types when
needed.

I do think the "RB" portion of the name is slightly unfortunate,
as we don't generally care that it is implemented as a red-black
tree internally; we just care about O(log N) complexity
guarantees.

Anyway - I apologize if i've merely regurgitated a litany of
obvious points into the conversation. I didn't really
understand why RBTree/MultiRBTree would be considered a
variant of Set?

Regards,

Bill

=end

#10 Updated by Yusuke Endoh about 4 years ago

=begin
Hi,

2010/3/22 Bill Kelly billk@cts.com:

RBTree and MultiRBTree provide functionality which, with its
worst-case O(log N) search, insert, and delete complexity for
a sorted pair associative container can't be readily duplicated
with Array, Hash, or Set. ?(As far as I know.)

Hash has amortized O(1) search, insert, and delete complexity,
I think. Indeed, it becomes O(N) at worst-case (when rehash
occurs). Does anyone have a concrete problem due to rehash?

I think this feature request is very tough because it can be
substituted by Hash in many cases. So I think you guys should
appeal the difference. It would be good to show some real-world
case where Hash cannot be used and RBTree is really needed.

I do think the "RB" portion of the name is slightly unfortunate,
as we don't generally care that it is implemented as a red-black
tree internally; we just care about O(log N) complexity
guarantees.

True.

Anyway - I apologize if i've merely regurgitated a litany of
obvious points into the conversation. ?I didn't really
understand why RBTree/MultiRBTree would be considered a
variant of Set?

There is no use case presented other than set, as far as I read.

--
Yusuke ENDOH mame@tsg.ne.jp

=end

#11 Updated by B Kelly about 4 years ago

=begin
Yusuke ENDOH wrote:

2010/3/22 Bill Kelly billk@cts.com:

RBTree and MultiRBTree provide functionality which, with its
worst-case O(log N) search, insert, and delete complexity for
a sorted pair associative container can't be readily duplicated
with Array, Hash, or Set. ?(As far as I know.)

Hash has amortized O(1) search, insert, and delete complexity,
I think. Indeed, it becomes O(N) at worst-case (when rehash
occurs). Does anyone have a concrete problem due to rehash?

Agreed: for Hash I would expect O(1) search, and amortized O(1)
insert and delete complexity.

To avoid rehash, a Hash#reserve(size) method might be nice, but,
for me, that is all separate from why I am interested in RBTree.

I think this feature request is very tough because it can be
substituted by Hash in many cases. So I think you guys should
appeal the difference. It would be good to show some real-world
case where Hash cannot be used and RBTree is really needed.

Some differences:

Hash is not maintained in key-sorted order.

Hash does not offer upperbound(key) or lowerbound(key)
or bound(key1, key2) in O(log N) time.

Hash doesn't provide fast search for partial string key.

An example, indexing words in documents, and doing
partial keyword searches.

(Note: MultiRBTree#bound seems to be broken.)

 require 'rbtree'

 ful_ = %w(
 fulcra
 fulcrum
 fulcrums
 fulfil
 fulfill
 fulfilled
 fulfilling
 fulfillment
 fulfills
 fulfilment
 fulfils
 full
 fullback
 fullbacks
 fulled
 fuller
 fullest
 fulling
 fullness
 fulls
 fully
 fulminate
 fulminated
 fulminates
 fulminating
 fulmination
 fulminations
 fulsome
 )

 multi_ = %w(
 multicolored
 multicultural
 multiculturalism
 multidimensional
 multifaceted
 multifarious
 multifariousness
 multilateral
 multilingual
 multimedia
 multimillionaire
 multimillionaires
 multinational
 multinationals
 multiple
 multiples
 multiplex
 multiplexed
 multiplexer
 multiplexers
 multiplexes
 multiplexing
 multiplicand
 multiplicands
 multiplication
 multiplications
 multiplicative
 multiplicities
 multiplicity
 multiplied
 multiplier
 multipliers
 multiplies
 multiply
 multiplying
 multiprocessing
 multipurpose
 multiracial
 multitasking
 multitude
 multitudes
 multitudinous
 multivariate
 multivitamin
 multivitamins
 )

 dis_ = %w(
 distortions
 distorts
 distract
 distracted
 distracting
 distraction
 distractions
 distracts
 distrait
 distraught
 distress
 distressed
 distresses
 distressful
 distressing
 distressingly
 distribute
 distributed
 distributes
 distributing
 distribution
 distributions
 distributive
 distributor
 distributors
 district
 districts
 distrust
 distrusted
 distrustful
 distrustfully
 distrusting
 distrusts
 disturb
 disturbance
 disturbances
 disturbed
 disturbing
 disturbingly
 disturbs
 )


 doc1 = [ "foo/doc1.txt", ful_   + multi_ ]
 doc2 = [ "bar/doc2.txt", multi_ + dis_   ]
 doc3 = [ "baz/doc3.txt", ful_   + dis_   ]


 dict = MultiRBTree.new

 [doc1, doc2, doc3].each do |docpath, words|
   words.each do |w|
     dict.store(w, docpath)
   end
 end


 puts dict.lower_bound("mult")  # => ["multicolored", "foo/doc1.txt"]
 puts dict.upper_bound("mult")  # => ["fulsome", "baz/doc3.txt"]
 puts dict.bound("mult")        # <-- broken

Note: The documentation for RBTree#bound reads:

  • call-seq:
  • rbtree.bound(key1, key2 = key1) => array
  • rbtree.bound(key1, key2 = key1) {|key, value| block} => rbtree *
  • Returns an array containing key-value pairs between the result of
  • MultiRBTree#lowerbound and MultiRBTree#upperbound. If a block is
  • given it calls the block once for each pair.

    So I expected dict.bound("mult") to return all elements from:

    dict.lower_bound("mult") => ["multicolored", "foo/doc1.txt"]

    through:

    dict.upper_bound("mult") => ["fulsome", "baz/doc3.txt"]

    However, #bound just retunrs [] :(

    I consider this a bug.


    A comment:

    Even if MultiRBTree#bound worked as expected, I must concede a
    significant liability of MultiRBTree's API compared to C++
    std::multimap, is the lack of iterators.

    With std::multimap, I can find dict.lower_bound("mult"), and
    then iterate over as many or as few subsequent elements in sorted
    order as I choose. (When building a typedown menu, for example,
    I may only want the first 10 results.)

    I suppose rbtree.bound(key1, key2, limit) would be one way to
    provide equivalent functionality; or perhaps support for 1.9
    Enumerable would be another.


    Anyway, issues with MultiRBTree#bound aside, other ways I've
    used a Sorted Pair Associative Container include implementing
    various kinds of priority queues. (Sorted integer keys.)


    I do think that for RBTree and MultiRBTree to be as generally
    useful as C++ std::map and std::multimap, there should be
    versions of methods like bound, lowerbound, upperbound, that
    return an enumerator.

    Also, I think it should be possible to unambiguously delete
    a specific element from a MultiRBTree.

    Currently:

    t = MultiRBTree.new
    t.store "foo", "456"
    t.store "foo", "123"
    t.delete "foo" # <-- which is deleted? foo/123 or foo/456 ?

    It appears that MultiRBTree#delete deletes the oldest key/value
    pair matching the supplied key, so it would be foo/456.

    As far as I can tell, there's no way to delete foo/123 from t
    without first deleting foo/456. So that is another limitation
    when compared to std::multimap.


    Hmm.

    So it seems that even though RBTree and MultiRBTree are
    internally equivalent to C++ std::map and std::multimap, the
    interface exposed to the programmer is less flexible than the
    C++ versions.

    I think RBTree and MultiRBTree would be more useful it were
    possible to obtain enumerators from bound and lower_bound,
    and to be able to delete arbitrary elements in a MultiRBTree.

    Sorry this email is so long. I didn't expect to encounter
    these issues.

    Regards,

    Bill

=end

#12 Updated by Yusuke Endoh about 4 years ago

=begin
Hi,

Thank you for your detailed reply!

2010/3/22 Bill Kelly billk@cts.com:

Hash is not maintained in key-sorted order.

Hash does not offer upperbound(key) or lowerbound(key)
or bound(key1, key2) in O(log N) time.

Good. I start to want RBTree too :-)

Hash doesn't provide fast search for partial string key.

You mean prefix search, right?
And, can partial array key be handled?

puts dict.upper_bound("mult") ?# => ["fulsome", "baz/doc3.txt"]

Is this correct? I expect it to return ["multivitamins", "foo/doc1.txt"]
or ["multivitamins", "bar/doc2.txt"].

However, #bound just retunrs [] ?:(

I guess it is because upper_bound is broken.

I do think that for RBTree and MultiRBTree to be as generally
useful as C++ std::map and std::multimap, there should be
versions of methods like bound, lowerbound, upperbound, that
return an enumerator.

Agreed. I think bound should return an enumerator instead of an
array when block is not given.

You presented dictionary-like application and priority queue as
use cases. I'm convinced at the explanation.
But RBTree seems to have some problems of not only simple bug but
also API design. If so, it is slightly premature, so it may be
better to defer its bundle to 1.9.3 or later.

--
Yusuke ENDOH mame@tsg.ne.jp

=end

#13 Updated by B Kelly about 4 years ago

=begin
Tanaka Akira wrote:

2010/3/22 Bill Kelly billk@cts.com:

Hash doesn't provide fast search for partial string key.

RBTree doesn't provide it.
Because RBTree uses <=> for comparing elements.
The result of <=> is not useful to test partial key match.

Ah. I meant via #lower_bound.

/*
* Look for the node corresponding to the lowest key that is equal to or
* greater than the given key. If there is no such node, return null.
*/

dnodet *dictlowerbound(dictt *dict, const void *key)

Seems to me this should provide a fast search for a partial
string key. (?)

Regards,

Bill

=end

#14 Updated by B Kelly about 4 years ago

=begin
Bill Kelly wrote:

Tanaka Akira wrote:

2010/3/22 Bill Kelly billk@cts.com:

Hash doesn't provide fast search for partial string key.
RBTree doesn't provide it.
Because RBTree uses <=> for comparing elements.
The result of <=> is not useful to test partial key match.

Ah. I meant via #lower_bound.

/*
* Look for the node corresponding to the lowest key that is equal to or
* greater than the given key. If there is no such node, return null.
*/

dnodet *dictlowerbound(dictt *dict, const void *key)

Seems to me this should provide a fast search for a partial
string key. (?)

Sorry, I was imprecise. By partial I meant prefix, as
Yusuke ENDOH pointed out.

Regards,

Bill

=end

#15 Updated by Charles Nutter about 4 years ago

=begin
Jumping in with JRuby perspective..

I suppose this would be easiest for us to implement by wrapping the
built-in TreeMap from Java:

http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeMap.html

I have not looked over RBTree API, but hopefully there's nothing there
we couldn't implement atop TreeMap/TreeSet.

  • Charlie

=end

#16 Updated by B Kelly about 4 years ago

=begin
Yusuke ENDOH wrote:

Hash doesn't provide fast search for partial string key.

You mean prefix search, right?
And, can partial array key be handled?

Ah, yes. Thanks, I did mean prefix.

And indeed, based on experiments in irb with array-based keys,
it does appear that lower_bound works with array key prefix
search.

puts dict.upper_bound("mult") ?# => ["fulsome", "baz/doc3.txt"]

Is this correct? I expect it to return ["multivitamins", "foo/doc1.txt"]
or ["multivitamins", "bar/doc2.txt"].

I had assumed it worked like std::map upperbound
( http://www.cplusplus.com/reference/stl/map/upper
bound/ )
returning "first element in the container whose key compares
greater than x."

However, in rbtree's dict.c, dictupperbound() is documented
as:

/*
* Look for the node corresponding to the greatest key that is equal to or
* lower than the given key. If there is no such node, return null.
*/

So, its behavior does not seem to match the comment. (I
don't know whether to consider the comment wrong, or the
behavior wrong. :)

Regards,

Bill

=end

#17 Updated by Kazuhiro NISHIYAMA about 4 years ago

  • Target version changed from 1.9.2 to 2.0.0

=begin

=end

#18 Updated by David Graham over 2 years ago

Is there a chance RBTree can be added to the standard library for Ruby 2.0? I've needed it to implement priority queues and key range scans, but the binary gem doesn't play well with JRuby or Rubinius. It would help if we could count on this data structure being included with Ruby.

Thanks!
David

#19 Updated by James Gray over 2 years ago

I still agree. We've literally been asking for NArray and RBTree in the standard library for years. Pretty please? :)

#20 Updated by B Kelly over 2 years ago

I wholeheartedly agree about the usefulness of the data structure.

I'm hesitant to type this, because I don't want to impede RBTree's path toward first-class citizenship.

But last time I checked there appeared to be some API deficiencies that significantly limited RBTree's potential usefulness:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/28860
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/28879

Although I suppose it's possible these could be addressed at a later date?

Regards,

Bill

#21 Updated by Konstantin Haase over 2 years ago

SortedSet could then depend on it properly instead of the voodoo code that ships with Ruby atm.

Konstantin

On Oct 6, 2011, at 13:22 , B Kelly wrote:

Issue #2348 has been updated by B Kelly.

I wholeheartedly agree about the usefulness of the data structure.

I'm hesitant to type this, because I don't want to impede RBTree's path toward first-class citizenship.

But last time I checked there appeared to be some API deficiencies that significantly limited RBTree's potential usefulness:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/28860
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/28879

Although I suppose it's possible these could be addressed at a later date?

Regards,

Bill


Feature #2348: RBTree Should be Added to the Standard Library
http://redmine.ruby-lang.org/issues/2348

Author: James Gray
Status: Assigned
Priority: Normal
Assignee: Yukihiro Matsumoto
Category: lib
Target version: 1.9.x

¾gin
The merits of this library have been discussed on Ruby core, with the strengths best summarized by this post:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/26602

RBTree has now been fixed to run on Ruby 1.9:

http://github.com/skade/rbtree

I think we should now give serious consideration to bringing it into the standard library.

#22 Updated by Koichi Sasada over 2 years ago

(2011/10/07 1:50), David Graham wrote:

Is there a chance RBTree can be added to the standard library for Ruby 2.0? I've needed it to implement priority queues and key range scans, but the binary gem doesn't play well with JRuby or Rubinius. It would help if we could count on this data structure being included with Ruby.

Gem is not enough?

--
// SASADA Koichi at atdot dot net

#23 Updated by Anonymous over 2 years ago

On Thu, Oct 6, 2011 at 6:34 PM, SASADA Koichi ko1@atdot.net wrote:

(2011/10/07 1:50), David Graham wrote:

Is there a chance RBTree can be added to the standard library for Ruby 2.0?  I've needed it to implement priority queues and key range scans, but the binary gem doesn't play well with JRuby or Rubinius.  It would help if we could count on this data structure being included with Ruby.

Gem is not enough?

I guess I just feel I would use RBTree and NArray a lot more than some
things we have in the standard library. It's about the same
usefulness as Set, in my opinion. Maybe even a little more.

James Edward Gray II

#24 Updated by Koichi Sasada over 2 years ago

(2011/10/07 9:46), James Gray wrote:

On Thu, Oct 6, 2011 at 6:34 PM, SASADA Koichi ko1@atdot.net wrote:

(2011/10/07 1:50), David Graham wrote:

Is there a chance RBTree can be added to the standard library for Ruby 2.0? I've needed it to implement priority queues and key range scans, but the binary gem doesn't play well with JRuby or Rubinius. It would help if we could count on this data structure being included with Ruby.

Gem is not enough?

I guess I just feel I would use RBTree and NArray a lot more than some
things we have in the standard library. It's about the same
usefulness as Set, in my opinion. Maybe even a little more.

Some people think most of standard libraries should be in gem. I think
you need to persuade them.

--
// SASADA Koichi at atdot dot net

#25 Updated by Anonymous over 2 years ago

On Thu, Oct 6, 2011 at 8:07 PM, SASADA Koichi ko1@atdot.net wrote:

Some people think most of standard libraries should be in gem.  I think
you need to persuade them.

I sympathize, but we are still adding new libraries as of Ruby 1.9.3
and people have literally been wanting these two for years. I'm not
clear on why some libraries make it but these don't.

James Edward Gray II

#26 Updated by Anonymous over 2 years ago

On Oct 6, 2011, at 9:07 PM, SASADA Koichi wrote:

Some people think most of standard libraries should be in gem. I think
you need to persuade them.

I think the intent is for RBTree to be included with the Ruby distribution via the standard library or via 'standard gems'. That is to say, the inclusion of RBTree into the standard Ruby 'distribution' is orthogonal to whether the standard distribution packages the standard library as gems or not.

Gary Wright

#27 Updated by Kenta Murata over 2 years ago

(2011.10.07 01:50 ), David Graham wrote:

Is there a chance RBTree can be added to the standard library for Ruby 2.0?

I agree with you if the library name is changed.
The name of RBTree is too specific to its internal algorithm.
If we adopt RBTree, we must change the name of the library after
more better algorithms would be discovered.

--
Kenta Murata muraken@gmail.com
1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

#28 Updated by Clifford Heath over 2 years ago

On 07/10/2011, at 1:16 PM, Kenta Murata wrote:

(2011.10.07 01:50 ), David Graham wrote:

Is there a chance RBTree can be added to the standard library for Ruby 2.0?
I agree with you if the library name is changed.
The name of RBTree is too specific to its internal algorithm.
If we adopt RBTree, we must change the name of the library after
more better algorithms would be discovered.

I agree. Hash is not named after the hashing algorithm that's being used,
and Array is not named after its structure either.

For sorted structures, I've previously used the name Sequence. I think
this name would be suitable.

I also wish that Ruby had this container type available as a standard.

Clifford Heath.

#29 Updated by Anonymous over 2 years ago

On Fri, Oct 7, 2011 at 1:20 AM, Clifford Heath clifford.heath@gmail.com wrote:

On 07/10/2011, at 1:16 PM, Kenta Murata wrote:

(2011.10.07 01:50 ), David Graham wrote:

Is there a chance RBTree can be added to the standard library for Ruby 2.0?
I agree with you if the library name is changed.
The name of RBTree is too specific to its internal algorithm.
If we adopt RBTree, we must change the name of the library after
more better algorithms would be discovered.

I agree. Hash is not named after the hashing algorithm that's being used,
and Array is not named after its structure either.

For sorted structures, I've previously used the name Sequence. I think
this name would be suitable.

I also wish that Ruby had this container type available as a standard.

I think Tree would be a fine name and closer to Hash.

James Edward Gray II

#30 Updated by Clifford Heath over 2 years ago

On 08/10/2011, at 1:10 AM, James Gray wrote:

On Fri, Oct 7, 2011 at 1:20 AM, Clifford Heath clifford.heath@gmail.com wrote:

On 07/10/2011, at 1:16 PM, Kenta Murata wrote:

(2011.10.07 01:50 ), David Graham wrote:

Is there a chance RBTree can be added to the standard library for Ruby 2.0?
I agree with you if the library name is changed.
The name of RBTree is too specific to its internal algorithm.
If we adopt RBTree, we must change the name of the library after
more better algorithms would be discovered.

I agree. Hash is not named after the hashing algorithm that's being used,
and Array is not named after its structure either.

For sorted structures, I've previously used the name Sequence. I think
this name would be suitable.

I also wish that Ruby had this container type available as a standard.

I think Tree would be a fine name and closer to Hash.

Is there any part of the API which allows a user to know it's a Tree?
If so, why?

If it's not externally visible in the API, it should not appear in the name.

My 2c.

Clifford Heath.

#31 Updated by Jeremy Voorhis almost 2 years ago

I think that Ruby developers would definitely benefit from having a range of well-implemented data structures within reach. I don't understand why the implementation-revealing name is an issue when our most common options are already named Array [contiguous chunk of memory] and Hash[-table]. Renaming this library's classes to something SortedMap and SortedMultiMap seems incongruous.

#32 Updated by Koichi Sasada over 1 year ago

ping. status?

#33 Updated by Yukihiro Matsumoto over 1 year ago

  • Target version changed from 2.0.0 to next minor

I am not positive about adding a new library to the distribution while we are discussion moving toward gems.
I am not refusuig, however, so I label this "next minor".

Matz.

#34 Updated by Zachary Scott 3 months ago

Theres a discussion going on about possibly removing dependency on RBTree, or SortedSet all together.

Please see #9121

Also available in: Atom PDF