Class: Dictionary

• Inheritance
• Description
• Related information
• Class protocol
  • Compatibility-Squeak
  • initialization
  • instance creation
• Instance protocol
  • Compatibility-Dolphin
  • Squeak Compatibility
  • accessing
  • adding & removing
  • comparing
  • converting
  • copying
  • enumerating
  • inspecting
  • printing & storing
  • private
  • searching
  • testing
  • visiting
• Private classes
• Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--Set
         |
         +--Dictionary
            |
            +--CacheDictionary
            |
            +--Comanche::HttpFormDictionary
            |
            +--Dolphin::LookupTable
            |
            +--IdentityDictionary
            |
            +--LookupTable
            |
            +--OrderedDictionary
            |
            +--ResourcePack
            |
            +--WeakValueDictionary

Package:

stx:libbasic

Category:

Collections-Unordered

Version:

rev: 1.101 date: 2010/02/26 10:48:56

user: cg

file: Dictionary.st directory: libbasic

module: stx stc-classLibrary: libbasic

Author:

Claus Gittinger

Description:

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.

Related information:

    Set,
    IdentityDictionary,
    IdentitySet,
    WeakIdentitySet
    and
    WeakIdentityDictionary

Class protocol:

 newFrom: aCollectionOfAssociations

return a new instance where associations are taken from the argument

 initialize

initialize the NilKey singleton

 decodeFromLiteralArray: anArray

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

 withAssociations: aCollectionOfAsociations

return a new instance where associations are taken from the argument

 withKeys: keyArray andValues: valueArray

return a new instance where keys and values are taken from
the argumentArrays.

 withKeysAndValues: anArray

return a new instance where keys and values are taken from alternating
elements of anArray

Instance protocol:

 equals: aDictionary

 hasKeyStartingWith: aString

 associationAt: aKey

return an association consisting of aKey and the element indexed
by aKey -
report an error, if no element is stored under 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

 associations

return an ordered collection containing the receivers associations.

 at: aKey

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

 at: aKey ifAbsent: exceptionBlock

return the element indexed by aKey -
return result of exceptionBlock if no element is stored under aKey

 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.

 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.

 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.

 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

 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.

 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.

 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.

 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.

 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.

 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.

 keys

return a collection containing all keys of the receiver

 values

return a collection containing all values of the receiver.
This is to make value access to an OrderedDictionary compatible with any-Collection

 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.

 addAll: aCollection

ANSI 5.7.2.1:
Message: addAll: dictionary
Synopsis
Store the elements of dictionary in the receiver at the
corresponding keys from dictionary.
Definition: <abstractDictionary>
This message is equivalent to repeatedly sending the #at:put:
message to the receiver with each of the keys and elements in
dictionary in turn. If a key in dictionary is key equivalent
to a key in the receiver, the associated element in dictionary
replaces the element in the receiver.

Returns the argument, aCollection (sigh).

WARNING: do not add elements while iterating over the receiver.
Iterate over a copy to do this.

 addPairsFrom: aSequenceableCollection

merge consecutive key-value pairs from aSequenceableCollection into the receiver.

 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.

Stubidity Notice:
Incompatibility with #declareAllFrom:, where the other values are
defined unconditionally.

WARNING: do not add elements while iterating over the receiver.
Iterate over a copy to do this.

 declareAllFrom: aDictionaryOrNil

merge all key-value pairs from aDictionary into the receiver.

sigh:
For compatibility with #declare:from: the behavior should be changed as following:
If the receiver already contains a key, the existing value is retained.
To keep the compatibility with other smalltalks, the semantics of this remains
as is, and #declareAllNewFrom: was added for convenience.
See #declareAllNewFrom: which does exactly what this name implies.

 declareAllNewFrom: aDictionaryOrNil

merge all new key-value pairs from aDictionary into the receiver
i.e. If the receiver already contains a key, the existing value is retained.
See also #declareAllFrom:

 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:

 removeAllKeys: aKeyCollection

remove all associations under each key in aKeyCollection 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.

 removeAllKeys: aKeyCollection ifAbsent: aBlock

remove all associations under each key in aKeyCollection from the collection.
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.

 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.

 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.

 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.

 removeValue: aValue

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, report an error.
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.

 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.

 saveRemoveKey: aKey

remove the association under aKey from the collection.
Return the value previously stored there.
If it was not in the collection return nil.

In contrast to #removeKey:, this does not resize the underlying collection
and therefore does NOT rehash & change the elements order.
Therefor this can be used while enumerating the receiver,
which is not possible if #removeKey: is used.

WARNING: since no resizing is done, the physical amount of memory used
by the container remains the same, although the logical size shrinks.
You may want to manually resize the receiver using #emptyCheck.

 saveRemoveValue: aValue

remove the (first) association to aValue from the collection,
return the key under which it was stored previously.
If it was not in the collection return nil.
The value is searched using equality compare here,
but identity compare in the IdentityDictionary subclass.

In contrast to #removeValue:, this does not resize the underlying collection
and therefore does NOT rehash & change the elements order.
Therefore, this can be used while enumerating the receiver,
which is not possible if #removeValue: is used.

WARNING: since no resizing is done, the physical amount of memory used
by the container remains the same, although the logical size shrinks.
You may want to manually resize the receiver using #emptyCheck.

 = aCollection

return true, if the argument is a Dictionary containing the same
key-value pairs as I do

 asDictionary

 fromLiteralArrayEncoding: encoding

read my values from an encoding.
The encoding is supposed to be of the form:
(Dictionary key1 val1 ... keyN valN)

 literalArrayEncoding

 , anotherDictionaryOrAssociation

return a new dictionary containing a merged set of associations.
If anotherDictionaryOrAssociation includes any of the receiver's keys,
the value from anotherDictionaryOrAssociation will be placed into the
returned result.

 postCopy

have to copy the valueArray too

 allKeysDo: aBlock

perform the block for all keys in the collection.
Obsolete: use keysDo: for ST-80 compatibility.

** This is an obsolete interface - do not use it (it may vanish in future versions) **

 associationsCollect: aBlock

for each key-value pair in the receiver, evaluate the argument, aBlock
and return a collection with the results.

See also:
#keysAndValuesCollect: (which passes separate keys & values)
#collect: (which only passes values)

This is much like #keysAndValuesCollect:, but aBlock gets the
key and value as a single association argument.
#keysAndValuesCollect: and is a bit faster therefore (no intermediate objects).

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 associationsDo: aBlock

perform the block for all associations in the collection.

See also:
#do: (which passes values to its block)
#keysDo: (which passes only keys to its block)
#keysAndValuesDo: (which passes keys&values)

This is much like #keysAndValuesDo:, but aBlock gets the
key and value as a single association argument.
#keysAndValuesDo: and is a bit faster therefore (no intermediate objects).

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 associationsReverseDo: aBlock

perform the block for all associations in the collection.
Since dictionary does not define any order of its elements,
this is the same as #associationsDo: here.
Provided for protocol compatibility with OrderedDictionary

 associationsSelect: aBlock

return a new collection with all elements from the receiver, for which
the argument aBlock evaluates to true.
The block gets keys and values as an association argument.

See also: #keysAndValuesSelect: (which is slightly faster),
#select: (which only passes the value)

This is much like #keysAndValuesSelect:, but aBlock gets the
key and value as a single association argument.
#keysAndValuesSelect: and is a bit faster therefore (no intermediate objects).

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 collect: aBlock

for each element in the receiver, evaluate the argument, aBlock
and return a Bag with the results.

See also:
#associationsCollect: (which passes key-value associations)
#keysAndValuesCollect: (which passes keys & values separately)

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 do: aBlock

perform the block for all values in the collection.

See also:
#associationsDo: (which passes key-value associations)
#keysAndValuesDo: (which passes keys & values separately)
#keysDo: (which passes keys only)

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 keysAndValuesCollect: aBlock

for each key-value pair in the receiver, evaluate the argument, aBlock
and return a collection with the results.

See also:
#associationsCollect: (which passes keys->value pairs)
#collect: (which only passes values)

This is much like #associationsCollect:, but aBlock gets the
key and value as two separate arguments.
#associationsCollect: is a bit slower.

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 keysAndValuesDo: aTwoArgBlock

evaluate the argument, aBlock for every element in the collection,
passing both key and element as arguments.

See also:
#associationsDo: (which passes keys->value pairs)
#do: (which only passes values)
#keysDo: (which only passes keys)

This is much like #associationsDo:, but aBlock gets the
key and value as two separate arguments.
#associationsDo: is a bit slower.

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 keysAndValuesSelect: aBlock

return a new collection with all elements from the receiver, for which
the argument aBlock evaluates to true.
The block gets keys and values as separate arguments.

See also:
#associationsSelect: (which passes key-value pairs),
#keysSelect: (which passes key values),
#select: (which only passes the value)

This is much like #associationsSelect:, but aBlock gets the
key and value as two separate arguments.
#associationsSelect: is a bit slower.

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 keysDo: aBlock

perform the block for all keys in the collection.

See also:
#associationsDo: (which passes key-value associations)
#keysAndValuesDo: (which passes keys & values separately)
#do: (which passes values only)

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 keysSelect: aBlock

return a new collection with all elements from the receiver, for which
the argument aBlock evaluates to true.
The block gets the individual keys as its single argument.

See also:
#associationsSelect: (which passes key->value associations),
#keysAndValuesSelect: (which passes key & value args)
#select: (which passes values as arg),

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 select: aBlock

return a new collection with all elements from the receiver, for which
the argument aBlock evaluates to true.
The block gets the individual values as its single argument.

See also:
#associationsSelect: (which passes key->value associations),
#keysAndValuesSelect: (which passes key & value args)
#keysSelect: (which passes key values),

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

 valuesDo: aBlock

perform the block for all values in the collection.
Same as #do: - for VisualWorks compatibility

 inspectorClass

redefined to use DictionaryInspector
(instead of the default Inspector).

 printElementsDo: aBlock

redefined, so #printOn: prints associations

 storeOn: aStream

output a printed representation (which can be re-read)
onto the argument aStream

 compareSame: element1 with: element2

compare two elements for being the same. Here, return true if the
elements are equal (i.e. using #=).
Redefinable in subclasses.

 emptyCollectionForKeys

return an empty collection to hold keys. Here, a Set is returned.
Redefinable in subclasses.

 grow: newSize

grow the receiver to make space for at least newSize elements.
To do this, we have to rehash into the new arrays.
(which is done by re-adding all elements to a new, empty key/value array pair).

 rehash

rehash contents - is done by re-adding all elements to a new, empty key/value array pair).

 rehashFrom: startIndex

rehash elements starting at index - after a remove.
NOTE: this method is no longer needed;
the trick using DeletedEntry avoids the need to do this time
consuming operation, making remove pretty fast :-)

 setTally: count

initialize the contents array (for at least count slots)
and set tally to zero.
The size is increased to the next prime for better hashing behavior.

 valueContainerOfSize: n

return a container for values of size n.
Extracted to make life of weak subclasses easier ...

 findFirstKey: aBlock

find and return the first key, for which evaluation of the argument, aBlock
returns true; return nil if none is detected.

 includes: anObject

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.

 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.

 includesEqualValue: 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.

 includesIdenticalValue: 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.

 includesKey: aKey

return true, if the argument, aKey is a key in the receiver

 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.

 occurrencesOf: anObject

count & return how often anObject is stored in the dictionary.
This counts values - not keys. Uses #= (i.e. equality) compare.

 acceptVisitor: aVisitor with: aParameter

Private classes:

    NilKey

Examples:

    |d|

    d := Dictionary new.
    d at:'1' put:'one'.
    d at:2 put:'two'.
    d at:2    

    |d|

    d := Dictionary new.
    d at:'1' put:'one'.
    d at:2   put:nil.
    d.
    d at:2  

    |d|

    d := Dictionary new.
    d at:'1' put:'one'.
    d at:2   put:nil.
    d includes:nil.  

    |d|

    d := Dictionary new.
    d at:'1' put:'one'.
    d includes:nil.