<> <> <> <> <> 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 [ <<-- A space saving Hack. Allows interest bloats of no more than 255/Lambda. Also requires strict containment of Rectangle's dimension in its InterestBoundary.>> 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.