Program Listing for File DialQueue.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File DialQueue.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/priority/RadixHeap.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS DialQueue ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , std::integral K = std::uint32_t >
class DialQueue {

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

 using Item = T;
 using Key = K;

 explicit DialQueue( std::size_t c = 1023 );

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

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

 [[nodiscard]] K topKey( 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 );

 [[nodiscard]] std::size_t window( void ) const { return( f_B.size() ); }

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

 using U = std::make_unsigned_t< K >;
 static U encode( K k ) {
  if constexpr( std::is_signed_v< K > )
   return( U( k ) ^ ( U( 1 ) << ( std::numeric_limits< U >::digits - 1 ) ) );
  else
   return( k );
  }

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

 void put( const T & x , U u );

 void pull( void );

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

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

 std::vector< std::vector< T > > f_B;
 std::vector< std::uint64_t > f_bits;
 U f_cur = 0;
 std::size_t f_in = 0;
 std::size_t f_n = 0;
 RadixHeap< T , U > f_over;

 };  // end( class DialQueue )

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

}  // end( namespace ADS )

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

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

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

#endif  /* DialQueue.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File DialQueue.h --------------------------*/
/*--------------------------------------------------------------------------*/