[squeak-dev] Re: includes: does linear search for SortedCollection???????

Andreas Raab andreas.raab at gmx.de
Sun Dec 19 18:10:13 UTC 2010


On 12/19/2010 9:55 AM, Levente Uzonyi wrote:
> On Sun, 19 Dec 2010, Igor Stasenko wrote:
>
>> On 19 December 2010 18:11, Ralph Boland <rpboland at gmail.com> wrote:
>>> The main advantage of a sorted list is that binary search can be
>>> performed on the list.
>>> So I was surprised to find that the method SortedCollection>>includes:
>>> (actually OrderedColection>includes:) does a linear search (Squeaks
>>> 10.2 and 4.1).
>>>
>>> I suggest we implement a version of SortedCollection>>includes: that
>>> runs in O(log n)
>>> time.  I can write this if desired or just about anybody.
>>>
>> you can do binary search if argument can be passed to sort block and
>> respond to any message(s) which sort block sends to it for determining
>> its order.
>>
>> and what you suppose to do with:
>> coll includes: nil
>>
>> or any other argument, which can't be used for binary search?
>
> You can catch the error and return false.

I'd say let it blow. I'm with Ralph on this one; SortedCollection really 
ought to use binary search. Inclusion should be defined in terms of the 
comparable that's being used in the collection; if (for example) 
"aSortedCollection add: nil" blows up, why would you then expect 
"aSortedCollection includes: nil" not to?

Generally speaking, SortedCollection already operates on a subdomain and 
not arbirary objects. I think it is reasonable to expect #includes: to 
have the same set of constraints.

ObRidiculous:

	(SortedCollection new)
		add: nil;  "<- works"
		add: 3.    "<- blows"

Cheers,
   - Andreas



More information about the Squeak-dev mailing list