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> >
less_range(Iter_t it1,uint32_t pos1,Iter_t it2,uint32_t pos2,Compare comp=Compare ())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>
full_merge4(const range<Iter1_t> & rdest,range<Iter2_t> vrange_input[4],uint32_t nrange_input,Compare comp)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>
uninit_full_merge4(const range<Value_t * > & dest,range<Iter_t> vrange_input[4],uint32_t nrange_input,Compare comp)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