public class VPNode<T extends VPPoint> extends java.lang.Object implements ByteSerializable
VPNodes
are the nodes of a vantage point vp-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 elements
member that contains all of the elements
stored in the node.
Non-leaf nodes will have non-null
children and contain no
elements of their own.ByteSerializable.Deserialize
Constructor and Description |
---|
VPNode(int binSize,
long prefix,
int depth)
Constructs a new, empty node with the given capacity.
|
VPNode(SerializationInputStream in) |
VPNode(T[] elements,
int lower,
int upper,
int binSize,
long prefix,
int depth)
Constructs a new node that contains a subset of the given array of
VPPoints . |
Modifier and Type | Method and Description |
---|---|
void |
absorbChildren()
Recursively absorbs the elements contained in this node's children into
this node, making this node a leaf node in the process.
|
long |
add(T point)
Adds a point to this node if it is a leaf node or one of its children
if not.
|
protected long |
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> elements)
Adds all of the elements 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 elements 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 elements 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. |
java.lang.String |
generateDot(int count) |
VPPoint |
getCenter()
Returns a new point that is coincident with this node's center point.
|
VPNode<T> |
getCloserNode()
Returns a reference to this node's child that contains elements that
are closer to this node's center than this node's distance threshold.
|
int |
getDepth() |
java.util.Collection<T> |
getElements()
Returns a collection of all the elements stored directly in this node.
|
VPNode<T> |
getFartherNode()
Returns a reference to this node's child that contains elements 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 elements close to the query
point.
|
long |
getPrefix()
Returns the prefix value of this node.
|
long |
getPrefixOf(T value)
Deprecated.
|
long |
getPrefixOf(T value,
int depth) |
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 elements than its maximum
capacity.
|
int |
nth_element(T[] elements,
int lower,
int upper,
int n,
VPPoint vp)
Implementation of the selection algorithm.
|
void |
partition()
Attempts to partition the elements contained in this node into two
child nodes.
|
protected void |
partition(T[] elements,
int lower,
int upper)
Attempts to partition the elements 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 elements.
|
void |
serialize(SerializationOutputStream out)
Serializes this object to binary form by passing it through a
serialization stream.
|
int |
size()
Returns the number of elements contained in this node and its child
nodes.
|
public VPNode(int binSize, long prefix, int depth)
binSize
- the largest number of elements this node should holdpublic VPNode(T[] elements, int lower, int upper, int binSize, long prefix, int depth)
VPPoints
. If the subset of elements is larger than the given bin
capacity, child nodes will be created recursively.elements
- the array of elements from which to build this nodelower
- the starting index (inclusive) of the subset of
the array from which to build this nodeupper
- the end index (exclusive) of the subset of the array from
which to build this nodebinSize
- the largest number of elements this node should hold@ByteSerializable.Deserialize public VPNode(SerializationInputStream in) throws java.io.IOException
java.io.IOException
public VPNode<T> getCloserNode()
null
if this is a leaf nodepublic VPNode<T> getFartherNode()
null
if this is a leaf nodepublic VPPoint getCenter()
public double getThreshold()
java.lang.IllegalStateException
- if this node is a leaf nodepublic long getPrefix()
@Deprecated public long getPrefixOf(T value)
public long getPrefixOf(T value, int depth)
public boolean addAll(java.util.Collection<? extends T> elements)
elements
- the collection of elements to add to this node or its
childrentrue
if this node or its children were modified or
false
otherwisepublic long 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 long add(T point, boolean deferMaintenance, java.util.Set<VPNode<T>> nodesAffected)
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 immediately. This
is useful when adding many elements at a time to the
partitioning step only once, rather than a partition of every
element added.nodesAffected
- a Set
that collects nodes that have received new
elements; 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 elements 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> getElements()
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 foundprotected void partition(T[] elements, int lower, int upper) throws PartitionException
elements
- an array from which to partition a subset of elementslower
- the start index of the sub-array of elements to
partition (inclusive)upper
- the end index of the sub-array of elements to partition
(exclusive)PartitionException
- if the range specified by lower
and
upper
includes fewer viable distance
threshold could be found (i.e. all of the
elements 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
elements or false
otherwisepublic boolean isOverloaded()
true
if the number of elements 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 elementspublic void addPointsToArray(java.lang.Object[] array)
array
- the array to which to add elementspublic int addPointsToArray(java.lang.Object[] array, int offset)
array
- the array to which to ad elementsoffset
- the starting index (inclusive) of the array to begin
adding elementspublic 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 nodepublic 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 nodespublic boolean isAncestorOfNode(VPNode<T> node)
node
- the node for which to test ancestrytrue
if the given node is a descendant of this node
or false
otherwisepublic int nth_element(T[] elements, int lower, int upper, int n, VPPoint vp)
elements
array from lower
to
upper
around n such that the values preceding n are less than it
and values following are greater. This is a more efficient way to find
the median of a collection than sorting and selecting the middle element.
The runtime is O(n) in all cases. This algorithm is run
in place and therefore will modify the elements array.elements
- the array to perform the selection algorithm onlower
- the lower bound (inclusive) of the range to be
partitionedupper
- the upper bound (inclusive) of the range to be
partitionedn
- the position to partition aroundpublic java.lang.String generateDot(int count)
public void serialize(SerializationOutputStream out) throws java.io.IOException
ByteSerializable
serialize
in interface ByteSerializable
out
- stream to serialize to.java.io.IOException
public int getDepth()