PriorityQueueBinaryHeapArray.h

Go to the documentation of this file.

// -*- C++ -*-

#if !defined(__ads_PriorityQueueBinaryHeapArray_h__)
#define __ads_PriorityQueueBinaryHeapArray_h__

#include "PriorityQueueBinaryHeapDynamicKeys.h"
#include "HeapHandleArray.h"

#include "../array/Array.h"

BEGIN_NAMESPACE_ADS


template < typename T,
           typename Key = typename std::iterator_traits<T>::value_type,
           class GetKey = Dereference<T>,
           class CompareKeys = std::less<Key>, 
           class Sequence = std::vector<T> >
class PriorityQueueBinaryHeapArray :
  public PriorityQueueBinaryHeapDynamicKeys
  < T, HeapHandleArray<T, typename Sequence::iterator>, Key,
    GetKey, CompareKeys, Sequence >
{
 private:

  typedef PriorityQueueBinaryHeapDynamicKeys
  < T, HeapHandleArray<T, typename Sequence::iterator>, Key,
    GetKey, CompareKeys, Sequence > base_type;
    
  typedef typename base_type::iterator heap_handle;
  typedef ads::Array<1,heap_handle> heap_handle_array_type;

  typedef HeapHandleArray<T, heap_handle> get_handle_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;
  typedef typename base_type::iterator iterator;

 protected:

  //
  // Member data.
  //

  heap_handle_array_type _heap_handles;

 private:

  //
  // Not implemented.
  //

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

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

 public:

  //
  // Constructors, Destructor.
  //


  template <class DataArray>
  PriorityQueueBinaryHeapArray( const DataArray& data_array, 
                                const sequence_type& 
                                container = sequence_type() ) :
    base_type( get_handle_functor(), container ),
    _heap_handles( data_array.size() )
  {
    base_type::_get_handle.initialize( data_array, _heap_handles );
  }

  template <class DataArray>
  PriorityQueueBinaryHeapArray( const DataArray& data_array, size_type n ) :
    base_type( n ),
    _heap_handles( data_array.size() )
  {
    base_type::_get_handle.initialize( data_array, _heap_handles );
  }

  template <class DataArray, class InputIterator>
  PriorityQueueBinaryHeapArray( const DataArray& data_array,
                                InputIterator first, 
                                InputIterator last,
                                const sequence_type& 
                                container = sequence_type() ) :
    base_type( first, last, get_handle_functor(), container ),
    _heap_handles( data_array.size() )
  {
    base_type::_get_handle.initialize( data_array, _heap_handles );
  }

  virtual 
  ~PriorityQueueBinaryHeapArray()
  {}
  
};

END_NAMESPACE_ADS

#endif

---