4. Collection and Stream Classes

Creating Instances

Collections can be creating using new, new:, with:, and similar protocol. The most basic way to create a new collection is using the 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.

new: anInteger, causes many Collection subclasses to create an instance that is pre-sized to hold anInteger elements. This avoids the need to expand the collection when elements are added. Pre-defining the size during creation is particularly important when creating a hashed collection that will hold a large number of objects. Hashed collections store elements in buckets, and the number of buckets must be increased when the number of objects in the collection reaches a threshold for the number of buckets. These expansions are expensive, since it requires that each element be re-added to the expanded collection at the recomputed hashed location.

Several kinds of Collections can be created as literals, using Smalltalk syntax. Arrays, ByteArrays, Strings and Symbols have literal syntax, and Arrays can also be created at runtime using Array constructors. ByteArrays, Strings and Symbols are discussed in Chapter 5.

Enumerating

Collection defines several methods that enable you to loop through a collection’s elements, evaluating a block for each element in the collection.

• The message do: aBlock is the most general; it evaluates aBlock for each element.
• Methods that iterate through the elements and return collections are collect:, select:, and reject:.

The class of the result collection is often, but not always, the same kind of collection as the receiver. The class methods species, speciesForSelect, and speciesForCollect determine the class of the result.

When sent to SequenceableCollections, these messages preserve the ordering of the receiver in the result. That is, if element a comes before element b in the receiver, then element a will come before b in the result.

• The messages detect:, detect:ifNone:, and any iterate to return a single element, based on the order the collection is enumerated. Enumeration stops after the an element is found.
• The message anySatisfy: enumerates each element, stopping if any is found that meet the block criteria; allSatisfy: enumerates, stopping if any is found that does not meet the block criteria.

To avoid unpredictable consequences, do not add elements to or remove them from a collection while you are enumerating it.

Conflicting updates

Due to the transactional nature of GemStone (see Chapter 9, “Transactions and Concurrency Control”), overlapping updates by two sessions may conflict, in which case the second update has failed and the work needs to be repeated.

There are some kinds of conflicts that, while they modify the same object, are not really conflicts in a logical sense. GemStone provides a number of different collection classes that avoid specific kinds of conflicts; these are described under Reduced-Conflict Collection Classes.

Visibility and ordering

When you add an element to a collection, this change does not become visible to other users until you have successfully committed the transaction. While it is important in a multiuser system to avoid long periods in a transaction prior to commit, the requirements are application specific and there may be minutes or hours between the time an object is created and when it is finally committed and visible to other users. Other users, in turn, must abort or commit before they see the changes.

For ordinary (non-reduced conflict) collections, this means that object changes may become visible to other users some time after the change is actually made.

For reduced-conflict sequenceable and queue classes, the order of objects in the collection may depend on the order of the commit, rather than the order of the time in which the object was created.

Internal Dictionary Structure

For performance reasons, the internal implementation of Dictionary classes varies. Instances of Dictionary itself consist of a collection of Association objects. KeyValueDictionary subclasses are implemented differently, as a sequence of keys and values, which may use CollisionBuckets to hold the actual values. IdentityDictionary is a sequence of keys and Associations. All these dictionaries understand common protocol, regardless of implementation.

Dictionary and KeyValueDictionary

Dictionary class uses Associations to store the key/value pair, while subclasses of KeyValueDictionary are slot-based. 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.

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

Copying

When copying a very large instance of a subclass of SequenceableCollection, it can be more efficient to use the method replaceFrom:to:with:startingAt:, which does not fault the contents into memory. This can improve performance significantly for very large collections.

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

Note that, while the replace method does not itself fault the contents into memory, displaying the results as in the example also faults the objects into memory.

Array

One of the most important differences between client Smalltalk arrays and a GemStone Smalltalk array is that GemStone arrays are extensible; you can increase the size of an array at any time. Sending at:put: will increase the size of the array, as long as the index is only one greater than the current array size. Other protocol such as addAll: also increase the size while adding elements.

It’s also possible to change the size without explicitly storing or removing elements, using the message size: inherited from class Object. When you lengthen an array with size:, the new elements are set to nil.

#( 'carrot' 'tomato' 'celery')

{ Date today . Time now }

SortedCollection

SortedCollection is a type of SequenceableCollection in which the elements are ordered by a specific sort order, not by the order in which they were added or by the method used to add the element. You may not send at:put:, addLast:, or similar methods to a SortedCollection.

Each instance of SortedCollection is associated with a sortBlock. The default block will sort elements that can be compared using <=, which includes strings and numbers. You can also define your own sortBlock, if you want elements ordered by some other criteria, such as the value of an instance variable.

For more on comparison, sorting, and sort blocks, see Sorting the objects in a collection.

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

PositionableStream and Position

PositionableStream, with its subclasses ReadStream and WriteStream, was traditionally implemented in GemStone with the position indicating an offset from 1; that is, the first position in the stream was 1.

ANSI specifies, and other Smalltalk dialects use, an offset of 0, so the first position in the stream is 0.

To allow both sets of classes to be available for use, while either one or the other uses the actual class name, GemStone includes the multiple sets of classes, implementing both interfaces. There are four sets of classes, which all exist in the image (and therefore, may have instances), with only three sets being visible at any time. The following two sets are always visible:

• Legacy-style PositionableStream classes, compatible with previous GemStone version’s PositionableStream classes:

PositionableStreamLegacy

	ReadStreamLegacy

	WriteStreamLegacy

• ANSI-compliant and portable PositionableStream classes:

PositionableStreamPortable

	ReadStreamPortable

	WriteStreamPortable

	ReadWriteStreamPortable

In addition, only one of the following sets is visible, depending on how your system is configured. These are two distinct sets of instances of Class, with the same name, but different implementations.

PositionableStream (with legacy definition and methods)

	ReadStream

	WriteStream

PositionableStream (with portable definition and methods)

	ReadStream

	WriteStream

Note that there are other classes within the PositionableStream hierarchies; these examples are simplified for clarity.

The legacy versions are stored in Globals at: #GemStone_Legacy_Streams. The portable, ANSI-compatible versions are stored in Globals at: #GemStone_Portable_Streams.

To check what is currently installed, use the following methods:

PositionableStream class >> isLegacyStreamImplementation 

PositionableStream class >> isPortableStreamImplementation

To install the portable version, use the method:

Stream class >> installPortableStreamImplementation

To install the legacy version, use the method:

Stream class >> installLegacyStreamImplementation

AppendStream

AppendStream is a kind of Stream that does not maintain a position. It is designed to optimize a common use-case for streams: composing long, complex blocks of text and returning the resulting string.

Like WriteStream, you can add strings and characters to an AppendStream, and like any stream, you can get the entire contents. Many other methods commonly associated with Stream classes are not available, however.

ReadByteStream

ReadByteStream is a kind of Stream that is optimized for reading strings and ByteArrays.

Union, Intersection, and Difference

Subclasses of UnorderedCollection provide messages that perform set arithmetic: union, set intersection, and set difference.

+ union, returning elements that are in either one, the other, or both.

- difference, returning elements that are in the receiver but not the argument.

* intersection, returning elements that are in both

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

| bagOfRodents |

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

'chipmunk' 'guinea pig').

(Array new: 5) replaceFrom: 3 to: 5  

with: bagOfRodents startingAt: 1.

 anArray( nil, nil, 'guinea pig', 'chipmunk', 'agouti')

RcIdentityBag

The class RcIdentityBag provides much of the same functionality as IdentityBag, but with no conflict for multiple sessions that add objects to the bag, and a single session that removes objects.

RcLowMaintenanceIdentityBag

RcLowMaintenanceIdentityBag is similar to RcIdentityBag in behavior, but does not require regular cleanup. Rather than using a per-session subcollection of add and remove elements, RcLowMaintenanceIdentityBag relies on replay to resolve conflicts. Like RcIdentityBag, it has no conflict for multiple sessions that add objects to the bag, and a single session that removes objects.

The cumbersome name is intended to be temporary, with this implementation replacing RcIdentityBag’s subcollection-based implementation in some future release.

RcIdentitySet

The class RcIdentitySet is similar to IdentitySet, but no conflict occurs when multiple users add objects to an RcIdentitySet. If a conflict with other update operations on the RcIdentitySet occur, the add is replayed so that the commit can succeed.

Example 4.4 FIFO Queue

| pipe |

pipe := RcPipe new.

pipe add: 'orange'.

pipe add: 'apple'.

pipe add: 'banana'.

pipe remove.

pipe.

%

 aRcPipe( 'apple', 'banana')

GsPipe

The class GsPipe implements a first-in-first-out queue, with no conflict when a single session adds objects to the RcPipe, and only one session removes objects.

Internally, the GsPipe is implemented as a linked list of GsPipeElements. Since adds and removes only affect the respective ends of the linked list, there is no conflict between add and remove.

RcPipe

The class RcPipe implements a first-in-first-out queue, with no conflict when multiple sessions add objects to the RcPipe, and only one session removes objects.

Internally, the RcPipe is implemented as a linked list of GsPipeElements. Unlike with GsPipe, if a conflict with an add by another session occurs, the add operation is replayed so that the commit can succeed. Only add: and operations that invoke add: are reduced conflict.

RcQueue

The class RcQueue implements a first-in-first-out queue, with no conflict when multiple sessions add objects to the RcQueue, and only one session removes objects.

RcQueue has a more complex internal implementation, which allows it to handle high rates of concurrent updates without affecting performance. However, some usage conditions make is necessary to perform manual cleanup

Example 4.6 SmallInteger and String sorting

(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')

The default sort of Strings is case-insensitive, unless the only difference is case in which uppercase is first. However, in many cases you may need a different ordering, particularly when languages other than English and character outside the ASCII range are involved. GemStone provides specialized tools for this, which are described in Chapter 5.

The options depend on the type of data in your collection.

• Sort based on predefined order of the objects. Some objects, such as Strings, Integers, and DateTimes, have an inherent sort ordering, and GemStone provides default sorts for Collections that contain only objects that can be compared using <=.

While strings have intuitive sort order, string sorting can be complex. Traditional and Unicode strings handle some cases differently. String sorting is described in String Sorting and Collation.

• Sort based on one or more of the predefined order of objects’s instance variable values. The sort you intend is based on the values in application objects instance variables, and these values have inherent sort order, such as sorting customers by zip code.
• Arbitrary Sort. sortBlocks allow you to specify expressions that can order any type of object according to your specific requirements.

These issues are the same when using a SortedCollection, which always maintains sort order as elements are added and removed, or when sorting another kind of collection for presentation.

Example 4.7 Employee class and AllEmployees

Object subclass: 'Employee'

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

	classVars: #()

	classInstVars: #()

	poolDictionaries: #()

	inDictionary: UserGlobals

Employee compileMissingAccessingMethods

UserGlobals at: #AllEmployees put: (	IdentityBag 

	with: (Employee new firstName: 'Lee'; lastName: 'Smith';

				job: #librarian; age: 40)

	with: (Employee	 new firstName: 'Kay'; lastName: 'Adams';

			job: #clerk; age: 24) 

	with:		(Employee new firstName: 'Al'; lastName: 'Jones';

			job: #busdriver; age: 40))

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

| sorted str |

str:= String new. 

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

sorted do: [:anEmp | 

	str add: (anEmp age asString); space; add: anEmp lastName; lf].

str

%

24 Adams

40 Jones

40 Smith

Sorting in multiple orders

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

| sorted str |

str := String new. 

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

                                 'lastName' 'Descending').

sorted do: [:anEmp | str add: (i age asString);

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

str

%

24 Adams

40 Smith

40 Jones

Example 4.10 Sorting large collections, committed incremental results

UserGlobals at: #SortedEmployees put: Array new.

System commitTransaction.

AllEmployees 

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

	persistentRoot: SortedEmployees