goldman.collection.spatial
Class KDTree<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.spatial.KDTree<E>
All Implemented Interfaces:
Collection<E>, SpatialCollection<E>, Tracked<E>, Iterable<E>

public class KDTree<E>
extends AbstractCollection<E>
implements SpatialCollection<E>, Tracked<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

KDTree

public KDTree(Comparator<? super E>... comparators)
Parameters:
comparators - a variable number of comparators defining the dimensions of this spatial collection
REQUIRES: at least two comparators are provided
Method Detail

getSize

public int getSize()
Description copied from interface: Collection
Returns the number of elements, size, in this collection.

Specified by:
getSize in interface Collection<E>
Overrides:
getSize in class AbstractCollection<E>
Returns:
the size of the collection

equivalent

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.

Overrides:
equivalent in class AbstractCollection<E>
Parameters:
a - the first element to compare
b - the second element to compare
Returns:
true if and only if a and b are equivalent

compare

protected int compare(E o1,
                      E o2)
Because the data set is multidimensional, the inherited compare method does not make sense. Comparison cannot occur without specifying a particular dimension.

Overrides:
compare in class AbstractCollection<E>
Parameters:
o1 - the first element to compare
o2 - the second element to compare
Returns:
a negative value when e1 < e2, zero when e1 equals e2, and a positive value when e1 > e2.

min

public E min(int dimension)
      throws NoSuchElementException
Description copied from interface: SpatialCollection
Returns a least element in the collection along the given dimension. This method throws a NoSuchElementException when the collection is empty. It throws an IllegalArgumentException when the given dimension index is not valid for this spatial collection.

Specified by:
min in interface SpatialCollection<E>
Parameters:
dimension - the dimension along which elements should be compared
Returns:
a least element in the collection along the given dimension
Throws:
NoSuchElementException

max

public E max(int dimension)
Description copied from interface: SpatialCollection
Returns a greatest element in the collection along the given dimension. This method throws a NoSuchElementException when the collection is empty. It throws an IllegalArgumentException when the given dimension index is not valid for this spatial collection.

Specified by:
max in interface SpatialCollection<E>
Parameters:
dimension - the dimension along which elements should be compared
Returns:
a greatest element in the collection along the given dimension

contains

public boolean contains(E element)
Description copied from class: AbstractCollection
This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.

Specified by:
contains in interface Collection<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
element - an element that may or may not be in the collection
Returns:
true if and only if an equivalent element exists in the collection

withinBounds

public Collection<E> withinBounds(E minCorner,
                                  E maxCorner)
Description copied from interface: SpatialCollection
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. 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.

Specified by:
withinBounds in interface SpatialCollection<E>
Parameters:
minCorner - the corner of the range having the values in all dimensions at the low end of the range
maxCorner - the corner of the range having the values in all dimensions at the high end of the range
REQUIRES: minCorner to be less than or equal to maxCorner
Returns:
a collection of all the elements in the tree that fall within the given range

getLocator

public Locator<E> getLocator(E x)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to 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.

Specified by:
getLocator in interface Collection<E>
Parameters:
x - the element to track
Returns:
a tracker that has been initialized at the given element.
Throws:
NoSuchElementException - the given element is not in the collection.

add

public void add(E element)
Description copied from interface: Collection
Inserts 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.

Specified by:
add in interface Collection<E>
Parameters:
element - an item to be added to the collection

addTracked

public Locator<E> addTracked(E element)
Description copied from interface: Tracked
Inserts 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.

Specified by:
addTracked in interface Tracked<E>
Parameters:
element - an item to be added to the collection
Returns:
a tracker positioned at that element

remove

public boolean remove(E element)
Removes from the collection an arbitrary element (if any) equivalent to element. Note that equivalence is defined as being of equal value along all dimensions of the comparator.

Specified by:
remove in interface Collection<E>
Parameters:
element - the element to remove
Returns:
true if an element was removed, and false otherwise.

iterator

public Locator<E> iterator()
Creates a new tracker at FORE. Note that because the data set is multidimensional, there is not a well-defined ordering of the elements. Therefore, one should not rely upon any particular ordering of the data during iteration.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

iteratorAtEnd

public Locator<E> iteratorAtEnd()
Creates a new tracker that is at AFT. Again, because the data set is multidimensional, there is not a well-defined ordering of the elements. Therefore, one should not rely upon any particular ordering during iteration.


checkRep

public void checkRep()
Description copied from class: AbstractCollection
Checks, for the purposes of checking correctness, that the correctness properties are preserved.

Specified by:
checkRep in interface Collection<E>
Overrides:
checkRep in class AbstractCollection<E>