author | Claus Gittinger <cg@exept.de> |
Wed, 23 Aug 2006 16:08:50 +0200 | |
changeset 9666 | cdcff7e1794f |
parent 9074 | 8358ce743c48 |
child 9916 | 5c76098e0377 |
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 |
||
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
13 |
"{ Package: 'stx:libbasic' }" |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
14 |
|
1 | 15 |
OrderedCollection subclass:#SortedCollection |
1155 | 16 |
instanceVariableNames:'sortBlock' |
17 |
classVariableNames:'DefaultSortBlock' |
|
18 |
poolDictionaries:'' |
|
19 |
category:'Collections-Sequenceable' |
|
1 | 20 |
! |
21 |
||
77 | 22 |
!SortedCollection class methodsFor:'documentation'! |
1 | 23 |
|
88 | 24 |
copyright |
25 |
" |
|
26 |
COPYRIGHT (c) 1993 by Claus Gittinger |
|
159 | 27 |
All Rights Reserved |
88 | 28 |
|
29 |
This software is furnished under a license and may be used |
|
30 |
only in accordance with the terms of that license and with the |
|
31 |
inclusion of the above copyright notice. This software may not |
|
32 |
be provided or otherwise made available to, or used by, any |
|
33 |
other person. No title to or ownership of the software is |
|
34 |
hereby transferred. |
|
35 |
" |
|
36 |
! |
|
37 |
||
77 | 38 |
documentation |
39 |
" |
|
40 |
I keep my elements sorted. The sort order is defined by a sortblock, |
|
8874 | 41 |
a two-argument block which, when given two elements of the collection, |
42 |
should return true if the element given as first arg has to come before the |
|
77 | 43 |
element given as second arg. |
44 |
||
1156 | 45 |
Equal elements may occur multiple times. |
46 |
||
47 |
SortedCollection uses quickSort to resort and a binary search when adding/removing |
|
8874 | 48 |
elements. |
1156 | 49 |
Because insertion/removal may require that remaining elements have to |
50 |
be shifted within the container, adding many individual elements may be done faster |
|
51 |
by creating a completely new collection from the unsorted elements. |
|
1167 | 52 |
(see examples) |
1156 | 53 |
|
77 | 54 |
Thus a sortBlock of [:a :b | a < b] defines ascending sort-order, |
55 |
while [:a :b | a > b] defines descening order. |
|
56 |
The default sortBlock for SortedCollections is the first one. |
|
1290 | 57 |
|
3251
87cac58a4e57
added VW compatibility warning
Claus Gittinger <cg@exept.de>
parents:
3250
diff
changeset
|
58 |
Compatibility Warning: |
8874 | 59 |
VW seems to use a default sortBlock which compares a<=b, |
60 |
while ST/X uses a<b. |
|
61 |
That means, that elements which are compared MUST understand #< in ST/X |
|
62 |
while the minumum protocol is #<= in VW. |
|
63 |
This may be changed in a future release of ST/X |
|
64 |
(it is not yet, to not confuse existing applications ... |
|
65 |
... be aware, that the sortBlock has an effect on a few algorithms |
|
66 |
found here; especially #indexForInserting is critical.) |
|
67 |
||
3251
87cac58a4e57
added VW compatibility warning
Claus Gittinger <cg@exept.de>
parents:
3250
diff
changeset
|
68 |
|
1290 | 69 |
[author:] |
8874 | 70 |
Claus Gittinger |
77 | 71 |
" |
1167 | 72 |
! |
73 |
||
74 |
examples |
|
75 |
" |
|
8874 | 76 |
when many elements are to be added, it may be better to add them |
1175 | 77 |
all en-bloeque instead of individually. |
1167 | 78 |
The reason is that for each individual #add:, the contents has to be |
1175 | 79 |
shifted, to create an empty slot for the new element. |
1167 | 80 |
|
81 |
timing example: |
|
82 |
||
9074 | 83 |
|o rnd| |
1167 | 84 |
|
9074 | 85 |
o := SortedCollection new. |
86 |
rnd := Random new. |
|
87 |
10000 timesRepeat:[ |
|
88 |
o add:rnd next. |
|
89 |
] |
|
1167 | 90 |
|
1175 | 91 |
takes 1365 ms on a P5 (admitted: this is a fast machine ;-) |
9074 | 92 |
(Times are a'changing: Just came around 2005: on my 1.5Ghz labtop, this now takes 260ms) |
93 |
||
1167 | 94 |
In contrast: |
95 |
||
9074 | 96 |
|o rnd| |
1167 | 97 |
|
9074 | 98 |
o := OrderedCollection new. |
99 |
rnd := Random new. |
|
100 |
10000 timesRepeat:[ |
|
101 |
o add:rnd next. |
|
102 |
]. |
|
103 |
o := o asSortedCollection |
|
1167 | 104 |
|
1175 | 105 |
takes 383 ms on the same machine. |
9074 | 106 |
(2005: on my 1.5Ghz labtop, this now takes 100ms) |
1173
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 |
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
|
109 |
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
|
110 |
the number of added items is more than some threshold number. |
3251
87cac58a4e57
added VW compatibility warning
Claus Gittinger <cg@exept.de>
parents:
3250
diff
changeset
|
111 |
However, the break-even point where bulk-adding is faster depends |
87cac58a4e57
added VW compatibility warning
Claus Gittinger <cg@exept.de>
parents:
3250
diff
changeset
|
112 |
on the machine ... (and ST/X version ;-). |
1167 | 113 |
" |
77 | 114 |
! ! |
1 | 115 |
|
116 |
!SortedCollection class methodsFor:'initialization'! |
|
117 |
||
118 |
initialize |
|
8180
7c346c8015f2
Only use #> for comparisons, since this is the base mechanism.
Stefan Vogel <sv@exept.de>
parents:
7554
diff
changeset
|
119 |
"setup the default sortBlock. |
7c346c8015f2
Only use #> for comparisons, since this is the base mechanism.
Stefan Vogel <sv@exept.de>
parents:
7554
diff
changeset
|
120 |
Use #>, since this is the base method in Magnitude." |
1155 | 121 |
|
122 |
"/ only do this once at early startup |
|
913 | 123 |
DefaultSortBlock isNil ifTrue:[ |
8874 | 124 |
DefaultSortBlock := [:a :b | a < b] |
913 | 125 |
] |
1 | 126 |
|
913 | 127 |
" |
128 |
SortedCollection initialize |
|
129 |
" |
|
1155 | 130 |
|
131 |
"Modified: 12.4.1996 / 12:29:27 / cg" |
|
1 | 132 |
! ! |
133 |
||
134 |
!SortedCollection class methodsFor:'instance creation'! |
|
135 |
||
2929 | 136 |
forStrings |
137 |
"this is supposed to return a sortedCollection, which sorts using |
|
138 |
the current locales collating sequence. For now, simply use a |
|
139 |
normal string compare. |
|
140 |
This will change" |
|
141 |
||
142 |
^ self new |
|
143 |
||
144 |
"Modified: 13.9.1997 / 10:18:58 / cg" |
|
145 |
"Created: 13.9.1997 / 10:41:54 / cg" |
|
146 |
! |
|
147 |
||
148 |
forStrings:size |
|
149 |
"this is supposed to return a sortedCollection, which sorts using |
|
150 |
the current locales collating sequence. For now, simply use a |
|
151 |
normal string compare. |
|
152 |
This will change" |
|
153 |
||
154 |
^ self new:size |
|
155 |
||
156 |
"Modified: 13.9.1997 / 10:18:58 / cg" |
|
157 |
! |
|
158 |
||
1 | 159 |
new |
2 | 160 |
"return a new sortedCollection, the sorting is done using |
1155 | 161 |
a compare for a < b, in ascending order" |
2 | 162 |
|
1 | 163 |
^ super new setSortBlock:DefaultSortBlock |
1155 | 164 |
|
165 |
"Modified: 12.4.1996 / 12:28:18 / cg" |
|
1 | 166 |
! |
167 |
||
168 |
new:size |
|
2 | 169 |
"return a new sortedCollection with preallocated size. |
1155 | 170 |
The sorting is done using a compare for a < b, in ascending order" |
2 | 171 |
|
1 | 172 |
^ (super new:size) setSortBlock:DefaultSortBlock |
1155 | 173 |
|
174 |
"Modified: 12.4.1996 / 12:28:22 / cg" |
|
1 | 175 |
! |
176 |
||
177 |
sortBlock:aBlock |
|
1155 | 178 |
"return a new sortedCollection, whe the sort order is defined |
8874 | 179 |
by aBlock. |
1155 | 180 |
This must be a two-argument block which returns true if its arg1 has to come before |
181 |
its arg2 in the collection." |
|
2 | 182 |
|
1 | 183 |
^ super new setSortBlock:aBlock |
1155 | 184 |
|
185 |
"default: |
|
186 |
|s| |
|
187 |
||
188 |
s := SortedCollection new. |
|
189 |
s add:15; add:99; add:3; add:-29; add:17; add:-6. |
|
1422 | 190 |
Transcript showCR:s |
1155 | 191 |
" |
192 |
||
193 |
"sorting by absolute values: |
|
194 |
|s| |
|
195 |
||
196 |
s := SortedCollection sortBlock:[:a :b | a abs < b abs]. |
|
197 |
s add:15; add:99; add:3; add:29; add:17; add:-6. |
|
1422 | 198 |
Transcript showCR:s |
1155 | 199 |
" |
200 |
||
201 |
"default again: |
|
202 |
|s| |
|
203 |
||
204 |
s := SortedCollection new. |
|
205 |
s add:'foo'; add:'Bar'; add:'baz'; add:'hello'; add:'world'; add:'Wow'. |
|
1422 | 206 |
Transcript showCR:s |
1155 | 207 |
" |
208 |
||
209 |
"sorting strings caseless: |
|
210 |
|s| |
|
211 |
||
212 |
s := SortedCollection sortBlock:[:a :b | a asLowercase < b asLowercase]. |
|
213 |
s add:'foo'; add:'Bar'; add:'baz'; add:'hello'; add:'world'; add:'Wow'. |
|
1422 | 214 |
Transcript showCR:s |
1155 | 215 |
" |
216 |
||
217 |
"Modified: 12.4.1996 / 12:26:28 / cg" |
|
329 | 218 |
! |
219 |
||
220 |
withAll:aCollection sortBlock:aBlock |
|
221 |
"initialize from aCollection and set the sort-block" |
|
222 |
||
2248 | 223 |
^ (self sortBlock:aBlock) addAll:aCollection; yourself |
329 | 224 |
|
225 |
" |
|
226 |
SortedCollection withAll:#(1 2 3 4 5 6 7 8 9 0) |
|
8874 | 227 |
sortBlock:[:a :b | a > b] |
1155 | 228 |
" |
229 |
||
230 |
"default: |
|
231 |
|s| |
|
232 |
||
233 |
s := SortedCollection withAll:#(15 99 3 29 17 -6). |
|
1422 | 234 |
Transcript showCR:s |
1155 | 235 |
" |
236 |
||
237 |
"sorting by absolute values: |
|
238 |
|s| |
|
239 |
||
240 |
s := SortedCollection withAll:#(15 99 3 29 17 -6) sortBlock:[:a :b | a abs < b abs]. |
|
1422 | 241 |
Transcript showCR:s |
329 | 242 |
" |
1155 | 243 |
|
244 |
"default again: |
|
245 |
|s| |
|
246 |
||
247 |
s := SortedCollection withAll:#('foo' 'Bar' 'baz' 'hello' 'world' 'Wow'). |
|
1422 | 248 |
Transcript showCR:s |
1155 | 249 |
" |
250 |
||
251 |
"sorting strings caseless: |
|
252 |
|s| |
|
253 |
||
254 |
s := SortedCollection withAll:#('foo' 'Bar' 'baz' 'hello' 'world' 'Wow') sortBlock:[:a :b | a asLowercase < b asLowercase]. |
|
1422 | 255 |
Transcript showCR:s |
1155 | 256 |
" |
257 |
||
258 |
"Modified: 12.4.1996 / 12:28:09 / cg" |
|
1 | 259 |
! ! |
260 |
||
7300 | 261 |
!SortedCollection class methodsFor:'Compatibility-Dolphin'! |
6411 | 262 |
|
263 |
sortBlock:aBlock withAll:aCollection |
|
264 |
^ self withAll:aCollection sortBlock:aBlock |
|
265 |
! ! |
|
266 |
||
9073 | 267 |
!SortedCollection methodsFor:'accessing'! |
268 |
||
269 |
median |
|
270 |
"Return the middle element, or as close as we can get." |
|
271 |
||
272 |
^ self at:(self size + 1 // 2) |
|
273 |
||
274 |
" |
|
275 |
#(10 35 20 45 30 5) asSortedCollection median |
|
276 |
#(10 35 20 45 30 5) median |
|
277 |
" |
|
278 |
! ! |
|
279 |
||
1 | 280 |
!SortedCollection methodsFor:'adding & removing'! |
281 |
||
607 | 282 |
add:anObject |
283 |
"add the argument, anObject at the proper place in the |
|
284 |
receiver. Returns the argument, anObject." |
|
2 | 285 |
|
607 | 286 |
|index| |
1 | 287 |
|
607 | 288 |
lastIndex < firstIndex "i.e. self size == 0" ifTrue:[ |
8874 | 289 |
"/ empty - add at the end |
290 |
index := lastIndex. |
|
291 |
(index == contentsArray size) ifTrue:[ |
|
292 |
self makeRoomAtLast. |
|
293 |
index := lastIndex. |
|
294 |
]. |
|
295 |
lastIndex := index := index + 1. |
|
607 | 296 |
] ifFalse:[ |
8874 | 297 |
index := self indexForInserting:anObject. |
298 |
index := self makeRoomAtIndex:index. |
|
607 | 299 |
]. |
3340 | 300 |
contentsArray basicAt:index put:anObject. |
607 | 301 |
^ anObject |
2 | 302 |
|
607 | 303 |
" |
8874 | 304 |
|c| #(7 3 9 10 99) asSortedCollection add:5; yourself |
305 |
#(7 3 9 10 99) asSortedCollection add:1; yourself |
|
306 |
#(7 3 9 10 99) asSortedCollection add:1000; yourself |
|
607 | 307 |
" |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
308 |
|
3340 | 309 |
"Modified: / 13.3.1998 / 16:21:52 / cg" |
1 | 310 |
! |
311 |
||
312 |
addAll:aCollection |
|
8874 | 313 |
"add all elements of the argument, aCollection to the receiver. |
5028
1f7e943ce46e
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
4596
diff
changeset
|
314 |
Returns the argument, aCollection (sigh)." |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
315 |
|
5816 | 316 |
|addedCollection| |
1 | 317 |
|
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
318 |
(aCollection isSortedCollection |
7554 | 319 |
and:[aCollection sortBlock == sortBlock]) ifTrue:[ |
8874 | 320 |
addedCollection := aCollection |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
321 |
] ifFalse:[ |
8874 | 322 |
addedCollection := Array withAll:aCollection. |
323 |
addedCollection sort:sortBlock. |
|
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
324 |
|
8874 | 325 |
"/ special case: I am empty - add them en-bloque. |
326 |
"/ (but only if the argument is not a sortedCollection, |
|
327 |
"/ because quicksort degenerates to a veeery slow operation then) |
|
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
328 |
|
8874 | 329 |
self size == 0 ifTrue:[ |
330 |
contentsArray := addedCollection. |
|
331 |
firstIndex := 1. |
|
332 |
lastIndex := addedCollection size. |
|
333 |
^ aCollection |
|
334 |
]. |
|
1 | 335 |
]. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
336 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
337 |
"/ |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
338 |
"/ do a mergeSort with the sortedContents |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
339 |
"/ |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
340 |
self mergeSorted:addedCollection. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
341 |
^ aCollection |
1 | 342 |
|
77 | 343 |
" |
8874 | 344 |
#(7 3 9 10 99) asSortedCollection addAll:#(77 0 1 16 5); yourself |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
345 |
|
5028
1f7e943ce46e
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
4596
diff
changeset
|
346 |
( #(7 3 9 10 99) asSortedCollection:[:a :b | a > b]) |
8874 | 347 |
addAll:#(77 0 1 16 5); yourself |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
348 |
|
8874 | 349 |
#(7 3 9 10 99) asSortedCollection |
350 |
addAll:( #(77 0 1 16 5) asSortedCollection:[:a :b | a > b]); yourself |
|
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
351 |
|
8874 | 352 |
(#(7 3 9 10 99) asSortedCollection:[:a :b | a > b]) |
353 |
addAll:( #(77 0 1 16 5) asSortedCollection:[:a :b | a < b]); yourself |
|
77 | 354 |
" |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
355 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
356 |
"Modified: 13.4.1996 / 12:42:15 / cg" |
1 | 357 |
! |
358 |
||
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
359 |
mergeSorted:aSortedCollection |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
360 |
"add all elements of the argument, aSortedCollection to the |
8874 | 361 |
receiver. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
362 |
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
|
363 |
|
8874 | 364 |
This should be used when a number of elements is to be added. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
365 |
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
|
366 |
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
|
367 |
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
|
368 |
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
|
369 |
|
8874 | 370 |
|newContentsArray |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
371 |
contentsArray2 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
372 |
destIndex "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
373 |
n1 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
374 |
n2 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
375 |
srcIndex1 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
376 |
srcIndex2 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
377 |
last1 "{ Class: SmallInteger }" |
8874 | 378 |
last2 "{ Class: SmallInteger }" |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
379 |
end1Reached end2Reached |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
380 |
el1 el2 | |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
381 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
382 |
n1 := self size. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
383 |
n2 := aSortedCollection size. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
384 |
|
5381
914e310a69be
Fix #mergeSorted if one of the collections is empty.
Stefan Vogel <sv@exept.de>
parents:
5359
diff
changeset
|
385 |
n1 == 0 ifTrue:[ |
8874 | 386 |
^ aSortedCollection. |
5381
914e310a69be
Fix #mergeSorted if one of the collections is empty.
Stefan Vogel <sv@exept.de>
parents:
5359
diff
changeset
|
387 |
]. |
914e310a69be
Fix #mergeSorted if one of the collections is empty.
Stefan Vogel <sv@exept.de>
parents:
5359
diff
changeset
|
388 |
n2 == 0 ifTrue:[ |
8874 | 389 |
^ self. |
5381
914e310a69be
Fix #mergeSorted if one of the collections is empty.
Stefan Vogel <sv@exept.de>
parents:
5359
diff
changeset
|
390 |
]. |
914e310a69be
Fix #mergeSorted if one of the collections is empty.
Stefan Vogel <sv@exept.de>
parents:
5359
diff
changeset
|
391 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
392 |
newContentsArray := Array new:(n1 + n2). |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
393 |
destIndex := 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
394 |
|
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
395 |
(aSortedCollection isSortedBy:sortBlock) ifTrue:[ |
8874 | 396 |
aSortedCollection isSortedCollection ifTrue:[ |
397 |
contentsArray2 := aSortedCollection contentsArray. |
|
398 |
srcIndex2 := aSortedCollection firstIndex. |
|
399 |
] ifFalse:[ |
|
400 |
contentsArray2 := aSortedCollection. |
|
401 |
srcIndex2 := 1. |
|
402 |
] |
|
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
403 |
] ifFalse:[ |
8874 | 404 |
contentsArray2 := aSortedCollection. |
405 |
srcIndex2 := 1. |
|
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
406 |
]. |
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
407 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
408 |
last2 := srcIndex2 + n2 -1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
409 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
410 |
srcIndex1 := firstIndex. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
411 |
last1 := srcIndex1 + n1 -1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
412 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
413 |
(srcIndex1 <= last1 and:[srcIndex2 <= last2]) ifTrue:[ |
8874 | 414 |
el1 := contentsArray at:srcIndex1. |
415 |
el2 := contentsArray2 at:srcIndex2. |
|
416 |
end1Reached := end2Reached := false. |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
417 |
|
8874 | 418 |
[end1Reached or:[end2Reached]] whileFalse:[ |
419 |
(sortBlock value:el1 value:el2) ifTrue:[ |
|
420 |
"/ el1 to come before el2 |
|
421 |
newContentsArray at:destIndex put:el1. destIndex := destIndex + 1. |
|
422 |
srcIndex1 := srcIndex1 + 1. |
|
423 |
srcIndex1 <= last1 ifTrue:[ |
|
424 |
el1 := contentsArray at:srcIndex1. |
|
425 |
] ifFalse:[ |
|
426 |
end1Reached := true |
|
427 |
] |
|
428 |
] ifFalse:[ |
|
429 |
"/ el2 to come before el1 |
|
430 |
newContentsArray at:destIndex put:el2. destIndex := destIndex + 1. |
|
431 |
srcIndex2 := srcIndex2 + 1. |
|
432 |
srcIndex2 <= last2 ifTrue:[ |
|
433 |
el2 := contentsArray2 at:srcIndex2. |
|
434 |
] ifFalse:[ |
|
435 |
end2Reached := true |
|
436 |
] |
|
437 |
] |
|
438 |
] |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
439 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
440 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
441 |
"/ 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
|
442 |
(srcIndex1 <= last1) ifTrue:[ |
8874 | 443 |
newContentsArray |
444 |
replaceFrom:destIndex |
|
445 |
to:(destIndex+(last1-srcIndex1)) |
|
446 |
with:contentsArray |
|
447 |
startingAt:srcIndex1 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
448 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
449 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
450 |
"/ 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
|
451 |
(srcIndex2 <= last2) ifTrue:[ |
8874 | 452 |
newContentsArray |
453 |
replaceFrom:destIndex |
|
454 |
to:(destIndex+(last2-srcIndex2)) |
|
455 |
with:contentsArray2 |
|
456 |
startingAt:srcIndex2 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
457 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
458 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
459 |
firstIndex := 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
460 |
lastIndex := n1 + n2. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
461 |
contentsArray := newContentsArray |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
462 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
463 |
" |
8874 | 464 |
#(7 3 9 10 99) asSortedCollection |
465 |
mergeSorted:#(77 0 1 16 5) asSortedCollection |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
466 |
|
8874 | 467 |
#(7 3 9 10 99) asSortedCollection |
468 |
mergeSorted:#(77 0 3 1 98 99 16 5) asSortedCollection |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
469 |
|
8874 | 470 |
#() asSortedCollection |
471 |
mergeSorted:#(77 0 3 1 98 99 16 5) asSortedCollection |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
472 |
|
8874 | 473 |
#(7 3 9 10 99) asSortedCollection |
474 |
mergeSorted:#() asSortedCollection |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
475 |
" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
476 |
|
3250
c4b444774f1c
oops - mergesort cannot simply copy remaining
Claus Gittinger <cg@exept.de>
parents:
2929
diff
changeset
|
477 |
"Modified: / 30.1.1998 / 01:49:42 / cg" |
607 | 478 |
! ! |
479 |
||
5560 | 480 |
!SortedCollection methodsFor:'blocked'! |
481 |
||
482 |
add:newObject after:oldObject |
|
483 |
"catch this - its not allowed for sortedCollections" |
|
484 |
||
485 |
self shouldNotImplement |
|
486 |
! |
|
487 |
||
488 |
add:newObject before:oldObject |
|
489 |
"catch this - its not allowed for sortedCollections" |
|
490 |
||
491 |
self shouldNotImplement |
|
492 |
! |
|
493 |
||
494 |
addFirst:anObject |
|
495 |
"catch this - its not allowed for sortedCollections" |
|
496 |
||
497 |
self shouldNotImplement |
|
498 |
! |
|
499 |
||
500 |
addLast:anObject |
|
501 |
"catch this - its not allowed for sortedCollections" |
|
502 |
||
503 |
self shouldNotImplement |
|
504 |
! ! |
|
505 |
||
607 | 506 |
!SortedCollection methodsFor:'converting'! |
507 |
||
508 |
asSortedCollection |
|
509 |
"return the receiver as a sorted collection" |
|
510 |
||
511 |
"could be an instance of a subclass..." |
|
512 |
self class == SortedCollection ifTrue:[ |
|
8874 | 513 |
sortBlock == DefaultSortBlock ifTrue:[ |
514 |
^ self |
|
515 |
] |
|
1 | 516 |
]. |
607 | 517 |
^ super asSortedCollection |
5029
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
518 |
! |
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
519 |
|
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
520 |
asSortedCollection:aSortBlock |
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
521 |
"return the receiver as a sorted collection, using aSortBlock. |
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
522 |
Return the receiver, if its a sortedCollection and the sortBlock |
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
523 |
is the same as the argument-sortBlock" |
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
524 |
|
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
525 |
"could be an instance of a subclass..." |
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
526 |
self class == SortedCollection ifTrue:[ |
8874 | 527 |
"/ if the sortBlock is the same, return the receiver |
528 |
aSortBlock == sortBlock ifTrue:[ |
|
529 |
^ self |
|
530 |
]. |
|
5029
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
531 |
]. |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
532 |
^ super asSortedCollection:aSortBlock |
1 | 533 |
! ! |
534 |
||
95 | 535 |
!SortedCollection methodsFor:'copying'! |
536 |
||
607 | 537 |
copyEmpty:size |
538 |
"return a copy of the receiver with no elements, but |
|
539 |
the same size. This method has been be redefined to |
|
540 |
preserve the sortBlock." |
|
541 |
||
542 |
^ (self species new:size) sortBlock:sortBlock |
|
543 |
! |
|
544 |
||
159 | 545 |
postCopyFrom:anOriginal |
546 |
"sent after a copy or when a new collection species has been created. |
|
95 | 547 |
The new collection should have the same sortBlock as the original." |
548 |
||
159 | 549 |
sortBlock := anOriginal sortBlock |
95 | 550 |
|
551 |
" |
|
552 |
#(4 7 1 99 -1 17) asSortedCollection inspect |
|
159 | 553 |
#(4 7 1 99 -1 17) asSortedCollection copy inspect |
95 | 554 |
(#(4 7 1 99 -1 17) asSortedCollection sortBlock:[:a :b | a > b]) inspect |
159 | 555 |
(#(4 7 1 99 -1 17) asSortedCollection sortBlock:[:a :b | a > b]) copy inspect |
556 |
(#(4 7 1 99 -1 17) asSortedCollection select:[:e| e even]) inspect |
|
95 | 557 |
" |
558 |
! ! |
|
559 |
||
216 | 560 |
!SortedCollection methodsFor:'enumerating'! |
184 | 561 |
|
562 |
collect:aBlock |
|
563 |
"evaluate the argument, aBlock for every element in the collection |
|
564 |
and return a collection of the results. Redefined to return an OrderedCollection; |
|
565 |
see X3J20 spec. (SortedCollection>>collect: should return an OrderedCollection)" |
|
566 |
||
567 |
|newCollection |
|
568 |
start "{ Class:SmallInteger }" |
|
569 |
stop "{ Class:SmallInteger }" | |
|
570 |
||
571 |
newCollection := OrderedCollection new:(self size). |
|
572 |
stop := lastIndex. |
|
573 |
start := firstIndex. |
|
574 |
start to:stop do:[:index | |
|
575 |
newCollection add:(aBlock value:(contentsArray at:index)). |
|
576 |
]. |
|
577 |
^ newCollection |
|
578 |
! ! |
|
579 |
||
607 | 580 |
!SortedCollection methodsFor:'instance protocol'! |
581 |
||
5668
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
582 |
sort:aSortBlock |
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
583 |
"redefined from superclass to change the sortBlock" |
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
584 |
|
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
585 |
sortBlock ~~ aSortBlock ifTrue:[ |
8874 | 586 |
self sortBlock:aSortBlock. |
5668
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
587 |
]. |
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
588 |
|
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
589 |
! |
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
590 |
|
607 | 591 |
sortBlock |
592 |
"return the block used for sorting" |
|
593 |
||
594 |
^ sortBlock |
|
595 |
! |
|
596 |
||
597 |
sortBlock:aSortBlock |
|
8874 | 598 |
"change the sort criteria for a sorted collection, resort the elements of |
607 | 599 |
the collection, and return the receiver. The argument, aSortBlock must |
600 |
be a two-argument block which returns true if its arg1 has to come before |
|
601 |
its arg2 in the collection." |
|
602 |
||
603 |
sortBlock := aSortBlock. |
|
604 |
lastIndex > firstIndex ifTrue:[ |
|
605 |
contentsArray quickSortFrom:firstIndex to:lastIndex sortBlock:aSortBlock |
|
606 |
] |
|
607 |
||
608 |
" |
|
609 |
#(9 8 7 6 5 4 3) asSortedCollection |
|
610 |
#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b] |
|
611 |
#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b] |
|
612 |
#($f $G $z $Y $o $H) asSortedCollection |
|
613 |
#($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase] |
|
614 |
" |
|
615 |
! ! |
|
616 |
||
617 |
!SortedCollection methodsFor:'private'! |
|
618 |
||
619 |
indexForInserting:anObject |
|
8874 | 620 |
"search the index at which to insert anObject. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
621 |
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
|
622 |
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
|
623 |
Uses a binarySearch since we can depend on the elements being on sorted order. |
607 | 624 |
The returned index is a physical one, for accessing contentsArray." |
625 |
||
626 |
|low "{ Class: SmallInteger}" |
|
627 |
high "{ Class: SmallInteger}" |
|
628 |
middle "{ Class: SmallInteger}" |
|
629 |
element| |
|
630 |
||
631 |
" |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
632 |
we can of course use a binary search - since the elements are sorted |
607 | 633 |
" |
634 |
low := firstIndex. |
|
635 |
high := lastIndex. |
|
9074 | 636 |
[low > high] whileFalse:[ |
637 |
middle := (low + high) // 2. |
|
638 |
element := contentsArray at:middle. |
|
639 |
(sortBlock value:element value:anObject) ifTrue:[ |
|
640 |
"middleelement is smaller than object" |
|
641 |
low := middle + 1 |
|
642 |
] ifFalse:[ |
|
643 |
high := middle - 1 |
|
644 |
] |
|
607 | 645 |
]. |
646 |
^ low |
|
647 |
||
648 |
" |
|
8874 | 649 |
#(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
650 |
#(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
|
607 | 651 |
" |
652 |
||
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
653 |
"Modified: 12.4.1996 / 13:22:03 / cg" |
607 | 654 |
! |
655 |
||
656 |
setSortBlock: aSortBlock |
|
657 |
"set the sortblock without resorting - private only" |
|
658 |
||
659 |
sortBlock := aSortBlock |
|
660 |
! ! |
|
661 |
||
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
662 |
!SortedCollection methodsFor:'queries'! |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
663 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
664 |
isSorted |
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
665 |
"return true. if my elements are sorted" |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
666 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
667 |
^ true |
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
668 |
! |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
669 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
670 |
isSortedBy:aBlock |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
671 |
"return true, if my elements are sorted (already) by the given criterion (sortBlock)." |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
672 |
|
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
673 |
aBlock == sortBlock ifTrue:[^ true]. |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
674 |
^ super isSortedBy:aBlock |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
675 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
676 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
677 |
! |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
678 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
679 |
isSortedCollection |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
680 |
"return true. if I am a sorted collection" |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
681 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
682 |
^ true |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
683 |
! ! |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
684 |
|
607 | 685 |
!SortedCollection methodsFor:'searching'! |
686 |
||
687 |
after:anObject ifAbsent:exceptionBlock |
|
688 |
"return the element after the argument, anObject; or nil if there is none. |
|
689 |
If anObject is contained multiple times in the collection, return the |
|
690 |
the first element which is non-equal to anObject. |
|
691 |
If the receiver does not contain anObject, return the result from evaluating |
|
692 |
exceptionBlock." |
|
693 |
||
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
694 |
|index "{ Class: SmallInteger }" |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
695 |
last "{ Class: SmallInteger }"| |
607 | 696 |
|
697 |
index := self indexForInserting:anObject. |
|
8874 | 698 |
((index < firstIndex) |
607 | 699 |
or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value]. |
700 |
||
8874 | 701 |
"skip multiple occurrences of the same ..." |
607 | 702 |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
703 |
last := lastIndex. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
704 |
[(index <= last) and:[(contentsArray at:index) = anObject]] whileTrue:[ |
8874 | 705 |
index := index + 1 |
607 | 706 |
]. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
707 |
(index > last) ifTrue:[^ nil]. |
607 | 708 |
^ contentsArray at:index |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
709 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
710 |
"Modified: 12.4.1996 / 13:20:33 / cg" |
607 | 711 |
! |
712 |
||
713 |
before:anObject ifAbsent:exceptionBlock |
|
714 |
"return the element before the argument, anObject; or nil if there is none. |
|
715 |
If the receiver does not contain anObject, return the result from evaluating |
|
716 |
exceptionBlock." |
|
717 |
||
718 |
|index "{ Class: SmallInteger }"| |
|
719 |
||
720 |
index := self indexForInserting:anObject. |
|
8874 | 721 |
((index <= firstIndex) |
607 | 722 |
or:[(contentsArray at:index) ~= anObject]) ifTrue:[^ exceptionBlock value]. |
723 |
||
724 |
^ contentsArray at:index - 1 |
|
725 |
||
726 |
" |
|
727 |
#(7 3 9 10 99) asSortedCollection before:50 |
|
8874 | 728 |
#(7 3 9 10 99) asSortedCollection before:1 |
729 |
#(7 3 9 10 99) asSortedCollection before:10 |
|
730 |
#(7 3 9 10 99) asSortedCollection before:7 |
|
731 |
#(7 3 9 10 99) asSortedCollection before:99 |
|
732 |
#(7 10 3 10 9 10 10 99) asSortedCollection before:9 |
|
733 |
#(7 10 3 10 9 10 10 99) asSortedCollection before:10 |
|
607 | 734 |
" |
4596 | 735 |
! |
736 |
||
737 |
indexOf:anElement |
|
8874 | 738 |
"Return the index of anElement within the receiver. |
4596 | 739 |
If the receiver does not contain anElement, return 0." |
740 |
||
741 |
^ self indexOf:anElement ifAbsent:0 |
|
742 |
! |
|
743 |
||
744 |
indexOf:anElement ifAbsent:exceptionBlock |
|
8874 | 745 |
"Return the index of anElement within the receiver. |
746 |
If the receiver does not contain anElement, |
|
4596 | 747 |
return the result of evaluating the argument, exceptionBlock." |
748 |
||
8874 | 749 |
|insertionIndex index "{ Class: SmallInteger }" |
4596 | 750 |
obj| |
751 |
||
752 |
firstIndex > lastIndex ifTrue:[ |
|
8874 | 753 |
"/ empty |
754 |
^ exceptionBlock value |
|
4596 | 755 |
]. |
756 |
||
757 |
"/ if I am small, the inherited linear search is faster ... |
|
758 |
(lastIndex - firstIndex) < 20 ifTrue:[ |
|
8874 | 759 |
^ super indexOf:anElement ifAbsent:exceptionBlock |
4596 | 760 |
]. |
761 |
||
762 |
insertionIndex := self indexForInserting:anElement. |
|
763 |
insertionIndex > lastIndex ifTrue:[ |
|
8874 | 764 |
insertionIndex := lastIndex |
4596 | 765 |
] ifFalse:[ |
8874 | 766 |
insertionIndex < firstIndex ifTrue:[ |
767 |
insertionIndex := firstIndex |
|
768 |
] |
|
4596 | 769 |
]. |
770 |
||
771 |
index := insertionIndex. |
|
772 |
[index >= firstIndex |
|
773 |
and:[obj := contentsArray basicAt:index. |
|
8874 | 774 |
anElement = obj ifTrue: [^ index - firstIndex + 1]. |
775 |
[sortBlock value:anElement value:obj]]] |
|
776 |
whileTrue: [index := index - 1]. |
|
4596 | 777 |
|
778 |
index := insertionIndex. |
|
779 |
[index <= lastIndex |
|
780 |
and: [obj := contentsArray basicAt: index. |
|
8874 | 781 |
anElement = obj ifTrue: [^ index - firstIndex + 1]. |
782 |
[sortBlock value:obj value:anElement]]] |
|
783 |
whileTrue: [index := index + 1]. |
|
4596 | 784 |
|
785 |
^exceptionBlock value |
|
786 |
||
787 |
" |
|
788 |
#('aa' 'bb' 'cc' 'dd') asSortedCollection indexOf:'bb' |
|
8874 | 789 |
#('aa' 'bb' 'cc' 'dd' 'aa' 'bb' 'cc' 'dd') asSortedCollection indexOf:'bb' |
4596 | 790 |
|
791 |
|allSyms indices| |
|
8874 | 792 |
allSyms := Symbol allInstances asSortedCollection. |
4596 | 793 |
Time millisecondsToRun:[ |
8874 | 794 |
indices := allSyms collect:[:el | allSyms indexOf:el]. |
4596 | 795 |
]. |
796 |
indices = (1 to:allSyms size) |
|
797 |
" |
|
607 | 798 |
! ! |
799 |
||
1 | 800 |
!SortedCollection methodsFor:'testing'! |
801 |
||
802 |
includes:anObject |
|
803 |
"return true, if the argument, anObject is in the collection. |
|
62 | 804 |
Redefined, since due to being sorted, the inclusion check can |
2 | 805 |
be done with log-n compares i.e. much faster." |
1 | 806 |
|
32 | 807 |
|index "{ Class: SmallInteger }"| |
1 | 808 |
|
77 | 809 |
index := self indexForInserting:anObject. |
32 | 810 |
((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ false]. |
811 |
^ (contentsArray at:index) = anObject |
|
2 | 812 |
|
77 | 813 |
" |
814 |
#(7 3 9 10 99) asSortedCollection includes:50 |
|
815 |
#(7 3 9 10 99) asSortedCollection includes:10 |
|
816 |
" |
|
1 | 817 |
! |
818 |
||
819 |
occurrencesOf:anObject |
|
820 |
"return how many times the argument, anObject is in the collection. |
|
62 | 821 |
Redefined, since due to being sorted, the range of checked objects |
5048 | 822 |
can be limited i.e. it can be done much faster. |
823 |
Uses #= (i.e. equality) compare." |
|
1 | 824 |
|
825 |
|index "{ Class: SmallInteger }" |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
826 |
tally "{ Class: SmallInteger }" |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
827 |
last "{ Class: SmallInteger }" | |
1 | 828 |
|
77 | 829 |
index := self indexForInserting:anObject. |
8874 | 830 |
last := lastIndex. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
831 |
((index < firstIndex) or:[index > last]) ifTrue:[^ 0]. |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
832 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
833 |
"/ there may be multiple of them; count 'em |
32 | 834 |
|
1 | 835 |
tally := 0. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
836 |
[(index <= last) and:[(contentsArray at:index) = anObject]] whileTrue:[ |
8874 | 837 |
tally := tally + 1. |
838 |
index := index + 1 |
|
1 | 839 |
]. |
840 |
^ tally |
|
2 | 841 |
|
77 | 842 |
" |
843 |
#(7 3 9 10 99) asSortedCollection occurrencesOf:50 |
|
844 |
#(7 3 9 10 99) asSortedCollection occurrencesOf:10 |
|
845 |
#(7 10 3 10 9 10 10 99) asSortedCollection occurrencesOf:10 |
|
846 |
" |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
847 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
848 |
"Modified: 12.4.1996 / 18:48:40 / cg" |
77 | 849 |
! ! |
850 |
||
629 | 851 |
!SortedCollection class methodsFor:'documentation'! |
852 |
||
853 |
version |
|
9074 | 854 |
^ '$Header: /cvs/stx/stx/libbasic/SortedCollection.st,v 1.58 2006-01-24 11:20:46 cg Exp $' |
629 | 855 |
! ! |
7300 | 856 |
|
607 | 857 |
SortedCollection initialize! |