
    <<PPTreeImpl.Mesa>>
        <<Copyright © 1985 by Xerox Corporation.  All rights reserved.>>
        <<Satterthwaite, January 13, 1981  9:27 AM>>
        <<Russ Atkinson, February 12, 1985 3:38:56 pm PST>>

    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};


        <<procedures for tree testing>>

        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]};


        <<procedures for tree traversal>>

        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};


        <<procedures for list testing>>

        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]};


        <<procedures for list traversal>>

        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]]};


        <<cross-table tree manipulation>>

            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.