Hi Georg.

> !SortedCollection methodsFor: 'testing' stamp: 'go 4/27/2000 13:05'!
> includes: anObject
>         "Answer whether anObject is one of the receiver's elements."
>
>         | idx |
>         idx := self indexForInserting: anObject.
>         ^(array atPin: idx) = anObject or: [(array atPin: idx - 1) =
> anObject ]! !

How will this behave when aSortedCollection has a sortBlock like [:x :y | x <= y],
and/or when the collection has duplicate elements in terms of order? Also, it
relies on #indexForInserting:. What if anObject is not compatible with the order
relationship specified in the sortBlock? Then it will fail instead of answering
false.

s _ SortedCollection sortBlock: [:x :y | x x + x y < (y x + y y)].
1 to: 5 do: [:each | 1 to: 5 do: [:some | s add: each @ some]].
s includes: 3 at 3.

In this example, the collection includes 3 at 3. The index for inserting 3 at 3 is 26,
but neither array at: 26 or array at: 25 is 3 at 3. Moreover, this fails:

s includes: #garbage.

*Perhaps* this could be fixed with exceptions... if the block triggers one, then
the object is incompatible and therefore it's not in the collection... I do not
think this assumption would be valid all the time.

Along these lines, I implemented QuickSearch for sorted collections as a separate
class whose instances are algorithms that know how to search. It has the advantage
that it avoids these problems when you do know what's inside a collection, and you
can also use the algorithm with something that is not a sorted collection, or even
with a different sort block. Together with an adapter, you can even run it in
things other than sequenceable collections, such as file streams.

> !SortedCollection methodsFor: 'adding' stamp: 'go 4/27/2000 13:16'!
> addAll: aCollection
>         "Optimize for large additions."
>
>         aCollection size > (self size // 3) ifTrue: [
>                 aCollection do: [ :each | super addLast: each ].
>                 self reSort ]
>          ifFalse: [ aCollection do: [ :each | self add: each ]].
>         ^aCollection! !

This may modify aCollection, although the collection supposed to be modified was
the receiver. Merge sort would be ok, but only if both collections had equivalent
(or nil) sortBlocks.

Andres.