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 
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       std::pair<RandomAccessIterator1, RandomAccessIterator1>* ne_seqs =
01309         static_cast<std::pair<RandomAccessIterator1, RandomAccessIterator1>*>(
01310         ::operator new(
01311             sizeof(std::pair<RandomAccessIterator1, RandomAccessIterator1>)
01312               * (seqs_end - seqs_begin)));
01313       int k = 0;
01314       difference_type total_length = 0;
01315       for (RandomAccessIteratorIterator raii = seqs_begin;
01316            raii != seqs_end; ++raii)
01317         {
01318           _DifferenceTp seq_length = _GLIBCXX_PARALLEL_LENGTH(*raii);
01319           if(seq_length > 0)
01320             {
01321               total_length += seq_length;
01322               //ne_seqs[k] = *raii;
01323               new(&(ne_seqs[k++]))
01324                 std::pair<RandomAccessIterator1, RandomAccessIterator1>(*raii);
01325             }
01326         }
01327 
01328       _GLIBCXX_CALL(total_length)
01329 
01330       length = std::min<_DifferenceTp>(length, total_length);
01331 
01332       if (total_length == 0 || k == 0)
01333       {
01334         ::operator delete(ne_seqs);
01335         return target;
01336       }
01337 
01338       std::vector<std::pair<difference_type, difference_type> >* pieces;
01339 
01340       num_threads = static_cast<thread_index_t>
01341         (std::min<difference_type>(num_threads, total_length));
01342 
01343 #     pragma omp parallel num_threads (num_threads)
01344         {
01345 #         pragma omp single
01346             {
01347               num_threads = omp_get_num_threads();
01348               // Thread t will have to merge pieces[iam][0..k - 1]
01349               pieces = new std::vector<
01350                   std::pair<difference_type, difference_type> >[num_threads];
01351               for (int s = 0; s < num_threads; ++s)
01352                 pieces[s].resize(k);
01353 
01354               difference_type num_samples =
01355                   __gnu_parallel::_Settings::get().merge_oversampling *
01356                     num_threads;
01357 
01358               splitter(ne_seqs, ne_seqs + k, length, total_length,
01359                        comp, pieces);
01360             } //single
01361 
01362           thread_index_t iam = omp_get_thread_num();
01363 
01364           difference_type target_position = 0;
01365 
01366           for (int c = 0; c < k; ++c)
01367             target_position += pieces[iam][c].first;
01368 
01369           std::pair<RandomAccessIterator1, RandomAccessIterator1>* chunks
01370             = new std::pair<RandomAccessIterator1, RandomAccessIterator1>[k];
01371 
01372           for (int s = 0; s < k; ++s)
01373             {
01374               chunks[s] = std::make_pair(
01375                 ne_seqs[s].first + pieces[iam][s].first,
01376                 ne_seqs[s].first + pieces[iam][s].second);
01377             }
01378 
01379           if(length > target_position)
01380             sequential_multiway_merge<stable, sentinels>(
01381               chunks, chunks + k, target + target_position,
01382                *(seqs_begin->second), length - target_position, comp);
01383 
01384           delete[] chunks;
01385         } // parallel
01386 
01387 #if _GLIBCXX_ASSERTIONS
01388       _GLIBCXX_PARALLEL_ASSERT(is_sorted(target, target + length, comp));
01389 #endif
01390 
01391       k = 0;
01392       // Update ends of sequences.
01393       for (RandomAccessIteratorIterator raii = seqs_begin;
01394            raii != seqs_end; ++raii)
01395         {
01396           _DifferenceTp length = _GLIBCXX_PARALLEL_LENGTH(*raii);
01397           if(length > 0)
01398             (*raii).first += pieces[num_threads - 1][k++].second;
01399         }
01400 
01401       delete[] pieces;
01402 
01403       return target + length;
01404     }
01405 
01406 /**
01407  * @brief Multiway Merge Frontend.
01408  *
01409  * Merge the sequences specified by seqs_begin and seqs_end into
01410  * target.  seqs_begin and seqs_end must point to a sequence of
01411  * pairs.  These pairs must contain an iterator to the beginning
01412  * of a sequence in their first entry and an iterator the end of
01413  * the same sequence in their second entry.
01414  *
01415  * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
01416  * that breaks ties by sequence number but is slower.
01417  *
01418  * The first entries of the pairs (i.e. the begin iterators) will be moved
01419  * forward.
01420  *
01421  * The output sequence has to provide enough space for all elements
01422  * that are written to it.
01423  *
01424  * This function will merge the input sequences:
01425  *
01426  * - not stable
01427  * - parallel, depending on the input size and Settings
01428  * - using sampling for splitting
01429  * - not using sentinels
01430  *
01431  * Example:
01432  *
01433  * <pre>
01434  *   int sequences[10][10];
01435  *   for (int i = 0; i < 10; ++i)
01436  *     for (int j = 0; i < 10; ++j)
01437  *       sequences[i][j] = j;
01438  *
01439  *   int out[33];
01440  *   std::vector<std::pair<int*> > seqs;
01441  *   for (int i = 0; i < 10; ++i)
01442  *     { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
01443  *
01444  *   multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
01445  * </pre>
01446  *
01447  * @see stable_multiway_merge
01448  *
01449  * @pre All input sequences must be sorted.
01450  * @pre Target must provide enough space to merge out length elements or
01451  *    the number of elements in all sequences, whichever is smaller.
01452  *
01453  * @post [target, return value) contains merged elements from the
01454  *    input sequences.
01455  * @post return value - target = min(length, number of elements in all
01456  *    sequences).
01457  *
01458  * @param RandomAccessIteratorPairIterator iterator over sequence
01459  *    of pairs of iterators
01460  * @param RandomAccessIteratorOut iterator over target sequence
01461  * @param _DifferenceTp difference type for the sequence
01462  * @param Comparator strict weak ordering type to compare elements
01463  *    in sequences
01464  *
01465  * @param seqs_begin  begin of sequence sequence
01466  * @param seqs_end    end of sequence sequence
01467  * @param target      target sequence to merge to.
01468  * @param comp        strict weak ordering to use for element comparison.
01469  * @param length Maximum length to merge, possibly larger than the
01470  * number of elements available.
01471  *
01472  * @return end iterator of output sequence
01473  */
01474 // multiway_merge
01475 // public interface
01476 template<
01477     typename RandomAccessIteratorPairIterator
01478   , typename RandomAccessIteratorOut
01479   , typename _DifferenceTp
01480   , typename Comparator>
01481 RandomAccessIteratorOut
01482 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01483     , RandomAccessIteratorPairIterator seqs_end
01484     , RandomAccessIteratorOut target
01485     , _DifferenceTp length, Comparator comp
01486     , __gnu_parallel::sequential_tag)
01487 {
01488   typedef _DifferenceTp difference_type;
01489   _GLIBCXX_CALL(seqs_end - seqs_begin)
01490 
01491   // catch special case: no sequences
01492   if (seqs_begin == seqs_end)
01493     return target;
01494 
01495   // Execute multiway merge *sequentially*.
01496   return sequential_multiway_merge
01497     </* stable = */ false, /* sentinels = */ false>
01498       (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01499 }
01500 
01501 // public interface
01502 template<
01503     typename RandomAccessIteratorPairIterator
01504   , typename RandomAccessIteratorOut
01505   , typename _DifferenceTp
01506   , typename Comparator>
01507 RandomAccessIteratorOut
01508 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01509     , RandomAccessIteratorPairIterator seqs_end
01510     , RandomAccessIteratorOut target
01511     , _DifferenceTp length, Comparator comp
01512     , __gnu_parallel::exact_tag tag)
01513 {
01514     typedef _DifferenceTp difference_type;
01515     _GLIBCXX_CALL(seqs_end - seqs_begin)
01516 
01517     // catch special case: no sequences
01518     if (seqs_begin == seqs_end)
01519       return target;
01520 
01521     // Execute merge; maybe parallel, depending on the number of merged
01522     // elements and the number of sequences and global thresholds in
01523     // Settings.
01524     if ((seqs_end - seqs_begin > 1) &&
01525           _GLIBCXX_PARALLEL_CONDITION(
01526           ((seqs_end - seqs_begin) >=
01527              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01528           && ((sequence_index_t)length >=
01529             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01530       return parallel_multiway_merge
01531                     </* stable = */ false, /* sentinels = */ false>(
01532           seqs_begin, seqs_end, target,
01533           multiway_merge_exact_splitting</* stable = */ false,
01534             typename std::iterator_traits<RandomAccessIteratorPairIterator>
01535               ::value_type*, Comparator, _DifferenceTp>,
01536           static_cast<difference_type>(length), comp, tag.get_num_threads());
01537     else
01538       return sequential_multiway_merge
01539                       </* stable = */ false, /* sentinels = */ false>(
01540           seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01541 }
01542 
01543 // public interface
01544 template<
01545     typename RandomAccessIteratorPairIterator
01546   , typename RandomAccessIteratorOut
01547   , typename _DifferenceTp
01548   , typename Comparator>
01549 RandomAccessIteratorOut
01550 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01551     , RandomAccessIteratorPairIterator seqs_end
01552     , RandomAccessIteratorOut target
01553     , _DifferenceTp length, Comparator comp
01554     , __gnu_parallel::sampling_tag tag)
01555 {
01556     typedef _DifferenceTp difference_type;
01557     _GLIBCXX_CALL(seqs_end - seqs_begin)
01558 
01559     // catch special case: no sequences
01560     if (seqs_begin == seqs_end)
01561       return target;
01562 
01563     // Execute merge; maybe parallel, depending on the number of merged
01564     // elements and the number of sequences and global thresholds in
01565     // Settings.
01566     if ((seqs_end - seqs_begin > 1) &&
01567           _GLIBCXX_PARALLEL_CONDITION(
01568           ((seqs_end - seqs_begin) >=
01569              __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01570           && ((sequence_index_t)length >=
01571             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01572       return parallel_multiway_merge
01573                     </* stable = */ false, /* sentinels = */ false>(
01574           seqs_begin, seqs_end,
01575           target,
01576           multiway_merge_exact_splitting</* stable = */ false,
01577             typename std::iterator_traits<RandomAccessIteratorPairIterator>
01578               ::value_type*, Comparator, _DifferenceTp>,
01579           static_cast<difference_type>(length), comp, tag.get_num_threads());
01580     else
01581       return sequential_multiway_merge
01582                       </* stable = */ false, /* sentinels = */ false>(
01583           seqs_begin, seqs_end,
01584           target, *(seqs_begin->second), length, comp);
01585 }
01586 
01587 // public interface
01588 template<
01589     typename RandomAccessIteratorPairIterator
01590   , typename RandomAccessIteratorOut
01591   , typename _DifferenceTp
01592   , typename Comparator>
01593 RandomAccessIteratorOut
01594 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01595     , RandomAccessIteratorPairIterator seqs_end
01596     , RandomAccessIteratorOut target
01597     , _DifferenceTp length, Comparator comp
01598     , parallel_tag tag = parallel_tag(0))
01599 {
01600   return multiway_merge(seqs_begin, seqs_end, target, length, comp,
01601                          exact_tag(tag.get_num_threads()));
01602 }
01603 
01604 // public interface
01605 template<
01606     typename RandomAccessIteratorPairIterator
01607   , typename RandomAccessIteratorOut
01608   , typename _DifferenceTp
01609   , typename Comparator>
01610 RandomAccessIteratorOut
01611 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01612     , RandomAccessIteratorPairIterator seqs_end
01613     , RandomAccessIteratorOut target
01614     , _DifferenceTp length, Comparator comp
01615     , default_parallel_tag tag)
01616 {
01617   return multiway_merge(seqs_begin, seqs_end, target, length, comp,
01618                          exact_tag(tag.get_num_threads()));
01619 }
01620 
01621 // stable_multiway_merge
01622 // public interface
01623 template<
01624     typename RandomAccessIteratorPairIterator
01625   , typename RandomAccessIteratorOut
01626   , typename _DifferenceTp
01627   , typename Comparator>
01628 RandomAccessIteratorOut
01629 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01630     , RandomAccessIteratorPairIterator seqs_end
01631     , RandomAccessIteratorOut target
01632     , _DifferenceTp length, Comparator comp
01633     , __gnu_parallel::sequential_tag)
01634 {
01635     typedef _DifferenceTp difference_type;
01636     _GLIBCXX_CALL(seqs_end - seqs_begin)
01637 
01638     // catch special case: no sequences
01639     if (seqs_begin == seqs_end)
01640       return target;
01641 
01642     // Execute multiway merge *sequentially*.
01643     return sequential_multiway_merge
01644       </* stable = */ true, /* sentinels = */ false>
01645         (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
01646 }
01647 
01648 // public interface
01649 template<
01650     typename RandomAccessIteratorPairIterator
01651   , typename RandomAccessIteratorOut
01652   , typename _DifferenceTp
01653   , typename Comparator>
01654 RandomAccessIteratorOut
01655 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01656     , RandomAccessIteratorPairIterator seqs_end
01657     , RandomAccessIteratorOut target
01658     , _DifferenceTp length, Comparator comp
01659     , __gnu_parallel::exact_tag tag)
01660 {
01661     typedef _DifferenceTp difference_type;
01662     _GLIBCXX_CALL(seqs_end - seqs_begin)
01663 
01664     // catch special case: no sequences
01665     if (seqs_begin == seqs_end)
01666       return target;
01667 
01668     // Execute merge; maybe parallel, depending on the number of merged
01669     // elements and the number of sequences and global thresholds in
01670     // Settings.
01671     if ((seqs_end - seqs_begin > 1) &&
01672           _GLIBCXX_PARALLEL_CONDITION(
01673           ((seqs_end - seqs_begin) >=
01674             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01675           && ((sequence_index_t)length >=
01676             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01677       return parallel_multiway_merge
01678         </* stable = */ true, /* sentinels = */ false>(
01679           seqs_begin, seqs_end,
01680           target,
01681           multiway_merge_exact_splitting</* stable = */ true,
01682             typename std::iterator_traits<RandomAccessIteratorPairIterator>
01683               ::value_type*, Comparator, _DifferenceTp>,
01684           static_cast<difference_type>(length), comp, tag.get_num_threads());
01685     else
01686       return sequential_multiway_merge</* stable = */ true,
01687         /* sentinels = */ false>(
01688           seqs_begin, seqs_end,
01689           target, *(seqs_begin->second), length, comp);
01690 }
01691 
01692 // public interface
01693 template<
01694     typename RandomAccessIteratorPairIterator
01695   , typename RandomAccessIteratorOut
01696   , typename _DifferenceTp
01697   , typename Comparator>
01698 RandomAccessIteratorOut
01699 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01700     , RandomAccessIteratorPairIterator seqs_end
01701     , RandomAccessIteratorOut target
01702     , _DifferenceTp length, Comparator comp
01703     , sampling_tag tag)
01704 {
01705     typedef _DifferenceTp difference_type;
01706     _GLIBCXX_CALL(seqs_end - seqs_begin)
01707 
01708     // catch special case: no sequences
01709     if (seqs_begin == seqs_end)
01710       return target;
01711 
01712     // Execute merge; maybe parallel, depending on the number of merged
01713     // elements and the number of sequences and global thresholds in
01714     // Settings.
01715     if ((seqs_end - seqs_begin > 1) &&
01716           _GLIBCXX_PARALLEL_CONDITION(
01717           ((seqs_end - seqs_begin) >=
01718             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01719           && ((sequence_index_t)length >=
01720             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01721       return parallel_multiway_merge
01722         </* stable = */ true, /* sentinels = */ false>(
01723           seqs_begin, seqs_end,
01724           target,
01725           multiway_merge_sampling_splitting</* stable = */ true,
01726             typename std::iterator_traits<RandomAccessIteratorPairIterator>
01727               ::value_type*, Comparator, _DifferenceTp>,
01728           static_cast<difference_type>(length), comp, tag.get_num_threads());
01729     else
01730       return sequential_multiway_merge
01731         </* stable = */ true, /* sentinels = */ false>(
01732           seqs_begin, seqs_end,
01733           target, *(seqs_begin->second), length, comp);
01734 }
01735 
01736 
01737 // public interface
01738 template<
01739     typename RandomAccessIteratorPairIterator
01740   , typename RandomAccessIteratorOut
01741   , typename _DifferenceTp
01742   , typename Comparator>
01743 RandomAccessIteratorOut
01744 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01745     , RandomAccessIteratorPairIterator seqs_end
01746     , RandomAccessIteratorOut target
01747     , _DifferenceTp length, Comparator comp
01748     , parallel_tag tag = parallel_tag(0))
01749 {
01750   return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
01751                          exact_tag(tag.get_num_threads()));
01752 }
01753 
01754 // public interface
01755 template<
01756     typename RandomAccessIteratorPairIterator
01757   , typename RandomAccessIteratorOut
01758   , typename _DifferenceTp
01759   , typename Comparator>
01760 RandomAccessIteratorOut
01761 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
01762     , RandomAccessIteratorPairIterator seqs_end
01763     , RandomAccessIteratorOut target
01764     , _DifferenceTp length, Comparator comp
01765     , default_parallel_tag tag)
01766 {
01767   return stable_multiway_merge(seqs_begin, seqs_end, target, length, comp,
01768                          exact_tag(tag.get_num_threads()));
01769 }
01770 
01771 /**
01772  * @brief Multiway Merge Frontend.
01773  *
01774  * Merge the sequences specified by seqs_begin and seqs_end into
01775  * target.  seqs_begin and seqs_end must point to a sequence of
01776  * pairs.  These pairs must contain an iterator to the beginning
01777  * of a sequence in their first entry and an iterator the end of
01778  * the same sequence in their second entry.
01779  *
01780  * Ties are broken arbitrarily.  See stable_multiway_merge for a variant
01781  * that breaks ties by sequence number but is slower.
01782  *
01783  * The first entries of the pairs (i.e. the begin iterators) will be moved
01784  * forward accordingly.
01785  *
01786  * The output sequence has to provide enough space for all elements
01787  * that are written to it.
01788  *
01789  * This function will merge the input sequences:
01790  *
01791  * - not stable
01792  * - parallel, depending on the input size and Settings
01793  * - using sampling for splitting
01794  * - using sentinels
01795  *
01796  * You have to take care that the element the end iterator points to is
01797  * readable and contains a value that is greater than any other non-sentinel
01798  * value in all sequences.
01799  *
01800  * Example:
01801  *
01802  * <pre>
01803  *   int sequences[10][11];
01804  *   for (int i = 0; i < 10; ++i)
01805  *     for (int j = 0; i < 11; ++j)
01806  *       sequences[i][j] = j; // last one is sentinel!
01807  *
01808  *   int out[33];
01809  *   std::vector<std::pair<int*> > seqs;
01810  *   for (int i = 0; i < 10; ++i)
01811  *     { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
01812  *
01813  *   multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
01814  * </pre>
01815  *
01816  * @pre All input sequences must be sorted.
01817  * @pre Target must provide enough space to merge out length elements or
01818  *    the number of elements in all sequences, whichever is smaller.
01819  * @pre For each @c i, @c seqs_begin[i].second must be the end
01820  *    marker of the sequence, but also reference the one more sentinel
01821  *    element.
01822  *
01823  * @post [target, return value) contains merged elements from the
01824  *    input sequences.
01825  * @post return value - target = min(length, number of elements in all
01826  *    sequences).
01827  *
01828  * @see stable_multiway_merge_sentinels
01829  *
01830  * @param RandomAccessIteratorPairIterator iterator over sequence
01831  *    of pairs of iterators
01832  * @param RandomAccessIteratorOut iterator over target sequence
01833  * @param _DifferenceTp difference type for the sequence
01834  * @param Comparator strict weak ordering type to compare elements
01835  *    in sequences
01836  *
01837  * @param seqs_begin  begin of sequence sequence
01838  * @param seqs_end    end of sequence sequence
01839  * @param target      target sequence to merge to.
01840  * @param comp        strict weak ordering to use for element comparison.
01841  * @param length Maximum length to merge, possibly larger than the
01842  * number of elements available.
01843  *
01844  * @return end iterator of output sequence
01845  */
01846 // multiway_merge_sentinels
01847 // public interface
01848 template<
01849     typename RandomAccessIteratorPairIterator
01850   , typename RandomAccessIteratorOut
01851   , typename _DifferenceTp
01852   , typename Comparator>
01853 RandomAccessIteratorOut
01854 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01855     , RandomAccessIteratorPairIterator seqs_end
01856     , RandomAccessIteratorOut target
01857     , _DifferenceTp length, Comparator comp
01858     , __gnu_parallel::sequential_tag)
01859 {
01860     typedef _DifferenceTp difference_type;
01861     _GLIBCXX_CALL(seqs_end - seqs_begin)
01862 
01863     // catch special case: no sequences
01864     if (seqs_begin == seqs_end)
01865       return target;
01866 
01867     // Execute multiway merge *sequentially*.
01868     return sequential_multiway_merge
01869       </* stable = */ false, /* sentinels = */ true>
01870         (seqs_begin, seqs_end,
01871          target, *(seqs_begin->second), length, comp);
01872 }
01873 
01874 // public interface
01875 template<
01876     typename RandomAccessIteratorPairIterator
01877   , typename RandomAccessIteratorOut
01878   , typename _DifferenceTp
01879   , typename Comparator>
01880 RandomAccessIteratorOut
01881 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01882     , RandomAccessIteratorPairIterator seqs_end
01883     , RandomAccessIteratorOut target
01884     , _DifferenceTp length, Comparator comp
01885     , __gnu_parallel::exact_tag tag)
01886 {
01887     typedef _DifferenceTp difference_type;
01888     _GLIBCXX_CALL(seqs_end - seqs_begin)
01889 
01890     // catch special case: no sequences
01891     if (seqs_begin == seqs_end)
01892       return target;
01893 
01894     // Execute merge; maybe parallel, depending on the number of merged
01895     // elements and the number of sequences and global thresholds in
01896     // Settings.
01897     if ((seqs_end - seqs_begin > 1) &&
01898           _GLIBCXX_PARALLEL_CONDITION(
01899           ((seqs_end - seqs_begin) >=
01900             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01901           && ((sequence_index_t)length >=
01902             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01903       return parallel_multiway_merge
01904         </* stable = */ false, /* sentinels = */ true>(
01905           seqs_begin, seqs_end,
01906           target,
01907           multiway_merge_exact_splitting</* stable = */ false,
01908             typename std::iterator_traits<RandomAccessIteratorPairIterator>
01909               ::value_type*, Comparator, _DifferenceTp>,
01910           static_cast<difference_type>(length), comp, tag.get_num_threads());
01911     else
01912       return sequential_multiway_merge
01913         </* stable = */ false, /* sentinels = */ true>(
01914           seqs_begin, seqs_end,
01915           target, *(seqs_begin->second), length, comp);
01916 }
01917 
01918 // public interface
01919 template<
01920     typename RandomAccessIteratorPairIterator
01921   , typename RandomAccessIteratorOut
01922   , typename _DifferenceTp
01923   , typename Comparator>
01924 RandomAccessIteratorOut
01925 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01926     , RandomAccessIteratorPairIterator seqs_end
01927     , RandomAccessIteratorOut target
01928     , _DifferenceTp length, Comparator comp
01929     , sampling_tag tag)
01930 {
01931     typedef _DifferenceTp difference_type;
01932     _GLIBCXX_CALL(seqs_end - seqs_begin)
01933 
01934     // catch special case: no sequences
01935     if (seqs_begin == seqs_end)
01936       return target;
01937 
01938     // Execute merge; maybe parallel, depending on the number of merged
01939     // elements and the number of sequences and global thresholds in
01940     // Settings.
01941     if ((seqs_end - seqs_begin > 1) &&
01942           _GLIBCXX_PARALLEL_CONDITION(
01943           ((seqs_end - seqs_begin) >=
01944             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
01945           && ((sequence_index_t)length >=
01946             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
01947       return parallel_multiway_merge
01948         </* stable = */ false, /* sentinels = */ true>
01949           (seqs_begin, seqs_end, target,
01950           multiway_merge_sampling_splitting</* stable = */ false,
01951             typename std::iterator_traits<RandomAccessIteratorPairIterator>
01952               ::value_type*, Comparator, _DifferenceTp>,
01953           static_cast<difference_type>(length), comp, tag.get_num_threads());
01954     else
01955       return sequential_multiway_merge
01956         </* stable = */false, /* sentinels = */ true>(
01957           seqs_begin, seqs_end,
01958           target, *(seqs_begin->second), length, comp);
01959 }
01960 
01961 // public interface
01962 template<
01963     typename RandomAccessIteratorPairIterator
01964   , typename RandomAccessIteratorOut
01965   , typename _DifferenceTp
01966   , typename Comparator>
01967 RandomAccessIteratorOut
01968 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01969     , RandomAccessIteratorPairIterator seqs_end
01970     , RandomAccessIteratorOut target
01971     , _DifferenceTp length, Comparator comp
01972     , parallel_tag tag = parallel_tag(0))
01973 {
01974   return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
01975                          exact_tag(tag.get_num_threads()));
01976 }
01977 
01978 // public interface
01979 template<
01980     typename RandomAccessIteratorPairIterator
01981   , typename RandomAccessIteratorOut
01982   , typename _DifferenceTp
01983   , typename Comparator>
01984 RandomAccessIteratorOut
01985 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
01986     , RandomAccessIteratorPairIterator seqs_end
01987     , RandomAccessIteratorOut target
01988     , _DifferenceTp length, Comparator comp
01989     , default_parallel_tag tag)
01990 {
01991   return multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
01992                          exact_tag(tag.get_num_threads()));
01993 }
01994 
01995 // stable_multiway_merge_sentinels
01996 // public interface
01997 template<
01998     typename RandomAccessIteratorPairIterator
01999   , typename RandomAccessIteratorOut
02000   , typename _DifferenceTp
02001   , typename Comparator>
02002 RandomAccessIteratorOut
02003 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02004     , RandomAccessIteratorPairIterator seqs_end
02005     , RandomAccessIteratorOut target
02006     , _DifferenceTp length, Comparator comp
02007     , __gnu_parallel::sequential_tag)
02008 {
02009     typedef _DifferenceTp difference_type;
02010     _GLIBCXX_CALL(seqs_end - seqs_begin)
02011 
02012     // catch special case: no sequences
02013     if (seqs_begin == seqs_end)
02014       return target;
02015 
02016     // Execute multiway merge *sequentially*.
02017     return sequential_multiway_merge
02018       </* stable = */ true, /* sentinels = */ true>
02019         (seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
02020 }
02021 
02022 // public interface
02023 template<
02024     typename RandomAccessIteratorPairIterator
02025   , typename RandomAccessIteratorOut
02026   , typename _DifferenceTp
02027   , typename Comparator>
02028 RandomAccessIteratorOut
02029 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02030     , RandomAccessIteratorPairIterator seqs_end
02031     , RandomAccessIteratorOut target
02032     , _DifferenceTp length, Comparator comp
02033     , __gnu_parallel::exact_tag tag)
02034 {
02035     typedef _DifferenceTp difference_type;
02036     _GLIBCXX_CALL(seqs_end - seqs_begin)
02037 
02038     // catch special case: no sequences
02039     if (seqs_begin == seqs_end)
02040       return target;
02041 
02042     // Execute merge; maybe parallel, depending on the number of merged
02043     // elements and the number of sequences and global thresholds in
02044     // Settings.
02045     if ((seqs_end - seqs_begin > 1) &&
02046           _GLIBCXX_PARALLEL_CONDITION(
02047           ((seqs_end - seqs_begin) >=
02048           __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
02049           && ((sequence_index_t)length >=
02050           __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
02051       return parallel_multiway_merge
02052         </* stable = */ true, /* sentinels = */ true>(
02053           seqs_begin, seqs_end,
02054           target,
02055           multiway_merge_exact_splitting</* stable = */ true,
02056             typename std::iterator_traits<RandomAccessIteratorPairIterator>
02057               ::value_type*, Comparator, _DifferenceTp>,
02058           static_cast<difference_type>(length), comp, tag.get_num_threads());
02059     else
02060       return sequential_multiway_merge
02061         </* stable = */ true, /* sentinels = */ true>(
02062           seqs_begin, seqs_end, target, *(seqs_begin->second), length, comp);
02063 }
02064 
02065 // public interface
02066 template<
02067     typename RandomAccessIteratorPairIterator
02068   , typename RandomAccessIteratorOut
02069   , typename _DifferenceTp
02070   , typename Comparator>
02071 RandomAccessIteratorOut
02072 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02073     , RandomAccessIteratorPairIterator seqs_end
02074     , RandomAccessIteratorOut target
02075     , _DifferenceTp length, Comparator comp
02076     , sampling_tag tag)
02077 {
02078     typedef _DifferenceTp difference_type;
02079     _GLIBCXX_CALL(seqs_end - seqs_begin)
02080 
02081     // catch special case: no sequences
02082     if (seqs_begin == seqs_end)
02083       return target;
02084 
02085     // Execute merge; maybe parallel, depending on the number of merged
02086     // elements and the number of sequences and global thresholds in
02087     // Settings.
02088     if ((seqs_end - seqs_begin > 1) &&
02089           _GLIBCXX_PARALLEL_CONDITION(
02090           ((seqs_end - seqs_begin) >=
02091             __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
02092           && ((sequence_index_t)length >=
02093             __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
02094       return parallel_multiway_merge
02095         </* stable = */ true, /* sentinels = */ true>(
02096           seqs_begin, seqs_end,
02097           target,
02098           multiway_merge_sampling_splitting</* stable = */ true,
02099             typename std::iterator_traits<RandomAccessIteratorPairIterator>
02100               ::value_type*, Comparator, _DifferenceTp>,
02101           static_cast<difference_type>(length), comp, tag.get_num_threads());
02102     else
02103       return sequential_multiway_merge
02104         </* stable = */ true, /* sentinels = */ true>(
02105           seqs_begin, seqs_end,
02106           target, *(seqs_begin->second), length, comp);
02107 }
02108 
02109 // public interface
02110 template<
02111     typename RandomAccessIteratorPairIterator
02112   , typename RandomAccessIteratorOut
02113   , typename _DifferenceTp
02114   , typename Comparator>
02115 RandomAccessIteratorOut
02116 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02117     , RandomAccessIteratorPairIterator seqs_end
02118     , RandomAccessIteratorOut target
02119     , _DifferenceTp length, Comparator comp
02120     , parallel_tag tag = parallel_tag(0))
02121 {
02122   return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
02123                          exact_tag(tag.get_num_threads()));
02124 }
02125 
02126 // public interface
02127 template<
02128     typename RandomAccessIteratorPairIterator
02129   , typename RandomAccessIteratorOut
02130   , typename _DifferenceTp
02131   , typename Comparator>
02132 RandomAccessIteratorOut
02133 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
02134     , RandomAccessIteratorPairIterator seqs_end
02135     , RandomAccessIteratorOut target
02136     , _DifferenceTp length, Comparator comp
02137     , default_parallel_tag tag)
02138 {
02139   return stable_multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp,
02140                          exact_tag(tag.get_num_threads()));
02141 }
02142 
02143 }; // namespace __gnu_parallel
02144 
02145 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */

Generated on Wed Jul 22 12:12:54 2009 for libstdc++ by  doxygen 1.5.9