Program Listing for File PerfectHashing.h

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

/*--------------------------------------------------------------------------*/
/*------------------------- File PerfectHashing.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/Iterators.h"
#include "ADS/dictionary/RandomHashing.h"
#include "ADS/dictionary/UniversalHashing.h"

#include <algorithm>
#include <cmath>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <stdexcept>
#include <string_view>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS PerfectHashTable --------------------------*/
/*--------------------------------------------------------------------------*/

class PerfectHashTable {

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

 using Key = std::uint64_t;

 explicit PerfectHashTable( const std::vector< std::uint64_t > & S ,
                            std::uint64_t seed = 1 );

 [[nodiscard]] bool contains( std::uint64_t k ) const;

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

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

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

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

 static constexpr std::uint64_t kEmpty = ~std::uint64_t( 0 );
 static constexpr std::size_t kMaxTrials = 1000;

 struct Bucket {
  std::size_t offset = 0;
  std::size_t size = 0;
  CarterWegmanHash h = CarterWegmanHash( 1 );
  };

 public:

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 // a constant view of the keys, in the order of the places, bidirectional

 struct Places {
  static std::size_t size( const auto & o ) { return( o.f_T.size() ); }
  static bool occupied( const auto & o , std::size_t i ) {
   return( o.f_T[ i ] != kEmpty );
   }
  static const std::uint64_t & read( const auto & o , std::size_t i ) {
   return( o.f_T[ i ] );
   }
  };

 using value_type = std::uint64_t;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const std::uint64_t &;
 using const_reference = const std::uint64_t &;
 using const_iterator = SlotIterator< PerfectHashTable , Places >;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , f_T.size() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 private:

 CarterWegmanHash f_h;
 std::vector< Bucket > f_B;
 std::vector< std::uint64_t > f_T;
 std::size_t f_n = 0;
 std::size_t f_trials = 0;

 };  // end( class PerfectHashTable )

/*--------------------------------------------------------------------------*/
/*-------------------- CLASS OrderedMinimalPerfectHash ---------------------*/
/*--------------------------------------------------------------------------*/

template< class K >
 requires( std::integral< K > ||
           std::convertible_to< const K & , std::string_view > )
class OrderedMinimalPerfectHash {

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

 using Key = K;

 explicit OrderedMinimalPerfectHash( const std::vector< K > & keys ,
                                     int r = 2 , double c = 0 ,
                                     std::uint64_t seed = 1 );

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

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

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

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

 [[nodiscard]] static std::optional< std::vector< std::uint32_t > >
  labelAcyclicGraph( std::size_t m , const std::vector< std::size_t > & E ,
                     const std::vector< std::size_t > & h , std::size_t n );

 [[nodiscard]] static std::optional< std::vector< std::uint32_t > >
  labelByPeeling( std::size_t m , const std::vector< std::size_t > & E ,
                  int r , const std::vector< std::size_t > & h ,
                  std::size_t n );

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

 static constexpr std::size_t kMaxTrials = 1000;

 [[nodiscard]] std::uint64_t fingerprint( const K & k , int i ) const;

 [[nodiscard]] std::size_t vertex( const K & k , int i ) const;

 int f_r;
 std::size_t f_n = 0;
 std::size_t f_m = 0;
 std::size_t f_block = 0;
 std::size_t f_trials = 0;
 std::vector< std::uint64_t > f_seed;
 std::vector< CarterWegmanHash > f_h;
 std::vector< std::uint32_t > f_g;

 };  // end( class OrderedMinimalPerfectHash )

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

}  // end( namespace ADS )

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

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

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

#endif  /* PerfectHashing.h included */

/*--------------------------------------------------------------------------*/
/*----------------------- End File PerfectHashing.h ------------------------*/
/*--------------------------------------------------------------------------*/