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

dynamic_sorted_vector.hpp

Go to the documentation of this file.

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

#ifndef DYNAMIC_SORTED_VEC_HPP
#define DYNAMIC_SORTED_VEC_HPP

#include <iterator>
#include <cmath>

#define VECTOR_SIZE_CUTOFF 16

namespace inplaceds
{

  template <class RandomAccessIterator, class StrictWeakOrdering>
  inline void
  build_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator last,
                                                StrictWeakOrdering comp)
  {
    if((last-first)%VECTOR_SIZE_CUTOFF !=0 )
    {
        std::sort(last-(last-first)%VECTOR_SIZE_CUTOFF, last, comp);

    }

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

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

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

        std::sort(last-t-block, last-t, comp);

        t = t+block;
      }

      block*=2;
      n/=2;
    }
    cout<<endl;
  }

  template <class RandomAccessIterator>
  inline void
  build_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator last)
  {
        build_dynamic_sorted_vector(first, last,
                                                        std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
  }

        template <class RandomAccessIterator, class StrictWeakOrdering>
  bool is_sorted(RandomAccessIterator first, RandomAccessIterator last,
                                                                                                                                        StrictWeakOrdering comp)
  {
        if(first==last || first==last-1)
        {
                return true;
        }
   for(RandomAccessIterator it=first++; it!=last-1; ++it)
   {
        if(comp(*first,*it))
        {
                return false;
        }
         ++first;
   }
                        return true;
  }

  template <class RandomAccessIterator, class StrictWeakOrdering>
  bool
  is_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator last,
                                                                                                                                        StrictWeakOrdering comp)
  {

    if((last-first)%VECTOR_SIZE_CUTOFF != 0)
    {
        //do nothing
    }


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

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

    while(n!=0)
    {
      if(n%2 !=0)
      {
        if(!is_sorted(last-t-block, last-t, comp))
        {
                return false;
        }
        t = t+block;
      }

      block*=2;
      n/=2;
    }

    return true;

  }

                template <class RandomAccessIterator>
  inline bool
  is_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator last)
  {
        return is_dynamic_sorted_vector(first, last,
                                                                                                                std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
  }


  template <class RandomAccessIterator, class StrictWeakOrdering>
  void
  insert_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator last,
                                                                                                                                                                                StrictWeakOrdering comp)
  {

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

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

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

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

    std::sort(last-block, last, comp);
  }

                template <class RandomAccessIterator>
  inline void
  insert_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator last)
  {
        insert_dynamic_sorted_vector(first, last,
                                                        std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
  }

  template <class RandomAccessIterator, class EqualityComparable>
  RandomAccessIterator
  find_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator last,
                                                                                                                                        const EqualityComparable& key)
  {

                                RandomAccessIterator result = last;

    if((last-first)%VECTOR_SIZE_CUTOFF != 0)
    {
      result = std::find(last-(last-first)%VECTOR_SIZE_CUTOFF, last, key);
    }

    if(result != last)
    {
            return result;
    }


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

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

    while(n!=0)
    {
      if(n%2!=0)
      {
        result = std::lower_bound(last-t-block, last-t, key);
        if(result != last-t && (*result)==      key)
        {
            return result;
        }
        t = t+block;
      }

      block*=2;
      n/=2;
    }

    return last;

  }

  template <class RandomAccessIterator, class StrictWeakOrdering>
  void
  remove_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator pos, RandomAccessIterator last,
                            StrictWeakOrdering comp)
  {
      --last;
      std::swap(*pos,*last);

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

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

                                                //if there is a buffer at the end, just sort the current block
      if(t!=0)
      {
        //find current block
              while(n!=0)
              {
                if(n%2!=0)
                {
                        if((pos < (last-t)) && !(pos < (last-t-block)) )
                        {
                                std::sort(last-block-t, last-t, comp);
                   return;
                        }
                        t+=block;
                }
                block*=2;
                n/=2;
              }
      }
      else
      {
              //otherwise, need to rebuild everything below the region
              //where the deleted element was located
              while(!(last-t < pos))
              {
                if(n%2!=0)
                {
                  std::sort(last-block-t, last-t, comp);
                  t+=block;
                }

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

  template <class RandomAccessIterator>
  inline void
  remove_dynamic_sorted_vector(RandomAccessIterator first, RandomAccessIterator pos, RandomAccessIterator last)
  {
        remove_dynamic_sorted_vector(first, pos, last,
                                                                std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
  }

}//namespace
#endif

---

Code Documentation generated Using Doxygen

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