vtf-logo

PriorityQueueBinaryHeapArray.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00008 #if !defined(__ads_PriorityQueueBinaryHeapArray_h__)
00009 #define __ads_PriorityQueueBinaryHeapArray_h__
00010 
00011 #include "PriorityQueueBinaryHeapDynamicKeys.h"
00012 #include "HeapHandleArray.h"
00013 
00014 #include "../array/Array.h"
00015 
00016 BEGIN_NAMESPACE_ADS
00017 
00019 
00037 template < typename T,
00038            typename Key = typename std::iterator_traits<T>::value_type,
00039            class GetKey = Dereference<T>,
00040            class CompareKeys = std::less<Key>, 
00041            class Sequence = std::vector<T> >
00042 class PriorityQueueBinaryHeapArray :
00043   public PriorityQueueBinaryHeapDynamicKeys
00044   < T, HeapHandleArray<T, typename Sequence::iterator>, Key,
00045     GetKey, CompareKeys, Sequence >
00046 {
00047  private:
00048 
00049   typedef PriorityQueueBinaryHeapDynamicKeys
00050   < T, HeapHandleArray<T, typename Sequence::iterator>, Key,
00051     GetKey, CompareKeys, Sequence > base_type;
00052     
00053   typedef typename base_type::iterator heap_handle;
00054   typedef ads::Array<1,heap_handle> heap_handle_array_type;
00055 
00056   typedef HeapHandleArray<T, heap_handle> get_handle_functor;
00057 
00058   typedef typename base_type::sequence_type sequence_type;
00059 
00060  public:
00061 
00062   //
00063   // public typedefs
00064   //
00065 
00067   typedef typename base_type::element_type element_type;
00069   typedef typename base_type::const_reference const_reference;
00071   typedef typename base_type::key_type key_type;
00073   typedef typename base_type::size_type size_type;
00074 
00076   typedef typename base_type::value_type value_type;
00078   typedef typename base_type::iterator iterator;
00079 
00080  protected:
00081 
00082   //
00083   // Member data.
00084   //
00085 
00087   heap_handle_array_type _heap_handles;
00088 
00089  private:
00090 
00091   //
00092   // Not implemented.
00093   //
00094 
00095   // Copy constructor not implemented.
00096   PriorityQueueBinaryHeapArray( const PriorityQueueBinaryHeapArray& );
00097 
00098   // Assignment operator not implemented.
00099   const PriorityQueueBinaryHeapArray& 
00100   operator=( const PriorityQueueBinaryHeapArray& );
00101 
00102  public:
00103 
00104   //
00105   // Constructors, Destructor.
00106   //
00107 
00109 
00112   template <class DataArray>
00113   PriorityQueueBinaryHeapArray( const DataArray& data_array, 
00114                                 const sequence_type& 
00115                                 container = sequence_type() ) :
00116     base_type( get_handle_functor(), container ),
00117     _heap_handles( data_array.size() )
00118   {
00119     base_type::_get_handle.initialize( data_array, _heap_handles );
00120   }
00121 
00123   template <class DataArray>
00124   PriorityQueueBinaryHeapArray( const DataArray& data_array, size_type n ) :
00125     base_type( n ),
00126     _heap_handles( data_array.size() )
00127   {
00128     base_type::_get_handle.initialize( data_array, _heap_handles );
00129   }
00130 
00132   template <class DataArray, class InputIterator>
00133   PriorityQueueBinaryHeapArray( const DataArray& data_array,
00134                                 InputIterator first, 
00135                                 InputIterator last,
00136                                 const sequence_type& 
00137                                 container = sequence_type() ) :
00138     base_type( first, last, get_handle_functor(), container ),
00139     _heap_handles( data_array.size() )
00140   {
00141     base_type::_get_handle.initialize( data_array, _heap_handles );
00142   }
00143 
00145   virtual 
00146   ~PriorityQueueBinaryHeapArray()
00147   {}
00148   
00149 };
00150 
00151 END_NAMESPACE_ADS
00152 
00153 #endif

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