Program Listing for File DaryHeap.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File DaryHeap.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/memory/HugePageAllocator.h"

#include <cstddef>
#include <functional>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS DaryHeap ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Better = std::less< T > , unsigned D = 4 ,
          bool BottomUp = false >
class DaryHeap {

 static_assert( D >= 2 , "a heap needs at least two children per node" );

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

 using Item = T;

 explicit DaryHeap( Better better = Better() );

 void push( const T & x );

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

 T pop( void );

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

 [[nodiscard]] std::size_t size( void ) const;

 void reserve( std::size_t n );

 void clear( void );

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

 // a constant view of the items in the order of the heap (the root first,
 // the rest in no useful order), contiguous; a change through it would
 // break the heap

 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const T &;
 using const_reference = const T &;
 using iterator = const T *;
 using const_iterator = const T *;

 [[nodiscard]] const_iterator begin( void ) const { return( f_A.data() ); }
 [[nodiscard]] const_iterator end( void ) const {
  return( f_A.data() + f_A.size() );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 // the hole at i moves up (down) until x fits in it; x comes as a value,
 // never stored and read back, which would stall the forwarding of the
 // store to the load

 void up( std::size_t i , T x );

 void down( std::size_t i , T x );

 void bottomUp( T x );

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

 std::vector< T , HugePageAllocator< T > > f_A;
 Better f_better;

 };  // end( class DaryHeap )

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

}  // end( namespace ADS )

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

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

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

#endif  /* DaryHeap.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File DaryHeap.h ---------------------------*/
/*--------------------------------------------------------------------------*/