Smalltalk80LanguageImplementationKor:Chapter 13
- 제 13 장 기본 컬렉션 프로토콜의 구현
기본 컬렉션 프로토콜의 구현
Collection 계층구조에서 클래스에 대한 프로토콜은 제 9장과 10장에서 소개하였다. 이번 장에서는 Collection 클래스의 완전한 구현과 Collection의 서브클래스마다 인스턴스 생성, 접근, 검사, 추가, 제거, 열거와 관련된 기본 프로토콜의 구현을 나타내고자 한다. 이러한 구현은 Collection 클래스에서 프레임워크의 사용을 효과적으로 하며, 그 서브클래스에서 개선된다. Collection 내 메시지는 매우 일반적인 방식으로 구현되거나 self subclassResponsibility로서 구현된다.
self subclassResponsibility
메서드가 인스턴스의 표현에 의존할 경우 메시지는 위와 같이 구현된다. 각 서브클래스는 "subclass responsibilities"(서브클래스 책임)을 수행하기 위해 그러한 메시지를 오버라이드해야 한다. 서브클래스는 효율성을 목적으로 표현을 활용하는 새로운 메서드를 이용해 다른 메시지를 오버라이드할 수도 있다. 서브클래스는 아래를 이용해 일부 메시지를 구현하기도 하는데,
self shouldNotImplement
그럴 경우 메시지가 클래스의 인스턴스로 전송되어선 안 된다는 보고가 발생한다. 예를 들어, SequenceableCollections는 remove:if:Absent: 로 응답할 수 없으므로 메서드는 self shouldNotImplement로서 구현된다.
Collection 클래스
❏ Collection 인스턴스 생성 프로토콜.
new와 new: 메시지 외에도 Collection의 인스턴스는 with: 키워드의 1회, 2회, 3회 또는 4회 발생까지 구성된 4개의 메시지 중 하나를 전송하여 생성할 수 있다. new와 new: 메시지는 Collection에서 재구현되지 않으며, 빈 컬렉션에 해당하는 인스턴스를 생성한다. 그 외 네 개의 인스턴스 생성 메서드들은 Collection에서 유사하게 명시된다. 먼저 인스턴스가 생성되고 (self new 표현식을 이용) 인자가 순서대로 인스턴스에 추가된다. 그 결과 새 인스턴스가 리턴된다. 인스턴스는 super new 또는 self basicNew보다 self new를 이용해 생성되는데 Collection의 서브클래스는 new 메시지를 재구현할 수 있기 때문이다. 색인된 인스턴스 변수가 있는 고정된 크기의 객체를 나타내는 Collection의 서브클래스는 모두 아래의 인스턴스 생성 메시지를 재구현해야 하는데, 그러한 서브클래스는 new에 대한 구현을 제공하지 못하기 때문이다.
| 클래스명 | Collection |
| 슈퍼클래스 | Object |
| 클래스 메서드 | instance creation
with: anObject
| newCollection |
newCollection ← self new.
newCollection add: anObject.
↑newCollection
with: firstObject with: secondObject
| newCollection |
newCollection ← self new.
newCollection add: firstObject.
newCollection add: secondObject.
↑newCollection
with: firstObject with: secondObject with: thirdObject
| newCollection |
newCollection ← self new.
newCollection add: firstObject.
newCollection add: secondObject.
newCollection add: thirdObject.
↑newCollection
with: firstObject with: secondObject with: thirdObject with: fourthObject
| newCollection |
newCollection ← self new.
newCollection add: firstObject.
newCollection add: secondObject.
newCollection add: thirdObject.
newCollection add: fourthObject.
↑newCollection
|
각 인스턴스 생성 메시지의 구현은 새로 생성된 인스턴스가 add: 메시지에 응답하는 기능에 따라 좌우된다. Collection 클래스는 아래 메시지들의 구현을 제공할 수 없는데, 그러한 구현들은 서브클래스가 사용하는 표현에 의존하기 때문이다.
add: anObject
remove: anObject ifAbsent: aBlock
do: aBlock
기본 컬렉션 프로토콜에 존재하는 다른 모든 메시지들은 위의 세 가지 메시지와 관련해 구현된다. 각 서브클래스는 세 가지 기본 메시지를 구현해야 하는데, 이 메시지는 각각 성능을 향상하기 위해 다른 메시지들을 재구현할 수 있다.
❏ Collection 추가 프로토콜.
컬렉션에 요소를 추가하기 위한 프로토콜은 아래와 같이 Collection 클래스에서 구현된다.
adding
add: anObject
self subclassResponsibility
addAll: aCollection
aCollection do: [ :each | self add: each ].
↑aCollection
addAll: 의 구현은 do: 와 add: 에 따라 좌우된다는 사실을 주목한다. aCollection 인자로부터 요소를 추가하는 순서는 컬렉션이 그 요소를 열거하는 순서와 (do:) 요소가 이 컬렉션에 추가되는 방식에 (add:) 따라 달라진다.
❏ Collection 제거 프로토콜.
remove: 와 removeAll: 메시지는 서브클래스에서 제공되어야 하는 기본 메시지 remove:ifAbsent: 와 관련해 구현된다. 이 메서드들은 제거되어야 할 요소가 컬렉션에 없을 경우 오류를 보고한다. remove:ifAbsent: 메서드를 이용하면 또 다른 예외 행위를 명시할 수 있다.
removing
remove: anObject ifAbsent: exceptionBlock
self subclassResponsibility
remove: anObject
self remove: anObject ifAbsent: [self errorNotFound]
removeAll: aCollection
aCollection do: [ :each | self remove: each].
↑aCollection
private
errorNotFound
self error: 'Object is not in the collection'
늘 그렇듯 private 범주는 다른 메시지들의 구현을 지원하기 위해 소개한 메시지를 참조하는데, 다른 객체에서 사용해선 안 된다. 한 번 이상 사용되는 대부분의 오류 메시지들은 리터럴 메시지 문자열을 한 번만 생성하기 위해 private 메시지로 명시될 것이다.
❏ Collection 검사 프로토콜.
컬렉션의 상태를 검사하기 위한 프로토콜 내 메시지는 모두 Collection에서 구현될 수 있다.
testing
isEmpty
↑self size = 0
includes: anObject
self do: [ :each | anObject = each ifTrue: [↑true]].
↑false
occurrencesOf: anObject
| tally |
tally ← 0.
self do: [ :each | anObject = each ifTrue: [tally ← tally + 1]].
↑tally
includes: 와 occurrencesOf: 의 구현은 기본 열거 메시지 do: 에 대한 서브클래스의 구현에 따라 좌우된다. includes: 에 대한 메서드에서 do: 의 블록 인자는 인자와 동일한 요소가 발견되는 즉시 종료된다. 그러한 요소가 발견되지 않으면 마지막 표현식(↑false)이 평가된다. isEmpty에 대한 응답과 includes: 는 Boolean 객체로서 true 또는 false에 해당한다. size 메시지는 Object 클래스에서 상속되지만 Collection에서 재구현되는데, Object에 정의된 바와 같이 size는 가변적 길이의 객체에 0이 아니기(nonzero) 때문이다.
accessing
size
| tally |
tally ← 0.
self do: [ :each | tally ← tally + 1].
↑tally
보다시피 이 접근법은 대부분의 서브클래스에서 재구현되는 컬렉션의 크기를 계산하는 데에 성능이 낮다.
❏ Collection 열거 프로토콜.
do: 를 제외하고 컬렉션의 요소를 열거하는 모든 메시지의 구현은 Collection 클래스에서 제공할 수 있다.
enumerating
do: aBlock
self subclassResponsibility
collect: aBlock
| newCollection |
newCollection ← self species new.
self do: [ :each | newCollection add: (aBlock value: each)].
↑newCollection
detect: aBlock
↑self detect: aBlock ifNone: [self errorNotFound]
detect: aBlock ifNone: exceptionBlock
self do: [ :each | (aBlock value: each) ifTrue: [↑each]].
↑exceptionBlock value
inject: thisValue into: binaryBlock
| nextValue |
nextValue ← thisValue.
self do: [ :each | nextValue ← binaryBlock value: nextValue value: each].
↑nextValue
reject: aBlock
↑self select: [ :element | (aBlock value: element) = = false]
select: aBlock
| newCollection |
newCollection ← self species new.
self do: [ :each | (aBlock value: each) ifTrue: [newCollection add: each]].
↑newCollection
collect: 와 select: 에 연관된 메서드에서 species 메시지는 self로 전송된다. 이 메시지는 컬렉션의 외부 프로토콜에 해당하지 않으므로 제 9장에서 설명하지 않았다. 이는 내부적 용도만 나타내므로 private한 것으로 분류된다. 메시지는 Object 클래스에서 구현되고 수신자의 클래스를 리턴한다.
private
species
↑self class
따라서 아래의 표현식은,
self species new
"수신자의 클래스와 동일한 클래스의 새 인스턴스를 생성하라" 는 의미가 된다.
일부 컬렉션의 경우 이렇게 “비슷한” 인스턴스를 생성하는 것이 적절하지 않은 경우가 있는데, 그러한 새로운 컬렉션이 그 클래스의 인스턴스가 아닐 수 있기 때문이다. 그러한 컬렉션은 species 메시지를 오버라이드할 것이다. 특히 Interval은 그 종류(species)가 Array라고 (Interval을 수정하는 것은 불가능하므로) 응답하며, MappedCollection의 종류는 그것이 매핑하는 컬렉션 종류에 해당한다 (MappedCollection은 해당 컬렉션에 대한 접근자 역할만 수행하므로).
클래스로 new 메시지를 전송하였는데 컬렉션이 인스턴스를 생성하지 못한다면 collect: 과 select: 메시지를 재구현해야 한다. reject: 과 select: 에 관련해 구현되므로 재구현될 필요가 없다.
inject:into: 에 대한 메서드는 수신자에 요소마다 블록 인자를 한 번씩 평가한다. 블록은 앞의 각 평가로부터 고유의 값과 함께 제공되고, 블록의 초기값은 inject: 의 인자로서 제공된다. 블록의 마지막 값은 inject:into: 메시지의 값으로서 리턴된다.
detect: 과 detect:ifNone: 이 두 개의 메시지를 소개하는 이유는 두 개의 제거 메시지, remove: 과 remove:ifAbsent: 메시지를 제공하는 이유와 유사하다. 일반적인 사례에서는 (detect:) 감지 기준에 부합하는 요소가 발견되지 않으면 오류를 보고하며, 프로그래머는 대안적 예외를 (detect:ifNone:) 명시함으로써 오류 보고를 피할 수 있다.
❏ Collection 변환 프로토콜.
어떤 컬렉션이든 Bag, Set, OrderedCollection, SortedCollection 중 하나로 변환하기 위한 프로토콜이 꽤 간단히 구현되는데, 목표 컬렉션의 새 인스턴스를 생성한 후 이를 수신자의 각 요소로 추가하면 된다. 대부분의 경우 새 인스턴스는 원본 컬렉션과 크기가 같다. OrderedCollection의 경우, 요소는 소스의 열거 순서와 상관없이 시퀀스의 끝에 (addLast:) 추가된다.
converting
asBag
| aBag |
aBag ← Bag new.
self do: [ :each | aBag add: each].
↑aBag
asOrderedCollection
| anOrderedCollection |
anOrderedCollection ← OrderedCollection new: self size.
self do:[ :each | anOrderedCollection addLast: each].
↑anOrderedCollection
asSet
| aSet |
aSet ← Set new: self size.
self do: [ :each | aSet add: each].
↑aSet
asSortedCollection
| aSortedCollection |
aSortedCollection ← SortedCollection new: self size.
aSortedCollection addAll: self.
↑aSortedCollection
asSortedCollection: aBlock
| aSortedCollection |
aSortedCollection ← SortedCollection new: self size.
aSortedCollection sortBlock: aBlock.
aSortedCollection addAll: self.
↑aSortedCollection
❏ Collection 출력 프로토콜.
Object에서 printOn: 과 storeOn: 메시지의 구현은 Collection에서 오버라이드된다. Collections는 아래의 형태로 출력되고
className (element element element )
Collections는 동일한 컬렉션을 구성할 수 있는 표현식으로 스스로를 저장한다. 따라서
((className new))
또는
((className new) add: element; yourself)
또는
((className new) add: element; add: element; yourself)
위의 형태를 취하는데, 컬렉션의 요소 수가 0개, 1개, 또는 그 이상인지에 따라 각 요소를 추가하기 위한 캐스케이드된(cascaded) 메시지의 수를 적절하게 이용한다. yourself 메시지는 메시지의 수신자를 리턴한다. 이는 캐스케이드된 메시지의 결과가 수신자가 되도록 보장하기 위해 캐스케이드된 메시지에서 사용된다. 모든 객체는 yourself 메시지로 응답하는데, 이 메시지는 Object 클래스에서 정의된다.
출력과 저장에 일반적으로 사용되는 메서드는 다음과 같다.
printing
printOn: aStream
| tooMany |
tooMany ← aStream position + self maxPrint.
aStream nextPutAll: self class name, '('.
self do:
[ :element |
aStream position > tooMany
ifTrue: [aStream nextPutAll: '...etc...). ↑self].
element printOn: aStream.
aStream space].
aStream nextPut: $)
storeOn: aStream
| noneYet |
aStream nextPutAll: '(('.
aStream nextPutAll: self class name.
aStream nextPutAll: 'new)'.
noneYet ← true.
self do:
[ :each |
noneYet
ifTrue: [noneYet ← false]
ifFalse: [aStream nextPut: $;].
aStream nextPutAll: 'add:'.
aStream store: each].
noneYet i↑false: [aStream nextPutAll: '; yourself'].
aStream nextPut: $)
private
maxPrint
↑5000
이러한 메서드들은 String에 대한 접근자 역할을 하는 Stream 유형의 인스턴스를 활용한다. printOn: 메서드는 String의 길이에 대한 한계를 생성하도록 설정하는데, 긴 컬렉션은 아래와 같이 출력될 것이다.
className (element element ...etc... )
한계는 maxPrint 메시지에 대한 응답으로 결정되며, 5000개 문자로 설정된다. 서브클래스는 한계를 수정하기 위해 private maxPrint 메시지를 오버라이드할 수 있다.
변수 대신 이렇게 메서드를 사용하는 기법은 메서드에서 매개변수를 제공하는 방법이 된다는 점을 주목한다. 변수는 모든 인스턴스로 접근 가능하려면 클래스 변수가 되어야 하므로 매개변수로서 사용될 수 없다. 서브클래스는 그 슈퍼클래스 중 하나의 클래스 변수와 이름이 같은 클래스 변수를 명시할 수 없으므로, 서브클래스가 만일 변수의 값을 변경하길 원한다면 그 슈퍼클래스의 인스턴스에 대해서도 동일한 조치를 취해야 할 것이다. 그리고 이는 바람직한 결과가 아니다.
출력 포맷은 여러 서브클래스에서 수정된다. Array는 자신의 클래스명을 출력하지 않으며, Intervals는 Number로 전송되는 to: 과 to:by: 메시지의 간단한 표기법을 이용해 출력한다. Symbol은 그것의 문자를 출력하며 (Symbol의 리터럴 형태에서 앞에 붙은 # 없이), String은 하나의 따옴표로 구분된 문자를 출력한다.
storeOn: 메시지는 ArrayedCollection과 그것의 서브클래스 몇몇에서 재구현되는데, 인스턴스들이 간단한 new 대신 new: anInteger를 이용해 생성되기 때문이다. Arrays, Strings, Symbols는 그것의 리터럴 형태에 저장한다. Intervals는 to: 과 to:by: 메시지의 간단한 표기법을 이용한다. MappedCollection은 간접적으로 접근되는 컬렉션으로 전송되는 변환 메시지 mappedBy: 을 이용해 저장한다.
Collection의 서브클래스
Collection의 각 서브클래스마다 우리는 필요한 세 개의 메시지 (add:, remove:ifAbsent:, do:), 그리고 재구현되는 추가, 제거, 검사, 열거 프로토콜의 메시지를 구현하는 메서드를 표시한다. 제 9장에 명시하였듯, 특정 서브클래스에 대한 새로운 컬렉션 프로토콜은 본 장에서는 제시되지 않을 것이다.
Bag 클래스
Bag은 요소가 한 번 이상 나타날 수 있는 정렬되지 않은 컬렉션을 나타낸다. Bags의 요소는 정렬되지 않기 때문에 at: 과 at:put: 메시지는 오류를 보고하기 위해 재구현된다.
Bag의 인스턴스는 Dictionary의 인스턴스를 contents라고 명명된 단일 인스턴스 변수로 가진다. Bag의 각 유일한 요소는 contents에서 Association의 키에 해당하며, Association의 값은 Bag에서 요소가 몇 번 나타나는지를 나타내는 Integer가 된다. 요소를 제거하면 기록이 감소하고, 기록이 1까지 떨어지면 Association은 contents로부터 제거된다. Bag은 new, size, includes:, occurrencesOf: 을 구현한다. 새로운 인스턴스는 그 인스턴스 변수를 Dictionary가 되도록 초기화해야 한다. size의 재구현은 contents의 요소에 대한 모든 값을 합하면 효율적이다. 검사 메시지의 인자들은 contents의 키로 사용된다. includes: 을 구현하면서 검사의 책임은 contents로 전가된다. occurrencesOf: anObject 쿼리에 응답하기 위해 메서드는 anObject가 contents에 키로서 포함되어 있는지 검사한 다음 그와 연관된 값을 (기록; tally) 검색한다.
| 클래스명 | Bag |
| 슈퍼클래스 | Collection |
| 인스턴스 변수명 | contents |
| 클래스 메서드 | instance creation
new
↑super new setDictionary
|
| 인스턴스 메서드 | accessing
at: index
self errorNotKeyed
at: index put: anObject
self errorNotKeyed
size
| tally |
tally ← 0
contents do: [ :each | tally ← tally + each].
↑tally
testing
includes: anObject
↑contents includesKey: anObject
occurrencesOf: anObject
(self includes: anObject)
ifTrue: [↑contents at: anObject]
ifFalse: [↑0]
private
setDictionary
contents ← Dictionary new
(in Collection)
private
errorNotKeyed
self error:
self class name, 's do not respond to keyed accessing messages'
|
요소의 추가는 한 번 추가를 의미하지만 Bags는 여러 번 추가할 수 있다. add: 의 구현은 add:withOccurrences: 을 호출한다. 요소를 제거하면 발생의 횟수를 검사하고 기록을 감소시키며, 기록이 1보다 작을 경우 contents에서 키로 사용되는 요소를 제거한다.
adding
add: newObject
↑self add: newObject withOccurrences: 1
add: newObject withOccurrences: anInteger
contents at: newObject
put: anInteger + (self occurrencesOf: newObject).
↑newObject
removing
remove: oldObject ifAbsent: exceptionBlock
| count |
count ← self occurrencesOf: oldObject.
count = 0 ifTrue: [↑exceptionBlock value].
count = 1
ifTrue: [contents removeKey: oldObject]
ifFalse: [contents at: oldObject put: count - 1]].
↑oldObject
Bag의 요소를 열거한다는 것은 Dictionary의 각 요소를 선택하여 해당 요소의 키로 블록을 평가한다는 의미다 (예: 실제 Bag 요소는 Dictionary의 키에 해당한다). 이는 요소의 발생마다 한 번씩 총 여러 번, 키와 연관된 값이 나타내는 대로 실행되어야 한다.
enumerating
do: aBlock
contents associationsDo:
[ :assoc | assoc value timesRepeat: [aBlock value: assoc key]]
Set 클래스
Sets의 요소들은 Bags의 요소들과 마찬가지로 정렬되어 있지 않으므로 at: 과 at:put: 메시지는 오류 보고를 생성한다. Set은 요소를 한 번 이상 포함할 수 없으므로 요소가 삽입될 때마다 이론상으로는 전체 컬렉션을 검사한다. 모든 요소의 검색을 피하기 위해 Set은 해싱 기법을 이용해 색인된 인스턴스 변수에서 특정 요소를 검색할 장소를 결정한다.
각 Set은 tally로 명명된 인스턴스 변수를 갖는다. 요소의 개수에 대한 기록(tally)을 유지하면 nil이 아닌 요소를 모두 계수함으로써 Set의 크기를 결정하는 데에 수반되는 비효율성을 피할 수 있다. 따라서 new, new:, size가 재구현되는데, new와 new: 은 tally 변수를 초기화하기 위함이고 size는 tally의 값으로 응답하기 위함이다.
| 클래스명 | Set |
| 슈퍼클래스 | Collection |
| 인스턴스 변수명 | tally |
| 클래스 메서드 | instance creation
new
↑self new: 2
new: anInteger
↑(super new: anInteger) setTally
|
| 인스턴스 메서드 | accessing
at: index
self errorNotKeyed
at: index put: anObject
self errorNotKeyed
size
↑tally
private
setTally
tally ← 0
|
new:에 대한 메서드에서 super는 재귀를 피하기 위해 사용된다. Set의 private 메시지인 findElementOrNil: 은 Set의 탐사(probing)를 시작할 색인을 생성하기 위해 인자를 해싱(hash)한다. 탐사는 anObject 인자가 발견될 때까지 또는 nil을 마주칠 때까지 진행된다. 그에 대해 마지막으로 검사한 위치의 색인이 응답된다. 이후 검사 메시지는 아래와 같이 구현된다.
testing
includes: anObject
↑(self basicAt: (self findElementOrNil: anObject)) ~~ nil
occurrencesOf: anObject
(self includes: anObject)
ifTrue: [↑1]
ifFalse: [↑0]
Set에서 어떤 요소든 발생 횟수는 절대 1을 넘지 않는다. Sets는 at: 또는 at:put: 이 사용될 경우 오류를 보고하므로 세 가지 기본 메시지는 basicAt: 과 basicAt:put: 을 사용해야 한다.
adding
add: newObject
| index |
newObject isNil ifTrue: [↑newObject].
index ← self findElementOrNil: newObject.
(self basicAt: index)isNil
ifTrue: [self basicAt: index put: newObject, tally ~ tally + 1].
↑newObject
removing
remove: oldObject ifAbsent: aBlock
| index |
index ← self find: oldObject ifAbsent: [↑aBlock value].
self basicAt: index put: nil.
tally ← tally - 1.
self fixCollisionsFrom: index.
↑oldObject
enumerating
do: aBlock
1 to: self basic Size do:
[ :index |
(self basicAt: index) isNil
ifFalse: [aBlock value: (self basicAt: index)]]
Private 메시지 find:ifAbsent: 은 findElementOrNil: 을 호출하는데, oldObject 요소가 발견되지 않으면 aBlock이 평가된다. 해싱/시험 기법이 올바로 작동하도록 보장하기 위해서는 하나씩 제거될 때마다 (fixCollisionsFrom:) 나머지 요소를 압축할(compact) 필요가 있다. 이러한 메서드는 접근 메시지 basicAt:, basicAt:put:, basicSize를 사용해야 하는 경우를 잘 나타내는 예다.
Dictionary 클래스
Dictionary는 Associations의 컬렉션이다. Dictionary 클래스는 그 슈퍼클래스 Set의 것과 같은 해싱 기법을 이용해 요소를 위치시키지만 Associations 자체가 아니라 Associations 내부의 키에 해싱한다. Dictionary에 대한 접근 메시지 대부분은 Associations 자체가 아니라 Associations의 값을 요소로 취급하도록 재구현된다.
Dictionary는 at: 과 at:put: 을 구현하지만 at: 키워드와 연관된 인자가 Dictionary 내에서 어떤 키가 되도록 재정의한다 (꼭 Integer 색인일 필요는 없다). includes: 의 인자는 Associations 중 하나가 아니라 Dictionary 내에 Associations 중 하나의 값이다. do: 메시지는 Associations가 아니라 값을 열거한다. remove: 에 대한 인자 또한 값이지만 요소들은 키를 이용해 참조되므로 Dictionary에서 삭제하기엔 부적절한 방법이다. removeAssociation: 과 removeKey: 중 하나를 사용해야 한다. 따라서 Dictionary에 대해 remove: 과 remove:ifAbsent: 은 구현되어선 안 된다.
접근 프로토콜에서 대부분의 작업은 Set에서 상속된 private 메시지 또는 키를 찾는 데에 사용되는 것과 유사한 메시지에서 (findKeyOrNil:) 이루어진다.
| 클래스명 | Dictionary |
| 슈퍼클래스 | Set |
| 인스턴스 메서드 | accessing
at: key
↑self at: key ifAbsent: [self errorKeyNotFound]
at: key put: anObject
| index element |
index ← self findKeyOrNil: key.
element ← self basicAt: index.
element isNil
ifTrue:
[self basicAt: index put: (Association key: key value: anObject).
tally ← tally + 1]
" element is an Association. The key already exists, change its value."
ifFalse:
[element value: anObject].
↑anObject
at: key ifAbsent: aBlock
| index |
index ← self findKey: key ifAbsent: [↑aBlock value].
↑(self basicAt: index) value
testing
includes: anObject
"Revert to the method used in Collection."
self do: [ :each | anObject = each ifTrue: [↑true]].
↑false
adding
add: anAssociation
| index element |
index ← self findKeyOrNil: anAssociation key.
element ← self basicAt: index.
element isNil
ifTrue: [self basicAt: index put: anAssociation.
tally ← tally + 1]
ifFalse: [element value: anAssociation value].
↑anAssociation
removing
remove: anObject ifAbsent: aBlock
self shouldNotImplement
enumerating
do: aBlock
self associationsDo: [ :assoc | aBlock value: assoc value]
private
errorKeyNotFound
self error: 'key not found'
|
at:put: 과 add: 의 유사점을 주목하라. 차이는 요소가 발견되지 않을 때 취하는 행동에 나타나는데, at:put: 의 경우 새로운 Association이 생성되어 Dictionary에 저장되고, add: 의 경우 anAssociation 인자가 저장되어 Association에 대한 어떠한 공유된 참조도 유지된다.
collect: 메시지는 동일한 값을 Set으로 수집하여 중복을 던지는 결과가 나타나는 문제를 피하기 위해 재구현된다. select: 메시지는 인자로서의 값을 블록으로 적용함으로써 Associations를 선택하기 위해 재구현된다.
enumerating
collect: aBlock
| newCollection |
newCollection ← Bag new.
self do: [:each I newCollection add: (aBlock value: each)].
↑newCollection
select: aBlock
| newCollection |
newCollection ← self species new.
self associationsDo:
[ :each |
(aBlock value each value)ifTrue: [newCollection add: each]].
↑newCollection
IdentityDictionary는 상등(equal)한 값 대신 동일한 키의 검사를 구현하기 위해 at:, at:put:, add: 을 오버라이드한다. IdentityDictionary는 하나의 Associations 컬렉션으로 구현되지 않고 두 개의 정렬된 키와 값 컬렉션으로 구현되었다. 따라서 do: 또한 재구현되어야 한다. 구현은 표시되지 않는다.
SequenceableCollections
SequenceableCollection은 요소가 정렬된 모든 컬렉션에 대한 슈퍼클래스다. 우리가 살펴보는 메시지들 중 remove:ifAbsent:은 일반적으로 SequenceableCollections에 부적절하다고 명시되는데, 요소들의 순서가 외부적으로 명시되었을 수가 있고 순서대로 제거되어야 한다고 가정하기 때문이다. SequenceableCollections는 정렬되어 있으므로 at: 을 이용해 요소로 접근하는데, 이 구현은 Object 클래스에 제공된다. do: 메시지는 컬렉션 크기에 걸쳐 색인 1에서 각 요소로 접근하여 구현된다. SequenceableCollections는 new: 메시지를 사용해 생성된다. 따라서 collect: 과 select: 은 new 보다는 new: 을 이용해 새로운 컬렉션을 생성하도록 재구현되어야 한다. 다음에 소개할 collect: 과 select: 에 대한 메서드는 새로운 컬렉션으로 접근하기 위해 WriteStream을 사용하고, 원본 컬렉션의 요소로 접근하기 위해서는 at: 메시지를 사용한다.
| 클래스명 | SequenceableCollection |
| 슈퍼클래스 | Collection |
| 인스턴스 메서드 | accessing
size
self subclassResponsibility
removing
remove: oldObject ifAbsent: anExceptionBlock
self shouldNotImplement
enumerating
do: aBlock
| index length |
index ← 0.
length ← self size.
[(index ← index + 1) < = length]
whileTrue: [aBlock value: (self at: index)]
collect: aBlock
| aStream index length |
aStream ← WriteStream on: (self species new: self size).
index ← O.
length ← self size.
[(index ← index + 1) < = length]
whileTrue: [aStream nextPut: (aBlock value: (self at: index))].
↑aStream contents
select: aBlock
| aStream index length |
aStream ← WriteStream on: (self species new: self size).
index ← O.
length ← self size.
[(index ← index + 1) < = length]
whileTrue:
[(aBlock value: (self at: index))
ifTrue: [aStream nextPut: (self at: index)]].
↑aStream contents
|
size가 SequenceableCollection에서 서브클래스의 책임으로 선언되었음을 주목한다. Collection 슈퍼클래스에서 상속된 메서드는 각 요소를 열거하고 그에 따라 계수하기 위해 do: 을 사용한다. 하지만 SequenceableCollection 에 명시되었듯 do: 에 대한 메서드는 컬렉션의 크기를 요청함으로써 색인에 대한 한계를 결정한다. 따라서 size는 do: 와 관련해 표기되지 않도록 재구현되어야 한다.
SequenceableCollection의 서브클래스
❏ LinkedList 클래스.
LinkedList의 요소들은 Link 또는 그 서브클래스 중 하나의 인스턴스들이다. 각 LinkedList는 두 개의 인스턴스 변수를 가지는데 첫 번째 요소에 대한 참조와 마지막 요소에 대한 참조가 그것이다. 요소의 추가는 마지막에 추가되도록 해석되는 것으로 간주하며 (addLast:), addLast: 에 대한 메서드는 요소를 현재 마지막 링크의 다음 링크로 만든다. 요소의 제거는 요소의 앞 링크가 요소의 그 다음 링크(또는 nil)를 참조해야 함을 의미한다. 제거되어야 할 요소가 첫 번째 요소라면 그 다음 링크가 첫 번째 요소가 된다.
| 클래스명 | LinkedList |
| 슈퍼클래스 | SequenceableCollection |
| 인스턴스 변수명 | firstLink lastLink |
| 인스턴스 메서드 | accessing
at: index
| count element size |
count ← 1.
element ← self first.
size ← self size.
[count > size] whileFalse:
[count = index
ifTrue: [↑element]
ifFalse: [count ← count + 1.
element ← element nextLink]].
↑self errorSubscriptBounds: index
at: index put: element
self error: 'Do not store into a LinkedList using at:put:'
adding
add: aLink
↑self addLast: aLink
addLast: aLink
self isEmpty
ifTrue: [firstLink ← aLink]
ifFalse: [lastLink nextLink: aLink].
lastLink ← aLink.
↑aLink
removing
remove: aLink ifAbsent: aBlock
| tempLink |
aLink = = firstLink
ifTrue:
[firstLink ~ aLink nextLink.
aLink = = lastLink ifTrue: [lastLink ←nil]]
ifFalse:
[tempLink ← firstLink.
[tempLink isNil ifTrue: [↑aBlock value].
tempLink nextLink = = aLink]
whileFalse: [tempLink ← tempLink nextLink].
tempLink nextLink: aLink nextLink.
aLink = = lastLink ifTrue: [lastLink ← tempLink]].
aLink nextLink: nil.
↑aLink
enumerating
do: aBlock
| aLink |
aLink ← firstLink.
[aLink isNil] whileFalse:
[aBlock value: aLink.
aLink ← aLink nextLink]
|
nil 링크는 LinkedList의 끝을 시그널링한다. 따라서 do: 열거 메시지가 단순 루프로 구현되어 루프는 컬렉션에서 nil을 만날 때까지 계속된다.
❏ Interval 클래스.
Intervals는 요소가 계산되는 SequenceableCollections다. 따라서 추가 및 제거를 위한 메시지는 지원되지 않는다. 요소는 명시적으로 저장되지 않으므로 모든 접근 메시지(at:, size, do:)는 계산을 필요로 한다. 각 메서드는 마지막으로 계산된 요소가 증가되어야 하는지 (양의 step) 감소되어야 하는지 (음의 step) 확인하여 한계에 (stop) 도달했는지 결정한다.
| 클래스명 | Interval |
| 슈퍼클래스 | SequenceableCollection |
| 인스턴스 변수명 | start stop step |
| 클래스 메서드 | instance creation
from: startInteger to: stopInteger
↑self new
setFrom: startInteger
to: stopInteger
by: 1
from: startInteger to: stopInteger by: stepInteger
↑self new
setFrom: startInteger
to: stopInteger
by: stepInteger
|
| 인스턴스 메서드 | accessing
size
step < 0
ifTrue: [start < stop
ifTrue: [↑O]
ifFalse: [↑stop -- start // step + 1]]
ifFalse: [stop < start
ifTrue: [↑O]
ifFalse: [↑stop -- start // step + 1]]
at: index
(index > = 1 and: [index < = self size])
ifTrue: [↑start + (step * (index - 1))]
ifFalse: [self errorSubscriptBounds: index]
at: index put: anObject
self error: 'you cannot store into an Interval'
adding
add: newObject
self error: 'elements cannot be added to an Interval'
removing
remove: newObject
self error: 'elements cannot be removed from an Interval'
enumerating
do: aBlock
| aValue |
aValue ← start.
step < 0
ifTrue: [[stop < = aValue]
whileTrue: [aBlock value: aValue.
aValue ← aValue + step]]
ifFalse: [[stop > = aValue]
whileTrue: [aBlock value: aValue.
aValue ← aValue + step]]
collect: aBlock
| nextValue i result |
result ← self species new: self size.
nextValue ← start.
i ← 1.
step < 0
ifTrue: [[stop < = nextValue]
whileTrue:
[result at: i put: (aBlock value: nextValue).
nextValue ← nextValue + step.
i ← i + 1]]
ifFalse: [[stop > = nextValue]
whileTrue:
[result at: i put: (aBlock value: nextValue).
nextValue ← nextValue + step.
i ← i + 1]].
↑result
private
setFrom: startInteger to: stopInteger by: stepInteger
start ← startInteger.
stop ← stopInteger.
step ← stepInteger
|
❏ ArrayedCollections -- Array, ByteArray, String, Text, Symbol ArrayedCollection은 SequenceableCollection의 서브클래스로, 각 ArrayedCollection은 가변적 길이의 객체다. 모든 인스턴스 생성 메서드는 new가 아니라 new: 를 이용하기 위해 재구현된다. ArrayedCollections는 고정된 길이를 가지므로 add: 이 허용되지 않으며, 그 슈퍼클래스에서는 이미 remove: 이 허용되지 않고 do: 이 구현되어 있다. 따라서 ArrayedCollection에서는 size만 구현되어 있는데, 이것은 색인된 인스턴스 변수의 개수를 보고하는 시스템 프리미티브다.
ArrayedCollection의 서브클래스 중에서 Array와 ByteArray는 본 장에서 소개하는 메시지 중 어떤 것도 재구현하지 않는다. String에 대한 접근 메시지인 at:, at:put:, size는 시스템 프리미티브로서, Text에서 모든 접근 메시지는 인스턴스 변수 string(String의 인스턴스)에 메시지로서 전달된다. Symbol은 at:put: 을 허용하지 않고 String을 그 종류(species)로서 리턴한다.
❏ OrderedCollections 그리고 SortedCollections.
OrderedCollection은 정렬되고 연속된 요소의 시퀀스를 저장한다. OrderedCollections는 확장 가능하며, 시퀀스에 추가 공간을 할당하여 효율성을 어느 정도 보장할 수 있다. 두 인스턴스 변수, firstIndex와 lastIndex는 시퀀스에서 실제 첫 번째 요소와 마지막 요소를 가리킨다.
OrderedCollection으로의 색인은 접근 메시지에 대해 (at: 과 at:put:) firstIndex에서 lastIndex까지 범위 내에서 변환되고, size는 두 색인 간 차이보다 하나 더 많을 뿐이다. 요소의 추가는 끝에 추가되는 것으로 해석되고, 끝에 공간이 없으면 할당된 추가 공간을 이용해 컬렉션이 복사된다 (makeRoomAtLast가 이러한 작업을 실행하는 private 메시지다.). 요소를 저장하는 실제 위치는 lastIndex 다음에 계산된 색인 위치다. 요소가 제거되면 나머지 요소들은 위로 이동하여 요소들이 연속된 채로 유지되어야 한다(removeIndex:).
| 클래스명 | OrderedCollection |
| 슈퍼클래스 | SequenceableCollection |
| 인스턴스 변수명 | firstIndex lastIndex |
| 클래스 메서드 | instance creation
new
↑self new: 10
new: anInteger
↑(super new: anInteger) setIndices
|
| 인스턴스 메서드 | accessing
size
↑lastIndex - firstIndex + 1
at: anInteger
(anInteger < 1 or: [anInteger + firstIndex - 1 > lastIndex])
ifTrue: [self errorNoSuchElement]
ifFalse: [↑super at: anInteger + firstIndex - 1]
at: anInteger put: anObject
| index |
index ← anInteger truncated.
(index < 1 or: [index + firstIndex - 1 > lastIndex])
ifTrue: [self errorNoSuchElement]
ifFalse: [↑super at: index + firstIndex - 1 put: anObject]
adding
add: newObject
↑self addLast: aLink
addLast: newObject
lastIndex = self basicSize ifTrue: [self makeRoomAtLast].
lastIndex ← lastIndex + 1.
self basicAt: lastIndex put: newObject.
↑newObject
removing
remove: oldObject ifAbsent: absentBlock
| index |
index ← firstIndex.
[index < = lastIndex]
whileTrue:
[oldObject = (self basicAt: index)
ifTrue: [self removeIndex: index.
↑oldObject]
ifFalse: [index ← index + 1]].
↑absentBlock value
private
setIndices
firstIndex ← self basicSize // 2 max: 1.
lastIndex ← firstIndex - 1 max: 0
errorNoSuchElement
self error:
'attempt to index non-existent element in an ordered collection'
|
열거 메시지 do:, collect:, select:은 각각 재구현되는데, do: 은 SequenceableCollection에서 제공되는 메서드보다 더 나은 성능을 제공한다.
enumerating
do: aBlock
| index |
index ← firstIndex.
[index < = lastIndex]
whileTrue:
[aBlock value: (self basicAt: index).
index ← index + 1]
collect: aBlock
| newCollection |
newCollection ← self species new.
self do: [:each | newCollection add: (aBlock value: each)].
↑newCollection
select: aBlock
| newCollection |
newCollection ← self copyEmpty.
self do: [ :each | (aBlock value: each) ifTrue: [newCollection add: each]].
↑newCollection
select: 에 대한 메서드에서는 copyEmpty 메시지를 원본 컬렉션으로 전송함으로써 새 컬렉션이 생성된다. 이 메시지는 원본의 모든 요소를 보유하기에 충분한 공간을 할당하여 새로운 컬렉션을 생성하긴 하지만 모든 요소가 저장되지는 않을 것이다. 이렇게 새 컬렉션을 확장하는 데에 소요되는 시간을 피할 수 있다.
SortedCollection은 OrderedCollection의 서브클래스다. at:put: 메시지는 오류를 보고하면서 프로그래머에게 add:를 사용할 것을 요청하고, 인스턴스 변수 sortBlock의 값에 따라 새 요소를 삽입한다. 삽입 위치는 "bubble sort"(버블 정렬)로 결정된다. collect: 또한 블록의 값을 수집하기 위해 SortedCollection가 아니라 OrderedCollection을 생성하도록 재구현된다. 코드는 표시되지 않으며, Smalltalk-80에서 버블 정렬은 다른 여느 프로그래밍 언어와 마찬가지로 표시된다.
MappedCollection 클래스
MappedCollection의 인스턴스는 두 개의 인스턴스 변수, domain과 map을 갖는다. domain의 값은 Dictionary이거나 SequenceableCollection이고, 그 요소들은 map을 통해 간접적으로 접근할 수 있다. add: 메시지는 허용되지 않는다. at: 과 at:put: 은 from으로부터 domain 요소로 간접 접근을 지원하기 위해 MappedCollection에서 재구현된다. MappedCollection의 size는 그 domain의 size다.
| 클래스명 | MappedCollection |
| 슈퍼클래스 | Collection |
| 인스턴스 변수명 | domain map |
| 클래스 메서드 | instance creation
collection: domainCollection map: mapCollection
↑super new setCollection: domainCollection map: mapCollection
new
self error: 'use collection:map: to create a Mapped Collection'
|
| 인스턴스 메서드 | accessing
at: anIndex
↑domain at: (map at: anIndex)
at: anIndex put: anObject
↑domain at: (map at: anIndex) put: anObject
size
↑map size
adding
add: newObject
self shouldNotImplement
enumerating
do: aBlock
map do:
[ :mapValue | aBlock value: (domain at: mapValue)]
collect: aBlock
| aStream |
aStream ← WriteStream on: (self species new: self size).
self do: [ :domainValue |
aStream nextPut: (aBlock value: domainValue)].
↑aStream contents
select: aBlock
| aStream |
aStream ← WriteStream on: (self species new: self size).
self do:
[ :domainValue |
(aBlock value: domainValue)
ifTrue: [aStream nextPut: domainValue]].
↑aStream contents
private
setCollection: domainCollection map: mapCollection
domain ← domainCollection.
map ← mapCollection
species
↑domain species
|