Представление списка истории

Для списка истории был задан абстрактный тип SOME_LIST, обладающий компонентами: put, empty, before, is_first,is_last, back, forth, item и remove_all_right. (Есть также on_item, выраженный в терминах empty и before, иnot_last, выраженный в терминах empty и is_last.)

Большинство из списочных классов базовой библиотеки можно использовать для реализации SOME_LIST; например, классTWO_WAY_LIST или одного из потомков класса CIRCULAR_LIST. Для получения независимой версии рассмотрим специально подобранный класс BOUNDED_LIST. В отличие от ссылочной реализации списков, подобных TWO_WAY_LIST, этот класс основан на массиве, так что он хранит лишь ограниченное число команд в истории. Пусть remembered будет максимальным числом хранимых команд. Если используется в системе подобное свойство, то запомните (если не хотите получить гневное письмо от меня как от пользователя вашей системы): этот максимум должен задаваться пользователем либо во время сессии, либо в профиле пользователя. По умолчанию он должен выбираться никак не менее 20.

Список BOUNDED_LIST может использовать массив с циклическим управлением, позволяющий использовать ранее занятые элементы, когда число команд переваливает за максимум remembered. Эта техника является общей для представления ограниченных очередей. Массив в этом случае представляется в виде баранки:

Рис. 3.6. Ограниченный циклический список, реализуемый массивом

Размером capacity массива является remembered + 1; это соглашение означает фиксирование одной из позиций (последней с индексом capacity), оно необходимо для различения пустого и полностью заполненного списка. Занятые позиции помечены двумя целочисленными атрибутами: oldest - является позицией самой старой запомненной команды, и next - первая свободная позиция (для следующей команды). Атрибут index указывает текущую позицию курсора.

Вот как выглядит реализация компонентов. Для put(c), вставляющей команду c в конец списка, имеем:

representation.put (x, next);

--где representation это имя массива

next:= (next\\ remembered) + 1

index:= next

где операция \\ представляет остаток от деления нацело. Значение empty истинно, если и только если next = oldest; значение is_first истинно, если и только если index = oldest; и before истинно, если и только если (index\\ remembered) + 1 = oldest. Телом forth является:

index:= (index\\ remembered) + 1

а телом back:

index:= ((index + remembered - 2) \\ remembered) + 1

Терм +remembered математически избыточен, но он включен из-за отсутствия стандартного соглашения для операции взятия остатка в случае отрицательных операндов.

Запрос item возвращает элемент в позиции курсора - representation @ index, - элемент массива с индексом index. Наконец, процедура remove_all_right, удаляющая все элементы справа от курсора, реализована так:

next:= (index remembered) + 1

Дата добавления: 2014-12-07