
    <<LichenCellDefs.Mesa>>
<<Last Edited by: Spreitzer, July 11, 1985 8:30:19 pm PDT>>

    DIRECTORY LichenDataStructure, LichenOps, IO, RedBlackTree, Real, Rope;

    LichenCellDefs: CEDAR PROGRAM
        IMPORTS LichenOps, IO, RedBlackTree, Real, Rope
        EXPORTS LichenDataStructure, LichenOps =

        BEGIN OPEN LichenDataStructure, LichenOps;

        TwoCount: TYPE = ARRAY RealGraphID OF CARDINAL;

        graphIDToRope: PUBLIC ARRAY GraphID OF ROPE _ [A: "A", B: "B", Unspecified: "Unspecified"];

        endOfQ: PUBLIC Vertex _ NEW [VertexRep];

        PortHashSize: CARDINAL = LAST[HashTableIndex];
        MinHashSize: CARDINAL _ 511;
        sizeFactor: REAL _ 0.25;
        initialNetColor: Color _ 1;

        CompareGraphs: PUBLIC PROC [a, b: CellType, seeAllInstanceNames: BOOL] RETURNS [equiv: BOOL] =
            BEGIN
            ComputeColor: PROC [v: Vertex] RETURNS [color: Color] = {
                color _ v.oldColor;
                FOR e: Edge _ v.firstEdge, e.sides[v.class].next WHILE e # NIL DO
                    nv: Vertex _ e.sides[OtherClass[v.class]].v;
                    IF e.sides[v.class].v # v THEN ERROR;
                    IF NOT nv.suspect THEN color _ (color + (e.color+1) * (nv.oldColor+1)) MOD hashTable.length;
                    ENDLOOP};
            EnQ: PROC [v: Vertex] = {IF (NOT v.unique) AND (v.QNext = notInQ) THEN {v.QNext _ QFirst; QFirst _ v; QCount _ QCount + 1}};
            AddFrontier: PROC [v: Vertex] = {
                FOR e: Edge _ v.firstEdge, e.sides[v.class].next WHILE e # NIL DO
                    IF e.sides[v.class].v # v THEN ERROR;
                    EnQ[e.sides[OtherClass[v.class]].v];
                    ENDLOOP};
            Initialize: PROC = {
                InitVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {
                    v: Vertex;
                    stop _ FALSE;
                    WITH ra SELECT FROM
                        vtx: Vertex => v _ vtx;
                        a: Alias => {v _ NARROW[AntiAlias[a]]; IF a.name # PickAName[v.names] THEN RETURN};
                        ENDCASE => ERROR;
                    v.graph _ curGraph;
                    IF v.unique OR v.QNext # notInQ THEN ERROR;
                    v.equiv _ NIL;
                    v.suspect _ FALSE;
                    SELECT v.class FROM
                        net => v.curColor _ initialNetColor;
                        cell => {
                            portIndex: PortIndex _ 0;
                            IF v.type.inittedFor # hts THEN InitCellType[v.type];
                            v.curColor _ v.type.color;
                            FOR e: Edge _ v.firstEdge, e.sides[cell].next WHILE e # NIL DO
                                IF e.portIndex # portIndex THEN ERROR;
                                IF e.sides[cell].v # v THEN ERROR;
                                e.color _ v.type.ports[portIndex].color;
                                portIndex _ portIndex + 1;
                                ENDLOOP;
                            IF portIndex # v.type.ports.length THEN ERROR;
                            };
                        ENDCASE => ERROR;
                    v.oldColor _ v.curColor;
                    EnQ[v]};
                InitCellType: PROC [ct: CellType] = {
                    ct.inittedFor _ hts;
                    ct.color _ HashRope[CTEquivClass[ct], hts];
                    FOR pi: PortIndex IN [0 .. ct.ports.length) DO
                        ct.ports[pi].color _ HashRope[PortEquivClass[ct, pi], PortHashSize];
                        ENDLOOP;
                    };
                hts: CARDINAL _ MAX[MinHashSize, Real.RoundC[sizeFactor * (a.parts.Size[] + b.parts.Size[] + 2)]];
                curGraph: RealGraphID;
                QFirst _ endOfQ; QCount _ 0;
                hashTable _ NEW [HashTableRep[hts]];
                hashTable.firstNonEmpty _ NullIndex;
                FOR hti: HashTableIndex IN [0 .. hashTable.length) DO
                    hashTable[hti] _ [];
                    ENDLOOP;
                curGraph _ A;
                a.parts.EnumerateIncreasing[InitVertex]; [] _ InitVertex[a.mirror]; --AM1
                curGraph _ B;
                b.parts.EnumerateIncreasing[InitVertex]; [] _ InitVertex[b.mirror];
                nonUniqueCount[A] _ a.parts.Size[] + 1;
                nonUniqueCount[B] _ b.parts.Size[] + 1;
                IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
                };
            SetQToAllNonUniques: PROC = {
                AddVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {
                    v: Vertex;
                    stop _ FALSE;
                    WITH ra SELECT FROM
                        vtx: Vertex => v _ vtx;
                        a: Alias => {v _ NARROW[AntiAlias[a]]; IF a.name # PickAName[v.names] THEN RETURN};
                        ENDCASE => ERROR;
                    IF v.QNext # notInQ THEN ERROR;
                    EnQ[v]};
                wasAll _ TRUE;
                a.parts.EnumerateIncreasing[AddVertex]; [] _ AddVertex[a.mirror]; --AM1
                b.parts.EnumerateIncreasing[AddVertex]; [] _ AddVertex[b.mirror];
                IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
                hashTable.firstNonEmpty _ NullIndex};
            ChoosePairs: PROC [useSuspects: BOOL] RETURNS [pairCount: CARDINAL] = {
                wasAll _ TRUE; pairCount _ 0;
                FOR hti: HashTableIndex _ hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty WHILE hti # NullIndex DO
                    first: ARRAY RealGraphID OF Vertex _ [NIL, NIL];
                    IF hashTable[hti].suspect # useSuspects THEN LOOP;
                    FOR v: Vertex _ hashTable[hti].v, v.colorNext WHILE v # NIL DO
                        IF v.QNext # notInQ THEN ERROR;
                        IF first[v.graph] = NIL THEN first[v.graph] _ v;
                        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 {
                            IF first[A].QNext # notInQ THEN ERROR;
                            IF first[B].QNext # notInQ THEN ERROR;
                            pairCount _ pairCount + 1;
                            EnQ[first[A]]; EnQ[first[B]]}};
                    ENDLOOP;
                hashTable.firstNonEmpty _ NullIndex};
            nonUniqueCount: TwoCount _ ALL[LAST[CARDINAL]];
            hashTable: HashTable _ NIL;
            pass: CARDINAL _ 0;
            QFirst: Vertex;
            QCount: CARDINAL;
            wasAll: BOOL _ TRUE;
            Initialize[];
            WriteAll["CompareCDs Initialized", a, b, hashTable];
            WHILE nonUniqueCount[A]#0 AND nonUniqueCount[B]#0 DO
                mcCount: CARDINAL _ 0;
                someMC: BOOL _ FALSE;
                pass _ pass + 1;
                WHILE QFirst # endOfQ DO
                    v: Vertex _ QFirst;
                    oldColor: Color _ v.oldColor;
                    newColor: Color _ v.curColor _ ComputeColor[v];
                    IF QFirst = notInQ THEN ERROR;
                    QFirst _ v.QNext;
                    v.QNext _ notInQ;
                    IF wasAll AND NOT someMC THEN {
                        IF hashTable[oldColor].newColor = noColor THEN hashTable[oldColor].newColor _ newColor
                        ELSE IF hashTable[oldColor].multicolored THEN ERROR
                        ELSE IF hashTable[oldColor].newColor = newColor THEN NULL
                        ELSE hashTable[oldColor].multicolored _ someMC _ TRUE;
                        };
                    IF hashTable[newColor].count[A] = 0 AND hashTable[newColor].count[B] = 0 THEN {
                        hashTable[newColor].v _ NIL;
                        hashTable[newColor].nextNonEmpty _ hashTable.firstNonEmpty;
                        hashTable.firstNonEmpty _ newColor};
                    v.colorNext _ hashTable[newColor].v;
                    hashTable[newColor].v _ v;
                    hashTable[newColor].count[v.graph] _ hashTable[newColor].count[v.graph] + 1;
                    ENDLOOP;
                QCount _ 0;
                FOR hti: HashTableIndex _ hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty WHILE hti # NullIndex DO
                    uniques: ARRAY RealGraphID OF BOOL = [hashTable[hti].count[A]=1, hashTable[hti].count[B]=1];
                    unique: BOOL _ uniques[A] AND uniques[B];
                    IF unique THEN {
                        a: Vertex _ hashTable[hti].v;
                        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 _ b.unique _ TRUE;
                        a.equiv _ b; b.equiv _ a;
                        nonUniqueCount[A] _ nonUniqueCount[A] - 1;
                        nonUniqueCount[B] _ nonUniqueCount[B] - 1;
                        };
                    ENDLOOP;
                FOR hti: HashTableIndex _ hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty WHILE hti # NullIndex DO
                    uniques: ARRAY RealGraphID OF BOOL = [hashTable[hti].count[A]=1, hashTable[hti].count[B]=1];
                    unique: BOOL _ uniques[A] AND uniques[B];
                    IF unique THEN {
                        a: Vertex _ hashTable[hti].v;
                        b: Vertex _ a.colorNext;
                        IF b.colorNext # NIL THEN ERROR;
                        IF a.graph = b.graph THEN ERROR;
                        IF NOT (a.unique AND b.unique) THEN ERROR;
                        AddFrontier[a]; AddFrontier[b];
                        };
                    hashTable[hti].suspect_ hashTable[hti].count[A] # hashTable[hti].count[B];
                    FOR v: Vertex _ hashTable[hti].v, v.colorNext WHILE v # NIL DO
                        v.oldColor _ v.curColor;
                        v.suspect _ hashTable[hti].suspect;
                        ENDLOOP;
                    hashTable[hti].count[A] _ 0;
                    hashTable[hti].count[B] _ 0;
                    hashTable[hti].newColor _ noColor;
                    hashTable[hti].multicolored _ FALSE;
                    ENDLOOP;
                WriteAll[IO.PutFR["Almost end of pass %g", IO.card[pass]], a, b, hashTable];
                Log["QCount=%g, nonUniqueCount=[%g, %g], someMC=%g, wasAll=%g\n",
                    IO.card[QCount], IO.card[nonUniqueCount[A]],
                    IO.card[nonUniqueCount[B]], IO.bool[someMC], IO.bool[wasAll]];
                WriteQ[QFirst];
                IF QCount > 0 THEN {
                    wasAll _ (nonUniqueCount[A] + nonUniqueCount[B]) = QCount;
                    hashTable.firstNonEmpty _ NullIndex}
                ELSE IF someMC OR (NOT wasAll) THEN SetQToAllNonUniques[]
                ELSE {pairCount: CARDINAL _ ChoosePairs[useSuspects: FALSE];
                    IF pairCount = 0 THEN {QFirst _ endOfQ; QCount _ 0;
                        pairCount _ ChoosePairs[useSuspects: TRUE];
                        IF pairCount = 0 THEN EXIT}};
                ENDLOOP;
            equiv _ nonUniqueCount[A]=0 AND nonUniqueCount[B]=0;
            END;

        HashRope: PROC [r: ROPE, hashTableSize: CARDINAL] RETURNS [c: Color] =
            BEGIN
            len: INT = r.Length[];
            c _ 1;
            FOR i: INT DECREASING IN [0 .. len) DO
                char: CHAR _ r.Fetch[i];
                long: LONG CARDINAL _ rot*c + (char-0C);
                c _ long MOD hashTableSize;
                ENDLOOP;
            END;
            rot: LONG CARDINAL _ 128 + 32 + 2;

        CTEquivClass: PROC [ct: CellType] RETURNS [equivClass: EquivClass] = {
            equivClass _ IF ct.equivClass = implicitClass THEN PickAName[ct.names] ELSE ct.equivClass};

        PortEquivClass: PROC [ct: CellType, pi: PortIndex] RETURNS [equivClass: EquivClass] = {
            equivClass _ IF ct.ports[pi].equivClass = implicitClass THEN PickAName[ct.ports[pi].names] ELSE ct.ports[pi].equivClass};

        WriteQ: PROC [QFirst: Vertex] =
            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", IO.rope[graphIDToRope[QFirst.graph]], IO.rope[PickAName[QFirst.names]]];
                ENDLOOP;
            Log["}\n"];
            END;

        Test: PROC [da, db: Design, aName, bName: ROPE] =
            BEGIN
            aType: CellType _ NARROW[Lookup[da.cellTypesByName, aName]];
            bType: CellType _ NARROW[Lookup[db.cellTypesByName, bName]];
            equiv: BOOL;
            EnsureParts[aType];
            EnsureParts[bType];
            Log["\nTesting %g %g\n", IO.rope[aName], IO.rope[bName]];
            equiv _ CompareGraphs[aType, bType, FALSE];
            Log["\nEquiv = %g.\n", IO.bool[equiv]];
            FlushLog[];
            END;

        END.