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: Jacobi, January 20, 1986 4:13:45 pm PST

Last Edited by: Beretta, February 13, 1985 11:46:26 am PST

Commander, CS, IO, Process, SafeStorage;

IMPORTS Commander, CS, IO, Process, SafeStorage

EXPORTS CS =

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

PrivateRec: TYPE = RECORD[notused: REF];

guard: REF = NEW[PrivateRec←[$CSGuard]];

deleted: REF = NEW[PrivateRec←[$CSDeleted]];

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

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

-- South-East

-- North-West

-- South-West

-- northBuffer

END;

BEGIN

ENABLE UNWIND => NULL;

IF cache#NIL THEN {

END;

BEGIN

ENABLE UNWIND => NULL;

tile ← InternalNewTile[];

END;

BEGIN

IF cache#NIL THEN {

ELSE tile ← NEW[TileRec];

END;

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

BEGIN

eastSpace: Tile = InternalNewTile[];

centreSpace: Tile = InternalNewTile[];

eastSpace^ ← [

centreSpace^ ← [

plane^ ← [southEast: eastSpace, current: centreSpace, data: NIL, stopFlag: plane.stopFlag, tileCount: 1];

IF plane.stopFlag=NIL THEN plane.stopFlag ← NEW[BOOL←FALSE];

END;

BEGIN

plane ← NEW[CS.TesselationRec←[[], FALSE, NIL, NIL, 1, stopFlag, data]];

Setup[plane];

##SafeStorage.EnableFinalization[plane];

END;

--This is to help the garbage collector (by NILing all REFs).

BEGIN

CacheTileList: PROC [header: Tile] = {

CacheIt: TileProc = {

MySetup: ENTRY PROC [plane: Tesselation] = {

header: Tile ← NIL;

IF plane#NIL THEN {

END;

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

};

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

SplitHorizontal: PROC [plane: Tesselation, splitY, x1, x2: Number] = INLINE

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.x1<plane.state.r.x1 OR rect.y1<plane.state.r.y1 OR rect.x2>plane.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

END;

TRUSTED BEGIN

IF plane.immute OR tile.pos.x<plane.state.r.x1 OR tile.pos.y<plane.state.r.y1 OR NE[tile].pos.x>plane.state.r.x2 OR EN[tile].pos.y>plane.state.r.y2 THEN ERROR callErr;

[] ← ChangeTile[plane, tile, new];

END;

-- 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 s<plane.state.r.y1 THEN ERROR;

IF w<plane.state.r.x1 THEN

IF e>plane.state.r.x2 THEN

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

--northwest corner treated with the west edge..

--northeast corner

tEast ← NE[tile];

IF tEast.value=new AND NEdge[tEast]>n THEN {

--southwest corner

tWest ← tile.sW;

IF tWest.value=new AND SEdge[tWest]<s THEN {

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

-- 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.y<n DO

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

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

IF CompToN[tile] THEN [] ← NSMerge[plane, tile, tNorth];

RETURN [tile]

END;

-- 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]<rect.y2 DO

RETURN [TRUE]

END;

-- relies on the Maximal East-West strip property.

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

bBox.y1 ← MAX[SEdge[tile], rect.y1];

WHILE SEdge[tile]<rect.y2 DO

--find north east corner by going up starting at the south east corner

tile ← Find[plane.current, rect.x2-1, rect.y1];

WHILE SEdge[tile]<rect.y2 DO

END;

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

HasOldBrother: PROC [me: Tile] RETURNS [BOOL] = INLINE {

CleanupUpperBorderOfTile: PROC [plane: Tesselation, tile: Tile] = INLINE {

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.x1<plane.state.r.x1 OR rect.y1<plane.state.r.y1 OR rect.x2>plane.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

plane.state ← outer;

PostMerge[plane, rect];

END;

--clipped rect of tile; (upper and right border exclusive)

RETURN [[

};

--reeinstalls properties for all tiles touching the line

BEGIN

CanEWMerge: PROC [plane: Tesselation, tileW: Tile] RETURNS [BOOL] = INLINE

tWest: Tile ← NIL;

--E—W merges

--tile looping, north to south

tile: Tile ← Find[plane.current, x0, n];

WHILE NEdge[tile]>s DO

plane.current ← tile; --speeds up later usage of east west line...

--N-S merges

--tile looping south to north

DO

END;

BEGIN

tile: Tile ← Find[plane.current, e, y0-1];

DO

END;

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;

--splits top and bottom tiles horizontally

--runs north to south splits other tiles vertically; without merges

--splits including y1

--at end: SEdge[rider]<y1; rider below or right of (splitX, y1)

BEGIN

plane.current ← rider ← Find[plane.current, splitX, y2-1];

IF NEdge[rider]>y2 AND WEdge[rider]<splitX THEN

WHILE rider.pos.y>=y1 DO

IF NEdge[rider]>y1 THEN

RETURN [rider];

END;

--don't wory about maximum stripes

--is that a good idea?

BEGIN

SplitEWLine: PROC [rider: Tile, endX, splitY: Number] RETURNS [Tile] =

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

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

HasOldBrother: PROC [me: Tile] RETURNS [BOOL] = INLINE {

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

plane.immute ← immute;

END;

BEGIN

PerTile: TileProc = {

EnumerateArea[plane, rect, PerTile, NIL, skip];

END;

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

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

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

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

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;

--a-symmetric

TRUSTED BEGIN

IF current.value=deleted THEN ERROR UseOfAlreadyDeletedTile;

DO

RETURN [current]

END;

-- 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.y1 THEN ERROR;

IF WEdge[tile]<plane.state.r.x1 THEN

IF EEdge[tile]>plane.state.r.x2 THEN

IF WEdge[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;

--protected NS split

BEGIN

IF SEdge[tile]<plane.state.r.y1 THEN RETURN [tile];

IF WEdge[tile]<plane.state.r.x1 THEN

IF EEdge[tile]>plane.state.r.x2 THEN

RETURN [NSSplit[plane, tile, y]];

END;

-- the North tile will be the new one.

-- y is south point of new north tile

TRUSTED BEGIN

t: Tile;

--check

IF SEdge[tile]<plane.state.r.y1 THEN ERROR;

IF WEdge[tile]<plane.state.r.x1 THEN

IF EEdge[tile]>plane.state.r.x2 THEN

IF SEdge[tile]>=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;

--assmes a tile does not intersect both, left and right

--returns east if not merged

BEGIN

IF SEdge[tileW]<plane.state.r.y1 THEN RETURN [tileE];

IF WEdge[tileW]<plane.state.r.x1 THEN

IF EEdge[tileE]>plane.state.r.x2 THEN

RETURN [EWMerge[plane, tileW, tileE]]

END;

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

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.y1 THEN ERROR;

IF WEdge[tileW]<plane.state.r.x1 THEN

IF EEdge[NE[tileW]]>plane.state.r.x2 THEN

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

--returns north tile if not merged

BEGIN

IF SEdge[tileS]<plane.state.r.y1 THEN RETURN [tileN];

IF WEdge[tileS]<plane.state.r.x1 THEN

IF EEdge[tileS]>plane.state.r.x2 THEN

RETURN [NSMerge[plane, tileS, tileN]]

END;

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

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.y1 THEN ERROR;

IF WEdge[tileS]<plane.state.r.x1 THEN

IF EEdge[tileS]>plane.state.r.x2 THEN

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

RETURN [LOOPHOLE[r]]

};

cmd.out.PutRope["CornerStiching loaded\n"];

};

BEGIN

ENABLE UNWIND => NULL;

InternalDispose: TileProc =

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

END;

BEGIN

DO

END;

Formatting

Find completely rewritten

Correct comments when which procedure is valid included in definition

EnumerateArea and ListArea made two procedures whith simpler parameters

maxSpace introduced,

finalization introduced

comments, invariants, shorter,

bug correction in ChangeTile,

BelowOf, WS, NE introduced

New algorithm for ChangeEnumerateArea