DIRECTORY
ImagerManhattan USING [Polygon, Visibility],
SF USING [Add, Box, BoxAction, Empty, Intersect, Max, Min, Nonempty, Vec];

ImagerManhattanImpl: CEDAR MONITOR
IMPORTS SF
EXPORTS ImagerManhattan
~ BEGIN OPEN ImagerManhattan, 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] ~ {
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];
};

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];
};
};

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]]];
};

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: NAT ~ polygon.first.min.s;
sMaxRow: NAT ~ polygon.first.max.s;
FOR s: NAT 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: NAT ~ row.first.min.s;
smax: NAT ~ row.first.max.s;
IF smax<=box.min.s THEN NULL
ELSE IF smin>=box.max.s THEN EXIT
ELSE FOR s: NAT 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: NAT ~ t.first.min.f;
fmax: NAT ~ 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] ~ {
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;
};
};

globalAvail: LIST OF Box _ NIL;
availCount: INT _ 0;
availLimit: INT _ 1000;
scratchChunkSize: NAT _ 8;

CreateFromBox: PUBLIC ENTRY PROC [deviceRectangle: Box] RETURNS [polygon: Polygon] ~ {
ENABLE UNWIND => NULL;
IF Empty[deviceRectangle] THEN RETURN [NIL];
IF availCount = 0 THEN RETURN [LIST[deviceRectangle]];
polygon _ globalAvail;
polygon.first _ deviceRectangle;
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;
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.
˜ImagerManhattanImpl.mesa
Copyright c 1984, 1985, 1986 by Xerox Corporation.  All rights reserved.
Michael Plass, October 30, 1985 9:55:45 am PST
Doug Wyatt, March 7, 1986 4:36:43 pm PST
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.
[] _ Validate[inverse];
IF Intersection[b, inverse] # NIL THEN ERROR;
IF NOT Equal[Union[a, b], Union[diff, b]] THEN ERROR;
For creating a new list via the debugger.
Free list management
Consistency check:
t _ globalAvail; FOR i: INT IN [0..availCount) DO t _ t.rest ENDLOOP; IF t#NIL THEN ERROR;
Κβ˜
code™Kšœ
Οm
œ=™HK™.K™(—K˜š
Οk	˜	Kšœžœ˜,Kšžœ
žœB˜J—K˜KšΠblœž
˜"Kšžœ
ž˜
Kšžœ˜Kšœžœ
žœžœ
˜!K˜šœžœ
žœžœ
˜-K˜—šΟnœžœ
žœžœ˜>šžœžœ
žœ˜Kš
œ˜Kš
œ˜Kšžœžœ
žœ˜5šžœžœ
ž˜Kšžœžœ
žœ˜5šžœ
žœ˜Kšœžœžœ ˜dKšžœ˜!K˜
—Kšžœ
žœ˜#K˜K˜Kšžœ
˜—Kš
œ˜—Kšžœ
˜Kš
œ˜K˜—š œžœ
žœ˜šœžœ
˜Kšœžœ
žœ	žœ˜+Kšœžœžœ
˜(Kš
œ
˜
—Kšœžœ˜ Kšœ	žœ
žœ˜$Kšœžœ
žœ˜Kšœžœ
žœžœ
˜&Kšœžœ
žœ˜!Kšœžœ˜!Kšœžœ˜š œžœ
žœ	žœ˜.Kšœ
žœ˜(šžœžœ˜!Kšžœ'žœ
žœ
˜4šžœž˜Kš
œ?˜?š
œ˜Kšžœ
žœ
žœ˜1Kš
œ˜Kš
œH˜HKš
œ ˜ Kš
œ˜—Kšžœžœ
˜—Kš
œ
˜
—šžœ˜Kšžœ"˜$Kšžœ:˜=Kšžœ1˜4KšžœR˜VKšžœžœ
žœ
žœ-˜JKš
œ"˜"Kš
œ"˜"Kš
œH˜HKš
œ˜Kš
œ˜Kšžœ'žœ
žœ
˜4Kš
œ˜—Kš
œ˜—š œžœžœ˜,Kšœžœ
žœ˜šžœž˜Kš
œ6˜6K˜Kšžœ
˜—Kš
œ˜—Kš
œ˜Kš
œ˜Kšžœ"˜$Kšžœ:˜=šžœ2žœ˜;Kš
œ˜šžœž˜Kš
œ˜Kšžœ
˜—Kš
œ˜—šžœ)žœ˜1Kš
œ˜Kš
œ˜Kšœžœ
˜Kš
œ
˜
—Kšžœ
žœžœž˜)šžœ˜Kš
œ˜Kš
œ˜Kšœžœ
˜Kš
œ˜—Kš
œ˜Kš
œ˜K˜—š
 œžœžœ
žœžœ
˜HKšžœžœ˜™K™BK™4K™.—Kšœžœ
˜
Kšœžœ
žœ˜$Kšœžœ
žœ˜$Kš
žœžœ
žœžœžœ
˜5Kšžœžœ
žœžœ˜&šžœžœ
žœž˜!Kš
žœžœžœ
žœžœ˜VK˜Kšžœ
˜—Kš
œ˜Kš
œ˜šžœžœ
žœž˜!Kšœ
žœ˜K˜Kšžœ
˜—Kšžœžœ˜Kš
œ˜K˜—š
 œžœ
žœžœ
žœ	˜5Kš
œ˜Kš
œ˜K˜—š œžœ
žœžœ˜@Kšœ	žœ
žœ˜$Kšœžœ
žœ˜šžœžœ
ž˜Kšžœ
žœ
žœ˜3Kš
œ˜Kš
œ˜Kš
œ˜Kšžœ
˜—Kšžœžœž˜!šžœ˜Kš
œ˜Kš
œ˜Kšœžœ
˜Kš
œ˜—Kš
œ˜Kš
œ˜K˜—šœžœžœ˜Kšœžœ
˜Kšœ
žœ
˜Kšœžœ
˜Kšœžœ
žœ˜#Kš
œ˜K˜—š 	œžœžœžœ˜>Kšžœžœ
žœ
žœžœ
žœžœžœžœ˜Gšžœ
žœ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ5˜5Kšœžœ
˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ˜K˜—š œžœ
žœžœ
žœž	œ˜9Kš
œ"˜"šžœžœ
žœ-žœ˜Cšžœžœ˜Kš
œ"˜"K˜Kš
œ˜Kš
œ
˜
—šžœ
žœžœ
žœ˜Kš
œ˜Kš
œ2˜2Kš
œ˜Kš
œ˜—Kš
œ˜—Kšžœžœ
žœžœ
žœžœžœžœ
˜@šžœ˜Kš
œ˜Kš
œ˜Kš
œ˜Kšžœžœ˜%Kš
œ˜—Kš
œ˜K˜—š œžœ
žœžœ
žœžœž	œ˜DKšžœ
žœ
žœ
˜šžœ	ž˜šžœžœžœ˜;Kšœžœžœ˜-Kš
œ˜Kš
œ&˜&Kš
œ
˜
—Kšžœ˜Kšžœ
˜—Kš
œ˜K˜—š 
œžœ˜'Kš
œ$˜$š œžœ˜Kšžœ
žœ
žœ
˜Kšžœžœ
žœ
˜#Kšžœžœ
žœ
˜&Kšžœžœ
žœ
˜&Kšžœžœ
žœ
˜&Kšžœ˜Kš
œ˜—Kšœžœ˜Kšžœ
žœ
žœ
žœ
˜Kš
œ˜K˜—š œžœ
žœžœ˜8š œžœžœ
žœ	žœžœžœžœ˜lKš
œ˜Kš
œ˜šžœžœž˜&Kšœžœ
˜Kšœžœ
˜Kšœžœžœ	˜Kšœžœžœ+˜@Kšœžœžœ
˜%šžœžœž˜'Kšœžœžœ
žœ˜ Kšœžœ
˜Kšžœžœ˜.Kšžœžœžœ˜;Kš
œ˜š
ž˜šžœ
žœ
ž˜šœžœ˜+Kšœžœ˜Kš
œ˜Kš
œ˜—šœžœ˜+Kšœžœ˜Kš
œ˜Kš
œ˜—Kšžœžœ
˜—Kšžœ
˜—Kšžœžœ7žœ˜RKšžœ
˜—šžœžœžœžœ˜.Kšžœžœ˜1Kš
œ˜Kš
œ˜Kš
œ˜—Kšžœ
˜—Kš
œ˜—Kšžœ˜Kš
œ˜K˜—š œžœ
žœžœ˜?š œžœžœ
žœ	žœžœžœžœ˜lKš
œ˜Kš
œ˜š
ž˜Kšœžœ
˜Kšœžœ
˜Kšœžœžœ
˜%Kš
žœžœžœžœ
žœ
˜UKš
žœžœžœžœ
žœ
˜UKš
œ˜Kšœ
žœ/˜?šžœžœž˜(Kšœžœžœ˜0Kšœžœžœ˜0Kšžœ
žœ3žœ˜Lšžœž˜Kš
œ$˜$Kš
œ$˜$Kšžœžœ
˜—Kšžœ
˜—šžœžœ˜Kšžœžœ˜/Kš
œ!˜!Kš
œ!˜!K˜—Kšžœ
˜—Kš
œ˜—Kšžœ˜Kš
œ˜K˜—š œžœžœ˜GKšœžœ
žœ˜Kšœžœ
žœ	˜Kš
œ˜Kšœžœžœ˜.Kšœžœžœ˜.Kšœžœžœ˜.Kšœžœžœ˜.š œžœžœ˜(Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜šžœ	žœ	žœ˜Kšžœ
žœ
žœ˜1Kš
œ˜Kš
œ"˜"Kš
œ˜—Kš
œ˜—Kšœžœ˜Kšœžœ˜šžœžœ
žœžœžœ
ž˜-Kš
œ˜šžœžœžœ˜K˜K˜	Kš
œ	˜	K˜K˜Kš
œ	˜	K˜K˜—Kšžœžœ
žœ
žœ
˜,K˜K˜Kš
ž˜—K˜K˜Kšžœ
žœž˜šžœ˜Kš
œ˜Kš
œ˜Kšœžœ
˜K˜—Kš
œ˜Kš
œ™Kšžœžœ
žœ
žœ
™-Kš
œ˜K˜—š 
œžœ
žœžœ˜CKš
œ˜Kš
œ"˜"Kš
žœžœ
žœ
žœ
žœ˜0šžœ˜Kš
œ!˜!Kš
œ˜K˜—Kšžœ
žœ$žœ
žœ
™5Kš
œ˜K˜—š œžœ
žœ$žœ˜BK˜$šžœžœ
ž˜K˜2K˜2Kš
œ˜Kšžœ
˜—Kš
œ˜K˜—š œžœžœ˜DJ˜Jš
œ˜Jš
œ˜Kš
œ˜K˜—š œžœ
žœžœ˜FK˜Kš
œ˜Kš
œ˜K˜—š
 œžœ
žœžœžœ˜SKšžœžœ
žœžœ
žœ
žœžœ˜(Kšžœ
žœ
žœ ˜4šžœ˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ˜K˜—š
 œžœ
žœžœžœ˜PKšœžœ
˜Kšœžœ
˜šžœžœ
ž˜Kš
œ˜Kšœžœžœ˜,Kšœžœžœ˜,Kšœžœžœ˜,Kšœžœžœ˜,K˜Kšžœžœžœ˜>šžœ˜Kš
œ'˜'Kšžœžœ
žœžœ˜?K˜
—Kšžœ
˜—Kšžœžœ
žœ
žœ
˜#Kš
œ˜Kš
œ˜K˜—š œžœ
žœžœ˜KKš
œ˜Kš
œ˜Kš
œ˜K˜—š œžœžœ
žœžœžœ
žœ	˜FKšœžœ
žœ	˜Kšœžœ˜šžœžœ
ž˜Kš
œ˜K˜Kšžœžœ
žœ
žœ˜,Kšžœ
˜—Kšžœžœž˜Kšžœžœ˜ Kš
œ˜K˜—š œžœ
žœžœ
žœžœ˜LKšœžœ
žœ)˜3Kšœžœ
žœ˜šžœžœ
žœ˜šžœžœ
ž˜Kšœžœ
žœ	˜K˜Kšœ
žœ
˜Kšžœžœ"˜<Kšžœ
˜—Kšžœ˜
Kš
œ
˜
—Kšžœ
žœ;˜FKš
œ˜K˜—š œžœ
žœžœ
˜=Kš
œ2˜2šžœ	žœ
žœ˜K˜šžœ)žœžœ
ž˜=K˜&K˜&Kšžœ
˜—K˜—Kšžœ˜Kš
œ˜K˜—š
 
œžœ
žœžœ	žœ	˜Gšžœžœ
ž˜Kš
œ˜Kš
œ˜Kšžœ
˜—Kš
œ˜K˜—š
 	œžœ
žœžœžœ	˜Ešžœžœ
ž˜Kšœžœ*˜;Kš
œ˜Kšžœ
˜—Kš
œ˜K˜—š 
œžœžœ˜9š œžœžœ
žœ	žœžœžœ˜fK˜]Kšœ2žœ˜8Kš
œ˜—Kšžœ˜Kš
œ˜K˜—š
 œžœ
žœ0žœžœ˜Qšžœžœ˜šžœžœ
ž˜Kšœ	žœ˜#Kšœ	žœ˜#šžœžœ
žœž˜#š	žœžœžœ
žœž˜NKš
œL˜LKšžœ
˜—Kšžœ
˜—šžœžœ
žœ ž˜9Kš
œ˜Kšžœ
˜—Kšžœ
˜—K˜
—šžœ˜šžœ$žœžœ
ž˜8Kš
œ˜Kšžœ
˜—K˜—Kš
œ˜K˜—š œžœ
žœ:žœ˜Tšžœžœ˜K˜šžœžœ
ž˜Kšœžœ˜Kšœžœ˜Kšžœžœ
ž˜Kšžœ
žœžœ
ž˜!š
žœ
žœžœ
žœžœžœž˜BKš
œ4˜4š	žœžœžœ
žœž˜AKšœžœ˜Kšœžœ˜Kšžœžœ
ž˜Kšžœ
žœžœ
ž˜!šžœ˜Kšœžœ˜!Kšœžœ˜!Kš
œ˜K˜—Kšžœ
˜—Kšžœ
˜—Kš
žœžœ
žœžœžœ
˜@Kšžœ
˜—K˜
—šžœ˜šžœ$žœžœ
ž˜8Kšžœžœ
ž˜(Kšžœ
žœžœ
ž˜-šžœ˜Kš
œ,˜,Kšžœžœ˜2K˜—Kšžœ
˜—K˜—Kš
œ˜K˜—š 	œžœ
žœžœ˜TKšžœžœ
žœžœ
žœ
žœ
˜7š
žœ
žœ
žœžœ
žœ˜0Kšœžœžœ(˜;Kšœžœžœ(˜;Kšœžœžœ(˜;Kšœžœžœ(˜;Kšžœžœžœ
žœ
˜8Kšžœ+žœ
žœ˜CKšžœ˜Kš
œ
˜
—šžœ˜Kš
œ4˜4š
œ˜Kšžœžœ
žœ
˜$Kšžœ
žœžœ˜.Kšžœ˜—Kš
œ˜Kšœžœ
˜K˜—Kš
œ˜K˜—š
 œžœ
žœžœžœ˜8šžœžœ
žœžœ
žœž˜ Kšžœžœ
žœžœ˜)K˜K˜Kšžœ
˜—Kšžœ	˜Kš
œ˜K˜—š œžœžœ
žœ
žœžœžœ
žœ	˜DK™)Kšœ	žœ
žœ˜$Kšœžœ
žœ˜šžœžœ
ž˜Kšœžœ
žœžœ˜&Kšœžœ
žœžœ˜+Kšœžœ
žœžœ˜0Kšœžœ
žœžœ˜5Kšžœ
žœ
žœ˜3Kš
œ˜Kš
œ.˜.Kš
œ&˜&Kšžœ
˜—Kšžœžœž˜ šžœ˜Kš
œ˜Kš
œ˜Kšœžœ
˜Kš
œ˜—Kš
œ˜K˜—™Kšœ
žœ
žœžœ
˜Kšœžœ˜Kšœžœ˜šœžœ˜K˜—š
 
œžœ
žœ
žœžœ˜VKšžœ
žœžœ
˜Kšžœžœ
žœžœ˜,Kšžœžœ
žœžœ˜6Kš
œ˜Kš
œ ˜ Kš
œ˜Kšœžœ
˜Kš
œ˜Kš
œ˜K˜—š 
œžœ
žœ
žœžœ
žœ	˜9Kšžœ
žœžœ
˜K˜Kšœžœ
žœ˜™Kšœžœžœ
žœžœžœžœžœ
žœ
žœ
™Z—šžœž˜&Kšœžœ˜'Kš
œ˜Kšžœ
˜—Kš
œ˜Kšžœžœ
žœ
˜6Kš
œ˜Kš
œ+˜+Kšœ	žœ
˜
Kš
œ˜K˜—š
 œžœ
žœžœ
žœ	˜2Kšžœ
žœžœ
˜Kšœžœžœ˜ šžœžœ
žœ˜Kšœžœ
žœ˜šžœ
žœ
ž˜K˜Kš
œ˜Kšžœ
˜—Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜—šžœž˜Kšœžœ
žœ˜Kš
œ˜Kšœ	žœ
˜
Kš
œ˜Kšžœ
˜—Kš
œ˜—K˜—Kšžœ
˜—…—BΘaB