<> <> <> <> <> DIRECTORY SafeStorage USING [GetSystemZone], CornerStitching ; CornerStitchingImpl: CEDAR MONITOR IMPORTS SafeStorage EXPORTS CornerStitching ~ BEGIN CSZ: ZONE; 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]}; RangeValue: TYPE ~ {lesser, inside, greater}; <<-- Error Codes>> TileValue: PUBLIC ERROR ~ CODE; TileDeleted: PUBLIC ERROR ~ CODE; TilePosition: ERROR ~ CODE; AreaNotEmpty: ERROR ~ CODE; TilesNotAdjacent: ERROR ~ CODE; DegenerateTile: ERROR ~ CODE; <<-- Co-ordinates at "infinity">> 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.SUCC, y1~Number.FIRST, x2~Number.LAST.PRED, y2~Number.LAST.PRED]; <<-- House-keeping tile values to flag deleted tiles and tiles at "infinity">> guard: REF ANY ~ $CornerStitchingPrivateEdgeGuard; deleted: REF ANY ~ $CornerStitchingPrivateDeletedTile; <<-- Border Tiles (shared by all tesselations)>> northLimit: REF Tile; northBuffer: REF Tile; southLimit: REF Tile; eastLimit: REF Tile; westLimit: REF Tile; InitTesselationBorderTiles: PROCEDURE ~ { northLimit _ NEW[Tile _ [pos~nwLimitCoord, value~guard]]; northBuffer _ NEW[Tile _ [pos~[emptyRect.x1, emptyRect.y2], value~guard]]; southLimit _ NEW[Tile _ [pos~swLimitCoord, value~guard]]; eastLimit _ NEW[Tile _ [pos~seLimitCoord, value~guard]]; westLimit _ NEW[Tile _ [pos~swLimitCoord, value~guard]]; <<-- 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>> northLimit.ne _ RtoP[eastLimit]; eastLimit.en _ northLimit; <<-- South-East>> southLimit.en _ eastLimit; southLimit.ne _ RtoP[eastLimit]; eastLimit.ws _ RtoP[southLimit]; eastLimit.sw _ southLimit; <<-- North-West>> westLimit.ne _ RtoP[northLimit]; westLimit.en _ northLimit; northLimit.sw _ westLimit; northLimit.ws _ RtoP[westLimit]; <<-- South-West>> southLimit.sw _ westLimit; westLimit.ws _ RtoP[southLimit]; <<-- northBuffer>> northBuffer.en _ northLimit; northBuffer.ne _ RtoP[eastLimit]; northBuffer.sw _ westLimit; northBuffer.ws _ NIL; }; TileCache: REF Tile; Disguise: TYPE ~ RECORD [ hiddenValue: REF ANY ]; DisguiseCache: REF Disguise; DumpCache: PUBLIC ENTRY PROCEDURE ~ { ENABLE UNWIND => NULL; IF TileCache # NIL THEN { lag: REF Tile _ TileCache; FOR tc: REF Tile _ TileCache.en, tc.en WHILE tc # NIL DO lag.en _ NIL; lag _ tc ENDLOOP; TileCache _ 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 }; }; NewTile: ENTRY PROCEDURE RETURNS [tile: REF Tile] ~ { ENABLE UNWIND => NULL; IF TileCache # NIL THEN { tile _ TileCache; TileCache _ TileCache.en; } ELSE tile _ CSZ.NEW[Tile]; }; CacheTile: ENTRY PROCEDURE [tile: REF Tile] ~ { ENABLE UNWIND => NULL; tile.sw _ NIL; -- Prevent potential circular chains in the cache. tile.en _ TileCache; TileCache _ tile; }; NewDisguise: ENTRY PROCEDURE RETURNS [disguise: REF Disguise] ~ { ENABLE UNWIND => NULL; IF DisguiseCache # NIL THEN { disguise _ DisguiseCache; DisguiseCache _ NARROW[DisguiseCache.hiddenValue]; } ELSE disguise _ CSZ.NEW[Disguise]; }; CacheDisguise: ENTRY PROCEDURE [disguise: REF Disguise] ~ { ENABLE UNWIND => NULL; disguise.hiddenValue _ DisguiseCache; DisguiseCache _ disguise; }; NewTesselation: PUBLIC PROCEDURE RETURNS [REF Tesselation] ~ { eastSpace: REF Tile _ NewTile[]; centreSpace: REF Tile _ NewTile[]; 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]; <<--Don't bother putting Tesselations in CSZ>> RETURN [NEW[Tesselation _ [southEast~eastSpace, current~centreSpace]]] }; FreeTesselation: PUBLIC PROCEDURE [plane: REF Tesselation, freeCache: BOOLEAN _ TRUE] ~ { CacheIt: CornerStitching.PerTileProc -- [tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY] -- ~ { <<-- Depends on fact that Enumeration proceeds NE to SW, so en ref may be clobbered by caching process.>> CacheTile[tile]; }; IF freeCache THEN { DumpCache[]; plane.current _ plane.southEast _ NIL; } ELSE { [] _ 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; }; plane.tilesInTesselationCount _ 0 }; ChangeRect: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, newValue: REF ANY _ NIL] ~ { SplitEWRunningBorder: PROCEDURE [StartTile: REF Tile, splitLine, lineEndpoint: Number] ~ INLINE { boundaryRider: REF Tile _ StartTile; WHILE WEdge[boundaryRider] < lineEndpoint DO WHILE SEdge[boundaryRider] > splitLine DO boundaryRider _ PtoR[boundaryRider.ws] ENDLOOP; <<-- 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.>> 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]; boundaryRider _ PtoR[boundaryRider.ne] ENDLOOP; }; tile: REF Tile _ FindTileContainingPoint[plane.current, [x~rect.x1, y~rect.y2]]; <<-- tile contains nw corner (sort of!)>> plane.current _ tile; <<--split tiles on the north border.>> SplitEWRunningBorder[ tile, rect.y2, rect.x2]; <<--split tiles on the south border.>> SplitEWRunningBorder[ FindTileContainingPoint[plane.current, [x~rect.x1, y~rect.y1]], rect.y1, rect.x2]; <<-- Now we start gobbling up all the tiles into wide flat bands of newValue.>> tile _ FindTileContainingPoint[plane.current, [x~rect.x1, y~rect.y2.PRED]]; <<-- First get our western border tile into shape.>> DO IF tile.value # newValue AND WEdge[tile] < rect.x1 THEN { outsideTile: REF Tile; tile _ EWSplit[plane, tile, rect.x1]; outsideTile _ tile.sw; <<-- Better make sure we keep outside tile in order NS-wise.>> 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 }; FuncChangeRect: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, perTile: CornerStitching.PerTileChangeProc, data: REF ANY _ NIL] ~ { DisguiseTile: CornerStitching.PerTileProc -- [tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY] -- ~ { disguise: REF Disguise; (disguise _ NewDisguise[]).hiddenValue _ tile.value; tile.value _ disguise; }; ApplyFuncToTile: CornerStitching.PerTileProc -- [tile: CornerStitching.TilePtr, data: REF ANY] RETURNS [REF ANY] -- ~ { 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 <<-- Restore tile value>> [] _ ChangeTile[plane~ plane, tile~ tile, newValue~ disguise.hiddenValue]; <<-- Call perTile function>> perTile[plane~ plane, rect~ clippedBB, oldValue~ disguise.hiddenValue, data~ data]; <<-- Put this disguise in the cache>> CacheDisguise[disguise]; }; [] _ EnumerateArea[plane, rect, DisguiseTile, NIL, deleted]; [] _ EnumerateArea[plane, rect, ApplyFuncToTile, data, deleted]; }; ChangeTile: PROCEDURE [plane: REF Tesselation, tile: REF Tile, newValue: REF ANY _ NIL] RETURNS [REF Tile] ~ { <<-- Returns the northernmost tile in the changed region. (There is only one such tile by the maximal-EW-property)>> 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 <<-- 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>> 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; <<-- 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>> 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; <<-- Analogous to split of NW corner.>> IF tEast.value = newValue AND NEdge[tEast] > south THEN [] _ NSSplit[plane, tEast, south]; <<-- 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.>> 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; <<-- tile is the northernmost strip in the changed area.>> IF tWest.value = newValue THEN tile _ EWMerge[plane, tWest, tile]; <<-- 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.>> 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; <<-- 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.>> 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] }; AreaEmpty: PUBLIC PROCEDURE [plane: REF Tesselation, rect: Rect, backgroundValue: REF ANY _ NIL] RETURNS [BOOLEAN] ~ { <<-- Return TRUE if all tiles in area are of value backgroundValue, else FALSE. Relies on the Maximal East-West strip property.>> 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] ~ { <<-- ContentsBound returns a minimal bounding box for non-backgroundValue tiles in rect. Relies on the Maximal East-West strip property.>> 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, [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 the east edge of tile must abut a non-backgroundValue tile (by the Maximal East-West strip property)>> 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 <<-- Note FindTileContainingPoint is assymetric so code is different here! (This is the cause of the ugly .PREDs)>> 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] ~ { <<-- 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.>> ChildOf: PROCEDURE [ me: REF Tile, you: REF Tile] RETURNS [BOOLEAN] ~ INLINE { RETURN [ you.sw = me AND SEdge[you] > rect.y1]; }; BrotherOf: 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, [x~rect.x1, y~rect.y2]]; doneSouthEastTile: BOOLEAN _ FALSE; <<-- correct for one off error when rect.y2 lies at tile boundary (YUK)>> 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 IF seeking = youth THEN { child: REF Tile _ PtoR[tile.ne]; WHILE SEdge[child] >= rect.y2 DO child _ PtoR[child.ws] ENDLOOP; IF ChildOf[tile, child] AND WEdge[child] < rect.x2 THEN { tile _ child; LOOP } ELSE seeking _ experience }; { prevT: REF Tile _ tile; <<-- Is tile a border tile?>> IF WEdge[tile] <= rect.x1 OR SEdge[tile] <= rect.y1 THEN { <<-- Find next border tile, i.e. next tree root>> 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 BrotherOf[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 _ CSZ.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] }; TileAbove: PROCEDURE [tile: REF Tile, x: Number] RETURNS [REF Tile] ~ { <<-- Assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)>> 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: Coord] RETURNS [CornerStitching.TilePtr] ~ { tile: REF Tile; pos.x _ MIN[ emptyRect.x2.PRED, pos.x]; pos.y _ MIN[ emptyRect.y2.PRED, pos.y]; tile _ FindTileContainingPoint[plane.current, pos]; IF tile = northBuffer THEN ERROR; RETURN [plane.current _ tile]; }; FindTileContainingPoint: PROCEDURE [tile: REF Tile, p: Coord] RETURNS [REF Tile] ~ { <> <<-- 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.>> <> <> IF tile.value = deleted THEN ERROR TileDeleted; DO <<-- Go North or South until a tile with appropriate range is found is found>> 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; <<-- Go East or West until a tile with appropriate range is found is found>> 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; <<-- Iterate to ensure going East-West did not screw up North-South>> 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: Number] RETURNS [REF Tile] ~ { <<-- The East one will be the new one.>> eastTile: REF Tile; t: REF Tile; IF WEdge[tile] >= x OR EEdge[tile] <= x THEN ERROR TilePosition; <<-- eastTile starts out a replica of tile>> (eastTile _ NewTile[])^ _ tile^; plane.tilesInTesselationCount _ plane.tilesInTesselationCount + 1; <<-- Fix the tiles relative to each other.>> tile.ne _ RtoP[eastTile]; eastTile.sw _ tile; eastTile.pos.x _ x; <<-- Fix North boundary>> t _ eastTile.en; WHILE t.pos.x >= x DO t.ws _ RtoP[eastTile]; t _ t.sw ENDLOOP; tile.en _ t; <<-- Fix East boundary>> t _ PtoR[eastTile.ne]; WHILE t.sw = tile DO t.sw _ eastTile; t _ PtoR[t.ws] ENDLOOP; <<-- Fix South boundary>> 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] }; NSSplit: PROCEDURE [plane: REF Tesselation, tile: REF Tile, y: Number] RETURNS [REF Tile] ~ { <<-- The North one will be the new one.>> northTile: REF Tile; t: REF Tile; IF SEdge[tile] >= y OR NEdge[tile] <= y THEN ERROR TilePosition; <<-- northTile starts out a replica of tile>> (northTile _ NewTile[])^ _ tile^; plane.tilesInTesselationCount _ plane.tilesInTesselationCount + 1; <<-- Fix the tiles relative to each other.>> tile.en _ northTile; northTile.ws _ RtoP[tile]; northTile.pos.y _ y; <<-- Fix East boundary>> t _ PtoR[northTile.ne]; WHILE t.pos.y >= y DO t.sw _ northTile; t _ PtoR[t.ws] ENDLOOP; tile.ne _ RtoP[t]; <<-- Fix North boundary>> t _ northTile.en; WHILE t.ws = RtoP[tile] DO t.ws _ RtoP[northTile]; t _ t.sw ENDLOOP; <<-- Fix West boundary>> 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] }; EWMerge: PROCEDURE [plane: REF Tesselation, tileW, tileE: REF Tile] RETURNS [REF Tile] ~ { <<-- The East one will be deallocated.>> 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; <<-- Fix the tiles relative to each other.>> tileW.en _ tileE.en; tileW.ne _ tileE.ne; <<-- Fix North boundary>> FOR t: REF Tile _ tileW.en, t.sw WHILE PtoR[t.ws] = tileE DO t.ws _ RtoP[tileW]; ENDLOOP; <<-- Fix East boundary>> FOR t: REF Tile _ PtoR[tileW.ne], PtoR[t.ws] WHILE t.sw = tileE DO t.sw _ tileW; ENDLOOP; <<-- Fix South boundary>> FOR t: REF Tile _ PtoR[tileE.ws], PtoR[t.ne] WHILE t.en = tileE DO t.en _ tileW; ENDLOOP; <<-- tileE may have been the current tesselation access pointer.>> <<-- see corresponding comment in NSMerge.>> tileE.value _ deleted; tileE.en _ NIL; IF plane.current = tileE THEN plane.current _ tileW; CacheTile[tileE]; plane.tilesInTesselationCount _ plane.tilesInTesselationCount - 1; RETURN [tileW]; }; NSMerge: PROCEDURE [plane: REF Tesselation, tileS, tileN: REF Tile] RETURNS [REF Tile] ~ { <<-- The North one will be deallocated.>> 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; <<-- Fix the tiles relative to each other.>> tileS.ne _ tileN.ne; tileS.en _ tileN.en; <<-- Fix East boundary>> FOR t: REF Tile _ PtoR[tileS.ne], PtoR[t.ws] WHILE t.sw = tileN DO t.sw _ tileS; ENDLOOP; <<-- Fix North boundary>> FOR t: REF Tile _ tileS.en, t.sw WHILE PtoR[t.ws] = tileN DO t.ws _ RtoP[tileS]; ENDLOOP; <<-- Fix West boundary>> FOR t: REF Tile _ tileN.sw, t.en WHILE PtoR[t.ne] = tileN DO t.ne _ RtoP[tileS]; ENDLOOP; <<-- 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.>> tileN.value _ deleted; tileN.en _ NIL; IF plane.current = tileN THEN plane.current _ tileS; CacheTile[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 ~ { CSZ _ SafeStorage.GetSystemZone[]; InitTesselationBorderTiles[] }; Init[]; END.