vtf-logo

PriorityQueueBinaryHeapDynamicKeys.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00008 #if !defined(__ads_PriorityQueueBinaryHeapDynamicKeys_h__)
00009 #define __ads_PriorityQueueBinaryHeapDynamicKeys_h__
00010 
00011 #include "PriorityQueue.h"
00012 
00013 #include "../functor/compose.h"
00014 
00015 #include <vector>
00016 
00017 BEGIN_NAMESPACE_ADS
00018 
00020 
00045 template < typename T,
00046            class GetHandle,
00047            typename Key = typename std::iterator_traits<T>::value_type,
00048            class GetKey = Dereference<T>,
00049            class CompareKeys = std::less<Key>, 
00050            class Sequence = std::vector<T> >
00051 class PriorityQueueBinaryHeapDynamicKeys :
00052   public PriorityQueue<T, Key, GetKey, CompareKeys, Sequence>
00053 {
00054  protected:
00055 
00057   typedef PriorityQueue<T, Key, GetKey, CompareKeys, Sequence> base_type;
00059   typedef GetHandle get_handle_functor;
00061   typedef typename base_type::get_key_functor get_key_functor;
00063   typedef typename base_type::compare_keys_functor compare_keys_functor;
00065   typedef typename base_type::sequence_type sequence_type;
00067   typedef ads::binary_compose_binary_unary< compare_keys_functor, 
00068                                             get_key_functor, 
00069                                             get_key_functor > 
00070   compare_values_functor;
00071 
00072  public:
00073 
00074   //
00075   // public typedefs
00076   //
00077 
00078 
00080   typedef typename base_type::element_type element_type;
00082   typedef typename base_type::const_reference const_reference;
00084   typedef typename base_type::key_type key_type;
00086   typedef typename base_type::size_type size_type;
00088   typedef typename base_type::value_type value_type;
00090   typedef typename base_type::iterator iterator;
00092   typedef typename base_type::difference_type difference_type;
00093 
00094  protected:
00095 
00096   //
00097   // Member data.
00098   //
00099 
00101   get_handle_functor _get_handle;
00103   compare_values_functor _compare;
00105   sequence_type _container;
00106 
00107  private:
00108 
00109   //
00110   // Not implemented.
00111   //
00112 
00113   // Copy constructor not implemented.
00114   PriorityQueueBinaryHeapDynamicKeys( const 
00115                                       PriorityQueueBinaryHeapDynamicKeys& );
00116 
00117   // Assignment operator not implemented.
00118   const PriorityQueueBinaryHeapDynamicKeys& 
00119   operator=( const PriorityQueueBinaryHeapDynamicKeys& );
00120 
00121  public:
00122 
00123   //
00124   // Constructors, Destructor.
00125   //
00126 
00128 
00131   explicit
00132   PriorityQueueBinaryHeapDynamicKeys( const get_handle_functor& 
00133                                       get_handle = get_handle_functor(),
00134                                       const sequence_type& 
00135                                       container = sequence_type() ) :
00136     _get_handle( get_handle ),
00137     _compare(),
00138     _container( container )
00139   {
00140     make();
00141   }
00142 
00144   explicit 
00145   PriorityQueueBinaryHeapDynamicKeys( size_type n,
00146                                       const get_handle_functor& 
00147                                       get_handle = get_handle_functor() ) :
00148     _get_handle( get_handle ),
00149     _compare(),
00150     _container()
00151   {
00152     _container.reserve( n ); 
00153   }
00154 
00156   template <class InputIterator>
00157   PriorityQueueBinaryHeapDynamicKeys( InputIterator first, 
00158                                       InputIterator last,
00159                                       const get_handle_functor& 
00160                                       get_handle = get_handle_functor(),
00161                                       const sequence_type& 
00162                                       container = sequence_type() ) :
00163     _get_handle( get_handle ),
00164     _compare(),
00165     _container( container )
00166   { 
00167     _container.insert( _container.end(), first, last);
00168     make();
00169   }
00170 
00172   virtual 
00173   ~PriorityQueueBinaryHeapDynamicKeys()
00174   {}
00175   
00176   //
00177   // Accessors
00178   //
00179 
00181   size_type
00182   size() const
00183   {
00184     return _container.size();
00185   }
00186 
00188   bool
00189   empty() const
00190   {
00191     return _container.empty();
00192   }
00193 
00195   const_reference
00196   top() const
00197   { 
00198     return _container.front(); 
00199   }
00200 
00201   //
00202   // Manipulators
00203   //
00204 
00206   void 
00207   push( element_type x )
00208   {
00209     // If we don't have to resize the container.
00210     if ( _container.size() < _container.capacity() ) {
00211       // Add the element.
00212       _container.push_back( x );
00213       // Set the element's handle.
00214       _get_handle( _container.back() ) = _container.end() - 1;
00215     }
00216     // The container will be resized when the element is added.
00217     else {
00218       // Add the element.
00219       _container.push_back( x );
00220       // Fix the element handles.
00221       set_handles();
00222     }
00223     // Insert the element in the heap.
00224     decrease( _container.end() - 1 );
00225   }
00226 
00228   void 
00229   pop()
00230   {
00231     // Store and erase the last element.
00232     value_type tmp( _container.back() );
00233     _container.pop_back();
00234 
00235     // Adjust the heap.
00236     difference_type parent = 0;
00237     difference_type child = small_child( parent );
00238     while ( child >= 0 && 
00239             _compare( *( _container.begin() + child ), tmp ) ) {
00240       copy( _container.begin() + parent, _container.begin() + child );
00241       parent = child;
00242       child = small_child( parent );
00243     }
00244 
00245     // Insert the last element.
00246     copy( _container.begin() + parent, iterator(&tmp) );
00247   }
00248 
00250   void 
00251   decrease( element_type x )
00252   {
00253     decrease( _get_handle( x ) );
00254   }
00255 
00256  protected:
00257 
00259   void
00260   make()
00261   {
00262     for ( iterator i = _container.begin(); i != _container.end(); ++i ) {
00263       _get_handle( *i ) = i;
00264       decrease( i );
00265     }
00266   }
00267 
00269   void 
00270   decrease( iterator iter )
00271   {
00272     difference_type child = iter - _container.begin();
00273     difference_type parent = (child - 1) / 2;
00274 
00275     while ( child > 0 && 
00276             _compare( *( _container.begin() + child ), 
00277                       *( _container.begin() + parent ) ) ) {
00278       swap( _container.begin() + child, _container.begin() + parent );
00279       child = parent;
00280       parent = (child - 1) / 2;
00281     }
00282   }
00283 
00285   void 
00286   swap( iterator a, iterator b )
00287   {
00288     std::swap( _get_handle( *a ), _get_handle( *b ) );
00289     std::swap( *a, *b );
00290   }
00291 
00293   void 
00294   copy( iterator a, iterator b )
00295   {
00296     *a = *b;
00297     _get_handle( *a ) = a;
00298   }
00299 
00301   void 
00302   set_handles()
00303   {
00304     for ( iterator i = _container.begin(); i != _container.end(); ++i ) {
00305       _get_handle( *i ) = i;
00306     }
00307   }
00308 
00310   difference_type 
00311   small_child( difference_type parent )
00312   {
00313     difference_type child = 2 * parent + 1;
00314     if ( child + 1 < static_cast<difference_type>( size() ) &&
00315          _compare( *( _container.begin() + child + 1 ),
00316                    *( _container.begin() + child ) ) ) {
00317       ++child;
00318     }
00319     if ( child < static_cast<difference_type>( size() ) ) {
00320       return child;
00321     }
00322     return -1;
00323   }
00324 
00325 };
00326 
00327 END_NAMESPACE_ADS
00328 
00329 #endif

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