author | Stefan Vogel <sv@exept.de> |
Tue, 28 Apr 2020 16:21:34 +0200 | |
changeset 25373 | f030619565e1 |
parent 24855 | bb545059703b |
permissions | -rw-r--r-- |
24621 | 1 |
"{ Encoding: utf8 }" |
2 |
||
1 | 3 |
" |
5 | 4 |
COPYRIGHT (c) 1991 by Claus Gittinger |
345 | 5 |
All Rights Reserved |
1 | 6 |
|
7 |
This software is furnished under a license and may be used |
|
8 |
only in accordance with the terms of that license and with the |
|
9 |
inclusion of the above copyright notice. This software may not |
|
10 |
be provided or otherwise made available to, or used by, any |
|
11 |
other person. No title to or ownership of the software is |
|
12 |
hereby transferred. |
|
13 |
" |
|
5375 | 14 |
"{ Package: 'stx:libbasic' }" |
15 |
||
18468 | 16 |
"{ NameSpace: Smalltalk }" |
17 |
||
1 | 18 |
Collection subclass:#Bag |
1057 | 19 |
instanceVariableNames:'contents' |
20 |
classVariableNames:'' |
|
21 |
poolDictionaries:'' |
|
22 |
category:'Collections-Unordered' |
|
1 | 23 |
! |
24 |
||
54 | 25 |
!Bag class methodsFor:'documentation'! |
26 |
||
88 | 27 |
copyright |
28 |
" |
|
29 |
COPYRIGHT (c) 1991 by Claus Gittinger |
|
345 | 30 |
All Rights Reserved |
88 | 31 |
|
32 |
This software is furnished under a license and may be used |
|
33 |
only in accordance with the terms of that license and with the |
|
34 |
inclusion of the above copyright notice. This software may not |
|
35 |
be provided or otherwise made available to, or used by, any |
|
36 |
other person. No title to or ownership of the software is |
|
37 |
hereby transferred. |
|
38 |
" |
|
39 |
! |
|
40 |
||
54 | 41 |
documentation |
42 |
" |
|
20628 | 43 |
Bags are collections where the elements are unordered and have no external key. |
44 |
Elements may occur more than once in a bag. |
|
45 |
There is no defined order within a bag. |
|
46 |
The default implementation uses a dictionary to store each object's occurrence count, |
|
47 |
using the object itself as key |
|
48 |
(i.e. using = and hash for inclusion tests). |
|
399 | 49 |
|
20628 | 50 |
There is also an instance creation variant (#identityNew:) which creats a |
345 | 51 |
bag which compares using #== and hashes using #identityHash. |
20628 | 52 |
(I'd say that instantiating an IdentityBag explicitly is better, |
399 | 53 |
... but for compatibility ... we do it here as well) |
1 | 54 |
|
1283 | 55 |
[Instance variables:] |
56 |
||
20628 | 57 |
contents <Dictionary> for each element, the number of occurrences |
1283 | 58 |
|
1 | 59 |
|
1290 | 60 |
[author:] |
20628 | 61 |
Claus Gittinger |
1290 | 62 |
|
1283 | 63 |
[See also:] |
20628 | 64 |
Set IdentitySet |
65 |
Dictionary IdentityDictionary |
|
66 |
OrderedCollection Array |
|
54 | 67 |
" |
68 |
! ! |
|
1 | 69 |
|
70 |
!Bag class methodsFor:'instance creation'! |
|
71 |
||
14956 | 72 |
contentsClass |
73 |
"the default class to use for the underlying contents array, |
|
74 |
used when instantiated with new/new:" |
|
75 |
||
76 |
^ Dictionary |
|
77 |
! |
|
78 |
||
79 |
equalityNew |
|
80 |
"return a new empty Bag. |
|
81 |
Elements will be compared using equality compare (i.e. #= not #== identity)." |
|
82 |
||
83 |
^ self basicNew initContentsForEquality |
|
84 |
! |
|
85 |
||
345 | 86 |
equalityNew:size |
87 |
"return a new empty Bag with initial space for size elements. |
|
88 |
Elements will be compared using equality compare (i.e. #= not #== identity)." |
|
1 | 89 |
|
14956 | 90 |
^ self basicNew initContentsForEquality:size |
345 | 91 |
! |
92 |
||
5375 | 93 |
identityNew |
14956 | 94 |
"return a new empty Identity-Bag. |
5375 | 95 |
Elements will be compared using identity compare (i.e. #== not #= equality)." |
96 |
||
14956 | 97 |
^ self basicNew initContentsForIdentity |
5375 | 98 |
! |
99 |
||
345 | 100 |
identityNew:size |
101 |
"return a new empty Bag with initial space for size elements. |
|
102 |
Elements will be compared using identity compare (i.e. #== not #= equality)." |
|
103 |
||
5558 | 104 |
^ self basicNew initContentsForIdentity:size |
1 | 105 |
! |
106 |
||
609 | 107 |
new |
108 |
"return a new empty Bag which compares for equality (i.e. not identity)" |
|
1 | 109 |
|
5558 | 110 |
^ self basicNew initContents |
345 | 111 |
! |
112 |
||
609 | 113 |
new:size |
114 |
"return a new empty Bag with initial space for size elements. |
|
115 |
Elements will be compared using equality compare (i.e. #= not #== identity)." |
|
345 | 116 |
|
24855 | 117 |
^ self basicNew initContents:size |
118 |
||
119 |
"Modified: / 22-10-2019 / 20:21:58 / Stefan Vogel" |
|
22308 | 120 |
! |
121 |
||
122 |
newWithCapacity:size |
|
123 |
"return a new empty Collection with capacity for n elements." |
|
124 |
||
125 |
^ self new:size |
|
126 |
||
127 |
"Created: / 10-10-2017 / 17:49:15 / stefan" |
|
1 | 128 |
! ! |
129 |
||
7261 | 130 |
!Bag methodsFor:'Compatibility-Dolphin'! |
6411 | 131 |
|
132 |
asAssociations |
|
11935 | 133 |
"return the dictionary which associates occurrence-counts |
134 |
to the bags elements. |
|
135 |
Same as #contents for dolphin compatibility." |
|
136 |
||
14685 | 137 |
^ self contents |
6411 | 138 |
! ! |
139 |
||
1 | 140 |
!Bag methodsFor:'accessing'! |
141 |
||
142 |
at:index |
|
143 |
"report an error: at: is not allowed for Bags" |
|
144 |
||
145 |
^ self errorNotKeyed |
|
146 |
! |
|
147 |
||
148 |
at:index put:anObject |
|
149 |
"report an error: at:put: is not allowed for Bags" |
|
150 |
||
151 |
^ self errorNotKeyed |
|
345 | 152 |
! |
153 |
||
154 |
contents |
|
155 |
"return the dictionary which associates occurrence-counts |
|
156 |
to the bags elements." |
|
157 |
||
158 |
^ contents |
|
15732 | 159 |
|
160 |
" |
|
161 |
Bag new |
|
162 |
add:'abc'; |
|
163 |
add:'def'; |
|
164 |
add:'ghi'; |
|
165 |
add:'abc'; |
|
166 |
add:'def'; |
|
167 |
add:'abc'; |
|
168 |
add:'abc'; |
|
169 |
contents |
|
170 |
" |
|
15686 | 171 |
! |
172 |
||
173 |
sortedCounts |
|
15732 | 174 |
"Answer with a collection of counts associated to elements, sorted by decreasing count." |
15686 | 175 |
"Suggested by l. Uzonyi" |
176 |
||
177 |
^ (Array new:contents size |
|
178 |
streamContents:[:stream | |
|
179 |
contents associationsDo:[:each | stream nextPut:each value -> each key ] |
|
180 |
]) |
|
16766 | 181 |
sort:[:x :y | y < x]; |
15686 | 182 |
yourself |
15731 | 183 |
|
184 |
" |
|
185 |
Bag new |
|
186 |
add:'abc'; |
|
187 |
add:'def'; |
|
188 |
add:'ghi'; |
|
189 |
add:'abc'; |
|
190 |
add:'def'; |
|
191 |
add:'abc'; |
|
192 |
add:'abc'; |
|
193 |
sortedCounts |
|
194 |
" |
|
16098 | 195 |
! |
196 |
||
197 |
valuesSortedByCounts |
|
198 |
"Answer with a collection of values, sorted by decreasing count. |
|
199 |
Count informtion is lost in the result" |
|
200 |
||
201 |
^ self sortedCounts collect:[:assoc | assoc value]. |
|
202 |
||
203 |
" |
|
204 |
Bag new |
|
205 |
add:'abc'; |
|
206 |
add:'def'; |
|
207 |
add:'ghi'; |
|
208 |
add:'abc'; |
|
209 |
add:'def'; |
|
210 |
add:'abc'; |
|
211 |
add:'abc'; |
|
212 |
valuesSortedByCounts |
|
213 |
" |
|
1 | 214 |
! ! |
215 |
||
216 |
!Bag methodsFor:'adding & removing'! |
|
217 |
||
54 | 218 |
add:newObject |
345 | 219 |
"add the argument, anObject to the receiver. |
14896 | 220 |
Returns the object (sigh). |
1057 | 221 |
|
222 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
14896 | 223 |
Iterate over a copy to do this." |
1 | 224 |
|
54 | 225 |
|n| |
226 |
||
1145
a094d90e11bf
dont use [0] blocks - use 0 constant instead
Claus Gittinger <cg@exept.de>
parents:
1110
diff
changeset
|
227 |
n := contents at:newObject ifAbsent:0. |
54 | 228 |
contents at:newObject put:(n + 1). |
229 |
^ newObject |
|
1057 | 230 |
|
231 |
"Modified: 1.3.1996 / 21:43:06 / cg" |
|
1 | 232 |
! |
233 |
||
1372
d7bd1b463a65
oops - typo; occurrences has two r's
Claus Gittinger <cg@exept.de>
parents:
1290
diff
changeset
|
234 |
add:newObject withOccurrences:anInteger |
345 | 235 |
"add the argument, anObject anInteger times to the receiver. |
1057 | 236 |
Returns the object. |
237 |
||
238 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
8873 | 239 |
Iterate over a copy to do this." |
1 | 240 |
|
54 | 241 |
|n| |
242 |
||
1145
a094d90e11bf
dont use [0] blocks - use 0 constant instead
Claus Gittinger <cg@exept.de>
parents:
1110
diff
changeset
|
243 |
n := contents at:newObject ifAbsent:0. |
54 | 244 |
contents at:newObject put:(n + anInteger). |
1 | 245 |
^ newObject |
1057 | 246 |
|
247 |
"Modified: 1.3.1996 / 21:43:12 / cg" |
|
1372
d7bd1b463a65
oops - typo; occurrences has two r's
Claus Gittinger <cg@exept.de>
parents:
1290
diff
changeset
|
248 |
"Created: 11.5.1996 / 12:13:43 / cg" |
1 | 249 |
! |
250 |
||
251 |
remove:oldObject ifAbsent:anExceptionBlock |
|
19081 | 252 |
"Remove one occurrence of oldObject from the collection. |
345 | 253 |
If it was not present, return the value of the exceptionBlock; |
1057 | 254 |
otherwise return the removed object. |
255 |
||
256 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
19081 | 257 |
Iterate over a copy to do this." |
1 | 258 |
|
259 |
|count| |
|
260 |
||
1145
a094d90e11bf
dont use [0] blocks - use 0 constant instead
Claus Gittinger <cg@exept.de>
parents:
1110
diff
changeset
|
261 |
count := contents at:oldObject ifAbsent:0. |
1 | 262 |
(count == 0) ifTrue:[^ anExceptionBlock value]. |
263 |
(count == 1) ifTrue:[ |
|
19081 | 264 |
contents removeKey:oldObject |
8873 | 265 |
] ifFalse:[ |
19081 | 266 |
contents at:oldObject put:(count - 1) |
1 | 267 |
]. |
268 |
^ oldObject |
|
1057 | 269 |
|
270 |
"Modified: 1.3.1996 / 21:43:18 / cg" |
|
345 | 271 |
! |
272 |
||
1110 | 273 |
removeAll |
1164 | 274 |
"remove all objects from the receiver collection (i.e. make it empty). |
275 |
Returns the receiver." |
|
1110 | 276 |
|
277 |
contents := contents species new. |
|
278 |
||
279 |
" |
|
280 |
|b| |
|
281 |
||
282 |
b := Bag new. |
|
283 |
b add:1; add:2; add:3; add:2; add:1. |
|
1422 | 284 |
Transcript showCR:b. |
1110 | 285 |
|
286 |
b removeAll. |
|
287 |
||
1422 | 288 |
Transcript showCR:b |
1110 | 289 |
" |
290 |
||
1164 | 291 |
"Modified: 12.4.1996 / 13:34:34 / cg" |
1110 | 292 |
! |
293 |
||
345 | 294 |
removeAllOccurrencesOf:oldObject ifAbsent:anExceptionBlock |
295 |
"Remove all occurrences of oldObject from the collection. |
|
296 |
If it was not present, return the value of the exceptionBlock; |
|
1057 | 297 |
otherwise return the number of removes. |
298 |
||
299 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
8873 | 300 |
Iterate over a copy to do this." |
345 | 301 |
|
302 |
|count| |
|
303 |
||
1145
a094d90e11bf
dont use [0] blocks - use 0 constant instead
Claus Gittinger <cg@exept.de>
parents:
1110
diff
changeset
|
304 |
count := contents at:oldObject ifAbsent:0. |
345 | 305 |
(count == 0) ifTrue:[^ anExceptionBlock value]. |
306 |
contents removeKey:oldObject. |
|
307 |
^ oldObject |
|
1057 | 308 |
|
309 |
"Modified: 1.3.1996 / 21:43:26 / cg" |
|
1 | 310 |
! ! |
311 |
||
8860 | 312 |
!Bag methodsFor:'bulk operations'! |
313 |
||
314 |
sum |
|
11522 | 315 |
"sum up all elements; return 0 for an empty collection. |
316 |
can be done easier, using bags knowledge." |
|
8860 | 317 |
|
318 |
|accu| |
|
319 |
||
11522 | 320 |
self isEmpty ifTrue:[ ^ 0 ]. |
11474 | 321 |
|
322 |
accu := nil. |
|
323 |
self |
|
324 |
valuesAndCountsDo:[:n :count | |
|
325 |
|thisAmount| |
|
326 |
||
327 |
thisAmount := count * n. |
|
328 |
accu := (accu isNil ifTrue:[thisAmount] ifFalse:[accu + thisAmount]) ]. |
|
8860 | 329 |
^ accu |
330 |
||
331 |
" |
|
11474 | 332 |
TestCase assert:((Bag new add:1; add:2; add:3; add:1; add:2; add:1; yourself) sum = 10). |
8860 | 333 |
" |
334 |
! ! |
|
335 |
||
6735
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
336 |
!Bag methodsFor:'comparing'! |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
337 |
|
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
338 |
= aBag |
11935 | 339 |
"Compare the receiver with the argument and return true if the |
340 |
receiver is equal to the argument (i.e. has the same size and elements). |
|
341 |
Otherwise return false." |
|
342 |
||
6735
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
343 |
aBag species == self species ifFalse:[^ false]. |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
344 |
self size == aBag size ifFalse:[^ false]. |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
345 |
self valuesAndCountsDo:[:val :cnt | |
11935 | 346 |
(aBag occurrencesOf:val) == cnt ifFalse:[^ false] |
6735
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
347 |
]. |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
348 |
^ true |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
349 |
! |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
350 |
|
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
351 |
hash |
11935 | 352 |
"return an integer useful for hashing on the receiver; |
353 |
redefined since = is redefined here." |
|
354 |
||
6735
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
355 |
|h| |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
356 |
|
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
357 |
h := self size. |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
358 |
self valuesAndCountsDo:[:val :cnt | |
11935 | 359 |
h := h + cnt hash. |
6735
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
360 |
]. |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
361 |
^ h |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
362 |
! ! |
fad09454a025
added #= and #hash (to put bags into Sets/Dictionaries)
Claus Gittinger <cg@exept.de>
parents:
6411
diff
changeset
|
363 |
|
609 | 364 |
!Bag methodsFor:'converting'! |
365 |
||
366 |
asBag |
|
367 |
"return the receiver as a bag" |
|
368 |
||
369 |
"could be an instance of a subclass..." |
|
370 |
self class == Bag ifTrue:[ |
|
371 |
^ self |
|
372 |
]. |
|
373 |
^ super asBag |
|
7161 | 374 |
! |
375 |
||
376 |
asSet |
|
377 |
"return the receiver as a set" |
|
378 |
||
379 |
^ contents keys copy |
|
380 |
||
381 |
" |
|
382 |
|b| |
|
383 |
||
384 |
b := Bag new. |
|
385 |
b add:1; add:2; add:3; add:1; add:1. |
|
386 |
b asSet. |
|
387 |
" |
|
609 | 388 |
! ! |
389 |
||
24181 | 390 |
!Bag methodsFor:'copying-private'! |
609 | 391 |
|
392 |
postCopy |
|
393 |
"must copy the contents as well" |
|
394 |
||
395 |
contents := contents copy |
|
396 |
! ! |
|
397 |
||
1 | 398 |
!Bag methodsFor:'enumerating'! |
399 |
||
400 |
do:aBlock |
|
1057 | 401 |
"evaluate the block for all elements in the collection. |
402 |
||
403 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
8873 | 404 |
Iterate over a copy to do this." |
1 | 405 |
|
54 | 406 |
contents keysAndValuesDo:[:key :value| |
8873 | 407 |
value timesRepeat:[ |
408 |
aBlock value:key |
|
409 |
] |
|
1 | 410 |
] |
1057 | 411 |
|
412 |
"Modified: 1.3.1996 / 21:42:39 / cg" |
|
345 | 413 |
! |
414 |
||
16779 | 415 |
keysAndValuesDo:aTwoArgBlock |
416 |
"evaluate the block for all distinct elements in the collection, |
|
417 |
passing both the element and the occurrence count as arguments. |
|
418 |
||
419 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
420 |
Iterate over a copy to do this." |
|
421 |
||
24621 | 422 |
contents keysAndValuesDo:aTwoArgBlock |
16779 | 423 |
! |
424 |
||
10835 | 425 |
valuesAndCounts |
11481 | 426 |
"return an orderedCollection containing value->count associations" |
10835 | 427 |
|
428 |
|coll| |
|
429 |
||
430 |
coll := OrderedCollection new. |
|
431 |
self valuesAndCountsDo:[:value :count | coll add:(value->count)]. |
|
432 |
^ coll |
|
433 |
||
434 |
"Modified: 1.3.1996 / 21:42:44 / cg" |
|
435 |
! |
|
436 |
||
24668 | 437 |
valuesAndCountsDetect:aTwoArgBlock ifNone:exceptionValue |
438 |
"evaluate the block for all distinct elements in the collection, |
|
439 |
passing both the element and the occurrence count as arguments. |
|
440 |
If any returns true, return an association consisting of value and occurrence count. |
|
441 |
If not, return the value from exceptionValue. |
|
442 |
||
443 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
444 |
Iterate over a copy to do this." |
|
445 |
||
446 |
|collected| |
|
447 |
||
448 |
collected := OrderedCollection new. |
|
449 |
self valuesAndCountsDo:[:eachValue :eachCount| |
|
450 |
(aTwoArgBlock value:eachValue value:eachCount) ifTrue:[ |
|
451 |
^ eachValue -> eachCount |
|
452 |
]. |
|
453 |
]. |
|
454 |
^ exceptionValue value |
|
455 |
||
456 |
" |
|
457 |
#(10 20 20 30 40) asBag |
|
458 |
valuesAndCountsDetect:[:eachValue :eachCount | eachCount > 1] |
|
459 |
ifNone:nil |
|
460 |
||
461 |
#(10 20 20 30 40) asBag |
|
462 |
valuesAndCountsDetect:[:eachValue :eachCount | eachCount > 3] |
|
463 |
ifNone:nil |
|
464 |
" |
|
465 |
! |
|
466 |
||
345 | 467 |
valuesAndCountsDo:aTwoArgBlock |
468 |
"evaluate the block for all distinct elements in the collection, |
|
8873 | 469 |
passing both the element and the occurrence count as arguments. |
1057 | 470 |
|
471 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
24621 | 472 |
Iterate over a copy to do this." |
345 | 473 |
|
24621 | 474 |
contents keysAndValuesDo:aTwoArgBlock |
1057 | 475 |
|
476 |
"Modified: 1.3.1996 / 21:42:44 / cg" |
|
20324 | 477 |
! |
478 |
||
479 |
valuesAndCountsSelect:aTwoArgBlock |
|
480 |
"evaluate the block for all distinct elements in the collection, |
|
481 |
passing both the element and the occurrence count as arguments. |
|
482 |
If that returns true, add the element to the OrderedCollection. |
|
483 |
Answer the OrderedCollection. |
|
484 |
||
485 |
WARNING: do not add/remove elements while iterating over the receiver. |
|
486 |
Iterate over a copy to do this." |
|
487 |
||
488 |
|collected| |
|
489 |
||
490 |
collected := OrderedCollection new. |
|
491 |
self valuesAndCountsDo:[:eachValue :eachCount| |
|
492 |
(aTwoArgBlock value:eachValue value:eachCount) ifTrue:[ |
|
493 |
collected add:eachValue |
|
494 |
]. |
|
495 |
]. |
|
496 |
^ collected |
|
497 |
||
498 |
" |
|
499 |
#(10 20 20 30 40) asBag |
|
500 |
valuesAndCountsSelect:[:eachValue :eachCount | eachCount > 1] |
|
501 |
" |
|
502 |
||
503 |
||
504 |
"Modified: 1.3.1996 / 21:42:44 / cg" |
|
1 | 505 |
! ! |
609 | 506 |
|
16766 | 507 |
|
12823 | 508 |
!Bag methodsFor:'printing & storing'! |
509 |
||
510 |
printElementsDo:aBlock |
|
14685 | 511 |
self valuesAndCountsDo:[:value :count| |
512 |
aBlock value:('%1(*%2)' bindWith:value with:count). |
|
12823 | 513 |
] |
514 |
! ! |
|
515 |
||
609 | 516 |
!Bag methodsFor:'private'! |
517 |
||
16888 | 518 |
grow:newSize |
519 |
"/ ignored here |
|
520 |
! |
|
521 |
||
609 | 522 |
initContents |
14956 | 523 |
"set the contents to be an empty Dictionary. |
524 |
This is the default method for initialization, which can be redefined in subclasses." |
|
525 |
||
526 |
contents := self class contentsClass new |
|
527 |
! |
|
528 |
||
529 |
initContents:size |
|
530 |
"set the contents to be an empty Dictionary with initial size. |
|
531 |
This is the default method for initialization, which can be redefined in subclasses." |
|
532 |
||
533 |
contents := self class contentsClass new: size |
|
534 |
! |
|
535 |
||
536 |
initContentsForEquality |
|
609 | 537 |
"set the contents to be an empty Dictionary" |
538 |
||
539 |
contents := Dictionary new |
|
540 |
! |
|
541 |
||
14956 | 542 |
initContentsForEquality:size |
609 | 543 |
"set the contents to be an empty Dictionary with initial size" |
544 |
||
545 |
contents := Dictionary new:size |
|
546 |
! |
|
547 |
||
5375 | 548 |
initContentsForIdentity |
549 |
"set the contents to be an empty IdentityDictionary" |
|
550 |
||
551 |
contents := IdentityDictionary new |
|
552 |
! |
|
553 |
||
609 | 554 |
initContentsForIdentity:size |
555 |
"set the contents to be an empty IdentityDictionary with initial size" |
|
556 |
||
557 |
contents := IdentityDictionary new:size |
|
558 |
! ! |
|
559 |
||
5557 | 560 |
!Bag methodsFor:'queries'! |
561 |
||
23699 | 562 |
includes:anObject |
563 |
"return true, if anObject is in the receiver" |
|
564 |
||
565 |
^ (self occurrencesOf:anObject) > 0 |
|
566 |
! |
|
567 |
||
568 |
occurrencesOf:anObject |
|
569 |
"return how many times anObject is in the receiver" |
|
570 |
||
571 |
^ contents at:anObject ifAbsent:0 |
|
572 |
! |
|
573 |
||
5557 | 574 |
size |
575 |
"return the number of bag elements" |
|
576 |
||
577 |
|count| |
|
578 |
||
579 |
count := 0. |
|
580 |
contents do:[:element | count := count + element]. |
|
581 |
^ count |
|
582 |
! ! |
|
583 |
||
15457 | 584 |
!Bag methodsFor:'statistical functions'! |
585 |
||
586 |
variance |
|
587 |
"compute the variance over a complete data set (and not of a sample)" |
|
588 |
||
589 |
|m sz sumDeltaSquares| |
|
590 |
||
591 |
m := self arithmeticMean. |
|
592 |
sumDeltaSquares := 0. |
|
593 |
sz := 0. |
|
594 |
self |
|
595 |
valuesAndCountsDo:[:val :count | |
|
596 |
sumDeltaSquares := sumDeltaSquares + ((val - m) squared). |
|
597 |
sz := sz + 1. |
|
598 |
]. |
|
599 |
||
600 |
^ sumDeltaSquares / sz |
|
601 |
||
602 |
" |
|
603 |
TestCase assert:( #(1 1 1 2 2 2 1 1 1 2 2 2) asBag variance = #(1 1 1 2 2 2 1 1 1 2 2 2) variance). |
|
604 |
TestCase assert:( #(1 1 1 1 1 0 0 0 0 0) asBag variance = #(1 1 1 1 1 0 0 0 0 0) variance). |
|
605 |
" |
|
606 |
! ! |
|
607 |
||
609 | 608 |
!Bag methodsFor:'testing'! |
609 |
||
15429 | 610 |
isFixedSize |
611 |
"return true if the receiver cannot grow" |
|
612 |
||
613 |
^ false |
|
614 |
! |
|
615 |
||
18468 | 616 |
isOrdered |
617 |
"return true, if the receiver's elements are ordered. |
|
618 |
Redefined to return false here, because the order of keys and values |
|
619 |
may change due to rehashing, when elements are added/removed" |
|
620 |
||
621 |
^ false |
|
609 | 622 |
! ! |
623 |
||
633 | 624 |
!Bag class methodsFor:'documentation'! |
625 |
||
626 |
version |
|
19081 | 627 |
^ '$Header$' |
12823 | 628 |
! |
629 |
||
630 |
version_CVS |
|
19081 | 631 |
^ '$Header$' |
633 | 632 |
! ! |
14685 | 633 |