DIRECTORY
Alloc: TYPE USING [Handle, Notifier, AddNotify, DropNotify],
Tree: TYPE USING [Base, Index, Link, Scan, Null, NullIndex, treeType],
TreeOps: TYPE USING [];
endIndex: Tree.Index = Tree.Index.LAST;
endMark: Tree.Link = [subtree[index: endIndex]];
tb: PRIVATE Tree.Base; -- tree base
UpdateBase: Alloc.Notifier = {tb ← base[Tree.treeType]};
Initialize:
PUBLIC
PROC [Alloc.Handle,
UNCOUNTED
ZONE] = {
Alloc.AddNotify[NIL, UpdateBase]};
Finalize: PUBLIC PROC = {Alloc.DropNotify[NIL, UpdateBase]};
ScanSons:
PUBLIC
PROC [root: Tree.Link, action: Tree.Scan] = {
IF root # Tree.Null
THEN
WITH root
SELECT
FROM
subtree => {
node: Tree.Index = index;
FOR i:
CARDINAL
IN [1 .. SonCount[node]]
DO
action[tb[node].son[i]] ENDLOOP};
ENDCASE;
RETURN};
SonCount:
PROC [node: Tree.Index]
RETURNS [
CARDINAL] = {
RETURN [
SELECT node
FROM
Tree.NullIndex, endIndex => 0,
ENDCASE =>
IF tb[node].name = $list
AND tb[node].nSons = 0
THEN ListLength[[subtree[index: node]]] + 1
ELSE tb[node].nSons]};
ListLength:
PUBLIC
PROC [t: Tree.Link]
RETURNS [
CARDINAL] = {
IF t = Tree.Null THEN RETURN [0];
WITH t
SELECT
FROM
subtree => {
node: Tree.Index = index;
n: CARDINAL;
IF tb[node].name # $list THEN RETURN [1];
n ← tb[node].nSons;
IF n # 0 THEN RETURN [n];
FOR i:
CARDINAL ← 1, i+1
UNTIL tb[node].son[i] = endMark
DO
n ← n+1 ENDLOOP;
RETURN [n]};
ENDCASE => RETURN [1]};
GetNode:
PUBLIC
PROC [t: Tree.Link]
RETURNS [Tree.Index] = {
RETURN [NARROW[t, Tree.Link.subtree].index]};
}.