
    <<LichenCompareStructure.Mesa>>
        <<Bertrand Serlet June 4, 1986 4:16:39 pm PDT>>
        <<Last tweaked by Mike Spreitzer on May 4, 1987 2:46:02 pm PDT>>

    DIRECTORY Basics, CardHashTableThreaded, IO, LichenComparisonOps, LichenDataOps, LichenDataStructure, Random, Rope, RopeHash, 
    SymTab;

    LichenCompareStructure: CEDAR PROGRAM
        IMPORTS Basics, CardHashTableThreaded, IO, LichenComparisonOps, LichenDataOps, LichenDataStructure, Random, SymTab
        EXPORTS LichenComparisonOps =

    BEGIN OPEN LichenDataOps, LichenDataStructure, LichenComparisonOps;

    TwoCount: TYPE = ARRAY RealGraphID OF CARDINAL;

    initialNetColor: Color = 1;
    mirrorColor: Color = 2;
    initialIMColor: Color = 3;

    colorClass: CardHashTableThreaded.Class = [GetColorDataKey, SetColorDataLink, GetColorDataLink];

    debug: BOOL _ TRUE;
    Break: SIGNAL = CODE;

    MidSquare: PROC [x: CARD] RETURNS [y: CARD] ~ {y _ MidSquareI[x]};

    MidSquareI: PROC [x: CARD] RETURNS [CARD] ~ INLINE {
        lowProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.LowHalf[x], Basics.LowHalf[x]]]];
        midProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.LowHalf[x], Basics.HighHalf[x]]]];
        highProd: Basics.LongNumber = [lc[Basics.LongMult[Basics.HighHalf[x], Basics.HighHalf[x]]]];
        m: Basics.LongNumber = [lc[AddC[lowProd.hi, midProd.lo, midProd.lo]]];
        lo: Basics.LongNumber = [pair[lo: lowProd.lo, hi: m.lo]];
        hi: CARD = highProd.lc + AddC[m.hi, midProd.hi, midProd.hi];
        RETURN [hi + lo.lc]};

    CompareGraphs: PUBLIC PROC [descriptions: RealGraphDescriptions, a, b: CellType, GenerateHints: PROC [Consume: PROC [vA, vB: 
    Vertex]], pick, mirrors, mayQuitEarly: BOOL, abort: REF BOOL] RETURNS [equiv, didQuitEarly: BOOL, partition: ColorTable] =
        BEGIN
        rs: Random.RandomStream = Random.Create[seed: 0];
        passColor: Color _ noColor;
        breakVs: SymTab.Ref _ NIL;
        ComputeColor: PROC [v: Vertex] RETURNS [color: Color] = {
            AddEdge: PROC [edgeColor: Color, nv: Vertex] = {
                IF NOT nv.suspect THEN color _ color + (edgeColor+1) * (nv.oldColor+1);
                };
            color _ v.oldColor + passColor;
            EnumerateEdges[v, AddEdge, mirrors];
            color _ FilterColor[MidSquareI[color]];
            IF debug AND breakVs#NIL AND breakVs.Fetch[Describe[v, v.containingCT]].found THEN Break;
            v _ v;
            };
        EnQNeighbor: PROC [edgeColor: Color, neighbor: Vertex] = {EnQ[neighbor]};
        EnQ: PROC [v: Vertex] = {
            v _ v;
            IF NOT mirrors THEN WITH v SELECT FROM
                ci: CellInstance => IF IsMirror[ci] THEN ERROR;
                w: Wire => NULL;
                im: Intermediary => NULL;
                ENDCASE => ERROR;
            IF (NOT v.unique) AND (v.QNext = notInQ) THEN {v.QNext _ QFirst; QFirst _ v; QCount _ QCount + 1}};
        AddFrontier: PROC [v: Vertex] = {EnumerateEdges[v, EnQNeighbor, mirrors]};
        Initialize: PROC = {
            ClearVertex: PROC [v: Vertex] = {
                v.QNext _ notInQ;
                v.equiv _ NIL;
                v.oldColor _ noColor; v.curColor _ noColor;
                v.unique _ FALSE;
                v.suspect _ FALSE;
                };
            NoteAssoc: PROC [vA, vB: Vertex] = {
                color: Color = FilterColor[rs.NextInt[]];
                vA.oldColor _ color; vA.curColor _ color;
                vB.oldColor _ color; vB.curColor _ color;
                };
            InitVertex: PROC [v: Vertex] = {
                v.graph _ curGraph;
                IF v.curColor = noColor THEN {
                    color: Color ~ WITH v SELECT FROM
                        w: Wire => initialNetColor,
                        ci: CellInstance => IF IsMirror[ci] THEN mirrorColor ELSE ci.type.color,
                        im: Intermediary => initialIMColor,
                        ENDCASE => ERROR;
                    v.oldColor _ color; v.curColor _ color;
                    };
                AddToColor[GetColorData[curColorData, v.curColor], v];
                nonUniqueCount[curGraph] _ nonUniqueCount[curGraph] + 1;
                };
            curGraph: RealGraphID;
            QFirst _ endOfQ; QCount _ 0;
            partition _ CardHashTableThreaded.Create[class: colorClass];
            curColorData _ CardHashTableThreaded.Create[class: colorClass];
            EnumerateParts[a, ClearVertex, mirrors];
            IF abort^ THEN RETURN;
            EnumerateParts[b, ClearVertex, mirrors];
            IF abort^ THEN RETURN;
            GenerateHints[NoteAssoc];
            IF abort^ THEN RETURN;
            nonUniqueCount _ ALL[IF mirrors THEN 1 ELSE 0];
            curGraph _ A; EnumerateParts[a, InitVertex, mirrors];
            IF abort^ THEN RETURN;
            curGraph _ B; EnumerateParts[b, InitVertex, mirrors];
            IF abort^ THEN RETURN;
            someSuspect _ FALSE;
            [] _ curColorData.Pairs[ComputeUnique];
            SetQToAllNonUniques[];
            IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
            };
        Finalize: PROC = {
            FinalVertex: PROC [v: Vertex] = {
                AddToColor[GetColorData[partition, v.curColor], v];
                };
            EnumerateParts[a, FinalVertex, mirrors];
            EnumerateParts[b, FinalVertex, mirrors];
            };
        SetQToAllNonUniques: PROC = {
            AddVertex: PROC [v: Vertex] = {IF v.QNext # notInQ THEN ERROR; EnQ[v]};
            EnumerateParts[a, AddVertex, mirrors];
            EnumerateParts[b, AddVertex, mirrors];
            IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
            };
        ChoosePairs: PROC [useSuspects, onlyOne: BOOL] RETURNS [pairCount: CARDINAL] = {
            ConsiderColor: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL _ FALSE] --CardHashTableThreaded.EachPairAction-- = {
                ccd: ColorData = NARROW[value];
                first: ARRAY RealGraphID OF Vertex _ [NIL, NIL];
                IF ccd.suspect # useSuspects THEN RETURN;
                FOR v: Vertex _ ccd.firstVertex, v.colorNext WHILE v # NIL DO
                    IF v.QNext # notInQ THEN ERROR;
                    IF first[v.graph] = NIL THEN {
                        first[v.graph] _ v;
                        IF first[OtherGraph[v.graph]] # NIL THEN EXIT};
                    ENDLOOP;
                IF first[A]#NIL AND first[B]#NIL THEN {
                    IF first[A].unique # first[B].unique THEN ERROR;
                    IF NOT first[A].unique THEN {
                        pairCount _ pairCount + 1;
                        EnQ[first[A]]; EnQ[first[B]];
                        quit _ onlyOne};
                    };
                };
            pairCount _ 0;
            [] _ curColorData.Pairs[ConsiderColor];
            };
        ComputeUnique: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL _ FALSE] --CardHashTableThreaded.EachPairAction-- = {
            ccd: ColorData = NARROW[value];
            uniques: ARRAY RealGraphID OF BOOL = [ccd.count[A]=1, ccd.count[B]=1];
            unique: BOOL _ uniques[A] AND uniques[B];
            IF unique THEN {
                a: Vertex _ ccd.firstVertex;
                b: Vertex _ a.colorNext;
                IF b.colorNext # NIL THEN ERROR;
                IF a.graph = b.graph THEN ERROR;
                IF a.unique OR b.unique THEN ERROR;
                a.unique _ TRUE;
                b.unique _ TRUE;
                a.equiv _ b; b.equiv _ a;
                nonUniqueCount[A] _ nonUniqueCount[A] - 1;
                nonUniqueCount[B] _ nonUniqueCount[B] - 1;
                };
            someSuspect _ (ccd.suspect _ ccd.count[A] # ccd.count[B]) OR someSuspect;
            FOR v: Vertex _ ccd.firstVertex, v.colorNext WHILE v # NIL DO
                v.oldColor _ v.curColor;
                v.suspect _ ccd.suspect;
                ENDLOOP;
            };
        QueueFrontier: PROC [key: CARD, value: REF ANY] RETURNS [quit: BOOL _ FALSE] --CardHashTableThreaded.EachPairAction-- = {
            ccd: ColorData = NARROW[value];
            uniques: ARRAY RealGraphID OF BOOL = [ccd.count[A]=1, ccd.count[B]=1];
            unique: BOOL _ uniques[A] AND uniques[B];
            IF unique THEN {
                v1: Vertex _ ccd.firstVertex;
                v2: Vertex _ v1.colorNext;
                IF v2.colorNext # NIL THEN ERROR;
                IF v1.graph = v2.graph THEN ERROR;
                IF NOT (v1.unique AND v2.unique) THEN ERROR;
                AddFrontier[v1]; AddFrontier[v2];
                };
            };
        nonUniqueCount: TwoCount _ ALL[LAST[CARDINAL]];
        curColorData, oldColorData: ColorTable _ NIL;
        pass: CARDINAL _ 0;
        QFirst: Vertex;
        QCount: CARDINAL;
        isAll: BOOL _ TRUE;
        someMC, someSuspect: BOOL _ FALSE;
        IF abort^ THEN RETURN [FALSE, FALSE, NIL];
        Initialize[];
        IF abort^ THEN RETURN [FALSE, FALSE, NIL];
        IF debug THEN WriteAll["CompareCDs Initialized", descriptions, a, b, oldColorData, curColorData];
        didQuitEarly _ mayQuitEarly AND someSuspect;
        WHILE nonUniqueCount[A]#0 AND nonUniqueCount[B]#0 AND NOT didQuitEarly DO
            mcCount: CARDINAL _ 0;
            keepOld: BOOL _ isAll;
            IF abort^ THEN RETURN [FALSE, FALSE, NIL];
            pass _ pass + 1;
            passColor _ LOOPHOLE[rs.NextInt[], Color];
            IF QCount > 0 THEN NULL
            ELSE IF NOT (isAll AND NOT someMC) THEN SetQToAllNonUniques[]
            ELSE {pairCount: CARDINAL _ 0;
                IF pick THEN pairCount _ ChoosePairs[FALSE, TRUE];
                IF pairCount = 0 THEN {
                    IF QFirst # endOfQ OR QCount # 0 THEN ERROR;
                    pairCount _ ChoosePairs[TRUE, FALSE];
                    IF pairCount = 0 THEN EXIT}};
            isAll _ (nonUniqueCount[A] + nonUniqueCount[B]) = QCount;
            oldColorData _ IF keepOld THEN curColorData ELSE CardHashTableThreaded.Create[curColorData.GetSize[], colorClass];
            curColorData _ CardHashTableThreaded.Create[curColorData.GetSize[], colorClass];
            someMC _ FALSE;
            WHILE QFirst # endOfQ DO
                v: Vertex = QFirst;
                oldColor: Color = v.oldColor;
                newColor: Color = ComputeColor[v];
                ncd: ColorData = GetColorData[curColorData, newColor];
                IF abort^ THEN RETURN [FALSE, FALSE, NIL];
                IF QFirst = notInQ THEN ERROR;
                v.curColor _ newColor;
                QFirst _ v.QNext;
                v.QNext _ notInQ;
                IF isAll AND NOT someMC THEN {
                    ocd: ColorData = GetColorData[oldColorData, oldColor, keepOld];
                    IF ocd.newColor = noColor THEN ocd.newColor _ newColor
                    ELSE IF ocd.multicolored THEN ERROR
                    ELSE IF ocd.newColor = newColor THEN NULL
                    ELSE ocd.multicolored _ someMC _ TRUE;
                    };
                AddToColor[ncd, v];
                ENDLOOP;
            QCount _ 0;
            someSuspect _ FALSE;
            [] _ curColorData.Pairs[ComputeUnique];
            [] _ curColorData.Pairs[QueueFrontier];
            IF debug THEN {
                Log["\nAt end of pass %g:\n", [cardinal[pass]]];
                WriteColorTable[curColorData, descriptions];
                Log["QCount=%g, nonUniqueCount=[%g, %g]", IO.card[QCount], IO.card[nonUniqueCount[A]], IO.card[nonUniqueCount[B]]];
                Log[", someMC=%g, isAll=%g, someSuspect=%g\n", IO.bool[someMC], IO.bool[isAll], IO.bool[someSuspect]];
                WriteQ[QFirst, descriptions];
                };
            ENDLOOP;
        equiv _ nonUniqueCount[A]=0 AND nonUniqueCount[B]=0;
        Finalize[];
        END;

    GetColorData: PROC [colorTable: ColorTable, color: Color, mayNotCreate: BOOL _ FALSE] RETURNS [cd: ColorData] = {
        cd _ NARROW[colorTable.Fetch[color].value];
        IF cd # NIL OR mayNotCreate THEN RETURN;
        cd _ NEW [ColorDataPrivate _ [color: color]];
        IF NOT colorTable.Insert[color, cd] THEN ERROR;
        };

    AddToColor: PROC [cd: ColorData, v: Vertex] = INLINE {
        v.colorNext _ cd.firstVertex;
        cd.firstVertex _ v;
        cd.count[v.graph] _ cd.count[v.graph] + 1;
        };

    EnumerateEdges: PROC [v: Vertex, Consume: PROC [Color, Vertex], includeMirror: BOOL] ~ {
        Pass: PROC [port: Port, w: Vertex] ~ {Consume[port.color, w]};
        EnumerateImmediateConnections[v, Pass];
        };

    WriteQ: PROC [QFirst: Vertex, descriptions: RealGraphDescriptions] =
        BEGIN
        first: BOOL _ TRUE;
        Log["Q = {"];
        FOR QFirst _ QFirst, QFirst.QNext WHILE QFirst # endOfQ DO
            IF QFirst = notInQ THEN ERROR;
            IF first THEN first _ FALSE ELSE Log[", "];
            Log["(%g)%g", [rope[descriptions[QFirst.graph]]], IO.rope[VerboseVName[QFirst]]];
            ENDLOOP;
        Log["}\n"];
        END;

    GetColorDataKey: PROC [value: REF ANY] RETURNS [key: CARD] = {
        cd: ColorData = NARROW[value];
        key _ cd.color;
        };

    SetColorDataLink: PROC [from, to: REF ANY] = {
        fromCD: ColorData = NARROW[from];
        toCD: ColorData = NARROW[to];
        fromCD.nextColor _ toCD;
        };

    GetColorDataLink: PROC [from: REF ANY] RETURNS [to: REF ANY] = {
        fromCD: ColorData = NARROW[from];
        to _ fromCD.nextColor;
        };

    AddC: PROC [c1, c2, c3: CARDINAL] RETURNS [CARD] = INLINE {
        RETURN [c1.LONG + c2.LONG + c3.LONG];
        };

    END.