Пояснения к интерфейсу:
Типы:
AdtRBTrees.Node
AdtRBTrees.Tree
абстрактные, т.е. разместить их нельзя.
Для использования нужно доопределить:
Tree, Node - дополнить своими полями
Что будет храниться в Node зависит от юзера. Можно определить не как в примере выше, а так, например:
Node* = POINTER TO RECORD (RBTrees.Node)
key: INTEGER;
val: ARRAY 50 OF CHAR;
END;
Также нужно определить мессагу Data и реализовать процедуры:
(n: Node) GetData- (VAR data: AdtRBTrees.Data), NEW, ABSTRACT;
(n: Node) SetData- (IN data: AdtRBTrees.Data), NEW, ABSTRACT
Так как уточнять тип параметров запрещено, то придется внутри этих процедур делать охрану типа (WITH). Т.е. юзер полностью контролирует, что кладется в ноду, и как кладется.
Эти процедуры извне недоступны (как и Node) Их юзает AdtRBTrees.Tree в определяющем модуле.
Положить в ноду неизвестный тип невозможно, т.к. нельзя написать без WITH, а исходный тип Data не имеет полей.
Мессагу Data тоже можно определять на свое усмотрение (как удобно).
Кроме того нужно реализовать (node: Node) Compare- (IN data: AdtRBTrees.Data): INTEGER; (извне недоступна, так как нет доступа к Node)
Еще нужно реализовать CopyFrom (но ее я планирую выпилить)
У дерева нужно реализовать (tree: Tree) NewNode- (): Node; чтобы дерево размещало ноды, определенные юзером (используется внутри AdtRBTrees.Tree)
Использование:
У Tree два метода:
(tree: Tree) Delete (IN data: Data);
(tree: Tree) Insert (IN data: Data);
Назначение думаю понятно. Работа осуществляется посредством мессаги, и внутри через SetData, GetData. Попытка засунуть неизвестный тип вызовет исключение.
Поиск в дереве и обход элементов осуществляется посредством бегунка (Rider).
Бегунку пофиг к какому дереву его присоединили и какие данные в дереве содержатся.
Поля:
tree - дерево, к которому присоединен бегунок
linked - состояние бегунка (связан с нодой или нет)
Методы:
Find (VAR data: Data): BOOLEAN - находит ноду, перемещает на нее бегунок и извлекает данные.
Next(data) и Prev(data) работают в зависимости от состояния бегунка (linked)
Если бегунок связан с нодой, то происходит перемещение и извлекаются данные.
В противном случае бегунок встает либо на первую ноду дерева (Next), либо на последнюю(Prev).
Reset - отвязывает бегунок от ноды (linked := FALSE)
Все методы возвращают статус своего завершения.
Также бегунок можно дополнить своими полями, и сделать их заполнение при перемещении.