Program Listing for File RandomHashing.h

↰ Return to documentation for file (ADS/dictionary/RandomHashing.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File RandomHashing.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <array>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <vector>

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

namespace ADS {

[[nodiscard]] constexpr std::uint64_t splitmix64( std::uint64_t x );

[[nodiscard]] constexpr std::uint64_t fibonacciPlace( std::uint64_t h ,
                                                      int b );

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS SplitMix64 ------------------------------*/
/*--------------------------------------------------------------------------*/

class SplitMix64 {
 public:
 using result_type = std::uint64_t;

 explicit constexpr SplitMix64( std::uint64_t seed = 0 ) : f_s( seed ) {}

 constexpr std::uint64_t operator()( void ) {
  const std::uint64_t r = splitmix64( f_s );
  f_s += 0x9e3779b97f4a7c15ULL;
  return( r );
  }

 static constexpr std::uint64_t min( void ) { return( 0 ); }
 static constexpr std::uint64_t max( void ) {
  return( std::numeric_limits< std::uint64_t >::max() );
  }

 private:
 std::uint64_t f_s;
 };

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS ZobristTable ----------------------------*/
/*--------------------------------------------------------------------------*/

class ZobristTable {
 public:
 ZobristTable( std::size_t n , std::size_t m , std::uint64_t seed = 1 );

 [[nodiscard]] std::uint64_t operator()( std::size_t f ,
                                         std::size_t v ) const;

 template< class V >
 [[nodiscard]] std::uint64_t hash( const std::vector< V > & S ) const;

 [[nodiscard]] std::uint64_t update( std::uint64_t h , std::size_t f ,
                                     std::size_t a , std::size_t b ) const;

 private:
 std::size_t f_n , f_m;
 std::vector< std::uint64_t > f_R;
 };

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS TabulationHash ---------------------------*/
/*--------------------------------------------------------------------------*/

class TabulationHash {
 public:
 explicit TabulationHash( std::uint64_t seed = 1 );

 [[nodiscard]] std::uint64_t operator()( std::uint64_t x ) const;

 private:
 std::array< std::array< std::uint64_t , 256 > , 8 > f_T;
 };

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

}  // end( namespace ADS )

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

#include "ADS/dictionary/impl/RandomHashing.tpp"

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

#endif  /* RandomHashing.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File RandomHashing.h ------------------------*/
/*--------------------------------------------------------------------------*/