Class RTreeNode

All Implemented Interfaces:
Serializable, Cloneable, Emptiable, org.opengis.geometry.Envelope
Direct Known Subclasses:
SpecializableTransform.SubArea

public class RTreeNode extends GeneralEnvelope
Placeholder for a RTree. This simple implementation is not designed for scalability or performance. This class is there for minimal service, to be replaced in some future Apache SIS version by a more sophisticated tree. Current version of this class is okay for small trees where big nodes are added before small nodes.

A RTreeNode instance is used as the root of the tree. Children nodes are stored as a linked list (the list is implemented by the sibling field, which reference the next element in the list).

Possible evolution: a future version could avoid extending GeneralEnvelope. Instead, we could provide abstract contains(…) methods and let subclasses define them, with possibly more efficient implementations. We would still need an implementation that delegate to GeneralEnvelope since that class has the advantage of handling envelopes crossing the anti-meridian.
Since:
1.1
Version:
1.1
See Also:
  • Field Details

    • serialVersionUID

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

      private RTreeNode parent
      The parent, or null if none.
      See Also:
    • firstChild

      private RTreeNode firstChild
      The first node fully included in this code, or null if none. If non-null, that node and all its siblings shall be fully included in this RTreeNode. The child may contain other children, thus forming a tree from this wider node to smaller nodes.
      See Also:
    • sibling

      private RTreeNode sibling
      The next node having the same parent than this node. This is used for creating a linked list of nodes that are the children of the parent.
      Design note: an RTreeNode children array instead of firstChild + sibling would be more intuitive. But the use of linked list avoid one level of indirection and is one less object to create for each node. The gain may be negligible with a few hundreds nodes, but a future version of this class may target much more numerous nodes.
  • Constructor Details

    • RTreeNode

      public RTreeNode(org.opengis.geometry.Envelope area)
      Creates a new node for the given envelope.
      Parameters:
      area - the region covered by this node.
  • Method Details

    • getParent

      public final RTreeNode getParent()
      Returns the parent of this node, or null if none.
      Returns:
      the parent of this node, or null if none.
    • getChildren

      public final List<RTreeNode> getChildren()
      Returns the immediate children of this node, or an empty list if none.
      Returns:
      the immediate children of this node.
    • walk

      public static void walk(RTreeNode node, Consumer<? super RTreeNode> action)
      Executes the given action on the given node, all its children and all its siblings.
      Parameters:
      node - the node on which to execute the action, or null if none.
      action - the action to execute.
    • addNode

      public final void addNode(RTreeNode node)
      Adds the given node to the tree having this node as the root. This method assumes that this node or its siblings are likely to contain the nodes given to this method. This method will work even if this assumption does not hold, but the tree will be inefficient in such case.

      A "professional" R-Tree would make a better effort for creating a balanced tree here. Current version of this class uses a simple algorithm, okay for small trees where big nodes are added before small nodes. This is not a good general purpose R-Tree.

      Parameters:
      node - the node to add to this tree. If this node has sibling, they will be added too.
      See Also:
    • tryAddChild

      private boolean tryAddChild(RTreeNode candidate)
      Tries to add a child. This method checks if the given candidate is fully included in this RTreeNode. The given node may have children but shall not have any sibling, because this method does not check if the siblings would also be included in this node.
      Parameters:
      candidate - the single node (without sibling) to add as a child if possible.
      Returns:
      whether the given node has been added.
    • finish

      public final RTreeNode finish()
      Finishes the construction of the tree. This method should be invoked only on the instance on which addNode(RTreeNode) has been invoked. It performs the following tasks:
      1. Verify that all nodes have the same CRS or null CRS. An exception is thrown if incompatible CRS are found. This method does not verify the number of dimensions; this check should have been done by the caller.
      2. Set the CRS of all nodes to the common value found in previous step.
      3. Ensure that the tree has a single root, by creating a synthetic parent if necessary.
      Returns:
      the root of the tree, which is this if this node has no sibling.
    • locate

      public static RTreeNode locate(RTreeNode node, org.opengis.geometry.DirectPosition pos)
      Returns the node that contains the given position, or null if none. The given node does not need to be the root of the tree; it can be any node. This method will check that node first. If it does not contain the position, then this method goes up in the parent nodes.

      If consecutive positions are close to each other, then a good strategy is to give to this method the most recently used node.

      Parameters:
      node - any node in the tree. Should be node most likely to contain the position.
      pos - the position of the node to locate, or null if none.
      Returns:
      the smallest node containing the given position, or null if none.
    • hashCode

      public int hashCode()
      Returns a hash code value based on the this node and its children, ignoring the parent and the siblings.
      Overrides:
      hashCode in class ArrayEnvelope
      Returns:
      a hash code value for this node and its children.
    • equals

      public boolean equals(Object obj)
      Compares this node with the given object for equality, ignoring the parent and the siblings.
      Overrides:
      equals in class ArrayEnvelope
      Parameters:
      obj - the object to compare with this node.
      Returns:
      whether the two objects are of the same class, have equal envelope and equal children list.
    • formatTo

      protected String formatTo(Formatter formatter)
      Formats this envelope as a "DOMAIN" element (non-standard).
      Overrides:
      formatTo in class AbstractEnvelope
      Parameters:
      formatter - the formatter where to format the inner content of this envelope.
      Returns:
      the pseudo-WKT keyword, which is "Box" for this element.
      See Also:
    • toString

      public String toString()
      Returns a string representation of this node and its children as a tree. This method is for debugging purposes.
      Overrides:
      toString in class ArrayEnvelope
      Returns:
      a string representation of this node and all its children.
    • toTree

      public final TreeTable toTree()
      Returns a representation of this node and its children as a tree. This is mostly for debugging purposes.
      Returns:
      a tree representation of this node and all its children.
    • toTree

      private void toTree(TreeTable.Node addTo)
      Adds this node and its children to the given node. This method invokes itself recursively.