--- a/SortedCollection.st Thu May 12 04:07:15 1994 +0200
+++ b/SortedCollection.st Tue May 17 12:09:46 1994 +0200
@@ -22,16 +22,23 @@
COPYRIGHT (c) 1993 by Claus Gittinger
All Rights Reserved
-I keep my elements sorted. The sort order is defined by a sortblock,
-a two-argument block which, when given two elements of the collection,
-returns true if the element given as first arg has to come before the
-element given as second arg.
-Thus a sortBlock of [:a :b | a < b] defines ascending sort-order,
-while [:a :b | a > b] defines descening order.
-The default sortBlock for SortedCollections is the first one.
+$Header: /cvs/stx/stx/libbasic/SortedCollection.st,v 1.8 1994-05-17 10:09:16 claus Exp $
+'!
+
+!SortedCollection class methodsFor:'documentation'!
-$Header: /cvs/stx/stx/libbasic/SortedCollection.st,v 1.7 1994-02-25 13:05:35 claus Exp $
-'!
+documentation
+"
+ I keep my elements sorted. The sort order is defined by a sortblock,
+ a two-argument block which, when given two elements of the collection,
+ should return true if the element given as first arg has to come before the
+ element given as second arg.
+
+ Thus a sortBlock of [:a :b | a < b] defines ascending sort-order,
+ while [:a :b | a > b] defines descening order.
+ The default sortBlock for SortedCollections is the first one.
+"
+! !
!SortedCollection class methodsFor:'initialization'!
@@ -113,7 +120,7 @@
newSize := mySize + otherSize.
newContents := Array new:newSize.
newContents replaceFrom:1 to:mySize with:contentsArray startingAt:1.
- (aCollection isKindOf:SequenceableCollection) ifTrue:[
+ aCollection isSequenceableCollection ifTrue:[
"maybe we can do it in one big move"
newContents replaceFrom:(mySize + 1) to:newSize with:aCollection startingAt:1.
] ifFalse:[
@@ -131,7 +138,9 @@
].
super addAll:aCollection
- "#(7 3 9 10 99) asSortedCollection addAll:#(77 0 1 16 5)"
+ "
+ #(7 3 9 10 99) asSortedCollection addAll:#(77 0 1 16 5)
+ "
!
add:anObject
@@ -143,11 +152,17 @@
lastIndex < firstIndex "i.e. self size == 0" ifTrue:[
super add:anObject
] ifFalse:[
- index := self findIndexFor:anObject.
+ index := self indexForInserting:anObject.
self makeRoomAtIndex:index.
contentsArray at:index put:anObject
].
^ anObject
+
+ "
+ |c| #(7 3 9 10 99) asSortedCollection add:5; yourself
+ #(7 3 9 10 99) asSortedCollection add:1; yourself
+ #(7 3 9 10 99) asSortedCollection add:1000; yourself
+ "
! !
!SortedCollection methodsFor:'converting'!
@@ -171,12 +186,14 @@
|index "{ Class: SmallInteger }"|
- index := self findIndexFor:anObject.
+ index := self indexForInserting:anObject.
((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ false].
^ (contentsArray at:index) = anObject
- "#(7 3 9 10 99) asSortedCollection includes:50"
- "#(7 3 9 10 99) asSortedCollection includes:10"
+ "
+ #(7 3 9 10 99) asSortedCollection includes:50
+ #(7 3 9 10 99) asSortedCollection includes:10
+ "
!
occurrencesOf:anObject
@@ -187,7 +204,7 @@
|index "{ Class: SmallInteger }"
tally "{ Class: SmallInteger }" |
- index := self findIndexFor:anObject.
+ index := self indexForInserting:anObject.
((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
tally := 0.
@@ -197,9 +214,92 @@
].
^ tally
- "#(7 3 9 10 99) asSortedCollection occurrencesOf:50"
- "#(7 3 9 10 99) asSortedCollection occurrencesOf:10"
- "#(7 10 3 10 9 10 10 99) asSortedCollection occurrencesOf:10"
+ "
+ #(7 3 9 10 99) asSortedCollection occurrencesOf:50
+ #(7 3 9 10 99) asSortedCollection occurrencesOf:10
+ #(7 10 3 10 9 10 10 99) asSortedCollection occurrencesOf:10
+ "
+! !
+
+!SortedCollection methodsFor:'searching'!
+
+before:anObject
+ "return the element before the argument, anObject; or nil if there is none.
+ If the receiver does not contain anObject, report an error"
+
+ ^ self before:anObject ifAbsent:[self error:'no such element']
+
+ "
+ #(7 3 9 10 99) asSortedCollection before:50
+ #(7 3 9 10 99) asSortedCollection before:1
+ #(7 3 9 10 99) asSortedCollection before:1000
+ #(7 3 9 10 99) asSortedCollection before:10
+ #(7 3 9 10 99) asSortedCollection before:7
+ #(7 3 9 10 99) asSortedCollection before:99
+ #(7 10 3 10 9 10 10 99) asSortedCollection before:9
+ #(7 10 3 10 9 10 10 99) asSortedCollection before:10
+ "
+!
+
+before:anObject ifAbsent:exceptionBlock
+ "return the element before the argument, anObject; or nil if there is none.
+ If the receiver does not contain anObject, return the result from evaluating
+ exceptionBlock."
+
+ |index "{ Class: SmallInteger }"|
+
+ index := self indexForInserting:anObject.
+ ((index <= firstIndex)
+ or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value].
+
+ ^ contentsArray at:index - 1
+
+ "
+ #(7 3 9 10 99) asSortedCollection before:50
+ #(7 3 9 10 99) asSortedCollection before:1
+ #(7 3 9 10 99) asSortedCollection before:10
+ #(7 3 9 10 99) asSortedCollection before:7
+ #(7 3 9 10 99) asSortedCollection before:99
+ #(7 10 3 10 9 10 10 99) asSortedCollection before:9
+ #(7 10 3 10 9 10 10 99) asSortedCollection before:10
+ "
+!
+
+after:anObject
+ "return the element after the argument, anObject; or nil if there is none.
+ If the receiver does not contain anObject, report an error"
+
+ ^ self after:anObject ifAbsent:[self error:'no such element']
+
+ "
+ #(7 3 9 10 99) asSortedCollection after:50
+ #(7 3 9 10 99) asSortedCollection after:1
+ #(7 3 9 10 99) asSortedCollection after:10
+ #(7 3 9 10 99) asSortedCollection after:7
+ #(7 3 9 10 99) asSortedCollection after:99
+ #(7 10 3 10 9 10 10 99) asSortedCollection after:9
+ #(7 10 3 10 9 10 10 99) asSortedCollection after:10
+ "
+!
+
+after:anObject ifAbsent:exceptionBlock
+ "return the element after the argument, anObject; or nil if there is none.
+ If the receiver does not contain anObject, return the result from evaluating
+ exceptionBlock."
+
+ |index "{ Class: SmallInteger }"|
+
+ index := self indexForInserting:anObject.
+ ((index < firstIndex)
+ or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value].
+
+ "skip multiple occurences of the same ..."
+
+ [(index <= lastIndex) and:[(contentsArray at:index) = anObject]] whileTrue:[
+ index := index + 1
+ ].
+ (index > lastIndex) ifTrue:[^ nil].
+ ^ contentsArray at:index
! !
!SortedCollection methodsFor:'instance protocol'!
@@ -221,11 +321,13 @@
contentsArray quickSortFrom:firstIndex to:lastIndex sortBlock:aSortBlock
]
- "#(9 8 7 6 5 4 3) asSortedCollection"
- "#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b]"
- "#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b]"
- "#($f $G $z $Y $o $H) asSortedCollection"
- "#($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase]"
+ "
+ #(9 8 7 6 5 4 3) asSortedCollection
+ #(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b]
+ #(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b]
+ #($f $G $z $Y $o $H) asSortedCollection
+ #($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase]
+ "
! !
!SortedCollection methodsFor:'private'!
@@ -236,7 +338,7 @@
sortBlock := aSortBlock
!
-findIndexFor:anObject
+indexForInserting:anObject
"search the index at which to insert anObject. Can also be used
to search for an existing element by checking if the element at
the returned index is the one we look for.
@@ -247,6 +349,10 @@
middle "{ Class: SmallInteger}"
element|
+ "
+ we can of course use a binary search - since the elements are
+ sorted
+ "
low := firstIndex.
high := lastIndex.
[low <= high] whileTrue:[
@@ -261,5 +367,9 @@
].
^ low
- "#(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection findIndexFor:50"
+ "
+ #(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50
+ #(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50
+ "
+
! !