-- File: DJExtSeg.mesa
-- segment sorting routines for the disjoint circuit extractor
-- Written by Martin Newell/Dan Fitzpatrick July 1981
-- Last edited: 12-Aug-81 13:50:39

DIRECTORY

DisjointAllocDefs: FROM "DisjointAllocDefs" USING [Alloc,Free],
DJExtractDefs: FROM "DJExtractDefs" USING [RecordNodeLoc],
DJExtAllocDefs: FROM "DJExtAllocDefs" USING [AllocateBox, AllocateSegment, FreeSegment],
DJExtCombineDefs: FROM "DJExtCombineDefs" USING [Combine],
DJExtMergeDefs: FROM "DJExtMergeDefs" USING [GenNodeNumber],
DJExtSegDefs: FROM "DJExtSegDefs",
DJExtSortDefs: FROM "DJExtSortDefs" USING [SortBox],
DJExtTypes: FROM "DJExtTypes" USING [Box, Segment, Position, NodeNumber, poly, diff, gate],
Runtime: FROM "Runtime" USING [CallDebugger],
Real: FROM "Real" USING [FixI];
 
DJExtSeg: PROGRAM
IMPORTS DisjointAllocDefs, DJExtractDefs, DJExtAllocDefs, DJExtCombineDefs, DJExtMergeDefs, DJExtSortDefs, Runtime, Real
EXPORTS DJExtSegDefs =
BEGIN
OPEN DisjointAllocDefs, DJExtractDefs, DJExtAllocDefs, DJExtCombineDefs, DJExtMergeDefs, DJExtSortDefs, DJExtTypes, Runtime, Real;

SegListSort: PUBLIC PROCEDURE [segList:Segment, s:Position] RETURNS[Segment] =
BEGIN
	pt,p: Point;
	next: Segment;
	list: PointRecord;

	IF segList = NIL THEN RETURN[NIL];
	pos _ s;
	-- decide whether segments in this list are horizontal or vertical
	IF pos = Bottom OR pos = Top THEN {			-- horizontal
		Vertical _ FALSE;
		ycur _ segList.by;
		}
	 ELSE IF pos = Left OR pos = Right THEN {	-- vertical
			Vertical _ TRUE;
			xcur _ segList.bx;
			}
		 ELSE CallDebugger["0 size segment"];

	list.next _ NIL;
	FOR seg: Segment _ segList,next UNTIL seg = NIL DO
		next _ seg.next;
		-- enter right side into list
		pt _ MakePoint[seg.tx,seg.ty,0,seg.layer,Right];
		FOR p _ @list,p.next UNTIL p.next = NIL DO
			IF pt.v < p.next.v THEN EXIT;
			ENDLOOP;
		pt.next _ p.next;
		p.next _ pt;
		-- enter left side into list
		pt _ MakePoint[seg.bx,seg.by,seg.node,seg.layer,Left];
		FOR p _ @list,p.next UNTIL p.next = NIL DO
			IF pt.v < p.next.v THEN EXIT;
			ENDLOOP;
		pt.next _ p.next;
		p.next _ pt;
		FreeSegment[seg];
		ENDLOOP;
	RETURN[ScanSegs[list.next]];
	END;

SegBucketSort: PUBLIC PROCEDURE [segList:Segment, n:CARDINAL, l,r:REAL, s:Position] RETURNS[Segment] =
BEGIN
	pt,p: Point;
	first,last,q: Point;
	seg,next: Segment;
	xbin: ARRAY [0..nBins) OF PointRecord;
	i: CARDINAL;
	left _ l;
	right _ r;
	n _ MIN[n,nBins];
	binSize _ (right - left + 1)/n;
	first _ last _ NIL;

	IF segList = NIL THEN RETURN[NIL];
	-- decide whether segments in this list are horizontal or vertical
	pos _ s;
	IF pos = Bottom OR pos = Top THEN {			-- horizontal
		Vertical _ FALSE;
		ycur _ segList.by;
		}
	 ELSE IF pos = Left OR pos = Right THEN {	-- vertical
			Vertical _ TRUE;
			xcur _ segList.bx;
			}
		 ELSE CallDebugger["0 size segment"];

	FOR i IN [0..n) DO
		xbin[i].next _ NIL;
		ENDLOOP;
	FOR seg _ segList,next UNTIL seg = NIL DO
		next _ seg.next;
		-- enter right side into list
		i _ GetBin[seg.tx,seg.ty];
		pt _ MakePoint[seg.tx,seg.ty,0,seg.layer,Right];
		FOR p _ @xbin[i],p.next UNTIL p.next = NIL DO
			IF pt.v < p.next.v THEN EXIT;
			ENDLOOP;
		pt.next _ p.next;
		p.next _ pt;
		-- enter left side into list
		i _ GetBin[seg.bx,seg.by];
		pt _ MakePoint[seg.bx,seg.by,seg.node,seg.layer,Left];
		FOR p _ @xbin[i],p.next UNTIL p.next = NIL DO
			IF pt.v < p.next.v THEN EXIT;
			ENDLOOP;
		pt.next _ p.next;
		p.next _ pt;
		FreeSegment[seg];
		ENDLOOP;
	-- concatenate all the lists together
	last _ first _ NIL;
	FOR i IN [0..n) DO
		IF xbin[i].next = NIL THEN q _ NIL
		 ELSE FOR q _ xbin[i].next,q.next UNTIL q.next = NIL DO ENDLOOP;
		IF last = NIL THEN first _ xbin[i].next
		 ELSE last.next _ xbin[i].next;
		IF q # NIL THEN last _ q;
		ENDLOOP;
	RETURN[ScanSegs[first]];
	END;

ScanSegs: PROCEDURE [ptList:Point] RETURNS[Segment] =
BEGIN
	next: Point;
	l: INTEGER;

	SegList _ NIL;
	depth _ ALL[0];
	count _ ALL[0];
	nodeNum _ ALL[0];
	FOR pt: Point _ ptList,next UNTIL pt = NIL DO
		next _ pt.next;
		l _ pt.layer;
		IF depth[l] = 0 THEN StartSeg[pt.v,l];
		IF pt.start THEN depth[l] _ depth[l] + 1 ELSE depth[l] _ depth[l] - 1;
		IF pt.node # 0 THEN SetNode[pt.node,l];
		IF depth[l] = 0 THEN EndSeg[pt.v,l];
		FreePoint[pt];
		ENDLOOP;
	RETURN[SegList];
	END;

StartSeg: PROCEDURE [v:REAL, layer:INTEGER] =
BEGIN
	count[layer] _ count[layer] + 1;
	SELECT layer FROM
		poly => IF depth[diff] # 0 THEN {
					EndSeg[v,diff];
					StartSeg[v,gate];
					};
		diff => IF depth[poly] # 0 THEN {
					StartSeg[v,gate];
					RETURN;
					};
		gate => IF count[layer] # 1 THEN RETURN;
		ENDCASE;
	SegLeft[layer] _ v;
	END;

SetNode: PROCEDURE [node:NodeNumber, layer:INTEGER] =
BEGIN
	IF nodeNum[layer] # 0 THEN nodeNum[layer] _ Combine[nodeNum[layer],node]
	 ELSE nodeNum[layer] _ node;
	END;

EndSeg: PROCEDURE [v:REAL, layer:INTEGER] =
BEGIN
	seg: Segment;
	count[layer] _ count[layer] - 1;
	SELECT layer FROM
		poly => IF depth[diff] # 0 THEN {
					EndSeg[v,gate];
					StartSeg[v,diff];
					};
		diff => IF depth[poly] # 0 THEN {
					EndSeg[v,gate];
					RETURN;
					};
		gate => IF count[layer] # 0 THEN RETURN;
		ENDCASE;
	IF SegLeft[layer] = v THEN RETURN;		-- don't keep 0 size segments
	-- if node number is 0 then assign number and make geometry box for extraction
	IF nodeNum[layer] = 0 THEN {
		box: Box _ AllocateBox[];
		nodeNum[layer] _ GenNodeNumber[];
		box^ _ [
				next: NIL,
				layer: layer,
				node: nodeNum[layer],
				l: SegLeft[layer],
				b: SegLeft[layer],
				r: v,
				t: v
				];
		IF Vertical THEN box.l _ box.r _ xcur ELSE box.b _ box.t _ ycur;
		RecordNodeLoc[box.node,(box.l+box.r)/2,(box.b+box.t)/2];
		SortBox[box];
		};
	-- add segment to SegList
	seg _ AllocateSegment[];
	seg^ _ [
			next: SegList,
			layer: layer,
			node: nodeNum[layer],
			pos: pos,
			bx: SegLeft[layer],
			by: SegLeft[layer],
			tx: v,
			ty: v
			];
	IF Vertical THEN seg.bx _ seg.tx _ xcur ELSE seg.by _ seg.ty _ ycur;
	SegList _ seg;
	nodeNum[layer] _ 0;
	END;

GetBin: PROCEDURE [x,y:REAL] RETURNS[INTEGER] =
BEGIN
	v: REAL _ IF Vertical THEN y ELSE x;
	RETURN[FixI[(v-left)/binSize]];
	END;

MakePoint: PROCEDURE [x,y:REAL, node:NodeNumber, layer:INTEGER, pos:Position] RETURNS[pt:Point] =
BEGIN
	pt _ AllocatePoint[];
	pt^ _ [
		next: NIL,
		node: node,
		layer: layer,
		v: IF Vertical THEN y ELSE x,
		start: pos = Left
		];
	END;

AllocatePoint: PUBLIC PROCEDURE RETURNS[e:Point] = INLINE
BEGIN
	 e _ Alloc[SIZE[PointRecord]];
	END;

FreePoint: PUBLIC PROCEDURE[e:Point] = INLINE
BEGIN
	Free[e,SIZE[PointRecord]];
	END;

left, right: REAL;
xcur, ycur: REAL;
Vertical: BOOLEAN;

binSize: REAL;					-- vertical size in CIF units of each bin
nBins: CARDINAL = 16;			-- number of bins

Point: TYPE = LONG POINTER TO PointRecord;
PointRecord: TYPE = RECORD [
		next: Point,
		node: NodeNumber,
		layer: INTEGER,
		v: REAL,
		start: BOOLEAN
		];

pos: Position;
SegList: Segment;
depth: ARRAY [0..16) OF INTEGER;
count: ARRAY [0..16) OF INTEGER;
nodeNum: ARRAY [0..16) OF NodeNumber;
SegLeft: ARRAY [0..16) OF REAL;
END.
(672)\180b10B596b8B293b12B175i63I43i10I92i8I183i26I182i25I251b13B343i63I53i10I92i8I209i26I214i25I250i34I294b8B478b8B347b7B164b6B372i26I5i75I388i15I302b6B126b9B234b13B90b9B157i38I28i14I