From: Bill Kelly <billk@...>
Date: 2010-03-23T08:07:13+09:00
Subject: [ruby-core:28879] Re: [Feature #2348] RBTree Should be Added to the Standard Library

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