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.smax;
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: INTEGERMIN[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: INTEGERMIN[as, bs];
duplicates: NATMIN[aReader.repeatCount, bReader.repeatCount];
somethingInScanline: BOOLEANFALSE;
WHILE s = aReader.s OR s = bReader.s DO
fStart: INTEGERLAST[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: BOOLEANFALSE;
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: INTEGERMAX[aReader.fMin, bReader.fMin];
fMax: INTEGERMIN[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: INTEGERMIN[universe.min.s, bb.min.s];
fMin: INTEGERMIN[universe.min.f, bb.min.f];
sMax: INTEGERMAX[universe.max.s, bb.max.s];
fMax: INTEGERMAX[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: INTEGERMAX[p.first.min.s, b.min.s];
fMin: INTEGERMAX[p.first.min.f, b.min.f];
sMax: INTEGERMIN[p.first.max.s, b.max.s];
fMax: INTEGERMIN[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: BOOLFALSE] ~ {
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 INTNARROW[numbers.first];
fMin: REF INTNARROW[numbers.rest.first];
sMax: REF INTNARROW[numbers.rest.rest.first];
fMax: REF INTNARROW[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: INTMAX[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.