-- File: DJExtSort.mesa
-- sorting routine for the disjoint circuit extractor
-- Written by Martin Newell/Dan Fitzpatrick July 1981
-- Last edited: August 6, 1981  3:55 PM

DIRECTORY

DisjointTypes: FROM "DisjointTypes" USING [Rectangle],
DisjointAllocDefs: FROM "DisjointAllocDefs" USING [Alloc, Free],
DJExtAllocDefs: FROM "DJExtAllocDefs" USING [MakeSide, FreeSide, FreeBox],
DJExtGeomDefs: FROM "DJExtGeomDefs" USING [NewSwath, StartRec, EndRec, SetNodeNumber],
DJExtSortDefs: FROM "DJExtSortDefs",
DJExtTypes: FROM "DJExtTypes" USING [Box, Side, SideRecord, Position, diff, poly],
Real: FROM "Real" USING [FixI];
 
DJExtSort: PROGRAM
IMPORTS DisjointAllocDefs, DJExtAllocDefs, DJExtGeomDefs, Real
EXPORTS DJExtSortDefs =
BEGIN
OPEN DisjointTypes, DisjointAllocDefs, DJExtAllocDefs, DJExtGeomDefs, DJExtTypes, Real;

InitSorter: PUBLIC PROCEDURE [bbox: Rectangle] =
-- bbox is the bounding box of the current cell
BEGIN
	i: INTEGER;

	ActiveList _ newActiveList _ NIL;
	depth _ ALL[0];
	bottom _ bbox.b;
	left _ bbox.l;
	right _ bbox.r;
	binSize _ (bbox.t - bbox.b)/(nBins-1);
	IF binSize < 200 THEN binSize _ 200;
	FOR i IN [0..nBins) DO
		bin[i] _ NIL;
		ENDLOOP;
	END;

SortBox: PUBLIC PROCEDURE [box: Box] =
-- Puts box into the appropriate bin
BEGIN
	n:INTEGER _ FixI[(box.b - bottom)/binSize];
	box.next _ bin[n];
	bin[n] _ box;
	END;

DumpSorter: PUBLIC PROCEDURE =
BEGIN
	i: INTEGER;

	ynext _ bottom;
	FOR i IN [0..nBins) DO
		SortBin[i];
		DumpBin[i];
		ENDLOOP;
	UNTIL ActiveList = NIL DO DumpSwath[]; ENDLOOP;
	END;

SortBin: PROCEDURE[n:CARDINAL] =
BEGIN
	next: Box;
	first,last: Side;
	f,l: Side;
	cnext: yCell;
	yCellList: yCellRecord;
	yCellList.next _ NIL;

	-- first create a list for each different y value
	FOR box: Box _ bin[n],next UNTIL box = NIL DO
		next _ box.next;
		FOR cell: yCell _ @yCellList,cell.next UNTIL cell.next = NIL DO
			IF cell.next.y = box.b THEN GOTO AddToList;
			IF box.b < cell.next.y THEN GOTO MakeNewYCell;
			REPEAT
				AddToList => {
					box.next _ cell.next.link;
					cell.next.link _ box;
					cell.next.count _ cell.next.count + 1;
					};
				MakeNewYCell => {
					tmp: yCell _ AllocateYCell[];
					tmp^ _ [
							next: cell.next,
							link: box,
							y: box.b,
							count: 1
							];
					box.next _ NIL;
					cell.next _ tmp;
					};
				FINISHED => {			-- at end of list
					tmp: yCell _ AllocateYCell[];
					tmp^ _ [
							next: NIL,
							link: box,
							y: box.b,
							count: 1
							];
					box.next _ NIL;
					cell.next _ tmp;
					};
			ENDLOOP;
		ENDLOOP;
	-- for each list sort, if the list has greater than N values bucket sort first
	first _ last _ NIL;
	FOR cell: yCell _ yCellList.next,cnext UNTIL cell = NIL DO
		cnext _ cell.next;
		IF nBreak < cell.count THEN [f,l] _ BucketSort[cell.link,cell.count]
		 ELSE [f,l] _ ListSort[cell.link];
		IF last = NIL THEN first _ f
		 ELSE last.next _ f;
		IF l # NIL THEN last _ l;
		FreeYCell[cell];
		ENDLOOP;
	bin[n] _ NIL;
	UnActiveList _ first;
	END;

ListSort: PROCEDURE[ptr: Box] RETURNS[first,last: Side] = -- INLINE
BEGIN
	side,p: Side;
	next: Box;
	list: SideRecord;

	IF ptr = NIL THEN RETURN[NIL,NIL];
	list.next _ NIL;
	FOR box: Box _ ptr,next UNTIL box = NIL DO
		next _ box.next;
		-- enter right side into list
		side _ MakeSide[box.r,box.b,box.t,box.node,Right,box.layer];
		FOR p _ @list,p.next UNTIL p.next = NIL DO
			IF SideLessThan[side,p.next] THEN EXIT;
			ENDLOOP;
		side.next _ p.next;
		p.next _ side;
		-- enter left side into list
		side _ MakeSide[box.l,box.b,box.t,box.node,Left,box.layer];
		FOR p _ @list,p.next UNTIL p.next = NIL DO
			IF SideLessThan[side,p.next] THEN EXIT;
			ENDLOOP;
		side.next _ p.next;
		p.next _ side;
		FreeBox[box];
		ENDLOOP;
	first _ list.next;
	FOR last _ first,last.next UNTIL last.next = NIL DO ENDLOOP;
	END;

BucketSort: PROCEDURE[ptr: Box, n: CARDINAL] RETURNS[first,last: Side] =
BEGIN
	side,p: Side;
	l: Side;
	next: Box;
	xbin: ARRAY [0..nBins) OF SideRecord;
	binSize:REAL;
	i: CARDINAL;
	n _ MIN[n,nBins];
	binSize _ (right - left)/(n-1);
	first _ last _ NIL;

	FOR i IN [0..n) DO
		xbin[i].next _ NIL;
		ENDLOOP;
	FOR ptr _ ptr,next UNTIL ptr = NIL DO
		next _ ptr.next;
		-- enter right side into list
		i _ FixI[(ptr.r - left)/binSize];
		side _ MakeSide[ptr.r,ptr.b,ptr.t,ptr.node,Right,ptr.layer];
		FOR p _ @xbin[i],p.next UNTIL p.next = NIL DO
			IF SideLessThan[side,p.next] THEN EXIT;
			ENDLOOP;
		side.next _ p.next;
		p.next _ side;
		-- enter left side into list
		i _ FixI[(ptr.l - left)/binSize];
		side _ MakeSide[ptr.l,ptr.b,ptr.t,ptr.node,Left,ptr.layer];
		FOR p _ @xbin[i],p.next UNTIL p.next = NIL DO
			IF SideLessThan[side,p.next] THEN EXIT;
			ENDLOOP;
		side.next _ p.next;
		p.next _ side;
		FreeBox[ptr];
		ENDLOOP;
	-- concatenate all the lists together
	FOR i IN [0..n) DO
		IF xbin[i].next = NIL THEN l _ NIL
		 ELSE FOR l _ xbin[i].next,l.next UNTIL l.next = NIL DO ENDLOOP;
		IF last = NIL THEN first _ xbin[i].next
		 ELSE last.next _ xbin[i].next;
		IF l # NIL THEN last _ l;
		ENDLOOP;
	END;

SideLessThan: PROCEDURE[s1,s2:Side] RETURNS[BOOLEAN] = INLINE
-- ordering on y min then x then on whether Left or Right edge. (left < right)
BEGIN
	RETURN[(s1.b < s2.b) OR (s1.b = s2.b AND s1.x < s2.x OR (s1.x = s2.x AND EdgeOrder[s1,s2]))];
	END;

EdgeOrder: PROCEDURE[s1,s2:Side] RETURNS[BOOLEAN] = INLINE
-- (left < right) poly always appears inside diffusion
BEGIN
	RETURN[(s1.pos = Left AND s2.pos = Right) OR (s1.pos = s2.pos AND
					((s1.pos = Left AND s1.layer = diff) OR (s1.pos = Right AND s1.layer = poly)))];
	END;

DumpBin: PROCEDURE[n:CARDINAL] =
BEGIN
	UNTIL UnActiveList = NIL DO
		DumpSwath[];
		ENDLOOP;
	END;

DumpSwath: PROCEDURE =
BEGIN
	depth _ ALL[0];
	IF UnActiveList = NIL THEN ycur _ ynext
		ELSE ycur _ MIN[ynext,UnActiveList.b];
	ynext _ infinity;
	endNewActiveList _ newActiveList _ NIL;
	NewSwath[ycur];
	DO
		IF UnActiveList = NIL OR ycur < UnActiveList.b THEN EXIT;
		IF ActiveList = NIL THEN EXIT;
		IF ActiveList.t <= ycur THEN {
			-- the first element on ActiveList is no longer valid, disgard it
			tmp: Side _ ActiveList;
			ActiveList _ ActiveList.next;
			FreeSide[tmp];
			LOOP;
			};
		-- at this point we know there is something of interest on both the ActiveList and list
		-- find the smaller element and place it on the new list
		IF Smaller[UnActiveList,ActiveList] THEN {		-- UnActiveList contains the smaller element
			Add[UnActiveList];
			UnActiveList _ UnActiveList.next;
			}
		 ELSE {											-- ActiveList contains the smaller element
			Add[ActiveList];
			ActiveList _ ActiveList.next;
			};
		ENDLOOP;
	IF UnActiveList = NIL OR ycur < UnActiveList.b THEN {	-- Just run down ActiveList
		UNTIL ActiveList = NIL DO
			IF ActiveList.t <= ycur THEN {
				-- the first element on ActiveList is no longer valid, disgard it
				tmp: Side _ ActiveList;
				ActiveList _ ActiveList.next;
				FreeSide[tmp];
				}
			 ELSE {
				Add[ActiveList];
				ActiveList _ ActiveList.next;
				};
			ENDLOOP;
		}
	 ELSE {												-- Just take elements from list
		UNTIL UnActiveList = NIL OR ycur < UnActiveList.b DO
			Add[UnActiveList];
			UnActiveList _ UnActiveList.next;
			ENDLOOP;
		};
	IF endNewActiveList # NIL THEN endNewActiveList.next _ NIL;
	ActiveList _ newActiveList;
	END;

Smaller: PROCEDURE[s1,s2:Side] RETURNS[BOOLEAN] = INLINE
-- ordering on x then on whether Left or Right edge. (left < right)
BEGIN
	RETURN[s1.x < s2.x OR (s1.x = s2.x AND EdgeOrder[s1,s2])];
	END;

Add: PROCEDURE[side:Side] = INLINE
-- add side to the new active list, compute ynext, compute depth, call StartRec & EndRec,
-- see if side has a node number, if so call SetNodeNumber
BEGIN
	layer: INTEGER _ side.layer;
	ynext _ MIN[ynext,side.t];
	IF depth[layer] = 0 THEN StartRec[side.x,layer];
	IF side.pos = Left THEN {
		depth[layer] _ depth[layer] + 1;
		IF side.node # 0 THEN SetNodeNumber[side.node,layer];
		}
	 ELSE depth[layer] _ depth[layer] - 1;
	IF depth[layer] = 0 THEN EndRec[side.x,layer];
	IF endNewActiveList = NIL THEN endNewActiveList _ newActiveList _ side
	 ELSE {
		endNewActiveList.next _ side;
		endNewActiveList _ side;
		}
	END;

AllocateYCell: PUBLIC PROCEDURE RETURNS[cell:yCell] =
BEGIN
	cell _ Alloc[SIZE[yCellRecord]];
	END;

FreeYCell: PUBLIC PROCEDURE[cell:yCell] =
BEGIN
	Free[cell,SIZE[yCellRecord]];
	END;

bottom,left,right: REAL;					-- bottom, left, and right of current symbol
ycur: REAL;						-- bottom of current swath
ynext: REAL;					-- top of current swath

binSize: REAL;					-- vertical size in CIF units of each bin
nBins: CARDINAL = 256;			-- number of bins
bin: ARRAY [0..nBins) OF Box;	-- bins

UnActiveList: Side;
ActiveList: Side;
newActiveList: Side;
endNewActiveList: Side;

yCell: TYPE = LONG POINTER TO yCellRecord;
yCellRecord: TYPE = RECORD [
		next: yCell,
		link: Box,
		y: REAL,
		count: CARDINAL
		];

nBreak: INTEGER = 15;			-- break off point on whether or not to list sort or bucket sort
infinity: REAL = 9.99999e+25;	-- large number

depth: PUBLIC ARRAY [0..16) OF INTEGER;

END.
(672)\172b10B438b9B191b11B42i44I260b7B35i33I94b10B177b7B143i46I600i14I207i75I368b8B235i26I208i25I318b10B364i26I247i25I272i34I247b12B53i75I109b9B53i51I167b7B94b9B332i21I10i31I99i64I12i3I11i53I63i28I99i28I129i13I81i21I10i31I200i23I234b7B53i64I74b3B35i68I8i3I6i47I489b13B88b9B109i41I21i23I21i20I24i38I29i14I34i4I248i61I34i12I