Program Listing for File MinMaxHeap.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File MinMaxHeap.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/priority/OrderKey.h"
#include "ADS/sort/Sort.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS MinMaxHeap -----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Better = std::less< T > >
class MinMaxHeap {

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

 using Item = T;

 explicit MinMaxHeap( Better better = Better() )
  : f_better( std::move( better ) ) {}

 void push( const T & x );

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

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

 T popMin( void );

 T popMax( void );

 [[nodiscard]] bool empty( void ) const { return( size() == 0 ); }
 [[nodiscard]] std::size_t size( void ) const {
  return( f_sorted ? f_hi - f_lo : f_A.size() );
  }
 void reserve( std::size_t n ) { f_A.reserve( n ); }
 void clear( void ) {
  f_A.clear();
  f_sorted = false;
  f_run = 0;
  }

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

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

 static bool minLevel( std::size_t i ) {
  return( ( std::bit_width( i + 1 ) - 1 ) % 2 == 0 );
  }

 template< bool Min >
 bool first( const T & a , const T & b ) const {
  return( Min ? f_better( a , b ) : f_better( b , a ) );
  }

 template< bool Min >
 void up( std::size_t i );

 template< bool Min >
 void down( std::size_t i );

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

 void run( void );

 void unsort( void );

 std::vector< T > f_A;
 Better f_better;
 bool f_sorted = false;
 std::size_t f_lo = 0 , f_hi = 0;
 std::size_t f_run = 0;

 };  // end( class MinMaxHeap )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS IntervalHeap ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Better = std::less< T > >
class IntervalHeap {

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

 using Item = T;

 explicit IntervalHeap( Better better = Better() )
  : f_better( std::move( better ) ) {}

 void push( const T & x );

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

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

 T popMin( void );

 T popMax( void );

 [[nodiscard]] bool empty( void ) const { return( size() == 0 ); }
 [[nodiscard]] std::size_t size( void ) const {
  return( f_sorted ? f_hi - f_lo : f_A.size() );
  }
 void reserve( std::size_t n ) { f_A.reserve( n ); }
 void clear( void ) {
  f_A.clear();
  f_sorted = false;
  f_run = 0;
  }

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

 [[nodiscard]] std::size_t hi( std::size_t j ) const {
  return( 2 * j + 1 < f_A.size() ? 2 * j + 1 : 2 * j );
  }

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

 void run( void );

 void unsort( void );

 std::vector< T > f_A;
 Better f_better;
 bool f_sorted = false;
 std::size_t f_lo = 0 , f_hi = 0;
 std::size_t f_run = 0;

 };  // end( class IntervalHeap )

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

}  // end( namespace ADS )

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

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

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

#endif  /* MinMaxHeap.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File MinMaxHeap.h -------------------------*/
/*--------------------------------------------------------------------------*/