1 //---------------------------------------------------------------------------- 2 /// @file merge_four.hpp 3 /// @brief This file have the functions for to merge 4 buffers 4 /// 5 /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n 6 /// Distributed under the Boost Software License, Version 1.0.\n 7 /// ( See accompanying file LICENSE_1_0.txt or copy at 8 /// http://www.boost.org/LICENSE_1_0.txt ) 9 /// @version 0.1 10 /// 11 /// @remarks 12 //----------------------------------------------------------------------------- 13 #ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_FOUR_HPP 14 #define __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_FOUR_HPP 15 16 #include <boost/sort/common/util/traits.hpp> 17 #include <boost/sort/common/range.hpp> 18 #include <functional> 19 #include <iterator> 20 #include <memory> 21 #include <vector> 22 23 namespace boost 24 { 25 namespace sort 26 { 27 namespace common 28 { 29 30 // 31 //############################################################################ 32 // ## 33 // F U S I O N O F ## 34 // ## 35 // F O U R E L E M E N T S R A N G E ## 36 // ## 37 //############################################################################ 38 // 39 40 //----------------------------------------------------------------------------- 41 // function : less_range 42 /// @brief Compare the elements pointed by it1 and it2, and if they 43 /// are equals, compare their position, doing a stable comparison 44 /// 45 /// @param it1 : iterator to the first element 46 /// @param pos1 : position of the object pointed by it1 47 /// @param it2 : iterator to the second element 48 /// @param pos2 : position of the element pointed by it2 49 /// @param comp : comparison object 50 /// @return result of the comparison 51 //----------------------------------------------------------------------------- 52 template<class Iter_t, class Compare = typename util::compare_iter<Iter_t> > 53 inline bool less_range(Iter_t it1, uint32_t pos1, Iter_t it2, uint32_t pos2, 54 Compare comp = Compare()) 55 { 56 return (comp(*it1, *it2)) ? true : 57 (pos2 < pos1) ? false : not (comp(*it2, *it1)); 58 }; 59 60 //----------------------------------------------------------------------------- 61 // function : full_merge4 62 /// @brief Merge four ranges 63 /// 64 /// @param dest: range where move the elements merged. Their size must be 65 /// greater or equal than the sum of the sizes of the ranges 66 /// in vrange_input 67 /// @param vrange_input : array of ranges to merge 68 /// @param nrange_input : number of ranges in vrange_input 69 /// @param comp : comparison object 70 /// @return range with all the elements moved with the size adjusted 71 //----------------------------------------------------------------------------- 72 template<class Iter1_t, class Iter2_t, class Compare> 73 range<Iter1_t> full_merge4(const range<Iter1_t> &rdest, 74 range<Iter2_t> vrange_input[4], 75 uint32_t nrange_input, Compare comp) 76 { 77 typedef range<Iter1_t> range1_t; 78 typedef util::value_iter<Iter1_t> type1; 79 typedef util::value_iter<Iter2_t> type2; 80 static_assert (std::is_same< type1, type2 >::value, 81 "Incompatible iterators\n"); 82 83 size_t ndest = 0; 84 uint32_t i = 0; 85 while (i < nrange_input) 86 { 87 if (vrange_input[i].size() != 0) 88 { 89 ndest += vrange_input[i++].size(); 90 } 91 else 92 { 93 for (uint32_t k = i + 1; k < nrange_input; ++k) 94 { 95 vrange_input[k - 1] = vrange_input[k]; 96 }; 97 --nrange_input; 98 }; 99 }; 100 101 if (nrange_input == 0) return range1_t(rdest.first, rdest.first); 102 if (nrange_input == 1) return move_forward(rdest, vrange_input[0]); 103 if (nrange_input == 2) 104 { 105 return merge(rdest, vrange_input[0], vrange_input[1], comp); 106 }; 107 108 //------------------------------------------------------------------------ 109 // Initial sort 110 //------------------------------------------------------------------------ 111 uint32_t pos[4] = 112 { 0, 1, 2, 3 }, npos = nrange_input; 113 114 //----------------------------------------------------------------------- 115 // thanks to Steven Ross by their suggestion about the optimal 116 // sorting networks 117 //----------------------------------------------------------------------- 118 if (less_range(vrange_input[pos[1]].first, pos[1], 119 vrange_input[pos[0]].first, pos[0], comp)) 120 { 121 std::swap(pos[0], pos[1]); 122 }; 123 if (npos == 4 and less_range(vrange_input[pos[3]].first, pos[3], 124 vrange_input[pos[2]].first, pos[2], comp)) 125 { 126 std::swap(pos[3], pos[2]); 127 }; 128 if (less_range (vrange_input[pos[2]].first, pos[2], 129 vrange_input[pos[0]].first, pos[0], comp)) 130 { 131 std::swap(pos[0], pos[2]); 132 }; 133 if (npos == 4 134 and less_range (vrange_input[pos[3]].first, pos[3], 135 vrange_input[pos[1]].first, pos[1], comp)) 136 { 137 std::swap(pos[1], pos[3]); 138 }; 139 if (less_range (vrange_input[pos[2]].first, pos[2], 140 vrange_input[pos[1]].first, pos[1], comp)) 141 { 142 std::swap(pos[1], pos[2]); 143 }; 144 145 Iter1_t it_dest = rdest.first; 146 while (npos > 2) 147 { 148 *(it_dest++) = std::move(*(vrange_input[pos[0]].first++)); 149 if (vrange_input[pos[0]].size() == 0) 150 { 151 pos[0] = pos[1]; 152 pos[1] = pos[2]; 153 pos[2] = pos[3]; 154 --npos; 155 } 156 else 157 { 158 if (less_range(vrange_input[pos[1]].first, pos[1], 159 vrange_input[pos[0]].first, pos[0], comp)) 160 { 161 std::swap(pos[0], pos[1]); 162 if (less_range(vrange_input[pos[2]].first, pos[2], 163 vrange_input[pos[1]].first, pos[1], comp)) 164 { 165 std::swap(pos[1], pos[2]); 166 if (npos == 4 167 and less_range(vrange_input[pos[3]].first, 168 pos[3], 169 vrange_input[pos[2]].first, 170 pos[2], comp)) 171 { 172 std::swap(pos[2], pos[3]); 173 }; 174 }; 175 }; 176 }; 177 }; 178 179 range1_t raux1(rdest.first, it_dest), raux2(it_dest, rdest.last); 180 if (pos[0] < pos[1]) 181 { 182 return concat(raux1,merge(raux2, vrange_input[pos[0]], 183 vrange_input[pos[1]], comp)); 184 } 185 else 186 { 187 return concat(raux1, merge (raux2, vrange_input[pos[1]], 188 vrange_input[pos[0]], comp)); 189 }; 190 }; 191 192 //----------------------------------------------------------------------------- 193 // function : uninit_full_merge4 194 /// @brief Merge four ranges and put the result in uninitialized memory 195 /// 196 /// @param dest: range where create and move the elements merged. Their 197 /// size must be greater or equal than the sum of the sizes 198 /// of the ranges in the array R 199 /// @param vrange_input : array of ranges to merge 200 /// @param nrange_input : number of ranges in vrange_input 201 /// @param comp : comparison object 202 /// @return range with all the elements move with the size adjusted 203 //----------------------------------------------------------------------------- 204 template<class Value_t, class Iter_t, class Compare> 205 range<Value_t *> uninit_full_merge4(const range<Value_t *> &dest, 206 range<Iter_t> vrange_input[4], 207 uint32_t nrange_input, Compare comp) 208 { 209 typedef util::value_iter<Iter_t> type1; 210 static_assert (std::is_same< type1, Value_t >::value, 211 "Incompatible iterators\n"); 212 213 size_t ndest = 0; 214 uint32_t i = 0; 215 while (i < nrange_input) 216 { 217 if (vrange_input[i].size() != 0) 218 { 219 ndest += vrange_input[i++].size(); 220 } 221 else 222 { 223 for (uint32_t k = i + 1; k < nrange_input; ++k) 224 { 225 vrange_input[k - 1] = vrange_input[k]; 226 }; 227 --nrange_input; 228 }; 229 }; 230 if (nrange_input == 0) return range<Value_t *>(dest.first, dest.first); 231 if (nrange_input == 1) return move_construct(dest, vrange_input[0]); 232 if (nrange_input == 2) 233 { 234 return merge_construct(dest, vrange_input[0], vrange_input[1], comp); 235 }; 236 237 //------------------------------------------------------------------------ 238 // Initial sort 239 //------------------------------------------------------------------------ 240 uint32_t pos[4] = { 0, 1, 2, 3 }, npos = nrange_input; 241 242 //----------------------------------------------------------------------- 243 // thanks to Steven Ross by their suggestion about the optimal 244 // sorting networks 245 //----------------------------------------------------------------------- 246 if (less_range(vrange_input[pos[1]].first, pos[1], 247 vrange_input[pos[0]].first, pos[0], comp)) 248 { 249 std::swap(pos[0], pos[1]); 250 }; 251 if (npos == 4 and less_range(vrange_input[pos[3]].first, pos[3], 252 vrange_input[pos[2]].first, pos[2], comp)) 253 { 254 std::swap(pos[3], pos[2]); 255 }; 256 if (less_range(vrange_input[pos[2]].first, pos[2], 257 vrange_input[pos[0]].first, pos[0], comp)) 258 { 259 std::swap(pos[0], pos[2]); 260 }; 261 if (npos == 4 and less_range(vrange_input[pos[3]].first, pos[3], 262 vrange_input[pos[1]].first, pos[1], comp)) 263 { 264 std::swap(pos[1], pos[3]); 265 }; 266 if (less_range(vrange_input[pos[2]].first, pos[2], 267 vrange_input[pos[1]].first, pos[1], comp)) 268 { 269 std::swap(pos[1], pos[2]); 270 }; 271 272 Value_t *it_dest = dest.first; 273 while (npos > 2) 274 { 275 util::construct_object(&(*(it_dest++)), 276 std::move(*(vrange_input[pos[0]].first++))); 277 if (vrange_input[pos[0]].size() == 0) 278 { 279 pos[0] = pos[1]; 280 pos[1] = pos[2]; 281 pos[2] = pos[3]; 282 --npos; 283 } 284 else 285 { 286 if (less_range (vrange_input[pos[1]].first, pos[1], 287 vrange_input[pos[0]].first, pos[0], comp)) 288 { 289 std::swap(pos[0], pos[1]); 290 if (less_range (vrange_input[pos[2]].first, pos[2], 291 vrange_input[pos[1]].first, pos[1], comp)) 292 { 293 std::swap(pos[1], pos[2]); 294 if (npos == 4 and less_range(vrange_input[pos[3]].first, 295 pos[3], 296 vrange_input[pos[2]].first, 297 pos[2], comp)) 298 { 299 std::swap(pos[2], pos[3]); 300 }; 301 }; 302 }; 303 }; 304 }; // end while (npos > 2) 305 306 range<Value_t *> raux1(dest.first, it_dest), raux2(it_dest, dest.last); 307 if (pos[0] < pos[1]) 308 { 309 return concat(raux1, 310 merge_construct(raux2, vrange_input[pos[0]], 311 vrange_input[pos[1]], comp)); 312 } 313 else 314 { 315 return concat(raux1, 316 merge_construct(raux2, vrange_input[pos[1]], 317 vrange_input[pos[0]], comp)); 318 }; 319 }; 320 321 //**************************************************************************** 322 };// End namespace common 323 };// End namespace sort 324 };// End namespace boost 325 //**************************************************************************** 326 // 327 #endif 328