"

 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