1
|
1 |
"
|
5
|
2 |
COPYRIGHT (c) 1991 by Claus Gittinger
|
155
|
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 |
|
12
|
13 |
Set subclass:#Dictionary
|
155
|
14 |
instanceVariableNames:'valueArray'
|
|
15 |
classVariableNames:''
|
|
16 |
poolDictionaries:''
|
|
17 |
category:'Collections-Unordered'
|
1
|
18 |
!
|
|
19 |
|
|
20 |
Dictionary comment:'
|
5
|
21 |
COPYRIGHT (c) 1991 by Claus Gittinger
|
155
|
22 |
All Rights Reserved
|
92
|
23 |
|
345
|
24 |
$Header: /cvs/stx/stx/libbasic/Attic/Dict.st,v 1.20 1995-05-16 17:06:43 claus Exp $
|
1
|
25 |
'!
|
|
26 |
|
68
|
27 |
!Dictionary class methodsFor:'documentation'!
|
|
28 |
|
88
|
29 |
copyright
|
|
30 |
"
|
|
31 |
COPYRIGHT (c) 1991 by Claus Gittinger
|
155
|
32 |
All Rights Reserved
|
88
|
33 |
|
|
34 |
This software is furnished under a license and may be used
|
|
35 |
only in accordance with the terms of that license and with the
|
|
36 |
inclusion of the above copyright notice. This software may not
|
|
37 |
be provided or otherwise made available to, or used by, any
|
|
38 |
other person. No title to or ownership of the software is
|
|
39 |
hereby transferred.
|
|
40 |
"
|
|
41 |
!
|
|
42 |
|
|
43 |
version
|
|
44 |
"
|
345
|
45 |
$Header: /cvs/stx/stx/libbasic/Attic/Dict.st,v 1.20 1995-05-16 17:06:43 claus Exp $
|
88
|
46 |
"
|
|
47 |
!
|
|
48 |
|
68
|
49 |
documentation
|
|
50 |
"
|
|
51 |
a Dictionary is (conceptionally) a set of Associations storing key-value pairs.
|
|
52 |
(The implementation uses two arrays to store the keys and values separately.)
|
|
53 |
Searching for an element is done using a hash into the key array.
|
345
|
54 |
Another wau of looking at a dictionary is as a array which uses
|
|
55 |
arbitrary access keys (i.e. not just integers as arrays do).
|
|
56 |
|
|
57 |
Since the keys are unordered, no internal element order is defined
|
|
58 |
(i.e. enumerating them may return element in any order - even changing
|
|
59 |
over time).
|
|
60 |
|
68
|
61 |
Many methods for searching and hashing are inherited from Set.
|
92
|
62 |
|
|
63 |
Instance variables:
|
345
|
64 |
|
155
|
65 |
keyArray <Array> (from Set) the keys
|
|
66 |
valueArray <Array> the values ('valueArray at:index' corresponds
|
|
67 |
to the value stored under 'keyArray at:index')
|
92
|
68 |
|
345
|
69 |
Performance hints:
|
92
|
70 |
since the dictionary does not store associations internally,
|
345
|
71 |
it is less efficient, to store/retrieve associations, because these
|
|
72 |
are created temporarily in some methods.
|
|
73 |
I.e. 'at:key put:value' is faster than 'add:anAssoc'
|
|
74 |
and 'keysAndValuesDo:' is faster than 'associationsDo:' etc.
|
92
|
75 |
|
|
76 |
If symbols or integers are used as keys, use IdentityDictionaries for slightly
|
|
77 |
more performance, since both hashing and comparison is faster.
|
345
|
78 |
|
|
79 |
If you have a rough idea how big the dictionary is going to grow,
|
|
80 |
create it using #new: instead of #new. Even if the size given is a
|
|
81 |
poor guess (say half of the real size), there is some 20-30% performance
|
|
82 |
win to expect, since many resizing operations are avoided when associations
|
|
83 |
are added.
|
68
|
84 |
"
|
|
85 |
! !
|
|
86 |
|
345
|
87 |
!Dictionary class methodsFor:'instance creation'!
|
|
88 |
|
|
89 |
withKeysAndValues:anArray
|
|
90 |
"return a new instance where keys and values are taken from alternating
|
|
91 |
elements of anArray"
|
|
92 |
|
|
93 |
|newDict sz "{ Class: SmallInteger }"|
|
|
94 |
|
|
95 |
sz := anArray size.
|
|
96 |
newDict := self new:(sz // 2).
|
|
97 |
1 to:sz by:2 do:[:i |
|
|
98 |
newDict at:(anArray at:i) put:(anArray at:i+1)
|
|
99 |
].
|
|
100 |
^ newDict
|
|
101 |
|
|
102 |
"
|
|
103 |
Dictionary withKeysAndValues:#('one' 1 'two' 2 'three' 3 'four' 4)
|
|
104 |
"
|
|
105 |
! !
|
|
106 |
|
282
|
107 |
!Dictionary methodsFor:'inspecting'!
|
|
108 |
|
|
109 |
inspectorClass
|
|
110 |
"redefined to use DictionaryInspector
|
|
111 |
(instead of the default Inspector)."
|
|
112 |
|
|
113 |
^ DictionaryInspectorView
|
|
114 |
! !
|
|
115 |
|
1
|
116 |
!Dictionary methodsFor:'testing'!
|
|
117 |
|
|
118 |
includesKey:aKey
|
|
119 |
"return true, if the argument, aKey is a key in the receiver"
|
|
120 |
|
12
|
121 |
^ (self find:aKey ifAbsent:[0]) ~~ 0
|
1
|
122 |
!
|
|
123 |
|
54
|
124 |
includesValue:aValue
|
|
125 |
"return true, if the argument, aValue is stored in the dictionary,
|
|
126 |
i.e. if there is an associaten, with aValue as value.
|
|
127 |
This is a slow search, since there is no fast reverse mapping;
|
68
|
128 |
the values have to be all scanned without any hashing.
|
|
129 |
You need a special collection (or two Dictionaries) to get this
|
|
130 |
reverse mapping fast."
|
1
|
131 |
|
12
|
132 |
^ valueArray includes:aValue
|
54
|
133 |
!
|
|
134 |
|
345
|
135 |
includes:anObject
|
|
136 |
"/ OLD:
|
|
137 |
"/ "return true, if there is an association in the receiver with the
|
|
138 |
"/ same key as the argument, anObject.
|
|
139 |
"/ NOTICE: in contrast to #includesAssociation:, this compares only the key."
|
|
140 |
"/
|
|
141 |
"/ ^ self includesKey:(anObject key)
|
54
|
142 |
|
345
|
143 |
"/ NEW:
|
|
144 |
"return true, if the argument, aValue is stored in the dictionary,
|
|
145 |
i.e. if there is an associaten, with aValue as value.
|
|
146 |
This is a slow search, since there is no fast reverse mapping;
|
|
147 |
the values have to be all scanned without any hashing.
|
|
148 |
You need a special collection (or two Dictionaries) to get this
|
|
149 |
reverse mapping fast."
|
|
150 |
|
|
151 |
^ self includesValue:anObject
|
68
|
152 |
!
|
|
153 |
|
|
154 |
includesAssociation:anAssociation
|
|
155 |
"return true, if there is an association in the receiver with the
|
|
156 |
same key and value as the argument, anAssociation.
|
|
157 |
NOTICE: in contrast to #includes:, this compares both key and value."
|
|
158 |
|
345
|
159 |
|val|
|
|
160 |
|
|
161 |
val := self at:(anAssociation key) ifAbsent:[^ false].
|
|
162 |
^ (self compareSame:val with:anAssociation) value
|
|
163 |
!
|
|
164 |
|
|
165 |
occurrencesOf:anObject
|
|
166 |
"count & return how often anObject is stored in the dictionary.
|
|
167 |
This counts values - not keys."
|
|
168 |
|
|
169 |
^ valueArray occurrencesOf:anObject
|
1
|
170 |
! !
|
|
171 |
|
|
172 |
!Dictionary methodsFor:'accessing'!
|
|
173 |
|
|
174 |
at:aKey
|
|
175 |
"return the element indexed by aKey - report an error if none found"
|
|
176 |
|
|
177 |
|index|
|
|
178 |
|
|
179 |
aKey isNil ifTrue:[
|
155
|
180 |
"nil is not allowed as key"
|
345
|
181 |
^ self errorInvalidKey:aKey
|
155
|
182 |
].
|
|
183 |
"
|
|
184 |
I could have written:
|
345
|
185 |
index := self find:aKey ifAbsent:[^ self errorKeyNotFound:aKey]
|
155
|
186 |
but the code below is slighlty more efficient, since it avoids
|
|
187 |
a block creation ([0] is very cheap) - thus speeding up the good case.
|
|
188 |
"
|
|
189 |
index := self find:aKey ifAbsent:[0].
|
|
190 |
index == 0 ifTrue:[
|
|
191 |
"no such key"
|
345
|
192 |
^ self errorKeyNotFound:aKey
|
155
|
193 |
].
|
|
194 |
^ valueArray basicAt:index
|
1
|
195 |
!
|
|
196 |
|
|
197 |
at:aKey ifAbsent:exceptionBlock
|
2
|
198 |
"return the element indexed by aKey -
|
68
|
199 |
return result of exceptionBlock if no element is stored under aKey"
|
2
|
200 |
|
1
|
201 |
|index|
|
|
202 |
|
|
203 |
aKey isNil ifTrue:[
|
155
|
204 |
"nil is not allowed as key"
|
|
205 |
^ self errorInvalidKey
|
|
206 |
].
|
|
207 |
"
|
|
208 |
I could have written:
|
|
209 |
index := self find:aKey ifAbsent:[^ exceptionBlock value]
|
|
210 |
but the code below is slighlty more efficient, since it avoids
|
|
211 |
a block creation ([0] is very cheap) - thus speeding up the good case.
|
|
212 |
"
|
|
213 |
index := self find:aKey ifAbsent:[0].
|
|
214 |
index == 0 ifTrue:[^ exceptionBlock value].
|
|
215 |
^ valueArray basicAt:index
|
1
|
216 |
!
|
|
217 |
|
2
|
218 |
associationAt:aKey
|
|
219 |
"return an association consisting of aKey and the element indexed
|
|
220 |
by aKey -
|
|
221 |
report an error, if no element is stored under aKey"
|
|
222 |
|
|
223 |
^ aKey -> (self at:aKey)
|
|
224 |
!
|
|
225 |
|
68
|
226 |
associationAt:aKey ifAbsent:exceptionBlock
|
|
227 |
"return an association consisting of aKey and the element indexed by aKey -
|
|
228 |
return result of exceptionBlock if no element is stored under aKey"
|
|
229 |
|
|
230 |
^ aKey -> (self at:aKey ifAbsent:[^ exceptionBlock value])
|
|
231 |
!
|
|
232 |
|
1
|
233 |
at:aKey put:anObject
|
|
234 |
"add the argument anObject under key, aKey to the receiver"
|
|
235 |
|
77
|
236 |
|index|
|
1
|
237 |
|
|
238 |
aKey isNil ifTrue:[
|
155
|
239 |
"nil is not allowed as key"
|
|
240 |
self errorInvalidKey
|
1
|
241 |
] ifFalse:[
|
155
|
242 |
index := self findKeyOrNil:aKey.
|
|
243 |
(valueArray basicAt:index) notNil ifTrue:[
|
|
244 |
valueArray basicAt:index put:anObject.
|
|
245 |
^ anObject
|
|
246 |
].
|
|
247 |
keyArray basicAt:index put:aKey.
|
|
248 |
valueArray basicAt:index put:anObject.
|
|
249 |
tally := tally + 1.
|
1
|
250 |
|
155
|
251 |
self fullCheck.
|
1
|
252 |
|
155
|
253 |
^ anObject
|
1
|
254 |
]
|
|
255 |
!
|
|
256 |
|
|
257 |
keys
|
|
258 |
"return a collection containing all keys of the receiver"
|
|
259 |
|
77
|
260 |
|keySet|
|
|
261 |
|
|
262 |
keySet := self emptyCollectionForKeys.
|
|
263 |
keyArray do:[:key |
|
155
|
264 |
(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
|
|
265 |
keySet add:key
|
|
266 |
]
|
77
|
267 |
].
|
|
268 |
^ keySet
|
10
|
269 |
!
|
|
270 |
|
54
|
271 |
values
|
92
|
272 |
"return a collection containing all values of the receiver"
|
54
|
273 |
|
92
|
274 |
"old:
|
|
275 |
kk: this fails if the receiver contains nils
|
54
|
276 |
^ valueArray asBag
|
92
|
277 |
new:
|
|
278 |
"
|
|
279 |
|aCollection|
|
|
280 |
aCollection := OrderedCollection new:valueArray size..
|
|
281 |
self do:[:value| aCollection add:value].
|
|
282 |
^ aCollection
|
54
|
283 |
!
|
|
284 |
|
|
285 |
associations
|
|
286 |
"return an ordered collection containing the receivers associations."
|
|
287 |
|
|
288 |
|coll|
|
|
289 |
|
|
290 |
coll := OrderedCollection new:(keyArray size).
|
|
291 |
self associationsDo:[:assoc | coll add:assoc].
|
|
292 |
^ coll
|
|
293 |
!
|
|
294 |
|
10
|
295 |
keyAtValue:aValue
|
345
|
296 |
"return the key whose value is identical (i.e. using #== for compare)
|
|
297 |
to the argument, nil if none found.
|
77
|
298 |
This is a slow access, since there is no fast reverse mapping.
|
|
299 |
The value is searched for using identity compare."
|
10
|
300 |
|
|
301 |
^ self keyAtValue:aValue ifAbsent:[nil]
|
|
302 |
!
|
|
303 |
|
|
304 |
keyAtValue:aValue ifAbsent:exceptionBlock
|
345
|
305 |
"return the key whose value is identical (i.e. using #== for compare)
|
|
306 |
to the argument, if not found, return the value of exceptionBlock.
|
68
|
307 |
This is a slow access, since there is no fast reverse mapping."
|
10
|
308 |
|
|
309 |
keyArray keysAndValuesDo:[:index :aKey |
|
155
|
310 |
(aKey notNil and:[aKey ~~ DeletedEntry]) ifTrue:[
|
345
|
311 |
(valueArray at:index) == aValue ifTrue:[^ aKey].
|
155
|
312 |
].
|
10
|
313 |
].
|
|
314 |
^ exceptionBlock value
|
1
|
315 |
! !
|
|
316 |
|
|
317 |
!Dictionary methodsFor:'adding & removing'!
|
|
318 |
|
|
319 |
add:anAssociation
|
|
320 |
"add the argument, anAssociation to the receiver"
|
|
321 |
|
|
322 |
self at:(anAssociation key) put:(anAssociation value).
|
|
323 |
^ anAssociation
|
|
324 |
!
|
|
325 |
|
345
|
326 |
declare:key from:aDictionary
|
|
327 |
"if the receiver does not include an association for key,
|
|
328 |
take the association from aDictionary and add it to the receiver.
|
|
329 |
If aDictionary does not contain such an association, use nil
|
|
330 |
as the value of the new dictionary."
|
|
331 |
|
|
332 |
|value|
|
|
333 |
|
|
334 |
(self includesKey:key) ifFalse:[
|
|
335 |
value := aDictionary at:key ifAbsent:nil.
|
|
336 |
self at:key put:value.
|
|
337 |
]
|
|
338 |
!
|
|
339 |
|
1
|
340 |
remove:oldObject ifAbsent:aBlock
|
|
341 |
"remove oldObject from the collection and return it.
|
|
342 |
If it was not in the collection return the value of aBlock."
|
|
343 |
|
|
344 |
self shouldNotImplement
|
|
345 |
!
|
|
346 |
|
|
347 |
removeAssociation:assoc
|
|
348 |
"remove the association from the collection.
|
|
349 |
If it was not in the collection report an error"
|
|
350 |
|
|
351 |
self removeKey:assoc key
|
|
352 |
!
|
|
353 |
|
|
354 |
removeKey:aKey
|
|
355 |
"remove the association under aKey from the collection.
|
|
356 |
If it was not in the collection report an error"
|
|
357 |
|
345
|
358 |
^ self removeKey:aKey ifAbsent:[^ self errorKeyNotFound:aKey]
|
1
|
359 |
!
|
|
360 |
|
|
361 |
removeKey:aKey ifAbsent:aBlock
|
|
362 |
"remove the association under aKey from the collection.
|
|
363 |
If it was not in the collection return result from evaluating aBlock"
|
|
364 |
|
3
|
365 |
|index "{ Class:SmallInteger }"
|
1
|
366 |
next "{ Class:SmallInteger }" |
|
|
367 |
|
|
368 |
aKey isNil ifTrue:[
|
155
|
369 |
self errorInvalidKey
|
1
|
370 |
] ifFalse:[
|
155
|
371 |
"
|
|
372 |
I could have written:
|
|
373 |
index := self find:aKey ifAbsent:[^ aBlock value]
|
|
374 |
but the code below is slighlty more efficient, since it avoids
|
|
375 |
a block creation ([0] is very cheap) - thus speeding up the good case.
|
|
376 |
"
|
|
377 |
index := self find:aKey ifAbsent:[0].
|
|
378 |
index == 0 ifTrue:[^ aBlock value].
|
77
|
379 |
|
155
|
380 |
valueArray basicAt:index put:nil.
|
|
381 |
keyArray basicAt:index put:nil.
|
|
382 |
tally := tally - 1.
|
|
383 |
tally == 0 ifTrue:[
|
|
384 |
self setTally:0
|
|
385 |
] ifFalse:[
|
|
386 |
index == keyArray basicSize ifTrue:[
|
|
387 |
next := 1
|
|
388 |
] ifFalse:[
|
|
389 |
next := index + 1.
|
|
390 |
].
|
|
391 |
(keyArray basicAt:next) notNil ifTrue:[
|
|
392 |
keyArray basicAt:index put:DeletedEntry
|
|
393 |
].
|
|
394 |
self emptyCheck
|
|
395 |
]
|
1
|
396 |
]
|
77
|
397 |
!
|
|
398 |
|
|
399 |
removeValue:aValue ifAbsent:aBlock
|
|
400 |
"remove (first) the association to aValue from the collection.
|
|
401 |
If it was not in the collection return result from evaluating aBlock.
|
|
402 |
The value is searched for using identity compare."
|
|
403 |
|
|
404 |
|next "{ Class:SmallInteger }" |
|
|
405 |
|
|
406 |
aValue notNil ifTrue:[
|
155
|
407 |
keyArray keysAndValuesDo:[:index :aKey |
|
|
408 |
(aKey notNil and:[aKey ~~ DeletedEntry]) ifTrue:[
|
345
|
409 |
(self compareSame:(valueArray at:index) with:aValue) ifTrue:[
|
155
|
410 |
"found it"
|
|
411 |
valueArray basicAt:index put:nil.
|
|
412 |
keyArray basicAt:index put:nil.
|
|
413 |
tally := tally - 1.
|
|
414 |
tally == 0 ifTrue:[
|
|
415 |
self setTally:0.
|
|
416 |
^ self
|
|
417 |
].
|
|
418 |
index == keyArray basicSize ifTrue:[
|
|
419 |
next := 1
|
|
420 |
] ifFalse:[
|
|
421 |
next := index + 1.
|
|
422 |
].
|
|
423 |
(keyArray basicAt:next) notNil ifTrue:[
|
|
424 |
keyArray basicAt:index put:DeletedEntry
|
|
425 |
].
|
|
426 |
self emptyCheck.
|
|
427 |
^ self
|
|
428 |
]
|
|
429 |
]
|
|
430 |
]
|
77
|
431 |
].
|
|
432 |
^ aBlock value
|
1
|
433 |
! !
|
|
434 |
|
155
|
435 |
!Dictionary methodsFor:'copying'!
|
|
436 |
|
|
437 |
postCopy
|
|
438 |
"have to copy the valueArray too"
|
|
439 |
|
|
440 |
super postCopy.
|
|
441 |
valueArray := valueArray shallowCopy
|
|
442 |
! !
|
|
443 |
|
217
|
444 |
!Dictionary methodsFor:'enumerating'!
|
1
|
445 |
|
302
|
446 |
keysDo:aBlock
|
|
447 |
"perform the block for all keys in the collection."
|
|
448 |
|
|
449 |
^ super do:aBlock
|
|
450 |
!
|
|
451 |
|
1
|
452 |
allKeysDo:aBlock
|
302
|
453 |
"perform the block for all keys in the collection.
|
|
454 |
Obsolete: use keysDo: for ST-80 compatibility."
|
1
|
455 |
|
155
|
456 |
^ super do:aBlock
|
1
|
457 |
!
|
|
458 |
|
|
459 |
associationsDo:aBlock
|
|
460 |
"perform the block for all associations in the collection."
|
|
461 |
|
38
|
462 |
|key n "{ Class: SmallInteger }"|
|
1
|
463 |
|
|
464 |
tally == 0 ifTrue:[^ self].
|
38
|
465 |
n := keyArray basicSize.
|
|
466 |
1 to:n do:[:index |
|
155
|
467 |
key := keyArray basicAt:index.
|
|
468 |
(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
|
|
469 |
aBlock value:(Association key:key value:(valueArray basicAt:index))
|
|
470 |
]
|
1
|
471 |
]
|
|
472 |
!
|
|
473 |
|
|
474 |
do:aBlock
|
|
475 |
"perform the block for all values in the collection."
|
|
476 |
|
38
|
477 |
|key n "{ Class: SmallInteger }"|
|
1
|
478 |
|
|
479 |
tally == 0 ifTrue:[^ self].
|
38
|
480 |
n := keyArray basicSize.
|
|
481 |
1 to:n do:[:index |
|
155
|
482 |
key := keyArray basicAt:index.
|
|
483 |
(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
|
|
484 |
aBlock value:(valueArray basicAt:index)
|
|
485 |
].
|
1
|
486 |
]
|
|
487 |
!
|
|
488 |
|
3
|
489 |
keysAndValuesDo:aTwoArgBlock
|
|
490 |
"evaluate the argument, aBlock for every element in the collection,
|
|
491 |
passing both key and element as arguments."
|
|
492 |
|
38
|
493 |
|key n "{ Class: SmallInteger }"|
|
3
|
494 |
|
|
495 |
tally == 0 ifTrue:[^ self].
|
38
|
496 |
n := keyArray basicSize.
|
|
497 |
1 to:n do:[:index |
|
155
|
498 |
key := keyArray basicAt:index.
|
|
499 |
(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
|
|
500 |
aTwoArgBlock value:key value:(valueArray basicAt:index)
|
|
501 |
].
|
3
|
502 |
]
|
|
503 |
!
|
|
504 |
|
1
|
505 |
collect:aBlock
|
|
506 |
"for each element in the receiver, evaluate the argument, aBlock
|
|
507 |
and return a Bag with the results"
|
|
508 |
|
|
509 |
|newCollection|
|
|
510 |
|
|
511 |
newCollection := Bag new.
|
|
512 |
self do:[:each |
|
155
|
513 |
newCollection add:(aBlock value:each)
|
1
|
514 |
].
|
|
515 |
^ newCollection
|
|
516 |
!
|
|
517 |
|
|
518 |
select:aBlock
|
|
519 |
"return a new collection with all elements from the receiver, for which
|
77
|
520 |
the argument aBlock evaluates to true. The block gets the individual values
|
|
521 |
as its single argument."
|
1
|
522 |
|
|
523 |
|newCollection|
|
|
524 |
|
|
525 |
newCollection := self species new.
|
77
|
526 |
self keysAndValuesDo:[:key :value |
|
155
|
527 |
(aBlock value:value) ifTrue:[
|
|
528 |
newCollection at:key put:value
|
|
529 |
]
|
1
|
530 |
].
|
|
531 |
^ newCollection
|
77
|
532 |
|
|
533 |
"
|
|
534 |
|d|
|
|
535 |
|
|
536 |
d := Dictionary new.
|
|
537 |
d at:#foo put:#bar.
|
|
538 |
d at:#bar put:#baz.
|
|
539 |
d at:#baz put:#foo.
|
|
540 |
|
|
541 |
d select:[:el | el startsWith:'b'].
|
|
542 |
"
|
1
|
543 |
! !
|
|
544 |
|
|
545 |
!Dictionary methodsFor:'private'!
|
|
546 |
|
345
|
547 |
compareSame:element1 with:element2
|
|
548 |
^ element1 = element2
|
|
549 |
!
|
|
550 |
|
92
|
551 |
valueContainerOfSize:n
|
|
552 |
"return a container for values of size n.
|
|
553 |
Extracted to make life of weak subclasses easier ..."
|
|
554 |
|
|
555 |
^ Array new:n
|
|
556 |
!
|
|
557 |
|
1
|
558 |
setTally:count
|
|
559 |
"initialize the contents array (for at least count slots)
|
|
560 |
and set tally to zero.
|
|
561 |
The size is increased to the next prime for better hashing behavior."
|
|
562 |
|
|
563 |
|n|
|
|
564 |
|
249
|
565 |
n := self class goodSizeFrom:count.
|
10
|
566 |
keyArray := self keyContainerOfSize:n.
|
92
|
567 |
valueArray := self valueContainerOfSize:n.
|
1
|
568 |
tally := 0
|
|
569 |
!
|
|
570 |
|
|
571 |
grow:newSize
|
|
572 |
"grow the receiver to make space for at least newSize elements.
|
|
573 |
To do this, we have to rehash into the new arrays.
|
|
574 |
(which is done by re-adding all elements to a new, empty key/value array pair)."
|
|
575 |
|
92
|
576 |
|key deletedEntry oldKeyArray oldValueArray n
|
|
577 |
oldSize "{ Class:SmallInteger }"
|
10
|
578 |
newIndex "{ Class:SmallInteger }" |
|
1
|
579 |
|
10
|
580 |
oldKeyArray := keyArray.
|
|
581 |
oldValueArray := valueArray.
|
1
|
582 |
|
249
|
583 |
n := self class goodSizeFrom:newSize.
|
|
584 |
oldSize := oldKeyArray size.
|
|
585 |
n == oldSize ifTrue:[^ self].
|
|
586 |
|
10
|
587 |
keyArray := self keyContainerOfSize:n.
|
92
|
588 |
valueArray := self valueContainerOfSize:n.
|
1
|
589 |
|
249
|
590 |
|
92
|
591 |
deletedEntry := DeletedEntry.
|
10
|
592 |
1 to:oldSize do:[:index |
|
155
|
593 |
key := oldKeyArray basicAt:index.
|
|
594 |
(key notNil and:[key ~~ deletedEntry]) ifTrue:[
|
|
595 |
newIndex := self findNil:key.
|
|
596 |
keyArray basicAt:newIndex put:key.
|
|
597 |
valueArray basicAt:newIndex put:(oldValueArray basicAt:index).
|
|
598 |
]
|
1
|
599 |
]
|
|
600 |
!
|
|
601 |
|
|
602 |
rehash
|
|
603 |
"rehash contents - is done by re-adding all elements to a new, empty key/value array pair)."
|
|
604 |
|
2
|
605 |
| oldKeyArray oldValueArray key
|
|
606 |
n "{ Class:SmallInteger }"
|
|
607 |
newIndex "{ Class:SmallInteger }" |
|
1
|
608 |
|
|
609 |
oldKeyArray := keyArray.
|
|
610 |
oldValueArray := valueArray.
|
|
611 |
|
|
612 |
n := keyArray size.
|
10
|
613 |
keyArray := self keyContainerOfSize:n.
|
92
|
614 |
valueArray := self valueContainerOfSize:n.
|
1
|
615 |
|
2
|
616 |
1 to:n do:[:index |
|
155
|
617 |
key := oldKeyArray basicAt:index.
|
|
618 |
(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
|
|
619 |
newIndex := self findNil:key.
|
|
620 |
keyArray basicAt:newIndex put:key.
|
|
621 |
valueArray basicAt:newIndex put:(oldValueArray basicAt:index).
|
|
622 |
]
|
1
|
623 |
]
|
|
624 |
!
|
|
625 |
|
|
626 |
rehashFrom:startIndex
|
77
|
627 |
"rehash elements starting at index - after a remove.
|
|
628 |
NOTE: this method is no longer needed;
|
155
|
629 |
the trick using DeletedEntry avoids the need to do this time
|
|
630 |
consuming operation, making remove pretty fast :-)
|
77
|
631 |
"
|
1
|
632 |
|
|
633 |
|key i length
|
|
634 |
index "{ Class:SmallInteger }" |
|
|
635 |
|
|
636 |
length := keyArray basicSize.
|
|
637 |
index := startIndex.
|
|
638 |
key := keyArray basicAt:index.
|
|
639 |
[key notNil] whileTrue:[
|
155
|
640 |
key ~~ DeletedEntry ifTrue:[
|
|
641 |
i := self findNil:key.
|
|
642 |
i == index ifTrue:[
|
|
643 |
^ self
|
|
644 |
].
|
|
645 |
keyArray basicAt:i put:key.
|
|
646 |
valueArray basicAt:i put:(valueArray basicAt:index).
|
|
647 |
keyArray basicAt:index put:nil.
|
|
648 |
valueArray basicAt:index put:nil.
|
|
649 |
].
|
|
650 |
index == length ifTrue:[
|
|
651 |
index := 1
|
|
652 |
] ifFalse:[
|
|
653 |
index := index + 1.
|
|
654 |
].
|
|
655 |
key := keyArray basicAt:index.
|
1
|
656 |
]
|
77
|
657 |
!
|
|
658 |
|
|
659 |
emptyCollectionForKeys
|
|
660 |
^ Set new:(self size)
|
1
|
661 |
! !
|
|
662 |
|
|
663 |
!Dictionary methodsFor:'printing & storing'!
|
|
664 |
|
|
665 |
stringWith:aSelector
|
|
666 |
"common code for printString & displayString"
|
|
667 |
|
|
668 |
|thisString string noneYet|
|
|
669 |
|
|
670 |
string := (self class name) , '('.
|
|
671 |
noneYet := true.
|
|
672 |
self associationsDo:[:element |
|
155
|
673 |
thisString := element perform:aSelector.
|
|
674 |
noneYet ifTrue:[noneYet := false]
|
|
675 |
ifFalse:[thisString := ' ' , thisString].
|
|
676 |
string := string , thisString
|
1
|
677 |
].
|
|
678 |
string := string , ')'.
|
|
679 |
^string
|
|
680 |
!
|
|
681 |
|
|
682 |
printString
|
44
|
683 |
"return a string for printing"
|
|
684 |
|
1
|
685 |
^ self stringWith:#printString
|
|
686 |
!
|
|
687 |
|
|
688 |
displayString
|
44
|
689 |
"return a string for displaying"
|
|
690 |
|
1
|
691 |
^ self stringWith:#displayString
|
44
|
692 |
!
|
|
693 |
|
|
694 |
storeOn:aStream
|
|
695 |
"output a printed representation (which can be re-read)
|
|
696 |
onto the argument aStream"
|
|
697 |
|
|
698 |
|isEmpty|
|
|
699 |
|
68
|
700 |
thisContext isRecursive ifTrue:[
|
155
|
701 |
Transcript showCr:'Error: storeOn: of self referencing collection.'.
|
293
|
702 |
aStream nextPutAll:'#recursive'.
|
155
|
703 |
^ self
|
68
|
704 |
].
|
|
705 |
|
44
|
706 |
aStream nextPutAll:'('.
|
|
707 |
aStream nextPutAll:(self class name).
|
|
708 |
aStream nextPutAll:' new'.
|
|
709 |
isEmpty := true.
|
|
710 |
self keysAndValuesDo:[:key :value |
|
155
|
711 |
aStream nextPutAll:' at:'.
|
|
712 |
key storeOn:aStream.
|
|
713 |
aStream nextPutAll:' put:'.
|
|
714 |
value storeOn:aStream.
|
|
715 |
aStream nextPutAll:'; '.
|
|
716 |
isEmpty := false
|
44
|
717 |
].
|
|
718 |
isEmpty ifFalse:[aStream nextPutAll:' yourself'].
|
|
719 |
aStream nextPut:$)
|
|
720 |
|
293
|
721 |
"
|
|
722 |
Dictionary new storeOn:Transcript
|
|
723 |
|
|
724 |
(Dictionary new at:1 put:'hello'; yourself) storeOn:Transcript
|
|
725 |
"
|
|
726 |
|
|
727 |
"
|
|
728 |
|d|
|
44
|
729 |
d := Dictionary new.
|
|
730 |
d at:1 put:'hello'.
|
|
731 |
d at:'hello' put:#world.
|
293
|
732 |
d storeOn:Transcript
|
|
733 |
"
|
|
734 |
|
|
735 |
"
|
|
736 |
|d|
|
|
737 |
d := Dictionary new.
|
|
738 |
d at:1 put:'hello'.
|
|
739 |
d at:'hello' put:#world.
|
|
740 |
d at:2 put:d.
|
|
741 |
d storeOn:Transcript
|
|
742 |
"
|
1
|
743 |
! !
|