merger_policy.hpp

// Copyright 2021 Arnaud Becheler    <abechele@umich.edu>
 
/*********************************************************************** * This program is free software; you can
 *redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free
 *Software Foundation; either version 2 of the License, or    * (at your option) any later version. *
 *                                                                      *
 ***************************************************************************/
 
#ifndef __COALESCENCE_MERGERS_H_INCLUDED__
#define __COALESCENCE_MERGERS_H_INCLUDED__
 
#include "algorithm/merge.hpp"
 
#include <cassert>
#include <functional> // std::plus
#include <iterator>   // std::distance
#include <random>     // bernoulli_distribution
 
namespace quetzal
{
namespace coalescence
{
namespace merger_policy
{
struct BinaryMerger
{
    template <class BidirectionalIterator, class T, class BinaryOperation, class Generator>
    static auto merge(BidirectionalIterator first, BidirectionalIterator last, unsigned int N, T init,
                      BinaryOperation const &op, Generator &g)
    {
        assert(N >= 1 && "Population size should be more than 1 for evaluating coalescence probability");
        assert(std::distance(first, last) > 1 &&
               "Coalescence should operate on a range containing more than one element.");
        double k = static_cast<double>(std::distance(first, last));
        double coal_proba = (k * (k - 1.0)) / static_cast<double>(2 * N);
        std::bernoulli_distribution d(coal_proba);
        if (d(g))
        {
            last = algorithm::binary_merge(first, last, init, op, g);
        }
        return last;
    }
    template <class BidirectionalIterator, class Generator>
    static auto merge(BidirectionalIterator first, BidirectionalIterator last, unsigned int N, Generator &g)
    {
        assert(N >= 1 && "Population size should be positive for evaluating coalescence probability");
        assert(std::distance(first, last) > 1 &&
               "Coalescence should operate on a range containing more than one element.");
        using T = typename BidirectionalIterator::value_type;
        return merge(first, last, N, T(), std::plus<T>(), g);
    }
};
template <class SpectrumSamplingPolicy> struct SimultaneousMultipleMerger
{
    template <class BidirectionalIterator, class T, class BinaryOperation, class Generator>
    static auto merge(BidirectionalIterator first, BidirectionalIterator last, unsigned int N, T const &init,
                      BinaryOperation const &op, Generator &g)
    {
        assert(N >= 1 && "Population size should be positive for evaluating coalescence probability");
        assert(std::distance(first, last) > 1 &&
               "Coalescence should operate on a range containing more than one element.");
        unsigned int k = std::distance(first, last);
        return algorithm::simultaneous_multiple_merge(first, last, init, SpectrumSamplingPolicy::sample(k, N, g), op,
                                                      g);
    }
    template <class BidirectionalIterator, class Generator>
    static auto merge(BidirectionalIterator first, BidirectionalIterator last, unsigned int N, Generator &g)
    {
        assert(N >= 1 && "Population size should be positive for evaluating coalescence probability");
        assert(std::distance(first, last) > 1 &&
               "Coalescence should operate on a range containing more than one element.");
        unsigned int k = std::distance(first, last);
        return algorithm::simultaneous_multiple_merge(first, last, SpectrumSamplingPolicy::sample(k, N, g), g);
    }
}; // end class SimultaneousMultipleMerger
} // end namespace merger_policy
} // end namespace coalescence
} // end namespace quetzal
 
#endif