<<>>
    <<MPTreeImpl.mesa>>
        <<Copyright Ó 1985, 1986, 1987, 1991 by Xerox Corporation.  All rights reserved.>>
        <<Satterthwaite, January 13, 1981  9:27 AM>>
        <<Russ Atkinson (RRA) January 19, 1987 7:53:05 pm PST>>
        <<Michael Plass, September 6, 1991 0:11 am PDT>>

    DIRECTORY
        MPLeaves USING [HTIndex, ISEIndex],
        MPTree USING [AttrId, Id, Handle, Link, Map, Node, NodeName, Scan, SonId, SubInfo, Test, Null, NullHandle],
        MPTreeOps USING [],
        Process USING [GetCurrent, InitializeCondition, EnableAborts, MsecToTicks];

    MPTreeImpl: CEDAR MONITOR IMPORTS Process EXPORTS MPTreeOps =
        BEGIN OPEN MPLeaves, Tree: MPTree;

        initialized: BOOL ¬ FALSE;

        StackIncr: CARDINAL = 32;

        LinkStack: TYPE = RECORD [SEQUENCE size: NAT OF Tree.Link];

        stack: REF LinkStack ¬ NIL;
        sI: NAT;

        done: CONDITION;
        InitializeDone: PROC RETURNS [BOOL ¬ FALSE] ~ TRUSTED {
            Process.InitializeCondition[@done, Process.MsecToTicks[500]];
            Process.EnableAborts[@done];
            };
        inUse: BOOL ¬ InitializeDone[];
        owner: PROCESS ¬ NIL;
        Initialize: PUBLIC ENTRY PROC = {
            WHILE inUse DO
                WAIT done;
                ENDLOOP;
            owner ¬ Process.GetCurrent[];
            IF initialized THEN initialized ¬ FALSE;
            stack ¬ AllocStack[StackIncr];
            sI ¬ 0;
            initialized ¬ TRUE;
            };

        Reset: PUBLIC PROC = {
            IF owner # Process.GetCurrent[] THEN ERROR; -- Client misuse
            IF initialized AND stack.size > 2*StackIncr THEN stack ¬ AllocStack[StackIncr];
            };

        Finalize: PUBLIC PROC = {
            LockedFinalize: ENTRY PROC ~ {
                inUse ¬ FALSE;
                initialized ¬ FALSE;
                owner ¬ NIL;
                };
            IF owner # Process.GetCurrent[] THEN ERROR; -- Client misuse
            LockedFinalize[];
            };

        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 owner # Process.GetCurrent[] THEN ERROR; -- Client misuse
            IF sI >= stack.size THEN ExpandStack[];
            stack[sI] ¬ v;  sI ¬ sI+1;
            };

        PopTree: PUBLIC PROC RETURNS [Tree.Link] = {
            IF owner # Process.GetCurrent[] THEN ERROR; -- Client misuse
            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]];
            node.name ¬ name;
            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]];
                    node.name ¬ list;
                    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]]];
                    node.name ¬ list;
                    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};

        SetSubInfo: PUBLIC PROC [subInfo: Tree.SubInfo] = {
            v: Tree.Link = stack[sI-1];
            WITH v SELECT FROM
                node: Tree.Handle => node.subInfo¬ subInfo;
                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]]];
                                dNode.name ¬ sNode.name;
                                dNode.attr ¬ sNode.attr;
                                dNode.info ¬ sNode.info;
                                FOR i: Tree.SonId IN [1..sNode.sonLimit)
                                    DO dNode.son[i] ¬ map[sNode.son[i]];
                                    ENDLOOP;
                                v ¬ dNode}};
                    ENDCASE => v ¬ map[root];
                };

            IdentityMap: PUBLIC Tree.Map = {
                RETURN [IF ISTYPE[t, Tree.Handle]
                    THEN CopyTree[t, IdentityMap]
                    ELSE t]};

            END.