Smalltalk80LanguageImplementationKor:Chapter 11

제 11 장 컬렉션 사용의 세 가지 예

컬렉션 사용의 세 가지 예

이번 장에서는 클래스 설명의 세 가지 예를 제시한다. 각 예는 Smalltalk-80에서 이용할 수 있는 숫자 및 컬렉션 객체를 사용하며, 기능을 시스템으로 추가하는 방법들을 각각 설명한다.

카드 게임은 카드 덱(deck)을 나타내는 컬렉션에서 무작위 선택을 이용해 생성 가능하다. Card 예제 클래스는 특정 세트와 등급이 있는 플레잉 카드를 나타낸다. CardDeck은 Cards와 같은 컬렉션을 표현하며, CardHand는 개별 플레이어에 대한 Cards의 컬렉션이다. CardDeck 또는 CardHand로부터 카드의 선택은 복원(replacement)을 이용한 표본 추출 SampleSpaceWithReplacement 와 복원이 없는 표본 추출 SampleSpaceWithoutReplacement를 나타내는 예제 클래스를 이용해 실행된다. 널리 사용되는 프로그래밍 문제인 술취한 바퀴벌레 문제는 바퀴벌레가 실내 모든 타일에 무작위로 순회하는 데에 필요한 모든 발자국 수를 세는 과정을 수반한다. 이번 장에 제시된 해답은 각 타일을 Tile이라는 예제 클래스의 인스턴스로 나타내고 DrunkenCockroach 의 인스턴스로서 버그로 나타낸다. 본 장에서 소개할 세 번째 예제는 Tree와 Node 클래스가 표현하는 트리형 데이터 구조체로, WordNode는 트리를 이용해 어떻게 단어를 표현하는 문자열을 저장하는지 설명한다.

무작위 선택과 플레잉 카드

0에서 1까지 무작위로 선택한 숫자의 생성기 역할을 하는 Smalltalk-80 클래스 Random을 제 8장에서 설명하였다. Random은 가능한 이벤트 집합에서 표본 추출하는 데에 기반을 제공하는데, 그러한 집합을 "sample space"(표본 공간)이라고 부른다. 단순한 형태의 이산적인 무작위 표본 추출은 시퀀스 가능한 컬렉션으로부터 요소를 선택하기 위해 무작위 숫자가 사용되는 경우에 얻을 수 있다. 선택된 요소가 컬렉션에 남아 있으면 "with replacement"(복원) 추출법이 이루어지는데, 컬렉션이 추출될 때마다 컬렉션의 모든 요소를 이용할 수 있다는 의미다. 추출된 요소는 컬렉션이 추출될 때마다 컬렉션에서 제거되는 경우를 "without replacement"(비복원) 추출법이라 부른다.

SampleSpaceWithReplacement 클래스는 시퀀스 가능한 항목의 컬렉션에서 복원할 수 있는 무작위 선택을 나타낸다. 클래스의 인스턴스는 무작위 추출법이 실행될 항목의 컬렉션을 명시하여 생성된다. 이러한 초기화 메시지에는 data: 선택자가 있다. 이후 next 메시지를 인스턴스로 전송함으로써 컬렉션으로부터 표본을 추출한다. 아니면 next: anInteger 메시지를 전송하여 표본의 anInteger 수만큼 얻을 수도 있다.

가령 사람들의 이름을 나타내는 Symbols의 Array에서 표본을 추출하길 원한다고 가정하자.

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

Array로부터 이름을 선택할 때마다 아래 표현식을 평가한다.

people next

이에 대한 응답은 sally, sam, sue, sarah, steve와 같은 Symbols 중 하나다.

people next: 5

5개 표본의 OrderedCollection이 선택된다. SampleSpaceWithReplacement의 인스턴스들은 표본 공간에 어떤 요소가 존재하는지와 얼마나 많은 요소가 존재하는지 검사하기 위해 isEmpty와 size 메시지에 응답한다. 따라서 아래에 대한 응답은

people isEmpty

false 가 되고, 아래에 대한 응답은

people size

5가 된다.

다음으로 SampleSpaceWithReplacement 클래스의 구현을 제시하겠다. 쌍따옴표로 분리된 주석은 각 메서드에 표시되어 목적을 나타낸다.

클래스명	SampleSpaceWithReplacement
슈퍼클래스	Object
인스턴스 변수명	data rand
클래스 메서드	instance creation data: aSequenceableCollection "Create an instance of SampleSpaceWithReplacement such that the argument, aSequenceableCollection, is the sample space." ↑self new setData: aSequenceableCollection
인스턴스 메서드	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

클래스 설명에서는 각 인스턴스가 data와 rand라는 이름의 두 변수를 가진다고 선언한다. 초기화 메시지 data: 은 data가 SequenceableCollection에 묶여 있고 (초기화 메시지의 인자 값) rand가 Random 메시지의 새 인스턴스로 묶여 있는 SetData: 메시지를 새로운 인스턴스로 전송한다.

SampleSpaceWithReplacement는 Collections가 응답할 수 있는 메시지로 구성된 작은 하위집합만 구현하므로 Collection의 서브클래스가 아니다. SampleSpaceWithReplacement로 전송된 next 와 size 메시지에 대한 응답으로 at: 과 size 메시지가 data 라는 인스턴스 변수로 전송된다. 즉, at: 과 size에 응답할 수 있는 컬렉션이라면 요소가 표본 추출되는 데이터 역할을 할 수 있다는 뜻이다. 모든 SequenceableCollections는 이 두 개의 메시지에 응답한다. 따라서 데이터는 앞서 설명한 Array 외에 Interval이 될 수도 있다. 주사위 던지기를 시뮬레이트한다고 가정하자. 표본 공간의 요소들은 1부터 6까지 양의 정수다.

die ← SampleSpaceWithReplacement data: (1 to: 6)

주사위 던지기는 아래를 평가하여 얻을 수 있다.

die next

위 메시지의 응답은 1, 2, 3, 4, 5, 6 중 하나의 Integer가 된다.

SampleSpaceWithReplacement의 인스턴스와 연관된 컬렉션이 카드 놀이를 나타내는 요소로 구성되어 있다면 카드 덱으로부터 위와 비슷한 방식으로 카드를 선택할 수 있다. 하지만 카드 게임을 하기 위해서는 플레이어에게 카드를 하나 나눠주고 카드 덱으로부터 그 카드를 제거할 수 있어야 한다. 따라서 복원 없이 무작위 선택을 사용해야 한다.

복원 없이 무작위 선택을 구현하려면 next 메시지에 대한 응답은 선택된 요소를 제거하는 것으로 정의한다. SequenceableCollections 는 모두 remove: 메시지에 응답하지 않으므로 (예: Interval은 응답하지 않는다) 초기화 메시지의 인자를 확인하거나 허용 가능한 컬렉션 유형의 인자를 확인해야 한다. 모든 OrderedCollections는 두 개의 메시지에 응답하고, 모든 컬렉션은 OrderedCollection으로 변환 가능하므로 변환 접근법을 이용할 수 있다. setData: 와 연관된 메서드는 이러한 목적을 달성하기 위해 그 인자에게 asOrderedCollection 메시지를 전송한다.

SampleSpaceWithoutReplacement 클래스는 SampleSpaceWithReplacement의 서브클래스가 되도록 정의된다. next 및 setData: 메시지와 연관된 메서드는 오버라이드되며, 나머지 메서드는 수정되지 않고 상속된다.

클래스명	SampleSpaceWithoutReplacement
슈퍼클래스	SampleSpaceWithReplacement
인스턴스 메서드	accessing next ↑data remove: super next private setData: aCollection data ← aCollection asOrderedCollection. rand ← Random new

next에 대한 메서드는 슈퍼클래스에 (super next) 구현된 메서드에 따라 좌우됨을 주목한다. 슈퍼클래스의 메서드는 표본 공간이 비어있지 않도록 확인한 후 요소를 무작위로 선택한다. 선택된 요소를 결정하고 나면 서브클래스의 메서드는 data로부터 요소를 제거한다. remove: 메시지의 결과는 인자이므로 SampleSpaceWithoutReplacement로 전송된 next 메시지의 경우 선택된 요소가 결과가 된다.

이제 간단한 카드 게임을 구현해보자. 카드 게임에 대한 표본 공간 데이터는 각 Card가 자신의 세트와 등급을 알고 있는 Card 클래스의 인스턴스에 해당한다. Card의 인스턴스는 세트(하트, 클럽, 스페이드 또는 다이아몬드)와 등급(1, 2, …, 13)을 두 인자로 명시하는 suit:rank: 메시지를 전송하여 생성된다. Card는 적절한 정보를 이용해 suit와 rank 메시지에 응답한다.

클래스명	Card
슈퍼클래스	Object
인스턴스 변수명	suit rank
클래스 메서드	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
인스턴스 메서드	accessing suit "Answer the receiver's suit." ↑suit rank "Answer the receiver's rank." ↑rank private setSuit: aSymbol rank: anInteger suit ← aSymbol. rank ← anInteger

카드 덱을 나타내는 cardDeck은 아래 표현식을 이용해 생성된다.

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

첫 번째 표현식은 52개 요소에 대해 OrderedCollection을 생성한다. 두 번째 표현식은 하트, 클럽, 스페이드, 다이아몬드로 된 한 세트마다 1부터 13까지 등급의 열거에 해당한다. OrderedCollection의 요소마다 세트와 등급이 다른 Card로 설정된다.

카드 덱에서 표본을 추출하는 기능은 그 카드 덱을 표본을 취할 컬렉션으로 두고 SampleSpaceWithoutReplacement의 인스턴스를 생성함으로써 얻는다.

cards ← SampleSpaceWithoutReplacement data: cardDeck

카드를 분배하기 위해서는 다음 표현식을 평가한다.

cards next

이 메시지에 대해 Card 클래스의 인스턴스가 응답된다.

CardDeck 클래스 예제의 설명에는 카드 덱을 제공하는 또 다른 방법이 제시되고 있다. 이는 카드의 선형 리스트를 저장하는 것을 기본 개념으로 하는데, next는 리스트에 첫 번째 카드를 제공함을 의미한다. 카드는 무작위 위치에 삽입하거나 끝에 위치시킴으로써 카드 덱으로 돌아올 수 있다. 선형 리스트는 “shuffling”(셔플링), 즉 무작위로 카드를 정렬하는 기능을 통해 무작위로 이루어진다.

다음 제시할 CardDeck 클래스의 구현에서 우리는 카드 덱의 초기 버전을 클래스 변수로서 저장한다. 이는 앞서 제공한 표현식을 이용해 생성된다. 이러한 변수의 복사본은 새로운 인스턴스가 생성될 때마다 인스턴스 변수로서 만들어지고, 카드를 나누기 전에 섞인다. 그 이후 카드를 섞을 때마다 클래스 변수가 아니라 인스턴스 변수의 현재 상태를 사용한다. 물론 섞는 과정은 SampleSpaceWithoutReplacement의 인스턴스 사용을 기반으로 하므로 꽤 획일적이다. 실제 셔플링의 시뮬레이션은 먼저 카드 덱을 대충 반으로 나누고 양쪽을 교차하여 배치한다. 교차 배치를 위해서는 양쪽에서 조금씩 카드를 선택해야 한다. 사실 이러한 시뮬레이션은 실제 사람이 섞는 것보다 더 무작위라고 볼 수 있는데 사람이 카드를 섞는 기술은 관찰 및 예측이 가능하기 때문이다.

CardDeck로 전송되는 return:, next, shuffle과 같은 메시지들은 카드 게임을 생성 시 유용하다.

클래스명	CardDeck
슈퍼클래스	Object
인스턴스 변수명	cards
클래스 변수명	InitialCardDeck
클래스 메서드	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
인스턴스 메서드	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

CardDeck 클래스는 아래의 표현식을 평가하여 초기화되어야 한다.

CardDeck initialize

CardDeck의 구현에서 cards는 인스턴스 변수이므로 게임을 할 때 사용되는 카드 덱이다. 게임을 하기 위해 CardDeck의 인스턴스가 생성되고,

CardDeck new

각 카드는 이렇게 새로운 인스턴스로 next 메시지가 전송되어 처리된다. 카드가 덱에 다시 놓이면 CardDeck으로 return: 메시지가 전송된다. 셔플링(shuffling)은 덱에 어떤 카드가 있든 항상 섞는다. 한 판을 완료한 후 전체 CardDeck이 다시 사용될 경우 덱에서 취한 카드는 모두 리턴되어야 한다.

shuffle 메시지의 구현을 주목한다. 현재 카드 덱의 복사본에 대해 비복원 표본 공간 sample이 생성된다. 이 표본 공간으로부터 무작위로 선택된 카드를 저장하기 위해 새로운 OrderedCollection인 tempDeck이 생성된다. 표본 추출은 가능한 카드마다 sample로부터 이루어지고, 선택된 카드마다 tempDeck으로 추가된다. 이용 가능한 모든 카드가 그곳에 섞이면 tempDeck은 현재 게임 덱으로서 저장된다.

4명의 플레이어와 한 명의 딜러가 있는 간단한 카드 게임을 생각해보자. 딜러는 각 플레이어에게 카드를 나눠준다. 최소 한 명의 플레이어가 18점에서 21점 사이의 점수를 내면 게임은 플레이어 각각에게 “prize”(포상)을 나눠주고 끝이 난다. 점수는 카드의 등급을 더하여 계산된다. 21점 이상을 얻은 플레이어에겐 새로운 카드를 돌리지 않는다.

각 플레이어는 카드 핸드(card hand)를 나타내는 CardHand 클래스의 인스턴스에 의해 표현된다. CardHand는 돌리는 카드를 알고, 총 점수를 결정할 수 있다 (points 메시지에 대한 응답).

클래스명	CardHand
슈퍼클래스	Object
인스턴스 변수명	cards
클래스 메서드	instance creation new ↑super new setCards
인스턴스 메서드	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

네 명의 플레이어로 된 Set을 생성한다. 각 플레이어는 CardHand의 인스턴스로 표현된다. 딜러의 카드는 gameCards이다. 딜러(즉, 프로그래머)는 덱 섞기부터 시작하며, 아직은 승자가 없다. 승자의 수는 한 명 이상이 될 수 있으며, 승자는 winners라는 Set에 열거된다.

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

승자가 없는 경우에 한해 21점 미만의 각 플레이어에게 gameCards로부터 또 다른 카드가 주어진다. 각 적격한 플레이어에게 카드를 나눠주기 전에 딜러는 각 플레이어의 점수를 검사하여 승자가 있는지 확인한다.

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

두 개의 표현식이 있는 블록은 게임을 계속하기 위한 조건이다. 첫 번째 표현식은 승자가 있을 경우 승자를 결정한다. 두 번째 표현식은 승자가 있는지 (winners isEmpty) 확인하고, 없을 경우 나눠주어야 할 카드가 있는지 (gameCards isEmpty not) 검사한다. 승자가 없고 더 이상 카드도 없다면 게임은 계속된다. 게임은 각 플레이어의 열거로 구성되므로 카드 점수가 21보다 작을 경우에만 (각 points < 21) 플레이어마다 다른 카드를 취한다 (each take: gameCards next).

다시 게임을 하려면 모든 카드가 게임 덱으로 돌아간 후 섞인다.

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

플레이어와 딜러는 다시 게임할 준비가 되었다.

술취한 바퀴벌레 문제

몇 가지 컬렉션 클래스를 이용해 널리 사용되는 프로그래밍 문제를 해결해볼 수 있겠다. 이 문제는 바로 술취한 바퀴벌레가 N개 타일의 너비와 M개 타일의 길이로 된 정사각형 타일 바닥에서 몇 개의 타일을 거쳤는지 측정하는 것이다. 문제를 약간만 수정하여 바퀴벌레가 “step”(한 발)을 움직인다고 가정하면 발을 디디기 전에 있던 타일과 그를 둘러싼 타일을 모두 합해 9개 타일 중에 어느 곳이든 동일한 확률로 이동할 수 있다. 물론 바퀴벌레가 벽 근처에 있다면 일부 타일로 이동할 확률은 제한된다. 따라서 바퀴벌레가 9개의 타일 모두에 한 번씩 발을 딛기까지 이동한 발자국 수를 세는 것으로 문제로 수정하였다.

이 문제를 해결하기 위해 사용할 간단한 알고리즘 하나는 빈 Set과 0으로 설정된 카운터로 시작된다. 한 발을 디딜 때마다 우리는 바퀴벌레가 이동한 타일을 Set으로 추가하고 발자국 수의 카운터를 증가시킨다. Set에선 어떤 중복도 허용되지 않으므로 Set의 요소 개수가 N*M에 도달하면 끝이 난다. 해답은 카운터의 값이 될 것이다.

이는 가장 간단한 문제 버전을 해결하지만 각 타일에 몇 번씩 방문했는지를 비롯해 추가 정보를 알고자 할 수도 있다. 이러한 정보를 기록하기 위해 Bag 클래스의 인스턴스를 사용한다. Bag의 크기는 바퀴벌레가 이동한 발자국 수로, Bag이 Set으로 변환될 때 Bag의 크기는 바퀴벌레가 건드린 각 타일의 총 개수가 된다. 이 수치가 N*M 에 도달하면 문제가 해결된다. Bag에서 각 타일의 발생 횟수는 바퀴벌레가 각 타일을 방문한 횟수와 동일하다.

바닥의 각 타일에 행과 열을 이용해 이름을 붙일 수 있다. 필자들이 제시한 해답에서 타일을 나타내는 객체들은 Tile 클래스의 인스턴스들이다. 주석을 포함한 Tile 클래스의 구현은 다음과 같다.

클래스명	Tile
슈퍼클래스	Object
인스턴스 변수명	location floorArea
인스턴스 메서드	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

Tile은 행과 열의 위치를 참조하는데 각 위치는 최소 1부터 시작해 바닥의 너비나 길이를 초과해선 안 된다. 따라서 Tile은 그 위치를 기억해야 할 뿐만 아니라 위치할 수 있는 바닥의 최대 공간도 기억해야 한다. Tile로는 neighborAt: aPoint 메시지를 전송하여 그 옆의 타일들 중 하나인 Tile을 결정한다. 이러한 새 Tile은 바닥의 경계 내 위치해야 한다.

바퀴벌레 발자국 시뮬레이션은 바퀴벌레가 있는 위치인 x-y 좌표에 일어나는 변화의 방향을 선택하는 방식으로 이루어진다. 바퀴벌레 위치가 주어지면 (타일 x,y) 타일이 모서리에 있지 않는 한 9개의 타일로 이동할 수 있다. x와 y에 일어날 수 있는 변화는 무작위 선정 데이터로 OrderedCollection에 저장할 것이다. OrderedCollection은 Points를 요소로 포함할 것인데, Points는 가능한 이동의 모든 조합을 나타내는 방향 벡터에 해당한다. 이러한 컬렉션은 아래와 같은 표현식으로 생성한다.

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

그리고 Directions는 아래의 요소가 있는 컬렉션이다.

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

술취한 바퀴벌레 시뮬레이션의 일부로, 가능한 이동에 대한 OrderedCollection으로부터 요소를 선택하기 위한 무작위 숫자를 생성할 것이다. 난수 발생기를 직접 사용하는 대신 앞의 예제의 Directions를 표본 공간으로 한 SampleSpaceWithReplacement를 사용해도 좋다.

바퀴벌레가 1@1 위치에 있는 Tile에서 시작한다고 가정하자. 바퀴벌레가 한 발을 디딜 때마다 우리는 Directions 컬렉션에서 요소 하나를 얻는다. 이 요소는 Tile로 전송되는 neighborAt: 메시지의 인자이다. 아래에서는 Rand가 Random 클래스의 인스턴스라고 가정하자.

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

결과가 되는 새로운 타일 위치는 바퀴벌레가 도착한 위치다.

모든 위치를 건드렸는지, 몇 발을 움직였는지 보고하기 위해서는 각 타일 위치를 기억해야 한다. 각 타일을 Bag으로 저장함으로써 바퀴벌레가 각 위치에 몇 번을 거치는지 횟수가 기록된다. 따라서 한 발을 움직일 때마다 이전 타일의 복사본인 새 타일이 생성된다. 이러한 새 타일은 무작위로 선택된 방향에 따라 변경되고 Bag으로 추가된다. Bag의 유일한 요소의 개수가 총 타일 개수와 동일하면 바퀴벌레는 할 일을 다한 것이다.

DrunkenCockroach 클래스에서는 두 개의 메시지만 필요로 한다. 하나는 바닥에 모든 타일을 건드릴 때까지 바닥에 특정 영역 주위로 바퀴벌레를 이동하도록 만드는 명령이다. 이는 walkWithin:startingAt: 메시지에 해당한다. 두 번째는 지금까지 바퀴벌레가 디딘 발자국의 횟수에 관한 질의로, numberOfSteps이다. DrunkenCockroach로 timesSteppedOn: 메시지를 전송하면 특정 타일에 바퀴벌레가 지나간 횟수를 문의할 수도 있다. 방향 벡터의 컬렉션(앞서 설명하였듯)은 DrunkenCockroach의 클래스 변수로서 생성되며, 난수 발생기 Ran 또한 DrunkenCockroach의 클래스 변수에 해당한다.

클래스명	DrunkenCockroach
슈퍼클래스	Object
인스턴스 변수명	currentTile tilesVisited
클래스 변수명	Directions Rand
클래스 메서드	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
인스턴스 메서드	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

이제 술취한 바퀴벌레 실험을 실행하도록 아래 메시지를 전송할 수 있다. 클래스를 초기화하고 인스턴스를 생성하라.

DrunkenCockroach initialize.
cockroach ← DrunkenCockroach new

5x5 공간으로 10개의 실험 결과를 얻어라.

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

10개 결과의 평균은 술취한 바퀴벌레에게 문제를 해결하도록 만드는 데에 필요한 평균 발자국 수를 나타낸다.

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

DrunkenCockroach 메시지 walkWithin:startingAt: 의 구현에서는 Bag이 Set으로 변환 시 N*M 요소를 갖게 되는지 여부가 종료 조건이라는 사실을 주목한다. 이 검사를 조금 더 빠르게 만드는 방법은 Bag 클래스에 uniqueElements 메시지를 추가하여 반복(iteration)을 통과할 때마다 Set으로의 변환이 이루어지는 일을 막는 것이다.

(이를 변경하고 싶은 독자를 위해 Bag 클래스로 추가되는 메서드를 아래 소개하겠다.

uniqueElements
    ↑contents size

이후 walkWithin:startingAt: 메시지를 변경하여 종료 조건이 tilesVisited uniqueElements < numberTiles가 되도록 만들 수 있다.)

이진트리(Binary Trees) 순회하기

트리는 중요한 비선형 데이터 구조체로, 컴퓨터 알고리즘에 유용하다. 트리 구조체는 요소들 간에 가지처럼 뻗어나가는 관계가 있음을 의미한다. 트리의 루트로 지정된 요소가 하나 있다. 하나의 요소만 존재한다면 이는 루트에 해당한다. 하나 이상의 요소가 있다면 몇 개의 (하위)트리로 나뉜다. 이진 트리는 하나의 이진 (하위)트리로 된 루트로만 구성되거나 두 개의 이진 (하위) 트리가 있는 루트로 구성된다. 트리 구조체의 계층도에 대한 전체적인 설명은 Knuth의 Art of Computer Programming의 제 1권을 참조한다. 본문에서는 독자가 어느 정도 지식을 겸비하고 있는 것으로 간주하므로 데이터 구조체를 Smalltalk-80 클래스로서 명시하는 방법을 설명하고자 한다.

LinkedList의 정의에 상응하는 방식으로 Tree 클래스를 정의할 것이다. Tree의 요소들은 Nodes로, LinkedList의 Links와 비교할 수 있으며, 다른 요소로 연결을 할 수 있다. Tree는 루트 노드만 참조할 것이다.

노드는 두 개의 인스턴스 변수가 있는 Smalltalk-80 객체를 표현하도록 단순하며, 인스턴스 변수 하나는 왼쪽 노드를, 다른 하나는 오른쪽 노드를 나타낸다. 노드의 순서는 “in-order traversal”(중위 순회)을 지원하도록 취급하기로 결정한다. 즉, 노드를 열거하면서 왼쪽 하위노드를 먼저 방문한 다음 루트, 그 다음 오른쪽 하위노드를 방문한다는 말이다. 노드에 하위노드가 없을 경우 “leaf”라고 부른다. 노드의 size는 1에 그 하위노드의 크기를 더한 값으로 정의한다. 따라서 leaf가 크기 1의 노드인 경우 두 개의 leaf를 가진 노드의 크기는 3이 될 것이다. 트리의 크기는 그 루트 노드의 크기다. size의 정의는 컬렉션에서 일반적인 크기 개념을 따른다.

Node로 전송되는 메시지는 왼쪽 노드, 오른쪽 노드, 마지막 또는 끝 노드로 접근을 제공한다. 또 하위노드(remove:ifAbsetn:)와 루트(rest)를 제거하는 것도 가능하다.

클래스명	Node
슈퍼클래스	Object
인스턴스 변수명	leftNode rightNode
클래스 메서드	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
인스턴스 메서드	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]

Node가 leaf일 경우 다음과 같이 표기된다.

열거는 중위(in-order) 순회를 사용하여 가장 먼저 왼쪽 하위노드를 블록의 값으로서 적용한 다음으로 루트, 그리고 오른쪽 하위노드로 진행된다.

다음으로 Nodes를 요소로 가진 SequenceableCollection 유형의 Tree를 제공하겠다. Tree에는 하나의 인스턴스 변수가 있으며 이를 root로 명명할 것인데, root의 값은 nil이거나 Node의 인스턴스로 되어 있다. SequenceableCollection의 서브클래스로서 Tree 클래스는 add: anElement, remove: anElement ifAbsent: exceptionBlock, do: aBlock 메시지를 구현한다. 기본적으로 이 메시지와 각각 연관된 메서드들은 트리가 비어 있는지 검사하고, 비어있지 않다면 root에 적절한 메시지를 전달한다. “empty”에 대한 검사는 Collection에서 상속된다. 이는 트리 구조체를 사용하는 프로그래머가 Tree 클래스의 인스턴스만 통해 해당 구조체의 요소로 접근하도록 만드는 데에 목적이 있다.

클래스명	Tree
슈퍼클래스	SequenceableCollection
인스턴스 변수명	root
인스턴스 메서드	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]

메시지를 제거한다고 해서 제거되어야 하는 노드부터 시작해 하위트리를 제거되는 것은 아니며 노드 자체만 제거함을 주목한다.

이진 워드 트리

Link의 정의와 마찬가지로 Node의 정의는 내용이 없이 전부 구조체에 해당한다. 각 Node의 내용은 서브클래스에서 명시하도록 두었다. Strings로 표현된 워드를 저장하도록 Node의 유형을 사용하길 원한다고 가정하자. 이를 WordNode 클래스라고 부른다. 어떤 하위노드도 명시되어 있지 않다면 WordNode의 인스턴스는 WordNode로 for: 메시지를 전송하여 생성되고, 두 개의 하위노드가 명시되어 있다면 for:left:right: 를 전송하면 생성된다. 따라서 아래와 같이 표현된 WordNode는

아래 표현식을 평가하여 생성된다.

WordNode for: 'cat'

아래와 같은 모습의 WordNode는

아래의 표현식을 평가하여 생성된다.

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

WordNode 클래스에 대한 구현이 따라온다. Nodes에서 워드는 동일함을 나타내기 위해 상등성(=)이 재정의됨을 주목하는데, 즉 워드가 인자의 워드와 동일할 경우 상속된 제거 메시지들은 하위노드를 제거할 것이란 의미다.

클래스명	WordNode
슈퍼클래스	Node
인스턴스 변수명	word
클래스 메서드	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
인스턴스 메서드	accessing word ↑word word: aString word ← aString comparing = aWordNode ↑(aWordNode isKindOf: WordNode) and: [word = aWordNode word] hash ↑word hash

WordNode의 사용을 설명하기 위해 표현식의 시퀀스가 잇따라 제시된다. 트리를 순회할 때 각 단어가 알파벳순으로 수집되는 요소의 삽입을 지원하기 위해 WordNode의 정의를 별도로 수정하지 않았음을 주목한다. 관심이 있다면 알파벳 정렬을 유지하는 insert: aWordNode 메시지를 WordNode로 추가하는 것도 가능하다.

tree ← Tree new.

tree add: (WordNode for: 'cat')

tree addFirst: (WordNode for: 'frog')

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

tree addFirst: (WordNode for: 'ape')

tree remove: (WordNode for: 'horse')

tree remove: (WordNode for: 'frog')