"
 COPYRIGHT (c) 1991 by Claus Gittinger
	      All Rights Reserved

 This software is furnished under a license and may be used
 only in accordance with the terms of that license and with the
 inclusion of the above copyright notice.   This software may not
 be provided or otherwise made available to, or used by, any
 other person.  No title to or ownership of the software is
 hereby transferred.
"

Set subclass:#Dictionary
	instanceVariableNames:'valueArray'
	classVariableNames:''
	poolDictionaries:''
	category:'Collections-Unordered'
!

!Dictionary class methodsFor:'documentation'!

copyright
"
 COPYRIGHT (c) 1991 by Claus Gittinger
	      All Rights Reserved

 This software is furnished under a license and may be used
 only in accordance with the terms of that license and with the
 inclusion of the above copyright notice.   This software may not
 be provided or otherwise made available to, or used by, any
 other person.  No title to or ownership of the software is
 hereby transferred.
"
!

documentation
"
    a Dictionary is (conceptionally) a set of Associations storing key-value pairs.
    (The implementation uses two arrays to store the keys and values separately.)
    Searching for an element is done using a hash into the key array.
    Another way of looking at a dictionary is as a array which uses
    arbitrary access keys (i.e. not just integers as arrays do).

    Since the keys are unordered, no internal element order is defined
    (i.e. enumerating them may return elements in any order - even changing
     over time).

    Many methods for searching and hashing are inherited from Set.

    Instance variables:

	keyArray        <Array>         (from Set) the keys
	valueArray      <Array>         the values ('valueArray at:index' corresponds
					to the value stored under 'keyArray at:index')

    Performance hints: 
      since the dictionary does not really store associations internally,
      it is less efficient, to store/retrieve associations. The reason is
      that these assocs are created temporarily in some extract methods. 
      I.e. 'at:key put:value' is faster than 'add:anAssoc' 
      and 'keysAndValuesDo:' is faster than 'associationsDo:' etc.

      If only symbols or smallIntegers are used as keys, use IdentityDictionaries
      for slightly better performance, since both hashing and comparison is faster.

      If you have a rough idea how big the dictionary is going to grow,
      create it using #new: instead of #new. Even if the size given is a
      poor guess (say half of the real size), there is some 20-30% performance
      win to expect, since many resizing operations are avoided when associations
      are added.

    See also: Set, IdentityDictionary, IdentitySet, WeakIdentitySet and
	      WeakIdentityDictionary
"
! !

!Dictionary class methodsFor:'instance creation'!

withKeys:keyArray andValues:valueArray
    "return a new instance where keys and values are taken from
     the argumentArrays."

    |newDict sz "{ Class: SmallInteger }"|

    sz := keyArray size.
    newDict := self new:sz.
    keyArray with:valueArray do:[:key :value |
	newDict at:key put:value
    ].
    ^ newDict

    "
     Dictionary withKeys:#('one' 'two' 'three' 'four')
	       andValues:#(1 2 3 4)
    "
!

withKeysAndValues:anArray
    "return a new instance where keys and values are taken from alternating
     elements of anArray"

    |newDict sz "{ Class: SmallInteger }"|

    sz := anArray size.
    newDict := self new:(sz // 2).
    1 to:sz by:2 do:[:i |
	newDict at:(anArray at:i) put:(anArray at:i+1)
    ].
    ^ newDict

    "
     Dictionary withKeysAndValues:#('one' 1 'two' 2 'three' 3 'four' 4)
    "
! !

!Dictionary methodsFor:'accessing'!

associationAt:aKey
    "return an association consisting of aKey and the element indexed 
     by aKey - 
     report an error, if no element is stored under aKey"

    ^ aKey -> (self at:aKey)
!

associationAt:aKey ifAbsent:exceptionBlock
    "return an association consisting of aKey and the element indexed by aKey - 
     return result of exceptionBlock if no element is stored under aKey"

    ^ aKey -> (self at:aKey ifAbsent:[^ exceptionBlock value])
!

associations
    "return an ordered collection containing the receivers associations."

    |coll|

    coll := OrderedCollection new:(keyArray size).
    self associationsDo:[:assoc | coll add:assoc].
    ^ coll
!

at:aKey
    "return the element indexed by aKey - report an error if none found"

    |index|

    aKey isNil ifTrue:[
	"/ nil is not allowed as key
	^ self errorInvalidKey:aKey
    ].

    "/
    "/ I could have written:
    "/ index := self find:aKey ifAbsent:[^ self errorKeyNotFound:aKey]
    "/ but the code below is slighlty more efficient, since it avoids
    "/ a block creation - thus speeding up the good case.
 
    index := self find:aKey ifAbsent:0.
    index ~~ 0 ifTrue:[
        ^ valueArray basicAt:index
    ].
    "no such key"
    ^ self errorKeyNotFound:aKey
!

at:aKey ifAbsent:exceptionBlock
    "return the element indexed by aKey - 
     return result of exceptionBlock if no element is stored under aKey"

    |index|

    aKey isNil ifTrue:[
	"/ nil is not allowed as key
	"/
	"/ previous versions of ST/X raised an error
	"/ here. However, there seem to exist applications
	"/ which depend on getting the exceptionBlocks value
	"/ in this case ... well ...
	"/ ^ self errorInvalidKey:aKey
	^ exceptionBlock value
    ].

    "/ I could have written:
    "/ index := self find:aKey ifAbsent:[^ exceptionBlock value]
    "/ but the code below is slighlty more efficient, since it avoids
    "/ a block creation - thus speeding up the good case.

    index := self find:aKey ifAbsent:0.
    index ~~ 0 ifTrue:[
        ^ valueArray basicAt:index
    ].
    ^ exceptionBlock value.
!

at:aKey put:anObject
    "add the argument anObject under key, aKey to the receiver.
     Return anObject (sigh).
     WARNING: do not add elements while iterating over the receiver.
              Iterate over a copy to do this."

    |index "{ Class: SmallInteger }" |

    aKey isNil ifTrue:[
        "nil is not allowed as key"
        self errorInvalidKey:aKey
    ] ifFalse:[
        index := self findKeyOrNil:aKey.
        (valueArray basicAt:index) notNil ifTrue:[
            valueArray basicAt:index put:anObject.
            ^ anObject
        ].
        keyArray basicAt:index put:aKey.
        valueArray basicAt:index put:anObject.
        tally := tally + 1.

        self fullCheck.
    ].
    ^ anObject

    "Modified: 19.4.1996 / 11:19:45 / cg"
!

keyAtEqualValue:aValue
    "return the key whose value is equal (i.e. using #= for compare)
     to the argument, nil if none found.
     This is a slow access, since there is no fast reverse mapping.
     NOTICE:
	The value is searched using equality compare; 
	use #keyAtValue: to compare for identity."

    ^ self keyAtEqualValue:aValue ifAbsent:[nil]
!

keyAtEqualValue:aValue ifAbsent:exceptionBlock
    "return the key whose value is equal (i.e. using #= for compare) 
     to the argument, if not found, return the value of exceptionBlock.
     This is a slow access, since there is no fast reverse mapping.
     NOTICE:
	The value is searched using equality compare; 
	use #keyAtValue:ifAbsent: to compare for identity."

    |idx|

    idx := valueArray indexOf:aValue.
    idx ~~ 0 ifTrue:[
	^ keyArray at:idx
    ].

"/  keyArray keysAndValuesDo:[:index :aKey |
"/      (aKey notNil and:[aKey ~~ DeletedEntry]) ifTrue:[
"/          (valueArray at:index) = aValue ifTrue:[^ aKey].  
"/      ].
"/  ].

    ^ exceptionBlock value
!

keyAtValue:aValue
    "return the key whose value is identical (i.e. using #== for compare)
     to the argument, nil if none found.
     This is a slow access, since there is no fast reverse mapping.
     NOTICE:
	The value is searched using identity compare; 
	use #keyAtEqualValue: to compare for equality."

    ^ self keyAtValue:aValue ifAbsent:[nil]
!

keyAtValue:aValue ifAbsent:exceptionBlock
    "return the key whose value is identical (i.e. using #== for compare) 
     to the argument, if not found, return the value of exceptionBlock.
     This is a slow access, since there is no fast reverse mapping.
     NOTICE:
	The value is searched using identity compare; 
	use #keyAtEqualValue:ifAbsent: to compare for equality."

    |idx|

    idx := valueArray identityIndexOf:aValue.
    idx ~~ 0 ifTrue:[
	^ keyArray at:idx
    ].

"/  keyArray keysAndValuesDo:[:index :aKey |
"/      (aKey notNil and:[aKey ~~ DeletedEntry]) ifTrue:[
"/          (valueArray at:index) == aValue ifTrue:[^ aKey].  
"/      ].
"/  ].

    ^ exceptionBlock value
!

keys
    "return a collection containing all keys of the receiver"

    |keySet|

    keySet := self emptyCollectionForKeys.
    keyArray do:[:key | 
	(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
	    keySet add:key
	]
    ].
    ^ keySet
!

values
    "return a collection containing all values of the receiver"

"old:
kk: this fails if the receiver contains nils
    ^ valueArray asBag
new:
"
    |aCollection|

    aCollection := OrderedCollection new:valueArray size.
    self do:[:value| aCollection add:value].
    ^ aCollection
! !

!Dictionary methodsFor:'adding & removing'!

add:anAssociation
    "add the argument, anAssociation to the receiver.

     WARNING: do not add elements while iterating over the receiver.
	      Iterate over a copy to do this."

    self at:(anAssociation key) put:(anAssociation value).
    ^ anAssociation

    "Modified: 1.3.1996 / 21:23:53 / cg"
!

declare:key from:aDictionary
    "if the receiver does not include an association for key,
     take the association from aDictionary and add it to the receiver.
     If aDictionary does not contain such an association, use nil
     as the value of the new dictionary.

     WARNING: do not add elements while iterating over the receiver.
	      Iterate over a copy to do this."

    |value|

    (self includesKey:key) ifFalse:[
	value := aDictionary at:key ifAbsent:nil.
	self at:key put:value.
    ]

    "Modified: 1.3.1996 / 21:24:03 / cg"
!

remove:oldObject ifAbsent:aBlock
    "remove oldObject from the collection and return it.
     If it was not in the collection return the value of aBlock.

     This is blocked here; you have to use one of
     #removeKey:, #saveRemoveKey:, #removeAssociation:,
     #removeValue: or #saveRemoveValue:"

    ^ self shouldNotImplement

    "Modified: 1.3.1996 / 21:21:38 / cg"
!

removeAssociation:assoc
    "remove the association from the collection.
     If it was not in the collection report an error.
     Only the key is used in the passed argument, and a new
     association, for the key and the previously stored value is returned.

     WARNING: do not remove elements while iterating over the receiver.
	      See #saveRemoveKey: to do this."

    |key|

    key := assoc key.
    ^ key -> (self removeKey:key)

    "Modified: 1.3.1996 / 21:21:11 / cg"
!

removeKey:aKey
    "remove the association under aKey from the collection.
     If it was not in the collection report an error.

     WARNING: do not remove elements while iterating over the receiver.
	      See #saveRemoveKey: to do this."

    ^ self removeKey:aKey ifAbsent:[self errorKeyNotFound:aKey]

    "Modified: 1.3.1996 / 21:21:52 / cg"
!

removeKey:aKey ifAbsent:aBlock
    "remove the association under aKey from the collection,
     return the value previously stored there..
     If it was not in the collection return the result 
     from evaluating aBlock.

     WARNING: do not remove elements while iterating over the receiver.
	     See #saveRemoveKey: to do this."

    |index "{ Class:SmallInteger }"
     next  "{ Class:SmallInteger }" 
     oldValue|

    aKey isNil ifTrue:[
	^ self errorInvalidKey:aKey
    ].

    "/   below, I could have written:
    "/      index := self find:aKey ifAbsent:[^ aBlock value]
    "/   but the code below is slighlty more efficient, since it avoids
    "/   a garbage block creation - thus speeding up the good case.

    index := self find:aKey ifAbsent:0.
    index == 0 ifTrue:[^ aBlock value].

    oldValue := valueArray basicAt:index.

    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.
	].
	(keyArray basicAt:next) notNil ifTrue:[
	    keyArray basicAt:index put:DeletedEntry
	].
	self emptyCheck
    ].
    ^ oldValue

    "Modified: 1.3.1996 / 21:21:01 / cg"
!

removeValue:aValue ifAbsent:aBlock
    "remove (first) the association to aValue from the collection,
     return the key under which it was stored previously.
     If it was not in the collection return result from evaluating aBlock.
     The value is searched using equality compare here,
     but identity compare in the IdentityDictionary subclass.

     Notice, this does a linear search through the values and may
     therefore be slow for big dictionaries.

     WARNING: do not remove elements while iterating over the receiver.
	     See #saveRemoveValue: to do this."

    |next  "{ Class:SmallInteger }" 
     oldKey|

    aValue notNil ifTrue:[
	keyArray keysAndValuesDo:[:index :aKey |
	    |idx "{Class:SmallInteger}"|

	    (aKey notNil and:[aKey ~~ DeletedEntry]) ifTrue:[
		idx := index.
		(self compareSame:(valueArray at:idx) with:aValue) ifTrue:[  
		    "found it"
		    valueArray basicAt:idx put:nil.
		    oldKey := keyArray basicAt:idx.
		    keyArray basicAt:idx put:nil.
		    tally := tally - 1.
		    tally == 0 ifTrue:[
			self setTally:0.
			^ oldKey
		    ].
		    idx == keyArray basicSize ifTrue:[
			next := 1
		    ] ifFalse:[
			next := index + 1.
		    ].
		    (keyArray basicAt:next) notNil ifTrue:[
			keyArray basicAt:idx put:DeletedEntry
		    ].
		    self emptyCheck.
		    ^ oldKey
		]
	    ]
	]
    ].
    ^ aBlock value

    "Modified: 1.3.1996 / 21:22:11 / cg"
!

saveRemoveKey:aKey
    "remove the association under aKey from the collection.
     Return the value previously stored there.
     If it was not in the collection return nil.

     In contrast to #removeKey:, this does not resize the underlying collection
     and therefore does NOT rehash & change the elements order.
     Therefor this can be used while enumerating the receiver,
     which is not possible if #removeKey: is used.

     WARNING: since no resizing is done, the physical amount of memory used
	      by the container remains the same, although the logical size shrinks.
	      You may want to manually resize the receiver using #emptyCheck."

    |index "{ Class:SmallInteger }"
     next  "{ Class:SmallInteger }" 
     oldValue|

    aKey isNil ifTrue:[^ nil].

    index := self find:aKey ifAbsent:0.
    index == 0 ifTrue:[^ nil].

    oldValue := valueArray basicAt:index.

    valueArray basicAt:index put:nil.
    keyArray basicAt:index put:nil.

    tally := tally - 1.
    tally ~~ 0 ifTrue:[
	index == keyArray basicSize ifTrue:[
	    next := 1
	] ifFalse:[
	    next := index + 1.
	].
	(keyArray basicAt:next) notNil ifTrue:[
	    keyArray basicAt:index put:DeletedEntry
	].
    ].
    ^ oldValue

    "does NOT work:

	|d|

	d := Dictionary new.
	d at:'one' put:1.
	d at:'two' put:2.
	d at:'three' put:3.
	d at:'four' put:4.
	d at:'five' put:5.
	d at:'six' put:6.
	d at:'seven' put:7.
	d at:'eight' put:8.
	d at:'nine' put:9.
	d keysAndValuesDo:[:k :v |
	    v odd ifTrue:[
		d removeKey:k
	    ]
	].
	d inspect
    "

    "DOES work:

	|d|

	d := Dictionary new.
	d at:'one' put:1.
	d at:'two' put:2.
	d at:'three' put:3.
	d at:'four' put:4.
	d at:'five' put:5.
	d at:'six' put:6.
	d at:'seven' put:7.
	d at:'eight' put:8.
	d at:'nine' put:9.
	d keysAndValuesDo:[:k :v |
	    v odd ifTrue:[
		d saveRemoveKey:k
	    ]
	].
	d inspect
    "

    "Created: 1.3.1996 / 21:14:42 / cg"
    "Modified: 1.3.1996 / 21:14:53 / cg"
!

saveRemoveValue:aValue
    "remove the (first) association to aValue from the collection,
     return the key under which it was stored previously.
     If it was not in the collection return nil.
     The value is searched using equality compare here,
     but identity compare in the IdentityDictionary subclass.

     In contrast to #removeValue:, this does not resize the underlying collection
     and therefore does NOT rehash & change the elements order.
     Therefor this can be used while enumerating the receiver,
     which is not possible if #removeValue: is used.

     WARNING: since no resizing is done, the physical amount of memory used
	      by the container remains the same, although the logical size shrinks.
	      You may want to manually resize the receiver using #emptyCheck."

    |next  "{ Class:SmallInteger }" 
     oldKey|

    aValue notNil ifTrue:[
	keyArray keysAndValuesDo:[:index :aKey |
	    |idx "{Class:SmallInteger}"|

	    (aKey notNil and:[aKey ~~ DeletedEntry]) ifTrue:[
		idx := index.
		(self compareSame:(valueArray at:idx) with:aValue) ifTrue:[  
		    "found it"
		    valueArray basicAt:idx put:nil.
		    oldKey := keyArray basicAt:idx.
		    keyArray basicAt:idx put:nil.
		    tally := tally - 1.
		    tally ~~ 0 ifTrue:[
			idx == keyArray basicSize ifTrue:[
			    next := 1
			] ifFalse:[
			    next := index + 1.
			].
			(keyArray basicAt:next) notNil ifTrue:[
			    keyArray basicAt:idx put:DeletedEntry
			].
		    ].
		    ^ oldKey
		]
	    ]
	]
    ].
    ^ aValue

    "does NOT work:

	|d|

	d := Dictionary new.
	d at:'one' put:1.
	d at:'two' put:2.
	d at:'three' put:3.
	d at:'four' put:4.
	d at:'five' put:5.
	d at:'six' put:6.
	d at:'seven' put:7.
	d at:'eight' put:8.
	d at:'nine' put:9.
	d keysAndValuesDo:[:k :v |
	    v odd ifTrue:[
		d removeValue:v ifAbsent:nil 
	    ]
	].
	d inspect
    "

    "DOES work:

	|d|

	d := Dictionary new.
	d at:'one' put:1.
	d at:'two' put:2.
	d at:'three' put:3.
	d at:'four' put:4.
	d at:'five' put:5.
	d at:'six' put:6.
	d at:'seven' put:7.
	d at:'eight' put:8.
	d at:'nine' put:9.
	d keysAndValuesDo:[:k :v |
	    v odd ifTrue:[
		d saveRemoveValue:v 
	    ]
	].
	d inspect
    "

    "Created: 1.3.1996 / 21:17:10 / cg"
    "Modified: 1.3.1996 / 21:23:04 / cg"
! !

!Dictionary methodsFor:'copying'!

postCopy
    "have to copy the valueArray too"

    super postCopy.
    valueArray := valueArray shallowCopy
! !

!Dictionary methodsFor:'enumerating'!

allKeysDo:aBlock
    "perform the block for all keys in the collection.
     Obsolete: use keysDo: for ST-80 compatibility."

    ^ super do:aBlock
!

associationsDo:aBlock
    "perform the block for all associations in the collection.

     WARNING: do not add/remove elements while iterating over the receiver.
	      Iterate over a copy to do this."

    |key n "{ Class: SmallInteger }"|

    tally == 0 ifTrue:[^ self].
    n := keyArray basicSize.
    1 to:n do:[:index |
	key := keyArray basicAt:index.
	(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
	    aBlock value:(Association key:key value:(valueArray basicAt:index))
	]
    ]

    "Modified: 1.3.1996 / 21:40:49 / cg"
!

collect:aBlock
    "for each element in the receiver, evaluate the argument, aBlock
     and return a Bag with the results.

     WARNING: do not add/remove elements while iterating over the receiver.
	      Iterate over a copy to do this."

    |newCollection|

    newCollection := Bag new.
    self do:[:each |
	newCollection add:(aBlock value:each)
    ].
    ^ newCollection

    "Modified: 1.3.1996 / 21:40:43 / cg"
!

do:aBlock
    "perform the block for all values in the collection.

     WARNING: do not add/remove elements while iterating over the receiver.
	      Iterate over a copy to do this."

    |key n "{ Class: SmallInteger }"|

    tally == 0 ifTrue:[^ self].
    n := keyArray basicSize.
    1 to:n do:[:index |
	key := keyArray basicAt:index.
	(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
	    aBlock value:(valueArray basicAt:index)
	].
    ]

    "Modified: 1.3.1996 / 21:39:18 / cg"
!

keysAndValuesDo:aTwoArgBlock
    "evaluate the argument, aBlock for every element in the collection,
     passing both key and element as arguments.

     WARNING: do not add/remove elements while iterating over the receiver.
	      Iterate over a copy to do this."

    |key n "{ Class: SmallInteger }"|

    tally == 0 ifTrue:[^ self].
    n := keyArray basicSize.
    1 to:n do:[:index |
	key := keyArray basicAt:index.
	(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
	    aTwoArgBlock value:key value:(valueArray basicAt:index)
	].
    ]

    "Modified: 1.3.1996 / 21:39:49 / cg"
!

keysDo:aBlock
    "perform the block for all keys in the collection.

     WARNING: do not add/remove elements while iterating over the receiver.
	      Iterate over a copy to do this."

    ^ super do:aBlock

    "Modified: 1.3.1996 / 21:39:41 / cg"
!

select:aBlock
    "return a new collection with all elements from the receiver, for which
     the argument aBlock evaluates to true. The block gets the individual values
     as its single argument.

     WARNING: do not add/remove elements while iterating over the receiver.
	      Iterate over a copy to do this."

    |newCollection|

    newCollection := self species new.
    self keysAndValuesDo:[:key :value |
	(aBlock value:value) ifTrue:[
	    newCollection at:key put:value
	]
    ].
    ^ newCollection

    "
     |d|

     d := Dictionary new.
     d at:#foo put:#bar.
     d at:#bar put:#baz.
     d at:#baz put:#foo.

     d select:[:el | el startsWith:'b'].
    "

    "Modified: 1.3.1996 / 21:40:17 / cg"
! !

!Dictionary methodsFor:'inspecting'!

inspectorClass
    "redefined to use DictionaryInspector
     (instead of the default Inspector)."

    ^ DictionaryInspectorView
! !

!Dictionary methodsFor:'printing & storing'!

displayString
    "return a string for displaying"

    ^ self stringWith:#displayString
!

printString
    "return a string for printing"

    ^ self stringWith:#printString
!

storeOn:aStream
    "output a printed representation (which can be re-read)
     onto the argument aStream"

    |isEmpty|

    thisContext isRecursive ifTrue:[
	Transcript showCr:'Error: storeOn: of self referencing collection.'.
	aStream nextPutAll:'#recursive'.
	^ self
    ].

    aStream nextPutAll:'('.
    aStream nextPutAll:(self class name).
    aStream nextPutAll:' new'.
    isEmpty := true.
    self keysAndValuesDo:[:key :value |
	aStream nextPutAll:' at:'.
	key storeOn:aStream.
	aStream nextPutAll:' put:'.
	value storeOn:aStream.
	aStream nextPutAll:'; '.
	isEmpty := false
    ].
    isEmpty ifFalse:[aStream nextPutAll:' yourself'].
    aStream nextPut:$)

    "
     Dictionary new storeOn:Transcript

     (Dictionary new at:1 put:'hello'; yourself) storeOn:Transcript
    "

    "
     |d|
     d := Dictionary new.
     d at:1 put:'hello'.
     d at:'hello' put:#world.
     d storeOn:Transcript
    "

    "
     |d|
     d := Dictionary new.
     d at:1 put:'hello'.
     d at:'hello' put:#world.
     d at:2 put:d.
     d storeOn:Transcript
    "
!

stringWith:aSelector
    "common code for printString & displayString"

    |thisString string noneYet|

    string := (self class name) , '('.
    noneYet := true.
    self associationsDo:[:element |
	thisString := element perform:aSelector.
	noneYet ifTrue:[noneYet := false]
	       ifFalse:[thisString := ' ' , thisString].
	string := string , thisString
    ].
    string := string , ')'.
    ^string
! !

!Dictionary methodsFor:'private'!

compareSame:element1 with:element2
    ^ element1 = element2
!

emptyCollectionForKeys
    ^ Set new:(self size)
!

grow:newSize
    "grow the receiver to make space for at least newSize elements.
     To do this, we have to rehash into the new arrays.
     (which is done by re-adding all elements to a new, empty key/value array pair)."

    |key deletedEntry oldKeyArray oldValueArray n
     oldSize  "{ Class:SmallInteger }" 
     newIndex "{ Class:SmallInteger }" |

    oldKeyArray := keyArray.
    oldValueArray := valueArray.

    n := self class goodSizeFrom:newSize.
    oldSize := oldKeyArray size.
    n == oldSize ifTrue:[^ self].

    keyArray := self keyContainerOfSize:n.
    valueArray := self valueContainerOfSize:n.


    deletedEntry := DeletedEntry.
    1 to:oldSize do:[:index |
	key := oldKeyArray basicAt:index.
	(key notNil and:[key ~~ deletedEntry]) ifTrue:[
	    newIndex := self findNil:key.
	    keyArray basicAt:newIndex put:key.
	    valueArray basicAt:newIndex put:(oldValueArray basicAt:index).
	]
    ]
!

rehash
    "rehash contents - is done by re-adding all elements to a new, empty key/value array pair)."

    | oldKeyArray oldValueArray key 
      n        "{ Class:SmallInteger }"
      newIndex "{ Class:SmallInteger }" |

    oldKeyArray := keyArray.
    oldValueArray := valueArray.

    n := keyArray size.
    keyArray := self keyContainerOfSize:n.
    valueArray := self valueContainerOfSize:n.

    1 to:n do:[:index |
	key := oldKeyArray basicAt:index.
	(key notNil and:[key ~~ DeletedEntry]) ifTrue:[
	    newIndex := self findNil:key.
	    keyArray basicAt:newIndex put:key.
	    valueArray basicAt:newIndex put:(oldValueArray basicAt:index).
	]
    ]
!

rehashFrom:startIndex
    "rehash elements starting at index - after a remove.
     NOTE: this method is no longer needed; 
	   the trick using DeletedEntry avoids the need to do this time 
	   consuming operation, making remove pretty fast :-)
    "

    |key i length
     index "{ Class:SmallInteger }" |

    length := keyArray basicSize.
    index := startIndex.
    key := keyArray basicAt:index.
    [key notNil] whileTrue:[
	key ~~ DeletedEntry ifTrue:[
	    i := self findNil:key.
	    i == index ifTrue:[
		^ self
	    ].
	    keyArray basicAt:i put:key.
	    valueArray basicAt:i put:(valueArray basicAt:index).
	    keyArray basicAt:index put:nil.
	    valueArray basicAt:index put:nil.
	].
	index == length ifTrue:[
	    index := 1
	] ifFalse:[
	    index := index + 1.
	].
	key := keyArray basicAt:index.
    ]
!

setTally:count
    "initialize the contents array (for at least count slots)
     and set tally to zero.
     The size is increased to the next prime for better hashing behavior."

    |n|

    n := self class goodSizeFrom:count.
    keyArray := self keyContainerOfSize:n.
    valueArray := self valueContainerOfSize:n.
    tally := 0
!

valueContainerOfSize:n
    "return a container for values of size n.
     Extracted to make life of weak subclasses easier ..."

    ^ Array basicNew:n
! !

!Dictionary methodsFor:'testing'!

includes:anObject
"/ OLD:
"/    "return true, if there is an association in the receiver with the
"/     same key as the argument, anObject.
"/     NOTICE: in contrast to #includesAssociation:, this compares only the key."
"/
"/    ^ self includesKey:(anObject key)

"/ NEW:
    "return true, if the argument, aValue is stored in the dictionary,
     i.e. if there is an associaten, with aValue as value.
     This is a slow search, since there is no fast reverse mapping;
     the values have to be all scanned without any hashing.
     You need a special collection (or two Dictionaries) to get this
     reverse mapping fast."

    ^ self includesValue:anObject
!

includesAssociation:anAssociation
    "return true, if there is an association in the receiver with the
     same key and value as the argument, anAssociation.
     NOTICE: in contrast to #includes:, this compares both key and value."

    |val|

    val := self at:(anAssociation key) ifAbsent:[^ false].
    ^ (self compareSame:val with:anAssociation) value
!

includesKey:aKey
    "return true, if the argument, aKey is a key in the receiver"

    ^ (self find:aKey ifAbsent:0) ~~ 0
!

includesValue:aValue
    "return true, if the argument, aValue is stored in the dictionary,
     i.e. if there is an associaten, with aValue as value.
     This is a slow search, since there is no fast reverse mapping;
     the values have to be all scanned without any hashing.
     You need a special collection (or two Dictionaries) to get this
     reverse mapping fast."

    ^ valueArray includes:aValue
!

occurrencesOf:anObject
    "count & return how often anObject is stored in the dictionary.
     This counts values - not keys."

    ^ valueArray occurrencesOf:anObject
! !

!Dictionary class methodsFor:'documentation'!

version
    ^ '$Header: /cvs/stx/stx/libbasic/Attic/Dict.st,v 1.36 1996-04-19 10:46:37 cg Exp $'
! !