[_CD4_]<datools7.0>CStitching4>CStitchingImpl.mesa!2

CStitchingImpl.mesa

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 December 19, 1986 2:14:23 pm PST

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];

--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;

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

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, eachTile: 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 call-back procedure eachTile is called.

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;

--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] = {

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.