bloom_filter.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2006-2022, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2022, Knut Reinert & MPI für molekulare Genetik
// This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
// shipped with this file and also available at: https://github.com/seqan/seqan3/blob/master/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <seqan3/search/dream_index/interleaved_bloom_filter.hpp>
 
namespace seqan3
{
 
template <data_layout data_layout_mode_ = data_layout::uncompressed>
class bloom_filter
{
private:
    template <data_layout data_layout_mode>
    friend class bloom_filter;
 
    using data_type =
        std::conditional_t<data_layout_mode_ == data_layout::uncompressed, sdsl::bit_vector, sdsl::sd_vector<>>;
 
    size_t size_in_bits{};
    size_t hash_shift{};
    size_t hash_funs{};
    data_type data{};
    static constexpr std::array<size_t, 5> hash_seeds{13572355802537770549ULL, // 2**64 / (e/2)
                                                      13043817825332782213ULL, // 2**64 / sqrt(2)
                                                      10650232656628343401ULL, // 2**64 / sqrt(3)
                                                      16499269484942379435ULL, // 2**64 / (sqrt(5)/2)
                                                      4893150838803335377ULL}; // 2**64 / (3*pi/5)
 
    inline constexpr size_t hash_and_fit(size_t h, size_t const seed) const
    {
        h *= seed;
        h ^= h >> hash_shift;         // XOR and shift higher bits into lower bits
        h *= 11400714819323198485ULL; // = 2^64 / golden_ration, to expand h to 64 bit range
                                      // Use fastrange (integer modulo without division) if possible.
#ifdef __SIZEOF_INT128__
        h = static_cast<uint64_t>((static_cast<__uint128_t>(h) * static_cast<__uint128_t>(size_in_bits)) >> 64);
#else
        h %= size_in_bits;
#endif
        return h;
    }
 
public:
    static constexpr data_layout data_layout_mode = data_layout_mode_;
 
    bloom_filter() = default;                                 
    bloom_filter(bloom_filter const &) = default;             
    bloom_filter & operator=(bloom_filter const &) = default; 
    bloom_filter(bloom_filter &&) = default;                  
    bloom_filter & operator=(bloom_filter &&) = default;      
    ~bloom_filter() = default;                                
 
    bloom_filter(seqan3::bin_size size, seqan3::hash_function_count funs = seqan3::hash_function_count{2u})
        requires (data_layout_mode == data_layout::uncompressed)
    {
        size_in_bits = size.get();
        hash_funs = funs.get();
 
        if (hash_funs == 0 || hash_funs > 5)
            throw std::logic_error{"The number of hash functions must be > 0 and <= 5."};
        if (size_in_bits == 0)
            throw std::logic_error{"The size of a bloom filter must be > 0."};
 
        hash_shift = std::countl_zero(size_in_bits);
        data = sdsl::bit_vector(size_in_bits);
    }
 
    bloom_filter(bloom_filter<data_layout::uncompressed> const & bf)
        requires (data_layout_mode == data_layout::compressed)
    {
        std::tie(size_in_bits, hash_shift, hash_funs) = std::tie(bf.size_in_bits, bf.hash_shift, bf.hash_funs);
 
        data = sdsl::sd_vector<>{bf.data};
    }
 
    void emplace(size_t const value) noexcept
        requires (data_layout_mode == data_layout::uncompressed)
    {
        for (size_t i = 0; i < hash_funs; ++i)
        {
            size_t idx = hash_and_fit(value, hash_seeds[i]);
            assert(idx < data.size());
            data[idx] = 1;
        };
    }
 
    void reset() noexcept
        requires (data_layout_mode == data_layout::uncompressed)
    {
        sdsl::util::_set_zero_bits(data);
    }
 
    bool contains(size_t const value) const noexcept
    {
        for (size_t i = 0; i < hash_funs; i++)
        {
            size_t idx = hash_and_fit(value, hash_seeds[i]);
            assert(idx < data.size());
            if (data[idx] == 0)
                return false;
        }
        return true;
    }
 
    template <std::ranges::range value_range_t>
    size_t count(value_range_t && values) const noexcept
    {
        static_assert(std::ranges::input_range<value_range_t>, "The values must model input_range.");
        static_assert(std::unsigned_integral<std::ranges::range_value_t<value_range_t>>,
                      "An individual value must be an unsigned integral.");
 
        size_t result = 0;
 
        for (auto && value : values)
            result += contains(value);
 
        return result;
    }
 
    size_t hash_function_count() const noexcept
    {
        return hash_funs;
    }
 
    size_t bit_size() const noexcept
    {
        return size_in_bits;
    }
 
    friend bool operator==(bloom_filter const & lhs, bloom_filter const & rhs) noexcept
    {
        return std::tie(lhs.size_in_bits, lhs.hash_shift, lhs.hash_funs, lhs.data)
            == std::tie(rhs.size_in_bits, rhs.hash_shift, rhs.hash_funs, rhs.data);
    }
 
    friend bool operator!=(bloom_filter const & lhs, bloom_filter const & rhs) noexcept
    {
        return !(lhs == rhs);
    }
 
    constexpr data_type & raw_data() noexcept
    {
        return data;
    }
 
    constexpr data_type const & raw_data() const noexcept
    {
        return data;
    }
 
    template <cereal_archive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        archive(size_in_bits);
        archive(hash_shift);
        archive(hash_funs);
        archive(data);
    }
};
 
} // namespace seqan3