
<<--File: IPSimpleTreeImpl.mesa>>
<<Last Edited by: CSChow, January 28, 1985 2:14:32 am PST>>

    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


        <<--(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.