node.hpp

Go to the documentation of this file.

#ifndef INCLUDE_KDTREE_NODE_HPP
#define INCLUDE_KDTREE_NODE_HPP

#ifdef KDTREE_DEFINE_OSTREAM_OPERATORS
#  include <ostream>
#endif

#include <cstddef>
#include <cmath>

namespace kd_tree
{
  struct _Node_base
  {
    typedef _Node_base* _Base_ptr;
    typedef _Node_base const* _Base_const_ptr;

    _Base_ptr _M_parent;
    _Base_ptr _M_left;
    _Base_ptr _M_right;

    _Node_base(_Base_ptr const __PARENT = NULL,
               _Base_ptr const __LEFT = NULL,
               _Base_ptr const __RIGHT = NULL)
      : _M_parent(__PARENT), _M_left(__LEFT), _M_right(__RIGHT) {}

    static _Base_ptr
    _S_minimum(_Base_ptr __x)
    {
      while (__x->_M_left) __x = __x->_M_left;
      return __x;
    }

    static _Base_ptr
    _S_maximum(_Base_ptr __x)
    {
      while (__x->_M_right) __x = __x->_M_right;
      return __x;
    }
  };

  template <typename _Val>
    struct _Node : public _Node_base
    {
      using _Node_base::_Base_ptr;
      typedef _Node* _Link_type;

      _Val _M_value;

      _Node(_Val const& __VALUE = _Val(),
            _Base_ptr const __PARENT = NULL,
            _Base_ptr const __LEFT = NULL,
            _Base_ptr const __RIGHT = NULL)
        : _Node_base(__PARENT, __LEFT, __RIGHT), _M_value(__VALUE) {}

#ifdef KDTREE_DEFINE_OSTREAM_OPERATORS

     template <typename Char, typename Traits>
       friend
       std::basic_ostream<Char, Traits>&
       operator<<(typename std::basic_ostream<Char, Traits>& out,
                  _Node_base const& node)
       {
         out << &node;
         out << " parent: " << node._M_parent;
         out << "; left: " << node._M_left;
         out << "; right: " << node._M_right;
         return out;
       }

     template <typename Char, typename Traits>
       friend
       std::basic_ostream<Char, Traits>&
       operator<<(typename std::basic_ostream<Char, Traits>& out,
                  _Node<_Val> const& node)
       {
         out << &node;
         out << ' ' << node._M_value;
         out << "; parent: " << node._M_parent;
         out << "; left: " << node._M_left;
         out << "; right: " << node._M_right;
         return out;
       }

#endif
    };

  template <typename _Val, typename _Acc, typename _Cmp>
    class _Node_compare
    {
    public:
      _Node_compare(size_t const __DIM, _Acc const& acc, _Cmp const& cmp)
    : _M_DIM(__DIM), _M_acc(acc), _M_cmp(cmp) {}

      bool
      operator()(_Val const& __A, _Val const& __B) const
      {
        return _M_cmp(_M_acc(__A, _M_DIM), _M_acc(__B, _M_DIM));
      }

    private:
      size_t _M_DIM;    // don't make this const so that an assignment operator can be auto-generated
      _Acc _M_acc;
      _Cmp _M_cmp;
  };

  template <typename _ValA, typename _ValB, typename _Cmp,
        typename _Acc>
  inline
  bool
  _S_node_compare (const size_t __dim,
           const _Cmp& __cmp, const _Acc& __acc,
           const _ValA& __a, const _ValB& __b)
  {
    return __cmp(__acc(__a, __dim), __acc(__b, __dim));
  }

  template <typename _ValA, typename _ValB, typename _Dist,
        typename _Acc>
  inline
  typename _Dist::distance_type
  _S_node_distance (const size_t __dim,
            const _Dist& __dist, const _Acc& __acc,
            const _ValA& __a, const _ValB& __b)
  {
    return __dist(__acc(__a, __dim), __acc(__b, __dim));
  }

  template <typename _ValA, typename _ValB, typename _Dist,
        typename _Acc>
  inline
  typename _Dist::distance_type
  _S_accumulate_node_distance (const size_t __dim,
                   const _Dist& __dist, const _Acc& __acc,
                   const _ValA& __a, const _ValB& __b)
  {
    typename _Dist::distance_type d = 0;
    for (size_t i=0; i<__dim; ++i)
      d += __dist(__acc(__a, i), __acc(__b, i));
    return d;
  }

  template <typename _Val, typename _Cmp, typename _Acc>
  inline
  _Node_base*
  _S_node_descend (const size_t __dim,
           const _Cmp& __cmp, const _Acc& __acc,
           const _Val& __val, const _Node_base* __node)
  {
    if (_S_node_compare(__dim, __cmp, __acc, __val,  static_cast<const _Node<_Val>* >(__node)->_M_value))
      return __node->_M_left;
    else
      return __node->_M_right;
  }

  template <class SearchVal,
           typename _Val, typename _Cmp,
           typename _Acc, typename _Dist,
           typename _Predicate>
  inline
  std::pair<const _Node<_Val>*,
        std::pair<size_t, typename _Dist::distance_type> >
  _S_node_nearest (const size_t __k, size_t __dim, SearchVal const& __val,
           const _Node<_Val>* __node, const _Node_base* __end,
           const _Node<_Val>* __best, typename _Dist::distance_type __max,
           const _Cmp& __cmp, const _Acc& __acc, const _Dist& __dist,
           _Predicate __p)
  {
    const _Node_base* pcur = __node;
    const _Node_base* cur = _S_node_descend(__dim % __k, __cmp, __acc, __val, __node);
    size_t cur_dim = __dim+1;
    // find the smallest __max distance in direct descent
    while (cur)
      {
    if (__p(static_cast<const _Node<_Val>* >(cur)->_M_value))
      {
        typename _Dist::distance_type d = 0;
        for (size_t i=0; i != __k; ++i)
          d += _S_node_distance(i, __dist, __acc, __val, static_cast<const _Node<_Val>* >(cur)->_M_value);
       d = sqrt(d);
        if (d <= __max)
          // ("bad candidate notes")
          // Changed: removed this test: || ( d == __max && cur < __best ))
          // Can't do this optimisation without checking that the current 'best' is not the root AND is not a valid candidate...
          // This is because find_nearest() etc will call this function with the best set to _M_root EVEN IF _M_root is not a valid answer (eg too far away or doesn't pass the predicate test)
          {
        __best = static_cast<const _Node<_Val>* >(cur);
        __max = d;
        __dim = cur_dim;
          }
      }
    pcur = cur;
    cur = _S_node_descend(cur_dim % __k, __cmp, __acc, __val, cur);
    ++cur_dim;
      }
    // swap cur to prev, only prev is a valid node.
    cur = pcur;
    --cur_dim;
    pcur = NULL;
    // Probe all node's children not visited yet (siblings of the visited nodes).
    const _Node_base* probe = cur;
    const _Node_base* pprobe = probe;
    const _Node_base* near_node;
    const _Node_base* far_node;
    size_t probe_dim = cur_dim;
    if (_S_node_compare(probe_dim % __k, __cmp, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value))
      near_node = probe->_M_right;
    else
      near_node = probe->_M_left;
    if (near_node
    // only visit node's children if node's plane intersect hypersphere
    && (sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value)) <= __max))
      {
    probe = near_node;
    ++probe_dim;
      }
    while (cur != __end)
      {
    while (probe != cur)
      {
        if (_S_node_compare(probe_dim % __k, __cmp, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value))
          {
        near_node = probe->_M_left;
        far_node = probe->_M_right;
          }
        else
          {
        near_node = probe->_M_right;
        far_node = probe->_M_left;
          }
        if (pprobe == probe->_M_parent) // going downward ...
          {
        if (__p(static_cast<const _Node<_Val>* >(probe)->_M_value))
          {
            typename _Dist::distance_type d = 0;
            for (size_t i=0; i < __k; ++i)
              d += _S_node_distance(i, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value);
          d = sqrt(d);
          if (d <= __max)  // CHANGED, see the above notes ("bad candidate notes")
              {
            __best = static_cast<const _Node<_Val>* >(probe);
            __max = d;
            __dim = probe_dim;
              }
          }
        pprobe = probe;
        if (near_node)
          {
            probe = near_node;
            ++probe_dim;
          }
        else if (far_node &&
             // only visit node's children if node's plane intersect hypersphere
             sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value)) <= __max)
          {
            probe = far_node;
            ++probe_dim;
          }
        else
          {
            probe = probe->_M_parent;
            --probe_dim;
          }
          }
        else // ... and going upward.
          {
        if (pprobe == near_node && far_node
            // only visit node's children if node's plane intersect hypersphere
            && sqrt(_S_node_distance(probe_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(probe)->_M_value)) <= __max)
          {
            pprobe = probe;
            probe = far_node;
            ++probe_dim;
          }
        else
          {
            pprobe = probe;
            probe = probe->_M_parent;
            --probe_dim;
          }
          }
      }
    pcur = cur;
    cur = cur->_M_parent;
    --cur_dim;
    pprobe = cur;
    probe = cur;
    probe_dim = cur_dim;
    if (cur != __end)
      {
        if (pcur == cur->_M_left)
          near_node = cur->_M_right;
        else
          near_node = cur->_M_left;
        if (near_node
        // only visit node's children if node's plane intersect hypersphere
        && (sqrt(_S_node_distance(cur_dim % __k, __dist, __acc, __val, static_cast<const _Node<_Val>* >(cur)->_M_value)) <= __max))
          {
        probe = near_node;
        ++probe_dim;
          }
      }
      }
    return std::pair<const _Node<_Val>*,
      std::pair<size_t, typename _Dist::distance_type> >
      (__best, std::pair<size_t, typename _Dist::distance_type>
       (__dim, __max));
  }


} // namespace kd_tree

#endif // include guard

/* COPYRIGHT --
 *
 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
 * root for more information.
 *
 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */