-- 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.