DIRECTORY CD USING [Number, Rect], CDBasics USING [empty] ; SXQuadTree: CEDAR DEFINITIONS = BEGIN Rectangle: TYPE = RECORD [ interestBound: CD.Rect, -- Bounding box of region which Rectangle influences. dimDecr: RectDelta, -- Decrement to be applied to interestBound give actual dimension. nodeInformation: REF ANY -- CircuitNode for conductive primitive rects, instance for cells. ]; Rectangles: TYPE = LIST OF REF Rectangle _ NIL; RectDelta: TYPE = RECORD [ dx1, dy1, dx2, dy2: [0..256) ]; AreaSplit: TYPE = {north, south, east, west}; QuadTreeRoot: TYPE = RECORD [ size: CD.Rect _ CDBasics.empty, geometry: REF QuadTree _ NIL, private: Rectangles _ NIL -- hack for internal use ]; QuadTree: TYPE = RECORD [ boxes: Rectangles, midX, midY: CD.Number _ 0, subTrees: ARRAY AreaSplit OF REF QuadTree _ ALL[NIL] -- Note SubTrees overlap! North or South is prefered over East or West distribution. ]; Dimension: PROCEDURE [r: REF Rectangle] RETURNS [CD.Rect] = INLINE { RETURN [[x1: r.interestBound.x1+r.dimDecr.dx1, y1: r.interestBound.y1+r.dimDecr.dy1, x2: r.interestBound.x2-r.dimDecr.dx2, y2: r.interestBound.y2-r.dimDecr.dy2]]; }; PerRectProc: TYPE = PROCEDURE [r: REF Rectangle, data: REF ANY]; Create: PROCEDURE [quadTree: QuadTreeRoot] RETURNS [newQuadTree: QuadTreeRoot]; Store: PROCEDURE [quadTree: QuadTreeRoot, rect: REF Rectangle] RETURNS [newQuadTree: QuadTreeRoot]; Enumerate: PROCEDURE [quadTree: QuadTreeRoot, clipRect: CD.Rect, PerRect: PerRectProc, data: REF ANY _ NIL] END. ŒSXQuadTree.mesa: Spinifex flavour of Quad Trees Copyright c 1985 by Xerox Corporation. All rights reserved. Written by Beretta, June 3, 1985 2:54:18 pm PDT Last Edited by: Beretta, June 29, 1985 7:49:05 pm PDT Last edited by: Christian Jacobi, November 17, 1986 5:28:51 pm PST -- A space saving Hack. Allows interest bloats of no more than 255/Lambda. Also requires strict containment of Rectangle's dimension in its InterestBoundary. Hack. When all rectangles are known, also the bounding box of their union is known, and the Quad Tree can be created a least. Stores a rectangle for subsequent insertion into a Quad Tree. Interim procedure. Κ˜šœ/™/Jšœ<™