1
|
1 |
"
|
|
2 |
COPYRIGHT (c) 1993 by Claus Gittinger
|
|
3 |
All Rights Reserved
|
|
4 |
|
|
5 |
This software is furnished under a license and may be used
|
|
6 |
only in accordance with the terms of that license and with the
|
|
7 |
inclusion of the above copyright notice. This software may not
|
|
8 |
be provided or otherwise made available to, or used by, any
|
|
9 |
other person. No title to or ownership of the software is
|
|
10 |
hereby transferred.
|
|
11 |
"
|
|
12 |
|
|
13 |
OrderedCollection subclass:#SortedCollection
|
|
14 |
instanceVariableNames:'sortBlock'
|
|
15 |
classVariableNames:'DefaultSortBlock'
|
|
16 |
poolDictionaries:''
|
|
17 |
category:'Collections-Ordered'
|
|
18 |
!
|
|
19 |
|
|
20 |
SortedCollection comment:'
|
|
21 |
|
|
22 |
COPYRIGHT (c) 1993 by Claus Gittinger
|
|
23 |
All Rights Reserved
|
|
24 |
|
|
25 |
I keep my elements sorted. The sort order is defined by a sortblock,
|
2
|
26 |
a two-argument block which, when given two elements of the collection,
|
|
27 |
returns true if the element given as first arg has to come before the
|
|
28 |
element given as second arg.
|
1
|
29 |
Thus a sortBlock of [:a :b | a < b] defines ascending sort-order,
|
|
30 |
while [:a :b | a > b] defines descening order.
|
2
|
31 |
The default sortBlock for SortedCollections is the first one.
|
1
|
32 |
|
13
|
33 |
$Header: /cvs/stx/stx/libbasic/SortedCollection.st,v 1.4 1993-12-11 00:58:06 claus Exp $
|
1
|
34 |
'!
|
|
35 |
|
|
36 |
!SortedCollection class methodsFor:'initialization'!
|
|
37 |
|
|
38 |
initialize
|
|
39 |
DefaultSortBlock := [:a :b | a < b ]
|
|
40 |
|
|
41 |
"SortedCollection initialize"
|
|
42 |
! !
|
|
43 |
|
|
44 |
!SortedCollection class methodsFor:'instance creation'!
|
|
45 |
|
|
46 |
new
|
2
|
47 |
"return a new sortedCollection, the sorting is done using
|
|
48 |
a compare for a > b, in ascending order"
|
|
49 |
|
1
|
50 |
^ super new setSortBlock:DefaultSortBlock
|
|
51 |
!
|
|
52 |
|
|
53 |
new:size
|
2
|
54 |
"return a new sortedCollection with preallocated size.
|
|
55 |
The sorting is done using a compare for a > b, in ascending order"
|
|
56 |
|
1
|
57 |
^ (super new:size) setSortBlock:DefaultSortBlock
|
|
58 |
!
|
|
59 |
|
|
60 |
sortBlock:aBlock
|
2
|
61 |
"set the sort-block"
|
|
62 |
|
1
|
63 |
^ super new setSortBlock:aBlock
|
|
64 |
! !
|
|
65 |
|
|
66 |
!SortedCollection methodsFor:'adding & removing'!
|
|
67 |
|
|
68 |
addFirst:anObject
|
2
|
69 |
"catch this - its not allowed for sortedCollections"
|
|
70 |
|
1
|
71 |
self shouldNotImplement
|
|
72 |
!
|
|
73 |
|
|
74 |
addLast:anObject
|
2
|
75 |
"catch this - its not allowed for sortedCollections"
|
|
76 |
|
1
|
77 |
self shouldNotImplement
|
|
78 |
!
|
|
79 |
|
|
80 |
at:index put:anObject
|
2
|
81 |
"catch this - its not allowed for sortedCollections"
|
|
82 |
|
1
|
83 |
self shouldNotImplement
|
|
84 |
!
|
|
85 |
|
|
86 |
add:newObject after:oldObject
|
2
|
87 |
"catch this - its not allowed for sortedCollections"
|
|
88 |
|
1
|
89 |
self shouldNotImplement
|
|
90 |
!
|
|
91 |
|
|
92 |
add:newObject before:oldObject
|
2
|
93 |
"catch this - its not allowed for sortedCollections"
|
|
94 |
|
1
|
95 |
self shouldNotImplement
|
|
96 |
!
|
|
97 |
|
|
98 |
addAll:aCollection
|
|
99 |
"add all elements of the argument, aCollection to the
|
|
100 |
receiver"
|
|
101 |
|
|
102 |
|mySize "{ Class: SmallInteger }"
|
|
103 |
otherSize "{ Class: SmallInteger }"
|
|
104 |
dstIndex "{ Class: SmallInteger }"
|
|
105 |
newSize newContents|
|
|
106 |
|
|
107 |
"if aCollection is bigger than a threshhold, its faster
|
|
108 |
to add all and resort - question: what is a good treshhold ?"
|
|
109 |
|
|
110 |
mySize := self size.
|
|
111 |
otherSize := aCollection size.
|
|
112 |
((mySize == 0) or:[otherSize > 5]) ifTrue:[
|
|
113 |
newSize := mySize + otherSize.
|
|
114 |
newContents := Array new:newSize.
|
|
115 |
newContents replaceFrom:1 to:mySize with:contentsArray startingAt:1.
|
|
116 |
(aCollection isKindOf:SequenceableCollection) ifTrue:[
|
|
117 |
"maybe we can do it in one big move"
|
|
118 |
newContents replaceFrom:(mySize + 1) to:newSize with:aCollection startingAt:1.
|
|
119 |
] ifFalse:[
|
|
120 |
dstIndex := mySize + 1.
|
|
121 |
aCollection do:[:element |
|
|
122 |
newContents at:dstIndex put:element.
|
|
123 |
dstIndex := dstIndex + 1
|
|
124 |
]
|
|
125 |
].
|
|
126 |
firstIndex := 1.
|
|
127 |
lastIndex := newSize.
|
|
128 |
contentsArray := newContents.
|
|
129 |
contentsArray sort:sortBlock.
|
|
130 |
^ self
|
|
131 |
].
|
|
132 |
super addAll:aCollection
|
|
133 |
|
|
134 |
"#(7 3 9 10 99) asSortedCollection addAll:#(77 0 1 16 5)"
|
|
135 |
!
|
|
136 |
|
|
137 |
add:anObject
|
|
138 |
"add the argument, anObject at the proper place in the
|
2
|
139 |
receiver. Returns the argument, anObject."
|
1
|
140 |
|
|
141 |
|sz index|
|
|
142 |
|
|
143 |
sz := self size.
|
|
144 |
sz == 0 ifTrue:[
|
13
|
145 |
super add:anObject
|
1
|
146 |
] ifFalse:[
|
|
147 |
index := self findIndexFor:anObject.
|
|
148 |
self makeRoomAtIndex:index.
|
|
149 |
contentsArray at:index put:anObject
|
|
150 |
].
|
|
151 |
^ anObject
|
|
152 |
! !
|
|
153 |
|
13
|
154 |
!SortedCollection methodsFor:'converting'!
|
|
155 |
|
|
156 |
asSortedCollection
|
|
157 |
"retrun the receiver as a sorted collection"
|
|
158 |
|
|
159 |
"could be an instance of a subclass..."
|
|
160 |
self class == SortedCollection ifTrue:[
|
|
161 |
^ self
|
|
162 |
].
|
|
163 |
^ super asSortedCollection
|
|
164 |
! !
|
|
165 |
|
1
|
166 |
!SortedCollection methodsFor:'testing'!
|
|
167 |
|
|
168 |
includes:anObject
|
|
169 |
"return true, if the argument, anObject is in the collection.
|
2
|
170 |
Redefined, since due to beeing sorted, the inclusion check can
|
|
171 |
be done with log-n compares i.e. much faster."
|
1
|
172 |
|
|
173 |
|index|
|
|
174 |
|
|
175 |
index := self findIndexFor:anObject.
|
|
176 |
^ (index <= self size) and:[(contentsArray at:index) = anObject]
|
2
|
177 |
|
|
178 |
"#(7 3 9 10 99) asSortedCollection includes:50"
|
|
179 |
"#(7 3 9 10 99) asSortedCollection includes:10"
|
1
|
180 |
!
|
|
181 |
|
|
182 |
occurrencesOf:anObject
|
|
183 |
"return how many times the argument, anObject is in the collection.
|
2
|
184 |
Redefined, since due to beeing sorted, the range of checked objects
|
|
185 |
can be limited i.e. it can be done much faster."
|
1
|
186 |
|
|
187 |
|index "{ Class: SmallInteger }"
|
|
188 |
mySize "{ Class: SmallInteger }"
|
|
189 |
tally "{ Class: SmallInteger }" |
|
|
190 |
|
|
191 |
index := self findIndexFor:anObject.
|
|
192 |
mySize := self size.
|
|
193 |
index > mySize ifTrue:[^ 0].
|
|
194 |
tally := 0.
|
|
195 |
[(index <= mySize) and:[(contentsArray at:index) = anObject]] whileTrue:[
|
|
196 |
tally := tally + 1.
|
|
197 |
index := index + 1
|
|
198 |
].
|
|
199 |
^ tally
|
2
|
200 |
|
|
201 |
"#(7 3 9 10 99) asSortedCollection occurrencesOf:50"
|
|
202 |
"#(7 3 9 10 99) asSortedCollection occurrencesOf:10"
|
|
203 |
"#(7 10 3 10 9 10 10 99) asSortedCollection occurrencesOf:10"
|
1
|
204 |
! !
|
|
205 |
|
|
206 |
!SortedCollection methodsFor:'instance protocol'!
|
|
207 |
|
|
208 |
sortBlock
|
|
209 |
"return the block used for sorting"
|
|
210 |
|
|
211 |
^ sortBlock
|
|
212 |
!
|
|
213 |
|
|
214 |
sortBlock:aSortBlock
|
|
215 |
"change the sort criteria for a sorted collection, resort the elements of
|
|
216 |
the collection, and return the receiver. The argument, aSortBlock must
|
|
217 |
be a two-argument block which returns true if its arg1 has to come before
|
|
218 |
its arg2 in the collection."
|
|
219 |
|
|
220 |
sortBlock := aSortBlock.
|
|
221 |
lastIndex > firstIndex ifTrue:[
|
|
222 |
contentsArray quickSortFrom:firstIndex to:lastIndex sortBlock:aSortBlock
|
|
223 |
]
|
|
224 |
|
|
225 |
"#(9 8 7 6 5 4 3) asSortedCollection"
|
2
|
226 |
"#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b]"
|
1
|
227 |
"#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b]"
|
2
|
228 |
"#($f $G $z $Y $o $H) asSortedCollection"
|
1
|
229 |
"#($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase]"
|
|
230 |
! !
|
|
231 |
|
|
232 |
!SortedCollection methodsFor:'private'!
|
|
233 |
|
|
234 |
setSortBlock: aSortBlock
|
|
235 |
"set the sortblock without resorting - private only"
|
|
236 |
|
|
237 |
sortBlock := aSortBlock
|
|
238 |
!
|
|
239 |
|
|
240 |
findIndexFor:anObject
|
|
241 |
"search the index at which to insert anObject. Can also be used
|
|
242 |
to search for an existing element by checking if the element at
|
|
243 |
the returned index is the one we look for."
|
|
244 |
|
|
245 |
|low "{ Class: SmallInteger}"
|
|
246 |
high "{ Class: SmallInteger}"
|
|
247 |
middle "{ Class: SmallInteger}"
|
|
248 |
element|
|
|
249 |
|
|
250 |
low := firstIndex.
|
|
251 |
high := lastIndex.
|
|
252 |
[low <= high] whileTrue:[
|
|
253 |
middle := (low + high) // 2.
|
|
254 |
element := super at:middle.
|
|
255 |
(sortBlock value:element value:anObject) ifTrue:[
|
|
256 |
"middleelement is smaller than object"
|
|
257 |
low := middle + 1
|
|
258 |
] ifFalse:[
|
|
259 |
high := middle - 1
|
|
260 |
]
|
|
261 |
].
|
|
262 |
^ low
|
|
263 |
|
2
|
264 |
"#(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection findIndexFor:50"
|
1
|
265 |
|
|
266 |
! !
|