vtf-logo

PriorityQueueBinaryHeap.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00008 #if !defined(__ads_PriorityQueueBinaryHeap_h__)
00009 #define __ads_PriorityQueueBinaryHeap_h__
00010 
00011 #include "PriorityQueue.h"
00012 
00013 #include "../functor/compose.h"
00014 
00015 #include <algorithm>
00016 #include <vector>
00017 
00018 BEGIN_NAMESPACE_ADS
00019 
00021 
00050 template < typename T, 
00051            typename Key = typename std::iterator_traits<T>::value_type,
00052            class GetKey = Dereference<T>,
00053            class CompareKeys = std::greater<Key>, 
00054            class Sequence = std::vector<T> >
00055 class PriorityQueueBinaryHeap :
00056   public PriorityQueue<T, Key, GetKey, CompareKeys, Sequence>
00057 {
00058  private:
00059 
00060   typedef PriorityQueue<T, Key, GetKey, CompareKeys, Sequence> base_type;
00061   typedef typename base_type::get_key_functor get_key_functor;
00062   typedef typename base_type::compare_keys_functor compare_keys_functor;
00063   typedef typename base_type::sequence_type sequence_type;
00064   typedef ads::binary_compose_binary_unary< compare_keys_functor, 
00065                                             get_key_functor, 
00066                                             get_key_functor > 
00067   compare_values_functor;
00068 
00069  public:
00070 
00071   //
00072   // public typedefs
00073   //
00074 
00075 
00077   typedef typename base_type::element_type element_type;
00079   typedef typename base_type::const_reference const_reference;
00081   typedef typename base_type::key_type key_type;
00083   typedef typename base_type::size_type size_type;
00085   typedef typename base_type::value_type value_type;
00086 
00087  protected:
00088 
00089   //
00090   // Member data.
00091   //
00092 
00094   compare_values_functor _compare;
00096   sequence_type _container;
00097 
00098  private:
00099 
00100   //
00101   // Not implemented.
00102   //
00103 
00104   // Copy constructor not implemented.
00105   PriorityQueueBinaryHeap( const PriorityQueueBinaryHeap& );
00106 
00107   // Assignment operator not implemented.
00108   const PriorityQueueBinaryHeap& 
00109   operator=( const PriorityQueueBinaryHeap& );
00110 
00111  public:
00112 
00113   //
00114   // Constructors, Destructor.
00115   //
00116 
00118 
00121   explicit
00122   PriorityQueueBinaryHeap( const sequence_type& 
00123                            container = sequence_type() ) :
00124     _compare(),
00125     _container( container )
00126   {
00127     std::make_heap( _container.begin(), _container.end(), _compare ); 
00128   }
00129 
00131   explicit 
00132   PriorityQueueBinaryHeap( size_type n ) :
00133     _compare(),
00134     _container()
00135   {
00136     _container.reserve( n ); 
00137   }
00138 
00140   template <class InputIterator>
00141   PriorityQueueBinaryHeap( InputIterator first, InputIterator last,
00142                            const sequence_type& 
00143                            container = sequence_type() ) :
00144     _compare(),
00145     _container( container )
00146   { 
00147     _container.insert( _container.end(), first, last);
00148     std::make_heap( _container.begin(), _container.end(), _compare ); 
00149   }
00150 
00152   virtual 
00153   ~PriorityQueueBinaryHeap()
00154   {}
00155   
00156   //
00157   // Accessors
00158   //
00159 
00161 
00162   size_type
00163   size() const
00164   {
00165     return _container.size();
00166   }
00167 
00169   bool
00170   empty() const
00171   {
00172     return _container.empty();
00173   }
00174 
00176   const_reference
00177   top() const
00178   { 
00179     return _container.front(); 
00180   }
00181 
00182   //
00183   // Manipulators
00184   //
00185 
00187   void 
00188   push( element_type x )
00189   {
00190     _container.push_back( x );
00191     std::push_heap( _container.begin(), _container.end(), _compare );
00192   }
00193 
00195   void 
00196   pop()
00197   {
00198     std::pop_heap( _container.begin(), _container.end(), _compare );
00199     _container.pop_back();
00200   }
00201 };
00202 
00203 END_NAMESPACE_ADS
00204 
00205 #endif

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