Smalltalk80LanguageImplementation:Chapter 10

From 흡혈양파의 번역工房
Jump to: navigation, search
Chapter 10 Hierarchy of the Collection Classes

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.

그림 10-1


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.


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.

adding
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]


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

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

key value
hot cold
push pull
stop go
come go
front back
top bottom


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.

expression result
opposites size 6
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.

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.
Dictionary instance protocol


Then we can try

expression result
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.

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.
Dictionary instance protocol


For example

expression result
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.

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

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 SequenceableCollection

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:).

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

expression result
'aaaaaaaaaa' size 10
'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: [0] 13
'ABCDEFGHIJKLMNOP' indexOf: $Z ifAbsent: [0] 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.

copying
, 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


Then

expression result
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

expression result
#(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.

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

Class OrderedCollection

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
pop removeLast
top last
empty isEmpty


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
delete removeFirst
front first
empty isEmpty


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.

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.
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.
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.
OrderedCollection instance protocol


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.

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

expression result
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.


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.

instance creation
nextLink: aLink Create an instance of Link that references the argument, aLink.
LinkedList class protocol


accessing
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

adding
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.
removing
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.

class name Entry
superclass Link
instance variable names element
class methods
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.

expression result
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)
list isEmpty false
list size 4
(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


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.

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


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


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.

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.
String instance protocol


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

expression result
'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.

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.
String instance protocol


Therefore we have

expression result
'first string' asUppercase 'FIRST STRING'
'First String' asLowercase 'first string'
'First' asSymbol First


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.

instance creation
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

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.

key value
come go
cold hot
front back
hot cold
push pull
stop start


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.

key value
cease stop
enter come
scalding hot
shove push


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

expression result
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.


Notes