Smalltalk80LanguageImplementation:Chapter 09
- Chapter 9 Protocol for All Collection Classes
Protocol for All Collection Classes
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
IdentifyDictionary
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.
| adding | |
| add: newObject | Include the argument, newObject, as one of the receiver's elements. Answer newObject. |
| addAll: 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. |
| Collection instance protocol | |
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
| expression | result | lotteryA if it changed |
| lotteryA isEmpty | false | |
| lotteryA includes: 572 | true | |
| lotteryA add: 596 | 596 | Bag (272 572 852 156 596) |
| lotteryA addAll: lotteryB | Bag(572 621 274) | Bag (272 274 852 156 596 572 572 621) |
| lotteryA occurrencesOf: 572 | 2 | |
| lotteryA remove: 572 | 572 | Bag(272 274 852 156 596 572 621) |
| lotteryA size | 7 | |
| lotteryA removeAll: lotteryB | Bag(572 621 274) | Bag(272 852 596 156) |
| lotteryA size | 4 |
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.
| 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. |
| Collection instance protocol | |
Each enumeration message provides a concise way to express a sequence of messages for testing or gathering information about the elements of a collection.
Selecting and Rejecting
We could have determined the number of occurrences of the character a or A using the message select:.
(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 subTotal.
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.
| instance creation | |
| with: anObject | Answer an instance of the collection containing anObject. |
| 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. |
| Collection class protocol | |
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.
| 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). |
| asSortedCollection | Answer a SortedCollection whose elements are those of the receiver, sorted so that each element is less than or equal to(< =) its successors. |
| asSortedCollection: aBlock | Answer a SortedCollection whose elements are those of the receiver, sorted according to the argument aBlock. |
| Collection instance protocol | |
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