83template <data_layout data_layout_mode_ = data_layout::uncompressed>
88 template <data_layout data_layout_mode>
97 size_t size_in_bits{};
106 13043817825332782213ULL,
107 10650232656628343401ULL,
108 16499269484942379435ULL,
109 4893150838803335377ULL};
118 inline constexpr size_t hash_and_fit(
size_t h,
size_t const seed)
const
121 h ^= h >> hash_shift;
122 h *= 11400714819323198485ULL;
124#ifdef __SIZEOF_INT128__
125 h =
static_cast<uint64_t
>((
static_cast<__uint128_t
>(h) *
static_cast<__uint128_t
>(size_in_bits)) >> 64);
161 size_in_bits = size.get();
162 hash_funs = funs.get();
164 if (hash_funs == 0 || hash_funs > 5)
165 throw std::logic_error{
"The number of hash functions must be > 0 and <= 5."};
166 if (size_in_bits == 0)
170 data = sdsl::bit_vector(size_in_bits);
187 std::tie(size_in_bits, hash_shift, hash_funs) =
std::tie(bf.size_in_bits, bf.hash_shift, bf.hash_funs);
189 data = sdsl::sd_vector<>{bf.data};
210 for (
size_t i = 0; i < hash_funs; ++i)
212 size_t idx = hash_and_fit(value, hash_seeds[i]);
213 assert(idx < data.size());
233 sdsl::util::_set_zero_bits(data);
253 for (
size_t i = 0; i < hash_funs; i++)
255 size_t idx = hash_and_fit(value, hash_seeds[i]);
256 assert(idx < data.size());
282 template <std::ranges::range value_range_t>
283 size_t count(value_range_t && values)
const noexcept
285 static_assert(std::ranges::input_range<value_range_t>,
"The values must model input_range.");
286 static_assert(std::unsigned_integral<std::ranges::range_value_t<value_range_t>>,
287 "An individual value must be an unsigned integral.");
291 for (
auto && value : values)
328 return std::tie(lhs.size_in_bits, lhs.hash_shift, lhs.hash_funs, lhs.data)
329 ==
std::tie(rhs.size_in_bits, rhs.hash_shift, rhs.hash_funs, rhs.data);
339 return !(lhs == rhs);
372 template <cereal_archive archive_t>
373 void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
375 archive(size_in_bits);
The Bloom Filter. A data structure that efficiently answers set-membership queries.
Definition bloom_filter.hpp:85
friend bool operator!=(bloom_filter const &lhs, bloom_filter const &rhs) noexcept
Test for inequality.
Definition bloom_filter.hpp:337
constexpr data_type & raw_data() noexcept
Provides direct, unsafe access to the underlying data structure.
Definition bloom_filter.hpp:353
bloom_filter(bloom_filter &&)=default
Defaulted.
static constexpr data_layout data_layout_mode
Indicates whether the Bloom Filter is compressed.
Definition bloom_filter.hpp:134
constexpr data_type const & raw_data() const noexcept
Provides direct, unsafe access to the underlying data structure.
Definition bloom_filter.hpp:359
bloom_filter & operator=(bloom_filter const &)=default
Defaulted.
bool contains(size_t const value) const noexcept
Check whether a value is present in the Bloom Filter.
Definition bloom_filter.hpp:251
bloom_filter(bloom_filter< data_layout::uncompressed > const &bf)
Construct a compressed Bloom Filter.
Definition bloom_filter.hpp:184
friend bool operator==(bloom_filter const &lhs, bloom_filter const &rhs) noexcept
Test for equality.
Definition bloom_filter.hpp:326
void reset() noexcept
Remove all values from the Bloom Filter by setting all bits to 0.
Definition bloom_filter.hpp:230
bloom_filter(bloom_filter const &)=default
Defaulted.
size_t hash_function_count() const noexcept
Returns the number of hash functions used in the Bloom Filter.
Definition bloom_filter.hpp:304
size_t count(value_range_t &&values) const noexcept
Counts the occurrences for all values in a range.
Definition bloom_filter.hpp:283
bloom_filter()=default
Defaulted.
size_t bit_size() const noexcept
Returns the size of the underlying bitvector.
Definition bloom_filter.hpp:312
bloom_filter & operator=(bloom_filter &&)=default
Defaulted.
void emplace(size_t const value) noexcept
Inserts a value into the Bloom Filter.
Definition bloom_filter.hpp:207
~bloom_filter()=default
Defaulted.
bloom_filter(seqan3::bin_size size, seqan3::hash_function_count funs=seqan3::hash_function_count{2u})
Construct an uncompressed Bloom Filter.
Definition bloom_filter.hpp:158
data_layout
Determines if the Interleaved Bloom Filter is compressed.
Definition interleaved_bloom_filter.hpp:28
@ uncompressed
The Interleaved Bloom Filter is uncompressed.
Definition interleaved_bloom_filter.hpp:29
@ compressed
The Interleaved Bloom Filter is compressed.
Definition interleaved_bloom_filter.hpp:30
Provides seqan3::interleaved_bloom_filter.
The main SeqAn3 namespace.
Definition aligned_sequence_concept.hpp:29
A strong type that represents the number of bits for each bin in the seqan3::interleaved_bloom_filter...
Definition interleaved_bloom_filter.hpp:43
A strong type that represents the number of hash functions for the seqan3::interleaved_bloom_filter.
Definition interleaved_bloom_filter.hpp:50
strong_type for seed.
Definition minimiser_hash.hpp:25