4. Collection and Stream Classes

Creating Instances

Collection classes respond to the instance creation message new. When sent to a Collection class, this message causes a new instance of the class with no elements (size zero) to be created. Most kinds of collections can expand as you add additional objects.

Another instance creation message, new: anInteger, causes many Collection subclasses to create an instance that is pre-sized to hold anInteger elements. It’s often more efficient to use new: than new, because a Collection created with new: need not expand repeatedly as you add new elements. This is particularly significant for large key-based Collections where the hash must be computed for each element in the collection when the Collection base size changes. For very large collections, growing may require a large amount of temporary object memory to complete, with the risk of running out of memory.

Collections also define the instance creation message, withAll: aCollection, that creates a new instance of the receiver containing all of the objects stored in aCollection, and with:, with:with:, with:with:with:, and with:with:with:with:, which create a new instance of the receiver with 1, 2, 3 or 4 (respectively) specific elements.

Adding Elements

Collection defines for its subclasses two basic methods for adding elements: add:, which adds one element to the Collection, and addAll:, which adds several elements to the Collection at once.

Collection subclasses override these methods in order to control access to elements or to enforce an ordering scheme. Certain subclasses of Collection provide additional methods that add an element at a numbered positions or based on an arbitrary key.

Removing Elements

Collection defines for its subclasses several methods for removing elements: remove:, which removes one element to the Collection, and removeAll:, which removes a collection of elements from the Collection at once.

While it is an error to remove objects that are not in the collection, the methods removeIfPresent: and removeAllPresent: perform the same removals, but do not error if the specified objects or objects are not in the collection.

Enumerating

Collection defines several methods that enable you to loop through a collection’s elements. The most general enumeration message is do: aBlock. When you send a Collection this message, the receiver evaluates the block repeatedly, using each of its elements in turn as the block’s argument.

Suppose that you made an instance of Array in this way:

UserGlobals

	at: #Virtues

	put: { 'humility' . 'generosity' . 'patience' }. 

This defines a Array constructor - an Array that is created containing the three given literal strings.

To create a single String to which each virtue has been appended, you could use the message do: aBlock like this:

| aString |

aString := String new. "Make a new, empty String."

"Append a virtue, followed by a space, to the new String"

(Virtues sortAscending) do: [:aVirtue | 

	aString := aString , ' ' , aVirtue]. 

^ aString

%

' generosity humility patience'

Dictionary

Dictionary class uses Associations to store the key/value pair. Dictionaries compare keys by equality, not by identity. If you need a dictionary that compares keys by identity, use IdentityDictionary, which is a subclass of KeyValueDictionary.

KeyValueDictionary

KeyValueDictionary has several subclasses, divided according to the type of key used to access the information:

• IdentityKeyValueDictionary
• IntegerKeyValueDictionary
• StringKeyValueDictionary
• SymbolKeyValueDictionary
• IdentityDictionary
• SymbolDictionary

KeySoftValueDictionary

A KeySoftValueDictionary is a subclass of KeyValueDictionary that allows the virtual machine to remove entries as needed to free up memory.

Typically, you might use a KeySoftValueDictionary to manage non-persistent objects that are large and take time to create, but that can be recreated whenever needed from small, readily available objects (tokens). For example, you might create a KeySoftValueDictionary to serve as a cache to hold large, expensive objects that are needed repeatedly. Within that dictionary, the values would be the large calculated objects, and the keys would be the corresponding tokens. If your application needs a large, expensive object but does not find it in the KeySoftValueDictionary, you can create the object and add it to the cache so that it might be available the next time it is needed.

As memory fills up, the virtual machine might remove some objects from the cache. (Remember, the contents of the cache are non-persistent and can be recreated.) The virtual machine may remove keys and values from the KeySoftValueDictionary until adequate memory is available. For details about how to manage the number of KeySoftValueDictionary entries, see Getting Rid of Non-Persistent Objects.

Bear in mind the following:

• Entries are removed from a KeySoftValueDictionary only if there are no strong references to the entry’s value.
• If an entry in a KeySoftValueDictionary is cleared, all other entries that reference this value directly or indirectly will also have been cleared.
• Before generating an OutOfMemory error, the virtual machine removes all KeySoftValueDictionary entries that are eligible for removal.
• KeySoftValueDictionary entries are cleared during a mark/sweep operation, but are not cleared during a scavenge. For more about mark/sweep and scavenge operations, see the “Managing Growth” chapter of the System Administration Guide.
• A corresponding subclass, IdentityKeySoftValueDictionary, uses identity (rather than equality) comparison on keys. For details, see the image.
• A KeySoftValueDictionary frequently contains instances of SoftReference. Do not be tempted to confuse this with the notion of WeakReference found in many Smalltalk dialects; the two mechanisms are quite different.

Adding and Removing Objects for SequenceableCollection

SequenceableCollection redefines add: so it puts the added object at the end of the receiver.There are additional methods for adding one or more objects to its instances at particular locations, and for removing one or more objects according to position, equality, or identity.

Comparing SequenceableCollection

SequenceableCollection redefines the comparison methods inherited from Object so that those methods take into account the classes of the collections to be compared and the number and order of their elements. In order for two SequenceableCollections to be considered equal, the following conditions must be met:

• The classes of the two SequenceableCollections must be the same.
• The two SequenceableCollections must be of the same size.
• Corresponding elements of the two objects must be equal.

Copying SequenceableCollection

SequenceableCollection understands several copying message, including those that:

• return a sequence of the receiver’s elements as a new collection
• copy a sequence of the receiver’s elements into an existing SequenceableCollection
• copy elements from one SequenceableCollection into another, without faulting the contents into memory.

The following example copies the first two elements of an literal Array to a new Array:

#('bear' 'tiger' 'turtle') copyFrom: 1 to: 2

%

an Array

#1 bear

#2 tiger

This example copies two elements of an array into a different array, overwriting the target array’s original contents:

| numericArray |

numericArray := Array with: 55; with: 66 with: 77 with: 88.

numericArray replaceFrom: 2 to: 3 with: #( 1 2 3 4 5 )startingAt: 4.

numericArray

%

an Array

 #1 55

 #2 4

 #3 5

 #4 88

The advantage of using the method replaceFrom:to:with: startingAt: is that it does not fault the contents into memory, which can improve performance when working with very large collections. Of course, displaying the results as in the example also faults the objects into memory.

Also keep in mind that copies of SequenceableCollection, like most GemStone Smalltalk copies, are “shallow.” In other words, the elements of the copy are not simply equal to the elements of the receiver—they are the same objects.

Enumeration and Searching Protocol

Class SequenceableCollection redefines the enumeration and searching messages inherited from Collection in order to guarantee that they process elements in order, starting with the element at index 1 and finishing with the element at the last index.

SequenceableCollection also defines a new enumeration message, reverseDo:, which acts like do: except that it processes the receiver’s elements in the opposite order.

SequenceableCollections understand findFirst: aBlock and findLast: aBlock. The message findFirst: returns the index of the first element that makes aBlock true, while findLast: returns the index of the last.

Creating Arrays

You are free to create an array with the inherited message new and let the array lengthen automatically as you add elements.

Arrays created with the new message initially allocate no space for elements. As you add objects to such an array, it must lengthen itself to accommodate the new objects. It’s usually more efficient to create your arrays with the message new: aSize (inherited from class Behavior), which makes a new instance of the specified size:

| tenElementArray |

tenElementArray := Array new: 100.

The selector new: stores nil in the indexed instance variables of the empty array. Having created an array with enough storage for the elements you intend to add, you can proceed to fill it quickly.

Literal Array and Array Constructors

Arrays can also be created in code without sending instance creation messages, by using literal array or array constructor syntax.

An Array literal is created with the following syntax:

#( element1 element2 element3 )

When your code includes a statement like this, at compile time an invariant instance of Array is created.

An Array constructor is created at runtime, rather than at compile time, and it not invariant - it can be modified by later code. The syntax for Array constructors is:

{ element1 . element2 . element3 }

Array constructors are not part of the ANSI standard.

Example 4.2

| scrabbleWords |

scrabbleWords := SortedCollection sortBlock: [:a :b | a size < b size]. 

scrabbleWords add: 'able'; add: 'zebra'; add: 'jumper'; add: 'yet'.

scrabbleWords

%

aSortedCollection( 'yet', 'able', 'zebra', 'jumper')

There is overhead in always keeping the collection sorted, so it usually more efficient to sort the elements only when you need them to be sorted for presentation. There are advantages to using a type of collection that is more suitable for managing the elements, then using methods such as sortWithBlock: to create a new Array with the original collection’s elements in sorted order.

Bag and Set

The classes Bag and Set are some of the simplest UnorderedCollections. In these classes duplicate checking is done based on equality (rather than identity), and a Set will ignore attempts to add a equal element. A Bag will accept an equal item but will do so by increasing the count of the existing element. Thus, adding two equal but not identical objects will be treated as if the first object is present twice.

If the Bag or Set contains elements that are themselves complex objects, determining the equality is complex and therefore slower than you might have hoped. GemStone recommends using IdentityBag or IdentitySet for anything but the most simple unordered collections.

IdentityBag

IdentityBag has faster duplicate checking than Bag. Like a Bag, an IdentityBag is elastic and can hold objects of any kind.

To compare an object that is in an IdentityBag, you rely on the identity (OOP) of the object. This is a much less time-consuming task than an equality comparison, and in most cases it should be sufficient for your design.

The inherited messages add: and addAll: work much as they do with other kinds of collection, except, of course, that they are not guaranteed to insert objects at any particular positions. There’s one other significant difference: if the argument to addAll: is an Array or OrderedCollection, the elements in the collection are not faulted into memory.

IdentityBag also defines a method that allow you to copy elements into a Collection (which must be a kind of Array or OrderedCollection) without faulting the contents into memory, using the message:

replaceFrom: startIndex to: stopIndex with: aCollection startingAt: repIndex

| bagOfRodents |

bagOfRodents := IdentityBag withAll: #('beaver' 'rat' 'agouti'

'chipmunk' 'guinea pig').

(Array new: 5) replaceFrom: 3 to: 5  with: bagOfRodents startingAt: 1.

 anArray( nil, nil, 'beaver', 'rat', 'agouti')

| bagOfRodents myRodent |

bagOfRodents := IdentityBag withAll: #('beaver' 'rat' 'agouti'). 

myRodent := bagOfRodents detect: [:aRodent | aRodent = 'agouti'].

myRodent

agouti

| myBag |

myBag := IdentityBag withAll: #(2 3 4 5). 

myBag remove: 3 ifAbsent: [^false]. 

myBag sortAscending.

%

anArray( 2, 4, 5)

| myBag array1 array2 |

"Create two objects that are equal but not identical,

 and add one of them to a new IdentityBag."

array1 := Array new add: 'stuff'; add:'nonsense' ; yourself.

array2 := Array new add: 'stuff'; add:'nonsense' ; yourself.

"Create an IdentityBag containing array1."

myBag := IdentityBag new add: array1.

UserGlobals at: #MyBag put: myBag.   

"Now try to remove one of the objects from the IdentityBag by

referring to its equal twin in the argument to remove:ifAbsent"

myBag remove: array2 ifAbsent: ['Sorry, can''t find it'].

%

Sorry, can’t find it

| pets rodents |

pets := IdentityBag with: 'dog' with: 'cat' with: 'gerbil'.

rodents := IdentityBag with: 'rat' with: 'gerbil' with: 'beaver'.

pets * rodents

%

 anIdentityBag( 'gerbil')

pets + rodents

%

 anIdentityBag( 'beaver', 'rat', 'gerbil', 'gerbil', 'cat', 'dog')

pets - rodents

%

 anIdentityBag( 'cat', 'dog')

IdentitySet

IdentitySet is similar to IdentityBag, except that IdentitySet cannot contain duplicate (that is, identical) elements.

Example 4.8

(Array with: 123 with: 3 with: 99 with: 10) sortDescending

%

 anArray( 123, 99, 10, 3)

(Array with: '123' with: '3' with: '99' with: '10') sortAscending

%

anArray( '10', '123', '3', '99')

It’s more likely that you will want to sort more complex objects in your collection, such as Customers by name or Addresses by zip code. If the instance variables in your complex objects are objects that have a defined sort order, you can take advantage of sortAscending:, sortDescending:, and sortWith:, to provide a specification for the desired sort order.

For example, say we have a class for Employee, and define AllEmployees as a collection that contains instances of Employee:

Example 4.9

Object subclass: 'Employee'

	instVarNames: #( 'firstName' 'lastName' 'job' 'age')

	classVars: #()

	classInstVars: #()

	poolDictionaries: #()

	inDictionary: UserGlobals

%

Employee compileAccessingMethodsFor:

	#('firstName' 'lastName' 'job' 'age').

%

"Make some Employees and store them in a AllEmployees."

| Lee Kay Al myEmployees |

Lee := (Employee new) firstName: 'Lee'; lastName: 'Smith';

   job: #librarian; age: 40.

Kay := (Employee new) firstName: 'Kay'; lastName: 'Adams';

   job: #clerk; age: 24. 

Al := (Employee new) firstName: 'Al'; lastName: 'Jones';

   job: #busdriver; age: 40. 

myEmployees := IdentityBag new.

myEmployees add: Lee; add: Kay; add: Al.

UserGlobals at: #AllEmployees put: myEmployees.

% 

To sort Employees by age and lastName, we can use the sortAscending: method, passing in the instance variables against which the ascending sort should be done:

Example 4.10

| returnArray tempString |

tempString := String new. 

returnArray := AllEmployees sortAscending: #('age' 'lastName').

"Build a printable list of the sorted ages and lastNames" 

returnArray do: [:i | 

	tempString add: (i age asString); add: ' '; add: i lastName; lf].

tempString

%

24 Adams

40 Jones

40 Smith

For finer control, you can use the sortWith: method, which allows you to define direction for each instance variable

Example 4.11

| returnArray tempString |

tempString := String new. 

returnArray := AllEmployees sortWith: #('age' 'Ascending'

                                 'lastName' 'Descending').

returnArray do: [:i | tempString add: (i age asString);

				add: ' '; add: i lastName; lf].

tempString

%

24 Adams

40 Smith

40 Jones

SortBlocks

You can also specify sort ordering by defining a sortBlock. A sortBlock is a two-argument block that should return true if the first argument should precede the second argument, and false if not. The expressions within the block are expected to by symmetrical - i.e., for two specific arguments for which the block returns true, then the block should return false when the arguments are reversed. If values compare equal, and the block returns the same results for both argument orders, then the final ordering of the equal elements is arbitrary.

SortedCollection is a type of Collection that includes a sortBlock; the SortedCollection class is discussed under SortedCollection. You can use sortBlocks to sort the elements of any collection, using methods such as sortWithBlock:.

For example, to sort customers by last name:

AllEmployees sortWithBlock: [:a :b | 

	a lastName <= b lastName]

You can create sort blocks that are as elaborate as you need; however, you should observe the symmetry of the expression.

For example, this block sorts by lastName, with further sorting by firstName if the lastNames are the same:

AllEmployees sortWithBlock: [:a :b | 

	a lastName = b lastName 

		ifTrue: [a firstName <= b firstName]

		ifFalse: [a lastName <= b lastName]

	].

Sorting Large Collections

When sorting using the above methods, the entire collection must fit into memory. This may not be practical for very large collections. To avoid out of memory errors when sorting large collections, you can allow the sort to issue periodic commits, which will make the sort results persistent. Persistent objects don’t need to stay in memory the way temporary objects do, which reduces the demand on memory.

These intermediate commits are enabled by specifying a persistentRoot for the sort, and by taking advantage of the IndexManager’s ability to set up autoCommit. IndexManager is a class that manages Indexes, which you’ll read more about in Chapter 7. You do not need to have an index on the collection in order to use this feature. However, you do need to set IndexManager’s autoCommit setting to true. For more information on autoCommit, see Auto-commit.

For example, the following code sorts AllEmployees collection using sortWithBlock:persistentRoot:

UserGlobals at: #SortedEmployees put: Array new.

System commitTransaction.

AllEmployees 

	sortWithBlock: [:a :b | a lastName <= b lastName]

	persistentRoot: SortedEmployees