"

 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.

"

!

version

    ^ '$Header: /cvs/stx/stx/libbasic/Dictionary.st,v 1.28 1995-11-11 14:28:21 cg Exp $'

!

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

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)

    "

!

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)

    "

! !

!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

!

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

!

occurrencesOf:anObject

    "count & return how often anObject is stored in the dictionary.

     This counts values - not keys."

    ^ valueArray occurrencesOf:anObject

! !

!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

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

    index := self find:aKey ifAbsent:0.

    index == 0 ifTrue:[

	"no such key"

	^ self errorKeyNotFound:aKey

    ].

    ^ 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

	"/

	"/ 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 ([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: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

!

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

    "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

!

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

! !

!Dictionary methodsFor:'adding & removing'!

add:anAssociation

    "add the argument, anAssociation to the receiver"

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

    ^ anAssociation

!

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

    |value|

    (self includesKey:key) ifFalse:[

	value := aDictionary at:key ifAbsent:nil.

	self at:key put:value.

    ]

!

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"

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

!

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:aKey

    ] 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 using identity compare."

    |next  "{ Class:SmallInteger }" |

    aValue notNil ifTrue:[

	keyArray keysAndValuesDo:[:index :aKey |

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

		(self compareSame:(valueArray at:index) with:aValue) 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