Space-efficient geometric algorithms and data structures By Ilya Katz and Hervé Brönnimann

dynamic_kd_tree.hpp

Go to the documentation of this file.

/*
 * Copyright © Ilya Katz and Herve Bronnimann, 2005.
 */

#ifndef DYNAMIC_KD_TREE_HPP
#define DYNAMIC_KD_TREE_HPP

#include <iterator>
#include "static_kd_tree.hpp"

namespace inplaceds
{

    //\O(n\log{n})
  template <class RandomAccessIterator, class AxisAlignedGeometry>
  inline void
  build_dynamic_kdtree(RandomAccessIterator first, RandomAccessIterator last,
                           AxisAlignedGeometry geom)
  {
    if((last-first)%STATIC_KD_TREE_CUTOFF !=0 )
    {

       build_static_kdtree(
        last - (last-first) % STATIC_KD_TREE_CUTOFF, last, geom);

    }

    typedef typename
        std::iterator_traits<RandomAccessIterator>::difference_type Distance;

      Distance block = STATIC_KD_TREE_CUTOFF,
           n = (last-first) / STATIC_KD_TREE_CUTOFF,
           t = (last-first) % STATIC_KD_TREE_CUTOFF;

      while(n!=0)
    {
      if(n%2!=0)
      {

        build_static_kdtree(last-t-block, last-t, geom);
        t = t+block;
      }

      block*=2;
      n/=2;
    }
  }

  template <class RandomAccessIterator, class AxisAlignedGeometry>
  void
  insert_dynamic_kdtree(RandomAccessIterator first, RandomAccessIterator last,
                            AxisAlignedGeometry geom)
  {

    //last-first is the new size
    if((last-first)%STATIC_KD_TREE_CUTOFF != 0)
    {
      return;

    }

      typedef typename
        std::iterator_traits<RandomAccessIterator>::difference_type Distance;

      Distance block = STATIC_KD_TREE_CUTOFF,
           n =  (last-first-1) / STATIC_KD_TREE_CUTOFF;

      while(n%2!=0)
      {
        block*=2;
        n/=2;
      }

    build_dynamic_kdtree(last-block, last, geom);
  }

  template <class Box, class RandomAccessIterator, class OutputIterator,
        class AxisAlignedGeometry>
  OutputIterator
  window_query_dynamic_kdtree(RandomAccessIterator first, RandomAccessIterator last,
               AxisAlignedGeometry geom, Box Q, OutputIterator result)
  {

    if((last-first)%STATIC_KD_TREE_CUTOFF <
              STATIC_KD_TREE_CUTOFF -1)
    {
      window_query_static_kdtree(
      last - (last-first) % STATIC_KD_TREE_CUTOFF, last, geom, Q, result);

    }

    typedef typename
        std::iterator_traits<RandomAccessIterator>::difference_type Distance;

      Distance block = STATIC_KD_TREE_CUTOFF,
           n = (last-first) / STATIC_KD_TREE_CUTOFF,
           t = (last-first) % STATIC_KD_TREE_CUTOFF;

      while(n!=0)
    {
      if(n%2 !=0)
      {
        window_query_static_kdtree (last-t-block, last-t, geom, Q, result);
        t = t+block;
      }

      block*=2;
      n/=2;
    }

  }

  template <class Halfplane, class RandomAccessIterator, class OutputIterator,
        class AxisAlignedGeometry>
  OutputIterator
  halfplane_query_dynamic_kdtree(RandomAccessIterator first, RandomAccessIterator last,
               AxisAlignedGeometry geom, Halfplane Q, OutputIterator result)
  {

    if((last-first)%STATIC_KD_TREE_CUTOFF <
              STATIC_KD_TREE_CUTOFF -1)
    {
      halfplane_query_static_kdtree(
      last - (last-first) % STATIC_KD_TREE_CUTOFF, last, geom, Q, result);

    }

    typedef typename
        std::iterator_traits<RandomAccessIterator>::difference_type Distance;

      Distance block = STATIC_KD_TREE_CUTOFF,
           n = (last-first) / STATIC_KD_TREE_CUTOFF,
           t = (last-first) % STATIC_KD_TREE_CUTOFF;

      while(n!=0)
    {
      if(n%2 !=0)
      {
        halfplane_query_static_kdtree (last-t-block, last-t, geom, Q, result);
        t = t+block;
      }

      block*=2;
      n/=2;
    }

  }

  template <class RandomAccessIterator, class AxisAlignedGeometry>
  void
  remove_dynamic_kdtree(RandomAccessIterator first, RandomAccessIterator pos, RandomAccessIterator last,
                            AxisAlignedGeometry geom)
  {
      --last;
            std::swap(*pos,*last);

      typedef typename
      std::iterator_traits<RandomAccessIterator>::difference_type Distance;

      Distance block = STATIC_KD_TREE_CUTOFF,
            n = (last-first) / STATIC_KD_TREE_CUTOFF,
           t = (last-first) % STATIC_KD_TREE_CUTOFF;

      if(t!=0)
      {
      build_static_kdtree(last-t, last, geom);
      }

      while(last-t >= pos && n!=0)
      {
        if(n%2!=0)
        {
          build_static_kdtree(last-block-t, last-t, geom);
          t+=block;
        }

        block*=2;
        n/=2;
      }
  }

}//namespace
#endif

---

Code Documentation generated Using Doxygen

Copyright © Ilya Katz and Hervé Brönnimann, 2005, 2006.