]>
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 | // | |
12 | // Stable sorting that works in O(N*log(N)) worst time | |
13 | // and uses O(1) extra memory | |
14 | // | |
15 | ////////////////////////////////////////////////////////////////////////////// | |
16 | // | |
17 | // The main idea of the adaptive_sort algorithm was developed by Andrey Astrelin | |
18 | // and explained in the article from the russian collaborative blog | |
19 | // Habrahabr (http://habrahabr.ru/post/205290/). The algorithm is based on | |
20 | // ideas from B-C. Huang and M. A. Langston explained in their article | |
21 | // "Fast Stable Merging and Sorting in Constant Extra Space (1989-1992)" | |
22 | // (http://comjnl.oxfordjournals.org/content/35/6/643.full.pdf). | |
23 | // | |
24 | // This implementation by Ion Gaztanaga uses previous ideas with additional changes: | |
25 | // | |
26 | // - Use of GCD-based rotation. | |
27 | // - Non power of two buffer-sizes. | |
28 | // - Tries to find sqrt(len)*2 unique keys, so that the merge sort | |
29 | // phase can form up to sqrt(len)*4 segments if enough keys are found. | |
30 | // - The merge-sort phase can take advantage of external memory to | |
31 | // save some additional combination steps. | |
b32b8144 | 32 | // - Combination phase: Blocks are selection sorted and merged in parallel. |
7c673cae FG |
33 | // - The combination phase is performed alternating merge to left and merge |
34 | // to right phases minimizing swaps due to internal buffer repositioning. | |
35 | // - When merging blocks special optimizations are made to avoid moving some | |
36 | // elements twice. | |
37 | // | |
38 | // The adaptive_merge algorithm was developed by Ion Gaztanaga reusing some parts | |
39 | // from the sorting algorithm and implementing an additional block merge algorithm | |
b32b8144 | 40 | // without moving elements to left or right. |
7c673cae FG |
41 | ////////////////////////////////////////////////////////////////////////////// |
42 | #ifndef BOOST_MOVE_ADAPTIVE_SORT_MERGE_HPP | |
43 | #define BOOST_MOVE_ADAPTIVE_SORT_MERGE_HPP | |
44 | ||
45 | #include <boost/move/detail/config_begin.hpp> | |
46 | #include <boost/move/detail/reverse_iterator.hpp> | |
47 | #include <boost/move/algo/move.hpp> | |
48 | #include <boost/move/algo/detail/merge.hpp> | |
49 | #include <boost/move/adl_move_swap.hpp> | |
50 | #include <boost/move/algo/detail/insertion_sort.hpp> | |
51 | #include <boost/move/algo/detail/merge_sort.hpp> | |
11fdf7f2 | 52 | #include <boost/move/algo/detail/heap_sort.hpp> |
7c673cae | 53 | #include <boost/move/algo/detail/merge.hpp> |
11fdf7f2 | 54 | #include <boost/move/algo/detail/is_sorted.hpp> |
7c673cae FG |
55 | #include <boost/assert.hpp> |
56 | #include <boost/cstdint.hpp> | |
57 | ||
b32b8144 FG |
58 | #ifndef BOOST_MOVE_ADAPTIVE_SORT_STATS_LEVEL |
59 | #define BOOST_MOVE_ADAPTIVE_SORT_STATS_LEVEL 1 | |
60 | #endif | |
61 | ||
7c673cae | 62 | #ifdef BOOST_MOVE_ADAPTIVE_SORT_STATS |
b32b8144 FG |
63 | #if BOOST_MOVE_ADAPTIVE_SORT_STATS_LEVEL == 2 |
64 | #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(STR, L) \ | |
65 | print_stats(STR, L)\ | |
66 | // | |
67 | ||
68 | #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(STR, L) \ | |
69 | print_stats(STR, L)\ | |
70 | // | |
71 | #else | |
72 | #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(STR, L) \ | |
73 | print_stats(STR, L)\ | |
74 | // | |
75 | ||
76 | #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(STR, L) | |
77 | #endif | |
7c673cae | 78 | #else |
b32b8144 FG |
79 | #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(STR, L) |
80 | #define BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(STR, L) | |
7c673cae FG |
81 | #endif |
82 | ||
b32b8144 FG |
83 | #ifdef BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS |
84 | #define BOOST_MOVE_ADAPTIVE_SORT_INVARIANT BOOST_ASSERT | |
85 | #else | |
86 | #define BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(L) | |
87 | #endif | |
88 | ||
7c673cae FG |
89 | namespace boost { |
90 | namespace movelib { | |
91 | ||
11fdf7f2 TL |
92 | #if defined(BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS) |
93 | ||
94 | bool is_sorted(::order_perf_type *first, ::order_perf_type *last, ::order_type_less) | |
95 | { | |
96 | if (first != last) { | |
97 | const order_perf_type *next = first, *cur(first); | |
98 | while (++next != last) { | |
99 | if (!(cur->key < next->key || (cur->key == next->key && cur->val < next->val))) | |
100 | return false; | |
101 | cur = next; | |
102 | } | |
103 | } | |
104 | return true; | |
105 | } | |
106 | ||
107 | #endif //BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS | |
108 | ||
7c673cae FG |
109 | namespace detail_adaptive { |
110 | ||
111 | static const std::size_t AdaptiveSortInsertionSortThreshold = 16; | |
112 | //static const std::size_t AdaptiveSortInsertionSortThreshold = 4; | |
113 | BOOST_STATIC_ASSERT((AdaptiveSortInsertionSortThreshold&(AdaptiveSortInsertionSortThreshold-1)) == 0); | |
114 | ||
115 | #if defined BOOST_HAS_INTPTR_T | |
116 | typedef ::boost::uintptr_t uintptr_t; | |
117 | #else | |
118 | typedef std::size_t uintptr_t; | |
119 | #endif | |
120 | ||
121 | template<class T> | |
122 | const T &min_value(const T &a, const T &b) | |
123 | { | |
124 | return a < b ? a : b; | |
125 | } | |
126 | ||
127 | template<class T> | |
128 | const T &max_value(const T &a, const T &b) | |
129 | { | |
130 | return a > b ? a : b; | |
131 | } | |
132 | ||
b32b8144 FG |
133 | template<class ForwardIt, class Pred, class V> |
134 | typename iterator_traits<ForwardIt>::size_type | |
135 | count_if_with(ForwardIt first, ForwardIt last, Pred pred, const V &v) | |
136 | { | |
137 | typedef typename iterator_traits<ForwardIt>::size_type size_type; | |
138 | size_type count = 0; | |
139 | while(first != last) { | |
140 | count += static_cast<size_type>(0 != pred(*first, v)); | |
141 | ++first; | |
142 | } | |
143 | return count; | |
144 | } | |
145 | ||
7c673cae FG |
146 | |
147 | template<class RandIt, class Compare> | |
148 | RandIt skip_until_merge | |
149 | ( RandIt first1, RandIt const last1 | |
150 | , const typename iterator_traits<RandIt>::value_type &next_key, Compare comp) | |
151 | { | |
152 | while(first1 != last1 && !comp(next_key, *first1)){ | |
153 | ++first1; | |
154 | } | |
155 | return first1; | |
156 | } | |
157 | ||
7c673cae | 158 | |
b32b8144 FG |
159 | template<class RandItKeys, class RandIt> |
160 | void swap_and_update_key | |
161 | ( RandItKeys const key_next | |
162 | , RandItKeys const key_range2 | |
163 | , RandItKeys &key_mid | |
164 | , RandIt const begin | |
165 | , RandIt const end | |
166 | , RandIt const with) | |
7c673cae | 167 | { |
b32b8144 FG |
168 | if(begin != with){ |
169 | ::boost::adl_move_swap_ranges(begin, end, with); | |
170 | ::boost::adl_move_swap(*key_next, *key_range2); | |
171 | if(key_next == key_mid){ | |
172 | key_mid = key_range2; | |
7c673cae | 173 | } |
b32b8144 FG |
174 | else if(key_mid == key_range2){ |
175 | key_mid = key_next; | |
7c673cae FG |
176 | } |
177 | } | |
7c673cae FG |
178 | } |
179 | ||
92f5a8d4 TL |
180 | template<class RandItKeys> |
181 | void update_key | |
182 | (RandItKeys const key_next | |
183 | , RandItKeys const key_range2 | |
184 | , RandItKeys &key_mid) | |
185 | { | |
186 | if (key_next != key_range2) { | |
187 | ::boost::adl_move_swap(*key_next, *key_range2); | |
188 | if (key_next == key_mid) { | |
189 | key_mid = key_range2; | |
190 | } | |
191 | else if (key_mid == key_range2) { | |
192 | key_mid = key_next; | |
193 | } | |
194 | } | |
195 | } | |
196 | ||
197 | template<class RandItKeys, class RandIt, class RandIt2, class Op> | |
198 | RandIt2 buffer_and_update_key | |
199 | (RandItKeys const key_next | |
200 | , RandItKeys const key_range2 | |
201 | , RandItKeys &key_mid | |
202 | , RandIt begin | |
203 | , RandIt end | |
204 | , RandIt with | |
205 | , RandIt2 buffer | |
206 | , Op op) | |
207 | { | |
208 | if (begin != with) { | |
209 | while(begin != end) { | |
210 | op(three_way_t(), begin++, with++, buffer++); | |
211 | } | |
212 | ::boost::adl_move_swap(*key_next, *key_range2); | |
213 | if (key_next == key_mid) { | |
214 | key_mid = key_range2; | |
215 | } | |
216 | else if (key_mid == key_range2) { | |
217 | key_mid = key_next; | |
218 | } | |
219 | } | |
220 | return buffer; | |
221 | } | |
222 | ||
7c673cae FG |
223 | /////////////////////////////////////////////////////////////////////////////// |
224 | // | |
b32b8144 | 225 | // MERGE BUFFERLESS |
7c673cae FG |
226 | // |
227 | /////////////////////////////////////////////////////////////////////////////// | |
228 | ||
229 | // [first1, last1) merge [last1,last2) -> [first1,last2) | |
230 | template<class RandIt, class Compare> | |
231 | RandIt partial_merge_bufferless_impl | |
232 | (RandIt first1, RandIt last1, RandIt const last2, bool *const pis_range1_A, Compare comp) | |
233 | { | |
234 | if(last1 == last2){ | |
235 | return first1; | |
236 | } | |
237 | bool const is_range1_A = *pis_range1_A; | |
238 | if(first1 != last1 && comp(*last1, last1[-1])){ | |
239 | do{ | |
240 | RandIt const old_last1 = last1; | |
b32b8144 | 241 | last1 = boost::movelib::lower_bound(last1, last2, *first1, comp); |
7c673cae FG |
242 | first1 = rotate_gcd(first1, old_last1, last1);//old_last1 == last1 supported |
243 | if(last1 == last2){ | |
244 | return first1; | |
245 | } | |
246 | do{ | |
247 | ++first1; | |
248 | } while(last1 != first1 && !comp(*last1, *first1) ); | |
249 | } while(first1 != last1); | |
250 | } | |
251 | *pis_range1_A = !is_range1_A; | |
252 | return last1; | |
253 | } | |
254 | ||
255 | // [first1, last1) merge [last1,last2) -> [first1,last2) | |
256 | template<class RandIt, class Compare> | |
257 | RandIt partial_merge_bufferless | |
258 | (RandIt first1, RandIt last1, RandIt const last2, bool *const pis_range1_A, Compare comp) | |
259 | { | |
260 | return *pis_range1_A ? partial_merge_bufferless_impl(first1, last1, last2, pis_range1_A, comp) | |
261 | : partial_merge_bufferless_impl(first1, last1, last2, pis_range1_A, antistable<Compare>(comp)); | |
262 | } | |
263 | ||
b32b8144 FG |
264 | template<class SizeType> |
265 | static SizeType needed_keys_count(SizeType n_block_a, SizeType n_block_b) | |
266 | { | |
267 | return n_block_a + n_block_b; | |
268 | } | |
269 | ||
270 | template<class RandItKeys, class KeyCompare, class RandIt, class Compare> | |
271 | typename iterator_traits<RandIt>::size_type | |
272 | find_next_block | |
92f5a8d4 | 273 | ( RandItKeys const key_first |
b32b8144 FG |
274 | , KeyCompare key_comp |
275 | , RandIt const first | |
276 | , typename iterator_traits<RandIt>::size_type const l_block | |
277 | , typename iterator_traits<RandIt>::size_type const ix_first_block | |
278 | , typename iterator_traits<RandIt>::size_type const ix_last_block | |
279 | , Compare comp) | |
280 | { | |
281 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
282 | typedef typename iterator_traits<RandIt>::value_type value_type; | |
283 | typedef typename iterator_traits<RandItKeys>::value_type key_type; | |
284 | BOOST_ASSERT(ix_first_block <= ix_last_block); | |
285 | size_type ix_min_block = 0u; | |
286 | for (size_type szt_i = ix_first_block; szt_i < ix_last_block; ++szt_i) { | |
287 | const value_type &min_val = first[ix_min_block*l_block]; | |
288 | const value_type &cur_val = first[szt_i*l_block]; | |
289 | const key_type &min_key = key_first[ix_min_block]; | |
290 | const key_type &cur_key = key_first[szt_i]; | |
7c673cae | 291 | |
b32b8144 FG |
292 | bool const less_than_minimum = comp(cur_val, min_val) || |
293 | (!comp(min_val, cur_val) && key_comp(cur_key, min_key)); | |
294 | ||
295 | if (less_than_minimum) { | |
296 | ix_min_block = szt_i; | |
297 | } | |
298 | } | |
299 | return ix_min_block; | |
300 | } | |
7c673cae | 301 | |
7c673cae FG |
302 | template<class RandItKeys, class KeyCompare, class RandIt, class Compare> |
303 | void merge_blocks_bufferless | |
92f5a8d4 | 304 | ( RandItKeys const key_first |
7c673cae | 305 | , KeyCompare key_comp |
b32b8144 | 306 | , RandIt const first |
7c673cae FG |
307 | , typename iterator_traits<RandIt>::size_type const l_block |
308 | , typename iterator_traits<RandIt>::size_type const l_irreg1 | |
b32b8144 FG |
309 | , typename iterator_traits<RandIt>::size_type const n_block_a |
310 | , typename iterator_traits<RandIt>::size_type const n_block_b | |
7c673cae FG |
311 | , typename iterator_traits<RandIt>::size_type const l_irreg2 |
312 | , Compare comp) | |
313 | { | |
b32b8144 FG |
314 | typedef typename iterator_traits<RandIt>::size_type size_type; |
315 | size_type const key_count = needed_keys_count(n_block_a, n_block_b); (void)key_count; | |
316 | //BOOST_ASSERT(n_block_a || n_block_b); | |
11fdf7f2 | 317 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted_and_unique(key_first, key_first + key_count, key_comp)); |
b32b8144 FG |
318 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_first + key_count, key_comp, key_first[n_block_a])); |
319 | ||
320 | size_type n_bef_irreg2 = 0; | |
321 | bool l_irreg_pos_count = true; | |
322 | RandItKeys key_mid(key_first + n_block_a); | |
323 | RandIt const first_irr2 = first + l_irreg1 + (n_block_a+n_block_b)*l_block; | |
324 | RandIt const last_irr2 = first_irr2 + l_irreg2; | |
325 | ||
326 | { //Selection sort blocks | |
327 | size_type n_block_left = n_block_b + n_block_a; | |
328 | RandItKeys key_range2(key_first); | |
329 | ||
330 | size_type min_check = n_block_a == n_block_left ? 0u : n_block_a; | |
92f5a8d4 | 331 | size_type max_check = min_value<size_type>(min_check+1, n_block_left); |
b32b8144 FG |
332 | for (RandIt f = first+l_irreg1; n_block_left; --n_block_left, ++key_range2, f += l_block, min_check -= min_check != 0, max_check -= max_check != 0) { |
333 | size_type const next_key_idx = find_next_block(key_range2, key_comp, f, l_block, min_check, max_check, comp); | |
334 | RandItKeys const key_next(key_range2 + next_key_idx); | |
92f5a8d4 | 335 | max_check = min_value<size_type>(max_value<size_type>(max_check, next_key_idx+size_type(2)), n_block_left); |
b32b8144 FG |
336 | |
337 | RandIt const first_min = f + next_key_idx*l_block; | |
338 | ||
339 | //Check if irregular b block should go here. | |
340 | //If so, break to the special code handling the irregular block | |
341 | if (l_irreg_pos_count && l_irreg2 && comp(*first_irr2, *first_min)){ | |
342 | l_irreg_pos_count = false; | |
7c673cae | 343 | } |
b32b8144 | 344 | n_bef_irreg2 += l_irreg_pos_count; |
7c673cae | 345 | |
b32b8144 | 346 | swap_and_update_key(key_next, key_range2, key_mid, f, f + l_block, first_min); |
92f5a8d4 TL |
347 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(f, f+l_block, comp)); |
348 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first_min, first_min + l_block, comp)); | |
b32b8144 | 349 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT((f == (first+l_irreg1)) || !comp(*f, *(f-l_block))); |
7c673cae FG |
350 | } |
351 | } | |
92f5a8d4 | 352 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first+l_irreg1+n_bef_irreg2*l_block, first_irr2, comp)); |
7c673cae | 353 | |
b32b8144 FG |
354 | RandIt first1 = first; |
355 | RandIt last1 = first+l_irreg1; | |
356 | RandItKeys const key_end (key_first+n_bef_irreg2); | |
357 | bool is_range1_A = true; | |
358 | ||
92f5a8d4 TL |
359 | for(RandItKeys key_next = key_first; key_next != key_end; ++key_next){ |
360 | bool is_range2_A = key_mid == (key_first+key_count) || key_comp(*key_next, *key_mid); | |
b32b8144 FG |
361 | first1 = is_range1_A == is_range2_A |
362 | ? last1 : partial_merge_bufferless(first1, last1, last1 + l_block, &is_range1_A, comp); | |
363 | last1 += l_block; | |
92f5a8d4 | 364 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, first1, comp)); |
b32b8144 FG |
365 | } |
366 | ||
367 | merge_bufferless(is_range1_A ? first1 : last1, first_irr2, last_irr2, comp); | |
92f5a8d4 | 368 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, last_irr2, comp)); |
7c673cae FG |
369 | } |
370 | ||
371 | // Complexity: 2*distance(first, last)+max_collected^2/2 | |
372 | // | |
373 | // Tries to collect at most n_keys unique elements from [first, last), | |
374 | // in the begining of the range, and ordered according to comp | |
375 | // | |
376 | // Returns the number of collected keys | |
b32b8144 | 377 | template<class RandIt, class Compare, class XBuf> |
7c673cae FG |
378 | typename iterator_traits<RandIt>::size_type |
379 | collect_unique | |
380 | ( RandIt const first, RandIt const last | |
381 | , typename iterator_traits<RandIt>::size_type const max_collected, Compare comp | |
b32b8144 | 382 | , XBuf & xbuf) |
7c673cae FG |
383 | { |
384 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
7c673cae FG |
385 | size_type h = 0; |
386 | if(max_collected){ | |
387 | ++h; // first key is always here | |
388 | RandIt h0 = first; | |
389 | RandIt u = first; ++u; | |
390 | RandIt search_end = u; | |
391 | ||
392 | if(xbuf.capacity() >= max_collected){ | |
b32b8144 | 393 | typename XBuf::iterator const ph0 = xbuf.add(first); |
7c673cae | 394 | while(u != last && h < max_collected){ |
b32b8144 | 395 | typename XBuf::iterator const r = boost::movelib::lower_bound(ph0, xbuf.end(), *u, comp); |
7c673cae FG |
396 | //If key not found add it to [h, h+h0) |
397 | if(r == xbuf.end() || comp(*u, *r) ){ | |
398 | RandIt const new_h0 = boost::move(search_end, u, h0); | |
399 | search_end = u; | |
400 | ++search_end; | |
401 | ++h; | |
402 | xbuf.insert(r, u); | |
403 | h0 = new_h0; | |
404 | } | |
405 | ++u; | |
406 | } | |
407 | boost::move_backward(first, h0, h0+h); | |
408 | boost::move(xbuf.data(), xbuf.end(), first); | |
409 | } | |
410 | else{ | |
411 | while(u != last && h < max_collected){ | |
b32b8144 | 412 | RandIt const r = boost::movelib::lower_bound(h0, search_end, *u, comp); |
7c673cae FG |
413 | //If key not found add it to [h, h+h0) |
414 | if(r == search_end || comp(*u, *r) ){ | |
415 | RandIt const new_h0 = rotate_gcd(h0, search_end, u); | |
416 | search_end = u; | |
417 | ++search_end; | |
418 | ++h; | |
419 | rotate_gcd(r+(new_h0-h0), u, search_end); | |
420 | h0 = new_h0; | |
421 | } | |
422 | ++u; | |
423 | } | |
424 | rotate_gcd(first, h0, h0+h); | |
425 | } | |
426 | } | |
427 | return h; | |
428 | } | |
429 | ||
430 | template<class Unsigned> | |
431 | Unsigned floor_sqrt(Unsigned const n) | |
432 | { | |
433 | Unsigned x = n; | |
434 | Unsigned y = x/2 + (x&1); | |
435 | while (y < x){ | |
436 | x = y; | |
437 | y = (x + n / x)/2; | |
438 | } | |
439 | return x; | |
440 | } | |
441 | ||
442 | template<class Unsigned> | |
443 | Unsigned ceil_sqrt(Unsigned const n) | |
444 | { | |
445 | Unsigned r = floor_sqrt(n); | |
446 | return r + Unsigned((n%r) != 0); | |
447 | } | |
448 | ||
449 | template<class Unsigned> | |
450 | Unsigned floor_merge_multiple(Unsigned const n, Unsigned &base, Unsigned &pow) | |
451 | { | |
452 | Unsigned s = n; | |
453 | Unsigned p = 0; | |
454 | while(s > AdaptiveSortInsertionSortThreshold){ | |
455 | s /= 2; | |
456 | ++p; | |
457 | } | |
458 | base = s; | |
459 | pow = p; | |
460 | return s << p; | |
461 | } | |
462 | ||
463 | template<class Unsigned> | |
464 | Unsigned ceil_merge_multiple(Unsigned const n, Unsigned &base, Unsigned &pow) | |
465 | { | |
466 | Unsigned fm = floor_merge_multiple(n, base, pow); | |
467 | ||
468 | if(fm != n){ | |
469 | if(base < AdaptiveSortInsertionSortThreshold){ | |
470 | ++base; | |
471 | } | |
472 | else{ | |
473 | base = AdaptiveSortInsertionSortThreshold/2 + 1; | |
474 | ++pow; | |
475 | } | |
476 | } | |
477 | return base << pow; | |
478 | } | |
479 | ||
480 | template<class Unsigned> | |
481 | Unsigned ceil_sqrt_multiple(Unsigned const n, Unsigned *pbase = 0) | |
482 | { | |
483 | Unsigned const r = ceil_sqrt(n); | |
484 | Unsigned pow = 0; | |
485 | Unsigned base = 0; | |
486 | Unsigned const res = ceil_merge_multiple(r, base, pow); | |
487 | if(pbase) *pbase = base; | |
488 | return res; | |
489 | } | |
490 | ||
7c673cae FG |
491 | struct less |
492 | { | |
493 | template<class T> | |
494 | bool operator()(const T &l, const T &r) | |
495 | { return l < r; } | |
496 | }; | |
497 | ||
498 | /////////////////////////////////////////////////////////////////////////////// | |
499 | // | |
500 | // MERGE BLOCKS | |
501 | // | |
502 | /////////////////////////////////////////////////////////////////////////////// | |
503 | ||
504 | //#define ADAPTIVE_SORT_MERGE_SLOW_STABLE_SORT_IS_NLOGN | |
505 | ||
506 | #if defined ADAPTIVE_SORT_MERGE_SLOW_STABLE_SORT_IS_NLOGN | |
507 | template<class RandIt, class Compare> | |
508 | void slow_stable_sort | |
509 | ( RandIt const first, RandIt const last, Compare comp) | |
510 | { | |
511 | boost::movelib::inplace_stable_sort(first, last, comp); | |
512 | } | |
513 | ||
514 | #else //ADAPTIVE_SORT_MERGE_SLOW_STABLE_SORT_IS_NLOGN | |
515 | ||
516 | template<class RandIt, class Compare> | |
517 | void slow_stable_sort | |
518 | ( RandIt const first, RandIt const last, Compare comp) | |
519 | { | |
520 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
521 | size_type L = size_type(last - first); | |
522 | { //Use insertion sort to merge first elements | |
523 | size_type m = 0; | |
524 | while((L - m) > size_type(AdaptiveSortInsertionSortThreshold)){ | |
525 | insertion_sort(first+m, first+m+size_type(AdaptiveSortInsertionSortThreshold), comp); | |
526 | m += AdaptiveSortInsertionSortThreshold; | |
527 | } | |
528 | insertion_sort(first+m, last, comp); | |
529 | } | |
530 | ||
531 | size_type h = AdaptiveSortInsertionSortThreshold; | |
532 | for(bool do_merge = L > h; do_merge; h*=2){ | |
533 | do_merge = (L - h) > h; | |
534 | size_type p0 = 0; | |
535 | if(do_merge){ | |
536 | size_type const h_2 = 2*h; | |
537 | while((L-p0) > h_2){ | |
538 | merge_bufferless(first+p0, first+p0+h, first+p0+h_2, comp); | |
539 | p0 += h_2; | |
540 | } | |
541 | } | |
542 | if((L-p0) > h){ | |
543 | merge_bufferless(first+p0, first+p0+h, last, comp); | |
544 | } | |
545 | } | |
546 | } | |
547 | ||
548 | #endif //ADAPTIVE_SORT_MERGE_SLOW_STABLE_SORT_IS_NLOGN | |
549 | ||
550 | //Returns new l_block and updates use_buf | |
551 | template<class Unsigned> | |
552 | Unsigned lblock_for_combine | |
553 | (Unsigned const l_block, Unsigned const n_keys, Unsigned const l_data, bool &use_buf) | |
554 | { | |
555 | BOOST_ASSERT(l_data > 1); | |
556 | ||
557 | //We need to guarantee lblock >= l_merged/(n_keys/2) keys for the combination. | |
558 | //We have at least 4 keys guaranteed (which are the minimum to merge 2 ranges) | |
559 | //If l_block != 0, then n_keys is already enough to merge all blocks in all | |
560 | //phases as we've found all needed keys for that buffer and length before. | |
561 | //If l_block == 0 then see if half keys can be used as buffer and the rest | |
562 | //as keys guaranteeing that n_keys >= (2*l_merged)/lblock = | |
563 | if(!l_block){ | |
564 | //If l_block == 0 then n_keys is power of two | |
565 | //(guaranteed by build_params(...)) | |
566 | BOOST_ASSERT(n_keys >= 4); | |
567 | //BOOST_ASSERT(0 == (n_keys &(n_keys-1))); | |
568 | ||
569 | //See if half keys are at least 4 and if half keys fulfill | |
570 | Unsigned const new_buf = n_keys/2; | |
571 | Unsigned const new_keys = n_keys-new_buf; | |
572 | use_buf = new_keys >= 4 && new_keys >= l_data/new_buf; | |
573 | if(use_buf){ | |
574 | return new_buf; | |
575 | } | |
576 | else{ | |
577 | return l_data/n_keys; | |
578 | } | |
579 | } | |
580 | else{ | |
581 | use_buf = true; | |
582 | return l_block; | |
583 | } | |
584 | } | |
585 | ||
7c673cae FG |
586 | template<class RandIt, class Compare, class XBuf> |
587 | void stable_sort( RandIt first, RandIt last, Compare comp, XBuf & xbuf) | |
588 | { | |
589 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
590 | size_type const len = size_type(last - first); | |
591 | size_type const half_len = len/2 + (len&1); | |
592 | if(std::size_t(xbuf.capacity() - xbuf.size()) >= half_len) { | |
593 | merge_sort(first, last, comp, xbuf.data()+xbuf.size()); | |
594 | } | |
595 | else{ | |
596 | slow_stable_sort(first, last, comp); | |
597 | } | |
598 | } | |
599 | ||
11fdf7f2 TL |
600 | template<class RandIt, class Comp, class XBuf> |
601 | void unstable_sort( RandIt first, RandIt last | |
602 | , Comp comp | |
603 | , XBuf & xbuf) | |
604 | { | |
605 | heap_sort(first, last, comp);(void)xbuf; | |
606 | } | |
607 | ||
608 | template<class RandIt, class Compare, class XBuf> | |
609 | void stable_merge | |
610 | ( RandIt first, RandIt const middle, RandIt last | |
611 | , Compare comp | |
612 | , XBuf &xbuf) | |
613 | { | |
614 | BOOST_ASSERT(xbuf.empty()); | |
615 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
616 | size_type const len1 = size_type(middle-first); | |
617 | size_type const len2 = size_type(last-middle); | |
92f5a8d4 | 618 | size_type const l_min = min_value<size_type>(len1, len2); |
11fdf7f2 TL |
619 | if(xbuf.capacity() >= l_min){ |
620 | buffered_merge(first, middle, last, comp, xbuf); | |
621 | xbuf.clear(); | |
622 | } | |
623 | else{ | |
92f5a8d4 TL |
624 | //merge_bufferless(first, middle, last, comp); |
625 | merge_adaptive_ONlogN(first, middle, last, comp, xbuf.begin(), xbuf.capacity()); | |
11fdf7f2 | 626 | } |
92f5a8d4 | 627 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, last, boost::movelib::unantistable(comp))); |
11fdf7f2 TL |
628 | } |
629 | ||
7c673cae FG |
630 | template<class RandIt, class Comp, class XBuf> |
631 | void initialize_keys( RandIt first, RandIt last | |
632 | , Comp comp | |
633 | , XBuf & xbuf) | |
634 | { | |
11fdf7f2 TL |
635 | unstable_sort(first, last, comp, xbuf); |
636 | BOOST_ASSERT(boost::movelib::is_sorted_and_unique(first, last, comp)); | |
7c673cae FG |
637 | } |
638 | ||
639 | template<class RandIt, class U> | |
640 | void initialize_keys( RandIt first, RandIt last | |
641 | , less | |
642 | , U &) | |
643 | { | |
644 | typedef typename iterator_traits<RandIt>::value_type value_type; | |
645 | std::size_t count = std::size_t(last - first); | |
646 | for(std::size_t i = 0; i != count; ++i){ | |
92f5a8d4 | 647 | *first = static_cast<value_type>(i); |
7c673cae FG |
648 | ++first; |
649 | } | |
650 | } | |
651 | ||
b32b8144 FG |
652 | template <class Unsigned> |
653 | Unsigned calculate_total_combined(Unsigned const len, Unsigned const l_prev_merged, Unsigned *pl_irreg_combined = 0) | |
654 | { | |
655 | typedef Unsigned size_type; | |
656 | ||
657 | size_type const l_combined = 2*l_prev_merged; | |
658 | size_type l_irreg_combined = len%l_combined; | |
659 | size_type l_total_combined = len; | |
660 | if(l_irreg_combined <= l_prev_merged){ | |
661 | l_total_combined -= l_irreg_combined; | |
662 | l_irreg_combined = 0; | |
663 | } | |
664 | if(pl_irreg_combined) | |
665 | *pl_irreg_combined = l_irreg_combined; | |
666 | return l_total_combined; | |
667 | } | |
668 | ||
669 | template<class RandItKeys, class KeyCompare, class SizeType, class XBuf> | |
7c673cae FG |
670 | void combine_params |
671 | ( RandItKeys const keys | |
672 | , KeyCompare key_comp | |
b32b8144 FG |
673 | , SizeType l_combined |
674 | , SizeType const l_prev_merged | |
675 | , SizeType const l_block | |
7c673cae | 676 | , XBuf & xbuf |
7c673cae | 677 | //Output |
b32b8144 FG |
678 | , SizeType &n_block_a |
679 | , SizeType &n_block_b | |
680 | , SizeType &l_irreg1 | |
681 | , SizeType &l_irreg2 | |
7c673cae | 682 | //Options |
7c673cae FG |
683 | , bool do_initialize_keys = true) |
684 | { | |
b32b8144 | 685 | typedef SizeType size_type; |
7c673cae FG |
686 | |
687 | //Initial parameters for selection sort blocks | |
688 | l_irreg1 = l_prev_merged%l_block; | |
689 | l_irreg2 = (l_combined-l_irreg1)%l_block; | |
690 | BOOST_ASSERT(((l_combined-l_irreg1-l_irreg2)%l_block) == 0); | |
691 | size_type const n_reg_block = (l_combined-l_irreg1-l_irreg2)/l_block; | |
b32b8144 FG |
692 | n_block_a = l_prev_merged/l_block; |
693 | n_block_b = n_reg_block - n_block_a; | |
694 | BOOST_ASSERT(n_reg_block>=n_block_a); | |
7c673cae FG |
695 | |
696 | //Key initialization | |
697 | if (do_initialize_keys) { | |
b32b8144 | 698 | initialize_keys(keys, keys + needed_keys_count(n_block_a, n_block_b), key_comp, xbuf); |
7c673cae | 699 | } |
b32b8144 FG |
700 | } |
701 | ||
b32b8144 | 702 | |
7c673cae | 703 | |
b32b8144 FG |
704 | ////////////////////////////////// |
705 | // | |
706 | // partial_merge | |
707 | // | |
708 | ////////////////////////////////// | |
709 | template<class InputIt1, class InputIt2, class OutputIt, class Compare, class Op> | |
710 | OutputIt op_partial_merge_impl | |
711 | (InputIt1 &r_first1, InputIt1 const last1, InputIt2 &r_first2, InputIt2 const last2, OutputIt d_first, Compare comp, Op op) | |
712 | { | |
713 | InputIt1 first1(r_first1); | |
714 | InputIt2 first2(r_first2); | |
715 | if(first2 != last2 && last1 != first1) | |
716 | while(1){ | |
717 | if(comp(*first2, *first1)) { | |
718 | op(first2++, d_first++); | |
719 | if(first2 == last2){ | |
720 | break; | |
721 | } | |
722 | } | |
723 | else{ | |
724 | op(first1++, d_first++); | |
725 | if(first1 == last1){ | |
726 | break; | |
727 | } | |
728 | } | |
729 | } | |
730 | r_first1 = first1; | |
731 | r_first2 = first2; | |
732 | return d_first; | |
733 | } | |
734 | ||
735 | template<class InputIt1, class InputIt2, class OutputIt, class Compare, class Op> | |
736 | OutputIt op_partial_merge | |
737 | (InputIt1 &r_first1, InputIt1 const last1, InputIt2 &r_first2, InputIt2 const last2, OutputIt d_first, Compare comp, Op op, bool is_stable) | |
738 | { | |
739 | return is_stable ? op_partial_merge_impl(r_first1, last1, r_first2, last2, d_first, comp, op) | |
740 | : op_partial_merge_impl(r_first1, last1, r_first2, last2, d_first, antistable<Compare>(comp), op); | |
741 | } | |
742 | ||
11fdf7f2 TL |
743 | ////////////////////////////////// |
744 | ////////////////////////////////// | |
b32b8144 FG |
745 | ////////////////////////////////// |
746 | // | |
11fdf7f2 | 747 | // op_partial_merge_and_save |
b32b8144 FG |
748 | // |
749 | ////////////////////////////////// | |
11fdf7f2 TL |
750 | ////////////////////////////////// |
751 | ////////////////////////////////// | |
b32b8144 FG |
752 | template<class InputIt1, class InputIt2, class OutputIt, class Compare, class Op> |
753 | OutputIt op_partial_merge_and_swap_impl | |
754 | (InputIt1 &r_first1, InputIt1 const last1, InputIt2 &r_first2, InputIt2 const last2, InputIt2 &r_first_min, OutputIt d_first, Compare comp, Op op) | |
755 | { | |
756 | InputIt1 first1(r_first1); | |
757 | InputIt2 first2(r_first2); | |
758 | ||
759 | if(first2 != last2 && last1 != first1) { | |
760 | InputIt2 first_min(r_first_min); | |
761 | bool non_empty_ranges = true; | |
762 | do{ | |
763 | if(comp(*first_min, *first1)) { | |
764 | op(three_way_t(), first2++, first_min++, d_first++); | |
765 | non_empty_ranges = first2 != last2; | |
766 | } | |
767 | else{ | |
768 | op(first1++, d_first++); | |
769 | non_empty_ranges = first1 != last1; | |
770 | } | |
771 | } while(non_empty_ranges); | |
772 | r_first_min = first_min; | |
773 | r_first1 = first1; | |
774 | r_first2 = first2; | |
775 | } | |
776 | return d_first; | |
777 | } | |
778 | ||
779 | template<class RandIt, class InputIt2, class OutputIt, class Compare, class Op> | |
780 | OutputIt op_partial_merge_and_swap | |
781 | (RandIt &r_first1, RandIt const last1, InputIt2 &r_first2, InputIt2 const last2, InputIt2 &r_first_min, OutputIt d_first, Compare comp, Op op, bool is_stable) | |
782 | { | |
783 | return is_stable ? op_partial_merge_and_swap_impl(r_first1, last1, r_first2, last2, r_first_min, d_first, comp, op) | |
784 | : op_partial_merge_and_swap_impl(r_first1, last1, r_first2, last2, r_first_min, d_first, antistable<Compare>(comp), op); | |
785 | } | |
786 | ||
11fdf7f2 TL |
787 | template<class RandIt1, class RandIt2, class RandItB, class Compare, class Op> |
788 | RandItB op_buffered_partial_merge_and_swap_to_range1_and_buffer | |
789 | ( RandIt1 first1, RandIt1 const last1 | |
790 | , RandIt2 &rfirst2, RandIt2 const last2, RandIt2 &rfirst_min | |
791 | , RandItB &rfirstb, Compare comp, Op op ) | |
792 | { | |
793 | RandItB firstb = rfirstb; | |
794 | RandItB lastb = firstb; | |
795 | RandIt2 first2 = rfirst2; | |
796 | ||
797 | //Move to buffer while merging | |
798 | //Three way moves need less moves when op is swap_op so use it | |
799 | //when merging elements from range2 to the destination occupied by range1 | |
800 | if(first1 != last1 && first2 != last2){ | |
801 | RandIt2 first_min = rfirst_min; | |
802 | op(four_way_t(), first2++, first_min++, first1++, lastb++); | |
803 | ||
804 | while(first1 != last1){ | |
805 | if(first2 == last2){ | |
806 | lastb = op(forward_t(), first1, last1, firstb); | |
807 | break; | |
808 | } | |
809 | ||
810 | if(comp(*first_min, *firstb)){ | |
811 | op( four_way_t(), first2++, first_min++, first1++, lastb++); | |
812 | } | |
813 | else{ | |
814 | op(three_way_t(), firstb++, first1++, lastb++); | |
815 | } | |
816 | } | |
817 | rfirst2 = first2; | |
818 | rfirstb = firstb; | |
819 | rfirst_min = first_min; | |
820 | } | |
821 | ||
822 | return lastb; | |
823 | } | |
824 | ||
825 | template<class RandIt1, class RandIt2, class RandItB, class Compare, class Op> | |
826 | RandItB op_buffered_partial_merge_to_range1_and_buffer | |
827 | ( RandIt1 first1, RandIt1 const last1 | |
828 | , RandIt2 &rfirst2, RandIt2 const last2 | |
829 | , RandItB &rfirstb, Compare comp, Op op ) | |
830 | { | |
831 | RandItB firstb = rfirstb; | |
832 | RandItB lastb = firstb; | |
833 | RandIt2 first2 = rfirst2; | |
834 | ||
835 | //Move to buffer while merging | |
836 | //Three way moves need less moves when op is swap_op so use it | |
837 | //when merging elements from range2 to the destination occupied by range1 | |
838 | if(first1 != last1 && first2 != last2){ | |
839 | op(three_way_t(), first2++, first1++, lastb++); | |
840 | ||
841 | while(true){ | |
842 | if(first1 == last1){ | |
843 | break; | |
844 | } | |
845 | if(first2 == last2){ | |
846 | lastb = op(forward_t(), first1, last1, firstb); | |
847 | break; | |
848 | } | |
849 | if (comp(*first2, *firstb)) { | |
850 | op(three_way_t(), first2++, first1++, lastb++); | |
851 | } | |
852 | else { | |
853 | op(three_way_t(), firstb++, first1++, lastb++); | |
854 | } | |
855 | } | |
856 | rfirst2 = first2; | |
857 | rfirstb = firstb; | |
858 | } | |
859 | ||
860 | return lastb; | |
861 | } | |
862 | ||
b32b8144 FG |
863 | template<class RandIt, class RandItBuf, class Compare, class Op> |
864 | RandIt op_partial_merge_and_save_impl | |
865 | ( RandIt first1, RandIt const last1, RandIt &rfirst2, RandIt last2, RandIt first_min | |
866 | , RandItBuf &buf_first1_in_out, RandItBuf &buf_last1_in_out | |
867 | , Compare comp, Op op | |
868 | ) | |
869 | { | |
870 | RandItBuf buf_first1 = buf_first1_in_out; | |
871 | RandItBuf buf_last1 = buf_last1_in_out; | |
872 | RandIt first2(rfirst2); | |
873 | ||
874 | bool const do_swap = first2 != first_min; | |
875 | if(buf_first1 == buf_last1){ | |
876 | //Skip any element that does not need to be moved | |
877 | RandIt new_first1 = skip_until_merge(first1, last1, *first_min, comp); | |
878 | buf_first1 += (new_first1-first1); | |
879 | first1 = new_first1; | |
880 | buf_last1 = do_swap ? op_buffered_partial_merge_and_swap_to_range1_and_buffer(first1, last1, first2, last2, first_min, buf_first1, comp, op) | |
881 | : op_buffered_partial_merge_to_range1_and_buffer (first1, last1, first2, last2, buf_first1, comp, op); | |
882 | first1 = last1; | |
883 | } | |
884 | else{ | |
885 | BOOST_ASSERT((last1-first1) == (buf_last1 - buf_first1)); | |
886 | } | |
887 | ||
888 | //Now merge from buffer | |
889 | first1 = do_swap ? op_partial_merge_and_swap_impl(buf_first1, buf_last1, first2, last2, first_min, first1, comp, op) | |
890 | : op_partial_merge_impl (buf_first1, buf_last1, first2, last2, first1, comp, op); | |
891 | buf_first1_in_out = buf_first1; | |
892 | buf_last1_in_out = buf_last1; | |
893 | rfirst2 = first2; | |
894 | return first1; | |
895 | } | |
896 | ||
897 | template<class RandIt, class RandItBuf, class Compare, class Op> | |
898 | RandIt op_partial_merge_and_save | |
899 | ( RandIt first1, RandIt const last1, RandIt &rfirst2, RandIt last2, RandIt first_min | |
900 | , RandItBuf &buf_first1_in_out | |
901 | , RandItBuf &buf_last1_in_out | |
902 | , Compare comp | |
903 | , Op op | |
904 | , bool is_stable) | |
905 | { | |
906 | return is_stable | |
907 | ? op_partial_merge_and_save_impl | |
908 | (first1, last1, rfirst2, last2, first_min, buf_first1_in_out, buf_last1_in_out, comp, op) | |
909 | : op_partial_merge_and_save_impl | |
910 | (first1, last1, rfirst2, last2, first_min, buf_first1_in_out, buf_last1_in_out, antistable<Compare>(comp), op) | |
911 | ; | |
912 | } | |
913 | ||
11fdf7f2 TL |
914 | ////////////////////////////////// |
915 | ////////////////////////////////// | |
916 | ////////////////////////////////// | |
917 | // | |
918 | // op_merge_blocks_with_irreg | |
919 | // | |
920 | ////////////////////////////////// | |
921 | ////////////////////////////////// | |
922 | ////////////////////////////////// | |
923 | ||
924 | template<class RandItKeys, class KeyCompare, class RandIt, class RandIt2, class OutputIt, class Compare, class Op> | |
925 | OutputIt op_merge_blocks_with_irreg | |
926 | ( RandItKeys key_first | |
927 | , RandItKeys key_mid | |
928 | , KeyCompare key_comp | |
b32b8144 FG |
929 | , RandIt first_reg |
930 | , RandIt2 &first_irr | |
931 | , RandIt2 const last_irr | |
932 | , OutputIt dest | |
933 | , typename iterator_traits<RandIt>::size_type const l_block | |
934 | , typename iterator_traits<RandIt>::size_type n_block_left | |
935 | , typename iterator_traits<RandIt>::size_type min_check | |
936 | , typename iterator_traits<RandIt>::size_type max_check | |
937 | , Compare comp, bool const is_stable, Op op) | |
938 | { | |
939 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
940 | ||
941 | for(; n_block_left; --n_block_left, ++key_first, min_check -= min_check != 0, max_check -= max_check != 0){ | |
942 | size_type next_key_idx = find_next_block(key_first, key_comp, first_reg, l_block, min_check, max_check, comp); | |
92f5a8d4 | 943 | max_check = min_value<size_type>(max_value<size_type>(max_check, next_key_idx+size_type(2)), n_block_left); |
b32b8144 FG |
944 | RandIt const last_reg = first_reg + l_block; |
945 | RandIt first_min = first_reg + next_key_idx*l_block; | |
946 | RandIt const last_min = first_min + l_block; (void)last_min; | |
947 | ||
92f5a8d4 TL |
948 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first_reg, last_reg, comp)); |
949 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!next_key_idx || boost::movelib::is_sorted(first_min, last_min, comp)); | |
b32b8144 FG |
950 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT((!next_key_idx || !comp(*first_reg, *first_min ))); |
951 | ||
952 | OutputIt orig_dest = dest; (void)orig_dest; | |
953 | dest = next_key_idx ? op_partial_merge_and_swap(first_irr, last_irr, first_reg, last_reg, first_min, dest, comp, op, is_stable) | |
954 | : op_partial_merge (first_irr, last_irr, first_reg, last_reg, dest, comp, op, is_stable); | |
92f5a8d4 | 955 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(orig_dest, dest, comp)); |
b32b8144 FG |
956 | |
957 | if(first_reg == dest){ | |
958 | dest = next_key_idx ? ::boost::adl_move_swap_ranges(first_min, last_min, first_reg) | |
959 | : last_reg; | |
960 | } | |
961 | else{ | |
962 | dest = next_key_idx ? op(three_way_forward_t(), first_reg, last_reg, first_min, dest) | |
963 | : op(forward_t(), first_reg, last_reg, dest); | |
964 | } | |
965 | ||
966 | RandItKeys const key_next(key_first + next_key_idx); | |
967 | swap_and_update_key(key_next, key_first, key_mid, last_reg, last_reg, first_min); | |
968 | ||
92f5a8d4 | 969 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(orig_dest, dest, comp)); |
b32b8144 FG |
970 | first_reg = last_reg; |
971 | } | |
972 | return dest; | |
973 | } | |
974 | ||
11fdf7f2 TL |
975 | ////////////////////////////////// |
976 | ////////////////////////////////// | |
977 | ////////////////////////////////// | |
978 | // | |
979 | // op_merge_blocks_left/right | |
980 | // | |
981 | ////////////////////////////////// | |
982 | ////////////////////////////////// | |
983 | ////////////////////////////////// | |
984 | ||
b32b8144 FG |
985 | template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class Op> |
986 | void op_merge_blocks_left | |
7c673cae | 987 | ( RandItKeys const key_first |
7c673cae FG |
988 | , KeyCompare key_comp |
989 | , RandIt const first | |
990 | , typename iterator_traits<RandIt>::size_type const l_block | |
991 | , typename iterator_traits<RandIt>::size_type const l_irreg1 | |
b32b8144 FG |
992 | , typename iterator_traits<RandIt>::size_type const n_block_a |
993 | , typename iterator_traits<RandIt>::size_type const n_block_b | |
7c673cae | 994 | , typename iterator_traits<RandIt>::size_type const l_irreg2 |
b32b8144 | 995 | , Compare comp, Op op) |
7c673cae | 996 | { |
b32b8144 FG |
997 | typedef typename iterator_traits<RandIt>::size_type size_type; |
998 | size_type const key_count = needed_keys_count(n_block_a, n_block_b); (void)key_count; | |
999 | // BOOST_ASSERT(n_block_a || n_block_b); | |
11fdf7f2 | 1000 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted_and_unique(key_first, key_first + key_count, key_comp)); |
b32b8144 FG |
1001 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_first + key_count, key_comp, key_first[n_block_a])); |
1002 | ||
1003 | size_type n_block_b_left = n_block_b; | |
1004 | size_type n_block_a_left = n_block_a; | |
1005 | size_type n_block_left = n_block_b + n_block_a; | |
1006 | RandItKeys key_mid(key_first + n_block_a); | |
1007 | ||
1008 | RandIt buffer = first - l_block; | |
1009 | RandIt first1 = first; | |
1010 | RandIt last1 = first1 + l_irreg1; | |
1011 | RandIt first2 = last1; | |
1012 | RandIt const irreg2 = first2 + n_block_left*l_block; | |
1013 | bool is_range1_A = true; | |
1014 | ||
1015 | RandItKeys key_range2(key_first); | |
1016 | ||
1017 | //////////////////////////////////////////////////////////////////////////// | |
1018 | //Process all regular blocks before the irregular B block | |
1019 | //////////////////////////////////////////////////////////////////////////// | |
1020 | size_type min_check = n_block_a == n_block_left ? 0u : n_block_a; | |
92f5a8d4 | 1021 | size_type max_check = min_value<size_type>(min_check+size_type(1), n_block_left); |
b32b8144 FG |
1022 | for (; n_block_left; --n_block_left, ++key_range2, min_check -= min_check != 0, max_check -= max_check != 0) { |
1023 | size_type const next_key_idx = find_next_block(key_range2, key_comp, first2, l_block, min_check, max_check, comp); | |
92f5a8d4 | 1024 | max_check = min_value<size_type>(max_value<size_type>(max_check, next_key_idx+size_type(2)), n_block_left); |
b32b8144 FG |
1025 | RandIt const first_min = first2 + next_key_idx*l_block; |
1026 | RandIt const last_min = first_min + l_block; (void)last_min; | |
1027 | RandIt const last2 = first2 + l_block; | |
1028 | ||
92f5a8d4 TL |
1029 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first1, last1, comp)); |
1030 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first2, last2, comp)); | |
1031 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_left || boost::movelib::is_sorted(first_min, last_min, comp)); | |
b32b8144 FG |
1032 | |
1033 | //Check if irregular b block should go here. | |
1034 | //If so, break to the special code handling the irregular block | |
1035 | if (!n_block_b_left && | |
1036 | ( (l_irreg2 && comp(*irreg2, *first_min)) || (!l_irreg2 && is_range1_A)) ){ | |
1037 | break; | |
1038 | } | |
1039 | ||
1040 | RandItKeys const key_next(key_range2 + next_key_idx); | |
1041 | bool const is_range2_A = key_mid == (key_first+key_count) || key_comp(*key_next, *key_mid); | |
1042 | ||
1043 | bool const is_buffer_middle = last1 == buffer; | |
1044 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT( ( is_buffer_middle && size_type(first2-buffer) == l_block && buffer == last1) || | |
1045 | (!is_buffer_middle && size_type(first1-buffer) == l_block && first2 == last1)); | |
1046 | ||
1047 | if(is_range1_A == is_range2_A){ | |
1048 | BOOST_ASSERT((first1 == last1) || !comp(*first_min, last1[-1])); | |
1049 | if(!is_buffer_middle){ | |
1050 | buffer = op(forward_t(), first1, last1, buffer); | |
1051 | } | |
1052 | swap_and_update_key(key_next, key_range2, key_mid, first2, last2, first_min); | |
1053 | first1 = first2; | |
1054 | last1 = last2; | |
1055 | } | |
1056 | else { | |
1057 | RandIt unmerged; | |
1058 | RandIt buf_beg; | |
1059 | RandIt buf_end; | |
1060 | if(is_buffer_middle){ | |
1061 | buf_end = buf_beg = first2 - (last1-first1); | |
1062 | unmerged = op_partial_merge_and_save( first1, last1, first2, last2, first_min | |
1063 | , buf_beg, buf_end, comp, op, is_range1_A); | |
1064 | } | |
1065 | else{ | |
1066 | buf_beg = first1; | |
1067 | buf_end = last1; | |
1068 | unmerged = op_partial_merge_and_save | |
1069 | (buffer, buffer+(last1-first1), first2, last2, first_min, buf_beg, buf_end, comp, op, is_range1_A); | |
1070 | } | |
1071 | (void)unmerged; | |
92f5a8d4 | 1072 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first-l_block, unmerged, comp)); |
b32b8144 FG |
1073 | |
1074 | swap_and_update_key( key_next, key_range2, key_mid, first2, last2 | |
1075 | , last_min - size_type(last2 - first2)); | |
1076 | ||
1077 | if(buf_beg != buf_end){ //range2 exhausted: is_buffer_middle for the next iteration | |
1078 | first1 = buf_beg; | |
1079 | last1 = buf_end; | |
1080 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(buf_end == (last2-l_block)); | |
1081 | buffer = last1; | |
1082 | } | |
1083 | else{ //range1 exhausted: !is_buffer_middle for the next iteration | |
1084 | first1 = first2; | |
1085 | last1 = last2; | |
1086 | buffer = first2 - l_block; | |
1087 | is_range1_A = is_range2_A; | |
1088 | } | |
1089 | } | |
1090 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT( (is_range2_A && n_block_a_left) || (!is_range2_A && n_block_b_left)); | |
1091 | is_range2_A ? --n_block_a_left : --n_block_b_left; | |
1092 | first2 = last2; | |
7c673cae | 1093 | } |
b32b8144 FG |
1094 | |
1095 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_range2 + n_block_left, key_comp, *key_mid)); | |
1096 | BOOST_ASSERT(!n_block_b_left); | |
1097 | ||
1098 | //////////////////////////////////////////////////////////////////////////// | |
1099 | //Process remaining range 1 left before the irregular B block | |
1100 | //////////////////////////////////////////////////////////////////////////// | |
1101 | bool const is_buffer_middle = last1 == buffer; | |
1102 | RandIt first_irr2 = irreg2; | |
1103 | RandIt const last_irr2 = first_irr2 + l_irreg2; | |
1104 | if(l_irreg2 && is_range1_A){ | |
1105 | if(is_buffer_middle){ | |
1106 | first1 = skip_until_merge(first1, last1, *first_irr2, comp); | |
1107 | //Even if we copy backward, no overlapping occurs so use forward copy | |
1108 | //that can be faster specially with trivial types | |
1109 | RandIt const new_first1 = first2 - (last1 - first1); | |
1110 | op(forward_t(), first1, last1, new_first1); | |
1111 | first1 = new_first1; | |
1112 | last1 = first2; | |
1113 | buffer = first1 - l_block; | |
1114 | } | |
1115 | buffer = op_partial_merge_impl(first1, last1, first_irr2, last_irr2, buffer, comp, op); | |
1116 | buffer = op(forward_t(), first1, last1, buffer); | |
7c673cae | 1117 | } |
b32b8144 FG |
1118 | else if(!is_buffer_middle){ |
1119 | buffer = op(forward_t(), first1, last1, buffer); | |
1120 | } | |
92f5a8d4 | 1121 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first-l_block, buffer, comp)); |
7c673cae | 1122 | |
b32b8144 FG |
1123 | //////////////////////////////////////////////////////////////////////////// |
1124 | //Process irregular B block and remaining A blocks | |
1125 | //////////////////////////////////////////////////////////////////////////// | |
1126 | buffer = op_merge_blocks_with_irreg | |
1127 | ( key_range2, key_mid, key_comp, first2, first_irr2, last_irr2 | |
1128 | , buffer, l_block, n_block_left, min_check, max_check, comp, false, op); | |
1129 | buffer = op(forward_t(), first_irr2, last_irr2, buffer);(void)buffer; | |
92f5a8d4 | 1130 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first-l_block, buffer, comp)); |
b32b8144 | 1131 | } |
7c673cae FG |
1132 | |
1133 | // first - first element to merge. | |
b32b8144 | 1134 | // first[-l_block, 0) - buffer (if use_buf == true) |
7c673cae FG |
1135 | // l_block - length of regular blocks. First nblocks are stable sorted by 1st elements and key-coded |
1136 | // keys - sequence of keys, in same order as blocks. key<midkey means stream A | |
1137 | // n_bef_irreg2/n_aft_irreg2 are regular blocks | |
1138 | // l_irreg2 is a irregular block, that is to be combined after n_bef_irreg2 blocks and before n_aft_irreg2 blocks | |
1139 | // If l_irreg2==0 then n_aft_irreg2==0 (no irregular blocks). | |
1140 | template<class RandItKeys, class KeyCompare, class RandIt, class Compare> | |
b32b8144 | 1141 | void merge_blocks_left |
7c673cae | 1142 | ( RandItKeys const key_first |
7c673cae FG |
1143 | , KeyCompare key_comp |
1144 | , RandIt const first | |
1145 | , typename iterator_traits<RandIt>::size_type const l_block | |
b32b8144 FG |
1146 | , typename iterator_traits<RandIt>::size_type const l_irreg1 |
1147 | , typename iterator_traits<RandIt>::size_type const n_block_a | |
1148 | , typename iterator_traits<RandIt>::size_type const n_block_b | |
7c673cae FG |
1149 | , typename iterator_traits<RandIt>::size_type const l_irreg2 |
1150 | , Compare comp | |
1151 | , bool const xbuf_used) | |
1152 | { | |
b32b8144 | 1153 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_first + needed_keys_count(n_block_a, n_block_b), key_comp, key_first[n_block_a])); |
7c673cae | 1154 | if(xbuf_used){ |
b32b8144 FG |
1155 | op_merge_blocks_left |
1156 | (key_first, key_comp, first, l_block, l_irreg1, n_block_a, n_block_b, l_irreg2, comp, move_op()); | |
1157 | } | |
1158 | else{ | |
1159 | op_merge_blocks_left | |
1160 | (key_first, key_comp, first, l_block, l_irreg1, n_block_a, n_block_b, l_irreg2, comp, swap_op()); | |
7c673cae | 1161 | } |
7c673cae FG |
1162 | } |
1163 | ||
b32b8144 FG |
1164 | // first - first element to merge. |
1165 | // [first+l_block*(n_bef_irreg2+n_aft_irreg2)+l_irreg2, first+l_block*(n_bef_irreg2+n_aft_irreg2+1)+l_irreg2) - buffer | |
1166 | // l_block - length of regular blocks. First nblocks are stable sorted by 1st elements and key-coded | |
1167 | // keys - sequence of keys, in same order as blocks. key<midkey means stream A | |
1168 | // n_bef_irreg2/n_aft_irreg2 are regular blocks | |
1169 | // l_irreg2 is a irregular block, that is to be combined after n_bef_irreg2 blocks and before n_aft_irreg2 blocks | |
1170 | // If l_irreg2==0 then n_aft_irreg2==0 (no irregular blocks). | |
1171 | template<class RandItKeys, class KeyCompare, class RandIt, class Compare> | |
1172 | void merge_blocks_right | |
1173 | ( RandItKeys const key_first | |
7c673cae FG |
1174 | , KeyCompare key_comp |
1175 | , RandIt const first | |
7c673cae | 1176 | , typename iterator_traits<RandIt>::size_type const l_block |
b32b8144 FG |
1177 | , typename iterator_traits<RandIt>::size_type const n_block_a |
1178 | , typename iterator_traits<RandIt>::size_type const n_block_b | |
1179 | , typename iterator_traits<RandIt>::size_type const l_irreg2 | |
7c673cae | 1180 | , Compare comp |
b32b8144 | 1181 | , bool const xbuf_used) |
7c673cae | 1182 | { |
b32b8144 FG |
1183 | merge_blocks_left |
1184 | ( (make_reverse_iterator)(key_first + needed_keys_count(n_block_a, n_block_b)) | |
1185 | , inverse<KeyCompare>(key_comp) | |
1186 | , (make_reverse_iterator)(first + ((n_block_a+n_block_b)*l_block+l_irreg2)) | |
1187 | , l_block | |
1188 | , l_irreg2 | |
1189 | , n_block_b | |
1190 | , n_block_a | |
1191 | , 0 | |
1192 | , inverse<Compare>(comp), xbuf_used); | |
1193 | } | |
7c673cae | 1194 | |
11fdf7f2 TL |
1195 | ////////////////////////////////// |
1196 | ////////////////////////////////// | |
1197 | ////////////////////////////////// | |
1198 | // | |
1199 | // op_merge_blocks_with_buf | |
1200 | // | |
1201 | ////////////////////////////////// | |
1202 | ////////////////////////////////// | |
1203 | ////////////////////////////////// | |
b32b8144 FG |
1204 | template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class Op, class RandItBuf> |
1205 | void op_merge_blocks_with_buf | |
1206 | ( RandItKeys key_first | |
1207 | , KeyCompare key_comp | |
1208 | , RandIt const first | |
1209 | , typename iterator_traits<RandIt>::size_type const l_block | |
1210 | , typename iterator_traits<RandIt>::size_type const l_irreg1 | |
1211 | , typename iterator_traits<RandIt>::size_type const n_block_a | |
1212 | , typename iterator_traits<RandIt>::size_type const n_block_b | |
1213 | , typename iterator_traits<RandIt>::size_type const l_irreg2 | |
1214 | , Compare comp | |
1215 | , Op op | |
1216 | , RandItBuf const buf_first) | |
1217 | { | |
1218 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
1219 | size_type const key_count = needed_keys_count(n_block_a, n_block_b); (void)key_count; | |
1220 | //BOOST_ASSERT(n_block_a || n_block_b); | |
11fdf7f2 | 1221 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted_and_unique(key_first, key_first + key_count, key_comp)); |
b32b8144 FG |
1222 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_first + key_count, key_comp, key_first[n_block_a])); |
1223 | ||
1224 | size_type n_block_b_left = n_block_b; | |
1225 | size_type n_block_a_left = n_block_a; | |
1226 | size_type n_block_left = n_block_b + n_block_a; | |
1227 | RandItKeys key_mid(key_first + n_block_a); | |
1228 | ||
1229 | RandItBuf buffer = buf_first; | |
1230 | RandItBuf buffer_end = buffer; | |
1231 | RandIt first1 = first; | |
1232 | RandIt last1 = first1 + l_irreg1; | |
1233 | RandIt first2 = last1; | |
1234 | RandIt const first_irr2 = first2 + n_block_left*l_block; | |
1235 | bool is_range1_A = true; | |
92f5a8d4 | 1236 | const size_type len = l_block * n_block_a + l_block * n_block_b + l_irreg1 + l_irreg2; (void)len; |
7c673cae | 1237 | |
b32b8144 | 1238 | RandItKeys key_range2(key_first); |
7c673cae | 1239 | |
b32b8144 FG |
1240 | //////////////////////////////////////////////////////////////////////////// |
1241 | //Process all regular blocks before the irregular B block | |
1242 | //////////////////////////////////////////////////////////////////////////// | |
1243 | size_type min_check = n_block_a == n_block_left ? 0u : n_block_a; | |
92f5a8d4 | 1244 | size_type max_check = min_value<size_type>(min_check+size_type(1), n_block_left); |
b32b8144 FG |
1245 | for (; n_block_left; --n_block_left, ++key_range2, min_check -= min_check != 0, max_check -= max_check != 0) { |
1246 | size_type const next_key_idx = find_next_block(key_range2, key_comp, first2, l_block, min_check, max_check, comp); | |
92f5a8d4 | 1247 | max_check = min_value<size_type>(max_value<size_type>(max_check, next_key_idx+size_type(2)), n_block_left); |
b32b8144 FG |
1248 | RandIt first_min = first2 + next_key_idx*l_block; |
1249 | RandIt const last_min = first_min + l_block; (void)last_min; | |
1250 | RandIt const last2 = first2 + l_block; | |
7c673cae | 1251 | |
b32b8144 | 1252 | bool const buffer_empty = buffer == buffer_end; (void)buffer_empty; |
92f5a8d4 TL |
1253 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(buffer_empty ? boost::movelib::is_sorted(first1, last1, comp) : boost::movelib::is_sorted(buffer, buffer_end, comp)); |
1254 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first2, last2, comp)); | |
1255 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_left || boost::movelib::is_sorted(first_min, last_min, comp)); | |
7c673cae | 1256 | |
b32b8144 FG |
1257 | //Check if irregular b block should go here. |
1258 | //If so, break to the special code handling the irregular block | |
1259 | if (!n_block_b_left && | |
1260 | ( (l_irreg2 && comp(*first_irr2, *first_min)) || (!l_irreg2 && is_range1_A)) ){ | |
1261 | break; | |
1262 | } | |
1263 | ||
1264 | RandItKeys const key_next(key_range2 + next_key_idx); | |
1265 | bool const is_range2_A = key_mid == (key_first+key_count) || key_comp(*key_next, *key_mid); | |
1266 | ||
1267 | if(is_range1_A == is_range2_A){ | |
1268 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT((first1 == last1) || (buffer_empty ? !comp(*first_min, last1[-1]) : !comp(*first_min, buffer_end[-1]))); | |
1269 | //If buffered, put those elements in place | |
1270 | RandIt res = op(forward_t(), buffer, buffer_end, first1); | |
92f5a8d4 | 1271 | BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" merge_blocks_w_fwd: ", len); |
b32b8144 FG |
1272 | buffer = buffer_end = buf_first; |
1273 | BOOST_ASSERT(buffer_empty || res == last1); (void)res; | |
92f5a8d4 TL |
1274 | //swap_and_update_key(key_next, key_range2, key_mid, first2, last2, first_min); |
1275 | buffer_end = buffer_and_update_key(key_next, key_range2, key_mid, first2, last2, first_min, buffer = buf_first, op); | |
1276 | BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" merge_blocks_w_swp: ", len); | |
1277 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first2, last2, comp)); | |
1278 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first_min, last_min, comp)); | |
b32b8144 | 1279 | first1 = first2; |
92f5a8d4 | 1280 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, first1, comp)); |
b32b8144 FG |
1281 | } |
1282 | else { | |
1283 | RandIt const unmerged = op_partial_merge_and_save(first1, last1, first2, last2, first_min, buffer, buffer_end, comp, op, is_range1_A); | |
92f5a8d4 | 1284 | BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" merge_blocks_w_mrs: ", len); |
b32b8144 FG |
1285 | bool const is_range_1_empty = buffer == buffer_end; |
1286 | BOOST_ASSERT(is_range_1_empty || (buffer_end-buffer) == (last1+l_block-unmerged)); | |
1287 | if(is_range_1_empty){ | |
1288 | buffer = buffer_end = buf_first; | |
1289 | first_min = last_min - (last2 - first2); | |
92f5a8d4 TL |
1290 | //swap_and_update_key(key_next, key_range2, key_mid, first2, last2, first_min); |
1291 | buffer_end = buffer_and_update_key(key_next, key_range2, key_mid, first2, last2, first_min, buf_first, op); | |
7c673cae FG |
1292 | } |
1293 | else{ | |
b32b8144 | 1294 | first_min = last_min; |
92f5a8d4 TL |
1295 | //swap_and_update_key(key_next, key_range2, key_mid, first2, last2, first_min); |
1296 | update_key(key_next, key_range2, key_mid); | |
7c673cae | 1297 | } |
b32b8144 | 1298 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!is_range_1_empty || (last_min-first_min) == (last2-unmerged)); |
92f5a8d4 TL |
1299 | BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" merge_blocks_w_swp: ", len); |
1300 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first_min, last_min, comp)); | |
b32b8144 FG |
1301 | is_range1_A ^= is_range_1_empty; |
1302 | first1 = unmerged; | |
92f5a8d4 | 1303 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, unmerged, comp)); |
b32b8144 FG |
1304 | } |
1305 | BOOST_ASSERT( (is_range2_A && n_block_a_left) || (!is_range2_A && n_block_b_left)); | |
1306 | is_range2_A ? --n_block_a_left : --n_block_b_left; | |
1307 | last1 += l_block; | |
1308 | first2 = last2; | |
1309 | } | |
b32b8144 | 1310 | RandIt res = op(forward_t(), buffer, buffer_end, first1); (void)res; |
92f5a8d4 TL |
1311 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, res, comp)); |
1312 | BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" merge_blocks_w_fwd: ", len); | |
b32b8144 FG |
1313 | |
1314 | //////////////////////////////////////////////////////////////////////////// | |
1315 | //Process irregular B block and remaining A blocks | |
1316 | //////////////////////////////////////////////////////////////////////////// | |
1317 | RandIt const last_irr2 = first_irr2 + l_irreg2; | |
1318 | op(forward_t(), first_irr2, first_irr2+l_irreg2, buf_first); | |
92f5a8d4 | 1319 | BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" merge_blocks_w_fwir:", len); |
b32b8144 FG |
1320 | buffer = buf_first; |
1321 | buffer_end = buffer+l_irreg2; | |
1322 | ||
1323 | reverse_iterator<RandItBuf> rbuf_beg(buffer_end); | |
1324 | RandIt dest = op_merge_blocks_with_irreg | |
1325 | ((make_reverse_iterator)(key_first + n_block_b + n_block_a), (make_reverse_iterator)(key_mid), inverse<KeyCompare>(key_comp) | |
92f5a8d4 | 1326 | , (make_reverse_iterator)(first_irr2), rbuf_beg, (make_reverse_iterator)(buffer), (make_reverse_iterator)(last_irr2) |
b32b8144 FG |
1327 | , l_block, n_block_left, 0, n_block_left |
1328 | , inverse<Compare>(comp), true, op).base(); | |
92f5a8d4 TL |
1329 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(dest, last_irr2, comp)); |
1330 | BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" merge_blocks_w_irg: ", len); | |
b32b8144 FG |
1331 | |
1332 | buffer_end = rbuf_beg.base(); | |
1333 | BOOST_ASSERT((dest-last1) == (buffer_end-buffer)); | |
1334 | op_merge_with_left_placed(is_range1_A ? first1 : last1, last1, dest, buffer, buffer_end, comp, op); | |
92f5a8d4 TL |
1335 | BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" merge_with_left_plc:", len); |
1336 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(first, last_irr2, comp)); | |
7c673cae FG |
1337 | } |
1338 | ||
11fdf7f2 TL |
1339 | ////////////////////////////////// |
1340 | ////////////////////////////////// | |
1341 | ////////////////////////////////// | |
1342 | // | |
1343 | // op_insertion_sort_step_left/right | |
1344 | // | |
1345 | ////////////////////////////////// | |
1346 | ////////////////////////////////// | |
1347 | ////////////////////////////////// | |
7c673cae FG |
1348 | |
1349 | template<class RandIt, class Compare, class Op> | |
1350 | typename iterator_traits<RandIt>::size_type | |
1351 | op_insertion_sort_step_left | |
1352 | ( RandIt const first | |
1353 | , typename iterator_traits<RandIt>::size_type const length | |
1354 | , typename iterator_traits<RandIt>::size_type const step | |
1355 | , Compare comp, Op op) | |
1356 | { | |
1357 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
1358 | size_type const s = min_value<size_type>(step, AdaptiveSortInsertionSortThreshold); | |
1359 | size_type m = 0; | |
1360 | ||
1361 | while((length - m) > s){ | |
1362 | insertion_sort_op(first+m, first+m+s, first+m-s, comp, op); | |
1363 | m += s; | |
1364 | } | |
1365 | insertion_sort_op(first+m, first+length, first+m-s, comp, op); | |
1366 | return s; | |
1367 | } | |
1368 | ||
11fdf7f2 TL |
1369 | template<class RandIt, class Compare, class Op> |
1370 | void op_merge_right_step_once | |
1371 | ( RandIt first_block | |
1372 | , typename iterator_traits<RandIt>::size_type const elements_in_blocks | |
1373 | , typename iterator_traits<RandIt>::size_type const l_build_buf | |
1374 | , Compare comp | |
1375 | , Op op) | |
1376 | { | |
1377 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
1378 | size_type restk = elements_in_blocks%(2*l_build_buf); | |
1379 | size_type p = elements_in_blocks - restk; | |
1380 | BOOST_ASSERT(0 == (p%(2*l_build_buf))); | |
1381 | ||
1382 | if(restk <= l_build_buf){ | |
1383 | op(backward_t(),first_block+p, first_block+p+restk, first_block+p+restk+l_build_buf); | |
1384 | } | |
1385 | else{ | |
1386 | op_merge_right(first_block+p, first_block+p+l_build_buf, first_block+p+restk, first_block+p+restk+l_build_buf, comp, op); | |
1387 | } | |
1388 | while(p>0){ | |
1389 | p -= 2*l_build_buf; | |
1390 | op_merge_right(first_block+p, first_block+p+l_build_buf, first_block+p+2*l_build_buf, first_block+p+3*l_build_buf, comp, op); | |
1391 | } | |
1392 | } | |
1393 | ||
1394 | ||
1395 | ////////////////////////////////// | |
1396 | ////////////////////////////////// | |
1397 | ////////////////////////////////// | |
1398 | // | |
1399 | // insertion_sort_step | |
1400 | // | |
1401 | ////////////////////////////////// | |
1402 | ////////////////////////////////// | |
1403 | ////////////////////////////////// | |
7c673cae FG |
1404 | template<class RandIt, class Compare> |
1405 | typename iterator_traits<RandIt>::size_type | |
1406 | insertion_sort_step | |
1407 | ( RandIt const first | |
1408 | , typename iterator_traits<RandIt>::size_type const length | |
1409 | , typename iterator_traits<RandIt>::size_type const step | |
1410 | , Compare comp) | |
1411 | { | |
1412 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
1413 | size_type const s = min_value<size_type>(step, AdaptiveSortInsertionSortThreshold); | |
1414 | size_type m = 0; | |
1415 | ||
1416 | while((length - m) > s){ | |
1417 | insertion_sort(first+m, first+m+s, comp); | |
1418 | m += s; | |
1419 | } | |
1420 | insertion_sort(first+m, first+length, comp); | |
1421 | return s; | |
1422 | } | |
1423 | ||
11fdf7f2 TL |
1424 | ////////////////////////////////// |
1425 | ////////////////////////////////// | |
1426 | ////////////////////////////////// | |
1427 | // | |
1428 | // op_merge_left_step_multiple | |
1429 | // | |
1430 | ////////////////////////////////// | |
1431 | ////////////////////////////////// | |
1432 | ////////////////////////////////// | |
7c673cae FG |
1433 | template<class RandIt, class Compare, class Op> |
1434 | typename iterator_traits<RandIt>::size_type | |
b32b8144 | 1435 | op_merge_left_step_multiple |
7c673cae FG |
1436 | ( RandIt first_block |
1437 | , typename iterator_traits<RandIt>::size_type const elements_in_blocks | |
1438 | , typename iterator_traits<RandIt>::size_type l_merged | |
1439 | , typename iterator_traits<RandIt>::size_type const l_build_buf | |
1440 | , typename iterator_traits<RandIt>::size_type l_left_space | |
1441 | , Compare comp | |
1442 | , Op op) | |
1443 | { | |
1444 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
1445 | for(; l_merged < l_build_buf && l_left_space >= l_merged; l_merged*=2){ | |
1446 | size_type p0=0; | |
1447 | RandIt pos = first_block; | |
1448 | while((elements_in_blocks - p0) > 2*l_merged) { | |
1449 | op_merge_left(pos-l_merged, pos, pos+l_merged, pos+2*l_merged, comp, op); | |
92f5a8d4 | 1450 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(pos-l_merged, pos+l_merged, comp)); |
7c673cae FG |
1451 | p0 += 2*l_merged; |
1452 | pos = first_block+p0; | |
1453 | } | |
1454 | if((elements_in_blocks-p0) > l_merged) { | |
1455 | op_merge_left(pos-l_merged, pos, pos+l_merged, first_block+elements_in_blocks, comp, op); | |
92f5a8d4 | 1456 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(pos-l_merged, pos-l_merged+(first_block+elements_in_blocks-pos), comp)); |
7c673cae FG |
1457 | } |
1458 | else { | |
1459 | op(forward_t(), pos, first_block+elements_in_blocks, pos-l_merged); | |
92f5a8d4 | 1460 | BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted(pos-l_merged, first_block+elements_in_blocks-l_merged, comp)); |
7c673cae FG |
1461 | } |
1462 | first_block -= l_merged; | |
1463 | l_left_space -= l_merged; | |
1464 | } | |
1465 | return l_merged; | |
1466 | } | |
1467 | ||
b32b8144 | 1468 | |
7c673cae FG |
1469 | } //namespace detail_adaptive { |
1470 | } //namespace movelib { | |
1471 | } //namespace boost { | |
1472 | ||
1473 | #include <boost/move/detail/config_end.hpp> | |
1474 | ||
1475 | #endif //#define BOOST_MOVE_ADAPTIVE_SORT_MERGE_HPP |