Program Listing for File PairingHeap.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File PairingHeap.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS PairingHeap -----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , std::totally_ordered P = int , bool Aux = false >
class PairingHeap {

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

 struct Node {
  P priority;
  T value;
  Node * child = nullptr;
  Node * next = nullptr;
  Node * prev = nullptr;
  };

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

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

 PairingHeap( PairingHeap && other ) noexcept;

 ~PairingHeap();

 [[nodiscard]] bool empty( void ) const { return( f_root == nullptr ); }

 [[nodiscard]] int size( void ) const { return( f_n ); }

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

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

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

 T deleteMin( void );

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

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

 static Node * link( Node * a , Node * b );

 static Node * twoPass( Node * x );

 static Node * multiPass( Node * x );

 static void cut( Node * x );

 [[nodiscard]] static bool tree( const Node * x , int & n );

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

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

 };  // end( class PairingHeap )

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

}  // end( namespace ADS )

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

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

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

#endif  /* PairingHeap.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File PairingHeap.h -------------------------*/
/*--------------------------------------------------------------------------*/