tlx
tlx::sort_strings_detail Namespace Reference

Classes

class  GenericCharStringSet
 Class implementing StringSet concept for char* and unsigned char* strings. More...
 
class  GenericCharStringSetTraits
 Traits class implementing StringSet concept for char* and unsigned char* strings. More...
 
struct  PerfectTreeCalculations
 Class to transform in-order to level-order indexes in a perfect binary tree. More...
 
class  PS5BigSortStep
 PS5BigSortStep Out-of-Place Parallel Sample Sort with Separate Jobs. More...
 
class  PS5Context
 Parallel Super Scalar String Sample Sort Context. More...
 
class  PS5ParametersDefault
 Parallel Super Scalar String Sample Sort Parameter Struct. More...
 
class  PS5SmallsortJob
 SampleSort: Non-Recursive In-Place Sequential Sample Sort for Small Sorts. More...
 
class  PS5SortStep
 PS5SortStep Top-Level Class to Keep Track of Substeps. More...
 
struct  RadixStep_CE0
 
struct  RadixStep_CE2
 
struct  RadixStep_CE3
 
struct  RadixStep_CI2
 
struct  RadixStep_CI3
 
class  SSClassifyEqualUnroll
 Sample Sort Classification Tree Unrolled with Equal Comparisons. More...
 
class  SSClassifyTreeCalcUnrollInterleave
 Sample Sort Classification Tree Unrolled, Interleaved, and with Perfect Tree Index Calculations. More...
 
class  SSClassifyTreeUnrollInterleave
 Sample Sort Classification Tree Unrolled and Interleaved. More...
 
class  SSTreeBuilderLevelOrder
 Recursive TreeBuilder for full-descent and unrolled variants, constructs only a level-order binary tree of splitters. More...
 
class  SSTreeBuilderPreAndLevelOrder
 Recursive TreeBuilder for full-descent and unrolled variants, constructs a both a pre-order and level-order array of splitters and the corresponding LCPs. More...
 
class  StdStringSet
 Class implementing StringSet concept for arrays of std::string objects. More...
 
class  StdStringSetTraits
 Class implementing StringSet concept for a std::string objects. More...
 
class  StringLcpPtr
 Objectified string and LCP array pointer arrays. More...
 
class  StringPtr
 Objectified string array pointer array. More...
 
class  StringSetBase
 Base class for common string set functions, included via CRTP. More...
 
class  StringShadowLcpPtr
 Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers. More...
 
class  StringShadowPtr
 Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers. More...
 
class  StringSuffixSet
 Class implementing StringSet concept for suffix sorting indexes of a std::string text object. More...
 
class  StringSuffixSetTraits
 Class implementing StringSet concept for suffix sorting indexes of a std::string text object. More...
 
class  UPtrStdStringSet
 Class implementing StringSet concept for a std::vector containing std::string objects. More...
 
class  UPtrStdStringSetTraits
 Class implementing StringSet concept for a std::unique_ptr<std::string objects, which are non-copyable. More...
 

Typedefs

typedef GenericCharStringSet< char > CharStringSet
 
typedef GenericCharStringSet< unsigned char > UCharStringSet
 
typedef GenericCharStringSet< const char > CCharStringSet
 
typedef GenericCharStringSet< const unsigned char > CUCharStringSet
 

Functions

template<typename StringPtr >
static enable_if<!StringPtr::with_lcp, void >::type insertion_sort (const StringPtr &strptr, size_t depth, size_t)
 Generic insertion sort for abstract string sets. More...
 
template<typename StringPtr >
static enable_if< StringPtr::with_lcp, void >::type insertion_sort (const StringPtr &strptr, size_t depth, size_t)
 LCP insertion sort for abstract string sets. More...
 
template<typename StringSet >
static void vec_swap (typename StringSet::Iterator a, typename StringSet::Iterator b, size_t n)
 
template<typename StringSet >
static StringSet::Iterator med3func (const StringSet &ss, typename StringSet::Iterator a, typename StringSet::Iterator b, typename StringSet::Iterator c, size_t depth)
 
template<typename StringPtr >
static void multikey_quicksort (const StringPtr &strptr, size_t depth, size_t memory)
 Generic multikey quicksort for strings. More...
 
template<typename KeyType >
static unsigned char lcpKeyType (const KeyType &a, const KeyType &b)
 LCP calculation of Splitter Strings. More...
 
template<typename KeyType >
static unsigned char lcpKeyDepth (const KeyType &a)
 
template<typename KeyType >
static unsigned char getCharAtDepth (const KeyType &a, unsigned char d)
 return the d-th character in the (swapped) key More...
 
template<size_t bktnum, typename Context , typename Classify , typename StringPtr , typename BktSizeType >
void ps5_sample_sort_lcp (const Context &ctx, const Classify &classifier, const StringPtr &strptr, size_t depth, const BktSizeType *bkt)
 LCP Calculation for Finished Sample Sort Steps. More...
 
template<typename PS5Parameters , typename StringPtr >
void parallel_sample_sort_base (const StringPtr &strptr, size_t depth)
 Main Parallel Sample Sort Function. See below for more convenient wrappers. More...
 
template<typename PS5Parameters , typename StringPtr >
enable_if<!StringPtr::with_lcp, void >::type parallel_sample_sort_params (const StringPtr &strptr, size_t depth, size_t memory=0)
 Parallel Sample Sort Function for a generic StringSet, this allocates the shadow array for flipping. More...
 
template<typename PS5Parameters , typename StringPtr >
enable_if< StringPtr::with_lcp, void >::type parallel_sample_sort_params (const StringPtr &strptr, size_t depth, size_t memory=0)
 Parallel Sample Sort Function for a generic StringSet with LCPs, this allocates the shadow array for flipping. More...
 
template<typename StringPtr >
void parallel_sample_sort (const StringPtr &strptr, size_t depth, size_t memory)
 Parallel Sample Sort Function with default parameter size for a generic StringSet. More...
 
template<typename StringShadowPtr >
static void radixsort_CE0_loop (const StringShadowPtr &strptr, size_t depth, size_t memory)
 
template<typename StringPtr >
static void radixsort_CE0 (const StringPtr &strptr, size_t depth, size_t memory)
 Adapter method to allocate shadow array if needed. More...
 
template<typename StringPtr >
static void radixsort_CI3 (const StringPtr &strptr, uint16_t *charcache, size_t depth, size_t memory)
 
template<typename StringShadowPtr >
static void radixsort_CE2_loop (const StringShadowPtr &strptr, uint8_t *charcache, size_t depth, size_t memory)
 
template<typename StringPtr >
static void radixsort_CE2 (const StringPtr &strptr, size_t depth, size_t memory)
 
template<typename StringShadowPtr >
static void radixsort_CE3_loop (const StringShadowPtr &strptr, uint16_t *charcache, size_t depth, size_t memory)
 
template<typename StringPtr >
static void radixsort_CE3 (const StringPtr &strptr, size_t depth, size_t memory)
 
template<typename StringPtr >
static void radixsort_CI2 (const StringPtr &strptr, uint8_t *charcache, size_t depth, size_t memory)
 
template<typename StringPtr >
static void radixsort_CI2 (const StringPtr &strptr, size_t depth, size_t memory)
 
template<typename StringPtr >
static void radixsort_CI3 (const StringPtr &strptr, size_t depth, size_t memory)
 
template<typename Type >
static std::string to_binary (Type v, const size_t width=(8 *sizeof(Type)))
 represent binary digits of large integer datatypes More...
 
static void perfect_tree_calculations_self_verify ()
 
template<typename Type , typename StringSet >
enable_if< sizeof(Type)==4, uint32_t >::type get_key (const StringSet &strset, const typename StringSet::String &s, size_t depth)
 
template<typename Type , typename StringSet >
enable_if< sizeof(Type)==8, uint64_t >::type get_key (const StringSet &strset, const typename StringSet::String &s, size_t depth)
 
template<typename Type , typename StringSet >
Type get_key_at (const StringSet &strset, size_t idx, size_t depth)
 

Variables

static const size_t g_inssort_threshold
 

Typedef Documentation

typedef GenericCharStringSet<const char> CCharStringSet

Definition at line 364 of file string_set.hpp.

Definition at line 361 of file string_set.hpp.

typedef GenericCharStringSet<const unsigned char> CUCharStringSet

Definition at line 365 of file string_set.hpp.

typedef GenericCharStringSet<unsigned char> UCharStringSet

Definition at line 362 of file string_set.hpp.

Function Documentation

enable_if<sizeof(Type) == 4, uint32_t>::type tlx::sort_strings_detail::get_key ( const StringSet &  strset,
const typename StringSet::String &  s,
size_t  depth 
)
inline

Definition at line 248 of file string_set.hpp.

enable_if<sizeof(Type) == 8, uint64_t>::type tlx::sort_strings_detail::get_key ( const StringSet &  strset,
const typename StringSet::String &  s,
size_t  depth 
)
inline

Definition at line 256 of file string_set.hpp.

Type tlx::sort_strings_detail::get_key_at ( const StringSet &  strset,
size_t  idx,
size_t  depth 
)
inline

Definition at line 263 of file string_set.hpp.

static unsigned char tlx::sort_strings_detail::getCharAtDepth ( const KeyType &  a,
unsigned char  d 
)
inlinestatic

return the d-th character in the (swapped) key

Definition at line 164 of file parallel_sample_sort.hpp.

static enable_if<!StringPtr::with_lcp, void>::type tlx::sort_strings_detail::insertion_sort ( const StringPtr strptr,
size_t  depth,
size_t   
)
inlinestatic

Generic insertion sort for abstract string sets.

This method only requires O(1) additional memory for sorting n strings, but runs in time O(nD).

Definition at line 35 of file insertion_sort.hpp.

static enable_if<StringPtr::with_lcp, void>::type tlx::sort_strings_detail::insertion_sort ( const StringPtr strptr,
size_t  depth,
size_t   
)
inlinestatic

LCP insertion sort for abstract string sets.

Enabled via SFINAE if StringPtr::with_lcp is true. This method only requires O(1) additional memory for sorting n strings, and runs in time O(n^2 + D).

Definition at line 82 of file insertion_sort.hpp.

static unsigned char tlx::sort_strings_detail::lcpKeyDepth ( const KeyType &  a)
inlinestatic

Definition at line 156 of file parallel_sample_sort.hpp.

static unsigned char tlx::sort_strings_detail::lcpKeyType ( const KeyType &  a,
const KeyType &  b 
)
inlinestatic

LCP calculation of Splitter Strings.

Definition at line 149 of file parallel_sample_sort.hpp.

static StringSet::Iterator tlx::sort_strings_detail::med3func ( const StringSet &  ss,
typename StringSet::Iterator  a,
typename StringSet::Iterator  b,
typename StringSet::Iterator  c,
size_t  depth 
)
inlinestatic

Definition at line 47 of file multikey_quicksort.hpp.

static void tlx::sort_strings_detail::multikey_quicksort ( const StringPtr strptr,
size_t  depth,
size_t  memory 
)
inlinestatic

Generic multikey quicksort for strings.

Based on multikey quicksort, a quick sort algorithm for arrays of character strings by Bentley and Sedgewick. This method requires up to O(maxlcp) memory due to the recursion stack and it runs in expected time O(D + n log n) and worst-case time O(D + n^2).

J. Bentley and R. Sedgewick. Fast algorithms for sorting and searching strings. In Proceedings of 8th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.

Definition at line 74 of file multikey_quicksort.hpp.

void tlx::sort_strings_detail::parallel_sample_sort ( const StringPtr strptr,
size_t  depth,
size_t  memory 
)

Parallel Sample Sort Function with default parameter size for a generic StringSet.

Definition at line 1510 of file parallel_sample_sort.hpp.

void tlx::sort_strings_detail::parallel_sample_sort_base ( const StringPtr strptr,
size_t  depth 
)

Main Parallel Sample Sort Function. See below for more convenient wrappers.

Definition at line 1420 of file parallel_sample_sort.hpp.

enable_if<!StringPtr::with_lcp, void>::type tlx::sort_strings_detail::parallel_sample_sort_params ( const StringPtr strptr,
size_t  depth,
size_t  memory = 0 
)

Parallel Sample Sort Function for a generic StringSet, this allocates the shadow array for flipping.

Definition at line 1464 of file parallel_sample_sort.hpp.

enable_if<StringPtr::with_lcp, void>::type tlx::sort_strings_detail::parallel_sample_sort_params ( const StringPtr strptr,
size_t  depth,
size_t  memory = 0 
)

Parallel Sample Sort Function for a generic StringSet with LCPs, this allocates the shadow array for flipping.

Definition at line 1487 of file parallel_sample_sort.hpp.

static void tlx::sort_strings_detail::perfect_tree_calculations_self_verify ( )
inlinestatic

Definition at line 103 of file sample_sort_tools.hpp.

void tlx::sort_strings_detail::ps5_sample_sort_lcp ( const Context &  ctx,
const Classify &  classifier,
const StringPtr strptr,
size_t  depth,
const BktSizeType *  bkt 
)

LCP Calculation for Finished Sample Sort Steps.

Definition at line 206 of file parallel_sample_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE0 ( const StringPtr strptr,
size_t  depth,
size_t  memory 
)
inlinestatic

Adapter method to allocate shadow array if needed.

Definition at line 166 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE0_loop ( const StringShadowPtr strptr,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 112 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE2 ( const StringPtr strptr,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 319 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE2_loop ( const StringShadowPtr strptr,
uint8_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 267 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE3 ( const StringPtr strptr,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 502 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CE3_loop ( const StringShadowPtr strptr,
uint16_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 430 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CI2 ( const StringPtr strptr,
uint8_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 616 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CI2 ( const StringPtr strptr,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 673 of file radix_sort.hpp.

static void radixsort_CI3 ( const StringPtr strptr,
uint16_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 788 of file radix_sort.hpp.

static void tlx::sort_strings_detail::radixsort_CI3 ( const StringPtr strptr,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 861 of file radix_sort.hpp.

static std::string tlx::sort_strings_detail::to_binary ( Type  v,
const size_t  width = (8 * sizeof(Type)) 
)
inlinestatic

represent binary digits of large integer datatypes

Definition at line 40 of file sample_sort_tools.hpp.

static void tlx::sort_strings_detail::vec_swap ( typename StringSet::Iterator  a,
typename StringSet::Iterator  b,
size_t  n 
)
inlinestatic

Definition at line 40 of file multikey_quicksort.hpp.

Variable Documentation

const size_t g_inssort_threshold
static

Definition at line 42 of file radix_sort.hpp.