Ruby » ruby-trunk

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

Hi,

At Mon, 9 Nov 2009 06:41:57 +0900,
James Gray wrote in [ruby-core:26635]:
> 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

-have_func('rb_enumeratorize')
+have_func('rb_exec_recursive', '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 HASH_PROC_DEFAULT   FL_USER2

-#ifndef HAVE_RB_ENUMERATORIZE
+#ifndef RETURN_ENUMERATOR
 #define RETURN_ENUMERATOR(obj, argc, argv) ((void)0)
 #endif

+#ifndef RHASH_TBL
+#define RHASH_TBL(h) RHASH(h)->tbl
+#endif
+#ifndef RHASH_IFNONE
+#define RHASH_IFNONE(h) RHASH(h)->ifnone
+#endif
+
 VALUE RBTree;
 VALUE MultiRBTree;
@@ -428,5 +435,5 @@ static int
 value_eq(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 @@ rbtree_to_hash(VALUE self)
     hash = rb_hash_new();
     rbtree_for_each(self, to_hash_i, (void*)hash);
-    RHASH(hash)->ifnone = IFNONE(self);
+    RHASH_IFNONE(hash) = IFNONE(self);
     if (FL_TEST(self, RBTREE_PROC_DEFAULT))
         FL_SET(hash, HASH_PROC_DEFAULT);
@@ -1097,7 +1104,6 @@ rbtree_begin_inspect(VALUE self)
 {
     const char* c = rb_class2name(CLASS_OF(self));
-    char str [strlen(c) + 5];
-    sprintf(str, "#<%s: ", c);
-    VALUE rb_str = rb_str_new2(str);
+    VALUE rb_str = rb_str_new(0, strlen(c) + 4);
+    sprintf(RSTRING_PTR(rb_str), "#<%s: ", c);
     return rb_str;
 }
@@ -1109,4 +1115,5 @@ to_s_rbtree(VALUE self, VALUE nil)
 }

+#ifdef HAVE_RB_EXEC_RECURSIVE
 VALUE
 rbtree_to_s_recursive(VALUE self, VALUE arg, int recursive)
@@ -1116,4 +1123,5 @@ rbtree_to_s_recursive(VALUE self, VALUE arg, int recursive)
     return to_s_rbtree(self, Qnil);
 }
+#endif

 /*
@@ -1123,8 +1131,11 @@ VALUE
 rbtree_to_s(VALUE self)
 {
+#ifdef HAVE_RB_EXEC_RECURSIVE
     return rb_exec_recursive(rbtree_to_s_recursive, self, Qnil);
-    //if (rb_inspecting_p(self))
-    //    return rb_str_cat2(rbtree_begin_inspect(self), "...>");
-    //return rb_protect_inspect(to_s_rbtree, self, Qnil);
+#else
+    if (rb_inspecting_p(self))
+	return rb_str_cat2(rbtree_begin_inspect(self), "...>");
+    return rb_protect_inspect(to_s_rbtree, self, Qnil);
+#endif
 }

@@ -1194,8 +1205,12 @@ VALUE
 rbtree_inspect(VALUE self)
 {
-    /*VALUE str = rbtree_begin_inspect(self);
-    if (rb_inspecting_p(self))
-        return rb_str_cat2(str, "...>");*/
+#ifdef HAVE_RB_EXEC_RECURSIVE
     return rb_exec_recursive(rbtree_inspect_recursive, self, Qnil);
+#else
+    VALUE str = rbtree_begin_inspect(self);
+    if (rb_inspecting_p(self))
+	return rb_str_cat2(str, "...>");
+    return rb_protect_inspect(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"] }
     assert_equal("C", rbtree.default(nil))
     assert_equal("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 }
     assert_not_equal(a, b)
     b.readjust(a.cmp_proc)
@@ -198,5 +198,14 @@ class RBTreeTest < Test::Unit::TestCase
     assert_equal("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)

     assert_raises(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)
-    assert_match(/#<Proc:\w+(@test.rb:\d+)?>/, cmp_proc)
+    assert_match(/#<Proc:\w+(@#{__FILE__}:\d+)?>/o, cmp_proc)

     rbtree = RBTree.new


-- 
Nobu Nakada

Hi,

thanks for the patch, I applied it with a minor addition (also matching on HAVE_RB_EXEC_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 HAVE_RB_EXEC_RECURSIVE: i looked it up and rb_inspecting_p 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?)

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

Hi,

At Tue, 10 Nov 2009 00:21:45 +0900,
Florian Gilcher wrote in [ruby-core:26654]:
> thanks for the patch, I applied it with a minor addition
> (also matching on HAVE_RB_EXEC_RECURSIVE in pp functions to
> use the "old" behaviour instead).

Indentation seems broken in rbtree_to_s().

> 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 rbtree_begin_inspect():

    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 rbtree_to_s():
    //if (rb_inspecting_p(self))

> Concerning HAVE_RB_EXEC_RECURSIVE: i looked it up and
> rb_inspecting_p 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 rb_inspecting_p().  I don't like
comment-out for such case.

-- 
Nobu Nakada

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

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:

* Gauche have RBTree http://practical-scheme.net/gauche/man/gauche-refe_166.html
* You should use RBTree when you want to use Array#assoc
* You should use RBTree when you want OrderedHash
So RBTree is worth to bundle with Ruby

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>

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

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>

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 upper_bound(key) or lower_bound(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#lower_bound and MultiRBTree#upper_bound. 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, lower_bound, upper_bound, 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

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 upper_bound(key) or lower_bound(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, lower_bound, upper_bound, 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>

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.
 */

dnode_t *dict_lower_bound(dict_t *dict, const void *key)



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



Regards,

Bill

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.
>  */
> 
> dnode_t *dict_lower_bound(dict_t *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

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

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 upper_bound
( 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, dict_upper_bound() 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