kdtree.hpp

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

/** \file
 * Defines the interface for the KDTree class.
 *
 * \author Martin F. Krafft <[e-mail]>
 *
 * Paul Harris figured this stuff out (below)
 * Notes:
 * This is similar to a binary tree, but its not the same.
 * There are a few important differences:
 *
 *  * Each level is sorted by a different criteria (this is fundamental to the design).
 *
 *  * It is possible to have children IDENTICAL to its parent in BOTH branches
 *    This is different to a binary tree, where identical children are always to the right
 *    So, KDTree has the relationships:
 *    * The left branch is <= its parent (in binary tree, this relationship is a plain < )
 *    * The right branch is <= its parent (same as binary tree)
 *
 *    This is done for mostly for performance.
 *    Its a LOT easier to maintain a consistent tree if we use the <= relationship.
 *    Note that this relationship only makes a difference when searching for an exact
 *    item with find() or find_exact, other search, erase and insert functions don't notice
 *    the difference.
 *
 *    In the case of binary trees, you can safely assume that the next identical item
 *    will be the child leaf,
 *    but in the case of KDTree, the next identical item might
 *    be a long way down a subtree, because of the various different sort criteria.
 *
 *    So erase()ing a node from a KDTree could require serious and complicated
 *    tree rebalancing to maintain consistency... IF we required binary-tree-like relationships.
 *
 *    This has no effect on insert()s, a < test is good enough to keep consistency.
 *
 *    It has an effect on find() searches:
 *      * Instead of using compare(child,node) for a < relationship and following 1 branch,
 *        we must use !compare(node,child) for a <= relationship, and test BOTH branches, as
 *        we could potentially go down both branches.
 *
 *    It has no real effect on bounds-based searches (like find_nearest, find_within_range)
 *    as it compares vs a boundary and would follow both branches if required.
 *
 *    This has no real effect on erase()s, a < test is good enough to keep consistency.
 */

#ifndef INCLUDE_KDTREE_KDTREE_HPP
#define INCLUDE_KDTREE_KDTREE_HPP

#include <vector>

#ifdef KDTREE_DEFINE_OSTREAM_OPERATORS
#  include <ostream>
#  include <stack>
#endif

#include <cmath>
#include <cstddef>
#include <cassert>

#include <kdtree++/accessor.hpp>
#include <kdtree++/allocator.hpp>
#include <kdtree++/iterator.hpp>
#include <kdtree++/node.hpp>
#include <kdtree++/region.hpp>

namespace KDTree
{

#ifdef KDTREE_CHECK_PERFORMANCE
   size_t num_dist_calcs = 0;
#endif


  template <size_t const __K, typename _Val,
            typename _Acc = _Bracket_accessor<_Val>,
            typename _Cmp = std::less<typename _Acc::result_type>,
            typename _Alloc = std::allocator<_Node<_Val> > >
    class KDTree : protected _Alloc_base<_Val, _Alloc>
    {
    protected:
      // typedef _Alloc allocator_type;
      typedef _Alloc_base<_Val, _Alloc> _Base;
      typedef typename _Base::allocator_type allocator_type;

      typedef _Node_base* _Base_ptr;
      typedef _Node_base const* _Base_const_ptr;
      typedef _Node<_Val>* _Link_type;
      typedef _Node<_Val> const* _Link_const_type;

      typedef _Node_compare<_Val, _Acc, _Cmp> _Node_compare;

      typedef _Region<__K, _Val, typename _Acc::result_type, _Acc, _Cmp>
        _Region;

    public:
      typedef _Region Region;
      typedef _Val value_type;
      typedef value_type* pointer;
      typedef value_type const* const_pointer;
      typedef value_type& reference;
      typedef value_type const& const_reference;
      typedef typename _Acc::result_type subvalue_type;
      typedef subvalue_type distance_type;   // NEW TYPE - for returning distances
      // I wanted to distinguish it from subvaluetype, for the future when/if we have
      // types that need a fancy distance calculation.
      // This is not complete yet, eg Region still uses subvalue_type for distance_type.
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;

      KDTree( _Acc const& acc = _Acc(), const allocator_type& __a = allocator_type()) throw ()
        : _Base(__a), _M_header(_Base::_M_allocate_node()), _M_count(0), _M_acc(acc)
      {
         _M_empty_initialise();
      }

      KDTree(const KDTree& __x) throw ()
         : _Base(__x.get_allocator()), _M_header(_Base::_M_allocate_node()), _M_count(0), _M_acc(__x._M_acc)
      {
         _M_empty_initialise();
         this->insert(begin(), __x.begin(), __x.end());
         this->optimise();
      }

      template<typename _InputIterator>
        KDTree(_InputIterator __first, _InputIterator __last,
             _Acc const& acc = _Acc(), const allocator_type& __a = allocator_type()) throw ()
        : _Base(__a), _M_header(_Base::_M_allocate_node()), _M_count(0), _M_acc(acc)
      {
         _M_empty_initialise();
         this->insert(begin(), __first, __last);
         this->optimise();
      }

      KDTree&
      operator=(const KDTree& __x)
      {
         if (this != &__x)
         {
            this->clear();
            this->insert(begin(),__x.begin(),__x.end());
            this->optimize();
         }
         return *this;
      }

      ~KDTree() throw ()
      {
        this->clear();
        _M_deallocate_node(_M_header);
      }

      allocator_type
      get_allocator() const
      {
        return _Base::get_allocator();
      }

      size_type
      size() const
      {
        return _M_count;
      }

      size_type
      max_size() const
      {
        return size_type(-1);
      }

      bool
      empty() const
      {
        return this->size() == 0;
      }

      void
      clear()
      {
        _M_erase_subtree(_M_get_root());
        _M_set_leftmost(_M_header);
        _M_set_rightmost(_M_header);
        _M_set_root(NULL);
        _M_count = 0;
      }

      // typedef _Iterator<_Val, reference, pointer> iterator;
      typedef _Iterator<_Val, const_reference, const_pointer> const_iterator;
      // No mutable iterator at this stage
      typedef const_iterator iterator;

      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
      typedef std::reverse_iterator<iterator> reverse_iterator;

      const_iterator begin() const { return const_iterator(_M_get_leftmost()); }
      const_iterator end() const { return const_iterator(_M_header); }
      const_reverse_iterator rbegin() const { return const_reverse_iterator(_M_get_rightmost()); }
      const_reverse_iterator rend() const { return const_reverse_iterator(_M_header); }

      // iterator begin() { return iterator(_M_get_leftmost()); }
      // iterator end() { return iterator(_M_header); }
      // reverse_iterator rbegin() { return reverse_iterator(end()); }
      // reverse_iterator rend() { return reverse_iterator(begin()); }

      iterator
      insert(iterator /* ignored */, const_reference __V) throw (std::bad_alloc)
      {
         return this->insert(__V);
      }

      iterator
      insert(const_reference __V) throw (std::bad_alloc)
      {
        if (!_M_get_root())
          {
            _Link_type __n = _M_new_node(__V, _M_header);
            ++_M_count;
            _M_set_root(__n);
            _M_set_leftmost(__n);
            _M_set_rightmost(__n);
            return iterator(__n);
          }
        return _M_insert(_M_get_root(), __V, 0);
      }

      template <class _InputIterator>
      void insert(_InputIterator __first, _InputIterator __last) {
         for (; __first != __last; ++__first)
            this->insert(*__first);
      }

      void
      insert(iterator __pos, size_type __n, const value_type& __x)
      {
        for (; __n > 0; --__n)
          this->insert(__pos, __x);
      }

      template<typename _InputIterator>
      void
      insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
         for (; __first != __last; ++__first)
            this->insert(__pos, *__first);
      }

      // Note: this uses the find() to location the item you want to erase.
      // find() compares by equivalence of location ONLY.  See the comments
      // above find_exact() for why you may not want this.
      //
      // If you want to erase ANY item that has the same location as __V,
      // then use this function.
      //
      // If you want to erase a PARTICULAR item, and not any other item
      // that might happen to have the same location, then you should use
      // erase_exact().
      void
      erase(const_reference __V) throw () {
        this->erase(this->find(__V));
      }

      void
      erase_exact(const_reference __V) throw () {
        this->erase(this->find_exact(__V));
      }

      // note: kept as const because its easier to const-cast it away
      void
      erase(const_iterator const& __IT) throw ()
      {
         assert(__IT != this->end());
        _Link_const_type target = static_cast<_Link_const_type>(__IT._M_node);
        _Link_const_type n = target;
        size_t level = 0;
        while ((n = _S_parent(n)) != _M_header)
           ++level;
        _M_erase( const_cast<_Link_type>(target), level );
        _M_delete_node( const_cast<_Link_type>(target) );
        --_M_count;
      }

/* this does not work since erasure changes sort order
      void
      erase(const_iterator __A, const_iterator const& __B) throw ()
      {
        if (0 && __A == this->begin() && __B == this->end())
          {
            this->clear();
          }
        else
          {
            while (__A != __B)
              this->erase(__A++);
          }
      }
*/

      // compares via equivalence
      // so if you are looking for any item with the same location,
      // according to the standard accessor comparisions,
      // then this is the function for you.
      const_iterator
      find(const_reference __V) const throw ()
      {
        if (!_M_get_root()) return this->end();
        return _M_find(_M_get_root(), __V, 0);
      }

      // compares via equality
      // if you are looking for a particular item in the tree,
      // and (for example) it has an ID that is checked via an == comparison
      // eg
      // struct Item
      // {
      //    unsigned int unique_id;
      //    bool operator==(Item const& a, Item const& b) { return a.unique_id == b.unique_id; }
      //    Location location;
      // };
      // Two items may be equivalent in location.  find() would return
      // either one of them.  But no two items have the same ID, so
      // find_exact() would always return the item with the same location AND id.
      //
      const_iterator
      find_exact(const_reference __V) const throw ()
      {
        if (!_M_get_root()) return this->end();
        return _M_find_exact(_M_get_root(), __V, 0);
      }

      size_t
        count_within_range(const_reference __V, subvalue_type const __R) const throw ()
        {
          if (!_M_get_root()) return 0;
          _Region __region(_M_acc,__V,__R);
          return this->count_within_range(__region);
        }

      size_t
        count_within_range(_Region const& __REGION) const throw ()
        {
          if (!_M_get_root()) return 0;

          _Region __bounds(__REGION);
          return _M_count_within_range(_M_get_root(),
                               __REGION, __bounds, 0);
        }

      template <typename SearchVal, class Visitor>
        Visitor
        visit_within_range(SearchVal V, subvalue_type const R, Visitor visitor) const throw ()
        {
          if (!_M_get_root()) return visitor;
          _Region region(_M_acc,V,R);
          return this->visit_within_range(region, visitor);
        }

      template <class Visitor>
        Visitor
        visit_within_range(_Region const& REGION, Visitor visitor) const throw ()
        {
          if (_M_get_root())
            {
              _Region bounds(REGION);
              return _M_visit_within_range(visitor, _M_get_root(), REGION, bounds, 0);
            }
          return visitor;
        }



      template <typename SearchVal, typename _OutputIterator>
        _OutputIterator
        find_within_range(SearchVal __V, subvalue_type const __R,
                          _OutputIterator __out) const throw ()
        {
          if (!_M_get_root()) return __out;
          _Region __region(_M_acc,__V,__R);
          return this->find_within_range(__region, __out);
        }

      template <typename _OutputIterator>
        _OutputIterator
        find_within_range(_Region const& __REGION,
                          _OutputIterator __out) const throw ()
        {
          if (_M_get_root())
            {
              _Region __bounds(__REGION);
              __out = _M_find_within_range(__out, _M_get_root(),
                                   __REGION, __bounds, 0);
            }
          return __out;
        }


      template <typename SearchVal>
         std::pair<const_iterator,distance_type>
        find_nearest(SearchVal __V, subvalue_type const __Max_R ) const throw ()
        {
          if (!_M_get_root())
             return std::pair<const_iterator,distance_type>(this->end(),__Max_R);
          _Region __region(_M_acc,__V);  // note: zero-area!