### Execution produces

SortedCollection (98 89 73 56 56 53 21 13)
SortedCollection (13 21 53 56 56 73 89 98)

Although the code sends `sortBlock`: twice, the two messages are different: The first is a *class* method and creates a `SortedCollection` with a non-default sort block, the second is an *instance* method and changes the sort block of the existing `SortedCollection` and resorts it.

### Example 1. Sorting a collection of random numbers

**Problem:** Generate ten random numbers, display them in the Transcript in the order in which they were generated, and then again in the ascending order of their magnitudes. Print the numbers in the format `#.###` where `#` is a digit. An example of the desired output is

```
0.030 0.762 0.421 0.988 0.299 0.048 0.786 0.921 0.718 0.300
0.030 0.048 0.299 0.300 0.421 0.718 0.762 0.786 0.921 0.988
```

**Solution:** The principle is simple:

1. Create a `SortedCollection` with the default sort block.

2. Create a random number generator.

3. Send next to the random number generator ten times and each time display the generated number and add it to the `SortedCollection`.

4. Display the resulting `SortedCollection` in the desired format.

The problem of formatting the output is new. There may already be a method to do this and we thus search the library using the *Implementers Of ...* browser for something like `print...`. We find many matching selectors and one of them is called `print:formattedBy`: which seems promising. It is defined as a class method in `PrintConverter` and the definition shows that it indeed does what we want. As an example,

`PrintConverter print: 3.14567 formattedBy: '#.###'`

returns the string `'3.14'`. With this information, we can solve our problem as follows:

```
| generator number randomNumbers |
"Create a sorted collection and a random number generator."
randomNumbers := SortedCollection new: 10. "Use default sort block."
generator := Random new.
Transcript clear.
"Generate random numbers, print them, and save in sorted collection."
10 timesRepeat: [number := generator next.
Transcript show: (PrintConverter print: number formattedBy: '#.###'), ' '.
randomNumbers add: number].
```

Transcript cr.
"Display all elements of the collection in the desired format."
randomNumbers do: [:element| Transcript show: (PrintConverter print: element formattedBy: '#.###'), '']

We ran the program several times getting a different output each time as expected.

### Example 2: Sorting shopping minder items.

**Problem:** We are to modify the shopping minder from the previous section to display the purchased items in alphabetical order.

**Solution:** We only need to use a `SortedCollection` in `initialize` instead of an `OrderedCollection` to store the items, and the sort block must make comparisons on the basis of the name of the item:

#### initialize
"Initialize items to a suitably sized sorted collection. Sort alphabetically by name."
items := SortedCollection sortBlock: [:item1 :item2| (item1 name) < (item2 name)].
self execute

## Main lessons learned:

* Sorted collections are ordered collections that automatically sort their elements according to a sort block.

* The default sort block uses `<=` but a different sort block can be assigned by a class or an instance message.

* As elements are added to a sorted collection, they are automatically inserted into the proper place according to the sort block.

* Every pair of elements must be able to execute the sort block.

## Exercises

1. Find and examine all references to `sortBlock`: and determine which of them are instance messages: and why they are used.

2. Study and describe how `SortedCollection` adds a new element.

3. Browse `SortedCollectionWithPolicy` and explain how it differs from `SortedCollection`.

4. Formulate the sort block for storing entries of the library catalog from the Section 8.3 in a `SortedCollection` using the alphabetical order of author names. Make up any necessary accessing methods.

5. Write a code fragment to create ten random rectangles and sort them in the order of increasing area.

6. Items are frequently sorted by more than one property. As an example, listings in telephone directories are by last name, and if last names are the same then by first name. Extend the previous exercise by using the area as the primary comparison key, and the circumference as the second comparison key, used when areas are the same.

7. Write a program to let the user compare the speed of execution of selected unary mathematical messages such as `squared`, `ln`, `sin`, and `cos`. Message names are entered by the user. Use `SortedCollection`.

8. Find forms of `perform:` that can be used when the method has one or more arguments and use them to write a more general version of the previous exercise that accepts any mathematical messages. (Hint: Use method keywords to obtain the number of keywords in the selector entered by the user.)

9. Modify the shopping minder to sort items in decreasing order of price.

10. Modify the System Browser to display names of categories in alphabetical order.

11. Ask the user to enter a string pattern and a series of strings, and sort the strings by their similarity to the pattern. As an example, if the user enters pattern 'abcd' and then strings 'abcd', 'abbd', 'aaad', and 'xxxx', one would expect that ordering by similarity will produce 'abcd', 'abbd', 'aaad', and 'xxxx'. (Hint: VisualWorks has a method for measuring the similarity of two strings. It is used by command correct displayed when you misspell the name of a variable. Find it.)

12. Ask the user to enter several labels and display them in alphabetical order in a multiple choice dialog.
## 8.6 The List collection

Class List combines properties of ordered and sorted collections and adds dependency. According to the manual, List is intended to supersede ordered and sorted collections but its main use in the library is as an item holder in multi-item GUI widgets. This is consistent with the placement of List in the UIBasics - Collections category in the library.

In terms of implementation, List is not on the OrderedCollection branch of the Collection subtree, but a subclass of ArrayedCollection. Its instance variables are collection, limit, collectionSize, and dependents.

According to the class comment, collection holds the list's elements and the creation methods initializes it to an Array. This means that List is not itself a collection but contains a collection as one of its components. The role of limit is to hold the index of the last element in the collection that holds a valid element. This is because List makes a distinction between size and capacity and must keep track of how many of its slots are valid elements. collectionSize holds the size of the collection. dependents is nil, one object, or a collection of objects and implements the dependency mechanism: When an object is added or deleted, all dependents are notified.

Lists can be used as sorted collections because they can sort their elements. However, List does not have a sort block and does not automatically insert new elements. Instead, new elements are added using the adding protocol of OrderedCollection, for example addLast: and addFirst:. To sort a List, send it sortWith: aSortBlock or the sort message which uses the default sort block [:a :b | a <= b].

If List does not have a sort block, how can it sort itself? The answer is that a List does not sort itself but asks class SequenceableCollectionSorter to do it. The details are obvious from the following definition of List's sorting methods:

### sort

`^SequenceableCollectionSorter sort: self`

### sortWith: aBlock

`^SequenceableCollectionSorter sort: self using: aBlock`

SequenceableCollectionSorter, a class that knows how to do sorting, is a nice example of object-oriented thinking - an object that can perform a service for its clients.

We will use List when we present widgets that depend on it later in this chapter.

### Main lessons learned:

* List objects resemble ordered and sorted collections and add dependency handling.

* For accessing, lists behave like ordered collections.

* Unlike sorted collections, List does not sort itself automatically but must be explicitly asked to do so.

* A List sorts itself by sending a message to SequenceableCollectionSorter.

* The most common use of lists is as item holders of multi-item GUI widgets.

### Exercises

1. List initializes collection to an Array which is a fixed size collection. What happens when you add a new item? What happens when you remove an element?

2. Write a program to test how sorting time depends on the number of elements in the list. The program should create a list with 10, 100, 1,000, and 10,000 random numbers and send them the sort message. Plot the numbers as a function of the size of the list.

3. Sorted collections insert a new element into its proper place as soon as it is added, lists sort their elements only when explicitly requested to do so. Write a program to compare the speed of the two approaches by creating a sorted collection containing a set of 100, 1,000, and 10,000 random numbers with a List and with a SortedCollection. Create the two collections so that they don't need to grow.
4. Class SequenceableCollectionSorter can be used with any sequenceable collection but its main purpose is to sort List objects, for example to display items in a multi-item widget in a particular order. Write a short description of its behavior and instance variables.

5. Write a comparison of List and OrderedCollection highlighting the similarities and differences in their behavior and implementation.

6. List is one of the few collection classes that are not variable-size classes and that store their elements in an instance variable. What does List gain from being in the Collection tree?

## 8.7 String, Text, and Symbol - an introduction

Classes String, Text, and Symbol are all in essence collections of characters such as letters, digits, and punctuation symbols. A String is a sequence of characters and its functionality includes searches, deletions, and replacements. Strings are concerned with contents and don't contain any information about rendering - font, size, boldness, and so on. When they are displayed ('rendered'), they use default system representation.

A Symbol is also a sequence of characters but the rules for its formation are slightly different and its main use is for selectors - names of methods; this is reflected in its different protocol. Unlike strings, symbols are unique in that only one instance of a particular sequence of characters can exist at a time. This is their most important defining property which guarantees very fast access. Finally, instances of Text are aggregate objects containing a string and information about its emphasis - font, size, color, and other rendering information.

The internal natures of String and Symbol are closely related - both are essentially collections of characters - whereas Text objects are related conceptually but their internal structure is different. This is reflected in the class hierarchy: Classes String and Symbol are on the same branch but Text is separate:

<figure><img src="image_165.png" /></figure>

All three classes inherit many useful methods from the abstract class CharacterArray. We used strings and symbols informally before and we will now present some new information and examples of both. Text will be covered in the next section.

### Class String

String is an abstract class that understands messages such as finding substrings and replacing substrings with other strings. Its superclass is the abstract superclass CharacterArray which means that its elements are characters (instances of class Character). Concrete strings are implemented by concrete subclasses of String, each designed for a different kind of character encoding. In most applications, strings are instances of ByteString which encodes its characters as one-byte ASCII codes. For large character sets requiring more codes, strings can be implemented as TwoByteString objects.

The fact that String is an abstract class and that string objects are instances of one of its concrete subclasses is hidden and you don't have to think about it. This is because when you create a new string as in

```
String new: 20 "String with room for 20 characters"
```
the definition of new: in class String automatically determines which concrete subclass to use as follows:

**new: size**

^self defaultImplementor new: size

Here defaultImplementor is a class method defined as follows:

**defaultImplementor**

"Answer a class that usually represents strings."

^ByteString

As a consequence,

String new: 20

is equivalent to

ByteString new: 20

and all messages to the resulting string object are handled by class ByteString. This trick of using an abstract class as if it were concrete and allowing it to select the most suitable concrete class is used in several places and we will encounter it again later. Its advantage is that applications can be made independent of the concrete class and the same program may be, for example, executed on different platforms that use different defaults.

Most of the interesting protocol of String is defined in CharacterArray. Since String is a collection, it also inherits the rich collection protocol of all its superclasses up to Collection. The most useful methods defined in String include comparison and conversion to text via asText which allows strings to be used where Text objects are expected.

The protocols inherited from CharacterArray include accessing (replacement and search), converting (to number, text, symbol, and other related objects), copying, comparing (alphabetical relations), and displaying on the screen. One example of an accessing message is changeFrom: start to: stop with: replacement which takes the receiver string, removes characters indexed from start to stop, and inserts the string provided as the third argument starting at index start. The replacement string may contain fewer, more or the same number of characters as the specified range of indices and when start > stop, the argument string is simply inserted into the original. Another useful accessing message is findString: substring startingAt: start which searches for the first occurrence of substring starting from start and returns the index of its first character or 0 if the substring is not found. We will now develop a new method using both messages.

**Example 1: Replacing substrings**

*Problem:* Write a method with three string arguments: a start string, a match string, and a replacement string. The method finds all occurrences of the match substring in the start string and substitutes the replacement string for them. The result is returned.

As an example, if the start string is 'a secret 1 containing encoded sub1s' and the match string is '1', and the replacement string is 'string', the program should replace every occurrence of 1 with 'string' and produce 'a secret string containing substrings'.

*Solution:* The basis of the method is the following algorithm:

1. Set starting position to 1.

2. Look for the next occurrence of the match string. If a match is found, make the replacement and repeat this step.
The algorithm is easy to implement because all steps can be implemented with built-in messages.
We will put the method in the *accessing* protocol in *CharacterArray* because it is related to other methods in
this protocol and because it will be useful in subclasses. The definition is as follows:

### replace: matchString with: replacementString

"Replace all occurrence of matchString in string with replacementString."

| index newString matchSize |
newString := self copy.
matchSize := matchString size.
"Find all occurrences and do replacement."
[index := newString findString: matchString startingAt: 1. index = 0]
whileFalse:
  [newString changeFrom: index to: index + matchSize - 1 with: replacementString].
^ newString

Unfortunately, when you try to execute the method, it enters into an infinite loop! The problem is
due to our misunderstanding of the exact operation of `changeFrom:to:with:`. We leave it to you to find and
correct this common error.

### Closing comments

Before we close this very brief introduction to String, here is a useful piece of information. As you
know, the most common way of concatenating two short strings (and many other collections) is with the,
message as in

'abc', 'def' "Returns 'abcdef.'"

However, what if you wanted to concatenate a string with a single character?

'abc', $d

does not work because one cannot concatenate a string with a character. One could, of course, use

'abc', 'd'

but what if the character is calculated or stored in a variable? In this case, you can use the `copyWith:`
message from `SequenceableCollection` which creates a copy of a collection and appends the argument at the
end as in

'abc' copyWith: aCharacter

This works because a string is a collection of characters.

Another comment related to concatenation is that the ``, method is very inefficient. When speed is
important, concatenate strings using streams, a topic covered in Chapter 10. Since concatenation is usually
an essential part of creating a string, streams are essential for *efficient* use of strings in general.

Finally, the concatenation method is defined in `SequenceableCollection` and its use is not limited
to strings. As an example, you can execute

`orderedCollection1`, `orderedCollection2`

### Class Symbol

Symbol is a special kind of String whose literal form is a sequence of characters preceded by the `#`
character as in `#aWidget` or `#aMethod` or even `#'abc def'`. A Symbol must not include characters such as
blank space, tab, line feed or the `#` character itself, unless the string following `#` is a literal string. As an
example, `#ab cd` is not a single Symbol but `#'ab cd'` is - and the apostrophes are *not* a part of it.

Unlike instances of String, Symbols are implemented as *unique* objects. This means that if you
create two or more Symbols consisting of identical characters, they will be stored in memory only once. On
the other hand, if you create two strings consisting of identical characters, they will be stored as two separate objects. As a consequence, two different instances of String may be equal (message =) but not equivalent (message ==), whereas for symbols, equality and equivalence are the same:

'characters' = 'characters' "Returns true."  
'characters' == 'characters' "Returns false."  
#characters = #characters "Returns true."  
#characters == #characters "Returns true."

Because Symbols are unique their comparison uses *equivalence* which, as we know, is fast because it requires only comparison of pointers to internal memory representations. Strings, on the other hand, are normally compared for equality which may be very time consuming. Note that although Symbol defines `==` to be the same as `=` and one could thus use `=` with the same effect, most programmers use `==` because it is faster, eliminating the `=` message send.

Symbols are used mainly for names of methods as in our comparison of speed of number messages, as widget IDs and *Action* and *Aspect* methods (see any `windowSpec` method for an example), and in similar situations in which uniqueness makes sense (such as days of the week, male and female gender, and other non-ambiguous characteristics) and in which the speed of comparison is important. Because one of their main uses is to represent method selectors, class *Symbol* contains a protocol dedicated to recognizing unary, binary, and keyword messages and similar aspects of selectors. The following example illustrates this protocol.

### Example 2: Get information about messages

*Problem:* Write a program to count how many unary, binary, and keyword methods are defined in the instance protocols of *Object*. In addition, find how many of the keyword messages have one argument, how many have two arguments, and so on. Print the result in *Transcript* in the following format:

Total number of methods: 161

Number of unary methods: 81

Number of binary methods: 5

Number of keyword methods: 75

Number of arguments/Number of methods

1: 53

2: 15

3: 5

4: 2

*Solution:* The problem is quite specialized and we will implement it as a code fragment. The implementation will use the following algorithm:

1. Create an ordered collection `keywordMethods` to hold the selectors of all keyword methods.

2. Enumerate over all methods defined in *Object* as follows:

a. If the method is unary, increment the count of unary messages.

b. If the method is binary, increment the count of binary messages.

c. If the method is a keyword method, increment the count and add its selector to `keywordMethods`.

3. Enumerate over all selectors in `keywordMethods` and count the number of methods with one argument, two arguments, and so on. Store the number of keyword messages with one argument in element 1 of `array` counts, the number of keyword messages with two argument in element 2, and so on.

4. Create an array called `keywordCounts` whose size is equal to the maximum number of keywords in `keywordMethods`. Store the number of all keyword messages of size n in the n-th element of this array.

5. Print results.

To implement this algorithm, we must know how to find all methods defined in a class, how to recognize whether they are unary, binary, or keyword methods and determine how many arguments they have. As we have already mentioned, *Symbol* is mainly used for selectors and it contains the selector-related
methods. But how about finding all methods defined in a class? One way to find out is to think of a Smalltalk tool that performs a similar function, and as usual, this tool is the Browser; its class view <operate> menu includes command *find method* which lists all instance or class methods. Its implementation in class *Browser* must know how to find the methods! When you examine *Browser*, you will find that the following definition contains the desired information:

### findMethodAndSelectAlphabetic

"Show a menu of the methods implemented by this class. Select the chosen one."
| chosenSelector selectorCollection |
self changeRequest ifFalse: [^self].
 selectorCollection := self selectedClass organization elements asSortedCollection) size = 0
etc. - the rest is irrelevant for our needs

It seems that the part *organization elements* does what we need. To test it, we execute

### Object organization elements

with *inspect* and find that it returns an array containing all instance methods defined in Object<fnref n="4" />.

The next task is to find Symbol methods that recognize various types of selectors and number of arguments. We find that instance protocol *system primitives* contains methods `isInfix` (recognizes binary messages), `isKeyword` (recognizes keyword messages), and `numArgs` (returns the number of arguments of a keyword message). There is no special method for unary messages but unary messages are those that are not keyword or binary. With this information, we can now convert our algorithm into the following code:

| unaryCount binaryCount keywordCounts keywordMethods methods |
| :----------------------------------------------------------- |
| unaryCount := 0.                                                 |
| binaryCount := 0.                                                 |
| keywordMethods := OrderedCollection new.                      |

"Enumerate over all selectors defined in Object and store their counts in unaryCount, binaryCount, and keywordCount."

(methods := Object organization elements) do:

[:method| method isInfix
  ifTrue: [unaryCount := binaryCount + 1]
  ifFalse: [method isKeyword
    ifTrue: [keywordMethods add: method]
    ifFalse: [unaryCount := unaryCount + 1]].
Transcript clear; show: 'Total number of methods: ', methods size printString; cr; cr;
  show: 'Number of unaryCount methods: ', unaryCount printString; cr;
  show: 'Number of binaryCount methods: ', binaryCount printString; cr;
  show: 'Number of keywordCount methods: ', keywordMethods size printString.

"Create an array to hold counts of keywordCount messages with the same number of arguments. Find its size as the maximum number of arguments over all keywordMethods elements."

keywordCounts := Array new:
  (keywordMethods inject: 0 into: [:max :method | method numArgs max: max]).
keywordCounts atAllPut: 0.
"Calculate the counts and store them in the array."

keywordMethods do:

[:method| size | size := method numArgs.
  keywordCounts at: size put: (keywordCounts at: size) + 1].

"Output results."

Transcript cr; cr; show: 'Number of arguments/Number of methods'; cr.

1 to: keywordCounts size do:

[:number| Transcript show: number printString, ':'; tab;
  show: (keywordCounts at: number) printString; cr]

<footnote n="4">⁴ To find more about organization, read Appendix 1.</footnote>
Note that we calculated the maximum number of arguments over keyword selectors using the `inject:into:` message.

### Main lessons learned:

* String is an abstract sequenceable collection whose elements are character codes.

* Concrete strings are instances of String subclasses, ByteString by default. Selection of the concrete class is transparent and the programmer does not need to pay attention to it unless a larger character set is needed. In that case, a TwoByteString may be used or a new subclass defined.

* The most useful protocols of String include messages to search for substrings and to replace substrings, copy, and compare strings.

* Symbol is a subclass of String that does not allow duplication.

* The main uses of symbols are for method selectors and as widget IDs in GUI specifications.

* Binary messages are also called infix messages.

### Exercises

1. Why didn't we use `self` instead of `newString` in `replace:with:?

2. Does our `replace:with:` method work in all subclasses of `CharacterArray`?

3. Write a method to remove all occurrence of a substring from a given string.

4. List all collections that understand the `,` (comma) concatenation message.

5. Explain the definition of `=` in class `String`.

6. Study the definition of `changeFrom:to:with:` and show how to use it to insert 'xyz' behind the first occurrence of letter $a$ in an existing string, and how to append a substring at the end.

7. One of the frequently used String methods is `withCRs`. Read its definition and find how it is used. Use `withCRs` to display a dialog request window whose prompt has 'Enter your first and last names.' on the first line, and 'Capitalize the first letter of each name' as the second line. Write the message with and without using `withCRs` and comment on the difference between the two styles.

8. Modify the example from the `Symbol` section to gather statistics on all classes in the library. The program should print the total number of unary, binary, and keyword messages in the library, and the selectors of all methods with the largest number of arguments. (Hint: To enumerate over all classes, use message `allClassesDo: from SystemDictionary`.)

9. Repeat the previous exercise for class methods. (Hint: Class methods are instance methods of the class's class and to ask an object what is its class, send it the class message. See Appendix 3 for more.)

10. Executing `aSymbol` as `Symbol` returns `#aSymbol`. What is ('Symbol1 ', 'Symbol2') as `Symbol`?

11. What is the difference between `asString`, `displayString`, and `printString`?

12. How many different characters can be implemented with `ByteString`? How many with `TwoByteString`?

## 8.8 Text - its nature and use

The purpose of `Text` objects is to gather all information necessary to display characters on a display medium such as the computer screen or a printer. Although you can display a `String` without converting it to `Text` because it automatically converts itself to a text object when asked to display itself, using a `Text` is necessary if you want to display the string with a non-default font or color, underlined, large or small, and so on.

`Text` has two instance variables called `string` and `runs`. Variable `string` holds the characters to be displayed (a `String`), and `runs` is an instance of `RunArray` which holds ranges of indices and encoded information about their emphasis. As an example, `runs` might say that the first characters use default style, the next 15 are underlined, and so on. Conversion from styles to actual fonts is performed with a `TextAttributes` object which indicates, for each style, the rendering parameters to be used. The concept of `TextAttributes` is not simple and we will not deal with it in this book.

As an example of a `Text` object, if we specify that string 'abcdefgh' should use emphasis `#bold` for elements 3 to 6, in other words should be displayed as 'abcdefgh', the internal variables are
```
runs = RunArray (nil nil #bold #bold #bold #bold nil nil)
string = 'abcdefgh'
```

where `nil` means default emphasis, in other words default boldness, font, color, and size. Style `#bold` is a code name for a certain font converted to an actual graphical representation when the character is displayed.

The protocol of `Text` contains `accessing`, `emphasis`, `displaying`, `comparison`, `copying`, and other protocols and most of them are *character oriented*. As an example, `accessing` method at: `anIndex` returns the character at location `index` but not its emphasis.

Truly sophisticated display of text requires the understanding of `TextAttributes` and other display characteristics. As we already mentioned, these are detail beyond our scope and we will restrict ourselves to explaining how to create `Text` objects with simple built-in emphases and how to control text color.

The basic message to control emphasis is `emphasizeFrom`: start to: stop with: emphasis where start and stop are the indices of the endpoints of the substring to be emphasized, and emphasis is a `Symbol` representing emphasis - an association specifying color, or an array containing emphasis and possibly color information. Standard emphases symbols include `#bold`, `#italic`, `#large`, `#normal`, `#serif`, `#small`, `#strikeout`, and `#underline`. As the simplest example,

`'Bold text' asText emphasizeFrom: 1 to: 4 with: #bold`

changes the emphasis of the word 'Bold' to `#bold`. Note that we had to convert the string to text before we could send the emphasis message.

When you want to change the color of a string, you must define it as an `Association` object consisting of the symbol `#color` and a value specifying the desired color expressed as a `ColorValue` object. We will have more to say about associations later but for now, use them as in the following example:

`'Bold text' asText emphasizeFrom: 1 to: 4 with: #color -> ColorValue red`

The binary message -> creates an `Association` object with the specified key (here `#color`) and value (here `ColorValue red`). An important point about specifying emphasis is that every message that defines new emphasis overrides the emphasis assigned previously. As an example,

```
| text |
text := 'Bold text' asText.
text emphasizeFrom: 1 to: 4 with: #bold.
text emphasizeFrom: 1 to: 2 with: #italics
```

ends up overriding the `#bold` emphasis for the first two characters with `#italics`. If you want to assign multiple emphasis to a character, you must specify it as an array, as in

```
| text |
text := 'Bold italicized text' asText.
text emphasizeFrom: 1 to: 15 with: #(#bold #italics).
text emphasizeFrom: 5 to: 15 with: #bold
```

or

```
| emphases text |
text := 'Bold italicized red text' asText.
emphases := Array with: #bold with: #italics with: #color -> ColorValue red.
text emphasizeFrom: 1 to: 19 with: emphases
```

As a matter of style, using specific numbers for the start and end index as we did is not usually a good idea because your indices may be wrong and must be recalculated if you change the string.

### Example 1: Experiment with emphasis and labels
Label widgets in user interfaces use text and this example is an experiment with labels, their
change at execution time, and emphasis.

**Problem:** Design an application with the user interface in Figure 8.12. When the user clicks *New label*, a series of prompts requests a string, an emphasis (using multiple choice dialog), and the starting and end index of a substring to which the selected emphasis should be applied. The emphasis selection dialog is repeated until the user clicks *Cancel*. The program then displays the text with the specified emphases in place of the original text 'Label'.

<figure><img src="image_166.png" /><figcaption>Figure 8.12. Desired user interface for Text example.</figcaption></figure>

**Solution:** This very simple application requires only an application model class. After painting the user interface, assign `#label` as the ID to the label widget so that it can be accessed and modified at run time, and install the user interface on an application model. The only method that needs to be written is the *Action* method for the button:

### newLabel

"Get text and emphases and display the label."

|text|

text := (Dialog request: 'Enter new text' initialAnswer: '') asText.

"Get emphases with ranges and apply them."

[] emphasis noSelection |

emphasis := self getEmphasis.

(noSelection := emphasis == #noChoice)

ifFalse: [text := self emphasizeText: text with: emphasis].

noSelection] whileFalse.

"Now send the new label to the builder for immediate display."

(self builder componentAt: #label) widget label: (Label with: text)

The two auxiliary methods used in the definition are

### getEmphasis

"Obtain emphasis through dialog."

Dialog choose: 'Select emphasis for ', text

fromList: #('bold' 'italic' 'underlined')

values: #(#bold #italic #underlined)

lines: 3

cancel: [#noChoice

### emphasizeText: text with: emphasis

"Apply specified emphasis to the text."

[] start end |

start := (Dialog request: 'Start index (', text, ') initialAnswer: '1') asNumber.

end := (Dialog request: 'End index (', text, ') initialAnswer: text size printString) asNumber.

^text copy "We cannot change the argument so we must work on the copy."

emphasizeFrom: start

to: end

with: emphasis

Printing text
There are two ways to print text. The more primitive one is to use the `hardcopy` message, the more sophisticated and more flexible approach uses class `Document`. We will now describe both.

Method `hardcopy` is defined in class `ComposedText` whose instances hold information about the display of text, indentation, spatial properties such as the box in which the text is displayed, and so on. Text objects themselves don't understand `hardcopy` and to display them with `hardcopy`, we must first convert them into `ComposedText`. Altogether, to display text, execute

### text asComposedText hardcopy

The limitation of `hardcopy` is that it prints the whole text in the default style and ignores emphasis. To print text with its emphases, use the `Document` class.

Class `Document` has all the functionality to create documents containing text and graphics on PostScript printers. Its message `toPrinter` sends an instance of `Document` to class `DocumentRenderer` which takes care of the details of transmitting the document to the printer via class `Printer`. Both `Document` and `Printer` contain several interesting examples illustrating their functionality. In the following, we will limit ourselves to showing how to print a `Text` object with its emphasis, and how to print a window displayed on the screen (not relevant to `Text` but useful).

The general procedure for creating a text document and printing it is as follows:

1. Create a new `Document` object using the new message.

2. Use messages `addParagraph` and `addString`: text to define the contents of the document.

3. Close the document with the `close` message.

4. Send the document to the printer using `toPrinter`.

### Example 2: Printing a `Text` object.

**Problem:** Create and print a document containing two consecutive paragraphs. The first paragraph consists of the text

#### Comment for class `Document`:

which is followed by an empty line and the class comment for `Document`. The comment is printed using italics.

**Solution:** Following the general algorithm for creating and printing a document, the code is as follows:

```text
| document string text start stop |
"Construct a Text object for the first line of document."
string := 'Comment for class Document:'.
start := string findString: 'Document' startingAt: 1.
stop := start + 'Document' size - 1.
text := string asText emphasizeFrom: start to: stop with: #(#bold #italic).
"Now go into a block that creates a Document and prints it, waiting until the process has been completed."
Cursor wait "Display a special cursor while the following block is executing."
showWhile:
    [document := Document new. "Create a Document object."  
     document startParagraph. "Do the first paragraph."  
     document addString: text.  
     document startParagraph. "Do the second paragraph with class comment."  
     document addString: (Document comment asText emphasizeAllWith: #italic).  
     "Close Document and send it to the default printer."  
     document close.  
     document toPrinter]
```

Expression `Cursor wait showWhile: aBlock` displays the 'wait' cursor while until the block executes, in our case until the printing process gets under way.
### Example 3: Printing a graphics object

The example method `doTest2` in class `Document` lets the user select a rectangle on the screen and prints it on the printer preceded with a short text. Its definition is as follows:

#### doTest2

"Make a simple PostScript file... a screen dump scaled in a device independent way."

| document |

Cursor wait

showWhile:

[document := Document new.

document startParagraph.

document addItalicHeader: 'Screen dump:' pixelSize: 24.

document addImage: Image fromUser.

document close.

document toPrinter]

The general procedure is the same as in the previous example but a new message called `addImage`: displays the graphics. The image itself is obtained from the user who selects it using crosshair cursors. Note that this method is based on class `Image`.

### Example 4: Extend Example 1 in Appendix 1 to print the window.

**Problem:** Write a method to print the window from Example 1 in Appendix 1 on the printer and add a new button to the window to do this.

**Solution:** We have seen how to print an `Image` using `Document` and the only remaining problem is how to make an `Image` out of a window. First, we need to know how to get hold of the window object. Since the window that we want to print is active when the user clicks the button, we will need to find the currently active window. Realizing that a `Window` object is a collection of widgets, labels, measurements, and other things - and not an `Image` - we must then find how to specify the rectangle occupied on the screen by the window, and how to convert it to an image.

We will start by determining how to identify a rectangle on the screen. We note that our previous example obtains the `Image` by sending `fromUser` to class `Image`. The definition of `fromUser` is as follows:

#### fromUser

"Answer an instance with the same contents as a user-specified rectangle of the default screen."

^Screen default contentsFromUser

As we already know, `Screen default` provides access to the screen, and `contentsFromUser` returns the `Image` drawn by the user on the screen. Its definition is
### contentsFromUser

"Answer an Image with the contents of a user-specified area on my screen."

`^self completeContentsOfArea: Rectangle fromUser`

This shows that if we have a window rectangle (call it `windowRectangle`) we can obtain its rectangle by

`Screen default completeContentsOfArea: windowRectangle`

The next step is to determine how to find the active window and its screen coordinates. Since the window is the active window of our application, we can get it by sending window to the builder. When we try this and *inspect* the window, we find that the returned object is an instance of `ApplicationWindow`. Finally, `ApplicationWindow`'s protocol includes message `getDisplayBox` which returns the window's rectangle. With this last piece of information, we can now write the complete solution of our problem:

### printActiveWindow

"Print currently active window on printer."

`| document window windowRectangle |`

"Find window rectangle."

`windowRectangle := self builder window getDisplayBox.`

`window := Screen default completeContentsOfArea: windowRectangle`

"Create document with window and print it."

`Cursor wait showWhile: "Display special cursor while the following block is evaluating."`

`[document := Document new.`

`document addImage: window.`

`document close.`

`document toPrinter]`

Add a `Print` button to the original interface in the example, add this method to the application model's class as the `Action` of the `Print` button, and test it.

### Main lessons learned:

* Class `Text` adds emphasis to strings, allowing their display in different fonts, sizes, and colors.

* `Text` objects consist of a string and a run array describing character fonts and other rendering parameters.

* `Text` objects are usually obtained by converting a string with `asText`.

* For simple output of text to the printer, convert text to `ComposedText` and send hardcopy. This message ignores emphasis.

* For sophisticated output, possibly including graphics, use class `Document`.

* The builder of an application window provides access to its window.

* Windows know about properties such as screen coordinates of their bounding rectangle.

### Exercises

1. Add button `Color` to Example 1. Clicking `Color` should open another multiple choice dialog listing all available colors. (Hint: See the class protocol of `ColorValue`.)

2. Define `Text` message `allItalic` to italicize the receiver.

3. Explain the operation of message `asText` in class `String`.

4. We simplified the nature of `RunArray` somewhat. Study its class definition and write a more accurate description. Explain why the description displayed by the inspector does not exactly correspond to the definition. Explain why `Text` uses `RunArray` rather than `Array`.

5. Write a description of class `Cursor`.

6. Class `Screen` and its superclasses provide access to some very interesting behaviors and information. Write their description.

7. Implement Example 4.
8. The method `printActiveWindow` does not contain any specific reference to the application example and can be used with any application based on the `UIBuilder`. Move it to a more general class where it could be used by any application, modify it as necessary, and test it.

9. Add a `print` command to the `<window>` menu so that the `printActiveWindow` method can be executed on any window. (Hint: Find currently active window using `Window currentWindow`.)

## 8.9 List widgets

In this section, we will introduce the list widget, both for its own sake and as an illustration of the use of collections. List widgets are available in two varieties - those that allow only one selection at a time, and those that allow multiple selections (Figure 8.13).

*Single selection lists* are much more common and they are used, for example, in the System Browser. Their purpose is similar to that of menus - making a selection - and their advantage over menus is that they allow the user to see the selections at all times - menus must be popped up or dropped down. Menus have the advantage that they don't take up space in the window. *Multiple selection lists* are used, for example, in the Definer in the UI Painter.

In addition to the similarity of the purpose of lists and menus, lists are also related to check boxes and radio buttons: Single selection lists allow one selection at a time, just as radio buttons, except that in a set of radio buttons one is normally always selected which is not required in lists. Multiple lists allow any number of selections, just like check boxes. One would use radio buttons or check boxes when the number of options is small and fixed, lists would be better when the list can change or when the number of choices is large. We will now cover both types of lists starting with single selection lists.

<figure><img src="image_167.png" /><figcaption>Figure 8.13. Single selection list (left) and multiple selection list (right).</figcaption></figure>

*Single selection lists*
The basic behaviors of list widgets are: create a list widget with labels, add a new label, remove an existing label, sense change of selection, get current selection, and access labels.

The model of a single selection list (the object on which the list widget is dependent) is normally an instance of `SelectionInList`. This class has two instance variables called `listHolder` and `selectionIndexHolder`, both instances of `ValueHolder`. Variable `listHolder` holds the list of objects displayed by the widget (a `List` object), and `selectionIndexHolder` holds the index of the currently selected item or 0 if no item is selected. To be able to use single selection lists you need to know that the *Aspect* of the list widget is a `SelectionInList` and that this `SelectionInList` can be created either with message new as in

### SelectionInList new

if the list is not available in a sequenceable, or using with: as in

### SelectionInList with: aSequenceableCollection

where the argument contains the items to be displayed.

To display some information in the list when the window opens, initialize the list holder in the `initialize` method. To obtain the value of the currently selected item, send `selection` (returns currently selected object or `nil`) or `selectionIndex` (returns index of selection or 0) to the list holder. To change the selection programmatically, send `selection`: a `Value` or `selectionIndex`: an `Integer` to the list holder. To obtain the collection of items displayed in the widget, send `list` to the list holder. And to change the displayed list, send `list`: a `SequenceableCollection` with any sequenceable collection containing the objects for its argument. The elements of the collection should be strings. As an example,

### listHolder list: #('line 1' 'line 2' 'line3')

will erase the current labels and replace them with 'line 1' 'line 2' 'line3'.

To ensure that the list notifies the application model when the selection changes, send `onChangeSend:to:` to the `selectionIndexHolder` during initialization, as in

### classList selectionIndexHolder CHANGESEND: #changedClass to: self

### Example 1: Basic list behaviors

**Problem:** Implement an application with the interface in Figure 8.14 such that the window opens with labels 'label 1', 'label 2', 'label 3'. The *Add* button will display a prompt asking the user for a new label and add it to the list, the *Delete* button removes the currently selected label, and the *Print* button displays all labels in the Transcript. Every change of selection displays a notification in the Transcript. The labels must be alphabetically sorted at all times.

<figure><img src="image_168.png" /></figure>
Figure 8.14. User interface for Example 1.

*Solution:* Paint and install the window and the widgets, and name the *Aspect* of the list (we used the name `#labels`). The *Action* methods will be called `add`, `delete`, and `print`. Since we want the window to open with three labels, we must initialize the `SelectionInList` and we will do this in the initialization method. The specification requires that every change in list selection trigger a message to the `Transcript`; we will register this interest in selection changes via the `onChangeSend:` message. The whole definition is as follows:

**initialize**

"Initialize labels in list and register interest in change in list selection."

`labels := SelectionInList with: #('label 1' 'label 2' 'label 3').`

`labels selectionIndexHolder ONCHANGE Send: #printChange to: self`

If you now open the application, it will look exactly like Figure 8.14 but the buttons will not work and any attempt to select a label in the list will open an exception window because we have not defined `printChange` specified as the change message. This method, which is executed whenever the selection changes, simply asks the list for the current selection and sends appropriate output messages to the `Transcript`:

**printChange**

"List selection has changed, print appropriate message to Transcript."

`labels selection isNil`

`ifTrue: [Transcript cr; show: 'no selection']`

`ifFalse: [Transcript cr; show: 'selection is ', labels selection]`

The `delete` method first checks whether we have a selection, and if we do, it deletes the selected label from the list. To do this, we must ask the list for its current labels (message `labels listHolder value`), remove the current selection from it, and assign this modified list as the new list using the `list:` message. It is essential to use `list:` because if we did not, the notification of change would not propagate to the widget and the binding between the `Aspect` and the list could be destroyed. The whole definition is as follows:

**delete**

"Check if there is a selection. If so, delete it from the list."

`labels selection isNil`

`ifFalse: [newList |`

Transcript cr; show: 'deleted ', labels selection.

`newList := (labels listHolder value) remove: labels selection; yourself.`

`labels list: newList]`

Note the use of `yourself` after `remove`: - it returns the modified receiver list. This is necessary because `remove`: modifies its receiver but returns the argument. Without `yourself`, the value of `newList` will be the string containing the deleted label, the widget will treat it as a sequenceable collection of objects, and display its individual characters as strings - instead of displaying the labels. Forgetting `yourself` is a very common mistake.

We used some unnecessary parentheses and an extra temporary variable to make the code more readable. Unfortunately, the method does not work because the `remove:` message is illegal for arrays which is the collection that we specified as underlying the list. To correct this, we convert the array to an ordered collection, changing initialization as follows:

**initialize**

"Initialize labels in list and register interest in change in list selection."

`labels := SelectionInList with: #('label 1' 'label 2' 'label 3') asOrderedCollection.`

`labels selectionIndexHolder ONCHANGE Send: #printChange to: self`

Deletion now works and we can proceed to the `add` method. This method requests a new label from the user and continues much like `delete` except that it adds a new element rather than removing it:
### add

"Request a new label. If one is supplied, add it to the list holder."

| string |

string := Dialog request: 'Enter new item' initialAnswer: "".

string empty

if False: [Transcript cr; show: 'added ', string.

labels list: ((labels listHolder value) add: string; yourself)]

Finally the method to print all labels when the print button is clicked. This method simply obtains the list from the list holder and displays its elements one after another in the Transcript:

### print

"Display all labels in the Transcript."

Transcript cr.

labels listHolder value do: [:item | Transcript show: item; cr]

### Example 2: Class definition browser

*Problem:* Write an application with the user interface in Figure 8.15. The single selection list on the top lists all classes in the library and when the user selects one, its definition appears in the text view at the bottom.

<figure><img src="image_169.png" /><figcaption>Figure 8.15. Definition browser.</figcaption></figure>

*Solution:* As we know, class information is stored in the Smalltalk dictionary, an instance of SystemDictionary. Among its class methods is one called `classNames` which returns an ordered collection of symbols, the names of all classes in the library. Once we have a class, Smalltalk at: `nameSymbol` as in

Smalltalk at: #Array

returns the class corresponding to the symbol.
The next question is how to get the answer when we have the class. One way to find out is to look at the definition of *Browser* because the browser knows how to display a definition. Another possibility is to examine *Class* and other classes in its category because we know that all class information comes from this group. After a bit of searching (alternatively, you could read Appendix 3), we find that class *ClassDescription* has method definition which returns the definition of the class. Since *ClassDescription* is a superclass of *Class*, we can send the message directly to the class. As an example,

*(Smalltalk at: #Array) definition*

returns the definition of class *Array* in the form of a *String*.

We are now ready to implement our task. We paint the interface, *Install* it, and specify and *Define* the properties. The methods that we need include initialization (the window should open with the class list and changes in the selection list must cause changes in the text view), and the change method which responds to a new list selection and displays the definition of the selected class in the text view.

**initialize**

"Define the list holder for the list widget and register interest in selection changes."

classList := SelectionInList with: Smalltalk classNames.

classList selectionIndexHolder ONCHANGE Send: #changedClass to: self

where method *changedClass* responds to a changed class selection in the list, and changes the text displayed in the text view (*Aspect* definition). The same effect can be achieved by specifying *Notification* properties in the Properties of the List widget in the UI Painter. The definition of the message is

**changedClass**

"Class selection has changed. Blank the text view or display the definition of the selected class."

classList selection isNil

ifTrue: [definition value: "'] "Nothing selected in the list view - blank the text editor."

ifFalse: [definition value: (Smalltalk at: classList selection asSymbol) definition]

*Multiple selection lists*

Single and multiple selection lists are essentially the same and the differences between them are as follows:

* To paint a multiple selection list, paint the List widget and click the *Multiple Selections* check box on the *Details* page of the *Properties* tool.

* The model of a multiple selection list is an instance of *MultiSelectionInList*.

* The methods accessing selections are called *selections* and *selectionIndexes*, and *selections*: and *selectionIndexes*: respectively. Message selections returns an ordered collection containing all selected objects, message *selectionIndexes* returns a value holder containing a set of indices. The argument of the corresponding *selections*: and *selectionIndexes*: messages must also be a collection and a set respectively.

**Example 3: Function calculator**

*Problem:* Write an application to generate and display tables of mathematical functions selected by the user from a list (Figure 8.16). If at least one function is selected, clicking *Print* prints the values of all selected functions for arguments 1 to 10 in steps of 1 in the Transcript using the following format:

<table><thead><tr><td>arg</td><td>cos</td><td>ln</td><td>log</td></tr></thead><tbody><tr><td>1</td><td>0.540302</td><td>0.0</td><td>0.0</td></tr><tr><td>2</td><td>-0.416147</td><td>0.693147</td><td>0.30103</td></tr><tr><td>3</td><td>-0.989993</td><td>1.09861</td><td>0.477121</td></tr><tr><td>4</td><td>-0.653644</td><td>1.38629</td><td>0.60206</td></tr><tr><td>5</td><td>0.283662</td><td>1.60944</td><td>0.69897</td></tr><tr><td>6</td><td>0.96017</td><td>1.79176</td><td>0.778151</td></tr><tr><td>7</td><td>0.753902</td><td>1.94591</td><td>0.845098</td></tr></tbody></table>
<table><tr><td>8</td><td>-0.1455</td><td>2.07944</td><td>0.90309</td></tr><tr><td>9</td><td>-0.911132.19722</td><td>0.954242</td><td></td></tr><tr><td>10</td><td>-0.839071</td><td>2.30259</td><td>1.0</td></tr></table>

When no function is selected, clicking *Print* opens a warning with appropriate text.

<figure><img src="image_170.png" /><figcaption>Figure 8.16. Selection window for Example 2.</figcaption></figure>

**Solution:** The initialization method initializes the list holder variable (list *Aspect* called *functions*) with the names of the functions:

**initialize**

```
"Create list holder."
functions := MultiSelectionInList with: #( 'cos' 'exp' 'factorial' 'ln' 'log' 'sin' ).
```

When the user clicks *Print*, we enumerate over the whole interval, and for each value of the argument and for each selected function we let the argument execute the message:

**print**

```
"Display selected functions in Transcript."
functions selectionIndexes ifTrue: [^Dialog warn: 'You must select at least one function.'].
```

```
"We have at least one selection. Clear Transcript and display heading."
Transcript clear; show: 'arg'; tab.
functions selections do: [:selection | Transcript show: selection asString; tab].
Transcript cr; cr.
```

```
"Calculate value for each argument and function and print it in Transcript."
1 to: 10 do: [:arg |
Transcript show: arg printString; tab.
functions selections do:
[:function | Transcript show: (arg perform: function) printString; tab].
Transcript cr]
```

Our examples show why message `onChangeSend/to:` is frequently used with single selection lists but rarely used with multiple selection lists. The reason is that it does not make sense to force the program to respond automatically to every new selection in a multiple selection list - presumably, the user will make several selections and then indicate that he or she is finished. With multiple selection lists, action is thus usually triggered by some other event such as clicking an action button.

With this example, we conclude our coverage of list widgets. They are among the most useful widgets and we will see many more examples of their use later.

**Main lessons learned:**

* List widgets display a list of labels and allow the user to make selections.

* Single selection lists allow one selection at a time, multiple selection lists allow any number of
selections at a time.

* The underlying data models of selection lists (their list holders) are instances of `SelectionInList` and `MultiSelectionInList`. Both hold the list of displayed items - an instance of `List` - and a value holder on the current selection or selections.

## Exercises

1. Write tutorial describing how to create a list widget.

2. Extend the single selection list example into a simple browser that displays class names, definition of the selected class, and an alphabetized list of the class's instance methods.

3. In the previous exercise, add a pair of radio buttons labeled *instance* and *class* to allow the user to choose between class and instance methods.

4. Extend the previous exercise to display also the definition of the selected method.

5. Modify the multi-selection list example by adding function `cubed`.

6. Extend Example 3 to allow the user to enter the start and end values of the argument and the step.

7. In Example 3, we used variables functions and messages to hold essentially the same arrays. Remove one of them and modify the solution appropriately.

8. If you register interest in selection change, a new list selection sends a change message. Is the message sent also when the contents of the list changes?

## Conclusion

In the first part of this chapter, we concluded our coverage of sequenceable (indexed) collections with ordered and sorted collections, lists, strings, text, and symbols.

Ordered collections can grow without limits and shrink (their elements can be removed) and distinguish between size and capacity. They are created with a default or specified capacity and when all slots are filled, new slots are automatically added. Growing an ordered collection is time-consuming and should be avoided by creating the ordered collection with a capacity at least equal to the maximum anticipated need. The memory space that may be wasted is generally negligible.

Ordered collections are used mainly when the number of elements is not known beforehand, or when the number of elements changes during the lifetime of the collection. They are usually accessed at the end or at the start. An important use of ordered collections is in the implementation of dependency. The major dependency protocols are defined in *Object* but the nature of the collection of dependents is redefined in *Model* which should be used as the superclass of all model objects under ordinary circumstances.

Sorted collections are ordered collections that sort their elements on the basis of a test defined by a sort block. The sort block compares two arbitrary elements of the collection and returns true if the first elements precedes the second element, and false otherwise. The built-in default sort block uses `<` comparison but can be redefined via a class or instance message. New elements are automatically inserted into the proper place according to the sort block. Every pair of elements in the collection must be able to execute the sort block.

*Class List* combines the accessing mechanism of ordered collections with sorting of sorted collections, and adds dependency handling. Unlike sorted collections, lists do not sort themselves automatically but must be explicitly asked to do so. They sort themselves by sending a message to `SequenceableCollectionSorter`. Lists are used mainly to hold elements of multi-item GUI widgets.

*Class String* is an abstract sequenceable collection whose elements are character codes. Concrete strings are instances of *String* subclasses, normally class `ByteString`, the default string implementer. The concrete implementation of strings as `ByteString` objects is transparent and the programmer does not need to pay attention to it unless a larger character set is needed. In that case, a `TwoByteString` may be used. The most common protocols of *String* include methods for finding and replacing substrings, copying, and comparison. Much of this protocol is inherited from the abstract class `CharacterArray`.

*Class Text* adds emphasis to strings, allowing their display in different fonts, styles, and colors.
Class **Symbol** is a subclass of **String** that does not allow duplication, making its processing, in particular comparison, more efficient. The main uses of symbols are for method selectors and as names of widgets in GUI specifications.

In the second part of this chapter, we introduced two new types of selection widgets. Single-selection lists allow only one selection at a time, multiple-selection lists allow any number of selections at a time. Their basis is **MultiSelectionInList** for single-selection widgets, and **SelectionInList** for multi-selection lists. They hold a list of items and the current selection or selections. The list component of the selection in list object is an instance of **List**.

We recommend that you now read Appendix 2 which covers additional widgets.

## Important classes introduced in this chapter

Classes whose names are **boldfaced** are very important, classes whose names are printed in *italics* are less important, classes whose names are printed in regular font are not of much interest.

*Association*, *ByteSymbol*, *CharacterArray*, *ComposedText*, *Cursor*, *Document*, *DocumentRenderer*, *List*, **MultiSelectionInList**, **OrderedCollection**. Printer, RunArray, SequenceableCollectionSorter, *Screen*, **SelectionInList**, **SortedCollection**, **String**, **Symbol**, **Text**, TwoByteString.

##Widgets introduced in this chapter

*Multiple selection list*, *Single selection list*.

## Terms introduced in this chapter

*association* - object consisting of a key-value pair, instance of **Association**

*emphasis* - specification of font, style, or color to be used when displaying a string

*multiple-selection list* - list widget allowing any number of selections

*ordered collection* - used either to refer to any collection whose elements are stored in a fixed externally accessible order, or in the more restrictive sense of an instance of class **OrderedCollection**

*single-selection list* - list widget allowing at most one selection at a time

*sort block* - a block defining how to compare two elements when sorting a collection

*sorted collection* - an ordered collection whose elements are ordered according to a comparison function called the sort block

*symbol* - a string with unique instantiation; used mainly for method selectors

*text* - string with emphasis prescribing how the string should display itself
# Chapter 9 - Sets, bags, and dictionaries

## Overview

This chapter presents the remaining frequently used collections - sets, bags, and dictionaries. All of them are unordered which means that they don't provide access to their elements in a user-defined order.

Sets are unordered collections that don't allow duplication so if you add an element to a set several times, the result is the same as if you added the element once. And if you delete an element, it is gone, no matter how many times it has been previously added. Sets are important and frequently used.

Bags are unordered collections that keep track of the number of occurrences of their elements. The Smalltalk library does not use bags and although this does not mean that they are useless, applications of bags are rare.

Dictionaries are sets of special kinds of objects called associations which are key-value pairs. For the purpose of preventing duplication, dictionaries compare association keys. Because the structure of dictionaries is substantially different from that of other collections, their protocols include a number of specialized methods. Dictionaries are used very often.

As a by-product of the discussion of sets, we will deal with the subject of copying objects. We introduce the concepts of shallow and deep copy, and point out the dangers of copying.

## 9.1 Sets

Sets are an important and frequently used kind of collection. Their capacity automatically grows when needed, and their elements are unordered which means that although they are internally stored as an indexed collection, there is no accessing method that allows accessing sets by index. Most often, sets are accessed by enumeration. The most important part of Set hierarchy is shown below with classes covered in this chapter in bold face.

### Object ()
### Collection ()

#### Set ('tally')

#### Dictionary ()

* IdentityDictionary ('valueArray')

* PoolDictionary ('definingClass')

* SystemDictionary ('organization')

#### IdentitySet ()

Sets eliminate duplication. This means that adding an element that is equal to an element already in the set has no effect. Since a set contains only one copy of each element, removing an element has the same effect no matter how many times the element has been added to the set before - a removed element is gone.

### Creating sets

Sets are usually created with `new` and `new:`. Message `new` creates a new empty set with room for two elements:

#### new

```
^self new: 2 "Capacity 2, size 0."
```

Although sets automatically grow when their capacity is filled, the best way to create them is to try to estimate the maximum required capacity beforehand and use `new:` to create the set with a capacity about 50% larger for better performance of element accessing.

Another creation message that is occasionally used to create sets is with: and its multi-keyword variants as in
Set with: 'a string' "Returns the one element set Set ('a string')"

The withAll: aCollection creation message can be used to create a set containing the elements of aCollection. The following code fragment uses this approach to create a collection of all elements of array that are divisible by 6 without duplication:

| array divisible |
array := #(13 13 12 12 24 24 56 56 54 54).
divisible := Set withAll: (array select: [:number | (number rem: 6) = 0])

It is instructive to see the definition of withAll:

withAll: aCollection

| newCollection |
newCollection := self new: aCollection size * 3 // 2.
newCollection addAll: aCollection.
^newCollection

The method first creates a new set (self is class Set) whose size is 50% bigger than the size of the collection, adds all the elements of the original collection one after another, and returns the result - the new set. The new set thus shares its elements with the original collection and if either the set or the original modifies one of them, the other collection is affected too.

Sets can also be created with asSet which is understood by all other collections, and this method is often used to eliminate duplication. With asSet, our previous code fragment could be rewritten as follows, giving exactly the same result:

| array divisible |
array := #(13 13 12 12 24 24 56 56 54 54).
divisible := (array select: [:number | (number rem: 6) = 0]) asSet

Note that if our only goal was to eliminate duplication in the original values, we could proceed as
follows:

| array |
array := #(13 13 12 12 24 24 56 56 54 54).
array := (array select: [:number | (number rem: 6) = 0]) asSet asArray

Adding, testing, and removing elements

Set messages for adding new elements include the usual add: anObject and addAll: aCollection.
Message add: adds a new element without duplication, addAll: adds all elements of aCollection individually,
again without duplication. To illustrate the difference between add: and addAll:; compare the results of
executing the following two expressions:

Set new addAll: #(1 2 3 4); yourself. "Returns Set (1 2 3 4) - a set with four elements."
Set new add: #(1 2 3 4); yourself. "Returns Set (#(1 2 3 4)) - a set with a single element."

Note that we had to use yourself to obtain the resulting set because both add: and addAll: return their argument rather than the modified receiver. This behavior is, of course, identical to the behavior of add: and addAll: in all other collections.

To test whether an object is a member of the set use includes: anElement or contains: aBlock.
Both messages return true or false. As an example,

| array set |
array := #(13 13 12 12 24 24 56 56 54 54).
set := (array select: [:number | (number rem: 6) = 0]) asSet. "Returns Set (12 24 54)."
set includes: 12.

"Returns true."

set includes: [:element| (element rem: 6) ~= 0]

"Returns false."

Removing methods include remove: anElement and remove: anElement ifAbsent: aBlock. Both
return the argument, just like add: and addAll:

| set |

set := Set new addAll: #(1 2 3 4); yourself. "Returns Set (1 2 3 4)."

set remove: 1. "Returns 1."

set "Returns Set (2 3 4)."

Another message that removes set elements is the binary message - (minus) which calculates set
difference. The difference of two sets is the set of those elements that are in the receiver set but not in the
argument set. In other words, the difference is a set obtained by removing from the receiver those elements
that are in the argument. As an example,

#(1 2 3 4 5) asSet - #(1 3 5) asSet

returns Set (2 4).

After this overview, we will now look at several short examples.

Example 1: Is there a difference between asSet and withAll?

Problem: asSet and withAll: seem to have the same effect. Is there any difference between them?

Solution: There are two definitions of asSet, one in Collection and one in Bag. The definition in Collection is the one that most collections inherit and its listing is as follows:

asSet

"Answer a new instance of Set whose elements are the unique elements of the receiver."

| aSet |

aSet := Set withAll: self.

^aSet

This shows that asSet and withAll: have exactly the same effect and that addAll: aCollection is more
direct.

Example 2: How does a Set eliminate duplication when adding a new element?

Solution: The definition of add: in Set is as follows:

add: newObject

"Include newObject as one of the receiver's elements. Answer newObject."

| index |

newObject == nil ifTrue: [^newObject]. "Ignore nil objects."

index := self findElementOrNil: newObject. "Find index where newObject should be."

(self basicAt: index) == nil "If newObject is not at this location, add it."

ifTrue: [self atNewIndex: index put: newObject].

^newObject

The definition reveals that sets are stored as indexed collections even though the Set protocol
makes the index invisible. The definition is based on findElementOrNil: which is defined as follows:

findElementOrNil: anObject

"Answer the index of anObject, if present, or the index of a nil entry where anObject would be placed."

| index length probe pass |

length := self basicSize.

pass := 1.

index := self initialIndexFor: anObject hash boundedBy: length.

[(probe := self basicAt: index) == nil or: [probe = anObject]]

whileFalse: [(index := index + 1) > length
<figure><img src="image_171.png" /></figure>

Method `findElementOrNil`: tries to find the object in the collection, and if it does not find it, it returns the index where it should be stored. The principle of the search is as follows (Figure 9.1):

1. Ask the object for its hash value and scales it to the size of the set. This is the index at which the object would *ideally* be stored.

2. If the corresponding slot is empty or if it already contains anObject, we are finished.

3. If the slot is not empty but does not contain anObject, anObject could be stored further down. The method checks the next index, and the next, and so on, until the an empty slot or a slot containing anObject is found, or until the method reaches the last index. If the method succeeds, we are finished.

4. If the method reaches the last index without finding an empty slot or anObject, it starts pass 2 from index = 1. Search continues until the condition succeeds (it then exits and returns index) or until it fails by reaching the last available index.

5. If search in Step 4 failed, the collection is full and does not contain anObject. The method thus grows the collection and sends `findElementOrNil`: again. This time, the message will succeed because we have just created empty slots.

<figure><img src="image_172.png" /><figcaption>Figure 9.1. Situations that can occur while adding an element to a set. Top (left to right): Slot at hash index is empty, slot contains the argument, slot is occupied by another element but another slot further down is available, slot is occupied by another element but the element is stored further down. Bottom (left to right): No success in the first pass but available slot is found on second pass, element is found on second pass, two passes fail because collection is full and does not contain element - enlarge capacity (gray squares) and try again, this time finding an empty slot.</figcaption></figure>

Our analysis of `findElementOrNil`: explains the major role of hash - it calculates an number characterizing an object. In this case, the number is used as the first candidate for an index to store the object. The same principle is used to find an object as follows:

**includes: anObject**

"Answer whether anObject is one of the receiver's elements."

`^(self basicAt: (self findElementOrNil: anObject)) notNil`

and hashing is also used to remove an element from the set. If the hash method is well designed and if there are enough available slots, the scaled hash values calculated for different objects will be spread out and the number of clashes between different objects producing the same hash value and competing for the same slot will be minimal. An element inserted into a set will then be accessed very fast and this is a major advantage of sets.

Since all objects must respond to the hash message, `hash` is defined in class `Object`. Since equality and hashing are closely related – two objects that are equal (`message =`) must have the same hash value -
hash should be redefined in all classes that redefine =. For efficiency of accessing in sets, two objects that are not equal should have a different hash value. However, this is not required and often not guaranteed.

The main use for hashing is fast access of set elements and its calculation must therefore be simple and fast. The principle of the hash method usually is that if only one component of a multi-component object is used to determine equality, its hash value is used for the hash value of the object. As an example, if class Person has instance variableseo first Name and last Name and if we compare Person objects by their last name only

= aPerson

^last Name = aPerson lastname

the definition of hash in class Person should be

hash

^lastname hash

If equality depends on more components, their hash values should be combined to get the hash
function of the object and the usual way of doing this is to use exclusive or. As an example, consider a
LibraryEntry class with instance variables author, title, publisher, and year. If we define equality on the basis
of author and title

= anEntry

^author = anEntry author) and: [title = anEntry author]

we will probably define hash in LibraryEntry as follows:

hash

^ (author hash) bitXor: (title hash)

With this definition, two entries that are equal will also have the same hash value, and if the hash
methods of author and title are good, the hash method of LibraryEntry will also behave well.

As a final note on hashing, the principle of converting an object to a representative integer is the
principle of hash tables, a very efficient technique for storing performance is better when the capacity of the
set is a prime number. More detailed coverage of hashing is beyond the scope of this book.

Example 3: Set union.

Problem: Set difference (the - message) is only one of several mathematical set operations. The other common operations are set union, intersection, and symmetric difference but these operations are not defined in the Set class. Define a method for set union as a binary message + using the definition that the union of two sets is the set containing all elements that are in at least one of the two sets.

Solution: The obvious solution of this problem is to take the first set and add all the elements of the second set to it as in

+ aCollection

"Calculate union of receiver and aCollection. Return the argument as in all add and remove messages."

^self addAll: aSet

which could be used as in

|set1 set2 set3 |
set1 := #(1 3 5) asSet.
set2 := #(1 2 3 4) asSet).
set3 := set1 + set2
etc.

"Returns Set (1 2 3 4 5)."
Although this solution works, it changes the receiver `set1` and this is undesirable. To calculate the union without changing the receiver, we can use a *copy* of the receiver rather than the receiver itself as in

### + aSet

"Calculate the union of the receiver and the argument."

| temp |

temp := self copy. "Make a copy so that we don't change the receiver."

temp addAll: aSet.

^temp

Note that the argument may be any collection, not just a `Set`.

### Example 4: Finding all text fonts available on the current platform

**Problem:** An application such as a word processor needs to know which text fonts are available on the current platform. Determine how to find their names.

**Solution:** Hoping that there are messages with the word `Font` in them, we opened the *implementors of ..* browser on \*Font messages, and found one called `availableFont`s. It turned out to be an instance message in class `FontPolicy`.

To be able to use the method, we need an instance of `FontPolicy`. After some further searching we found a `FontPolicy` used as a component of class `GraphicsDevice` responsible for display devices. `FontPolicy` has an instance variable called `defaultFontPolicy` which provides access to `defaultFont`s. The next question is how to get an instance of `GraphicsDevice`. After looking at subclasses of `GraphicsDevice`, we found class `Screen` and we thus inspected

### Screen default defaultFontPolicy availableFont`s

and this indeed returned a large array of `FontDescription` objects. When we inspected one of them, we found that `FontDescription` has many components and one of them called `family` contains a string with the name of the font. To collect the names of all fonts, we thus inspected

### Screen default defaultFontPolicy availableFont`s collect: [:font| font family]

This returned a large array of strings and when we inspected them, we found that many of them are duplicates. The reason for this is turned out to be that there are usually several instance of the same family differing in various parameters such as size. To eliminate this duplication we converted the array of family names to a set by

### (Screen default defaultFontPolicy availableFont`s collect: [:font| font family]) asSet

This indeed returns the desired result.

### Example 5. The 'lost object' paradox

Consider the following code fragment:

| rectangle |

rectangle := 10@10 corner: 100 @ 100.

Transcript clear; show: rectangle hash printString; cr.

rectangle origin: 20 @ 20.

Transcript show: rectangle hash printString

It will not surprise you that the two values of hash output to Transcript are different because the `rectangle` object, while maintaining its identity, changed its structure and thus its hash value. (When we say that "object x maintains its identity after a change" we mean that all objects that referred to x before the change still refer to it after the change. Just like John Doe remains John Doe when he moves from one
address to another or loses weight, the x object retains its identity even when it changes its state.) Now
assume that we insert the **rectangle** into a set, change it, and then test the set for its presence as in

| rectangle set |

...

"some statements calculating set"

rectangle := 10@10 corner: 100 @ 100.

set add: rectangle.

...

"some more statements"

...

rectangle origin: 20 @ 20

"some more statements"

set includes: **rectangle**

The amazing result is that although **rectangle** is still in the set when we send `includes:`; the last statement *may* return `false`! The reason for this is that when we execute `includes:`; its `findElementOrNil:` method will recalculate hash (getting a different result than when it inserted rectangle into set) and the starting index for its search will thus be different from what it was when we inserted rectangle into set. `findElementOrNil:` will thus look for rectangle in a slot different from the one where it was initially put.

One of the bad things that can now happen is that the slot corresponding to the new index is still empty, the `findElementOrNil:` method concludes that the element is not in the set, and `includes:` returns `false`.

In essence, the reason for this abnormality is that the set element **rectangle** changed its hash value during its lifetime. To eliminate this possibility, the library contains another kind of set called **IdentitySet** which uses `identityHash` (and `==`) instead of `hash` (and `=`) in its `findElementOrNil:` method. The difference between `identityHash` and `hash` is that the value of `identityHash` never changes during the lifetime of an object, even if the object itself changes. We leave the study of **IdentitySet** and `identityHash` as an exercise.

## Main lessons learned:

* Sets (and other unordered collections) store their elements in a sequential fashion but don't allow index-based access.

* The most common set-related protocols are creation, conversion, enumeration, adding, and removing. All behave consistently with other collections.

* To access an element, sets calculate its hash value, a `SmallInteger`, using the `hash` method. The default definition of `hash` is in class `Object`.

* Because of their shared use in sets, `hash` and `=` are related and when `=` is redefined, `hash` should be redefined as well.

* The value of `hash` may change during an object's lifetime even though the identity of the object does not. This may have unexpected results when testing sets. Class `IdentitySet` eliminates this problem.

## Exercises

1. Explain the purpose of instance variable *tally* in the definition of *Set*.

2. To create a collection of elements without duplication, you can create a set and add the elements to it, or create an `OrderedCollection` with the elements and convert it to a set. Which approach is faster?

3. Define *Set* methods to calculate symmetric difference (set of all elements that are in one set but not in the other), and intersection (set of all elements that are in both sets). The receiver should not be affected.

4. Is there a measurable difference in speed between `withAll:` and `asSet`? What do you conclude about the penalty of extra message sends?

5. Implement a new set class using equality instead of hashing to eliminate duplication and compare its performance with the existing implementation.

6. Method `findElementOrNil:` is the basis of accessing objects in a set. Explain how its implementation creates a close relationship between `hash` and `=` messages.
7. How does `remove:ifAbsent:` work? What is the major problem that it must resolve?

8. Explain why inspecting a `Set` often shows many nil elements.

9. The size of a set should always be considerably smaller than its capacity. Why?

10. We explained that if a set element changes its state during its lifetime, the test for its presence in the set may fail. This begs two questions:

a. Under what conditions will the test succeed, and when will it fail?

b. What can we do to prevent this from happening without using `IdentitySet`? (Hint: Consider what is the cause of the problem and examine the protocols of `Set` for a solution.)

11. Demonstrate the 'lost object' paradox in a code fragment. (Hint: Under what conditions is it more likely to occur?)

12. Experiment with efficiency of hashing as a function of the relation between set capacity and its size, and the choice of the capacity of the set as a prime number.

13. How does class `IdentitySet` differ from `Set`?

14. Examine ten definitions of `hash` in the library and check if each has a corresponding definition of `==`.

15. Explain the difference between `hash` and `identityHash` and illustrate it on several examples.

16. Explain the reason for the word `identity` in the name of `identityHash`.

17. The comment of `identityHash` contains the following sentence: When two objects are not `==`, their `identityHash` values may or may not be the same. Explain it.

18. Are there other uses of hashing in the class library beyond the one discussed in this section?

## 9.2 Copying objects

How does the `copy` method that we used in the previous section work? Does it create a new object that shares its components with the original, or is it a completely new object with new components? Or is it something in between? This is a very important question because if `copy` shares instance variables with the original then changes of the original affect the copy and vice versa, and this may not be desirable. As an example, if you wanted to make a new version of a document by making and editing a copy, changing the copy would change the original as well.

As a specific example, consider a Smalltalk `Rectangle` - an object with instance variables `origin` and `corner`, each of them an instance of `Point`. What does the following program fragment do?

| aRectangle aRectangleCopy |
aRectangle: = Rectangle origin: 10@10 corner: 20@20.
aRectangleCopy := aRectangle copy

The two ways in which copy could be implemented are as follows (Figure 9.2):

* The copy message could create a new `Rectangle` object and make its two instance variables share its values with the instance variables of the original. This kind of copy is called a *shallow copy*.

* The message could create a new `Rectangle` and assign its instance variables copies of instance variables of the original. This kind of copy is called a *deep copy*.

<figure><img src="image_173.png" /></figure>
<figure><img src="image_174.png" /><figcaption>Figure 9.2. Shallow copy (top) and deep copy (bottom).</figcaption></figure>

Using these new terms, we can rephrase our original question as follows: Does Smalltalk make shallow copies, deep copies, or some other kind of copies? The answer is that Smalltalk generally makes shallow copies but provides a mechanism to extend the copy operation, allowing the programmer to create a deep copy if it is needed. We will now explain how this works.
The default version of copy is defined in Object as follows:

**copy**

"Answer another instance just like the receiver."

^self shallowCopy postCopy

The method first makes a shallow copy and then sends postCopy to the result. The default definition of postCopy does not do anything and its only purpose is to allow other classes to perform any additional work after the shallow copy has been made. In other words, postCopy is a hook.

The overwhelming majority of classes don't redefine postCopy and for most classes, a copy is thus a shallow copy. Method shallowCopy itself is almost never redefined and the only exceptions are classes that do not allow copies at all such as Symbol (each Symbol is unique) or UndefinedObject (there is only one instance - nil). As an example, the definition of shallowCopy in Symbol is

**shallowCopy**

"Answer the receiver because Symbols are unique."

^self

As we have already mentioned, few classes redefine postCopy and the default definition is to do nothing. The following example shows how postCopy is *redefined* in class Rectangle:

**postCopy**

super postCopy.

origin := origin copy.

corner := corner copy.

The definition creates two new Point objects whose values are the same as those of the original and a copy of a Rectangle is thus a deep copy as in the bottom part of Figure 9.2.

Although the difference between the effects of shallow and deep copy should now be clear, we will illustrate it on a small example. The following fragment first creates a Rectangle and makes its shallow copy using shallowCopy (not the usual way of making copies) and a deep copy using copy. It then modifies the origin of the original rectangle and shows how this change affects the shallow and the deep copy:

| deepCopyRectangle shallowCopyRectangle originalRectangle corner |
"Create a rectangle."

originalRectangle := Rectangle origin: 10@10 corner: 20@20.

"Make shallow and deep copies."

shallowCopyRectangle := originalRectangle shallowCopy.

deepCopyRectangle := originalRectangle copy.

"Show whether instance variables are the same objects or just copies."

Transcript show: 'shallow copy corner == original corner ?',
(shallowCopyRectangle corner == originalRectangle corner) printString; cr.

Transcript show: ' deep copy corner == original corner ?',
(deepCopyRectangle corner == originalRectangle corner) printString; cr.

"Get the corner of the original and change it."

corner := originalRectangle corner.

corner x: 0; y: 0.

"Show how this affected the original, the shallow copy, and the deep copy."

Transcript cr: show: 'Rectangles: '; cr;
tab; show: 'original rectangle: ', originalRectangle printString; cr;
tab; show: 'shallow copy: ', shallowCopyRectangle printString; cr;
tab; show: 'deep copy: ', deepCopyRectangle printString

The program produces the following output:

shallow copy corner == original corner? true

deep copy corner == original corner? false

Rectangles:

original rectangle: 10@10 corner: 0@0

shallow copy: 10@10 corner: 0@0

deep copy: 10@10 corner: 20@20

The result is as expected: Changing the corner object in the original affects the shallow copy (and the original would be similarly affected by changing the shallow copy), but not the deep copy.

Note that the side effect produced by shallow copy and illustrated by the above example occurs only if we change the *state* of a shared component but not its *identity*. If we *replace* a component rather than *change* it, we change the identity (the two objects now refer to different components) and there is no side effect (Figure 9.3). To see this, replace

corner := originalRectangle corner.

corner x: 0; y: 0.

in the example above with

originalRectangle corner: (Point x: 0 y: 0)

and re-execute it. This time, the original will be different even from its shallow copy.

<figure><img src="image_175.png" /></figure>
<figure><img src="image_176.png" /><figcaption>Figure 9.3. Original and shallow copy from Figure 9.2 after changing the value of corner (top) and after assigning a new Point to corner (bottom).</figcaption></figure>

Up until recently, Smalltalk contained a `deepCopy` method but the method was removed because it is difficult to implement for circular (recursive) structures - objects, whose instance variables point to objects whose instance variables point to the original or to some other object that points to the original. A deep copy can then enter into an infinite loop, copying and recopying all objects in the component chain. Since many situations don't really require a deep copy, the method has been dropped in favor of `postCopy`.

Circular structures are not only of academic interest and occur frequently in natural situations. As an example, a `Student` object could have a variable called `major` whose value is an instance of class `Major` representing the field in which the student majors. `Major`, in turn, could have a variable whose value is the collection of all students with this major. By following the pointers, we thus very quickly return to the starting object (Figure 9.4) and deep copy will have to be more sophisticated than just following references and making copies of referenced objects until no more references can be found.
<figure><img src="image_177.png" /><figcaption>Figure 9.4. Example of a circular structure.</figcaption></figure>

### Main lessons learned:

* The copy operation comes in two flavors - shallow copy and deep copy.

* A shallow copy creates a new object which shares its components with the original.

* A deep copy creates a new object whose components are distinct from the corresponding components of the original but equal in value.

* Changing the state of a component of a shallow copy or its original affects both the original and the copy. This does not happen with deep copy.

* Replacing the component of a shallow copy or its original with a new object breaks sharing.

* VisualWorks default copy is a shallow copy followed by postCopy. The default behavior of postCopy is to do nothing but the method is redefined in several classes to obtain non-default behavior.

* The definition of shallowCopy is shared by all classes except those that don't allow a copy. These classes reimplement shallowCopy to return the receiver.

## Exercises

1. Define class Student with instance variables name, a String. To test how instances of Student behave with respect to the default copy operation, create a Student object with name 'John' and its copy and observe the effect of changing the value of name in the original on the copy and vice versa. Change the name by a message such as student name at: 2 put: $x.

2. Modify class Student to eliminate the side effect resulting from shallow copy.

3. Add class Major implementing the essence of the example in this section and make deep copies of student-major combinations.

## 9.3 Bags

A bag is like a set in that it is an unordered collection. Unlike sets, however, it keeps track of the number of occurrences of each of its elements. As an example, if the same element is added to a bag five times and one copy is then removed, the bag knows that it still has four copies of the element.

Bags can be useful when we collect objects and don't care about keeping individual copies of each and the order in which they are stored, but want to know how many copies of each element we have. A typical example is, of course, putting items in a shopping bag and we will illustrate bags in this context.

### Example: A better shopping minder

Modify the shopping minder program from Section 8.2 according to the following new specification:
*Problem:* The program allows the user (presumably a store employee) to initialize a list of items and prices via a sequence of dialogs. The program then asks the user (now the customer) to select items from a multiple choice dialog window (Figure 9.5) repeated as many times as necessary. Note that the items are displayed in alphabetical order.

When the user indicates the end of selections by clicking *Cancel*, the program prints the selected items with their counts, the total price, and all selected items costing more than ten dollars in the Transcript. The form of output is similar to that in Chapter 8. (This is still a preliminary implementation of a program with a nice user interface and file storage, but the final implementation is left as an exercise.)

<figure><img src="image_178.png" /><figcaption>Figure 9.5. Example: Desired user interface for item selections.</figcaption></figure>

*Solution:* Our previous implementation Item in Section 8.2 used classes *ShoppingMinder*. The details of *ShoppingMinder* will clearly change but the nature of class Item remains unchanged. We will thus restrict our attention to analyzing and modifying *ShoppingMinder*.

The existing *ShoppingMinder* stores items in an *OrderedCollection* called *items*. In the new solution, we will use this collection for the original list and add a new variable called *selectedItems* to hold the items selected by the customer; this variable will be used as the *shopping Bag*. The new *ShoppingMinder* thus has two instance variables called *items* and *selectedItems* and the new initialization method now has two instance variables to initialize:

**initialize**

"Initialize items to a suitably sized ordered collection."

items := (SortedCollection new: 20) sortBlock: [:item1 :item2| item1 name < item2 name].

selections := Bag new: 20

Execution of the program is the responsibility of the *execute* method, as before. Its essence remains valid for the new formulation except that we have now separated item entry and item selection:

**execute**

"Let store person add items. let the user select, and display the results."

[self addItem] whileTrue.

[self selectItem] whileTrue.

self displayItems.

self displayTotal.

self displayExpensiveItems

It now remains to update the components of this definition. Method *addItem* simply asks the user to confirm that another item is to be added, requests the information, and adds it to the *items* variable. The old definition is

**addItem**

"Obtain an Item object from the user or an indication that no more items are needed. Add it to items."

| name price |

name := Dialog request: 'Enter item name' initialAnswer: "".
name empty ifTrue: [^false]. "Exit and terminate loop - user indicated end of entry."

price := (Dialog request: 'Enter item price' initialAnswer: '') asNumber.

items add: (Item name: name price: price).

^true

and although the nature of variable items has changed from OrderedCollection to SortedCollection, this does
not affect the validity of the original code thanks to polymorphism - OrderedCollection and SortedCollection
both respond to add: appropriately. This method thus remains unchanged.

Method selectItem is new. It opens a multiple choice dialog window with items, and allows the
customer to make a selection. The definition is

## selectItems

"Open window with available items and allow customer to make selections."

| labels selectedItem |

labels := (items collect: [:anItem | anItem name]).

selectedItem := Dialog choose: 'Select an item and click OK. Click Cancel to stop.'
                      fromList: labels
                      values: items
                      lines: 5
                      cancel: [nil].

selectedItem isNil

ifTrue: [^false]

ifFalse: [selectedItems add: selectedItem.

^true]

The definition of displayItems is simple, we only add the display of the number of occurrences of each item:

## displayItems

"Display alphabetically all items selected by the customer along with their prices. Use alphabetical order."

Transcript clear.

selections asSortedCollection do: [:item | Transcript show: item displayString; tab;

show: (selections occurrencesOf: item) printString; cr]

The code illustrates the power and flexibility of collections - the bag is easily converted into a
sorted list and easily displayed alphabetically in the Transcript. The definition of displayTotal is almost the
same as before except that we must take care of the number of occurrences of individual items:

## displayTotal

"Add together prices of all selected items and display them in Transcript."

Transcript cr; show: 'Total price: '; tab; show: (selectedItems inject: (Currency cents: 0))

into: [:total :item | total + (item price * (selectedItems occurrencesOf: item))] displayString

Finally, the only change in displayExpensiveItems is that it operates on selectedItems rather than items:

## displayExpensiveItems

"Display a heading and all items that cost more than 10 dollars."

Transcript cr; cr; show: 'Expensive items:'; cr.

selectedItems do: [:item | item isExpensive ifTrue: [Transcript show: item displayString; cr]]

We are now finished and the last step is to test that everything works. And sure enough, when we
test, the program does not do quite what we expected. The problem is that the total price seems to be
incorrect as in

<table><tr><td>apple juice</td><td>price: 1 dollars 90 cents</td><td>number of units: 2</td></tr><tr><td>cat food</td><td>price: 24 dollars 50 cents</td><td>number of units: 1</td></tr><tr><td>mineral water</td><td>price: 2 dollars 50 cents</td><td>number of units: 3</td></tr></table>

Total price: 54 dollars, 60 cents
Expensive items:

cat food price: 24 dollars 50 cents

Something is wrong with displayTotal, and the only thing that can be wrong is the calculation in
inject:into:. This method is defined in Collection in terms of do: and we should thus check whether we are
not misunderstanding do:. Checking implementors of do:, we find that Bag has its own definition

do: aBlock

contents keysAndValuesDo: "Use block providing access to objects and their counts."
[:obj :count | count timesRepeat: [aBlock value: obj]]

which shows that for each element of the bag, the block statements are executed as many times as there are
occurrences of the element and this is the cause of our problem. We must eliminate multiplication by the
number of occurrences as follows:

displayTotal

"Add together prices of all selected items and display them in Transcript."

Transcript cr; show: 'Total price: '; tab; show: (selectedItems inject: (Currency cents: 0)
into: [:total :item | total + item price]) displayString

After this change, everything works fine and the output for the same items is

apple juice price: 1 dollars 90 cents number of units: 2
cat food price: 24 dollars 50 cents number of units: 1
mineral water price: 2 dollars 50 cents number of units: 3

Total price: 35 dollars, 80 cents

Expensive items:

cat food price: 24 dollars 50 cents

Main lessons learned:

* Bags are unordered collections that don't eliminate duplication.

* If the number of occurrences of an element is *n*, the `do:` message in class `Bag` executes the block statements with this element *n* times.

Exercises

1. Although bags are conceptually related to sets, this relationship is not reflected in their place in the Collection hierarchy. Examine the definitions of `Set` and `Bag` and write a brief comparison.

2. How does `Bag` know the number of occurrences of its elements?

3. Is `Bag`'s treatment of new elements based on equality or equivalence?

4. Write a summary of all definitions of `occurrencesOf`:

5. Create an array containing 500 random integer numbers between 1 and 1,000 and calculate how many different integers it contains and how many copies of each. Use `Bag`.

9.4 Associations and dictionaries

Many applications involve operations on key-value pairs. Arrays and other kinds of sequenceable
collections provide a specialized form of this structure if we consider consecutive integer indices to be keys,
but in many cases we need a non-integer object for the key. For situations such as these, Smalltalk provides
class `Dictionary`.
An obvious example of the need for dictionaries is an assembler program which translates a source program into machine instructions, replacing symbolic instruction names with their binary opcodes. This process is based on associating symbolic names with binary opcodes which could be described as

'add' -> 2r10010001 "The prefix 2r means that the code is a base 2 number. r stands for radix."
'sub' -> 2r10010010
etc.

Another possible use of dictionaries is an English-French dictionary consisting of pairs of English words and their French equivalents as in

'father' -> Set('pere', 'papa')
'mother' -> Set('mere', 'maman')

As yet another example, one could represent a font as a set of associations such as

'Arial' -> Dictionary ('a' -> shape of 'a', 'b' -> shape of 'b', etc.)
'New Times Roman' -> Dictionary ('a' -> shape of 'a', 'b' -> shape of 'b', etc.)

A library of fonts would then be a dictionary whose values are other dictionaries (Figure 9.6).

<figure><img src="image_179.png" /><figcaption>Figure 9.6. Font library as a dictionary of dictionaries.</figcaption></figure>

### Class Dictionary

According to its comment, Dictionary is a Set of Association objects, key->value pairs. It is a computer analogy of the conventional dictionary except that it is not ordered. Another difference is that while a conventional dictionary often include entries with the same keys, a Smalltalk dictionary does not allow two different associations with the same key because it is a Set and its comparison for equality uses `=` on keys. Associating a new value with a key already present in a Dictionary thus replaces the old association with the new one. As an example, if a Dictionary contains association<fnref n="1" />

'father' -> 'dad'

and you add a new association

'father' -> 'daddy'

<footnote n="1">¹ Binary message -> which creates a new association is declared in class Object because any object may be used as the key of an Association.</footnote>
the second association replaces the first one because its key is equal to the first key.

IdentityDictionary is an important subclass of Dictionary that uses equivalence instead of equality, and is internally represented as a collection of keys and a collection of values rather than as a set of associations. An IdentityDictionary is often used as a kind of a knapsack to carry around a variety of identifiable objects that could not be predicted when a class was designed and consequently could not be declared as instance variables. To put this differently, an IdentityDictionary can be used as an on-the-fly collection of instance variables. As an example, when a user interface implements drag and drop functionality (Appendix 8), the object in charge of following the mouse cursor around the screen is an instance of DragDropManager. One of the functions of this object is to carry around information about the source widget and the target widgets that might be useful in the operation. Since the nature of some of these objects is unpredictable, they can be stored in an IdentityDictionary as associations identifyingSymbol -> object. Any object that needs them may then access them by their symbolic name, almost as if they were instance variables. As another example, a software agent wandering around the Web might carry along and gather all kinds of unpredictable objects, and these objects, along with identifying symbols, could be stored in an IdentityDictionary. An ordinary Dictionary could be used as well but Symbols are unique and identity comparison is thus appropriate.

The idea of making the dictionary class a subclass of set seems strange. After all, real dictionaries are arranged alphabetically by their keys and subclassing to SortedCollection would seem more logical. The reason for this choice is efficiency: Set elements are accessed by hashing and this is a very fast operation.

After this general introduction, we will now examine the main protocols of class *Dictionary* and give several short examples of their use.

## Creation

Dictionaries are usually created with message `new` which creates an uninitialized dictionary with a default capacity. If you can estimate the size, use the `new:` message to eliminate growing. You can also create an initialized dictionary using message `withKeysAndValues:` whose argument is an array of alternating keys and values as in

```
|array |
array := #'(a' 1 'b' 2 'c' 3).
Dictionary withKeysAndValues: array "Returns Dictionary ('a'->1 'b'->2 'c'->3)."
```

This method is rarely used.

## Adding and changing elements

Message `at:` `key put:` `value` adds a new association or replaces an existing association that has the same (equal) key. This message is frequently used as in the following example which creates a table of natural logarithms:

```
|logarithms |
logarithms := Dictionary new: 10.
1 to: 10 do: [:key | logarithms at: key put: key log].
etc.
```

Storing values in a *Dictionary* for easy retrieval is one of its typical uses. It is useful when we need frequent access to objects that require a long time to calculate and when we are willing to trade memory space for execution time. This approach to increasing program speed is called *caching*.

Note that `at:put:` returns the value of the second argument rather than the dictionary itself. This behavior is, of course, in line with behavior common to all collections.
Another way to add associations to a *dictionary* or to change them is to use `add:` *anAssociation* as in

`dictionary add: key -> value`
which has the same effect as

`dictionary at: key put: value`

### Removing associations

To remove an association from a dictionary, use `removeKey:` or `removeKey:ifAbsent:`. The standard `Collection` messages `remove:` and `remove:ifAbsent:` are illegal with dictionaries because they are redefined as follows:

**remove: anObject ifAbsent: exceptionBlock**

> "Provide an error notification that Dictionaries can not respond to remove: messages."
> self shouldNotImplement

and similarly for `remove:`.

### Accessing

To obtain the value associated with a given key, use the `at:` message if you know that the key is present, or the `at:ifAbsent:` message if you are not sure. The following example allows the user to enter an English word and displays the French equivalent if the pair is in the dictionary. If the English word is not in the dictionary, it displays a `'not in the dictionary'` warning:

`| answer array dictionary key |`

> "Construct a dictionary."

> `array := #( mother 'mere' 'father' 'pere' 'sister' 'soeur' 'father' 'papa')`.

> `dictionary := Dictionary withKeysAndValues: array.`

> "Prompt user for key word."

> `key := Dialog request: 'Enter an English word present in the dictionary' initialAnswer: "."`

> "Check whether the key is in the dictionary and construct a message."

> `answer := dictionary`

> `at: key`

> `ifAbsent: ['not in the dictionary']`.

> "Display result."

> `Dialog warn: 'The French equivalent of ', key, ' is ', answer`

Note that we put two associations with keyword `'father'` in the dictionary. Check what is the result.

Two other useful accessing messages are `keys` and `values`. `Message keys` returns the `set` of all keys, `message values` returns an *ordered collection* of values as in

`| array itemsAndPrices |`

> `array := # (sugar 15 salt 8 coffee 35 eggplant 20 kiwi 25)`.

> `itemsAndPrices := Dictionary withKeysAndValues: array.`

> `itemsAndPrices keys. "Returns Set (#eggplant #kiwi #sugar #salt #coffee)."`

> `itemsAndPrices values. "Returns OrderedCollection (20 25 15 8 35)."`

### Enumeration

Dictionaries can be enumerated with `do:` and other enumeration methods just like other collections. Remember, however, that `do:` works on *values*, not on associations as one might expect. As an example of the use of enumeration, the total price of grocery items stored in a dictionary containing item-price pairs could be calculated with `inject:into:` because its definition uses `do:` and therefore works on `values`:

`| array itemsAndPrices total |`

> "Create an Array with items and prices."

> `array := # (sugar 15 salt 8 coffee 35 eggplant 20 kiwi 25)`.
"Convert it to a Dictionary of symbol -> integer values."
`itemsAndPrices := Dictionary withKeysAndValues: array.`
"Calculate the total."
`total := itemsAndPrices inject: 0 into: [:subTotal:price | subTotal + price].`
`total "Returns 103."`

The reason why enumeration works on values is that *Dictionary* is conceptually a keyed collection, a generalization of the concepts of *Array* and *OrderedCollection*. Just as enumeration messages for *Array* and *OrderedCollection* enumerate over values rather than indices, enumeration over *dictionary* elements thus ignores keys. In fact, this analysis suggests that *Dictionary* is conceptually misplaced in the class hierarchy and that its position is dictated by implementation reasons. In other Smalltalk dialects, *Dictionary* is indeed located on a different branch of the *Collection* tree.

In addition to enumeration over values, it is often necessary to enumerate over *associations*. For this, use message `keysAndValues`. As the name suggests, `keysAndValues:` requires a two-argument block ranging over the keys and values of individual association. The first block argument is the key and the second is the value as in the following example which uses `keysAndValues:` to display the pairs of item names and prices from a shopping list in the Transcript in the following format:

eggplant costs 20
kiwi costs 25

The program is as follows:

|array itemsAndPrices |
"Construct a dictionary of names and prices."
`array := #(sugar 15 salt 8 coffee 35 eggplant 20 kiwi 25).`
`itemsAndPrices := Dictionary withKeysAndValues: array.`
"Display the name-price pairs."
Transcript clear.
`itemsAndPrices keysAndValuesDo: [:item:price | Transcript show: item, ' costs ', price printString; cr]`

Since a dictionary is a set, the order in which the associations are listed is unpredictable. It is interesting to note that `keysAndValuesDo:` is also understood by all sequenceable collections where it treats keys as integer indices.

## Testing

Message contains: `aBlock` is defined in *Collection* on the basis of `detect`: which, in turn, uses `do:`.
As a consequence, *Dictionary* inherits `contains`: and applies it to values as in

`itemsAndPrices contains: [: aValue | aValue > 10]`

Message includes: `aValue` tests whether the dictionary contains an association with value `aValue`.
To check for a *key*, use `includesKey`: `aKey`. All testing messages return true or false. As you can see, many dictionary messages access values by default.

## Main lessons learned:

* A dictionary is a set whose elements are associations.

* An association is a pair of objects called key and value.

* Uniqueness in dictionaries is based on equality of keys.

* The most frequently used *Dictionary* messages include creation, adding, removing, accessing, and enumeration.

* Most dictionary methods work with values rather than associations.

* One of the uses of dictionaries is for caching frequently needed objects that would require considerable time to calculate. The price for improved speed is increased memory requirements.
## Exercises

1. Test whether caching logarithms in a dictionary really saves time.

2. What does the `add:` `anAssociation` message return?

3. Write and test method `withKeys:` `array1` `withValues:` `array2` to create a new dictionary from two arrays.

4. Implement two-dimensional arrays using dictionaries. Each association's key is a row number and the value is an array of elements of the corresponding row.

5. Reimplement the two dimensional array by using an array of indices for the key and the element value as the value of the association.

6. Reimplement `NDArray` from Chapter 7 using a dictionary.

7. Write a description of `IdentityDictionary`.

## 9.5 Dictionary with multiple values

In many situations requiring dictionaries, the value part of each association is a collection. As an example, each English word in an English-French dictionary may have multiple French counterparts. When we add an English-French pair to such a dictionary, the message should create a new pair if the dictionary does not yet contain the English word, but if the English word already is in the dictionary the French word should be added to the existing collection of meanings. Assuming that the dictionary is stored in instance variable dictionary, this can be done as follows:

### `addEnglish:` `string1` `french:` `string2`

"Add `string2` to the collection for `string1` if it exists, otherwise create new `string->collection` association."

`dictionary includesKey: string1`

`ifTrue: [dictionary at: string1 add: string2]`

`ifFalse: [dictionary at: string1 put: (Set with: string2)]`

Checking whether a French word is among the values of such a dictionary could be done by obtaining all the values (a collection of Set objects) and checking whether any of them includes the word:

### `includesFrench:` `aString`

"Check whether French word `aString` is in the dictionary."

`^dictionary values contains: [:collection| collection contains: [:el| el = aString]]`

Deletion is also possible but again not trivial.

Dealing with collection-type values is thus possible but not completely elementary. Since one of the main principles of Smalltalk is that programming should be made as simple as possible by extending the built-in facilities, it makes sense to create a new kind of dictionary whose values are collections and where manipulations of the above kind are implemented as methods. We will create such a class and call it `MultiValueDictionary`. The new class is a specialization of `Dictionary` and all methods available in `Dictionary` should remain executable. We will thus make `Dictionary` its superclass.

If we want to make our new class really useful, it should allow any type of collection as the value of its associations, not just sets as in the above example. However, it seems natural that all collections of a particular instance of `MultiValueDictionary` should be collections of the same kind. As an example, the methods in the example above were based on the assumption that the value is a `Set` and used `Set with:`. To make it possible to create new associations with the proper kind of value collection, each `MultiValueDictionary` must know what kind of collection its values should be. We will keep this information in a new instance variable called `collectionClass` and define the class as follows:

`Dictionary variableSubclass: #MultiValueDictionary`

`instanceVariableNames: 'collectionClass'`

`classVariableNames: ''`

`poolDictionaries: ''`

`category: 'Chapter 9'`
The next question is which protocols inherited from *Dictionary* must be redefined. The place to start is, of course, *creation*. Since our new class has a new instance variable which is essential for the operation of some of the other messages, none of the existing *Dictionary* creation messages is appropriate. We will thus disable all inherited creation messages (`^self shouldNotImplement`) and define new ones as follows:

**newOnClass: aClass**

"Create new MultiValueDictionary with default capacity on the specified class."

^{self new: 2} collectionClass: aClass

**new: size onClass: aClass**

"Create new MultiValueDictionary with specified capacity on the specified class."

^{super new: size} collectionClass: aClass

where *collectionClass*: is an instance accessing method of instance variable *collectionClass*. Time to test!
We executed the following expression with *inspect*

MultiValueDictionary newOnClass: OrderedCollection

and obtained the inspector in Figure 9.7. There is obviously something wrong here - where is our
*collectionClass* instance variable?

<figure><img src="image_180.png" /><figcaption>Figure 9.7. Inspector obtained for a MultiValueDictionary.</figcaption></figure>

There are two possible explanations - either the inspector is 'wrong' or our definition is wrong.
Since our definition is very simple and does not seem to leave room for error, we check whether *Dictionary* happens to have its own definition of *inspect* - and it turns out that it does:

**inspect**

DictionaryInspector openOn: self

where *DictionaryInspector* is a subclass of *ApplicationModel*. We will leave writing a new inspector for *MultiValueDictionary* to you as an exercise and restrict ourselves to redefining *printString* and using it for testing instead of the inspector. As we know, *printString* is based on *printOn*: and we will thus redefine *printOn*: We will reuse the definition inherited from *Dictionary* to display the associations, and append the name of the *collectionClass*:

**printOn: aStream**

"Print dictionary associations followed by name of value class."

super printOn: aStream.
`aStream nextPutAll: ', '; print: collectionClass`

To test, we execute

`MultiValueDictionary newOnClass: OrderedCollection`

with *print it* and *obtain*

`MultiValueDictionary (), OrderedCollection`

as expected.

The next protocol that we must re-examine is *accessing* of keys, values, and associations. `Dictionary` has numerous *accessing* methods and we will restrict ourselves to `at: put:`, leaving the rest to you. Our new `at: put:` must first check whether an association with the specified key already exists and if it does not, it must create one with the appropriate collection as its value. If the key already exists, it will add the new value:

**at: key put: anObject**

"If key already exists, add anObject to its value collection, otherwise create new collection with anObject."

`^(self includesKey: key)`

`ifTrue: [(self at: key) add: anObject]`

`ifFalse: [super at: key put: (collectionClass new add: anObject; yourself)]`

Note that we used `super` to reuse the definition of `at:put`: inherited from `Dictionary`, and yourself to assign the collection as the value. Note also that we returned the argument to follow the general convention used by `at:put`: methods. To test the new method, we executed

`((MultiValueDictionary newOnClass: OrderedCollection)`

`at: 'Science' put: 'Computer Science';`

`at: 'Science' put: 'Physics';`

`at: 'Art' put: 'Music';`

`at: 'Art' put: 'Drama') printString;`

with *print it* and *obtained*

`'MultiValueDictionary ('Art'->OrderedCollection ('Music' "Drama") "Science"->OrderedCollection ('Computer Science' "Physics")), OrderedCollection'`

Perfect! We will leave the rest to you and conclude by showing how much our new class simplifies the definition of an English-French dictionary. In the original implementation, adding a new pair of words required

**addEnglish: string1 french: string2**

`^dictionary includesKey: string1`

`ifTrue: [dictionary at: string1 add: string2]`

`ifFalse: [dictionary at: string1 put: (Set new add: string2; yourself)]`

Assuming that *dictionary* is a *MultiValueDictionary*, the new definition is simply

**addEnglish: string1 french: string2**

`^dictionary at: string1 put: string2`

## Exercises

1. Complete the definition of `MultiValueDictionary` so that its protocols match the protocols of `Dictionary`. Make sure to redefine only those methods that must be redefined.

2. Create an inspector for `MultiValueDictionary`. (Hint: An inspector is an application.)
3. When the collection class of a `MultiValueDictionary` is `SortedCollection`, we should be able to specify its sort block. To do this, we could modify the definition of `MultiValueDictionary` or create a subclass of `MultiValueDictionary` called, for example, `SortedMultiValueDictionary`. Compare these two approaches and implement the one that you consider better.

4. Compare our definition of `MultiValueDictionary` with `MultiValueDictionary` defined as a subclass of `Object` with instance variables collection and `collectionClass`.

5. What requirements must a class satisfy so that it can be used as the argument of the `new:onClass:` message?

## 9.6 Example - A Two-Way Dictionary

In this section, we will design and implement a computerized dictionary for two languages such as English and French. This application, an example of the use of dictionaries, will be designed according to the following specification.

### Specification

The program provides access to two complementary dictionaries using the interface in Figure 9.8. The information kept in the two dictionaries is complementary in that one dictionary can at any time be constructed from the other dictionary and any change made in one dictionary is automatically reflected in the other dictionary.

Each word in each language may have multiple equivalents in the other language. Selecting a word in the list of 'originals' in the user interface displays all its equivalents in the associated list of 'translations' and selections in the two lists of originals are independent. Control over the dictionaries is via pop up menus in the list of 'originals' according to details described below.

The application is opened by executing a Smalltalk opening message which identifies the languages to be used to label the user interface.

<figure><img src="image_181.png" /><figcaption>Figure 9.8. Desired interface of the two-way dictionary.</figcaption></figure>
The pop up menu of both lists of original words is as in Figure 9.9. Its commands allow the user to add a new pair of words, add a new meaning to a word selected in the list, delete the selected word, and correct its spelling.

<figure><img src="image_182.png" /><figcaption>Figure 9.9. Pop up menu of the ‘original’ list widgets.</figcaption></figure>

*Solution:* The problem is conceptually simple and we will implement it using an application model class, and a domain model class called TwoWayDictionary. We will leave the application model class as an exercise and concentrate on the domain model class.

### Class TwoWayDictionary

Class TwoWayDictionary holds two complementary dictionaries<fnref n="2" />, one from language 1 to language 2, the other from language 2 to language 1. Its responsibilities include instance creation, and methods implementing the menu commands in Figure 9.9.

The class will hold the names of the two languages in instance variables `lang1` and `lang2`. The two complementary one-way dictionaries will be stored in instance variables `lang1lang2` and `lang2lang1`. Instance variable `lang1lang2` will hold the language 1 → language 2 dictionary, `lang2lang1` will map language 2 to language 1. The key of each association will be a string and the value will be a sorted collection of strings (a not so accidental use for class MultiValueDictionary from the previous section). Figure 9.10 is an example of a possible state of the two dictionaries; note that all words appear in both dictionaries.

<figure><img src="image_183.png" /><figcaption>Figure 9.10. Typical dictionary components of a two-way dictionary for English and French.</figcaption></figure>

Class TwoWayDictionary is a domain model, therefore not a subclass of ApplicationModel. Since the library does not contain any related class, it will be a subclass of Object. Its definition is

```
Object subclass: #TwoWayDictionary
    instanceVariableNames: 'lang1 lang2 lang1lang2 lang2lang1'
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Book'
```

and its comment is

Class TwoWayDictionary implements two complementary dictionaries such as English-French and French-English. In each of the two dictionaries, one key may have any number of meanings (values). Entering a key-value pair into one of the two dictionaries automatically updates the other dictionary.

<footnote n="2">² Note that we are using delegation to implement a complex dictionary with simpler dictionaries.</footnote>
Instance variables are

`<lang1>` - name of the first language, a String

`<lang2>` - name of the second language, a String

`<lang1lang2>` - one language dictionary, a `MultiValueDictionary` on `SortedCollection`

`<lang2lang1>` - the other language dictionary, a `MultiValueDictionary` on `SortedCollection`

In both dictionaries, keys are strings (words in one language) and values are sorted collections of strings - equivalents of the key word in the other language.

Having decided these basic features, we will now list the selectors of some of the methods and write the corresponding short methods or their descriptions. The remaining methods are left as an exercise.

*Creation* will be implemented by method `on: lang1String` and: `lang2String`. This class method creates a new `TwoWayDictionary` on languages named `lang1String` and `lang2String`. Example of use:

`TwoWayDictionary on: 'English' and: 'French'`

The underlying dictionaries will be two multiway dictionaries using `SortedCollection` as their value. The creation message is

**on: lang1String and: lang2String**

`^(self new) initialize; lang1: lang1String; lang2: lang2String`

and the initialization method creates the appropriate `MultiValueDictionary` objects:

**initialize**

`lang1lang2 := MultiValueDictionary newOnClass: SortedCollection.`

`lang2lang1 := MultiValueDictionary newOnClass: SortedCollection`

We test our definition with the above statement using *inspect* and everything works fine.

*Addition* will be implemented by instance method `addLang1:lang2` which adds a pair of words, one to each, without damaging the information already in the dictionary. Example of use:

`addLang1: 'dad' lang2: 'pere'`

The problem is simple because the `MultiValueDictionary` does all the hard work, and the corresponding definition is

**addLang1: lang1String lang2: lang2String**

"Update both dictionaries."

`lang1lang2 at: lang1String put: lang2String.`

`lang2lang1 at: lang2String put: lang1String.`

`^lang1String -> lang2String`

Note that we return the argument as all `add` methods do. A test with

`| dict |`

`dict := TwoWayDictionary on: 'English' and: 'French'.`

`dict addLang1: 'dad' lang2: 'papa';`

`addLang1: 'dad' lang2: 'pere';`

`addLang1: 'father' lang2: 'papa';`

`yourself`

confirms that everything works.
Deletion will be implemented by instance method `language1Delete: aString` (and a symmetric method `language2Delete: aString`). The method deletes the whole `language1` association with key `aString`, and propagates the change to `language2`. Since this and similar messages are sent by the pop up menu after the user has made a selection in the user interface, we can assume that `aString` is present in the set of keys of `language1`. We can thus use `removeKey:` and similar messages without worrying about the `ifAbsent:` part. The algorithm for responding to pop up command `delete` when a word in language 1 is selected is as follows:

1. Obtain all language 2 meanings of the association whose language 1 key is to be deleted.

2. Delete the `language1-language2` association.

3. Find all language 2 -> language 1 associations corresponding to the words found in Step 1 and delete the language 1 word from their value collection. (The language 1 word is guaranteed to be there.)

and the corresponding definition is as follows:

**language1Delete: aString**

"Remove language1 word aString from both dictionaries."

| meanings |

"Get all language2 meanings for aString."

meanings := lang1lang2 at: aString.

"Remove aString from all associations in language 2 containing them."

meanings do: [:meaning| (lang2lang1 at: meaning) remove: aString].

"Remove association with key aString from language 1. We know that aString is an existing key."

lang1lang2 removeKey: aString

The definition of `language2Delete:` is similar and we leave it to you to test that both methods work.
## Exercises

1. Complete the definition of class TwoWayDictionary and test it.

2. Create the application model of the dictionary application and test it.

3. Our popup menus are in English. Modify the design to make it possible to translate the commands to another language. The technical term for such an extension is internationalization and VisualWorks provides several tools to simplify it. These tools are not included in the basic library but you can solve the problem without them.

## 9.7 A Finite State Automaton

As an example of the use of dictionaries, we will now develop a class implementing a finite state automaton (FSA). A finite state automaton is a very important theoretical concept used in several areas of computer science including hardware design, compiler design, and software engineering.

The principle of an FSA can be formulated as follows (Figure 9.11): An FSA consists of a collection of *states*, each performing some *actions*. When an FSA enters a state, it executes all actions associated with this state and makes a transition to a new state depending on the outcome of these actions. Typically, one of the actions executed in each state is a response to an event such as user input. FSA operation starts in a well-defined *initial* state and continues until the FSA reaches one of its *terminal* states where it stops.

<figure><img src="image_184.png" /><figcaption>Figure 9.11. An FSA with states represented as rectangles and transitions represented as links between states. The initial state is shown as an oval, final states are thick line rectangles.</figcaption></figure>

Since all FSAs work on the same principle, we can implement an FSA as a class whose instances are FSAs with specific behavior defined at the time of their creation. Each FSA must know

* all its states and their associated actions,

* transitions corresponding to action outcomes,

* the initial state,

* the terminal states,

* the current state

For practical reasons, we will also require that an FSA know what to do if the requested destination state does not exist - because the creation message did not provide a proper FSA description.

To describe state-action pairs, we will use a dictionary whose keys are state objects (for example integers or symbols) and whose values are blocks defining the actions executed in this state. Each block must return the next state and thus define a transition.

To illustrate this approach, the state behavior of the FSA depicted in Figure 9.12 can be described by a dictionary containing the following associations which ignore the failure mechanism:
<table><thead><tr><td>key</td><td>value</td></tr></thead><tbody><tr><td>1</td><td>[Transcript show: 'state 1'.<br/>^ (DialogView request: 'Enter name of next state (1 or 2 to continue, 3 or 4 to quit)') asNumber]</td></tr><tr><td>2</td><td>[Transcript show: 'state 2'.<br/>^ (DialogView request: 'Enter name of next state (1 to continue, 3 to quit)') asNumber]</td></tr><tr><td>3</td><td>[Transcript show: 'state 3 - end'. ^3]</td></tr><tr><td>4</td><td>[Transcript show: 'state 4 - end'. ^4]</td></tr></tbody></table>

<figure><img src="image_185.png" /><figcaption>Figure 9.12. Example FSA with transitions obtained from user.</figcaption></figure>

The FSA works in a loop that can be described as follows:

current state := initial state.

[current state := value of block corresponding to current state.

currentState is valid if False: [currentState := failBlock value]]

current state is an end state] while False.

self executeState "To execute action in terminal state."

After this analysis, we can now implement class FSA. Its definition is as follows:

Object subclass: #FSA
    instanceVariableNames: ' currentState endStates initialState stateDictionary failBlock '
    classVariableNames: "
    poolDictionaries: "
    category: 'Book'

The comment is

I implement an abstract finite state automaton.

Instance variables:

<table><tr><td>stateDictionary</td><td>&lt;Dictionary&gt;</td><td>- keys are states, values are blocks; each block returns a next state</td></tr><tr><td>endStates</td><td>&lt;Set&gt;</td><td>- a Set of terminal states, subset of stateDictionary keys</td></tr><tr><td>current state</td><td>&lt;anObject&gt;</td><td>- current state object - a key in stateDictionary</td></tr><tr><td>initialState</td><td>&lt;anObject&gt;</td><td>- initial state - a key in stateDictionary</td></tr><tr><td>failBlock</td><td>&lt;aBlockClosure&gt;</td><td>- block executed on any attempt to make an illegal transition; must return a next state</td></tr></table>

As usual, we will start with a class method to create a fully specified FSA. The definition is

onDictionary: aStateDictionary initialState: anInitialObject endStates: aSet failBlock: aBlock
"Create an initialized FSA."
```
^self new
```

```
onDictionary: aStateDictionary
```

```
initialState: anInitialObject
```

```
endStates: aSet
```

```
failBlock: aBlock
```

where the instance method initializing the created FSA is simply

```
onDictionary: aDictionary initialState: anInitialState endStates: aSet failBlock: aBlock
```

```
"Initialize FSA."
```

```
stateDictionary := aDictionary.
```

```
initialState := anInitialState.
```

```
currentState := anInitialState.
```

```
endStates := aSet.
```

```
failBlock := aBlock
```

The operation of the FSA follows our algorithms and is defined by the following method:

### run

```
"Iterate until FSA enters one of the terminal states."
currentState := initialState.
```

```
(currentState := self executeState.
```

```
(stateDictionary includesKey: currentState)
```

```
ifFalse: [currentState := failBlock value].
```

```
endStates includes: currentState] whileFalse.
```

```
self executeState "Execute terminal state."
```

Method executeState evaluates the action block of the current block and returns the result, presumably the next state. The definition is as follows:

### executeState

```
"Execute action and make transition."
```

```
^(stateDictionary at: currentState) value
```

We will now test FSA on the example in Figure 9.11. To do this, we must create the complete description of the state graph, use it to create the FSA, and start FSA operation. The operation is controlled by the user via dialogs:

```
| dictionary fsa |
```

```
"Create state dictionary."
dictionary := Dictionary new.
```

```
dictionary at: '1'
```

```
put: [Transcript show: 'state 1'; cr.
```

```
Dialog request: 'This is state 1.\Enter name of next state (1 or 2 to continue, 3 or 4 to quit)' withCRs initialAnswer: '1'];
```

```
at: '2'
```

```
put: [Transcript show: 'state 2'; cr.
```

```
Dialog request: 'This is state 2.\Enter name of next state (1 or 2 to continue, 3 or 4 to quit)' withCRs initialAnswer: '2'];
```

```
at: '3'
```

```
put: [Transcript show: 'state 3'; cr. Dialog warn: 'This is state 3 - a terminal state'. '3'];
```

```
at: '4'
```

```
put: [Transcript show: 'state 4'; cr. Dialog warn: 'This is state 4 - a terminal state'. '4'].
```

```
"Create FSA."
```

```
fsa := FSA
```

```
onDictionary: dictionary
```

```
initialState: '1'
```

```
endStates: #('3' '4') asSet
```

```
failBlock: [Dialog request: 'Illegal choice; try again' initialAnswer: ""]
```

```
Transcript clear; show: 'Sequence of states:'; cr; cr.
```

```
"Run."
```
fsa run

The program runs correctly.

Exercises

1. Use FSA to simulate the JK flip-flop. The JK flip-flop is a binary storage element that stores 0 or 1 and changes state depending on its current state and two inputs called J and K. Its transitions are shown in Figure 9.13. Assume initial state 0, have user enter the two inputs.

2. Use FSA to implement a recognizer that reads and calculates non-negative integer numbers such as 13, 0, and 383888495000101 digit-by-digit. The digits are entered by the user with a Dialog request: initialAnswer: message. The machine returns the calculated value when it encounters a non-digit character.

3. The classical application of FSAs is to 'recognize' input sequences. Use the FSA developed in this section to

a. recognize legal Smalltalk identifiers (letter followed by a sequence of letters or digits). Input is via a letter-by-letter dialog, output is to the Transcript. The output will show the entered string followed by the word 'legal' or 'illegal'. This kind of operation is performed by compilers.

b. unlock a door when the user enters the combination '2', '7', '9', '3', '9'.

4. Find how the Smalltalk compiler recognizes identifiers and relate this to Exercise 5.

5. A frequent programming task is reading text, processing it according to some fixed scheme (filtering it), and printing the result. Implement a filter defined as follows:

• Replace every blank line preceded and followed by a line of text with a line of asterisks.

• Replace every block of two or more blank lines between two text lines with one line of dots.

• Leave lines with text unchanged.

As an example of the desired behavior,

Line 1.

Line 2.

Line 3.

Line 4.

should be replaced with

Line 1.

Line 2.

*********************

Line 3.

........................

Line 4.

This behavior can be described as in Figure 9.14. Implement the filter using FSA, extending our definition if necessary.
<figure><img src="image_186.png" /><figcaption>Figure 9.13. State transition table of a JK flip-flop.</figcaption></figure>

<figure><img src="image_187.png" /><figcaption>Figure 9.14. FSA for processing lines of text.</figcaption></figure>

## Conclusion

Sets, bags, and dictionaries are unordered collections which means that their protocol does not allow element accessing by an index. Although the external interface is non-sequenceable, internal implementation is based on sequential storage and uses the `basicAt:` method inherited from `Object`.

Sets eliminate duplication: No matter how many times a particular object is added to a set, the set contains only one occurrence and if this occurrence is deleted no other copies of the element remain in the set. One of the main uses of sets is to eliminate duplication (often by the conversion message `asSet`). Testing whether an element is already in the set is based on hashing - calculation of an integer characterizing the object. A subclass of `Set` called `IdentitySet` uses identity hash for comparison to eliminate the possibility of changed hash values during an object's lifetime. If the hash function is well designed and the set is not too full, hashing allows very fast element access and this is another reason while sets and their subclasses are very popular.

Bags keep track of the number of occurrences of their elements both during addition and during removal. They are little used but their ability to keep the count of the number of copies of individual elements while eliminating their storage is useful.

Dictionaries are sets whose elements are associations, in other words pairs of key-value objects. Because of their special structure, `Dictionary` protocols contain a number of specialized messages and even the messages shared with other collections sometimes have specialized behaviors. Uniqueness of dictionary elements (the essential property of sets) is implemented by comparison of keys. A frequently used subclass of `Dictionary` called `IdentityDictionary` uses identity hashing and equivalence instead of hashing and equality for comparison. A very important subclass of `Dictionary` is `SystemDictionary` which holds information about the structure of the system and its shared objects. Its only instance is `Smalltalk`.

When using an object, it is often essential to decide whether we want to use the object itself or its copy. In many cases, we must use a copy because the original must not be affected by subsequent
operations. A copy may be shallow (new object which shares instance variables with the original), deep (completely separate from the original), or intermediate, obtained in a special way. When using a shallow copy, remember that state changes of the components of the original affect the copy and vice versa.

The difficulty with deep copy is that it is not easy to implement when the copied objects have circular structure. In VisualWorks, copy is implemented as a combination of shallow copy and a post-copy operation which makes it possible to implement any form of copying be redefining the postCopy method. The default behavior is equivalent to shallow copy and it is used by most classes.

**Important classes introduced in this chapter**

Classes whose names are **boldfaced** are very important, classes whose names are printed in *italics* are less important, classes whose names are printed in regular font are not of much interest.

*Association, Bag, Dictionary, IdentityDictionary, IdentitySet, Set, SystemDictionary.*

**Terms introduced in this chapter**

*finite state automaton* - an abstraction of a machine mechanically changing its state in response to actions associated with states

*filter* - a process that mechanically transforms an input (usually text) into a new form

*hash* - an integer characterizing an object; used, for example, to place or find an object in a set efficiently; depends on object's state and may change during its lifetime

*deep copy* - a copy completely disjoint from the original

*identity hash* - a hash that does not change hash value during an object's lifetime

*post copy* - method executed by the copy method after a shallow copy is made; allows customization of copying mechanism

*shallow copy* - a copy in which the top level object is new but its components are shared with the original; the basis of the copy operation in Smalltalk
# Chapter 10 - Streams, files, and BOSS

## Overview

Sequenceable collections are often processed in linear order, one element after another. Although linear access can be performed with collection accessing and enumeration methods, Smalltalk library contains a group of classes called streams that simplify linear access and improve its efficiency. It is important to understand that streams are not a new kind of collection but rather a mechanism for accessing an existing collection.

Smalltalk distinguishes two kinds of streams with largely overlapping protocols - internal and external. Internal streams are used to access sequenceable collections whereas external streams are for file access.

Storing data in a file and reading it back requires two facilities: access to the contents of the file (provided by external streams) and access to the file system itself (for operations such as accessing directories and files, and for creation, naming, and deleting files and directories). Access to the file system is provided by class *Filename*. Most file operations thus require both an instance of an external stream and an instance of *Filename*.

External streams provide byte-by-byte access to file contents but no tools to store objects, thus lacking the facility that most Smalltalk programs need. Although every class knows how to convert its instances into text representing executable Smalltalk code, this facility is too inefficient for larger objects. VisualWorks thus provides a special group of classes for storing objects as binary codes. This tool is called the Binary Object Streaming Service (BOSS). Since storage and retrieval of binary objects depend on files and streaming access, the use of BOSS requires understanding of external streams and *Filename* objects.

## 10.1 Introduction to streams

Sequenceable collections must often be accessed one element after another with intermediate processing, as if viewed through a window that remembers which element is being viewed (Figure 10.1). Another, and historically more relevant analogy, is that a stream is like a digital magnetic tape whose recordings (collections of sound codes) are read one after another in the order in which they were recorded. This kind of access is called *streaming* and although it can be achieved with standard enumeration methods, the Smalltalk library provides a group of classes that makes streaming access easier and more efficient. A stream is thus a tool for viewing existing sequenceable collections - a collection accessor. A stream is *not a* new kind of collection.

<figure><img src="image_188.png" /><figcaption>Figure 10.1. Stream is a mechanism for accessing a sequenceable collection via a positionable window.</figcaption></figure>

Here are a few examples of situations that require streaming:

* Construction of text from strings extracted from a file or entered by the user. Examples include creation of reports and form letters.

* Analysis of text such as extraction of words from an article or processing of Smalltalk source code by the compiler.
* Reading and writing of files.

Execution of each of these tasks involves some or all of the following operations:

* Opening a stream on a collection.

* Selecting the starting position.

* Moving to the next or the previous element and examining its contents.

* Replacing the object at the current position with another object.

* Adding an object behind the object processed so far.

* Peeking ahead at the next element without changing the current position.

* Repositioning the stream pointer to the beginning or the end of the stream, or to any location given by an index.

* Testing whether the position pointer is at the end of the stream.

* Accessing file elements.

Since different tasks require different types of streaming access, Smalltalk streams are implemented by a group of classes, a subtree of the abstract class *Stream*. *Stream* factors out the shared properties of all streams such as having contents (the underlying collection), testing whether the end of the stream has been reached, and moving the position pointer. Some of these methods are completely defined in the abstract class *Stream* and possibly overridden at lower levels, others are defined as 'subclass responsibility'.

An example of a stream operation shared by all types of streams is enumeration. Its implementation is the same for all streams and class *Stream* thus contains its full definition:

**do: aBlock**

"Evaluate aBlock for each of the elements of the receiver."

[self atEnd] whileFalse: [aBlock value: self next] "Evaluate block with successive elements."

Method next which is the basis of the method is left as subclass responsibility.

To emphasize the close relationship between streams and collections, all classes in the *Stream* hierarchy with the exception of *Random* are defined in category *Collections - Streams* even though the *Stream* subtree in the class hierarchy is totally disjoint from the *Collection* subtree<fnref n="1" />. The whole subtree is as follows:

**Object**

**Stream**

PeekableStream

PositionableStream

**ExternalStream**

BufferedExternalStream

ExternalReadStream

ExternalReadAppendStream

ExternalReadWriteStream

ExternalWriteStream

**InternalStream**

ReadStream

WriteStream

ReadWriteStream

TextStream

**Random**

<footnote n="1">¹ Class *Random* is a subclass of *Stream* only because its elements are obtained in a linear fashion. Unlike other streams, elements accessed by *Random* don't exist independently and are created when requested by *stream* next.</footnote>
As we have already suggested, streams can be classified according to several parameters. The first distinction used in the class hierarchy is whether the stream allows reading the next element and returning to the original position; in other words, whether it is possible to "peek" ahead without moving the cell (window) pointer. With elements generated by random number generators, this is obviously not possible since a random number generator cannot be asked to recall the random number that it generated before, and this is where *Random* splits from other streams in the *Stream* tree. Since we have already covered random numbers, the rest of this chapter deals with *peekable* collections only.

The fact that we can peek ahead does not imply that we can reposition the window to any place in the stream, in other words, jump from one place to another. This additional property is needed, for example, for random access of files, and its underlying mechanism is defined in class *PositionableStream* via its instance variable *position*. Its value is an integer number, an index that points to the current position of the window on the stream, an element in the underlying sequenceable collection. Most stream accessing operations first move the pointer by one position "to the right" (increment the index) and then access the corresponding element. The pointer thus always points before the element that will be accessed by the next stream accessing message. Since the index of the first element in a stream is 1, resetting a stream sets *position* to 0. To provide control over positioning limits, *PositionableStream* has two instance variables called *readLimit* and *writeLimit*. These two integers determine the current last position accessed by the stream; the first position is always the element at index 1 of the underlying collection.

Class *PositionableStream* is the root of two sub-trees - internal streams and external streams. *Internal streams* are used for accessing sequenceable collections residing, in principle, in the internal memory of the computer. Smalltalk uses internal streams extensively to construct messages, menu labels, arrays of coordinates of geometric objects, parsing during the compilation of Smalltalk programs, and in other operations. *External streams* are an extension of the stream concept to files. They are used to read or write elements of files stored on external media such as disks or obtained from the network.

One important difference between internal and external streams is in the *kind of objects* stored in their underlying collections (Figure 10.2). Elements of collections accessed by *internal* streams can be any objects such as integers, characters, strings, rectangles, or even other streams. *External streams*, on the other hand, are byte-oriented which means that their elements are individual bytes such as ASCII characters or binary codes with another interpretation. Byte orientation of external streams is due to the fact that files are managed by operating system functions, and operating systems access consecutive elements of files as bytes.

internal stream

<table><tr><td>anObject</td><td>anObject</td><td>anObject</td><td>anObject</td><td>anObject</td><td>anObject</td><td>anObject</td><td>anObject</td></tr></table>

external stream

<table><caption>Figure 10.2. *Internal streams* may stream over collections containing any objects but *external stream* access is byte-oriented.</caption><tr><td>a byte</td><td>a byte</td><td>a byte</td><td>a byte</td><td>a byte</td><td>a byte</td><td>a byte</td><td>a byte</td></tr></table>

Another difference between *internal* and *external streams* is that their hierarchy contains an additional abstract class called *BufferedExternalStream*. This class implements the concept of a *buffer*, a memory area holding the working copy of a portion of a file (Figure 10.3).
<figure><img src="image_189.png" /><figcaption>Figure 10.3. Only a part of a file is kept in the memory.</figcaption></figure>

Another difference between internal and external streams is that internal streams include class TextStream specialized for accessing Text objects. External streams, on the other hand, include appendable streams that allow adding information only at the end of a file which does not have an equivalent among internal streams.

Besides the distinction between internal and external streams, we can also distinguish streams that can only be read from streams that can only be written, and streams that can be either read or written. This classification applies both to internal and external streams although there are a few differences in details.

After this brief overview, we will now present internal streams. External streams, files, and related concepts of external storage are covered in the second part of this chapter.

### Main lessons learned:

* A stream is an accessor of consecutive elements of sequenceable collections.

* The two main groups of streams are internal and external streams.

* Internal streams are used to access sequenceable collections whose elements may be arbitrary objects stored in memory. External streams are used to access consecutive bytes stored in a file or on the network.

* Besides the distinction between internal and external streams, Smalltalk also distinguishes between read-only, write-only, and read-write streams.

* The class hierarchies of internal and external streams are somewhat different. The hierarchy of external streams includes class *BufferedExternalStream* which is responsible for hiding the fact that only a part of a file is present in memory at any time, internal streams include *TextStream*.

## 10.2 Internal streams

The Smalltalk library uses internal streams a lot but novice programmers often neglect them, probably because their functions can be implemented by operating directly on their underlying collections. Or possibly because there is such an overwhelming number of stream methods, some of them with rather obscure behaviors. This is unfortunate because stream methods considerably simplify frequently needed operations in the same way that specialized enumeration methods simplify specialized enumeration. Moreover, streams may significantly improve performance, for example as an alternative of string concatenation. And finally, most uses of streams depend on only four or five simple messages.

In the rest of this section, we will outline stream protocols, and the next section will give examples of their use. Note that although most streaming methods are shared by all stream classes, some are not:
There are methods that only work with external streams, methods that can be used with read streams but not with write streams, and so on. Most of these limitations are obvious and natural.

## Creation

Internal streams are usually created with class methods `on:` with:., or by messages addressed to the underlying sequenceable collections; rarely, streams are created with and `on:from:to:` and `with:from:to:.` All these methods create a new stream over the specified collection and initialize the position, `readLimit`, and `writeLimit` variables. The details are initially a bit confusing because each method initializes these variables differently but you don't have to think about the details in most cases because the typical behavior is quite natural.

It is interesting to note that creation methods succeed even if the underlying collection is not sequenceable (for example a `Set`) but any subsequent attempt to access a stream created over such a collection will fail. Now for the details:

`aStreamClass` on: `aCollection`, creates a stream over `aCollection` and positions the pointer at the start, to `position = 0`. The initial settings of the `readLimit` and `writeLimit` depend on the kind of stream and the effect is summarized in Figure 10.4.

<table><caption>Figure 10.4. Effect of `on:` on various types of internal streams.</caption><thead><tr><td></td><td>position</td><td>readLimit</td><td>writeLimit</td></tr></thead><tbody><tr><td>ReadStream</td><td>0</td><td>end of collection</td><td>end - irrelevant</td></tr><tr><td>ReadWriteStream</td><td>0</td><td>0</td><td>end of collection</td></tr><tr><td>WriteStream</td><td>0</td><td>0 - irrelevant</td><td>end of collection</td></tr></tbody></table>

`aStreamClass` with: `aCollection`, creates a stream over `aCollection` and initializes position, `readLimit`, and `writeLimit` to the last index, positioning the pointer at the end. To remember the difference between `with:` and `on:`, use the mnemonic that the first letter of `with:` is 'at the end of the alphabet' whereas the first letter of `on:` is 'at the start of the alphabet'. The effect of `with:` is summarized in Figure 10.5. with differences with respect to `on:` italicized.

<table><caption>Figure 10.5. Effect of `with:` on various types of internal streams.</caption><thead><tr><td></td><td>position</td><td>readLimit</td><td>writeLimit</td></tr></thead><tbody><tr><td>ReadStream</td><td>end of collection</td><td>end of collection</td><td>end - irrelevant</td></tr><tr><td>WriteStream</td><td>end of collection</td><td>end of collection</td><td>end of collection</td></tr><tr><td>WriteStream</td><td>end of collection</td><td>end - irrelevant</td><td>end of collection</td></tr></tbody></table>

The following are examples of the effect of several stream creation messages:

```
ReadStream on: #(1 3 'abc') "Opens a read stream on array #(1 3 'abc'); position is initialized to 0."
ReadStream with: #(1 3 'abc') "Opens a read stream on array #(1 3 'abc'); position is initialized to 3."
WriteStream on: (String new: 16) "Opens a write stream on an empty string; position is initialized to 0."
ReadStream with: ('abcd') asSet "Succeeds but any attempt to access the stream will fail."
```

Most stream applications use the `on:` creation message and only a few use `with:`. Creating a new stream with message new is illegal because it does not specify the underlying collection.

Instead of creating a stream by sending a creation message to a `stream` class, you can also create a stream by sending `readStream`, `writeStream`, or `readWriteStream` to a sequenceable collection as in

```
#(12 43 23 67) readStream
```

which produces the same result as
ReadStream on: #(12 43 23 67)

## Accessing

This protocol includes many instance messages that return the contents of the stream (the underlying collection), reposition the pointer, or access elements of the underlying collection. The 'setting' messages (various forms of put which add one or more new elements) grow the underlying collection if necessary. Some of the messages in this protocol are:

**size** - returns the larger of readLimit and position. If position is larger, it increases readLimit to position.

**contents** - returns a copy of the part of the underlying collection from the start to the readLimit of the stream. Its definition is

### contents

"Answer a copy of the receiver's collection from 1 to readLimit."

readLimit := readLimit max: position.

^collection copyFrom: 1 to: readLimit

**next** is used for reading the next element. It first moves the pointer to the right by one position (increments position by 1) and returns the element at this position. If the pointer is already at the end of the stream (measured with respect to readLimit or writeLimit), next returns nil and does not change the pointer.

**nextPut**: anObject - increments the pointer and stores anObject as the next element of the underlying collection. Returns anObject just like other adding messages. Overwrites the existing element of the collection if there was one at this position, and grows the collection if the new element is being added to a full collection. It is important to note that the stream does not work with a copy of the collection but with the collection itself.

**nextPutAll**: aSequenceableCollection - stores individual elements of aSequenceableCollection of size n as the next n elements of the stream. Compare this with nextPut: which would add the whole collection as a single element (Figure 10.6). The difference is similar to the difference between add: and addAll: collection messages. Another similarity between add methods in collections and nextPut in streams is that they all return the argument rather than the modified receiver.

<figure><img src="image_190.png" /><figcaption>Figure 10.6. Result of nextPut: (left) and nextPutAll: (right). Note which elements are added and which elements are gone.</figcaption></figure>

**peek** - increments position and returns the element at that position like next, but resets the pointer to its original place.
**upTo:** anObject - repeats sending next until it reaches the first occurrence of anObject or the readLimit. It returns a *collection* whose elements<fnref n="2" /> are the elements retrieved by the consecutive next messages from the start of the iteration up to but *not including* anObject. The pointer is left pointing at anObject so that the next message will return the item following anObject. If anObject is not found, the message returns a collection containing all elements from the current position up to and including the last element of the receiver stream.

**through:** anObject - has the same effect as upTo: but anObject is included in the returned stream. The final value of position is the same as for upTo:.

### Positioning

Methods in this protocol reposition the pointer without retrieving or storing elements.

**position:** anInteger - changes the value of pointer to anInteger. This method is used mainly for reading and the value of anInteger is usually between 0 and readLimit. Remember that the element accessed by next will be the element at position anInteger + 1.

**reset** - resets the pointer to 0 to prepare for access to the first element. Same as position: 0.

**setToEnd** sets pointer to the last element of the stream marked by readLimit.

**skip:** anInteger - jumps over the specified number of elements without accessing them. Performs

**self position:** position + anInteger

In other words, method skip: performs *relative* repositioning with respect to the initial position, whereas position: is for *absolute* repositioning. As a consequence, skip: -1 may be legal but position: -1 never is.

**skipUpTo:** anObject - skips forward to anObject and leaves pointer pointing at it. Next access will thus be to the element following anObject. Returns the receiver stream on success, nil if it does not find anObject.

**skipSeparators** - skips a sequence of any of the following characters: space, cr, tab, line feed, null, and form feed. This and some other methods hint that internal streams are often used for character processing.

**do:** - uninterrupted enumeration over the underlying collection until self atEnd returns true. Since it uses next to access the consecutive elements, it *starts at the current position* rather than at the start of the collection. As a consequence, it *may not enumerate over all elements of the collection*.

### Testing

Testing messages determine whether the stream is empty, what is the current position in the stream, and whether position points at the end.

**atEnd** - returns true if position is greater than or equal to readLimit. If the stream is not defined over the whole underlying collection(e.g, on:from:to:), readLimit does not refer to the last element of the collection.

<footnote n="2">² We will use 'stream elements' to refer to the elements of the underlying collection.</footnote>
empty - tests whether position = 0, in other words, refers to how much of the collection has been viewed. This is somewhat confusing because it is not clear what it means that a stream is empty. As an example

(ReadStream on: 'abcd') isEmpty

returns true although the underlying collection is not empty.

position - returns the current value of the pointer.

The following code fragment illustrates some of these new messages and more examples will be given later:

| stream |
stream := ReadStream on: #(13 3 'abc' 'xyz' $a $b). "Creates new stream over the specified array."
stream contents. "Returns #(13 3 'abc' 'xyz' $a $b)."
stream position. "Returns 0 - stream is positioned to read the first element."
stream next. "Returns 13, the next element of the underlying collection."
stream skip: 2. "Increments position by 2 and returns receiver stream."
stream next. "Returns 'xyz' and increments position."
stream skip: 20. "Opens an Exception notifier - position out of bounds."

## Main lessons learned:

* The main stream protocols are creation, accessing, positioning, testing, and enumeration.

* The essential stream messages are on:, with:, next, nextPut, nextPutAll, and testing.

* Stream creation messages create a stream over a collection and position a pointer at the start or at the end of the underlying collection.

* A stream may be opened over a sub-range of the underlying collection.

* The values of readLimit and writeLimit represents the effective end of the stream.

* The most common accessing messages are next and nextPut. Both first increment the pointer and then access (and possibly change) the collection.

* Positioning messages are used for random (non-linear) access.

* Details of stream messages depend on the kind of stream.

## Exercises

1. What is the relationship between the position and the index in the underlying collection?

2. Examine what happens to the underlying collection when you add new elements at the end of a write stream.

3. Examine what happens to the underlying collection when you add new elements at the end of a write stream opened over its sub-range.

4. How does on:from:to: work and how does it limit the new stream's access to a part of the underlying collection?

5. Message upTo: anObject returns a subcollection of the stream's collection. What happens when you then send nextPut: to this stream?

6. What does skipSeparators return?

7. `printString` for streams returns only the name of the class. Redefine it to return class name followed by contents, position, and (depending on the kind of stream) the value of `readLimit` and `writeLimit`.

8. Can any other enumeration methods in addition to do: be used on streams?

9. Explain the result of each of the following lines:
   (ReadStream on: 'abcdef') next; next; position: 3; next
   (WriteStream on: Array new) nextPut: $a; nextPut: 13
   (ReadStream on: 'abcdef') peek; peek
   (WriteStream on: String new) nextPut: $a; nextPut: $b; nextPut: 3
(WriteStream with: 'abcd') nextPutAll: 'xyz'; yourself
(WriteStream on: 'abcd') nextPutAll: 'xyz'; yourself
(WriteStream with: 'abcd') nextPutAll: 'xyz'; contents
(ReadWriteStream with: 'abcd') position: 2; nextPutAll: 'xyz'; contents

10. How does contents work on writeable streams?

## 10.3 Examples of operations on internal streams

In this section, we will give several examples of stream behavior and demonstrate some of the most common uses of streams.

### Example 1: Stream enumeration

As we already mentioned, stream implementation of `do:` operates only over the elements following the current position. Because the method does not reset the pointer when it ends, the pointer ends up pointing at the end of the stream. The method returns the receiver stream. As an example,

```
| stream |
stream := ReadStream on: 'abcdefg'. "Creates a stream on characters; position = 0."
stream skip: 2. "Value of position is now 2."
stream do: [:element | Transcript show: (element printString)]
```

prints 'cdefg' and returns the read stream with position = 7.

### Example 2: Using streams to edit strings - filtering

**Problem:** String modification is a typical use of internal streams. Write method `replace:` char with: `aString` to replace all occurrences of character `char` with replacement string `aString`. As an example,

```
'This is ~ true' replace: $~ with: 'not' "Should produce 'This is not true'."
```

<figure><img src="image_191.png" /><figcaption>Figure 10.7. Principle of solution of Example 2.</figcaption></figure>

**Solution:** To solve this problem (Figure 10.7), we will create a `ReadStream` on the string entered by the user, create an uninitialized `WriteStream` of suitable size for creating the output, and process the `ReadStream` one character after another, copying all characters except for `$~` into the `WriteStream`, and replacing every `$~` character with 'not'.

We will put `replace:` char with: `aString` in class `CharacterArray` and its definition is as follows:

```
replace: char with: aString
"Replace all occurrences of char with aString."
| output input |
"Open ReadStream on string."
input := ReadStream on: self.
```
"Create a WriteStream on a String."
output := WriteStream on: (String new: self size).
input do: [:ch | "Use the stream to build the result."
ch == char
  ifFalse: ["Make replacement on match."
    output nextPut: ch]
  ifTrue: ["Leave other characters unchanged." output nextPutAll: aString]].
"Returns processed string."

This is a typical use of internal streams - scanning a ReadStream and constructing a WriteStream a piece at a time. Note the use of contents to obtain the resulting string. Since the elements of the underlying String are characters, we use nextPut: to enter the unchanged characters but nextPutAll: to enter the string 'aString' as a sequence of characters.

### Example 3: Constructing a string using a stream

*Problem:* As an experiment with the use of streams, write a code fragment to create a simple personalized letter from a pre-stored template. The letter is a reminder that a book borrowed from the library is overdue and it should have the following form:

May 23, 1997

Dear Ms. Jones,

I would like to remind you that the book borrowed from the Xaviera Library is now overdue.

Yours,

Ivan Tomek
Adjunct Librarian

The program should automatically calculate the date, the user selects one of Mr. Mrs. or Ms. from a multiple choice dialog, and the names of the borrower and the Adjunct Librarian are entered by the user. (Unfortunately, I am usually the one who gets the reminders rather than the one who issues them.)

*Solution:* In this program - another typical application of internal streams - we will use a TextStream because it can handle emphasis and inherits messages for inserting carriage returns, tabs, and other useful characters. We start by opening a TextStream of suitable size, construct the text from strings that are either predefined or calculated or selected by the user, and return the resulting Text object. The principle is simple and the code is as follows:

| labels letter |
labels := #('Miss' 'Mr.' 'Mrs.' 'Ms.').
"Create a TextStream on a String of suitable length."
letter := TextStream on: (String new: 170).
"Construct letter."
letter emphasis: nil; cr; cr;
  nextPutAll: (Date today printString); cr; cr;
  nextPutAll: 'Dear ';
  nextPutAll: (Dialog
    choose: 'Which one do you want?'
    fromList: labels
    values: labels
    lines: 4
    cancel: ["");
    space; nextPutAll: (Dialog request: 'Enter borrower"s name' initialAnswer: "");
  nextPut: $.; cr; cr; tab;
  nextPutAll: 'Please note that the book which you borrowed from our Library is now '; cr;
  crtab: 3; emphasis: #(#bold #underline); nextPutAll: 'overdue';
  emphasis: nil; cr; cr; cr; "Set and clear emphasis"
nextPutAll: 'Yours,'; cr; cr; cr;
nextPutAll: (Dialog request: 'Enter Adjunct Librarian''s name' initialAnswer: ""); cr;
nextPutAll: 'Adjunct Librarian'

Test the program and print the letter – the contents of the letter TextStream. Use class Document.
Note again that this example is only an illustration of the use of streams. To implement the problem of
creating form letters, we would have to create one or more classes to perform the task in a more general
context.

### Example 4: An example of TextStream methods

As an example of how TextStream handles character oriented operations, the definition of cr
inherited from Stream is

cr
"Append a return character to the receiver."
self nextPut: Character cr

and this is then used with the tab method to define crtab as follows:

crtab
"Append a return character, followed by a single tab character, to the receiver."
self cr; tab

### Example 5: Skipping up to a specific character

A compiler skips over characters such as spaces and line feeds which don't have any effect on
execution. This is implemented by messages such as skipTo:, upTo:, and others. We will now illustrate this
principle by reading a string entered by the user and converting it into an array of strings corresponding to
sections of the original terminated by $-. As an example, if the user enters the string

'This is-not-my day'

the program will convert it to

#('This is' 'not' 'my day')

The basis of the solution is message upTo: anObject which returns the collection of objects
preceding the next occurrence of anObject or the tail of the stream; it returns an empty collection when
issued at the end of the collection. The message sets the pointer to anObject so that next access starts just
behind it. Our program again first opens a ReadStream on the original string, and then constructs the
resulting collection by streaming.

|stream collection string|  
"Create OrderedCollection to hold the result – we cannot predict the eventual size."  
collection := OrderedCollection new.  
stream := ReadStream on: (Dialog request: 'Enter text using - as separator' initialAnswer: ").  
[(string := stream upTo: $-) empty] "Get next piece of string. Stop at end of stream."  
whileFalse: [collection addLast: string].  
collection asArray "Convert because the specification required an Array."

### Example 6: Using with: to access the whole underlying stream

When you create an instance of ReadWriteStream on an existing stream, its position is initialized
to 0. As a consequence, a message such as

(ReadWriteStream on: 'A string') contents

returns an empty string and stream size returns 0. If you then add a new element with nextPut:, it will
replace the first element of the original collection, and repeated use of nextPut: will eventually destroy all
original data. If you want to be able to access the contents of the whole underlying collection or add
elements at the end, use the with: creation message as in

| rwStream |
(rwStream := (ReadWriteStream with: 'A string') nextPutAll: '!!!'; yourself) contents.
rwStream nextPutAll: 'And another string!!!'.
rwStream contents "Returns 'A string!!! And another string!!!""

### Example 7: The use of internal streams is not limited to strings

Although internal streams are used mainly for operations on strings, they work with collections of
any objects. In fact, enumeration methods such as collect: and select: defined in class
SequenceableCollection are based on internal streams. As an example, method reverse which returns a
copy of a collection with its elements in reverse order is defined as follows:

#### reverse

"Answer a new sequenceable collection with its elements in the opposite order."

| aStream |
(aStream := WriteStream on: (self species new: self size).
self size to: 1 by: -1 do:
  [:index | aStream nextPut: (self at: index)]).
^aStream contents

### Example 8: Streams can make code more readable

Since operations on streams are actually operations on their underlying collections, what do we
gain by using streams? One advantage of streams is conceptual clarity and simplicity. As an example, the
following two code fragments have exactly the same effect but the second formulation is more natural,
simpler and less error prone because we don't have to deal explicitly with the position pointer:

"Displaying selected elements of a collection. Implementation with collection."
|array position|
array := #('a' 'b' 'c' 'd' 'e').
position := 1.
Transcript show: (array at: position); cr.
position := position + 2.
Transcript show: (array at: position); cr.
position := position + 1.
Transcript show: (array at: position); cr.
etc.

"Displaying selected elements of a collection. Implementation with stream."
| array stream |
array := #('a' 'b' 'c' 'd' 'e').
stream := ReadStream on: array.
Transcript show: (stream next); cr.
stream skip: 1. "Note that we had to increment the pointer by 2 in the previous version."
Transcript show: (stream next); cr.
Transcript show: (stream next); cr.
etc.

### Example 9: Stream operations are often more efficient

A classical example where streams improve execution speed is concatenation. The following two
code fragments produce the same string but the implementation with concatenation is many times slower
than the implementation with streams.

"Test of concatenation. Implementation with string concatenation."
Time millisecondsToRun: [
  | string |
  string := 'abcdefg'.
  1000 timesRepeat: [string := string, 'abcd'] "Returns 181 on my laptop."
"Test of concatenation. Implementation using internal stream"

Time millisecondsToRun: [
    | string stream |
    string := 'abcdefg'.
    stream := WriteStream on: (String new: 8000).
    stream nextPutAll: string.
    1000 timesRepeat: [stream nextPutAll: 'abcd')] "Returns 5."

The reason why concatenation is very inefficient is that it creates a new string containing a copy of the original and then adds the argument string to it. Don't use concatenation if you must repeat it more than a few times and if execution speed is important.

## Main lessons learned:

* Internal streams are used mainly (but not exclusively) for operations on strings.

* Class TextStream adds emphasis handling to inherited character-oriented text operations.

* Appropriate use of internal streams makes programs simpler and often more efficient.

## Exercises

1. Implement the problem in Example 2 with Collection methods and compare the two solutions.

2. Implement the problem in Example 2 with String methods and compare the two solutions.

3. Can you implement Examples 2 and 3 with class StringParameterSubstitution? Note that this implementation of string replacement is also based on streams.

4. Explain the definition of printString with your current background on streams.

5. What will happen if you open a ReadStream and a WriteStream over the same collection and use the two streams alternatively?

6. Browse uses of ReadWriteStream.

7. What happens when you execute nextPut: after reaching the last element and the underlying collection is not large enough?

8. Arrays cannot grow or shrink. What happens when you add an element to a stream whose underlying collection is an array?

9. Write method skipSeparators: aCollection to skip all elements included in aCollection.

10. The Transcript - an instance of TextCollector - is a major application of internal streams. In essence, a TextCollector is a value holder for the Transcript window and its contents are accessed via a write stream. This is why some parts of the Transcript protocol are identical to the protocol of internal streams. Write a short description of TextCollector focusing on its relation to internal streams.
## 10.4 Example: A Text filter

In Examples 2 and 3 in the previous section, we needed to replace strings, sometimes obtained by evaluating a block. In other words, we needed to filter input text and transform it into new text. This seems like a generally useful functionality and we will now implement it as a new class called `TextFilter`.

**Specification:** Class `TextFilter` takes an initial String object and replaces occurrences of any one of matching substrings with a corresponding String or Text object. Replacement objects are specified as String or Text objects or as blocks that calculate String or Text objects.
Examples of application:

* A form letter could contain 'formal parameters' (in the terminology of `StringParameterSubstitution`) such as `<name>` and `<date>`, and the filtering process would replace the first parameter with a string provided by the user, and the second by an expression calculating today's day.

* A text editor could provide an extended string replacement facility allowing the user to replace not just one string but any number of strings simultaneously.

### Scenario

Assume original string = 'abcdefg' and match/replacement pairs `pair1` = 'bc'->'xxx', `pair2` = 'bed'->'y'.

1. Set current position in string to 1. Compare `$a` with the first character of `pair1` key (no match) and first character of `pair2` key (no match).

2. Increment position in string, compare with first character in both pairs, find match in both.

3. Increment position in string, compare with second character in both pairs, find match in both. `pair1` match is complete, perform replacement, reset matching for both pairs.

4. Increment position in string, compare with first character in both pairs, and so on.

**Preliminary Design:** The specification can be implemented with a class-tool and the only questions are how to represent the necessary parameters and how to perform the replacement. We will implement the replacement by scanning the given string character by character and matching it against all match strings at each step. When a match is found, the corresponding replacement is made and the search continues from the next character of the original string. All partial matches are reset at this point.

Considering this principle, we immediately see that the state of processing and additional parameters require the following information:

* The original string and our current place in it.

* The new string as constructed up to this point and our current place in it.

* A collection of match strings and their replacements (strings, texts, or blocks)

* For each match/replacement pair, remember currently reached position in matching.

**Design Refinement:** We will now decide on the details of the components identified in Preliminary Design, and construct the replacement algorithm.

* The original string is accessed one-element-t-a-time and we will access it through a `ReadStream`. This also takes care of keeping track of the current location in the string.

* For the same reason, we will access the new string through a `WriteStream`.

* The obvious storage for strings and their translations is a dictionary with the match string as the key and the replacement string as the value. When we consider that we must also keep track of how much of the match string has been checked, we decide to hold this information also as a part of the value. Altogether the dictionary elements will be match string -> Array (replacement value, position).

The replacement algorithm will be as follows:

1. Create a `ReadStream` over the original string and a `WriteStream` over the string being constructed. Initialize the second element of the value array of each element to 0.
2. Repeat for each position of the input stream beginning from the start:

a. For each element of the dictionary do:

i. Increment current position holder for match string.

ii. Compare input string and match character.

1. If no match, reset current position holder for match string to 0.

2. If match, check if this is the last character to match.

If this is the last character (match succeeded), make replacement in output stream, reset current position holder for match string in all dictionary entries to 0, and repeat Step a.

If this is not the last character (match incomplete), increment current position holder.

The intent is to perform filtering is a one-step operation – by submitting a string with all filter parameters, executing the message without interruption, and receiving the result. We will thus never need more than one instance of the filter at a time and we will implement the method as a class method, somewhat like `sort:` in `SequenceableCollectionSorter`<fnref n="3" />.

We now have all necessary information except for the placement of `TextFilter` in the class hierarchy. Since there are no related classes, we will make `TextFilter` a subclass of `Object`.

Implementation:

The comment of `TextFilter` is as follows:

I implement general filtering of text. To create an instance, I need the original string and two arrays consisting of strings to be matched, and replacements. Replacement values may be string or text objects or blocks. My filtering method returns the result without affection the original.

Class Variables:

<table><tr><td>InputStream</td><td>&lt;readstream&gt;</td><td>streams over input string</td></tr><tr><td>OutputStream</td><td>&lt;WriteStream&gt;</td><td>used to build filtered string</td></tr><tr><td>MatchDictionary</td><td>&lt;String, Text, Block&gt;</td><td>used to do replacements</td></tr></table>

`TextFilter` will implement all its functionality via class method `filter:` `aString match:` `matchArray replace:` `replaceArray`. The definition strictly follows the algorithm outlined above but we will restrict our implementation to string replacements and leave extension to `Text` and `BlockClosure` arguments as an exercise. The definition is as follows:

filter: aString match: matchArray replace: replacementArray

"I filter aString using matchArray and replacementArray, and return the resulting String."

"Initialization."

MatchDictionary := Dictionary new.

matchArray with: replacementArray do:

[:match :replace | MatchDictionary at: match put: (Array with: replace with: 0)].

InputStream := ReadStream on: aString.

OutputStream := WriteStream on: (String new: aString size).

"Filtering."

[InputStream atEnd] whileFalse: [self matchAndReplace].

^OutputStream contents

Most of the work is done by class method `match` which takes a single character from the input stream and tries to match it. Its definition is

matchAndReplace

"Get next character, match it against all dictionary entries, and do replacement if necessary."

| ch |

<footnote n="3">³ Defining behavior via class methods is generally frowned upon by Smalltalk experts because it may complicate specialization via subclassing. In our example, we are following the philosophy of the sorting mechanism in class `SequenceableCollectionSorter` which serves a similar purpose.</footnote>
ch := InputStream next.
"Copy the input character into the output stream for now."
OutputStream nextPut: ch.
"Now try to match against successive entries in the dictionary."
MatchDictionary
keysAndValuesDo:
    [:key :value |
    | index |
    "Get index of next character in this dictionary entry."
    index := (value at: 2) + 1.
    "Check if it equals the input character."
ch == (key at: index)
    ifTrue: [index = key size "We have a match. Did we match the whole replacement value?"]
    ifTrue: "We matched the whole value."
        "Go back in output stream for replacement."
        [OutputStream skip: key size negated.
         "Put replacement into output stream."
         OutputStream nextPutAll: (value at: 1).
         "Reset match positions in all entries."
         MatchDictionary do: [:valueArray |
             valueArray at: 2 put: 0].
             "Done with this character."
             ^self]
    ifFalse: "Not end of matching yet - update index."
        [value at: 2 put: index]]
    ifFalse: "No match, reset index in this entry to 0."
        [value at: 2 put: 0]]

This seems a bit long but that's mainly because of our copious comments. To test the method, I executed the following test code

|matchArray replacementArray|
matchArray := #'(ab' 'eab').
replacementArray := #'(xx' 'yy').
TextFilter filter: 'abcdeab' match: matchArray replace: replacementArray.

with *inspect* and got 'xxcdexx' which is not quite what I expected - I hoped for the 'better' match 'xxcdyy'.
(Essentially, by 'better' I mean 'more compressed'.) What is the problem?

In fact, the problem is with our specification. What is happening is that in our example that the 'ab'
-> 'xx' replacement is made before the method can make the nicer 'eab' -> 'yy' replacement. We should have
said that if several replacements are possible in a given pass, one of those that give the longest replacement
will be made. Implementing this specification would have produced the 'expected' result. We will formulate
a better specification and develop a solution in the next chapter.

Could we have avoided our mistake? If we executed a scenario corresponding to our example in its entirety, we would have noticed the problem. The conclusion is that not only the implementation but also the design and even the specification must be tested.

## Main lessons learned:

* When we know that we will never need several instances of a class, we can implement its functionality as a class protocol.

* Before you conclude that your design is incorrect, make sure that your specification is correct and complete. Better still, make sure that your specification is correct before you start design. A good way to obtain this assurance is to completely execute a set of exhaustive scenarios.

## Exercises
1. Extend TextFilter to accept blocks as replacement arguments as stated in the specification.

## 10.5 Example: Circular Buffer

In computing terminology, a *buffer* is a memory area that accepts data from one process and emits it to another process; the two processes work at their own speeds. An example of the use of a buffer is reading a block of data from a file into memory where it is processed one byte at a time by a program. Another example is a computing node on a network that accepts parcels of data arriving in unpredictable amounts and at unpredictable times, processes them one byte at-a-time, and possibly sends the data on to another network node.

The hardware implementation of buffers often has the form of a special memory chip with a fixed number of memory locations with pointers to the first byte to be retrieved, and to the location where the next byte is to be stored as in Figure 10.8. When a new byte arrives, it is stored at the next available location and the pointer is incremented, and when a byte is required from storage, it is removed from the location pointed to and the pointer incremented.

<figure><img src="image_192.png" /><figcaption>Figure 10.8. Buffer as a fixed size array with pointers to the next available byte and the next available location.</figcaption></figure>

In reality, of course, a byte read from the buffer is not 'removed' and only the changed value of the pointer indicates that the byte has been used. Similarly, an 'empty' position is not really empty but the new value simply overrides the old value. Finally, when a pointer reaches the end of the array, the buffer is treated as if it were circular, as if its beginning were glued to its end, and when the pointer reaches the end, it 'increments' by being repositioned to the start. In mathematical terms, incrementing is performed in modular arithmetic as the remainder of division of the position by the size of the buffer.

The buffer does not, of course, have to be a special hardware chip and, in fact, it usually is not. Instead, it can be just a memory region that emulates the circular buffer area. Implementing this pretend circular buffer structure is the purpose of this section.

**Problem.** Implement a circular buffer based on a fixed-size array. Instances of the CircularBuffer class implementing this structure must be able to return the next available byte as a result of executing the next message which also updates the internal pointer, and to store a byte in response to nextPut; again automatically updating the internal pointer. The buffer can also be tested with messages empty and full.

**Solution.** If it wasn't for the very suggestive choice of message names, our first impulse would probably be to implement CircularBuffer as some kind of collection. On second thought, it becomes clear that CircularBuffer is not a collection but rather a mechanism for accessing the collection hidden inside it. Since the access is 'linear', this immediately suggests that CircularBuffer is a stream. We will thus implement it as a part of the Stream hierarchy.

The next question, of course, is where to put it in the Stream tree. To answer this question, let's start from the top and go down only as far as necessary to inherit useful behaviors. Class PeekableStream adds the ability to peak ahead but if we emulate the model of a hardware chip, such functionality should not be present and we conclude that we should subclass CircularBuffer directly to Stream.

The last question before we start implementing the class is what functionality it should implement. According to the specification, we need an accessing protocol (next, nextPut:), a testing protocol (isEmpty, isFull,
isFull), and it will be useful to implement enumeration (message do:) for consistency with other streams and for printing. A printing protocol is necessary for the inspector and for testing, and initialization is required to back up the creation protocol. Printing obviously enumerates over all elements in the buffer and we will thus need an enumeration protocol. With this, we can now start implementing the class.

The class will need an instance variable for the array that holds the data (array), pointers to the first available location and the first available element (firstLocation and firstElement), and it will be useful to have a variable to hold the state (isEmpty). The modular arithmetic that we will need for updating indices will require the size of the underlying array. We will keep it in an instance variable so that we don't have to retrieve it every time and since the buffer may not be full at all times, we will refer to it as capacity.

The creation message will create an instance with an array of the specified size and initialize the remaining instance variable

**new: anInteger**

^self basicNew initialize: anInteger

where

**initialize: anInteger**

array := Array new: anInteger.
capacity := array size.
firstIndex := 1.
lastIndex := 1.
isEmpty := true

initializes the instance variables in an obvious way. A simple test such as

CircularArray new: 10

executed with *inspect* confirms that everything is OK so far.

What should we implement next? We cannot do anything without nextPut: and next, and these require testing for empty and full so we will first implement the testing methods. Method empty simply returns the value of empty but isFull requires calculation. The buffer is full if the firstLocation has been pushed far enough to coincide with firstElement and so

**isFull**

"Are all slots occupied?"
^(firstElement = firstLocation) and: [isEmpty not]

because the two pointers will coincide not only when the buffer is full but also when it is empty.

With these two methods, we can now implement next and nextPut: Method nextPut: adds a new element if the buffer is not yet full. After the test, it then puts the new element into the first available location and updates the pointer:

**nextPut: anObject**

"Add new element if there is room, otherwise execute exception block."
self isFull ifTrue: [^self error: 'Buffer is full'].
array at: firstLocation put: anObject.
self moveFirstLocationIndex.
^anObject

Moving of the first location pointer is left to another method which increments the pointer using modular arithmetic and adds 1 because modulo n arithmetic counts from 0 to n-1 whereas arrays are numbered from 1 to n-1:

**moveFirstLocationIndex**

"An element has been added, 'increment' firstIndex."
firstLocation := (firstLocation rem: capacity) + 1.