`empty := false`

Method next first checks whether the buffer is empty and if it is not, it returns the element at the pointer location and updates the pointer:

**next**

"Return next element and move pointer, return nil if empty."

`^isEmpty`

`ifTrue: [nil]`

`ifFalse:`

```
[ ] el
```

`el := array at: firstElement.`

`self moveFirstElementIndex.`

`el]`

Here incrementing is done with modular arithmetic as follows:

**moveFirstElementIndex**

"Element was removed, update firstElement."

`firstElement := (firstElement rem: capacity) + 1.`

`empty := firstElement = firstLocation`

Finally, we can now implement printing, in other words method `printOn: aStream`. The desired format is

CircularBuffer (13 25 11)

which hides how the data is arranged internally and shows the first element to be retrieved next as the first element inside the brackets, in this case 13. The definition is simple

**printOn: aStream**

"Append to the argument aStream a sequence of characters that identifies the collection."

`| first |`

`aStream print: self class; nextPutAll: ' ('.`

`first := true.`

`self do: [:element | first ifTrue: [first := false]`

`ifFalse: [aStream space].`

`element printOn: aStream].`

`aStream nextPut: $)`

if we have a `do:` message that processes the elements starting with the first available element and ending with the last one. This operation is implemented as follows:

**do: aBlock**

"Evaluate aBlock with each of the receiver's elements as the argument."

`self empty ifTrue: [^self].`

`firstElement := firstLocation`

`ifTrue:`

`[firstElement to: capacity do: [:index | aBlock value: (array at: index)]].`

`1 to: firstLocation - 1 do: [:index | aBlock value: (array at: index)]]`

`ifFalse: [firstElement to: firstLocation - 1 do: [:index | aBlock value: (array at: index)]]]`

The principle of this method is that if the buffer is not empty, the index of the first available element is either less than the index of the last available element or the opposite is true (Figure 10.9). The handling of these two cases can be deduced from the diagram.

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

<figure><img src="image_194.png" /></figure>
<figure><img src="image_195.png" /><figcaption>Figure 10.9. The two possible relative positions of firstElement and firstLocation. Arrows point from first available element upward. Filled circle denotes the first element, filled square is the last element.</figcaption></figure>

Exercises

1. We have cached the value of size and empty in instance variables to avoid the need to recalculate them. Is there any advantage in caching empty? Implement this modification and note that this internal change has no effect on the behavior of CircularBuffer or any other classes the use it.

10.6 Introduction to files and external streams

External streams are the basis of operations on files and all other data transmission that occurs as a
stream of bytes such as network data transmission. We will focus on the use of external streams with files
which allows operation on textual data, graphics, sound, and other digital information. In this section, we
introduce the basics of file and external streams, and several examples of their use are presented in the
following sections.

Smalltalk operations on files and directories are implemented by combining external streams and class Filename (Figure 10.10). The main purpose of *external streams* is to provide byte-oriented streaming access to data, the role of *Filename* is to construct filenames, allow checking whether a file exists, whether a filename name has the proper structure, creating a new directory or file, and perform other file-system related operations.
<figure><img src="image_196.png" /><figcaption>Figure 10.10. Main classes used in file processing.</figcaption></figure>

The cookbook procedure for processing data stored in a file is as follows:

1. Create a `Filename` object with a filename string. The string is the name of the file that may include its drive/directory path.

2. Create the appropriate kind of external stream and associate the `Filename` object with it.

3. Perform byte operations on to the stream.

4. Close the stream object; this will close the file too.

Closing a file is very important for two reasons. One is that if a file is not explicitly closed, the data 'written to it' may not be stored on the disk. The second reason is that the operating system assigns to each file that it opens one of a limited number of 'handles'. Failure to close a file means that the handle is not released and if too many handles are in use, new files cannot be open. It may then be impossible even to save your work when leaving Smalltalk!

As a preliminary example demonstrating the above procedure and the role of external streams and `Filename` objects, the following code fragment opens a file for writing, stores some information in it, and closes the stream and its associated file.

```
[file fileStream]
file := Filename named: 'c:\testfile'. "Open a file called 'testfile' in the root directory on drive C."
fileStream := file writeStream. "Attach the file to a write stream (write only access)."
fileStream nextPutAll: 'abc'. "Store the ASCII codes of 'abc' in the file buffer."
fileStream close "Flush buffer to disk and release OS handle."
```

Execute the program and open the file with the file editor to see that the file has indeed been created and contains the string 'abc'.

Although almost all Smalltalk applications use files, direct byte-oriented operations on files via streams as shown above are rare (except when reading data, possibly coming from a network) because `Filename` and external stream operations cannot directly store *objects*. Smalltalk programmers thus use files and external streams mainly as a vehicle for more powerful object-oriented tools such as BOSS (Section 10.9) and for operations on directories or files as a whole.

Class `Filename` and various external stream classes contain a large number of methods and we will present only the most important ones. Before we do, however, a few comments about the classes themselves.
Class *Filename* is an abstract class and its concrete subclasses (*MaxFilename*, *PCFilename* and its subclasses, and *UnixFilename*) implement the platform-specific behavior needed on your machine, such as parsing platform-specific syntax of file names. However, you never need to deal with these concrete subclasses because *Filename* automatically sends all platform-dependent messages to the subclass representing your platform. This is done via *Filename*'s class variable *DefaultClass* which holds the name of the appropriate *Filename* class. Removing explicit dependence on one platform makes it possible to write programs that will run on different platforms. This arrangement is similar to the implementation of strings.

*External streams* perform data transfer operations. Instances of external streams are never created by class messages to external stream classes but by messages to the *Filename* object as in our example above. The *Filename* object, in turn, asks class *ExternalStream* to create and return the appropriate kind of stream; this procedure also opens the file.

After this brief introduction, we will now introduce class *Filename* and its essential protocols. We will then present external streams.

### Main lessons learned:

* Byte-oriented file operations require the combination of *Filename* and an external stream.

* *Filename* objects provide interaction with the file system, external streams provide byte-by-byte access to file elements.

* *Filename* is an abstract class which transparently communicates with appropriate concrete subclass.

* Smalltalk programs rarely perform byte-oriented file access explicitly. To store and retrieve objects in files, use tools such as BOSS or a data base program.

### Exercises

1. Examine and describe how *Filename* achieves passing of messages to its concrete subclass. Compare this with the similar behavior of *Character*.

2. We created a write stream by sending *writeStream* to *Filename*. Examine its definition.

## 10.7 Class Filename

Class *Filename* is an interface to the file system and provides access to files and directories. The essence of its comment is as follows:

Class *Filename* is an abstract class. Instances of its subclasses encapsulate the platform-specific syntax of OS file path names. This class can almost be used as a concrete class, except name syntax is not interpreted. There is standard protocol provided to do most of the things that OS's can do with references to files -- deleting, renaming, etc.

The best way to understand the role of *Filename* is to examine its protocols and file-related protocols in other classes.

### Creating Filename objects

*Filename* objects can be created in two ways:

* By sending named: *aString* to *Filename* as in *Filename* named: 'prog'.

* By sending *asFilename* to a string as in 'c:\st\prog' *asFilename*.

In both cases, the string may be either a 'relative' specification (the first example) or an 'absolute' specification (the second example). In other words, the filename string may refer either to a file in the currently active directory or specify the complete path. As another example of relative specification, 'file.st' refers to the file called 'file.st' in the current directory, whereas 'c:\smalltalk\examples\example.1' specifies
the path including the disk drive. Certain messages (but not creation messages) allow wildcard characters # (any single character) and * (any group of characters) inside a filename. As an example, in some contexts 'story.1#' refers to any string consisting of 'story.1' followed by a single character (such as 'story.12'), whereas 'story.1*' refers to any string starting with 'story.1' followed by zero or more characters (as in 'story.1', 'story.12' or 'story.123').

If you are developing an application that should run on several different platforms, you must consider that different operating systems use different separators between directories and file names in the filename path (in our example, we assumed the PC platform which uses \). To get the appropriate separator for an arbitrary platform, use message *Filename separator*; this way, the program can construct path name at run time in the appropriate way. Remember, however, that different platforms also have different rules for the maximum filename length. To get the maximum filename length for a platform, execute *Filename longestLength*. You can ignore these details if your application is designed to run on one platform only.

## Filename prompts in class Dialog

Class Dialog provides several powerful `requestFileName:` messages in the *file name dialogs* protocol. All these methods prompt the user for a file name and return a *string* which can then be used to construct the *Filename* object as explained above. These messages also allow you to specify, for example, whether the file should be new (succeeds only if the file does not yet exist) or old (succeeds only if the file already exists). Some of these messages repeat prompting until the desired condition is satisfied, and some allow you to specify a block to be executed when the message fails. The simplest of these messages is `requestFileName:` which displays a prompt. It can be used as in

```
| file |
file := (Dialog requestFileName: 'Enter file name') asFilename
```

This message behaves just like the familiar *Dialog request*: but allows wildcard characters * and # in the answer. If the user enters a string with wildcard characters, the method displays a pop up menu containing the names of all matching filenames and allows the user to make a selection, try again, or abort by clicking *Cancel* (Figure 10.11). In the last case, the message returns an empty string and this must be kept in mind to prevent `asFilename` from crashing.

<figure><img src="image_197.png" /><figcaption>Figure 10.11. Possible result of typing '*.hlp' in response to Dialog requestFileName:.</figcaption></figure>

The proper use of the combination of `requestFileName:` and `asFilename` should thus be something like
| file name |
name := Dialog requestFileName: 'Enter file name'.
name empty? ifTrue: [^self].
file := name asFilename.
etc.

A more powerful filename dialog message has the form `requestFileName:default:`. This message allows the specification of an initial filename as in

`Dialog requestFileName: 'Select a file' default: '*.st'`

An even more powerful version is `requestFileName:default:version:` which lets you specify not only the default filename but also its type. The version: argument may be `#mustBeNew` (user is asked how to proceed if the filename already exists on the specified path), `#mustBeOld` (user is asked what to do if the name is not found on the specified path), `#new` (user is warned if the file exists), `#old` (user is warned if the file does not exist), or `#any`. Yet another version of file prompt messages is the message `requestFileName:default:version:ifFail:` which includes an exception block to be executed when the 'version' condition fails in the case of `#mustBeNew` or `#mustBeOld`.

Accessing operations are scattered across several protocols and include the following methods:

`contentsOfEntireFile` - opens an external read stream on the file, gets its contents, returns it as a `String`, and closes the stream and the file. The user is not aware of the read stream created and closed during the operation. Note that we can also access the contents of a file by attaching it to an external stream and sending contents to the stream. However, message `contentsOfEntireFile` saves you from creating an external stream and closing it explicitly. The following example creates a new file, stores some data in it, closes the file, and gets and displays its contents.

|file fileStream|  
"Create a file, put some text in it, and close it."  
file := Filename named: 'c:\testfile'.  
fileStream := file writeStream.  
fileStream nextPutAll: 'abc'.  
fileStream close.  
"Display file contents in the Transcript"  
Transcript cr; show: (Filename named: 'c:\testfile') contentsOfEntireFile "Displays the string 'abc'." |

`directory` - returns the directory containing the file corresponding to the `Filename` receiver. As an example,

| file |
file := 'c:\abc\xyz' asFilename.
file directory

returns an object such as a `FATFilename` (a concrete subclass of abstract class `PCFilename` for the MS-DOS operating system). Note that both files and directories are instances of `Filename`.

`Class message defaultDirectoryName` returns the `String` describing the full path of the current directory as in

`Filename defaultDirectoryName "Returns, for example, 'c:\visual\image'"`

The related class message `currentDirectory` returns the corresponding `Filename` directory object.

Deleting, copying, moving, renaming, and printing files
delete - as in file Name delete - deletes the Filename object (a file or a directory). As an example of its use, the following fragment creates and opens a file called 'test' in the root directory of drive C, stores data in it, closes it, displays the file's contents, and deletes the file:

|file fileStream|

"Create, initialize, and close a file."

file := Filename named: 'c:\testfile'.

fileStream := file writeStream. "Create write stream on the file."

fileStream nextPutAll: 'abc'.

fileStream close.

"Display file contents in the Transcript."

Transcript cr; show: (Filename named: 'c:\testfile') contentsOfEntireFile.

"Delete the file."

(Filename named: 'c:\testfile') delete

Note that delete must be sent to the Filename object - the stream does not understand delete.

renameTo: pathname renames the receiver Filename object, *and moves it* to a new directory if the new path is different from the old one; the original name is deleted. As an example,

| filename |

filename := Filename named: 'test'.

filename renameTo: 'c:\smalltalk\examples\example.1'. "Renames and moves the file."

copyTo: pathnameString creates a copy of the receiver under a new name, possibly in a new location. The original file and its name remain unchanged.

To *print* a text file, print its *String* contents. To print a *PostScript* file, use class *Document*.
## Testing

**exists** - checks whether the receiver Filename exists and returns true or false. Note again that the receiver may be a file or a directory. As an example,

Filename defaultDirectoryName asFilename exists

returns true.

**isDirectory** - tests whether the Filename receiver is a directory or a file. Returns true for a directory, false for a file. As an example,

Filename currentDirectory isDirectory

returns true.

## Directory operations

**makeDirectory** - creates a directory according to the specification in the Filename receiver as in

```
(Filename named: 'new') makeDirectory      "Creates subdirectory 'new' of the current directory."
(Filename named: 'c:\dos\new') makeDirectory  "Creates directory 'new' with the specified path."
```

**date** returns an IdentityDictionary containing the dates of creation, last modification, and last access of the receiver - if these parameters are supported by the operating system. As an example,

```
| file |
file := (Dialog requestFileName: 'Enter file name' default: '*.st') asFilename.
file date
```

returns an instance of IdentityDictionary with date information on a file selected by the user. On PC platforms, for example, this fragment will return something like

```
IdentityDictionary (#statusChanged->nil #modified->#(6 April 1993 1:59:50 pm) #accessed->nil)
```

where nil values indicate that the corresponding parameter is not supported on the current platform.

**directoryContents** returns an array of strings, the names of files and subdirectories in the current directory. As an example,

Filename currentDirectory directoryContents

could return something like `#('VISUAL.IM' 'VISUAL.SOU' 'VISUAL.CHA' 'WORKSP.2')`

## Main lessons learned:

* Class Filename supports operations such as deletion, renaming, copying, and closing of files and directories. It also provides tests and access to internal parameters such as the length of a file and the contents of a directory.

* Some file operations require only Filename, others also require an external stream.

* Filename can be used to create directories but creation of files requires an external stream.

* Class Dialog provides several file-related dialogs that search the directory for the specified filename, allowing wildcard characters and specification of the type of the desired file.

## Exercises
1. Try `requestFileName:default:version:` with various values of version: and names of files that already exist/don't yet exist.

2. What happens when you send message directory to a Filename object and the directory with the specified name does not exist?

3. Create a table of all essential messages introduced in this section. For each method, specify whether it is a class or an instance method, what are its arguments, what object it returns, what are its preconditions, and what is its effect.

4. Why are `defaultDirectoryName` and `currentDirectory` class methods?

5. Define method `deleteDirectory`: aString ifFail: aBlock which checks whether aString is a directory name, deletes the directory if appropriate, and executes aBlock otherwise.

## 10.8 Examples of the use of file operations that don't require external streams

External streams are needed only for byte-by-byte access to files. Operations on directories, and operations on the contents of a file treated as a string do not require explicit use of external streams. This section gives several examples of such operations.

**Example: List alphabetically all files in the current directory and their sizes**

**Solution:** As we know, there are two messages to access to current directory. Message `currentDirectory` returns the current directory as a Filename object, and message `currentDirectoryString` returns a String containing the filename path of the current directory. Since we need the contents of the file, we need the Filename object. We will thus use the `currentDirectory` message.

If you examine the Filename protocols, you will find that you can get the contents of a Filename directory object by sending it the `directoryContents` message. This message returns an Array of strings - names of the files and subdirectories in the receiver - and to sort it alphabetically, we will convert it to a `SortedCollection`. To obtain information on the corresponding files, we must create Filename objects over the individual string elements and ask them about their size using the instance message `fileSize` (returns the size of the file in bytes). The whole program is as follows:

```
| names |
```

"Extract names and convert to sorted collection."
names := Filename currentDirectory directoryContents asSortedCollection.
Transcript cr.

"Convert names individually to filenames and extract and print the desired information."
names do: [:name | Transcript show: name; tab; show: name asFilename fileSize printString; cr]

Note that the program does not check whether the extracted names are names of files or directories and lists them all. We leave it to you to correct this imperfection.

**Example 2: Test whether two files (two directories) entered by the user have the same contents**

**Solution:** To check whether two files contain the same data, we don't need an external stream because we can compare the `contentsOfEntireFile` of both files:

```
| file1 file2 text1 text2 |
```

"Let the user select two files from the current directory."
file1 := (Dialog requestFileName: 'Select the first file.' default: '.*') asFilename.
file2 := (Dialog requestFileName: 'Select the second file.' default: '.*') asFilename.
text1 := file1 contentsOfEntireFile.
text2 := file2 contentsOfEntireFile.
text1 = text2

If the files are large, this program will work with two large objects and take a long time to execute. Using streams explicitly may then be preferable.
### Example 3: Let user delete a file from a list

**Problem:** Implement a method to display the file names in the current directory in a multiple choice dialog, and allow the user to delete a file

**Solution:** This problem does not require a specific `Filename` and we will implement it as a class method in `Filename`, following the example of several existing `*fromUser` methods. The method will obtain the current directory, display its contents in a multiple choice dialog asking the user which file to delete, and delete the file if the user makes a selection. The implementation is as follows:

#### deleteFromUser

"Display dialog with names in current directory and allow user to delete one."

| choice filesNames |

"Display dialog with names of all files in the current directory."

`filesNames := Filename currentDirectory directoryContents asSortedCollection.`

`choice := Dialog`

`choose: 'Which file do you want to delete?'`

`fromList: filesNames`

`values: filesNames`

`lines: 20`

`cancel: [

"If the user selected a file, delete it."

`choice empty ifFalse: [choice asFilename delete]`

#### Main lessons learned:

* File and directory operations that don't require explicit byte-oriented access can be performed without external streams. These operations include operations on entire contents of a file, deleting, renaming, accessing contents, and similar operations.

### Exercises

1. Refine Example 1 to distinguish between files and subdirectories. Your version of the program should print 'directory' instead of the size for those filenames that are directories.

2. Define a new method called `=`, to test whether two files or directories have the same contents.

3. Why does Example 2 take so long to execute for larger files?

4. The method in Example 3 is not a safe way to delete files and it does not distinguish between files and directories. Write a new version that will request a confirmation and ask the user whether to delete a subdirectory if it is not empty.

5. When you use `named:` to create a new `Filename` object on a PC platform, the name is reduced to at most 8 characters. How does this happen? Since this can be a problem with names of drives on networks, can it be avoided? (Hint: Try another creation method, possibly inherited.)

## 10.9 External streams

We have seen that `Filename` and external stream functionalities somewhat overlap. If you find it confusing, the rule of thumb is that creating external streams and attaching them to `Filename` objects is necessary only to access the contents of the file in a streaming fashion or to store or access objects created by `BOSS`. External streams are not necessary for operations on whole files and directories.

We have already seen that the attachment of a stream to a file is performed by asking a `Filename` to create a stream of the desired kind. The following messages are available for this purpose: `appendStream`, `newReadAppendStream`, `newReadWriteStream`, `readStream`, `readAppendStream`, `readWriteStream`, and `writeStream`. Each of them creates a different kind of stream over the same file and will now explain them briefly. A summary table is provided below.

### Creating external streams
* **appendStream** opens an 'append stream', a file that allows only sequential writing at the end. As an example, create file 'test' containing the string 'abc' using the file editor. The following program

<table><tr><td>[file fileStream]</td></tr><tr><td>file := 'test' asFilename.</td></tr><tr><td>fileStream := file appendStream.</td><td>"Attach file to an append stream."</td></tr><tr><td>fileStream nextPutAll: 'xyz'.</td><td>"Store the ASCII codes of 'xyz' in the file buffer."</td></tr><tr><td>fileStream close</td><td>"Close file via its associated stream."</td></tr></table>

opens the file for appending, writes the three characters 'xyz' at the end, and closes the file. The file now contains 'abcxyz'. Check this by opening an editor on the file.

* **newReadAppendStream** opens an **ExternalReadWrite** stream at the beginning of the file for unrestricted reading, but writing is restricted to appending at the end. For reading, the file can be positioned with **position**: but this has no effect on writing. The message clears (erases) all original contents if the file already exists; this is suggested by the word **new** in the name of the method.

* **newReadWriteStream** opens a new read/write stream that can be randomly positioned for both reading and writing using **position**. The word **new** in the name of the method indicates that if the file existed before the message was sent, the original contents are deleted. Writing to a position within the file replaces the old byte with the new value.

* **readAppendStream** has the same properties as **newReadAppendStream** but does not reset and clear the receiver file.

* **readStream** can only read an existing file and is fully positionable.

* **readWriteStream** opens a read/write stream on a new or existing file without deleting the old contents. This is indicated by the absence of **new** in the name of the message. The message opens the file at the beginning and allows arbitrary positioning. It behaves as **newReadWriteStream** in all other respects.

* **writeStream** opens a purely sequential write stream at the beginning of an existing or new file. If the file existed, all data is lost. The stream does not understand any positioning messages and cannot be read.

<table><caption>Table 10.1. Properties of external streams.</caption><thead><tr><th></th><th>readable</th><th>writeable</th><th>positionable</th><th>append only</th><th>clears original</th></tr></thead><tbody><tr><td>appendStream</td><td>no</td><td>yes</td><td>no</td><td>yes</td><td>no</td></tr><tr><td>newReadAppendStream</td><td>yes</td><td>yes</td><td>reading</td><td>yes</td><td>yes</td></tr><tr><td>newReadWriteStream</td><td>yes</td><td>yes</td><td>yes</td><td>no</td><td>yes</td></tr><tr><td>readAppendStream</td><td>yes</td><td>yes</td><td>reading</td><td>yes</td><td>no</td></tr><tr><td>readStream</td><td>yes</td><td>no</td><td>yes</td><td>n/a</td><td>no</td></tr><tr><td>readWriteStream</td><td>yes</td><td>yes</td><td>yes</td><td>no</td><td>no</td></tr><tr><td>writeStream</td><td>no</td><td>yes</td><td>yes</td><td>no</td><td>no</td></tr></tbody></table>

To understand how stream messages work, it is useful to examine the definition of **newReadAppendStream** which is as follows:

**newReadWriteStream**

"Answer a new readWrite stream connected to the file represented by the receiver."

^ExternalReadWriteStream on:

(FileConnection

openFileNamed: self

mode: #readWrite

creationRule: #truncateOrCreate)
This explains how the limited number of external stream classes (Figure 10.8) can provide such a variety of accessing modes - the type of access is controlled by an instance of **FileConnection**. The other stream creation messages are similar.

Since a file and its mode of access are two separate things, a file initially accessed via one kind of stream may be closed and accessed again via another type of stream. As an example, we have already seen that you may open a file for writing, store some data in it, close it, and open it for reading later.

## Operations on external streams

The following are the main operations on external streams:

### Accessing

Includes reading or writing of individual bytes to or from the buffer and control of the buffer itself. The operation of accessing messages depends on the principle of the interface between Smalltalk's external streams and the operating system, and between the operating system and disk storage. This will be explained next.

As we already mentioned, external streams are 'buffered' which means that the stream object holds on to the part of the file which it is currently accessing via its instance variable ioBuffer. When accessing operations fill the stream buffer, its contents are automatically sent to the operating system and the buffer is reset. You can also perform this operation explicitly by sending flush, commit, or close to the stream (see below). For read-only streams, the buffer is just a multi-byte window into a file stored on the disk.

In addition to the buffer kept by Smalltalk, the operating system maintains its own buffer which operates in a similar way but is under the control of the operating system. Sending the contents of the stream buffer to the operating system thus writes to the *operating system's buffer* but it does not guarantee that the contents of the buffer is written to the disk ('committed'). Messages close and commit perform even this task.

<figure><img src="image_198.png" /><figcaption>Figure 10.12. Data transfers resulting from various stream messages.</figcaption></figure>

The buffer flushing, committing, and accessing messages are defined on writeable streams (Figure 10.12). Note again that these operations work on external streams, not on **FileName** objects! Note also that **flush** and **commit** are needed only for explicit buffer operations and that these operations happen automatically when the corresponding buffers become full.

* **flush** - sends the bytes accumulated in the stream's memory buffer to the *operating system*.

* **commit** - writes the contents of stream's buffer to the *disk*.

* **next**, **nextPut**: streaming access in the style of **next** and **nextPut**: messages of internal streams. Operate on the contents of the stream buffer and flush or refill it when necessary.

We have already mentioned that external streams are normally read one character at a time; in other words, they are byte-oriented. They can, however, also be accessed in a bit-wise fashion. To access external streams one *bit* at a time, send message binary to the stream. To change bit access back to byte access, send text to the stream. Note that although you can change stream access from byte-oriented to bit-oriented and vice versa while the file is open. On the other hand, you cannot change the type of stream (for example from write only to read only); to do this, you must close the file and create the desired new kind of stream.
## Positioning

* `position`, `position:`, `setToEnd` – work the same way as for internal streams.

In closing, we will now illustrate the difference between the various writeable external streams on a short example.

### Example: Behavior of writeable external streams

In this example, we assume that the underlying file called 'test' already exists and contains the string '123456789'. Each example is executed from this initial state.

* After executing the following code fragment that uses `appendStream`

```text
| stream |
stream := (Filename named: 'test') appendStream.
stream nextPutAll: 'abc'. "Store characters $a, $b, $c at the end of the file."
stream close
```

the contents of the file become '123456789abc'. The new data have been appended at the end, the old data have not changed. Neither positioning nor reading are possible.

* When you change the previous program to use `newReadAppendStream` as in

```text
| stream |
stream := (Filename named: 'test') newReadAppendStream.
stream nextPutAll: 'abc'. "Store characters $a, $b, $c in the file."
stream close
```

the contents of the file become '123456789' to 'abc'. The old data is thus lost. The stream can be positioned with `position: but positioning affects only reading. Writing always occurs at the end of the file.

* With `newReadWriteStream`, writing erases the original contents of the file. The pointer can be repositioned for reading and for writing within the limits of the new contents.

```text
| stream |
stream := (Filename named: 'test') newReadWriteStream.
stream nextPutAll: 'abc'. "The stream now contains three characters $a, $b, $c."
stream position: 1; nextPut: $X. "Replaces the second element."
stream close
```

changes the contents from '123456789' to 'aXc', erasing the original contents. Message `nextPut`: issued after setting `position` to 1 overwrites the element in `position 2` because the value of `position` is incremented before writing takes place.

* With `readWriteStream`, we don't lose the original contents of the file.

```text
| stream |
stream := (Filename named: 'test') readWriteStream.
stream position: stream size. "Position at end."
stream nextPutAll: 'abc'.
stream position: 1.
stream nextPut: $X.
stream close
```

changes the original contents '123456789' to '1X3456789abc'. The stream is fully positionable.

* Finally, a `writeStream` allows positioning and writing starts from the beginning of the file. The original contents of the file are lost.
| stream |

stream := (Filename named: 'test') writeStream.

stream nextPutAll: 'abc'.

stream close

changes the contents of the file to 'abc'.

Finally, note that we have been careful to close the file stream when it was no longer needed.

## Main lessons learned:

* Several kinds of external streams can be opened by sending the appropriate stream creation message to the Filename object.

* External streams differ in the kind of access (read-only, write-only, read-write) and the kind of positioning (random, sequential only, append only) that they provide.

* Stream messages operate on a part of the file stored in a buffer. The contents of the buffer is flushed to the operating system or committed to the disk only when the buffer fills, when a flush or commit message is sent, or when the file is closed.

## Exercises

1. How is it that the reading position of a ReadAppendStream can be changed but writing always occurs at the end of the file?

2. We have seen that different kinds of file access are obtained by collaboration with class FileConnection. Write a short description of this class.

3. For each task listed below, write the message that will open the file for the specified purpose assuming that the file is named 'test' and is stored in directory c:\binary.

a. Append new data to the end of the file.

b. Empty the file and write new data into it in sequential order.

c. Open the file, add data at the end, and read data anywhere in the file.

d. Open the file without losing the existing data and write new data anywhere in the file. No reading is anticipated.

e. Same as the previous situation but you want to be able to read the data randomly too.

4. One of the numerous suggestions for extensions of VisualWorks tools is adding save and load commands to the <operate> menu in the Workspace. Implement these extensions as described below. (Hint: Use the Resource Finder tool to examine the menu bar of the Visual Launcher to find how it opens a Workspace.)

a. Command save opens a file dialog and when the user accepts, the contents of the whole Workspace window is saved in the specified file. The load command works similarly but adds the contents of the file to the current Workspace contents.

b. Add command save it to save only the currently selected part of the Workspace.

5. Define an internal read-append stream that stores its contents in an external stream and resets itself when it reaches a specified size.

## 10.10 Storing objects with BOSS

BOSS - Binary Object Streaming Service - is a very important tool for converting most types of Smalltalk objects into compact binary representation that requires relatively little memory space. Although BOSS is used mainly to store objects in a file and retrieve them, it can also be used for other purposes such as sending objects across a network. BOSS is the essence of all programs that store data in a file.

BOSS is implemented by a group of Smalltalk classes in category System-Binary Storage. It is a very powerful tool that can, for example, store both classes and their instances, help converting from one version of a class to another, and read objects in the sequence in which they were stored or in random order.
In this section, we will limit ourselves to the simplest but most important use of BOSS - storing class instances and accessing them sequentially. For more sophisticated use, refer to User's Guide.
The typical BOSS usage pattern is as follows:

1. Create an instance of class `BinaryObjectStorage` and open it on an external stream associated with a file.

2. Read the stored objects from the stream using `next` or write them to the stream using `nextPut`.

3. Close the BOSS object; this closes the file too.

The main BOSS protocols are as follows:

## Creating and closing BOSS

The following two class methods are used to create BOSS objects and tie them to streams:

* `onOld`: `aStream` creates a BOSS object for reading the stream argument associated with an existing file or for appending to it. The stream must, of course, be capable of the desired type of access.

* `onNew`: `aStream` creates a BOSS object for writing to `aStream` starting at the beginning of the file. The file does not have to be new but will be treated as if it were. The stream must be capable of desired type of access.

* `close` closes the stream and the file associated with the BOSS object.

## Accessing - reading and storing objects, changing position

BOSS is based on streams and its accessing messages are a subset of `Stream` accessing messages.
The most important ones are

<table><tr><td>next</td><td>reads and reconstructs the next object from the BOSS stream</td></tr><tr><td>nextPut: anObject</td><td>increments the position pointer and stores anObject in the stream</td></tr><tr><td>nextPutAll: aCollection</td><td>stores all elements of a collection of objects, one after another</td></tr><tr><td>position</td><td>returns the current position in the stream</td></tr><tr><td>position: changes the current position</td><td></td></tr><tr><td>reset</td><td>resets position to start</td></tr><tr><td>setToEnd</td><td>resets position to end</td></tr><tr><td>atEnd</td><td>tests whether the stream is positioned at the end</td></tr></table>

The following example shows how to use BOSS to store an object in a new file called `'c:\boss.tst'`:

```text
| boss |
"Create a BOSS object."
boss := BinaryObjectStorage onNew: (Filename named: 'c:\boss.tst') writeStream.
"Store object in file using BOSS."
boss nextPut: #('string1' 'string2').
"Close BOSS object and the file."
boss close
```

The following complementary program reads the object back and recreates it. Note that it is not necessary to specify that the object is an array, this information is recovered by BOSS. Using BOSS is thus simple and the only thing you must watch is to assign the retrieved objects to the correct variables when you read the objects back.

```text
| array boss|
"Create a BOSS object."
boss := BinaryObjectStorage onOld: (Filename named: 'c:\boss.tst') readStream.
"Read the array previously stored in the file."
array := boss next.
```
"Close the file."
boss close

In most situations, you will use BOSS to store complete objects by a single operation rather than storing each component separately. As an example, store a whole collection as one object rather than storing the elements as separate objects one after another - and read it back without reconstructing it laboriously by enumeration. If, however, BOSS is used to access and frequently modify a large collection of objects, and if this access is not always sequential, you may want to store the objects one after another.

Another point to realize is that when inter-related objects are 'bossed' to one file, no duplication occurs and object relationships are preserved. This does not happen if the objects are stored in separate files. The following example illustrates the difference.

**Example: Store network of inter-related objects in one file**

Consider the simplest group of inter-related objects – two arrays sharing one element (Figure 10.13). Clearly, this group consists of three objects – the two arrays, and the shared fraction.

<figure><img src="image_199.png" /><figcaption>Figure 10.13. Two arrays sharing one element.</figcaption></figure>

The following program creates the arrays, bosses them in two separate files, and reads them back. When you execute it with *inspect*, you will find that the test at the end returns *false*, indicating that the two reconstituted arrays *do not* share the fraction that the original arrays did (Figure 10.14). This is not surprising because we did not boss out any inverse references from the fraction to the other array.

<figure><img src="image_200.png" /><figcaption>Figure 10.13. The two arrays after bossing out into two separate files, and bossing in again.</figcaption></figure>

| array1 array2 boss x |
x := 3/4.
"Create two arrays sharing one object and boss each to its own file."
array1 := Array with: x.
array2 := Array with: x.
boss := BinaryObjectStorage onNew: (Filename named: 'c:\boss.tst1') writeStream.
boss nextPut: array1.
boss close.
boss := BinaryObjectStorage onNew: (Filename named: 'c:\boss.tst2') writeStream.
boss nextPut: array2.
boss close.
"Read the two objects back."
boss := BinaryObjectStorage onOld: (Filename named: 'c:\boss.tst1') readStream.
array1 := boss next.
boss close.

boss := BinaryObjectStorage onOld: (Filename named: 'c:\boss.tst2') readStream.

array2 := boss next.

boss close.

"Check whether the two arrays still share the element."

(array1 at: 1) = (array2 at: 1) "Returns false."

If we now modify the program to write both arrays to the *same* file

| array1 array2 boss x |

x := 3/4.

"Create two arrays sharing one object and boss both to the same file."

array1 := Array with: x.

array2 := Array with: x.

boss := BinaryObjectStorage onNew: (Filename named: 'c:\boss.tst1') writeStream.

boss nextPut: array1.

boss nextPut: array2.

boss close.

"Read the two objects back."

boss := BinaryObjectStorage onOld: (Filename named: 'c:\boss.tst1') readStream.

array1 := boss next.

array2 := boss next.

boss close.

"Check whether the two arrays still share the element."

(array1 at: 1) = (array2 at: 1) "Returns true."

we find that the two reconstituted arrays now *do* share the fraction, as they did before being bossed out. We conclude that storing multiple objects in one file preserves the original structure of their relationship. In fact, the second version also saves space because it stores the shared fraction object only ones.

In closing, we want to repeat that BOSS is one of the most important Smalltalk tools and if you don't have a data base program, you will probably store all your data using it. The small amount of space that we dedicated to BOSS is a tribute to the simplicity of its basic use and does not reflect its importance. We will use BOSS in all our applications to store persistent data.

## Main lessons learned:

* BOSS - a collection of built in Smalltalk classes - is the standard tool for storing objects in files.

* BOSS is one of the most important VisualWorks tools.

* To use BOSS, create an instance of `BinaryObjectStorage` on a suitable external stream, perform the storage or retrieval operation, and close the BOSS object.

* Upon reading an object, BOSS recognizes its type automatically.

* Store compound objects as single entities rather than component by component.

* Store interrelated objects in the same file.

## Exercises

1. What happens to the value of a variable associated with a `BinaryObjectStorage` when you close the BOSS object?

2. Must the stream used by BOSS be an external stream?

3. Write a program to use BOSS to store an array containing the factorials of all integers from 1 to 20 in file 'test' in directory c:\. Write another program to read the object back and print it in the Transcript.

4. Open a file editor on the BOSS file created in the previous exercise.

5. BOSS can be used as a simple database system by storing elements of a collection in consecutive locations and accessing them by position, for example through some translation table (a dictionary). Explain how this would be done on the example of an inventory of items with unique Ids. Explain the BOSS accessing methods suitable for this use.
6. Write a program that creates two arrays called `array1` and `array2`, both containing element `x = 5/6`. 'Boss' array1 to file test.1a and array2 to file test.1b, and then boss the two objects back in, storing them in variables `array3` and `array4`. The original arrays `array1` and `array2` shared the same element `x`, in other words, there were originally three objects – `array1`, `array2`, and `x`. Arrays `array3` and `array4`, on the other hand, each have their own copy of 5/6 corresponding to four objects altogether. The objects bossed back are thus an imprecise representation of the original objects.

7. Repeat the previous exercise but write the two arrays to the same BOSS file. What do you get when you read the two arrays back? Compare with the previous exercise and state a conclusion about storing networks of inter-related objects.

## 10.11 Other ways of storing objects

As you know, parts of the class library can be stored using `file out` and restored using `file in`. The file out procedure saves the source code and adds a few extra characters to separate, for example, one method from another. `File in` uses these extra characters and the compiler to recompile the code and save it back in the library. As a simple example, the file out of the following method in protocol accessing

```abo Pascal
firstName: aString
firstName := aString
```

is the following ASCII file:

'From VisualWorks(R), Release 2.5 of September 26, 1995 on July 11, 1997 at 12:56:20 am'!

!Name methodsFor: 'accesing'!

```abo Pascal
firstName: aString
firstName := aString! 
```

As we have seen in the previous section, classes can also be stored by BOSS but their restoration requires BOSS classes rather than the compiler.

Classes and their instances can also be stored and restored by methods `storeOn:` and `readFrom:`, both defined in class `Object` and redefined in several classes at lower levels of the class hierarchy. This approach is independent of BOSS but much less efficient and limited, and it is never used in Smalltalk applications. We introduce it only because its implementation is an interesting example of the use of polymorphism and delegation, and because it is the basis of the automatic saving of changes in your library code.

Message `storeOn:` `aStream` constructs an ASCII string describing the receiver and adds it to the specified stream. Message `readFrom:` `aStream` then reconstructs the original object from it as in

```
| dictionary stream |
dictionary := Dictionary new.
dictionary add: 'Saleem' -> 'Khan'; add: 'Ke'->'Qiu'.
stream := WriteStream on: (String new: 20).
"Store the Dictionary object in the stream using storeOn:"
dictionary storeOn: stream.
"Produces stream on '(Dictionary new) add: ("Ke" -> "Qiu"); add: ("Saleem" -> "Khan"); yourself)' .
"Create a copy of the original Dictionary object using readFrom:"
Object readFrom: (ReadStream on: stream contents)
```

as you can see when you execute this fragment with `inspect`.

If the stream in which the string is stored is external, this approach can be used to store an object in a file and reconstruct it but the representation is bulky.
The basic definition of `storeOn`: in Object simply generates messages to create a new instance of the receiver and further messages to initialize its variables. The interesting part of the definition is that it asks each component of the receiver to store itself. Typically, this results in the component asking its own components to store themselves, and so on. You can see how this can create problems if the structure is circular. The definition of `storeOn`: is as follows:

### storeOn: aStream

"Append to aStream an expression whose evaluation creates an object similar to the receiver. This is appropriate only for smaller simpler objects and it cannot handle arbitrary circular references of objects."
`aStream nextPut: $().`
`self class isVariable`

`ifTrue: "For instances of classes with indexable elements."`
`[aStream nextPutAll: '(', self class name, ' basicNew: ' ; self basicSize; nextPutAll: ' ) ]`

`ifFalse: "For instances of classes with named instance variables"`

`[aStream nextPutAll: self class name, ' basicNew']`

"Get values of instance variables of the receiver object being stored and ask them to store themselves using store.."

1 to: self class instSize do:

[:i | aStream nextPutAll: ' instVarAt: ' ; store: i;
nextPutAll: ' put: ' ; store: (self instVarAt: i); nextPut: $;].

1 to: self basicSize do: "Get values of indexed variables"

[:i | aStream nextPutAll: ' basicAt: ' ; store: i; store: (self basicAt: i); nextPut: $;].

`aStream nextPutAll: ' yourself'`

If the object being stored has some special properties, we may be able to store the object more efficiently. As an example, Array redefines `storeOn:` to take advantage of literal arrays as follows:

### storeOn: aStream

"Use the literal form if possible."
`self isLiteral`

`ifTrue: [aStream nextPut: $#; nextPut: $(.`
`self do: [:element | storeOn: aStream. space].`
`aStream nextPut: $)]`

`ifFalse: [super storeOn: aStream] "Use general implementation if not literal."`

and the definition of `storeOn:` in class Point is

### storeOn: aStream

`aStream nextPut: $();`
`nextPutAll: self species name;`
`nextPutAll: ' x: ';`
`store: x;`
`nextPutAll: ' y: ';`
`store: y;`
`nextPut: $).`

Note that the basic definition of `storeOn:` depends on method `store:` which is defined in class `Stream` as follows:

### store: anObject

"Have anObject print itself on the receiver for rereading."
`anObject storeOn: self`

This interesting definition simply exchanges the receiver and the argument of `storeOn:` (`anObject storeOn:` `aStream` is equivalent to `aStream store:` `anObject`) to make the definition of `storeOn:` simpler. Since `store:` both uses and is used by `storeOn:`, the definition of `storeOn:` is recursive - when it stores the values of instance variables of an object, it asks them to store themselves (Figure 10.13).

create some of the code and send `storeOn:`
to components to create the rest
<figure><img src="image_201.png" /><figcaption>Figure 10.13. The definition of `storeOn:` is recursive.</figcaption></figure>

As an illustration of the operation of this recursive definition, consider using `storeOn:` on a literal array containing string elements: The `storeOn:` method creates the code to create a literal array and asks the string elements to create their own description of how they are stored. As a result, when you *inspect*

```
| stream |
stream := WriteStream on: (String new: 16).
#('ab' 'cd' 'ef') storeOn: stream.
stream
```

you will find that the stream's contents are

`'#("ab" "cd" "ef")'`

where the underlined parts were created by the string elements of the array, and the rest by `storeOn:` in `Array`. When `BOSS` stores compound objects, it operates the same way.

As a closing note, the simple nature of `storeOn:` does not allow it to handle circular structures – unlike `BOSS` which does.

### Main lessons learned:

* Methods `storeOn:` and `readFrom:` can store and reconstruct any object that does not have circular structure.

* Both `storeOn:` and `readFrom:` are used by the system but applications use either `BOSS` or a data base system to store objects in files.

* Method `storeOn:` is recursive and delegates the storage of the components of the object being stored to the components themselves.

* Method `storeOn:` cannot handle circular structures.

### Exercises

1. What is the difference between `printOn:` and `storeOn`:?

2. Examine and explain the result of executing `storeOn:` on the object created with message Array with: 'abc' with: (Array with: with: 13 $x with: 5 factorial) with: (Dictionary with: ('key' -> 'value')). Test that `readFrom:` reconstructs the original object.

3. Execute the previous exercise with an external stream and file and open a file editor on the file. Compare the contents of the file with the contents of the equivalent `BOSS` file.

4. Explain the definition of `readFrom:` in three selected classes.

5. Rewrite the definition of `storeOn:` in `Object` without using `store:` to appreciate the gain in simplicity.

6. Explain the definitions of `storeOn:` in the following classes: `Character`, `Collection`, `Date`, and `Time`.
7. How would a Point be stored by the original `storeOn:` method defined in `Object`? How is it stored by its special `storeOn:` method? (Hint: Redefine `storeOn:` in `Point` to use `super storeOn:`.)

8. Find references to `storeOn:` and `readFrom:`.

9. Compare the speed and storage requirements of `storeOn:` and `readFrom:`, and BOSS, by storing several arrays of increasing size. Plot the results in terms of speed and file size as a function of the size of the arrays.

## Conclusion

Sequenceable collections are often accessed linearly - one element after another. When a loop executing identical statements for each element is desired, this is best implemented with enumeration. When access is irregular, for example dispersed over several consecutive statements, streaming (use of streams for accessing) is preferable because it eliminates the need to maintain the current position within the collection. This becomes almost essential when the access is distributed over several methods.

All streams are subclasses of the abstract class `Stream` and can be divided into three groups: class `Random`, internal streams, and external streams. In this chapter, we dealt with internal and external streams and their three main forms - read-only, write-only, and read-write streams.

Internal streams are used for streaming over sequenceable collections, mainly strings and ordered collections. Their main uses are for string processing and their advantage is increased clarity of programs, simplification of programming, and sometimes increased execution speed. Internal streams are heavily used by the system and experienced programmers but novice programmers often don't take advantage of them and access collection elements by their index when streaming would be preferable.

External streams are used for accessing files and networks in a byte-by-byte fashion. In VisualWorks, files are implemented as instances of class `Filename`. Class `Filename` implements Smalltalk's interface to the platform's file system and executes various file-oriented and disk-oriented operations without explicit cooperation of an external stream. (Some of these operations use an external stream but hide it.) When the operation requires explicit access to the elements of the file, an external stream of the appropriate kind must first be created by sending a stream-creation message to the `Filename` object. `Filename` objects themselves are created with a string specifying the name of the file or directory. Class `Dialog` provides several powerful file-request messages that make obtaining the name of a file easier.

To use external streams and files properly, one must understand that external streams use an intermediate buffer object to hold a working copy of a part of the file or transmitted data. Sending `flush` to the stream sends the contents of the Smalltalk buffer to the operating system's buffer, `commit` sends it directly to the disk. The buffer is also flushed or committed whenever it becomes full, and committed when the file is closed by sending the `close` message to the stream.

The Binary Object Streaming Service (or BOSS) stores and restores objects efficiently and with minimum effort on the part of the programmer. To use BOSS, specify the file, create an appropriate external stream over it, create a `BinaryStorageObject` over the stream, perform the required operation, and close the `BinaryStorageObject` object. We have only covered basic storage and retrieval of class instances; more sophisticated uses are described in the User Manual. There are only a few occasions when an application might need to deal with a file directly, such as when you want to read a file containing a digitized picture rather than a Smalltalk object.

Two other ways of storing and restoring objects are the use of a data base system (VisualWorks library does not contain one), and the `storeOn:` and `readFrom:` messages. These two messages are heavily used by the system to save changes to the library but not by applications because they are very inefficient.

## 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.
* `BufferedExternalStream`, *ExternalStream*, *ExternalReadAppendStream*, *ExternalReadStream*, *ExternalReadWriteStream*, *ExternalWriteStream*, **Filename**, *InternalStream*, *PositionableStream*, *ReadStream*, *ReadWriteStream*, *Stream*, *TextStream*, *WriteStream*.

**Terms introduced in this chapter**

* *append stream* - stream allowing adding elements only at the end

* *binary object storage* - storage of objects in binary form rather than as printable ASCII codes

* *buffer* - area in memory holding data such as a part of a file

* *commit* - save contents of a buffer on the disk

* *external stream* - a stream designed for file or network access

* *file handle* - a binary number used by the operating system to refer to a file

* *internal stream* - accessor of sequenceable collections such as strings and ordered collections

* *stream* - an accessor of linearly arranged data

* *streaming* - linear access of sequentially organized data using a stream
# Chapter 11 - Stacks, queues, linked lists, trees, and graphs

## Overview

Although the collection classes presented in previous chapters are sufficient for most tasks, several other structures for holding collections of objects are also commonly used. The most important of them are stacks, queues, linked lists, trees, and graphs. This chapter is an introduction to these structures with emphasis on intuitive rather than most efficient implementations. For a more advanced treatment, we recommend one of the many books on data structures.

A stack is a collection whose elements can be accessed only at one end called the top of the stack. The operation adding an element on the top of the stack is called push, the operation removing the top element from the stack is called pop. Implementing stacks in Smalltalk does not require a new class because stack behavior is subsumed by OrderedCollection. Our coverage will thus be limited to several examples of the uses of the stack.

A queue is a collection in which elements are added at one end and retrieved at the other. Its familiar real-life example is a line in a bank. Queues do not require a new class because their behavior is also a part of the behavior of OrderedCollection and our presentation will thus be limited to examples.

A linked list is a linearly arranged collection of elements that allows insertion and deletion at any place in the sequence. This behavior is necessary in many applications and not easily achieved in the collections presented so far. Smalltalk's class LinkedList implements a basic linked list.

A tree is a structure whose graphical representation looks like a family tree: It starts with a root at the top, and branches downward. Typical uses of trees are the representation of the class hierarchy, storing data for fast access, and translation of program code. Computer applications use many kinds of trees but Smalltalk does not contain a general-purpose tree class. We will develop a class implementing the simplest kind of tree - the binary tree.

Graphs can be used to represent concepts such as road maps, house plumbing diagrams, and telephone networks. They consist of nodes and connections between them. Graphs have many different applications but Smalltalk does not have any built-in graph classes because the system does not need them. We will design and implement a graph class and demonstrate a few typical graph operations.

### 11.1 Stack - an access-at-top-only collection

A stack is usually defined with reference to a stack of cafeteria trays. New objects are added on the top by the push operation, and existing elements can only be removed by the pop operation which removes the top element (Figure 11.1). For obvious reasons, a stack is also called a last-in first-out (LIFO) collection. Stacks are very important in several areas of theoretical Computer Science and in the process of computing.

<figure><img src="image_202.png" /><figcaption>Figure 11.1. Execution of Smalltalk messages is based on a stack of 'contexts'.</figcaption></figure>
In essence, a stack is an ordered collection whose elements can only be accessed at one end. If we treat the start of the collection as the top of the stack, addFirst: performs push and removeFirst performs pop. Alternatively, we can use the end of the OrderedCollection as the top of the stack with addLast: for push and removeLast for pop. If we need a stack and if we want to restrict ourselves to the stack-like behavior of OrderedCollection, there is thus no need to define a new Stack class and this is the approach taken in the built-in VisualWorks library. From a strict OO point of view, however, this approach is not appropriate because it leaves the simulated stack object open to all behaviors of oo instead of restricting it to the very small behavior of stacks.

In the following, we will restrict our coverage to two examples from the Smalltalk environment and leave an implementation of a Stack class as an assignment. Our first example is a behavior that resembles stacks but is not really a stack, the second is a very important use of a stack at the core of Smalltalk implementation.

### Example 1: The stack-like behavior of the *paste* operation

The *paste* command in the text editor pop up menu can paste any of the recently cut or copied strings. To do this, press <shift> when selecting *paste*. This opens a dialog (Figure 11.2) displaying the most recent *copy* or *cut* string at the top and the oldest *copy* or *cut* string at the bottom.

<figure><img src="image_203.png" /><figcaption>Figure 11.2. <shift> *paste* displays the latest *copy/cut* strings and allows selection.</figcaption></figure>

Although this behavior is based on the stack principle and demonstrates its main purpose - keeping recent information accessible in the last-in first-out style - the structure is not strictly a stack: For one thing, the definition of the stack in class ParagraphEditor restricts its depth to five strings. To implement this restriction, updates of the OrderedCollection discard the element at the bottom when the size reaches five elements. Also, before adding a new string, the definition first checks whether the string already is on the top of the stack and if it is, it does not duplicate it. The main difference between the copy buffer and a true stack is that the user can select any string in the buffer and not only the top one.

It is interesting to note that the string buffer is held in a *class* variable of ParagraphEditor, making it available to any instance of ParagraphEditor. As a result, any of the last five strings copied from *any* text editor can be pasted into *any* text editor.

Although the paste buffer is not a pure implementation of a stack, its behavior is a nice illustration of the usefulness of the concept.
## Example 2: Stack as the basis of message execution

When a program sends a message, the context associated with it - the code and the objects that the message needs to execute - are pushed on the top of the context stack. During execution, the Smalltalk *object engine* (the program responsible for managing program execution; also called the *virtual machine*) accesses this information to obtain the objects that it needs and the messages to send. When sending a message, the virtual machine creates a new context for this message, puts it on the stack, and starts its execution. When the message is finished, its context is popped from the stack and execution returns to the sending message (Figure 11.1).

The principle of message execution does not require further elaboration and we will thus dedicate the rest of this section to a brief discussion of contexts, the objects stored on context stacks. The reason for including this subject is its essential importance for understanding Smalltalk operation, and the fact that it illustrates the importance of stacks.

### Context and related concepts

To start this discussion, we will first put message execution into the context of transformation of the source code into an executing program.

Before we can execute a method, its source code must be compiled, for example by clicking *accept*. In response to this, the compiler produces an internal representation of the code whose essential part is an instance of `CompiledMethod` (to be discussed shortly). We will now demonstrate how the compiling process works and what it produces.

Consider a class called `Test` and its instance method

### `test1: anInteger`

```
| temp |
temp := anInteger factorial.
^temp
```

defined in protocol `test`. To see how this method is compiled and added to protocol `test` of class `Test` (with the same result as if you clicked *accept*) execute

```
self halt.
Test compile: 'test: anInteger |temp| temp := anInteger factorial. ^temp'
classified: 'test'
```

When you observe the operation in the Debugger, you will find that execution of this expression consists of two main steps: In the first step, the code is compiled, producing a `CompiledMethod` object which is inserted into the method dictionary of class `Test`. In the second step, this object is complemented by the source code and other information. To see the result, *inspect*

### `Test compiledMethodAt: #test1`:

The returned `CompiledMethod` object has several instance variables and the most interesting ones contain the source code of the method and the *bytecodes* stored in instance variable `bytes`. Under byte codes, you will find the following:

```
short CompiledMethod numArgs=1 numTemps=1 frameSize=12
```

literals: (#factorial)

```
1 <10> push local 0
2 <70> send factorial
3 <4D> store local 1; pop
```
```
4 <11> push local 1
5 <65> return
```

As you can see, a `CompiledMethod` contains information about the number of arguments of the method, the number of its temporary variables, a list of literals - the messages sent by this method (only `#factorial` in this case), and a sequence of bytecodes - an internal representation of the source code ready for execution by the stack-based virtual machine<fnref n="1" />. Let us now examine the bytecodes in more detail:

```
1 <10> push local 0
2 <70> send factorial
3 <4D> store local 1; pop
4 <11> push local 1
5 <65> return
```

The codes in brackets in the second column are expressed in hexadecimal notation, a shorthand for internal binary representation. They are the translation of the original source code and represent ‘opcodes’ of a fictitious Smalltalk CPU. This CPU does not in reality exist but is emulated by the virtual machine which interprets<fnref n="2" /> the codes and produces the effect described next to the byte code. As an example, hexadecimal code 10 has the effect of pushing the value of the first argument of the message on the stack of intermediate results. We will now illustrate how the “interpreter” executes the byte codes representing the method, assuming the following situation:

```
test
"Some method. containing test1."
...
Test new test1: 5
...
```

When the virtual machine encounters, for example, the message `test1: 20` (its `CompiledMethod` equivalent produced by the compiler), it puts its context on the context stack (more on this later) and creates an *evaluation stack* to hold the intermediate results of execution (Figure 11.3). It then starts executing the byte codes of the `test1:` method one after another starting with the code in position 1:

1. Code 10: Push the value of argument 20 ('local object 0') on the evaluation stack.

2. Code 70: Send message `factorial` ('literal 0') to the object on the top of the evaluation stack. This finds and executes the `CompiledMethod` with the byte codes of `factorial` (not shown), and leaves the result (`SmallInteger 720`) on the top of evaluation the stack, replacing the original object (`SmallInteger 20`). Control returns to the `test1:` method. (This `factorial` message `send` is executed in the same way as the `test1:` message that we are now tracing.)

3. Code 4D: Stores the value on the top of the evaluation stack (the result of 20 `factorial`) in `temp` ('local 1') and pops the stack, removing the 20 `factorial` value. This step is equivalent to the assignment part of the assignment statement in the source code.

4. Code 11: Push the `temp` object ('local 1') on the evaluation stack.

5. Code 65: Return to the message that `sent test`: (in this case message `test`), pushing the value of `temp` - the value that `test1` was supposed to return - on the top of its evaluation stack.

<footnote n="1">¹ For more on the virtual machine, see Appendix 8.</footnote>

<footnote n="2">² The statement about 'interpretation' was strictly true for earlier implementations of Smalltalk but modern implementations translate bytecodes into the machine code of the CPU running the program when the method is first invoked during execution. This process, called *dynamic compilation* or *just in time (JIT) compilation* makes execution more efficient. Once compiled, the machine code is stored in a code cache so that it does not have to be retranslated.</footnote>
<figure><img src="image_204.png" /><figcaption>Figure 11.3. Effect of execution of `test1`: on its evaluation stack. In this case, the execution stack never contains more than one element but other methods may require a deeper stack.</figcaption></figure>

Let us now analyze what information the virtual machine needs to have, to be able to do what we have just described. To execute a message, the virtual machine must know

* the *bytecodes* of the message with information about its arguments and temporary variables

* the *sender* of the message (to be able to transfer the result back to it)

* the *receiver* of the message (required by `self`, `super`, and for access to instance variables)

* an *evaluation stack* for calculations required by byte codes

* the *current position* in the execution of the byte code sequence; this object is referred to as the *program counter* or the PC of the virtual machine.

The object containing all this information is called a *context* and it is an instance of class *MethodContext*.

For a concrete illustration of these concepts, create the following method

### test2

| context temp |

context := thisContext. "thisContext is a special variable like self and super. It returns the currently active context."

temp := 3 + 7 * 5 factorial.

^temp

in class Test and execute

self halt.

Test new test2

In the Debugger, execute the message step-by-step and observe the changing value of PC in the *context* variable. Observe also the stack and the stack pointer.

Now that you understand the use of a *context* in execution, let's look at an example of execution in a broader setting. First, create the following three methods in class Test:

### test3

| context |

context := thisContext.

self test4.

^self

### test4

| context |

context := thisContext.

self test5.

^self

### test5

| context |

context := thisContext.

^self
Next, execute the following expression and observe how control passes from one method to another, how their contexts are pushed on top of one another in the context stack, and how they are popped when execution of the method ends:

### self halt. Test new test3

These examples illustrate the critical importance of the stack in Smalltalk: At all times, Smalltalk operation directly depends on two stacks - one for contexts (representing message code), the other for intermediate results of the currently executing message. Whereas the context stack is shared by all contexts, each invoked message has its own working stack associated with its context.

### Main lessons learned:

* A stack is a last-in first-out (LIFO) structure. Elements are added on the top using the push operation and removed using the pop operation.

* The behavior of a stack is included in the behavior of OrderedCollection and there is no need for a Stack class.

* Execution of Smalltalk messages depends on a stack of context objects, each of them carrying all information about a message, its receiver and sender, its arguments and local variables, and current state of execution.

* Translation of the source code of a method into a form executable on the virtual machine is expressed in bytecodes.

* A part of the context of each executing method is an evaluation stack holding intermediate results.

### Exercises

1. Examine the nature of the copy buffer; in particular, check whether its elements must be strings. If not, can you think of some additional uses of the copy buffer?

2. When implementing a stack, is it better to use the end or the start of an OrderedCollection as the top?

3. Implement class Stack with only the essential stack behavior.

4. While debugging, you might want to print the names of selected messages whenever they are sent. You could, of course, use the `show:` message with the name of the selector explicitly spelled out as in `Transcript show: 'Executing with:with:with:'` but this is somewhat awkward. A neater solution is to extract the name of the method from the context. Implement this approach via a new method called `printMethodName`:

5. Browse context-related classes and write a short description.

## 11.2 Context Stack and Exceptions

As another illustration of the use of stacks, we will now implement *Tester*, a tool to help automate the testing of classes. Testing is a very serious concern in software development because all code must be carefully tested before it is delivered to customers. Because testing generally requires verifying program behavior with many test conditions, the process may be very time consuming and expensive. To minimize the effort and time required for this part of program development, software tools have been developed to automate the process as much as possible. In Smalltalk, these test programs often assume that a class under test contains special testing methods in a special protocol, search these methods out, and execute them. We will develop a very simple version of such a program.

Our test tool (to be implemented by class *Tester*) will allow the user to select the class to be tested, locate all the test methods defined in the class, execute them, and write a report to the Transcript. The user interface will be as in Figure 11.4. For each of the executed methods, *Tester* will print the name of the method followed by the result (*success* or *failure*) in the Transcript. If a test method fails, *Tester* also prints
a message to the Transcript. All test methods of a class are assumed to be in class protocol *testing*, and each test must return true if it succeeds and false if it fails.

<figure><img src="image_205.png" /><figcaption>Figure 11.4. Desired user interface for Tester.</figcaption></figure>

The required functionality is described by the following scenarios:

**Scenario 1: User selects a class and test methods and successfully runs the test**

*Conversation:*

1. User clicks class to be tested.

2. System displays the list of all methods defined in its class protocol *testing*.

3. User selects methods to be executed and clicks *Test*.

4. System executes the selected methods and prints report in Transcript.

**Scenario 2: User selects a class and test methods, one of the methods fails during execution**

*Conversation:*

1. User clicks class.

2. System displays list of corresponding test methods.

3. User selects methods to be executed and clicks *Test*.

4. System starts executing the selected methods and one of them fails as 'not understood'.

5. System displays appropriate note in the Transcript and executes the remaining methods.

**Solution:** Scenario 1 can be implemented rather easily but Scenario 2 introduces a problem that we have not yet encountered: The Tester must be capable of completing execution even if a method fails to execute - technically speaking, even when an exception occurs. In the following, we will show how to deal with this problem without explaining how the mechanism works. (We will also skip the user interface of Tester and leave it as an exercise.) In the next section, we will explain the principle of exception handling in VisualWorks and show that it relies on the context stack.

*Preliminary considerations.* To implement the given scenarios, Tester must know how to

1. obtain a list of class names

2. obtain a list of methods in class protocol *testing*

3. execute a method and recover if it raises an exception.
We assume that our test methods don't have any parameters but this restriction could be easily removed

To test whether the method works, we created a class called Test and defined the following three methods in its class protocol testing:

### test1

"Should cause an exception."
3 open.
^true

### test2

"Should execute and return true."
^3 factorial = 6

### test3

"Should execute and return false."
^3 squared = 10

Since we don't have the proper user interface, we tested our code by executing

Tester new testClass: Test methods: #(#test1 #test2 #test3)

which produced the following expected result:

#### Results of test on class Test

test1 Message not understood

test2 success

test3 failure

Watch out and make sure that you put your Test test methods in the correct class protocol, otherwise you will get only 'message not understood' reports. We leave the full implementation of Tester with the prescribed user interface as an exercise.

### Main lessons learned:

* VisualWorks Smalltalk has a built-in mechanism for dealing with exceptional situations. It allows the programmer to anticipate exceptional behaviors and deal with them programatically, preventing the program from raising an exception.

* Exception handling depends on instances of class Signal.

### Exercises

1. Implement and test the Tester.

2. Generalize Tester to handle test methods with any number of arguments.
### 11.3 More about exceptions

To explain the internal operation of exceptions, we will now take our example from the previous section and trace its execution. The sequence is lengthy and we suggest that you read and execute it, read the summary, and reread the trace one more time. Our test code is as follows:

```ruby
self halt.

ArithmeticValue divisionByZeroSignal
    handle: [:exception| Transcript cr; show: 'Division by zero'.
            exception return]
    do: [ 3 / 0].

Transcript cr; show: 'Look ma, no exception window'
```

and the main events that occur in its execution are as follows (Figure 11.5):

Expression `ArithmeticValue divisionByZeroSignal` returns the `DivisionByZeroSignal` object. This `Signal` object then executes `handle:do:` which is defined as follows:

```
handle: handlerBlock do: doBlock
"Execute doBlock. If an exception occurs whose Signal is included in the receiver, execute handlerBlock."
<exception: #handle>
^doBlock value
```

The message first evaluates the `doBlock` which in our example invokes the division message `3/0`. As this message executes, it eventually reaches the following method in class `Fraction`:

```
reducedNumerator: numInteger denominator: denInteger
"Answer a new Fraction numInteger/denInteger."
| gcd denominator numerator |
denominator := denInteger truncated abs.
denominator isZero
ifTrue: [^self raise: #divisionByZeroSignal
        receiver: numInteger
        selector: #/
        arg: denInteger
        errorString: 'Can''t create a Fraction with a zero denominator']
etc.
```

If the denominator argument is 0, the method sends `raise:receiver:selector:arg:errorString: defined` in the `ArithmeticValue` superclass of `Fraction` as follows:

```
raise: signalName receiver: anObject selector: aSymbol arg: anArg errorString: aMessage
^(self perform: signalName) raiseRequestWith: (MessageSend receiver: anObject selector: aSymbol argument: anArg) errorString: aMessage
```

This message essentially asks the appropriate `Signal` to 'raise an exception request'. The part

`self perform: signalName`

returns `DivisionByZeroSignal`, and

`MessageSend receiver: anObject selector: aSymbol argument: anArg`

returns a `MessageSend`. This is an interesting object and we will digress briefly to explain it. Its *print it* execution in the debugger produces
a MessageSend with receiver: 3, selector: #/ and arguments: #(0)

which shows that this object knows the receiver, the selector, and the arguments of a message, and is an
instance of class MessageSend, a subclass of Message. The comment of Message is as follows:

Class Message represents a selector and its argument values. Generally, the system does not use
instances of Message. However, when a message is not understood by its receiver, the interpreter will
make up a Message (to capture the information involved in an actual message transmission) and send it as
an argument with the message doesNotUnderstand:.

In other words, instances of Message are not used to execute messages (messages are compiled
from byte codes into machine code and executed by the CPU). But when a message is not understood, the
system creates a Message, passes it up the inheritance chain from the original receiver to Object to produce
an appropriate doesNotUnderstand: message. This explains the secret of doesNotUnderstand:.

Class MessageSend, which is what we are dealing with here, adds several new behaviors and
information about the sender. Its class comment is as follows:

A MessageSend represents a specific invocation of a Message. It is essentially a message send
represented as an object, and supports protocol for evaluating that send.

After this digression, let's return to our original problem. All arguments of
raiseRequestWith: errorString: are now available and Signal executes it. This method is defined as follows:

`raiseRequestWith: parameter errorString: aString`

"Raise the receiver, that is, create an exception on the receiver and have it search the execution stack for a
handler that accepts the receiver, then evaluate the handler's exception block. The exception block may
choose to proceed if this message is sent. The exception will answer the first argument when asked for its
parameter, and will use aString as its error string"

```
^self newException
    parameter: parameter;
    errorString: aString;
    originator: thisContext sender homeReceiver;
    raiseRequest
```

The first thing that happens is self newException according to

`newException`

"Answer an appropriate new Exception object.Subclasses may wish to override this."
^Exception new signal: self

This returns a new Exception object whose main function is to know which kind of Signal is
associated with it. In our case, this is the DivisionByZeroSignal signal. As the next step,
raiseRequestWith: errorString: obtains some additional information and raiseRequest raises the exception,
triggering a sequence of events to find the handler code. To do this, raiseRequest searches the context stack
from the top down until it finds the context in which everything started, in our case the unboundMethod

self halt.
ArithmeticValue divisionByZeroSignal
    handle: [:exception| Transcript cr; show: 'Division by zero'.
        exception return]
    do: [3 / 0].
Transcript cr; show: 'Look ma, no exception window'

The highlighted handle: block is now evaluated, displays 'Division by zero' in the Transcript, and
proceeds to exception return. This message 'unwinds' the context stack (the whole context stack is still
there, the exception only accessed and executed the handler block), removing all contexts down to the
originating context and terminating their execution. Our unboundMethod context is now on the top of the stack and execution continues at the point where we left off in our test program.

<figure><img src="image_206.png" /><figcaption>Figure 11.5. Behavior of the context stack in the execution of the test example. The class in which the currently active message is defined is shown below the context stack. Occurrence of exception is indicated.</figcaption></figure>

Let's now summarize what we found: To execute a block of statements safely, let a Signal execute AS IN

aSignal handle: blockThatHandlesException do: blockToBeExecutedWhereExceptionCouldOccur

The sequence of events is as follows:

aSignal evaluates the do: block. If the block evaluates normally, execution continues to the next message. If a message in the do: block raises an exception addressed to aSignal, aSignal executes the following exception handling mechanism:

a. aSignal creates an Exception object.

b. The Exception object searches the context stack looking from top downward for the context of the Signal that raised the exception and executes its handler block – the argument of handle:.
c. In our case, the handler sends *return* and in response to this, the *Exception* object unwinds all contexts from the top of the context stack down to and including the *handle:do*: context and execution continues.

We have only scratched the surface of exception handling and we encourage you to explore it further. Exception handling is very important because many situations require catching illegal or special situations and handling them. Some of the examples are attempts to execute a message that the receiver does not understand, sending a mathematical method with inappropriate arguments, accessing an array with an index out of bounds, and failed file access. The principle of implementation of exceptions again shows the critical importance of stacks in Smalltalk's operation.

In closing, note that numerous signals and other ways of handling exceptions are predefined. The following classes contain the most useful signals: ArithmeticValue, BinaryStorage, ByteCodeStream, ByteEncodedStream, ClassBuilder, CodeStream, ColorValue, CompiledCode, Context, GraphicalContext, KeyboardEvent, Metaclass, Object, ObjectMemory, OSErrorHandler, Palette, ParagraphEditor, and Process. The programmer can also define new signals to intercept any desired conditions.

### Main lessons learned:

* Signal delegates the handling of exceptions to an instance of Exception.

* Exception handling depends on the context stack.

* A number of Signal objects are built into the library and users can define their own as well.

### Exercises

1. Assume that two other exceptions that might occur in our test methods are division by zero and subscript out of bounds. Modify Tester to intercept these exceptions. (Hint: Use class HandlerList.)

2. Modify Tester to catch *any* error condition. (Hint: Examine the Object protocol.)

3. Explain the role of the MessageSend object in exception handling.

4. MessageSend objects can be evaluated as in (MessageSend receiver: 3 selector: #factorial) value. Execute 3 + 4 and 3 between: 5 and: 17 using this technique.

5. What happens when you remove exception return from the handle: block?

6. What other messages can be sent to the Exception object in the handle: block and what is their effect?

7. Trace the operation of doesNotUnderstand: by executing $s factorial. Write a short description.

## 11.4. Queues

A queue is a collection of linearly ordered elements in which elements are added at one end and retrieved at the other end (Figure 11.6). As in a queue in a bank, the first item entering the queue is also the first to be retrieved and removed from the queue and this is why a queue is also called a first-in-first-out (FIFO) structure.
<figure><img src="image_207.png" /><figcaption>Figure 11.6. In a queue, elements are added at the tail and removed at the head.</figcaption></figure>

In spite of its simplicity, the queue is a very important concept with many applications in simulation of real life events such as lines of customers at a cash register or cars waiting at an intersection, and in programming (such as printer jobs waiting to be processed. Many Smalltalk applications use a queue but instead of implementing it as a new class, they use an OrderedCollection because it performs all the required functions<fnref n="3" />. Since the concept is so simple, we will limit ourselves to an illustration of its use on two examples, one in this section and one in the next.

## Simulating a bank queue

At the beginning of the design of a new bank outlet, the designer needs to know how many tellers to provide to satisfy the expected number of customers, and the management will need how to staff the tellers to guarantee satisfactory but economical handling of customers. In our example, the management wants to simulate the following situation in order to evaluate the need for tellers, the cost of operation, and the number of customers that can be handled.

**Problem:** A bank has a certain fixed number of teller stations (Figure 11.7). Customers arrive at unpredictable random times and queue up for service. There is a single queue and when a teller becomes available, the customer at the head of the queue goes to this teller. Each customer has an unpredictable number of transactions and takes an unpredictable amount of time to process. Our task is to develop and test a program to simulate this situation - but not to use it to make managerial decisions.

<figure><img src="image_208.png" /><figcaption>Figure 11.7. Bank layout.</figcaption></figure>

**Preliminary considerations:** The task has several components. We must

* decide how to model the random arrivals of customers and their random servicing times,

* identify the external parameters that characterize the problem,

* identify expected results

* identify, design, and implement the classes involved in the simulation,

* decide on the user interface.

<footnote n="3">³ Just as with stacks, a cleaner implementation would be a Queue class with behaviors limited to those required by a queue.</footnote>
## Modeling randomness

We will assume that the unpredictable parts of the behavior of the problem can be described by a probabilistic model. In other words, we will assume that we can formulate a mathematical function describing the probability that a new customer will join the queue within the next n minutes, and we will use a random number generator to generate customers according to this formula. We will use the same principle to determine how much time each individual customer spends at the teller.

Practitioners of simulation use a variety of probabilistic models in their simulations, all of them based on specific mathematical assumptions. Matching the situation at hand with the proper set of assumptions requires some knowledge of probability and an understanding of the domain that is being simulated and we will restrict ourselves to the simplest model – we will assume that the distribution of arrival times is *uniform*. In other words, we will assume that there is a certain minimum and maximum inter-arrival time, and that any time between these two limits is equally likely to occur. The advantages of this model are that it is simple and that generation of random numbers is already implemented by class *Random*, its disadvantage is that it does not describe a bank queue well. We will leave a more realistic model as an exercise.

## External parameters

In order to make simulation possible, we must identify the parameters that must be specified to start a new simulation. From the specification of the problem and from our discussion of modeling of randomness, it is clear that we need the following parameters:

* Total number of tellers.

* Minimum inter-arrival time.

* Maximum inter-arrival time.

* Minimum expected time required to service a customer.

* Maximum expected time required to service a customer.

* Desired duration of simulation in terms of time or number of customers.

All time-related parameters are expressed in fictitious time units.

## Expected results

We will restrict ourselves to creating a log listing customer arrival times, customer departure times, and the average length of the queue calculated over the whole simulation.

## Desired user interface

The user interface must make it possible to enter any combination of input parameters and run a simulation. The input of data will be as in Figure 11.8 and the results will be printed in the Transcript ordered along the fictitious time axis.
<figure><img src="image_209.png" /><figcaption>Figure 11.8. Desired user interface. The *Show steps* check box determines whether all customer transfers are output to the Transcript or not.</figcaption></figure>

### *Class exploration*

The objects immediately identifiable from the specification are customer objects (class Customer), tellers (class Teller), and the queue (class Queue). We also need an object to generate new customers and add them to the queue (class CustomerProducer). With this basic set of objects, let us explore how the simulation might proceed:

* The CustomerProducer generates a new customer and adds it to the queue. It then creates a random inter-arrival time t and another customer who will enter the queue at time t.

* The customer in the queue is allocated to the first available teller. (This is not quite fair because the first teller will be getting more work than others and we should allocate customers to tellers randomly. In our problem, such considerations are irrelevant because they don't change anything on the outcome.)

* The teller starts processing the customer and releases him or her after the amount of time required for processing by this particular customer object. This parameter is generated by CustomerProducer.

* From this point, execution continues along the following lines until the total length of simulation is completed:

* If one or more tellers are available and a customer is waiting, the customer is sent to the first available teller.

* When the inter-arrival time expires, the CustomerProducer generates a new customer object and adds it to the end of the queue. It also generates a new inter-arrival time to be used to generate a new customer.

* Processing of customers by tellers is as explained above.

This algorithm suggests that the simulation is driven by time – the ticks of a fictitious clock determine when new customers are produced and when they are released by teller. We thus need a time managing object (class SimulationManager) whose responsibility will be to notify the CustomerProducer, Teller, and Queue objects when a unit of time expired. These objects will be responsible for taking an appropriate action. We also need to take care of the results. We will have the Queue and Teller objects report the appropriate information and the Queue object will be responsible for calculating the average
queue length. The output will, of course, be left to the application model (class BankSimulation) to display. This way, if we want to change the user interface (output of results) or make our simulation a part of a larger scheme, the domain objects can stay the same and only the application model must be changed.

## Preliminary design of classes and their responsibilities

We have, so far, identified need for the following classes:

* BankSimulation. In charge of user interface: Input of parameters, start of simulation, output of results.

* Customer. Knows when it entered the queue and how much processing time it will require from a teller.

* CustomerProducer. Generates Customer objects with random values of processing time, keeps information about inter-arrival time and uses it to produce another customer when the time arrives.

* Queue. Knows its customers, can accept new Customer objects, knows how to check whether a Teller is available, knows how to send a Customer to a Teller. Calculates queue statistics and notifies BankSimulation when a customer is added.

* SimulationManager. Starts, runs, and ends simulation. Collects results at the end and notifies BankSimulation. Issues timing information to CustomerProducer, Queue, and Teller objects.

* Teller. Knows how to accept and process a customer, knows whether it has a Customer. Notifies BankSimulation when a customer arrives or is released.

Is this set of classes complete? To find out, we will re-execute our informal scenario dividing it into three phases: simulation start up, body (repeated over and over until the end of simulation), and end of simulation. The following is a rather detailed description with comments on the feasibility of individual steps within the existing class descriptions:

<table><thead><tr><th>Phase</th><th>Description of step.</th><th>Comment</th></tr></thead><tbody><tr><td rowspan="10">Start up</td><td>BankSimulation gets valid parameters and starts SimulationManager.</td><td>OK</td></tr><tr><td>SimulationManager initializes time and asks CustomerProducer, Queue, and Teller to initialize themselves.</td><td>OK</td></tr><tr><td>CustomerProducer generates a Customer with random processing time and adds it to the Queue.</td><td>How?</td></tr><tr><td>Queue tells BankSimulation that it received a Customer.</td><td>OK</td></tr><tr><td>BankSimulation outputs the event to Transcript.</td><td>OK</td></tr><tr><td>Queue sends Customer to the first available Teller.</td><td>OK</td></tr><tr><td>Teller tells BankSimulation that it received a Customer.</td><td>OK</td></tr><tr><td>BankSimulation outputs the event to Transcript.</td><td>OK</td></tr><tr><td>CustomerProducer generates another Customer with random processing time and assigns it a random waiting time (customer 'waits in front of the bank'). It will now wait to release the customer to Queue.</td><td>How?</td></tr><tr><td rowspan="5">Body</td><td>SimulationManager increments time and checks for end of simulation. If not end, it informs CustomerProducer, Queue, and Teller about time change.</td><td>OK</td></tr><tr><td>CustomerProducer checks whether to release a Customer. If so, it sends Customer to Queue which updates and notifies BankSimulation. BankSimulation outputs the event to Transcript. CustomerProducer creates new Customer and inter-arrival (waiting) time.</td><td>OK</td></tr><tr><td>Each Teller checks whether to release its Customer. If so, it releases Customer and notifies BankSimulation which outputs the event to Transcript.</td><td>OK</td></tr><tr><td>Queue checks whether it has a waiting Customer. If so, it checks whether a Teller is available.</td><td>OK</td></tr></tbody></table>
<table><tr><td></td><td>If so, it sends Customer to the first available Teller, Teller calculates time to release this Customer, notifies BankSimulation of arrival, BankSimulation outputs the event to Transcript. Repeated until either no more customers in queue or all tellers busy.</td><td></td></tr><tr><td>End of simulation</td><td>SimulationManager calculates average wait time and sends this information and total number of customers to BankSimulation.</td><td>OK</td></tr><tr><td></td><td>BankSimulation outputs the result to Transcript.</td><td>OK</td></tr></table>

Our conclusions from this analysis are as follows:

* We need a new class to generate random numbers uniformly distributed between two positive integers (we will call this class `RandomInteger`).

* We have reassigned the responsibility for reporting events and results to the objects that are involved in the events. This has the following consequences:

* Queue needs to know about BankSimulation so that it can communicate results.

* Teller needs to know about BankSimulation so that it can communicate results.

* Since Queue is created by SimulationManager, SimulationManager must know about BankSimulation.

The last point is worth closer examination. In our problem, we have two choices to implement the generation of the report. One is to have BankSimulation poll all objects that have something to report, the other is to leave it to the components to notify BankSimulation (Figure 11.9). The first solution has several disadvantages: One is that whenever we change the simulation by adding new types of objects, we must modify the corresponding part of BankSimulation. Another disadvantage is that as the number of objects that have something to report gets larger, the complexity of methods in BankSimulation that perform the gathering of reports also increases. Eventually, BankSimulation will become much too large and its role in the application too predominant. Finally, polling is based on the assumption that the polled object may or may not have something to report. If it does not, polling wastes time. The second approach - leaving the responsibility to report an event to the object that experienced the event (event-driven design) can be more efficient. We selected the event-driven approach and leave the polling approach as an exercise.

<figure><img src="image_210.png" /><figcaption>Figure 11.9. Centralized control (left) results in unbalanced distribution of intelligence. Distributed intelligence (right) is generally preferred. The ‘intelligence’ of an object is indicated by the thickness of the line around it.</figcaption></figure>

## Final design

We are now ready to write detailed descriptions of all required classes. We will use the term reporter to refer to the BankSimulation object because it is responsible for reporting results:
**BankSimulation**: In charge of user interface - input of parameters, start of simulation, output of results.

**Attributes**: simulationManager, simulation parameters (number of tellers, minimum and maximum customer processing and arrival times), other aspect variables.

**Responsibilities and collaborators**:

* Output - implemented by

* displayEvent: aString. Writes aString to Transcript followed by cr.

* User interface action buttons

* run - starts simulation

* close - close application

* help - display help window

**Customer**: Represents customer with timing information.

**Attributes**: processingTime (time to spend at teller station), timeToQueue (time at which Customer entered Queue - for calculation of time spent in bank).

**Responsibilities and collaborators**:

* Creation - implemented by

* newWithProcessingTime: anInteger. Creates new Customer. Collaborates with Customer.

**CustomerProducer**: Generates Customer objects with random values of processing time, keeps information about inter-arrival time and uses it to send Customer to Queue when the time expires and produces another Customer.

**Attributes**: customer (customer waiting to be released to the queue), releaseTime (when to release current Customer), gapGenerator (random number generator calculating inter-arrival times), processingGenerator (random number generator calculating Customer processing times).

**Responsibilities and collaborators**:

* Creation - implemented by

* newWithGapGenerator: aRandomInteger withGapGenerator: gapGenerator withProcessingGenerator: processingGenerator. Collaborates with RandomInteger.

* Updating - implemented by

* updateTime. Updates time, sends Customer to Queue and creates a new one if appropriate. Collaborates with Queue.

**Queue**: Knows its customers, can accept new Customer objects, knows how to check whether a Teller is available, knows how to send a Customer to a Teller. Calculates queue statistics and notifies BankSimulation when a customer is added.

**Attributes**: customers, reporter (reference to BankSimulation), tellers, time (fictitious simulation time)

**Responsibilities and collaborators**:

* Creation - implemented by

* numberOfTellers: anInteger reporter: aBankSimulation. Also creates the required number of Teller objects. Collaborates with Teller.

* Processing - implemented by

* updateTime. Checks whether it has Customer; if so, checks if there is an available Teller; if so, sends Customer to it. Repeated until Queue is empty or no more tellers available. Collaborates with RandomInteger, Teller.

* addCustomer: aCustomer. Add Customer at end of queue and report it to BankSimulator. Collaborates with BankSimulator.

**RandomInteger**: Generates random integer numbers within prescribed range.

**Attributes**: randomGenerator (reference to Random), lowerLimit, upperLimit

**Responsibilities and collaborators**:

* Creation - implemented by
* lowerLimit: anInteger upperLimit: anInteger.

* Accessing - implemented by

* next. Returns random integer.

**SimulationManager:** Starts, runs, and ends simulation. Collects results at the end and notifies BankSimulation. Issues timing information to CustomerProducer, Queue, and Teller objects.

**Attributes:** customer, lengthOfSimulation, producer, queue, reporter, totalCustomers (total number of customers sent to Queue), totalTimeInBank (sum of times spent in bank by all customers), simulation parameters.

**Responsibilities and collaborators:**

* Creation - implemented by

* tellers: anInteger reporter: aBankSimulator simulationLength: anInteger, minProcessing: anInteger maxProcessing: anInteger minArrival: anInteger maxArrival: anInteger. Collaborates with Queue.

* Simulation - implemented by

* run. Starts time, creates CustomerProducer, creates Queue, creates one object and puts it in Queue, asks CustomerProducer to produce another Customer and hold it until release. Repeats time update notifying Queue and CustomerProducer, moving Customer to queue when released by CustomerProducer. Tells reporter about number of processed customers and average time in bank. Collaborates with Queue, CustomerProducer.

**Teller:** Knows how to accept and process a customer, knows whether it has a Customer. Notifies BankSimulation when a Customer arrives or is released.

**Attributes:** customer, customerReleaseTime, reporter, time, number (number of teller used in reporting).

**Responsibilities and collaborators:**

* Creation - implemented by

* number: anInteger reporter: aBankSimulation.

* Updating - implemented by

* addCustomer: aCustomer. Adds Customer and calculates release time. Collaborates with Customer.

* updateTime. Checks whether to release Customer, reports when Customer released. Collaborates with BankSimulator.

## Implementation

The implementation is simple and we will limit ourselves to a few methods. The rest is left as an exercise.

## Output of customer transfers to the Transcript

A typical simulation will run for many units of time and generate a lot of output to the Transcript if the *Show steps* check box is on. This can be relatively time consuming because individual *show* messages consume long time. In cases like these, it is better to accumulate the output in the Transcript object (a *TextCollector*) using `nextPut: aCharacter` and `nextPutAll: aString` messages, and flush all accumulated output at the end. We will illustrate this technique on the example of customer dispatch to tellers by Queue.

When Queue contains customers and there is an available teller, it sends a customer using the following message. As a part of this message it informs reporter, the active BankSimulation object:

### customer: aCustomer

"A customer has arrived.

customer := aCustomer.

customerReleaseTime := customer processingTime + time.

reporter displayEvent: 'Time: ', time printString, '. Teller ', number printString, '
new customer with processing time ', customer processingTime printString
steps: true

The message to reporter uses method displayEvent: aString steps: aBoolean as general purpose event notification message. The method is defined in BankSimulation as follows:

**displayEvent: aString steps: aBoolean**

"Send aString to Transcript unless this is one of the detailed steps and display of steps is not desired."

(showSteps value or: [aBoolean not])

ifTrue: [Transcript nextPut: Character cr; nextPutAll: aString]

Since the message to Transcript is not show:, the event notification string is not displayed at this point but only stored for future input in Transcript. At the end of simulation, the SimulationManager sends message flush to BankSimulation which then sends the flush message to the Transcript. This causes all accumulated output to be output in Transcript in one chunk, a much more efficient operation than a sequence of show: messages.

**Main lessons learned:**

* A queue is a first-in first-out structure (FIFO). Elements are added at one end (tail) and removed from the other end (head).

* Queue behavior is subsumed by OrderedCollection and there is no need for class Queue.

**Exercises**

1. Implement class Queue with only the essential stack behavior.

2. Implement bank simulation as described.

3. Reimplement bank simulation using polling instead of event-driven design.

4. Modify bank simulation by adding output to file.

5. Repeat our simulation using Poisson's distribution for all random events in the simulation. This distribution is based on the assumption that there is no limit on inter-arrival time.

6. Implement cash register simulation where customers line up in front of individual registers.

7. Explain why queues are also called First-In-First-Out (or FIFO) objects while stacks are called First-In-Last-Out objects.

## 11.5 Text filter - a new implementation

In this section, we will show how the text filter from the previous chapter can be implemented in a more sophisticated way using a queue.

**Problem:** The behavior of our previous solution was unsatisfactory and we will thus try to find a better specification and a better solution. Let's try this: Class TextFilter takes an original String object and replaces occurrences of match substrings with corresponding replacement substrings, compressing the original as much as possible.

**Scenario 1:** Filtering 'abcdeab' using match/replacement pairs pair1 = 'ab'->'xx', pair2 = 'eab'->'yy'

Assume original string = 'abcdeab' and match/replacement pairs pair1 = 'ab'->'xx', pair2 = 'eab'->'yy'. This is the scenario that failed in our previous implementation. We will now show how the scenario is executed assuming that we keep track of the current position in the original and in each match string via a position counter, and that the resulting string is held in result.

1. Initialize result to empty string; initialize position counters to 1.

2. Compare position 1 in pair1 ($a$) with first character of string; match found, increment pair1 pointer.

3. Compare position 1 in pair2 ($e$) with first character of string key; no match.
4. No complete match, copy character from string to result, increment position in string and result.

5. Compare position 2 in pair1 ($b$) with first character of string - match.

6. Compare position 1 in pair2 ($a$) with first character of string key; no match.

7. We have a complete match. Select the longest replacement possible, changing result to 'xx'.

8. Continue in this way until the last character in string. At this point, there are two matches and two possible replacements. The longer one is selected giving result = 'xxcdyy' as expected.

This scenario works as expected. But wait - the behavior in the following scenario does not quite meet our expectations.

**Scenario 2: Filtering string = 'abcd' with match/replacement pairs**

```
pair1 = 'bc'->'xx', pair2 = 'abcd'->'yy'
Assume string = 'abcd' and match/replacement pairs
pair1 = 'bc'->'xx', pair2 = 'abcd'->'yy'. We would
assume to obtain the most compressed result = 'yy' but our position counter-based implementation will
produce 'axxcd' (left as an exercise).
```

The reason for the unsatisfactory behavior is that 'bc' is finished matching before 'abcd', and 'abcd' thus never gets a chance to complete matching and be replaced. We thus need a new approach and the best place to start is to analyze why our current approach fails. Our approach does not work because as soon as a substring is matched, it is immediately replaced. However, we cannot make a replacement unless we know that there is no matching in progress that started earlier than the matching that just succeeded, and that is not yet finished.

To deal with this situation, we will use a *queue* of all matching processes in progress such that the matching or matchings that started first are at the head of the queue. The idea is as follows: Match the original character by character. For each character, put all (match string -> replacement string) associations that succeed in matching their first character into a collection and add the collection to the end of the queue. (The queue thus consists of collection objects.) When an association fails to match, remove it from the queue. When a complete match occurs, check whether the matching association is in the collection at the head of the queue. If it is, there is no earlier matching in progress and we can thus safely make the replacement in result. At this point, we will empty the whole queue and start a new matching sequence. If the matching association is not in the collection at the head of the queue, mark it as ready for replacement and proceed; don't do any replacement yet - wait until the association reaches the beginning of the queue. When it does, use it to make the appropriate replacement.

Before we formulate the algorithm more carefully, we will take a look at the objects needed to support it. In addition to streams and position counters to keep track of the original string and the result, we also need

* A queue whose elements are collections of partially matched associations. We will call it `MatchesInWaiting` and implement it as a class variable.

* A collection of all associations that are fully matched and ready for replacement. This will be a class variable called `ReadyForReplacement`.

With this background, we can fully describe the matching procedure as follows:

1. Create a `ReadStream` over the original string and a `WriteStream` over the string being constructed.
Create an empty `MatchesInWaiting` queue.

Create a `MatchDictionary` and initialize it to `match string -> two-element array` associations; each association has a match string for key. The first element of its value array is the replacement string, the second element of the array is the position counter initialized to 0.

2. Repeat for each position of the input stream beginning from the start:

a. Add a new collection to the end of the `MatchesInWaiting` queue.

b. For each element of the dictionary do:

Increment position counter of this dictionary item.
Compare original character and match character.

If no match, reset current position counter of dictionary item to 0. If this item is in MatchesInWaiting, remove it.

If match, check if this is match on first character of match string.

If so,
add this association to the collection at the end of the MatchesInWaiting queue.

Check if this is the last character to match.

If so (match succeeded), check if ReadyReplacement is empty.

If so, store this association in ReadyReplacement.

If this is not the last character (match incomplete), increment position counter of this association.

c. If ReadyReplacement contains an association and if this association is at the head of the queue, use the association to make a replacement in OutputStream.

Empty MatchesInWaiting queue, reset ReadyReplacement and ReplacementPosition to nil.

We leave it to you to check whether this algorithm works, correct it if it does not, and implement it.

Exercises

1. Complete the design of the text filter and implement and test it.

2. Our algorithm will work if all the replacement strings are equally long. But what if they are not?

3. Extend the filter to allow replacement calculated by blocks.

4. Our various formulations of the string replacement problem were not incorrect but merely different. Are there any other possible formulations of the string replacement problem? If so, outline the appropriate solutions.

5. Since there are several possible formulations of text filtering that each require a different solution, the problem seems amenable to an abstract class with concrete subclasses implementing different specifications. Design such a hierarchy and comment on the advantages of this approach - if any.

11.5 Linked Lists

None of the sequenceable collections covered so far are specifically designed for insertion of new elements at arbitrary locations. Arrays allow replacement but not insertion, and ordered collections allow insertion but the internal operation is complex and inefficient.

A linked list is a collection of objects linked to one another like a string of pearls. As a minimum, a linked list knows about its first element, and each element knows about its successor. A doubly linked list is an extension of a singly linked list whose elements also know about their predecessor (Figure 11.10). Both provide a way to insert a new element at any location. Another advantage of linked lists is that they occupy only a small amount of space required to hold their elements whereas ordered collections may occupy more space because they are normally only partially filled. However, elements of linked lists (their nodes) must be packaged in more complex objects.

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

<figure><img src="image_212.png" /></figure>
<figure><img src="image_213.png" /><figcaption>Figure 11.10. Linked list (top), doubly linked list (bottom). List elements are shaded.</figcaption></figure>

As our illustration shows, the implementation of linked lists requires two kinds of objects - list elements and a linked list object itself. A minimal linked list must know at least about its first node. In the Smalltalk library, linked lists are implemented by class `LinkedList` with the following comment:

The class `LinkedList` implements ordered collections using a chain of elements. Each element of a `LinkedList` must be an instance of class `Link` or of one of its subclasses.

A new instance of `LinkedList` can be initialized using

`LinkedList` with: Link new

Instance Variables:

<table><tr><td>firstLink</td><td>&lt;Link&gt;</td></tr><tr><td>lastLink</td><td>&lt;Link&gt;</td></tr></table>

Class `LinkedList` is a subclass of `SequenceableCollection` and inherits its protocol including creation, enumeration, and access by index (normally unused), and redefines many of them.

Class `Link` whose instances are nodes of `LinkedList` is very primitive and implements only linking with no provision to hold a value. Its comment is

Class `Link` represents a simple record of a pointer to another `Link`.

Instance Variables:

<table><tr><td>nextLink</td><td>&lt;Link&gt; a pointer referencing the next Link in the chain</td></tr></table>

Link protocol includes `nextLink` (returns the next node in a linked list), `nextLink`: a `Link` (sets `nextLink` to specified `Link` object), and the creation message `nextLink`: that initializes the successor of the receiver. Being so primitive, `Link` is only used as a superclass of classes that attach a value to the link object, thus allowing the creation of `LinkedList` objects with non-trivial elements as in Figure 11.10.

Linked lists are simple but useful objects and we will illustrate their use on the following example:

### Example. Reimplement sorted collections using linked lists

**Problem:** Use a linked list to implement class `SortedLinkedList` with the functionality of `SortedCollection`. Restrict the definition to creation and adding.

**Solution:** Being an extension of `LinkedList`, `SortedLinkedList` will be a subclass of `LinkedList` with a new instance variable called `sortBlock`. The nature of the sort block will be the same as that of `SortedCollection` and there will also be a default sort block stored in a class variable `DefaultSortBlock`. Its value will be `[:x:y | x <= y]` so that a `SortedLinkedList` with the default block will have its elements sorted in the order of ascending magnitude of its elements. The new message will create a `SortedLinkedList` with the default sort block, and an instance with a different sort block can be created by the class method `sortBlock`: `aSortBlock`.

The definition of the class is
```
-linkedList subclass: #SortedLinkedList
    instanceVariableNames: 'sortBlock'
    classVariableNames: 'DefaultSortBlock'
    poolDictionaries:"
    category: 'Book'
```

The value of the default sort block will be assigned by the same *class* initialization method as in
`SortedCollection`:

initialize
"Create a default sort block"
DefaultSortBlock := [:x:y | x <= y]

Don't forget to execute the initialization method with

SortedLinkedList initialize

before using `SortedLinkedList` for the first time. We suggest using `inspect` to see the effect.
Next, the creation method. The method creates a new instance and then initializes the sort block by

new
^super new initialize

where the `instance` method `initialize` is again the same as in `SortedCollection`:

initialize
"Set the initial value of the receiver's sorting algorithm to a default."
sortBlock := DefaultSortBlock

When we test the code developed so far with

SortedLinkedList new

we get the expected result – try it with `inspect`.

Before we can implement adding, we must be able to create node objects. Since the nodes in our list have a value, they cannot be simple `Link` objects. We will thus create a new class called `LinkNode` with instance variable `value`, extending `Link` with creation method `nodeValue: anObject`, and accessing methods `value` and `value: anObject`. We will leave these methods as an exercise and limit ourselves to comparison by `<=` which is required by the sort block:

<= aNode
"Compare the value of the receiver and the value of the argument."
^self value <= aNode value

We suggest that you test that `LinkNode` methods work.

Now that we have a class to implement nodes, we can return to `SortedLinkedList`. We will limit ourselves to method `add: anObject` for adding a new object to a linked list and leave other functionality as an exercise. The `add:` message will be based on careful consideration of all possible situations expressed in the following algorithm:

1. If the list is empty, add the new node using the inherited `add:` message and exit.

2. If the list is not empty, search it from the beginning looking for a node that returns `false` when compared with the new node using the sort block.

a. If such a node is found, insert the new node before this element and exit.
b. If such a node is not found, add the new node at the end of the list

We will now examine Step 2 in more detail. Each evaluation of the sort block has two possible outcomes: If the block returns true, we must continue the search and proceed to the next node. If the block returns false, the current node is either at the beginning of the linked list or inside it (Figure 11.11). If the current node is the first node in the list, the new node must be inserted in front of it using the inherited addFirst: message. If the current node is not the first node, the new node must become the nextLink of the previous node, and its own nextLink must point to the 'current' node. This means that the method must keep track of the previous node.

<figure><img src="image_214.png" /><figcaption>Figure 11.11. When the list is not empty, the new node will be inserted either at the start of the list (top), or into the list (bottom), or behind the last element (not shown).</figcaption></figure>

With this background, the definition of add: can be written as follows:

### add: anObject

"Add anObject to the list at position determined by sortBlock. Return anObject."

| current newNode previous |

"Create a node link with value anObject."

newNode := LinkNode nodeValue: anObject.

"If the list is empty, simply put the node at the start of the list."

self isEmpty ifTrue: [super add: newNode. ^anObject].

"List is not empty, traverse it from the start."

current := self first.

[current isNil] "End of list?"

whileFalse: [

(sortBlock value: current value: newNode) "Is new node behind current node?"

ifTrue: "Sort block succeeded, go to next list node."

[previous := current.

current := current nextLink]

ifFalse: "Sort block failed, distinguish two possibilities."

[current == firstLink

ifTrue: "Insert new node at the start of the list."

[newNode nextLink: firstLink.

self addFirst: newNode]
```
ifFalse: "Insert between previous and current."
        [previous nextLink: newNode.
         newNode nextLink: current].
```

### ^anObject]]

"Node does not fit inside the linked list, add it at the end."

self addLast: newNode.

previous nextLink: newNode.

### ^anObject

We are now ready for testing. We cannot test every possible situation but we must try to test every logical possibility. We will test add: in the following situations:

1. List is empty.

2. List is not empty and the new node becomes the first node in the list.

3. List is not empty and the new node is inserted between two existing nodes.

4. List is not empty and the new node is added at the end of the list

An example of a test program that checks all these alternatives is

```
| sll |
Transcript clear.
sll := SortedLinkedList new.
Transcript show: sll printString; cr.
sll add: 3.
Transcript show: sll printString; cr.
sll add: 33.
Transcript show: sll printString; cr.
sll add: 13.
Transcript show: sll printString; cr.
sll add: 0.
Transcript show: sll printString
```

Before we can execute this program, we must make sure that printString creates meaningful SortedLinkedList descriptions. Since SortedLinkedList is a subclass of Collection, we reuse the printing protocol in Collection which depends on do:. We must thus define do: as follows:

### do: aBlock

"Evaluate aBlock with each of the receiver's elements as the argument."

current := firstLink.

"Initialize for traversal."

[current isNil]

"Iterate up to and including the last node."

whileFalse:

[aBlock value: current.

current := current nextLink].

"Get the next node, if any."

With this method, printing works but does not produce any meaningful information about nodes. We define node printing as

### printOn: aStream

"Append to the argument, aStream, the elements of the Array enclosed by parentheses."

aStream nextPutAll: self class name; nextPutAll: ''; nextPutAll: self value printString

and with this, our test program produces the following correct output which confirms that our definitions work as expected:

```
SortedLinkedList ()
SortedLinkedList (LinkNode 3)
SortedLinkedList (LinkNode 3 LinkNode 33)
```
SortedLinkedList (LinkNode 3 LinkNode 13 LinkNode 33)
SortedLinkedList (LinkNode 0 LinkNode 3 LinkNode 13 LinkNode 33)

Finally, we must test that SortedLinkedList works even with non-default sort blocks and we thus define a new SortedLinkedList creation method called sortBlock: and modify our test program to create a new list with the same elements sorted in *descending* order:

| sll |
Transcript clear.
sll := SortedLinkedList sortBlock: [[:x :y | x > y].
Transcript show: sll printString; cr.
sll add: 3.
Transcript show: sll printString; cr.
sll add: 33.
Transcript show: sll printString; cr.
sll add: 13.
Transcript show: sll printString; cr.
sll add: 0.
Transcript show: sll printString

The test produces

SortedLinkedList ()
SortedLinkedList (LinkNode LinkNode 3)
SortedLinkedList (LinkNode LinkNode 33 LinkNode LinkNode 3)
SortedLinkedList (LinkNode LinkNode 33 LinkNode LinkNode 13 LinkNode LinkNode 3)
SortedLinkedList (LinkNode LinkNode 33 LinkNode LinkNode 13 LinkNode LinkNode 3 LinkNode LinkNode 0)

in the Transcript and again confirms the correctness of our implementation.

## Main lessons learned:

* A linked list is a linear collection of nodes with a pointer to its first element and links between consecutive nodes.

* In addition to forward links, linked nodes can also have backward links. Such lists are called doubly linked lists.

* A linked list allows insertion of elements at any point in the list.

* Smalltalk library contains a pair of general classes called **LinkedIn** and **Link** implementing the basic linked list behavior. For concrete use, these classes must be subclassed.

## Exercises

1. Complete the implementation of the example from this section and add node removal.

2. Find how an element can be inserted into an OrderedCollection.

3. Test which implementation of sorted collection is faster using the Speed Profiler included in the Advanced Tools of VisualWorks. Justify the result.

4. Compare the memory requirements of the two implementations of sorted collection using the Allocation Profiler included in the Advanced Tools of VisualWorks.

5. Add node removal to sorted linked list.

6. Add method asArray returning an Array containing the values of all elements of the list in the order in which they are stored.

7. Implement a doubly linked list.
11.6 Trees

A tree is a two-dimensional collection of objects called nodes. Three examples are a class hierarchy tree, a family tree, and a tree of student records as in Figure 11.12. The nodes of a tree can be classified as follows:

* The node at the top of the tree is called the *root*. This is the node through which the tree can be accessed. The node with ID 27 in our example is the root of the tree. A tree has exactly one root.

* A node that is not a root and has at least one child is an *internal node*. The records with IDs 13 and 32 in our example are internal nodes. Every internal node has exactly one parent node but it may have any number of children, unless the definition of the tree specifies otherwise.

* A node that does not have any children is called a *leaf*. The node with ID 11 in our example is a leaf node. Like an internal node, a leaf has exactly one parent node.

An interesting and useful property of trees is that any node in the tree can be treated as the root of a new tree consisting of all the underlying nodes. Such a tree is called a *subtree* of the original tree. As an example, the node with ID 32 in Figure 11.12 can be used as the root of a tree with children 29 and 45. Leaves, such as 29, can be thought of as degenerate trees that consist of a root and nothing else.

Trees are very important in computer applications and a variety of trees have been devised to provide the best possible performance for different uses. The differences between different kinds of trees are in the number of children that a node may have<fnref n="4" />, and the way in which the tree is managed (how nodes are added and deleted). The subject of trees is not trivial and we will restrict our presentation to the example of a simple binary tree. In a binary tree, each node may have at most two children as in Figure 11.12.

<figure><img src="image_215.png" /><figcaption>Figure 11.12. Binary tree of student records based on comparison of student IDs.</figcaption></figure>

*Problem:* Implement a binary tree whose nodes are arranged on the basis of comparison of node values. The tree must be capable of adding a new object, deleting an existing node, and finding whether an object with a given value is in the tree. Provide enumeration and printing as well.

*Solution:* Our implementation will use two kinds of objects - nodes (class Node), and the tree itself (class BinaryTree). The BinaryTree object must know about its root and how to perform comparison (comparison block), the Node object must know its value and its children; knowing the parent may also be useful. We will start with Node because we cannot create BinaryTree without nodes. The comment of Node is as follows:

Class Node implements nodes for class BinaryTree. Each node consists of

<footnote n="4">⁴ Each node with the exception of the root always has exactly one parent.</footnote>
<table><tr><td>value</td><td>&lt;Object&gt;</td><td>- value of node, must understand the tree's comparison block</td></tr><tr><td>leftChild</td><td>&lt;Node|nil&gt;</td><td>- root of left sub-tree of this node, a Node or nil</td></tr><tr><td>rightChild</td><td>&lt;Node|nil&gt;</td><td>- root of right sub-tree of this node, a Node or nil</td></tr><tr><td>parent</td><td>&lt;Node|nil&gt;</td><td>- parent of this node, a Node or nil</td></tr></table>

The superclass of Node will be Object and we will start its implementation with a class method to create a Node with its value. The method is styled in the usual way:

**newWithObject: anObject**

```
^self new value: anObject
```

and instance method value: sets value to anObject. We leave the remaining instance variables uninitialized which is as it should be because they will be assigned as new objects are added to the tree. The methods to add children and the parent are equally simple but we must remember that when a node is added as a child, the receiver node must become the child's parent as in

**rightChild: aNode**

```
rightChild := aNode.
```

```
aNode parent: self
```

After defining all accessing methods, we can now test our design by executing the following code with *inspect*:

```
[parentNode node nodeOnLeft nodeOnRight]
parentNode:= Node newWithObject: 'parent node'.
node := Node newWithObject: 'this node'.
nodeOnLeft := Node newWithObject: 'left sub-node'.
nodeOnRight := Node newWithObject: 'right sub-node'.
node parent: parentNode.
node leftChild: nodeOnLeft.
node rightChild: nodeOnRight.
node
```

We find that everything is OK.

Now that we have a working Node, we can start working on class *BinaryTree*. Each instance of *BinaryTree* needs to know the tree's root node and its comparison block which is used to decide whether a new node should be inserted in the left subtree or the right subtree. We will call these two instance variables *root* and *isLeftBlock* and comment the class as follows:

Class *BinaryTree* implements a binary tree. Nodes are added as leaves on the basis of a comparison block applied to the value of the new object and values of existing nodes.

Instance variables

<table><tr><td>root</td><td>&lt;Node|nil&gt;</td><td>- root node of the tree, a Node or nil.</td></tr><tr><td>isLeftBlock</td><td>&lt;BlockClosure&gt;</td><td>- a two-argument block used to determine whether a new node should be added to the left of an existing node. The first argument of the block is the new node, the second argument is an existing node to which the new node is being compared. When the block returns true, the new node is attached as the left subnode; on false, the new node is attached on the right.</td></tr></table>

The superclass of *BinaryTree* is *Object*. The *creation* method will specify the root of the tree and the comparison block. It will be used as in

```
BinaryTree withRoot: 13 withBlock: [:new :old| new < old]
```
The creation method is as follows:

**withRoot: anObject withBlock: comparisonBlock**

```self new root: (Node newWithObject: anObject) block: comparisonBlock```

where instance method `root:block:` initializes root and `isLeftBlock`. Implement these two methods and test everything by executing the above expression with *inspect*.

Now that we can create a tree with a root and a comparison block, we need a method to add an object to an existing tree. To add a new object, we start from the root and proceed downwards using the following principle: If the value of the new object satisfies the comparison block with the value of the current node, proceed to the left child, if any; otherwise proceed right. Upon reaching a node whose desired child is `nil`, further traversal is impossible; add the new object as a new leaf on the left or on the right on the basis of comparison of comparison.

Since adding works the same way for the root and for sub-nodes, the `add:` method can take any node as its argument and treat it as the root of a tree and re-send itself with this node as the root. A more accurate description of the algorithm is as follows:

1. If the tree is empty, make the new object the root of the tree and exit.

2. If the tree is not empty, proceed as follows:

a. If the root and the new object satisfy the sort block, send `add:` to its left subtree.

b. If evaluation of the sort block returns `false`, send `add:` to the right subtree.

You can check that the tree in Figure 11.12 is the result of this algorithm with nodes added in the following order of IDs: 27, 13, 8, 32, 29, 11, 45. Our description is easily translated into the following code:

**add: newNode toNode: existingNode**

```text
"Attach newNode as leaf of the appropriate subtree of existingNode."
existingNode isNil ifTrue: [root := newNode. ^newNode].
(isLeftBlock value: newNode value value: existingNode value)
ifTrue: [ "Add newNode to left sub-tree."
existingNode leftChild isNil
    ifTrue: "Attach aNode as leftChild."
           [existingNode addLeftChild: newNode]
    ifFalse: "Apply this method recursively."
           [self add: newNode toNode: existingNode leftChild]]
ifFalse: "Add newNode to right sub-tree."
[existingNode rightChild isNil
    ifTrue: "Attach aNode as rightChild."
           [existingNode addRightChild: newNode]
    ifFalse: "Apply this method recursively."
           [self add: newNode toNode: existingNode rightChild]].
^newNode
```

Note that we used `value:` `value:` to evaluate the comparison block because the block has two arguments.

This method can be used to add a node once we have a node to start from. First, however, we must get into the tree and get the starting node – the root. To do this, we will use the following method:

**add: anObject**

```text
"Add node with anObject as a new leaf of the tree."
self add: (Node newWithObject: anObject) toNode: root
```

We can now test our solution with the following program which should create the tree in Figure 11.13:
```
|tree |
tree := BinaryTree withRoot: 15 withBlock: [:new :old| new value < old value].
tree add: 8;
    add: 21;
    add: 14;
    add: 36;
    add: 17;
    add: 49;
    add: 32;
yourself
```

Execute the program with *inspect* and check that the resulting *BinaryTree* is correct. Note that once you open the tree inspector, you can use it to traverse the whole tree by selecting first the root and then inspecting its children, proceeding recursively in this way as far as you wish.

<figure><img src="image_216.png" /><figcaption>Figure 11.13. Binary tree created with the program in the text.</figcaption></figure>

Unfortunately, our `add:` method ignores the possibility that the root is `nil` which will happen if we deleted all nodes. This can be corrected as follows:

```Smalltalk
add: anObject
"Attach node with anObject as a new leaf of the tree."
| newNode |
newNode := Node newWithObject: anObject.
root isNil
    ifTrue: [root := newNode]
    ifFalse: [self add: newNode toNode: root]
```

The next protocol is finding. The `find:` `anObject` method will return the node whose value is `anObject`, or `nil` if such a node is not in the tree. We leave it as an exercise and suggest that you implement it via two methods as we did for adding.

To *delete* a node with a specified value, we must find the node, remove it from the tree, and rearrange the tree so that new node ordering still satisfies the sort block. The new tree may not look like the original tree but the relation between a node and its children must satisfy the comparison block.

The easiest (but not the most efficient) way to implement this specification is to remove the node and then add all its children and the remaining nodes to its parent using the `add` operation. By definition, this will preserve proper ordering. A detailed description of the deletion algorithm is as follows:

1. Find node *node* whose value is *anObject*. If there is no such node, execute an exception block and exit.

2. If *node* is root, then

a. If its left child is `nil` then

i. Replace root with left child.

ii. Replace new root's parent with `nil` to cut the link to the removed root.

b. Else (the left child is not `nil`)
i) Add root's right child to the root's left child.

ii) Make left child the new root.

iii) Replace new root's parent with nil to cut the link to the removed root.

3. If node is not root then

a. Remove connection from node's parent to node.

b. Add the left child of node to the parent – this adds all left subnodes because it leaves the child's subtrees unchanged.

c. Add the right child of node to the parent– this adds all right subnodes because it leaves the child's subtrees unchanged.

This algorithm can be used to define delete as follows:

**remove: anObject ifAbsent: aBlock**

"Delete anObject from the tree and return anObject; evaluate aBlock if not present."

| parent theNode |

theNode := self find: anObject.

theNode isNil ifTrue: [^aBlock value].

parent := theNode parent.

parent isNil

ifTrue: ["theNode must be the root."

root leftChild isNil

ifTrue: [root := root rightChild]

ifFalse: [self add: root rightChild toNode: root leftChild.

root := root leftChild].

root parent: nil]

ifFalse: [parent leftChild = theNode

ifTrue: [self removeLeftChild]

ifFalse: [self removeRightChild].

self add: theNode leftChild toNode: parent.

self add: theNode rightChild toNode: parent].

^anObject

where removeLeftChild and removeRightChild simply replace the child with nil. Finally, *enumeration* can be
implemented by a combination of two methods:

**do: aBlock**

"Evaluate aBlock for each node of the tree rooted at the root."

self do: aBlock startingFrom: root

and

**do: aBlock startingFrom: aNode**

"Evaluate aBlock for each node of the tree rooted at aNode."

aNode isNil

ifFalse: [aBlock value: aNode.

self do: aBlock startingFrom: aNode leftChild.

self do: aBlock startingFrom: aNode rightChild]

This very concise method is a typical example of the advantage of using recursion to implement a
non-trivial operation on a complicated collection. The method can be tested, for example, by

| tree |

tree := BinaryTree withRoot: 15 withBlock: [:new :old| new value < old value].

tree add: 8;

add: 21;

add: 14;

add: 36;
add: 17;

add: 49;

add: 32;

do: [:node | Transcript show: node value printString; cr]

which produces

8

14

21

17

36

32

49

## Main lessons learned:

* A tree is a branching structure of nodes and their children emanating from one node called the root.

* Nodes at the bottom of the tree (nodes with no children) are called leaves.

* Every node in a tree except the root has exactly one parent node. The root does not have a parent.

* Specialized trees may restrict the number of children of a node or the structure of the tree.

## Exercises

1. List two different number sequences that will produce the tree in Figure 11.13.

2. Complete and test `BinaryTree`.

3. How could we improve our design of `BinaryTree`? One weakness of our approach is that when we traverse the tree, we check each node to determine whether it is empty or not because an empty node requires different treatment. This overhead is unnecessary if we use polymorphism and implement `BinaryTree` as an abstract class with two subclasses – one for an empty binary tree and one for a non-empty tree. Implement this idea (borrowed from [Pugh, Lalonde]) and compare the efficiency of the two approaches.

4. Add the following methods to the implementation of binary tree:

a. A method to merge two trees together.

b. A method to check whether a tree contains another tree as its subtree.

c. A method to copy nodes from one tree to another tree.

5. Assume that in addition to binary trees, we also want to implement trees with up to three children, and trees with up to four children. Both trees use some further unspecified construction rules. Is it desirable to define an abstract superclass? If so describe its properties in detail. What other classes must be defined?

6. Explain in what order the `do:startingFrom:` method traverses the nodes of the tree. Can you describe other traversals? Implement them.

7. Add a method to find the depth of the tree - the maximum number of nodes encountered during the traversal from the root to a leaf.

8. Consider $n = 255$ objects sorted according to their value. What is the maximum number of steps required to find a given object if the objects are stored in a sorted collection? What is the answer if the objects are stored in a balanced tree whose branches have, as much as possible, equal depth? What is the answer for a general value of $n$?

9. A two-dimensional array can be implemented with a tree as in Figure 11.14. Describe how this principle could be used to implement an n-dimensional array.

<figure><img src="image_217.png" /></figure>
<figure><img src="image_218.png" /></figure>

leaf – an array with three elements

<caption>Figure 11.14. Representing a two-dimensional 4x3 matrix by a two-level tree. Leaves represent rows.</caption>

## 11.7 Use of trees in compilation

One of the most important uses of trees is in compilation. When you compile a method with *accept*, the following sequence of events occurs:

1. A message is sent to the Compiler object with the source code as one of its arguments.

2. The compiler sends a message to the Parser object to find the structure of the method.

3. The parser sends a message to the *lexical analyzer* which converts the source code string into *tokens* - symbols representing higher level language entities such as literal numbers or strings, and unary or binary selectors.

4. The parser uses the tokens and the definition of Smalltalk syntax to construct the *parse tree* representing the source code.

5. The *code generator*, reads the parse tree, and produces the translation - an instance of *CompiledMethod*.

The process is, of course, interrupted if the code contains illegal source code. We will now illustrate the operation on an example. Assume that you entered the following method in class Test using the *Browser* and clicked *accept*.

### test

"A test to illustrate compilation."

3 + 3.

5 factorial

If you trace the execution of the ensuing compilation by inserting a breakpoint in front of the statement in Step 1 (below), you will find that the steps listed above take the following form:

1. The compiler is invoked with the message

Compiler new compile: 'test 3 + 3. 5 factorial'

in: Test

notifying: nil

ifFail: []

2. The compiler invokes the parser with the message

Parser parse: aStream

class: class

noPattern: noPattern

context: context

notifying: handler

builder: ProgramNodeBuilder new

saveComments: mapFlag

ifFail: [^failBlock value]

where *aStream* contains the source code of the method, and the remaining arguments specify who will build the parse tree and provide additional information.
3. The parser asks the scanner to convert the source code into tokens. In our case, the scanner produces the following sequence of token-type/token-value pairs:

<table><tr><td>#word</td><td>'test'</td></tr><tr><td>#number</td><td>3</td></tr><tr><td>#binary</td><td>+</td></tr><tr><td>#number</td><td>3</td></tr><tr><td>#period</td><td>.</td></tr><tr><td>#number</td><td>5</td></tr><tr><td>#word</td><td>'factorial'</td></tr></table>

In constructing this sequence, the scanner skipped all characters that don't have any execution effect such as spaces, tabs, and carriage returns. (In actual operation, the scanner transfers control to the parser after each token-type/token-value pair but the principle is the same as if all tokens were generated first which is what we will assume for ease of presentation.)

4. The parser converts the tokens into a parse tree. In terms of Smalltalk objects, the parse tree is one big nested object, the MethodNode object shown in Figures 11.15.
<figure><img src="image_219.png" /><figcaption>Figure 11.15. Nested MethodNode object produced for the example method in the text. Only the essential attributes are shown.</figcaption></figure>

The `methodNode` object can be represented as the *parse tree* in Figure 11.16. Note that each node may be a different kind of object with different instance variables, that there is no prescribed number of children, and that the structure of the tree is determined by the structure of the source code and the syntax rules of Smalltalk rather than comparison of node values as in our previous example.

<figure><img src="image_220.png" /><figcaption>Figure 11.16. Parse tree corresponding to Figure 11.15.</figcaption></figure>

5. Finally, the code generator uses the parse tree to calculate the following `CompiledMethod`:

```
normal CompiledMethod numArgs=0 numTemps=0 frameSize=12
literals: (#factorial)
```
1 <D8 03> push 3
3 <D8 03> push 3
5 <DF 00> no-check send +
7 <66> pop
8 <D8 05> push 5
10 <CC 00> no-check send factorial
12 <45> pop; push self
13 <65> return

In conclusion, let's note that both Parser and Scanner are in the library and you can subclasses them to create recognizer for objects defined by their syntax or to parse programs written in another programming language.

**Main lessons learned:**

* Compilation consists of lexical analysis (scanning), parsing, and code generation.

* Lexical analysis extracts program tokens from the source code, parsing recognizes the grammatical structure of the program, code generation produces a `CompiledMethod` with executable bytecodes.

* Parsing explicitly or implicitly creates a parse tree.

### Exercises

1. Create a simple method, trace its execution, and describe the process.

## 11.8 Graphs

A graph is a mathematical abstraction of concepts such as the road map (Figure 11.17), the layout of house plumbing, the telephone network, the structure of course prerequisites, or the world-wide web. A graph can be completely described by listing its *nodes* (usually called *vertices* - the plural of *vertex*) and the *edges* (*arcs*) connecting them. When the edges are labeled with numbers representing, for example, distances or driving times between cities on a road map, the graph is called a *weighted graph* and edge weights must be included in the description of the graph. As an example, our road map can be described as follows:

V = {Chicago, New York, Toronto, Montreal, Vancouver, San Francisco, Denver, Dallas} "Set of vertices."

E = {(VT,60), (TM,6), (VS,21), (VD,33), (TD,31), (TC,11), etc.} "Set of weighted edges."

<figure><img src="image_221.png" /><figcaption>Figure 11.17. Road map with driving times along selected highways.</figcaption></figure>
The graph in Figure 11.14 is an *undirected graph* because its edges don't restrict the direction in which they must be traversed. In other words, the roads between the cities are not one-way roads. A map showing airline connections (Figure 11.18), on the other hand, may have restrictions because the airline may not provide flights in both directions between all cities. Such a graph is called a *directed graph*.

<figure><img src="image_222.png" /><figcaption>Figure 11.18. Directed graph of fictitious airline connections.</figcaption></figure>

Many books have been written about graphs, their representation, the algorithms for performing various calculations on them, and their relative efficiency. In this section, we will only address the problem of finding the shortest path between two vertices in an undirected graph with weighted edges (the shortest driving time between two cities), finding the shortest path between two vertices in a directed graph with unweighted edges (the minimum number of flight changes), and testing connectivity (existence of a path from one city to another).

## Class Graph

All graphs can be represented as directed weighted graphs: Undirected graphs are directed graphs in which all pairs of vertices have either edges in both directions or none, and unweighted graphs can be represented as graphs where all edges have some irrelevant weight, possibly nil. We can thus implement all graphs using just one class whose attributes consist of vertices and weighted edges. This representation is, of course, redundant but we will use it for our examples.

One way to think about a graph is as a set of vertices, each of which has a distinguished value (such as a city name), knows its neighbors (vertices that can be reached from it), and the cost of getting to each neighbor. This is easily implemented by a Dictionary whose keys are vertices and whose values are objects consisting of a connection to a neighbor (edge) and the weight of the connecting edge. We could implement these edge-weight objects as instances of a new class but they are so simple that we will implement them as two-element arrays. As an example, our unweighted airline map could be represented as a dictionary containing the following associations:

'Chicago' -> Set (#{'NewYork' nil}#{'Denver' nil})

'Dallas' -> Set ()

'Denver' -> Set#{'Dallas' nil}#{'NewYork' nil}#{'SanFrancisco' nil}

etc.

It is tempting to make the new class Graph a subclass of Dictionary but this would be wrong because the two classes don't share any functionality. We will thus make Graph a subclass of Object and put the Dictionary describing its structure into an instance variable called structure. The following is the comment of the class:

I implement directed graphs consisting of vertices and weighted edges.
## Instance variables

**structure** `<Dictionary>` association key is node, value is a set of two-element arrays consisting of vertex ID and the corresponding edge weight.

As usual, we will start implementation with the creation protocol. The creation method simply creates a new Graph and assigns a dictionary to structure as follows:

**newWith: aDictionary**

"Create a new graph whose structure is defined by aDictionary."

^self new dictionary: aDictionary

After creating a printOn: method and testing it (left as an exercise), we now define additional accessing methods. As an example, the following accessing method to simplifies access to neighbors:

**edgesFor: anObject**

"Return the set of vertex-weight objects of vertex anObject."

^structure at: anObject

We are now ready to deal with the graph problems listed at the beginning of this section.

## Testing connectivity

**Problem:** Define a method to determine whether there is a path from one vertex to another, for example, a sequence of flights from Montreal to San Francisco.

**Solution:** The principle of the solution is simple (Figure 11.19): First, we find and mark all vertices that can be reached directly from to source vertex (Montreal). We then find and mark all vertices that can be reached directly from these cities. And we continue doing this until we either reach the destination vertex (San Francisco) or until there are no more unmarked reachable cities. In the first case there is a path from Montreal to San Francisco, in the second case there is no such path.

<figure><img src="image_223.png" /><figcaption>Figure 11.19. Testing connectivity. The source (Montreal) is a white rectangle, adjacent cities are shown with light gray, cities directly reachable from them are shown with darker gray, and so on until we reach San Francisco.</figcaption></figure>

The method implementing this idea requires two arguments – an identification of the source vertex and the destination vertex - and returns true or false. We will call it connected:to: and use it as in

flights connected: 'San Francisco' to: 'Toronto'
where flights is presumably the graph describing the flight map.

Our definition will follow the informal description given above but refined down to the level of implementation. The informal description shows that we are always dealing with three kinds of vertices: Those that have already been processed, those that are now being used to find new reachable vertices, and those that have not yet been used at all. This can be implemented by keeping vertices of each kind in a collection. If we call these boxes done, active, and remaining, we can describe the algorithm as follows:

1. Put the starting vertex into active, initialize remaining to all other vertices, and done to empty.

2. Repeat the following until the destination vertex appears in active, or until no more vertices are accessible, in other words until active becomes empty:

a. Enumerate over all vertices in active:

For each vertex v

add all its immediate neighbors in remaining into active

move vertex v from active to done.

Using a queue for the collection leads to a *breadth-first algorithm* which first explores all vertices at the same 'level' from the starting situation. An algorithm that follows a path all the way down and then starts another is called a *depth-first algorithm*. We will use a queue for active as follows:

### connected: object1ID to: object2ID

"Is the object whose ID is object1ID connected to the object whose ID is object2ID? Return true or false."

| active | done | remaining | startObject | found |

"Initialization."

active := OrderedCollection new: structure size. "Use OrderedCollection as a queue."

active add: (startObject := structure associationAt: object1ID).

done := Set new: structure size.

remaining := structure - (Dictionary with: startObject).

found := false.

"Iteration."

[active empty or: [ found := active contains:

[:vertex| (vertex value contains: [:array | (array at: 1) = object2ID)]]] whileFalse:

[ |currentVertex neighbors |

done add: (currentVertex := active removeFirst).

neighbors := self unprocessedNeighborsOf: currentVertex key
from: remaining.

active addAll: neighbors.

remaining := remaining - (Dictionary withAll: neighbors)].

^found

where neighborsOf: currentVertex searches collection remaining (unprocessed vertices) for the neighbors of the vertex currently being examined. To make its definition more readable, we expressed it using cities instead of general objects:

### unprocessedNeighborsOf: aCity from: remainingVertices

"Return collection of associations of all neighbors of aCity that remain unprocessed."

| cities | unprocessedNeighbors | remainingCities | neighboringCityArrays |

"Gather names of unprocessed cities that are neighbors of aCity."

remainingCities := remainingVertices keys. "Get names of all remaining city-vertices."

neighboringCityArrays := (structure at: aCity) select: [ "Select those that neighbor aCity." :setElement | remainingCities contains: [:cityEl | cityEl = (setElement at: 1)]]].

cities := neighboringCityArrays collect: [:array | array at: 1]. "Extract city names out of arrays."

unprocessedNeighbors := OrderedCollection new.

"Now use cities to get associations – the complete vertex descriptions."

remainingVertices keysAndValuesDo: [:key :value | (cities contains: [:city | city = key])

ifTrue: [unprocessedNeighbors add: (remainingVertices associationAt: key)]].

^ unprocessedNeighbors
Perhaps the trickiest part of these methods was to figure out what the individual messages return. As an example, we made the mistake of using `includes:` instead of `contains:` and it took a while before we realized that this was wrong.

To test our code, we used our map and checked whether Montreal is connected to San Francisco (should return true) and whether San Francisco is connected to Toronto (should return false):

```
| cities flights |
"Create data."
cities := Dictionary new
    add: 'Montreal' -> (Set withAll: #(#('Chicago' nil) #('New York' nil)));
    add: 'New York' -> (Set withAll: #(#('San Francisco' nil)));
    add: 'Chicago' -> (Set withAll: #(#('Denver' nil) #('New York' nil)));
    add: 'Toronto' -> (Set withAll: #(#('Vancouver' nil) #('Montreal' nil) #('New York' nil)
('Dallas' nil) #('San Francisco' nil)));
    add: 'Denver' -> (Set withAll: #(#('New York' nil) #('San Francisco' nil) #('Dallas', nil)));
    add: 'Dallas' -> (Set new);
    add: 'San Francisco' -> (Set withAll: #(#('Dallas' nil) #('Vancouver' nil)));
    add: 'Vancouver' -> (Set withAll: #(#('San Francisco' nil) #('Denver' nil)));
yourself.
flights := Graph newWith: cities.
"Do calculations and output results."
Transcript clear
    show: 'Montreal is',
        ((flights connected: 'Montreal' to: 'San Francisco')
           ifTrue: ['] ifFalse: ['not'],
           ' connected to San Francisco';
cr;
    show: 'San Francisco is',
        ((flights connected: 'San Francisco' to: 'Toronto')
           ifTrue: ['] ifFalse: ['not'],
           ' connected to Toronto'
```

The test returns the correct result

Montreal is connected to San Francisco
San Francisco is not connected to Toronto

The shortest path in a weighted undirected graph

Consider our road map now and the problem of finding the shortest path from one city to another. Assuming that all weights are non-negative, this can again be done by successive iterations, constantly enlarging the set S of vertices whose shortest distance to the starting vertex v is already known.

At the beginning, we only have one vertex whose shortest distance to v is known - v itself - and its distance to v is 0. We will thus initialize set S to v. In each consecutive step, we examine all vertices that can be reached from any vertex already in S in exactly one step, select the one whose distance to v (calculated from vertices in S) is the shortest, and add it to S. Since this changes S, we recalculate the shortest distance of all vertices not in S that can be reached in one step from S. If the destination node is reachable from v, it will eventually become a member of S and the distance calculated at that point is its shortest distance from v.

This interesting strategy is called a greedy algorithm because it always grabs the most appealing choice. We will prove shortly that it indeed gives the desired result but first, let's demonstrate how it works when finding the shortest distance from vertex 1 to vertex 6 in Figure 11.20.

<figure><img src="image_224.png" /></figure>
<figure><img src="image_225.png" /><figcaption>Figure 11.20. Left to right, top to bottom: Finding the shortest distance from vertex 1 to vertex 6.</figcaption></figure>

1. Initialization. Initialize S to source vertex 1: $S = \{1\}$. This is indicated in the top leftmost diagram by showing vertex 1 with a dashed border.

2. Iteration 1. $S = \{1\}$.

a. For each vertex reachable from S in one step, calculate the shortest distance from source vertex 1 to this vertex. In our case there are two such vertices - vertex 2 and vertex 3 - and we obtain the distances indicated in the diagram.

b. Find the vertex that is not in S and whose calculated distance to vertex 1 is the shortest. In our case, this is vertex 2. Add this vertex to S so that $S = \{1, 2\}$. We indicate that 2 is now in S by drawing its border dashed (second diagram from left).

3. Iteration 2. $S = \{1, 2\}$.

a. Recalculate shortest distances to 1 for all vertices not in S. In our case, this does not change existing distances.

b. Find the vertex closest to v and not in S. In our case, this is vertex 4. Add this vertex to S (second diagram from left).

4. Iteration 3. $S = \{1, 2, 4\}$.

a. Recalculate shortest distances for vertices not in S. No change in existing distances.

b. Find the vertex closest to v and not in S. In our case, there are two candidates - vertex 3 and vertex 5, both with distance 4. We arbitrarily choose 3 (third diagram from left).

5. Iteration 4. $S = \{1, 2, 4, 3\}$.

a. Recalculate the shortest distances for vertices not in S. No change in existing distances.

b. Find the vertex closest to v and not in S and add it to S. This will be vertex 5 3 (first diagram at left bottom).

6. Iteration 5. $S = \{1, 2, 3, 4, 5\}$.

a. Recalculate the shortest distances for vertices not in S. This changes the shortest distance between vertex 1 and vertex 6.
b. Find the vertex closest to v and not in S and add it to S. This will be vertex 6 (second diagram from left).

7. There is only one vertex left that is not in S - vertex 6. Add it to S and stop (bottom right diagram). The shortest distance from 1 to 6 has now been found and its value is 5. Note that we found not only the shortest distance between 1 and 6 but also the shortest distance between 1 and all other vertices in the graph reachable from vertex 1.

After demonstrating how the algorithm works, we will now prove that it really produces the shortest
distance. Our proof is based on induction and indirection.

*Proof.* Assume that the algorithm works for some intermediate value of S. (It obviously does when S consists of the source vertex only.) Assume that we just added vertex v to S using our algorithm. According to our claim, the distance from the source vertex to v is the shortest distance from the source to v.

Assume, for a momemnt, that the claim is *false*<fnref n="5" /> and that there is a path giving a *shorter* distance from the source to v. Assume that the first vertex on this alternative path that is outside S is x (Figure 11.21). Let the distance from source to v found by our algorithm be dv, and let the distance from the source to v going through x be dx. If the distance through x is shorter, then dx < dv.
Since the distance from x to v is not negative,

$$
\text{dist}(\text{source} \to x) \le \text{dist}(\text{source} \to x \to v) = dx < dv
$$

This implies $dx < dv$. However, if $dx < dv$, our algorithm would have added $x$ to S rather than $v$
because it always adds the closest reachable vertex. Since it added $v$, the assumption that the path through $x$
is shorter is false. Consequently, the distance obtained for $v$ by our algorithm *is* the shortest distance from
the source and $v$.

<figure><img src="image_226.png" /><figcaption>Figure 11.21. Illustration supporting the proof of the shortest path algorithm.</figcaption></figure>

After proving that our algorithm indeed finds the shortest distance, let's formulate it in more detail.
Using three collections (*remaining*, *done*, *activeNeighbors*), a more precise description is as follows:

1. Put all vertices except the source vertex s in remaining. Put vertex s in done. Initialize activeNeighbors to an empty collection. Initialize distance of vertex s to 0.

2. Repeat the following until remaining becomes empty or until done contains the destination vertex:

a. Move all vertices in remaining reachable in one move from done into activeNeighbors

b. For each vertex in activeNeighbors calculate the shortest distance to s via done.

c. Move the activeNeighbors vertex whose distance to s is the shortest into done.

3. If done contains the destination vertex, return its distance to s. Otherwise return nil to indicate that there is no path from the source to the destination.

<footnote n="5">⁵ Proving a claim by showing that its negation is false is called an indirect proof.</footnote>
We leave it to you to implement the algorithm as an exercise.

### Main lessons learned:

* A graph consists of nodes (vertices) connected by edges.

* Graphs and operations on them can be very complex and their efficient implementation is one of the major areas of research in Computer Science.

### Exercises

1. Extend the flight connection checking method to calculate the smallest number of cities that must be traversed if there is a connection.

2. Prove that our connection checking algorithm indeed fulfills its purpose.

3. Design and implement methods that return the shortest weighted and unweighted path in addition to the weighted or unweighted distance.

4. One of the common applications of graphs is representation of activities that must occur in a certain order. Academic courses and their prerequisites and the sequence of activities in building a house are two typical examples. Sorting a directed graph on the basis of vertex precedences is called topological sort. Formulate, implement, and test an algorithm performing topological sort.

5. Examine our implementation of graph algorithms, find the most inefficient points, and improve the implementation.

## Conclusion

This chapter introduced several specialized kinds of collections including stacks, queues, linked lists, trees, and graphs. Although most of them are not explicitly included in VisualWorks library, they are essential for Smalltalk operation and very important in Computer Science applications. In exploring these collections, we introduced several features of internal operation of Smalltalk.

A stack is a last-in first-out structure. Elements are added at the top using the push operation, and removed again from the top using the pop operation. Stack behavior is a part of the behavior of OrderedCollection and there is no need for a Stack class.

An important use of stacks is Smalltalk's execution of messages. Execution of Smalltalk messages depends on a stack of context objects, each of them carrying full information about a message including its receiver and sender, its arguments and local variables, and current state of execution. Each message context also has its evaluation stack for intermediate results. When a message is sent, its context is pushed on the top of the context stack and when finished, the context is popped off. A part of the context is a translation of the code into bytecodes.

Another important example of the use of stacks is exception handling. Smalltalk has a built-in mechanism for dealing with exceptional situations and since this process intervenes into message execution, it is very closely tied to the operation of the context stack. The existence of exception handling allows the programmer to anticipate possible exceptional behaviors and deal with them programatically, preventing the program from raising an exception. Exception handling is achieved by sending a message specifying the desired behavior and the exception handling code to an instance of Signal which then delegates the handling to an instance of Exception. A number of Signal objects for dealing with common exceptions are built into the library and users can define their own as well.

A queue is a first-in first-out structure where elements are added at one end and removed from the other. Queue behavior is subsumed by OrderedCollection and there is no need for class Queue. One of the most important applications of queues is in simulation but the Smalltalk run-time environment also uses queues for several operations. Some of these will be covered in Chapter 12.

A list is a linear collection in which each element knows about its successor (single linked list) or its successor and predecessor (doubly linked list). VisualWorks library contains a pair of general classes
called **LinkedList** and **Link** implementing the basic linked list behavior. For concrete use, these classes are usually subclassed. The advantage of links is that they allow easy insertion and deletion.

A tree is a branching structure of nodes and their children. The node at the top of a tree is called the root. Every node in a tree except the root has exactly one parent. The root does not have a parent. The bottom nodes in a tree - the nodes that don't have any children - are called leafs.

In general, a node in a tree may have any number of children but specialized trees may restrict the number of children a node is allowed to have. As an example, a node in a binary tree may have at most two children. A very important use of trees is in compilation but the Smalltalk compiler does not build a tree explicitly. Instead, it constructs a nested structure of node objects equivalent to a tree.

Graphs are the most complex type of collection. A graph consists of nodes (vertices) connected by edges. Edges may be directed or undirected, weighted or unweighted. Graphs and operations on them can be very complex and their efficient implementation is one of the major areas of research in Computer Science. Since the operation of Smalltalk does not require any graphs, graphs are not included in the library.

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

CompiledMethod, Exception, Signal, **LinkedList**, Link.

**Terms introduced in this chapter**

*binary tree* - a tree allowing at most two children per node

*breadth-first algorithm* - an algorithm that deals with all children of a node before examining the children's children

*context* - information needed to execute a message including its code, sender, receiver, arguments, temporary variables, current state of execution, and working stack

*context stack* - stack of contexts of all currently active messages stored in order of execution

*depth-first algorithm* - an algorithm that follows a complete path to a leaf before dealing with sibling nodes on the same level

*exception* - abnormal behavior such as attempt to divide by zero or attempt to access an illegal index

*exception handling* - execution of predefined code when an exception occurs

*graph* - a collection of vertices connected by edges, possibly directed and weighted

*leaf* - a tree node with no children

*lexical analysis* - the process of converting textual source code into a collection of program components such as number, word, binary selector, or keyword; first step in compilation

*linked list* - linear collection held together by single links

*parsing* - the process of recognizing grammatical constructs such as statements and blocks during compilation; follows scanning and precedes code generation

*pop* - the act of removing an element from the top of a stack

*push* - the act of adding an element at the top of a stack

*queue* - linear collection where elements are added at one end and removed at the other

*root* - the top node of a tree; has no parent

*scanning* - synonym of lexical analysis

*stack* - linear collection where elements are added and removed at the same end

*tree* - collection of object nodes in which each node may have one or more children, and where each node except the root has exactly one parent
# Chapter 12 - Developing user interfaces

## Overview

The group of classes supporting graphical user interfaces (GUIs) is one of the most complex parts of VisualWorks and its detailed coverage is beyond the scope of this book. Fortunately, to be able to use the tools for routine applications and to create interesting extensions of the widget library, you only need to understand a limited number of concepts, and specialized books are available for more advanced uses.

The first requirement for creating a user interface is to be able to draw objects such as lines, widgets, and text on the screen. VisualWorks perspective is that drawing requires a surface to draw on (such as a computer screen or printer paper), the graphical objects being drawn, and an object that does the drawing and holds the parameters that describe the drawing context (such as fonts, colors, and line widths).

Being able to draw an object on the screen is, however, only a part of a typical GUI. Unless the displayed windows are completely passive, the user must also interact with them via the mouse and the keyboard. A user interface must also ensure that the display reflects changes of the displayed data model, and that damage caused, for example, by resizing a window is automatically repaired.

To implement automatic response to model changes and user interaction, Smalltalk uses the model-view-controller paradigm - MVC for short. The model part of the MVC triad holds data and provides notification when the data changes. The view is responsible for drawing the component on the screen, response to model changes, and damage repair. The controller handles user input.

To maintain the UI painting paradigm supported by the UI Painter, we also need a way to integrate a new visual component into a canvas. This is achieved by a widget called the subview which implements access to its view part and the connection to its window container.

## 12.1 Principles of user interfaces - display surfaces, graphics contexts, and visual parts

This section is dedicated to the principles of VisualWorks user interfaces and provides background for customization of windows and their main components. In routine applications, no programming involving these components is necessary but understanding of these concepts is useful.

Displaying graphical objects on the screen is a complex task and different languages and even different dialogs of Smalltalk approach it differently. The view of VisualWorks is that drawing requires a drawing surface, objects to be displayed, and an object that can do the drawing and holds parameters describing how and where the drawing takes place. We will now deal with these concepts one by one and illustrate them on simple examples. A larger example follows in the next section.

### Display surfaces

Display surfaces are the media on which all visuals, including geometric objects, images, widgets, and text, are displayed. The hierarchy of display media is large and its skeleton is as follows:

#### Object

**GraphicsMedium**

**DisplaySurface**

* UnmappableSurface

* Mask

* Pixmap

**Window**

**ScheduledWindow**

**ApplicationWindow**

* TransientWindow

* HostPrintJob

* MockMedium

* PostScriptFile
The abstract class GraphicsMedium at the top of the hierarchy defines the protocol for accessing information such as display defaults (paint, font, and look preferences which include background and foreground color), size of the display surface, number of bits used to represent the color of pixels, and graphics context (an object responsible for display of geometric objects, images, and text). GraphicsMedium is the supporting instance variables are defined in subclasses.

Subclasses of GraphicsMedium can be divided into those displaying on the screen, those used to construct displayable surfaces in memory, and those dedicated to printing. We will deal only with the first two categories and leave printing to you as an exercise. The group of classes responsible for screen display and display construction are headed by DisplaySurface whose comment essentially says:

Class DisplaySurface is the abstract class for all classes that act as destinations for graphics operations targeted for a bitmap video display (as opposed to printing, for example).

Instance variables:

<table><tr><td>handle</td><td>&lt;GraphicsHandle | nil&gt;</td><td>handle to the host resource, an interface to the operating system which performs the low level display functions</td></tr><tr><td>width</td><td>&lt;SmallInteger&gt;</td><td>width of the surface in pixels</td></tr><tr><td>height</td><td>&lt;SmallInteger&gt;</td><td>height of the surface in pixels</td></tr><tr><td>background</td><td>&lt;Paint&gt;</td><td>paint used to clear the surface</td></tr></table>

Even though DisplaySurface is abstract, it provides a lot of useful functionality such as closing the display surface (for example, a window) and access to any part of the display area. Subclasses of DisplaySurface can be subdivided into classes whose instances correspond to windows displayed on the screen, and classes that instantiate display surfaces in memory but don't display them.

## Windows

Class Window at the top of the window hierarchy is a concrete class with much functionality but rather useless by itself because its instances have neither a controller (thus allowing only minimal user interaction) nor a component (thus incapable of containing widgets). A lot of the behavior inherited from Window is, however, essential. This includes the knowledge of the window's origin on the screen, its label, its icon, and its sensor which holds information about mouse and keyboard events that occur within the window's extent. Window also defines methods for opening a window (redefined in subclasses), collapsing it into an icon and re-expanding it, moving and resizing a window, and raising it to the top to become the active window on the screen. It also knows the currently active window (class message currentWindow).

As an example of window manipulation, execute the following code fragment to see some of the Window functionality:

```
"Open window, collapse it, expand it, and close it."
| window |
window := Window openNewIn: (100@100 corner: 200@200).
(Delay forSeconds: 3) wait.
window label: 'Test'.
(Delay forSeconds: 3) wait.
window collapse.
(Delay forSeconds: 3) wait.
window expand.
(Delay forSeconds: 3) wait.
window close "Without this statement, you will not be able to close the window."
```

Class Window has very little direct use and we will thus proceed to its subclass ScheduledWindow. This class adds several behaviors and instance variables, the most important being controller (handles user interaction), component (makes it possible to include a visual part or a collection of visual parts in the window), and model (allowing another object to control a window). The controller of ScheduledWindow is an instance of StandardSystemController which provides the `<window>` menu and methods for closing,
resizeing, moving, relabeling, and other window operations. The window controller is also the means by
which Smalltalk keeps track of all its windows and the controllers of all open Smalltalk windows are kept in
ScheduledControllers, an instance of ControlManager. The following is a simple example showing how to
open a ScheduledWindow:

"Open window with label but with no component, and let user close it."

| window |
window := ScheduledWindow new.
window insideColor: ColorValue blue;
label: 'Test'.
window openIn: (100@100 corner: 200@200)

The user can close a ScheduledWindow in the usual way which is not true for a Window. The
window in this example does not have any components so it's not of any interest but we will do an example
with a component later.

Until recent VisualWorks releases, ScheduledWindow was the basis of all user interfaces - there
was no UI Painter and all UIs had to be created programmatically using ScheduledWindow. With the
introduction of the UI Painter, this has changed and applications based on the application model use the
ApplicationWindow subclass of ScheduledWindow. ScheduledWindow has thus lost its importance except
that it defines many behaviors inherited by ApplicationWindow. In the current class library, most references
to ScheduledWindow are in examples because (as our example shows) it is easier to create a very simple
demo window programatically than to paint one using the UI Painter.

From within an application, the ApplicationWindow of the interface can be accessed by sending
message window to the application builder. As an example, the application model could send

self builder window label: 'New label'

to change the window's label at run time. The essential part of the comment of ApplicationWindow is as
follows:

ApplicationWindow adds functionality required by the User Interface building classes. It also provides for
tighter coordination with a corresponding ApplicationModel. In particular, an ApplicationWindow can notify
its application of window events (e.g. closing or collapsing), so that other dependent windows can follow
suit. Recognized events are #expand, #collapse, #bounds, #enter, #exit, #close, #hibernate, #reopen, and
#release.

Instance Variables:

<Table><tr><td>keyboardProcessor</td><td>&lt;KeyboardProcessor&gt;</td><td>Manages keyboard input</td></tr><tr><td>application</td><td>&lt;Object | nil&gt;</td><td>The application, typically an ApplicationModel</td></tr><tr><td>receiveWindowEvents</td><td>&lt;Array | nil&gt;</td><td>Window events the receiver should respond to</td></tr><tr><td>damageRepairIsLazy</td><td>&lt;Boolean&gt;</td><td>Used to control when damage coming up from below is repaired.</td></tr></Table>

Variable damageRepairIsLazy is used to determine whether a damaged window should be repaired
(redrawn) immediately or whether redisplay can wait until a suitable later time. We will talk about damage
repair later.

Typical messages sent by the application model to an application include changing its label or
background color at run time (messages label: and background:), moving it to a new position (message
moveTo:) obtaining its bounding rectangle (displayBox), closing the window (close - usually achieved by
sending closeRequest to the application model), collapsing it to an icon and expanding the icon back to a
window (collapse and expand), and hiding the window without destroying its internal representation
(message unmap) and restoring it without having to reconstruct it (message map). In many cases, a window
changed at run time must be redisplayed by message display.

When an application model needs to access more than one window, create a new builder for each
of the secondary windows, specify its source as the application model, specify the window's application as
the application model, and ask the secondary builder to open the interface. You can also make the
secondary window a slave of the master window (message slave). The result is that the slave will mimic
closing, collapsing, and expanding of the master window. The slave window may also be made sensitive to
other master window events such as cursor entry or exit. Finally, windows can also be partners by sending bePartner to the window. Partner windows are tied together in the same way as master and slave windows.

We will see examples of some of this functionality in the following sections and other examples are provided in the cookbook.

### Main lessons learned:

* In the perspective of VisualWorks, display requires a display surface, objects to be displayed, and a drawing engine (a graphics context).

* Display surfaces are subclasses of GraphicsMedium which has two subtrees, one for display on screens and one for printing on paper.

* Display on screen uses windows and the window hierarchy includes classes Window, ScheduledWindow, and ApplicationWindow.

* Windows created with the UI Painter and used by application models are ApplicationWindows. They inherit most of their functionality from ApplicationWindow superclasses.

* ApplicationWindow has numerous instance variables holding parameters such as bounding box, clipping rectangle, graphics context, background paint, and others.

* Pixmap and Mask are display surfaces used to construct displays before they are mapped to the screen.

## 12.2 An example of the use of windows – a Virtual Desktop

One annoying aspect of graphical user interfaces is that computer screens are always too small to display all the windows that one would like to see at a time. A partial solution to this problem is a 'virtual desk' program which allows the user to place individual open windows on 'desks' and view only one desk at a time. We will design and implement a very simple version of such a program. We will call it Desk Manager and implement it via class SmallDesk.

Our program will make the screen behave as a peep hole on a much larger desktop divided into four screen-size rectangular areas. The selection of the desired desk is via the user interface in Figure 12.1. The four buttons on the left represent the virtual desks and the button of the currently displayed desk is highlighted. When the user clicks an un-selected desk, SmallDesk hides all VisualWorks windows on the current desk and displays all VisualWorks windows assigned by the user to the selected desk. The Desktop window itself remains visible at all times.

<figure><img src="image_227.png" /><figcaption>Figure 12.1. Default user interface of SmallDesk manager.</figcaption></figure>

The buttons on the top right allow the user to open a Workspace and a Browser on the current desk because opening a Browser or a Workspace is the most common way to start populating a desk with windows. The two buttons on the bottom right allow the user to rename desk buttons and to move a selected window from one desk to another. A desktop can also be opened with other than default desk names and the user can specify which applications should be displayed on individual desks.
Additional specification details:

* When SmallDesk opens with the default open message, it selects desk 1 and maps (displays) all windows already on the screen on this desk. All other desks are empty.
* When **SmallDesk** closes, it maps all windows from all desks. In other words, it displays all VisualWorks windows assigned to all four desks on the screen.

* When the user clicks **Rename desk**, a prompt requests the new name for the current desk and displays it on the button.

* The **Move** button allows the user to move a window from the current desk to another desk. It opens two consecutive prompts that allow the user to identify the window to be moved and its new desk. If the destination is different from the current desk, the selected window is unmapped and assigned to the specified desk; no desk switch occurs. The **Desk Manager** window itself cannot be moved to another desk and is always displayed.

* The user can also open **SmallDesk** by one of several more powerful messages. As an example, to open the desk on desk 2 with button names, and assign application **LecturePad** to the first desk, two workspaces to the second, a **Browser** to the third, and two copies of **Notes** to the fourth, the user will execute

### SmallDesk

```
openWithManyApps: #(#(LecturePad) #((ComposedTextView ComposedTextView) #((Browser) #((Notes Notes)))
andNames: #('desk 1' 'desk 2' 'desk 3' 'desk 4')
onDesk: 2
```

## Preliminary design

We only need one class - an application model to be called **SmallDesk**. This class will be responsible for user interface specification, opening messages, and action buttons. We will keep the mapping of windows to desks in a dictionary, using windows as keys and integer numbers of desks as values.

The major responsibilities of **SmallDesk** are as follows:

**Opening.** The default opening message assigns all VisualWorks windows on the screen to desk 1 and highlights its button. Specialized opening messages do one or more of the following: rename buttons, assign specified applications to specified desks, open on specified desk.

**Action methods.** Action methods can be divided into the following groups:

* **Desk button** action methods. The user clicks a desk button either to switch to a different desk or to identify the destination desk when moving a window from one desk to another.

* **Browser button** and **Workspace** button open the **Browser** and the **Workspace** on the current desk.

* The **Rename** button displays a prompt and assigns the obtained string as the label to the currently selected desk button.

* The **Move** button displays a prompt to identify a window, another prompt to identify the destination desk, unmaps the window from the current desk, and assigns it to the destination map. An attempt to move the **Desk Manager** window itself will be refused with a warning.

**Closing.** This button will prompt the user to confirm when he or she attempts to close **SmallDesk**. It will then map all windows to the screen and close **SmallDesk**.

## Design refinement

Before writing the specification of **SmallDesk**, we will examine some of the details that we ignored in preliminary design starting with instance variables. We need a window registry that holds information about the assignment of windows to desks. We also need to know the current desk's number so that we can rename it and map and unmap windows on desk change request, and check whether a new desk selection is different from the current one.
To deal with the two different modes of operation that affect the result of clicking a desk button (switching to a different desk versus renaming it), we must also keep track of the mode. We will represent it by a **Symbol** which will be identical to the name of the method that executes the operation so that we can execute the method by the **perform:** message. Finally, we will use ‘lazy opening’ to open applications specified by the user in the opening message. **SmallDesk** will initially open only applications on the opening desk, and the remaining applications will only be opened when the user switches to the desk assigned to them. We will keep unopened applications in a four-element array with one element corresponding to each desk.

We can now start thinking about the methods. Default initialization puts all VisualWorks windows on the screen on desk 1, sets current desk number to 1, and mode to ‘switch to another desk’. It also initializes the array of unopened applications.

The method performing desk change checks whether the new desk is different from the current one (and do nothing if it is), change the colors of backgrounds of the current and new desk buttons, update window registry (windows may have opened or closed on the current desk since the last registry refresh and this must be recorded), unmap the windows on the current desk, map windows on the new desk, open the unopened applications assigned to this desk, and make new desk the current desk.

Finally, when the user clicks to close **SmallDesk** and confirms, all scheduled windows from all desks are mapped to the screen.

We can now write the following detailed specification of class **SmallDesk**:

**SmallDesk.** This class helps the user to reduce screen clutter by creating four virtual screens called desks. **SmallDesk** continuously displays a Desk Manager window with four buttons representing the virtual desks and allows VisualWorks windows to be associated with any one of them. Only windows assigned to the current desk are displayed. Desk buttons can be renamed and windows can be moved from one desk to another. The application can open on any desk, with any combination of desk button names, and with specified applications assigned to individual desks.

*Superclass: ApplicationWindow.*

*Instance variables: windowRegistry <IdentityDictionary> pairs windows with desktops (integers), waitingApps <Array> contains an array with class names of unopened applications for each desk, currentDesk <Integer> identifies currently displayed desk, mode <Symbol> identifies the current context of operation - one of #changeTo:, #moveTo:*

*Responsibilities:*

* Opening

* `openWithManyApps: andNames: onDesk:` opens the application on the specified desk and with the specified applications. All currently displayed Smalltalk windows are assigned to desk 1.

* `open` - special case of the above method that opens with default button names, on desk 1, and with no new applications.

* Initialization and closing.

* `initialize` - the standard opening hook method. Gets all VisualWorks windows from **ScheduledController** to initialize **windowRegistry**, initializes **currentDesk** to 1 (overridden later when a different desk is specified), mode to #changeTo:.

* `closeRequest` asks the user to confirm **SmallDesk** closing, maps all windows referenced by **ScheduledControllers** and allows the Desk Manager window to close.

* Action methods responding to UI buttons.

* **desk1**, **desk2**, **desk3**, **desk4** methods all act in the same way and the only difference between them is that each identifies a different desk. Consequently, they all send private message **updateDesk**: with their number as the argument and further processing happens in this method. Since the same method is used for changes, its operation depends on the context: It performs one of the two possible actions corresponding to the two possible contexts in which the button may be activated. These two actions will be implemented by

* `changeTo:` - checks whether the new desk is different and if it is, hides currently displayed windows, displays windows assigned to the new desk, opens waiting applications assigned to this desk, and colors the buttons appropriately.