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  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
 
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 StringPtr >
static enable_if
<!StringPtr::with_lcp, void >
::type 
insertion_sort (const StringPtr &strptr, size_t depth, size_t)
 
template<typename StringPtr >
static enable_if
< StringPtr::with_lcp, void >
::type 
insertion_sort (const StringPtr &strptr, 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 StringPtr >
static void multikey_quicksort (const StringPtr &strptr, size_t depth, size_t memory)
 Generic multikey quicksort for strings. More...
 
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 StringShadowPtr >
static void radixsort_CE0_loop (const StringShadowPtr &strptr, 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_CE2_loop (const StringShadowPtr &strptr, uint8_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 StringShadowPtr >
static void radixsort_CE3_loop (const StringShadowPtr &strptr, uint16_t *charcache, 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, uint16_t *charcache, size_t depth, size_t memory)
 
template<typename StringPtr >
static void radixsort_CI3 (const StringPtr &strptr, 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 271 of file string_set.hpp.

Definition at line 268 of file string_set.hpp.

typedef GenericCharStringSet<const unsigned char> CUCharStringSet

Definition at line 272 of file string_set.hpp.

typedef GenericCharStringSet<unsigned char> UCharStringSet

Definition at line 269 of file string_set.hpp.

Function Documentation

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.

References StringPtr< StringSet_ >::active(), TLX_LIKELY, and TLX_UNLIKELY.

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

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.

References StringPtr< StringSet_ >::active(), and StringPtr< StringSet_ >::set_lcp().

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.

Referenced by multikey_quicksort().

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.

References StringPtr< StringSet_ >::active(), insertion_sort(), med3func(), min(), StringPtr< StringSet_ >::set_lcp(), StringPtr< StringSet_ >::sub(), and tlx::swap().

Referenced by radixsort_CE0(), radixsort_CE0_loop(), radixsort_CE2_loop(), radixsort_CE3_loop(), radixsort_CI2(), and radixsort_CI3().

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.

References StringPtr< StringSet_ >::active(), StringPtr< StringSet_ >::add_shadow(), g_inssort_threshold, insertion_sort(), multikey_quicksort(), and radixsort_CE0_loop().

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.

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

Referenced by radixsort_CE0().

static void tlx::sort_strings_detail::radixsort_CE2 ( const StringPtr &  strptr,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CE2_loop ( const StringShadowPtr &  strptr,
uint8_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CE3 ( const StringPtr &  strptr,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CE3_loop ( const StringShadowPtr &  strptr,
uint16_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CI2 ( const StringPtr &  strptr,
uint8_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CI2 ( const StringPtr &  strptr,
size_t  depth,
size_t  memory 
)
inlinestatic
static void radixsort_CI3 ( const StringPtr &  strptr,
uint16_t *  charcache,
size_t  depth,
size_t  memory 
)
inlinestatic
static void tlx::sort_strings_detail::radixsort_CI3 ( const StringPtr &  strptr,
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 40 of file multikey_quicksort.hpp.

References tlx::swap().

Variable Documentation

const size_t g_inssort_threshold = 32
static