8 be provided or otherwise made available to, or used by, any |
8 be provided or otherwise made available to, or used by, any |
9 other person. No title to or ownership of the software is |
9 other person. No title to or ownership of the software is |
10 hereby transferred. |
10 hereby transferred. |
11 " |
11 " |
12 |
12 |
13 Collection subclass:#Dictionary |
13 Set subclass:#Dictionary |
14 instanceVariableNames:'valueArray keyArray tally' |
14 instanceVariableNames:'valueArray' |
15 classVariableNames:'' |
15 classVariableNames:'' |
16 poolDictionaries:'' |
16 poolDictionaries:'' |
17 category:'Collections-Unordered' |
17 category:'Collections-Unordered' |
18 ! |
18 ! |
19 |
19 |
24 |
24 |
25 a Dictionary is (conceptionally) a collection of Associations storing key-value pairs. |
25 a Dictionary is (conceptionally) a collection of Associations storing key-value pairs. |
26 (The implementation uses two array to store the keys and values separately.) |
26 (The implementation uses two array to store the keys and values separately.) |
27 Searching for an element is done using a hash into the key array. |
27 Searching for an element is done using a hash into the key array. |
28 |
28 |
29 $Header: /cvs/stx/stx/libbasic/Dictionary.st,v 1.5 1993-11-08 02:30:03 claus Exp $ |
29 $Header: /cvs/stx/stx/libbasic/Dictionary.st,v 1.6 1993-12-11 00:45:55 claus Exp $ |
30 |
30 |
31 written jun 91 by claus |
31 written jun 91 by claus |
32 rewritten 92 to use hash scheme |
32 rewritten 92 to use hash scheme |
33 '! |
33 '! |
34 |
34 |
35 !Dictionary class methodsFor:'instance creation'! |
|
36 |
|
37 new |
|
38 "return a new empty Dictionary" |
|
39 |
|
40 ^ self new:5 |
|
41 ! |
|
42 |
|
43 new:anInteger |
|
44 "return a new empty Dictionary with space for anInteger elements" |
|
45 |
|
46 ^ self basicNew setTally:anInteger |
|
47 ! ! |
|
48 |
|
49 !Dictionary methodsFor:'private'! |
|
50 |
|
51 keyContainerOfSize:n |
|
52 "return a container for keys and values of size n. |
|
53 Extracted to make life of WeakDictionary easier ..." |
|
54 |
|
55 ^ Array new:n |
|
56 ! ! |
|
57 |
|
58 !Dictionary methodsFor:'testing'! |
35 !Dictionary methodsFor:'testing'! |
59 |
|
60 size |
|
61 "return the number of elements in the receiver" |
|
62 |
|
63 ^ tally |
|
64 ! |
|
65 |
36 |
66 includesKey:aKey |
37 includesKey:aKey |
67 "return true, if the argument, aKey is a key in the receiver" |
38 "return true, if the argument, aKey is a key in the receiver" |
68 |
39 |
69 ^ (self findKey:aKey ifAbsent:[0]) ~~ 0 |
40 ^ (self find:aKey ifAbsent:[0]) ~~ 0 |
70 ! |
41 ! |
71 |
42 |
72 isFixedSize |
43 includes:aValue |
73 "return true if the receiver cannot grow - this will vanish once |
44 "return true, if the argument, aValue is stoerd in the dictionary, |
74 Arrays and Strings learn how to grow ..." |
45 This is a slow search, since there is no fast reverse mapping" |
75 |
46 |
76 ^ false |
47 ^ valueArray includes:aValue |
77 ! ! |
48 ! ! |
78 |
49 |
79 !Dictionary methodsFor:'accessing'! |
50 !Dictionary methodsFor:'accessing'! |
80 |
51 |
81 at:aKey |
52 at:aKey |
156 "return the key whose value equals the argument, the value of the |
127 "return the key whose value equals the argument, the value of the |
157 exceptionBlock if none is found.. |
128 exceptionBlock if none is found.. |
158 This is a slow access, since there is no fast reverse mapping" |
129 This is a slow access, since there is no fast reverse mapping" |
159 |
130 |
160 keyArray keysAndValuesDo:[:index :aKey | |
131 keyArray keysAndValuesDo:[:index :aKey | |
161 aKey notNil ifTrue:[ |
132 aKey notNil ifTrue:[ |
162 (valueArray at:index) = aValue ifTrue:[^ aKey]. |
133 (valueArray at:index) = aValue ifTrue:[^ aKey]. |
163 ]. |
134 ]. |
164 ]. |
135 ]. |
165 ^ exceptionBlock value |
136 ^ exceptionBlock value |
166 ! ! |
137 ! ! |
167 |
138 |
168 !Dictionary methodsFor:'adding & removing'! |
139 !Dictionary methodsFor:'adding & removing'! |
190 |
161 |
191 removeKey:aKey |
162 removeKey:aKey |
192 "remove the association under aKey from the collection. |
163 "remove the association under aKey from the collection. |
193 If it was not in the collection report an error" |
164 If it was not in the collection report an error" |
194 |
165 |
|
166 ^ self removeKey:aKey ifAbsent:[^ self errorNotFound] |
|
167 ! |
|
168 |
|
169 removeKey:aKey ifAbsent:aBlock |
|
170 "remove the association under aKey from the collection. |
|
171 If it was not in the collection return result from evaluating aBlock" |
|
172 |
195 |index "{ Class:SmallInteger }" |
173 |index "{ Class:SmallInteger }" |
196 next "{ Class:SmallInteger }" | |
174 next "{ Class:SmallInteger }" | |
197 |
175 |
198 aKey isNil ifTrue:[ |
176 aKey isNil ifTrue:[ |
199 self errorInvalidKey |
177 self errorInvalidKey |
200 ] ifFalse:[ |
178 ] ifFalse:[ |
201 index := self findKey:aKey ifAbsent:[0]. |
179 index := self find:aKey ifAbsent:[0]. |
202 (index == 0) ifTrue:[^ self errorNotFound]. |
|
203 valueArray basicAt:index put:nil. |
|
204 keyArray basicAt:index put:nil. |
|
205 tally := tally - 1. |
|
206 tally == 0 ifTrue:[ |
|
207 self setTally:0 |
|
208 ] ifFalse:[ |
|
209 index == keyArray basicSize ifTrue:[ |
|
210 next := 1 |
|
211 ] ifFalse:[ |
|
212 next := index + 1. |
|
213 ]. |
|
214 "redundant check to save a send sometimes" |
|
215 (keyArray basicAt:next) notNil ifTrue:[ |
|
216 self rehashFrom:next. |
|
217 ] |
|
218 ] |
|
219 ] |
|
220 ! |
|
221 |
|
222 removeKey:aKey ifAbsent:aBlock |
|
223 "remove the association under aKey from the collection. |
|
224 If it was not in the collection return result from evaluating aBlock" |
|
225 |
|
226 |index "{ Class:SmallInteger }" |
|
227 next "{ Class:SmallInteger }" | |
|
228 |
|
229 aKey isNil ifTrue:[ |
|
230 self errorInvalidKey |
|
231 ] ifFalse:[ |
|
232 index := self findKey:aKey ifAbsent:[0]. |
|
233 index == 0 ifTrue:[^ aBlock value]. |
180 index == 0 ifTrue:[^ aBlock value]. |
234 valueArray basicAt:index put:nil. |
181 valueArray basicAt:index put:nil. |
235 keyArray basicAt:index put:nil. |
182 keyArray basicAt:index put:nil. |
236 tally := tally - 1. |
183 tally := tally - 1. |
237 tally == 0 ifTrue:[ |
184 tally == 0 ifTrue:[ |
331 ^ newCollection |
278 ^ newCollection |
332 ! ! |
279 ! ! |
333 |
280 |
334 !Dictionary methodsFor:'private'! |
281 !Dictionary methodsFor:'private'! |
335 |
282 |
336 fullCheck |
|
337 "check if dictionary is full, grow if so. |
|
338 Definition of full is currently:'filled more than 70%'" |
|
339 |
|
340 "grow if filled more than 70% " |
|
341 tally > (keyArray basicSize * 7 // 10) ifTrue:[ |
|
342 self grow |
|
343 ] |
|
344 ! |
|
345 |
|
346 goodSizeFor:arg |
|
347 "return a good array size for the given argument. |
|
348 Returns the next prime after arg" |
|
349 |
|
350 arg <= 7 ifTrue:[^ 7]. |
|
351 arg <= 131072 ifTrue:[ |
|
352 "2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072" |
|
353 ^ #(7 7 11 17 37 67 131 257 521 1031 2053 4099 8209 16411 32771 65537 131101) at:(arg highBit) |
|
354 ]. |
|
355 ^ arg bitOr:1 |
|
356 ! |
|
357 |
|
358 setTally:count |
283 setTally:count |
359 "initialize the contents array (for at least count slots) |
284 "initialize the contents array (for at least count slots) |
360 and set tally to zero. |
285 and set tally to zero. |
361 The size is increased to the next prime for better hashing behavior." |
286 The size is increased to the next prime for better hashing behavior." |
362 |
287 |
366 keyArray := self keyContainerOfSize:n. |
291 keyArray := self keyContainerOfSize:n. |
367 valueArray := Array new:n. |
292 valueArray := Array new:n. |
368 tally := 0 |
293 tally := 0 |
369 ! |
294 ! |
370 |
295 |
371 findKeyOrNil:key |
|
372 "Look for the key in the receiver. If it is found, return |
|
373 the index of the association containing the key, otherwise |
|
374 return the index of the first unused slot. Grow the receiver, |
|
375 if key was not found, and no unused slots where present" |
|
376 |
|
377 |index "{ Class:SmallInteger }" |
|
378 length startIndex probe| |
|
379 |
|
380 length := keyArray basicSize. |
|
381 startIndex := key hash \\ length + 1. |
|
382 |
|
383 index := startIndex. |
|
384 [true] whileTrue:[ |
|
385 probe := keyArray basicAt:index. |
|
386 (probe isNil or: [key = probe]) ifTrue:[^ index]. |
|
387 |
|
388 index == length ifTrue:[ |
|
389 index := 1 |
|
390 ] ifFalse:[ |
|
391 index := index + 1 |
|
392 ]. |
|
393 index == startIndex ifTrue:[^ self grow findKeyOrNil:key] |
|
394 ] |
|
395 ! |
|
396 |
|
397 findKey:key ifAbsent:aBlock |
|
398 "Look for the key in the receiver. If it is found, return |
|
399 the index of the association containing the key, otherwise |
|
400 return the value of evaluating aBlock." |
|
401 |
|
402 |index "{ Class:SmallInteger }" |
|
403 length "{ Class:SmallInteger }" |
|
404 startIndex |
|
405 probe| |
|
406 |
|
407 length := keyArray basicSize. |
|
408 length < 10 ifTrue:[ |
|
409 "assuming, that for small dictionaries the overhead of hashing |
|
410 is large ... maybe that proves wrong (if overhead of comparing |
|
411 is high)" |
|
412 ^ keyArray indexOf:key ifAbsent:aBlock |
|
413 ]. |
|
414 |
|
415 startIndex := key hash \\ length + 1. |
|
416 |
|
417 index := startIndex. |
|
418 [true] whileTrue:[ |
|
419 probe := (keyArray basicAt:index). |
|
420 key = probe ifTrue:[^ index]. |
|
421 |
|
422 index == length ifTrue:[ |
|
423 index := 1 |
|
424 ] ifFalse:[ |
|
425 index := index + 1 |
|
426 ]. |
|
427 ((probe isNil) or:[index == startIndex]) ifTrue:[ |
|
428 ^ aBlock value |
|
429 ] |
|
430 ] |
|
431 ! |
|
432 |
|
433 grow |
|
434 "change the number of element slots of the collection to a useful |
|
435 new size" |
|
436 |
|
437 self grow:(keyArray basicSize * 2) |
|
438 ! |
|
439 |
|
440 grow:newSize |
296 grow:newSize |
441 "grow the receiver to make space for at least newSize elements. |
297 "grow the receiver to make space for at least newSize elements. |
442 To do this, we have to rehash into the new arrays. |
298 To do this, we have to rehash into the new arrays. |
443 (which is done by re-adding all elements to a new, empty key/value array pair)." |
299 (which is done by re-adding all elements to a new, empty key/value array pair)." |
444 |
300 |
450 oldValueArray := valueArray. |
306 oldValueArray := valueArray. |
451 |
307 |
452 n := self goodSizeFor:newSize. |
308 n := self goodSizeFor:newSize. |
453 keyArray := self keyContainerOfSize:n. |
309 keyArray := self keyContainerOfSize:n. |
454 valueArray := Array new:n. |
310 valueArray := Array new:n. |
455 tally := 0. |
|
456 |
311 |
457 oldSize := oldKeyArray size. |
312 oldSize := oldKeyArray size. |
458 1 to:oldSize do:[:index | |
313 1 to:oldSize do:[:index | |
459 key := oldKeyArray basicAt:index. |
314 key := oldKeyArray basicAt:index. |
460 key notNil ifTrue:[ |
315 key notNil ifTrue:[ |
461 newIndex := self findKeyOrNil:key. |
316 newIndex := self findNil:key. |
462 keyArray basicAt:newIndex put:key. |
317 keyArray basicAt:newIndex put:key. |
463 valueArray basicAt:newIndex put:(oldValueArray basicAt:index). |
318 valueArray basicAt:newIndex put:(oldValueArray basicAt:index). |
464 ] |
319 ] |
465 ] |
320 ] |
466 ! |
321 ! |
480 valueArray := Array new:n. |
335 valueArray := Array new:n. |
481 |
336 |
482 1 to:n do:[:index | |
337 1 to:n do:[:index | |
483 key := oldKeyArray basicAt:index. |
338 key := oldKeyArray basicAt:index. |
484 key notNil ifTrue:[ |
339 key notNil ifTrue:[ |
485 newIndex := self findKeyOrNil:key. |
340 newIndex := self findNil:key. |
486 keyArray basicAt:newIndex put:key. |
341 keyArray basicAt:newIndex put:key. |
487 valueArray basicAt:newIndex put:(oldValueArray basicAt:index). |
342 valueArray basicAt:newIndex put:(oldValueArray basicAt:index). |
488 ] |
343 ] |
489 ] |
344 ] |
490 ! |
345 ! |
497 |
352 |
498 length := keyArray basicSize. |
353 length := keyArray basicSize. |
499 index := startIndex. |
354 index := startIndex. |
500 key := keyArray basicAt:index. |
355 key := keyArray basicAt:index. |
501 [key notNil] whileTrue:[ |
356 [key notNil] whileTrue:[ |
502 i := self findKeyOrNil:key. |
357 i := self findNil:key. |
503 i == index ifTrue:[ |
358 i == index ifTrue:[ |
504 ^ self |
359 ^ self |
505 ]. |
360 ]. |
506 keyArray basicAt:i put:key. |
361 keyArray basicAt:i put:key. |
507 valueArray basicAt:i put:(valueArray basicAt:index). |
362 valueArray basicAt:i put:(valueArray basicAt:index). |