
    <<StructuralComparisonDataStructure.Mesa>>
        <<Last tweaked by Mike Spreitzer on March 7, 1989 4:26:36 pm PST>>

    DIRECTORY Asserting, CardHashTableThreaded, Histograms, IO, Rope, SymTab;

    StructuralComparisonDataStructure: CEDAR DEFINITIONS =

        BEGIN

        LORA: TYPE = LIST OF REF ANY;
        LOLORA: TYPE = LIST OF LORA;
        ROPE: TYPE = Rope.ROPE;
        RopeList: TYPE = LIST OF ROPE;
        SymbolTable: TYPE ~ SymTab.Ref;
        Assertions: TYPE = Asserting.Assertions;
        ColorTable: TYPE = CardHashTableThreaded.Table;
        Histogram: TYPE ~ Histograms.Histogram;

        GraphID: TYPE = {A, B, Unspecified};
        RealGraphID: TYPE = GraphID[A .. B];
        OtherGraph: ARRAY RealGraphID OF RealGraphID = [A: B, B: A];
        graphIDToRope: GraphDescriptions;
        GraphDescriptions: TYPE ~ ARRAY GraphID OF ROPE;
        RealGraphDescriptions: TYPE ~ ARRAY RealGraphID OF ROPE;

        Color: TYPE = CARD;
        noColor: Color = LAST[Color];
        someColor: Color = 87654321H;
        FilterColor: PROC [color: Color] RETURNS [filtered: Color] = INLINE {
            filtered _ IF color # noColor THEN color ELSE someColor};

        ViewStatsPrivate: TYPE ~ RECORD [
            sizeDists: ARRAY Generation OF Histogram,
                <<Each histogram is two-dimensional, X=number of instances, Y=num wires>>
            maxFlatTransistors, maxFlatWires: ARRAY Generation OF INT _ ALL[0],
            missingTransistors: NAT _ 0
                <<Number of subtrees with no transistor data>>
            ];
        Generation: TYPE ~ {Original, Reconciled};
        minbin: REAL; --hack: 0 in histograms is this instead

        VertexClass: TYPE = {net, cell};
        OtherClass: ARRAY VertexClass OF VertexClass = [net: cell, cell: net];

        CellType: TYPE = REF CellTypeRep;
        CellTypeRep: TYPE = RECORD [
            name: ROPE _ NIL,
            color: Color _ noColor,
            ports: PortS _ NIL,
            internalsKnown, destroyed: BOOL _ FALSE,
            firstPart: Vertex _ NIL,
            size: NAT _ 0,    --number of parts
            mirror: Vertex _ NIL,    --the outside world, as seen from the inside
                <<AM1: A mirror is not entered in its parent's parts list.>>
                <<AM2: A mirror is not linked in as an instance of its type.>>
            netCount, cellCount: NAT _ 0,
                <<Counts are redundant with parts.>>
            transCounts: TransCounts _ NIL,
                <<Not needed for anything, just comfortning info to have.>>
            otherPublic, otherPrivate: Assertions _ NIL];

        TransCounts: TYPE ~ REF TransCountsPrivate;
        TransCountsPrivate: TYPE ~ RECORD [flatTransistors, flatTransMerges, flatWires, flatWireDels: INT _ 0];

        IsMirror: PROC [v: Vertex] RETURNS [is: BOOL] = INLINE {is _ v.isMirror};

        EnumerateParts: PROC [ct: CellType, Consume: PROC [Vertex], mirrorToo: BOOL] = INLINE {
            next: Vertex;
            FOR v: Vertex _ ct.firstPart, next WHILE v # NIL DO
                next _ v.nextPart;
                IF NOT v.deleted THEN Consume[v]
                ENDLOOP;
            IF mirrorToo THEN Consume[ct.mirror];
            };

        PortS: TYPE = REF PortSeq;
        PortSeq: TYPE = RECORD [length: PortIndex, ports: SEQUENCE size: PortIndex OF Port];
        PortIndex: TYPE = NAT;
        NullPortIndex: PortIndex = LAST[PortIndex];

        Port: TYPE = RECORD [name: ROPE _ NIL, net: Vertex _ NIL, other: Assertions _ NIL, color: Color _ noColor];

        VertexList: TYPE = LIST OF Vertex;
        Vertex: TYPE = REF VertexRep;
        VertexRep: PRIVATE TYPE = RECORD [
            name: ROPE,
            QNext: Vertex _ notInQ,
            nextPart: Vertex _ NIL,
            colorNext, equiv: Vertex _ NIL,
            firstEdge, lastEdge: Edge _ NIL,
            type: CellType _ NIL,
            other: Assertions _ NIL,
            oldColor, curColor: Color _ noColor,
            better: Vertex _ NIL,
            graph: GraphID _ Unspecified,
            class: VertexClass,
            unique, suspect, isMirror, deleted: BOOL _ FALSE];

        Edge: TYPE = REF EdgeRep;
        EdgeRep: TYPE = RECORD [
            sides: ARRAY VertexClass OF RECORD [v: Vertex, next, prev: Edge],
            color: Color];

        notInQ: Vertex --don't look:-- = NIL --you looked!--;
        endOfQ: Vertex;

        ColorData: TYPE = REF ColorDataPrivate;
        ColorDataPrivate: TYPE = RECORD [
            color: Color,
            nextColor: ColorData _ NIL,
            firstVertex: Vertex _ NIL,
            count: ARRAY RealGraphID OF CARDINAL _ [0, 0],
            newColor: Color _ noColor,
            suspect, multicolored: BOOL _ FALSE
            ];
            <<newColor and multicolored are indexed by oldColor; the rest by curColor.>>

        EnumerateEdges: PROC [v: Vertex, Consume: PROC [Color, Vertex], includeMirror: BOOL] = INLINE {
            FOR e: Edge _ v.firstEdge, e.sides[v.class].next WHILE e # NIL DO
                w: Vertex = e.sides[OtherClass[v.class]].v;
                IF e.sides[v.class].v # v THEN ERROR;
                IF includeMirror OR NOT IsMirror[w] THEN Consume[e.color, w];
                ENDLOOP;
            };

        EnumerateFullEdges: PROC [v: Vertex, Consume: PROC [e: Edge], includeMirror: BOOL] = INLINE {
            nextEdge: Edge _ v.firstEdge;
            FOR e: Edge _ v.firstEdge, nextEdge WHILE e # NIL DO
                w: Vertex = e.sides[OtherClass[v.class]].v;
                IF e.sides[v.class].v # v THEN ERROR;
                nextEdge _ e.sides[v.class].next;
                IF includeMirror OR NOT IsMirror[w] THEN Consume[e];
                ENDLOOP;
            };

        InitialColor: PROC [v: Vertex] RETURNS [Color];

        VName: PROC [v: Vertex] RETURNS [r: ROPE] = INLINE {r _ v.name};
        VDead: PROC [v: Vertex] RETURNS [ded: BOOL] = INLINE {ded _ v.class = cell AND v.type.destroyed};
        OldColor: PROC [v: Vertex] RETURNS [c: Color] = INLINE {c _ v.oldColor};
        SetOldColor: PROC [v: Vertex, c: Color] = INLINE {v.oldColor _ c};
        CurColor: PROC [v: Vertex] RETURNS [c: Color] = INLINE {c _ v.curColor};
        SetCurColor: PROC [v: Vertex, c: Color] = INLINE {v.curColor _ c};
        GetGraph: PROC [v: Vertex] RETURNS [g: GraphID] = INLINE {g _ v.graph};
        SetGraph: PROC [v: Vertex, g: GraphID] = INLINE {v.graph _ g};
        GetUnique: PROC [v: Vertex] RETURNS [b: BOOL] = INLINE {b _ v.unique};
        SetUnique: PROC [v: Vertex, b: BOOL] = INLINE {v.unique _ b};
        GetSuspect: PROC [v: Vertex] RETURNS [b: BOOL] = INLINE {b _ v.suspect};
        SetSuspect: PROC [v: Vertex, b: BOOL] = INLINE {v.suspect _ b};

        GetQNext: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w _ v.QNext};
        SetQNext: PROC [v: Vertex, w: Vertex] = INLINE {v.QNext _ w};
        GetColorNext: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w _ v.colorNext};
        SetColorNext: PROC [v: Vertex, w: Vertex] = INLINE {v.colorNext _ w};
        GetEquiv: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w _ v.equiv};
        SetEquiv: PROC [v: Vertex, w: Vertex] = INLINE {v.equiv _ w};

        END.