]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
b32b8144 FG |
19 | #include <boost/move/algo/predicate.hpp> |
20 | #include <boost/move/detail/iterator_to_raw_pointer.hpp> | |
7c673cae FG |
21 | #include <boost/assert.hpp> |
22 | ||
23 | namespace boost { | |
24 | namespace movelib { | |
25 | ||
26 | // @cond | |
27 | ||
28 | /* | |
29 | template<typename Unsigned> | |
30 | inline 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 | |
48 | template<typename Unsigned> | |
49 | Unsigned 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 | ||
73 | template<typename RandIt> | |
74 | RandIt 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 | ||
108 | template <class RandIt, class T, class Compare> | |
109 | RandIt 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 | ||
133 | template <class RandIt, class T, class Compare> | |
134 | RandIt 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 | ||
159 | template<class RandIt, class Compare, class Op> | |
160 | void 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 | } | |
7c673cae FG |
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 | |
192 | template<class RandIt, class Compare> | |
193 | void 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 | |
203 | template<class RandIt, class Compare> | |
204 | void 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 | ||
210 | template<class RandIt, class Compare, class Op> | |
211 | void 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 | |
242 | template<class RandIt, class Compare> | |
243 | void 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 | |
252 | template<class RandIt, class Compare> | |
253 | void 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 | ||
11fdf7f2 TL |
259 | //Complexity: min(len1,len2)^2 + max(len1,len2) |
260 | template<class RandIt, class Compare> | |
261 | void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp) | |
262 | { | |
263 | if((middle - first) < (last - middle)){ | |
264 | while(first != middle){ | |
265 | RandIt const old_last1 = middle; | |
266 | middle = boost::movelib::lower_bound(middle, last, *first, comp); | |
267 | first = rotate_gcd(first, old_last1, middle); | |
268 | if(middle == last){ | |
269 | break; | |
270 | } | |
271 | do{ | |
272 | ++first; | |
273 | } while(first != middle && !comp(*middle, *first)); | |
274 | } | |
275 | } | |
276 | else{ | |
277 | while(middle != last){ | |
278 | RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp); | |
279 | last = rotate_gcd(p, middle, last); | |
280 | middle = p; | |
281 | if(middle == first){ | |
282 | break; | |
283 | } | |
284 | --p; | |
285 | do{ | |
286 | --last; | |
287 | } while(middle != last && !comp(last[-1], *p)); | |
288 | } | |
289 | } | |
290 | } | |
291 | ||
292 | static const std::size_t MergeBufferlessONLogNRotationThreshold = 32; | |
293 | ||
294 | template <class RandIt, class Distance, class Compare> | |
7c673cae | 295 | void merge_bufferless_ONlogN_recursive |
11fdf7f2 | 296 | (RandIt first, RandIt middle, RandIt last, Distance len1, Distance len2, Compare comp) |
7c673cae | 297 | { |
11fdf7f2 TL |
298 | typedef typename iterator_traits<RandIt>::size_type size_type; |
299 | ||
7c673cae | 300 | while(1) { |
11fdf7f2 TL |
301 | //trivial cases |
302 | if (!len2) { | |
7c673cae FG |
303 | return; |
304 | } | |
11fdf7f2 | 305 | else if (!len1) { |
7c673cae FG |
306 | return; |
307 | } | |
11fdf7f2 | 308 | else if (size_type(len1 | len2) == 1u) { |
7c673cae FG |
309 | if (comp(*middle, *first)) |
310 | adl_move_swap(*first, *middle); | |
311 | return; | |
312 | } | |
11fdf7f2 TL |
313 | else if(size_type(len1+len2) < MergeBufferlessONLogNRotationThreshold){ |
314 | merge_bufferless_ON2(first, middle, last, comp); | |
7c673cae | 315 | return; |
7c673cae FG |
316 | } |
317 | ||
11fdf7f2 TL |
318 | RandIt first_cut = first; |
319 | RandIt second_cut = middle; | |
7c673cae FG |
320 | Distance len11 = 0; |
321 | Distance len22 = 0; | |
322 | if (len1 > len2) { | |
323 | len11 = len1 / 2; | |
324 | first_cut += len11; | |
b32b8144 | 325 | second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp); |
7c673cae FG |
326 | len22 = size_type(second_cut - middle); |
327 | } | |
328 | else { | |
329 | len22 = len2 / 2; | |
330 | second_cut += len22; | |
b32b8144 | 331 | first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp); |
7c673cae FG |
332 | len11 = size_type(first_cut - first); |
333 | } | |
11fdf7f2 | 334 | RandIt new_middle = rotate_gcd(first_cut, middle, second_cut); |
7c673cae FG |
335 | |
336 | //Avoid one recursive call doing a manual tail call elimination on the biggest range | |
337 | const Distance len_internal = len11+len22; | |
338 | if( len_internal < (len1 + len2 - len_internal) ) { | |
339 | merge_bufferless_ONlogN_recursive(first, first_cut, new_middle, len11, len22, comp); | |
7c673cae FG |
340 | first = new_middle; |
341 | middle = second_cut; | |
342 | len1 -= len11; | |
343 | len2 -= len22; | |
344 | } | |
345 | else { | |
7c673cae FG |
346 | merge_bufferless_ONlogN_recursive(new_middle, second_cut, last, len1 - len11, len2 - len22, comp); |
347 | middle = first_cut; | |
348 | last = new_middle; | |
349 | len1 = len11; | |
350 | len2 = len22; | |
351 | } | |
352 | } | |
353 | } | |
354 | ||
355 | //Complexity: NlogN | |
11fdf7f2 TL |
356 | template<class RandIt, class Compare> |
357 | void merge_bufferless_ONlogN(RandIt first, RandIt middle, RandIt last, Compare comp) | |
7c673cae FG |
358 | { |
359 | merge_bufferless_ONlogN_recursive | |
360 | (first, middle, last, middle - first, last - middle, comp); | |
361 | } | |
362 | ||
7c673cae FG |
363 | template<class RandIt, class Compare> |
364 | void merge_bufferless(RandIt first, RandIt middle, RandIt last, Compare comp) | |
365 | { | |
11fdf7f2 | 366 | #define BOOST_ADAPTIVE_MERGE_NLOGN_MERGE |
7c673cae FG |
367 | #ifdef BOOST_ADAPTIVE_MERGE_NLOGN_MERGE |
368 | merge_bufferless_ONlogN(first, middle, last, comp); | |
369 | #else | |
370 | merge_bufferless_ON2(first, middle, last, comp); | |
371 | #endif //BOOST_ADAPTIVE_MERGE_NLOGN_MERGE | |
372 | } | |
373 | ||
7c673cae FG |
374 | // [r_first, r_last) are already in the right part of the destination range. |
375 | template <class Compare, class InputIterator, class InputOutIterator, class Op> | |
376 | void op_merge_with_right_placed | |
377 | ( InputIterator first, InputIterator last | |
378 | , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last | |
379 | , Compare comp, Op op) | |
380 | { | |
381 | BOOST_ASSERT((last - first) == (r_first - dest_first)); | |
382 | while ( first != last ) { | |
383 | if (r_first == r_last) { | |
384 | InputOutIterator end = op(forward_t(), first, last, dest_first); | |
385 | BOOST_ASSERT(end == r_last); | |
386 | (void)end; | |
387 | return; | |
388 | } | |
389 | else if (comp(*r_first, *first)) { | |
390 | op(r_first, dest_first); | |
391 | ++r_first; | |
392 | } | |
393 | else { | |
394 | op(first, dest_first); | |
395 | ++first; | |
396 | } | |
397 | ++dest_first; | |
398 | } | |
399 | // Remaining [r_first, r_last) already in the correct place | |
400 | } | |
401 | ||
402 | template <class Compare, class InputIterator, class InputOutIterator> | |
403 | void swap_merge_with_right_placed | |
404 | ( InputIterator first, InputIterator last | |
405 | , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last | |
406 | , Compare comp) | |
407 | { | |
408 | op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, swap_op()); | |
409 | } | |
410 | ||
b32b8144 | 411 | // [first, last) are already in the right part of the destination range. |
7c673cae FG |
412 | template <class Compare, class Op, class BidirIterator, class BidirOutIterator> |
413 | void op_merge_with_left_placed | |
414 | ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last | |
415 | , BidirIterator const r_first, BidirIterator r_last | |
416 | , Compare comp, Op op) | |
417 | { | |
418 | BOOST_ASSERT((dest_last - last) == (r_last - r_first)); | |
419 | while( r_first != r_last ) { | |
420 | if(first == last) { | |
421 | BidirOutIterator res = op(backward_t(), r_first, r_last, dest_last); | |
422 | BOOST_ASSERT(last == res); | |
423 | (void)res; | |
424 | return; | |
425 | } | |
426 | --r_last; | |
427 | --last; | |
428 | if(comp(*r_last, *last)){ | |
429 | ++r_last; | |
430 | --dest_last; | |
431 | op(last, dest_last); | |
432 | } | |
433 | else{ | |
434 | ++last; | |
435 | --dest_last; | |
436 | op(r_last, dest_last); | |
437 | } | |
438 | } | |
439 | // Remaining [first, last) already in the correct place | |
440 | } | |
441 | ||
442 | // @endcond | |
443 | ||
b32b8144 | 444 | // [irst, last) are already in the right part of the destination range. |
7c673cae FG |
445 | template <class Compare, class BidirIterator, class BidirOutIterator> |
446 | void merge_with_left_placed | |
447 | ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last | |
448 | , BidirIterator const r_first, BidirIterator r_last | |
449 | , Compare comp) | |
450 | { | |
451 | op_merge_with_left_placed(first, last, dest_last, r_first, r_last, comp, move_op()); | |
452 | } | |
453 | ||
454 | // [r_first, r_last) are already in the right part of the destination range. | |
455 | template <class Compare, class InputIterator, class InputOutIterator> | |
456 | void merge_with_right_placed | |
457 | ( InputIterator first, InputIterator last | |
458 | , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last | |
459 | , Compare comp) | |
460 | { | |
461 | op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, move_op()); | |
462 | } | |
463 | ||
464 | // [r_first, r_last) are already in the right part of the destination range. | |
465 | // [dest_first, r_first) is uninitialized memory | |
466 | template <class Compare, class InputIterator, class InputOutIterator> | |
467 | void uninitialized_merge_with_right_placed | |
468 | ( InputIterator first, InputIterator last | |
469 | , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last | |
470 | , Compare comp) | |
471 | { | |
472 | BOOST_ASSERT((last - first) == (r_first - dest_first)); | |
473 | typedef typename iterator_traits<InputOutIterator>::value_type value_type; | |
474 | InputOutIterator const original_r_first = r_first; | |
475 | ||
b32b8144 | 476 | destruct_n<value_type, InputOutIterator> d(dest_first); |
7c673cae FG |
477 | |
478 | while ( first != last && dest_first != original_r_first ) { | |
479 | if (r_first == r_last) { | |
480 | for(; dest_first != original_r_first; ++dest_first, ++first){ | |
b32b8144 | 481 | ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first)); |
7c673cae FG |
482 | d.incr(); |
483 | } | |
484 | d.release(); | |
485 | InputOutIterator end = ::boost::move(first, last, original_r_first); | |
486 | BOOST_ASSERT(end == r_last); | |
487 | (void)end; | |
488 | return; | |
489 | } | |
b32b8144 FG |
490 | else if (comp(*r_first, *first)) { |
491 | ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*r_first)); | |
492 | d.incr(); | |
493 | ++r_first; | |
494 | } | |
495 | else { | |
496 | ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first)); | |
497 | d.incr(); | |
498 | ++first; | |
499 | } | |
500 | ++dest_first; | |
501 | } | |
502 | d.release(); | |
503 | merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp); | |
504 | } | |
505 | ||
506 | /* | |
507 | // [r_first, r_last) are already in the right part of the destination range. | |
508 | // [dest_first, r_first) is uninitialized memory | |
509 | template <class Compare, class BidirOutIterator, class BidirIterator> | |
510 | void uninitialized_merge_with_left_placed | |
511 | ( BidirOutIterator dest_first, BidirOutIterator r_first, BidirOutIterator r_last | |
512 | , BidirIterator first, BidirIterator last | |
513 | , Compare comp) | |
514 | { | |
515 | BOOST_ASSERT((last - first) == (r_last - r_first)); | |
516 | typedef typename iterator_traits<BidirOutIterator>::value_type value_type; | |
517 | BidirOutIterator const original_r_last = r_last; | |
518 | ||
519 | destruct_n<value_type> d(&*dest_last); | |
520 | ||
521 | while ( first != last && dest_first != original_r_first ) { | |
522 | if (r_first == r_last) { | |
523 | for(; dest_first != original_r_first; ++dest_first, ++first){ | |
524 | ::new(&*dest_first) value_type(::boost::move(*first)); | |
525 | d.incr(); | |
526 | } | |
527 | d.release(); | |
528 | BidirOutIterator end = ::boost::move(first, last, original_r_first); | |
529 | BOOST_ASSERT(end == r_last); | |
530 | (void)end; | |
531 | return; | |
532 | } | |
7c673cae FG |
533 | else if (comp(*r_first, *first)) { |
534 | ::new(&*dest_first) value_type(::boost::move(*r_first)); | |
535 | d.incr(); | |
536 | ++r_first; | |
537 | } | |
538 | else { | |
539 | ::new(&*dest_first) value_type(::boost::move(*first)); | |
540 | d.incr(); | |
541 | ++first; | |
542 | } | |
543 | ++dest_first; | |
544 | } | |
545 | d.release(); | |
546 | merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp); | |
547 | } | |
b32b8144 | 548 | */ |
7c673cae FG |
549 | |
550 | } //namespace movelib { | |
551 | } //namespace boost { | |
552 | ||
553 | #endif //#define BOOST_MOVE_MERGE_HPP |