
    <<LichenDataImplArrays3.Mesa>>
        <<Last tweaked by Mike Spreitzer on August 15, 1988 4:23:11 pm PDT>>

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

    LichenDataImplArrays3: CEDAR PROGRAM
        IMPORTS AbSets, BiRelBasics, BiRels, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, SetBasics
        EXPORTS LichenDataOps
        =

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

    MayDeletePorts: PUBLIC PROC [ct: CellType, ports: Set--of port--, timid, isWholeTrees: BOOL] RETURNS [whyNot: ROPE _ NIL] ~ {
        d: Design ~ ct.d;
        PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ {
            act: CellType ~ NARROW[actv.VA];
            a: Array ~ act.asArray;
            verts: Set--of StatVertex-- ~ Sets.CreateHashSet[a.statrep.svSpace];
            edges: Set ~ a.statrep.portEdge[FALSE].Image[ports] .Union[a.statrep.portEdge[TRUE].Image[ports]];
            CheckEdge: PROC [sev: Sets.Value] RETURNS [BOOL] ~ {
                se: StatEdge ~ NARROW[sev.VA];
                FOR b: BOOL IN BOOL DO
                    sv: StatVertex ~ se.SeSv[a, b];
                    IF ports.HasMemA[sv.port] THEN {
                        IF sv#se.SeSv[a, NOT b] AND NOT verts.AddElt[SvV[sv]] --this test is stronger than it needs to be, but maybe there's no arising 
                        case that exercises the difference-- THEN {
                            whyNot _ IO.PutFR["deleting static vertex %g@%g,%g in %g might partition a component", [rope[Describe[d, sv.port, ct]]], 
                            [integer[sv.phase[X]]], [integer[sv.phase[Y]]], [rope[Describe[d, act, d]]]];
                            RETURN [TRUE]}};
                    ENDLOOP;
                RETURN [FALSE]};
            [] _ edges.Scan[CheckEdge];
            IF whyNot#NIL THEN RETURN [TRUE];
            {losers, abandoned: Set;
            [losers, abandoned] _ ArrayLosers[act, ports, FALSE];
            IF NOT timid THEN ERROR --not implemented--;
            IF NOT abandoned.Empty THEN whyNot _ IO.PutFR["would abandon ports %g of %g", [rope[abandoned.FormatSet[length: INT.LAST, order: 
            act.nameOrder[p]]]], [rope[act.ACtName[]]]]
            ELSE whyNot _ MayDeletePorts[act, losers, timid, TRUE];
            RETURN [whyNot#NIL]}};
        IF NOT isWholeTrees THEN ERROR --case not implemented--;
        [] _ d.arrayElt.ScanMapping[AV[ct], PerArray, rightToLeft];
        RETURN};

    NoteExEltPorts: PUBLIC PROC [ect: CellType, eps: Set, mayHaveConsequences: BOOL, log: IO.STREAM _ NIL] ~ {
        d: Design ~ ect.d;
        PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ {
            act: CellType ~ NARROW[actv.VA];
            a: Array ~ act.asArray;
            edges: Set ~ a.statrep.portEdge[FALSE].Image[eps] .Union[a.statrep.portEdge[TRUE].Image[eps]] .CreateHashCopy[];
            losers, abandoned: Set;
            IF a.buildPhase # statrepFixed THEN ERROR;
            [losers, abandoned] _ ArrayLosers[act, eps, TRUE];
            IF NOT abandoned.Empty THEN ERROR --shouldn't arise--;
            {notLosers: Set ~ losers.Negate;
            Undumb: PROC [epv: Sets.Value] RETURNS [BOOL] ~ {
                ep: Port ~ NARROW[epv.VA];
                dws: REF Fn ~ NARROW[a.dumrep.epToWire.Apply[epv].MDA];
                PerWire: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
                    dw: DumbWire ~ NARROW[dwv.VA];
                    IF NOT dw.eps.DeleteA[ep] THEN ERROR;
                    IF dw.eps.Empty THEN {
                        aps: Set ~ a.dumrep.epToWire.Mapping[AV[dw], rightToLeft];
                        IF NOT aps.Intersection[notLosers].Empty THEN ERROR;
                        IF NOT a.dumrep.wires.RemA[dw] THEN ERROR;
                        --let DeletePorts[aps] fix apToWire--};
                    RETURN [FALSE]};
                IF dws#NIL AND dws^.SetOn[right].Scan[PerWire].found THEN ERROR;
                RETURN [FALSE]};
            [] _ a.statrep.edges.RemSet[edges] --AAASEP says we don't have to worry about creating the child edges, if any--;
            [] _ a.statrep.portEdge[FALSE].DeleteSet[edges, right];
            [] _ a.statrep.portEdge[TRUE].DeleteSet[edges, right];
            [] _ a.statrep.svEdge[FALSE].DeleteSet[edges, right];
            [] _ a.statrep.svEdge[TRUE].DeleteSet[edges, right];
            IF a.buildPhase = statrepFixed THEN {
                IF eps.Scan[Undumb].found THEN ERROR;
                [] _ a.dumrep.epToWire.DeleteSet[eps]};
            IF NOT losers.Empty THEN {
                IF NOT mayHaveConsequences THEN ERROR;
                IF log#NIL THEN log.PutF["DelPs %g of %g exded.\n", [rope[losers.FormatSet[length: INT.LAST, order: act.nameOrder[p]]]], 
                [rope[Describe[d, act, d]]]];
                DeletePorts[act, losers, TRUE, FALSE, log];
                log _ log};
            RETURN [FALSE]}};
        [] _ d.arrayElt.ScanMapping[AV[ect], PerArray, rightToLeft];
        RETURN};

    NoteEltPortMerge: PUBLIC PROC [ect: CellType, kept: Port, lost: Set--of port--] ~ {
        d: Design ~ ect.d;
        PerArray: PROC [actv: Sets.Value] RETURNS [BOOL] ~ {
            act: CellType ~ NARROW[actv.VA];
            a: Array ~ act.asArray;
            kdws: REF Fn _ GetDumbWires[a, kept, FALSE];
            PerLoser: PROC [lv: Sets.Value] RETURNS [BOOL] ~ {
                loser: Port ~ NARROW[lv.VA];
                ldws: REF Fn ~ GetDumbWires[a, loser, FALSE];
                FixDW: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
                    dw: DumbWire ~ NARROW[dwv.VA];
                    dw.eps.SubstituteA[loser, kept, left];
                    RETURN [FALSE]};
                IF ldws#NIL THEN {
                    IF kdws=NIL THEN kdws _ GetDumbWires[a, kept, TRUE];
                    {had: BiRels.HadSetPair ~ kdws^.AddSet[ldws^, BiRels.addIfNew];
                    IF had[leftToRight][different] THEN ERROR;
                    IF ldws^.SetOn[right].Scan[FixDW].found THEN ERROR;
                    IF NOT a.dumrep.epToWire.DeleteA[loser] THEN ERROR}};
                RETURN [FALSE]};
            FixEdge: PROC [ev: Sets.Value] RETURNS [BOOL] ~ --probably relies on AAASEP-- {
                se: StatEdge ~ NARROW[ev.VA];
                FOR b: BOOL IN BOOL DO
                    sv: StatVertex ~ se.SeSv[a, b];
                    IF lost.HasMemA[sv.port] THEN {
                        [] _ a.statrep.portEdge[b].AddAA[kept, se];
                        [] _ a.statrep.svEdge[b].AddPair[[SvV[[kept, sv.phase]], AV[se]]]};
                    ENDLOOP;
                RETURN [FALSE]};
            FixExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
                pai: PortAtIndex ~ VPai[pair[right]];
                IF lost.HasMemA[pai.port] THEN {
                    had: BiRels.HadPair ~ a.statrep.apToPAI.AddPair[[pair[left], PaiV[[kept, pai.ai]]], BiRels.addIfOld];
                    IF had[leftToRight] # different THEN ERROR};
                RETURN [FALSE]};
            edges: Set ~ a.statrep.portEdge[FALSE].Image[lost] .Union[a.statrep.portEdge[TRUE].Image[lost]] .CreateHashCopy[];
            IF a.buildPhase # statrepFixed THEN ERROR;
            IF lost.Scan[PerLoser].found THEN ERROR;
            IF edges.Scan[FixEdge].found THEN ERROR;
            IF a.statrep.apToPAI.Scan[FixExport].found THEN ERROR;
            TrimStatrep[act, a, edges];
            RETURN [FALSE]};
        [] _ d.arrayElt.ScanMapping[AV[ect], PerArray, rightToLeft];
        RETURN};

    ArrayLosers: PROC [act: CellType, eps: Set, replace: BOOL] RETURNS [losers, abandoned: Set] ~ {
        d: Design ~ act.d; a: Array ~ act.asArray;
        starts: Set ~ Sets.CreateHashSet[d.eSpace];
        roots: Set ~ Sets.CreateHashSet[d.eSpace];
        cousins: Set ~ d.ancest.Image[roots, rightToLeft];
        CheckExport: PROC [pair: BiRels.Pair] RETURNS [BOOL] ~ {
            pai: PortAtIndex ~ VPai[pair[right]];
            IF eps.HasMemA[pai.port] THEN {
                ap: Port ~ NARROW[pair[left].VA];
                dw: DumbWire ~ NARROW[a.dumrep.apToWire.ApplyA[ap].MA];
                repl: Port ~ NARROW[dw.eps.SetOn[left].Difference[eps].AnElt.MDA];
                IF repl=NIL THEN {[] _ starts.AddA[ap]; [] _ roots.AddA[d.PWRoot[ap]]}
                ELSE IF replace THEN {
                    epcai: BiRels.Pair ~ dw.eps.ScanMapping[AV[repl], Sets.AcceptAny].P;
                    cai: NAT ~ epcai[right].VI;
                    ai: Int2 ~ DecomposeAI[a, cai];
                    IF epcai[left] # AV[repl] THEN ERROR;
                    [] _ a.statrep.apToPAI.AddPair[[AV[ap], PaiV[[repl, ai]] ]]};
                };
            RETURN [FALSE]};
        IF a.buildPhase # statrepFixed THEN ERROR;
        IF a.statrep.apToPAI.Scan[CheckExport].found THEN ERROR;
        losers _ d.ancest.Image[starts].CreateHashCopy[];
        abandoned _ cousins.Difference[losers];
        RETURN};

    intSets: Sets.Space ~ Sets.CreateSetSpace[SetBasics.ints];

    TryToMergeDumbWires: PUBLIC PROC [d: Design, act: CellType, wires: Set] RETURNS [balks: Set] ~ {
        a: Array ~ act.asArray;
        balks _ Sets.CreateHashSet[a.dumrep.dwSpace];
        IF wires.Trivial THEN RETURN;
        DO
            AddEdge: PROC [sep: StatEdgeSpec] ~ {
                [] _ EnsureStatEdge[d, a.statrep, sep, FALSE, TRUE, FALSE];
                RETURN};
            anDw: DumbWire ~ NARROW[wires.AnElt.MA];
            dumby: DumbWire ~ CreateBareDumbWire[act];
            losers: Set ~ wires.Difference[Sets.CreateSingleA[anDw, a.dumrep.dwSpace]];
            StartDumb: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
                dw: DumbWire ~ NARROW[dwv.VA];
                [] _ dumby.eps.AddSet[dw.eps];
                IF dw.children#nilBiRel THEN ERROR;
                IF dw.parent#NIL THEN ERROR;
                RETURN [FALSE]};
            FixExport: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
                dw: DumbWire ~ NARROW[dwv.VA];
                IF dw#anDw THEN a.dumrep.apToWire.SubstituteA[dw, anDw, right];
                RETURN [FALSE]};
            IF wires.Scan[StartDumb].found THEN ERROR;
            {givenCai: Set ~ dumby.eps.SetOn[right];
            splort: BOOL ~ givenCai.NonTrivial;
            allCai: Set ~ IF splort THEN Sets.IIAsSet[[0, a.size-1]] ELSE Sets.CreateSingleton[givenCai.TheElt, SetBasics.ints];
            allEp: Set ~ a.dumrep.epw.Image[wires, rightToLeft].CreateHashCopy[];
            allEps: BiRel ~ BiRels.CreateProduct[[allEp, allCai]];
            missedEps: BiRel ~ allEps.Difference[dumby.eps];
            IF missedEps.NonEmpty THEN {
                missedEp: Set ~ missedEps.SetOn[left].CreateHashCopy[];
                theirWires: Set ~ a.dumrep.epw.Image[missedEp];
                ourLosses: Set ~ wires.Intersection[theirWires].CreateHashCopy[];
                [] _ balks.AddSet[ourLosses];
                [] _ wires.RemSet[ourLosses];
                IF wires.Trivial THEN RETURN ELSE LOOP};
            IF wires.Scan[FixExport].found THEN ERROR;
            {edges: Set ~ a.statrep.portEdge[FALSE].Image[allEp] .Union[a.statrep.portEdge[TRUE].Image[allEp]] .CreateHashCopy[];
            theCai: CompositeArrayIndex ~ givenCai.AnElt.MI;
            theAi: Int2 ~ DecomposeAI[a, theCai];
            thePhase: Int2 ~ Mod[theAi, a.basePeriod];
            anEp: Port ~ NARROW[anDw.eps.SetOn[left].AnElt.MA];
            epSofar: Set ~ Sets.CreateHashSet[d.eSpace];
            caiSofar: Set _ Sets.CreateSingleI[theCai, SetBasics.ints];
            epsSofar: BiRel _ BiRels.CreateProduct[[epSofar, caiSofar]];
            splable: BOOL _ splort;
            FinishDumb: PROC [dwv: Sets.Value] RETURNS [BOOL] ~ {
                dw: DumbWire ~ NARROW[dwv.VA];
                missedEps: Set ~ dw.eps.SetOn[left].Difference[epSofar];
                DO
                    missedEp: Port ~ NARROW[missedEps.AnElt.MDA];
                    IF missedEp#NIL THEN {
                        IF splort THEN FOR 
                            AddEdge[[vs: [[anEp, [
                            ENDLOOP ENDLOOP
                        ELSE AddEdge[[vs: [[anEp, thePhase], [missedEp, thePhase]], 
                        IF NOT epSofar.AddA[missedEp] THEN ERROR;
                        LOOP};
                    IF NOT splable THEN EXIT;
                    {missedCaiMv: Sets.MaybeValue ~ dw.eps.SetOn[right].Difference[caiSofar].AnElt;
                    IF NOT missedCaiMv.found THEN EXIT;
                    {missedAi: Int2 ~ DecomposeAI[a, missedCaiMv.it.VI];
                    mep: Port ~ NARROW[dw.eps.Mapping[missedCaiMv.it, rightToLeft].AnElt.MA];
                    doDim: ARRAY Dim2 OF BOOL ~ [a.size2[X]>1, a.size2[Y]>1];
                    FOR dim: Dim2 IN Dim2 DO
                        IF doDim[dim] THEN FOR 
                            delta: Int2 ~ ConsInt2[dim, 1, 0];
                            
                            IF a.size2[dim]>
                            ENDLOOP ENDLOOP;
                        ENDLOOP;
                    splable _ FALSE;
                    caiSofar _ allCai;
                    }}ENDLOOP;
                RETURN [FALSE]};
            FinishEP: PROC [epv: Sets.Value] RETURNS [BOOL] ~ {
                ep: Port ~ NARROW[epv.VA];
                dws: Fn--composite array index 
                [] _ dws.AddSet[BiRels.CreateProduct[[allCai, Sets.CreateSingleA[anDw, a.dumrep.dwSpace]]]];
                RETURN [FALSE]};
            IF NOT epSofar.AddA[anEp] THEN ERROR;
            IF wires.Scan[FinishDumb].found THEN ERROR;
            IF allEp.Scan[FinishEP].found THEN ERROR;
            [] _ anDw.eps.AddSet[allEps];
            IF NOT a.dumrep.wires.RemSet[losers].had.all THEN ERROR;
            TrimStatrep[act, a, edges];
            RETURN}};
            ENDLOOP;
        };

    END.