The C and C++ Include Header Files

/usr/include/c++/11/parallel/multiway_merge.h


$ cat -n /usr/include/c++/11/parallel/multiway_merge.h

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