Class NodeIterator.Cursor<E>
- Enclosing class:
NodeIterator<E>
PointTreeNode
.
The starting point is PointTree.root
. A new NodeIterator.Cursor
instance is created
for each level when the node at next level is itself a parent of at least two nodes
(if there is only one child node, then this implementation takes a shortcut).-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final long[]
Masks for clearing the bits of all quadrants that do not intersect the search region on the left side.(package private) PointTreeNode
The node for which to iterate over elements.private NodeIterator.Cursor
<E> The cursor that created this cursor, ornull
if none.(package private) long
Bitmask of quadrants/octants on which to iterate.private final double[]
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) final void
Computes a bitmask of all quadrants/octants that intersect the search area.(package private) final NodeIterator.Cursor
<E> Marks thisNodeIterator.Cursor
as available for recycling and returns its parent.(package private) final void
moveDown
(int q) Changes the state of thisCursor
for getting elements in the specified quadrant/octant.(package private) final NodeIterator.Cursor
<E> push
(NodeIterator<E> it, int q) Creates a newCursor
for getting element arrays in the node quadrant/octant, without changing the state of thisCursor
.
-
Field Details
-
parent
The cursor that created this cursor, ornull
if none. If non-null, we will continue iteration with that parent after thisNodeIterator.Cursor
finished to return all element arrays.If this
NodeIterator.Cursor
instance is not used anymore (for now) and is made available for recycling, then this field is instead used for storing the next recyclable instance that may be used after this one, with no child-parent relationship. -
node
PointTreeNode nodeThe node for which to iterate over elements. Only the quadrants/octants identified by thequadrants
bitmask will be traversed. -
quadrants
long quadrantsBitmask of quadrants/octants on which to iterate. Quadrants/octants are iterated from rightmost bit to leftmost bit. Bits are cleared when the corresponding quadrant/octant become the current one. A value of 0 means that there are no more quadrants to iterate for the node.Note: we take "quadrant" name from QuadTree, but this algorithm can actually be used with more dimensions.
- See Also:
-
region
private final double[] region -
CLEAR_MASKS
private static final long[] CLEAR_MASKSMasks for clearing the bits of all quadrants that do not intersect the search region on the left side. For example, for x dimension, this is the mask to apply if thexmin <= cx
condition is false. In this exampleCLEAR_MASKS[0]
clears the bits of all quadrants on the West side, which are quadrants 1, 3, 5, etc.The index in this array is the dimension in which the quadrant do not intersect the search region. The length of this array should be equal to
PointTree.MAXIMUM_DIMENSIONS
.
-
-
Constructor Details
-
Cursor
Cursor(double[] region) Creates a new cursor. It is caller responsibility to initialize thenode
field, theparent
field if a parent exists, and to invokefindIntersections(NodeIterator)
.
-
-
Method Details
-
findIntersections
Computes a bitmask of all quadrants/octants that intersect the search area. This method must be invoked afterregion
values changed.- Parameters:
it
- the iterator which defines the area of interest.
-
push
Creates a newCursor
for getting element arrays in the node quadrant/octant, without changing the state of thisCursor
. This method is invoked when there is a need to iterate in two more more children, in which case we cannot yet discard the information contained in thisCursor
instance.Caller is responsible to update the
node
field after this method call and to invokefindIntersections(NodeIterator)
.- Parameters:
it
- the enclosing iterator.q
- the quadrant/octant in which to iterate.- Returns:
- the cursor to use for getting element arrays in the specified quadrant/octant.
-
moveDown
final void moveDown(int q) Changes the state of thisCursor
for getting elements in the specified quadrant/octant. This method is invoked when there is no need to keep currentCursor
information anymore, because there are no other quadrants/octants than the specified one in which to iterate.Caller is responsible to update the
node
field after this method call and to invokefindIntersections(NodeIterator)
.- Parameters:
q
- the quadrant/octant in which to iterate.
-
getParentAndRecycle
Marks thisNodeIterator.Cursor
as available for recycling and returns its parent.- Parameters:
it
- the enclosing iterator.- Returns:
- the parent of this
Cursor
, ornull
if none.
-