--- a/Dict.st Sat Dec 11 01:42:02 1993 +0100
+++ b/Dict.st Sat Dec 11 01:46:55 1993 +0100
@@ -10,8 +10,8 @@
hereby transferred.
"
-Collection subclass:#Dictionary
- instanceVariableNames:'valueArray keyArray tally'
+Set subclass:#Dictionary
+ instanceVariableNames:'valueArray'
classVariableNames:''
poolDictionaries:''
category:'Collections-Unordered'
@@ -26,54 +26,25 @@
(The implementation uses two array to store the keys and values separately.)
Searching for an element is done using a hash into the key array.
-$Header: /cvs/stx/stx/libbasic/Attic/Dict.st,v 1.5 1993-11-08 02:30:03 claus Exp $
+$Header: /cvs/stx/stx/libbasic/Attic/Dict.st,v 1.6 1993-12-11 00:45:55 claus Exp $
written jun 91 by claus
rewritten 92 to use hash scheme
'!
-!Dictionary class methodsFor:'instance creation'!
-
-new
- "return a new empty Dictionary"
-
- ^ self new:5
-!
-
-new:anInteger
- "return a new empty Dictionary with space for anInteger elements"
-
- ^ self basicNew setTally:anInteger
-! !
-
-!Dictionary methodsFor:'private'!
-
-keyContainerOfSize:n
- "return a container for keys and values of size n.
- Extracted to make life of WeakDictionary easier ..."
-
- ^ Array new:n
-! !
-
!Dictionary methodsFor:'testing'!
-size
- "return the number of elements in the receiver"
-
- ^ tally
-!
-
includesKey:aKey
"return true, if the argument, aKey is a key in the receiver"
- ^ (self findKey:aKey ifAbsent:[0]) ~~ 0
+ ^ (self find:aKey ifAbsent:[0]) ~~ 0
!
-isFixedSize
- "return true if the receiver cannot grow - this will vanish once
- Arrays and Strings learn how to grow ..."
+includes:aValue
+ "return true, if the argument, aValue is stoerd in the dictionary,
+ This is a slow search, since there is no fast reverse mapping"
- ^ false
+ ^ valueArray includes:aValue
! !
!Dictionary methodsFor:'accessing'!
@@ -86,7 +57,7 @@
aKey isNil ifTrue:[
self errorInvalidKey
] ifFalse:[
- index := self findKey:aKey ifAbsent:[0].
+ index := self find:aKey ifAbsent:[0].
index == 0 ifTrue:[^ self errorKeyNotFound].
^ valueArray basicAt:index
]
@@ -101,7 +72,7 @@
aKey isNil ifTrue:[
self errorInvalidKey
] ifFalse:[
- index := self findKey:aKey ifAbsent:[0].
+ index := self find:aKey ifAbsent:[0].
index == 0 ifTrue:[^ exceptionBlock value].
^ valueArray basicAt:index
]
@@ -158,9 +129,9 @@
This is a slow access, since there is no fast reverse mapping"
keyArray keysAndValuesDo:[:index :aKey |
- aKey notNil ifTrue:[
- (valueArray at:index) = aValue ifTrue:[^ aKey].
- ].
+ aKey notNil ifTrue:[
+ (valueArray at:index) = aValue ifTrue:[^ aKey].
+ ].
].
^ exceptionBlock value
! !
@@ -192,31 +163,7 @@
"remove the association under aKey from the collection.
If it was not in the collection report an error"
- |index "{ Class:SmallInteger }"
- next "{ Class:SmallInteger }" |
-
- aKey isNil ifTrue:[
- self errorInvalidKey
- ] ifFalse:[
- index := self findKey:aKey ifAbsent:[0].
- (index == 0) ifTrue:[^ self errorNotFound].
- valueArray basicAt:index put:nil.
- keyArray basicAt:index put:nil.
- tally := tally - 1.
- tally == 0 ifTrue:[
- self setTally:0
- ] ifFalse:[
- index == keyArray basicSize ifTrue:[
- next := 1
- ] ifFalse:[
- next := index + 1.
- ].
- "redundant check to save a send sometimes"
- (keyArray basicAt:next) notNil ifTrue:[
- self rehashFrom:next.
- ]
- ]
- ]
+ ^ self removeKey:aKey ifAbsent:[^ self errorNotFound]
!
removeKey:aKey ifAbsent:aBlock
@@ -229,7 +176,7 @@
aKey isNil ifTrue:[
self errorInvalidKey
] ifFalse:[
- index := self findKey:aKey ifAbsent:[0].
+ index := self find:aKey ifAbsent:[0].
index == 0 ifTrue:[^ aBlock value].
valueArray basicAt:index put:nil.
keyArray basicAt:index put:nil.
@@ -311,7 +258,7 @@
newCollection := Bag new.
self do:[:each |
- newCollection add:each
+ newCollection add:(aBlock value:each)
].
^ newCollection
!
@@ -333,28 +280,6 @@
!Dictionary methodsFor:'private'!
-fullCheck
- "check if dictionary is full, grow if so.
- Definition of full is currently:'filled more than 70%'"
-
- "grow if filled more than 70% "
- tally > (keyArray basicSize * 7 // 10) ifTrue:[
- self grow
- ]
-!
-
-goodSizeFor:arg
- "return a good array size for the given argument.
- Returns the next prime after arg"
-
- arg <= 7 ifTrue:[^ 7].
- arg <= 131072 ifTrue:[
- "2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072"
- ^ #(7 7 11 17 37 67 131 257 521 1031 2053 4099 8209 16411 32771 65537 131101) at:(arg highBit)
- ].
- ^ arg bitOr:1
-!
-
setTally:count
"initialize the contents array (for at least count slots)
and set tally to zero.
@@ -368,75 +293,6 @@
tally := 0
!
-findKeyOrNil:key
- "Look for the key in the receiver. If it is found, return
- the index of the association containing the key, otherwise
- return the index of the first unused slot. Grow the receiver,
- if key was not found, and no unused slots where present"
-
- |index "{ Class:SmallInteger }"
- length startIndex probe|
-
- length := keyArray basicSize.
- startIndex := key hash \\ length + 1.
-
- index := startIndex.
- [true] whileTrue:[
- probe := keyArray basicAt:index.
- (probe isNil or: [key = probe]) ifTrue:[^ index].
-
- index == length ifTrue:[
- index := 1
- ] ifFalse:[
- index := index + 1
- ].
- index == startIndex ifTrue:[^ self grow findKeyOrNil:key]
- ]
-!
-
-findKey:key ifAbsent:aBlock
- "Look for the key in the receiver. If it is found, return
- the index of the association containing the key, otherwise
- return the value of evaluating aBlock."
-
- |index "{ Class:SmallInteger }"
- length "{ Class:SmallInteger }"
- startIndex
- probe|
-
- length := keyArray basicSize.
- length < 10 ifTrue:[
- "assuming, that for small dictionaries the overhead of hashing
- is large ... maybe that proves wrong (if overhead of comparing
- is high)"
- ^ keyArray indexOf:key ifAbsent:aBlock
- ].
-
- startIndex := key hash \\ length + 1.
-
- index := startIndex.
- [true] whileTrue:[
- probe := (keyArray basicAt:index).
- key = probe ifTrue:[^ index].
-
- index == length ifTrue:[
- index := 1
- ] ifFalse:[
- index := index + 1
- ].
- ((probe isNil) or:[index == startIndex]) ifTrue:[
- ^ aBlock value
- ]
- ]
-!
-
-grow
- "change the number of element slots of the collection to a useful
- new size"
-
- self grow:(keyArray basicSize * 2)
-!
-
grow:newSize
"grow the receiver to make space for at least newSize elements.
To do this, we have to rehash into the new arrays.
@@ -452,13 +308,12 @@
n := self goodSizeFor:newSize.
keyArray := self keyContainerOfSize:n.
valueArray := Array new:n.
- tally := 0.
oldSize := oldKeyArray size.
1 to:oldSize do:[:index |
key := oldKeyArray basicAt:index.
key notNil ifTrue:[
- newIndex := self findKeyOrNil:key.
+ newIndex := self findNil:key.
keyArray basicAt:newIndex put:key.
valueArray basicAt:newIndex put:(oldValueArray basicAt:index).
]
@@ -482,7 +337,7 @@
1 to:n do:[:index |
key := oldKeyArray basicAt:index.
key notNil ifTrue:[
- newIndex := self findKeyOrNil:key.
+ newIndex := self findNil:key.
keyArray basicAt:newIndex put:key.
valueArray basicAt:newIndex put:(oldValueArray basicAt:index).
]
@@ -499,7 +354,7 @@
index := startIndex.
key := keyArray basicAt:index.
[key notNil] whileTrue:[
- i := self findKeyOrNil:key.
+ i := self findNil:key.
i == index ifTrue:[
^ self
].
@@ -517,13 +372,6 @@
]
! !
-!Dictionary methodsFor: 'binary storage'!
-
-readBinaryContentsFrom: stream manager: manager
- super readBinaryContentsFrom: stream manager: manager.
- self rehash
-! !
-
!Dictionary methodsFor:'printing & storing'!
stringWith:aSelector