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

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

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

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

RangeWithDirList: TYPE = LIST OF RangeWithDir;
RangeWithDir: TYPE = RECORD [
range: RoutePrivate.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 PROCEDURE[routingArea: Route.RoutingArea, routerUsed: RoutePrivate.RouterUsed] RETURNS [anythingToDo: BOOLEAN] = {
chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
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[routingArea]; -- 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[routingArea, pin.pWidth]/2]};

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

pinPosition: RouteChannel.PinPosition _ chanPins.sides[index];
pLoc: Route.Number _ pinPosition.pLoc;
widestPinD2: Route.Number _ RouteUtil.GetWidthWithContact[routingArea, routingArea.rules.branchWidth]/2;
minLimit, maxLimit: RouteChannel.MPinsOnCh;

[] _ RouteChannel.EnumPins[routingArea, pinPosition, WidestPinProc];
[minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[routingArea, 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 _ pinPosition.pins[chanBottom];

IF ProcessConstraints[routingArea, upperPin, lowerPin, middle, pins] THEN GOTO GoRound;
FOR innerPins: RouteChannel.ChanPinList _ pinPosition.innerPins, innerPins.rest WHILE innerPins # NIL DO
innerPin: RouteChannel.ChanPin _ innerPins.first;
IF ProcessConstraints[routingArea, upperPin, innerPin, middle, pins] THEN GOTO GoRound;
IF ProcessConstraints[routingArea, 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: Route.Number _ NARROW[ref1, RouteChannel.ChanPin].qLoc;
p2: Route.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[routingArea, 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[routingArea, seg, NIL, whichEnd, pins];
IF BreaksFound[break] > 0 THEN {
DoBreak[routingArea, break]; GOTO GoRound}
ELSE {  -- mark seg as failed --
seg.failed _ TRUE;
TerminalIO.WriteRope[Rope.Cat["\nunable to find a place to dogleg, net: ", seg.net.name, " failed"]]}};
IF FALSE 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
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;
chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
graph: RouteDiGraph.Graph _ chanData.constraints;
IF leftToRightSegList # NIL THEN
{density: RouteChannel.Density _ RouteChannel.ComputeDensity[routingArea];
segBreak: FullSegBreakSpec _ FindBreak[routingArea, leftToRightSegList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[routingArea, segBreak]
ELSE {  -- choose a victim --
lSegs.first.failed _ TRUE;
TerminalIO.WriteRope[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[routingArea];
segBreak: FullSegBreakSpec _ FindBreak[routingArea, rightToLeftSegList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[routingArea, segBreak]
ELSE {  -- choose a victim --
lSegs.first.failed _ TRUE;
TerminalIO.WriteRope[Rope.Cat["\nnet: ", lSegs.first.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 [routingArea: Route.RoutingArea] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
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[routingArea, pinPosition, ClearConstraints];
ENDLOOP;

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

ProcessConstraints: PROCEDURE[routingArea: Route.RoutingArea, 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[routingArea, 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];
IF DoConstraint[routingArea, lowerSeg, upperSeg, whichEnd, pins] THEN segBroken _ TRUE;
ENDLOOP; -- FOR upperSegIndex
ENDLOOP; -- FOR lowerSegIndex
};

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

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

DoConstraint: PROCEDURE[routingArea: Route.RoutingArea, 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.netNum # upperSeg.net.netNum OR lowerSeg.net.netPart # upperSeg.net.netPart) THEN {
segList: RouteChannel.SegmentList;
chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
graph: RouteDiGraph.Graph _ chanData.constraints;
nets: RoutePrivate.NetTab _ NARROW[routingArea.nets];
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[routingArea];
segBreak: FullSegBreakSpec _ FindBreak[routingArea, segList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[routingArea, segBreak]
ELSE {  -- choose a victim --
segList.first.failed _ TRUE;
TerminalIO.WriteRope[Rope.Cat["\nnet: ", 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 = {
IF arc.superiorNode = lowerNode THEN
{nodeInfo: RouteChannel.SegmentConstraint _ NARROW[lowerNode.nodeInfo];
segList _ CONS[nodeInfo.segment, segList];
quit _ TRUE}
ELSE quit _ RouteDiGraph.EnumArcsFromNode[graph, arc.superiorNode, out, ArcProc];
IF quit THEN
{nodeInfo: RouteChannel.SegmentConstraint _ NARROW[node.nodeInfo];
segList _ CONS[nodeInfo.segment, segList]}};

[] _ RouteDiGraph.EnumArcsFromNode[graph, upperNode, out, ArcProc]};

FindBreak: PROC [routingArea: Route.RoutingArea, segList: RouteChannel.SegmentList, density: RouteChannel.Density, whichEnd: Lmr, pins: TestPins] RETURNS [bestBreak: FullSegBreakSpec _ [NIL, [NIL, NIL, NIL]]] = {

bestResult: BreakResult _ [LAST[INT], LAST[INT], LAST[INT]];

FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO
seg: RouteChannel.Segment _ segs.first;
break: FullSegBreakSpec _ BreakOneSeg[routingArea, seg, density, whichEnd, pins];
result: BreakResult _ EvalBreak[routingArea, break, density];
IF CompareResult[result, bestResult] = less THEN
{bestResult _ result; bestBreak _ break};
ENDLOOP;

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

BreakOneSeg: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, density: RouteChannel.Density, whichEnd: Lmr, pins: TestPins] RETURNS [break: FullSegBreakSpec] = {

parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms];
exitsSeparate: BOOLEAN _ IF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet _ GetPins[exitsSeparate, seg];
rangeList: RangeWithDirList _ SegRanges[routingArea, pinLists];
break _ [seg, [NIL, NIL, NIL]];
SELECT parms.routerUsed FROM
channel => {
FOR ranges: RangeWithDirList _ rangeList, ranges.rest WHILE ranges # NIL DO
break.breaks[middle] _ BreakWithInRange[routingArea, seg, ranges.first, pins];
IF break.breaks[middle] # NIL THEN EXIT;
ENDLOOP;

IF break.breaks[middle] = NIL THEN
break.breaks[middle] _ BreakAtExit[routingArea, 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[routingArea, 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[routingArea, 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[routingArea, seg, rightRange, pins]}};

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
cEnd1: Route.Number _ chanData.chanPins.cEnd1;
cEnd2: Route.Number _ chanData.chanPins.cEnd2;
left, top, right, bottom: BOOLEAN;
[left, top, right, bottom] _ RouteChannel.PinsOnSide[routingArea, 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."];
};

BreakWithInRange: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, range: RangeWithDir, pins: TestPins] RETURNS [break: SegBreakSpec _ NIL] = {

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

NextPosToRight: PROC [pinIndex: RouteChannel.ZMPinsOnCh] RETURNS[pos: Route.Number] ~ {
IF pinIndex = 0 THEN
pos _ chanPins.cEnd1 + routingArea.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[routingArea, pinPosition, WidestPinProc];
pos _ pinPosition.pLoc + widestPinD2 + routingArea.rules.branchSpacing + seg.net.branchWidth/2}};

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

-- minPinD2: Route.Number _ RouteUtil.GetWidthWithContact[routingArea, routingArea.rules.branchWidth]/2;
minPinD2: Route.Number _ routingArea.rules.branchWidth/2;
chanPins: RouteChannel.RoutingChannelPins _ NARROW[routingArea.privateData, RouteChannel.ChannelData].chanPins;
widestPinD2: Route.Number;

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

DogLegNotAllowed: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, pos: Route.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[routingArea, pin, pins.trialPin] THEN quit _ TRUE};

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

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
netTab: RoutePrivate.NetTab _ NARROW[routingArea.nets];
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
minLimit, maxLimit, leftIndex, rightIndex: RouteChannel.ZMPinsOnCh;
width: Route.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[routingArea, pos];

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

[minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[routingArea, leftIndex, rightIndex, CheckInner];
FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pinPosition: RouteChannel.PinPosition _ chanPins.sides[index];
notAllowed _ RouteChannel.EnumPins[routingArea, pinPosition, CheckInner];
ENDLOOP;
[minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[routingArea, 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[routingArea, topPin, pins.trialPin];
constrainBottom: BOOLEAN _ Constraining[routingArea, 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[routingArea, topPin, bP] AND constrainTop AND constrainBottom THEN notAllowed _ TRUE;
IF topNet = bN AND Constraining[routingArea, bottomPin, tP] AND constrainTop AND constrainBottom THEN notAllowed _ TRUE;
ENDLOOP;

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

BreakAtExit: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, density: RouteChannel.Density] RETURNS [break: SegBreakSpec] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
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[routingArea, leftFullBreak, density];
rightResult: BreakResult _ EvalBreak[routingArea, rightFullBreak, density];
IF CompareResult[leftResult, rightResult] = less THEN RETURN [leftBreak]
ELSE RETURN [rightBreak]};

EvalBreak: PROC [routingArea: Route.RoutingArea, break: FullSegBreakSpec, density: RouteChannel.Density] RETURNS [result: BreakResult] = {

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

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

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

DoBreak: PROC [routingArea: Route.RoutingArea, 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;
};

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

FOR lmr: Lmr IN Lmr DO
segBreak: SegBreakSpec _ fullSegBreak.breaks[lmr];
IF segBreak # NIL THEN {
pinIndex: RouteChannel.ZMPinsOnCh _ RouteChannel.FindPinPos[routingArea, 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;
seg2.exitBreak _ TRUE;
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[routingArea, seg1, oldSeg.trackConstraint];
SetTrackConstraints[routingArea, seg2, oldSeg.trackConstraint];

TerminalIO.WriteRope[Rope.Cat["\ntrunk segment for net: ", fullSegBreak.seg.net.name, " divided at: "]];
TerminalIO.WriteInt[chanPins.sides[pinIndex].pLoc/routingArea.rules.CDLambda];
};
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 [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, trackConstraint: Route.Number] = {

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

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

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

l1Range: RoutePrivate.Range _ RouteChannel.GetRange[pinListPair.list1];
l2Range: RoutePrivate.Range _ RouteChannel.GetRange[pinListPair.list2];
IF pin # NIL THEN {
pLoc: Route.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: Route.Number _ MIN[ABS[pLoc - l1Range.l], ABS[pLoc - l1Range.r]];
distToL2: Route.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: Route.Number _ NARROW[ref1, RouteChannel.ChanPin].pinPosition.pLoc;
p2: Route.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 # newPin THEN {chanPin.conctSeg[chanRight] _ seg}
ELSE
{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 # newPin THEN
{chanPin.conctSeg[chanLeft] _ seg; -- chanPin.conctSeg[chanRight] _ NIL -- }
ELSE
{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 [routingArea: Route.RoutingArea, density: RouteChannel.Density, r: RoutePrivate.Range, width: Route.Number] RETURNS [maxDensity: Route.Number _ 0] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;

IF density # NIL THEN
FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
pos: Route.Number _ chanPins.sides[index].pLoc;
thisDensity: Route.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 _ RouteUtil.SimpleCompare[r1.numDogLegs, r2.numDogLegs];
IF result # equal THEN RETURN;

result _ RouteUtil.SimpleCompare[r1.deltaDensity, r2.deltaDensity];
IF result # equal THEN RETURN;

result _ RouteUtil.SimpleCompare[r1.duplicateLength, r2.duplicateLength];
RETURN};


ClosestPins: PROC [routingArea: Route.RoutingArea, target: Route.Number] RETURNS [nextLower, nextHigher: RouteChannel.ZMPinsOnCh _ 0] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
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 [routingArea: Route.RoutingArea, pinLists: ChanPinListSet] RETURNS [rangeList: RangeWithDirList] = {

chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins;
lr: RoutePrivate.Range _ RouteChannel.GetRange[pinLists.bottomList];
ur: RoutePrivate.Range _ RouteChannel.GetRange[pinLists.topList];
ce1: Route.Number _ chanPins.cEnd1;
ce2: Route.Number _ chanPins.cEnd2;
min: Route.Number _ MIN[lr.l, ur.l];
max: Route.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

}.



RouteChannelConstraintsImpl.mesa   ///Route/RouteChannelConstraintsImpl.mesa
Bryan Preas July 10, 1986 6:01:08 pm PDT
Copyright c 1985 by Xerox Corporation.  All rights reserved.
by Bryan Preas   July 10, 1985 6:57:00 pm PDT 
last edited by Bryan Preas   July 10, 1985 6:57:07 pm PDT
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
IF index = chanPins.count THEN {
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
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
decide on which segment to divide and the position
run through the segs in the cycle. find the best
find the best position to break this seg
find the best position to break this seg within this range
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
RouteChannel.AuditPins[routingArea];
RouteChannel.AuditSegs[routingArea];
link the segment to the pin in the list and vice versa
update old seg pointer
chanPin.conctSeg[chanLeft] _ NIL
no old seg pointer, but make sure both segs on new pin are initialized
update old seg pointer
no old seg pointer, but make sure both segs on new pin are initialized
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:                         
Κ"‰˜š
œL™LIcode™(—˜Jšœ
Οm
œ1™<Jš
œ.™.Jš
œ9™9—J˜š
Οk	˜	J˜Jšžœ
˜J˜J˜Jš
œ˜J˜
J˜
Jš
œ
˜
J˜
Jš
œ˜J˜—šΟnœžœ
ž˜*JšžœE˜LJšžœ
˜Jšžœ
˜J˜JšœžœΟc ˜EJšœžœžœ˜)šœžœžœ˜ Jš
œ˜Jš
œ˜—Jšœžœ˜"šœžœžœ˜!Jšœžœ
˜Jš	œžœžœžœ
žœ˜.J˜—šœ
žœžœ˜Jš
œ˜Jš
œ˜Jš
œ˜J˜—Jšœžœžœ
žœ˜.šœžœžœ˜Jš
œ˜Jš
œ"˜"J˜—šœžœžœ˜Jšœ,žœ
˜0Jšœ0žœ˜5J˜—šœžœžœ˜ Jšœ)žœ˜.J˜—Jšœ
žœžœ
˜!šœ
žœžœ˜Jšœ<žœ˜A—J˜š
Ÿœžœ
ž	œFžœžœ˜Ž
Jš
œ$™$Jš
œ<™<J™Jš
œ™Jšœ%žœ˜EJš
œ>˜>Jšœ'žœ˜AJšœžœ˜.Jšœžœžœ
˜Jšœ-žœ7˜gJšœ!žœr˜–
Jšœ-žœD˜tJšœ$žœs˜š
Jšœ.žœD˜uJšœ%žœt˜œ
Jš
œJ˜JJšžœžœ
žœ
žœ˜)J˜šžœž˜Jš
œ9™9Jšœžœ
˜Jšžœžœ
žœ% ˜^Jš
œ;˜;J˜šžœžœž˜=J˜šŸ
œ$˜1šžœžœ
ž˜JšœžœI˜Z—J˜—šŸ	œ$˜-šžœžœ
ž˜Jš
œP˜PJ˜,šžœž˜Jšœž˜—šžœ
žœž˜Jš
œL˜L—šžœ
 ˜Jš
œO˜O——J˜—Jš
œ>˜>Jš
œ&˜&Jš
œh˜hJš
œ+˜+J˜Jš
œ0™0Jš
œD˜DJš
œ_˜_šžœ$žœž˜CJš
œH˜HJš
œ@˜@Jš
œ>˜>J˜JšžœCžœ
žœ	˜WJ™Jš
œ;™;šžœMžœ
žœ
ž˜hJš
œ1˜1J™Jš
œ™JšžœCžœ
žœ	˜WJšžœCžœ
žœ	˜WJšžœ ˜—šžœ ˜J˜——Jš
œD™Dšžœžœžœžœ˜KJ˜šŸœ˜!Jšœžœ"˜;Jšœžœ"˜;šžœ
žœ	žœ˜-Jšžœ
žœ	žœ˜,Jšžœ˜!——J˜Jšœžœžœžœ˜2Jšœžœ(˜@Jšœžœ)˜Ašžœ
žœ
 œžœ	žœ
ž˜dJšœ!žœ˜5Jš
œF˜FJ˜Jš
œ™šžœžœ
žœ˜Jšœ!žœ˜:JšžœEžœ
žœ
˜Z—J˜Jš
œ+™+šžœ3žœžœ
ž˜IJš
œ'˜'š
žœžœžœ.žœ
žœ˜
Jšœ8žœ˜Mšžœžœ˜ Jšœžœ	˜*—šžœ ˜ Jšœ
žœ
˜Jš
œg˜g——Kšžœ
žœ
žœ˜š
œ ™ Kš
œŸ
™Ÿ
Kš
œ>˜>Kš
œB˜BJš
œ2™2šžœ=žœ
žœ
ž˜UJšœ žœ˜5Jš
œF˜FJš
œ&™&šžœ6žœ	žœ
ž˜MJš
œ,˜,Jš
œ8˜8Jš
œ5˜5Jš
œ]˜]Jš
œ-˜-Jšœ%žœ˜EJš
œ1˜1šžœžœ
ž˜ Jš
œ4™4Jš
œJ˜JJš
œa˜aJšžœžœ˜@šžœ ˜Jšœžœ
˜Jš
œn˜n—J˜Jšœžœžœ
˜ —Jš
œC˜Cšžœžœ
ž˜ Jš
œ4™4Jš
œJ˜JJš
œa˜aJšžœžœ˜@šžœ ˜Jšœžœ
˜Jš
œn˜n—J˜Jšœžœžœ
˜ —Jšžœ
˜—Jšžœ
˜—Kš
œ˜—Jšžœ
˜—Jšžœ˜	——Jšžœžœ
˜#Jšžœ ˜—Jšžœ ˜—šžœ
žœ ˜%J˜——šŸœžœ
žœ%˜GJš
œ$™$J˜Jšœ%žœ˜EJš
œ>˜>JšŸœ žœ˜2J˜JšŸ
œžœ˜.J˜šŸœ˜*Jšœ+žœ˜AJšœžœ˜—J˜šŸœ$˜4Jš
œ7˜7Jš
œ9˜9Jšžœžœ
žœžœ
˜3Jšžœžœ
žœžœ˜6J˜—šžœžœž˜=Jš
œ>˜>Jš
œG˜GJšžœ
˜—J˜Jš
œX˜XJ˜—š
Ÿœž	œjžœ
žœžœ˜―
Jš
œ5™5J˜Jš
œ ™ š	žœžœ
žœžœ
ž˜)šžœžœž˜Bšžœžœžœžœžœž˜ 
šžœ/ž˜5Jš
œL™Lšžœ(žœžœž˜Yšžœ(žœžœž˜YJš
œB˜BJš
œB˜BJšžœ?žœ
žœ
˜WJšžœ ˜—Jšžœ ˜————Jš
œ˜J˜——š
ŸœžœDžœžœžœ˜
J™,J˜š	žœžœ
žœžœ
ž˜!Jš
œ*˜*Kš
œU˜UKš
œ!˜!Jš
œ)˜)Jš
œU˜UJš
œ!˜!šžœ	ž˜Jšœž˜—šžœ
žœ	ž˜š
œL˜LJš
œ@˜@——šžœ
 
˜š
œL˜LJš
œC˜C———J˜—š
Ÿœž	œjžœ
žœžœ˜©
Jš
œ5™5J˜šžœžœ
žœžœ
žœž˜Aš
žœžœžœ,žœ.žœ˜Ž
J˜"Jšœ%žœ˜EJš
œ1˜1Jšœžœ˜5Jš
œ7˜7Jš
œ7˜7šžœ
žœ
ž˜Jšœ.žœD˜uJš
œ7˜7Jš
œ%˜%—šžœ
žœ
ž˜Jšœ.žœD˜uJš
œ7˜7Jš
œ%˜%J˜—Jš
œ3˜3šžœžœ
ž˜Jš
œ4™4Jš
œJ˜JJš
œV˜VJšžœžœ˜@šžœ ˜Jšœžœ
˜Jš
œp˜pJ˜—Jšœžœ
˜—šžœ ˜"J˜Jš
œ3™3Jš
œ™šžœ7ž˜=Jš
œN™NJšœ#žœ˜A————J˜—šŸœž	œD˜ZJšžœ&žœ˜5J˜Jš
œ&™&šŸœ'˜.šžœž˜$Jšœ,žœ˜GJšœ
žœ˜*Jšœžœ
˜—JšžœM˜Qšžœž˜Jšœ,žœ˜BJšœ
žœ˜,—J˜—Jš
œD˜DJ˜—šŸ	œžœƒ
žœ!žœžœžœžœ˜Τ
Jš
œ2™2J˜Jš
œžœ
žœžœ
žœžœ
žœ˜<J˜Jš
œ0™0šžœ5žœžœ
ž˜KJš
œ'˜'Jš
œQ˜QJš
œ=˜=šžœ*ž˜0Jš
œ)˜)—Jšžœ
˜J˜—Jšžœžœ
žœ
žœžœžœžœžœ˜<J˜—šŸœžœ{žœ˜±
J™(J˜Jšœ'žœ˜AJš
œžœžœžœ
žœ
žœ
žœ
˜LJš
œ7˜7Jš
œ?˜?Jšœžœžœžœ˜šžœž˜˜šžœ3žœ
žœ
ž˜KJš
œN˜NJšžœžœ
žœ
žœ
˜(Jšžœ
˜J˜—šžœžœ
ž˜"Jš
œ?˜?J˜——˜šŸœžœ˜šžœžœžœžœ˜3šžœ3žœ
žœ
ž˜KJš
œN˜NJšžœžœ
žœ
žœ
˜(Jšžœ˜
———K˜šŸœžœ˜šžœžœžœžœ	žœžœ˜FJš
œ8˜8Jš
œK˜K—K˜—šŸœžœ˜šžœžœžœžœ	žœžœ˜FJš
œ9˜9Jš
œM˜M—K˜—Jšœ%žœ˜EJš
œ.˜.Jš
œ.˜.Jšœžœ
˜"Jš
œG˜GJ˜šžœ
žœ
ž˜Kš
œ/˜/Kš
œ0˜0Kš
œ7˜7Kšžœ ˜'—Jš
œ˜J˜—Jšžœ@˜G—J˜J˜—šŸœžœbžœžœ˜Ÿ
J™:J˜šŸ
œ$˜1šžœžœ
ž˜JšœžœI˜Z—J˜—šŸœžœ%žœ˜Wšžœž˜Jš
œL˜L—šžœ
žœž˜)Jšœžœ
žœ
˜—šžœ˜Jš
œA˜AJš
œ˜Jš
œD˜DJš
œa˜aJ˜——šŸ
œžœ%žœ˜Všžœž˜Jšœžœ
žœ
˜—šžœ
žœž˜&Jš
œL˜L—šžœ˜Jš
œA˜AJš
œ˜Jš
œD˜DJš
œa˜a——J˜Jš
œh˜hJš
œ9˜9Jšœ,žœ=˜oJš
œ˜J˜šžœž˜š
œ˜Jš
œW˜Wšžœ>žœž˜^šžœ0žœ˜8Jšœžœ#˜.Jšžœ˜—Jšœžœ"˜1Jšžœ˜	——š
œ˜Jš
œY˜Yšžœ>žœž˜^šžœ0žœ˜9Jšœžœ#˜.Jšžœ˜—Jšœ
žœ˜$Jšžœ˜	——Jšžœ˜	—J˜—š
Ÿœžœ`žœžœžœ˜Ÿ
J™J˜šŸœžœžœžœ˜Zšœ
žœžœ
ž˜Jš
œ3˜3Jš
œ3˜3Jšžœžœ
žœ
˜Jšžœ
žœžœ
žœ
˜"JšžœD˜H—J˜—šŸ
œ$˜.šžœžœ
ž˜šžœžœž˜9Jšžœ/žœžœ˜C—J˜——šŸœ$˜4šžœžœ
ž˜šžœžœž˜>šžœ/žœžœ˜CJ˜————Jšœ%žœ˜EJšœžœ˜7Jš
œ>˜>Jš
œC˜CJšœžœ*˜CJš
œ%˜%Jš
œ˜Jš
œ ˜ Jš
œ!˜!Jš
œ8˜8J˜Jš
œ#™#Jšžœ<žœžœ
˜UJšžœ=žœžœ
˜VJ˜J™Jš
œi˜išžœžœžœ
ž˜PJš
œ"™"Jš
œ>˜>Jš
œI˜IJšžœ
˜—J™J™Jš
œo˜ošžœžœžœ
ž˜PJš
œ>˜>Jš
œ?˜?Jš
œ9˜9Jš
œ:˜:Jš
œ4˜4Jšœžœ4˜IJšœžœ7˜OJ˜Jš
œ2™2šžœžœžœ
ž˜LJš
œ1˜1Jš
œ/˜/Jš
œ,˜,Jš
œ,˜,Jš
œ,˜,Jšžœžœ'žœžœžœžœ
˜xJšžœ
žœ*žœžœžœžœ
˜xJšžœ
˜—J˜Jš
œ#™#Jš
œJ™JJšžœžœžœžœ
˜:Jšžœ˜	—J˜—šŸœžœ\žœ˜Ž
J™$J˜Jšœ%žœ˜EJš
œ>˜>Jšœžœ+˜HJšœ4žœžœ˜?Jšœžœ+˜IJšœ*žœžœ˜AJš
œI˜IJš
œK˜KJšžœ/žœ
žœ˜HJšžœ
žœ˜J˜—šŸ	œžœZžœ˜Š
J™&J˜Jš
œ˜Jš
œ4˜4Jšœ'žœ˜AJš
œžœžœžœ
žœ
žœ
žœ
˜LJš
œ=˜=Jšžœžœ
žœžœ
žœžœ
žœžœ
žœ˜IJ˜šžœžœ
žœ˜%Jš
œ
˜
Jš
œ~˜~Jš
œ7˜7Jšžœžœ=˜Z—Jšžœ˜J˜Jš
œE˜EJš
œ6˜6Jš
œ/˜/Jš
œ˜šžœ
žœž˜Jšžœžœ
žœ+˜JJšžœ˜	—J˜—šŸœžœE˜Rš
œ™Jš
œ3™3Jš
œ™Jš
œ™Jš
œ™J™—šŸœ$˜5Kšžœ!žœžœ
˜EKšžœ"žœžœ
˜GKšžœ$žœžœ
˜KKšžœ%žœžœ
˜MKš
œ˜K˜—Jšœ%žœ˜EJš
œ>˜>Jšœ'žœ˜AJš
œ0˜0Jš
œ3˜3Jš
œ1˜1šžœ ž˜&Jš
œ7˜7—Jš
œH˜HJ˜šžœ
žœž˜Jš
œ2˜2šžœžœ
žœ˜Jš
œW˜WJš
œA˜AJšœ+žœ
˜/Jš
œ˜Jšœžœ_˜Jšœžœ_˜J˜šžœž˜˜Jš
œžœžœžœ
žœ
žœ
žœ
˜LJš
œ:˜:Jšœžœ˜4Jšœžœw˜
Jšœžœ"˜>Jš
œ=˜=J˜—˜	š
œ"˜"Jšžœ žœ	˜/Jšžœ
žœ žœ
˜5JšžœA˜E—Jšœ#žœ
˜1Jšœžœ
˜Jšœžœ
˜Jšœžœq˜Jšœžœ"˜>Jš
œ]™]Jšœžœžœžœ˜Qšžœžœ
žœ˜Jšœžœq˜Jšœžœ"˜>—šžœ˜Jš
œ˜—Jš
œ<˜<Jš
œ˜—šžœ
˜J˜——Jš
œ2˜2Jš
œ2˜2Jš
œ?˜?Jš
œ?˜?J˜Jš
œh˜hJš
œN˜N—J™Jš
œ%™%Jš
œ$™$Jš
œ$™$J˜Jšžœ
˜—Jš
œ˜J˜—š
Ÿ
œžœJžœ"žœžœ˜‘
šžœž˜˜	Kšžœžœ
žœ;˜ZKšœžœ˜2KšœPžœ˜q—K˜š
œ˜Kšœ)žœžœ˜OKšœ)žœžœ˜LKš
œ?˜?Kš
œA˜A—K˜˜
Kšžœžœ
žœ;˜[Kšœžœ˜3KšœPžœ˜p—Kšžœ
˜—J˜J˜šŸœžœ_˜xJ˜šŸœ$˜+šžœžœ
žœ˜šžœž˜Jš
œ,˜,——J˜—Jš
œ=˜=J˜——šŸœžœ;žœ˜vK˜Kš
œG˜GKš
œG˜Gšžœžœ
žœ˜Kš
œ*˜*Kš
žœžœžœ
žœžœ-˜iKšžœ
žœžœžœ
žœžœ˜nšžœ˜Kšœžœ
žœžœ˜KKšœžœ
žœžœ˜KKšžœžœ
žœžœ-˜UKšžœ
žœžœ˜@——Kšžœ
žœ˜K˜—šŸœžœa˜uJ™6J˜šŸ
œ˜ Jšœžœ.˜GJšœžœ.˜Gšžœ
žœ	žœ˜-Jšžœ
žœ	žœ˜,Jšžœ˜!——J˜Jšœžœ˜2Jšœžœ(˜@Jšœ!žœ%˜LJšœ žœ$˜JJ˜šžœ
žœ
 œžœ	žœ
ž˜dJšœ žœ˜4šžœžœ˜Jš
œ™šžœžœ$˜<Jš
œ ™ —š
ž˜Jš
œF™FJšœ
žœžœ
žœ"˜LJšžœ'˜+—Jš
œ%˜%—J˜š	žœ
žœžœžœž˜9š
œ™Jšœ# 'œ˜L—š
ž˜Jš
œF™FJšœ
žœžœ
žœ!˜JJšžœ&˜*—Jš
œ&˜&—J˜šžœžœ˜9šžœž˜š
œ˜Jš
œE˜E—š
œ˜š	žœžœ
žœžœ
ž˜NJš
œE˜E—š
ž˜Jš
œM˜M——Jš
œK˜KJšžœ˜	——Jšžœ˜	—J˜—šŸœžœmžœ#˜£
J™2J˜Jšœ%žœ˜EJš
œ>˜>J˜šžœžœ
ž˜šžœžœž˜=Jš
œ/˜/šœžœžœžœ˜[Jšžœ˜—Jšœ
žœ˜*Jšžœ˜	——J˜—šŸ
œžœžœ ˜QJ™J˜Jš
œ?˜?Jšžœžœ
žœ
˜J˜Jš
œC˜CJšžœžœ
žœ
˜J˜Jš
œI˜IJšžœ˜J˜J˜—šŸœžœ8žœ9˜‰
Jš
œ'™'J˜Jšœ%žœ˜EJš
œ>˜>Jš
œ˜Jš
œ˜Jš
œ˜J˜šžœ
žœž˜(Jš
œ"˜"Kšžœ%žœ˜>Kšžœ
žœ%žœ˜BKšžœ ˜$Jšžœ˜	—J˜—šŸœžœžœžœžœžœžœžœ˜J™:Jš
œ6™6J˜šŸ
œžœ ˜0Jšžœžœžœ˜WJšžœ
žœžœžœ˜QJšžœ
žœžœžœ˜HJ˜—šŸœžœA˜Ršžœž˜šœ
žœž˜šžœ˜
Jš
œ|™|Jš
œY˜YJš
œ#˜#Jš
œ!˜!—šžœ˜	Jšžœ1žœ˜OJšžœ˜—Jšžœ6˜=——Jš
œ˜J˜—Jš
œ6™6Jšœ'žœ
˜+Jš
œ;˜;Jš
œ=˜=Jš
œ˜Jš
œ˜šžœ>žœžœ
ž˜TJš
œ˜Jšžœ
˜J˜—Jš
œ.™.Jš
œ˜Jš
œ!˜!J˜Jš
œ0™0šžœ8žœžœ
ž˜NJš
œ‚
™‚
Jš
œ`˜`Jš
œ#˜#Jš
œ ˜ Jšžœ
˜—Jš
œ˜J˜—šŸ	œžœ<žœ"˜tJ™2J˜Jšœ%žœ˜EJš
œ>˜>Jš
œD˜DJš
œA˜AJš
œ#˜#Jš
œ#˜#Jšœžœ
˜$Jšœžœ
˜$Jšœžœžœžœ˜aJšœžœžœžœ˜aJ˜šžœ
žœ
ž˜šœžœ˜Jšœžœ(˜8J˜—˜Jš
œ ™ Jš
œ
™
Jš
œ1˜1Jšœžœ:˜J—J˜šœžœžœžœ˜FJš
œ™Jš
œ™Jš
œ2˜2Jš
œ7˜7Jš
œ7˜7Jšœžœ˜-J˜—šœžœžœžœ˜EJš
œ™Jš
œ™Jš
œ0˜0Jš
œ/˜/Jšœžœ*˜:J˜—šœžœžœžœ˜FJš
œ™Jš 
œ
™Jš
œ0˜0Jš
œ/˜/Jšœžœ*˜:J˜—šœžœžœžœ˜FJš 
œ™Jš 
œ ™Jš
œ2˜2Jš
œ7˜7Jš
œ7˜7Jšœžœ˜-J˜—˜Jš 
œ™Jš 
œ™&Jš
œ1˜1Jšœžœ:˜JJ˜—Jšžœ=˜D—J˜—šŸœž	œžœ
žœ	˜QJ˜šžœ
žœž˜Jšžœžœ
žœ˜:Jšžœ˜	J˜——šŸ
œžœ"žœžœ˜PKšœžœ
˜
šžœžœ
ž˜Kšœžœ˜K˜Kšžœ
˜—Kšžœ˜Kšœ ˜K˜—Jš
œ˜—J˜J˜J˜—…—‘$ΒΓ