Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
examples::suffix_sorting Namespace Reference

Namespaces

 dc3_local
 
 dc7_local
 

Classes

struct  IndexChar
 
struct  IndexFlag
 
struct  IndexRank
 A pair (index, rank) More...
 
struct  IndexRankFlag
 

Enumerations

enum  Status : uint8_t {
  UNDECIDED = 0, UNIQUE = 1, FULLY_DISCARDED = 2, UNDECIDED = 0,
  UNIQUE = 1, FULLY_DISCARDED = 2
}
 
enum  Status : uint8_t {
  UNDECIDED = 0, UNIQUE = 1, FULLY_DISCARDED = 2, UNDECIDED = 0,
  UNIQUE = 1, FULLY_DISCARDED = 2
}
 

Functions

template<typename InputDIA , typename SuffixArrayDIA >
bool CheckSA (const InputDIA &input, const SuffixArrayDIA &suffix_array)
 
template<typename InputDIA , typename SuffixArrayDIA >
InputDIA ConstructBWT (const InputDIA &input, const SuffixArrayDIA &suffix_array, uint64_t input_size)
 
template<typename InputDIA , typename IndexDIA >
IndexDIA ConstructLCP (const InputDIA &input, const IndexDIA &, const InputDIA &bwt, uint64_t input_size)
 
template<typename InputDIA >
auto ConstructWaveletTree (const InputDIA &input_dia, const std::string &output_path)
 
template<typename InputDIA >
auto ConstructWaveletTree (const InputDIA &input_dia)
 
template<typename Index , typename InputDIA >
thrill::DIA< Index > DC3 (const InputDIA &input_dia, size_t input_size, size_t K)
 
template<typename Index , typename InputDIA >
DIA< Index > DC3 (const InputDIA &input_dia, size_t input_size, size_t K)
 
template DIA< common::uint40DC3< common::uint40 > (const DIA< uint8_t > &input_dia, size_t input_size, size_t K)
 
template DIA< uint32_t > DC3< uint32_t > (const DIA< uint8_t > &input_dia, size_t input_size, size_t K)
 
template DIA< uint64_t > DC3< uint64_t > (const DIA< uint8_t > &input_dia, size_t input_size, size_t K)
 
template<typename Index , typename InputDIA >
DIA< dc3_local::StringFragment
< Index, typename
InputDIA::ValueType > > 
DC3Recursive (const InputDIA &input_dia, size_t input_size, size_t K)
 
template<typename Index , typename InputDIA >
thrill::DIA< Index > DC7 (const InputDIA &input_dia, size_t input_size, size_t K)
 
template<typename Index , typename InputDIA >
DIA< Index > DC7 (const InputDIA &input_dia, size_t input_size, size_t K)
 
template DIA< common::uint40DC7< common::uint40 > (const DIA< uint8_t > &input_dia, size_t input_size, size_t K)
 
template DIA< uint32_t > DC7< uint32_t > (const DIA< uint8_t > &input_dia, size_t input_size, size_t K)
 
template DIA< uint64_t > DC7< uint64_t > (const DIA< uint8_t > &input_dia, size_t input_size, size_t K)
 
template<typename Index , typename InputDIA >
DIA< dc7_local::StringFragment
< Index, typename
InputDIA::ValueType > > 
DC7Recursive (const InputDIA &input_dia, size_t input_size, size_t K)
 
static bool IsDiffCover7 (size_t i)
 
template<typename Index , typename InputDIA >
thrill::DIA< Index > PrefixDoublingDiscarding (const InputDIA &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
DIA< Index > PrefixDoublingDiscarding (const InputDIA &input_dia, size_t input_size, bool packed)
 
template DIA< common::uint40PrefixDoublingDiscarding< common::uint40 > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint32_t > PrefixDoublingDiscarding< uint32_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint64_t > PrefixDoublingDiscarding< uint64_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
DIA< IndexRank< Index > > PrefixDoublingPack (const InputDIA &input_dia, size_t input_size, bool packed, size_t &iteration)
 take input and pack it into an array of Index characters More...
 
template<typename Index , typename InputDIA >
thrill::DIA< Index > PrefixDoublingSorting (const InputDIA &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
DIA< Index > PrefixDoublingSorting (const InputDIA &input_dia, size_t input_size, bool packed)
 
template DIA< common::uint40PrefixDoublingSorting< common::uint40 > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint32_t > PrefixDoublingSorting< uint32_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint64_t > PrefixDoublingSorting< uint64_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
thrill::DIA< Index > PrefixDoublingWindow (const InputDIA &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
DIA< Index > PrefixDoublingWindow (const InputDIA &input_dia, size_t input_size, bool packed)
 
template DIA< common::uint40PrefixDoublingWindow< common::uint40 > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint32_t > PrefixDoublingWindow< uint32_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint64_t > PrefixDoublingWindow< uint64_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
thrill::DIA< Index > PrefixQuadrupling (const InputDIA &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
DIA< Index > PrefixQuadrupling (const InputDIA &input_dia, size_t input_size, bool packed)
 
template DIA< common::uint40PrefixQuadrupling< common::uint40 > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint32_t > PrefixQuadrupling< uint32_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint64_t > PrefixQuadrupling< uint64_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
thrill::DIA< Index > PrefixQuadruplingDiscarding (const InputDIA &input_dia, size_t input_size, bool packed)
 
template<typename Index , typename InputDIA >
DIA< Index > PrefixQuadruplingDiscarding (const InputDIA &input_dia, size_t input_size, bool packed)
 
template DIA< common::uint40PrefixQuadruplingDiscarding< common::uint40 > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint32_t > PrefixQuadruplingDiscarding< uint32_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 
template DIA< uint64_t > PrefixQuadruplingDiscarding< uint64_t > (const DIA< uint8_t > &input_dia, size_t input_size, bool packed)
 

Variables

static constexpr bool debug = false
 
bool debug_print = false
 
struct
examples::suffix_sorting::IndexRank 
TLX_ATTRIBUTE_PACKED
 

Enumeration Type Documentation

enum Status : uint8_t
strong
Enumerator
UNDECIDED 
UNIQUE 
FULLY_DISCARDED 
UNDECIDED 
UNIQUE 
FULLY_DISCARDED 

Definition at line 107 of file prefix_quadrupling.cpp.

enum Status : uint8_t
strong
Enumerator
UNDECIDED 
UNIQUE 
FULLY_DISCARDED 
UNDECIDED 
UNIQUE 
FULLY_DISCARDED 

Definition at line 130 of file prefix_doubling.cpp.

Function Documentation

bool examples::suffix_sorting::CheckSA ( const InputDIA &  input,
const SuffixArrayDIA &  suffix_array 
)

A pair (rank, index)

Definition at line 28 of file check_sa.hpp.

References IndexRank< Index >::index, LOG1, TLX_ATTRIBUTE_PACKED, and thrill::api::Zip().

InputDIA examples::suffix_sorting::ConstructBWT ( const InputDIA &  input,
const SuffixArrayDIA &  suffix_array,
uint64_t  input_size 
)
IndexDIA examples::suffix_sorting::ConstructLCP ( const InputDIA &  input,
const IndexDIA &  ,
const InputDIA &  bwt,
uint64_t  input_size 
)
auto examples::suffix_sorting::ConstructWaveletTree ( const InputDIA &  input_dia,
const std::string &  output_path 
)
auto examples::suffix_sorting::ConstructWaveletTree ( const InputDIA &  input_dia)

Definition at line 40 of file wavelet_tree.cpp.

References debug, tlx::integer_log2_ceil(), sLOG, and thrill::common::str_sprintf().

thrill::DIA<Index> examples::suffix_sorting::DC3 ( const InputDIA &  input_dia,
size_t  input_size,
size_t  K 
)

Definition at line 638 of file dc3.cpp.

DIA<Index> examples::suffix_sorting::DC3 ( const InputDIA &  input_dia,
size_t  input_size,
size_t  K 
)

Definition at line 638 of file dc3.cpp.

template DIA<common::uint40> examples::suffix_sorting::DC3< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)
template DIA<uint32_t> examples::suffix_sorting::DC3< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)
template DIA<uint64_t> examples::suffix_sorting::DC3< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)
DIA<dc3_local::StringFragment<Index, typename InputDIA::ValueType> > examples::suffix_sorting::DC3Recursive ( const InputDIA &  input_dia,
size_t  input_size,
size_t  K 
)
thrill::DIA<Index> examples::suffix_sorting::DC7 ( const InputDIA &  input_dia,
size_t  input_size,
size_t  K 
)

Definition at line 905 of file dc7.cpp.

DIA<Index> examples::suffix_sorting::DC7 ( const InputDIA &  input_dia,
size_t  input_size,
size_t  K 
)

Definition at line 905 of file dc7.cpp.

template DIA<common::uint40> examples::suffix_sorting::DC7< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)
template DIA<uint32_t> examples::suffix_sorting::DC7< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)
template DIA<uint64_t> examples::suffix_sorting::DC7< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)
DIA<dc7_local::StringFragment<Index, typename InputDIA::ValueType> > examples::suffix_sorting::DC7Recursive ( const InputDIA &  input_dia,
size_t  input_size,
size_t  K 
)
static bool examples::suffix_sorting::IsDiffCover7 ( size_t  i)
inlinestatic

Definition at line 404 of file dc7.cpp.

Referenced by DC7Recursive().

template DIA<common::uint40> examples::suffix_sorting::PrefixDoublingDiscarding< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint32_t> examples::suffix_sorting::PrefixDoublingDiscarding< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint64_t> examples::suffix_sorting::PrefixDoublingDiscarding< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
DIA<IndexRank<Index> > examples::suffix_sorting::PrefixDoublingPack ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed,
size_t &  iteration 
)

take input and pack it into an array of Index characters

Definition at line 179 of file prefix_doubling.cpp.

References debug_print, IndexRank< Index >::index, tlx::integer_log2_ceil(), tlx::integer_log2_floor(), and LOG1.

thrill::DIA<Index> examples::suffix_sorting::PrefixDoublingSorting ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)
DIA<Index> examples::suffix_sorting::PrefixDoublingSorting ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<common::uint40> examples::suffix_sorting::PrefixDoublingSorting< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint32_t> examples::suffix_sorting::PrefixDoublingSorting< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint64_t> examples::suffix_sorting::PrefixDoublingSorting< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
thrill::DIA<Index> examples::suffix_sorting::PrefixDoublingWindow ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)
DIA<Index> examples::suffix_sorting::PrefixDoublingWindow ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<common::uint40> examples::suffix_sorting::PrefixDoublingWindow< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint32_t> examples::suffix_sorting::PrefixDoublingWindow< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint64_t> examples::suffix_sorting::PrefixDoublingWindow< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
thrill::DIA<Index> examples::suffix_sorting::PrefixQuadrupling ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)
DIA<Index> examples::suffix_sorting::PrefixQuadrupling ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<common::uint40> examples::suffix_sorting::PrefixQuadrupling< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint32_t> examples::suffix_sorting::PrefixQuadrupling< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint64_t> examples::suffix_sorting::PrefixQuadrupling< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
thrill::DIA<Index> examples::suffix_sorting::PrefixQuadruplingDiscarding ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)
DIA<Index> examples::suffix_sorting::PrefixQuadruplingDiscarding ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<common::uint40> examples::suffix_sorting::PrefixQuadruplingDiscarding< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint32_t> examples::suffix_sorting::PrefixQuadruplingDiscarding< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)
template DIA<uint64_t> examples::suffix_sorting::PrefixQuadruplingDiscarding< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

Variable Documentation

constexpr bool debug = false
static

Definition at line 35 of file wavelet_tree.cpp.

Referenced by ConstructWaveletTree().

struct examples::suffix_sorting::Index3Rank TLX_ATTRIBUTE_PACKED

Referenced by CheckSA(), and ConstructBWT().