Program Listing for File SequenceHeap.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File SequenceHeap.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS SequenceHeap ----------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 using Item = T;

 static constexpr std::size_t M = 4096;

 static constexpr std::size_t K = 16;

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

 void push( const T & x );

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

 T pop( void );

 [[nodiscard]] bool empty( void ) const { return( f_n == 0 ); }

 [[nodiscard]] std::size_t size( void ) const { return( f_n ); }

 void clear( void );

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

 struct Run {
  std::vector< T > a;
  std::size_t at = 0;

  [[nodiscard]] bool done( void ) const { return( at == a.size() ); }
  [[nodiscard]] std::size_t left( void ) const { return( a.size() - at ); }
  };

 struct Group {
  std::vector< Run > seqs;
  Run buf;
  };

 void flush( void );

 void join( std::size_t i , Run && s );

 void refill( Group & g );

 void refillDeletion( void );

 static constexpr std::size_t D = 4;

 void up( std::size_t i );

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

 void ready( void );

 void close( void );

 void refillBulk( void );

 void sortRange( T * a , T * b );

 T * partition( T * a , T * b , const T & pv );

 void merge( std::vector< Run * > & R , std::vector< T > & out ,
             std::size_t n );

 void merge2( const T * a , std::size_t na , const T * b , std::size_t nb ,
              std::vector< T > & out ) const;

 [[nodiscard]] bool bt( const T & a , const T & b ) const {
  if constexpr( detail::kKeyed< T , Better > )
   return( detail::orderKeyBy< Better >( a ) <
           detail::orderKeyBy< Better >( b ) );
  else
   return( f_better( a , b ) );
  }

 [[nodiscard]] bool worse( const T & a , const T & b ) const {
  return( bt( b , a ) );
  }

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

 std::vector< T > f_ins;
 Run f_del;
 std::vector< Group > f_groups;
 std::vector< T > f_scratch;
 bool f_heaped = true;
 bool f_open = false;
 int f_scans = 0;
 bool f_minLast = false;
 std::vector< T , HugePageAllocator< T > > f_bulk;
 std::size_t f_lo = 0;
 std::vector< std::pair< std::size_t , std::size_t > > f_piv;
 Run f_bbuf;
 std::vector< T > f_key;
 std::vector< unsigned char > f_dead;
 std::vector< std::size_t > f_lose;
 std::vector< std::size_t > f_lose2;
 std::vector< T * > f_cur , f_end;
 std::size_t f_n = 0;
 Better f_better;

 };  // end( class SequenceHeap )

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

}  // end( namespace ADS )

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

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

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

#endif  /* SequenceHeap.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File SequenceHeap.h ------------------------*/
/*--------------------------------------------------------------------------*/