combined with others in new combinations, thereby eliminating the need to construct a variety of custom user interfaces with similar behaviors. Some of the possibilities are as follows:

* The same model data may be displayed by a different view in different modes of operation of the application. As an example, an object representing economic data may be represented as a pie chart or as a graph and the switch from one to another may be controlled by clicking a button.

* The same model may be simultaneously displayed by several different views. As an example, a mathematical function may be displayed as a collection of x and y values in a table, and as a diagram in the same window.

* The same view can be used with many different models. As an example, a pie chart object may represent economic data in one application and demographic data in another without any change in its definition. The switch requires only the assignment of a different model.

* The same view can use different controllers. As an example, the same Text Editor may use a read-write controller when the application is used by fully authorized users, and a read-only controller when the program is used by less authorized users.

* The same controller may be used with different views. As an example, a controller sensitive to mouse clicks and equipped with an `<operate>` menu could be used in an input field and a text editor.

Smalltalk's implementation of the MVC concept is based on the communication patterns in Figure 6.8 and made possible by instance variables of the three objects. As the diagram shows, each object in the triad can communicate directly with each other object except that the model does not have direct access to the controller view. The typical communications are as follows:

The *controller* generally needs to notify the *model* about user interaction. As an example, when the user clicks a square in a clickable chess board view in a chess program (Section 12.7), the controller must tell the model which square has been selected.

The *view* needs access to its *model* when it needs to redisplay itself. As an example, when a chess player clicks a piece, the controller notifies the model, the chess board model asks the view to display it, and the view asks the model for information about the squares that must be redisplayed. This typical scenario thus requires controller -> model and model <> view communication.

As an example of communication between a *controller* and its *view*, consider an application such as the canvas painter in which the user can drag objects within a window. To do this, the controller can communicate with the view directly.

Communication from the *view* to the *controller* is usually restricted to specifying an appropriate controller class when the first input event occurs. This message then creates the controller.

<figure><img src="image_135.png" /></figure>
<figure><img src="image_136.png" /><figcaption>Figure 6.8. Top: Standard lines of communication among the three components of the MVC triad and the meaning of MVC components. Bottom: A single model may have two or more different view-controller pairs.</figcaption></figure>

Although every widget that displays data has its special model, view, and controller, it is not surprising that all models, all views, and all controllers have something in common and that their implementation is based on abstract class called Model, View, and Cotroller. We will now outline the principle of these class and return to views and controllers in much more detail in Chapter 12 which is fully dedicated to this subject.

Class Model is responsible for the dependency mechanism. Its definition is quite simple and consists of variable dependents which can hold any number of objects dependent on the model, and methods implementing dependency. (In fact, these methods are inherited from Object.) Class Model has numerous subclasses including ApplicationModel (and with it all application models defined by the system or the user) and ValueHolder (a subclass of ValueModel which defines value, value: and value: VALUE).

Class Controller is the father of all controllers. It introduces variables view and model that refer to its companions in the MVC triad, and numerous methods. Perhaps the most interesting of these are methods that provide hooks to input events and are sent when a user clicks a button, moves the mouse, presses a key, and so on. These methods are hooks that are reused by all subclasses whether system-defined or user-defined.

Class View is the mother of all view. It knows about its model and controller and provides or inherits mechanisms for creating nested views. It also provides automatic damage repair which is necessary when the view is damaged (for example obstructed and then uncovered). Any class subclassed to View inherits this essential and valuable behavior.

We will have much more to say about the MVC triad and about its components in Chapter 12 which is completely dedicated to views and controllers.

## 12.7 IDs make widgets accessible at run time - a Tic-Tac-Toe game

In this section, we will explain the purpose of widget IDs and illustrate it on a program implementing a Tic-Tac-Toe game with the user interface in Figure 6.28.
<figure><img src="image_137.png" /><figcaption>Figure 6.28. Desired user interface.</figcaption></figure>

The game is played by two players denoted X and O; the first player is always X. When the window first opens, the squares on the game board are blank and the players start taking turns clicking the squares. When a player clicks an empty square, the square displays the player's symbol (X or O). If this results in three vertical, three horizontal, or three diagonal squares marked by the same symbol, the player wins; otherwise the game continues. If the player clicks an already marked square, the program displays a warning asking the user to click an empty square. The *Reset* button resets the board to blank squares.
The usage scenarios are as follows:

**Scenario 1:** Player clicks empty square.

**Conversation:**

1. User clicks square.

2. System displays player's symbol.

3. System checks whether the game is over. If it is, it displays an appropriate notification and resets the board; if it is not, it changes current player from X to O or vice versa.

**Scenario 2:** Player clicks square that already contains a symbol.

**Conversation:**

1. User clicks square.

2. System displays a warning asking the player to click and empty square.

**Scenario 3:** Player clicks *Reset*.

**Conversation:**

1. User clicks *Reset*.

2. System erases all squares.

3. System resets player symbol to X.

## Design

The problem is simple and we can design the solution without going into much detail. The domain objects consist of players and the grid. The only thing the program needs to know about the players is who is the current player (X or O) and this requires only a *String* object. The only other required class is the *application model*.

All in all, we don't need any domain classes and the only necessary information is instance variable *player* holding the string identifying the current player. Our program will thus consist of a single class, an *application model* class called *TicTacToe*, a subclass of *ApplicationModel*. Its behaviors will be as follows:
* initialization - initialize player to 'X'

* actions - respond to activation of board squares and the *Reset* button

* private - check for end of game, toggle players after a move

## Implementation

We will implement the squares as action buttons with blanks, Xs or Os as labels. We will need to change button labels at run time as the players click them, and to do this, we need run time access to them. This access can be gained via the builder which holds a dictionary of all *named widgets* (widgets assigned IDs with the Properties Tool) which associates widget IDs and the corresponding value holders. To make a widget accessible fill in its ID property; to access it, ask the builder to locate this component via its ID. As an example, if we assigned the upper left action button the ID `button1`, we can access it at run time by

`builder componentAt: #button1`

To assign IDs, use the *ID* field in the Properties Tool as in Figure 6.29. Any widget may have an ID.

<figure><img src="image_138.png" /><figcaption>Figure 6.29. Assigning an ID to a widget so that it can be accessed at run time.</figcaption></figure>

Now that we know how to access a widget, how can we access its label? First of all, the component accessed by the builder is not really the widget but a *wrapper* object containing the widget. To get the widget, send the widget message to the wrapper. After this, ask the widget for its label, and then access the label's text. Altogether, to get a widget's label, execute

`(aBuilder componentAt: #button1) widget label text "Get text of label of button1."`

To change the text of the label, use message `labelString`:

We are now ready to start implementing the program. First, paint the canvas and name the button IDs `#button1`, `#button2`, and so on. Since the window should open with empty squares, the *String* assigned to button labels in the Properties Tool will be empty (Figure 6.29). When the user clicks `button1`, its *Action* method will check whether the label is an empty string and respond as follows:

`button1`
"Button was clicked. Check if it is already labeled and respond appropriately."

self builder componentAt: #button1 widget label text empty

ifTrue: ["Get component, change its label, exit if game is over, switch players."

self builder componentAt: #button1 widget label labelString: player.

self endOfGame ifTrue: [^Dialog warn: 'Game over.'].

self newPlayer]

ifFalse: [Dialog warn: 'This field is already occupied']

This works but repeating expression

self builder componentAt: #button1 widget

is ugly. Moreover, it will have to be accessed again in the reset *Action* method and we thus decide to
evaluate the expression once for all during initialization and save (cache) the result in an instance variable
as

button1 := self builder componentAt: #button1 widget

Assuming that this has been done, the definition becomes

### button1

"Button was clicked. Check if it is already labeled and respond appropriately."

button1 text empty

ifTrue: [button1 text: player.

self endOfGame ifTrue: [^self].

self newPlayer]

ifFalse: [Dialog warn: 'This field is already occupied']

This definition must be repeated with minor variations for each button and this is not very nice. We
will give a better solution at the end of this section.

The next question is where to put the assignment to button1 and the variables corresponding to the
other buttons. Clearly, it must be before the application opens, in one of the hook methods. It cannot be
done in initialize because the builder does not yet exist, it cannot be done in preBuildWith: because the
builder has not yet processed widget properties and does not have the ID dictionary. We will thus do it in
postBuildWith: as follows:

### postBuildWith: aBuilder

"Cache button labels for easy access in Action methods."

button1 := (aBuilder componentAt: #button1) widget label.

button2 := (aBuilder componentAt: #button2) widget label.

button3 := (aBuilder componentAt: #button3) widget label.

button4 := (aBuilder componentAt: #button4) widget label.

button5 := (aBuilder componentAt: #button5) widget label.

button6 := (aBuilder componentAt: #button6) widget label.

button7 := (aBuilder componentAt: #button7) widget label.

button8 := (aBuilder componentAt: #button8) widget label.

button9 := (aBuilder componentAt: #button9) widget label.

As the next step, we will implement endOfGame which checks for end of game. Our
implementation will be very straightforward - we will simply check whether any of the rows, columns, or
diagonals are filled with copies of the current player's symbol, and return the *or* of this combination. The
definition is as follows:

### endOfGame

"Check all rows and columns and diagonals for end of game. Return true or false."

| end |

end := ((self isPlayer: button1) & (self isPlayer: button2) & (self isPlayer: button3)) |

((self isPlayer: button4) & (self isPlayer: button5) & (self isPlayer: button6)) |

((self isPlayer: button7) & (self isPlayer: button8) & (self isPlayer: button9)) |
((self isPlayer: button1) & (self isPlayer: button4) & (self isPlayer: button7)) |
((self isPlayer: button2) & (self isPlayer: button5) & (self isPlayer: button8)) |
((self isPlayer: button3) & (self isPlayer: button6) & (self isPlayer: button9)) |
((self isPlayer: button1) & (self isPlayer: button5) & (self isPlayer: button9)) |
((self isPlayer: button3) & (self isPlayer: button5) & (self isPlayer: button7)).
end ifTrue: [self reset. Dialog warn: 'Player ', player, ' wins. Game over.'].
^end

where we used fully evaluating logic because it is more readable and because evaluation speed is irrelevant
in this case. Method isPlayer: aButton checks whether aButton's symbol is equal to the player's symbol as
follows:

isPlayer: button

"Is the symbol displayed in button the same as the player's symbol?"

^button label text = player asText

where we had to convert the player string because a label's text is a Text object which is somewhat different
from a string and cannot be directly compared with it. We will learn about Text later.

Finally, method newPlayer toggles the player:

newPlayer

"Update player."

player = 'X'
ifTrue: [player := 'O']
ifFalse: [player := 'X']

Finally, the reset method. It resets all button labels and initializes player to 'X':

reset

"Reset button and reinitialize the player."

button1 labelString: "".
button2 labelString: "".
button3 labelString: "".
button4 labelString: "".
button5 labelString: "".
button6 labelString: "".
button7 labelString: "".
button8 labelString: "".
button9 labelString: "".
player := 'X'

Improving button methods

When we wrote the button1 method, we noted that it is repeated with very minor variations for all
buttons and this is ugly. Besides, if we decide to make any changes, we will have to repeat them in all nine
methods. We will thus change all button methods to the following style

button1

self doButton: (builder componentAt: #button1)

and put all the shared code in

doButton: aButton

"Game button aButton has been clicked. Check if the button is already in use and if not, change its label, check for end of game, and switch players if not done."

aButton widget label text empty

ifTrue:
    [aButton widget labelString: player.
self endOfGame ifTrue: [^self].
self newPlayer]
ifFalse: [Dialog warn: 'This field is already occupied']

Note that as we are changing the state of the object assigned to variables button1, button2, etc., we don't have to make any changes to the variables themselves – they keep pointing to ‘the same’ object whose properties have changed via doButton:.

You might argue that method reset has a similar problem as our button methods – it seems unnecessarily repetitive and it should be possible to simplify it. We will see in Chapter 7 that this can indeed be done.

## Main lessons learned:

* If you want to be able to refer to a widget at run time, assign it an ID property and use the builder to access it via componentAt: message.

* A widget in a running application is enclosed in a wrapper. To access the widget, send widget to the component.

## Exercises

1. Complete and test the implementation of class TicTacToe.

2. Our implementation of endOfGame ignores the possibility that the game ends in a draw. Correct this shortcoming.

3. Improve TicTacToe by adding a button to display the score of the two players in a notifier window.

4. Formulate a strategy for the computer to be one of the players. The strategy may be very simple such as choosing a square randomly, or more sophisticated.

5. Open TicTacToe in step-by-step mode and inspect the builder. List the contents of its namedComponents dictionary.

6. Our application can be implemented more neatly by defining domain model class GameBoard implementing all the functionality except the user interface, and implementing the GUI by a simplified version of TicTacToe with no domain behavior. Reimplement the program along these lines.

## Conclusion

This chapter introduced development of applications with graphical user interfaces. VisualWorks' application architecture has three components: the graphical user interface (GUI), the application model, and the domain model. The role of the GUI is to display results and provide means of interaction between the user and the computer. The domain model is a collection of classes representing objects in the problem world. The application model provides the link between the GUI and the domain model, converting user actions into messages to domain objects, and changes in domain objects to messages to the user interface. Most applications contain all three parts but very simple applications combine the domain model and the application model in one class. Occasionally, an application does not have a GUI and does not require an application model either. Such applications are called ‘headless’.

To minimize the effort required to create an application, VisualWorks provides a library of GUI components, class ApplicationModel containing shared properties of application models, and tools for interactive creation of the user interface with minimal programming. To take full advantage of the built-in functionality, application models must be subclasses of ApplicationModel.

VisualWorks UI development environment is based on three tools: a canvas (the future window), a Palette of widget buttons, and a Canvas Tool. To create a user interface, the programmer selects widgets on the palette, paints them on the canvas, and defines their properties such as labels, colors, and actions using the Properties Tool.

During the process of creating a user interface, the programmer installs the GUI on the application model which stores a description of the GUI in a class method of the application model. The *Define* command of the Canvas Tool defines aspect variables and stubs of *Action* and *Aspect* methods.
The principle of updating value holding widgets is dependence between the value objects and the widgets themselves. This dependence is achieved by storing the values in instances of *ValueHolder* whose instances provide a uniform interface to their value components and implement dependency. When the value of a *ValueHolder* is changed with the *value* message, the *ValueHolder* notifies its dependents and they respond by executing their predefined behavior. A Text Editor widget, for example, responds by using its *Aspect* message to request text from the application model and by redisplaying itself with the new text.

When an application model class receives the *open* message, it executes a series of messages including the building of the user interface by a *UIBuilder* object and the opening of the window from this 'built' before it transfers control to the user interface. The opening sequence includes several hooks - do-nothing messages defined in *ApplicationModel* to allow the programmer to insert any appropriate actions into the application opening process.

Any widget can be assigned an ID and this ID can be used to access the widget at run time for effects such as changes of labels and other effects.

The basis of VisualWorks graphical user interfaces is the MVC paradigm in which an object holding data (the model) is displayed by a view and the user interface is implemented by a controller. Class *View* defines several mechanisms for keeping views up to date, and new view classes created for new GUI components should thus be subclassed to *View*.

The controller part of MVC is responsible for mouse- and keyboard-based user interaction within the view's area. The preferred method for propagating model changes to the view is via *dependency* where each significant change of the model notifies all model's dependents. In the MVC triad, the dependent is the view.

As a side product of developing our example applications, we introduced the very important concept of the pseudo-variable *super*. The purpose of *super* is to provide access to a higher level definition of a method, usually to avoid recursion in a new method with the same name. Pseudo-variable *super* does not represent an object and cannot be used by itself. It must always be used as a receiver of a message.

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

*ApplicationModel*, *SimpleHelp*, *UIBuilder*, *ValueHolder*.

## Terms introduced in this chapter

*active widget* - a widget capable of interaction with the user

*application model* - object linking user interface and domain model; subclassed from *ApplicationModel*

*Action button* - UI button that executes a predefined action when clicked

*Action method* - action button property; method defined in application model and invoked when user clicks the button

*Aspect method* - widget property; application model method used to access the value of the widget's value holder

*Aspect variable* - application model variable bound to a *ValueHolder* holding the model of a widget

*builder* - instance of *UIBuilder*, part of VisualWorks framework which constructs the user interface before a window opens, and provides access to UI components during execution

*canvas* - blueprint of a future window on which widgets are painted during user interface design

*Canvas Tool* - window providing access to commands during the construction of the user interface

*controller* - the object responsible for dealing with user input in an MVC triad

*Define Tool* - tool for automatic definition of *Action* and *Aspect* methods and aspect variables

*dependency* - model ↔ dependent relationship in which the model automatically notifies its dependents of its changes

*domain model* - collection of classes representing objects in the problem domain
**graphical user interface (GUI)** - interface between an application and its human user implemented with
windows and widgets

GUI - graphical user interface

hook - method built into a process such as application opening or closing to allow developers to insert
application-specific actions into the process

input event - operation such as pressing a key on the keyboard, moving the mouse, or clicking a mouse button

Install - UI Painter command; defines the application model class if it does not exist and stores the GUI description in a user-specified class method

lazy initialization - leaving initialization of an instance variable until the time when its value is requested

MVC paradigm - model - view - controller - the three parts of VisualWorks user interfaces responsible for the data, its display, and user interaction respectively

model - the controlling part of the model ↔ dependent relationship

model↔dependent relationship - see dependency

passive widget - a widget that does not allow user interaction

Properties Tool - tool allowing specification of window and widget properties such as labels, names of
Action and Aspect methods, colors, and so on

pseudo-variable - identifier whose meaning depends on the context but whose value cannot be changed by assignment; self and super are pseudo-variables

super – pseudo-variable providing access to a higher level definition of a method

Text Editor - active GUI widget displaying text and allowing user input

UI builder - user interface builder - see *builder*

UI Painter - interactive tool for GUI development with minimal programming

value holder - instance of ValueHolder, an object holding a value and a list of dependents; used as model in
the model ↔ dependent relationships

view - the object responsible for displaying the model in the MVC triad

widget - a passive or active GUI component such as an Action Button, a Label, or a List
# Chapter 7 - Introduction to Collections

## Overview

Catalogs, inventories, dictionaries, lists of popup menu commands, items in a shopping cart - all these are examples of the fact that objects almost always occur in groups. Because collections of objects are so essential and varied, the Smalltalk library contains many collection classes and numerous useful methods for manipulating them.

In this chapter, we will survey the general properties of the collection class hierarchy and explore arrays, the basic kind of 'ordered' collections whose elements are stored in a fixed order and accessible by an index. We will also examine some extensions of the concept of an array, and the table widget as its application. The remaining collections will be covered in the following chapters.

The last section of this chapter introduces a new GUI widget - the Table. We encourage you to complement this material by reading Appendix 1 which contains a description of additional widgets, explains in more detail how widgets work, and includes several interesting examples.

## 7.1. Introduction

Although the world consists of individual objects, objects most often occur in groups. Some examples are bicycles standing in a school yard, a sequence of pages in a book, cars following one another on a highway, customers lined up in a bank, a bag of items bought in a store, a team of hockey players, and the seats in an auditorium.

Given this reality, it is not surprising that most programming problems objects also deal with collections of objects. As an example, the text on a page is a string of letters, digits, and punctuation symbols. List widgets, pop up menus, drop down menus, tables, and other user interface components also display collections of items. Other examples include an airport display of flight departures, an inventory program managing a collection of inventory items, and a course-marking program managing a collection of student records, themselves collections of marks and other information. Finally, a computerized encyclopedia provides access to a collection of keywords and their definitions. Several of these examples show that the elements of some collections are themselves collections and it thus makes perfect sense to treat collections themselves as objects.

A closer look shows that collections come in a variety of forms (Figure 7.1):

* Each player on a hockey team has a unique number and the number of players on the team is fixed. We could line the players up in the order of their numbers and we could refer to each by his or her number. If the numbers were consecutive integers, we could put the players into consecutive numbered slots and access them by these numbers. A line up of swimmers on starting blocks is an even better illustration of this kind of collection. In the programming context, this kind of collection is called an *array* and its characteristics are that it has a fixed size and its elements can be accessed by an integer 'index'.

* Cars on a parking lot can also be associated with numbers. The area could be divided into rows and columns, consecutive rows and columns assigned numbers, and each car identified by its row and column numbers. This collection of slots and their contents (cars) is again an array because it has a fixed size and can be accessed by a 'key', but it has two dimensions - rows and columns. A parking lot is an example of a *two-dimensional array*.

* Cars on a highway are a different kind of collection because their number constantly changes as cars arrive on the highway and leave it through exits. In Smalltalk, this kind of collection is called an *ordered collection* and its characteristics are that the number of elements in an ordered collection can change and that the contents are ordered: Assuming a one-lane highway, the cars follow one another. In principle, we can again access the cars by an index but since new cars are added all the time at one end, and leave at the other end, this is not the most natural way to refer to the elements of an ordered collection. The first, the last, and the next or the previous element are usually more important concepts.
* An encyclopedia is yet another kind of collection because its elements themselves have a structure - each consists of a keyword and a value (such as the definition of a word). This kind of collection occurs so often that Smalltalk treats it as a special kind of collection called a *dictionary*. Elements of dictionaries are usually accessed by their key as in 'what does the word *xenophobia* mean?'

* The structure of a collection of items in a shopping bag is very different from the previous examples because its contents are *not* ordered. In Smalltalk, this kind of collection is rather predictably called a *bag*. An interesting property of the shopping bag example is that each item in the bag often is of a different kind such as tooth paste, apple juice, and melon. In fact, most Smalltalk collections allow their elements to be arbitrary objects.

How are the elements in a bag accessed? Some people just throw them in the bag to settle wherever there is place for them, and when you pull them out without looking, they come out in an unpredictable order.

<figure><img src="image_139.png" /><figcaption>Figure 7.1. Collections may have different structures.</figcaption></figure>

Our programming examples illustrate that collections come in various forms:

* A text stored in a document is a string of letters, digits, and punctuation symbols, in other words an ordered collection of characters.

* List widgets display one string on each line and since strings are ordered collections, a list widget is an ordered collection of ordered collections!

* The contents of a display of flight departures at an airport is an ordered collection of flight descriptions, and flight descriptions themselves are complicated objects with many components such as flight number, flight destination, departure time, and so on. In fact, since flight descriptions are arranged by their departure times, it is better to think of them as *sorted* rather than ordered collections: A *sorted collection* is just like an ordered collection, but its elements are sorted on the basis of some calculation. In our case, the calculation is comparison of departure times.

It is interesting to note that the nature of individual items in the display of departing flights can be interpreted in two ways: One is to view the individual items of the flight display (flight number, flight destination, departure time, and so on) as items of a 'flight object' collection. On the other hand, components of flight items are accessed by name as in 'what is your flight number?' or 'what is your departure time?' and it thus seems more natural to treat each flight item as an instance of a 'flight information' object. The second interpretation seems more convenient because if we treat flight information
as a collection, its elements are nameless and we can only ask questions such as 'what is the value of the third element of the flight information collection' - when we mean 'what is the departure time?'. This shows that the decision whether to treat a complex object as a collection or an instance of a special kind of object may not be obvious until we start thinking about how we want to use this object.

We have just seen that one distinction between a collection and a composite object is that collection elements are accessed anonymously whereas elements of composite objects are accessed by a name. Another distinction between a collection object and a composite object is that a collection can have any number of components but an object consisting of a fixed number of named components can only have the predetermined fixed number of components. As an example, the number of cars on a highway depends on the current situation. Even the number of slots in a parking lot is arbitrary because a parking lot can be designed any size or shape we want. A flight object treated as an instance of a composite object Flight, on the other hand, may only have a flightNumber component, a FlightDestination component, and a DepartureTime component if this is how the object Flight is defined.

The fact that collection elements are not named has the advantage that they can be accessed more easily. As an example, it is easy to describe how to calculate the total price of all elements in the shopping bag: 'Take the elements in the bag one after another and add their prices.' This procedure will work whether the bag contains one element or 100 elements, and whether the items are oranges, dishwasher liquid bottles, soap, or anything else. Similarly, counting all trucks in a satellite snapshot of a highway can be described: 'Start with the first element and count one element after another until you reach the last element.'

In the case of a composite object with named components, enumeration (execution of the same operation on each component) is more complicated and requires explicit naming. Assume, as an example, that we refer to the 11 players on a soccer team as goalie, leftDefence, rightDefence, and so on. If we wanted to calculate the average weight of all players on the team, we would have to calculate

averageWeight := (goalie weight + leftDefence weight + etc.) / 11

naming each player explicitly. If we put player information into an array, the solution is simply

averageWeight := (sum of weights of elements 1 to 11) / 11

The obvious need for collections, their open nature, and the generality of enumeration over collections are their essential advantages that make them members of the family of essential Smalltalk classes.

## Main lessons learned:

* Objects usually occur in groups. In Smalltalk, such groups are called collections.

* Careful examination shows that different situations require different kinds of collections such as ordered or unordered and fixed or variable sized.

* Performing the same operation on each element of a collection is called enumeration. Enumeration is one of the most important operations on collections.

* Smalltalk objects can be divided in two categories - those that contain zero or more named objects, and those that contain a variable number of nameless objects. Collection items are nameless and this has two major advantages:

* A collection may contain any number of elements whereas an object with named components contains only the named components.

* It is much easier to enumerate over unnamed elements of a collection than over named instance variables of a multi-component object.

* Collections belong to the most important programming concepts.
## Exercises

1. What kind of collection or named object is most natural for the following situations:

a. Customers waiting in a bank queue.

b. Filing cabinet drawer with alphabetically arranged current student files.

c. Book information including author, title, and catalog number.

d. Filing cabinet drawer with files of students who graduated last year.

e. Description of all trees in the city of Halifax.

f. A list of all rooms on one floor in a student residence.

g. Student information including first name, last name, home address, home phone number, local address, local phone number, year of first registration, courses taken each past year, courses being taken this year, major area of study, previous degrees, participation in coop program.

h. A list of rooms in one residence building.

i. Bank account containing customer name, address, telephone number, and a list of accounts.

j. A chess board.

k. A list of 'print jobs' waiting to be printed on a shared printer.

2. What is the nature of the components of the collections and composite objects in Exercise 1?

## 7.2 Essential collections

Since collections are so useful and their applications so varied, the Smalltalk library contains more than 70 predefined collection classes. Some of them are abstract because different kinds of collections share many properties, but most are concrete. In the library, collections are divided into nine categories according to their abstractness, distinguishing characteristics, and uses. Many collection classes support the Smalltalk environment itself, but others are intended for general use. In the rest of this section, we will identify the essential collections (Figure 7.2) and give a brief overview of each.

<figure><img src="image_140.png" /><figcaption>Figure 7.2. The most commonly used classes of the Collection hierarchy. Classes that will be covered in more detail are **boldfaced**, abstract classes are **italicized**.</figcaption></figure>

Collections can be classified according to several criteria. One of them is whether their elements can be accessed by a key or not. A very important part of this group can access its elements by an integer number corresponding to the position of the element in the collection. These collections are called *sequenceable* and are implemented on a special branch of the class tree (Figure 7.2). Many of the collections whose elements are accessed by a non-integer key share the abstract class *KeyedCollection* as
their superclass and their branch is separate from sequenceable collections. These classes, however, are used mainly in Smalltalk implementation rather than general applications. Ironically, the most frequently used members of the family of collections accessed by a non-integer key (various kinds of dictionaries) is completely separate, and resides on the branch of classes that are not accessible by a key at all. This is because of the way they are implemented and because of the limitations of single inheritance.

Some collections (such as bags and sets) cannot be accessed by a key and Smalltalk calls them unordered. Although their elements are internally stored in consecutive memory locations, this internal arrangement is hidden from the user.

Another distinguishing feature of collections is that some collections have a *fixed size* which is established when the collection is created, and other collections can grow. Most Smalltalk collections automatically grow when they need more room to accommodate a new element.

Another distinction is that some collections allow *duplicates* whereas other collections throw duplicates away and keep just one copy of each element.

Finally, some sequenceable collections are *sorted* according to a predefined sorting function whereas other sequenceable collections are arranged according to the order in which the elements are added. In some sequenceable collections, the absolute position of an element may change when a new element is added or when an existing element is deleted, in other collections the position of an element never changes.

After this general overview, we will now review the main concrete collections before examining each of them in more detail later.

**Arrays** have fixed size determined by their creation message which has the form 'create an array of size n'. Their elements are ordered in sequence and accessed by an integer index. The index of the first element is always 1 (some other languages start at 0) and the following elements have consecutive indexes; as an example, elements of an array with five elements are numbered 1, 2, 3, 4, and 5. Once an object is assigned to a position, its position never changes unless this is explicitly requested by the program. Elements of Smalltalk arrays and most other collections may be any objects, and even a heterogeneous collection of objects of different kinds is acceptable. Because arrays have a fixed size, they are used when we know exactly how many elements the collection will have. Their advantage is that their accessing is very efficient and that they are often easier to create and initialize than other types of collections.

**Ordered collections** are also sequenceable which means that their elements are also ordered in a sequence and indexed. Unlike arrays, however, ordered collections have a built-in mechanism for growing. Also, ordered collections often add elements at the beginning and this changes the index of elements already in the collection. Programs using ordered collections in this way thus cannot use the index of an element to access it. The price for the flexibility of ordered collections is that some operations on them are not as efficient as operations on arrays. Automatic growing, in particular, which occurs when the currently allocated size becomes too small, is time-consuming. Ordered collections are used when we need to collect objects whose total number is variable or initially unknown and when the order in which they are received matters as when we simulate a queue of customers in a bank.

**Sorted collections** are a special kind of ordered collections that insert new elements into a position determined by some sorting function, typically comparison by magnitude. For greater flexibility, the sorting function can be specified or changed by the program. The ability to sort is very valuable but its price is that inserting a new element may require considerable processing.

**Lists** are a relatively recent addition to VisualWorks library and according to the manual, they are intended to supersede ordered and sorted collections. In essence, lists are ordered collections that understand sorting messages and implement the concept of dependency which makes them useful as item holders for widgets such as list views. This is, in fact, the main use of lists.

**Two-dimensional lists** are a variation on lists and arrays. Like arrays, they have fixed size and their elements are accessed by index or rather a pair of indices, one for row and one for column. They are used to support table widgets because they implement dependency.

**Strings** are indexed sequences of characters with no information about how they should be displayed. We have already seen that strings are among the most frequently used Smalltalk objects.

**Text** is an object combining the concept of a string with information about its rendering - the font, style, size, and color in which the string will be displayed on the screen or printed.
Whereas the collections listed above are all sequenceable, the following collections are unordered. We have already explained that this means that although their elements are internally stored in a sequence, the order is determined by the implementation rather than by the accessing message and is hidden from the user.

**Sets** are unordered collections that don't allow duplication. In other words, if you add an element that is already in the set, the set does not change. This property makes it possible to weed out duplicates from an existing collection simply by converting it to a set.

**Bags** are unordered just like sets but they keep a tally of the number of occurrences of their elements. If the same element is inserted into a bag five times, for example, the bag knows that its number of occurrences. When an element is removed, its count is decremented by 1 and when the count reaches zero, the element is removed. In contrast, if you remove an element from a set, it is gone, no matter how many times it has been added before.

**Dictionaries** are collections in which values are accessed by a **key**. The **key** may be any object and if we used integers for keys, we would essentially obtain ordered collections, Dictionaries are therefore conceptually generalized ordered collections. In terms of implementation, however, dictionaries are implemented as a subclass of **Set**. In practice, elements of dictionaries are usually **Association** objects, **key-value** pairs similar to entries in a dictionary or an encyclopedia. Being sets, dictionaries eliminate duplication using keys to perform the comparison. This means that adding an association whose **key** is already in the dictionary replaces the original association. Because the structure of dictionaries is different from the structure of other collections (by relying on **key** and **value** access), dictionaries provide a number of specialized messages.

**IdentitySet** and **IdentityDictionary** are important subclasses of **Set** and **Dictionary** that use `==` instead of `=`, to eliminate duplication.

### Main lessons learned:

* VisualWorks contains many collection classes, some for system needs but many for general use.

* The main differences between collections are whether their size is fixed or not, whether they allow duplication of elements, whether they can be accessed by a **key**, and whether their elements are ordered and how this ordering is achieved.

* Collections most useful for general use are arrays, ordered and sorted collections, lists, strings, text, symbols, sets, bags, and dictionaries.

### Exercises

1. Find the number of library references to `Array`, `OrderedCollection`, `SortedCollection`, `List`, `Set`, `Bag`, and `Dictionary`.

2. All classes understand message `allInstances` which returns an array with all currently existing instances of the class. As an example, `Bag allInstances` returns all instances of active instances of `Bag` currently in the system. Use this message to find the number of instances of `Array`, `OrderedCollection`, `SortedCollection`, `List`, `Set`, `Bag`, `Dictionary`. The number, of course, depends on the current state of your session.

3. Extend the previous exercise by calculating the smallest, largest, and average size of collection instances.

4. For each of the concrete collection classes listed in this section, give an example of one situation in which the collection would be appropriate.
### 7.3 Properties shared by all collections

Before presenting individual collection classes in detail, we will now survey their most important shared characteristics, most of them defined in the abstract class Collection. They include protocols for creating collections, adding and deleting elements, accessing them, converting one kind of collection into another, and enumeration.

#### Creation of new collections (class methods)

The most common messages for creating collections are new or new:. Both are inherited from class Behavior which defines most of the shared functionality of all class methods across Smalltalk library. The typical uses of new and new: are as follows:

<table><tr><td>Array new: 20</td><td>“Creates an instance of Array with 20 uninitialized elements.”</td></tr><tr><td>Set new</td><td>“Creates a Set object with room for a default number of elements (2).”</td></tr></table>

To create a collection with only a few initially known elements, use one of the with: creation messages as in:

<table><tr><td>Array with: 4 factorial</td><td>“Creates an Array with the single element 4 factorial.”</td></tr><tr><td>Array with: students with: teachers</td><td>“Creates a two-element Array with the specified elements.”</td></tr></table>

Predefined with: messages have up to four keywords (with:with:with:with: is the last one) but you can easily define your own with: messages with more keywords if you wish.

Another useful creation message is withAll: aCollection which creates a new collection and initializes it to all elements of aCollection. As an example,

OrderedCollection withAll: anArray

creates an OrderedCollection containing all elements of anArray. Object anArray is not affected.

Several collection classes have their own specialized creation messages in addition to the ones listed above. Moreover, arrays have the distinction that they can be created as literal arrays without any creation message. As an example,

(34 43 78 -22)

creates a four-element array containing the four specified numbers. We will say more about this later. Collections are also often created by converting existing collections as explained next.

#### Converting one kind of collection to another (instance methods)

Almost any kind of collection can be converted into almost any other collection. The process creates a new collection containing the elements of the original collection but the original is not changed. As we have already seen, conversion messages generally begin with the word as.

Conversion is sometimes used just to perform some operation on the receiver. As an example, if anArray contains some numbers and we want to sort them, message

aSortedCollection: = #(34 43 78 -22) asSortedCollection

creates a SortedCollection and fills it with the elements of anArray sorted in ascending order of magnitude. When you execute

| anArray aSortedCollection |
anArray := #(32 96 -34 89 32 45).
aSortedCollection := anArray asSortedCollection
you will get SortedCollection (-34 32 32 45 89 96) and anArray remains changed. (This is a very important property of all conversion messages that is frequently overlooked, causing problems that may be difficult to trace.)

To convert the result back to an array, we could use

anArray := anArray asSortedCollection asArray. "Sort and convert back to Array."

The combination of the asSortedCollection and asArray thus sorts the array. Another frequently used conversion message is asSet, as in

aCollection asSet

which creates a Set with elements from aCollection and removes all duplicates. The receiver is not affected.

anArray := anArray asSet asArray

removes all duplicates from anArray and stores them in some unpredictable order in a new array.

Another reason for performing conversion is that some operation require a collection of a kind different from the receiver's class. As an example, a popup menu expects its labels to be supplied in an sequenceable collection. If the labels are, for example, in the form of a Set, we must convert them as in

listOfLabels := aSet asArray

### Accessing (instance methods)

One of the main distinctions between different collection classes is how their elements are accessed and so Collection leaves accessing of individual elements to concrete collection classes. Its own accessing protocol is limited to *size* and *capacity* corresponding, respectively, to the number of elements present in the collection, and the space available in the collection.

aCollection capacity

returns the number of slots available in aCollection for 'storing' its elements. Note that if the capacity of a collection is 5, the collection does not necessarily contain five elements; this only means that in its present state, the collection has room for five elements (Figure 7.3).

<figure><img src="image_141.png" /><figcaption>Figure 7.3. A collection with capacity 5 and size 3.</figcaption></figure>

The reason why we put 'storing' in quotes is to emphasize that collections don't really store their elements. In other words, the representation of a collection object in computer memory does not contain the representation of its elements. It only contains references to these objects, pointers to their binary representations - essentially their memory addresses - and each slot is thus only big enough to store a pointer to the corresponding element. This has two important consequences. One is that collections as such require relatively little memory space, and the other is that two or more different collections can share elements. This should not surprise you because all Smalltalk objects, not just collections, access their components via pointers. This principle is, however, worth repeating because the potentially large number of elements of collections might lead one to think that collections must occupy a lot of memory space. They don't - but their elements might. We will ignore this technical detail in the future and generally say that a
collection 'contains' or 'stores' its elements and depict collections as if they contained their elements although this is not literally true.
The complement of capacity, the size message, as in

aCollection size

tells us how many slots of aCollection actually contain pointers to objects, in other words, how many
elements the collection really 'has'. For arrays, capacity and size are always the same; for most other
collections, capacity and size are different concepts.

Enumeration - doing something with all elements in a collection (instance methods)

One of the most common operations on collections is executing one or more statements with each of its elements. As an example, one might want to print each element in the Transcript, or calculate the square of each element. This is called iteration or enumeration. The most common enumeration messages are illustrated by the following examples in which the block argument is applied to each element of the receiver collection:

| aCollection selections rejections squares sum product|

aCollection := #(
13 7 89 11 76 4 65 32
).

aCollection do: [:element| Transcript cr; show: element printString].

selections := aCollection select: [:element| element > 45]. "Collection of all elements > 45."

rejections := aCollection reject: [:element| element > 45]. "Collection of all elements not > 45."

squares := aCollection collect: [:element| element squared]. "Collection of all element squares."

sum := aCollection inject: 0 into: [:element:tempSum| tempSum + element]. "Sum of all elements."

product := aCollection inject: 1 into: [:element:tempProd| tempProd * element] "Product of all elements."

The do: message executes the block for each element of the receiver. In our example, it displays each element of aCollection in the Transcript. Receiver aCollection is not affected in any way. Message do: is the most important enumeration message and can be used to implement all other types of enumeration. In fact, message do: is the only enumeration message which is left as subclass responsibility and all others are fully defined on the basis of do: in class Collection (some are redefined in a few subclasses). In spite of the power of do:, experienced Smalltalk programmers always use the specialized messages below when appropriate to avoid unnecessary work and possible errors involved in re-inventing the operation.

The next three enumeration messages all *create a new collection* without changing the receiver. As a result, if you don't save the result in a variable or reuse it immediately, the result is immediately lost.

Message select: creates a new collection containing only those elements that satisfy the block, in other words, those elements for which the block evaluates to true (Figure 7.4).

<figure><img src="image_142.png" /><figcaption>Figure 7.4. aNewCollection := aCollection select: [:element| element > 45].</figcaption></figure>

In our example, the result of the simple test is a new collection containing only those elements of
aCollection that are greater than 45. The tests can be much more complex, as long as the block returns true
or false for each element, and the whole expression fails if even one element of aCollection cannot execute
the block. This is, of course, true for all enumeration messages.
**Message reject:** is the opposite of **select:** - it rejects all elements that evaluate the block to true and puts the remaining elements into a new collection. In our case, the new collection will contain all elements of a collection that are not greater than 45, in other words, all elements smaller or equal to 45.

**Message collect:** creates a new collection whose size is identical to that of the receiver and whose elements are the objects returned by evaluating the block. In our case,

```
squares := aCollection collect: [:element| element squared]
```

calculates a collection of squares of the original numbers and assigns it to `squares`.

**The inject:into: message** uses a block with two arguments. The first argument enumerates over all elements of the collection, the second is the initial value of some calculation performed by the block. In general, the expression in the block takes the element (the first argument) and updates the value of the intermediate result (the second argument). The message returns the last value of the second argument.

**Message inject:into:** is very powerful but not used much by beginners, perhaps because it is not so easy to understand as other enumerations and because of confusion over which argument is which. To help with the second problem, we suggest that you remember that the first argument is the receiver's element – and if you read the expression from left to right, the receiver comes first too.

All enumeration messages that create collections, including `collect:`, `select:`, and `reject:`, create a collection of the same species as the receiver. In most cases, the species of a class is the class itself (the species of `Array` is `OrderedCollection`, the species of `OrderedCollection` is `OrderedCollection`, and so on) because most classes inherit the following definition of species defined in `Object`:

### species

"Answer the preferred class for reconstructing the receiver. Species and class are not always the same."

`^self class`

In a few classes, the most suitable result is not of the same kind as the receiver and species is then redefined, returning a class different from the class of the receiver.

The handling of species is typical for dealing with messages that behave identically for almost all classes with a few exceptions. Such methods are usually defined in class `Object` or a suitable superclass in a way that reflects the predominant behavior, and inherited. The few classes that require different behavior override the inherited definition.

The definition of enumeration methods is a classical example of the use of inheritance. All of them are defined in terms of `do:` and only `do:` is left to subclasses - as noted prominently in `Collection's` comment. As an example, the definition of `collect:` in `Collection` is as follows:

### collect: aBlock

"Evaluate aBlock with each of the values of the receiver as the argument. Collect the resulting values into a collection that is like the receiver. Answer the new collection."

```
| newCollection |
newCollection := self species new.
self do: [:each | newCollection add: (aBlock value: each)].
^newCollection
```

Inheriting this definition by all collections, provides a great saving and consistency, and only a few classes redefine `collect:` because their internal structure allows them to perform it more efficiently.

### Testing (instance methods)

The testing protocol of collections allows checking whether a collection contains objects satisfying a block, specific objects, or any objects at all. It includes the following messages:
<table><tr><td>aCollection empty</td><td>"Returns true or false."</td></tr><tr><td>aCollection includes: 'Air Canada'</td><td>"Returns true or false."</td></tr><tr><td>aCollection contains: [:element| element > 7]</td><td>"Returns true or false."</td></tr><tr><td>aCollection occurrencesOf: 'abc'</td><td>"Returns an integer number."</td></tr></table>

As an example of the implementation of these messages, the definition of empty is simply

### isEmpty

`^self size = 0`

Message includes: returns true if at least one of the elements of aCollection is equal to the string 'Air Canada'; it returns false otherwise.

Message contains: returns true if at least one element of aCollection satisfies the *block argument*; it returns false otherwise. Just as in enumeration, it is important to remember that during its execution, contains: may have to execute the block argument for each element of aCollection. Consequently, if even a single element of the collection cannot execute the block, the message may fail. As an example, if all but one of the elements of aCollection in our example are numbers, the message may generate an error because a string cannot compare itself with a number. Ignoring this principle is another common programming mistake.

Finally, occurrencesOf: counts how many occurrences of the collection are equal to the argument. Its definition uses do: as follows:

### occurrencesOf: anObject

"Answer how many of the receiver's elements are equal to anObject."

```
| tally |
tally := 0.
self do: [:each | anObject = each ifTrue: [tally := tally + 1]].
^tally
```

## Adding elements (instance methods)

If a collection can grow - and most collections can - it understands messages add: and addAll:.

Message add: anObject adds anObject in a way consistent with the nature of the collection (ordered or unordered) and 'grows' the collection by increasing its capacity if necessary. Growing can be a very time-consuming because it first creates a new larger collection, and then copies all elements of the original collection into it. It then causes the new collection to 'become' the original collection, changing all existing references to the old version to refer to the new version. (Message become: from class Object performs this operation.) This overhead can be very significant and the only way to avoid it is to try to predict the maximum capacity that the collection will ever need and create it initially with this (or larger) capacity using, for example, the new: message.

Creating a collection whose capacity may never be fully utilized may appear to be wasteful but since a collection is just a bunch of pointers, its memory requirements are small and probably worth the run time saved in growing. The methods that make growing possible also use this strategy - when a collection's capacity must be increased, it is not increased by adding one slot but by adding several slots so that consecutive add: or addAll: messages don't have to grow the collection again.

Message addAll: aCollection copies each element from aCollection into the receiver. As an example, if aCollection contains 25 elements, the receiver collection will gain 25 new elements, growing in the process if necessary. (If the receiver is a Set, all duplicates will, of course, be ignored.)

Both add: and addAll: are frequently used and their behavior is slightly but critically different. As an example, consider the following code and the illustration of its effect in Figure 7.5:

```
collection1 add: collection2. "Adds collection2 to collection1 as a single object."
collection1 addAll: collection2. "Adds all elements to collection1 one by one."
```

Message add: anObject adds anObject to the receiver collection as a single new element, whereas addAll: anObject assumes that anObject is a collection, 'takes it apart', and adds each element to the
receiver individually. In both cases, the receiver must be able to grow which means that `add:` and `allAdd:` cannot be used with arrays.

In both `add:` and `allAdd:` in our example, `collection1` and `collection2` share elements and if the program later modifies any of these elements, both collections will be affected. If, however, one collection *replaces* one of the elements with a new object, the corresponding pointer will point to the new object but the other collection will not be affected because it still points to the original object. We will clarify this point later.

<figure><img src="image_143.png" /><figcaption>Figure 7.5. Effect of `collection1 add:` `collection2` (left) and `collection1 addAll:` `collection2` (right).</figcaption></figure>

Class `Collection` leaves `add:` as subclass responsibility because the exact place at which the element is added depends on the nature of the receiver. Method `allAdd:`, on the other hand, is fully defined in `Collection` using `add:` and subclasses only need to define `add:`. The shared definition of `allAdd:` uses enumeration:

**allAdd: aCollection**

"Include all the elements of aCollection as the receiver's elements. Answer aCollection."

`aCollection do: [:each | self add: each]`.

`^aCollection`

Unlike other methods (such as conversion) that make a copy of the receiver and work on the copy without changing the receiver, `add:` and `allAdd:` change the receiver. This is natural but worth mentioning and you can test it on the following code:

```
| orderedCollection |
orderedCollection := OrderedCollection with: 'abc' with: 'xyz'. "OrderedCollection ('abc' 'xyz')."
orderedCollection add: 'uvw'. "Changes orderedCollection but returns the 'uvw' object"
orderedCollection     "Returns OrderedCollection ('abc' 'xyz' 'uvw')"
```

A somewhat unexpected and confusing feature of all `add` (and `remove`) messages is that they *return* the argument rather than the changed receiver. As an example,

`orderedCollection add: 'uvw'`

changes `orderedCollection` but returns `'uvw'` rather than the modified `orderedCollection` as one might expect. Failing to realize this is a very frequent cause of errors.

**Removing elements (instance methods)**
Removing objects from a collection is subject to similar restrictions as adding because collections that cannot grow don't know how to remove elements either. As an example, you can *change* the elements of an array but you cannot *remove* them. Like add, remove messages also return the argument rather than the receiver as one might expect.

If you are certain that the object that you want to remove is in the collection, use `remove:` as in

`aCollection remove: 45 "Returns 45."`

or in

`aCollection remove: aStudent`

If the object is not in the collection, this message will raise an error. Consequently, if you are not sure, use the alternative `remove:ifAbsent:` as in

`aCollection remove: 45 ifAbsent: [] "Do nothing if the element is not in aCollection."`

or in

`aCollection remove: aStudent ifAbsent: [Dialog warn: aStudent printString, ' is not in the collection']`

The first expression will not do anything if the collection does not contain 45, the second will display a warning if `aStudent` is not in the collection. These two styles of `remove:` - one providing an alternative block, and one providing an unprotected operation - are typical for collection messages. Since `remove:` is a special case of `remove:ifAbsent:` it is defined as

**remove: oldObject**

"Remove oldObject as one of the receiver's elements. Answer oldObject unless no element is equal to oldObject, in which case, provide an error notification."

`^self remove: oldObject ifAbsent: [self notFoundError]`

where `notFoundError` opens an exception window. Method `remove:ifAbsent:` itself is left as subclass responsibility.

**Example: A new enumeration method**

There are occasions when one needs to perform an operation on each element of a collection except a particular one. A method dealing with this problem might be useful for any kind of collection and will thus add it to the enumeration protocol of the abstract class `Collection` and all other collections will inherit it. In doing this, we must be sure to design the method so that all collections will be able to execute it.

Our method, called `do:exceptFor:`, first constructs a new collection by removing the special element from it, and then sends `do:` to the result to enumerate over all remaining elements:

**do: aBlock exceptFor: anObject**

"Evaluate `aBlock` with each of the receiver's elements except `anObject`."

```
| collection |
collection := self reject: [:el | el = anObject]].
collection do: aBlock
```

We tested this approach by printing all elements of a literal array of numbers that are not equal to 3. We used arrays of the following kinds: An array that does not contain 3, an array that contains exactly one element equal to 3, and an array that contains more than one copy of three. As an example, the last of the three tests was
## `(1 2 3 4 5 3 4 5 3 4 5) do: [:el] Transcript cr; show: el printString] exceptFor: 3`

We found that all tests worked but we should, of course, test the method for other kinds of collections as well. This is left as an exercise but for now, we will generalize our method somewhat: In some situations, we might want to execute selective enumeration on the basis of a test rather than by specifying the element explicitly. As an example, we might want to do something with all elements that are greater than 3.

In this problem, we must allow the second argument to be either a block or any other object, and treat blocks in a special way. Our approach will be the same as before but the construction of the collection will be performed differently if the second argument is some kind of a block. In that case, we will simply reject all elements of the receiver that satisfy the block. The whole solution is as follows:

### do: aBlock exceptFor: blockOrAny

"Evaluate aBlock with each of the receiver's elements except those implied by blockOrAny."

```ruby
collection := (blockOrAny isKindOf: BlockClosure)
    ifTrue: [self reject: [:el | blockOrAny value: el]]
    ifFalse: [self reject: [:el | el = blockOrAny]].
collection do: aBlock
```

where `message isKindOf:` checks whether the receiver is an instance of the argument class or its subclass. We tested that our previous tests still work and than added tests of the following kind:

## `(1 2 3 4 5 3 4 5 3 4 5) do: [:el| Transcript cr; show: el printString] exceptFor: [:el| el > 3]`

We found that all tests work as expected.

After this general introduction to collections, we will now examine the essential collections in more detail and illustrate them on examples. In the rest of this chapter, we will present sequenceable collections, all of them subclasses of the abstract class SequenceableCollection. SequenceableCollection implements some of the shared protocols, among them the all important `do:` which it defines as follows:

### do: aBlock

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

1 to: self size do: [:i | aBlock value: (self at: i)]

As you can see, the definition is based on the `to:do:` message defined in number classes and uses the essence of SequenceableCollection - the fact that its elements are accessible by consecutive integer indices starting at 1.

### Main lessons learned:

* Abstract class Collection defines many behaviors shared by all collections.

* The main protocols of collections include creation, accessing, testing, adding and removing elements, conversion to other kinds of collections, and enumeration (iteration over collection elements).

* Conversion is often used to perform operations such as elimination of duplicates or sorting.

* When using collection methods, make sure to understand what kind of object the method returns and whether it changes the original or returns a modified copy while leaving the original unchanged.

* Enumeration is among the most frequent collection operations and good Smalltalk programmers always use the specialized enumeration messages when appropriate.

* Messages that add or remove elements always return the argument and modify the receiver.

### Exercises
1. Test conversion messages `asSet`, `asSortedCollection`, `asOrderedCollection` on literal arrays `#(75 13 254 41 -65 75 75)` and `#('word' 'symbols' 'digits' 'letters' 'letters')` and examine the result and the effect on the receiver.

2. Print the elements of the arrays in the previous exercises in the Transcript in reverse order. (Hint: Check out the enumeration protocol of `SequenceableCollection`.)

3. Execute
```
anArray := #(32 96 -34 89 32 45).
anArray := anArray asSet asArray
```
and comment on the result (type of returned collection, its size, and order of elements).

4. Find how collections grow (Hint: Read the definition of `add:`).

5. Classes `SequenceableCollection` and `ArrayedCollection` are abstract. Write their brief summaries with a description of one important method from each of three selected instance protocols.

6. Browse class `Collection`, read the definitions of its enumeration messages, and examine their use by looking at three existing references. Write a summary including one example of each.

7. Find two `Collection` methods redefined in some of its subclasses and describe the differences.

8. Method `add:` in `Collection` should not be used with `Array` receivers. What will happen if you do send `add:` to an instance of `Array`?

9. Find two other examples of the use of the mechanism discovered in the previous exercise. Find definitions of `new` and `new:`. (See also Appendix 1).

10. Under what conditions contains: will/will not raise an error?

11. We stated that messages that behave identically in most classes are usually defined in class `Object` in a way that reflects the predominant behavior, and the few classes that require different behavior override the inherited definition. Browse definitions of `species`, `isNil`, and `isSymbol` as examples of this technique.

12. What is the difference between
`aCollection remove: 45 ifAbsent: [self]`
and
`aCollection remove: 45 ifAbsent: [^self]`

13. `Interval` is a collection frequently used to represent an arithmetic progression of numbers defined by `start`, `end`, and `step` values, and its main use is for certain types of enumeration. Find `Interval` in the browser, examine its uses, and write a short summary of your findings.

## 7.4 Arrays

Among the numerous collection classes, arrays are perhaps conceptually the simplest. They are also among the most frequently used and we will thus start our coverage of collections with them.

Arrays are fixed-size sequenceable collections and their elements are numbered by successive integer indices starting from 1. Unlike some other sequenceable collections, elements of arrays don't change their position during the array's lifetime. Arrays are accessed mostly by enumeration and less frequently by index. Since we have already presented enumeration messages which all apply almost identically to all collections, we will start with element accessing.

### Accessing an array element

To obtain the value of the element at a particular index, send the `at:` index message as in

`anArray at: 7` "Returns element at index 7. Fails if anArray has fewer than 7 elements."

To replace the element at a known index with a new object, send the `at:put:` message. As an example,

`anArray at: 7 put: 0.4 sin` "Replaces element at index 7 with 0.4 sin. Fails if anArray size < 7."

replaces the seventh element with the object 0.4 sin.
Just like add and remove messages, the `at:put:` message changes the receiver but returns the second argument. As a consequence, the statement

`anArray := anArray at: 3 put: 5 factorial`

changes the value of variable `anArray` to 120 - probably not what was desired (Figure 7.6). If all we wanted was to change the array, we should have written simply

`anArray at: 3 put: 5 factorial`

<figure><img src="image_144.png" /><figcaption>Figure 7.6. Value of `anArray` before (left) and after (right) executing `anArray := anArray at: 3 put: 5 factorial.`</figcaption></figure>

An important aspect of array accessing is that Smalltalk always checks whether the index is within the bounds of the interval <1, size>. If the index is out of bounds, the attempted access produces an Exception window. This automatic checking adds overhead time and some people think that bound checking should be optional. The great majority of Smalltalk programmers consider the security provided by bounds checking more important than speed of access and eliminating bounds checking is not an option.

## Creating new arrays

Arrays are usually created either as literals, or by a creation message such as `new:` or `with:`, or by conversion. We will now illustrate all these possibilities.
The easiest way to create an array is as a *literal* as in

```
array := #(1 3 5 7).
"Four-element array containing four numbers."
array := #('string 1' 'string 2').
"Two-element array containing two strings."
array := #$a $e $i $o $u.
"Five-element array of characters."
array := #('string' #symbol).
"Two-element array with a string and a symbol."
array := #(#symbol1 #symbol2 #('abc' 4)).
"Three-element array with two symbols and a sub-array."
```

## Executing

`array at: 3`

returns 5 for the first array, fails with the second and fourth, returns array `#('abc' 4)` with the fifth, and character `$i` for the third. If we wanted to obtain the second element of the *nested array* in the fifth example, we would have to extract the sub-array first and then access its second element as in

`(array at: 3) at: 2 "Returns 4."`

The limitation of literal arrays is that they can only be created with literal components, in other words, only with the following *literal* objects: `nil`, `true`, `false`, numbers (other than Fraction), characters, strings, symbols, and literal arrays. The following statements thus will not produce what you might expect:

```
array1 := #(3 factorial 5 factorial 7 factorial).
"Same as #(3 #factorial #5 #factorial #7 #factorial)."
array2 := $(3/4 (5/6 7/8)).
"Same as $(3 #/ 4 #(5 #/ 6 7 #/ 8))."
array3 := $(student1 student2).
"Same as $(#student1 #student2)."
```

When an array cannot be created as a literal array, the following methods are the most common:
Neither of these arrays could be constructed as a literal array because all their elements are not literals.

Although the maximum number of with: keywords in the Array protocol is four (message with:with:with:with:) you could define a method with more arguments by creating an uninitialized array and then assigning the individual arguments as in

### with: firstObject with: secondObject with: thirdObject with: fourthObject with: fifthObject

```
| newCollection |
newCollection := self new: 5.
newCollection at: 1 put: firstObject.
newCollection at: 2 put: secondObject.
newCollection at: 3 put: thirdObject.
newCollection at: 4 put: fourthObject.
newCollection at: 4 put: fourthObject.
newCollection at: 5 put: fifthObject.
^newCollection
```

This style is used by the predefined with messages.

## Method 3: Creating an array by converting another type of collection

It occasionally happens that we need an array but don't know how many elements it will have. In this case, we start with a suitable type of collection to collect the elements, and convert it to an array as in

```
“Create variable size collection shoppingList.”
```

```
...
```

```
“Convert it to an Array.”
```

```
shoppingList := shoppingList asArray
```

Note that simply sending the conversion message would not give the desired result

```
“Create collection shoppingList”
```

```
...
```

```
“Convert it to an Array”
```

```
shoppingList asArray
```

because the last statement creates an array from collection shoppingList but does not change the value of variable shoppingList itself. The creating array is thrown away because it is not referenced by any object.

## Method 4: Creating an array by enumeration

Creating a collection by enumeration is very common. As an example, the following code fragment uses an array of strings to create another array called shortStrings containing only those strings that contain at most 15 characters:

```
| strings shortStrings |
```

```
strings := #('short string 1' 'in our context, this is a long string' 'short string 2').
```

```
“Get a new array by selection.”
```

```
shortStrings := strings select: [:string| string size <= 15].
```

```
etc.
```

Note that we did *not* have to convert the result to an array even though its size is different from that of the original, because the species of receiver strings is Array.

As another example, assume that we want to calculate an array of cosines of arguments stored in another array. To do this, we use collect: as follows:

```
| argArray cosArray |
```

```
argArray := #(0.1 0.15 0.25 0.4 0.45 0.5).
```
cosArray := argArray collect: [:arg| arg cos].
etc.

Note that we could not use `to:by:do:` because the arguments stored in `argArray` are not regularly spaced.

### Main lessons learned:

* An array is a fixed-size sequenceable collection whose elements are accessed by consecutive integer indices numbered from 1.

* Arrays, like most other Smalltalk collections, allow any objects to be their elements.

* Arrays are usually created as literals or by conversion from other types of collections, using `new`: followed by calculation of individual elements, or using one of the `with:` messages.

* When an array is created, it is assigned a fixed size and all its elements are initialized to `nil`.

* Each array access checks whether the index is within the array's index bounds.

* The main advantage of arrays is their efficient accessing.

### Exercises

1. Array's definition of `collect`: is not inherited from `Collection`. Find where it comes from and what saving it provides compared to the `Collection` definition.

3. Inspect `#(3/4 5/6 7/8)`.

4. What happens when you execute `#(1 2 3 4)` at: `7`?

5. Since any Smalltalk programs can fail and produce an Exception window, what is so bad about failures that could occur if Smalltalk did not have automatic bounds checking?

6. One of the following expressions succeeds and the other fails. Explain why.
`#(13 53 21 87 9 'abc') contains: [:n| n>200]`

a. `#(13 53 21 87 9 'abc') contains: [:n| n>20]`

7. Write a code fragment to print

a. successive elements of an array separated by carriage returns (use `do:separatedBy:`)

b. elements of an array with their indices (use `keysAndValuesDo:`)

c. elements of an array in reverse order (use `reverseDo:`)

8. When you try to print a large array such as `Smalltalk classNames asArray`, you will only get some of its elements. Which method controls this behavior?

9. Use the `inject:into:` message to solve the following tasks where appropriate.

a. Find the sum of all elements of an array of numbers.

b. Find the product of all elements of an array of numbers.

c. Repeat the previous problem without assuming that all elements of the array are numbers.

d. Find the product of all non-zero numbers in an array whose elements are all numbers.

e. Find the largest number in an array whose elements are all numbers.

f. Find the smallest rectangle containing all rectangles in an array of rectangles. (Hint: Check the protocols of `Rectangle` and create rectangles using `originPoint corner: cornerPoint` as in `1@1 corner: 10@15`.)

g. Find the largest rectangle contained in all rectangles in an array of rectangles.

10. Calculate the following collections using enumeration messages:

a. The string containing all vowels in 'abcdefg'. (Hint: Use message `isVowel`.)

b. The string containing all characters that are not vowels in 'abcdefg'.

c. The string of characters in 'abcdefg' shifted by one position - in other words, 'bcdefgh'. (Hint: Convert a character to its integer code using `asInteger`, then increment the code, and convert to `Character` again.)

d. String entered by the user, encoded by shifting characters as in the previous exercise.

e. All numbers between 1 and 5000 that are divisible by 7 and 11 but not by 13. (Hint: The species of an *Interval* is an *Array* and an expression such as `(1 to: 5000) select: aBlock` thus produces an *array*.)

11. Calculate the sum of 10,000 numbers using `do:` and then using `inject:into:` and compare the speed.
12. Perform the following tasks using enumeration messages:

a. Create an array of three rectangles and use the current window to display their outlines. (Hint: To display the circumference of a Rectangle in the current window, use expression aRectangle displayStrokedOn: Window currentWindow component graphicsContex. Message displayFilledOn: displays the rectangle filled. We will talk about graphics in detail in Chapter 12.)

b. Ask user for the sides of a square and for a displacement d, construct an array containing five squares with the specified side whose origins are displaced by d@d, and display the filled squares in the current window. (Hint: See class Rectangle for rectangle operations, and the previous exercise for information about display.)

## 7.5 Examples of uses of arrays

Smalltalk programmers use arrays extensively but not as universally as programmers in some other languages. One reason for this is that if you really need a collection, Smalltalk provides many other types of collections which are often more suitable because they can grow, because they sort their elements, eliminate duplication, and so on. And if you need an object whose components have identifiable roles, the only correct solution in most cases is to define a class with named instance variables.

When you browse the Smalltalk library, you will find many references to arrays. Most of them use an array because they require enumeration and enumeration is particularly efficient with arrays.

After this introduction, we will now do three more examples showing the use of arrays.

### Example 1. Multiple choice dialogs

A typical use of arrays is for creating menus and multiple choice dialogs. As an example, the following statement produces the dialog window in Figure 7.7 and returns the selected ice cream flavor if the user clicks OK, or an empty string if the user clicks the Cancel button.

Dialog choose: 'Which kind of ice cream do you prefer?'
fromList: #('vanilla' 'strawberry' 'raspberry' 'banana' 'pecan' 'pistachio')
values: #('vanilla' 'strawberry' 'raspberry' 'banana' 'pecan' 'pistachio')
lines: 6
cancel: [""]

<figure><img src="image_145.png" /><figcaption>Figure 7.7. Multiple choice dialog produced with literal arrays.</figcaption></figure>

The message choose:fromList:values:lines:cancel: is one of several very useful multiple choice dialogs in class Dialog. The argument of choose: is the prompt line, the argument of fromList: is an array of displayed strings, the values: argument is an array of objects that are returned when the corresponding label is selected (its elements may be anything you want but we chose strings identical to the labels), lines:
specifies how many lines should be displayed at a time (the rest can be scrolled), and the last argument is a block that will be executed if the user clicks *Cancel* (returns an empty string in our example).

### Example 2. Using arrays for mapping

A interesting use of arrays is for converting one collection of objects into another. Assume, for example, that we want to convert some text into unreadable strings. In a very simple scheme, each letter in the message could be replaced by some other fixed letter, preferably without any easily discernible pattern. As an example, letter $a$ could be replaced by letter $f$, letter $b$ by letter $z$, $c$ by $v$, $d$ by $r$, and so on. With this scheme, a string such as 'acdc' would be encrypted into 'fzrz'. This task can be nicely implemented by storing the encryption scheme in a literal array such as

encryption := #($f $z $v $r etc.)

and extracting the encoding from the array, using the original character's position in the alphabet to calculate the index. As an example, $a$ is the first letter of the alphabet and so we use the first letter in the encryption array to encrypt it. Character $b$ is the second letter in the alphabet and its encryption character is the second character in the encryption array, and so on (Figure 7.8).

<figure><img src="image_146.png" /><figcaption>Figure 7.8. Encrypting secret message using a mapping array.</figcaption></figure>

Since each character has a numeric code (the ASCII code<fnref n="1" />) which is related to its position in the alphabet (the code of $a$ is 97, the code of $b$ is 98, and so on), and since the code of a character can be obtained by sending message asInteger, the formula for finding the index of a character is

(character asInteger) - ($a$ asInteger) + 1 "Returns 1 for $a$, 2, for $b$, and so on."

We will now write a code fragment to ask the user for a string, print it, encrypt it using the mapping in Figure 7.8, and print the encrypted string. As an example, the program will encode the string 'a multi-word string' into 'lixyb-cdtr uytbnm'. The basis of the program is the use of collect: to calculate the encrypted string from the original string:

| encrypted encryption original shift |

"Initialize an encryption array, making sure that each letter appears exactly once."
encryption := #($f $z $v $r g $h $m $j $b $k $w $x $l $n $d $o $s $t $u $y $i $a $c $p $q $e).

"Pre-calculate and cache index shift to avoid the need to recalculate it for each character."

shift := $a$ asInteger - 1.

"Get string from user."

original := Dialog request: 'Enter a string' initialAnswer: "".

<footnote n="1">¹ ASCII (American Standard Code for Information Interchange) is a widely used set of codes of printable characters and control characters such as Line Feed and Escape.</footnote>
"Display original."

Transcript clear; show: original; cr.

"Encrypt and display."

encrypted := original collect: [:char| encryption at: char asInteger - shift].

Transcript show: encrypted

Unfortunately, if the character is not a lowercase letter, the index calculated in the collect: block falls outside of the limits of the array and causes an exception. We leave it to you to correct this shortcoming.

### Example 3. Creating the encrypting array automatically

Instead of having to create an encrypting array by hand as we did in Example 2, we can create it randomly as follows: Start with an array containing all 26 letters of the alphabet. Create a random number between 1 and 26 and insert the corresponding letter at the start of the encryption array; then remove the letter from the original array. In the next iteration, create a random number between 1 and 25, extract the corresponding letter, put it at index 2 of the encryption array, and so on. The principle is as follows:

"Create a string with all letters as a startt for the mapping array."

alphabet := 'abcdefghijklmnopqrstuvwxyz'.

"Create a random number generator, create a mapping array with 26 elements, initialize index."

"Calculate encryption array."

26 to: 1 by: -1 do: whileTrue:

[:max| "Get a random number between 1 and max, extract corresponding character from alphabet, put it in the mapping array, remove it from alphabet].

This is all relatively simple but we must find how to remove an element from a String, in other words, how to make a copy of the original without the removed character. Browsing the collection classes (a string is a collection of characters), we find that there is a useful message called copyWithout: anElement defined in SequenceableCollection and therefore applicable to strings. When we test it with

'abc' copyWithout: 'b'

it does not work because the elements of strings are characters. When we try

'abc' copyWithout: $b

we get the correct result 'ac'. We can now write our code for creating the encoding array as follows:

| rg map alphabet |

"Create alphabet string and random generator, initialize index for accessing mapping array."

alphabet := 'abcdefghijklmnopqrstuvwxyz'.

rg := Random new.

map := Array new: 26.

1 to: 26 do: [ :index | | ch |

"Extract characters at random locations, deleting the selected character from the alphabet each time."

ch := alphabet at: (rg next * alphabet size) truncated + 1.

map at: index put: ch.

alphabet copyWithout: ch].

"Print result in Transcript to see if it works."

Transcript show: map printString

The code works correctly.

### Example 4. Using arrays to execute a list of messages

A clever and common use of arrays is for execution of one of several alternative messages in a list or all the messages in a list. We will use this idea to print the values of sin, cos, ln, exp, and sqrt for x = 1 to 10 in increments of 0.5 in the Transcript.
**Solution:** We will use enumeration over #(#sin #cos #ln #exp #sqrt) and the powerful perform: message.
The perform: message requires a Symbol argument, treats it as a method, and executes it. As an example,

### 5 perform: #factorial

has the same effect as

### 5 factorial

We would, of course, never use perform: if we knew exactly which message we want to send (as in
5 perform: #factorial) but if the message may be any one of several messages, as in our example, or is
supplied as a variable or an argument, perform: is the only way to go. With the perform: message, the
solution of our problem is simply

1 to: 10 by: 1/2 do: [:x |
Transcript cr; show: x printString.
#(#sin #cos #ln #exp #sqrt) do:
    [:message | | value |
    value := x perform: message.
Transcript tab; show: value printString]]

## Example 5. Inappropriate use of arrays

As an example of an *inappropriate* use of arrays, assume that we need an object containing an
address with components including country, state, city, street name, and postal code. Each of these
components has an identifiable role and we should define a class with named instance variables to hold the
individual components. If we used an array to represent this object and put the city name, for example, into
the fourth element, we would have to access city names as in

### address at: 4 put: 'Halifax'

which is not intuitive because the index in expression at: 4 put: 'Halifax' does not provide any hint that we
are dealing with a nameOfCity object. This is dangerous because it makes it too easy to use the wrong index
with the result of storing the name of the city in the wrong element. Similarly, accessing a component of an
array by an expression such as

### address at: 4

does not make any sense and requires that you remember the nature of element 4. A very unpleasant
possibility is that somebody (maybe even you) changes the usage of the array so that city name is now the
third rather than the fourth element, and does not change all code that depends on it. Our code will then give
an incorrect result.

For all these reasons, arrays should not be employed in this way. And if they are, access to their
elements should at least be explicit, for example by special accessing methods such as

### city

"Return the value of city."

^array at: 4

### city: aString

"Change the value of city"

array at: 4 put: aString

With these methods, we can replace the ugly

### address at: 4 put: 'Halifax'

with
address city: 'Halifax'

which is both more readable and safer. If somebody changes the meaning of individual elements, he or she
only needs to change the definition of accessing messages and all code using the array will continue
working as before. If the elements were accessed by index, *all* uses of the index would have to be found and
corrected. Nevertheless, as we already mentioned, the best solution usually is to gather the components as
named instance variables in a new class called perhaps *Address*.

Main lessons learned:

* Like other collections, arrays are used to hold and process nameless elements. Their advantages over other collections are greater efficiency of access and smaller memory requirements.

* Arrays are not used as much in Smalltalk as in other languages because Smalltalk provides many other types of collections and because a class with named components is often preferable.

* Literal arrays are often used for multiple choice dialogs and popup menus.

* Arrays are useful to map one set of objects into another.

Exercises

1. Modify the multiple choice dialog example so that if the user clicks *Cancel*, the program opens a dialog window showing: *We regret that you don't like our ice creams*. To display the apostrophe, repeat it as follows: *We regret that you don't like our ice creams.*

2. Check out other multiple choice dialogs. Use `choose`: `fromList`: `values`: `buttons`: `values`: `lines`: `cancel`: to create a multiple choice dialog as in Figure 7.9. Making a selection in the list should return the same string as the label, clicking `'Cancel'` should return `nil`, clicking `'Copy all'` should return `#copyAll`, and clicking `'Delete all'` should return `#deleteAll`.

3. Combine the encryption program and random generation of encryption and add code to decrypt the encrypted string.

4. The idea of mapping with a mapping array looks like a potentially useful operation. Define a class called *Mapper* that will encrypt and decrypt a string. Decide the details of desired behaviors and implementation and use your class to reimplement the encrypting example.

<figure><img src="image_147.png" /><figcaption>Figure 7.9. Desired user interface for Exercise 2.</figcaption></figure>

7.6 Two-dimensional arrays - tables and matrices
A table is a collection of elements accessible by row and column numbers. It is thus closely related to an array and most programming languages would call it a two-dimensional array; mathematicians would call it a two-dimensional matrix. More generally, an n-dimensional array or matrix is a collection whose elements can be accessed by a set of n indices. An array is thus a one-dimensional matrix, and a table is a two-dimensional matrix.

Two-dimensional matrices are very useful because they capture the substance of a table widget and because they have applications in two-dimensional geometry. While the VisualWorks library does not include a class implementing general n-dimensional matrices, it does have a class called TwoDList which implements two-dimensional arrays and uses it as the value holder for the table widget. In this section, we will present class TwoDList and show how it could be extended to include mathematical behavior of matrices; the use of TwoDList in the table widget will be illustrated in the next section.

## Class TwoDList

Class TwoDList is a subclass of ArrayedCollection and this means that its size is fixed. Its instance variables are dependents, collection, rows, columns, and transposed. Variable dependents makes it possible to use TwoDList as a table widget model which is its intended function. Dependency is implemented so that the change of any of its elements sends an update message to all dependents. Variable collection holds the elements of the table in a linear array. Variables rows and columns hold the number of rows and columns of the table, and variable transposed holds true or false depending on whether the table elements should be viewed in their original arrangement or transposed - with rows and columns interchanged.

A table is an interesting example of information hiding because the concept can be implemented in at least four ways and the user does not need to know which one is used (Figure 7.10). One possibility is to implement a table as a one-dimensional array of elements and access it by converting row and column indices into a single linear index. (VisualWorks uses the first index as column number and the second as row number, treating horizontal axis as the x coordinate of a point and vertical axis as y. This is the opposite of the usual mathematical interpretation.) This can be done in two ways: row-wise (all elements of row 1 followed by all elements of row 2, and so on), or column-wise (all elements of column 1 followed by all elements of column 2, and so on). Another possible implementation is as an array whose elements are rows which are themselves arrays or as an array whose elements are columns which are arrays. As indicated below, TwoDList uses one-dimensional row-wise storage.

<figure><img src="image_148.png" /><figcaption>Figure 7.10. Tables can be stored as arrays of columns or rows (top) or as one-dimensional arrays (bottom). Class TwoDList uses the bottom right arrangement.</figcaption></figure>

## Creating a TwoDList

The two main TwoDList creation messages are on: aCollection columns: c rows: r and columns: c rows: r. The first creates a TwoDList with elements initialized to aCollection, the second creates an uninitialized TwoDList with specified shape and size. As an example,

TwoDList on: #(12 14 16 21 42 24) columns: 3 rows: 2
returns TwoDList (12 14 16 21 42 24) with rows #(12 14 16) and #(21 42 24)

whereas
TwoDList columns: 3 rows: 5

returns TwoDList (nil nil nil nil nil nil nil nil nil nil nil nil nil).

### Accessing a TwoDList

Just like Array, TwoDList is accessed by `at:` and `at:put:`. The difference is that the `at:` argument is normally a Point because a position in a table requires two coordinates. The `x` part of the point is the column number, and the `y` part is the row number. The following example illustrates the principle:

| table |

`table := TwoDList on: #(12 14 16 21 42 24) columns: 3 rows: 2.`

Transcript clear; cr; show: (table at: 1@2) printString.

"Prints 21 - element in column 1, row 2."

`table at: 2@2 put: 77.`

"Changes table to TwoDList (12 14 16 21 77 24) and returns 77."

The internal conversion from the `Point` argument to the position in the underlying array uses the following method:

### `integerIndexFor: aPoint`

`^(columns* (aPoint y - 1)) + aPoint x`

which confirms that elements are stored row-wise because `1@1` is converted to index 1, `2@1` is converted to index 2, and so on.

The `at:` message can also be used with an integer argument, in which case the table is treated as a one-dimensional array and accessed directly.

### Example. Implementing a two-dimensional matrix with TwoDList

As we already mentioned, matrices are very important for computer graphics because they are the basis of transformations of geometric objects such as shifting, scaling, rotation, and mirroring. All these operations can be performed by a combination of matrix scaling, multiplication, addition, and subtraction and implementation of a class capable of these operations would thus be very useful. Creating a framework with a truly sophisticated set of classes supporting matrices and related concepts is beyond the available space and expected mathematical prerequisites and we will thus limit ourselves to designing a simple Matrix class supporting scaling, addition, and transposition.

The first question is where to put Matrix in the class hierarchy. Since Matrix has use for much of TwoDList behavior, we will make Matrix a subclass of TwoDList. Its basic functionality - creation, accessing, and even transposition - are inherited from TwoDList and all we have to do is define methods for scaling and addition.

<figure><img src="image_149.png" /><figcaption>Figure 7.11. Matrix scaling.</figcaption></figure>

To scale a matrix by a number, all its elements are multiplied by the number (Figure 7.11). This can be implemented by enumeration via the `collect:`, multiplying all elements by the scaling factor:

### `scaledBy: aNumber`

"Create a new matrix whose elements are elements of self multiplied by aNumber."

`^self collect: [:el | el * aNumber]`

Unfortunately, when we test this on an example such as
| matrix |

matrix := Matrix on: #(12 14 16 21 42 24) columns: 3 rows: 2.

matrix scaledBy: 3

we fail miserably, getting a walkback (Exception window) which says that "this class does not support variable size allocation" and indicates that it failed in the new: message which was sent by collect:. The problem is that message new: cannot be used if all parts of the class are not accessed by index. We could have anticipated a problem had we compared the definition of Array

ArrayedCollection **variableSubclass**: #Array

instanceVariableNames: "

classVariableNames: "

poolDictionaries: "

category: 'Collections-Arrayed'

with the definition of Matrix which is

TwoDList **subclass**: #Matrix

instanceVariableNames: "

classVariableNames: "

poolDictionaries: "

category: 'Book'

This is an important lesson because it tells us that some collections don't understand the collect: message and even the new: message! If collect: does not work with Matrix because it is not just a collection, it should work with the collection component of Matrix. We will thus rewrite our method to create a new scaled collection from the receiver's collection and then create a new Matrix from it as follows:

**scaledBy: aNumber**

"Return a new matrix whose elements are elements of self multiplied by aNumber."

| newCollection |

"Modify existing collection."

newCollection := collection collect: [:el | el * aNumber].

"Create new instance with the same size and shape and with the new collection."

^self class

on: newCollection

columns: self columnSize

rows: self rowSize

This indeed works as it should as you can test by executing the following example:

| matrix |

matrix := Matrix on: #(12 14 16 21 42 24) columns: 3 rows: 2.

matrix scaledBy: 3

As an alternative solution, we will now implement the same operation by enumeration over indices. There are two ways to do this: We can either calculate over the two-dimensional coordinates, or we can access the elements of the underlying array directly. The first approach requires two nested loops (over rows and columns), the second approach depends on the knowledge of the internal representation of TwoDList. The second approach is dangerous because it depends on internal representation and if the implementation of TwoDList changed, our method would stop working. We will thus use the first approach:

**scaledBy: aNumber**

"Return a new matrix whose elements are elements of the receiver multiplied by aNumber."

| scaled |

"Create a new Matrix object with the appropriate size and shape."

scaled := self class columns: self columnSize rows: self rowSize.

"Calculate its elements from the elements of the receiver."
1 to: self rowSize do: [:rowIndex |

1 to: columnSize do:

[:columnIndex | |point| point := columnIndex @ rowIndex.

scaled at: point put: (self at: point) * aNumber]].

^scaled

This definition is more complicated than the first one but it works.

To add two matrices together, elements from the corresponding cells are added together (Figure 7.12).

<figure><img src="image_150.png" /><figcaption>Figure 7.12. Matrix sum. Both matrices must have the same number of rows and columns.</figcaption></figure>

We can thus define matrix addition as follows:

1. Create a new uninitialized matrix with the same size and shape as the receiver.

2. For each point in the range calculate the sum of the corresponding elements of the receiver and the argument and put this value at the corresponding position of the sum.

3. Return the sum.

The implementation is

+ aMatrix

"Calculate a new matrix whose elements are sums of corresponding receiver and argument elements."

| sum |

sum := self class columns: self columnSize rows: self rowSize.

1 to: self rowSize do: [:rowIndex | "Enumerate over rows first."

1 to: self columnSize do: [:columnIndex | | point |

point := columnIndex @ rowIndex.

sum at: point put: (self at: point) + (aMatrix at: point)].]

^sum

and execution of the following program fragment with *inspect* confirms that it works:

| matrix1 matrix2 |

matrix1 := Matrix on: #(12 14 16 21 42 24) columns: 3 rows: 2.

matrix2 := Matrix on: #(6 3 8 5 9 7) columns: 3 rows: 2.

matrix1 + matrix2

## Main lessons learned:

* Class `TwoDList` implements a two-dimensional array with dependency.

* The main purpose of `TwoDList` is to serve as the value holder for table widgets but its behavior can be extended to implement the mathematical concept of a matrix.

* Some collections don't understand all enumeration messages.

## Exercises

1. How can you determine whether a particular collection class has fixed size?

2. Define and test `Matrix` method `multipliedBy`: implementing matrix multiplication. Add printing.

3. The concept of a mathematical matrix is different from the intended use of `TwoDList`. Redefine `Matrix` independently of `TwoDList`. Provide the following protocols: creation, accessing, arithmetic (addition, subtraction, negation, scaling, multiplication), and printing.

4. Define a three-dimensional matrix class called `ThreeDArray` with the protocols listed in Exercise 3.

5. We found that `collect:` does not work for `Matrix`. This raises several questions:

a. Does `do:` work?
b. Which other basic Collection messages don't work with Matrix?

c. Which other collection classes suffer from the same problem as Matrix?

d. How can we redefine collect: for Matrix?

e. What is the advantage of putting TwoDList in the Collection hierarchy if it does not understand collect:?

6. Implement matrix addition using with:do:

7. Our matrix addition does not check whether the two matrices can be added. Add such a check.

## 7.7 Implementing an n-dimensional array

Although most applications use one- or two-dimensional arrays, three-dimensional arrays are also useful (for example in three-dimensional graphics) and higher dimensional arrays have their uses as well. It is thus natural to extend our definitions and define a class that can implement arrays of *any* dimension. We will now implement such a class under the name NDArry in two different ways.

Class NDArry will have the following responsibilities:

*   **Creation** - create an uninitialized NDArry with the specified number of dimensions and 'shape' (size of individual dimensions). This will be implemented with message dimensions: anArray where anArray is an array of integers specifying sizes along individual axes. As an example

NDArray dimensions: #[3 4]

will create a two-dimensional array with 3 by 4 elements.

*   **Accessing** - get or set an element specified by its indices. The two messages will be atIndexArray: anArray and atIndexArray: anArray put: anObject. As an example, if x is an instance of NDArry,

x atIndexArray: #[3 4]

will return the element with indices 3 and 4.

*   **Arithmetic** - negation, addition, subtraction, and multiplication (messages negated, +, -, and *)

*   **Printing** (implemented by printOn: aStream). The style of printing will be 'change the first index first'. As an example, a three-dimensional array with dimension sizes #[2 3 4] will be printed as follows:

element at index 1 1 1
element at index 2 1 1
element at index 1 2 1
element at index 2 2 1
element at index 1 2 1
element at index 2 2 1
element at index 1 3 1
element at index 2 3 1
element at index 3 3 1
element at index 1 1 2
element at index 2 1 2
etc.

*   Any auxiliary protocols required to implement the above functionality.

In the following, we will consider two approaches to this problem. One is based on the fact that all collections are internally stored as sequential collections, and the other on the fact that an n-dimensional collection is an array of n-1 dimensional collections.

**Solution 1: n-dimensional array as a mapping to one dimension**
In this arrangement, the n indices of the n-dimensional array are mapped into a single index of the corresponding one-dimensional array using some mathematical formula. Since the formula is not obvious, we will feel our way through to it by starting with a solution for small dimensions and generalizing the experience to n dimensions.

In the *one-dimensional case*, no mapping is needed – a one-dimensional array is stored as a one-dimensional array and the counterpart of element $a_i$ in the original array is element $a_i$ in the ‘storage’ array. Index i maps into index i.

In the *two-dimensional case*, we already have experience with TwoDList and we know how it is mapped. For a TwoDList with m columns, element $col@row$ is stored in location $(row-1)*m + col$. We conclude, that when we are traversing the storage, ‘the first index changes first’. We will apply this principle to any number of dimensions.

Consider now the *three-dimensional array* in Figure 7.14. To access the shaded element with indices 4,3,1 (column, row, ‘plane’), we must first skip all elements of the first two-dimensional plane in the foreground $(1*(4*3)$ elements), then the first two rows of the background plane $(2*4)$ elements), and then access the fourth element in the row. In general, if the number of elements along the column, row, plane dimensions is m, n, and k, the formula to access an element with indices (a, b, c) is $(c-1)*m*n + (b-1)*m + a$ or $a + (b-1)*m + (c-1)*m*n$. It is useful to realize that the first element of the sum corresponds to the first dimension, the second to the second dimension, and the last to the last dimension.
<figure><img src="image_151.png" /><figcaption>Figure 7.14. A three-dimensional array with dimensions 4, 3, 2 (columns, rows, planes).</figcaption></figure>

We can now deduce that if an n-dimensional array has dimension sizes $a_1, a_2, a_3, ..., a_n$, the formula for converting an n-dimensional index $i_1, i_2, i_3, ..., i_n$ into a one-dimensional index $i$ is

$$i = (i_{n-1}) * a_{n-1} * a_{n-2} * a_{n-3} * \dots * a_1 + (i_{n-1-1}) * a_{n-1} * a_{n-2} * a_{n-3} * \dots * a_1 + (i_{n-2-1}) * a_{n-2} * a_{n-3} * \dots * a_1 + \dots + (i_{3-1}) * a_2 * a_1 + (i_{2-1}) * a_1 + i_1$$

To confirm, at least partially, that this formula is correct, check that it gives the correct result for the cases that we investigated above - one-, two-, and three-dimensional arrays.

After finding the general formula, we will now improve it to speed up the calculation of the index. To do this, we will multiply out the parenthesized expressions, separate the constants, and keep them in instance variables of each instance of NDArray. We find that

$$ 
\begin{aligned}
i &= (i_{n-1}) * a_{n-1} * a_{n-2} * a_{n-3} * \dots * a_1 + (i_{n-1-1}) * a_{n-1} * a_{n-2} * a_{n-3} * \dots * a_1 + (i_{n-2-1}) * a_{n-2} * a_{n-3} * \dots * a_1 + \dots + (i_{3-1}) * a_2 * a_1 + (i_{2-1}) * a_1 + i_1 \\
&= (i_n * a_{n-1} * a_{n-2} * a_{n-3} * \dots * a_1 + i_{n-1} * a_{n-2} * a_{n-3} * \dots * a_1 + \dots + i_{2} * a_1 + i_1) - (a_{n-1} * a_{n-2} * a_{n-3} * \dots * a_1) - (a_{n-2} * \dots * a_1) - \dots - a_1 \\
&= (i_n * c_n + i_{n-1} * c_{n-1} + i_{n-2} * c_{n-2} + \dots + i_2 * c_2 + i_1 * c_1) - C
\end{aligned}
$$

where

$$c_n = a_{n-1} * a_{n-2} * a_{n-3} * \dots * a_1$$

$$c_{n-1} = a_{n-2} * a_{n-3} * \dots * a_1$$

etc.

$$c_3 = a_2 * a_1$$

$$c_2 = a_1$$

$$c_1 = 1$$

and

$$C = c_2 + c_3 + \dots + c_n \qquad \text{"Does not include } c_1\text{"}$$

After establishing this theoretical background, it remains to identify the internal attributes of NDArray. An NDArray needs to know its elements and we will keep them in instance variables elements - an Array of sufficient size. We also need to know the sizes of the individual axes (instance variable sizes - an Array of integers), and the constants calculated according to the formulas derived above. These constants will be held in instance variables multipliers (an Array of $c_i$ constants) and constant (holding the value of C). Finally, we will find it useful to have an instance variable to hold the number of dimensions (dimensions). With this, we can now proceed to implementation.
Implementation

*Creation protocol.* Method dimensions: `anArray` will return an `NDArray` with properly initialized instance variables but no elements. We will define it in the usual way:

dimensions: `anArrOfSizes`

^self new dimensions: anArrOfSizes

where instance method dimensions: performs all initialization as follows:

dimensions: `anArrOfSizes`

"Initialize, including calculation of internal constants from specification."

| temp |

dimensions := anArrOfSizes size.

sizes := anArrOfSizes.

"The total number of elements is equal to the product of all dimensions."

elements := Array new: (anArrOfSizes inject: 1 into: [:size :el | el * size]).

multipliers := Array new: dimensions.

multipliers at: 1 put: (temp := 1).

2 to: dimensions

do:

[:index |

temp := temp * (anArrOfSizes at: index - 1).

multipliers at: index put: temp.].

constant := multipliers inject: -1 into: [:sum :el | el + sum]

Test that the method works correctly.

*Accessing protocol.* To identify an element, we must specify all its indices. The argument of both the `get` and the `put` method must therefore be an n-dimensional array of indices. If we called our methods at: and at:put, this could cause some problems because conventional at: and at:put: methods expect an integer argument. To avoid this, we will thus use names `atIndices` and `atIndices:put`. The definition of `atIndices` is a simple implementation of the formulas derived above:

atIndices: `anArray`

"Return element specified by its n indices."

| index |

index := 0.

multipliers with: anArray do: [:el1 :el2 | index := index + (el1 * el2)].

^elements at: index - constant

We took advantage of the `with:do`: enumeration method which operates on two collections simultaneously. Method `atIndices:put`: is a simple extension of this definition. Since the calculation of the index is the same in both accessing method, it would be advantageous to define it as a special method and share it. When you are finished, create an `NDArray` and test its accessing protocol.

*Arithmetic protocol.* Given our accessing protocol, arithmetic is easy and we will leave it as an exercise.

*Printing.* Assume that we want to print the contents of a `NDArray` with dimensions `(3 4 6)` as

1 1 1: e "Element at index 1 1 1"

2 1 1: e "Element at index 2 1 1"

3 2 1: e "Element at index 3 2 1"

1 3 1: e "Element at index 1 3 1"

2 3 1: e "Element at index 2 3 1"

3 3 1: e "Element at index 3 3 1"

1 1 2: e "Element at index 1 1 2"

2 1 2: e "Element at index 2 1 2"

3 1 2: e "Element at index 3 1 2"
1 2 2: e "Element at index 1 2 2"
etc. (comments added only for explanation)

in other words, we again use the principle ‘first index changes first’.

To obtain the proper behavior of printString, we must redefine the printOn: method. In our
example, the desired output consists of a pattern of indices followed by the element at that index. We will
implement this by constructing and continuously updating the index pattern, printing it, printing the
element, and updating a pointer into the elements array. Pattern updating will be implemented with a
method that returns nil when the last pattern has been printed:

printOn: aStream

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

| pattern position |

position := 1.

aStream nextPutAll: 'NDArray'; nextPutAll: ' ('; cr.

pattern := (Array new: dimensions) atAllPut: 1.

[pattern isNil] whileFalse:

[1 to: pattern size do: [:index | aStream nextPutAll: (pattern at: index) printString , ' ].

aStream nextPutAll: ': ', (self atIndices: pattern) printString; cr.

position := position + 1.

pattern := self nextPattern: pattern].

aStream nextPut: $)

The process of updating the pattern is as follows: Start from the left end of the current pattern and go right, looking for a number whose value is smaller than the value of the corresponding dimension. If such an element exists, increment it by 1 and reset all elements to the left to 1; return the resulting new pattern. If such an element does not exist, return nil to indicate the end of the process. This algorithm is implemented by the following private method:

nextPattern: anArray

"Find the next pattern of indices, return nil if there is none."

| nextPattern |

nextPattern := anArray copy.

"Look for the first element that is smaller than the corresponding dimension."

1 to: dimensions do:

[:index | | value |

value := anArray at: index.

value < (sizes at: index)

ifTrue: [ "Increment the element, reset the preceding, return result."

nextPattern at: index put: value + 1.

nextPattern atAll: ( 1 to: index - 1) put: 1.

^nextPattern]]].

"All patterns printed, we are finished."

^nil

Solution 2: n-dimensional array as an array of n-1 dimensional arrays

A completely different view of an n-dimensional array is as a one-dimensional array of n-1
dimensional arrays (Figure 7.14). This is a recursive view in which a structure contains objects of similar
structure but simpler and the bottom object in the hierarchy is a one-dimensional array which contains the
actual elements. Although this idea appears complicated, its implementation is simpler than Solution 1. To
distinguish our two approaches, we will call this class NDArrayRecursive.
<figure><img src="image_152.png" /><figcaption>Figure 7.15. Three-dimensional array (three indices) as an array of two-dimensional arrays.</figcaption></figure>

The class will have similar protocol as in Solution 1 and its instance variables will also be similar. They will include **dimensions** (integer number of dimensions), **sizes** (array of sizes of individual dimensions), **elements** (array of n-1 dimensional arrays for n > 1, array of elements for n = 1). Our printing strategy will again be based on a pattern array holding indices and this array will be held in instance variable **pattern**. Since several of the methods will be recursive, it will be useful to keep track of the number of dimensions of the whole matrix and we will use instance variable **globalSize** for this purpose.

### Implementatio of protocols

**Creation.** We need two creation messages: One to create the topmost matrix, and another to create the matrices inside it. The reason for this is that we want all enclosed matrices know the size of the outermost matrix.

The topmost creation method will be called **newWithDimensions**: anArray where anArray is the array of dimensions as in Solution 1. This method recursively creates lower level matrices by message dimensions: **anArray globalSize**: anInteger. The definitions of the top level class creation method is

**newWithDimensions: anArray**

"Return new instance with axe dimensions as specified"
^self new dimensions: anArray globalSize: anArray size

and the corresponding class method for creating the enclosed lower level matrices is

**dimensions: anArray globalSize: anInteger**

"Return new instance with axe dimensions as specified"
^self new dimensions: anArray globalSize: anInteger

This method sends the instance message dimensions: **globalSize**: which initializes the created object:

**dimensions: anArray globalSize: anInteger**

"Initialize elements from specification."
| size |
sizes := anArray.
dimensions := anArray size.
globalSize := anInteger.
size := anArray at: 1.
elements := Array new: size.
dimensions > 1 ifTrue: "Create the lower level matrix."
[1 to: size do:
[:index | elements at: index put: (NDArrayRecursive
dimensions: (anArray copyFrom: 2 to: dimensions)
globalSize: anInteger)]]

The block statement creates the appropriate number of lower dimensionality arrays if dimension is greater than 1 and passes the remaining dimensions down. As an example, if we want to create a three-dimensional array with sizes #(
6 2), the creation method creates an NDArrayRecursive with dimension =3, size = 4, and three elements, each of them a two-dimensional NDArrayRecursive. Each of these arrays has dimension 2 (it is two-dimensional), size = 6, and contains six one-dimensional arrays. Each of these one-dimensional arrays has two uninitialized elements. All share the same globalSize = 3.
When we tried to test the creation mechanism with `inspect`, we got an exception because inspecting elements requires the `do:` message which class `Collection` leaves as subclass responsibility. We thus added `do:` as follows:

### do: aBlock

"Evaluate aBlock with each of the receiver's elements as the argument."
dimensions = 1 ifTrue: [elements do: [:element | aBlock value: element]]
ifFalse: [elements do: [:element | element do: aBlock]]

We then inspected

`NDArrayRecursive dimensions: #(2 3 4)`

and the result was as expected.

*Accessing*. Here again, we must distinguish higher dimension arrays whose elements are lower dimensionality arrays, and the actual data stored in the `NDArray`:

### atIndices: anArray

^dimensions = 1 ifTrue: [elements at: (anArray at: 1)]
ifFalse: [(elements at: (anArray at: 1))
atIndices: (anArray copyFrom: 2 to: dimensions)]

Note that we must use message `atIndices:` on the last line - message `at:` would fail because the argument is an array rather than an integer. Note also that we remove the first index from the elements array as we pass it to the n-1 dimension array. Method `atIndices:put:` is similar and we leave it as an exercise. We tested accessing by executing the following test program with `inspect`

| nda |
nda := NDArrayRecursive dimensions: #(2 3 4).
1 to: 2 do:
    [:col| 1 to: 3 do:
        [:row| 1 to: 4 do:
            [:plane| nda atIndices: (Array with: col with: row with: plane)
                put: col*row*plane]]].

nda

and everything works.

*Printing*. For this implementation, we will write code to output the following format (produced for the array from the test code above):

### NDArrayRecursive (

1 1 1: 1
1 1 2: 2
1 1 3: 3
1 2 1: 2
1 2 2: 4
1 2 3: 6
1 3 1: 3
1 3 2: 6
1 3 3: 9
2 1 1: 2
2 1 2: 4
2 1 3: 6
2 2 1: 4
2 2 2: 8
2 2 3: 12
2 3 1: 6
2 3 2 : 12

2 3 3 : 18

)

Our solution will again be based on an pattern of indices but we will leave all printing to the lowermost
NDArray level - the one-dimensional array. However, all levels in the hierarchy must contribute to the
pattern as they increment their indices and we will implement this as follows:

* When a request to execute `printOn:` arrives to the uppermost n-dimensional NDArray, this object initializes pattern to an array consisting of all 1s. It then passes pattern down to its n-1 dimensional elements which pass it down to their components, and so on. The one-dimensional at the bottom NDArray prints the indices and the values.

* During each iteration through the printing loop of a k-dimensional NDArray, the NDArray object updates pattern by incrementing its k-th component, and resetting the elements to the right to 1. This is done recursively and all indices are thus correctly updated.

The implementation of this strategy is as follows:

**printOn: aStream**

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

"The top level array prints the name of the class, etc."

dimensions = globalSize

ifTrue: [aStream nextPutAll: 'NDArrayRecursive'; nextPutAll: ' ('; cr.

"Initialize index pattern and pass it down to lower level arrays."

pattern := (Array new: dimensions) atAllPut: 1.

elements do: [[:element | element pattern: pattern]].

dimensions > 1

ifTrue: [elements do: [:element |

aStream nextPutAll: element printString.

self updatePattern]]

ifFalse: [pattern size timesRepeat:

[1 to: pattern size do: [:index | aStream nextPutAll: (pattern at: index) printString , ''].

aStream nextPutAll: ': ', (elements at: pattern last) printString; cr.

self updatePattern]].

"Top level array prints the closing bracket."

dimensions = globalSize ifTrue: [aStream nextPut: $)]

where

**pattern: anArray**

"Initialize this pattern and pass it down to lower level patterns."

pattern := anArray.

dimensions > 1 ifTrue: [elements do: [:element | element pattern: anArray]]

Finally, method `updatePattern` simply assigns a new pattern to `pattern`, and updating is done as follows:

**updatePattern**

"Increment my pattern index by 1 and reset those to the right to 1."

| myIndex |

myIndex := globalSize - dimensions + 1.

pattern at: myIndex put: (pattern at: myIndex) + 1.

pattern atAll: (myIndex + 1 to: globalSize) put: 1

This completes the implementation. We conclude that the solution based on recursion is simpler –
we did not even have to figure out how to calculate the index from the index array. It would be interesting
to compare the speed and memory requirements of the two solutions.
## Main lessons learned:

* Recursion may be applied to structure, not only to algorithms.

* Recursive implementations of algorithms and objects are often simpler.

## Exercises

1. Compare the number of calculation required to calculate the index before and after the simplification of the formula.

2. Implement the missing protocols in each implementation of NDArray.

3. Implement printing of the first solution by accessing elements directly. Compare speed.

4. Re-implement printing for the second solution so that the first index changes first.

5. Compare the speed of element accessing of both implementations.

## 7.8 Use of TwoDList in the Table widget

To conclude the chapter, we will now present the table widget, both as an example of the use of sequenceable collections and as a useful GUI component.

The table is a read only widget (you cannot change the contents of its cells) for displaying objects in two-dimensional form. A closely related widget is a data set which also displays data in the form of a table but allows the user to modify cell values. Also, while a table can display any mixture of objects, a data set is used to display rows of related multi-item objects such as student records, or book information. In both the table and the data set, the user can select a cell, a row, or a column, and the program can monitor selection changes and respond appropriately.

The *Aspect* of a table is a *TableInterface* object (Figure 7.16) with

* information about the data displayed in the table, and the current selection (combined into a *SelectionInTable* object),

* a description of the table's row and column labels and its other visual aspects.

<figure><img src="image_153.png" /><figcaption>Figure 7.16. The structure of table widget support.</figcaption></figure>

The following slightly edited comment of *TableInterface* captures its main properties.

"A TableInterface is used to hold the information needed for controlling the format and content of a TableView. The tabular structure of the underlying data is usually captured in terms of a SelectionInTable. TableInterface is also a point at which many operations may be done to the table component. Any operations that are needed to be done to either the row labels or column labels of a table should go through the TableInterface.
Operations that have to deal with the visual properties of a table (color and emphasis) on a column, row, or element basis should either be done in the same way that the `TableInterface` does it, or through the `TableInterface`.

### Instance Variables:

<table><tr><td>columnWidths</td><td>&lt;ArrayedCollection of &lt;Integer&gt; | Integer | nil&gt; The widths of the columns</td></tr><tr><td>columnFormats</td><td>&lt;Array | Symbol | nil&gt; #left, #right, and #centered are format symbols</td></tr><tr><td>columnLabels</td><td>&lt;ValueHolder with: &lt;TableAdaptor&gt; | nil&gt; Labels for the columns of the Table</td></tr><tr><td>columnLabelsFormats</td><td>&lt;Array | Symbol | nil&gt; #left, #right, and #centered are format symbols</td></tr><tr><td>rowLabelsWidth</td><td>&lt;Integer | nil&gt; The width of the row label display</td></tr><tr><td>rowLabels</td><td>&lt;ValueHolder with: TableAdaptor | nil&gt; Labels for the rows of the Table</td></tr><tr><td>rowLabelsFormat</td><td>&lt;Symbol | nil&gt; #left, #right, or #centered</td></tr><tr><td>selectionInTable</td><td>&lt;SelectionInTable&gt; The underlying data in tabular form</td></tr><tr><td>columnLabelsAndSelection</td><td>&lt;SelectionInTable&gt; Models the selection of an entire column</td></tr><tr><td>rowLabelsAndSelection</td><td>&lt;SelectionInTable&gt; Models the selection of an entire row</td></tr></table>

A `TableInterface` allows you to control the width of columns in pixels, and the format (left justified, right justified, or centered) of the contents of the cells and the row and column labels. It also allows the user to select either an individual cell or a whole row or column.

### Example: Table of functions

**Problem:** Write an application displaying a table of values of sin, cos, ln, log, and square for all values from 1 to 10 in steps of 1. The desired format is shown in Figure 7.16.

**Solution:** To solve this problem, we must paint the user interface, define its parameters, and define the required methods.

*Painting the table and defining its parameters.* This step is routine. Draw the outline of the table, enter the name of the *Aspect* (name of method returning a `TableInterface` - we called it `tableInterface`) and specify any *Details* you want to override the defaults. *Define the Aspect* of the table. The labels and the number of columns and cells will be assigned by the `initialize` method.

*Defining the methods.* Since our application is so simple, we only need an `initialize` method to create the all-important `TableInterface` object from its pieces: A `TwoDList` with appropriate size and values, and the `TableInterface` object itself with a `SelectionInTable` containing the `TwoDList` object as its underlying collection value holder. Finally, we will specify visual aspects of the table including column widths, text format, and row and label column:

### initialize

*Create objects underlying the Table widget and calculate its parameters.*

| functions | values | columnWidths |

*Create a `TwoDList` to hold the data and provide dependency based binding to the widget.*

values := TwoDList columns: 5 rows: 10.

*Calculate the data to be displayed, format it, and insert it into the `TwoDList`.*

functions := #(#cos #sin #ln #log #squared).

1 to: values | columnSize do:

:[column | 1 to: values | rowSize do:

:[row | values atPoint: column @ row

put: (PrintConverter print: (row perform: (functions at: column))
formattedBy: '#####.###'))].

*Create the `TableInterface` and associate it with the list of values.*

tableInterface := TableInterface new selectionInTable: (SelectionInTable with: values).

*Define labels and column widths of the `TableInterface`.*

columnWidths := 60. "All columns have the same width."

tableInterface columnLabelsArray: #('cos' 'sin' 'ln' 'log' 'square');

rowLabelsArray: #(
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    );

columnWidths: columnWidths

This definition requires several comments:
1. Since we access the `TwoDList` via rows and columns, we use accessing method `atPoint`: `aPoint` put: an `Object`. Be careful to specify `aPoint` correctly as `column@row`. In our first attempt, we accidentally reversed the order of row and column and obtained a strange result.

2. To calculate cell values, we stored the names of the necessary methods as `Symbols` in an array called `functions`. We then sent the messages by using the column number to extract the appropriate function from the array, and sending `perform:` with the value of the row as the argument.

3. After calculating a cell value, we used the `PrintConverter` to convert the number to a suitable format - the default format is not satisfactory.

4. The default display of the table is awkward and does not have any labels. To obtain the desired look, we ask the `TableInterface` to set suitable column widths, and define appropriate labels.

### Main lessons learned:

* A table is a read-only widget.

* The *Aspect* of a table is an instance of `TableInterface`.

* `TableInterface` has two functions: It holds the displayed data and the current selection, and contains information about the visual aspects of the table such as column width and row and column labels.

## Conclusion

Most computer applications work with collections of objects. Collections can be divided according to several classification criteria and VisualWorks library contains many collection classes, some for system needs, others for general use.

Abstract class `Collection` at the top of the collection hierarchy defines several protocols shared by all or most collections. Besides creation, the most important of these is probably enumeration - iteration over all elements of the collection. Enumeration messages are used in most iterations over collections and experienced programmers use their specialized forms whenever opportunity arises.

The collections most useful for general use are `array`, `ordered` and `sorted` collection, `list`, `string`, `symbol`, `set`, `bag`, and `dictionary`. The main differences between these collections are whether they are restricted to a fixed size, whether they allow duplication, and whether their elements are ordered and how this ordering works. The class hierarchy uses ordering as the distinguishing feature to divide collections into two main groups - `sequenceable` and `non-sequenceable`.

The main protocols shared by all collections include `creation`, `enumeration`, `accessing`, `testing`, `adding` and `removing` elements (if allowed), and conversion to another kind of collection. Conversion is often used to perform an operation such as `sorting` or `elimination` of duplication.

Beginners usually encounter problems when using certain collection messages. For proper use, make sure to know which object the message returns (some methods return the argument when one might expect the receiver), and whether the method changes the receiver or returns its modified copy while leaving the receiver unchanged.

In this chapter, we started our presentation of collections with class `Array`. An array is a fixed-size sequenceable collection which means that its size cannot grow or shrink, and that its elements are accessed by consecutive integer indices numbered from 1. Arrays are most commonly created as literals, by conversion from other types of collections, by `new`: followed by calculation of individual elements, or by one of the with: messages. When an array is created by the `new`: creation message, all its slots are filled with `nil` objects. Arrays - like most other Smalltalk collections - allow their elements to be any objects or even a mixture of different kinds of objects. The main advantages of arrays over other sequenceable collections are their ease of creation, compactness in terms of internal representation, and fast access.

Each array access in Smalltalk checks whether the specified index is within the array's bounds. This checking adds some execution overhead but makes use of arrays safe.

Arrays are not used as much in Smalltalk as in other languages because Smalltalk provides many other types of collections which may be more suitable for the task at hand, and because it is often preferable to define a class with named components to hold the values instead of using collections. The test that determines whether a multi-component object should be represented by a collection or a class with named
variables is whether the components have identifiable, 'name-able' roles or whether they are just a
collection of objects of the same kind.

A TwoDList is a collection designed to support table widgets. It can be considered an extension of Array in two ways: Its elements are accessed by a pair of indices representing a row and a column number, and it implements dependency. We showed how TwoDList could be used to create a new class implementing mathematical matrices with minimal effort.

The table widget is a read-only two-dimensional GUI component equipped with vertical and
horizontal scroll bars and visual features including row and column labels, programmable cell width and
height, and formatting of labels and cell contents. Its underlying *Aspect* object is a *TableInterface*. A
*TableInterface* holds information related to the appearance of the table such as labels and column widths,
and a *SelectionInTable* object containing the displayed data and the current selection. The data itself is
represented by a TwoDList.

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

**Array**, **Association**, **Bag**, **Collection**, **Dictionary**, **List**, **OrderedCollection**, **SelectionInTable**, **Set**, **SortedCollection**, **String**, **Symbol**, **TableInterface**, **Text**, **TwoDList**.

**Widgets introduced in this chapter**

Table.

**Terms introduced in this chapter**

*array* - fixed-size collection whose elements are indexed by consecutive integers starting at 1

*bag* - unordered collection that keeps track of the number of occurrences of its elements

*bounds checking* - testing whether an index of a sequenceable collection falls within acceptable limits

*collection* - group of nameless elements with creation, accessing, testing, adding, deletion, and enumeration protocols

*dictionary* - collection of key-value pairs

*enumeration* - iteration over collection elements

*index* - integer number used to access elements of sequenceable collections

*nested collection* - collection used as an element of another collection

*ordered collection* - collection whose elements are stored in a fixed externally accessible order; in a more restrictive sense, instance of class *OrderedCollection*

*set* - unordered collection that eliminates duplication of elements

*sort block* - block used by sorted collection to determine the order of its elements

*sorted collection* - a sequenceable collection whose elements are ordered according to a sort block

*sequenceable collection* - a collection whose elements are arranged in a fixed order defined by integer indices

*string* - a sequence of character codes with no information about their rendition

*table* - a fixed size read-only two-dimensional widget for displaying heterogeneous objects in tabular form

*text* - string with emphasis prescribing how the string should display itself

*unordered collection* - collection whose internal ordering is determined by the implementation and inaccessible to the user
# Chapter 8 - More Sequenceable Collections, List widgets

## Overview

In this chapter, we conclude our exploration of sequenceable collections with OrderedCollection, SortedCollection, List, String, Symbol, and Text. We then present single- and multiple-selection lists. Unordered collections are the subject of the next chapter, and additional widgets including Dataset, Subcanvas, Notebook, Dialog Window, and Menus are covered in Appendix 2.

## 8.1 Class OrderedCollection

Class OrderedCollection is a very frequently used subclass of SequenceableCollection. Its instances have the following properties:

* Elements are indexed starting with 1 (as in all sequenceable collection).

* Size (number of elements in collection) may be smaller than capacity (number of slots).

* Capacity automatically grows when size = capacity and a new element is added.

* Elements can be removed, changing size but not capacity.

* Elements are usually accessed by enumeration, at the start, or the end rather than by index.

Ordered collections are used mainly to gather elements whose number is not known beforehand or whose number changes. One example of both situations is a program that collects labels for a list widget when the number of labels is initially unknown. Two common situations of the second kind are stacks and queues. Quoting from the comment of OrderedCollection 'a stack is a sequential list for which all additions and deletions are made at one end of the list; a queue is a sequential list for which all additions are made at one end, but all deletions are made from the other end'. You will immediately recognize that a pile of stacked trays in a cafeteria is an example of a stack, and that a line of customers in a bank is an example of a queue. Stacks and queues are very important in computer applications and we will deal with them in more detail in Chapter 11.

After this general introduction, we will now briefly examine OrderedCollection protocols and then give several examples of their use.

### Creation

Ordered collections can be created in the same ways as arrays except that there is no concept of a literal OrderedCollection. In practice, ordered collections are most often created with new (default capacity 5) because the eventual maximum size of the collection is usually unknown. When the approximate size is known beforehand, one should always use new: to eliminate time-consuming growing. When a new OrderedCollection is created, it is allocated a number of slots equal to the requested capacity but its size is 0 and its response to isEmpty is true.

Ordered collections are also often created by the conversion message asOrderedCollection, and the withAll: aCollection message is occasionally used with the same effect.

### Accessing

Although elements of OrderedCollection may be accessed by at: and at:put:, they are mostly accessed by enumeration, at the start, at the end, or by locating the desired element by its value. Some of the messages used for accessing are

first "Returns the first element without changing the collection."

last "Returns the last element without changing the collection."

addFirst: anObject "Makes anObject the first element, shifts rest to the right, grows if necessary."
<table><tr><td><code>addLast: anObject</code></td><td><code>"Adds anObject at end, grows if necessary."</code></td></tr><tr><td><code>add: anObject</code></td><td><code>"Same as addLast: anObject."</code></td></tr><tr><td><code>add: newObject after: oldObject</code></td><td><code>"Inserts newObject after the first occurrence of oldObject."</code></td></tr><tr><td><code>removeFirst</code></td><td><code>"Removes the first element."</code></td></tr><tr><td><code>removeLast</code></td><td><code>"Removes the last element."</code></td></tr><tr><td><code>remove: anObject</code></td><td><code>"Removes the first occurrence of anObject."</code></td></tr><tr><td><code>removeAllSuchThat: aBlock</code></td><td><code>"Removes all elements that satisfy the block."</code></td></tr></table>

Note that adding an element at the beginning of an OrderedCollection or inside it changes the index of all the remaining elements. As the collection evolves, the index of an element may thus change and this is one of the reasons why `at:` and `at:put:` messages are not much used with ordered collections.

To understand ordered collections and how they differ from arrays, it is useful to know how they are implemented. When an element is removed, it is replaced with `nil` and the OrderedCollection adjusts its instance variables `firstIndex` and `lastIndex` which it uses to keep track of its first and last valid elements (Figure 8.1). This means that the concept of a position and an index are not equivalent and to deal with this, OrderedCollection redefines accessing messages `at:` and `at:put:` on the basis of `firstIndex` and `lastIndex`.

<figure><img src="image_154.png" /><figcaption>Figure 8.1. Operation of `removeFirst` and `removeLast`.</figcaption></figure>

Here is the definition of `removeFirst`:

### removeFirst

"Remove the first element of the receiver. If the receiver is empty, provide an error notification."

```
| firstObject |
self emptyCheck.
firstObject := self basicAt: firstIndex.
self basicAt: firstIndex put: nil.
firstIndex := firstIndex + 1.
^firstObject
```

Message `emptyCheck` first tests whether the collection is empty. If it is, `emptyCheck` causes a non-proceedable error, opening an Exception notifier with the `Proceed` button disabled. Clicking `Terminate` exits the execution of the method and avoids getting into further trouble by attempting to access an object at a non-existent index. The `Debug` button remains enabled and you can proceed in the Debugger - only to run into other error conditions.

Note that `removeFirst` does not use the `at:` message, but rather `basicAt:`. The reason for this is that `OrderedCollection` defines its own `at:` and this definition is inappropriate in this context. What we want to use is the definition that works on the basis of the 'regular' index rather than `firstIndex` and `basicAt:` allows us to do that. Method `basicAt:` is defined in `Object` and is equivalent to the usual `at:` message.

To see why we need methods such as `basicAt:`, consider the situation in Figure 8.2 and assume that class C needs the top level definition of `at:`. If we used `super at:` we would access the definition in class A, presumably different from that in class `Object`. The only way to deal with this situation is to define a synonym of `at:` in `Object` and make a gentlemen's agreement with all Smalltalk programmers that they will
never redefine it in any subclass. Method `basicAt:` has exactly this role. If everybody plays by the rules, `basicAt:` thus has a guaranteed single definition that we can always rely on. When you examine the library, you will find that there are quite a few `basic...` methods.

<figure><img src="image_155.png" /><figcaption>Figure 8.2. The need for `basicAt:`. Class A redefines `at:` but class C needs `at:` from Object.</figcaption></figure>

## How much are ordered collections used and how?

To find how much Smalltalk relies on ordered collections, we checked how many methods in the library use them and we found several hundred references to class `OrderedCollection`. This shows that `OrderedCollection` is one of the most heavily used classes. Browsing shows that ordered collections are usually created with `new` and used mainly to gather a collection of elements whose number is initially unknown. The resulting collection is often processed in some way, for example sorted, converted to an array for more efficient processing, or to a set to eliminate multiple copies of duplicated elements.
We also checked how many instances of `OrderedCollection` our running session has by executing

### OrderedCollection allInstances size

We found over 200 references, a large number that will fluctuate greatly as you run an application<fnref n="1" />. These findings confirm that ordered collections are very popular and that they are a very important part of the Smalltalk environment.

### Main lessons learned:

* Ordered collections are indexed but the index is rarely explicitly used for access. Instead, elements are usually added and retrieved at the end or at the start, preserving the order in which elements are added.

* The size of an ordered collection may be smaller than its capacity.

* Adding a new element to an ordered collection automatically grows the capacity if necessary.

* The growth of an ordered collection is relatively time-consuming and the only way to avoid it is to create the ordered collection with capacity equal to the maximum anticipated need or greater.

* Making an ordered collection larger than necessary wastes a negligible amount of memory but making it too small may cost considerable execution time.

* Removing an element from the beginning of an ordered collection changes the index of remaining elements. It does not shrink the capacity.

* A new ordered collection contains slots but no elements.

* Ordered collections are used mainly to collect elements when their exact final number is unknown and as stacks or queues.

## Exercises

<footnote n="1">¹ Method `allInstances` does not give an accurate picture of all instances of a class because it counts even unreferenced objects that have not yet been garbage-collected.</footnote>
1. When a new ordered collection is created, it contains slots but no elements. What are these 'slots'? Is something stored in them? (Hint: Check the implementation of `at` in `OrderedCollection` and see if you can examine the unoccupied slots.)

2. Find how to obtain the number of references to a given class. (Hint: The browser knows how to find all references and returns them as a collection.)

3. List at least two useful methods inherited by `OrderedCollection` from `SequenceableCollection` and give examples of their use.

4. `OrderedCollection` and other variable-size collections automatically grow but don't shrink. Define a method to shrink an ordered collection. Comment on the usefulness of such a method.

5. Why is `add`: in `OrderedCollection` equivalent to `addLast`:? (Hint: Which of `addFirst` and `addLast` is faster? Why?)

6. Find two other basic... methods and explain their purpose.

7. Write a code fragment to create an `OrderedCollection` with capacity 5 and three elements. Add four new elements, then delete one at the beginning and one at the end. Print all slots of the collection before and after each step. (Hint: Use `basicAt`.)

8. Since `removeFirst` moves the first index pointer, the 'removed' element cannot be accessed so why bother changing it to `nil`?

9. Are the slots vacated at the beginning of an `OrderedCollection` by `removeFirst` ever reclaimed? If so, when and how?

## 8.2 Several examples with ordered collections

In this section, we present several examples using ordered collections. They include code from the library, a brief code fragment, and a small application using two classes.

### Example 1: Selecting book entries from a library catalog

**Problem:** Assume that we have a library catalog application with information about books. All book information is stored in a collection accessible via variable `books`. The collection is an `OrderedCollection` because it must be able to grow and shrink, and its elements are instances of class `Book`. Class `Book` has instance variables `title`, `author`, `publisher`, `year`, and `number` (Figure 8.3) and accessing methods for accessing them. A typical task for the application is to extract all books published by 'Addison-Wesley' in 1997.

<table><caption>Figure 8.3. Structure of ordered collection books.</caption><thead><tr><th></th><th>title</th><th>author</th><th>publisher</th><th>year</th><th>number</th></tr></thead><tbody><tr><td>book 1</td><td>'The personal computer ...'</td><td>'Sargent ...'</td><td>'Addison-Wesley'</td><td>1995</td><td>11</td></tr><tr><td>book 2</td><td>'Principles of computer science'</td><td>'Schaffer'</td><td>'Prentice-Hall'</td><td>1988</td><td>22</td></tr><tr><td>book 3</td><td>'Programmer's guide to the IBM PC'</td><td>'Norton'</td><td>'Microsoft Press'</td><td>1985</td><td>13</td></tr><tr><td>book 4</td><td>'Programming languages'</td><td>'Pratt'</td><td>'Prentice-Hall'</td><td>1965</td><td>54</td></tr><tr><td>book 5</td><td>'Data structures ...'</td><td>'Kruse'</td><td>'Prentice-Hall'</td><td>1994</td><td>52</td></tr><tr><td>book 6</td><td>'Introduction to AI'</td><td>'Charniak ...'</td><td>'Addison-Wesley'</td><td>1986</td><td>36</td></tr><tr><td>book 7</td><td>etc.</td><td>etc.</td><td>etc.</td><td>etc.</td><td>etc.</td></tr></tbody></table>

**Solution:** To solve this problem, the code must check the publisher and year components of each instance of `Book` and select all books that satisfy the given condition. This calculation can be performed very easily with `select`: as follows:

`selectedBooks := books select: [:book| (book publisher = 'Prentice Hall') and: [book year = 1997]]`

### Example 2: Conversion to OrderedCollection - how does it work?

Class `Collection` contains many conversion messages and one of them - `asOrderedCollection` - converts its receiver - an arbitrary collection - to an `OrderedCollection`. Here is its definition:
### asOrderedCollection

```
| anOrderedCollection |
anOrderedCollection := OrderedCollection new: self size.
self do: [:each | anOrderedCollection addLast: each].
^anOrderedCollection
```

The method first creates a new ordered collection whose capacity is equal to the size of the receiver collection. It then adds all elements of the receiver at the end of the new collection and returns the new collection. The original collection is not affected but shares all its elements with the returned ordered collection.

### Example 3: A simple shopping minder application

**Problem:** This problem is a test of an idea that will be explored in more detail in the next chapter. In the present version, our task is to write a program allowing the user to enter a list of store items and prices and display it in the Transcript one item per line followed by the total price. Items are sorted alphabetically by name and all items that cost more than $10 are listed behind the total. An example of the desired output is

cat food price: 24 dollars 54 cents

flour price: 4 dollars 75 cents

sugar price: 3 dollars 15 cents

Total price: 32 dollars, 44 cents

Expensive items:

cat food price: 24 dollars 54 cents

**Solution:** We will define two classes, one to hold item information, and the other the future application model. Since the problem is quite simple, we can write class specifications without constructing scenarios and performing other preliminary work:

**ShoppingMinder:** Holds a collection of items, knows how to obtain item information from user and how to display summary information in the Transcript.

**Superclass:** Object. In the final implementation, Shopping minder will be a subclass of ApplicationModel.

**Components:**

* items - OrderedCollection of Item objects – the number of items is unpredictable

**Contracts and behaviors:**

**Collaborators**

* Creation

* Create and initialize items to a reasonably large OrderedCollection (capacity 20)

* Accessing

* Get item information from user via Dialog and create an Item

* Adding

* Add new item to items

* Arithmetic

* Calculate totals

* Printing

* Display items

* Display expensive items

* Display total

* Execution

* Execute shopping process including entry of items and output of results

**Item:** Holds name and price of item.

**Superclass:** Object

**Components:**

* name - name of item (a String)
* price - dollars and cents (a Currency)

Contracts and behaviors:

* Creation

* Create instance with given name and price

* Accessing

* Get and set methods

* Printing

* Return name and price as a suitably formatted String

Collaborators

On the basis of this plan, it is now easy to write the implmentation. We will leave most of the work to you and confine ourselves to a few elements.

## Class ShoppingMinder

We will start at the execution level. To run the application, the user will execute

### ShoppingMinder new execute

This method creates a new instance of ShoppingMinder and initializes its items instance variable. Its definition is

### new

^super new initialize

and the initialize method is

### initialize

"Initialize items to a suitably sized ordered collection."

items := OrderedCollection new: 20.

Method execute obtains items from the user and displays the results. Its definition is simply

### execute

"Get items from the user and display the results."

[self addItem] whileTrue: [self addItem].

self displayItems.

self displayTotal.

self displayExpensiveItems

Note that the formulation implies that addItem returns true when an item is added, and false when the user indicates that there are no more items. Its definition is as follows:

### addItem

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

| name price |

name := Dialog request: 'Enter item name' initialAnswer: "".

name isEmpty ifTrue: [^false]. "Exit and terminate loop - user indicated end of entry."

price := Dialog request: 'Enter item price' initialAnswer: "".

price isEmpty ifTrue: [^false]. "Exit and terminate loop - user indicated end of entry."

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

^true

where name:price: is the creation method for Item, to be defined later.

### displayTotal

"Add prices of all items and display the total in Transcript."

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

Note the use of `inject:into:` with `Currency` objects, and the `displayString` message - you may have expected `printString`. `displayString` is one of the two standard methods that convert an object to a String, the other being the familiar `printString`. As you know, `printString` is used mainly to display information during debugging and in the inspector ; in other words, it is intended primarily for the *code developer*. Method `displayString`, on the other hand, is intended for the *user interface*, for example, when displaying an object in a list widget. Its essence is the same as that of `printString` (it creates a String or Text describing an object) but the contents may and the form (for example the font) may be different.

The default definition of `displayString` in `Object` is simply `printString` and most classes don't redefine this definition.

To follow the spirit of the distinction of the two messages, we will expect them to produce different strings. Message `printString` will produce text such as

'Item: Apple, a Currency: 13 dollars, 27 cents'

taking advantage of `printString` in `Currency`, whereas `displayString` will produce

sugar price: 3 dollars 15 cents

Both methods will be defined in class `Item`. The definition of `displayItems` is

### displayItems

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

Transcript clear.

(items asSet asSortedCollection: [:item1 :item2 | item1 name < item2 name])

do: [:item | Transcript show: item displayString; cr]

The notable thing about this definition is that the conversion to a sorted collection uses a special `sort` block instead of the simple `asSortedCollection` message. The definition of `displayExpensiveItems` is

### displayExpensiveItems

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

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

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

We leave the other methods in `ShoppingMinder` to you as an exercise.

### Class Item

The `name:price:` creation method that we used in `addItem` expects a `String` and a `Number` which it converts to a `Currency` object. Its definition is as follows:

#### name: aString price: aNumber

"Create new instance using aString for name and a aFixedPoint for currency."

| dollars cents |

dollars := aNumber asInteger.

"Get the integer part of the price."

cents := ((aNumber - dollars) * 100) asInteger.

"Get the fractional part."

^self new

name: aString;

price: (Currency dollars: dollars cents: cents)

where we assume that accessing messages `name:` and `price:` have already been defined. The definition of `displayString` is as follows:

#### displayString
```
| tabString |
tabString := String with: Character tab.
^name, tabString, 'price: ', price dollars printString, 'dollars ',
    (price cents rem: 100) printString, 'cents'
```

We leave the rest, including the printString method, as an exercise. By the way, we are not happy with the strategy that we used to implement our application. It would have been better to implement the domain class first and test it, and then go to the application model and test it with the already existing domain class. Most developers proceed in this order.

## What happens when a collection grows?

When you add a new element to a collection filled to capacity, the following steps take place:

1. A new collection of the same kind as the receiver is created with double the capacity of the original.

2. All elements of the receiver are copied to the new collection. (In reality, only the pointers are copied, of course.)

3. All references from the system to the receiver are switched to point to the new collection (Figure 8.4). This step uses message *become*: which is understood by all objects and may be time consuming.

4. Since there are now no references to the old collection, it is garbage collected<fnref n="2" />.

<figure><img src="image_156.png" /><figcaption>Figure 8.4. Message *object1 become: object2* switches references.</figcaption></figure>

The heart of the process is the following method:

### changeCapacityTo: newCapacity

"Change the capacity of the collection to be newCapacity."

```
| newSelf |
"Make an empty copy whose capacity is obtained elsewhere."
newSelf := self copyEmpty: newCapacity.
"Initialize value of firstIndex."
newSelf setIndicesFrom: 1.
"Add all elements of existing collection fast - with no checks."
firstIndex to: lastIndex do:
    [:index | newSelf addLastNoCheck: (self basicAt: index)].
"Switch references."
self become: newSelf
```

## The nature of collections - variable sized classes

The definition of OrderedCollection in the browser

```
SequenceableCollection variableSubclass: #OrderedCollection
instanceVariableNames: 'firstIndex lastIndex'
```

<footnote n="2">² See Appendix 8 for a discussion of garbage collection.</footnote>
classVariableNames: "
poolDictionaries: "
category: 'Collections-Sequenceable'

uses a creation message different from most other classes such as

Object subclass: #Document
instanceVariableNames: 'entities currentMargins '
classVariableNames: 'DefaultMargins DefaultTabStops '
poolDictionaries: "
category: 'System-Printing'

You will find that several other collection class definitions use the keyword *variableSubclass*: instead of *subclass*. This is because Smalltalk recognizes essentially two types of classes - those whose components are accessed by an index, and those that don't have index-based access. Both types of classes may or may not have named instance variables. The standard browser template for declaring a new class assumes the second kind of class because most classes have only named variables, and if you want to define a class with indexed variables (a *variable class*), you must modify the definition template in the browser.

A class such as OrderedCollection thus has the structure shown in Figure 8.5 and contains *unnamed* index elements and (possibly) *named* instance variables. Named instance variables are accessed via an accessing method, but indexed elements are accessed using a mechanism such as `self at: index` and `self at: index put: object`. The fact that there is an indexed component can only be recognized from the definition of the class because the indexed components don't have any variable name associated with them.

<figure><img src="image_157.png" /><figcaption>Figure 8.5. Indexed elements are accessed by index as in `self at: index` rather than by name.</figcaption></figure>

### Main lessons learned:

* VisualWorks has two forms of messages converting an object to a String. Message `printString` should be used for debugging, `displayString` is for output to the user interface.

* Smalltalk recognizes two main types of classes - those that have index-accessed elements and those that don't. The standard browser template for creating a new class creates a class without access by index unless the superclass is a variable size class itself. To create a new variable-size class that is not a subclass of a variable-size class, modify the class creation template.

### Exercises

1. Complete the shopping minder example. Add `printString` to both new classes for testing.

2. Write a code fragment to request a list of labels from the user and use them in a multiple choice dialog. Repeat with both forms of Dialog's multiple choice messages.

3. Read Appendix 3 and write an expression to find all variable class in the library.

4. `ClassOrderedCollection` defines method `removeAllSuchThat:` `aBlock`. Compare it with `reject:`.

## 8.3 Ordered collections as the basis of dependency
In this section, we will take a closer look at an important application of ordered collection - the dependency mechanism - and illustrate it on an example. Let us start by recapitulating what we know about dependency.

Any object may have any number of dependents. The basic dependency mechanism is defined in class *Object* and redefined in class *Model*. Model's implementation is preferable because it holds dependents in instance variable called *dependents* (an *OrderedCollection*) rather than a global variable as *Object* does. As a consequence, when a *Model* object ceases to exist, its dependents are no longer referenced and may be garbage collected, whereas *Object*'s dependents remain referenced until explicitly removed from the global variable that references them. If *Object*'s dependents are forgotten, they will thus stay in the image forever.

The protocol for adding new dependents and removing existing ones is defined in class *Object* and only the accessing method for the *dependents* collection is redefined in *Model*<fnref n="3" />. The dependency mechanism is based on three changed methods called *changed*, *changed:*, and *changed:with*. All three are defined in class *Object*, exhibit the same basic behavior (Figure 8.6), and differ only in their number of arguments.

<figure><img src="image_158.png" /><figcaption>Figure 8.6. A model with two dependents and its response to `self changed:with:`. Numbers indicate order of message execution.</figcaption></figure>

Dependency works as follows: When the model object needs to notify its dependents that it has changed in a way that might affect them, it sends *itself* an appropriate *changed* message as in

* self changed

* or

* self changed: #value

* or

* self changed: #value with: 153

In response to the last message, for example, the definition of changed messages in *Object* then sends update: #value with: 153 to each of its dependents:

* changed: anAspectSymbol with: aParameter

* "The receiver changed. The change is denoted by the argument anAspectSymbol. Usually the argument is a *Symbol* that is part of the dependent's change protocol, that is, some aspect of the object's behavior, and aParameter is additional information. Inform all of the dependents."

* self myDependents update: anAspectSymbol with: aParameter from: self

<footnote n="3">³ The ease with which Model can redefine its inherited behavior by redefining only one accessing method illustrates the advantage of using accessor methods instead of direct access to instance and class variables.</footnote>
where `myDependents` returns the dependents collection. Each dependent then responds according to its own definition of `update:with:`. Typically, the definition of `update:with:` examines the argument `anAspectSymbol`, decides whether it cares to do anything for the kind of change indicated by the argument and if it does, it uses `aParameter` to execute the appropriate response. The response of individual dependents may range from identical for each dependent to different for each dependent, to none for some or all dependents. A default implementation of all update messages is defined in `Object` and does not do anything. As a consequence, if a dependent does not have an update method, it simply does not do anything when the model changes (unless update is defined in a superclass).

The implementation of changed messages is interesting. The simplest one - the changed method with no arguments - is as follows:

**changed**

`self changed: nil`

This definition thus does not send any update message and depends on changed: to do so. The changed: message is defined as

**changed: anAspectSymbol**

`self changed: anAspectSymbol with: nil`

It again passes the real work to a more complete version of changed which is defined as follows:

**changed: anAspectSymbol with: aParameter**

`self myDependents update: anAspectSymbol with: aParameter from: self`

This method finally sends an update message to the dependents. This update message contains an extra argument - the sender of the message. This is essential in some situations because it allows the dependent to ask the model for additional information.

We conclude that no matter which changed message the model sends, the result is always the same update message, namely `update:with:from:`. The question now arises how a dependent that does not define this rich version of update responds. As an example, how does a dependent who defines only update: aSymbol respond to `update:with:from:?:`

The answer is obvious: If an object gets a message that it does not understand, Smalltalk looks for the method in the method dictionary of its superclass. If this class does not contain the definition, it searches the next superclass, and so on until it reaches class `Object`. To find how the update mechanism works, we must thus look at the definition of update: in `Object` where we find, for example,

**update: anAspectSymbol with: aParameter from: aSender**

> "Receive a change notice from an object, denoted by a `aSender`, of whom the receiver is a dependent. The argument `anAspectSymbol` is typically a `Symbol` that indicates what change has occurred and `aParameter` is additional information. The default behavior defined here is to do nothing; a subclass might want to change itself in some way. Note that this implementation assumes that the object does not respond to this protocol and an attempt is made to try a simpler message."

`^self update: anAspectSymbol with: aParameter`

This shows that if the dependent does not understand the 'rich' update message, `Object` downgrades the message to a simpler update and asks the dependent to execute it. If the dependent does not have that definition, update again goes up the superclass chain and if it reaches `Object`, it is downgraded again, and so on, until either a suitable update definition is found in the receiver's class or its superclass or until execution eventually passes to update in `Object` - which does nothing.

We have already seen the most conspicuous use of dependency in VisualWorks in its implementation of the user interface: A widget is a dependent of its `ValueHolder` (a subclass of `Model`) and when the value holder gets a `value:` message, it informs its dependent widget via changed and update, and the widget then gets the necessary information from the `ValueHolder` and redraws itself.

Although UI implementation is the most prominent use of dependency, there are other uses as we will illustrate in the following example. Note that this example (and all other uses of dependency) could be
implemented without the dependency mechanism. The use of dependency just makes the implementation
more logical and neater because it gives the model object a uniform way to deal with all its dependents,
whatever their nature may be.

### Example. Dependence of object state on weather

The most common use of dependency is to send changed: aValue and use the value in the update: method of the dependent to decide exactly what to do. We will now present a very simple example that uses this form of dependency.

**Problem:** Objects on Earth respond to weather in various ways. When the sun is out, people sit in the shade, talk, and smile, birds sing, and stones get warm. When it rains, people get umbrellas, stones get wet, and birds don't do anything. When it snows, people ski, and birds and stones disappear. We will now write a program that asks the user to select current weather (Figure 8.7) and prints the state of people, birds, and stones in the Transcript. The program terminates when the user clicks *Stop*.

<figure><img src="image_159.png" /><figcaption>Figure 8.7. User interface for text example.</figcaption></figure>

**Solution.** We will define a class for each part of the problem - Weather, Person, Bird, and Stone. Class Weather will be responsible for running the program and displaying the user interface, Person, Bird, and Stone will be its dependents and will respond to weather changes by printing their state to the Transcript.

### Class Person

The only responsibility of Person is to respond to an update message. This message must specify the new weather, a Symbol, one of #sunny, #rainy, or #snow. This is the 'aspect' of change and we will thus use the update: anAspect message. According to the specification, the definition is simply

#### update: aSymbol

"Display appropriate string according to weather described by aSymbol."
(aSymbol == #sunny)
ifTrue: [^Transcript show: 'People talk and sit in the shade.' ; cr].
(aSymbol == #rainy)
ifTrue: [^Transcript show: 'People get umbrellas.' ; cr].
(aSymbol == #snow)
"This test is not really necessary."
fTrue: [^Transcript show: 'People go skiing.' ; cr].

No other methods need to be defined because instances can be created with the new message.

### Class Bird

This class is essentially identical to Person but the details of update: are different because birds
behave differently:

#### update: aSymbol

"Display appropriate string according to weather described by aSymbol."
(aSymbol == #sunny)
```ruby
ifTrue: [^Transcript show: 'Birds sing.' ; cr].
(aSymbol == #snow)
fTrue: [^Transcript show:'Birds disappear.'; cr].
```

Note that `Bird` does not respond when the value of the `update:` argument is `#rainy`. No other methods need to be defined because instances can be created with the new message.

### Class Stone

Similar to the two classes above and left as an exercise.

### Class Weather.

Since `Weather` has dependents it will be a subclass of `Model`. Since it is also an application model, we will make it a subclass of `ApplicationModel` (which is a subclass of `Model`). Its initialization method must assign new instances of `Person`, `Bird`, and `Stone` as its dependents:

#### initialize

"Create new instance and add Person, Bird, and Stone as its dependents."

self dependents

addDependent: Person new;
    addDependent: Bird new;
    addDependent: Stone new.

self run "We don't know how to create lists yet so we will use this intermediate implementation for now."

and the instance method `run` is

#### run

"Repeatedly ask user to select weather and stop when the selection is `Cancel`. Notify dependents."

repeat [selection := Dialog choose: 'Select weather or Cancel to stop'

fromList: #('sunny' 'rain' 'snow')
    values: #(#sunny #rainy #snow)
    lines: 3
    cancel: []

selection isNil ifTrue: [^self].
    self changed: selection]

Now assume that we decided to add another object, such as a river. We must define its class and modify the `initialize` method to add a `River` dependent, but the handling of changes does not change because the `Model` does not need to be explicitly aware of its individual dependents and does not care what they are and what are the details of their behavior as long as they know how to respond to an appropriate update message. This is dependency's main claim to fame.

### Main lessons learned:

* Dependency is defined by specifying the dependents of a model object.

* The model object is normally a direct or indirect subclass of `Model` although any object can have dependents via the mechanism defined in `Object`.

* Dependents in `Model` subclasses are stored in an ordered collection.

* When the model changes in a way that may affect its dependents, it sends itself one of the changed messages.

* The changed message sends a matching update message to each dependent.

* There are several varieties of changed and update and they differ in the number of keywords.

* The update method defined in the dependent's classes does not have to match the changed message sent by the model but it normally does.

* Dependency is used mainly by the user interface but there are many other possibilities for its use.

* All problems can be solved without dependency but the use of dependency makes the solution cleaner.
and more flexible.

## Exercises

1. Browse and describe implementation of dependency in class Object.

2. Complete the weather example and test it.

3. Add a river object to the example. When it is sunny, the river gets warm, when it snows, the river freezes. Rain does not have any effect.

## 8.4. Tennis - another example of dependency

Have you ever watched the spectators at a tennis game? As the ball moves across the court, their heads turn in unison as if enchanted. In this example, we want to simulate this effect. Consider a very simple implementation of the problem, assuming a collection of spectators arranged in a straight line in parallel with the axis of the court and a ball moving along the axis from one end of the court to the other (Figure 8.8).

<figure><img src="image_160.png" /><figcaption>Figure 8.8. Tennis court with spectators following the ball's motion.</figcaption></figure>

In this section, we will not represent the court and the moving ball graphically because we don't know how to do that yet; we refer you to Chapter 12 for information necessary for a graphical implementation. Our implementation will simply print the position of the ball and spectator information to the Transcript in the following form:

Move number 1
Ball position: 10 direction: left.
Spectator location: 1 angle: 1.25
Spectator location: 4 angle: 1.11
Spectator location: 7 angle: 0.79

Move number 2
Ball position: 9 direction: left.
Spectator location: 1 angle: 1.21
Spectator location: 4 angle: 1.03
Spectator location: 7 angle: 0.59

and so on for each consecutive ball displacement. Angles are expressed in radians.

To make the program more interesting, we will provide the user interface in Figure 8.9 allowing selection of court parameters, the number of spectators, and the number of successive changes of ball positions (*Number of moves*). The location of spectators along the court will be calculated from the assumption that spectators are uniformly distributed.
<figure><img src="image_161.png" /><figcaption>Figure 8.9. User interface for Tennis program with initial default parameters.</figcaption></figure>

## Specification

The statement of the problem is clear and there are only two interesting scenarios - opening the application and clicking Go.

### Scenario 1: Starting the program

1. User executes expression such as Tennis open

2. Program opens the window in Figure 8.7.

### Scenario 2: Starting simulation by clicking Go.

1. User clicks Go.

2. Program places the ball at the right end of the court and starts simulation, performing a series of ball displacements accompanied by adjustments of spectators' viewing angles.

## Preliminary design

The specification suggests three classes - Tennis, Ball, and Spectator. Their initial description is as follows:

**Tennis:** I maintain simulation parameters, perform the simulation, and display the user interface.

<table><thead><tr><th>Responsibilities</th><th>Collaborators</th></tr></thead><tbody><tr><td>interface specs - define UI window</td><td></td></tr><tr><td>creation - open user interface, initialize default values</td><td>Ball, Spectator</td></tr><tr><td>action - response to Go. Reset ball and perform the required number of steps, printing simulation results in Transcript</td><td>Ball, Spectator</td></tr></tbody></table>

**Ball:** I represent the tennis ball moving across the tennis court.

<table><thead><tr><th>Responsibilities</th><th>Collaborators</th></tr></thead><tbody><tr><td>creation - create a ball with initial position and direction</td><td></td></tr><tr><td>moving - calculate new position and notify spectators</td><td>Spectator</td></tr></tbody></table>

**Spectator:** I represent a spectator who turns his or her head while watching the moving ball.

<table><thead><tr><th>Responsibilities</th><th>Collaborators</th></tr></thead><tbody><tr><td>creation - create a spectator at given location</td><td></td></tr><tr><td>watching - calculate new head position</td><td>Ball</td></tr></tbody></table>

We will now check whether these three candidate classes can support our two scenarios and how.

### Scenario 1: Starting the program

1. User executes expression Tennis open

2. Tennis initializes user interface parameters and opens the interface in Figure 8.7.
## Scenario 2: Starting simulation by clicking Go.

1. User clicks Go.

2. Tennis creates a new Ball and a new collection of Spectator objects according to the values of user interface parameters.

3. Tennis executes simulation by asking the ball to move the specified number of times, displaying the required output for each step. Ball moves by incrementing or decrementing its position depending on its current direction of motion, notifies all spectators of its new position, and checks whether it has reached the end of the court and should change direction. Each Spectator calculates its viewing angle from its location and the current position of the ball.

We conclude that our three classes should be able to handle the problem.

## Design refinement

Let's start with a preliminary discussion of the place of the three classes in the class hierarchy. Tennis is a subclass of ApplicationModel because it is responsible for the user interface, Ball and Spectator have no class relatives and this suggests superclass Object.

As the next step, we will take a closer look at class descriptions starting with Ball and Spectator. Clearly, the state of Spectator depends directly on the position of the ball: Whenever the ball moves, every spectator is notified and responds by changing its viewing angle. Spectators are thus dependents of the ball. This has several consequences. First, Ball should thus be a subclass of Model. Second, the action responsibility of Tennis now requires only the collaboration of Ball, because Ball will take care of Spectator. With this insight, we can now rewrite the class descriptions as shown below. Note that we changed the descriptions of some of the responsibilities to reflect our better understanding of the situation.

**Tennis:** I perform the simulation and display the user interface.

Concrete class.

**Superclass:** ApplicationModel

**Components:** ball (Ball), spectators (Array), and aspect variables on integer values courtWidth, courtLength, numberOf Moves, and numberOf Spectators

**Responsibilities**

**Collaborators**

* interface specs - define UI window

* creation - open user interface, initialize default values

* initialize - initialize aspect variables, create a Ball

Ball

* action - response to Go.

* go - reset everything, create spectators and make them dependents of ball, perform the required number of steps, printing simulation steps in Transcript

* printing - supply your description

printOn: - return descriptive string according to output specification
**Ball**: I represent the tennis ball moving back and forth across the tennis court.

Concrete class.

Superclass: Model

Components: court (Tennis), direction (Symbol) direction of motion - #left or #right, position (Integer) - rightmost position is 0, increases towards left

Responsibilities

Collaborators

* creation - create a ball

* onCourt: aTennis - Ball needs access to Tennis to get simulation parameters at the start of each run

* moving - move the ball by one step

* move - increment or decrement position depending on direction, notify dependent spectators, check for end of court and change direction if necessary

Spectator

* printing - supply your description

* printOn: - return descriptive string according to output specification

**Spectator**: I represent a spectator turning his or her head while watching the moving ball.

Concrete class.

Superclass: Object

Components: angle (Float) - viewing angle, distance (Integer) distance to ball line (court axis), location (Integer) - location measured from the right end of the court

Responsibilities

Collaborators

* creation - create a spectator

* distance:location: - create new spectator at given distance from ball line and at given location from right end of court

* updating - respond to update request from Ball

* update:with: - calculate new viewing angle from ball position

* printing - supply your description

* printOn: - return descriptive string according to output specification

Figure 8.10 shows the Hierarchy Diagram and the Object Model Diagram.

<figure><img src="image_162.png" /><figcaption>Figure 8.10. Hierarchy Diagram (left) and Object Model Diagram (right) of Tennis.</figcaption></figure>

Implementation

We will now show some selected methods class by class.

Class Tennis

The definition of the class is

ApplicationModel subclass: #Tennis
instanceVariableNames: 'ball spectators courtWidth courtLength numberOfMoves
`numberOfSpectators`'

`classVariableNames: "`

`poolDictionaries: "`

`category: 'Tennis'`

Initialization defines default values for value holders and creates a Ball:

**initialize**

"Initialize the opening values of simulation parameters, create a ball."

`courtLength := 10 asValue.`

`courtWidth := 10 asValue.`

` numberOfSpectators := 5 asValue.`

` numberOf Moves := 20 asValue.`

`ball := Ball for: self "Create tennis ball on this court."`

The basis of the operation of the whole program is response to the Go button which is defined as follows:

**go**

"Reinitialize parameters according to current settings, execute the simulation the required number of times, and display the result."

`self reset.`

`Transcript clear.`

`1 to: numberOf Moves value`

`do: [:number | Transcript cr; cr; show: 'Move number ', number printString; cr; show: self printString.`

`self ball move]`

Method reset reads the current settings of user interface value holders and uses them to create spectators and assign them to ball as its dependents:

**reset**

"Remove existing spectators, if any, create equally spaced new spectators and make them dependents of the ball. Used to update parameters before the start of each simulation run."

`| distance |`

`1 to: spectators size do: [:index | self ball removeDependent: (spectators at: index)].`

`spectators := Array new: self numberOfSpectators value.`

`distance := (courtLength value / spectators size) truncated.`

`1 to: spectators size do: [:index | spectators at: index put: (Spectator distance: distance location: 1 + (distance * (index - 1)))].`

`spectators do: [:aSpectator | self ball addDependent: aSpectator]`

Note that we had to remove existing spectators before creating new ones; we assume that simulation parameters have changed. Printing of results uses the `printOn:` method because this is only a test. The definitive user interface will be implemented when we learn about graphics.

**printOn: aStream**

"Display ball and spectator information."

`aStream nextPutAll: self ball printString, '.'; cr.`

`self ball dependents do: [:aSpectator | aStream nextPutAll: aSpectator printString, '.'; cr]`

The operation of this method depends on `printOn:` methods defined in `Ball` and `Spectator`.

**Class Ball**

The definition of the class is

`Model subclass: #Ball`

`instanceVariableNames: 'court direction position '`

`classVariableNames: "`

`poolDictionaries: "`

`category: 'Tennis'`
Operation of Ball requires access to Tennis to obtain court parameters and we thus define the creation message as follows:

**for: aTennis**

"Create a ball at the right end of the court."
^(self new) court: aTennis; reset

Initialization depends on method reset which sets the ball's initial position and direction of motion:

**reset**

"Assign initial position (right end of court) and direction of motion (left)."
self position: self court courtLength value.
self direction: #left

The essence of the whole simulation is method move which moves the ball by one step and changes its direction when it reaches the end of the court:

**move**

"Make a one-pixel move in the current direction. Check for end of court and change direction if necessary."
self direction == #left
ifTrue: [self position: self position - 1]
ifFalse: [self position: self position + 1].
self changed: #position with: self position.
"This triggers the dependency mechanism."
self endOfCourt ifTrue: [self reverseDirection]

where the test for the end of the court is

**endOfTrack**

"Did I reach the end of the court? Return true or false."
^position = 1 or: [position = self court courtLength value]

and the change of direction is implemented as follows:

**reverseDirection**

"I reached the end of the course and direction of motion must be reversed."
self direction: (self direction == #left
ifTrue: [#right]
ifFalse: [#left])

Finally, printing uses the printOn: method which is defined as follows:

**printOn: aStream**

aStream nextPutAll: 'Ball position: ', self position printString, ' direction: ', self direction asString

**Class Spectator**

The definition of the class is

Object subclass: #Spectator
instanceVariableNames: 'angle distance location'
classVariableNames: "
poolDictionaries: "
category: 'Tennis'

To create a Spectator, we must initialize its distance from the right end of the court and its distance from the axis of ball motion:
**distance: distanceInteger location: locationInteger**

^self new distance: distanceInteger location: locationInteger

This definition depends on the following creation method defined on the instance side of Spectator protocol:

**distance: distanceInteger location: locationInteger**

"Complete initialization and calculate initial head angle for ball in position 1."

self distance: distanceInteger.

self location: locationInteger.

self calculateAngleFor: 1

Angle calculation uses some simple trigonometry and its definition is

**calculateAngleFor: anInteger**

"Find angle for this spectator from current ball position anInteger."

| xDistance |

xDistance := anInteger - location.

self angle: (xDistance / self distance) arcTan

The temporary variable xDistance is used only to make the code more readable.

Since spectators are dependents of Ball, they must understand an update message. The only parameter we need from the model is the ball's current position but to follow established conventions, the update: argument is a Symbol even though the method does not use it, and the second argument will be the ball's position:

**update: aSymbol with: anInteger**

"The ball has moved to position anInteger - recalculate head angle."

self calculateAngleFor: anInteger

Finally, the printOn: method is as follows:

**printOn: aStream**

aStream nextPutAll: 'Spectator location: ', self location printString, ' angle: ',

(self angle asFixedPoint: 2) printString

**Exercises**

1. Complete and test the program from this section.

2. Dependency may be mutual as in the following simulation problem: Consider a collection of 5 nuclear particles distributed uniformly along a line. Each particle initially has some random amount of energy between 1 and 5. In each simulation step, the energy of a particle grows by a random integer amount between 1 and 3. When a particle's energy reaches or exceeds 10, it explodes, loses all its energy, and transfers it to the other particles in equal amounts. Implement the problem with a user interface allowing the user to control simulation parameters.

**8.5 Class SortedCollection**

SortedCollection is a subclass of OrderedCollection that automatically inserts new elements in their proper place among elements already in the collection. Insertion is based on a *sort block* stored in instance variable sortBlock (Figure 8.11). Most methods inherited from OrderedCollection work for sorted collections as well but some, such as addAfter:, are invalid because sorted collections determine where to put new elements themselves.

<figure><img src="image_163.png" /></figure>
<figure><img src="image_164.png" /><figcaption>Figure 8.11. SortedCollection is a variable-size collection with one named instance variable whose value is a two-argument block. Its default value is `[:x:y | x <= y]`.</figcaption></figure>

Since each `SortedCollection` keeps its sort block in instance variable `sortBlock`, its value can be assigned when the `SortedCollection` is being created or even during its lifetime. Most sorted collections are created with `new` or `new:`, both of which assign `sortBlock` the default value stored in class variable `DefaultSortBlock`. This value is assigned by the `SortedCollection` `initialize` method which is

initialize

`DefaultSortBlock := [:x:y | x <= y]`

This definition deserves several comments:

* None of the references to `SortedCollection` sends message `initialize`. What is its purpose then? This is executed to initialize `SortedCollection` when the class is first defined and the result is saved in the Smalltalk dictionary as a part of `SortedCollection`. You can change the default sort block by redefining `initialize` and re-executing `SortedCollection initialize` or by assigning a new value to `DefaultSortBlock` directly, and you could make the change permanent by saving the image. This, however, would change the effect of those existing uses of sorted collections that assume the current value of the sort block.

* The definition of `initialize` shows that default comparison uses message `<=`. This means that if you create a sorted collection with its default sort block, all elements that will ever be added to the collection must be able to compare themselves with all objects already in the collection using `<=`. Collections of strings and collections of numbers satisfy this condition. We can also define `<=` for other objects and compare, for example, rectangles by their size, Smalltalk methods by the amount of time that they take to execute, colors by the value of their hue or redness, and so on, and all these objects will now be able to sort themselves. The mechanism is very powerful.

The assignment of the default sort block in `new:` happens as follows:

new: anInteger

`^(super new: anInteger) initialize`

Here `super new:` refers to `new:` in `OrderedCollection` and creates a new uninitialized instance of `SortedCollection`. This `SortedCollection` object then executes the instance message `initialize` whose definition is

initialize

`sortBlock := DefaultSortBlock "Instance method accessing a class variable."`

We have already mentioned that you can assign a different `sortBlock` when creating an instance of `SortedCollection` or during its lifetime. In the second case, the sorted collection automatically resorts itself according to the new sort block. The following code fragment shows both possibilities. It first creates a sorted collection with a non-default sort block and then changes the sort block to the default value:

`sortedCollection |`

`sortedCollection := SortedCollection sortBlock: [:x:y | x > y]. "Non-default sort block - descending order."`

`sortedCollection addAll: #(13 53 56 21 98 73 56 89). "Elements added one by one and sorted."`

`Transcript clear; show: sortedCollection printString; cr.`

`sortedCollection sortBlock: [:x:y | x <= y]. "Switch to a different sort block and resort."`

`Transcript show: sortedCollection printString`