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