|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.ordered.AbstractSearchTree<E>
goldman.collection.spatial.QuadTree<E>
public class QuadTree<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 |
---|
public QuadTree()
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.
public QuadTree(XYComparator<? super E> comp)
comp
- an XYComparator for comparing the elements of this collectionMethod Detail |
---|
public void checkRep()
AbstractCollection
checkRep
in interface Collection<E>
checkRep
in class AbstractCollection<E>
protected goldman.collection.spatial.QuadTree.QTNode createTreeNode(E data)
public String toString()
Collection
toString
method for that element), in the iteration order.
toString
in interface Collection<E>
toString
in class AbstractCollection<E>
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
- where 0 is the x dimension and 1 is the y dimension
public E min(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.
min
in interface SpatialCollection<E>
dimension
- where 0 is the x dimension and 1 is the y dimension
public Collection<E> withinBounds(E cornerA, E cornerB)
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>
cornerA
- an element defining one corner of a bounding boxcornerB
- an element defining the opposite corner of the bounding box
public void withinBounds(E cornerA, E cornerB, Collection<? super E> elements)
cornerA
- an element defining one corner of a bounding boxcornerB
- an element defining the opposite corner of the bounding boxelements
- the collection in which to place the elements that lie within, or on the boundary of, the bounding boxprotected AbstractSearchTree.TreeNode find(E target)
find
in class AbstractSearchTree<E>
target
- any value of type E
protected goldman.collection.spatial.QuadTree.QTNode findInsertPosition(goldman.collection.spatial.QuadTree.QTNode subtree, E element)
subtree
- a quad tree node at the root of a subtreeelement
- an element for insertion into the quad tree
protected goldman.collection.spatial.QuadTree.QTNode insert(E element)
AbstractSearchTree
insert
in class AbstractSearchTree<E>
element
- the element
to be inserted into the tree
protected goldman.collection.spatial.QuadTree.QTNode insertNode(goldman.collection.spatial.QuadTree.QTNode node, goldman.collection.spatial.QuadTree.QTNode subtree)
node
- a quad tree nodesubtree
- the root of the subtree into which the node should be insertedpublic boolean remove(E element)
remove
in interface Collection<E>
remove
in class AbstractSearchTree<E>
element
- an element in the collection
protected void remove(AbstractSearchTree.TreeNode toDelete)
AbstractSearchTree
remove
in class AbstractSearchTree<E>
toDelete
- the quad tree node to be deletedprotected void traverseForVisitor(Visitor<? super E> v) throws Exception
AbstractSearchTree
traverseForVisitor
in class AbstractSearchTree<E>
v
- a visitor
Exception
public Locator<E> iterator()
Collection
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public Locator<E> getLocator(E element)
iterator
method should be used to iterate through the collection.
getLocator
in interface Collection<E>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |