
    <<LichenArrayRecovery.Mesa>>
        <<Last tweaked by Mike Spreitzer on July 18, 1988 10:51:21 pm PDT>>

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

    LichenArrayRecovery: CEDAR PROGRAM
        IMPORTS AbSets, BasicTime, BiRels, IO, LichenArrayPrivate, LichenDataOps, LichenDataStructure, LichenIntBasics, Rope, SetBasics
        =

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

    MinimizeArraysPeriod: PROC [d: Design, cts: Set--of CellType--, pacify: IO.STREAM] RETURNS [report: Fn--CellType 
        PerCT: PROC [ctv: Sets.Value] RETURNS [BOOL] ~ {
            ct: CellType ~ NARROW[ctv.VA];
            start: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
            IF pacify#NIL THEN pacify.PutRope[Describe[d, ct]];
            {period: Int2 ~ MinimizeArrayPeriod[ct];
            report.AddNewPair[[AV[ct], I2V[period]]];
            IF pacify#NIL THEN {
                end: BasicTime.Pulses ~ BasicTime.GetClockPulses[];
                pacify.PutF[" %g\n", [real[BasicTime.PulsesToSeconds[end-start]]]]};
            RETURN [FALSE]}};
        report _ BiRels.CreateHashTable[[d.eSpace, int2s]];
        IF cts.Scan[PerCT].found THEN ERROR;
        RETURN};

    MinimizeArrayPeriod: PROC [act: CellType] RETURNS [Int2] ~ {
        d: Design ~ act.d;
        a: Array ~ act.asArray;
        sr: StatRep ~ a.statrep;
        CheckDown: PROC [sev: Sets.Value] RETURNS [BOOL] ~ {
            se: StatEdge ~ NARROW[sev.VA];
            sep: StatEdgeSpec _ se.SeSp[sr];
            sep.vs[TRUE].phase _ SubMod[sep.vs[TRUE].phase, sep.vs[FALSE].phase, a.basePeriod];
            sep.vs[FALSE].phase _ ALL[0];
            IF FindStatEdge[sr, sep, FALSE].fse=NIL THEN RETURN [TRUE];
            RETURN [FALSE]};
        CheckUp: PROC [sev: Sets.Value] RETURNS [BOOL] ~ {
            se: StatEdge ~ NARROW[sev.VA];
            sep: StatEdgeSpec ~ se.SeSp[sr];
            IF sep.vs[FALSE].phase = ALL[0] THEN {
                FOR 
                    dsep: StatEdgeSpec _ sep;
                    dsep.vs[FALSE].phase _ [
                    dsep.vs[TRUE].phase _ AddMod[dsep.vs[TRUE].phase, [
                    IF FindStatEdge[sr, dsep, FALSE].fse=NIL THEN RETURN [TRUE];
                    ENDLOOP ENDLOOP;
                };
            RETURN [FALSE]};
        ShiftDown: PROC [sev: Sets.Value] RETURNS [BOOL] ~ {
            se: StatEdge ~ NARROW[sev.VA];
            sep: StatEdgeSpec _ se.SeSp[sr];
            IF sep.vs[FALSE].phase = ALL[0] THEN {
                sep.vs[TRUE].phase _ ALL[0];
                IF sr.svEdge[TRUE].AddPair[[SvV[sep.vs[TRUE]], AV[se]]].had[rightToLeft]=none THEN ERROR}
            ELSE RemStatEdge[d, sr, sep];
            RETURN [FALSE]};
        IF a.basePeriod=ALL[1] THEN RETURN [ALL[1]];
        IF sr.edges.Scan[CheckDown].found THEN RETURN [a.basePeriod];
        IF sr.edges.Scan[CheckUp].found THEN RETURN [a.basePeriod];
        IF a.
            xfms: Set ~ a.
            qr: QuotRem ~ DivMod[a.offsets[0].o1, a.basePeriod];
            IF xfms.NonTrivial OR qr.r#ALL[0] THEN RETURN [a.basePeriod];
            FOR 
                c
                IF a.offsets[c
                IF a.offsets[c
                ENDLOOP ENDLOOP;
            {theXfm: Sets.Value ~ xfms.TheElt;
            a.offsets _ OffsetsFromList[LIST[[a.offsets[0].o0, qr.q]]];
            a.
            a.
            }};
        IF sr.edges.Scan[ShiftDown].found THEN ERROR;
        RETURN [a.basePeriod _ ALL[1]]};

    SimilarizeArrays: PROC [d: Design, acts: Set--of CellType--] ~ {
        ects: Set--of CellType-- ~ d.arrayElt.Image[acts];
        SimilarizeGroup: PROC [ectv: Sets.Value] RETURNS [BOOL] ~ {
            ect: CellType ~ NARROW[ectv.VA];
            allActs: Set ~ d.arrayElt.Mapping[ectv, rightToLeft].Intersection[acts];
            keeps: Set--of act-- ~ Sets.CreateHashSet[d.eSpace];
            TryAct: PROC [actv: Sets.Value] RETURNS [BOOL] ~ {
                act: CellType ~ NARROW[actv.VA];
                TryExisting: PROC [xctv: Sets.Value] RETURNS [BOOL] ~ {
                    xct: CellType ~ NARROW[xctv.VA];
                    equiv: BOOL;
                    assoc: OneToOne;
                    [equiv, assoc] _ StructurallyEquivalent[act, xct];
                    IF equiv THEN {
                        MergeCellTypes[d, act, xct, assoc];
                        RETURN [TRUE]}
                    ELSE equiv _ equiv;
                    RETURN [FALSE]};
                IF NOT keeps.Scan[TryExisting].found THEN {
                    IF NOT keeps.AddElt[actv] THEN ERROR;
                    };
                RETURN [FALSE]};
            IF allActs.Scan[TryAct].found THEN ERROR;
            RETURN [FALSE]};
        SimplifyNames: PROC [ectv: Sets.Value] RETURNS [BOOL] ~ {
            ect: CellType ~ NARROW[ectv.VA];
            allActs: Set ~ d.arrayElt.Mapping[ectv, rightToLeft];
            IF allActs.Trivial THEN {
                act: CellType ~ NARROW[allActs.AnElt.MA];
                [] _ d.ctName.DeleteA[act];
                [] _ d.ctName.AddAA[act, ect.ACtName[].Cat["-array"]]}
            ELSE d _ d;
            RETURN [FALSE]};
        IF ects.Scan[SimilarizeGroup].found THEN ERROR;
        IF ects.Scan[SimplifyNames].found THEN ERROR;
        RETURN};

    END.