toolbox.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 <cinttypes>  // for uint64_t, int64_t
#include <cstddef>    // for size_t
#include <functional> // for greater
#include <queue>      // for priority_queue
#include <vector>     // for vector
 
#include <hibf/contrib/robin_hood.hpp> // for unordered_flat_map
#include <hibf/sketch/hyperloglog.hpp> // for hyperloglog
 
namespace seqan::hibf::sketch::toolbox
{
 
struct clustering_node
{
    // children in the tree
    size_t left;
    size_t right;
    // hll sketch of the union if the node is still a root
    hyperloglog hll;
};
 
struct neighbor
{
    size_t id;
    double dist;
 
    bool operator>(neighbor const & other) const
    {
        return dist > other.dist;
    }
};
 
using prio_queue = std::priority_queue<neighbor, std::vector<neighbor>, std::greater<neighbor>>;
 
struct entry
{
    size_t id;
    prio_queue pq;
};
 
using distance_matrix = std::vector<entry>;
 
void sort_by_cardinalities(std::vector<size_t> const & counts, std::vector<size_t> & positions);
 
void precompute_union_estimates_for(std::vector<uint64_t> & estimates,
                                    std::vector<hyperloglog> const & sketches,
                                    std::vector<size_t> const & counts,
                                    std::vector<size_t> const & positions,
                                    int64_t const j);
 
void precompute_initial_union_estimates(std::vector<uint64_t> & estimates,
                                        std::vector<hyperloglog> const & sketches,
                                        std::vector<size_t> const & counts,
                                        std::vector<size_t> const & positions);
 
#if 0 // Currently unused
uint64_t estimate_interval(std::vector<hyperloglog> const & sketches, std::vector<size_t> const & positions);
#endif
 
void rearrange_bins(std::vector<hyperloglog> const & sketches,
                    std::vector<size_t> const & counts,
                    std::vector<size_t> & positions,
                    double const max_ratio,
                    size_t const num_threads);
 
void cluster_bins(std::vector<hyperloglog> const & sketches,
                  std::vector<size_t> & positions,
                  std::vector<size_t> & permutation,
                  size_t const first,
                  size_t const last,
                  size_t const num_threads);
 
void random_shuffle(distance_matrix & dist, robin_hood::unordered_flat_map<size_t, size_t> & remaining_ids);
 
void prune(distance_matrix & dist, robin_hood::unordered_flat_map<size_t, size_t> & remaining_ids);
 
bool rotate(std::vector<clustering_node> & clustering,
            size_t const previous_rightmost,
            size_t const first,
            size_t const id);
 
void trace(std::vector<clustering_node> const & clustering,
           std::vector<size_t> & permutation,
           size_t const previous_rightmost,
           size_t const first,
           size_t const id);
 
} // namespace seqan::hibf::sketch::toolbox