merge.hpp

Go to the documentation of this file.

// 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_MERGE_ALGORITHM_H_INCLUDED__
#define __COALESCENCE_MERGE_ALGORITHM_H_INCLUDED__
 
#include <algorithm> // std::shuffle
#include <cassert>
#include <functional> // std::plus
#include <iostream>
#include <iterator>    // std::advance
#include <type_traits> // std::is_invocable
 
namespace quetzal
{
namespace coalescence
{
namespace algorithm
{
template <class BidirectionalIterator, class T, class BinaryOperation, class Generator>
BidirectionalIterator binary_merge(BidirectionalIterator first, BidirectionalIterator last, T init, BinaryOperation op,
                                   Generator &g)
{
    assert(std::distance(first, last) > 1 && "Coalescence should operate on a range containing more than one element.");
    std::shuffle(first, last, g);
    if constexpr (std::is_invocable<T>::value)
    {
        *first = op(init(), *first);
    }
    else
    {
        *first = op(init, *first);
    }
    *first = op(*first, *(--last));
    return last;
}
 
template <class BidirectionalIterator, class Generator>
BidirectionalIterator binary_merge(BidirectionalIterator first, BidirectionalIterator last, Generator &g)
{
    assert(std::distance(first, last) > 1 && "Coalescence should operate on a range containing more than one element.");
    using T = typename BidirectionalIterator::value_type;
    return binary_merge(first, last, T(), std::plus<T>(), g);
}
 
template <class BidirectionalIterator, class T, class BinaryOperation, class OccupancySpectrum, class Generator>
BidirectionalIterator simultaneous_multiple_merge(BidirectionalIterator first, BidirectionalIterator last, T init,
                                                  OccupancySpectrum const &sp, BinaryOperation op, Generator &g)
{
    assert(std::distance(first, last) > 1 && "Coalescence should operate on a range containing more than one element.");
    std::shuffle(first, last, g);
    // directly go to binary merge.
    auto m_it = sp.cbegin();
    std::advance(m_it, 2);
    int j = 2;
    while (m_it != sp.cend())
    {
        for (unsigned int i = 1; i <= *m_it; ++i)
        {
            // loop on the m_j parents
            if constexpr (std::is_invocable<T>::value)
            {
                *first = op(init(), *first);
            }
            else
            {
                *first = op(init, *first);
            }
            for (int k = 1; k < j; ++k)
            {
                // loop on the others children
                *first = op(*first, *(--last));
            }
            ++first;
        }
        ++j;
        ++m_it;
    }
    return last;
}
 
template <class BidirectionalIterator, class OccupancySpectrum, class Generator>
BidirectionalIterator simultaneous_multiple_merge(BidirectionalIterator first, BidirectionalIterator last,
                                                  OccupancySpectrum const &sp, Generator &g)
{
    assert(std::distance(first, last) > 1 && "Coalescence should operate on a range containing more than one element.");
    using T = typename BidirectionalIterator::value_type;
    return simultaneous_multiple_merge(first, last, T(), sp, std::plus<T>(), g);
}
} // namespace algorithm
} // end namespace coalescence
} // end namespace quetzal
 
#endif