multiway_merge.h

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

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1