]>
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 | ||
20effc67 | 14 | #include <boost/core/ignore_unused.hpp> |
7c673cae FG |
15 | #include <boost/move/algo/move.hpp> |
16 | #include <boost/move/adl_move_swap.hpp> | |
17 | #include <boost/move/algo/detail/basic_op.hpp> | |
18 | #include <boost/move/detail/iterator_traits.hpp> | |
19 | #include <boost/move/detail/destruct_n.hpp> | |
b32b8144 FG |
20 | #include <boost/move/algo/predicate.hpp> |
21 | #include <boost/move/detail/iterator_to_raw_pointer.hpp> | |
7c673cae | 22 | #include <boost/assert.hpp> |
92f5a8d4 | 23 | #include <cstddef> |
7c673cae | 24 | |
1e59de90 TL |
25 | #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600)) |
26 | #pragma GCC diagnostic push | |
27 | #pragma GCC diagnostic ignored "-Wsign-conversion" | |
28 | #endif | |
29 | ||
7c673cae FG |
30 | namespace boost { |
31 | namespace movelib { | |
32 | ||
1e59de90 | 33 | template<class T, class RandRawIt = T*, class SizeType = typename iter_size<RandRawIt>::type> |
92f5a8d4 TL |
34 | class adaptive_xbuf |
35 | { | |
36 | adaptive_xbuf(const adaptive_xbuf &); | |
37 | adaptive_xbuf & operator=(const adaptive_xbuf &); | |
38 | ||
39 | #if !defined(UINTPTR_MAX) | |
40 | typedef std::size_t uintptr_t; | |
41 | #endif | |
42 | ||
43 | public: | |
44 | typedef RandRawIt iterator; | |
45 | typedef SizeType size_type; | |
46 | ||
1e59de90 | 47 | BOOST_MOVE_FORCEINLINE adaptive_xbuf() |
92f5a8d4 TL |
48 | : m_ptr(), m_size(0), m_capacity(0) |
49 | {} | |
50 | ||
1e59de90 TL |
51 | BOOST_MOVE_FORCEINLINE adaptive_xbuf(RandRawIt raw_memory, size_type cap) |
52 | : m_ptr(raw_memory), m_size(0), m_capacity(cap) | |
92f5a8d4 TL |
53 | {} |
54 | ||
55 | template<class RandIt> | |
56 | void move_assign(RandIt first, size_type n) | |
57 | { | |
1e59de90 | 58 | typedef typename iterator_traits<RandIt>::difference_type rand_diff_t; |
92f5a8d4 | 59 | if(n <= m_size){ |
1e59de90 TL |
60 | boost::move(first, first+rand_diff_t(n), m_ptr); |
61 | size_type sz = m_size; | |
62 | while(sz-- != n){ | |
63 | m_ptr[sz].~T(); | |
92f5a8d4 TL |
64 | } |
65 | m_size = n; | |
66 | } | |
67 | else{ | |
1e59de90 TL |
68 | RandRawIt result = boost::move(first, first+rand_diff_t(m_size), m_ptr); |
69 | boost::uninitialized_move(first+rand_diff_t(m_size), first+rand_diff_t(n), result); | |
92f5a8d4 TL |
70 | m_size = n; |
71 | } | |
72 | } | |
73 | ||
74 | template<class RandIt> | |
75 | void push_back(RandIt first, size_type n) | |
76 | { | |
77 | BOOST_ASSERT(m_capacity - m_size >= n); | |
78 | boost::uninitialized_move(first, first+n, m_ptr+m_size); | |
79 | m_size += n; | |
80 | } | |
81 | ||
82 | template<class RandIt> | |
83 | iterator add(RandIt it) | |
84 | { | |
85 | BOOST_ASSERT(m_size < m_capacity); | |
86 | RandRawIt p_ret = m_ptr + m_size; | |
87 | ::new(&*p_ret) T(::boost::move(*it)); | |
88 | ++m_size; | |
89 | return p_ret; | |
90 | } | |
91 | ||
92 | template<class RandIt> | |
93 | void insert(iterator pos, RandIt it) | |
94 | { | |
95 | if(pos == (m_ptr + m_size)){ | |
96 | this->add(it); | |
97 | } | |
98 | else{ | |
99 | this->add(m_ptr+m_size-1); | |
100 | //m_size updated | |
101 | boost::move_backward(pos, m_ptr+m_size-2, m_ptr+m_size-1); | |
102 | *pos = boost::move(*it); | |
103 | } | |
104 | } | |
105 | ||
1e59de90 | 106 | BOOST_MOVE_FORCEINLINE void set_size(size_type sz) |
92f5a8d4 | 107 | { |
1e59de90 | 108 | m_size = sz; |
92f5a8d4 TL |
109 | } |
110 | ||
1e59de90 | 111 | void shrink_to_fit(size_type const sz) |
92f5a8d4 | 112 | { |
1e59de90 TL |
113 | if(m_size > sz){ |
114 | for(size_type szt_i = sz; szt_i != m_size; ++szt_i){ | |
92f5a8d4 TL |
115 | m_ptr[szt_i].~T(); |
116 | } | |
1e59de90 | 117 | m_size = sz; |
92f5a8d4 TL |
118 | } |
119 | } | |
120 | ||
1e59de90 | 121 | void initialize_until(size_type const sz, T &t) |
92f5a8d4 TL |
122 | { |
123 | BOOST_ASSERT(m_size < m_capacity); | |
1e59de90 | 124 | if(m_size < sz){ |
92f5a8d4 TL |
125 | BOOST_TRY |
126 | { | |
127 | ::new((void*)&m_ptr[m_size]) T(::boost::move(t)); | |
128 | ++m_size; | |
1e59de90 | 129 | for(; m_size != sz; ++m_size){ |
92f5a8d4 TL |
130 | ::new((void*)&m_ptr[m_size]) T(::boost::move(m_ptr[m_size-1])); |
131 | } | |
132 | t = ::boost::move(m_ptr[m_size-1]); | |
133 | } | |
134 | BOOST_CATCH(...) | |
135 | { | |
136 | while(m_size) | |
137 | { | |
138 | --m_size; | |
139 | m_ptr[m_size].~T(); | |
140 | } | |
141 | } | |
142 | BOOST_CATCH_END | |
143 | } | |
144 | } | |
145 | ||
146 | private: | |
147 | template<class RIt> | |
1e59de90 | 148 | BOOST_MOVE_FORCEINLINE static bool is_raw_ptr(RIt) |
92f5a8d4 TL |
149 | { |
150 | return false; | |
151 | } | |
152 | ||
1e59de90 | 153 | BOOST_MOVE_FORCEINLINE static bool is_raw_ptr(T*) |
92f5a8d4 TL |
154 | { |
155 | return true; | |
156 | } | |
157 | ||
158 | public: | |
159 | template<class U> | |
1e59de90 | 160 | bool supports_aligned_trailing(size_type sz, size_type trail_count) const |
92f5a8d4 TL |
161 | { |
162 | if(this->is_raw_ptr(this->data()) && m_capacity){ | |
1e59de90 | 163 | uintptr_t u_addr_sz = uintptr_t(&*(this->data()+sz)); |
92f5a8d4 TL |
164 | uintptr_t u_addr_cp = uintptr_t(&*(this->data()+this->capacity())); |
165 | u_addr_sz = ((u_addr_sz + sizeof(U)-1)/sizeof(U))*sizeof(U); | |
166 | return (u_addr_cp >= u_addr_sz) && ((u_addr_cp - u_addr_sz)/sizeof(U) >= trail_count); | |
167 | } | |
168 | return false; | |
169 | } | |
170 | ||
171 | template<class U> | |
1e59de90 | 172 | BOOST_MOVE_FORCEINLINE U *aligned_trailing() const |
92f5a8d4 TL |
173 | { |
174 | return this->aligned_trailing<U>(this->size()); | |
175 | } | |
176 | ||
177 | template<class U> | |
1e59de90 | 178 | BOOST_MOVE_FORCEINLINE U *aligned_trailing(size_type pos) const |
92f5a8d4 TL |
179 | { |
180 | uintptr_t u_addr = uintptr_t(&*(this->data()+pos)); | |
181 | u_addr = ((u_addr + sizeof(U)-1)/sizeof(U))*sizeof(U); | |
182 | return (U*)u_addr; | |
183 | } | |
184 | ||
1e59de90 | 185 | BOOST_MOVE_FORCEINLINE ~adaptive_xbuf() |
92f5a8d4 TL |
186 | { |
187 | this->clear(); | |
188 | } | |
189 | ||
1e59de90 | 190 | BOOST_MOVE_FORCEINLINE size_type capacity() const |
92f5a8d4 TL |
191 | { return m_capacity; } |
192 | ||
1e59de90 | 193 | BOOST_MOVE_FORCEINLINE iterator data() const |
92f5a8d4 TL |
194 | { return m_ptr; } |
195 | ||
1e59de90 | 196 | BOOST_MOVE_FORCEINLINE iterator begin() const |
92f5a8d4 TL |
197 | { return m_ptr; } |
198 | ||
1e59de90 | 199 | BOOST_MOVE_FORCEINLINE iterator end() const |
92f5a8d4 TL |
200 | { return m_ptr+m_size; } |
201 | ||
1e59de90 | 202 | BOOST_MOVE_FORCEINLINE size_type size() const |
92f5a8d4 TL |
203 | { return m_size; } |
204 | ||
1e59de90 | 205 | BOOST_MOVE_FORCEINLINE bool empty() const |
92f5a8d4 TL |
206 | { return !m_size; } |
207 | ||
1e59de90 | 208 | BOOST_MOVE_FORCEINLINE void clear() |
92f5a8d4 TL |
209 | { |
210 | this->shrink_to_fit(0u); | |
211 | } | |
212 | ||
213 | private: | |
214 | RandRawIt m_ptr; | |
215 | size_type m_size; | |
216 | size_type m_capacity; | |
217 | }; | |
218 | ||
219 | template<class Iterator, class SizeType, class Op> | |
220 | class range_xbuf | |
221 | { | |
222 | range_xbuf(const range_xbuf &); | |
223 | range_xbuf & operator=(const range_xbuf &); | |
224 | ||
225 | public: | |
226 | typedef SizeType size_type; | |
227 | typedef Iterator iterator; | |
228 | ||
229 | range_xbuf(Iterator first, Iterator last) | |
230 | : m_first(first), m_last(first), m_cap(last) | |
231 | {} | |
232 | ||
233 | template<class RandIt> | |
234 | void move_assign(RandIt first, size_type n) | |
235 | { | |
236 | BOOST_ASSERT(size_type(n) <= size_type(m_cap-m_first)); | |
1e59de90 TL |
237 | typedef typename iter_difference<RandIt>::type d_type; |
238 | m_last = Op()(forward_t(), first, first+d_type(n), m_first); | |
92f5a8d4 TL |
239 | } |
240 | ||
241 | ~range_xbuf() | |
242 | {} | |
243 | ||
244 | size_type capacity() const | |
245 | { return m_cap-m_first; } | |
246 | ||
247 | Iterator data() const | |
248 | { return m_first; } | |
249 | ||
250 | Iterator end() const | |
251 | { return m_last; } | |
252 | ||
253 | size_type size() const | |
254 | { return m_last-m_first; } | |
255 | ||
256 | bool empty() const | |
257 | { return m_first == m_last; } | |
258 | ||
259 | void clear() | |
260 | { | |
261 | m_last = m_first; | |
262 | } | |
263 | ||
264 | template<class RandIt> | |
265 | iterator add(RandIt it) | |
266 | { | |
267 | Iterator pos(m_last); | |
268 | *pos = boost::move(*it); | |
269 | ++m_last; | |
270 | return pos; | |
271 | } | |
272 | ||
1e59de90 | 273 | void set_size(size_type sz) |
92f5a8d4 TL |
274 | { |
275 | m_last = m_first; | |
1e59de90 | 276 | m_last += sz; |
92f5a8d4 TL |
277 | } |
278 | ||
279 | private: | |
280 | Iterator const m_first; | |
281 | Iterator m_last; | |
282 | Iterator const m_cap; | |
283 | }; | |
284 | ||
285 | ||
286 | ||
7c673cae FG |
287 | // @cond |
288 | ||
289 | /* | |
290 | template<typename Unsigned> | |
291 | inline Unsigned gcd(Unsigned x, Unsigned y) | |
292 | { | |
293 | if(0 == ((x &(x-1)) | (y & (y-1)))){ | |
294 | return x < y ? x : y; | |
295 | } | |
296 | else{ | |
297 | do | |
298 | { | |
299 | Unsigned t = x % y; | |
300 | x = y; | |
301 | y = t; | |
302 | } while (y); | |
303 | return x; | |
304 | } | |
305 | } | |
306 | */ | |
307 | ||
308 | //Modified version from "An Optimal In-Place Array Rotation Algorithm", Ching-Kuang Shene | |
309 | template<typename Unsigned> | |
310 | Unsigned gcd(Unsigned x, Unsigned y) | |
311 | { | |
312 | if(0 == ((x &(x-1)) | (y & (y-1)))){ | |
313 | return x < y ? x : y; | |
314 | } | |
315 | else{ | |
316 | Unsigned z = 1; | |
317 | while((!(x&1)) & (!(y&1))){ | |
1e59de90 TL |
318 | z = Unsigned(z << 1); |
319 | x = Unsigned(x >> 1); | |
320 | y = Unsigned(y >> 1); | |
7c673cae FG |
321 | } |
322 | while(x && y){ | |
323 | if(!(x&1)) | |
1e59de90 | 324 | x = Unsigned(x >> 1); |
7c673cae | 325 | else if(!(y&1)) |
1e59de90 | 326 | y = Unsigned (y >> 1); |
7c673cae | 327 | else if(x >=y) |
1e59de90 | 328 | x = Unsigned((x-y) >> 1u); |
7c673cae | 329 | else |
1e59de90 | 330 | y = Unsigned((y-x) >> 1); |
7c673cae | 331 | } |
1e59de90 | 332 | return Unsigned(z*(x+y)); |
7c673cae FG |
333 | } |
334 | } | |
335 | ||
336 | template<typename RandIt> | |
337 | RandIt rotate_gcd(RandIt first, RandIt middle, RandIt last) | |
338 | { | |
1e59de90 | 339 | typedef typename iter_size<RandIt>::type size_type; |
7c673cae FG |
340 | typedef typename iterator_traits<RandIt>::value_type value_type; |
341 | ||
342 | if(first == middle) | |
343 | return last; | |
344 | if(middle == last) | |
345 | return first; | |
346 | const size_type middle_pos = size_type(middle - first); | |
347 | RandIt ret = last - middle_pos; | |
348 | if (middle == ret){ | |
349 | boost::adl_move_swap_ranges(first, middle, middle); | |
350 | } | |
351 | else{ | |
352 | const size_type length = size_type(last - first); | |
353 | for( RandIt it_i(first), it_gcd(it_i + gcd(length, middle_pos)) | |
354 | ; it_i != it_gcd | |
355 | ; ++it_i){ | |
356 | value_type temp(boost::move(*it_i)); | |
357 | RandIt it_j = it_i; | |
358 | RandIt it_k = it_j+middle_pos; | |
359 | do{ | |
360 | *it_j = boost::move(*it_k); | |
361 | it_j = it_k; | |
362 | size_type const left = size_type(last - it_j); | |
1e59de90 | 363 | it_k = left > middle_pos ? it_j + middle_pos : first + middle_pos - left; |
7c673cae FG |
364 | } while(it_k != it_i); |
365 | *it_j = boost::move(temp); | |
366 | } | |
367 | } | |
368 | return ret; | |
369 | } | |
370 | ||
371 | template <class RandIt, class T, class Compare> | |
372 | RandIt lower_bound | |
373 | (RandIt first, const RandIt last, const T& key, Compare comp) | |
374 | { | |
1e59de90 | 375 | typedef typename iter_size<RandIt>::type size_type; |
7c673cae FG |
376 | size_type len = size_type(last - first); |
377 | RandIt middle; | |
378 | ||
379 | while (len) { | |
1e59de90 | 380 | size_type step = size_type(len >> 1); |
7c673cae FG |
381 | middle = first; |
382 | middle += step; | |
383 | ||
384 | if (comp(*middle, key)) { | |
385 | first = ++middle; | |
1e59de90 | 386 | len = size_type(len - (step + 1)); |
7c673cae FG |
387 | } |
388 | else{ | |
389 | len = step; | |
390 | } | |
391 | } | |
392 | return first; | |
393 | } | |
394 | ||
395 | template <class RandIt, class T, class Compare> | |
396 | RandIt upper_bound | |
397 | (RandIt first, const RandIt last, const T& key, Compare comp) | |
398 | { | |
1e59de90 | 399 | typedef typename iter_size<RandIt>::type size_type; |
7c673cae FG |
400 | size_type len = size_type(last - first); |
401 | RandIt middle; | |
402 | ||
403 | while (len) { | |
1e59de90 | 404 | size_type step = size_type(len >> 1); |
7c673cae FG |
405 | middle = first; |
406 | middle += step; | |
407 | ||
408 | if (!comp(key, *middle)) { | |
409 | first = ++middle; | |
1e59de90 | 410 | len = size_type(len - (step + 1)); |
7c673cae FG |
411 | } |
412 | else{ | |
413 | len = step; | |
414 | } | |
415 | } | |
416 | return first; | |
417 | } | |
418 | ||
419 | ||
420 | template<class RandIt, class Compare, class Op> | |
421 | void op_merge_left( RandIt buf_first | |
422 | , RandIt first1 | |
423 | , RandIt const last1 | |
424 | , RandIt const last2 | |
425 | , Compare comp | |
426 | , Op op) | |
427 | { | |
428 | for(RandIt first2=last1; first2 != last2; ++buf_first){ | |
429 | if(first1 == last1){ | |
430 | op(forward_t(), first2, last2, buf_first); | |
431 | return; | |
432 | } | |
433 | else if(comp(*first2, *first1)){ | |
434 | op(first2, buf_first); | |
435 | ++first2; | |
436 | } | |
437 | else{ | |
438 | op(first1, buf_first); | |
439 | ++first1; | |
440 | } | |
441 | } | |
442 | if(buf_first != first1){//In case all remaining elements are in the same place | |
443 | //(e.g. buffer is exactly the size of the second half | |
444 | //and all elements from the second half are less) | |
445 | op(forward_t(), first1, last1, buf_first); | |
446 | } | |
7c673cae FG |
447 | } |
448 | ||
449 | // [buf_first, first1) -> buffer | |
450 | // [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1)) | |
451 | // Elements from buffer are moved to [last2 - (first1-buf_first), last2) | |
452 | // Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs | |
453 | template<class RandIt, class Compare> | |
454 | void merge_left | |
455 | (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp) | |
456 | { | |
457 | op_merge_left(buf_first, first1, last1, last2, comp, move_op()); | |
458 | } | |
459 | ||
460 | // [buf_first, first1) -> buffer | |
461 | // [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1)) | |
462 | // Elements from buffer are swapped to [last2 - (first1-buf_first), last2) | |
463 | // Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs | |
464 | template<class RandIt, class Compare> | |
465 | void swap_merge_left | |
466 | (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp) | |
467 | { | |
468 | op_merge_left(buf_first, first1, last1, last2, comp, swap_op()); | |
469 | } | |
470 | ||
471 | template<class RandIt, class Compare, class Op> | |
472 | void op_merge_right | |
473 | (RandIt const first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp, Op op) | |
474 | { | |
475 | RandIt const first2 = last1; | |
476 | while(first1 != last1){ | |
477 | if(last2 == first2){ | |
478 | op(backward_t(), first1, last1, buf_last); | |
479 | return; | |
480 | } | |
481 | --last2; | |
482 | --last1; | |
483 | --buf_last; | |
484 | if(comp(*last2, *last1)){ | |
485 | op(last1, buf_last); | |
486 | ++last2; | |
487 | } | |
488 | else{ | |
489 | op(last2, buf_last); | |
490 | ++last1; | |
491 | } | |
492 | } | |
493 | if(last2 != buf_last){ //In case all remaining elements are in the same place | |
494 | //(e.g. buffer is exactly the size of the first half | |
495 | //and all elements from the second half are less) | |
496 | op(backward_t(), first2, last2, buf_last); | |
497 | } | |
498 | } | |
499 | ||
500 | // [last2, buf_last) - buffer | |
501 | // [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last) | |
502 | // Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs | |
503 | template<class RandIt, class Compare> | |
504 | void merge_right | |
505 | (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp) | |
506 | { | |
507 | op_merge_right(first1, last1, last2, buf_last, comp, move_op()); | |
508 | } | |
509 | ||
510 | // [last2, buf_last) - buffer | |
511 | // [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last) | |
512 | // Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs | |
513 | template<class RandIt, class Compare> | |
514 | void swap_merge_right | |
515 | (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp) | |
516 | { | |
517 | op_merge_right(first1, last1, last2, buf_last, comp, swap_op()); | |
518 | } | |
519 | ||
92f5a8d4 TL |
520 | /////////////////////////////////////////////////////////////////////////////// |
521 | // | |
522 | // BUFFERED MERGE | |
523 | // | |
524 | /////////////////////////////////////////////////////////////////////////////// | |
525 | template<class RandIt, class Compare, class Op, class Buf> | |
526 | void op_buffered_merge | |
527 | ( RandIt first, RandIt const middle, RandIt last | |
528 | , Compare comp, Op op | |
529 | , Buf &xbuf) | |
530 | { | |
531 | if(first != middle && middle != last && comp(*middle, middle[-1])){ | |
1e59de90 | 532 | typedef typename iter_size<RandIt>::type size_type; |
92f5a8d4 TL |
533 | size_type const len1 = size_type(middle-first); |
534 | size_type const len2 = size_type(last-middle); | |
535 | if(len1 <= len2){ | |
536 | first = boost::movelib::upper_bound(first, middle, *middle, comp); | |
537 | xbuf.move_assign(first, size_type(middle-first)); | |
538 | op_merge_with_right_placed | |
539 | (xbuf.data(), xbuf.end(), first, middle, last, comp, op); | |
540 | } | |
541 | else{ | |
542 | last = boost::movelib::lower_bound(middle, last, middle[-1], comp); | |
543 | xbuf.move_assign(middle, size_type(last-middle)); | |
544 | op_merge_with_left_placed | |
545 | (first, middle, last, xbuf.data(), xbuf.end(), comp, op); | |
546 | } | |
547 | } | |
548 | } | |
549 | ||
550 | template<class RandIt, class Compare, class XBuf> | |
551 | void buffered_merge | |
552 | ( RandIt first, RandIt const middle, RandIt last | |
553 | , Compare comp | |
554 | , XBuf &xbuf) | |
555 | { | |
556 | op_buffered_merge(first, middle, last, comp, move_op(), xbuf); | |
557 | } | |
558 | ||
11fdf7f2 TL |
559 | //Complexity: min(len1,len2)^2 + max(len1,len2) |
560 | template<class RandIt, class Compare> | |
561 | void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp) | |
562 | { | |
563 | if((middle - first) < (last - middle)){ | |
564 | while(first != middle){ | |
565 | RandIt const old_last1 = middle; | |
566 | middle = boost::movelib::lower_bound(middle, last, *first, comp); | |
567 | first = rotate_gcd(first, old_last1, middle); | |
568 | if(middle == last){ | |
569 | break; | |
570 | } | |
571 | do{ | |
572 | ++first; | |
573 | } while(first != middle && !comp(*middle, *first)); | |
574 | } | |
575 | } | |
576 | else{ | |
577 | while(middle != last){ | |
578 | RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp); | |
579 | last = rotate_gcd(p, middle, last); | |
580 | middle = p; | |
581 | if(middle == first){ | |
582 | break; | |
583 | } | |
584 | --p; | |
585 | do{ | |
586 | --last; | |
587 | } while(middle != last && !comp(last[-1], *p)); | |
588 | } | |
589 | } | |
590 | } | |
591 | ||
92f5a8d4 | 592 | static const std::size_t MergeBufferlessONLogNRotationThreshold = 16u; |
11fdf7f2 | 593 | |
92f5a8d4 | 594 | template <class RandIt, class Compare> |
7c673cae | 595 | void merge_bufferless_ONlogN_recursive |
92f5a8d4 | 596 | ( RandIt first, RandIt middle, RandIt last |
1e59de90 TL |
597 | , typename iter_size<RandIt>::type len1 |
598 | , typename iter_size<RandIt>::type len2 | |
92f5a8d4 | 599 | , Compare comp) |
7c673cae | 600 | { |
1e59de90 | 601 | typedef typename iter_size<RandIt>::type size_type; |
11fdf7f2 | 602 | |
7c673cae | 603 | while(1) { |
11fdf7f2 TL |
604 | //trivial cases |
605 | if (!len2) { | |
7c673cae FG |
606 | return; |
607 | } | |
11fdf7f2 | 608 | else if (!len1) { |
7c673cae FG |
609 | return; |
610 | } | |
11fdf7f2 | 611 | else if (size_type(len1 | len2) == 1u) { |
7c673cae FG |
612 | if (comp(*middle, *first)) |
613 | adl_move_swap(*first, *middle); | |
614 | return; | |
615 | } | |
11fdf7f2 TL |
616 | else if(size_type(len1+len2) < MergeBufferlessONLogNRotationThreshold){ |
617 | merge_bufferless_ON2(first, middle, last, comp); | |
7c673cae | 618 | return; |
7c673cae FG |
619 | } |
620 | ||
11fdf7f2 TL |
621 | RandIt first_cut = first; |
622 | RandIt second_cut = middle; | |
92f5a8d4 TL |
623 | size_type len11 = 0; |
624 | size_type len22 = 0; | |
7c673cae FG |
625 | if (len1 > len2) { |
626 | len11 = len1 / 2; | |
627 | first_cut += len11; | |
b32b8144 | 628 | second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp); |
7c673cae FG |
629 | len22 = size_type(second_cut - middle); |
630 | } | |
631 | else { | |
632 | len22 = len2 / 2; | |
633 | second_cut += len22; | |
b32b8144 | 634 | first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp); |
7c673cae FG |
635 | len11 = size_type(first_cut - first); |
636 | } | |
11fdf7f2 | 637 | RandIt new_middle = rotate_gcd(first_cut, middle, second_cut); |
7c673cae FG |
638 | |
639 | //Avoid one recursive call doing a manual tail call elimination on the biggest range | |
1e59de90 | 640 | const size_type len_internal = size_type(len11+len22); |
7c673cae | 641 | if( len_internal < (len1 + len2 - len_internal) ) { |
1e59de90 | 642 | merge_bufferless_ONlogN_recursive(first, first_cut, new_middle, len11, len22, comp); |
7c673cae FG |
643 | first = new_middle; |
644 | middle = second_cut; | |
1e59de90 TL |
645 | len1 = size_type(len1-len11); |
646 | len2 = size_type(len2-len22); | |
7c673cae FG |
647 | } |
648 | else { | |
1e59de90 TL |
649 | merge_bufferless_ONlogN_recursive |
650 | (new_middle, second_cut, last, size_type(len1 - len11), size_type(len2 - len22), comp); | |
7c673cae FG |
651 | middle = first_cut; |
652 | last = new_middle; | |
653 | len1 = len11; | |
654 | len2 = len22; | |
655 | } | |
656 | } | |
657 | } | |
658 | ||
92f5a8d4 | 659 | |
7c673cae | 660 | //Complexity: NlogN |
11fdf7f2 TL |
661 | template<class RandIt, class Compare> |
662 | void merge_bufferless_ONlogN(RandIt first, RandIt middle, RandIt last, Compare comp) | |
7c673cae | 663 | { |
1e59de90 | 664 | typedef typename iter_size<RandIt>::type size_type; |
7c673cae | 665 | merge_bufferless_ONlogN_recursive |
92f5a8d4 | 666 | (first, middle, last, size_type(middle - first), size_type(last - middle), comp); |
7c673cae FG |
667 | } |
668 | ||
7c673cae FG |
669 | template<class RandIt, class Compare> |
670 | void merge_bufferless(RandIt first, RandIt middle, RandIt last, Compare comp) | |
671 | { | |
11fdf7f2 | 672 | #define BOOST_ADAPTIVE_MERGE_NLOGN_MERGE |
7c673cae FG |
673 | #ifdef BOOST_ADAPTIVE_MERGE_NLOGN_MERGE |
674 | merge_bufferless_ONlogN(first, middle, last, comp); | |
675 | #else | |
676 | merge_bufferless_ON2(first, middle, last, comp); | |
677 | #endif //BOOST_ADAPTIVE_MERGE_NLOGN_MERGE | |
678 | } | |
679 | ||
7c673cae FG |
680 | // [r_first, r_last) are already in the right part of the destination range. |
681 | template <class Compare, class InputIterator, class InputOutIterator, class Op> | |
682 | void op_merge_with_right_placed | |
683 | ( InputIterator first, InputIterator last | |
684 | , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last | |
685 | , Compare comp, Op op) | |
686 | { | |
687 | BOOST_ASSERT((last - first) == (r_first - dest_first)); | |
688 | while ( first != last ) { | |
689 | if (r_first == r_last) { | |
690 | InputOutIterator end = op(forward_t(), first, last, dest_first); | |
691 | BOOST_ASSERT(end == r_last); | |
20effc67 | 692 | boost::ignore_unused(end); |
7c673cae FG |
693 | return; |
694 | } | |
695 | else if (comp(*r_first, *first)) { | |
696 | op(r_first, dest_first); | |
697 | ++r_first; | |
698 | } | |
699 | else { | |
700 | op(first, dest_first); | |
701 | ++first; | |
702 | } | |
703 | ++dest_first; | |
704 | } | |
705 | // Remaining [r_first, r_last) already in the correct place | |
706 | } | |
707 | ||
708 | template <class Compare, class InputIterator, class InputOutIterator> | |
709 | void swap_merge_with_right_placed | |
710 | ( InputIterator first, InputIterator last | |
711 | , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last | |
712 | , Compare comp) | |
713 | { | |
714 | op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, swap_op()); | |
715 | } | |
716 | ||
b32b8144 | 717 | // [first, last) are already in the right part of the destination range. |
7c673cae FG |
718 | template <class Compare, class Op, class BidirIterator, class BidirOutIterator> |
719 | void op_merge_with_left_placed | |
720 | ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last | |
721 | , BidirIterator const r_first, BidirIterator r_last | |
722 | , Compare comp, Op op) | |
723 | { | |
724 | BOOST_ASSERT((dest_last - last) == (r_last - r_first)); | |
725 | while( r_first != r_last ) { | |
726 | if(first == last) { | |
727 | BidirOutIterator res = op(backward_t(), r_first, r_last, dest_last); | |
728 | BOOST_ASSERT(last == res); | |
20effc67 | 729 | boost::ignore_unused(res); |
7c673cae FG |
730 | return; |
731 | } | |
732 | --r_last; | |
733 | --last; | |
734 | if(comp(*r_last, *last)){ | |
735 | ++r_last; | |
736 | --dest_last; | |
737 | op(last, dest_last); | |
738 | } | |
739 | else{ | |
740 | ++last; | |
741 | --dest_last; | |
742 | op(r_last, dest_last); | |
743 | } | |
744 | } | |
745 | // Remaining [first, last) already in the correct place | |
746 | } | |
747 | ||
748 | // @endcond | |
749 | ||
92f5a8d4 | 750 | // [first, last) are already in the right part of the destination range. |
7c673cae FG |
751 | template <class Compare, class BidirIterator, class BidirOutIterator> |
752 | void merge_with_left_placed | |
753 | ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last | |
754 | , BidirIterator const r_first, BidirIterator r_last | |
755 | , Compare comp) | |
756 | { | |
757 | op_merge_with_left_placed(first, last, dest_last, r_first, r_last, comp, move_op()); | |
758 | } | |
759 | ||
760 | // [r_first, r_last) are already in the right part of the destination range. | |
761 | template <class Compare, class InputIterator, class InputOutIterator> | |
762 | void merge_with_right_placed | |
763 | ( InputIterator first, InputIterator last | |
764 | , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last | |
765 | , Compare comp) | |
766 | { | |
767 | op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, move_op()); | |
768 | } | |
769 | ||
770 | // [r_first, r_last) are already in the right part of the destination range. | |
771 | // [dest_first, r_first) is uninitialized memory | |
772 | template <class Compare, class InputIterator, class InputOutIterator> | |
773 | void uninitialized_merge_with_right_placed | |
774 | ( InputIterator first, InputIterator last | |
775 | , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last | |
776 | , Compare comp) | |
777 | { | |
778 | BOOST_ASSERT((last - first) == (r_first - dest_first)); | |
779 | typedef typename iterator_traits<InputOutIterator>::value_type value_type; | |
780 | InputOutIterator const original_r_first = r_first; | |
781 | ||
b32b8144 | 782 | destruct_n<value_type, InputOutIterator> d(dest_first); |
7c673cae FG |
783 | |
784 | while ( first != last && dest_first != original_r_first ) { | |
785 | if (r_first == r_last) { | |
786 | for(; dest_first != original_r_first; ++dest_first, ++first){ | |
b32b8144 | 787 | ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first)); |
7c673cae FG |
788 | d.incr(); |
789 | } | |
790 | d.release(); | |
791 | InputOutIterator end = ::boost::move(first, last, original_r_first); | |
792 | BOOST_ASSERT(end == r_last); | |
20effc67 | 793 | boost::ignore_unused(end); |
7c673cae FG |
794 | return; |
795 | } | |
b32b8144 FG |
796 | else if (comp(*r_first, *first)) { |
797 | ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*r_first)); | |
798 | d.incr(); | |
799 | ++r_first; | |
800 | } | |
801 | else { | |
802 | ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first)); | |
803 | d.incr(); | |
804 | ++first; | |
805 | } | |
806 | ++dest_first; | |
807 | } | |
808 | d.release(); | |
809 | merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp); | |
810 | } | |
811 | ||
92f5a8d4 TL |
812 | /// This is a helper function for the merge routines. |
813 | template<typename BidirectionalIterator1, typename BidirectionalIterator2> | |
814 | BidirectionalIterator1 | |
815 | rotate_adaptive(BidirectionalIterator1 first, | |
816 | BidirectionalIterator1 middle, | |
817 | BidirectionalIterator1 last, | |
1e59de90 TL |
818 | typename iter_size<BidirectionalIterator1>::type len1, |
819 | typename iter_size<BidirectionalIterator1>::type len2, | |
92f5a8d4 | 820 | BidirectionalIterator2 buffer, |
1e59de90 | 821 | typename iter_size<BidirectionalIterator1>::type buffer_size) |
92f5a8d4 TL |
822 | { |
823 | if (len1 > len2 && len2 <= buffer_size) | |
824 | { | |
825 | if(len2) //Protect against self-move ranges | |
826 | { | |
827 | BidirectionalIterator2 buffer_end = boost::move(middle, last, buffer); | |
828 | boost::move_backward(first, middle, last); | |
829 | return boost::move(buffer, buffer_end, first); | |
830 | } | |
831 | else | |
832 | return first; | |
833 | } | |
834 | else if (len1 <= buffer_size) | |
835 | { | |
836 | if(len1) //Protect against self-move ranges | |
837 | { | |
838 | BidirectionalIterator2 buffer_end = boost::move(first, middle, buffer); | |
839 | BidirectionalIterator1 ret = boost::move(middle, last, first); | |
840 | boost::move(buffer, buffer_end, ret); | |
841 | return ret; | |
842 | } | |
843 | else | |
844 | return last; | |
845 | } | |
846 | else | |
847 | return rotate_gcd(first, middle, last); | |
848 | } | |
849 | ||
850 | template<typename BidirectionalIterator, | |
851 | typename Pointer, typename Compare> | |
852 | void merge_adaptive_ONlogN_recursive | |
853 | (BidirectionalIterator first, | |
854 | BidirectionalIterator middle, | |
855 | BidirectionalIterator last, | |
1e59de90 TL |
856 | typename iter_size<BidirectionalIterator>::type len1, |
857 | typename iter_size<BidirectionalIterator>::type len2, | |
92f5a8d4 | 858 | Pointer buffer, |
1e59de90 | 859 | typename iter_size<BidirectionalIterator>::type buffer_size, |
92f5a8d4 TL |
860 | Compare comp) |
861 | { | |
1e59de90 | 862 | typedef typename iter_size<BidirectionalIterator>::type size_type; |
92f5a8d4 TL |
863 | //trivial cases |
864 | if (!len2 || !len1) { | |
1e59de90 | 865 | // no-op |
92f5a8d4 | 866 | } |
1e59de90 | 867 | else if (len1 <= buffer_size || len2 <= buffer_size) { |
92f5a8d4 TL |
868 | range_xbuf<Pointer, size_type, move_op> rxbuf(buffer, buffer + buffer_size); |
869 | buffered_merge(first, middle, last, comp, rxbuf); | |
870 | } | |
871 | else if (size_type(len1 + len2) == 2u) { | |
872 | if (comp(*middle, *first)) | |
873 | adl_move_swap(*first, *middle); | |
92f5a8d4 TL |
874 | } |
875 | else if (size_type(len1 + len2) < MergeBufferlessONLogNRotationThreshold) { | |
876 | merge_bufferless_ON2(first, middle, last, comp); | |
92f5a8d4 | 877 | } |
1e59de90 TL |
878 | else { |
879 | BidirectionalIterator first_cut = first; | |
880 | BidirectionalIterator second_cut = middle; | |
881 | size_type len11 = 0; | |
882 | size_type len22 = 0; | |
883 | if (len1 > len2) //(len1 < len2) | |
884 | { | |
885 | len11 = len1 / 2; | |
886 | first_cut += len11; | |
887 | second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp); | |
888 | len22 = size_type(second_cut - middle); | |
889 | } | |
890 | else | |
891 | { | |
892 | len22 = len2 / 2; | |
893 | second_cut += len22; | |
894 | first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp); | |
895 | len11 = size_type(first_cut - first); | |
896 | } | |
897 | ||
898 | BidirectionalIterator new_middle | |
899 | = rotate_adaptive(first_cut, middle, second_cut, | |
900 | size_type(len1 - len11), len22, buffer, | |
901 | buffer_size); | |
902 | merge_adaptive_ONlogN_recursive(first, first_cut, new_middle, len11, | |
903 | len22, buffer, buffer_size, comp); | |
904 | merge_adaptive_ONlogN_recursive(new_middle, second_cut, last, | |
905 | size_type(len1 - len11), size_type(len2 - len22), buffer, buffer_size, comp); | |
92f5a8d4 | 906 | } |
92f5a8d4 TL |
907 | } |
908 | ||
909 | ||
910 | template<typename BidirectionalIterator, typename Compare, typename RandRawIt> | |
911 | void merge_adaptive_ONlogN(BidirectionalIterator first, | |
912 | BidirectionalIterator middle, | |
913 | BidirectionalIterator last, | |
914 | Compare comp, | |
915 | RandRawIt uninitialized, | |
1e59de90 | 916 | typename iter_size<BidirectionalIterator>::type uninitialized_len) |
92f5a8d4 TL |
917 | { |
918 | typedef typename iterator_traits<BidirectionalIterator>::value_type value_type; | |
1e59de90 | 919 | typedef typename iter_size<BidirectionalIterator>::type size_type; |
92f5a8d4 TL |
920 | |
921 | if (first == middle || middle == last) | |
922 | return; | |
923 | ||
924 | if(uninitialized_len) | |
925 | { | |
926 | const size_type len1 = size_type(middle - first); | |
927 | const size_type len2 = size_type(last - middle); | |
928 | ||
929 | ::boost::movelib::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len); | |
930 | xbuf.initialize_until(uninitialized_len, *first); | |
931 | merge_adaptive_ONlogN_recursive(first, middle, last, len1, len2, xbuf.begin(), uninitialized_len, comp); | |
932 | } | |
933 | else | |
934 | { | |
935 | merge_bufferless(first, middle, last, comp); | |
936 | } | |
937 | } | |
938 | ||
7c673cae FG |
939 | } //namespace movelib { |
940 | } //namespace boost { | |
941 | ||
1e59de90 TL |
942 | #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600)) |
943 | #pragma GCC diagnostic pop | |
944 | #endif | |
945 | ||
7c673cae | 946 | #endif //#define BOOST_MOVE_MERGE_HPP |