DIRECTORY 
CD, IO, Real, Rope, RTBasic,  RTSets, SC, SCChanUtil, SCInstUtil, SCNetUtil,  SCPrivate, SCRowUtil, SCPlaceUtil, SCNewWidth, SCExprRoutePinsUtil, SCExprGlobalRoute, SCUtil, TerminalIO;

SCExprGlobalRouteImpl: CEDAR PROGRAM
IMPORTS IO, Real, RTBasic, RTSets, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCNewWidth, SCExprRoutePinsUtil, SCPlaceUtil, SCRowUtil, SCUtil, TerminalIO
EXPORTS SCExprGlobalRoute
SHARES SC = { 

hvRatio: NAT _ 500;
debug: BOOLEAN _ TRUE;
Edge: TYPE ~ REF EdgeRec;
EdgeRec: TYPE ~ RECORD[
pin1, pin2: SCExprRoutePinsUtil.PinInChan,
cutEdge, buildInEdge: BOOLEAN,
weight: SC.Number
];
EdgeList: TYPE = LIST OF Edge;
WeightFun: TYPE = PROC[handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number]; 
EdgeTest: TYPE =  PROC [edge: Edge] RETURNS [delete: BOOLEAN _ FALSE]; 

GlobalRoute: PUBLIC PROCEDURE[handle: SC.Handle, nets: SCPrivate.NetList] = {
layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows _ layoutData.lgRows;
TerminalIO.PutRope["Begin global route\n Stage 1\n"];
SCNewWidth.AllChanWidths[handle, areaFom];
SCInstUtil.AsgnChanPos[handle];
[lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle];
hvRatio _ lgRows.maxRowWidth / 8;
AddFTsInNets[handle, nets];
TerminalIO.PutRope["Stage 2\n"];
DecideEdgesInNets[handle, nets];
SCInstUtil.AllOffsets[handle];
[lgRows.maxRowWidth, lgRows.numMaxRows] _ SCRowUtil.FindMaxRow[handle];
SCNewWidth.ComputeAllChanDW[handle, areaFom];
SCInstUtil.AsgnChanPos[handle];
TerminalIO.PutRope["End global route\n"];
[] _ SCUtil.WriteResults["End global route\n estimated size:", handle, 0]};
UndoGlobalRoute: PUBLIC PROCEDURE[handle: SC.Handle, nets: SCPrivate.NetList] = {};

GlobalRouteAllNets: PUBLIC PROCEDURE[handle: SC.Handle] = {

EachNet: SCNetUtil.EachNetProc = { nets _ CONS[net, nets]};

nets: SCPrivate.NetList _ NIL;
[] _ SCNetUtil.EnumerateNets[handle, EachNet];
GlobalRoute[handle, nets]};

AddFTsInNets: PROC [handle: SC.Handle, nets: SCPrivate.NetList]   ~ {

edgeList: EdgeList _ NIL;

AddExitsInNets[handle, nets];
EnterPinNodes[handle];
edgeList _ BuildGraphs1[handle, nets];
MarkBuildInEdges[handle, nets];
GetAllRowWeights[handle];
edgeList _ ComputeWeights[handle, nets, edgeList, Cost1, EdgeTest1];
GenerateTrees1[handle, nets, edgeList];
RemoveGraph1[handle, nets];
RemoveUnusedFTs[handle, nets];
};

DecideEdgesInNets: PROC [handle: SC.Handle, nets: SCPrivate.NetList]  ~ {

edgeList: EdgeList _ NIL;

edgeList _ BuildGraphs2[handle, nets];
GetNetsSpan[handle, nets];
GetAllChanDensity[handle];
MarkAllCutEdges[handle, nets];
edgeList _ ComputeWeights[handle, nets, edgeList, Cost2, EdgeTest2];
GenerateTrees2[handle, nets, edgeList];
};

AddExitsInNets: PROC [handle: SC.Handle, nets: SCPrivate.NetList]  ~ {

EachNet: SCNetUtil.EachNetProc = {
onSide: SCPrivate.SideSet;
onRow: SCPrivate.RowSet;
leftOnChan, rightOnChan: SCPrivate.ChanSet _ RTSets.RTLgSetEmpty;
instList: SCPrivate.InstanceList _ SCNetUtil.InstsOnNets[LIST[net]];
numInstances: SCPrivate.ZMaxInstanceSr _ SCInstUtil.NumInstsOnList[instList];

[onSide, onRow] _ SCRowUtil.RowsForInsts[instList];
IF onSide[LOOPHOLE[SC.Side[left], INTEGER]] THEN
[] _ DetermineExits[handle, left, net];
IF onSide[LOOPHOLE[SC.Side[right], INTEGER]] THEN
[] _ DetermineExits[handle, right, net];
};

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows _ layoutData.lgRows;
rowChans: SCPrivate.RowChans _ layoutData.rowChans;
FOR netLst: SCPrivate.NetList _ nets, netLst.rest WHILE netLst # NIL DO 
[] _ EachNet[netLst.first];
ENDLOOP;
};

DetermineExits: PROCEDURE[handle: SC.Handle, side: SCPrivate.LRSide, net: SCPrivate.Net]
RETURNS [onChan: SCPrivate.ChanSet _ RTSets.RTLgSetEmpty] = {

ChanExitProc: SCChanUtil.EachRowChanProc = {
IF onChan[(chan) - 1] THEN AddExit[handle, rowChan, side, net]};

EachPinProc: SCNetUtil.EachPinProc = {
instance: SCPrivate.Instance _ netPin.instance;
pin: SCPrivate.ObjectPin _ netPin.pin;

IF instance.whichClass = io THEN {
sideOn: SC.Side _ SCInstUtil.PosOf[instance, pin].sideOn;
yPos: SC.Number _ SCInstUtil.InstPosOf[handle, instance, pin].q;
IF instance.curSide = side AND instance.curPos > 0 AND sideOn = chanSide THEN {
ChanProc: SCChanUtil.EachRowChanProc = {
chanPos: SC.Number _ rowChan.chanPos + rowChan.chanWidth/2;
dist: SC.Number _ ABS[chanPos - holdBpPos];
useThisChan: BOOLEAN _ (1 < chan AND chan < rowChans.count) OR (chan = 1 AND rowChans.count = 2);

IF useThisChan AND dist < minDist THEN {minDistChan _ chan; minDist _ dist};
IF useThisChan AND touchesChan[(chan)-1] THEN {
IF chanPos > maxChanPos THEN {maxChan _ chan; maxChanPos _ chanPos};
IF chanPos < minChanPos THEN {minChan _ chan; minChanPos _ chanPos}}};

minDist, minChanPos: SC.Number _ LAST[INT];
maxChanPos: SC.Number _ -LAST[INT];
minDistChan, maxChan, minChan: SCPrivate.ZMaxChanSr _ 0;
holdBpPos: SC.Number _ SCInstUtil.BpPos[handle, instance] + yPos;

[] _ SCChanUtil.EnumerateRowChans[handle, ChanProc];

SELECT TRUE FROM
holdBpPos > maxChanPos AND maxChan > 0 =>
onChan _ RTSets.RTLgSetUnion[onChan, RTSets.RTLgSetGenerateElement[(maxChan)-1]];

holdBpPos < minChanPos AND minChan > 0 =>
onChan _ RTSets.RTLgSetUnion[onChan, RTSets.RTLgSetGenerateElement[(minChan)-1]];

minDistChan > 0 =>
onChan _ RTSets.RTLgSetUnion[onChan, RTSets.RTLgSetGenerateElement[(minDistChan)-1]];
ENDCASE => SC.Error[programmingError, "Not suppose to happen."]}}};

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans _ layoutData.rowChans;
chanSide: RTBasic.Side _ RTBasic.OtherSide[side];
instList: SCPrivate.InstanceList _ SCNetUtil.InstsOnNets[LIST[net]];
touchesChan: SCPrivate.ChanSet _ SCInstUtil.ChansForInsts[handle, instList];

net.chanExits[side] _ RTSets.RTLgSetEmpty;

[] _ SCNetUtil.EnumeratePinsOnNet[net, EachPinProc];
[] _ SCChanUtil.EnumerateRowChans[handle, ChanExitProc]};


AddExit: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, side: SC.Side, net: SCPrivate.Net] = {

IF rowChan.chanNum = 0 THEN SC.Error[programmingError, NIL]
ELSE {
index: NAT _ rowChan.numExits[side] _ rowChan.numExits[side] + 1;
net.chanExits[side] _
RTSets.RTLgSetUnion[net.chanExits[side], RTSets.RTLgSetGenerateElement[(rowChan.chanNum)-1]];
rowChan.exits[side][index] _ NEW[SCPrivate.ExitRec _ [net: net, pos: 0, pinInChan: NIL, layer: handle.rules.rowRules.trunkLayer]]}};


EnterPinNodes: PROC [handle: SC.Handle]  ~ {

EachChan: SCChanUtil.EachRowChanProc  = {
layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans _ layoutData.rowChans;

SCExprRoutePinsUtil.InitGetChanPins[handle, rowChan];
IF rowChan.chanNum = 1 THEN {
SCNewWidth.EnterSideData[rowChan, handle, bottom, top, bottom];
SCNewWidth.EnterRowData[rowChan, handle, 1, bottom]}
ELSE IF rowChan.chanNum = rowChans.count THEN {
SCNewWidth.EnterRowData[rowChan, handle, lgRows.count, top];
SCNewWidth.EnterSideData[rowChan, handle, top, bottom, top]}
ELSE {
SCNewWidth.EnterRowData[rowChan, handle, rowChan.chanNum-1, top];
SCNewWidth.EnterRowData[rowChan, handle, rowChan.chanNum, bottom]};
SCNewWidth.EnterExitData[handle, rowChan, left];
SCNewWidth.EnterExitData[handle, rowChan, right];
};

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows _ layoutData.lgRows;

IF lgRows.rows[1].lgsOnRow[1].pinNets[1].pinInChan = NIL THEN  --graph nodes have not been created.
[] _ SCChanUtil.EnumerateRowChans[handle, EachChan]
};

BuildGraphs1: PROC [handle: SC.Handle, nets: SCPrivate.NetList] RETURNS [edgeList: EdgeList _ NIL] ~ {
--build complete graph for nets.

EachNet: PROC [net: SCPrivate.Net]  ~ {

pinList: SCExprRoutePinsUtil.PinList _ NARROW[net.pinList];
compNo: NAT _ 0;

FOR pinList1: SCExprRoutePinsUtil.PinList _ pinList, pinList1.rest WHILE pinList1 # NIL DO
pin1: SCExprRoutePinsUtil.PinInChan _ pinList1.first;
compNo _ compNo + 1;
pin1.component _ compNo;
FOR pinList2: SCExprRoutePinsUtil.PinList _ pinList1.rest, pinList2.rest WHILE pinList2 # NIL DO
pin2: SCExprRoutePinsUtil.PinInChan _ pinList2.first;
edge: Edge _ EnterAEdge[pin1, pin2, FALSE, FALSE];
edgeList _ CONS[edge, edgeList];
ENDLOOP;
ENDLOOP;
};

FOR netList: SCPrivate.NetList _ nets, netList.rest WHILE netList # NIL DO
net: SCPrivate.Net _ netList.first;
EachNet[net];
ENDLOOP;
};

EnterAEdge: PROC [pin1, pin2: SCExprRoutePinsUtil.PinInChan, cutEdge, buildInEdge: BOOLEAN] RETURNS [edge: Edge] ~ {

adjList1: EdgeList _ NARROW[pin1.adjList];
adjList2: EdgeList _ NARROW[pin2.adjList];
netEdges: EdgeList _ NARROW[pin1.net.edgeList];
pinA, pinB: SCExprRoutePinsUtil.PinInChan _ NIL;
IF pin1.net # pin2.net THEN SC.Error[programmingError,  "Invalid graph edge"];
IF pin1.min <= pin2.min THEN {
pinA _ pin1; 
pinB _ pin2}
ELSE { 
pinA _ pin2;
pinB _ pin1};
edge _ NEW[EdgeRec _ [
pin1: pinA,
pin2: pinB,
cutEdge: cutEdge,
buildInEdge: buildInEdge,
weight: 0]];
adjList1 _ CONS[edge, adjList1];
adjList2 _ CONS[edge, adjList2];
pin1.adjList _ adjList1;
pin2.adjList _ adjList2;
netEdges _ CONS[edge, netEdges];
pin1.net.edgeList _ netEdges
};

GetAllRowWeights: PROC [handle: SC.Handle]  ~ {
--compute weight for each row.

EachRow: SCRowUtil.EachRowProc  = {
IF lgRow.size.p = maxRowWidth THEN lgRow.weight _ 4
ELSE  lgRow.weight _ 1};

maxRowWidth, maxRowNo : SC.Number _ 0;
[maxRowWidth, maxRowNo] _ SCRowUtil.FindMaxRow[handle];
[] _ SCRowUtil.EnumerateRows[handle, EachRow]};

ComputeWeights: PROC [handle: SC.Handle, nets: SCPrivate.NetList, edgeList: EdgeList, Cost: WeightFun, DeleteTest: EdgeTest]  RETURNS[ EdgeList ]  ~ {

edges: EdgeList _ NIL;
WHILE edgeList # NIL AND DeleteTest[edgeList.first] DO
edgeList _ edgeList.rest;
ENDLOOP;
IF edgeList # NIL THEN 
edgeList.first.weight _ Cost[handle, edgeList.first];
edges _ edgeList;
WHILE edges # NIL DO
IF edges.rest # NIL THEN  
IF DeleteTest[edges.rest.first]  THEN 
edges.rest _ edges.rest.rest
ELSE { edges.rest.first.weight _ Cost[handle, edges.rest.first];
         edges _ edges.rest}
ELSE EXIT;
ENDLOOP;
RETURN[edgeList];
};

RemoveNetEdge: PROC[net: SCPrivate.Net, edge: Edge] = {
netEdges: EdgeList _ NARROW[net.edgeList];
net.edgeList _ DRemove[edge,  netEdges]};

Cost1: WeightFun = {

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows _ layoutData.lgRows;
horiWeight, vertWeight: SC.Number _ 0;
pin1: SCExprRoutePinsUtil.PinInChan _ edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan _ edge.pin2;
bound1, bound2: NAT;

horiWeight _ LengthE[edge];
IF pin1.chanNum <= pin2.chanNum THEN {
bound1 _ pin1.chanNum;
bound2 _ pin2.chanNum}
ELSE {
bound1 _ pin2.chanNum;
bound2 _ pin1.chanNum};
FOR index: NAT _ bound1, index + 1 WHILE index < bound2 DO
vertWeight _ vertWeight + lgRows.rows[index].weight;
ENDLOOP;
cost _ horiWeight + hvRatio * vertWeight;
};

LengthE: PROC [edge: Edge] RETURNS [length: SC.Number] ~ {
length _ ABS[edge.pin1.min - edge.pin2.min]
};


Cost2: WeightFun = {
pin, left, right: SCExprRoutePinsUtil.PinInChan _ NIL;
pin1: SCExprRoutePinsUtil.PinInChan _ edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan _ edge.pin2;

IF edge.buildInEdge THEN cost _ 0
ELSE IF pin1.chanNum # pin2.chanNum THEN 
SC.Error[programmingError,  "Invalid Graph Edge"]
ELSE IF pin1.min = pin2.min  THEN 
cost _ 0
ELSE {
layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans _ layoutData.rowChans;
left _ pin1;
right _ pin2;
cost _ 0;
pin _ left;
DO
cost _ MAX[cost, pin.localDensity];
IF pin = right THEN EXIT
ELSE pin _ pin.nextPinInChan;
ENDLOOP;
cost _ Real.InlineRound[100 * Real.FDiv[cost, rowChans.chans[pin1.chanNum].chanDensity]]}
};

EdgeTest1: EdgeTest = {
pin1: SCExprRoutePinsUtil.PinInChan _ edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan _ edge.pin2;

IF (pin1.component = pin2.component) THEN 
delete _ TRUE
ELSE delete _ FALSE;
};

EdgeTest2: EdgeTest = {
IF edge.cutEdge OR edge.buildInEdge THEN 
delete _ TRUE
ELSE delete _ FALSE
};

BuildGraphs2: PROC [handle: SC.Handle, nets: SCPrivate.NetList] RETURNS [edgeList: EdgeList _ NIL] ~ {

SortAllChanPins[handle];
edgeList _ EnterNetEdges[handle, nets];
edgeList _ Nconc[edgeList, EnterBuildInEdges[handle, nets]];
};

SortAllChanPins: PROC [handle: SC.Handle]  ~ {

EachChan: SCChanUtil.EachRowChanProc  = {
SCExprRoutePinsUtil.CreateNetDat[handle, rowChan]};

[] _ SCChanUtil.EnumerateRowChans[handle, EachChan]};

EnterNetEdges: PROC [handle: SC.Handle, nets: SCPrivate.NetList] RETURNS [edgeList: EdgeList _ NIL] ~ {

EachNet: PROC [net: SCPrivate.Net]  ~ {
pinList: SCExprRoutePinsUtil.PinList _ NARROW[net.pinList];
FOR pins: SCExprRoutePinsUtil.PinList _ pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan _ pins.first;
edge: Edge _ NIL;
IF pin.nextPinInNet # NIL AND InUseChan[handle, pin.chanNum] THEN {
edge _ EnterAEdge[pin, pin.nextPinInNet, FALSE, FALSE];
edgeList _ CONS[edge, edgeList]};
ENDLOOP};

FOR netList: SCPrivate.NetList _ nets, netList.rest WHILE netList # NIL DO
EachNet[netList.first];
ENDLOOP};

InUseChan: PROC [handle: SC.Handle, chan: SCPrivate.MaxChanSr] RETURNS [yes: BOOLEAN _ FALSE] ~ {
rowChans: SCPrivate.RowChans _ NARROW[handle.layoutData, SCPrivate.LayoutData].rowChans;
IF chan = 1  THEN 
IF rowChans.count > 2 THEN yes _ FALSE
ELSE yes _ TRUE
ELSE 
IF chan = rowChans.count THEN yes _ FALSE
ELSE yes _ TRUE
};

EnterBuildInEdges: PROC [handle: SC.Handle, nets: SCPrivate.NetList] RETURNS [edgeList: EdgeList _ NIL] ~ {

EachRow: SCRowUtil.EachRowProc  = {

InstProc: SCRowUtil.EachInstProc = {
FOR pinNum1: NAT IN [0 .. instance.pinNets.size) DO
netPin1: SCPrivate.PinNet _ instance.pinNets.n[pinNum1];
pin1: SCExprRoutePinsUtil.PinInChan _ NARROW[netPin1.pinInChan];
FOR pinNum2: NAT IN [pinNum1 + 1 .. instance.pinNets.size)  DO
netPin2: SCPrivate.PinNet _ instance.pinNets.n[pinNum2];
pin2: SCExprRoutePinsUtil.PinInChan _ NARROW[netPin2.pinInChan];
IF netPin1.net = netPin2.net AND pin1.min = pin2.min THEN {
edge: Edge _ EnterAEdge[pin1, pin2, FALSE, TRUE];
edgeList _ CONS[edge, edgeList]};
ENDLOOP;
ENDLOOP}; -- end of instProc

[ ] _ SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc]};

[ ] _ SCRowUtil.EnumerateRows[handle, EachRow]};


MarkBuildInEdges: PROC [handle: SC.Handle, nets: SCPrivate.NetList]  ~ {

EachRow: SCRowUtil.EachRowProc  = {

[ ] _ SCRowUtil.EnumerateAllInstsOnRow[handle, row, MarkBuildInEdgeOnInst]};

[ ] _ SCRowUtil.EnumerateRows[handle, EachRow]};


MarkBuildInEdgeOnInst: SCRowUtil.EachInstProc = {
FOR pinNum1: NAT IN [0 .. instance.pinNets.size) DO
netPin1: SCPrivate.PinNet _ instance.pinNets.n[pinNum1];
pin1: SCExprRoutePinsUtil.PinInChan _ NARROW[netPin1.pinInChan];
FOR pinNum2: NAT IN [pinNum1 + 1 .. instance.pinNets.size)  DO
netPin2: SCPrivate.PinNet _ instance.pinNets.n[pinNum2];
pin2: SCExprRoutePinsUtil.PinInChan _ NARROW[netPin2.pinInChan];
IF netPin1.net = netPin2.net THEN {
compNo: NAT _ MAX[pin1.component, pin2.component];  
pin1.component _ compNo;
pin2.component _ compNo};
ENDLOOP;
ENDLOOP};

GetNetsSpan: PROC [handle: SC.Handle, nets: SCPrivate.NetList]  ~ {
--  to decide pin connections, we folow the rule : left + right -> interior
EachNet: PROC [net: SCPrivate.Net]  ~ {
pinList: SCExprRoutePinsUtil.PinList _ NARROW[net.pinList];
edgeList: EdgeList _ NARROW[net.edgeList];
FOR pins: SCExprRoutePinsUtil.PinList _ pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan _ pins.first;
pin.pinConn _ unconnected;
ENDLOOP;
FOR edges: EdgeList _ edgeList, edges.rest WHILE edges # NIL DO
pin1: SCExprRoutePinsUtil.PinInChan _ edges.first.pin1;
pin2: SCExprRoutePinsUtil.PinInChan _ edges.first.pin2;
IF pin1.chanNum = pin2.chanNum  AND ~ edges.first.buildInEdge THEN {
IF pin1.pinConn = unconnected THEN pin1.pinConn _ left
ELSE IF pin1.pinConn = right THEN pin1.pinConn _ interior
ELSE SC.Error[programmingError,  "overlaid graph edge"];
IF pin2.pinConn = unconnected THEN pin2.pinConn _ right
ELSE IF pin2.pinConn = left THEN pin2.pinConn _ interior
ELSE SC.Error[programmingError,  "overlaid graph edge"]};
ENDLOOP};

FOR netList: SCPrivate.NetList _ nets, netList.rest WHILE netList # NIL DO
EachNet[netList.first];
ENDLOOP;
};

GetAllChanDensity: PROC [handle: SC.Handle]  ~ {

EachChan: SCChanUtil.EachRowChanProc  = {
[rowChan.chanDensity, rowChan.wireLength] _ SCNewWidth.ComputeDW[rowChan];
IF debug THEN {}};

[] _ SCChanUtil.EnumerateRowChans[handle, EachChan]};


RemoveGraph1: PROC [handle: SC.Handle, nets: SCPrivate.NetList]   ~ {
-- we only remove edges! nodes are shared by stage 2.

EachNet: PROC [net: SCPrivate.Net]  ~ {
pinList: SCExprRoutePinsUtil.PinList _ NARROW[net.pinList];
FOR pins: SCExprRoutePinsUtil.PinList _ pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan _ pins.first;
pin.pinConn _ unconnected;
pin.adjList _ NIL;
ENDLOOP;
net.edgeList _ NIL};

FOR netList: SCPrivate.NetList _ nets, netList.rest WHILE netList # NIL DO
EachNet[netList.first];
ENDLOOP;
};

RemoveUnusedFTs: PROC [handle: SC.Handle, nets: SCPrivate.NetList]  ~ {
};

GenerateTrees1: PROC [handle: SC.Handle, nets: SCPrivate.NetList, edgeList: EdgeList]  ~ {

WHILE edgeList # NIL DO
edge: Edge _ NIL;
edge _ MinEdge[edgeList];
edgeList _ AddTreeEdge1[handle, edgeList, edge];
GetAllRowWeights[handle];
edgeList _ ComputeWeights[handle, nets, edgeList, Cost1, EdgeTest1];
ENDLOOP;
};

GenerateTrees2: PROC [handle: SC.Handle, nets: SCPrivate.NetList, edgeList: EdgeList]  ~ {
WHILE edgeList # NIL DO
edge: Edge _ NIL;
edge _ MaxEdge[edgeList];
edgeList _ DeleteGraphEdge2[handle, edgeList, edge];
edgeList _ ComputeWeights[handle, nets, edgeList, Cost2, EdgeTest2];
ENDLOOP;
};

MinEdge: PROC [edgeList: EdgeList]  RETURNS [edge: Edge _ NIL] ~ {

minWeight: SC.Number _ LAST[INT];
FOR edges: EdgeList _ edgeList, edges.rest WHILE edges # NIL DO
IF edges.first.weight < minWeight THEN {
minWeight _ edges.first.weight;
edge _ edges.first};
ENDLOOP;
};

MaxEdge: PROC [edgeList: EdgeList] RETURNS [edge: Edge _ NIL] ~ {
-- Maybe we should break tie by wire length
maxWeight: SC.Number _ FIRST[INT];
FOR edges: EdgeList _ edgeList, edges.rest WHILE edges # NIL DO
IF edges.first.weight > maxWeight THEN {
maxWeight _ edges.first.weight;
edge _ edges.first}
ELSE IF edges.first.weight = maxWeight THEN 
{IF LengthE[edges.first] > LengthE[edge] THEN edge _ edges.first};
ENDLOOP;
};

AddTreeEdge1: PROC [handle: SC.Handle, edgeList: EdgeList, edge: Edge]  RETURNS[newEdgeList: EdgeList] ~ {

pinA, pinB:  SCExprRoutePinsUtil.PinInChan;
compNo: NAT;
pin1: SCExprRoutePinsUtil.PinInChan _ edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan _ edge.pin2;
pinList: SCExprRoutePinsUtil.PinList _ NARROW[pin1.net.pinList];
newEdgeList _ edgeList;
IF edge.pin1.chanNum <= edge.pin2.chanNum THEN {
pinA _ edge.pin1;
pinB _ edge.pin2}
ELSE {
pinA _ edge.pin2;
pinB _ edge.pin1};
IF pinA.net # pinB.net THEN SC.Error[programmingError,  "Invalid graph edge"];
FOR row: SCPrivate.MaxRowSr _ pinA.chanNum, row + 1 WHILE row < pinB.chanNum DO
loc: SC.Number _  pinA.min + (row - pinA.chanNum + 1) * (pinB.min - pinA.min) / (pinB.chanNum - pinA.chanNum + 1);
newEdges: EdgeList _ AddFT[handle, row, loc, pinA.net];
newEdgeList _  Nconc[newEdgeList, newEdges];
ENDLOOP;
compNo _ MAX[pinA.component, pinB.component];  ---Union operation
pinList _ NARROW[pin1.net.pinList];
FOR pins: SCExprRoutePinsUtil.PinList _ pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan _ pins.first;
IF pin.component = pinA.component OR pin.component = pinB.component OR pin.component = 0 THEN 
pin.component _ compNo;
ENDLOOP;
IF debug THEN {}
};

AddFT: PROC [handle: SC.Handle, row: SCPrivate.MaxRowSr, loc: SC.Number, net: SCPrivate.Net] RETURNS[newEdges: EdgeList _ NIL]  ~ {

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows _ layoutData.lgRows;
lgRow: SCPrivate.LgRow _ lgRows.rows[row];
savPos: SCPrivate.MaxPosSr _ 1;
nodeList: SCExprRoutePinsUtil.PinList _ NIL;
ftInst: SCPrivate.Instance_ NewFt[handle, net, lgRow];

savPos _ GetFTPos[handle, lgRow, loc];
SCPlaceUtil.PutLgPos[handle, ftInst, lgRow.rowNum, savPos, SCInstUtil.defltLgOrien, TRUE];
newEdges _ AddPinNodes[handle, row, ftInst];
SCInstUtil.AsgnChanPos[handle];
UpdateNodeLoc[handle]
};

GetFTPos: PROC [handle: SC.Handle, lgRow: SCPrivate.LgRow, loc: SC.Number] RETURNS [pos: SCPrivate.MaxPosSr _ 1] ~ {

WHILE pos <= lgRow.nLgsOnRow  AND lgRow.rowOrg.p + lgRow.lgsOnRow[pos].offset < loc DO
pos _ pos + 1;
ENDLOOP;
};

NewFt: PUBLIC PROCEDURE[handle: SC.Handle, net: SCPrivate.Net, lgRow: SCPrivate.LgRow] RETURNS [ftInst: SCPrivate.Instance] = {
parms: SCPrivate.Parms _ NARROW[handle.parms];
name: Rope.ROPE _ IO.PutFR["%g-%g", IO.rope[net.name], IO.int[lgRow.rowNum]];
ftInst _ SCInstUtil.DefineInstance[handle, name, parms.ftObject, NIL];
ftInst.ftNet _ net;
SCNetUtil.AddConnection[handle, net, ftInst, parms.ftObject.pins.p[0], 0, ftPin];
SCNetUtil.AddConnection[handle, net, ftInst, parms.ftObject.pins.p[1], 1, ftPin]};
AddPinNodes: PROC [handle: SC.Handle,  row: SCPrivate.MaxRowSr, ftInst: SCPrivate.Instance]  RETURNS[newEdges: EdgeList _ NIL] ~ {

PinProc: SCInstUtil.EachPinProc = {
IF netPin.pin # NIL AND netPin.net # NIL THEN { 
pd: SCInstUtil.PinDescription _ SCInstUtil.PosOf[instance, netPin.pin];
chan: NAT _ IF pd.sideOn = bottom THEN row ELSE row + 1;
pinList: SCExprRoutePinsUtil.PinList _ NARROW[netPin.net.pinList];
tail: SCExprRoutePinsUtil.PinInChan;
alwaysUse: BOOLEAN _ netPin.net.externNet AND (chan = 1 AND SCNetUtil.ExitOnSide[handle, netPin.net, bottom]) OR (chan = rowChans.count AND SCNetUtil.ExitOnSide[handle, netPin.net, top]);
rowOffset: SC.Number _ lgRows.horzRowOrg + lgRow.rowOrg.p;
rect: CD.Rect _ SCInstUtil.RotateRect[instance, netPin.pin.rect];
min: SC.Number _ rowOffset + instance.offset + rect.x1;
tail _ SCExprRoutePinsUtil.EnterPin[rowChan: rowChans.chans[chan], min: min, max: min + rect.x2 - rect.x1, depth: 0, layer: netPin.pin.layer, net: netPin.net, side: RTBasic.OtherSide[pd.sideOn], alwaysUse: alwaysUse];
netPin.pinInChan _ tail;
FOR pinList1: SCExprRoutePinsUtil.PinList _ pinList, pinList1.rest WHILE pinList1 # NIL DO
pin1: SCExprRoutePinsUtil.PinInChan _ pinList1.first;
edge: Edge _ EnterAEdge[tail, pin1, FALSE, FALSE];
newEdges _ CONS[edge, newEdges];
ENDLOOP;
pinList _ CONS[tail, pinList]; 
netPin.net.pinList _ pinList}};

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans _ layoutData.rowChans;
lgRows: SCPrivate.LgRows _ NARROW[handle.layoutData, SCPrivate.LayoutData].lgRows;
lgRow: SCPrivate.LgRow _ layoutData.lgRows.rows[row];
[ ] _ SCInstUtil.EnumeratePinsOnInst[ftInst, PinProc];
};

UpdateNodeLoc: PROC [handle: SC.Handle]  ~ {

UpdateNodeLocInRow: SCRowUtil.EachRowProc  ~ {

InstProc: SCRowUtil.EachInstProc = {
FOR pinNum: NAT IN [0 .. instance.pinNets.size) DO
netPin: SCPrivate.PinNet _ instance.pinNets.n[pinNum];
pin: SCExprRoutePinsUtil.PinInChan _ NARROW[netPin.pinInChan];
IF netPin.pin # NIL AND netPin.net # NIL  AND pin # NIL THEN {
rowOffset: SC.Number _ lgRows.horzRowOrg + lgRow.rowOrg.p;
rect: CD.Rect _ SCInstUtil.RotateRect[instance, netPin.pin.rect];
pin.min _  rowOffset + instance.offset + rect.x1;
pin.max _ pin.min + rect.x2 - rect.x1};
ENDLOOP};

ExitProc: SCChanUtil.EachExitProc = {

pos: SC.Number _ IF lrSide = left THEN lgRows.horzRowOrg ELSE lgRows.horzRowOrg + lgRows.maxRowWidth;
pin: SCExprRoutePinsUtil.PinInChan _ NARROW[exit.pinInChan];
IF pin # NIL THEN pin.min _ pin.max _ pos
};

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows _ layoutData.lgRows;
rowChans: SCPrivate.RowChans _ layoutData.rowChans;

[ ] _ SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc];
FOR lrSide: RTBasic.LRSide IN [left..right] DO
[] _ SCChanUtil.EnumerateExits[handle, rowChans.chans[row], lrSide, ExitProc];
[] _ SCChanUtil.EnumerateExits[handle, rowChans.chans[row+1], lrSide, ExitProc];
ENDLOOP;
};

[] _ SCRowUtil.EnumerateRows[handle, UpdateNodeLocInRow]};

DeleteGraphEdge2: PROC [handle: SC.Handle, edgeList: EdgeList, edge: Edge] RETURNS [newEdgeList: EdgeList _ NIL] ~ {

layoutData: SCPrivate.LayoutData _ NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans _ layoutData.rowChans;
pin1: SCExprRoutePinsUtil.PinInChan _ edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan _ edge.pin2;
IF pin1.chanNum # pin2.chanNum THEN SC.Error[programmingError,  "Invalid Net Segment"];
-- re-compute net span
IF pin1.pinConn = left THEN  {
IF pin2.pinConn = right  THEN pin2.pinConn _ unconnected
ELSE IF pin2.pinConn = interior THEN pin2.pinConn _ left
ELSE SC.Error[programmingError,  "Bad net segment"];
pin1.pinConn _ unconnected}
ELSE IF pin1.pinConn = interior THEN {
IF pin2.pinConn = right  THEN pin2.pinConn _ unconnected
ELSE IF pin2.pinConn = interior THEN pin2.pinConn _ left
ELSE SC.Error[programmingError,  "Bad net segment"];
pin1.pinConn _ right}
ELSE SC.Error[programmingError,  "Bad net segment"];
RemoveAEdge[handle,  edge];
newEdgeList _ DRemove[edge, edgeList];
MarkCutEdges[pin1.net];
[rowChans.chans[pin1.chanNum].chanDensity, rowChans.chans[pin1.chanNum].wireLength] _ SCNewWidth.ComputeDW[rowChans.chans[pin1.chanNum]]
};

RemoveAEdge: PROC [handle: SC.Handle, edge: Edge]  ~ {

pin1: SCExprRoutePinsUtil.PinInChan _ edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan _ edge.pin2;
adjList1: EdgeList _ NARROW[pin1.adjList];
adjList2: EdgeList _ NARROW[pin2.adjList];
pin1.adjList _ DRemove[edge, adjList1];
pin2.adjList _ DRemove[edge, adjList2];
RemoveNetEdge[pin1.net, edge]
};

MarkCutEdges: PROC [net: SCPrivate.Net]  ~ {

DFS: PROC [pin, father: SCExprRoutePinsUtil.PinInChan]  ~ {
edgeList: EdgeList _ NARROW[pin.adjList];
labelNo _ labelNo + 1;
pin.dfsLabel _ labelNo;
pin.minLabel _ labelNo;
FOR edges: EdgeList _ edgeList, edges.rest WHILE edges # NIL DO
edge: Edge _ edges.first;
nextPin: SCExprRoutePinsUtil.PinInChan _ IF pin = edge.pin1 THEN edge.pin2 ELSE edge.pin1;
IF  nextPin.dfsLabel = 0  THEN {
DFS[nextPin, pin];
pin.minLabel _ MIN[pin.minLabel, nextPin.minLabel];
IF nextPin.minLabel > pin.dfsLabel THEN edge.cutEdge _ TRUE
ELSE edge.cutEdge _ FALSE
}
ELSE --node has been visited
IF nextPin # father THEN 
pin.minLabel _ MIN[pin.minLabel, nextPin.minLabel];
ENDLOOP};

pinList: SCExprRoutePinsUtil.PinList _ NARROW[net.pinList];
labelNo: NAT _ 0;
FOR pins: SCExprRoutePinsUtil.PinList _ pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan _ pins.first;
pin.dfsLabel _ 0;
ENDLOOP;
[] _ DFS[pinList.first, NIL];
IF debug THEN {}
};

MarkAllCutEdges: PROC [handle: SC.Handle, nets: SCPrivate.NetList] ~ {

FOR netLst: SCPrivate.NetList _ nets, netLst.rest WHILE netLst # NIL DO 
MarkCutEdges[netLst.first];
ENDLOOP
};

Append: PUBLIC PROC [l1: EdgeList, l2: EdgeList _ NIL] RETURNS[val: EdgeList] = {
z: EdgeList _ NIL;
val _ l2;
IF l1 = NIL THEN RETURN[val];
val _ CONS[l1.first, val];
z _ val;
UNTIL (l1 _ l1.rest) = NIL DO
z.rest _ CONS[l1.first, z.rest];
z _ z.rest;
ENDLOOP;
RETURN[val];
}; -- of Append

Remove: PUBLIC PROC [ref: Edge, list: EdgeList] RETURNS[val: EdgeList] =  {
z: EdgeList _ NIL;
val _ NIL;
UNTIL list = NIL DO
IF ~Eq[list.first, ref] THEN
{IF val = NIL THEN {val _ CONS[list.first, NIL]; z _ val}
ELSE {z.rest _ CONS[list.first, z.rest]; z _ z.rest}};
list _ list.rest;
ENDLOOP;	
}; -- of Remove		

Eq: PROC [x, y: Edge] RETURNS[BOOL] = INLINE {RETURN[x = y]};



DRemove:  PROC [ref: Edge, list: EdgeList] RETURNS[EdgeList] =  {
l, l1: EdgeList _ NIL;
l _ list;
UNTIL l = NIL DO
IF Eq[l.first, ref] THEN {
IF l1 = NIL THEN RETURN[l.rest]; -- ref was first object on list
l1.rest _ l.rest;
RETURN[list];
};
l1 _ l;
l _ l.rest;
ENDLOOP;
RETURN [list];
}; -- of Dremove;

Nconc:  PROC [l1, l2: EdgeList] RETURNS[EdgeList] = {
z: EdgeList _ l1;
IF z = NIL THEN RETURN[l2];
UNTIL z.rest = NIL DO
z _ z.rest;
ENDLOOP;
z.rest _ l2;
RETURN[l1];
};

}.

SCExprGlobalRouteImpl.mesa
Copyright Σ 1987 by Xerox Corporation.  All rights reserved.
Jason Cong, August 28, 1987 2:33:06 pm PDT
Jean-Marc Frailong October 11, 1987 4:26:30 pm PDT
Bryan Preas March 30, 1988 1:29:01 pm PST

Implementation of the new global routing algorithms based on M.S.T.  approaches.

Complete global routing for the nets specified in the input net list.

Undo global routing for the nets specified in the input net list.
Do global routing for all nets.
add side exits as required to net lists 
find preferred position for exit to side surface
PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOL _ FALSE];
PROC [netPin: SCPrivate.NetPin] RETURNS [quit: BOOL _ FALSE];
get position of instance on side 
must compute the channel to put the exit on
PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOL _ FALSE];
find distance of port to closest existing channel
determine channel to exit

found channels to exit from, indicated in onChan 
add an exit to a channel 
EachRowChanProc: TYPE = PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOL _ FALSE];

EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL _ FALSE];
remove a net edge from net.edgelist
WeightFun: TYPE = PROC[handle: handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];
WeightFun: TYPE = PROC[handle: handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];

EdgeTest: TYPE =  PROC [edge: Edge] RETURNS [delete: BOOLEAN _ FALSE]; 

EdgeTest: TYPE =  PROC [edge: Edge] RETURNS [delete: BOOLEAN _ FALSE]; 

EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL _ FALSE];
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL _ FALSE];
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL _ FALSE];
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL _ FALSE];
pin.component _ 0;
add ft to row width 
get a component entry for the ft, construct a new entry for instance 

construct and add an entry to net list for this instance 

EachPinProc: TYPE = PROC [instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet] RETURNS [quit: BOOL _ FALSE];
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL _ FALSE];
EachExitProc: TYPE = PROC [exitNum: SCPrivate.MaxExitsSr, lrSide: SCPrivate.LRSide, rowChan: SCPrivate.RowChan, exit: SCPrivate.Exit] RETURNS [quit: BOOL _ FALSE];
Κ}˜š
œ™Icodeš
œ<™<Kš
œ*™*K™2K™)K™—™PK™—šΟk	œ
˜
Kšœ œ
˜Έ
K˜—šΟnœœ
˜$Kšœ
œœp˜•
Kšœ˜Kšœ
œ˜K˜Kšœ	œ˜Kšœœœ
˜Kšœœœ	˜šœ	œœ
˜Kš
œ*˜*Kšœœ
˜Kšœœ˜Kš
œ˜—Kšœ
œœ
œ˜Kšœœœ	œœœ
˜Pšœ
œœœ
œœ˜GK˜——Kšžœœ
	œ	œ%˜Mš
œE™EK™Kšœ#œ˜=Kš
œ-˜-Kš
œ5˜5Kš
œ*˜*Kš
œ˜Kš
œG˜GKš
œ!˜!K˜Kš
œ ˜ K˜ Kš
œ˜Kš
œG˜GKš
œ-˜-Kš
œ˜Kš
œ)˜)Kš
œK˜K—Kšžœœ
	œ	œ'˜Sš
œA™AK˜—Kšžœœ
	œ	œ˜;š
œ™K˜Kšžœ#œ
˜;K˜Kšœœ
˜Kš
œ.˜.Kš
œ˜K˜—šžœœ
œ'˜EK˜Kšœœ
˜K˜Kš
œ˜Kš
œ˜K˜&Kš
œ˜K˜K˜DK˜'K˜K˜K˜K˜—šžœœ
œ&˜IK˜Kšœœ
˜K˜K˜&K˜K˜K˜K˜DK˜'K˜K˜—šžœœ
œ&˜FK˜šžœ˜"Kš
œ˜Kš
œ˜Kš
œA˜AKšœ9œ˜DKš
œM˜MK˜Kš
œ3˜3š	œœ
œ
œ˜0Kš
œ'˜'—š	œœ
œœ˜1Kš
œ(˜(—K˜—K˜Kšœ#œ˜=Kš
œ-˜-Kš
œ3˜3šœ/œ
œ
œ
˜HKš
œ˜Kšœ
˜—K˜K˜—šžœ	œ	œ4˜XKšœ6˜=Kš
œ(™(K˜Kš
œ0™0šžœ ˜,Kšœ9œœœ™ZKšœœ&˜@K˜—šžœ˜&Kšœœœœ™=Kš
œ/˜/Kš
œ&˜&K˜Kš
œ!™!šœœ˜"Kšœœ/˜9Kšœœ8˜@šœœœœ˜OKš
œ+™+šžœ ˜(Kšœ9œœœ™ZKšœ	œ0˜;Kšœœ
œ˜+Kš	œ
œ
œœœ˜aK˜Kšœ
œœ&˜Lšœ
œœ˜/Kšœœ(˜DKšœœ*˜F—K˜—Kšœœ
œ
œ˜+Kšœœœ
œ˜#Kš
œ8˜8Kšœœ4˜AK˜Kš
œ1™1Kš
œ4˜4K˜Kš
œ™šœ
œ
˜šœœ˜)Kš
œQ˜QK˜—šœœ˜)Kš
œQ˜Q—K˜š
œ˜Kš
œU˜U—Kš?œ˜C———K˜—Kšœ#œ˜=Kš
œ3˜3Kš
œ1˜1Kšœ9œ˜DKš
œL˜LK˜Kš
œ*˜*K˜Kš
œ4˜4K™Kš
œ1™1Kš
œ9˜9K˜K˜—š
žœœ
	œ	œ+œ˜oKš
œ™K˜Kšœœ
œœ
˜;šœ˜Kšœœ7˜Aš
œ˜Kš
œ]˜]—Kšœœ3œ.˜„
—K˜K˜—šž
œœ
œ
˜,K˜šžœ!˜)Kšœœœ9œœœ™rK™Kšœ#œ˜=Kš
œ3˜3K˜Kš
œ5˜5šœœ˜Kš
œ?˜?Kš
œ4˜4—šœ
œ"œ˜/Kš
œ<˜<Kš
œ<˜<—šœ˜Kš
œA˜AKš
œC˜C—Kš
œ0˜0Kš
œ1˜1K˜K˜—Kšœ#œ˜=Kš
œ-˜-K˜šœ3œ
œΟc$˜cKš
œ3˜3—K˜K˜—š
žœœ
œ"œœ˜fK˜ K˜šžœœ˜'K˜Kšœ'œ˜;Kšœœ˜K˜šœ@œœ
˜ZKš
œ5˜5K˜K˜šœFœœ
˜`Kš
œ5˜5Kšœ$œœ˜2Kšœœ˜ Kšœ
˜—Kšœ
˜—K˜K˜—šœ1œœ
˜JKš
œ#˜#K˜
Kšœ
˜—K˜K˜—šž
œœCœœ˜tK˜Kšœœ˜*Kšœœ˜*Kšœœ˜/Kšœ,œ
˜0Kšœœ
œ0˜Nšœœ˜K˜
K˜—šœ˜K˜K˜
—šœœ˜K˜K˜K˜K˜K˜—Kšœœ˜ Kšœœ˜ K˜K˜Kšœœ˜ K˜K˜K˜—šžœœ
œ
˜/K˜K˜šžœ˜#Kšœ
œœ3œœœ™hKšœœ˜3Kšœ˜—K˜Kšœœ˜&Kš
œ7˜7Kš
œ/˜/K˜—šžœœ
œ6žœ
ž
œ
œ˜–
K˜Kšœœ
˜šœœ
œ˜6Kš
œ˜Kšœ
˜—šœœ
˜Kš
œ5˜5—Kš
œ˜šœ	œ
˜šœœ
œ˜šœœ
˜&Kš
œ˜—Kšœ<˜@Kš
œ˜—Kšœ
œ
˜
Kšœ
˜—Kšœ˜K˜K˜—šž
œœ$˜7Kš
œ#™#Kšœœ˜*K˜)K˜—šžœ˜Kšœœœœœœ	™WK˜Kšœ#œ˜=Kš
œ-˜-Kšœœ˜&Kš
œ0˜0Kš
œ0˜0Kšœœ
˜K˜Kš
œ˜šœœ˜&Kš
œ˜Kš
œ˜—šœ˜Kš
œ˜Kš
œ˜—šœœœ˜:K˜4Kšœ
˜—K˜)K˜K˜—šžœœœ
œ˜:Kšœ	œ˜+Kš
œ˜—K˜˜Kšžœ˜Kšœœœœœœ	™WK™Kšœ2œ
˜6Kš
œ0˜0Kš
œ0˜0K˜Kšœœ	˜!šœ
œœ
˜)Kšœ/˜1—šœ
œœ
˜"K˜—šœ˜Kšœ#œ˜=Kš
œ3˜3K˜K˜
K˜	K˜š
˜Kšœœ˜#Kšœ
œ
˜Kšœ˜Kšœ
˜—Kš
œY˜Y—K˜K˜—šž	œ˜Kšœ
œœœ
œœ™GK™Kš
œ0˜0Kš
œ0˜0K˜šœ#œ
˜*Kšœ	˜
—Kšœ
œ
˜K˜K˜—šž	œ˜Kšœ
œœœ
œœ™GK™šœœœ
˜)Kšœ	˜
—Kšœ
˜K˜K˜—š
žœœ
œ"œœ˜fK˜K˜K˜'Kšœžœ,˜<K˜K˜—šžœœ
œ
˜.K˜šžœ!˜)Kš
œ3˜3K˜—Kš
œ5˜5K˜—š
ž
œœ
œ"œœ˜gK˜šžœœ˜'Kšœ'œ˜;šœ8œœ
˜NKš
œ0˜0Kšœ
œ
˜šœœ$œ˜CKšœ)œœ˜7Kšœœ˜!—Kšœ˜	K˜——šœ1œœ
˜JK˜Kšœ˜	—K˜—šž	œœ
œ$œœœ˜aKšœœ3˜Xšœœ
˜Kšœœ˜&Kšœ˜—šœ
˜Kšœœ˜)Kšœ˜—K˜K˜—š
žœœ
œ"œœ˜kK˜šžœ˜#Kšœ
œœ3œœœ™hK˜šžœ˜$Kš
œœœœ œœœ™`šœ
œ
œ˜3Kš
œ8˜8Kšœ&œ˜@šœ
œ
œ)˜>Kš
œ8˜8Kšœ&œ˜@šœ3œ˜;Kšœ$œœ˜1Kšœœ˜!—Kšœ
˜—KšœŸ˜K˜——Kš
œ?˜?—K˜Kš
œ0˜0K˜K˜—šžœœ
œ&˜HK˜šžœ˜#Kšœ
œœ3œœœ™hK˜Kšœ4žœ˜L—K˜Kš
œ0˜0K˜K˜—šžœ˜1Kš
œœœœ œœœ™`šœ
œ
œ˜3Kš
œ8˜8Kšœ&œ˜@šœ
œ
œ)˜>Kš
œ8˜8Kšœ&œ˜@šœœ˜#Kšœœœ#˜4Kš
œ˜Kš
œ˜—Kšœ
˜—Kšœ˜	—K˜—šžœœ
œ&˜CK˜Kšžœœ˜'Kšœ'œ˜;Kšœœ˜*šœ8œœ
˜NKš
œ0˜0K˜Kšœ
˜—šœ(œ	œ
˜?Kš
œ7˜7Kš
œ7˜7šœ<œ˜DKšœœ˜6Kšœ
œœ˜9Kšœ
œ1˜8Kšœœ˜7Kšœ
œœ˜8Kšœ
œ2˜9—Kšœ˜	—K˜—šœ1œœ
˜JK˜Kšœ
˜—K˜K˜—šžœœ
œ
˜0K˜šžœ!˜)Kš
œJ˜JKšœœ˜K˜—Kš
œ5˜5K˜K˜—šžœœ
œ'˜EK˜5K˜šžœœ˜'Kšœ'œ˜;šœ8œœ
˜NKš
œ0˜0K˜Kšœœ
˜Kš
œ™Kšœ
˜—Kšœœ˜—K˜šœ1œœ
˜JK˜Kšœ
˜—K˜K˜—šžœœ
œ&˜GK˜K˜—šžœœ
œ:˜ZK˜šœœ
˜Kšœ
œ
˜K˜K˜0K˜K˜DKšœ
˜—K˜K˜—šžœœ
œ:˜Zšœœ
˜Kšœ
œ
˜K˜K˜4K˜DKšœ
˜—K˜K˜—šžœœœœ˜BK˜Kšœœ
œ
œ˜!šœ(œ	œ
˜?šœ œ˜(Kš
œ˜Kš
œ˜—Kšœ
˜—K˜K˜—šžœœœœ˜AKš
œ+˜+Kšœœ
œ
œ˜"šœ(œ	œ
˜?šœ œ˜(Kš
œ˜Kš
œ˜—šœ
œœ
˜,Kšœ
œ%œ˜B—Kšœ
˜—K˜K˜—šžœœ
œ*œ˜jK˜Kš
œ+˜+Kšœœ
˜Kš
œ0˜0Kš
œ0˜0Kšœ'œ˜@Kš
œ˜šœ(œ˜0K˜K˜—šœ˜K˜K˜—Kšœœ
œ0˜Nšœ1œ˜OKšœœk˜rKš
œ7˜7Kšœžœ˜,Kšœ
˜—Kšœ	œ#Ÿ˜AKšœ
œ˜#šœ8œœ
˜NKš
œ0˜0šœ œ œœ
˜^Kš
œ˜—Kšœ
˜—K˜K˜K˜—šžœœ
œ'œœœ˜ƒ
K˜Kšœ#œ˜=Kš
œ-˜-Kš
œ*˜*Kš
œ˜Kšœ(œ
˜,Kš
œ6˜6K˜Kš
œ&˜&KšœTœ˜ZK˜,Kš
œ˜K˜K˜K˜—š
žœœ
œ&œ	œ"˜tK˜šœœ3˜VK˜Kšœ
˜—K˜K˜—š
žœœ
	œ	œ5œ!˜Kš
œ™Kš
œE™EKšœœ˜.Kš	œœœœœ˜MKšœAœ˜FK˜K™Kš
œ9™9Kš
œQ˜QKš
œR˜RK™—š
žœœ
œ@œœ˜‚
K˜šžœ˜#Kš
œ
œœ%œœœœ™yš
œœ
œœ
œ˜0Kš
œG˜GKš	œœœœœ	˜8Kšœ'œ˜BKš
œ$˜$Kšœœœœ1œœ0˜»
Kšœœ-˜:Kšœœ9˜AKšœœ0˜7Kš
Ͻ
˜Ω
J˜šœ@œœ
˜ZKš
œ5˜5Kšœ$œœ˜2Kšœœ˜ —Kšœ
˜Kšœ
œ˜Kš
œ˜—K˜—Kšœ#œ˜=Kš
œ3˜3Kšœœ1˜RKš
œ5˜5Kš
œ6˜6K˜K˜—šž
œœ
œ
˜,K˜šžœ˜.K˜šžœ˜$Kš
œœœœ œœœ™`šœ	œ
œ˜2Kš
œ6˜6Kšœ%œ˜>šœœ
œœœœ
œ˜>Kšœœ-˜:Kšœœ9˜AKš
œ1˜1Kš
œ'˜'—Kšœ˜	K˜——šžœ˜%Kšœœœmœœœ™£
K˜Kš	œœ
œœœ(˜eKšœ%œ˜<Kšœœ
œ˜)Kš
œ˜K˜—Kšœ#œ˜=Kš
œ-˜-Kš
œ3˜3K˜Kš
œ>˜>šœœ˜.Kš
œN˜NKš
œP˜PKšœ
˜—K˜K˜—Kšœ%žœ˜:K˜—š
žœœ
œ)œœ˜tK˜Kšœ#œ˜=Kš
œ3˜3Kš
œ0˜0Kš
œ0˜0Kšœœ
œ1˜WKš
˜šœœ˜Kšœœ˜8Kšœ
œœ˜8Kšœ
œ-˜4Kš
œ˜—šœ
œœ˜&Kšœœ˜8Kšœ
œœ˜8Kšœ
œ-˜4Kš
œ˜—Kšœ
œ-˜4K˜K˜&K˜K˜ˆ
K˜K˜—šžœœ
œ˜6K˜Kš
œ0˜0Kš
œ0˜0Kšœœ˜*Kšœœ˜*Kš
œ'˜'Kš
œ'˜'K˜K˜K˜—šžœœ˜,K˜šœœ2˜;Kšœœ˜)K˜K˜K˜šœ(œ	œ
˜?K˜Kšœ)œœœ˜Zšœœ˜ Kšœ˜Kšœœ!˜3Kšœ!œ˜;Kšœ˜Kš
œ
˜
—šœ
Ÿ˜Kšœœ
˜Kšœœ!˜3—Kšœ˜	—K˜—Kšœ'œ˜;Kšœ	œ˜šœ8œœ
˜NKš
œ0˜0K˜Kšœ
˜—Kšœœœ˜Kšœœ˜K˜K˜—šžœœ
œ%˜FK˜šœ/œ
œ
œ
˜HKš
œ˜Kš
˜—K˜K˜—š
žœœ
œœœ˜QKšœœ
˜K˜	Kšœœ
œ
œ˜Kšœœ˜K˜šœœ
˜Kšœ	œ˜ K˜Kšœ
˜—Kšœ˜KšœŸ˜K˜—šžœœ
œœ˜KKšœœ
˜Kšœœ
˜
šœœ
˜šœ˜Kšœ
œœ
œœ
œ˜9Kšœœ#˜6——K˜Kšœ˜	KšœŸ˜K˜—šžœœœ
œœœ
˜>K˜K˜—šžœœœ˜AKšœœ
˜K˜	šœœ
˜šœœ˜Kš	œœ
œ
œ
Ÿ˜@K˜Kšœ˜
Kš
œ˜—K˜K˜Kšœ
˜—Kšœ˜KšœŸ˜—K˜šžœœœ˜5Kš
œ˜Kšœœ
œ
œ˜šœ
œ
˜Kš
œ˜Kšœ
˜—K˜Kšœ˜Kš
œ˜—K˜K˜—…—l•%