
<<GCCIGImpl.mesa>>
<<Copyright © 1986 by Xerox Corporation.  All rights reserved.>>
<<Last Edited by: Preas, January 15, 1987 11:46:11 am PST>>
    <<Massoud Pedram June 24, 1988 11:47:08 am PDT>>
<<Don Curry December 4, 1987 4:18:30 pm PST>>
<<Provide operations on a channel intersection graph>>
<<>>
DIRECTORY
CD, CDCells, CDRects, DABasics, GC, GCPrivate, GCCIG, IP, IPCoTab, IPCTG, IPTop, RefTab, Route, RTBasic, CoreRouteFlat, Graphs0, 
Graphs0Path, Basics;

GCCIGImpl: CEDAR PROGRAM
IMPORTS CDCells, CDRects, GC, GCPrivate, IPCoTab, IPCTG, RefTab, CoreRouteFlat, Graphs0, Graphs0Path, Basics
EXPORTS GCCIG
<<SHARES GC = BEGIN>>
= BEGIN

RefINT:                TYPE = REF INT;

IntersectionInfo:        TYPE = REF IntersectionInfoRec;
IntersectionInfoRec:    TYPE = RECORD[    -- Info for intersection nodes
hCh:            IPCTG.Channel        _ NIL,    -- Channels for this node
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:        CoreRouteFlat.Instance    _ NIL,
oNode:        CoreRouteFlat.ONode    _ NIL,
pPin:            CoreRouteFlat.Pin        _ [ ],
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]};
            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;
            [] _ AllIntersectionsOrdered[ch, EachIntersection];
            [] _ NewArc[cig, ch, IPCTG.End[ch, pos], lastNode]};

        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};
            lastNode: Graphs0.Node _ NARROW[OppsiteInt[ch, IPCTG.End[ch, neg]].any];
            posNode: Graphs0.Node _ NARROW[OppsiteInt[ch, IPCTG.End[ch, pos]].any];
            [] _ AllIntersectionsOrdered[ch, EachIntersection];
            [] _ Graphs0.AddNewArc
                [cig.graph, ArcWeight[lastNode, posNode, ch], lastNode, posNode]};

        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]};

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

    UpdateCIGWeights: PUBLIC PROC [cig: GCCIG.Graph] = {

    enumArc: Graphs0.EnumArcProc ~ {
    <<PROC[graph: Graph, arc: Arc, data: REF] RETURNS [quit: BOOL _ FALSE];>>
    arcInfo: ArcInfo _ NARROW[arc.arcInfo];
    arcInfo.cost _ ArcWeight[arc.node1, arc.node2, arcInfo.ch].cost};

    [] _ Graphs0.EnumArcs[cig.graph, enumArc]};  -- UpdateCIGWeights

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

        IF connectionStrength # none THEN {
            FOR ins: LIST OF CoreRouteFlat.InstONode _ net.instONodes, ins.rest WHILE ins#NIL DO 
                pinNodes: GCCIG.NodeList _ InsertPin[cig, net, ins.first];
                IF pinNodes # NIL THEN {
                    SELECT connectionStrength FROM
                        goodInternal => {
                            IF NOT ins.first.oNode.public THEN {
                                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 => {
                            IF NOT ins.first.oNode.public THEN {
                                FOR list: GCCIG.NodeList _ pinNodes, list.rest WHILE list # NIL DO
                                    nodes: GCCIG.NodeList _NIL;
                                    nodeSetList _ CONS[CONS[list.first, nodes], nodeSetList] ENDLOOP}
                            ELSE nodeSetList _ CONS[pinNodes, nodeSetList]};
                        highImpedance => nodeSetList _ CONS[pinNodes, nodeSetList];
                        ENDCASE => GC.Error[programmingError, "Not suppose to happen"]}
                ENDLOOP}};

    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: CoreRouteFlat.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
                            ELSE IF EndOfCh[ch, int, pos] THEN netDesc.topOrRightExit _ TRUE
                            ELSE {
                                <<add channel intersection data to list>>
                                intersectionPin: GCPrivate.IntersectionPinDesc _ IF ch.type = ver THEN
                                    NEW[GCPrivate.IntersectionPinDescRec _ [NARROW[int.hCh.any]]]
                                    ELSE NEW[GCPrivate.IntersectionPinDescRec _ [NARROW[int.vCh.any]]];
                                IF ~GCPrivate.IntersectionOnList[netDesc, intersectionPin] THEN
                                    netDesc.intersectionList _ CONS[intersectionPin, netDesc.intersectionList]
                                }};
                        pin: PinInfo => {
                            phyPin: GCPrivate.PhyPinDesc _ NEW[GCPrivate.PhyPinDescRec _ [pin.instance, pin.oNode, 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];
                val:    REF ANY _ RefTab.Fetch[channel.connections, net].val;
                netDesc:    GCPrivate.NetDesc _ IF val = NIL
                    THEN    NEW[GCPrivate.NetDescRec]
                    ELSE    NARROW[val];
                DoNode[arc.node1];
                DoNode[arc.node2];
                [] _ RefTab.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--

    Audit: PUBLIC PROC [cig: GCCIG.Graph] ={
    <<check for invalid arcs left in the graph>>
    AuditOneArc: Graphs0.EnumArcProc ~ {
    <<PROC[graph: Graph, arc: Arc, data: REF] RETURNS [quit: BOOL _ FALSE];>>
    cost: INT _ NARROW[arc.arcInfo, ArcInfo].cost;
    ch: IPCTG.Channel _ NARROW[arc.arcInfo, ArcInfo].ch;
        IF cost = 0 OR ch = NIL THEN cost _ 0};

    [] _ Graphs0.EnumArcs[cig.graph, AuditOneArc]
        }; -- Audit--

    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]};
<<Internal Procedures>>
    InsertPin: PROC[cig: GCCIG.Graph, net: CoreRouteFlat.Net, instONode: CoreRouteFlat.InstONode]
        RETURNS [pinNodes: GCCIG.NodeList _ NIL] ~ {
        <<Add the pin to cig.>>
        IF instONode.oNode.public THEN { -- this is a public object node
            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."]};
            side: DABasics.Side;
            bottomChannel, rightChannel, topChannel, leftChannel: IPCTG.Channel;
            FOR side IN DABasics.Side DO
                topology:    IPTop.Ref _ NARROW[cig.context.topology];
                IF ~ParentFacesSide[net, side] THEN LOOP;
                [bottomChannel, rightChannel, topChannel, leftChannel] _
                    IPCTG.GetBoundingChannels[topology.ctg];
                IF ~ChildrenFaceSide[cig, net, side] THEN
                    [] _ Graphs0.EnumNodes[cig.graph, EachNode];
                        <<If the children don't face the side then channel intersection nodes must be sources and targets in the shortest path search.>>
                ENDLOOP}
            ELSE
                FOR pins: LIST OF CoreRouteFlat.Pin _ instONode.oNode.pins, pins.rest
                    WHILE pins#NIL DO 
                        channel: GCPrivate.Channel _ NARROW[IPCoTab.GetPrinCh[NARROW[instONode.instance.any], SideToEdgeType[pins.first.side]].any];
                        rules: Route.DesignRules _ IF channel.direction = horizontal
                            THEN    cig.context.rules.horizRules
                            ELSE    cig.context.rules.vertRules;
                        branchLayer: CD.Layer _ rules.branchLayer;
                        IF pins.first.layer = branchLayer THEN {
                            oldArc:    Graphs0.Arc _ FindArcForPin[cig, instONode.instance, pins.first];
                            arcInfo:    ArcInfo _ NARROW[oldArc.arcInfo];
                            newNode:    Graphs0.Node _ Graphs0.AddNewNode[cig.graph, NEW[PinInfoRec _ [
                                instance:    instONode.instance,
                                oNode:    instONode.oNode,
                                pPin:    pins.first,
                                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]}
                        ENDLOOP}; -- InsertPin -- 

    ParentFacesSide: PROC [net: CoreRouteFlat.Net, side: DABasics.Side]
        RETURNS [faces: BOOLEAN _ FALSE] ~ {
            FOR ins: LIST OF CoreRouteFlat.InstONode _ net.instONodes, ins.rest WHILE ins#NIL DO 
                IF ~ins.first.oNode.public THEN LOOP;
                FOR pins: LIST OF CoreRouteFlat.Pin _ ins.first.oNode.pins, pins.rest WHILE pins#NIL DO 
                    IF pins.first.side = side THEN RETURN[TRUE] ENDLOOP ENDLOOP};

    ChildrenFaceSide: PROC [cig: GCCIG.Graph, net: CoreRouteFlat.Net, side: DABasics.Side]
        RETURNS [faces: BOOLEAN _ FALSE] ~ {
        <<RETURNS TRUE iff this net has a physical pin on a boundry for the higher level cell>>
        topology: IPTop.Ref _ NARROW[cig.context.topology];
        FOR ins: LIST OF CoreRouteFlat.InstONode _ net.instONodes, ins.rest WHILE ins#NIL DO 
            IF ins.first.oNode.public THEN LOOP;
            FOR pins: LIST OF CoreRouteFlat.Pin _ ins.first.oNode.pins, pins.rest WHILE pins#NIL DO 
                ch: IPCTG.Channel _ IPCoTab.GetPrinCh
                    [NARROW[ins.first.instance.any], SideToEdgeType[pins.first.side]];
                IF IPCTG.IsBoundingChannel[topology.ctg, ch] THEN
                IF pins.first.side = side THEN RETURN[TRUE] ENDLOOP ENDLOOP};

    ArcWeight: PROC [node1, node2: Graphs0.Node, ch: IPCTG.Channel]
        RETURNS [arcInfo: ArcInfo] ~ {
        congestionPen: INT _ 500000;
        channel: GCPrivate.Channel _ NARROW[ch.any]; 
        node1Pos: INT _ PQPosOfNode[node1, ch.type].p;
        node2Pos: INT _ PQPosOfNode[node2, ch.type].p;
        extraWeight: INT _ 0;
        minPos: INT _ IF node1Pos < node2Pos THEN node1Pos ELSE node2Pos;
        maxPos: INT _ IF node1Pos >= node2Pos THEN node1Pos ELSE node2Pos;
        <<Add extraWeight only if channel is critical>>
        IF channel.ch.slack.neg = channel.ch.slack.pos THEN 
            IF channel.trackInfo#NIL THEN
                FOR list: LIST OF RTBasic.Range _ channel.trackInfo.rangeList, list.rest WHILE list # NIL DO
                    range: RTBasic.Range _ list.first;
                    IF extraWeight=0 THEN
                        extraWeight _ IF (range.l <= minPos AND range.r <= minPos) OR (range.l >= maxPos AND range.r >= maxPos) THEN 0 ELSE congestionPen;
                    ENDLOOP;
        arcInfo _ NEW[ArcInfoRec _ [cost: maxPos-minPos+extraWeight, 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]};

CompareCoord: PROC [ref1, ref2: REF IP.IntersectionNodeRep] RETURNS [Basics.Comparison] ~ { 
coord1: INT _ NARROW[ref1, REF IP.IntersectionNodeRep].intersection.ch.coord;
coord2: INT _ NARROW[ref2, REF IP.IntersectionNodeRep].intersection.ch.coord;
RETURN[Basics.CompareInt[coord1, coord2]]};  -- CompareCoord

    AllIntersectionsOrdered: PROC [ch: IPCTG.Channel, p: IPCTG.EachIntersectionAction]
        RETURNS [quit: BOOL _ FALSE] ~ {
        negList: LIST OF REF IP.IntersectionNodeRep _ ch.boundary.negSideHd;
        posList: LIST OF REF IP.IntersectionNodeRep _ ch.boundary.posSideHd;
        WHILE negList # NIL OR posList # NIL DO
            IF negList #  NIL AND posList = NIL THEN {
                quit _  p[negList.first.intersection]; negList _ negList.rest}
            ELSE IF posList # NIL AND negList = NIL THEN {
                quit _  p[posList.first.intersection]; posList _ posList.rest}
            ELSE IF CompareCoord[negList.first, posList.first] = less THEN {
                quit _  p[negList.first.intersection]; negList _ negList.rest}
            ELSE {
                quit _  p[posList.first.intersection]; posList _ posList.rest}
            ENDLOOP;
        };


    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: CoreRouteFlat.Instance, pin: CoreRouteFlat.Pin]
            RETURNS [foundArc: Graphs0.Arc _ NIL] ~ {
        ArcProc: Graphs0.EnumArcProc ~ {
            arcCh:    IPCTG.Channel _ NARROW[arc.arcInfo, ArcInfo].ch;
            node1:    Graphs0.Node _ NARROW[arc.node1];
            node2:    Graphs0.Node _ NARROW[arc.node2];
            posNode1:    INT _ PQPosOfNode[node1, ch.type].p;
            posNode2:    INT _ PQPosOfNode[node2, ch.type].p;
            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[pin.side]];
        range: CoreRouteFlat.Range _ CoreRouteFlat.TranslateRange[instance, pin];
        pos: INT _ (range.min + range.max)/2;
        IF ~Graphs0.EnumArcs[cig.graph, ArcProc] THEN 
            GC.Error[programmingError, "Not suppose to happen."]};

    SideToEdgeType: PROC [side: DABasics.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: CoreRouteFlat.Range _ CoreRouteFlat.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 [DABasics.Position] ~ {
        <<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: CoreRouteFlat.Range _ CoreRouteFlat.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] ~ { -- TRUE if node is at end of 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:        DABasics.Position _ [8, 8];
pos:        DABasics.Position _ 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:    DABasics.Position _ PosOfNode[arc.node1];
        pos2:    DABasics.Position _ 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:    DABasics.Position _ 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]};

END.