Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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  RadixStep_CE0
 
struct  RadixStep_CE2
 
struct  RadixStep_CE3
 
struct  RadixStep_CI2
 
struct  RadixStep_CI3
 
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  StringSetBase
 Base class for common string set functions, included via CRTP. More...
 
class  StringShadowPtr
 
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
< const char > 
CCharStringSet
 
typedef GenericCharStringSet
< char > 
CharStringSet
 
typedef GenericCharStringSet
< const unsigned char > 
CUCharStringSet
 
typedef GenericCharStringSet
< unsigned char > 
UCharStringSet
 

Functions

template<typename StringSet >
static void insertion_sort (const StringSet &ss, size_t depth, size_t)
 
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 StringSet >
static void multikey_quicksort (const StringSet &ss, size_t depth, size_t memory)
 Generic multikey quicksort for strings. More...
 
template<typename StringSet >
static void radixsort_CE0 (const StringSet &ss, size_t depth, size_t memory)
 
template<typename StringSet >
static void radixsort_CE2 (const StringShadowPtr< StringSet > &strptr, uint8_t *charcache, size_t depth, size_t memory)
 
template<typename StringSet >
static void radixsort_CE2 (const StringSet &ss, size_t depth, size_t memory)
 
template<typename StringSet >
static void radixsort_CE3 (const StringSet &ss, size_t depth, size_t memory)
 
template<typename StringSet >
static void radixsort_CI2 (const StringSet &ss, uint8_t *charcache, size_t depth, size_t memory)
 
template<typename StringSet >
static void radixsort_CI2 (const StringSet &ss, size_t depth, size_t memory)
 
template<typename StringSet >
static void radixsort_CI3 (const StringSet &ss, size_t depth, size_t memory)
 
template<typename StringSet >
static void vec_swap (typename StringSet::Iterator a, typename StringSet::Iterator b, size_t n)
 

Variables

static const size_t g_inssort_threshold = 32
 

Typedef Documentation

typedef GenericCharStringSet<const char> CCharStringSet

Definition at line 257 of file string_set.hpp.

Definition at line 254 of file string_set.hpp.

typedef GenericCharStringSet<const unsigned char> CUCharStringSet

Definition at line 258 of file string_set.hpp.

typedef GenericCharStringSet<unsigned char> UCharStringSet

Definition at line 255 of file string_set.hpp.

Function Documentation

static void tlx::sort_strings_detail::insertion_sort ( const StringSet &  ss,
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 28 of file insertion_sort.hpp.

References TLX_LIKELY, and TLX_UNLIKELY.

Referenced by multikey_quicksort(), radixsort_CE0(), radixsort_CE2(), radixsort_CE3(), radixsort_CI2(), and radixsort_CI3().

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 43 of file multikey_quicksort.hpp.

Referenced by multikey_quicksort().

static void tlx::sort_strings_detail::multikey_quicksort ( const StringSet &  ss,
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 70 of file multikey_quicksort.hpp.

References insertion_sort(), med3func(), min(), and tlx::swap().

Referenced by radixsort_CE0(), radixsort_CE2(), radixsort_CE3(), radixsort_CI2(), and radixsort_CI3().

static void tlx::sort_strings_detail::radixsort_CE0 ( const StringSet &  ss,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CE2 ( const StringShadowPtr< StringSet > &  strptr,
uint8_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CE2 ( const StringSet &  ss,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 252 of file radix_sort.hpp.

References g_inssort_threshold, insertion_sort(), and radixsort_CI3().

static void tlx::sort_strings_detail::radixsort_CE3 ( const StringSet &  ss,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CI2 ( const StringSet &  ss,
uint8_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CI2 ( const StringSet &  ss,
size_t  depth,
size_t  memory 
)
inlinestatic

Definition at line 529 of file radix_sort.hpp.

References g_inssort_threshold, insertion_sort(), and multikey_quicksort().

static void radixsort_CI3 ( const StringSet &  ss,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::vec_swap ( typename StringSet::Iterator  a,
typename StringSet::Iterator  b,
size_t  n 
)
inlinestatic

Definition at line 36 of file multikey_quicksort.hpp.

References tlx::swap().

Variable Documentation

const size_t g_inssort_threshold = 32
static