Program Listing for File UniversalHashing.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File UniversalHashing.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/dictionary/RandomHashing.h"
#include "ADS/numeric/NumberTheory.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iterator>
#include <optional>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS CarterWegmanHash --------------------------*/
/*--------------------------------------------------------------------------*/

class CarterWegmanHash {
 public:
 explicit CarterWegmanHash( std::uint64_t m , std::uint64_t seed = 1 );

 CarterWegmanHash( std::uint64_t p , std::uint64_t a , std::uint64_t b ,
                   std::uint64_t m );

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

 [[nodiscard]] std::uint64_t p( void ) const { return( f_p ); }
 [[nodiscard]] std::uint64_t a( void ) const { return( f_a ); }
 [[nodiscard]] std::uint64_t b( void ) const { return( f_b ); }
 [[nodiscard]] std::uint64_t m( void ) const { return( f_m ); }

 private:
 std::uint64_t f_p , f_a , f_b , f_m;
 };

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS DotProductHash ---------------------------*/
/*--------------------------------------------------------------------------*/

class DotProductHash {
 public:
 DotProductHash( std::uint64_t m , int r , std::uint64_t seed = 1 );

 DotProductHash( std::uint64_t m , std::vector< std::uint64_t > a );

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

 [[nodiscard]] std::uint64_t universe( void ) const;

 private:
 std::uint64_t f_m;
 std::vector< std::uint64_t > f_a;
 };

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS MultiplyShiftHash -------------------------*/
/*--------------------------------------------------------------------------*/

class MultiplyShiftHash {
 public:
 MultiplyShiftHash( int h , int l , std::uint64_t seed = 1 );

 [[nodiscard]] static MultiplyShiftHash ofMultiplier( int h , int l ,
                                                      std::uint64_t a );

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

 private:
 int f_h , f_l;
 std::uint64_t f_a;
 std::uint64_t f_mask;
 };

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS StringHash ----------------------------*/
/*--------------------------------------------------------------------------*/

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

 [[nodiscard]] std::uint64_t operator()( std::string_view s ) const;

 private:
 std::uint64_t f_x;
 };

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS DLeftHashTable ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class K , class V , class H = std::hash< K > >
class DLeftHashTable {

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

 using Key = K;
 using Value = V;

 DLeftHashTable( std::size_t m , int d , std::uint64_t seed = 1 ,
                 H h = H() );

 [[nodiscard]] std::optional< V > lookup( const K & k ) const;

 void insert( const K & k , const V & v );

 void remove( const K & k );

 [[nodiscard]] bool contains( const K & k ) const;

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

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

 [[nodiscard]] int tables( void ) const;

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

 using Bucket = std::vector< std::pair< K , V > >;

 public:

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

 // a constant view of the pairs ( key , value ), table after table and
 // list after list, forward; an insertion or a removal invalidates it

 class const_iterator {
  public:
  using reference = std::pair< const K & , const V & >;
  using value_type = reference;
  using difference_type = std::ptrdiff_t;
  using iterator_concept = std::forward_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;
  const_iterator( const std::vector< Bucket > * T , std::size_t b )
   : f_T( T ) , f_b( b ) { forward(); }

  reference operator*( void ) const {
   const auto & e = ( *f_T )[ f_b ][ f_i ];
   return( reference( e.first , e.second ) );
   }
  const_iterator & operator++( void ) {
   ++f_i;
   forward();
   return( *this );
   }
  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }
  bool operator==( const const_iterator & o ) const {
   return( ( f_b == o.f_b ) && ( f_i == o.f_i ) );
   }

  private:
  void forward( void ) {
   while( ( f_b < f_T->size() ) && ( f_i >= ( *f_T )[ f_b ].size() ) ) {
    ++f_b;
    f_i = 0;
    }
   }

  const std::vector< Bucket > * f_T = nullptr;
  std::size_t f_b = 0;
  std::size_t f_i = 0;
  };

 using value_type = std::pair< const K & , const V & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = value_type;
 using const_reference = value_type;
 using iterator = const_iterator;

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

 private:

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

 [[nodiscard]] std::optional< std::pair< std::size_t , std::size_t > >
  find( const K & k ) const;

 [[nodiscard]] bool placed( const K & k ) const;

 std::vector< Bucket > f_T;
 std::size_t f_w;
 std::vector< TabulationHash > f_g;
 std::size_t f_n = 0;
 H f_h;

 };  // end( class DLeftHashTable )

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

}  // end( namespace ADS )

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

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

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

#endif  /* UniversalHashing.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File UniversalHashing.h -----------------------*/
/*--------------------------------------------------------------------------*/