readme

一个C++写的KdTree容器模板库

libkdtree++ README
==================

libkdtree++ is (c) 2004-2007 Martin F. Krafft <[e-mail]>
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 <[e-mail]>.

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
[e-mail] .

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髆ez 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.