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

Levente Uzonyi leves at elte.hu
Sun Dec 19 18:14:50 UTC 2010


On Sun, 19 Dec 2010, Igor Stasenko wrote:

> 2010/12/19 Levente Uzonyi <leves at elte.hu>:
>> 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.
>>
>
> yes.. and so, you can't make difference between 'it is really not in
> collection' and its 'not in a collection' ,
> because sort block may trigger an error due to some mistake, which
> occurs only for particular object :)

If the object is in the collection, then it was already used several times 
with the sortblock and the user got the error (or will get it soon).
If it's not in the collection and the error is raised, then you should 
return false anyway.


Levente

>
>>
>> Levente
>>
>>>
>>>
>>>
>>>> Regards,
>>>>
>>>> Ralph Boland
>>>>
>>>> --
>>>> Quantum Theory cannot save us from the tyranny of a deterministic
>>>> universe
>>>> but it does give God something to do
>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> Best regards,
>>> Igor Stasenko AKA sig.
>>>
>>
>>
>>
>>
>
>
>
> -- 
> Best regards,
> Igor Stasenko AKA sig.
>
>


More information about the Squeak-dev mailing list