author | Claus Gittinger <cg@exept.de> |
Sat, 11 Nov 1995 15:28:26 +0100 | |
changeset 528 | a083413dfbe8 |
parent 399 | c15cfaf3ed4d |
child 609 | 12be97f6d5a7 |
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 |
" |
|
12 |
||
13 |
Collection subclass:#Bag |
|
14 |
instanceVariableNames:'contents' |
|
15 |
classVariableNames:'' |
|
16 |
poolDictionaries:'' |
|
17 |
category:'Collections-Unordered' |
|
18 |
! |
|
19 |
||
54 | 20 |
!Bag class methodsFor:'documentation'! |
21 |
||
88 | 22 |
copyright |
23 |
" |
|
24 |
COPYRIGHT (c) 1991 by Claus Gittinger |
|
345 | 25 |
All Rights Reserved |
88 | 26 |
|
27 |
This software is furnished under a license and may be used |
|
28 |
only in accordance with the terms of that license and with the |
|
29 |
inclusion of the above copyright notice. This software may not |
|
30 |
be provided or otherwise made available to, or used by, any |
|
31 |
other person. No title to or ownership of the software is |
|
32 |
hereby transferred. |
|
33 |
" |
|
34 |
! |
|
35 |
||
36 |
version |
|
528
a083413dfbe8
converted version methods from comment-only to returning-a-string
Claus Gittinger <cg@exept.de>
parents:
399
diff
changeset
|
37 |
^ '$Header: /cvs/stx/stx/libbasic/Bag.st,v 1.14 1995-11-11 14:26:49 cg Exp $' |
88 | 38 |
! |
39 |
||
54 | 40 |
documentation |
41 |
" |
|
88 | 42 |
Bag implements collections whose elements are unordered and have no |
154 | 43 |
external key. Elements may occur more than once in a bag. There is no defined |
44 |
order within a bag. |
|
345 | 45 |
The default implementation uses a dictionary to store each objects occurence |
46 |
count, using the object itself as key (i.e. using = and hash for inclusion |
|
47 |
tests). |
|
399 | 48 |
|
345 | 49 |
There is also an instance creation variant (#identityNew:) creating a |
50 |
bag which compares using #== and hashes using #identityHash. |
|
399 | 51 |
(I'd say that an IdentityBag was a better thing to implement ... |
52 |
... but for compatibility ... we do it here as well) |
|
1 | 53 |
|
88 | 54 |
Instance variables: |
1 | 55 |
|
345 | 56 |
contents <Dictionary> for each element, the number of occurrences |
54 | 57 |
" |
58 |
! ! |
|
1 | 59 |
|
60 |
!Bag class methodsFor:'instance creation'! |
|
61 |
||
62 |
new |
|
345 | 63 |
"return a new empty Bag which compares for equality (i.e. not identity)" |
1 | 64 |
|
65 |
^ super new initContents |
|
66 |
! |
|
67 |
||
68 |
new:size |
|
345 | 69 |
"return a new empty Bag with initial space for size elements. |
70 |
Elements will be compared using equality compare (i.e. #= not #== identity)." |
|
71 |
||
72 |
^ self equalityNew:size |
|
73 |
! |
|
74 |
||
75 |
equalityNew:size |
|
76 |
"return a new empty Bag with initial space for size elements. |
|
77 |
Elements will be compared using equality compare (i.e. #= not #== identity)." |
|
1 | 78 |
|
79 |
^ super new initContents:size |
|
345 | 80 |
! |
81 |
||
82 |
identityNew:size |
|
83 |
"return a new empty Bag with initial space for size elements. |
|
84 |
Elements will be compared using identity compare (i.e. #== not #= equality)." |
|
85 |
||
86 |
^ super new initContentsForIdentity:size |
|
1 | 87 |
! ! |
88 |
||
89 |
!Bag methodsFor:'private'! |
|
90 |
||
91 |
initContents |
|
92 |
"set the contents to be an empty Dictionary" |
|
93 |
||
94 |
contents := Dictionary new |
|
95 |
! |
|
96 |
||
97 |
initContents:size |
|
98 |
"set the contents to be an empty Dictionary with initial size" |
|
99 |
||
100 |
contents := Dictionary new:size |
|
345 | 101 |
! |
102 |
||
103 |
initContentsForIdentity:size |
|
104 |
"set the contents to be an empty IdentityDictionary with initial size" |
|
105 |
||
106 |
contents := IdentityDictionary new:size |
|
1 | 107 |
! ! |
108 |
||
109 |
!Bag methodsFor:'accessing'! |
|
110 |
||
111 |
at:index |
|
112 |
"report an error: at: is not allowed for Bags" |
|
113 |
||
114 |
^ self errorNotKeyed |
|
115 |
! |
|
116 |
||
117 |
at:index put:anObject |
|
118 |
"report an error: at:put: is not allowed for Bags" |
|
119 |
||
120 |
^ self errorNotKeyed |
|
345 | 121 |
! |
122 |
||
123 |
contents |
|
124 |
"return the dictionary which associates occurrence-counts |
|
125 |
to the bags elements." |
|
126 |
||
127 |
^ contents |
|
1 | 128 |
! ! |
129 |
||
130 |
!Bag methodsFor:'testing'! |
|
131 |
||
132 |
size |
|
133 |
"return the number of bag elements" |
|
134 |
||
135 |
|count| |
|
136 |
||
137 |
count := 0. |
|
138 |
contents do:[:element | count := count + element]. |
|
139 |
^ count |
|
140 |
! |
|
141 |
||
142 |
occurrencesOf:anObject |
|
143 |
"return how many times anObject is in the receiver" |
|
144 |
||
145 |
^ contents at:anObject ifAbsent:[0] |
|
146 |
! |
|
147 |
||
148 |
includes:anObject |
|
149 |
"return true, if anObject is in the receiver" |
|
150 |
||
151 |
^ contents includesKey:anObject |
|
152 |
! ! |
|
153 |
||
154 | 154 |
!Bag methodsFor:'copying'! |
155 |
||
156 |
postCopy |
|
157 |
"must copy the contents as well" |
|
158 |
||
159 |
contents := contents copy |
|
160 |
! ! |
|
161 |
||
11 | 162 |
!Bag methodsFor:'converting'! |
163 |
||
164 |
asBag |
|
165 |
"return the receiver as a bag" |
|
166 |
||
167 |
"could be an instance of a subclass..." |
|
168 |
self class == Bag ifTrue:[ |
|
345 | 169 |
^ self |
11 | 170 |
]. |
171 |
^ super asBag |
|
172 |
! ! |
|
173 |
||
1 | 174 |
!Bag methodsFor:'adding & removing'! |
175 |
||
54 | 176 |
add:newObject |
345 | 177 |
"add the argument, anObject to the receiver. |
178 |
Returns the object." |
|
1 | 179 |
|
54 | 180 |
|n| |
181 |
||
182 |
n := contents at:newObject ifAbsent:[0]. |
|
183 |
contents at:newObject put:(n + 1). |
|
184 |
^ newObject |
|
1 | 185 |
! |
186 |
||
187 |
add:newObject withOccurences:anInteger |
|
345 | 188 |
"add the argument, anObject anInteger times to the receiver. |
189 |
Returns the object." |
|
1 | 190 |
|
54 | 191 |
|n| |
192 |
||
193 |
n := contents at:newObject ifAbsent:[0]. |
|
194 |
contents at:newObject put:(n + anInteger). |
|
1 | 195 |
^ newObject |
196 |
! |
|
197 |
||
198 |
remove:oldObject ifAbsent:anExceptionBlock |
|
345 | 199 |
"Remove oldObject from the collection. |
200 |
If it was not present, return the value of the exceptionBlock; |
|
201 |
otherwise return the removed object." |
|
1 | 202 |
|
203 |
|count| |
|
204 |
||
54 | 205 |
count := contents at:oldObject ifAbsent:[0]. |
1 | 206 |
(count == 0) ifTrue:[^ anExceptionBlock value]. |
207 |
(count == 1) ifTrue:[ |
|
345 | 208 |
contents removeKey:oldObject |
1 | 209 |
] ifFalse:[ |
345 | 210 |
contents at:oldObject put:(count - 1) |
1 | 211 |
]. |
212 |
^ oldObject |
|
345 | 213 |
! |
214 |
||
215 |
removeAllOccurrencesOf:oldObject ifAbsent:anExceptionBlock |
|
216 |
"Remove all occurrences of oldObject from the collection. |
|
217 |
If it was not present, return the value of the exceptionBlock; |
|
218 |
otherwise return the number of removes." |
|
219 |
||
220 |
|count| |
|
221 |
||
222 |
count := contents at:oldObject ifAbsent:[0]. |
|
223 |
(count == 0) ifTrue:[^ anExceptionBlock value]. |
|
224 |
contents removeKey:oldObject. |
|
225 |
^ oldObject |
|
1 | 226 |
! ! |
227 |
||
228 |
!Bag methodsFor:'enumerating'! |
|
229 |
||
230 |
do:aBlock |
|
345 | 231 |
"evaluate the block for all elements in the collection." |
1 | 232 |
|
54 | 233 |
contents keysAndValuesDo:[:key :value| |
345 | 234 |
value timesRepeat:[ |
235 |
aBlock value:key |
|
236 |
] |
|
1 | 237 |
] |
345 | 238 |
! |
239 |
||
240 |
valuesAndCountsDo:aTwoArgBlock |
|
241 |
"evaluate the block for all distinct elements in the collection, |
|
242 |
passing both the element and the occurence count as arguments." |
|
243 |
||
244 |
^ contents keysAndValuesDo:aTwoArgBlock |
|
1 | 245 |
! ! |