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, less equal than the
286 * total number of elements available.
288 * @return End iterator of output sequence.
290 template<template<typename RAI
, typename C
> class iterator
,
291 typename RandomAccessIteratorIterator
,
292 typename RandomAccessIterator3
,
293 typename _DifferenceTp
,
295 RandomAccessIterator3
296 multiway_merge_3_variant(
297 RandomAccessIteratorIterator seqs_begin
,
298 RandomAccessIteratorIterator seqs_end
,
299 RandomAccessIterator3 target
,
300 Comparator comp
, _DifferenceTp length
)
302 _GLIBCXX_CALL(length
);
304 typedef _DifferenceTp difference_type
;
306 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
307 ::value_type::first_type
308 RandomAccessIterator1
;
309 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
315 #if _GLIBCXX_ASSERTIONS
316 _DifferenceTp orig_length
= length
;
319 iterator
<RandomAccessIterator1
, Comparator
>
320 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
321 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
322 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
);
346 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \
348 *target = *seq ## a; \
352 if (length == 0) goto finish; \
353 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
354 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
355 goto s ## b ## c ## a;
357 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
358 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
359 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
360 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
361 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
362 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
364 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
369 #if _GLIBCXX_ASSERTIONS
370 _GLIBCXX_PARALLEL_ASSERT(
371 ((RandomAccessIterator1
)seq0
- seqs_begin
[0].first
) +
372 ((RandomAccessIterator1
)seq1
- seqs_begin
[1].first
) +
373 ((RandomAccessIterator1
)seq2
- seqs_begin
[2].first
)
377 seqs_begin
[0].first
= seq0
;
378 seqs_begin
[1].first
= seq1
;
379 seqs_begin
[2].first
= seq2
;
385 * @brief Highly efficient 4-way merging procedure.
387 * Merging is done with the algorithm implementation described by Peter
388 * Sanders. Basically, the idea is to minimize the number of necessary
389 * comparison after merging out an element. The implementation trick
390 * that makes this fast is that the order of the sequences is stored
391 * in the instruction pointer (translated into goto labels in C++).
393 * This works well for merging up to 4 sequences.
395 * Note that making the merging stable does <em>not</em> come at a
398 * Whether the merging is done guarded or unguarded is selected by the
399 * used iterator class.
401 * @param seqs_begin Begin iterator of iterator pair input sequence.
402 * @param seqs_end End iterator of iterator pair input sequence.
403 * @param target Begin iterator out output sequence.
404 * @param comp Comparator.
405 * @param length Maximum length to merge, less equal than the
406 * total number of elements available.
408 * @return End iterator of output sequence.
410 template<template<typename RAI
, typename C
> class iterator
,
411 typename RandomAccessIteratorIterator
,
412 typename RandomAccessIterator3
,
413 typename _DifferenceTp
,
415 RandomAccessIterator3
416 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin
,
417 RandomAccessIteratorIterator seqs_end
,
418 RandomAccessIterator3 target
,
419 Comparator comp
, _DifferenceTp length
)
421 _GLIBCXX_CALL(length
);
422 typedef _DifferenceTp difference_type
;
424 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
425 ::value_type::first_type
426 RandomAccessIterator1
;
427 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
430 iterator
<RandomAccessIterator1
, Comparator
>
431 seq0(seqs_begin
[0].first
, seqs_begin
[0].second
, comp
),
432 seq1(seqs_begin
[1].first
, seqs_begin
[1].second
, comp
),
433 seq2(seqs_begin
[2].first
, seqs_begin
[2].second
, comp
),
434 seq3(seqs_begin
[3].first
, seqs_begin
[3].second
, comp
);
436 #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \
437 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
438 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
439 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
440 goto s ## a ## b ## c ## d; }
445 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
448 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
450 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
457 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
459 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
462 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
465 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \
466 s ## a ## b ## c ## d: \
467 if (length == 0) goto finish; \
468 *target = *seq ## a; \
472 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
473 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
474 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
475 goto s ## b ## c ## d ## a;
477 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
478 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
479 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
480 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
481 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
482 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
483 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
484 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
485 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
486 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
487 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
488 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
489 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
490 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
491 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
492 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
493 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
494 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
495 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
496 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
497 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
498 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
499 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
500 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
502 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
503 #undef _GLIBCXX_PARALLEL_DECISION
508 seqs_begin
[0].first
= seq0
;
509 seqs_begin
[1].first
= seq1
;
510 seqs_begin
[2].first
= seq2
;
511 seqs_begin
[3].first
= seq3
;
516 /** @brief Multi-way merging procedure for a high branching factor,
519 * This merging variant uses a LoserTree class as selected by <tt>LT</tt>.
521 * Stability is selected through the used LoserTree class <tt>LT</tt>.
523 * At least one non-empty sequence is required.
525 * @param seqs_begin Begin iterator of iterator pair input sequence.
526 * @param seqs_end End iterator of iterator pair input sequence.
527 * @param target Begin iterator out output sequence.
528 * @param comp Comparator.
529 * @param length Maximum length to merge, less equal than the
530 * total number of elements available.
532 * @return End iterator of output sequence.
534 template<typename LT
,
535 typename RandomAccessIteratorIterator
,
536 typename RandomAccessIterator3
,
537 typename _DifferenceTp
,
539 RandomAccessIterator3
540 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin
,
541 RandomAccessIteratorIterator seqs_end
,
542 RandomAccessIterator3 target
,
544 _DifferenceTp length
)
546 _GLIBCXX_CALL(length
)
548 typedef _DifferenceTp difference_type
;
549 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
550 ::value_type::first_type
551 RandomAccessIterator1
;
552 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
555 int k
= static_cast<int>(seqs_end
- seqs_begin
);
559 // Default value for potentially non-default-constructible types.
560 value_type
* arbitrary_element
= NULL
;
562 for (int t
= 0; t
< k
; ++t
)
564 if(arbitrary_element
== NULL
565 && _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[t
]) > 0)
566 arbitrary_element
= &(*seqs_begin
[t
].first
);
569 for (int t
= 0; t
< k
; ++t
)
571 if (seqs_begin
[t
].first
== seqs_begin
[t
].second
)
572 lt
.insert_start(*arbitrary_element
, t
, true);
574 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
581 for (difference_type i
= 0; i
< length
; ++i
)
584 source
= lt
.get_min_source();
586 *(target
++) = *(seqs_begin
[source
].first
++);
589 if (seqs_begin
[source
].first
== seqs_begin
[source
].second
)
590 lt
.delete_min_insert(*arbitrary_element
, true);
592 // Replace from same source.
593 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
599 /** @brief Multi-way merging procedure for a high branching factor,
602 * Merging is done using the LoserTree class <tt>LT</tt>.
604 * Stability is selected by the used LoserTrees.
606 * @pre No input will run out of elements during the merge.
608 * @param seqs_begin Begin iterator of iterator pair input sequence.
609 * @param seqs_end End iterator of iterator pair input sequence.
610 * @param target Begin iterator out output sequence.
611 * @param comp Comparator.
612 * @param length Maximum length to merge, less equal than the
613 * total number of elements available.
615 * @return End iterator of output sequence.
617 template<typename LT
,
618 typename RandomAccessIteratorIterator
,
619 typename RandomAccessIterator3
,
620 typename _DifferenceTp
, typename Comparator
>
621 RandomAccessIterator3
622 multiway_merge_loser_tree_unguarded(
623 RandomAccessIteratorIterator seqs_begin
,
624 RandomAccessIteratorIterator seqs_end
,
625 RandomAccessIterator3 target
,
626 const typename
std::iterator_traits
<typename
std::iterator_traits
<
627 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
630 _DifferenceTp length
)
632 _GLIBCXX_CALL(length
)
633 typedef _DifferenceTp difference_type
;
635 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
636 ::value_type::first_type
637 RandomAccessIterator1
;
638 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
641 int k
= seqs_end
- seqs_begin
;
643 LT
lt(k
, sentinel
, comp
);
645 for (int t
= 0; t
< k
; ++t
)
647 #if _GLIBCXX_ASSERTIONS
648 _GLIBCXX_PARALLEL_ASSERT(seqs_begin
[t
].first
!= seqs_begin
[t
].second
);
650 lt
.insert_start(*seqs_begin
[t
].first
, t
, false);
657 #if _GLIBCXX_ASSERTIONS
658 difference_type i
= 0;
661 RandomAccessIterator3 target_end
= target
+ length
;
662 while (target
< target_end
)
665 source
= lt
.get_min_source();
667 #if _GLIBCXX_ASSERTIONS
668 _GLIBCXX_PARALLEL_ASSERT(0 <= source
&& source
< k
);
669 _GLIBCXX_PARALLEL_ASSERT(i
== 0
670 || !comp(*(seqs_begin
[source
].first
), *(target
- 1)));
674 *(target
++) = *(seqs_begin
[source
].first
++);
676 #if _GLIBCXX_ASSERTIONS
679 // Replace from same source.
680 lt
.delete_min_insert(*seqs_begin
[source
].first
, false);
687 /** @brief Multi-way merging procedure for a high branching factor,
688 * requiring sentinels to exist.
690 * @param stable The value must the same as for the used LoserTrees.
691 * @param UnguardedLoserTree Loser Tree variant to use for the unguarded
693 * @param GuardedLoserTree Loser Tree variant to use for the guarded
696 * @param seqs_begin Begin iterator of iterator pair input sequence.
697 * @param seqs_end End iterator of iterator pair input sequence.
698 * @param target Begin iterator out output sequence.
699 * @param comp Comparator.
700 * @param length Maximum length to merge, less equal than the
701 * total number of elements available.
703 * @return End iterator of output sequence.
706 typename UnguardedLoserTree
,
707 typename RandomAccessIteratorIterator
,
708 typename RandomAccessIterator3
,
709 typename _DifferenceTp
,
711 RandomAccessIterator3
712 multiway_merge_loser_tree_sentinel(
713 RandomAccessIteratorIterator seqs_begin
,
714 RandomAccessIteratorIterator seqs_end
,
715 RandomAccessIterator3 target
,
716 const typename
std::iterator_traits
<typename
std::iterator_traits
<
717 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
720 _DifferenceTp length
)
722 _GLIBCXX_CALL(length
)
724 typedef _DifferenceTp difference_type
;
725 typedef std::iterator_traits
<RandomAccessIteratorIterator
> traits_type
;
726 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
727 ::value_type::first_type
728 RandomAccessIterator1
;
729 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
732 RandomAccessIterator3 target_end
;
734 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
735 // Move the sequends end behind the sentinel spots. This has the
736 // effect that the sentinel appears to be within the sequence. Then,
737 // we can use the unguarded variant if we merge out as many
738 // non-sentinel elements as we have.
741 target_end
= multiway_merge_loser_tree_unguarded
743 (seqs_begin
, seqs_end
, target
, sentinel
, comp
, length
);
745 #if _GLIBCXX_ASSERTIONS
746 _GLIBCXX_PARALLEL_ASSERT(target_end
== target
+ length
);
747 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target_end
, comp
));
750 // Restore the sequence ends so the sentinels are not contained in the
751 // sequence any more (see comment in loop above).
752 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
759 * @brief Traits for determining whether the loser tree should
760 * use pointers or copies.
762 * The field "use_pointer" is used to determine whether to use pointers in
763 * the loser trees or whether to copy the values into the loser tree.
765 * The default behavior is to use pointers if the data type is 4 times as
766 * big as the pointer to it.
768 * Specialize for your data type to customize the behavior.
773 * struct loser_tree_traits<int>
774 * { static const bool use_pointer = false; };
777 * struct loser_tree_traits<heavyweight_type>
778 * { static const bool use_pointer = true; };
780 * @param T type to give the loser tree traits for.
782 template <typename T
>
783 struct loser_tree_traits
786 * @brief True iff to use pointers instead of values in loser trees.
788 * The default behavior is to use pointers if the data type is four
789 * times as big as the pointer to it.
791 static const bool use_pointer
= (sizeof(T
) > 4 * sizeof(T
*));
795 * @brief Switch for 3-way merging with sentinels turned off.
797 * Note that 3-way merging is always stable!
800 bool sentinels
/*default == false*/,
801 typename RandomAccessIteratorIterator
,
802 typename RandomAccessIterator3
,
803 typename _DifferenceTp
,
805 struct multiway_merge_3_variant_sentinel_switch
807 RandomAccessIterator3
operator()(
808 RandomAccessIteratorIterator seqs_begin
,
809 RandomAccessIteratorIterator seqs_end
,
810 RandomAccessIterator3 target
,
811 Comparator comp
, _DifferenceTp length
)
813 return multiway_merge_3_variant
<guarded_iterator
>(
814 seqs_begin
, seqs_end
, target
, comp
, length
);
819 * @brief Switch for 3-way merging with sentinels turned on.
821 * Note that 3-way merging is always stable!
824 typename RandomAccessIteratorIterator
,
825 typename RandomAccessIterator3
,
826 typename _DifferenceTp
,
828 struct multiway_merge_3_variant_sentinel_switch
829 <true, RandomAccessIteratorIterator
, RandomAccessIterator3
,
830 _DifferenceTp
, Comparator
>
832 RandomAccessIterator3
operator()(
833 RandomAccessIteratorIterator seqs_begin
,
834 RandomAccessIteratorIterator seqs_end
,
835 RandomAccessIterator3 target
,
836 Comparator comp
, _DifferenceTp length
)
838 return multiway_merge_3_variant
<unguarded_iterator
>(
839 seqs_begin
, seqs_end
, target
, comp
, length
);
844 * @brief Switch for 4-way merging with sentinels turned off.
846 * Note that 4-way merging is always stable!
849 bool sentinels
/*default == false*/,
850 typename RandomAccessIteratorIterator
,
851 typename RandomAccessIterator3
,
852 typename _DifferenceTp
,
854 struct multiway_merge_4_variant_sentinel_switch
856 RandomAccessIterator3
operator()(
857 RandomAccessIteratorIterator seqs_begin
,
858 RandomAccessIteratorIterator seqs_end
,
859 RandomAccessIterator3 target
,
860 Comparator comp
, _DifferenceTp length
)
862 return multiway_merge_4_variant
<guarded_iterator
>(
863 seqs_begin
, seqs_end
, target
, comp
, length
);
868 * @brief Switch for 4-way merging with sentinels turned on.
870 * Note that 4-way merging is always stable!
873 typename RandomAccessIteratorIterator
,
874 typename RandomAccessIterator3
,
875 typename _DifferenceTp
,
877 struct multiway_merge_4_variant_sentinel_switch
878 <true, RandomAccessIteratorIterator
, RandomAccessIterator3
,
879 _DifferenceTp
, Comparator
>
881 RandomAccessIterator3
operator()(
882 RandomAccessIteratorIterator seqs_begin
,
883 RandomAccessIteratorIterator seqs_end
,
884 RandomAccessIterator3 target
,
885 Comparator comp
, _DifferenceTp length
)
887 return multiway_merge_4_variant
<unguarded_iterator
>(
888 seqs_begin
, seqs_end
, target
, comp
, length
);
893 * @brief Switch for k-way merging with sentinels turned on.
898 typename RandomAccessIteratorIterator
,
899 typename RandomAccessIterator3
,
900 typename _DifferenceTp
,
902 struct multiway_merge_k_variant_sentinel_switch
904 RandomAccessIterator3
operator()(
905 RandomAccessIteratorIterator seqs_begin
,
906 RandomAccessIteratorIterator seqs_end
,
907 RandomAccessIterator3 target
,
908 const typename
std::iterator_traits
<typename
std::iterator_traits
<
909 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
911 Comparator comp
, _DifferenceTp length
)
913 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
914 ::value_type::first_type
915 RandomAccessIterator1
;
916 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
919 return multiway_merge_loser_tree_sentinel
<
920 typename
__gnu_cxx::__conditional_type
<
921 loser_tree_traits
<value_type
>::use_pointer
922 , LoserTreePointerUnguarded
<stable
, value_type
, Comparator
>
923 , LoserTreeUnguarded
<stable
, value_type
, Comparator
>
924 >::__type
>(seqs_begin
, seqs_end
, target
, sentinel
, comp
, length
);
929 * @brief Switch for k-way merging with sentinels turned off.
933 typename RandomAccessIteratorIterator
,
934 typename RandomAccessIterator3
,
935 typename _DifferenceTp
,
937 struct multiway_merge_k_variant_sentinel_switch
938 <false, stable
, RandomAccessIteratorIterator
, RandomAccessIterator3
,
939 _DifferenceTp
, Comparator
>
941 RandomAccessIterator3
operator()(
942 RandomAccessIteratorIterator seqs_begin
,
943 RandomAccessIteratorIterator seqs_end
,
944 RandomAccessIterator3 target
,
945 const typename
std::iterator_traits
<typename
std::iterator_traits
<
946 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
948 Comparator comp
, _DifferenceTp length
)
950 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
951 ::value_type::first_type
952 RandomAccessIterator1
;
953 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
956 return multiway_merge_loser_tree
<
957 typename
__gnu_cxx::__conditional_type
<
958 loser_tree_traits
<value_type
>::use_pointer
959 , LoserTreePointer
<stable
, value_type
, Comparator
>
960 , LoserTree
<stable
, value_type
, Comparator
>
961 >::__type
>(seqs_begin
, seqs_end
, target
, comp
, length
);
965 /** @brief Sequential multi-way merging switch.
967 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
969 * @param seqs_begin Begin iterator of iterator pair input sequence.
970 * @param seqs_end End iterator of iterator pair input sequence.
971 * @param target Begin iterator out output sequence.
972 * @param comp Comparator.
973 * @param length Maximum length to merge, possibly larger than the
974 * number of elements available.
975 * @param stable Stable merging incurs a performance penalty.
976 * @param sentinel The sequences have a sentinel element.
977 * @return End iterator of output sequence. */
981 typename RandomAccessIteratorIterator
,
982 typename RandomAccessIterator3
,
983 typename _DifferenceTp
,
985 RandomAccessIterator3
986 sequential_multiway_merge(
987 RandomAccessIteratorIterator seqs_begin
,
988 RandomAccessIteratorIterator seqs_end
,
989 RandomAccessIterator3 target
,
990 const typename
std::iterator_traits
<typename
std::iterator_traits
<
991 RandomAccessIteratorIterator
>::value_type::first_type
>::value_type
&
993 Comparator comp
, _DifferenceTp length
)
995 _GLIBCXX_CALL(length
)
997 typedef _DifferenceTp difference_type
;
998 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
999 ::value_type::first_type
1000 RandomAccessIterator1
;
1001 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1004 #if _GLIBCXX_ASSERTIONS
1005 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1007 _GLIBCXX_PARALLEL_ASSERT(is_sorted((*s
).first
, (*s
).second
, comp
));
1011 _DifferenceTp total_length
= 0;
1012 for (RandomAccessIteratorIterator s
= seqs_begin
; s
!= seqs_end
; ++s
)
1013 total_length
+= _GLIBCXX_PARALLEL_LENGTH(*s
);
1015 length
= std::min
<_DifferenceTp
>(length
, total_length
);
1020 RandomAccessIterator3 return_target
= target
;
1021 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1028 return_target
= std::copy(seqs_begin
[0].first
,
1029 seqs_begin
[0].first
+ length
,
1031 seqs_begin
[0].first
+= length
;
1034 return_target
= merge_advance(seqs_begin
[0].first
,
1035 seqs_begin
[0].second
,
1036 seqs_begin
[1].first
,
1037 seqs_begin
[1].second
,
1038 target
, length
, comp
);
1041 return_target
= multiway_merge_3_variant_sentinel_switch
<
1043 , RandomAccessIteratorIterator
1044 , RandomAccessIterator3
1046 , Comparator
>()(seqs_begin
, seqs_end
, target
, comp
, length
);
1049 return_target
= multiway_merge_4_variant_sentinel_switch
<
1051 , RandomAccessIteratorIterator
1052 , RandomAccessIterator3
1054 , Comparator
>()(seqs_begin
, seqs_end
, target
, comp
, length
);
1057 return_target
= multiway_merge_k_variant_sentinel_switch
<
1060 , RandomAccessIteratorIterator
1061 , RandomAccessIterator3
1064 (seqs_begin
, seqs_end
, target
, sentinel
, comp
, length
);
1067 #if _GLIBCXX_ASSERTIONS
1068 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1071 return return_target
;
1075 * @brief Stable sorting functor.
1077 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
1079 template<bool stable
, class RandomAccessIterator
, class StrictWeakOrdering
>
1080 struct sampling_sorter
1082 void operator()(RandomAccessIterator first
, RandomAccessIterator last
,
1083 StrictWeakOrdering comp
)
1084 { __gnu_sequential::stable_sort(first
, last
, comp
); }
1088 * @brief Non-stable sorting functor.
1090 * Used to reduce code instantiation in multiway_merge_sampling_splitting.
1092 template<class RandomAccessIterator
, class StrictWeakOrdering
>
1093 struct sampling_sorter
<false, RandomAccessIterator
, StrictWeakOrdering
>
1095 void operator()(RandomAccessIterator first
, RandomAccessIterator last
,
1096 StrictWeakOrdering comp
)
1097 { __gnu_sequential::sort(first
, last
, comp
); }
1101 * @brief Sampling based splitting for parallel multiway-merge routine.
1105 , typename RandomAccessIteratorIterator
1106 , typename Comparator
1107 , typename difference_type
>
1108 void multiway_merge_sampling_splitting(
1109 RandomAccessIteratorIterator seqs_begin
,
1110 RandomAccessIteratorIterator seqs_end
,
1111 Comparator comp
, difference_type length
,
1112 difference_type total_length
,
1113 std::vector
<std::pair
<difference_type
, difference_type
> > *pieces
)
1115 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1116 ::value_type::first_type
1117 RandomAccessIterator1
;
1118 typedef typename
std::iterator_traits
<RandomAccessIterator1
>::value_type
1122 int k
= static_cast<int>(seqs_end
- seqs_begin
);
1124 int num_threads
= omp_get_num_threads();
1126 difference_type num_samples
=
1127 __gnu_parallel::_Settings::get().merge_oversampling
* num_threads
;
1129 value_type
* samples
= static_cast<value_type
*>(
1130 ::operator new(sizeof(value_type
) * k
* num_samples
));
1132 for (int s
= 0; s
< k
; ++s
)
1133 for (difference_type i
= 0; i
< num_samples
; ++i
)
1135 difference_type sample_index
=
1136 static_cast<difference_type
>(
1137 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[s
])
1138 * (double(i
+ 1) / (num_samples
+ 1))
1139 * (double(length
) / total_length
));
1140 new(&(samples
[s
* num_samples
+ i
]))
1141 value_type(seqs_begin
[s
].first
[sample_index
]);
1144 // Sort stable or non-stable, depending on value of template parameter
1146 sampling_sorter
<stable
, value_type
*, Comparator
>()(
1147 samples
, samples
+ (num_samples
* k
), comp
);
1149 for (int slab
= 0; slab
< num_threads
; ++slab
)
1150 // For each slab / processor.
1151 for (int seq
= 0; seq
< k
; ++seq
)
1153 // For each sequence.
1155 pieces
[slab
][seq
].first
=
1157 seqs_begin
[seq
].first
,
1158 seqs_begin
[seq
].second
,
1159 samples
[num_samples
* k
* slab
/ num_threads
],
1161 - seqs_begin
[seq
].first
;
1163 // Absolute beginning.
1164 pieces
[slab
][seq
].first
= 0;
1165 if ((slab
+ 1) < num_threads
)
1166 pieces
[slab
][seq
].second
=
1168 seqs_begin
[seq
].first
,
1169 seqs_begin
[seq
].second
,
1170 samples
[num_samples
* k
* (slab
+ 1) /
1172 - seqs_begin
[seq
].first
;
1175 pieces
[slab
][seq
].second
= _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1177 ::operator delete(samples
);
1181 * @brief Exact splitting for parallel multiway-merge routine.
1183 * None of the passed sequences may be empty.
1187 , typename RandomAccessIteratorIterator
1188 , typename Comparator
1189 , typename difference_type
>
1190 void multiway_merge_exact_splitting(
1191 RandomAccessIteratorIterator seqs_begin
,
1192 RandomAccessIteratorIterator seqs_end
,
1194 difference_type length
,
1195 difference_type total_length
,
1196 std::vector
<std::pair
<difference_type
, difference_type
> > *pieces
)
1198 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1199 ::value_type::first_type
1200 RandomAccessIterator1
;
1202 const bool tight
= (total_length
== length
);
1205 const int k
= static_cast<int>(seqs_end
- seqs_begin
);
1207 const int num_threads
= omp_get_num_threads();
1209 // (Settings::multiway_merge_splitting == __gnu_parallel::_Settings::EXACT).
1210 std::vector
<RandomAccessIterator1
>* offsets
=
1211 new std::vector
<RandomAccessIterator1
>[num_threads
];
1213 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>
1216 copy(seqs_begin
, seqs_end
, se
.begin());
1218 difference_type
* borders
=
1219 new difference_type
[num_threads
+ 1];
1220 equally_split(length
, num_threads
, borders
);
1222 for (int s
= 0; s
< (num_threads
- 1); ++s
)
1224 offsets
[s
].resize(k
);
1226 se
.begin(), se
.end(), borders
[s
+ 1],
1227 offsets
[s
].begin(), comp
);
1229 // Last one also needed and available.
1232 offsets
[num_threads
- 1].resize(k
);
1233 multiseq_partition(se
.begin(), se
.end(),
1234 difference_type(length
),
1235 offsets
[num_threads
- 1].begin(), comp
);
1240 for (int slab
= 0; slab
< num_threads
; ++slab
)
1242 // For each slab / processor.
1243 for (int seq
= 0; seq
< k
; ++seq
)
1245 // For each sequence.
1248 // Absolute beginning.
1249 pieces
[slab
][seq
].first
= 0;
1252 pieces
[slab
][seq
].first
=
1253 pieces
[slab
- 1][seq
].second
;
1254 if (!tight
|| slab
< (num_threads
- 1))
1255 pieces
[slab
][seq
].second
=
1256 offsets
[slab
][seq
] - seqs_begin
[seq
].first
;
1259 // slab == num_threads - 1
1260 pieces
[slab
][seq
].second
=
1261 _GLIBCXX_PARALLEL_LENGTH(seqs_begin
[seq
]);
1268 /** @brief Parallel multi-way merge routine.
1270 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1271 * and runtime settings.
1273 * Must not be called if the number of sequences is 1.
1275 * @param Splitter functor to split input (either exact or sampling based)
1277 * @param seqs_begin Begin iterator of iterator pair input sequence.
1278 * @param seqs_end End iterator of iterator pair input sequence.
1279 * @param target Begin iterator out output sequence.
1280 * @param comp Comparator.
1281 * @param length Maximum length to merge, possibly larger than the
1282 * number of elements available.
1283 * @param stable Stable merging incurs a performance penalty.
1284 * @param sentinel Ignored.
1285 * @return End iterator of output sequence.
1290 typename RandomAccessIteratorIterator
,
1291 typename RandomAccessIterator3
,
1292 typename _DifferenceTp
,
1296 RandomAccessIterator3
1297 parallel_multiway_merge(RandomAccessIteratorIterator seqs_begin
,
1298 RandomAccessIteratorIterator seqs_end
,
1299 RandomAccessIterator3 target
,
1302 _DifferenceTp length
)
1304 #if _GLIBCXX_ASSERTIONS
1305 _GLIBCXX_PARALLEL_ASSERT(seqs_end
- seqs_begin
> 1);
1308 _GLIBCXX_CALL(length
)
1310 typedef _DifferenceTp difference_type
;
1311 typedef typename
std::iterator_traits
<RandomAccessIteratorIterator
>
1312 ::value_type::first_type
1313 RandomAccessIterator1
;
1315 std::iterator_traits
<RandomAccessIterator1
>::value_type value_type
;
1317 // Leave only non-empty sequences.
1318 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* ne_seqs
=
1319 static_cast<std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>*>(
1321 sizeof(std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>)
1322 * (seqs_end
- seqs_begin
)));
1324 difference_type total_length
= 0;
1325 for (RandomAccessIteratorIterator raii
= seqs_begin
;
1326 raii
!= seqs_end
; ++raii
)
1328 _DifferenceTp seq_length
= _GLIBCXX_PARALLEL_LENGTH(*raii
);
1331 total_length
+= seq_length
;
1332 //ne_seqs[k] = *raii;
1333 new(&(ne_seqs
[k
++]))
1334 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>(*raii
);
1338 _GLIBCXX_CALL(total_length
)
1340 length
= std::min
<_DifferenceTp
>(length
, total_length
);
1342 if (total_length
== 0 || k
== 0)
1344 ::operator delete(ne_seqs
);
1348 std::vector
<std::pair
<difference_type
, difference_type
> >* pieces
;
1350 thread_index_t num_threads
= static_cast<thread_index_t
>
1351 (std::min
<difference_type
>(get_max_threads(), total_length
));
1353 # pragma omp parallel num_threads (num_threads)
1357 num_threads
= omp_get_num_threads();
1358 // Thread t will have to merge pieces[iam][0..k - 1]
1359 pieces
= new std::vector
<
1360 std::pair
<difference_type
, difference_type
> >[num_threads
];
1361 for (int s
= 0; s
< num_threads
; ++s
)
1362 pieces
[s
].resize(k
);
1364 difference_type num_samples
=
1365 __gnu_parallel::_Settings::get().merge_oversampling
*
1368 splitter(ne_seqs
, ne_seqs
+ k
, comp
, length
, total_length
,
1372 thread_index_t iam
= omp_get_thread_num();
1374 difference_type target_position
= 0;
1376 for (int c
= 0; c
< k
; ++c
)
1377 target_position
+= pieces
[iam
][c
].first
;
1379 std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>* chunks
1380 = new std::pair
<RandomAccessIterator1
, RandomAccessIterator1
>[k
];
1382 for (int s
= 0; s
< k
; ++s
)
1384 chunks
[s
] = std::make_pair(
1385 ne_seqs
[s
].first
+ pieces
[iam
][s
].first
,
1386 ne_seqs
[s
].first
+ pieces
[iam
][s
].second
);
1389 if(length
> target_position
)
1390 sequential_multiway_merge
<stable
, sentinels
>(
1391 chunks
, chunks
+ k
, target
+ target_position
,
1392 *(seqs_begin
->second
), comp
, length
- target_position
);
1397 #if _GLIBCXX_ASSERTIONS
1398 _GLIBCXX_PARALLEL_ASSERT(is_sorted(target
, target
+ length
, comp
));
1402 // Update ends of sequences.
1403 for (RandomAccessIteratorIterator raii
= seqs_begin
;
1404 raii
!= seqs_end
; ++raii
)
1406 _DifferenceTp length
= _GLIBCXX_PARALLEL_LENGTH(*raii
);
1408 (*raii
).first
+= pieces
[num_threads
- 1][k
++].second
;
1413 return target
+ length
;
1417 * @brief Multiway Merge Frontend.
1419 * Merge the sequences specified by seqs_begin and seqs_end into
1420 * target. seqs_begin and seqs_end must point to a sequence of
1421 * pairs. These pairs must contain an iterator to the beginning
1422 * of a sequence in their first entry and an iterator the end of
1423 * the same sequence in their second entry.
1425 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1426 * that breaks ties by sequence number but is slower.
1428 * The first entries of the pairs (i.e. the begin iterators) will be moved
1431 * The output sequence has to provide enough space for all elements
1432 * that are written to it.
1434 * This function will merge the input sequences:
1437 * - parallel, depending on the input size and Settings
1438 * - using sampling for splitting
1439 * - not using sentinels
1444 * int sequences[10][10];
1445 * for (int i = 0; i < 10; ++i)
1446 * for (int j = 0; i < 10; ++j)
1447 * sequences[i][j] = j;
1450 * std::vector<std::pair<int*> > seqs;
1451 * for (int i = 0; i < 10; ++i)
1452 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1454 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1457 * @see stable_multiway_merge
1459 * @pre All input sequences must be sorted.
1460 * @pre Target must provide enough space to merge out length elements or
1461 * the number of elements in all sequences, whichever is smaller.
1463 * @post [target, return value) contains merged elements from the
1465 * @post return value - target = min(length, number of elements in all
1468 * @param RandomAccessIteratorPairIterator iterator over sequence
1469 * of pairs of iterators
1470 * @param RandomAccessIteratorOut iterator over target sequence
1471 * @param _DifferenceTp difference type for the sequence
1472 * @param Comparator strict weak ordering type to compare elements
1475 * @param seqs_begin begin of sequence sequence
1476 * @param seqs_end end of sequence sequence
1477 * @param target target sequence to merge to.
1478 * @param comp strict weak ordering to use for element comparison.
1479 * @param length Maximum length to merge, possibly larger than the
1480 * number of elements available.
1482 * @return end iterator of output sequence
1486 typename RandomAccessIteratorPairIterator
1487 , typename RandomAccessIteratorOut
1488 , typename _DifferenceTp
1489 , typename Comparator
>
1490 RandomAccessIteratorOut
1491 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1492 , RandomAccessIteratorPairIterator seqs_end
1493 , RandomAccessIteratorOut target
1494 , Comparator comp
, _DifferenceTp length
)
1496 typedef _DifferenceTp difference_type
;
1497 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1499 // catch special case: no sequences
1500 if (seqs_begin
== seqs_end
)
1503 // Execute merge; maybe parallel, depending on the number of merged
1504 // elements and the number of sequences and global thresholds in
1506 if ((seqs_end
- seqs_begin
> 1) &&
1507 _GLIBCXX_PARALLEL_CONDITION(
1508 ((seqs_end
- seqs_begin
) >=
1509 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1510 && ((sequence_index_t
)length
>=
1511 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1512 return parallel_multiway_merge
1513 </* stable = */ false, /* sentinels = */ false>
1514 (seqs_begin
, seqs_end
, target
, comp
,
1515 multiway_merge_sampling_splitting
</* stable = */ false,
1516 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1517 ::value_type
*, Comparator
, _DifferenceTp
>,
1518 static_cast<difference_type
>(length
));
1520 return sequential_multiway_merge
1521 </* stable = */false, /* sentinels = */ false>(
1522 seqs_begin
, seqs_end
,
1523 target
, *(seqs_begin
->second
), comp
, length
);
1528 typename RandomAccessIteratorPairIterator
1529 , typename RandomAccessIteratorOut
1530 , typename _DifferenceTp
1531 , typename Comparator
>
1532 RandomAccessIteratorOut
1533 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1534 , RandomAccessIteratorPairIterator seqs_end
1535 , RandomAccessIteratorOut target
1536 , Comparator comp
, _DifferenceTp length
1537 , __gnu_parallel::sequential_tag
)
1539 typedef _DifferenceTp difference_type
;
1540 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1542 // catch special case: no sequences
1543 if (seqs_begin
== seqs_end
)
1546 // Execute multiway merge *sequentially*.
1547 return sequential_multiway_merge
1548 </* stable = */ false, /* sentinels = */ false>
1549 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), comp
, length
);
1554 typename RandomAccessIteratorPairIterator
1555 , typename RandomAccessIteratorOut
1556 , typename _DifferenceTp
1557 , typename Comparator
>
1558 RandomAccessIteratorOut
1559 multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1560 , RandomAccessIteratorPairIterator seqs_end
1561 , RandomAccessIteratorOut target
1562 , Comparator comp
, _DifferenceTp length
1563 , __gnu_parallel::exact_tag
)
1565 typedef _DifferenceTp difference_type
;
1566 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1568 // catch special case: no sequences
1569 if (seqs_begin
== seqs_end
)
1572 // Execute merge; maybe parallel, depending on the number of merged
1573 // elements and the number of sequences and global thresholds in
1575 if ((seqs_end
- seqs_begin
> 1) &&
1576 _GLIBCXX_PARALLEL_CONDITION(
1577 ((seqs_end
- seqs_begin
) >=
1578 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1579 && ((sequence_index_t
)length
>=
1580 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1581 return parallel_multiway_merge
1582 </* stable = */ false, /* sentinels = */ false>(
1583 seqs_begin
, seqs_end
,
1585 multiway_merge_exact_splitting
</* stable = */ false,
1586 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1587 ::value_type
*, Comparator
, _DifferenceTp
>,
1588 static_cast<difference_type
>(length
));
1590 return sequential_multiway_merge
1591 </* stable = */ false, /* sentinels = */ false>(
1592 seqs_begin
, seqs_end
,
1593 target
, *(seqs_begin
->second
), comp
, length
);
1598 typename RandomAccessIteratorPairIterator
1599 , typename RandomAccessIteratorOut
1600 , typename _DifferenceTp
1601 , typename Comparator
>
1602 RandomAccessIteratorOut
1603 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1604 , RandomAccessIteratorPairIterator seqs_end
1605 , RandomAccessIteratorOut target
1606 , Comparator comp
, _DifferenceTp length
)
1608 typedef _DifferenceTp difference_type
;
1609 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1611 // catch special case: no sequences
1612 if (seqs_begin
== seqs_end
)
1615 // Execute merge; maybe parallel, depending on the number of merged
1616 // elements and the number of sequences and global thresholds in
1618 if ((seqs_end
- seqs_begin
> 1) &&
1619 _GLIBCXX_PARALLEL_CONDITION(
1620 ((seqs_end
- seqs_begin
) >=
1621 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1622 && ((sequence_index_t
)length
>=
1623 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1624 return parallel_multiway_merge
1625 </* stable = */ true, /* sentinels = */ false>(
1626 seqs_begin
, seqs_end
,
1628 multiway_merge_sampling_splitting
</* stable = */ true,
1629 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1630 ::value_type
*, Comparator
, _DifferenceTp
>,
1631 static_cast<difference_type
>(length
));
1633 return sequential_multiway_merge
1634 </* stable = */ true, /* sentinels = */ false>(
1635 seqs_begin
, seqs_end
,
1636 target
, *(seqs_begin
->second
), comp
, length
);
1641 typename RandomAccessIteratorPairIterator
1642 , typename RandomAccessIteratorOut
1643 , typename _DifferenceTp
1644 , typename Comparator
>
1645 RandomAccessIteratorOut
1646 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1647 , RandomAccessIteratorPairIterator seqs_end
1648 , RandomAccessIteratorOut target
1649 , Comparator comp
, _DifferenceTp length
1650 , __gnu_parallel::sequential_tag
)
1652 typedef _DifferenceTp difference_type
;
1653 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1655 // catch special case: no sequences
1656 if (seqs_begin
== seqs_end
)
1659 // Execute multiway merge *sequentially*.
1660 return sequential_multiway_merge
1661 </* stable = */ true, /* sentinels = */ false>
1662 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), comp
, length
);
1667 typename RandomAccessIteratorPairIterator
1668 , typename RandomAccessIteratorOut
1669 , typename _DifferenceTp
1670 , typename Comparator
>
1671 RandomAccessIteratorOut
1672 stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin
1673 , RandomAccessIteratorPairIterator seqs_end
1674 , RandomAccessIteratorOut target
1675 , Comparator comp
, _DifferenceTp length
1676 , __gnu_parallel::exact_tag
)
1678 typedef _DifferenceTp difference_type
;
1679 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1681 // catch special case: no sequences
1682 if (seqs_begin
== seqs_end
)
1685 // Execute merge; maybe parallel, depending on the number of merged
1686 // elements and the number of sequences and global thresholds in
1688 if ((seqs_end
- seqs_begin
> 1) &&
1689 _GLIBCXX_PARALLEL_CONDITION(
1690 ((seqs_end
- seqs_begin
) >=
1691 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1692 && ((sequence_index_t
)length
>=
1693 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1694 return parallel_multiway_merge
1695 </* stable = */ true, /* sentinels = */ false>(
1696 seqs_begin
, seqs_end
,
1698 multiway_merge_exact_splitting
1699 </* stable = */ true,
1700 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1701 ::value_type
*, Comparator
, _DifferenceTp
>,
1702 static_cast<difference_type
>(length
));
1704 return sequential_multiway_merge
</* stable = */ true,
1705 /* sentinels = */ false>(
1706 seqs_begin
, seqs_end
,
1707 target
, *(seqs_begin
->second
), comp
, length
);
1711 * @brief Multiway Merge Frontend.
1713 * Merge the sequences specified by seqs_begin and seqs_end into
1714 * target. seqs_begin and seqs_end must point to a sequence of
1715 * pairs. These pairs must contain an iterator to the beginning
1716 * of a sequence in their first entry and an iterator the end of
1717 * the same sequence in their second entry.
1719 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1720 * that breaks ties by sequence number but is slower.
1722 * The first entries of the pairs (i.e. the begin iterators) will be moved
1723 * forward accordingly.
1725 * The output sequence has to provide enough space for all elements
1726 * that are written to it.
1728 * This function will merge the input sequences:
1731 * - parallel, depending on the input size and Settings
1732 * - using sampling for splitting
1735 * You have to take care that the element the end iterator points to is
1736 * readable and contains a value that is greater than any other non-sentinel
1737 * value in all sequences.
1742 * int sequences[10][11];
1743 * for (int i = 0; i < 10; ++i)
1744 * for (int j = 0; i < 11; ++j)
1745 * sequences[i][j] = j; // last one is sentinel!
1748 * std::vector<std::pair<int*> > seqs;
1749 * for (int i = 0; i < 10; ++i)
1750 * { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
1752 * multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);
1755 * @pre All input sequences must be sorted.
1756 * @pre Target must provide enough space to merge out length elements or
1757 * the number of elements in all sequences, whichever is smaller.
1758 * @pre For each @c i, @c seqs_begin[i].second must be the end
1759 * marker of the sequence, but also reference the one more sentinel
1762 * @post [target, return value) contains merged elements from the
1764 * @post return value - target = min(length, number of elements in all
1767 * @see stable_multiway_merge_sentinels
1769 * @param RandomAccessIteratorPairIterator iterator over sequence
1770 * of pairs of iterators
1771 * @param RandomAccessIteratorOut iterator over target sequence
1772 * @param _DifferenceTp difference type for the sequence
1773 * @param Comparator strict weak ordering type to compare elements
1776 * @param seqs_begin begin of sequence sequence
1777 * @param seqs_end end of sequence sequence
1778 * @param target target sequence to merge to.
1779 * @param comp strict weak ordering to use for element comparison.
1780 * @param length Maximum length to merge, possibly larger than the
1781 * number of elements available.
1783 * @return end iterator of output sequence
1787 typename RandomAccessIteratorPairIterator
1788 , typename RandomAccessIteratorOut
1789 , typename _DifferenceTp
1790 , typename Comparator
>
1791 RandomAccessIteratorOut
1792 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1793 , RandomAccessIteratorPairIterator seqs_end
1794 , RandomAccessIteratorOut target
1795 , Comparator comp
, _DifferenceTp length
)
1797 typedef _DifferenceTp difference_type
;
1798 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1800 // catch special case: no sequences
1801 if (seqs_begin
== seqs_end
)
1804 // Execute merge; maybe parallel, depending on the number of merged
1805 // elements and the number of sequences and global thresholds in
1807 if ((seqs_end
- seqs_begin
> 1) &&
1808 _GLIBCXX_PARALLEL_CONDITION(
1809 ((seqs_end
- seqs_begin
) >=
1810 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1811 && ((sequence_index_t
)length
>=
1812 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1813 return parallel_multiway_merge
1814 </* stable = */ false, /* sentinels = */ true>
1815 (seqs_begin
, seqs_end
, target
, comp
,
1816 multiway_merge_sampling_splitting
1817 </* stable = */ false,
1818 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1819 ::value_type
*, Comparator
, _DifferenceTp
>,
1820 static_cast<difference_type
>(length
));
1822 return sequential_multiway_merge
1823 </* stable = */false, /* sentinels = */ true>(
1824 seqs_begin
, seqs_end
,
1825 target
, *(seqs_begin
->second
), comp
, length
);
1830 typename RandomAccessIteratorPairIterator
1831 , typename RandomAccessIteratorOut
1832 , typename _DifferenceTp
1833 , typename Comparator
>
1834 RandomAccessIteratorOut
1835 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1836 , RandomAccessIteratorPairIterator seqs_end
1837 , RandomAccessIteratorOut target
1838 , Comparator comp
, _DifferenceTp length
1839 , __gnu_parallel::sequential_tag
)
1841 typedef _DifferenceTp difference_type
;
1842 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1844 // catch special case: no sequences
1845 if (seqs_begin
== seqs_end
)
1848 // Execute multiway merge *sequentially*.
1849 return sequential_multiway_merge
1850 </* stable = */ false, /* sentinels = */ true>
1851 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), comp
, length
);
1856 typename RandomAccessIteratorPairIterator
1857 , typename RandomAccessIteratorOut
1858 , typename _DifferenceTp
1859 , typename Comparator
>
1860 RandomAccessIteratorOut
1861 multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1862 , RandomAccessIteratorPairIterator seqs_end
1863 , RandomAccessIteratorOut target
1864 , Comparator comp
, _DifferenceTp length
1865 , __gnu_parallel::exact_tag
)
1867 typedef _DifferenceTp difference_type
;
1868 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1870 // catch special case: no sequences
1871 if (seqs_begin
== seqs_end
)
1874 // Execute merge; maybe parallel, depending on the number of merged
1875 // elements and the number of sequences and global thresholds in
1877 if ((seqs_end
- seqs_begin
> 1) &&
1878 _GLIBCXX_PARALLEL_CONDITION(
1879 ((seqs_end
- seqs_begin
) >=
1880 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1881 && ((sequence_index_t
)length
>=
1882 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1883 return parallel_multiway_merge
1884 </* stable = */ false, /* sentinels = */ true>(
1885 seqs_begin
, seqs_end
,
1887 multiway_merge_exact_splitting
1888 </* stable = */ false,
1889 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1890 ::value_type
*, Comparator
, _DifferenceTp
>,
1891 static_cast<difference_type
>(length
));
1893 return sequential_multiway_merge
1894 </* stable = */ false, /* sentinels = */ true>(
1895 seqs_begin
, seqs_end
,
1896 target
, *(seqs_begin
->second
), comp
, length
);
1901 typename RandomAccessIteratorPairIterator
1902 , typename RandomAccessIteratorOut
1903 , typename _DifferenceTp
1904 , typename Comparator
>
1905 RandomAccessIteratorOut
1906 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1907 , RandomAccessIteratorPairIterator seqs_end
1908 , RandomAccessIteratorOut target
1909 , Comparator comp
, _DifferenceTp length
)
1911 typedef _DifferenceTp difference_type
;
1912 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1914 // catch special case: no sequences
1915 if (seqs_begin
== seqs_end
)
1918 // Execute merge; maybe parallel, depending on the number of merged
1919 // elements and the number of sequences and global thresholds in
1921 if ((seqs_end
- seqs_begin
> 1) &&
1922 _GLIBCXX_PARALLEL_CONDITION(
1923 ((seqs_end
- seqs_begin
) >=
1924 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1925 && ((sequence_index_t
)length
>=
1926 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1927 return parallel_multiway_merge
1928 </* stable = */ true, /* sentinels = */ true>(
1929 seqs_begin
, seqs_end
,
1931 multiway_merge_sampling_splitting
1932 </* stable = */ true,
1933 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
1934 ::value_type
*, Comparator
, _DifferenceTp
>,
1935 static_cast<difference_type
>(length
));
1937 return sequential_multiway_merge
1938 </* stable = */ true, /* sentinels = */ true>(
1939 seqs_begin
, seqs_end
,
1940 target
, *(seqs_begin
->second
), comp
, length
);
1945 typename RandomAccessIteratorPairIterator
1946 , typename RandomAccessIteratorOut
1947 , typename _DifferenceTp
1948 , typename Comparator
>
1949 RandomAccessIteratorOut
1950 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1951 , RandomAccessIteratorPairIterator seqs_end
1952 , RandomAccessIteratorOut target
1953 , Comparator comp
, _DifferenceTp length
1954 , __gnu_parallel::sequential_tag
)
1956 typedef _DifferenceTp difference_type
;
1957 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1959 // catch special case: no sequences
1960 if (seqs_begin
== seqs_end
)
1963 // Execute multiway merge *sequentially*.
1964 return sequential_multiway_merge
1965 </* stable = */ true, /* sentinels = */ true>
1966 (seqs_begin
, seqs_end
, target
, *(seqs_begin
->second
), comp
, length
);
1971 typename RandomAccessIteratorPairIterator
1972 , typename RandomAccessIteratorOut
1973 , typename _DifferenceTp
1974 , typename Comparator
>
1975 RandomAccessIteratorOut
1976 stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
1977 , RandomAccessIteratorPairIterator seqs_end
1978 , RandomAccessIteratorOut target
1979 , Comparator comp
, _DifferenceTp length
1980 , __gnu_parallel::exact_tag
)
1982 typedef _DifferenceTp difference_type
;
1983 _GLIBCXX_CALL(seqs_end
- seqs_begin
)
1985 // catch special case: no sequences
1986 if (seqs_begin
== seqs_end
)
1989 // Execute merge; maybe parallel, depending on the number of merged
1990 // elements and the number of sequences and global thresholds in
1992 if ((seqs_end
- seqs_begin
> 1) &&
1993 _GLIBCXX_PARALLEL_CONDITION(
1994 ((seqs_end
- seqs_begin
) >=
1995 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1996 && ((sequence_index_t
)length
>=
1997 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1998 return parallel_multiway_merge
1999 </* stable = */ true, /* sentinels = */ true>(
2000 seqs_begin
, seqs_end
,
2002 multiway_merge_exact_splitting
2003 </* stable = */ true,
2004 typename
std::iterator_traits
<RandomAccessIteratorPairIterator
>
2005 ::value_type
*, Comparator
, _DifferenceTp
>,
2006 static_cast<difference_type
>(length
));
2008 return sequential_multiway_merge
2009 </* stable = */ true, /* sentinels = */ true>(
2010 seqs_begin
, seqs_end
,
2011 target
, *(seqs_begin
->second
), comp
, length
);
2014 }; // namespace __gnu_parallel