Sorry for the delay in responding to the above request... I've been rather busy lately.
Okay, I've stripped out my kdtree implementation from one of my projects. What is presented herein is barebones stuff. To use it, you need to add functionality to the kdtree class appropriate to the task at hand. The code below is offered "as is" and no warranties or support are offered. Use it at your own risk. I've included a little test program that should run compile with 0 errors and 0 warnings under VC++ 7.0 and run cleanly with no memory leaks. It shows you some of the basic ways to create a tree using the supplied classes.
If you want a more full-blooded example of the use of this code (as in, for a nearest neighbour search) I might be prepared to share example code, but only if I know it is to be used for non-commericial or research purposes (but not for school assignments). Send me an email if you need this with an explanation as to why.
Anyway, here it is...
treetype_kdtree.h/* ************************************************************************** * * * Module: kdtree.h * * * * Author: Tim Wilkin * * (c) March, 2004 * * * * Last Modified: 20 Apr 2006 * * * * This header declares the templated data storage classes * * kdnode * * kdtree * * * ************************************************************************** */#pragma once#include <algorithm>#include "treetype_utility.h"// define a (hopefully) unique namespacenamespace TreeTypes{ /* ****************************************************************************** * kdnode class * ****************************************************************************** */ template <typename BinType> struct kdnode{ typedef BinType bin_type; typedef typename bin_type::value_type vector_type; typedef typename vector_type::value_type scalar_type; typedef typename bin_type::size_type size_type; typedef typename bin_type::iterator iterator; typedef typename bin_type::const_iterator const_iterator; typedef typename bin_type::reverse_iterator reverse_iterator; typedef typename bin_type::const_reverse_iterator const_reverse_iterator; kdnode *left, * right; bin_type *data; size_type keyID; scalar_type keyPartition; static size_type leafSize; kdnode():left(NULL), right(NULL), data(NULL), keyID(0), keyPartition(0){} kdnode(bin_type* _bin); ~kdnode(); bool isLeaf() const { return !this->left && !this->right;} }; //<== End kdnode class declaration /* ****************************************************************************** * kdtree class * ****************************************************************************** */ template <typename BinType> class kdtree{ public: typedef BinType bin_type; typedef kdnode<bin_type> node_type; typedef typename bin_type::value_type vector_type; private: node_type* root; public: kdtree(); kdtree(const bin_type& _data, const size_t& leafsize=10); ~kdtree(); }; // <== End kdtree class declaration // define the kdnode static member leafSize template <typename V> typename kdnode<V>::size_type kdnode<V>::leafSize; /* ****************************************************************************** * kdnode methods * ****************************************************************************** */ template <typename B> kdnode<B>::kdnode(bin_type* _data){ this->keyID = size_type(0); this->keyPartition = scalar_type(0); if (_data->size()<=kdnode<B>::leafSize){ this->data = _data; this->left = NULL; this->right = NULL; } else{ vector_type mu = mean<bin_type>(_data->begin(),_data->end()); vector_type var = variance<bin_type>(_data->begin(),_data->end()); scalar_type m = 0; for (size_type i=0;i<var.size();i++){ if (var>m){ m=var; this->keyID=i; } } this->keyPartition = mu[this->keyID]; iterator spliceIter = std::partition( _data->begin(), _data->end(), std::bind2nd(less<vector_type>(this->keyID), this->keyPartition ) ); bin_type* right = new bin_type(); right->splice(right->end(),*_data,spliceIter,_data->end()); if (right->size()==0){ this->data = _data; this->left = NULL; this->right = NULL; } else if (_data->size()==0){ this->data = right; this->left = NULL; this->right = NULL; } else{ this->data = NULL; this->left = new kdnode(_data); this->right = new kdnode(right); } } } // <== end kdnode constructor definition template <typename B> kdnode<B>::~kdnode(){ if (this->isLeaf()){ if (!data->empty()) data->clear(); delete data; } else{ if (this->left){ delete this->left; this->left = 0; } if (this->right){ delete this->right; this->right = 0; } } } // <== end kdnode destructor definition /* ****************************************************************************** * kdtree methods * ****************************************************************************** */ template <typename B> kdtree<B>::kdtree(){ root = new node_type(); } template <typename B> kdtree<B>::kdtree(const typename kdtree<B>::bin_type& _data, const size_t& leafsize){ node_type::leafSize = leafsize; bin_type* pBin = new bin_type(_data); root = new node_type(pBin); } template <typename B> kdtree<B>::~kdtree(){ delete root; }} // <== End TreeTypes namespace declaration
/* ************************************************************************** * * * Module: treetype_utility.h * * * * Author: Tim Wilkin * * (c) March, 2004 * * * * Last Modified: 30 May 2006 * * * * This header declares template utility functions and classes * * for use in treetype_kdtree * * * ************************************************************************** */#pragma once/* ****************************************************************************** * utility functions * ****************************************************************************** * * These functions make certain assumptions about the type SetType::value_type, * that is, the type herein called vector_type. This type must support the * following operations: * constructors: * default - vector_type() * sized - vector_type(const scalar_type &, const size_type&) * copy - vector_type(const vector_type&) * * mathematical operators: * operator+= * operator-= * operator/= * operator* * * An example of a type that supports these methods is std::valarray*/template <typename SetType>typename SetType::value_type mean(typename SetType::const_iterator& first, typename SetType::const_iterator& last){ typedef SetType::value_type vector_type; typedef vector_type::value_type scalar_type; SetType::difference_type d = std::distance(first,last); if (d==0) return vector_type(); else if (d==1) return *first; else{ size_t dim = first->size(); vector_type buffer(*first); SetType::const_iterator setIter = first; setIter++; for (; setIter!=last; setIter++) buffer += *setIter; return buffer/=(scalar_type)d; }}template <typename SetType>typename SetType::value_type variance(typename SetType::const_iterator& first, typename SetType::const_iterator& last){ typedef SetType::value_type vector_type; typedef vector_type::value_type scalar_type; SetType::difference_type d = std::distance(first,last); if (d==0) return vector_type(); else{ size_t dim = first->size(); vector_type sum((scalar_type)0,dim); if (d==1) return sum; else{ vector_type mu(mean<SetType>(first,last)); SetType::const_iterator setIter = first; for (; setIter!=last; setIter++){ vector_type buffer(*setIter); buffer -= mu; sum += (buffer * buffer); } return sum/=(scalar_type)(d-1); // unbiased variance } }}/* ****************************************************************************** * utility classes * ****************************************************************************** * * less<VectorType> is a simple functor providing an indexed less than operator * for objects of a vector class. This functor assumes that VectorType supports * subscripted indexing via VectorType::operator[](const size_t& i). * */template <typename VectorType>class less: public std::binary_function<VectorType, typename VectorType::value_type, bool>{ public: typedef VectorType vector_type; typedef typename vector_type::value_type value_type; private: const size_t index; public: less(const size_t& i):index(i){}; bool operator()(const vector_type& vec, const value_type& val) const{ return vec[index]<val; }};
/* ************************************************************************** * * * Module: bin.h * * * * Author: Tim Wilkin * * (c) March, 2004 * * * * Last Modified: 30 May 2006 * * * * This header declares the template data storage class kdbin * * * ************************************************************************** */#pragma once// required headers, since kdbin is just an adaptor for std::list in this example// You could do anything with this class, so long as it maintains this interface// (or you appropriately change the kdnode class)#include <list>/* ****************************************************************************** * kdbin class * ****************************************************************************** * * kdbin is an example of a custom bin class that could be used with the * kdtree class. It shows the minimum interface required by the tree * constructors*/template <typename VectorType>class kdbin{ public: typedef VectorType value_type; typedef std::list<value_type> container_type; typedef typename container_type::size_type size_type; typedef typename container_type::iterator iterator; typedef typename container_type::const_iterator const_iterator; typedef typename container_type::reverse_iterator reverse_iterator; typedef typename container_type::const_reverse_iterator const_reverse_iterator; typedef typename container_type::difference_type difference_type; private: container_type bin; public: kdbin(); ~kdbin(); kdbin(const kdbin& rhs); kdbin& operator=(const kdbin& rhs); const size_type size() const; bool empty() const; void insert(iterator _Where, const value_type& _Value); void push_back(const value_type& _Value); void splice(iterator _Where, kdbin& _Right, iterator _First, iterator _Last); void erase(iterator _Where); void clear(); iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const;}; //<== End class declaration/* ****************************************************************************** * kdbin methods * *******************************************************************************/// constructor (default)template <typename V>kdbin<V>::kdbin():bin(){}// destructortemplate <typename V>kdbin<V>::~kdbin(){ bin.clear();}// constructor (copy)template <typename V>kdbin<V>::kdbin(const kdbin<V>& rhs){ if (&rhs!=this){ if (!this->bin.empty()) bin.clear(); const_iterator rhsIter = rhs.begin(); for (; rhsIter!=rhs.end(); rhsIter++) bin.push_back(*rhsIter); }}// operator (assignment)template <typename V>kdbin<V>& kdbin<V>::operator =(const kdbin<V>& rhs){ if (&rhs!=this){ this->bin = rhs.bin; this->buf = rhs.buf; } return *this;}// method (size)// returns number of elements in bintemplate <typename V>const typename kdbin<V>::size_type kdbin<V>::size() const{ return bin.size();}// method (empty)// returns true if size==0template <typename V>bool kdbin<V>::empty() const{ return bin.empty();}// method (insert)// insert a vector at the given positiontemplate <typename V>void kdbin<V>::insert(iterator _Where, const value_type& _Value){ bin.insert(_Where, _Value);}// method (push_back)// insert a vector after the last vector currently storedtemplate <typename V>void kdbin<V>::push_back(const value_type& _Value){ bin.push_back(_Value);}// method (splice)// remove vectors from the argument bin (_right), starting at _first and ending// at last vector before _last, then insert them into the target bin (this->bin)template <typename V>void kdbin<V>::splice(iterator _where, kdbin<V>& _right, iterator _first, iterator _last){ bin.splice(_where,_right.bin,_first,_last);}template <typename V>void kdbin<V>::erase(iterator _Where){ bin.erase(_Where);}// method (clear)// delete all vectors stored in the bintemplate <typename V>void kdbin<V>::clear(){ bin.clear();}// method (begin)// return iterator pointing to first stored vectortemplate <typename V>typename kdbin<V>::iterator kdbin<V>::begin(){ return bin.begin();}// method (end)// return iterator pointing one beyond last stored vectortemplate <typename V>typename kdbin<V>::iterator kdbin<V>::end(){ return bin.end();}// method (begin) (const)// return a constant iterator pointing to first stored objecttemplate <typename V>typename kdbin<V>::const_iterator kdbin<V>::begin() const{ return bin.begin();}// method (end) (const)// return constant iterator pointing one beyond last stored vectortemplate <typename V>typename kdbin<V>::const_iterator kdbin<V>::end() const{ return bin.end();}
// include time.h and stdio.h just for this example#include <time.h>#include <stdio.h>#include <valarray>// use either an STL container like std::list<>, or a custom container like kdbin<>#include "bin.h"#include <list>// include kdtree.h for tree template classes#include "treetype_kdtree.h"int main(void){ typedef float value_type; typedef std::valarray<value_type> vector_type;// typedef kdbin<vector_type> bin_type; typedef std::list<vector_type> bin_type; typedef TreeTypes::kdtree< bin_type> tree_type; bin_type data; vector_type tmpVec(3); srand( (unsigned)time( NULL ) ); for (size_t i=0; i<16; i++){ for (size_t j=0; j<tmpVec.size(); j++) tmpVec[j] = (value_type)(2 * rand() - RAND_MAX) / (value_type)RAND_MAX; data.push_back(tmpVec); } // test the creation and destruction of a dynamic tree object tree_type *pTree = new tree_type(data,25); delete pTree; // test the use of the tree as a heap object tree_type myTree(data); // now test the ability to directly create a tree as a dynamic, recursivel constructed // kdnode object bin_type *pBin = new bin_type(data); tree_type::node_type *pNode = new tree_type::node_type(pBin); delete pNode; // be careful here, since pBin is cleaned up when you delete the root node of the tree // and hence pBin itself now points to inaccessible memory... trying to derefence it // now would cause a segmentation fault... hence the use of the kdtree class to wrap // the recursive creation of the tree from a static source object (data) safely // now try building a tree using a std::list<> as the bin type! //typedef std::list<vector_type> list_type; //list_type myList(data.begin(),data.end()); //TreeTypes::kdtree<list_type> *pRoot = new TreeTypes::kdtree<list_type>(myList); //delete pRoot; return 0;}
