Читать онлайн «Основы объектно-ориентированного программирования». Страница 26

Выполнение требования Независимости Представлений поможет также реализовать связанный с ним принцип Единственного Выбора, сформулированный при обсуждении модульности, который предписывает избегать ситуаций, связанных с разбором вариантов, например

if "t это массив, управляемый хешированием" then

"Применить поиск с хешированием"

elseif "t это дерево двоичного поиска" then

"Применить обход дерева двоичного поиска"

elseif

(и т.д.)

end

Было бы в равной степени неудобно иметь такую структуру в самом модуле (нельзя же ожидать, что модуль, организующий таблицу, знает обо всех текущих и будущих вариантах), так и воспроизводить ее в каждом модуле-клиенте. (См. "Единственный выбор", лекция 3) Решение состоит в том, чтобы обеспечить автоматический выбор, осуществляемый системой исполнения. Такова будет роль динамического связывания (dynamic binding), ключевой составляющей ОО-подхода, которая подробно будет рассматриваться при обсуждении наследования. (См. "Динамическое связывание" ("Dynamic binding"), лекция 14)

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

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

[x]. Таблицы, организуемые по некоторой схеме хеширования.

[x]. Таблицы, организуемые как некоторая разновидность деревьев.

[x]. Таблицы, организуемые последовательно.

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

Рис. 4.1.  Некоторые возможные реализации таблицы

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

has (t: SEQUENTIAL_TABLE; x: ELEMENT): BOOLEAN is

-- Содержится ли x в последовательной таблице t?

do

from start until

after or else found (x)

loop

forth

end

Result := not after

end

Это представление основано на использовании четырех подпрограмм, которые должны иметься в любой последовательной реализации таблицы(Подробно методика работы с курсором будет рассмотрена в лекции 5 курса "Основы объектно-ориентированного проектирования""Активные структуры данных" ("Active data structures"). ):

[x]. start (начать) , переместить курсор к первому элементу, если он имеется.

[x]. forth (следующий) , переместить курсор к следующей позиции.

[x]. after (после) , булев запрос, переместился ли курсор за последний элемент.

[x]. found (x) , булев запрос, возвращающий true, когда курсор указывает на элемент, имеющий значение x.

Рис. 4.2.  Последовательная структура с курсором

Несмотря на сходство с шаблоном подпрограммы, использованным в начале этого обсуждения, новый текст - это уже не шаблон, это настоящая подпрограмма, написанная в непосредственно исполняемой нотации (такая нотация используется в лекциях 7-18 этого курса). Если задать реализации для четырех операций start, forth, after и found, то можно откомпилировать и выполнить последнюю версию has.

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

В первом из них используется массив из capacity элементов, и таблица занимает позиции от 1 до count + 1. (Последнее значение необходимо в случае, когда курсор переместился на позицию после ("after") последнего элемента.)

Рис. 4.3.  Представление последовательной таблицы с курсором на основе массива

Во втором представлении используется связный список, в котором доступ к первому элементу обеспечивается по ссылке first_cell и каждый элемент связан со следующим по ссылке right. При этом курсор можно представить ссылкой cursor.

Рис. 4.4.  Представление последовательной таблицы с курсором на основе связного списка

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

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

Реализация операций start, forth, after и found будет разной для каждого из вариантов. В следующей таблице4.3) показана реализация для каждого случая. Здесь t @ i означает i-й элемент массива t, который записывается как t [i] в языках Pascal или C; Void означает "пустую" ссылку; обозначение f- языка Pascal, для файла f, означает элемент в текущей позиции чтения из файла.

start forth after found (x) Массив i :=1 i :=i + 1 i >count t @ i =x Связный список c := first_cell c :=c. right c =Void c. item =x Файл rewind read end_of_file f -=x

Таблица 4.1.Классы и методы

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

Все варианты последовательной таблицы совместно используют функцию has, и отличаются только реализацией операций. Хорошее решение проблемы повторного использования требует, чтобы в такой ситуации текст has находился бы лишь в одном месте, связанном с общим понятием последовательной таблицы. Для описания каждого нового варианта не нужно больше беспокоиться о подпрограмме has; требуется лишь подготовить подходящие версии start, forth, after и found.

Наряду с требованиями к модульности, изложенными в предыдущей лекции, пять требований Изменчивости Типов, Группирования Подпрограмм, Изменчивости Реализаций, Независимости Представлений и Факторизации Общего Поведения определяют, чего следует ожидать от наших повторно используемых компонентов - абстрактных модулей.

Рассмотрим решения, предшествовавшие ОО-подходу, чтобы понять, что нас не устраивает, и что следует взять с собой в ОО-мир.

Классический подход к повторному использованию состоит в том, чтобы создавать библиотеки подпрограмм. Здесь термин подпрограмма (routine) означает программный элемент, который может быть вызван другими элементами для выполнения некоторого алгоритма, используя некоторые входные данные, создавая некоторые выходные данные, и, возможно, модифицируя другие данные. Вызывающий элемент передает свои входные данные (а иногда - выходные данные и модифицируемые данные) в виде фактических аргументов (actual arguments) . Подпрограмма может также возвращать выходные данные в виде результата; в этом случае она называется функцией.