tlx
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 
32 namespace tlx {
33 
34 //! \addtogroup tlx_algorithm
35 //! \{
36 
37 namespace multiway_merge_detail {
38 
39 //! Size of a sequence described by a pair of iterators.
40 template <typename RandomAccessIteratorPair>
41 typename std::iterator_traits<
42  typename RandomAccessIteratorPair::first_type
43  >::difference_type
44 iterpair_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 */
53 template <typename RandomAccessIterator, typename Comparator>
55 {
56 public:
57  //! Our own type
59 
60  //! Value type of the iterator
61  using value_type =
62  typename std::iterator_traits<RandomAccessIterator>::value_type;
63 
64 protected:
65  //! Current iterator position.
66  RandomAccessIterator current;
67  //! End iterator of the sequence.
68  RandomAccessIterator end_;
69  //! Comparator.
70  Comparator& comp_;
71 
72 public:
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 
139 template <typename RandomAccessIterator, typename Comparator>
141 {
142 public:
143  //! Our own type
145 
146  //! Value type of the iterator
147  using value_type =
148  typename std::iterator_traits<RandomAccessIterator>::value_type;
149 
150 protected:
151  //! Current iterator position.
152  RandomAccessIterator current;
153  //! Comparator.
154  Comparator& comp_;
155 
156 public:
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  */
225 template <
226  bool Stable,
227  typename RandomAccessIteratorIterator,
228  typename Comparator>
229 typename 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  */
306 template <typename RandomAccessIteratorIterator, typename Comparator>
307 typename 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  */
369 template <
370  template <typename RAI, typename C> class Iterator,
371  typename RandomAccessIteratorIterator,
372  typename RandomAccessIterator3,
373  typename Comparator>
374 RandomAccessIterator3 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 
441 finish:
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 
449 template <
450  typename RandomAccessIteratorIterator,
451  typename RandomAccessIterator3,
452  typename Comparator>
453 RandomAccessIterator3 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  */
543 template <
544  template <typename RAI, typename C> class iterator,
545  typename RandomAccessIteratorIterator,
546  typename RandomAccessIterator3,
547  typename Comparator>
548 RandomAccessIterator3 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 
642 finish:
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 
651 template <
652  typename RandomAccessIteratorIterator,
653  typename RandomAccessIterator3,
654  typename Comparator>
655 RandomAccessIterator3 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  */
723 template <
724  bool Stable,
725  typename RandomAccessIteratorIterator,
726  typename RandomAccessIterator3,
727  typename Comparator>
728 RandomAccessIterator3 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  */
910 template <
911  typename LoserTreeType,
912  typename RandomAccessIteratorIterator,
913  typename RandomAccessIterator3,
914  typename Comparator>
915 RandomAccessIterator3 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  */
996 template <
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 
1068 template <
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 
1120 template <
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  */
1172 };
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  */
1189 template <
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> >
1198 RandomAccessIterator3 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)
1219  mwma = MWMA_LOSER_TREE_COMBINED;
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  */
1317 template <
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> >
1324 RandomAccessIterator3 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  */
1350 template <
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> >
1357 RandomAccessIterator3 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  */
1383 template <
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> >
1390 RandomAccessIterator3 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  */
1416 template <
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> >
1423 RandomAccessIterator3 stable_multiway_merge_sentinels(
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 /******************************************************************************/
std::iterator_traits< typename RandomAccessIteratorPair::first_type >::difference_type iterpair_size(const RandomAccessIteratorPair &p)
Size of a sequence described by a pair of iterators.
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.
#define TLX_DECISION(a, b, c, d)
#define TLX_MERGE4CASE(a, b, c, d, c0, c1, c2)
#define TLX_MERGE3CASE(a, b, c, c0, c1)
RandomAccessIterator end_
End iterator of the sequence.
RandomAccessIterator & iterator()
Convert to wrapped iterator.
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_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)
Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all compariso...
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(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.
Simpler non-growing vector without initialization.
MultiwayMergeAlgorithm
Different merging algorithms: bubblesort-alike, loser-tree variants, enum sentinel.
RandomAccessIterator current
Current iterator position.
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.
#define TLX_UNLIKELY(c)
Definition: likely.hpp:24
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.
unguarded_iterator(RandomAccessIterator begin, RandomAccessIterator, Comparator &comp)
Constructor.
value_type & operator*()
Dereference operator.
friend bool operator<(self_type &bi1, self_type &bi2)
Compare two elements referenced by guarded iterators.
guarded_iterator(RandomAccessIterator begin, RandomAccessIterator end, Comparator &comp)
Constructor.
void unused(Types &&...)
Definition: unused.hpp:20
#define TLX_POS(i)
std::iterator_traits< typename std::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)
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
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)
typename std::iterator_traits< RandomAccessIterator >::value_type value_type
Value type of the iterator.
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.
RandomAccessIterator current
Current iterator position.
static uint32_t min(uint32_t x, uint32_t y)
Definition: md5.cpp:32
std::iterator_traits< typename std::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.
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change) ...
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.
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_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)
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.
friend bool operator<=(self_type &bi1, self_type &bi2)
Compare two elements referenced by guarded iterators.
self_type & operator++()
Pre-increment operator.
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)
typename std::iterator_traits< RandomAccessIterator >::value_type value_type
Value type of the iterator.
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.
#define TLX_STOPS(i)
RandomAccessIterator & iterator()
Convert to wrapped iterator.