DIRECTORY
ImagerManhattan USING [DeviceRectangle, Polygon, Visibility],
ImagerManhattanExtras USING [];

ImagerManhattanImpl: CEDAR MONITOR
EXPORTS ImagerManhattan, ImagerManhattanExtras
~ BEGIN OPEN ImagerManhattan;

InvalidManhattanPolygon: PUBLIC ERROR ~ CODE;

Validate: PUBLIC PROC [polygon: Polygon] RETURNS [Polygon] ~ {
IF polygon # NIL THEN {
a: Polygon _ polygon;
b: Polygon _ polygon.rest;
IF a.first.sSize = 0 OR a.first.sSize = 0 THEN ERROR InvalidManhattanPolygon;
UNTIL b = NIL DO
IF b.first.sSize = 0 OR b.first.sSize = 0 THEN ERROR InvalidManhattanPolygon;
IF NOT (
(a.first.sMin = b.first.sMin AND a.first.sSize = b.first.sSize AND a.first.fMin+a.first.fSize <= b.first.fMin)
OR a.first.sMin+a.first.sSize <= b.first.sMin
)
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 DeviceRectangle _ GetScratch[];
last: LIST OF DeviceRectangle _ scratch;
secondLastRowStart: LIST OF DeviceRectangle _ NIL;
lastRowStart: LIST OF DeviceRectangle _ last;
secondLastRowCount: INTEGER _ -1;
lastRowCount: INTEGER _ 0;
Run: PROC[sMin, fMin: INTEGER, fSize: NAT] ~ {
fMaxCurrent: INTEGER ~ last.first.fMin+last.first.fSize;
IF sMin = last.first.sMin THEN {
IF last.first.sSize # 1 THEN ERROR;
SELECT fMin FROM
= fMaxCurrent => {last.first.fSize _ last.first.fSize + fSize};
> fMaxCurrent => {
IF last.rest = NIL THEN last.rest _ GetScratch[];
last _ last.rest;
last.first _ [sMin: sMin, fMin: fMin, sSize: 1, fSize: fSize];
lastRowCount _ lastRowCount + 1;
};
ENDCASE => ERROR;
}
ELSE {
IF secondLastRowCount = lastRowCount
AND secondLastRowStart.first.sMin + secondLastRowStart.first.sSize = lastRowStart.first.sMin
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 _ [sMin: sMin, fMin: fMin, sSize: 1, fSize: fSize];
lastRowStart _ last;
lastRowCount _ 1;
IF secondLastRowStart.first.sMin + secondLastRowStart.first.sSize > sMin THEN ERROR;
};
};
Repeat: PROC[timesToRepeatScanline: NAT] ~ {
t: LIST OF DeviceRectangle _ lastRowStart;
THROUGH [0..lastRowCount) DO
t.first.sSize _ t.first.sSize + timesToRepeatScanline;
t _ t.rest;
ENDLOOP;
};
last.first _ [FIRST[INTEGER], FIRST[INTEGER], 0, 0];
runs[Run, Repeat];
IF secondLastRowCount = lastRowCount
AND secondLastRowStart.first.sMin + secondLastRowStart.first.sSize = lastRowStart.first.sMin
AND TryToMergeRows[secondLastRowStart, lastRowCount] THEN {
last _ secondLastRowStart;
THROUGH [0..lastRowCount-1) DO
last _ last.rest;
ENDLOOP;
};
IF scratch.first.fSize # 0 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 DeviceRectangle, boxesPerRow: INT]
RETURNS [success: BOOLEAN] ~ {
size: NAT;
s: LIST OF DeviceRectangle _ secondLastRowStart;
t: LIST OF DeviceRectangle _ 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.fMin # t.first.fMin OR s.first.fSize # t.first.fSize THEN RETURN [FALSE];
s _ s.rest; t _ t.rest;
ENDLOOP;
t _ s; s _ secondLastRowStart;
size _ s.first.sSize + t.first.sSize;
FOR i: INT IN [0..boxesPerRow) DO
s.first.sSize _ size;
s _ s.rest;
ENDLOOP;
RETURN [TRUE];
};

Destroy: PUBLIC PROC [rectangleList: LIST OF DeviceRectangle] ~ {
FreeScratch[rectangleList];
};

Copy: PUBLIC PROC [polygon: Polygon] RETURNS [copy: Polygon] ~ {
scratch: LIST OF DeviceRectangle _ GetScratch[];
last: LIST OF DeviceRectangle _ 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 DeviceRectangle
];

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.sMin,
fMin: polygon.first.fMin,
fMax: polygon.first.fMin+polygon.first.fSize,
repeatCount: polygon.first.sSize,
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.sMin # r.currentRow.first.sMin 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.sSize;
r.s _ next.first.sMin;
};
};
IF next = NIL THEN r^ _ [LAST[INTEGER], 0, 0, 0, TRUE, NIL, NIL]
ELSE {
r.fMin _ next.first.fMin;
r.fMax _ r.fMin + next.first.fSize;
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 [sMin, fMin: INTEGER, fSize: NAT] ~ {
IF reader.done THEN ERROR;
IF sMin # reader.s THEN ERROR;
IF fMin # reader.fMin THEN ERROR;
IF fMin+fSize # reader.fMax THEN ERROR;
TRUSTED {Advance[@reader]};
};
MapRuns[polygon, Run];
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: DeviceRectangle] RETURNS [inverse: Polygon] ~ {
c: LIST OF DeviceRectangle _ GetScratch[];
last: LIST OF DeviceRectangle _ c;
bb: DeviceRectangle _ BoundingBox[b];
sMin: INTEGER _ MIN[universe.sMin, bb.sMin];
fMin: INTEGER _ MIN[universe.fMin, bb.fMin];
sMax: INTEGER _ MAX[universe.sMin + universe.sSize, bb.sMin + bb.sSize];
fMax: INTEGER _ MAX[universe.fMin + universe.fSize, bb.fMin + bb.fSize];
Emit: PROC [s0, f0, s1, f1: INTEGER] ~ {
s0 _ MAX[s0, universe.sMin];
s1 _ MIN[s1, universe.sMin+universe.sSize];
f0 _ MAX[f0, universe.fMin];
f1 _ MIN[f1, universe.fMin+universe.fSize];
IF s0 < s1 AND f0 < f1 THEN {
IF last.rest = NIL THEN last.rest _ GetScratch[];
last _ last.rest;
last.first _ [s0, f0, s1-s0, f1-f0];
};
};
s: INTEGER _ sMin;
f: INTEGER _ fMax;
FOR p: LIST OF DeviceRectangle _ b, p.rest UNTIL p=NIL DO
r: DeviceRectangle ~ p.first;
IF r.sMin > sMin OR p=b THEN {
Emit[sMin, f, s, fMax];
f _ fMin;
sMin _ s;
s _ r.sMin;
Emit[sMin, f, s, fMax];
sMin _ s;
s _ r.sMin + r.sSize;
};
IF sMin # r.sMin OR s # r.sMin + r.sSize THEN ERROR;
Emit[sMin, f, s, r.fMin];
f _ r.fMin + r.fSize;
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: DeviceRectangle _ 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] ~ {
IPair: TYPE ~ RECORD [s, f: INTEGER];
WHILE polygon # NIL DO
[polygon.first.sMin, polygon.first.fMin] _ IPair[polygon.first.sMin + sShift, polygon.first.fMin + fShift];
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: DeviceRectangle] RETURNS [i: Polygon _ NIL] ~ {
last: Polygon _ NIL;
junk: Polygon _ NIL;
UNTIL a = NIL DO
p: Polygon _ a;
sMin: INTEGER _ MAX[p.first.sMin, b.sMin];
fMin: INTEGER _ MAX[p.first.fMin, b.fMin];
sMax: INTEGER _ MIN[INT[p.first.sMin]+p.first.sSize, INT[b.sMin]+b.sSize];
fMax: INTEGER _ MIN[INT[p.first.fMin]+p.first.fSize, INT[b.fMin]+b.fSize];
a _ a.rest;
IF sMax <= sMin OR fMax <= fMin THEN {p.rest _ junk; junk _ p}
ELSE {
p.first _ [sMin, fMin, sMax-sMin, fMax-fMin];
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 DeviceRectangle] RETURNS [r: LIST OF DeviceRectangle] ~ {
b: LIST OF DeviceRectangle _ 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 DeviceRectangle] RETURNS [Polygon] ~ {
b: LIST OF DeviceRectangle _ SplitOffSecondHalf[rectangleList];
a: LIST OF DeviceRectangle _ rectangleList;
IF b = NIL THEN {
WHILE a # NIL DO
a1: LIST OF DeviceRectangle _ a;
a _ a1.rest;
a1.rest _ NIL;
IF a1.first.sSize > 0 AND a1.first.fSize > 0 THEN b _ FullyDestructiveUnion[b, a1];
ENDLOOP;
RETURN [b]
}
ELSE RETURN [FullyDestructiveUnion[Canonicalize[a], Canonicalize[b]]];
};

BoundingBox: PUBLIC PROC [polygon: Polygon] RETURNS [DeviceRectangle] ~ {
sMin, fMin: INTEGER _ LAST[INTEGER];
sMax, fMax: INTEGER _ FIRST[INTEGER];
WHILE polygon # NIL DO
r: DeviceRectangle _ polygon.first;
IF r.sSize # 0 AND r.fSize # 0 THEN {
sMin _ MIN[sMin, r.sMin];
fMin _ MIN[fMin, r.fMin];
sMax _ MAX[sMax, r.sMin+r.sSize];
fMax _ MAX[fMax, r.fMin+r.fSize];
};
polygon _ polygon.rest;
ENDLOOP;
IF sMin > sMax THEN {sMin _ fMin _ sMax _ fMax _ 0};
RETURN [[sMin: sMin, fMin: fMin, sSize: sMax-sMin, fSize: fMax-fMin]]
};

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 + polygon.first.sSize;
polygon _ polygon.rest;
ENDLOOP;
};

TestCreate: PROC [polygon: Polygon] RETURNS [Polygon] ~ {
Runs: PROC[
run: PROC[sMin, fMin: INTEGER, fSize: NAT],
repeat: PROC[timesToRepeatScanline: NAT]] ~ {MapRuns[polygon, run]};
RETURN [CreateFromRuns[Runs]]
};

MapRuns: PUBLIC PROC [polygon: Polygon, run: PROC [sMin, fMin: INTEGER, fSize: NAT]] ~ {
s: INTEGER _ FIRST[INTEGER];
WHILE polygon # NIL DO
sMinRow: INTEGER ~ polygon.first.sMin;
sMaxRow: INTEGER ~ sMinRow + polygon.first.sSize;
FOR s: INTEGER IN [sMinRow..sMaxRow) DO
FOR t: Polygon _ polygon, t.rest UNTIL (t = NIL OR t.first.sMin # sMinRow) DO
run[s, t.first.fMin, t.first.fSize];
ENDLOOP;
ENDLOOP;
UNTIL (polygon = NIL OR polygon.first.sMin # sMinRow) DO
polygon _ polygon.rest;
ENDLOOP;
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.sMin, clipper.first.sMin];
sMax: INTEGER ~ MIN[mask.first.sMin + mask.first.sSize, clipper.first.sMin+clipper.first.sSize];
fMin: INTEGER ~ MAX[mask.first.fMin, clipper.first.fMin];
fMax: INTEGER ~ MIN[mask.first.fMin + mask.first.fSize, clipper.first.fMin+clipper.first.fSize];
IF sMax <= sMin OR fMax <= fMin THEN RETURN [invisible];
IF mask.first = [sMin, fMin, sMax-sMin, fMax-fMin] 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 DeviceRectangle] ~ {
scratch: LIST OF DeviceRectangle _ GetScratch[];
last: LIST OF DeviceRectangle _ scratch;
WHILE numbers # NIL DO
sMin: REF INT _ NARROW[numbers.first];
fMin: REF INT _ NARROW[numbers.rest.first];
sSize: REF INT _ NARROW[numbers.rest.rest.first];
fSize: REF INT _ NARROW[numbers.rest.rest.rest.first];
IF last.rest = NIL THEN {last.rest _ GetScratch[]};
last _ last.rest;
last.first _ [sMin^, fMin^, sSize^, fSize^];
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 DeviceRectangle _ NIL;
availCount: INT _ 0;
availLimit: INT _ 1000;
scratchChunkSize: NAT _ 8;

CreateFromBox: PUBLIC ENTRY PROC [deviceRectangle: DeviceRectangle] RETURNS [polygon: Polygon] ~ {
ENABLE UNWIND => NULL;
IF deviceRectangle.sSize = 0 OR deviceRectangle.fSize = 0 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 DeviceRectangle] ~ {
ENABLE UNWIND => NULL;
empty: DeviceRectangle ~ [0, 0, 0, 0];
t: LIST OF DeviceRectangle;
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 DeviceRectangle] ~ {
ENABLE UNWIND => NULL;
limit: INT _ MAX[availLimit, 0];
IF scratch # NIL THEN {
t: LIST OF DeviceRectangle _ 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 DeviceRectangle _ globalAvail;
globalAvail _ globalAvail.rest;
t.rest _ NIL;
availCount _ availCount - 1;
ENDLOOP;
};

END.
’ImagerManhattanImpl.mesa
Copyright c 1984, 1985 by Xerox Corporation.  All rights reserved.
Michael Plass, October 30, 1985 9:55:45 am PST
Doug Wyatt, March 7, 1985 6:15:55 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;
Κn˜
code™Kšœ
Οm
œ7™BK™.K™(—K˜š
Οk	˜	Kšœžœ(˜=Kšœžœ˜—K˜KšΠblœž
˜"Kšžœ'˜.Kšœžœ
žœ˜K˜šœžœ
žœžœ
˜-K˜—šΟnœžœ
žœžœ˜>šžœžœ
žœ˜Kš
œ˜Kš
œ˜Kšžœžœžœ
žœ˜Mšžœžœ
ž˜Kšžœžœžœ
žœ˜Mšžœ
žœ˜Kšœžœžœ,˜nKšžœ+˜-K˜
—Kšžœ
žœ˜#K˜K˜Kšžœ
˜—Kš
œ˜—Kšžœ
˜Kš
œ˜K˜—š œžœ
žœ˜šœžœ
˜Kšœžœ
žœ	žœ˜+Kšœžœžœ
˜(Kš
œ
˜
—Kšœžœ˜ Kšœ	žœ
žœ ˜0Kšœžœ
žœ˜(Kšœžœ
žœžœ
˜2Kšœžœ
žœ˜-Kšœžœ˜!Kšœžœ˜š œžœ
žœ	žœ˜.Kšœ
žœ$˜8šžœžœ˜ Kšžœžœ
žœ
˜#šžœž˜Kš
œ?˜?š
œ˜Kšžœ
žœ
žœ˜1Kš
œ˜Kš
œ>˜>Kš
œ ˜ Kš
œ˜—Kšžœžœ
˜—Kš
œ
˜
—šžœ˜Kšžœ"˜$KšžœY˜\Kšžœ1˜4KšžœR˜VKšžœžœ
žœ
žœ-˜JKš
œ"˜"Kš
œ"˜"Kš
œ>˜>Kš
œ˜Kš
œ˜KšžœGžœ
žœ
˜TKš
œ˜—Kš
œ˜—š œžœžœ˜,Kšœžœ
žœ ˜*šžœž˜Kš
œ6˜6K˜Kšžœ
˜—Kš
œ˜—Kš	œžœ
žœžœ
žœ	˜4Kš
œ˜Kšžœ"˜$KšžœY˜\šžœ2žœ˜;Kš
œ˜šžœž˜Kš
œ˜Kšžœ
˜—Kš
œ˜—šžœžœ˜!Kš
œ˜Kš
œ˜Kšœžœ
˜Kš
œ
˜
—Kšžœ
žœžœž˜)šžœ˜Kš
œ˜Kš
œ˜Kšœžœ
˜Kš
œ˜—Kš
œ˜Kš
œ˜K˜—š
 œžœžœ
žœžœ
˜TKšžœžœ˜™K™BK™4K™.—Kšœžœ
˜
Kšœžœ
žœ&˜0Kšœžœ
žœ&˜0Kš
žœžœ
žœžœžœ
˜5Kšžœžœ
žœžœ˜&šžœžœ
žœž˜!Kš
žœžœžœ
žœžœ˜TK˜Kšžœ
˜—Kš
œ˜Kš
œ%˜%šžœžœ
žœž˜!Kšœ
žœ˜K˜Kšžœ
˜—Kšžœžœ˜Kš
œ˜K˜—š
 œžœ
žœžœ
žœ˜AKš
œ˜Kš
œ˜K˜—š œžœ
žœžœ˜@Kšœ	žœ
žœ ˜0Kšœžœ
žœ˜(šžœžœ
ž˜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š
œ!˜!Kšœžœ
˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ˜K˜—š œžœ
žœžœ
žœž	œ˜9Kš
œ"˜"šžœžœ
žœ+žœ˜Ašžœžœ˜Kš
œ"˜"K˜Kš
œ˜Kš
œ
˜
—šžœ
žœžœ
žœ˜Kš
œ˜Kš
œ!˜!Kš
œ˜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˜—š œžœ
žœžœ˜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˜—š œžœ)žœ˜SKšœžœ
žœ ˜*Kšœžœ
žœ˜"Kš
œ%˜%Kšœžœžœ˜,Kšœžœžœ˜,Kšœžœžœ5˜HKšœžœžœ5˜Hš œžœžœ˜(Kšœžœ˜Kšœžœ#˜+Kšœžœ˜Kšœžœ#˜+šžœ	žœ	žœ˜Kšžœ
žœ
žœ˜1Kš
œ˜Kš
œ$˜$Kš
œ˜—Kš
œ˜—Kšœžœ˜Kšœžœ˜šžœžœ
žœžœžœ
ž˜9Kš
œ˜šžœžœžœ˜K˜K˜	Kš
œ	˜	K˜K˜Kš
œ	˜	K˜K˜—Kšžœžœžœ
žœ
˜4K˜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š
œk˜kKš
œ˜Kšžœ
˜—Kš
œ˜K˜—š œžœžœ˜DJ˜Jš
œ˜Jš
œ˜Kš
œ˜K˜—š œžœ
žœžœ˜FK˜Kš
œ˜Kš
œ˜K˜—š
 œžœ
žœžœžœ˜SKšžœžœ
žœžœ
žœ
žœžœ˜(Kšžœ
žœ
žœ ˜4šžœ˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ˜K˜—š
 œžœ
žœ"žœžœ˜\Kšœžœ
˜Kšœžœ
˜šžœžœ
ž˜Kš
œ˜Kšœžœžœ˜*Kšœžœžœ˜*Kš	œžœžœ
žœžœ˜JKš	œžœžœ
žœžœ˜JK˜Kšžœžœžœ˜>šžœ˜Kš
œ-˜-Kšžœžœ
žœžœ˜?K˜
—Kšžœ
˜—Kšžœžœ
žœ
žœ
˜#Kš
œ˜Kš
œ˜K˜—š œžœ
žœžœ˜KKš
œ˜Kš
œ˜Kš
œ˜K˜—š œžœžœ
žœžœžœ
žœ˜^Kšœžœ
žœ˜Kšœžœ˜šžœžœ
ž˜Kš
œ˜K˜Kšžœžœ
žœ
žœ˜,Kšžœ
˜—Kšžœžœž˜Kšžœžœ˜ Kš
œ˜K˜—š œžœ
žœžœ
žœžœ˜XKšœžœ
žœ5˜?Kšœžœ
žœ!˜+šžœžœ
žœ˜šžœžœ
ž˜Kšœžœ
žœ˜ K˜Kšœ
žœ
˜Kšžœžœžœ"˜SKšžœ
˜—Kšžœ˜
Kš
œ
˜
—Kšžœ
žœ;˜FKš
œ˜K˜—š œžœ
žœžœ˜IKšœžœžœ
žœ˜$Kšœžœžœ
žœ˜%šžœžœ
ž˜Kš
œ#˜#šžœ
žœ
žœ˜%Kšœžœ˜Kšœžœ˜Kšœžœ˜!Kšœžœ˜!Kš
œ˜—Kš
œ˜Kšžœ
˜—Kšžœ
žœ!˜4Kšžœ?˜EKš
œ˜K˜—š
 
œžœ
žœžœ	žœ	˜Gšžœžœ
ž˜Kš
œ˜Kš
œ˜Kšžœ
˜—Kš
œ˜K˜—š
 	œžœ
žœžœžœ	˜Ešžœžœ
ž˜Kš
œ"˜"Kš
œ˜Kšžœ
˜—Kš
œ˜K˜—š 
œžœžœ˜9š œžœ
˜Kšœžœ
žœ	žœ˜+Kšœžœžœ˜D—Kšžœ˜Kš
œ˜K˜—š œžœ
žœžœžœ	žœ˜XKšœžœžœ
žœ˜šžœžœ
ž˜Kšœ	žœ˜&Kšœ	žœ!˜1šžœžœ
žœž˜'š	žœžœžœ
žœž˜MKš
œ$˜$Kšžœ
˜—Kšžœ
˜—šžœžœ
žœž˜8Kš
œ˜Kšžœ
˜—Kšžœ
˜—Kš
œ˜K˜—š 	œžœ
žœžœ˜TKšžœžœ
žœžœ
žœ
žœ
˜7š
žœ
žœ
žœžœ
žœ˜0Kšœžœžœ&˜9KšœžœžœM˜`Kšœžœžœ&˜9KšœžœžœM˜`Kšžœžœžœ
žœ
˜8Kšžœ1žœ
žœ˜IKšžœ˜Kš
œ
˜
—šžœ˜Kš
œ4˜4š
œ˜Kšžœžœ
žœ
˜$Kšžœ
žœžœ˜.Kšžœ˜—Kš
œ˜Kšœžœ
˜K˜—Kš
œ˜K˜—š
 œžœ
žœžœžœ˜8šžœžœ
žœžœ
žœž˜ Kšžœžœ
žœžœ˜)K˜K˜Kšžœ
˜—Kšžœ	˜Kš
œ˜K˜—š œžœžœ
žœ
žœžœžœ
žœ˜PK™)Kšœ	žœ
žœ ˜0Kšœžœ
žœ˜(šžœžœ
ž˜Kšœžœ
žœžœ˜&Kšœžœ
žœžœ˜+Kšœžœ
žœžœ˜1Kšœžœ
žœžœ˜6Kšžœ
žœ
žœ˜3Kš
œ˜Kš
œ,˜,Kš
œ&˜&Kšžœ
˜—Kšžœžœž˜ šžœ˜Kš
œ˜Kš
œ˜Kšœžœ
˜Kš
œ˜—Kš
œ˜K˜—™Kšœ
žœ
žœžœ
˜+Kšœžœ˜Kšœžœ˜šœžœ˜K˜—š
 
œžœ
žœ
žœ$žœ˜bKšžœ
žœžœ
˜Kš
žœžœžœ
žœžœ˜LKšžœžœ
žœžœ˜6Kš
œ˜Kš
œ ˜ Kš
œ˜Kšœžœ
˜Kš
œ˜Kš
œ˜K˜—š 
œžœ
žœ
žœžœ
žœ˜EKšžœ
žœžœ
˜K˜&Kšœžœ
žœ˜™Kšœžœžœ
žœžœžœžœžœ
žœ
žœ
™Z—šžœž˜&Kšœžœ˜'Kš
œ˜Kšžœ
˜—Kš
œ˜Kšžœžœ
žœ
˜6Kš
œ˜Kš
œ+˜+Kšœ	žœ
˜
Kš
œ˜K˜—š
 œžœ
žœžœ
žœ˜>Kšžœ
žœžœ
˜Kšœžœžœ˜ šžœžœ
žœ˜Kšœžœ
žœ˜%šžœ
žœ
ž˜K˜Kš
œ˜Kšžœ
˜—Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜—šžœž˜Kšœžœ
žœ˜)Kš
œ˜Kšœ	žœ
˜
Kš
œ˜Kšžœ
˜—Kš
œ˜—K˜—Kšžœ
˜—…—Aδ^δ