PriorityQueueBinaryHeapDynamicKeys.h

Go to the documentation of this file.

// -*- C++ -*-

#if !defined(__ads_PriorityQueueBinaryHeapDynamicKeys_h__)
#define __ads_PriorityQueueBinaryHeapDynamicKeys_h__

#include "PriorityQueue.h"

#include "../functor/compose.h"

#include <vector>

BEGIN_NAMESPACE_ADS


template < typename T,
           class GetHandle,
           typename Key = typename std::iterator_traits<T>::value_type,
           class GetKey = Dereference<T>,
           class CompareKeys = std::less<Key>, 
           class Sequence = std::vector<T> >
class PriorityQueueBinaryHeapDynamicKeys :
  public PriorityQueue<T, Key, GetKey, CompareKeys, Sequence>
{
 protected:

  typedef PriorityQueue<T, Key, GetKey, CompareKeys, Sequence> base_type;
  typedef GetHandle get_handle_functor;
  typedef typename base_type::get_key_functor get_key_functor;
  typedef typename base_type::compare_keys_functor compare_keys_functor;
  typedef typename base_type::sequence_type sequence_type;
  typedef ads::binary_compose_binary_unary< compare_keys_functor, 
                                            get_key_functor, 
                                            get_key_functor > 
  compare_values_functor;

 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;
  typedef typename base_type::difference_type difference_type;

 protected:

  //
  // Member data.
  //

  get_handle_functor _get_handle;
  compare_values_functor _compare;
  sequence_type _container;

 private:

  //
  // Not implemented.
  //

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

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

 public:

  //
  // Constructors, Destructor.
  //


  explicit
  PriorityQueueBinaryHeapDynamicKeys( const get_handle_functor& 
                                      get_handle = get_handle_functor(),
                                      const sequence_type& 
                                      container = sequence_type() ) :
    _get_handle( get_handle ),
    _compare(),
    _container( container )
  {
    make();
  }

  explicit 
  PriorityQueueBinaryHeapDynamicKeys( size_type n,
                                      const get_handle_functor& 
                                      get_handle = get_handle_functor() ) :
    _get_handle( get_handle ),
    _compare(),
    _container()
  {
    _container.reserve( n ); 
  }

  template <class InputIterator>
  PriorityQueueBinaryHeapDynamicKeys( InputIterator first, 
                                      InputIterator last,
                                      const get_handle_functor& 
                                      get_handle = get_handle_functor(),
                                      const sequence_type& 
                                      container = sequence_type() ) :
    _get_handle( get_handle ),
    _compare(),
    _container( container )
  { 
    _container.insert( _container.end(), first, last);
    make();
  }

  virtual 
  ~PriorityQueueBinaryHeapDynamicKeys()
  {}
  
  //
  // Accessors
  //

  size_type
  size() const
  {
    return _container.size();
  }

  bool
  empty() const
  {
    return _container.empty();
  }

  const_reference
  top() const
  { 
    return _container.front(); 
  }

  //
  // Manipulators
  //

  void 
  push( element_type x )
  {
    // If we don't have to resize the container.
    if ( _container.size() < _container.capacity() ) {
      // Add the element.
      _container.push_back( x );
      // Set the element's handle.
      _get_handle( _container.back() ) = _container.end() - 1;
    }
    // The container will be resized when the element is added.
    else {
      // Add the element.
      _container.push_back( x );
      // Fix the element handles.
      set_handles();
    }
    // Insert the element in the heap.
    decrease( _container.end() - 1 );
  }

  void 
  pop()
  {
    // Store and erase the last element.
    value_type tmp( _container.back() );
    _container.pop_back();

    // Adjust the heap.
    difference_type parent = 0;
    difference_type child = small_child( parent );
    while ( child >= 0 && 
            _compare( *( _container.begin() + child ), tmp ) ) {
      copy( _container.begin() + parent, _container.begin() + child );
      parent = child;
      child = small_child( parent );
    }

    // Insert the last element.
    copy( _container.begin() + parent, iterator(&tmp) );
  }

  void 
  decrease( element_type x )
  {
    decrease( _get_handle( x ) );
  }

 protected:

  void
  make()
  {
    for ( iterator i = _container.begin(); i != _container.end(); ++i ) {
      _get_handle( *i ) = i;
      decrease( i );
    }
  }

  void 
  decrease( iterator iter )
  {
    difference_type child = iter - _container.begin();
    difference_type parent = (child - 1) / 2;

    while ( child > 0 && 
            _compare( *( _container.begin() + child ), 
                      *( _container.begin() + parent ) ) ) {
      swap( _container.begin() + child, _container.begin() + parent );
      child = parent;
      parent = (child - 1) / 2;
    }
  }

  void 
  swap( iterator a, iterator b )
  {
    std::swap( _get_handle( *a ), _get_handle( *b ) );
    std::swap( *a, *b );
  }

  void 
  copy( iterator a, iterator b )
  {
    *a = *b;
    _get_handle( *a ) = a;
  }

  void 
  set_handles()
  {
    for ( iterator i = _container.begin(); i != _container.end(); ++i ) {
      _get_handle( *i ) = i;
    }
  }

  difference_type 
  small_child( difference_type parent )
  {
    difference_type child = 2 * parent + 1;
    if ( child + 1 < static_cast<difference_type>( size() ) &&
         _compare( *( _container.begin() + child + 1 ),
                   *( _container.begin() + child ) ) ) {
      ++child;
    }
    if ( child < static_cast<difference_type>( size() ) ) {
      return child;
    }
    return -1;
  }

};

END_NAMESPACE_ADS

#endif

---