eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'SmallDictionary':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: SmallDictionary


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:

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

o  new: capacity
(comment from inherited method)
return an instance of myself with anInteger indexed variables

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

accessing
o  at: key ifAbsent: aBlock
return the element indexed by aKey -
return result of exceptionBlock if no element is stored under aKey

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

o  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

o  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    

o  order
returns the keys in the order of their appearance

o  size
return the number of elements in the receiver.

o  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    

accessing - ordered
o  atIndex: index
return an element at a given index

o  atIndex: index ifAbsent: aBlock
return an element at a given index

o  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

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

o  keyAt: index
return a key at a given index

o  last
return the last value

Usage example(s):

        SmallDictionary new last

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

Usage example(s):

     OrderedDictionary new lastKey.
     SmallDictionary new lastKey.

o  valueAt: index
return an element at a given index

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

o  valueAtIndex: index
return an element at a given index

Usage example(s):

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

adding
o  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.

o  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

o  addFirst: anAssociation
Add the argument, anAssociation, to the front. Return anAssociation.

copying-private
o  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)

o  private privateAppendKey: key value: value
append a key/value pair at the end.
Grow the collection if necessary.

enumerating
o  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].

o  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].

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

o  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].    

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

initialize-release
o  initialize: capacity

inspecting
o  inspector2TabLabel
( an extension from the stx:libtool package )
label of the main tab

o  inspectorExtraAttributes
( an extension from the stx:libtool package )
extra (pseudo instvar) entries to be shown in an inspector.

o  inspectorValueListIconFor: anInspector
( an extension from the stx:libtool package )
returns the icon to be shown alongside the value list of an inspector

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

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

o  grow: capacity
(comment from inherited method)
change the receiver's size

o  growKeysAndValues
duplicate the capacity

o  indexOfKeyInArray: aKey
return the index of aKey

o  setKeysAndValues: anArray

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

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

o  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)

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

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

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

removing
o  empty
RefactoryBrowser compatibility

o  remove: anAssociation ifAbsent: anExceptionBlock
Modified (format): / 14-09-2018 / 15:40:44 / Stefan Vogel

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

o  removeKey: key ifAbsent: aBlock
}

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

searching
o  identityIndexOfKey: aKey
return the index of aKey

o  indexOfKey: aKey
return the index of aKey

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

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

visiting
o  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).
]


ST/X 7.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Tue, 10 Dec 2024 21:09:10 GMT