hierarchical_binning.hpp

// SPDX-FileCopyrightText: 2006-2025, Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2025, Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: BSD-3-Clause
 
#pragma once
 
#include <cstddef> // for size_t
#include <memory>  // for addressof
#include <utility> // for pair
#include <vector>  // for vector
 
#include <hibf/config.hpp>                   // for config
#include <hibf/layout/data_store.hpp>        // for data_store
#include <hibf/misc/subtract_empty_bins.hpp> // for subtract_empty_bins
#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{}; 
 
        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;
            }
        }
    };
 
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() ? subtract_empty_bins(config.tmax, config.empty_bin_fraction)
                                                  : needed_technical_bins(num_user_bins)}
    {}
    hierarchical_binning(data_store & data_, seqan::hibf::config const & config_) : {…}
 
    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(std::vector<std::vector<size_t>> & matrix,
                        std::vector<std::vector<size_t>> & ll_matrix,
                        std::vector<std::vector<std::pair<size_t, size_t>>> & trace);
 
    void recursion(std::vector<std::vector<size_t>> & matrix,
                   std::vector<std::vector<size_t>> & ll_matrix,
                   std::vector<std::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(std::vector<std::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;
};
class hierarchical_binning {…};
 
} // namespace seqan::hibf::layout