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

TLX_DECISION

#define TLX_DECISION	(		a,
			b,
			c,
			d
	)

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().

TLX_MERGE3CASE

#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().

TLX_MERGE4CASE

#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().

TLX_POS

#define TLX_POS

(

i

)

seqs_begin[(i)].first

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

TLX_STOPS

#define TLX_STOPS

(

i

)

seqs_begin[(i)].second

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