Program Listing for File KnuthHashing.h

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

/*--------------------------------------------------------------------------*/
/*-------------------------- File KnuthHashing.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/Iterators.h"

#include <cstddef>
#include <functional>
#include <optional>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS CoalescedHashTable ------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 explicit CoalescedHashTable( std::size_t m , std::size_t cellar = 0 ,
                              H h = H() );

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

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

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

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

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

 // a constant view of the pairs ( key , value ), in the order of the
 // places (the cellar last), 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 ].used );
   }
  static auto read( const auto & o , std::size_t i ) {
   return( std::pair< const K & , const V & >( o.f_T[ i ].key ,
                                              o.f_T[ i ].value ) );
   }
  };

 using value_type = std::pair< const K & , const V & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = std::pair< const K & , const V & >;
 using const_reference = std::pair< const K & , const V & >;
 using const_iterator = SlotIterator< CoalescedHashTable , 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 , Places::size( *this ) ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 struct Slot {
  bool used = false;
  K key{};
  V value{};
  long link = -1;
  };

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

 std::vector< Slot > f_T;
 std::size_t f_m;
 long f_free;
 std::size_t f_size = 0;
 mutable std::size_t f_probes = 0;
 H f_h;

 };  // end( class CoalescedHashTable )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS BrentHashTable --------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 explicit BrentHashTable( std::size_t m , H h = H() );

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

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

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

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

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

 // a constant view of the pairs ( key , value ), in the order of the
 // places, bidirectional; an insertion may move the pairs

 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 ].has_value() );
   }
  static const std::pair< K , V > & read( const auto & o , std::size_t i ) {
   return( *o.f_T[ i ] );
   }
  };

 using value_type = std::pair< K , V >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const std::pair< K , V > &;
 using const_reference = const std::pair< K , V > &;
 using const_iterator = SlotIterator< BrentHashTable , 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 , Places::size( *this ) ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

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

 std::vector< std::optional< std::pair< K , V > > > f_T;
 std::size_t f_size = 0;
 mutable std::size_t f_probes = 0;
 H f_h;

 };  // end( class BrentHashTable )

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

}  // end( namespace ADS )

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

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

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

#endif  /* KnuthHashing.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File KnuthHashing.h -------------------------*/
/*--------------------------------------------------------------------------*/