[ruby-core:28863] Re: [Feature #2348] RBTree Should be Added to the Standard Library

Hi,

Thank you for your detailed reply!


2010/3/22 Bill Kelly <[e-mail]>:
> 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 <[e-mail]>