
    <<LichenDataImplArrays1.Mesa>>
        <<Last tweaked by Mike Spreitzer on August 26, 1988 3:43:49 pm PDT>>

    DIRECTORY AbSets, Basics, BasicTime, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, 
    Rope, SetBasics;

    LichenDataImplArrays1: CEDAR PROGRAM
        IMPORTS AbSets, BiRels, IntStuff, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics
        EXPORTS LichenArrayPrivate, LichenDataStructure, LichenDataOps
        =

    BEGIN OPEN LIB:LichenIntBasics, LIB, LichenDataStructure, LichenDataOps, LichenArrayPrivate, Sets:AbSets;

    CreateArray: PUBLIC PROC [d: Design, eltType: CellType, size, basePeriod: Int2,     names: Set--of ROPE--] RETURNS [act: CellType] ~ {
        act _ CreateCellType[d, array, emptyRange2, names];
        SetArrayPart[act, eltType, CreateArrayPart[act, eltType, size, basePeriod, 
        RETURN};

    SetArrayPart: PUBLIC PROC [act, ect: CellType, a: Array] ~ {
        sizeRange: Range2 ~ SizeRange[a.size2];
        act.asArray _ a;
        [] _ act.d.arrayElt.AddAA[act, ect];
        IF a.offsets=NIL THEN ect _ ect
        ELSE FOR 
            
            c
            div: Range2 ~ Range2Div[sizeRange, a.basePeriod, 
            xfm: Transform ~ VXfm[a.
            IF Range2Empty[div] OR Range2Empty[ect.bbox] THEN act _ act ELSE {
                min: Int2 ~ Mul[Range2Min[div], a.offsets[cf].o1, a.offsets[cf].o0];
                max: Int2 ~ Mul[Range2Max[div], a.offsets[cf].o1, a.offsets[cf].o0];
                act.bbox _ Range2Mbb[act.bbox, Range2Mbb[TransOffRange2[xfm, min, ect.bbox], TransOffRange2[xfm, max, ect.bbox]]];
                a _ a};
            ENDLOOP ENDLOOP;
        a _ a;
        RETURN};

    CreateArrayPart: PUBLIC PROC [act, ect: CellType, size, basePeriod: Int2, 
        d: Design ~ act.d;
        aName: ROPE ~ act.ACtName[];
        svSpace: Sets.Space ~ NEW [SetBasics.SpacePrivate _ [
            Contains: SVContains,
            Equal: SVEqual,
            AHash: SVHash,
            ACompare: SVCompare,
            Print: SVPrint,
            name: Rope.Cat["stat verts of ", aName],
            data: act]];
        paiSpace: Sets.Space ~ NEW [SetBasics.SpacePrivate _ [
            Contains: PAIContains,
            Equal: PAIEqual,
            AHash: PAIHash,
            ACompare: PAICompare,
            Print: PAIPrint,
            name: Rope.Cat["pais of ", aName],
            data: act]];
        edgeSpace: Sets.Space ~ NEW [SetBasics.SpacePrivate _ [
            Contains: SEContains,
            Equal: SetBasics.reps.Equal,
            AHash: SetBasics.reps.AHash,
            ACompare: SetBasics.reps.ACompare,
            Print: SEPrint,
            name: Rope.Cat["stat edges of ", aName],
            data: act]];
        a: Array ~ NEW [ArrayPrivate _ [
            size2: size,
            size: Area[size],
            basePeriod: basePeriod,
            
            offsets: offsets,
            connToPhys: [],
            statrep: NEW [StatRepPrivate _ [
                edgeSpace: edgeSpace, paiSpace: paiSpace, svSpace: svSpace,
                svNameOrder: [SVNameCompare, TRUE, FALSE, act],
                edgeNameOrder: [SENameCompare, TRUE, FALSE, act],
                edges: Sets.CreateHashSet[edgeSpace],
                paiToEP: BiRels.FnFromProc[PaiExtract, [paiSpace, d.eSpace], $p, TRUE],
                paiToX: BiRels.FnFromProc[PaiExtract, [paiSpace, SetBasics.ints], $x, TRUE],
                paiToY: BiRels.FnFromProc[PaiExtract, [paiSpace, SetBasics.ints], $y, TRUE],
                portEdge: [
                    FALSE: BiRels.CreateHashReln[spaces: [d.eSpace, edgeSpace], functional: [FALSE, TRUE]],
                    TRUE: BiRels.CreateHashReln[spaces: [d.eSpace, edgeSpace], functional: [FALSE, TRUE]]
                    ],
                svEdge: [
                    FALSE: BiRels.CreateHashReln[spaces: [svSpace, edgeSpace], functional: [FALSE, TRUE]],
                    TRUE: BiRels.CreateHashReln[spaces: [svSpace, edgeSpace], functional: [FALSE, TRUE]]
                    ],
                apToPAI: BiRels.CreateHashFn[[d.eSpace, paiSpace]]
                ]]
            ]];
        IF 
            IF 
            IF offsets#NIL THEN {
                o00: Int2 ~ EltCtr[a, ect, [0, 0]];
                FOR dim: Dim2 IN Dim2 DO
                    IF size[dim]>1 THEN {
                        on: Int2 ~ EltCtr[a, ect, ConsInt2[dim, size[dim]-1, 0]];
                        a.connToPhys.mirror[dim] _ on[dim] < o00[dim]};
                    ENDLOOP;
                offsets _ offsets}};
        RETURN [a]};

    PaiExtract: PROC [data: REF ANY, v: Sets.Value] RETURNS [mv: Sets.MaybeValue] ~ {
        pai: PortAtIndex ~ VPai[v];
        SELECT data FROM
            $p => RETURN [[TRUE, AV[pai.port] ]];
            $x => RETURN [[TRUE, IV[pai.ai[X]] ]];
            $y => RETURN [[TRUE, IV[pai.ai[Y]] ]];
            ENDCASE => ERROR};

    SVContains: PUBLIC PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
        WITH v.ra SELECT FROM
            port: Port => RETURN [TRUE];
            ENDCASE => RETURN [FALSE]};

    SVHash: PROC [data: REF ANY, v: Sets.Value] RETURNS [CARDINAL] ~ {
        act: CellType ~ NARROW[data];
        sv: StatVertex ~ VSv[v];
        RETURN [act.d.eSpace.SHash[AV[sv.port]] + Int2Hash[sv.phase]]};

    SVEqual: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [BOOL] ~ {
        RETURN [SVCompare[data, v1, v2]=equal]};

    SVCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
        act: CellType ~ NARROW[data];
        sv1: StatVertex ~ VSv[v1];
        sv2: StatVertex ~ VSv[v2];
        IF (c _ act.d.eSpace.SCompare[AV[sv1.port], AV[sv2.port]]) # equal THEN RETURN;
        c _ Int2Compare[sv1.phase, sv2.phase];
        RETURN};

    SVNameCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
        act: CellType ~ NARROW[data];
        ect: CellType ~ act.EltType[];
        sv1: StatVertex ~ VSv[v1];
        sv2: StatVertex ~ VSv[v2];
        IF (c _ ect.nameOrder[p].PCompare[AV[sv1.port], AV[sv2.port]]) # equal THEN RETURN;
        c _ Int2Compare[sv1.phase, sv2.phase];
        RETURN};

    SVPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
        act: CellType ~ NARROW[data];
        sv: StatVertex ~ VSv[v];
        act.d.eSpace.SPrint[AV[sv.port], to, depth, length, verbose];
        PrintQual[to, "~", act.asArray.basePeriod, sv.phase];
        RETURN};

    PAIContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
        WITH v.ra SELECT FROM
            port: Port => RETURN [TRUE];
            ENDCASE => RETURN [FALSE]};

    PAIHash: PROC [data: REF ANY, v: Sets.Value] RETURNS [CARDINAL] ~ {
        act: CellType ~ NARROW[data];
        pai: PortAtIndex ~ VPai[v];
        RETURN [act.d.eSpace.SHash[AV[pai.port]] + Int2Hash[pai.ai]]};

    PAIEqual: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [BOOL] ~ {
        RETURN [PAICompare[data, v1, v2]=equal]};

    PAICompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
        act: CellType ~ NARROW[data];
        pai1: PortAtIndex ~ VPai[v1];
        pai2: PortAtIndex ~ VPai[v2];
        IF (c _ act.d.eSpace.SCompare[AV[pai1.port], AV[pai2.port]]) # equal THEN RETURN;
        c _ Int2Compare[pai1.ai, pai2.ai];
        RETURN};

    PAIPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
        act: CellType ~ NARROW[data];
        pai: PortAtIndex ~ VPai[v];
        act.d.eSpace.SPrint[AV[pai.port], to, depth, length, verbose];
        PrintQual[to, "@", act.asArray.size2, pai.ai];
        RETURN};

    SEContains: PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
        IF v.i#0 THEN RETURN [FALSE];
        WITH v.ra SELECT FROM
            se: StatEdge => RETURN [TRUE];
            ENDCASE => RETURN [FALSE]};

    increasingSERank: PUBLIC Sets.Order ~ [SERankCompare, TRUE, FALSE, $up];
    decreasingSERank: PUBLIC Sets.Order ~ [SERankCompare, TRUE, FALSE, $dn];

    SERankCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [SetBasics.TotalComparison] ~ {
        se1: StatEdge ~ NARROW[v1.VA];
        se2: StatEdge ~ NARROW[v2.VA];
        SELECT data FROM
            $up => RETURN SetBasics.CompareIntI[se1.rank, se2.rank];
            $dn => RETURN SetBasics.CompareIntI[se2.rank, se1.rank];
            ENDCASE => ERROR};

    SENameCompare: PROC [data: REF ANY, v1, v2: Sets.Value] RETURNS [c: SetBasics.TotalComparison] ~ {
        act: CellType ~ NARROW[data];
        sr: StatRep ~ act.asArray.statrep;
        se1: StatEdge ~ NARROW[v1.VA];
        se2: StatEdge ~ NARROW[v2.VA];
        IF (c _ sr.svNameOrder.PCompare[se1.SeRSvV[sr, FALSE], se2.SeRSvV[sr, FALSE]]) # equal THEN RETURN;
        IF (c _ sr.svNameOrder.PCompare[se1.SeRSvV[sr, TRUE], se2.SeRSvV[sr, TRUE]]) # equal THEN RETURN;
        c _ Int2Compare[se1.
        RETURN};

    SEPrint: PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
        act: CellType ~ NARROW[data];
        sr: StatRep ~ act.asArray.statrep;
        se: StatEdge ~ NARROW[v.VA];
        sr.svSpace.SPrint[se.SeRSvV[sr, FALSE], to, depth-1, length, verbose];
        to.PutRope[" -> "];
        sr.svSpace.SPrint[se.SeRSvV[sr, TRUE], to, depth-1, length, verbose];
        PrintQual[to, " by ", act.asArray.size2, se.
        RETURN};

    DWContains: PUBLIC PROC [data: REF ANY, v: Sets.Value] RETURNS [BOOL] ~ {
        IF v.i#0 THEN RETURN [FALSE];
        WITH v.ra SELECT FROM
            dw: DumbWire => RETURN [TRUE];
            ENDCASE => RETURN [FALSE];
        };

    DWPrint: PUBLIC PROC [data: REF ANY, v: Sets.Value, to: IO.STREAM, depth, length: INT, verbose: BOOL] ~ {
        act: CellType ~ NARROW[data];
        dw: DumbWire ~ NARROW[v.VA];
        pai: PortAtIndex ~ SomePAI[act, dw];
        IF pai.port#NIL THEN {
            to.PutRope["{"];
            act.d.eSpace.SPrint[AV[pai.port], to, depth, length, verbose];
            PrintQual[to, "@", act.asArray.size2, pai.ai];
            to.PutRope["}"]}
        ELSE to.PutF["%bB", [cardinal[LOOPHOLE[dw]]]];
        RETURN};

    PrintQual: PROC [to: IO.STREAM, intro: ROPE, size2, qual: Int2] ~ {
        IF size2[X]=1
            THEN IF size2[Y]=1
                THEN NULL
                ELSE to.PutF["%g%g", [rope[intro]], [integer[qual[Y]]]]
            ELSE IF size2[Y]=1
                THEN to.PutF["%g%g", [rope[intro]], [integer[qual[X]]]]
                ELSE to.PutF["%g<%g,%g>", [rope[intro]], [integer[qual[X]]], [integer[qual[Y]]]];
        };

    ScanStatEdgesFrom: PUBLIC PROC [sr: StatRep, from: StatVertex, start: ARRAY BOOL OF BOOL, Test: PROC [se: StatEdge, ob: BOOL] 
    RETURNS [BOOL]] RETURNS [found: BOOL _ FALSE, se: StatEdge _ NIL, ob: BOOL _ FALSE] ~ {
        FOR ob IN BOOL DO
            sb: BOOL ~ NOT ob;
            TestEdge: PROC [ra: Sets.Value] RETURNS [pass: BOOL] ~ {
                se: StatEdge ~ NARROW[ra.VA];
                pass _ Test[se, ob];
                RETURN};
            IF start[sb] THEN {
                mp: BiRels.MaybePair ~ sr.svEdge[sb].ScanMapping[SvV[from], TestEdge];
                IF mp.found THEN RETURN [TRUE, NARROW[mp.it[right].VA], ob]};
            ENDLOOP;
        RETURN};

    RedundantEdge: PUBLIC PROC [act: CellType, avoid: StatEdge, a: Array, sep: StatEdgeSpec] RETURNS [redundant: BOOL] ~ {
        range: Range2 ~ Int2sRange[ALL[0], sep.
        seen: Set ~ Sets.CreateHashSet[a.statrep.paiSpace];
        goal: PortAtIndex ~ [sep.vs[TRUE].port, sep.
        SearchFrom: PROC [src: PortAtIndex] RETURNS [ans: BOOL] ~ {
            TryEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [BOOL] ~ {
                IF se=avoid THEN RETURN [FALSE];
                {dest: PortAtIndex ~ [se.SeP[a, ob], IF ob THEN LIB.Add[src.ai, se.
                IF dest = goal THEN RETURN [TRUE];
                RETURN [InRange[dest.ai, range] AND SearchFrom[dest]]}};
            IF NOT seen.AddElt[PaiV[src]] THEN RETURN [FALSE];
            ans _ ScanStatEdgesFrom[a.statrep, [src.port, Mod[src.ai, a.basePeriod]], ALL[TRUE], TryEdge].found;
            IF NOT seen.RemElt[PaiV[src]] THEN ERROR;
            RETURN};
        IF sep.
        redundant _ SearchFrom[[sep.vs[FALSE].port, ALL[0]]];
        RETURN};

    TrimStatrep: PUBLIC PROC [act: CellType, a: Array, edges: Set--of StatEdge-- _ nilSet] ~ {
        CheckEdge: PROC [ev: Sets.Value] RETURNS [BOOL] ~ {
            se: StatEdge ~ NARROW[ev.VA];
            IF NOT a.statrep.edges.HasMember[ev] THEN RETURN [FALSE];
            IF NOT RedundantEdge[act, se, a, se.SeSp[a.statrep]] THEN {
                IF se.
                RETURN [FALSE]};
            RemStatEdge[act.d, a.statrep, se.SeSp[a.statrep]];
            RETURN [FALSE]};
        IF edges=nilSet THEN edges _ a.statrep.edges;
        IF edges.Scan[CheckEdge].found THEN ERROR;
        RETURN};
        nTough: INT _ 0;

    CreateBareDumbWire: PUBLIC PROC [act: CellType] RETURNS [DumbWire] ~ {
        RETURN [NEW [DumbWirePrivate _ [
            eps: BiRels.GenCreate[
                spaces: [act.d.eSpace, SetBasics.ints],
                mappable: [TRUE, TRUE],
                hints: [
                    leftToRight: [
                        fn: [$Hash],
                        set: [$Vector, LIST[
                            [$Bounds, NEW [SetBasics.IntInterval _ [0, act.asArray.size-1]] ]
                            ]]],
                    rightToLeft: [
                        set: [$Hash],
                        fn: [$Vector]] ]]
            ]]]};

    CreateDumbWireKids: PUBLIC PROC [a: Array, len: LNAT] RETURNS [Seq--of DumbWire--] ~ {
        RETURN BiRels.CreateVector[
            bounds: [0, len],
            rightSpace: a.dumrep.dwSpace]};

    NoteNewArrayPort: PUBLIC PROC [act: CellType, ap: Port] ~ {
        d: Design ~ act.d;
        a: Array ~ act.asArray;
        portKids: Seq--of Port-- ~ d.SubSeq[ap];
        dumKids: Seq--of DumbWire-- ~ portKids.Compose[a.dumrep.apToWire];
        width: LNAT ~ portKids.Size.EN;
        pdw: DumbWire;
        IF a.buildPhase#statrepFixed THEN ERROR;
        IF portKids=nilBiRel THEN ERROR;
        IF width=0 THEN ERROR;
        IF width # dumKids.Size.EN THEN RETURN;
        FOR i: LNAT IN [0 .. width) DO
            WITH dumKids.ApplyI[i].MA SELECT FROM
                cdw: DumbWire => {
                    IF cdw.parent=NIL THEN RETURN;
                    IF i=0 THEN {IF (pdw _ cdw.parent).children.Size.EN # width THEN RETURN}
                    ELSE IF pdw#cdw.parent THEN RETURN;
                    IF cdw.index # i THEN RETURN};
                ENDCASE => RETURN;
            ENDLOOP;
        {pai: PortAtIndex ~ act.SomePAI[pdw];
        IF pai.port=NIL THEN ERROR;
        a.statrep.apToPAI.AddNewPair[[AV[ap], pai.PaiV]];
        a.dumrep.apToWire.AddNewAA[ap, pdw];
        RETURN}};

    NoteNewEltPort: PUBLIC PROC [act: CellType, ep: Port] ~ {
        IF act.d.Atomic[ep] THEN RETURN;
        {d: Design ~ act.d; a: Array ~ act.asArray;
        width: LNAT ~ d.Width[ep];
        cp0: Port ~ NARROW[d.Sub[ep, 0]];
        TryUpEdge: PROC [se: StatEdge, ob: BOOL] RETURNS [BOOL] ~ {
            parentSEP: StatEdgeSpec ~ ParentSEP[d, se.SeSp[a.statrep]];
            sb: BOOL ~ NOT ob;
            oep: Port ~ parentSEP.vs[ob].port;
            IF parentSEP.vs[sb].port # ep THEN ERROR;
            IF oep = NIL THEN RETURN [FALSE];
            IF d.Width[oep] # width THEN RETURN [FALSE];
            IF d.Sub[oep, 0] # se.SeP[a, ob] THEN RETURN [FALSE];
            FOR i: LNAT IN [1 .. width) DO
                IF FindStatEdge[a.statrep, ChildSEP[d, parentSEP, i], FALSE].fse = NIL THEN RETURN [FALSE];
                ENDLOOP;
            {pse: StatEdge ~ EnsureStatEdge[d, a.statrep, parentSEP, FALSE, TRUE, FALSE];
            IF pse=NIL OR FindStatEdge[a.statrep, parentSEP, FALSE].fse#pse THEN ERROR;
            SELECT a.buildPhase FROM
                buildingStatrep => NULL;
                statrepFixed => DumbifyStatEdge[act, pse, TRUE];
                ENDCASE => ERROR;
            RETURN [FALSE]}};
        FOR 
            IF ScanStatEdgesFrom[a.statrep, [cp0, [
            ENDLOOP ENDLOOP;
        RETURN}};

    SeSp: PUBLIC PROC [se: StatEdge, sr: StatRep] RETURNS [StatEdgeSpec]
        ~ {RETURN [[vs: [se.SeRSv[sr, FALSE], se.SeRSv[sr, TRUE]], 

    END.