Главная » Java, Структуры данных и алгоритмы » Модель проектирования «локатор»

0

Как видно на примере списков и бинарных деревьев, абстрактная позиционная информация в контейнере представляет собой достаточно мощное инструментальное средство. АТД «позиция», описанный в п. 5.2.2, позволяет обнаружить специфическое место,в контейнере, способное хранить элемент. Хранящийся в этом месте элемент может быть изменен, например, операцией swapElements, но само место не изменяется. В разделе 5.4 приводились способы применения позиций в реализациях алгоритмов упорядочивания. Существуют приложения, в которых необходимо отслеживать движение элементов внутри позиционного контейнера. Предположим, требуется удалить элемент е из последовательности S. Методы удаления из АТД «последовательность» требуют указать либо позицию, либо ранг е в S. Если после ввода е последовательность S модифицируется серией операций swapElements, то элемент е оказывается в позиции, отличной от той, в которую он был введен. Значит, чтобы удалить элемент е, понадобится найти е в последовательности S (затратив время, в крайнем случае пропорциональное размерности -5), что не всегда удобно. Естественно, предпочтительнее иметь механизм отслеживания позиций элементов в контейнере.

Проектной моделью, отвечающей этому требованию, является локатор (locator). Локатор представляет собой механизм хранения и обновления ассоциаций между элементами и их текущими позициями в контейнере. Локатор «цепляется» к элементу и сопровождает его даже при изменении позиции в контейнере. Локатор выступает в качестве бирки, которую мы получаем при сдаче пальто в гардероб и возвращая которую, получаем пальто обратно. Относительное положение нашего пальто может меняться, как и других пальто, которые могут добавляться или удаляться, но с нашей биркой всегда получим наше пальто. Итак, главное, что следует знать о локаторе — он всегда следует за объектом, даже если тот меняет свое место.

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

Другим важным назначением локаторов является отслеживание объектов, хранящихся в контейнере, операции которого применимы не к позициям, а исключительно к ключам и элементам, как в приоритетной очереди. В принципе модель проектирования «локатор» обеспечивает

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

Как абстрактный тип данных, локатор / поддерживает следующие методы:

element(): возвращает элемент объекта, ассоциируемого с /.

Input: отсутствует; Output: объект.

кеу(): возвращает ключ объекта, ассоциируемого с /.

Input: отсутствует; Output: объект.

Для конкретизации обсудим способ применения локаторов, расширяющий перечень операций АТД «очередь с приоритетами» для введения дополнительных методов возврата локаторов и их использования как аргументов.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии