Кирютенко Ю.А., Савельев В.А. Объектно-ориентированное программирование. Язык Smalltalk

Подождите немного. Документ загружается.

130 Глава 7. Наборы на любой вкус

Класс String

Cо строками — экземплярами класса String мы уже много раз встреча-

лись. Систематизируем наши знания и отметим некоторые их новые свой-

ства. Строка может содержать в качестве элементов только экземпляры

класса Character. Экземпляры класса String понимают все сообщения, до-

пустимые для индексированных наборов. Кроме того, класс String поддер-

живает дополнительный протокол лексикографического сравнения своих

экземпляров (<, <=, >, >=) в соответствии с содержащимися в стро-

ках символами. Строку можно конвертировать только в строку прописных

символов (asUpperCase) или только строчных (asLowerCase). При пере-

даче строк в интерфейсы операционной системы используется сообщение

asAsciiZ, которое возвращает Си-строку (в конец строки добавляет нулевой

байт); обратное преобразование выполняет сообщение trimNullTerminator.

Приведем еще несколько примеров работы со строками:

’four’ < ’two’ → true

’fifth’ > ’second’ → false

’first string’ asUpperCase → ’FIRST STRING’

’First String’ asLowerCase → ’first string’

В качестве примера работы со строками как с индексированными набо-

рами приведем реализацию сообщения asLowerCase:

asLowerCase

| answer size index aCharacter |

size := self size.

answer := String new: size.

index := 1.

[index <= size] whileTrue: [

(aCharacter := self at: index) isUpperCase

ifTrue: [aCharacter := aCharacter asLowerCase].

answer at: index put: aCharacter.

index := index + 1].

^ answer

Класс Symbol

Экземпляр класса Symbol (СистемноеИмя) — уникальная последова-

тельность символов, которая используется в системе Смолток в качестве

имени объекта или метода. Напомним, что экземпляр класса Symbol можно

ввести литерально, используя символ ’#’ как префикс определяющей по-

следовательности символов, но используется и печатается уже введенное

имя без префикса. Класс Symbol, в отличие от класса String, не поддержи-

вает сообщения new:.

7.2. Индексированные наборы 131

В классе String определен метод asSymbol, который преобразует строку,

получившую это сообщение, в экземпляр класса Symbol.

Преимуществом экземпляров класса Symbol является то, что система

заботится об их уникальности, и два литерально совпадающие экземпляра

этого класса совпадают и как объекты. Такой способ хранения позволяет

вместо проверки имен на равенство использовать более эффективную про-

верку на идентичность. Система также запрещает все изменения имени.

Поэтому для редактирования имя сначала преобразуют в строку, которую

и редактируют, после чего строка может быть преобразована в новое имя.

При выполнении над именами итераций, создающих новый набор, этот на-

бор создается как строка. Класс Symbol, подобно классу Interval, переопре-

деляет сообщение species:

species

^ String

Приведем не сколько примеров, в которых используются имена.

#Volvo size → 5

#Volvo asString → ’Volvo’

#at:put: first → $a

’ABCDEFGH’ asSymbol → ABCDEFGH

Symbol mustBeSymbol: 123 → ERROR

Symbol mustBeSymbol: #String → Symbol

Symbol intern: ’Alpha’ → Alpha

В заключение отметим одну очень полезную операцию сразу со всеми

символами системы Smalltalk Express. Поскольку экземпляры класса Sym-

bol не собираются сборщиком мусора, неиспользуемые имена постепенно

накапливаются и засоряют систему. При выполнении выражения Symbol

purgeUnusedSymbols имена, которые больше не используются, удаляются.

7.2.2. Наборы, динамически меняющие размер

Класс OrderedCollection

Класс OrderedCollection описывает наборы, порядок в которых опреде-

ляется той последовательностью, в которой элементы добавляются в набор

и удаляются из него. При этом экземпляры класса OrderedCollection расши-

ряемы с обоих концов. Поэтому экземпляр класса OrderedCollection может

выступать и как стек, и как очередь. Напомним, что стек — это последова-

тельный набор, в котором удаление и добавление элементов производятся

на одном и том же конце, называемом вершиной стека. Часто о стеке гово-

рят, что это набор с порядком «последним пришел — первым ушел» (“last-in

132 Глава 7. Наборы на любой вкус

first-out”) или сокращенно lifo-набор. Очередь — это последовательный на-

бор, в котором удаление элементов производится в его начале, а добавление

— в конце. Часто об очереди говорят, что это набор с порядком «первым

пришел — первым ушел» (“first-in first-out”) или сокращенно fifo-набор.

Из определения класса OrderedCollection

IndexedCollection subclass: #OrderedCollection

instanceVariableNames: ’startPosition endPosition contents ’

classVariableNames: ’ ’

poolDictionaries: ’ ’

видно, что его экземпляры имеют три переменные. Переменные startPo-

sition с начальным значением 1 и endPosition с начальным значением 0

указывают на первый и последний элементы экземпляра. Сами элементы

доступны по внешним ключам-индексам и хранятся в массиве contents.

Поэтому все сообщения к экземпляру OrderedCollection, связанные с до-

ступом к элементам набора, вызывают обращение к переменной contents.

Рассмотрим реализацию в классе OrderedCollection двух основных со-

общений — add: и remove:ifAbsent:. Сообщение add: реализуется так же,

как и сообщение addLast:, и добавляет новый элемент в конец набора.

add: anObject

endPosition = contents size

ifTrue: [self putSpaceAtEnd].

endPosition := endPosition + 1.

contents at: endPosition put: anObject.

^ anObject

remove: anObject ifAbsent: aBlock

| index |

index := startPosition.

[index <= endPosition]

whileTrue: [anObject = (contents at: index)

ifTrue: [self removeIndex: index.

^ anObject].

index := index + 1].

^ aBlock value

Код этих методов нуждается в небольшом комментарии. Выражение self

putSpaceAtEnd расширяет набор, добавляя в него место для размещения

нового элемента в случае, если все ранее выделенное пространство ис-

черпано. Выражение self removeIndex: index реально производит удаление

элемента, расположенного по индексу index, возвращая его; если index ока-

жется вне допустимых границ, будет выдано сообщение об ошибке.

7.2. Индексированные наборы 133

Также отметим, что в связи с таким определением класс а многие сооб-

щения, наследуемые из суперклассов, в целях достижения большей эффек-

тивности переопределяются. Приведем только один простой пример:

size

^ endPosition − (startPosition − 1)

В дополнение к сообщениям, наследуемым из своих суперклассов, этот

класс определяет много новых сообщений, которые реализуют специфику

именно этого класса и позволяют добавлять, удалять и обращаться к эле-

ментам в начале набора, в конце набора и в любом другом места набора,

определяя предшествующий или последующий элемент.

Класс OrderedCollection Протокол экземпляра

after: oldObject Возвращает элемент из получателя, стоящий после элемента old-

Object; если в получателе нет элемента oldObject или элемента после него,

сообщает об ошибке.

before: oldObject Возвращает элемент, стоящий до элемента oldObject; если в по-

лучателе нет элемента oldObject или элемента до него, сообщает об ошибке.

add: newObject after: oldObject Добавляет после элемента oldObject элемент new-

Object, возвращает newObject; если элемента oldObject в получателе нет, со-

общает об ошибке.

add: newObject before: oldObject Аналогично предыдущему, но объект newObject

добавляется в получатель перед элементом oldObject.

addAllFirst: anOrderedCollection Добавляет каждый элемент из аргумента anOrde-

redCollection в начало получателя, возвращает anOrderedCollection.

addAllLast: anOrderedCollection Добавляет каждый элемент из аргумента anOrde-

redCollection в конец получателя, возвращает anOrderedCollection.

addFirst: newObject Добавляет элемент newObject в начало получателя, возвра-

щает newObject.

addLast: newObject Добавляет элемент newObject в конец получателя, возвращает

newObject.

removeFirst Удаляет первый элемент в получателе и возвращает его; если получа-

тель пуст, сообщает об ошибке.

removeLast Удаляет последний элемент из получателя и возвращает его; если по-

лучатель пуст, сообщает об ошибке.

Класс SortedCollection

Класс SortedCollection — подкласс класса OrderedCollection. Элементы

в экземпляре класса SortedCollection упорядочиваются с помощью функ-

ции двух переменных. Эта функция представляется блоком с двумя аргу-

ментами, называемым блоком сортировки. В такие наборы новый элемент

134 Глава 7. Наборы на любой вкус

можно добавить только с помощью сообщения add:, которое этим классом

переопределяется. Сообщения, точно указывающие место вставки нового

элемента (типа addFirst:, addLast), не могут посылаться экземплярам клас-

са SortedCollection. По этому все такие сообщения переопределяются, и их

реализации состоят из одного выражения ^ self invalidMessage.

Чтобы создать новый экземпляр класса SortedCollection, в котором ре-

ально еще нет ни одного элемента, следует использовать одно из следую-

щих пяти выражений.

SortedCollection new.

SortedCollection new: 10.

SortedCollection sortBlock: [:a :b | . . . ].

anyCollection asSortedCollection.

anyCollection asSortedCollection: [:a :b | . . . ].

Блок сортировки может иметь любую структуру, но последнее выраже-

ние блока должно обязательно возвращать true или false. Когда во время

создания экземпляра блок сортировки не указывается, по умолчанию ис-

пользуется блок сортировки [:a :b | a <= b]. Поэтому элементы такого

набора должны понимать сообщение сравнения <=. Блок сортировки уже

созданного экземпляра может быть изменен в любое время посылкой эк-

земпляру сообщения sortBlock: newBlock, что приведет к автоматической

пересортировке набора в соответствии с блоком newBlock.

Обратите внимание, что одно и то же сообщение sortBlock: aBlock по-

сылается классу SortedCollection, если необходимо создать новый экзем-

пляр с указанным блоком сортировки, и его экземпляру, если в экземпляре

надо изменить критерий сортировки элементов. Никакого недоразумения

или неоднозначности здесь нет. Вспомните, как объект, пользуясь иерархи-

ей, определяет метод, необходимый для выполнения сообщения.

Реализация большинства сообщений наследуется из суперкласса, а со-

общение add: переопределяется, чтобы реализовать сортировку:

add: anObject

| index element |

endPosition = contents size

ifTrue: [self putSpaceAtEnd].

index := endPosition.

endPosition := endPosition + 1.

[index < startPosition]

whileFalse: [

element := contents at: index.

(sortBlock value: anObject value: element)

ifFalse: [^ contents at: index + 1 put: anObject].

7.3. Неиндексированные наборы 135

contents at: index + 1 put: element.

index := index - 1].

^ contents at: index + 1 put: anObject

Рассмотрим небольшой пример. Предположим, что мы желаем создать

упорядоченный по алфавиту список имен. Пусть ch := SortedCollection

new. По умолчанию у набора ch используется блок [:a :b| a <= b]. Элемен-

тами нашего набора будут экземпляры класса Symbol, которые понимают

сообщения сравнения. Приведем примеры выражений и отметим значение

переменной ch после каждой операции.

ch add: #Joe → Joe (SortedCollection(Joe))

ch add: #Bill → Bill (SortedCollection(Bill Joe))

ch sortBlock: [:a :b | a > b] → SortedCollection(Joe Bill)

7.3. Неиндексированные наборы

Неиндексированные наборы определяются двумя классами Set и Bag,

экземпляры которых не отвечают на сообщения at: и at:put:. Экземпляры

этих классов ведут себя точно в соответствии с протоколом класса Collec-

tion, и поведение их внешне очень похоже. Единственное различие состоит

в том, что экземпляры класса Bag могут содержать дубли, а экземпляры

класса Set не могут.

7.3.1. Класс Set

Класс Set представляет в системе конечные множества. Как и в мате-

матических множествах, равные элементы не различаются и сохраняют-

ся только один раз. Элементом множества может быть любой объект си-

стемы, за исключением объекта nil. В системе также присутствует класс

IdentitySet, который считает равными только идентичные (совпадающие)

объекты, и класс SymbolSet, оптимизированный для хранения объектов,

являющихся экземплярами класса Symbol. Реализация класса Set и его под-

классов довольно сложна и основана на технике, использующей функцию

расстановки (хеширования). Ограничимся простыми примерами.

mySet := Set new. → Set()

mySet isEmpty. → true

mySet add: 1; add: 1; add: 3; yourself. → Set(1 3)

mySet add: 2. → 2

mySet add: 4; yourself. → Set(1 2 3 4)

mySet isEmpty. → false

136 Глава 7. Наборы на любой вкус

Словари

Класс Dictionary представляет ассоциативные массивы (словари), храня-

щие значения в связи с некоторым уникальным (в пределах словаря) объ-

ектом — ключом. Доступ к значениям словаря осуществляется по ключам.

По традиции, восходящей к Smalltalk-80, Dictionary реализуется как

множество, элементы которого — ассоциативные пары (экземпляры клас-

са Association)

. Природа ассоциативного массива находит отражение и

в протоколе сообщений этого класса. Сообщения includes:, do:, select:,

occurencesOf: переопределяются так, чтобы иметь дело со значениями сло-

варей, а не с ключами или самими парами. Напротив, сообщения at:, at:put:

переопределяются так, чтобы обращаться к ключам ассоциативных пар.

А сообщение add: переопределяется так, чтобы работать с самими ассо-

циативными парами. Так как при обращении к элементам словаря обяза-

тельна ссылка на ключ, основной метод remove:ifAbsent: определяется как

недопустимый и его функции передаются методам removeKey: ifAbsent: и

removeKey:.

Кроме того, протокол работы по поиску, перечислению и удалению в

словаре расширяется для взаимодействия как с самими парами, так и с их

ключами и значениями. Обратите внимание на то, что возвращает каждый

из перечисленных ниже методов.

Класс Dictionary Протокол экземпляра

at: aKey ifAbsent: aBlock Возвращает значение ассоциативной пары получателя c

заданным ключом aKey; если пары с таким ключом нет, возвращает ре зультат

выполнения блока aBlock.

associationAt: aKey Возвращает ассоциативную пару с заданным ключом aKey; ес-

ли ключ не найден, сообщает об ошибке.

associationAt: aKey ifAbsent: aBlock Возвращает ассоциативную пару с заданным

ключом aKey; если ключ не найден, возвращает результат выполнения блока

aBlock.

associationsDo: aBlock Возвращает получателя. Для каждой ассоциативной пары

выполняет одноаргументный блок aBlock с этой парой как аргументом.

includesKey: aKey Возвращает true, когда получатель содержит ассоциативную па-

ру с ключом, равным аргументу aKey; иначе возвращает false.

keyAtValue: value Возвращает первый ключ, найденный по значению value; если

такового нет, возвращает nil.

Ассоциативные пары — это деталь, зависящая от реализации, и некоторые но-

вые реализации содержат словари, использующие другие техники хранения. Там

весь протокол, имеющий дело с ассоциативными парами, отсутствует.

7.3. Неиндексированные наборы 137

keyAtValue: value ifAbsent: aBlock Возвращает первый ключ, найденный по значе-

нию value; если такового нет, возвращает результат выполнения блока aBlock.

keys Возвращает экземпляр класса Set (поскольку ключи уникальны), содержащий

все ключи получателя.

keysDo: aBlock Возвращает получателя. Для каждого ключа получателя выполняет

блок aBlock с этим ключом как аргументом.

removeKey: aKey Удаляет из получателя пару c ключом, равным aKey, возвращает

измененного получателя; если такой пары нет, сообщает об ошибке.

removeAssociation: anAssociation Удаляет из получателя пару, равную аргументу

anAssociation, возвращает измененного получателя; если такой пары нет, со-

общает об ошибке.

values Возвращает экземпляр класс а Bag (поскольку значения не уникальны и мо-

гут повторяться), содержащий все значения словаря.

Для демонстрации возможностей словарей со-

ключ значение

hot cold

push pull

stop go

come go

front back

top bottom

здадим словарь с именем opposites, состоящий из

слов-ключей и их антонимов-значений. При этом

для добавления в словарь элементов используем два

разных сообщения.

| opposites |

opposites:= Dictionary new.

opposites at: #hot put: #cold.

opposites at: #push put: #pull.

opposites at: #stop put: #go.

opposites at: #come put: #go.

opposites add: (Association key: #front value: #back).

opposites add: (Association key: #top value: #bottom).

Обратите внимание на еще одно различие между at:put: и add:. В случае

at:put: возвращается значение (аргумент ключевого слова put:); а в случае

add: — ассоциативная пара.

Теперь словарь opposites состоит из пар «ключ → значение», приве-

денных в таблице. Не забывайте, что одно и то же значение может быть

связано с любым числом ключей, в то время как ключи уникальны.

В следующих примерах, применяя сообщения для проверки, посмот-

рим, есть ли в словаре opposites некоторые значения:

opposites size → 6

opposites includes: #cold → true

opposites includes: #hot → false

opposites occurrencesOf: #go → 2

opposites at: #stop put: #start → start

138 Глава 7. Наборы на любой вкус

Поскольку каждый ключ в словаре уникален и может появиться толь-

ко один раз, в по следнем выражении для уже существовавшего в словаре

ключа stop определяется новое значение start, которое заменяет прежнее

значение go. Аналогичным образом можно проверить наличие в словаре

opposites некоторых ассоциативных пар и ключей.

opposites includes: (Association key: #come value: #go) → true

opposites includesKey: #come → true

opposites includesKey: #hot → true

opposites includesKey: #go → false

Экземпляры класса IdentityDictionary по понимаемым ими сообщениям

ничем не отличаются от экземпляров его суперкласса Dictionary. Но класс

IdentityDictionary почти все наследуемые методы переопределяет так, чтобы

проверять идентичность ключей, а не их равенство (см. с. 88).

Класс SystemDictionary — подкласс IdentityDictionary; он имеет в систе-

ме только один экземпляр — системный словарь с именем Smalltalk. Его

ключи — системные имена. Дополнительно класс SystemDictionary содер-

жит сообщения для управления самой системой через свой единственный

экземпляр (см. раздел 3.4.4).

7.3.2. Класс Bag

Экземпляр класса Bag (простой набор, или «мешок») может содержать

дубли, ведет себя согласно протоколу для всех наборов, и его поведение

похоже на поведение экземпляров класса Set,

Возможность хранения дублей подчеркивается наличием сообщения

add: newObject withOccurrences: anInteger, которое добавляет объект new-

Object в получатель в количестве anInteger и возвращает newObject.

В качестве примера рассмотрим код, который вычисляет частоту букв

английского а лфавита в некотором текстовом файле, например, с именем

packing.txt.

| input frequency output ch |

input := File pathName:’packing.txt’.

output := File pathName:’frqltrs.txt’.

frequency := Bag new.

[input atEnd] whileFalse: [

ch := input next.

(ch isLetter) ifTrue: [frequency add: ch asLowerCase]].

frequency asSet asSortedCollection do: [:ch |

output nextPutAll: ch printString;

7.3. Неиндексированные наборы 139

nextPutAll: ’ –> ’;

nextPutAll: (frequency occurrencesOf: ch) printString;

cr].

output close.

input close.

В результате выполнения этой последовательности выражений будет со-

здан новый файл с именем frqltrs.txt, в который в алфавитном порядке будут

записаны строки (cr — переход на новую строку). Каждая строка состоит

из английской буквы (поскольку это символ, ему предшествует $), стрелки

вида ’–>’ и числа, возникшего в результате вычисления того, сколько раз

встречается данная буква в текстовом файле packing.txt. В этом примере

переменная frequency содержала экземпляр класса Bag, ch — следующий

символ из input, а переменные input и output — потоки. В данном примере

используется сообщение nextPutAll:, записывающее в поток все объекты из

набора, переданного в качестве аргумента.