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