Program Listing for File ChainedHashTable.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File ChainedHashTable.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/dictionary/TableSize.h"
#include "ADS/sequence/List.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS ChainedHashTable -------------------------*/
/*--------------------------------------------------------------------------*/

enum class Chain {
 FRONT ,
 MOVE_TO_FRONT ,
 SORTED
 };

template< class K , class V , Chain C = Chain::FRONT ,
          class H = std::hash< K > >
 requires( C != Chain::SORTED || std::totally_ordered< K > )
class ChainedHashTable {

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

 using Key = K;
 using Value = V;

 explicit ChainedHashTable( std::size_t m , bool restructure = false ,
                            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]] bool empty( void ) const;

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

 [[nodiscard]] double load( void ) const;

 template< class F >
 void forEach( F && f ) const;

 [[nodiscard]] std::vector< K > chain( std::size_t i ) const;

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

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

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

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

 using Pair = std::pair< K , V >;
 using Bucket = List< Pair , false >;
 using Pos = typename Bucket::Pos;

 public:

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

 // a constant view of the pairs ( key , value ), list by list, forward;
 // with Chain::MOVE_TO_FRONT even a lookup moves a pair, and with the
 // restructuring an insertion or a removal rebuilds the table, both of
 // which invalidate it

 class const_iterator {
  using Lists = std::vector< Bucket >;

  public:
  using iterator_category = std::forward_iterator_tag;
  using value_type = Pair;
  using difference_type = std::ptrdiff_t;
  using reference = const Pair &;
  using pointer = const Pair *;

  const_iterator( void ) = default;

  const_iterator( const Lists * T , std::size_t b ) : f_T( T ) , f_b( b ) {
   if( f_b < f_T->size() ) f_c = ( *f_T )[ f_b ].begin();
   settle();
   }

  reference operator*( void ) const { return( *f_c ); }
  pointer operator->( void ) const { return( &*f_c ); }

  const_iterator & operator++( void ) {
   ++f_c;
   settle();
   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_T == nullptr ) || ( f_b >= f_T->size() ) ||
             ( f_c == o.f_c ) ) );
   }

  private:
  void settle( void ) {                     // past the empty lists
   while( ( f_b < f_T->size() ) && ( f_c == ( *f_T )[ f_b ].end() ) )
    if( ++f_b < f_T->size() ) f_c = ( *f_T )[ f_b ].begin();
   }

  const Lists * f_T = nullptr;
  std::size_t f_b = 0;
  typename Bucket::const_iterator f_c;
  };

 using value_type = Pair;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = const Pair &;
 using const_reference = const Pair &;
 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 place( const K & k ) const;

 Pos find( const Bucket & L , const K & k ) const;

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

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

 [[nodiscard]] bool listOk( std::size_t i , const K & k ,
                            std::size_t & n ) const;

 void rebuild( std::size_t m );

 mutable std::vector< Bucket > f_T;
 std::size_t f_m0;
 bool f_restructure;
 H f_h;
 std::size_t f_size = 0;
 mutable std::size_t f_probes = 0;
 std::size_t f_rebuilds = 0;
 std::size_t f_moved = 0;

 };  // end( class ChainedHashTable )

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

}  // end( namespace ADS )

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

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

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

#endif  /* ChainedHashTable.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File ChainedHashTable.h -----------------------*/
/*--------------------------------------------------------------------------*/