IIManhattanImpl.mesa
Copyright © 1984, 1985, 1986 by Xerox Corporation. All rights reserved.
Michael Plass, September 23, 1986 4:10:34 pm PDT
Doug Wyatt, March 7, 1986 4:36:43 pm PST
DIRECTORY
IIManhattan USING [Polygon, Visibility],
SF USING [Add, Box, BoxAction, BoxGenerator, Empty, Intersect, Max, Min, Nonempty, Vec];
IIManhattanImpl: CEDAR MONITOR
IMPORTS SF
EXPORTS IIManhattan
~ BEGIN OPEN IIManhattan, SF;
InvalidManhattanPolygon:
PUBLIC
ERROR ~
CODE;
Validate:
PUBLIC
PROC [polygon: Polygon]
RETURNS [Polygon] ~ {
IF polygon #
NIL
THEN {
a: Polygon ← polygon;
b: Polygon ← polygon.rest;
IF Empty[a.first] THEN ERROR InvalidManhattanPolygon;
UNTIL b =
NIL
DO
IF Empty[b.first] THEN ERROR InvalidManhattanPolygon;
IF
NOT (
(a.first.min.s = b.first.min.s AND a.first.max.s = b.first.max.s AND a.first.max.f <= b.first.min.f)
OR a.first.max.s <= b.first.min.s
)
THEN ERROR InvalidManhattanPolygon;
a ← b;
b ← b.rest;
ENDLOOP;
};
RETURN [polygon]
};
CreateFromRuns:
PUBLIC
PROC [
runs:
PROC[
run: PROC[sMin, fMin: INTEGER, fSize: NAT],
repeat: PROC[timesToRepeatScanline: NAT]
]
] RETURNS [polygon: Polygon] ~ {
scratch: LIST OF Box ← GetScratch[];
last: LIST OF Box ← scratch;
secondLastRowStart: LIST OF Box ← NIL;
lastRowStart: LIST OF Box ← last;
secondLastRowCount: INTEGER ← -1;
lastRowCount: INTEGER ← 0;
Run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT] ~ {
fMaxCurrent: INTEGER ~ last.first.max.f;
IF sMin = last.first.min.s
THEN {
IF last.first.max.s-last.first.min.s # 1 THEN ERROR;
SELECT fMin
FROM
= fMaxCurrent => {last.first.max.f ← last.first.max.f + fSize};
> fMaxCurrent => {
IF last.rest = NIL THEN last.rest ← GetScratch[];
last ← last.rest;
last.first ← [min: [s: sMin, f: fMin], max: [s: sMin+1, f: fMin+fSize]];
lastRowCount ← lastRowCount + 1;
};
ENDCASE => ERROR;
}
ELSE {
IF secondLastRowCount = lastRowCount
AND secondLastRowStart.first.max.s = lastRowStart.first.min.s
AND TryToMergeRows[secondLastRowStart, lastRowCount]
THEN {last ← lastRowStart; lastRowStart ← secondLastRowStart; secondLastRowCount ← -1}
ELSE {IF last.rest = NIL THEN last.rest ← GetScratch[]; last ← last.rest};
secondLastRowStart ← lastRowStart;
secondLastRowCount ← lastRowCount;
last.first ← [min: [s: sMin, f: fMin], max: [s: sMin+1, f: fMin+fSize]];
lastRowStart ← last;
lastRowCount ← 1;
IF secondLastRowStart.first.max.s > sMin THEN ERROR;
};
};
Repeat:
PROC[timesToRepeatScanline:
NAT] ~ {
t: LIST OF Box ← lastRowStart;
THROUGH [0..lastRowCount)
DO
t.first.max.s ← t.first.max.s + timesToRepeatScanline;
t ← t.rest;
ENDLOOP;
};
last.first ← [[0, 0], [0, 0]];
runs[Run, Repeat];
IF secondLastRowCount = lastRowCount
AND secondLastRowStart.first.max.s = lastRowStart.first.min.s
AND TryToMergeRows[secondLastRowStart, lastRowCount]
THEN {
last ← secondLastRowStart;
THROUGH [0..lastRowCount-1)
DO
last ← last.rest;
ENDLOOP;
};
IF scratch.first.max.f>scratch.first.min.f
THEN {
polygon ← scratch;
scratch ← last.rest;
last.rest ← NIL;
}
ELSE IF last = scratch THEN polygon ← NIL
ELSE {
polygon ← scratch.rest;
scratch.rest ← last.rest;
last.rest ← NIL;
};
FreeScratch[scratch];
};
TryToMergeRows:
PROC [secondLastRowStart:
LIST
OF Box, boxesPerRow:
INT]
RETURNS [success: BOOLEAN] ~ {
Assume
the secondLast row and the last row have the same number of boxes,
boxes in the secondLast row all have the same sSize,
boxes in the last row all have the same sSize.
max: INTEGER;
s: LIST OF Box ← secondLastRowStart;
t: LIST OF Box ← secondLastRowStart;
FOR i: INT IN [0..boxesPerRow) DO t ← t.rest ENDLOOP;
IF boxesPerRow = 0 THEN RETURN [TRUE];
FOR i:
INT
IN [0..boxesPerRow)
DO
IF s.first.min.f # t.first.min.f OR s.first.max.f # t.first.max.f THEN RETURN [FALSE];
s ← s.rest; t ← t.rest;
ENDLOOP;
t ← s; s ← secondLastRowStart;
max ← t.first.max.s;
FOR i:
INT
IN [0..boxesPerRow)
DO
s.first.max.s ← max;
s ← s.rest;
ENDLOOP;
RETURN [TRUE];
};
Destroy:
PUBLIC
PROC [rectangleList:
LIST
OF Box] ~ {
FreeScratch[rectangleList];
};
Copy:
PUBLIC
PROC [polygon: Polygon]
RETURNS [copy: Polygon] ~ {
scratch: LIST OF Box ← GetScratch[];
last: LIST OF Box ← scratch;
WHILE polygon #
NIL
DO
IF last.rest = NIL THEN {last.rest ← GetScratch[]};
last ← last.rest;
last.first ← polygon.first;
polygon ← polygon.rest;
ENDLOOP;
IF last = scratch THEN copy ← NIL
ELSE {
copy ← scratch.rest;
scratch.rest ← last.rest;
last.rest ← NIL;
};
FreeScratch[scratch];
};
Reader:
TYPE ~
RECORD [
s, fMin, fMax: INTEGER,
repeatCount: CARDINAL,
done: BOOLEAN,
currentRow, currentBox: LIST OF Box
];
NewReader:
PROC [polygon: Polygon]
RETURNS [Reader] ~
INLINE {
IF polygon = NIL THEN RETURN [[LAST[INTEGER], 0, 0, 0, TRUE, NIL, NIL]]
ELSE
RETURN [[
s: polygon.first.min.s,
fMin: polygon.first.min.f,
fMax: polygon.first.max.f,
repeatCount: polygon.first.max.s-polygon.first.min.s,
done: FALSE,
currentRow: polygon,
currentBox: polygon
]]
};
Advance:
UNSAFE
PROC [r:
POINTER
TO Reader] ~
UNCHECKED {
next: Polygon ← r.currentBox.rest;
IF next =
NIL
OR next.first.min.s # r.currentRow.first.min.s
THEN {
IF r.repeatCount > 1
THEN {
r.repeatCount ← r.repeatCount - 1;
r.s ← r.s + 1;
next ← r.currentRow;
}
ELSE
IF next #
NIL
THEN {
r.currentRow ← next;
r.repeatCount ← next.first.max.s-next.first.min.s;
r.s ← next.first.min.s;
};
};
IF next = NIL THEN r^ ← [LAST[INTEGER], 0, 0, 0, TRUE, NIL, NIL]
ELSE {
r.fMin ← next.first.min.f;
r.fMax ← next.first.max.f;
r.currentBox ← next;
IF r.repeatCount = 0 THEN Advance[r];
};
};
SkipTo:
UNSAFE
PROC [r:
POINTER
TO Reader, s:
INTEGER] ~
UNCHECKED {
IF r.s >= s THEN RETURN;
WHILE r.s < s
DO
IF r.currentRow = r.currentBox
AND r.repeatCount > 1
THEN {
delta: INTEGER ← MIN[r.repeatCount-1, s-r.s];
r.s ← r.s + delta;
r.repeatCount ← r.repeatCount - delta;
}
ELSE Advance[r];
ENDLOOP;
};
TestReader:
PROC [polygon: Polygon] ~ {
reader: Reader ← NewReader[polygon];
Run:
PROC [box: Box] ~ {
IF reader.done THEN ERROR;
IF box.min.s # reader.s THEN ERROR;
IF (box.max.s-box.min.s)#1 THEN ERROR;
IF box.min.f # reader.fMin THEN ERROR;
IF box.max.f # reader.fMax THEN ERROR;
TRUSTED {Advance[@reader]};
};
Map[polygon, Run, TRUE];
IF NOT reader.done THEN ERROR;
};
Union:
PUBLIC
PROC [a, b: Polygon]
RETURNS [Polygon] ~ {
Runs:
PROC[run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT], repeat:
PROC[timesToRepeatScanline:
NAT]] ~
TRUSTED {
aReader: Reader ← NewReader[a];
bReader: Reader ← NewReader[b];
UNTIL aReader.done
AND bReader.done
DO
as: INTEGER ← aReader.s;
bs: INTEGER ← bReader.s;
s: INTEGER ← MIN[as, bs];
duplicates: NAT ← MIN[aReader.repeatCount, bReader.repeatCount];
somethingInScanline: BOOLEAN ← FALSE;
WHILE s = aReader.s
OR s = bReader.s
DO
fStart: INTEGER ← LAST[INTEGER];
fEnd: INTEGER;
IF s = aReader.s THEN {fStart ← aReader.fMin};
IF s = bReader.s THEN {fStart ← MIN[fStart, bReader.fMin]};
fEnd ← fStart;
DO
SELECT
TRUE
FROM
s = aReader.s
AND aReader.fMin <= fEnd => {
fEnd ← MAX[fEnd, aReader.fMax];
Advance[@aReader];
};
s = bReader.s
AND bReader.fMin <= fEnd => {
fEnd ← MAX[fEnd, bReader.fMax];
Advance[@bReader];
};
ENDCASE => EXIT;
ENDLOOP;
IF fEnd > fStart THEN {run[s, fStart, fEnd - fStart]; somethingInScanline ← TRUE};
ENDLOOP;
IF as = s
AND bs = s
AND duplicates > 1
THEN {
IF somethingInScanline THEN repeat[duplicates-1];
SkipTo[@aReader, s+duplicates];
SkipTo[@bReader, s+duplicates];
};
ENDLOOP;
};
RETURN[CreateFromRuns[Runs]];
};
Intersection:
PUBLIC
PROC [a, b: Polygon]
RETURNS [Polygon] ~ {
Runs:
PROC[run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT], repeat:
PROC[timesToRepeatScanline:
NAT]] ~
TRUSTED {
aReader: Reader ← NewReader[a];
bReader: Reader ← NewReader[b];
DO
duplicates: NAT;
s: INTEGER;
somethingInScanline: BOOLEAN ← FALSE;
IF aReader.s < bReader.s THEN SkipTo[@aReader, bReader.s]; IF aReader.done THEN EXIT;
IF aReader.s > bReader.s THEN SkipTo[@bReader, aReader.s]; IF bReader.done THEN EXIT;
s ← aReader.s;
duplicates ← MIN[aReader.repeatCount, bReader.repeatCount] - 1;
WHILE s = aReader.s
AND s = bReader.s
DO
fMin: INTEGER ← MAX[aReader.fMin, bReader.fMin];
fMax: INTEGER ← MIN[aReader.fMax, bReader.fMax];
IF fMin < fMax THEN {run[s, fMin, fMax - fMin]; somethingInScanline ← TRUE};
SELECT fMax
FROM
aReader.fMax => {Advance[@aReader]};
bReader.fMax => {Advance[@bReader]};
ENDCASE => ERROR;
ENDLOOP;
IF duplicates > 0
THEN {
IF somethingInScanline THEN repeat[duplicates];
SkipTo[@aReader, s+1+duplicates];
SkipTo[@bReader, s+1+duplicates];
};
ENDLOOP;
};
RETURN[CreateFromRuns[Runs]];
};
Invert:
PROC [b: Polygon, universe: Box]
RETURNS [inverse: Polygon] ~ {
c: LIST OF Box ← GetScratch[];
last: LIST OF Box ← c;
bb: Box ← BoundingBox[b];
sMin: INTEGER ← MIN[universe.min.s, bb.min.s];
fMin: INTEGER ← MIN[universe.min.f, bb.min.f];
sMax: INTEGER ← MAX[universe.max.s, bb.max.s];
fMax: INTEGER ← MAX[universe.max.f, bb.max.f];
Emit:
PROC [s0, f0, s1, f1:
INTEGER] ~ {
s0 ← MAX[s0, universe.min.s];
s1 ← MIN[s1, universe.max.s];
f0 ← MAX[f0, universe.min.f];
f1 ← MIN[f1, universe.max.f];
IF s0 < s1
AND f0 < f1
THEN {
IF last.rest = NIL THEN last.rest ← GetScratch[];
last ← last.rest;
last.first ← [[s0, f0], [s1, f1]];
};
};
s: INTEGER ← sMin;
f: INTEGER ← fMax;
FOR p:
LIST
OF Box ← b, p.rest
UNTIL p=
NIL
DO
r: Box ~ p.first;
IF r.min.s > sMin
OR p=b
THEN {
Emit[sMin, f, s, fMax];
f ← fMin;
sMin ← s;
s ← r.min.s;
Emit[sMin, f, s, fMax];
sMin ← s;
s ← r.max.s;
};
IF sMin # r.min.s OR s # r.max.s THEN ERROR;
Emit[sMin, f, s, r.min.f];
f ← r.max.f;
ENDLOOP;
Emit[sMin, f, s, fMax];
Emit[s, fMin, sMax, fMax];
IF c = last THEN inverse ← NIL
ELSE {
inverse ← c.rest;
c.rest ← last.rest;
last.rest ← NIL;
};
FreeScratch[c];
[] ← Validate[inverse];
IF Intersection[b, inverse] # NIL THEN ERROR;
};
Difference:
PUBLIC
PROC [a, b: Polygon]
RETURNS [diff: Polygon] ~ {
bb: Box ← BoundingBox[a];
bInverse: Polygon ← Invert[b, bb];
IF a # NIL AND a.rest = NIL THEN diff ← bInverse
ELSE {
diff ← Intersection[a, bInverse];
FreeScratch[bInverse];
};
IF NOT Equal[Union[a, b], Union[diff, b]] THEN ERROR;
};
Shift:
PUBLIC
PROC [polygon: Polygon, sShift, fShift:
INTEGER] ~ {
shift: Vec ~ [s: sShift, f: fShift];
WHILE polygon #
NIL
DO
polygon.first.min ← Add[polygon.first.min, shift];
polygon.first.max ← Add[polygon.first.max, shift];
polygon ← polygon.rest;
ENDLOOP;
};
FullyDestructiveUnion:
PROC [a, b: Polygon]
RETURNS [u: Polygon] ~ {
u ← Union[a, b];
FreeScratch[a];
FreeScratch[b];
};
DestructiveUnion:
PUBLIC
PROC [a, b: Polygon]
RETURNS [u: Polygon] ~ {
u ← Union[a, b];
FreeScratch[a];
};
DestructiveIntersection:
PUBLIC
PROC [a, b: Polygon]
RETURNS [i: Polygon ←
NIL] ~ {
IF a = NIL OR b = NIL THEN RETURN [NIL];
IF b.rest = NIL THEN i ← DestructiveClip[a, b.first]
ELSE {
i ← Intersection[a, b];
FreeScratch[a];
};
};
DestructiveClip:
PUBLIC
PROC [a: Polygon, b: Box]
RETURNS [i: Polygon ←
NIL] ~ {
last: Polygon ← NIL;
junk: Polygon ← NIL;
UNTIL a =
NIL
DO
p: Polygon ← a;
sMin: INTEGER ← MAX[p.first.min.s, b.min.s];
fMin: INTEGER ← MAX[p.first.min.f, b.min.f];
sMax: INTEGER ← MIN[p.first.max.s, b.max.s];
fMax: INTEGER ← MIN[p.first.max.f, b.max.f];
a ← a.rest;
IF sMax <= sMin OR fMax <= fMin THEN {p.rest ← junk; junk ← p}
ELSE {
p.first ← [[sMin, fMin], [sMax, fMax]];
IF last = NIL THEN i ← last ← p ELSE {last.rest ← p; last ← p};
}
ENDLOOP;
IF last # NIL THEN last.rest ← NIL;
FreeScratch[junk];
};
DestructiveDifference:
PUBLIC
PROC [a, b: Polygon]
RETURNS [d: Polygon] ~ {
d ← Difference[a, b];
FreeScratch[a];
};
SplitOffSecondHalf:
PROC [a:
LIST
OF Box]
RETURNS [r:
LIST
OF Box] ~ {
b: LIST OF Box ← a;
n: INT ← 0;
WHILE a#
NIL
DO
a ← a.rest; n ← n + 1;
b ← b.rest;
IF a = NIL THEN EXIT; a ← a.rest; n ← n + 1;
ENDLOOP;
IF n < 8 THEN r ← NIL
ELSE {r ← b.rest; b.rest ← NIL};
};
Canonicalize:
PUBLIC
PROC [rectangleList:
LIST
OF Box]
RETURNS [Polygon] ~ {
b: LIST OF Box ← SplitOffSecondHalf[rectangleList];
a: LIST OF Box ← rectangleList;
IF b =
NIL
THEN {
WHILE a #
NIL
DO
a1: LIST OF Box ← a;
a ← a1.rest;
a1.rest ← NIL;
IF Nonempty[a1.first] THEN b ← FullyDestructiveUnion[b, a1];
ENDLOOP;
RETURN [b]
}
ELSE RETURN [FullyDestructiveUnion[Canonicalize[a], Canonicalize[b]]];
};
CreateFromBoxes:
PUBLIC
PROC [boxes:
SF.BoxGenerator]
RETURNS [Polygon] ~ {
head: LIST OF Box ← GetScratch[];
last: LIST OF Box ← head;
new: LIST OF Box ← NIL;
AddBox:
PROC [box: Box] ~ {
IF
NOT Empty[box]
THEN {
IF last.rest = NIL THEN last.rest ← GetScratch[];
last ← last.rest;
last.first ← box;
};
};
boxes[AddBox];
{t: LIST OF Box ← last.rest; last.rest ← NIL; new ← head.rest; head.rest ← t};
FreeScratch[head]; head ← last ← NIL;
RETURN [Validate[new ! InvalidManhattanPolygon => CONTINUE]];
RETURN [Canonicalize[new]];
};
BoundingBox:
PUBLIC
PROC [polygon: Polygon]
RETURNS [Box] ~ {
box: Box ← [min: [s: 0, f: 0], max: [s: 0, f: 0]];
IF polygon#
NIL
THEN {
box ← polygon.first;
FOR each: Polygon ← polygon.rest, each.rest
UNTIL each=
NIL
DO
box.min ← box.min.Min[each.first.min];
box.max ← box.max.Max[each.first.max];
ENDLOOP;
};
RETURN[box];
};
CountBoxes:
PUBLIC
PROC [polygon: Polygon]
RETURNS [boxes:
INT ← 0] ~ {
WHILE polygon #
NIL
DO
boxes ← boxes + 1;
polygon ← polygon.rest;
ENDLOOP;
};
CountRuns:
PUBLIC
PROC [polygon: Polygon]
RETURNS [runs:
INT ← 0] ~ {
WHILE polygon #
NIL
DO
runs ← runs + NAT[polygon.first.max.s-polygon.first.min.s];
polygon ← polygon.rest;
ENDLOOP;
};
TestCreate:
PROC [polygon: Polygon]
RETURNS [Polygon] ~ {
Runs:
PROC [run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT],
repeat:
PROC[timesToRepeatScanline:
NAT]] ~ {
boxAction: BoxAction ~ { run[sMin: box.min.s, fMin: box.min.f, fSize: box.max.f-box.min.f] };
Map[polygon: polygon, boxAction: boxAction, runs: TRUE];
};
RETURN [CreateFromRuns[Runs]]
};
Map:
PUBLIC
PROC [polygon: Polygon, boxAction: BoxAction, runs:
BOOL ←
FALSE] ~ {
IF runs
THEN {
WHILE polygon #
NIL
DO
sMinRow: INTEGER ~ polygon.first.min.s;
sMaxRow: INTEGER ~ polygon.first.max.s;
FOR s:
INTEGER
IN [sMinRow..sMaxRow)
DO
FOR t: Polygon ← polygon, t.rest
UNTIL (t =
NIL
OR t.first.min.s # sMinRow)
DO
boxAction[[min: [s: s, f: t.first.min.f], max: [s: s+1, f: t.first.max.f]]];
ENDLOOP;
ENDLOOP;
UNTIL (polygon =
NIL
OR polygon.first.min.s # sMinRow)
DO
polygon ← polygon.rest;
ENDLOOP;
ENDLOOP;
}
ELSE {
FOR each: Polygon ← polygon, each.rest
UNTIL each=
NIL
DO
boxAction[each.first];
ENDLOOP;
};
};
Clip:
PUBLIC
PROC [polygon: Polygon, box: Box, boxAction: BoxAction, runs:
BOOL] ~ {
IF runs
THEN {
row: Polygon ← polygon;
WHILE row#
NIL
DO
smin: INTEGER ~ row.first.min.s;
smax: INTEGER ~ row.first.max.s;
IF smax<=box.min.s THEN NULL
ELSE IF smin>=box.max.s THEN EXIT
ELSE
FOR s:
INTEGER
IN [
MAX[smin, box.min.s]..
MIN[smax, box.max.s])
DO
run: Box ← [min: [s: s, f: 0], max: [s: s+1, f: 0]];
FOR t: Polygon ← row, t.rest
UNTIL t=
NIL
OR t.first.min.s#smin
DO
fmin: INTEGER ~ t.first.min.f;
fmax: INTEGER ~ t.first.max.f;
IF fmax<=box.min.f THEN NULL
ELSE IF fmin>=box.max.f THEN EXIT
ELSE {
run.min.f ← MAX[fmin, box.min.f];
run.max.f ← MIN[fmax, box.max.f];
boxAction[run];
};
ENDLOOP;
ENDLOOP;
UNTIL row=NIL OR row.first.min.s#smin DO row ← row.rest ENDLOOP;
ENDLOOP;
}
ELSE {
FOR each: Polygon ← polygon, each.rest
UNTIL each=
NIL
DO
IF each.first.max.s<=box.min.s THEN NULL
ELSE IF each.first.min.s>=box.max.s THEN EXIT
ELSE {
clippedBox: Box ~ each.first.Intersect[box];
IF clippedBox.Nonempty THEN boxAction[clippedBox];
};
ENDLOOP;
};
};
IsVisible:
PUBLIC
PROC [mask, clipper: Polygon]
RETURNS [visibility: Visibility] ~ {
IF mask = NIL OR clipper = NIL THEN RETURN [invisible];
IF mask.rest =
NIL
AND clipper.rest =
NIL
THEN {
sMin: INTEGER ~ MAX[mask.first.min.s, clipper.first.min.s];
sMax: INTEGER ~ MIN[mask.first.max.s, clipper.first.max.s];
fMin: INTEGER ~ MAX[mask.first.min.f, clipper.first.min.f];
fMax: INTEGER ~ MIN[mask.first.max.f, clipper.first.max.f];
IF sMax <= sMin OR fMax <= fMin THEN RETURN [invisible];
IF mask.first = [[sMin, fMin], [sMax, fMax]] THEN RETURN [visible];
RETURN [partlyVisible];
}
ELSE {
intersection: Polygon ← Intersection[mask, clipper];
visibility ←
IF intersection = NIL THEN invisible
ELSE IF Equal[intersection, mask] THEN visible
ELSE partlyVisible;
Destroy[intersection];
intersection ← NIL;
};
};
Equal:
PUBLIC
PROC [a, b: Polygon]
RETURNS [
BOOLEAN] ~ {
WHILE a#
NIL
AND b#
NIL
AND a#b
DO
IF a.first # b.first THEN RETURN [FALSE];
a ← a.rest;
b ← b.rest;
ENDLOOP;
RETURN [a = b];
};
FromList:
PROC [numbers:
LIST
OF
REF]
RETURNS [new:
LIST
OF Box] ~ {
For creating a new list via the debugger.
scratch: LIST OF Box ← GetScratch[];
last: LIST OF Box ← scratch;
WHILE numbers #
NIL
DO
sMin: REF INT ← NARROW[numbers.first];
fMin: REF INT ← NARROW[numbers.rest.first];
sMax: REF INT ← NARROW[numbers.rest.rest.first];
fMax: REF INT ← NARROW[numbers.rest.rest.rest.first];
IF last.rest = NIL THEN {last.rest ← GetScratch[]};
last ← last.rest;
last.first ← [[sMin^, fMin^], [sMax^, fMax^]];
numbers ← numbers.rest.rest.rest.rest;
ENDLOOP;
IF last = scratch THEN new ← NIL
ELSE {
new ← scratch.rest;
scratch.rest ← last.rest;
last.rest ← NIL;
};
};
Free list management
globalAvail: LIST OF Box ← NIL;
availCount: INT ← 0;
availLimit: INT ← 1000;
scratchChunkSize:
NAT ← 8;
CreateFromBox:
PUBLIC
ENTRY
PROC [box: Box]
RETURNS [polygon: Polygon] ~ {
ENABLE UNWIND => NULL;
IF Empty[box] THEN RETURN [NIL];
IF availCount = 0 THEN RETURN [LIST[box]];
polygon ← globalAvail;
polygon.first ← box;
globalAvail ← polygon.rest;
polygon.rest ← NIL;
availCount ← availCount - 1;
};
GetScratch:
ENTRY
PROC
RETURNS [scratch:
LIST
OF Box] ~ {
ENABLE UNWIND => NULL;
empty: Box ~ [[0, 0], [0, 0]];
t: LIST OF Box;
Consistency check:
t ← globalAvail; FOR i: INT IN [0..availCount) DO t ← t.rest ENDLOOP; IF t#NIL THEN ERROR;
WHILE availCount < scratchChunkSize
DO
globalAvail ← CONS[empty, globalAvail];
availCount ← availCount + 1;
ENDLOOP;
scratch ← t ← globalAvail;
THROUGH [0..scratchChunkSize-1) DO t ← t.rest ENDLOOP;
globalAvail ← t.rest;
availCount ← availCount - scratchChunkSize;
t.rest ← NIL;
};
FreeScratch:
ENTRY
PROC [scratch:
LIST
OF Box] ~ {
ENABLE UNWIND => NULL;
limit: INT ← MAX[availLimit, 0];
IF scratch #
NIL
THEN {
t: LIST OF Box ← scratch;
UNTIL t.rest =
NIL
DO
t ← t.rest;
availCount ← availCount + 1;
ENDLOOP;
availCount ← availCount + 1;
t.rest ← globalAvail;
globalAvail ← scratch;
};
WHILE availCount > limit
DO
t: LIST OF Box ← globalAvail;
globalAvail ← globalAvail.rest;
t.rest ← NIL;
availCount ← availCount - 1;
ENDLOOP;
};
END.