PriorityQueueBinaryHeap.h

Go to the documentation of this file.

// -*- C++ -*-

#if !defined(__ads_PriorityQueueBinaryHeap_h__)
#define __ads_PriorityQueueBinaryHeap_h__

#include "PriorityQueue.h"

#include "../functor/compose.h"

#include <algorithm>
#include <vector>

BEGIN_NAMESPACE_ADS


template < typename T, 
           typename Key = typename std::iterator_traits<T>::value_type,
           class GetKey = Dereference<T>,
           class CompareKeys = std::greater<Key>, 
           class Sequence = std::vector<T> >
class PriorityQueueBinaryHeap :
  public PriorityQueue<T, Key, GetKey, CompareKeys, Sequence>
{
 private:

  typedef PriorityQueue<T, Key, GetKey, CompareKeys, Sequence> base_type;
  typedef typename base_type::get_key_functor get_key_functor;
  typedef typename base_type::compare_keys_functor compare_keys_functor;
  typedef typename base_type::sequence_type sequence_type;
  typedef ads::binary_compose_binary_unary< compare_keys_functor, 
                                            get_key_functor, 
                                            get_key_functor > 
  compare_values_functor;

 public:

  //
  // public typedefs
  //


  typedef typename base_type::element_type element_type;
  typedef typename base_type::const_reference const_reference;
  typedef typename base_type::key_type key_type;
  typedef typename base_type::size_type size_type;
  typedef typename base_type::value_type value_type;

 protected:

  //
  // Member data.
  //

  compare_values_functor _compare;
  sequence_type _container;

 private:

  //
  // Not implemented.
  //

  // Copy constructor not implemented.
  PriorityQueueBinaryHeap( const PriorityQueueBinaryHeap& );

  // Assignment operator not implemented.
  const PriorityQueueBinaryHeap& 
  operator=( const PriorityQueueBinaryHeap& );

 public:

  //
  // Constructors, Destructor.
  //


  explicit
  PriorityQueueBinaryHeap( const sequence_type& 
                           container = sequence_type() ) :
    _compare(),
    _container( container )
  {
    std::make_heap( _container.begin(), _container.end(), _compare ); 
  }

  explicit 
  PriorityQueueBinaryHeap( size_type n ) :
    _compare(),
    _container()
  {
    _container.reserve( n ); 
  }

  template <class InputIterator>
  PriorityQueueBinaryHeap( InputIterator first, InputIterator last,
                           const sequence_type& 
                           container = sequence_type() ) :
    _compare(),
    _container( container )
  { 
    _container.insert( _container.end(), first, last);
    std::make_heap( _container.begin(), _container.end(), _compare ); 
  }

  virtual 
  ~PriorityQueueBinaryHeap()
  {}
  
  //
  // Accessors
  //


  size_type
  size() const
  {
    return _container.size();
  }

  bool
  empty() const
  {
    return _container.empty();
  }

  const_reference
  top() const
  { 
    return _container.front(); 
  }

  //
  // Manipulators
  //

  void 
  push( element_type x )
  {
    _container.push_back( x );
    std::push_heap( _container.begin(), _container.end(), _compare );
  }

  void 
  pop()
  {
    std::pop_heap( _container.begin(), _container.end(), _compare );
    _container.pop_back();
  }
};

END_NAMESPACE_ADS

#endif

---