tlx
Loading...
Searching...
No Matches
multiway_merge.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/algorithm/multiway_merge.hpp
3 *
4 * Many variants of multiway merge.
5 *
6 * Copied and modified from STXXL, see http://stxxl.org, which itself extracted
7 * it from MCSTL http://algo2.iti.uni-karlsruhe.de/singler/mcstl/. Both are
8 * distributed under the Boost Software License, Version 1.0.
9 *
10 * Part of tlx - http://panthema.net/tlx
11 *
12 * Copyright (C) 2007 Johannes Singler <singler@ira.uka.de>
13 * Copyright (C) 2014-2018 Timo Bingmann <tb@panthema.net>
14 *
15 * All rights reserved. Published under the Boost Software License, Version 1.0
16 ******************************************************************************/
17
18#ifndef TLX_ALGORITHM_MULTIWAY_MERGE_HEADER
19#define TLX_ALGORITHM_MULTIWAY_MERGE_HEADER
20
21#include <algorithm>
22#include <functional>
23#include <numeric>
24#include <utility>
25#include <vector>
26
30#include <tlx/unused.hpp>
31
32namespace tlx {
33
34//! \addtogroup tlx_algorithm
35//! \{
36
37namespace multiway_merge_detail {
38
39//! Size of a sequence described by a pair of iterators.
40template <typename RandomAccessIteratorPair>
41typename std::iterator_traits<
42 typename RandomAccessIteratorPair::first_type
43 >::difference_type
44iterpair_size(const RandomAccessIteratorPair& p) {
45 return p.second - p.first;
46}
47
48/*!
49 * Iterator wrapper supporting an implicit supremum at the end of the sequence,
50 * dominating all comparisons. Deriving from RandomAccessIterator is not
51 * possible since RandomAccessIterator need not be a class.
52*/
53template <typename RandomAccessIterator, typename Comparator>
55{
56public:
57 //! Our own type
59
60 //! Value type of the iterator
61 using value_type =
62 typename std::iterator_traits<RandomAccessIterator>::value_type;
63
64protected:
65 //! Current iterator position.
66 RandomAccessIterator current;
67 //! End iterator of the sequence.
68 RandomAccessIterator end_;
69 //! Comparator.
70 Comparator& comp_;
71
72public:
73 /*!
74 * Constructor. Sets iterator to beginning of sequence.
75 * \param begin Begin iterator of sequence.
76 * \param end End iterator of sequence.
77 * \param comp Comparator provided for associated overloaded compare
78 * operators.
79 */
80 guarded_iterator(RandomAccessIterator begin, RandomAccessIterator end,
81 Comparator& comp)
82 : current(begin), end_(end), comp_(comp)
83 { }
84
85 /*!
86 * Pre-increment operator.
87 * \return This.
88 */
90 ++current;
91 return *this;
92 }
93
94 /*!
95 * Dereference operator.
96 * \return Referenced element.
97 */
99 return *current;
100 }
101
102 /*!
103 * Convert to wrapped iterator.
104 * \return Wrapped iterator.
105 */
106 RandomAccessIterator& iterator() {
107 return current;
108 }
109
110 /*!
111 * Compare two elements referenced by guarded iterators.
112 * \param bi1 First iterator.
113 * \param bi2 Second iterator.
114 * \return \c True if less.
115 */
116 friend bool operator < (self_type& bi1, self_type& bi2) {
117 if (bi1.current == bi1.end_) // bi1 is sup
118 return bi2.current == bi2.end_; // bi2 is not sup
119 if (bi2.current == bi2.end_) // bi2 is sup
120 return true;
121 return bi1.comp_(*bi1, *bi2); // normal compare
122 }
123
124 /*!
125 * Compare two elements referenced by guarded iterators.
126 * \param bi1 First iterator.
127 * \param bi2 Second iterator.
128 * \return \c True if less equal.
129 */
130 friend bool operator <= (self_type& bi1, self_type& bi2) {
131 if (bi2.current == bi2.end_) // bi1 is sup
132 return bi1.current != bi1.end_; // bi2 is not sup
133 if (bi1.current == bi1.end_) // bi2 is sup
134 return false;
135 return !bi1.comp_(*bi2, *bi1); // normal compare
136 }
137};
138
139template <typename RandomAccessIterator, typename Comparator>
141{
142public:
143 //! Our own type
145
146 //! Value type of the iterator
148 typename std::iterator_traits<RandomAccessIterator>::value_type;
149
150protected:
151 //! Current iterator position.
152 RandomAccessIterator current;
153 //! Comparator.
154 Comparator& comp_;
155
156public:
157 /*!
158 * Constructor. Sets iterator to beginning of sequence.
159 * \param begin Begin iterator of sequence.
160 * param end Unused, only for compatibility.
161 * \param comp Unused, only for compatibility.
162 */
163 unguarded_iterator(RandomAccessIterator begin,
164 RandomAccessIterator /* end */,
165 Comparator& comp)
166 : current(begin), comp_(comp)
167 { }
168
169 /*!
170 * Pre-increment operator.
171 * \return This.
172 */
174 ++current;
175 return *this;
176 }
177
178 /*!
179 * Dereference operator.
180 * \return Referenced element.
181 */
183 return *current;
184 }
185
186 /*!
187 * Convert to wrapped iterator.
188 * \return Wrapped iterator.
189 */
190 RandomAccessIterator& iterator() {
191 return current;
192 }
193
194 /*!
195 * Compare two elements referenced by unguarded iterators.
196 * \param bi1 First iterator.
197 * \param bi2 Second iterator.
198 * \return \c True if less.
199 */
200 friend bool operator < (self_type& bi1, self_type& bi2) {
201 return bi1.comp_(*bi1, *bi2); // normal compare, unguarded
202 }
203
204 /*!
205 * Compare two elements referenced by unguarded iterators.
206 * \param bi1 First iterator.
207 * \param bi2 Second iterator.
208 * \return \c True if less equal.
209 */
210 friend bool operator <= (self_type& bi1, self_type& bi2) {
211 return !bi1.comp_(*bi2, *bi1); // normal compare, unguarded
212 }
213};
214
215/*!
216 * Prepare a set of sequences to be merged without a (end) guard
217 *
218 * \param seqs_begin
219 * \param seqs_end
220 * \param comp
221 * \param min_sequence
222 * \tparam Stable
223 * \pre (seqs_end - seqs_begin > 0)
224 */
225template <
226 bool Stable,
227 typename RandomAccessIteratorIterator,
228 typename Comparator>
229typename std::iterator_traits<
230 typename std::iterator_traits<
231 RandomAccessIteratorIterator>::value_type::first_type>::difference_type
233 RandomAccessIteratorIterator seqs_begin,
234 RandomAccessIteratorIterator seqs_end,
235 Comparator comp,
236 int& min_sequence) {
237 using RandomAccessIterator =
238 typename std::iterator_traits<RandomAccessIteratorIterator>
239 ::value_type::first_type;
240 using value_type = typename std::iterator_traits<RandomAccessIterator>
241 ::value_type;
242 using diff_type = typename std::iterator_traits<RandomAccessIterator>
243 ::difference_type;
244
245 if ((*seqs_begin).first == (*seqs_begin).second)
246 {
247 // empty sequence found, it's the first one
248 min_sequence = 0;
249 return -1;
250 }
251
252 // last element in sequence
253 value_type min = *((*seqs_begin).second - 1);
254 min_sequence = 0;
255 for (RandomAccessIteratorIterator s = seqs_begin + 1; s != seqs_end; ++s)
256 {
257 if ((*s).first == (*s).second)
258 {
259 // empty sequence found
260 min_sequence = static_cast<int>(s - seqs_begin);
261 return -1;
262 }
263 const value_type& v = *((*s).second - 1);
264 if (comp(v, min))
265 {
266 // last element in sequence is strictly smaller
267 min = v;
268 min_sequence = static_cast<int>(s - seqs_begin);
269 }
270 }
271
272 diff_type overhang_size = 0;
273
274 int s = 0;
275 for (s = 0; s <= min_sequence; ++s)
276 {
277 RandomAccessIterator split;
278 if (Stable)
279 split = std::upper_bound(seqs_begin[s].first, seqs_begin[s].second,
280 min, comp);
281 else
282 split = std::lower_bound(seqs_begin[s].first, seqs_begin[s].second,
283 min, comp);
284
285 overhang_size += seqs_begin[s].second - split;
286 }
287
288 for ( ; s < (seqs_end - seqs_begin); ++s)
289 {
290 RandomAccessIterator split =
291 std::lower_bound(seqs_begin[s].first, seqs_begin[s].second,
292 min, comp);
293 overhang_size += seqs_begin[s].second - split;
294 }
295
296 // so many elements will be left over afterwards
297 return overhang_size;
298}
299
300/*!
301 * Prepare a set of sequences to be merged with a (end) guard (sentinel)
302 * \param seqs_begin
303 * \param seqs_end
304 * \param comp
305 */
306template <typename RandomAccessIteratorIterator, typename Comparator>
307typename std::iterator_traits<
308 typename std::iterator_traits<
309 RandomAccessIteratorIterator>::value_type::first_type>::difference_type
311 RandomAccessIteratorIterator seqs_begin,
312 RandomAccessIteratorIterator seqs_end,
313 Comparator comp) {
314 using RandomAccessIterator =
315 typename std::iterator_traits<RandomAccessIteratorIterator>
316 ::value_type::first_type;
317 using value_type = typename std::iterator_traits<RandomAccessIterator>
318 ::value_type;
319 using diff_type = typename std::iterator_traits<RandomAccessIterator>
320 ::difference_type;
321
322 value_type* max_value = nullptr; // last element in sequence
323 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
324 {
325 if ((*s).first == (*s).second)
326 continue;
327 value_type& v = *((*s).second - 1); // last element in sequence
328 if (!max_value || comp(*max_value, v)) // strictly greater
329 max_value = &v;
330 }
331
332 diff_type overhang_size = 0;
333
334 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
335 {
336 RandomAccessIterator split = std::lower_bound(
337 (*s).first, (*s).second, *max_value, comp);
338 overhang_size += (*s).second - split;
339 *((*s).second) = *max_value; // set sentinel
340 }
341
342 // so many elements will be left over afterwards
343 return overhang_size;
344}
345
346/*!
347 * Highly efficient 3-way merging procedure.
348 *
349 * Merging is done with the algorithm implementation described by Peter
350 * Sanders. Basically, the idea is to minimize the number of necessary
351 * comparison after merging an element. The implementation trick that makes
352 * this fast is that the order of the sequences is stored in the instruction
353 * pointer (translated into labels in C++).
354 *
355 * This works well for merging up to 3 sequences.
356 *
357 * Note that making the merging stable does \a not come at a performance hit.
358 *
359 * Whether the merging is done guarded or unguarded is selected by the used
360 * iterator class.
361 *
362 * \param seqs_begin Begin iterator of iterator pair input sequence.
363 * \param seqs_end End iterator of iterator pair input sequence.
364 * \param target Begin iterator out output sequence.
365 * \param size Maximum size to merge.
366 * \param comp Comparator.
367 * \return End iterator of output sequence.
368 */
369template <
370 template <typename RAI, typename C> class Iterator,
371 typename RandomAccessIteratorIterator,
372 typename RandomAccessIterator3,
373 typename Comparator>
374RandomAccessIterator3 multiway_merge_3_variant(
375 RandomAccessIteratorIterator seqs_begin,
376 RandomAccessIteratorIterator seqs_end,
377 RandomAccessIterator3 target,
378 typename std::iterator_traits<
379 typename std::iterator_traits<
380 RandomAccessIteratorIterator>::value_type::first_type>::
381 difference_type size,
382 Comparator comp) {
383
384 assert(seqs_end - seqs_begin == 3);
385 unused(seqs_end);
386
387 using RandomAccessIterator =
388 typename std::iterator_traits<RandomAccessIteratorIterator>
389 ::value_type::first_type;
390
391 if (size == 0)
392 return target;
393
394 Iterator<RandomAccessIterator, Comparator>
395 seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
396 seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
397 seq2(seqs_begin[2].first, seqs_begin[2].second, comp);
398
399 if (seq0 <= seq1)
400 {
401 if (seq1 <= seq2)
402 goto s012;
403 else if (seq2 < seq0)
404 goto s201;
405 else
406 goto s021;
407 }
408 else
409 {
410 if (seq1 <= seq2)
411 {
412 if (seq0 <= seq2)
413 goto s102;
414 else
415 goto s120;
416 }
417 else
418 goto s210;
419 }
420
421#define TLX_MERGE3CASE(a, b, c, c0, c1) \
422 s ## a ## b ## c: \
423 *target = *seq ## a; \
424 ++target; \
425 --size; \
426 ++seq ## a; \
427 if (size == 0) goto finish; \
428 if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
429 if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
430 goto s ## b ## c ## a;
431
432 TLX_MERGE3CASE(0, 1, 2, <=, <=);
433 TLX_MERGE3CASE(1, 2, 0, <=, <);
434 TLX_MERGE3CASE(2, 0, 1, <, <);
435 TLX_MERGE3CASE(1, 0, 2, <, <=);
436 TLX_MERGE3CASE(0, 2, 1, <=, <=);
437 TLX_MERGE3CASE(2, 1, 0, <, <);
438
439#undef TLX_MERGE3CASE
440
441finish:
442 seqs_begin[0].first = seq0.iterator();
443 seqs_begin[1].first = seq1.iterator();
444 seqs_begin[2].first = seq2.iterator();
445
446 return target;
447}
448
449template <
450 typename RandomAccessIteratorIterator,
451 typename RandomAccessIterator3,
452 typename Comparator>
453RandomAccessIterator3 multiway_merge_3_combined(
454 RandomAccessIteratorIterator seqs_begin,
455 RandomAccessIteratorIterator seqs_end,
456 RandomAccessIterator3 target,
457 typename std::iterator_traits<
458 typename std::iterator_traits<
459 RandomAccessIteratorIterator>::value_type::first_type>::
460 difference_type size,
461 Comparator comp) {
462 using RandomAccessIterator =
463 typename std::iterator_traits<RandomAccessIteratorIterator>
464 ::value_type::first_type;
465 using DiffType = typename std::iterator_traits<RandomAccessIterator>
466 ::difference_type;
467
468 assert(seqs_end - seqs_begin == 3);
469
470 int min_seq;
471 RandomAccessIterator3 target_end;
472 DiffType overhang = prepare_unguarded<true>(seqs_begin, seqs_end, comp, min_seq);
473
474 DiffType total_size = 0;
475 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
476 total_size += iterpair_size(*s);
477
478 if (overhang != static_cast<DiffType>(-1))
479 {
480 DiffType unguarded_size = std::min(size, total_size - overhang);
481 target_end = multiway_merge_3_variant<unguarded_iterator>
482 (seqs_begin, seqs_end, target, unguarded_size, comp);
483 overhang = size - unguarded_size;
484 }
485 else
486 {
487 // empty sequence found
488 overhang = size;
489 target_end = target;
490 }
491
492 switch (min_seq)
493 {
494 case 0:
495 // iterators will be advanced accordingly
496 target_end = merge_advance(
497 seqs_begin[1].first, seqs_begin[1].second,
498 seqs_begin[2].first, seqs_begin[2].second,
499 target_end, overhang, comp);
500 break;
501 case 1:
502 target_end = merge_advance(
503 seqs_begin[0].first, seqs_begin[0].second,
504 seqs_begin[2].first, seqs_begin[2].second,
505 target_end, overhang, comp);
506 break;
507 case 2:
508 target_end = merge_advance(
509 seqs_begin[0].first, seqs_begin[0].second,
510 seqs_begin[1].first, seqs_begin[1].second,
511 target_end, overhang, comp);
512 break;
513 default:
514 assert(false);
515 }
516
517 return target_end;
518}
519
520/*!
521 * Highly efficient 4-way merging procedure.
522 *
523 * Merging is done with the algorithm implementation described by Peter
524 * Sanders. Basically, the idea is to minimize the number of necessary
525 * comparison after merging an element. The implementation trick that makes
526 * this fast is that the order of the sequences is stored in the instruction
527 * pointer (translated into goto labels in C++).
528 *
529 * This works well for merging up to 4 sequences.
530 *
531 * Note that making the merging stable does \a not come at a performance hit.
532 *
533 * Whether the merging is done guarded or unguarded is selected by the used
534 * iterator class.
535 *
536 * \param seqs_begin Begin iterator of iterator pair input sequence.
537 * \param seqs_end End iterator of iterator pair input sequence.
538 * \param target Begin iterator out output sequence.
539 * \param size Maximum size to merge.
540 * \param comp Comparator.
541 * \return End iterator of output sequence.
542 */
543template <
544 template <typename RAI, typename C> class iterator,
545 typename RandomAccessIteratorIterator,
546 typename RandomAccessIterator3,
547 typename Comparator>
548RandomAccessIterator3 multiway_merge_4_variant(
549 RandomAccessIteratorIterator seqs_begin,
550 RandomAccessIteratorIterator seqs_end,
551 RandomAccessIterator3 target,
552 typename std::iterator_traits<
553 typename std::iterator_traits<
554 RandomAccessIteratorIterator>::value_type::first_type>::
555 difference_type size,
556 Comparator comp) {
557 assert(seqs_end - seqs_begin == 4);
558 unused(seqs_end);
559 using RandomAccessIterator =
560 typename std::iterator_traits<RandomAccessIteratorIterator>
561 ::value_type::first_type;
562
563 if (size == 0)
564 return target;
565
566 iterator<RandomAccessIterator, Comparator>
567 seq0(seqs_begin[0].first, seqs_begin[0].second, comp),
568 seq1(seqs_begin[1].first, seqs_begin[1].second, comp),
569 seq2(seqs_begin[2].first, seqs_begin[2].second, comp),
570 seq3(seqs_begin[3].first, seqs_begin[3].second, comp);
571
572#define TLX_DECISION(a, b, c, d) do { \
573 if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
574 if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
575 if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
576 goto s ## a ## b ## c ## d; \
577} \
578 while (0)
579
580 if (seq0 <= seq1)
581 {
582 if (seq1 <= seq2)
583 TLX_DECISION(0, 1, 2, 3);
584 else if (seq2 < seq0)
585 TLX_DECISION(2, 0, 1, 3);
586 else
587 TLX_DECISION(0, 2, 1, 3);
588 }
589 else
590 {
591 if (seq1 <= seq2)
592 {
593 if (seq0 <= seq2)
594 TLX_DECISION(1, 0, 2, 3);
595 else
596 TLX_DECISION(1, 2, 0, 3);
597 }
598 else
599 TLX_DECISION(2, 1, 0, 3);
600 }
601
602#define TLX_MERGE4CASE(a, b, c, d, c0, c1, c2) \
603 s ## a ## b ## c ## d: \
604 *target = *seq ## a; \
605 ++target; \
606 --size; \
607 ++seq ## a; \
608 if (size == 0) goto finish; \
609 if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
610 if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
611 if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
612 goto s ## b ## c ## d ## a;
613
614 TLX_MERGE4CASE(0, 1, 2, 3, <=, <=, <=);
615 TLX_MERGE4CASE(0, 1, 3, 2, <=, <=, <=);
616 TLX_MERGE4CASE(0, 2, 1, 3, <=, <=, <=);
617 TLX_MERGE4CASE(0, 2, 3, 1, <=, <=, <=);
618 TLX_MERGE4CASE(0, 3, 1, 2, <=, <=, <=);
619 TLX_MERGE4CASE(0, 3, 2, 1, <=, <=, <=);
620 TLX_MERGE4CASE(1, 0, 2, 3, <, <=, <=);
621 TLX_MERGE4CASE(1, 0, 3, 2, <, <=, <=);
622 TLX_MERGE4CASE(1, 2, 0, 3, <=, <, <=);
623 TLX_MERGE4CASE(1, 2, 3, 0, <=, <=, <);
624 TLX_MERGE4CASE(1, 3, 0, 2, <=, <, <=);
625 TLX_MERGE4CASE(1, 3, 2, 0, <=, <=, <);
626 TLX_MERGE4CASE(2, 0, 1, 3, <, <, <=);
627 TLX_MERGE4CASE(2, 0, 3, 1, <, <=, <);
628 TLX_MERGE4CASE(2, 1, 0, 3, <, <, <=);
629 TLX_MERGE4CASE(2, 1, 3, 0, <, <=, <);
630 TLX_MERGE4CASE(2, 3, 0, 1, <=, <, <);
631 TLX_MERGE4CASE(2, 3, 1, 0, <=, <, <);
632 TLX_MERGE4CASE(3, 0, 1, 2, <, <, <);
633 TLX_MERGE4CASE(3, 0, 2, 1, <, <, <);
634 TLX_MERGE4CASE(3, 1, 0, 2, <, <, <);
635 TLX_MERGE4CASE(3, 1, 2, 0, <, <, <);
636 TLX_MERGE4CASE(3, 2, 0, 1, <, <, <);
637 TLX_MERGE4CASE(3, 2, 1, 0, <, <, <);
638
639#undef TLX_MERGE4CASE
640#undef TLX_DECISION
641
642finish:
643 seqs_begin[0].first = seq0.iterator();
644 seqs_begin[1].first = seq1.iterator();
645 seqs_begin[2].first = seq2.iterator();
646 seqs_begin[3].first = seq3.iterator();
647
648 return target;
649}
650
651template <
652 typename RandomAccessIteratorIterator,
653 typename RandomAccessIterator3,
654 typename Comparator>
655RandomAccessIterator3 multiway_merge_4_combined(
656 RandomAccessIteratorIterator seqs_begin,
657 RandomAccessIteratorIterator seqs_end,
658 RandomAccessIterator3 target,
659 typename std::iterator_traits<
660 typename std::iterator_traits<
661 RandomAccessIteratorIterator>::value_type::first_type>::
662 difference_type size,
663 Comparator comp) {
664
665 assert(seqs_end - seqs_begin == 4);
666 using RandomAccessIteratorPair =
667 typename std::iterator_traits<RandomAccessIteratorIterator>
668 ::value_type;
669 using DiffType = typename std::iterator_traits<RandomAccessIteratorIterator>
670 ::difference_type;
671
672 int min_seq;
673 RandomAccessIterator3 target_end;
674 DiffType overhang = prepare_unguarded<true>(seqs_begin, seqs_end, comp, min_seq);
675
676 DiffType total_size = 0;
677 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
678 total_size += iterpair_size(*s);
679
680 if (overhang != static_cast<DiffType>(-1))
681 {
682 DiffType unguarded_size = std::min(size, total_size - overhang);
683 target_end = multiway_merge_4_variant<unguarded_iterator>(
684 seqs_begin, seqs_end, target, unguarded_size, comp);
685 overhang = size - unguarded_size;
686 }
687 else
688 {
689 // empty sequence found
690 overhang = size;
691 target_end = target;
692 }
693
694 std::vector<RandomAccessIteratorPair> one_missing(seqs_begin, seqs_end);
695 // remove
696 one_missing.erase(one_missing.begin() + min_seq);
697
698 target_end = multiway_merge_3_variant<guarded_iterator>(
699 one_missing.begin(), one_missing.end(), target_end, overhang, comp);
700
701 // insert back again
702 one_missing.insert(one_missing.begin() + min_seq, seqs_begin[min_seq]);
703 // write back modified iterators
704 std::copy(one_missing.begin(), one_missing.end(), seqs_begin);
705
706 return target_end;
707}
708
709/*!
710 * Basic multi-way merging procedure.
711 *
712 * The head elements are kept in a sorted array, new heads are inserted
713 * linearly.
714 *
715 * \param seqs_begin Begin iterator of iterator pair input sequence.
716 * \param seqs_end End iterator of iterator pair input sequence.
717 * \param target Begin iterator out output sequence.
718 * \param size Maximum size to merge.
719 * \param comp Comparator.
720 * \tparam Stable Stable merging incurs a performance penalty.
721 * \return End iterator of output sequence.
722 */
723template <
724 bool Stable,
725 typename RandomAccessIteratorIterator,
726 typename RandomAccessIterator3,
727 typename Comparator>
728RandomAccessIterator3 multiway_merge_bubble(
729 RandomAccessIteratorIterator seqs_begin,
730 RandomAccessIteratorIterator seqs_end,
731 RandomAccessIterator3 target,
732 typename std::iterator_traits<
733 typename std::iterator_traits<
734 RandomAccessIteratorIterator>::value_type::first_type>::
735 difference_type size,
736 Comparator comp) {
737 using RandomAccessIterator =
738 typename std::iterator_traits<RandomAccessIteratorIterator>
739 ::value_type::first_type;
740 using value_type = typename std::iterator_traits<RandomAccessIterator>
741 ::value_type;
742 using DiffType = typename std::iterator_traits<RandomAccessIterator>
743 ::difference_type;
744
745 // num remaining pieces
746 int num_seqs = static_cast<int>(seqs_end - seqs_begin), nrp;
747
748 simple_vector<value_type> pl(num_seqs);
749 simple_vector<int> source(num_seqs);
750 DiffType total_size = 0;
751
752#define TLX_POS(i) seqs_begin[(i)].first
753#define TLX_STOPS(i) seqs_begin[(i)].second
754
755 // write entries into queue
756 nrp = 0;
757 for (int pi = 0; pi < num_seqs; ++pi)
758 {
759 if (TLX_STOPS(pi) != TLX_POS(pi))
760 {
761 pl[nrp] = *(TLX_POS(pi));
762 source[nrp] = pi;
763 ++nrp;
764 total_size += iterpair_size(seqs_begin[pi]);
765 }
766 }
767
768 if (Stable)
769 {
770 for (int k = 0; k < nrp - 1; ++k)
771 for (int pi = nrp - 1; pi > k; --pi)
772 if (comp(pl[pi], pl[pi - 1]) ||
773 (!comp(pl[pi - 1], pl[pi]) && source[pi] < source[pi - 1]))
774 {
775 std::swap(pl[pi - 1], pl[pi]);
776 std::swap(source[pi - 1], source[pi]);
777 }
778 }
779 else
780 {
781 for (int k = 0; k < nrp - 1; ++k)
782 for (int pi = nrp - 1; pi > k; --pi)
783 if (comp(pl[pi], pl[pi - 1]))
784 {
785 std::swap(pl[pi - 1], pl[pi]);
786 std::swap(source[pi - 1], source[pi]);
787 }
788 }
789
790 // iterate
791 if (Stable)
792 {
793 int j;
794 while (nrp > 0 && size > 0)
795 {
796 if (source[0] < source[1])
797 {
798 // pl[0] <= pl[1] ?
799 while ((nrp == 1 || !(comp(pl[1], pl[0]))) && size > 0)
800 {
801 *target = pl[0];
802 ++target;
803 ++TLX_POS(source[0]);
804 --size;
805 if (TLX_POS(source[0]) == TLX_STOPS(source[0]))
806 {
807 // move everything to the left
808 for (int s = 0; s < nrp - 1; ++s)
809 {
810 pl[s] = pl[s + 1];
811 source[s] = source[s + 1];
812 }
813 --nrp;
814 break;
815 }
816 else
817 pl[0] = *(TLX_POS(source[0]));
818 }
819 }
820 else
821 {
822 // pl[0] < pl[1] ?
823 while ((nrp == 1 || comp(pl[0], pl[1])) && size > 0)
824 {
825 *target = pl[0];
826 ++target;
827 ++TLX_POS(source[0]);
828 --size;
829 if (TLX_POS(source[0]) == TLX_STOPS(source[0]))
830 {
831 for (int s = 0; s < nrp - 1; ++s)
832 {
833 pl[s] = pl[s + 1];
834 source[s] = source[s + 1];
835 }
836 --nrp;
837 break;
838 }
839 else
840 pl[0] = *(TLX_POS(source[0]));
841 }
842 }
843
844 // sink down
845 j = 1;
846 while ((j < nrp) && (comp(pl[j], pl[j - 1]) ||
847 (!comp(pl[j - 1], pl[j]) && (source[j] < source[j - 1]))))
848 {
849 std::swap(pl[j - 1], pl[j]);
850 std::swap(source[j - 1], source[j]);
851 ++j;
852 }
853 }
854 }
855 else
856 {
857 int j;
858 while (nrp > 0 && size > 0)
859 {
860 // pl[0] <= pl[1] ?
861 while ((nrp == 1 || !comp(pl[1], pl[0])) && size > 0)
862 {
863 *target = pl[0];
864 ++target;
865 ++TLX_POS(source[0]);
866 --size;
867 if (TLX_POS(source[0]) == TLX_STOPS(source[0]))
868 {
869 for (int s = 0; s < (nrp - 1); ++s)
870 {
871 pl[s] = pl[s + 1];
872 source[s] = source[s + 1];
873 }
874 --nrp;
875 break;
876 }
877 else
878 pl[0] = *(TLX_POS(source[0]));
879 }
880
881 // sink down
882 j = 1;
883 while ((j < nrp) && comp(pl[j], pl[j - 1]))
884 {
885 std::swap(pl[j - 1], pl[j]);
886 std::swap(source[j - 1], source[j]);
887 ++j;
888 }
889 }
890 }
891
892#undef TLX_POS
893#undef TLX_STOPS
894
895 return target;
896}
897
898/*!
899 * Multi-way merging procedure for a high branching factor, guarded case.
900 *
901 * The head elements are kept in a loser tree.
902 * \param seqs_begin Begin iterator of iterator pair input sequence.
903 * \param seqs_end End iterator of iterator pair input sequence.
904 * \param target Begin iterator out output sequence.
905 * \param size Maximum size to merge.
906 * \param comp Comparator.
907 * \tparam Stable Stable merging incurs a performance penalty.
908 * \return End iterator of output sequence.
909 */
910template <
911 typename LoserTreeType,
912 typename RandomAccessIteratorIterator,
913 typename RandomAccessIterator3,
914 typename Comparator>
915RandomAccessIterator3 multiway_merge_loser_tree(
916 RandomAccessIteratorIterator seqs_begin,
917 RandomAccessIteratorIterator seqs_end,
918 RandomAccessIterator3 target,
919 typename std::iterator_traits<
920 typename std::iterator_traits<
921 RandomAccessIteratorIterator>::value_type::first_type>::
922 difference_type size,
923 Comparator comp) {
924 using Source = typename LoserTreeType::Source;
925 using size_type = typename LoserTreeType::Source;
926 using RandomAccessIteratorPair =
927 typename std::iterator_traits<RandomAccessIteratorIterator>::value_type;
928 using RandomAccessIterator = typename RandomAccessIteratorPair::first_type;
929 using DiffType = typename std::iterator_traits<RandomAccessIterator>
930 ::difference_type;
931
932 const Source k = static_cast<Source>(seqs_end - seqs_begin);
933
934 LoserTreeType lt(static_cast<size_type>(k), comp);
935
936 const DiffType total_size = std::min<DiffType>(
937 size,
938 std::accumulate(seqs_begin, seqs_end, DiffType(0),
939 [](DiffType sum, const RandomAccessIteratorPair& x) {
940 return sum + iterpair_size(x);
941 }));
942
943 for (Source t = 0; t < k; ++t)
944 {
945 if (TLX_UNLIKELY(seqs_begin[t].first == seqs_begin[t].second))
946 lt.insert_start(nullptr, t, true);
947 else
948 lt.insert_start(&*seqs_begin[t].first, t, false);
949 }
950
951 lt.init();
952
953 if (total_size == 0)
954 return target;
955
956 // take out first
957 Source source = lt.min_source();
958
959 *target = *seqs_begin[source].first;
960 ++target;
961 ++seqs_begin[source].first;
962
963 for (DiffType i = 1; i < total_size; ++i)
964 {
965 // feed
966 if (seqs_begin[source].first == seqs_begin[source].second)
967 lt.delete_min_insert(nullptr, true);
968 else
969 // replace from same source
970 lt.delete_min_insert(&*seqs_begin[source].first, false);
971
972 // take out following
973 source = lt.min_source();
974
975 *target = *seqs_begin[source].first;
976 ++target;
977 ++seqs_begin[source].first;
978 }
979
980 return target;
981}
982
983/*!
984 * Multi-way merging procedure for a high branching factor, unguarded case.
985 * The head elements are kept in a loser tree.
986 *
987 * \param seqs_begin Begin iterator of iterator pair input sequence.
988 * \param seqs_end End iterator of iterator pair input sequence.
989 * \param target Begin iterator out output sequence.
990 * \param size Maximum size to merge.
991 * \param comp Comparator.
992 * \tparam Stable Stable merging incurs a performance penalty.
993 * \return End iterator of output sequence.
994 * \pre No input will run out of elements during the merge.
995 */
996template <
997 typename LoserTreeType,
998 typename RandomAccessIteratorIterator,
999 typename RandomAccessIterator3,
1000 typename Comparator>
1002 RandomAccessIteratorIterator seqs_begin,
1003 RandomAccessIteratorIterator seqs_end,
1004 RandomAccessIterator3 target,
1005 typename std::iterator_traits<
1006 typename std::iterator_traits<
1007 RandomAccessIteratorIterator>::value_type::first_type>::
1008 difference_type size,
1009 Comparator comp) {
1010 using Source = typename LoserTreeType::Source;
1011 using size_type = typename LoserTreeType::Source;
1012 using RandomAccessIteratorPair =
1013 typename std::iterator_traits<RandomAccessIteratorIterator>
1014 ::value_type;
1015 using RandomAccessIterator = typename RandomAccessIteratorPair
1016 ::first_type;
1017 using DiffType = typename std::iterator_traits<RandomAccessIterator>
1018 ::difference_type;
1019
1020 Source k = static_cast<Source>(seqs_end - seqs_begin);
1021
1022 // sentinel is item at end of first sequence.
1023 LoserTreeType lt(static_cast<size_type>(k), *(seqs_begin->second - 1), comp);
1024
1025 DiffType total_size = 0;
1026
1027 for (Source t = 0; t < k; ++t)
1028 {
1029 assert(seqs_begin[t].first != seqs_begin[t].second);
1030
1031 lt.insert_start(&*seqs_begin[t].first, t, false);
1032
1033 total_size += iterpair_size(seqs_begin[t]);
1034 }
1035
1036 lt.init();
1037
1038 // do not go past end
1039 size = std::min(total_size, size);
1040
1041 RandomAccessIterator3 target_end = target + size;
1042 if (target == target_end)
1043 return target;
1044
1045 // take out first
1046 int source = lt.min_source();
1047
1048 *target = *seqs_begin[source].first;
1049 ++seqs_begin[source].first;
1050 ++target;
1051
1052 while (target < target_end)
1053 {
1054 // feed. replace from same source
1055 lt.delete_min_insert(&*seqs_begin[source].first, false);
1056
1057 // take out following
1058 source = lt.min_source();
1059
1060 *target = *seqs_begin[source].first;
1061 ++seqs_begin[source].first;
1062 ++target;
1063 }
1064
1065 return target;
1066}
1067
1068template <
1069 bool Stable,
1070 typename RandomAccessIteratorIterator,
1071 typename RandomAccessIterator3,
1072 typename Comparator>
1074 RandomAccessIteratorIterator seqs_begin,
1075 RandomAccessIteratorIterator seqs_end,
1076 RandomAccessIterator3 target,
1077 typename std::iterator_traits<
1078 typename std::iterator_traits<
1079 RandomAccessIteratorIterator>::value_type::first_type>::
1080 difference_type size,
1081 Comparator comp) {
1082 using RandomAccessIterator =
1083 typename std::iterator_traits<RandomAccessIteratorIterator>
1084 ::value_type::first_type;
1085 using value_type = typename std::iterator_traits<RandomAccessIterator>
1086 ::value_type;
1087 using DiffType = typename std::iterator_traits<RandomAccessIterator>
1088 ::difference_type;
1089
1090 int min_seq;
1091 RandomAccessIterator3 target_end;
1092 DiffType overhang = prepare_unguarded<Stable>(seqs_begin, seqs_end, comp, min_seq);
1093
1094 DiffType total_size = 0;
1095 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
1096 total_size += iterpair_size(*s);
1097
1098 if (overhang != static_cast<DiffType>(-1))
1099 {
1100 DiffType unguarded_size = std::min(size, total_size - overhang);
1102 LoserTreeUnguarded<Stable, value_type, Comparator> >(
1103 seqs_begin, seqs_end, target, unguarded_size, comp);
1104 overhang = size - unguarded_size;
1105 }
1106 else
1107 {
1108 // empty sequence found
1109 overhang = size;
1110 target_end = target;
1111 }
1112
1113 target_end = multiway_merge_loser_tree<
1114 LoserTree<Stable, value_type, Comparator> >(
1115 seqs_begin, seqs_end, target_end, overhang, comp);
1116
1117 return target_end;
1118}
1119
1120template <
1121 bool Stable,
1122 typename RandomAccessIteratorIterator,
1123 typename RandomAccessIterator3,
1124 typename Comparator>
1126 RandomAccessIteratorIterator seqs_begin,
1127 RandomAccessIteratorIterator seqs_end,
1128 RandomAccessIterator3 target,
1129 typename std::iterator_traits<
1130 typename std::iterator_traits<
1131 RandomAccessIteratorIterator>::value_type::first_type>::
1132 difference_type size,
1133 Comparator comp) {
1134 using RandomAccessIterator =
1135 typename std::iterator_traits<RandomAccessIteratorIterator>
1136 ::value_type::first_type;
1137 using value_type = typename std::iterator_traits<RandomAccessIterator>
1138 ::value_type;
1139
1140 // move end of sequences to include the sentinel for merging
1141 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
1142 ++(*s).second;
1143
1144 RandomAccessIterator3 target_end
1146 LoserTreeUnguarded<Stable, value_type, Comparator> >(
1147 seqs_begin, seqs_end, target, size, comp);
1148
1149 // restore end of sequences
1150 for (RandomAccessIteratorIterator s = seqs_begin; s != seqs_end; ++s)
1151 --(*s).second;
1152
1153 return target_end;
1154}
1155
1156} // namespace multiway_merge_detail
1157
1158/******************************************************************************/
1159// Multiway Merge Algorithm Switch
1160
1161/*!
1162 * Different merging algorithms: bubblesort-alike, loser-tree variants, enum
1163 * sentinel
1164 */
1173
1174/*!
1175 * Sequential multi-way merging switch.
1176 *
1177 * The decision if based on the branching factor and runtime settings.
1178 *
1179 * \param seqs_begin Begin iterator of iterator pair input sequence.
1180 * \param seqs_end End iterator of iterator pair input sequence.
1181 * \param target Begin iterator out output sequence.
1182 * \param size Maximum size to merge.
1183 * \param comp Comparator.
1184 * \param mwma MultiwayMergeAlgorithm set to use.
1185 * \tparam Stable Stable merging incurs a performance penalty.
1186 * \tparam Sentinels The sequences have a sentinel element.
1187 * \return End iterator of output sequence.
1188 */
1189template <
1190 bool Stable,
1191 bool Sentinels,
1192 typename RandomAccessIteratorIterator,
1193 typename RandomAccessIterator3,
1194 typename Comparator = std::less<
1195 typename std::iterator_traits<
1196 typename std::iterator_traits<RandomAccessIteratorIterator>
1197 ::value_type::first_type>::value_type> >
1198RandomAccessIterator3 multiway_merge_base(
1199 RandomAccessIteratorIterator seqs_begin,
1200 RandomAccessIteratorIterator seqs_end,
1201 RandomAccessIterator3 target,
1202 typename std::iterator_traits<
1203 typename std::iterator_traits<
1204 RandomAccessIteratorIterator>::value_type::first_type>::
1205 difference_type size,
1206 Comparator comp = Comparator(),
1208
1209 using RandomAccessIterator =
1210 typename std::iterator_traits<RandomAccessIteratorIterator>
1211 ::value_type::first_type;
1212 using value_type = typename std::iterator_traits<RandomAccessIterator>
1213 ::value_type;
1214
1215 RandomAccessIterator3 return_target = target;
1216 int k = static_cast<int>(seqs_end - seqs_begin);
1217
1218 if (!Sentinels && mwma == MWMA_LOSER_TREE_SENTINEL)
1220
1221 using namespace multiway_merge_detail;
1222
1223 switch (k)
1224 {
1225 case 0:
1226 break;
1227 case 1:
1228 return_target = std::copy(
1229 seqs_begin[0].first, seqs_begin[0].first + size, target);
1230 seqs_begin[0].first += size;
1231 break;
1232 case 2:
1233 return_target = merge_advance(
1234 seqs_begin[0].first, seqs_begin[0].second,
1235 seqs_begin[1].first, seqs_begin[1].second,
1236 target, size, comp);
1237 break;
1238 case 3:
1239 switch (mwma)
1240 {
1242 return_target = multiway_merge_3_combined(
1243 seqs_begin, seqs_end, target, size, comp);
1244 break;
1246 return_target = multiway_merge_3_variant<unguarded_iterator>(
1247 seqs_begin, seqs_end, target, size, comp);
1248 break;
1249 default:
1250 return_target = multiway_merge_3_variant<guarded_iterator>(
1251 seqs_begin, seqs_end, target, size, comp);
1252 break;
1253 }
1254 break;
1255 case 4:
1256 switch (mwma)
1257 {
1259 return_target = multiway_merge_4_combined(
1260 seqs_begin, seqs_end, target, size, comp);
1261 break;
1263 return_target = multiway_merge_4_variant<unguarded_iterator>(
1264 seqs_begin, seqs_end, target, size, comp);
1265 break;
1266 default:
1267 return_target = multiway_merge_4_variant<guarded_iterator>(
1268 seqs_begin, seqs_end, target, size, comp);
1269 break;
1270 }
1271 break;
1272 default:
1273 {
1274 switch (mwma)
1275 {
1276 case MWMA_BUBBLE:
1277 return_target = multiway_merge_bubble<Stable>(
1278 seqs_begin, seqs_end, target, size, comp);
1279 break;
1280 case MWMA_LOSER_TREE:
1281 return_target = multiway_merge_loser_tree<
1282 LoserTree<Stable, value_type, Comparator> >(
1283 seqs_begin, seqs_end, target, size, comp);
1284 break;
1286 return_target = multiway_merge_loser_tree_combined<Stable>(
1287 seqs_begin, seqs_end, target, size, comp);
1288 break;
1290 return_target = multiway_merge_loser_tree_sentinel<Stable>(
1291 seqs_begin, seqs_end, target, size, comp);
1292 break;
1293 default:
1294 assert(0 && "multiway_merge algorithm not implemented");
1295 break;
1296 }
1297 }
1298 }
1299
1300 return return_target;
1301}
1302
1303/******************************************************************************/
1304// multiway_merge() Frontends
1305
1306/*!
1307 * Sequential multi-way merge.
1308 *
1309 * \param seqs_begin Begin iterator of iterator pair input sequence.
1310 * \param seqs_end End iterator of iterator pair input sequence.
1311 * \param target Begin iterator out output sequence.
1312 * \param size Maximum size to merge.
1313 * \param comp Comparator.
1314 * \param mwma MultiwayMergeAlgorithm set to use.
1315 * \return End iterator of output sequence.
1316 */
1317template <
1318 typename RandomAccessIteratorIterator,
1319 typename RandomAccessIterator3,
1320 typename Comparator = std::less<
1321 typename std::iterator_traits<
1322 typename std::iterator_traits<RandomAccessIteratorIterator>
1323 ::value_type::first_type>::value_type> >
1324RandomAccessIterator3 multiway_merge(
1325 RandomAccessIteratorIterator seqs_begin,
1326 RandomAccessIteratorIterator seqs_end,
1327 RandomAccessIterator3 target,
1328 typename std::iterator_traits<
1329 typename std::iterator_traits<
1330 RandomAccessIteratorIterator>::value_type::first_type>::
1331 difference_type size,
1332 Comparator comp = Comparator(),
1334
1335 return multiway_merge_base</* Stable */ false, /* Sentinels */ false>(
1336 seqs_begin, seqs_end, target, size, comp, mwma);
1337}
1338
1339/*!
1340 * Stable sequential multi-way merge.
1341 *
1342 * \param seqs_begin Begin iterator of iterator pair input sequence.
1343 * \param seqs_end End iterator of iterator pair input sequence.
1344 * \param target Begin iterator out output sequence.
1345 * \param size Maximum size to merge.
1346 * \param comp Comparator.
1347 * \param mwma MultiwayMergeAlgorithm set to use.
1348 * \return End iterator of output sequence.
1349 */
1350template <
1351 typename RandomAccessIteratorIterator,
1352 typename RandomAccessIterator3,
1353 typename Comparator = std::less<
1354 typename std::iterator_traits<
1355 typename std::iterator_traits<RandomAccessIteratorIterator>
1356 ::value_type::first_type>::value_type> >
1357RandomAccessIterator3 stable_multiway_merge(
1358 RandomAccessIteratorIterator seqs_begin,
1359 RandomAccessIteratorIterator seqs_end,
1360 RandomAccessIterator3 target,
1361 typename std::iterator_traits<
1362 typename std::iterator_traits<
1363 RandomAccessIteratorIterator>::value_type::first_type>::
1364 difference_type size,
1365 Comparator comp = Comparator(),
1367
1368 return multiway_merge_base</* Stable */ true, /* Sentinels */ false>(
1369 seqs_begin, seqs_end, target, size, comp, mwma);
1370}
1371
1372/*!
1373 * Sequential multi-way merge with sentinels in sequences.
1374 *
1375 * \param seqs_begin Begin iterator of iterator pair input sequence.
1376 * \param seqs_end End iterator of iterator pair input sequence.
1377 * \param target Begin iterator out output sequence.
1378 * \param size Maximum size to merge.
1379 * \param comp Comparator.
1380 * \param mwma MultiwayMergeAlgorithm set to use.
1381 * \return End iterator of output sequence.
1382 */
1383template <
1384 typename RandomAccessIteratorIterator,
1385 typename RandomAccessIterator3,
1386 typename Comparator = std::less<
1387 typename std::iterator_traits<
1388 typename std::iterator_traits<RandomAccessIteratorIterator>
1389 ::value_type::first_type>::value_type> >
1390RandomAccessIterator3 multiway_merge_sentinels(
1391 RandomAccessIteratorIterator seqs_begin,
1392 RandomAccessIteratorIterator seqs_end,
1393 RandomAccessIterator3 target,
1394 typename std::iterator_traits<
1395 typename std::iterator_traits<
1396 RandomAccessIteratorIterator>::value_type::first_type>::
1397 difference_type size,
1398 Comparator comp = Comparator(),
1400
1401 return multiway_merge_base</* Stable */ false, /* Sentinels */ true>(
1402 seqs_begin, seqs_end, target, size, comp, mwma);
1403}
1404
1405/*!
1406 * Stable sequential multi-way merge with sentinels in sequences.
1407 *
1408 * \param seqs_begin Begin iterator of iterator pair input sequence.
1409 * \param seqs_end End iterator of iterator pair input sequence.
1410 * \param target Begin iterator out output sequence.
1411 * \param size Maximum size to merge.
1412 * \param comp Comparator.
1413 * \param mwma MultiwayMergeAlgorithm set to use.
1414 * \return End iterator of output sequence.
1415 */
1416template <
1417 typename RandomAccessIteratorIterator,
1418 typename RandomAccessIterator3,
1419 typename Comparator = std::less<
1420 typename std::iterator_traits<
1421 typename std::iterator_traits<RandomAccessIteratorIterator>
1422 ::value_type::first_type>::value_type> >
1424 RandomAccessIteratorIterator seqs_begin,
1425 RandomAccessIteratorIterator seqs_end,
1426 RandomAccessIterator3 target,
1427 typename std::iterator_traits<
1428 typename std::iterator_traits<
1429 RandomAccessIteratorIterator>::value_type::first_type>::
1430 difference_type size,
1431 Comparator comp = Comparator(),
1433
1434 return multiway_merge_base</* Stable */ true, /* Sentinels */ true>(
1435 seqs_begin, seqs_end, target, size, comp, mwma);
1436}
1437
1438//! \}
1439
1440} // namespace tlx
1441
1442#endif // !TLX_ALGORITHM_MULTIWAY_MERGE_HEADER
1443
1444/******************************************************************************/
Simpler non-growing vector without initialization.
Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all compariso...
friend bool operator<=(self_type &bi1, self_type &bi2)
Compare two elements referenced by guarded iterators.
typename std::iterator_traits< RandomAccessIterator >::value_type value_type
Value type of the iterator.
value_type & operator*()
Dereference operator.
RandomAccessIterator end_
End iterator of the sequence.
RandomAccessIterator current
Current iterator position.
friend bool operator<(self_type &bi1, self_type &bi2)
Compare two elements referenced by guarded iterators.
RandomAccessIterator & iterator()
Convert to wrapped iterator.
self_type & operator++()
Pre-increment operator.
guarded_iterator(RandomAccessIterator begin, RandomAccessIterator end, Comparator &comp)
Constructor.
friend bool operator<=(self_type &bi1, self_type &bi2)
Compare two elements referenced by unguarded iterators.
typename std::iterator_traits< RandomAccessIterator >::value_type value_type
Value type of the iterator.
value_type & operator*()
Dereference operator.
unguarded_iterator(RandomAccessIterator begin, RandomAccessIterator, Comparator &comp)
Constructor.
RandomAccessIterator current
Current iterator position.
friend bool operator<(self_type &bi1, self_type &bi2)
Compare two elements referenced by unguarded iterators.
RandomAccessIterator & iterator()
Convert to wrapped iterator.
self_type & operator++()
Pre-increment operator.
RandomAccessIterator3 multiway_merge(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
Sequential multi-way merge.
RandomAccessIterator3 stable_multiway_merge(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
Stable sequential multi-way merge.
RandomAccessIterator3 multiway_merge_base(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
Sequential multi-way merging switch.
RandomAccessIterator3 multiway_merge_sentinels(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
Sequential multi-way merge with sentinels in sequences.
MultiwayMergeAlgorithm
Different merging algorithms: bubblesort-alike, loser-tree variants, enum sentinel.
RandomAccessIterator3 stable_multiway_merge_sentinels(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp=Comparator(), MultiwayMergeAlgorithm mwma=MWMA_ALGORITHM_DEFAULT)
Stable sequential multi-way merge with sentinels in sequences.
OutputIterator merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, DiffType max_size, Comparator comp)
Merge routine being able to merge only the max_size smallest elements.
@ MWMA_ALGORITHM_DEFAULT
@ MWMA_LOSER_TREE_SENTINEL
@ MWMA_ALGORITHM_LAST
@ MWMA_LOSER_TREE
@ MWMA_LOSER_TREE_COMBINED
#define TLX_UNLIKELY(c)
Definition: likely.hpp:24
std::vector< std::string > split(char sep, const std::string &str, std::string::size_type limit)
Split the given string at each separator character into distinct substrings.
Definition: split.cpp:20
#define TLX_DECISION(a, b, c, d)
#define TLX_STOPS(i)
#define TLX_MERGE4CASE(a, b, c, d, c0, c1, c2)
#define TLX_MERGE3CASE(a, b, c, c0, c1)
#define TLX_POS(i)
RandomAccessIterator3 multiway_merge_loser_tree_combined(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
std::iterator_traits< typenamestd::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type prepare_unguarded(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp, int &min_sequence)
Prepare a set of sequences to be merged without a (end) guard.
RandomAccessIterator3 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
Multi-way merging procedure for a high branching factor, guarded case.
RandomAccessIterator3 multiway_merge_3_variant(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
Highly efficient 3-way merging procedure.
std::iterator_traits< typenamestd::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type prepare_unguarded_sentinel(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp)
Prepare a set of sequences to be merged with a (end) guard (sentinel)
RandomAccessIterator3 multiway_merge_3_combined(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
RandomAccessIterator3 multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
Multi-way merging procedure for a high branching factor, unguarded case.
RandomAccessIterator3 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
Highly efficient 4-way merging procedure.
RandomAccessIterator3 multiway_merge_bubble(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
Basic multi-way merging procedure.
RandomAccessIterator3 multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
std::iterator_traits< typenameRandomAccessIteratorPair::first_type >::difference_type iterpair_size(const RandomAccessIteratorPair &p)
Size of a sequence described by a pair of iterators.
RandomAccessIterator3 multiway_merge_4_combined(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, Comparator comp)
void unused(Types &&...)
Definition: unused.hpp:20