
    <<LichenDataStructure.Mesa>>
        <<Mike Spreitzer November 13, 1986 9:02:21 pm PST>>

    DIRECTORY Asserting, Basics, HashTable, IntHashTable, LichenSetTheory, Rope;

    LichenDataStructure: CEDAR DEFINITIONS
        IMPORTS HashTable, IntHashTable =

        BEGIN OPEN LichenSetTheory;

        nyet: ERROR --not yet implemented--;

        Warning: SIGNAL [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL];

        Error: ERROR [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL];

        LORA: TYPE = LIST OF REF ANY;
        LOLORA: TYPE = LIST OF LORA;
        ROPE: TYPE = Rope.ROPE;
        RopeList: TYPE = LIST OF ROPE;
        Assertions: TYPE = Asserting.Assertions;

        RefTable: TYPE = HashTable.Table;
        CreateRefTable: PROC RETURNS [rt: RefTable]
            = INLINE {rt _ HashTable.Create[]};

        IntTable: TYPE = IntHashTable.Table;
        CreateIntTable: PROC RETURNS [it: IntTable]
            = INLINE {it _ IntHashTable.Create[]};

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

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

        Design: TYPE = REF DesignPrivate;
        DesignPrivate: TYPE = RECORD [
            cellTypes: Set,
            other: Assertions _ NIL,
            allKnown: BOOL _ FALSE];

        nameReln: ATOM;    --relative to narrowest enclosing scope
        Describe: PROC [subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [ROPE];

        NameGenerator: TYPE = REF NameGeneratorPrivate;
        NameGeneratorPrivate: TYPE = RECORD [
            GenerateName: PROC [data, subject: REF ANY] RETURNS [ROPE],
            data: REF ANY _ NIL
            ];

        EnumerateCellTypes: PROC [design: Design, Consume: PROC [CellType]];

        CellClass: TYPE = REF CellClassPrivate;
        CellClassPrivate: TYPE = RECORD [
            DefinePrivates: PROC [CellType]
            ];

        CellType: TYPE = REF CellTypePrivate;
        CellTypePrivate: TYPE = RECORD [
            class: CellClass,
            designs: Set,
            publicKnown, privateKnown: BOOL _ FALSE,
            wasntNormalized: BOOL _ FALSE,
                <<Leftover>>
            port: Port _ NIL,
            asUnorganized: Unorganized _ NIL,
            asArray: Array _ NIL,
            firstInstance, lastInstance: CellInstance _ NIL,
            firstArray, lastArray: CellType _ NIL,
            useCount: INT _ 0 --#instances + #arrays--,
            otherPublic, otherPrivate: Assertions _ NIL,
            color: Color _ noColor];

        EnumeratePorts: PROC [cellType: CellType, Consume: PROC [Port]];
        EnumerateInstances: PROC [cellType: CellType, Consume: PROC [CellInstance]];
        EnumerateArrays: PROC [cellType: CellType, Consume: PROC [CellType]];

        partsByNameKey: ATOM;
            <<private CellType >>

        PortList: TYPE = LIST OF Port;
        Port: TYPE = REF PortPrivate;
        PortPrivate: TYPE = RECORD [
            next, prev: Port,
            firstChild, lastChild: Port,
            parent: REF ANY--UNION [Port, CellType]--,
            wire: Wire _ NIL,
            other: Assertions _ NIL,
            color: Color _ noColor];

        PortCCT: PROC [port: Port] RETURNS [containingCT: CellType];
        FirstChildPort: PROC [port: Port] RETURNS [child: Port]
            = INLINE {child _ port.firstChild};
        NextChildPort: PROC [child: Port] RETURNS [sibling: Port]
            = INLINE {sibling _ child.next};

        PortIndex: PROC [parent, child: Port] RETURNS [index: INT];
        SubPort: PROC [parent: Port, index: INT] RETURNS [child: Port];

        Unorganized: TYPE = REF UnorganizedPrivate;
        UnorganizedPrivate: TYPE = RECORD [
            internalWire: Wire _ NIL,
            containedInstances: Set--of CellInstance-- _ NIL,
            mirror: CellInstance _ NIL --the outside world, as seen from the inside
                <<AM1: A mirror is not entered in containedInstances.>>
                <<AM2: A mirror is not counted as an instance of its type.>>
                <<AM3: mirror.type = mirror.container>>
            ];

        Vertex: TYPE = REF VertexPrivate;
        VertexPrivate: TYPE = RECORD [
            containingCT: CellType,
            QNext: Vertex _ notInQ,
            colorNext, equiv: Vertex _ NIL,
            firstEdge, lastEdge: Edge _ NIL,
                <<The connections to/from cells.>>
                <<AI1: The edges are in the following order: first, the cellward ones, if any, in any order, then the wireward ones, ordered by 
                port.>>
            other: Assertions _ NIL,
            oldColor, curColor: Color _ noColor,
            graph: GraphID _ Unspecified,
            unique, suspect: BOOL _ FALSE,
            variant: SELECT class: VertexClass FROM
                cell => [
                    type: CellType _ NIL,
                    nextInstance, prevInstance: CellInstance _ NIL
                    ],
                intermediate => [
                    port: Port
                    ],
                wire => [
                    containingWire: Wire _ NIL,
                    next, prev: Wire _ NIL, --Siblings
                    firstChild, lastChild: Wire _ NIL
                    ],
                ENDCASE];

        VertexClass: TYPE = {cell, intermediate, wire};

        CellInstance: TYPE = REF cell VertexPrivate;
        Intermediary: TYPE = REF intermediate VertexPrivate;
        Wire: TYPE = REF wire VertexPrivate;

        WireIndex: PROC [parent, child: Wire] RETURNS [index: INT];
        SubWire: PROC [parent: Wire, index: INT] RETURNS [child: Wire];
        EnumeratePortAndWire: PROC [port: Port, wire: Wire, Consume: PROC [Port, Wire]];
        FirstChildWire: PROC [parent: Wire] RETURNS [child: Wire]
            = INLINE {child _ parent.firstChild};
        NextChildWire: PROC [child: Wire] RETURNS [sibling: Wire]
            = INLINE {sibling _ child.next};

        Edge: TYPE = REF EdgePrivate;
        EdgePrivate: TYPE = RECORD [
            sides: ARRAY GraphDirection OF RECORD [v: Vertex, next, prev: Edge],
            port: Port --what the wireward vertex is connected to
            ];

        GraphDirection: TYPE = {cellward, wireward};
        OppositeDirection: ARRAY GraphDirection OF GraphDirection = [cellward: wireward, wireward: cellward];

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

        EnumerateImmediateEdges: PROC [v: Vertex, Consume: PROC [Port, Vertex, Edge], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], 
        order: Order _ any];
            <<the Port is the wireward one.>>
        EnumerateImmediateConnections: PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], 
        order: Order _ any];
        EnumerateTransitiveConnections: PROC [v: Vertex, Consume: PROC [Port, Vertex]];
        EnumerateTopEdges: PROC [ci: CellInstance, Consume: PROC [Port, Wire, Edge]];
        EnumerateTopConnections: PROC [ci: CellInstance, Consume: PROC [Port, Wire]];
        EnumerateNeighboringVertices: PROC [v: Vertex, Consume: PROC [Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE]];
        FindImmediateConnection: PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex];
        FindImmediateEdge: PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex, e: Edge];
        FindTransitiveConnection: PROC [cellward: Vertex, port: Port] RETURNS [w: Wire];
        ImParent: PROC [im: Intermediary] RETURNS [v: Vertex];

        Order: TYPE = {forward, backward, any};

        Array: TYPE = REF ArrayPrivate;
        ArrayPrivate: TYPE = RECORD [
            eltType: CellType _ NIL,
            nextArray, prevArray: CellType _ NIL,
            size: Size2 _ ALL[1],
            jointsPeriod: Nat2 _ ALL[1],
            groupingParmses: GroupingParmses,
            groupingses: RefSeq--groupings index 
            toRole: ARRAY Dim OF ARRAY End OF RefTable--dim 
            roles: ARRAY Dim OF VarRefSeq--dim 
            nrp: ARRAY Dim OF NAT _ ALL[0],
            joints: ARRAY Dim--in which we are joining-- OF RefSeq--of Joint-- _ ALL[NIL],
            portConnections: RefTable--ap 
                <<redundant with porting.>>
            porting: RefTable--ep 
                <<porting[p] gives port connections for e[f, b].p, for all f, b on edge of array.>>
            ];

        Dim--ension--: TYPE = {Foo, Bar};
        OtherDim: ARRAY Dim OF Dim = [Foo: Bar, Bar: Foo];

        Size2: TYPE = ARRAY Dim OF NAT;
        Range: TYPE = RECORD [min, maxPlusOne: INT];
        Range2: TYPE = ARRAY Dim OF Range;
        Int2: TYPE = ARRAY Dim OF INT;
        Nat2: TYPE = ARRAY Dim OF NAT;

        Central: PROC [a: Array, ai: ArrayIndex] RETURNS [BOOL];

        GroupingParmses: TYPE = ARRAY Dim OF GroupingParms;
        GroupingParms: TYPE = RECORD [
            middle: Range--or array indices or joint instance indices--,
            firstHigh, sum: NAT,
            
            ];
            <<middle is range of (joint | array) indices covered>>
            <<firstHigh is first grouping index of high range of irregulars>>
            <<>>
            <<hasMiddle = middle.maxPlusOne > middle.min>>
            <<sum = >>
            <<sum = >>
            <<firstHigh = sum - (size-middle.maxPlusOne)>>
            <<>>

        HasMiddle: PROC [gp: GroupingParms] RETURNS [has: BOOL]
            = INLINE {has _ gp.middle.maxPlusOne > gp.middle.min};
        ComputeGroupingsIndex: PROC [a: Array, ai: ArrayIndex] RETURNS [gi2, gii2: Nat2, gi, cgii: NAT];
        GPMiddle: PROC [gp: GroupingParmses] RETURNS [r2: Range2]
            = INLINE {r2 _ [gp[Foo].middle, gp[Bar].middle]};

        Groupings: TYPE = REF GroupingsPrivate;
        GroupingsPrivate: TYPE = RECORD [
            toGroup: RefTable--port 
            groups: Set
            ];

        PortToGroup: PROC [a: Array, gi: NAT, port: Port] RETURNS [g: Group] = INLINE {
            gs: Groupings = NARROW[a.groupingses[gi]];
            g _ NARROW[gs.toGroup.Fetch[port].value];
            };

        GroupListPair: TYPE = ARRAY End OF GroupList;
        GroupList: TYPE = LIST OF Group;
        Group: TYPE = REF GroupPrivate;
        GroupPrivate: TYPE = RECORD [
            ports: PortList _ NIL,
            better: Group _ NIL,
            worse: GroupList _ NIL,
            stopLooking: ARRAY Dim OF ARRAY End OF BOOL _ ALL[ALL[FALSE]]
            ];

        BestGroup: PROC [g: Group] RETURNS [bg: Group]
            = INLINE {IF g = NIL THEN bg _ g ELSE FOR bg _ g, bg.better WHILE bg.better # NIL DO NULL ENDLOOP};

        ComputeJointGroupingsIndex: PROC [a: Array, j: Joint, jii: Nat2] RETURNS [jgi2: Nat2, jgi, ctii: NAT, jiir: Range2];
            <<<low side's groupings index, high side's gi> >>

        Joint: TYPE = REF JointPrivate;
        JointPrivate: TYPE = RECORD [
            size2: Size2--number of instances--,
            size: INT--
            groupingParmses: GroupingParmses,
            ties: RefSeq--joint groupings index 
            toTie: ARRAY End OF RefSeq--side of joint 
            ];

        GetArrayJoint: PROC [a: Array, d: Dim, phase: Nat2] RETURNS [j: Joint]
            = INLINE {j _ NARROW[a.joints[d][ArrayJointIndex[a, phase]]]};
        ArrayJointIndex: PROC [a: Array, phase: Nat2] RETURNS [i: INT]
            = INLINE {i _ phase[Foo]*a.jointsPeriod[Bar] + phase[Bar]};

        Jgi2ToLair: PROC [a: Array, phase: Nat2, j: Joint, jgi2: Nat2] RETURNS [lair, jiir: Range2, jCount: NAT];

        FetchTie: PROC [j: Joint, side: End, jgi: NAT, g: Group] RETURNS [tie: Tie]
            = INLINE {rt: RefTable = NARROW[j.toTie[side][jgi]]; tie _ NARROW[rt.Fetch[g].value]};

        TieList: TYPE = LIST OF Tie;
        Tie: TYPE = REF TiePrivate;
        TiePrivate: TYPE = RECORD [
            groups: ARRAY End OF Group,
            completion: Completion _ NIL,
            better: Tie _ NIL--when tie gets merged with another, better=that union--
            ];

        BestTie: PROC [x: Tie] RETURNS [bx: Tie]
            = INLINE {FOR bx _ x, bx.better WHILE bx.better # NIL DO NULL ENDLOOP};

        GroupsHypotheticallyConnected: PROC [a: Array, j: Joint, jgi: NAT, gs: ARRAY End OF Group] RETURNS [BOOL];

        GroupsActuallyConnected: PROC [a: Array, j: Joint, jgi: NAT, lai: Nat2, gs: ARRAY End OF Group] RETURNS [BOOL];

        RoledPortDataList: TYPE = LIST OF RoledPortData;
        RoledPortData: TYPE = REF RoledPortDataPrivate;
        RoledPortDataPrivate: TYPE = RECORD [
            port: Port,
            side: End,
            index: NAT,
            links: Links _ NIL
            ];

        RoledPortList: TYPE = LIST OF RoledPort;
        RoledPort: TYPE = RECORD [side: End, port: Port];

        FetchRPD: PROC [a: Array, d: Dim, rp: RoledPort] RETURNS [rpd: RoledPortData]
            = INLINE {rpd _ NARROW[a.toRole[d][rp.side].Fetch[rp.port].value]};

        Links: TYPE = REF LinksPrivate;
        LinksPrivate: TYPE = RECORD [
            linkSize: NAT,
            negLinkSize, negLgLinksPerWord: INTEGER,
            lgLinksPerWord: Sublg,
            words: SEQUENCE length: NAT OF WORD
            ];
            <<words[clai ShiftRight lgLinksPerWord] ShiftRight (linkSize*(clai MaskLast lgLinksPerWord)) MaskLast linkSize gives index of 
            another roledPort connected to this one at ji>>
            <<where:>>
                <<clai = <size[Foo], size[Bar]> >>
                <<`>>
                <<size is the size of array>>
                <<lai is the array index of the element on the low side of the joint>>

        GetRoot: PROC [a: Array, d: Dim, rp: RoledPortData, clai: NAT] RETURNS [root: NAT];
        GetNext: PROC [rp: RoledPortData, clai: NAT] RETURNS [next: NAT];
        RPDNeedsLinks: PROC [a: Array, d: Dim, rpd: RoledPortData] RETURNS [needs: BOOL];

        ArrayEltPortsConnected: PROC [a: Array, d: Dim, lowIndex: ArrayIndex, rp1, rp2: RoledPort] RETURNS [hypothetically, really: BOOL];

        Sublg: TYPE = NAT [0 .. Basics.logBitsPerWord];

        Completion: TYPE = REF CompletionPrivate;
        CompletionPrivate: TYPE = RECORD [
            nIncomplete: NAT _ 0,
            complete: PACKED SEQUENCE length: NAT OF BOOL
            ];
            <<complete[instance index] { all connections present at this instance>>

        IsIncompleteArray: PROC [ct: CellType] RETURNS [BOOL];

        Porting: TYPE = REF ANY --actually UNION [{notPorted, unknownPorting}, DetailedPorting]--;
        notPorted: Porting;
        unknownPorting: Porting;
        DetailedPorting: TYPE = REF DetailedPortingRep;
        DetailedPortingRep: TYPE = RECORD [
            corners: ARRAY End--Foo-- OF ARRAY End--Bar-- OF Port,
                <<e[Foo.LAST, Bar.LAST].p >>
                <<NIL means elt port not connected to any array port.>>
            sideIndices: ARRAY End OF ARRAY Dim OF SideIndex,
                <<sideIndices[low][Foo] covers [f, b] >>
            slots: SEQUENCE length: NAT OF Port];

        End: TYPE = {low, high};
        OtherEnd: ARRAY End OF End = [low: high, high: low];

        SideIndex: TYPE = RECORD [same: BOOL, firstSlot: NAT];

        ArrayPortConnections: TYPE = REF ArrayPortConnectionsPrivate;
        ArrayPortConnectionsPrivate: TYPE = ARRAY End OF ARRAY Dim OF SideConnection;
        SideConnection: TYPE = IntTable--index[other dim] 
        ArrayIndex: TYPE = ARRAY Dim OF INT;

        GetArrayPort: PROC [a: Array, index: ArrayIndex, ep: Port] RETURNS [arrayPort: Port];

        RefSeq: TYPE = REF RefSequence;
        RefSequence: TYPE = RECORD [
            elts: SEQUENCE length: NAT OF REF ANY];

        CreateRefSeq: PROC [len: NAT] RETURNS [rs: RefSeq]
            = INLINE {rs _ NEW [RefSequence[len]]};

        VarRefSeq: TYPE = REF VarRefSequence;
        VarRefSequence: TYPE = RECORD [
            length: NAT,
            refs: RefSeq];

        CreateVarRefSeq: PROC [size: NAT _ 12] RETURNS [vrs: VarRefSeq]
            = INLINE {vrs _ NEW [VarRefSequence _ [0, CreateRefSeq[size]]]};

        VarRefSeqAppend: PROC [vrs: VarRefSeq, value: REF ANY];

        BoolSeq: TYPE = REF BoolSequence;
        BoolSequence: TYPE = RECORD [elts: PACKED SEQUENCE length: NAT OF BOOL];

        CreateBoolSeq: PROC [len: NAT, b0: BOOL _ FALSE] RETURNS [bs: BoolSeq]
            = INLINE {bs _ NEW [BoolSequence[len]]; FOR i: NAT IN [0 .. len) DO bs[i] _ b0 ENDLOOP};

        FloorDiv: PROC [num, den: INT] RETURNS [quot: INT];
        CeilDiv: PROC [num, den: INT] RETURNS [quot: INT];

        Int2Add: PROC [a, b: Int2] RETURNS [c: Int2]
            = INLINE {c _ [Foo: a[Foo]+b[Foo], Bar: a[Bar]+b[Bar]]};
        Int2Sub: PROC [a, b: Int2] RETURNS [c: Int2]
            = INLINE {c _ [Foo: a[Foo]-b[Foo], Bar: a[Bar]-b[Bar]]};
        Int2InRange: PROC [i: Int2, r: Range2] RETURNS [in: BOOL]
            = INLINE {in _ i[Foo] IN [r[Foo].min .. r[Foo].maxPlusOne) AND i[Bar] IN [r[Bar].min .. r[Bar].maxPlusOne)};
        Int2Tweak: PROC [i: Int2, d: Dim, 
            = INLINE {j _ i; j[d] _ j[d] + 
        ConsNat2: PROC [d1: Dim, x1, x2: NAT] RETURNS [x: Nat2]
            = INLINE {x[d1] _ x1; x[OtherDim[d1]] _ x2};
        Nat2Add: PROC [a, b: Nat2] RETURNS [c: Nat2]
            = INLINE {c _ [Foo: a[Foo]+b[Foo], Bar: a[Bar]+b[Bar]]};
        Nat2Mul: PROC [a, b: Nat2] RETURNS [c: Nat2]
            = INLINE {c _ [Foo: a[Foo]*b[Foo], Bar: a[Bar]*b[Bar]]};
        Nat2Tweak: PROC [i: Nat2, d: Dim, 
            = INLINE {j _ i; j[d] _ j[d] + 
        Nat2Area: PROC [x: Nat2] RETURNS [a: NAT]
            = INLINE {a _ x[Foo] * x[Bar]};
        RangeOff: PROC [r: Range, 
            = INLINE {s _ [min: r.min + 
        RangeOffClip: PROC [r: Range, 
            = INLINE {s _ [min: MAX[r.min + 
        ShaveRange2Top1: PROC [r: Range2, d: Dim] RETURNS [sr: Range2]
            = INLINE {sr _ r; sr[d].min _ MIN[sr[d].min, sr[d].maxPlusOne _ sr[d].maxPlusOne - 1]};
        ConsRange2: PROC [d1: Dim, x1, x2: Range] RETURNS [x: Range2]
            = INLINE {x[d1] _ x1; x[OtherDim[d1]] _ x2};
        Range2Off: PROC [r: Range2, 
            = INLINE {s _ [Foo: RangeOff[r[Foo], 
        RangeArea: PROC [r: Range2] RETURNS [area: NAT]
            = INLINE {area _ RangeLength[r[Foo]] * RangeLength[r[Bar]]};
        RangeShape: PROC [r: Range2] RETURNS [shape: Nat2]
            = INLINE {shape _ [RangeLength[r[Foo]], RangeLength[r[Bar]]]};
        SizeRange: PROC [size: Nat2] RETURNS [r: Range2]
            = INLINE {r _ [[0, size[Foo]], [0, size[Bar]]]};
        RangeLength: PROC [r: Range] RETURNS [length: NAT]
            = INLINE {length _ r.maxPlusOne - r.min};
        RangesIntersect: PROC [r1, r2: Range] RETURNS [theyDo: BOOL]
            = INLINE {theyDo _
                (r1.min IN [r2.min .. r2.maxPlusOne) AND r1.maxPlusOne > r1.min) OR
                (r2.min IN [r1.min .. r1.maxPlusOne) AND r2.maxPlusOne > r2.min)};
        Range1Mul: PROC [r: Range, 
        Range2Mul: PROC [r: Range2, 
        Range1Div: PROC [r: Range, 
        Range2Div: PROC [r: Range2, 

        END.