Oberon space
General Category => Общий раздел => Тема начата: ilovb от Ноябрь 16, 2013, 04:51:47 pm
-
Интерфейс абстрактного типа данных:
DEFINITION AdtRBTrees;
TYPE
Node = POINTER TO ABSTRACT RECORD
(n: Node) Compare- (IN data: Data): INTEGER, NEW, ABSTRACT;
(n: Node) CopyFrom- (other: Node), NEW, ABSTRACT;
(n: Node) GetData- (VAR data: Data), NEW, ABSTRACT;
(n: Node) SetData- (IN data: Data), NEW, ABSTRACT
END;
Rider = POINTER TO EXTENSIBLE RECORD
tree-: Tree;
linked-: BOOLEAN;
(rd: Rider) Connect (tree: Tree), NEW;
(rd: Rider) Find (IN data: Data): BOOLEAN, NEW;
(rd: Rider) Next (VAR data: Data): BOOLEAN, NEW;
(rd: Rider) Prev (VAR data: Data): BOOLEAN, NEW;
(rd: Rider) Reset, NEW
END;
Tree = POINTER TO ABSTRACT RECORD
(tree: Tree) Delete (IN data: Data), NEW;
(tree: Tree) Insert (IN data: Data), NEW;
(t: Tree) NewNode- (): Node, NEW, ABSTRACT
END;
Data = EXTENSIBLE RECORD END;
END AdtRBTrees.
Цена вопроса:
MODULE AdtTest;
IMPORT
RBTrees := AdtRBTrees, Log;
TYPE
Tree* = POINTER TO RECORD (RBTrees.Tree) END;
Rider* = POINTER TO RECORD (RBTrees.Rider) END;
Node* = POINTER TO RECORD (RBTrees.Node)
data*: Data;
END;
Data* = RECORD (RBTrees.Data)
key*: INTEGER;
END;
PROCEDURE (tree: Tree) NewNode- (): Node;
VAR node: Node;
BEGIN
NEW(node);
RETURN node;
END NewNode;
PROCEDURE (node: Node) CopyFrom- (other: RBTrees.Node);
BEGIN
WITH other: Node DO
node.data := other.data;
END;
END CopyFrom;
PROCEDURE (node: Node) SetData- (IN data: RBTrees.Data);
BEGIN
WITH data: Data DO
node.data := data;
END;
END SetData;
PROCEDURE (node: Node) GetData- (VAR data: RBTrees.Data);
BEGIN
WITH data: Data DO
data := node.data;
END;
END GetData;
PROCEDURE (node: Node) Compare- (IN data: RBTrees.Data): INTEGER;
VAR
res: INTEGER;
BEGIN
WITH data: Data DO
IF node.data.key > data.key THEN
res := 1;
ELSIF node.data.key < data.key THEN
res := -1;
ELSE
res := 0;
END;
END;
RETURN res;
END Compare;
PROCEDURE Do*;
VAR
t: Tree;
d: Data;
rd: Rider;
i: INTEGER;
BEGIN
NEW(t); NEW(rd); rd.Connect(t);
FOR i := 10 TO 1 BY -1 DO
d.key := i;
t.Insert(d);
END;
WHILE rd.Next(d) DO
Log.Int(d.key);
END;
WHILE rd.Prev(d) DO
Log.Int(d.key);
END;
END Do;
BEGIN
END AdtTest.Do
Прошу обратить внимание, что модуль поддается банальному копипасту и последующей модификации:
Data* = RECORD (RBTrees.Data)
key*: INTEGER;
END;
и
PROCEDURE (node: Node) Compare- (IN data: RBTrees.Data): INTEGER;
VAR
res: INTEGER;
BEGIN
WITH data: Data DO
IF node.data.key > data.key THEN
res := 1;
ELSIF node.data.key < data.key THEN
res := -1;
ELSE
res := 0;
END;
END;
RETURN res;
END Compare;
Реализацию AdtRBTrees пока не показываю, так как оно еще в процессе обдумывания/модификации/отладки/тестирования
-
Что мне помешает положить в это дерево два элемента разных типов?
-
Поясню - с точки зрения адепта динамической типизации, в Обероне и в КП действительно без дженериков жить вполне можно. Цена тому - динамическая типизация.
С точки зрения адепта статической типизации, без дженериков жить нельзя.
-
Что мне помешает положить в это дерево два элемента разных типов?
Попробуй :)
ps Возможно интерфейс где и протекает, но вот на вскидку не вижу.
-
Пояснения к интерфейсу:
Типы:
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)
Все методы возвращают статус своего завершения.
Также бегунок можно дополнить своими полями, и сделать их заполнение при перемещении.
-
Еще планирую добавить выборку среза по условиям >, <, IN(first, last) (first<{...}<last)
Замечу что выборку на >=, <= можно делать с помощью комбинации Find, Next/Last
Пример выборки элементов (key >= 3)
d.key := 3;
IF rd.Find(d) THEN
REPEAT
Log.Int(d.key);
UNTIL ~rd.Next(d);
END;
Еще один внезапный для меня вывод: форыч с итераторами тоже нинужен. С WHILE можно вполне удобно жить. Нужно просто делать человечий интерфейс у коллекции.
-
с помощью комбинации Find, Next/Last
Фу ты блин. Не Last, а Prev конечно.
-
Замечу что выборку на >=, <= можно делать с помощью комбинации Find, Next/Last
Хотя нет, туплю. Нельзя так. Нужно тоже добавлять такую возможность отдельно.
-
Борис, поздравляю, идёшь путём, который, видимо, оптимален в КП (доступ к данным через бегунок и т.п.)
IF rd.Find(d) THEN
REPEAT
Log.Int(d.key);
UNTIL ~rd.Next(d);
END;
Не понимаю только, почему ты не пошёл стандартным для КП-шной экосистемы паттерном, когда значение об успехе после операции кладётся в бегунок.ok (т.к. "жена, оружие, ложка и бегунок есть орудия индвидуальные", то никаких проблем для многопоточности нет) - и используется схема бег.ПопробоватьВзятьПервый; ПОКА бег.успех ДЕЛАТЬ ... бег.ПопробоватьВзятьСледующий; КОН (иногда первый и следующий берутся одинаково, но дублирование не должно смущать - действие делается на 1 раз больше, чем повтор других действий в цикле, значит место добавочному разу как раз вне цикла).
-
форыч с итераторами тоже нинужен. С WHILE можно вполне удобно жить. Нужно просто делать человечий интерфейс у коллекции.
Райдер - это и есть итератор : ).
-
По сути да :)
Просто когда говорят "итератор", то у меня сразу ассоциация с чем-то неявным и форычем. Как в Lua например:
for item in string.gmatch(line,"%w+") do
array[i] = item;
i = i +1
end
А бегунок у меня прочно с курсором (СУБД) ассоциируется. Тут уже все явно. Получаешь курсор и вызываешь его методы.
-
Не понимаю только, почему ты не пошёл стандартным для КП-шной экосистемы паттерном, когда значение об успехе после операции кладётся в бегунок.ok (т.к. "жена, оружие, ложка и бегунок есть орудия индвидуальные", то никаких проблем для многопоточности нет) - и используется схема бег.ПопробоватьВзятьПервый; ПОКА бег.успех ДЕЛАТЬ ... бег.ПопробоватьВзятьСледующий; КОН (иногда первый и следующий берутся одинаково, но дублирование не должно смущать - действие делается на 1 раз больше, чем повтор других действий в цикле, значит место добавочному разу как раз вне цикла).
Мне такой подход просто кажется более простым и удобным. Возможно тебе такая логика непривычна, но у меня это уже в подкорке, т.к. я повторил поведение курсоров 1С :)
Выборка = Запрос.Выбрать();
Пока Выборка.Следующий() Цикл
Сообщить(Выборка.Ключ);
КонецЦикла;
С RBTree будет так:
rd.Connect(t);
WHILE rd.Next(d) DO
Log.Int(d.key);
END;
Принцип: Получил курсор и побежал (в любом направлении)
После присоединения курсора к дереву rd.linked = FALSE, это значит, что первый вызов Next/Prev переместит курсор на первый/последний элемент и прочитает его данные.
Никаких лишних телодвижений для установки курсора на первый/последний элемент не нужно. По окончании цикла опять rd.linked = FALSE, и можно снова обходить коллекцию в любом направлении, и тоже без лишних телодвижений.
Т.е. получается что-то вроде форыча, но мощнее. Так как можно прервать цикл (rd.linked = TRUE) и курсор останется на этой позиции, т.е. можно будет продолжить обход в любом направлении уже с этой позиции. То же самое с Find().
Если курсор связан с нодой, а нам нужно начать обход с первого/последнего элемента, то вызываем Reset() (rd.linked := FALSE)
Отдельное получение первого/последнего элемента слишком редкие операции, чтобы жертвовать ради них удобным обходом. И кроме того реализовать их очень легко:
PROCEDURE (rd: Rider) First (VAR data: Data): BOOLEAN, NEW;
BEGIN
rd.Reset();
RETURN rd.Next(data);
END First;