public class VPTree<E extends VPPoint> extends java.lang.Object implements ByteSerializable
ByteSerializable.Deserialize
Modifier and Type | Field and Description |
---|---|
protected int |
binSize |
static int |
DEFAULT_BIN_SIZE
The default node capacity (32 points) for nodes in this vp-tree.
|
protected VPNode<E> |
root |
Constructor and Description |
---|
VPTree()
Constructs a new, empty vp-tree with a default node capacity.
|
VPTree(java.util.Collection<? extends VPPoint> 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(java.util.Collection<E> points)
Constructs a new vp-tree that contains (and indexes) all of the points in
the given collection.
|
VPTree(int nodeCapacity)
Constructs a new, empty vp-tree with the specified node capacity.
|
VPTree(SerializationInputStream in) |
Modifier and Type | Method and Description |
---|---|
long |
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.
|
java.lang.String |
generateDot() |
int |
getBinSize()
Returns the maximum number of points any leaf node of this vp-tree should
contain.
|
E |
getNearestNeighbor(VPPoint queryPoint) |
java.util.List<E> |
getNearestNeighbors(VPPoint queryPoint,
int maxResults) |
long |
getPrefixOf(E value)
Deprecated.
|
long |
getPrefixOf(E value,
int depth) |
VPNode<E> |
getRoot()
Returns a reference to this vp-tree's root node.
|
boolean |
isEmpty()
Tests whether this vp-tree is empty.
|
protected void |
pruneEmptyNode(VPNode<E> node)
"Prunes" an empty leaf node from the vp-tree.
|
protected boolean |
remove(E point,
boolean deferPruning,
java.util.Set<VPNode<E>> nodesToPrune)
Removes a point from this vp-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 vp-tree.
|
boolean |
removeAll(java.util.Collection<?> c)
Removes all of the points in the given collection from this vp-tree.
|
void |
serialize(SerializationOutputStream out)
Serializes this object to binary form by passing it through a
serialization stream.
|
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) |
public static final int DEFAULT_BIN_SIZE
protected final int binSize
public VPTree()
public VPTree(int nodeCapacity)
nodeCapacity
- the maximum number of points to store in a leaf node
of the vp-treepublic VPTree(java.util.Collection<E> points)
points
- the points to use to populate this vp-treepublic VPTree(java.util.Collection<? extends VPPoint> points, int nodeCapacity)
points
- the points to use to populate this vp-treenodeCapacity
- the largest number of points any leaf node of the
vp-tree should contain@ByteSerializable.Deserialize public VPTree(SerializationInputStream in) throws java.io.IOException
java.io.IOException
public VPNode<E> getRoot()
public int getBinSize()
public long add(E point)
point
- the point to add to this vp-treetrue
if the vp-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 vp-treetrue
if the vp-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 vp-treetrue
if this vp-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 vp-treetrue
if this vp-tree contains all of the members of the
given collection or false
otherwise@Deprecated public long getPrefixOf(E value)
public long getPrefixOf(E value, int depth)
public boolean isEmpty()
true
if this vp-tree contains no points or false
otherwisepublic boolean remove(java.lang.Object o)
o
- the point to removetrue
if the vp-tree was modified by removing this point
(i.e. if the point was present in the vp-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 vp-tree was modified by removing this point
(i.e. if the point was present in the vp-tree) or false
otherwisepublic boolean removeAll(java.util.Collection<?> c)
c
- the collection of points to remove from this truetrue
if the vp-tree was modified by removing the given
points (i.e. if any of the points were present in the vp-tree) or
false
otherwiseprotected void pruneEmptyNode(VPNode<E> node)
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 vp-treepublic int size()
public java.lang.Object[] toArray()
public <T> T[] toArray(T[] a)
public java.util.List<E> getNearestNeighbors(VPPoint queryPoint, int maxResults)
public java.lang.String generateDot()
public void serialize(SerializationOutputStream out) throws java.io.IOException
ByteSerializable
serialize
in interface ByteSerializable
out
- stream to serialize to.java.io.IOException