CornerStitching.mesa
Copyright © 1983, 1985 by Xerox Corporation. All rights reserved.
Written by Mark Shand, September 12, 1983 11:40 pm
Last Edited by: McCreight, November 28, 1983 5:53 pm
Last Edited by: Jacobi, February 24, 1984 12:14 pm
Last Edited by: Shand, June 1, 1984 2:20:32 pm PDT
Last Edited by: Jacobi, September 30, 1985 2:17:17 pm PDT
DIRECTORY
D2Basic USING [Number, Pos, Rect];
CornerStitching: CEDAR DEFINITIONS =
-- Types.
Number: TYPE = D2Basic.Number;
Pos: TYPE = D2Basic.Pos;
CsRect:
TYPE = D2Basic.Rect;
--WARNING: Conventions are different from D2Basic and ChipNDale:
--In CornerStitching, lower left border is inclusive; upper right border is exclusive.
--(In D2Basic all borders are inclusive).
D2ToCS:
PROC [r: D2Basic.Rect]
RETURNS [CsRect] =
INLINE {
r.x2 ← r.x2-1; r.y2 ← r.y2-1; RETURN [r]
};
CSToD2:
PROC [r: CsRect]
RETURNS [D2Basic.Rect] =
INLINE {
r.x2 ← r.x2+1; r.y2 ← r.y2+1; RETURN [r]
};
--Transfers may be ommited if done consistently
Tile:
TYPE =
RECORD [
--readonly please
-- Always leave tile in second direction,
-- i.e en = NorthEast corner, facing North; ne faces East.
en, sw: REF Tile ← NIL,
ne, ws: LONG POINTER TO Tile ← NIL,
pos: Pos,
value: REF ← NIL -- NIL for space tiles
];
-- Corner stitching is too circular for the current implementation of Cedar safestorage (too many tiles are pinned) so some of the stitches are pointers (idea courtesy of Mark Brown). We are careful to stitch in a way that connects every tile through a chain of REFs to the southeast tile, which we hang on to in the Tesselation record. Actually there is one benefit, now to free a Tesselation you only need drop this REF.
Tesselation:
TYPE =
RECORD [
southEast, current: REF Tile ←, --readonly
tilesInTesselationCount: INT ← 1, --readonly
stopFlag: REF BOOL,
data: REF
];
--use only NewTesselation to create Tesselations
--data: reserved for clients
--stopFlag: reserved for clients
--All procedures sharing a tesselation must be synchrounized by caller; Cornerstitching does not monitor clients on the same tesselation.
-- Tile Worlds.
NewTesselation:
PROC [data:
REF ←
NIL, stopFlag:
REF
BOOL ←
NIL]
RETURNS [
REF Tesselation];
--creates a new tesselation
FreeTesselation:
PROC [plane:
REF Tesselation, freeCache:
BOOL ←
TRUE];
-- returns the memory. Helps the garbage collector.
-- freeCache: implicite call of DumpCache
DumpCache:
PROC;
--returns cached memory used global for all tesselations
-- Modifying Tile Worlds.
ChangeRect:
PROC [plane:
REF Tesselation, rect: CsRect, newValue:
REF ←
NIL];
-- Change the rect having newValue as tile value
ChangeTile:
PROC [plane:
REF Tesselation, tile:
REF Tile, newValue:
REF ←
NIL];
-- Change a tile; fast if the tesselation does not need to be tiled differently
FuncChangeRect:
PROC [plane:
REF Tesselation, rect: CsRect, perTile: PerTileChangeProc, data:
REF ←
NIL];
-- Change the rect.
-- For each tile in the rect (independent of previous value) call "perTile";
-- data is passed through to "perTile".
-- perTile is allowed to change or even querry the plane inside rect only.
-- (While FuncChangeRect is in progress some tiles may have temporary different values)
PerTileChangeProc: TYPE = PROC [plane: REF Tesselation, rect: CsRect, oldValue: REF, data: REF];
-- Enumeration routines.
TileAt:
PROC [plane:
REF Tesselation, pos: Pos]
RETURNS [
REF Tile];
--finds the tile which contains the point at pos
PerTileProc: TYPE = PROC [tile: REF Tile, data: REF];
EnumerateArea:
PROC [plane:
REF Tesselation, rect: CsRect, perTile: PerTileProc, data:
REF ←
NIL, skipValue:
REF ←
NIL];
--Enumerates all the tiles covering points of rect in the tesseleation plane.
--You must not change any tile value while an enumeration; the enumeration
-- may get fooled otherwise. You may call EnumerateArea recursively.
--data: passed through to the perTile procedure.
--skipValue: tiles with value skipValue will be ignored and not enumerated. If you
-- want every tile, set skipValue to some value you know no tile has (e.g. NEW[INT]).
-- In EnumerateArea the order of enumeration is well defined. A tile appears in the enumeration immediately after the last of its children. Where tileA is defined to be a child of tileB iff its sw stitch points to tileB. Children are ordered such that the southernmost is the last. For tiles touching the western and southern borders these rules do not apply, these tiles are parent-less. Such tiles appear at some point after all the parent-less tiles touching touching a given parent-less tile's northern and western borders have been enumerated.
ListArea:
PROC [plane:
REF Tesselation, rect: CsRect, skipValue:
REF ←
NIL]
RETURNS [
LIST
OF
REF Region];
--Returns a list of regions describing the area rect in the tesselation plane.
--Regions with tile value skipValue are not returned.
Region: TYPE = RECORD [rect: CsRect, value: REF]; -- value NIL for space tiles
-- Stepping from Tile to Tile.
-- Coordinates increase from south to north, and west to east. All tile worlds are bordered by tile at 'infinity' (i.e. INT.FIRST or INT.LAST), so bounded searches never need worry about tile = NIL. The tiles at infinity are not stitched to tiles in the Tesselation, rather they are stitched to each other in the manner of the bevelled edges of a picture frame. The meanings of the Stepping routines are as follows ...
-- ENorthNeighbour — eastern most tile to the north
-- NEastNeighbour — northern most tile to the east
-- WSouthNeighbour — western most tile to the south
-- SWestNeighbour — southern most tile to the west
ENorthNeighbour:
PROC [tile:
REF Tile]
RETURNS [
REF Tile] =
INLINE {
RETURN [tile.en]
};
NEastNeighbour:
PROC [tile:
REF Tile]
RETURNS [
REF Tile] =
INLINE {
TRUSTED { RETURN [LOOPHOLE[tile.ne]] }
};
WSouthNeighbour:
PROC [tile:
REF Tile]
RETURNS [
REF Tile] =
INLINE {
TRUSTED { RETURN [LOOPHOLE[tile.ws]] }
};
SWestNeighbour:
PROC [tile:
REF Tile]
RETURNS [
REF Tile] =
INLINE {
RETURN [tile.sw]
};
-- Tile Enquiries
Value:
PROC [tile:
REF Tile]
RETURNS [
REF
ANY] =
INLINE {
RETURN [tile.value]
};
Area:
PROC [tile:
REF Tile]
RETURNS [CsRect] =
INLINE {
RETURN [[WestEdge[tile], SouthEdge[tile], EastEdge[tile], NorthEdge[tile]]]
};
NorthEdge: PROC [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.en.pos.y]};
EastEdge: PROC [t: REF Tile] RETURNS [Number] = INLINE {TRUSTED { RETURN [t.ne.pos.x] }};
SouthEdge: PROC [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.pos.y]};
WestEdge: PROC [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.pos.x]};
-- Area Enquiries.
all: CsRect = [Number.FIRST, Number.FIRST, Number.LAST, Number.LAST];
AreaEmpty:
PROC [plane:
REF Tesselation, rect: CsRect ← all, skipValue:
REF ←
NIL]
RETURNS [
BOOL];
--returns whether or not rect in plane has only tiles with value skipValue.
ContentsBound:
PROC [plane:
REF Tesselation, rect: CsRect ← all, skipValue:
REF ←
NIL]
RETURNS [bBox: CsRect];
-- returns a minimal bounding box for non-skipValue tiles in rect
END.