
    <<StructuralComparisonDataStructureImpl.Mesa>>
        <<Last tweaked by Mike Spreitzer on March 24, 1989 2:57:57 pm PST>>

    DIRECTORY Asserting, CoreStructuralComparison, Histograms, HistogramsOut, IO, Real, RealFns, Rope, 
    StructuralComparisonDataStructure, StructuralComparisonOps, StructuredStreams, UnparserBuffer;

    StructuralComparisonDataStructureImpl: CEDAR PROGRAM
        IMPORTS Asserting, Histograms, HistogramsOut, IO, Real, RealFns, Rope, StructuralComparisonDataStructure, StructuredStreams, 
        UnparserBuffer
        EXPORTS CoreStructuralComparison, StructuralComparisonDataStructure, StructuralComparisonOps
        =

    BEGIN OPEN CSC:CoreStructuralComparison, StructuralComparisonDataStructure, SS:StructuredStreams, UB:UnparserBuffer;

    ViewStats: TYPE ~ REF ViewStatsPrivate;
    ViewStatsPrivate: PUBLIC TYPE ~ StructuralComparisonDataStructure.ViewStatsPrivate;

    TransistorTolerances: TYPE ~ CSC.TransistorTolerances;
    TransistorDim: TYPE ~ CSC.TransistorDim;
    TransistorTolerancesPrivate: TYPE ~ CSC.TransistorTolerancesPrivate;

    graphIDToRope: PUBLIC GraphDescriptions _ [A: "A", B: "B", Unspecified: "Unspecified"];

    wideTransistorTolerances: PUBLIC TransistorTolerances ~ NEW [TransistorTolerancesPrivate _ ALL[[1.0E-6, 1.0E6]]];
    tightTransistorTolerances: PUBLIC TransistorTolerances ~ NEW [TransistorTolerancesPrivate _ ALL[[1.0, 1.0]]];

    TransistorDimName: PUBLIC ARRAY TransistorDim OF ROPE _ ["length", "width"];

    FormatTolerances: PUBLIC PROC [ttols: TransistorTolerances] RETURNS [ROPE] ~ {
        Fmt: PROC [dim: TransistorDim] RETURNS [rope: ROPE] ~ {
            t: CSC.Tolerance ~ ttols[dim];
            IF t.min=1.0/t.max OR t.max=1.0/t.min
                THEN rope _ IO.PutFR["%g: %g", [rope[TransistorDimName[dim]]], [real[t.max]]]
                ELSE rope _ IO.PutFR["%g: %g..%g", [rope[TransistorDimName[dim]]], [real[t.min]], [real[t.max]]]};
        RETURN Fmt[length].Cat[", ", Fmt[width]]};

    endOfQ: PUBLIC Vertex _ NEW [VertexRep];

    initialNetColor: Color _ 1;
    mirrorColor: Color _ 2;

    InitialColor: PUBLIC PROC [v: Vertex] RETURNS [initialColor: Color] = {
        SELECT v.class FROM
            net => initialColor _ initialNetColor;
            cell => initialColor _ IF IsMirror[v] THEN mirrorColor ELSE v.type.color;
            ENDCASE => ERROR;
        initialColor _ FilterColor[initialColor];
        };

    mergeBreak: Vertex _ NIL;

    MergeVertices: PUBLIC PROC [parent: CellType, v1, v2: Vertex] RETURNS [merged, doomed: Vertex] =
        BEGIN
        MoveToMerged: PROC [e: Edge] = {
            e.sides[net].v _ merged;
            };
        IF v1 = v2 THEN RETURN [v1, NIL];
        merged _ v1;
        doomed _ v2;
        IF merged.deleted OR doomed.deleted THEN ERROR;
        IF merged.class # doomed.class THEN ERROR;
        IF v1=mergeBreak OR v2=mergeBreak THEN merged _ merged;
        doomed.better _ merged;
        merged.name _ UnionNames[merged.name, doomed.name];
        SELECT merged.class FROM
            net => {
                EnumerateFullEdges[doomed, MoveToMerged, FALSE];
                IF doomed.firstEdge # NIL THEN {
                    IF merged.lastEdge # NIL THEN merged.lastEdge.sides[net].next _ doomed.firstEdge ELSE merged.firstEdge _ doomed.firstEdge;
                    merged.lastEdge _ doomed.lastEdge;
                    doomed.firstEdge.sides[net].prev _ merged.lastEdge;
                    doomed.firstEdge _ NIL;
                    doomed.lastEdge _ NIL;
                    };
                };
            cell => -- If they're cells, the caller asserts that they are connected identically  i.e., nothing needs to be done but delete the 
            doomed vertex and the edges touching it.-- parent.transCounts.flatTransMerges _ parent.transCounts.flatTransMerges + 
            merged.type.transCounts.flatTransistors;
            ENDCASE => ERROR;
        DeleteVertex[parent, doomed];
        merged.other _ Asserting.Union[merged.other, doomed.other];
        END;

    UnionNames: PROC [n1, n2: ROPE] RETURNS [un: ROPE] = {
        un _ IF n1.Length[] = 0 THEN n2 ELSE IF n2.Length[] = 0 THEN n1 ELSE n1.Cat["|", n2];
        };

    DeleteVertex: PUBLIC PROC [parent: CellType, v: Vertex] = {
        Killit: PROC [e: Edge] = {
            RemoveEdge[e];
            };
        EnumerateFullEdges[v, Killit, FALSE];
        v.deleted _ TRUE;
        SELECT v.class FROM
            cell => parent.cellCount _ parent.cellCount - 1;
            net => parent.netCount _ parent.netCount - 1;
            ENDCASE => ERROR;
        parent.size _ parent.size - 1;
        };

    RemoveEdge: PUBLIC PROC [e: Edge] = {
        FOR dir: VertexClass IN VertexClass DO
            [e.sides[dir].v.firstEdge, e.sides[dir].v.lastEdge] _ UnlinkEdge[e.sides[dir].v.firstEdge, e.sides[dir].v.lastEdge, e, dir];
            ENDLOOP;
        };

    UnlinkEdge: PROC [head, tail, e: Edge, dir: VertexClass] RETURNS [newHead, newTail: Edge] = {
        newHead _ head; newTail _ tail;
        IF e.sides[dir].next # NIL THEN e.sides[dir].next.sides[dir].prev _ e.sides[dir].prev ELSE newTail _ e.sides[dir].prev;
        IF e.sides[dir].prev # NIL THEN e.sides[dir].prev.sides[dir].next _ e.sides[dir].next ELSE newHead _ e.sides[dir].next;
        };

    PrintObject: PROC [to: IO.STREAM, PrintIt: PROC, cond: UB.BreakCondition _ width, sep: ROPE _ NIL] = {
        SS.Bp[to, cond, step, sep];
        SS.Begin[to];
        PrintIt[!UNWIND => SS.End[to]];
        SS.End[to];
        };
        step: NAT _ 3;

    PrintCellType: PROC [to: IO.STREAM, ct: CellType] ~ {
        NetPrint: PROC ~ {
            first: BOOL _ TRUE;
            PerVertex: PROC [v: Vertex] ~ {
                IF v.class#net THEN RETURN;
                IF first
                    THEN {first _ FALSE; SS.Bp[to, width, step]}
                    ELSE {to.PutRope[","]; SS.Bp[to, width, step, " "]};
                to.PutRope[v.name];
                RETURN};
            to.PutRope["wires = ("];
            ct.EnumerateParts[PerVertex, FALSE];
            to.PutRope[")"];
            RETURN};
        CellPrint: PROC ~ {
            sep: ROPE _ NIL;
            PerVertex: PROC [v: Vertex] ~ {
                IPrint: PROC ~ {PrintInstance[to, ct, v]};
                IF v.class#cell THEN RETURN;
                IF sep#NIL THEN to.PutRope[";"];
                PrintObject[to, IPrint, width, sep];
                sep _ " ";
                RETURN};
            to.PutRope["components = ("];
            ct.EnumerateParts[PerVertex, TRUE];
            to.PutRope[")"];
            RETURN};
        IF NOT SS.IsAnSS[to] THEN to _ SS.Create[UB.NewInittedHandle[[margin: 69, output: [stream[to]]]]];
        to.PutF["%g: CellType ~ {", [rope[ct.name]]];
        PrintObject[to, NetPrint];
        to.PutRope[";"];
        PrintObject[to, CellPrint, width, " "];
        to.PutRope["}"];
        RETURN};

    PrintInstance: PROC [to: IO.STREAM, ct: CellType, v: Vertex] ~ {
        first: BOOL _ TRUE;
        pi: PortIndex _ 0;
        PerEdge: PROC [c: Color, w: Vertex] ~ {
            IF first
                THEN {first _ FALSE; SS.Bp[to, width, step]}
                ELSE {to.PutRope[","]; SS.Bp[to, width, step, " "]};
            IF ct.ports[pi].color # c THEN ERROR;
            to.PutF["%g(%08x): %g", [rope[ct.ports[pi].name]], [cardinal[c]], [rope[w.name]]];
            pi _ pi + 1;
            RETURN};
        to.PutF["%g: %g[", [rope[v.name]], [rope[ct.name]]];
        v.EnumerateEdges[PerEdge, TRUE];
        to.PutRope["]"];
        IF pi#ct.ports.length THEN ERROR;
        RETURN};

    factor: REAL _ RealFns.Root[4, 2];
    minbin: PUBLIC REAL _ RealFns.Power[base: factor, exponent: Real.Round[RealFns.Log[base: factor, arg: 0.1]]];

    CreateViewStatsPair: PUBLIC PROC RETURNS [vsp: CSC.ViewStatsPair] ~ {
        FOR r: CSC.Role IN CSC.Role DO
            vsp[r] _ NEW [ViewStatsPrivate _ [ALL[NIL] ]];
            FOR g: Generation IN Generation DO
                vsp[r].sizeDists[g] _ Histograms.Create2D[iFactor: factor, jFactor: factor, iOffset: minbin, jOffset: minbin, logI: TRUE, logJ: 
                TRUE];
                ENDLOOP;
            ENDLOOP;
        RETURN};

    FmtViewStatsPair: PUBLIC PROC [vsp: CSC.ViewStatsPair, roleNames: CSC.RoleNames] RETURNS [ROPE] ~ {
        out: IO.STREAM ~ IO.ROS[];
        FOR r: CSC.Role IN CSC.Role DO
            out.PutRope[roleNames[r]]; out.PutRope["\n"];
            out.PutF["Cell types missing transistor counts: %g\n\n", [integer[vsp[r].missingTransistors]] ];
            FOR g: Generation IN Generation DO
                out.PutF["%g\nMax flat transistors: %g\nMax flat wires: %g\nCell type size distribution: ", [rope[genNames[g]]], 
                [integer[vsp[r].maxFlatTransistors[g]]], [integer[vsp[r].maxFlatWires[g]]]];
                HistogramsOut.WriteTo[vsp[r].sizeDists[g], out, TRUE, TRUE];
                out.PutRope["\n\n"];
                ENDLOOP;
            out.PutRope["\n"];
            ENDLOOP;
        RETURN out.RopeFromROS[]};

    genNames: ARRAY Generation OF ROPE ~ ["Original", "Reconciled"];

    END.