author | Stefan Vogel <sv@exept.de> |
Fri, 27 Oct 2017 16:14:37 +0200 | |
branch | expecco_2_11_1_branch |
changeset 22329 | 20662662693b |
parent 20634 | 41a01dac11d3 |
child 20727 | fb8c5591428b |
child 21438 | d8471a555b10 |
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 |
" |
|
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
12 |
"{ Package: 'stx:libbasic' }" |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
13 |
|
18508 | 14 |
"{ NameSpace: Smalltalk }" |
15 |
||
1 | 16 |
OrderedCollection subclass:#SortedCollection |
1155 | 17 |
instanceVariableNames:'sortBlock' |
18 |
classVariableNames:'DefaultSortBlock' |
|
19 |
poolDictionaries:'' |
|
20 |
category:'Collections-Sequenceable' |
|
1 | 21 |
! |
22 |
||
77 | 23 |
!SortedCollection class methodsFor:'documentation'! |
1 | 24 |
|
88 | 25 |
copyright |
26 |
" |
|
27 |
COPYRIGHT (c) 1993 by Claus Gittinger |
|
159 | 28 |
All Rights Reserved |
88 | 29 |
|
30 |
This software is furnished under a license and may be used |
|
31 |
only in accordance with the terms of that license and with the |
|
32 |
inclusion of the above copyright notice. This software may not |
|
33 |
be provided or otherwise made available to, or used by, any |
|
34 |
other person. No title to or ownership of the software is |
|
35 |
hereby transferred. |
|
36 |
" |
|
37 |
! |
|
38 |
||
77 | 39 |
documentation |
40 |
" |
|
41 |
I keep my elements sorted. The sort order is defined by a sortblock, |
|
8874 | 42 |
a two-argument block which, when given two elements of the collection, |
43 |
should return true if the element given as first arg has to come before the |
|
77 | 44 |
element given as second arg. |
45 |
||
1156 | 46 |
Equal elements may occur multiple times. |
47 |
||
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
48 |
SortedCollection uses quickSort to resort and a binary search when adding/removing elements. |
1156 | 49 |
Because insertion/removal may require that remaining elements have to |
20634 | 50 |
be shifted within the container, adding many individual elements will be faster above a |
51 |
particular number of added elements by creating a completely new collection from the |
|
52 |
unsorted elements. |
|
1167 | 53 |
(see examples) |
1156 | 54 |
|
20634 | 55 |
A sortblock, given arguments a,b should return true, if a is to be shown before b. |
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
56 |
A sortBlock of [:a :b | a < b] defines ascending sort-order, |
77 | 57 |
while [:a :b | a > b] defines descening order. |
20634 | 58 |
The default sortBlock for SortedCollections is the first one (i.e. sorting in ascending order). |
1290 | 59 |
|
3251
87cac58a4e57
added VW compatibility warning
Claus Gittinger <cg@exept.de>
parents:
3250
diff
changeset
|
60 |
Compatibility Warning: |
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
61 |
VW seems to use a default sortBlock which compares a<=b, wheras ST/X uses a<b. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
62 |
That means, that elements which are compared MUST understand #< in ST/X |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
63 |
while the minumum protocol is #<= in VW. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
64 |
This may be changed in a future release of ST/X |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
65 |
(it is not yet, to not confuse existing applications ... |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
66 |
... be aware, that the sortBlock has an effect on a few algorithms |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
67 |
found here; especially #indexForInserting is critical.) |
8874 | 68 |
|
14304 | 69 |
[caveat:] |
70 |
a balanced tree may be a better choice, as inserting may be slow when |
|
20634 | 71 |
elements have to be shifted. See the performance measuremens in AATree. |
3251
87cac58a4e57
added VW compatibility warning
Claus Gittinger <cg@exept.de>
parents:
3250
diff
changeset
|
72 |
|
1290 | 73 |
[author:] |
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
74 |
Claus Gittinger |
77 | 75 |
" |
1167 | 76 |
! |
77 |
||
78 |
examples |
|
79 |
" |
|
8874 | 80 |
when many elements are to be added, it may be better to add them |
1175 | 81 |
all en-bloeque instead of individually. |
1167 | 82 |
The reason is that for each individual #add:, the contents has to be |
1175 | 83 |
shifted, to create an empty slot for the new element. |
1167 | 84 |
|
85 |
timing example: |
|
86 |
||
9074 | 87 |
|o rnd| |
1167 | 88 |
|
9074 | 89 |
o := SortedCollection new. |
90 |
rnd := Random new. |
|
91 |
10000 timesRepeat:[ |
|
92 |
o add:rnd next. |
|
93 |
] |
|
1167 | 94 |
|
1175 | 95 |
takes 1365 ms on a P5 (admitted: this is a fast machine ;-) |
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
96 |
Times are a'changing: |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
97 |
Just came around 2005: on my 1.5Ghz laptop, this now takes 260ms... |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
98 |
an another comment 2008: on a 1.8Ghz laptop, it takes now 105ms... |
9074 | 99 |
|
1167 | 100 |
In contrast: |
101 |
||
9074 | 102 |
|o rnd| |
1167 | 103 |
|
9074 | 104 |
o := OrderedCollection new. |
105 |
rnd := Random new. |
|
106 |
10000 timesRepeat:[ |
|
107 |
o add:rnd next. |
|
108 |
]. |
|
109 |
o := o asSortedCollection |
|
1167 | 110 |
|
1175 | 111 |
takes 383 ms on the same machine. |
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
112 |
2005: on my 1.5Ghz laptop, this now takes 100ms |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
113 |
2008: on a 1.8Ghz laptop, this now takes 47ms |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
114 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
115 |
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
|
116 |
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
|
117 |
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
|
118 |
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
|
119 |
on the machine ... (and ST/X version ;-). |
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
120 |
|
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
121 |
|
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
122 |
adding elements in order: |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
123 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
124 |
|c| |
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
125 |
Time millisecondsToRun:[ |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
126 |
10 timesRepeat:[ |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
127 |
|c| |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
128 |
c := SortedCollection new. |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
129 |
(1 to:100000) do:[:e | c add:e]. |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
130 |
] |
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
131 |
]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
132 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
133 |
(5.4.1: 2031 2187) |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
134 |
(5.4.3: 484 516) |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
135 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
136 |
|c| |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
137 |
c := SortedCollection new. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
138 |
(1 to:100000) do:[:e | c add:e]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
139 |
self assert:(c asBag = (1 to:100000) asBag). |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
140 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
141 |
adding elements in reverse order: |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
142 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
143 |
Time millisecondsToRun:[ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
144 |
10 timesRepeat:[ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
145 |
|c| |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
146 |
c := SortedCollection new. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
147 |
(1 to:100000) reverseDo:[:e | c add:e]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
148 |
] |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
149 |
]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
150 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
151 |
(5.4.1: 201969) |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
152 |
(5.4.3: 1609 1766) |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
153 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
154 |
|c| |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
155 |
c := SortedCollection new. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
156 |
(1 to:100000) reverseDo:[:e | c add:e]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
157 |
self assert:(c asBag = (1 to:100000) asBag). |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
158 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
159 |
adding elements in random order: |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
160 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
161 |
|toAdd| |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
162 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
163 |
toAdd := (1 to:100000) asOrderedCollection randomShuffle. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
164 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
165 |
Time millisecondsToRun:[ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
166 |
10 timesRepeat:[ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
167 |
|c| |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
168 |
c := SortedCollection new. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
169 |
toAdd do:[:e | c add:e]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
170 |
] |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
171 |
]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
172 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
173 |
(5.4.1: 108484) |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
174 |
(5.4.3: 75734) |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
175 |
|
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
176 |
|c| |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
177 |
c := SortedCollection new. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
178 |
(1 to:100000) asOrderedCollection randomShuffle do:[:e | c add:e]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
179 |
self assert:(c asBag = (1 to:100000) asBag). |
1167 | 180 |
" |
77 | 181 |
! ! |
1 | 182 |
|
183 |
!SortedCollection class methodsFor:'initialization'! |
|
184 |
||
185 |
initialize |
|
8180
7c346c8015f2
Only use #> for comparisons, since this is the base mechanism.
Stefan Vogel <sv@exept.de>
parents:
7554
diff
changeset
|
186 |
"setup the default sortBlock. |
12034 | 187 |
Use #<, since this is the base method in Magnitude." |
1155 | 188 |
|
189 |
"/ only do this once at early startup |
|
913 | 190 |
DefaultSortBlock isNil ifTrue:[ |
12034 | 191 |
DefaultSortBlock := [:a :b | a < b] |
913 | 192 |
] |
1 | 193 |
|
913 | 194 |
" |
195 |
SortedCollection initialize |
|
196 |
" |
|
1155 | 197 |
|
198 |
"Modified: 12.4.1996 / 12:29:27 / cg" |
|
1 | 199 |
! ! |
200 |
||
201 |
!SortedCollection class methodsFor:'instance creation'! |
|
202 |
||
2929 | 203 |
forStrings |
204 |
"this is supposed to return a sortedCollection, which sorts using |
|
205 |
the current locales collating sequence. For now, simply use a |
|
206 |
normal string compare. |
|
207 |
This will change" |
|
208 |
||
209 |
^ self new |
|
210 |
||
211 |
"Modified: 13.9.1997 / 10:18:58 / cg" |
|
212 |
"Created: 13.9.1997 / 10:41:54 / cg" |
|
213 |
! |
|
214 |
||
215 |
forStrings:size |
|
216 |
"this is supposed to return a sortedCollection, which sorts using |
|
217 |
the current locales collating sequence. For now, simply use a |
|
218 |
normal string compare. |
|
219 |
This will change" |
|
220 |
||
221 |
^ self new:size |
|
222 |
||
223 |
"Modified: 13.9.1997 / 10:18:58 / cg" |
|
224 |
! |
|
225 |
||
1 | 226 |
new |
2 | 227 |
"return a new sortedCollection, the sorting is done using |
1155 | 228 |
a compare for a < b, in ascending order" |
2 | 229 |
|
1 | 230 |
^ super new setSortBlock:DefaultSortBlock |
1155 | 231 |
|
232 |
"Modified: 12.4.1996 / 12:28:18 / cg" |
|
1 | 233 |
! |
234 |
||
235 |
new:size |
|
2 | 236 |
"return a new sortedCollection with preallocated size. |
1155 | 237 |
The sorting is done using a compare for a < b, in ascending order" |
2 | 238 |
|
1 | 239 |
^ (super new:size) setSortBlock:DefaultSortBlock |
1155 | 240 |
|
241 |
"Modified: 12.4.1996 / 12:28:22 / cg" |
|
1 | 242 |
! |
243 |
||
244 |
sortBlock:aBlock |
|
1155 | 245 |
"return a new sortedCollection, whe the sort order is defined |
8874 | 246 |
by aBlock. |
1155 | 247 |
This must be a two-argument block which returns true if its arg1 has to come before |
248 |
its arg2 in the collection." |
|
2 | 249 |
|
1 | 250 |
^ super new setSortBlock:aBlock |
1155 | 251 |
|
252 |
"default: |
|
253 |
|s| |
|
254 |
||
255 |
s := SortedCollection new. |
|
256 |
s add:15; add:99; add:3; add:-29; add:17; add:-6. |
|
1422 | 257 |
Transcript showCR:s |
1155 | 258 |
" |
259 |
||
260 |
"sorting by absolute values: |
|
261 |
|s| |
|
262 |
||
263 |
s := SortedCollection sortBlock:[:a :b | a abs < b abs]. |
|
264 |
s add:15; add:99; add:3; add:29; add:17; add:-6. |
|
1422 | 265 |
Transcript showCR:s |
1155 | 266 |
" |
267 |
||
268 |
"default again: |
|
269 |
|s| |
|
270 |
||
271 |
s := SortedCollection new. |
|
272 |
s add:'foo'; add:'Bar'; add:'baz'; add:'hello'; add:'world'; add:'Wow'. |
|
1422 | 273 |
Transcript showCR:s |
1155 | 274 |
" |
275 |
||
276 |
"sorting strings caseless: |
|
277 |
|s| |
|
278 |
||
279 |
s := SortedCollection sortBlock:[:a :b | a asLowercase < b asLowercase]. |
|
280 |
s add:'foo'; add:'Bar'; add:'baz'; add:'hello'; add:'world'; add:'Wow'. |
|
1422 | 281 |
Transcript showCR:s |
1155 | 282 |
" |
283 |
||
284 |
"Modified: 12.4.1996 / 12:26:28 / cg" |
|
329 | 285 |
! |
286 |
||
287 |
withAll:aCollection sortBlock:aBlock |
|
288 |
"initialize from aCollection and set the sort-block" |
|
289 |
||
2248 | 290 |
^ (self sortBlock:aBlock) addAll:aCollection; yourself |
329 | 291 |
|
292 |
" |
|
293 |
SortedCollection withAll:#(1 2 3 4 5 6 7 8 9 0) |
|
8874 | 294 |
sortBlock:[:a :b | a > b] |
1155 | 295 |
" |
296 |
||
297 |
"default: |
|
298 |
|s| |
|
299 |
||
300 |
s := SortedCollection withAll:#(15 99 3 29 17 -6). |
|
1422 | 301 |
Transcript showCR:s |
1155 | 302 |
" |
303 |
||
304 |
"sorting by absolute values: |
|
305 |
|s| |
|
306 |
||
307 |
s := SortedCollection withAll:#(15 99 3 29 17 -6) sortBlock:[:a :b | a abs < b abs]. |
|
1422 | 308 |
Transcript showCR:s |
329 | 309 |
" |
1155 | 310 |
|
311 |
"default again: |
|
312 |
|s| |
|
313 |
||
314 |
s := SortedCollection withAll:#('foo' 'Bar' 'baz' 'hello' 'world' 'Wow'). |
|
1422 | 315 |
Transcript showCR:s |
1155 | 316 |
" |
317 |
||
318 |
"sorting strings caseless: |
|
319 |
|s| |
|
320 |
||
321 |
s := SortedCollection withAll:#('foo' 'Bar' 'baz' 'hello' 'world' 'Wow') sortBlock:[:a :b | a asLowercase < b asLowercase]. |
|
1422 | 322 |
Transcript showCR:s |
1155 | 323 |
" |
324 |
||
325 |
"Modified: 12.4.1996 / 12:28:09 / cg" |
|
1 | 326 |
! ! |
327 |
||
7300 | 328 |
!SortedCollection class methodsFor:'Compatibility-Dolphin'! |
6411 | 329 |
|
330 |
sortBlock:aBlock withAll:aCollection |
|
331 |
^ self withAll:aCollection sortBlock:aBlock |
|
332 |
! ! |
|
333 |
||
1 | 334 |
!SortedCollection methodsFor:'adding & removing'! |
335 |
||
607 | 336 |
add:anObject |
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
337 |
"add the argument, anObject at the proper place in the receiver. |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
338 |
Returns the argument, anObject (sigh)." |
2 | 339 |
|
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
340 |
|index lastElement| |
1 | 341 |
|
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
342 |
"/ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
343 |
"/ cg: the original code was simply: |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
344 |
"/ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
345 |
"/ index := self indexForInserting:anObject. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
346 |
"/ index := self makeRoomAtIndex:index. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
347 |
"/ contentsArray basicAt:index put:anObject. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
348 |
"/ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
349 |
"/ which was nice and simple to understand. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
350 |
"/ However, the code below is 5 times faster, if elements are added in an already ordered fashion, |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
351 |
"/ which often happens. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
352 |
"/ so we allow the code to be a bit more complicated... |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
353 |
|
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
354 |
(lastIndex < firstIndex "i.e. self size == 0" |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
355 |
or:[ |
18508 | 356 |
lastElement := contentsArray basicAt:lastIndex. |
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
357 |
(sortBlock value:lastElement value:anObject) |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
358 |
]) ifTrue:[ |
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
359 |
"/ empty or lastElement is smaller then newElement; add at the end |
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
360 |
index := lastIndex. |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
361 |
(index == contentsArray size) ifTrue:[ |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
362 |
self makeRoomAtLast. |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
363 |
index := lastIndex. |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
364 |
]. |
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
365 |
lastIndex := index := index + 1. |
607 | 366 |
] ifFalse:[ |
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
367 |
index := self indexForInserting:anObject. |
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
368 |
(index == firstIndex) ifTrue:[ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
369 |
(firstIndex == 1) ifTrue:[ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
370 |
self makeRoomAtFront. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
371 |
]. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
372 |
index := firstIndex := firstIndex - 1. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
373 |
] ifFalse:[ |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
374 |
index := self makeRoomAtIndex:index. |
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
375 |
]. |
607 | 376 |
]. |
3340 | 377 |
contentsArray basicAt:index put:anObject. |
607 | 378 |
^ anObject |
2 | 379 |
|
607 | 380 |
" |
11268
7ce883e9a42e
tuned add: if the elements are added in sorted order
Claus Gittinger <cg@exept.de>
parents:
9920
diff
changeset
|
381 |
#(7 3 9 10 99) asSortedCollection add:5; yourself |
8874 | 382 |
#(7 3 9 10 99) asSortedCollection add:1; yourself |
383 |
#(7 3 9 10 99) asSortedCollection add:1000; yourself |
|
11274
a6f648b1d291
tune adding in order / in reverse order
Claus Gittinger <cg@exept.de>
parents:
11268
diff
changeset
|
384 |
#(7 3 9 10 99) asSortedCollection add:1; yourself |
607 | 385 |
" |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
386 |
|
11276 | 387 |
"Modified: / 22-10-2008 / 17:09:39 / cg" |
1 | 388 |
! |
389 |
||
390 |
addAll:aCollection |
|
8874 | 391 |
"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
|
392 |
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
|
393 |
|
20007 | 394 |
|addedCollection| |
1 | 395 |
|
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
396 |
(aCollection isSortedCollection |
7554 | 397 |
and:[aCollection sortBlock == sortBlock]) ifTrue:[ |
11286 | 398 |
addedCollection := aCollection. |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
399 |
] ifFalse:[ |
11286 | 400 |
addedCollection := Array withAll:aCollection. |
14101 | 401 |
addedCollection stableSort:sortBlock. |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
402 |
|
20007 | 403 |
self size == 0 ifTrue:[ |
11286 | 404 |
"/ special case: I am empty - add them en-bloque. |
405 |
contentsArray := addedCollection. |
|
406 |
firstIndex := 1. |
|
20007 | 407 |
lastIndex := aCollection size. |
11286 | 408 |
^ aCollection |
409 |
]. |
|
1 | 410 |
]. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
411 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
412 |
"/ |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
413 |
"/ 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
|
414 |
"/ |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
415 |
self mergeSorted:addedCollection. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
416 |
^ aCollection |
1 | 417 |
|
77 | 418 |
" |
8874 | 419 |
#(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
|
420 |
|
5028
1f7e943ce46e
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
4596
diff
changeset
|
421 |
( #(7 3 9 10 99) asSortedCollection:[:a :b | a > b]) |
11286 | 422 |
addAll:#(77 0 1 16 5); yourself |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
423 |
|
8874 | 424 |
#(7 3 9 10 99) asSortedCollection |
11286 | 425 |
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
|
426 |
|
8874 | 427 |
(#(7 3 9 10 99) asSortedCollection:[:a :b | a > b]) |
11286 | 428 |
addAll:( #(77 0 1 16 5) asSortedCollection:[:a :b | a < b]); yourself |
429 |
" |
|
430 |
||
431 |
" |
|
432 |
|x e| |
|
433 |
||
434 |
e := (1 to:100) asSortedCollection. |
|
435 |
TimeDuration toRun:[ |
|
436 |
10000 timesRepeat:[ |
|
437 |
x := SortedCollection new:100. |
|
438 |
x addAll:e. |
|
439 |
]. |
|
440 |
]. |
|
77 | 441 |
" |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
442 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
443 |
"Modified: 13.4.1996 / 12:42:15 / cg" |
1 | 444 |
! |
445 |
||
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
446 |
mergeSorted:aSortedCollection |
11286 | 447 |
"add all elements of the argument, aSortedCollection to the receiver. |
12038 | 448 |
This leads to an error, if the argument is not sorted. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
449 |
|
8874 | 450 |
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
|
451 |
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
|
452 |
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
|
453 |
Therefore, adding chunks is better done by sorting the chunk and merging |
14310 | 454 |
it in, instead of resorting the receiver. |
455 |
||
456 |
aSortedCollection must be sorted by the same sortBlock as myself!!" |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
457 |
|
8874 | 458 |
|newContentsArray |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
459 |
contentsArray2 |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
460 |
destIndex "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
461 |
n1 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
462 |
n2 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
463 |
srcIndex1 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
464 |
srcIndex2 "{ Class: SmallInteger }" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
465 |
last1 "{ Class: SmallInteger }" |
8874 | 466 |
last2 "{ Class: SmallInteger }" |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
467 |
end1Reached end2Reached |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
468 |
el1 el2 | |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
469 |
|
14310 | 470 |
n2 := aSortedCollection size. |
471 |
n2 == 0 ifTrue:[ |
|
472 |
^ self. |
|
473 |
]. |
|
474 |
||
475 |
aSortedCollection isSortedCollection ifTrue:[ |
|
476 |
contentsArray2 := aSortedCollection contentsArray. |
|
477 |
srcIndex2 := aSortedCollection firstIndex. |
|
478 |
] ifFalse:[ |
|
479 |
contentsArray2 := aSortedCollection. |
|
480 |
srcIndex2 := 1. |
|
481 |
]. |
|
482 |
||
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
483 |
n1 := self size. |
5381
914e310a69be
Fix #mergeSorted if one of the collections is empty.
Stefan Vogel <sv@exept.de>
parents:
5359
diff
changeset
|
484 |
n1 == 0 ifTrue:[ |
14310 | 485 |
firstIndex := srcIndex2. |
486 |
lastIndex := firstIndex + n2 - 1. |
|
487 |
contentsArray := contentsArray2 copy. |
|
11286 | 488 |
^ self. |
5381
914e310a69be
Fix #mergeSorted if one of the collections is empty.
Stefan Vogel <sv@exept.de>
parents:
5359
diff
changeset
|
489 |
]. |
914e310a69be
Fix #mergeSorted if one of the collections is empty.
Stefan Vogel <sv@exept.de>
parents:
5359
diff
changeset
|
490 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
491 |
newContentsArray := Array new:(n1 + n2). |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
492 |
destIndex := 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
493 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
494 |
last2 := srcIndex2 + n2 -1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
495 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
496 |
srcIndex1 := firstIndex. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
497 |
last1 := srcIndex1 + n1 -1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
498 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
499 |
(srcIndex1 <= last1 and:[srcIndex2 <= last2]) ifTrue:[ |
18508 | 500 |
el1 := contentsArray basicAt:srcIndex1. |
501 |
el2 := contentsArray2 basicAt:srcIndex2. |
|
11286 | 502 |
end1Reached := end2Reached := false. |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
503 |
|
11286 | 504 |
[end1Reached or:[end2Reached]] whileFalse:[ |
505 |
(sortBlock value:el1 value:el2) ifTrue:[ |
|
506 |
"/ el1 to come before el2 |
|
18508 | 507 |
newContentsArray basicAt:destIndex put:el1. destIndex := destIndex + 1. |
11286 | 508 |
srcIndex1 := srcIndex1 + 1. |
509 |
srcIndex1 <= last1 ifTrue:[ |
|
18508 | 510 |
el1 := contentsArray basicAt:srcIndex1. |
11286 | 511 |
] ifFalse:[ |
512 |
end1Reached := true |
|
513 |
] |
|
514 |
] ifFalse:[ |
|
515 |
"/ el2 to come before el1 |
|
18508 | 516 |
newContentsArray basicAt:destIndex put:el2. destIndex := destIndex + 1. |
11286 | 517 |
srcIndex2 := srcIndex2 + 1. |
518 |
srcIndex2 <= last2 ifTrue:[ |
|
18508 | 519 |
el2 := contentsArray2 basicAt:srcIndex2. |
11286 | 520 |
] ifFalse:[ |
521 |
end2Reached := true |
|
522 |
] |
|
523 |
] |
|
524 |
] |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
525 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
526 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
527 |
"/ 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
|
528 |
(srcIndex1 <= last1) ifTrue:[ |
11286 | 529 |
newContentsArray |
530 |
replaceFrom:destIndex |
|
531 |
to:(destIndex+(last1-srcIndex1)) |
|
532 |
with:contentsArray |
|
533 |
startingAt:srcIndex1 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
534 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
535 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
536 |
"/ 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
|
537 |
(srcIndex2 <= last2) ifTrue:[ |
11286 | 538 |
newContentsArray |
539 |
replaceFrom:destIndex |
|
540 |
to:(destIndex+(last2-srcIndex2)) |
|
541 |
with:contentsArray2 |
|
542 |
startingAt:srcIndex2 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
543 |
]. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
544 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
545 |
firstIndex := 1. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
546 |
lastIndex := n1 + n2. |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
547 |
contentsArray := newContentsArray |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
548 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
549 |
" |
8874 | 550 |
#(7 3 9 10 99) asSortedCollection |
11286 | 551 |
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
|
552 |
|
8874 | 553 |
#(7 3 9 10 99) asSortedCollection |
11286 | 554 |
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
|
555 |
|
8874 | 556 |
#() asSortedCollection |
11286 | 557 |
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
|
558 |
|
8874 | 559 |
#(7 3 9 10 99) asSortedCollection |
11286 | 560 |
mergeSorted:#() asSortedCollection |
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
561 |
" |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
562 |
|
3250
c4b444774f1c
oops - mergesort cannot simply copy remaining
Claus Gittinger <cg@exept.de>
parents:
2929
diff
changeset
|
563 |
"Modified: / 30.1.1998 / 01:49:42 / cg" |
607 | 564 |
! ! |
565 |
||
5560 | 566 |
!SortedCollection methodsFor:'blocked'! |
567 |
||
568 |
add:newObject after:oldObject |
|
569 |
"catch this - its not allowed for sortedCollections" |
|
570 |
||
571 |
self shouldNotImplement |
|
572 |
! |
|
573 |
||
574 |
add:newObject before:oldObject |
|
575 |
"catch this - its not allowed for sortedCollections" |
|
576 |
||
577 |
self shouldNotImplement |
|
578 |
! |
|
579 |
||
580 |
addFirst:anObject |
|
581 |
"catch this - its not allowed for sortedCollections" |
|
582 |
||
583 |
self shouldNotImplement |
|
584 |
! |
|
585 |
||
586 |
addLast:anObject |
|
587 |
"catch this - its not allowed for sortedCollections" |
|
588 |
||
589 |
self shouldNotImplement |
|
590 |
! ! |
|
591 |
||
607 | 592 |
!SortedCollection methodsFor:'converting'! |
593 |
||
594 |
asSortedCollection |
|
595 |
"return the receiver as a sorted collection" |
|
596 |
||
597 |
"could be an instance of a subclass..." |
|
598 |
self class == SortedCollection ifTrue:[ |
|
8874 | 599 |
sortBlock == DefaultSortBlock ifTrue:[ |
600 |
^ self |
|
601 |
] |
|
1 | 602 |
]. |
607 | 603 |
^ super asSortedCollection |
5029
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
604 |
! |
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
605 |
|
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
606 |
asSortedCollection:aSortBlock |
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
607 |
"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
|
608 |
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
|
609 |
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
|
610 |
|
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
611 |
"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
|
612 |
self class == SortedCollection ifTrue:[ |
8874 | 613 |
"/ if the sortBlock is the same, return the receiver |
614 |
aSortBlock == sortBlock ifTrue:[ |
|
615 |
^ self |
|
616 |
]. |
|
5029
ae3312dda1dd
avoid creation of a new sortedCollection in #asSortedCollection:
Claus Gittinger <cg@exept.de>
parents:
5028
diff
changeset
|
617 |
]. |
5030
655a0f0a60c3
use my sortBlock when merge-sorting
Claus Gittinger <cg@exept.de>
parents:
5029
diff
changeset
|
618 |
^ super asSortedCollection:aSortBlock |
1 | 619 |
! ! |
620 |
||
95 | 621 |
!SortedCollection methodsFor:'copying'! |
622 |
||
607 | 623 |
copyEmpty:size |
624 |
"return a copy of the receiver with no elements, but |
|
625 |
the same size. This method has been be redefined to |
|
626 |
preserve the sortBlock." |
|
627 |
||
14110 | 628 |
^ (super copyEmpty:size) sortBlock:sortBlock |
607 | 629 |
! |
630 |
||
159 | 631 |
postCopyFrom:anOriginal |
632 |
"sent after a copy or when a new collection species has been created. |
|
95 | 633 |
The new collection should have the same sortBlock as the original." |
634 |
||
159 | 635 |
sortBlock := anOriginal sortBlock |
95 | 636 |
|
637 |
" |
|
638 |
#(4 7 1 99 -1 17) asSortedCollection inspect |
|
159 | 639 |
#(4 7 1 99 -1 17) asSortedCollection copy inspect |
95 | 640 |
(#(4 7 1 99 -1 17) asSortedCollection sortBlock:[:a :b | a > b]) inspect |
159 | 641 |
(#(4 7 1 99 -1 17) asSortedCollection sortBlock:[:a :b | a > b]) copy inspect |
642 |
(#(4 7 1 99 -1 17) asSortedCollection select:[:e| e even]) inspect |
|
95 | 643 |
" |
644 |
! ! |
|
645 |
||
216 | 646 |
!SortedCollection methodsFor:'enumerating'! |
184 | 647 |
|
648 |
collect:aBlock |
|
649 |
"evaluate the argument, aBlock for every element in the collection |
|
650 |
and return a collection of the results. Redefined to return an OrderedCollection; |
|
651 |
see X3J20 spec. (SortedCollection>>collect: should return an OrderedCollection)" |
|
652 |
||
653 |
|newCollection |
|
654 |
start "{ Class:SmallInteger }" |
|
655 |
stop "{ Class:SmallInteger }" | |
|
656 |
||
18508 | 657 |
newCollection := self speciesForCollecting new:(self size). |
184 | 658 |
stop := lastIndex. |
659 |
start := firstIndex. |
|
660 |
start to:stop do:[:index | |
|
18508 | 661 |
newCollection add:(aBlock value:(contentsArray basicAt:index)). |
184 | 662 |
]. |
663 |
^ newCollection |
|
664 |
! ! |
|
665 |
||
607 | 666 |
!SortedCollection methodsFor:'instance protocol'! |
667 |
||
5668
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
668 |
sort:aSortBlock |
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
669 |
"redefined from superclass to change the sortBlock" |
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
670 |
|
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
671 |
sortBlock ~~ aSortBlock ifTrue:[ |
8874 | 672 |
self sortBlock:aSortBlock. |
5668
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
673 |
]. |
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
674 |
|
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
675 |
! |
0cbaa16dc17c
Inherited #sort: shows a debugger.
Stefan Vogel <sv@exept.de>
parents:
5604
diff
changeset
|
676 |
|
607 | 677 |
sortBlock |
678 |
"return the block used for sorting" |
|
679 |
||
680 |
^ sortBlock |
|
681 |
! |
|
682 |
||
683 |
sortBlock:aSortBlock |
|
8874 | 684 |
"change the sort criteria for a sorted collection, resort the elements of |
607 | 685 |
the collection, and return the receiver. The argument, aSortBlock must |
686 |
be a two-argument block which returns true if its arg1 has to come before |
|
687 |
its arg2 in the collection." |
|
688 |
||
689 |
sortBlock := aSortBlock. |
|
690 |
lastIndex > firstIndex ifTrue:[ |
|
691 |
contentsArray quickSortFrom:firstIndex to:lastIndex sortBlock:aSortBlock |
|
692 |
] |
|
693 |
||
694 |
" |
|
695 |
#(9 8 7 6 5 4 3) asSortedCollection |
|
696 |
#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b] |
|
697 |
#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b] |
|
698 |
#($f $G $z $Y $o $H) asSortedCollection |
|
699 |
#($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase] |
|
700 |
" |
|
701 |
! ! |
|
702 |
||
703 |
!SortedCollection methodsFor:'private'! |
|
704 |
||
18508 | 705 |
indexForInserting:anObject |
706 |
"search the index at which to insert anObject. |
|
707 |
Can also be used to search for an existing element |
|
708 |
by checking if the element at the returned index is the one we look for. |
|
709 |
Uses a binarySearch since we can depend on the elements being in sorted order. |
|
710 |
The returned index is a physical one, for accessing contentsArray." |
|
711 |
||
712 |
|low "{ Class: SmallInteger}" |
|
713 |
high "{ Class: SmallInteger}" |
|
714 |
middle "{ Class: SmallInteger}" |
|
715 |
element| |
|
716 |
||
717 |
" |
|
718 |
we can of course use a binary search - since the elements are sorted |
|
719 |
" |
|
720 |
low := firstIndex. |
|
721 |
high := lastIndex. |
|
722 |
[low > high] whileFalse:[ |
|
723 |
middle := (low + high) // 2. |
|
724 |
element := contentsArray basicAt:middle. |
|
725 |
(sortBlock value:element value:anObject) ifTrue:[ |
|
726 |
"middleelement is smaller than object" |
|
727 |
low := middle + 1 |
|
728 |
] ifFalse:[ |
|
729 |
high := middle - 1 |
|
730 |
] |
|
731 |
]. |
|
732 |
^ low |
|
733 |
||
734 |
" |
|
735 |
#(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
|
736 |
||
737 |
#(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50 |
|
738 |
||
739 |
" |
|
740 |
||
741 |
"Modified: 12.4.1996 / 13:22:03 / cg" |
|
742 |
! |
|
743 |
||
607 | 744 |
setSortBlock: aSortBlock |
745 |
"set the sortblock without resorting - private only" |
|
746 |
||
747 |
sortBlock := aSortBlock |
|
748 |
! ! |
|
749 |
||
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
750 |
!SortedCollection methodsFor:'queries'! |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
751 |
|
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
752 |
isSorted |
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
753 |
"return true. if my elements are sorted" |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
754 |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
755 |
^ true |
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
756 |
! |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
757 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
758 |
isSortedBy:aBlock |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
759 |
"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
|
760 |
|
5359
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
761 |
aBlock == sortBlock ifTrue:[^ true]. |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
762 |
^ super isSortedBy:aBlock |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
763 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
764 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
765 |
! |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
766 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
767 |
isSortedCollection |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
768 |
"return true. if I am a sorted collection" |
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
769 |
|
396b77b6f1d2
added #isSortedCollection, #isSortedBy:
Claus Gittinger <cg@exept.de>
parents:
5048
diff
changeset
|
770 |
^ true |
18508 | 771 |
! |
772 |
||
773 |
speciesForCollecting |
|
774 |
"Redefined to return an OrderedCollection; |
|
775 |
see X3J20 spec. (SortedCollection>>collect: should return an OrderedCollection)" |
|
776 |
||
777 |
^ OrderedCollection |
|
1173
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
778 |
! ! |
1d831f2c0d44
added #mergeSorted; changed #addAll: to make use of it
Claus Gittinger <cg@exept.de>
parents:
1167
diff
changeset
|
779 |
|
607 | 780 |
!SortedCollection methodsFor:'searching'! |
781 |
||
782 |
after:anObject ifAbsent:exceptionBlock |
|
783 |
"return the element after the argument, anObject; or nil if there is none. |
|
784 |
If anObject is contained multiple times in the collection, return the |
|
785 |
the first element which is non-equal to anObject. |
|
786 |
If the receiver does not contain anObject, return the result from evaluating |
|
787 |
exceptionBlock." |
|
788 |
||
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
789 |
|index "{ Class: SmallInteger }" |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
790 |
last "{ Class: SmallInteger }"| |
607 | 791 |
|
18508 | 792 |
index := self indexOf:anObject. |
793 |
index == 0 ifTrue:[ |
|
794 |
^ exceptionBlock value. |
|
795 |
]. |
|
607 | 796 |
|
8874 | 797 |
"skip multiple occurrences of the same ..." |
18508 | 798 |
index := index + firstIndex - 1. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
799 |
last := lastIndex. |
18508 | 800 |
[(index <= last) and:[(contentsArray basicAt:index) = anObject]] whileTrue:[ |
801 |
index := index + 1 |
|
607 | 802 |
]. |
18508 | 803 |
(index > last) ifTrue:[^ exceptionBlock value]. |
804 |
^ contentsArray basicAt:index |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
805 |
|
18508 | 806 |
" |
807 |
#(7 3 9 10 99) asSortedCollection after:50 |
|
808 |
#(7 3 9 10 99) asSortedCollection after:3 |
|
809 |
#(7 3 9 10 99) asSortedCollection after:1 |
|
810 |
#(7 3 9 10 99) asSortedCollection after:10 |
|
811 |
#(7 3 9 10 99) asSortedCollection after:7 |
|
812 |
#(7 3 9 10 99) asSortedCollection after:99 |
|
813 |
#(7 10 3 10 9 10 10 99) asSortedCollection after:9 |
|
814 |
#(7 10 3 10 9 10 10 99) asSortedCollection after:10 |
|
815 |
" |
|
607 | 816 |
! |
817 |
||
818 |
before:anObject ifAbsent:exceptionBlock |
|
819 |
"return the element before the argument, anObject; or nil if there is none. |
|
820 |
If the receiver does not contain anObject, return the result from evaluating |
|
821 |
exceptionBlock." |
|
822 |
||
823 |
|index "{ Class: SmallInteger }"| |
|
824 |
||
18508 | 825 |
index := self indexOf:anObject. |
826 |
index <= 1 ifTrue:[ |
|
827 |
^ exceptionBlock value. |
|
828 |
]. |
|
829 |
^ contentsArray basicAt:firstIndex + index - 2 |
|
607 | 830 |
|
831 |
" |
|
832 |
#(7 3 9 10 99) asSortedCollection before:50 |
|
18508 | 833 |
#(7 3 9 10 99) asSortedCollection before:3 |
8874 | 834 |
#(7 3 9 10 99) asSortedCollection before:1 |
835 |
#(7 3 9 10 99) asSortedCollection before:10 |
|
836 |
#(7 3 9 10 99) asSortedCollection before:7 |
|
837 |
#(7 3 9 10 99) asSortedCollection before:99 |
|
838 |
#(7 10 3 10 9 10 10 99) asSortedCollection before:9 |
|
839 |
#(7 10 3 10 9 10 10 99) asSortedCollection before:10 |
|
607 | 840 |
" |
4596 | 841 |
! |
842 |
||
18508 | 843 |
indexOf:anObject |
844 |
"return true, if the argument, anObject is in the collection. |
|
845 |
Redefined, since due to being sorted, the inclusion check can |
|
846 |
be done with log-n compares i.e. much faster." |
|
847 |
||
848 |
|index "{ Class: SmallInteger }" |
|
849 |
initialIndex "{ Class: SmallInteger }" |
|
850 |
element| |
|
851 |
||
852 |
"/ if I am small, the inherited linear search is faster ... |
|
853 |
(lastIndex - firstIndex) < 20 ifTrue:[ |
|
854 |
firstIndex > lastIndex ifTrue:[ |
|
855 |
"/ empty |
|
856 |
^ 0 |
|
857 |
]. |
|
858 |
^ super indexOf:anObject. |
|
859 |
]. |
|
860 |
||
861 |
initialIndex := self indexForInserting:anObject. |
|
862 |
initialIndex > lastIndex ifTrue:[ |
|
863 |
initialIndex := lastIndex |
|
864 |
] ifFalse:[ |
|
865 |
initialIndex < firstIndex ifTrue:[ |
|
866 |
initialIndex := firstIndex |
|
867 |
] |
|
868 |
]. |
|
14310 | 869 |
|
19129 | 870 |
"the complex case: the collection may include elements, which are ordered only by |
18508 | 871 |
a single component (e.g. Associations by key). So we have to test all |
872 |
previous and next elements having the same component" |
|
873 |
||
874 |
"for previous elements: while element is not smaller and not larger than anObject ... compare" |
|
875 |
index := initialIndex. |
|
876 |
[index >= firstIndex |
|
877 |
and:[ |
|
878 |
element := contentsArray basicAt:index. |
|
879 |
((sortBlock value:element value:anObject) or:[sortBlock value:anObject value:element]) not] |
|
880 |
] whileTrue:[ |
|
881 |
element = anObject ifTrue:[ |
|
882 |
^ index - firstIndex + 1. |
|
883 |
]. |
|
884 |
index := index - 1. |
|
885 |
]. |
|
886 |
||
887 |
"for next elements: while element is not smaller and not larger than anObject ... compare" |
|
888 |
index := initialIndex. |
|
889 |
[index <= lastIndex |
|
890 |
and:[ |
|
891 |
element := contentsArray basicAt:index. |
|
892 |
((sortBlock value:element value:anObject) or:[sortBlock value:anObject value:element]) not] |
|
893 |
] whileTrue:[ |
|
894 |
element = anObject ifTrue:[ |
|
895 |
^ index - firstIndex + 1. |
|
896 |
]. |
|
897 |
index := index + 1. |
|
898 |
]. |
|
899 |
||
900 |
^ 0. |
|
14310 | 901 |
|
902 |
" |
|
18508 | 903 |
#(7 3 9 10 99) asSortedCollection indexOf:50 |
904 |
#(7 3 9 10 99) asSortedCollection indexOf:10 |
|
905 |
||
906 |
#('aa' 'bb' 'cc' 'dd') asSortedCollection indexOf:'bb' |
|
907 |
#('aa' 'bb' 'cc' 'dd' 'aa' 'bb' 'cc' 'dd') asSortedCollection indexOf:'bb' |
|
14310 | 908 |
|
18508 | 909 |
|allSyms indices| |
910 |
allSyms := Symbol allInstances asSortedCollection. |
|
911 |
Time millisecondsToRun:[ |
|
912 |
indices := allSyms collect:[:el | allSyms indexOf:el]. |
|
913 |
]. |
|
914 |
indices = (1 to:allSyms size) |
|
14310 | 915 |
" |
4596 | 916 |
! |
917 |
||
918 |
indexOf:anElement ifAbsent:exceptionBlock |
|
8874 | 919 |
"Return the index of anElement within the receiver. |
920 |
If the receiver does not contain anElement, |
|
4596 | 921 |
return the result of evaluating the argument, exceptionBlock." |
922 |
||
18508 | 923 |
|idx| |
4596 | 924 |
|
18508 | 925 |
idx := self indexOf:anElement. |
926 |
idx == 0 ifTrue:[^ exceptionBlock value]. |
|
927 |
^ idx. |
|
16002 | 928 |
! |
929 |
||
930 |
largest:n |
|
931 |
"return a collection containing the n largest elements, largest last. |
|
932 |
Raises an exception, if the receiver does not contain at least n elements" |
|
933 |
||
934 |
|mySize| |
|
935 |
||
936 |
mySize := self size. |
|
937 |
n > mySize ifTrue:[ |
|
938 |
self notEnoughElementsError |
|
939 |
]. |
|
940 |
sortBlock == DefaultSortBlock ifTrue:[ |
|
941 |
^ self copyFrom:(mySize-n+1) |
|
942 |
]. |
|
943 |
"/ do not trust the sortblock to sort small-to-large |
|
944 |
^ super largest:n |
|
945 |
||
946 |
" |
|
947 |
#(10 35 20 45 30 5) asSortedCollection largest:3 |
|
948 |
(#(10 35 20 45 30 5) asSortedCollection:[:a :b | a > b]) largest:3 |
|
949 |
||
950 |
#(10 35 20 45 30 5) asSortedCollection largest:6 |
|
951 |
#(10 35 20 45 30 5) asSortedCollection largest:7 |
|
952 |
" |
|
953 |
! |
|
954 |
||
955 |
max |
|
19074 | 956 |
"return the maximum value in the receiver collection, |
957 |
redefined, since this can be easily computed. |
|
958 |
Raises an error, if the receiver is empty." |
|
16002 | 959 |
|
960 |
sortBlock == DefaultSortBlock ifTrue:[ |
|
961 |
^ self last |
|
962 |
]. |
|
963 |
^ super max |
|
964 |
||
965 |
" |
|
966 |
#(10 35 20 45 30 5) asSortedCollection max |
|
19075 | 967 |
#(10 35 20 45 30 5) max |
19074 | 968 |
#() asSortedCollection max |
16002 | 969 |
" |
970 |
! |
|
971 |
||
972 |
min |
|
19074 | 973 |
"return the minimum value in the receiver collection, |
974 |
redefined, since this can be easily computed. |
|
975 |
Raises an error, if the receiver is empty." |
|
16002 | 976 |
|
977 |
sortBlock == DefaultSortBlock ifTrue:[ |
|
978 |
^ self first |
|
979 |
]. |
|
980 |
^ super min |
|
981 |
||
982 |
" |
|
983 |
#(10 35 20 45 30 5) asSortedCollection min |
|
19075 | 984 |
#(10 35 20 45 30 5) min |
985 |
" |
|
986 |
! |
|
987 |
||
988 |
minMax |
|
989 |
"return the minimum and maximum values in the receiver collection |
|
990 |
as a two element array, using #< to compare elements. |
|
991 |
Raises an error, if the receiver is empty." |
|
992 |
||
993 |
"return the minimum value in the receiver collection, |
|
994 |
redefined, since this can be easily computed. |
|
995 |
Raises an error, if the receiver is empty." |
|
996 |
||
997 |
sortBlock == DefaultSortBlock ifTrue:[ |
|
998 |
^ { self first . self last } |
|
999 |
]. |
|
1000 |
^ super minMax |
|
1001 |
||
1002 |
" |
|
1003 |
#(10 35 20 45 30 5) asSortedCollection minMax |
|
1004 |
#(10 35 20 45 30 5) minMax |
|
16002 | 1005 |
" |
1006 |
! |
|
1007 |
||
1008 |
smallest:n |
|
1009 |
"return a collection containing the n smallest elements, largest last. |
|
1010 |
Raises an exception, if the receiver does not contain at least n elements" |
|
1011 |
||
1012 |
|mySize| |
|
1013 |
||
1014 |
mySize := self size. |
|
1015 |
n > mySize ifTrue:[ |
|
1016 |
self notEnoughElementsError |
|
1017 |
]. |
|
1018 |
sortBlock == DefaultSortBlock ifTrue:[ |
|
1019 |
^ self copyTo:n |
|
1020 |
]. |
|
1021 |
"/ do not trust the sortblock to sort small-to-large |
|
1022 |
^ super smallest:n |
|
1023 |
||
1024 |
" |
|
1025 |
#(10 35 20 45 30 5) asSortedCollection smallest:3 |
|
1026 |
(#(10 35 20 45 30 5) asSortedCollection:[:a :b | a > b]) smallest:3 |
|
1027 |
||
1028 |
#(10 35 20 45 30 5) asSortedCollection smallest:6 |
|
1029 |
#(10 35 20 45 30 5) asSortedCollection smallest:7 |
|
1030 |
" |
|
1031 |
! ! |
|
1032 |
||
1033 |
!SortedCollection methodsFor:'statistical functions'! |
|
1034 |
||
1035 |
median |
|
1036 |
"Return the middle element, or as close as we can get." |
|
1037 |
||
18508 | 1038 |
^ self basicAt:(self size + 1 // 2) |
16002 | 1039 |
|
1040 |
" |
|
1041 |
#(10 35 20 45 30 5) asSortedCollection median |
|
1042 |
#(10 35 20 45 30 5) median |
|
1043 |
" |
|
607 | 1044 |
! ! |
1045 |
||
1 | 1046 |
!SortedCollection methodsFor:'testing'! |
1047 |
||
1048 |
includes:anObject |
|
1049 |
"return true, if the argument, anObject is in the collection. |
|
62 | 1050 |
Redefined, since due to being sorted, the inclusion check can |
2 | 1051 |
be done with log-n compares i.e. much faster." |
1 | 1052 |
|
18508 | 1053 |
|index "{ Class: SmallInteger }" |
1054 |
initialIndex "{ Class: SmallInteger }" |
|
1055 |
element| |
|
1056 |
||
1057 |
"/ if I am small, the inherited linear search is faster ... |
|
1058 |
(lastIndex - firstIndex) < 20 ifTrue:[ |
|
1059 |
firstIndex > lastIndex ifTrue:[ |
|
1060 |
"/ empty |
|
1061 |
^ false |
|
1062 |
]. |
|
1063 |
^ super includes:anObject. |
|
1064 |
]. |
|
1065 |
||
1066 |
initialIndex := self indexForInserting:anObject. |
|
1067 |
((initialIndex < firstIndex) or:[initialIndex > lastIndex]) ifTrue:[^ false]. |
|
1068 |
(contentsArray basicAt:initialIndex) = anObject ifTrue:[ |
|
1069 |
"the simple case - plain objects" |
|
1070 |
^ true. |
|
1071 |
]. |
|
1072 |
||
1073 |
"the complex case: the collection may include elements, which are odered only by |
|
1074 |
a single component (e.g. Associations by key). So we have to test all |
|
1075 |
previous and next elements having the same component" |
|
1 | 1076 |
|
18508 | 1077 |
"for previous elements: while element is not smaller and not larger than anObject ... compare" |
1078 |
index := initialIndex - 1. |
|
1079 |
[index >= firstIndex |
|
1080 |
and:[ |
|
1081 |
element := contentsArray basicAt:index. |
|
1082 |
((sortBlock value:element value:anObject) or:[sortBlock value:anObject value:element]) not] |
|
1083 |
] whileTrue:[ |
|
1084 |
element = anObject ifTrue:[ |
|
1085 |
^ true. |
|
1086 |
]. |
|
1087 |
index := index - 1. |
|
1088 |
]. |
|
1089 |
||
1090 |
"for next elements: while element is not smaller and not larger than anObject ... compare" |
|
1091 |
index := initialIndex + 1. |
|
1092 |
[index <= lastIndex |
|
1093 |
and:[ |
|
1094 |
element := contentsArray basicAt:index. |
|
1095 |
((sortBlock value:element value:anObject) or:[sortBlock value:anObject value:element]) not] |
|
1096 |
] whileTrue:[ |
|
1097 |
element = anObject ifTrue:[ |
|
1098 |
^ true. |
|
1099 |
]. |
|
1100 |
index := index + 1. |
|
1101 |
]. |
|
1102 |
||
1103 |
^ false. |
|
2 | 1104 |
|
77 | 1105 |
" |
1106 |
#(7 3 9 10 99) asSortedCollection includes:50 |
|
1107 |
#(7 3 9 10 99) asSortedCollection includes:10 |
|
1108 |
" |
|
1 | 1109 |
! |
1110 |
||
1111 |
occurrencesOf:anObject |
|
1112 |
"return how many times the argument, anObject is in the collection. |
|
62 | 1113 |
Redefined, since due to being sorted, the range of checked objects |
5048 | 1114 |
can be limited i.e. it can be done much faster. |
1115 |
Uses #= (i.e. equality) compare." |
|
1 | 1116 |
|
1117 |
|index "{ Class: SmallInteger }" |
|
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
1118 |
tally "{ Class: SmallInteger }" |
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
1119 |
last "{ Class: SmallInteger }" | |
1 | 1120 |
|
18508 | 1121 |
index := self indexOf:anObject. |
1122 |
index == 0 ifTrue:[ |
|
1123 |
^ 0 |
|
1124 |
]. |
|
1125 |
||
1126 |
index := index + firstIndex - 1. |
|
8874 | 1127 |
last := lastIndex. |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
1128 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
1129 |
"/ there may be multiple of them; count 'em |
32 | 1130 |
|
1 | 1131 |
tally := 0. |
18508 | 1132 |
[(index <= last) and:[(contentsArray basicAt:index) = anObject]] whileTrue:[ |
1133 |
tally := tally + 1. |
|
1134 |
index := index + 1 |
|
1 | 1135 |
]. |
1136 |
^ tally |
|
2 | 1137 |
|
77 | 1138 |
" |
1139 |
#(7 3 9 10 99) asSortedCollection occurrencesOf:50 |
|
1140 |
#(7 3 9 10 99) asSortedCollection occurrencesOf:10 |
|
18508 | 1141 |
#(7 10 3 10 9 10 10 10 10 10 10 10 10 99) asSortedCollection occurrencesOf:10 |
77 | 1142 |
" |
1162
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
1143 |
|
3995101dfa44
changed for new #makeRoomAtIndex:; added comments
Claus Gittinger <cg@exept.de>
parents:
1156
diff
changeset
|
1144 |
"Modified: 12.4.1996 / 18:48:40 / cg" |
77 | 1145 |
! ! |
1146 |
||
629 | 1147 |
!SortedCollection class methodsFor:'documentation'! |
1148 |
||
1149 |
version |
|
18508 | 1150 |
^ '$Header$' |
14309
602e61cb64a3
Remove now unused helper method
Stefan Vogel <sv@exept.de>
parents:
14308
diff
changeset
|
1151 |
! |
602e61cb64a3
Remove now unused helper method
Stefan Vogel <sv@exept.de>
parents:
14308
diff
changeset
|
1152 |
|
602e61cb64a3
Remove now unused helper method
Stefan Vogel <sv@exept.de>
parents:
14308
diff
changeset
|
1153 |
version_CVS |
18508 | 1154 |
^ '$Header$' |
629 | 1155 |
! ! |
7300 | 1156 |
|
16000 | 1157 |
|
607 | 1158 |
SortedCollection initialize! |