Program Listing for File HeapPriorityQueue.h

↰ Return to documentation for file (ADS/priority/HeapPriorityQueue.h)

/*--------------------------------------------------------------------------*/
/*------------------------ File HeapPriorityQueue.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_HeapPriorityQueue
 #define __ADS_HeapPriorityQueue
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/Iterators.h"
#include "ADS/memory/ObjectPool.h"
#include "ADS/priority/PriorityQueue.h"

#include <concepts>
#include <cstddef>
#include <memory>
#include <utility>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS HeapPriorityQueue -------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , std::totally_ordered P = int , int D = 2 >
 requires( D >= 2 )
class HeapPriorityQueue {

/*--------------------------------------------------------------------------*/
 public:

 struct PriorityItem {
  P priority;
  T value;
  int pos;
  };

 using Item = T;
 using Priority = P;
 using Handle = PriorityItem *;

 explicit HeapPriorityQueue( int n );

 HeapPriorityQueue( const HeapPriorityQueue & ) = delete;
 HeapPriorityQueue & operator=( const HeapPriorityQueue & ) = delete;

 HeapPriorityQueue( HeapPriorityQueue && other ) noexcept;

 HeapPriorityQueue & operator=( HeapPriorityQueue && other ) noexcept;

 ~HeapPriorityQueue();

 [[nodiscard]] bool empty( void ) const;

 [[nodiscard]] int size( void ) const;

 [[nodiscard]] int capacity( void ) const;

 [[nodiscard]] const T & min( void ) const;

 [[nodiscard]] const P & minPriority( void ) const;

 T deleteMin( void );

 Handle insert( const T & x , const P & p );

 void decrease( Handle y , const P & p );

 [[nodiscard]] std::vector< P > priorities( void ) const;

 static int parent( int i ) { return( ( i - 1 ) / D ); }

 static int child( int i , int j ) { return( D * i + j + 1 ); }

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 // a constant view of the items with their priorities, PriorityItem, in
 // the order of the heap (the minimum first, the rest in no useful order),
 // random access; a change through it would break the heap

 using value_type = PriorityItem;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const PriorityItem &;
 using const_reference = const PriorityItem &;
 using const_iterator = IndirectIterator<
  typename std::vector< PriorityItem * >::const_iterator >;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( f_H.begin() ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( f_H.end() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

/*--------------------------------------------------------------------------*/
 private:

 void swap( int i , int j );

 void up( int i );

 void minHeapRestore( int i , int dim );

 [[nodiscard]] bool owns( Handle y ) const;

 [[nodiscard]] bool isHeap( void ) const;

 int f_capacity;
 std::vector< PriorityItem * > f_H;
 ObjectPool< PriorityItem > f_pool;

 };  // end( class HeapPriorityQueue )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/priority/impl/HeapPriorityQueue.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* HeapPriorityQueue.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File HeapPriorityQueue.h ----------------------*/
/*--------------------------------------------------------------------------*/