QuadTree.mesa
Copyright Ó 1992 by Xerox Corporation. All rights reserved.
Greene, August 14, 1989 5:47:01 pm PDT
DIRECTORY
Vector;
QuadTree: CEDAR DEFINITIONS =
BEGIN
BoundingBox: TYPE = RECORD[lowerLeft, upperRight: Vector.VEC];
InternalVEC: TYPE = RECORD[x, y: CARDINAL];
InternalBoundingBox: TYPE = RECORD[lowerLeft, upperRight: InternalVEC];
QT: TYPE = REF QTRec;
QTRec: TYPE;
QTItem: TYPE = REF QTItemRec;
QTItemRec:
TYPE =
RECORD [
size: InternalBoundingBox,
data: REF ANY
];
Create:
PROC [universe: BoundingBox]
RETURNS [tree:
QT];
Client must define the "universe" at creation time. The universe should be large enough to contain all the bounding boxes of items that will be inserted in the tree. It generally does not hurt for the universe to be too large, except that the depth of the quad tree is limited to 16 levels.
Insert:
PROC [tree:
QT, itemSize: BoundingBox, itemData:
REF
ANY, locked:
BOOL ¬
FALSE];
The "itemSize" is scaled according to the universe and stored in the "QTItem" in Cardinal form. If the "itemSize" is larger than the universe the itemSize will be clipped without warning, making bugs hard to catch (try using the celtics break package on QuadTreeImpl.ScaleVec to see the amount of clipping). Locking is optional (see discussion below).
PerItemProc:
TYPE =
PROC [item: QTItem]
RETURNS [quit:
BOOLEAN ¬
FALSE];
Quit = TRUE stops the enumeration.
Enumerate:
PROC [tree:
QT, region: BoundingBox,
PerItem: PerItemProc, quanta:
CARD ¬
LAST[
CARD], locked:
BOOL ¬
FALSE];
Enumerate all items whose bounding box overlaps "region." (Items may, of course, have different shapes than boxes, in which case it is the client's responsibility to further refine the selection inside the PerItem proc.) The items are normally enumerated in prefix order of their location in the quad tree. If "quanta" is less than infinity, then the prefix order is modified so that no more than quanta items from one quad tree node are used per traversal of the tree (after multiple traversals all items are enumerated as before). This tends to give a more even spacial enumeration. Locking is optional except when quanta is less than infinity (see discussion below).
Destroy:
PROC [tree:
QT,
PerItem: PerItemProc ¬
NIL];
Nil's all internal pointers. Performs PerItem on each item, and ignores the return value. Locking is always true.
. . . Locking . . .
The package does not yet have full read-write locking. The safest use of the package is to lock everything. The current locking structure is designed for a specific application (CensusMap) that needs simultaneous unlocked inserts and enumerates in parallel with one, long-running, locked enumeration. This leaves a slight probability that enumerates will miss items due to tree rearrangements, but no errors will occur as a result of simultaneous operations.
END.