00001 00010 00011 00012 #ifndef _CoverTree_H_ 00013 #define _CoverTree_H_ 00014 00015 00016 #include <Array/Array.h> 00017 #include <ReClaM/KernelFunction.h> 00018 00019 00032 class CoverTree 00033 { 00034 public: 00036 CoverTree(const Array<double>& points); 00037 00039 virtual ~CoverTree(); 00040 00041 00045 unsigned int OneNN(const Array<double>& query) const; 00046 00050 unsigned int SecondNN(unsigned int query) const; 00051 00059 void KNN(const Array<double>& query, unsigned int k, std::vector<unsigned int>& neighbors) const; 00060 00063 inline const ArrayReference<double> Point(unsigned int index) const 00064 { 00065 return (*points)[index]; 00066 } 00067 00074 virtual double distance2(const Array<double>& p1, const Array<double>& p2) const; 00075 00076 inline double distance(const Array<double>& p1, const Array<double>& p2) const 00077 { 00078 return sqrt(distance2(p1, p2)); 00079 } 00080 00081 protected: 00082 struct Node 00083 { 00084 unsigned int index; 00085 Node* firstchild; 00086 Node* nextsibling; 00087 int scale; 00088 }; 00089 00090 struct tNode 00091 { 00092 Node* node; 00093 double dist; 00094 }; 00095 00096 inline Node* freeNode() 00097 { 00098 Node* ret = &mem[usedmem]; 00099 usedmem++; 00100 return ret; 00101 } 00102 00103 void Insert(unsigned int index); 00104 00105 const Array<double>* points; 00106 Node* root; 00107 std::vector<Node> mem; 00108 unsigned int usedmem; 00109 00110 friend bool cmp(const tNode& n1, const tNode& n2); 00111 }; 00112 00113 00117 class KernelCoverTree : public CoverTree 00118 { 00119 public: 00122 KernelCoverTree(KernelFunction* kernel, const Array<double>& points); 00123 00125 ~KernelCoverTree(); 00126 00127 00129 double distance2(const Array<double>& p1, const Array<double>& p2) const; 00130 00131 protected: 00132 KernelFunction* kernel; 00133 }; 00134 00135 00136 #endif