## Object

### Magnitude

Character

Date

Time

### Number

Float

Fraction

Integer

LargeNegativeInteger

LargePositiveInteger

SmallInteger

### LookupKey

Association

### Link

### Process

### Collection

### SequenceableCollection

LinkedList

### Semaphore

### ArrayedCollection

Array

### Bitmap

DisplayBitmap

### RunArray

String

Symbol

Text

ByteArray

### Interval

### OrderedCollection

### SortedCollection

### Bag

### MappedCollection

### Set

### Dictionary

IdentityDictionary

### Stream

PositionableStream

ReadStream

WriteStream

ReadWriteStream

ExternalStream

FileStream

### Random

File

FileDirectory

FilePage

### UndefinedObject

Boolean

False

True

### ProcessorScheduler

Delay

SharedQueue

### Behavior

ClassDescription

Class

MetaClass

### Point

Rectangle

BitBit

CharacterScanner

### Pen

### DisplayObject

DisplayMedium

Form

Cursor

DisplayScreen

InfiniteForm

OpaqueForm

Path

Arc

Circle

Curve

Line

LinearFit

Spline
The Smalltalk-80 system provides several classes representing objects that measure something with linear ordering. Real world examples of such measurable quantities are (1) temporal quantities such as dates and time, (2) spatial quantities such as distance, and (3) numerical quantities such as reals and rationals.

## Class Magnitude

Is one number less than another number? Does one date come after another date? Does one time precede another time? Does a character come after another one in the alphabet? Is one distance the same or less than another distance?

The common protocol for answering these queries is provided in the class Magnitude. Magnitude provides the protocol for objects that have the ability to be compared along a linear dimension. Subclasses of class Magnitude include Date, Time, and Number. Classes Character (an element of a string) and LookupKey (a key in a dictionary association) are also implemented as subclasses of class Magnitude. Character is interesting as an example of immutable objects in the system and so is introduced in this chapter; LookupKey is less interesting and is deferred until needed in the chapter on collections. A class Distance is not provided in the actual Smalltalk-80 system.

Magnitude instance protocol

comparing

< aMagnitude
Answer whether the receiver is less than the argument.

<= aMagnitude
Answer whether the receiver is less than or equal to the argument.

> aMagnitude
Answer whether the receiver is greater than the argument.

> = aMagnitude
Answer whether the receiver is greater than or equal to the argument.

between: min and: max
Answer whether the receiver is greater than or equal to the argument, min, and less than or equal to the argument, max.

Although Magnitude inherits from its superclass, Object, the message = for comparing the equality of two quantifiable objects, every kind of Magnitude must redefine this message. The method associated with = in class Magnitude is

self subclassResponsibility

If a subclass of Magnitude does not implement =, then an attempt to send the message to an instance of the subclass results in the special error message that a subclass should have implemented the message, as specified in its superclass.
An instance of a kind of Magnitude can also respond to messages that determine which of two objects that can be linearly measured is the larger or the smaller.

Magnitude instance protocol

testing

min: aMagnitude Answer the receiver or the argument, whichever has the lesser magnitude.

max: aMagnitude Answer the receiver or the argument, whichever has the greater magnitude.

Note that protocol for the equality comparisons `==`, `~==`, and `~(~)` is inherited from class `Object`. Using `Integers` as the example kinds of Magnitudes, we have

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>3 &lt;= 4</td><td>true</td></tr><tr><td>3 &gt; 4</td><td>false</td></tr><tr><td>5 between: 2 and: 6</td><td>true</td></tr><tr><td>5 between: 2 and: 4</td><td>false</td></tr><tr><td>34 min: 45</td><td>34</td></tr><tr><td>34 max: 45</td><td>45</td></tr></tbody></table>

The programmer does not create instances of Magnitude, but only of its subclasses. This is due to the fact that Magnitude is not able to implement all of the messages it specifies, indeed, that it implements one or more of these messages by the expression `self subclassResponsibility`.

## Class Date

Now that we have defined the general protocol of Magnitudes, it is possible to add additional protocol that supports arithmetic and inquiries about specific linear measurements. The first refinement we will examine is the subclass `Date`.

An instance of `Date` represents a specific day since the start of the Julian calendar. A day exists in a particular month and year. Class `Date` knows about some obvious information: (1) there are seven days in a week, each day having a symbolic name and an index 1, 2, ..., or 7; (2) there are 12 months in a year, each having a symbolic name and an index, 1, 2, ..., or 12; (3) months have 28, 29, 30, or 31 days; and (4) a particular year might be a leap year.

Protocol provided for the object, `Date`, supports inquiries about Dates in general as well as about a specific `Date`. Both `Date` and `Time` provide interesting examples of classes in the system for which special knowledge is attributed to and accessible from the class itself, rather than
from its instances. This "class protocol" is specified in the metaclass of the class. Let's first look at the class protocol of Date supporting general inquiries.

Date class protocol

<table><tr><td>general inquiries</td><td></td></tr><tr><td>dayOfWeek: dayName</td><td>Answer the index in a week, 1, 2, ..., or 7, of the day named as the argument, dayName.</td></tr><tr><td>nameOfDay: dayIndex</td><td>Answer a Symbol that represents the name of the day whose index is the argument, dayIndex, where 1 is Monday, 2, is Tuesday, and so on.</td></tr><tr><td>indexOfMonth: monthName</td><td>Answer the index in a year, 1, 2, ..., or 12, of the month named as the argument, monthName.</td></tr><tr><td>nameOfMonth: monthIndex</td><td>Answer a Symbol that represents the name of the month whose index is the argument, monthIndex, where 1 is January, 2, is February, and so on.</td></tr><tr><td>daysInMonth: monthName forYear: yearInteger</td><td>Answer the number of days in the month whose name is monthName in the year yearInteger (the year must be known in order to account for a leap year).</td></tr><tr><td>daysInYear: yearInteger</td><td>Answer the number of days in the year, yearInteger.</td></tr><tr><td>leapYear: yearInteger</td><td>Answer 1 if the year yearInteger is a leap year; answer 0 otherwise.</td></tr><tr><td>dateAndTimeNow</td><td>Answer an Array whose first element is the current date (an instance of class Date representing today's date) and whose second element is the current time (an instance of class Time representing the time right now).</td></tr></table>

Thus we can send the following messages.

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>Date daysInYear: 1982</td><td>365</td></tr><tr><td>Date dayOfWeek: #Wednesday</td><td>3</td></tr><tr><td>Date nameOfMonth: 10</td><td>October</td></tr><tr><td>Date leapYear: 1972</td><td>1 (meaning it is a leap year)</td></tr><tr><td>Date daysInMonth: #February forYear: 1972</td><td>29</td></tr><tr><td>Date daysInMonth: #Feb forYear: 1971</td><td>28</td></tr></tbody></table>

Date is familiar with the common abbreviations for names of months.
There are four messages that can be used to create an instance of class Date. The one commonly used in the Smalltalk-80 system, notably for marking the creation date of a file, is Date today.

Date class protocol

<table><tr><td>instance creation</td><td></td></tr><tr><td>today</td><td>Answer an instance of Date representing the day the message is sent.</td></tr><tr><td>fromDays: dayCount</td><td>Answer an instance of Date that is dayCount number of days before or after January 1, 1901 (depending on the sign of the argument).</td></tr><tr><td>newDay: day month: monthName year: yearInteger</td><td>Answer an instance of Date that is day number of days into the month named monthName in the year yearInteger.</td></tr><tr><td>newDay: dayCount year: yearInteger</td><td>Answer an instance of Date that is dayCount number of days after the beginning of the year yearInteger.</td></tr></table>

Four examples of instance creation messages are

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>Date today</td><td>3 February 1982</td></tr><tr><td>Date fromDays: 200</td><td>20 July 1901</td></tr><tr><td>Date newDay: 6 month: #Feb year: 82</td><td>6 February 1982</td></tr><tr><td>Date newDay: 3 year: 82</td><td>3 January 1982</td></tr></tbody></table>

Messages that can be sent to an instance of Date are categorized as accessing, inquiries, arithmetic, and printing messages. Accessing and inquiries about a particular day consist of

* the day index, month index, or year

* the number of seconds, days, or months since some other date

* the total days in the date's month or year

* the days left in the date's month or year

* the first day of the date's month

* the name of the date's weekday or month

* the date of a particular weekday previous to the instance

Simple arithmetic is supported in the protocol of class Date.
Date instance protocol

arithmetic

<table><tr><td><code>addDays:</code> <code>dayCount</code></td><td>Answer a Date that is dayCount number of days after the receiver.</td></tr><tr><td><code>subtractDays:</code> <code>dayCount</code></td><td>Answer a Date that is dayCount number of days before the receiver.</td></tr><tr><td><code>subtractDate:</code> <code>aDate</code></td><td>Answer an Integer that represents the number of days between the receiver and the argument, aDate.</td></tr></table>

Such arithmetic is useful, for example, in order to compute due dates for books in a library or fines for late books. Suppose `dueDate` is an instance of `Date` denoting the day a book was supposed to be returned to the library. Then

`Date today subtractDate: dueDate`

computes the number of days for which the borrower should be fined. If a book is being borrowed today and it can be kept out for two weeks, then

`Date today addDays: 14`

is the due date for the book. If the librarian wants to quit work 16 days before Christmas day, then the date of the last day at work is

`(Date newDay: 25 month: #December year: 1982) subtractDays: 16`

An algorithm to determine the fine a borrower must pay might first compare today's date with the due date and then, if the due date has past, determine the fine as a 10-cent multiple of the number of days overdue.

```java
Date today < dueDate
    ifTrue: [fine ← 0]
    ifFalse: [fine ← 0.10 * (Date today subtractDate: dueDate)]
```

Class Time

An instance of class `Time` represents a particular second in a day. `Days` start at midnight. `Time` is a subclass of `Magnitude`. Like class `Date`, `Time` can respond to general inquiry messages that are specified in the class protocol.
Time class protocol

general inquiries

millisecondClockValue

Answer the number of milliseconds since the
millisecond clock was last reset or rolled over
to 0.

millisecondsToRun: timedBlock

Answer the number of milliseconds
timedBlock takes to return its value.

timeWords

Answer the seconds (in Greenwich Mean Time) since Jan. 1, 1901. The answer is a four-element ByteArray (ByteArray is described in Chapter 10).

totalSeconds

Answer the total seconds from Jan. 1, 1901,
corrected for time zone and daylight savings
time.

dateAndTimeNow

Answer an Array whose first element is the
current date (an instance of class Date that
represents today's date) and whose second ele-
ment is the current time (an instance of class
Time that represents the time right now). The
result of sending this message to Time is iden-
tical to the result of sending it to Date.

The only non-obvious inquiry is millisecondsToRun: timedBlock. An example is

Time millisecondsToRun: [Date today]

where the result is the number of milliseconds it took the system to compute today's date. Because there is some overhead in responding to this message, and because the resolution of the clock affects the result, the careful programmer should determine the machine-dependent uncertainties associated with selecting reasonable arguments to this message.

A new instance of Time can be created by sending Time the message now; the corresponding method reads the current time from a system clock. Alternatively, an instance of Time can be created by sending the message fromSeconds: secondCount, where secondCount is the number of seconds since midnight.

Time class protocol

instance creation

now

Answer an instance of Time representing the
second the message is sent.

fromSeconds: secondCount

Answer an instance of Time that is
secondCount number of seconds since mid-
night.

Accessing protocol for instances of class Time provide information as to
the number of hours (hours), minutes (minutes) and seconds (seconds)
that the instance represents.

Arithmetic is also supported.

Time instance protocol

arithmetic

addTime: timeAmount Answer an instance of Time that is the argument, timeAmount, after the receiver.

subtractTime: timeAmount Answer an instance of Time that is the argument, timeAmount, before the receiver.

In the messages given above, the arguments (timeAmount) may be either Dates or Times. For this to be possible, the system must be able to convert a Date and a Time to a common unit of measurement; it converts them to seconds. In the case of Time, the conversion is to the number of seconds since midnight; in the case of Date, the conversion is to the number of seconds between a time on January 1, 1901, and the same time in the receiver's day. To support these methods, instances of each class respond to the conversion message asSeconds.

Time instance protocol

converting

asSeconds Answer the number of seconds since midnight that the receiver represents.

Date instance protocol

converting

asSeconds Answer the number of seconds between a time on January 1, 1901, and the same time in the receiver's day.

Arithmetic for Time can be used in ways analogous to that for Date. Suppose the amount of time a person spends working on a particular project is to be logged so that a customer can be charged an hourly fee. Suppose the person started work at startTime and worked continuously during the day until right now; the phone rings and the customer wants to know today's charges. At that moment, the bill at $5.00 an hour is

(Time now subtractTime: startTime) hours * 5

ignoring any additional minutes or seconds. If a charge for any fraction of an hour over 30 minutes is to be charged as a full hour then an additional $5.00 is added if

(Time now subtractTime: startTime) minutes > 30
Who is more productive, the worker who finished the job with time logged at timeA or the worker with time timeB? The answer is the first worker if timeA < timeB. Comparing protocol is inherited from the superclasses Magnitude and Object.

Suppose times are computed across days, for example, in computing the time of a car in a four-day rally. If the first day of the rally started at timeTime on day startDate, then the time for a car arriving at the finish line right now is computed as follows.

Let the start time be 6:00 a.m.

startTime <- Time fromSeconds: (60*60*6).

on February 2, 1982

startDate <- Date newDay: 2 month: #Feb year: 82.

The time that has passed up to the start of the current day is

todayStart <- (((Time fromSeconds: 0) addTime: Date today) subtractTime:datesubtractTime: timeTime)

That is, add all the seconds since Jan. 1, 1901, up to the start of today and then subtract all the seconds since Jan. 1, 1901, up to the start of the start date. This is equivalent to adding the number of seconds in the number of elapsed days, but then the programmer would have to do all the conversions.

(Date today subtractDate:datesubtractTime: timeTime) * 24*60*60)

By adding the current time, we have the elapsed rally time for the car.

todayStart addTime: Time now

Class Character

Class Character is the third subclass of class Magnitude we shall examine. It is a kind of Magnitude because instances of class Character form an ordered sequence about which we can make inquiries such as whether one character precedes (>) or succeeds (<) another character alphabetically. There are 256 instances of class Character in the system. Each one is associated with a code in an extended ASCII character set.

Characters can be expressed literally by preceding the alphabetic character by a dollar sign ($); thus, $A is the Character representing the capital letter "A". Protocol for creating instances of class Character consists of
Character class protocol

instance creation

value: anInteger

Answer an instance of Character whose value is the argument, anInteger. The value is associated with an element of the ASCII character set. For example, Character value: 65 is a capital "A".

digitValue: anInteger

Answer an instance of Character whose digit value is the argument, anInteger. For example, answer $9 if the argument is 9; answer $0 for 0; answer $A for 10, and $Z for 35. This method is useful in parsing numbers into strings. Typically, only Characters up to $F are useful (for base 16 numbers).

Class protocol, that is, the set of messages to the object Character, provides a vocabulary for accessing characters that are not easy to distinguish when printed: backspace, cr, esc, newPage (that is, form feed), space, and tab.

Messages to instances of Character support accessing the ASCII value and the digit value of the instance and testing the type of character. The only state of a Character is its value which can never change. Objects that can not change their internal state are called *immutable objects*. This means that, once created, they are not destroyed and then recreated when they are needed again. Rather, the 256 instances of Character are created at the time the system is initialized and remain in the system. Whenever a new Character whose code is between 0 and 255 is requested, a reference is provided to an already existing Character. In this way the 256 Characters are unique. Besides Characters, the Smalltalk-80 system includes SmallIntegers and Symbols as immutable objects.

Character instance protocol

accessing

asciiValue

Answer the number corresponding to the ASCII encoding for the receiver.

digitValue

Answer the number corresponding to the numerical radix represented by the receiver (see the instance creation message digitValue: for the correspondences).

testing

isAlphaNumeric

Answer true if the receiver is a letter or a digit.

isDigit

Answer whether the receiver is a digit.

isLetter

Answer whether the receiver is a letter.

isLowercase

Answer whether the receiver is a lowercase letter.

isUppercase

Answer whether the receiver is an uppercase letter.
isSeparator

Answer whether the receiver is one of the separator characters in the expression syntax: space, cr, tab, line feed, or form feed.

isVowel

Answer whether the receiver is one of the vowels: a, e, i, o, or u, in upper or lowercase.

Instance protocol also provides conversion of a character into upper- or lowercase (asLowercase and asUppercase) and into a symbol (asSymbol).

A simple alphabetic comparison demonstrates the use of comparing protocol for instances of Character. Suppose we wish to know if one string of characters precedes another string in the telephone book. Strings respond to the message at: to retrieve the element whose index is the argument; elements of Strings are Characters. Thus 'abc' at: 2 is $b. In the following we assume we are specifying a method in class String whose message selector is min:. The method returns a String, either the receiver of the message min: or its argument, whichever is related first alphabetically.

min: aString

1 to: self size do:

[ :index |
  (index > aString size) ifTrue: [↑aString].
  (self at: index) > (aString at: index) ifTrue: [↑aString].
  (self at: index) < (aString at: index) ifTrue: [↑self]].

↑self

The algorithm consists of two statements. The first is an iteration over each element of the receiver. The iteration stops when either (1) the argument, aString, no longer has a character with which to compare the next character in the receiver (i.e., index > aString size); (2) the next character in self comes after the next character in aString (i.e., (self at: index) > (aString at: index)); or (3) the next character in self comes before the next character in aString. As an example of (1), take the comparison of 'abcd' and 'abc' which terminates when index = 4; the answer is that 'abc' is first alphabetically. For (2), suppose we compare 'abde' with 'abce'. When index = 3, $d > $c is true; the answer is 'abce'. For (3), compare 'az' with 'by' which terminates when index = 1; the answer is 'az'. In the case that the receiver has fewer characters than the argument, even when the receiver is the initial substring of the argument, the first statement will complete and the second statement is evaluated; the result is the receiver. An example is the comparison of 'abc' and 'abcd'.

Note that arithmetic on characters is not supported. For example, the following expression is incorrect.

$$a \leftarrow \$A + 1$$

The error occurs because a Character does not understand the message +.
# Numerical Classes

Protocol of the Number Classes

Classes Float and Fraction

Integer Classes

Class Random: A Random Number Generator

<figure><img src="image_104.png" /></figure>
Object

Magnitude

Character

Date

Time

Stream

PositionableStream

ReadStream

WriteStream

ReadWriteStream

ExternalStream

FileStream

Number

Float

Fraction

Integer

LargeNegativeInteger

LargePositiveInteger

SmallInteger

Random

File

FileDirectory

FilePage

LookupKey

Association

UndefinedObject

Boolean

False

True

Link

Process

Collection

SequenceableCollection

LinkedList

Semaphore

ArrayedCollection

Array

Bitmap

DisplayBitmap

RunArray

String

Symbol

Text

ByteArray

Interval

OrderedCollection

SortedCollection

Bag

MappedCollection

Set

Dictionary

IdentityDictionary

ProcessorScheduler

Delay

SharedQueue

Behavior

ClassDescription

Class

MetaClass

Point

Rectangle

BitBit

CharacterScanner

Pen

DisplayObject

DisplayMedium

Form

Cursor

DisplayScreen

InfiniteForm

OpaqueForm

Path

Arc

Circle

Curve

Line

LinearFit

Spline
One of the major goals of the Smalltalk programming system is to apply a single metaphor for information processing as uniformly as possible. The Smalltalk metaphor, as described in earlier chapters, is one of objects that communicate by sending messages. This metaphor is very similar to the one used in Simula for implementing simulation systems. One of the greatest challenges to the application of the Smalltalk metaphor to all aspects of a programming system has been in the area of arithmetic. Simula used the object message metaphor only for the higher level interactions in the simulations it implemented. For arithmetic, as well as most algorithmic control structures, Simula relied on the embedded Algol programming language with its built-in number representations, operations, and syntax. The contention that even the addition of two integers should be interpreted as message-sending met with a certain amount of resistance in the early days of Smalltalk. Experience has demonstrated that the benefits of this extreme uniformity in the programming language outweigh any inconvenience in its implementation. Over several versions of Smalltalk, implementation techniques have been developed to reduce the message-sending overhead for the most common arithmetic operations so that there is now almost no cost for the benefits of uniformity.

Objects that represent numerical values are used in most systems done in Smalltalk (as with most other programming languages). Numbers are naturally used to perform mathematical computations; they are also used in algorithms as indices, counters, and encodings of states or conditions (often called flags). Integral numbers are also used as collections of binary digits (bits) that perform boolean masking operations with each other.

Each different kind of numerical value is represented by a class. The number classes have been implemented so that all numbers behave as if they were of the most general type. The actual class of a particular number object is determined by how much of the full generality is needed to represent its value. Therefore the external protocol of all number objects is inherited from the class Number. Number has three subclasses: Float, Fraction, and Integer. Integer has three subclasses: SmallInteger, LargePositiveInteger, and LargeNegativeInteger. Integral numbers provide further protocol to support treating the number as a sequence of bits. This protocol is specified in the class Integer. Numbers in the system are instances of Float, Fraction, SmallInteger, LargePositiveInteger, or LargeNegativeInteger. Classes Number and Integer specify shared protocol, but they do not specify particular representations for numeric values. Therefore no instances of Number or Integer are created.

Unlike other objects that may change their internal state, the only state of a number is its value, which should never change. The object 3, for example, should never change its state to 4, or disastrous effects could occur.
## Protocol of the Number Classes

Number defines the protocol of all numeric objects. Its messages support standard arithmetic operations and comparisons. Most of these must be implemented by subclasses of Number since they depend on the actual representation of values.

The protocol of arithmetic messages consists of the usual binary operators such as +, -, * and /, and several unary and keyword messages for computing the absolute value of a number, the negation of a number, or the integer quotient or remainder of a number. The category for arithmetic messages is as follows.

### Number instance protocol

#### arithmetic

* `+ aNumber` Answer the sum of the receiver and the argument, aNumber.

* `- aNumber` Answer the difference between the receiver and the argument, aNumber.

* `* aNumber` Answer the result of multiplying the receiver by the argument, aNumber.

* `/ aNumber` Answer the result of dividing the receiver by the argument, aNumber. Note that since as much precision as possible is retained, if the division is not exact, the result will be an instance of Fraction.

* `// aNumber` Answer the integer quotient defined by division with truncation toward negative infinity.

* `\\ aNumber` Answer the integer remainder defined by division with truncation toward negative infinity. This is the modulo operation.

* `abs` Answer a Number that is the absolute value (positive magnitude) of the receiver.

* `negated` Answer a Number that is the negation of the receiver.

* `quo: aNumber` Answer the integer quotient defined by division with truncation toward zero.

* `rem: aNumber` Answer the integer remainder defined by division with truncation toward zero.

* `reciprocal` Answer 1 divided by the receiver. Report an error to the user if the receiver is 0.

Some examples follow.

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>1 + 10</td><td>11</td></tr><tr><td>5.6 - 3</td><td>2.6</td></tr><tr><td>5 - 2.6</td><td>2.4</td></tr><tr><td>(-4) abs</td><td>4</td></tr><tr><td>6 / 2</td><td>3</td></tr></tbody></table>
<table><tr><td>7 / 2</td><td>(7/2), a Fraction with numerator 7 and denominator 2</td></tr><tr><td>7 reciprocal</td><td>(1/7), a Fraction with numerator 1 and denominator 7</td></tr></table>

Arithmetic messages that return integral quotients and remainders from a division operation follow two conventions. One convention truncates the resulting number toward zero, the other toward negative infinity. These are the same for positive results since zero and negative infinity are in the same direction. For negative results, the two conventions round in different directions. The protocol for Number provides for both conventions.

The following table shows the relationships among the selectors.

<table><thead><tr><th>result</th><th>truncate toward<br>negative infinity</th><th>truncate toward zero</th></tr></thead><tbody><tr><td>quotient</td><td>//</td><td>quo:</td></tr><tr><td>remainder</td><td>\\</td><td>rem:</td></tr></tbody></table>

Examples include:

<table><thead><tr><th>expression</th><th>result</th></tr></thead><tbody><tr><td>6 quo: 2</td><td>3</td></tr><tr><td>7 quo: 2</td><td>3</td></tr><tr><td>(7 quo: 2) + 1</td><td>4</td></tr><tr><td>7 quo: 2 + 1</td><td>2</td></tr><tr><td>7 rem: 2</td><td>1</td></tr><tr><td>7 // 2</td><td>3</td></tr><tr><td>7 \ 2</td><td>1</td></tr><tr><td>7 \ 2 + 1</td><td>2</td></tr><tr><td>-7 quo: 2</td><td>-3</td></tr><tr><td>-7 rem: 2</td><td>-1</td></tr><tr><td>-7 // 2</td><td>-4</td></tr><tr><td>-7 \ 2</td><td>1</td></tr></tbody></table>

The result of quo:, rem:, or // is always to return a value whose sign is positive if the receiver and argument have the same sign, and negative if their signs are different. \\ always produces a positive result.

Additional mathematical functions are
Number instance protocol

mathematical functions

exp
Answer a floating point number that is the exponential of the receiver.

In
Answer the natural log of the receiver.

log: aNumber
Answer the log base aNumber of the receiver.

floorLog: radix
Answer the floor of the log base radix of the receiver, where the floor is the integer nearest the receiver toward negative infinity.

raisedTo: aNumber
Answer the receiver raised to the power of the argument, aNumber.

raisedToInteger: anInteger
Answer the receiver raised to the power of the argument, anInteger, where the argument must be a kind of Integer.

sqrt
Answer a floating point number that is the positive square root of the receiver.

squared
Answer the receiver multiplied by itself.

Some examples are

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>2.718284 In</td><td>1.0</td></tr><tr><td>6 exp</td><td>403.429</td></tr><tr><td>2 exp</td><td>7.38906</td></tr><tr><td>7.38906 In</td><td>1.99998 (that is, 2)</td></tr><tr><td>2 log: 2</td><td>1.0</td></tr><tr><td>2 floorLog: 2</td><td>1</td></tr><tr><td>6 log: 2</td><td>2.58496</td></tr><tr><td>6 floorLog: 2</td><td>2</td></tr><tr><td>6 raisedTo: 1.2</td><td>8.58579</td></tr><tr><td>6 raisedToInteger: 2</td><td>36</td></tr><tr><td>64 sqrt</td><td>8.0</td></tr><tr><td>8 squared</td><td>64</td></tr></tbody></table>

Properties of numbers that deal with whether a number is even or odd and negative or positive can be tested with the following messages.

Number instance protocol

testing

even
Answer whether the receiver is an even number.

odd
Answer whether the receiver is an odd number.

negative
Answer whether the receiver is less than 0.

positive
Answer whether the receiver is greater than or equal to 0.

strictlyPositive
Answer whether the receiver is greater than 0.

sign
Answer 1 if the receiver is greater than 0, answer -1 if less than 0, else answer 0.
Properties of numbers that deal with truncation and round off are supplied by the following protocol.

Number instance protocol

<table><tr><td>truncation and round off</td><td></td></tr><tr><td>ceiling</td><td>Answer the integer nearest the receiver toward positive infinity.</td></tr><tr><td>floor</td><td>Answer the integer nearest the receiver toward negative infinity.</td></tr><tr><td>truncated</td><td>Answer the integer nearest the receiver toward zero.</td></tr><tr><td>truncateTo: aNumber</td><td>Answer the next multiple of the argument, aNumber, that is nearest the receiver toward zero.</td></tr><tr><td>rounded</td><td>Answer the integer nearest the receiver.</td></tr><tr><td>roundTo: aNumber</td><td>Answer the multiple of the argument, aNumber, that is nearest the receiver.</td></tr></table>

Whenever a Number must be converted to an Integer, the message truncated can be used. So we have

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>16.32 ceiling</td><td>17</td></tr><tr><td>16.32 floor</td><td>16</td></tr><tr><td>-16.32 floor</td><td>-17</td></tr><tr><td>-16.32 truncated</td><td>-16</td></tr><tr><td>16.32 truncated</td><td>16</td></tr><tr><td>16.32 truncateTo: 5</td><td>15</td></tr><tr><td>16.32 truncateTo: 5.1</td><td>15.3</td></tr><tr><td>16.32 rounded</td><td>16</td></tr><tr><td>16.32 roundTo: 6</td><td>18</td></tr><tr><td>16.32 roundTo: 6.3</td><td>18.9</td></tr></tbody></table>

The protocol provided in class Number includes various messages for converting a number into another kind of object or a different unit of representation. Numbers can represent various unit measurements such as degrees and radians. The following two messages perform conversions.

Number instance protocol

<table><tr><td>converting</td><td></td></tr><tr><td>degreesToRadians</td><td>The receiver is assumed to represent degrees. Answer the conversion to radians.</td></tr><tr><td>radiansToDegrees</td><td>The receiver is assumed to represent radians. Answer the conversion to degrees.</td></tr></table>

So that

$$30 \text{ degreesToRadians} = 0.523599$$ $$90 \text{ degreesToRadians} = 1.5708$$
Trigonometric and logarithmic functions are included in the protocol for mathematical functions. The receiver for the trigonometric functions cos, sin, and tan is an angle measured in radians; the result of the functions arcCos, arcSin and arcTan is the angle measured in radians.

In the following examples, 30 degrees is given as 0.523599 radians; 90 degrees is 1.5708 radians.

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>0.523599 sin</td><td>0.5</td></tr><tr><td>0.523599 cos</td><td>0.866025</td></tr><tr><td>0.523599 tan</td><td>0.57735</td></tr><tr><td>1.5708 sin</td><td>1.0</td></tr><tr><td>0.57735 arcTan</td><td>0.523551</td></tr><tr><td>1.0 arcSin</td><td>1.5708</td></tr></tbody></table>

When a kind of Integer is asked to add itself to another kind of Integer, the result returned will naturally also be a kind of Integer. The same is true for the sum of two Floats; the class of the result will be the same as the class of the operands. If the two operands are SmallIntegers and the absolute value of their sum is too large to be represented as a SmallInteger, the result will be a LargePositiveInteger or a LargeNegativeInteger. The determination of the appropriate class of result when the operands are of different classes is somewhat more complicated. Two design criteria are that there be as little loss of information as possible and that commutative operations produce the same result regardless of which operand is the receiver of the message and which is the argument. So for example, 3.1 * 4 will return the same result as 4 * 3.1.

The appropriate representation for the result of operations on numbers of different classes is determined by a numerical measure of generality assigned to each class. Classes said to have more generality will have a larger number for this generality measure. Each class must be able to convert its instances into equal-valued instances of more general classes. The measure of generality is used to decide which of the operands should be converted. In this way, the arithmetic operations obey the law of commutativity with no loss of numerical information. When the differences between two classes of numbers are only a matter of precision (where "precision" is a measure of the information provided in a number), the more precise class is assigned a higher degree of generality. We have arbitrarily assigned approximate numbers a higher generality in cases where precision was not the issue (so, Float is more general than Fraction).

The generality hierarchy for the kinds of numbers in the Smalltalk-80 system, with most general listed first, is
Float

Fraction

LargePositiveInteger, LargeNegativeInteger

SmallInteger

The messages in the Number protocol designed to support the necessary coercions are categorized as "coercing" messages.

Number instance protocol

coercing

coerce: aNumber

Answer a number representing the argument, aNumber, that is the same kind of Number as the receiver. This method must be defined by all subclasses of Number.

generality

Answer the number representing the ordering of the receiver in the generality hierarchy.

retry: aSymbol coercing: aNumber

An arithmetic operation denoted by the sym-
bol, aSymbol, could not be performed with the
receiver and the argument, aNumber, as the
operands because of the difference in repre-
sentation. Coerce either the receiver or the ar-
gument, depending on which has the lower
generality, and then try the arithmetic opera-
tion again. If the symbol is the equals sign,
answer false if the argument is not a Number.
If the generalities are the same, then
retry:coercing: should not have been sent, so
report an error to the user.

Thus if we try to evaluate 32.45 * 4, the multiplication of a Float by a SmallInteger will result in evaluating the expression

32.45 retry: #* coercing: 4

and the argument 4 will be coerced to 4.0 (Float has higher generality than SmallInteger). Then the multiplication will be carried out successfully.

Defining a hierarchy of the numbers in terms of a numerical mea-
sure of generality works for the kinds of numbers provided in the basic
Smalltalk-80 system because the generality is transitive for these kinds
of numbers. However, it does not provide a technique that can be used
for all kinds of numbers.

Intervals (described in detail in Chapter 10) can be created by sending
one of two messages to a number. For each element of such an interval,
a block can be evaluated with the element as the block value.
Number instance protocol

intervals

to: stop
Answer an Interval from the receiver up to the argument, stop, with each next element computed by incrementing the previous one by 1.

to: stop by: step
Answer an Interval from the receiver up to the argument, stop, with each next element computed by incrementing the previous one by step.

to: stop do: aBlock
Create an Interval from the receiver up to the argument, stop, incrementing by 1. Evaluate the argument, aBlock, for each element of the Interval.

to: stop by: step do: aBlock
Create an Interval from the receiver up to the argument, stop, incrementing by step. Evaluate the argument, aBlock, for each element of the Interval.

Thus if we evaluate

a = 0.

10 to: 100 by: 10 do: [ :each | a = a + each]

the final value of a will be 550.

If a is the array #('one' 'two' 'three' 'four' 'five'), then each element of the array can be accessed by indices that are in the interval from 1 to the size of the array. The following expression changes each element so that only the initial characters are kept.

1 to: a size do: [ :index | a at: index put: ((a at: index) at: 1)]

The resulting array is #('o' 't' 't' 'f' 'f'). Note that, like an array, elements of a string can be accessed using the messages at: and at:put:. Messages to objects like strings and arrays are detailed in Chapters 9 and 10.

## Classes Float and Fraction

The classes Float and Fraction provide two representations of non-integral values. Floats are representations of real numbers that may be approximate; they represent about 6 digits of accuracy with a range between plus or minus 10 raised to the power plus or minus 32. Some examples are

8.0

13.3
0.3
2.5e6
1.27e-30
-12.987654e12

Fractions are representations of rational numbers that will always be exact. All arithmetic operations on a Fraction answer a reduced fractional result.

Instances of Float can be created by literal notation in methods (for example, 3.14159) or as the result of an arithmetic operation, one argument of which is another Float.

Instances of Fraction can be created as a result of an arithmetic operation if one of the operands is a Fraction and the other is not a Float. (If it were a Float, the result would be a Float since the generality number of Float is higher than that of Fraction). Instances of Fraction can also be created when the mathematical division operation (`/`) is performed on two Integers and the result is not integral. In addition, class protocol for Fraction supports sending a message of the form numerator: `numInteger` denominator: `denInteger` in order to create an instance.

Float responds to the message `pi` to return the corresponding constant. It adds truncation and round off protocol to return the fraction and integer parts of the receiver (`fractionPart` and `integerPart`), and it adds converting protocol to convert the receiver to a Fraction (`asFraction`). Similarly class Fraction adds converting protocol to convert the receiver to a Float (`asFloat`).

## Integer Classes

Class `Integer` adds protocol particular to integral numbers. It has three subclasses. One is class `SmallInteger`, which provides a space-economical representation for a substantial range of integral values that occur frequently in counting and indexing. The representation limits the range to a little less than the magnitudes representable by a single machine word. Large integers, which are represented by instances of `LargePositiveInteger` or `LargeNegativeInteger` depending on the sign of the integer, do not have a limit to their magnitude. The cost in providing the generality of large integers is longer computation time. Thus if the result of an arithmetic operation on a large integer is representable as a small integer, it will in fact be a small integer.

In addition to the messages inherited from the class `Number`, class `Integer` adds converting protocol (`asCharacter`, `asFloat` and `asFraction`), further printing (`printOn`: a stream base: b, radix: `baseInteger`), and enumerating protocol. Thus 8 radix: 2 is `2r1000`.
For enumerating, it is possible to evaluate a block repetitively an integral number of times using the message timesRepeat: aBlock. Take as an example

a ← 1.

10 timesRepeat: [a ← a + a]

where the block has no arguments. The resulting value of a is 2¹⁰, or 1024.

Class Integer provides factorization and divisibility protocol not specified for numbers in general.

Integer instance protocol

factorization and divisibility

factorial

Answer the factorial of the receiver. The receiver must not be less than 0.

gcd: anInteger

Answer the greatest common divisor of the receiver and the argument, aninteger.

lcm: anInteger

Answer the least common multiple of the receiver and the argument, aninteger.

Examples are

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>3 factorial</td><td>6</td></tr><tr><td>55 gcd: 30</td><td>5</td></tr><tr><td>6 lcm: 10</td><td>30</td></tr></tbody></table>

In addition to the numerical properties of integers, some algorithms make use of the fact that integers can be interpreted as a sequence of bits. Thus protocol for bit manipulation is specified in Integer.

Integer instance protocol

bit manipulation

allMask: anInteger

Treat the argument anInteger as a bit mask. Answer whether *all* of the bits that are 1 in anInteger are 1 in the receiver.

anyMask: anInteger

Treat the argument anInteger as a bit mask. Answer whether *any* of the bits that are 1 in anInteger are 1 in the receiver.

noMask: anInteger

Treat the argument anInteger as a bit mask. Answer whether *none* of the bits that are 1 in anInteger are 1 in the receiver.

bitAnd: anInteger

Answer an Integer whose bits are the logical *and* of the receiver's bits and those of the argument anInteger.

bitOr: anInteger

Answer an Integer whose bits are the logical *or* of the receiver's bits and those of the argument anInteger.
<table><tr><td>bitXor: anInteger</td><td>Answer an Integer whose bits are the logical xor of the receiver's bits and those of the argument anInteger.</td></tr><tr><td>bitAt: index</td><td>Answer the bit (0 or 1) at position index of the receiver.</td></tr><tr><td>bitInvert</td><td>Answer an Integer whose bits are the complement of the receiver.</td></tr><tr><td>highBit</td><td>Answer the index of the high order bit of the binary representation of the receiver.</td></tr><tr><td>bitShift: anInteger</td><td>Answer an Integer whose value (in two's-complement representation) is the receiver's value (in two's-complement representation) shifted left by the number of bits indicated by the argument, anInteger. Negative arguments shift right. Zeros are shifted in from the right in left shifts. The sign bit is extended in right shifts.</td></tr></table>

Some examples follow. Note that the default radix for printing an Integer is 10.

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>2r111000111000111</td><td>29127</td></tr><tr><td>2r101010101010101</td><td>21845</td></tr><tr><td>2r101000101000101</td><td>20805</td></tr><tr><td>2r000111000111000</td><td>3640</td></tr><tr><td>29127 allMask: 20805</td><td>true</td></tr><tr><td>29127 allMask: 21845</td><td>false</td></tr><tr><td>29127 anyMask: 21845</td><td>true</td></tr><tr><td>29127 noMask: 3640</td><td>true</td></tr><tr><td>29127 bitAnd: 3640</td><td>0</td></tr><tr><td>29127 bitOr: 3640</td><td>32767</td></tr><tr><td>32767 radix: 2</td><td>2r111111111111111</td></tr><tr><td>29127 bitOr: 21845</td><td>30167</td></tr><tr><td>30167 radix: 2</td><td>2r111010111010111</td></tr><tr><td>3640 bitShift: 1</td><td>7280</td></tr></tbody></table>

Class Random:
A Random
Number
Generator

Many applications require random choices of numbers. Random numbers are useful, for example, in statistical applications and data encryption algorithms. Class Random is a random number generator that is included in the standard Smalltalk-80 system. It provides a simple way of obtaining a sequence of random numbers that will be uniformly distributed over the interval between, but not including, 0.0 and 1.0.

An instance of class Random maintains a seed from which the next random number is generated. The seed is initialized in a pseudo-random
dom way. An instance of Random is sent the message next whenever a new random number is desired.

A random number generator can be created with the expression

rand ← Random new

The expression

rand next

can then be evaluated whenever a new random number is needed. The response is a number (Float) between 0.0 and 1.0.

The implementation of next is based on Lehmer's linear congruential method as presented in Knuth, Volume 1 [D. E. Knuth, *The Art of Computer Programming: Fundamental Algorithms*, Volume 1, Reading, Mass: Addison Wesley, 1968].

next

| temp |

"Lehmer's linear congruential method with modulus m = 2 raisedTo: 16, a = 27181 odd, and 5 = a \ 8, c = 13849 odd, and c / m approximately 0.21132"

[seed ← 13849 + (27181 * seed) bitAnd: 8r177777.

temp ← seed / 65536.0.

temp = 0] while True.

↑temp

It is also possible to send an instance of class Random the messages next: an `Integer`, to obtain an `OrderedCollection` of an `Integer` number of random numbers, and `nextMatchFor`: a `Number`, to determine whether the next random number is equal to a `Number`.

Suppose we want to select one of 10 integers, 1, ..., 10, using the random number generator `rand`. The expression to be evaluated is

(rand next * 10) truncated + 1

That is,

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>rand next</td><td>a random number between 0 and 1</td></tr><tr><td>rand next * 10</td><td>a random number between 0 and 10</td></tr><tr><td>(rand next * 10) truncated</td><td>an integer &gt;= 0 and &lt;= 9</td></tr><tr><td>(rand next * 10) truncated + 1</td><td>an integer &gt;= 1 and &lt;= 10</td></tr></tbody></table>
# 9

## Protocol for All
Collection Classes

### Adding, Removing, and Testing Elements

#### Enumerating Elements

*Selecting and Rejecting*

*Collecting*

*Detecting*

*Injecting*

#### Instance Creation

### Conversion Among Collection Classes

<figure><img src="image_105.png" /></figure>
## Object

### Magnitude

Character

Date

Time

### Number

Float

Fraction

Integer

LargeNegativeInteger

LargePositiveInteger

SmallInteger

### LookupKey

Association

### Link

## Process

### Collection

### SequenceableCollection

LinkedList

Semaphore

### ArrayedCollection

Array

### Bitmap

DisplayBitmap

RunArray

String

Symbol

Text

ByteArray

### Interval

### OrderedCollection

SortedCollection

Bag

MappedCollection

Set

### Dictionary

IdentityDictionary

### Stream

PositionableStream

ReadStream

WriteStream

ReadWriteStream

ExternalStream

FileStream

### Random

File

FileDirectory

FilePage

UndefinedObject

Boolean

False

True

### ProcessorScheduler

Delay

SharedQueue

### Behavior

ClassDescription

Class

MetaClass

Point

Rectangle

BitBit

CharacterScanner

Pen

### DisplayObject

DisplayMedium

Form

Cursor

DisplayScreen

InfiniteForm

OpaqueForm

Path

Arc

Circle

Curve

Line

LinearFit

Spline
A collection represents a group of objects. These objects are called the *elements* of the collection. For example, an *Array* is a collection. The *Array*

`(#( 'word' 3 5 $G (1 2 3))`

is a collection of five elements. The first one is a *String*, the second and third are *SmallIntegers*, the fourth element is a *Character*, and the fifth is itself an *Array*. The first element, the *String*, is also a collection; in this case, it is a collection of four *Characters*.

Collections provide basic data structures for programming in the Smalltalk-80 system. Elements of some of the collections are unordered and elements of other collections are ordered. Of the collections with unordered elements, *Bags* allow duplicate elements and *Sets* do not allow duplication. There are also *Dictionaries* that associate pairs of objects. Of the collections with ordered elements, some have the order specified externally when the elements are added (*OrderedCollections*, *Arrays*, *Strings*) and others determine the order based on the elements themselves (*SortedCollections*). For example, the common data structures of arrays and strings are provided by classes that associate integer indices and elements and that have external ordering corresponding to the ordering of the indices.

This chapter introduces the protocol shared by all collections. Each message described in this chapter is understood by any kind of collection, unless that collection specifically disallows it. Descriptions of each kind of collection are provided in the next chapter.

Collections support four categories of messages for accessing elements:

* messages for adding new elements

* messages for removing elements

* messages for testing occurrences of elements

* messages for enumerating elements

A single element or several elements can be added or removed from a collection. It is possible to test whether a collection is empty or whether it includes a particular element. It is also possible to determine the number of times a particular element occurs in the collection. Enumeration allows one to access the elements without removing them from the collection.
Adding,
Removing,
and Testing
Elements

The basic protocol for collections is specified by the superclass of all collection classes, named Collection. Class Collection is a subclass of class Object. The protocol for adding, removing, and testing elements follows.

Collection instance protocol

adding

add: newObject
Include the argument, newObject, as one of the receiver's elements. Answer newObject.

ADD: aCollection
Include all the elements of the argument, aCollection, as the receiver's elements. Answer aCollection.

removing

remove: oldObject
Remove the argument, oldObject, from the receiver's elements. Answer oldObject unless no element is equal to oldObject, in which case, report that an error occurred.

remove: oldObject ifAbsent: anExceptionBlock
Remove the argument, oldObject, from the receiver's elements. If several of the elements are equal to oldObject, only one is removed. If no element is equal to oldObject, answer the result of evaluating anExceptionBlock. Otherwise, answer oldObject.

removeAll: aCollection
Remove each element of the argument, aCollection, from the receiver. If successful for each, answer aCollection. Otherwise report that an error occurred.

testing

includes: anObject
Answer whether the argument, anObject, is equal to one of the receiver's elements.

isEmpty
Answer whether the receiver contains any elements.

occurrencesOf: anObject
Answer how many of the receiver's elements are equal to the argument, anObject.

In order to demonstrate the use of these messages, we introduce the collection lotteryA

(272 572 852 156)

and the collection lotteryB

(572 621 274)

We will assume that these two collections, representing numbers drawn in a lottery, are instances of Bag, a subclass of Collection. Collection itself is abstract in the sense that it describes protocol for all collections. Collection does not provide sufficient representation for storing elements and so it is not possible to provide implementations in Collection
of all of its messages. Because of this incompleteness in the definition of Collection, it is not useful to create instances of Collection. Bag is concrete in the sense that it provides a representation for storing elements and implementations of the messages not implementable in its superclass.

All collections respond to size in order to answer the number of their elements. So we can determine that

lotteryA size

is 4 and

lotteryB size

is 3. Then, evaluating the messages in order, we have

<table><thead><tr><td>expression</td><td>result</td><td>lotteryA if it changed</td></tr></thead><tbody><tr><td>lotteryA empty</td><td>false</td><td></td></tr><tr><td>lotteryA includes: 572</td><td>true</td><td></td></tr><tr><td>lotteryA add: 596</td><td>596</td><td>Bag (272 572 852 156 596)</td></tr><tr><td>lotteryA addAll: lotteryB</td><td>Bag (572 621 274)</td><td>Bag (272 274 852 156 596 572 572 621)</td></tr><tr><td>lotteryA occurrencesOf: 572</td><td>2</td><td></td></tr><tr><td>lotteryA remove: 572</td><td>572</td><td>Bag (272 274 852 156 596 572 621)</td></tr><tr><td>lotteryA size</td><td>7</td><td></td></tr><tr><td>lotteryA removeAll: lotteryB</td><td>Bag (572 621 274)</td><td>Bag (272 852 596 156)</td></tr><tr><td>lotteryA size</td><td>4</td><td></td></tr></tbody></table>

Note that the add: and remove: messages answer the argument rather than the collection itself so that computed arguments can be accessed. The message remove: deletes only one occurrence of the argument, not all occurrences.

Blocks were introduced in Chapter 2. The message remove: oldObject ifAbsent: anExceptionBlock makes use of a block in order to specify the behavior of the collection if an error should occur. The argument anExceptionBlock is evaluated if the object referred to by oldObject is not an element of the collection. This block can contain code to deal with the error or simply to ignore it. For example, the expression

lotteryA remove: 121 ifAbsent: []

does nothing when it is determined that 121 is not an element of lotteryA.
The default behavior of the message remove: is to report the error by sending the collection the message error: 'object is not in the collection'. (Recall that the message error: is specified in the protocol for all objects and is therefore understood by any collection.)

## Enumerating Elements

Included in the instance protocol of collections are several enumeration messages that support the ability to list the elements of a collection and to supply each element in the evaluation of a block. The basic enumeration message is do: aBlock. It takes a one-argument block as its argument and evaluates the block once for each of the elements of the collection. As an example, suppose letters is a collection of Characters and we want to know how many of the Characters are a or A.

count ← 0.
letters do: [ :each | each asLowercase == $a
  ifTrue: [count ← count + 1]]

That is, increment the counter, count, by 1 for each element that is an upper- or lowercase a. The desired result is the final value of count. We can use the equivalence test (==) rather than equality since objects representing Characters are unique.

Six enhancements of the basic enumeration messages are specified in the protocol for all collections. The description of these enumeration messages indicates that "a new collection like the receiver" is created for gathering the resulting information. This phrase means that the new collection is an instance of the same class as that of the receiver. For example, if the receiver of the message select: is a Set or an Array, then the response is a new Set or Array, respectively. In the Smalltalk-80 system, the only exception is in the implementation of class Interval, which returns a new OrderedCollection, not a new Interval, from these enumeration messages. The reason for this exception is that the elements of an Interval are created when the Interval is first created; it is not possible to store elements into an existing Interval.

### Collection instance protocol

* enumerating

* do: aBlock

Evaluate the argument, aBlock, for each of the receiver's elements.

* select: aBlock

Evaluate the argument, aBlock, for each of the receiver's elements. Collect into a new collection like that of the receiver, only those elements for which aBlock evaluates to true. Answer the new collection.
reject: aBlock Evaluate the argument, aBlock, for each of the receiver's elements. Collect into a new collection like that of the receiver only those elements for which aBlock evaluates to false. Answer the new collection.

collect: aBlock Evaluate the argument, aBlock, for each of the receiver's elements. Answer a new collection like that of the receiver containing the values returned by the block on each evaluation.

detect: aBlock Evaluate the argument, aBlock, for each of the receiver's elements. Answer the first element for which aBlock evaluates to true. If none evaluates to true, report an error.

detect: aBlock ifNone: exceptionBlock Evaluate the argument, aBlock, for each of the receiver's elements. Answer the first element for which aBlock evaluates to true. If none evaluates to true, evaluate the argument, exceptionBlock. exceptionBlock must be a block requiring no arguments.

inject: thisValue into: binaryBlock Evaluate the argument, binaryBlock, once for each element in the receiver. The block has two arguments: the second is an element from the receiver; the first is the value of the previous evaluation of the block, starting with the argument, thisValue. Answer the final value of the block.

Each enumeration message provides a concise way to express a sequence of messages for testing or gathering information about the elements of a collection.

We could have determined the number of occurrences of the character a or A using the message select:

Selecting and Rejecting

(letters select: [ :each | each asLowercase == $a]) size

That is, create a collection containing only those elements of letters that are a or A, and then answer the size of the resulting collection.

We could also have determined the number of occurrences of the character a or A using the message reject:

(letters reject: [ :each | each asLowercase ~ $a]) size

That is, create a collection by eliminating those elements of letters that are not a or A, and then answer the size of the resulting collection.

The choice between select: and reject: should be based on the best expression of the test. If the selection test is best expressed in terms of acceptance, then select: is easier to use; if the selection test is best expressed in terms of rejection, then reject: is easier to use. In this example, select: would be preferred.
As another example, assume `employees` is a collection of workers, each of whom responds to the message `salary` with his or her gross earnings. To make a collection of all employees whose salary is at least $10,000, use

```
employees select: [ :each | each salary >= 10000]
or
employees reject: [ :each | each salary < 10000]
```

The resulting collections are the same. The choice of which message to use, `select` or `reject`, depends on the way the programmer wishes to express the criterion "at least $10,000."

### Collecting

Suppose we wish to create a new collection in which each element is the salary of each worker in the collection `employees`.

```
employees collect: [ :each | each salary]
```

The resulting collection is the same size as `employees`. Each of the elements of the new collection is the salary of the corresponding element of `employees`.

### Detecting

Suppose we wish to find one worker in the collection of employees whose salary is greater than $20,000. The expression

```
employees detect: [ :each | each salary > 20000]
```

will answer with that worker, if one exists. If none exists, then `employees` will be sent the message `error: 'object is not in the collection'`. Just as in the specification of the removing messages, the programmer has the option to specify the exception behavior for an unsuccessful `detect`. The next expression answers one worker whose salary exceeds $20,000, or, if none exists, answers `nil`.

```
employees detect: [ :each | each salary > 20000] ifNone: [nil]
```

### Injecting

In the message `inject:into:`, the first argument is the initial value that takes part in determining the result; the second argument is a two-argument block. The first block argument names the variable that refers to the result; the second block argument refers to each element of the collection. An example using this message sums the salaries of the workers in the collection `employees`.

```
employees
  inject: 0
  into: [ :subTotal :nextWorker | subTotal + nextWorker salary]
```
where the initial value of 0 increases by the value of the salary for each worker in the collection, employees. The result is the final value of sub-Total.

By using the message `inject:into`, the programmer can locally specify temporary variable names and can avoid separate initialization of the object into which the result is accumulated. For example, in an earlier expression that counted the number of occurrences of the Characters a and A in the collection letters, we used a counter, `count`.

count ← 0.
letters do: [ :each | each asLowercase == $a
                 ifTrue: [count ← count + 1]]

An alternative approach is to use the message `inject:into`. In the example expression, the result is accumulated in `count`. `count` starts at 0. If the next character (`nextElement`) is a or A, then add 1 to `count`; otherwise add 0.

letters inject: 0
into: [ :count :nextElement |
        count + (nextElement asLowerCase == $a
                  ifTrue: [1]
                  ifFalse: [0])]

## Instance Creation

In the beginning of this chapter, examples were given in which new collections were expressed as literals. These collections were Arrays and Strings. For example, an expression for creating an array is

#('first' 'second' 'third')

where each element is a String expressed literally.

The messages `new` and `new:` can be used to create instances of particular kinds of collections. In addition, the class protocol for all collections supports messages for creating instances with one, two, three, or four elements. These messages provide a shorthand notation for creating kinds of collections that are not expressible as literals.

Collection class protocol

instance creation

with: anObject

Answer an instance of the collection containing an object.
with: firstObject with: secondObject

Answer an instance of the collection containing firstObject and secondObject as elements.

with: firstObject with: secondObject with: thirdObject

Answer an instance of the collection containing firstObject, secondObject, and thirdObject as elements.

with: firstObject with: secondObject with: thirdObject with: fourthObject

Answer an instance of the collection, containing firstObject, secondObject, thirdObject, and fourthObject as the elements.

For example, Set is a subclass of Collection. To create a new Set with three elements that are the Characters s, e, and t, evaluate the expression

Set with: $s with: $e with: $t

Note that the rationale for providing these four instance creation messages, no more and no fewer, is that this number satisfies the uses to which collections are put in the system itself.

## Conversion Among Collection Classes

A complete description and understanding of the permissible conversions between kinds of collections depends on a presentation of all the subclasses of Collection. Here we simply note that five messages are specified in the converting protocol for all collections in order to convert the receiver to a Bag, a Set, an OrderedCollection, and a SortedCollection. These messages are specified in class Collection because it is possible to convert any collection into any of these kinds of collections. The ordering of elements from any collection whose elements are unordered, when converted to a collection whose elements are ordered, is arbitrary.

### Collection instance protocol

converting

asBag

Answer a Bag whose elements are those of the receiver.

asSet

Answer a Set whose elements are those of the receiver (any duplications are therefore eliminated).

asOrderedCollection

Answer an OrderedCollection whose elements are those of the receiver (ordering is possibly arbitrary).
Conversion Among Collection Classes

asSortedCollection

Answer a SortedCollection whose elements are
those of the receiver, sorted so that each ele-
ment is less than or equal to (<=) its succes-
sors.

asSortedCollection: aBlock

Answer a SortedCollection whose elements are
those of the receiver, sorted according to the
argument aBlock.

Thus if lotteryA is a Bag containing elements

272 572 852 156 596 272 572

then

lotteryA asSet

is a Set containing elements

852 596 156 572 272

and

lotteryA asSortedCollection

is a SortedCollection containing elements ordered (the first element is
listed as the leftmost one)

156 272 272 572 572 596 852
<figure><img src="image_106.png" /></figure>

10

# Hierarchy of the Collection Classes

Class Bag

Class Set

Classes Dictionary and IdentityDictionary

Class SequenceableCollection

Subclasses of SequenceableCollection

Class OrderedCollection

Class SortedCollection

Class VINList

Class Interval

Class ArrayedCollection

Class String

Class Symbol

Class MappedCollection

Summary of Conversions Among Collections
Object

Magnitude

Character

Date

Time

Number

Float

Fraction

Integer

LargeNegativellnteger

LargePositiveInteger

SmallInteger

LookupKey
Association

Link

Process

Collection

SequenceableCollection
LinkedList

Semaphore

ArrayedCollection
Array

Bitmap
DisplayBitmap

RunArray
String
Symbol

Text
byteArray

Interval
OrderedCollection
SortedCollection

Bag
MappedCollection
Set

Dictionary
IdentityDictionary

Stream

PositionableStream

ReadStream

WriteStream

ReadWriteStream

ExternalStream

FileStream

Random

File

FileDirectory

FilePage

UndefinedObject

Boolean
False

True

ProcessorScheduler

Delay

SharedQueue

Behavior

ClassDescription

Class

MetaClass

Point

Rectangle

BitBit

CharacterScanner

Pen

DisplayObject

DisplayMedium

Form

Cursor

DisplayScreen

InfiniteForm

OpaqueForm

Path

Arc

Circle

Curve

Line

LinearFit

Spline
Figure 10.1 provides a road map for distinguishing among the various collection classes in the system. Following the choices in the figure is a useful way to determine which kind of collection to use in an implementation.

One distinction among the classes is whether or not a collection has a well-defined order associated with its elements. Another distinction is that elements of some collections can be accessed through externally-known names or *keys*. The type of key defines another way of distinguishing among kinds of collections. Some are integer indices, implicitly assigned according to the order of the elements; others are explicitly assigned objects that serve as lookup keys.

One unordered collection with external keys is a *Dictionary*. Its keys are typically instances of `String` or `LookupKey`; the comparison for matching keys is equality (`=`). *Dictionary* has a subclass, `IdentityDictionary`, whose external keys are typically *Symbols*. Its comparison for matching keys is equivalence (`==`). Elements of a *Bag* or a *Set* are unordered and not accessible through externally-known keys. Duplicates are allowed in a *Bag*, but not allowed in a *Set*.

All ordered collections are kinds of *SequenceableCollections*. Elements of all *SequenceableCollections* are accessible through keys that are integer indices. Four subclasses of *SequenceableCollection* support different ways in which to create the ordering of elements. An additional distinction among the *SequenceableCollection* classes is whether the elements can be any object or whether they are restricted to be instances of a particular kind of object.

The order of elements is determined externally for *OrderedCollections*, *LinkedLists*, and *ArrayedCollections*. For *OrderedCollection* and *LinkedList*, the programmer's sequence for adding and removing elements defines the ordering of the elements. An element of an *OrderedCollection* can be any object, while that of a *LinkedList* must be a kind of *Link*. The different *ArrayedCollections* in the system include *Array*, *String*, and *byteArray*. The elements of an *Array* or a *RunArray* can be any kind of object, elements of a *String* or of a *Text* must be *Characters*, and those of a *byteArray* must be *SmallIntegers* between 0 and 255.

The order of elements is determined internally for *Intervals* and *SortedCollections*. For an *Interval*, the ordering is an arithmetic progression that is specified at the time the instance is created. For a *SortedCollection*, the ordering is specified by a sorting criterion determined by evaluating a block known to the collection. Elements of an *Interval* must be *Numbers*; elements of a *SortedCollection* can be any kind of object.

In addition to the collection classes already mentioned, *MappedCollection* is a *Collection* that represents an indirect access path to a collection whose elements are accessible via external keys. The
<figure><img src="image_107.png" /><figcaption>Figure 10.1</figcaption></figure>
mapping from one set of external keys to the collection is determined at the time the MappedCollection is created.

The remainder of this chapter explores each of the collection subclasses, describing any additions to the message protocols and providing simple examples.

## Class Bag

A Bag is the simplest kind of collection. It represents collections whose elements are unordered and have no external keys. It is a subclass of Collection. Since its instances do not have external keys, they cannot respond to the messages at: and at:put. The message size answers the total number of elements in the collection.

A Bag is nothing more than a group of elements that behaves according to the protocol of all collections. The general description of collections does not restrict the number of occurrences of an element in an individual collection. Class Bag emphasizes this generality by specifying an additional message for adding elements.

Bag instance protocol

adding

add: newObject withOccurrences: anInteger

Include the argument, newObject, as an element of the receiver, an integer number of times. Answer the argument, newObject.

Consider the example class Product which represents a grocery item and its price. A new Product may be created using the message of: name at: price, and the price of an instance is accessible by sending it the message price. Filling one's grocery bag may be expressed by

sack ← Bag new.

sack add: (Product of: #steak at: 5.80).

sack add: (Product of: #potatoes at: 0.50) withOccurrences: 6.

sack add: (Product of: #carrots at: 0.10) withOccurrences: 4.

sack add: (Product of: #milk at: 2.20)

Then the grocery bill is determined by the expression

amount ← 0.

sack do: [ :eachProduct | amount ← amount + eachProduct price]

or
sack inject: 0

into: [ :amount :eachProduct | amount + eachProduct price]

to be $11.40. Note that the messages add:, do:, and inject:into: to a Bag are inherited from its superclass, Collection.

A Bag is unordered, so that, although enumeration messages are supported, the programmer cannot depend on the order in which elements are enumerated.

## Class Set

Class Set represents collections whose elements are unordered and have no external keys. Its instances cannot respond to the messages at: and at:put:. A Set is like a Bag except that its elements cannot be duplicated. The adding messages add the element only if it is not already in the collection. Class Set is a subclass of class Collection.

## Classes
Dictionary and
IdentityDictionary

Class Dictionary represents a set of associations between keys and values. The elements of a Dictionary are instances of class Association, a simple data structure for storing and retrieving the members of the key-value pair.

An alternative way of thinking about a Dictionary is that it is a collection whose elements are unordered but have explicitly assigned keys or names. From this perspective, the elements of a Dictionary are arbitrary objects (values) with external keys. These alternative ways of thinking about a Dictionary are reflected in the message protocol of the class. Messages inherited from class Collection—includes:, do:, and other enumeration messages—are applied to the values of the Dictionary. That is, these messages refer to the values of each association in the Dictionary, rather than to the keys or to the associations themselves.

Messages inherited from class Object—at: and at:put:—are applied to the keys of the Dictionary. The at: and at:put: paradigm is extended for the associations and the values by adding messages associationAt: and keyAtValue:. In order to provide additional control when looking up elements in a Dictionary, the message at:ifAbsent: is provided; using it, the programmer can specify the action to take if the element whose key is the first argument is not found. The inherited message at: reports an error if the key is not found.
Dictionary instance protocol

accessing

at: key ifAbsent: aBlock
Answer the value named by the argument, key. If key is not found, answer the result of evaluating aBlock.

associationAt: key
Answer the association named by the argument, key. If key is not found, report an error.

associationAt: key ifAbsent: aBlock
Answer the association named by the argument, key. If key is not found, answer the result of evaluating aBlock.

keyAtValue: value
Answer the name for the argument, value. If there is no such value, answer nil. Since values are not necessarily unique, answer the name for the first one encountered in the search.

keyAtValue: value ifAbsent: exceptionBlock
Answer the key for the argument, value. If there is no such value, answer the result of evaluating exceptionBlock.

keys
Answer a Set containing the receiver's keys.

values
Answer a Bag containing the receiver's values (includes any duplications).

As an example of the use of a Dictionary, suppose opposites is a Dictionary of word Symbols and their opposites.

opposites ← Dictionary new.

opposites at: #hot put: #cold.

opposites at: #push put: #pull.

opposites at: #stop put: #go.

opposites at: #come put: #go

Alternatively, an element can be added using the message add: by creating an Association as the argument.

opposites add: (Association key: #front value: #back).

opposites add: (Association key: #top value: #bottom)

The Dictionary, opposites, now consists of

<table><thead><tr><td>key</td><td>value</td></tr></thead><tbody><tr><td>hot</td><td>cold</td></tr><tr><td>push</td><td>pull</td></tr><tr><td>stop</td><td>go</td></tr><tr><td>come</td><td>go</td></tr><tr><td>front</td><td>back</td></tr><tr><td>top</td><td>bottom</td></tr></tbody></table>
We can use the testing protocol inherited from class `Collection` to test the values in the `Dictionary`. Notice that `includes:` tests the inclusion of a value, not a key.

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>opposites size</td><td>6</td></tr><tr><td>opposites includes: #cold</td><td>true</td></tr><tr><td>opposites includes: #hot</td><td>false</td></tr><tr><td>opposites occurrencesOf: #go</td><td>2</td></tr><tr><td>opposites at: #stop put: #start</td><td>start</td></tr></tbody></table>

The fourth example indicates that, although a key can appear only once in a `Dictionary`, a value can be associated with any number of keys. The last example re-associates the key `#stop` with a new value, `#start`. Additional messages are provided in class `Dictionary` for testing associations and keys.

### Dictionary instance protocol

#### dictionary testing

#### `includesAssociation: anAssociation`

Answer whether the receiver has an element (association between a key and a value) that is equal to the argument, `anAssociation`.

#### `includesKey: key`

Answer whether the receiver has a key equal to the argument, `key`.

Then we can try

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>opposites includesAssociation: (Association key: #come value: #go)</td><td>true</td></tr><tr><td>opposites includesKey: #hot</td><td>true</td></tr></tbody></table>
Similarly, the removing protocol specified in class Collection is extended to provide access by reference to associations and keys, as well as to values. However, the message remove: itself is not appropriate for a Dictionary; in removing an element, mention of the key is required.

### Dictionary instance protocol

**dictionary removing**

removeAssociation: anAssociation

Remove the key and value association, anAssociation, from the receiver. Answer anAssociation.

removeKey: key

Remove key (and its associated value) from the receiver. If key is not in the receiver, report an error. Otherwise, answer the value associated with key.

removeKey: key ifAbsent: aBlock

Remove key (and its associated value) from the receiver. If key is not in the receiver, answer the result of evaluating aBlock. Otherwise, answer the value named by key.

### For example

<table><thead><tr><th>expression</th><th>result</th></tr></thead><tbody><tr><td>opposites removeAssociation: (Association key: #top value: #bottom)</td><td>The association whose key is #top and value is #bottom. opposite sites has one less element.</td></tr><tr><td>opposites removeKey: #hot</td><td>The association whose key is #hot and whose value is #cold. This association is removed from opposites.</td></tr><tr><td>opposites removeKey: #cold ifAbsent: [opposites at: #cold put: #hot]</td><td>hot</td></tr></tbody></table>

As a result of the last example, the association of #cold with #hot is now an element of opposites.

The message do: evaluates its argument, a block, for each of the Dictionary's values. The collection enumerating protocol, inherited from class Collection, is again extended in order to provide messages for enumerating over the associations and the keys. Messages supporting uses of reject: and inject: into: are not provided.
Dictionary instance protocol

dictionary enumerating

associationsDo: aBlock Evaluate aBlock for each of the receiver's key/value associations.

keysDo: aBlock Evaluate aBlock for each of the receiver's keys.

We thus have three possible ways of enumerating over a Dictionary. Suppose newWords is a Set of vocabulary words that a child has not yet learned. Any word in opposites is now part of the child's repertoire and can be removed from newWords. Evaluating the following two expressions removes these words (the first removes the values, the second the keys).

opposites do: [ :word | newWords remove: word ifAbsent: []].

opposites keysDo: [ :word | newWords remove: word ifAbsent: []]

Note that if a word from opposites is not in newWords, then nothing (no error report) happens. Alternatively, one expression, enumerating the Associations, can be used.

opposites associationsDo:

[ :each | newWords remove: each key ifAbsent: []. newWords remove: each value ifAbsent: []]

The accessing messages keys and values can be used to obtain collections of the words in the opposites dictionary. Assuming the evaluation of all previous example expressions, then

opposites keys

returns the Set whose elements are

push come front stop cold

and

opposites values

returns the Bag whose elements are

pull go back start hot
Class
Sequenceable-
Collection

Class SequenceableCollection represents collections whose elements are ordered and are externally named by integer indices. SequenceableCollection is a subclass of Collection and provides the protocol for accessing, copying, and enumerating elements of a collection when it is known that there is an ordering associated with the elements. Since the elements are ordered, there is a well-defined first and last element of the collection. It is possible to ask the index of a particular element (indexOf:) and the index of the beginning of a sequence of elements within the collection (indexOfSubCollection:startingAt:). All collections inherit messages from class Object for accessing indexed variables. As described in Chapter 6, these are at:, at:put:, and size. In addition, SequenceableCollections support putting an object at all positions named by the elements of a Collection (atAll:put:), and putting an object at all positions in the sequence (atAllPut:). Sequences of elements within the collection can be replaced by the elements of another collection (replaceFrom:to:with: and replaceFrom:to:with:startingAt:).

SequenceableCollection instance protocol

accessing

atAll: aCollection put: anObject
Associate each element of the argument, aCollection (an Integer or other external key), with the second argument, anObject.

atAllPut: anObject
Put the argument, anObject, as every one of the receiver's elements.

first
Answer the first element of the receiver. Report an error if the receiver contains no elements.

last
Answer the last element of the receiver. Report an error if the receiver contains no elements.

indexOf: anElement
Answer the first index of the argument, anElement, within the receiver. If the receiver does not contain anElement, answer 0.

indexOf: anElement ifAbsent: exceptionBlock
Answer the first index of the argument, anElement, within the receiver. If the receiver does not contain anElement, answer the result of evaluating the argument, exceptionBlock.

indexOfSubCollection: aSubCollection startingAt: anIndex
If the elements of the argument, aSubCollection, appear, in order, in the receiver, then answer the index of the first element of the first such occurrence. If no such match is found, answer 0.

indexOfSubCollection: aSubCollection startingAt: anIndex
ifAbsent: exceptionBlock
Answer the index of the receiver's first element, such that that element equals the first
element of the argument, aSubCollection, and the next elements equal the rest of the elements of aSubCollection. Begin the search of the receiver at the element whose index is the argument, anIndex. If no such match is found, answer the result of evaluating the argument, exceptionBlock.

replaceFrom: start to: stop with: replacementCollection

Associate each index between start and stop with the elements of the argument, replacementCollection. Answer the receiver. The number of elements in replacementCollection must equal stop-start+1.

replaceFrom: start to: stop with: replacementCollection startingAt: repStart

Associate each index between start and stop with the elements of the argument, replacementCollection, starting at the element of replacementCollection whose index is repStart. Answer the receiver. No range checks are performed, except if the receiver is the same as replacementCollection but repStart is not 1, then an error reporting that indices are out of range will occur.

Examples of using these accessing messages, using instances of String, are

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>'aaaaaaaaaa' size</td><td>10</td></tr><tr><td>'aaaaaaaaaaa' atAll: (2 to: 10 by: 2) put: $b</td><td>'ababababab'</td></tr><tr><td>'aaaaaaaaaaa' atAllPut: $b</td><td>'bbbbbbbbbbb'</td></tr><tr><td>'This string' first</td><td>$T</td></tr><tr><td>'This string' last</td><td>$g</td></tr><tr><td>'abcdefghiikLMNOP' indexOf: $F</td><td>6</td></tr><tr><td>'abcdefghiikLMNOP' indexOf: $M ifAbsent: [0]</td><td>13</td></tr><tr><td>'abcdefghiikLMNOP' indexOf: $Z ifAbsent: [0]</td><td>0</td></tr><tr><td>'The cow jumped' indexOfSubCollection: 'cow' startingAt: 1</td><td>5</td></tr><tr><td>'The cow jumped' replaceFrom: 5 to: 7 with: 'dog'</td><td>'The dog jumped'</td></tr><tr><td>'The cow jumped' replaceFrom: 5 to: 7 with: 'the spoon ran' startingAt: 5</td><td>'The spo jumped'</td></tr></tbody></table>

Any of these examples could be similarly carried out with an instance of any subclass of SequenceableCollection, for example, with an Array. For the Array, $# (The brown jug), replacement of brown by black is carried out by evaluating the expression

#(The brown jug) replaceFrom: 2 to: 2 with: $# (black)
Notice that the last argument must be an Array as well. And notice that the replacement messages do not change the size of the original collection (the receiver), although they do alter the collection. It may be preferrable to preserve the original by creating a copy. The copying protocol of SequenceableCollections supports copying a sequence of elements in the collection, copying the entire collection with part of it replaced, copying the entire collection with an element deleted, or copying the entire collection with one or more elements concatenated.

SequenceableCollection instance protocol

copying

<table><tr><td>aSequenceableCollection</td><td>This is the concatenation operation. Answer a copy of the receiver with each element of the argument, aSequenceableCollection, added, in order.</td></tr><tr><td>copyFrom: start to: stop</td><td>Answer a copy of a subset of the receiver, starting from element at index start until element at index stop.</td></tr><tr><td>copyReplaceAll: oldSubCollection with: newSubCollection</td><td>Answer a copy of the receiver in which all occurrences of oldSubCollection have been replaced by newSubCollection.</td></tr><tr><td>copyReplaceFrom: start to: stop with: replacementCollection</td><td>Answer a copy of the receiver satisfying the following conditions: If stop is less than start, then this is an insertion; stop should be exactly start-1. start = 1 means insert before the first character. start = size + 1 means append after last character. Otherwise, this is a replacement; start and stop have to be within the receiver's bounds.</td></tr><tr><td>copyWith: newElement</td><td>Answer a copy of the receiver that is 1 bigger than the receiver and has newElement as the last element.</td></tr><tr><td>copyWithout: oldElement</td><td>Answer a copy of the receiver in which all occurrences of oldElement have been left out.</td></tr></table>

Using the replace and copy messages, a simple text editor can be devised. The Smalltalk-80 system includes class String as well as class Text, the latter providing support for associating the characters in the String with font or emphasis changes in order to mix character fonts, bold, italic, and underline. The message protocol for Text is that of a SequenceableCollection with additional protocol for setting the emphasis codes. For illustration purposes, we use an instance of class String, but remind the reader of the analogous application of editing messages for an instance of class Text. Assume that line is initially an empty string

line ← String new: 0
Then

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>line - line copyReplaceFrom: 1<br/>to: 0<br/>with: 'this is the first line tril'</td><td>'this is the first line tril'</td></tr><tr><td>line - line copyReplaceAll: 'tril'<br/>with: 'trial'</td><td>'this is the first line trial'</td></tr><tr><td>line - line copyReplaceFrom:<br/>(line size + 1)<br/>to: (line size)<br/>with: 'and so on'</td><td>'this is the first line<br/>trial and so on'</td></tr><tr><td>line indexOfSubCollection: 'trial'<br/>startingAt: 1</td><td>24</td></tr><tr><td>line - line copyReplaceFrom: 29<br/>to: 28<br/>with: ''</td><td>'this is the first line trial<br/>and so on'</td></tr></tbody></table>

The last two messages of the copying protocol given above are useful in obtaining copies of an Array with or without an element. For example

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>#(one two three)<br/>copyWith: #four</td><td>(one two three four)</td></tr><tr><td>#(one two three)<br/>copyWithout: #two</td><td>(one three)</td></tr></tbody></table>

Because the elements of a SequenceableCollection are ordered, enumeration is in order, starting with the first element and taking each successive element until the last. Reverse enumeration is also possible, using the message reverseDo: aBlock. Enumeration of two SequenceableCollections can be done together so that pairs of elements, one from each collection, can be used in evaluating a block.

SequenceableCollection instance protocol

enumerating

findFirst: aBlock

Evaluate aBlock with each of the receiver's elements as the argument. Answer the index of the first element for which the argument, aBlock evaluates to true.
## Subclasses of SequenceableCollection

**findLast: aBlock**

Evaluate aBlock with each of the receiver's elements as the argument. Answer the index of the last element for which the argument, aBlock evaluates to true.

**reverseDo: aBlock**

Evaluate aBlock with each of the receiver's elements as the argument, starting with the last element and taking each in sequence up to the first. For SequenceableCollections, this is the reverse of the enumeration for do.. aBlock is a one-argument block.

**with: aSequenceableCollection do: aBlock**

Evaluate aBlock with each of the receiver's elements along with the corresponding element from aSequenceableCollection. aSequenceableCollection must be the same size as the receiver, and aBlock must be a two-argument block.

The following expressions create the Dictionary, opposites, which was introduced in an earlier example.

opposites -- Dictionary new.

#(come cold front hot push stop)

with: #(go hot back cold pull start)

do: [ :key :value | opposites at: key put: value]

The Dictionary now has six associations as its elements.

Any SequenceableCollection can be converted to an Array or a MappedCollection. The messages are asArray and mappedBy: aSequenceableCollection.

## Subclasses of SequenceableCollection

Subclasses of SequenceableCollection are OrderedCollection, LinkedList, Interval, and MappedCollection. ArrayedCollection is a subclass representing a collection of elements with a fixed range of integers as external keys. Subclasses of ArrayedCollection are, for example, Array and String.

OrderedCollections are ordered by the sequence in which objects are added and removed from them. The elements are accessible by external keys that are indices. The accessing, adding, and removing protocols are augmented to refer to the first and last elements, and to elements preceding or succeeding other elements.

OrderedCollections can act as stacks or queues. A stack is a sequential list for which all additions and deletions are made at one end of the

Class OrderedCollection
list (called either the "rear" or the "front") of the list. It is often called a *last-in first-out* queue.

<table><thead><tr><th>usual vocabulary</th><th>OrderedCollection<br>message</th></tr></thead><tbody><tr><td>push newObject</td><td>addLast: newObject</td></tr><tr><td>pop</td><td>removeLast</td></tr><tr><td>top</td><td>last</td></tr><tr><td>empty</td><td>empty</td></tr></tbody></table>

A queue is a sequential list for which all additions are made at one end of the list (the "rear"), but all deletions are made from the other end (the "front"). It is often called a *first-in first-out* queue.

<table><thead><tr><th>usual vocabulary</th><th>OrderedCollection<br>message</th></tr></thead><tbody><tr><td>add newObject</td><td>addLast: newObject</td></tr><tr><td>delete</td><td>removeFirst</td></tr><tr><td>front</td><td>first</td></tr><tr><td>empty</td><td>empty</td></tr></tbody></table>

The message add: to an OrderedCollection means "add the element as the last member of the collection" and remove: means "remove the argument as an element." The message protocol for OrderedCollections, in addition to that inherited from classes Collection and SequenceableCollection, follows.

OrderedCollection instance protocol

accessing

after: oldObject
Answer the element after oldObject in the receiver. If the receiver does not contain oldObject or if the receiver contains no elements after oldObject, report an error.

before: oldObject
Answer the element before oldObject in the receiver. If the receiver does not contain oldObject or if the receiver contains no elements before oldObject, report an error.

adding

add: newObject after: oldObject
Add the argument, newObject, as an element of the receiver. Put it in the sequence just succeeding oldObject. Answer newObject. If oldObject is not found, then report an error.
## Subclasses of SequenceableCollection

**add: newObject before: oldObject**

Add the argument, newObject, as an element of the receiver. Put it in the sequence just preceding oldObject. Answer newObject. If oldObject is not found, then report an error.

**allFirst: anOrderedCollection**

Add each element of the argument, anOrderedCollection, at the beginning of the receiver. Answer anOrderedCollection.

**allLast: anOrderedCollection**

Add each element of the argument, anOrderedCollection, to the end of the receiver. Answer anOrderedCollection.

**addFirst: newObject**

Add the argument, newObject, to the beginning of the receiver. Answer newObject.

**addLast: newObject**

Add the argument, newObject, to the end of the receiver. Answer newObject.

### removing

**removeFirst**

Remove the first element of the receiver and answer it. If the receiver is empty, report an error.

**removeLast**

Remove the last element of the receiver and answer it. If the receiver is empty, report an error.

## Class SortedCollection

Class SortedCollection is a subclass of OrderedCollection. The elements in a SortedCollection are ordered by a function of two elements. The function is represented by a two-argument block called the sort block. It is possible to add an element only with the message add:; messages such as addLast: that allow the programmer to specify the order of inserting are disallowed for SortedCollections.

An instance of class SortedCollection can be created by sending SortedCollection the message sortBlock:. The argument to this message is a block with two-arguments, for example,

```
SortedCollection sortBlock: [ :a :b | a <= b ]
```

This particular block is the default sorting function when an instance is created simply by sending SortedCollection the message new. Thus examples of the four ways to create a SortedCollection are

```
SortedCollection new
SortedCollection sortBlock: [ :a :b | a > b ]
anyCollection asSortedCollection
anyCollection asSortedCollection: [ :a :b | a > b ]
```

It is possible to determine the block and to reset the block using two additional accessing messages to instances of SortedCollection. When the block is changed, the elements of the collection are, of course, re-sorted. Notice that the same message is sent to the class itself (sortBlock:) to
create an instance with a particular sorting criterion, and to an instance to change its sorting criterion.

SortedCollection class protocol

instance creation

sortBlock: aBlock

Answer an instance of SortedCollection such that its elements will be sorted according to the criterion specified in the argument, aBlock.

SortedCollection instance protocol

accessing

sortBlock

sortBlock: aBlock

Answer the block that is the criterion for sorting elements of the receiver.

Make the argument, aBlock, be the criterion for ordering elements of the receiver.

Suppose we wish to maintain an alphabetical list of the names of children in a classroom.

children ← SortedCollection new

The initial sorting criterion is the default block [ :a :b | a <= b]. The elements of the collection can be Strings or Symbols because, as we shall show presently, these kinds of objects respond to the comparison messages <, >, <=, and >=.

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>children add: #Joe</td><td>Joe</td></tr><tr><td>children add: #Bill</td><td>Bill</td></tr><tr><td>children add: #Alice</td><td>Alice</td></tr><tr><td>children</td><td>SortedCollection<br>(Alice Bill Joe)</td></tr><tr><td>children add: #Sam</td><td>Sam</td></tr><tr><td>children</td><td>SortedCollection<br>(Sam Joe Bill Alice)</td></tr><tr><td>sortBlock: [ :a :b | a < b]</td><td>Henrietta</td></tr><tr><td>children add: #Henrietta</td><td>Henrietta</td></tr><tr><td>children</td><td>SortedCollection<br>(Sam Joe Henrietta<br>Bill Alice)</td></tr></tbody></table>

The sixth message in the example reversed the order in which elements are stored in the collection, children.
## Class `LinkedList`

`LinkedList` is another subclass of `SequenceableCollection` whose elements are explicitly ordered by the sequence in which objects are added and removed from them. Like `OrderedCollection`, the elements of a `LinkedList` can be referred to by external keys that are indices. Unlike `OrderedCollection`, where the elements may be any object, the elements of a `LinkedList` are homogeneous; each must be an instance of class `Link` or of a subclass of `Link`.

A `Link` is a record of a reference to another `Link`. Its message protocol consists of three messages. The same message (`nextLink:`) is used to create an instance of `Link` with a particular reference, and to change the reference of an instance.

### `LinkedList` class protocol

#### instance creation

<table><tr><td>nextLink: aLink</td><td>Create an instance of `Link` that references the argument, aLink.</td></tr></table>

### `LinkedList` instance protocol

#### accessing

<table><tr><td>nextLink</td><td>Answer the receiver's reference.</td></tr><tr><td>nextLink: aLink</td><td>Set the receiver's reference to be the argument, aLink.</td></tr></table>

Since class `Link` does not provide a way to record a reference to the actual element of the collection, it is treated as an abstract class. That is, instances of it are not created. Rather, subclasses are defined that provide the mechanisms for storing one or more elements, and instances of the subclasses are created.

Since `LinkedList` is a subclass of `SequenceableCollection`, its instances can respond to the accessing, adding, removing, and enumerating messages defined for all collections. Additional protocol for `LinkedList` consists of

#### `LinkedList` instance protocol

##### adding

<table><tr><td>addFirst: aLink</td><td>Add aLink to the beginning of the receiver's list. Answer aLink.</td></tr><tr><td>addLast: aLink</td><td>Add aLink to the end of the receiver's list. Answer aLink.</td></tr></table>

##### removing

<table><tr><td>removeFirst</td><td>Remove the receiver's first element and answer it. If the receiver is empty, report an error.</td></tr><tr><td>removeLast</td><td>Remove the receiver's last element and answer it. If the receiver is empty, report an error.</td></tr></table>
An example of a subclass of Link in the Smalltalk-80 system is class Process. Class Semaphore is a subclass of LinkedList. These two classes are discussed in Chapter 15, which is about multiple independent processes in the system.

The following is an example of the use of LinkedList. Link does not provide instance information other than a reference to another Link. So, as an example, assume that there is a subclass of Link named Entry. Entry adds the ability to store one object. The instance creation message for an Entry is for: anObject, and its accessing message is element.

<table><tr><td>class name</td><td>Entry</td></tr><tr><td>superclass</td><td>Link</td></tr><tr><td>instance variable names</td><td>element</td></tr><tr><td>class methods</td><td></td></tr></table>

instance creation

**for: anObject**

↑self new setElement: anObject

instance methods

accessing

**element**

↑element

printing

**printOn: aStream**

aStream nextPutAll: ' Entry for: ', element printString

private

**setElement: anObject**

element ← anObject

The classes LinkedList and Entry can then be used as follows.

<table><thead><tr><th>expression</th><th>result</th></tr></thead><tbody><tr><td>list ← LinkedList new</td><td>LinkedList ()</td></tr><tr><td>list add: (Entry for: 2)</td><td>Entry for: 2</td></tr><tr><td>list add: (Entry for: 4)</td><td>Entry for: 4</td></tr><tr><td>list addLast: (Entry for: 5)</td><td>Entry for: 5</td></tr><tr><td>list addFirst: (Entry for: 1)</td><td>Entry for: 1</td></tr><tr><td>list</td><td>LinkedList (Entry for: 1<br>Entry for: 2<br>for: 4 Entry for: 5)</td></tr><tr><td>list.isEmpty</td><td>false</td></tr><tr><td>list.size</td><td>4</td></tr></tbody></table>
list inject: 0 12
into: [ :value :each | (each element) + value]

list last Entry for: 5

list first Entry for: 1

list remove: (Entry for: 4) Entry for: 4

list removeFirst Entry for: 1

list removeLast Entry for: 5

list first == list last true

Class Interval

Another kind of SequenceableCollection is a collection of numbers representing a mathematical progression. For example, the collection might consist of all the integers in the interval from 1 to 100; or it might consist of all even integers in the interval from 1 to 100. Or the collection might consist of a series of numbers where each additional number in the series is computed from the previous one by multiplying it by 2. The series might start with 1 and end with the last number that is less than or equal to 100. This would be the sequence 1, 2, 4, 8, 16, 32, 64.

A mathematical progression is characterized by a first number, a limit (maximum or minimum) for the last computed number, and a method for computing each succeeding number. The limit could be positive or negative infinity. An arithmetic progression is one in which the computation method is simply the addition of an increment. For example, it could be a series of numbers where each additional number in the series is computed from the previous one by adding a negative 20. The series might start with 100 and end with the last number that is greater than or equal to 1. This would be the sequence 100, 80, 60, 40, 20.

In the Smalltalk-80 system, the class of collections called Intervals consists of finite arithmetic progressions. In addition to those messages inherited from its superclasses SequenceableCollection and Collection, class Interval supports messages for initialization and for accessing those values that characterize the instance. New elements cannot be added or removed from an Interval.

The class protocol of Interval consists of the following messages for creating instances.

Interval class protocol

instance creation

from: startInteger to: stopInteger Answer an instance of class Interval, starting with the number startInteger, ending with the number stopInteger, and using the increment 1 to compute each successive element.
from: startInteger to: stopInteger by: stepInteger

Answer an instance of Interval, starting with the number startInteger, ending with the number stopInteger, and using the increment stepInteger to compute each successive element.

All messages appropriate to SequenceableCollections can be sent to an Interval. In addition, the instance protocol of Interval provides a message for accessing the increment of the arithmetic progression (increment).

Class Number supports two messages that provide a shorthand for expressing new Intervals—to: stop and to: stop by: step. Thus to create an Interval of all integers from 1 to 10, evaluate either

Interval from: 1 to: 10

or

1 to: 10

To create an Interval starting with 100 and ending with 1, adding a negative 20 each time, evaluate either

Interval from: 100 to: 1 by: -20

or

100 to: 1 by: -20

This is the sequence 100, 80, 60, 40, 20. The Interval need not consist of Integers—to create an Interval between 10 and 40, incrementing by 0.2, evaluate either

Interval from: 10 to: 40 by: 0.2

or

10 to: 40 by: 0.2

This is the sequence 10, 10.2, 10.4, 10.6, 10.8, 11.0, ... and so on.

Note that we could provide the more general case of a progression by replacing the numeric value of step by a block. When a new element is to be computed, it would be done by sending the current value as the argument of the message value: to the block. The computations of size and do: would have to take this method of computation into account.
The message `do:` to an `Interval` provides the function of the usual for-loop in a programming language. The `Algol` statement

```
for i := 10 step 6 until 100 do
    begin
        <statements>
    end
```

is represented by

(10 to: 100 by: 6) do: [ :i | statements ]

Numbers respond to the message `to:by:do:` as though the expression had been written as given in the example. So that iteration can be written without parentheses as

10 to: 100 by: 6 do: [ :i | statements ]

To increment by 1 every sixth numeric element of an `OrderedCollection`, numbers, evaluate

6 to: numbers size
by: 6
do: [ :index | numbers at: index put: (numbers at: index) + 1]

The `Interval` created is 6, 12, 18, ..., up to the index of the last element of numbers. If the size of the collection is less than 6 (the supposedly first index), nothing happens. Otherwise elements at position 6, 12, 18, and so on, until the last possible position, are replaced.

### Class ArrayedCollection

As stated earlier, class `ArrayedCollection` is a subclass of `Collection`. It represents a collection of elements with a fixed range of integers as external keys. `ArrayedCollection` has five subclasses in the `Smalltalk-80` system—`Array`, `String`, `Text`, `RunArray`, and `ByteArray`.

An `Array` is a collection whose elements are any objects. It provides the concrete representation for storing a collection of elements that have integers as external keys. Several examples of the use of `Arrays` have already been given in this chapter.

A `String` is a collection whose elements are `Characters`. Many examples of the use of `Strings` have been given in this and in previous chapters.
ters. Class String provides additional protocol for initializing and comparing its instances.

Text represents a String that has font and emphasis changes. It is used in storing information needed for creating textual documents in the Smalltalk-80 system. An instance of Text has two instance variables, the String and an instance of RunArray in which an encoding of the font and emphasis changes is stored.

Class RunArray provides a space-efficient storage of data that tends to be constant over long runs of the possible indices. It stores repeated elements singly and then associates with each single element a number that denotes the consecutive occurrences of the element. For example, suppose the Text representing the String 'He is a good boy.' is to be displayed with the word "boy" in bold, and further suppose that the code for the font is 1 and for its boldface version is 2. Then the RunArray for the Text that is associated with 'He is a good boy.' (a String of 17 Characters) consists of 1 associated with 13, 2 associated with 3, and 1 associated with 1. That is, the first 13 Characters are in font 1, the next three in font 2, and the last in font 1.

A BeanArray represents an ArrayedCollection whose elements are integers between 0 and 255. The implementation of a BeanArray stores two bytes to a 16-bit word; the class supports additional protocol for word and double-word access. BeanArrays are used in the Smalltalk-80 system for storing time in milliseconds.

Class String

As stated earlier, the class protocol for String adds messages for creating a copy of another String (fromString: aString) or for creating a String from the Characters in a Stream (readFrom: aStream). The main significance of this second message is that pairs of embedded quotes are read and stored as one element, the quote character. In addition, class String adds comparing protocol like that specified in class Magnitude. We introduced some of these messages earlier in the description of class SortedCollection.

String instance protocol

comparing

< aString

Answer whether the receiver collates before the argument, aString. The collation sequence is ASCII with case differences ignored.

< = aString

Answer whether the receiver collates before the argument, aString, or is the same as aString. The collation sequence is ASCII with case differences ignored.

> aString

Answer whether the receiver collates after the argument, aString. The collation sequence is ASCII with case differences ignored.
> = aString
Answer whether the receiver collates after the argument, aString, or is the same as aString. The collation sequence is ASCII with case differences ignored.

match: aString
Treat the receiver as a pattern that can contain characters # and *. Answer whether the argument, aString, matches the pattern in the receiver. Matching ignores upper/lower case differences. Where the receiver contains the character #, aString may contain any single character. Where the receiver contains *, aString may contain any sequence of characters, including no characters.

sameAs: aString
Answer whether the receiver collates precisely with the argument, aString. The collation sequence is ASCII with case differences ignored.

We have not as yet given examples of using the last two messages.

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>'first string' sameAs: 'first string'</td><td>true</td></tr><tr><td>'First String' sameAs: 'first string'</td><td>true</td></tr><tr><td>'First String' = 'first string'</td><td>false</td></tr><tr><td>'#first string' match: 'first string'</td><td>true</td></tr><tr><td>'* string' match: 'any string'</td><td>true</td></tr><tr><td>'*.st' match: 'filename.st'</td><td>true</td></tr><tr><td>'first string' match: 'first *'</td><td>false</td></tr></tbody></table>

Strings can be converted to all lowercase characters or all uppercase characters. They can also be converted to instances of class Symbol.

String instance protocol

converting

asLowercase
Answer a String made up from the receiver whose characters are all lowercase.

asUppercase
Answer a String made up from the receiver whose characters are all uppercase.

asSymbol
Answer the unique Symbol whose characters are the characters of the receiver.

Therefore we have

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>'first string' asUppercase</td><td>'FIRST STRING'</td></tr><tr><td>'First String' asLowercase</td><td>'first string'</td></tr><tr><td>'First' asSymbol</td><td>First</td></tr></tbody></table>
Class Symbol
Symbols are arrays of Characters that are guaranteed to be unique. Thus

'a string' asSymbol == 'a string' asSymbol

answers true. Class Symbol provides two instance creation messages in its class protocol for this purpose.

<table><thead><tr><th colspan="2">Symbol class protocol</th></tr></thead><tbody><tr><td>instance creation</td><td></td></tr><tr><td>intern: aString</td><td>Answer a unique Symbol whose characters are those of aString.</td></tr><tr><td>internCharacter: aCharacter</td><td>Answer a unique Symbol of one character, the argument, aCharacter.</td></tr></tbody></table>

In addition, Symbols can be expressed literally using the character # as a prefix to a sequence of Characters. For example, #dave is a Symbol of four Characters. Symbols print without this prefix notation.

Class MappedCollection

Class MappedCollection is a subclass of Collection. It represents an access mechanism for referencing a subcollection of a collection whose elements are named. This mapping can determine a reordering or filtering of the elements of the collection. The basic idea is that a MappedCollection refers to a *domain* and a *map*. The domain is a Collection that is to be accessed indirectly through the external keys stored in the map. The map is a Collection that associates a set of external keys with another set of external keys. This second set of keys must be external keys that can be used to access the elements of the domain. The domain and the map, therefore, must be instances of Dictionary or of a subclass of SequenceableCollection.

Take, for example, the Dictionary of word Symbols, opposites, introduced earlier.

<table><thead><tr><th>key</th><th>value</th></tr></thead><tbody><tr><td>come</td><td>go</td></tr><tr><td>cold</td><td>hot</td></tr><tr><td>front</td><td>back</td></tr><tr><td>hot</td><td>cold</td></tr><tr><td>push</td><td>pull</td></tr><tr><td>stop</td><td>start</td></tr></tbody></table>
Suppose we create another Dictionary of synonym Symbols for some of the keys of the entries in opposites and refer to it by the variable name alternates.

<table><thead><tr><td>key</td><td>value</td></tr></thead><tbody><tr><td>cease</td><td>stop</td></tr><tr><td>enter</td><td>come</td></tr><tr><td>scalding</td><td>hot</td></tr><tr><td>shove</td><td>push</td></tr></tbody></table>

Then we can provide a MappedCollection by evaluating the expression

words → MappedCollection collection: opposites map: alternates

Through words, we can access the elements of opposites. For example, the value of the expression words at: #cease is start (i.e., the value of the key cease in alternatives is stop; the value of the key stop in opposites is start). We can determine which part of opposites is referenced by words by sending words the message contents.

words contents

The result is a Bag containing the symbols start go cold pull.

The message at:put: is an indirect way to change the domain collection. For example

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>words at: #scalding</td><td>cold</td></tr><tr><td>words at: #cease</td><td>start</td></tr><tr><td>words at: #cease</td><td>continue</td></tr><tr><td>put: #continue</td><td></td></tr><tr><td>opposites at: #stop</td><td>continue</td></tr></tbody></table>

## Summary of Conversions Among Collections

In the sections describing the various kinds of collections, we have indicated which collections can be converted to which other collections. In summary, any collection can be converted to a Bag, a Set, an OrderedCollection, or a SortedCollection. All collections except Bags and Sets can be converted to an Array or a MappedCollection. Strings and Symbols can be converted into one another; but no collection can be converted into an Interval or alsthedList.
<figure><img src="image_108.png" /></figure>
# 11

## Three Examples That Use Collections

* Random Selection and Playing Cards

* The Drunken Cockroach Problem

* Traversing Binary Trees

* *A Binary Word Tree*

<figure><img src="image_109.png" /></figure>
Three examples of class descriptions are given in this chapter. Each example makes use of the numeric and collections objects available in the Smalltalk-80 system; each illustrates a different way to add functionality to the system.

Card games can be created in terms of random selection from a collection representing a deck of cards. The example class Card represents a playing card with a particular suit and rank. CardDeck represents a collection of such Cards; a CardHand is a collection of Cards for an individual player. Selecting cards from a CardDeck or a CardHand is carried out using example classes that represent sampling with replacement, SampleSpaceWithReplacement, and sampling without replacement, SampleSpaceWithoutReplacement. A well-known programming problem, the drunken cockroach problem, involves counting the number of steps it takes a cockroach to randomly travel over all the tiles in a room. The solution given in this chapter represents each tile as an instance of example class Tile and the bug as an instance of DrunkenCockroach. The third example in this chapter is of a tree-like data structure represented by classes Tree and Node; a WordNode illustrates the way trees can be used to store strings representing words.

## Random Selection and Playing Cards

The Smalltalk-80 class Random, which acts as a generator for randomly selected numbers between 0 and 1, was described in Chapter 8. Random provides the basis for sampling from a set of possible events; such a set is known as a *sample space*. A simple form of discrete random sampling can be obtained in which a random number is used to select an element from a sequenceable collection. If the selected element remains in the collection, then the sampling is done "with replacement"—that is, every element of the collection is available each time the collection is sampled. Alternatively, the sampled element can be removed from the collection each time the collection is sampled; this is sampling "without replacement."

Class SampleSpaceWithReplacement represents random selection with replacement from a sequenceable collection of items. An instance of the class is created by specifying the collection of items from which random sampling will be done. This initialization message has selector data: We then sample from the collection by sending the instance the message next. Or we can obtain an *integer* number of samples by sending the message next: an *integer*.

For example, suppose we wish to sample from an *Array* of *Symbols* representing the names of people.
people - SampleSpaceWithReplacement
data: #(sally sam sue sarah steve)

Each time we wish to select a name from the Array, we evaluate the expression

people next

The response is one of the Symbols, sally, sam, sue, sarah, or steve. By evaluating the expression

people next: 5

an OrderedCollection of five samples is selected. Instances of SampleSpaceWithReplacement respond to messages empty and size to test whether any elements exist in the sample space and how many elements exist. Thus the response to

people empty

is false; and the response to

people size

is 5.

An implementation of class SampleSpaceWithReplacement is given next. Comments, delimited by double quotes, are given in each method to indicate its purpose.

<table><tr><td>class name</td><td>SampleSpaceWithReplacement</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>data<br/>rand</td></tr></table>

class methods

instance creation

data: aSequenceableCollection

"Create an instance of SampleSpaceWithReplacement such that the argument, aSequenceableCollection, is the sample space."

tself new: aSequenceableCollection

instance methods

accessing

next

"The next element selected is chosen at random from the data collection. The index into the data collection is determined by obtaining a
random number between 0 and 1, and normalizing it to be within the
range of the size of the data collection."

self.isEmpty

ifTrue: [self error: 'no values exist in the sample space'].

↑data at: (rand next * data size) truncated + 1

next: anInteger

"Answer an OrderedCollection containing anInteger number of selec-
tions from the data collection."

| aCollection |

aCollection ← OrderedCollection new: anInteger.

anInteger timesRepeat: [aCollection addLast: self next].

↑aCollection

testing

"Answer whether any items remain to be sampled."

↑self size = 0

size

"Answer the number of items remaining to be sampled."

↑data size

private

setData: aSequenceableCollection

"The argument, aSequenceableCollection, is the sample space. Create
a random number generator for sampling from the space."

data ← aSequenceableCollection.

rand ← Random new

The class description declares that each instance has two variables
whose names are data and rand. The initialization message. data:, sends
the new instance the message: in which data is bound to a
SequenceableCollection (the value of the argument of the initialization
message) and rand is bound to a new instance of class Random.

SampleSpaceWithReplacement is not a subclass of Collection because
it implements only a small subset of the messages to which Collections
can respond. In response to the messages next and size to a
SampleSpaceWithReplacement, the messages at: and size are sent to the
instance variable data. This means that any collection that can respond
to at: and size can serve as the data from which elements are sampled.
All SequenceableCollections respond to these two messages. So, for ex-
ample, in addition to an Array as illustrated earlier, the data can be an
Interval. Suppose we wish to simulate the throw of a die. Then the ele-
ments of the sample space are the positive integers 1 through 6.
die → SampleSpaceWithReplacement data: (1 to: 6)

A throw of the die is obtained by evaluating

die next

The response from this message is one of the Integers, 1, 2, 3, 4, 5, or 6.

We could select a card from a deck of cards in a similar way if the collection associated with the instance of SampleSpaceWithReplacement consists of elements representing playing cards. In order to play card games, however, we have to be able to deal a card out to a player and remove it from the deck. So, we have to use random selection without replacement.

To implement random selection without replacement, we define the response to the message next as removing the selected element. Since all SequenceableCollections do not respond to the message remove:, (for example, Interval does not) we either must check the argument of the initialization message or we must convert the argument to an acceptable kind of collection. Since all OrderedCollections respond to the two messages, and since all collections can be converted to an OrderedCollection, we can use the conversion approach. The method associated withassearch: sends its argument the message asOrderedCollection in order to accomplish the goal.

Class SampleSpaceWithoutReplacement is defined to be a subclass of SampleSpaceWithReplacement. The methods associated with the messages next andassearch: are overridden; the remaining messages are inherited without modification.

<table><tr><td>class name</td><td>SampleSpaceWithoutReplacement</td></tr><tr><td>superclass</td><td>SampleSpaceWithReplacement</td></tr><tr><td>instance methods</td><td></td></tr></table>

accessing

next

↑data remove: super next

private

assearch: aCollection

data → aCollection asOrderedCollection.

rand → Random new

Notice that the method for next depends on the method implemented in the superclass (super next). The superclass's method checks to make certain that the sample space is not empty and then randomly selects an element. After determining the selected element, the subclass's method removes the element from data. The result of the remove: message is
the argument, so that the result of the message next to a `SampleSpaceWithoutReplacement` is the selected element.

Now let's implement a simple card game. Suppose the sample space data for the card game are instances of a class `Card` where each `Card` knows its suit and rank. An instance of `Card` is created by sending it the message `suit:rank;`, specifying the suit (heart, club, spade, or diamond) and its rank (1, 2, ..., 13) as the two arguments. A `Card` responds to the messages `suit` and `rank` with the appropriate information.

<table><tr><td>class name</td><td>Card</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>suit<br>rank</td></tr></table>

class methods

instance creation

**suit: aSymbol rank: anInteger**

"Create an instance of `Card` whose suit is the argument, `aSymbol`, and whose rank is the argument, `anInteger`."

↑self new setSuit: aSymbol rank: anInteger

instance methods

accessing

**suit**

"Answer the receiver's suit."

↑suit

**rank**

"Answer the receiver's rank."

↑rank

private

**setSuit: aSymbol rank: anInteger**

suit ← aSymbol.

rank ← anInteger

A deck of cards, `cardDeck`, is created by the following expressions.

`cardDeck ← OrderedCollection new: 52.`

`#(heart club spade diamond) do:`

```
[ :eachSuit |
  1 to: 13 do: [ :n | cardDeck add: (Card suit: eachSuit rank: n)]]
```

The first expression creates an `OrderedCollection` for 52 elements. The second expression is an enumeration of the ranks 1 through 13 for each of the four suits: heart, club, spade, and diamond. Each element of the `OrderedCollection` is set to be a `Card` with a different suit and rank.
The ability to sample from this deck of cards is obtained by creating an instance of SampleSpaceWithoutReplacement with the card deck as the collection from which samples will be taken

cards ← SampleSpaceWithoutReplacement data: cardDeck

To deal a card, evaluate the expression

cards next

The response to this message is an instance of class Card.

Another way to provide a deck of playing cards is illustrated in the description of example class CardDeck. The basic idea is to store a linear list of cards; next means supply the first card in the list. A card can be returned to the deck by placing it at the end or by inserting it at some random position. The linear list is made random by shuffling—that is, randomly ordering the cards.

In the implementation of class CardDeck provided next, we store an initial version of the deck of cards as a class variable. It is created using the expressions given earlier. A copy of this variable is made as an instance variable whenever a new instance is created; it is shuffled before cards are dealt out. Each subsequent shuffle of the deck uses the current state of the instance variable, not of the class variable. Of course, the shuffling process, since it is based on the use of an instance of SampleSpaceWithoutReplacement, is quite uniform. A simulation of real shuffling involves first splitting the deck approximately in half and then interleaving the two halves. The interleaving involves selecting chunks from one half and then the other half. Indeed, such a simulation may be more random than an actual person's shuffling; a person's shuffling ability might be observable and predictable.

Messages to a CardDeck, such as return, next, and shuffle, are useful in creating card games.

<table><tr><td>class name</td><td>CardDeck</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>cards</td></tr><tr><td>class variable names</td><td>InitialCardDeck</td></tr><tr><td>class methods</td><td></td></tr></table>

class initialization

initialize

"Create a deck of 52 playing cards."

InitialCardDeck ← OrderedCollection new: 52.

#(heart club spade diamond) do:

[ :aSuit |

1 to: 13

do: [ :n | InitialCardDeck add: (Card suit: aSuit rank: n)]]
### instance creation

**new**

"Create an instance of CardDeck with an initial deck of 52 playing cards."

↑super new cards: InitialCardDeck copy

### instance methods

### accessing

**next**

"Deal (give out) the next card."

↑cards removeFirst

**return: aCard**

"Put the argument, aCard, at the bottom of the deck."

cards addLast: aCard

**shuffle**

| sample tempDeck |

sample ← SampleSpaceWithoutReplacement data: cards.

tempDeck ← OrderedCollection new: cards size.

cards size timesRepeat: [tempDeck addLast: sample next].

self cards: tempDeck

### testing

****

"Answer whether any more cards remain in the deck."

↑cards empty

### private

**cards: aCollection**

cards ← aCollection

The class CardDeck must be initialized by evaluating the expression

### CardDeck initialize

In the implementation of CardDeck, cards is the instance variable and
is therefore the deck of cards used in playing a game. To play a game,
an instance of CardDeck is created

### CardDeck new

and then each card is dealt by sending this new instance the message
next. When a card is put back in the deck, the CardDeck is sent the
message return: Shuffling always shuffles whichever cards are currently in the deck. If a full CardDeck is to be reused after a round of play, any cards taken from the deck must be returned.

Note the implementation of the message shuffle. A sample space without replacement, sample, is created for a copy of the current deck of cards. A new OrderedCollection, tempDeck, is created for storing randomly selected cards from this sample space. Sampling is done from sample for each possible card; each selected card is added to the tempDeck. Once all the available cards have been shuffled into it, tempDeck is stored as the current game deck.

Suppose we create a simple card game in which there are four players and a dealer. The dealer deals out cards to each of the players. If at least one of the players has between 18 and 21 points, the game ends with the "prize" divided among each of these players. Points are counted by adding up the ranks of the cards. A player with more than 21 points is not dealt new cards.

Each player is represented by an instance of class CardHand that represents a card hand. A CardHand knows the cards it is dealt and can determine its total point count (in response to the message points).

<table><tr><td>class name</td><td>CardHand</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>cards</td></tr><tr><td>class methods</td><td></td></tr></table>

instance creation

new

↑super new setCards

instance methods

accessing

take: aCard

"The argument, aCard, is added to the reciever."

cards add: aCard

returnAllCardsTo: cardDeck

"Place all of the receiver's cards into the deck of cards referred to by the argument, cardDeck, and remove these cards from the receiver's hand."

cards do: [ :eachCard | cardDeck return: eachCard].

self setCards
inquiries

points

"Answer the sum of the ranks of the receiver's cards."
tcards inject: 0 into: [ :value :nextCard | value + nextCard rank]

private

setCards

cards ← OrderedCollection new

We create a Set of four players. Each player is represented by an instance of CardHand. The dealer's cards are the gameCards. The dealer (that is, the programmer) starts by shuffling the deck; there is no winner yet. There may be more than one winner; winners will be listed in the Set, winners.

players ← Set new.
4 timesRepeat: [players add: CardHand new].
gameCards ← CardDeck new.
gameCards shuffle

As long as there is no winner, each player with less than 21 points is given another card from the gameCards. Before dealing a card to each eligible player, the dealer looks to see if there are any winners by testing the points for each player.

[ winners ← players select: [ :each | each points between: 18 and: 21].
winners empty? and: [gameCards empty? not]]
whileTrue:
[ players do:
    [ :each |
        each points < 21 ifTrue: [each take: gameCards next]]

The condition for continuing to play is a block with two expressions. The first expression determines the winners, if any. The second expression tests to see if there are any winners yet (winners empty?) and, if not, if there are any more cards to deal out (gameCards empty? not). If there are no winners and more cards, the game continues. The game consists of an enumeration of each player; each player takes another card (each take: gameCards next) only if the number of card points is less than 21 (each points < 21).

To play again, all cards have to be returned to the game deck, which is then shuffled.

players do: [ :each | each returnAllCardsTo: gameCards].
gameCards shuffle

The players and dealer are ready to play again.
## The Drunken Cockroach Problem

We can use some of the collection classes to solve a well-known programming problem. The problem is to measure how long it takes a drunken cockroach to touch each tile of a floor of square tiles which is N tiles wide and M tiles long. To slightly idealize the problem: in a given "step" the cockroach is equally likely to try to move to any of nine tiles, namely the tile the roach is on before the step and the tiles immediately surrounding it. The cockroach's success in moving to some of these tiles will be limited, of course, if the cockroach is next to a wall of the room. The problem is restated as counting the number of steps it takes the cockroach to land on *all* of the tiles at least once.

One straightforward algorithm to use to solve this problem starts with an empty Set and a counter set to 0. After each step, we add to the Set the tile that the cockroach lands on and increment a counter of the number of steps. Since no duplication is allowed in a Set, we would be done when the number of elements in the Set reaches N*M. The solution would be the value of the counter.

While this solves the simplest version of the problem, we might also like to know some additional information, such as how many times each tile was visited. To record this information, we can use an instance of class Bag. The size of the Bag is the total number of steps the cockroach took; the size of the Bag when it is converted to a Set is the total number of distinct tiles touched by the cockroach. When this number reaches N*M, the problem is solved. The number of occurrences of each tile in the Bag is the same as the number of times the roach visited each tile.

Each tile on the floor can be labeled with respect to its row and its column. The objects representing tiles in the solution we offer are instances of class Tile. A commented implementation of class Tile follows.

<table><tr><td>class name</td><td>Tile</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>location<br/>floorArea</td></tr><tr><td>instance methods</td><td></td></tr></table>

accessing

**location**

"Answer the location of the receiver on the floor."

↑location

**location: aPoint**

"Answer the location of the receiver on the floor."

↑location

**location: aPoint**

"Set the receiver's location on the floor to be the argument, aPoint."

location ← aPoint
**floorArea: aRectangle**

"Set the floor area to be the rectangular area represented by the argument, aRectangle."

floorArea ← aRectangle

moving

**neighborAt: deltaPoint**

"Create and answer a new Tile that is at the location of the receiver changed by the x and y amounts represented by the argument, deltaPoint. Keep the location of the newTile within the boundaries of the floor area."

| newTile |

newTile ← Tile new floorArea: floorArea.

newTile location: ((location + deltaPoint max: floorArea origin)
                 min: floorArea corner).

↑newTile

comparing

**= aTile**

"Answer whether the receiver is equal to the argument, aTile."

↑(aTile isKindOf: Tile) and: [location = aTile location]

**hash**

↑location hash

A Tile refers to its row and column locations, each of which must be at least 1 and no larger than the width or length of the floor. Therefore, in addition to remembering its location, a Tile must remember the maximum floor space in which it can be placed. A Tile can be sent the message `neighborAt: aPoint` in order to determine a Tile at one of the locations next to it. This new Tile must be at a location within the boundaries of the floor.

The way we will simulate the cockroach's walk is to select a direction in terms of changes in the x-y coordinates of the cockroach's location. Given the location of the cockroach (tile x,y), there are 9 tiles to which the insect can move unless the tile is along one of the edges. We will store the possible changes of x and y in an OrderedCollection that is the data for random selection. The OrderedCollection will contain Points as elements; the Points are direction vectors representing all the possible combinations of moves. We create this collection by the expressions

Directions ← OrderedCollection new: 9.

(-1 to: 1) do: [ :x | (-1 to: 1) do: [ :y | Directions add: x@y]]

Directions, then, is a collection with elements

-1@-1, -1@0, -1@1, 0@-1, 0@0, 0@1, 1@-1, 1@0, 1@1
As part of the drunken walk simulation, we will generate a random number for selecting an element from this OrderedCollection of possible moves. As an alternative to using a random number generator directly, we could use the previous example's SampleSpaceWithReplacement with Directions as the sample space.

Suppose the cockroach starts on the Tile that is at location 1@1. Each time the cockroach is supposed to take a step, we obtain an element from the collection, Directions. This element is then the argument of the message neighborAt: to the Tile. In the following, assume Rand is an instance of class Random.

### tile neighborAt:

(Directions at: ((Rand next * Directions size) truncated + 1)).

The resulting new tile location is the place where the cockroach landed.

Each tile position has to be remembered in order to be able to report on whether every location has been touched and how many steps were required. By storing each tile in a Bag, a tally is kept of the number of times the cockroach landed in each location. So at each step, a new tile is created that is a copy of the previous tile. This new tile is changed according to the randomly selected direction and is added to the Bag. When the number of unique elements of the Bag equals the total number of tiles, the cockroach is done.

Only two messages are needed in class DrunkenCockroach. One is a command to have the cockroach take a walk around a specific floor area until every tile on the floor has been touched. This is the message walkWithin:startingAt:. The second is an inquiry as to the number of steps the cockroach has taken so far; this is the message numberOfSteps. We can also inquire about the number of times the roach stepped on a particular tile by sending the DrunkenCockroach the message timesSteppedOn:. The collection of direction vectors (as described earlier) is created as a class variable of DrunkenCockroach; the random number generator Rand is also a class variable of DrunkenCockroach.

<table><tr><td>class name</td><td>DrunkenCockroach</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>currentTile<br/>tilesVisited</td></tr><tr><td>class variable names</td><td>Directions<br/>Rand</td></tr></table>

### class methods

### class initialization

#### initialize

"Create the collection of direction vectors and the random number generator."
Three Examples That Use Collections

Directions ← OrderedCollection new: 9.

(-1 to: 1) do: [ :x | (-1 to: 1) do: [ :y | Directions add: x@y]].

Rand ← Random new

instance creation

new

↑super new setVariables

instance methods

simulation

walkWithin: aRectangle startingAt: aPoint

| numberTiles |

tilesVisited ← Bag new.

currentTile location: aPoint.

currentTile floorArea: aRectangle.

numberTiles ← (aRectangle width + 1) * (aRectangle height + 1).

tilesVisited add: currentTile.

[tilesVisited asSet size < numberTiles] whileTrue:

[currentTile ← currentTile neighborAt:

(Directions at: (Rand next * Directions size) truncated + 1).

tilesVisited add: currentTile]

data

numberOfSteps

†tilesVisited size

timesSteppedOn: aTile

†tilesVisited occurrencesOf: aTile

private

setVariables

currentTile ← Tile new.

tilesVisited ← Bag new

We can now send the following messages in order to experiment with a
drunken cockroach. Initialize the class and create an instance.

DrunkenCockroach initialize.

cockroach ← DrunkenCockroach new

Obtain the results of 10 experiments with a 5 by 5 room.

results ← OrderedCollection new: 10.

10 timesRepeat:

[cockroach walkWithin: (1@1 corner: 5@5) startingAt: (1@1).

results add: cockroach numberOfSteps]
The average of the 10 results is the average number of steps it took the drunken cockroach to solve the problem.

(results inject: 0 into: [ :sum :exp | sum + exp]) / 10

Note that in the implementation of the *Drunken Cockroach* message *walkWithin:startingAt*, the termination condition is whether the *Bag*, when converted to a *Set*, has *N*\*M elements. A faster way to make this test would be to add the message *uniqueElements* to the class *Bag* so that the conversion to a *Set* is not done each time through the iteration.

(For those readers wishing to try this change, the method to be added to *class Bag* is)

### uniqueElements

†contents size

Then the message *walkWithin:startingAt*: can be changed so that the termination condition is *tilesVisited uniqueElements* < *numberTiles*.)

## Traversing Binary Trees

A tree is an important nonlinear data structure that is useful in computer algorithms. A tree structure means that there is a branching relationship between elements. There is one element designated as the root of the tree. If there is only one element, then it is the root. If there are more elements, then they are partitioned into disjoint (sub)trees. A binary tree is either the root only, the root with one binary (sub)tree, or the root together with two binary (sub)trees. A complete description of the genealogy of tree structures is provided by Knuth in Volume 1 of the *Art of Computer Programming*. Here we assume the reader is familiar with the idea so that we can demonstrate how to specify the data structure as a Smalltalk-80 class.

We will define a class *Tree* in a way that corresponds to the definition of *LinkedList*. Elements of a *Tree* will be *Nodes* that are like the *Links* of *LinkedLists*, able to make connections to other elements. The *Tree* will reference the root node only.

A node is simple to represent as a Smalltalk-80 object with two instance variables, one refers to the *left* node and another to the *right* node. We choose to treat the order of the nodes to support *in-order traversal*. That is, in enumerating the nodes, visit the left subnode first, the root second, and the right subnode third. If a node has no subnodes, then it is called a *leaf*. We define the *size* of the node to be 1 plus the size of its subnodes, if any. Thus a *leaf* is a node of size 1, and a node
with two leaves as subnodes has size 3. The size of a tree is the size of its root node. This definition of *size* corresponds to the general notion of size for collections.

Messages to a Node give access to the left node, the right node, and the last or end node. It is also possible to remove a subnode (remove:ifAbsent:) and the root (rest).

<table><tr><td>class name</td><td>Node</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>leftNode<br/>rightNode</td></tr></table>

class methods

instance creation

**left: INode right: rNode**

"Create an instance of a Node with the arguments INode and rNode as the left and right subnodes, respectively."

```
| newNode |
newNode ← self new.
newNode left: INode.
newNode right: rNode.
↑newNode
```

instance methods

testing

**isLeaf**

"Answer whether the receiver is a leaf, that is, whether it is a node without any subnodes."

```
↑leftNode isNil & rightNode isNil
```

accessing

**left**

```
↑leftNode
```

**left: aNode**

```
leftNode ← aNode
```

**right**

```
↑rightNode
```

**right: aNode**

```
rightNode ← aNode
```
### size

11 + (leftNode isNil
    ifTrue: [0]
    ifFalse: [leftNode size])
+ (rightNode isNil
    ifTrue: [0]
    ifFalse: [rightNode size])

### end

| aNode |
aNode - self.
[aNode right isNil] whileFalse: [aNode - aNode right].
↑aNode

### removing

#### remove: subnode ifAbsent: exceptionBlock

"Assumes the root, self, is not the one to remove."
self isLeaf ifTrue: [↑exceptionBlock value].
leftNode = subnode
    ifTrue: [leftNode - leftNode rest. ↑subnode].
rightNode = subnode
    ifTrue: [rightNode - rightNode rest. ↑subnode].
leftNode isNil
    ifTrue: [↑rightNode remove: subnode ifAbsent: exceptionBlock].
↑leftNode
    remove: subnode
    ifAbsent:
        [rightNode isNil
            ifTrue: [exceptionBlock value]
            ifFalse:
                [rightNode remove: subnode
                    ifAbsent: exceptionBlock]]

### rest

leftNode isNil
    ifTrue: [↑rightNode]
    ifFalse: [leftNode end right: rightNode.
               ↑leftNode]

### enumerating

#### do: aBlock

leftNode isNil ifFalse: [leftNode do: aBlock].
aBlock value: self.
rightNode isNil ifFalse: [rightNode do: aBlock]
<figure><img src="image_110.png" /></figure>

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

Enumeration uses in-order traversal, first applying the left subnode as the value of the block, then the root, and third the right subnode. The block must be defined for a block argument that is a Node.

Next we provide a Tree as a kind of SequenceableCollection whose elements are Nodes. A Tree has one instance variable which we name root; root is either nil or it is an instance of Node. As a subclass of SequenceableCollection, class Tree implements messages add: anElement, remove: anElement ifAbsent: exceptionBlock, and do: aBlock. Basically, the methods associated with each of these messages checks to see whether the tree is empty (root isNil) and, if not, passes the appropriate message to root. The check on "empty" is inherited from Collection. The intention is that the programmer who uses a tree structure accesses the elements of that structure only via an instance of class Tree.

<table><tr><td>class name</td><td>Tree</td></tr><tr><td>superclass</td><td>SequenceableCollection</td></tr><tr><td>instance variable names</td><td>root</td></tr><tr><td>instance methods</td><td></td></tr></table>

testing

## isEmpty

root isNil

accessing

## first

| save |
self emptyCheck.
save - root.
[save left isNil] whileFalse: [save ← save left].
↑save

**last**

self emptyCheck.
↑root end

**size**

self isEmpty
  ifTrue: [↑0]
  ifFalse: [↑root size]

**adding**

**add: aNode**

↑self addLast: aNode

**addFirst: aNode**

"If the collection is empty, then the argument, aNode, is the new root; otherwise, it is the left node of the current first node."

self isEmpty
  ifTrue: [↑root ← aNode]
  ifFalse: [self first left: aNode].
↑aNode

**addLast: aNode**

"If the collection is empty, then the argument, aNode, is the new root; otherwise it is the last element of the current root."

self emptyCheck.
  ifTrue: [root ← aNode]
  ifFalse: [self last right: aNode].
↑aNode

**removing**

**remove: aNode ifAbsent: exceptionBlock**

"First check the root. If not found, move down the tree checking each node."

self emptyCheck ifTrue: [↑exceptionBlock value].

root = aNode
  ifTrue: [root ← root rest. ↑aNode]
  ifFalse: [↑root remove: aNode ifAbsent: exceptionBlock]

**removeFirst**

self emptyCheck.
↑self remove: self first ifAbsent: []

**removeLast**

self emptyCheck.
↑self remove: self last ifAbsent: []

**enumerating**

**do: aBlock**

self emptyCheck ifFalse: [root do: aBlock]
Note that the removing messages do not remove the subtree beginning with the node to be removed, only the node itself.

## A Binary Word Tree

The definition of a Node, like that of a Link, is all structure without content. We have left the content of each Node to be specified by a sub-class. Suppose we wish to use a kind of Node to store words represented as Strings. We call this class WordNode. An instance of WordNode is created by sending WordNode the message for:., if no subnodes are specified, or for:left:right: if the two subnodes are specified. So a WordNode illustrated as

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

is created by evaluating the expression

`WordNode for: 'cat'`

A WordNode that looks like

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

is created by evaluating the expression

`WordNode for: 'cat'`
`left: (WordNode for: 'dog')`
`right: (WordNode for: 'goat')`

An implementation for the class WordNode follows. Notice that equality (`=`) is redefined to mean that the words in the Nodes are the same; this means that the inherited removing messages will remove a subnode if its word is the same as the word of the argument.

<table><tr><td>class name</td><td>WordNode</td></tr><tr><td>superclass</td><td>Node</td></tr><tr><td>instance variable names</td><td>word</td></tr><tr><td>class methods</td><td></td></tr></table>

instance creation

`for: aString`

`↑self new word: aString`
**for: aString left: INode right: rNode**

| newNode |
newNode ← super left: INode right: rNode.
newNode word: aString.
↑newNode

instance methods

accessing

**word**

↑word

**word: aString**

word ← aString

comparing

= **aWordNode**

↑(aWordNode isKindOf: WordNode) and: [word = aWordNode word]

**hash**

↑word hash

A sequence of expressions follows to illustrate the use of WordNode.
Note that no effort is made in the definition of WordNode to support in-
serting elements so that each word collates alphabetically when the
tree is traversed. An interested reader might add an insert: aWordNode
message to WordNode that maintains the alphabetic sort.

tree → Tree new.

tree add: (WordNode for: 'cat')

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

tree addFirst: (WordNode for: 'frog')

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

tree addLast: (WordNode for: 'horse' left: (WordNode for: 'monkey') right: nil)

<figure><img src="image_116.png" /></figure>
Three Examples That Use Collections

<figure><img src="image_117.png" /><figcaption>tree remove: (WordNode for: 'horse')</figcaption></figure>

<figure><img src="image_118.png" /><figcaption>tree remove: (WordNode for: 'frog')</figcaption></figure>

<figure><img src="image_119.png" /></figure>
# 12

## Protocol for Streams

* Class Stream

* Positionable Streams

* Class ReadStream

* Class WriteStream

* Class ReadWriteStream

* Streams of Generated Elements

* Streams for Collections Without External Keys

* External Streams and File Streams

<figure><img src="image_120.png" /></figure>
Object

Magnitude

Character

Date

Time

Number

Float

Fraction

Integer

LargeNegательInteger

LargePositiveInteger

SmallInteger

LookupKey

Association

Link

Process

Collection

SequenceableCollection

LinkedList

Semaphore

ArrayedCollection

Array

Bitmap

DisplayBitmap

RunArray

String

Symbol

Text

ByteArray

Interval

OrderedCollection

SortedCollection

Bag

MappedCollection

Set

Dictionary

IdentityDictionary

Stream

PositionableStream

ReadStream

WriteStream

ReadWriteStream

ExternalStream

FileStream

Random

File

FileDirectory

FilePage

UndefinedObject

Boolean

False

True

ProcessorScheduler

Delay

SharedQueue

Behavior

ClassDescription

Class

MetaClass

Point

Rectangle

BitBit

CharacterScanner

Pen

DisplayObject

DisplayMedium

Form

Cursor

DisplayScreen

InfiniteForm

OpaqueForm

Path

Arc

Circle

Curve

Line

LinearFit

Spline
The collection classes provide the basic data structure for storing objects together as nonlinear and linear groups. The protocol for these classes makes it possible directly to access (store and retrieve) individual elements. It also, through the enumeration messages, supports noninterruptible accessing of all of the elements, in order. However, it does not support intermingling the two kinds of accessing operations—enumerating and storing. Nor does the collection protocol support accessing individual elements, one at a time, unless an external position reference is separately maintained.

Unless an easily computed external name for each element exists, in-
terruptible enumeration of individual elements can not be carried out
efficiently. It is possible, for example, sequentially to read elements of
an OrderedCollection using a combination of first and after, as long as
the elements of the collection are unique. An alternative approach in-
volves the collection itself remembering, in some way, which element
was last accessed. We call this the "position reference" in the discussion
that follows. The possibility of shared access to a sequence of elements,
however, means that it is necessary to maintain a separate, external
memory of the last element accessed.

Class Stream represents the ability to maintain a position reference
into a collection of objects. We use the phrase streaming over a collection to mean accessing the elements of a collection in such a way that it
is possible to enumerate or store each element, one at a time, possibly
intermingling these operations. By creating several Streams over the
same collection, it is possible to maintain multiple position references
into the same collection.

There are a number of ways to maintain a position reference for
streaming over a collection. A common one is to use an integer as an
index. This approach can be used for any collection whose elements are
externally named by an integer. All SequenceableCollections fall into
this category. As we shall describe later, such a Stream is represented
in the Smalltalk-80 system by the class PositionableStream. A second
way to maintain a position reference is to use a seed for a generator of
objects. An example of this kind of Stream in the Smalltalk-80 system is
class Random which was already presented in Chapter 8. And a third
way is to maintain a non-numerical position reference, such as a refer-
ence to a node in a sequence; this approach is illustrated in this chapter
by an example class that supports streaming over a linked list or a tree
structure.

Class Stream

Class Stream, a subclass of class Object, is a superclass that specifies the
accessing protocol for streaming over collections. Included in this proto-
col are messages for reading (retrieving) and writing (storing) into the
collection, although not all the subclasses of class Stream can support both kinds of accessing operations. The basic reading message is next; its response is the next element in the collection that is referenced by the Stream. Given the ability to access the next element, more general reading messages can be supported. These are next: anInteger, which re- sponds with a collection of anInteger number of elements; nextMatchFor: anObject, which reads the next element and answers whether it is equal to the argument, anObject; and contents, which answers a collection of all of the elements.

Stream instance protocol

<table><tr><td>accessing—reading</td><td></td></tr><tr><td>next</td><td>Answer the next object accessible by the receiver.</td></tr><tr><td>next: anInteger</td><td>Answer the next anInteger number of objects accessible by the receiver. Generally, the answer will be a collection of the same class as the one accessed by the receiver.</td></tr><tr><td>nextMatchFor: anObject</td><td>Access the next object and answer whether it is equal to the argument, anObject.</td></tr><tr><td>contents</td><td>Answer all of the objects in the collection accessed by the receiver. Generally, the answer will be a collection of the same class as the one accessed by the receiver.</td></tr></table>

The basic writing message is nextPut: anObject; this means to store the argument, anObject, as the next element accessible by the receiver. If both read and write messages are possible, a next message following a nextPut: anElement does not read the element just stored, but rather the one after it in the collection. Writing messages also include nextPutAll: aCollection, which stores all of the elements in the argument into the collection accessed by the receiver, and next: anInteger put: anObject, which stores the argument, anObject, as the next anInteger number of elements.

Stream instance protocol

<table><tr><td>accessing—writing</td><td></td></tr><tr><td>nextPut: anObject</td><td>Store the argument, anObject, as the next element accessible by the receiver. Answer anObject.</td></tr><tr><td>nextPutAll: aCollection</td><td>Store the elements in the argument, aCollection, as the next elements accessible by the receiver. Answer aCollection.</td></tr><tr><td>next: anInteger put: anObject</td><td>Store the argument, anObject, as the next anInteger number of elements accessible by the receiver. Answer anObject.</td></tr></table>

The reading and writing messages each determine if a next element can
be read or written and, if not, an error is reported. The programmer might therefore wish to determine whether accessing is still feasible; this is accomplished by sending the Stream the message atEnd.

Stream instance protocol

testing

atEnd

Answer whether the receiver cannot access any more objects.

Noninterrupted reading of elements that are applied as arguments to a block can be done by sending the message do: aBlock, similar to the enumerating message supported by the collection classes.

Stream instance protocol

enumerating

do: aBlock

Evaluate the argument, aBlock, for each of the remaining elements that can be accessed by the receiver.

The implementation of this enumeration message depends on sending the messages atEnd and next to the message receiver. We show this method as an example of the use of these messages.

do: aBlock

[self atEnd] whileFalse: [aBlock value: self next]

Each kind of Stream must specify its instance creation messages. In general, a Stream can not be created simply by sending the message new because the Stream must be informed of which collection it accesses and what is its initial position reference.

As a simple example, let's assume that the collection accessed by a Stream is an Array and that the Stream is called accessor. The contents of the Array are the Symbols

Bob Dave Earl Frank Harold Jim Kim Mike Peter Rick Sam Tom

and the position reference is such that Bob is the next accessible element. Then

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>accessor next</td><td>Bob</td></tr><tr><td>accessor next</td><td>Dave</td></tr><tr><td>accessor</td><td>false</td></tr><tr><td>nextMatchFor: #Bob</td><td></td></tr></tbody></table>
<table><tr><td>accessor</td><td>true</td></tr><tr><td>nextMatchFor: #Frank</td><td></td></tr><tr><td>accessor next</td><td>Harold</td></tr><tr><td>accessor nextPut: #James</td><td>James</td></tr><tr><td>accessor contents</td><td>(Bob Dave Earl Frank<br/>Harold James Kim<br/>Mike Peter Rick<br/>Sam Tom)</td></tr><tr><td>accessor</td><td>(Karl Larry Paul)</td></tr><tr><td>nextPutAll:<br/>#(Karl Larry Paul)</td><td></td></tr><tr><td>accessor contents</td><td>(Bob Dave Earl Frank<br/>Harold James Karl<br/>Larry Paul Rick Sam<br/>Tom)</td></tr><tr><td>accessor next: 2 put: #John</td><td>John</td></tr><tr><td>accessor contents</td><td>(Bob Dave Earl Frank<br/>Harold James Karl<br/>Larry Paul John<br/>John Tom)</td></tr><tr><td>accessor next</td><td>Tom</td></tr><tr><td>accessor atEnd</td><td>true</td></tr></table>

## Positionable Streams

In the introduction to this chapter we indicated three possible approaches that a Stream might use in order to maintain a position reference. The first one we will present uses an integer index which is incremented each time the Stream is accessed. The Stream accesses only those kinds of collections whose elements have integers as external keys; these include all of the subclasses of SequenceableCollection.

Class PositionableStream is a subclass of class Stream. It provides additional protocol appropriate to Streams that can reposition their position references, but, it is an abstract class because it does not provide an implementation of the inherited messages next and nextPut: anObject. The implementation of these messages is left to the subclasses of PositionableStream—ReadStream, WriteStream, and ReadWriteStream.

A PositionableStream is created by sending the class one of two instance creation messages, on: aCollection or on: aCollection from: firstIndex to: lastIndex. The argument, aCollection, is the collection the Stream accesses; in the second case, a copy of a subcollection of aCollection is accessed, i.e., the one delimited by the two arguments firstIndex and lastIndex.
PositionableStream class protocol

instance creation

on: aCollection

Answer an instance of a kind of
PositionableStream that streams over the argu-
ment, aCollection.

on: aCollection from: firstIndex to: lastIndex

Answer an instance of a kind of
PositionableStream that streams over a copy of
a subcollection of the argument, aCollection,
from firstIndex to lastIndex.

PositionableStream supports additional protocol for accessing and testing the contents of the collection.

PositionableStream instance protocol

testing

empty

Answer true if the collection the receiver
accesses has no elements; otherwise, answer
false.

accessing

peek

Answer the next element in the collection (as
in the message next), but do not change the
position reference. Answer nil if the receiver is
at the end.

peekFor: anObject

Determine the response to the message peek.
If it is the same as the argument, anObject,
then increment the position reference and an-
swer true. Otherwise answer false and do not
change the position reference.

upTo: anObject

Answer a collection of elements starting with
the next element accessed by the receiver, and
up to, not inclusive of, the next element that
is equal to anObject. If anObject is not in the
collection, answer the entire rest of the collec-
tion.

reverseContents

Answer a copy of the receiver's contents in reverse order.

Since a PositionableStream is known to store an explicit position refer-
ence, protocol for accessing that reference is supported. In particular,
the reference can be reset to access the beginning, the end, or any other
position of the collection.

PositionableStream instance protocol

positioning

position

Answer the receiver's current position refer-
ence for accessing the collection.

position: anInteger

Set the receiver's current position reference
for accessing the collection to be the argu-
ment, anInteger. If the argument is not within
reset

setToEnd

skip: anInteger

skipTo: anObject

the bounds of the receiver's collection, report an error.

Set the receiver's position reference to the beginning of the collection.

Set the receiver's position reference to the end of the collection.

Set the receiver's position reference to be the current position plus the argument, anInteger, possibly adjusting the result so as to remain within the bounds of the collection.

Set the receiver's position reference to be past the next occurrence of the argument, anObject, in the collection. Answer whether such an occurrence existed.

Class ReadStream
Class ReadStream is a concrete subclass of PositionableStream that represents an accessor that can only read elements from its collection. We can create an example similar to the previous one to demonstrate the use of the additional protocol provided in class PositionableStream and inherited by all ReadStreams. None of the nextPut, next:put, nor nextPutAll: messages can be successfully sent to a ReadStream.

accessor →

ReadStream on: #(Bob Dave Earl Frank Harold Jim Kim Mike Peter Rick Sam Tom)

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>accessor next</td><td>Bob</td></tr><tr><td>accessor nextMatchFor: #Dave</td><td>true</td></tr><tr><td>accessor peek</td><td>Earl</td></tr><tr><td>accessor next</td><td>Earl</td></tr><tr><td>accessor peekFor: #Frank</td><td>true</td></tr><tr><td>accessor next</td><td>Harold</td></tr><tr><td>accessor upTo: #Rick</td><td>(Jim Kim Mike Peter)</td></tr><tr><td>accessor position</td><td>10</td></tr><tr><td>accessor skip: 1</td><td>the accessor itself</td></tr><tr><td>accessor next</td><td>Tom</td></tr><tr><td>accessor atEnd</td><td>true</td></tr><tr><td>accessor reset</td><td>the accessor itself</td></tr><tr><td>accessor skipTo: #Frank</td><td>true</td></tr><tr><td>accessor next</td><td>Harold</td></tr></tbody></table>

Class WriteStream
Class WriteStream is a subclass of PositionableStream representing accessors for writing elements into a collection. None of the next, next:, nor do: messages can be successfully sent to a WriteStream.
WriteStreams are used throughout the Smalltalk-80 system as a part of the methods for printing or storing a string description of any object. Each object in the system can respond to the messages printOn: aStream and storeOn: aStream. The methods associated with these messages consist of a sequence of messages to the argument, which is a kind of Stream that allows writing elements into the collection it accesses. These messages are nextPut; where the argument is a Character, and nextPutAll; where the argument is a String or a Symbol. An example will illustrate this idea.

Class Object printing protocol, as described in Chapter 6, includes the message printString. An implementation of this message is

**printString**

| aStream |
aStream ← WriteStream on: (String new: 16).
self printOn: aStream.
taStream contents

If a collection is sent the message printString, then the answer is a String that is a description of the instance. The method creates a WriteStream that the collection can store into, sends the message printOn: to the collection, and then responds with the contents of the resulting WriteStream. The message storeString to any object is similarly implemented in class Object, the difference being that the second expression consists of the message storeOn: aStream rather than printOn: aStream.

The general way in which collections print a description of themselves is to print their class name followed by a left parenthesis, followed by a description of each element separated by spaces, and terminated by a right parenthesis. So if a Set has four elements—the Symbols one, two, three, and four—then it prints on a Stream as

Set (one two three four)

An OrderedCollection with the same elements prints on a Stream as

OrderedCollection (one two three four)

and so on.

Recall that the definition of printOn: and storeOn: given in Chapter 6 is that any suitable description can be provided for printOn:., but the description created by storeOn: must be a well-formed expression that, when evaluated, re-constructs the object it purports to describe.

Here is an implementation in class Collection for printOn:.
### printOn: aStream

aStream nextPutAll: self class name.

aStream space.

aStream nextPut: $().

self do:

[ :element |

element printOn: aStream.

aStream space].

aStream nextPut: $)

Notice that the message space is sent to the WriteStream (aStream). It, and a number of other messages are provided in class WriteStream to support concise expressions for storing delimiters into such Streams. They are

### WriteStream instance protocol

character writing

cr

Store the return character as the next element of the receiver.

crTab

Store the return character and a single tab character as the next two elements of the receiver.

crTab: anInteger

Store the return character as the next element of the receiver, followed by anInteger number of tab characters.

space

Store the space character as the next element of the receiver.

tab

Store the tab character as the next element of the receiver.

Thus to construct the String

<table><thead><tr><td>'name</td><td>city</td></tr></thead><tbody><tr><td>bob</td><td>New York</td></tr><tr><td>joe</td><td>Chicago</td></tr><tr><td>bill</td><td>Rochester</td></tr></tbody></table>

from two corresponding Arrays,

names ← # (bob joe bill)

cities ← # ('New York' 'Chicago' 'Rochester')

evaluate the expressions
aStream ← WriteStream on: (String new: 16).

aStream nextPutAll: 'name'.

aStream tab.

aStream nextPutAll: 'city'.

aStream cr; cr.

names with: cities do:

[ :name :city |
 aStream nextPutAll: name.
 aStream tab.
 aStream nextPutAll: city.
 aStream cr]

then the desired result is obtained by evaluating aStream contents.

Suppose a collection already exists and we wish to append further information into it by using `Stream` protocol. Class `WriteStream` supports instance creation protocol that accepts a collection and sets the position reference for writing to the end.

WriteStream class protocol

instance creation

with: aCollection
Answer an instance of WriteStream accessing the argument, aCollection, but positioned to store the next element at the end of it.

with: aCollection from: firstIndex to: lastIndex
Answer an instance of WriteStream accessing the subcollection of the argument, aCollection, from locaton firstIndex to lastIndex, but positioned to store the next element at the end of the subcollection.

Thus if a String referred to as header already existed, containing

'name city

then the previous example String would be constructed by

aStream ← WriteStream with: header.

names with: cities do:

[ :name :city |
 aStream nextPutAll: name.
 aStream tab.
 aStream nextPutAll: city.
 aStream cr].

aStream contents
Class
ReadWriteStream

Class ReadWriteStream is a subclass of WriteStream that represents an accessor that can both read and write elements into its collection. It supports all the protocol of both ReadStream and WriteStream, as given above.

## Streams of Generated Elements

Of the three ways to create a position reference for streaming over a collection, the second way cited in the introduction to this chapter was to specify a *seed* by which the next elements of the collection can be generated. This kind of Stream only permits reading the elements, not writing. The reference, however, can be repositioned by resetting the *seed*.

Class Random, introduced in Chapter 8, is a subclass of Stream that determines its elements based on an algorithm employing a number as a *seed*. Random provides a concrete implementation for next and atEnd. Because the size of the collection is infinite, it never ends; moreover, Random can not respond to the message contents. It can respond to the message `do;`, but the method will never end without the programmer's purposeful intervention.

The following is an implementation of class Random; the reader is referred to Chapters 11 and 21 for examples making use of instances of the class. The implementations for `do:` and `nextMatchFor:` `anObject` are inherited from class `Stream`.

<table><tr><td>class name</td><td>Random</td></tr><tr><td>superclass</td><td>Stream</td></tr><tr><td>instance variable names</td><td>seed</td></tr><tr><td>class methods</td><td></td></tr><tr><td>instance creation</td><td></td></tr></table>

**new**

`↑self basicNew setSeed`

instance methods

testing

**atEnd**

`↑false`

accessing

**next**

`| temp |`

"Lehmer's linear congruential method with modulus m = 2 raisedTo:
16, a = 27181 odd, and 5 = a \ 8, c = 13849 odd, and c/m approximately 0.21132"

[seed -> 13849 + (27181 * seed) bitAnd: 8r177777.

temp -> seed / 65536.0.

temp = 0] whileTrue.

item

private

### setSeed

"For pseudo-random seed, get a time from the system clock. It is a large positive integer; just use the lower 16 bits."

seed -> Time millisecondClockValue bitAnd: 8r177777

Another possible example of a stream of generated elements are the probability distributions that are presented in Chapter 21. The superclass ProbabilityDistribution is implemented as a subclass of Stream. The message next: anInteger is inherited from Stream. Each kind of ProbabilityDistribution determines whether it is "read-only" and, if so, implements nextPut: as self shouldNotImplement. Class SampleSpace, another example in Chapter 21, maintains a collection of data items and implements nextPut: anObject as adding to the collection.

## Streams for Collections Without External Keys

The third way to maintain a position reference for streaming over a collection cited in the introduction to this chapter was to maintain a non-numerical reference. This would be useful in cases where the elements of the collection cannot be accessed by external keys or where such access is not the most efficient means to retrieve an element.

Streaming over instances of class LinkedList provides an example in which the elements can be accessed by indexes as the external keys, but each such access requires a search down the chain of linked elements. It is more efficient to maintain a reference to a particular element in the collection (a kind of Link) and then to access the next element by requesting the current elements nextLink. Both reading and writing into the LinkedList can be supported by such a Stream.

Suppose we create a subclass of Stream that we call LinkedListStream. Each instance maintains a reference to a LinkedList and a position reference to an element in the collection. Since both reading and writing are supported, the messages next, nextPut, atEnd, and contents must be implemented. (Note that these four messages are defined in class Stream as self subclassResponsibility.) A new instance of LinkedListStream is created by sending it the message on: aLinkedList.
<table><tr><td>class name</td><td>LinkedListStream</td></tr><tr><td>superclass</td><td>Stream</td></tr><tr><td>instance variable names</td><td>collection<br>currentNode</td></tr></table>

class methods

instance creation

**on: aLinkedList**

↑self basicNew setOn: aLinkedList

instance methods

testing

**atEnd**

↑currentNode isNil

accessing

**next**

| saveCurrentNode |
saveCurrentNode ← currentNode.
self atEnd
ifFalse: [currentNode ← currentNode nextLink].
↑saveCurrentNode

**nextPut: aLink**

| index previousLink |
self atEnd ifTrue: [↑collection addLast: aLink].
index ← collection indexOf: currentNode.
index = 1
ifTrue: [collection addFirst: aLink]
ifFalse: [previousLink ← collection at: index - 1.
previousLink nextLink: aLink].
aLink nextLink: currentNode nextLink.
currentNode ← aLink nextLink.
↑aLink

private

**setOn: aLinkedList**

collection ← aLinkedList.
currentNode ← aLinkedList first

Now suppose in order to demonstrate the use of this new kind of
Stream we make up a LinkedList of nodes that are instances of class
WordLink; class WordLink is a subclass of Link that stores a String or a
Symbol.
<table><tr><td>class name</td><td>WordLink</td></tr><tr><td>superclass</td><td>Link</td></tr><tr><td>instance variable names</td><td>word</td></tr></table>

class methods

instance creation

**for: aString**

↑self new word: aString

instance methods

accessing

**word**

↑word

**word: aString**

word ← aString

comparing

**= aWordLink**

↑word = aWordLink word

printing

**printOn: aStream**

aStream nextPutAll: 'a WordLink for'.

aStream nextPutAll: word

From the above we can see that an instance of WordLink for the word
#one is created by

WordLink for: #one

Its print string is

'a WordLink for one'

We can then create a LinkedList of WordLinks and then a
LinkedListStream that accesses this LinkedList.

list ← LinkedList new.

list add: (WordLink for: #one).

list add: (WordLink for: #two).

list add: (WordLink for: #three).

list add: (WordLink for: #four).

list add: (WordLink for: #five).

accessor ← LinkedListStream on: list

Then an example sequence of messages to accessor is
<table><thead><tr><th>expression</th><th>result</th></tr></thead><tbody><tr><td>accessor next</td><td>a WordLink for one</td></tr><tr><td>accessor next</td><td>a WordLink for two</td></tr><tr><td>accessor nextMatchFor:<br>(WordLink for: #three)</td><td>true</td></tr><tr><td>accessor nextPut:<br>(WordLink for: #insert)</td><td>a WordLink for insert</td></tr><tr><td>accessor contents</td><td>LinkedList<br>(a WordLink for one<br>a WordLink for two<br>a WordLink for three<br>a WordLink for insert<br>a WordLink for five)</td></tr><tr><td>accessor next</td><td>a WordLink for five</td></tr><tr><td>accessor atEnd</td><td>true</td></tr></tbody></table>

Similarly, traversing the nodes of a tree structure, such as that of class Tree given in Chapter 11, can be done by a kind of Stream that maintains a reference to a current node and then accesses the next element by accessing the current node's left tree, root, or right tree. This kind of Stream is slightly more complicated to implement than that for a LinkedList because it is necessary to retain knowledge of whether the left or right tree has been traversed and back references to the *father* of the current node. The order of traversal of the tree structure can be implemented in the Stream, ignoring the method by which subtrees were added to the structure. Thus, although we used in-order traversal in the implementations of class Tree and class Node, we can stream over a Tree with postorder traversal by implementing the messages next and nextPut: appropriately.

## External Streams and File Streams

The Streams we have examined so far make the assumption that the elements of the collection can be any objects, independent of representation. For communicating with input/output devices, such as a disk, however, this assumption is not valid. In these cases, the elements are stored as binary, byte-sized elements that may prefer to be accessed as numbers, strings, words (two bytes), or bytes. Thus we have a need to support a mixture of nonhomogeneous accessing messages for reading and writing these different-sized "chunks" of information.

Class ExternalStream is a subclass of class ReadWriteStream. Its purpose is to add the nonhomogeneous accessing protocol. This includes protocol for positioning as well as accessing.
ExternalStream instance protocol

nonhomogeneous accessing

nextNumber: n
Answer the next n bytes of the collection accessed by the receiver as a positive Small-Integer or LargePositiveInteger.

nextNumber: n put: v
Store the argument, v, which is a positive SmallInteger or LargePositiveInteger, as the next n bytes of the collection accessed by the receiver. If necessary, pad with zeros.

nextString
Answer a String made up of the next elements of the collection accessed by the receiver.

nextStringPut: aString
Store the argument, aString, in the collection accessed by the receiver.

nextWord
Answer the next two bytes from the collection accessed by the receiver as an Integer.

nextWordPut: anInteger
Store the argument, anInteger, as the next two bytes of the collection accessed by the receiver.

nonhomogeneous positioning

padTo: bsize
Skip to the next boundary of bsize characters, and answer how many characters were skipped.

padTo: bsize put: aCharacter
Skip—writing the argument, aCharacter, into the collection accessed by the receiver in order to pad the collection—to the next boundary of bsize characters and answer how many characters were written (padded).

padToNextWord
Make the position reference even (on word boundary), answering the padding character, if any.

padToNextWordPut: aCharacter
Make the position reference even (on word boundary), writing the padding character, aCharacter, if necessary.

skipWords: nWords
Position after nWords number of words.

wordPosition
Answer the current position in words.

wordPosition: wp
Set the current position in words to be the argument, wp.

Class卧Stream is a subclass of ExternalStream. All accesses to external files are done using an instance of卧Stream. A卧Stream acts as though it were accessing a large sequence of bytes or characters; the elements of the sequence are assumed to be Integers or Characters. The protocol for a卧Stream is essentially that of class ExternalStream and its superclasses. In addition, protocol is provided to set and to test the status of the sequence the卧Stream is streaming over.

Classes ExternalStream and卧Stream are provided in the Smalltalk-80 system as the framework in which a file system can be created. Additional protocol in class卧Stream assumes that a file system is based on a framework consisting of a directory or dictionary of files, where a file is a sequence of file pages. The Smalltalk-80 system includes classes FileDirectory, File, and FilePage to represent these struc-
tural parts of a file system. A FilePage is a record of data that is
uniquely identified within its File by a page number. A File is uniquely
identified both by an alphanumeric name and a serial number; it main-
tains a reference to the FileDirectory which contains the File. And the
FileDirectory is itself uniquely identified by the device or "server" to
which it refers. User programs typically do not access a File or its
FilePages directly; rather they access it as a sequence of characters or
bytes through aindeStream. Thus the programmer can create a
FileStream as an accessor to a file using an expression of the form

Disk file: ' name.smalltalk '

where Disk is an instance of a FileDirectory. TheindeStream can then be
sent sequences of reading and writing messages as specified in the pro-
tocol of this chapter.
13

Implementation of the
Basic Collection Protocol

Class Collection

Subclasses of Collection

Class Bag

Class Set

Class Dictionary

SequenceableCollections

Subclasses of SequenceableCollection

Class MappedCollection

<figure><img src="image_121.png" /></figure>
The protocol for the classes in the Collection hierarchy was presented in Chapters 9 and 10. This chapter presents the complete implementation of class Collection and the implementation of the basic protocol for instance creation, accessing, testing, adding, removing, and enumerating for each subclass of Collection. These implementations make effective use of a framework in class Collection that is refined in its subclasses. Messages in Collection are implemented in a very general way or as self subclassResponsibility. Messages are implemented as

### self subclassResponsibility

if the method depends on the representation of the instances. Each subclass must override such messages to fulfill any "subclass responsibilities." Subclasses may override other messages, for efficiency purposes, with a new method that takes advantage of the representation. A subclass may implement some messages with

### self shouldNotImplement

which results in a report that the message should not be sent to instances of the class. For example, SequenceableCollections cannot respond to remove:ifAbsent; therefore the method is implemented as self shouldNotImplement.

## Class Collection

☐ Collection *instance creation protocol* In addition to the messages new and new;, an instance of a Collection can be created by sending any one of four messages made up of one, two, three, or four occurrences of the keyword with:. The messages new and new: are not reimplemented in Collection; they produce an instance that is an empty collection. Each of the other four instance creation methods is specified in Collection in a similar way. First an instance is created (with the expression self new) and then the arguments, in order, are added to the instance. The new instance is returned as the result. The instance is created using self new, rather than super new or self basicNew, because a subclass of Collection might reimplement the message new. Any subclass of Collection that represents fixed-size objects with indexed instance variables must reimplement the following instance creation messages since such a subclass cannot provide an implementation for new.
<table><tr><td>class name</td><td>Collection</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>class methods</td><td></td></tr></table>

## instance creation

### with: anObject

| newCollection |
newCollection ← self new.
newCollection add: anObject.
↑newCollection

### with: firstObject with: secondObject

| newCollection |
newCollection ← self new.
newCollection add: firstObject.
newCollection add: secondObject.
↑newCollection

### with: firstObject with: secondObject with: thirdObject

| newCollection |
newCollection ← self new.
newCollection add: firstObject.
newCollection add: secondObject.
newCollection add: thirdObject.
↑newCollection

### with: firstObject with: secondObject with: thirdObject

### with: fourthObject

| newCollection |
newCollection ← self new.
newCollection add: firstObject.
newCollection add: secondObject.
newCollection add: thirdObject.
newCollection add: fourthObject.
↑newCollection

The implementation of each of the instance creation messages depends on the ability of the newly-created instance to respond to the message add. Class Collection cannot provide implementations of the following messages because they depend on the representation used by a subclass:

add: anObject

remove: anObject ifAbsent: aBlock

do: aBlock

All other messages in the basic collection protocol are implemented in terms of these three messages. Each subclass must implement the three basic messages; each can then reimplement any others in order to improve its performance.
☐ Collection *adding protocol* The protocol for adding elements to a collection is implemented in class *Collection* as follows.

### adding

**add: anObject**

self subclassResponsibility

**all: aCollection**

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

taCollection

Notice that the implementation of `all:.` depends on both `do:` and `add:`. The order of adding elements from the argument, `aCollection`, depends on both the order in which the collection enumerates its elements (`do:`) and the manner in which the elements are included into this collection (`add:`).

☐ Collection *removing protocol* The messages `remove:` and `removeAll:` are implemented in terms of the basic message `remove:ifAbsent:`, which must be provided in a subclass. These methods report an error if the element to be removed is not in the collection. The method `remove:ifAbsent:` can be used to specify different exception behavior.

### removing

**remove: anObject ifAbsent: exceptionBlock**

self subclassResponsibility

**remove: anObject**

self remove: anObject ifAbsent: [self errorNotFoundError]

**removeAll: aCollection**

aCollection do: [ :each | self remove: each].

taCollection

### private

**errorNotFoundError**

self error: ' Object is not in the collection '

As usual, the category `private` refers to messages introduced to support the implementations of other messages; it is not to be used by other objects. Most error messages that are used more than once will be specified as private messages in order to create the literal message string once only.

☐ Collection *testing protocol* All the messages in the protocol for testing the status of a collection can be implemented in *Collection*.
testing

**empty**

↑self size = 0

**includes: anObject**

self do: [ :each | anObject = each ifTrue: [↑true]].

↑false

**occurrencesOf: anObject**

| tally |

tally ← 0.

self do: [ :each | anObject = each ifTrue: [tally ← tally + 1]].

↑tally

The implementations of includes: and occurrencesOf: depend on the subclass's implementation of the basic enumerating message do:. The block argument of do: in the method for includes: terminates as soon as an element equal to the argument is found. If no such element is found, the last expression (↑false) is evaluated. The response to empty and includes: are Boolean objects, true or false. The message size is inherited from class Object, but is reimplemented in Collection because size, as defined in Object, is only nonzero for variable-length objects.

accessing

**size**

| tally |

tally ← 0.

self do: [ :each | tally ← tally + 1].

↑tally

This is a low-performance approach to computing the size of a collection which, as we shall see, is reimplemented in most of the subclasses.

□ Collection *enumerating protocol* An implementation of all of the messages that enumerate the elements of collections, except do:, can be provided in class Collection.

enumerating

**do: aBlock**

self subclassResponsibility

**collect: aBlock**

| newCollection |

newCollection ← self species new.

self do: [ :each | newCollection add: (aBlock value: each)].

↑newCollection

**detect: aBlock**

↑self detect: aBlock ifNone: [self errorNotFound]
**detect: aBlock ifNone: exceptionBlock**

self do: [ :each | (aBlock value: each) ifTrue: [↑each]].

↑exceptionBlock value

**inject: thisValue into: binaryBlock**

| nextValue |

nextValue ← thisValue.

self do: [ :each | nextValue ← binaryBlock value: nextValue value: each].

↑nextValue

**reject: aBlock**

↑self select: [ :element | (aBlock value: element) == false]

**select: aBlock**

| newCollection |

newCollection ← self species new.

self do: [ :each | (aBlock value: each) ifTrue: [newCollection add: each]].

↑newCollection

In the methods associated with collect: and select:, the message species is sent to self. This message was not shown in Chapter 9 because it is not part of the external protocol of collections. It is categorized as private to indicate the intention for internal use only. The message is implemented in class Object as returning the class of the receiver.

private

**species**

↑self class

Thus the expression

self species new

means "create a new instance of the same class as that of the receiver."

For some collections, it may not be appropriate to create a "similar" instance in this way; a new collection that is like it may not be an instance of its class. Such a collection will override the message species. In particular, an Interval responds that its species is Array (because it is not possible to modify an Interval); the species of a MappedCollection is the species of the collection it maps (since the MappedCollection is simply acting as an accessor for that collection).

If a collection cannot create an instance by simply sending the class the message new, it must reimplement messages collect: and select:. Since reject: is implemented in terms of select:, it need not be reimplemented.

The method for inject:into: evaluates the block argument once for each element in the receiver. The block is also provided with its own value from each previous evaluation; the initial value is provided as the argument of inject:. The final value of the block is returned as the value of the inject:into: message.
The reason for the introduction of two messages, detect: and detect:ifNone:, is similar to the reason for the two removing messages, remove: and remove:ifAbsent:. The general case (detect:) reports an error if no element meeting the detection criterion is found; the programmer can avoid this error report by specifying an alternative exception (detect:ifNone:).

□ Collection *converting protocol* The protocol for converting from any collection into a Bag, Set, OrderedCollection, or SortedCollection is implemented in a straightforward way—create a new instance of the target collection, then add to it each element of the receiver. In most cases, the new instance is the same size as the original collection. In the case of OrderedCollections, elements are added at the end of the sequence (addLast:), regardless of the order of enumerating from the source.

converting

**asBag**

| aBag |
* aBag → Bag new.
self do: [ :each | aBag add: each].
↑aBag

**asOrderedCollection**

| anOrderedCollection |
* anOrderedCollection ← OrderedCollection new: self size.
self do: [ :each | anOrderedCollection addLast: each].
↑anOrderedCollection

**asSet**

| aSet |
* aSet ← Set new: self size.
self do: [ :each | aSet add: each].
↑aSet

**asSortedCollection**

| aSortedCollection |
* aSortedCollection ← SortedCollection new: self size.
aSortedCollection addAll: self.
↑aSortedCollection

**asSortedCollection: aBlock**

| aSortedCollection |
* aSortedCollection ← SortedCollection new: self size.
aSortedCollection sortBlock: aBlock.
aSortedCollection addAll: self.
↑aSortedCollection
□ Collection *printing protocol* The implementations of the printOn: and storeOn: messages in Object are overridden in Collection. Collections print in the form

`ClassName (element element element)`

Collections store themselves as an expression from which an equal collection can be constructed. This takes the form of

`((ClassName new))`

or

`((ClassName new) add: element; yourself)`

or

`((ClassName new) add: element; add: element; yourself)`

with the appropriate number of cascaded messages for adding each element, depending on whether the collection has no, one, or more elements. The message yourself returns the receiver of the message. It is used in cascaded messages to guarantee that the result of the cascaded message is the receiver. All objects respond to the message yourself; it is defined in class Object.

The general methods for printing and storing are

`printing`

**printOn: aStream**

| tooMany |
tooMany ← aStream position + self maxPrint.
aStream nextPutAll: self class name, '(.'
self do:
    [ :element |
        aStream position > tooMany
        ifTrue: [aStream nextPutAll: '...etc...]'. tself].
        element printOn: aStream.
        aStream space].
aStream nextPut: $)

**storeOn: aStream**

| noneYet |
aStream nextPutAll: '(('.
aStream nextPutAll: self class name.
aStream nextPutAll: 'new)'.
noneYet ← true.
self do:

[ :each |
noneYet
ifTrue: [noneYet ← false]
ifFalse: [aStream nextPut: $;].
aStream nextPutAll: 'add:'.
aStream store: each].
noneYet ifFalse: [aStream nextPutAll: ' ; yourself ].
aStream nextPut: $)

private

maxPrint

15000

These methods make use of instances of a kind of Stream that acts as
an accessor for a String. The method printOn: sets a threshold for the
length of the String to be created; a long collection may print as

ClassName (element element ...etc...)

The threshold is determined as the response to the message maxPrint
which is set at 5000 characters. Subclasses can override the private
message maxPrint in order to modify the threshold.

Note that this technique of using a method rather than a variable is
a way of providing a parameter in a method. A variable cannot be used
as the parameter because the variable, to be accessible to all instances,
would have to be a class variable. Subclasses cannot specify a class vari-
able whose name is the same as a class variable in one of its
superclasses; thus if a subclass wants to change the value of the vari-
able, it will do so for instances of its superclass as well. This is not the
desired effect.

The printing format is modified in several subclasses. Array does not
print its class name; Intervals print using the shorthand notation of the
messages to: and to:by: to a Number. A Symbol prints its characters
(without the # prefix of the literal form of a Symbol); a String prints its
characters delimited by single quotes.

The storeOn: message is reimplemented in ArrayedCollection and sev-
eral of its subclasses because instances are created using new: anInteger
rather than simply new. Arrays, Strings, and Symbols store in their lit-
eral forms. Intervals use the shorthand notation of messages to: and
to:by:. MappedCollections store using the converting message mappedBy:
that is sent to the collection that is indirectly accessed.

Subclasses of
Collection

For each subclass of Collection, we show the methods that implement
the three required messages (add:, remove:ifAbsent:, and do:) and the
messages in the adding, removing, testing, and enumerating protocols
that are reimplemented. New collection protocol for a particular subclass as specified in Chapter 9 will generally not be presented in this chapter.

## Class Bag

Bag represents an unordered collection in which an element can appear more than once. Since the elements of Bags are unordered, the messages at: and at:put: are reimplemented to report an error.

Instances of Bag have an instance of `Dictionary` as a single instance variable named `contents`. Each unique element of a Bag is the key of an `Association` in `contents`; the value of an `Association` is an `Integer` representing the number of times the element appears in the Bag. Removing an element decrements the tally; when the tally falls below 1, the `Association` is removed from `contents`. Bag implements `new`, `size`, `includes:`, and `occurrencesOf:`. A new instance must initialize its instance variable to be a `Dictionary`. The reimplementation of `size` is made efficient by summing all the values of elements of `contents`. The arguments of the testing messages are used as keys of `contents`. In implementing `includes:`, the responsibility for checking is passed to `contents`. In order to answer the query `occurrencesOf`: an `Object`, the method checks that an `Object` is included as a key in `contents` and then looks up the value (the tally) associated with it.

<table><tr><td>class name</td><td>Bag</td></tr><tr><td>superclass</td><td>Collection</td></tr><tr><td>instance variable names</td><td>contents</td></tr><tr><td>class methods</td><td></td></tr></table>

### instance creation

**new**

†super new setDictionary

### instance methods

### accessing

**at: index**

self errorNotKeyed

**at: index put: anObject**

self errorNotKeyed

**size**

| tally | .

tally ← 0

contents do: [ :each | tally ← tally + each].

↑tally

### testing

**includes: anObject**

↑contents includesKey: anObject
**occurrencesOf: anObject**

(self includes: anObject)

ifTrue: [↑contents at: anObject]

ifFalse: [↑0]

private

**setDictionary**

contents ← Dictionary new

(in Collection)

private

**errorNotKeyed**

self error:

self class name, 's do not respond to keyed accessing messages'

To add an element is to add it once, but Bags can add multiple times.
The implementation of add: calls on add:withOccurrences:. Removing an
element checks the number of occurrences, decrementing the tally or
removing the element as a key in contents if the tally is less than 1.

adding

**add: newObject**

↑self add: newObject withOccurrences: 1

**add: newObject withOccurrences: anInteger**

contents at: newObject

put: anInteger + (self occurrencesOf: newObject).

↑newObject

removing

**remove: oldObject ifAbsent: exceptionBlock**

| count |

count ← self occurrencesOf: oldObject.

count = 0 ifTrue: [↑exceptionBlock value].

count = 1

ifTrue: [contents removeKey: oldObject]

ifFalse: [contents at: oldObject put: count - 1]].

↑oldObject

Enumerating the elements of a Bag means selecting each element of
the Dictionary and evaluating a block with the key of that element (i.e.,
the actual Bag element is the key of the Dictionary). This has to be done
multiple times, once for each occurrence of the element, as indicated by
the value associated with the key.