Program Listing for File FibonacciHeapPriorityQueue.h

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

/*--------------------------------------------------------------------------*/
/*------------------- File FibonacciHeapPriorityQueue.h --------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_FibonacciHeapPriorityQueue
 #define __ADS_FibonacciHeapPriorityQueue
                      /* 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 <iterator>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------- CLASS FibonacciHeapPriorityQueue ---------------------*/
/*--------------------------------------------------------------------------*/

template< class T , std::totally_ordered P = int >
class FibonacciHeapPriorityQueue {

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

 struct Node {
  P priority;
  T value;
  Node * parent = nullptr;
  Node * child = nullptr;
  Node * left = this;
  Node * right = this;
  int degree = 0;
  bool mark = false;
  };

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

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

 FibonacciHeapPriorityQueue( FibonacciHeapPriorityQueue && other ) noexcept;

 ~FibonacciHeapPriorityQueue();

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

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

 [[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 );

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

 // a constant view of the pairs ( priority , item ), in preorder over the
 // circular lists of the roots and of the children (no useful order),
 // forward; a list is done when the walk is back at its first node, the
 // child of the parent (or the minimum, for the roots)

 class const_iterator {
  public:
  using reference = std::pair< const P & , const T & >;
  using value_type = reference;
  using difference_type = std::ptrdiff_t;
  using iterator_concept = std::forward_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;
  explicit const_iterator( const Node * min ) : f_x( min ) , f_min( min ) {}

  reference operator*( void ) const {
   return( reference( f_x->priority , f_x->value ) );
   }

  const_iterator & operator++( void ) {
   if( f_x->child ) {
    f_x = f_x->child;
    return( *this );
    }
   while( f_x ) {
    const Node * first = f_x->parent ? f_x->parent->child : f_min;
    if( f_x->right != first ) {
     f_x = f_x->right;
     return( *this );
     }
    f_x = f_x->parent;                      // the list is done
    }
   return( *this );
   }

  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }

  bool operator==( const const_iterator & o ) const {
   return( f_x == o.f_x );
   }

  private:
  const Node * f_x = nullptr;
  const Node * f_min = nullptr;
  };

 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 iterator = const_iterator;

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

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

 static void unlink( Node * x );

 static void splice( Node * x , Node * y );

 static void remove( Node * x , Node * & head );

 void add_root( Node * z );

 void cut( Node * x , Node * y );

 void consolidate( Node * w );

 [[nodiscard]] bool owns( const Node * x ) const;

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

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

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

 };  // end( class FibonacciHeapPriorityQueue )

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

}  // end( namespace ADS )

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

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

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

#endif  /* FibonacciHeapPriorityQueue.h included */

/*--------------------------------------------------------------------------*/
/*----------------- End File FibonacciHeapPriorityQueue.h ------------------*/
/*--------------------------------------------------------------------------*/