DIRECTORY
CD USING [Error, ErrorCode, Instance, Number, Object, Orientation, Position, Rect],
CDBasics USING [BaseOfRect, Extend, Intersect, Intersection, NonEmpty, ToRect],
CDOrient USING [ComposeOrient, DeMapRect, MapRect, original, RectAt, rotate180, rotate270, rotate90],
CStitching USING [Area, IsEmpty, ChangeRect, Rect, EEdge, EN, EnumerateArea, ResetTesselation, ChangeEnumerateArea, ListArea, NE, NewTesselation, NEdge, RectProc, TileProc, Region, SEdge, SW, Tesselation, Tile, FindTile, WEdge, WS],
PrincOpsUtils USING [],
SX USING [AdjustNode, Circuit, CircuitNode, Constraint, ConstraintResolution, FindRootNode, GeometricRule, LogicalCell, LookupNode, MergeNode, nodeIndex, NormalizeCircuit, spaceIndex, SpinifexLayerIndex],
SXAccess USING [design, stopFlag, sxTech],
SXAccessInternal USING [GetLogicalCell, PutError],
SXLayers USING [],
SXQuadTree USING [AreaSplit, Create, Dimension, Enumerate, PerRectProc, QuadTree, QuadTreeRoot, Rectangle, Rectangles],
TerminalIO USING [WriteRope];
SXLayersImpl: CEDAR PROGRAM
IMPORTS CD, CDBasics, CDOrient, CStitching, SX, SXAccess, SXAccessInternal, SXQuadTree, TerminalIO
EXPORTS SXLayers = BEGIN
TilePtr: TYPE = CStitching.Tile;
nothing: REF INT ~ NEW [INT];
Constraint: TYPE = SX.Constraint;
Rectangle: TYPE = SXQuadTree.Rectangle;
Node: TYPE = SX.CircuitNode;

ConflictWorlds: TYPE = ARRAY SX.SpinifexLayerIndex OF CStitching.Tesselation;
GeometryWorlds: TYPE = ARRAY SX.SpinifexLayerIndex OF CStitching.Tesselation;
ConstraintQueue: TYPE = ARRAY SX.SpinifexLayerIndex OF LIST OF REF CStitching.Region _ ALL[NIL];
conflictWorlds: ConflictWorlds;
geometryWorlds: GeometryWorlds;
saveTesselations: BOOL _ FALSE;
freeTesselations: BOOL _ FALSE;
UseLevelOrderHeuristic: PROC [clipRect: CD.Rect, old, new: SXQuadTree.Rectangles] RETURNS [BOOLEAN] = BEGIN
ThinLimit: CD.Number = SXAccess.design.technology.lambda * 10;
RETURN [(clipRect.x2 - clipRect.x1 > ThinLimit) AND (clipRect.y2 - clipRect.y1 > ThinLimit)]
END;	-- UseLevelOrderHeuristic
ComputeConflicts: PROC [
qt:		REF SXQuadTree.QuadTree,
conflictWorld:	CStitching.Tesselation,
layer:		SX.SpinifexLayerIndex,
cir:		REF SX.Circuit] = BEGIN
descentDepth: INT _ 1;
OccupyByNode: CStitching.RectProc = BEGIN
WITH oldValue SELECT FROM
a: ATOM => IF a # $Conflict THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r: REF Rectangle => IF data # r THEN
CStitching.ChangeRect [conflictWorld, rect, $Conflict];
s: SXQuadTree.Rectangles =>
IF data # s.first THEN BEGIN
CStitching.ChangeRect [conflictWorld, rect, data];
Flatten [rect, s]
END
ELSE CD.Error [ec: other, explanation: "Quad-tree screwed up (subcell found twice)"];
c: REF Constraint =>
IF NOT SameConstraints [ResolveConstraints [c, data, SXAccess.sxTech.constraintResolutions[layer]], data] THEN
CStitching.ChangeRect [conflictWorld, rect, $Conflict];
ENDCASE =>
IF oldValue = NIL THEN
CStitching.ChangeRect [conflictWorld, rect, data]
ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]
END;	-- OccupyByNode
OccupyByConstr: CStitching.RectProc = BEGIN
WITH oldValue SELECT FROM
a: ATOM => IF a # $Conflict THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r: REF Rectangle =>
IF NOT SameConstraints [ResolveConstraints[NARROW[data], r, SXAccess.sxTech.constraintResolutions[layer]], r] THEN
CStitching.ChangeRect [conflictWorld, rect, $Conflict];
s: SXQuadTree.Rectangles => BEGIN
conflictWorld.ChangeRect[rect, data];
Flatten [rect, s]
END;
c: REF Constraint => BEGIN
resolution: REF ANY = ResolveConstraints [c, data, SXAccess.sxTech.constraintResolutions [layer]];
IF (NOT SameConstraints[resolution, c] AND NOT SameConstraints[resolution, data]) THEN CStitching.ChangeRect [conflictWorld, rect, $Conflict]
ELSE IF NOT SameConstraints[resolution, c] THEN
CStitching.ChangeRect [conflictWorld, rect, resolution];
END;
ENDCASE => 
IF oldValue = NIL THEN
CStitching.ChangeRect [conflictWorld, rect, data]
ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]
END;	-- OccupyByConstr
OccupyByAppl: CStitching.RectProc = BEGIN
WITH oldValue SELECT FROM
a: ATOM => IF a # $Conflict THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r: REF Rectangle => BEGIN
IF NARROW[data, SXQuadTree.Rectangles].first = r THEN
CD.Error [ec: other, explanation: "Rectangle has already been processed"];
Flatten [rect, NARROW[data]]
END;
s: SXQuadTree.Rectangles =>
IF data # s THEN
IF UseLevelOrderHeuristic [rect, s, NARROW[data]] THEN
DescendOneLevel [rect, s, NARROW[data]]
ELSE BEGIN
CStitching.ChangeRect [conflictWorld, rect, NIL];
Flatten [rect, s];
Flatten [rect, NARROW[data]]
END;
c: REF Constraint => Flatten [rect, NARROW[data]];
ENDCASE =>
IF oldValue = NIL THEN
CStitching.ChangeRect [conflictWorld, rect, data]
ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]
END;	-- OccupyByAppl
Flatten: PROC [clipRect: CD.Rect, applRef: SXQuadTree.Rectangles] = BEGIN
appl: CD.Instance = NARROW [applRef.first.nodeInformation];
FlattenCell: PROC [appl: CD.Instance, pos: CD.Position, orient: CD.Orientation] = BEGIN
MapRect: PROC [inCellRect: CD.Rect] RETURNS [inWorldRect: CD.Rect] = INLINE BEGIN
inWorldRect _ CDBasics.Intersection [
CDOrient.MapRect [itemInCell: inCellRect,
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos],
clipRect]
END;	-- MapRect
FlattenTree: PROC [qt: REF SXQuadTree.QuadTree] = BEGIN
FOR boxes: SXQuadTree.Rectangles _ qt.boxes, boxes.rest WHILE boxes#NIL DO
WITH boxes.first.nodeInformation SELECT FROM
node: REF Node => {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r] THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, OccupyByNode, applRef.first, nothing]
};
constr: REF Constraint => {
r: CD.Rect = MapRect[boxes.first.interestBound];
IF CDBasics.NonEmpty[r] THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, OccupyByConstr, constr, nothing]
};
subAppl: CD.Instance =>
IF CDBasics.Intersect [boxes.first.interestBound, mappedClip] THEN {
FlattenCell [
subAppl, 
CDBasics.BaseOfRect [CDOrient.MapRect [
itemInCell: CDOrient.RectAt [pos: subAppl.location, size: subAppl.ob.size, orient: subAppl.orientation], 
cellSize: appl.ob.size, 
cellInstOrient: orient, 
cellInstPos: pos]], 
CDOrient.ComposeOrient [subAppl.orientation, orient]]
};
ENDCASE => ERROR;	-- Quad tree srewed up
ENDLOOP;
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
IF mappedClip.y2>qt.midY AND qt.subTrees[north]#NIL THEN
FlattenTree[qt.subTrees[north]];
IF mappedClip.y1<qt.midY AND qt.subTrees[south]#NIL THEN
FlattenTree[qt.subTrees[south]];
IF mappedClip.x2>qt.midX AND qt.subTrees[east]#NIL THEN
FlattenTree[qt.subTrees[east]];
IF mappedClip.x1<qt.midX AND qt.subTrees[west]#NIL THEN
FlattenTree[qt.subTrees[west]];
END;	-- FlattenTree
cellQt: REF SXQuadTree.QuadTree;
mappedClip: CD.Rect = CDOrient.DeMapRect [itemInWorld: clipRect,
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos];
cellQt _ SXAccessInternal.GetLogicalCell[appl.ob].circuit.spinifexLayers[layer].geometry;
IF cellQt # NIL THEN
FlattenTree [cellQt]
END;	-- FlattenCell
FlattenCell[appl, appl.location, appl.orientation]
END;	-- Flatten
DescendOneLevel: PROC [clipRect: CD.Rect, old, new: SXQuadTree.Rectangles] = BEGIN
levelCount: INT;
BidByNode: CStitching.RectProc = BEGIN
WITH oldValue SELECT FROM
a: ATOM => IF a # $Conflict THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r: REF Rectangle => IF data # r THEN
CD.Error [ec: other, explanation: "Tesselation screwed up"];
s: SXQuadTree.Rectangles => CStitching.ChangeRect [conflictWorld, rect, data];
c: REF Constraint => CStitching.ChangeRect [conflictWorld, rect, data];
ENDCASE => ERROR
END;	-- BidByNode
BidByConstr: CStitching.RectProc = BEGIN
WITH oldValue SELECT FROM
a: ATOM => IF a # $Conflict THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r: REF Rectangle => IF new.first # r THEN
CD.Error [ec: other, explanation: "Tesselation screwed up"];
s: SXQuadTree.Rectangles => 
IF s # new THEN CStitching.ChangeRect [conflictWorld, rect, data];
c: REF Constraint => BEGIN
resolution: REF ANY = ResolveConstraints [c, data, SXAccess.sxTech.constraintResolutions [layer]];
IF NOT SameConstraints [resolution, c] THEN
CStitching.ChangeRect [conflictWorld, rect, resolution];
END;
ENDCASE => ERROR;
END;	-- BidByConstr
BidByAppl: CStitching.RectProc = BEGIN
WITH oldValue SELECT FROM
a: ATOM => IF a # $Conflict THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r: REF Rectangle => 
IF NARROW[data, SXQuadTree.Rectangles].first # r THEN
CD.Error [ec: other, explanation: "Tesselation screwed up"];
s: SXQuadTree.Rectangles => 
IF data # s THEN CStitching.ChangeRect [conflictWorld, rect, data];
c: REF Constraint => CStitching.ChangeRect [conflictWorld, rect, data];
ENDCASE => ERROR;
END;	-- BidByAppl
DescendCell: PROC [appl: CD.Instance, pos: CD.Position, orient: CD.Orientation] = BEGIN
MapRect: PROC [inCellRect: CD.Rect] RETURNS [inWorldRect: CD.Rect] = INLINE BEGIN
inWorldRect _ CDBasics.Intersection [
CDOrient.MapRect [
itemInCell: inCellRect, 
cellSize: appl.ob.size, 
cellInstOrient: orient, 
cellInstPos: pos], 
clipRect]
END;	-- MapRect
DescendTree: PROC [qt: REF SXQuadTree.QuadTree] = BEGIN
IF qt=NIL THEN RETURN;
FOR boxes: SXQuadTree.Rectangles _ qt.boxes, boxes.rest WHILE boxes#NIL DO
WITH boxes.first.nodeInformation SELECT FROM
node: REF Node => {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r] THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, BidByNode, new.first, nothing]
};
constr: REF Constraint => {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r] THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, BidByConstr, constr, nothing]
};
subAppl: CD.Instance =>
IF CDBasics.Intersect [boxes.first.interestBound, mappedClip] THEN {
IF levelCount > 0 THEN
DescendCell [
subAppl, 
CDBasics.BaseOfRect [CDOrient.MapRect [
itemInCell: CDOrient.RectAt [pos: subAppl.location, size: subAppl.ob.size, orient: subAppl.orientation],
cellSize: appl.ob.size, 
cellInstOrient: orient, 
cellInstPos: pos]], 
CDOrient.ComposeOrient [subAppl.orientation, orient]]
ELSE {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r] THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, BidByAppl, new, nothing]
}
};
ENDCASE => ERROR;
ENDLOOP;
IF mappedClip.y2 > qt.midY AND qt.subTrees[north] # NIL THEN
DescendTree [qt.subTrees[north]];
IF mappedClip.y1<qt.midY AND qt.subTrees[south]#NIL THEN
DescendTree [qt.subTrees[south]];
IF mappedClip.x2>qt.midX AND qt.subTrees[east]#NIL THEN
DescendTree [qt.subTrees[east]];
IF mappedClip.x1<qt.midX AND qt.subTrees[west]#NIL THEN
DescendTree [qt.subTrees[west]];
END;	-- DescendTree
cellQt: REF SXQuadTree.QuadTree;
mappedClip: CD.Rect = CDOrient.DeMapRect [itemInWorld: clipRect,
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos];
cellQt _ SXAccessInternal.GetLogicalCell[appl.ob].circuit.spinifexLayers[layer].geometry;
levelCount _ levelCount-1;
DescendTree [cellQt];
levelCount _ levelCount+1;
END;	-- DescendCell
appl: CD.Instance = NARROW [new.first.nodeInformation];
descentDepth _ descentDepth + 1;
levelCount _ descentDepth/2;	-- Descend until levelCount = 0
DescendCell [appl, appl.location, appl.orientation];
CStitching.ChangeEnumerateArea [conflictWorld, clipRect, OccupyByAppl, old, nothing];
descentDepth _ descentDepth -1
END; -- DescendOneLevel
IF qt = NIL THEN RETURN;
FOR boxes: SXQuadTree.Rectangles _ qt.boxes, boxes.rest WHILE boxes#NIL DO
WITH boxes.first.nodeInformation SELECT FROM
node: REF Node => 
CStitching.ChangeEnumerateArea [conflictWorld, boxes.first.interestBound, OccupyByNode, boxes.first, nothing];
constr: REF Constraint => 
CStitching.ChangeEnumerateArea [conflictWorld, boxes.first.interestBound, OccupyByConstr, constr, nothing];
appl: CD.Instance => 
CStitching.ChangeEnumerateArea [conflictWorld, boxes.first.interestBound, OccupyByAppl, boxes, nothing];
ENDCASE => ERROR;
ENDLOOP;
FOR quad: SXQuadTree.AreaSplit IN SXQuadTree.AreaSplit DO
ComputeConflicts [qt.subTrees[quad], conflictWorld, layer, cir]
ENDLOOP;
IF descentDepth#1 THEN
CD.Error [ec: other, explanation: "ComputeConflicts: descentDepth#1"]
END;	-- ComputeConflicts
SameConstraints: PROC [c1, c2: REF ANY] RETURNS [BOOLEAN] = {
IF c1 = c2 THEN RETURN[TRUE];
WITH c1 SELECT FROM 
con1: REF Constraint => {
WITH c2 SELECT FROM
con2: REF Constraint => RETURN [con1.name = con2.name]; 
ENDCASE => RETURN [FALSE];
};
ENDCASE => RETURN[FALSE];
};	-- SameConstraints
ResolveConstraints: PROC [newConstraint: REF Constraint, oldValue: REF ANY, resolution: REF SX.ConstraintResolution] RETURNS [REF ANY] = BEGIN
WITH oldValue SELECT FROM
oldConstraint: REF Constraint => {
specificNode: REF SX.CircuitNode _ NIL;
result: REF Constraint _ resolution[newConstraint.index][oldConstraint.index];
IF result=NIL THEN CD.Error[ec~ other, explanation~ "Invalid ConstraintResolution"];
specificNode _ IF newConstraint.specificCorrespondingNode # NIL THEN newConstraint.specificCorrespondingNode ELSE oldConstraint.specificCorrespondingNode; 
IF specificNode # NIL THEN {
result _ NEW[Constraint _ result^];
result.specificCorrespondingNode _ specificNode};
RETURN [result]
};	-- end oldConstraint: REF CircuitConstraint
node: REF Node => {
result: REF Constraint _ resolution[newConstraint.index][SX.nodeIndex];
IF result=NIL THEN RETURN [node]
ELSE {
IF newConstraint.specificCorrespondingNode # NIL THEN {
result _ NEW[Constraint _ result^];
result.specificCorrespondingNode _ newConstraint.specificCorrespondingNode};
RETURN [result]};
};
rect: REF Rectangle => {
result: REF Constraint _ resolution[newConstraint.index][SX.nodeIndex];
IF result=NIL THEN RETURN [rect]
ELSE {
IF newConstraint.specificCorrespondingNode # NIL THEN {
result _ NEW[Constraint _ result^];
result.specificCorrespondingNode _ newConstraint.specificCorrespondingNode};
RETURN [result]};
};
ENDCASE => ERROR
END;	-- ResolveConstraints
BloatConflictsIntoAOIs: PROC [
cir:		REF SX.Circuit,
layer:		SX.SpinifexLayerIndex,
conflictWorld:	CStitching.Tesselation]
RETURNS [cleanedConflictWorld: CStitching.Tesselation] = BEGIN
CopyBloated: CStitching.TileProc = BEGIN
IF tile.value = $Conflict THEN
cleanedConflicts.ChangeRect [
rect: CDBasics.Extend[tile.Area, bloatValue],
new: $AOI];
END;	-- CopyBloated
bloatValue: INT _ SXAccess.sxTech.layerInterestBloat [layer];
cleanedConflicts: CStitching.Tesselation _ CStitching.NewTesselation [];
[] _ conflictWorld.EnumerateArea [cir.spinifexLayers[layer].size, CopyBloated];
CStitching.ResetTesselation [conflictWorld];
cleanedConflictWorld _ cleanedConflicts;
END;	-- BloatConflictsIntoAOIs
InstantiateAOIs: PROC [
cir:		REF SX.Circuit,
qt:		REF SXQuadTree.QuadTree,
cellBBox:		CD.Rect,
flatLoc:		CD.Position _ [0, 0],
flatOrient:	CD.Orientation _ CDOrient.original,
appl:		CD.Instance _ NIL,
nameQualifier:	LIST OF CD.Instance _ NIL,
layer:		SX.SpinifexLayerIndex,
conflictWorld:	CStitching.Tesselation,
geometryWorld:	CStitching.Tesselation,
constraintQueue:	ConstraintQueue]
RETURNS [newConstraintQueue: ConstraintQueue] = BEGIN
InstantiateTree: PROC [qt: REF SXQuadTree.QuadTree, qtBranchBox: CD.Rect] = BEGIN
EnqueueConstraintRegion: PROC [cc: REF Constraint, r: CStitching.Rect] = BEGIN
constraintQueue[layer] _ CONS [
NEW [CStitching.Region _ [rect: r, value: cc]],
constraintQueue[layer]] 
END;	-- EnqueueConstraintRegion
branchBox: CD.Rect = CDOrient.MapRect [itemInCell: qtBranchBox,
cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size),
cellInstOrient: flatOrient,
cellInstPos: flatLoc];
IF conflictWorld.IsEmpty [branchBox] THEN RETURN;
FOR boxes: SXQuadTree.Rectangles _ qt.boxes, boxes.rest WHILE boxes#NIL DO
mappedDim: CD.Rect = CDOrient.MapRect [
itemInCell: SXQuadTree.Dimension [boxes.first],
cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size),
cellInstOrient: flatOrient,
cellInstPos: flatLoc];
IF NOT conflictWorld.IsEmpty[mappedDim] THEN {
WITH boxes.first.nodeInformation SELECT FROM
subAppl: CD.Instance => {
cellQt: REF SXQuadTree.QuadTree;
subcellBBox: CD.Rect;
rect: CD.Rect = CDOrient.RectAt [pos: subAppl.location,
size: subAppl.ob.size,
orient: subAppl.orientation];
mappedRect: CD.Rect = CDOrient.MapRect [itemInCell: rect,
cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size),
cellInstOrient: flatOrient,
cellInstPos: flatLoc];
orient: CD.Orientation = CDOrient.ComposeOrient [
itemOrientInCell: subAppl.orientation,
cellOrientInWorld: flatOrient];
[size: subcellBBox, geometry: cellQt] _ SXAccessInternal.GetLogicalCell[subAppl.ob].circuit.spinifexLayers[layer]; 
IF cellQt = NIL THEN LOOP;
constraintQueue _ InstantiateAOIs [qt: cellQt,
cellBBox: subcellBBox,
flatLoc: CDBasics.BaseOfRect [mappedRect],
flatOrient: orient,
appl: subAppl,
nameQualifier: CONS [subAppl, nameQualifier],
-- following are the parameters added in the restructuration: --
cir: cir,
layer: layer,
conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
constraintQueue: constraintQueue];
};	-- end rectangle is a subcell
cNode: REF SX.CircuitNode => {
name: REF SX.CircuitNode = IF (nameQualifier=NIL) THEN cNode ELSE cir.FindRootNode [subcircuitNode: cNode,
qualifier: nameQualifier,
insertIfNotInCircuit: TRUE].node;
occupants: LIST OF REF CStitching.Region _ NARROW[geometryWorld.ListArea[mappedDim] ];
newList: LIST OF REF SX.CircuitNode _ LIST[name];
geometryWorld.ChangeRect [rect: mappedDim, new: newList];
WHILE occupants # NIL DO
IF NOT conflictWorld.IsEmpty[occupants.first.rect] THEN
WITH occupants.first.value SELECT FROM
oldList: LIST OF REF SX.CircuitNode => -- oldList forms shared tail in all multiply occupied areas.  Subsequent processing allows this.  We must ensure that each node appears only once and that the list head is unique.
IF ~(oldList.first = name AND oldList.rest=NIL) THEN {
old: LIST OF REF SX.CircuitNode _ oldList;
replaceList: LIST OF REF SX.CircuitNode;
WHILE old#NIL DO
IF old.first = name THEN EXIT;
old _ old.rest;
ENDLOOP;
replaceList _ IF old#NIL THEN 
CONS [oldList.first, oldList.rest] 
ELSE CONS [name, oldList];
geometryWorld.ChangeRect [rect: occupants.first.rect, new: replaceList]
};
ENDCASE => ERROR;
occupants _ occupants.rest;
ENDLOOP;
}; -- end rectangle is a node
cc: REF Constraint => EnqueueConstraintRegion[cc, mappedDim];
ENDCASE => ERROR	-- This type not expected in quad tree
}
ENDLOOP;	-- instantiate all rectangles in this Quad Tree node
{
IF qt.subTrees[north] # NIL THEN
InstantiateTree [qt.subTrees[north],
[x1: qtBranchBox.x1, y1: qt.midY, x2: qtBranchBox.x2, y2: qtBranchBox.y2]];
IF qt.subTrees[south] # NIL THEN
InstantiateTree [qt.subTrees[south],
[x1: qtBranchBox.x1, y1: qtBranchBox.y1, x2: qtBranchBox.x2, y2: qt.midY]];
IF qt.subTrees[east] # NIL THEN
InstantiateTree [qt.subTrees[east],
[x1: qt.midX, y1: qtBranchBox.y1, x2: qtBranchBox.x2, y2: qtBranchBox.y2]];
IF qt.subTrees[west] # NIL THEN
InstantiateTree [qt.subTrees[west],
[x1: qtBranchBox.x1, y1: qtBranchBox.y1, x2: qt.midX, y2: qtBranchBox.y2]];
}
END; -- InstantiateTree
InstantiateTree [qt, cellBBox];
newConstraintQueue _ constraintQueue
END; -- InstantiateAOIs
AnalyzeNodesInAOIs: PROC [
cir:		REF SX.Circuit,
layer:		SX.SpinifexLayerIndex,
geometryWorld:	CStitching.Tesselation] = BEGIN
MergeNodeTiles: CStitching.TileProc = BEGIN
CountEdge: PROC [nl1, nl2: LIST OF REF SX.CircuitNode] RETURNS [INT] = BEGIN
InAButNotB: PROC [a,b: LIST OF REF SX.CircuitNode] RETURNS [c: INT _ 0] = BEGIN
FOR s1: LIST OF REF SX.CircuitNode _ a, s1.rest WHILE s1#NIL DO
s2: LIST OF REF SX.CircuitNode _ b;
WHILE s2#NIL DO
IF s1.first=s2.first THEN EXIT;  -- Shared sources.
s2 _ s2.rest;
ENDLOOP;
IF s2=NIL THEN c _ c+1;  -- node in s1 not in s2
ENDLOOP;
END;	-- InAButNotB
RETURN [InAButNotB[a: nl1, b: nl2] + InAButNotB[a: nl2, b: nl1]]
END;	-- CountEdge
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
WITH tile.value SELECT FROM
cnList: LIST OF REF SX.CircuitNode => {
list: LIST OF REF SX.CircuitNode _ cnList.rest;
eastBound: INT = tile.EEdge;
northBound: INT = tile.NEdge;
westBound: INT = tile.WEdge;
southBound: INT = tile.SEdge;
r: CD.Rect = tile.Area;
extraNodes: INT _ 0;
n1: REF SX.CircuitNode = SX.LookupNode [cnList.first];
WHILE list # NIL DO
n2: REF SX.CircuitNode = SX.LookupNode [list.first];
IF n1 # n2 THEN cir.MergeNode [to: n1, from: n2];
SX.AdjustNode [node: n1, layer: layer, area: -((r.x2 - r.x1)*(r.y2 - r.y1)), perim: 0];
extraNodes _ extraNodes+1;
list _ list.rest;
ENDLOOP;
FOR tileSouth: TilePtr _ tile.WS, tileSouth.NE WHILE tileSouth.WEdge < eastBound DO
IF tileSouth.value#NIL THEN WITH tileSouth.value SELECT FROM
cnSouthList: LIST OF REF SX.CircuitNode => {
n2: REF SX.CircuitNode = SX.LookupNode [cnSouthList.first];
IF n1 # n2 THEN cir.MergeNode [to: n1, from: n2];
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(CountEdge[cnList, cnSouthList] * (MIN[eastBound, tileSouth.EEdge] - MAX[westBound, tileSouth.WEdge]))]
};
constraint: REF Constraint => NULL;  -- Ignore
ENDCASE =>  ERROR
ELSE	-- tileSouth.value=NIL
IF extraNodes > 0 THEN
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(extraNodes * (MIN[eastBound, tileSouth.EEdge] - MAX[westBound, tileSouth.WEdge]))]
ENDLOOP;	-- end FOR tileSouth
FOR tileWest: TilePtr _ tile.SW, tileWest.EN WHILE tileWest.SEdge < northBound DO
IF tileWest.value#NIL THEN WITH tileWest.value SELECT FROM
cnWestList: LIST OF REF SX.CircuitNode => {
n2: REF SX.CircuitNode;
IF n1 # (n2_SX.LookupNode[cnWestList.first]) THEN 
cir.MergeNode [to: n1, from: n2];
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(CountEdge[cnList, cnWestList] * (MIN[northBound, tileWest.NEdge] - MAX[southBound, tileWest.SEdge]))]
};
constraint: REF Constraint => NULL;  -- Ignore
ENDCASE => ERROR
ELSE IF extraNodes > 0 THEN
SX.AdjustNode [node: n1,
layer: layer, area: 0,
perim: -(extraNodes * (MIN[northBound,tileWest.NEdge] - MAX[southBound,tileWest.SEdge]))]
ENDLOOP; -- tileWest
FOR tileNorth: TilePtr _ tile.EN, tileNorth.SW WHILE tileNorth.EEdge > westBound DO
IF (tileNorth.value = NIL) AND (extraNodes > 0) THEN
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(extraNodes * (MIN[eastBound, tileNorth.EEdge] - MAX[westBound, tileNorth.WEdge]))]
ENDLOOP; -- tileNorth
FOR tileEast: TilePtr _ tile.NE, tileEast.WS WHILE tileEast.NEdge > southBound DO
IF (tileEast.value=NIL) AND (extraNodes > 0) THEN
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(extraNodes * (MIN[northBound, tileEast.NEdge] - MAX[southBound, tileEast.SEdge]))]
ENDLOOP; -- tileEast
};
ENDCASE =>  ERROR
END;	-- MergeNodeTiles
[] _ geometryWorld.EnumerateArea [rect: cir.spinifexLayers[layer].size,
eachTile: MergeNodeTiles];
END;	-- AnalyzeNodesInAOIs
MixRec: TYPE = RECORD [newConstraint: REF Constraint,
rect: CD.Rect,
resolution: REF SX.ConstraintResolution,
tilesToPaint: LIST OF REF CStitching.Region];
CheckRec: TYPE = RECORD [conflictWorld: CStitching.Tesselation,
geometryWorld: CStitching.Tesselation,
rules: LIST OF REF SX.GeometricRule,
cell: REF SX.LogicalCell,
cir: REF SX.Circuit];
DesignRuleCheckAOIs: PROC [
	cir:		REF SX.Circuit,
	cell:		REF SX.LogicalCell,
	constraintQueue:	ConstraintQueue,
	layer:		SX.SpinifexLayerIndex,
	geometryWorld:	CStitching.Tesselation,
	conflictWorld:	CStitching.Tesselation] = BEGIN
mixRef: REF MixRec = NEW [MixRec];	-- used to transfer parameters to MixConstraints
checkRef: REF CheckRec = NEW[CheckRec];	-- used to transfer parameters to CheckTile
FOR newCc: LIST OF REF CStitching.Region _ constraintQueue[layer], newCc.rest
WHILE newCc#NIL DO
mixRef^ _ [newConstraint: NARROW [newCc.first.value],
rect: newCc.first.rect,
resolution: SXAccess.sxTech.constraintResolutions[layer],
tilesToPaint: NIL];
[] _ geometryWorld.EnumerateArea [rect: mixRef.rect,
eachTile: MixConstraints,
skip: $Nothing,
data: mixRef];
FOR tilesToPaint: LIST OF REF CStitching.Region _ mixRef.tilesToPaint, tilesToPaint.rest WHILE tilesToPaint#NIL DO
geometryWorld.ChangeRect [rect: tilesToPaint.first.rect, new: tilesToPaint.first.value]
ENDLOOP;
ENDLOOP;
checkRef^ _ [conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
cell: cell,
cir: cir,
rules: SXAccess.sxTech.rules[layer]];
[] _ geometryWorld.EnumerateArea [rect: cir.spinifexLayers[layer].size,
eachTile: CheckTile,
skip: $Nothing,
data: checkRef]
END; -- DesignRuleCheckAOIs
MixConstraints: CStitching.TileProc = BEGIN
mixRef: REF MixRec = NARROW [data];
newval: REF ANY _ mixRef.newConstraint;
IF (tile.value = NIL) OR (tile.value # (newval _ ResolveConstraints [mixRef.newConstraint, tile.value, mixRef.resolution])) THEN
mixRef.tilesToPaint _ CONS [
NEW [CStitching.Region _ [rect: CDBasics.Intersection [mixRef.rect, tile.Area],
	value: newval]],
mixRef.tilesToPaint]
END; -- MixConstraints
FindNode: PROC [handle: REF CheckRec, nodeLayer: SX.SpinifexLayerIndex, r: CD.Rect] RETURNS [REF ANY] = BEGIN
node: REF SX.CircuitNode;
FoundIt: SIGNAL [n: REF SX.CircuitNode];
{
ENABLE FoundIt => {node _ n; GOTO Done};
FindNodeInner: PROC [circuit: REF SX.Circuit, rect: CD.Rect, aChain: LIST OF CD.Instance] = BEGIN
SearchForNode: SXQuadTree.PerRectProc = BEGIN
WITH r.nodeInformation SELECT FROM
n: REF SX.CircuitNode => IF CDBasics.Intersect[r.Dimension, rect] THEN {
parentNode: REF SX.CircuitNode;
newChain: LIST OF CD.Instance;
[parentNode, newChain] _ handle.cir.FindRootNode[n, aChain];
IF newChain=NIL THEN SIGNAL FoundIt[parentNode]
};
a: CD.Instance => {
subcir: REF SX.Circuit = SXAccessInternal.GetLogicalCell[a.ob].circuit;
subR: CD.Rect = CDOrient.DeMapRect [itemInWorld: rect, cellSize: a.ob.size, cellInstOrient: a.orientation, 
cellInstPos: a.location
];
FindNodeInner[subcir, subR, CONS[a, aChain]];
};
ENDCASE;
END;	-- SearchForNode
SXQuadTree.Enumerate [circuit.spinifexLayers[nodeLayer], rect, SearchForNode, NIL]
END;	-- FindNodeInner
FindNodeInner[handle.cir, r, NIL];
RETURN [NEW[INT]];
EXITS Done => RETURN [node];
}
END;	-- FindNode
CheckTile: CStitching.TileProc = BEGIN
Quadrants: TYPE = {ne, nw, sw, se};
DesignRuleCheckCorner: PROC [quadVals: ARRAY Quadrants OF REF ANY, pos: CD.Position] =
BEGIN
CheckArea: PROC [rule: REF SX.GeometricRule, orient: CD.Orientation, flavour: { convex, concave}] = BEGIN
FindNodeAtCorner: PROC [n: REF ANY] RETURNS [REF ANY] = BEGIN
WITH n SELECT FROM
cn: REF SX.CircuitNode => RETURN [cn];
cc: REF Constraint => {
IF cc.specificCorrespondingNode # NIL THEN RETURN[SX.LookupNode[cc.specificCorrespondingNode]];  --Bowers, September 4, 1985 2:10:58 pm PDT
IF ~cc.hasCorrespondingNode THEN CD.Error[ec: other, explanation: "FindNodeAtCorner: ~cc.hasCorrespondingNode"];
RETURN [FindNode[handle, cc.correspondingNodeLayer, CDBasics.Extend[CDBasics.ToRect[pos, pos], 1]] ]
};
ENDCASE => RETURN [NEW[INT]];
END;
FindNodeInTile: PROC [n: REF ANY, area: CD.Rect] RETURNS [REF ANY] = BEGIN
WITH n SELECT FROM
cn: REF SX.CircuitNode => RETURN [cn];
cc: REF Constraint => {
IF ~cc.hasCorrespondingNode THEN CD.Error[ec: other, explanation: "FindNodeInTile: ~cc.hasCorrespondingNode"];
RETURN [FindNode[handle, cc.correspondingNodeLayer, area]]
};
ENDCASE => RETURN [NEW[INT]];
END;
CheckTileValue: CStitching.TileProc = BEGIN
CheckValue[tile.value, tile.Area]
END;
CheckValue: PROC [value: REF ANY, area: CD.Rect]  = BEGIN
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
WITH value SELECT FROM
cn: REF SX.CircuitNode => {
IF ~rule.trigger2[SX.nodeIndex] THEN RETURN;
IF (rule.okIfConnected AND nodeAtCorner#NIL AND FindNodeAtCorner[nodeAtCorner] = SX.LookupNode[cn]) THEN
RETURN;
};
cc: REF Constraint => {
IF ~rule.trigger2[cc.index] THEN RETURN;
IF (rule.okIfConnected AND nodeAtCorner#NIL AND cc.hasCorrespondingNode AND FindNodeAtCorner[nodeAtCorner] = FindNodeInTile[cc, area] OR
(cc.specificCorrespondingNode # NIL AND FindNodeAtCorner[nodeAtCorner] = SX.LookupNode[cc.specificCorrespondingNode])) THEN
RETURN;
};
cnList: LIST OF REF SX.CircuitNode =>
CD.Error[ec: other, explanation: "CheckValue: found a list of circuit nodes where a single one was expected"];
ENDCASE => {
IF value=NIL THEN {
IF ~rule.trigger2[SX.spaceIndex] THEN RETURN;
}
ELSE CD.Error [ec: other, explanation: "CheckValue: value # NIL"]
};
IF notReportedYet AND conflictWorld.IsEmpty[
rect: CDOrient.MapRect[
itemInCell: [x1: -delta, y1: -delta, x2: len, y2: len], 
cellSize: [0, 0], 
cellInstOrient: orient, 
cellInstPos: pos
],
skip: $AOI] THEN { -- FOUND AN ERROR
rect: CD.Rect = CDOrient.MapRect [
itemInCell: [x1: 0, y1: 0, x2: rule.extent, y2: rule.extent],
cellSize: [0, 0],
cellInstOrient: orient,
cellInstPos: pos];
SXAccessInternal.PutError [ob: handle.cell.cellObj,
r: rect,
message: rule.message];
notReportedYet _ FALSE
}
END; -- CheckValue
notReportedYet: BOOLEAN _ TRUE;
len: INT = rule.extent;
delta: INT = 1;
IF len = 0 THEN {
IF notReportedYet THEN
CheckValue[quadVals[ne], [pos.x, pos.y, pos.x+delta, pos.y+delta]];
IF notReportedYet THEN
CheckValue[quadVals[nw], [pos.x, pos.y-delta, pos.x+delta, pos.y]];
IF notReportedYet THEN
CheckValue[quadVals[sw], [pos.x-delta, pos.y-delta, pos.x, pos.y]];
IF notReportedYet THEN
CheckValue[quadVals[se], [pos.x-delta, pos.y, pos.x, pos.y+delta]];
}
ELSE {
SELECT flavour FROM
convex => {
[] _ handle.geometryWorld.EnumerateArea [
rect: CDOrient.MapRect [itemInCell: [x1: -delta, y1: 0, x2: len, y2: len], cellSize: [0, 0], cellInstOrient: orient, cellInstPos: pos], 
eachTile: CheckTileValue,
skip: $Nix];
[] _ handle.geometryWorld.EnumerateArea [
rect: CDOrient.MapRect [itemInCell: [x1: 0, y1: -delta, x2: len, y2: 0], cellSize: [0, 0], cellInstOrient: orient, cellInstPos: pos],
eachTile: CheckTileValue,
skip: $Nix];
};
concave => {
[] _ handle.geometryWorld.EnumerateArea [
rect: CDOrient.MapRect [itemInCell: [x1: 0, y1: 0, x2: len, y2: len], cellSize: [0, 0], cellInstOrient: orient, cellInstPos: pos], 
eachTile: CheckTileValue,
skip: $Nix];
};
ENDCASE
}
END;	-- CheckArea

or0: CD.Orientation = CDOrient.original;
or90: CD.Orientation = CDOrient.rotate90;
or180: CD.Orientation = CDOrient.rotate180;
or270: CD.Orientation = CDOrient.rotate270;
nodeAtCorner: REF ANY _ NIL;
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
FOR ruleList: LIST OF REF SX.GeometricRule _ handle.rules, ruleList.rest WHILE ruleList#NIL DO
rule: REF SX.GeometricRule = ruleList.first;
bitIndex: ARRAY Quadrants OF INTEGER = [8, 4, 2, 1];
quadBits: INTEGER _ 0;
nodeAtCorner _ NIL;
FOR q: Quadrants IN Quadrants DO
WITH quadVals[q] SELECT FROM
cn: REF SX.CircuitNode => {
IF rule.trigger1[SX.nodeIndex] THEN {
quadBits _ quadBits + bitIndex[q];
nodeAtCorner _ cn
}
};
cc: REF Constraint => {
IF rule.trigger1[cc.index] THEN {
quadBits _ quadBits + bitIndex[q];
IF cc.hasCorrespondingNode AND nodeAtCorner=NIL THEN nodeAtCorner _ cc
}
};
cnList: LIST OF REF SX.CircuitNode => {
CD.Error [ec: other, explanation: "DesignRuleCheckCorner: 'LIST OF REF SX.CircuitNode' should have been squashed to 'REF SX.CircuitNode' in `AnalyzeNodesInAOIs'.\nPLEASE save a copy of this design and make it available to Giordano. Thanks"]
};
ENDCASE => {
IF quadVals[q]=NIL THEN {
IF rule.trigger1[SX.spaceIndex] THEN quadBits _ quadBits + bitIndex[q]
}
ELSE CD.Error[ec: other, explanation: "DesignRuleCheckCorner: quadVals[q]#NIL"]
};
ENDLOOP;	-- end Translate the quadrant contents into bit vector values
SELECT quadBits FROM
0 => NULL;
1 => CheckArea[rule, or90, convex];
2 => CheckArea[rule, or0, convex];
3 => NULL;
4 => CheckArea[rule, or270, convex];
5 => { CheckArea[rule, or90, convex]; CheckArea[rule, or270, convex] };
6 => NULL;
7 => CheckArea[rule, or0, concave];
8 => CheckArea[rule, or180, convex];
9 => NULL;
10 => { CheckArea[rule, or0, convex]; CheckArea[rule, or180, convex] };
11 => CheckArea[rule, or90, concave];
12 => NULL;
13 => CheckArea[rule, or180, concave];
14 => CheckArea[rule, or270, concave];
15 => NULL;
ENDCASE => ERROR;
ENDLOOP;
END;	-- DesignRuleCheckCorner
handle: REF CheckRec = NARROW[data];
conflictWorld: CStitching.Tesselation = handle.conflictWorld;
tileBound: CD.Rect = tile.Area;
IF conflictWorld.FindTile[[x: tileBound.x1, y: tileBound.y1]].value = $AOI THEN {
IF tile.SW.SEdge = tileBound.y1 THEN {
IF tile.WS.WEdge = tileBound.x1 THEN NULL  -- This is a (rare I suspect) 4 way corner it is handled at the NE corner.
ELSE {
IF tile.value = tile.SW.value THEN 
CD.Error[ec: other, explanation: "CheckTile: violated Max horz rule"];
DesignRuleCheckCorner[
[ne: tile.value, nw: tile.SW.value, sw: tile.WS.value, se: tile.WS.value], 
[tileBound.x1, tileBound.y1]
];
}
}
ELSE {	-- tile.WS.WEdge = tileBound.x1 IMPLICITLY
IF tile.value = tile.WS.value THEN NULL	-- No corner really
ELSE {
DesignRuleCheckCorner [
[ne: tile.value, nw: tile.SW.value, sw: tile.SW.value, se: tile.WS.value],
[tileBound.x1, tileBound.y1]];
}
}
};
IF conflictWorld.FindTile[[x: tileBound.x2, y: tileBound.y2]].value = $AOI THEN {
IF tile.NE.NEdge = tileBound.y2 THEN {
IF tile.EN.EEdge = tileBound.x2 THEN {
neQTile: TilePtr _ tile.EN.NE;
WHILE neQTile.SEdge > tileBound.y2 DO
neQTile _ neQTile.WS;
ENDLOOP;
DesignRuleCheckCorner [
[ne: neQTile.value, nw: tile.EN.value, sw: tile.value, se: tile.NE.value],
[tileBound.x2, tileBound.y2]];
}
ELSE {
IF tile.value = tile.NE.value THEN 
CD.Error[ec: other, explanation: "CheckTile:  violated Max horz rule NEast"];
DesignRuleCheckCorner [
[ne: tile.EN.value, nw: tile.EN.value, sw: tile.value, se: tile.NE.value],
[tileBound.x2, tileBound.y2]];
}
}
ELSE {	-- tile.EN.EEdge = tileBound.x2 IMPLICITLY
IF tile.value = tile.EN.value THEN NULL	-- No corner really
ELSE {
DesignRuleCheckCorner [
[ne: tile.NE.value, nw: tile.EN.value, sw: tile.value, se: tile.NE.value], 
[tileBound.x2, tileBound.y2]];
}
}
}
END;	-- CheckTile
AnalyzeGeometry: PUBLIC PROC [cell: REF SX.LogicalCell] = BEGIN
cir: REF SX.Circuit = cell.circuit;
constraintQueue: ConstraintQueue;
IF freeTesselations THEN FreeTesselations[circuit: cir];
FOR layer: SX.SpinifexLayerIndex IN [0 .. SXAccess.sxTech.numSpinifexLayers) DO
conflictWorld: CStitching.Tesselation _ conflictWorlds[layer] _ CStitching.NewTesselation[];
geometryWorld: CStitching.Tesselation _ geometryWorlds[layer] _ CStitching.NewTesselation[];
cir.spinifexLayers[layer] _ SXQuadTree.Create [cir.spinifexLayers[layer]];
IF cir.spinifexLayers[layer].geometry = NIL THEN LOOP;
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
ComputeConflicts [cir.spinifexLayers[layer].geometry, conflictWorld, layer, cir]; 
conflictWorld _ conflictWorlds[layer] _ BloatConflictsIntoAOIs [cir, layer, conflictWorld]; 
constraintQueue _ InstantiateAOIs [cir: cir,
qt: cir.spinifexLayers[layer].geometry,
cellBBox: cir.spinifexLayers[layer].size,
layer: layer,
conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
constraintQueue: constraintQueue]; 
AnalyzeNodesInAOIs [cir, layer, geometryWorld]; 
ENDLOOP;	-- end of FOR "layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO"
TerminalIO.WriteRope [". "];
FOR layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO
geometryWorld: CStitching.Tesselation _ geometryWorlds[layer];
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
FOR tiles: LIST OF REF CStitching.Region _ NARROW[geometryWorld.ListArea[rect: cir.spinifexLayers[layer].size]], tiles.rest WHILE tiles#NIL DO
geometryWorld.ChangeRect [rect: tiles.first.rect,
new: SX.LookupNode[NARROW[tiles.first.value, LIST OF REF SX.CircuitNode].first]]
ENDLOOP;
ENDLOOP;
SX.NormalizeCircuit [cir];
TerminalIO.WriteRope [". "];
FOR layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO
conflictWorld: CStitching.Tesselation _ conflictWorlds[layer];
geometryWorld: CStitching.Tesselation _ geometryWorlds[layer];
DesignRuleCheckAOIs [cir, cell, constraintQueue, layer, geometryWorld, conflictWorld];
ENDLOOP;
TerminalIO.WriteRope [". "];
IF saveTesselations THEN freeTesselations _ TRUE ELSE FreeTesselations [circuit: cir];
END;	-- AnalyzeGeometry
SaveTesselations: PUBLIC PROC [save: BOOL _ FALSE] = BEGIN
saveTesselations _ save
END;
GetTesselation: PUBLIC PROC [conflicts: BOOL _ TRUE, layer: SX.SpinifexLayerIndex] RETURNS [CStitching.Tesselation] = BEGIN
RETURN [IF conflicts THEN conflictWorlds[layer] ELSE geometryWorlds[layer]]
END;
FreeTesselations: PROC [circuit: REF SX.Circuit] = BEGIN
FOR layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO
CStitching.ResetTesselation [conflictWorlds[layer]];
CStitching.ResetTesselation [geometryWorlds[layer]];
ENDLOOP;
TerminalIO.WriteRope [". "];
freeTesselations _ FALSE
END;
END.
<XSXLayersImpl.mesa	
Copyright c 1984, 1985 by Xerox Corporation.  All rights reserved.
Creates a representation of the layout suitable for hierarchical analysis.  Spinifex produces a hierarchical circuit representation, and list of regions containing design rule violations.
Written by Shand, September 12, 1983 11:40 pm
Last Edited by Mark Shand, March 13, 1985 2:50:54 am PST
Last Edited by: Jacobi, April 8, 1985 4:39:46 pm PST
Bowers, September 6, 1985 11:50:22 am PDT
Last edited by: gbb June 6, 1986 3:09:40 pm PDT
Global Types and Variables
The conflict worlds are used to find the regions where interactions occour.
The geometry worlds contain the flattened regions where conflicts occour.
The following two data structures are global for maintenance purposes.
The conflict worlds are used to find the regions where interactions occour.
The geometry worlds contain the flattened regions where conflicts occour.
Maintenance aids
Conflict Resolution
Only bother with Level-order Conflict Resolution when the contended region is not too narrow.
The quad-trees are enumerated and the conflict world is constructed. Each rectangle has an area of interest depending on the material. Constraints do not overlap: they are ordered into the technology dependent part; the larger prevails. Every constraint is represented by a number which is an index in a boolean array to infere whether it is there.
4 things are put into the conflictWorld they are:
REF Rectangle:	occupied by a node (possibly within a subcell as determined by val.nodeInformation's TYPE, either REF circuitNode or CD.Instance)
REF Constraint:	occupied by a constraint or some resolution of constraints such that the resolution at each step was one of the two contending constraints vying for occupancy of the region.
SXQuadTree.Rectangles:	Bid for occupancy by a subcell to some unspecified depth.
ATOM ~ $Conflict	being the result of an irresolvable conflict for occupancy and flagging a region as requiring instantiation and analysis.
[plane: REF Tesselation, rect: Rect, new: REF _ NIL] 
If there already is a conflict nothing needs to be done.
Different rectangle g conflict.
Old contents is subcell which needs to be flattened out: insert node and flatten subcell.
Else no change.
Initially the plane is empty, hence tile = NIL. Insert a new tile.
[plane: REF Tesselation, rect: Rect, new: REF _ NIL] 
If there already is a conflict nothing needs to be done.
Resolve constraints against each other.
Initially the plane is empty, hence tile=NIL.
Initially the plane is empty, hence tile = NIL. Insert a new tile.
[plane: REF Tesselation, rect: Rect, new: REF _ NIL] 
If oldValue is a subcell, then rect is the intersection of the subcell oldValue and the cell data. Otherwise it is a conflict, a a rectangle or a constraint.
If there already is a conflict nothing needs to be done.
Clear present occupant out of region.
Add flattened rectangles from each cell to region.
If subcell of same subcell: already done.
Initially the plane is empty, hence tile = NIL. Insert a new tile.
(local of FlattenCell, local of Flatten)
Use quad-tree to filter what has to be flattened.
Situation: two cells overlap. Goal: Try not to flatten unnecessary cells (i.e. which do not have material or constraints in the overlap or interacting material.
[plane: REF Tesselation, rect: Rect, oldValue: REF, data: REF] 
[plane: REF Tesselation, rect: Rect, oldValue: REF, data: REF] 
[plane: REF Tesselation, rect: Rect, oldValue: REF, data: REF] 
(local of DescendCell, local of DescendOneLevel)
(local of DescendCell, local of DescendOneLevel)
main of DescendCell
Main of ComputeConflicts
The big boxes are inserted first, then the smaller stuff.  Having radix sorted the boxes into sub-trees increases locality of reference to the corner stitched data structure.
CStitching.ChangeEnumerateArea is for local changes. For each rectangle in the first parameter, the function which is the second parameter is called the third parameter as the function's parameter:
Only the first box is of interest. A list is passed because the type is used as a discriminant to decide:
  1. if list then may or may not have actual geometry and needs further discrimination.
  2. if ref then cell is known to have geometry there.
Recursive because of quad-trees.
The consistency rules for SX.ConstraintResolution are non-trivial, the order of application should not be importantthis is the key attribute.
Check for side effects of returning NEW Constraint!!!
Be careful if you have more than one constraint type with a specificCorrespondingNode 
Bowers September 4, 1985 4:13:08 pm PDT
Procedures For First Per Layer Loop
[BloatConflictsIntoAOIs (AOI = Area Of Interest)]
All rectangles where there is no overlap are deleted. Since the area of interest is 1/2 of the maximal interaction distance, at the end there may be regions which contain none of the original material. For this reason the areas of interest are bloated by 1/2 of the maximal interaction distance.
[tile: TilePtr, data: REF ANY] RETURNS [REF ANY] 
Depth first instantiation of those regions of the hierarchy that were found to be interesting.
InstantiateTree
nameQualifier is not NIL when this node comes from a subcell of the cell currently being processed:
check not already on list.

Main of InstantiateAOIs
The nodes are analysed. Problem: parasitics. The constraints are put in and resolved (additional complexity for electrical conductivity).
[tile: TilePtr, data: REF ANY] RETURNS [REF ANY]
This is quite an embarassment to me, but ...
This code deals with area and perimeter calculation, perhaps it could be done better.  I could think of two ways to do this, neither of them particularly great.  I chose to implement the one I understood best although it is perhaps the less efficient of the two.  Each cornersitched tile is a list of CircuitNodes which had tiles in the area, think of them as the set of sources for any tile.  I'm sure with a bit more time someone could come up with a better way to represent these sets than lists, however it should not be too bad as I expect the list will only ever contain a couple of members.  Just be warned that pathological behaviour may arise.  Note the length of source lists is precisely the degree of overlap of boxes with the proviso that subcells only contribute one box.  Actually it hasn't turned out too badly.
There is an edge for every SX.CircuitNode not shared by the two lists.
MergeNodeTiles:
Process merging and area changes in the interior of the tile.
Area adjustment.
Process merging and perim changes at the tile southern and western boundary.
To do this we must count the number of edges at each tile-pair boundary.
AnalyzeNodesInAOIs.
Procedures For Third Per Layer Loop
Corner based checking. The tesselation is enumerated, etc. Fine point: inside/outside (concave corners).
Tile types: Space (0), Current (1), Constraint (2-7).
Each rule has two boolean vectors:
trigger1 identifies whether it is really a corner and gives the orientation.
trigger2 gives the checking rectangle.
CStitching.Enumerate is called to find all rectangles which intersect the checking rectangle. Trigger2 is used to see whether the type is there. If yes, the design rule is checked. If there is connection and it is legal, then it is not flagged as an error. This (CheckValue) is the place where the Euclidean distance would complement the Manhattan distance.
 First add the constraint regions to the geometry.
examine every tile
called from DesignRuleCheckAOIs only
[tile: TilePtr, data: REF ANY] RETURNS [REF ANY] 
logically local to CheckTile
[r: REF SXQuadTree.Rectangle, data: REF ANY]
(local of FindNodeInner, local of FindNode, local of DesignRuleCheckAOIs, local of AnalyzeGeometry)
Compose Clip and recurse
FindNodeInner
[tile: TilePtr, data: REF ANY] RETURNS [REF ANY]  
called from DesignRuleCheckAOIs only
PROC [tile: TilePtr, data: REF ANY] RETURNS [REF ANY] 
Each rule has two boolean vectors:
trigger1 identifies whether it is really a corner and gives the orientation.
trigger2 gives the checking rectangle.
CStitching.Enumerate is called to find all rectangles which intersect the checking rectangle. Trigger2 is used to see whether the type is there. If yes, the design rule is checked. If there is connection and it is legal, then it is not flagged as an error. This (CheckValue) is the place where the Euclidean distance would complement the Manhattan distance.
Check it is really an error.  (Kind of funny sort of empty!   
What we mean is empty of non-$AOI tiles)
Optimize purely local checks.
DesignRuleCheckCorner
Translate the quadrant contents into bit vector values.
Is this really a corner in the terms of this rule?
Bits are ne=8, nw=4, sw=2, se=1.  The check is applied to the quad opposite the generating corner.  (IE rot. 180)
Here are are some diagrams to make it explicit, X=TRUE, O=FALSE
0 - OO     1 - OO     2 - OO     3 - OO
    OO         OX         XO         XX

4 - XO     5 - XO     6 - XO     7 - XO
    OO         OX         XO         XX

8 - OX     9 - OX     10- OX     11- OX
    OO         OX         XO         XX

12- XX     13- XX     14- XX     15- XX
    OO         OX         XO         XX
CheckTile
Since tile are stitched at their North-East and South-West corners these are favoured points from which to DRC.  We exploit the fact that every corner has either 3 or (rarely) 4 edges meeting at it, and thus contains a NE or SW or (rarely) both tile corner at it.
SW corner
Get the quadrants at the SW corner and call DesignRuleCheckCorner
Get the quadrants at the SW corner and call DesignRuleCheckCorner
NE corner
4 way corner, damn it
Get the quadrants at the NE corner and call DesignRuleCheckCorner
Get the quadrants at the NE corner and call DesignRuleCheckCorner
Main Procedure
Process each of the analysis layers.
First per layer loop. The quad-trees are enumerated and the conflict world is constructed. Then the areas of interest are bloated. Finally the quad-tree is instantiated into the geometry world and the nodes are analysed.
The quad-trees are enumerated and the conflict world is constructed. Each rectangle has an area of interest depending on the material. Constraints do not overlap: they are ordered into the technology dependent part; the larger prevails. Every constraint is represented by a number which is an index in a boolean array to infere whether it is there.
Set break point here to look at the conflict world !
SXAccess.sxTech.spinifexLayerNames[layer].layerId
CSMonitor.Monitor [plane: conflictWorld, name: "conflictWorld", paintDark: NIL];
All rectangles where there is no overlap are deleted. Since the area of interest is 1/2 of the maximal interaction distance, at the end there may be regions which contain none of the original material. For this reason the areas of interest are bloated by 1/2 of the maximal interaction distance.
The quad-tree is instantiated into the geometry world. This is done in two steps, because a tile can have only one value. First the electrical carrying stuff is handled, then the constraints.
Now the nodes are analysed. Problem: parasitics. The constraints are put in and resolved (additional complexity for electrical conductivity).
Second per layer loop.  For each conductive region in the geometry worlds, change the "LIST OF REF SX.CircuitNode"s (which have already been compressed into a single node per region) to a REF SX.CircuitNode. Normalises the geometrical representation of nodes (All electrically connected regions are made to point to the same node [which was determined in `AnalyzeNodesInAOIs']).
The loop in plain text:
for every Spinifex layer
for every rectangle of material in the design
get the list of the electrically connected rectangles in the circuit
collapse the attributes (value) of all rectangle to a single instance of the attributes
transform the list consisting of a single element in a single element (attributes).
Third per layer loop. Corner based checking. The tesselation is enumerated, etc. Fine point: inside/outside (concave corners).
Maintenance Aids
Edited on January 3, 1985 11:45:56 am PST, by Jacobi
Fehler umgangen, nicht wirklich korrigiert da nicht verstanden.
Edited on January 3, 1985 4:58:12 pm PST, by Beretta
Tried to improve readability & debuggability.
Took out ComputeConflicts and ResolveConstraints to create a new module SXConflicts. Reason: storage overflow in the compiler.
Edited on January 23, 1985 3:45:47 pm PST, by Beretta
Improved structure
Edited on February 26, 1985 11:46:36 am PST, by Jacobi
stopFlag test feature
Edited on March 6, 1985, by Shand
Made Constraint to node conflict detection more uniform so that OccupyByConstr and OccupyByNode implement same approach.
changes to: OccupyByConstr $Conflict results only if ResolveConstraints[Constraint, Node] # Node.
Edited on March 7, 1985 1:21:40 am PST, by Shand
Removed unnecessary parameters from Tree enumeration procedures
Added Heuristic procedure to override Level-order Conflict Resolution based on value returned by UseLevelOrderHeuristic.
changes to: FlattenCell (local of Flatten), DescendTree (local of DescendCell, local of DescendOneLevel), DescendCell (local of DescendOneLevel)
changes to: UseLevelOrderHeuristic to choose when to apply Level-order Conflict Resolution, ComputeConflicts, OccupyByAppl in case where region is currently occupied by another cell, either DescendOneLevel, or Flatten., OccupyByAppl, ThinLimit, UseLevelOrderHeuristic, OccupyByAppl, DIRECTORY, FlattenTree (local of FlattenCell, local of Flatten), DescendTree (local of DescendCell, local of DescendOneLevel)
Edited on March 7, 1985 2:50:27 am PST, by Shand
Fixed bug in FlattenTree when calling back to bid for Node.  Used to call on subcell's REF Rectangle (boxes.first) rather than topcell's REF Rectangle (applRef.first)
changes to: FlattenTree (local of FlattenCell, local of Flatten) case node
Edited on March 8, 1985 6:04:21 pm PST, by Shand
Added parameter to SXConflicts.ResolveConstraints from TechHandle.
changes to: MixConstraints
Edited on March 9, 1985 12:22:24 pm PST, by Shand
Changed name of CircuitConstraint in SX to Constraint, added tech parameter to ComputeConflicts, changed ResolveConstraints to deal with new constraint resolution representation.
changes to: DIRECTORY, ComputeConflicts, OccupyByNode, ResolveConstraints, node (local of ResolveConstraints), rect (local of ResolveConstraints), ComputeConflicts
Edited on March 13, 1985 0:39:24 am PST, by Shand
Optimizations and enhancements to allow zero extent rules.
changes to: DesignRuleCheckAOIs
Edited on March 19, 1985 6:20:07 pm PST, by Beretta
Added maintenance aids section.
changes to: saveTesselations: new, freeTesselations: new, AnalyzeGeometry: check whether old tessellations hang around and fourth loop is done only if necessary in a separate procedure, SaveTesselations: new, GetTesselation: new, FreeTesselations: new
Edited on March 27, 1985 8:02:00 pm PST, by Beretta
procedures MixConstraints, CheckTile made global
Edited on April 8, 1985 3:36:29 pm PST, by Jacobi
reformatted
Edited on June 29, 1985 8:25:03 pm PDT, by Beretta
Tried to fix Quad Tree stuff
gbb December 3, 1985 4:13:28 pm PST
Partially re-re-restored formatting; cleaned up.
gbb February 10, 1986 11:46:37 am PST
Tracked change in Compiler and merged in again ComputeConflicts and ResolveConstraints., SXLayersImpl, BEGIN, ComputeConflicts, ResolveConstraints, AnalyzeGeometry


�Ê+ç˜
codeš
œ™Kšœ
Ïm
œ7™BIheadš
œ»
™»
K™-K™8J™4K™)K™/—
unitš
Ïk	˜	Kšžœ
žœK˜SKšœ	žœA˜OKšœ	žœW˜eKšœžœØ
˜è
Kšœžœ˜Kšžœ
žœÄ
˜Ì
Kšœ	žœ˜*Kšœžœ˜2Kšœ	žœ˜Kšœžœg˜wKšœžœ
˜—
code2šÐblœžœ
ž˜Mšžœ
žœ"žœ4˜bMšžœž˜—š
œ™Mšœ	žœ˜ Kš	œ	žœ
žœžœžœ˜Nšœžœžœ˜!Kšœžœ˜'Kšœžœžœ
˜K˜šœžœžœ
žœžœ
žœ
˜MK™K—šœžœžœ
žœžœ
žœ
˜MK™I—Kšœžœžœ
žœžœ
žœ
žœ
žœžœ
žœ˜`M™Fš
œ˜K™K—š
œ˜K™I—Mš
œ™Kšœžœžœ
˜Kšœžœžœ
˜—L™šÏnœžœžœ(žœžœž˜kK™]Kšœžœ1˜>Kšžœ*žœ)˜\KšžœÏc˜—š œžœžœ%žœ
žœžœ
žœž˜š
Kš
œÜ™ÜM•StartOfExpansiona -- [plane: REF CornerStitching.Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY] -- šœžœ˜š
œ1™1JšÏe
œƒ
™�
Jš¢œ¯
™½
Jš¢œ;™PJš¢œ†
™Š
—šÏbœž˜)Kšœžœžœžœ™5šžœ
žœ
ž˜šœžœžœž˜ KšžœG˜IK™8—šœžœžœ
ž˜$Kšœ�
œ
™Kš
œ7˜7—š
œ˜K™Yšžœžœ
ž˜Kš
œ2˜2Kš
œ˜Kš
ž˜—Kšžœ
žœN˜U—šœžœ˜šžœ
žœdž˜nKš
œ7˜7—K™—šžœ˜
šžœžœ
ž˜Kš
œB™BKš
œ1˜1—Kšžœ
žœF˜M——Kšžœ¡Ðce˜—š£œž˜+Kšœžœžœžœ™5šžœ
žœ
ž˜šœžœžœž˜ KšžœG˜IK™8—šœžœ
˜šžœ
žœ%žœ=ž˜rKš
œ7˜7——šœž˜!Kš
œ%˜%Kš
œ˜Kšžœ
˜—šœžœž˜K™'Kšœžœ
žœO˜bKš
žœžœ žœ
žœ$žœ7˜�
šžœ
žœ
žœ ž˜/Kš
œ8˜8—Kšžœ
˜—šžœ˜Kš
œ-™-šžœžœ
ž˜Kš
œB™BKš
œ1˜1—Kšžœ
žœF˜M——Kšžœ¡¤˜—š£œž˜)Kšœžœžœžœ™5Kš	œ¢œ¢œ$¢œ¢œ<™�
šžœ
žœ
ž˜šœžœžœž˜ KšžœG˜IK™8—šœžœž˜šžœ
žœ(ž˜5KšžœH˜J—Kšœžœ˜Kšžœ
˜—š
œ˜šžœ
ž˜šžœ"žœž˜6Kšœžœ˜'—šžœ
ž˜
K™%Kšœ,žœ˜1K™2Kš
œ˜Kšœžœ˜Kšžœ
˜——K™)—Mšœžœžœ˜2šžœ˜
šžœžœ
ž˜Kš
œB™BKš
œ1˜1—Kšžœ
žœF˜M——Kšžœ¡¤˜—š œžœžœ)ž˜IKšœžœžœ!˜;š œžœžœžœžœž˜Wš
 œžœžœžœžœ	žœ
ž˜Qš
œ%˜%Kš
œl˜lKš
œ	˜	—Kšžœ¡
˜—š œžœžœž˜7Kš
œ(™(šžœ5žœžœ
ž˜Jšžœžœ
ž˜,šœžœ
˜Kšœžœ,˜1šžœž˜Kš
œW˜W—Kš
œ˜—šœžœ˜Kšœžœ+˜0šžœž˜Kš
œR˜R—Kš
œ˜—šœ	žœ˜šžœ<žœ˜Dš
œ
˜
Kš
œ	˜	š
œ'˜'Kš
œi˜iKš
œ˜Kš
œ˜Kš
œ˜—Kš
œ5˜5—K˜——Kšžœžœ¡˜(—Kšžœ
˜—M™1Kšžœžœ
žœ
žœ
˜)šžœžœžœ
ž˜8Kš
œ ˜ —šžœžœžœ
ž˜8Kš
œ ˜ —šžœžœžœ
ž˜7Kš
œ˜—šžœžœžœ
ž˜7Kš
œ˜—Kšžœ¡¤˜—Mšœžœ˜ Kšœžœu˜ƒ
Kš
œY˜Yšžœ	žœ
ž˜Kš
œ˜—Kšžœ¡¤˜—Mš
œ2˜2Kšžœ¡¤˜—š œžœžœ*ž˜RK™ 
Kšœžœ
˜š£	œž˜&Kšœžœ$žœžœ™?šžœ
žœ
ž˜šœžœžœž˜ KšžœG˜I—šœžœžœ
ž˜$Kšžœ:˜<—Mš
œN˜NMšœžœA˜GMšžœž˜—Kšžœ¡¤	˜—š£œž˜(Kšœžœ$žœžœ™?šžœ
žœ
ž˜šœžœžœž˜ KšžœG˜I—šœžœžœž˜)Kšžœ:˜<—š
œ˜Kšžœ	žœ3˜B—šœžœž˜Kšœžœ
žœO˜bšžœ
žœ!ž˜+Kš
œ8˜8—Kšžœ
˜—Mšžœžœ
˜—Kšžœ¡¤˜—š£	œž˜&Kšœžœ$žœžœ™?šžœ
žœ
ž˜šœžœžœž˜ KšžœG˜I—šœžœ˜šžœ
žœ(ž˜5Kšžœ:˜<——š
œ˜Kšžœ
žœ3˜C—MšœžœA˜GMšžœžœ
˜—Kšžœ¡¤	˜—š œžœžœžœžœž˜Wš
 œžœžœžœžœ	žœ
ž˜QKš
œ0™0š
œ%˜%š
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ	˜	—Kšžœ¡¤˜—š œžœžœž˜7Kš
œ0™0Kšžœžœ
žœ
žœ
˜šžœ5žœžœ
ž˜Jšžœžœ
ž˜,šœžœ
˜Kšœžœ,˜1šžœž˜Kš
œP˜P—Kš
œ˜—šœžœ˜Kšœžœ,˜1šžœž˜Kš
œO˜O—Kš
œ˜—šœ	žœ˜šžœ<žœ˜Dšžœž˜š
œ
˜
Kš
œ	˜	š
œ'˜'Kš
œh˜hKš
œ˜Kš
œ˜Kš
œ˜—Kš
œ5˜5——šžœ˜Kšœžœ,˜1šžœž˜Kš
œJ˜J—Kš
œ
˜
—K˜——Kšžœžœ
˜—Kšžœ
˜—šžœžœžœ
ž˜<Kš
œ!˜!—šžœžœžœ
ž˜8Kš
œ!˜!—šžœžœžœ
ž˜7Kš
œ ˜ —šžœžœžœ
ž˜7Kš
œ ˜ —Kšžœ¡¤˜—Mš
œ™Kšœžœ˜ Kšœžœu˜ƒ
Kš
œY˜YKš
œ˜Kš
œ˜Kš
œ˜Kšžœ¡¤˜—Mšœžœžœ˜7Mš
œ ˜ Kšœ¡˜<Kš
œ4˜4Kš
œU˜UKš
œ˜Kšžœ¡¤˜—Nš
Ïl™K™®
Kšžœžœ
žœ
žœ
˜šžœ5žœžœ
ž˜Jšžœžœ
ž˜,šœžœ	˜Kš
ρ
™Å
Kš
œn˜n—šœžœ˜Kš
œk˜k—šœžœ
˜š
œh˜hK™ø
——Mšžœžœ
˜—Kšžœ
˜—šžœžœž˜9š
œ?˜?K™ —Kšžœ
˜—šžœž˜KšžœC˜E—Kšžœ¡¤˜—š œžœ
žœ
žœžœžœ˜=Kšžœ	žœ
žœ
žœ˜šžœžœ
žœ
˜šœžœ˜šžœžœ
ž˜Kšœžœžœ˜8Kšžœžœžœ˜—K˜—Kšžœžœ
žœ˜—Kšœ¡˜—š œžœžœžœ
žœžœ
žœžœžœ
žœž˜Ž
Kšœ¢œ]™Ž
Mš
£5™5šžœ
žœ
ž˜šœžœ˜"Kš
£'˜'KšœžœC˜NKšžœžœ
žœ
žœ?˜TKš
£›
˜›
Kšœ<£œ
™VKš
£'™'š
£˜Kš
£#˜#Kš
£1˜1—Kšžœ	˜Kšœ¡¤(˜.—šœžœ
˜Kšœžœ.žœ˜GKšžœžœ
žœ
žœ˜ šžœ
ž
˜š
£7˜7Kš
£#˜#Kš
£L˜L—Kšžœ˜—Kš
œ˜—šœžœ˜Kšœžœ.žœ˜GKšžœžœ
žœ
žœ˜ šžœ
ž
˜š
£7˜7Kš
£#˜#Kš
£L˜L—Kšžœ˜—Kš
œ˜—Mšžœž˜—Kšžœ¡¤˜—š
œ#™#Kš
œ1™1—š
 œžœ	žœ
žœžœ;˜zJšžœ2ž˜>J™§š£œž˜(Kšœžœ
žœžœžœ
žœ™1šžœž˜Kš
œW˜W—Kšžœ¡˜—Mšœžœ.˜=Kš
œH˜HKš
œO˜OKš
œ,˜,Kš
œ(˜(Kšžœ¡¤˜—š œžœ	žœ
žœžœ!žœžœ žœ)žœžœžœ
žœ
žœžœ
žœ„
˜‚Jšžœ)ž˜5J™^š	 œžœžœ#žœ	ž˜Qš œžœžœ#ž˜NKšœžœžœE˜hKšžœ¡˜—Mš
œ™Kšœžœ>žœžœ
žœžœB˜©
Mšžœ#žœ
žœ
˜1šžœ5žœžœ
ž˜JKšœžœVžœžœ
žœžœB˜Á
šžœ
žœ"žœ˜.šžœžœ
ž˜,šœ	žœ˜Kšœžœ˜ Kšœ
žœ˜Kšœžœd˜lKšœžœ7žœžœ
žœžœB˜£
Kšœžœn˜xMš
œs˜sKšžœ
žœ
žœ
žœ
˜Kšœ£
žœ¡@œw˜ùKšœ¡˜ —šœžœ
žœ˜Kš
œc™cKšœžœ
žœžœžœžœžœZžœ˜¦
Kš	œžœ
žœ
žœžœ%˜VKšœ	žœ
žœ
žœ
žœžœ˜1Kš
œ9˜9šžœ
žœ
ž˜šžœ
žœ-ž˜7šžœžœ
ž˜&š
œ	žœ
žœ
žœ
žœ¡³
˜Ú
šžœžœžœžœ˜6Kš	œžœ
žœ
žœ
žœ˜*Kš	œ
žœ
žœ
žœ
žœ
˜(šžœžœ
ž˜K™Kšžœžœ
žœ
˜K˜Kšžœ
˜—šœžœžœ
žœ
˜Kšžœ˜#Kšžœ
žœ˜—Kš
œG˜GK˜——Kšžœžœ
˜——Kš
œ˜Kšžœ
˜—Kšœ¡˜—Kšœžœ6˜=Kšžœžœ
¡&˜7—K˜
—Kšžœ¡4˜=—š
œ
˜
šžœžœ
ž˜ š
œ$˜$Kš
œK˜K——šžœžœ
ž˜ š
œ$˜$Kš
œK˜K——šžœžœ
ž˜š
œ#˜#Kš
œK˜K——šžœžœ
ž˜š
œ#˜#Kš
œK˜K——K˜
—Kšžœ¡˜—J™Jš
œ™Kš
œ˜Kš
œ$˜$Kšžœ¡˜—š œžœ	žœ
žœžœ>ž˜~J™‰
š œÐck
ž˜+Jšœžœ
žœžœžœ
žœ
™0Jš
œ,™,Jš
œ»™»š 	œžœžœ
žœ
žœžœžœž˜LJš
œF™Fš 
œžœžœ
žœ
žœžœžœž˜Oš
žœžœ
žœ
žœžœžœ
ž˜?Jšœžœ
žœ
žœ˜#šžœžœ
ž˜Jšžœžœ
žœ¡˜3Jš
œ
˜
Jšžœ
˜—Jšžœžœ
žœ¡˜0Jšžœ
˜—Jšžœ¡
˜—Mšžœ:˜@Jšžœ¡¤	˜—Mš
œ™Jšžœžœ
žœ
žœ
˜)šžœžœ
ž˜šœžœ
žœ
žœ˜'J™=Jšœžœ
žœ
žœ˜/Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ/˜6šžœžœ
ž˜Jšœžœ
žœžœ˜4Jšžœ	žœ"˜1J™JšžœU˜WJ˜Jš
œ˜Jšžœ
˜—™LJ™H—šžœ,žœž˜Sšžœžœ
žœ
žœžœ
ž˜<š	œ
žœ
žœ
žœ
žœ˜,Kšœžœ
žœžœ ˜;Kšžœ	žœ"˜1KšžœYžœžœ˜Ÿ
K˜—Kšœžœžœ¡	˜.Kšžœž˜—šž¢˜šžœž˜KšœGžœžœ˜‹
——Kšžœ¢˜—šžœ*žœž˜Qšžœžœ
žœ
žœžœ
ž˜:šœžœ
žœ
žœ˜+Jšœžœ˜šžœ
žœžœ
˜2Jš
œ!˜!—KšžœXžœžœ˜ž
J˜—Jšœžœžœ¡	˜.Jšžœž˜—šžœ
žœž˜KšžœEžœžœ˜‰
—JšžœÐew˜—šžœ,žœž˜Sšžœžœžœž˜4KšžœEžœžœ˜‹
—Jšžœ¢	˜—šžœ*žœž˜Qšžœžœžœž˜1KšžœEžœžœ˜‹
—Kšžœ¡¤˜—J˜—Jšžœž˜—Jšžœ¡¤˜—Mš
œ™Kš
œb˜bJšžœ¢˜—L™#Mšœžœžœžœžœžœ
žœ%žœ
žœ
žœ˜›
Kšœ
žœžœWžœ
žœ
žœ
žœžœ
žœžœ
žœ
˜»
š œžœ
žœ
žœžœ
žœ:žœgž˜é
š
œž
™ž
™"J™LJ™&—J™å—Kšœžœ
žœ¡0˜SKšœ
žœžœ¡+˜SM™2š
žœžœ
žœ
žœ8žœžœ
ž˜`Kšœžœvžœ˜›
Kš
œm˜mš
žœžœ
žœ
žœ<žœžœ
ž˜rKš
œW˜WKšžœ
˜—Kšžœ
˜—M™Kš
œ„
˜„
Kš
œ|˜|Jšžœ¡¤˜—š£œž˜+Jš
œ$™$Jšœžœ
žœžœžœ
žœ™1Jšœžœ
žœ˜#Jšœžœ
žœ˜'šžœžœžœdž˜€
Kšœžœžœs˜“
—Jšžœ¡¤˜—š œžœ
žœ0žœžœžœ
žœž˜mJš
œ™Jšœžœ˜Jš œžœžœ
žœ˜(˜
Jšžœžœ˜(š 
œžœžœžœžœ
žœ
žœ
ž˜aš£
œž˜-Jšœžœžœ
žœ
™,Jš
œc™cšžœžœ
ž˜"šœžœžœ'žœ˜HJšœžœ˜Jšœ
žœ
žœ
žœ
˜Jš
œ<˜<Jšžœ
žœ
žœ˜/J˜—šœžœ˜J™Jšœžœ<˜Gšœžœc˜kJš
œ˜Jš
œ˜—Jšœžœ
˜-Jš
œ˜—Jšžœ
˜—Jšžœ¡¤
˜—Mš
œ
™
JšœNžœ
˜RJšžœ¡¤
˜—Mšœžœ˜"Jšžœžœ
žœ˜Jšžœ	žœ˜J˜
—Jšžœ¡¤˜—š£	œž˜&Jšœžœ
žœžœžœ
žœ™2Jš
œ$™$Jšœžœ˜#š œžœžœžœ
žœ
žœžœ˜VJš
ž˜š 	œžœžœ
žœžœ-ž˜iš œžœžœ
žœžœžœ
žœž˜=šžœžœ
ž˜Jšœžœ
žœžœ˜&šœžœ˜Jš
£‹
˜‹
Jšžœžœ
žœM˜pJšžœ^˜dJ˜—Jšžœžœžœ
žœ˜—Jšžœ
˜—š œžœžœ
žœžœžœžœ
žœž˜Jšžœžœ
ž˜Jšœžœ
žœžœ˜&šœžœ˜Jšžœžœ
žœK˜nJšžœ4˜:J˜—Jšžœžœžœ
žœ˜—Jšžœ
˜—š£œž˜+Jšžœžœ
žœžœžœ
žœ™6Jš
œ!˜!Jšžœ
˜—š 
œžœ	žœ
žœžœ
ž˜9™"J™LJ™&—J™åMšžœžœ
žœ
žœ
˜)šžœžœ
ž˜šœžœ
žœ˜Jšžœžœžœ
žœ
˜,šžœžœžœ
žœ"žœž˜hJšžœ
˜—J˜—šœžœ˜Jšžœžœ
žœ
˜(šžœžœžœ
žœžœ:£˜ˆ
Jš£uœž˜{Jšžœ
˜—J˜—š	œžœ
žœ
žœ
žœ˜%Kšžœl˜n—šžœ˜šžœžœ
žœ˜Jšžœžœ
žœ
žœ
˜-J˜
—Jšžœ
žœ:˜AJ˜——Jš
œg™gšžœžœ˜,š
œ˜š
œ8˜8Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜——šœžœ¡˜$Kšœžœ•
˜�
Kš
œT˜TKšœž˜K˜
——Jšžœ¡¤
˜—Mšœžœžœ
˜Jšœžœ˜Jšœžœ˜šžœ	žœ˜J™šžœž˜Jš
œC˜C—šžœž˜Jš
œC˜C—šžœž˜Jš
œC˜C—šžœž˜Jš
œC˜C—J˜
—šžœ˜šžœ	ž˜˜š
œ)˜)Kš
œˆ
˜ˆ
Kš
œ˜Kš
œ˜—š
œ)˜)Kš
œ…
˜…
Kš
œ˜Kš
œ˜—K˜—š
œ˜š
œ)˜)Kš
œƒ
˜ƒ
Kš
œ˜Kš
œ˜—K˜—Kš
ž˜—K˜
—Jšžœ¡¤	˜—J˜Jš
¥™Jšœžœ!˜(Jšœžœ!˜)Jšœžœ"˜+Jšœžœ"˜+Jšœžœ
žœžœ
˜Jšžœžœ
žœ
žœ
˜)š
žœžœ
žœ
žœ0žœ
žœ
ž˜^Jšœžœ
žœ ˜,Jšœ
žœžœ
žœ˜4Jšœ
žœ˜Jšœžœ
˜J™7šžœžœž˜ šžœ
žœ
ž˜šœžœ
žœ˜šžœžœ˜%Jš
œ"˜"Jš
œ˜J˜
—J˜—šœžœ˜šžœžœ˜!Jš
œ"˜"Jšžœžœžœ
žœ˜FJ˜
—J˜—šœžœ
žœ
žœ˜'Kšžœî
˜ð
Jš
œ˜—šžœ˜šžœ
žœ
žœ˜Jšžœžœ"˜FJš
œ
˜
—Jšžœ
žœH˜OJš
œ˜——Jšžœ¡¤:˜F—J™2J™qJš
Ïf‚™‚šžœ
ž˜Jšœžœ
˜
Jš
œ#˜#Jš
œ"˜"Jšœžœ
˜
Jš
œ$˜$Jš
œG˜GJšœžœ
˜
Jš
œ#˜#Jš
œ$˜$Jšœžœ
˜
Jš
œG˜GJš
œ%˜%Jšœžœ
˜Jš
œ&˜&Jš
œ&˜&Jšœžœ
˜Jšžœžœ
˜—Jšžœ
˜—Jšžœ¡¤˜—Mš
£	™	J™‡Jšœžœžœ˜$Jš
œ=˜=Jšœžœ˜Mš
œ	™	šžœIžœ˜Qšžœžœ˜&Kšžœžœ
žœ¡J˜ušžœ˜šžœžœ
˜#KšžœD˜F—Kš
œA™Aš
œ˜Kš
œK˜KKš
œ˜Kš
œ˜—Kš
œ
˜
—K˜
—šžœ¡*˜1Kšžœžœ
žœ
¡˜;šžœ˜Kš
œA™AKš
œ�
˜�
K˜
—K˜
—K˜—Mš
œ	™	šžœIžœ˜Qšžœžœ˜&šžœžœ˜&K™Kš
œ˜šžœž˜%Kš
œ˜Kšžœ
˜—Kš
œ�
˜�
K˜
—šžœ˜šžœžœ
˜#KšžœJ¡
˜M—Kš
œA™AKš
œ�
˜�
K˜
—K˜
—šžœ¡*˜1Kšžœžœ
žœ
¡˜;šžœ˜Kš
œA™AKš
œ‚
˜‚
K˜
—K˜
—K˜
—Jšžœ¡˜—L™š œžœ
žœžœ
žœž˜?Jš
œ$™$Jšœžœ
žœ˜#Jš
œ!˜!Mšžœžœ ˜8Mš¥œ×
™Ü
šžœžœžœ*ž˜OKš
œ\˜\Kš
œ\˜\Mš
œJ˜JJšžœ&žœ
žœ
žœ
˜6Jšžœžœ
žœ
žœ
˜)š
œR˜RJš
œÜ™Ü—Mšœ£œ%™4Jš
œ1™1Jš
œP™Pš
œ\˜\J™§—Jš
œ¿
™¿
Kš
ϓ
˜ì
J™�
Jš
œ0˜0Jšžœ¡¤1¡¤˜b—M˜Mš¥œô™ú™™™-J™DJ™WJ™S———šžœžœžœ(ž˜MJš
œ>˜>Jšžœžœ
žœ
žœ
˜)šžœžœ
žœ
žœžœKžœžœ
ž˜Ž
Kš
œ7žœžœžœ
žœ
žœ
žœ˜‚
Jšžœ
˜Jšžœ
˜——Jšžœ˜M˜Mš¥œy™~šžœžœ(ž˜MKš
œ>˜>Kš
œ>˜>Mš
œV˜VKšžœ
˜—M˜Mšžœžœž	œ!˜VJšžœ¡¤˜—Lš
œ™š œžœ
žœžœžœž˜:Jš
œ˜Jšžœ
˜—š œžœ
žœ
žœžœ	žœžœž˜{Jšžœžœžœžœ˜KJšžœ
˜—š	 œžœžœ
žœž˜8šžœžœ(ž˜MJš
œ4˜4Jš
œ4˜4Jšžœ
˜—Jš
œ˜Jšœž˜Jšžœ
˜—Nšžœ
˜š
œ4™4K™?—™4Kš
œ-™-Kš
œ~™~—™5K™—š
œ6™6K™—™!Jšœ@Ïrœ©œ™xJšœ©œG™a—™0J™?JšœaÐenœ
™xJšœ©œ©
œ1©
œ™�
Jš
œ©œ8© œDªœªœ
©Wœ)©
œ1™˜—™0Jš
œ¦
™¦
Jš
œJ™J—™0Kš
œB™BKšœ©™—™1JšœO©œ
©œ7™²
Jšœ©Cœ©œ©™£
—™1K™:Kšœ©™—™3Kš
œ™Kš
œ©œ©œ©œo©œ©œ©œ™û
—™3Kš©œ©™0—™1K™—™2K™—™#K™0—™%Kšœ/¢œ¢©L™£
—K™K™—…—ŽöU