DIRECTORY
CornerStitching;
CornerStitchingImpl: CEDAR MONITOR
EXPORTS CornerStitching =
BEGIN

Tesselation: TYPE = CornerStitching.Tesselation;
Tile: TYPE = CornerStitching.Tile;
Number: TYPE = CornerStitching.Number;
Coord: TYPE = CornerStitching.Coord;
Rect: TYPE = CornerStitching.Rect;

NEdge: PROCEDURE [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.en.pos.y]};
EEdge: PROCEDURE [t: REF Tile] RETURNS [Number] = INLINE {RETURN [PtoR[t.ne].pos.x]};
SEdge: PROCEDURE [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.pos.y]};
WEdge: PROCEDURE [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.pos.x]};
TileValue: PUBLIC ERROR = CODE;
TileDeleted: PUBLIC ERROR = CODE;
DegenerateTile: ERROR = CODE;
neLimitCoord: Coord = [x: Number.LAST, y: Number.LAST];
nwLimitCoord: Coord = [x: Number.FIRST, y: Number.LAST];
swLimitCoord: Coord = [x: Number.FIRST, y: Number.FIRST];
seLimitCoord: Coord = [x: Number.LAST, y: Number.FIRST];
emptyRect: Rect = [x1: Number.FIRST+1, y1: Number.FIRST, x2: Number.LAST-1, y2: Number.LAST-1];
guard: REF ANY = $CornerStitchingPrivateEdgeGuard;
deleted: REF ANY = $CornerStitchingPrivateDeletedTile;
northLimit: REF Tile = NEW[Tile _ [pos: nwLimitCoord, value: guard]];
northBuffer: REF Tile = NEW[Tile _ [pos: [emptyRect.x1, emptyRect.y2], value: guard]];
southLimit: REF Tile = NEW[Tile _ [pos: swLimitCoord, value: guard]];
eastLimit: REF Tile = NEW[Tile _ [pos: seLimitCoord, value: guard]];
westLimit: REF Tile = NEW[Tile _ [pos: swLimitCoord, value: guard]];

InitTesselationBorderTiles: PROCEDURE =
BEGIN
northLimit.ne _ RtoP[eastLimit];
eastLimit.en _ northLimit;
southLimit.en _ eastLimit;
southLimit.ne _ RtoP[eastLimit];
eastLimit.ws _ RtoP[southLimit];
eastLimit.sw _ southLimit;
westLimit.ne _ RtoP[northLimit];
westLimit.en _ northLimit;
northLimit.sw _ westLimit;
northLimit.ws _ RtoP[westLimit];
southLimit.sw _ westLimit;
westLimit.ws _ RtoP[southLimit];
northBuffer.en _ northLimit;
northBuffer.ne _ RtoP[eastLimit];
northBuffer.sw _ westLimit;
northBuffer.ws _ NIL;
END;

Disguise: TYPE = RECORD [
hiddenValue: REF ANY
];

disposedTiles: REF Tile _ NIL;
disguiseCache: REF Disguise _ NIL;

DumpCache: PUBLIC ENTRY PROCEDURE =
BEGIN
ENABLE UNWIND => NULL;
IF disposedTiles#NIL THEN {
lag: REF Tile _ disposedTiles;
FOR tc: REF Tile _ disposedTiles.en, tc.en WHILE tc#NIL DO
lag.en _ NIL;
lag _ tc
ENDLOOP;
disposedTiles _ NIL
};
IF disguiseCache#NIL THEN {
lag: REF Disguise _ disguiseCache;
FOR dc: REF Disguise _ NARROW[disguiseCache.hiddenValue], NARROW[dc.hiddenValue] WHILE dc # NIL DO
lag.hiddenValue _ NIL;
lag _ dc
ENDLOOP;
disguiseCache _ NIL
};
END;

NewTile: ENTRY PROCEDURE RETURNS [tile: REF Tile] =
BEGIN
ENABLE UNWIND => NULL;
IF disposedTiles#NIL THEN {
tile _ disposedTiles;
disposedTiles _ disposedTiles.en;
}
ELSE tile _ NEW[Tile];
END;

DisposeTile: ENTRY PROCEDURE [tile: REF Tile] = 
BEGIN
ENABLE UNWIND => NULL;
tile.sw _ NIL;  -- Prevent potential circular chains in the disposed cache.
tile.ne _ tile.ws _ NIL;
tile.value _ deleted;
tile.en _ disposedTiles;
disposedTiles _ tile;
END;

NewDisguise: ENTRY PROCEDURE [hiddenValue: REF_NIL] RETURNS [disguise: REF Disguise] =
BEGIN
ENABLE UNWIND => NULL;
IF disguiseCache#NIL THEN {
disguise _ disguiseCache;
disguiseCache _ NARROW[disguiseCache.hiddenValue];
}
ELSE disguise _ NEW[Disguise];
disguise.hiddenValue _ hiddenValue;
END;

DisposeDisguise: ENTRY PROCEDURE [disguise: REF Disguise] =
BEGIN
ENABLE UNWIND => NULL;
disguise.hiddenValue _ disguiseCache;
disguiseCache _ disguise;
END;

NewTesselation: PUBLIC PROCEDURE [data: REF_NIL, stopFlag: REF BOOL_NIL] 
RETURNS [REF Tesselation] =
BEGIN
eastSpace: REF Tile = NewTile[];
centreSpace: REF Tile = NewTile[];
IF stopFlag=NIL THEN stopFlag _ NEW[BOOL_FALSE];
eastSpace^ _ [
en: northBuffer, ne: RtoP[eastLimit], sw: centreSpace, ws: RtoP[southLimit],
pos: [emptyRect.x2, emptyRect.y1], 
value: guard
];
centreSpace^ _ [
en: northBuffer, ne: RtoP[eastSpace], sw: westLimit, ws: RtoP[southLimit], 
pos: [emptyRect.x1, emptyRect.y1], 
value: NIL
];
RETURN [NEW[Tesselation _ [southEast: eastSpace, current: centreSpace, data: data, stopFlag: stopFlag]]]
END;

FreeTesselation: PUBLIC PROCEDURE [plane: REF Tesselation, freeCache: BOOLEAN _ TRUE] =
BEGIN

CacheIt: CornerStitching.PerTileProc = 
BEGIN
DisposeTile[tile];
END;

[] _ EnumerateArea[plane, [x1~Number.FIRST/2, y1~Number.FIRST/2, x2~Number.LAST/2, y2~Number.LAST/2], CacheIt, NIL, deleted];
plane.current _ plane.southEast _ NIL;
IF freeCache THEN
DumpCache[];
plane.tilesInTesselationCount _ 0
END;

ChangeRect: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, newValue: REF ANY _ NIL] =
BEGIN

SplitEWRunningBorder: PROCEDURE [StartTile: REF Tile, splitLine, lineEndpoint: Number] = 
INLINE BEGIN
boundaryRider: REF Tile _ StartTile;
WHILE WEdge[boundaryRider]<lineEndpoint DO
WHILE SEdge[boundaryRider]>splitLine DO 
boundaryRider _ PtoR[boundaryRider.ws] 
ENDLOOP;
IF SEdge[boundaryRider]<splitLine AND (boundaryRider.value#newValue OR EEdge[boundaryRider]<lineEndpoint) THEN 
boundaryRider _ NSSplit[ plane, boundaryRider, splitLine];
boundaryRider _ PtoR[boundaryRider.ne]
ENDLOOP;
END;

tile: REF Tile _ FindTileContainingPoint[plane.current, rect.x1, rect.y2];
plane.current _ tile;
SplitEWRunningBorder[tile, rect.y2, rect.x2]; --north border
SplitEWRunningBorder[FindTileContainingPoint[plane.current, rect.x1, rect.y1],
rect.y1, rect.x2]; --south border
tile _ FindTileContainingPoint[plane.current, rect.x1, rect.y2-1];
DO
IF tile.value # newValue AND WEdge[tile] < rect.x1 THEN {
outsideTile: REF Tile;
tile _ EWSplit[plane, tile, rect.x1];
outsideTile _ tile.sw;
IF outsideTile.value=outsideTile.en.value AND WEdge[outsideTile]=WEdge[outsideTile.en] AND EEdge[outsideTile]=EEdge[outsideTile.en] THEN
outsideTile _ NSMerge[plane, outsideTile, outsideTile.en];
IF outsideTile.value=PtoR[outsideTile.ws].value AND WEdge[outsideTile]=WEdge[PtoR[outsideTile.ws]] AND EEdge[outsideTile]=EEdge[PtoR[outsideTile.ws]] THEN
outsideTile _ NSMerge[plane, PtoR[outsideTile.ws], outsideTile]
};
DO
IF tile.value#newValue THEN {
IF EEdge[tile]>rect.x2 THEN {
outsideTile: REF Tile;
outsideTile _ EWSplit[plane, tile, rect.x2];
IF outsideTile.value=outsideTile.en.value AND WEdge[outsideTile]=WEdge[outsideTile.en] AND EEdge[outsideTile] = EEdge[outsideTile.en] THEN
outsideTile _ NSMerge[plane, outsideTile, outsideTile.en];
IF outsideTile.value=PtoR[outsideTile.ws].value AND WEdge[outsideTile]=WEdge[PtoR[outsideTile.ws]] AND EEdge[outsideTile]=EEdge[PtoR[outsideTile.ws]] THEN
outsideTile _ NSMerge[plane, PtoR[outsideTile.ws], outsideTile]
};
tile _ ChangeTile[plane, tile, newValue]
};
IF EEdge[tile]>=rect.x2 THEN EXIT;
tile _ PtoR[tile.ne];
WHILE SEdge[tile]>=rect.y2 DO 
tile _ PtoR[tile.ws] 
ENDLOOP; -- EMM
ENDLOOP;
IF WEdge[tile]>rect.x1 THEN ERROR;
IF SEdge[tile]<=rect.y1 THEN EXIT;
tile _ PtoR[tile.ws];
WHILE EEdge[tile]<=rect.x1 DO 
tile _ PtoR[tile.ne] 
ENDLOOP
ENDLOOP
END;

FuncChangeRect: PUBLIC PROCEDURE [plane: REF Tesselation, 
rect: Rect, 
perTile: CornerStitching.PerTileChangeProc, 
data: REF ANY _ NIL] =
BEGIN

DisguiseTile: CornerStitching.PerTileProc =
 -- [tile: REF Tile, data: REF ANY] RETURNS [REF ANY]   
BEGIN
tile.value _ NewDisguise[tile.value];
END;

ApplyFuncToTile: CornerStitching.PerTileProc =
BEGIN
disguise: REF Disguise = NARROW[tile.value];
clippedBB: Rect = [
MAX[WEdge[tile], rect.x1], 
MAX[SEdge[tile], rect.y1], 
MIN[EEdge[tile], rect.x2], 
MIN[NEdge[tile], rect.y2]
]; -- Clip tile against Enumeration's bounding box
[] _ ChangeTile[plane: plane, tile: tile, newValue: disguise.hiddenValue];
perTile[plane: plane, rect: clippedBB, oldValue: disguise.hiddenValue, data: data];
DisposeDisguise[disguise];
END;
[] _ EnumerateArea[plane, rect, DisguiseTile, NIL, deleted];
[] _ EnumerateArea[plane, rect, ApplyFuncToTile, data, deleted];
END;

ChangeTile: PROCEDURE [plane: REF Tesselation, tile: REF Tile, newValue: REF ANY _ NIL] RETURNS [REF Tile] =
BEGIN
north: Number = NEdge[tile];
east: Number = EEdge[tile];
south: Number = SEdge[tile];
west: Number = WEdge[tile];
tWest, tEast, tNorth: REF Tile;
tile.value _ newValue;  
-- Give tile newValue, then restore maximal East-West strip property
tEast _ PtoR[tile.ne];
IF tEast.value=newValue AND NEdge[tEast]>north THEN [] _ NSSplit[plane, tEast, north];
tWest _ tile.en;
WHILE WEdge[tWest]>=west DO 
tWest _ tWest.sw 
ENDLOOP;
IF tWest.value=newValue AND SEdge[tWest]<north THEN [] _ NSSplit[plane, tWest, north];
tWest _ tile.sw;
IF tWest.value=newValue AND SEdge[tWest]<south THEN [] _ NSSplit[plane, tWest, south];
tEast _ PtoR[tile.ws];
WHILE EEdge[tEast]<=east DO 
tEast _ PtoR[tEast.ne] 
ENDLOOP;
IF tEast.value=newValue AND NEdge[tEast]>south THEN [] _ NSSplit[plane, tEast, south];
tWest _ tile.sw;
WHILE NEdge[tWest]<north DO
IF tWest.value#newValue AND tWest.en.value#newValue THEN tWest _ tWest.en
ELSE {
tile _ NSSplit[plane, tile, NEdge[tWest]];
IF tWest.value=newValue THEN [] _ EWMerge[plane, tWest, PtoR[tWest.ne]];
tWest _ tile.sw;
}
ENDLOOP;
IF tWest.value=newValue THEN tile _ EWMerge[plane, tWest, tile];
tEast _ PtoR[tile.ne];
WHILE SEdge[tEast]>south DO
tile _ tEast.sw;
IF (tEast.value=newValue OR PtoR[tEast.ws].value=newValue) AND SEdge[tile]<SEdge[tEast] THEN
[] _ NSSplit[plane, tile, SEdge[tEast]];
tEast _ PtoR[tEast.ws]
ENDLOOP;
tNorth _ tEast.sw;
WHILE NEdge[tNorth]<=south DO
tNorth _ tNorth.en;
ENDLOOP;
DO
tile _ tNorth;
tNorth _ tNorth.en;
IF PtoR[tile.ne].value=newValue THEN {
IF tile.ne=tNorth.ne THEN [] _ NSSplit[plane, PtoR[tile.ne], NEdge[tile]];
tile _ EWMerge[plane, tile, PtoR[tile.ne]]
};
IF tile.value=PtoR[tile.ws].value AND WEdge[tile]=WEdge[PtoR[tile.ws]] AND EEdge[tile]=EEdge[PtoR[tile.ws]] THEN
tile _ NSMerge[plane, PtoR[tile.ws], tile];
IF NEdge[tNorth]>north THEN EXIT
ENDLOOP;
IF tile.value=tNorth.value AND WEdge[tile]=WEdge[tNorth] AND EEdge[tile]=EEdge[tNorth] THEN
[] _ NSMerge[plane, tile, tNorth];
RETURN [tile]
END;

AreaEmpty: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, backgroundValue: REF ANY _ NIL] RETURNS [BOOLEAN] =
BEGIN
plane.current _ FindTileContainingPoint[plane.current, rect.x1, rect.y1];
FOR tile: REF Tile _ plane.current, TileAbove[tile, rect.x1] WHILE SEdge[tile]<rect.y2 DO
IF tile.value#backgroundValue OR EEdge[tile]<rect.x2 THEN RETURN [FALSE]
ENDLOOP;
RETURN [TRUE]
END;

ContentsBound: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, backgroundValue: REF ANY _ NIL] RETURNS [bBox: Rect] =
BEGIN
tile: REF Tile;
bBox _ [x1~Number.LAST, y1~Number.LAST,  x2~Number.FIRST, y2~Number.FIRST];
IF rect.x1=rect.x2 THEN ERROR DegenerateTile;
plane.current _ FindTileContainingPoint[plane.current, rect.x1, rect.y1];
FOR tile _ plane.current, TileAbove[tile, rect.x1] DO
IF SEdge[tile]>=rect.y2 THEN RETURN;  -- Tile is empty
IF tile.value#backgroundValue OR EEdge[tile]<rect.x2 THEN EXIT
ENDLOOP;
bBox.y1 _ MAX[SEdge[tile], rect.y1];
WHILE SEdge[tile]<rect.y2 DO
IF tile.value#backgroundValue THEN { 
bBox.x1 _ rect.x1; 
EXIT
};
IF EEdge[tile]<rect.x2 AND EEdge[tile]<bBox.x1 THEN bBox.x1 _ EEdge[tile];
tile _ TileAbove[tile, rect.x1];
ENDLOOP;
tile _ FindTileContainingPoint[plane.current, rect.x2-1, rect.y1];
WHILE SEdge[tile]<rect.y2 DO
IF tile.value#backgroundValue THEN {
bBox.x2 _ rect.x2;
bBox.y2 _ NEdge[tile]
}
ELSE IF WEdge[tile]>rect.x1 THEN {
IF WEdge[tile]>bBox.x2 THEN bBox.x2 _ WEdge[tile];
bBox.y2 _ NEdge[tile]
};
tile _ TileAbove[tile, rect.x2-1];
ENDLOOP;
END;

EnumerateArea: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, perTile: CornerStitching.PerTileProc _ NIL, data: REF ANY _ NIL, backgroundValue: REF ANY _ NIL] RETURNS [REF ANY] =
BEGIN

IsChildOf: PROCEDURE [ me: REF Tile, you: REF Tile] RETURNS [BOOLEAN] = INLINE {
RETURN [you.sw=me AND SEdge[you]>rect.y1];
};

IsBrotherOf: PROCEDURE [ me: REF Tile, you: REF Tile] RETURNS [BOOLEAN] = INLINE {
RETURN [me.sw=you.sw AND SEdge[you]>rect.y1];
};

tileEnumeration: LIST OF REF CornerStitching.Region _ NIL;
tile: REF Tile _ FindTileContainingPoint[plane.current, rect.x1, rect.y2];
doneSouthEastTile: BOOLEAN _ FALSE;
IF SEdge[tile]=rect.y2 AND SEdge[tile]>rect.y1 THEN {
tile _ PtoR[tile.ws];
WHILE EEdge[tile]<=rect.x1 DO
tile _ PtoR[tile.ne]
ENDLOOP;
};
plane.current _ tile;
WHILE ~doneSouthEastTile DO
seeking: {youth, experience, nothing} _ youth;
DO
prevT: REF Tile;
IF seeking=youth THEN {
child: REF Tile _ PtoR[tile.ne];
WHILE SEdge[child]>=rect.y2 DO 
child _ PtoR[child.ws] 
ENDLOOP;
IF IsChildOf[tile, child] AND WEdge[child]<rect.x2 THEN {
tile _ child;
LOOP
}
ELSE seeking _ experience
};
prevT _ tile;
IF WEdge[tile]<=rect.x1 OR SEdge[tile]<=rect.y1 THEN {
seeking _ nothing;
IF SEdge[tile]>rect.y1 THEN {
tile _ PtoR[tile.ws];
WHILE EEdge[tile]<=rect.x1 DO 
tile _ PtoR[tile.ne] 
ENDLOOP
}
ELSE {
IF EEdge[tile]>=rect.x2 THEN doneSouthEastTile _ TRUE
ELSE {
tile _ PtoR[tile.ne];
WHILE SEdge[tile]>rect.y1 DO
tile _ PtoR[tile.ws]
ENDLOOP;
}
}
}
ELSE {
IF IsBrotherOf[tile, PtoR[tile.ws]] THEN {
tile _ PtoR[tile.ws];
seeking _ youth
}
ELSE tile _ tile.sw;
};
IF prevT.value#backgroundValue THEN {
IF perTile#NIL THEN perTile[prevT, data]
ELSE tileEnumeration _ CONS[NEW[ CornerStitching.Region _ [
[ MAX[WEdge[prevT], rect.x1], MAX[SEdge[prevT], rect.y1],  MIN[EEdge[prevT], rect.x2], MIN[NEdge[prevT], rect.y2]],
prevT.value] ], tileEnumeration];
};
IF seeking=nothing THEN EXIT
ENDLOOP
ENDLOOP;
IF perTile=NIL THEN data _ tileEnumeration;
RETURN [data]
END;

TileAbove: PROCEDURE [tile: REF Tile, x: Number] RETURNS [REF Tile] =
BEGIN
IF WEdge[tile]>x OR EEdge[tile]<=x THEN ERROR;
tile _ tile.en;
WHILE WEdge[tile]>x DO
tile _ tile.sw;
ENDLOOP;
RETURN [tile]
END;

lastm1: Number = Number.LAST-2;

TileAt: PUBLIC PROCEDURE [plane: REF Tesselation, pos: Coord] RETURNS [tile: REF Tile] =
BEGIN
tile _ FindTileContainingPoint[plane.current, MIN[lastm1, pos.x], MIN[lastm1, pos.y]];
IF tile=northBuffer THEN ERROR;
plane.current _ tile;
END;

FindTileContainingPoint: PROCEDURE [tile: REF Tile, x, y: Number] RETURNS [REF Tile] =
TRUSTED BEGIN
IF tile.value=deleted THEN ERROR TileDeleted;
DO
--south-- WHILE y<tile.pos.y DO tile _ LOOPHOLE[tile.ws] ENDLOOP;
--north-- WHILE y>=tile.en.pos.y DO tile _ tile.en ENDLOOP;
IF x<tile.pos.x THEN --west-- 
WHILE x<tile.pos.x DO tile _ tile.sw ENDLOOP
ELSE IF x>=tile.ne.pos.x THEN --east--
WHILE x>=tile.ne.pos.x DO tile _ LOOPHOLE[tile.ne] ENDLOOP
ELSE EXIT
ENDLOOP;
RETURN [tile]
END;

EWSplit: PROCEDURE [plane: REF Tesselation, tile: REF Tile, x: Number] RETURNS [REF Tile] =
BEGIN
eastTile: REF Tile _ NewTile[];
t: REF Tile;
IF WEdge[tile]>=x OR EEdge[tile]<= x THEN ERROR;
eastTile^ _ tile^;
plane.tilesInTesselationCount _ plane.tilesInTesselationCount + 1;
tile.ne _ RtoP[eastTile];
eastTile.sw _ tile;
eastTile.pos.x _ x;
t _ eastTile.en;
WHILE t.pos.x>=x DO  
t.ws _ RtoP[eastTile]; 
t _ t.sw
ENDLOOP;
tile.en _ t;
t _ PtoR[eastTile.ne];
WHILE t.sw=tile DO  
t.sw _ eastTile; 
t _ PtoR[t.ws]  
ENDLOOP;
t _ PtoR[tile.ws];
WHILE PtoR[t.ne].pos.x<=x DO  
t _ PtoR[t.ne]  
ENDLOOP;
eastTile.ws _ RtoP[t];
WHILE t.en=tile DO  
t.en _ eastTile; 
t _ PtoR[t.ne]  
ENDLOOP;
RETURN [eastTile]
END;

NSSplit: PROCEDURE [plane: REF Tesselation, tile: REF Tile, y: Number] RETURNS [REF Tile] =
BEGIN
northTile: REF Tile _ NewTile[];
t: REF Tile;
IF SEdge[tile]>=y OR NEdge[tile]<=y THEN ERROR;
northTile^ _ tile^;
plane.tilesInTesselationCount _ plane.tilesInTesselationCount + 1;
tile.en _ northTile;
northTile.ws _ RtoP[tile];
northTile.pos.y _ y;
t _ PtoR[northTile.ne];
WHILE t.pos.y>=y DO  
t.sw _ northTile; 
t _ PtoR[t.ws]  
ENDLOOP;
tile.ne _ RtoP[t];
t _ northTile.en;
WHILE t.ws=RtoP[tile] DO  
t.ws _ RtoP[northTile]; 
t _ t.sw  
ENDLOOP;
t _ tile.sw;
WHILE t.en.pos.y<=y DO  
t _ t.en  
ENDLOOP;
northTile.sw _ t;
WHILE PtoR[t.ne]=tile DO  
t.ne _ RtoP[northTile]; 
t _ t.en  
ENDLOOP;
RETURN [northTile]
END;

EWMerge: PROCEDURE [plane: REF Tesselation, tileW, tileE: REF Tile] RETURNS [REF Tile] =
BEGIN
IF tileE.sw#tileW OR PtoR[tileW.ne]#tileE OR tileW.pos.y#tileE.pos.y OR tileW.en.pos.y#tileE.en.pos.y OR tileW.value#tileE.value THEN ERROR;
tileW.en _ tileE.en;
tileW.ne _ tileE.ne;
FOR t: REF Tile _ tileW.en, t.sw WHILE PtoR[t.ws]=tileE DO
t.ws _ RtoP[tileW];
ENDLOOP;
FOR t: REF Tile _ PtoR[tileW.ne], PtoR[t.ws] WHILE t.sw=tileE DO
t.sw _ tileW;
ENDLOOP;
FOR t: REF Tile _ PtoR[tileE.ws], PtoR[t.ne] WHILE t.en=tileE DO
t.en _ tileW;
ENDLOOP;
tileE.value _ deleted;
tileE.en _ NIL;
IF plane.current=tileE THEN plane.current _ tileW;
DisposeTile[tileE];
plane.tilesInTesselationCount _ plane.tilesInTesselationCount - 1;
RETURN [tileW];
END;

NSMerge: PROCEDURE [plane: REF Tesselation, tileS, tileN: REF Tile] RETURNS [REF Tile] = 
BEGIN
IF PtoR[tileN.ws]#tileS OR tileS.en#tileN OR tileS.pos.x#tileN.pos.x OR PtoR[tileS.ne].pos.x#PtoR[tileN.ne].pos.x OR tileS.value#tileN.value THEN ERROR;
tileS.ne _ tileN.ne;
tileS.en _ tileN.en;
FOR t: REF Tile _ PtoR[tileS.ne], PtoR[t.ws] WHILE t.sw=tileN DO
t.sw _ tileS;
ENDLOOP;
FOR t: REF Tile _ tileS.en, t.sw WHILE PtoR[t.ws]=tileN DO
t.ws _ RtoP[tileS];
ENDLOOP;
FOR t: REF Tile _ tileN.sw, t.en WHILE PtoR[t.ne]=tileN DO
t.ne _ RtoP[tileS];
ENDLOOP;
tileN.value _ deleted;
tileN.en _ NIL;
IF plane.current=tileN THEN plane.current _ tileS;
DisposeTile[tileN];
plane.tilesInTesselationCount _ plane.tilesInTesselationCount - 1;
RETURN [tileS];
END;

PtoR: PROCEDURE [p: LONG POINTER TO Tile] RETURNS [REF Tile] ~ INLINE {
TRUSTED { RETURN [LOOPHOLE[p]] }
};
RtoP: PROCEDURE [r: REF Tile] RETURNS [LONG POINTER TO Tile] ~ INLINE {
TRUSTED { RETURN [LOOPHOLE[r]] }
};

InitTesselationBorderTiles[]
END.


†CornerStitchingImpl.mesa
Copyright c 1983, 1985 by Xerox Corporation.  All rights reserved.
Written by Shand, September 12, 1983 11:40 pm PDT
Last Edited by: McCreight, November 28, 1983 5:53 pm
Last Edited by: Jacobi, February 23, 1984 3:59 pm
Last Edited by: Shand, August 6, 1984 4:16:51 am PDT
Last Edited by: Jacobi, April 11, 1985 3:03:55 pm PST
Last Edited by: Beretta, February 13, 1985 11:46:26 am PST

-- Error Codes

-- Co-ordinates at "infinity"

-- House-keeping tile values to flag deleted tiles and tiles at "infinity"

-- Border Tiles (shared by all tesselations)
-- The stitching is not quite Kosher at Guard corners.
-- Think of the guard tile as having bevelled ends.  
-- which fit together like a picture-frame and are stitched accordingly.
-- North-East
-- South-East
-- North-West
-- South-West
-- northBuffer
--and cache the tile, this is faster than going through the garbage collector
[tile: REF Tile, data: REF ANY] RETURNS [REF ANY] --  
-- Depends on fact that Enumeration proceeds NE to SW, so en ref may be clobbered by caching process.
When freeing the tile cache as well as the tesselation, the tesselation's tiles are first added to the cache, and then the cache is dumped.  This is to help the Garbage Collector (by NILing all REFs).
-- The second clause here is necessary to avoid splitting tiles which will never be repaired by changeTile, and will thus not be made maximal north-south.  Its kind of subtle, and probably more than a little ugly, but I can probably prove its correct if pressed.
-- This tile straddles the border, chop chop.
-- tile contains nw corner (sort of!)
-- Now  we start gobbling up all the tiles into wide flat bands of newValue.
-- First get our western border tile into shape.
-- Better make sure we keep outside tile in order NS-wise.
--[tile: REF Tile, data: REF ANY] RETURNS [REF ANY]   
-- Restore tile value
-- Call user perTile function

--FuncChangeRect
-- Returns the northernmost tile in the changed region.  (There is only one such tile by the maximal-EW-property)
-- First we tidy up any newValue tiles that abut any of the tile's four corners, 
-- but extend beyond the corner in a North-South direction
-- Now we are at the tile whose east EEdge is >= west but whose WEdge is < west.  
-- In fact SEdge[tWest] < north will only hold if EEdge = west
-- Analogous to split of NW corner.
-- Now we convert the West and East adjacent tiles to maximal East-West strips
-- First run South to North along the West edge splitting North-South, and merging East-West the newValue tile created from the tile being changed.
-- tile is the northernmost strip in the changed area.
-- Now any maximal-EW-property violations of tile are confined to its Eastern border.  
-- There may however still be some pending merges at the northern and southern borders.
-- Run North to South along the East edge splitting North-South any newValue tile to 
-- the East which abuts more than one newValue tile in the changed area.
-- Then run South to North along the East edge splitting North-South, 
-- and merging East-West the newValue tiles created from the tile being changed.
-- Return TRUE if all tiles in area are of value backgroundValue, else FALSE.  
-- Relies on the Maximal East-West strip property.
-- ContentsBound returns a minimal bounding box for non-backgroundValue 
-- tiles in rect.  
-- Relies on the Maximal East-West strip property.
-- else the east edge of tile must abut a non-backgroundValue tile (by the Maximal East-West strip property)
-- Note FindTileContainingPoint is assymetric so code is different here!  
-- (This is the cause of the ugly .PREDs)
-- Uses the tiles own links to maintain an implicit stack of tiles.  
-- Enumeration proceeds in a manner which ensures that a tiles ne and en 
-- pointers will never be needed once that tile has appeared in the enumeration; 
-- this fact is exploited in FreeTesselation.
-- Defn:	b is a's child iff b.sw = a.
-- correct for one off error when rect.y2 lies at tile boundary (YUK)
-- Is tile a border tile?
-- Find next border tile, i.e. next tree root
-- Assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)
--a-symmetric
-- The East one will be the new one.
-- eastTile starts out a replica of tile
-- Fix the tiles relative to each other.
-- Fix North boundary
-- Fix East boundary
-- Fix South boundary
-- The North one will be the new one.
-- northTile starts out a replica of tile
-- Fix the tiles relative to each other.
-- Fix East boundary
-- Fix North boundary
-- Fix West boundary
-- The East tile will be deallocated.
-- The caller must assure that tileW.value=tileE.value and that the tiles really
-- do have a common border of equal length.
--checks
-- Fix the tiles relative to each other.
-- Fix North boundary
-- Fix East boundary
-- Fix South boundary
-- The North tile will be deallocated.
-- The caller must assure that tileS.value=tileN.value and that the tiles really
-- do have a common border of equal length.
--checks
-- Fix the tiles relative to each other.
-- Fix East boundary
-- Fix North boundary
-- Fix West boundary
Edited on February 8, 1985 4:40:46 pm PST, by Jacobi
Formatting

Edited on February 8, 1985 4:40:46 pm PST, by Jacobi
FindTileContainingPoint rewritten

�ÊᘙJšœ
Ïm
œ7™BJš
œ1™1J™4J™1J™4J™5J™:—J˜š
Ïk	˜	Jš
œ˜—šÏbœžœ
ž˜"Jšžœ˜—Jš
ž˜J˜Jšœ
žœ˜0Jšœžœ˜"Jšœžœ˜&Jšœžœ˜$Jšœžœ˜"J˜JšÏnœž	œžœžœžœžœ˜OJš œž	œžœžœžœžœ˜UJš œž	œžœžœžœžœ˜LJš œž	œžœžœžœžœ˜LJ™™Jšœžœ
žœžœ
˜Jšœ
žœ
žœžœ
˜!Jšœžœžœ
˜—J™™Jšœ!žœžœ˜7Jšœ!žœžœ˜8Jšœ!žœžœ˜9Jšœ!žœžœ˜8Jš	œžœžœ
žœžœ˜_—J™™JJšœžœ
žœ$˜2Jšœ	žœ
žœ&˜6—J™™,Jšœžœžœ+˜EJšœ
žœžœ;˜VJšœžœžœ+˜EJšœžœžœ+˜DJšœžœžœ+˜D—J˜š œž	œ˜'Jš
ž˜J™6J™5J™H™
Jš
œ ˜ Jš
œ˜—™
Jš
œ˜Jš
œ ˜ Jš
œ ˜ Jš
œ˜—™
Jš
œ ˜ Jš
œ˜Jš
œ˜Jš
œ ˜ —™
Jš
œ˜Jš
œ ˜ —š
œ™Jš
œ˜Jš
œ!˜!Jš
œ˜Jšœžœ
˜—Jšžœ
˜—J˜šœ
žœžœ˜Jšœ
žœ
ž˜J˜J˜—Jšœžœžœ
˜Jšœžœžœ
˜"J˜š 	œžœ
žœ
ž	œ˜#Jš
ž˜Jšžœ
žœžœ
˜šžœžœ
žœ˜Jšœžœ˜š	žœžœ žœžœ
ž˜:Jšœ	žœ
˜
J˜Jšžœ
˜—Jšœž˜J˜—šžœžœ
žœ˜Jšœžœ˜"š
žœžœžœžœžœžœ
ž˜bJšœžœ
˜J˜Jšžœ
˜—Jšœž˜J˜—Jšžœ
˜—J˜š
 œžœ
ž	œ
žœžœ˜3Jš
ž˜Jšžœ
žœžœ
˜šžœžœ
žœ˜Jš
œ˜Jš
œ!˜!J˜
—Jšžœžœ˜Jšžœ
˜—J˜š œžœ
ž	œžœ	˜0Jš
œM™MJš
ž˜Jšžœ
žœžœ
˜Jšœ
žœÏc;˜KJšœžœ
˜Jš
œ˜Jš
œ˜Jš
œ˜Jšžœ
˜—J˜š œžœ
ž	œžœžœžœ˜VJš
ž˜Jšžœ
žœžœ
˜šžœžœ
žœ˜Jš
œ˜Jšœžœ˜2J˜
—Jšžœžœ˜Jš
œ#˜#Jšžœ
˜—J˜š œžœ
ž	œžœ˜;Jš
ž˜Jšžœ
žœžœ
˜Jš
œ%˜%Jš
œ˜Jšžœ
˜—J˜š œžœ
ž	œžœ
žœžœ
žœ
žœ˜IJšžœžœ˜Jš
ž˜Jšœžœ˜ Jšœ
žœ˜"Jšžœ
žœ
žœžœ
žœ
žœ˜0š
œ˜Jš
œL˜LJš
œ#˜#Jš
œ˜Jš
œ˜—š
œ˜Jš
œK˜KJš
œ#˜#Jšœž˜
Jš
œ˜—Jšžœžœ]˜hJšžœ
˜—J˜š œžœ
ž	œ	žœžœžœ˜WJš
ž˜J•StartOfExpansionH -- [tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY] -- ˜šŸœ ˜'Jš
œ6™6Jš
œe™eJš
ž˜Jš
œ˜Jšžœ
˜—J˜J™È
Jšœ%žœžœžœžœžœ˜}Jšœ"žœ
˜&šžœž˜Jš
œ˜—Jš
œ!˜!Jšžœ
˜—J˜š 
œžœ
ž	œ	žœ$žœ
žœžœ˜\Jš
ž˜J˜š œž	œ
žœ*˜YJšžœ
ž˜Jšœžœ˜$šžœ#ž˜*šžœ žœ
˜(Jš
œ'˜'Jšžœ
˜—J™†šžœ žœžœ$žœ
˜oJš
œ-™-Jš
œ:˜:—Jš
œ&˜&Jšžœ
˜—Jšžœ
˜—J˜JšœžœA˜JJ™%Jš
œ˜Jšœ.¡˜<Jšœb¡˜pJš
œL™LJš
œB˜BJš
œ0™0š
ž˜šžœžœžœ˜9Jšœ
žœ˜Jš
œ%˜%Jš
œ˜J™:šžœ(žœ*žœ*ž˜ˆ
Jš
œ:˜:—šžœ.žœ0žœ0ž˜š
Jš
œ?˜?—J˜—š
ž˜šžœžœ˜šžœžœ˜Jšœ
žœ˜Jš
œ,˜,šžœ(žœ*žœ,ž˜Š
Jš
œ:˜:—šžœ.žœ0žœ0ž˜š
Jš
œ?˜?—J˜—Jš
œ(˜(J˜—Jšžœžœ
žœ
˜"Jš
œ˜šžœžœ
˜Jš
œ˜Jšžœ¡˜—Jšžœ
˜—Jšžœžœ
žœ
˜"Jšžœžœ
žœ
˜"Jš
œ˜šžœžœ
˜Jš
œ˜Jš
ž˜—Jš
ž˜—Jšžœ
˜—J˜š œžœ
ž	œ	žœ˜:Jš
œ˜Jš
œ,˜,Jšœžœ
žœžœ˜Jš
ž˜J–H -- [tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY] -- ˜šŸœ˜+Jšœ
¡5œ˜8Jš
ž˜Jš
œ%˜%Jšžœ
˜—J–H -- [tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY] -- ˜šŸœ˜.Jš
œ6™6Jš
ž˜Jšœ
žœžœ
˜,š
œ˜Jšžœ˜Jšžœ˜Jšžœ˜Jšžœ˜Jšœ¡/˜2—J™Jš
œJ˜JJ™Jš
œS˜SJš
œ˜Jšžœ
˜—J™Jš
œ™Jšœ.žœ˜<Jš
œ@˜@Jšžœ
˜—J˜š 
œž	œ	žœžœžœ
žœžœžœžœ˜lJ™qJ˜J˜J˜J˜J˜Jšœžœ˜Jš
œ˜Jš
¡D˜DJš
œQ™QJš
œ:™:Jš
œ˜Jšžœžœžœ#˜VJ˜šžœžœ
˜Jš
œ˜Jšžœ
˜—Jš
œR™RJš
œ>™>Jšžœžœžœ#˜VJš
œ˜Jšžœžœžœ#˜VJš
œ˜šžœžœ
˜Jš
œ˜Jšžœ
˜—J™#Jšžœžœžœ#˜VJ™NJš
œ“
™“
J˜šžœž˜Jšžœžœžœ˜Išžœ˜Jš
œ*˜*Jšžœžœ,˜HJ˜J˜
—Jšžœ
˜—Jš
œ6™6Jšžœžœ$˜@Jš
œW™WJš
œW™WJš
œU™UJš
œH™HJš
œ˜šžœž˜J˜šžœžœ žœž˜\Jš
œ(˜(—Jš
œ˜Jšžœ
˜—Jš
œF™FJš
œP™PJš
œ˜šžœž˜Jš
œ˜Jšžœ
˜—š
ž˜J˜Jš
œ˜šžœžœ˜&Jšžœžœ1˜JJš
œ*˜*J˜—šžœ žœ"žœ"ž˜pJš
œ+˜+—Jšžœžœ
ž˜ Jšžœ
˜—šžœžœžœž˜[J˜"—Jšžœ˜
Jš
œ˜—J˜š 	œžœ
ž	œ	žœ+žœ
žœžœžœžœ˜tJš¡
Ðck¡9¢œ™OJš
œ2™2Jš
ž˜Jš
œI˜Išžœžœ0žœž˜YJš
žœžœžœ
žœžœ
˜HJšžœ
˜—Jšžœžœ
˜
Jšžœ
˜—J˜š 
œžœ
ž	œ	žœ+žœ
žœžœžœ˜{Jš
œH™HJš
œ™Jš
œ2™2Jš
ž˜Jšœžœ˜Jš	œžœžœ
žœžœ˜KJšžœžœ
žœ˜-Jš
œI˜Išžœ0ž˜5Jšžœžœ
žœ¡˜6Jšžœžœžœ
ž˜>Jšžœ
˜—Jšœ
žœ˜$šžœž˜šžœžœ˜%Jš
œ˜Jš
ž˜Jš
œ˜—Jš
œl™lJšžœžœžœ˜JJš
œ ˜ Jšžœ
˜—Jš
œB˜Bšžœž˜Jš
œJ™JJš
œ)™)šžœžœ˜$Jš
œ˜Jš
œ˜J˜
—šžœ
žœžœ˜"Jšžœžœ˜2Jš
œ˜J˜—Jš
œ"˜"Jšžœ
˜—Jšžœ
˜—J˜š 
œžœ
ž	œ	žœAžœžœ
žœžœžœ
žœžœžœžœ
žœ˜¹
Jš
œE™EJš
œI™IJš
œQ™QJš
œ-™-Jš
œ%™%Jš
ž˜J˜š 	œž	œžœžœžœžœžœ˜PJšžœžœ˜*J˜—J˜š œž	œžœžœžœžœžœ˜RJšžœžœ˜-J˜—J˜Jš	œžœ
žœ
žœžœ
˜:JšœžœA˜JJšœžœžœ
˜#J™Ešžœžœžœ˜5Jš
œ˜šžœž˜Jš
œ˜Jšžœ
˜—J˜—Jš
œ˜šžœž˜J˜.š
ž˜Jšœžœ˜šžœžœ˜Jšœžœ˜ šžœžœ
˜Jš
œ˜Jšžœ
˜—šžœžœžœ˜9Jš
œ
˜
Jš
ž˜J˜
—Jšžœ˜J˜—Jš
œ
˜
J™šžœžœžœ˜6J™-J˜šžœžœ˜Jš
œ˜šžœžœ
˜Jš
œ˜Jš
ž˜—J˜
—šžœ˜Jšžœžœž˜5šžœ˜Jš
œ˜šžœž˜Jš
œ˜Jšžœ
˜—J˜
—J˜
—J˜
—šžœ˜šžœ"žœ˜*Jš
œ˜J˜J˜
—Jšžœ˜J˜—šžœžœ˜%Jšžœ	žœ
žœ˜(Jšžœžœ
žœžœžœžœžœ;˜Ñ
J˜—Jšžœžœ
ž˜Jš
ž˜—Jšžœ
˜—Jšžœ	žœ
žœ˜+Jšžœ˜
Jšžœ
˜—J˜š
 	œž	œžœžœžœ˜EJš
œE™EJš
ž˜Jšžœžœžœ
žœ
˜.J˜šžœž˜J˜Jšžœ
˜—Jšžœ˜
Jšžœ
˜—J˜Jšœžœ˜J˜š œžœ
ž	œ	žœžœžœ˜XJš
ž˜Jšœ.žœžœ˜VJšžœžœ
žœ
˜Jš
œ˜Jšžœ
˜—J˜š
 œž	œžœžœžœ˜VJš
œ
™
Jšžœ
ž˜
Jšžœžœ
žœ
˜-š
ž˜Jš
¡	œ
žœžœžœ
žœ
˜AJš¡	œ
žœžœžœ
˜;šžœž¡œ
˜Jšžœžœž˜,—šžœ
žœžœ
¡˜&Jšžœžœžœ
ž˜:—Jšžœ
ž˜	Jšžœ
˜—Jšžœ˜
Jšžœ
˜—J˜š œž	œ	žœžœžœžœ˜[J™$Jš
ž˜Jšœ
žœ˜Jšœžœ˜Jšžœžœžœ
žœ
˜0Jš
œ(™(Jš
œ˜Jš
œB˜BJ™(Jš
œ˜Jš
œ˜J˜J™Jš
œ˜šžœžœ˜Jš
œ˜Jš
œ˜Jšžœ
˜—J˜J™Jš
œ˜šžœžœ˜Jš
œ˜Jš
œ˜Jšžœ
˜—J™Jš
œ˜šžœžœ˜Jš
œ˜Jšžœ
˜—Jš
œ˜šžœžœ˜Jš
œ˜Jš
œ˜Jšžœ
˜—Jšžœ˜Jšžœ
˜—J˜š œž	œ	žœžœžœžœ˜[J™%Jš
ž˜Jšœžœ˜ Jšœžœ˜Jšžœžœžœ
žœ
˜/Jš
œ)™)Jš
œ˜Jš
œB˜BJ™(J˜J˜J˜J™Jš
œ˜šžœžœ˜Jš
œ˜Jš
œ˜Jšžœ
˜—J˜J™Jš
œ˜šžœžœ˜Jš
œ˜Jš
œ
˜
Jšžœ
˜—J™Jš
œ˜šžœžœ˜Jš
œ
˜
Jšžœ
˜—J˜šžœžœ˜Jš
œ˜Jš
œ
˜
Jšžœ
˜—Jšžœ˜Jšžœ
˜—J˜š œž	œ	žœžœžœžœ˜XJ™%Jš
œP™PJ™+Jš
ž˜Jš
œ™Jšžœžœžœžœžœžœ
žœ
˜Œ
J™(Jš
œ˜Jš
œ˜J™šžœžœžœž˜:Jš
œ˜Jšžœ
˜—J™šžœžœ#žœž˜@Jš
œ
˜
Jšžœ
˜—J™šžœžœ#žœž˜@Jš
œ
˜
Jšžœ
˜—J˜Jšœžœ
˜Jšžœžœ˜2Jš
œ˜Jš
œB˜BJšžœ	˜Jšžœ
˜—J˜š œž	œ	žœžœžœžœ	˜YJ™&Jš
œP™PJ™+Jš
ž˜Jš
œ™Jšžœžœžœžœ+žœžœ
žœ
˜˜
J™(Jš
œ˜J˜J™šžœžœ#žœž˜@Jš
œ
˜
Jšžœ
˜—J™šžœžœžœž˜:Jš
œ˜Jšžœ
˜—J™šžœžœžœž˜:Jš
œ˜Jšžœ
˜—J˜Jšœžœ
˜Jšžœžœ˜2J˜Jš
œB˜BJšžœ	˜Jšžœ
˜—J˜š œž	œžœ
žœ
žœžœžœ	žœ˜GJšžœžœžœ˜ J˜—š œž	œžœžœžœ
žœ
žœ	žœ
˜GJšžœžœžœ˜ J˜—J˜Jš
œ˜Jšžœ
˜J˜™4J™
—J™™4Jš
œ!™!—J™J˜—…—D¤t