Представление списка истории
Для списка истории был задан абстрактный тип 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