|File Search||Catalog||Content Search|
libkdtree++-dev - C++ template container implementation of kd-tree sorting… more info»
libkdtree++ README ================== libkdtree++ is (c) 2004-2007 Martin F. Krafft <email@example.com> and distributed under the terms of the Artistic License 2.0. See the file LICENSE in the source distribution for more information. Please send bugreports to <firstname.lastname@example.org>. Introduction ------------ libkdtree++ is a C++ template container implementation of k-dimensional space sorting, using a kd-tree. It: - sports an unlimited number of dimensions (in theory) - can store any data structure, access and comparison between the individual dimensional components defaults to the bracket operator, in the range [0, k-1] and the std::less functor by default, but other accessors and comparator can be defined. - has support for custom allocators - implements iterators - provides standard find as well as range queries - has amortised O(lg n) time (O(n lg n) worst case) on most operations (insert/erase/find optimised) and worst-case O(n) space. - provides a means to rebalance and thus optimise the tree. - exists in its own namespace - uses STL coding style, basing a lot of the code on stl_tree.h Notes ----- Note that the library is not (yet) complete and it's not thoroughly tested. However, given the effort and grief I went through in writing it, I would like to make it available to folks, get people to test it, and hopefully have some peeps submit improvements. If you have any suggestions, please write to email@example.com . It's not yet documented, although the usage should be fairly straight forward. I am hoping to find someone else to document it as I suck at documentation and as the author, it's exceptionally difficult to stay didactically correct. Credits (Martin F. Kraft) ------------------------- While the library was written all by myself, it would not have been possible without the help of a number of people. Foremost, I would like to thank the folks from the #c++ channel on Freenode, specifically (in no particular order) orbitz, quix, Erwin, pwned, wcstok, dasOp, Chaku, Adrinael, The_Vulture, and LIM2 (if I left anyone out, let me know). Finally, I thank the Artificial Intelligence Laboratory of the University of Zurich, Dr. Peter Eggenberger and Gabriel G�mez for giving me the opportunity to write this stuff. Since libkdtree++ makes an effort to stay as close as possible to the feel of a STL container, concepts and inspiration was gained from the SGI C++ implementation of red-black trees (stl_tree.h). I also have to thank the Debian project for providing an amazingly reliable and flexible developer station with their operating system. I am sorry for everyone who has to use something else. Installation ------------ As there is no need to compile any files, you can just: $ ./configure $ sudo make install Read the following to make use of the library. Usage ----- A simple example program is provided in the ./examples directory (/usr/share/doc/libkdtree++-dev/examples on Debian). The library supports pkg-config. Thus, to compile with the library, #include <kdtree++/kdtree.hpp> and append the output of `pkg-config libkdtree++ --cflags` to your $CPPFLAGS. Each call to erase() and insert() unbalances the tree. It is possible that nodes will not be found while the tree is unbalanced. You rebalance the tree by calling optimize(), and you should call it before you need to search the tree (this includes erase(value) calls, which search the tree). It is ok to call insert(value) many times and optimize() at the end, but every erase() call should be followed with optimize(). Have fun.