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