Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
multiway_merge.hpp File Reference
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <vector>
#include <tlx/algorithm/merge_advance.hpp>
#include <tlx/container/loser_tree.hpp>
#include <tlx/container/simple_vector.hpp>
#include <tlx/unused.hpp>
+ Include dependency graph for multiway_merge.hpp:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  guarded_iterator< RandomAccessIterator, Comparator >
 Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. More...
 
class  unguarded_iterator< RandomAccessIterator, Comparator >
 

Namespaces

 tlx
 
 tlx::multiway_merge_detail
 

Macros

#define TLX_DECISION(a, b, c, d)
 
#define TLX_MERGE3CASE(a, b, c, c0, c1)
 
#define TLX_MERGE4CASE(a, b, c, d, c0, c1, c2)
 
#define TLX_POS(i)   seqs_begin[(i)].first
 
#define TLX_STOPS(i)   seqs_begin[(i)].second
 

Enumerations

enum  MultiwayMergeAlgorithm {
  MWMA_LOSER_TREE, MWMA_LOSER_TREE_COMBINED, MWMA_LOSER_TREE_SENTINEL, MWMA_BUBBLE,
  MWMA_ALGORITHM_LAST, MWMA_ALGORITHM_DEFAULT = MWMA_LOSER_TREE_COMBINED
}
 Different merging algorithms: bubblesort-alike, loser-tree variants, enum sentinel. More...
 

Functions

template<typename RandomAccessIteratorPair >
std::iterator_traits< typename
RandomAccessIteratorPair::first_type >
::difference_type 
iterpair_size (const RandomAccessIteratorPair &p)
 Size of a sequence described by a pair of iterators. More...
 
template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
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. More...
 
template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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)
 
template<template< typename RAI, typename C > class Iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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. More...
 
template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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)
 
template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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. More...
 
template<bool Stable, bool Sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
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. More...
 
template<bool Stable, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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. More...
 
template<typename LoserTreeType , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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. More...
 
template<bool Stable, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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)
 
template<bool Stable, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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)
 
template<typename LoserTreeType , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator >
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. More...
 
template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
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. More...
 
template<bool Stable, typename RandomAccessIteratorIterator , typename Comparator >
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. More...
 
template<typename RandomAccessIteratorIterator , typename Comparator >
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) More...
 
template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
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. More...
 
template<typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename Comparator = std::less< typename std::iterator_traits< typename std::iterator_traits<RandomAccessIteratorIterator> ::value_type::first_type>::value_type>>
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. More...
 

Macro Definition Documentation

#define TLX_DECISION (   a,
  b,
  c,
 
)
Value:
do { \
if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \
if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \
if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \
goto s ## a ## b ## c ## d; \
} \
while (0)

Referenced by tlx::multiway_merge_detail::multiway_merge_4_variant().

#define TLX_MERGE3CASE (   a,
  b,
  c,
  c0,
  c1 
)
Value:
s ## a ## b ## c: \
*target = *seq ## a; \
++target; \
--size; \
++seq ## a; \
if (size == 0) goto finish; \
if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \
if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \
goto s ## b ## c ## a;

Referenced by tlx::multiway_merge_detail::multiway_merge_3_variant().

#define TLX_MERGE4CASE (   a,
  b,
  c,
  d,
  c0,
  c1,
  c2 
)
Value:
s ## a ## b ## c ## d: \
*target = *seq ## a; \
++target; \
--size; \
++seq ## a; \
if (size == 0) goto finish; \
if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \
if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \
if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \
goto s ## b ## c ## d ## a;

Referenced by tlx::multiway_merge_detail::multiway_merge_4_variant().

#define TLX_POS (   i)    seqs_begin[(i)].first
#define TLX_STOPS (   i)    seqs_begin[(i)].second