sort/common/merge_vector.hpp

0001 //----------------------------------------------------------------------------
0002 /// @file merge_vector.hpp
0003 /// @brief In this file have the functions for to do a stable merge of
0004 //         ranges, in a vector
0005 ///
0006 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
0007 ///         Distributed under the Boost Software License, Version 1.0.\n
0008 ///         ( See accompanying file LICENSE_1_0.txt or copy at
0009 ///           http://www.boost.org/LICENSE_1_0.txt  )
0010 /// @version 0.1
0011 ///
0012 /// @remarks
0013 //-----------------------------------------------------------------------------
0014 #ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_VECTOR_HPP
0015 #define __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_VECTOR_HPP
0016
0017
0018 #include <ciso646>
0019 #include <functional>
0020 #include <iterator>
0021 #include <memory>
0022 #include <type_traits>
0023 #include <vector>
0024 #include <boost/sort/common/merge_four.hpp>
0025
0026 namespace boost
0027 {
0028 namespace sort
0029 {
0030 namespace common
0031 {
0032
0033 //############################################################################
0034 //                                                                          ##
0035 //                       F U S I O N     O F                                ##
0036 //                                                                          ##
0037 //              A  V E C T O R   O F    R A N G E S                         ##
0038 //                                                                          ##
0039 //############################################################################
0040
0041 //
0042 //-----------------------------------------------------------------------------
0043 //  function : merge_level4
0044 /// @brief merge the ranges in the vector v_input with the full_merge4 function.
0045 ///        The v_output vector is used as auxiliary memory in the internal
0046 ///        process. The final results is in the dest range.
0047 ///        All the ranges of v_output are inside the range dest
0048 /// @param dest : range where move the elements merged
0049 /// @param v_input : vector of ranges to merge
0050 /// @param v_output : vector of ranges obtained
0051 /// @param comp : comparison object
0052 /// @return range with all the elements moved
0053 //-----------------------------------------------------------------------------
0054 template<class Iter1_t, class Iter2_t, class Compare>
0055 void merge_level4(range<Iter1_t> dest, std::vector<range<Iter2_t> > &v_input,
0056                   std::vector<range<Iter1_t> > &v_output, Compare comp)
0057 {
0058     typedef range<Iter1_t> range1_t;
0059     typedef util::value_iter<Iter1_t> type1;
0060     typedef util::value_iter<Iter2_t> type2;
0061     static_assert (std::is_same< type1, type2 >::value,
0062                     "Incompatible iterators\n");
0063
0064     v_output.clear();
0065     if (v_input.size() == 0) return;
0066     if (v_input.size() == 1)
0067     {
0068         v_output.emplace_back(move_forward(dest, v_input[0]));
0069         return;
0070     };
0071
0072     uint32_t nrange = v_input.size();
0073     uint32_t pos_ini = 0;
0074     while (pos_ini < v_input.size())
0075     {
0076         uint32_t nmerge = (nrange + 3) >> 2;
0077         uint32_t nelem = (nrange + nmerge - 1) / nmerge;
0078         range1_t rz = full_merge4(dest, &v_input[pos_ini], nelem, comp);
0079         v_output.emplace_back(rz);
0080         dest.first = rz.last;
0081         pos_ini += nelem;
0082         nrange -= nelem;
0083     };
0084     return;
0085 };
0086 //
0087 //-----------------------------------------------------------------------------
0088 //  function : uninit_merge_level4
0089 /// @brief merge the ranges moving the objects and constructing them in
0090 ///        uninitialized memory, in the vector v_input
0091 ///        using full_merge4. The v_output vector is used as auxiliary memory
0092 ///        in the internal process. The final results is in the dest range.
0093 ///        All the ranges of v_output are inside the range dest
0094 ///
0095 /// @param dest : range where move the elements merged
0096 /// @param v_input : vector of ranges to merge
0097 /// @param v_output : vector of ranges obtained
0098 /// @param comp : comparison object
0099 /// @return range with all the elements moved and constructed
0100 //-----------------------------------------------------------------------------
0101 template<class Value_t, class Iter_t, class Compare>
0102 void uninit_merge_level4(range<Value_t *> dest,
0103                          std::vector<range<Iter_t> > &v_input,
0104                          std::vector <range<Value_t *> > &v_output, Compare comp)
0105 {
0106     typedef range<Value_t *> range1_t;
0107     typedef util::value_iter<Iter_t> type1;
0108     static_assert (std::is_same< type1, Value_t >::value,
0109                     "Incompatible iterators\n");
0110
0111     v_output.clear();
0112     if (v_input.size() == 0) return;
0113     if (v_input.size() == 1)
0114     {
0115         v_output.emplace_back(move_construct(dest, v_input[0]));
0116         return;
0117     };
0118
0119     uint32_t nrange = v_input.size();
0120     uint32_t pos_ini = 0;
0121     while (pos_ini < v_input.size())
0122     {
0123         uint32_t nmerge = (nrange + 3) >> 2;
0124         uint32_t nelem = (nrange + nmerge - 1) / nmerge;
0125         range1_t rz = uninit_full_merge4(dest, &v_input[pos_ini], nelem, comp);
0126         v_output.emplace_back(rz);
0127         dest.first = rz.last;
0128         pos_ini += nelem;
0129         nrange -= nelem;
0130     };
0131     return;
0132 };
0133 //
0134 //-----------------------------------------------------------------------------
0135 //  function : merge_vector4
0136 /// @brief merge the ranges in the vector v_input using the merge_level4
0137 ///        function. The v_output vector is used as auxiliary memory in the
0138 ///        internal process
0139 ///        The final results is in the range_output range.
0140 ///        All the ranges of v_output are inside the range range_output
0141 ///        All the ranges of v_input are inside the range range_input
0142 /// @param range_input : range including all the ranges of v_input
0143 /// @param ange_output : range including all the elements of v_output
0144 /// @param v_input : vector of ranges to merge
0145 /// @param v_output : vector of ranges obtained
0146 /// @param comp : comparison object
0147 /// @return range with all the elements moved
0148 //-----------------------------------------------------------------------------
0149 template<class Iter1_t, class Iter2_t, class Compare>
0150 range<Iter2_t> merge_vector4(range<Iter1_t> range_input,
0151                              range<Iter2_t> range_output,
0152                              std::vector<range<Iter1_t> > &v_input,
0153                              std::vector<range<Iter2_t> > &v_output,
0154                              Compare comp)
0155 {
0156     typedef range<Iter2_t> range2_t;
0157     typedef util::value_iter<Iter1_t> type1;
0158     typedef util::value_iter<Iter2_t> type2;
0159     static_assert (std::is_same< type1, type2 >::value,
0160                     "Incompatible iterators\n");
0161
0162     v_output.clear();
0163     if (v_input.size() == 0)
0164     {
0165         return range2_t(range_output.first, range_output.first);
0166     };
0167     if (v_input.size() == 1)
0168     {
0169         return move_forward(range_output, v_input[0]);
0170     };
0171     bool sw = false;
0172     uint32_t nrange = v_input.size();
0173
0174     while (nrange > 1)
0175     {
0176         if (sw)
0177         {
0178             merge_level4(range_input, v_output, v_input, comp);
0179             sw = false;
0180             nrange = v_input.size();
0181         }
0182         else
0183         {
0184             merge_level4(range_output, v_input, v_output, comp);
0185             sw = true;
0186             nrange = v_output.size();
0187         };
0188     };
0189     return (sw) ? v_output[0] : move_forward(range_output, v_input[0]);
0190 };
0191
0192 //****************************************************************************
0193 };//    End namespace common
0194 };//    End namespace sort
0195 };//    End namespace boost
0196 //****************************************************************************
0197 //
0198 #endif