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

Function Documentation

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
nNumber of elements
pNumber of parts
sSplitters
Returns
End of splitter sequence, i. e. s+p+1

Definition at line 57 of file multiway_merge_splitting.hpp.

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.

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.

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
Returns
End iterator of output sequence.

Definition at line 374 of file multiway_merge.hpp.

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.

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
Returns
End iterator of output sequence.

Definition at line 548 of file multiway_merge.hpp.

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
Template Parameters
StableStable merging incurs a performance penalty.
Returns
End iterator of output sequence.

Definition at line 728 of file multiway_merge.hpp.

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
Template Parameters
StableStable merging incurs a performance penalty.
Returns
End iterator of output sequence.

Definition at line 915 of file multiway_merge.hpp.

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.

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.

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_beginBegin iterator of iterator pair input sequence.
seqs_endEnd iterator of iterator pair input sequence.
targetBegin iterator out output sequence.
sizeMaximum size to merge.
compComparator.
Template Parameters
StableStable 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.

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.

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.