Class: SmallDictionary

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • accessing - ordered
  • adding
  • copying-private
  • enumerating
  • initialize-release
  • inspecting
  • private
  • queries
  • removing
  • searching
  • testing
  • visiting
• Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--KeyedCollection
         |
         +--SmallDictionary
            |
            +--SmallIdentityDictionary

Package:

stx:libbasic

Category:

Collections-Unordered

Version:

rev: 1.31 date: 2024/03/11 14:20:50

user: cg

file: SmallDictionary.st directory: libbasic

module: stx stc-classLibrary: libbasic

Description:

A lightweight Dictionary implementation (without hashing)
for small dictionaries.

Use this, when you have to store a small number (e.g. < 20) key/value pairs,
assuming that the hash-computation outweights a small number of linear comparisons.
(which obviously depends on the complexity of the keys and the cost of hashing/comparing).

As a side effect of the implementation, the dictionary is also ordered.

Inspired by and compatible with RBSmallDictionary from RefactoryBrowser
(although the implementaion is different).

[instance variables:]
    keysAndValues       Array           keys are stored at odd indices, values at even indices
    tally               SmallInterger   the number of valid key/value pairs

[class variables:]

copyright
COPYRIGHT (c) 2018 by eXept Software AG
             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.

Class protocol:

 new

(comment from inherited method)
return an instance of myself without indexed variables

 new: capacity

(comment from inherited method)
return an instance of myself with anInteger indexed variables

 withKeysAndValues: aSequenceableCollection

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

Usage example(s):

self withKeysAndValues:#(1 one 2 second 3 third) => SmallDictionary(1->#one 2->#second 3->#third)

Instance protocol:

 at: key ifAbsent: aBlock

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

 at: key ifAbsentPut: aBlock

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: key put: value

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.

Usage example(s):

SmallDictionary new at:#test put:'abc'; yourself

 keys

return a collection containing the keys of the receiver

Usage example(s):

|s| s := SmallDictionary new. s at:#a put:'aaa'; at:#b put:'bbb'; at:#c put:'ccc'; at:#d put:'ddd'; at:#a put:'aaaa'. s keys

 order

returns the keys in the order of their appearance

 size

return the number of elements in the receiver.

 values

returns the values in the order of their appearance

Usage example(s):

|s| s := SmallDictionary new. s at:#a put:'aaa'; at:#b put:'bbb'; at:#c put:'ccc'; at:#d put:'ddd'; at:#a put:'aaaa'. s values

 atIndex: index

return an element at a given index

 atIndex: index ifAbsent: aBlock

return an element at a given index

 firstAssociation

Return the first association of the receiver.
Provide an error notification if the receiver contains no elements.

Usage example(s):

SmallDictionary new firstAssociation SmallDictionary new first (SmallDictionary new at:'one' put:1; yourself) firstAssociation (SmallDictionary new at:'one' put:1; yourself) first (SmallDictionary new at:'one' put:1; yourself) firstKey

 firstKey

Return the first key of the receiver.
Raises an error if the receiver contains no elements.

Usage example(s):

OrderedDictionary new firstKey. SmallDictionary new firstKey.

 keyAt: index

return a key at a given index

 last

return the last value

Usage example(s):

SmallDictionary new last

 lastKey

return the last key.
Raises an error if the receiver contains no elements.

Usage example(s):

OrderedDictionary new lastKey. SmallDictionary new lastKey.

 valueAt: index

return an element at a given index

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

 valueAtIndex: index

return an element at a given index

Usage example(s):

OrderedDictionary new valueAtIndex:1. SmallDictionary new valueAtIndex:1.

 add: anAssociation

add the argument, anAssociation to the receiver.
Returns the argument, anAssociation.

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

 add: anAssociation beforeIndex: spot

Add the argument, anAssociation, as an element of the receiver.
Put it in the position just preceding the indexed position spot.
Return anAssociation.

Usage example(s):

|d| d := SmallDictionary withKeysAndValues:#(one 1 two 2 three 3). d add:('new' -> 4) beforeIndex:1. d |d| d := SmallDictionary withKeysAndValues:#(one 1 two 2 three 3). d add:('new' -> 4) beforeIndex:2. d |d| d := SmallDictionary withKeysAndValues:#(one 1 two 2 three 3). d add:('new' -> 4) beforeIndex:3. d |d| d := SmallDictionary withKeysAndValues:#(one 1 two 2 three 3). d add:('new' -> 4) beforeIndex:4. d

 addFirst: anAssociation

Add the argument, anAssociation, to the front. Return anAssociation.

 postCopy

(comment from inherited method)
this is for compatibility with ST-80 code, which uses postCopy for
cleanup after copying, while ST/X passes the original in postCopyFrom:
(see there)

 private privateAppendKey: key value: value

append a key/value pair at the end.
Grow the collection if necessary.

 do: aBlock

enumerate the values

Usage example(s):

(SmallDictionary withKeys:#(one two three four five) andValues:#(1 2 3 4 5)) do:[:each| Transcript showCR:each].

 from: firstIndex to: lastIndex do: aBlock

Evaluate aBlock with each of the dictionary's associations from index
firstIndex to lastIndex as the argument.

Usage example(s):

(SmallDictionary withKeys:#(one two three four five) andValues:#(1 2 3 4 5)) from:2 to:4 do:[:each| Transcript showCR:each]. (SmallDictionary withKeys:#(one two three four five) andValues:#(1 2 3 4 5)) from:1 to:1 do:[:each| Transcript showCR:each].

 keysAndValuesDo: aBlock

(comment from inherited method)
evaluate aBlock for each key and value

 keysAndValuesReverseDo: aBlock

|d|

d := SmallDictionary new.
d at:'one' put:1.
d at:'two' put:2.
d at:'three' put:3.
d at:'four' put:4.
d at:'uno' put:1.
d at:'due' put:2.
d at:'tre' put:3.
d at:'eins' put:1.
d at:'zwei' put:2.
d at:'drei' put:3.
d keysAndValuesReverseDo:[:k :v| Transcript showCR:k].

Usage example(s):

|d| d := SmallDictionary new. d at:'one' put:1. d at:'two' put:2. d at:'three' put:3. d at:'four' put:4. d at:'uno' put:1. d at:'due' put:2. d at:'tre' put:3. d at:'eins' put:1. d at:'zwei' put:2. d at:'drei' put:3. d keysAndValuesReverseDo:[:k :v| Transcript showCR:k].

 keysDo: aBlock

(comment from inherited method)
evaluate the argument, aBlock for every key in the collection.

 initialize: capacity

 inspector2TabLabel
( an extension from the stx:libtool package )

label of the main tab

 inspectorExtraAttributes
( an extension from the stx:libtool package )

extra (pseudo instvar) entries to be shown in an inspector.

 inspectorValueListIconFor: anInspector
( an extension from the stx:libtool package )

returns the icon to be shown alongside the value list of an inspector

 fastSizeOr0

optimization for subclasses that can provide the collection's size in a fast way

 findLast: aBlock ifNone: exceptionValue

(comment from inherited method)
find the index of the last element, for which evaluation of the argument, aBlock returns true.
Return its index or the value from exceptionValue if none detected.

 grow: capacity

(comment from inherited method)
change the receiver's size

 growKeysAndValues

duplicate the capacity

 indexOfKeyInArray: aKey

return the index of aKey

 setKeysAndValues: anArray

 includesKey: aKey

(comment from inherited method)
return true, if the argument, aKey is a key in the receiver

 isEmpty

(comment from inherited method)
return true, if the receiver is empty

 isEmptyOrNil

(comment from inherited method)
return true if I am nil or an empty collection - true here, if the receiver's size is 0,
(from Squeak)

 notEmpty

(comment from inherited method)
return true, if the receiver is not empty

 notEmptyOrNil

(comment from inherited method)
Squeak compatibility:
return true if I am neither nil nor an empty collection.

 speciesForCollecting

like species, but used when doing collect operations.
Redefined for collections which return a different classes object when doing collect.

 empty

RefactoryBrowser compatibility

 remove: anAssociation ifAbsent: anExceptionBlock

Modified (format): / 14-09-2018 / 15:40:44 / Stefan Vogel

 removeAll

(comment from inherited method)
remove all elements from the receiver. Returns the receiver.
This should be reimplemented in subclasses for better
performance.

 removeKey: key ifAbsent: aBlock

}

 removeLast

(comment from inherited method)
remove the last element from the receiver.
Return the removed element.
An error is raised here - it is to be implemented by a concrete subclass.

 identityIndexOfKey: aKey

return the index of aKey

 indexOfKey: aKey

return the index of aKey

 isDictionary

return true, if the receiver is some kind of dictionary;
true returned here - the method is redefined from Object.

 isFixedSize

return true if the receiver cannot grow - this will vanish once
Arrays and Strings learn how to grow ...

 acceptVisitor: aVisitor with: aParameter

dispatch for visitor pattern; send #visitDictionary:with: to aVisitor

Examples:

Creation timing:

{SmallDictionary. Dictionary. OrderedDictionary} do:[:eachClass|
    |keys values dict time|

    keys := #(aaaaa  bbbb cccc dddd ffff gggg hhhh jjjj kkkk llll).
    values := #(1 2 3 4 5 6 7 8 9 10).


    time := TimeDuration toRun:[
        1000000 timesRepeat:[
            dict := eachClass withKeys:keys andValues:values.
        ]
    ].
    Transcript showCR:(eachClass name, ' time: ', time printString).
]


Access timing:

{SmallDictionary. Dictionary. OrderedDictionary} do:[:eachClass|
    |keys values dict time|

    keys := #(aaaaa  bbbb cccc dddd ffff gggg hhhh jjjj kkkk llll).
    values := #(1 2 3 4 5 6 7 8 9 10).

    dict := eachClass withKeys:keys andValues:values.

    time := TimeDuration toRun:[
        1000000 timesRepeat:[
            1 to:keys size do:[:idx|
                dict at:(keys at:idx)
            ]
        ]
    ].
    Transcript showCR:(eachClass name, ' time: ', time printString).
]