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,
			d
	)

#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

)