CStitchingImpl.mesa
Copyright Ó 1983, 1986 by Xerox Corporation. All rights reserved.
Written by Shand, September 12, 1983 11:40 pm PDT
Last Edited by: McCreight, November 28, 1983 5:53 pm
Last Edited by: Jacobi, February 23, 1984 3:59 pm
Last Edited by: Shand, August 6, 1984 4:16:51 am PDT
Last Edited by: Beretta, February 13, 1985 11:46:26 am PST
gbb May 26, 1987 2:04:24 pm PDT
Last edited by: Christian Jacobi, November 4, 1986 2:17:58 pm PST
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𡤌nt+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𡤌nt+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];
SafeStorage.EnableFinalization[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]<endX
DO
--Ia and Ib
--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]<splitY
THEN {
--this second test prevents splitting tiles outside area of interest which might have to be remerged later (but ChangeRect wont do it, laying outside)
IF EEdge[rider]<endX
OR rider.value#new
--left edge said must split--
THEN
rider ← NSSplit[plane, rider, splitY];
--I rider touches or intersects split line
};
--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]<rect.x1
THEN {
left: Tile;
tile ← EWSplit[plane, tile, rect.x1].east;
left ← tile.sW;
-- make sure we keep outside tile in order NS-wise.
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]<n THEN [] ← NSSplit[plane, tWest, n];
--southwest corner
tWest ← tile.sW;
IF tWest.value=new AND SEdge[tWest]<s 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 [] ← 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]<n
DO
IF tWest.value#new AND tWest.eN.value#new THEN tWest ← tWest.eN
ELSE {
tile ← NSSplit[plane, tile, NEdge[tWest]];
IF tWest.value=new THEN [] ← EWMerge[plane, tWest, NE[tWest]];
tWest ← tile.sW;
}
ENDLOOP;
-- tile is the northernmost strip in the changed area.
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]<SEdge[tEast]
THEN
[] ← NSSplit[plane, tile, SEdge[tEast]];
tEast ← WS[tEast]
ENDLOOP;
--I SEdge[tEast]<=s
-- 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]<rect.y2
DO
IF tile.value#skip OR EEdge[tile]<rect.x2 THEN RETURN [FALSE]
ENDLOOP;
RETURN [TRUE]
};
BBox:
PUBLIC
PROC [plane: Tesselation, rect: Rect, skip:
REF ←
NIL]
RETURNS [bBox: Rect ← empty] = {
-- relies on the Maximal East-West strip property.
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]<rect.x2 THEN EXIT
ENDLOOP;
bBox.y1 ← MAX[SEdge[tile], rect.y1];
WHILE SEdge[tile]<rect.y2
DO
IF tile.value#skip THEN {bBox.x1 ← rect.x1; EXIT};
-- else the east edge of tile must abut a non-skip tile (Maximal East-West)
IF EEdge[tile]<rect.x2 AND EEdge[tile]<bBox.x1 THEN bBox.x1 ← EEdge[tile];
tile ← Above[tile, rect.x1];
ENDLOOP;
--find north east corner by going up starting at the south east corner
tile ← MyFindTile[plane.current, rect.x2-1, rect.y1];
WHILE SEdge[tile]<rect.y2
DO
IF tile.value#skip
THEN {
bBox.x2 ← rect.x2;
bBox.y2 ← NEdge[tile]
}
ELSE
IF WEdge[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]<rect.x2
THEN {
tile ← child;
LOOP
}
ELSE seeking ← experience --all childs of tile are handled
};
--NOT seeking youth!
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, eachTileS, eachTileW, eachTileN, eachTileE: TileProc, data:
REF ←
NIL, skip:
REF ←
NIL] ~
BEGIN
Enumerates the tiles neighboring tile in canonical order (positive orientation from the southwestern vertex). On each such tile whose value is different from skip, the appropriate call-back procedure eachTileX is called.
eastBound: Number ~ tile.EEdge;
northBound: Number ~ tile.NEdge;
westBound: Number ~ tile.WEdge;
southBound: Number ~ tile.SEdge;
IF (eachTileS #
NIL)
THEN
FOR tileSouth: Tile ← tile.
WS, tileSouth.
NE
WHILE tileSouth.WEdge < eastBound
DO
IF (tileSouth.value # skip) THEN eachTileS [tileSouth, data]
ENDLOOP;
IF (eachTileW #
NIL)
THEN
FOR tileWest: Tile ← tile.
SW, tileWest.
EN
WHILE tileWest.SEdge < northBound
DO
IF (tileWest.value # skip) THEN eachTileW [tileWest, data]
ENDLOOP;
IF (eachTileN #
NIL)
THEN
FOR tileNorth: Tile ← tile.
EN, tileNorth.
SW
WHILE tileNorth.EEdge > westBound
DO
IF (tileNorth.value # skip) THEN eachTileN [tileNorth, data]
ENDLOOP;
IF (eachTileE #
NIL)
THEN
FOR tileEast: Tile ← tile.
NE, tileEast.
WS
WHILE tileEast.NEdge > southBound
DO
IF (tileEast.value # skip) THEN eachTileE [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.pos.y DO current ← LOOPHOLE[current.wS] ENDLOOP;
--north-- WHILE y>=current.eN.pos.y DO current ← current.eN ENDLOOP;
IF x<current.pos.x
THEN
--west--
WHILE x<current.pos.x DO current ← current.sW ENDLOOP
ELSE
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]] }
};
Just drop it
FinalizeTesselation: ENTRY PROC [plane: CStitching.Tesselation] = {
ENABLE UNWIND => NULL;
InternalDispose: 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.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;
};
FinalizerProcess: PROC[fooFQ: SafeStorage.FinalizationQueue] = {
DO
foo: CStitching.Tesselation = NARROW[SafeStorage.FQNext[fooFQ]];
FinalizeTesselation[foo];
ENDLOOP
};
fooFQ: SafeStorage.FinalizationQueue = SafeStorage.NewFQ[];
SafeStorage.EstablishFinalization[CODE[CStitching.TesselationRec], 0, fooFQ];
TRUSTED {Process.Detach[FORK FinalizerProcess[fooFQ]]};
InitTesselationBorderTiles[];
END.
Edited on February 8, 1985 4:40:46 pm PST, by Jacobi
Formatting
MyFindTile completely rewritten
Edited on September 30, 1985 1:43:22 pm PDT, by Jacobi
Correct comments when which procedure is valid included in definition
EnumerateArea and ListArea made two procedures whith simpler parameters
Edited on December 12, 1985 6:28:29 pm PST, by Jacobi
maxSpace introduced,
Edited on January 14, 1986 7:07:36 pm PST, by Jacobi
finalization introduced
Edited on January 17, 1986 4:06:17 pm PST, by Jacobi
comments, invariants, shorter,
bug correction in ChangeTile,
Below, WS, NE introduced
Edited on March 18, 1986 5:51:41 pm PST, by Jacobi
better names,
better parameters
gbb December 19, 1986 2:12:57 pm PST
Implemented EnumerateNeighborhood.
changes to: EnumerateNeighborhood: new.
Edited on March 20, 1987 5:27:12 pm PST, by Jacobi
TrustedDisposeTesselation: new procedure.
gbb May 26, 1987 2:02:56 pm PDT
Allow to enumerate the neighbourhood of a tile using a different call-back procedure along each edge.
changes to: EnumerateNeighborhood