PriorityQueueBinaryHeapStoreKeys.h

Go to the documentation of this file.

// -*- C++ -*-

#if !defined(__ads_PriorityQueueBinaryHeapStoreKeys_h__)
#define __ads_PriorityQueueBinaryHeapStoreKeys_h__

#include "PriorityQueue.h"

#include "../functor/compose.h"
#include "../functor/select.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< std::pair<Key,T> > >
class PriorityQueueBinaryHeapStoreKeys :
  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;

 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;

 private:

  typedef 
  ads::binary_compose_binary_unary< compare_keys_functor, 
                                    Select1st<value_type>,
                                    Select1st<value_type> > 
  compare_values_functor;

 protected:

  //
  // Member data.
  //

  get_key_functor _get_key;
  compare_values_functor _compare;
  sequence_type _container;

 private:

  //
  // Not implemented.
  //

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

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

 public:

  //
  // Constructors, Destructor.
  //


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

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

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

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


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

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

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

  //
  // Manipulators
  //

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

  void 
  push( element_type x, key_type k )
  {
    _container.push_back( value_type( k, 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

---