libstdc++-v3/include/parallel/multiway_merge.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file parallel/multiway_merge.h
  26 *  @brief Implementation of sequential and parallel multiway merge.
  27 *
  28 *  Explanations on the high-speed merging routines in the appendix of
  29 *
  30 *  P. Sanders.
  31 *  Fast priority queues for cached memory.
  32 *  ACM Journal of Experimental Algorithmics, 5, 2000.
  33 *
  34 *  This file is a GNU parallel extension to the Standard C++ Library.
  35 */
  36
  37 // Written by Johannes Singler and Manuel Holtgrewe.
  38
  39 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
  40 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
  41
  42 #include <vector>
  43
  44 #include <bits/stl_algo.h>
  45 #include <parallel/features.h>
  46 #include <parallel/parallel.h>
  47 #include <parallel/losertree.h>
  48 #if _GLIBCXX_ASSERTIONS
  49 #include <parallel/checkers.h>
  50 #endif
  51
  52 /** @brief Length of a sequence described by a pair of iterators. */
  53 #define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first)
  54
  55 namespace __gnu_parallel
  56 {
  57   /** @brief _Iterator wrapper supporting an implicit supremum at the end
  58    *         of the sequence, dominating all comparisons.
  59    *
  60    * The implicit supremum comes with a performance cost.
  61    *
  62    * Deriving from _RAIter is not possible since
  63    * _RAIter need not be a class.
  64    */
  65   template<typename _RAIter, typename _Compare>
  66     class _GuardedIterator
  67     {
  68     private:
  69       /** @brief Current iterator __position. */
  70       _RAIter _M_current;
  71
  72       /** @brief End iterator of the sequence. */
  73       _RAIter _M_end;
  74
  75       /** @brief _Compare. */
  76       _Compare& __comp;
  77
  78     public:
  79       /** @brief Constructor. Sets iterator to beginning of sequence.
  80       *  @param __begin Begin iterator of sequence.
  81       *  @param __end End iterator of sequence.
  82       *  @param __comp Comparator provided for associated overloaded
  83       *  compare operators. */
  84       _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp)
  85       : _M_current(__begin), _M_end(__end), __comp(__comp)
  86       { }
  87
  88       /** @brief Pre-increment operator.
  89       *  @return This. */
  90       _GuardedIterator<_RAIter, _Compare>&
  91       operator++()
  92       {
  93         ++_M_current;
  94         return *this;
  95       }
  96
  97       /** @brief Dereference operator.
  98       *  @return Referenced element. */
  99       typename std::iterator_traits<_RAIter>::value_type&
 100       operator*()
 101       { return *_M_current; }
 102
 103       /** @brief Convert to wrapped iterator.
 104       *  @return Wrapped iterator. */
 105       operator _RAIter()
 106       { return _M_current; }
 107
 108       /** @brief Compare two elements referenced by guarded iterators.
 109        *  @param __bi1 First iterator.
 110        *  @param __bi2 Second iterator.
 111        *  @return @__c true if less. */
 112       friend bool
 113       operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
 114                 _GuardedIterator<_RAIter, _Compare>& __bi2)
 115       {
 116         if (__bi1._M_current == __bi1._M_end)       // __bi1 is sup
 117           return __bi2._M_current == __bi2._M_end;  // __bi2 is not sup
 118         if (__bi2._M_current == __bi2._M_end)       // __bi2 is sup
 119           return true;
 120         return (__bi1.__comp)(*__bi1, *__bi2);      // normal compare
 121       }
 122
 123       /** @brief Compare two elements referenced by guarded iterators.
 124        *  @param __bi1 First iterator.
 125        *  @param __bi2 Second iterator.
 126        *  @return @__c True if less equal. */
 127       friend bool
 128       operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
 129                  _GuardedIterator<_RAIter, _Compare>& __bi2)
 130       {
 131         if (__bi2._M_current == __bi2._M_end)       // __bi1 is sup
 132           return __bi1._M_current != __bi1._M_end;  // __bi2 is not sup
 133         if (__bi1._M_current == __bi1._M_end)       // __bi2 is sup
 134           return false;
 135         return !(__bi1.__comp)(*__bi2, *__bi1);     // normal compare
 136       }
 137     };
 138
 139   template<typename _RAIter, typename _Compare>
 140     class _UnguardedIterator
 141     {
 142     private:
 143       /** @brief Current iterator __position. */
 144       _RAIter _M_current;
 145       /** @brief _Compare. */
 146       mutable _Compare& __comp;
 147
 148     public:
 149       /** @brief Constructor. Sets iterator to beginning of sequence.
 150       *  @param __begin Begin iterator of sequence.
 151       *  @param __end Unused, only for compatibility.
 152       *  @param __comp Unused, only for compatibility. */
 153       _UnguardedIterator(_RAIter __begin,
 154                          _RAIter /* __end */, _Compare& __comp)
 155       : _M_current(__begin), __comp(__comp)
 156       { }
 157
 158       /** @brief Pre-increment operator.
 159       *  @return This. */
 160       _UnguardedIterator<_RAIter, _Compare>&
 161       operator++()
 162       {
 163         ++_M_current;
 164         return *this;
 165       }
 166
 167       /** @brief Dereference operator.
 168       *  @return Referenced element. */
 169       typename std::iterator_traits<_RAIter>::value_type&
 170       operator*()
 171       { return *_M_current; }
 172
 173       /** @brief Convert to wrapped iterator.
 174       *  @return Wrapped iterator. */
 175       operator _RAIter()
 176       { return _M_current; }
 177
 178       /** @brief Compare two elements referenced by unguarded iterators.
 179        *  @param __bi1 First iterator.
 180        *  @param __bi2 Second iterator.
 181        *  @return @__c true if less. */
 182       friend bool
 183       operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
 184                 _UnguardedIterator<_RAIter, _Compare>& __bi2)
 185       {
 186         // Normal compare.
 187         return (__bi1.__comp)(*__bi1, *__bi2);
 188       }
 189
 190       /** @brief Compare two elements referenced by unguarded iterators.
 191        *  @param __bi1 First iterator.
 192        *  @param __bi2 Second iterator.
 193        *  @return @__c True if less equal. */
 194       friend bool
 195       operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
 196                  _UnguardedIterator<_RAIter, _Compare>& __bi2)
 197       {
 198         // Normal compare.
 199         return !(__bi1.__comp)(*__bi2, *__bi1);
 200       }
 201     };
 202
 203   /** @brief Highly efficient 3-way merging procedure.
 204    *
 205    * Merging is done with the algorithm implementation described by Peter
 206    * Sanders.  Basically, the idea is to minimize the number of necessary
 207    * comparison after merging an element.  The implementation trick
 208    * that makes this fast is that the order of the sequences is stored
 209    * in the instruction pointer (translated into labels in C++).
 210    *
 211    * This works well for merging up to 4 sequences.
 212    *
 213    * Note that making the merging stable does <em>not</em> come at a
 214    * performance hit.
 215    *
 216    * Whether the merging is done guarded or unguarded is selected by the
 217    * used iterator class.
 218    *
 219    * @param __seqs_begin Begin iterator of iterator pair input sequence.
 220    * @param __seqs_end End iterator of iterator pair input sequence.
 221    * @param __target Begin iterator of output sequence.
 222    * @param __comp Comparator.
 223    * @param __length Maximum length to merge, less equal than the
 224    * total number of elements available.
 225    *
 226    * @return End iterator of output sequence.
 227    */
 228   template<template<typename RAI, typename C> class iterator,
 229            typename _RAIterIterator,
 230            typename _RAIter3,
 231            typename _DifferenceTp,
 232            typename _Compare>
 233     _RAIter3
 234     multiway_merge_3_variant(_RAIterIterator __seqs_begin,
 235                              _RAIterIterator __seqs_end,
 236                              _RAIter3 __target,
 237                              _DifferenceTp __length, _Compare __comp)
 238     {
 239       _GLIBCXX_CALL(__length);
 240
 241       typedef _DifferenceTp _DifferenceType;
 242
 243       typedef typename std::iterator_traits<_RAIterIterator>
 244         ::value_type::first_type
 245         _RAIter1;
 246       typedef typename std::iterator_traits<_RAIter1>::value_type
 247         _ValueType;
 248
 249       if (__length == 0)
 250         return __target;
 251
 252 #if _GLIBCXX_ASSERTIONS
 253       _DifferenceTp __orig_length = __length;
 254 #endif
 255
 256       iterator<_RAIter1, _Compare>
 257         __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
 258         __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
 259         __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp);
 260
 261       if (__seq0 <= __seq1)
 262         {
 263           if (__seq1 <= __seq2)
 264             goto __s012;
 265           else
 266             if (__seq2 <  __seq0)
 267               goto __s201;
 268             else
 269               goto __s021;
 270         }
 271       else
 272         {
 273           if (__seq1 <= __seq2)
 274             {
 275               if (__seq0 <= __seq2)
 276                 goto __s102;
 277               else
 278                 goto __s120;
 279             }
 280           else
 281             goto __s210;
 282         }
 283 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \
 284       __s ## __a ## __b ## __c :                            \
 285         *__target = *__seq ## __a;                          \
 286         ++__target;                                         \
 287         --__length;                                         \
 288         ++__seq ## __a;                                     \
 289         if (__length == 0) goto __finish;                   \
 290         if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
 291         if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
 292         goto __s ## __b ## __c ## __a;
 293
 294       _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
 295       _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
 296       _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
 297       _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
 298       _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
 299       _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
 300
 301 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
 302
 303     __finish:
 304       ;
 305
 306 #if _GLIBCXX_ASSERTIONS
 307     _GLIBCXX_PARALLEL_ASSERT(
 308         ((_RAIter1)__seq0 - __seqs_begin[0].first) +
 309         ((_RAIter1)__seq1 - __seqs_begin[1].first) +
 310         ((_RAIter1)__seq2 - __seqs_begin[2].first)
 311         == __orig_length);
 312 #endif
 313
 314       __seqs_begin[0].first = __seq0;
 315       __seqs_begin[1].first = __seq1;
 316       __seqs_begin[2].first = __seq2;
 317
 318       return __target;
 319     }
 320
 321   /**
 322    * @brief Highly efficient 4-way merging procedure.
 323    *
 324    * Merging is done with the algorithm implementation described by Peter
 325    * Sanders. Basically, the idea is to minimize the number of necessary
 326    * comparison after merging an element.  The implementation trick
 327    * that makes this fast is that the order of the sequences is stored
 328    * in the instruction pointer (translated into goto labels in C++).
 329    *
 330    * This works well for merging up to 4 sequences.
 331    *
 332    * Note that making the merging stable does <em>not</em> come at a
 333    * performance hit.
 334    *
 335    * Whether the merging is done guarded or unguarded is selected by the
 336    * used iterator class.
 337    *
 338    * @param __seqs_begin Begin iterator of iterator pair input sequence.
 339    * @param __seqs_end End iterator of iterator pair input sequence.
 340    * @param __target Begin iterator of output sequence.
 341    * @param __comp Comparator.
 342    * @param __length Maximum length to merge, less equal than the
 343    * total number of elements available.
 344    *
 345    * @return End iterator of output sequence.
 346    */
 347   template<template<typename RAI, typename C> class iterator,
 348            typename _RAIterIterator,
 349            typename _RAIter3,
 350            typename _DifferenceTp,
 351            typename _Compare>
 352     _RAIter3
 353     multiway_merge_4_variant(_RAIterIterator __seqs_begin,
 354                              _RAIterIterator __seqs_end,
 355                              _RAIter3 __target,
 356                              _DifferenceTp __length, _Compare __comp)
 357     {
 358       _GLIBCXX_CALL(__length);
 359       typedef _DifferenceTp _DifferenceType;
 360
 361       typedef typename std::iterator_traits<_RAIterIterator>
 362         ::value_type::first_type
 363         _RAIter1;
 364       typedef typename std::iterator_traits<_RAIter1>::value_type
 365         _ValueType;
 366
 367       iterator<_RAIter1, _Compare>
 368         __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
 369         __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
 370         __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp),
 371         __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp);
 372
 373 #define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) {  \
 374         if (__seq ## __d < __seq ## __a)                  \
 375           goto __s ## __d ## __a ## __b ## __c;           \
 376         if (__seq ## __d < __seq ## __b)                  \
 377           goto __s ## __a ## __d ## __b ## __c;           \
 378         if (__seq ## __d < __seq ## __c)                  \
 379           goto __s ## __a ## __b ## __d ## __c;           \
 380         goto __s ## __a ## __b ## __c ## __d;  }
 381
 382       if (__seq0 <= __seq1)
 383         {
 384           if (__seq1 <= __seq2)
 385             _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
 386             else
 387               if (__seq2 < __seq0)
 388                 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
 389                 else
 390                   _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
 391                     }
 392       else
 393         {
 394           if (__seq1 <= __seq2)
 395             {
 396               if (__seq0 <= __seq2)
 397                 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
 398                 else
 399                   _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
 400                     }
 401           else
 402             _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
 403               }
 404
 405 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d,  \
 406                                        __c0, __c1, __c2)    \
 407       __s ## __a ## __b ## __c ## __d:                      \
 408       if (__length == 0) goto __finish;                     \
 409       *__target = *__seq ## __a;                            \
 410       ++__target;                                           \
 411       --__length;                                           \
 412       ++__seq ## __a;                                       \
 413       if (__seq ## __a __c0 __seq ## __b)      \
 414         goto __s ## __a ## __b ## __c ## __d;  \
 415       if (__seq ## __a __c1 __seq ## __c)      \
 416         goto __s ## __b ## __a ## __c ## __d;  \
 417       if (__seq ## __a __c2 __seq ## __d)      \
 418         goto __s ## __b ## __c ## __a ## __d;  \
 419       goto __s ## __b ## __c ## __d ## __a;
 420
 421       _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
 422       _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
 423       _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
 424       _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
 425       _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
 426       _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
 427       _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
 428       _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
 429       _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
 430       _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
 431       _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
 432       _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
 433       _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
 434       _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
 435       _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
 436       _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
 437       _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
 438       _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
 439       _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
 440       _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
 441       _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
 442       _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
 443       _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
 444       _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
 445
 446 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
 447 #undef _GLIBCXX_PARALLEL_DECISION
 448
 449     __finish:
 450       ;
 451
 452       __seqs_begin[0].first = __seq0;
 453       __seqs_begin[1].first = __seq1;
 454       __seqs_begin[2].first = __seq2;
 455       __seqs_begin[3].first = __seq3;
 456
 457       return __target;
 458     }
 459
 460   /** @brief Multi-way merging procedure for a high branching factor,
 461    *         guarded case.
 462    *
 463    * This merging variant uses a LoserTree class as selected by <tt>_LT</tt>.
 464    *
 465    * Stability is selected through the used LoserTree class <tt>_LT</tt>.
 466    *
 467    * At least one non-empty sequence is required.
 468    *
 469    * @param __seqs_begin Begin iterator of iterator pair input sequence.
 470    * @param __seqs_end End iterator of iterator pair input sequence.
 471    * @param __target Begin iterator of output sequence.
 472    * @param __comp Comparator.
 473    * @param __length Maximum length to merge, less equal than the
 474    * total number of elements available.
 475    *
 476    * @return End iterator of output sequence.
 477    */
 478   template<typename _LT,
 479            typename _RAIterIterator,
 480            typename _RAIter3,
 481            typename _DifferenceTp,
 482            typename _Compare>
 483     _RAIter3
 484     multiway_merge_loser_tree(_RAIterIterator __seqs_begin,
 485                               _RAIterIterator __seqs_end,
 486                               _RAIter3 __target,
 487                               _DifferenceTp __length, _Compare __comp)
 488     {
 489       _GLIBCXX_CALL(__length)
 490
 491       typedef _DifferenceTp _DifferenceType;
 492       typedef typename std::iterator_traits<_RAIterIterator>
 493         ::value_type::first_type
 494         _RAIter1;
 495       typedef typename std::iterator_traits<_RAIter1>::value_type
 496         _ValueType;
 497
 498       int __k = static_cast<int>(__seqs_end - __seqs_begin);
 499
 500       _LT __lt(__k, __comp);
 501
 502       // Default value for potentially non-default-constructible types.
 503       _ValueType* __arbitrary_element = NULL;
 504
 505       for (int __t = 0; __t < __k; ++__t)
 506         {
 507           if(__arbitrary_element == NULL
 508              && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
 509             __arbitrary_element = &(*__seqs_begin[__t].first);
 510         }
 511
 512       for (int __t = 0; __t < __k; ++__t)
 513         {
 514           if (__seqs_begin[__t].first == __seqs_begin[__t].second)
 515             __lt.__insert_start(*__arbitrary_element, __t, true);
 516           else
 517             __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
 518         }
 519
 520       __lt.__init();
 521
 522       int __source;
 523
 524       for (_DifferenceType __i = 0; __i < __length; ++__i)
 525         {
 526           //take out
 527           __source = __lt.__get_min_source();
 528
 529           *(__target++) = *(__seqs_begin[__source].first++);
 530
 531           // Feed.
 532           if (__seqs_begin[__source].first == __seqs_begin[__source].second)
 533             __lt.__delete_min_insert(*__arbitrary_element, true);
 534           else
 535             // Replace from same __source.
 536             __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
 537         }
 538
 539       return __target;
 540     }
 541
 542   /** @brief Multi-way merging procedure for a high branching factor,
 543    *         unguarded case.
 544    *
 545    * Merging is done using the LoserTree class <tt>_LT</tt>.
 546    *
 547    * Stability is selected by the used LoserTrees.
 548    *
 549    * @pre No input will run out of elements during the merge.
 550    *
 551    * @param __seqs_begin Begin iterator of iterator pair input sequence.
 552    * @param __seqs_end End iterator of iterator pair input sequence.
 553    * @param __target Begin iterator of output sequence.
 554    * @param __comp Comparator.
 555    * @param __length Maximum length to merge, less equal than the
 556    * total number of elements available.
 557    *
 558    * @return End iterator of output sequence.
 559    */
 560   template<typename _LT,
 561            typename _RAIterIterator,
 562            typename _RAIter3,
 563            typename _DifferenceTp, typename _Compare>
 564     _RAIter3
 565     multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin,
 566                                         _RAIterIterator __seqs_end,
 567                                         _RAIter3 __target,
 568        const typename std::iterator_traits<typename std::iterator_traits<
 569           _RAIterIterator>::value_type::first_type>::value_type&
 570                                         __sentinel,
 571                                         _DifferenceTp __length,
 572                                         _Compare __comp)
 573     {
 574       _GLIBCXX_CALL(__length)
 575       typedef _DifferenceTp _DifferenceType;
 576
 577       typedef typename std::iterator_traits<_RAIterIterator>
 578         ::value_type::first_type
 579         _RAIter1;
 580       typedef typename std::iterator_traits<_RAIter1>::value_type
 581         _ValueType;
 582
 583       int __k = __seqs_end - __seqs_begin;
 584
 585       _LT __lt(__k, __sentinel, __comp);
 586
 587       for (int __t = 0; __t < __k; ++__t)
 588         {
 589 #if _GLIBCXX_ASSERTIONS
 590           _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
 591                                    != __seqs_begin[__t].second);
 592 #endif
 593           __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
 594         }
 595
 596       __lt.__init();
 597
 598       int __source;
 599
 600 #if _GLIBCXX_ASSERTIONS
 601       _DifferenceType __i = 0;
 602 #endif
 603
 604       _RAIter3 __target_end = __target + __length;
 605       while (__target < __target_end)
 606         {
 607           // Take out.
 608           __source = __lt.__get_min_source();
 609
 610 #if _GLIBCXX_ASSERTIONS
 611           _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
 612           _GLIBCXX_PARALLEL_ASSERT(__i == 0
 613               || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
 614 #endif
 615
 616           // Feed.
 617           *(__target++) = *(__seqs_begin[__source].first++);
 618
 619 #if _GLIBCXX_ASSERTIONS
 620           ++__i;
 621 #endif
 622           // Replace from same __source.
 623           __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
 624         }
 625
 626       return __target;
 627     }
 628
 629
 630   /** @brief Multi-way merging procedure for a high branching factor,
 631    *         requiring sentinels to exist.
 632    *
 633    * @param __stable The value must the same as for the used LoserTrees.
 634    * @param UnguardedLoserTree _Loser Tree variant to use for the unguarded
 635    *   merging.
 636    * @param GuardedLoserTree _Loser Tree variant to use for the guarded
 637    *   merging.
 638    *
 639    * @param __seqs_begin Begin iterator of iterator pair input sequence.
 640    * @param __seqs_end End iterator of iterator pair input sequence.
 641    * @param __target Begin iterator of output sequence.
 642    * @param __comp Comparator.
 643    * @param __length Maximum length to merge, less equal than the
 644    * total number of elements available.
 645    *
 646    * @return End iterator of output sequence.
 647    */
 648   template<typename UnguardedLoserTree,
 649            typename _RAIterIterator,
 650            typename _RAIter3,
 651            typename _DifferenceTp,
 652            typename _Compare>
 653     _RAIter3
 654     multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin,
 655                                        _RAIterIterator __seqs_end,
 656                                        _RAIter3 __target,
 657       const typename std::iterator_traits<typename std::iterator_traits<
 658         _RAIterIterator>::value_type::first_type>::value_type&
 659                                        __sentinel,
 660                                        _DifferenceTp __length,
 661                                        _Compare __comp)
 662     {
 663       _GLIBCXX_CALL(__length)
 664
 665       typedef _DifferenceTp _DifferenceType;
 666       typedef std::iterator_traits<_RAIterIterator> _TraitsType;
 667       typedef typename std::iterator_traits<_RAIterIterator>
 668         ::value_type::first_type
 669         _RAIter1;
 670       typedef typename std::iterator_traits<_RAIter1>::value_type
 671         _ValueType;
 672
 673       _RAIter3 __target_end;
 674
 675       for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
 676         // Move the sequence ends to the sentinel.  This has the
 677         // effect that the sentinel appears to be within the sequence. Then,
 678         // we can use the unguarded variant if we merge out as many
 679         // non-sentinel elements as we have.
 680         ++((*__s).second);
 681
 682       __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree>
 683         (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
 684
 685 #if _GLIBCXX_ASSERTIONS
 686       _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
 687       _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
 688 #endif
 689
 690       // Restore the sequence ends so the sentinels are not contained in the
 691       // sequence any more (see comment in loop above).
 692       for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
 693         --((*__s).second);
 694
 695       return __target_end;
 696     }
 697
 698   /**
 699    * @brief Traits for determining whether the loser tree should
 700    *   use pointers or copies.
 701    *
 702    * The field "_M_use_pointer" is used to determine whether to use pointers
 703    * in he loser trees or whether to copy the values into the loser tree.
 704    *
 705    * The default behavior is to use pointers if the data type is 4 times as
 706    * big as the pointer to it.
 707    *
 708    * Specialize for your data type to customize the behavior.
 709    *
 710    * Example:
 711    *
 712    *   template<>
 713    *   struct _LoserTreeTraits<int>
 714    *   { static const bool _M_use_pointer = false; };
 715    *
 716    *   template<>
 717    *   struct _LoserTreeTraits<heavyweight_type>
 718    *   { static const bool _M_use_pointer = true; };
 719    *
 720    * @param _Tp type to give the loser tree traits for.
 721    */
 722   template <typename _Tp>
 723     struct _LoserTreeTraits
 724     {
 725       /**
 726        * @brief True iff to use pointers instead of values in loser trees.
 727        *
 728        * The default behavior is to use pointers if the data type is four
 729        * times as big as the pointer to it.
 730        */
 731       static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*));
 732     };
 733
 734   /**
 735    * @brief Switch for 3-way merging with __sentinels turned off.
 736    *
 737    * Note that 3-way merging is always stable!
 738    */
 739   template<bool __sentinels /*default == false*/,
 740            typename _RAIterIterator,
 741            typename _RAIter3,
 742            typename _DifferenceTp,
 743            typename _Compare>
 744     struct __multiway_merge_3_variant_sentinel_switch
 745     {
 746       _RAIter3
 747       operator()(_RAIterIterator __seqs_begin,
 748                  _RAIterIterator __seqs_end,
 749                  _RAIter3 __target,
 750                  _DifferenceTp __length, _Compare __comp)
 751       { return multiway_merge_3_variant<_GuardedIterator>
 752           (__seqs_begin, __seqs_end, __target, __length, __comp); }
 753     };
 754
 755   /**
 756    * @brief Switch for 3-way merging with __sentinels turned on.
 757    *
 758    * Note that 3-way merging is always stable!
 759    */
 760   template<typename _RAIterIterator,
 761            typename _RAIter3,
 762            typename _DifferenceTp,
 763            typename _Compare>
 764     struct __multiway_merge_3_variant_sentinel_switch<true, _RAIterIterator,
 765                                                       _RAIter3, _DifferenceTp,
 766                                                       _Compare>
 767     {
 768       _RAIter3
 769       operator()(_RAIterIterator __seqs_begin,
 770                  _RAIterIterator __seqs_end,
 771                  _RAIter3 __target,
 772                  _DifferenceTp __length, _Compare __comp)
 773       { return multiway_merge_3_variant<_UnguardedIterator>
 774           (__seqs_begin, __seqs_end, __target, __length, __comp); }
 775     };
 776
 777   /**
 778    * @brief Switch for 4-way merging with __sentinels turned off.
 779    *
 780    * Note that 4-way merging is always stable!
 781    */
 782   template<bool __sentinels /*default == false*/,
 783            typename _RAIterIterator,
 784            typename _RAIter3,
 785            typename _DifferenceTp,
 786            typename _Compare>
 787     struct __multiway_merge_4_variant_sentinel_switch
 788     {
 789       _RAIter3
 790       operator()(_RAIterIterator __seqs_begin,
 791                  _RAIterIterator __seqs_end,
 792                  _RAIter3 __target,
 793                  _DifferenceTp __length, _Compare __comp)
 794       { return multiway_merge_4_variant<_GuardedIterator>
 795           (__seqs_begin, __seqs_end, __target, __length, __comp); }
 796     };
 797
 798   /**
 799    * @brief Switch for 4-way merging with __sentinels turned on.
 800    *
 801    * Note that 4-way merging is always stable!
 802    */
 803   template<typename _RAIterIterator,
 804            typename _RAIter3,
 805            typename _DifferenceTp,
 806            typename _Compare>
 807     struct __multiway_merge_4_variant_sentinel_switch<true, _RAIterIterator,
 808                                                       _RAIter3, _DifferenceTp,
 809                                                       _Compare>
 810     {
 811       _RAIter3
 812       operator()(_RAIterIterator __seqs_begin,
 813                  _RAIterIterator __seqs_end,
 814                  _RAIter3 __target,
 815                  _DifferenceTp __length, _Compare __comp)
 816       { return multiway_merge_4_variant<_UnguardedIterator>
 817           (__seqs_begin, __seqs_end, __target, __length, __comp); }
 818     };
 819
 820   /**
 821    * @brief Switch for k-way merging with __sentinels turned on.
 822    */
 823   template<bool __sentinels,
 824            bool __stable,
 825            typename _RAIterIterator,
 826            typename _RAIter3,
 827            typename _DifferenceTp,
 828            typename _Compare>
 829     struct __multiway_merge_k_variant_sentinel_switch
 830     {
 831       _RAIter3
 832       operator()(_RAIterIterator __seqs_begin,
 833                  _RAIterIterator __seqs_end,
 834                  _RAIter3 __target,
 835       const typename std::iterator_traits<typename std::iterator_traits<
 836       _RAIterIterator>::value_type::first_type>::value_type&
 837                  __sentinel,
 838                  _DifferenceTp __length, _Compare __comp)
 839       {
 840         typedef typename std::iterator_traits<_RAIterIterator>
 841           ::value_type::first_type
 842           _RAIter1;
 843         typedef typename std::iterator_traits<_RAIter1>::value_type
 844           _ValueType;
 845
 846         return multiway_merge_loser_tree_sentinel<
 847         typename __gnu_cxx::__conditional_type<
 848         _LoserTreeTraits<_ValueType>::_M_use_pointer,
 849           _LoserTreePointerUnguarded<__stable, _ValueType, _Compare>,
 850           _LoserTreeUnguarded<__stable, _ValueType, _Compare>
 851           >::__type>
 852           (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
 853       }
 854     };
 855
 856   /**
 857    * @brief Switch for k-way merging with __sentinels turned off.
 858    */
 859   template<bool __stable,
 860            typename _RAIterIterator,
 861            typename _RAIter3,
 862            typename _DifferenceTp,
 863            typename _Compare>
 864     struct __multiway_merge_k_variant_sentinel_switch<false, __stable,
 865                                                       _RAIterIterator, _RAIter3,
 866                                                       _DifferenceTp, _Compare>
 867     {
 868       _RAIter3
 869       operator()(_RAIterIterator __seqs_begin,
 870                  _RAIterIterator __seqs_end,
 871                  _RAIter3 __target,
 872        const typename std::iterator_traits<typename std::iterator_traits<
 873        _RAIterIterator>::value_type::first_type>::value_type&
 874                  __sentinel,
 875                  _DifferenceTp __length, _Compare __comp)
 876       {
 877         typedef typename std::iterator_traits<_RAIterIterator>
 878           ::value_type::first_type
 879           _RAIter1;
 880         typedef typename std::iterator_traits<_RAIter1>::value_type
 881           _ValueType;
 882
 883         return multiway_merge_loser_tree<
 884         typename __gnu_cxx::__conditional_type<
 885         _LoserTreeTraits<_ValueType>::_M_use_pointer,
 886           _LoserTreePointer<__stable, _ValueType, _Compare>,
 887           _LoserTree<__stable, _ValueType, _Compare>
 888           >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp);
 889       }
 890     };
 891
 892   /** @brief Sequential multi-way merging switch.
 893    *
 894    *  The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
 895    *  runtime settings.
 896    *  @param __seqs_begin Begin iterator of iterator pair input sequence.
 897    *  @param __seqs_end End iterator of iterator pair input sequence.
 898    *  @param __target Begin iterator of output sequence.
 899    *  @param __comp Comparator.
 900    *  @param __length Maximum length to merge, possibly larger than the
 901    *  number of elements available.
 902    *  @param __stable Stable merging incurs a performance penalty.
 903    *  @param __sentinel The sequences have __a __sentinel element.
 904    *  @return End iterator of output sequence. */
 905   template<bool __stable,
 906            bool __sentinels,
 907            typename _RAIterIterator,
 908            typename _RAIter3,
 909            typename _DifferenceTp,
 910            typename _Compare>
 911     _RAIter3
 912     __sequential_multiway_merge(_RAIterIterator __seqs_begin,
 913                                 _RAIterIterator __seqs_end,
 914                                 _RAIter3 __target,
 915       const typename std::iterator_traits<typename std::iterator_traits<
 916         _RAIterIterator>::value_type::first_type>::value_type&
 917                                 __sentinel,
 918                                 _DifferenceTp __length, _Compare __comp)
 919     {
 920       _GLIBCXX_CALL(__length)
 921
 922       typedef _DifferenceTp _DifferenceType;
 923       typedef typename std::iterator_traits<_RAIterIterator>
 924         ::value_type::first_type
 925         _RAIter1;
 926       typedef typename std::iterator_traits<_RAIter1>::value_type
 927         _ValueType;
 928
 929 #if _GLIBCXX_ASSERTIONS
 930       for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
 931         {
 932           _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first,
 933                                                (*__s).second, __comp));
 934         }
 935 #endif
 936
 937       _DifferenceTp __total_length = 0;
 938       for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
 939         __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
 940
 941       __length = std::min<_DifferenceTp>(__length, __total_length);
 942
 943       if(__length == 0)
 944         return __target;
 945
 946       _RAIter3 __return_target = __target;
 947       int __k = static_cast<int>(__seqs_end - __seqs_begin);
 948
 949       switch (__k)
 950         {
 951         case 0:
 952           break;
 953         case 1:
 954           __return_target = std::copy(__seqs_begin[0].first,
 955                                       __seqs_begin[0].first + __length,
 956                                       __target);
 957           __seqs_begin[0].first += __length;
 958           break;
 959         case 2:
 960           __return_target = __merge_advance(__seqs_begin[0].first,
 961                                             __seqs_begin[0].second,
 962                                             __seqs_begin[1].first,
 963                                             __seqs_begin[1].second,
 964                                             __target, __length, __comp);
 965           break;
 966         case 3:
 967           __return_target = __multiway_merge_3_variant_sentinel_switch
 968             <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
 969             (__seqs_begin, __seqs_end, __target, __length, __comp);
 970           break;
 971         case 4:
 972           __return_target = __multiway_merge_4_variant_sentinel_switch
 973             <__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
 974             (__seqs_begin, __seqs_end, __target, __length, __comp);
 975           break;
 976         default:
 977           __return_target = __multiway_merge_k_variant_sentinel_switch
 978             <__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp,
 979              _Compare>()
 980             (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
 981           break;
 982         }
 983 #if _GLIBCXX_ASSERTIONS
 984       _GLIBCXX_PARALLEL_ASSERT(
 985         __is_sorted(__target, __target + __length, __comp));
 986 #endif
 987
 988       return __return_target;
 989     }
 990
 991   /**
 992    * @brief Stable sorting functor.
 993    *
 994    * Used to reduce code instanciation in multiway_merge_sampling_splitting.
 995    */
 996   template<bool __stable, class _RAIter, class _StrictWeakOrdering>
 997     struct _SamplingSorter
 998     {
 999       void
1000       operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
1001       { __gnu_sequential::stable_sort(__first, __last, __comp); }
1002     };
1003
1004   /**
1005    * @brief Non-__stable sorting functor.
1006    *
1007    * Used to reduce code instantiation in multiway_merge_sampling_splitting.
1008    */
1009   template<class _RAIter, class _StrictWeakOrdering>
1010     struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering>
1011     {
1012       void
1013       operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
1014       { __gnu_sequential::sort(__first, __last, __comp); }
1015     };
1016
1017   /**
1018    * @brief Sampling based splitting for parallel multiway-merge routine.
1019    */
1020   template<bool __stable,
1021            typename _RAIterIterator,
1022            typename _Compare,
1023            typename _DifferenceType>
1024     void
1025     multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin,
1026                                       _RAIterIterator __seqs_end,
1027                                       _DifferenceType __length,
1028                                       _DifferenceType __total_length,
1029                                       _Compare __comp,
1030      std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1031     {
1032       typedef typename std::iterator_traits<_RAIterIterator>
1033         ::value_type::first_type
1034         _RAIter1;
1035       typedef typename std::iterator_traits<_RAIter1>::value_type
1036         _ValueType;
1037
1038       // __k sequences.
1039       int __k = static_cast<int>(__seqs_end - __seqs_begin);
1040
1041       int __num_threads = omp_get_num_threads();
1042
1043       _DifferenceType __num_samples =
1044         __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
1045
1046       _ValueType* __samples = static_cast<_ValueType*>
1047         (::operator new(sizeof(_ValueType) * __k * __num_samples));
1048       // Sample.
1049       for (int __s = 0; __s < __k; ++__s)
1050         for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
1051           {
1052             _DifferenceType sample_index = static_cast<_DifferenceType>
1053               (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
1054                * (double(__i + 1) / (__num_samples + 1))
1055                * (double(__length) / __total_length));
1056             new(&(__samples[__s * __num_samples + __i]))
1057               _ValueType(__seqs_begin[__s].first[sample_index]);
1058           }
1059
1060       // Sort stable or non-stable, depending on value of template parameter
1061       // "__stable".
1062       _SamplingSorter<__stable, _ValueType*, _Compare>()
1063         (__samples, __samples + (__num_samples * __k), __comp);
1064
1065       for (int __slab = 0; __slab < __num_threads; ++__slab)
1066         // For each slab / processor.
1067         for (int __seq = 0; __seq < __k; ++__seq)
1068           {
1069             // For each sequence.
1070             if (__slab > 0)
1071               __pieces[__slab][__seq].first = std::upper_bound
1072                 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1073                  __samples[__num_samples * __k * __slab / __num_threads],
1074                  __comp)
1075                 - __seqs_begin[__seq].first;
1076             else
1077               // Absolute beginning.
1078               __pieces[__slab][__seq].first = 0;
1079             if ((__slab + 1) < __num_threads)
1080               __pieces[__slab][__seq].second = std::upper_bound
1081                 (__seqs_begin[__seq].first, __seqs_begin[__seq].second,
1082                  __samples[__num_samples * __k * (__slab + 1) / __num_threads],
1083                  __comp)
1084                 - __seqs_begin[__seq].first;
1085             else
1086               // Absolute end.
1087               __pieces[__slab][__seq].second =
1088                 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1089           }
1090       ::operator delete(__samples);
1091     }
1092
1093   /**
1094    * @brief Exact splitting for parallel multiway-merge routine.
1095    *
1096    * None of the passed sequences may be empty.
1097    */
1098   template<bool __stable,
1099            typename _RAIterIterator,
1100            typename _Compare,
1101            typename _DifferenceType>
1102     void
1103     multiway_merge_exact_splitting(_RAIterIterator __seqs_begin,
1104                                    _RAIterIterator __seqs_end,
1105                                    _DifferenceType __length,
1106                                    _DifferenceType __total_length,
1107                                    _Compare __comp,
1108        std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
1109     {
1110       typedef typename std::iterator_traits<_RAIterIterator>
1111         ::value_type::first_type
1112         _RAIter1;
1113
1114       const bool __tight = (__total_length == __length);
1115
1116       // __k sequences.
1117       const int __k = static_cast<int>(__seqs_end - __seqs_begin);
1118
1119       const int __num_threads = omp_get_num_threads();
1120
1121       // (Settings::multiway_merge_splitting
1122       //  == __gnu_parallel::_Settings::EXACT).
1123       std::vector<_RAIter1>* __offsets =
1124         new std::vector<_RAIter1>[__num_threads];
1125       std::vector<std::pair<_RAIter1, _RAIter1> > __se(__k);
1126
1127       copy(__seqs_begin, __seqs_end, __se.begin());
1128
1129       _DifferenceType* __borders =
1130         new _DifferenceType[__num_threads + 1];
1131       equally_split(__length, __num_threads, __borders);
1132
1133       for (int __s = 0; __s < (__num_threads - 1); ++__s)
1134         {
1135           __offsets[__s].resize(__k);
1136           multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
1137                              __offsets[__s].begin(), __comp);
1138
1139           // Last one also needed and available.
1140           if (!__tight)
1141             {
1142               __offsets[__num_threads - 1].resize(__k);
1143               multiseq_partition(__se.begin(), __se.end(),
1144                                  _DifferenceType(__length),
1145                                  __offsets[__num_threads - 1].begin(),
1146                                  __comp);
1147             }
1148         }
1149       delete[] __borders;
1150
1151       for (int __slab = 0; __slab < __num_threads; ++__slab)
1152         {
1153           // For each slab / processor.
1154           for (int __seq = 0; __seq < __k; ++__seq)
1155             {
1156               // For each sequence.
1157               if (__slab == 0)
1158                 {
1159                   // Absolute beginning.
1160                   __pieces[__slab][__seq].first = 0;
1161                 }
1162               else
1163                 __pieces[__slab][__seq].first =
1164                   __pieces[__slab - 1][__seq].second;
1165               if (!__tight || __slab < (__num_threads - 1))
1166                 __pieces[__slab][__seq].second =
1167                   __offsets[__slab][__seq] - __seqs_begin[__seq].first;
1168               else
1169                 {
1170                   // __slab == __num_threads - 1
1171                   __pieces[__slab][__seq].second =
1172                     _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
1173                 }
1174             }
1175         }
1176       delete[] __offsets;
1177     }
1178
1179   /** @brief Parallel multi-way merge routine.
1180    *
1181    * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1182    * and runtime settings.
1183    *
1184    * Must not be called if the number of sequences is 1.
1185    *
1186    * @param _Splitter functor to split input (either __exact or sampling based)
1187    *
1188    * @param __seqs_begin Begin iterator of iterator pair input sequence.
1189    * @param __seqs_end End iterator of iterator pair input sequence.
1190    * @param __target Begin iterator of output sequence.
1191    * @param __comp Comparator.
1192    * @param __length Maximum length to merge, possibly larger than the
1193    * number of elements available.
1194    * @param __stable Stable merging incurs a performance penalty.
1195    * @param __sentinel Ignored.
1196    * @return End iterator of output sequence.
1197    */
1198   template<bool __stable,
1199            bool __sentinels,
1200            typename _RAIterIterator,
1201            typename _RAIter3,
1202            typename _DifferenceTp,
1203            typename _Splitter,
1204            typename _Compare>
1205     _RAIter3
1206     parallel_multiway_merge(_RAIterIterator __seqs_begin,
1207                             _RAIterIterator __seqs_end,
1208                             _RAIter3 __target,
1209                             _Splitter __splitter,
1210                             _DifferenceTp __length,
1211                             _Compare __comp,
1212                             _ThreadIndex __num_threads)
1213       {
1214 #if _GLIBCXX_ASSERTIONS
1215         _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
1216 #endif
1217
1218         _GLIBCXX_CALL(__length)
1219
1220         typedef _DifferenceTp _DifferenceType;
1221         typedef typename std::iterator_traits<_RAIterIterator>
1222           ::value_type::first_type
1223           _RAIter1;
1224         typedef typename
1225           std::iterator_traits<_RAIter1>::value_type _ValueType;
1226
1227         // Leave only non-empty sequences.
1228         typedef std::pair<_RAIter1, _RAIter1> seq_type;
1229         seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
1230         int __k = 0;
1231         _DifferenceType __total_length = 0;
1232         for (_RAIterIterator __raii = __seqs_begin;
1233              __raii != __seqs_end; ++__raii)
1234           {
1235             _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1236             if(__seq_length > 0)
1237               {
1238                 __total_length += __seq_length;
1239                 __ne_seqs[__k++] = *__raii;
1240               }
1241           }
1242
1243         _GLIBCXX_CALL(__total_length)
1244
1245         __length = std::min<_DifferenceTp>(__length, __total_length);
1246
1247         if (__total_length == 0 || __k == 0)
1248         {
1249           delete[] __ne_seqs;
1250           return __target;
1251         }
1252
1253         std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
1254
1255         __num_threads = static_cast<_ThreadIndex>
1256           (std::min<_DifferenceType>(__num_threads, __total_length));
1257
1258 #       pragma omp parallel num_threads (__num_threads)
1259         {
1260 #         pragma omp single
1261           {
1262             __num_threads = omp_get_num_threads();
1263             // Thread __t will have to merge pieces[__iam][0..__k - 1]
1264             __pieces = new std::vector<
1265             std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
1266             for (int __s = 0; __s < __num_threads; ++__s)
1267               __pieces[__s].resize(__k);
1268
1269             _DifferenceType __num_samples =
1270               __gnu_parallel::_Settings::get().merge_oversampling
1271               * __num_threads;
1272
1273             __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
1274                        __comp, __pieces);
1275           } //single
1276
1277           _ThreadIndex __iam = omp_get_thread_num();
1278
1279           _DifferenceType __target_position = 0;
1280
1281           for (int __c = 0; __c < __k; ++__c)
1282             __target_position += __pieces[__iam][__c].first;
1283
1284           seq_type* __chunks = new seq_type[__k];
1285
1286           for (int __s = 0; __s < __k; ++__s)
1287             __chunks[__s] = std::make_pair(__ne_seqs[__s].first
1288                                            + __pieces[__iam][__s].first,
1289                                            __ne_seqs[__s].first
1290                                            + __pieces[__iam][__s].second);
1291
1292           if(__length > __target_position)
1293             __sequential_multiway_merge<__stable, __sentinels>
1294               (__chunks, __chunks + __k, __target + __target_position,
1295                *(__seqs_begin->second), __length - __target_position, __comp);
1296
1297           delete[] __chunks;
1298         } // parallel
1299
1300 #if _GLIBCXX_ASSERTIONS
1301         _GLIBCXX_PARALLEL_ASSERT(
1302           __is_sorted(__target, __target + __length, __comp));
1303 #endif
1304
1305         __k = 0;
1306         // Update ends of sequences.
1307         for (_RAIterIterator __raii = __seqs_begin;
1308              __raii != __seqs_end; ++__raii)
1309           {
1310             _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
1311             if(__length > 0)
1312               (*__raii).first += __pieces[__num_threads - 1][__k++].second;
1313           }
1314
1315         delete[] __pieces;
1316         delete[] __ne_seqs;
1317
1318         return __target + __length;
1319       }
1320
1321   /**
1322    * @brief Multiway Merge Frontend.
1323    *
1324    * Merge the sequences specified by seqs_begin and __seqs_end into
1325    * __target.  __seqs_begin and __seqs_end must point to a sequence of
1326    * pairs.  These pairs must contain an iterator to the beginning
1327    * of a sequence in their first entry and an iterator the _M_end of
1328    * the same sequence in their second entry.
1329    *
1330    * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1331    * that breaks ties by sequence number but is slower.
1332    *
1333    * The first entries of the pairs (i.e. the begin iterators) will be moved
1334    * forward.
1335    *
1336    * The output sequence has to provide enough space for all elements
1337    * that are written to it.
1338    *
1339    * This function will merge the input sequences:
1340    *
1341    * - not stable
1342    * - parallel, depending on the input size and Settings
1343    * - using sampling for splitting
1344    * - not using sentinels
1345    *
1346    * Example:
1347    *
1348    * <pre>
1349    *   int sequences[10][10];
1350    *   for (int __i = 0; __i < 10; ++__i)
1351    *     for (int __j = 0; __i < 10; ++__j)
1352    *       sequences[__i][__j] = __j;
1353    *
1354    *   int __out[33];
1355    *   std::vector<std::pair<int*> > seqs;
1356    *   for (int __i = 0; __i < 10; ++__i)
1357    *     { seqs.push(std::make_pair<int*>(sequences[__i],
1358    *                                      sequences[__i] + 10)) }
1359    *
1360    *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1361    * </pre>
1362    *
1363    * @see stable_multiway_merge
1364    *
1365    * @pre All input sequences must be sorted.
1366    * @pre Target must provide enough space to merge out length elements or
1367    *    the number of elements in all sequences, whichever is smaller.
1368    *
1369    * @post [__target, return __value) contains merged __elements from the
1370    *    input sequences.
1371    * @post return __value - __target = min(__length, number of elements in all
1372    *    sequences).
1373    *
1374    * @param _RAIterPairIterator iterator over sequence
1375    *    of pairs of iterators
1376    * @param _RAIterOut iterator over target sequence
1377    * @param _DifferenceTp difference type for the sequence
1378    * @param _Compare strict weak ordering type to compare elements
1379    *    in sequences
1380    *
1381    * @param __seqs_begin  __begin of sequence __sequence
1382    * @param __seqs_end    _M_end of sequence __sequence
1383    * @param __target      target sequence to merge to.
1384    * @param __comp        strict weak ordering to use for element comparison.
1385    * @param __length Maximum length to merge, possibly larger than the
1386    * number of elements available.
1387    *
1388    * @return _M_end iterator of output sequence
1389    */
1390   // multiway_merge
1391   // public interface
1392   template<typename _RAIterPairIterator,
1393            typename _RAIterOut,
1394            typename _DifferenceTp,
1395            typename _Compare>
1396     _RAIterOut
1397     multiway_merge(_RAIterPairIterator __seqs_begin,
1398                    _RAIterPairIterator __seqs_end,
1399                    _RAIterOut __target,
1400                    _DifferenceTp __length, _Compare __comp,
1401                    __gnu_parallel::sequential_tag)
1402     {
1403       typedef _DifferenceTp _DifferenceType;
1404       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1405
1406       // catch special case: no sequences
1407       if (__seqs_begin == __seqs_end)
1408         return __target;
1409
1410       // Execute multiway merge *sequentially*.
1411       return __sequential_multiway_merge
1412         </* __stable = */ false, /* __sentinels = */ false>
1413         (__seqs_begin, __seqs_end, __target,
1414          *(__seqs_begin->second), __length, __comp);
1415     }
1416
1417   // public interface
1418   template<typename _RAIterPairIterator,
1419            typename _RAIterOut,
1420            typename _DifferenceTp,
1421            typename _Compare>
1422     _RAIterOut
1423     multiway_merge(_RAIterPairIterator __seqs_begin,
1424                    _RAIterPairIterator __seqs_end,
1425                    _RAIterOut __target,
1426                    _DifferenceTp __length, _Compare __comp,
1427                    __gnu_parallel::exact_tag __tag)
1428     {
1429       typedef _DifferenceTp _DifferenceType;
1430       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1431
1432       // catch special case: no sequences
1433       if (__seqs_begin == __seqs_end)
1434         return __target;
1435
1436       // Execute merge; maybe parallel, depending on the number of merged
1437       // elements and the number of sequences and global thresholds in
1438       // Settings.
1439       if ((__seqs_end - __seqs_begin > 1)
1440           && _GLIBCXX_PARALLEL_CONDITION(
1441             ((__seqs_end - __seqs_begin) >=
1442                __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1443             && ((_SequenceIndex)__length >=
1444               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1445         return parallel_multiway_merge
1446           </* __stable = */ false, /* __sentinels = */ false>
1447           (__seqs_begin, __seqs_end, __target,
1448            multiway_merge_exact_splitting</* __stable = */ false,
1449            typename std::iterator_traits<_RAIterPairIterator>
1450            ::value_type*, _Compare, _DifferenceTp>,
1451            static_cast<_DifferenceType>(__length), __comp,
1452            __tag.__get_num_threads());
1453       else
1454         return __sequential_multiway_merge
1455           </* __stable = */ false, /* __sentinels = */ false>
1456           (__seqs_begin, __seqs_end, __target,
1457            *(__seqs_begin->second), __length, __comp);
1458     }
1459
1460   // public interface
1461   template<typename _RAIterPairIterator,
1462            typename _RAIterOut,
1463            typename _DifferenceTp,
1464            typename _Compare>
1465     _RAIterOut
1466     multiway_merge(_RAIterPairIterator __seqs_begin,
1467                    _RAIterPairIterator __seqs_end,
1468                    _RAIterOut __target,
1469                    _DifferenceTp __length, _Compare __comp,
1470                    __gnu_parallel::sampling_tag __tag)
1471     {
1472       typedef _DifferenceTp _DifferenceType;
1473       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1474
1475       // catch special case: no sequences
1476       if (__seqs_begin == __seqs_end)
1477         return __target;
1478
1479       // Execute merge; maybe parallel, depending on the number of merged
1480       // elements and the number of sequences and global thresholds in
1481       // Settings.
1482       if ((__seqs_end - __seqs_begin > 1)
1483           && _GLIBCXX_PARALLEL_CONDITION(
1484             ((__seqs_end - __seqs_begin) >=
1485                __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1486             && ((_SequenceIndex)__length >=
1487               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1488         return parallel_multiway_merge
1489           </* __stable = */ false, /* __sentinels = */ false>
1490           (__seqs_begin, __seqs_end, __target,
1491            multiway_merge_exact_splitting</* __stable = */ false,
1492            typename std::iterator_traits<_RAIterPairIterator>
1493            ::value_type*, _Compare, _DifferenceTp>,
1494            static_cast<_DifferenceType>(__length), __comp,
1495            __tag.__get_num_threads());
1496       else
1497         return __sequential_multiway_merge
1498           </* __stable = */ false, /* __sentinels = */ false>
1499           (__seqs_begin, __seqs_end, __target,
1500            *(__seqs_begin->second), __length, __comp);
1501     }
1502
1503   // public interface
1504   template<typename _RAIterPairIterator,
1505            typename _RAIterOut,
1506            typename _DifferenceTp,
1507            typename _Compare>
1508     _RAIterOut
1509     multiway_merge(_RAIterPairIterator __seqs_begin,
1510                    _RAIterPairIterator __seqs_end,
1511                    _RAIterOut __target,
1512                    _DifferenceTp __length, _Compare __comp,
1513                    parallel_tag __tag = parallel_tag(0))
1514     { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1515                             __comp, exact_tag(__tag.__get_num_threads())); }
1516
1517   // public interface
1518   template<typename _RAIterPairIterator,
1519            typename _RAIterOut,
1520            typename _DifferenceTp,
1521            typename _Compare>
1522     _RAIterOut
1523     multiway_merge(_RAIterPairIterator __seqs_begin,
1524                    _RAIterPairIterator __seqs_end,
1525                    _RAIterOut __target,
1526                    _DifferenceTp __length, _Compare __comp,
1527                    default_parallel_tag __tag)
1528     { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
1529                             __comp, exact_tag(__tag.__get_num_threads())); }
1530
1531   // stable_multiway_merge
1532   // public interface
1533   template<typename _RAIterPairIterator,
1534            typename _RAIterOut,
1535            typename _DifferenceTp,
1536            typename _Compare>
1537     _RAIterOut
1538     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1539                           _RAIterPairIterator __seqs_end,
1540                           _RAIterOut __target,
1541                           _DifferenceTp __length, _Compare __comp,
1542                           __gnu_parallel::sequential_tag)
1543     {
1544       typedef _DifferenceTp _DifferenceType;
1545       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1546
1547       // catch special case: no sequences
1548       if (__seqs_begin == __seqs_end)
1549         return __target;
1550
1551       // Execute multiway merge *sequentially*.
1552       return __sequential_multiway_merge
1553         </* __stable = */ true, /* __sentinels = */ false>
1554           (__seqs_begin, __seqs_end, __target,
1555            *(__seqs_begin->second), __length, __comp);
1556     }
1557
1558   // public interface
1559   template<typename _RAIterPairIterator,
1560            typename _RAIterOut,
1561            typename _DifferenceTp,
1562            typename _Compare>
1563     _RAIterOut
1564     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1565                           _RAIterPairIterator __seqs_end,
1566                           _RAIterOut __target,
1567                           _DifferenceTp __length, _Compare __comp,
1568                           __gnu_parallel::exact_tag __tag)
1569     {
1570       typedef _DifferenceTp _DifferenceType;
1571       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1572
1573       // catch special case: no sequences
1574       if (__seqs_begin == __seqs_end)
1575         return __target;
1576
1577       // Execute merge; maybe parallel, depending on the number of merged
1578       // elements and the number of sequences and global thresholds in
1579       // Settings.
1580       if ((__seqs_end - __seqs_begin > 1)
1581           && _GLIBCXX_PARALLEL_CONDITION(
1582             ((__seqs_end - __seqs_begin) >=
1583               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1584             && ((_SequenceIndex)__length >=
1585               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1586         return parallel_multiway_merge
1587           </* __stable = */ true, /* __sentinels = */ false>
1588           (__seqs_begin, __seqs_end, __target,
1589            multiway_merge_exact_splitting</* __stable = */ true,
1590            typename std::iterator_traits<_RAIterPairIterator>
1591            ::value_type*, _Compare, _DifferenceTp>,
1592            static_cast<_DifferenceType>(__length), __comp,
1593            __tag.__get_num_threads());
1594       else
1595         return __sequential_multiway_merge
1596           </* __stable = */ true, /* __sentinels = */ false>
1597           (__seqs_begin, __seqs_end, __target,
1598            *(__seqs_begin->second), __length, __comp);
1599     }
1600
1601   // public interface
1602   template<typename _RAIterPairIterator,
1603            typename _RAIterOut,
1604            typename _DifferenceTp,
1605            typename _Compare>
1606     _RAIterOut
1607     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1608                           _RAIterPairIterator __seqs_end,
1609                           _RAIterOut __target,
1610                           _DifferenceTp __length, _Compare __comp,
1611                           sampling_tag __tag)
1612     {
1613       typedef _DifferenceTp _DifferenceType;
1614       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1615
1616       // catch special case: no sequences
1617       if (__seqs_begin == __seqs_end)
1618         return __target;
1619
1620       // Execute merge; maybe parallel, depending on the number of merged
1621       // elements and the number of sequences and global thresholds in
1622       // Settings.
1623       if ((__seqs_end - __seqs_begin > 1)
1624           && _GLIBCXX_PARALLEL_CONDITION(
1625             ((__seqs_end - __seqs_begin) >=
1626               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1627             && ((_SequenceIndex)__length >=
1628               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1629         return parallel_multiway_merge
1630           </* __stable = */ true, /* __sentinels = */ false>
1631           (__seqs_begin, __seqs_end, __target,
1632            multiway_merge_sampling_splitting</* __stable = */ true,
1633            typename std::iterator_traits<_RAIterPairIterator>
1634            ::value_type*, _Compare, _DifferenceTp>,
1635            static_cast<_DifferenceType>(__length), __comp,
1636            __tag.__get_num_threads());
1637       else
1638         return __sequential_multiway_merge
1639           </* __stable = */ true, /* __sentinels = */ false>
1640           (__seqs_begin, __seqs_end, __target,
1641            *(__seqs_begin->second), __length, __comp);
1642     }
1643
1644   // public interface
1645   template<typename _RAIterPairIterator,
1646            typename _RAIterOut,
1647            typename _DifferenceTp,
1648            typename _Compare>
1649     _RAIterOut
1650     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1651                           _RAIterPairIterator __seqs_end,
1652                           _RAIterOut __target,
1653                           _DifferenceTp __length, _Compare __comp,
1654                           parallel_tag __tag = parallel_tag(0))
1655     {
1656       return stable_multiway_merge
1657         (__seqs_begin, __seqs_end, __target, __length, __comp,
1658          exact_tag(__tag.__get_num_threads()));
1659     }
1660
1661   // public interface
1662   template<typename _RAIterPairIterator,
1663            typename _RAIterOut,
1664            typename _DifferenceTp,
1665            typename _Compare>
1666     _RAIterOut
1667     stable_multiway_merge(_RAIterPairIterator __seqs_begin,
1668                           _RAIterPairIterator __seqs_end,
1669                           _RAIterOut __target,
1670                           _DifferenceTp __length, _Compare __comp,
1671                           default_parallel_tag __tag)
1672     {
1673       return stable_multiway_merge
1674         (__seqs_begin, __seqs_end, __target, __length, __comp,
1675          exact_tag(__tag.__get_num_threads()));
1676     }
1677
1678   /**
1679    * @brief Multiway Merge Frontend.
1680    *
1681    * Merge the sequences specified by seqs_begin and __seqs_end into
1682    * __target.  __seqs_begin and __seqs_end must point to a sequence of
1683    * pairs.  These pairs must contain an iterator to the beginning
1684    * of a sequence in their first entry and an iterator the _M_end of
1685    * the same sequence in their second entry.
1686    *
1687    * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
1688    * that breaks ties by sequence number but is slower.
1689    *
1690    * The first entries of the pairs (i.e. the begin iterators) will be moved
1691    * forward accordingly.
1692    *
1693    * The output sequence has to provide enough space for all elements
1694    * that are written to it.
1695    *
1696    * This function will merge the input sequences:
1697    *
1698    * - not stable
1699    * - parallel, depending on the input size and Settings
1700    * - using sampling for splitting
1701    * - using sentinels
1702    *
1703    * You have to take care that the element the _M_end iterator points to is
1704    * readable and contains a value that is greater than any other non-sentinel
1705    * value in all sequences.
1706    *
1707    * Example:
1708    *
1709    * <pre>
1710    *   int sequences[10][11];
1711    *   for (int __i = 0; __i < 10; ++__i)
1712    *     for (int __j = 0; __i < 11; ++__j)
1713    *       sequences[__i][__j] = __j; // __last one is sentinel!
1714    *
1715    *   int __out[33];
1716    *   std::vector<std::pair<int*> > seqs;
1717    *   for (int __i = 0; __i < 10; ++__i)
1718    *     { seqs.push(std::make_pair<int*>(sequences[__i],
1719    *                                      sequences[__i] + 10)) }
1720    *
1721    *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1722    * </pre>
1723    *
1724    * @pre All input sequences must be sorted.
1725    * @pre Target must provide enough space to merge out length elements or
1726    *    the number of elements in all sequences, whichever is smaller.
1727    * @pre For each @__c __i, @__c __seqs_begin[__i].second must be the end
1728    *    marker of the sequence, but also reference the one more __sentinel
1729    *    element.
1730    *
1731    * @post [__target, return __value) contains merged __elements from the
1732    *    input sequences.
1733    * @post return __value - __target = min(__length, number of elements in all
1734    *    sequences).
1735    *
1736    * @see stable_multiway_merge_sentinels
1737    *
1738    * @param _RAIterPairIterator iterator over sequence
1739    *    of pairs of iterators
1740    * @param _RAIterOut iterator over target sequence
1741    * @param _DifferenceTp difference type for the sequence
1742    * @param _Compare strict weak ordering type to compare elements
1743    *    in sequences
1744    *
1745    * @param __seqs_begin  __begin of sequence __sequence
1746    * @param __seqs_end    _M_end of sequence __sequence
1747    * @param __target      target sequence to merge to.
1748    * @param __comp        strict weak ordering to use for element comparison.
1749    * @param __length Maximum length to merge, possibly larger than the
1750    * number of elements available.
1751    *
1752    * @return _M_end iterator of output sequence
1753    */
1754   // multiway_merge_sentinels
1755   // public interface
1756   template<typename _RAIterPairIterator,
1757            typename _RAIterOut,
1758            typename _DifferenceTp,
1759            typename _Compare>
1760     _RAIterOut
1761     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1762                              _RAIterPairIterator __seqs_end,
1763                              _RAIterOut __target,
1764                              _DifferenceTp __length, _Compare __comp,
1765                              __gnu_parallel::sequential_tag)
1766     {
1767       typedef _DifferenceTp _DifferenceType;
1768       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1769
1770       // catch special case: no sequences
1771       if (__seqs_begin == __seqs_end)
1772         return __target;
1773
1774       // Execute multiway merge *sequentially*.
1775       return __sequential_multiway_merge
1776         </* __stable = */ false, /* __sentinels = */ true>
1777           (__seqs_begin, __seqs_end,
1778            __target, *(__seqs_begin->second), __length, __comp);
1779     }
1780
1781   // public interface
1782   template<typename _RAIterPairIterator,
1783            typename _RAIterOut,
1784            typename _DifferenceTp,
1785            typename _Compare>
1786     _RAIterOut
1787     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1788                              _RAIterPairIterator __seqs_end,
1789                              _RAIterOut __target,
1790                              _DifferenceTp __length, _Compare __comp,
1791                              __gnu_parallel::exact_tag __tag)
1792     {
1793       typedef _DifferenceTp _DifferenceType;
1794       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1795
1796       // catch special case: no sequences
1797       if (__seqs_begin == __seqs_end)
1798         return __target;
1799
1800       // Execute merge; maybe parallel, depending on the number of merged
1801       // elements and the number of sequences and global thresholds in
1802       // Settings.
1803       if ((__seqs_end - __seqs_begin > 1)
1804           && _GLIBCXX_PARALLEL_CONDITION(
1805             ((__seqs_end - __seqs_begin) >=
1806               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1807             && ((_SequenceIndex)__length >=
1808               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1809         return parallel_multiway_merge
1810           </* __stable = */ false, /* __sentinels = */ true>
1811           (__seqs_begin, __seqs_end, __target,
1812            multiway_merge_exact_splitting</* __stable = */ false,
1813            typename std::iterator_traits<_RAIterPairIterator>
1814            ::value_type*, _Compare, _DifferenceTp>,
1815            static_cast<_DifferenceType>(__length), __comp,
1816            __tag.__get_num_threads());
1817       else
1818         return __sequential_multiway_merge
1819           </* __stable = */ false, /* __sentinels = */ true>
1820           (__seqs_begin, __seqs_end, __target,
1821            *(__seqs_begin->second), __length, __comp);
1822     }
1823
1824   // public interface
1825   template<typename _RAIterPairIterator,
1826            typename _RAIterOut,
1827            typename _DifferenceTp,
1828            typename _Compare>
1829     _RAIterOut
1830     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1831                              _RAIterPairIterator __seqs_end,
1832                              _RAIterOut __target,
1833                              _DifferenceTp __length, _Compare __comp,
1834                              sampling_tag __tag)
1835     {
1836       typedef _DifferenceTp _DifferenceType;
1837       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1838
1839       // catch special case: no sequences
1840       if (__seqs_begin == __seqs_end)
1841         return __target;
1842
1843       // Execute merge; maybe parallel, depending on the number of merged
1844       // elements and the number of sequences and global thresholds in
1845       // Settings.
1846       if ((__seqs_end - __seqs_begin > 1)
1847           && _GLIBCXX_PARALLEL_CONDITION(
1848             ((__seqs_end - __seqs_begin) >=
1849               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1850             && ((_SequenceIndex)__length >=
1851               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1852         return parallel_multiway_merge
1853           </* __stable = */ false, /* __sentinels = */ true>
1854           (__seqs_begin, __seqs_end, __target,
1855            multiway_merge_sampling_splitting</* __stable = */ false,
1856            typename std::iterator_traits<_RAIterPairIterator>
1857            ::value_type*, _Compare, _DifferenceTp>,
1858            static_cast<_DifferenceType>(__length), __comp,
1859            __tag.__get_num_threads());
1860       else
1861         return __sequential_multiway_merge
1862           </* __stable = */false, /* __sentinels = */ true>(
1863             __seqs_begin, __seqs_end, __target,
1864             *(__seqs_begin->second), __length, __comp);
1865     }
1866
1867   // public interface
1868   template<typename _RAIterPairIterator,
1869            typename _RAIterOut,
1870            typename _DifferenceTp,
1871            typename _Compare>
1872     _RAIterOut
1873     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1874                              _RAIterPairIterator __seqs_end,
1875                              _RAIterOut __target,
1876                              _DifferenceTp __length, _Compare __comp,
1877                              parallel_tag __tag = parallel_tag(0))
1878     {
1879       return multiway_merge_sentinels
1880         (__seqs_begin, __seqs_end, __target, __length, __comp,
1881          exact_tag(__tag.__get_num_threads()));
1882     }
1883
1884   // public interface
1885   template<typename _RAIterPairIterator,
1886            typename _RAIterOut,
1887            typename _DifferenceTp,
1888            typename _Compare>
1889     _RAIterOut
1890     multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1891                              _RAIterPairIterator __seqs_end,
1892                              _RAIterOut __target,
1893                              _DifferenceTp __length, _Compare __comp,
1894                              default_parallel_tag __tag)
1895     {
1896       return multiway_merge_sentinels
1897         (__seqs_begin, __seqs_end, __target, __length, __comp,
1898          exact_tag(__tag.__get_num_threads()));
1899     }
1900
1901   // stable_multiway_merge_sentinels
1902   // public interface
1903   template<typename _RAIterPairIterator,
1904            typename _RAIterOut,
1905            typename _DifferenceTp,
1906            typename _Compare>
1907     _RAIterOut
1908     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1909                                     _RAIterPairIterator __seqs_end,
1910                                     _RAIterOut __target,
1911                                     _DifferenceTp __length, _Compare __comp,
1912                                     __gnu_parallel::sequential_tag)
1913     {
1914       typedef _DifferenceTp _DifferenceType;
1915       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1916
1917       // catch special case: no sequences
1918       if (__seqs_begin == __seqs_end)
1919         return __target;
1920
1921       // Execute multiway merge *sequentially*.
1922       return __sequential_multiway_merge
1923         </* __stable = */ true, /* __sentinels = */ true>
1924         (__seqs_begin, __seqs_end, __target,
1925          *(__seqs_begin->second), __length, __comp);
1926     }
1927
1928   // public interface
1929   template<typename _RAIterPairIterator,
1930            typename _RAIterOut,
1931            typename _DifferenceTp,
1932            typename _Compare>
1933     _RAIterOut
1934     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1935                                     _RAIterPairIterator __seqs_end,
1936                                     _RAIterOut __target,
1937                                     _DifferenceTp __length, _Compare __comp,
1938                                     __gnu_parallel::exact_tag __tag)
1939     {
1940       typedef _DifferenceTp _DifferenceType;
1941       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1942
1943       // catch special case: no sequences
1944       if (__seqs_begin == __seqs_end)
1945         return __target;
1946
1947       // Execute merge; maybe parallel, depending on the number of merged
1948       // elements and the number of sequences and global thresholds in
1949       // Settings.
1950       if ((__seqs_end - __seqs_begin > 1)
1951           && _GLIBCXX_PARALLEL_CONDITION(
1952             ((__seqs_end - __seqs_begin) >=
1953             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1954             && ((_SequenceIndex)__length >=
1955             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
1956         return parallel_multiway_merge
1957           </* __stable = */ true, /* __sentinels = */ true>
1958           (__seqs_begin, __seqs_end, __target,
1959            multiway_merge_exact_splitting</* __stable = */ true,
1960            typename std::iterator_traits<_RAIterPairIterator>
1961            ::value_type*, _Compare, _DifferenceTp>,
1962            static_cast<_DifferenceType>(__length), __comp,
1963            __tag.__get_num_threads());
1964       else
1965         return __sequential_multiway_merge
1966           </* __stable = */ true, /* __sentinels = */ true>
1967           (__seqs_begin, __seqs_end, __target,
1968            *(__seqs_begin->second), __length, __comp);
1969     }
1970
1971   // public interface
1972   template<typename _RAIterPairIterator,
1973            typename _RAIterOut,
1974            typename _DifferenceTp,
1975            typename _Compare>
1976     _RAIterOut
1977     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
1978                                     _RAIterPairIterator __seqs_end,
1979                                     _RAIterOut __target,
1980                                     _DifferenceTp __length,
1981                                     _Compare __comp,
1982                                     sampling_tag __tag)
1983     {
1984       typedef _DifferenceTp _DifferenceType;
1985       _GLIBCXX_CALL(__seqs_end - __seqs_begin)
1986
1987       // catch special case: no sequences
1988       if (__seqs_begin == __seqs_end)
1989         return __target;
1990
1991       // Execute merge; maybe parallel, depending on the number of merged
1992       // elements and the number of sequences and global thresholds in
1993       // Settings.
1994       if ((__seqs_end - __seqs_begin > 1)
1995           && _GLIBCXX_PARALLEL_CONDITION(
1996             ((__seqs_end - __seqs_begin) >=
1997               __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
1998             && ((_SequenceIndex)__length >=
1999               __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
2000         return parallel_multiway_merge
2001           </* __stable = */ true, /* __sentinels = */ true>
2002           (__seqs_begin, __seqs_end, __target,
2003            multiway_merge_sampling_splitting</* __stable = */ true,
2004            typename std::iterator_traits<_RAIterPairIterator>
2005            ::value_type*, _Compare, _DifferenceTp>,
2006            static_cast<_DifferenceType>(__length), __comp,
2007            __tag.__get_num_threads());
2008       else
2009         return __sequential_multiway_merge
2010           </* __stable = */ true, /* __sentinels = */ true>
2011           (__seqs_begin, __seqs_end, __target,
2012            *(__seqs_begin->second), __length, __comp);
2013     }
2014
2015   // public interface
2016   template<typename _RAIterPairIterator,
2017            typename _RAIterOut,
2018            typename _DifferenceTp,
2019            typename _Compare>
2020     _RAIterOut
2021     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2022                                     _RAIterPairIterator __seqs_end,
2023                                     _RAIterOut __target,
2024                                     _DifferenceTp __length,
2025                                     _Compare __comp,
2026                                     parallel_tag __tag = parallel_tag(0))
2027     {
2028       return stable_multiway_merge_sentinels
2029         (__seqs_begin, __seqs_end, __target, __length, __comp,
2030          exact_tag(__tag.__get_num_threads()));
2031     }
2032
2033   // public interface
2034   template<typename _RAIterPairIterator,
2035            typename _RAIterOut,
2036            typename _DifferenceTp,
2037            typename _Compare>
2038     _RAIterOut
2039     stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
2040                                     _RAIterPairIterator __seqs_end,
2041                                     _RAIterOut __target,
2042                                     _DifferenceTp __length, _Compare __comp,
2043                                     default_parallel_tag __tag)
2044     {
2045       return stable_multiway_merge_sentinels
2046         (__seqs_begin, __seqs_end, __target, __length, __comp,
2047          exact_tag(__tag.__get_num_threads()));
2048     }
2049 }; // namespace __gnu_parallel
2050
2051 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */