Package VASSAL.tools.qtree

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)

navigate

public void navigate(QNode<T> node,
 QFunc<T> func,
 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.