public class VPNode<T extends VPPoint>
extends java.lang.Object
VPNodes
are the nodes of a vantage point tree. VPNodes
may or may not be leaf nodes; if they are leaf nodes, they have no
children (their child node members will be null
) and they will
have a non-null points
member that contains all of the points
stored in the node.
Non-leaf nodes will have non-null
children and contain no
points of their own.
Constructor and Description |
---|
VPNode(int binSize)
Constructs a new, empty node with the given capacity.
|
VPNode(T[] points,
int fromIndex,
int toIndex,
int binSize)
Constructs a new node that contains a subset of the given array of
points.
|
Modifier and Type | Method and Description |
---|---|
void |
absorbChildren()
Recursively absorbs the points contained in this node's children into
this node, making this node a leaf node in the process.
|
boolean |
add(T point)
Adds a point to this node if it is a leaf node or one of its children
if not.
|
protected boolean |
add(T point,
boolean deferMaintenance,
java.util.Set<VPNode<T>> nodesAffected)
Adds a point to this node if it is a leaf node or one of its
children if not.
|
boolean |
addAll(java.util.Collection<? extends T> points)
Adds all of the points in a collection to this node (if it is a
leaf node) or its children.
|
void |
addPointsToArray(java.lang.Object[] array)
Adds all of the points from this node if it is a leaf node or its
children if it is not to an array.
|
int |
addPointsToArray(java.lang.Object[] array,
int offset)
Adds all of the points from this node and its children to the given
array starting at the given offset.
|
boolean |
contains(T point)
Tests whether this node or one of its children contains the given
point.
|
void |
findNodeContainingPoint(VPPoint p,
java.util.Deque<VPNode<T>> stack)
Finds the node at or below this node that contains (or would contain)
the given point.
|
void |
gatherLeafNodes(java.util.List<VPNode<T>> leafNodes)
Populates the given
List with all of the leaf nodes that are
descendants of this node. |
VPPoint |
getCenter()
Returns a point that is coincident with this node's center point.
|
VPNode<T> |
getCloserNode()
Returns a reference to this node's child that contains points that
are closer to this node's center than this node's distance threshold.
|
VPNode<T> |
getFartherNode()
Returns a reference to this node's child that contains points that
are farther away from this node's center than this node's distance
threshold.
|
void |
getNearestNeighbors(VPPoint queryPoint,
BoundedPriorityQueue<T> results)
Populates the given search result set with points close to the query
point.
|
java.util.Collection<T> |
getPoints()
Returns a collection of all the points stored directly in this node.
|
double |
getThreshold()
Returns the distance threshold for this node if it is a non-leaf
node.
|
boolean |
isAncestorOfNode(VPNode<T> node)
Tests whether this node is an ancestor of the given node.
|
boolean |
isEmpty()
Tests whether this node and all of its children are empty.
|
boolean |
isLeafNode()
Tests whether this is a leaf node.
|
boolean |
isOverloaded()
Tests whether this node contains more points than its maximum
capacity.
|
void |
partition()
Attempts to partition the points contained in this node into two
child nodes.
|
protected void |
partition(T[] points,
int fromIndex,
int toIndex)
Attempts to partition the points in a subset of the given array into
two child nodes based on their distance from the center of this node.
|
boolean |
remove(T point)
Removes a point from this node's internal list of points.
|
int |
size()
Returns the number of points contained in this node and its child
nodes.
|
public VPNode(int binSize)
binSize
- the largest number of points this node should holdpublic VPNode(T[] points, int fromIndex, int toIndex, int binSize)
points
- the array of points from which to build this nodefromIndex
- the starting index (inclusive) of the subset of the array
from which to build this nodetoIndex
- the end index (exclusive) of the subset of the array from
which to build this nodebinSize
- the largest number of points this node should holdpublic VPNode<T> getCloserNode()
null
if
this is a leaf nodeisLeafNode()
public VPNode<T> getFartherNode()
null
if this is a leaf nodeisLeafNode()
public VPPoint getCenter()
public double getThreshold()
java.lang.IllegalStateException
- if this node is a leaf nodegetCenter()
,
getCloserNode()
,
getFartherNode()
public boolean addAll(java.util.Collection<? extends T> points)
Adds all of the points in a collection to this node (if it is a leaf node) or its children. If this node is a leaf node and the added points push this node beyond its capacity, it is partitioned as needed after all points have been added.
This method defers partitioning of child nodes until all points have been added.
points
- the collection of points to add to this node or its
childrentrue
if this node or its children were modified or
false
otherwise; vp-trees are always modified by the
addition of points, so this method always returns
true
if points
is not emptypublic boolean add(T point)
point
- the point to add to this node or one of its childrentrue
if this node or one of its children was modified
by the addition of this point or false
otherwiseprotected boolean add(T point, boolean deferMaintenance, java.util.Set<VPNode<T>> nodesAffected)
Adds a point to this node if it is a leaf node or one of its children if not. If the node that ultimately holds the new point is loaded beyond its capacity, it will be partitioned.
Partitioning may optionally be deferred, in which case it is the responsibility of the caller to partition overloaded nodes.
point
- the point to add to this node or one of its childrendeferMaintenance
- if true
, defer partitioning of overloaded nodes
and trimming of nodes with spare capacity until the caller
chooses to partition or trim them; if false
,
overloaded nodes are partitioned or trimmed immediatelynodesAffected
- a Set
that collects nodes that have received new
points; this may be null
if
deferMaintenance
is false
. Callers must
use this set to partition or trim nodes later.true
if this node or any of its children were
modified by the addition of the new point or false
otherwise; note that adding points always results in
modificationpublic boolean contains(T point)
point
- the point whose presence is to be testedtrue
if the given point is present in this node or
one of its children or false
otherwisepublic int size()
public java.util.Collection<T> getPoints()
java.lang.IllegalStateException
- if this node is not a leaf nodepublic void partition() throws PartitionException
PartitionException
- if this node is node a leaf node, if this node is empty,
or if no viable distance threshold could be found (i.e.
all points in this node have the same distance from the
node's center)protected void partition(T[] points, int fromIndex, int toIndex) throws PartitionException
points
- an array from which to partition a subset of pointsfromIndex
- the start index of the sub-array of points to partition
(inclusive)toIndex
- the end index of the sub-array of points to partition
(exclusive)PartitionException
- if the range specified by fromIndex
and
toIndex
includes fewer than two points or if no
viable distance threshold could be found (i.e. all of the
points in the subarray have the same distance from this
node's center point)public boolean isLeafNode()
true
if this node is a leaf node or false
otherwisepublic boolean isEmpty()
true
if this node and all of its children contain no
points or false
otherwisepublic boolean isOverloaded()
true
if the number of points stored in this node is
greater than its capacity or false
otherwisejava.lang.IllegalStateException
- if this is not a leaf nodepublic void getNearestNeighbors(VPPoint queryPoint, BoundedPriorityQueue<T> results)
queryPoint
- the point for which to find nearby neighborsresults
- the result set to which to offer pointspublic void addPointsToArray(java.lang.Object[] array)
array
- the array to which to add pointssize()
public int addPointsToArray(java.lang.Object[] array, int offset)
array
- the array to which to ad pointsoffset
- the starting index (inclusive) of the array to begin
adding pointspublic void findNodeContainingPoint(VPPoint p, java.util.Deque<VPNode<T>> stack)
p
- the point for which to find the containing nodestack
- the stack to populate with the chain of nodes leading to
the leaf node that contains or would contain the given
pointpublic boolean remove(T point)
point
- the point to remove from this nodetrue
if the point was removed from this node (i.e.
this node actually contained the given point) or
false
otherwisejava.lang.IllegalStateException
- if this node is not a leaf nodepublic void absorbChildren()
java.lang.IllegalStateException
- if this node is a leaf node (and thus has no children)public void gatherLeafNodes(java.util.List<VPNode<T>> leafNodes)
List
with all of the leaf nodes that are
descendants of this node.leafNodes
- the list to populate with leaf nodes