goldman.collection.spatial
Class QuadTree<E>

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

public class QuadTree<E>
extends AbstractSearchTree<E>
implements SpatialCollection<E>

A quad tree divides the subdomain into four regions at each internal node. In general, if there are k dimensions, once can think of each node (in the k-dimensional extension of the quad tree) as grouping k consecutive levels of a k-d tree, giving a combined branching factor of 2k. At each node, a comparison is made along all k dimensions. To do this compression, a single k-dimensional point is used to partition the domain into 2k subdomains. Thus, the expected height of a k-dimensional extension of quad tree is less than the expected height of a k-d tree by a factor of k. While the expected number of comparisons is the same, the larger expected depth in a k-d tree slightly increases the search time. Furthermore, if there is support to make up to 3 comparisons in parallel, then a quad tree (for k=2) or an oct tree (for k=3) leads to significantly faster expected search times since all k comparisons can be made in parallel whereas for a k-d tree the comparisons must be made sequentially. A k-d tree could also perform two levels of comparison in parallel, but an extra comparison would then be made. Each node in a quad tree contains an element representing an (x,y) point. Each point divides the plane into four quadrants: lower left, lower right, upper right, and upper left. Each node has four subtrees containing elements for points in these respective quadrants.


Nested Class Summary
 
Nested classes/interfaces inherited from class goldman.collection.ordered.AbstractSearchTree
AbstractSearchTree.TreeNode
 
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
DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version
 
Constructor Summary
QuadTree()
          The default constructor uses a default comparator, under the assumption that type E implements the XYPoint interface.
QuadTree(XYComparator<? super E> comp)
           
 
Method Summary
 void checkRep()
          Checks, for the purposes of checking correctness, that the correctness properties are preserved.
protected  goldman.collection.spatial.QuadTree.QTNode createTreeNode(E data)
           
protected  AbstractSearchTree.TreeNode find(E target)
           
protected  goldman.collection.spatial.QuadTree.QTNode findInsertPosition(goldman.collection.spatial.QuadTree.QTNode subtree, E element)
           
 Locator<E> getLocator(E element)
          The iterator method should be used to iterate through the collection.
protected  goldman.collection.spatial.QuadTree.QTNode insert(E element)
          Inserts it into the collection
protected  goldman.collection.spatial.QuadTree.QTNode insertNode(goldman.collection.spatial.QuadTree.QTNode node, goldman.collection.spatial.QuadTree.QTNode subtree)
           
 Locator<E> iterator()
          Returns a locator that has been initialized to FORE.
 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.
protected  void remove(AbstractSearchTree.TreeNode toDelete)
          Removes the given node.
 boolean remove(E element)
          Removes the given element from the collection
 String toString()
          Returns a string that includes each element in this collection (as produced by the toString method for that element), in the iteration order.
protected  void traverseForVisitor(Visitor<? super E> v)
          Applies the visitor to each element of the collection in sorted order
 Collection<E> withinBounds(E cornerA, E cornerB)
          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.
 void withinBounds(E cornerA, E cornerB, Collection<? super E> elements)
           
 
Methods inherited from class goldman.collection.ordered.AbstractSearchTree
add, contains, get, getEquivalentElement, getLastNodeSearchIndex, max, min, writeElements
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, clear, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, trimToSize
 
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, add, addAll, clear, contains, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, trimToSize
 

Constructor Detail

QuadTree

public QuadTree()
The default constructor uses a default comparator, under the assumption that type E implements the XYPoint interface. If type E does not implement XYPoint, then an XYComparator for E should be provided, using the other constructor. Otherwise, a ClassCastException will occur when the second element is added to the quad tree.


QuadTree

public QuadTree(XYComparator<? super E> comp)
Parameters:
comp - an XYComparator for comparing the elements of this collection
Method Detail

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>

createTreeNode

protected goldman.collection.spatial.QuadTree.QTNode createTreeNode(E data)

toString

public String toString()
Description copied from interface: Collection
Returns a string that includes each element in this collection (as produced by the toString method for that element), in the iteration order.

Specified by:
toString in interface Collection<E>
Overrides:
toString in class AbstractCollection<E>
Returns:
a comma-separated string that shows the sequence held in the collection, in the iteration order. Braces mark the beginning and the end of the collection.

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 - where 0 is the x dimension and 1 is the y dimension
Returns:
a maximum element along the given dimension

min

public E min(int dimension)
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 - where 0 is the x dimension and 1 is the y dimension
Returns:
a minimum element along the given dimension

withinBounds

public Collection<E> withinBounds(E cornerA,
                                  E cornerB)
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:
cornerA - an element defining one corner of a bounding box
cornerB - an element defining the opposite corner of the bounding box
Returns:
a collection of all elements in this quad tree that lie within, or on the boundary of, this bounding box, based on the XYComparator of this quad tree

withinBounds

public void withinBounds(E cornerA,
                         E cornerB,
                         Collection<? super E> elements)
Parameters:
cornerA - an element defining one corner of a bounding box
cornerB - an element defining the opposite corner of the bounding box
elements - the collection in which to place the elements that lie within, or on the boundary of, the bounding box

find

protected AbstractSearchTree.TreeNode find(E target)
Specified by:
find in class AbstractSearchTree<E>
Parameters:
target - any value of type E
Returns:
the tree node containing an element equal to the target, or the frontier node if no matching element is found. If the frontier node is returned, then its parent will have been set to the last non-frontier node on the search path.

findInsertPosition

protected goldman.collection.spatial.QuadTree.QTNode findInsertPosition(goldman.collection.spatial.QuadTree.QTNode subtree,
                                                                        E element)
Parameters:
subtree - a quad tree node at the root of a subtree
element - an element for insertion into the quad tree
Returns:
the frontier node at the insert position of the target. That is, the frontier node's parent is set to the quad tree node that should become the parent of the target.

insert

protected goldman.collection.spatial.QuadTree.QTNode insert(E element)
Description copied from class: AbstractSearchTree
Inserts it into the collection

Specified by:
insert in class AbstractSearchTree<E>
Parameters:
element - the element to be inserted into the tree
Returns:
a reference to the newly inserted element

insertNode

protected goldman.collection.spatial.QuadTree.QTNode insertNode(goldman.collection.spatial.QuadTree.QTNode node,
                                                                goldman.collection.spatial.QuadTree.QTNode subtree)
Parameters:
node - a quad tree node
subtree - the root of the subtree into which the node should be inserted

remove

public boolean remove(E element)
Removes the given element from the collection

Specified by:
remove in interface Collection<E>
Overrides:
remove in class AbstractSearchTree<E>
Parameters:
element - an element in the collection
Returns:
true if and only if the given element was found in the collection

remove

protected void remove(AbstractSearchTree.TreeNode toDelete)
Description copied from class: AbstractSearchTree
Removes the given node.

Specified by:
remove in class AbstractSearchTree<E>
Parameters:
toDelete - the quad tree node to be deleted

traverseForVisitor

protected void traverseForVisitor(Visitor<? super E> v)
                           throws Exception
Description copied from class: AbstractSearchTree
Applies the visitor to each element of the collection in sorted order

Overrides:
traverseForVisitor in class AbstractSearchTree<E>
Parameters:
v - a visitor
Throws:
Exception

iterator

public Locator<E> iterator()
Description copied from interface: Collection
Returns a locator that has been initialized to FORE. The locator returned can be used to navigate within the collection and to remove the element currently associated with the locator. In general, no assumption is made about the iteration order, the order in which the iterator advances through the collection. However, some collection ADTs specify a particular iteration order.

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

getLocator

public Locator<E> getLocator(E element)
The iterator method should be used to iterate through the collection.

Specified by:
getLocator in interface Collection<E>