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@3.
In this example, the collection includes 3@3. The index for inserting 3@3 is 26, but neither array at: 26 or array at: 25 is 3@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.