1//////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2015-2016.
4// Distributed under the Boost Software License, Version 1.0.
5// (See accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7//
8// See http://www.boost.org/libs/move for documentation.
9//
10//////////////////////////////////////////////////////////////////////////////
11#ifndef BOOST_MOVE_MERGE_HPP
12#define BOOST_MOVE_MERGE_HPP
13
14#include <boost/move/algo/move.hpp>
15#include <boost/move/adl_move_swap.hpp>
16#include <boost/move/algo/detail/basic_op.hpp>
17#include <boost/move/detail/iterator_traits.hpp>
18#include <boost/move/detail/destruct_n.hpp>
19#include <boost/move/algo/predicate.hpp>
20#include <boost/move/detail/iterator_to_raw_pointer.hpp>
21#include <boost/assert.hpp>
22
23namespace boost {
24namespace movelib {
25
26// @cond
27
28/*
29template<typename Unsigned>
30inline Unsigned gcd(Unsigned x, Unsigned y)
31{
32 if(0 == ((x &(x-1)) | (y & (y-1)))){
33 return x < y ? x : y;
34 }
35 else{
36 do
37 {
38 Unsigned t = x % y;
39 x = y;
40 y = t;
41 } while (y);
42 return x;
43 }
44}
45*/
46
47//Modified version from "An Optimal In-Place Array Rotation Algorithm", Ching-Kuang Shene
48template<typename Unsigned>
49Unsigned gcd(Unsigned x, Unsigned y)
50{
51 if(0 == ((x &(x-1)) | (y & (y-1)))){
52 return x < y ? x : y;
53 }
54 else{
55 Unsigned z = 1;
56 while((!(x&1)) & (!(y&1))){
57 z <<=1, x>>=1, y>>=1;
58 }
59 while(x && y){
60 if(!(x&1))
61 x >>=1;
62 else if(!(y&1))
63 y >>=1;
64 else if(x >=y)
65 x = (x-y) >> 1;
66 else
67 y = (y-x) >> 1;
68 }
69 return z*(x+y);
70 }
71}
72
73template<typename RandIt>
74RandIt rotate_gcd(RandIt first, RandIt middle, RandIt last)
75{
76 typedef typename iterator_traits<RandIt>::size_type size_type;
77 typedef typename iterator_traits<RandIt>::value_type value_type;
78
79 if(first == middle)
80 return last;
81 if(middle == last)
82 return first;
83 const size_type middle_pos = size_type(middle - first);
84 RandIt ret = last - middle_pos;
85 if (middle == ret){
86 boost::adl_move_swap_ranges(first, middle, middle);
87 }
88 else{
89 const size_type length = size_type(last - first);
90 for( RandIt it_i(first), it_gcd(it_i + gcd(length, middle_pos))
91 ; it_i != it_gcd
92 ; ++it_i){
93 value_type temp(boost::move(*it_i));
94 RandIt it_j = it_i;
95 RandIt it_k = it_j+middle_pos;
96 do{
97 *it_j = boost::move(*it_k);
98 it_j = it_k;
99 size_type const left = size_type(last - it_j);
100 it_k = left > middle_pos ? it_j + middle_pos : first + (middle_pos - left);
101 } while(it_k != it_i);
102 *it_j = boost::move(temp);
103 }
104 }
105 return ret;
106}
107
108template <class RandIt, class T, class Compare>
109RandIt lower_bound
110 (RandIt first, const RandIt last, const T& key, Compare comp)
111{
112 typedef typename iterator_traits
113 <RandIt>::size_type size_type;
114 size_type len = size_type(last - first);
115 RandIt middle;
116
117 while (len) {
118 size_type step = len >> 1;
119 middle = first;
120 middle += step;
121
122 if (comp(*middle, key)) {
123 first = ++middle;
124 len -= step + 1;
125 }
126 else{
127 len = step;
128 }
129 }
130 return first;
131}
132
133template <class RandIt, class T, class Compare>
134RandIt upper_bound
135 (RandIt first, const RandIt last, const T& key, Compare comp)
136{
137 typedef typename iterator_traits
138 <RandIt>::size_type size_type;
139 size_type len = size_type(last - first);
140 RandIt middle;
141
142 while (len) {
143 size_type step = len >> 1;
144 middle = first;
145 middle += step;
146
147 if (!comp(key, *middle)) {
148 first = ++middle;
149 len -= step + 1;
150 }
151 else{
152 len = step;
153 }
154 }
155 return first;
156}
157
158
159template<class RandIt, class Compare, class Op>
160void op_merge_left( RandIt buf_first
161 , RandIt first1
162 , RandIt const last1
163 , RandIt const last2
164 , Compare comp
165 , Op op)
166{
167 for(RandIt first2=last1; first2 != last2; ++buf_first){
168 if(first1 == last1){
169 op(forward_t(), first2, last2, buf_first);
170 return;
171 }
172 else if(comp(*first2, *first1)){
173 op(first2, buf_first);
174 ++first2;
175 }
176 else{
177 op(first1, buf_first);
178 ++first1;
179 }
180 }
181 if(buf_first != first1){//In case all remaining elements are in the same place
182 //(e.g. buffer is exactly the size of the second half
183 //and all elements from the second half are less)
184 op(forward_t(), first1, last1, buf_first);
185 }
186}
187
188// [buf_first, first1) -> buffer
189// [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1))
190// Elements from buffer are moved to [last2 - (first1-buf_first), last2)
191// Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs
192template<class RandIt, class Compare>
193void merge_left
194 (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp)
195{
196 op_merge_left(buf_first, first1, last1, last2, comp, move_op());
197}
198
199// [buf_first, first1) -> buffer
200// [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1))
201// Elements from buffer are swapped to [last2 - (first1-buf_first), last2)
202// Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs
203template<class RandIt, class Compare>
204void swap_merge_left
205 (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp)
206{
207 op_merge_left(buf_first, first1, last1, last2, comp, swap_op());
208}
209
210template<class RandIt, class Compare, class Op>
211void op_merge_right
212 (RandIt const first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp, Op op)
213{
214 RandIt const first2 = last1;
215 while(first1 != last1){
216 if(last2 == first2){
217 op(backward_t(), first1, last1, buf_last);
218 return;
219 }
220 --last2;
221 --last1;
222 --buf_last;
223 if(comp(*last2, *last1)){
224 op(last1, buf_last);
225 ++last2;
226 }
227 else{
228 op(last2, buf_last);
229 ++last1;
230 }
231 }
232 if(last2 != buf_last){ //In case all remaining elements are in the same place
233 //(e.g. buffer is exactly the size of the first half
234 //and all elements from the second half are less)
235 op(backward_t(), first2, last2, buf_last);
236 }
237}
238
239// [last2, buf_last) - buffer
240// [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last)
241// Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs
242template<class RandIt, class Compare>
243void merge_right
244 (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp)
245{
246 op_merge_right(first1, last1, last2, buf_last, comp, move_op());
247}
248
249// [last2, buf_last) - buffer
250// [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last)
251// Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs
252template<class RandIt, class Compare>
253void swap_merge_right
254 (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp)
255{
256 op_merge_right(first1, last1, last2, buf_last, comp, swap_op());
257}
258
259template <class BidirIt, class Distance, class Compare>
260void merge_bufferless_ONlogN_recursive
261 (BidirIt first, BidirIt middle, BidirIt last, Distance len1, Distance len2, Compare comp)
262{
263 typedef typename iterator_traits<BidirIt>::size_type size_type;
264 while(1) {
265 //#define MERGE_BUFFERLESS_RECURSIVE_OPT
266 #ifndef MERGE_BUFFERLESS_RECURSIVE_OPT
267 if (len2 == 0) {
268 return;
269 }
270
271 if (!len1) {
272 return;
273 }
274
275 if ((len1 | len2) == 1) {
276 if (comp(*middle, *first))
277 adl_move_swap(*first, *middle);
278 return;
279 }
280 #else
281 if (len2 == 0) {
282 return;
283 }
284
285 if (!len1) {
286 return;
287 }
288 BidirIt middle_prev = middle; --middle_prev;
289 if(!comp(*middle, *middle_prev))
290 return;
291
292 while(true) {
293 if (comp(*middle, *first))
294 break;
295 ++first;
296 if(--len1 == 1)
297 break;
298 }
299
300 if (len1 == 1 && len2 == 1) {
301 //comp(*middle, *first) == true already tested in the loop
302 adl_move_swap(*first, *middle);
303 return;
304 }
305 #endif
306
307 BidirIt first_cut = first;
308 BidirIt second_cut = middle;
309 Distance len11 = 0;
310 Distance len22 = 0;
311 if (len1 > len2) {
312 len11 = len1 / 2;
313 first_cut += len11;
314 second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp);
315 len22 = size_type(second_cut - middle);
316 }
317 else {
318 len22 = len2 / 2;
319 second_cut += len22;
320 first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp);
321 len11 = size_type(first_cut - first);
322 }
323 BidirIt new_middle = rotate_gcd(first_cut, middle, second_cut);
324
325 //Avoid one recursive call doing a manual tail call elimination on the biggest range
326 const Distance len_internal = len11+len22;
327 if( len_internal < (len1 + len2 - len_internal) ) {
328 merge_bufferless_ONlogN_recursive(first, first_cut, new_middle, len11, len22, comp);
329 //merge_bufferless_recursive(new_middle, second_cut, last, len1 - len11, len2 - len22, comp);
330 first = new_middle;
331 middle = second_cut;
332 len1 -= len11;
333 len2 -= len22;
334 }
335 else {
336 //merge_bufferless_recursive(first, first_cut, new_middle, len11, len22, comp);
337 merge_bufferless_ONlogN_recursive(new_middle, second_cut, last, len1 - len11, len2 - len22, comp);
338 middle = first_cut;
339 last = new_middle;
340 len1 = len11;
341 len2 = len22;
342 }
343 }
344}
345
346//Complexity: NlogN
347template<class BidirIt, class Compare>
348void merge_bufferless_ONlogN(BidirIt first, BidirIt middle, BidirIt last, Compare comp)
349{
350 merge_bufferless_ONlogN_recursive
351 (first, middle, last, middle - first, last - middle, comp);
352}
353
354//Complexity: min(len1,len2)^2 + max(len1,len2)
355template<class RandIt, class Compare>
356void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp)
357{
358 if((middle - first) < (last - middle)){
359 while(first != middle){
360 RandIt const old_last1 = middle;
361 middle = boost::movelib::lower_bound(middle, last, *first, comp);
362 first = rotate_gcd(first, old_last1, middle);
363 if(middle == last){
364 break;
365 }
366 do{
367 ++first;
368 } while(first != middle && !comp(*middle, *first));
369 }
370 }
371 else{
372 while(middle != last){
373 RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp);
374 last = rotate_gcd(p, middle, last);
375 middle = p;
376 if(middle == first){
377 break;
378 }
379 --p;
380 do{
381 --last;
382 } while(middle != last && !comp(last[-1], *p));
383 }
384 }
385}
386
387template<class RandIt, class Compare>
388void merge_bufferless(RandIt first, RandIt middle, RandIt last, Compare comp)
389{
390 //#define BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
391 #ifdef BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
392 merge_bufferless_ONlogN(first, middle, last, comp);
393 #else
394 merge_bufferless_ON2(first, middle, last, comp);
395 #endif //BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
396}
397
398// [r_first, r_last) are already in the right part of the destination range.
399template <class Compare, class InputIterator, class InputOutIterator, class Op>
400void op_merge_with_right_placed
401 ( InputIterator first, InputIterator last
402 , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
403 , Compare comp, Op op)
404{
405 BOOST_ASSERT((last - first) == (r_first - dest_first));
406 while ( first != last ) {
407 if (r_first == r_last) {
408 InputOutIterator end = op(forward_t(), first, last, dest_first);
409 BOOST_ASSERT(end == r_last);
410 (void)end;
411 return;
412 }
413 else if (comp(*r_first, *first)) {
414 op(r_first, dest_first);
415 ++r_first;
416 }
417 else {
418 op(first, dest_first);
419 ++first;
420 }
421 ++dest_first;
422 }
423 // Remaining [r_first, r_last) already in the correct place
424}
425
426template <class Compare, class InputIterator, class InputOutIterator>
427void swap_merge_with_right_placed
428 ( InputIterator first, InputIterator last
429 , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
430 , Compare comp)
431{
432 op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, swap_op());
433}
434
435// [first, last) are already in the right part of the destination range.
436template <class Compare, class Op, class BidirIterator, class BidirOutIterator>
437void op_merge_with_left_placed
438 ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last
439 , BidirIterator const r_first, BidirIterator r_last
440 , Compare comp, Op op)
441{
442 BOOST_ASSERT((dest_last - last) == (r_last - r_first));
443 while( r_first != r_last ) {
444 if(first == last) {
445 BidirOutIterator res = op(backward_t(), r_first, r_last, dest_last);
446 BOOST_ASSERT(last == res);
447 (void)res;
448 return;
449 }
450 --r_last;
451 --last;
452 if(comp(*r_last, *last)){
453 ++r_last;
454 --dest_last;
455 op(last, dest_last);
456 }
457 else{
458 ++last;
459 --dest_last;
460 op(r_last, dest_last);
461 }
462 }
463 // Remaining [first, last) already in the correct place
464}
465
466// @endcond
467
468// [irst, last) are already in the right part of the destination range.
469template <class Compare, class BidirIterator, class BidirOutIterator>
470void merge_with_left_placed
471 ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last
472 , BidirIterator const r_first, BidirIterator r_last
473 , Compare comp)
474{
475 op_merge_with_left_placed(first, last, dest_last, r_first, r_last, comp, move_op());
476}
477
478// [r_first, r_last) are already in the right part of the destination range.
479template <class Compare, class InputIterator, class InputOutIterator>
480void merge_with_right_placed
481 ( InputIterator first, InputIterator last
482 , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
483 , Compare comp)
484{
485 op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, move_op());
486}
487
488// [r_first, r_last) are already in the right part of the destination range.
489// [dest_first, r_first) is uninitialized memory
490template <class Compare, class InputIterator, class InputOutIterator>
491void uninitialized_merge_with_right_placed
492 ( InputIterator first, InputIterator last
493 , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
494 , Compare comp)
495{
496 BOOST_ASSERT((last - first) == (r_first - dest_first));
497 typedef typename iterator_traits<InputOutIterator>::value_type value_type;
498 InputOutIterator const original_r_first = r_first;
499
500 destruct_n<value_type, InputOutIterator> d(dest_first);
501
502 while ( first != last && dest_first != original_r_first ) {
503 if (r_first == r_last) {
504 for(; dest_first != original_r_first; ++dest_first, ++first){
505 ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first));
506 d.incr();
507 }
508 d.release();
509 InputOutIterator end = ::boost::move(first, last, original_r_first);
510 BOOST_ASSERT(end == r_last);
511 (void)end;
512 return;
513 }
514 else if (comp(*r_first, *first)) {
515 ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*r_first));
516 d.incr();
517 ++r_first;
518 }
519 else {
520 ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first));
521 d.incr();
522 ++first;
523 }
524 ++dest_first;
525 }
526 d.release();
527 merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp);
528}
529
530/*
531// [r_first, r_last) are already in the right part of the destination range.
532// [dest_first, r_first) is uninitialized memory
533template <class Compare, class BidirOutIterator, class BidirIterator>
534void uninitialized_merge_with_left_placed
535 ( BidirOutIterator dest_first, BidirOutIterator r_first, BidirOutIterator r_last
536 , BidirIterator first, BidirIterator last
537 , Compare comp)
538{
539 BOOST_ASSERT((last - first) == (r_last - r_first));
540 typedef typename iterator_traits<BidirOutIterator>::value_type value_type;
541 BidirOutIterator const original_r_last = r_last;
542
543 destruct_n<value_type> d(&*dest_last);
544
545 while ( first != last && dest_first != original_r_first ) {
546 if (r_first == r_last) {
547 for(; dest_first != original_r_first; ++dest_first, ++first){
548 ::new(&*dest_first) value_type(::boost::move(*first));
549 d.incr();
550 }
551 d.release();
552 BidirOutIterator end = ::boost::move(first, last, original_r_first);
553 BOOST_ASSERT(end == r_last);
554 (void)end;
555 return;
556 }
557 else if (comp(*r_first, *first)) {
558 ::new(&*dest_first) value_type(::boost::move(*r_first));
559 d.incr();
560 ++r_first;
561 }
562 else {
563 ::new(&*dest_first) value_type(::boost::move(*first));
564 d.incr();
565 ++first;
566 }
567 ++dest_first;
568 }
569 d.release();
570 merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp);
571}
572*/
573
574} //namespace movelib {
575} //namespace boost {
576
577#endif //#define BOOST_MOVE_MERGE_HPP
578