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
abstract class PointTreeNode extends Object implements Cloneable, Serializable
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 as Object arrays instead of using a more object-oriented approach with some TreeNodeLeaf class.
Since:
1.1
Version:
1.1

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    (package private) static final class 
    PointTreeNode.Default
    Default implementation of PointTreeNode when no specialized class is available.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final long
    serialVersionUID
    For cross-version compatibility.

  • Constructor Summary

    Constructors
    Constructor
    Description
    PointTreeNode()
    Constructs an initially empty PointTree node.

  • Method Summary

    Modifier and Type
    Method
    Description
    (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
    newInstance()
    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
    setChild(int quadrant, Object child)
    Sets the node's quadrant/octant to the specified child.

    Methods inherited from class java.lang.Object

    equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      For cross-version compatibility.
      See Also:

  • Constructor Details

    • PointTreeNode

      PointTreeNode()
      Constructs an initially empty PointTree 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 by quadrant(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 by quadrant(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

      abstract Object getChild(int quadrant)
      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 another PointTreeNode for reducing the number of objects created.
      Any other kind of object is an error.
      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.

    • setChild

      abstract void setChild(int quadrant, Object child)
      Sets the node's quadrant/octant to the specified child. The child value must be one of the types documented in getChild(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

      abstract PointTreeNode newInstance()
      Creates a new instance of the same class than this node.

    • clone

      protected Object clone()
      Returns a clone of this node. This is invoked when creating a copy of PointTree. The clone is a semi-deep clone: all children that are instances of PointTreeNode shall be cloned recursively, but instances of Object[] (the leaf nodes) are not cloned. It is safe to not clone the Object[] arrays because PointTree uses a copy-on-write strategy when data need to be modified.
      Overrides:
      clone in class Object