DIRECTORY
CornerStitching
;
CornerStitchingImpl: CEDAR PROGRAM
EXPORTS CornerStitching
~ BEGIN
maxnum: CornerStitching.Number = LAST[CornerStitching.Number]/2;
minnum: CornerStitching.Number = FIRST[CornerStitching.Number]/2;
empty: CornerStitching.Rect = [maxnum, maxnum, minnum, minnum];
Tesselation: TYPE ~ CornerStitching.Tesselation;
Rect: TYPE ~ CornerStitching.Rect;
Position: TYPE ~ CornerStitching.Position;
Tile: TYPE ~ CornerStitching.Tile;
Coord: TYPE ~ CornerStitching.Coord;
NEdge: PROCEDURE [t: REF Tile] RETURNS [INT] ~ INLINE {RETURN [t.en.pos.y]};
EEdge: PROCEDURE [t: REF Tile] RETURNS [INT] ~ INLINE {RETURN [PtoR[t.ne].pos.x]};
SEdge: PROCEDURE [t: REF Tile] RETURNS [INT] ~ INLINE {RETURN [t.pos.y]};
WEdge: PROCEDURE [t: REF Tile] RETURNS [INT] ~ INLINE {RETURN [t.pos.x]};
CoerceToTesselation: PUBLIC PROCEDURE [ref: REF ANY] RETURNS [REF Tesselation] ~ {
RETURN [NARROW[ref]]  -- may raise NARROWREFFAULT
};
RangeValue: TYPE ~ {lesser, inside, greater};
TileValue: PUBLIC ERROR ~ CODE;
TileDeleted: PUBLIC ERROR ~ CODE;
TilePosition: ERROR ~ CODE;
AreaNotEmpty: ERROR ~ CODE;
TilesNotAdjacent: ERROR ~ CODE;
DegenerateTile: ERROR ~ CODE;
neLimitCoord: Coord ~ [x~INT.LAST, y~INT.LAST];
nwLimitCoord: Coord ~ [x~INT.FIRST, y~INT.LAST];
swLimitCoord: Coord ~ [x~INT.FIRST, y~INT.FIRST];
seLimitCoord: Coord ~ [x~INT.LAST, y~INT.FIRST];
guard: REF ANY ~ $CornerStitchingPrivateEdgeGuard;
deleted: REF ANY ~ $CornerStitchingPrivateDeletedTile;
northLimit: REF Tile;
southLimit: REF Tile;
eastLimit: REF Tile;
westLimit: REF Tile;
InitTesselationBorderTiles: PROCEDURE ~ {
northLimit _ NEW[Tile _ [pos~nwLimitCoord, value~guard]];
southLimit _ NEW[Tile _ [pos~swLimitCoord, value~guard]];
eastLimit _ NEW[Tile _ [pos~seLimitCoord, value~guard]];
westLimit _ NEW[Tile _ [pos~swLimitCoord, value~guard]];
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];
};
NewTesselation: PUBLIC PROCEDURE RETURNS [REF Tesselation] ~ {
centreSpace: REF Tile _ NEW[Tile _ [en~northLimit, ne~RtoP[eastLimit], sw~westLimit, ws~RtoP[southLimit], pos~swLimitCoord]];
RETURN [NEW[Tesselation _ [southEast~centreSpace, current~centreSpace]]]
};
FreeTesselation: PUBLIC PROCEDURE [plane: REF Tesselation] ~ {
centreSpace: REF Tile _ NEW[Tile _ [en~northLimit, ne~RtoP[eastLimit], sw~westLimit, ws~RtoP[southLimit], pos~swLimitCoord]];
plane.current _ plane.southEast _ centreSpace;
plane.deletionCache _ NIL;  -- allow the cache to be garbage collected.
plane.tilesInTesselationCount _ 1;
};
ChangeRect: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, newvalue: REF ANY _ NIL, checkOldvalue: BOOLEAN _ TRUE, oldvalue: REF ANY _ NIL] ~ {
SplitEWRunningBorder: PROCEDURE [StartTile: REF Tile, splitLine, lineEndpoint: INT] ~ INLINE {
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 -- This tile straddles the border, chop chop.
boundaryRider _ NSSplit[ plane, boundaryRider, splitLine].larger;
boundaryRider _ PtoR[boundaryRider.ne]
ENDLOOP;
};
tile: REF Tile _ FindTileContainingPoint[plane.current, [x~rect.x1, y~rect.y2]];
plane.current _ tile;
SplitEWRunningBorder[ tile, rect.y2, rect.x2];
SplitEWRunningBorder[ FindTileContainingPoint[plane.current, [x~rect.x1, y~rect.y1]],
rect.y1, rect.x2];
tile _ FindTileContainingPoint[plane.current, [x~rect.x1, y~rect.y2.PRED]];
DO
IF tile.value # newvalue AND WEdge[tile] < rect.x1 THEN {
outsideTile: REF Tile;
[smaller~outsideTile, larger~tile] _ EWSplit[plane, tile, rect.x1];
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 checkOldvalue AND tile.value # oldvalue THEN ERROR TileValue;
IF tile.value # newvalue THEN {
IF EEdge[tile] > rect.x2 THEN {
outsideTile: REF Tile;
[smaller~tile, larger~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
};
ChangeTile: PROCEDURE [plane: REF Tesselation, tile: REF Tile, newvalue: REF ANY _ NIL] RETURNS [REF Tile] ~ {
swCorner: Coord ~ tile.pos;
neCorner: Coord ~ [x~EEdge[tile], y~NEdge[tile]];
tWest, tEast, tCentre: REF Tile;
tile.value _ newvalue;  -- Make tile a newvalue tile, then restore maximal East-West strip property
tEast _ PtoR[tile.ne];
IF tEast.value = newvalue AND NEdge[tEast] > neCorner.y
THEN [] _ NSSplit[plane, tEast, neCorner.y];
tWest _ tile.en;
WHILE WEdge[tWest] >= swCorner.x DO tWest _ tWest.sw ENDLOOP;
IF tWest.value = newvalue AND SEdge[tWest] < neCorner.y THEN [] _ NSSplit[plane, tWest, neCorner.y];
tWest _ tile.sw;
IF tWest.value = newvalue AND SEdge[tWest] < swCorner.y
THEN [] _ NSSplit[plane, tWest, swCorner.y];
tEast _ PtoR[tile.ws];
WHILE EEdge[tEast] <= neCorner.x DO tEast _ PtoR[tEast.ne] ENDLOOP;
IF tEast.value = newvalue AND NEdge[tEast] > swCorner.y
THEN [] _ NSSplit[plane, tEast, swCorner.y];
tWest _ tile.sw;
WHILE NEdge[tWest] < neCorner.y DO
IF tWest.value # newvalue AND tWest.en.value # newvalue THEN
tWest _ tWest.en
ELSE {
tile _ NSSplit[plane, tile, NEdge[tWest]].larger;
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] > swCorner.y 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;
tCentre _ tEast.sw;
WHILE NEdge[tCentre] <= swCorner.y DO
tCentre _ tCentre.en;
ENDLOOP;
tile _ tCentre;
WHILE NEdge[tCentre] <= neCorner.y DO
tile _ tCentre;
IF PtoR[tCentre.ne].value # newvalue THEN {
tCentre _ tCentre.en;
}
ELSE {
tCentre _ tCentre.en;
IF tile.ne = tCentre.ne THEN  -- Should not occur at north.
[] _ 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]
ENDLOOP;
IF tile.value = tCentre.value AND WEdge[tile] = WEdge[tile.en] AND EEdge[tile] = EEdge[tile.en]
THEN tile _ NSMerge[plane, tile, tile.en];
RETURN [tile]
};
AreaEmpty: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, backgroundValue: REF ANY _ NIL] RETURNS [BOOLEAN] ~ {
plane.current _ FindTileContainingPoint[plane.current, [x~rect.x1, y~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]
};
ContentsBound: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, backgroundValue: REF ANY _ NIL] RETURNS [bBox: Rect] ~ {
tile: REF Tile;
bBox _ empty;
IF rect.x1 = rect.x2 THEN ERROR DegenerateTile;
plane.current _ FindTileContainingPoint[plane.current, [x~rect.x1, y~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}
ELSE 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, [x~rect.x2.PRED, y~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.PRED];
ENDLOOP;
};
EnumerateArea: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, perTile: CornerStitching.PerTileProc _ NIL, data: REF ANY _ NIL, backgroundValue: REF ANY _ NIL] RETURNS [REF ANY] ~ {
ChildOf: PROCEDURE [ me: REF Tile, you: REF Tile] RETURNS [BOOLEAN] ~ INLINE {
RETURN [ you.sw = me];
};
BrotherOf: PROCEDURE [ me: REF Tile, you: REF Tile] RETURNS [BOOLEAN] ~ INLINE {
RETURN [ me.sw = you.sw];
};
EnumerateShadow: PROCEDURE [tile: REF Tile] RETURNS [REF Tile]~ {
seeking: {youth, experience} _ youth;
DO
IF seeking = youth THEN {
child: REF Tile _ PtoR[tile.ne];
WHILE SEdge[child] >= rect.y2 DO
child _ PtoR[child.ws]
ENDLOOP;
IF ChildOf[ me~tile, you~child] AND WEdge[child] < rect.x2 AND SEdge[child] > rect.y1 THEN {
tile _ child;
LOOP
}
ELSE
seeking _ experience
};
IF tile.value # backgroundValue THEN
IF perTile # NIL THEN data _ perTile[ tile, data]
ELSE tileEnumeration _ CONS[ NEW[ CornerStitching.Region _ [
[ MAX[ WEdge[tile], rect.x1], MAX[ SEdge[tile], rect.y1],  MIN[ EEdge[tile], rect.x2], MIN[ NEdge[tile], rect.y2]],
tile.value] ], tileEnumeration];
IF WEdge[tile] <= rect.x1 OR SEdge[tile] <= rect.y1 THEN
RETURN [tile];
IF BrotherOf[ me~tile, you~PtoR[tile.ws]] AND SEdge[PtoR[tile.ws]] > rect.y1 THEN {
tile _ PtoR[tile.ws];
seeking _ youth
}
ELSE
tile _ tile.sw;
ENDLOOP
};
tileEnumeration: LIST OF REF CornerStitching.Region _ NIL;
borderTile: REF Tile _ FindTileContainingPoint[plane.current, [x~rect.x1, y~rect.y2]];
IF SEdge[borderTile] = rect.y2 AND SEdge[borderTile] > rect.y1 THEN {
borderTile _ PtoR[borderTile.ws];
WHILE EEdge[borderTile] <= rect.x1 DO
borderTile _ PtoR[borderTile.ne]
ENDLOOP;
};
plane.current _ borderTile;
WHILE SEdge[borderTile] > rect.y1 DO
borderTile _ EnumerateShadow[ borderTile];
borderTile _ PtoR[borderTile.ws];
WHILE EEdge[borderTile] <= rect.x1 DO
borderTile _ PtoR[borderTile.ne]
ENDLOOP
ENDLOOP;
WHILE WEdge[borderTile] < rect.x2 OR WEdge[borderTile] <= rect.x1 DO
nextTile: REF Tile _ PtoR[borderTile.ne];
WHILE SEdge[nextTile] > rect.y1 DO
nextTile _ PtoR[nextTile.ws]
ENDLOOP;
borderTile _ EnumerateShadow[ borderTile];
borderTile _ nextTile
ENDLOOP;
IF perTile = NIL THEN data _ tileEnumeration;
RETURN [data]
};
TileAbove: PROCEDURE [tile: REF Tile, x: INT] RETURNS [REF Tile] ~ {
IF ~ (WEdge[tile] <= x AND EEdge[tile] > x) THEN ERROR TilePosition;
tile _ tile.en;
WHILE WEdge[tile] > x DO
tile _ tile.sw;
ENDLOOP;
RETURN [tile]
};
TileAt: PUBLIC PROCEDURE [plane: REF Tesselation, pos: Position] RETURNS [CornerStitching.TilePtr] ~ {
pos.x _ MIN[ INT.LAST.PRED, pos.x]; pos.y _ MIN[ INT.LAST.PRED, pos.y];
RETURN [plane.current _ FindTileContainingPoint[plane.current, [x~pos.x, y~pos.y]] ];
};
FindTileContainingPoint: PROCEDURE [tile: REF Tile, p: Coord] RETURNS [REF Tile] ~ {
IF tile.value = deleted THEN ERROR TileDeleted;
DO
SELECT NSRange[tile, p] FROM
inside => NULL;
lesser => WHILE p.y < SEdge[tile] DO
tile _ PtoR[tile.ws];
ENDLOOP;
greater => WHILE p.y >= NEdge[tile] DO
tile _ tile.en;
ENDLOOP;
ENDCASE;
SELECT EWRange[tile, p] FROM
inside => EXIT;  -- We have found the tile with NSRange & EWRange satisfied
lesser => WHILE p.x < WEdge[tile] DO
tile _ tile.sw;
ENDLOOP;
greater => WHILE p.x >= EEdge[tile] DO
tile _ PtoR[tile.ne];
ENDLOOP;
ENDCASE;
ENDLOOP;
RETURN [tile]
};
NSRange: PROCEDURE [tile: REF Tile, p: Coord] RETURNS [RangeValue] ~ {
RETURN [SELECT p.y FROM
< SEdge[tile] => lesser,
>= NEdge[tile] => greater,
ENDCASE => inside]
};
EWRange: PROCEDURE [tile: REF Tile, p: Coord] RETURNS [RangeValue] ~ {
RETURN [SELECT p.x FROM
< WEdge[tile] => lesser,
>= EEdge[tile] => greater,
ENDCASE => inside]
};
EWSplit: PROCEDURE [plane: REF Tesselation, tile: REF Tile, x: INT] RETURNS [ larger, smaller: REF Tile] ~ {
eastTile: REF Tile;
t: REF Tile;
IF WEdge[tile] >= x OR EEdge[tile] <= x THEN ERROR TilePosition;
IF plane.deletionCache = NIL THEN eastTile _ NEW[Tile _ tile^]
ELSE {
eastTile _ plane.deletionCache;
plane.deletionCache _ plane.deletionCache.sw;
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 [larger~eastTile, smaller~tile]
};
NSSplit: PROCEDURE [plane: REF Tesselation, tile: REF Tile, y: INT] RETURNS [ larger, smaller: REF Tile] ~ {
northTile: REF Tile;
t: REF Tile;
IF SEdge[tile] >= y OR NEdge[tile] <= y THEN ERROR TilePosition;
IF plane.deletionCache = NIL THEN northTile _ NEW[Tile _ tile^]
ELSE {
northTile _ plane.deletionCache;
plane.deletionCache _ plane.deletionCache.sw;
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 [larger~northTile, smaller~tile]
};
EWMerge: PROCEDURE [plane: REF Tesselation, tileW, tileE: REF Tile] RETURNS [REF Tile] ~ {
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 THEN ERROR TilesNotAdjacent;
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;
tileE.sw _ plane.deletionCache;
plane.deletionCache _ tileE;
plane.tilesInTesselationCount _ plane.tilesInTesselationCount - 1;
RETURN [tileW];
};
NSMerge: PROCEDURE [plane: REF Tesselation, tileS, tileN: REF Tile] RETURNS [REF Tile] ~ {
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 THEN ERROR TilesNotAdjacent;
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;
tileN.sw _ plane.deletionCache;
plane.deletionCache _ tileN;
plane.tilesInTesselationCount _ plane.tilesInTesselationCount - 1;
RETURN [tileS];
};
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]] }
};
Init: PROCEDURE ~ {
InitTesselationBorderTiles[]
};
Init[];
END.
XCornerStitchingImpl.mesa
Written by Shand, September 12, 1983 11:40 pm
Last Edited by: Mccreight, November 28, 1983 5:53 pm
Last Edited by: Jacobi, February 23, 1984 3:59 pm
Last Edited by: Beach, June 12, 1984 11:00:30 pm PDT
-- 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.  They fit together like a picture-frame and are stitched accordingly.
-- North-East
-- South-East
-- North-West
-- South-West
-- All the following was made obsolete by making ne and ws LONG POINTERs
-- Corner stitched structures contain circular pointer chains.  The reference count based garbage collector in Cedar cannot handle such structures, so this routine breaks cycles so that tiles can be freed.  But we must be careful not to recurse too deeply or cedar will run out of MDS and go to fon-fon.  Therefore we don't take the obvious fully recursive approach rather we apply EnumerateArea.
Smash: CornerStitching.PerTileProc -- [tile: TilePtr, data: REF ANY] RETURNS [REF ANY] -- ~ {
tile.ne _ tile.en _ NIL;
RETURN [ NIL]
};
-- Unfortunately the world here is not quite ansiotropic, so that it is fine to talk about points along the western and southern edges of the world, but very dangerous on the northern and eastern borders.  The reason is simple, every point must be assigned to some tile.  when points lie on tile boundary some arbitrary decision must be made, we choose to put such points in the northern or eastern tile.  Thus points on the Northern and Eastern borders get put in the guard tiles, with often dire results.  A quick and dirty fix takes the PRED of NE limits.
[] _ EnumerateArea[ plane, [ swLimitCoord.x, swLimitCoord.y,   neLimitCoord.x.PRED, neLimitCoord.y.PRED], Smash, NIL, guard];

-- Acutally we only clear the design, this way we will still know what to do if subsequently passed such a Tesselation.  Reassignment of the Tesselation through NewTesselation will free centreSpace.
-- 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.
-- tile contains nw corner (sort of!)
--split tiles on the north border.
--split tiles on the south border.
-- 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.
-- 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 >= swCorner.x but whose WEdge is < swCorner.x.  In fact SEdge[tWest] < neCorner.y will only hold if EEdge = swCorner.x
-- 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.
-- tile is the northernmost strip in the changed area.
-- It may need to be merged with the tile above.
-- tCentre is still the northernmost strip in the changed area though it may extend north of it.
-- 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 proceed 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.
-- He ain't no son o' mine
-- Add tile to enumeration.
-- Hand control to older sibling or parent (if you're the oldest).
-- This tile is the result of spontaneous generation!
-- Progress Southwards along the west border.
-- borderTile is now the tile containing [rect.x1, rect.y1].  Progress Eastwards along the south border.
-- The second clause in the WHILE test is a little hack to ensure at least one tile is enumerated for degenerate (ie x1 = x2) rects.  EnumerateShadow always enumerates one tile at least.
-- Assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)
WHILE tile.value = deleted DO
-- We may have be passed a tile ptr derived from the current tesselation access pointer in a Tesselation record.  This tile may have been subject to a merge after the current tesselation access pointer was set to point at it, so we leap from deleted tile to deleted tile trying to reach stable ground.  When a tile is merged the en REF is set to point at a valid tile, so we will always reach stable ground.
tile _ tile.en;
ENDLOOP;
-- Go North or South until a tile with appropriate range is found is found
-- Go East or West until a tile with appropriate range is found is found
-- Iterate to ensure going East-West did not screw up North-South
-- 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 one will be deallocated.
-- Fix the tiles relative to each other.
-- Fix North boundary
-- Fix East boundary
-- Fix South boundary
-- tileE may have been the current tesselation access pointer.
-- see corresponding comment in NSMerge.
-- The North one will be deallocated.
-- Fix the tiles relative to each other.
-- Fix East boundary
-- Fix North boundary
-- Fix West boundary
-- tileN may have been the current tesselation access pointer.
-- We explicitly check for this condition and correct it.  OLD METHOD => It is given a special unique value to ensure that FindTileContainingPoint will never return this tile, however it is still stitched to tiles near to where it was so search effiency is not sacrificed.  It is possible that after several subsequent megres tileN will point to other deleted tiles however there will be no cycles amongst the deleted tiles so that as soon as the current tesselation access pointer is set to point into valid tiles, the deleted tiles will be garbage collected.
ส‰˜
code™K™-J™4J™1J™4—K˜š
ฯk	˜	Kš
œ˜K˜
—Iunitšฯbœœ
˜"Kšœ˜Kšœ˜Lšœ!œ˜@Jšœ!œ˜AJš
œ?˜?Lšœ
œ˜0Lšœœ˜"Lšœ
œ˜*Lšœœ˜"Lšœœ˜$Lšฯnœ	œœœœœœ˜LKšŸœ	œœœœœœœ˜RKšŸœ	œœœœœœ˜IKšŸœ	œœœœœœ˜IšŸœœ
	œœ
œœœ˜RKšœœฯc˜1K˜—Lšœœ˜-™Lšœœ
œœ
˜Kšœ
œ
œœ
˜!Lšœœœ
˜Kšœœœ
˜Kšœœœ
˜Kšœœœ
˜—™Kš	œœ
œœ
œ˜/Kš	œœ
œœ
œ˜0Kš	œœ
œœ
œ˜1Kš	œœ
œœ
œ˜0—™JKšœœ
œ$˜2Kšœ	œ
œ&˜6—™,Kšœœ˜Kšœœ˜Kšœœ˜Kšœœ˜—šŸœ	œ˜)Lšœ
œ)˜9Kšœ
œ)˜9Kšœœ)˜8Kšœœ)˜8™6K™y—™
Kš
œ ˜ Kš
œ˜—™
Kš
œ˜Kš
œ ˜ Kš
œ ˜ Kš
œ˜—™
Kš
œ ˜ Kš
œ˜Kš
œ˜Kš
œ ˜ —™
Kš
œ˜Kš
œ ˜ —K˜—š
Ÿœœ
	œ
œœ˜>Lšœ
œœb˜}Kšœœ=˜HK˜—šŸœœ
	œ	œ˜>™HJš
œŒ™ŒšŸœ 6œ™]Kšœœ
™Kšœœ
™
K™—J™ฎKšœNœœ
œ
™~—Jš
œฦ
™ฦ
Lšœ
œœb˜}Kš
œ.˜.Kšœœ +˜GKš
œ"˜"K˜—šŸ
œœ
	œ	œ$œ
œœœœœ
œœ˜–
š
Ÿœ	œ
œ œœ˜^Kšœœ
˜$šœ%˜,Kšœ"œœœ
˜YK™†š	œ"œ!œ&œ
 -˜ข
Kš
œA˜A—Kšœœ˜&Kšœ
˜—K˜—KšœœG˜PK™%Kš
œ˜Lš
œ"™"Kš
œ.˜.Lš
œ"™"Kš
œh˜hLš
œL™LLšœDœ˜KLš
œ0™0š
˜šœœœ˜9Kšœ
œ˜Kš
œC˜CK™:šœ*œ,œ,˜Ž
Kš
œ:˜:—š
œœœœœœ˜ 
Kšœœ˜?—K˜—š
˜Kšœœœ
œ˜@šœœ˜šœœ˜Kšœ
œ˜Kš
œC˜Cšœ*œ,œ,˜Ž
Kš
œ:˜:—š
œœœœœœ˜ 
Kšœœ˜?—K˜—Kš
œ(˜(K˜—Kšœœ
œ
˜$Kšœœ
˜Kšœœœ ˜DKšœ
˜—Kšœœ
œ
˜$Kšœœ
œ
˜$Kšœœ
˜Kšœœ˜<Kš
˜—K˜—šŸ
œ	œ	œœœ
œœœœ
˜nL™qK˜K˜1Kšœœ˜ Lšœ ะco 4˜cLšœฯoœh™ˆ
Kšœœ
˜Kšœœœ(˜dK˜Kšœœœ
˜=Kš
œค
™ค
Kšœœœ(˜dLš
œ˜Kšœœœ(˜dKšœœ
˜Kšœœ	œœ
˜CK™#Kšœœœ(˜dL™NLšœaขœ*™“
K˜šœ˜"šœœ˜<K˜—šœ˜Kš
œ1˜1Kšœœœ˜JK˜K˜
—Kšœ
˜—Kšœขœ/™6Kšœœ$˜BLšœ-ขœz™ซ
LšœDขœ,ขœ™š
Kšœœ
˜šœ˜"K˜š	œœ
œœ˜bKš
œ(˜(—Kšœœ
˜Kšœ
˜—Lšœ`ขœ+™“
Kš
œ˜šœ˜%Kš
œ˜Kšœ
˜—Lš
œ˜šœ˜%Kš
œ˜šœ
œœ˜+Kš
œ˜Kš
œ
˜
—šœ˜Kš
œ˜šœœ ˜;Kšœœ˜0—Kšœœ˜+K˜—š
œœœœœœ˜vKšœœ˜*—Kšœ
˜—Lšœขœ/™6L™0šœœœ˜_Kšœ&˜*—LšœขœV™`Kšœ˜
Kš
œ˜—šŸ	œœ
	œ	œ+œ
œœœœ˜vKš 
ะck 9ฃœ2™~Kš
œO˜Ošœœ0œ˜[Kš
œœœ
œœ
˜LKšœ
˜—Kšœœ
˜
K˜—šŸ
œœ
	œ	œ+œ
œœœ˜}Kšœ8ขœ
ขœ2™‡
Kšœœ˜Kš
œ
˜
Kšœœ
œ˜/Kš
œO˜Ošœ0˜5Kšœœ
œ ˜8Kšœœœ
˜BKšœ
˜—Lšœ
œ˜%šœ˜Kšœœœ
˜?Kšœขœขœ/™lKšœ
œœœ˜SKš
œ ˜ Kšœ
˜—Lšœ9œ˜Kšœ˜KšœขœJขœ
™pšœœ˜&Kš
œ˜Kš
œ˜K˜
—šœ
œœ˜$Kšœœ˜4Kš
œ˜K˜—Kšœœ˜%Kšœ
˜—K˜—šŸ
œœ
	œ	œAœœ
œœœ
œœœœ
œ˜ป
Jš
œฅ™ฅšŸœ	œœœœœœ˜NJšœ˜J˜—šŸ	œ	œœœœœœ˜PJšœ˜J˜—š
Ÿœ	œœœœ	˜AK˜%š
˜šœœ˜Kšœœœ
˜ šœ˜ J™Kšœœ
˜Kšœ
˜—šœœœœ˜\K˜
Kš
˜K˜
—š
˜Kš
œ˜—K˜—J™šœ˜$Kšœœ
œ˜1Kšœœœœœœœ:˜ั
—J™Bšœœ˜8K™5Kšœ˜—š
œœœœœ˜SKšœœ
˜Kš
œ˜K˜
—š
˜K˜—Kš
˜—K˜—Lš	œœ
œ
œœ
˜:KšœœG˜Všœœœ˜EKšœ
œ˜!šœ˜%Kšœ
œ˜ Kšœ
˜—K˜—Kš
œ˜L™-šœ˜$Kš
œ*˜*Kšœ
œ˜!šœ˜%Kšœ
œ˜ Kš
˜—Kšœ
˜—Lš
œh™hKš
œบ
™บ
šœœ˜DKšœ
œœ˜)šœ˜"Kšœœ
˜Kšœ
˜—Kš
œ*˜*Kš
œ˜Kšœ
˜—Kšœœ
œ˜-Kšœ˜
Kš
œ˜—šŸ	œ	œœ
œœœ
˜DKšœข
œขœ*™EKšœœœ
œ˜DK˜šœ˜K˜Kšœ
˜—Kšœ˜
K˜—š
Ÿœœ
	œ	œœ˜fKšœœœ
œ
œœœ
œ
œ	˜GKšœO˜UKš
œ˜—š
Ÿœ	œœœœ
˜Tšœ™Jš
œ—™—Kš
œ™Kšœ
™—Kšœœ
œ˜/š
˜K™Jšœ˜Kšœ
œ
˜šœ
œ˜$Kšœœ
˜Kšœ
˜—šœœ˜&Kš
œ˜Kšœ
˜—Kšœ
˜—K™Hšœ˜Kšœ
œ :˜Kšœ
œ˜$Kš
œ˜Kšœ
˜—šœœ˜&Kšœœ
˜Kšœ
˜—Kšœ
˜—K™AKšœ
˜—Kšœ˜
K˜—šŸœ	œœœ˜Fšœœ˜Kš
œ˜Kš
œ˜Kšœ˜—K˜—šŸœ	œœœ˜Fšœœ˜Kš
œ˜Kš
œ˜Kšœ˜—Kš
œ˜—šŸœ	œ œ
œœœ
˜lK™$Kšœ
œ˜Kšœœ˜Lšœœœ
œ˜@Lšœขœข™(Lšœœ
œœ˜>šœ˜Kš
œ˜Kš
œ-˜-Kš
œ˜K˜—Kš
œB˜BL™(Kš
œ˜Kš
œ˜K˜L™Kš
œ˜Kšœœ#œ
˜@K˜L™Kšœœ˜Kšœ
œœœ
˜?L™Kšœœ
˜Kš
œ
œœœœ
˜8Kš
œ˜Kšœ
œœœ
˜?Lšœ ˜&K˜—šŸœ	œ œ
œœœ
˜lK™%Kšœœ˜Kšœœ˜Lšœœœ
œ˜@Lšœข	œข™)Lšœœ
œ
œ˜?šœ˜Kš
œ ˜ Kš
œ-˜-Kš
œ˜K˜—Kš
œB˜BL™(K˜K˜K˜L™Kšœœ˜Kšœœœœ
˜AK˜L™Kš
œ˜Kšœœ$œ
˜FL™Kš
œ˜Kšœœœ
˜,K˜Kšœ
œœ$œ
˜FLšœ!˜'K˜—š
Ÿœ	œ(œœœ
˜ZK™$Lšœœ
œœœ!œ
œ˜Š
L™(Kš
œ˜Kš
œ˜L™š	œœœ
œ˜<Kš
œ˜Kšœ
˜—L™šœœœœœ˜BKš
œ
˜
Kšœ
˜—L™šœœœœœ˜BKš
œ
˜
Kšœ
˜—šœข"œ
™>Kš
 (™(—K˜Kšœœ
˜Kšœœ˜4Kš
œ˜Kš
œ˜Kš
œB˜BLšœ	˜K˜—š
Ÿœ	œ(œœœ
˜ZK™%Lšœ
œœœœ
œœœ
œ˜–
L™(Kš
œ˜K˜L™šœœœœœ˜BKš
œ
˜
Kšœ
˜—L™š	œœœ
œ˜<Kš
œ˜Kšœ
˜—L™š	œœœ
œ˜<Kš
œ˜Kšœ
˜—šœข"œ
™>Kšœ{ขœญข"œO™ฐ—K˜Kšœœ
˜Kšœœ˜4Kš
œ˜Kš
œ˜Kš
œB˜BLšœ	˜K˜—šŸœ	œœ
œ
œœœ	œ˜GKšœœœ˜ K˜—šŸœ	œœœœ
œ
œ	œ
˜GKšœœœ˜ K˜—šŸœ	œ˜Kš
œ˜K˜—L˜Kšœ
˜—…—@,t