sort/common/merge_four.hpp

0001 //----------------------------------------------------------------------------
0002 /// @file merge_four.hpp
0003 /// @brief This file have the functions for to merge 4 buffers
0004 ///
0005 /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n
0006 ///         Distributed under the Boost Software License, Version 1.0.\n
0007 ///         ( See accompanying file LICENSE_1_0.txt or copy at
0008 ///           http://www.boost.org/LICENSE_1_0.txt  )
0009 /// @version 0.1
0010 ///
0011 /// @remarks
0012 //-----------------------------------------------------------------------------
0013 #ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_FOUR_HPP
0014 #define __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_FOUR_HPP
0015
0016 #include <ciso646>
0017 #include <functional>
0018 #include <iterator>
0019 #include <memory>
0020 #include <vector>
0021 #include <boost/sort/common/util/traits.hpp>
0022 #include <boost/sort/common/range.hpp>
0023
0024
0025 namespace boost
0026 {
0027 namespace sort
0028 {
0029 namespace common
0030 {
0031
0032 //
0033 //############################################################################
0034 //                                                                          ##
0035 //                       F U S I O N     O F                                ##
0036 //                                                                          ##
0037 //              F O U R     E L E M E N T S    R A N G E                    ##
0038 //                                                                          ##
0039 //############################################################################
0040 //
0041
0042 //-----------------------------------------------------------------------------
0043 //  function : less_range
0044 /// @brief Compare the elements pointed by it1 and it2, and if they
0045 ///        are equals, compare their position, doing a stable comparison
0046 ///
0047 /// @param it1 : iterator to the first element
0048 /// @param pos1 : position of the object pointed by it1
0049 /// @param it2 : iterator to the second element
0050 /// @param pos2 : position of the element pointed by it2
0051 /// @param comp : comparison object
0052 /// @return result of the comparison
0053 //-----------------------------------------------------------------------------
0054 template<class Iter_t, class Compare = typename util::compare_iter<Iter_t> >
0055 inline bool less_range(Iter_t it1, uint32_t pos1, Iter_t it2, uint32_t pos2,
0056                        Compare comp = Compare())
0057 {
0058     return (comp(*it1, *it2)) ? true :
0059            (pos2 < pos1) ? false : not (comp(*it2, *it1));
0060 };
0061
0062 //-----------------------------------------------------------------------------
0063 //  function : full_merge4
0064 /// @brief Merge four ranges
0065 ///
0066 /// @param dest: range where move the elements merged. Their size must be
0067 ///              greater or equal than the sum of the sizes of the ranges
0068 ///              in vrange_input
0069 /// @param vrange_input : array of ranges to merge
0070 /// @param nrange_input : number of ranges in vrange_input
0071 /// @param comp : comparison object
0072 /// @return range with all the elements moved with the size adjusted
0073 //-----------------------------------------------------------------------------
0074 template<class Iter1_t, class Iter2_t, class Compare>
0075 range<Iter1_t> full_merge4(const range<Iter1_t> &rdest,
0076                            range<Iter2_t> vrange_input[4],
0077                            uint32_t nrange_input, Compare comp)
0078 {
0079     using std::swap;
0080     typedef range<Iter1_t> range1_t;
0081     typedef util::value_iter<Iter1_t> type1;
0082     typedef util::value_iter<Iter2_t> type2;
0083     static_assert (std::is_same< type1, type2 >::value,
0084                     "Incompatible iterators\n");
0085
0086     size_t ndest = 0;
0087     uint32_t i = 0;
0088     while (i < nrange_input)
0089     {
0090         if (vrange_input[i].size() != 0)
0091         {
0092             ndest += vrange_input[i++].size();
0093         }
0094         else
0095         {
0096             for (uint32_t k = i + 1; k < nrange_input; ++k)
0097             {
0098                 vrange_input[k - 1] = vrange_input[k];
0099             };
0100             --nrange_input;
0101         };
0102     };
0103
0104     if (nrange_input == 0) return range1_t(rdest.first, rdest.first);
0105     if (nrange_input == 1) return move_forward(rdest, vrange_input[0]);
0106     if (nrange_input == 2)
0107     {
0108         return merge(rdest, vrange_input[0], vrange_input[1], comp);
0109     };
0110
0111     //------------------------------------------------------------------------
0112     // Initial sort
0113     //------------------------------------------------------------------------
0114     uint32_t pos[4] =
0115     { 0, 1, 2, 3 }, npos = nrange_input;
0116
0117     //-----------------------------------------------------------------------
0118     // thanks to Steven Ross by their suggestion about the optimal
0119     // sorting networks
0120     //-----------------------------------------------------------------------
0121     if (less_range(vrange_input[pos[1]].first, pos[1],
0122                     vrange_input[pos[0]].first, pos[0], comp))
0123     {
0124         swap(pos[0], pos[1]);
0125     };
0126     if (npos == 4 and less_range(vrange_input[pos[3]].first, pos[3],
0127                                  vrange_input[pos[2]].first, pos[2], comp))
0128     {
0129         swap(pos[3], pos[2]);
0130     };
0131     if (less_range (vrange_input[pos[2]].first, pos[2],
0132                     vrange_input[pos[0]].first, pos[0], comp))
0133     {
0134         swap(pos[0], pos[2]);
0135     };
0136     if (npos == 4
0137                     and less_range (vrange_input[pos[3]].first, pos[3],
0138                                     vrange_input[pos[1]].first, pos[1], comp))
0139     {
0140         swap(pos[1], pos[3]);
0141     };
0142     if (less_range (vrange_input[pos[2]].first, pos[2],
0143                     vrange_input[pos[1]].first, pos[1], comp))
0144     {
0145         swap(pos[1], pos[2]);
0146     };
0147
0148     Iter1_t it_dest = rdest.first;
0149     while (npos > 2)
0150     {
0151         *(it_dest++) = std::move(*(vrange_input[pos[0]].first++));
0152         if (vrange_input[pos[0]].size() == 0)
0153         {
0154             pos[0] = pos[1];
0155             pos[1] = pos[2];
0156             pos[2] = pos[3];
0157             --npos;
0158         }
0159         else
0160         {
0161             if (less_range(vrange_input[pos[1]].first, pos[1],
0162                             vrange_input[pos[0]].first, pos[0], comp))
0163             {
0164                 swap(pos[0], pos[1]);
0165                 if (less_range(vrange_input[pos[2]].first, pos[2],
0166                                 vrange_input[pos[1]].first, pos[1], comp))
0167                 {
0168                     swap(pos[1], pos[2]);
0169                     if (npos == 4
0170                                     and less_range(vrange_input[pos[3]].first,
0171                                                     pos[3],
0172                                                     vrange_input[pos[2]].first,
0173                                                     pos[2], comp))
0174                     {
0175                         swap(pos[2], pos[3]);
0176                     };
0177                 };
0178             };
0179         };
0180     };
0181
0182     range1_t raux1(rdest.first, it_dest), raux2(it_dest, rdest.last);
0183     if (pos[0] < pos[1])
0184     {
0185         return concat(raux1,merge(raux2, vrange_input[pos[0]],
0186                                   vrange_input[pos[1]], comp));
0187     }
0188     else
0189     {
0190         return concat(raux1, merge (raux2, vrange_input[pos[1]],
0191                                     vrange_input[pos[0]], comp));
0192     };
0193 };
0194
0195 //-----------------------------------------------------------------------------
0196 //  function : uninit_full_merge4
0197 /// @brief Merge four ranges and put the result in uninitialized memory
0198 ///
0199 /// @param dest: range where create and move the elements merged. Their
0200 ///              size must be greater or equal than the sum of the sizes
0201 ///              of the ranges in the array R
0202 /// @param vrange_input : array of ranges to merge
0203 /// @param nrange_input : number of ranges in vrange_input
0204 /// @param comp : comparison object
0205 /// @return range with all the elements move with the size adjusted
0206 //-----------------------------------------------------------------------------
0207 template<class Value_t, class Iter_t, class Compare>
0208 range<Value_t *> uninit_full_merge4(const range<Value_t *> &dest,
0209                                     range<Iter_t> vrange_input[4],
0210                                     uint32_t nrange_input, Compare comp)
0211 {
0212     using std::swap;
0213     typedef util::value_iter<Iter_t> type1;
0214     static_assert (std::is_same< type1, Value_t >::value,
0215                     "Incompatible iterators\n");
0216
0217     size_t ndest = 0;
0218     uint32_t i = 0;
0219     while (i < nrange_input)
0220     {
0221         if (vrange_input[i].size() != 0)
0222         {
0223             ndest += vrange_input[i++].size();
0224         }
0225         else
0226         {
0227             for (uint32_t k = i + 1; k < nrange_input; ++k)
0228             {
0229                 vrange_input[k - 1] = vrange_input[k];
0230             };
0231             --nrange_input;
0232         };
0233     };
0234     if (nrange_input == 0) return range<Value_t *>(dest.first, dest.first);
0235     if (nrange_input == 1) return move_construct(dest, vrange_input[0]);
0236     if (nrange_input == 2)
0237     {
0238         return merge_construct(dest, vrange_input[0], vrange_input[1], comp);
0239     };
0240
0241     //------------------------------------------------------------------------
0242     // Initial sort
0243     //------------------------------------------------------------------------
0244     uint32_t pos[4] = { 0, 1, 2, 3 }, npos = nrange_input;
0245
0246     //-----------------------------------------------------------------------
0247     // thanks to Steven Ross by their suggestion about the optimal
0248     // sorting networks
0249     //-----------------------------------------------------------------------
0250     if (less_range(vrange_input[pos[1]].first, pos[1],
0251                     vrange_input[pos[0]].first, pos[0], comp))
0252     {
0253         swap(pos[0], pos[1]);
0254     };
0255     if (npos == 4  and less_range(vrange_input[pos[3]].first, pos[3],
0256                                   vrange_input[pos[2]].first, pos[2], comp))
0257     {
0258         swap(pos[3], pos[2]);
0259     };
0260     if (less_range(vrange_input[pos[2]].first, pos[2],
0261                     vrange_input[pos[0]].first, pos[0], comp))
0262     {
0263         swap(pos[0], pos[2]);
0264     };
0265     if (npos == 4 and less_range(vrange_input[pos[3]].first, pos[3],
0266                                  vrange_input[pos[1]].first, pos[1], comp))
0267     {
0268         swap(pos[1], pos[3]);
0269     };
0270     if (less_range(vrange_input[pos[2]].first, pos[2],
0271                     vrange_input[pos[1]].first, pos[1], comp))
0272     {
0273         swap(pos[1], pos[2]);
0274     };
0275
0276     Value_t *it_dest = dest.first;
0277     while (npos > 2)
0278     {
0279         util::construct_object(&(*(it_dest++)),
0280                         std::move(*(vrange_input[pos[0]].first++)));
0281         if (vrange_input[pos[0]].size() == 0)
0282         {
0283             pos[0] = pos[1];
0284             pos[1] = pos[2];
0285             pos[2] = pos[3];
0286             --npos;
0287         }
0288         else
0289         {
0290             if (less_range (vrange_input[pos[1]].first, pos[1],
0291                             vrange_input[pos[0]].first, pos[0], comp))
0292             {
0293                 swap(pos[0], pos[1]);
0294                 if (less_range (vrange_input[pos[2]].first, pos[2],
0295                                 vrange_input[pos[1]].first, pos[1], comp))
0296                 {
0297                     swap(pos[1], pos[2]);
0298                     if (npos == 4 and less_range(vrange_input[pos[3]].first,
0299                                                  pos[3],
0300                                                  vrange_input[pos[2]].first,
0301                                                  pos[2], comp))
0302                     {
0303                         swap(pos[2], pos[3]);
0304                     };
0305                 };
0306             };
0307         };
0308     }; // end while (npos > 2)
0309
0310     range<Value_t *> raux1(dest.first, it_dest), raux2(it_dest, dest.last);
0311     if (pos[0] < pos[1])
0312     {
0313         return concat(raux1,
0314                       merge_construct(raux2, vrange_input[pos[0]],
0315                                       vrange_input[pos[1]], comp));
0316     }
0317     else
0318     {
0319         return concat(raux1,
0320                       merge_construct(raux2, vrange_input[pos[1]],
0321                                       vrange_input[pos[0]], comp));
0322     };
0323 };
0324
0325 //****************************************************************************
0326 };//    End namespace common
0327 };//    End namespace sort
0328 };//    End namespace boost
0329 //****************************************************************************
0330 //
0331 #endif