"

 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.

"

"{ Package: 'stx:libbasic' }"

"{ NameSpace: Smalltalk }"

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 an array that 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.

    Special note:

      in previous versions, nil was not allowed as valid key

      This has been changed; internally, a special nil-key is used,

      which is converted back to nil whenever keys are accessed.

    [See also:]

        Set, IdentityDictionary, IdentitySet, WeakIdentitySet and

        WeakIdentityDictionary

    [author:]

        Claus Gittinger

"

!

examples

"

                                                                        [exBegin]

    |d|

    d := Dictionary new.

    d at:'1' put:'one'.

    d at:2 put:'two'.

    d at:2

                                                                        [exEnd]

                                                                        [exBegin]

    |d|

    d := Dictionary new.

    d at:'1' put:'one'.

    d at:2   put:nil.

    d.

    d at:2

                                                                        [exEnd]

                                                                        [exBegin]

    |d|

    d := Dictionary new.

    d at:'1' put:'one'.

    d at:2   put:nil.

    d includes:nil.

                                                                        [exEnd]

                                                                        [exBegin]

    |d|

    d := Dictionary new.

    d at:'1' put:'one'.

    d includes:nil.

                                                                        [exEnd]

                                                                        [exBegin]

    |d1 d2|

    d1 := Dictionary withKeys:#(a b c) andValues:#( 1 2 3).

    d2 := Dictionary newFrom:d1.

    d2.

                                                                        [exEnd]

"

! !

!Dictionary class methodsFor:'instance creation'!

decodeFromLiteralArray:anArray

    "create & return a new instance from information encoded in anArray."

    |dictionary

     sz "{ Class: SmallInteger }"|

    sz := anArray size.

    dictionary := self new:sz//2.

    2 to:sz by:2 do:[:idx | |key val|

	key := (anArray at:idx) decodeAsLiteralArray.

	val := (anArray at:idx+1) decodeAsLiteralArray.

	dictionary at:key put:val

    ].

    ^ dictionary

    "

     (Dictionary new

	 at:1 put:'one';

	 at:2 put:'two';

	 yourself

     ) literalArrayEncoding decodeAsLiteralArray

    "

!

withAssociations:aCollectionOfAssociations

    "return a new instance where associations are taken from the argument"

    |newDict sz "{ Class: SmallInteger }"|

    sz := aCollectionOfAssociations size.

    newDict := self new:sz.

    aCollectionOfAssociations do:[:assoc |

        newDict at:assoc key put:assoc value

    ].

    ^ newDict

    "

     Dictionary withAssociations:{ #'one'->1 .

                                   #'two'->2 .

                                   #'three'->3 .

                                   #'four'->4 }

    "

    "Created: / 11.2.2000 / 10:05:54 / cg"

!

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.

    1 to:sz do:[:index |

        newDict at:(keyArray at:index) put:(valueArray at:index).

    ].

    ^ newDict

    "

     Dictionary withKeys:#('one' 'two' 'three' 'four')

               andValues:#(1 2 3 4)

    "

!

withKeys:aCollection valueBlock:aOneArgBlock

    "return a Dictionary with keys from aCollection's elements,

     using aOneArgBlock to generate the values from aCollection's elements."

    |d|

    d := self new:aCollection size.

    aCollection do:[:each|

        d at:each put:(aOneArgBlock value:each).

    ].

    ^ d

    "

     Dictionary withKeys:#(10 20 30 40 50 60 70 80 90) valueBlock:[:e| e asString]

    "

!

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)

    "

!

withValues:aCollection keyBlock:aOneArgBlock

    "return a Dictionary with values from aCollection's elements,

     using aOneArgBlock to generate the keys from aCollection's elements."

    |d|

    d := self new:aCollection size.

    aCollection do:[:each|

        d at:(aOneArgBlock value:each) put:each.

    ].

    ^ d

    "

     Dictionary withValues:#(10 20 30 40 50 60 70 80 90) keyBlock:[:e| e asString]

    "

! !

!Dictionary class methodsFor:'Compatibility-Squeak'!

newFrom:aCollectionOfAssociations

    "return a new instance where associations are taken from the argument"

    aCollectionOfAssociations isDictionary ifTrue:[

        ^ (self new:aCollectionOfAssociations size)

                declareAllFrom:aCollectionOfAssociations.

    ].    

    ^ self withAssociations:aCollectionOfAssociations

    "

     Dictionary newFrom:{#foo -> #Foo. #bar -> #Bar}

     Dictionary

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

    "

! !

!Dictionary methodsFor:'Compatibility-Dolphin'!

equals:aDictionary

    ^ self = aDictionary

! !

!Dictionary methodsFor:'Compatibility-VW5.4'!

contentsEquals: aDictionary

    "Anwer true if  the receiver and aDictionary contain the same key/values.

     (ignoring the classes)"

    self size == aDictionary size ifFalse: [ ^false ].

    self keysAndValuesDo: [ :key :value |

        ( aDictionary at: key ifAbsent: [ ^false ] ) = value

        ifFalse: [ ^false ]

    ].

    ^ true

! !

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

    ^ self associationAt:aKey ifAbsent:[self errorKeyNotFound: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.

     Warning: this is a comatibility interface only, with a different semantic as

              the original ST80 implementation. The returned assoc is created on the fly,

              and not the one stored in the receiver (there are not assocs there)"

    |index|

    "/ must return the real key in the assoc - not aKey, which might be equal but not identical

    index := self find:aKey ifAbsent:0.

    index ~~ 0 ifTrue:[

        ^ Association key:(keyArray basicAt:index) value:(valueArray basicAt:index)

    ].

    ^ exceptionBlock value

!

associations

    "return an ordered collection containing the receiver's 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"

    ^ self at:aKey ifAbsent:[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 k|

    (k := 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

"/ no longer invalid.

"/      ^ exceptionBlock value

	k := NilEntry

    ].

    "/ 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:k ifAbsent:0.

    index ~~ 0 ifTrue:[

	^ valueArray basicAt:index

    ].

    ^ exceptionBlock value.

!

at:aKey ifAbsent:default update:aBlock

    "update the element stored under aKey with the result from

     evaluating aBlock with the previous stored value as argument, or with default,

     if there was no such key initially.

     I.e. this is the same as self at:aKey put:(aBlock value:(self at:aKey ifAbsent:default)).

     Return the new value stored.

     This is an optimized accessor, which only computes the hash value once."

    |k index "{ Class: SmallInteger }"

     newValue oldKeyArray oldKey|

    (k := aKey) isNil ifTrue:[

        k := NilEntry

    ].

    oldKeyArray := keyArray.

    index := self findKeyOrNilOrDeletedEntry:k.

    oldKey := keyArray basicAt:index.

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

        "/ key is present

        newValue := aBlock value:(valueArray basicAt:index).

    ] ifFalse:[

        "/ a new key

        newValue := aBlock value:default.

    ].

    (keyArray ~~ oldKeyArray or:[(keyArray basicAt:index) ~~ oldKey]) ifTrue:[

        "I have been changed while performing aBlock.

         have to find the key again."

        index := self findKeyOrNil:k.

    ].

    valueArray basicAt:index put:newValue.

    oldKey := keyArray basicAt:index.

    (oldKey isNil or:[oldKey == DeletedEntry]) ifTrue:[

        "key is not or no longer present"

        keyArray basicAt:index put:k.

        tally := tally + 1.

        self possiblyGrow.

    ].

    ^ newValue

    "

     |d|

     d := Dictionary new.

     d at:'one'  ifAbsent:0 update:[:val | val + 1].

     d at:'two'  ifAbsent:0 update:[:val | val + 1].

     d at:'three' ifAbsent:0  update:[:val | val + 1].

     d at:'two' ifAbsent:0  update:[:val | val + 1].

     d at:'three' ifAbsent:0  update:[:val | val + 1].

     d at:'three' ifAbsent:0  update:[:val | val + 1].

     d

    "

    "

     |d|

     d := Dictionary new.

     d at:'two'  ifAbsent:0 update:[:val | val + 1].

     d at:'two'  ifAbsent:0 update:[:val | 1 to:30 do:[:idx| d at:idx printString put:idx]. val + 1].

     d

    "

    "

     |d|

     d := Dictionary new.

     d at:'two'  ifAbsent:0 update:[:val | val + 1].

     d at:'two'  ifAbsent:0 update:[:val | d removeKey:'two'. val + 1].

     d

    "

!

at:aKey ifAbsentPut:valueBlock

    "return the element indexed by aKey if present,

     if not present, store the result of evaluating valueBlock

     under aKey and return it.

     WARNING: do not add elements while iterating over the receiver.

              Iterate over a copy to do this."

    |index "{ Class: SmallInteger }"

     k newValue oldKeyArray probeKey|

    (k := aKey) isNil ifTrue:[

        k := NilEntry

    ].

    index := self findKeyOrNilOrDeletedEntry:k.

    probeKey := keyArray basicAt:index.

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

        "/ key is already present

        ^ valueArray at:index.

    ].

    "/ a new key

    oldKeyArray := keyArray.

    newValue := valueBlock value.

    (keyArray ~~ oldKeyArray or:[(keyArray basicAt:index) ~~ probeKey]) ifTrue:[

        "I have been changed while performing the valueBlock.

         have to find the key again."

        index := self findKeyOrNil:k.

        (keyArray basicAt:index) notNil ifTrue:[

            "/ key was not, but is now present.

            "/ since we executed the valueBlock, overwrite the value in the Dictionary

            valueArray at:index put:newValue.

            ^ newValue

        ].

    ].

    "/ a new key...

    keyArray basicAt:index put:k.

    valueArray basicAt:index put:newValue.

    tally := tally + 1.

    self possiblyGrow.