
<<LichenArrayImpl.Mesa>>
    <<Last tweaked by Mike Spreitzer on August 28, 1987 11:44:43 am PDT>>

    DIRECTORY Basics, Convert, GList, InterpreterOps, IntHashTable, IO, LichenArrayStuff, LichenCollections, LichenDataOps, 
    LichenDataStructure, LichenPairCollections, RefTab, Rope;

    LichenArrayImpl: CEDAR PROGRAM
        IMPORTS Basics, GList, IntHashTable, LichenArrayStuff, LichenCollections, LichenDataOps, LichenDataStructure, 
        LichenPairCollections, RefTab
        EXPORTS LichenArrayStuff, LichenDataStructure
        =

    BEGIN OPEN LichenDataStructure, LichenArrayStuff, LichenDataOps, Sets:LichenCollections, Fns:LichenPairCollections;

    Quit: ERROR = CODE;

    PackedArrayIndex: PUBLIC TYPE = INT;

    PackArrayIndex: PUBLIC PROC [ai: ArrayIndex] RETURNS [PackedArrayIndex]
        = {RETURN [PackArrayIndexI[ai]]};

    PackArrayIndexI: PROC [ai: ArrayIndex] RETURNS [PackedArrayIndex]
        = INLINE {RETURN [LOOPHOLE[Nat2[ai[Foo], ai[Bar]]]]};

    UnpackArrayIndex: PUBLIC PROC [pai: PackedArrayIndex] RETURNS [ArrayIndex]
        = {RETURN [UnpackArrayIndexI[pai]]};

    UnpackArrayIndexI: PROC [pai: PackedArrayIndex] RETURNS [ArrayIndex]
        = INLINE {RETURN [[LOOPHOLE[pai, Nat2][Foo], LOOPHOLE[pai, Nat2][Bar]]]};

    Central: PUBLIC PROC [a: Array, ai: ArrayIndex] RETURNS [BOOL] = {
        RETURN [
            ai[Foo] > 0 AND ai[Foo]+1 < a.size[Foo] AND
            ai[Bar] > 0 AND ai[Bar]+1 < a.size[Bar]];
        };

    ComputeGroupingsIndex: PUBLIC PROC [a: Array, ai: ArrayIndex] RETURNS [gi2, gii2: Nat2, gi, cgii: NAT] = {
        ngii: Nat2 _ [1, 1];
        Gi1D: PROC [d: Dim] = {
            i: INT = ai[d];
            SELECT TRUE FROM
                i < a.groupingParmses[d].middle.min => gi2[d] _ i;
                i >= a.groupingParmses[d].middle.maxPlusOne => gi2[d] _ i + a.groupingParmses[d].
                ENDCASE => {
                    
                    
                    jiir: Range = Range1Div[a.groupingParmses[d].middle, 
                    gi2[d] _ a.groupingParmses[d].middle.min + 
                    gii2[d] _ i/a.jointsPeriod[d] - jiir.min;
                    ngii[d] _ RangeLength[jiir];
                    }};
        gii2 _ [0, 0];
        Gi1D[Foo]; Gi1D[Bar];
        gi _ a.groupingParmses[Bar].sum * gi2[Foo] + gi2[Bar];
        cgii _ ngii[Bar] * gii2[Foo] + gii2[Bar]};

    ComputeJointGroupingsIndex: PUBLIC PROC [a: Array, j: Joint, jii: Nat2] RETURNS [jgi2: Nat2, jgi, ctii: NAT, jiir: Range2] = {
        njgii: Nat2 _ [1, 1];
        jgii2: Nat2 _ [0, 0];
        Gi1D: PROC [d: Dim] = {
            i: NAT = jii[d];
            jiir[d] _ [min: i, maxPlusOne: i+1];
            SELECT TRUE FROM
                i < j.groupingParmses[d].middle.min => jgi2[d] _ i;
                i >= j.groupingParmses[d].middle.maxPlusOne => jgi2[d] _ i + j.groupingParmses[d].
                ENDCASE => {
                    jgi2[d] _ j.groupingParmses[d].middle.min;
                    jiir[d] _ j.groupingParmses[d].middle;
                    jgii2[d] _ i - jgi2[d];
                    njgii[d] _ RangeLength[jiir[d]];
                    }};
        Gi1D[Foo]; Gi1D[Bar];
        jgi _ j.groupingParmses[Bar].sum * jgi2[Foo] + jgi2[Bar];
        ctii _ njgii[Bar] * jgii2[Foo] + jgii2[Bar]};

    AddTiedGroups: PROC [d: Dim, j: Joint, side: End, jgi: NAT, g: Group, to: GroupList] RETURNS [tied: GroupList] = {
        IF g = NIL THEN RETURN [to];
        IF FetchTie[j, side, jgi, g] # NIL THEN RETURN [CONS[g, to]];
        IF g.stopLooking[d][side] THEN RETURN [to];
        tied _ to;
        FOR worse: GroupList _ g.worse, worse.rest WHILE worse # NIL DO
            tied _ AddTiedGroups[d, j, side, jgi, worse.first, tied];
            ENDLOOP;
        tied _ tied;
        };

    AddListTiedGroups: PROC [d: Dim, j: Joint, side: End, jgi: NAT, gs, to: GroupList] RETURNS [tied: GroupList] = {
        tied _ NIL;
        FOR gs _ gs, gs.rest WHILE gs # NIL DO
            tied _ AddTiedGroups[d, j, side, jgi, gs.first, tied];
            ENDLOOP;
        tied _ tied;
        };

    ArrayWireForGroup: PUBLIC PROC [a: Array, index: ArrayIndex, gi: NAT, g: Group, mayAdd: BOOL] RETURNS [aw: ArrayWire] ~ {
        pai: PackedArrayIndex ~ PackArrayIndexI[index];
        last: IntTable --PackedArrayIndex 
        IF g.ports=NIL THEN ERROR;
        IF last # NIL THEN {
            aw _ NARROW[last.Fetch[pai].value];
            IF aw # NIL THEN RETURN;
            };
        IF NOT mayAdd THEN RETURN [NIL];
        aw _ NEW [ArrayWirePrivate _ [
            members: Fns.CreateHashFn[],
            ports: Sets.CreateHashSet[]
            ]];
        IF NOT a.wires.AddElt[aw] THEN ERROR;
        AddEltToArrayWire[a, aw, [g, index]];
        };

    SetGroupInWireAt: PROC [a: Array, gi2: Nat2, g: Group, aw: ArrayWire, ai: ArrayIndex] RETURNS [news: BOOL] ~ {
        air: Range2 ~ Gi2ToAir[a, gi2].air;
        shape: Nat2 ~ RangeShape[air];
        gii: Nat2 ~ Nat2Div[Int2SubN[ai, Range2Min[air]], a.jointsPeriod];
        index: NAT ~ shape[Bar] * gii[Foo] + gii[Bar];
        bs: BoolSeq _ WITH aw.members.Apply[g].val SELECT FROM
            x: BoolSeq => x,
            x: Sets.NoValue => NARROW[aw.members.Inserted[[g, CreateBoolSeq[Nat2Area[shape]]]]],
            ENDCASE => ERROR;
        IF g.ports=NIL THEN ERROR;
        IF bs = NIL AND NOT aw.members.Store[[g, bs _ CreateBoolSeq[Nat2Area[shape]]]].new THEN ERROR;
        IF bs[index] THEN RETURN [FALSE];
        {
        last: IntTable --PackedArrayIndex 
        pai: PackedArrayIndex ~ PackArrayIndexI[ai];
        IF last = NIL AND NOT a.toWire.Insert[g, last _ CreateIntTable[]] THEN ERROR;
        [] _ last.Store[pai, aw];
        news _ bs[index] _ TRUE;
        }};

    AddEltToArrayWire: PROC [a: Array, aw: ArrayWire, elt: ArrayWireElt] = {
        NoteConnection: PROC [ain: ArrayIndex, gn: Group] ~ {
            IF gn.ports#NIL THEN {
                gi2n: Nat2 ~ ComputeGroupingsIndex[a, ain].gi2;
                IF SetGroupInWireAt[a, gi2n, gn, aw, ain].news THEN stack _ CONS[[gn, ain], stack];
                };
            };
        stack: LIST OF ArrayWireElt _ NIL;
        NoteConnection[elt.ai, elt.g];
        WHILE stack # NIL DO
            elt: ArrayWireElt ~ stack.first;
            gi: NAT ~ ComputeGroupingsIndex[a, elt.ai].gi;
            stack _ stack.rest;
            EnumerateLocalConnections[a, elt.ai, gi, elt.g, NoteConnection];
            stack _ stack;
            ENDLOOP;
        stack _ stack;
        };

    JoinArrayWires: PROC [a: Array, aw1, aw2: ArrayWire] ~ {
        MoveElt: PROC [pair: Fns.Pair] ~ {
            g: Group ~ NARROW[pair[left]];
            bs: BoolSeq ~ NARROW[pair[right]];
            air: Range2 ~ Gi2ToAir[a, g.gi2].air;
            shape: Nat2 ~ RangeShape[air];
            FOR aif: NAT _ air[Foo].min, aif+a.jointsPeriod[Foo] WHILE aif < air[Foo].maxPlusOne DO FOR aib: NAT _ air[Bar].min, 
            aib+a.jointsPeriod[Bar] WHILE aib < air[Bar].maxPlusOne DO
                ai: ArrayIndex ~ [aif, aib];
                gii: Nat2 ~ Nat2Div[Int2SubN[ai, Range2Min[air]], a.jointsPeriod];
                index: NAT ~ shape[Bar] * gii[Foo] + gii[Bar];
                IF bs[index] THEN {
                    AddEltToArrayWire[a, aw1, [g, ai]];
                    Quit;
                    };
                ENDLOOP ENDLOOP;
            };
        MovePort: PROC [ra: REF ANY] ~ {
            ap: Port ~ NARROW[ra];
            IF NOT aw1.ports.AddElt[ap] THEN ERROR;
            IF NOT a.portWire.Replace[ap, aw1] THEN ERROR;
            };
        aw2.members.Enumerate[MoveElt !Quit => CONTINUE];
        aw2.ports.Enumerate[MovePort];
        IF NOT a.wires.RemoveElt[aw2] THEN ERROR;
        };

    EnumerateLocalConnections: PROC [a: Array, index: ArrayIndex, gi: NAT, g: Group, Consume: PROC [ain: ArrayIndex, gn: Group]] = {
        FOR d: Dim IN Dim DO FOR side: End IN End DO
            otherSide: End = OtherEnd[side];
            lai: ArrayIndex = Int2Tweak[index, d, SELECT side FROM low => 0, high => -1, ENDCASE => ERROR];
            hai: ArrayIndex = Int2Tweak[lai, d, 1];
            IF lai[d] < 0 OR hai[d] >= a.size[d] THEN LOOP;
            {jii: Nat2 = [lai[Foo]/a.jointsPeriod[Foo], lai[Bar]/a.jointsPeriod[Bar]];
            phase: Nat2 = [lai[Foo] - jii[Foo]*a.jointsPeriod[Foo], lai[Bar] - jii[Bar]*a.jointsPeriod[Bar]];
            j: Joint = GetArrayJoint[a, d, phase];
            jgi: NAT = ComputeJointGroupingsIndex[a, j, jii].jgi;
            tie: Tie = FetchTie[j, side, jgi, g];
            IF tie = NIL THEN LOOP;
            IF tie.groups[side] # g THEN ERROR;
            IF tie.groups[otherSide] # NIL THEN Consume[SELECT side FROM low => hai, high => lai, ENDCASE => ERROR, tie.groups[otherSide]];
            }ENDLOOP ENDLOOP;
        a _ a;
        };

    EnumerateArrays: PUBLIC PROC [cellType: CellType, Consume: PROC [CellType]] = {
        FOR act: CellType _ cellType.firstArray, act.asArray.nextArray WHILE act # NIL DO
            Consume[act];
            ENDLOOP;
        };

    Jgi2ToGi: PUBLIC PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, side: End] RETURNS [gi2: Nat2, gi: NAT] = {
        Do1: PROC [d: Dim] RETURNS [ji: NAT] = {
            SELECT TRUE FROM
                jgi2[d] < j.groupingParmses[d].middle.min => RETURN [jgi2[d]];
                jgi2[d] >= j.groupingParmses[d].firstHigh => RETURN [jgi2[d]-j.groupingParmses[d].
                ENDCASE => RETURN [j.groupingParmses[d].middle.min];
            };
        ji2: Int2 = [Foo: Do1[Foo], Bar: Do1[Bar]];
        lai: ArrayIndex = [
            Foo: phase[Foo] + a.jointsPeriod[Foo] * ji2[Foo],
            Bar: phase[Bar] + a.jointsPeriod[Bar] * ji2[Bar]];
        [gi2: gi2, gi: gi] _ ComputeGroupingsIndex[a, IF side = low THEN lai ELSE Int2Tweak[lai, d, 1]];
        };

    Jgi2ToGip: PUBLIC PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2] RETURNS [gip: GIPair] = {
        gip _  [
            low: Jgi2ToGi[a, d, phase, j, jgi2, low].gi,
            high: Jgi2ToGi[a, d, phase, j, jgi2, high].gi];
        };

    AgiToAi: PUBLIC PROC [a: Array, gi2, gii2: Nat2] RETURNS [ai: ArrayIndex] = {
        Do: PROC [d: Dim] RETURNS [INT] = {
            SELECT TRUE FROM
                gi2[d] < a.groupingParmses[d].middle.min => RETURN [gi2[d]];
                gi2[d] >= a.groupingParmses[d].firstHigh => RETURN [gi2[d] - a.groupingParmses[d].
                ENDCASE => {
                    
                    
                    min: NAT = CeilDiv[MAX[a.groupingParmses[d].middle.min, 
                    RETURN [(gii2[d] + min) * 
                    };
            };
        ai[Foo] _ Do[Foo];
        ai[Bar] _ Do[Bar];
        };

    JGRListize: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, lowRange: Range2] RETURNS [jgrl: JGRList] = {
        jiir: Range2 = Range2Div[lowRange, a.jointsPeriod, phase];
        Enum: PROC [de: Dim, Per: PROC [NAT, NAT, NAT, NAT, NAT, INT, INT, Range, Range]] = {
            
            
            giml: NAT = a.groupingParmses[de].middle.min + phase[de];
            gimh: NAT = a.groupingParmses[de].middle.min + 
            jirm: ARRAY End OF Range = [
                low: Range1Div[a.groupingParmses[de].middle, a.jointsPeriod[de], phase[de]],
                high: Range1Div[RangeOffClip[a.groupingParmses[de].middle, -
            nm: ARRAY End OF NAT = [low: RangeLength[jirm[low]], high: RangeLength[jirm[high]]];
            gijl: NAT _ jiir[de].min;
            gial: NAT _ gijl * a.jointsPeriod[de] + phase[de];
            ji: NAT _ jiir[de].maxPlusOne-1;
            ai: NAT _ ji * a.jointsPeriod[de] + phase[de] + 
            giah: INT _ ai + a.groupingParmses[de].
            gijh: INT _ ji + j.groupingParmses[de].
            lowLimit: NAT = MIN[j.groupingParmses[de].middle.min, jiir[de].maxPlusOne];
            highLimit: NAT = MAX[j.groupingParmses[de].middle.maxPlusOne, jiir[de].min];
            FOR gijl _ gijl, gijl+1 WHILE gijl < lowLimit DO
                this: Range = [min: gijl, maxPlusOne: gijl+1];
                nh: NAT _ 1;
                giah: INT _ gial + 
                IF 
                    THEN {giah _ gimh; nh _ nm[high]};
                Per[gial, giah, gijl, 1, nh, gijl, gijl, this, this];
                gial _ gial + a.jointsPeriod[de];
                ENDLOOP;
            FOR ji _ ji, ji-1 WHILE ji >= highLimit DO
                this: Range = [min: ji, maxPlusOne: ji + 1];
                nl: NAT _ 1;
                jii0al: INT _ ji;
                gial: INT _ giah - 
                IF 
                    THEN {gial _ giml; nl _ nm[low]; jii0al _ jirm[low].min};
                Per[gial, giah, gijh, nl, 1, jii0al, ji, this, this];
                giah _ giah - a.jointsPeriod[de];
                gijh _ gijh - 1;
                ENDLOOP;
            IF RangesIntersect[jiir[de], j.groupingParmses[de].middle] THEN {
                mjir: Range = [
                    min: MAX[j.groupingParmses[de].middle.min, jiir[de].min],
                    maxPlusOne: MIN[j.groupingParmses[de].middle.maxPlusOne, jiir[de].maxPlusOne]];
                Per[
                    giml,
                    gimh,
                    j.groupingParmses[de].middle.min,
                    nm[low],
                    nm[high],
                    jirm[low].min,
                    jirm[high].min,
                    mjir,
                    j.groupingParmses[de].middle
                    ];
                };
            };
        PerFoo: PROC [gialf, giahf, gijf, ngiilf, ngiihf: NAT, jii0alf, jii0ahf: INT, jirf, fullJiirf: Range] = {
            cf: BOOL = jirf = fullJiirf;
            PerBar: PROC [gialb, giahb, gijb, ngiilb, ngiihb: NAT, jii0alb, jii0ahb: INT, jirb, fullJiirb: Range] = {
                cb: BOOL = jirb = fullJiirb;
                jgrl _ CONS[
                    [
                        gis: [
                            low: a.groupingParmses[Bar].sum * gialf + gialb,
                            high: a.groupingParmses[Bar].sum * giahf + giahb],
                        ngii: [low: [ngiilf, ngiilb], high: [ngiihf, ngiihb]],
                        firstJIIOfGI: [low: [jii0alf, jii0alb], high: [jii0ahf, jii0ahb]],
                        jgi2: [Foo: gijf, Bar: gijb],
                        jgi: j.groupingParmses[Bar].sum * gijf + gijb,
                        jiir: [Foo: jirf, Bar: jirb],
                        fullJiir: [Foo: fullJiirf, Bar: fullJiirb],
                        complete: cf AND cb
                        ],
                    jgrl];
                };
            Enum[Bar, PerBar];
            };
        jgrl _ NIL;
        Enum[Foo, PerFoo];
        jgrl _ jgrl;
        };

    JGRList: TYPE = LIST OF READONLY JGR;
    JGR: TYPE = RECORD [
        gis: ARRAY End OF NAT,
        ngii: ARRAY End OF ARRAY Dim OF NAT,
        firstJIIOfGI: ARRAY End OF Int2,
        jgi2: Nat2,
        jgi: NAT,
        jiir, fullJiir: Range2,
        complete: BOOL
        ];
        <<ngii[side] is the number of instances of gis[side] in the entire array.>>
        <<firstJIIOfGI[side] is the jii of the first joint in the entire array that has gis[side] on side; note that this may include 
        imaginary joints along the low sides of the array.>>

    MakeArrayConnection: PUBLIC PROC [ct: CellType, d: Dim, lowRange: Range2, rp1, rp2: SidedPort, may: BOOL] RETURNS [connected: BOOL] 
    = {
        o: Dim = OtherDim[d];
        a: Array = ct.asArray;
        
        
        IF a = NIL THEN ERROR;
        IF lowRange[d].min<0 OR lowRange[d].maxPlusOne>=a.size[d] THEN ERROR;
        IF lowRange[o].min<0 OR lowRange[o].maxPlusOne>a.size[o] THEN ERROR;
        IF a.jointsPeriod[d] > a.size[d] THEN ERROR;
        FOR 
            phase2: Nat2 = [
            j: Joint = GetArrayJoint[a, d, phase2];
            jgrl: JGRList _ JGRListize[a, d, phase2, j, lowRange];
            FOR jgrl _ jgrl, jgrl.rest WHILE jgrl # NIL DO
                jgr: JGR = jgrl.first;
                njgiib: NAT = RangeLength[jgr.fullJiir[Bar]];
                g1: Group = GetGroup[a, jgr.gis[rp1.side], rp1.port, may];
                g2: Group = GetGroup[a, jgr.gis[rp2.side], rp2.port, may];
                tie: Tie;
                rpd1, rpd2: SidedPortData;
                IF g1 = NIL OR g2 = NIL THEN {IF may THEN ERROR ELSE RETURN [FALSE]};
                [tie, rpd1, rpd2] _ GetTieAndRPD[a, d, phase2, j, jgr.jgi2, jgr.jgi, jgr.fullJiir, rp1, rp2, g1, g2, jgr.gis[rp1.side], 
                jgr.gis[rp2.side], may];
                IF tie = NIL THEN {IF may THEN ERROR ELSE RETURN [FALSE]};
                IF may AND tie.completion # NIL THEN {
                    FOR jiif: INT IN [jgr.jiir[Foo].min .. jgr.jiir[Foo].maxPlusOne) DO FOR jiib: INT IN [jgr.jiir[Bar].min .. 
                    jgr.jiir[Bar].maxPlusOne) DO
                        lai: ArrayIndex = [
                            Foo: jiif*a.jointsPeriod[Foo] + 
                            Bar: jiib*a.jointsPeriod[Bar] + 
                        giis: ARRAY End OF NAT = [
                            low: jgr.ngii[low][Bar] * (jiif - jgr.firstJIIOfGI[low][Foo]) + jiib - jgr.firstJIIOfGI[low][Bar],
                            high: jgr.ngii[high][Bar] * (jiif - jgr.firstJIIOfGI[high][Foo]) + jiib - jgr.firstJIIOfGI[high][Bar]];
                        ctii: NAT = njgiib * (jiif - jgr.fullJiir[Foo].min) + jiib - jgr.fullJiir[Bar].min;
                        Merge[a, d, lai, j, jgr.jgi, tie, rpd1, rpd2, ctii];
                        tie _ BestTie[tie];
                        IF tie.completion = NIL THEN GOTO Completed;
                        ENDLOOP ENDLOOP;
                    EXITS Completed => tie _ tie;
                    };
                ENDLOOP;
            ENDLOOP ENDLOOP;
        connected _ TRUE;
        IF NOT may THEN RETURN;
        FOR f: NAT IN [NAT[lowRange[Foo].min] .. NAT[lowRange[Foo].maxPlusOne]) DO FOR b: NAT IN [NAT[lowRange[Bar].min] .. 
        NAT[lowRange[Bar].maxPlusOne]) DO
            ais: ARRAY End OF ArrayIndex = [[f, b], Int2Tweak[[f, b], d, 1]];
            gis: ARRAY End OF NAT = [ComputeGroupingsIndex[a, ais[low]].gi, ComputeGroupingsIndex[a, ais[high]].gi];
            g1: Group = GetGroup[a, gis[rp1.side], rp1.port, FALSE];
            g2: Group = GetGroup[a, gis[rp2.side], rp2.port, FALSE];
            aw1: ArrayWire = ArrayWireForGroup[a, ais[rp1.side], gis[rp1.side], g1, FALSE];
            aw2: ArrayWire = ArrayWireForGroup[a, ais[rp2.side], gis[rp2.side], g2, FALSE];
            IF aw1 = aw2 THEN NULL
            ELSE IF aw2 = NIL THEN AddEltToArrayWire[a, aw1, [g2, ais[rp2.side]]]
            ELSE IF aw1 = NIL THEN AddEltToArrayWire[a, aw2, [g1, ais[rp1.side]]]
            ELSE JoinArrayWires[a, aw1, aw2];
            ENDLOOP ENDLOOP;
        };

    MakeGroupsForPort: PUBLIC PROC [a: Array, ep: Port] ~ {
        a _ a;
        FOR gi: NATURAL IN [0 .. a.groupingses.length) DO
            [] _ GetGroup[a, gi, ep, TRUE];
            ENDLOOP;
        a _ a;
        };

    GetGroup: PUBLIC PROC [a: Array, gi: NAT, ep: Port, mayAdd: BOOL] RETURNS [g: Group] ~ {
        gs: Groupings ~ NARROW[a.groupingses[gi]];
        g _ NARROW[gs.toGroup.Fetch[ep].val];
        IF g = NIL AND mayAdd THEN {
            gi2: Nat2 ~ GiToGi2[a, gi];
            g _ MakeGroup[a, gi2, gs];
            AddPortToGroup[a, gi, ep, g, TRUE];
            IF gs.toGroup.Fetch[ep].val # g THEN ERROR};
        };

    MakeGroup: PUBLIC PROC [a: Array, gi2: Nat2, gs: Groupings] RETURNS [g: Group] = {
        g _ NEW [GroupPrivate _ [gi2: gi2]];
        IF NOT gs.groups.AddElt[g] THEN ERROR;
        g _ g};

    AddPortToGroup: PUBLIC PROC [a: Array, gi: NATURAL, ep: Port, g: Group, links: BOOL] ~ {
        gs: Groupings ~ NARROW[a.groupingses[gi]];
        IF g.better#NIL OR g.worse#NIL THEN ERROR;
        g.ports _ CONS[ep, g.ports];
        IF NOT gs.toGroup.Insert[ep, g] THEN ERROR;
        FOR d: Dim IN Dim DO
            FOR side: End IN End DO
                EnsureRPD[a, d, [side: side, port: ep], links];
                ENDLOOP;
            ENDLOOP;
        g _ g};

    RemovePortFromGroup: PUBLIC PROC [a: Array, gi: NATURAL, ep: Port, g: Group] ~ {
        gs: Groupings ~ NARROW[a.groupingses[gi]];
        IF g.better#NIL OR g.worse#NIL THEN ERROR;
        IF gs.toGroup.Fetch[ep].val # g THEN ERROR;
        g.ports _ NARROW[GList.DRemove[ep, g.ports]];
        IF NOT gs.toGroup.Delete[ep] THEN ERROR;
        g _ g};

    UnrolePort: PUBLIC PROC [a: Array, ep: Port] ~ {
        FOR d: Dim IN Dim DO FOR s: End IN End DO
            spd: SidedPortData ~ NARROW[a.toRole[d][s].Fetch[ep].val];
            IF a.roles[d].refs[spd.index] # spd THEN ERROR;
            IF spd.index+1 = a.nextRP[d] THEN {
                a.nextRP[d] _ a.nextRP[d]-1;
                a.roles[d].length _ a.roles[d].length-1};
            a.roles[d].refs[spd.index] _ NIL;
            IF NOT a.toRole[d][s].Delete[ep] THEN ERROR;
            ENDLOOP ENDLOOP;
        a _ a;
        };

    EnsureRPD: PROC [a: Array, d: Dim, rp: SidedPort, links: BOOL] = {
        rpd: SidedPortData _ FetchRPD[a, d, rp];
        IF rpd = NIL THEN {
            rpd _ NEW [SidedPortDataPrivate _ [
                port: rp.port,
                side: rp.side,
                index: a.nextRP[d],
                links: NIL
                ]];
            IF a.roles[d].length # rpd.index THEN ERROR;
            VarRefSeqAppend[a.roles[d], rpd];
            a.nextRP[d] _ a.nextRP[d] + 1;
            IF NOT a.toRole[d][rp.side].Store[rp.port, rpd] THEN ERROR;
            IF links THEN AddLinks[a, d, rpd];
            };
        rpd _ rpd};

    GetTieAndRPD: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, jgi: NAT, jiir: Range2, rp1, rp2: SidedPort, g1, g2: 
    Group, gi1, gi2: NAT, may: BOOL] RETURNS [tie: Tie, rpd1, rpd2: SidedPortData] = {
        tie1: Tie = GetTie[a, d, phase, j, rp1.side, jgi2, jgi, jiir, g1, gi1, may];
        tie2: Tie = GetTie[a, d, phase, j, rp2.side, jgi2, jgi, jiir, g2, gi2, may];
        tie _ SELECT TRUE FROM
            tie1 = tie2 => tie1,
            NOT may => NIL,
            ENDCASE => JoinTies[a, d, phase, j, jgi2, jgi, jiir, LIST[tie1, tie2], TRUE];
        IF may AND tie.completion # NIL THEN {
            rpd1 _ FetchRPD[a, d, rp1];
            rpd2 _ FetchRPD[a, d, rp2];
            };
        };

    GetTie: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, side: End, jgi2: Nat2, jgi: NAT, jiir: Range2, g: Group, gi: NAT, may: BOOL] 
    RETURNS [tie: Tie] = {
        tie _ FetchTie[j, side, jgi, g];
        IF tie = NIL AND may THEN {
            cn: Completion _ NIL;
            IF g.ports # NIL AND g.ports.rest # NIL THEN {
                ntii: NAT = RangeArea[jiir];
                tii, ni: NAT _ 0;
                
                cn _ NEW [CompletionPrivate[ntii]];
                IF side = high THEN 
                FOR jiif: INT IN [jiir[Foo].min .. jiir[Foo].maxPlusOne) DO FOR jiib: INT IN [jiir[Bar].min .. jiir[Bar].maxPlusOne) DO
                    lai: ArrayIndex = [jiif*a.jointsPeriod[Foo]+phase[Foo], jiib*a.jointsPeriod[Bar]+phase[Bar]];
                    jSize: Nat2 = Nat2Tweak[a.size, d, -1];
                    IF NOT (cn[tii] _ ComputeGroupCompleteAt[a, g, jSize[Bar]*lai[Foo]+lai[Bar], d, side]) THEN ni _ ni + 1;
                    ENDLOOP ENDLOOP;
                cn.nIncomplete _ ni;
                IF ni = 0 THEN cn _ NIL;
                };
            tie _ NEW [TiePrivate _ [
                groups: ALL[NIL],
                completion: cn
                ]];
            tie.groups[side] _ g;
            g.stopLooking[d][side] _ TRUE;
            AddTie[j, jgi, tie];
            };
        };

    JoinTies: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, jgi: NAT, jiir: Range2, ties: TieList, mayJoinGroups: BOOL] 
    RETURNS [tie: Tie] = {
        ntii: NAT = RangeArea[jiir];
        groups: ARRAY End OF Group _ ALL[NIL];
        urTies: TieList = ties;
        doomeds: TieList _ NIL;
        gi2s: ARRAY End OF Nat2;
        gis: ARRAY End OF NAT;
        hPhase: Nat2 _ phase;
        hPhase[d] _ (phase[d] + 1) MOD a.jointsPeriod[d];
        FOR ts: TieList _ ties, ts.rest WHILE ts # NIL DO
            tie: Tie = ts.first;
            IF tie.better # NIL THEN ERROR;
            IF GList.Member[tie, ts.rest] THEN ERROR;
            ENDLOOP;
        FOR side: End IN End DO
            olds: GroupList _ NIL;
            [gi2s[side], gis[side]] _ Jgi2ToGi[a, d, phase, j, jgi2, side];
            FOR ts: TieList _ ties, ts.rest WHILE ts # NIL DO
                g: Group = BestGroup[ts.first.groups[side]];
                IF g # NIL AND NOT GList.Member[g, olds] THEN olds _ CONS[g, olds];
                ENDLOOP;
            groups[side] _ IF olds # NIL THEN IF olds.rest = NIL THEN olds.first ELSE IF mayJoinGroups THEN JoinGroups[a, phase, gi2s[side], 
            olds, NARROW[a.groupingses[gis[side]]]] ELSE ERROR ELSE NIL;
            ENDLOOP;
        FOR side: End IN End DO
            best: Group = groups[side] _ BestGroup[groups[side]];
            FOR worses: GroupList _ AddTiedGroups[d, j, side, jgi, best, NIL], worses.rest WHILE worses # NIL DO
                worse: Group = worses.first;
                tie: Tie = FetchTie[j, side, jgi, worse];
                IF tie = NIL THEN ERROR
                ELSE IF NOT GList.Member[tie, doomeds] THEN doomeds _ CONS[tie, doomeds];
                ENDLOOP;
            ENDLOOP;
        FOR ts: TieList _ urTies, ts.rest WHILE ts # NIL DO
            IF NOT GList.Member[ts.first, doomeds] THEN ERROR;
            ENDLOOP;
        tie _ NEW [TiePrivate _ [groups: groups]];
        FOR ts: TieList _ doomeds, ts.rest WHILE ts # NIL DO
            doomed: Tie = ts.first;
            Incompletify[a, d, doomed, ntii];
            doomed.better _ tie;
            ENDLOOP;
        FinishIncompletion[a, d, phase, tie, ntii];
        FOR ts: TieList _ doomeds, ts.rest WHILE ts # NIL DO
            doomed: Tie = ts.first;
            DeleteTie[j, jgi, doomed];
            ENDLOOP;
        AddTie[j, jgi, tie];
        FOR sideg: End IN End DO --make sure all ties for group on this side are joined
            gPhase: Nat2 = IF sideg = low THEN phase ELSE hPhase;
            g: Group = groups[sideg];
            IF g # NIL THEN {
                FOR de: Dim IN Dim DO
                    FOR sidee: End IN End DO
                        Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi: NAT, j: Joint] = {
                            oldTies: TieList _ NIL;
                            FOR ws: GroupList _ AddTiedGroups[de, j, sidee, jgi, g, NIL], ws.rest WHILE ws # NIL DO
                                worse: Group = ws.first;
                                tie: Tie = FetchTie[j, sidee, jgi, worse];
                                IF tie = NIL THEN ERROR
                                ELSE IF NOT GList.Member[tie, oldTies] THEN oldTies _ CONS[tie, oldTies];
                                ENDLOOP;
                            IF oldTies # NIL AND (oldTies.rest # NIL OR oldTies.first.groups[sidee] # g) THEN {
                                jiir: Range2 = Jgi2ToLair[a, gPhase, j, jgi2].jiir;
                                newTie: Tie = JoinTies[a, de, gPhase, j, jgi2, jgi, jiir, oldTies, FALSE];
                                IF newTie.groups[sidee] # g THEN ERROR;
                                oldTies _ oldTies;
                                };
                            oldTies _ oldTies;
                            };
                        EnumerateJointsForGi[a, de, sidee, gPhase, gi2s[sideg], Consume];
                        g.stopLooking[de][sidee] _ TRUE;
                        ENDLOOP;
                    ENDLOOP;
                IF g.stopLooking = ALL[ALL[TRUE]] THEN KillWorse[g];
                };
            ENDLOOP;
        tie _ tie;
        };

    KillWorse: PROC [g: Group] = {
        FOR ws: GroupList _ g.worse, ws.rest WHILE ws # NIL DO
            KillWorse[ws.first];
            ENDLOOP;
        g.worse _ NIL;
        };

    JoinGroups: PROC [a: Array, phase: Nat2, gi2: Nat2, groups: GroupList, gs: Groupings] RETURNS [g: Group] = {
        bests: GroupList _ NIL;
        ports: PortList _ NIL;
        FOR raws: GroupList _ groups, raws.rest WHILE raws # NIL DO
            IF raws.first = NIL THEN LOOP;
            IF raws.first.ports = NIL THEN ERROR;
            {best: Group = BestGroup[raws.first];
            IF NOT GList.Member[best, bests] THEN {
                bests _ CONS[best, bests];
                ports _ NARROW[GList.Append[best.ports, ports]];
                };
            }ENDLOOP;
        IF bests = NIL THEN ERROR;
        IF bests.rest = NIL THEN RETURN [bests.first];
        g _ NEW [GroupPrivate _ [ports: ports, worse: bests, gi2: gi2]];
        FOR pl: PortList _ g.ports, pl.rest WHILE pl # NIL DO
            IF NOT gs.toGroup.Replace[pl.first, g] THEN ERROR;
            ENDLOOP;
        IF NOT gs.groups.AddElt[g] THEN ERROR;
        FOR worse: GroupList _ bests, worse.rest WHILE worse # NIL DO
            IF NOT gs.groups.RemoveElt[worse.first] THEN ERROR;
            worse.first.better _ g;
            ENDLOOP;
        FOR d: Dim IN Dim DO
            FOR side: End IN End DO
                Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi: NAT, j: Joint] = {
                    otherSide: End = OtherEnd[side];
                    otherGs: Groupings = NARROW[a.groupingses[otherGi]];
                    otherSideGroups: GroupList _ NIL;
                    FOR ws: GroupList _ AddListTiedGroups[d, j, side, jgi, bests, NIL], ws.rest WHILE ws # NIL DO
                        worse: Group = ws.first;
                        tie: Tie = FetchTie[j, side, jgi, worse];
                        IF tie = NIL THEN ERROR
                        ELSE IF tie.groups[otherSide] # NIL THEN otherSideGroups _ CONS[tie.groups[otherSide], otherSideGroups];
                        ENDLOOP;
                    IF otherSideGroups # NIL AND otherSideGroups.rest # NIL THEN [] _ JoinGroups[a, otherPhase, otherGi2, otherSideGroups, otherGs];
                    };
                EnumerateJointsForGi[a, d, side, phase, gi2, Consume];
                ENDLOOP;
            ENDLOOP;
        g _ g;
        };

    EnumerateJointsForGi: PROC [a: Array, d: Dim, side: End, phase, gi2: Nat2, Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, 
    otherGi, jgi: NAT, j: Joint]] = {
        lowPhase, highPhase: Nat2 _ phase;
        IF side = high THEN {
            lowPhase[d] _ (phase[d] + a.jointsPeriod[d] - 1) MOD a.jointsPeriod[d];
            }
        ELSE {
            highPhase[d] _ (phase[d] + 1) MOD a.jointsPeriod[d];
            };
        {j: Joint = GetArrayJoint[a, d, lowPhase];
        otherPhase: Nat2 = IF side = low THEN highPhase ELSE lowPhase;
        otherGi2, jgi2: Nat2 _ [LAST[NAT], LAST[NAT]];
        Do1: PROC [de: Dim, Consume1: PROC] = {
            SELECT TRUE FROM
                de # d => {
                    otherGi2[de] _ gi2[de];
                    SELECT TRUE FROM
                        gi2[de] < a.groupingParmses[de].middle.min => jgi2[de] _ gi2[de] / a.jointsPeriod[de];
                        gi2[de] >= a.groupingParmses[de].firstHigh => {
                            lai: NAT = gi2[de] - a.groupingParmses[de].
                            jii: NAT = lai / a.jointsPeriod[de];
                            jgi2[de] _ jii + j.groupingParmses[de].
                        ENDCASE => jgi2[de] _ j.groupingParmses[de].middle.min;
                    Consume1[];
                    };
                side = low => SELECT TRUE FROM
                    gi2[de] < a.groupingParmses[de].middle.min => IF gi2[de]+1 < a.groupingParmses[de].sum THEN {
                        jgi2[de] _ gi2[de] / a.jointsPeriod[de];
                        IF gi2[de]+1 < a.groupingParmses[de].middle.min THEN otherGi2[de] _ gi2[de]+1
                        ELSE IF HasMiddle[a.groupingParmses[de]] THEN otherGi2[de] _ a.groupingParmses[de].middle.min + otherPhase[de]
                        ELSE otherGi2[de] _ a.groupingParmses[de].middle.maxPlusOne;
                        Consume1[];
                        };
                    gi2[de] >= a.groupingParmses[de].firstHigh => IF gi2[de]+1 < a.groupingParmses[de].sum THEN {
                        lai: NAT = gi2[de] - a.groupingParmses[de].
                        jii: NAT = lai / a.jointsPeriod[de];
                        jgi2[de] _ jii + j.groupingParmses[de].
                        otherGi2[de] _ gi2[de] + 1;
                        Consume1[];
                        };
                    ENDCASE => {
                        IF HasMiddle[j.groupingParmses[de]] THEN {
                            otherGi2[de] _ a.groupingParmses[de].middle.min + otherPhase[de];
                            jgi2[de] _ j.groupingParmses[de].middle.min;
                            Consume1[];
                            };
                        IF highPhase[de] = (a.groupingParmses[de].middle.maxPlusOne MOD a.jointsPeriod[de]) AND a.groupingParmses[de].firstHigh < 
                        a.groupingParmses[de].sum THEN {
                            jgi2[de] _ j.groupingParmses[de].firstHigh;
                            otherGi2[de] _ a.groupingParmses[de].firstHigh;
                            Consume1[];
                            };
                        };
                side = high => SELECT TRUE FROM
                    gi2[de] < a.groupingParmses[de].middle.min => IF gi2[de] > 0 THEN {
                        otherGi2[de] _ gi2[de] - 1;
                        jgi2[de] _ otherGi2[de] / a.jointsPeriod[de];
                        Consume1[];
                        };
                    gi2[de] >= a.groupingParmses[de].firstHigh => IF gi2[de] > 0 THEN {
                        lai, jii: NAT;
                        IF gi2[de] > a.groupingParmses[de].firstHigh THEN {
                            otherGi2[de] _ gi2[de]-1;
                            lai _ otherGi2[de] - a.groupingParmses[de].
                            jii _ lai / a.jointsPeriod[de];
                            jgi2[de] _ jii + j.groupingParmses[de].
                            }
                        ELSE IF HasMiddle[a.groupingParmses[de]] THEN {
                            otherGi2[de] _ a.groupingParmses[de].middle.min + otherPhase[de];
                            jgi2[de] _ j.groupingParmses[de].firstHigh;
                            }
                        ELSE {
                            otherGi2[de] _ a.groupingParmses[de].middle.min-1;
                            jgi2[de] _ j.groupingParmses[de].firstHigh;
                            };
                        Consume1[];
                        };
                    ENDCASE => {
                        IF HasMiddle[j.groupingParmses[de]] THEN {
                            otherGi2[de] _ a.groupingParmses[de].middle.min + otherPhase[de];
                            jgi2[de] _ j.groupingParmses[de].middle.min;
                            Consume1[];
                            };
                        IF highPhase[de] = (a.groupingParmses[de].middle.min MOD a.jointsPeriod[de]) AND a.groupingParmses[de].middle.min > 0 THEN {
                            jgi2[de] _ j.groupingParmses[de].middle.min-1;
                            otherGi2[de] _ a.groupingParmses[de].middle.min-1;
                            Consume1[];
                            };
                        };
                ENDCASE => ERROR;
            };
        PerFoo: PROC = {Do1[Bar, PerBoth]};
        PerBoth: PROC = {
            Consume[otherPhase, otherGi2, jgi2, a.groupingParmses[Bar].sum*otherGi2[Foo] + otherGi2[Bar], j.groupingParmses[Bar].sum*jgi2[Foo] 
            + jgi2[Bar], j];
            };
        Do1[Foo, PerFoo];
        }};

    AddTie: PUBLIC PROC [j: Joint, jgi: NAT, tie: Tie] = {
        ties: Set--of Tie-- = Sets.DeRef[j.ties[jgi]];
        IF NOT ties.AddElt[tie] THEN ERROR;
        FOR side: End IN End DO
            last: RefTable--Group 
            g: Group = tie.groups[side];
            IF g # NIL THEN {
                IF NOT last.Insert[g, tie] THEN ERROR;
                };
            ENDLOOP;
        };

    DeleteGroup: PUBLIC PROC [a: Array, g: Group] ~ {
        gs: Groupings ~ NARROW[a.groupingses[ComposeGI[a, g.gi2]]];
        Untie: PROC [d: Dim, phase: Nat2, jgi: NATURAL, jgi2: Nat2, j: Joint, tie: Tie, side: End] ~ {
            IF tie.completion#NIL OR tie.groups[side]#g THEN ERROR;
            IF FetchTie[j, side, jgi, g] # tie THEN ERROR;
            tie.groups[side] _ NIL;
            IF tie.groups = ALL[NIL] THEN DeleteTie[j, jgi, tie];
            };
        places: IntTable ~ NARROW[a.toWire.Fetch[g].val];
        IF places # NIL THEN {
            Unwire: PROC [key: PackedArrayIndex, value: REF ANY] RETURNS [quit: BOOL _ FALSE] --IntHashTable.EachPairAction-- ~ {
                aw: ArrayWire ~ NARROW[value];
                [] _ aw.members.Store[[g, NIL]];
                };
            IF places.Pairs[Unwire] THEN ERROR;
            IF NOT a.toWire.Delete[g] THEN ERROR;
            };
        EnumerateTiesOfGroup[a, g.gi2, g, Untie];
        FOR ports: PortList _ g.ports, ports.rest WHILE ports # NIL DO
            IF gs.toGroup.Fetch[ports.first].val # g THEN ERROR;
            IF NOT gs.toGroup.Delete[ports.first] THEN ERROR;
            ENDLOOP;
        IF NOT gs.groups.RemoveElt[g] THEN ERROR;
        };

    DeleteTie: PUBLIC PROC [j: Joint, jgi: NAT, tie: Tie] = {
        ties: Set--of Tie-- = Sets.DeRef[j.ties[jgi]];
        IF NOT ties.RemoveElt[tie] THEN ERROR;
        FOR side: End IN End DO
            last: RefTable--Group 
            IF tie.groups[side] # NIL AND NOT last.Delete[tie.groups[side]] THEN ERROR;
            ENDLOOP;
        };

    PortPair: TYPE = ARRAY [1 .. 2] OF Port;
    MergeStack: TYPE = LIST OF MergeStackFrame;
    MergeStackFrame: TYPE = RECORD [
        lai: ArrayIndex,
        d: Dim,
        side: End,
        pair: PortPair];

    Merge: PROC [a: Array, d: Dim, lai: ArrayIndex, j: Joint, jgi: NAT, tie: Tie, rpd1, rpd2: SidedPortData, ctii: NAT] = {
        stack: MergeStack _ NIL;
        Consider: PROC [ai: ArrayIndex, d: Dim, eltSide: End, pair: PortPair] = {
            jointSide: End = OtherEnd[eltSide];
            o: Dim = OtherDim[d];
            lai: ArrayIndex = IF eltSide = high THEN ai ELSE Int2Tweak[ai, d, -1];
            IF lai[d] IN [0 .. a.size[d]-1) AND lai[o] IN [0 .. a.size[o]) THEN {
                stack _ CONS[[lai, d, jointSide, pair], stack];
                };
            };
        DO
            jSize: Nat2 = Nat2Tweak[a.size, d, -1];
            clai: INT = jSize[Bar] * lai[Foo] + lai[Bar];
            r1: NAT = GetRoot[a, d, rpd1, clai];
            r2: NAT = GetRoot[a, d, rpd2, clai];
            IF r1 # r2 THEN {
                o: Dim = OtherDim[d];
                hai: Int2 = Int2Tweak[lai, d, 1];
                IF tie.completion[ctii] THEN ERROR;
                FOR side: End IN End DO
                    g: Group = tie.groups[side];
                    ai: ArrayIndex = IF side = low THEN lai ELSE hai;
                    pair: PortPair _ ALL[NIL];
                    otherSide: End = OtherEnd[side];
                    IF rpd1.side = side AND rpd2.side = side THEN pair _ [rpd1.port, rpd2.port]
                    ELSE {
                        IF g # NIL THEN FOR pl: PortList _ g.ports, pl.rest WHILE pl # NIL DO
                            rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
                            r: NAT = GetRoot[a, d, rpd, clai];
                            i: INT = SELECT r FROM r1 => 1, r2 => 2, ENDCASE => 3;
                            IF i IN [1 .. 2] AND pair[i] = NIL THEN {
                                pair[i] _ pl.first;
                                IF pair[3-i] # NIL THEN EXIT};
                            ENDLOOP;
                        };
                    IF pair[1] # NIL AND pair[2] # NIL THEN {
                        Consider[ai, d, side, pair];
                        Consider[ai, o, side, pair];
                        Consider[ai, o, otherSide, pair];
                        };
                    ENDLOOP;
                IF r1 < r2 THEN SetNext[a, d, r2, clai, r1] ELSE SetNext[a, d, r1, clai, r2];
                IF tie.completion[ctii] _ ComputeTieCompleteAt[a, d, tie, clai] THEN {
                    IF (tie.completion.nIncomplete _ tie.completion.nIncomplete - 1) = 0 THEN CompletifyTie[a, d, tie];
                    };
                };
            DO
                IF stack = NIL THEN GOTO Dun;
                {msf: MergeStackFrame = stack.first;
                stack _ stack.rest;
                d _ msf.d;
                lai _ msf.lai;
                {ai: ArrayIndex = IF msf.side = low THEN lai ELSE Int2Tweak[lai, d, 1];
                gi: NAT = ComputeGroupingsIndex[a, ai].gi;
                jii: Nat2 = [
                    Foo: lai[Foo] / a.jointsPeriod[Foo],
                    Bar: lai[Bar] / a.jointsPeriod[Bar]];
                phase: Nat2 = [
                    Foo: lai[Foo] - jii[Foo] * a.jointsPeriod[Foo],
                    Bar: lai[Bar] - jii[Bar] * a.jointsPeriod[Bar]];
                rp1: SidedPort = [msf.side, msf.pair[1]];
                rp2: SidedPort = [msf.side, msf.pair[2]];
                g1: Group = GetGroup[a, gi, rp1.port, TRUE];
                g2: Group = GetGroup[a, gi, rp2.port, TRUE];
                jgi2: Nat2;
                jiir: Range2;
                j _ GetArrayJoint[a, d, phase];
                [jgi2, jgi, ctii, jiir] _ ComputeJointGroupingsIndex[a, j, jii];
                [tie, rpd1, rpd2] _ GetTieAndRPD[a, d, phase, j, jgi2, jgi, jiir, rp1, rp2, g1, g2, gi, gi, TRUE];
                IF tie.completion # NIL THEN EXIT;
                }}ENDLOOP;
            ENDLOOP;
        EXITS
            Dun => a _ a;
        };

    Incompletify: PROC [a: Array, d: Dim, tie: Tie, ntii: NAT] = {
        IF tie.completion # NIL THEN RETURN;
        tie.completion _ NEW [CompletionPrivate[ntii]];
        tie.completion.nIncomplete _ 0;
        FOR tii: NAT IN [0 .. tie.completion.length) DO
            tie.completion[tii] _ TRUE;
            ENDLOOP;
        tie _ tie;
        };

    CompletifyTie: PROC [a: Array, d: Dim, tie: Tie] = {
        IF tie.completion = NIL THEN ERROR;
        tie.completion _ NIL;
        };

    FinishIncompletion: PROC [a: Array, d: Dim, phase: Nat2, tie: Tie, ntii: NAT] = {
        IF tie.completion # NIL THEN ERROR;
        tie.completion _ NEW [CompletionPrivate[ntii]];
        tie.completion.nIncomplete _ ntii;
        FOR ctii: NAT IN [0 .. ntii) DO tie.completion[ctii] _ FALSE ENDLOOP;
        };

    AddLinks: PROC [a: Array, d: Dim, rpd: SidedPortData] = {
        IF rpd.links # NIL THEN ERROR;
        IF rpd.index = 0 THEN RETURN;
        {
        linksNeeded: NAT = Nat2Area[Nat2Tweak[a.size, d, -1]];
        linkSize, wordsNeeded: NAT;
        lgLinksPerWord: Sublg;
        [linkSize, lgLinksPerWord] _ ChooseLinkSize[rpd.index];
        wordsNeeded _ CeilDiv[linkSize * linksNeeded, Basics.bitsPerWord];
        rpd.links _ NEW [LinksPrivate[wordsNeeded]];
        rpd.links.linkSize _ linkSize;
        rpd.links.negLinkSize _ - linkSize;
        rpd.links.negLgLinksPerWord _ - lgLinksPerWord;
        rpd.links.lgLinksPerWord _ lgLinksPerWord;
        FOR clai: NAT IN [0 .. linksNeeded) DO
            SetNext[a, d, rpd.index, clai, rpd.index];
            ENDLOOP;
        rpd _ rpd;
        }};

    ChooseLinkSize: PROC [index: NAT] RETURNS [linkSize: NAT, lgLinksPerWord: Sublg] = {
        SELECT index FROM
            <1 => ERROR;
            <2 => RETURN [1, Basics.logBitsPerWord];
            <4 => RETURN [2, Basics.logBitsPerWord-1];
            <16 => RETURN [4, Basics.logBitsPerWord-2];
            <256 => RETURN [8, Basics.logBitsPerWord-3];
            <=32767 => RETURN [16, Basics.logBitsPerWord-4];
            ENDCASE => ERROR;
        };

    RPDNeedsLinks: PUBLIC PROC [a: Array, d: Dim, rpd: SidedPortData] RETURNS [needs: BOOL] = {
        phase: NAT _ 0;
        needs _ FALSE;
        FOR 
            j: Joint = NARROW[a.joints[d][phase]];
            jgi: NAT _ 0;
            FOR jgif: NAT IN [0 .. j.groupingParmses[Foo].sum) DO
                FOR jgib: NAT IN [0 .. j.groupingParmses[Bar].sum) DO
                    gi: NAT = Jgi2ToGi[a, d, [
                    gs: Groupings = NARROW[a.groupingses[gi]];
                    g: Group = NARROW[gs.toGroup.Fetch[rpd.port].val];
                    IF g # NIL THEN {
                        tie: Tie = FetchTie[j, rpd.side, jgi, g];
                        IF tie # NIL AND tie.completion # NIL THEN RETURN [TRUE];
                        };
                    jgi _ jgi + 1;
                    ENDLOOP;
                ENDLOOP;
            phase _ phase + 1;
            ENDLOOP ENDLOOP;
        needs _ needs;
        };

    GroupCompleteAt: PROC [a: Array, gi: NAT, g: Group, ai: ArrayIndex] RETURNS [complete: BOOL] = {
        complete _ FALSE;
        FOR d: Dim IN Dim DO
            Try: PROC [side: End, lai: ArrayIndex] RETURNS [determined: BOOL] = {
                jii: Nat2 = [lai[Foo]/a.jointsPeriod[Foo], lai[Bar]/a.jointsPeriod[Bar]];
                phase: Nat2 = [lai[Foo] - jii[Foo]*a.jointsPeriod[Foo], lai[Bar] - jii[Bar]*a.jointsPeriod[Bar]];
                j: Joint = GetArrayJoint[a, d, phase];
                jgi: NAT = ComputeJointGroupingsIndex[a, j, jii].jgi;
                tie: Tie = FetchTie[j, side, jgi, g];
                jSize: Nat2 = Nat2Tweak[a.size, d, -1];
                IF tie = NIL THEN RETURN [FALSE];
                complete _  tie.completion = NIL OR ComputeGroupCompleteAt[a, g, jSize[Bar]*lai[Foo]+lai[Bar], d, side];
                determined _ TRUE;
                };
            IF
                (ai[d] < a.size[d]-1 AND Try[low, ai]) OR
                (ai[d] > 0 AND Try[high, Int2Tweak[ai, d, -1]])
                THEN EXIT;
            ENDLOOP;
        RETURN;
        };

    ComputeGroupCompleteAt: PROC [a: Array, g: Group, clai: NAT, d: Dim, side: End--of joint--] RETURNS [complete: BOOL] = {
        root: NAT;
        first: BOOL _ TRUE;
        someNIL, someNonNIL: BOOL _ FALSE;
        complete _ TRUE;
        {FOR pl: PortList _ g.ports, pl.rest WHILE pl # NIL DO
            rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
            r2: NAT;
            IF rpd.index = 0 THEN r2 _ 0
            ELSE IF rpd.links = NIL THEN {r2 _ LAST[NAT]; someNIL _ TRUE}
            ELSE {r2 _ GetRoot[a, d, rpd, clai]; someNonNIL _ TRUE};
            IF first
                THEN {root _ r2; first _ FALSE}
                ELSE IF r2 # root THEN GOTO Fail;
            ENDLOOP;
        EXITS Fail => complete _ FALSE};
        IF someNIL AND someNonNIL THEN ERROR;
        };

    ComputeTieCompleteAt: PUBLIC PROC [a: Array, d: Dim, tie: Tie, clai: NAT] RETURNS [complete: BOOL] = {
        root: NAT;
        first: BOOL _ TRUE;
        someNIL, someNonNIL: BOOL _ FALSE;
        complete _ TRUE;
        {FOR side: End IN End DO
            g: Group = tie.groups[side];
            IF g # NIL THEN FOR pl: PortList _ g.ports, pl.rest WHILE pl # NIL DO
                rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
                r2: NAT;
                IF rpd.index = 0 THEN r2 _ 0
                ELSE IF rpd.links = NIL THEN {r2 _ LAST[NAT]; someNIL _ TRUE}
                ELSE {r2 _ GetRoot[a, d, rpd, clai]; someNonNIL _ TRUE};
                IF first
                    THEN {root _ r2; first _ FALSE}
                    ELSE IF r2 # root THEN GOTO Fail;
                ENDLOOP;
            ENDLOOP;
        EXITS Fail => complete _ FALSE};
        IF someNIL AND someNonNIL THEN ERROR;
        };

    WordPtr: TYPE = LONG POINTER TO WORD;

    GetNext: PUBLIC PROC [rp: SidedPortData, clai: NAT] RETURNS [next: NAT] = TRUSTED {
        IF rp.index = 0 THEN RETURN [rp.index];
        {ls: Links = rp.links;
        wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
        rightShift: INTEGER = ls.negLinkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
        mask: WORD = last[ls.linkSize];
        next _ Basics.BITAND[Basics.BITSHIFT[wordPtr^, rightShift], mask];
        }};

    ArrayEltPortsConnectedByJoint: PUBLIC PROC [a: Array, d: Dim, lowIndex: ArrayIndex, rp1, rp2: SidedPort] RETURNS [hypothetically, 
    really: BOOL] = {
        o: Dim = OtherDim[d];
        IF NOT (lowIndex[d] IN [0 .. a.size[d]-1) AND lowIndex[o] IN [0 .. a.size[o])) THEN RETURN [FALSE, FALSE];
        {phase: Nat2 = [
            Foo: lowIndex[Foo] MOD a.jointsPeriod[Foo],
            Bar: lowIndex[Bar] MOD a.jointsPeriod[Bar]];
        j: Joint = GetArrayJoint[a, d, phase];
        jii: Nat2 = [
            Foo: lowIndex[Foo] / a.jointsPeriod[Foo],
            Bar: lowIndex[Bar] / a.jointsPeriod[Bar]];
        jgi2: Nat2;
        jgi, ctii: NAT;
        jiir: Range2;
        [jgi2, jgi, ctii, jiir] _ ComputeJointGroupingsIndex[a, j, jii];
        {gis: ARRAY End OF NAT = [
            low: Jgi2ToGi[a, d, phase, j, jgi2, low].gi,
            high: Jgi2ToGi[a, d, phase, j, jgi2, high].gi];
        g1: Group = GetGroup[a, gis[rp1.side], rp1.port, FALSE];
        g2: Group = GetGroup[a, gis[rp2.side], rp2.port, FALSE];
        IF g1 = NIL OR g2 = NIL THEN RETURN [FALSE, FALSE];
        {tie1: Tie = FetchTie[j, rp1.side, jgi, g1];
        tie2: Tie = FetchTie[j, rp2.side, jgi, g2];
        jSize: Nat2 = Nat2Tweak[a.size, d, -1];
        IF tie1 # tie2 OR tie1 = NIL THEN RETURN [FALSE, FALSE]
        ELSE IF tie1.completion = NIL THEN RETURN [TRUE, TRUE]
        ELSE {
            rpd1: SidedPortData = FetchRPD[a, d, rp1];
            rpd2: SidedPortData = FetchRPD[a, d, rp2];
            clai: INT = jSize[Bar] * lowIndex[Foo] + lowIndex[Bar];
            really _ GetRoot[a, d, rpd1, clai] = GetRoot[a, d, rpd2, clai];
            hypothetically _ TRUE;
            };
        }}}};

    ArrayEltPortsConnected: PUBLIC PROC [a: Array, ai1, ai2: ArrayIndex, ep1, ep2: Port] RETURNS [hypothetically: BOOL] = {
        gi1: NAT = ComputeGroupingsIndex[a, ai1].gi;
        gi2: NAT = ComputeGroupingsIndex[a, ai2].gi;
        g1: Group = GetGroup[a, gi1, ep1, FALSE];
        g2: Group = GetGroup[a, gi2, ep2, FALSE];
        IF g1 = NIL OR g2 = NIL THEN RETURN [FALSE];
        {aw1: ArrayWire = ArrayWireForGroup[a, ai1, gi1, g1, TRUE];
        aw2: ArrayWire = ArrayWireForGroup[a, ai2, gi2, g2, TRUE];
        RETURN [aw1 = aw2];
        }};

    GroupsHypotheticallyConnected: PUBLIC PROC [a: Array, j: Joint, jgi: NAT, gs: ARRAY End OF Group] RETURNS [BOOL] = {
        Get: PROC [side: End] RETURNS [tie: Tie] = {
            rt: RefTable = NARROW[j.toTie[side][jgi]];
            tie _ NARROW[rt.Fetch[gs[side]].val]};
        RETURN [Get[low] = Get[high]];
        };

    GetRoot: PUBLIC PROC [a: Array, d: Dim, rp: SidedPortData, clai: NAT] RETURNS [root: NAT] = TRUSTED {
        IF rp.index = 0 THEN RETURN [rp.index];
        {ls: Links = rp.links;
        wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
        rightShift: INTEGER = ls.negLinkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
        mask: WORD = last[ls.linkSize];
        next: NAT = Basics.BITAND[Basics.BITSHIFT[wordPtr^, rightShift], mask];
        IF next = rp.index THEN RETURN [rp.index];
        {rp2: SidedPortData = NARROW[a.roles[d].refs[next]];
        IF next # rp2.index THEN ERROR;
        root _ GetRoot[a, d, rp2, clai];
        IF root # next THEN {
            leftShift: INTEGER = - rightShift;
            shiftedMask: WORD = Basics.BITNOT[Basics.BITSHIFT[mask, leftShift]];
            shiftedRoot: WORD = Basics.BITSHIFT[root, leftShift];
            word: WORD = Basics.BITOR[shiftedRoot, Basics.BITAND[shiftedMask, wordPtr^]];
            wordPtr^ _ word;
            };
        }}};

    SetNext: PROC [a: Array, d: Dim, index, clai, next: NAT] = TRUSTED {
        IF index = 0 THEN ERROR;
        {rpd: SidedPortData = NARROW[a.roles[d].refs[index]];
        ls: Links = rpd.links;
        wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
        leftShift: INTEGER = ls.linkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
        shiftedMask: WORD = Basics.BITNOT[Basics.BITSHIFT[last[ls.linkSize], leftShift]];
        shiftedNext: WORD = Basics.BITSHIFT[next, leftShift];
        word: WORD = Basics.BITOR[shiftedNext, Basics.BITAND[shiftedMask, wordPtr^]];
        IF Basics.BITAND[shiftedNext, shiftedMask] # 0 THEN ERROR;
        wordPtr^ _ word;
        }};

    last: ARRAY [0 .. Basics.bitsPerWord] OF WORD = [
        00000H,
        00001H, 00003H, 00007H, 0000FH,
        0001FH, 0003FH, 0007FH, 000FFH,
        001FFH, 003FFH, 007FFH, 00FFFH,
        01FFFH, 03FFFH, 07FFFH, 0FFFFH];

    EnsurePortForGroups: PUBLIC PROC [act: CellType, gis, giis: ARRAY End OF Nat2, gss: GroupListPair] RETURNS [ap: Port] = {
        a: Array = act.asArray;
        ais: ARRAY End OF ArrayIndex = [AgiToAi[a, gis[low], giis[low]], AgiToAi[a, gis[high], giis[high]]];
        Enumerate: PROC [Consume: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOL _ FALSE]] RETURNS [aborted: BOOL] = {
            FOR side: End IN End DO
                FOR gs: GroupList _ gss[side], gs.rest WHILE gs # NIL DO
                    g: Group = gs.first;
                    FOR ps: PortList _ g.ports, ps.rest WHILE ps # NIL DO
                        IF Consume[ais[side], ps.first] THEN RETURN [TRUE];
                        ENDLOOP;
                    ENDLOOP;
                ENDLOOP;
            aborted _ FALSE;
            };
        Search: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOL _ FALSE] = {
            stop _ (NOT Central[a, ai]) AND (ap _ GetArrayPortForPort[act, a, ai, ep, FALSE]) # NIL;
            };
        Export: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOL _ FALSE] = {
            IF NOT Central[a, ai] THEN SetArrayPortForPort[a, ai, ep, ap];
            };
        IF Enumerate[Search] THEN RETURN;
        IF act.port = NIL THEN ERROR --is it true that a cell type always has a port?--;
        ap _ FullyAddPort[[parent: act.port]].port;
        IF Enumerate[Export] THEN ERROR;
        };

    CrossATie: PUBLIC PROC [ct: CellType, d: Dim, fromP: Port, fromS: End] RETURNS [toP: Port] = {
        toS: End = OtherEnd[fromS];
        a: Array = ct.asArray;
        
        
        candidates: PortList _ NIL;
        first: BOOL _ TRUE;
        FOR 
            phase: Nat2 = [
            j: Joint = GetArrayJoint[a, d, phase];
            FOR jgif: NAT IN [0 .. j.groupingParmses[Foo].sum) DO FOR jgib: NAT IN [0 .. j.groupingParmses[Bar].sum) DO
                jgi2: Nat2 = [jgif, jgib];
                jgi: NAT = j.groupingParmses[Bar].sum * jgif + jgib;
                gif: NAT = Jgi2ToGi[a, d, phase, j, jgi2, fromS].gi;
                gf: Group = GetGroup[a, gif, fromP, FALSE];
                IF gf = NIL THEN RETURN [NIL];
                {tie: Tie = FetchTie[j, fromS, jgi, gf];
                IF tie = NIL THEN RETURN [NIL];
                {gt: Group = tie.groups[toS];
                IF gt = NIL THEN NULL
                ELSE IF first THEN {first _ FALSE; candidates _ gt.ports}
                ELSE candidates _ NARROW[GList.Intersection[candidates, gt.ports]];
                IF candidates = NIL THEN RETURN [NIL];
                }}ENDLOOP ENDLOOP;
            ENDLOOP ENDLOOP;
        toP _ IF candidates # NIL THEN candidates.first ELSE NIL;
        };

    Range1Mul: PUBLIC PROC [r: Range, 
        rr _ [
            min: r.min*
            maxPlusOne: r.maxPlusOne*
        };

    Range2Mul: PUBLIC PROC [r: Range2, 
        rr _ [
            Foo: [
                min: r[Foo].min*
                maxPlusOne: r[Foo].maxPlusOne*
            Bar: [
                min: r[Bar].min*
                maxPlusOne: r[Bar].maxPlusOne*
        };

    Range1Div: PUBLIC PROC [r: Range, 
        rr _ [
            min: CeilDiv[r.min-
            maxPlusOne: FloorDiv[r.maxPlusOne-1-
        };

    Range2Div: PUBLIC PROC [r: Range2, 
        rr _ [
            Foo: [
                min: CeilDiv[r[Foo].min-
                maxPlusOne: FloorDiv[r[Foo].maxPlusOne-1-
            Bar: [
                min: CeilDiv[r[Bar].min-
                maxPlusOne: FloorDiv[r[Bar].maxPlusOne-1-
        };

    END.