On Dec 19, 2010, at 10:10 AM, Andreas Raab wrote:

> 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

In GemStone we used to do a binary search on #'includes:' but a customer complained that they had a domain object where #'=' was implemented using different instance variables than #'<=' so that a linear search would find an equivalent object but a binary search would miss it. We changed #'includes:' to use a linear search and added another method, #'binarySearchIncludes:' to have the old (fast) behavior.

James

> ; 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
> 
>