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}; 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]}; 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}; 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]}; 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]]}; 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. >PPTreeImpl.Mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Satterthwaite, January 13, 1981 9:27 AM Russ Atkinson, February 12, 1985 3:38:56 pm PST procedures for tree testing procedures for tree traversal procedures for list testing procedures for list traversal cross-table tree manipulation Κ Ω˜codešœ™Kšœ Οmœ1™šžœ ˜ šžœžœž œžœ ˜/Kšžœž˜'—šžœžœžœ ˜$Kšžœžœ˜(——Kšžœžœ˜'K˜K˜—šŸœžœžœžœ˜)Kšœžœžœ˜šžœž˜Kšœžœ˜ K˜šžœ˜ Kšœžœ(˜?šžœ ˜ šžœžœž œžœ ˜0Kšžœž˜'—šžœžœžœ ˜%Kšžœžœ˜(——Kšžœžœ˜'K˜K˜———šŸœžœžœžœ˜/šžœžœžœ˜Kšžœ˜šžœ˜Kšœžœ žœ˜CKšžœ žœ˜)K˜K˜K˜———šŸœžœžœžœ˜)K˜šžœžœž˜K˜&Kšžœžœ˜K˜——šŸœžœžœžœ˜:K˜šžœžœž˜K˜.Kšžœžœ˜K˜K˜K˜——Kšœ™K˜šŸœžœžœžœ˜9Kš žœžœžœžœžœžœ˜AK˜—šŸœžœžœžœ˜=Kš žœžœžœžœžœžœ˜IK˜—šŸœžœžœžœ˜8Kšžœ˜K˜—šŸœžœžœžœ˜Išžœžœžœž˜K˜!Kšžœžœ˜K˜——š Ÿœžœžœžœžœ˜3šžœžœžœž˜K˜%Kšžœ˜K˜——šŸœžœžœžœ˜>Kš žœžœžœžœ!žœ ˜MK˜K˜—Kšœ™K˜šŸœžœžœ)˜>šžœžœž˜˜Kšžœžœžœžœ˜I—Kšžœ˜ K˜——šŸ œžœžœ"žœ˜Ušžœ˜Kšžœ˜šž˜šžœžœž˜˜šžœžœ˜)Kšžœ žœ˜*—K˜ —Kšžœ˜———Kšžœ˜K˜K˜—Kšœ™K˜š Ÿ œžœžœžœžœ˜8šžœ˜Kšžœžœ˜šžœžœžœž˜Kšœžœžœžœ˜EKšžœ˜K˜———šŸœžœžœžœ˜<šžœžœžœž˜˜šžœžœž˜K˜K˜#Kšžœ˜——Kšžœ˜K˜——šŸœžœžœžœ˜<šžœžœžœž˜˜šžœžœž˜K˜K˜/Kšžœ˜——Kšžœ˜K˜K˜——Kšœ™K˜šŸœžœžœ)˜>šžœ˜šž˜šžœžœž˜˜šžœ˜Kšžœ ˜šž˜šžœžœ˜'Kšžœžœ˜————Kšžœ˜K˜————šŸœžœžœ)˜Ešžœ˜šž˜šžœžœž˜˜šžœ˜Kšžœ ˜šž˜šžœž œžœ˜2Kšžœžœ˜————Kšžœ˜K˜————šŸ œžœžœ'˜>šžœ˜šž˜šžœžœž˜˜šžœ˜Kšžœ˜šž˜šžœžœ˜'Kš žœžœžœžœžœ˜*————Kšžœ˜K˜————šŸ œžœžœ"žœ˜PKšžœžœžœ ˜,šžœžœž˜˜Kšžœžœžœ ˜,šžœžœ˜'Kšžœ žœ˜*—Kšžœ ˜—Kšžœžœ˜K˜——šŸœžœžœ"žœ˜WKšžœžœžœ ˜,šžœžœž˜˜Kšžœžœžœ ˜,šžœž œžœ˜2Kšžœ žœ˜*—Kšžœ ˜—Kšžœžœ˜K˜K˜——Kšœ™˜šŸœžœžœ žœ˜Ošžœžœž˜˜šžœ˜Kšžœ˜šžœ˜šœžœ˜4K˜K˜K˜K˜—šžœžœ˜(Kšžœ"žœ˜,—K˜ ———Kšžœ˜—Kšžœ˜K˜—šœ žœ ˜ šžœžœžœ˜!Kšžœ˜Kšžœ˜ K˜——Kšžœ˜———…—|)“