|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectedu.wlu.cs.levy.CG.KDTree<T>
public class KDTree<T>
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:
@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} }
Constructor Summary | |
---|---|
KDTree(int k)
Creates a KD-tree with specified number of dimensions. |
|
KDTree(int k,
long timeout)
|
Method Summary | |
---|---|
void |
delete(double[] key)
|
void |
delete(double[] key,
boolean optional)
Delete a node from a KD-tree. |
void |
edit(double[] key,
edu.wlu.cs.levy.CG.Editor<T> editor)
Edit a node in a KD-tree |
void |
insert(double[] key,
T value)
Insert a node in a KD-tree. |
T |
nearest(double[] key)
Find KD-tree node whose key is nearest neighbor to key. |
java.util.List<T> |
nearest(double[] key,
int n)
Find KD-tree nodes whose keys are n nearest neighbors to key. |
java.util.List<T> |
nearest(double[] key,
int n,
edu.wlu.cs.levy.CG.Checker<T> checker)
Find KD-tree nodes whose keys are n nearest neighbors to key. |
java.util.List<T> |
nearestEuclidean(double[] key,
double dist)
Find KD-tree nodes whose keys are within a given Euclidean distance of a given key. |
java.util.List<T> |
nearestHamming(double[] key,
double dist)
Find KD-tree nodes whose keys are within a given Hamming distance of a given key. |
java.util.List<T> |
range(double[] lowk,
double[] uppk)
Range search in a KD-tree. |
T |
search(double[] key)
Find KD-tree node whose key is identical to key. |
int |
size()
|
java.lang.String |
toString()
|
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public KDTree(int k)
k
- number of dimensionspublic KDTree(int k, long timeout)
Method Detail |
---|
public void insert(double[] key, T value) throws KeySizeException, KeyDuplicateException
@Book{GonnetBaezaYates1991, author = {G.H. Gonnet and R. Baeza-Yates}, title = {Handbook of Algorithms and Data Structures}, publisher = {Addison-Wesley}, year = {1991} }
key
- key for KD-tree nodevalue
- value at that key
KeySizeException
- if key.length mismatches K
KeyDuplicateException
- if key already in treepublic void edit(double[] key, edu.wlu.cs.levy.CG.Editor<T> editor) throws KeySizeException, KeyDuplicateException
key
- key for KD-tree nodeeditor
- object to edit the value at that key
KeySizeException
- if key.length mismatches K
KeyDuplicateException
- if key already in treepublic T search(double[] key) throws KeySizeException
key
- key for KD-tree node
KeySizeException
- if key.length mismatches Kpublic void delete(double[] key) throws KeySizeException, KeyMissingException
KeySizeException
KeyMissingException
public void delete(double[] key, boolean optional) throws KeySizeException, KeyMissingException
key
- key for KD-tree nodeoptional
- if false and node not found, throw an exception
KeySizeException
- if key.length mismatches K
KeyMissingException
- if no node in tree has keypublic T nearest(double[] key) throws KeySizeException
key
- key for KD-tree node
KeySizeException
- if key.length mismatches Kpublic java.util.List<T> nearest(double[] key, int n) throws KeySizeException, java.lang.IllegalArgumentException
key
- key for KD-tree noden
- number of nodes to return
KeySizeException
- if key.length mismatches K
java.lang.IllegalArgumentException
public java.util.List<T> nearestEuclidean(double[] key, double dist) throws KeySizeException
key
- key for KD-tree noded
- Euclidean distance
KeySizeException
- if key.length mismatches Kpublic java.util.List<T> nearestHamming(double[] key, double dist) throws KeySizeException
key
- key for KD-tree noded
- Hamming distance
KeySizeException
- if key.length mismatches Kpublic java.util.List<T> nearest(double[] key, int n, edu.wlu.cs.levy.CG.Checker<T> checker) throws KeySizeException, java.lang.IllegalArgumentException
key
- key for KD-tree noden
- how many neighbors to findchecker
- an optional object to filter matches
KeySizeException
- if key.length mismatches K
java.lang.IllegalArgumentException
- if n is negative or
exceeds tree sizepublic java.util.List<T> range(double[] lowk, double[] uppk) throws KeySizeException
lowk
- lower-bounds for keyuppk
- upper-bounds for key
KeySizeException
- on mismatch among lowk.length, uppk.length, or Kpublic int size()
public java.lang.String toString()
toString
in class java.lang.Object
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |