3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
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 2, or (at your option) any later
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.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/multiway_merge.h
32 * @brief Implementation of sequential and parallel multiway merge.
34 * Explanations on the high-speed merging routines in the appendix of
37 * Fast priority queues for cached memory.
38 * ACM Journal of Experimental Algorithmics, 5, 2000.
40 * This file is a GNU parallel extension to the Standard C++ Library.
43 // Written by Johannes Singler and Manuel Holtgrewe.
45 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
46 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
50 #include <bits/stl_algo.h>
51 #include <parallel/features.h>
52 #include <parallel/parallel.h>
53 #include <parallel/losertree.h>
54 #if _GLIBCXX_ASSERTIONS
55 #include <parallel/checkers.h>
58 /** @brief Length of a sequence described by a pair of iterators. */
59 #define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first)
61 namespace __gnu_parallel
64 // Announce guarded and unguarded iterator.
66 template<typename RandomAccessIterator
, typename Comparator
>
67 class guarded_iterator
;
69 // Making the arguments const references seems to dangerous,
70 // the user-defined comparator might not be const.
71 template<typename RandomAccessIterator
, typename Comparator
>
73 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
74 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
76 template<typename RandomAccessIterator
, typename Comparator
>
78 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
79 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
81 /** @brief Iterator wrapper supporting an implicit supremum at the end
82 * of the sequence, dominating all comparisons.
84 * The implicit supremum comes with a performance cost.
86 * Deriving from RandomAccessIterator is not possible since
87 * RandomAccessIterator need not be a class.
89 template<typename RandomAccessIterator
, typename Comparator
>
90 class guarded_iterator
93 /** @brief Current iterator position. */
94 RandomAccessIterator current
;
96 /** @brief End iterator of the sequence. */
97 RandomAccessIterator end
;
99 /** @brief Comparator. */
103 /** @brief Constructor. Sets iterator to beginning of sequence.
104 * @param begin Begin iterator of sequence.
105 * @param end End iterator of sequence.
106 * @param comp Comparator provided for associated overloaded
107 * compare operators. */
108 guarded_iterator(RandomAccessIterator begin
,
109 RandomAccessIterator end
, Comparator
& comp
)
110 : current(begin
), end(end
), comp(comp
)
113 /** @brief Pre-increment operator.
115 guarded_iterator
<RandomAccessIterator
, Comparator
>&
122 /** @brief Dereference operator.
123 * @return Referenced element. */
124 typename
std::iterator_traits
<RandomAccessIterator
>::value_type
&
128 /** @brief Convert to wrapped iterator.
129 * @return Wrapped iterator. */
130 operator RandomAccessIterator()
134 operator< <RandomAccessIterator
, Comparator
>(
135 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
136 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
139 operator<= <RandomAccessIterator
, Comparator
>(
140 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
141 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
144 /** @brief Compare two elements referenced by guarded iterators.
145 * @param bi1 First iterator.
146 * @param bi2 Second iterator.
147 * @return @c True if less. */
148 template<typename RandomAccessIterator
, typename Comparator
>
150 operator<(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
151 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
153 if (bi1
.current
== bi1
.end
) //bi1 is sup
154 return bi2
.current
== bi2
.end
; //bi2 is not sup
155 if (bi2
.current
== bi2
.end
) //bi2 is sup
157 return (bi1
.comp
)(*bi1
, *bi2
); //normal compare
160 /** @brief Compare two elements referenced by guarded iterators.
161 * @param bi1 First iterator.
162 * @param bi2 Second iterator.
163 * @return @c True if less equal. */
164 template<typename RandomAccessIterator
, typename Comparator
>
166 operator<=(guarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
167 guarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
169 if (bi2
.current
== bi2
.end
) //bi1 is sup
170 return bi1
.current
!= bi1
.end
; //bi2 is not sup
171 if (bi1
.current
== bi1
.end
) //bi2 is sup
173 return !(bi1
.comp
)(*bi2
, *bi1
); //normal compare
176 template<typename RandomAccessIterator
, typename Comparator
>
177 class unguarded_iterator
;
179 template<typename RandomAccessIterator
, typename Comparator
>
181 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
182 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
184 template<typename RandomAccessIterator
, typename Comparator
>
186 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
187 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
189 template<typename RandomAccessIterator
, typename Comparator
>
190 class unguarded_iterator
193 /** @brief Current iterator position. */
194 RandomAccessIterator current
;
195 /** @brief Comparator. */
196 mutable Comparator
& comp
;
199 /** @brief Constructor. Sets iterator to beginning of sequence.
200 * @param begin Begin iterator of sequence.
201 * @param end Unused, only for compatibility.
202 * @param comp Unused, only for compatibility. */
203 unguarded_iterator(RandomAccessIterator begin
,
204 RandomAccessIterator end
, Comparator
& comp
)
205 : current(begin
), comp(comp
)
208 /** @brief Pre-increment operator.
210 unguarded_iterator
<RandomAccessIterator
, Comparator
>&
217 /** @brief Dereference operator.
218 * @return Referenced element. */
219 typename
std::iterator_traits
<RandomAccessIterator
>::value_type
&
223 /** @brief Convert to wrapped iterator.
224 * @return Wrapped iterator. */
225 operator RandomAccessIterator()
229 operator< <RandomAccessIterator
, Comparator
>(
230 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
231 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
234 operator<= <RandomAccessIterator
, Comparator
>(
235 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
236 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
);
239 /** @brief Compare two elements referenced by unguarded iterators.
240 * @param bi1 First iterator.
241 * @param bi2 Second iterator.
242 * @return @c True if less. */
243 template<typename RandomAccessIterator
, typename Comparator
>
245 operator<(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
246 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
249 return (bi1
.comp
)(*bi1
, *bi2
);
252 /** @brief Compare two elements referenced by unguarded iterators.
253 * @param bi1 First iterator.
254 * @param bi2 Second iterator.
255 * @return @c True if less equal. */
256 template<typename RandomAccessIterator
, typename Comparator
>
258 operator<=(unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi1
,
259 unguarded_iterator
<RandomAccessIterator
, Comparator
>& bi2
)
262 return !(bi1
.comp
)(*bi2
, *bi1
);
265 /** @brief Highly efficient 3-way merging procedure.
267 * Merging is done with the algorithm implementation described by Peter
268 * Sanders. Basically, the idea is to minimize the number of necessary
269 * comparison after merging out an element. The implementation trick
270 * that makes this fast is that the order of the sequences is stored
271 * in the instruction pointer (translated into labels in C++).
273 * This works well for merging up to 4 sequences.
275 * Note that making the merging stable does <em>not</em> come at a
278 * Whether the merging is done guarded or unguarded is selected by the
279 * used iterator class.
281 * @param seqs_begin Begin iterator of iterator pair input sequence.
282 * @param seqs_end End iterator of iterator pair input sequence.
283 * @param target Begin iterator out output sequence.
284 * @param comp Comparator.
285 * @param length Maximum length to merge.
287 * @return End iterator of output sequence.
289 template<template<typename RAI
, typename C
> class iterator
,
290 typename RandomAccessIteratorIterator
,
291 typename RandomAccessIterator3
,
292 typename _DifferenceTp
,
294 RandomAccessIterator3
295 multiway_merge_3_variant(
296 RandomAccessIteratorIterator seqs_begin
,
297 RandomAccessIteratorIterator seqs_end
,
298 RandomAccessIterator3 target
,
299 Comparator comp
, _DifferenceTp length
)
301 _GLIBCXX_CALL(length
);
303 typedef _DifferenceTp difference_type
;
305 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
306 ::value_type::first_type
307 RandomAccessIterator1
;
308 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
314 #if _GLIBCXX_ASSERTIONS
315 _DifferenceTp orig_length
= length
;
318 iterator
<RandomAccessIterator1
, Comparator
>
319 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
320 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
321 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
);
345 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \
347 *target = *seq ## a; \
351 if (length == 0) goto finish; \
352 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
353 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
354 goto s ## b ## c ## a;
356 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
357 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
358 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
359 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
360 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
361 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
363 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
368 #if _GLIBCXX_ASSERTIONS
369 _GLIBCXX_PARALLEL_ASSERT(
370 ((RandomAccessIterator1
)seq0
- seqs_begin
[0].first
) +
371 ((RandomAccessIterator1
)seq1
- seqs_begin
[1].first
) +
372 ((RandomAccessIterator1
)seq2
- seqs_begin
[2].first
)
376 seqs_begin
[0].first
= seq0
;
377 seqs_begin
[1].first
= seq1
;
378 seqs_begin
[2].first
= seq2
;
384 * @brief Highly efficient 4-way merging procedure.
386 * Merging is done with the algorithm implementation described by Peter
387 * Sanders. Basically, the idea is to minimize the number of necessary
388 * comparison after merging out an element. The implementation trick
389 * that makes this fast is that the order of the sequences is stored
390 * in the instruction pointer (translated into goto labels in C++).
392 * This works well for merging up to 4 sequences.
394 * Note that making the merging stable does <em>not</em> come at a
397 * Whether the merging is done guarded or unguarded is selected by the
398 * used iterator class.
400 * @param seqs_begin Begin iterator of iterator pair input sequence.
401 * @param seqs_end End iterator of iterator pair input sequence.
402 * @param target Begin iterator out output sequence.
403 * @param comp Comparator.
404 * @param length Maximum length to merge.
406 * @return End iterator of output sequence.
408 template<template<typename RAI
, typename C
> class iterator
,
409 typename RandomAccessIteratorIterator
,
410 typename RandomAccessIterator3
,
411 typename _DifferenceTp
,
413 RandomAccessIterator3
414 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin
,
415 RandomAccessIteratorIterator seqs_end
,
416 RandomAccessIterator3 target
,
417 Comparator comp
, _DifferenceTp length
)
419 _GLIBCXX_CALL(length
);
420 typedef _DifferenceTp difference_type
;
422 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
423 ::value_type::first_type
424 RandomAccessIterator1
;
425 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
428 iterator
<RandomAccessIterator1
, Comparator
>
429 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
430 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
431 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
),
432 seq3(seqs_begin
[3].first
, seqs_begin
[3].second
, comp
);
434 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \
435 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
436 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
437 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
438 goto s ## a ## b ## c ## d; }
443 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
446 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
448 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
455 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
457 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
460 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
463 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \
464 s ## a ## b ## c ## d: \
465 if (length == 0) goto finish; \
466 *target = *seq ## a; \
470 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
471 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
472 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
473 goto s ## b ## c ## d ## a;
475 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
476 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
477 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
478 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
479 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
480 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
481 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
482 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
483 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
484 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
485 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
486 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
487 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
488 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
489 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
490 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
491 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
492 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
493 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
494 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
495 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
496 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
497 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
498 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
500 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
501 #undef _GLIBCXX_PARALLEL_DECISION
506 seqs_begin
[0].first
= seq0
;
507 seqs_begin
[1].first
= seq1
;
508 seqs_begin
[2].first
= seq2
;
509 seqs_begin
[3].first
= seq3
;
514 /** @brief Multi-way merging procedure for a high branching factor,
517 * This merging variant uses a LoserTree class as selected by <tt>LT</tt>.
519 * Stability is selected through the used LoserTree class <tt>LT</tt>.
521 * @param seqs_begin Begin iterator of iterator pair input sequence.
522 * @param seqs_end End iterator of iterator pair input sequence.
523 * @param target Begin iterator out output sequence.
524 * @param comp Comparator.
525 * @param length Maximum length to merge.
527 * @return End iterator of output sequence.
529 template<typename LT
,
530 typename RandomAccessIteratorIterator
,
531 typename RandomAccessIterator3
,
532 typename _DifferenceTp
,
534 RandomAccessIterator3
535 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin
,
536 RandomAccessIteratorIterator seqs_end
,
537 RandomAccessIterator3 target
,
539 _DifferenceTp length
)
541 _GLIBCXX_CALL(length
)
543 typedef _DifferenceTp difference_type
;
544 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
545 ::value_type::first_type
546 RandomAccessIterator1
;
547 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
550 int k
= static_cast<int>(seqs_end
- seqs_begin
);
554 difference_type total_length
= 0;
556 // Default value for potentially non-default-constructible types.
557 value_type
* arbitrary_element
= NULL
;
559 for (int t
= 0; t
< k
; ++t
)
561 if(arbitrary_element
== NULL
562 && _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]) > 0)
563 arbitrary_element
= &(*seqs_begin
[t
].first
);
564 total_length
+= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]);
567 if(total_length
== 0)
570 for (int t
= 0; t
< k
; ++t
)
572 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
573 lt
.insert_start(*arbitrary_element
, t
, true);
575 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
580 const difference_type
const_total_length(std::min(total_length
, length
));
584 for (difference_type i
= 0; i
< const_total_length
; ++i
)
587 source
= lt
.get_min_source();
589 *(target
++) = *(seqs_begin
[source
].first
++);
592 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
593 lt
.delete_min_insert(*arbitrary_element
, true);
595 // Replace from same source.
596 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
602 /** @brief Multi-way merging procedure for a high branching factor,
605 * Merging is done using the LoserTree class <tt>LT</tt>.
607 * Stability is selected by the used LoserTrees.
609 * @pre No input will run out of elements during the merge.
611 * @param seqs_begin Begin iterator of iterator pair input sequence.
612 * @param seqs_end End iterator of iterator pair input sequence.
613 * @param target Begin iterator out output sequence.
614 * @param comp Comparator.
615 * @param length Maximum length to merge.
617 * @return End iterator of output sequence.
619 template<typename LT
,
620 typename RandomAccessIteratorIterator
,
621 typename RandomAccessIterator3
,
622 typename _DifferenceTp
, typename Comparator
>
623 RandomAccessIterator3
624 multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin
,
625 RandomAccessIteratorIterator seqs_end
,
626 RandomAccessIterator3 target
,
627 int min_seq
, Comparator comp
,
628 _DifferenceTp length
)
630 _GLIBCXX_CALL(length
)
631 typedef _DifferenceTp difference_type
;
633 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
634 ::value_type::first_type
635 RandomAccessIterator1
;
636 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
639 int k
= seqs_end
- seqs_begin
;
641 // Determine the sentinel. The sentinel is largest/last element of the
642 // sequences with the smallest largest/last element.
643 value_type sentinel
= *(seqs_begin
[min_seq
].second
- 1);
645 LT
lt(k
, sentinel
, comp
);
647 difference_type total_length
= 0;
649 for (int t
= 0; t
< k
; ++t
)
651 #if _GLIBCXX_ASSERTIONS
652 _GLIBCXX_PARALLEL_ASSERT(seqs_begin
[t
].first
!= seqs_begin
[t
].second
);
654 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
656 total_length
+= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]);
661 // Do not go past end.
662 length
= std::min(total_length
, length
);
666 #if _GLIBCXX_ASSERTIONS
667 difference_type i
= 0;
670 RandomAccessIterator3 target_end
= target
+ length
;
671 while (target
< target_end
)
674 source
= lt
.get_min_source();
676 #if _GLIBCXX_ASSERTIONS
677 _GLIBCXX_PARALLEL_ASSERT(0 <= source
&& source
< k
);
678 _GLIBCXX_PARALLEL_ASSERT(i
== 0
679 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
683 *(target
++) = *(seqs_begin
[source
].first
++);
685 #if _GLIBCXX_ASSERTIONS
686 _GLIBCXX_PARALLEL_ASSERT(
687 (seqs_begin
[source
].first
!= seqs_begin
[source
].second
)
688 || (i
>= length
- 1));
691 // Replace from same source.
692 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
699 /** @brief Multi-way merging procedure for a high branching factor,
700 * requiring sentinels to exist.
701 * @param stable The value must the same as for the used LoserTrees.
702 * @param UnguardedLoserTree Loser Tree variant to use for the unguarded
704 * @param GuardedLoserTree Loser Tree variant to use for the guarded
707 * @param seqs_begin Begin iterator of iterator pair input sequence.
708 * @param seqs_end End iterator of iterator pair input sequence.
709 * @param target Begin iterator out output sequence.
710 * @param comp Comparator.
711 * @param length Maximum length to merge.
713 * @return End iterator of output sequence.
716 typename UnguardedLoserTree
,
717 typename RandomAccessIteratorIterator
,
718 typename RandomAccessIterator3
,
719 typename _DifferenceTp
,
721 RandomAccessIterator3
722 multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin
,
723 RandomAccessIteratorIterator seqs_end
,
724 RandomAccessIterator3 target
,
726 _DifferenceTp length
)
728 _GLIBCXX_CALL(length
)
730 typedef _DifferenceTp difference_type
;
731 typedef std::iterator_traits
<RandomAccessIteratorIterator
> traits_type
;
732 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
733 ::value_type::first_type
734 RandomAccessIterator1
;
735 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
738 RandomAccessIterator3 target_end
;
740 difference_type total_length
= 0;
741 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
743 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*s
);
745 // Move the sequends end behind the sentinel spots. This has the
746 // effect that the sentinel appears to be within the sequence. Then,
747 // we can use the unguarded variant if we merge out as many
748 // non-sentinel elements as we have.
752 difference_type unguarded_length
=
753 std::min(length
, total_length
);
754 target_end
= multiway_merge_loser_tree_unguarded
756 (seqs_begin
, seqs_end
, target
, 0, comp
, unguarded_length
);
758 #if _GLIBCXX_ASSERTIONS
759 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
760 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
763 // Restore the sequence ends so the sentinels are not contained in the
764 // sequence any more (see comment in loop above).
765 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
772 * @brief Traits for determining whether the loser tree should
773 * use pointers or copies.
775 * The field "use_pointer" is used to determine whether to use pointers in
776 * the loser trees or whether to copy the values into the loser tree.
778 * The default behavior is to use pointers if the data type is 4 times as
779 * big as the pointer to it.
781 * Specialize for your data type to customize the behavior.
786 * struct loser_tree_traits<int>
787 * { static const bool use_pointer = false; };
790 * struct loser_tree_traits<heavyweight_type>
791 * { static const bool use_pointer = true; };
793 * @param T type to give the loser tree traits for.
795 template <typename T
>
796 struct loser_tree_traits
799 * @brief True iff to use pointers instead of values in loser trees.
801 * The default behavior is to use pointers if the data type is four
802 * times as big as the pointer to it.
804 static const bool use_pointer
= (sizeof(T
) > 4 * sizeof(T
*));
808 * @brief Switch for 3-way merging with sentinels turned off.
810 * Note that 3-way merging is always stable!
813 bool sentinels
/*default == false*/,
814 typename RandomAccessIteratorIterator
,
815 typename RandomAccessIterator3
,
816 typename _DifferenceTp
,
818 struct multiway_merge_3_variant_sentinel_switch
820 RandomAccessIterator3
operator()(
821 RandomAccessIteratorIterator seqs_begin
,
822 RandomAccessIteratorIterator seqs_end
,
823 RandomAccessIterator3 target
,
824 Comparator comp
, _DifferenceTp length
)
826 return multiway_merge_3_variant
<guarded_iterator
>(
827 seqs_begin
, seqs_end
, target
, comp
, length
);
832 * @brief Switch for 3-way merging with sentinels turned on.
834 * Note that 3-way merging is always stable!
837 typename RandomAccessIteratorIterator
,
838 typename RandomAccessIterator3
,
839 typename _DifferenceTp
,
841 struct multiway_merge_3_variant_sentinel_switch
842 <true, RandomAccessIteratorIterator
, RandomAccessIterator3
,
843 _DifferenceTp
, Comparator
>
845 RandomAccessIterator3
operator()(
846 RandomAccessIteratorIterator seqs_begin
,
847 RandomAccessIteratorIterator seqs_end
,
848 RandomAccessIterator3 target
,
849 Comparator comp
, _DifferenceTp length
)
851 return multiway_merge_3_variant
<unguarded_iterator
>(
852 seqs_begin
, seqs_end
, target
, comp
, length
);
857 * @brief Switch for 4-way merging with sentinels turned off.
859 * Note that 4-way merging is always stable!
862 bool sentinels
/*default == false*/,
863 typename RandomAccessIteratorIterator
,
864 typename RandomAccessIterator3
,
865 typename _DifferenceTp
,
867 struct multiway_merge_4_variant_sentinel_switch
869 RandomAccessIterator3
operator()(
870 RandomAccessIteratorIterator seqs_begin
,
871 RandomAccessIteratorIterator seqs_end
,
872 RandomAccessIterator3 target
,
873 Comparator comp
, _DifferenceTp length
)
875 return multiway_merge_4_variant
<guarded_iterator
>(
876 seqs_begin
, seqs_end
, target
, comp
, length
);
881 * @brief Switch for 4-way merging with sentinels turned on.
883 * Note that 4-way merging is always stable!
886 typename RandomAccessIteratorIterator
,
887 typename RandomAccessIterator3
,
888 typename _DifferenceTp
,
890 struct multiway_merge_4_variant_sentinel_switch
891 <true, RandomAccessIteratorIterator
, RandomAccessIterator3
,
892 _DifferenceTp
, Comparator
>
894 RandomAccessIterator3
operator()(
895 RandomAccessIteratorIterator seqs_begin
,
896 RandomAccessIteratorIterator seqs_end
,
897 RandomAccessIterator3 target
,
898 Comparator comp
, _DifferenceTp length
)
900 return multiway_merge_4_variant
<unguarded_iterator
>(
901 seqs_begin
, seqs_end
, target
, comp
, length
);
906 * @brief Switch for k-way merging with sentinels turned on.
911 typename RandomAccessIteratorIterator
,
912 typename RandomAccessIterator3
,
913 typename _DifferenceTp
,
915 struct multiway_merge_k_variant_sentinel_switch
917 RandomAccessIterator3
operator()(
918 RandomAccessIteratorIterator seqs_begin
,
919 RandomAccessIteratorIterator seqs_end
,
920 RandomAccessIterator3 target
,
921 Comparator comp
, _DifferenceTp length
)
923 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
924 ::value_type::first_type
925 RandomAccessIterator1
;
926 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
929 return multiway_merge_loser_tree_sentinel
<
930 typename
__gnu_cxx::__conditional_type
<
931 loser_tree_traits
<value_type
>::use_pointer
932 , LoserTreePointerUnguarded
<stable
, value_type
, Comparator
>
933 , LoserTreeUnguarded
<stable
, value_type
, Comparator
>
934 >::__type
>(seqs_begin
, seqs_end
, target
, comp
, length
);
939 * @brief Switch for k-way merging with sentinels turned off.
943 typename RandomAccessIteratorIterator
,
944 typename RandomAccessIterator3
,
945 typename _DifferenceTp
,
947 struct multiway_merge_k_variant_sentinel_switch
948 <false, stable
, RandomAccessIteratorIterator
, RandomAccessIterator3
,
949 _DifferenceTp
, Comparator
>
951 RandomAccessIterator3
operator()(
952 RandomAccessIteratorIterator seqs_begin
,
953 RandomAccessIteratorIterator seqs_end
,
954 RandomAccessIterator3 target
,
955 Comparator comp
, _DifferenceTp length
)
957 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
958 ::value_type::first_type
959 RandomAccessIterator1
;
960 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
963 return multiway_merge_loser_tree
<
964 typename
__gnu_cxx::__conditional_type
<
965 loser_tree_traits
<value_type
>::use_pointer
966 , LoserTreePointer
<stable
, value_type
, Comparator
>
967 , LoserTree
<stable
, value_type
, Comparator
>
968 >::__type
>(seqs_begin
, seqs_end
, target
, comp
, length
);
972 /** @brief Sequential multi-way merging switch.
974 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
976 * @param seqs_begin Begin iterator of iterator pair input sequence.
977 * @param seqs_end End iterator of iterator pair input sequence.
978 * @param target Begin iterator out output sequence.
979 * @param comp Comparator.
980 * @param length Maximum length to merge.
981 * @param stable Stable merging incurs a performance penalty.
982 * @param sentinel The sequences have a sentinel element.
983 * @return End iterator of output sequence. */
987 typename RandomAccessIteratorIterator
,
988 typename RandomAccessIterator3
,
989 typename _DifferenceTp
,
991 RandomAccessIterator3
992 sequential_multiway_merge(RandomAccessIteratorIterator seqs_begin
,
993 RandomAccessIteratorIterator seqs_end
,
994 RandomAccessIterator3 target
,
995 Comparator comp
, _DifferenceTp length
)
997 _GLIBCXX_CALL(length
)
999 typedef _DifferenceTp difference_type
;
1000 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1001 ::value_type::first_type
1002 RandomAccessIterator1
;
1003 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1006 #if _GLIBCXX_ASSERTIONS
1007 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1009 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s
).first
, (*s
).second
, comp
));
1013 RandomAccessIterator3 return_target
= target
;
1014 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1021 return_target
= std::copy(seqs_begin
[0].first
,
1022 seqs_begin
[0].first
+ length
,
1024 seqs_begin
[0].first
+= length
;
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
);
1034 return_target
= multiway_merge_3_variant_sentinel_switch
<
1036 , RandomAccessIteratorIterator
1037 , RandomAccessIterator3
1039 , Comparator
>()(seqs_begin
, seqs_end
, target
, comp
, length
);
1042 return_target
= multiway_merge_4_variant_sentinel_switch
<
1044 , RandomAccessIteratorIterator
1045 , RandomAccessIterator3
1047 , Comparator
>()(seqs_begin
, seqs_end
, target
, comp
, length
);
1050 return_target
= multiway_merge_k_variant_sentinel_switch
<
1053 , RandomAccessIteratorIterator
1054 , RandomAccessIterator3
1056 , Comparator
>()(seqs_begin
, seqs_end
, target
, comp
, length
);
1059 #if _GLIBCXX_ASSERTIONS
1060 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1063 return return_target
;
1067 * @brief Stable sorting functor.
1069 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
1071 template<bool stable
, class RandomAccessIterator
, class StrictWeakOrdering
>
1072 struct sampling_sorter
1074 void operator()(RandomAccessIterator first
, RandomAccessIterator last
,
1075 StrictWeakOrdering comp
)
1076 { __gnu_sequential::stable_sort(first
, last
, comp
); }
1080 * @brief Non-stable sorting functor.
1082 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
1084 template<class RandomAccessIterator
, class StrictWeakOrdering
>
1085 struct sampling_sorter
<false, RandomAccessIterator
, StrictWeakOrdering
>
1087 void operator()(RandomAccessIterator first
, RandomAccessIterator last
,
1088 StrictWeakOrdering comp
)
1089 { __gnu_sequential::sort(first
, last
, comp
); }
1093 * @brief Sampling based splitting for parallel multiway-merge routine.
1097 , typename RandomAccessIteratorIterator
1098 , typename Comparator
1099 , typename difference_type
>
1100 void multiway_merge_sampling_splitting(
1101 RandomAccessIteratorIterator seqs_begin
,
1102 RandomAccessIteratorIterator seqs_end
,
1103 Comparator comp
, difference_type length
,
1104 difference_type total_length
,
1105 std::vector
<std::pair
<difference_type
, difference_type
> > *pieces
)
1107 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1108 ::value_type::first_type
1109 RandomAccessIterator1
;
1110 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1114 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1116 int num_threads
= omp_get_num_threads();
1118 difference_type num_samples
=
1119 __gnu_parallel::_Settings::get().merge_oversampling
* num_threads
;
1121 value_type
* samples
= static_cast<value_type
*>(
1122 ::operator new(sizeof(value_type
) * k
* num_samples
));
1124 for (int s
= 0; s
< k
; ++s
)
1125 for (difference_type i
= 0; i
< num_samples
; ++i
)
1127 difference_type sample_index
=
1128 static_cast<difference_type
>(
1129 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[s
]) * (double(i
+ 1) /
1130 (num_samples
+ 1)) * (double(length
)
1132 new(&(samples
[s
* num_samples
+ i
])) value_type(
1133 seqs_begin
[s
].first
[sample_index
]);
1136 // Sort stable or non-stable, depending on value of template parameter
1138 sampling_sorter
<stable
, value_type
*, Comparator
>()(
1139 samples
, samples
+ (num_samples
* k
), comp
);
1141 for (int slab
= 0; slab
< num_threads
; ++slab
)
1142 // For each slab / processor.
1143 for (int seq
= 0; seq
< k
; ++seq
)
1145 // For each sequence.
1147 pieces
[slab
][seq
].first
=
1149 seqs_begin
[seq
].first
,
1150 seqs_begin
[seq
].second
,
1151 samples
[num_samples
* k
* slab
/ num_threads
],
1153 - seqs_begin
[seq
].first
;
1156 // Absolute beginning.
1157 pieces
[slab
][seq
].first
= 0;
1159 if ((slab
+ 1) < num_threads
)
1160 pieces
[slab
][seq
].second
=
1162 seqs_begin
[seq
].first
,
1163 seqs_begin
[seq
].second
,
1164 samples
[num_samples
* k
* (slab
+ 1) /
1166 - seqs_begin
[seq
].first
;
1168 pieces
[slab
][seq
].second
= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1170 ::operator delete(samples
);
1174 * @brief Exact splitting for parallel multiway-merge routine.
1178 , typename RandomAccessIteratorIterator
1179 , typename Comparator
1180 , typename difference_type
>
1181 void multiway_merge_exact_splitting(
1182 RandomAccessIteratorIterator seqs_begin
,
1183 RandomAccessIteratorIterator seqs_end
,
1185 difference_type length
,
1186 difference_type total_length
,
1187 std::vector
<std::pair
<difference_type
, difference_type
> > *pieces
)
1189 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1190 ::value_type::first_type
1191 RandomAccessIterator1
;
1193 const bool tight
= (total_length
== length
);
1196 const int k
= static_cast<int>(seqs_end
- seqs_begin
);
1198 const int num_threads
= omp_get_num_threads();
1200 // (Settings::multiway_merge_splitting == __gnu_parallel::_Settings::EXACT).
1201 std::vector
<RandomAccessIterator1
>* offsets
=
1202 new std::vector
<RandomAccessIterator1
>[num_threads
];
1204 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>
1207 copy(seqs_begin
, seqs_end
, se
.begin());
1209 difference_type
* borders
=
1210 new difference_type
[num_threads
+ 1];
1211 equally_split(length
, num_threads
, borders
);
1213 for (int s
= 0; s
< (num_threads
- 1); ++s
)
1215 offsets
[s
].resize(k
);
1217 se
.begin(), se
.end(), borders
[s
+ 1],
1218 offsets
[s
].begin(), comp
);
1220 // Last one also needed and available.
1223 offsets
[num_threads
- 1].resize(k
);
1224 multiseq_partition(se
.begin(), se
.end(),
1225 difference_type(length
),
1226 offsets
[num_threads
- 1].begin(), comp
);
1231 for (int slab
= 0; slab
< num_threads
; ++slab
)
1233 // For each slab / processor.
1234 for (int seq
= 0; seq
< k
; ++seq
)
1236 // For each sequence.
1239 // Absolute beginning.
1240 pieces
[slab
][seq
].first
= 0;
1243 pieces
[slab
][seq
].first
=
1244 pieces
[slab
- 1][seq
].second
;
1245 if (!tight
|| slab
< (num_threads
- 1))
1246 pieces
[slab
][seq
].second
=
1247 offsets
[slab
][seq
] - seqs_begin
[seq
].first
;
1250 // slab == num_threads - 1
1251 pieces
[slab
][seq
].second
=
1252 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1259 /** @brief Parallel multi-way merge routine.
1261 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1262 * and runtime settings.
1264 * Must not be called if the number of sequences is 1.
1266 * @param Splitter functor to split input (either exact or sampling based)
1268 * @param seqs_begin Begin iterator of iterator pair input sequence.
1269 * @param seqs_end End iterator of iterator pair input sequence.
1270 * @param target Begin iterator out output sequence.
1271 * @param comp Comparator.
1272 * @param length Maximum length to merge.
1273 * @param stable Stable merging incurs a performance penalty.
1274 * @param sentinel Ignored.
1275 * @return End iterator of output sequence.
1280 typename RandomAccessIteratorIterator
,
1281 typename RandomAccessIterator3
,
1282 typename _DifferenceTp
,
1286 RandomAccessIterator3
1287 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin
,
1288 RandomAccessIteratorIterator seqs_end
,
1289 RandomAccessIterator3 target
,
1292 _DifferenceTp length
)
1294 #if _GLIBCXX_ASSERTIONS
1295 _GLIBCXX_PARALLEL_ASSERT(seqs_end
- seqs_begin
> 1);
1298 _GLIBCXX_CALL(length
)
1300 typedef _DifferenceTp difference_type
;
1301 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1302 ::value_type::first_type
1303 RandomAccessIterator1
;
1305 std::iterator_traits
<RandomAccessIterator1
>::value_type value_type
;
1308 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1310 difference_type total_length
= 0;
1311 for (RandomAccessIteratorIterator raii
= seqs_begin
;
1312 raii
!= seqs_end
; ++raii
)
1313 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*raii
);
1315 _GLIBCXX_CALL(total_length
)
1317 if (total_length
== 0 || k
== 0)
1320 std::vector
<std::pair
<difference_type
, difference_type
> >* pieces
;
1322 thread_index_t num_threads
= static_cast<thread_index_t
>(
1323 std::min
<difference_type
>(get_max_threads(), total_length
));
1325 # pragma omp parallel num_threads (num_threads)
1329 num_threads
= omp_get_num_threads();
1330 // Thread t will have to merge pieces[iam][0..k - 1]
1331 pieces
= new std::vector
<
1332 std::pair
<difference_type
, difference_type
> >[num_threads
];
1333 for (int s
= 0; s
< num_threads
; ++s
)
1334 pieces
[s
].resize(k
);
1336 difference_type num_samples
=
1337 __gnu_parallel::_Settings::get().merge_oversampling
*
1340 splitter(seqs_begin
, seqs_end
, comp
, length
, total_length
,
1344 thread_index_t iam
= omp_get_thread_num();
1346 difference_type target_position
= 0;
1348 for (int c
= 0; c
< k
; ++c
)
1349 target_position
+= pieces
[iam
][c
].first
;
1353 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* chunks
1355 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>[k
];
1357 difference_type local_length
= 0;
1358 for (int s
= 0; s
< k
; ++s
)
1360 chunks
[s
] = std::make_pair(
1361 seqs_begin
[s
].first
+ pieces
[iam
][s
].first
,
1362 seqs_begin
[s
].first
+ pieces
[iam
][s
].second
);
1363 local_length
+= _GLIBCXX_PARALLEL_LENGTH(chunks
[s
]);
1366 sequential_multiway_merge
<stable
, sentinels
>(
1367 chunks
, chunks
+ k
, target
+ target_position
, comp
,
1368 std::min(local_length
, length
- target_position
));
1374 RandomAccessIterator1
1375 begin0
= seqs_begin
[0].first
+ pieces
[iam
][0].first
,
1376 begin1
= seqs_begin
[1].first
+ pieces
[iam
][1].first
;
1377 merge_advance(begin0
,
1378 seqs_begin
[0].first
+ pieces
[iam
][0].second
,
1380 seqs_begin
[1].first
+ pieces
[iam
][1].second
,
1381 target
+ target_position
,
1382 (pieces
[iam
][0].second
- pieces
[iam
][0].first
) +
1383 (pieces
[iam
][1].second
- pieces
[iam
][1].first
),
1388 #if _GLIBCXX_ASSERTIONS
1389 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1392 // Update ends of sequences.
1393 for (int s
= 0; s
< k
; ++s
)
1394 seqs_begin
[s
].first
+= pieces
[num_threads
- 1][s
].second
;
1398 return target
+ length
;
1402 * @brief Multiway Merge Frontend.
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.
1410 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1411 * that breaks ties by sequence number but is slower.
1413 * The first entries of the pairs (i.e. the begin iterators) will be moved
1416 * The output sequence has to provide enough space for all elements
1417 * that are written to it.
1419 * This function will merge the input sequences:
1422 * - parallel, depending on the input size and Settings
1423 * - using sampling for splitting
1424 * - not using sentinels
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;
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)) }
1439 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1442 * @see stable_multiway_merge
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.
1448 * @post [target, return value) contains merged elements from the
1450 * @post return value - target = min(length, number of elements in all
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
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 the number of elements to merge into target.
1466 * @return end iterator of output sequence
1469 typename RandomAccessIteratorPairIterator
1470 , typename RandomAccessIteratorOut
1471 , typename _DifferenceTp
1472 , typename Comparator
>
1473 RandomAccessIteratorOut
1474 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1475 , RandomAccessIteratorPairIterator seqs_end
1476 , RandomAccessIteratorOut target
1477 , Comparator comp
, _DifferenceTp length
)
1479 typedef _DifferenceTp difference_type
;
1480 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1482 // catch special case: no sequences
1483 if (seqs_begin
== seqs_end
)
1486 // Execute merge; maybe parallel, depending on the number of merged
1487 // elements and the number of sequences and global thresholds in
1489 RandomAccessIteratorOut target_end
;
1490 if ((seqs_end
- seqs_begin
> 1) &&
1491 _GLIBCXX_PARALLEL_CONDITION(
1492 ((seqs_end
- seqs_begin
) >=
1493 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1494 && ((sequence_index_t
)length
>=
1495 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1496 target_end
= parallel_multiway_merge
1497 </* stable = */ false, /* sentinels = */ false>
1498 (seqs_begin
, seqs_end
, target
, comp
,
1499 multiway_merge_sampling_splitting
</* stable = */ false,
1500 RandomAccessIteratorPairIterator
, Comparator
, _DifferenceTp
>,
1501 static_cast<difference_type
>(length
));
1503 target_end
= sequential_multiway_merge
1504 </* stable = */false, /* sentinels = */ false>(
1505 seqs_begin
, seqs_end
,
1506 target
, comp
, length
);
1512 typename RandomAccessIteratorPairIterator
1513 , typename RandomAccessIteratorOut
1514 , typename _DifferenceTp
1515 , typename Comparator
>
1516 RandomAccessIteratorOut
1517 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1518 , RandomAccessIteratorPairIterator seqs_end
1519 , RandomAccessIteratorOut target
1520 , Comparator comp
, _DifferenceTp length
1521 , __gnu_parallel::sequential_tag
)
1523 typedef _DifferenceTp difference_type
;
1524 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1526 // catch special case: no sequences
1527 if (seqs_begin
== seqs_end
)
1530 // Execute multiway merge *sequentially*.
1531 return sequential_multiway_merge
1532 </* stable = */ false, /* sentinels = */ false>
1533 (seqs_begin
, seqs_end
, target
, comp
, length
);
1537 typename RandomAccessIteratorPairIterator
1538 , typename RandomAccessIteratorOut
1539 , typename _DifferenceTp
1540 , typename Comparator
>
1541 RandomAccessIteratorOut
1542 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1543 , RandomAccessIteratorPairIterator seqs_end
1544 , RandomAccessIteratorOut target
1545 , Comparator comp
, _DifferenceTp length
1546 , __gnu_parallel::exact_tag
)
1548 typedef _DifferenceTp difference_type
;
1549 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1551 // catch special case: no sequences
1552 if (seqs_begin
== seqs_end
)
1555 // Execute merge; maybe parallel, depending on the number of merged
1556 // elements and the number of sequences and global thresholds in
1558 RandomAccessIteratorOut target_end
;
1559 if ((seqs_end
- seqs_begin
> 1) &&
1560 _GLIBCXX_PARALLEL_CONDITION(
1561 ((seqs_end
- seqs_begin
) >=
1562 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1563 && ((sequence_index_t
)length
>=
1564 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1565 target_end
= parallel_multiway_merge
1566 </* stable = */ false, /* sentinels = */ false>(
1567 seqs_begin
, seqs_end
,
1569 multiway_merge_exact_splitting
</* stable = */ false,
1570 RandomAccessIteratorPairIterator
, Comparator
, _DifferenceTp
>,
1571 static_cast<difference_type
>(length
));
1573 target_end
= sequential_multiway_merge
1574 </* stable = */ false, /* sentinels = */ false>(
1575 seqs_begin
, seqs_end
,
1576 target
, comp
, length
);
1582 typename RandomAccessIteratorPairIterator
1583 , typename RandomAccessIteratorOut
1584 , typename _DifferenceTp
1585 , typename Comparator
>
1586 RandomAccessIteratorOut
1587 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1588 , RandomAccessIteratorPairIterator seqs_end
1589 , RandomAccessIteratorOut target
1590 , Comparator comp
, _DifferenceTp length
)
1592 typedef _DifferenceTp difference_type
;
1593 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1595 // catch special case: no sequences
1596 if (seqs_begin
== seqs_end
)
1599 // Execute merge; maybe parallel, depending on the number of merged
1600 // elements and the number of sequences and global thresholds in
1602 RandomAccessIteratorOut target_end
;
1603 if ((seqs_end
- seqs_begin
> 1) &&
1604 _GLIBCXX_PARALLEL_CONDITION(
1605 ((seqs_end
- seqs_begin
) >=
1606 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1607 && ((sequence_index_t
)length
>=
1608 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1609 target_end
= parallel_multiway_merge
1610 </* stable = */ true, /* sentinels = */ false>(
1611 seqs_begin
, seqs_end
,
1613 multiway_merge_sampling_splitting
</* stable = */ true,
1614 RandomAccessIteratorPairIterator
, Comparator
, _DifferenceTp
>,
1615 static_cast<difference_type
>(length
));
1617 target_end
= sequential_multiway_merge
1618 </* stable = */ true, /* sentinels = */ false>(
1619 seqs_begin
, seqs_end
,
1620 target
, comp
, length
);
1626 typename RandomAccessIteratorPairIterator
1627 , typename RandomAccessIteratorOut
1628 , typename _DifferenceTp
1629 , typename Comparator
>
1630 RandomAccessIteratorOut
1631 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1632 , RandomAccessIteratorPairIterator seqs_end
1633 , RandomAccessIteratorOut target
1634 , Comparator comp
, _DifferenceTp length
1635 , __gnu_parallel::sequential_tag
)
1637 typedef _DifferenceTp difference_type
;
1638 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1640 // catch special case: no sequences
1641 if (seqs_begin
== seqs_end
)
1644 // Execute multiway merge *sequentially*.
1645 return sequential_multiway_merge
1646 </* stable = */ true, /* sentinels = */ false>
1647 (seqs_begin
, seqs_end
, target
, comp
, length
);
1651 typename RandomAccessIteratorPairIterator
1652 , typename RandomAccessIteratorOut
1653 , typename _DifferenceTp
1654 , typename Comparator
>
1655 RandomAccessIteratorOut
1656 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1657 , RandomAccessIteratorPairIterator seqs_end
1658 , RandomAccessIteratorOut target
1659 , Comparator comp
, _DifferenceTp length
1660 , __gnu_parallel::exact_tag
)
1662 typedef _DifferenceTp difference_type
;
1663 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1665 // catch special case: no sequences
1666 if (seqs_begin
== seqs_end
)
1669 // Execute merge; maybe parallel, depending on the number of merged
1670 // elements and the number of sequences and global thresholds in
1672 RandomAccessIteratorOut target_end
;
1673 if ((seqs_end
- seqs_begin
> 1) &&
1674 _GLIBCXX_PARALLEL_CONDITION(
1675 ((seqs_end
- seqs_begin
) >=
1676 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1677 && ((sequence_index_t
)length
>=
1678 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1679 target_end
= parallel_multiway_merge
1680 </* stable = */ true, /* sentinels = */ false>(
1681 seqs_begin
, seqs_end
,
1683 multiway_merge_exact_splitting
1684 </* stable = */ true, RandomAccessIteratorPairIterator
,
1685 Comparator
, _DifferenceTp
>,
1686 static_cast<difference_type
>(length
));
1688 target_end
= sequential_multiway_merge
</* stable = */ true,
1689 /* sentinels = */ false>(
1690 seqs_begin
, seqs_end
,
1691 target
, comp
, length
);
1697 * @brief Multiway Merge Frontend.
1699 * Merge the sequences specified by seqs_begin and seqs_end into
1700 * target. seqs_begin and seqs_end must point to a sequence of
1701 * pairs. These pairs must contain an iterator to the beginning
1702 * of a sequence in their first entry and an iterator the end of
1703 * the same sequence in their second entry.
1705 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1706 * that breaks ties by sequence number but is slower.
1708 * The first entries of the pairs (i.e. the begin iterators) will be moved
1711 * The output sequence has to provide enough space for all elements
1712 * that are written to it.
1714 * This function will merge the input sequences:
1717 * - parallel, depending on the input size and Settings
1718 * - using sampling for splitting
1721 * You have to take care that the element the end iterator points to is
1722 * readable and contains a value that is greater than any other non-sentinel
1723 * value in all sequences.
1728 * int sequences[10][11];
1729 * for (int i = 0; i < 10; ++i)
1730 * for (int j = 0; i < 11; ++j)
1731 * sequences[i][j] = j; // last one is sentinel!
1734 * std::vector<std::pair<int*> > seqs;
1735 * for (int i = 0; i < 10; ++i)
1736 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1738 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1741 * @pre All input sequences must be sorted.
1742 * @pre Target must provide enough space to merge out length elements or
1743 * the number of elements in all sequences, whichever is smaller.
1744 * @pre For each @c i, @c seqs_begin[i].second must be the end
1745 * marker of the sequence, but also reference the one more sentinel
1748 * @post [target, return value) contains merged elements from the
1750 * @post return value - target = min(length, number of elements in all
1753 * @see stable_multiway_merge_sentinels
1755 * @param RandomAccessIteratorPairIterator iterator over sequence
1756 * of pairs of iterators
1757 * @param RandomAccessIteratorOut iterator over target sequence
1758 * @param _DifferenceTp difference type for the sequence
1759 * @param Comparator strict weak ordering type to compare elements
1762 * @param seqs_begin begin of sequence sequence
1763 * @param seqs_end end of sequence sequence
1764 * @param target target sequence to merge to.
1765 * @param comp strict weak ordering to use for element comparison.
1766 * @param length the number of elements to merge into target.
1768 * @return end iterator of output sequence
1771 typename RandomAccessIteratorPairIterator
1772 , typename RandomAccessIteratorOut
1773 , typename _DifferenceTp
1774 , typename Comparator
>
1775 RandomAccessIteratorOut
1776 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1777 , RandomAccessIteratorPairIterator seqs_end
1778 , RandomAccessIteratorOut target
1779 , Comparator comp
, _DifferenceTp length
)
1781 typedef _DifferenceTp difference_type
;
1782 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1784 // catch special case: no sequences
1785 if (seqs_begin
== seqs_end
)
1788 // Execute merge; maybe parallel, depending on the number of merged
1789 // elements and the number of sequences and global thresholds in
1791 RandomAccessIteratorOut target_end
;
1792 if ((seqs_end
- seqs_begin
> 1) &&
1793 _GLIBCXX_PARALLEL_CONDITION(
1794 ((seqs_end
- seqs_begin
) >=
1795 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1796 && ((sequence_index_t
)length
>=
1797 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1798 target_end
= parallel_multiway_merge
1799 </* stable = */ false, /* sentinels = */ true>
1800 (seqs_begin
, seqs_end
, target
, comp
,
1801 multiway_merge_sampling_splitting
1802 </* stable = */ false, RandomAccessIteratorPairIterator
,
1803 Comparator
, _DifferenceTp
>,
1804 static_cast<difference_type
>(length
));
1806 target_end
= sequential_multiway_merge
1807 </* stable = */false, /* sentinels = */ true>(
1808 seqs_begin
, seqs_end
,
1809 target
, comp
, length
);
1815 typename RandomAccessIteratorPairIterator
1816 , typename RandomAccessIteratorOut
1817 , typename _DifferenceTp
1818 , typename Comparator
>
1819 RandomAccessIteratorOut
1820 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1821 , RandomAccessIteratorPairIterator seqs_end
1822 , RandomAccessIteratorOut target
1823 , Comparator comp
, _DifferenceTp length
1824 , __gnu_parallel::sequential_tag
)
1826 typedef _DifferenceTp difference_type
;
1827 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1829 // catch special case: no sequences
1830 if (seqs_begin
== seqs_end
)
1833 // Execute multiway merge *sequentially*.
1834 return sequential_multiway_merge
1835 </* stable = */ false, /* sentinels = */ true>
1836 (seqs_begin
, seqs_end
, target
, comp
, length
);
1840 typename RandomAccessIteratorPairIterator
1841 , typename RandomAccessIteratorOut
1842 , typename _DifferenceTp
1843 , typename Comparator
>
1844 RandomAccessIteratorOut
1845 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1846 , RandomAccessIteratorPairIterator seqs_end
1847 , RandomAccessIteratorOut target
1848 , Comparator comp
, _DifferenceTp length
1849 , __gnu_parallel::exact_tag
)
1851 typedef _DifferenceTp difference_type
;
1852 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1854 // catch special case: no sequences
1855 if (seqs_begin
== seqs_end
)
1858 // Execute merge; maybe parallel, depending on the number of merged
1859 // elements and the number of sequences and global thresholds in
1861 RandomAccessIteratorOut target_end
;
1862 if ((seqs_end
- seqs_begin
> 1) &&
1863 _GLIBCXX_PARALLEL_CONDITION(
1864 ((seqs_end
- seqs_begin
) >=
1865 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1866 && ((sequence_index_t
)length
>=
1867 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1868 target_end
= parallel_multiway_merge
1869 </* stable = */ false, /* sentinels = */ true>(
1870 seqs_begin
, seqs_end
,
1872 multiway_merge_exact_splitting
1873 </* stable = */ false, RandomAccessIteratorPairIterator
,
1874 Comparator
, _DifferenceTp
>,
1875 static_cast<difference_type
>(length
));
1877 target_end
= sequential_multiway_merge
1878 </* stable = */ false, /* sentinels = */ true>(
1879 seqs_begin
, seqs_end
,
1880 target
, comp
, length
);
1886 typename RandomAccessIteratorPairIterator
1887 , typename RandomAccessIteratorOut
1888 , typename _DifferenceTp
1889 , typename Comparator
>
1890 RandomAccessIteratorOut
1891 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1892 , RandomAccessIteratorPairIterator seqs_end
1893 , RandomAccessIteratorOut target
1894 , Comparator comp
, _DifferenceTp length
)
1896 typedef _DifferenceTp difference_type
;
1897 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1899 // catch special case: no sequences
1900 if (seqs_begin
== seqs_end
)
1903 // Execute merge; maybe parallel, depending on the number of merged
1904 // elements and the number of sequences and global thresholds in
1906 RandomAccessIteratorOut target_end
;
1907 if ((seqs_end
- seqs_begin
> 1) &&
1908 _GLIBCXX_PARALLEL_CONDITION(
1909 ((seqs_end
- seqs_begin
) >=
1910 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1911 && ((sequence_index_t
)length
>=
1912 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1913 target_end
= parallel_multiway_merge
1914 </* stable = */ true, /* sentinels = */ true>(
1915 seqs_begin
, seqs_end
,
1917 multiway_merge_sampling_splitting
1918 </* stable = */ true, RandomAccessIteratorPairIterator
,
1919 Comparator
, _DifferenceTp
>,
1920 static_cast<difference_type
>(length
));
1922 target_end
= sequential_multiway_merge
1923 </* stable = */ true, /* sentinels = */ true>(
1924 seqs_begin
, seqs_end
,
1925 target
, comp
, length
);
1931 typename RandomAccessIteratorPairIterator
1932 , typename RandomAccessIteratorOut
1933 , typename _DifferenceTp
1934 , typename Comparator
>
1935 RandomAccessIteratorOut
1936 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1937 , RandomAccessIteratorPairIterator seqs_end
1938 , RandomAccessIteratorOut target
1939 , Comparator comp
, _DifferenceTp length
1940 , __gnu_parallel::sequential_tag
)
1942 typedef _DifferenceTp difference_type
;
1943 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1945 // catch special case: no sequences
1946 if (seqs_begin
== seqs_end
)
1949 // Execute multiway merge *sequentially*.
1950 return sequential_multiway_merge
1951 </* stable = */ true, /* sentinels = */ true>
1952 (seqs_begin
, seqs_end
, target
, comp
, length
);
1956 typename RandomAccessIteratorPairIterator
1957 , typename RandomAccessIteratorOut
1958 , typename _DifferenceTp
1959 , typename Comparator
>
1960 RandomAccessIteratorOut
1961 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1962 , RandomAccessIteratorPairIterator seqs_end
1963 , RandomAccessIteratorOut target
1964 , Comparator comp
, _DifferenceTp length
1965 , __gnu_parallel::exact_tag
)
1967 typedef _DifferenceTp difference_type
;
1968 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1970 // catch special case: no sequences
1971 if (seqs_begin
== seqs_end
)
1974 // Execute merge; maybe parallel, depending on the number of merged
1975 // elements and the number of sequences and global thresholds in
1977 RandomAccessIteratorOut target_end
;
1978 if ((seqs_end
- seqs_begin
> 1) &&
1979 _GLIBCXX_PARALLEL_CONDITION(
1980 ((seqs_end
- seqs_begin
) >=
1981 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1982 && ((sequence_index_t
)length
>=
1983 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1984 target_end
= parallel_multiway_merge
1985 </* stable = */ true, /* sentinels = */ true>(
1986 seqs_begin
, seqs_end
,
1988 multiway_merge_exact_splitting
1989 </* stable = */ true, RandomAccessIteratorPairIterator
,
1990 Comparator
, _DifferenceTp
>,
1991 static_cast<difference_type
>(length
));
1993 target_end
= sequential_multiway_merge
1994 </* stable = */ true, /* sentinels = */ true>(
1995 seqs_begin
, seqs_end
,
1996 target
, comp
, length
);
2001 }; // namespace __gnu_parallel