Smalltalk80LanguageImplementation:Chapter 11: Difference between revisions

From 흡혈양파의 번역工房
Jump to navigation Jump to search
(SMALLTALK80 Chapter 11 Three Examples that Use Collections 페이지 추가)
 
(정오표 수정)
 
Line 155: Line 155:




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




Line 223: Line 223:




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




Line 359: Line 359:




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


<syntaxhighlight lang="smalltalk">
<syntaxhighlight lang="smalltalk">
Line 371: Line 371:




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




Line 394: Line 394:




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




Line 442: Line 442:




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




Line 493: Line 493:
class initialization
class initialization
     initialize
     initialize
         "Create the collection of direction vectors and the raondom number generator."
         "Create the collection of direction vectors and the random number generator."
         Directions ← OrderedCollection new: 9.
         Directions ← OrderedCollection new: 9.
         (-1 to: 1) do: [ :x | (-1 to: 1) do: [ :y | Directions add: x@y]].
         (-1 to: 1) do: [ :x | (-1 to: 1) do: [ :y | Directions add: x@y]].
Line 593: Line 593:
|<syntaxhighlight lang="smalltalk">
|<syntaxhighlight lang="smalltalk">
instance creation
instance creation
     left: INode right: rNode
     left: lNode right: rNode
         "Create an instance of a Node with the arguments INode and rNode as the left and right subnodes, respectively."
         "Create an instance of a Node with the arguments lNode and rNode as the left and right subnodes, respectively."
         | newNode|
         | newNode|
         newNode ← self new.
         newNode ← self new.
         newNode left: INode.
         newNode left: lNode.
         newNode right: rNode.
         newNode right: rNode.
         ↑newNode
         ↑newNode
Line 744: Line 744:
===A Binary Word Tree===
===A Binary Word Tree===


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


[[image:Smalltalk80LanguageImplementation_11-2.png|그림 11-2]]
[[image:Smalltalk80LanguageImplementation_11-2.png|그림 11-2]]
Line 785: Line 785:
     for: aString
     for: aString
         ↑self new word: aString
         ↑self new word: aString
     for: aString left: INode right: rNode
     for: aString left: lNode right: rNode
         | newNode |
         | newNode |
         newNode ← super left: INode right: rNode.
         newNode ← super left: lNode right: rNode.
         newNode word: aString.
         newNode word: aString.
         ↑newnode
         ↑newNode
</syntaxhighlight>
</syntaxhighlight>
|- style="vertical-align:top;"
|- style="vertical-align:top;"

Latest revision as of 09:20, 9 May 2014

Chapter 11 Three Examples that Use Collections

Three Examples that Use Collections

Three examples of class descriptions are given in this chapter. Each example makes use of the numeric and collections objects available in the Smalltalk-80 system; each illustrates a different way to add functionality to the system.


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


Random Selection and Playing Cards

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


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


For example, suppose we wish to sample from an Array of Symbols representing the names of people.

people  SampleSpaceWithReplacement
    data: #(sally sam sue sarah steve)


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

people next


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

people next: 5


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

people isEmpty


is false; and the response to

people size


is 5.


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

class name SampleSpaceWithReplacement
superclass Object
instance variable names data
rand
class methods
instance creation
    data: aSequenceableCollection
        "Create an instance of SampleSpaceWithReplacement such that the argument, aSequenceableCollection, is the sample space."
        self new setData: aSequenceableCollection
instance methods
accessing
    next
        "The next element selected is chosen at random from the data collection. The index into the data collection is determined by obtaining a random number between 0 and 1, and normalizing it to be within the range of the size of the data collection."
        self isEmpty
            ifTrue: [self error: 'no values exist in the sample space'].
        data at: (rand next * data size) truncated + 1
    next: anInteger
        "Answer an OrderedCollection containing anInteger number of selections from the data collection."
        | aCollection |
        aCollection  OrderedCollection new: anInteger.
        anInteger timesRepeat: [aCollection addLast: self next].
        aCollection

testing
    isEmpty
        "Answer whether any items remain to be sampled."
        self size = 0
    size
        "Answer the number of items remaining to be sampled."
        data size

private
    setData: aSequenceableCollection
        "The argument, aSequenceableCollection, is the sample space, Create a random number generator for sampling from the space."
        data  aSequenceableCollection.
        rand  Random new


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


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

die  SampleSpaceWithReplacement data: (1 to: 6)


A throw of the die is obtained by evaluating

die next


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


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


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


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

class name SampleSpaceWithoutReplacement
superclass SampleSpaceWithReplacement
instance methods
accessing
    next
        data remove: super next

private
    setData: aCollection
        data  aCollection asOrderedCollection.
        rand  Random new


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


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

class name Card
superclass Object
instance variable names suit
rank
class methods
instance creation
    suit: aSymbol rank: anInteger
        "Create an instance of Card whose suit is the argument, aSymbol, and whose rank is the argument, anInteger."
        self new setSuit: aSymbol rank: anInteger
instance methods
accessing
    suit
        "Answer the receiver's suit."
        suit
    rank
        "Answer the receiver's rank."
        rank
private
    setSuit: aSymbol rank: anInteger
        suit  aSymbol.
        rank  anInteger


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

cardDeck  OrderedCollection new: 52.
#(heart club spade diamond) do:
    [ :eachSuit |
        1 to: 13 do: [ :n | cardDeck add: (Card suit: eachSuit rank: n)]]


The first expression creates an OrderedCollection for 52 elements. The second expression is an enumeration of the ranks 1 through 13 for each of the four suits: heart, club, spade, and diamond. Each element of the OrderedCollection is set to be a Card with a different suit and rank.


The ability to sample from this deck of cards is obtained by creating an instance of SampleSpaceWithoutReplacement with the card deck as the collection from which samples will be taken

cards  SampleSpaceWithoutReplacement data: cardDeck


To deal a card, evaluate the expression

cards next


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


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


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


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

class name CardDeck
superclass Object
instance variable names cards
class variable names InitialCardDeck
class methods
class initialization
    initialize
        "Create a deck of 52 playing cards."
        InitialCardDeck  OrderedCollection new: 52.
        #(heart club spade diamond) do:
            [ :aSuit |
                1 to: 13
                    do: [ :n | InitialCardDeck add: (Card suit: aSuit rank: n)]]

instance creation
    new
        "Create an instance of CardDeck with an initial deck of 52 playing cards."
        super new cards: InitialCardDeck copy
instance methods
accessing
    next
        "Deal (give out) the next card."
        cards removeFirst
    return: aCard
        "Put the argument, aCard, at the bottom of the deck."
        cards addLast: aCard
    shuffle
        | sample tempDeck |
        sample  SampleSpaceWithoutReplacement data: cards.
        tempDeck  OrderedCollection new: cards size.
        cards size timesRepeat: [tempDeck addLast: sample next].
        self cards: tempDeck

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

private
    cards: aCollection
        cards  aCollection


The class CardDeck must be initialized by evaluating the expression

CardDeck initialize


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

CardDeck new


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


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


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


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

class name CardHand
superclass Object
instance variable names cards
class methods
instance creation
    new
        super new setCards
instance methods
accessing
    take: aCard
        "The argument, aCard, is added to the reciever."
        cards add: aCard
    returnAllCardsTo: cardDeck
        "Place all of the receiver's cards into the deck of cards referred to by the argument, cardDeck, and remove these cards from the receiver's hand."
    cards do: [ :eachCard | cardDeck return: eachCard].
    self setCards

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

private
    setCards
        cards  OrderedCollection new


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

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


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

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


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


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

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


The players and dealer are ready to play again.


The Drunken Cockroach Problem

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


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


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


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

class name Tile
superclass Object
instance variable names location
floorArea
instance methods
accessing
    location
        "Answer the location of the receiver on the floor."
        location
    location: aPoint
        "Answer the location of the receiver on the floor."
        location
    location: aPoint
        "Set the receiver's location on the floor to be the argument, aPoint."
        location  aPoint
    floorArea: aRectangle
        "Set the floor area to be the rectangular area represented by the argument, aRectangle."
        floorArea  aRectangle

moving
    neighborAt: deltaPoint
        "Create and answer a new Tile that is at the location of the receiver changed by the x and y amounts represented by the argument, deltaPoint. Keep the location of the newTile within the boundries of the floor area."
        | newTile |
        newTile  Tile new floorArea: floorArea.
        newTile location: ((location + deltaPoint max: floorArea origin)
            min: floorArea corner).
        newTile

comparing
    = aTile
        "Answer whether the receiver is equal to the argument, aTile."
        (aTile isKindOf: Tile) and: [location = aTile location]
    hash
        location hash


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


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

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


Directions, then, is a collection with elements

-1@-1, -1@0, -1@1, 0@-1, 0@0, 0@1, 1@-1, 1@0, 1@1


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


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

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


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


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


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

class name DrunkenCockroach
superclass Object
instance variable names currentTile
tilesVisited
class variable names Directions
Rand
class methods
class initialization
    initialize
        "Create the collection of direction vectors and the random number generator."
        Directions  OrderedCollection new: 9.
        (-1 to: 1) do: [ :x | (-1 to: 1) do: [ :y | Directions add: x@y]].
        Rand  Random new
instance creation
    new
        super new setVariables
instance methods
simulation
    walkWithin: aRectangle startingAt: aPoint
        | numberTiles |
        tilesVisited  Bag new.
        currentTile location: aPoint.
        currentTile floorArea: aRectangle.
        numberTiles  (aRectangle width + 1) * (aRectangle height + 1).
        tilesVisited add: currentTile.
        [tilesVisited asSet size < numberTiles] whileTrue:
            [currentTile  currentTile neighborAt:
                (Directions at: (Rand next * Directions size) truncated + 1).
            tilesVisited add: currentTile]
data
    numberOfSteps
        tilesVisited size
    timesSteppedOn: aTile
        tilesVisited occurrencesOf: aTile
private
    setVariables
        currentTile  Tile new.
        tilesVisited  Bag new


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

DrunkenCockroach initialize.
cockroach  DrunkenCockroach new


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

results  OrderedCollection new: 10.
10 timesRepeat:
    [cockroach walkWithin: (1 @ 1 cornet: 5 @ 5) startingAt: (1 @ 1).
    results add: cockroach numberOfSteps]


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

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


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


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

uniqueElements
    contents size


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


Traversing Binary Trees

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


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


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


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

class name Node
superclass Object
instance variable names leftNode
rightNode
class methods
instance creation
    left: lNode right: rNode
        "Create an instance of a Node with the arguments lNode and rNode as the left and right subnodes, respectively."
        | newNode|
        newNode  self new.
        newNode left: lNode.
        newNode right: rNode.
        newNode
instance methods
testing
    isLeaf
        "Answer whether the receiver is a leaf, that is, whether it is a node without any subnodes."
        leftNode isNil & rightNode isNil

accessing
    left
        leftNode
    left: aNode
        leftNode  aNode
    right
        rightNode
    right: aNode
        rightNode  aNode
    size
        1 + (leftNode isNil
                ifTrue: [0]
                ifFalse: [leftNode size])
            + (rightNode isNil
                ifTrue: [0]
                ifFalse: [rightNode size])
    end
        | aNode |
        aNode  self.
        [aNode right isNil] whileFalse: [aNode  aNode right].
        aNode

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

enumerating
    do: aBlock
        leftNode isNil ifFalse: [leftNode do: aBlock]. 
        aBlock value: self.
        rightNode isNil ifFalse: [rightNode do: aBlock]


그림 11-1


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


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

class name Tree
superclass SequenceableCollection
instance variable names root
instance methods
testing
    isEmpty
        root isNil

accessing
    first
        | save |
        self emptyCheck.
        save  root.
        [save left isNil] whileFalse: [save  save left].
        save
    last
        self emptyCheck.
        root end
    size
        self isEmpty
            ifTrue: [0]
            ifFalse: [root size]

adding
    add: aNode
        self addLast: aNode
    addFirst: aNode
        "If the collection is empty, then the argument, aNode, is the new root; otherwise, it is the left node of the current first node."
        self isEmpty
            ifTure: [root  aNode]
            ifFalse: [self first left: aNode].
        aNode
    addLast: aNode
        "If the collection is empty, then the argument, aNode, is the new root; otherwise it is the last element of the current root."
        self isEmpty
            ifTrue: [root  aNode]
            ifFalse: [self last right: aNode].
        aNode

removing
    remove: aNode ifAbsent: exceptionBlock
        "First check the root. If not found, move down the tree checking each node."
        self isEmpty ifTrue: [exceptionBlock value].
        root = aNode
            ifTrue: [root  root rest. aNode]
            ifFalse: [root remove: aNode ifAbsent: exceptionBlock]
    removeFirst
        self emptyCheck.
        self remove: self first ifAbsent: []
    removeLast
        self emptyCheck.
        self remove: self last ifAbsent: []

enumerating
    do: aBlock
        self isEmpty ifFalse: [root do: aBlock]


Note that the removing messages do not remove the subtree beginning with the node to be removed, only the node itself.


A Binary Word Tree

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

그림 11-2


is created by evaluating the expression

WordNode for: 'cat'


A WordNode that looks like

그림 11-3


is created by evaluating the expression

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


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

class name WordNode
superclass Node
instance variable names word
class methods
instance creation
    for: aString
        self new word: aString
    for: aString left: lNode right: rNode
        | newNode |
        newNode  super left: lNode right: rNode.
        newNode word: aString.
        newNode
instance methods
accessing
    word
        word
    word: aString
        word  aString
comparing
    = aWordNode
        (aWordNode isKindOf: WordNode) and: [word = aWordNode word]
    hash
        word hash


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

tree  Tree new.

tree add: (WordNode for: 'cat')

그림 11-4


tree addFirst: (WordNode for: 'frog')

그림 11-5


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

그림 11-6


tree addFirst: (WordNode for: 'ape')

그림 11-7


tree remove: (WordNode for: 'horse')

그림 11-8


tree remove: (WordNode for: 'frog')

그림 11-9


Notes