author | Claus Gittinger <cg@exept.de> |
Fri, 19 Apr 1996 12:47:25 +0200 | |
changeset 1221 | 46d72af387e9 |
parent 1175 | 7ca26065cf02 |
child 1290 | 15ba3221b89b |
permissions | -rw-r--r-- |
1 | 1 |
" |
2 |
COPYRIGHT (c) 1993 by Claus Gittinger |
|
159 | 3 |
All Rights Reserved |
1 | 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 |
|
1155 | 14 |
instanceVariableNames:'sortBlock' |
15 |
classVariableNames:'DefaultSortBlock' |
|
16 |
poolDictionaries:'' |
|
17 |
category:'Collections-Sequenceable' |
|
1 | 18 |
! |
19 |
||
77 | 20 |
!SortedCollection class methodsFor:'documentation'! |
1 | 21 |
|
88 | 22 |
copyright |
23 |
" |
|
24 |
COPYRIGHT (c) 1993 by Claus Gittinger |
|
159 | 25 |
All Rights Reserved |
88 | 26 |
|
27 |
This software is furnished under a license and may be used |
|
28 |
only in accordance with the terms of that license and with the |
|
29 |
inclusion of the above copyright notice. This software may not |
|
30 |
be provided or otherwise made available to, or used by, any |
|
31 |
other person. No title to or ownership of the software is |
|
32 |
hereby transferred. |
|
33 |
" |
|
34 |
! |
|
35 |
||
77 | 36 |
documentation |
37 |
" |
|
38 |
I keep my elements sorted. The sort order is defined by a sortblock, |
|
39 |
a two-argument block which, when given two elements of the collection, |
|
40 |
should return true if the element given as first arg has to come before the |
|
41 |
element given as second arg. |
|
42 |
||
1156 | 43 |
Equal elements may occur multiple times. |
44 |
||
45 |
SortedCollection uses quickSort to resort and a binary search when adding/removing |
|
46 |
elements. |
|
47 |
Because insertion/removal may require that remaining elements have to |
|
48 |
be shifted within the container, adding many individual elements may be done faster |
|
49 |
by creating a completely new collection from the unsorted elements. |
|
1167 | 50 |
(see examples) |
1156 | 51 |
|
77 | 52 |
Thus a sortBlock of [:a :b | a < b] defines ascending sort-order, |
53 |
while [:a :b | a > b] defines descening order. |
|
54 |
The default sortBlock for SortedCollections is the first one. |
|
55 |
" |
|
1167 | 56 |
! |
57 |
||
58 |
examples |
|
59 |
" |
|
1175 | 60 |
when many elements are to be added, it may be better to add them |
61 |
all en-bloeque instead of individually. |
|
1167 | 62 |
The reason is that for each individual #add:, the contents has to be |
1175 | 63 |
shifted, to create an empty slot for the new element. |
1167 | 64 |
|
65 |
timing example: |
|
66 |
||
67 |
|o rnd| |
|
68 |
||
69 |
o := SortedCollection new. |
|
70 |
rnd := Random new. |
|
1175 | 71 |
10000 timesRepeat:[ |
1167 | 72 |
o add:rnd next. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
73 |
] |
1167 | 74 |
|
1175 | 75 |
takes 1365 ms on a P5 (admitted: this is a fast machine ;-) |
1167 | 76 |
In contrast: |
77 |
||
78 |
|o rnd| |
|
79 |
||
80 |
o := OrderedCollection new. |
|
81 |
rnd := Random new. |
|
1175 | 82 |
10000 timesRepeat:[ |
1167 | 83 |
o add:rnd next. |
84 |
]. |
|
85 |
o := o asSortedCollection |
|
86 |
||
1175 | 87 |
takes 383 ms on the same machine. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
88 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
89 |
If you already have a big sortedCollection at hand, adding multiple |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
90 |
items may be better done with #addAll:, which resorts all elements, if |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
91 |
the number of added items is more than some threshold number. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
92 |
Building some big collection: |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
93 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
94 |
|o rnd c| |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
95 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
96 |
o := OrderedCollection new. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
97 |
rnd := Random new. |
1175 | 98 |
10000 timesRepeat:[ |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
99 |
o add:rnd next. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
100 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
101 |
o := o asSortedCollection. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
102 |
|
1175 | 103 |
adding 1000 elements individually to it: |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
104 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
105 |
1000 timesRepeat:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
106 |
o add:rnd next. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
107 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
108 |
|
1175 | 109 |
takes 258 ms |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
110 |
(because the elements have to be shifted around for each added element); |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
111 |
|
1175 | 112 |
while adding them en-bloque with: |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
113 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
114 |
c := OrderedCollection new. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
115 |
1000 timesRepeat:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
116 |
c add:rnd next. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
117 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
118 |
o addAll:o |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
119 |
|
1175 | 120 |
takes 71 ms |
1167 | 121 |
" |
77 | 122 |
! ! |
1 | 123 |
|
124 |
!SortedCollection class methodsFor:'initialization'! |
|
125 |
||
126 |
initialize |
|
1155 | 127 |
"setup the default sortBlock." |
128 |
||
129 |
"/ only do this once at early startup |
|
913 | 130 |
DefaultSortBlock isNil ifTrue:[ |
1155 | 131 |
DefaultSortBlock := [:a :b | a < b ] |
913 | 132 |
] |
1 | 133 |
|
913 | 134 |
" |
135 |
SortedCollection initialize |
|
136 |
" |
|
1155 | 137 |
|
138 |
"Modified: 12.4.1996 / 12:29:27 / cg" |
|
1 | 139 |
! ! |
140 |
||
141 |
!SortedCollection class methodsFor:'instance creation'! |
|
142 |
||
143 |
new |
|
2 | 144 |
"return a new sortedCollection, the sorting is done using |
1155 | 145 |
a compare for a < b, in ascending order" |
2 | 146 |
|
1 | 147 |
^ super new setSortBlock:DefaultSortBlock |
1155 | 148 |
|
149 |
"Modified: 12.4.1996 / 12:28:18 / cg" |
|
1 | 150 |
! |
151 |
||
152 |
new:size |
|
2 | 153 |
"return a new sortedCollection with preallocated size. |
1155 | 154 |
The sorting is done using a compare for a < b, in ascending order" |
2 | 155 |
|
1 | 156 |
^ (super new:size) setSortBlock:DefaultSortBlock |
1155 | 157 |
|
158 |
"Modified: 12.4.1996 / 12:28:22 / cg" |
|
1 | 159 |
! |
160 |
||
161 |
sortBlock:aBlock |
|
1155 | 162 |
"return a new sortedCollection, whe the sort order is defined |
163 |
by aBlock. |
|
164 |
This must be a two-argument block which returns true if its arg1 has to come before |
|
165 |
its arg2 in the collection." |
|
2 | 166 |
|
1 | 167 |
^ super new setSortBlock:aBlock |
1155 | 168 |
|
169 |
"default: |
|
170 |
|s| |
|
171 |
||
172 |
s := SortedCollection new. |
|
173 |
s add:15; add:99; add:3; add:-29; add:17; add:-6. |
|
174 |
Transcript showCr:s |
|
175 |
" |
|
176 |
||
177 |
"sorting by absolute values: |
|
178 |
|s| |
|
179 |
||
180 |
s := SortedCollection sortBlock:[:a :b | a abs < b abs]. |
|
181 |
s add:15; add:99; add:3; add:29; add:17; add:-6. |
|
182 |
Transcript showCr:s |
|
183 |
" |
|
184 |
||
185 |
"default again: |
|
186 |
|s| |
|
187 |
||
188 |
s := SortedCollection new. |
|
189 |
s add:'foo'; add:'Bar'; add:'baz'; add:'hello'; add:'world'; add:'Wow'. |
|
190 |
Transcript showCr:s |
|
191 |
" |
|
192 |
||
193 |
"sorting strings caseless: |
|
194 |
|s| |
|
195 |
||
196 |
s := SortedCollection sortBlock:[:a :b | a asLowercase < b asLowercase]. |
|
197 |
s add:'foo'; add:'Bar'; add:'baz'; add:'hello'; add:'world'; add:'Wow'. |
|
198 |
Transcript showCr:s |
|
199 |
" |
|
200 |
||
201 |
"Modified: 12.4.1996 / 12:26:28 / cg" |
|
329 | 202 |
! |
203 |
||
204 |
withAll:aCollection sortBlock:aBlock |
|
205 |
"initialize from aCollection and set the sort-block" |
|
206 |
||
207 |
^ (self sortBlock:aBlock) addAll:aCollection |
|
208 |
||
209 |
" |
|
210 |
SortedCollection withAll:#(1 2 3 4 5 6 7 8 9 0) |
|
1155 | 211 |
sortBlock:[:a :b | a > b] |
212 |
" |
|
213 |
||
214 |
"default: |
|
215 |
|s| |
|
216 |
||
217 |
s := SortedCollection withAll:#(15 99 3 29 17 -6). |
|
218 |
Transcript showCr:s |
|
219 |
" |
|
220 |
||
221 |
"sorting by absolute values: |
|
222 |
|s| |
|
223 |
||
224 |
s := SortedCollection withAll:#(15 99 3 29 17 -6) sortBlock:[:a :b | a abs < b abs]. |
|
225 |
Transcript showCr:s |
|
329 | 226 |
" |
1155 | 227 |
|
228 |
"default again: |
|
229 |
|s| |
|
230 |
||
231 |
s := SortedCollection withAll:#('foo' 'Bar' 'baz' 'hello' 'world' 'Wow'). |
|
232 |
Transcript showCr:s |
|
233 |
" |
|
234 |
||
235 |
"sorting strings caseless: |
|
236 |
|s| |
|
237 |
||
238 |
s := SortedCollection withAll:#('foo' 'Bar' 'baz' 'hello' 'world' 'Wow') sortBlock:[:a :b | a asLowercase < b asLowercase]. |
|
239 |
Transcript showCr:s |
|
240 |
" |
|
241 |
||
242 |
"Modified: 12.4.1996 / 12:28:09 / cg" |
|
1 | 243 |
! ! |
244 |
||
245 |
!SortedCollection methodsFor:'adding & removing'! |
|
246 |
||
607 | 247 |
add:anObject |
248 |
"add the argument, anObject at the proper place in the |
|
249 |
receiver. Returns the argument, anObject." |
|
2 | 250 |
|
607 | 251 |
|index| |
1 | 252 |
|
607 | 253 |
lastIndex < firstIndex "i.e. self size == 0" ifTrue:[ |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
254 |
super add:anObject |
607 | 255 |
] ifFalse:[ |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
256 |
index := self indexForInserting:anObject. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
257 |
index := self makeRoomAtIndex:index. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
258 |
contentsArray at:index put:anObject |
607 | 259 |
]. |
260 |
^ anObject |
|
2 | 261 |
|
607 | 262 |
" |
263 |
|c| #(7 3 9 10 99) asSortedCollection add:5; yourself |
|
264 |
#(7 3 9 10 99) asSortedCollection add:1; yourself |
|
265 |
#(7 3 9 10 99) asSortedCollection add:1000; yourself |
|
266 |
" |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
267 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
268 |
"Modified: 12.4.1996 / 16:47:41 / cg" |
1 | 269 |
! |
270 |
||
271 |
add:newObject after:oldObject |
|
2 | 272 |
"catch this - its not allowed for sortedCollections" |
273 |
||
1 | 274 |
self shouldNotImplement |
275 |
! |
|
276 |
||
277 |
add:newObject before:oldObject |
|
2 | 278 |
"catch this - its not allowed for sortedCollections" |
279 |
||
1 | 280 |
self shouldNotImplement |
281 |
! |
|
282 |
||
283 |
addAll:aCollection |
|
284 |
"add all elements of the argument, aCollection to the |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
285 |
receiver. Returns the argument, aCollection." |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
286 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
287 |
|newContents| |
1 | 288 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
289 |
"/ special case: I am empty - add them en-bloque. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
290 |
"/ (but only if the argument is not a sortedCollection, |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
291 |
"/ because quicksort degenerates to a veeery slow operation then) |
1 | 292 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
293 |
(self size == 0 and:[aCollection isSorted not]) ifTrue:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
294 |
newContents := Array withAll:(aCollection asArray). |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
295 |
newContents == aCollection ifTrue:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
296 |
newContents := newContents shallowCopy |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
297 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
298 |
newContents sort:sortBlock. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
299 |
contentsArray := newContents. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
300 |
firstIndex := 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
301 |
lastIndex := newContents size. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
302 |
^ aCollection |
1 | 303 |
]. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
304 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
305 |
"/ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
306 |
"/ do a mergeSort |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
307 |
"/ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
308 |
self mergeSorted:(aCollection asSortedCollection). |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
309 |
^ aCollection |
1 | 310 |
|
77 | 311 |
" |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
312 |
#(7 3 9 10 99) asSortedCollection addAll:#(77 0 1 16 5); yourself |
77 | 313 |
" |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
314 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
315 |
"Modified: 13.4.1996 / 12:42:15 / cg" |
1 | 316 |
! |
317 |
||
607 | 318 |
addFirst:anObject |
319 |
"catch this - its not allowed for sortedCollections" |
|
320 |
||
321 |
self shouldNotImplement |
|
322 |
! |
|
1 | 323 |
|
607 | 324 |
addLast:anObject |
325 |
"catch this - its not allowed for sortedCollections" |
|
326 |
||
327 |
self shouldNotImplement |
|
328 |
! |
|
1 | 329 |
|
607 | 330 |
at:index put:anObject |
331 |
"catch this - its not allowed for sortedCollections" |
|
332 |
||
333 |
self shouldNotImplement |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
334 |
! |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
335 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
336 |
mergeSorted:aSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
337 |
"add all elements of the argument, aSortedCollection to the |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
338 |
receiver. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
339 |
This leads to an error, if the argument is not a sortedCollection. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
340 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
341 |
This should be used when a number of elements is to be added. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
342 |
Notice, that quicksort degenerates to a veeery slow bubble-like |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
343 |
sort when a collection of already sorted elements is given to it. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
344 |
Therefore, adding chunks is better done by sorting the chunk and merging |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
345 |
it in, instead of resorting the receiver." |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
346 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
347 |
|newContentsArray |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
348 |
contentsArray2 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
349 |
destIndex "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
350 |
n1 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
351 |
n2 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
352 |
srcIndex1 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
353 |
srcIndex2 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
354 |
last1 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
355 |
last2 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
356 |
end1Reached end2Reached |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
357 |
el1 el2 | |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
358 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
359 |
n1 := self size. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
360 |
n2 := aSortedCollection size. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
361 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
362 |
newContentsArray := Array new:(n1 + n2). |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
363 |
destIndex := 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
364 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
365 |
contentsArray2 := aSortedCollection contentsArray. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
366 |
srcIndex2 := aSortedCollection firstIndex. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
367 |
last2 := srcIndex2 + n2 -1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
368 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
369 |
srcIndex1 := firstIndex. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
370 |
last1 := srcIndex1 + n1 -1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
371 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
372 |
(srcIndex1 <= last1 and:[srcIndex2 <= last2]) ifTrue:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
373 |
el1 := contentsArray at:srcIndex1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
374 |
el2 := contentsArray2 at:srcIndex2. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
375 |
end1Reached := end2Reached := false. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
376 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
377 |
[end1Reached or:[end2Reached]] whileFalse:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
378 |
(sortBlock value:el1 value:el2) ifTrue:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
379 |
"/ el1 to come before el2 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
380 |
newContentsArray at:destIndex put:el1. destIndex := destIndex + 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
381 |
srcIndex1 := srcIndex1 + 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
382 |
srcIndex1 <= last1 ifTrue:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
383 |
el1 := contentsArray at:srcIndex1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
384 |
] ifFalse:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
385 |
end1Reached := true |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
386 |
] |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
387 |
] ifFalse:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
388 |
"/ el2 to come before el1 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
389 |
newContentsArray at:destIndex put:el2. destIndex := destIndex + 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
390 |
srcIndex2 := srcIndex2 + 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
391 |
srcIndex2 <= last2 ifTrue:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
392 |
el2 := contentsArray2 at:srcIndex2. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
393 |
] ifFalse:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
394 |
end2Reached := true |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
395 |
] |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
396 |
] |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
397 |
] |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
398 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
399 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
400 |
"/ fill up with remaining elements from source1 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
401 |
(srcIndex1 <= last1) ifTrue:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
402 |
newContentsArray |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
403 |
replaceFrom:destIndex |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
404 |
with:contentsArray |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
405 |
startingAt:srcIndex1 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
406 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
407 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
408 |
"/ fill up with remaining elements from source2 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
409 |
(srcIndex2 <= last2) ifTrue:[ |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
410 |
newContentsArray |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
411 |
replaceFrom:destIndex |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
412 |
with:contentsArray2 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
413 |
startingAt:srcIndex2 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
414 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
415 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
416 |
firstIndex := 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
417 |
lastIndex := n1 + n2. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
418 |
contentsArray := newContentsArray |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
419 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
420 |
" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
421 |
#(7 3 9 10 99) asSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
422 |
mergeSorted:#(77 0 1 16 5) asSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
423 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
424 |
#(7 3 9 10 99) asSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
425 |
mergeSorted:#(77 0 3 1 98 99 16 5) asSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
426 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
427 |
#() asSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
428 |
mergeSorted:#(77 0 3 1 98 99 16 5) asSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
429 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
430 |
#(7 3 9 10 99) asSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
431 |
mergeSorted:#() asSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
432 |
" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
433 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
434 |
"Modified: 13.4.1996 / 12:48:34 / cg" |
607 | 435 |
! ! |
436 |
||
437 |
!SortedCollection methodsFor:'converting'! |
|
438 |
||
439 |
asSortedCollection |
|
440 |
"return the receiver as a sorted collection" |
|
441 |
||
442 |
"could be an instance of a subclass..." |
|
443 |
self class == SortedCollection ifTrue:[ |
|
444 |
^ self |
|
1 | 445 |
]. |
607 | 446 |
^ super asSortedCollection |
1 | 447 |
! ! |
448 |
||
95 | 449 |
!SortedCollection methodsFor:'copying'! |
450 |
||
607 | 451 |
copyEmpty:size |
452 |
"return a copy of the receiver with no elements, but |
|
453 |
the same size. This method has been be redefined to |
|
454 |
preserve the sortBlock." |
|
455 |
||
456 |
^ (self species new:size) sortBlock:sortBlock |
|
457 |
! |
|
458 |
||
159 | 459 |
postCopyFrom:anOriginal |
460 |
"sent after a copy or when a new collection species has been created. |
|
95 | 461 |
The new collection should have the same sortBlock as the original." |
462 |
||
159 | 463 |
sortBlock := anOriginal sortBlock |
95 | 464 |
|
465 |
" |
|
466 |
#(4 7 1 99 -1 17) asSortedCollection inspect |
|
159 | 467 |
#(4 7 1 99 -1 17) asSortedCollection copy inspect |
95 | 468 |
(#(4 7 1 99 -1 17) asSortedCollection sortBlock:[:a :b | a > b]) inspect |
159 | 469 |
(#(4 7 1 99 -1 17) asSortedCollection sortBlock:[:a :b | a > b]) copy inspect |
470 |
(#(4 7 1 99 -1 17) asSortedCollection select:[:e| e even]) inspect |
|
95 | 471 |
" |
472 |
! ! |
|
473 |
||
216 | 474 |
!SortedCollection methodsFor:'enumerating'! |
184 | 475 |
|
476 |
collect:aBlock |
|
477 |
"evaluate the argument, aBlock for every element in the collection |
|
478 |
and return a collection of the results. Redefined to return an OrderedCollection; |
|
479 |
see X3J20 spec. (SortedCollection>>collect: should return an OrderedCollection)" |
|
480 |
||
481 |
|newCollection |
|
482 |
start "{ Class:SmallInteger }" |
|
483 |
stop "{ Class:SmallInteger }" | |
|
484 |
||
485 |
newCollection := OrderedCollection new:(self size). |
|
486 |
stop := lastIndex. |
|
487 |
start := firstIndex. |
|
488 |
start to:stop do:[:index | |
|
489 |
newCollection add:(aBlock value:(contentsArray at:index)). |
|
490 |
]. |
|
491 |
^ newCollection |
|
492 |
! ! |
|
493 |
||
607 | 494 |
!SortedCollection methodsFor:'instance protocol'! |
495 |
||
496 |
sortBlock |
|
497 |
"return the block used for sorting" |
|
498 |
||
499 |
^ sortBlock |
|
500 |
! |
|
501 |
||
502 |
sortBlock:aSortBlock |
|
503 |
"change the sort criteria for a sorted collection, resort the elements of |
|
504 |
the collection, and return the receiver. The argument, aSortBlock must |
|
505 |
be a two-argument block which returns true if its arg1 has to come before |
|
506 |
its arg2 in the collection." |
|
507 |
||
508 |
sortBlock := aSortBlock. |
|
509 |
lastIndex > firstIndex ifTrue:[ |
|
510 |
contentsArray quickSortFrom:firstIndex to:lastIndex sortBlock:aSortBlock |
|
511 |
] |
|
512 |
||
513 |
" |
|
514 |
#(9 8 7 6 5 4 3) asSortedCollection |
|
515 |
#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b] |
|
516 |
#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b] |
|
517 |
#($f $G $z $Y $o $H) asSortedCollection |
|
518 |
#($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase] |
|
519 |
" |
|
520 |
! ! |
|
521 |
||
522 |
!SortedCollection methodsFor:'private'! |
|
523 |
||
524 |
indexForInserting:anObject |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
525 |
"search the index at which to insert anObject. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
526 |
Can also be used to search for an existing element |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
527 |
by checking if the element at the returned index is the one we look for. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
528 |
Uses a binarySearch since we can depend on the elements being on sorted order. |
607 | 529 |
The returned index is a physical one, for accessing contentsArray." |
530 |
||
531 |
|low "{ Class: SmallInteger}" |
|
532 |
high "{ Class: SmallInteger}" |
|
533 |
middle "{ Class: SmallInteger}" |
|
534 |
element| |
|
535 |
||
536 |
" |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
537 |
we can of course use a binary search - since the elements are sorted |
607 | 538 |
" |
539 |
low := firstIndex. |
|
540 |
high := lastIndex. |
|
541 |
[low <= high] whileTrue:[ |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
542 |
middle := (low + high) // 2. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
543 |
element := contentsArray at:middle. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
544 |
(sortBlock value:element value:anObject) ifTrue:[ |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
545 |
"middleelement is smaller than object" |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
546 |
low := middle + 1 |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
547 |
] ifFalse:[ |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
548 |
high := middle - 1 |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
549 |
] |
607 | 550 |
]. |
551 |
^ low |
|
552 |
||
553 |
" |
|
554 |
#(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
|
555 |
#(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
|
556 |
" |
|
557 |
||
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
558 |
"Modified: 12.4.1996 / 13:22:03 / cg" |
607 | 559 |
! |
560 |
||
561 |
setSortBlock: aSortBlock |
|
562 |
"set the sortblock without resorting - private only" |
|
563 |
||
564 |
sortBlock := aSortBlock |
|
565 |
! ! |
|
566 |
||
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
567 |
!SortedCollection methodsFor:'queries'! |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
568 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
569 |
isSorted |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
570 |
^ true |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
571 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
572 |
"Created: 13.4.1996 / 12:36:29 / cg" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
573 |
! ! |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
574 |
|
607 | 575 |
!SortedCollection methodsFor:'searching'! |
576 |
||
577 |
after:anObject |
|
578 |
"return the element after the argument, anObject; or nil if there is none. |
|
579 |
If anObject is contained multiple times in the collection, return the |
|
580 |
the first element which is non-equal to anObject. |
|
581 |
If the receiver does not contain anObject, report an error" |
|
582 |
||
583 |
^ self after:anObject ifAbsent:[self errorValueNotFound:anObject] |
|
584 |
||
585 |
" |
|
586 |
#(7 3 9 10 99) asSortedCollection after:50 |
|
587 |
#(7 3 9 10 99) asSortedCollection after:1 |
|
588 |
#(7 3 9 10 99) asSortedCollection after:10 |
|
589 |
#(7 3 9 10 99) asSortedCollection after:7 |
|
590 |
#(7 3 9 10 99) asSortedCollection after:99 |
|
591 |
#(7 10 3 10 9 10 10 99) asSortedCollection after:9 |
|
592 |
#(7 10 3 10 9 10 10 99) asSortedCollection after:10 |
|
593 |
" |
|
594 |
! |
|
595 |
||
596 |
after:anObject ifAbsent:exceptionBlock |
|
597 |
"return the element after the argument, anObject; or nil if there is none. |
|
598 |
If anObject is contained multiple times in the collection, return the |
|
599 |
the first element which is non-equal to anObject. |
|
600 |
If the receiver does not contain anObject, return the result from evaluating |
|
601 |
exceptionBlock." |
|
602 |
||
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
603 |
|index "{ Class: SmallInteger }" |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
604 |
last "{ Class: SmallInteger }"| |
607 | 605 |
|
606 |
index := self indexForInserting:anObject. |
|
607 |
((index < firstIndex) |
|
608 |
or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value]. |
|
609 |
||
610 |
"skip multiple occurences of the same ..." |
|
611 |
||
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
612 |
last := lastIndex. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
613 |
[(index <= last) and:[(contentsArray at:index) = anObject]] whileTrue:[ |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
614 |
index := index + 1 |
607 | 615 |
]. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
616 |
(index > last) ifTrue:[^ nil]. |
607 | 617 |
^ contentsArray at:index |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
618 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
619 |
"Modified: 12.4.1996 / 13:20:33 / cg" |
607 | 620 |
! |
621 |
||
622 |
before:anObject |
|
623 |
"return the element before the argument, anObject; or nil if there is none. |
|
624 |
If the receiver does not contain anObject, report an error" |
|
625 |
||
626 |
^ self before:anObject ifAbsent:[self errorValueNotFound:anObject] |
|
627 |
||
628 |
" |
|
629 |
#(7 3 9 10 99) asSortedCollection before:50 |
|
630 |
#(7 3 9 10 99) asSortedCollection before:1 |
|
631 |
#(7 3 9 10 99) asSortedCollection before:1000 |
|
632 |
#(7 3 9 10 99) asSortedCollection before:10 |
|
633 |
#(7 3 9 10 99) asSortedCollection before:7 |
|
634 |
#(7 3 9 10 99) asSortedCollection before:99 |
|
635 |
#(7 10 3 10 9 10 10 99) asSortedCollection before:9 |
|
636 |
#(7 10 3 10 9 10 10 99) asSortedCollection before:10 |
|
637 |
" |
|
638 |
! |
|
639 |
||
640 |
before:anObject ifAbsent:exceptionBlock |
|
641 |
"return the element before the argument, anObject; or nil if there is none. |
|
642 |
If the receiver does not contain anObject, return the result from evaluating |
|
643 |
exceptionBlock." |
|
644 |
||
645 |
|index "{ Class: SmallInteger }"| |
|
646 |
||
647 |
index := self indexForInserting:anObject. |
|
648 |
((index <= firstIndex) |
|
649 |
or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value]. |
|
650 |
||
651 |
^ contentsArray at:index - 1 |
|
652 |
||
653 |
" |
|
654 |
#(7 3 9 10 99) asSortedCollection before:50 |
|
655 |
#(7 3 9 10 99) asSortedCollection before:1 |
|
656 |
#(7 3 9 10 99) asSortedCollection before:10 |
|
657 |
#(7 3 9 10 99) asSortedCollection before:7 |
|
658 |
#(7 3 9 10 99) asSortedCollection before:99 |
|
659 |
#(7 10 3 10 9 10 10 99) asSortedCollection before:9 |
|
660 |
#(7 10 3 10 9 10 10 99) asSortedCollection before:10 |
|
661 |
" |
|
662 |
! ! |
|
663 |
||
1 | 664 |
!SortedCollection methodsFor:'testing'! |
665 |
||
666 |
includes:anObject |
|
667 |
"return true, if the argument, anObject is in the collection. |
|
62 | 668 |
Redefined, since due to being sorted, the inclusion check can |
2 | 669 |
be done with log-n compares i.e. much faster." |
1 | 670 |
|
32 | 671 |
|index "{ Class: SmallInteger }"| |
1 | 672 |
|
77 | 673 |
index := self indexForInserting:anObject. |
32 | 674 |
((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ false]. |
675 |
^ (contentsArray at:index) = anObject |
|
2 | 676 |
|
77 | 677 |
" |
678 |
#(7 3 9 10 99) asSortedCollection includes:50 |
|
679 |
#(7 3 9 10 99) asSortedCollection includes:10 |
|
680 |
" |
|
1 | 681 |
! |
682 |
||
683 |
occurrencesOf:anObject |
|
684 |
"return how many times the argument, anObject is in the collection. |
|
62 | 685 |
Redefined, since due to being sorted, the range of checked objects |
2 | 686 |
can be limited i.e. it can be done much faster." |
1 | 687 |
|
688 |
|index "{ Class: SmallInteger }" |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
689 |
tally "{ Class: SmallInteger }" |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
690 |
last "{ Class: SmallInteger }" | |
1 | 691 |
|
77 | 692 |
index := self indexForInserting:anObject. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
693 |
last := lastIndex. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
694 |
((index < firstIndex) or:[index > last]) ifTrue:[^ 0]. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
695 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
696 |
"/ there may be multiple of them; count 'em |
32 | 697 |
|
1 | 698 |
tally := 0. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
699 |
[(index <= last) and:[(contentsArray at:index) = anObject]] whileTrue:[ |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
700 |
tally := tally + 1. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
701 |
index := index + 1 |
1 | 702 |
]. |
703 |
^ tally |
|
2 | 704 |
|
77 | 705 |
" |
706 |
#(7 3 9 10 99) asSortedCollection occurrencesOf:50 |
|
707 |
#(7 3 9 10 99) asSortedCollection occurrencesOf:10 |
|
708 |
#(7 10 3 10 9 10 10 99) asSortedCollection occurrencesOf:10 |
|
709 |
" |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
710 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
711 |
"Modified: 12.4.1996 / 18:48:40 / cg" |
77 | 712 |
! ! |
713 |
||
629 | 714 |
!SortedCollection class methodsFor:'documentation'! |
715 |
||
716 |
version |
|
1175 | 717 |
^ '$Header: /cvs/stx/stx/libbasic/SortedCollection.st,v 1.30 1996-04-13 13:29:39 cg Exp $' |
629 | 718 |
! ! |
607 | 719 |
SortedCollection initialize! |