<> <> <> <> <> <> <> <> <> DIRECTORY CStitching; --, Process, SafeStorage; CStitchingImpl: CEDAR MONITOR IMPORTS CStitching --, Process, SafeStorage EXPORTS CStitching = BEGIN OPEN CStitching; UseOfAlreadyDeletedTile: ERROR = CODE; <<-- Co-ordinates at "infinity">> neLimit: Pos = [x: Number.LAST, y: Number.LAST]; nwLimit: Pos = [x: Number.FIRST, y: Number.LAST]; swLimit: Pos = [x: Number.FIRST, y: Number.FIRST]; seLimit: Pos = [x: Number.LAST, y: Number.FIRST]; allSpace: Rect = [x1: Number.FIRST+1, y1: Number.FIRST, x2: Number.LAST-1, y2: Number.LAST-1]; maxSpace: Rect = [x1: allSpace.x1+1, y1: allSpace.y1+1, x2: allSpace.x2-1, y2: allSpace.y2-1]; empty: Rect = [x1: Number.LAST, y1: Number.LAST, x2: Number.FIRST, y2: Number.FIRST]; <<>> <<-- House-keeping tile values to flag deleted tiles and tiles at "infinity">> PrivateRec: TYPE = RECORD[notused: REF]; guard: REF = NEW[PrivateRec_[$CSGuard]]; deleted: REF = NEW[PrivateRec_[$CSDeleted]]; <<>> <<-- Border Tiles (shared by all tesselations)>> northLimit: Tile = NEW[TileRec _ [pos: nwLimit, value: guard]]; northBuffer: Tile = NEW[TileRec _ [pos: [allSpace.x1, allSpace.y2], value: guard]]; southLimit: Tile = NEW[TileRec _ [pos: swLimit, value: guard]]; eastLimit: Tile = NEW[TileRec _ [pos: seLimit, value: guard]]; westLimit: Tile = NEW[TileRec _ [pos: swLimit, value: guard]]; Disguise: TYPE = RECORD [hiddenValue: REF]; disposedTiles: Tile _ NIL; disguiseCache: REF Disguise _ NIL; InitTesselationBorderTiles: PROC = { <<-- 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>> 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; }; DumpCache: PUBLIC ENTRY PROC = { ENABLE UNWIND => NULL; cnt: INT _ 0; IF disposedTiles#NIL THEN { lag: Tile _ disposedTiles; FOR tc: Tile _ disposedTiles.eN, tc.eN WHILE tc#NIL DO lag.eN _ NIL; lag _ tc; IF (cnt_cnt+1)>1000 THEN EXIT ENDLOOP; disposedTiles _ NIL }; IF disguiseCache#NIL THEN { lag: REF Disguise _ disguiseCache; cnt _ 0; FOR dc: REF Disguise _ NARROW[disguiseCache.hiddenValue], NARROW[dc.hiddenValue] WHILE dc # NIL DO lag.hiddenValue _ NIL; lag _ dc; IF (cnt_cnt+1)>1000 THEN EXIT ENDLOOP; disguiseCache _ NIL }; IF disposedTesselations#NIL AND disposedTesselations.rest#NIL THEN disposedTesselations.rest.rest _ NIL }; NewTile: ENTRY PROC RETURNS [tile: Tile] = { ENABLE UNWIND => NULL; tile _ InternalNewTile[]; }; InternalNewTile: INTERNAL PROC RETURNS [tile: Tile] = INLINE { IF disposedTiles#NIL THEN { tile _ disposedTiles; disposedTiles _ disposedTiles.eN; } ELSE tile _ NEW[TileRec]; }; DisposeTile: ENTRY PROC [tile: Tile] = { <<--caller must check that it is not a current tile>> <<--and cache the tile, this is faster than going through the garbage collector>> 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; }; NewDisguise: ENTRY PROC [hiddenValue: REF_NIL] RETURNS [disguise: REF Disguise] = { ENABLE UNWIND => NULL; IF disguiseCache#NIL THEN { disguise _ disguiseCache; disguiseCache _ NARROW[disguiseCache.hiddenValue]; } ELSE disguise _ NEW[Disguise]; disguise.hiddenValue _ hiddenValue; }; DisposeDisguise: ENTRY PROC [disguise: REF Disguise] = { ENABLE UNWIND => NULL; disguise.hiddenValue _ disguiseCache; disguiseCache _ disguise; }; SetupBorderTiles: ENTRY PROC [plane: Tesselation] = { eastSpace: Tile = InternalNewTile[]; centreSpace: Tile = InternalNewTile[]; eastSpace^ _ [ eN: northBuffer, nE: RtoP[eastLimit], sW: centreSpace, wS: RtoP[southLimit], pos: [allSpace.x2, allSpace.y1], value: guard ]; centreSpace^ _ [ eN: northBuffer, nE: RtoP[eastSpace], sW: westLimit, wS: RtoP[southLimit], pos: [allSpace.x1, allSpace.y1], value: NIL ]; plane.tileCount _ 1; plane.current _ centreSpace; plane.southEast _ eastSpace; }; disposedTesselations: LIST OF Tesselation _ NIL; ReturnDisposedTess: ENTRY PROC [] RETURNS [plane: Tesselation_NIL] = INLINE { ENABLE UNWIND => plane _ NIL; IF disposedTesselations#NIL THEN { plane _ disposedTesselations.first; disposedTesselations _ disposedTesselations.rest; }; }; DisposeTess: ENTRY PROC [plane: Tesselation] = INLINE { ENABLE UNWIND => disposedTesselations _ NIL; plane.data _ NIL; plane.stopFlag _ NIL; disposedTesselations _ CONS[plane, disposedTesselations]; }; NewTesselation: PUBLIC PROC [data: REF _ NIL, stopFlag: REF BOOL _ NIL] RETURNS [plane: Tesselation] = { plane _ ReturnDisposedTess[]; IF plane=NIL THEN { plane _ NEW[CStitching.TesselationRec_[current: NIL, southEast: NIL]]; SetupBorderTiles[plane]; <> }; plane.stopFlag _ (IF stopFlag=NIL THEN NEW[BOOL_FALSE] ELSE stopFlag); plane.data _ data; }; TrustedDisposeTesselation: PUBLIC PROC [plane: Tesselation] = { IF plane#NIL THEN { ResetTesselation[plane]; DisposeTess[plane]; } }; ResetTesselation: PUBLIC PROC [plane: Tesselation, stopFlag: REF BOOL_NIL] = { DisposeTileList: PROC [header: Tile] = INLINE { WHILE header#NIL DO t: Tile _ header; header _ header.eN; DisposeTile[t]; ENDLOOP; }; CacheIt: TileProc = { <<-- Depends on fact that Enumeration proceeds NE to SW, >> <<-- so eN ref may be clobbered by caching process.>> tile.value _ deleted; tile.eN _ header; header _ tile; }; header: Tile _ NIL; IF plane#NIL THEN { EnumerateArea[plane, maxSpace, CacheIt, NIL, deleted]; DisposeTileList[header]; SetupBorderTiles[plane]; IF stopFlag#NIL THEN plane.stopFlag _ stopFlag; }; }; EWCompatible: PROC [a, b: Tile] RETURNS [BOOL] = INLINE { <<--test whether tiles have same west border, same east border and same value>> RETURN [a.value=b.value AND a.pos.x=b.pos.x AND NE[a].pos.x=NE[b].pos.x] }; ChangeRect: PUBLIC PROC [plane: Tesselation, rect: Rect, new: REF ANY _ NIL] = { SplitEWRunning: PROC [rider: Tile, splitY, endX: Number] = { <<--split tiles, starting with rider, going eastwards>> <<--rider must intersect splitY horizontal line >> <<--splitY will belong to the north tiles>> <<--endX is first point not to be split>> <<--knows value to be inserted and might not split the last tile if already right value. ugh>> <<-->> <<--Invariants>> <<--Ia (tiles to the left of rider are handled) >> <<--Ib (while SEdge[rider]>splitY rider _ WS[rider] wouldnt change rider's left x coordinate)>> <<--at beginning Ia and Ib true because of parameters>> <<--go east>> WHILE WEdge[rider]> <<--go south until split line is hit>> WHILE SEdge[rider]>splitY DO rider _ WS[rider] ENDLOOP; --won't go left nor right! (Ib) <<--Ia and Ib and (rider touches or intersects split line)>> <<--split>> IF SEdge[rider]> IF EEdge[rider]> }; <<--I rider touches or intersects split line>> rider _ NE[rider]; --reinstalls Ia and Ib (Ib because old rider limits all WS..) ENDLOOP; }; tile: Tile; rect.x1 _ MAX[maxSpace.x1, rect.x1]; rect.x2 _ MIN[maxSpace.x2, rect.x2]; rect.y1 _ MAX[maxSpace.y1, rect.y1]; rect.y2 _ MIN[maxSpace.y2, rect.y2]; IF rect.x1>=rect.x2 OR rect.y1>=rect.y2 THEN RETURN; tile _ MyFindTile[plane.current, rect.x1, rect.y2]; <<-- tile containing nw corner (right north of area of interest)>> plane.current _ tile; SplitEWRunning[tile, rect.y2, rect.x2]; --north border SplitEWRunning[MyFindTile[plane.current, rect.x1, rect.y1], rect.y1, rect.x2]; --south border <<-- change values.>> tile _ MyFindTile[plane.current, rect.x1, rect.y2-1]; DO <<--I all northern tiles are already handled>> <<-- split out left part of tile if necessary.>> IF tile.value#new AND WEdge[tile]> IF EWCompatible[left, left.eN] THEN left _ NSMerge[plane, left, left.eN]; IF EWCompatible[left, WS[left]] THEN left _ NSMerge[plane, WS[left], left]; }; DO --loop rides tile eastwards and changes value until border is hit IF tile.value#new THEN { <<-- right border>> IF EEdge[tile]>rect.x2 THEN { right: Tile _ EWSplit[plane, tile, rect.x2].east; IF EWCompatible[right, right.eN] THEN right _ NSMerge[plane, right, right.eN]; IF EWCompatible[right, WS[right]] THEN right _ NSMerge[plane, WS[right], right]; }; tile _ MyChangeTile[plane, tile, new]; --returns northernmost tile if changed }; <<--I tile has value >> IF EEdge[tile]>=rect.x2 THEN EXIT; tile _ NE[tile]; WHILE SEdge[tile]>=rect.y2 DO tile _ WS[tile] ENDLOOP; -- EMM <<--I tile.s <=rect.y2 >> ENDLOOP; <<--I tile touches east border and all northern tiles are already handled>> IF WEdge[tile]>rect.x1 THEN ERROR; IF SEdge[tile]<=rect.y1 THEN EXIT; <<--set tile back up and left; remember, the northern tiles are merged already >> tile _ Below[tile, rect.x1]; ENDLOOP }; ChangeEnumerateArea: PUBLIC PROC [plane: Tesselation, rect: Rect, eachRect: RectProc, data: REF _ NIL, skip: REF] = { DisguiseTile: TileProc = { tile.value _ NewDisguise[tile.value]; }; ApplyFuncToTile: TileProc = { 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>> [] _ MyChangeTile[plane, tile, disguise.hiddenValue]; <<-- call user eachRect function>> IF disguise.hiddenValue#skip THEN eachRect[plane: plane, rect: clippedBB, oldValue: disguise.hiddenValue, data: data]; DisposeDisguise[disguise]; }; <<>> <<--ChangeEnumerateArea>> EnumerateArea[plane, rect, DisguiseTile, NIL, deleted]; EnumerateArea[plane, rect, ApplyFuncToTile, data, deleted]; }; ChangeTile: PUBLIC PROC [plane: Tesselation, tile: Tile, new: REF _ NIL] = TRUSTED { IF tile.value#new THEN [] _ MyChangeTile[plane, tile, new] }; MyChangeTile: PROC [plane: Tesselation, tile: Tile, new: REF] RETURNS [Tile] = { <<-- returns the northernmost tile intersecting the changed region. >> <<-- (there is exactly one such tile! maximal-EW-property)>> n: Number = NEdge[tile]; e: Number = EEdge[tile]; s: Number = SEdge[tile]; w: Number = WEdge[tile]; tWest, tEast, tNorth: Tile; IF tile.value=new THEN RETURN [tile]; tile.value _ new; <<-- restore maximal East-West strip property>> <<>> <<-- split up tiles that horizontally abut any of the tile's four corners, >> <<-- but extend beyond the corner in a North-South direction>> <<--northeast corner>> tEast _ NE[tile]; IF tEast.value=new AND NEdge[tEast]>n THEN [] _ NSSplit[plane, tEast, n]; <<--northwest corner>> tWest _ tile.eN; --east now but west soon WHILE WEdge[tWest]>=w DO tWest _ tWest.sW ENDLOOP; <<-- the tile with EEdge >= w but WEdge < w. >> <<-- In fact SEdge[tWest] < n holds only if EEdge = w>> IF tWest.value=new AND SEdge[tWest]> tWest _ tile.sW; IF tWest.value=new AND SEdge[tWest]> tEast _ WS[tile]; WHILE EEdge[tEast]<=e DO tEast _ NE[tEast] ENDLOOP; <<-- analogous to split of northwest corner.>> IF tEast.value=new AND NEdge[tEast]>s THEN [] _ NSSplit[plane, tEast, s]; <<>> <<-- convert the West and East adjacent tiles to maximal East-West strips>> <<-- run South to North along the West edge >> <<-- splitting North-South, merging East-West >> tWest _ tile.sW; WHILE NEdge[tWest]> IF tWest.value=new THEN tile _ EWMerge[plane, tWest, tile]; <<-- now any maximal-EW-property violations of tile are confined to its Eastern border. >> <<-- however, some merges at the northern and southern borders may be pending.>> <<>> <<-- run North to South along the East edge splitting North-South any tile to >> <<-- the East which abuts more than one new tile in the changed area.>> tEast _ NE[tile]; WHILE SEdge[tEast]>s DO tile _ tEast.sW; IF (tEast.value=new OR WS[tEast].value=new) AND SEdge[tile]> <<>> <<-- run South to North along the East edge >> <<-- splitting North-South, merging East-West; eventually merging North-South..>> tNorth _ tEast.sW; --not yet north.. WHILE NEdge[tNorth]<=s DO tNorth _ tNorth.eN ENDLOOP; DO tile _ tNorth; --current tile in area tNorth _ tile.eN; --now north of current tile only IF NE[tile].value=new THEN { IF tile.nE=tNorth.nE THEN [] _ NSSplit[plane, NE[tile], NEdge[tile]]; tile _ EWMerge[plane, tile, NE[tile]] }; IF EWCompatible[tile, WS[tile]] THEN tile _ NSMerge[plane, WS[tile], tile]; IF NEdge[tNorth]>n THEN EXIT ENDLOOP; IF EWCompatible[tile, tNorth] THEN [] _ NSMerge[plane, tile, tNorth]; RETURN [tile] }; IsEmpty: PUBLIC PROC [plane: Tesselation, rect: Rect, skip: REF ANY _ NIL] RETURNS [BOOL] = { <<-- Relies on the Maximal East-West strip property.>> rect.x1 _ MAX[maxSpace.x1, rect.x1]; rect.x2 _ MIN[maxSpace.x2, rect.x2]; rect.y1 _ MAX[maxSpace.y1, rect.y1]; rect.y2 _ MIN[maxSpace.y2, rect.y2]; IF rect.x1>rect.x2 OR rect.y1>rect.y2 THEN RETURN [TRUE]; plane.current _ MyFindTile[plane.current, rect.x1, rect.y1]; FOR tile: Tile _ plane.current, Above[tile, rect.x1] WHILE SEdge[tile]> tile: Tile; rect.x1 _ MAX[maxSpace.x1, rect.x1]; rect.x2 _ MIN[maxSpace.x2, rect.x2]; rect.y1 _ MAX[maxSpace.y1, rect.y1]; rect.y2 _ MIN[maxSpace.y2, rect.y2]; IF rect.x1>rect.x2 OR rect.y1>rect.y2 THEN RETURN [empty]; <<--find south west corner>> plane.current _ MyFindTile[plane.current, rect.x1, rect.y1]; FOR tile _ plane.current, Above[tile, rect.x1] DO IF SEdge[tile]>=rect.y2 THEN RETURN; -- plane is empty IF tile.value#skip OR EEdge[tile]> IF EEdge[tile]> tile _ MyFindTile[plane.current, rect.x2-1, rect.y1]; WHILE SEdge[tile]rect.x1 THEN { bBox.x2 _ MAX[bBox.x2, WEdge[tile]]; bBox.y2 _ NEdge[tile] }; tile _ Above[tile, rect.x2-1]; ENDLOOP; }; EnumerateArea: PUBLIC PROC [plane: Tesselation, rect: Rect, eachTile: TileProc, data: REF _ NIL, skip: REF] = { <<-- 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 ResetTesselation.>> <<-- Defn: b is a's child iff b.sW = a.>> IsChild: PROC [me: Tile, you: Tile] RETURNS [BOOL] = INLINE { RETURN [you.sW=me AND you.pos.y>rect.y1]; }; IsBrother: PROC [me: Tile, you: Tile] RETURNS [BOOL] = INLINE { RETURN [me.sW=you.sW AND you.pos.y>rect.y1]; }; tile, visit: Tile; doneSouthEastTile: BOOL _ FALSE; rect.x1 _ MAX[maxSpace.x1, rect.x1]; rect.x2 _ MIN[maxSpace.x2, rect.x2]; rect.y1 _ MAX[maxSpace.y1, rect.y1]; rect.y2 _ MIN[maxSpace.y2, rect.y2]; IF rect.x1>=rect.x2 OR rect.y1>=rect.y2 THEN RETURN; tile _ MyFindTile[plane.current, rect.x1, rect.y2]; <<-- 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 _ Below[tile, rect.x1]; plane.current _ tile; <<--a tile is visited only after all its children>> WHILE ~doneSouthEastTile DO seeking: {youth, experience, nothing} _ youth; --of tile DO IF seeking=youth THEN { child: Tile _ NE[tile]; WHILE SEdge[child]>=rect.y2 DO child _ WS[child] ENDLOOP; <<--if child is a child of tile then it is southernmost one>> IF IsChild[tile, child] AND WEdge[child]> visit _ 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 _ Below[tile, rect.x1] ELSE { IF EEdge[tile]>=rect.x2 THEN doneSouthEastTile _ TRUE ELSE { tile _ NE[tile]; WHILE SEdge[tile]>rect.y1 DO tile _ WS[tile] ENDLOOP; } } } ELSE { IF IsBrother[tile, WS[tile]] THEN { tile _ WS[tile]; --brother seeking _ youth } ELSE tile _ tile.sW; --father! }; IF visit.value#skip THEN eachTile[visit, data]; --must not fool tile IF seeking=nothing THEN EXIT ENDLOOP ENDLOOP; }; ListArea: PUBLIC PROC [plane: Tesselation, rect: Rect, skip: REF _ NIL] RETURNS [rl: LIST OF REF Region_NIL] = { PerTile: TileProc = { rl _ CONS[NEW[ Region _ [ [ MAX[WEdge[tile], rect.x1], MAX[SEdge[tile], rect.y1], MIN[EEdge[tile], rect.x2], MIN[NEdge[tile], rect.y2] ], tile.value ]], rl]; }; EnumerateArea[plane, rect, PerTile, NIL, skip]; }; EnumerateNeighborhood: PUBLIC PROC [plane: Tesselation, tile: Tile, eachTile: TileProc, data: REF _ NIL, skip: REF _ NIL] = BEGIN <> eastBound: Number ~ tile.EEdge; northBound: Number ~ tile.NEdge; westBound: Number ~ tile.WEdge; southBound: Number ~ tile.SEdge; FOR tileSouth: Tile _ tile.WS, tileSouth.NE WHILE tileSouth.WEdge < eastBound DO IF (tileSouth.value # skip) THEN eachTile [tileSouth, data] ENDLOOP; FOR tileWest: Tile _ tile.SW, tileWest.EN WHILE tileWest.SEdge < northBound DO IF (tileWest.value # skip) THEN eachTile [tileWest, data] ENDLOOP; FOR tileNorth: Tile _ tile.EN, tileNorth.SW WHILE tileNorth.EEdge > westBound DO IF (tileNorth.value # skip) THEN eachTile [tileNorth, data] ENDLOOP; FOR tileEast: Tile _ tile.NE, tileEast.WS WHILE tileEast.NEdge > southBound DO IF (tileEast.value # skip) THEN eachTile [tileEast, data] ENDLOOP END; -- EnumerateNeighborhood Below: PROC [tile: Tile, x: Number] RETURNS [t: Tile] = INLINE { <<-- assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)>> t _ WS[tile]; WHILE NE[t].pos.x<=x DO t _ NE[t] ENDLOOP; }; Above: PROC [tile: Tile, x: Number] RETURNS [t: Tile] = INLINE { <<-- assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)>> t _ tile.eN; WHILE t.pos.x>x DO t _ t.sW ENDLOOP; }; FindTile: PUBLIC PROC [plane: Tesselation, pos: Pos] RETURNS [tile: Tile] = { pos.x _ MIN[maxSpace.x2, pos.x]; pos.y _ MIN[maxSpace.y2, pos.y]; tile _ MyFindTile[current: plane.current, x: pos.x, y: pos.y]; IF tile.value=guard THEN ERROR; plane.current _ tile; }; MyFindTile: PROC [current: Tile, x, y: Number] RETURNS [Tile] = TRUSTED { <<--a-symmetric>> IF current.value=deleted THEN ERROR UseOfAlreadyDeletedTile; DO --south-- WHILE y=current.eN.pos.y DO current _ current.eN ENDLOOP; IF x=current.nE.pos.x THEN --east-- WHILE x>=current.nE.pos.x DO current _ LOOPHOLE[current.nE] ENDLOOP ELSE EXIT ENDLOOP; RETURN [current] }; EWSplit: PROC [plane: Tesselation, tile: Tile, x: Number] RETURNS [east: Tile] = { <<-- the East tile will be the new one.>> <<-- x is west point in new east tile.>> t: Tile; east _ NewTile[]; IF WEdge[tile]>=x OR EEdge[tile]<= x THEN ERROR; <<-- east starts out a replica of tile>> east^ _ tile^; plane.tileCount _ plane.tileCount + 1; <<-- Fix the tiles relative to each other.>> tile.nE _ RtoP[east]; east.sW _ tile; east.pos.x _ x; <<-- Fix North boundary>> t _ east.eN; WHILE t.pos.x>=x DO t.wS _ RtoP[east]; t _ t.sW ENDLOOP; tile.eN _ t; <<-- Fix East boundary>> t _ NE[east]; WHILE t.sW=tile DO t.sW _ east; t _ WS[t] ENDLOOP; <<-- Fix South boundary>> t _ Below[tile, x]; east.wS _ RtoP[t]; WHILE t.eN=tile DO t.eN _ east; t _ NE[t] ENDLOOP; RETURN [east] }; NSSplit: PROC [plane: Tesselation, tile: Tile, y: Number] RETURNS [north: Tile] = { <<-- the North tile will be the new one.>> <<-- y is south point of new north tile>> t: Tile; north _ NewTile[]; IF SEdge[tile]>=y OR NEdge[tile]<=y THEN ERROR; <<-- north starts out a replica of tile>> north^ _ tile^; plane.tileCount _ plane.tileCount + 1; <<-- Fix the tiles relative to each other.>> tile.eN _ north; north.wS _ RtoP[tile]; north.pos.y _ y; <<-- Fix East boundary>> t _ NE[north]; WHILE t.pos.y>=y DO t.sW _ north; t _ WS[t] ENDLOOP; tile.nE _ RtoP[t]; <<-- Fix North boundary>> t _ north.eN; WHILE t.wS=RtoP[tile] DO t.wS _ RtoP[north]; t _ t.sW ENDLOOP; <<-- Fix West boundary>> t _ tile.sW; WHILE t.eN.pos.y<=y DO t _ t.eN ENDLOOP; north.sW _ t; WHILE NE[t]=tile DO t.nE _ RtoP[north]; t _ t.eN ENDLOOP; RETURN [north] }; EWMerge: PROC [plane: Tesselation, tileW, tileE: Tile] RETURNS [Tile] = { <<-- 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>> IF tileE.sW#tileW OR NE[tileW]#tileE OR tileW.pos.y#tileE.pos.y OR tileW.eN.pos.y#tileE.eN.pos.y OR tileW.value#tileE.value THEN ERROR; <<-- Fix the tiles relative to each other.>> tileW.eN _ tileE.eN; tileW.nE _ tileE.nE; <<-- Fix North boundary>> FOR t: Tile _ tileW.eN, t.sW WHILE WS[t]=tileE DO t.wS _ RtoP[tileW] ENDLOOP; <<-- Fix East boundary>> FOR t: Tile _ NE[tileW], WS[t] WHILE t.sW=tileE DO t.sW _ tileW ENDLOOP; <<-- Fix South boundary>> FOR t: Tile _ WS[tileE], NE[t] WHILE t.eN=tileE DO t.eN _ tileW ENDLOOP; IF plane.current=tileE THEN plane.current _ tileW; DisposeTile[tileE]; plane.tileCount _ plane.tileCount - 1; RETURN [tileW]; }; NSMerge: PROC [plane: Tesselation, tileS, tileN: Tile] RETURNS [Tile] = { <<-- 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>> IF WS[tileN]#tileS OR tileS.eN#tileN OR tileS.pos.x#tileN.pos.x OR NE[tileS].pos.x#NE[tileN].pos.x OR tileS.value#tileN.value THEN ERROR; <<-- Fix the tiles relative to each other.>> tileS.nE _ tileN.nE; tileS.eN _ tileN.eN; <<-- Fix East boundary>> FOR t: Tile _ NE[tileS], WS[t] WHILE t.sW=tileN DO t.sW _ tileS ENDLOOP; <<-- Fix North boundary>> FOR t: Tile _ tileS.eN, t.sW WHILE WS[t]=tileN DO t.wS _ RtoP[tileS] ENDLOOP; <<-- Fix West boundary>> FOR t: Tile _ tileN.sW, t.eN WHILE NE[t]=tileN DO t.nE _ RtoP[tileS] ENDLOOP; IF plane.current=tileN THEN plane.current _ tileS; DisposeTile[tileN]; plane.tileCount _ plane.tileCount - 1; RETURN [tileS]; }; RtoP: PROC [r: Tile] RETURNS [LONG POINTER TO TileRec] ~ INLINE { TRUSTED { RETURN [LOOPHOLE[r]] } }; <> <> < NULL;>> <<>> <> <<-- Depends on fact that Enumeration proceeds NE to SW, >> <<-- so eN ref may be clobbered by caching process.>> <> <> <

> <<};>> <<>> <> <> <> <> <> <> <

> <> <> <<};>> <<>> <> <> <> <> <> <<};>> <<>> <> <> <> <<>> InitTesselationBorderTiles[]; END. <> <> <> <<>> <> <> <> <<>> <> <> <<>> <> <> <<>> <> <> <> <> <<>> <> <> <> <<>> <> <> <> <<>> <> <> <<>>