robot/include/boost/sort/common/merge_vector.hpp

//----------------------------------------------------------------------------
/// @file merge_vector.hpp
/// @brief In this file have the functions for to do a stable merge of
//         ranges, in a vector
///
/// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
///         Distributed under the Boost Software License, Version 1.0.\n
///         ( See accompanying file LICENSE_1_0.txt or copy at
///           http://www.boost.org/LICENSE_1_0.txt  )
/// @version 0.1
///
/// @remarks
//-----------------------------------------------------------------------------
#ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_VECTOR_HPP
#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_VECTOR_HPP


#include <ciso646>
#include <functional>
#include <iterator>
#include <memory>
#include <type_traits>
#include <vector>
#include <boost/sort/common/merge_four.hpp>

namespace boost
{
namespace sort
{
namespace common
{

//############################################################################
//                                                                          ##
//                       F U S I O N     O F                                ##
//                                                                          ##
//              A  V E C T O R   O F    R A N G E S                         ##
//                                                                          ##
//############################################################################

//
//-----------------------------------------------------------------------------
//  function : merge_level4
/// @brief merge the ranges in the vector v_input with the full_merge4 function.
///        The v_output vector is used as auxiliary memory in the internal
///        process. The final results is in the dest range.
///        All the ranges of v_output are inside the range dest
/// @param dest : range where move the elements merged
/// @param v_input : vector of ranges to merge
/// @param v_output : vector of ranges obtained
/// @param comp : comparison object
/// @return range with all the elements moved
//-----------------------------------------------------------------------------
template<class Iter1_t, class Iter2_t, class Compare>
void merge_level4(range<Iter1_t> dest, std::vector<range<Iter2_t> > &v_input,
                  std::vector<range<Iter1_t> > &v_output, Compare comp)
{
    typedef range<Iter1_t> range1_t;
    typedef util::value_iter<Iter1_t> type1;
    typedef util::value_iter<Iter2_t> type2;
    static_assert (std::is_same< type1, type2 >::value,
                    "Incompatible iterators\n");

    v_output.clear();
    if (v_input.size() == 0) return;
    if (v_input.size() == 1)
    {
        v_output.emplace_back(move_forward(dest, v_input[0]));
        return;
    };

    uint32_t nrange = v_input.size();
    uint32_t pos_ini = 0;
    while (pos_ini < v_input.size())
    {
        uint32_t nmerge = (nrange + 3) >> 2;
        uint32_t nelem = (nrange + nmerge - 1) / nmerge;
        range1_t rz = full_merge4(dest, &v_input[pos_ini], nelem, comp);
        v_output.emplace_back(rz);
        dest.first = rz.last;
        pos_ini += nelem;
        nrange -= nelem;
    };
    return;
};
//
//-----------------------------------------------------------------------------
//  function : uninit_merge_level4
/// @brief merge the ranges moving the objects and constructing them in
///        uninitialized memory, in the vector v_input
///        using full_merge4. The v_output vector is used as auxiliary memory
///        in the internal process. The final results is in the dest range.
///        All the ranges of v_output are inside the range dest
///
/// @param dest : range where move the elements merged
/// @param v_input : vector of ranges to merge
/// @param v_output : vector of ranges obtained
/// @param comp : comparison object
/// @return range with all the elements moved and constructed
//-----------------------------------------------------------------------------
template<class Value_t, class Iter_t, class Compare>
void uninit_merge_level4(range<Value_t *> dest,
                         std::vector<range<Iter_t> > &v_input,
                         std::vector <range<Value_t *> > &v_output, Compare comp)
{
    typedef range<Value_t *> range1_t;
    typedef util::value_iter<Iter_t> type1;
    static_assert (std::is_same< type1, Value_t >::value,
                    "Incompatible iterators\n");

    v_output.clear();
    if (v_input.size() == 0) return;
    if (v_input.size() == 1)
    {
        v_output.emplace_back(move_construct(dest, v_input[0]));
        return;
    };

    uint32_t nrange = v_input.size();
    uint32_t pos_ini = 0;
    while (pos_ini < v_input.size())
    {
        uint32_t nmerge = (nrange + 3) >> 2;
        uint32_t nelem = (nrange + nmerge - 1) / nmerge;
        range1_t rz = uninit_full_merge4(dest, &v_input[pos_ini], nelem, comp);
        v_output.emplace_back(rz);
        dest.first = rz.last;
        pos_ini += nelem;
        nrange -= nelem;
    };
    return;
};
//
//-----------------------------------------------------------------------------
//  function : merge_vector4
/// @brief merge the ranges in the vector v_input using the merge_level4
///        function. The v_output vector is used as auxiliary memory in the
///        internal process
///        The final results is in the range_output range.
///        All the ranges of v_output are inside the range range_output
///        All the ranges of v_input are inside the range range_input
/// @param range_input : range including all the ranges of v_input
/// @param ange_output : range including all the elements of v_output
/// @param v_input : vector of ranges to merge
/// @param v_output : vector of ranges obtained
/// @param comp : comparison object
/// @return range with all the elements moved
//-----------------------------------------------------------------------------
template<class Iter1_t, class Iter2_t, class Compare>
range<Iter2_t> merge_vector4(range<Iter1_t> range_input,
                             range<Iter2_t> range_output,
                             std::vector<range<Iter1_t> > &v_input,
                             std::vector<range<Iter2_t> > &v_output,
                             Compare comp)
{
    typedef range<Iter2_t> range2_t;
    typedef util::value_iter<Iter1_t> type1;
    typedef util::value_iter<Iter2_t> type2;
    static_assert (std::is_same< type1, type2 >::value,
                    "Incompatible iterators\n");

    v_output.clear();
    if (v_input.size() == 0)
    {
        return range2_t(range_output.first, range_output.first);
    };
    if (v_input.size() == 1)
    {
        return move_forward(range_output, v_input[0]);
    };
    bool sw = false;
    uint32_t nrange = v_input.size();

    while (nrange > 1)
    {
        if (sw)
        {
            merge_level4(range_input, v_output, v_input, comp);
            sw = false;
            nrange = v_input.size();
        }
        else
        {
            merge_level4(range_output, v_input, v_output, comp);
            sw = true;
            nrange = v_output.size();
        };
    };
    return (sw) ? v_output[0] : move_forward(range_output, v_input[0]);
};

//****************************************************************************
};//    End namespace common
};//    End namespace sort
};//    End namespace boost
//****************************************************************************
//
#endif