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

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

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

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

ляют порядок элементов в наборе. В других используется явно связанные

с элементами набора внешние объекты, служащие ключами поиска. Еще

одно отличие состоит в ограничении того, какие объекты могут быть эле-

ментами набора.

Представим эти характеристики классов в виде табл. 7.1, в которой ис-

пользованы такие сокращения: X — абстрактный класс, да! — набор упо-

рядочен в соответствии с внутренними характеристиками, о.п. — свойство

определяется подклассом.

Таблица 7.1. Характеристики наборов

Класс Порядок Размер Дубли Ключ Элементы

Bag нет любой да нет любой

IndexedCollection X да о.п. о.п. целый о.п.

FixedSizeCollection X да фикс. о.п. целый о.п.

Array да фикс. да целый любой

ByteArray да фикс. да целый 0 – 255

Interval да! фикс. нет целый Number

String да фикс. да целый Character

Symbol да фикс. да целый Character

OrderedCollection да перем. да целый любой

SortedCollection да! перем. да целый любой

Set нет перем. нет нет любой

Dictionary нет перем. нет любой любой

IdentityDictionary нет перем. нет любой любой

SystemDictionary нет перем. нет Symbol любой

Элементы в экземплярах классов Bag и Set не сортируются и не связы-

ваются ни с какими ключами. Дубликаты элементов возможны в экземпля-

рах класса Bag и невозможны в экземплярах класса Set.

Все упорядоченные наборы — это экземпляры подклассов класса In-

dexedCollection. В них элементы доступны через целые положительные

ключи-индексы. Подклассы класса IndexedCollection поддерживают разные

способы упорядочивания своих элементов. Экземпляры подклассов класса

FixedSizeCollection после создания не могут менять свой размер. Элемен-

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

экземпляров класса ByteArray — целые в диапазоне от 0 до 255, элемента-

ми экземпляров класса String — экземпляры класса Character.

Порядок элементов является внешним для экземпляров классов Orde-

redCollection, FixedSizeCollection. Порядок элементов в экземплярах Orde-

7.1. Протокол класса Collection 121

redCollection определяется последовательностью операций по их добавле-

нию и удалению. Элементами экземпляров класса OrderedCollection могут

быть любые объекты. Порядок среди элементов экземпляров классов In-

terval и SortedCollection определяется внутренними свойствами самих эле-

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

земпляра класса Interval составляют арифметическую прогрессию, которая

однозначно определяется во время инициализации экземпляра. Для клас-

са SortedCollection порядок элементов определяется заданным для данного

экземпляра блоком (функцией) сортировки.

Экземпляр класса Dictionary — несортированный набор с внешними

ключами, которые могут быть любыми объектами системы, а сравнение

ключей происходит с помощью равенства =. В его подклассах IdentityDic-

tionary, SystemDictionary внешние ключи сравниваются с помощью опера-

ции тождества ==, что происходит значительно быстрее.

Наша цель — коротко описать протокол самого класса Collection и все

особенности протоколов сообщений его подклассов, а также привести про-

стые поясняющие примеры.

Один из общих протоколов класса Collection нам уже знаком: это прото-

кол, обеспечивающий итерации над наборами (его часто называют прото-

колом перечисления). Кроме того, класс Collection обеспечивает протоколы

для создания новых наборов, преобразования наборов, добавления и удале-

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

7.1.1. Создание новых наборов

В главе, посвященной синтаксису языка, приводились примеры лите-

рального создания некоторых наборов (экземпляров классов Array, String,

Symbol). Для создания новых наборов можно также использовать сообще-

ния new и new:. Но протокол класса Collection содержит специальные со-

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

тремя или четырьмя элементами (в зависимости от числа ключевых слов

with: в ключевом сообщении). Например:

Set with: $a with: $b with: $c. → Set($a $b $c)

Заметим, что основная причина, по которой обеспечиваются только эти

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

в том, что именно такое их количество оказалось достаточным для решения

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

в систему. При желании их число можно увеличить. Например, создадим

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

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

withElements: anArray

"Возвратить набор со всеми элементами из массива anArray."

| answer |

answer := self new.

anArray do: [:element | answer add: element].

^ answer

Теперь множество из предыдущего примера можно создать и так:

Set withElements: #($a $b $c). → Set($a $b $c)

Но почему такой метод будет корректно работать для подклассов клас-

са Collection, ведь они такие разные? Все дело в том, что существующие

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

нии и перечислении элементов набора. Класс Collection реализует сообще-

ния add: anObject (добавить:), remove: anObject ifAbsent: aBlock (уда-

лить:еслиОтсутствует:), do: aBlock (выполнить:) как ^ self implementedBy-

Subclass. То есть эти сообщения должны ре ализовываться подклассами с

учетом их особенностей. Остальной протокол класса Collection реализо-

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

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

^ self invalidMessage. Например, сообщение add: в классе FixedSizeCollec-

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

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

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

из класса Collection, опирающиеся на три перечисленных выше основных

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

классах в качестве примеров.

7.1.2. Преобразование наборов

Так как разные классы наборов имеют разные характеристики, полез-

но иметь возможность преобразовывать набор одного вида в набор другого

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

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

классов. Класс Collection определяет пять сообщений для преобразования

наборов:

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

asArray Возвращает экземпляр класса Array с элементами из получателя.

asBag Возвращает экземпляр класса Bag с элементами из получателя.

asSet Возвращает экземпляр класса Set с теми же элементами, что и у получателя,

при этом дубликаты уничтожаются.

7.1. Протокол класса Collection 123

asOrderedCollection Возвращает экземпляр класс а OrderedCollection с теми же эле-

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

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

asSortedCollection: aBlock Аналогично предыдущему, но с элементами, отсортиро-

ванными согласно блоку сортировки aBlock.

asSortedCollection Возвращает экземпляр класса SortedCollection с элементами из

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

сортировки [:a :b | a <= b].

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

дем только одно из них:

asArray

| answer index |

answer := Array new: self size.

index := 1.

self do: [:element | answer at: index put: element.

index := index + 1].

^ answer

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

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

класса OrderedCollection элементы добавляются в конец последовательно-

сти с помощью сообщения addLast: (добавитьПоследним:). Обратите вни-

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

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

наборе непредсказуем.

Пусть переменная numbers содержит массив #(5 5 1 2 2 3 4). Тогда:

numbers asBag → Bag(5 5 4 3 2 2 1)

numbers asSet → Set(5 4 3 2 1)

numbers asOrderedCollection → OrderedCollection(5 5 1 2 2 3 4)

numbers asSortedCollection → SortedCollection(1 2 2 3 4 5 5)

numbers asSortedCollection: [:a :b | a >= b]

→ SortedCollection(5 5 4 3 2 2 1)

Подводя итог, еще раз подчеркнем, что любой набор можно преобра-

зовать в экземпляр классов Bag, Set, OrderedCollection, Sor tedCollection,

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

Array. Как мы увидим далее, экземпляры классов String и Symbol могут

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

общим протоколом класса Collection. Никакие наборы не могут преобразо-

вываться в экземпляры класс а Interval.

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

7.1.3. Добавление и удаление элементов

Класс Collection обеспечивает общий протокол, позволяющий единооб-

разно манипулировать любыми наборами: добавлять в набор новые элемен-

ты и удалять существующие.

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

add: newObject Добавляет в получатель объект newObject как один из его элемен-

тов; возвращает объект newObject.

addAll: aCollection Добавляет в получатель все элементы из набора aCollection как

его элементы; возвращает aCollection.

remove: oldObject ifAbsent: aBlock Удаляет из получателя элемент, равный объекту

oldObject; если в наборе есть несколько элементов, равных oldObject, уда ляет

первый найденный и возвращает oldObject; если в получателе нет такого

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

remove: oldObject Аналогично предыдущему, но если в получателе нет такого эле-

мента, сообщает об ошибке.

removeAll: aCollection Удаляет из получателя все элементы, входящие в набор aCol-

lection; если какой-либо элемент из набора aCollection не обнаружен, сообща-

ет об ошибке.

Последние два сообщения реализуются через сообщение remove:ifAb-

sent:. Кроме того, в их реализации используется сообщение errorAbsent-

Object, которое сообщает об отсутствии нужного элемента:

remove: anObject

^ self remove: anObject ifAbsent: [self errorAbsentObject]

removeAll: aCollection

aCollection do: [:each | self remove: each].

^ aCollection

Обратите внимание, что для каждого набора, в который добавляется

новый элемент с помощью сообщения add: или удаляется существующий

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

ет аргумент сообщения, а не набор, получивший сообщение, как почему-то

нередко предполагается. В результате часто ошибочно пишут что-то вроде

(myCollection add: x) remove: y, тогда как правильно было бы написать:

myCollection add: x; remove: y

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

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

набору сообщение yourself, реализованное в классе Object и возвращающее

получателя сообщения:

Set new add: x; add: y;. . . ; yourself

7.1. Протокол класса Collection 125

7.1.4. Проверка состояния набора

Следующие сообщения позволяют исследовать состояние набора:

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

includes: anObject Возвращает true только тогда, когда хотя бы один из элементов

получателя равен аргументу anObject.

isEmpty Возвращает true только тогда, когда в получателе нет элементов.

occurencesOf: anObject Возвращает целое число — количество элементов получа-

теля, равных аргументу anObject.

Кроме этих сообщений вс е наборы понимают сообщение size, которое

возвращает количество элементов в наборе. В самом классе Collection такое

сообщение не определено; оно наследуется из класса Object. Посмотрим на

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

онное сообщение inject:into:.

occurrencesOf: anObject

^ self inject: 0

into: [:occurrences :each |

occurrences + (anObject = each ifTrue: [1]

ifFalse: [0])]

В заключение приведем примеры использования сообщений, описанных

в последних двух разделах, используя для этого множество numbers :=

Set new. В последнем столбце указывается значение переменной numbers,

если сообщение привело к его изменению. Тогда:

Выражение Результат Значение numbers

numbers add: 0 0 Set(0)

numbers addAll: #(1 2 3 4 5) (1 2 3 4 5) Set(0 1 2 3 4 5)

numbers addAll: #(6 7) (6 7) Set(0 1 2 3 4 5 6 7)

numbers remove: 0 0 Set(1 2 3 4 5 6 7)

numbers removeAll: #(7 8) ERROR Set(6 5 4 3 2 1 )

numbers size 6

numbers isEmpty false

numbers occurrencesOf: 5 1

numbers includes: 0 false

numbers includes: 3 true

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

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

Абстрактный класс IndexedCollection определяет общий протокол для

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

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

ный класс FixedSizeCollection, который определяет индексированные на-

боры с фиксированным диапазоном изменения целочисленных индексов.

Класс OrderedCollection и его подклассы определяют индексированные на-

боры, размеры которых могут динамически изменяться. Хотя эти классы

во многом похожи, есть характеристики, по которым они сильно отличают-

ся. Рассмотрим некоторые из особенностей протоколов и реализаций этих

системных классов.

Говоря об экземплярах класс а IndexedCollection, мы всегда имеем в виду

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

мый им общий протокол. Класс IndexedCollection наследует из класса Ob-

ject сообщения для работы с индексированными элементами: at:, at:put:,

size. Класс IndexedCollection также расширяет протоколы класса Collection,

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

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

дящих замену элементов набора на элементы из другого набора.

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

atAll: aCollection put: anObject Заменяет каждый элемент получателя с индексом

из aCollection на объект anObject; возвращает обновленный набор.

atAllPut: anObject Заменяет каждый элемент из получателя на объект anObject,

возвращает обновленный набор.

first Возвращает первый элемент получателя; сообщает об ошибке, если получатель

пуст.

last Возвращает последний элемент получателя; сообщает об ошибке, если получа-

тель пуст.

indexOf: anElement ifAbsent: aBlock Возвращает индекс первого элемента получа-

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

зультат выполнения блока aBlock.

indexOf: anElement Аналогично предыдущему, но если нужного элемента нет, воз-

вращает 0.

replaceFrom: start to: stop with: aCollection

Возвращает получателя, в котором, начиная с индекса start и заканчивая ин-

дексом stop, элементы заменены на элементы из аргумента aCollection; в на-

боре aCollection должно быть ровно stop −start + 1 элементов, иначе сооб-

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

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

Рассмотрим примеры посылки т аких сообщений экземплярам класса

String (аналогичные примеры можно написать и для экземпляров других

подклассов класса IndexedCollection):

’aaaaaaaa’ size → 8

’aaaaaaaa’ atAll: #(2 3 8) put: $b → ’abbaaaab’

’abababab’ indexOf: $b → 2

’aaaaaaaa’ atAllPut: $b → ’bbbbbbbb’

’This string’ first → $T

’This string’ last → $g

’ABCDEFGH’ indexOf: $F → 6

’ABCDEFGH’ indexOf: $M ifAbsent: [0] → 0

’ABCDEFGH’ indexOf: $C ifAbsent: [0] → 3

’The cow eat’ replaceFrom: 5 to: 7 with: ’dog’ → ’The dog eat’

Иногда при преобразованиях надо сохранять набор-оригинал. Чтобы не

делать предварительно его копии, проще во время выполнения операции

создать новый набор — копию оригинала с необходимыми изменениями.

Протокол копирования класса IndexedCollection включает довольно много

сообщений такого рода. Вот некоторые из них:

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

, anIndexedCollection Возвращает копию получателя, в которую по порядку добав-

лены все элементы из anIndexedCollection.

copyFrom: start to: stop Возвращает копию части получателя, состоящую из его

элементов с индексами от start до stop.

copyReplaceFrom: start to: stop with: aCollection Возвращает копию получателя

сообщения, в которой элементы от индекса start и до индекса stop заменены

на элементы набора aCollection.

copyWith: newElement Возвращает копию получателя, в конец которого добавлен

объект newElement.

copyWithout: oldElement Возвращает копию получателя, из которого удален первый

встретившийся элемент, равный oldElement.

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

#(one two three) copyWith: #four → (one two three four)

#(one two three) copyWithout: #two → (one three)

Так как элементы в экземплярах класса IndexedCollection упорядочены

(см. с. 120), то возможно их перечисление, начиная с первого и до послед-

него. Поэтому класс IndexedCollection переопределяет сообщение do:.

do: aBlock

"Возвращает получателя. Пользуясь каждым элементом

получателя в качестве аргумента блока, выполняет aBlock."

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

| index size |

index := 1.

size := self size.

[index > size] whileFalse: [aBlock value: (self at: index).

index := index + 1]

Но тогда возможно и перечисление от последнего до первого, для чего

определяется сообщение reverseDo: aBlock. Кроме того, протокол расши-

ряется следующими полезными сообщениями:

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

findFirst: aBlock Вычисляет одноаргументный блок aBlock с каждым элементом по-

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

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

ния true. Если такого элемента нет, сообщает об ошибке.

findLast: aBlock Вычисляет одноаргументный блок aBlock с каждым элементом по-

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

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

ем значения true. Если такого элемента нет, сообщает об ошибке.

with: anIndexedCollection do: aBlock Вычисляет блок aBlock, имеющий два пара-

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

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

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

Поясним последнее сообщение примером. Реализуем в классе Indexed-

Collection метод, который проверяет, содержат ли получатель и аргумент

хотя бы в одной позиции равные элементы.

isEqualElementsInIndex: anIndexedCollection

| length |

length := self size min: anIndexedCollection size.

(self copyFrom: 1 to: length)

with: (anIndexedCollection copyFrom: 1 to: length)

do: [:a :b | (a = b) ifTrue: [^ true]].

^ false

Теперь можно посылать сообщение isEqualElementsInIndex: anIndexed-

Collection любому индексированному набору.

’after’ isEqualElementsInIndex: ’before’ → true

#(1 2 3 4) isEqualElementsInIndex: #(4 3 2 1) → false

#Volvo isEqualElementsInIndex: #Toto → true

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

7.2.1. Наборы фиксированного размера

Класс FixedSizeCollection — абстрактный подкласс класса Collection, эк-

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

ра, определяемого при создании. Ради эффективности здесь переопределя-

ются несколько сообщений из суперклассов (например, collect: и select:).

Экземпляр класса Array в качестве элементов может содержать любые

объекты и представляет собой простейшую структуру для хранения объек-

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

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

бавляя, а лишь переопределяя сообщения printOn: и storeOn:.

Класс Interval

Экземпляры класса Interval (будем называть их интервалами) представ-

ляют конечную арифметическую прогрессию. Элементами могут быть лю-

бые числа: целые, рациональные числа с плавающей точкой или рацио-

нальные дроби. Хотя интервал содержит все числа внутри определенного

числового диапазона с определенной разностью прогрессии (приращением

между соседними числами), на самом деле он реализуется вычислением

членов конечной арифметической прогрессии с помощью трех параметров:

beginning — первый член прогрессии; end — граница для членов прогрес-

сии; increment — разность прогрессии.

Кроме сообщений класс а Number, создающих интервал, его можно со-

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

Interval from: 2 to: 5 → Interval(2 3 4 5)

Interval from: 2 to: 7 by: 2 → Interval(2 4 6 )

10.2 to: 11 by: 0.3 → Interval(10.2 10.5 10.8)

Заметим, что все элементы экземпляра класса Interval «создаются» в мо-

мент инициализации экземпляра, поэтому элементы из экземпляра нельзя

удалять, а новые элементы нельзя добавлять в него. Interval также пере-

определяет метод at:, а метод at:put: запрещает. В дополнение к наследуе-

мым сообщениям протокол экземпляра класса Interval поддерживает сооб-

щение для определения разности арифметической прогрессии (сообщение

increment).

Поскольку при выполнении итераций над арифметической прогрессией

нет никакой гарантии, что создаваемый новый набор снова будет арифме-

тической прогрессией, класс Interval переопределяет сообщение species,

необходимое в итерационных вычислениях (см. с. 105):

species

^ Array