tlx
multiway_merge_splitting.hpp File Reference
#include <algorithm>
#include <vector>
#include <tlx/algorithm/multisequence_partition.hpp>
#include <tlx/simple_vector.hpp>

Go to the source code of this file.

Namespaces

 tlx
 
 tlx::multiway_merge_detail
 

Enumerations

enum  MultiwayMergeSplittingAlgorithm { MWMSA_SAMPLING, MWMSA_EXACT, MWMSA_LAST, MWMSA_DEFAULT }
 Different splitting strategies for sorting/merging: by sampling, exact. More...
 

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<bool Stable, typename RandomAccessIteratorIterator , typename Comparator >
void multiway_merge_sampling_splitting (const RandomAccessIteratorIterator &seqs_begin, const RandomAccessIteratorIterator &seqs_end, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type total_size, Comparator comp, std::vector< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type > *chunks, const size_t num_threads, const size_t merge_oversampling)
 Splitting method for parallel multi-way merge routine: use sampling and binary search for in-exact splitting. More...
 
template<bool Stable, typename RandomAccessIteratorIterator , typename Comparator >
void multiway_merge_exact_splitting (const RandomAccessIteratorIterator &seqs_begin, const RandomAccessIteratorIterator &seqs_end, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type size, typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::difference_type total_size, Comparator comp, std::vector< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type > *chunks, const size_t num_threads)
 Splitting method for parallel multi-way merge routine: use multisequence selection for exact splitting. More...