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

beap_set.hpp

Go to the documentation of this file.

/*
 * Copyright © Ilya Katz and Herve Bronnimann, 2005.
 *
 * A beap_set is an adaptor that encapsulates functionality of the \c beap functions:
 * it povides the ability to insert and remove elements, inspection of the top and bottom elements.
 * Top element is the smallest element if default comparison is used.
 *
 * Beap_set is a container adaptor, meaning that it is implemented on top of some
 *  underlying container type. By default that underlying type is vector, but a different
 *  type may be selected explicitly.
 */

#ifndef BEAP_SET_HPP
#define BEAP_SET_HPP

//testing is not complete
#include <vector>

namespace inplaceds
{
  template <class _Tp,
        class _Sequence = std::vector<_Tp>,
        class _Compare =  std::less<typename _Sequence::value_type> >
  class beap_set
  {

  public:
    typedef typename _Sequence::value_type      value_type;
    typedef typename _Sequence::size_type       size_type;
    typedef          _Sequence                  container_type;

    typedef typename _Sequence::iterator         iterator;
    typedef typename _Sequence::const_iterator   const_iterator;

  protected:
    _Sequence c;
    _Compare comp;

  public:

     beap_set(const value_type* first, const value_type* last)
     :  c(first, last)
     {
       make_beap(c.begin(), c.end(), comp);
     }

     beap_set(const value_type* first, const value_type* last, const Comp& compare)
     :  c(first, last), comp(compare)
     {
       make_beap(c.begin(), c.end(), comp);
     }

    reference find(_Tp x)
    {
      return find_beap(c.begin(), c.end(), x, comp);
    }

    bool is_empty()
    {
      return empty();
    }

    const_iterator top() const
    {
      return min_beap(c.begin(), c.end(), comp);
    }

    const_iterator bottom() const
    {
      return max_beap(c.begin(), c.end(), comp);
    }

      void insert(_Tp x)
      {
        insert_beap(c.begin(), c.end(), comp);
      }

      bool remove(_Tp x)
      {
        reference pos = find(x);
        if(pos!=c.end())
        {
          remove_beap(c.begin(), pos ,c.end() );
          return true;
        }

        else
        {
          return false;
        }
      }

      void sort(reference first)
      {
      typedef typename std::iterator_traits<RandomAccessIterator>::difference_type Distance;
        copy(c.begin(), c.end(), first);
        sort_beap(first, first+Distance(c.begin(), c.end()), comp);
      }

      const_iterator end()
      {
        return c.end();
      }
  };
}//namespace

#endif

---

Code Documentation generated Using Doxygen

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