Loading...
Searching...
No Matches
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
std::addressof
T addressof(T... args)
std::string
raptor::hierarchical_interleaved_bloom_filter::counting_agent_type
Manages counting ranges of values for the raptor::hierarchical_interleaved_bloom_filter.
Definition hierarchical_interleaved_bloom_filter.hpp:421
raptor::hierarchical_interleaved_bloom_filter::membership_agent_type
Manages membership queries for the raptor::hierarchical_interleaved_bloom_filter.
Definition hierarchical_interleaved_bloom_filter.hpp:311
raptor::hierarchical_interleaved_bloom_filter::membership_agent_type::hibf_t
hierarchical_interleaved_bloom_filter< data_layout_mode > hibf_t
The type of the augmented hierarchical_interleaved_bloom_filter.
Definition hierarchical_interleaved_bloom_filter.hpp:314
raptor::hierarchical_interleaved_bloom_filter::user_bins
Bookkeeping for user and technical bins.
Definition hierarchical_interleaved_bloom_filter.hpp:176
raptor::hierarchical_interleaved_bloom_filter::counting_agent
counting_agent_type< value_t > counting_agent() const
Returns a counting_agent_type to be used for counting.
Definition hierarchical_interleaved_bloom_filter.hpp:148
raptor::hierarchical_interleaved_bloom_filter::hierarchical_interleaved_bloom_filter
hierarchical_interleaved_bloom_filter(hierarchical_interleaved_bloom_filter const &)=default
Defaulted.
raptor::hierarchical_interleaved_bloom_filter::~hierarchical_interleaved_bloom_filter
~hierarchical_interleaved_bloom_filter()=default
Defaulted.
raptor::hierarchical_interleaved_bloom_filter::membership_agent
membership_agent_type membership_agent() const
Returns a membership_agent to be used for counting.
Definition hierarchical_interleaved_bloom_filter.hpp:138
raptor::hierarchical_interleaved_bloom_filter< data_layout_mode >::ibf_vector
std::vector< ibf_t > ibf_vector
Definition hierarchical_interleaved_bloom_filter.hpp:123
raptor::hierarchical_interleaved_bloom_filter::operator=
hierarchical_interleaved_bloom_filter & operator=(hierarchical_interleaved_bloom_filter const &)=default
Defaulted.
raptor::hierarchical_interleaved_bloom_filter< data_layout_mode >::data_layout_mode
static constexpr seqan3::data_layout data_layout_mode
Definition hierarchical_interleaved_bloom_filter.hpp:103
raptor::hierarchical_interleaved_bloom_filter::serialize
void serialize(archive_t &archive)
Serialisation support function.
Definition hierarchical_interleaved_bloom_filter.hpp:163
raptor::hierarchical_interleaved_bloom_filter::operator=
hierarchical_interleaved_bloom_filter & operator=(hierarchical_interleaved_bloom_filter &&)=default
Defaulted.
raptor::hierarchical_interleaved_bloom_filter< data_layout_mode >::next_ibf_id
std::vector< std::vector< int64_t > > next_ibf_id
Definition hierarchical_interleaved_bloom_filter.hpp:132
raptor::hierarchical_interleaved_bloom_filter::hierarchical_interleaved_bloom_filter
hierarchical_interleaved_bloom_filter(hierarchical_interleaved_bloom_filter &&)=default
Defaulted.
raptor::hierarchical_interleaved_bloom_filter::ibf_t
seqan3::interleaved_bloom_filter< data_layout_mode_ > ibf_t
The type of an individual Bloom filter.
Definition hierarchical_interleaved_bloom_filter.hpp:106
raptor::hierarchical_interleaved_bloom_filter::hierarchical_interleaved_bloom_filter
hierarchical_interleaved_bloom_filter()=default
Defaulted.
raptor::hierarchical_interleaved_bloom_filter::user_bins
user_bins user_bins
The underlying user bins.
Definition hierarchical_interleaved_bloom_filter.hpp:135
std::string::clear
T clear(T... args)
raptor::hibf
Must be first include.
Definition bin_size_in_bits.hpp:18
std::pair
std::vector::resize
T resize(T... args)
std::vector::size
T size(T... args)
std::to_string
T to_string(T... args)
std::vector