"

 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' }"

Set subclass:#Dictionary

	instanceVariableNames:'valueArray'

	classVariableNames:'NilKey'

	poolDictionaries:''

	category:'Collections-Unordered'

!

Object subclass:#NilKey

	instanceVariableNames:''

	classVariableNames:'TheOneAndOnlyInstance'

	poolDictionaries:''

	privateIn:Dictionary

!

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

    Special note:

      in previous versions, nil was not allowed as valid key

      (due to the inheritance from Set, which still does not allow for

       nil elements).

      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]

"

! !

!Dictionary class methodsFor:'initialization'!

initialize

    "initialize the NilKey singleton"

    NilKey isNil ifTrue:[

        NilKey := Dictionary::NilKey new

    ].

    "

     Dictionary initialize

    "

! !

!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:aCollectionOfAsociations

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

    |newDict sz "{ Class: SmallInteger }"|

    sz := aCollectionOfAsociations size.

    newDict := self new:sz.

    aCollectionOfAsociations do:[:assoc |

        newDict at:assoc key put:assoc value

    ].

    ^ newDict

    "

     Dictionary withAssociations:(Array 

                                    with:#'one'->1 

                                    with:#'two'->2 

                                    with:#'three'->3 

                                    with:#'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.

    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 class methodsFor:'Compatibility-Squeak'!

newFrom:aCollectionOfAssociations

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

    ^  self withAssociations:aCollectionOfAssociations

    "

     Dictionary newFrom:(Array with:#foo->#Foo

                               with:#bar->#Bar)

    "

! !

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

    ^ Association key:aKey value:(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"

    ^ Association key:aKey value:(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"

    ^ 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 := NilKey

    ].

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

    (k := aKey) isNil ifTrue:[

        k := NilKey

    ].

    index := self findKeyOrNil:k.

    (keyArray basicAt:index) notNil ifTrue:[

        "/ already present

        ^ valueArray at:index.

    ].

    "/ a new one

    newValue := valueBlock value.

    keyArray basicAt:index put:k.

    valueArray basicAt:index put:newValue.

    tally := tally + 1.

    self fullCheck.

    ^ newValue

    "

     |d|

     d := Dictionary new.

     Transcript showCR:(d at:'foo' ifAbsentPut:'bar').

     Transcript showCR:(d at:'foo2' ifAbsentPut:'bar2').

     Transcript showCR:(d at:'foo' ifAbsentPut:'barX').

     Transcript showCR:(d at:'foo2' ifAbsentPut:'bar2X').

    "

    "Created: / 23.1.1998 / 18:28:26 / cg"

    "Modified: / 26.2.1998 / 19:10:09 / stefan"

!

at:aKey ifPresent:aBlock

    "if the receiver contains an element stored under aKey,

     retrieve it and evaluate aBlock passing the element as argument,

     return the blocks value.

     If not, do nothing and return nil."

    |v|

    v := self at:aKey ifAbsent:[^ nil].

    ^ aBlock value:v.

!

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

    |k index "{ Class: SmallInteger }"|

    (k := aKey) isNil ifTrue:[

        k := NilKey

    ].

    index := self findKeyOrNil:k.

    (keyArray basicAt:index) notNil ifTrue:[

        "/ key already present

        valueArray basicAt:index put:anObject.

        ^ anObject

    ].

    "/ a new key

    keyArray basicAt:index put:k.

    valueArray basicAt:index put:anObject.

    tally := tally + 1.

    self fullCheck.

    ^ anObject

    "Modified: 30.1.1997 / 14:59:10 / cg"

!

at:aKey put:aValue ifPresent:aBlock

    "if the receiver contains an element stored under aKey,

     retrieve it and evaluate aBlock passing the element as argument,

     return the blocks value.

     If not, store aValue under the key. 

     Use this with an error-reporting block, to ensure that no keys are reused"

    (self includesKey:aKey) ifTrue: [ ^ aBlock value ].

    ^ self at:aKey put:aValue.

    "

     |d|

     d := Dictionary new.

     d at:'foo' put:1234 ifPresent:[ self error: 'duplicate' ].

     d at:'foo' put:2345 ifPresent:[ self error: 'duplicate' ].

    "

!

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

    idx := 0.

    [true] whileTrue:[

        idx := valueArray indexOf:aValue startingAt:idx+1.

        idx == 0 ifTrue:[

            ^ exceptionBlock value

        ].

        (k := keyArray at:idx) notNil ifTrue:[

            k ~~ DeletedEntry ifTrue:[

                k == NilKey ifTrue:[

                    ^ nil

                ].

                ^ k

            ].

        ].

    ].

    "/ NOT REACHED

!

keyAtIdentityValue: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 keyAtIdentityValue:aValue ifAbsent:[nil]

!

keyAtIdentityValue: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 k|

    idx := 0.

    [true] whileTrue:[

        idx := valueArray identityIndexOf:aValue startingAt:idx+1.

        idx == 0 ifTrue:[

            ^ exceptionBlock value

        ].

        (k := keyArray at:idx) notNil ifTrue:[

            k ~~ DeletedEntry ifTrue:[