1 //----------------------------------------------------------------------------
2 /// @file merge.hpp
3 /// @brief low level merge functions
4 ///
5 /// @author Copyright (c) 2016 Francisco Jose 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_COMMON_UTIL_MERGE_HPP
14 #define __BOOST_SORT_COMMON_UTIL_MERGE_HPP
15
16 #include <algorithm>
17 #include <functional>
18 #include <iterator>
19 #include <memory>
20
21 #include <boost/sort/common/util/algorithm.hpp>
22 #include <boost/sort/common/util/traits.hpp>
23 #include <boost/sort/common/util/circular_buffer.hpp>
24
25 namespace boost
26 {
27 namespace sort
28 {
29 namespace common
30 {
31 namespace util
32 {
33 namespace here = boost::sort::common::util;
34 //----------------------------------------------------------------------------
35 //
36 // F U N C T I O N S I N T H E F I L E
37 //----------------------------------------------------------------------------
38 //
39 // template < class Iter1_t, class Iter2_t, class Compare >
40 // Iter2_t merge (Iter1_t buf1, const Iter1_t end_buf1, Iter1_t buf2,
41 // const Iter1_t end_buf2, Iter2_t buf_out, Compare comp)
42 //
43 // template < class Iter_t, class Value_t, class Compare >
44 // Value_t *merge_construct (Iter_t first1, const Iter_t last1, Iter_t first2,
45 // const Iter_t last2, Value_t *it_out, Compare comp)
46 //
47 // template < class Iter1_t, class Iter2_t, class Compare >
48 // Iter2_t merge_half (Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
49 // const Iter2_t end_buf2, Iter2_t buf_out, Compare comp)
50 //
51 // template < class Iter1_t, class Iter2_t, class Compare >
52 // Iter2_t merge_half_backward (Iter1_t buf1, Iter1_t end_buf1,
53 // Iter2_t buf2, Iter2_t end_buf2,
54 // Iter1_t end_buf_out, Compare comp)
55 //
56 // template < class Iter1_t, class Iter2_t, class Iter3_t, class Compare >
57 // bool merge_uncontiguous (Iter1_t src1, const Iter1_t end_src1,
58 // Iter2_t src2, const Iter2_t end_src2,
59 // Iter3_t aux, Compare comp)
60 //
61 // template < class Iter1_t, class Iter2_t, class Compare >
62 // bool merge_contiguous (Iter1_t src1, Iter1_t src2, Iter1_t end_src2,
63 // Iter2_t buf, Compare comp)
64 //
65 // template < class Iter_t, class Circular ,class Compare >
66 // bool merge_circular (Iter_t buf1, Iter_t end_buf1,
67 // Iter_t buf2, Iter_t end_buf2,
68 // Circular &circ, Compare comp, Iter_t &it_aux)
69 //
70 //----------------------------------------------------------------------------
71 //
72 //-----------------------------------------------------------------------------
73 // function : merge
74 /// @brief Merge two contiguous buffers pointed by buf1 and buf2, and put
75 /// in the buffer pointed by buf_out
76 ///
77 /// @param buf1 : iterator to the first element in the first buffer
78 /// @param end_buf1 : final iterator of first buffer
79 /// @param buf2 : iterator to the first iterator to the second buffer
80 /// @param end_buf2 : final iterator of the second buffer
81 /// @param buf_out : buffer where move the elements merged
82 /// @param comp : comparison object
83 //-----------------------------------------------------------------------------
84 template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
merge(Iter1_t buf1,const Iter1_t end_buf1,Iter2_t buf2,const Iter2_t end_buf2,Iter3_t buf_out,Compare comp)85 static Iter3_t merge(Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
86 const Iter2_t end_buf2, Iter3_t buf_out, Compare comp)
87 {
88 //-------------------------------------------------------------------------
89 // Metaprogramming
90 //-------------------------------------------------------------------------
91 typedef value_iter<Iter1_t> value1_t;
92 typedef value_iter<Iter2_t> value2_t;
93 typedef value_iter<Iter3_t> value3_t;
94 static_assert (std::is_same< value1_t, value2_t >::value,
95 "Incompatible iterators\n");
96 static_assert (std::is_same< value3_t, value2_t >::value,
97 "Incompatible iterators\n");
98
99 //-------------------------------------------------------------------------
100 // Code
101 //-------------------------------------------------------------------------
102 const size_t MIN_CHECK = 1024;
103
104 if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
105 {
106 if (buf1 == end_buf1) return move_forward(buf_out, buf2, end_buf2);
107 if (buf2 == end_buf2) return move_forward(buf_out, buf1, end_buf1);
108
109 if (not comp(*buf2, *(end_buf1 - 1)))
110 {
111 Iter3_t mid = move_forward(buf_out, buf1, end_buf1);
112 return move_forward(mid, buf2, end_buf2);
113 };
114
115 if (comp(*(end_buf2 - 1), *buf1))
116 {
117 Iter3_t mid = move_forward(buf_out, buf2, end_buf2);
118 return move_forward(mid, buf1, end_buf1);
119 };
120 };
121 while ((buf1 != end_buf1) and (buf2 != end_buf2))
122 {
123 *(buf_out++) = (not comp(*buf2, *buf1)) ?
124 std::move(*(buf1++)) : std::move(*(buf2++));
125 };
126
127 return (buf1 == end_buf1) ?
128 move_forward(buf_out, buf2, end_buf2) :
129 move_forward(buf_out, buf1, end_buf1);
130 }
131 ;
132 //
133 //-----------------------------------------------------------------------------
134 // function : merge_construct
135 /// @brief Merge two contiguous buffers pointed by first1 and first2, and put
136 /// in the uninitialized buffer pointed by it_out
137 ///
138 /// @param first1 : iterator to the first element in the first buffer
139 /// @param last1 : last iterator of the first buffer
140 /// @param first2 : iterator to the first element to the second buffer
141 /// @param last2 : final iterator of the second buffer
142 /// @param it_out : uninitialized buffer where move the elements merged
143 /// @param comp : comparison object
144 //-----------------------------------------------------------------------------
145 template<class Iter1_t, class Iter2_t, class Value_t, class Compare>
merge_construct(Iter1_t first1,const Iter1_t last1,Iter2_t first2,const Iter2_t last2,Value_t * it_out,Compare comp)146 static Value_t *merge_construct(Iter1_t first1, const Iter1_t last1,
147 Iter2_t first2, const Iter2_t last2,
148 Value_t *it_out, Compare comp)
149 {
150 //-------------------------------------------------------------------------
151 // Metaprogramming
152 //-------------------------------------------------------------------------
153 typedef value_iter<Iter1_t> type1;
154 typedef value_iter<Iter2_t> type2;
155 static_assert (std::is_same< Value_t, type1 >::value,
156 "Incompatible iterators\n");
157 static_assert (std::is_same< Value_t, type2 >::value,
158 "Incompatible iterators\n");
159
160 //-------------------------------------------------------------------------
161 // Code
162 //-------------------------------------------------------------------------
163 const size_t MIN_CHECK = 1024;
164
165 if (size_t((last1 - first1) + (last2 - first2)) >= MIN_CHECK)
166 {
167 if (first1 == last1) return move_construct(it_out, first2, last2);
168 if (first2 == last2) return move_construct(it_out, first1, last1);
169
170 if (not comp(*first2, *(last1 - 1)))
171 {
172 Value_t* mid = move_construct(it_out, first1, last1);
173 return move_construct(mid, first2, last2);
174 };
175
176 if (comp(*(last2 - 1), *first1))
177 {
178 Value_t* mid = move_construct(it_out, first2, last2);
179 return move_construct(mid, first1, last1);
180 };
181 };
182 while (first1 != last1 and first2 != last2)
183 {
184 construct_object((it_out++),
185 (not comp(*first2, *first1)) ?
186 std::move(*(first1++)) :
187 std::move(*(first2++)));
188 };
189 return (first1 == last1) ?
190 move_construct(it_out, first2, last2) :
191 move_construct(it_out, first1, last1);
192 };
193 //
194 //---------------------------------------------------------------------------
195 // function : merge_half
196 /// @brief : Merge two buffers. The first buffer is in a separate memory.
197 /// The second buffer have a empty space before buf2 of the same size
198 /// than the (end_buf1 - buf1)
199 ///
200 /// @param buf1 : iterator to the first element of the first buffer
201 /// @param end_buf1 : iterator to the last element of the first buffer
202 /// @param buf2 : iterator to the first element of the second buffer
203 /// @param end_buf2 : iterator to the last element of the second buffer
204 /// @param buf_out : iterator to the first element to the buffer where put
205 /// the result
206 /// @param comp : object for Compare two elements of the type pointed
207 /// by the Iter1_t and Iter2_t
208 //---------------------------------------------------------------------------
209 template<class Iter1_t, class Iter2_t, class Compare>
merge_half(Iter1_t buf1,const Iter1_t end_buf1,Iter2_t buf2,const Iter2_t end_buf2,Iter2_t buf_out,Compare comp)210 static Iter2_t merge_half(Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
211 const Iter2_t end_buf2, Iter2_t buf_out, Compare comp)
212 {
213 //-------------------------------------------------------------------------
214 // Metaprogramming
215 //-------------------------------------------------------------------------
216 typedef value_iter<Iter1_t> value1_t;
217 typedef value_iter<Iter2_t> value2_t;
218 static_assert (std::is_same< value1_t, value2_t >::value,
219 "Incompatible iterators\n");
220
221 //-------------------------------------------------------------------------
222 // Code
223 //-------------------------------------------------------------------------
224 #ifdef __BS_DEBUG
225 assert ( (buf2 - buf_out) == ( end_buf1 - buf1));
226 #endif
227 const size_t MIN_CHECK = 1024;
228
229 if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
230 {
231 if (buf1 == end_buf1) return end_buf2;
232 if (buf2 == end_buf2) return move_forward(buf_out, buf1, end_buf1);
233
234 if (not comp(*buf2, *(end_buf1 - 1)))
235 {
236 move_forward(buf_out, buf1, end_buf1);
237 return end_buf2;
238 };
239
240 if (comp(*(end_buf2 - 1), *buf1))
241 {
242 Iter2_t mid = move_forward(buf_out, buf2, end_buf2);
243 return move_forward(mid, buf1, end_buf1);
244 };
245 };
246 while ((buf1 != end_buf1) and (buf2 != end_buf2))
247 {
248 *(buf_out++) = (not comp(*buf2, *buf1)) ?
249 std::move(*(buf1++)) : std::move(*(buf2++));
250 };
251 return (buf2 == end_buf2)? move_forward(buf_out, buf1, end_buf1) : end_buf2;
252 };
253
254 //
255 //---------------------------------------------------------------------------
256 // function : merge_half_backward
257 /// @brief : Merge two buffers. The first buffer is in a separate memory.
258 /// The second buffer have a empty space before buf2 of the same size
259 /// than the (end_buf1 - buf1)
260 ///
261 /// @param buf1 : iterator to the first element of the first buffer
262 /// @param end_buf1 : iterator to the last element of the first buffer
263 /// @param buf2 : iterator to the first element of the second buffer
264 /// @param end_buf2 : iterator to the last element of the second buffer
265 /// @param buf_out : iterator to the first element to the buffer where put
266 /// the result
267 /// @param comp : object for Compare two elements of the type pointed
268 /// by the Iter1_t and Iter2_t
269 //---------------------------------------------------------------------------
270 template<class Iter1_t, class Iter2_t, class Compare>
merge_half_backward(Iter1_t buf1,Iter1_t end_buf1,Iter2_t buf2,Iter2_t end_buf2,Iter1_t end_buf_out,Compare comp)271 static Iter2_t merge_half_backward(Iter1_t buf1, Iter1_t end_buf1, Iter2_t buf2,
272 Iter2_t end_buf2, Iter1_t end_buf_out,
273 Compare comp)
274 {
275 //-------------------------------------------------------------------------
276 // Metaprogramming
277 //-------------------------------------------------------------------------
278 typedef value_iter<Iter1_t> value1_t;
279 typedef value_iter<Iter2_t> value2_t;
280 static_assert (std::is_same< value1_t, value2_t >::value,
281 "Incompatible iterators\n");
282
283 //-------------------------------------------------------------------------
284 // Code
285 //-------------------------------------------------------------------------
286 #ifdef __BS_DEBUG
287 assert ((end_buf_out - end_buf1) == (end_buf2 - buf2) );
288 #endif
289 const size_t MIN_CHECK = 1024;
290
291 if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
292 {
293 if (buf2 == end_buf2) return buf1;
294 if (buf1 == end_buf1)
295 return here::move_backward(end_buf_out, buf2, end_buf2);
296
297 if (not comp(*buf2, *(end_buf1 - 1)))
298 {
299 here::move_backward(end_buf_out, buf2, end_buf2);
300 return buf1;
301 };
302
303 if (comp(*(end_buf2 - 1), *buf1))
304 {
305 Iter1_t mid = here::move_backward(end_buf_out, buf1, end_buf1);
306 return here::move_backward(mid, buf2, end_buf2);
307 };
308 };
309 while ((buf1 != end_buf1) and (buf2 != end_buf2))
310 {
311 *(--end_buf_out) =
312 (not comp(*(end_buf2 - 1), *(end_buf1 - 1))) ?
313 std::move(*(--end_buf2)):
314 std::move(*(--end_buf1));
315 };
316 return (buf1 == end_buf1) ?
317 here::move_backward(end_buf_out, buf2, end_buf2) : buf1;
318 };
319
320 //
321 //-----------------------------------------------------------------------------
322 // function : merge_uncontiguous
323 /// @brief : merge two uncontiguous buffers, placing the results in the buffers
324 /// Use an auxiliary buffer pointed by aux
325 ///
326 /// @param src1 : iterator to the first element of the first buffer
327 /// @param end_src1 : last iterator of the first buffer
328 /// @param src2 : iterator to the first element of the second buffer
329 /// @param end_src2 : last iterator of the second buffer
330 /// @param aux : iterator to the first element of the auxiliary buffer
331 /// @param comp : object for to Compare elements
332 /// @return true : not changes done, false : changes in the buffers
333 /// @remarks
334 //-----------------------------------------------------------------------------
335 template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
merge_uncontiguous(Iter1_t src1,const Iter1_t end_src1,Iter2_t src2,const Iter2_t end_src2,Iter3_t aux,Compare comp)336 static bool merge_uncontiguous(Iter1_t src1, const Iter1_t end_src1,
337 Iter2_t src2, const Iter2_t end_src2,
338 Iter3_t aux, Compare comp)
339 {
340 //-------------------------------------------------------------------------
341 // Metaprogramming
342 //-------------------------------------------------------------------------
343 typedef value_iter<Iter1_t> type1;
344 typedef value_iter<Iter2_t> type2;
345 typedef value_iter<Iter3_t> type3;
346 static_assert (std::is_same< type1, type2 >::value,
347 "Incompatible iterators\n");
348 static_assert (std::is_same< type3, type2 >::value,
349 "Incompatible iterators\n");
350
351 //-------------------------------------------------------------------------
352 // Code
353 //-------------------------------------------------------------------------
354 if (src1 == end_src1 or src2 == end_src2
355 or not comp(*src2, *(end_src1 - 1))) return true;
356
357 while (src1 != end_src1 and not comp(*src2, *src1))
358 ++src1;
359
360 Iter3_t const end_aux = aux + (end_src1 - src1);
361 Iter2_t src2_first = src2;
362 move_forward(aux, src1, end_src1);
363
364 while ((src1 != end_src1) and (src2 != end_src2))
365 {
366 *(src1++) = std::move((not comp(*src2, *aux)) ? *(aux++) : *(src2++));
367 }
368
369 if (src2 == end_src2)
370 {
371 while (src1 != end_src1)
372 *(src1++) = std::move(*(aux++));
373 move_forward(src2_first, aux, end_aux);
374 }
375 else
376 {
377 merge_half(aux, end_aux, src2, end_src2, src2_first, comp);
378 };
379 return false;
380 };
381
382 //
383 //-----------------------------------------------------------------------------
384 // function : merge_contiguous
385 /// @brief : merge two contiguous buffers,using an auxiliary buffer pointed
386 /// by buf. The results are in src1 and src2
387 ///
388 /// @param src1: iterator to the first position of the first buffer
389 /// @param src2: final iterator of the first buffer and first iterator
390 /// of the second buffer
391 /// @param end_src2 : final iterator of the second buffer
392 /// @param buf : iterator to buffer used as auxiliary memory
393 /// @param comp : object for to Compare elements
394 /// @return true : not changes done, false : changes in the buffers
395 //-----------------------------------------------------------------------------
396 template<class Iter1_t, class Iter2_t, class Compare>
merge_contiguous(Iter1_t src1,Iter1_t src2,Iter1_t end_src2,Iter2_t buf,Compare comp)397 static bool merge_contiguous(Iter1_t src1, Iter1_t src2, Iter1_t end_src2,
398 Iter2_t buf, Compare comp)
399 {
400 //-------------------------------------------------------------------------
401 // Metaprogramming
402 //-------------------------------------------------------------------------
403 typedef value_iter<Iter1_t> type1;
404 typedef value_iter<Iter2_t> type2;
405 static_assert (std::is_same< type1, type2 >::value,
406 "Incompatible iterators\n");
407
408 //-------------------------------------------------------------------------
409 // Code
410 //-------------------------------------------------------------------------
411 if (src1 == src2 or src2 == end_src2 or not comp(*src2, *(src2 - 1)))
412 return true;
413
414 Iter1_t end_src1 = src2;
415 while (src1 != end_src1 and not comp(*src2, *src1))
416 ++src1;
417
418 if (src1 == end_src1) return false;
419
420 size_t nx = end_src1 - src1;
421 move_forward(buf, src1, end_src1);
422 merge_half(buf, buf + nx, src2, end_src2, src1, comp);
423 return false;
424 };
425 //
426 //-----------------------------------------------------------------------------
427 // function : merge_circular
428 /// @brief : merge two buffers,using a circular buffer
429 /// This function don't check the parameters
430 /// @param buf1: iterator to the first position of the first buffer
431 /// @param end_buf1: iterator after the last element of the first buffer
432 /// @param buf2: iterator to the first element of the secind buffer
433 /// @param end_buf2: iterator to the first element of the secind buffer
434 /// @param circ : circular buffer
435 /// @param comp : comparison object
436 /// @return true : finished buf1, false : finished buf2
437 /// @comments : be carefully because the iterators buf1 and buf2 are modified
438 //-----------------------------------------------------------------------------
439 template<class Iter1_t, class Iter2_t, class Circular, class Compare>
merge_circular(Iter1_t buf1,Iter1_t end_buf1,Iter2_t buf2,Iter2_t end_buf2,Circular & circ,Compare comp,Iter1_t & it1_out,Iter2_t & it2_out)440 static bool merge_circular(Iter1_t buf1, Iter1_t end_buf1, Iter2_t buf2,
441 Iter2_t end_buf2, Circular &circ, Compare comp,
442 Iter1_t &it1_out, Iter2_t &it2_out)
443 {
444 //-------------------------------------------------------------------------
445 // Metaprogramming
446 //-------------------------------------------------------------------------
447 typedef value_iter<Iter1_t> type1;
448 typedef value_iter<Iter2_t> type2;
449 static_assert (std::is_same< type1, type2 >::value,
450 "Incompatible iterators\n");
451 typedef typename Circular::value_t type3;
452 static_assert (std::is_same<type1, type3>::value,
453 "Incompatible iterators\n");
454
455 //-------------------------------------------------------------------------
456 // Code
457 //-------------------------------------------------------------------------
458 #ifdef __BS_DEBUG
459 assert ( circ.free_size() >= size_t ((end_buf1-buf1) + (end_buf2-buf2)));
460 #endif
461
462 if (not comp(*buf2, *(end_buf1 - 1)))
463 {
464 circ.push_move_back(buf1, (end_buf1 - buf1));
465 it1_out = end_buf1;
466 it2_out = buf2;
467 return true;
468 };
469 if (comp(*(end_buf2 - 1), *buf1))
470 {
471 circ.push_move_back(buf2, (end_buf2 - buf2));
472 it1_out = buf1;
473 it2_out = end_buf2;
474 return false;
475 }
476 while (buf1 != end_buf1 and buf2 != end_buf2)
477 {
478 circ.push_back(comp(*buf2, *buf1) ? std::move(*(buf2++))
479 : std::move(*(buf1++)));
480 };
481 it2_out = buf2;
482 it1_out = buf1;
483 bool ret = (buf1 == end_buf1);
484 return ret;
485 };
486 //
487 //****************************************************************************
488 };// End namespace util
489 };// End namespace common
490 };// End namespace sort
491 };// End namespace boost
492 //****************************************************************************
493 //
494 #endif
495