Пассивные классы

Ясно, что нам нужны два класса: 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 в этой первой версии. Убедитесь при этом, что поддерживается истинность инварианта.