DIRECTORY
Basics, CD, DABasics, List, IO, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, RTBasic, TerminalIO;

RouteChannelConstraintsImpl: CEDAR PROGRAM
IMPORTS Basics, List, IO, Rope, Route, RouteChannel, RouteDiGraph, RouteUtil, RTBasic, TerminalIO
EXPORTS RouteChannel = {

SegBreakType: TYPE = {dogLeg, exit}; -- should add pinDogLeg sometime
SegBreakSpec: TYPE = REF SegBreakSpecRec;
SegBreakSpecRec: TYPE = RECORD [
pos: DABasics.Number _ 0,
type: SegBreakType _ dogLeg,
chainLength: INT _ 0];
Lmr: TYPE = {left, middle, right};
FullSegBreakSpec: TYPE = RECORD [
seg: RouteChannel.Segment _NIL,
breaks: ARRAY Lmr OF SegBreakSpec _ ALL[NIL]];

BreakResult: TYPE = RECORD [
deltaDensity: DABasics.Number,
duplicateLength: DABasics.Number,
numDogLegs: DABasics.Number,
chainLength: DABasics.Number];

RangeWithDirList: TYPE = LIST OF RangeWithDir;
RangeWithDir: TYPE = RECORD [
range: RTBasic.Range,
dir: RouteChannel.GoingDirection];

ChanPinListSet: TYPE = RECORD [
leftExit, rightExit: RouteChannel.ChanPin _ NIL,
bottomList, topList: RouteChannel.ChanPinList _ NIL];

ChanPinListPair: TYPE = RECORD [
list1, list2: RouteChannel.ChanPinList _ NIL];

TestPins: TYPE = REF TestPinsRec;
TestPinsRec: TYPE = RECORD [
trialPin, leftExitPin, rightExitPin: RouteChannel.ChanPin _ NIL];

GenerateConstraints: PUBLIC PROC [chanData: RouteChannel.ChannelData, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
routerUsed: RoutePrivate.RouterUsed] 
RETURNS [anythingToDo: BOOLEAN] ~ {
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
graphName: Rope.ROPE _ "Vertical Constraints";
segBroken: BOOLEAN _ TRUE;
trialPinPosition: RouteChannel.PinPosition _ NEW[RouteChannel.PinPositionRec _ [pinIndex: 0, pLoc: 0]];
trialPin: RouteChannel.ChanPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: none, qLoc: 0, pWidth: 0, kindOfPin: dogLeg, pinPosition: trialPinPosition]];
leftExitPosition: RouteChannel.PinPosition _ NEW[RouteChannel.PinPositionRec _ [pinIndex: 0, pLoc: chanPins.cEnd1]];
leftExitPin: RouteChannel.ChanPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: none, qLoc: 0, pWidth: 0, kindOfPin: exitPin, pinPosition: leftExitPosition]];
rightExitPosition: RouteChannel.PinPosition _ NEW[RouteChannel.PinPositionRec _ [pinIndex: 0, pLoc: chanPins.cEnd2]];
rightExitPin: RouteChannel.ChanPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: none, qLoc: 0, pWidth: 0, kindOfPin: exitPin, pinPosition: rightExitPosition]];
pins: TestPins _ NEW[TestPinsRec _ [trialPin, leftExitPin, rightExitPin]];
IF chanPins.count = 0 THEN RETURN[FALSE];

WHILE segBroken DO
segBroken _ FALSE;
IF chanData.constraints # NIL THEN DestroyOldConstraints[chanData]; -- unlink the old graph
chanData.constraints _ RouteDiGraph.CreateGraph[graphName];

FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO

WidestPinProc: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
widestPinD2 _ MAX[widestPinD2, RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2]};

LimitProc: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
{width: DABasics.Number _ RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2;
pinPos: DABasics.Number _ pin.pinPosition.pLoc;
IF pinPos = pLoc THEN
quit _ TRUE
ELSE IF pinPos < pLoc THEN
quit _ pinPos + width + rules.branchSpacing > pLoc - widestPinD2
ELSE -- pinPos >= pLoc
quit _ pLoc + widestPinD2 + rules.branchSpacing > pinPos - width}};

pinPosition: RouteChannel.PinPosition _ chanPins.sides[index];
testPin: RouteChannel.ChanPin _ pinPosition.pins[chanBottom];
pLoc: DABasics.Number _ pinPosition.pLoc;
widestPinD2: DABasics.Number _ RouteUtil.GetWidthWithContact[rules, rules.branchWidth]/2;
minLimit, maxLimit: RouteChannel.MPinsOnCh;

[] _ RouteChannel.EnumPins[pinPosition, WidestPinProc];
[minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[chanPins, parms, rules, index, index, LimitProc];
FOR upperIndex: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] DO
upperPinPosition: RouteChannel.PinPosition _ chanPins.sides[upperIndex];
upperPin: RouteChannel.ChanPin _ upperPinPosition.pins[chanTop];
lowerPin: RouteChannel.ChanPin _ upperPinPosition.pins[chanBottom];

IF ProcessConstraints[chanData, parms, rules, upperPin, testPin, middle, pins] THEN GOTO GoRound;
FOR innerPins: RouteChannel.ChanPinList _ pinPosition.innerPins, innerPins.rest WHILE innerPins # NIL DO
innerPin: RouteChannel.ChanPin _ innerPins.first;
IF ProcessConstraints[chanData, parms, rules, upperPin, innerPin, middle, pins] THEN GOTO GoRound;
IF ProcessConstraints[chanData, parms, rules, innerPin, lowerPin, middle, pins] THEN GOTO GoRound;
ENDLOOP; -- FOR innerPins
ENDLOOP; -- FOR upperIndex

IF routerUsed = switchBox AND (index = 1 OR  index = chanPins.count) THEN {

QPinCompare: List.CompareProc = {
p1: DABasics.Number _ NARROW[ref1, RouteChannel.ChanPin].qLoc;
p2: DABasics.Number _ NARROW[ref2, RouteChannel.ChanPin].qLoc;
RETURN[IF p1 < p2 THEN Basics.Comparison.less
ELSE IF p1 = p2 THEN Basics.Comparison.equal
ELSE Basics.Comparison.greater]};

whichEnd: Lmr _ IF index = 1 THEN left ELSE right;
mungedPinList: List.LORA _ ConvertToLORA[pinPosition.innerPins];
sortedPinList: List.LORA _ List.Sort[mungedPinList, QPinCompare];
FOR pList: List.LORA -- RouteChannel.ChanPinList -- _ sortedPinList, pList.rest WHILE pList # NIL DO
lowerPin: RouteChannel.ChanPin _ NARROW[pList.first];
sList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[lowerPin];

IF pList.rest # NIL THEN {
upperPin: RouteChannel.ChanPin _ NARROW[pList.rest.first];
IF ProcessConstraints[chanData, parms, rules, upperPin, lowerPin, whichEnd, pins] THEN GOTO GoRound};

FOR segs: RouteChannel.SegmentList _ sList, segs.rest WHILE segs # NIL DO
seg: RouteChannel.Segment _ segs.first;
IF seg.trackConstraint # 0 AND seg.secTrackConstraint # 0 AND seg.trackConstraint # seg.secTrackConstraint AND ~seg.failed THEN {
break: FullSegBreakSpec _ BreakOneSeg[chanData, parms, rules, seg, NIL, whichEnd, pins];
IF BreaksFound[break] > 0 THEN {
DoBreak[chanData, parms, break]; GOTO GoRound}
ELSE {  -- mark seg as failed --
seg.failed _ TRUE;
Route.Signal[noResource, Rope.Cat["\nunable to find a place to dogleg, net: ", seg.net.name, " failed"]]}};
IF index = chanPins.count THEN {
leftPinPosition: RouteChannel.PinPosition _ chanPins.sides[1];
leftPinList: RouteChannel.ChanPinList _ leftPinPosition.innerPins;
FOR lPList: RouteChannel.ChanPinList _ leftPinList, lPList.rest WHILE lPList # NIL DO
leftPin: RouteChannel.ChanPin _ NARROW[lPList.first];
lSList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[leftPin];
FOR lSegs: RouteChannel.SegmentList _ lSList, lSegs.rest WHILE lSegs # NIL DO
graph: RouteDiGraph.Graph _ chanData.constraints;
leftSeg: RouteChannel.Segment _ lSegs.first;
leftSegNode: RouteDiGraph.Node _ leftSeg.constraintNode;
rightSegNode: RouteDiGraph.Node _ seg.constraintNode;
leftToRightSegList: RouteChannel.SegmentList _ SegsInCycle[graph, leftSegNode, rightSegNode];
rightToLeftSegList: RouteChannel.SegmentList;
IF leftToRightSegList # NIL THEN
{density: RouteChannel.Density _ RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec _ FindBreak[chanData, parms, rules, leftToRightSegList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanData, parms, segBreak]
ELSE {  -- choose a victim --
lSegs.first.failed _ TRUE;
Route.Signal[noResource, Rope.Cat["\nnet: ", lSegs.first.net.name, " failed, unable to find a place to dogleg"]]};

segBroken _ TRUE; GOTO GoRound};
rightToLeftSegList _ SegsInCycle[graph, rightSegNode, leftSegNode];
IF rightToLeftSegList # NIL THEN
{density: RouteChannel.Density _ RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec _ FindBreak[chanData, parms, rules, rightToLeftSegList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanData, parms, segBreak]
ELSE {  -- choose a victim --
lSegs.first.failed _ TRUE;
Route.Signal[noResource, Rope.Cat["\nnet: ", lSegs.first.net.name, " failed, unable to find a place to dogleg"]]};

segBroken _ TRUE; GOTO GoRound};
IF seg.trackConstraint = leftSeg.trackConstraint AND RTBasic.Overlaps[RouteChannel.SegRange[seg], RouteChannel.SegRange[leftSeg]] AND seg.net # leftSeg.net THEN
{density: RouteChannel.Density _ RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec _ FindBreak[chanData, parms, rules, LIST[seg, leftSeg], density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanData, parms, segBreak]
ELSE {  -- choose a victim --
seg.failed _ TRUE;
Route.Signal[noResource, Rope.Cat["\nnet: ", seg.net.name, " failed, unable to find a place to dogleg"]]};

segBroken _ TRUE; GOTO GoRound};
ENDLOOP;
ENDLOOP;
};
ENDLOOP;
ENDLOOP};
REPEAT GoRound => segBroken _ TRUE;
ENDLOOP; -- WHILE index
ENDLOOP; -- WHILE segBroken
RETURN[TRUE]}; -- GenerateConstraints

DestroyOldConstraints: PUBLIC PROC [chanData: RouteChannel.ChannelData] = {

chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
DestroyGraph: RouteDiGraph.EnumGraphProc = {NULL};

DestroyArc: RouteDiGraph.EnumArcProc = {NULL};

DestroyNode: RouteDiGraph.EnumNodeProc = {
nodeInfo: RouteChannel.SegmentConstraint _ NARROW[node.nodeInfo];
nodeInfo.segment _ NIL};

ClearConstraints: RouteChannel.EachPinActionProc = {
leftSeg: RouteChannel.Segment _ pin.conctSeg[chanLeft];
rightSeg: RouteChannel.Segment _ pin.conctSeg[chanRight];
IF leftSeg # NIL THEN leftSeg.constraintNode _ NIL;
IF rightSeg # NIL THEN rightSeg.constraintNode _ NIL};

FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
pinPosition: RouteChannel.PinPosition _ chanPins.sides[index];
[] _ RouteChannel.EnumPins[pinPosition, ClearConstraints];
ENDLOOP;

RouteDiGraph.DestroyGraph[chanData.constraints, DestroyGraph, DestroyNode, DestroyArc]};

ProcessConstraints: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, upperPin, lowerPin: RouteChannel.ChanPin, whichEnd: Lmr, pins: TestPins] RETURNS [segBroken: BOOLEAN _ FALSE] = {

IF upperPin # NIL AND lowerPin # NIL THEN
IF upperPin.kindOfPin # noPin AND  lowerPin.kindOfPin # noPin THEN
IF (upperPin.kindOfPin # exitPin AND lowerPin.kindOfPin # exitPin) OR (whichEnd # middle AND upperPin.kindOfPin = exitPin AND lowerPin.kindOfPin = exitPin) THEN
IF Constraining[rules, upperPin, lowerPin] THEN
FOR lowerSegIndex: RouteChannel.ChanLRSide IN [chanLeft .. chanRight] WHILE ~segBroken DO
FOR upperSegIndex: RouteChannel.ChanLRSide IN [chanLeft .. chanRight] WHILE ~segBroken DO
lowerSeg: RouteChannel.Segment _ lowerPin.conctSeg[lowerSegIndex];
upperSeg: RouteChannel.Segment _ upperPin.conctSeg[upperSegIndex];
lowerAltSeg: RouteChannel.Segment _ lowerPin.altConctSeg[lowerSegIndex];
upperAltSeg: RouteChannel.Segment _ upperPin.altConctSeg[upperSegIndex];
IF HackedDoConstraint[chanData, parms, rules, lowerSeg, upperSeg, whichEnd, pins] THEN segBroken _ TRUE;
IF HackedDoConstraint[chanData, parms, rules, lowerSeg, upperAltSeg, whichEnd, pins] THEN segBroken _ TRUE;
IF HackedDoConstraint[chanData, parms, rules, lowerAltSeg, upperSeg, whichEnd, pins] THEN segBroken _ TRUE;
IF HackedDoConstraint[chanData, parms, rules, lowerAltSeg, upperAltSeg, whichEnd, pins] THEN segBroken _ TRUE;
ENDLOOP; -- FOR upperSegIndex
ENDLOOP; -- FOR lowerSegIndex
};

Constraining: PROC [rules: Route.DesignRules, pin1, pin2: RouteChannel.ChanPin] RETURNS [constraining: BOOLEAN _ FALSE] = {

IF pin1 # NIL AND pin2 # NIL THEN
{p1: DABasics.Number _ pin1.pinPosition.pLoc;
w1WContact: DABasics.Number _ RouteUtil.GetWidthWithContact[rules, pin1.pWidth]/2;
w1: DABasics.Number _ pin1.pWidth/2;
p2: DABasics.Number _ pin2.pinPosition.pLoc;
w2WContact: DABasics.Number _ RouteUtil.GetWidthWithContact[rules, pin2.pWidth]/2;
w2: DABasics.Number _ pin2.pWidth/2;
IF p1 = p2 THEN
constraining _ TRUE
ELSE IF p1 < p2 THEN
constraining _ (p1 + w1WContact + rules.branchSpacing > p2 - w2)
OR (p1 + w1 + rules.branchSpacing > p2 - w2WContact)
ELSE -- p1 > p2
constraining _ (p2 + w2WContact + rules.branchSpacing > p1 - w1)
OR (p2 + w2 + rules.branchSpacing > p1 - w1WContact)}};

DoConstraint: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, lowerSeg, upperSeg: RouteChannel.Segment, whichEnd: Lmr, pins: TestPins] RETURNS [segBroken: BOOLEAN _ FALSE] = {

IF lowerSeg # NIL AND upperSeg # NIL AND lowerSeg # upperSeg THEN
IF ~lowerSeg.failed AND ~upperSeg.failed AND lowerSeg.net.num # upperSeg.net.num THEN {
segList: RouteChannel.SegmentList;
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
graph: RouteDiGraph.Graph _ chanData.constraints;
lowerNode: RouteDiGraph.Node _ lowerSeg.constraintNode;
upperNode: RouteDiGraph.Node _ upperSeg.constraintNode;
IF lowerNode = NIL THEN
{constraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [lowerSeg.net.name, lowerSeg]];
lowerNode _ RouteDiGraph.AddNewNode[graph, constraint];
lowerSeg.constraintNode _ lowerNode};
IF upperNode = NIL THEN
{constraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [upperSeg.net.name, upperSeg]];
upperNode _ RouteDiGraph.AddNewNode[graph, constraint];
upperSeg.constraintNode _ upperNode};

segList _ SegsInCycle[graph, lowerNode, upperNode];
IF segList # NIL THEN {
density: RouteChannel.Density _ RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec _ FindBreak[chanData, parms, rules, segList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanData, parms, segBreak]
ELSE {  -- choose a victim --
segList.first.failed _ TRUE;
Route.Signal[noResource, Rope.Cat["net: ", segList.first.net.name, " failed, unable to find a place to dogleg"]]};

segBroken _ TRUE}
ELSE { -- add a segment constraint

IF ~RouteDiGraph.PathExists[graph, upperNode, lowerNode] THEN
[] _ RouteDiGraph.AddNewArc[graph, NIL, upperNode, lowerNode]}}};

SegsInCycle: PROCEDURE[graph: RouteDiGraph.Graph, lowerNode, upperNode: RouteDiGraph.Node]
RETURNS [segList: RouteChannel.SegmentList _ NIL] = {

ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
-- PROC[graph: Graph, arc: Arc, node: Node, direction: Direction] RETURNS [quit: BOOLEAN _ FALSE];
IF arc.inferiorNode = upperNode THEN
{nodeInfo: RouteChannel.SegmentConstraint _ NARROW[upperNode.nodeInfo];
segList _ CONS[nodeInfo.segment, segList];
quit _ TRUE}
ELSE {
IF ~List.Memb[arc.inferiorNode, visitedNodes] THEN {
visitedNodes _ CONS[arc.inferiorNode, visitedNodes];
quit _ RouteDiGraph.EnumArcsFromNode[graph, arc.inferiorNode, in, ArcProc]}};
IF quit THEN
{nodeInfo: RouteChannel.SegmentConstraint _ NARROW[node.nodeInfo];
segList _ CONS[nodeInfo.segment, segList]}};

visitedNodes: RouteDiGraph.ArcList _ NIL;
[] _ RouteDiGraph.EnumArcsFromNode[graph, lowerNode, in, ArcProc]};

PrintSegs: PROC [
segList: RouteChannel.SegmentList] = {

FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO
seg: RouteChannel.Segment _ segs.first;
range: RTBasic.Range _ RouteChannel.SegRange[seg];
TerminalIO.PutF["\n\tnet: %g at %g , %g ( %g, %g )", IO.rope[seg.net.name], IO.int[range.l], IO.int[range.r], IO.int[range.l/8], IO.int[range.r/8]];
ENDLOOP};

FindBreak: PROC [chanData: RouteChannel.ChannelData, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
segList: RouteChannel.SegmentList, 
density: RouteChannel.Density, 
whichEnd: Lmr, 
pins: TestPins] RETURNS [bestBreak: FullSegBreakSpec _ [NIL, [NIL, NIL, NIL]]] = {

chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
bestResult: BreakResult _ [LAST[INT], LAST[INT], LAST[INT], LAST[INT]];

TerminalIO.PutRope["\nSegements in Cycle:"];
FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO
seg: RouteChannel.Segment _ segs.first;
break: FullSegBreakSpec _ BreakOneSeg[chanData, parms, rules, seg, density, whichEnd, pins];
result: BreakResult _ EvalBreak[chanPins, parms, break, density];
range: RTBasic.Range _ RouteChannel.SegRange[seg];
TerminalIO.PutF["\n\tnet: %g at %g , %g ( %g, %g )", IO.rope[seg.net.name], IO.int[range.l], IO.int[range.r], IO.int[range.l/8], IO.int[range.r/8]];
TerminalIO.PutF["\n\t\tdeltaDensity: %g duplicateLength: %g numDogLegs: %g , chainLength: %g", IO.int[result.deltaDensity], IO.int[result.duplicateLength], IO.int[result.numDogLegs], IO.int[result.chainLength]];
IF CompareResult[result, bestResult] = less THEN
{bestResult _ result; bestBreak _ break};
ENDLOOP;

IF bestBreak.seg = NIL THEN RETURN[[NIL, [NIL, NIL, NIL]]]};

BreakOneSeg: PROC [chanData: RouteChannel.ChannelData, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
seg: RouteChannel.Segment, 
density: RouteChannel.Density, 
whichEnd: Lmr, 
pins: TestPins] 
RETURNS [break: FullSegBreakSpec] = {

chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
exitsSeparate: BOOLEAN _ IF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet _ GetPins[exitsSeparate, seg];
rangeList: RangeWithDirList _ SegRanges[chanPins, pinLists];
break _ [seg, [NIL, NIL, NIL]];

IF ~HasDogleg[seg] THEN {
SELECT parms.routerUsed FROM
channel => {
FOR ranges: RangeWithDirList _ rangeList, ranges.rest WHILE ranges # NIL DO
break.breaks[middle] _ HackedBreakWithInRange[chanData, parms, rules, seg, ranges.first, pins];
IF break.breaks[middle] # NIL THEN EXIT;
ENDLOOP;

IF break.breaks[middle] = NIL AND seg.net.mayExit THEN
break.breaks[middle] _ BreakAtExit[chanPins, parms, seg, density]};

switchBox => {
DoMiddle: PROC [] ~ {
IF top AND bottom AND BreaksFound[break] = 0 THEN {
FOR ranges: RangeWithDirList _ rangeList, ranges.rest WHILE ranges # NIL DO
break.breaks[middle] _ BreakWithInRange[chanData, parms, rules, seg, ranges.first, pins];
IF break.breaks[middle] # NIL THEN EXIT;
ENDLOOP;
};
};

DoLeft: PROC [] ~ {
IF left AND (top OR right OR bottom) AND BreaksFound[break] = 0 THEN {
leftRange: RangeWithDir _ [[cEnd1, cEnd2], leftToRight];
break.breaks[left] _ BreakWithInRange[chanData, parms, rules, seg, leftRange, pins];
};
};

DoRight: PROC [] ~ {
IF right AND (top OR left OR bottom) AND BreaksFound[break] = 0 THEN {
rightRange: RangeWithDir _ [[cEnd1, cEnd2], rightToLeft];
break.breaks[right] _ BreakWithInRange[chanData, parms, rules, seg, rightRange, pins];
};
};

cEnd1: DABasics.Number _ chanPins.cEnd1;
cEnd2: DABasics.Number _ chanPins.cEnd2;
left, top, right, bottom: BOOLEAN;
[left, top, right, bottom] _ RouteChannel.PinsOnSide[seg];

SELECT TRUE FROM
whichEnd = left => {DoLeft; DoRight; DoMiddle};
whichEnd = right => {DoRight; DoLeft; DoMiddle};
seg.trackConstraint # 0 => {DoRight; DoLeft; DoMiddle};
ENDCASE => {DoMiddle; DoRight; DoLeft}};

ENDCASE => Route.Error[programmingError, "Invalid router being used."]
}};

HasDogleg: PROC [seg: RouteChannel.Segment] RETURNS [hasDogleg: BOOLEAN _ FALSE] ~ {


EachPin: RouteChannel.EachPinActionProc ~ {

IF pin.kindOfPin = dogLeg  THEN quit _ TRUE};

hasDogleg _ RouteChannel.EnumPinsOnSeg[seg, EachPin]};

BreakWithInRange: PROC [chanData: RouteChannel.ChannelData, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
seg: RouteChannel.Segment, 
range: RangeWithDir, 
pins: TestPins] 
RETURNS [break: SegBreakSpec _ NIL] = {

WidestPinProc: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
widestPinD2 _ MAX[widestPinD2, RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2]};

NextPosToRight: PROC [pinIndex: RouteChannel.ZMPinsOnCh] RETURNS[pos: DABasics.Number] ~ {
IF pinIndex = 0 THEN
pos _ chanPins.cEnd1 + rules.branchSpacing + seg.net.branchWidth
ELSE IF pinIndex >= chanPins.count+1 THEN
pos _ LAST[INT]
ELSE {
pinPosition: RouteChannel.PinPosition _ chanPins.sides[pinIndex];
widestPinD2 _ minPinD2;
[] _ RouteChannel.EnumPins[pinPosition, WidestPinProc];
pos _ pinPosition.pLoc + widestPinD2 + rules.branchSpacing + RouteUtil.GetWidthWithContact[rules, seg.net.branchWidth]/2}};

NextPosToLeft: PROC [pinIndex: RouteChannel.ZMPinsOnCh] RETURNS[pos: DABasics.Number] ~ {
IF pinIndex <= 0 THEN
pos _ FIRST[INT]
ELSE IF pinIndex = chanPins.count THEN
pos _ chanPins.cEnd2 - rules.branchSpacing - seg.net.branchWidth
ELSE {
pinPosition: RouteChannel.PinPosition _ chanPins.sides[pinIndex];
widestPinD2 _ minPinD2;
[] _ RouteChannel.EnumPins[pinPosition, WidestPinProc];
pos _ pinPosition.pLoc - widestPinD2 - rules.branchSpacing - RouteUtil.GetWidthWithContact[rules, seg.net.branchWidth]/2}};

chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
minPinD2: DABasics.Number _ rules.branchWidth/2;
widestPinD2: DABasics.Number;

SELECT range.dir FROM
leftToRight => {
nextLower: RouteChannel.ZMPinsOnCh _ ClosestPins[chanPins, range.range.l].nextLower;
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, range.range.l, pins] THEN
break _ NEW[SegBreakSpecRec _  [range.range.l, dogLeg]];
FOR pos: DABasics.Number _ NextPosToRight[nextLower], NextPosToRight[nextLower] WHILE pos <= range.range.r AND break = NIL DO
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, pos, pins] THEN
break _ NEW[SegBreakSpecRec _  [pos, dogLeg]];
nextLower _ MIN[chanPins.count+1, nextLower + 1];
ENDLOOP};
rightToLeft => {
nextHigher: RouteChannel.ZMPinsOnCh _ ClosestPins[chanPins, range.range.r].nextHigher;
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, range.range.r, pins] THEN
break _ NEW[SegBreakSpecRec _  [range.range.r, dogLeg]];
FOR pos: DABasics.Number _ NextPosToLeft[nextHigher], NextPosToLeft[nextHigher] WHILE pos >= range.range.l AND break = NIL DO
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, pos, pins] THEN
break _ NEW[SegBreakSpecRec _  [pos, dogLeg]];
nextHigher _ MAX[0, nextHigher - 1];
ENDLOOP};
ENDCASE};

DogLegNotAllowed: PROC [chanPins: RouteChannel.RoutingChannelPins, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
seg: RouteChannel.Segment, 
pos: DABasics.Number, 
pins: TestPins] 
RETURNS [notAllowed: BOOLEAN _ FALSE] = {

FindConnectedNet: PROC [pin: RouteChannel.ChanPin] RETURNS [net: RoutePrivate.Net _ NIL] =
{IF pin # NIL THEN
{s1: RouteChannel.Segment _ pin.conctSeg[chanLeft];
s2: RouteChannel.Segment _ pin.conctSeg[chanRight];
IF s1 # NIL THEN net _ s1.net
ELSE IF s2 # NIL THEN net _ s2.net
ELSE Route.Error[programmingError, "Pin not connected to a segment."]}};

CheckInner: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
IF pin.kindOfPin = exitPin OR pin.kindOfPin = dogLeg THEN
IF Constraining[rules, pin, pins.trialPin] THEN quit _ TRUE};

OuterConstraints: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
IF pin.kindOfPin = chanConnect OR pin.kindOfPin = compPin THEN
IF Constraining[rules, pin, pins.trialPin] THEN quit _ TRUE};

minLimit, maxLimit, leftIndex, rightIndex: RouteChannel.ZMPinsOnCh;
width: DABasics.Number _ MAX[seg.net.trunkWidth, seg.net.branchWidth];
pins.trialPin.pinPosition.pLoc _ pos;
pins.trialPin.pWidth _ width;
pins.leftExitPin.pWidth _ width;
pins.rightExitPin.pWidth _ width;
[leftIndex, rightIndex] _ ClosestPins[chanPins, pos];

IF Constraining[rules, pins.trialPin, pins.leftExitPin] THEN notAllowed _ TRUE;
IF Constraining[rules, pins.trialPin, pins.rightExitPin] THEN notAllowed _ TRUE;

[minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[chanPins, parms, rules, leftIndex, rightIndex, CheckInner];
FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pinPosition: RouteChannel.PinPosition _ chanPins.sides[index];
notAllowed _ RouteChannel.EnumPins[pinPosition, CheckInner];
ENDLOOP;
[minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[chanPins, parms, rules, leftIndex, rightIndex, OuterConstraints];
FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pinPosition: RouteChannel.PinPosition _ chanPins.sides[index];
bottomPin: RouteChannel.ChanPin _ pinPosition.pins[chanBottom];
topPin: RouteChannel.ChanPin _ pinPosition.pins[chanTop];
bottomNet: RoutePrivate.Net _ FindConnectedNet[bottomPin];
topNet: RoutePrivate.Net _ FindConnectedNet[topPin];
constrainTop: BOOLEAN _ Constraining[rules, topPin, pins.trialPin];
constrainBottom: BOOLEAN _ Constraining[rules, bottomPin, pins.trialPin];

FOR i: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pP: RouteChannel.PinPosition _ chanPins.sides[i];
bP: RouteChannel.ChanPin _ pP.pins[chanBottom];
tP: RouteChannel.ChanPin _ pP.pins[chanTop];
bN: RoutePrivate.Net _ FindConnectedNet[bP];
tN: RoutePrivate.Net _ FindConnectedNet[tP];
IF bottomNet = tN AND Constraining[rules, topPin, bP] AND constrainTop AND constrainBottom THEN notAllowed _ TRUE;
IF topNet = bN AND Constraining[rules, bottomPin, tP] AND constrainTop AND constrainBottom THEN notAllowed _ TRUE;
ENDLOOP;

IF constrainTop OR constrainBottom THEN notAllowed _ TRUE;
ENDLOOP};

BreakAtExit: PROC [chanPins: RouteChannel.RoutingChannelPins, parms: RoutePrivate.RoutingAreaParms, seg: RouteChannel.Segment, density: RouteChannel.Density] RETURNS [break: SegBreakSpec] = {

leftBreak: SegBreakSpec _ NEW[SegBreakSpecRec _ [chanPins.cEnd1, exit]];
leftFullBreak: FullSegBreakSpec _ [seg, [leftBreak, NIL, NIL]];
rightBreak: SegBreakSpec _ NEW[SegBreakSpecRec _ [chanPins.cEnd2, exit]];
rightFullBreak: FullSegBreakSpec _ [seg, [NIL, NIL, rightBreak]];
leftResult: BreakResult _ EvalBreak[chanPins, parms, leftFullBreak, density];
rightResult: BreakResult _ EvalBreak[chanPins, parms, rightFullBreak, density];
IF CompareResult[leftResult, rightResult] = less THEN RETURN [leftBreak]
ELSE RETURN [rightBreak]};

EvalBreak: PROC [chanPins: RouteChannel.RoutingChannelPins, parms: RoutePrivate.RoutingAreaParms, break: FullSegBreakSpec, density: RouteChannel.Density] RETURNS [result: BreakResult] = {

maxDensity: DABasics.Number;
lowerRange, upperRange, overlap: RTBasic.Range;
exitsSeparate: BOOLEAN _ IF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet _ GetPins[exitsSeparate, break.seg];
chain: INT _ LAST[INT];
IF BreaksFound[break] = 0 THEN RETURN[[LAST[INT], LAST[INT], LAST[INT], LAST[INT]]];

IF break.breaks[middle] # NIL THEN { 
lowerRange _ RTBasic.Span[[break.breaks[middle].pos, break.breaks[middle].pos], RouteChannel.GetRange[pinLists.bottomList]];
upperRange _ RTBasic.Span[[break.breaks[middle].pos, break.breaks[middle].pos], RouteChannel.GetRange[pinLists.topList]];
overlap _ RTBasic.Overlap[lowerRange, upperRange];
IF overlap.l > overlap.r THEN Route.Error[programmingError, "overlap should not be NIL."];
chain _ break.breaks[middle].chainLength}
ELSE overlap _ [0,0];

maxDensity _ AddSeg[chanPins, density, overlap, break.seg.qWidth];
result.deltaDensity _ maxDensity - density.maxDensity;
result.duplicateLength _ overlap.r - overlap.l;
result.numDogLegs _ 0;
result.chainLength _ chain;
FOR lmr: Lmr IN Lmr DO
IF break.breaks[lmr] # NIL THEN result.numDogLegs _ result.numDogLegs + 1;
ENDLOOP};

DoBreak: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, fullSegBreak: FullSegBreakSpec] = {
UnlinkSegFromPins: RouteChannel.EachPinActionProc ~ {
IF pin.conctSeg[chanLeft] = oldSeg THEN pin.conctSeg[chanLeft] _ NIL;
IF pin.conctSeg[chanRight] = oldSeg THEN pin.conctSeg[chanRight] _ NIL;
IF pin.altConctSeg[chanLeft] = oldSeg THEN pin.altConctSeg[chanLeft] _ NIL;
IF pin.altConctSeg[chanRight] = oldSeg THEN pin.altConctSeg[chanRight] _ NIL;
};

chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
oldSeg: RouteChannel.Segment _ fullSegBreak.seg;
branchWidth: DABasics.Number _ oldSeg.net.branchWidth;
trunkWidth: DABasics.Number _ oldSeg.net.trunkWidth;
IF BreaksFound[fullSegBreak]  # 1 THEN
Route.Error[programmingError, "Not suppose to happen"];
[] _ RouteChannel.EnumPinsOnSeg[oldSeg, UnlinkSegFromPins];

FOR lmr: Lmr IN Lmr DO
segBreak: SegBreakSpec _ fullSegBreak.breaks[lmr];
IF segBreak # NIL THEN {
pinIndex: RouteChannel.ZMPinsOnCh _ RouteChannel.FindPinPos[chanPins, segBreak.pos];
pinPosition: RouteChannel.PinPosition _ chanPins.sides[pinIndex];
upperPin, lowerPin: RouteChannel.ChanPin _ NIL;
pinListPair: ChanPinListPair;
seg1: RouteChannel.Segment _ NEW[RouteChannel.SegmentRec _ [net: oldSeg.net, qWidth: trunkWidth, exitBreak: oldSeg.exitBreak]];
seg2: RouteChannel.Segment _ NEW[RouteChannel.SegmentRec _ [net: oldSeg.net, qWidth: trunkWidth, exitBreak: oldSeg.exitBreak]];

SELECT segBreak.type FROM
dogLeg => {
exitsSeparate: BOOLEAN _ IF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet _ GetPins[exitsSeparate, oldSeg];
parms.widestPin _ MAX[branchWidth, parms.widestPin];
upperPin _ lowerPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: none, qLoc: 0, pWidth: branchWidth, kindOfPin: dogLeg, pinPosition: pinPosition]];
pinPosition.innerPins _ CONS[upperPin, pinPosition.innerPins];
pinListPair _ DividePins[lmr, pinLists, lowerPin, upperPin]};

exit => {
pinSide: RouteChannel.ChanLRSide _
IF segBreak.pos <= chanPins.cEnd1 THEN chanLeft
ELSE IF segBreak.pos >= chanPins.cEnd2 THEN chanRight
ELSE Route.Error[programmingError, "Invalid data. Call maintainer."];
pinLists: ChanPinListSet _ GetPins[TRUE, oldSeg];
seg1.exitBreak _ TRUE; seg1.part _ 1;
seg2.exitBreak _ TRUE; seg2.part _ 2;
upperPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: pinSide, qLoc: 0, pWidth: 0, kindOfPin: exitPin, pinPosition: pinPosition]];
pinPosition.innerPins _ CONS[upperPin, pinPosition.innerPins];
lowerPin _ IF pinSide = chanRight THEN pinLists.rightExit ELSE pinLists.leftExit;
IF lowerPin = NIL THEN {
lowerPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: pinSide, qLoc: 0, pWidth: 0, kindOfPin: exitPin, pinPosition: pinPosition]];
pinPosition.innerPins _ CONS[lowerPin, pinPosition.innerPins]}
ELSE {
};
pinListPair _ DividePins[lmr, pinLists, lowerPin, upperPin]};
ENDCASE;

LinkSegsToPins[seg1, pinListPair.list1, lowerPin];
LinkSegsToPins[seg2, pinListPair.list2, upperPin];
SetTrackConstraints[seg1, oldSeg.trackConstraint];
SetTrackConstraints[seg2, oldSeg.trackConstraint];

TerminalIO.PutRope[Rope.Cat["\ntrunk segment for net: ", fullSegBreak.seg.net.name, ]];
TerminalIO.PutF1[" divided at: %g", IO.int[chanPins.sides[pinIndex].pLoc/8]];
RouteChannel.AuditPins[chanPins]};
ENDLOOP;
};

DividePins: PROC [which: Lmr, pinLists: ChanPinListSet, pin1, pin2: RouteChannel.ChanPin] RETURNS [pinListPair: ChanPinListPair _ [NIL, NIL]] = {
SELECT which FROM
left => {
IF pinLists.leftExit = NIL THEN Route.Error[programmingError, "exit dogleg with no exit"];
pinListPair.list1 _ LIST[pin1, pinLists.leftExit];
pinListPair.list2 _ RouteChannel.Combine[pinLists.bottomList, pinLists.topList, LIST[pinLists.rightExit, pin2]]};

middle => {
pinListPair.list1 _ RouteChannel.Combine[LIST[pin1], pinLists.bottomList, NIL];
pinListPair.list2 _ RouteChannel.Combine[LIST[pin2], pinLists.topList, NIL];
pinListPair _ AddToClosestList[pinListPair, pinLists.leftExit];
pinListPair _ AddToClosestList[pinListPair, pinLists.rightExit]};

right => {
IF pinLists.rightExit = NIL THEN Route.Error[programmingError, "exit dogleg with no exit"];
pinListPair.list1 _ LIST[pin1, pinLists.rightExit];
pinListPair.list2 _ RouteChannel.Combine[pinLists.bottomList, pinLists.topList, LIST[pinLists.leftExit, pin2]]};
ENDCASE;
};

SetTrackConstraints: PROC [seg: RouteChannel.Segment, trackConstraint: DABasics.Number] = {

EachPin: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN {
IF pin.trackConstraint # 0 THEN
seg.trackConstraint _ pin.trackConstraint;
};
};

[] _ RouteChannel.EnumPinsOnSeg[seg, EachPin];
};

AddToClosestList: PROC [pinListPair: ChanPinListPair, pin: RouteChannel.ChanPin] RETURNS [result: ChanPinListPair] ~ {

l1Range: RTBasic.Range _ RouteChannel.GetRange[pinListPair.list1];
l2Range: RTBasic.Range _ RouteChannel.GetRange[pinListPair.list2];
IF pin # NIL THEN {
pLoc: DABasics.Number _ pin.pinPosition.pLoc;
IF l1Range.l <= pLoc AND pLoc <= l1Range.r THEN RETURN[[CONS[pin, pinListPair.list1], pinListPair.list2]]
ELSE IF l2Range.l <= pLoc AND pLoc <= l2Range.r THEN RETURN[[pinListPair.list1, CONS[pin, pinListPair.list2]]]
ELSE {
distToL1: DABasics.Number _ MIN[ABS[pLoc - l1Range.l], ABS[pLoc - l1Range.r]];
distToL2: DABasics.Number _ MIN[ABS[pLoc - l2Range.l], ABS[pLoc - l2Range.r]];
IF distToL1 < distToL2 THEN RETURN[[CONS[pin, pinListPair.list1], pinListPair.list2]]
ELSE RETURN[[pinListPair.list1, CONS[pin, pinListPair.list2]]]}}
ELSE RETURN[pinListPair]};

LinkSegsToPins: PROC [seg: RouteChannel.Segment, pinList: RouteChannel.ChanPinList, newPin: RouteChannel.ChanPin] = {

PinCompare: List.CompareProc = {
p1: DABasics.Number _ NARROW[ref1, RouteChannel.ChanPin].pinPosition.pLoc;
p2: DABasics.Number _ NARROW[ref2, RouteChannel.ChanPin].pinPosition.pLoc;
RETURN[IF p1 < p2 THEN Basics.Comparison.less
ELSE IF p1 = p2 THEN Basics.Comparison.equal
ELSE Basics.Comparison.greater]};

mungedPinList: List.LORA _ ConvertToLORA[pinList];
sortedPinList: List.LORA _ List.Sort[mungedPinList, PinCompare];
rightPin: RouteChannel.ChanPin _ NARROW[List.NthElement[sortedPinList, -1]];
leftPin: RouteChannel.ChanPin _ NARROW[List.NthElement[sortedPinList, 1]];

FOR pList: List.LORA -- RouteChannel.ChanPinList -- _ sortedPinList, pList.rest WHILE pList # NIL DO
chanPin: RouteChannel.ChanPin _ NARROW[pList.first];
IF chanPin = leftPin THEN {
{IF chanPin.conctSeg[chanRight] = NIL THEN chanPin.conctSeg[chanRight] _ seg
ELSE chanPin.altConctSeg[chanRight] _ seg};

seg.exteriorPins[chanLeft] _ chanPin}

ELSE IF chanPin = rightPin THEN {
{IF chanPin.conctSeg[chanLeft] = NIL THEN chanPin.conctSeg[chanLeft] _ seg
ELSE chanPin.altConctSeg[chanLeft] _ seg};

seg.exteriorPins[chanRight] _ chanPin}

ELSE {seg.interiorPins _ CONS[chanPin, seg.interiorPins];
SELECT chanPin.kindOfPin FROM
chanConnect, compPin => {
chanPin.conctSeg[chanRight] _ seg; chanPin.conctSeg[chanLeft] _ seg};
dogLeg => {
IF chanPin.conctSeg[chanRight] = NIL AND chanPin.conctSeg[chanLeft] = NIL THEN
{chanPin.conctSeg[chanRight] _ seg; chanPin.conctSeg[chanLeft] _ seg}
ELSE
{chanPin.altConctSeg[chanLeft] _ seg; chanPin.altConctSeg[chanRight] _ seg}};
exitPin => Route.Error[programmingError, "Exit pin not on end of segment"];
ENDCASE};
ENDLOOP};

AddSeg: PROC [chanPins: RouteChannel.RoutingChannelPins, density: RouteChannel.Density, r: RTBasic.Range, width: DABasics.Number] RETURNS [maxDensity: DABasics.Number _ 0] = {

IF density # NIL THEN
FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
pos: DABasics.Number _ chanPins.sides[index].pLoc;
thisDensity: DABasics.Number _ IF r.l <= pos AND pos <= r.r THEN density.values[index] + width
ELSE density.values[index];
maxDensity _ MAX[maxDensity, thisDensity];
ENDLOOP};

CompareResult: PROC [r1, r2: BreakResult] RETURNS [result: Basics.Comparison] = {

result _ Basics.CompareInt[r1.chainLength, r2.chainLength];
IF result # equal THEN RETURN;

result _ Basics.CompareInt[r1.numDogLegs, r2.numDogLegs];
IF result # equal THEN RETURN;

result _ Basics.CompareInt[r1.deltaDensity, r2.deltaDensity];
IF result # equal THEN RETURN;

result _ Basics.CompareInt[r1.duplicateLength, r2.duplicateLength];
RETURN};


ClosestPins: PROC [chanPins: RouteChannel.RoutingChannelPins, target: DABasics.Number] RETURNS [nextLower, nextHigher: RouteChannel.ZMPinsOnCh _ 0] = {

trial: RouteChannel.ZMPinsOnCh;
nextHigher _ chanPins.count;
nextLower _ 1;

WHILE ABS[nextHigher - nextLower] > 1 DO
trial _(nextHigher + nextLower)/2;
IF target < chanPins.sides[trial].pLoc THEN nextHigher _ trial
ELSE IF target > chanPins.sides[trial].pLoc THEN nextLower _ trial
ELSE nextLower _ nextHigher _ trial;
ENDLOOP};

GetPins: PROC [exitsSeparate: BOOLEAN, seg: RouteChannel.Segment] RETURNS [pinLists: ChanPinListSet _ [NIL, NIL, NIL, NIL]] = {

IncludePin: PROC [pin: RouteChannel.ChanPin] = {
IF pin.pinSide = chanBottom  THEN  pinLists.bottomList _ CONS[pin, pinLists.bottomList]
ELSE IF pin.pinSide = chanTop THEN pinLists.topList _ CONS[pin, pinLists.topList]
ELSE IF pin.kindOfPin = dogLeg THEN dogLegList _ CONS[pin, dogLegList]};

IncludeExit: PROC [pin: RouteChannel.ChanPin, chanSide: RouteChannel.ChanSide] = {
IF pin.kindOfPin = exitPin THEN
{SELECT exitsSeparate FROM
FALSE => {
result: ChanPinListPair _ AddToClosestList[[pinLists.bottomList, pinLists.topList], pin];
pinLists.bottomList _ result.list1;
pinLists.topList _ result.list2};
TRUE => {
IF pin.pinPosition.pLoc = leftPin.pinPosition.pLoc THEN pinLists.leftExit _ pin
ELSE pinLists.rightExit _ pin};
ENDCASE => Route.Error[programmingError, "Invalid Router."]};
};

dogLegList: RouteChannel.ChanPinList _ NIL;
leftPin: RouteChannel.ChanPin _ seg.exteriorPins[chanLeft];
rightPin: RouteChannel.ChanPin _ seg.exteriorPins[chanRight];
IncludePin[leftPin];
IncludePin[rightPin];
FOR list: RouteChannel.ChanPinList _ seg.interiorPins, list.rest WHILE list # NIL DO
IncludePin[list.first];
ENDLOOP;

IncludeExit[leftPin, chanLeft];
IncludeExit[rightPin, chanRight];

FOR list: RouteChannel.ChanPinList _ dogLegList, list.rest WHILE list # NIL DO
result: ChanPinListPair _ AddToClosestList[[pinLists.bottomList, pinLists.topList], list.first];
pinLists.bottomList _ result.list1;
pinLists.topList _ result.list2;
ENDLOOP;
};

SegRanges: PROC [chanPins: RouteChannel.RoutingChannelPins, pinLists: ChanPinListSet] RETURNS [rangeList: RangeWithDirList] = {

lr: RTBasic.Range _ RouteChannel.GetRange[pinLists.bottomList];
ur: RTBasic.Range _ RouteChannel.GetRange[pinLists.topList];
ce1: DABasics.Number _ chanPins.cEnd1;
ce2: DABasics.Number _ chanPins.cEnd2;
min: DABasics.Number _ MIN[lr.l, ur.l];
max: DABasics.Number _ MAX[lr.r, ur.r];
left: RangeWithDir _ IF ce1 < min THEN [[ce1, min], rightToLeft] ELSE [[ce1, ce1], rightToLeft]; 
right: RangeWithDir _ IF ce2 > max THEN [[max, ce2], leftToRight] ELSE [[ce2, ce2], leftToRight];

SELECT TRUE FROM
lr.r < lr.l OR ur.r < ur.l =>
rangeList _ LIST[RangeWithDir[[ce1, ce2], leftToRight]];

lr.r < ur.l =>
{gap: RangeWithDir _ [[lr.r, ur.l], leftToRight];
rangeList _ LIST[gap, [lr, rightToLeft], [ur, leftToRight], left, right]};

(lr.l <= ur.l AND ur.l <= lr.r) AND (ur.l <= lr.r AND lr.r <= ur.r) =>
{dual: RangeWithDir _ [[ur.l, lr.r], leftToRight];
ls: RangeWithDir _ [[lr.l, dual.range.l], rightToLeft];
rs: RangeWithDir _ [[dual.range.r, ur.r], leftToRight];
rangeList _ LIST[dual, ls, rs, left, right]};

(lr.l <= ur.l AND ur.l < lr.r) AND (lr.l <= ur.r AND ur.r <= lr.r) =>
{ls: RangeWithDir _ [[lr.l, ur.l], rightToLeft];
rs: RangeWithDir _ [[ur.r, lr.r], leftToRight];
rangeList _ LIST[[ur, leftToRight], ls, rs, left, right]};

(ur.l <= lr.l AND lr.l <= ur.r) AND (ur.l <= lr.r AND lr.r <= ur.r) =>
{ls: RangeWithDir _ [[ur.l, lr.l], rightToLeft];
rs: RangeWithDir _ [[lr.r, ur.r], leftToRight];
rangeList _ LIST[[lr, leftToRight], ls, rs, left, right]};

(ur.l <= lr.l AND lr.l <= ur.r) AND (lr.l <= ur.r AND ur.r <= lr.r) =>
{dual: RangeWithDir _ [[lr.l, ur.r], leftToRight];
ls: RangeWithDir _ [[ur.l, dual.range.l], rightToLeft];
rs: RangeWithDir _ [[dual.range.r, lr.r], leftToRight];
rangeList _ LIST[dual, ls, rs, left, right]};

ur.r < lr.l =>
{gap: RangeWithDir _ [[ur.r, lr.l], leftToRight];
rangeList _ LIST[gap, [lr, leftToRight], [ur, rightToLeft], left, right]};

ENDCASE => Route.Error[programmingError, "Not suppose to happen."]};

BreaksFound: PROCEDURE [break: FullSegBreakSpec] RETURNS [numBreaks: INT _ 0] = {

FOR lmr: Lmr IN Lmr DO
IF break.breaks[lmr] # NIL THEN numBreaks _ numBreaks + 1;
ENDLOOP};

ConvertToLORA: PROC [list: RouteChannel.ChanPinList] RETURNS[val: List.LORA] = {
val _ NIL;
UNTIL list = NIL DO
val _ CONS[list.first, val];
list _ list.rest;
ENDLOOP;
RETURN[val];
}; -- of ConvertToLORA


HackedBreakWithInRange: PROC [chanData: RouteChannel.ChannelData, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
seg: RouteChannel.Segment, 
range: RangeWithDir, 
pins: TestPins] 
RETURNS [break: SegBreakSpec _ NIL] = {

chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
minPinD2: DABasics.Number _ rules.branchWidth/2;
chainLength: INT;
notAllowed: BOOLEAN;

SELECT range.dir FROM
leftToRight => {
FOR pos: DABasics.Number _ range.range.l, pos + 4*11 WHILE pos <= range.range.r AND break = NIL DO
[notAllowed, chainLength] _ NewDogLegNotAllowed[chanData, parms, rules, seg, pos, pins];
IF ~notAllowed THEN
break _ NEW[SegBreakSpecRec _  [pos, dogLeg, chainLength]];
ENDLOOP};
rightToLeft => {
FOR pos: DABasics.Number _ range.range.r, pos- 4*11 WHILE pos >= range.range.l AND break = NIL DO
[notAllowed, chainLength] _ NewDogLegNotAllowed[chanData, parms, rules, seg, pos, pins];
IF ~notAllowed THEN
break _ NEW[SegBreakSpecRec _  [pos, dogLeg, chainLength]];
ENDLOOP};
ENDCASE};

NewDogLegNotAllowed: PROC [chanData: RouteChannel.ChannelData, 
parms: RoutePrivate.RoutingAreaParms, 
rules: Route.DesignRules, 
seg: RouteChannel.Segment, 
pos: DABasics.Number, 
pins: TestPins] 
RETURNS [notAllowed: BOOLEAN _ FALSE, chainLength: INT _ LAST[INT]] = {

FindConnectedNet : PROC [pin: RouteChannel.ChanPin] RETURNS [net: RoutePrivate.Net _ NIL] =
{IF pin # NIL THEN
{s1: RouteChannel.Segment _ pin.conctSeg[chanLeft];
s2: RouteChannel.Segment _ pin.conctSeg[chanRight];
IF s1 # NIL THEN net _ s1.net
ELSE IF s2 # NIL THEN net _ s2.net
ELSE Route.Error[programmingError, "Pin not connected to a segment."]}};

CheckInner: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
IF pin.kindOfPin = exitPin OR pin.kindOfPin = dogLeg THEN
IF Constraining[rules, pin, pins.trialPin] THEN quit _ TRUE};

OuterConstraints: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
IF pin.kindOfPin = chanConnect OR pin.kindOfPin = compPin THEN
IF Constraining[rules, pin, pins.trialPin] THEN quit _ TRUE};

chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
minLimit, maxLimit, leftIndex, rightIndex: RouteChannel.ZMPinsOnCh;
width: DABasics.Number _ MAX[seg.net.trunkWidth, seg.net.branchWidth];
graph: RouteDiGraph.Graph _ chanData.constraints;
pins.trialPin.pinPosition.pLoc _ pos;
pins.trialPin.pWidth _ width;
pins.leftExitPin.pWidth _ width;
pins.rightExitPin.pWidth _ width;
[leftIndex, rightIndex] _ ClosestPins[chanPins, pos];

IF Constraining[rules, pins.trialPin, pins.leftExitPin] THEN notAllowed _ TRUE;
IF Constraining[rules, pins.trialPin, pins.rightExitPin] THEN notAllowed _ TRUE;

[minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[chanPins, parms, rules, leftIndex, rightIndex, CheckInner];
FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pinPosition: RouteChannel.PinPosition _ chanPins.sides[index];
notAllowed _ RouteChannel.EnumPins[pinPosition, CheckInner];
ENDLOOP;
IF ~notAllowed THEN {
originalNode: RouteDiGraph.Node _ seg.constraintNode;
originalArcs: RouteDiGraph.ArcList _ RouteDiGraph.RemoveNode[graph, seg.constraintNode];
upperSeg: RouteChannel.Segment _ NEW[RouteChannel.SegmentRec _ [net: seg.net, qWidth: seg.qWidth, exitBreak: seg.exitBreak]];
upperConstraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [Rope.Cat[upperSeg.net.name, "-upperSegment"], upperSeg]];
newUpperConstraintNode: RouteDiGraph.Node _ RouteDiGraph.AddNewNode[graph, upperConstraint];
lowerSeg: RouteChannel.Segment _ NEW[RouteChannel.SegmentRec _ [net: seg.net, qWidth: seg.qWidth, exitBreak: seg.exitBreak]];
lowerConstraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [Rope.Cat[lowerSeg.net.name, "-lowerSegment"], lowerSeg]];
newLowerConstraintNode: RouteDiGraph.Node _ RouteDiGraph.AddNewNode[graph, lowerConstraint];
TransferConstraints[graph, originalArcs, originalNode, newUpperConstraintNode, newLowerConstraintNode];

[minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[chanPins, parms, rules, leftIndex, rightIndex, OuterConstraints];
FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pinPosition: RouteChannel.PinPosition _ chanPins.sides[index];
bottomPin: RouteChannel.ChanPin _ pinPosition.pins[chanBottom];
bottomNet: RoutePrivate.Net _ FindConnectedNet[bottomPin];
constrainBottom: BOOLEAN _ Constraining[rules, bottomPin, pins.trialPin];

IF constrainBottom THEN {
IF bottomNet = seg.net THEN notAllowed _ TRUE;  -- Don't let a dogleg constratin its own net
AddConstraintsToPin[graph, newLowerConstraintNode, bottomPin]};

FOR i: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pP: RouteChannel.PinPosition _ chanPins.sides[i];
topPin: RouteChannel.ChanPin _ pP.pins[chanTop];
topNet: RoutePrivate.Net _ FindConnectedNet[topPin];
constrainTop: BOOLEAN _ Constraining[rules, topPin, pins.trialPin];

IF constrainTop THEN {
IF  topNet = seg.net THEN notAllowed _ TRUE;  -- Don't let a dogleg constratin its own net
AddConstraintsFromPin[graph, topPin, newUpperConstraintNode]};

IF constrainBottom AND constrainTop THEN {
IF bottomNet = topNet THEN notAllowed _ TRUE;  -- Rule 1
};

ENDLOOP;
ENDLOOP;

IF ~RouteDiGraph.PathExists[graph, newUpperConstraintNode, newLowerConstraintNode] THEN
[] _ RouteDiGraph.AddNewArc[graph, NIL, newUpperConstraintNode, newLowerConstraintNode];
IF notAllowed OR SegsInCycle[graph, newLowerConstraintNode, newUpperConstraintNode] # NIL THEN notAllowed _ TRUE;
IF notAllowed OR SegsInCycle[graph, newUpperConstraintNode, newUpperConstraintNode] # NIL THEN notAllowed _ TRUE;
IF notAllowed OR SegsInCycle[graph, newLowerConstraintNode, newLowerConstraintNode] # NIL THEN notAllowed _ TRUE;

IF ~notAllowed THEN
chainLength _ UpperConstrainedNodes[graph, newUpperConstraintNode] + LowerConstrainedNodes[graph, newLowerConstraintNode];

[] _ RouteDiGraph.RemoveNode[graph, newUpperConstraintNode];
[] _ RouteDiGraph.RemoveNode[graph, newLowerConstraintNode];
RouteDiGraph.IncludeNode[graph, originalNode];
RouteDiGraph.IncludeArcs[graph, originalArcs]};
};

GetBreakSpec: PROC [break: FullSegBreakSpec] RETURNS [segBreak: SegBreakSpec _ NIL] ~ {
FOR lmr: Lmr IN Lmr DO
IF break.breaks[lmr] # NIL THEN segBreak _ break.breaks[lmr];
ENDLOOP;
};

GetLmr: PROC [break: FullSegBreakSpec] RETURNS [lmr: Lmr _ middle] ~ {
FOR where: Lmr IN Lmr DO
IF break.breaks[where] # NIL THEN lmr _ where;
ENDLOOP;
};

HackedDoBreak: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, fullSegBreak: FullSegBreakSpec] = {
UnlinkSegFromPins: RouteChannel.EachPinActionProc ~ {
IF pin.conctSeg[chanLeft] = oldSeg THEN pin.conctSeg[chanLeft] _ NIL;
IF pin.conctSeg[chanRight] = oldSeg THEN pin.conctSeg[chanRight] _ NIL;
IF pin.altConctSeg[chanLeft] = oldSeg THEN pin.altConctSeg[chanLeft] _ NIL;
IF pin.altConctSeg[chanRight] = oldSeg THEN pin.altConctSeg[chanRight] _ NIL;
};

chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
oldSeg: RouteChannel.Segment _ fullSegBreak.seg;
branchWidth: DABasics.Number _ oldSeg.net.branchWidth;
trunkWidth: DABasics.Number _ oldSeg.net.trunkWidth;
segBreak: SegBreakSpec _ GetBreakSpec[fullSegBreak];
lmr: Lmr _ GetLmr[fullSegBreak];
pinIndex: RouteChannel.ZMPinsOnCh _ RouteChannel.FindPinPos[chanPins, segBreak.pos];
pinPosition: RouteChannel.PinPosition _ chanPins.sides[pinIndex];
upperPin, lowerPin: RouteChannel.ChanPin _ NIL;
pinListPair: ChanPinListPair;
segRange: RTBasic.Range _ RouteChannel.SegRange[oldSeg];
seg1: RouteChannel.Segment _ NEW[RouteChannel.SegmentRec _ [net: oldSeg.net, qWidth: trunkWidth, exitBreak: oldSeg.exitBreak]];
seg2: RouteChannel.Segment _ NEW[RouteChannel.SegmentRec _ [net: oldSeg.net, qWidth: trunkWidth, exitBreak: oldSeg.exitBreak]];

IF (segRange.l < pinPosition.pLoc AND pinPosition.pLoc < segRange.r) OR segBreak.type = exit THEN {
[] _ RouteChannel.EnumPinsOnSeg[oldSeg, UnlinkSegFromPins];

SELECT segBreak.type FROM
dogLeg => {
exitsSeparate: BOOLEAN _ IF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet _ GetPins[exitsSeparate, oldSeg];
parms.widestPin _ MAX[branchWidth, parms.widestPin];
upperPin _ lowerPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: none, qLoc: 0, pWidth: rules.branchWidth, kindOfPin: dogLeg, pinPosition: pinPosition]];
pinPosition.innerPins _ CONS[upperPin, pinPosition.innerPins];
pinListPair _ DividePins[lmr, pinLists, lowerPin, upperPin]};

exit => {
pinSide: RouteChannel.ChanLRSide _
IF segBreak.pos <= chanPins.cEnd1 THEN chanLeft
ELSE IF segBreak.pos >= chanPins.cEnd2 THEN chanRight
ELSE Route.Error[programmingError, "Invalid data. Call maintainer."];
pinLists: ChanPinListSet _ GetPins[TRUE, oldSeg];
seg1.exitBreak _ TRUE; seg1.part _ 1;
seg2.exitBreak _ TRUE; seg2.part _ 2;
upperPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: pinSide, qLoc: 0, pWidth: 0, kindOfPin: exitPin, pinPosition: pinPosition]];
pinPosition.innerPins _ CONS[upperPin, pinPosition.innerPins];
lowerPin _ IF pinSide = chanRight THEN pinLists.rightExit ELSE pinLists.leftExit;
IF lowerPin = NIL THEN {
lowerPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: pinSide, qLoc: 0, pWidth: 0, kindOfPin: exitPin, pinPosition: pinPosition]];
pinPosition.innerPins _ CONS[lowerPin, pinPosition.innerPins]}
ELSE {
};
pinListPair _ DividePins[lmr, pinLists, lowerPin, upperPin]};
ENDCASE;

LinkSegsToPins[seg1, pinListPair.list1, lowerPin];
LinkSegsToPins[seg2, pinListPair.list2, upperPin];
SetTrackConstraints[seg1, oldSeg.trackConstraint];
SetTrackConstraints[seg2, oldSeg.trackConstraint];

TerminalIO.PutRope[Rope.Cat["\ntrunk segment for net: ", fullSegBreak.seg.net.name, ]];
TerminalIO.PutF1[" divided at: %g", IO.int[chanPins.sides[pinIndex].pLoc/8]];
}

ELSE { -- replace all segments for net with one segment
net: RoutePrivate.Net _ oldSeg.net; 
pinLists: ChanPinListSet _ GetPinsOnNet[chanPins, net];
parms.widestPin _ MAX[rules.branchWidth, parms.widestPin];
upperPin _ lowerPin _ NEW[RouteChannel.ChanPinRec _ [pinSide: none, qLoc: 0, pWidth: rules.branchWidth, kindOfPin: dogLeg, pinPosition: pinPosition]];
pinPosition.innerPins _ CONS[upperPin, pinPosition.innerPins];
pinListPair _ DividePins[middle, pinLists, lowerPin, upperPin];

UnlinkPinsOnNet[chanPins, net]; -- unlink the old segments

LinkSegsToPins[seg1, pinListPair.list1, lowerPin];
LinkSegsToPins[seg2, pinListPair.list2, upperPin];
SetTrackConstraints[seg1, oldSeg.trackConstraint];
SetTrackConstraints[seg2, oldSeg.trackConstraint];

TerminalIO.PutRope[Rope.Cat["\ntrunk segment divided for net: ", fullSegBreak.seg.net.name ]];
TerminalIO.PutF1[" dogleg at: %g", IO.int[chanPins.sides[pinIndex].pLoc/8]];
};

RouteChannel.AuditPins[chanPins]
};

GetPinsOnNet: PROC [chanPins: RouteChannel.RoutingChannelPins, net: RoutePrivate.Net] RETURNS [pinLists: ChanPinListSet_ [NIL, NIL, NIL, NIL]] ~ {


EachPinPosition: RouteChannel.EachPinPositionActionProc ~ {

EachPin: RouteChannel.EachPinActionProc ~ {

IF OnNet[net, pin] THEN {
SELECT pin.pinSide FROM
chanBottom => pinLists.bottomList _ CONS[pin, pinLists.bottomList];
chanTop => pinLists.topList _ CONS[pin, pinLists.topList];
chanLeft => leftPin _ pin;
chanRight => rightPin _ pin;
ENDCASE => Route.Error[programmingError, "Invalid pin on net."];
}
};

[] _ RouteChannel.EnumPins[pinPosition, EachPin]};

leftPin, rightPin: RouteChannel.ChanPin;
[] _ RouteChannel.EnumPinPositions[chanPins, EachPinPosition];
IF leftPin # NIL THEN {
result: ChanPinListPair _ AddToClosestList[[pinLists.bottomList, pinLists.topList], leftPin];
pinLists.bottomList _ result.list1;
pinLists.topList _ result.list2};
IF rightPin # NIL THEN {
result: ChanPinListPair _ AddToClosestList[[pinLists.bottomList, pinLists.topList], rightPin];
pinLists.bottomList _ result.list1;
pinLists.topList _ result.list2};
};

UnlinkPinsOnNet: PROC [chanPins: RouteChannel.RoutingChannelPins, net: RoutePrivate.Net] ~ {


EachPinPosition: RouteChannel.EachPinPositionActionProc ~ {

EachPin: RouteChannel.EachPinActionProc ~ {

IF OnNet[net, pin] THEN {
pin.conctSeg[chanLeft] _ NIL;
pin.conctSeg[chanRight] _ NIL;
pin.altConctSeg[chanLeft] _ NIL;
pin.altConctSeg[chanRight] _ NIL;
}};

[] _ RouteChannel.EnumPins[pinPosition, EachPin]};

[] _ RouteChannel.EnumPinPositions[chanPins, EachPinPosition]};

OnNet: PROC [net: RoutePrivate.Net, pin: RouteChannel.ChanPin] RETURNS [onNet: BOOLEAN _ FALSE] ~ {

IF pin # NIL THEN {
IF pin.conctSeg[chanLeft] # NIL AND pin.conctSeg[chanLeft].net = net THEN onNet _ TRUE;
IF pin.conctSeg[chanRight] # NIL AND pin.conctSeg[chanRight].net = net THEN onNet _ TRUE;
IF pin.altConctSeg[chanLeft] # NIL AND pin.altConctSeg[chanLeft].net = net THEN onNet _ TRUE;
IF pin.altConctSeg[chanRight] # NIL AND pin.altConctSeg[chanRight].net = net THEN onNet _ TRUE;
}};

CycleFromPins: PROC [chanData: RouteChannel.ChannelData, lowerPin, upperPin: RouteChannel.ChanPin] RETURNS [cycleExists: BOOLEAN _ FALSE] ~ {

graph: RouteDiGraph.Graph _ chanData.constraints;
FOR lowerSegIndex: RouteChannel.ChanLRSide IN [chanLeft .. chanRight] WHILE ~cycleExists DO
FOR upperSegIndex: RouteChannel.ChanLRSide IN [chanLeft .. chanRight] WHILE ~cycleExists DO
IF lowerPin # NIL AND upperPin # NIL THEN {
lowerSeg: RouteChannel.Segment _ lowerPin.conctSeg[lowerSegIndex];
upperSeg: RouteChannel.Segment _ upperPin.conctSeg[upperSegIndex];
IF lowerSeg # NIL AND upperSeg # NIL AND lowerSeg # upperSeg THEN
IF ~lowerSeg.net.num # upperSeg.net.num THEN {
lowerNode: RouteDiGraph.Node _ lowerSeg.constraintNode;
upperNode: RouteDiGraph.Node _ upperSeg.constraintNode;
IF SegsInCycle[graph, lowerNode, upperNode] # NIL THEN cycleExists _ TRUE}};
ENDLOOP; -- FOR upperSegIndex
ENDLOOP; -- FOR lowerSegIndex
};

HackedDoConstraint: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, lowerSeg, upperSeg: RouteChannel.Segment, whichEnd: Lmr, pins: TestPins] RETURNS [segBroken: BOOLEAN _ FALSE] = {

IF lowerSeg # NIL AND upperSeg # NIL AND lowerSeg # upperSeg THEN
IF ~lowerSeg.failed AND ~upperSeg.failed AND lowerSeg.net.num # upperSeg.net.num THEN {
segList: RouteChannel.SegmentList;
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
graph: RouteDiGraph.Graph _ chanData.constraints;
lowerNode: RouteDiGraph.Node _ lowerSeg.constraintNode;
upperNode: RouteDiGraph.Node _ upperSeg.constraintNode;
IF lowerNode = NIL THEN
{constraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [lowerSeg.net.name, lowerSeg]];
lowerNode _ RouteDiGraph.AddNewNode[graph, constraint];
lowerSeg.constraintNode _ lowerNode};
IF upperNode = NIL THEN
{constraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [upperSeg.net.name, upperSeg]];
upperNode _ RouteDiGraph.AddNewNode[graph, constraint];
upperSeg.constraintNode _ upperNode};

segList _ SegsInCycle[graph, lowerNode, upperNode];
IF segList # NIL THEN {
dummy: RouteDiGraph.Arc _ RouteDiGraph.AddNewArc[graph, NIL, upperNode, lowerNode];
density: RouteChannel.Density _ RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec _ FindBreak[chanData, parms, rules, segList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN HackedDoBreak[chanData, parms, rules, segBreak]
ELSE {  -- choose a victim --
segList.first.failed _ TRUE;
Route.Signal[noResource, Rope.Cat["net: ", segList.first.net.name, " failed, unable to find a place to dogleg"]]};

segBroken _ TRUE}
ELSE { -- add a segment constraint

IF ~RouteDiGraph.PathExists[graph, upperNode, lowerNode] THEN
[] _ RouteDiGraph.AddNewArc[graph, NIL, upperNode, lowerNode]}}};

AddConstraintsToPin: PROC [graph: RouteDiGraph.Graph, constraintNode: RouteDiGraph.Node, pin: RouteChannel.ChanPin] ~ {
segList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[pin];
FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO
lowerNode: RouteDiGraph.Node _ segs.first.constraintNode;
IF lowerNode = NIL THEN {
constraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [segs.first.net.name, segs.first]];
lowerNode _ RouteDiGraph.AddNewNode[graph, constraint];
segs.first.constraintNode _ lowerNode};
IF ~RouteDiGraph.PathExists[graph, constraintNode, lowerNode] THEN
[] _ RouteDiGraph.AddNewArc[graph, NIL, constraintNode, lowerNode];
ENDLOOP;
};

AddConstraintsFromPin: PROC [graph: RouteDiGraph.Graph, pin: RouteChannel.ChanPin, constraintNode: RouteDiGraph.Node] ~ {
segList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[pin];
FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO
upperNode: RouteDiGraph.Node _ segs.first.constraintNode;
IF upperNode = NIL THEN {
constraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [segs.first.net.name, segs.first]];
upperNode _ RouteDiGraph.AddNewNode[graph, constraint];
segs.first.constraintNode _ upperNode};

IF ~RouteDiGraph.PathExists[graph, upperNode, constraintNode] THEN
[] _ RouteDiGraph.AddNewArc[graph, NIL, upperNode, constraintNode];
ENDLOOP;
};

TransferConstraints: PROC [graph: RouteDiGraph.Graph, originalArcs: RouteDiGraph.ArcList, originalNode, newUpperConstraintNode, newLowerConstraintNode: RouteDiGraph.Node] ~ {
FOR aList: RouteDiGraph.ArcList _ originalArcs, aList.rest WHILE aList # NIL DO
arc: RouteDiGraph.Arc _ NARROW[aList.first];
IF arc.superiorNode = originalNode THEN [] _ RouteDiGraph.AddNewArc[graph, NIL, newUpperConstraintNode, arc.inferiorNode]
ELSE IF arc.inferiorNode = originalNode THEN [] _ RouteDiGraph.AddNewArc[graph, NIL, arc.superiorNode, newLowerConstraintNode]
ELSE Route.Error;
ENDLOOP;
};

LowerConstrainedNodes: PROCEDURE[graph: RouteDiGraph.Graph, node: RouteDiGraph.Node]
RETURNS [constrainedNodes: INT _ 0] = {

ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
IF ~List.Memb[arc.inferiorNode, visitedNodes] THEN {
visitedNodes _ CONS[arc.inferiorNode, visitedNodes];
constrainedNodes _ constrainedNodes + 1;
quit _ RouteDiGraph.EnumArcsFromNode[graph, arc.inferiorNode, in, ArcProc]}};

visitedNodes: RouteDiGraph.NodeList _ NIL;
[] _ RouteDiGraph.EnumArcsFromNode[graph, node, in, ArcProc]};

UpperConstrainedNodes: PROCEDURE[graph: RouteDiGraph.Graph, node: RouteDiGraph.Node]
RETURNS [constrainedNodes: INT _ 0] = {

ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
IF ~List.Memb[arc.superiorNode, visitedNodes] THEN {
visitedNodes _ CONS[arc.superiorNode, visitedNodes];
constrainedNodes _ constrainedNodes + 1;
quit _ RouteDiGraph.EnumArcsFromNode[graph, arc.superiorNode, out, ArcProc]}};

visitedNodes: RouteDiGraph.NodeList _ NIL;
[] _ RouteDiGraph.EnumArcsFromNode[graph, node, out, ArcProc]};

}.
nRouteChannelConstraintsImpl.mesa   
Copyright Ó 1985, 1986, 1987, 1989 by Xerox Corporation.  All rights reserved.
by Bryan Preas   July 10, 1985 6:57:00 pm PDT 
last edited by Bryan Preas   July 16, 1987 8:36:23 pm PDT
Christian Le Cocq January 11, 1988 12:45:14 pm PST
Altered version for improved dogleg routes

run through the pins on the channel,
create segment constraints from the pin to pin relationships

return if no pins
outer loop can be removed whe constraints by seg is added
generate constraints for this coordinate, if any

now do constraints for doglegs and exits wrt the upper pins

first the upper pin, if any
do the exits wrt each other if this is a switchBox and a channel end
process pin to pin constraints
break any segments that must be in 2 tracks
Must resolve constraints accross the ends of the switchbox.  If there is a constraint from a segment on one end to a segment on the other, it must be resolved.
these are the pins on the left side of the channel
these are the segments on the left pin
choose a segment to break and the position to dogleg
choose a segment to break and the position to dogleg
next check if the external segments are in the same track, they overlap, and they are in different nets
choose a segment to break and the position to dogleg
must explicitly destroy the old data
add a segment constraint if it does not create a loop
do upper to lower pin constraint
generate pin to pin constraints, process all segments attached to these pins
determining if pin1 actually constrains pin2
add a segment constraint if it does not create a loop
choose a segment to break and the position to dogleg
need to change so I don't add duplicate constraints
constrain Upper above Lower
arcName: Rope.ROPE _ Rope.Cat[upperSeg.net.name,"-above-", lowerSeg.net.name];
recursively go through the constraints
print segments on list
decide on which segment to divide and the position
run through the segs in the cycle. find the best
-- try breaks at ALL places as an experiment
IF BreaksFound[break] > 0 THEN HackedDoBreak[chanData, parms, rules, break];
find the best position to break this seg
returns TRUE if seg has a dogleg
PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN _ FALSE];
find the best position to break this seg within this range
minPinD2: DABasics.Number _ RouteUtil.GetWidthWithContact[routingArea, routingArea.rules.branchWidth]/2;
see if a dogleg is allowed here
must reserve place for future exits
see if inner pins interfere
see if there are existing dog legs

see if outer pins interfere
see if any nets within th range cross the channels
see if a constraint loop is created
later --  for now dont use pin positions that could cause constraint loops
find the best exit to break this seg
evaluate the break of ths seg at break
break the segment at position:
add pin position at fullSegBreak.breaks[mumble].pos
unlink segBreak
create 2 new segments
link in the pins

if this segment already has an exit on this side, then use that one, otherwise make a new pin

remove these statments for production
link the segment to the pin in the list and vice versa
update old seg pointer
IF chanPin # newPin THEN {chanPin.conctSeg[chanRight] _ seg}
chanPin.conctSeg[chanLeft] _ NIL
ELSE
no old seg pointer, but make sure both segs on new pin are initialized
{IF chanPin.conctSeg[chanRight] = NIL THEN chanPin.conctSeg[chanRight] _ seg
ELSE chanPin.altConctSeg[chanRight] _ seg};
BTP August 1, 1988 6:37:29 pm PDT
update old seg pointer
IF chanPin # newPin THEN
{chanPin.conctSeg[chanLeft] _ seg; -- chanPin.conctSeg[chanRight] _ NIL -- }
ELSE
no old seg pointer, but make sure both segs on new pin are initialized
{IF chanPin.conctSeg[chanLeft] = NIL THEN chanPin.conctSeg[chanLeft] _ seg
ELSE chanPin.altConctSeg[chanLeft] _ seg};
BTP August 1, 1988 6:37:29 pm PDT
compute the track density when this range is added
compare r1 and r2
find the PinPosition closest to target.
get the pins attached to the segment on the indicated side
bottomList == lowerPinList and topList == upperPinList
Compiler problem: [pinLists.bottomList, pinLists.topList] _ AddToClosestList[[pinLists.bottomList, pinLists.topList], pin]};
first include the obvious pins: top, bottom and dogleg
next decide which segments the exit pins go in
next decide which segments the dogleg pins go in
Compiler problem: [pinLists.bottomList, pinLists.topList] _ AddToClosestList[[pinLists.bottomList, pinLists.topList], list.first];
find distinct ranges for this seg, use enumeration
-- ur:                   
-- lr:  
-- ur:          
-- lr:   
-- ur:      
lr:    
ur:    
-- lr:       
-- ur:    
-- lr:         
-- ur:    
-- lr:                         
Code for improved dogleg routes.  Should be made permenent or deleted
BTP April 18, 1989 11:32:59 am PDT
this code taken from this module or from RouteChannelInitImpl.mesa
find the best position to break this seg within this range
Special for DDE: don't try dogleg positions between pins positions
BTP: April 17, 1989 3:27:49 pm PDT
minPinD2: DABasics.Number _ RouteUtil.GetWidthWithContact[routingArea, routingArea.rules.branchWidth]/2;

BTP April 13, 1989 3:18:33 pm PDT
Implements dogleg rules in ICCAD paper

see if a dogleg is allowed here
must reserve place for future exits (Rule 0: unstated, but obvious)
see if inner pins interfere (Rule 2)
see if there are existing dog legs

-- see if this dogleg position participates in a cycle
see if outer pins can cross the channel
add constraints for new trial segments
Check if bottom and top pins constrain each other (Rule 1)
Check if bottom and top pins belong to the same net (Rule 3)
see if any nets within the range cross the channels
add constraints for new trial segments
check Rule 3
put things back the way they were
extract the break spec for the full break
extract the Lmr spec for the full break
break the segment at position:
add pin position at fullSegBreak.breaks[mumble].pos
unlink segBreak
create 2 new segments
link in the pins

break this one segment
if this segment already has an exit on this side, then use that one, otherwise make a new pin
remove this statment for production
get the pins attached to the net on the indicated side
bottomList == lowerPinList and topList == upperPinList
this is a heavy duty way to perform this action;  needs to be improved
PROC[pinPosition: PinPosition, pinIndex: MPinsOnCh] RETURNS [quit: BOOLEAN _ FALSE];
PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN _ FALSE];
Unlink the old segments for Garbage collection
PROC[pinPosition: PinPosition, pinIndex: MPinsOnCh] RETURNS [quit: BOOLEAN _ FALSE];
PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN _ FALSE];
Returns TRUE if pin is connected to net
add a segment constraint if it does not create a loop
choose a segment to break and the position to dogleg

add constraint that caused this
constrain Upper above Lower
arcName: Rope.ROPE _ Rope.Cat[upperSeg.net.name,"-above-", lowerSeg.net.name];
add constraints from the constraint node to the segments on the pin
add constraints from the constraint node to the segments on the pin
transfer constraints from removed arcs to new nodes
recursively go through the constraints
PROC[graph: Graph, arc: Arc, node: Node, direction: Direction] RETURNS [quit: BOOLEAN _ FALSE];
recursively go through the constraints
PROC[graph: Graph, arc: Arc, node: Node, direction: Direction] RETURNS [quit: BOOLEAN _ FALSE];
�Ê6˜
codeš
œ#™#Kš
œN™NKšœ*Ïkœ
™.Kšœ6�™9K™2K™*K™—š
�	˜	Kšœ�œ�œX˜vK˜—šÐlnœ�œ
�˜*Kš�œ�œI˜aKš�œ˜K˜Kšœ�œÏc ˜EKšœ�œ�œ˜)šœ�œ�œ˜ Kš
œ˜Kš
œ˜Kšœ
�œ˜—Kšœ�œ˜"šœ�œ�œ˜!Kšœ�œ
˜Kš	œ�œ�œ�œ
�œ˜.K˜—šœ
�œ�œ˜Kš
œ˜Kš
œ!˜!Kš
œ˜Kš
œ˜K˜—Kšœ�œ�œ
�œ˜.šœ�œ�œ˜Kš
œ˜Kš
œ"˜"K˜—šœ�œ�œ˜Kšœ,�œ
˜0Kšœ0�œ˜5K˜—šœ�œ�œ˜ Kšœ)�œ˜.K˜—Kšœ
�œ�œ
˜!šœ
�œ�œ˜Kšœ<�œ˜A—K˜—šÏnœ�œ%˜FKš
œ&˜&Kš
œ˜Kš
œ%˜%Kš�œ�œ˜#Kš
œ$™$Kš
œ<™<K™Kš
œ™Kš
œ>˜>Kšœ�œ˜.Kšœ�œ�œ
˜Kšœ-�œ7˜gKšœ!�œr˜–
Kšœ-�œD˜tKšœ$�œs˜š
Kšœ.�œD˜uKšœ%�œt˜œ
Kšœ�œ6˜JKš�œ�œ
�œ
�œ˜)K˜š�œ�˜Kš
œ9™9Kšœ�œ
˜Kš�œ�œ
�œ"Ÿ˜[Kš
œ;˜;K˜š�œ�œ�˜=K˜š 
œ$˜1š�œ�œ
�˜Kšœ�œC˜T—K˜—š 	œ$˜-š�œ�œ
�˜Kš
œM˜MKš
œ/˜/š�œ�˜Kšœ�˜—š�œ
�œ�˜Kš
œ@˜@—š�œ
Ÿ˜Kš
œC˜C——K˜—Kš
œ>˜>Kš
œ=˜=Kš
œ)˜)Kš
œY˜YKš
œ+˜+K˜Kš
œ0™0Kš
œ7˜7Kš
œj˜jš�œ$�œ�˜CKš
œH˜HKš
œ@˜@Kš
œC˜CK˜Kš�œM�œ
�œ	˜aK™Kš
œ;™;š�œM�œ
�œ
�˜hKš
œ1˜1K™Kš
œ™Kš�œN�œ
�œ	˜bKš�œN�œ
�œ	˜bKš�œŸ˜—š�œŸ˜K˜——Kš
œD™Dš�œ�œ�œ�œ˜KK˜š œ˜!Kšœ�œ"˜>Kšœ�œ"˜>š�œ
�œ	�œ˜-Kš�œ
�œ	�œ˜,Kš�œ˜!——K˜Kšœ�œ�œ�œ˜2Kšœ�œ(˜@Kšœ�œ)˜Aš�œ
�œ
Ÿœ�œ	�œ
�˜dKšœ!�œ˜5Kš
œF˜FK˜Kš
œ™š�œ�œ
�œ˜Kšœ!�œ˜:Kš�œP�œ
�œ
˜e—K˜Kš
œ+™+š�œ3�œ�œ
�˜IKš
œ'˜'š
�œ�œ�œ.�œ
�œ˜�
KšœC�œ˜Xš�œ�œ˜ Kšœ!�œ	˜.—š�œŸ˜ Kšœ
�œ
˜Kš
œk˜k——š�œ�œ˜ Kš
œŸ
™Ÿ
Kš
œ>˜>Kš
œB˜BKš
œ2™2š�œ=�œ
�œ
�˜UKšœ �œ˜5Kš
œF˜FKš
œ&™&š�œ6�œ	�œ
�˜MKš
œ1˜1Kš
œ,˜,Kš
œ8˜8Kš
œ5˜5Kš
œ]˜]Kš
œ-˜-š�œ�œ
�˜ Kš
œ4™4Kš
œN˜NKš
œl˜lKš�œ�œ#˜Dš�œŸ˜Kšœ�œ
˜Kš
œr˜r—K˜Kšœ�œ�œ
˜ —Kš
œC˜Cš�œ�œ
�˜ Kš
œ4™4Kš
œN˜NKš
œl˜lKš�œ�œ#˜Dš�œŸ˜Kšœ�œ
˜Kš
œr˜r—K˜Kšœ�œ�œ
˜ —Kš
œg™gš�œ/�œN�œ�˜ 
Kš
œ4™4Kš
œN˜NKšœ?�œ)˜lKš�œ�œ#˜Dš�œŸ˜Kšœ
�œ
˜Kš
œj˜j—K˜Kšœ�œ�œ
˜ —Kš�œ
˜—Kš�œ
˜—Kš
œ˜—Kš�œ
˜—Kš�œ˜	——Kš�œ�œ
˜#Kš�œŸ˜—Kš�œŸ˜—š�œ
�œŸ˜%K˜——š œ�œ
�œ)˜KKš
œ$™$K˜Kš
œ>˜>Kš œ �œ˜2K˜Kš 
œ�œ˜.K˜š œ˜*Kšœ+�œ˜AKšœ�œ˜—K˜š œ$˜4Kš
œ7˜7Kš
œ9˜9Kš�œ�œ
�œ�œ
˜3Kš�œ�œ
�œ�œ˜6K˜—š�œ�œ�˜=Kš
œ>˜>Kš
œ:˜:Kš�œ
˜—K˜Kš
œX˜XK˜—š
 œ�œ®
�œ
�œ�œ˜ï
Kš
œ5™5K˜Kš
œ ™ š	�œ�œ
�œ�œ
�˜)š�œ�œ�˜Bš�œ�œ�œ�œ�œ�˜ 
š�œ)�˜/Kš
œL™Lš�œ(�œ�œ�˜Yš�œ(�œ�œ�˜YKš
œB˜BKš
œB˜BKš
œH˜HKš
œH˜HKš�œP�œ
�œ
˜hKš�œS�œ
�œ
˜kKš�œS�œ
�œ
˜kKš�œV�œ
�œ
˜nKš�œŸ˜—Kš�œŸ˜————Kš
œ˜K˜——š
 œ�œ>�œ�œ�œ˜{K™,K˜š	�œ�œ
�œ�œ
�˜!Kš
œ-˜-Kš
œR˜RKš
œ$˜$Kš
œ,˜,Kš
œR˜RKš
œ$˜$š�œ	�˜Kšœ�˜—š�œ
�œ	�˜š
œ@˜@Kš�œ2˜4——š�œ
Ÿ
˜š
œ@˜@Kš�œ5˜7———K˜—š
 œ�œ®
�œ
�œ�œ˜é
Kš
œ5™5K˜š�œ�œ
�œ�œ
�œ�˜Aš�œ�œ�œ%�œ˜WK˜"Kš
œ>˜>Kš
œ1˜1Kš
œ7˜7Kš
œ7˜7š�œ
�œ
�˜Kšœ.�œD˜uKš
œ7˜7Kš
œ%˜%—š�œ
�œ
�˜Kšœ.�œD˜uKš
œ7˜7Kš
œ%˜%K˜—Kš
œ3˜3š�œ�œ
�˜Kš
œ4™4Kš
œM˜MKš
œa˜aKš�œ�œ#˜Dš�œŸ˜Kšœ�œ
˜Kš
œr˜rK˜—Kšœ�œ
˜—š�œŸ˜"K˜Kš
œ3™3Kš
œ™š�œ7�˜=Kšœ�œ<™NKšœ#�œ˜A————K˜—š œ�	œD˜ZKš�œ&�œ˜5K˜Kš
œ&™&š œ'˜.Kš	œ�œ;�œ�œ�œ˜bš�œ�˜$Kšœ,�œ˜GKšœ
�œ˜*Kšœ�œ
˜—š�œ˜š�œ,�˜4Kšœ�œ!˜4Kš
œM˜M——š�œ�˜Kšœ,�œ˜BKšœ
�œ˜,—K˜—Kšœ%�œ
˜)Kš
œC˜CK˜—š 	œ�œ˜Kš
œ&˜&Kš
œ™K˜š�œ5�œ�œ
�˜KKš
œ'˜'K˜2Kšœ5�œ�œ�œ�œ�œ˜”
Kš�œ˜	—K˜—š 	œ�œ&˜5Kš
œ&˜&Kš
œ˜Kš
œ#˜#Kš
œ˜Kš
œ˜Kšœ�œ!�œ�œ�œ�œ˜RKš
œ2™2K˜Kš
œ>˜>Kšœ�œ
�œ�œ
�œ�œ
�œ�œ
�œ˜GK˜Kš
œ0™0Kš
œ,˜,š�œ5�œ�œ
�˜KKš
œ'˜'Kš
œ\˜\Kš
œA˜AK˜2Kšœ5�œ�œ�œ�œ�œ˜”
Kš	œ_�œ�œ�œ�œ˜Ó
K™,Kš�œ�œ.™Lš�œ*�˜0Kš
œ)˜)—Kš�œ
˜K˜—Kš�œ�œ
�œ
�œ�œ�œ�œ�œ˜<K˜—š œ�œ&˜7Kš
œ&˜&Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš�œ˜%K™(K˜Kš
œ>˜>Kš
œ�œ�œ�œ
�œ
�œ
�œ
˜LKš
œ7˜7Kš
œ<˜<Kšœ�œ�œ�œ˜K˜š�œ�œ˜š�œ�˜˜š�œ3�œ
�œ
�˜KKš
œ_˜_Kš�œ�œ
�œ
�œ
˜(Kš�œ
˜K˜—š�œ�œ
�œ�˜6Kš
œC˜CK˜——˜š œ�œ˜š�œ�œ�œ�œ˜3š�œ3�œ
�œ
�˜KKš
œY˜YKš�œ�œ
�œ
�œ
˜(Kš
�˜—Kš
œ˜—Kš
œ˜—K˜š œ�œ˜š�œ�œ�œ�œ	�œ�œ˜FKš
œ8˜8Kš
œT˜TKš
œ˜—Kš
œ˜K˜—š œ�œ˜š�œ�œ�œ�œ	�œ�œ˜FKš
œ9˜9Kš
œV˜VKš
œ˜—Kš
œ˜K˜—Kš
œ(˜(Kš
œ(˜(Kšœ�œ
˜"Kš
œ:˜:K˜š�œ
�œ
�˜Kš
œ/˜/Kš
œ0˜0Kš
œ7˜7Kš�œ!˜(—K˜—Kš�œ?˜FKš
œ˜——K˜—š
 	œ�œ�œ
�œ�œ˜TK˜Jšœ�œ™ K˜š œ$˜+Kš�œ)�œ�œ�œ™MK˜Kš�œ�œ�œ˜-K˜—Kš
œ6˜6K˜—š œ�œ&˜<Kš
œ&˜&Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš�œ�œ˜'K™:K˜š 
œ$˜1š�œ�œ
�˜Kšœ�œC˜T—K˜—š œ�œ%�œ˜Zš�œ�˜Kš
œ@˜@—š�œ
�œ�˜)Kšœ�œ
�œ
˜—š�œ˜Kš
œA˜AKš
œ˜Kš
œ7˜7Kš
œ{˜{K˜——š 
œ�œ%�œ˜Yš�œ�˜Kšœ�œ
�œ
˜—š�œ
�œ�˜&Kš
œ@˜@—š�œ˜Kš
œA˜AKš
œ˜Kš
œ7˜7Kš
œ{˜{——K˜Kš
œh™hKš
œ>˜>Kš
œ0˜0Kš
œ˜K˜š�œ�˜š
œ˜Kš
œT˜Tš
œK˜KKšœ�œ-˜8—š	�œM�œ�œ	�œ
�˜}š
œA˜AKšœ�œ#˜.—Kšœ�œ"˜1Kš�œ˜	——š
œ˜Kš
œV˜Vš
œK˜KKšœ�œ-˜8—š	�œM�œ�œ	�œ
�˜}š�œ;�˜AKšœ�œ#˜.—Kšœ
�œ˜$Kš�œ˜	——Kš�œ˜	—K˜—š œ�œ-˜CKš
œ&˜&Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš�œ�œ�œ˜)K™K˜š œ�œ�œ�œ˜Zšœ
�œ�œ
�˜Kš
œ3˜3Kš
œ3˜3Kš�œ�œ
�œ
˜Kš�œ
�œ�œ
�œ
˜"Kš�œD˜H—K˜—š 
œ$˜.š�œ�œ
�˜š�œ�œ�˜9Kš�œ)�œ�œ˜=—K˜——š œ$˜4š�œ�œ
�˜š�œ�œ�˜>š�œ)�œ�œ˜=K˜————Kš
œC˜CKšœ�œ*˜FKš
œ%˜%Kš
œ˜Kš
œ ˜ Kš
œ!˜!Kš
œ5˜5K˜Kš
œ#™#Kš�œ6�œ�œ
˜OKš�œ7�œ�œ
˜PK˜K™Kš
œt˜tš�œ�œ�œ
�˜PKš
œ"™"Kš
œ>˜>Kš
œ<˜<Kš�œ
˜—K™K™Kš
œz˜zš�œ�œ�œ
�˜PKš
œ>˜>Kš
œ?˜?Kš
œ9˜9Kš
œ:˜:Kš
œ4˜4Kšœ�œ.˜CKšœ�œ1˜IK˜Kš
œ2™2š�œ�œ�œ
�˜LKš
œ1˜1Kš
œ/˜/Kš
œ,˜,Kš
œ,˜,Kš
œ,˜,Kš�œ�œ!�œ�œ�œ�œ
˜rKš�œ
�œ$�œ�œ�œ�œ
˜rKš�œ
˜—K˜Kš
œ#™#KšœŸD™JKš�œ�œ�œ�œ
˜:Kš�œ˜	—K˜—š œ�œ�
�œ˜¿
K™$K˜Kšœ�œ+˜HKšœ4�œ�œ˜?Kšœ�œ+˜IKšœ*�œ�œ˜AKš
œM˜MKš
œO˜OKš�œ/�œ
�œ˜HKš�œ
�œ˜K˜—š 	œ�œ‹
�œ˜»
K™&K˜Kš
œ˜Kš
œ/˜/Kš
œ�œ�œ�œ
�œ
�œ
�œ
˜LKš
œ=˜=Kšœ�œ�œ
�œ˜Kš�œ�œ
�œ�œ
�œ�œ
�œ�œ
�œ�œ
�œ˜TK˜š�œ�œ
�œ˜%Kš
œ|˜|Kš
œy˜yKš
œ2˜2Kš�œ�œ=˜ZKš
œ)˜)—Kš�œ˜K˜Kš
œB˜BKš
œ6˜6Kš
œ/˜/Kš
œ˜Kš
œ˜š�œ
�œ�˜Kš�œ�œ
�œ+˜JKš�œ˜	—K˜—š œ�œo˜|š
œ™Kš
œ3™3Kš
œ™Kš
œ™Kš
œ™K™—š œ$˜5Kš�œ!�œ�œ
˜EKš�œ"�œ�œ
˜GKš�œ$�œ�œ
˜KKš�œ%�œ�œ
˜MKš
œ˜K˜—Kš
œ>˜>Kš
œ0˜0Kš
œ6˜6Kš
œ4˜4š�œ �˜&Kš
œ7˜7—Kš
œ;˜;K˜š�œ
�œ�˜Kš
œ2˜2š�œ�œ
�œ˜Kš
œT˜TKš
œA˜AKšœ+�œ
˜/Kš
œ˜Kšœ�œ_˜Kšœ�œ_˜K˜š�œ�˜˜Kš
œ�œ�œ�œ
�œ
�œ
�œ
˜LKš
œ:˜:Kšœ�œ˜4Kšœ�œw˜�
Kšœ�œ"˜>Kš
œ=˜=K˜—˜	š
œ"˜"Kš�œ �œ	˜/Kš�œ
�œ �œ
˜5Kš�œA˜E—Kšœ#�œ
˜1Kšœ�œ˜%Kšœ�œ˜%Kšœ�œq˜Kšœ�œ"˜>Kš
œ]™]Kšœ�œ�œ�œ˜Qš�œ�œ
�œ˜Kšœ�œq˜Kšœ�œ"˜>—š�œ˜Kš
œ˜—Kš
œ=˜=—š�œ
˜K˜——Kš
œ2˜2Kš
œ2˜2Kš
œ2˜2Kš
œ2˜2K˜Kš
œW˜WKšœ$�œ'˜M—™Kš
œ%™%Kš
œ"˜"—Kš�œ
˜—Kš
œ˜K˜—š
 
œ�œJ�œ"�œ�œ˜‘
š�œ�˜˜	Kš�œ�œ
�œ;˜ZKšœ�œ˜2KšœP�œ˜q—K˜š
œ˜Kšœ)�œ�œ˜OKšœ)�œ�œ˜LKš
œ?˜?Kš
œA˜A—K˜˜
Kš�œ�œ
�œ;˜[Kšœ�œ˜3KšœP�œ˜p—Kš�œ
˜—K˜K˜—š œ�œB˜[K˜š œ$˜+š�œ�œ
�œ˜š�œ�˜Kš
œ*˜*—Kš
œ˜—Kš
œ˜K˜—Kš
œ.˜.Kš
œ˜K˜—š œ�œ;�œ˜vK˜Kš
œB˜BKš
œB˜Bš�œ�œ
�œ˜Kš
œ-˜-Kš
�œ�œ�œ
�œ�œ-˜iKš�œ
�œ�œ�œ
�œ�œ˜nš�œ˜Kšœ�œ
�œ�œ˜NKšœ�œ
�œ�œ˜NKš�œ�œ
�œ�œ-˜UKš�œ
�œ�œ˜@——Kš�œ
�œ˜K˜—š œ�œa˜uK™6K˜š 
œ˜ Kšœ�œ.˜JKšœ�œ.˜Jš�œ
�œ	�œ˜-Kš�œ
�œ	�œ˜,Kš�œ˜!——K˜Kšœ�œ˜2Kšœ�œ(˜@Kšœ!�œ%˜LKšœ �œ$˜JK˜š�œ
�œ
Ÿœ�œ	�œ
�˜dKšœ �œ˜4š�œ�œ˜Kš
œ™Kšœ
�œ�œ
�œ"˜LKš�œ'˜+K˜š�œ�œ$™<Kšœ�™ —š
�™Kš
œF™FKšœ
�œ�œ
�œ"™LKš�œ'™+—Kš
œ!™!Kš
œ%˜%—K˜š�œ
�œ�œ˜!Kš
œ™Kšœ
�œ�œ
�œ!˜JKš�œ&˜*K˜š�œ�™Kšœ#Ÿ'œ™L—š
�™Kš
œF™FKšœ
�œ�œ
�œ!™JKš�œ&™*Kš
œ!™!—Kš
œ&˜&—K˜š�œ�œ˜9š�œ�˜š
œ˜Kš
œE˜E—š
œ˜š	�œ�œ
�œ�œ
�˜NKš
œE˜E—š
�˜Kš
œM˜M——Kš
œK˜KKš�œ˜	——Kš�œ˜	—K˜—š œ�œv�œ&˜¯
K™2K˜š�œ�œ
�˜š�œ�œ�˜=Kš
œ2˜2šœ�œ�œ�œ˜^Kš�œ˜—Kšœ
�œ˜*Kš�œ˜	——K˜—š 
œ�œ�œ ˜QK™K˜Kš
œ;˜;Kš�œ�œ
�œ
˜K˜Kš
œ9˜9Kš�œ�œ
�œ
˜K˜Kš
œ=˜=Kš�œ�œ
�œ
˜K˜Kš
œC˜CKš�œ˜K˜K˜—š œ�œF�œ9˜—
Kš
œ'™'K˜Kš
œ˜Kš
œ˜Kš
œ˜K˜š�œ
�œ�˜(Kš
œ"˜"Kš�œ%�œ˜>Kš�œ
�œ%�œ˜BKš�œ ˜$Kš�œ˜	—K˜—š œ�œ�œ�œ�œ�œ�œ�œ˜K™:Kš
œ6™6K˜š 
œ�œ ˜0Kš�œ�œ�œ˜WKš�œ
�œ�œ�œ˜QKš�œ
�œ�œ�œ˜HK˜—š œ�œA˜Rš�œ�˜šœ
�œ�˜š�œ˜
Kš
œ|™|Kš
œY˜YKš
œ#˜#Kš
œ!˜!—š�œ˜	Kš�œ1�œ˜OKš�œ˜—Kš�œ6˜=——Kš
œ˜K˜—Kš
œ6™6Kšœ'�œ
˜+Kš
œ;˜;Kš
œ=˜=Kš
œ˜Kš
œ˜š�œ>�œ�œ
�˜TKš
œ˜Kš�œ
˜K˜—Kš
œ.™.Kš
œ˜Kš
œ!˜!K˜Kš
œ0™0š�œ8�œ�œ
�˜NKš
œ‚
™‚
Kš
œ`˜`Kš
œ#˜#Kš
œ ˜ Kš�œ
˜—Kš
œ˜K˜—š 	œ�œG�œ"˜K™2K˜Kš
œ?˜?Kš
œ<˜<Kš
œ&˜&Kš
œ&˜&Kšœ�œ
˜'Kšœ�œ
˜'Kšœ�œ�œ�œ˜aKšœ�œ�œ�œ˜aK˜š�œ
�œ
�˜šœ�œ˜Kšœ�œ(˜8K˜—˜Kš
Ÿ ™ Kš
Ÿ
™
Kš
œ1˜1Kšœ�œ:˜J—K˜šœ�œ�œ�œ˜FKš
Ÿ™Kš
Ÿ™Kš
œ2˜2Kš
œ7˜7Kš
œ7˜7Kšœ�œ˜-K˜—šœ�œ�œ�œ˜EKš
Ÿ™Kš
œ™Kš
œ0˜0Kš
œ/˜/Kšœ�œ*˜:K˜—šœ�œ�œ�œ˜FKš
œ™Kš
Ÿ™Kš
œ0˜0Kš
œ/˜/Kšœ�œ*˜:K˜—šœ�œ�œ�œ˜FKš
Ÿ™Kš
Ÿ™Kš
œ2˜2Kš
œ7˜7Kš
œ7˜7Kšœ�œ˜-K˜—˜Kš
Ÿ™Kš
Ÿ&™&Kš
œ1˜1Kšœ�œ:˜JK˜—Kš�œ=˜D—K˜—š œ�	œ�œ
�œ	˜QK˜š�œ
�œ�˜Kš�œ�œ
�œ˜:Kš�œ˜	K˜——š 
œ�œ"�œ�œ˜PKšœ�œ
˜
š�œ�œ
�˜Kšœ�œ˜K˜Kš�œ
˜—Kš�œ˜KšœŸ˜K˜—Kš
œE™EKš
œ"™"Kš
œB™BK˜š œ�œ&˜BKš
œ&˜&Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš�œ�œ˜'K™:K™BK™"K˜Kš
œh™hKš
œ>˜>Kš
œ0˜0Kšœ
�œ
˜Kšœ�œ
˜K˜š�œ�˜š
œ˜š	�œ2�œ�œ	�œ
�˜bKš
œX˜Xš�œ
�˜Kšœ�œ0˜;—Kš�œ˜	——š
œ˜š	�œ1�œ�œ	�œ
�˜aKš
œX˜Xš�œ
�˜Kšœ�œ0˜;—Kš�œ˜	——Kš�œ˜	—K˜—š œ�œ&˜?Kš
œ&˜&Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš�œ�œ�œ�œ�œ
�œ˜GK™Kš
œ!™!Kš
œ&™&K™K™K˜š œ�œ�œ�œ˜[šœ
�œ�œ
�˜Kš
œ3˜3Kš
œ3˜3Kš�œ�œ
�œ
˜Kš�œ
�œ�œ
�œ
˜"Kš�œD˜H—K˜—š 
œ$˜.š�œ�œ
�˜š�œ�œ�˜9Kš�œ)�œ�œ˜=—K˜——š œ$˜4š�œ�œ
�˜š�œ�œ�˜>š�œ)�œ�œ˜=K˜————Kš
œ>˜>Kš
œC˜CKšœ�œ*˜FKš
œ1˜1Kš
œ%˜%Kš
œ˜Kš
œ ˜ Kš
œ!˜!Kš
œ5˜5K˜Kš
œC™CKš�œ6�œ�œ
˜OKš�œ7�œ�œ
˜PK˜K™$Kš
œt˜tš�œ�œ�œ
�˜PKš
œ"™"Kš
œ>˜>Kš
œ<˜<Kš�œ
˜—K™š�œ�œ˜K™6Kš
œ5˜5Kš
œX˜XKšœ!�œY˜}Kšœ2�œ_˜”
Kš
œ\˜\Kšœ!�œY˜}Kšœ2�œ_˜”
Kš
œ\˜\Kš
œg˜gK˜K™'Kš
œz˜zš�œ�œ�œ
�˜PKš
œ>˜>Kš
œ?˜?Kš
œ:˜:Kšœ�œ1˜IK˜š�œ�˜Kšœ�œ�œŸ,˜\K™&Kš
œ?˜?—K˜Kš
œ:™:š
œ<™<Kš
œ3™3—š�œ�œ�œ
�˜LKš
œ1˜1Kš
œ0˜0Kš
œ4˜4Kšœ�œ.˜CK˜š�œ�˜Kšœ�œ�œŸ,˜ZK™&Kš
œ>˜>—K˜š�œ�œ�œ˜*Kš�œ�œ�œŸ	˜8J˜J˜—Kš�œ
˜—Kš�œ
˜K˜K™š�œQ�˜WKšœ#�œ2˜X—Kš	�œ�œF�œ
�œ
�˜qKš
�œ�œF�œ
�œ�œ
˜qKš
�œ�œF�œ
�œ�œ
˜qK˜š�œ
�˜Kš
œz˜z—K˜K™!Kš
œ<˜<Kš
œ<˜<Kš
œ.˜.Kš
œ/˜/Kš
œ˜——K˜—š œ�œ�œ�œ˜WKš
œ)™)š�œ
�œ�˜Kš�œ�œ
�œ˜=Kš�œ
˜—K˜K˜—š œ�œ�œ˜FKš
œ'™'š�œ�œ�˜Kš�œ�œ
�œ
˜.Kš�œ
˜—K˜K˜—š 
œ�œ‰
˜œ
š
œ™Kš
œ3™3Kš
œ™Kš
œ™Kš
œ™K™—š œ$˜5Kš�œ!�œ�œ
˜EKš�œ"�œ�œ
˜GKš�œ$�œ�œ
˜KKš�œ%�œ�œ
˜MKš
œ˜K˜—Kš
œ>˜>Kš
œ0˜0Kš
œ6˜6Kš
œ4˜4Kš
œ4˜4Kš
œ ˜ Kš
œT˜TKš
œA˜AKšœ+�œ
˜/Kš
œ˜Kš
œ8˜8Kšœ�œ_˜Kšœ�œ_˜K˜š�œ[�œ˜cKš
œ™Kš
œ;˜;K˜š�œ�˜˜Kš
œ�œ�œ�œ
�œ
�œ
�œ
˜LKš
œ:˜:Kšœ�œ˜4Kšœ�œ}˜–
Kšœ�œ"˜>Kš
œ=˜=K˜—˜	š
œ"˜"Kš�œ �œ	˜/Kš�œ
�œ �œ
˜5Kš�œA˜E—Kšœ#�œ
˜1Kšœ�œ˜%Kšœ�œ˜%Kšœ�œq˜Kšœ�œ"˜>Kš
œ]™]Kšœ�œ�œ�œ˜Qš�œ�œ
�œ˜Kšœ�œq˜Kšœ�œ"˜>—š�œ˜Kš
œ˜—Kš
œ=˜=—š�œ
˜K˜——Kš
œ2˜2Kš
œ2˜2Kš
œ2˜2Kš
œ2˜2K˜Kš
œW˜WKšœ$�œ'˜MKš
œ
˜
K˜—š�œŸ0˜7Kš
œ$˜$Kš
œ7˜7Kšœ�œ%˜:Kšœ�œ}˜–
Kšœ�œ"˜>Kš
œ?˜?J˜Kšœ Ÿ˜:K˜Kš
œ2˜2Kš
œ2˜2Kš
œ2˜2Kš
œ2˜2K˜Kš
œ^˜^Kšœ#�œ'˜LK˜K˜—Kš
œ#™#Kš
œ ˜ Kš
œ˜K˜—š œ�œD�œ�œ�œ�œ�œ˜’
K˜K™6Kš
œ6™6K™FK˜š œ,˜;Kš�œ0�œ�œ�œ™TK˜š œ$˜+Kš�œ)�œ�œ�œ™MK˜š�œ�œ˜š�œ
�˜Kšœ$�œ˜CKšœ�œ˜:Kš
œ˜Kš
œ˜Kš�œ9˜@—Kš
œ
˜
—Kš
œ˜K˜—Kš
œ2˜2—K˜Kš
œ(˜(Kš
œ>˜>š�œ�œ
�œ˜Kš
œ]˜]Kš
œ#˜#Kš
œ!˜!—š�œ�œ
�œ˜Kš
œ^˜^Kš
œ#˜#Kš
œ!˜!—Kš
œ˜K˜—š œ�œG˜\K˜Jš
œ.™.K˜š œ,˜;Kš�œ0�œ�œ�œ™TK˜š œ$˜+Kš�œ)�œ�œ�œ™MK˜š�œ�œ˜Kšœ�œ
˜Kšœ�œ
˜Kšœ�œ
˜ Kšœ�œ
˜!Kš
œ˜—K˜—Kš
œ2˜2—K˜Kš
œ?˜?K˜—š
 œ�œ4�œ	�œ�œ˜cK˜Kšœ�œ™'š�œ�œ
�œ˜Kš	�œ�œ
�œ �œ	�˜WKš
�œ�œ
�œ"�œ	�œ
˜YKš
�œ�œ
�œ$�œ	�œ
˜]Kš
�œ�œ
�œ%�œ	�œ
˜_K˜K˜——š
 
œ�œP�œ�œ�œ˜�
K˜Kš
œ1˜1š�œ(�œ�œ�˜[š�œ(�œ�œ�˜[š	�œ�œ
�œ�œ
�˜+Kš
œB˜BKš
œB˜Bš�œ�œ
�œ�œ
�œ�˜Aš�œ&�œ˜.Kš
œ7˜7Kš
œ7˜7Kš�œ,�œ
�œ�œ˜L———Kš�œŸ˜—Kš�œŸ˜—K˜K˜—š
 œ�œ®
�œ
�œ�œ˜ï
Kš
œ5™5K˜š�œ�œ
�œ�œ
�œ�˜Aš�œ�œ�œ%�œ˜WK˜"Kš
œ>˜>Kš
œ1˜1Kš
œ7˜7Kš
œ7˜7š�œ
�œ
�˜Kšœ.�œD˜uKš
œ7˜7Kš
œ%˜%—š�œ
�œ
�˜Kšœ.�œD˜uKš
œ7˜7Kš
œ%˜%K˜—Kš
œ3˜3š�œ�œ
�˜Kš
œ4™4K™Kš
œ™Kšœ8�œ˜SKš
œM˜MKš
œa˜aKš�œ�œ0˜Qš�œŸ˜Kšœ�œ
˜Kš
œr˜rK˜—Kšœ�œ
˜—š�œŸ˜"K˜Kš
œ™š�œ7�˜=Kšœ�œ<™NKšœ#�œ˜A————K˜—š œ�œ^˜wKš
œC™CKš
œC˜Cš�œ5�œ�œ
�˜KKš
œ9˜9š�œ
�œ
�˜Kšœ-�œH˜xKš
œ7˜7Kš
œ'˜'—š�œ<�˜BKšœ#�œ˜C—Kš�œ
˜—K˜—K˜š œ�œ^˜yKš
œC™CKš
œC˜Cš�œ5�œ�œ
�˜KKš
œ9˜9š�œ
�œ
�œ˜Kšœ-�œH˜xKš
œ7˜7Kš
œ'˜'K˜—š�œ<�˜BKšœ#�œ˜C—Kš�œ
˜—K˜K˜—š œ�œ•
˜®
K™3š�œ8�œ	�œ
�˜OKšœ�œ˜,Kš�œ �œ$�œ+˜yKš�œ
�œ �œ$�œ+˜~Kš�œ
˜Kš�œ
˜—K˜K˜—š œ�	œ4˜TKš�œ�œ	˜'K˜Kš
œ&™&š œ'˜.š�œ;�œ�œ�œ™_š�œ,�œ˜4Kšœ�œ!˜4Kš
œ(˜(Kš
œM˜M——K˜—Kšœ&�œ
˜*Kš
œ>˜>K˜—š œ�	œ4˜TKš�œ�œ	˜'K˜Kš
œ&™&š œ'˜.š�œ;�œ�œ�œ™_š�œ,�œ˜4Kšœ�œ!˜4Kš
œ(˜(Kš
œN˜N——K˜—Kšœ&�œ
˜*Kš
œ?˜?K˜—Kš
œ˜—…—â|5í