hierarchical_interleaved_bloom_filter.hpp

Go to the documentation of this file.

// --------------------------------------------------------------------------------------------------
// Copyright (c) 2006-2023, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2023, 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/raptor/blob/main/LICENSE.md
// --------------------------------------------------------------------------------------------------

 
#pragma once
 
#include <ranges>
 
#include <seqan3/search/dream_index/interleaved_bloom_filter.hpp>
 
#ifndef RAPTOR_HIBF_HAS_COUNT
#    define RAPTOR_HIBF_HAS_COUNT 0
#endif
 
namespace raptor
{

template <seqan3::data_layout data_layout_mode_ = seqan3::data_layout::uncompressed>
class hierarchical_interleaved_bloom_filter
{
public:
    // Forward declaration
    class user_bins;
 
    // Forward declaration
    class membership_agent_type;
 
#if RAPTOR_HIBF_HAS_COUNT
    // Forward declaration
    template <std::integral value_t>
    class counting_agent_type;
#endif

    static constexpr seqan3::data_layout data_layout_mode = data_layout_mode_;

    using ibf_t = seqan3::interleaved_bloom_filter<data_layout_mode_>;

    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;            


    std::vector<ibf_t> ibf_vector;

    std::vector<std::vector<int64_t>> next_ibf_id;

    user_bins user_bins;

    membership_agent_type membership_agent() const
    {
        return typename hierarchical_interleaved_bloom_filter<data_layout_mode>::membership_agent_type{*this};
    }
 
#if RAPTOR_HIBF_HAS_COUNT
    template <std::integral value_t = uint16_t>
    counting_agent_type<value_t> counting_agent() const
    {
        return counting_agent_type<value_t>{*this};
    }
#endif

    template <seqan3::cereal_archive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        archive(ibf_vector);
        archive(next_ibf_id);
        archive(user_bins);
    }

};

template <seqan3::data_layout data_layout_mode>
class hierarchical_interleaved_bloom_filter<data_layout_mode>::user_bins
{
private:
    std::vector<std::string> user_bin_filenames;

    std::vector<std::vector<int64_t>> ibf_bin_to_filename_position{};
 
public:
    size_t num_user_bins() const noexcept
    {
        return user_bin_filenames.size();
    }

    void set_ibf_count(size_t const size)
    {
        ibf_bin_to_filename_position.resize(size);
    }

    void set_user_bin_count(size_t const size)
    {
        user_bin_filenames.resize(size);
    }

    std::vector<int64_t> & bin_indices_of_ibf(size_t const idx)
    {
        return ibf_bin_to_filename_position[idx];
    }

    std::string & filename_of_user_bin(size_t const idx)
    {
        return user_bin_filenames[idx];
    }

    std::string const & operator[](std::pair<size_t, size_t> const & index_pair) const
    {
        return user_bin_filenames[ibf_bin_to_filename_position[index_pair.first][index_pair.second]];
    }

    auto operator[](size_t const ibf_idx) const
    {
        return ibf_bin_to_filename_position[ibf_idx]
             | std::views::transform(
                   [this](int64_t i)
                   {
                       if (i == -1)
                           return std::string{};
                       else
                           return user_bin_filenames[i];
                   });
    }

    int64_t filename_index(size_t const ibf_idx, size_t const bin_idx) const
    {
        return ibf_bin_to_filename_position[ibf_idx][bin_idx];
    }

    template <typename stream_t>
    void write_filenames(stream_t & out_stream) const
    {
        size_t position{};
        std::string line{};
        for (auto const & filename : user_bin_filenames)
        {
            line.clear();
            line = '#';
            line += std::to_string(position);
            line += '\t';
            line += filename;
            line += '\n';
            out_stream << line;
            ++position;
        }
    }

    template <typename archive_t>
    void serialize(archive_t & archive)
    {
        archive(user_bin_filenames);
        archive(ibf_bin_to_filename_position);
    }
};

template <seqan3::data_layout data_layout_mode> // TODO: value_t as template?
class hierarchical_interleaved_bloom_filter<data_layout_mode>::membership_agent_type
{
private:
    using hibf_t = hierarchical_interleaved_bloom_filter<data_layout_mode>;

    hibf_t const * const hibf_ptr{nullptr};

    template <std::ranges::forward_range value_range_t>
    void bulk_contains_impl(value_range_t && values, int64_t const ibf_idx, size_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 current_filename_index = hibf_ptr->user_bins.filename_index(ibf_idx, bin);
 
            if (current_filename_index < 0) // merged bin
            {
                if (sum >= threshold)
                    bulk_contains_impl(values, hibf_ptr->next_ibf_id[ibf_idx][bin], threshold);
                sum = 0u;
            }
            else if (bin + 1u == result.size() ||                                                    // last bin
                     current_filename_index != hibf_ptr->user_bins.filename_index(ibf_idx, bin + 1)) // end of split bin
            {
                if (sum >= threshold)
                    result_buffer.emplace_back(current_filename_index);
                sum = 0u;
            }
        }
    }
 
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(hibf_t const & hibf) : hibf_ptr(std::addressof(hibf))
    {}

    std::vector<int64_t> result_buffer;

    template <std::ranges::forward_range value_range_t>
    [[nodiscard]] std::vector<int64_t> const & bulk_contains(value_range_t && values, size_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();
 
        bulk_contains_impl(values, 0, threshold);
 
        std::ranges::sort(result_buffer); // TODO: necessary?
 
        return result_buffer;
    }
 
    // `bulk_contains` cannot be called on a temporary, since the object the returned reference points to
    // is immediately destroyed.
    template <std::ranges::range value_range_t>
    [[nodiscard]] std::vector<int64_t> const & bulk_contains(value_range_t && values,
                                                             size_t const threshold) && noexcept = delete;
};
 
#if RAPTOR_HIBF_HAS_COUNT
template <seqan3::data_layout data_layout_mode>
template <std::integral value_t>
class hierarchical_interleaved_bloom_filter<data_layout_mode>::counting_agent_type
{
private:
    using hibf_t = hierarchical_interleaved_bloom_filter<data_layout_mode>;

    hibf_t const * const hibf_ptr{nullptr};

    template <std::ranges::forward_range value_range_t>
    void bulk_count_impl(value_range_t && values, int64_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 current_filename_index = hibf_ptr->user_bins.filename_index(ibf_idx, bin);
 
            if (current_filename_index < 0) // merged bin
            {
                if (sum >= threshold)
                    bulk_count_impl(values, hibf_ptr->next_ibf_id[ibf_idx][bin], threshold);
                sum = 0u;
            }
            else if (bin + 1u == result.size() ||                                                    // last bin
                     current_filename_index != hibf_ptr->user_bins.filename_index(ibf_idx, bin + 1)) // end of split bin
            {
                if (sum >= threshold)
                    result_buffer[current_filename_index] = sum;
                sum = 0u;
            }
        }
    }
 
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(hibf_t const & hibf) :
        hibf_ptr(std::addressof(hibf)),
        result_buffer(hibf_ptr->user_bins.num_user_bins())
    {}

    seqan3::counting_vector<value_t> result_buffer;

    template <std::ranges::forward_range value_range_t>
    [[nodiscard]] seqan3::counting_vector<value_t> const & bulk_count(value_range_t && values,
                                                                      size_t const threshold = 1u) & noexcept
    {
        assert(hibf_ptr != nullptr);
        assert(threshold > 0u);
        assert(result_buffer.size() == hibf_ptr->user_bins.num_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>(0u));
 
        bulk_count_impl(values, 0, threshold);
 
        return result_buffer;
    }
 
    // `bulk_count` cannot be called on a temporary, since the object the returned reference points to
    // is immediately destroyed.
    template <std::ranges::range value_range_t>
    [[nodiscard]] seqan3::counting_vector<value_t> const & bulk_count(value_range_t && values,
                                                                      size_t const threshold = 1u) && noexcept = delete;
};
#endif // RAPTOR_HIBF_HAS_COUNT
 
} // namespace raptor