
    <<CompareCellDefs.Mesa>>
<<Last Edited by: Spreitzer, July 10, 1984 4:47:47 pm PDT>>

    DIRECTORY ComparePrivate, IO, OrderedSymbolTableRef, Real;

    CompareCellDefs: CEDAR PROGRAM
        IMPORTS ComparePrivate, IO, OrderedSymbolTableRef, Real
        EXPORTS ComparePrivate =

    BEGIN OPEN ComparePrivate;

    TwoCount: TYPE = ARRAY GraphID OF CARDINAL;

    endOfQ: PUBLIC Vertex _ NEW [VertexRep[net][0]];

    sizeFactor: REAL _ 0.25;

    CompareCDs: PUBLIC PROC [vertices: SymbolTablePair] =
        BEGIN
        ComputeColor: PROC [v: Vertex] RETURNS [color: Color] = {
            color _ v.oldColor;
            WITH v SELECT FROM
                cv: ComponentVertex => FOR i: CARDINAL IN [0 .. cv.length) DO
                    nv: Vertex _ cv.neighbors[i];
                    ec: Color _ cv.ports[i].color;
                    vc: Color _ nv.oldColor;
                    IF NOT nv.suspect THEN color _ (color + (ec+1) * (vc+1)) MOD hashTable.length;
                    ENDLOOP;
                nv: NetVertex => FOR i: CARDINAL IN [0 .. nv.length) DO
                    cv: Vertex _ nv.neighbors[i].v;
                    ec: Color _ nv.neighbors[i].color;
                    vc: Color _ cv.oldColor;
                    IF NOT cv.suspect THEN color _ (color + (ec+1) * (vc+1)) MOD hashTable.length;
                    ENDLOOP;
                ENDCASE => ERROR};
        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] = {
            WITH v SELECT FROM
                nv: NetVertex => FOR n: CARDINAL IN [0 .. nv.length) DO
                    EnQ[nv.neighbors[n].v];
                    ENDLOOP;
                cv: ComponentVertex => FOR n: CARDINAL IN [0 .. cv.length) DO
                    EnQ[cv.neighbors[n]];
                    ENDLOOP;
                ENDCASE => ERROR};
        Initialize: PROC = {
            InitVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {
                v: Vertex _ NARROW[ra];
                stop _ FALSE;
                IF v.unique OR v.QNext # notInQ THEN ERROR;
                EnQ[v]};
            hts: CARDINAL _ MAX[MinHashSize, Real.RoundC[sizeFactor * (vertices[A].Size[] + vertices[B].Size[])]];
            QFirst _ endOfQ; QCount _ 0;
            hashTable _ NEW [HashTableRep[hts]];
            hashTable.firstNonEmpty _ NullIndex;
            FOR hti: HashTableIndex IN [0 .. hashTable.length) DO
                hashTable[hti] _ [];
                ENDLOOP;
            vertices[A].EnumerateIncreasing[InitVertex];
            vertices[B].EnumerateIncreasing[InitVertex];
            nonUniqueCount[A] _ vertices[A].Size[];
            nonUniqueCount[B] _ vertices[B].Size[];
            IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
            };
        SetQToAllNonUniques: PROC = {
            AddVertex: PROC [ra: REF ANY] RETURNS [stop: BOOL] = {
                v: Vertex _ NARROW[ra];
                stop _ FALSE;
                IF v.QNext # notInQ THEN ERROR;
                EnQ[v]};
            wasAll _ TRUE;
            vertices[A].EnumerateIncreasing[AddVertex];
            vertices[B].EnumerateIncreasing[AddVertex];
            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 GraphID 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 {
                        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", vertices, 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 GraphID 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 GraphID 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]], vertices, 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;
        END;

    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[QFirst.name]];
            ENDLOOP;
        Log["}\n"];
        END;

    END.