public class VPTree<E extends VPPoint>
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
static int |
DEFAULT_BIN_SIZE
The default node capacity (32 points) for nodes in this tree.
|
Constructor and Description |
---|
VPTree()
Constructs a new, empty vp-tree with a default node capacity.
|
VPTree(java.util.Collection<E> points)
Constructs a new vp-tree that contains (and indexes) all of the points in
the given collection.
|
VPTree(java.util.Collection<E> points,
int nodeCapacity)
Constructs a new vp-tree that contains (and indexes) all of the points in
the given collection and has leaf nodes with the given point capacity.
|
VPTree(int nodeCapacity)
Constructs a new, empty vp-tree with the specified node capacity.
|
Modifier and Type | Method and Description |
---|---|
boolean |
add(E point)
Adds a single point to this vp-tree.
|
boolean |
addAll(java.util.Collection<? extends E> points)
Adds all of the points in the given collection to this vp-tree.
|
void |
clear()
Removes all points from this vp-tree.
|
boolean |
contains(java.lang.Object o)
Tests whether this vp-tree contains the given point.
|
boolean |
containsAll(java.util.Collection<?> c)
Tests whether this vp-tree contains all of the points in the given
collection.
|
int |
getBinSize()
Returns the maximum number of points any leaf node of this tree should
contain.
|
E |
getNearestNeighbor(VPPoint queryPoint) |
java.util.List<E> |
getNearestNeighbors(VPPoint queryPoint,
int maxResults) |
protected VPNode<E> |
getRoot()
Returns a reference to this tree's root node.
|
boolean |
isEmpty()
Tests whether this tree is empty.
|
protected void |
pruneEmptyNode(VPNode<E> node)
"Prunes" an empty leaf node from the tree.
|
protected boolean |
remove(E point,
boolean deferPruning,
java.util.Set<VPNode<E>> nodesToPrune)
Removes a point from this tree and optionally defers pruning of nodes
left empty after the removal of their last point.
|
boolean |
remove(java.lang.Object o)
Removes a point from this tree.
|
boolean |
removeAll(java.util.Collection<?> c)
Removes all of the points in the given collection from this tree.
|
int |
size()
Returns the total number of points stored in this vp-tree.
|
java.lang.Object[] |
toArray()
Returns an array containing all of the points in this vp-tree.
|
<T> T[] |
toArray(T[] a)
Returns an array containing all of the points in this vp-tree; the
runtime type of the returned array is that of the specified array.
|
public static final int DEFAULT_BIN_SIZE
public VPTree()
public VPTree(int nodeCapacity)
nodeCapacity
- the maximum number of points to store in a leaf node of the
treepublic VPTree(java.util.Collection<E> points)
points
- the points to use to populate this treepublic VPTree(java.util.Collection<E> points, int nodeCapacity)
points
- the points to use to populate this treenodeCapacity
- the largest number of points any leaf node of the tree should
containprotected VPNode<E> getRoot()
public int getBinSize()
public boolean add(E point)
point
- the point to add to this treetrue
if the tree was modified by the addition of this
point; vp-trees are always modified by adding points, so this
method always returns truepublic boolean addAll(java.util.Collection<? extends E> points)
points
- the points to add to this treetrue
if the tree was modified by the addition of the
points; vp-trees are always modified by adding points, so this
method always returns truepublic void clear()
public boolean contains(java.lang.Object o)
o
- the object to test for membership in this treetrue
if this tree contains the given point or
false
otherwisepublic boolean containsAll(java.util.Collection<?> c)
c
- the collection of points to test for membership in this treetrue
if this tree contains all of the members of the
given collection or false
otherwisepublic boolean isEmpty()
true
if this tree contains no points or false
otherwisepublic boolean remove(java.lang.Object o)
o
- the point to removetrue
if the tree was modified by removing this point
(i.e. if the point was present in the tree) or false
otherwiseprotected boolean remove(E point, boolean deferPruning, java.util.Set<VPNode<E>> nodesToPrune)
point
- the point to removedeferPruning
- if true
and the removal of the given point would leave
a node empty, pruning of the empty node is deferred until a
time chosen by the caller; otherwise, empty nodes are pruned
immediatelynodesToPrune
- a Set
to be populated with nodes left empty by the
removal of points; this may be null
if
deferPruning
is false
true
if the tree was modified by removing this point
(i.e. if the point was present in the tree) or false
otherwisepublic boolean removeAll(java.util.Collection<?> c)
c
- the collection of points to remove from this truetrue
if the tree was modified by removing the given
points (i.e. if any of the points were present in the tree) or
false
otherwiseprotected void pruneEmptyNode(VPNode<E> node)
"Prunes" an empty leaf node from the tree. When a node is pruned, its parent absorbs the points from both of its child nodes (though only one may actually contain points) and discards its child nodes. If the parent node is empty after the absorption of its child nodes, it is also pruned; this process continues until either an ancestor of the original node is non-empty after absorbing its children or until the root of the tree is reached.
The pruning process may leave an ancestor node overly-full, in which case it is the responsibility of the caller to repartition that node.
node
- the empty node to prune from the treepublic int size()
public java.lang.Object[] toArray()
public <T> T[] toArray(T[] a)
Returns an array containing all of the points in this vp-tree; the runtime type of the returned array is that of the specified array. If the collection fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this collection.
If all of the points in this tree fit in the specified array with room
to spare (i.e., the array has more elements than this vp-tree), the
element in the array immediately following the end of the collection is
set to null
.
a
- the array into which the elements of this tree are to be
stored, if it is big enough; otherwise, a new array of the
same runtime type is allocated for this purposepublic java.util.List<E> getNearestNeighbors(VPPoint queryPoint, int maxResults)