libkdtree++

About

libkdtree++ is an STL-like C++ template container implementation of k-dimensional space sorting, using a kd-tree. It sports a theoretically unlimited number of dimensions, and can store any data structure. Provided the data structure, it provides operator[0 - k-1] to access the individual dimensional components (arrays, std::vector already do) and a std::less implementation for the type of dimensional components. It has support for custom allocators, implements iterators, and provides standard find as well as range queries. It 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, and also provides a means to rebalance and thus optimise the tree.

The library is in a usable state, but very unlikely bug-free.

libkdtree++ was written in 2004 by Martin F. Krafft. Paul Harris has made some valuable contributions after its first release. Martin switched fields of research in 2005 and never needed the code again, letting it rot. In 2007, Sylvain Bougerel stepped up to take over maintenance.

libkdtree++ is © 2004-2007 Martin F. Krafft. Parts of kdtree++.hpp are © 2004 Paul Harris. Parts of the code are © 2007 Sylvain Bougerel. It is released under the terms of the Artistic License 2.0.

News

25 Nov 2007: fixed the reverse_iterator. Now it can be used. Moreover I’ve added some tarballs for those who do not have git.

24 Oct 2007: An update of the library is now available. That update features numerous of enhancements by Paul Harris:

Additionally, the library will not raise any warnings when compiled with the flags:

  -Wall -pedantic -ansi

29 Sep 2007: Sylvain Bougerel spent some time cleaning up the code and build infrastructure of the code from Sourceforge, and I imported the results of his work to a git repository on git.debian.org today. Unfortunately, I had to give up the history because the GNU arch repository I had used in between was corrupted.

Getting the source

For now, please obtain the source directly from the git repository:

git clone git://git.debian.org/git/libkdtree/libkdtree.git

Alternatively you can get either of the tarball:

Commit messages are sent to this mailinglist, so if you like to receive emails when changes are commited, subscribe there.

You can also browse the code online.

Example

A simple example/test programme is included with the code. Its output (on i386) is as follows:

meta node:   0x8053008 (0,0,0); parent: 0x8053028; left: 0x8053148; right: 0x8053108
nodes total: 10
dimensions:  3
0x8053028 (5,4,0); parent: 0x8053008; left: 0x8053048; right: 0x8053068
0x8053068 (7,6,9); parent: 0x8053028; left: 0x80530a8; right: 0x80530c8
0x80530c8 (5,7,0); parent: 0x8053068; left: 0; right: 0x8053108
0x8053108 (9,7,3); parent: 0x80530c8; left: 0; right: 0
0x80530a8 (8,0,5); parent: 0x8053068; left: 0; right: 0
0x8053048 (4,2,1); parent: 0x8053028; left: 0x8053148; right: 0x8053088
0x8053088 (2,2,1); parent: 0x8053048; left: 0; right: 0x80530e8
0x80530e8 (3,3,8); parent: 0x8053088; left: 0x8053128; right: 0
0x8053128 (2,2,6); parent: 0x80530e8; left: 0; right: 0
0x8053148 (2,0,6); parent: 0x8053048; left: 0; right: 0


meta node:   0x8053008 (0,0,0); parent: 0x8053148; left: 0x80530e8; right: 0x8053068
nodes total: 6
dimensions:  3
0x8053148 (7,6,9); parent: 0x8053008; left: 0x8053128; right: 0x8053068
0x8053068 (9,7,3); parent: 0x8053148; left: 0x8053108; right: 0
0x8053108 (8,0,5); parent: 0x8053068; left: 0; right: 0
0x8053128 (2,2,6); parent: 0x8053148; left: 0x80530e8; right: 0x80530a8
0x80530a8 (3,3,8); parent: 0x8053128; left: 0; right: 0
0x80530e8 (2,0,6); parent: 0x8053128; left: 0; right: 0

counted 1 nodes within range 3 of (5,4,3).
found   1 nodes within range 3 of (5,4,3).
(2,2,6)

Nearest to (5,4,3): (2,2,6)
Nearest to (10,10,2): (9,7,3)

meta node:   0x8053008 (0,0,0); parent: 0x8053148; left: 0x80530e8; right: 0x8053068
nodes total: 6
dimensions:  3
0x8053148 (7,6,9); parent: 0x8053008; left: 0x8053128; right: 0x8053068
0x8053068 (9,7,3); parent: 0x8053148; left: 0x8053108; right: 0
0x8053108 (8,0,5); parent: 0x8053068; left: 0; right: 0
0x8053128 (2,2,6); parent: 0x8053148; left: 0x80530e8; right: 0x80530a8
0x80530a8 (3,3,8); parent: 0x8053128; left: 0; right: 0
0x80530e8 (2,0,6); parent: 0x8053128; left: 0; right: 0

Support

Please direct all enquiries about libkdtree++ to the mailing list, which is archived. Posting is limited to subscribers only.

Contributing

We welcome any contributions in the form of patches. To submit a patch, please follow these guidelines. The procedure is roughly as follows:

First, the setup, which you only have to do once on each machine you work with:

# leave out --global if you want to set your identity only for libkdtree++
git config --global user.name 'your name'
git config --global user.email 'your@email.address'
# the next two are not needed but ensure that git does not send patches to
# your own email address.
git config sendemail.signedoffcc false
git config sendemail.suppressfrom true
git clone git://git.debian.org/git/libkdtree/libkdtree.git

To make changes to the code, bring your local clone up to date, create a throwaway branch and do your work on it.

git pull
git checkout -b some-name-identifying-my-work
# while not finished:
  # if resuming after a while, maybe update your branch:
  # git rebase master
  // edit files
  git add files
  git commit
# end

After you’ve brought your change to a state where you want to submit it, please squash it into logical single commits. If you only made one change, then this will do:

git checkout -b temp-squash master
git merge --squash some-name-identifying-my-work
git commit // ... remove the "Squashed commit of the following:" leader
git format-patch -M -s master
// now inspect the files this created in $PWD
// when you're ready to submit, do:
git send-email --to your@email.address 
// check that it's okay when it arrives
git send-email --to libkdtree-devel@lists.alioth.debian.org

For multiple logical changes, cherry-pick or squash-merge every commit belonging to a change to the integration branch and then commit it. Also, read the git-send-email manpage in case you’re submitting multiple logical changes, in case you want to thread them.

The manpage also includes information about adding a prologue message explaining your patch, or how to insert it into an existing thread (in-reply-to).

Developers with write access to the repository may also push their changes, using the ssh transport instead of the git protocol. If you contribute a lot, we will gladly give you write access.

Webpage

This webpage is managed with Joey’s awesome ikiwiki and git. You can browse the source or clone it:

git clone git://git.debian.org/git/libkdtree/ikiwiki.git

Patches welcome. Or just hit the ‘Edit’ button at the top and make the changes through the web; it’s a wiki, after all!

Links