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

source code of boost/libs/sort/include/boost/sort/common/merge_four.hpp