XTreePack.Mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Satterthwaite, October 9, 1985 12:03:50 pm PDT
DIRECTORY
Tree: TYPE USING [Id, Index, Info, Link, MapFromX, Node, NodeName, Scan, Null, NullIndex],
TreeOps: TYPE USING [NodeSize, PopTree, PushNode, PushProperList, PushTree, SetAttr, SetInfo],
XTree: TYPE Tree USING [Id, Index, Link, NullIndex],
XTreeOps: TYPE USING [];
XTreePack:
PROGRAM
IMPORTS TreeOps
EXPORTS XTreeOps = {
end markers in external trees
endXIndex: XTree.Index = XTree.Index.LAST;
endXMark: XTree.Link = [subtree[index: endXIndex]];
end markers in internal trees
endIndex: Tree.Index = Tree.Index.LAST;
endMark: Tree.Link = [subtree[index: endIndex]];
link conversion
LinkFromX:
PUBLIC PROC[link: XTree.Link]
RETURNS[Tree.Link] = {
RETURN[
WITH t: link
SELECT
FROM
subtree => [subtree[
index: (
IF t.index = endXIndex
--endIndex
THEN endIndex
ELSE Tree.Index.FIRST + (t.index-XTree.Index.FIRST))
]],
hash => [hash[t.index]],
symbol => [symbol[t.index]],
literal => [literal[t.index]],
ENDCASE => ERROR]
};
LinkToX:
PUBLIC PROC[link: Tree.Link]
RETURNS[XTree.Link] = {
RETURN[
WITH t: link
SELECT
FROM
subtree => [subtree[
index: (
IF t.index = endIndex
THEN endXIndex
ELSE XTree.Index.FIRST + (t.index-Tree.Index.FIRST))
]],
hash => [hash[t.index]],
symbol => [symbol[t.index]],
literal => [literal[t.index]],
ENDCASE => ERROR]
};
cross-table tree manipulation
CopyTreeFromX:
PUBLIC PROC[root: XTree.Id, map: Tree.MapFromX]
RETURNS[v: Tree.Link] = {
WITH root.link
SELECT
FROM
subtree => {
node: XTree.Index = index;
IF node = XTree.NullIndex THEN v ← Tree.Null
ELSE
{
n: CARDINAL ← root.baseP^[node].nSons;
IF root.baseP^[node].name = $list
THEN {
i: CARDINAL;
t: XTree.Link;
IF n # 0
THEN
FOR i ← 1, i+1
WHILE i <= n
DO
TreeOps.PushTree[map[root.baseP^[node].son[i]]];
ENDLOOP
ELSE
FOR i ← 1, i+1 UNTIL (t←root.baseP^[node].son[i]) = endXMark DO
TreeOps.PushTree[map[t]];
n ← n + 1;
ENDLOOP;
TreeOps.PushProperList[n]}
ELSE {
FOR i:
CARDINAL
IN [1 .. root.baseP^[node].nSons]
DO
TreeOps.PushTree[map[root.baseP^[node].son[i]]];
ENDLOOP;
TreeOps.PushNode[root.baseP^[node].name, n]};
TreeOps.SetInfo[root.baseP^[node].info];
TreeOps.SetAttr[1, root.baseP^[node].attr1];
TreeOps.SetAttr[2, root.baseP^[node].attr2];
TreeOps.SetAttr[3, root.baseP^[node].attr3];
v ← TreeOps.PopTree[]};
};
ENDCASE => v ← map[root.link];
RETURN};
ForEachSon:
PUBLIC PROC [node: Tree.Id, action: Tree.Scan] = {
WITH node.link
SELECT
FROM
subtree => {
sNode: Tree.Index = index;
IF sNode # Tree.NullIndex
THEN {
size: CARDINAL = TreeOps.NodeSize[node.baseP, sNode];
FOR i:
CARDINAL
IN [1..(size-Tree.Node.
SIZE)/Tree.Link.
SIZE]
DO
action[node.baseP^[sNode].son[i]];
ENDLOOP;
};
};
ENDCASE => NULL;
};
}.