tlx
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>

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_MERGE3CASE(a, b, c, c0, c1)
 
#define TLX_DECISION(a, b, c, d)
 
#define TLX_MERGE4CASE(a, b, c, d, c0, c1, c2)
 
#define TLX_POS(i)
 
#define TLX_STOPS(i)
 

Enumerations

enum  MultiwayMergeAlgorithm {
  MWMA_LOSER_TREE, MWMA_LOSER_TREE_COMBINED, MWMA_LOSER_TREE_SENTINEL, MWMA_BUBBLE,
  MWMA_ALGORITHM_LAST, MWMA_ALGORITHM_DEFAULT
}
 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<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<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_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_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<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<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<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<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<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<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 = 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 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<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,
 
)
#define TLX_MERGE3CASE (   a,
  b,
  c,
  c0,
  c1 
)
#define TLX_MERGE4CASE (   a,
  b,
  c,
  d,
  c0,
  c1,
  c2 
)
#define TLX_POS (   i)
#define TLX_STOPS (   i)