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