Class QuadTree<T>

java.lang.Object
VASSAL.tools.qtree.QuadTree<T>
All Implemented Interfaces:
Cloneable
Direct Known Subclasses:
VassalMapQuadTree
public class QuadTree<T> extends Object implements Cloneable
Datastructure: A point Quad Tree for representing 2D data. Each region has the same ratio as the bounds for the tree.

The implementation currently requires pre-determined bounds for data as it can not rebalance itself to that degree.

  • Constructor Summary

    Constructors
    Constructor
    Description
    QuadTree()
     
    QuadTree(double minX, double minY, double maxX, double maxY)
    Constructs a new quad tree.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Removes all items from the tree.
    QuadTree<T>
    clone()
    Clones the quad-tree and returns the new instance.
    boolean
    contains(double x, double y)
    Returns true if the point at (x, y) exists in the tree.
    QNode<T>
    find(QNode<T> node, double x, double y)
    Finds a leaf node with the same (x, y) coordinates as the target point, or null if no point exists.
    T
    get(double x, double y, T opt_default)
    Gets the value of the point at (x, y) or null if the point is empty.
    int
    getCount()
     
    QPoint<T>[]
    getKeys()
    Returns an array containing the coordinates of each point stored in the tree.
    QNode<T>
    getRootNode()
    Returns a reference to the tree's root node.
    List<T>
    getValues()
    Returns a list containing all values stored within the tree.
    boolean
    isEmpty()
     
    void
    navigate(QNode<T> node, QFunc<T> func, double xmin, double ymin, double xmax, double ymax)
     
    T
    remove(double x, double y)
    Removes a point from (x, y) if it exists.
    QPoint<T>[]
    searchIntersect(double xmin, double ymin, double xmax, double ymax)
     
    QPoint<T>[]
    searchWithin(double xmin, double ymin, double xmax, double ymax)
     
    void
    set(double x, double y, T value)
    Sets the value of an (x, y) point within the quad-tree.
    void
    setRootNode(QNode<T> root)
     
    void
    traverse(QNode<T> node, QFunc<T> func)
    Traverses the tree depth-first, with quadrants being traversed in clockwise order (NE, SE, SW, NW).

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • QuadTree

      public QuadTree(double minX, double minY, double maxX, double maxY)
      Constructs a new quad tree.

    • QuadTree

      public QuadTree()

  • Method Details

    • getRootNode

      public QNode<T> getRootNode()
      Returns a reference to the tree's root node. Callers shouldn't modify nodes, directly. This is a convenience for visualization and debugging purposes.
      Returns:
      {Node} The root node.

    • setRootNode

      public void setRootNode(QNode<T> root)

    • set

      public void set(double x, double y, T value)
      Sets the value of an (x, y) point within the quad-tree.

    • get

      public T get(double x, double y, T opt_default)
      Gets the value of the point at (x, y) or null if the point is empty.
      Returns:
      {*} The value of the node, the default value if the node doesn't exist, or undefined if the node doesn't exist and no default has been provided.

    • remove

      public T remove(double x, double y)
      Removes a point from (x, y) if it exists.
      Returns:
      {T} The value of the node that was removed, or null if the node doesn't exist.

    • contains

      public boolean contains(double x, double y)
      Returns true if the point at (x, y) exists in the tree.
      Returns:
      {boolean} Whether the tree contains a point at (x, y).

    • isEmpty

      public boolean isEmpty()
      Returns:
      {boolean} Whether the tree is empty.

    • getCount

      public int getCount()
      Returns:
      {number} The number of items in the tree.

    • clear

      public void clear()
      Removes all items from the tree.

    • getKeys

      public QPoint<T>[] getKeys()
      Returns an array containing the coordinates of each point stored in the tree.
      Returns:
      {Array.} Array of coordinates.

    • getValues

      public List<T> getValues()
      Returns a list containing all values stored within the tree.
      Returns:
      {List} The values stored within the tree.

    • searchIntersect

      public QPoint<T>[] searchIntersect(double xmin, double ymin, double xmax, double ymax)

    • searchWithin

      public QPoint<T>[] searchWithin(double xmin, double ymin, double xmax, double ymax)

    • clone

      public QuadTree<T> clone()
      Clones the quad-tree and returns the new instance.
      Overrides:
      clone in class Object
      Returns:
      {QuadTree} A clone of the tree.

    • traverse

      public void traverse(QNode<T> node, QFunc<T> func)
      Traverses the tree depth-first, with quadrants being traversed in clockwise order (NE, SE, SW, NW). The provided function will be called for each leaf node that is encountered.

    • find

      public QNode<T> find(QNode<T> node, double x, double y)
      Finds a leaf node with the same (x, y) coordinates as the target point, or null if no point exists.
      Returns:
      {QuadTree.Node} The leaf node that matches the target, or null if it doesn't exist.