com.savarese.spatial
Class KDTree<Coord extends java.lang.Comparable<? super Coord>,P extends Point<Coord>,V>

java.lang.Object
  com.savarese.spatial.KDTree<Coord,P,V>

All Implemented Interfaces:

RangeSearchTree<Coord,P,V>, java.util.Map<P,V>

public class KDTree<Coord extends java.lang.Comparable<? super Coord>,P extends Point<Coord>,V>
extends java.lang.Object
implements RangeSearchTree<Coord,P,V>

A k-d tree divides a k-dimensional space relative to the points it contains by storing them in a binary tree, discriminating by a different dimension at each level of the tree. It allows efficient point data retrieval (O(lg(n))) and range searching.

KDTree conforms to the java.util.Map interface except that Iterator.remove is not supported by the returned views.

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Constructor Summary

KDTree()
Creates a two-dimensional KDTree.

KDTree(int dimensions)
Creates a KDTree of the specified number of dimensions.

Method Summary

void	clear() Removes all elements from the container, leaving it empty.
boolean	containsKey(java.lang.Object key) Returns true if the container contains a mapping for the specified key.
boolean	containsValue(java.lang.Object value) Returns true if the container contains a mapping with the specified value.
java.util.Set<java.util.Map.Entry<P,V>>	entrySet() Returns a Set view of the point to value mappings in the KDTree.
boolean	equals(java.lang.Object o) Returns true if the object contains the same mappings, false if not.
V	get(java.lang.Object point) Retrieves the value at the given location.
int	hashCode() Returns the hash code value for this map.
boolean	isEmpty() Returns true if the container has no elements, false if it contains one or more elements.
java.util.Iterator<java.util.Map.Entry<P,V>>	iterator(P lower, P upper) Returns an iterator for mappings that are contained in the rectangle defined by the given lower left-hand and upper right-hand corners.
java.util.Set<P>	keySet() Returns a Set view of the point keys for the mappings in the KDTree.
void	optimize() Optimizes the performance of future search operations by balancing the KDTree.
V	put(P point, V value) Inserts a point value pair into the tree, preserving the spatial ordering.
void	putAll(java.util.Map<? extends P,? extends V> map) Copies all of the point-value mappings from the given Map into the KDTree.
V	remove(java.lang.Object key) Removes the point-value mapping corresponding to the given point key.
int	size() Returns the number of point-value mappings in the KDTree.
java.util.Collection<V>	values() Returns a Collection view of the values contained in the KDTree.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

KDTree

public KDTree()

Creates a two-dimensional KDTree.

KDTree

public KDTree(int dimensions)

Creates a KDTree of the specified number of dimensions.

Parameters:

dimensions - The number of dimensions. Must be greater than 0.

Method Detail

clear

public void clear()

Removes all elements from the container, leaving it empty.

Specified by:

clear in interface java.util.Map<P extends Point<Coord>,V>

containsKey

public boolean containsKey(java.lang.Object key)
                    throws java.lang.ClassCastException

Returns true if the container contains a mapping for the specified key.

Specified by:

containsKey in interface java.util.Map<P extends Point<Coord>,V>

Parameters:

key - The point key to search for.

Returns:

true if the container contains a mapping for the specified key.

Throws:

java.lang.ClassCastException - if the key is not an instance of P.

containsValue

public boolean containsValue(java.lang.Object value)

Returns true if the container contains a mapping with the specified value. Note: this is very inefficient for KDTrees because it requires searching the entire tree.

Specified by:

containsValue in interface java.util.Map<P extends Point<Coord>,V>

Parameters:

value - The value to search for.

Returns:

true If the container contains a mapping with the specified value.

entrySet

public java.util.Set<java.util.Map.Entry<P,V>> entrySet()

Returns a Set view of the point to value mappings in the KDTree. Modifications to the resulting set will be reflected in the KDTree and vice versa, except that Iterator.remove is not supported.

Specified by:

entrySet in interface java.util.Map<P extends Point<Coord>,V>

Returns:

A Set view of the point to value mappings in the KDTree.

equals

public boolean equals(java.lang.Object o)
               throws java.lang.ClassCastException

Returns true if the object contains the same mappings, false if not.

Specified by:

equals in interface java.util.Map<P extends Point<Coord>,V>

Overrides:

equals in class java.lang.Object

Parameters:

o - The object to test for equality.

Returns:

true if the object contains the same mappings, false if not.

Throws:

java.lang.ClassCastException

get

public V get(java.lang.Object point)
      throws java.lang.ClassCastException

Retrieves the value at the given location.

Specified by:

get in interface java.util.Map<P extends Point<Coord>,V>

Parameters:

point - The location from which to retrieve the value.

Returns:

The value at the given location, or null if no value is present.

Throws:

java.lang.ClassCastException - If the given point is not of the expected type.

hashCode

public int hashCode()

Returns the hash code value for this map.

Specified by:

hashCode in interface java.util.Map<P extends Point<Coord>,V>

Overrides:

hashCode in class java.lang.Object

Returns:

The sum of the hash codes of all of the map entries.

isEmpty

public boolean isEmpty()

Returns true if the container has no elements, false if it contains one or more elements.

Specified by:

isEmpty in interface java.util.Map<P extends Point<Coord>,V>

Returns:

true if the container has no elements, false if it contains one or more elements.

keySet

public java.util.Set<P> keySet()

Returns a Set view of the point keys for the mappings in the KDTree. Changes to the Set are reflected in the KDTree and vice versa, except that Iterator.remove is not supported.

Specified by:

keySet in interface java.util.Map<P extends Point<Coord>,V>

Returns:

A Set view of the point keys for the mappings in the KDTree.

put

public V put(P point,
             V value)

Inserts a point value pair into the tree, preserving the spatial ordering.

Specified by:

put in interface java.util.Map<P extends Point<Coord>,V>

Parameters:

point - The point serving as a key.

value - The value to insert at the point.

Returns:

The old value if an existing value is replaced by the inserted value.

putAll

public void putAll(java.util.Map<? extends P,? extends V> map)

Copies all of the point-value mappings from the given Map into the KDTree.

Specified by:

putAll in interface java.util.Map<P extends Point<Coord>,V>

Parameters:

map - The Map from which to copy the mappings.

remove

public V remove(java.lang.Object key)
         throws java.lang.ClassCastException

Removes the point-value mapping corresponding to the given point key.

Specified by:

remove in interface java.util.Map<P extends Point<Coord>,V>

Parameters:

key - The point key of the mapping to remove.

Returns:

The value part of the mapping, if a mapping existed and was removed. Null if not.

Throws:

java.lang.ClassCastException - If the key is not an instance of P.

size

public int size()

Returns the number of point-value mappings in the KDTree.

Specified by:

size in interface java.util.Map<P extends Point<Coord>,V>

Returns:

The number of point-value mappings in the KDTree.

values

public java.util.Collection<V> values()

Returns a Collection view of the values contained in the KDTree. Changes to the Collection are reflected in the KDTree and vice versa. Note: the resulting Collection is very inefficient.

Specified by:

values in interface java.util.Map<P extends Point<Coord>,V>

Returns:

A Collection view of the values contained in the KDTree.

iterator

public java.util.Iterator<java.util.Map.Entry<P,V>> iterator(P lower,
                                                             P upper)

Description copied from interface: RangeSearchTree

Returns an iterator for mappings that are contained in the rectangle defined by the given lower left-hand and upper right-hand corners. The mappings returned include those occuring at points on the bounding rectangle, not just those inside.

Specified by:

iterator in interface RangeSearchTree<Coord extends java.lang.Comparable<? super Coord>,P extends Point<Coord>,V>

Parameters:

lower - The lower left-hand corner of the bounding rectangle. A null value can be used to specify the region is unbounded in that direction.

upper - The upper right-hand corner of the bounding rectangle. A null value can be used to specify the region is unbounded in that direction.

Returns:

An iterator for mappings that are contained in the specified rectangle.

optimize

public void optimize()

Optimizes the performance of future search operations by balancing the KDTree. The balancing operation is relatively expensive, but can significantly improve the performance of searches. Usually, you don't have to optimize a tree which contains random key values inserted in a random order.