vtf-logo

PriorityQueueBinaryHeapStoreKeys.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00008 #if !defined(__ads_PriorityQueueBinaryHeapStoreKeys_h__)
00009 #define __ads_PriorityQueueBinaryHeapStoreKeys_h__
00010 
00011 #include "PriorityQueue.h"
00012 
00013 #include "../functor/compose.h"
00014 #include "../functor/select.h"
00015 
00016 #include <algorithm>
00017 #include <vector>
00018 
00019 BEGIN_NAMESPACE_ADS
00020 
00022 
00055 template < typename T, 
00056            typename Key = typename std::iterator_traits<T>::value_type,
00057            class GetKey = Dereference<T>,
00058            class CompareKeys = std::greater<Key>, 
00059            class Sequence = std::vector< std::pair<Key,T> > >
00060 class PriorityQueueBinaryHeapStoreKeys :
00061   public PriorityQueue<T, Key, GetKey, CompareKeys, Sequence>
00062 {
00063  private:
00064 
00065   typedef PriorityQueue<T, Key, GetKey, CompareKeys, Sequence> base_type;
00066   typedef typename base_type::get_key_functor get_key_functor;
00067   typedef typename base_type::compare_keys_functor compare_keys_functor;
00068   typedef typename base_type::sequence_type sequence_type;
00069 
00070  public:
00071 
00072   //
00073   // public typedefs
00074   //
00075 
00076 
00078   typedef typename base_type::element_type element_type;
00080   typedef typename base_type::const_reference const_reference;
00082   typedef typename base_type::key_type key_type;
00084   typedef typename base_type::size_type size_type;
00086   typedef typename base_type::value_type value_type;
00087 
00088  private:
00089 
00090   typedef 
00091   ads::binary_compose_binary_unary< compare_keys_functor, 
00092                                     Select1st<value_type>,
00093                                     Select1st<value_type> > 
00094   compare_values_functor;
00095 
00096  protected:
00097 
00098   //
00099   // Member data.
00100   //
00101 
00103   get_key_functor _get_key;
00105   compare_values_functor _compare;
00107   sequence_type _container;
00108 
00109  private:
00110 
00111   //
00112   // Not implemented.
00113   //
00114 
00115   // Copy constructor not implemented.
00116   PriorityQueueBinaryHeapStoreKeys( const 
00117                                     PriorityQueueBinaryHeapStoreKeys& );
00118 
00119   // Assignment operator not implemented.
00120   const PriorityQueueBinaryHeapStoreKeys& 
00121   operator=( const PriorityQueueBinaryHeapStoreKeys& );
00122 
00123  public:
00124 
00125   //
00126   // Constructors, Destructor.
00127   //
00128 
00130 
00133   explicit
00134   PriorityQueueBinaryHeapStoreKeys( const sequence_type& 
00135                                     container = sequence_type() ) :
00136     _get_key(),
00137     _compare(),
00138     _container( container )
00139   {
00140     std::make_heap( _container.begin(), _container.end(), _compare ); 
00141   }
00142 
00144   explicit 
00145   PriorityQueueBinaryHeapStoreKeys( size_type n ) :
00146     _get_key(),
00147     _compare(),
00148     _container()
00149   {
00150     _container.reserve( n );
00151   }
00152 
00154   template <class InputIterator>
00155   PriorityQueueBinaryHeapStoreKeys( InputIterator first, InputIterator last,
00156                                     const sequence_type& 
00157                                     container = sequence_type() ) :
00158     _get_key(),
00159     _compare(),
00160     _container( container )
00161   { 
00162     _container.insert( _container.end(), first, last);
00163     std::make_heap( _container.begin(), _container.end(), _compare ); 
00164   }
00165 
00167   virtual 
00168   ~PriorityQueueBinaryHeapStoreKeys()
00169   {}
00170   
00171   //
00172   // Accessors
00173   //
00174 
00176 
00177   size_type
00178   size() const
00179   {
00180     return _container.size();
00181   }
00182 
00184   bool
00185   empty() const
00186   {
00187     return _container.empty();
00188   }
00189 
00191   const_reference
00192   top() const
00193   { 
00194     return _container.front().second;
00195   }
00196 
00197   //
00198   // Manipulators
00199   //
00200 
00202   void 
00203   push( element_type x )
00204   {
00205     _container.push_back( value_type( _get_key( x ), x ) );
00206     std::push_heap( _container.begin(), _container.end(), _compare );
00207   }
00208 
00210   void 
00211   push( element_type x, key_type k )
00212   {
00213     _container.push_back( value_type( k, x ) );
00214     std::push_heap( _container.begin(), _container.end(), _compare );
00215   }
00216 
00218   void 
00219   pop()
00220   {
00221     std::pop_heap( _container.begin(), _container.end(), _compare );
00222     _container.pop_back();
00223   }
00224 };
00225 
00226 END_NAMESPACE_ADS
00227 
00228 #endif

Generated on Fri Aug 24 12:55:27 2007 for Algorithms and Data Structures Package by  doxygen 1.4.7