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


Слияние списка и стражей - часть 3


Проблема, конечно, была в том, что first_element мог иметь значение void для пустого списка, что принуждало во все алгоритмы встраивать тесты в форме if before then ... Мы точно не хотим возвращаться назад к этой ситуации. Но можем использовать концептуальную модель, показанную на рисунке, избавленную от стража

Заголовок как страж (на непустом списке)

Рис. 5.13.  Заголовок как страж (на непустом списке)

Концептуально решение является тем же самым, что и прошлое, с заменой zeroth_element ссылкой на сам заголовок списка. Для представления того, что ранее было zeroth_element.right, теперь используется first_element.

Заголовок как страж (на пустом списке)

Рис. 5.14.  Заголовок как страж (на пустом списке)

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

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

previous /= Void (active = Void) = after; (active = previous) = before (not before) implies (previous.right = active) is_last = ((active /= Void) and then (active.right = Void))

Предложения, включающие ранее zeroth_element:

zeroth_element /= Void empty = (zeroth_elemenеt.right = Void) (previous = zeroth_element) = (before or is_first)

теперь будут иметь вид:

first_element /= Void empty = (first_element = Current) (previous = Current) = (before or is_first)

Но чтобы все получилось так просто, необходимо (нас ждут опасные вещи, поэтому пристегните ремни) сделать LINKED_LIST наследником LINKABLE:

class LINKED_LIST [G] inherit LINKABLE [G] rename right as first_element, put_right as set_first_element end ...Остальное в классе остается как ранее с выше показанной заменой zeroth_element...

Не нонсенс ли это - позволить LINKED_LIST быть наследником LINKABLE? Совсем нет! Вся идея в том, чтобы слить воедино два понятия заголовка списка и стража, другими словами рассматривать заголовок списка как элемент списка. Поэтому мы имеем прекрасный пример отношения "is-a" ("является") при наследовании.


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



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