Program Listing for File LinkedHeapPriorityQueue.h

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

/*--------------------------------------------------------------------------*/
/*--------------------- File LinkedHeapPriorityQueue.h ---------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_LinkedHeapPriorityQueue
 #define __ADS_LinkedHeapPriorityQueue
                      /* 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>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------- CLASS LinkedHeapPriorityQueue ----------------------*/
/*--------------------------------------------------------------------------*/

template< class T , std::totally_ordered P = int , bool L = false >
class LinkedHeapPriorityQueue {

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

 using Item = T;
 using Priority = P;

 LinkedHeapPriorityQueue( void ) = default;
 LinkedHeapPriorityQueue( const LinkedHeapPriorityQueue & ) = delete;
 LinkedHeapPriorityQueue & operator=( const LinkedHeapPriorityQueue & ) =
  delete;

 LinkedHeapPriorityQueue( LinkedHeapPriorityQueue && other ) noexcept;

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

 ~LinkedHeapPriorityQueue();

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

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

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

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

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

 T deleteMin( void );

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

 struct Node {
  P priority;
  T value;
  Node * parent;
  Node * left = nullptr , * right = nullptr;
  Node( const P & p , const T & v , Node * u )
   : priority( p ) , value( v ) , parent( u ) {}
  };

 public:

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

 // a constant view of the pairs ( priority , item ), in the symmetric
 // order of the tree (no useful order), bidirectional

 struct Shape {
  static auto root( const auto & o ) {
   return( static_cast< const Node * >( o.f_root ) );
   }
  static auto left( const auto * n ) {
   return( static_cast< const Node * >( n->left ) );
   }
  static auto right( const auto * n ) {
   return( static_cast< const Node * >( n->right ) );
   }
  static auto read( const auto * n ) {
   return( std::pair< const P & , const T & >( n->priority , n->value ) );
   }
  };

 using value_type = std::pair< const P & , const T & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = value_type;
 using const_reference = value_type;
 using const_iterator = PathIterator< LinkedHeapPriorityQueue , Shape >;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , true ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , false ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 private:

 Node * at( int k ) const;

 static void swap_contents( Node * a , Node * b );

 [[nodiscard]] bool shaped( const Node * u , int k , int & n ) const;

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

 [[nodiscard]] Node * nextParent( void ) const;

 [[nodiscard]] Node * previousLeaf( void ) const;

 void release( Node * u );

 Node * f_root = nullptr;
 Node * f_last = nullptr;
 int f_n = 0;
 ObjectPool< Node > f_pool;

 };  // end( class LinkedHeapPriorityQueue )

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

}  // end( namespace ADS )

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

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

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

#endif  /* LinkedHeapPriorityQueue.h included */

/*--------------------------------------------------------------------------*/
/*------------------- End File LinkedHeapPriorityQueue.h -------------------*/
/*--------------------------------------------------------------------------*/