"

 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 comment:'

COPYRIGHT (c) 1991 by Claus Gittinger

	      All Rights Reserved

'!

!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.

"

!

version

"

"

!

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.

    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')

      since the dictionary does not store associations internally,

      If symbols or integers are used as keys, use IdentityDictionaries for slightly

      more performance, since both hashing and comparison is faster.

"

! !

!Dictionary methodsFor:'inspecting'!

inspectorClass

    "redefined to use DictionaryInspector

     (instead of the default Inspector)."

    ^ DictionaryInspectorView

! !

!Dictionary methodsFor:'testing'!

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

!

!

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."

! !

!Dictionary methodsFor:'accessing'!

at:aKey

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

    |index|

    aKey isNil ifTrue:[

	"nil is not allowed as key"

    ].

    "

     I could have written:

     but the code below is slighlty more efficient, since it avoids

     a block creation ([0] is very cheap) - thus speeding up the good case.

    "

    index := self find:aKey ifAbsent:[0].

    index == 0 ifTrue:[

	"no such key"

    ].

    ^ valueArray basicAt:index

!

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"

	^ self errorInvalidKey

    ].

    "

     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 ([0] is very cheap) - thus speeding up the good case.

    "

    index := self find:aKey ifAbsent:[0].

    index == 0 ifTrue:[^ exceptionBlock value].

    ^ valueArray basicAt:index

!

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])

!

at:aKey put:anObject

    "add the argument anObject under key, aKey to the receiver"

    |index|

    aKey isNil ifTrue:[

	"nil is not allowed as key"

	self errorInvalidKey

    ] 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

    ]

!

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

!

associations

    "return an ordered collection containing the receivers associations."

    |coll|

    coll := OrderedCollection new:(keyArray size).

    self associationsDo:[:assoc | coll add:assoc].

    ^ coll

!

keyAtValue:aValue

     This is a slow access, since there is no fast reverse mapping.

     The value is searched for using identity compare."

    ^ self keyAtValue:aValue ifAbsent:[nil]

!

keyAtValue:aValue ifAbsent:exceptionBlock

     This is a slow access, since there is no fast reverse mapping."

    keyArray keysAndValuesDo:[:index :aKey |

	(aKey notNil and:[aKey ~~ DeletedEntry]) ifTrue:[

	].

    ].

    ^ exceptionBlock value

! !

!Dictionary methodsFor:'adding & removing'!

add:anAssociation

    "add the argument, anAssociation to the receiver"

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

    ^ anAssociation

!

remove:oldObject ifAbsent:aBlock

    "remove oldObject from the collection and return it.

     If it was not in the collection return the value of aBlock."

    self shouldNotImplement

!

removeAssociation:assoc

    "remove the association from the collection.

     If it was not in the collection report an error"

    self removeKey:assoc key

!

removeKey:aKey

    "remove the association under aKey from the collection.

     If it was not in the collection report an error"

!

removeKey:aKey ifAbsent:aBlock

    "remove the association under aKey from the collection.

     If it was not in the collection return result from evaluating aBlock"

    |index "{ Class:SmallInteger }"

     next  "{ Class:SmallInteger }" |

    aKey isNil ifTrue:[

	self errorInvalidKey

    ] ifFalse:[

	"

	 I could have written:

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

	 but the code below is slighlty more efficient, since it avoids

	 a block creation ([0] is very cheap) - thus speeding up the good case.

	"

	index := self find:aKey ifAbsent:[0].

	index == 0 ifTrue:[^ aBlock value].

	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

	]

    ]

!

removeValue:aValue ifAbsent:aBlock

    "remove (first) the association to aValue from the collection.

     If it was not in the collection return result from evaluating aBlock.

     The value is searched for using identity compare."

    |next  "{ Class:SmallInteger }" |

    aValue notNil ifTrue:[

	keyArray keysAndValuesDo:[:index :aKey |

	    (aKey notNil and:[aKey ~~ DeletedEntry]) ifTrue:[

		    "found it"

		    valueArray basicAt:index put:nil.

		    keyArray basicAt:index put:nil.

		    tally := tally - 1.

		    tally == 0 ifTrue:[

			self setTally:0.

			^ self

		    ].

		    index == keyArray basicSize ifTrue:[

			next := 1

		    ] ifFalse:[

			next := index + 1.

		    ].

		    (keyArray basicAt:next) notNil ifTrue:[

			keyArray basicAt:index put:DeletedEntry

		    ].

		    self emptyCheck.

		    ^ self

		]

	    ]

	]

    ].

    ^ aBlock value

! !

!Dictionary methodsFor:'copying'!

postCopy

    "have to copy the valueArray too"

    super postCopy.

    valueArray := valueArray shallowCopy

! !

!Dictionary methodsFor:'enumerating'!

keysDo:aBlock

    "perform the block for all keys in the collection."

    ^ super do:aBlock

!

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."

    |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))

	]

    ]

!

do:aBlock

    "perform the block for all values in the collection."

    |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)

	].

    ]

!

keysAndValuesDo:aTwoArgBlock

    "evaluate the argument, aBlock for every element in the collection,

     passing both key and element as arguments."

    |key n "{ Class: SmallInteger }"|