-- File: DisjointSplit.mesa
-- Splits symbols into non-overlapping segements
-- Written by Martin Newell/Dan Fitzpatrick February 1981
-- Last edited (Pilot): August 6, 1981 3:46 PM

DIRECTORY

DisjointGatherDefs: FROM "DisjointGatherDefs" USING [Gather],
DisjointSplitDefs: FROM "DisjointSplitDefs",
DisjointTypes: FROM "DisjointTypes" USING [DisCell, Symbol, Instance,
Rectangle, PIP, Geometry],
DisjointAllocDefs: FROM "DisjointAllocDefs" USING [AllocateRectangle,
AllocateDisCell, AllocatePIP, FreePIP, AllocateGeometry, FreeGeometry, Alloc, Free],
Inline: FROM "Inline" USING [LowHalf];

DisjointSplit: PROGRAM
IMPORTS DisjointGatherDefs, DisjointAllocDefs, Inline
EXPORTS DisjointSplitDefs =
BEGIN
OPEN DisjointGatherDefs, DisjointAllocDefs, DisjointTypes, Inline;

--PrimInstance Edges
PIEdge: TYPE = LONG POINTER TO PIEdgeRecord;
PIEdgeRecord: TYPE = RECORD [
next: PIEdge,
x,yMin,yMax: REAL,
up: BOOLEAN,
pi: Instance
];

PIEdgeList,PIActiveList: PIEdge;
PIyPrev,PIyCurr,PIyNext: REAL;

Split: PUBLIC PROCEDURE[symbol: Symbol] =
--This procedure takes a list of PrimInstances, pi, and a list of windows,
-- windows, that mask pi, and generates a list of
-- disjoint cells, DisCell, within the window.
BEGIN
pi: Instance ← symbol.insts;
windows: Rectangle ← symbol.windows;
edge,newPIActiveList,endOfNewPIActiveList:PIEdge;
xCurr,pieceL,bottom,top: REAL;
PISet: PIP; --list of PrimInstances covering current region of swath
dcList: DisCell;
StartPiece: PROCEDURE[x: REAL] =
BEGIN
pieceL ← x;
END;
EndPiece: PROCEDURE[x,yMin,yMax: REAL, piSet: PIP] =
BEGIN
newdc: DisCell;
copyPISet,copyPISetEnd: PIP;
dc: DisCell;
IF PISet=NIL THEN RETURN;
IF yMin>=yMax OR pieceL>=x THEN RETURN;
IF (dc←Exists[piSet])#NIL THEN AddWindow[dc, pieceL,yMin,x,yMax]
ELSE
{newdc ← AllocateDisCell[];
copyPISet ← copyPISetEnd ← NIL;
FOR pi:PIP ← piSet, pi.next UNTIL pi=NIL DO
copypi: PIP ← AllocatePIP[];
copypi↑ ← [
next: NIL,
inst: pi.inst
];
IF copyPISet=NIL THEN copyPISet ← copyPISetEnd ← copypi
ELSE
{copyPISetEnd.next ← copypi;
copyPISetEnd ← copypi;
};
ENDLOOP;
newdc↑ ← [
next: NIL,
geom: NIL, --***!!!NOT RIGHT!!!
insts: copyPISet,
windows: AllocateRectangle[],
symbol: NIL
];
newdc.windows↑ ← [
next: NIL,
l:pieceL, b:yMin, r:x, t:yMax
];
EnterDC[newdc];
};
END;
AddToEndOfNewPIActiveList: PROCEDURE[edge: PIEdge] =
BEGIN
edge.next ← NIL;
IF newPIActiveList=NIL THEN
newPIActiveList ← endOfNewPIActiveList ← edge
ELSE
{endOfNewPIActiveList.next ← edge;
endOfNewPIActiveList ← edge;
}
END;

IF pi=NIL THEN
{PartitionGeometry[symbol, NIL]; --to get clipping to symbol boundary
RETURN;
};
[PIEdgeList,bottom,top] ← BuildPIEdgeList[pi, windows];
PIActiveList ← newPIActiveList ← endOfNewPIActiveList ← NIL;
PIyPrev ← PIyCurr ← bottom;
PIyNext ← top;
InitDCSet[101];

UNTIL (PIEdgeList=NIL AND PIActiveList=NIL) OR PIyPrev>=top DO --once per swath
windowdepth: INTEGER ← 0;
PISet ← NIL;
FOR edge ← GetPIEdge[], GetPIEdge[] UNTIL edge=NIL DO
xCurr ← edge.x;
IF PIyCurr>PIyPrev AND edge.yMin<PIyCurr THEN
IF edge.pi=NIL THEN --a window edge
{IF windowdepth=0 THEN StartPiece[xCurr];
windowdepth ← IF edge.up THEN windowdepth+1 ELSE windowdepth-1;
IF windowdepth=0 THEN EndPiece[xCurr,PIyPrev,PIyCurr,PISet];
}
ELSE
{IF windowdepth#0 THEN EndPiece[xCurr,PIyPrev,PIyCurr,PISet];
IF edge.up THEN PISet ← PIInsert[PISet, edge.pi]
ELSE PISet ← PIRemove[PISet, edge.pi];
IF windowdepth#0 THEN StartPiece[xCurr];
};
IF edge.yMax>PIyCurr THEN
{AddToEndOfNewPIActiveList[edge];
PIyNext ← MIN[PIyNext,edge.yMax];
}
ELSE FreePIEdge[edge];
ENDLOOP;
PIActiveList ← newPIActiveList;
newPIActiveList ← NIL;
IF PIEdgeList#NIL THEN PIyNext ← MIN[PIyNext,PIEdgeList.yMin];
PIyPrev ← PIyCurr;
PIyCurr ← PIyNext;
PIyNext ← top;
ENDLOOP;
dcList ← MakeDCList[];
PartitionGeometry[symbol, dcList];
--PrintDisCells[dcList];
Gather[symbol, dcList];
END;

BuildPIEdgeList: PROCEDURE[pi: Instance, windows: Rectangle]
RETURNS[edgeList: PIEdge, bottom,top: REAL] =
--Build edge list of pi edges and window edges.
--Window edges will have a NIL PrimInstance
--bottom and top are extrema of all edges
--insertion sort for now
BEGIN
bottom ← windows.b;
top ← windows.t;
edgeList ← NIL;
FOR p:Instance ← pi, p.next UNTIL p=NIL DO
s: Symbol ← p.symbol;
l: REAL ← s.windows.l+p.xOffset;
b: REAL ← s.windows.b+p.yOffset;
r: REAL ← s.windows.r+p.xOffset;
t: REAL ← s.windows.t+p.yOffset;
edgeList ← InsertPIEdges[edgeList, l,b,r,t, p];
bottom ← MIN[bottom,b];
top ← MAX[top,t];
ENDLOOP;
FOR rec:Rectangle ← windows, rec.next UNTIL rec=NIL DO
edgeList ← InsertPIEdges[edgeList, rec.l,rec.b,rec.r,rec.t, NIL];
bottom ← MIN[bottom,rec.b];
top ← MAX[top,rec.t];
ENDLOOP;
END;

InsertPIEdges: PROCEDURE[edgeList: PIEdge, l,b,r,t: REAL, pi: Instance]
RETURNS[PIEdge] =
--Create and insert edges corresponding to given rectangle into edgeList
BEGIN
e1: PIEdge ←
AllocatePIEdge[l,b,t,TRUE,pi];
e2: PIEdge ←
AllocatePIEdge[r,b,t,FALSE,pi];
eptr: LONG POINTER TO PIEdge;
--find where e1 goes
FOR eptr ← @edgeList,@eptr.next UNTIL eptr↑=NIL DO
IF PIEdgeLessThan[e1,eptr↑] THEN EXIT;
ENDLOOP;
--and insert it
e1.next ← eptr↑;
eptr↑ ← e1;
--continue search for position of e2
FOR eptr ← eptr,@eptr.next UNTIL eptr↑=NIL DO
IF PIEdgeLessThan[e2,eptr↑] THEN EXIT;
ENDLOOP;
--and insert it
e2.next ← eptr↑;
eptr↑ ← e2;
RETURN[edgeList];
END;

PIInsert: PROCEDURE[piSet: PIP, pi: Instance] RETURNS[newpiSet: PIP] =
-- Simply search for it, for now
BEGIN
pp: LONG POINTER TO PIP;
p: PIP ← NIL;
--find where pi goes
FOR pp ← @piSet, @pp.next UNTIL pp↑=NIL DO
p ← pp↑;
IF p.inst=pi THEN RETURN[piSet]; --already there
IF AddressLessThan[pi,p.inst] THEN EXIT;
ENDLOOP;
--and insert it
p ← AllocatePIP[];
p.next ← pp↑;
p.inst ←pi;
pp↑ ← p;
RETURN[piSet];
END;

PIRemove: PROCEDURE[piSet: PIP, pi: Instance] RETURNS[newpiSet: PIP] =
BEGIN
pp: LONG POINTER TO PIP;
p: PIP ← NIL;
FOR pp ← @piSet, @pp.next UNTIL pp↑=NIL DO
p ← pp↑;
IF p.inst=pi THEN EXIT;
ENDLOOP;
pp↑ ← pp.next;
IF p#NIL THEN FreePIP[p];
RETURN[piSet];
END;

AddressLessThan: PROCEDURE[p1,p2: LONG POINTER] RETURNS[BOOLEAN] =
BEGIN
c1: LONG CARDINAL ← LOOPHOLE[p1];
c2: LONG CARDINAL ← LOOPHOLE[p2];
RETURN[c1<c2];
END;

GetPIEdge: PROCEDURE RETURNS[edge: PIEdge] =
--Get edge from PIActiveList or PIEdgeList that crosses swath PIyPrev
-- to PIyCurr. Also returns edges that start at PIyCurr
BEGIN
IF PIActiveList=NIL THEN
IF PIEdgeList=NIL OR PIEdgeList.yMin>PIyCurr THEN RETURN[NIL]
ELSE {edge ← PIEdgeList; PIEdgeList ← PIEdgeList.next}
ELSE
IF PIEdgeList=NIL OR PIEdgeList.yMin>PIyCurr THEN
{edge ← PIActiveList; PIActiveList ← PIActiveList.next}
ELSE --both candidates
IF PIActiveList.x<PIEdgeList.x THEN
{edge ← PIActiveList; PIActiveList ← PIActiveList.next}
ELSE {edge ← PIEdgeList; PIEdgeList ← PIEdgeList.next};
edge.next ← NIL;
END;

PIEdgeLessThan: PROCEDURE[e1,e2: PIEdge] RETURNS[BOOLEAN] =
BEGIN
RETURN[e1.yMin<e2.yMin OR (e1.yMin=e2.yMin AND e1.x<e2.x)];
END;

InitDCSet: PROCEDURE[length: CARDINAL] =
BEGIN
DCTable ← ALL[NIL];
END;

Exists: PROCEDURE[pip: PIP] RETURNS[DisCell] =
--determine if table contains a dc with same list of priminstances
--return NIL if not
BEGIN
h: CARDINAL ← Hash[pip];
FOR d:DisCell ← DCTable[h], d.next UNTIL d=NIL DO
IF SameInstances[pip,d.insts] THEN RETURN[d];
ENDLOOP;
RETURN[NIL];
END;

EnterDC: PROCEDURE[dc: DisCell] =
--add dc to set
BEGIN
h: CARDINAL ← Hash[dc.insts];
dc.next ← DCTable[h];
DCTable[h] ← dc;
END;

MakeDCList: PROCEDURE RETURNS[dcList: DisCell] =
--convert Set of DisCells to a list, and free table
BEGIN
nextdc: DisCell;
dcList ← NIL;
FOR i:CARDINAL IN [0..LENGTH[DCTable]) DO
FOR dc:DisCell ← DCTable[i],nextdc UNTIL dc=NIL DO
nextdc ← dc.next;
dc.next ← dcList;
dcList ← dc;
ENDLOOP;
ENDLOOP;
END;

SameInstances: PROCEDURE[pip1,pip2: PIP] RETURNS[BOOLEAN] =
BEGIN
DO
IF pip1=NIL THEN RETURN[pip2=NIL];
IF pip2=NIL THEN RETURN[pip1=NIL];
IF pip1.inst#pip2.inst THEN RETURN[FALSE];
pip1 ← pip1.next;
pip2 ← pip2.next;
ENDLOOP;
END;

AddWindow: PROCEDURE[dc: DisCell, l,b,r,t: REAL] =
--merge window l,b,r,t into windows of dc
--b will always be = top of existing window if they can be merged
BEGIN
w: Rectangle;
FOR w ← dc.windows, w.next UNTIL w=NIL DO
IF w.t=b AND w.l=l AND w.r=r THEN --extend existing window
{w.t ← t;
RETURN;
};
IF w.t<b THEN EXIT; --all remaining windows are from earlier swaths
ENDLOOP;
--create new window
w ← AllocateRectangle[];
w↑ ← [
next: dc.windows,
l:l, b:b, r:r, t:t
];
dc.windows ← w;
END;

Hash: PROCEDURE[pip:PIP] RETURNS[CARDINAL] =
BEGIN
h: CARDINAL ← 0;
FOR p:PIP ← pip,p.next UNTIL p=NIL DO
h ← h + LowHalf[p.inst];
ENDLOOP;
RETURN[h MOD LENGTH[DCTable]];
END;

DCTable: ARRAY [0..101] OF DisCell;

--***

AllocatePIEdge: PROCEDURE[x,yMin,yMax: REAL, up:BOOLEAN, pi: Instance]
RETURNS[edge: PIEdge] =
BEGIN
edge ← Alloc[SIZE[PIEdgeRecord]];
edge↑ ← [
next: NIL,
x: x,
yMin: yMin,
yMax: yMax,
up: up,
pi: pi
];
END;

FreePIEdge: PROCEDURE[edge: PIEdge] =
BEGIN
Free[edge,SIZE[PIEdgeRecord]];
END;



CompareInstances: PROCEDURE[pi1,pi2: Instance]
RETURNS[{less,greater,equal}] =
BEGIN
--ordering is used for two purposes -
-- 1. to remove duplicate PrimInstance lists from intersection list,
-- 2. to facilitate detection of repeated DisCellSymbols in Gather
-- Ordering will be .yOffset within .xOffset within .symbol address
s1: LONG INTEGER ← LOOPHOLE[pi1.symbol];
s2: LONG INTEGER ← LOOPHOLE[pi2.symbol];
RETURN[SELECT s1 FROM
<s2 => less,
>s2 => greater,
ENDCASE =>
SELECT pi1.xOffset FROM
<pi2.xOffset => less,
>pi2.xOffset => greater,
ENDCASE =>
SELECT pi1.yOffset FROM
<pi2.yOffset => less,
>pi2.yOffset => greater,
ENDCASE => equal];
END;

PartitionGeometry: PUBLIC PROCEDURE[symbol: Symbol, dcList: DisCell] =
--This procedure takes a list of Geometry, symbol.geom, and a list of
-- DisCells, dcList.
--It partitions the geometry onto the Discells(.geom) by clipping to
-- the .windows of each DisCell, and replaces symbol.geom with
-- a list of any remaining Geometry, additionally clipped to boundary
-- of symbol
BEGIN
geom: Geometry;
inside,outside: Geometry;
IF symbol=NIL THEN RETURN;
IF symbol.geom=NIL THEN RETURN;
geom ← symbol.geom;
FOR dc:DisCell ← dcList, dc.next UNTIL dc=NIL DO
inside ← NIL;
FOR w:Rectangle ← dc.windows, w.next UNTIL w=NIL DO
outside ← NIL;
UNTIL geom=NIL DO
in,out1,outn: Geometry;
r: Geometry ← geom;
geom ← geom.next;
[in,out1,outn] ← Clip[w,r];
IF in#NIL THEN {in.next ← inside; inside ← in;};
IF out1#NIL THEN
{outn.next ← outside; outside ← out1;};
ENDLOOP;
geom ← outside;
ENDLOOP;
dc.geom ← inside;
ENDLOOP;
--geom now contains what’s left over after assigning pieces to discells
--clip geom to windows of symbol
inside ← NIL;
FOR w:Rectangle ← symbol.windows, w.next UNTIL w=NIL DO
outside ← NIL;
UNTIL geom=NIL DO
in,out1,outn: Geometry;
r: Geometry ← geom;
geom ← geom.next;
[in,out1,outn] ← Clip[w,r];
IF in#NIL THEN {in.next ← inside; inside ← in;};
IF out1#NIL THEN
{outn.next ← outside; outside ← out1;};
ENDLOOP;
geom ← outside;
ENDLOOP;
symbol.geom ← inside;
--free geom
FOR g:Geometry ← geom,geom UNTIL g=NIL DO
geom ← geom.next;
FreeGeometry[g];
ENDLOOP;
END;

Clip: PROCEDURE[w: Rectangle, r: Geometry]
RETURNS[in,out1,outn: Geometry] =
--Clip rectangle, r, against window, w, and return relevant pieces
--out1,outn are head and tail of outside pieces (up to 4)
--r will be overwritten to make one of the pieces
BEGIN
left: REAL ← MAX[w.l,r.l];
bottom: REAL ← MAX[w.b,r.b];
right: REAL ← MIN[w.r,r.r];
top: REAL ← MIN[w.t,r.t];
IF left>=right OR bottom>=top THEN RETURN[NIL,r,r]; --all out
out1 ← outn ← NIL;
IF bottom#r.b THEN --slice off bottom part
{g: Geometry ← AllocateGeometry[];
g↑ ← [next:out1, layer:r.layer, l:r.l, b:r.b, r:r.r, t:w.b];
out1 ← g; IF outn=NIL THEN outn ← g;
r.b ← w.b;
};
IF top#r.t THEN --slice off top part
{g: Geometry ← AllocateGeometry[];
g↑ ← [next:out1, layer:r.layer, l:r.l, b:w.t, r:r.r, t:r.t];
out1 ← g; IF outn=NIL THEN outn ← g;
r.t ← w.t;
};
IF left#r.l THEN --slice off left part
{g: Geometry ← AllocateGeometry[];
g↑ ← [next:out1, layer:r.layer, l:r.l, b:r.b, r:w.l, t:r.t];
out1 ← g; IF outn=NIL THEN outn ← g;
r.l ← w.l;
};
IF right#r.r THEN --slice off right part
{g: Geometry ← AllocateGeometry[];
g↑ ← [next:out1, layer:r.layer, l:w.r, b:r.b, r:r.r, t:r.t];
out1 ← g; IF outn=NIL THEN outn ← g;
r.r ← w.r;
};
--r now contains inside part
RETURN[r,out1,outn];
END;

END.