-- 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.
(635)\183b4B412b13B403b5B458b10B53b8B869b25B1669b15B825b13B664b8B421b8B268b15B152b9B642b14B121b9B67b6B291b7B129b10B313b13B234b9B508b4B225b14B215b10B77b16B674b17B1559b4B