Основы объектно-ориентированного программирования - Бертран Мейер

Деревья - это списки и их элементы

Класс дерева TREE - еще один яркий пример множественного наследования.

Деревом называется иерархическая структура, составленная из узлов с данными. Обычно ее определяют так: "Дерево либо пусто, либо содержит объект, именуемый его корнем, с присоединенным списком деревьев (рекурсивно определяемых) - потомков корневого узла". К этому добавляют определение узла: "Пустое дерево не содержит узлов; узлами непустого дерева являются его корень и по рекурсии узлы потомков". Эти определения, хотя и отражают рекурсивную сущность дерева, не способны показать его внутренней простоты.

Мы же заметим, что между понятиями дерева и узла нет серьезных различий. Узел можно определить как поддерево, корнем которого он является. В итоге приходим к классу TREE [G], который описывает как узлы, так и деревья. Формальный родовой параметр G отражает тип данных в каждом узле. Следующее дерево, является, например, экземпляром TREE [INTEGER]:

Рис. 15.6.  Дерево целых чисел

Вспомним также о понятии списка, чей класс LIST рассмотрен в предыдущих лекциях. В общем случае его реализация требует введения класса CELL для представления его элементов структуры.

Рис. 15.7.  Представление списка

Эти понятия позволяют прийти к простому определению дерева: дерево (или его узел) есть список, - список его потомков, но является также потенциальным элементом списка, поскольку может представлять поддерево другого дерева.

Определение: дерево

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

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

deferred class TREE [G] inherit

LIST [G]

CELL [G]

feature

...

end

От класса LIST наследуются такие компоненты как количество узлов (count), добавление, удаление узлов и т. д.

От класса CELL наследуются компоненты, позволяющие работать с узлами, задающими родителя или братьев: следующий брат, добавить брата, присоединить к другому родителю.

Этот пример характерен тем, что иллюстрирует преимущества повторного использования при множественном наследовании. Создание специальных компонентов вставки или удаления поддеревьев означало бы повторение того, что уже сделано для списка элементов. Нам же остаются лишь косметические доработки.

Кроме того, следует позаботиться о добавлении в предложение feature специфических компонентов, присущих только деревьям, и компонентов, являющихся результатом взаимных компромиссов, неизбежных при любой свадьбе, и обеспечивающих взаимную гармонию родительских классов. Их текст невелик и займет в классе TREE чуть больше страницы, поскольку наш класс вполне законный плод союза списков и элементов списка.

Этот процесс подобен процессу, применяемому математиками при комбинировании теорий: топологическое векторное пространство является одновременно топологическим пространством и векторным пространством. Здесь тоже необходимы некоторые связующие аксиомы.

Составные фигуры

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

Рассмотрим структуру, введенную в предыдущей лекции для изучения наследования и содержащую классы графических фигур: FIGURE, OPEN_FIGURE, POLYGON, RECTANGLE, ELLIPSE и т.д. До сих пор в этой структуре использовалось лишь единичное наследование.

Рис. 15.8.  Элементарные фигуры

Пусть в этой иерархии представлены все нужные нам базовые фигуры. Однако в библиотеку классов хотелось бы включить и не базовые фигуры, имеющие широкое распространение. Конечно, любое изображение каждый раз можно строить из примитивов, но это неудобно. Поэтому мы создадим библиотеку фигур, часть которых будут базовыми, а часть - построена на их основе. Так, из экземпляров базисных классов: отрезка и окружности можно собрать колесо:

Рис. 15.9.  Составная фигура

Колесо, в свою очередь, может пригодиться при рисовании велосипеда, и т. д.

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

Назовем новые фигуры составными (COMPOSITE_FIGURE). Каждую такую фигуру, безусловно, надо порождать от FIGURE, что позволит ей быть "на равных" с базовыми примитивами. Составная фигура - это еще и список фигур, ее образующих, каждая из которых может быть базовой или составной. Воспользуемся множественным наследованием (рис. 15.10).

Для получения эффективного класса COMPOSITE_FIGURE выберем одну из возможных реализаций списка, например связный список - LINKED_LIST. Объявление класса будет выглядеть так:

class COMPOSITE_FIGURE inherit

FIGURE

LINKED_LIST [FIGURE]

feature

...

end

Рис. 15.10.  Составная фигура - это фигура и список фигур одновременно

Предложение feature записывать приятно вдвойне. Работа с составными фигурами во многом сводится к работе со всеми их составляющими. Например, процедура display может быть реализована так:

display is

-- Отображает фигуру, последовательно отображая все ее компоненты.

do

from

start

until

after

loop

item.display

forth

end

end

Как и в предыдущих рассмотрениях, мы предполагаем, что класс список предлагает механизм обхода элементов, основанный на понятии курсора. Команда start устанавливает курсор на первый элемент, если он есть (иначе after сразу же равно True), after указывает, обошел ли курсор все элементы, item дает значение элемента, на который указывает курсор, forth передвигает курсор к следующему элементу.

Я нахожу эту схему прекрасной и, надеюсь, вы тоже пленитесь ее красотой. В ней вы найдете почти весь арсенал средств: классы, множественное наследование, полиморфные структуры данных (LINKED_LIST [FIGURE]), динамическое связывание (вызов item.display применяет метод display того класса, которому принадлежит текущий элемент списка), рекурсию (каждый элемент item сам может быть составной фигурой без ограничения глубины вложенности). Подумать только: есть люди, которые могут прожить всю жизнь и не увидеть этого великолепия!

Но можно пойти еще дальше. Обратимся к другим компонентам COMPOSITE_FIGURE - методам вращения (rotate) и переноса (translate). Они также должны выполнять надлежащие операции над каждым элементом фигуры, и каждый из них может во многом напоминать display. Для ОО-проектировщика это может стать причиной тревоги: хотелось бы избежать повторения; потому выполним преобразование - от инкапсуляции к повторному использованию. (Это могло бы стать девизом.) Техника, рассматриваемая здесь, состоит в использовании отложенного класса "итератор", чьи экземпляры способны выполнять цикл по COMPOSITE_FIGURE. Его эффективным потомком может стать DISPLAY_ ITERATOR, а также ряд других классов. Реализацию этой схемы мы оставляем читателю (см. упражнение 15.4).

Описание составных структур с применением множественного наследования и списка или иного контейнерного класса, как одного из родителей, - это универсальный образец проектирования. Примерами его воплощения являются подменю (см. упражнение 15.8), а также составные команды в ряде интерактивных систем.

Брак по расчету

В приведенных примерах оба родителя играли симметричные роли, но это не всегда так. Иногда вклад каждого из них различен по своей природе.

Важным приложением множественного наследования является обеспечение реализации абстракции, описанной отложенным классом, используя свойства, обеспечиваемые эффективным классом. Один класс абстрактен, второй - эффективен.

Рис. 15.11.  Брак по расчету

Рассмотрим реализацию стека, заданную массивом. У нас уже есть классы для поддержки стеков и массивов в отдельности (абстрактный STACK и эффективный ARRAY, см. предыдущие лекции). Лучший способ реализации класса ARRAYED_STACK (стек, заданный массивом) - описать его как наследника классов STACK и ARRAY. Это концептуально верно: стек-массив одновременно является стеком (с точки зрения клиента) и массивом (с позиций поставщика). Вот описание класса: