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
= 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 ~ {
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] ~ {

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] ~ {

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] ~ {

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 {
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] ={
AuditOneArc: Graphs0.EnumArcProc ~ {
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] ~ {
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]};
InsertPin: PROC[cig: GCCIG.Graph, net: CoreRouteFlat.Net, instONode: CoreRouteFlat.InstONode]
RETURNS [pinNodes: GCCIG.NodeList _ NIL] ~ {
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];
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] ~ {
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;
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] ~ {
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] ~ {
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] ~ {

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.
6GCCIGImpl.mesa
Copyright c 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

SHARES GC = BEGIN
PROC[graph: Graph, arc: Arc, data: REF] RETURNS [quit: BOOL _ FALSE];
Add the net to cig. 
Remove a net from cig
Find shortest path among pins of net
add channel intersection data to list
check for invalid arcs left in the graph
PROC[graph: Graph, arc: Arc, data: REF] RETURNS [quit: BOOL _ FALSE];
Find shortest path among nodeSetList and construct a ChipNDale object
Internal Procedures
Add the pin to cig.
If the children don't face the side then channel intersection nodes must be sources and targets in the shortest path search.
RETURNS TRUE iff this net has a physical pin on a boundry for the higher level cell
Add extraWeight only if channel is critical
find intersection on oppsite channel corresponding to this one
find position of node in direction
find position of node
Κˆ˜š
Οc™Jšœ
Οm
œ1™<JšœΟk ™7Icode™,J™)J™2—J™š
Ÿ	˜	Jš
ŸœŸœ
ŸœŸœŸœM˜•
J˜—šΟn	œŸœ
Ÿ˜JšŸœŸœŸœ5˜lJšŸœ
Ÿ˜
JšŸœ
ŸœŸ™šœŸ˜J˜—šœŸœŸœ
Ÿœ
˜J˜—JšœŸœŸœ˜2šœŸœŸœ˜BJšœŸœŸœ˜6JšœŸœŸœ˜6JšœŸœŸœ˜FJ˜J˜—Jšœ
ŸœŸœ˜ šœŸœŸœ˜0Jšœ$Ÿœ
˜(JšœŸœ
˜"Jš
œ!˜!JšœŸœ˜"J˜—Jšœ
ŸœŸœ˜ šœŸœŸœ˜0JšœŸœ˜JšœŸœŸœ˜J˜—š œŸœ
Ÿœ
Ÿœ
ŸœŸœ	˜DK–

"Cedar" style˜–

"Cedar" styleš œŸœ˜4–

"Cedar" styleš œŸœ˜0Kš
œ*˜*—K–

"Cedar" stylešœ	ŸœŸœ˜1–

"Cedar" stylešœ7Ÿ˜:K–

"Cedar" styleš
œK˜K—K–

"Cedar" styleš
œ˜K–

"Cedar" styleš
œ3˜3KšœŸœ˜4K–

"Cedar" style˜—–

"Cedar" styleš œŸœ˜2–

"Cedar" styleš œŸœ˜2KšœŸœ˜:K–

"Cedar" styleš
œ_˜_K–

"Cedar" styleš
œ˜—K–

"Cedar" stylešœŸœŸœ˜HK–

"Cedar" stylešœŸœŸœ˜GK–

"Cedar" styleš
œ3˜3–

"Cedar" styleš
œ˜K–

"Cedar" styleš
œB˜B—K–

"Cedar" style˜—K–

"Cedar" styleš
œ(˜(K–

"Cedar" stylešœŸœŸœ"˜9K–

"Cedar" stylešœŸœ
Ÿœ.˜=K–

"Cedar" stylešœŸœ6˜@K–

"Cedar" stylešœŸœ5˜?K˜—š œŸœ
ŸœŸœ'˜GK˜—š œŸœ
ŸœŸœ˜4J˜š
œ ˜ Jš
ŸœŸœŸœŸœŸœ™EJšœŸœ˜'Jš
œA˜A—J˜Jšœ-˜@—J˜š 	œŸœ
Ÿ˜šœŸœ4Ÿœ˜XKšŸœŸœŸœ˜2—Kš
œ™K˜šŸœŸœ˜#šŸœŸœ
Ÿœ4ŸœŸœ
Ÿœ
˜UKšœ
Ÿœ+˜:šŸœŸœ
Ÿœ˜šŸœŸ˜š
œ˜šŸœ
ŸœŸœ˜$š	ŸœŸœ ŸœŸœ
Ÿ˜BKš
œ%˜%šŸœ
Ÿœ
Ÿœ˜Kš
œ+˜+š
œ˜KšœŸœŸœ˜J——KšŸœ˜	——KšœŸœ˜+—š
œ
˜
šŸœ
ŸœŸœ˜$š	ŸœŸœ ŸœŸœ
Ÿ˜BKšœŸœŸœ
˜KšœŸœ
Ÿœ"Ÿœ
˜A——KšŸœŸœ˜0—KšœŸœ˜;KšŸœŸœ2˜?——KšŸœ˜
——K˜—š
 œŸœ
ŸœŸœŸœ˜NKš
œ™K˜š	ŸœŸœ*ŸœŸœ
Ÿ˜Tš	ŸœŸœ'Ÿœ	Ÿœ
Ÿ˜KKš
œ!˜!šŸœŸœ
Ÿ˜KšœŸœ
˜š
œ˜Kš
œ<˜<KšœŸœ$˜@šŸœ)ŸœŸœ
Ÿ˜?šŸœŸœŸ˜;KšŸœ3˜5—KšŸœ
˜—Kš
œO˜O—KšŸœŸœ/˜<—KšŸœ
˜—KšŸœ
˜—Kšœœ
˜K˜—š
 œŸœ
ŸœŸœŸœ)˜gK™$K˜Kš œ$Ÿœ˜NK˜š œ˜)KšœŸœ˜'KšœŸœŸœ
˜'šŸœŸœ
Ÿœ˜š œŸœŸœ
˜#šŸœŸœ
Ÿ˜š
œ˜KšŸœŸœŸ˜=KšŸœ
ŸœŸœŸ˜@šŸœ˜Kš
œ%™%šœ1ŸœŸ˜FKšŸœ%Ÿœ˜=KšŸœ
Ÿœ%Ÿœ˜C—šŸœ9Ÿ˜?KšœŸœ+˜J—Kš
œ˜——š
œ˜KšœŸœ@˜bšŸœ'Ÿ˜-KšœŸœ˜1——KšŸœŸœ0˜=——K˜KšœŸœ	˜,KšœŸœ
Ÿœ.˜:šœŸœŸ˜)KšŸœ
Ÿœ˜KšŸœ
Ÿœ˜—Kš
œ˜Kš
œ˜Kš
œ7˜7——K˜š
œ˜Kš
œ]˜]—K˜—š	 œŸœ
ŸœŸœ%
˜MK˜—š œŸœ
ŸœŸœ
˜(Jš
œ(™(š œ˜$Jš
ŸœŸœŸœŸœŸœ™EJšœŸœŸœ˜.JšœŸœŸœ˜4Kš
Ÿœ
ŸœŸœ
Ÿœ
Ÿœ˜'K˜—Jš
œ-˜-Kšœ
˜
K˜—š
 œŸœ
ŸœŸœŸœ
˜PKšŸœ
Ÿœ˜Kš
œE™EKšœ+Ÿœ˜Nš
œ)˜)KšœŸœ1˜:Kš
œ˜—Kš
œ˜š
œ˜Kš
œ]˜]—K˜—š 
œŸœ
ŸœŸœŸœ
Ÿœ(˜fš œ˜"KšœŸœ1˜:K–

"Cedar" styleš
œ!˜!—š œ˜ KšœŸœ0˜9Kš
œ˜—Kš
œ,˜,Kš
œ+˜+——
head™š 	œŸœŸœC˜]KšŸœŸœŸœ˜,Kš
œ™šŸœŸœ˜@š œ˜"šŸœŸœ
Ÿ˜š
œ˜šœŸœŸœŸ˜&Kš
œ"˜"Kš
œ ˜ Kš
œ˜Kš
œ˜KšŸœŸœ
˜—šŸœŸœ˜-KšŸœŸœ˜&——KšœŸœ
˜KšŸœŸœ0˜>——KšœŸ
˜Kšœ6Ÿœ	˜DšŸœŸœŸ˜KšœŸœ˜3KšŸœŸœ
Ÿœ
˜)š
œ8˜8KšŸœ#˜(—šŸœ#Ÿ˜)š
œ,˜,K™|——KšŸœ
˜—š
Ÿ˜šŸœŸœ
Ÿœ4˜EšŸœŸœ
Ÿœ
˜KšœŸœŸœ@˜|šœŸœ˜<KšŸœ˜!KšŸœ˜!—Kš
œ*˜*šŸœŸœ˜(Kš
œI˜IKšœŸœ˜*šœ6Ÿœ˜HKš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜—KšœŸœ˜#Kš
œh˜hKš
œh˜hKš
œ%˜%—KšŸœœ
˜————K˜—–

"Cedar" styleš œŸœ.˜C–

"Cedar" stylešŸœ	ŸœŸœ˜$šŸœŸœ
Ÿœ4ŸœŸœ
Ÿœ
˜UKšŸœŸœ
Ÿœ
˜%šŸœŸœ
Ÿœ5ŸœŸœ
Ÿœ
˜XKšŸœŸœ
Ÿœ
ŸœŸœ
Ÿœ˜=———K–

"Cedar" style˜—–

"Cedar" styleš œŸœŸœ4˜VK–

"Cedar" stylešŸœ	ŸœŸœ˜$KšŸœ
ŸœG™SKšœŸœ˜3šŸœŸœ
Ÿœ4ŸœŸœ
Ÿœ
˜UKšŸœŸœ
Ÿœ
˜$šŸœŸœ
Ÿœ5ŸœŸœ
Ÿœ
˜XšœŸœ˜%Kšœ
Ÿœ;˜B—KšŸœ
Ÿœ%Ÿ˜1KšŸœŸœ
Ÿœ
ŸœŸœ
Ÿœ
˜=——K˜—–

"Cedar" styleš 	œŸœ"Ÿœ	˜?K–

"Cedar" stylešŸœ˜K–

"Cedar" stylešœŸœ
˜K–

"Cedar" stylešœŸœ
˜-K–

"Cedar" stylešœ
Ÿœ!˜.K–

"Cedar" stylešœ
Ÿœ!˜.K–

"Cedar" stylešœ
Ÿœ˜K–

"Cedar" styleš	œŸœŸœŸœ
Ÿœ
˜AK–

"Cedar" styleš	œŸœŸœŸœ
Ÿœ
˜BK–

"Cedar" styleš
œ+™+–

"Cedar" stylešŸœ-Ÿœ
˜4–

"Cedar" stylešŸœŸœ
Ÿ˜–

"Cedar" stylešŸœŸœ
Ÿœ8ŸœŸœ
Ÿ˜\Kš
œ"˜"šŸœŸ˜Kš
œŸœŸœŸœŸœŸœŸœ˜‚
—KšŸœ
˜———K–

"Cedar" stylešœ
Ÿœ:˜GK˜—–

"Cedar" styleš œŸ˜–

"Cedar" stylešœŸœ
ŸœŸœ&˜WK–

"Cedar" stylešŸœ˜&—–

"Cedar" stylešœ,Ÿœ˜EK–

"Cedar" styleš
œ-˜-—K–

"Cedar" styleš
œ˜–

"Cedar" styleš
œ˜K–

"Cedar" styleš
œK˜K—K˜—š
 œŸœŸœ
ŸœŸœ˜\Jš	œŸœŸœŸœ
Ÿœ,˜MJš	œŸœŸœŸœ
Ÿœ,˜MšŸœ'˜<K˜——–

"Cedar" styleš œŸœŸœ
Ÿœ˜RK–

"Cedar" stylešŸœŸœŸœ˜ Kš	œ	Ÿœ
Ÿœ
Ÿœ
Ÿœ-˜DKš	œ	Ÿœ
Ÿœ
Ÿœ
Ÿœ-˜Dš	ŸœŸœ
ŸœŸœ
Ÿ˜'š
ŸœŸœ
ŸœŸœ
Ÿœ˜*Kš
œ>˜>—šŸœ
ŸœŸœ
ŸœŸœ
Ÿœ˜.Kš
œ>˜>—šŸœ
Ÿœ3Ÿœ˜@Kš
œ>˜>—šŸœ˜Kš
œ>˜>—KšŸœ
˜—K–

"Cedar" styleš
œ˜K˜K˜—–

"Cedar" styleš œŸœŸœ
Ÿœ˜KK–

"Cedar" stylešŸœŸœ˜Kš œŸœŸœŸœ˜FKšœŸœ1˜YKšŸœŸœŸœ !˜[K˜—–

"Cedar" styleš 
œŸ˜–

"Cedar" stylešœŸœA˜LK–

"Cedar" stylešŸœŸœ˜)—–

"Cedar" styleš œ˜ KšœŸœŸœ˜7KšœŸœ˜(KšœŸœ˜(Kšœ
Ÿœ!˜.Kšœ
Ÿœ!˜.K–

"Cedar" stylešœŸœŸœ˜4K–

"Cedar" stylešœŸœŸœ˜3K–

"Cedar" styleš
ŸœŸœŸœŸœ	Ÿœ˜E—KšœŸœŸœ*˜VKš
œI˜IKšœŸœ˜%šŸœ'Ÿœ
˜.KšŸœ4˜6—K˜—š œŸœŸœŸœ˜IšœŸœŸ˜Kš
œ
˜
Kš
œ
˜
Kš
œ˜Kš
œ˜KšŸœŸœ-˜:—K˜—š 
œŸœŸœ
ŸœŸœŸœ˜fKš
œ>™>Kš
 œŸœŸœŸœŸœ˜XKšœŸœ#˜0KšŸœŸœŸœ˜3KšŸœŸœŸœ˜3KšŸœŸœ
Ÿœ4˜DK˜—š œŸœ!Ÿœ	Ÿœ˜XKš
œ"™"KšœŸœ
˜
šŸœŸœ
Ÿ˜š
œ˜šŸœ˜KšŸœ'˜+KšŸœ(˜,——š
œ˜Kš
œR˜RšœŸœ˜%Kšœ
Ÿœ3˜:—Kš
œ-˜-—KšŸœŸœ/˜<—KšŸœ
˜K˜—š 	œŸœŸœ˜DKš
œ™K˜KšœŸœ
˜
šŸœŸœ
Ÿ˜Kš
œ@˜@š
œ˜Kš
œR˜RKšœŸœ˜(šœŸœ˜%Kšœ
Ÿœ3˜:—šŸœ˜KšŸœ˜KšŸœ˜!——KšŸœŸœ/˜?—KšŸœ
˜K˜—š œŸœ
ŸœŸœŸœŸœ	˜LšŸœŸœ
Ÿ˜Kš
œ˜Kš
œ˜KšŸœ˜	—K˜—š œŸœŸœ&Ÿœ˜OKšŸœ	ŸœŸœ2˜WKš	œŸœŸœŸœ	Ÿœ	˜BKšŸœ	ŸœŸœ	Ÿœ˜4K˜—š 
œŸœŸœ
ŸœŸœŸœ˜LšŸœŸœ
Ÿ˜KšŸœŸœ
Ÿœ
Ÿœ˜'Kš
œ˜KšŸœ
˜—KšŸœ
Ÿœ˜K˜—–

"Cedar" styleš 
œŸœŸœŸœ˜QKš
œ"˜"Jš
œ*˜*Jšœ	Ÿœ.˜9Jš
œQ˜QJ˜—š 	œŸœŸœŸœ˜MKšœŸœ˜Kš
œ/˜/Kš
œ/˜/KšœŸœŸœ
Ÿœ˜-KšœŸœŸœ
Ÿœ˜-KšœŸœ5˜?šœŸœ˜+KšŸœŸœ˜,šŸœ
Ÿœ˜KšŸœŸœ#˜,KšŸœŸœŸœ˜0——Kš
œ/˜/K˜—J–

"Cedar" stylešŸœ
˜——…—D‚a@