Пассивные классы
Ясно, что нам нужны два класса: LINKED_LIST для списка (более точно, заголовка списка), LINKABLE для элементов списка - звеньев. Оба они являются универсальными.
Понятие LINKABLE является основой реализации, но не столь важно для большинства клиентов. Следует позаботиться об интерфейсе, обеспечивающем модули клиентов нужными примитивами, но не следует беспокоить их такими деталями реализации как представление элементов в звене списка. Атрибуты, соответствующие рисунку, появятся как:
indexing description: "Звенья, используемые в связном списке" note: "Частичная версия, только атрибуты" class LINKABLE1 [G] feature {LINKED_LIST} item: G -- Значение звена right: LINKABLE [G] -- Правый сосед endТип right можно было бы задавать как like Current, но предпочтительнее на этом этапе сохранить больше свободы в переопределении, поскольку пока непонятно, что может потребовать изменений у потомков LINKABLE.
Для получения настоящего класса следует добавить подпрограммы. Что допустимо для клиентов при работе со звеньями? Они могут изменять поля item и right. Можно также ожидать, что многие из клиентов захотят при создании звена инициализировать его значение, что требует процедуры создания. Вот подходящая версия класса:
indexing description: "Звенья, используемые в связном списке" class LINKABLE [G] creation make feature {LINKED_LIST} item: G -- Значение звена right: LINKABLE [G] -- Правый сосед make (initial: G) is -- Инициализация item значением initial do put (initial) end put (new: G) is -- Замена значения на new do item := new end put_right (other: LINKABLE [G]) is -- Поместить other справа от текущего звена do right := other end endДля краткости в классе опущены очевидные постусловия процедуры (такие как ensure item = initial для make). Предусловий здесь нет.
Ну, вот и все о LINKABLE. Теперь рассмотрим сам связный список, внутренне доступный через заголовок. Рассмотрим его экспортируемые компоненты: запрос на получение числа элементов (count), пуст ли список (empty), значение элемента по индексу i(item), вставка нового элемента в определенную позицию (put), изменение значения i-го элемента (replace), поиск элемента с заданным значением (occurrence).
Нам также понадобится запрос, возвращающий ссылку на первый элемент (void, если список пуст), который не должен экспортироваться.
Вот набросок первой версии. Некоторые тела подпрограмм опущены.
indexing description: "Односвязный список" note: "Первая версия, пассивная" class LINKED_LIST1 [G] feature -- Access count: G empty: BOOLEAN is -- Пуст ли список? do Result := (count = 0) ensure empty_if_no_element: Result = (count = 0) end item (i: INTEGER): G is -- Значение i-го элемента require 1 <= i; i <= count local elem: LINKABLE [G]; j: INTEGER do from j := 1; elem := first_element invariant j <= i; elem /= Void variant i - j until j = i loop j := j + 1; elem := elem.right end Result := elem.item end occurrence (v: G): INTEGER is -- Позиция первого элемента со значением v (0, если нет) do ... end feature -- Element change put (v: G; i: INTEGER) is -- Вставка нового элемента со значением v, -- так что он становится i-м элементом require 1 <= i; i <= count + 1 local previous, new: LINKABLE [G]; j: INTEGER do -- Создание нового элемента create new.make (v) if i = 1 then -- Вставка в голову списка new.put (first_element); first_element := new else from j := 1; previous := first_element invariant j >= 1; j <= i - 1; previous /= Void -- previous - это j-й элемент списка variant i - j - 1 until j = i - 1 loop j := j + 1; previous := previous.right end Вставить после previous previous.put_right (new) new.put_right (previous.right) end count := count + 1 ensure one_more: count = old count + 1 not_empty: not empty inserted: item (i) = v -- For 1 <= j < i, -- элемент с индексом j не изменил свое значение -- For i < j <= count, -- элемент с индексом j изменил свое значение -- на то, которое элемент с индексом j - 1 -- имел перед вызовом end replace (i: INTEGER; v: G) is -- Заменить на v значение i-го элемента require 1 <= i; i <= count do ... ensure replaced: item (i) = v end feature -- Removal prune (i: INTEGER) is -- Удалить i-й элемент require 1 <= i; i <= count do ...ensure one_less: count = old count - 1 end ... Другие компоненты ... feature {LINKED_LIST} -- Implementation first_element: LINKABLE [G] invariant empty_definition: empty = (count = 0) empty_iff_no_first_element: empty = (first_element = Void) end
Это хорошая идея попытаться самому закончить определение occurrence, replace и prune в этой первой версии. Убедитесь при этом, что поддерживается истинность инварианта.
