<> <> <<>> <> <> <> <> <> <> <> DIRECTORY Commander, CS, IO, Process, SafeStorage; CSImpl: CEDAR MONITOR IMPORTS Commander, CS, IO, Process, SafeStorage EXPORTS CS = BEGIN OPEN CS; UseOfAlreadyDeletedTile: ERROR = CODE; callErr: 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]]; cache: Tile _ NIL; InitTesselationBorderTiles: PROC = BEGIN <<-- 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 _ P[eastLimit]; eastLimit.eN _ northLimit; <<-- South-East>> southLimit.eN _ eastLimit; southLimit.nE _ P[eastLimit]; eastLimit.wS _ P[southLimit]; eastLimit.sW _ southLimit; <<-- North-West>> westLimit.nE _ P[northLimit]; westLimit.eN _ northLimit; northLimit.sW _ westLimit; northLimit.wS _ P[westLimit]; <<-- South-West>> southLimit.sW _ westLimit; westLimit.wS _ P[southLimit]; <<-- northBuffer>> northBuffer.eN _ northLimit; northBuffer.nE _ P[eastLimit]; northBuffer.sW _ westLimit; northBuffer.wS _ NIL; END; DumpCache: PUBLIC ENTRY PROC = BEGIN ENABLE UNWIND => NULL; IF cache#NIL THEN { lag: Tile _ cache; FOR tc: Tile _ cache.eN, tc.eN WHILE tc#NIL DO lag.eN _ NIL; lag _ tc ENDLOOP; cache _ NIL }; END; NewTile: ENTRY PROC RETURNS [tile: Tile] = BEGIN ENABLE UNWIND => NULL; tile _ InternalNewTile[]; END; InternalNewTile: INTERNAL PROC RETURNS [tile: Tile] = INLINE BEGIN IF cache#NIL THEN { tile _ cache; cache _ cache.eN; } ELSE tile _ NEW[TileRec]; END; 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>> BEGIN ENABLE UNWIND => NULL; tile.sW _ NIL; tile.nE _ tile.wS _ NIL; -- prevent potential circularity. tile.value _ deleted; tile.eN _ cache; cache _ tile; END; Setup: INTERNAL PROC [plane: Tesselation] = BEGIN eastSpace: Tile = InternalNewTile[]; centreSpace: Tile = InternalNewTile[]; eastSpace^ _ [ eN: northBuffer, nE: P[eastLimit], sW: centreSpace, wS: P[southLimit], pos: [allSpace.x2, allSpace.y1], value: guard]; centreSpace^ _ [ eN: northBuffer, nE: P[eastSpace], sW: westLimit, wS: P[southLimit], pos: [allSpace.x1, allSpace.y1], value: NIL]; plane^ _ [southEast: eastSpace, current: centreSpace, data: NIL, stopFlag: plane.stopFlag, tileCount: 1]; IF plane.stopFlag=NIL THEN plane.stopFlag _ NEW[BOOL_FALSE]; END; NewTesselation: PUBLIC ENTRY PROC [data: REF_NIL, stopFlag: REF BOOL_NIL] RETURNS [plane: Tesselation] = BEGIN plane _ NEW[CS.TesselationRec_[[], FALSE, NIL, NIL, 1, stopFlag, data]]; Setup[plane]; <<##SafeStorage.EnableFinalization[plane];>> END; ResetTesselation: PUBLIC PROC [plane: Tesselation] = <<--This is to help the garbage collector (by NILing all REFs).>> BEGIN CacheTileList: PROC [header: Tile] = { 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; }; MySetup: ENTRY PROC [plane: Tesselation] = { Setup[plane]; }; header: Tile _ NIL; IF plane#NIL THEN { EnumerateArea[plane, maxSpace, CacheIt, NIL, deleted]; CacheTileList[header]; MySetup[plane]; }; END; CompToN: PROC [t: Tile] RETURNS [BOOL] = INLINE { <<--tile is compatible with its north neighbour (except maybe range problems)>> RETURN [t.value=t.eN.value AND t.pos.x=t.eN.pos.x AND NE[t].pos.x=NE[t.eN].pos.x] }; ChangeRect: PUBLIC PROC [plane: Tesselation, rect: Rect, new: REF ANY _ NIL] = <<--we dont check left and right border with state>> <<--state.rect left and right must be pre-split>> BEGIN SplitHorizontal: PROC [plane: Tesselation, splitY, x1, x2: Number] = INLINE <<--only splits if value # new>> <<--split must be in legal range; x1> BEGIN tile: Tile _ Find[plane.current, x1, splitY-1]; <<--tile rides from west to east, containing the point below the split line>> plane.current _ tile; DO <<--Assert: tile.pos.x> IF NEdge[tile]=splitY THEN { tile _ NE[tile]; IF tile.pos.x>=x2 THEN EXIT; } ELSE IF tile.value=new THEN { IF EEdge[tile]>=x2 THEN EXIT; tile _ RightOf[tile, splitY-1]; } ELSE { [] _ NSSplit[plane, tile, splitY]; tile _ NE[tile]; IF tile.pos.x>=x2 THEN EXIT; } ENDLOOP END; <<>> <> <<--only splits if value # new>> <<--split must be in legal range; x1> <> <> <> <> <<--Assert: tile.pos.x> <> <<--correct but slowish: tile _ RightOf[tile, splitY]>> <<--east-west property tells: its faster to move eastwards>> <=x2 THEN RETURN;>> <> <> <> <=x2 THEN RETURN;>> <> <<}>> <> <=x2 THEN RETURN;>> <> <<}>> <> <> <> 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; IF plane.immute OR rect.x1plane.state.r.x2 OR rect.y2>plane.state.r.y2 THEN ERROR callErr; SplitHorizontal[plane, rect.y1, rect.x1, rect.x2]; SplitHorizontal[plane, rect.y2, rect.x1, rect.x2]; <<-- change values.>> <<-- tile containing nw corner neighbour (but inside area of interest)>> tile _ Find[plane.current, rect.x1, rect.y2-1]; DO <<--I tile touches west border>> <<--I all northern tiles are already handled>> <<-- split out left part of tile if necessary.>> IF tile.value#new AND WEdge[tile]> left: Tile; tile _ EWSplit[plane, tile, rect.x1].east; left _ tile.sW; <<-- make sure we keep outside tile in order NS-wise.>> IF CompToN[left] THEN left _ NSMerge[plane, left, left.eN]; IF CompToN[WS[left]] THEN IF WS[left].pos.y>=plane.state.r.y1 THEN [] _ 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 { <<--wont enter with e-w border problems>> right: Tile _ EWSplit[plane, tile, rect.x2].east; IF CompToN[right] THEN right _ NSMerge[plane, right, right.eN]; IF CompToN[WS[right]] THEN IF WS[right].pos.y>=plane.state.r.y1 THEN [] _ NSMerge[plane, WS[right], right]; }; tile _ RestrictedMyChangeTile[plane, tile, new]; --returns northernmost tile IF WEdge[tile]>rect.x1 THEN ERROR; }; <<--I tile has value >> IF EEdge[tile]>=rect.x2 THEN EXIT; tile _ NE[tile]; WHILE tile.pos.y>=rect.y2 DO tile _ WS[tile] ENDLOOP; -- EMM <<--I tile.s <=rect.y2 >> ENDLOOP; <<--I tile touches west border>> <<--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 _ BelowOf[tile, rect.x1]; ENDLOOP END; ChangeTile: PUBLIC PROC [plane: Tesselation, tile: Tile, new: REF _ NIL] = TRUSTED BEGIN IF plane.immute OR tile.pos.xplane.state.r.x2 OR EN[tile].pos.y>plane.state.r.y2 THEN ERROR callErr; [] _ ChangeTile[plane, tile, new]; END; RestrictedMyChangeTile: 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)>> <<-- immute-test and area-test done by caller>> <<-- restricts splits and joins to plane's state>> <<-- it is allowed to change the value to itself! that cleans up the upper part of the border>> BEGIN n: Number = NEdge[tile]; e: Number = EEdge[tile]; s: Number = SEdge[tile]; w: Number = WEdge[tile]; tWest, tEast, tNorth: Tile; <<>> <<--checks>> IF splane.state.r.x2 THEN IF s> <<>> <<-- split up tiles that horizontally abut any of the tile's four corners, >> <<-- but extend beyond the corner in a North-South direction>> <<>> <<--northwest corner treated with the west edge..>> <<--northeast corner>> tEast _ NE[tile]; IF tEast.value=new AND NEdge[tEast]>n THEN { IF EEdge[tEast]<=plane.state.r.x2 OR n>=plane.state.ys THEN [] _ NSSplit[plane, tEast, n]; }; <<>> <<--southwest corner>> tWest _ tile.sW; IF tWest.value=new AND SEdge[tWest]=plane.state.r.x1 OR s>=plane.state.yf THEN [] _ NSSplit[plane, tWest, s]; }; <<>> <<--southeast corner>> 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 { IF EEdge[tEast]<=plane.state.r.x2 OR s>=plane.state.ys 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; easy since tile is not yet split >> tWest _ tile.sW; WHILE tWest.pos.ySEdge[tile] THEN tile _ NSSplit[plane, tile, SEdge[tWest]]; IF NEdge[tWest]=NEdge[tile]>> IF NEdge[tWest]>NEdge[tile] THEN [] _ NSSplit[plane, tWest, NEdge[tile]]; [] _ EWMerge[plane, tWest, tile]; tile _ tWest; EXIT }; [] _ EWMerge[plane, tWest, NE[tWest]]; tWest _ tile.sW; }; ENDLOOP; <<-- now any maximal-EW-property violations of tile are confined to its Eastern border. >> <<-- NS merges at the northern and southern borders may be pending.>> <<>> <<-- run North to South along the East edge >> <<-- splitting inside (west of edge) North-South any tile necessary >> tEast _ NE[tile]; WHILE tEast.pos.y>s DO tile _ tEast.sW; IF (tEast.value=new OR WS[tEast].value=new) AND tile.pos.y=plane.state.ys) THEN [] _ NSSplit[plane, tile, tEast.pos.y]; tEast _ WS[tEast] ENDLOOP; <<--I SEdge[tEast]<=s>> <<>> <<-- run South to North along the East edge >> <<-- splitting outside (east)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 AND (EEdge[tile]=plane.state.ys) THEN { IF tile.nE=tNorth.nE THEN [] _ NSSplit[plane, NE[tile], NEdge[tile]]; tile _ EWMerge[plane, tile, NE[tile]] }; IF CompToN[WS[tile]] AND (SEdge[tile]>plane.state.r.y1) THEN tile _ NSMerge[plane, WS[tile], tile]; IF NEdge[tNorth]>n THEN EXIT ENDLOOP; IF CompToN[tile] THEN [] _ NSMerge[plane, tile, tNorth]; RETURN [tile] END; IsEmpty: PUBLIC PROC [plane: Tesselation, rect: Rect, skip: REF ANY _ NIL] RETURNS [BOOL] = <<-- relies on the Maximal East-West strip property.>> BEGIN 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 _ Find[plane.current, rect.x1, rect.y1]; FOR tile: Tile _ plane.current, AboveOf[tile, rect.x1] WHILE SEdge[tile]> BEGIN 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 _ Find[plane.current, rect.x1, rect.y1]; FOR tile _ plane.current, AboveOf[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 _ Find[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 _ AboveOf[tile, rect.x2-1]; ENDLOOP; END; ChangeEnumerateArea: PUBLIC PROC [plane: Tesselation, rect: Rect, eachRect: RectProc, 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.>> BEGIN IsChild: PROC [me: Tile, you: Tile] RETURNS [BOOL] = INLINE { <<--actually only childs not on the border>> RETURN [you.sW=me AND you.pos.y>rect.y1]; }; HasOldBrother: PROC [me: Tile] RETURNS [BOOL] = INLINE { <<--actually only brother not on the border>> RETURN [me.sW=WS[me].sW AND WS[me].pos.y>rect.y1]; }; CleanupUpperBorderOfTile: PROC [plane: Tesselation, tile: Tile] = INLINE { plane.current _ tile; [] _ RestrictedMyChangeTile[plane, tile, tile.value] }; val: REF; tile, visit: Tile; outer: State _ plane.state; ys, nextys: Number; doneSouthEastTile: BOOL _ FALSE; IF plane.immute THEN ERROR callErr; 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; IF rect.x1plane.state.r.x2 OR rect.y2>plane.state.r.y2 THEN ERROR callErr; PreSplit[plane, rect]; tile _ Find[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 _ BelowOf[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 _ RightOf[tile, rect.y2-1]; <<--if child is a child of tile then it is southernmost one>> IF IsChild[tile, child] THEN { IF WEdge[child]> ys _ nextys; visit _ tile; <<-- Is tile a border tile?>> IF tile.pos.x<=rect.x1 OR tile.pos.y<=rect.y1 THEN { <<-- Find next border tile, i.e. next tree root>> seeking _ nothing; IF tile.pos.y>rect.y1 THEN tile _ BelowOf[tile, rect.x1] ELSE { IF EEdge[tile]>=rect.x2 THEN doneSouthEastTile _ TRUE ELSE tile _ RightOf[tile, rect.y1]; } } ELSE { IF HasOldBrother[tile] THEN { tile _ WS[tile]; --brother seeking _ youth } ELSE { nextys _ tile.pos.y; tile _ tile.sW; --father! } }; val _ visit.value; plane.state.r _ BArea[visit, rect]; plane.state.ys _ ys; plane.state.yf _ IF rect.y1=plane.state.r.y1 THEN plane.state.r.y1 ELSE IF plane.state.r.x1>rect.x1 THEN NEdge[SW[visit]] ELSE rect.y2+1; --dont touch outside <<--if tile touches south border it is visited after its father...>> CleanupUpperBorderOfTile[plane, visit]; IF val#skip THEN eachRect[plane, plane.state.r, val, data]; --must not fool tile IF seeking=nothing THEN EXIT ENDLOOP ENDLOOP; plane.state _ outer; PostMerge[plane, rect]; END; BArea: PROC [t: Tile, r: Rect] RETURNS [Rect] = TRUSTED INLINE { <<--clipped rect of tile; (upper and right border exclusive)>> RETURN [[ x1: MAX[t.pos.x, r.x1], y1: MAX[t.pos.y, r.y1], x2: MIN[t.nE.pos.x, r.x2], y2: MIN[t.eN.pos.y, r.y2] ]] }; NSLineCleanup: PROC [plane: Tesselation, n, s, x0: Number] = <<--reeinstalls properties for all tiles touching the line>> BEGIN CanEWMerge: PROC [plane: Tesselation, tileW: Tile] RETURNS [BOOL] = INLINE <<--check whether in mutable region>> <<--doesnt check whether the height matches;>> BEGIN IF SEdge[tileW]plane.state.r.x2 THEN IF SEdge[tileW]> <<--tile looping, north to south>> tile: Tile _ Find[plane.current, x0, n]; WHILE NEdge[tile]>s DO next: Tile _ BelowOf[tile, x0]; IF WEdge[tile]=x0 THEN { <<--check for E-W merges>> tWest _ tile.sW; <<--tWest looping south to north in range of tile; eventually split southernmost tWest>> WHILE SEdge[tWest]NEdge[tile] THEN [] _ PNSSplit[plane, tWest, NEdge[tile]] ELSE IF NEdge[tile]>NEdge[tWest] THEN [] _ PNSSplit[plane, tile, NEdge[tWest]]; --north IF CanEWMerge[plane, tWest] THEN { next _ AboveOf[tile, x0]; <<--but we wont do this AboveOf a second time; so tile is visited at max twice>> [] _ EWMerge[plane, tWest, tile]; } ELSE next _ BelowOf[tile, x0]; --forwards to exit the outer loop EXIT; } ENDLOOP; }; tile _ next; ENDLOOP; plane.current _ tile; --speeds up later usage of east west line... <<--N-S merges>> <<--tile looping south to north>> DO IF SEdge[tile]>n THEN EXIT; IF WEdge[tile]=x0 THEN { tWest _ tile.sW; DO WHILE CompToN[tWest] DO tWest _ PNSMerge[plane, tWest, EN[tWest]] ENDLOOP; IF NEdge[tWest]<=NEdge[tile] THEN tWest _ EN[tWest] ELSE EXIT; ENDLOOP; }; IF CompToN[tile] THEN tile _ PNSMerge[plane, tile, EN[tile]] --north ELSE tile _ AboveOf[tile, x0]; ENDLOOP; END; EWLineCleanup: PROC [plane: Tesselation, w, e, y0: Number] = BEGIN tile: Tile _ Find[plane.current, e, y0-1]; DO IF CompToN[tile] THEN IF SEdge[tile]>=plane.state.r.y1 THEN [] _ NSMerge[plane, tile, EN[tile]]; tile _ LeftOf[tile, y0-1]; IF WEdge[tile]<=w THEN EXIT; ENDLOOP; END; PostMerge: PROC [plane: Tesselation, rect: Rect] = BEGIN NSLineCleanup[plane, rect.y2, rect.y1, rect.x1]; NSLineCleanup[plane, rect.y2, rect.y1, rect.x2]; EWLineCleanup[plane, rect.x1, rect.x2, rect.y1]; END; SplitNSLine: PROC [plane: Tesselation, splitX, y1, y2: Number] RETURNS [rider: Tile] = <<--splits top and bottom tiles horizontally>> <<--runs north to south splits other tiles vertically; without merges>> <<--splits including y1>> <<--at end: SEdge[rider]> BEGIN plane.current _ rider _ Find[plane.current, splitX, y2-1]; IF NEdge[rider]>y2 AND WEdge[rider]=y1 DO IF rider.pos.xy1 THEN IF rider.pos.x> <<--is that a good idea?>> BEGIN SplitEWLine: PROC [rider: Tile, endX, splitY: Number] RETURNS [Tile] = <<--runs west to east; without merges>> <<--assumes at begin: SEdge[rider]> <<--splits including endX>> BEGIN WHILE rider.pos.xsplitY THEN [] _ NSSplit[plane, rider, splitY]; rider _ NE[rider]; ENDLOOP; RETURN [rider]; END; <<>> <<--cut east border, nort to south>> tile: Tile _ SplitNSLine[plane, rect.x1, rect.y1, rect.y2]; --north to south at the west border tile _ SplitEWLine[tile, rect.x2, rect.y1]; --west to east at the south border [] _ SplitNSLine[plane, rect.x2, rect.y1, rect.y2]; --north to south at the east border END; 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.>> BEGIN IsChild: PROC [me: Tile, you: Tile] RETURNS [BOOL] = INLINE { <<--actually only childs not on the border>> RETURN [you.sW=me AND you.pos.y>rect.y1]; }; HasOldBrother: PROC [me: Tile] RETURNS [BOOL] = INLINE { <<--actually only brother not on the border>> RETURN [me.sW=WS[me].sW AND WS[me].pos.y>rect.y1]; }; immute: BOOL; tile: 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; immute _ plane.immute; plane.immute _ TRUE; tile _ Find[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 _ BelowOf[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 _ RightOf[tile, rect.y2-1]; <<--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 _ BelowOf[tile, rect.x1] ELSE { IF EEdge[tile]>=rect.x2 THEN doneSouthEastTile _ TRUE ELSE tile _ RightOf[tile, rect.y1]; } } ELSE { IF HasOldBrother[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; plane.immute _ immute; END; ListArea: PUBLIC PROC [plane: Tesselation, rect: Rect, skip: REF _ NIL] RETURNS [rl: LIST OF REF Region_NIL] = BEGIN 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]; END; LeftOf: PROC [tile: Tile, y: Number] RETURNS [t: Tile] = INLINE <<-- assumes y is within tile (i.e. SEdge[tile] <= x & NEdge[tile] > x)>> BEGIN t _ SW[tile]; WHILE NEdge[t]<=y DO t _ EN[t] ENDLOOP; END; RightOf: PROC [tile: Tile, y: Number] RETURNS [t: Tile] = INLINE <<-- assumes y is within tile (i.e. SEdge[tile] <= x & NEdge[tile] > x)>> BEGIN t _ NE[tile]; WHILE t.pos.y>y DO t _ WS[t] ENDLOOP; END; BelowOf: PROC [tile: Tile, x: Number] RETURNS [t: Tile] = INLINE <<-- assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)>> BEGIN t _ WS[tile]; WHILE NE[t].pos.x<=x DO t _ NE[t] ENDLOOP; END; AboveOf: PROC [tile: Tile, x: Number] RETURNS [t: Tile] = INLINE <<-- assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)>> BEGIN t _ tile.eN; WHILE t.pos.x>x DO t _ t.sW ENDLOOP; END; FindTile: PUBLIC PROC [plane: Tesselation, pos: Pos] RETURNS [tile: Tile] = BEGIN pos.x _ MIN[maxSpace.x2, pos.x]; pos.y _ MIN[maxSpace.y2, pos.y]; tile _ Find[current: plane.current, x: pos.x, y: pos.y]; IF tile.value=guard THEN ERROR; plane.current _ tile; END; Find: PROC [current: Tile, x, y: Number] RETURNS [Tile] = <<--a-symmetric>> TRUSTED BEGIN 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] END; 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.>> TRUSTED BEGIN t: Tile; <<--checks>> IF SEdge[tile]plane.state.r.x2 THEN IF SEdge[tile]=x OR EEdge[tile]<= x THEN ERROR; east _ NewTile[]; <<-- east starts out a replica of tile>> east^ _ tile^; plane.tileCount _ plane.tileCount + 1; <<-- Fix the tiles relative to each other.>> tile.nE _ LOOPHOLE[east]; east.sW _ tile; east.pos.x _ x; <<-- Fix North boundary>> t _ east.eN; WHILE t.pos.x>=x DO t.wS _ LOOPHOLE[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 _ BelowOf[tile, x]; east.wS _ LOOPHOLE[t]; WHILE t.eN=tile DO t.eN _ east; t _ NE[t] ENDLOOP; RETURN [east] END; PNSSplit: PROC [plane: Tesselation, tile: Tile, y: Number] RETURNS [north: Tile] = <<--protected NS split>> BEGIN IF SEdge[tile]plane.state.r.x2 THEN IF SEdge[tile]> <<-- y is south point of new north tile>> TRUSTED BEGIN t: Tile; <<--check>> IF SEdge[tile]plane.state.r.x2 THEN IF y=y OR NEdge[tile]<=y THEN ERROR; north _ NewTile[]; <<-- 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 _ LOOPHOLE[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 _ LOOPHOLE[t]; <<-- Fix North boundary>> t _ north.eN; WHILE t.wS=P[tile] DO t.wS _ LOOPHOLE[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 _ LOOPHOLE[north]; t _ t.eN ENDLOOP; RETURN [north] END; PEWMerge: PROC [plane: Tesselation, tileW, tileE: Tile] RETURNS [Tile] = <<--assmes a tile does not intersect both, left and right>> <<--returns east if not merged>> BEGIN IF SEdge[tileW]plane.state.r.x2 THEN IF SEdge[tileE]> <<-- The caller must assure that tileW.value=tileE.value and that the tiles really>> <<-- do have a common border of equal length.>> TRUSTED BEGIN <<--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; <<>> IF SEdge[tileW]plane.state.r.x2 THEN IF SEdge[tileW]> <<-- 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 _ LOOPHOLE[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]; END; PNSMerge: PROC [plane: Tesselation, tileS, tileN: Tile] RETURNS [Tile] = <<--returns north tile if not merged>> BEGIN IF SEdge[tileS]plane.state.r.x2 THEN IF SEdge[tileS]> <<-- the caller must assure that tileS.value=tileN.value and that the tiles really>> <<-- do have a common border of equal length.>> TRUSTED BEGIN <<--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; IF SEdge[tileS]plane.state.r.x2 THEN IF SEdge[tileS]> 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 _ LOOPHOLE[tileS] ENDLOOP; <<-- Fix West boundary>> FOR t: Tile _ tileN.sW, t.eN WHILE NE[t]=tileN DO t.nE _ LOOPHOLE[tileS] ENDLOOP; IF plane.current=tileN THEN plane.current _ tileS; DisposeTile[tileN]; plane.tileCount _ plane.tileCount - 1; RETURN [tileS]; END; P: PROC [r: Tile] RETURNS [LONG POINTER TO TileRec] ~ TRUSTED INLINE { RETURN [LOOPHOLE[r]] }; Load: Commander.CommandProc = { cmd.out.PutRope["CornerStiching loaded\n"]; }; FinalizeTesselation: ENTRY PROC [plane: REF CS.TesselationRec] = BEGIN ENABLE UNWIND => NULL; InternalDispose: TileProc = <<-- Depends on fact that Enumeration proceeds NE to SW, >> <<-- so eN ref may be clobbered by caching process.>> BEGIN tile.value _ deleted; tile.eN _ header; header _ tile; END; header: Tile _ NIL; IF plane.current#NIL THEN EnumerateArea[plane, maxSpace, InternalDispose, NIL, deleted]; plane.current _ plane.southEast _ NIL; plane.data _ NIL; WHILE header#NIL DO t: Tile _ header; header _ header.eN; t.sW _ t.eN _ NIL; t.nE _ t.wS _ NIL; ENDLOOP; END; <> <> <> <> <> <> <> <<>> <> <> <> <<>> InitTesselationBorderTiles[]; Commander.Register[key: "CornerStiching", proc: Load, doc: "loads the CornerStiching"]; END. <> <> <> <<>> <> <> <> <<>> <> <> <<>> <> <> <<>> <> <> <> <> <<>> <> <>