
    <<-- File: GCCIGImpl.mesa>>
        <<Copyright © 1986 by Xerox Corporation.  All rights reserved.>>
        <<Last Edited by: Preas, January 15, 1987 11:46:11 am PST>>
        <<Provide operations on a channel intersection graph>>
    <<>>
    DIRECTORY
        CD, CDCells, CDRects, CoreProperties, GC, GCPrivate, GCCIG, D2Basic, HashTable, IP, IPCoTab, IPCTG, IPTop, RTBasic, RTStructure, 
        Graphs0, Graphs0Path;

    GCCIGImpl: CEDAR PROGRAM
        IMPORTS CDCells, CDRects, CoreProperties, GC, GCPrivate, HashTable, IPCoTab, IPCTG, RTBasic, RTStructure, Graphs0, Graphs0Path
        EXPORTS GCCIG
        SHARES GC = BEGIN

        RefINT: TYPE = REF INT;

        IntersectionInfo: TYPE = REF IntersectionInfoRec;
        IntersectionInfoRec: TYPE = RECORD[    -- Info for intersection nodes
            hCh, vCh: IPCTG.Channel _ NIL,    -- Channels for this node
            intersection: IPCTG.Intersection _ NIL    -- Intersection for this node
            ];

        PinInfo: TYPE = REF PinInfoRec;
        PinInfoRec: TYPE = RECORD[    -- Info for pin nodes
            instance: RTStructure.Instance _ NIL,
            oPin: RTStructure.ObjectPin _ NIL,
            pPin: RTStructure.PhysicalPin _ NIL,
            removedArc: Graphs0.Arc _ NIL
            ];

        ArcInfo: TYPE = REF ArcInfoRec;
        ArcInfoRec: TYPE = RECORD[    -- Info for pin nodes
            cost: INT _ 0,
            ch: IPCTG.Channel _ NIL
            ];

        Create: PUBLIC PROC[context: GC.Context] RETURNS[cig: GCCIG.Graph]={

            ConnectHorizontalChannel: IPCTG.EachChannelAction ={

                EachIntersection: IPCTG.EachIntersectionAction ={
                    lastNode _ NewArc[cig, ch, i, lastNode];
                    }; --EachIntersection--

                lastInt: IPCTG.Intersection _ IPCTG.End[ch, neg];
                lastNode: Graphs0.Node _ Graphs0.AddNewNode[cig.graph, NEW[IntersectionInfoRec _ [hCh: ch, vCh: lastInt.ch, intersection: 
                lastInt]]];
                lastInt.any _ lastNode;
                [] _ AllIntersections[ch, EachIntersection];
                [] _ NewArc[cig, ch, IPCTG.End[ch, pos], lastNode];
                }; --CreateIntersectionsForChannel--

            ConnectVerticalChannel: IPCTG.EachChannelAction ={

                EachIntersection: IPCTG.EachIntersectionAction ={
                    currentNode: Graphs0.Node _ NARROW[OppsiteInt[ch, i].any];
                    [] _ Graphs0.AddNewArc[cig.graph, ArcWeight[lastNode, currentNode, ch], lastNode, currentNode];
                    lastNode _ currentNode;
                    }; --EachIntersection--

                lastNode: Graphs0.Node _ NARROW[OppsiteInt[ch, IPCTG.End[ch, neg]].any];
                posNode: Graphs0.Node _ NARROW[OppsiteInt[ch, IPCTG.End[ch, pos]].any];

                [] _ AllIntersections[ch, EachIntersection];
                [] _ Graphs0.AddNewArc[cig.graph, ArcWeight[lastNode, posNode, ch], lastNode, posNode];
                }; --CreateIntersectionsForChannel--

            graph: Graphs0.Graph _ Graphs0.Create[];
            ctg: IPCTG.Ref _ NARROW[context.topology, IPTop.Ref].ctg;
            cig _ NEW[GCCIG.GraphRec _ [context: context, graph: graph]];
            [] _ IPCTG.DirectedChannels[ctg, ConnectHorizontalChannel, hor];
            [] _ IPCTG.DirectedChannels[ctg, ConnectVerticalChannel, ver];
            }; -- Create -- 

        Destroy: PUBLIC PROC [cig: GCCIG.Graph] ={
            Graphs0.Destroy[cig.graph]}; -- Destroy -- 

        InsertNet: PUBLIC PROC[cig: GCCIG.Graph, net: RTStructure.Net, connectionStrength: GCCIG.ConnectionStrength] RETURNS [nodeSetList: 
        GCCIG.NodeSetList _ NIL]~ {
            <<Add the net to cig. >>

            EachPin: RTStructure.EachNetPinAction ~ {
                pinNodes: GCCIG.NodeList _ InsertPin[cig, net, nPin];
                IF pinNodes # NIL THEN {
                    SELECT connectionStrength FROM
                        goodInternal => {
                            FOR list: GCCIG.NodeList _ pinNodes, list.rest WHILE list # NIL DO
                                firstNode: Graphs0.Node _ list.first;
                                IF list.rest # NIL THEN {
                                    secondNode: Graphs0.Node _ list.rest.first;
                                    [] _ Graphs0.AddNewArc[cig.graph, NEW[ArcInfoRec _ [cost: 0, ch: NIL]], firstNode, secondNode]};
                                ENDLOOP;
                            nodeSetList _ CONS[pinNodes, nodeSetList]};
                        power => {
                            FOR list: GCCIG.NodeList _ pinNodes, list.rest WHILE list # NIL DO
                                nodes: GCCIG.NodeList _NIL;
                                nodeSetList _ CONS[CONS[list.first, nodes], nodeSetList];
                                ENDLOOP};
                        highImpedance => nodeSetList _ CONS[pinNodes, nodeSetList];
                        ENDCASE => GC.Error[programmingError, "Not suppose to happen"]}};

            [] _ RTStructure.EnumerateNetPins[net, EachPin];
            }; -- InsertNet -- 

        RemoveNodes: PUBLIC PROC[cig: GCCIG.Graph, nodeSetList: GCCIG.NodeSetList] ~ {
            <<Remove a net from cig>>

            FOR nodeSets: GCCIG.NodeSetList _ nodeSetList, nodeSets.rest WHILE nodeSets # NIL DO
                FOR nodes: GCCIG.NodeList _ nodeSets.first, nodes.rest WHILE nodes # NIL DO
                    node: Graphs0.Node _ nodes.first;
                    WITH node.nodeInfo SELECT FROM
                        int: IntersectionInfo => NULL;
                        pin: PinInfo => {
                            arcs: Graphs0.ArcList _ Graphs0.RemoveNode[cig.graph, node];
                            oldArc: Graphs0.Arc _ NARROW[node.nodeInfo, PinInfo].removedArc;
                            FOR list: Graphs0.ArcList _ arcs, list.rest WHILE list # NIL DO
                                IF list.first.node1 # node AND list.first.node2 # node THEN
                                    GC.Error[programmingError, "Not suppose to happen."];
                                ENDLOOP;
                            [] _ Graphs0.AddNewArc[cig.graph, oldArc.arcInfo, oldArc.node1, oldArc.node2]};
                        ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."];
                    ENDLOOP;
                ENDLOOP;
            }; -- RemoveNodes -- 

        ShortestPath: PUBLIC PROC[cig: GCCIG.Graph, nodeSetList: GCCIG.NodeSetList, net: RTStructure.Net] ~ {
            <<Find shortest path among pins of net>>
            <<>>
            arcCost: Graphs0Path.ArcCostProc ~ {
                cost _ NARROW[arc.arcInfo, ArcInfo].cost};

            arcTraversed: Graphs0Path.EnumArcProc ~ {
                arcInfo: ArcInfo _ NARROW[arc.arcInfo];
                ch: IPCTG.Channel _ NARROW[arcInfo.ch];
                IF ch # NIL THEN {

                    DoNode: PROC [node: GCCIG.Node] ~ {
                        WITH node.nodeInfo SELECT FROM
                            int: IntersectionInfo => {
                                IF EndOfCh[ch, int, neg] THEN netDesc.bottomOrLeftExit _ TRUE;
                                IF EndOfCh[ch, int, pos] THEN netDesc.topOrRightExit _ TRUE};
                            pin: PinInfo => {
                                phyPin: GCPrivate.PhyPinDesc _ NEW[GCPrivate.PhyPinDescRec _ [pin.instance, pin.oPin, pin.pPin]];
                                IF ~GCPrivate.PinOnList[netDesc, phyPin] THEN
                                    netDesc.pinList _ CONS[phyPin, netDesc.pinList]};
                            ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."];
                        };

                    channel: GCPrivate.Channel _ NARROW[ch.any];
                    value: REF ANY _ HashTable.Fetch[channel.connections, net].value;
                    netDesc: GCPrivate.NetDesc _ IF value = NIL THEN NEW[GCPrivate.NetDescRec]
                        ELSE NARROW[value];
                    DoNode[arc.node1];
                    DoNode[arc.node2];
                    [] _ HashTable.Store[channel.connections, net, netDesc]}};

            [] _ Graphs0Path.FindPath[graph: cig.graph, nodeSets: nodeSetList, arcCostProc: arcCost, arcDeliverProc: arcTraversed]};

        Check: PUBLIC PROC [cig: GCCIG.Graph] ={
            Graphs0.Check[cig.graph]}; -- Check--

        PaintShortestPath: PUBLIC PROC[cig: GCCIG.Graph, nodeSetList: GCCIG.NodeSetList] RETURNS [object: CD.Object] ~ {
            <<Find shortest path among nodeSetList and construct a ChipNDale object>>
            <<>>
            arcCost: Graphs0Path.ArcCostProc ~ {
                cost _ NARROW[arc.arcInfo, ArcInfo].cost};

            arcTraversed: Graphs0Path.EnumArcProc ~ {
                layer: CD.Layer _ cig.context.rules.vertRules.branchLayer;
                MakeCDArc[arc, object, layer]};

            object _ PaintGraph[cig];
            [] _ Graphs0Path.FindPath[graph: cig.graph, nodeSets: nodeSetList, arcCostProc: arcCost, arcDeliverProc: arcTraversed]};

        PaintGraph: PUBLIC PROC [cig: GCCIG.Graph] RETURNS [object: CD.Object _ CDCells.CreateEmptyCell[]] ~ {

            EachNode: Graphs0.EnumNodeProc ~ {
                layer: CD.Layer _ cig.context.rules.horizRules.trunkLayer;
                MakeCDNode[node, object, layer]};

            EachArc: Graphs0.EnumArcProc ~ {
                layer: CD.Layer _ cig.context.rules.vertRules.trunkLayer;
                MakeCDArc[arc, object, layer]};

            [] _ Graphs0.EnumNodes[cig.graph, EachNode];
            [] _ Graphs0.EnumArcs[cig.graph, EachArc];
            RTBasic.RepositionCell[object]};
    <<Internal Procedures>>
        InsertPin: PROC[cig: GCCIG.Graph, net: RTStructure.Net, nPin: RTStructure.NetPin] RETURNS [pinNodes: GCCIG.NodeList _ NIL] ~ {
            <<Add the pin to cig.>>

            IF nPin.oPin.heirarchyLevel = this THEN {
                <<this is an internal (private) pin>>

                InsertPhysicalPin: RTStructure.EachPhysicalPinAction ~ {
                    <<PROC [oPin: ObjectPin, pPin: PhysicalPin] RETURNS [quit: BOOLEAN _ FALSE];>>
                    oldArc: Graphs0.Arc _ FindArcForPin[cig, nPin.instance, oPin, pPin];
                    arcInfo: ArcInfo _ NARROW[oldArc.arcInfo];
                    newNode: Graphs0.Node _ Graphs0.AddNewNode[cig.graph, NEW[PinInfoRec _ [instance: nPin.instance, oPin: oPin, pPin: pPin, 
                    removedArc: oldArc]]];
                    pinNodes _ CONS[newNode, pinNodes];
                    [] _ Graphs0.AddNewArc[cig.graph, ArcWeight[oldArc.node1, newNode, arcInfo.ch], oldArc.node1, newNode];
                    [] _ Graphs0.AddNewArc[cig.graph, ArcWeight[newNode, oldArc.node2, arcInfo.ch], newNode, oldArc.node2];
                    Graphs0.RemoveArc[cig.graph, oldArc]};

                [] _ RTStructure.EnumeratePhysicalPins[nPin.oPin, InsertPhysicalPin]}
            ELSE {
                <<this is a public pin>>

                EachNode: Graphs0.EnumNodeProc ~ {
                    WITH node.nodeInfo SELECT FROM
                        int: IntersectionInfo => {
                            useThisOne: BOOLEAN _ SELECT side FROM
                                bottom => int.hCh = bottomChannel,
                                right => int.vCh = rightChannel,
                                top => int.hCh = topChannel,
                                left => int.vCh = leftChannel,
                                ENDCASE => FALSE;
                            IF useThisOne AND ~MemberNode[node, pinNodes] THEN
                                pinNodes _ CONS[node, pinNodes]};
                        pin: PinInfo => NULL;
                        ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."]};

                sideProp: ATOM _ NARROW[CoreProperties.GetProp[net.properties, GC.sideProp]];
                side: RTBasic.SideOrNone _ GetSide[sideProp];
                topology: IPTop.Ref _ NARROW[cig.context.topology];
                bottomChannel, rightChannel, topChannel, leftChannel: IPCTG.Channel;
                [bottomChannel, rightChannel, topChannel, leftChannel] _ IPCTG.GetBoundingChannels[topology.ctg];
                IF ~FacesSide[cig, net, side] THEN [] _ Graphs0.EnumNodes[cig.graph, EachNode]}}; -- InsertPin -- 

        ArcWeight: PROC [node1, node2: Graphs0.Node, ch: IPCTG.Channel] RETURNS [arcInfo: ArcInfo] ~ {

            arcInfo _ NEW[ArcInfoRec _ [cost: ABS[PQPosOfNode[node1, ch.type].p - PQPosOfNode[node2, ch.type].p], ch: ch]]};

        NewArc: PROC [cig: GCCIG.Graph, hCh: IPCTG.Channel, int: IPCTG.Intersection, lastNode: Graphs0.Node] RETURNS [currentNode: 
        Graphs0.Node]~ {
            currentNode _ Graphs0.AddNewNode[cig.graph, NEW[IntersectionInfoRec _ [hCh: hCh, vCh: int.ch, intersection: int]]];
            int.any _ currentNode;
            [] _ Graphs0.AddNewArc[cig.graph, ArcWeight[lastNode, currentNode, hCh], lastNode, currentNode]};

        AllIntersections: PROC [ch: IPCTG.Channel, p: IPCTG.EachIntersectionAction] RETURNS [quit: BOOL] ~ {

            Wrap: IPCTG.EachIntersectionAction ~ {
                IF i.type = 1 THEN quit _ p[i]};

            quit _ IPCTG.Intersections[ch, neg, p];            -- enumerate all below and crossing intersections
            IF ~quit THEN quit _ IPCTG.Intersections[ch, pos, Wrap];    -- enumerate above intersections 
            };

        FindArcForPin: PROC [cig: GCCIG.Graph, instance: RTStructure.Instance, oPin: RTStructure.ObjectPin, pPin: RTStructure.PhysicalPin] 
        RETURNS [foundArc: Graphs0.Arc _ NIL] ~ {

            ArcProc: Graphs0.EnumArcProc ~ {
                node1: Graphs0.Node _ NARROW[arc.node1];
                posNode1: INT _ PQPosOfNode[node1, ch.type].p;
                node2: Graphs0.Node _ NARROW[arc.node2];
                posNode2: INT _ PQPosOfNode[node2, ch.type].p;
                arcCh: IPCTG.Channel _ NARROW[arc.arcInfo, ArcInfo].ch;
                norm: BOOLEAN _ posNode1 <= pos AND pos <= posNode2;
                rev: BOOLEAN _ posNode2 <= pos AND pos <= posNode1;
                IF ch = arcCh AND (norm OR rev) THEN {quit _ TRUE; foundArc _ arc}
                };

            ch: IPCTG.Channel _ IPCoTab.GetPrinCh[NARROW[instance.any], SideToEdgeType[pPin.side]];
            range: RTStructure.Range _ RTStructure.TranslateRange[instance, pPin];
            pos: INT _ (range.min + range.max)/2;
            IF ~Graphs0.EnumArcs[cig.graph, ArcProc] THEN 
                GC.Error[programmingError, "Not suppose to happen."]};

        SideToEdgeType: PROC [side: RTBasic.Side] RETURNS [et: IP.EdgeTypes] ~ {
            et _ SELECT side FROM
                top => north,
                left => west,
                bottom => south,
                right => east,
                ENDCASE => GC.Error[programmingError, "Call maintainer"]};

        OppsiteInt: PROC [ch: IPCTG.Channel, i: IPCTG.Intersection] RETURNS [oppsiteI: IPCTG.Intersection] ~ {
            <<find intersection on oppsite channel corresponding to this one>>

            IntTest: IPCTG.EachIntersectionAction ~ {
                IF i.ch = ch THEN {oppsiteI _ i; quit _ TRUE}};

            quit: BOOLEAN _ AllIntersections[i.ch, IntTest];
            IF ~quit THEN quit _ IntTest[IPCTG.End[i.ch, neg]];
            IF ~quit THEN quit _ IntTest[IPCTG.End[i.ch, pos]];
            IF ~quit THEN GC.Error[programmingError, "Not suppose to happen."]};

        PQPosOfNode: PROC [node: Graphs0.Node, direction: IP.ChType] RETURNS [RTBasic.PQPos] ~ {
            <<find position of node in direction>>

            p, q: INT;
            WITH node.nodeInfo SELECT FROM
                int: IntersectionInfo =>
                    IF direction = hor THEN {
                        p _ int.vCh.coord; q _ int.hCh.coord}
                    ELSE {
                        p _ int.hCh.coord; q _ int.vCh.coord};
                pin: PinInfo => {
                    range: RTStructure.Range _ RTStructure.TranslateRange[pin.instance, pin.pPin];
                    ch: IPCTG.Channel _ IPCoTab.GetPrinCh[NARROW[pin.instance.any], SideToEdgeType[pin.pPin.side]];
                    p _ (range.min + range.max)/2; q _ ch.coord};
                ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."];
            RETURN[[p, q]]};

        PosOfNode: PROC [node: Graphs0.Node] RETURNS [D2Basic.Vector] ~ {
            <<find position of node>>

            x, y: INT;
            WITH node.nodeInfo SELECT FROM
                int: IntersectionInfo => {x _ int.vCh.coord; y _ int.hCh.coord};
                pin: PinInfo => {
                    range: RTStructure.Range _ RTStructure.TranslateRange[pin.instance, pin.pPin];
                    middle: INT _ (range.min + range.max)/2;
                    ch: IPCTG.Channel _ IPCoTab.GetPrinCh[NARROW[pin.instance.any], SideToEdgeType[pin.pPin.side]];
                    IF ch.type = hor THEN {x _ middle; y _ ch.coord}
                    ELSE {x _ ch.coord; y _ middle}};
                ENDCASE => GC.Error[callingError, "Invalid nodeInfo type."];
            RETURN[[x, y]]};

        Length: PUBLIC PROC [nodeSetList: GCCIG.NodeSetList] RETURNS[n: INT _ 0] = {
            UNTIL nodeSetList = NIL DO
                n _ n+1;
                nodeSetList _ nodeSetList.rest;
                ENDLOOP};

        EndOfCh: PROC [ch: IPCTG.Channel, int: IntersectionInfo, pol: IP.PolarityTypes] RETURNS [found: BOOLEAN _ FALSE] ~ {
            <<RETURN TRUE if node is at end co ch represented by pol>>

            trial: IPCTG.Channel _ IF ch.type = hor THEN int.vCh ELSE int.hCh;
            IF trial = IPCTG.End[ch, pol].ch THEN found _ TRUE};

        MemberNode: PROC [node: GCCIG.Node, list: GCCIG.NodeList] RETURNS [BOOL] = {
            UNTIL list = NIL DO
                IF list.first = node THEN RETURN[TRUE];
                list _ list.rest;
                ENDLOOP;
            RETURN[FALSE]};

        MakeCDNode: PROC [node: Graphs0.Node, object: CD.Object, nodeLayer: CD.Layer] ~ {
            size: D2Basic.Vector _ [8, 8];
            pos: D2Basic.Vector _ PosOfNode[node];
            nodeObj: CD.Object _ CDRects.CreateRect[size, nodeLayer];
            [] _ GCPrivate.IncludeOb[object, nodeObj, [pos.x - size.x/2, pos.y - size.y/2]]};

        MakeCDArc: PROC [arc: Graphs0.Arc, object: CD.Object, arcLayer: CD.Layer] ~ {

            width: INT _ 4;
            pos1: D2Basic.Vector _ PosOfNode[arc.node1];
            pos2: D2Basic.Vector _ PosOfNode[arc.node2];
            xDim: INT _ MAX[ABS[pos1.x - pos2.x], width];
            yDim: INT _ MAX[ABS[pos1.y - pos2.y], width];
            arcObj: CD.Object _ CDRects.CreateRect[[xDim, yDim], arcLayer];
            pos: D2Basic.Vector _ IF pos1.x = pos2.x THEN [pos1.x - width/2, MIN[pos1.y, pos2.y]]
                ELSE IF pos1.y = pos2.y THEN [MIN[pos1.x, pos2.x], pos1.y - width/2]
                ELSE [MIN[pos1.x, pos2.x], MIN[pos1.y, pos2.y]];
            [] _ GCPrivate.IncludeOb[object, arcObj, pos]};

        FacesSide: PROC [cig: GCCIG.Graph, net: RTStructure.Net, side: RTBasic.SideOrNone] RETURNS [faces: BOOLEAN] ~ {
            <<RETURNS TRUE iff this net has a physical pin on a boundry for the higher level cell>>

            EachNetPin: RTStructure.EachNetPinAction ~ {
                EachPhysicalPin: RTStructure.EachPhysicalPinAction ~ {
                    <<PROC [oPin: ObjectPin, pPin: PhysicalPin] RETURNS [quit: BOOLEAN _ FALSE];>>
                    ch: IPCTG.Channel _ IPCoTab.GetPrinCh[NARROW[nPin.instance.any], SideToEdgeType[pPin.side]];
                    IF IPCTG.IsBoundingChannel[topology.ctg, ch] THEN {
                        quit _ IF side = none THEN quit _ TRUE ELSE pPin.side = side}};

                quit _ RTStructure.EnumeratePhysicalPins[nPin.oPin, EachPhysicalPin]};

            topology: IPTop.Ref _ NARROW[cig.context.topology];
            faces _ RTStructure.EnumerateNetPins[net, EachNetPin]};

        GetSide: PROC [atom: ATOM] RETURNS [side: RTBasic.SideOrNone] ~ {
            side _ SELECT atom FROM
                GC.bottomSideValue => bottom,
                GC.rightSideValue => right,
                GC.topSideValue => top,
                GC.leftSideValue => left,
                ENDCASE => none};

        END.