Program Listing for File RadixHeap.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File RadixHeap.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <array>
#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS RadixHeap ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , std::integral K = std::uint32_t , unsigned B = 4 >
class RadixHeap {

 static_assert( ( B >= 1 ) && ( B <= 8 ) , "a digit of 1 to 8 bits" );

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

 using Item = T;
 using Key = K;

 void push( const T & x , K k );

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

 [[nodiscard]] K topKey( void );

 [[nodiscard]] K peekKey( void ) const;

 T pop( void );

 template< class F >
 void extractBelow( K limit , F && f );

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

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

 void clear( void );

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

 using U = std::make_unsigned_t< K >;

 static constexpr unsigned W = std::numeric_limits< U >::digits;
 static constexpr unsigned ROWS = ( W + B - 1 ) / B;
 static constexpr unsigned R = 1u << B;
 static constexpr unsigned NB = ROWS * R;
 static constexpr unsigned NW = ( NB + 63 ) / 64;

 struct Entry {
  U key;
  T item;
  };

 static U encode( K k ) {
  if constexpr( std::is_signed_v< K > )
   return( U( k ) ^ ( U( 1 ) << ( W - 1 ) ) );
  else
   return( k );
  }

 static K decode( U u ) {
  if constexpr( std::is_signed_v< K > )
   return( K( u ^ ( U( 1 ) << ( W - 1 ) ) ) );
  else
   return( u );
  }

 unsigned bucket( U x ) const {
  const U d = x ^ f_last;
  const unsigned r = d ? unsigned( std::bit_width( d ) - 1 ) / B : 0;
  return( r * R + unsigned( ( x >> ( r * B ) ) & U( R - 1 ) ) );
  }

 void place( unsigned i , Entry && e ) {
  if( e.key < f_min[ i ] ) f_min[ i ] = e.key;
  f_mask[ i >> 6 ] |= std::uint64_t( 1 ) << ( i & 63 );
  f_B[ i ].push_back( std::move( e ) );
  }

 U ceiling( unsigned i ) const {
  const unsigned r = i / R , sh = ( r + 1 ) * B;
  const U high = sh >= W ? U( 0 ) : U( ( f_last >> sh ) << sh );
  const U low = r * B >= W ? ~U( 0 ) : U( ( U( 1 ) << ( r * B ) ) - 1 );
  return( U( high | ( U( i % R ) << ( r * B ) ) | low ) );
  }

 unsigned first( void ) const {
  for( unsigned w = 0 ; ; ++w )
   if( f_mask[ w ] )
    return( w * 64 + unsigned( std::countr_zero( f_mask[ w ] ) ) );
  }

 void pull( void );

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

 std::array< std::vector< Entry > , NB > f_B;
 std::array< U , NB > f_min = fill_max();
 std::array< std::uint64_t , NW > f_mask = {};
 U f_last = 0;
 unsigned f_cur = 0;
 std::size_t f_size = 0;

 static std::array< U , NB > fill_max( void ) {
  std::array< U , NB > a;
  a.fill( std::numeric_limits< U >::max() );
  return( a );
  }

 };  // end( class RadixHeap )

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

}  // end( namespace ADS )

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

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

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

#endif  /* RadixHeap.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File RadixHeap.h --------------------------*/
/*--------------------------------------------------------------------------*/