DIRECTORY Rope, SymTab, IP, IPSimpleTree; IPSimpleTreeImpl: CEDAR PROGRAM IMPORTS Rope, SymTab, IP EXPORTS IPSimpleTree = BEGIN OPEN IPSimpleTree; Create: PUBLIC PROC [] RETURNS [Ref] ={ RETURN[NEW[Rep _[SymTab.Create[]]]]}; --Create 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 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. Š--File: IPSimpleTreeImpl.mesa Last Edited by: CSChow, January 28, 1985 2:14:32 am PST --(A) Tree Constructors: --(B) Tree Queries: Κ˜˜J™J™7J˜codešΟk ˜ K˜Kšœ˜Kšœ˜Kšœ ˜ —K˜šœœœ˜ Kšœ˜Kšœœœ˜0K˜šΟnœœœœ ˜'KšœœΟc˜.—K˜K˜K™šžœœœœ œœœ œœ˜qKšœœ˜Kšœ"œ5˜ZKšœŸ ˜ —K˜š ž œœœœœœ˜FKšœœ˜Kšœ˜%KšœŸ ˜—K˜K™šžœœœ œ ˜/Kšœœ ˜!KšœŸ ˜)—K˜š ž œœœ œ œœ˜Pšœ œ˜šœ*œœ˜=šœœ˜šœŸ˜Kšœ œ˜ Kšœœ˜—Kšœ˜—KšœŸ ˜——Kšœœ ˜!Kšœ˜KšœŸ ˜—K˜šžœœœœœœœ ˜]Kšœœ˜ Kšœœ˜ Kšœœ ˜!Kšœ/˜/Kšœœœœ˜#šœ ˜KšœœœA˜NKšœœœŸ ˜——K˜š ž œœœœœ˜PKšœœ ˜!š œœœœœœ˜AKšœ œ ˜/Kšœ˜—KšœŸ ˜—K˜šž œœœœ ˜=Kšœœ ˜!KšœœŸ ˜6—K˜šžœœ ˜Kšœ œ˜šœ"˜"Kšœ œ˜šœœœ˜šœœ˜Kšœ ˜Kšœœœ,˜9——Kšœœ˜JšœŸ ˜ —šœ œ œœ˜-šœœ˜Kšœœ˜šœ˜Kšœœ˜šœ*œœ˜=Kšœ1˜1Kšœ˜—Kšœ!˜!Kšœ˜——KšœŸ ˜—KšœœŸC˜ZKšœ$˜$šœœ˜Kšœœœ#˜0Kšœ˜—Kšœ˜KšœŸ˜ —K˜K˜Kšœ˜—K˜K˜—…— Δζ