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


Взгляд изнутри - часть 2


Обращаться с ними нужно довольно деликатно, в утешение можно заметить, что лишь небольшая их часть - start, forth, put_right, put_left и remove, - выполняет нетривиальные операции над ссылками. Давайте начнем с команд start и forth. Процедура start должна работать как с пустым, так и с не пустым списком. Для пустого списка соглашение состоит в том, что start передвигает курсор ко второму стражу.

start1 is -- Передвигает курсор к первой позиции. -- (Предварительная версия.) do index := 1 previous := Void active := first_element ensure moved_to_first: index = 1 empty_convention: empty implies after end forth1 is -- Передвигает курсор к следующей позиции. -- (Предварительная версия.) require not_after: not after do index := index + 1 if before then active := first_element; previous := Void else check active /= Void end previous := active; active := active.right end ensure moved_by_one: index = old index + 1 end



Пора остановиться! Все становится слишком сложным и неэффективным. Производительность процедуры forth является критической, поскольку типично она используется клиентом в цикле from start until after loop ...; forth end. Можно ли избавиться от теста?

Можно, если всерьез рассматривать левого стража и всегда создавать его одновременно с созданием списка. (Процедура создания make для LINKED_LIST остается в качестве упражнения.) Заменим first_element ссылкой zeroth_element на левого стража:

Представление списка с курсором (пересмотренная версия)

Рис. 5.11.  Представление списка с курсором (пересмотренная версия)

Свойства zeroth_element /= Void и previous /= Void будут теперь частью инварианта (следует, конечно, убедиться, что процедура создания обеспечивает его выполнение). Они весьма ценны, поскольку позволяют избавиться от многих повторяемых проверок.

Процедура forth, запускаемая после обновленной процедуры start, теперь проще и быстрее (без проверок!):

start is -- Передвигает курсор к первой позиции do index := 1 previous := zeroth_element active := previous.right ensure moved_to_first: index = 1 empty_convention: empty implies after previous_is_zeroth: previous = zeroth_element end forth is -- Передвинуть курсор к следующей позиции. -- (Версия пересмотрена в интересах эффективности.


Начало  Назад  Вперед



Книжный магазин