[FIX][ENH] SortedCollection robustness & speedup

Florin X Mateoc mateoc_florin at jpmorgan.com
Thu Apr 27 20:09:35 UTC 2000


Georg,

I am afraid your implementation of the #includes: method only works for the
particular cases where the object is arithmetically compared directly.

I took a stab at (re)implementing #includes and #indexOf: for the
SequenceableCollection classes.

'From Squeak2.8alpha of 19 January 2000 [latest update: #2042] on 26 April 2000
at 4:01:18 pm'!

!SequenceableCollection methodsFor: 'accessing' stamp: 'fm 4/26/2000 15:13'!

indexOf: anElement
     "Answer the index of anElement within the receiver. If the receiver does
     not contain anElement, answer 0."
     1 to: self size do:
          [:i | (self at: i) = anElement ifTrue: [^ i]].
     ^ 0! !

!SequenceableCollection methodsFor: 'testing' stamp: 'fm 4/26/2000 15:36'!

includes: anObject
     ^(self indexOf: anObject) ~~ 0! !

!OrderedCollection methodsFor: 'accessing' stamp: 'fm 4/26/2000 15:39'!

indexOf: anObject
     firstIndex to: lastIndex do:
          [:index |
          anObject = (array at: index) ifTrue: [^index + 1 - firstIndex]].
     ^ 0! !

!SortedCollection methodsFor: 'accessing' stamp: 'fm 4/26/2000 15:08'!

indexOf: newObject
     | index low |
     low := self indexForInserting: newObject.
     sortBlock isNil
          ifTrue: [
               index := low -1.
               ^[index >= firstIndex and: [(array at: index) = newObject] ]
                    ifTrue: [low - firstIndex]
                    ifFalse: [0]]
          ifFalse: [
               index := low -1.
               [index >= firstIndex and:
               [(sortBlock value: (array at: index) value: newObject) and:
               [sortBlock value: newObject value: (array at: index)]]]
                    whileTrue:
                         [(array at: index) = newObject
                              ifTrue: [^index + 1 - firstIndex].
                         index := index - 1].
               index := low.
               [index <= lastIndex and:
               [(sortBlock value: (array at: index) value: newObject) not and:
               [(sortBlock value: newObject value: (array at: index)) not]]]
                    whileTrue:
                         [(array at: index) = newObject
                              ifTrue: [^index + 1 - firstIndex].
                         index := index + 1].
               ^0]! !


Cheers,

Florin

P.S. I have also included the above code as an attachement(See attached file:
collections.1.cs)



<snip>

!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 ]! !

<snip>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: collections.1.cs
Type: application/octet-stream
Size: 1647 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20000427/5da2c3bc/collections.1.obj


More information about the Squeak-dev mailing list