public class LockingVPTree<E extends GeospatialPoint> extends VPTree<E>
A LockingVPTree
is a thread-safe subclass of a VPTree
. It
uses an internal ReentrantReadWriteLock
to manage concurrent reading
and modification of its data points.
All operations that read the contents of this tree acquire the tree's internal read lock, while operations that could modify the tree's contents or structure acquire the tree's internal write lock.
ReentrantReadWriteLock
DEFAULT_BIN_SIZE
Constructor and Description |
---|
LockingVPTree()
Constructs a new, empty
LockingVPTree with a default node
capacity and locking fairness policy. |
LockingVPTree(boolean fair)
Constructs a new, empty
LockingVPTree with a default node
capacity and the given fairness policy. |
LockingVPTree(Collection<E> points)
Constructs a new
LockingVPTree that contains (and indexes) all of
the points in the given collection with a default node capacity and
locking fairness policy. |
LockingVPTree(Collection<E> points,
boolean fair)
Constructs a new
LockingVPTree that contains (and indexes) all of
the points in the given collection with a default node capacity and the
given locking fairness policy. |
LockingVPTree(Collection<E> points,
int nodeCapacity)
Constructs a new
LockingVPTree that contains (and indexes) all of
the points in the given collection with the given node capacity and a
default locking fairness policy. |
LockingVPTree(Collection<E> points,
int nodeCapacity,
boolean fair)
Constructs a new
LockingVPTree that contains (and indexes) all of
the points in the given collection with the given node capacity and
locking fairness policy. |
LockingVPTree(int nodeCapacity)
Constructs a new, empty
LockingVPTree with the given node
capacity and a default locking fairness policy. |
LockingVPTree(int nodeCapacity,
boolean fair)
Constructs a new, empty
LockingVPTree with the given node
capacity and locking fairness policy. |
Modifier and Type | Method and Description |
---|---|
boolean |
add(E point)
Adds a single point to this vp-tree.
|
boolean |
addAll(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(Object o)
Tests whether this vp-tree contains the given point.
|
boolean |
containsAll(Collection<?> c)
Tests whether this vp-tree contains all of the points in the given
collection.
|
List<E> |
getAllNeighborsWithinDistance(GeospatialPoint queryPoint,
double maxDistance)
Returns a list of all points within a given distance to a query point.
|
List<E> |
getAllNeighborsWithinDistance(GeospatialPoint queryPoint,
double maxDistance,
SearchCriteria<E> searchCriteria)
Returns a list of all points within a given distance to a query point
that meet a set of search criteria.
|
E |
getNearestNeighbor(GeospatialPoint queryPoint)
Returns the nearest neighbor to the given query point.
|
E |
getNearestNeighbor(GeospatialPoint queryPoint,
double maxDistance)
Returns the nearest neighbor to the given query point so long as the
nearest neighbor is within the given maximum distance.
|
E |
getNearestNeighbor(GeospatialPoint queryPoint,
double maxDistance,
SearchCriteria<E> searchCriteria)
Returns the nearest neighbor to the query point that satisfies the given
search criteria so long as that point falls within the given maximum
distance from the query point.
|
E |
getNearestNeighbor(GeospatialPoint queryPoint,
SearchCriteria<E> searchCriteria)
Returns the nearest neighbor to the given query point that satisfies the
given search criteria.
|
List<E> |
getNearestNeighbors(GeospatialPoint queryPoint,
int maxResults)
Returns a list of the nearest neighbors to a given query point.
|
List<E> |
getNearestNeighbors(GeospatialPoint queryPoint,
int maxResults,
double maxDistance)
Returns a list of the nearest neighbors to a given query point and
within a given maximum distance.
|
List<E> |
getNearestNeighbors(GeospatialPoint queryPoint,
int maxResults,
double maxDistance,
SearchCriteria<E> searchCriteria)
Returns a list of the nearest neighbors to a given query point and
within a given maximum distance.
|
List<E> |
getNearestNeighbors(GeospatialPoint queryPoint,
int maxResults,
SearchCriteria<E> searchCriteria)
Returns a list of the nearest neighbors to a given query point that
satisfy the given search criteria.
|
boolean |
isEmpty()
Tests whether this tree is empty.
|
boolean |
isFair()
Tests whether this tree's internal lock uses a "fair" locking policy.
|
Iterator<E> |
iterator()
Returns an
Iterator over all of the points contained in this
tree. |
boolean |
remove(Object o)
Removes a point from this tree.
|
boolean |
removeAll(Collection<?> c)
Removes all of the points in the given collection from this tree.
|
boolean |
retainAll(Collection<?> c)
Retains only the points in this vp-tree that are contained in the
specified collection.
|
int |
size()
Returns the total number of points stored in this vp-tree.
|
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.
|
getAllPointsInBoundingBox, getAllPointsInBoundingBox, getAllPointsInBoundingBox, getAllPointsInBoundingBox, getBinSize
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
equals, hashCode
public LockingVPTree()
LockingVPTree
with a default node
capacity and locking fairness policy.public LockingVPTree(boolean fair)
LockingVPTree
with a default node
capacity and the given fairness policy.fair
- true
if this tree's lock should use a fair ordering
policy or false
otherwiseReentrantReadWriteLock.ReentrantReadWriteLock(boolean)
public LockingVPTree(int nodeCapacity)
LockingVPTree
with the given node
capacity and a default locking fairness policy.nodeCapacity
- the maximum number of points to store in a leaf node of the
treeReentrantReadWriteLock.ReentrantReadWriteLock(boolean)
public LockingVPTree(int nodeCapacity, boolean fair)
LockingVPTree
with the given node
capacity and locking fairness policy.nodeCapacity
- the maximum number of points to store in a leaf node of the
treefair
- true
if this tree's lock should use a fair ordering
policy or false
otherwiseReentrantReadWriteLock.ReentrantReadWriteLock(boolean)
public LockingVPTree(Collection<E> points)
LockingVPTree
that contains (and indexes) all of
the points in the given collection with a default node capacity and
locking fairness policy.points
- the points to use to populate this treeReentrantReadWriteLock.ReentrantReadWriteLock(boolean)
public LockingVPTree(Collection<E> points, boolean fair)
LockingVPTree
that contains (and indexes) all of
the points in the given collection with a default node capacity and the
given locking fairness policy.points
- the points to use to populate this treefair
- true
if this tree's lock should use a fair ordering
policy or false
otherwiseReentrantReadWriteLock.ReentrantReadWriteLock(boolean)
public LockingVPTree(Collection<E> points, int nodeCapacity)
LockingVPTree
that contains (and indexes) all of
the points in the given collection with the given node capacity and a
default locking fairness policy.points
- the points to use to populate this treenodeCapacity
- the maximum number of points to store in a leaf node of the
treeReentrantReadWriteLock.ReentrantReadWriteLock(boolean)
public LockingVPTree(Collection<E> points, int nodeCapacity, boolean fair)
LockingVPTree
that contains (and indexes) all of
the points in the given collection with the given node capacity and
locking fairness policy.points
- the points to use to populate this treenodeCapacity
- the maximum number of points to store in a leaf node of the
treefair
- true
if this tree's lock should use a fair ordering
policy or false
otherwiseReentrantReadWriteLock.ReentrantReadWriteLock(boolean)
public boolean isFair()
true
if this tree's internal lock uses a "fair" locking
policy or false
otherwiseReentrantReadWriteLock.isFair()
public boolean add(E point)
VPTree
add
in interface Collection<E extends GeospatialPoint>
add
in class VPTree<E extends GeospatialPoint>
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(Collection<? extends E> points)
VPTree
addAll
in interface Collection<E extends GeospatialPoint>
addAll
in class VPTree<E extends GeospatialPoint>
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()
VPTree
clear
in interface Collection<E extends GeospatialPoint>
clear
in class VPTree<E extends GeospatialPoint>
public boolean contains(Object o)
VPTree
contains
in interface Collection<E extends GeospatialPoint>
contains
in class VPTree<E extends GeospatialPoint>
o
- the object to test for membership in this treetrue
if this tree contains the given point or
false
otherwisepublic boolean containsAll(Collection<?> c)
VPTree
containsAll
in interface Collection<E extends GeospatialPoint>
containsAll
in class VPTree<E extends GeospatialPoint>
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()
VPTree
isEmpty
in interface Collection<E extends GeospatialPoint>
isEmpty
in class VPTree<E extends GeospatialPoint>
true
if this tree contains no points or false
otherwisepublic Iterator<E> iterator()
VPTree
Iterator
over all of the points contained in this
tree. The order of iteration is not defined, and the Iterator
returned by this method does not support the optional remove
method. The behavior of the returned Iterator
is not defined if
the tree is modified after the Iterator
is returned.iterator
in interface Iterable<E extends GeospatialPoint>
iterator
in interface Collection<E extends GeospatialPoint>
iterator
in class VPTree<E extends GeospatialPoint>
Iterator
over the points contained in this treepublic boolean remove(Object o)
VPTree
remove
in interface Collection<E extends GeospatialPoint>
remove
in class VPTree<E extends GeospatialPoint>
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
otherwisepublic boolean removeAll(Collection<?> c)
VPTree
removeAll
in interface Collection<E extends GeospatialPoint>
removeAll
in class VPTree<E extends GeospatialPoint>
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
otherwisepublic boolean retainAll(Collection<?> c)
VPTree
retainAll
in interface Collection<E extends GeospatialPoint>
retainAll
in class VPTree<E extends GeospatialPoint>
c
- collection containing elements to be retained in this treetrue
if this tree was modified by calling this method or
false
otherwisepublic int size()
VPTree
size
in interface Collection<E extends GeospatialPoint>
size
in class VPTree<E extends GeospatialPoint>
public Object[] toArray()
VPTree
toArray
in interface Collection<E extends GeospatialPoint>
toArray
in class VPTree<E extends GeospatialPoint>
public <T> T[] toArray(T[] a)
VPTree
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
.
toArray
in interface Collection<E extends GeospatialPoint>
toArray
in class VPTree<E extends GeospatialPoint>
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 List<E> getNearestNeighbors(GeospatialPoint queryPoint, int maxResults)
GeospatialPointDatabase
Returns a list of the nearest neighbors to a given query point. The returned list is sorted by increasing distance from the query point.
This returned list will contain at most maxResults
elements
(and may contain fewer if maxResults
is larger than the number of
points in the database). If multiple points have the same distance from
the query point, the order in which they appear in the returned list is
undefined. By extension, if multiple points have the same distance from
the query point and those points would "straddle" the end of the returned
list, which points are included in the list and which are cut off is not
prescribed.
getNearestNeighbors
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getNearestNeighbors
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find neighborsmaxResults
- the maximum length of the returned listpublic List<E> getNearestNeighbors(GeospatialPoint queryPoint, int maxResults, double maxDistance)
GeospatialPointDatabase
Returns a list of the nearest neighbors to a given query point and within a given maximum distance. The returned list is sorted by increasing distance from the query point.
This returned list will contain at most maxResults
elements
(and may contain fewer if maxResults
is larger than the number of
points in the database or if fewer than maxResults
points were
found within the given maximum distance). If multiple points have the
same distance from the query point, the order in which they appear in the
returned list is undefined. By extension, if multiple points have the
same distance from the query point and those points would "straddle" the
end of the returned list, which points are included in the list and which
are cut off is not prescribed.
getNearestNeighbors
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getNearestNeighbors
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find neighborsmaxResults
- the maximum length of the returned listmaxDistance
- the maximum allowable distance, in meters, from the query
point; points farther away than maxDistance
will not
be included in the returned listpublic List<E> getNearestNeighbors(GeospatialPoint queryPoint, int maxResults, SearchCriteria<E> searchCriteria)
GeospatialPointDatabase
Returns a list of the nearest neighbors to a given query point that satisfy the given search criteria. The returned list is sorted by increasing distance from the query point.
This returned list will contain at most maxResults
elements
(and may contain fewer if maxResults
is larger than the number of
points in the database). If multiple points have the same distance from
the query point, the order in which they appear in the returned list is
undefined. By extension, if multiple points have the same distance from
the query point and those points would "straddle" the end of the returned
list, which points are included in the list and which are cut off is not
prescribed.
getNearestNeighbors
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getNearestNeighbors
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find neighborsmaxResults
- the maximum length of the returned listsearchCriteria
- the search criteria to be met by all returned pointspublic List<E> getNearestNeighbors(GeospatialPoint queryPoint, int maxResults, double maxDistance, SearchCriteria<E> searchCriteria)
GeospatialPointDatabase
Returns a list of the nearest neighbors to a given query point and within a given maximum distance. The returned list is sorted by increasing distance from the query point.
This returned list will contain at most maxResults
elements
(and may contain fewer if maxResults
is larger than the number of
points in the database or if fewer than maxResults
points were
found within the given maximum distance). If multiple points have the
same distance from the query point, the order in which they appear in the
returned list is undefined. By extension, if multiple points have the
same distance from the query point and those points would "straddle" the
end of the returned list, which points are included in the list and which
are cut off is not prescribed.
getNearestNeighbors
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getNearestNeighbors
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find neighborsmaxResults
- the maximum length of the returned listmaxDistance
- the maximum allowable distance, in meters, from the query
point; points farther away than maxDistance
will not
be included in the returned listsearchCriteria
- the search criteria to be met by all returned pointspublic List<E> getAllNeighborsWithinDistance(GeospatialPoint queryPoint, double maxDistance)
GeospatialPointDatabase
getAllNeighborsWithinDistance
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getAllNeighborsWithinDistance
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find neighborsmaxDistance
- the maximum allowable distance, in meters, from the query
point; points farther away than maxDistance
will not
be included in the returned listpublic List<E> getAllNeighborsWithinDistance(GeospatialPoint queryPoint, double maxDistance, SearchCriteria<E> searchCriteria)
GeospatialPointDatabase
getAllNeighborsWithinDistance
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getAllNeighborsWithinDistance
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find neighborsmaxDistance
- the maximum allowable distance, in meters, from the query
point; points farther away than maxDistance
will not
be included in the returned listsearchCriteria
- the search criteria to be met by all points in the returned
listpublic E getNearestNeighbor(GeospatialPoint queryPoint)
GeospatialPointDatabase
getNearestNeighbor
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getNearestNeighbor
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find the nearest neighbornull
if the
database contains no pointspublic E getNearestNeighbor(GeospatialPoint queryPoint, double maxDistance)
GeospatialPointDatabase
getNearestNeighbor
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getNearestNeighbor
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find the nearest neighbormaxDistance
- the maximum allowable distance from the query point in metersnull
if the
database contains no points within maxDistance
meters of
the query pointpublic E getNearestNeighbor(GeospatialPoint queryPoint, SearchCriteria<E> searchCriteria)
GeospatialPointDatabase
getNearestNeighbor
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getNearestNeighbor
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find the nearest neighborsearchCriteria
- the criteria to apply to potential nearest neighborsnull
if the
database contains no points that satisfy the given search
criteriapublic E getNearestNeighbor(GeospatialPoint queryPoint, double maxDistance, SearchCriteria<E> searchCriteria)
GeospatialPointDatabase
getNearestNeighbor
in interface GeospatialPointDatabase<E extends GeospatialPoint>
getNearestNeighbor
in class VPTree<E extends GeospatialPoint>
queryPoint
- the point for which to find the nearest neighbormaxDistance
- the maximum allowable distance from the query point in meterssearchCriteria
- the criteria to apply to potential nearest neighborsnull
if no
points matching the given search criteria were found within
maxDistance
meters of the query pointjeospatial is an open-source library hosted at https://github.com/jchambers/jeospatial.