IPSimpleTreeImpl:
CEDAR
PROGRAM
IMPORTS Rope, SymTab, IP
EXPORTS IPSimpleTree = BEGIN OPEN IPSimpleTree;
Create:
PUBLIC
PROC []
RETURNS [Ref] ={
RETURN[NEW[Rep ←[SymTab.Create[]]]]}; --Create
--(A) Tree Constructors:
AddNode:
PUBLIC
PROC[st: Ref, ndName, parent: Rope.
ROPE, children:
LIST
OF Rope.
ROPE, areaEst:
INT, any:
REF] = {
st.initialized ← FALSE;
[] ← SymTab.Store[st.tab, ndName, NEW[NodeRep ← [ndName, areaEst, any, parent, children]]]
}; --AddNode
RemoveNode:
PUBLIC
PROC[st: Ref, ndName: Rope.
ROPE]
RETURNS [
BOOL] = {
st.initialized ← FALSE;
RETURN[SymTab.Delete[st.tab, ndName]]
}; --RemoveNode
--(B) Tree Queries:
GetRoot:
PUBLIC
PROC[st: Ref]
RETURNS [Node] ={
IF ~st.initialized THEN Init[st];
RETURN [GetNode[st, st.root]]}; --GetRoot
GetLeaves:
PUBLIC
PROC[st: Ref]
RETURNS [count:
NAT ← 0, leaves: Nodes ←
NIL] ={
nextNode:
PROC[node: Node] ={
FOR l: Nodes ← GetChildren[st, node], l.rest
UNTIL l =
NIL
DO
IF l.first.children =
NIL
THEN {
--found a leaf
leaves ← CONS[l.first, leaves];
count ← count.SUCC}
ELSE nextNode[l.first];
ENDLOOP;}; --nextNode
IF ~st.initialized THEN Init[st];
nextNode[GetRoot[st]]
}; --GetLeaves
GetNode:
PUBLIC
PROC[st: Ref, nodeName: Rope.
ROPE, raiseError:
BOOL ←
TRUE]
RETURNS [Node] ={
found: BOOL;
val: REF;
IF ~st.initialized THEN Init[st];
[found, val] ← SymTab.Fetch[st.tab, nodeName];
IF found THEN RETURN [NARROW[val]];
IF raiseError
THEN ERROR IP.Error[missingRegistration, Rope.Cat[nodeName, " is not a node"]]
ELSE RETURN [NIL]}; --GetNode
GetChildren:
PUBLIC
PROC[st: Ref, node: Node]
RETURNS [children: Nodes ←
NIL] ={
IF ~st.initialized THEN Init[st];
FOR l:
LIST
OF Rope.
ROPE ← node.children, l.rest
UNTIL l =
NIL
DO
children ← CONS[GetNode[st, l.first], children]
ENDLOOP;
}; --GetChildren
GetParent:
PUBLIC
PROC[st: Ref, node: Node]
RETURNS [Node] ={
IF ~st.initialized THEN Init[st];
RETURN [GetNode[st, node.parent, FALSE]]}; --GetParent
Init:
PROC[st: Ref] ={
root: Node ← NIL;
findRoot: SymTab.EachPairAction ={
node: Node ← NARROW[val];
IF node.parent =
NIL
THEN {
IF root =
NIL
THEN root ← node
ELSE ERROR IP.Error[programmingError, "Multiple Roots"]};
RETURN [FALSE]
}; --findRoot
assignArea:
PROC[node: Node]
RETURNS [
INT]= {
IF node.children =
NIL
THEN RETURN [node.areaEstimate]
ELSE {
areaEstimate: INT ← 0;
FOR l: Nodes ← GetChildren[st, node], l.rest
UNTIL l =
NIL
DO
areaEstimate ← areaEstimate + assignArea[l.first]
ENDLOOP;
node.areaEstimate ← areaEstimate;
RETURN [areaEstimate]};
}; --assignArea
st.initialized ← TRUE; --Has to come early (before assignArea) to avoid infinite recursion
[] ← SymTab.Pairs[st.tab, findRoot];
IF root =
NIL
THEN ERROR IP.Error[programmingError, "No Root"]
ELSE st.root ← root.name;
[] ← assignArea[root]
}; --Init
END.