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

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