The Question Mark - blog by Mark Volkmann

Smalltalk supports a large number of collection classes. Collection elements can be any kind of object, including other collections.

The Cuis Smalltalk base image contains 60 subclasses of the Collection class. The following list depicts the partial class hierarchy of those:

• Collection
  • SequenceableCollection
    • ArrayedCollection
      • Array
      • ByteArray
      • ColorArray
      • FloatArray
      • IntegerArray
        • PointArray
    • Heap
    • Interval
    • LinkedList
    • OrderedCollection
      • SortedCollection
  • Bag
  • Set
    • Dictionary
      • OrderedDictionary
• Array2D - a two-dimensional array
• SharedQueue

Association

Some programming languages provide a Pair data type that represents a collection of a pair of values. Smalltalk provides two of these.

Instances of the Point class represents a pair of numbers with accessor methods x and y. Sometimes these represent 2D Cartesian coordinates. Sometimes these represent a width and height. But they can be used for any pair of numbers.

Instances of the Association class represents a key/value pair where the keys and values can be any kind of object. These are used by several other classes including Dictionary and Bag.

An Association instance can be created in the following ways:

a := Association key: someKey value: someValue.
a := someKey -> someValue.

The message -> is defined in the Object class which make it easy to create an Association with any object as the key.

The following table describes some of the instance methods defined in the Association class and its superclass LookupKey.

Collection

The following table describes some of the class methods defined in the Collection class. These must be called on a concrete subclass, not on Collection.

The following table describes some of the instance methods defined in the Collection class.

Collections support binary messages that operate on all the elements and return a new array containing the results. For example, #(1 2 3) * 2 returns #(2 4 6).

The allSatisfy: method can be used to verify whether all the characters in a String are digits before asking for the value as a number. For example:

someString allSatisfy: [:char | char isDigit] :: ifTrue: [
    number := someString asNumber.
    ...
]

The fold: method uses the first element as the initial value and folds in the remaining elements. The inject:into: method takes an initial value and folds in all the elements.

The following code demonstrates some of the methods described above:

#('red' 'green' 'blue') asCommaStringAnd "gives 'red, green and blue'

#(1 2 3 4) mean` "gives Fraction 5/2"

numbers := #(1 2 3 4).
numbers collect: [:n | n * 2]. "#(2 4 6 8)"
numbers select: [:n | n odd]. "#(1 3)"
numbers inject: 0 into: [:acc :n | acc + n]. "10"

I implemented the method asOxfordCommaAnd so the example above gives 'red, green, and blue;.

SequenceableCollection

There are no particularly interesting class methods in the SequenceableCollection class.

The following table describes some of the instance methods defined in the SequenceableCollection class that are not defined in the Collection superclass.

All indexes are 1-based.

In polynomialEval:, the first element is the constant, the second is the x coefficient, the third is the x^2 coefficient, and so on.

The following code demonstrates using the do:displayingProgress: method.

c := #(10 20 30 40 50).
delay := Delay forSeconds: 1.
c do: [:n |
    ('processing {1}' format: {n}) print.
    delay wait.
] displayingProgress: 'doing stuff'

ArrayedCollection

There are no particularly interesting methods in this class.

Array

Array instances are fixed-length, ordered collections. They are indexed starting at 1, not 0. Elements cannot be added or deleted, but they can be modified.

Most of the interesting Array methods are defined in the superclasses SequenceableCollection and Collection.

Compile-time literal arrays begin with #(, end with ), and contain space-separated expressions. The expressions can be literal values or expressions whose values can be determined at compile-time. For example, #(true 7 'Tami' (Color red)).

Compile-time literal arrays cannot contain references to variables or other expressions whose values cannot be determined until run-time. The expression #(a b c) is not interpreted as an array containing the values of the variables a, b, c. It is instead interpreted as an array containing the symbols #a, #b, and #c.

Run-time literal arrays (a.k.a. dynamic arrays) begin with {, end with }, and contain dot-separated expressions. For example, {name. breed}. This is an alternative to the more verbose syntax Array with: name with: breed. A common error is to separate expressions with commas instead of periods.

To create an array of a given size where the initial value of all the elements is nil, send the message #ofSize: to the Array class. For example, rgb := Array ofSize: 3.

To create an array of a given size where the initial value of all the elements is the same non-nil value, send the message #new:withAll: to the Array class. For example, rgb := Array new: 3 withAll: 255.

The following table describes some of the instance methods defined in the Array class that are not defined in its superclasses.

To create an array of numbers from a range, send the #asArray message to a Range. For example, (1 to: 5) asArray returns #(1 2 3 4 5).

In addition to the Array class that can hold values of any type, there are predefined, type-specific array classes including ByteArray, ColorArray, DoubleByteArray, DoubleWordArray, Int16PointArray, FloatArray, Float32Array, Float32PointArray, Float64Array, IntegerArray, PointArray, RunArray, RunNotArray, and WordArray.

Interval

Instances of the Interval class represent a finite arithmetic progression. This is a sequence of numbers where the difference between consecutive terms is constant. An example is the numbers 2, 4, 6, and 8.

The Interval class is a subclass of SequenceableCollection which is a subclass of Collection.

The following table describes some of the class methods defined in the Interval class.

The following table describes some of the instance methods defined in the Interval class that are not also defined in superclasses.

LinkedList

LinkedList instances represent a singly-linked list of Link subclasses. Custom Link subclasses must be defined. For example, the StringLink class defined below has a single instance variable named “value”.

Link subclass: #StringLink
    instanceVariableNames: 'value'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Volkmann'!

The StringLink class has the following class method for creating instances.

value: aString
    | link |
    link := self new.
    link setValue: aString.
    ^ link

The StringLink class has the following instance methods.

setValue: aString
    value := aString

value
    ^value

value: aString
    value := aString

We can now create an instance of LinkList whose links are StringLink instances.

list := LinkedList new.
list addLast: (StringLink value: 'banana').
list addLast: (StringLink value: 'cherry').
list addFirst: (StringLink value: 'apple').

"Output all the link values which are apple, banana, and cherry."
list do: [:link | link value print].

list size print. "3"

('first is {1}' format: {list first value}) print. "apple"
('last is {1}' format: {list last value}) print. "cherry"

list removeLast. "removes cherry"

"Output all the link values which are apple and banana."
list do: [:link | link value print].

Link instances have the methods nextLink and nextLink: to get and set the link to which they refer. In addition to the LinkedList methods described below, these can be used to insert new Link instances into a LinkedList.

The following table describes some of the instance methods defined in the LinkedList class that are not also defined in superclasses.

OrderedCollection

The OrderedCollection class is a subclass of SequenceableCollection. Instances are variable-length, ordered collections that can contain duplicates.

To create an OrderedCollection from an array, send the #newFrom: message. For example, fruits := OrderedCollection newFrom: #('apple' 'banana' 'cherry')

To create an OrderedCollection of a given size where the initial value of all the elements is nil, send the message #ofSize: to the OrderedCollection class. For example, players := OrderedCollection ofSize: 4.

To get the number of elements, send the #size message. For example, fruits size returns 3.

To get an element at a specific position send messages like #first, #last, and #at: which takes a 1-based index. For example, fruits first returns 'apple', fruits last returns 'cherry', and fruits at: 2 returns 'banana'.

To add an element to the end, send the #add message. For example, fruits add: 'date'.

To add an element at a specific index, send the #add:beforeIndex: or #add:afterIndex message. For example, fruits add: 'orange' beforeIndex: 3.

To remove an element at a given 1-based index send the #removeAt message. For example, fruits removeAt: 3 removes 'cherry'.

To get the index of the first occurrence of a given value, send the #indexOf: message. For example, fruits indexOf: 'banana' returns 2.

The following table describes some of the instance methods defined in the OrderedCollection class that are not also defined in superclasses.

The following code creates an instance of OrderedCollection containing Symbol objects that are names of fruits. It then sorts them on their length.

oc := OrderedCollection newFrom: #(#banana #watermelon #cherry #apple #plum).
oc sort: [:a :b | a size < b size].

SortedCollection

The SortedCollection class is a subclass of OrderedCollection. Instances keep their elements in sorted order. The element objects must implement the <= instance method.

The following code demonstrates defining a Dog class whose instances can used as elements in a SortedCollection.

Object subclass: #Dog
    instanceVariableNames: 'breed name'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Volkmann'

"class methods follow"

name: nameString breed: breedString
    ^self new setName: nameString breed: breedString

"instance methods follow"

breed
    ^ breed

name
    ^ name

<= aDog
    ^ self name <= aDog name

setName: nameString breed: breedString
    name := nameString.
    breed := breedString

The following code demonstrates creating a SortedCollection of Dog objects and printing their names.

comet := Dog name: 'Comet' breed: 'Whippet'.
oscar := Dog name: 'Oscar' breed: 'German Shorthaired Pointer'.
dogs := SortedCollection newFrom: {oscar. comet}.
dogs do: [:dog | dog name print]

The output in the Transcript will be “Comet” followed by “Oscar”.

Bag

Bag instances are variable-length, unordered collections that can contain duplicates. Elements are stored in a dictionary where the keys are the objects and the values are their number of occurrences.

The following table describes some of the instance methods defined in the OrderedCollection class that are not also defined in the superclass Collection.

The following code creates a Bag instance containing String fruit names, including many duplicates. It then sends several messages to the Bag.

b := Bag newFrom: #('apple' 'banana' 'cherry' 'apple' 'cherry' 'apple').
b sortedCounts print.
b sortedElements print.
b withOccurrencesDo: [:obj :count |
   ('{1} occurs {2} times.' format: {obj. count}) print
].

The code above produces the following output in the Transcript:

a SortedCollection(3 -> 'apple' 2 -> 'cherry' 1 -> 'banana')
a SortedCollection('apple' -> 3 'banana' -> 1 'cherry' -> 2)
cherry occurs 2 times.
apple occurs 3 times.
banana occurs 1 times.

Set

Set instances are unordered collections of unique values. The elements must supports the = and hash messages and cannot be nil.

To create an empty Set:

set := Set new

To create a Set that is populated from an Array:

set := Set newFrom: #('apple' 'banana' 'cherry' 'apple')

The following code demonstrates adding an element, removing an element, and testing for the existence of an element:

set add: `orange`.
set remove: 'banana'.
set includes: 'apple`. "true"
set includes: 'banana`. "false"

Numbers in a Set are compared based on their values, not considering the classes of which they are instances. For example, the SmallInteger value 2, the Float value 2.0, and the Fraction value 6/3 are all considered equal, so only one of those values can be present in a Set.

Dictionary

Dictionary instances are collections of key/value pairs. The keys are often symbols, but they can be any kind of object that supports the = and hash messages. The values can be any kind of object.

To create a Dictionary:

dict := Dictionary new.

"Can populate from a run-time Array of Association objects."
dict := Dictionary newFrom: { k1 -> v1. k2 -> v2. ... }.

dict := { k1 -> v1. k2 -> v2. ... } asDictionary.

It is not possible to create a Dictionary instance from a compile-time Array of Association objects because Association objects cannot be created at compile-time. This means the following cannot be used:

#( k1->v1 k2->v2 ... )

To add a key/value pair:

dict at: #key put: value.
dict add: key -> value.

To get the value for a key:

value := dict at: #key
value := dict at: #key ifAbsent: defaultValue
value := dict at: #key ifAbsentPut: defaultValue

If a default value is not provided and the key is not found, an Error window will open that says “key not found”.

To get all the keys, values, or associations:

ks := dict keys.
vs = dict values.
as = dict associations.

To iterate over the values:

dict do: [:value | value print].

To iterate over the keys and values:

dict associationsDo: [:assoc |
    Transcript
        show: assoc key;
        show: ' ';
        show: assoc value;
        cr
].

The following table describes some of the instance methods defined in the Dictionary class that are not also defined in the superclasses Set or Collection.

One way to delete an entry from a Dictionary is to inspect it, right-click a key in the left column, and select “Remove”. There are also context menu items to add and rename keys.

The at:ifAbsentPut method can be used to implement memoized methods that avoid computing their result if the same arguments have been passed before. The following code demonstrates this by adding the Object instance method memoize: which takes a block. This caches previously computed values in an IdentityDictionary that is saved in Smalltalk which is also an IdentityDictionary.

memoize: aBlock
    "Cache the result of evaluating a method with specific arguments.
    This intended for use in class methods that only use their arguments.
    To clear the cache for all methods in a given class, send
    Object clearMemo: 'SomeClassName'"
    | cache cacheKey sender valueKey |

    sender := thisContext sender.

    "Smalltalk is a SystemDictionary which is an IdentityDictionary.
    That is why cacheKey must be a Symbol."
    cacheKey := ('memo-', sender name) asSymbol.

    cache := Smalltalk at: cacheKey ifAbsentPut: [ IdentityDictionary new ].
    valueKey := thisContext name, sender arguments asString :: asSymbol.

    ^ cache at: valueKey ifAbsentPut: [ aBlock value ].memoize: aBlock

Using the memoize: method is demonstrated in the class method indentDepth: (added to any class) which takes an integer and returns a string with four times that number of spaces.

indentDepth: aNumber
    ^ self memoize: [
        String new: aNumber * 4 withAll: Character space.
    ]

Here is another class method that uses memoize: to avoid repeated computations:

fibonacci: anInteger
    ^ self memoize: [
        anInteger = 0 ifTrue: [ 0 ]
        ifFalse: [ anInteger = 1 ifTrue: [ 1 ]
        ifFalse: [ (self fibonacci: (anInteger - 1)) + (self fibonacci: (anInteger - 2)) ] ]
    ]

OrderedDictionary

The OrderedDictionary class is a subclass of Dictionary. Instances remember the order in which entries were added. Iteration methods like do:, keysDo: and associationsDo: and valuesDo:. process the entries in that order.

The following code demonstrates creating an OrderedDictionary whose values are objects from the Dog class defined the SortedCollection section above, and printing their names.

comet := Dog name: 'Comet' breed: 'Whippet'.
oscar := Dog name: 'Oscar' breed: 'German Shorthaired Pointer'.
dict := OrderedDictionary new.
dict at: comet name put: comet.
dict at: oscar name put: oscar.
dogs do: [:dog | dog name print]

The output in the Transcript will be “Comet” followed by “Oscar”.

Indexable Classes

Classes whose instances respond to messages like #at:put: are “indexable”. This means they hold a collection of objects that are accessed by index. Such classes are defined with by sending the message #variableSubclass:instanceVariableNames:classVariableNames:poolDictionaries:category: to another class. That is handled by an instance method in the class Class. An example of a class that is defined this way is Array.

Also see the Class instance methods whose names begin with variableByteSubclass:, variableDoubleByteSubclass:, variableDoubleWordSubclass:, and variableWordSubclass:.

See the instance method instSpec in the Behavior class which defines values for the format instance variable. The values 2 and 3 indicate that the object in indexable.

Identity Collections

The collection classes IdentityBag, IdentityDictionary, and IdentitySet are similar to their non-identity counterparts, but differ in that elements are compared using == instead of =. This means they check whether objects are the same memory rather than checking for equal values. The advantage is that this check can be done more quickly.

They use hash values returned by the ProtoObject instance method identityHash. TODO: Does this use the memory address of the object?

Weak Collections

The collection classes WeakArray, WeakKeyDictionary, WeakIdentityKeyDictionary, WeakValueDictionary, WeakSet, and WeakIdentitySet are similar to their non-week counterparts, but they differ in that objects to which they refer are not prevented from being garbage collected if they are only referred to by weak collections.

If an attempt is made to use an element in one of these collections that has been garbage collected, its value will be nil.

For example, create a class named WeakSetDemo with the instance variable set and the following instance methods:

initialize
    | comet oscar |
    comet := Dog name: 'Comet' breed: 'Whippet'.
    oscar := Dog name: 'Oscar' breed: 'GSP'.
    set := WeakSet newFrom: {comet. oscar}.
    set do: [:dog | dog name print].

first
    ^ set asArray first

Enter the following lines in a Workspace, select them, and “Print it”:

demo := WeakSetDemo new. "invokes initialize"
demo first

The result will be nil because the comet and oscar objects will be garbage collected after the initialize method executes.

Conversions

Many collection classes have instance methods whose names begin with “as” that create a different type of collection containing its elements.

Highlights include:

• asArray: answers Array representation of any kind of Collection
• asBag: answers Bag representation of any kind of Collection
• asDictionary: answers Dictionary representation of any kind of Collection whose elements are Association instances
• asOrderedCollection: answers an OrderedCollection representation of any kind of Collection
• asSet: answers a Set representation of any Collection, removing duplicates
• asSortedCollection: answers SortedCollection representation of any Collection

In addition, the asJsonString method answers a JSON String representation of any kind of collection.

Common Abbreviations

For method arguments and variables whose values are expected to be a kind of collection, it’s useful to include the least restrictive kind of collection that is suitable in the name of the argument or variable. For example, it’s rarely the case that an Array is required and often the case that any kind of SequenceableCollection will suffice.

The names of many of the collection classes are long. I recommend using the following abbreviations in variable names.