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