00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
00040 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
00041
00042 #include <vector>
00043
00044 #include <bits/stl_algo.h>
00045 #include <parallel/features.h>
00046 #include <parallel/parallel.h>
00047 #include <parallel/losertree.h>
00048 #if _GLIBCXX_ASSERTIONS
00049 #include <parallel/checkers.h>
00050 #endif
00051
00052
00053 #define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first)
00054
00055 namespace __gnu_parallel
00056 {
00057
00058
00059
00060
00061
00062
00063
00064
00065 template<typename _RAIter, typename _Compare>
00066 class _GuardedIterator
00067 {
00068 private:
00069
00070 _RAIter _M_current;
00071
00072
00073 _RAIter _M_end;
00074
00075
00076 _Compare& __comp;
00077
00078 public:
00079
00080
00081
00082
00083
00084 _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp)
00085 : _M_current(__begin), _M_end(__end), __comp(__comp)
00086 { }
00087
00088
00089
00090 _GuardedIterator<_RAIter, _Compare>&
00091 operator++()
00092 {
00093 ++_M_current;
00094 return *this;
00095 }
00096
00097
00098
00099 typename std::iterator_traits<_RAIter>::value_type&
00100 operator*()
00101 { return *_M_current; }
00102
00103
00104
00105 operator _RAIter()
00106 { return _M_current; }
00107
00108
00109
00110
00111
00112 friend bool
00113 operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
00114 _GuardedIterator<_RAIter, _Compare>& __bi2)
00115 {
00116 if (__bi1._M_current == __bi1._M_end)
00117 return __bi2._M_current == __bi2._M_end;
00118 if (__bi2._M_current == __bi2._M_end)
00119 return true;
00120 return (__bi1.__comp)(*__bi1, *__bi2);
00121 }
00122
00123
00124
00125
00126
00127 friend bool
00128 operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
00129 _GuardedIterator<_RAIter, _Compare>& __bi2)
00130 {
00131 if (__bi2._M_current == __bi2._M_end)
00132 return __bi1._M_current != __bi1._M_end;
00133 if (__bi1._M_current == __bi1._M_end)
00134 return false;
00135 return !(__bi1.__comp)(*__bi2, *__bi1);
00136 }
00137 };
00138
00139 template<typename _RAIter, typename _Compare>
00140 class _UnguardedIterator
00141 {
00142 private:
00143
00144 _RAIter _M_current;
00145
00146 _Compare& __comp;
00147
00148 public:
00149
00150
00151
00152
00153 _UnguardedIterator(_RAIter __begin,
00154 _RAIter , _Compare& __comp)
00155 : _M_current(__begin), __comp(__comp)
00156 { }
00157
00158
00159
00160 _UnguardedIterator<_RAIter, _Compare>&
00161 operator++()
00162 {
00163 ++_M_current;
00164 return *this;
00165 }
00166
00167
00168
00169 typename std::iterator_traits<_RAIter>::value_type&
00170 operator*()
00171 { return *_M_current; }
00172
00173
00174
00175 operator _RAIter()
00176 { return _M_current; }
00177
00178
00179
00180
00181
00182 friend bool
00183 operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
00184 _UnguardedIterator<_RAIter, _Compare>& __bi2)
00185 {
00186
00187 return (__bi1.__comp)(*__bi1, *__bi2);
00188 }
00189
00190
00191
00192
00193
00194 friend bool
00195 operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
00196 _UnguardedIterator<_RAIter, _Compare>& __bi2)
00197 {
00198
00199 return !(__bi1.__comp)(*__bi2, *__bi1);
00200 }
00201 };
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228 template<template<typename RAI, typename C> class iterator,
00229 typename _RAIterIterator,
00230 typename _RAIter3,
00231 typename _DifferenceTp,
00232 typename _Compare>
00233 _RAIter3
00234 multiway_merge_3_variant(_RAIterIterator __seqs_begin,
00235 _RAIterIterator __seqs_end,
00236 _RAIter3 __target,
00237 _DifferenceTp __length, _Compare __comp)
00238 {
00239 _GLIBCXX_CALL(__length);
00240
00241 typedef _DifferenceTp _DifferenceType;
00242
00243 typedef typename std::iterator_traits<_RAIterIterator>
00244 ::value_type::first_type
00245 _RAIter1;
00246 typedef typename std::iterator_traits<_RAIter1>::value_type
00247 _ValueType;
00248
00249 if (__length == 0)
00250 return __target;
00251
00252 #if _GLIBCXX_ASSERTIONS
00253 _DifferenceTp __orig_length = __length;
00254 #endif
00255
00256 iterator<_RAIter1, _Compare>
00257 __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
00258 __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
00259 __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp);
00260
00261 if (__seq0 <= __seq1)
00262 {
00263 if (__seq1 <= __seq2)
00264 goto __s012;
00265 else
00266 if (__seq2 < __seq0)
00267 goto __s201;
00268 else
00269 goto __s021;
00270 }
00271 else
00272 {
00273 if (__seq1 <= __seq2)
00274 {
00275 if (__seq0 <= __seq2)
00276 goto __s102;
00277 else
00278 goto __s120;
00279 }
00280 else
00281 goto __s210;
00282 }
00283 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \
00284 __s ## __a ## __b ## __c : \
00285 *__target = *__seq ## __a; \
00286 ++__target; \
00287 --__length; \
00288 ++__seq ## __a; \
00289 if (__length == 0) goto __finish; \
00290 if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
00291 if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
00292 goto __s ## __b ## __c ## __a;
00293
00294 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
00295 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
00296 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
00297 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
00298 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
00299 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
00300
00301 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
00302
00303 __finish:
00304 ;
00305
00306 #if _GLIBCXX_ASSERTIONS
00307 _GLIBCXX_PARALLEL_ASSERT(
00308 ((_RAIter1)__seq0 - __seqs_begin[0].first) +
00309 ((_RAIter1)__seq1 - __seqs_begin[1].first) +
00310 ((_RAIter1)__seq2 - __seqs_begin[2].first)
00311 == __orig_length);
00312 #endif
00313
00314 __seqs_begin[0].first = __seq0;
00315 __seqs_begin[1].first = __seq1;
00316 __seqs_begin[2].first = __seq2;
00317
00318 return __target;
00319 }
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347 template<template<typename RAI, typename C> class iterator,
00348 typename _RAIterIterator,
00349 typename _RAIter3,
00350 typename _DifferenceTp,
00351 typename _Compare>
00352 _RAIter3
00353 multiway_merge_4_variant(_RAIterIterator __seqs_begin,
00354 _RAIterIterator __seqs_end,
00355 _RAIter3 __target,
00356 _DifferenceTp __length, _Compare __comp)
00357 {
00358 _GLIBCXX_CALL(__length);
00359 typedef _DifferenceTp _DifferenceType;
00360
00361 typedef typename std::iterator_traits<_RAIterIterator>
00362 ::value_type::first_type
00363 _RAIter1;
00364 typedef typename std::iterator_traits<_RAIter1>::value_type
00365 _ValueType;
00366
00367 iterator<_RAIter1, _Compare>
00368 __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
00369 __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
00370 __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp),
00371 __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp);
00372
00373 #define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \
00374 if (__seq ## __d < __seq ## __a) \
00375 goto __s ## __d ## __a ## __b ## __c; \
00376 if (__seq ## __d < __seq ## __b) \
00377 goto __s ## __a ## __d ## __b ## __c; \
00378 if (__seq ## __d < __seq ## __c) \
00379 goto __s ## __a ## __b ## __d ## __c; \
00380 goto __s ## __a ## __b ## __c ## __d; }
00381
00382 if (__seq0 <= __seq1)
00383 {
00384 if (__seq1 <= __seq2)
00385 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
00386 else
00387 if (__seq2 < __seq0)
00388 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
00389 else
00390 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
00391 }
00392 else
00393 {
00394 if (__seq1 <= __seq2)
00395 {
00396 if (__seq0 <= __seq2)
00397 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
00398 else
00399 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
00400 }
00401 else
00402 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
00403 }
00404
00405 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \
00406 __c0, __c1, __c2) \
00407 __s ## __a ## __b ## __c ## __d: \
00408 if (__length == 0) goto __finish; \
00409 *__target = *__seq ## __a; \
00410 ++__target; \
00411 --__length; \
00412 ++__seq ## __a; \
00413 if (__seq ## __a __c0 __seq ## __b) \
00414 goto __s ## __a ## __b ## __c ## __d; \
00415 if (__seq ## __a __c1 __seq ## __c) \
00416 goto __s ## __b ## __a ## __c ## __d; \
00417 if (__seq ## __a __c2 __seq ## __d) \
00418 goto __s ## __b ## __c ## __a ## __d; \
00419 goto __s ## __b ## __c ## __d ## __a;
00420
00421 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
00422 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
00423 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
00424 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
00425 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
00426 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
00427 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
00428 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
00429 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
00430 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
00431 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
00432 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
00433 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
00434 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
00435 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
00436 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
00437 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
00438 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
00439 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
00440 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
00441 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
00442 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
00443 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
00444 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
00445
00446 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
00447 #undef _GLIBCXX_PARALLEL_DECISION
00448
00449 __finish:
00450 ;
00451
00452 __seqs_begin[0].first = __seq0;
00453 __seqs_begin[1].first = __seq1;
00454 __seqs_begin[2].first = __seq2;
00455 __seqs_begin[3].first = __seq3;
00456
00457 return __target;
00458 }
00459
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478 template<typename _LT,
00479 typename _RAIterIterator,
00480 typename _RAIter3,
00481 typename _DifferenceTp,
00482 typename _Compare>
00483 _RAIter3
00484 multiway_merge_loser_tree(_RAIterIterator __seqs_begin,
00485 _RAIterIterator __seqs_end,
00486 _RAIter3 __target,
00487 _DifferenceTp __length, _Compare __comp)
00488 {
00489 _GLIBCXX_CALL(__length)
00490
00491 typedef _DifferenceTp _DifferenceType;
00492 typedef typename std::iterator_traits<_RAIterIterator>
00493 ::difference_type _SeqNumber;
00494 typedef typename std::iterator_traits<_RAIterIterator>
00495 ::value_type::first_type
00496 _RAIter1;
00497 typedef typename std::iterator_traits<_RAIter1>::value_type
00498 _ValueType;
00499
00500 _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
00501
00502 _LT __lt(__k, __comp);
00503
00504
00505 _ValueType* __arbitrary_element = 0;
00506
00507 for (_SeqNumber __t = 0; __t < __k; ++__t)
00508 {
00509 if(!__arbitrary_element
00510 && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
00511 __arbitrary_element = &(*__seqs_begin[__t].first);
00512 }
00513
00514 for (_SeqNumber __t = 0; __t < __k; ++__t)
00515 {
00516 if (__seqs_begin[__t].first == __seqs_begin[__t].second)
00517 __lt.__insert_start(*__arbitrary_element, __t, true);
00518 else
00519 __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
00520 }
00521
00522 __lt.__init();
00523
00524 _SeqNumber __source;
00525
00526 for (_DifferenceType __i = 0; __i < __length; ++__i)
00527 {
00528
00529 __source = __lt.__get_min_source();
00530
00531 *(__target++) = *(__seqs_begin[__source].first++);
00532
00533
00534 if (__seqs_begin[__source].first == __seqs_begin[__source].second)
00535 __lt.__delete_min_insert(*__arbitrary_element, true);
00536 else
00537
00538 __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
00539 }
00540
00541 return __target;
00542 }
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562 template<typename _LT,
00563 typename _RAIterIterator,
00564 typename _RAIter3,
00565 typename _DifferenceTp, typename _Compare>
00566 _RAIter3
00567 multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin,
00568 _RAIterIterator __seqs_end,
00569 _RAIter3 __target,
00570 const typename std::iterator_traits<typename std::iterator_traits<
00571 _RAIterIterator>::value_type::first_type>::value_type&
00572 __sentinel,
00573 _DifferenceTp __length,
00574 _Compare __comp)
00575 {
00576 _GLIBCXX_CALL(__length)
00577 typedef _DifferenceTp _DifferenceType;
00578
00579 typedef typename std::iterator_traits<_RAIterIterator>
00580 ::difference_type _SeqNumber;
00581 typedef typename std::iterator_traits<_RAIterIterator>
00582 ::value_type::first_type
00583 _RAIter1;
00584 typedef typename std::iterator_traits<_RAIter1>::value_type
00585 _ValueType;
00586
00587 _SeqNumber __k = __seqs_end - __seqs_begin;
00588
00589 _LT __lt(__k, __sentinel, __comp);
00590
00591 for (_SeqNumber __t = 0; __t < __k; ++__t)
00592 {
00593 #if _GLIBCXX_ASSERTIONS
00594 _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
00595 != __seqs_begin[__t].second);
00596 #endif
00597 __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
00598 }
00599
00600 __lt.__init();
00601
00602 _SeqNumber __source;
00603
00604 #if _GLIBCXX_ASSERTIONS
00605 _DifferenceType __i = 0;
00606 #endif
00607
00608 _RAIter3 __target_end = __target + __length;
00609 while (__target < __target_end)
00610 {
00611
00612 __source = __lt.__get_min_source();
00613
00614 #if _GLIBCXX_ASSERTIONS
00615 _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
00616 _GLIBCXX_PARALLEL_ASSERT(__i == 0
00617 || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
00618 #endif
00619
00620
00621 *(__target++) = *(__seqs_begin[__source].first++);
00622
00623 #if _GLIBCXX_ASSERTIONS
00624 ++__i;
00625 #endif
00626
00627 __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
00628 }
00629
00630 return __target;
00631 }
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651
00652 template<typename UnguardedLoserTree,
00653 typename _RAIterIterator,
00654 typename _RAIter3,
00655 typename _DifferenceTp,
00656 typename _Compare>
00657 _RAIter3
00658 multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin,
00659 _RAIterIterator __seqs_end,
00660 _RAIter3 __target,
00661 const typename std::iterator_traits<typename std::iterator_traits<
00662 _RAIterIterator>::value_type::first_type>::value_type&
00663 __sentinel,
00664 _DifferenceTp __length,
00665 _Compare __comp)
00666 {
00667 _GLIBCXX_CALL(__length)
00668
00669 typedef _DifferenceTp _DifferenceType;
00670 typedef std::iterator_traits<_RAIterIterator> _TraitsType;
00671 typedef typename std::iterator_traits<_RAIterIterator>
00672 ::value_type::first_type
00673 _RAIter1;
00674 typedef typename std::iterator_traits<_RAIter1>::value_type
00675 _ValueType;
00676
00677 _RAIter3 __target_end;
00678
00679 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
00680
00681
00682
00683
00684 ++((*__s).second);
00685
00686 __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree>
00687 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
00688
00689 #if _GLIBCXX_ASSERTIONS
00690 _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
00691 _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
00692 #endif
00693
00694
00695
00696 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
00697 --((*__s).second);
00698
00699 return __target_end;
00700 }
00701
00702
00703
00704
00705
00706
00707
00708
00709
00710
00711
00712
00713
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726 template <typename _Tp>
00727 struct _LoserTreeTraits
00728 {
00729
00730
00731
00732
00733
00734
00735 static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*));
00736 };
00737
00738
00739
00740
00741
00742
00743 template<bool __sentinels ,
00744 typename _RAIterIterator,
00745 typename _RAIter3,
00746 typename _DifferenceTp,
00747 typename _Compare>
00748 struct __multiway_merge_3_variant_sentinel_switch
00749 {
00750 _RAIter3
00751 operator()(_RAIterIterator __seqs_begin,
00752 _RAIterIterator __seqs_end,
00753 _RAIter3 __target,
00754 _DifferenceTp __length, _Compare __comp)
00755 { return multiway_merge_3_variant<_GuardedIterator>
00756 (__seqs_begin, __seqs_end, __target, __length, __comp); }
00757 };
00758
00759
00760
00761
00762
00763
00764 template<typename _RAIterIterator,
00765 typename _RAIter3,
00766 typename _DifferenceTp,
00767 typename _Compare>
00768 struct __multiway_merge_3_variant_sentinel_switch<true, _RAIterIterator,
00769 _RAIter3, _DifferenceTp,
00770 _Compare>
00771 {
00772 _RAIter3
00773 operator()(_RAIterIterator __seqs_begin,
00774 _RAIterIterator __seqs_end,
00775 _RAIter3 __target,
00776 _DifferenceTp __length, _Compare __comp)
00777 { return multiway_merge_3_variant<_UnguardedIterator>
00778 (__seqs_begin, __seqs_end, __target, __length, __comp); }
00779 };
00780
00781
00782
00783
00784
00785
00786 template<bool __sentinels ,
00787 typename _RAIterIterator,
00788 typename _RAIter3,
00789 typename _DifferenceTp,
00790 typename _Compare>
00791 struct __multiway_merge_4_variant_sentinel_switch
00792 {
00793 _RAIter3
00794 operator()(_RAIterIterator __seqs_begin,
00795 _RAIterIterator __seqs_end,
00796 _RAIter3 __target,
00797 _DifferenceTp __length, _Compare __comp)
00798 { return multiway_merge_4_variant<_GuardedIterator>
00799 (__seqs_begin, __seqs_end, __target, __length, __comp); }
00800 };
00801
00802
00803
00804
00805
00806
00807 template<typename _RAIterIterator,
00808 typename _RAIter3,
00809 typename _DifferenceTp,
00810 typename _Compare>
00811 struct __multiway_merge_4_variant_sentinel_switch<true, _RAIterIterator,
00812 _RAIter3, _DifferenceTp,
00813 _Compare>
00814 {
00815 _RAIter3
00816 operator()(_RAIterIterator __seqs_begin,
00817 _RAIterIterator __seqs_end,
00818 _RAIter3 __target,
00819 _DifferenceTp __length, _Compare __comp)
00820 { return multiway_merge_4_variant<_UnguardedIterator>
00821 (__seqs_begin, __seqs_end, __target, __length, __comp); }
00822 };
00823
00824
00825
00826
00827 template<bool __sentinels,
00828 bool __stable,
00829 typename _RAIterIterator,
00830 typename _RAIter3,
00831 typename _DifferenceTp,
00832 typename _Compare>
00833 struct __multiway_merge_k_variant_sentinel_switch
00834 {
00835 _RAIter3
00836 operator()(_RAIterIterator __seqs_begin,
00837 _RAIterIterator __seqs_end,
00838 _RAIter3 __target,
00839 const typename std::iterator_traits<typename std::iterator_traits<
00840 _RAIterIterator>::value_type::first_type>::value_type&
00841 __sentinel,
00842 _DifferenceTp __length, _Compare __comp)
00843 {
00844 typedef typename std::iterator_traits<_RAIterIterator>
00845 ::value_type::first_type
00846 _RAIter1;
00847 typedef typename std::iterator_traits<_RAIter1>::value_type
00848 _ValueType;
00849
00850 return multiway_merge_loser_tree_sentinel<
00851 typename __gnu_cxx::__conditional_type<
00852 _LoserTreeTraits<_ValueType>::_M_use_pointer,
00853 _LoserTreePointerUnguarded<__stable, _ValueType, _Compare>,
00854 _LoserTreeUnguarded<__stable, _ValueType, _Compare>
00855 >::__type>
00856 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
00857 }
00858 };
00859
00860
00861
00862
00863 template<bool __stable,
00864 typename _RAIterIterator,
00865 typename _RAIter3,
00866 typename _DifferenceTp,
00867 typename _Compare>
00868 struct __multiway_merge_k_variant_sentinel_switch<false, __stable,
00869 _RAIterIterator,
00870 _RAIter3, _DifferenceTp,
00871 _Compare>
00872 {
00873 _RAIter3
00874 operator()(_RAIterIterator __seqs_begin,
00875 _RAIterIterator __seqs_end,
00876 _RAIter3 __target,
00877 const typename std::iterator_traits<typename std::iterator_traits<
00878 _RAIterIterator>::value_type::first_type>::value_type&
00879 __sentinel,
00880 _DifferenceTp __length, _Compare __comp)
00881 {
00882 typedef typename std::iterator_traits<_RAIterIterator>
00883 ::value_type::first_type
00884 _RAIter1;
00885 typedef typename std::iterator_traits<_RAIter1>::value_type
00886 _ValueType;
00887
00888 return multiway_merge_loser_tree<
00889 typename __gnu_cxx::__conditional_type<
00890 _LoserTreeTraits<_ValueType>::_M_use_pointer,
00891 _LoserTreePointer<__stable, _ValueType, _Compare>,
00892 _LoserTree<__stable, _ValueType, _Compare>
00893 >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp);
00894 }
00895 };
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907
00908
00909
00910 template<bool __stable,
00911 bool __sentinels,
00912 typename _RAIterIterator,
00913 typename _RAIter3,
00914 typename _DifferenceTp,
00915 typename _Compare>
00916 _RAIter3
00917 __sequential_multiway_merge(_RAIterIterator __seqs_begin,
00918 _RAIterIterator __seqs_end,
00919 _RAIter3 __target,
00920 const typename std::iterator_traits<typename std::iterator_traits<
00921 _RAIterIterator>::value_type::first_type>::value_type&
00922 __sentinel,
00923 _DifferenceTp __length, _Compare __comp)
00924 {
00925 _GLIBCXX_CALL(__length)
00926
00927 typedef _DifferenceTp _DifferenceType;
00928 typedef typename std::iterator_traits<_RAIterIterator>
00929 ::difference_type _SeqNumber;
00930 typedef typename std::iterator_traits<_RAIterIterator>
00931 ::value_type::first_type
00932 _RAIter1;
00933 typedef typename std::iterator_traits<_RAIter1>::value_type
00934 _ValueType;
00935
00936 #if _GLIBCXX_ASSERTIONS
00937 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
00938 {
00939 _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first,
00940 (*__s).second, __comp));
00941 }
00942 #endif
00943
00944 _DifferenceTp __total_length = 0;
00945 for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
00946 __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
00947
00948 __length = std::min<_DifferenceTp>(__length, __total_length);
00949
00950 if(__length == 0)
00951 return __target;
00952
00953 _RAIter3 __return_target = __target;
00954 _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
00955
00956 switch (__k)
00957 {
00958 case 0:
00959 break;
00960 case 1:
00961 __return_target = std::copy(__seqs_begin[0].first,
00962 __seqs_begin[0].first + __length,
00963 __target);
00964 __seqs_begin[0].first += __length;
00965 break;
00966 case 2:
00967 __return_target = __merge_advance(__seqs_begin[0].first,
00968 __seqs_begin[0].second,
00969 __seqs_begin[1].first,
00970 __seqs_begin[1].second,
00971 __target, __length, __comp);
00972 break;
00973 case 3:
00974 __return_target = __multiway_merge_3_variant_sentinel_switch
00975 <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
00976 (__seqs_begin, __seqs_end, __target, __length, __comp);
00977 break;
00978 case 4:
00979 __return_target = __multiway_merge_4_variant_sentinel_switch
00980 <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
00981 (__seqs_begin, __seqs_end, __target, __length, __comp);
00982 break;
00983 default:
00984 __return_target = __multiway_merge_k_variant_sentinel_switch
00985 <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp,
00986 _Compare>()
00987 (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
00988 break;
00989 }
00990 #if _GLIBCXX_ASSERTIONS
00991 _GLIBCXX_PARALLEL_ASSERT(
00992 __is_sorted(__target, __target + __length, __comp));
00993 #endif
00994
00995 return __return_target;
00996 }
00997
00998
00999
01000
01001
01002
01003 template<bool __stable, class _RAIter, class _StrictWeakOrdering>
01004 struct _SamplingSorter
01005 {
01006 void
01007 operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
01008 { __gnu_sequential::stable_sort(__first, __last, __comp); }
01009 };
01010
01011
01012
01013
01014
01015
01016 template<class _RAIter, class _StrictWeakOrdering>
01017 struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering>
01018 {
01019 void
01020 operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
01021 { __gnu_sequential::sort(__first, __last, __comp); }
01022 };
01023
01024
01025
01026
01027 template<bool __stable,
01028 typename _RAIterIterator,
01029 typename _Compare,
01030 typename _DifferenceType>
01031 void
01032 multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin,
01033 _RAIterIterator __seqs_end,
01034 _DifferenceType __length,
01035 _DifferenceType __total_length,
01036 _Compare __comp,
01037 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
01038 {
01039 typedef typename std::iterator_traits<_RAIterIterator>
01040 ::difference_type _SeqNumber;
01041 typedef typename std::iterator_traits<_RAIterIterator>
01042 ::value_type::first_type
01043 _RAIter1;
01044 typedef typename std::iterator_traits<_RAIter1>::value_type
01045 _ValueType;
01046
01047
01048 _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
01049
01050 _ThreadIndex __num_threads = omp_get_num_threads();
01051
01052 _DifferenceType __num_samples =
01053 __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
01054
01055 _ValueType* __samples = static_cast<_ValueType*>
01056 (::operator new(sizeof(_ValueType) * __k * __num_samples));
01057
01058 for (_SeqNumber __s = 0; __s < __k; ++__s)
01059 for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
01060 {
01061 _DifferenceType sample_index = static_cast<_DifferenceType>
01062 (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
01063 * (double(__i + 1) / (__num_samples + 1))
01064 * (double(__length) / __total_length));
01065 new(&(__samples[__s * __num_samples + __i]))
01066 _ValueType(__seqs_begin[__s].first[sample_index]);
01067 }
01068
01069
01070
01071 _SamplingSorter<__stable, _ValueType*, _Compare>()
01072 (__samples, __samples + (__num_samples * __k), __comp);
01073
01074 for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
01075
01076 for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
01077 {
01078
01079 if (__slab > 0)
01080 __pieces[__slab][__seq].first = std::upper_bound
01081 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
01082 __samples[__num_samples * __k * __slab / __num_threads],
01083 __comp)
01084 - __seqs_begin[__seq].first;
01085 else
01086
01087 __pieces[__slab][__seq].first = 0;
01088 if ((__slab + 1) < __num_threads)
01089 __pieces[__slab][__seq].second = std::upper_bound
01090 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
01091 __samples[__num_samples * __k * (__slab + 1) / __num_threads],
01092 __comp)
01093 - __seqs_begin[__seq].first;
01094 else
01095
01096 __pieces[__slab][__seq].second =
01097 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
01098 }
01099 ::operator delete(__samples);
01100 }
01101
01102
01103
01104
01105
01106
01107 template<bool __stable,
01108 typename _RAIterIterator,
01109 typename _Compare,
01110 typename _DifferenceType>
01111 void
01112 multiway_merge_exact_splitting(_RAIterIterator __seqs_begin,
01113 _RAIterIterator __seqs_end,
01114 _DifferenceType __length,
01115 _DifferenceType __total_length,
01116 _Compare __comp,
01117 std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
01118 {
01119 typedef typename std::iterator_traits<_RAIterIterator>
01120 ::difference_type _SeqNumber;
01121 typedef typename std::iterator_traits<_RAIterIterator>
01122 ::value_type::first_type
01123 _RAIter1;
01124
01125 const bool __tight = (__total_length == __length);
01126
01127
01128 const _SeqNumber __k = __seqs_end - __seqs_begin;
01129
01130 const _ThreadIndex __num_threads = omp_get_num_threads();
01131
01132
01133
01134 std::vector<_RAIter1>* __offsets =
01135 new std::vector<_RAIter1>[__num_threads];
01136 std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k);
01137
01138 copy(__seqs_begin, __seqs_end, __se.begin());
01139
01140 _DifferenceType* __borders =
01141 new _DifferenceType[__num_threads + 1];
01142 equally_split(__length, __num_threads, __borders);
01143
01144 for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
01145 {
01146 __offsets[__s].resize(__k);
01147 multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
01148 __offsets[__s].begin(), __comp);
01149
01150
01151 if (!__tight)
01152 {
01153 __offsets[__num_threads - 1].resize(__k);
01154 multiseq_partition(__se.begin(), __se.end(),
01155 _DifferenceType(__length),
01156 __offsets[__num_threads - 1].begin(),
01157 __comp);
01158 }
01159 }
01160 delete[] __borders;
01161
01162 for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
01163 {
01164
01165 for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
01166 {
01167
01168 if (__slab == 0)
01169 {
01170
01171 __pieces[__slab][__seq].first = 0;
01172 }
01173 else
01174 __pieces[__slab][__seq].first =
01175 __pieces[__slab - 1][__seq].second;
01176 if (!__tight || __slab < (__num_threads - 1))
01177 __pieces[__slab][__seq].second =
01178 __offsets[__slab][__seq] - __seqs_begin[__seq].first;
01179 else
01180 {
01181
01182 __pieces[__slab][__seq].second =
01183 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
01184 }
01185 }
01186 }
01187 delete[] __offsets;
01188 }
01189
01190
01191
01192
01193
01194
01195
01196
01197
01198
01199
01200
01201
01202
01203
01204
01205
01206
01207
01208
01209 template<bool __stable,
01210 bool __sentinels,
01211 typename _RAIterIterator,
01212 typename _RAIter3,
01213 typename _DifferenceTp,
01214 typename _Splitter,
01215 typename _Compare>
01216 _RAIter3
01217 parallel_multiway_merge(_RAIterIterator __seqs_begin,
01218 _RAIterIterator __seqs_end,
01219 _RAIter3 __target,
01220 _Splitter __splitter,
01221 _DifferenceTp __length,
01222 _Compare __comp,
01223 _ThreadIndex __num_threads)
01224 {
01225 #if _GLIBCXX_ASSERTIONS
01226 _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
01227 #endif
01228
01229 _GLIBCXX_CALL(__length)
01230
01231 typedef _DifferenceTp _DifferenceType;
01232 typedef typename std::iterator_traits<_RAIterIterator>
01233 ::difference_type _SeqNumber;
01234 typedef typename std::iterator_traits<_RAIterIterator>
01235 ::value_type::first_type
01236 _RAIter1;
01237 typedef typename
01238 std::iterator_traits<_RAIter1>::value_type _ValueType;
01239
01240
01241 typedef std::pair<_RAIter1, _RAIter1> seq_type;
01242 seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
01243 _SeqNumber __k = 0;
01244 _DifferenceType __total_length = 0;
01245 for (_RAIterIterator __raii = __seqs_begin;
01246 __raii != __seqs_end; ++__raii)
01247 {
01248 _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
01249 if(__seq_length > 0)
01250 {
01251 __total_length += __seq_length;
01252 __ne_seqs[__k++] = *__raii;
01253 }
01254 }
01255
01256 _GLIBCXX_CALL(__total_length)
01257
01258 __length = std::min<_DifferenceTp>(__length, __total_length);
01259
01260 if (__total_length == 0 || __k == 0)
01261 {
01262 delete[] __ne_seqs;
01263 return __target;
01264 }
01265
01266 std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
01267
01268 __num_threads = static_cast<_ThreadIndex>
01269 (std::min<_DifferenceType>(__num_threads, __total_length));
01270
01271 # pragma omp parallel num_threads (__num_threads)
01272 {
01273 # pragma omp single
01274 {
01275 __num_threads = omp_get_num_threads();
01276
01277 __pieces = new std::vector<
01278 std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
01279 for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
01280 __pieces[__s].resize(__k);
01281
01282 _DifferenceType __num_samples =
01283 __gnu_parallel::_Settings::get().merge_oversampling
01284 * __num_threads;
01285
01286 __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
01287 __comp, __pieces);
01288 }
01289
01290 _ThreadIndex __iam = omp_get_thread_num();
01291
01292 _DifferenceType __target_position = 0;
01293
01294 for (_SeqNumber __c = 0; __c < __k; ++__c)
01295 __target_position += __pieces[__iam][__c].first;
01296
01297 seq_type* __chunks = new seq_type[__k];
01298
01299 for (_SeqNumber __s = 0; __s < __k; ++__s)
01300 __chunks[__s] = std::make_pair(__ne_seqs[__s].first
01301 + __pieces[__iam][__s].first,
01302 __ne_seqs[__s].first
01303 + __pieces[__iam][__s].second);
01304
01305 if(__length > __target_position)
01306 __sequential_multiway_merge<__stable, __sentinels>
01307 (__chunks, __chunks + __k, __target + __target_position,
01308 *(__seqs_begin->second), __length - __target_position, __comp);
01309
01310 delete[] __chunks;
01311 }
01312
01313 #if _GLIBCXX_ASSERTIONS
01314 _GLIBCXX_PARALLEL_ASSERT(
01315 __is_sorted(__target, __target + __length, __comp));
01316 #endif
01317
01318 __k = 0;
01319
01320 for (_RAIterIterator __raii = __seqs_begin;
01321 __raii != __seqs_end; ++__raii)
01322 {
01323 _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
01324 if(__length > 0)
01325 (*__raii).first += __pieces[__num_threads - 1][__k++].second;
01326 }
01327
01328 delete[] __pieces;
01329 delete[] __ne_seqs;
01330
01331 return __target + __length;
01332 }
01333
01334
01335
01336
01337
01338
01339
01340
01341
01342
01343
01344
01345
01346
01347
01348
01349
01350
01351
01352
01353
01354
01355
01356
01357
01358
01359
01360
01361
01362
01363
01364
01365
01366
01367
01368
01369
01370
01371
01372
01373
01374
01375
01376
01377
01378
01379
01380
01381
01382
01383
01384
01385
01386
01387
01388
01389
01390
01391
01392
01393
01394
01395
01396
01397
01398
01399
01400
01401
01402
01403
01404
01405 template<typename _RAIterPairIterator,
01406 typename _RAIterOut,
01407 typename _DifferenceTp,
01408 typename _Compare>
01409 _RAIterOut
01410 multiway_merge(_RAIterPairIterator __seqs_begin,
01411 _RAIterPairIterator __seqs_end,
01412 _RAIterOut __target,
01413 _DifferenceTp __length, _Compare __comp,
01414 __gnu_parallel::sequential_tag)
01415 {
01416 typedef _DifferenceTp _DifferenceType;
01417 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01418
01419
01420 if (__seqs_begin == __seqs_end)
01421 return __target;
01422
01423
01424 return __sequential_multiway_merge
01425 < false, false>
01426 (__seqs_begin, __seqs_end, __target,
01427 *(__seqs_begin->second), __length, __comp);
01428 }
01429
01430
01431 template<typename _RAIterPairIterator,
01432 typename _RAIterOut,
01433 typename _DifferenceTp,
01434 typename _Compare>
01435 _RAIterOut
01436 multiway_merge(_RAIterPairIterator __seqs_begin,
01437 _RAIterPairIterator __seqs_end,
01438 _RAIterOut __target,
01439 _DifferenceTp __length, _Compare __comp,
01440 __gnu_parallel::exact_tag __tag)
01441 {
01442 typedef _DifferenceTp _DifferenceType;
01443 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01444
01445
01446 if (__seqs_begin == __seqs_end)
01447 return __target;
01448
01449
01450
01451
01452 if ((__seqs_end - __seqs_begin > 1)
01453 && _GLIBCXX_PARALLEL_CONDITION(
01454 ((__seqs_end - __seqs_begin) >=
01455 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01456 && ((_SequenceIndex)__length >=
01457 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01458 return parallel_multiway_merge
01459 < false, false>
01460 (__seqs_begin, __seqs_end, __target,
01461 multiway_merge_exact_splitting< false,
01462 typename std::iterator_traits<_RAIterPairIterator>
01463 ::value_type*, _Compare, _DifferenceTp>,
01464 static_cast<_DifferenceType>(__length), __comp,
01465 __tag.__get_num_threads());
01466 else
01467 return __sequential_multiway_merge
01468 < false, false>
01469 (__seqs_begin, __seqs_end, __target,
01470 *(__seqs_begin->second), __length, __comp);
01471 }
01472
01473
01474 template<typename _RAIterPairIterator,
01475 typename _RAIterOut,
01476 typename _DifferenceTp,
01477 typename _Compare>
01478 _RAIterOut
01479 multiway_merge(_RAIterPairIterator __seqs_begin,
01480 _RAIterPairIterator __seqs_end,
01481 _RAIterOut __target,
01482 _DifferenceTp __length, _Compare __comp,
01483 __gnu_parallel::sampling_tag __tag)
01484 {
01485 typedef _DifferenceTp _DifferenceType;
01486 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01487
01488
01489 if (__seqs_begin == __seqs_end)
01490 return __target;
01491
01492
01493
01494
01495 if ((__seqs_end - __seqs_begin > 1)
01496 && _GLIBCXX_PARALLEL_CONDITION(
01497 ((__seqs_end - __seqs_begin) >=
01498 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01499 && ((_SequenceIndex)__length >=
01500 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01501 return parallel_multiway_merge
01502 < false, false>
01503 (__seqs_begin, __seqs_end, __target,
01504 multiway_merge_exact_splitting< false,
01505 typename std::iterator_traits<_RAIterPairIterator>
01506 ::value_type*, _Compare, _DifferenceTp>,
01507 static_cast<_DifferenceType>(__length), __comp,
01508 __tag.__get_num_threads());
01509 else
01510 return __sequential_multiway_merge
01511 < false, false>
01512 (__seqs_begin, __seqs_end, __target,
01513 *(__seqs_begin->second), __length, __comp);
01514 }
01515
01516
01517 template<typename _RAIterPairIterator,
01518 typename _RAIterOut,
01519 typename _DifferenceTp,
01520 typename _Compare>
01521 _RAIterOut
01522 multiway_merge(_RAIterPairIterator __seqs_begin,
01523 _RAIterPairIterator __seqs_end,
01524 _RAIterOut __target,
01525 _DifferenceTp __length, _Compare __comp,
01526 parallel_tag __tag = parallel_tag(0))
01527 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
01528 __comp, exact_tag(__tag.__get_num_threads())); }
01529
01530
01531 template<typename _RAIterPairIterator,
01532 typename _RAIterOut,
01533 typename _DifferenceTp,
01534 typename _Compare>
01535 _RAIterOut
01536 multiway_merge(_RAIterPairIterator __seqs_begin,
01537 _RAIterPairIterator __seqs_end,
01538 _RAIterOut __target,
01539 _DifferenceTp __length, _Compare __comp,
01540 default_parallel_tag __tag)
01541 { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
01542 __comp, exact_tag(__tag.__get_num_threads())); }
01543
01544
01545
01546 template<typename _RAIterPairIterator,
01547 typename _RAIterOut,
01548 typename _DifferenceTp,
01549 typename _Compare>
01550 _RAIterOut
01551 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
01552 _RAIterPairIterator __seqs_end,
01553 _RAIterOut __target,
01554 _DifferenceTp __length, _Compare __comp,
01555 __gnu_parallel::sequential_tag)
01556 {
01557 typedef _DifferenceTp _DifferenceType;
01558 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01559
01560
01561 if (__seqs_begin == __seqs_end)
01562 return __target;
01563
01564
01565 return __sequential_multiway_merge
01566 < true, false>
01567 (__seqs_begin, __seqs_end, __target,
01568 *(__seqs_begin->second), __length, __comp);
01569 }
01570
01571
01572 template<typename _RAIterPairIterator,
01573 typename _RAIterOut,
01574 typename _DifferenceTp,
01575 typename _Compare>
01576 _RAIterOut
01577 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
01578 _RAIterPairIterator __seqs_end,
01579 _RAIterOut __target,
01580 _DifferenceTp __length, _Compare __comp,
01581 __gnu_parallel::exact_tag __tag)
01582 {
01583 typedef _DifferenceTp _DifferenceType;
01584 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01585
01586
01587 if (__seqs_begin == __seqs_end)
01588 return __target;
01589
01590
01591
01592
01593 if ((__seqs_end - __seqs_begin > 1)
01594 && _GLIBCXX_PARALLEL_CONDITION(
01595 ((__seqs_end - __seqs_begin) >=
01596 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01597 && ((_SequenceIndex)__length >=
01598 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01599 return parallel_multiway_merge
01600 < true, false>
01601 (__seqs_begin, __seqs_end, __target,
01602 multiway_merge_exact_splitting< true,
01603 typename std::iterator_traits<_RAIterPairIterator>
01604 ::value_type*, _Compare, _DifferenceTp>,
01605 static_cast<_DifferenceType>(__length), __comp,
01606 __tag.__get_num_threads());
01607 else
01608 return __sequential_multiway_merge
01609 < true, false>
01610 (__seqs_begin, __seqs_end, __target,
01611 *(__seqs_begin->second), __length, __comp);
01612 }
01613
01614
01615 template<typename _RAIterPairIterator,
01616 typename _RAIterOut,
01617 typename _DifferenceTp,
01618 typename _Compare>
01619 _RAIterOut
01620 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
01621 _RAIterPairIterator __seqs_end,
01622 _RAIterOut __target,
01623 _DifferenceTp __length, _Compare __comp,
01624 sampling_tag __tag)
01625 {
01626 typedef _DifferenceTp _DifferenceType;
01627 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01628
01629
01630 if (__seqs_begin == __seqs_end)
01631 return __target;
01632
01633
01634
01635
01636 if ((__seqs_end - __seqs_begin > 1)
01637 && _GLIBCXX_PARALLEL_CONDITION(
01638 ((__seqs_end - __seqs_begin) >=
01639 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01640 && ((_SequenceIndex)__length >=
01641 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01642 return parallel_multiway_merge
01643 < true, false>
01644 (__seqs_begin, __seqs_end, __target,
01645 multiway_merge_sampling_splitting< true,
01646 typename std::iterator_traits<_RAIterPairIterator>
01647 ::value_type*, _Compare, _DifferenceTp>,
01648 static_cast<_DifferenceType>(__length), __comp,
01649 __tag.__get_num_threads());
01650 else
01651 return __sequential_multiway_merge
01652 < true, false>
01653 (__seqs_begin, __seqs_end, __target,
01654 *(__seqs_begin->second), __length, __comp);
01655 }
01656
01657
01658 template<typename _RAIterPairIterator,
01659 typename _RAIterOut,
01660 typename _DifferenceTp,
01661 typename _Compare>
01662 _RAIterOut
01663 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
01664 _RAIterPairIterator __seqs_end,
01665 _RAIterOut __target,
01666 _DifferenceTp __length, _Compare __comp,
01667 parallel_tag __tag = parallel_tag(0))
01668 {
01669 return stable_multiway_merge
01670 (__seqs_begin, __seqs_end, __target, __length, __comp,
01671 exact_tag(__tag.__get_num_threads()));
01672 }
01673
01674
01675 template<typename _RAIterPairIterator,
01676 typename _RAIterOut,
01677 typename _DifferenceTp,
01678 typename _Compare>
01679 _RAIterOut
01680 stable_multiway_merge(_RAIterPairIterator __seqs_begin,
01681 _RAIterPairIterator __seqs_end,
01682 _RAIterOut __target,
01683 _DifferenceTp __length, _Compare __comp,
01684 default_parallel_tag __tag)
01685 {
01686 return stable_multiway_merge
01687 (__seqs_begin, __seqs_end, __target, __length, __comp,
01688 exact_tag(__tag.__get_num_threads()));
01689 }
01690
01691
01692
01693
01694
01695
01696
01697
01698
01699
01700
01701
01702
01703
01704
01705
01706
01707
01708
01709
01710
01711
01712
01713
01714
01715
01716
01717
01718
01719
01720
01721
01722
01723
01724
01725
01726
01727
01728
01729
01730
01731
01732
01733
01734
01735
01736
01737
01738
01739
01740
01741
01742
01743
01744
01745
01746
01747
01748
01749
01750
01751
01752
01753
01754
01755
01756
01757
01758
01759
01760
01761
01762
01763
01764
01765
01766
01767
01768
01769 template<typename _RAIterPairIterator,
01770 typename _RAIterOut,
01771 typename _DifferenceTp,
01772 typename _Compare>
01773 _RAIterOut
01774 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
01775 _RAIterPairIterator __seqs_end,
01776 _RAIterOut __target,
01777 _DifferenceTp __length, _Compare __comp,
01778 __gnu_parallel::sequential_tag)
01779 {
01780 typedef _DifferenceTp _DifferenceType;
01781 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01782
01783
01784 if (__seqs_begin == __seqs_end)
01785 return __target;
01786
01787
01788 return __sequential_multiway_merge
01789 < false, true>
01790 (__seqs_begin, __seqs_end,
01791 __target, *(__seqs_begin->second), __length, __comp);
01792 }
01793
01794
01795 template<typename _RAIterPairIterator,
01796 typename _RAIterOut,
01797 typename _DifferenceTp,
01798 typename _Compare>
01799 _RAIterOut
01800 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
01801 _RAIterPairIterator __seqs_end,
01802 _RAIterOut __target,
01803 _DifferenceTp __length, _Compare __comp,
01804 __gnu_parallel::exact_tag __tag)
01805 {
01806 typedef _DifferenceTp _DifferenceType;
01807 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01808
01809
01810 if (__seqs_begin == __seqs_end)
01811 return __target;
01812
01813
01814
01815
01816 if ((__seqs_end - __seqs_begin > 1)
01817 && _GLIBCXX_PARALLEL_CONDITION(
01818 ((__seqs_end - __seqs_begin) >=
01819 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01820 && ((_SequenceIndex)__length >=
01821 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01822 return parallel_multiway_merge
01823 < false, true>
01824 (__seqs_begin, __seqs_end, __target,
01825 multiway_merge_exact_splitting< false,
01826 typename std::iterator_traits<_RAIterPairIterator>
01827 ::value_type*, _Compare, _DifferenceTp>,
01828 static_cast<_DifferenceType>(__length), __comp,
01829 __tag.__get_num_threads());
01830 else
01831 return __sequential_multiway_merge
01832 < false, true>
01833 (__seqs_begin, __seqs_end, __target,
01834 *(__seqs_begin->second), __length, __comp);
01835 }
01836
01837
01838 template<typename _RAIterPairIterator,
01839 typename _RAIterOut,
01840 typename _DifferenceTp,
01841 typename _Compare>
01842 _RAIterOut
01843 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
01844 _RAIterPairIterator __seqs_end,
01845 _RAIterOut __target,
01846 _DifferenceTp __length, _Compare __comp,
01847 sampling_tag __tag)
01848 {
01849 typedef _DifferenceTp _DifferenceType;
01850 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01851
01852
01853 if (__seqs_begin == __seqs_end)
01854 return __target;
01855
01856
01857
01858
01859 if ((__seqs_end - __seqs_begin > 1)
01860 && _GLIBCXX_PARALLEL_CONDITION(
01861 ((__seqs_end - __seqs_begin) >=
01862 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01863 && ((_SequenceIndex)__length >=
01864 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01865 return parallel_multiway_merge
01866 < false, true>
01867 (__seqs_begin, __seqs_end, __target,
01868 multiway_merge_sampling_splitting< false,
01869 typename std::iterator_traits<_RAIterPairIterator>
01870 ::value_type*, _Compare, _DifferenceTp>,
01871 static_cast<_DifferenceType>(__length), __comp,
01872 __tag.__get_num_threads());
01873 else
01874 return __sequential_multiway_merge
01875 <false, true>(
01876 __seqs_begin, __seqs_end, __target,
01877 *(__seqs_begin->second), __length, __comp);
01878 }
01879
01880
01881 template<typename _RAIterPairIterator,
01882 typename _RAIterOut,
01883 typename _DifferenceTp,
01884 typename _Compare>
01885 _RAIterOut
01886 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
01887 _RAIterPairIterator __seqs_end,
01888 _RAIterOut __target,
01889 _DifferenceTp __length, _Compare __comp,
01890 parallel_tag __tag = parallel_tag(0))
01891 {
01892 return multiway_merge_sentinels
01893 (__seqs_begin, __seqs_end, __target, __length, __comp,
01894 exact_tag(__tag.__get_num_threads()));
01895 }
01896
01897
01898 template<typename _RAIterPairIterator,
01899 typename _RAIterOut,
01900 typename _DifferenceTp,
01901 typename _Compare>
01902 _RAIterOut
01903 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
01904 _RAIterPairIterator __seqs_end,
01905 _RAIterOut __target,
01906 _DifferenceTp __length, _Compare __comp,
01907 default_parallel_tag __tag)
01908 {
01909 return multiway_merge_sentinels
01910 (__seqs_begin, __seqs_end, __target, __length, __comp,
01911 exact_tag(__tag.__get_num_threads()));
01912 }
01913
01914
01915
01916 template<typename _RAIterPairIterator,
01917 typename _RAIterOut,
01918 typename _DifferenceTp,
01919 typename _Compare>
01920 _RAIterOut
01921 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
01922 _RAIterPairIterator __seqs_end,
01923 _RAIterOut __target,
01924 _DifferenceTp __length, _Compare __comp,
01925 __gnu_parallel::sequential_tag)
01926 {
01927 typedef _DifferenceTp _DifferenceType;
01928 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01929
01930
01931 if (__seqs_begin == __seqs_end)
01932 return __target;
01933
01934
01935 return __sequential_multiway_merge
01936 < true, true>
01937 (__seqs_begin, __seqs_end, __target,
01938 *(__seqs_begin->second), __length, __comp);
01939 }
01940
01941
01942 template<typename _RAIterPairIterator,
01943 typename _RAIterOut,
01944 typename _DifferenceTp,
01945 typename _Compare>
01946 _RAIterOut
01947 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
01948 _RAIterPairIterator __seqs_end,
01949 _RAIterOut __target,
01950 _DifferenceTp __length, _Compare __comp,
01951 __gnu_parallel::exact_tag __tag)
01952 {
01953 typedef _DifferenceTp _DifferenceType;
01954 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01955
01956
01957 if (__seqs_begin == __seqs_end)
01958 return __target;
01959
01960
01961
01962
01963 if ((__seqs_end - __seqs_begin > 1)
01964 && _GLIBCXX_PARALLEL_CONDITION(
01965 ((__seqs_end - __seqs_begin) >=
01966 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01967 && ((_SequenceIndex)__length >=
01968 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01969 return parallel_multiway_merge
01970 < true, true>
01971 (__seqs_begin, __seqs_end, __target,
01972 multiway_merge_exact_splitting< true,
01973 typename std::iterator_traits<_RAIterPairIterator>
01974 ::value_type*, _Compare, _DifferenceTp>,
01975 static_cast<_DifferenceType>(__length), __comp,
01976 __tag.__get_num_threads());
01977 else
01978 return __sequential_multiway_merge
01979 < true, true>
01980 (__seqs_begin, __seqs_end, __target,
01981 *(__seqs_begin->second), __length, __comp);
01982 }
01983
01984
01985 template<typename _RAIterPairIterator,
01986 typename _RAIterOut,
01987 typename _DifferenceTp,
01988 typename _Compare>
01989 _RAIterOut
01990 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
01991 _RAIterPairIterator __seqs_end,
01992 _RAIterOut __target,
01993 _DifferenceTp __length,
01994 _Compare __comp,
01995 sampling_tag __tag)
01996 {
01997 typedef _DifferenceTp _DifferenceType;
01998 _GLIBCXX_CALL(__seqs_end - __seqs_begin)
01999
02000
02001 if (__seqs_begin == __seqs_end)
02002 return __target;
02003
02004
02005
02006
02007 if ((__seqs_end - __seqs_begin > 1)
02008 && _GLIBCXX_PARALLEL_CONDITION(
02009 ((__seqs_end - __seqs_begin) >=
02010 __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
02011 && ((_SequenceIndex)__length >=
02012 __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
02013 return parallel_multiway_merge
02014 < true, true>
02015 (__seqs_begin, __seqs_end, __target,
02016 multiway_merge_sampling_splitting< true,
02017 typename std::iterator_traits<_RAIterPairIterator>
02018 ::value_type*, _Compare, _DifferenceTp>,
02019 static_cast<_DifferenceType>(__length), __comp,
02020 __tag.__get_num_threads());
02021 else
02022 return __sequential_multiway_merge
02023 < true, true>
02024 (__seqs_begin, __seqs_end, __target,
02025 *(__seqs_begin->second), __length, __comp);
02026 }
02027
02028
02029 template<typename _RAIterPairIterator,
02030 typename _RAIterOut,
02031 typename _DifferenceTp,
02032 typename _Compare>
02033 _RAIterOut
02034 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
02035 _RAIterPairIterator __seqs_end,
02036 _RAIterOut __target,
02037 _DifferenceTp __length,
02038 _Compare __comp,
02039 parallel_tag __tag = parallel_tag(0))
02040 {
02041 return stable_multiway_merge_sentinels
02042 (__seqs_begin, __seqs_end, __target, __length, __comp,
02043 exact_tag(__tag.__get_num_threads()));
02044 }
02045
02046
02047 template<typename _RAIterPairIterator,
02048 typename _RAIterOut,
02049 typename _DifferenceTp,
02050 typename _Compare>
02051 _RAIterOut
02052 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
02053 _RAIterPairIterator __seqs_end,
02054 _RAIterOut __target,
02055 _DifferenceTp __length, _Compare __comp,
02056 default_parallel_tag __tag)
02057 {
02058 return stable_multiway_merge_sentinels
02059 (__seqs_begin, __seqs_end, __target, __length, __comp,
02060 exact_tag(__tag.__get_num_threads()));
02061 }
02062 };
02063
02064 #endif