hierarchical_binning.hpp

// SPDX-FileCopyrightText: 2006-2024, Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2024, Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
 
#pragma once
 
#include <cassert> // for assert
#include <cstddef> // for size_t
#include <memory>  // for addressof
#include <utility> // for pair
#include <vector>  // for vector
 
#include <hibf/build/bin_size_in_bits.hpp> // for bin_size_in_bits
#include <hibf/config.hpp>                 // for config
#include <hibf/layout/data_store.hpp>      // for data_store
#include <hibf/misc/md_vector.hpp>
#include <hibf/platform.hpp> // for HIBF_WORKAROUND_GCC_BOGUS_MEMCPY
 
namespace seqan::hibf::layout
{
 
class hierarchical_binning
{
private:
    seqan::hibf::config config{};
    data_store * data{nullptr};
 
    size_t num_user_bins{};
    size_t num_technical_bins{};
 
    struct maximum_bin_tracker
    {
        size_t max_id{};         
        size_t max_size{};       
        size_t max_split_id{};   
        size_t max_split_size{}; 
 
        void update_max(size_t const new_id, size_t const new_size)
        {
            if (new_size > max_size)
            {
                max_id = new_id;
                max_size = new_size;
            }
        }
 
        void update_split_max(size_t const new_id, size_t const new_size)
        {
            if (new_size > max_split_size)
            {
                max_split_id = new_id;
                max_split_size = new_size;
            }
        }
 
        size_t choose_max_bin(seqan::hibf::config const & config)
        {
            if (max_id == max_split_id) // Overall max bin is a split bin.
                return max_id;
 
            // Split cardinality `max_split_size` already accounts for fpr correction.
            // The minimum size of the TBs of this IBF to ensure the maximum_false_positive_rate for split bins.
            size_t const minimum_bits{build::bin_size_in_bits({.fpr = config.maximum_fpr,
                                                               .hash_count = config.number_of_hash_functions,
                                                               .elements = max_split_size})};
 
            // The potential size of the TBs of this IBF given the allowed merged bin FPR.
            size_t const merged_bits{build::bin_size_in_bits({.fpr = config.relaxed_fpr, //
                                                              .hash_count = config.number_of_hash_functions,
                                                              .elements = max_size})};
 
            // If split and merged bits are the same, we prefer merged bins. Better for build parallelisation.
            if ((minimum_bits > merged_bits))
                return max_split_id;
 
            return max_id;
        }
    };
 
public:
    hierarchical_binning() = default;                                        
    hierarchical_binning(hierarchical_binning const &) = delete;             
    hierarchical_binning & operator=(hierarchical_binning const &) = delete; 
    hierarchical_binning(hierarchical_binning &&) = default;                 
    hierarchical_binning & operator=(hierarchical_binning &&) = default;     
    ~hierarchical_binning() = default;                                       
 
    hierarchical_binning(data_store & data_, seqan::hibf::config const & config_) :
        config{config_},
        data{std::addressof(data_)},
        num_user_bins{data->positions.size()},
        num_technical_bins{data->previous.empty() ? config.tmax : needed_technical_bins(num_user_bins)}
    {
        assert(data != nullptr);
    }
 
    size_t execute();
 
private:
    [[nodiscard]] size_t needed_technical_bins(size_t const requested_num_ub) const;
 
    [[nodiscard]] size_t max_merge_levels(size_t const num_ubs_in_merge) const;
 
    void initialization(md_vector<size_t> & matrix,
                        md_vector<size_t> & ll_matrix,
                        md_vector<std::pair<size_t, size_t>> & trace);
 
    void
    recursion(md_vector<size_t> & matrix, md_vector<size_t> & ll_matrix, md_vector<std::pair<size_t, size_t>> & trace);
 
    void backtrack_merged_bin(size_t trace_j,
                              size_t const next_j,
                              size_t const bin_id,
                              maximum_bin_tracker & max_tracker,
                              bool is_first_row = false);
 
    void backtrack_split_bin(size_t trace_j,
                             size_t const number_of_bins,
                             size_t const bin_id,
                             maximum_bin_tracker & max_tracker);
 
    size_t backtracking(md_vector<std::pair<size_t, size_t>> const & trace);
 
    data_store initialise_libf_data(size_t const trace_j) const;
 
    void process_merged_bin(data_store & libf_data, size_t const bin_id) const;
 
    void update_libf_data(data_store & libf_data, size_t const bin_id) const;
 
    size_t add_lower_level(data_store & libf_data) const;
};
 
} // namespace seqan::hibf::layout