DIRECTORY
PPLeaves USING [HTIndex, ISEIndex],
PPTree USING [AttrId, Id, Handle, Link, Map, Node, NodeName, Scan, SonId, Test, Null, NullHandle],
PPTreeOps USING [];
PPTreeImpl:
CEDAR
PROGRAM
EXPORTS PPTreeOps =
BEGIN OPEN PPLeaves, Tree: PPTree;
initialized: BOOL ← FALSE;
StackIncr: CARDINAL = 32;
LinkStack: TYPE = RECORD [SEQUENCE size: NAT OF Tree.Link];
stack: REF LinkStack ← NIL;
sI: NAT;
Initialize:
PUBLIC
PROC = {
IF initialized THEN Finalize[];
stack ← AllocStack[StackIncr];
sI ← 0;
initialized ← TRUE};
Reset:
PUBLIC
PROC = {
IF initialized
AND stack.size > 2*StackIncr
THEN stack ← AllocStack[StackIncr]};
Finalize: PUBLIC PROC = {initialized ← FALSE};
AllocStack:
PROC [size:
NAT, forceNew:
BOOL ←
FALSE]
RETURNS [st:
REF LinkStack] = {
st ← IF forceNew THEN NIL ELSE stack;
IF st = NIL OR st.size < size THEN st ← NEW[LinkStack[size]];
};
ExpandStack:
PROC = {
newStack: REF LinkStack = AllocStack[stack.size+StackIncr, TRUE];
FOR i: NAT IN [0 .. stack.size) DO newStack[i] ← stack[i] ENDLOOP;
stack ← newStack};
PushTree:
PUBLIC
PROC [v: Tree.Link] = {
IF sI >= stack.size THEN ExpandStack[];
stack[sI] ← v; sI ← sI+1};
PopTree: PUBLIC PROC RETURNS [Tree.Link] = {RETURN [stack[sI←sI-1]]};
InsertTree:
PUBLIC
PROC [v: Tree.Link, n:
NAT] = {
i: NAT ← sI;
IF sI >= stack.size THEN ExpandStack[];
sI ← sI+1;
THROUGH [1 .. n) DO stack[i] ← stack[i-1]; i ← i-1 ENDLOOP;
stack[i] ← v};
ExtractTree:
PUBLIC
PROC [n:
NAT]
RETURNS [v: Tree.Link] = {
i: NAT ← sI - n;
v ← stack[i];
THROUGH [1 .. n) DO stack[i] ← stack[i+1]; i ← i+1 ENDLOOP;
sI ← sI - 1;
RETURN};
MakeNode:
PUBLIC
PROC [name: Tree.NodeName, count:
INTEGER]
RETURNS [Tree.Link] = {
PushNode[name, count]; RETURN [PopTree[]]};
MakeList:
PUBLIC
PROC [size:
INTEGER]
RETURNS [Tree.Link] = {
PushList[size]; RETURN [PopTree[]]};
PushNode:
PUBLIC
PROC [name: Tree.NodeName, count:
INTEGER] = {
nSons: NAT = ABS[count];
node: Tree.Handle = NEW[Tree.Node[nSons] ← [name:name, son:]];
IF count >= 0
THEN
FOR i: Tree.SonId
DECREASING
IN [1..nSons]
DO node.son[i] ← stack[sI←sI-1] ENDLOOP
ELSE
FOR i: Tree.SonId
IN [1..nSons]
DO node.son[i] ← stack[sI←sI-1] ENDLOOP;
IF sI >= stack.size THEN ExpandStack[];
stack[sI] ← node; sI ← sI+1};
PushList:
PUBLIC
PROC [size:
INTEGER] = {
nSons: NAT = ABS[size];
SELECT nSons
FROM
1 => NULL;
0 => PushTree[Tree.Null];
ENDCASE => {
node: Tree.Handle = NEW[Tree.Node[nSons] ← [name: list, son:]];
IF size > 0
THEN
FOR i: Tree.SonId
DECREASING
IN [1..nSons]
DO node.son[i] ← stack[sI←sI-1] ENDLOOP
ELSE
FOR i: Tree.SonId
IN [1..nSons]
DO node.son[i] ← stack[sI←sI-1] ENDLOOP;
IF sI >= stack.size THEN ExpandStack[];
stack[sI] ← node; sI ← sI+1}};
PushProperList:
PUBLIC
PROC [size:
INTEGER] = {
IF size
NOT
IN [-1..1]
THEN PushList[size]
ELSE {
node: Tree.Handle = NEW[Tree.Node[ABS[size]] ← [name: list, son:]];
IF size # 0 THEN node.son[1] ← PopTree[];
PushTree[node]}};
SetInfo:
PUBLIC
PROC [info:
CARDINAL] = {
v: Tree.Link = stack[sI-1];
WITH v
SELECT
FROM
node: Tree.Handle => node.info ← info;
ENDCASE => ERROR};
SetAttr:
PUBLIC
PROC [which: Tree.AttrId, value:
BOOL] = {
v: Tree.Link = stack[sI-1];
WITH v
SELECT
FROM
node: Tree.Handle => node.attr[which] ← value;
ENDCASE => ERROR};
procedures for tree testing
GetHash:
PUBLIC
PROC [t: Tree.Link]
RETURNS [HTIndex] = {
RETURN [WITH t SELECT FROM id: HTIndex => id, ENDCASE => ERROR]};
GetNode:
PUBLIC
PROC [t: Tree.Link]
RETURNS [Tree.Handle] = {
RETURN [WITH t SELECT FROM node: Tree.Handle => node, ENDCASE => ERROR]};
GetSe:
PUBLIC
PROC [t: Tree.Link]
RETURNS [ISEIndex] = {
RETURN [GetHash[t].name]};
NthSon:
PUBLIC
PROC [t: Tree.Link, n: Tree.SonId]
RETURNS [Tree.Link] = {
RETURN [
WITH t
SELECT
FROM
node: Tree.Handle => node.son[n],
ENDCASE => ERROR]};
NSons:
PUBLIC
PROC [t: Tree.Link]
RETURNS [
NAT] = {
RETURN [
WITH t
SELECT
FROM
node: Tree.Handle => node.sonLimit-1,
ENDCASE => 0]};
OpName:
PUBLIC
PROC [t: Tree.Link]
RETURNS [Tree.NodeName] = {
RETURN [WITH t SELECT FROM node: Tree.Handle => node.name, ENDCASE => none]};
procedures for tree traversal
ScanSons:
PUBLIC
PROC [root: Tree.Link, action: Tree.Scan] = {
WITH root
SELECT
FROM
node: Tree.Handle =>
FOR i: Tree.SonId IN [1 .. node.sonLimit) DO action[node.son[i]] ENDLOOP;
ENDCASE};
UpdateLeaves:
PUBLIC
PROC [root: Tree.Link, map: Tree.Map]
RETURNS [v: Tree.Link] = {
IF root = Tree.Null
THEN v ← Tree.Null
ELSE
WITH root
SELECT
FROM
node: Tree.Handle => {
FOR i: Tree.SonId
IN [1 .. node.sonLimit)
DO node.son[i] ← map[node.son[i]] ENDLOOP;
v ← root};
ENDCASE => v ← map[root];
RETURN};
procedures for list testing
ListLength:
PUBLIC
PROC [t: Tree.Link]
RETURNS [
NAT] = {
RETURN [
IF t = Tree.Null THEN 0
ELSE
WITH t
SELECT
FROM
node: Tree.Handle => IF node.name # list THEN 1 ELSE node.sonLimit-1,
ENDCASE => 1]};
ListHead:
PUBLIC
PROC [t: Tree.Link]
RETURNS [Tree.Link] = {
RETURN [
WITH t
SELECT
FROM
node: Tree.Handle =>
SELECT
TRUE
FROM
(node.name # list) => t,
(node.sonLimit # 1) => node.son[1],
ENDCASE => Tree.Null,
ENDCASE => t]};
ListTail:
PUBLIC
PROC [t: Tree.Link]
RETURNS [Tree.Link] = {
RETURN [
WITH t
SELECT
FROM
node: Tree.Handle =>
SELECT
TRUE
FROM
(node.name # list) => t,
(node.sonLimit # 1) => node.son[ListLength[t]],
ENDCASE => Tree.Null,
ENDCASE => t]};
procedures for list traversal
ScanList:
PUBLIC
PROC [root: Tree.Link, action: Tree.Scan] = {
IF root # Tree.Null
THEN
WITH root
SELECT
FROM
node: Tree.Handle =>
IF node.name # list
THEN action[root]
ELSE
FOR i: Tree.SonId
IN [1..node.sonLimit)
DO action[node.son[i]] ENDLOOP;
ENDCASE => action[root]};
ReverseScanList:
PUBLIC
PROC [root: Tree.Link, action: Tree.Scan] = {
IF root # Tree.Null
THEN
WITH root
SELECT
FROM
node: Tree.Handle =>
IF node.name # list
THEN action[root]
ELSE
FOR i: Tree.SonId
DECREASING
IN [1..node.sonLimit)
DO action[node.son[i]] ENDLOOP;
ENDCASE => action[root]};
SearchList:
PUBLIC
PROC [root: Tree.Link, test: Tree.Test] = {
IF root # Tree.Null
THEN
WITH root
SELECT
FROM
node: Tree.Handle =>
IF node.name # list
THEN [] ← test[root]
ELSE
FOR i: Tree.SonId
IN [1..node.sonLimit)
DO IF test[node.son[i]] THEN EXIT ENDLOOP;
ENDCASE => [] ← test[root]};
UpdateList:
PUBLIC
PROC [root: Tree.Link, map: Tree.Map]
RETURNS [Tree.Link] = {
IF root = Tree.Null THEN RETURN [Tree.Null];
WITH root
SELECT
FROM
node: Tree.Handle => {
IF node.name # list THEN RETURN [map[root]];
FOR i: Tree.SonId
IN [1..node.sonLimit)
DO node.son[i] ← map[node.son[i]] ENDLOOP;
RETURN [root]};
ENDCASE => RETURN [map[root]]};
ReverseUpdateList:
PUBLIC
PROC [root: Tree.Link, map: Tree.Map]
RETURNS [Tree.Link] = {
IF root = Tree.Null THEN RETURN [Tree.Null];
WITH root
SELECT
FROM
node: Tree.Handle => {
IF node.name # list THEN RETURN [map[root]];
FOR i: Tree.SonId
DECREASING
IN [1..node.sonLimit)
DO node.son[i] ← map[node.son[i]] ENDLOOP;
RETURN [root]};
ENDCASE => RETURN [map[root]]};
cross-table tree manipulation
CopyTree:
PUBLIC
PROC [root: Tree.Id, map: Tree.Map]
RETURNS [v: Tree.Link] = {
WITH root
SELECT
FROM
sNode: Tree.Handle => {
IF sNode = Tree.NullHandle
THEN v ← Tree.Null
ELSE {
dNode: Tree.Handle =
NEW[Tree.Node[NSons[sNode]] ← [
name: sNode.name,
attr: sNode.attr,
info: sNode.info,
son: ]];
FOR i: Tree.SonId
IN [1..sNode.sonLimit)
DO dNode.son[i] ← map[sNode.son[i]] ENDLOOP;
v ← dNode}};
ENDCASE => v ← map[root];
RETURN};
IdentityMap:
PUBLIC Tree.Map = {
RETURN [
IF
ISTYPE[t, Tree.Handle]
THEN CopyTree[t, IdentityMap]
ELSE t]};
END.