Program Listing for File FingerprintPerfectHash.h

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

/*--------------------------------------------------------------------------*/
/*---------------------- File FingerprintPerfectHash.h ---------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/dictionary/FastHash.h"

#include <algorithm>
#include <array>
#include <bit>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <type_traits>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------- CLASS FingerprintPerfectHash ----------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class H = DefaultHash< T > >
class FingerprintPerfectHash {

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

 using Key = T;

 explicit FingerprintPerfectHash( const std::vector< T > & keys ,
                                  double gamma = 2 , std::uint64_t seed = 1 ,
                                  H h = H() );

 [[nodiscard]] std::size_t operator()( const T & k ) const;

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

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

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

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

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

 static constexpr std::size_t kMaxLevels = 64;
 static constexpr std::size_t kBlock = 512;

 [[nodiscard]] std::uint64_t base( const T & k ) const;

 [[nodiscard]] static std::size_t place( std::uint64_t x , std::size_t i ,
                                         std::size_t m );

 [[nodiscard]] std::size_t rank( std::size_t g ) const;

 std::uint64_t f_seed;
 std::size_t f_n = 0;
 std::vector< std::uint64_t > f_bits;
 std::vector< std::uint32_t > f_rank;
 std::vector< std::size_t > f_at;
 std::vector< std::size_t > f_m;
 H f_h;

 };  // end( class FingerprintPerfectHash )

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

}  // end( namespace ADS )

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

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

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

#endif  /* FingerprintPerfectHash.h included */

/*--------------------------------------------------------------------------*/
/*--------------------- End File FingerprintPerfectHash.h ------------------*/
/*--------------------------------------------------------------------------*/