- Chapter 10 Hierarchy of the Collection Classes
- 1 Hierarchy of the Collection Classes
- 2 Class Bag
- 3 Class Set
- 4 Classes Dictionary and IdentityDictionary
- 5 Class SequenceableCollection
- 6 SubClasses of SequenceableCollection
- 7 Class ArrayedCollection
- 8 Class Symbol
- 9 Class MappedCollection
- 10 Summary of Conversions Among Collections
- 11 Notes
Hierarchy of the 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
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 sequencefor 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 kink. 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 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.
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.
|add: newObject withOccurrences: anInteger||Include the argument, newObject, as an element of the receiver, anInteger number of times. Answer the argument, newObject.|
|Bag instance protocol|
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) with Occurrences: 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]
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 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:mare 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.
|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).|
|Dictionary instance protocol|
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
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.
|opposites includes: #cold||true|
|opposites includes: #hot||false|
|opposites occurrencesOf: #go||2|
|opposites at: #stop put: #start||start|
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.
|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.|
|Dictionary instance protocol|
Then we can try
|opposites includesAssociation:(Association key: #come value: #go)||true|
|opposites includesKey: #hot||true|
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.
|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.|
|Dictionary instance protocol|
|opposites removeAssociation: (Association key: #top value: #bottom)||The association whose key is #top and value is #bottom. opposites has one less element.|
|opposites removeKey: #hot||The association whose key is #hot and whose value is #cold. This association is removed from opposites.|
|opposites removeKey: #cold ifAbsent: [opposites at: #cold put: #hot]||hot|
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.
|associationsDo: aBlock||Evaluate aBlock for each of the receiver's key/value associations.|
|keysDo: aBlock||Evaluate aBlock for each of the receiver's keys.|
|Dictionary instance protocol|
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
returns the Set whose elements are
push come front stop cold
returns the Bag whose elements are
pull go back start hot
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:).
|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||AAnswer 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||AAnswer the first index of the argument, anElement, within the receiver. If the receiver does not contain anElement, answer 0.|
|indexOf: anElement ifAbsent: exception Block||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 ifAbsetnt: 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.|
|SequenceableCollection instance protocol|
Examples of using these accessing messages, using instances of String, are
|'aaaaaaaaaa' atAll: (2 to: 10 by: 2) put: $b||'ababababab'|
|'aaaaaaaaaa' atAllPut: $b||'bbbbbbbbbb'|
|'This string' first||$T|
|'This string' last||$g|
|'ABCDEFGHIJKLMNOP' indexOf: $F||6|
|'ABCDEFGHIJKLMNOP' indexof: $M ifAbsent: ||13|
|'ABCDEFGHIJKLMNOP' indexOf: $Z ifAbsent: ||0|
|'The cow jumped' indexOfSubCollection: 'cow' startingAt: 1||5|
|'The cow jumped' replaceFrom: 5 to: 7 with: 'dog'||'The dog jumped'|
|'The cow jumped' replaceFrom: 5 to: 7 with: 'the spoon ran' startingAt: 5||'The spo jumped'|
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.
|, aSequenceableCollection||This is the concatenation operation. Answer a copy of the receiver with each element of the argument, aSequenceableCollection, added, in order.|
|copyFrom: start to: stop||Answer a copy of a subset of the receiver, starting from element at index start until element at index stop.|
|copyReplaceAll: oldSubCollection with: newSubCollection||Answer a copy of the receiver in which all occurrences of oldSubCollection have been replaced by newSubCollection.|
|copyReplaceFrom: start to: stop with: replacementCollection||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.|
|copyWith: newElement||Answer a copy of the receiver that is 1 bigger than the receiver and has newElement as the last element.|
|copyWithout: oldElement||Answer a copy of the receiver in which all occurrences of oldElement have been left out.|
|SequenceableCollection instance protocol|
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
|line ← line copyReplaceFrom: 1 to: 0 with: 'this is the first line tril'||'this is the first line tril'|
|line ← line copyReplaceAll: 'tril' with: 'trial'||'this is the first line trial'|
|line ← line copyReplaceFrom: (line size + 1) to: (line size) with: 'and so on'||this is the first line trial and so on'|
|line indexOfSubCollection: 'trial' startingAt: 1||24|
|line ← line copyReplaceFrom: 29 to: 28 with: ' '||'this is the first line trial and so on'|
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
|#(one two three) copyWith: #four||(one two three four)|
|#(one two three) copyWithout: #two||(one three)|
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.
|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.|
|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.|
|SequenceableCollection instance protocol|
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 list (called either the "rear" or the "front") of the list. It is often called a last-in first-out queue.
|usual vocabulary||OrderedCollection message|
|push newObject||addLast: newObject|
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.
|usual vocabulary||OrderedCollection message|
|add newObject||addLast: newObject|
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.
|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.|
|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.|
|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.|
|addAllFirst: anOrderedCollection||Add each element of the argument, anOrderedCollection, at the beginning of the receiver. Answer anOrderedCollection.|
|addAllLast: 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.|
|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.|
|OrderedCollection instance protocol|
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.
|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|
|sortBlock||Answer the block that is the criterion for sorting elements of the receiver.|
|sortBlock: aBlock||Make the argument, aBlock, be the criterion for ordering elements of the receiver.|
|SortedCollection class protocol|
Suppose we with to maintain an alphabetical list of the names of children in a classroom.
children ← s=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 > =.
|children add: #Joe||Joe|
|children add: #Bill||Bill|
|children add: #Alice||Alice|
|children||SortedCollection(Alice Bill Joe)|
|children add: #Sam||Sam|
|a < b ]||SortedCollection(Sam Joe Bill Alice)|
|children add: #Henrietta||Henrietta|
|children||SortedCollection(Sam Joe Henrietta Bill Alice)|
The sixth message in the example reversed the order in which elements are stored in the collection, children.
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.
|nextLink: aLink||Create an instance of Link that references the argument, aLink.|
|LinkedList class protocol|
|nextLink||Answer the receiver's reference.|
|nextLink: aLink||Set the receiver's reference to be the argument, aLink.|
|LinkedList instance protocol|
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
|addFirst: aLink||Add aLink to the beginning of the receiver's list. Answer aLink.|
|addLast: aLink||Add aLink to the end of the receiver's list. Answer aLink.|
|removeFirst||Remove the receiver's first element and answer it. If the receiver is empty, report an error.|
|removeLast||Remove the receiver's last element and answer it. If the receiver is empty, report an error.|
|LinkedList instance protocol|
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.
|instance variable names||element|
instance creation for: anObject ↑self new setElement: anObject
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.
|link ← LinkedList new||LinkedList ()|
|list add: (Entry for: 2)||Entry for: 2|
|list add: (Entry for: 4)||Entry for: 4|
|list addLast: (Entry for: 5)||Entry for: 5|
|list addFirst: (Entry for: 1)||Entry for: 1|
|list||LinkedList (Entry for: 1 Entry for: 2 Entry for: 4 Entry for: 5)|
|(each element) + value ]||12|
|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|
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.
|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.|
|Interval class protocol|
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
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
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
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.
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. 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 ByteArray represents an ArrayedCollection whose elements are integers between 0 and 255. The implementation of a ByteArray stores two bytes to a 16-bit word; the class supports additional protocol for word and double-word access. ByteArrays are used in the Smalltalk-80 system for storing time in milliseconds.
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.
|< 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.|
|String instance protocol|
We have not as yet given examples of using the last two messages.
|'first string' sameAs: 'first string'||true|
|'First String' sameAs: 'first string'||true|
|'First String' = 'first string'||false|
|'#irst string' match: 'first string'||true|
|'*string' match: 'any string'||true|
|'*.st' match: 'filename.st'||true|
|'first string' match: 'first *'||false|
Strings can be converted to all lowercase characters or all uppercase characters. They can also be converted to instances of class Symbol.
|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.|
|String instance protocol|
Therefore we have
|'first string' asUppercase||'FIRST STRING'|
|'First String' asLowercase||'first string'|
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.
|intern: aString||Answer a unique Symbol whose characters are those of aString.|
|internCharacter: aCharacter||Answer a unique Symbol of one character, the argument, aCharacter.|
|Symbol class protocol|
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 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.
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.
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.
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
|words at: #scalding||cold|
|words at: #cease||start|
|words at: #cease put: #continue||continue|
|opposites at: #stop||continue|
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 a LinkedList.