Package org.apache.sis.index.tree
Class PointTreeNode
java.lang.Object
org.apache.sis.index.tree.PointTreeNode
- All Implemented Interfaces:
Serializable
,Cloneable
- Direct Known Subclasses:
PointTreeNode.Default
,QuadTreeNode
A node in a
PointTree
which is the parent of other nodes. The number of child nodes depends
on the number of dimensions of the tree: 4 children with two-dimensional QuadTree,
8 children with three-dimensional Octree, etc.
The child node can be another PointTreeNode
if that node is itself the parent of more nodes.
Otherwise (i.e. if the child node is leaf) the child is an instance of Object[]
.
Features of arbitrary types are stored in Object[]
arrays. Those arrays should be small:
if the number of elements in a leaf exceeds a maximal capacity specified by the PointTree
,
then the leaf is replaced by a new PointTreeNode
and the Object[]
content
is distributed between the new child nodes.
Addition of new features in Object[]
arrays uses a copy-on-write strategy
in order to keep memory usage minimal (a tree may have thousands of small arrays) and for making
easier to ensure thread-safety during concurrent read/write operations.
Design note
Trees may have huge amount of nodes. For that reason, the nodes should contain as few fields as possible. We should also avoid classes that are just wrappers around arrays. This is the reason why leaf nodes are stored directly asObject
arrays instead of using a more object-oriented approach with some
TreeNodeLeaf
class.- Since:
- 1.1
- Version:
- 1.1
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static final class
Default implementation ofPointTreeNode
when no specialized class is available. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final long
For cross-version compatibility. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) abstract void
clear()
Removes all elements from this node.protected Object
clone()
Returns a clone of this node.(package private) static void
enterQuadrant
(double[] region, int quadrant) Modifies in place the specified for describing the coordinates of the specified quadrant.(package private) static double
factor
(int quadrant, int dimension) Returns 0.5 if the given quadrant is in the East/North/Up/Future side, or -0.5 if in the West/South/Down/Past side.(package private) abstract Object
getChild
(int quadrant) Returns the child of this node that resides in the specified quadrant/octant.(package private) abstract PointTreeNode
Creates a new instance of the same class than this node.(package private) static int
quadrant
(double[] point, double[] region) Returns the quadrant/octant relative to the given point.(package private) abstract void
Sets the node's quadrant/octant to the specified child.
-
Field Details
-
serialVersionUID
private static final long serialVersionUIDFor cross-version compatibility.- See Also:
-
-
Constructor Details
-
PointTreeNode
PointTreeNode()Constructs an initially emptyPointTree
node.
-
-
Method Details
-
quadrant
static int quadrant(double[] point, double[] region) Returns the quadrant/octant relative to the given point. Each bit specifies the relative position for a dimension. For (x, y, z, t) coordinates, the pattern is:- Bit 0 is the relative position of x coordinate: 0 for East and 1 for West.
- Bit 1 is the relative position of y coordinate: 0 for North and 1 for South.
- Bit 2 is the relative position of z coordinate: 0 for up and 1 for down.
- Bit 3 is the relative position of t coordinate: 0 for future and 1 for past.
- etc. for any additional dimensions.
- Parameters:
point
- data (x, y, …) coordinate.region
- region of current node, as the center in first half and size in second half.- Returns:
- an identification of the quadrant where the given point is located.
-
enterQuadrant
static void enterQuadrant(double[] region, int quadrant) Modifies in place the specified for describing the coordinates of the specified quadrant.- Parameters:
region
- region of current node, as the center in first half and size in second half.quadrant
- the quadrant as computed byquadrant(double[], double[])
.
-
factor
static double factor(int quadrant, int dimension) Returns 0.5 if the given quadrant is in the East/North/Up/Future side, or -0.5 if in the West/South/Down/Past side.- Parameters:
quadrant
- the quadrant as computed byquadrant(double[], double[])
.dimension
- the dimension index: 0 for x, 1 for y, etc.
-
clear
abstract void clear()Removes all elements from this node.- See Also:
-
getChild
Returns the child of this node that resides in the specified quadrant/octant. The return value can be null or an instance of one of those two classes:- Another
PointTreeNode
if the node in a quadrant/octant is itself a parent of other children. Object[]
if the node in a quadrant/octant is a leaf. In such case, the array contains elements. We do not wrap the leaf in anotherPointTreeNode
for reducing the number of objects created.
- Parameters:
quadrant
- quadrant/octant of child to get.- Returns:
- child in the specified quadrant/octant.
- Throws:
IndexOutOfBoundsException
- if the specified quadrant/octant is out of bounds.
- Another
-
setChild
Sets the node's quadrant/octant to the specified child. Thechild
value must be one of the types documented ingetChild(int)
.- Parameters:
quadrant
- quadrant/octant where the child resides.child
- child of this node in the specified quadrant/octant.- Throws:
IndexOutOfBoundsException
- if the specified quadrant/octant is out of bounds.
-
newInstance
Creates a new instance of the same class than this node. -
clone
Returns a clone of this node. This is invoked when creating a copy ofPointTree
. The clone is a semi-deep clone: all children that are instances ofPointTreeNode
shall be cloned recursively, but instances ofObject[]
(the leaf nodes) are not cloned. It is safe to not clone theObject[]
arrays becausePointTree
uses a copy-on-write strategy when data need to be modified.
-