|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.spatial.KDTree<E>
public class KDTree<E>
The k-d tree cycles among the k dimensions, dividing each region by a halfspace with respect to the dimensions associated with that level. Since the partition at each node uses just one dimension, a k-d tree has the flexibility needed to efficiently partition the domain for certain data distributions (e.g., points along the diagonal). Because of this flexibility, the space usage of a k-d tree scales well in the number of dimensions, and so it is the spatial collection data structure of choice for k > 3. While the expected height of a k-d tree is roughly k times more than a k-dimensional extension of a quad tree, each level only requires a single comparison in a k-d tree, versus k comparisons in a k-dimensional extension of a quad tree. Also, deletion is much less complex in a k-d tree than it is for a quad tree. The internal representation for a k-d tree uses KDTreeImpl, which is a special type of binary search tree data structure.
Nested Class Summary |
---|
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection |
---|
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator |
Field Summary |
---|
Fields inherited from class goldman.collection.AbstractCollection |
---|
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version |
Constructor Summary | |
---|---|
KDTree(Comparator<? super E>... comparators)
|
Method Summary | |
---|---|
void |
add(E element)
Inserts value into
the collection in an arbitrary location. |
Locator<E> |
addTracked(E element)
Inserts o into
the collection in an arbitrary location and returns
a tracker to the inserted element. |
void |
checkRep()
Checks, for the purposes of checking correctness, that the correctness properties are preserved. |
protected int |
compare(E o1,
E o2)
Because the data set is multidimensional, the inherited compare
method does not make sense. |
boolean |
contains(E element)
This implementation for contains takes linear time, so it
is overridden by a more efficient method in most data structure
implementations. |
protected boolean |
equivalent(E a,
E b)
Note that, in the case of a multidimensional data set, equivalence is defined as the elements having equal value along all dimensions. |
Locator<E> |
getLocator(E x)
Returns a locator that has been initialized to an element equivalent to target . |
int |
getSize()
Returns the number of elements, size, in this collection. |
Locator<E> |
iterator()
Creates a new tracker at FORE. |
Locator<E> |
iteratorAtEnd()
Creates a new tracker that is at AFT. |
E |
max(int dimension)
Returns a greatest element in the collection along the given dimension. |
E |
min(int dimension)
Returns a least element in the collection along the given dimension. |
boolean |
remove(E element)
Removes from the collection an arbitrary element (if any) equivalent to element . |
Collection<E> |
withinBounds(E minCorner,
E maxCorner)
Returns a collection of the elements that fall within (or on) the boundary of the multidimensional box defined by the two given corners, minCorner and maxCorner . |
Methods inherited from class goldman.collection.AbstractCollection |
---|
accept, addAll, clear, ensureCapacity, getCapacity, getComparator, getElementAtRank, getElementAtRank, getEquivalentElement, isEmpty, retainAll, toArray, toArray, toString, traverseForVisitor, trimToSize, writeElements |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Methods inherited from interface goldman.collection.Collection |
---|
accept, addAll, clear, ensureCapacity, getCapacity, getComparator, getEquivalentElement, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Methods inherited from interface goldman.collection.Collection |
---|
accept, addAll, clear, ensureCapacity, getCapacity, getComparator, getEquivalentElement, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Constructor Detail |
---|
public KDTree(Comparator<? super E>... comparators)
comparators
- a variable number of comparators defining the
dimensions of this spatial collection
Method Detail |
---|
public int getSize()
Collection
getSize
in interface Collection<E>
getSize
in class AbstractCollection<E>
protected boolean equivalent(E a, E b)
equivalent
in class AbstractCollection<E>
a
- the first element to compareb
- the second element to compare
a
and b
are
equivalentprotected int compare(E o1, E o2)
compare
method does not make sense.
Comparison cannot occur without specifying a particular dimension.
compare
in class AbstractCollection<E>
o1
- the first element to compareo2
- the second element to compare
e1
< e2
,
zero when e1
equals e2
, and
a positive value when e1
> e2
.public E min(int dimension) throws NoSuchElementException
SpatialCollection
NoSuchElementException
when the collection is empty. It throws an
IllegalArgumentException
when the given dimension index is not
valid for this spatial collection.
min
in interface SpatialCollection<E>
dimension
- the dimension along which elements should be compared
NoSuchElementException
public E max(int dimension)
SpatialCollection
NoSuchElementException
when the collection is empty. It
throws an
IllegalArgumentException
when the given dimension index is not
valid for this spatial collection.
max
in interface SpatialCollection<E>
dimension
- the dimension along which elements should be compared
public boolean contains(E element)
AbstractCollection
contains
takes linear time, so it
is overridden by a more efficient method in most data structure
implementations.
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
element
- an element that may or may not be in the collection
public Collection<E> withinBounds(E minCorner, E maxCorner)
SpatialCollection
minCorner
and maxCorner
. That is, this method performs an
orthogonal range search. It requires that the
coordinates of minCorner
are less than or equal to those of maxCorner
along every dimension of the spatial collection.
withinBounds
in interface SpatialCollection<E>
minCorner
- the corner of the range having the values in all dimensions at the low end of the rangemaxCorner
- the corner of the range having the values in all dimensions at the high end of the range
public Locator<E> getLocator(E x)
Collection
target
. Like the iterator
method, this method enables
navigation, but from a specified starting point. This method
throws a NoSuchElementException
if there is no equivalent element
in the collection.
getLocator
in interface Collection<E>
x
- the element to track
NoSuchElementException
- the given element is not in the collection.public void add(E element)
Collection
value
into
the collection in an arbitrary location. If a tracker is to be returned
then the method addTracked
which is part of the
Tracked
interface should be called instead.
An AtCapacityException
(an unchecked exception) is thrown when a bounded
collection is already at capacity.
add
in interface Collection<E>
element
- an item to be added to the collectionpublic Locator<E> addTracked(E element)
Tracked
o
into
the collection in an arbitrary location and returns
a tracker to the inserted element.
An AtCapacityException
(an unchecked exception) is thrown if the
collection is already at capacity.
addTracked
in interface Tracked<E>
element
- an item to be added to the collection
public boolean remove(E element)
element
.
Note that equivalence is defined as being of equal value along all dimensions of the comparator.
remove
in interface Collection<E>
element
- the element to remove
true
if an element was removed, and false
otherwise.public Locator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public Locator<E> iteratorAtEnd()
public void checkRep()
AbstractCollection
checkRep
in interface Collection<E>
checkRep
in class AbstractCollection<E>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |