hierarchical_interleaved_bloom_filter.hpp

// SPDX-FileCopyrightText: 2006-2026, Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2026, Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
 
#pragma once
 
#include <algorithm> // for __sort, fill, sort
#include <cassert>   // for assert
#include <cstddef>   // for size_t
#include <cstdint>   // for uint64_t, uint16_t, uint32_t
#include <limits>    // for numeric_limits
#include <memory>    // for addressof
#include <ranges>    // for forward_range, integral, range, range_value_t, unsigned_integral
#include <vector>    // for vector, operator==
 
#include <cereal/cereal.hpp>       // for make_nvp
#include <cereal/macros.hpp>       // for CEREAL_SERIALIZE_FUNCTION_NAME
#include <cereal/types/vector.hpp> // IWYU pragma: keep
 
#include <hibf/cereal/concepts.hpp>          // for cereal_archive
#include <hibf/config.hpp>                   // for config
#include <hibf/interleaved_bloom_filter.hpp> // for interleaved_bloom_filter
#include <hibf/layout/layout.hpp>            // for layout
#include <hibf/misc/counting_vector.hpp>     // for counting_vector
#include <hibf/misc/timer.hpp>               // for concurrent_timer
#include <hibf/platform.hpp>                 // for HIBF_CONSTEXPR_VECTOR
 
namespace seqan::hibf
{
 
namespace bin_kind
{
 
inline constexpr uint64_t merged{std::numeric_limits<uint64_t>::max()};
inline constexpr uint64_t deleted{std::numeric_limits<uint64_t>::max() - 1u};
 
} // namespace bin_kind
 
class hierarchical_interleaved_bloom_filter
{
public:
    size_t number_of_user_bins{};
 
    class membership_agent_type;
    template <std::integral value_t>
    class counting_agent_type;
    struct previous_ibf_id_pair;
 
    hierarchical_interleaved_bloom_filter() = default;                                              
    hierarchical_interleaved_bloom_filter(hierarchical_interleaved_bloom_filter const &) = default; 
    hierarchical_interleaved_bloom_filter &
    operator=(hierarchical_interleaved_bloom_filter const &) = default;                        
    hierarchical_interleaved_bloom_filter(hierarchical_interleaved_bloom_filter &&) = default; 
    hierarchical_interleaved_bloom_filter &
    operator=(hierarchical_interleaved_bloom_filter &&) = default; 
    ~hierarchical_interleaved_bloom_filter() = default;            
 
    hierarchical_interleaved_bloom_filter(config & configuration);
 
    hierarchical_interleaved_bloom_filter(config & configuration, layout::layout const & layout);
 
    std::vector<interleaved_bloom_filter> ibf_vector;
 
    std::vector<std::vector<uint64_t>> next_ibf_id;
 
    std::vector<previous_ibf_id_pair> prev_ibf_id;
 
    std::vector<std::vector<uint64_t>> ibf_bin_to_user_bin_id{};
 
    membership_agent_type membership_agent() const;
 
    template <std::integral value_t = uint16_t>
    counting_agent_type<value_t> counting_agent() const;
 
    constexpr bool operator==(hierarchical_interleaved_bloom_filter const &) const;
 
    static constexpr uint32_t version{1};
 
    template <seqan::hibf::cereal_archive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        uint32_t parsed_version{version};
        archive(cereal::make_nvp("version", parsed_version));
        archive(number_of_user_bins);
        archive(ibf_vector);
        archive(next_ibf_id);
        archive(prev_ibf_id);
        archive(ibf_bin_to_user_bin_id);
    }
 
    concurrent_timer layout_compute_sketches_timer{};
    concurrent_timer layout_union_estimation_timer{};
    concurrent_timer layout_rearrangement_timer{};
    concurrent_timer layout_dp_algorithm_timer{};
    concurrent_timer index_allocation_timer{};
    concurrent_timer user_bin_io_timer{};
    concurrent_timer merge_kmers_timer{};
    concurrent_timer fill_ibf_timer{};
};
 
struct hierarchical_interleaved_bloom_filter::previous_ibf_id_pair
{
    size_t ibf_idx{}; 
    size_t bin_idx{}; 
 
    friend constexpr auto operator<=>(previous_ibf_id_pair const &, previous_ibf_id_pair const &) = default;
 
    template <seqan::hibf::cereal_archive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        archive(ibf_idx);
        archive(bin_idx);
    }
};
 
constexpr bool
hierarchical_interleaved_bloom_filter::operator==(hierarchical_interleaved_bloom_filter const &) const = default;
 
class hierarchical_interleaved_bloom_filter::membership_agent_type
{
private:
    hierarchical_interleaved_bloom_filter const * hibf_ptr{nullptr};
 
    template <std::ranges::forward_range value_range_t>
    void membership_for_impl(value_range_t && values, size_t const ibf_idx, uint16_t const threshold)
    {
        auto agent = hibf_ptr->ibf_vector[ibf_idx].template counting_agent<uint16_t>();
        auto & result = agent.bulk_count(values);
 
        uint16_t sum{};
 
        for (size_t bin{}; bin < result.size(); ++bin)
        {
            sum += result[bin];
 
            auto const user_bin_id = hibf_ptr->ibf_bin_to_user_bin_id[ibf_idx][bin];
 
            // It does not seem to make a difference whether the following block is done via a switch or if-else.
            // The switch is easier to read.
            switch (user_bin_id)
            {
            case bin_kind::deleted: // GCOVR_EXCL_LINE
                break;              // GCOVR_EXCL_LINE
            case bin_kind::merged:
                if (sum >= threshold)
                    membership_for_impl(values, hibf_ptr->next_ibf_id[ibf_idx][bin], threshold);
                sum = 0u;
                break;
            default:
                if (bin + 1u == result.size() || user_bin_id != hibf_ptr->ibf_bin_to_user_bin_id[ibf_idx][bin + 1])
                { //  last bin || end of split bin
                    if (sum >= threshold)
                        result_buffer.emplace_back(user_bin_id);
                    sum = 0u;
                }
            }
        }
    }
 
    std::vector<uint64_t> result_buffer;
 
public:
    membership_agent_type() = default;                                          
    membership_agent_type(membership_agent_type const &) = default;             
    membership_agent_type & operator=(membership_agent_type const &) = default; 
    membership_agent_type(membership_agent_type &&) = default;                  
    membership_agent_type & operator=(membership_agent_type &&) = default;      
    ~membership_agent_type() = default;                                         
 
    explicit membership_agent_type(hierarchical_interleaved_bloom_filter const & hibf) : hibf_ptr(std::addressof(hibf))
    {}
 
    void sort_results()
    {
        std::ranges::sort(result_buffer);
    }
 
    template <std::ranges::forward_range value_range_t>
    [[nodiscard]] std::vector<uint64_t> const & membership_for(value_range_t && values,
                                                               uint16_t const threshold) & noexcept
    {
        assert(hibf_ptr != nullptr);
 
        static_assert(std::ranges::forward_range<value_range_t>, "The values must model forward_range.");
        static_assert(std::unsigned_integral<std::ranges::range_value_t<value_range_t>>,
                      "An individual value must be an unsigned integral.");
 
        result_buffer.clear();
 
        membership_for_impl(values, 0u, threshold);
 
        return result_buffer;
    }
 
    template <std::ranges::range value_range_t>
    [[nodiscard]] std::vector<uint64_t> const & membership_for(value_range_t && values,
                                                               uint16_t const threshold) && noexcept = delete;
};
 
inline hierarchical_interleaved_bloom_filter::membership_agent_type
hierarchical_interleaved_bloom_filter::membership_agent() const
{
    return typename hierarchical_interleaved_bloom_filter::membership_agent_type{*this};
}
 
template <std::integral value_t>
class hierarchical_interleaved_bloom_filter::counting_agent_type
{
private:
    hierarchical_interleaved_bloom_filter const * hibf_ptr{nullptr};
 
    template <std::ranges::forward_range value_range_t>
    void bulk_count_impl(value_range_t && values, size_t const ibf_idx, size_t const threshold)
    {
        auto agent = hibf_ptr->ibf_vector[ibf_idx].template counting_agent<value_t>();
        auto & result = agent.bulk_count(values);
 
        value_t sum{};
 
        for (size_t bin{}; bin < result.size(); ++bin)
        {
            sum += result[bin];
 
            auto const user_bin_id = hibf_ptr->ibf_bin_to_user_bin_id[ibf_idx][bin];
 
            // It does not seem to make a difference whether the following block is done via a switch or if-else.
            // The switch is easier to read.
            switch (user_bin_id)
            {
            case bin_kind::deleted: // GCOVR_EXCL_LINE
                break;              // GCOVR_EXCL_LINE
            case bin_kind::merged:
                if (sum >= threshold)
                    bulk_count_impl(values, hibf_ptr->next_ibf_id[ibf_idx][bin], threshold);
                sum = 0u;
                break;
            default:
                if (bin + 1u == result.size() || user_bin_id != hibf_ptr->ibf_bin_to_user_bin_id[ibf_idx][bin + 1])
                { //  last bin || end of split bin
                    if (sum >= threshold)
                        result_buffer[user_bin_id] = sum;
                    sum = 0u;
                }
            }
        }
    }
 
    counting_vector<value_t> result_buffer;
 
public:
    counting_agent_type() = default;                                        
    counting_agent_type(counting_agent_type const &) = default;             
    counting_agent_type & operator=(counting_agent_type const &) = default; 
    counting_agent_type(counting_agent_type &&) = default;                  
    counting_agent_type & operator=(counting_agent_type &&) = default;      
    ~counting_agent_type() = default;                                       
 
    explicit counting_agent_type(hierarchical_interleaved_bloom_filter const & hibf) :
        hibf_ptr(std::addressof(hibf)),
        result_buffer(hibf_ptr->number_of_user_bins)
    {}
 
    template <std::ranges::forward_range value_range_t>
    [[nodiscard]] counting_vector<value_t> const & bulk_count(value_range_t && values,
                                                              size_t const threshold) & noexcept
    {
        assert(hibf_ptr != nullptr);
        assert(threshold > 0u);
        assert(result_buffer.size() == hibf_ptr->number_of_user_bins);
 
        static_assert(std::ranges::forward_range<value_range_t>, "The values must model forward_range.");
        static_assert(std::unsigned_integral<std::ranges::range_value_t<value_range_t>>,
                      "An individual value must be an unsigned integral.");
 
        std::ranges::fill(result_buffer, static_cast<value_t>(0));
 
        bulk_count_impl(values, 0u, threshold);
 
        return result_buffer;
    }
 
    template <std::ranges::range value_range_t>
    [[nodiscard]] counting_vector<value_t> const & bulk_count(value_range_t && values,
                                                              size_t const threshold) && noexcept = delete;
};
 
template <std::integral value_t>
inline hierarchical_interleaved_bloom_filter::counting_agent_type<value_t>
hierarchical_interleaved_bloom_filter::counting_agent() const
{
    return typename hierarchical_interleaved_bloom_filter::counting_agent_type<value_t>{*this};
}
 
} // namespace seqan::hibf