Без дженериков можно жить

[ilovb]

Интерфейс абстрактного типа данных:

Код: [Выделить]

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 пока не показываю, так как оно еще в процессе обдумывания/модификации/отладки/тестирования

[valexey_u]

Что мне помешает положить в это дерево два элемента разных типов?

[valexey_u]

Поясню - с точки зрения адепта динамической типизации, в Обероне и в КП действительно без дженериков жить вполне можно. Цена тому - динамическая типизация.

С точки зрения адепта статической типизации, без дженериков жить нельзя.

[ilovb]

Что мне помешает положить в это дерево два элемента разных типов?

Попробуй

ps Возможно интерфейс где и протекает, но вот на вскидку не вижу.

[ilovb]

Пояснения к интерфейсу:
Типы:
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)
Все методы возвращают статус своего завершения.
Также бегунок можно дополнить своими полями, и сделать их заполнение при перемещении.

[ilovb]

Еще планирую добавить выборку среза по условиям >, <, 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 можно вполне удобно жить. Нужно просто делать человечий интерфейс у коллекции.

[ilovb]

с помощью комбинации  Find, Next/Last

Фу ты блин. Не Last, а Prev конечно.

[ilovb]

Замечу что выборку на >=, <= можно делать с помощью комбинации  Find, Next/Last

Хотя нет, туплю. Нельзя так. Нужно тоже добавлять такую возможность отдельно.

[Илья Ермаков]

Борис, поздравляю, идёшь путём, который, видимо, оптимален в КП (доступ к данным через бегунок и т.п.)

IF rd.Find(d) THEN
   REPEAT
      Log.Int(d.key);
   UNTIL ~rd.Next(d);
END;

Не понимаю только, почему ты не пошёл стандартным для КП-шной экосистемы паттерном, когда значение об успехе после операции кладётся в бегунок.ok (т.к. "жена, оружие, ложка и бегунок есть орудия индвидуальные", то никаких проблем для многопоточности нет) - и используется схема бег.ПопробоватьВзятьПервый; ПОКА бег.успех ДЕЛАТЬ ... бег.ПопробоватьВзятьСледующий; КОН (иногда первый и следующий берутся одинаково, но дублирование не должно смущать - действие делается на 1 раз больше, чем повтор других действий в цикле, значит место добавочному разу как раз вне цикла).

[Valery Solovey]

форыч с итераторами тоже нинужен. С WHILE можно вполне удобно жить. Нужно просто делать человечий интерфейс у коллекции.

Райдер - это и есть итератор : ).

[ilovb]

По сути да 

Просто когда говорят "итератор", то у меня сразу ассоциация с чем-то неявным и форычем. Как в Lua например:

Код: [Выделить]

for item in string.gmatch(line,"%w+") do
      array[i] = item;
      i = i +1
end
А бегунок у меня прочно с курсором (СУБД) ассоциируется. Тут уже все явно. Получаешь курсор и вызываешь его методы.

[ilovb]

Не понимаю только, почему ты не пошёл стандартным для КП-шной экосистемы паттерном, когда значение об успехе после операции кладётся в бегунок.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;