//package edu.wlu.cs.levy.CG;
import java.util.List;
import java.util.LinkedList;
import java.util.Stack;
/**
* KDTree is a class supporting KD-tree insertion, deletion, equality
* search, range search, and nearest neighbor(s) using double-precision
* floating-point keys. Splitting dimension is chosen naively, by
* depth modulo K. Semantics are as follows:
*
*
* - Two different keys containing identical numbers should retrieve the
* same value from a given KD-tree. Therefore keys are cloned when a
* node is inserted.
*
* - As with Hashtables, values inserted into a KD-tree are not
* cloned. Modifying a value between insertion and retrieval will
* therefore modify the value stored in the tree.
*
*
* Implements the Nearest Neighbor algorithm (Table 6.4) of
*
*
* @techreport{AndrewMooreNearestNeighbor,
* author = {Andrew Moore},
* title = {An introductory tutorial on kd-trees},
* institution = {Robotics Institute, Carnegie Mellon University},
* year = {1991},
* number = {Technical Report No. 209, Computer Laboratory,
* University of Cambridge},
* address = {Pittsburgh, PA}
* }
*
*
*
* @author Simon Levy, Bjoern Heckel
* @version %I%, %G%
* @since JDK1.2
*/
public class KDTree
{
// number of milliseconds
final long m_timeout;
// K = number of dimensions
final private int m_K;
// root of KD-tree
private KDNode m_root;
// count of nodes
private int m_count;
/**
* Creates a KD-tree with specified number of dimensions.
*
* @param k number of dimensions
*/
public KDTree(int k)
{
this(k, 0);
}
public KDTree(int k, long timeout)
{
this.m_timeout = timeout;
m_K = k;
m_root = null;
}
/**
* Insert a node in a KD-tree. Uses algorithm translated from 352.ins.c of
*
*
* @Book{GonnetBaezaYates1991,
* author = {G.H. Gonnet and R. Baeza-Yates},
* title = {Handbook of Algorithms and Data Structures},
* publisher = {Addison-Wesley},
* year = {1991}
* }
*
*
* @param key key for KD-tree node
* @param value value at that key
*
* @throws KeySizeException if key.length mismatches K
* @throws KeyDuplicateException if key already in tree
*/
public void insert(double[] key, T value)
throws KeySizeException, KeyDuplicateException
{
this.edit(key, new Editor.Inserter(value));
}
/**
* Edit a node in a KD-tree
*
* @param key key for KD-tree node
* @param editor object to edit the value at that key
*
* @throws KeySizeException if key.length mismatches K
* @throws KeyDuplicateException if key already in tree
*/
public void edit(double[] key, Editor editor)
throws KeySizeException, KeyDuplicateException
{
if (key.length != m_K)
{
throw new KeySizeException();
}
synchronized (this)
{
// the first insert has to be synchronized
if (null == m_root)
{
m_root = KDNode.create(new HPoint(key), editor);
m_count = m_root.deleted ? 0 : 1;
return;
}
}
m_count += KDNode.edit(new HPoint(key), editor, m_root, 0, m_K);
}
/**
* Find KD-tree node whose key is identical to key. Uses algorithm
* translated from 352.srch.c of Gonnet & Baeza-Yates.
*
* @param key key for KD-tree node
*
* @return object at key, or null if not found
*
* @throws KeySizeException if key.length mismatches K
*/
public T search(double[] key) throws KeySizeException
{
if (key.length != m_K)
{
throw new KeySizeException();
}
KDNode kd = KDNode.srch(new HPoint(key), m_root, m_K);
return (kd == null ? null : kd.v);
}
public void delete(double[] key)
throws KeySizeException, KeyMissingException
{
delete(key, false);
}
/**
* Delete a node from a KD-tree. Instead of actually deleting node and
* rebuilding tree, marks node as deleted. Hence, it is up to the caller
* to rebuild the tree as needed for efficiency.
*
* @param key key for KD-tree node
* @param optional if false and node not found, throw an exception
*
* @throws KeySizeException if key.length mismatches K
* @throws KeyMissingException if no node in tree has key
*/
public void delete(double[] key, boolean optional)
throws KeySizeException, KeyMissingException
{
if (key.length != m_K)
{
throw new KeySizeException();
}
KDNode t = KDNode.srch(new HPoint(key), m_root, m_K);
if (t == null)
{
if (optional == false)
{
throw new KeyMissingException();
}
} else
{
if (KDNode.del(t))
{
m_count--;
}
}
}
/**
* Find KD-tree node whose key is nearest neighbor to
* key.
*
* @param key key for KD-tree node
*
* @return object at node nearest to key, or null on failure
*
* @throws KeySizeException if key.length mismatches K
*/
public T nearest(double[] key, int n) throws KeySizeException
{
List nbrs = nearest(key, n, null);
int nearpoint = 0; // n-1;
// if (nbrs.size() == 0)
// nearpoint = 0;
//
// if (nbrs.get(nearpoint).equals(key))
// nearpoint = 1;
return nbrs.get(nearpoint);
}
/**
* Find KD-tree nodes whose keys are n nearest neighbors to
* key.
*
* @param key key for KD-tree node
* @param n number of nodes to return
*
* @return objects at nodes nearest to key, or null on failure
*
* @throws KeySizeException if key.length mismatches K
*/
// public List nearest(double[] key, int n)
// throws KeySizeException, IllegalArgumentException
// {
// return nearest(key, n, null);
// }
/**
* Find KD-tree nodes whose keys are within a given Euclidean distance of
* a given key.
*
* @param key key for KD-tree node
* @param d Euclidean distance
*
* @return objects at nodes with distance of key, or null on failure
*
* @throws KeySizeException if key.length mismatches K
*/
public List nearestEuclidean(double[] key, double dist)
throws KeySizeException
{
return nearestDistance(key, dist, new EuclideanDistance());
}
/**
* Find KD-tree nodes whose keys are within a given Hamming distance of
* a given key.
*
* @param key key for KD-tree node
* @param d Hamming distance
*
* @return objects at nodes with distance of key, or null on failure
*
* @throws KeySizeException if key.length mismatches K
*/
public List nearestHamming(double[] key, double dist)
throws KeySizeException
{
return nearestDistance(key, dist, new HammingDistance());
}
/**
* Find KD-tree nodes whose keys are n nearest neighbors to
* key. Uses algorithm above. Neighbors are returned in ascending
* order of distance to key.
*
* @param key key for KD-tree node
* @param n how many neighbors to find
* @param checker an optional object to filter matches
*
* @return objects at node nearest to key, or null on failure
*
* @throws KeySizeException if key.length mismatches K
* @throws IllegalArgumentException if n is negative or
* exceeds tree size
*/
public List nearest(double[] key, int n, CheckerInterface checker)
throws KeySizeException, IllegalArgumentException
{
if (n <= 0)
{
return new LinkedList();
}
NearestNeighborList> nnl = getnbrs(key, n, checker);
n = nnl.getSize();
Stack nbrs = new Stack();
for (int i = 0; i < n; ++i)
{
KDNode kd = nnl.removeHighest();
nbrs.push(kd.v);
}
return nbrs;
}
/**
* Range search in a KD-tree. Uses algorithm translated from
* 352.range.c of Gonnet & Baeza-Yates.
*
* @param lowk lower-bounds for key
* @param uppk upper-bounds for key
*
* @return array of Objects whose keys fall in range [lowk,uppk]
*
* @throws KeySizeException on mismatch among lowk.length, uppk.length, or K
*/
public List range(double[] lowk, double[] uppk)
throws KeySizeException
{
if (lowk.length != uppk.length)
{
throw new KeySizeException();
} else if (lowk.length != m_K)
{
throw new KeySizeException();
} else
{
List> found = new LinkedList>();
KDNode.rsearch(new HPoint(lowk), new HPoint(uppk),
m_root, 0, m_K, found);
List o = new LinkedList();
for (KDNode node : found)
{
o.add(node.v);
}
return o;
}
}
public int size()
{ /* added by MSL */
return m_count;
}
public String toString()
{
return m_root.toString(0);
}
private NearestNeighborList> getnbrs(double[] key)
throws KeySizeException
{
return getnbrs(key, m_count, null);
}
private NearestNeighborList> getnbrs(double[] key, int n,
CheckerInterface checker) throws KeySizeException
{
if (key.length != m_K)
{
throw new KeySizeException();
}
NearestNeighborList> nnl = new NearestNeighborList>(n);
// initial call is with infinite hyper-rectangle and max distance
HRect hr = HRect.infiniteHRect(key.length);
double max_dist_sqd = Double.MAX_VALUE;
HPoint keyp = new HPoint(key);
if (m_count > 0)
{
long timeout = (this.m_timeout > 0)
? (System.currentTimeMillis() + this.m_timeout)
: 0;
KDNode.nnbr(m_root, keyp, hr, max_dist_sqd, 0, m_K, nnl, checker, timeout);
}
return nnl;
}
private List nearestDistance(double[] key, double dist,
DistanceMetric metric) throws KeySizeException
{
NearestNeighborList> nnl = getnbrs(key);
int n = nnl.getSize();
Stack nbrs = new Stack();
for (int i = 0; i < n; ++i)
{
KDNode kd = nnl.removeHighest();
HPoint p = kd.k;
if (metric.distance(kd.k.coord, key) < dist)
{
nbrs.push(kd.v);
}
}
return nbrs;
}
}