tlx::multiway_merge_detail Namespace Reference

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

Functions
template<typename DiffType , typename DiffTypeOutputIterator >
DiffTypeOutputIterator	equally_split (DiffType n, size_t p, DiffTypeOutputIterator s)
	Split a sequence into parts of almost equal size. More...
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 >
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, 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<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...

Function Documentation

equally_split()

DiffTypeOutputIterator tlx::multiway_merge_detail::equally_split	(	DiffType	n,
		size_t	p,
		DiffTypeOutputIterator	s
	)

Split a sequence into parts of almost equal size.

The resulting sequence s of length p+1 contains the splitting positions when splitting the range [0,n) into parts of almost equal size (plus minus 1). The first entry is 0, the last one n. There may result empty parts.

Parameters

n	Number of elements
p	Number of parts
s	Splitters

Returns

End of splitter sequence, i. e. s+p+1

Definition at line 57 of file multiway_merge_splitting.hpp.

References tlx::split().

Referenced by tlx::parallel_mergesort_detail::determine_samples(), and tlx::multiway_merge_exact_splitting().

iterpair_size()

std::iterator_traits< typename RandomAccessIteratorPair::first_type >::difference_type tlx::multiway_merge_detail::iterpair_size

(

const RandomAccessIteratorPair &

p

)

Size of a sequence described by a pair of iterators.

Definition at line 44 of file multiway_merge.hpp.

Referenced by multiway_merge_3_combined(), multiway_merge_4_combined(), multiway_merge_bubble(), multiway_merge_loser_tree(), multiway_merge_loser_tree_combined(), and multiway_merge_loser_tree_unguarded().

multiway_merge_3_combined()

RandomAccessIterator3 tlx::multiway_merge_detail::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
	)

Definition at line 453 of file multiway_merge.hpp.

References guarded_iterator< RandomAccessIterator, Comparator >::iterator(), iterpair_size(), tlx::merge_advance(), and min().

Referenced by tlx::multiway_merge_base().

multiway_merge_3_variant()

RandomAccessIterator3 tlx::multiway_merge_detail::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.

Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into labels in C++).

This works well for merging up to 3 sequences.

Note that making the merging stable does not come at a performance hit.

Whether the merging is done guarded or unguarded is selected by the used iterator class.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.

Returns

End iterator of output sequence.

Definition at line 374 of file multiway_merge.hpp.

References TLX_MERGE3CASE, and tlx::unused().

multiway_merge_4_combined()

RandomAccessIterator3 tlx::multiway_merge_detail::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
	)

Definition at line 655 of file multiway_merge.hpp.

References iterpair_size(), and min().

Referenced by tlx::multiway_merge_base().

multiway_merge_4_variant()

RandomAccessIterator3 tlx::multiway_merge_detail::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.

Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into goto labels in C++).

This works well for merging up to 4 sequences.

Note that making the merging stable does not come at a performance hit.

Whether the merging is done guarded or unguarded is selected by the used iterator class.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.

Returns

End iterator of output sequence.

Definition at line 548 of file multiway_merge.hpp.

References TLX_DECISION, TLX_MERGE4CASE, and tlx::unused().

multiway_merge_bubble()

RandomAccessIterator3 tlx::multiway_merge_detail::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.

The head elements are kept in a sorted array, new heads are inserted linearly.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.

Template Parameters

Stable

Stable merging incurs a performance penalty.

Returns

End iterator of output sequence.

Definition at line 728 of file multiway_merge.hpp.

References iterpair_size(), tlx::swap(), TLX_POS, and TLX_STOPS.

multiway_merge_loser_tree()

RandomAccessIterator3 tlx::multiway_merge_detail::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.

The head elements are kept in a loser tree.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.

Template Parameters

Stable

Stable merging incurs a performance penalty.

Returns

End iterator of output sequence.

Definition at line 915 of file multiway_merge.hpp.

References iterpair_size(), TLX_UNLIKELY, and gen_data::x.

Referenced by tlx::multiway_merge_base(), and multiway_merge_loser_tree_combined().

multiway_merge_loser_tree_combined()

RandomAccessIterator3 tlx::multiway_merge_detail::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
	)

Definition at line 1073 of file multiway_merge.hpp.

References iterpair_size(), min(), multiway_merge_loser_tree(), and multiway_merge_loser_tree_unguarded().

multiway_merge_loser_tree_sentinel()

RandomAccessIterator3 tlx::multiway_merge_detail::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
	)

Definition at line 1125 of file multiway_merge.hpp.

References multiway_merge_loser_tree_unguarded().

multiway_merge_loser_tree_unguarded()

RandomAccessIterator3 tlx::multiway_merge_detail::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.

The head elements are kept in a loser tree.

Parameters

seqs_begin	Begin iterator of iterator pair input sequence.
seqs_end	End iterator of iterator pair input sequence.
target	Begin iterator out output sequence.
size	Maximum size to merge.
comp	Comparator.

Template Parameters

Stable

Stable merging incurs a performance penalty.

Returns

End iterator of output sequence.

Precondition

No input will run out of elements during the merge.

Definition at line 1001 of file multiway_merge.hpp.

References iterpair_size(), and min().

Referenced by multiway_merge_loser_tree_combined(), and multiway_merge_loser_tree_sentinel().

prepare_unguarded()

std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator>::value_type::first_type>::difference_type tlx::multiway_merge_detail::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.

Parameters

seqs_begin
seqs_end
comp
min_sequence

Template Parameters

Stable

Precondition

(seqs_end - seqs_begin > 0)

Definition at line 232 of file multiway_merge.hpp.

References min(), and tlx::split().

prepare_unguarded_sentinel()

std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator>::value_type::first_type>::difference_type tlx::multiway_merge_detail::prepare_unguarded_sentinel	(	RandomAccessIteratorIterator	seqs_begin,
		RandomAccessIteratorIterator	seqs_end,
		Comparator	comp
	)

Prepare a set of sequences to be merged with a (end) guard (sentinel)

Parameters

seqs_begin
seqs_end
comp

Definition at line 310 of file multiway_merge.hpp.

References tlx::split().