Program Listing for File BloomVariants.h

↰ Return to documentation for file (ADS/set/BloomVariants.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File BloomVariants.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/dictionary/RandomHashing.h"
#include "ADS/set/BloomFilter.h"

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <unordered_set>
#include <utility>
#include <vector>

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

namespace ADS {

[[nodiscard]] inline double bloomFalsePositive( double m , double n ,
                                                int r );

[[nodiscard]] inline int bloomBestHashes( double m , double n );

[[nodiscard]] inline double bloomLowerBound( double n , double epsilon );

[[nodiscard]] inline double bloomBits( double n , double epsilon );

[[nodiscard]] inline std::pair< double , double > compressedBloom(
                                                   double bitsPerKey , int r );

template< class T , class H = std::hash< T > >
[[nodiscard]] std::pair< std::vector< T > , std::vector< T > >
 bloomIntersection( const std::vector< T > & A , const std::vector< T > & B ,
                    std::size_t mA );

/*--------------------------------------------------------------------------*/
/*----------------------- CLASS SpectralBloomFilter ------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class C = std::uint32_t , class H = std::hash< T > >
class SpectralBloomFilter {

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

 SpectralBloomFilter( std::size_t m , int r , H h = H() );

 void insert( const T & x , C f = 1 );

 void remove( const T & x , C f = 1 );

 [[nodiscard]] C count( const T & x ) const;

 [[nodiscard]] bool maybe( const T & x ) const;

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

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

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

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

 [[nodiscard]] std::vector< std::size_t > places( const T & x ) const;

 std::vector< C > f_C;
 int f_r;
 H f_h;

 };  // end( class SpectralBloomFilter )

/*--------------------------------------------------------------------------*/
/*---------------------- CLASS PartitionedBloomFilter ----------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class H = std::hash< T > >
class PartitionedBloomFilter {

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

 PartitionedBloomFilter( std::size_t m , int r , H h = H() );

 void insert( const T & x );

 [[nodiscard]] bool maybe( const T & x ) const;

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

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

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

 [[nodiscard]] detail::BloomProbe probe( const T & x ) const;

 std::vector< bool > f_B;
 std::size_t f_w;
 int f_r;
 H f_h;

 };  // end( class PartitionedBloomFilter )

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

}  // end( namespace ADS )

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

#include "ADS/set/impl/BloomVariants.tpp"

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

#endif  /* BloomVariants.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File BloomVariants.h ------------------------*/
/*--------------------------------------------------------------------------*/