Loading [MathJax]/extensions/tex2jax.js
Thrill  0.1
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules 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)
 
std::ostream & operator<< (std::ostream &os, const Status &s)
 
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

◆ Status [1/2]

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

Definition at line 107 of file prefix_quadrupling.cpp.

◆ Status [2/2]

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

◆ CheckSA()

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().

◆ ConstructBWT()

InputDIA examples::suffix_sorting::ConstructBWT ( const InputDIA &  input,
const SuffixArrayDIA &  suffix_array,
uint64_t  input_size 
)

◆ ConstructLCP()

IndexDIA examples::suffix_sorting::ConstructLCP ( const InputDIA &  input,
const IndexDIA &  ,
const InputDIA &  bwt,
uint64_t  input_size 
)

◆ ConstructWaveletTree() [1/2]

auto examples::suffix_sorting::ConstructWaveletTree ( const InputDIA &  input_dia,
const std::string &  output_path 
)

◆ ConstructWaveletTree() [2/2]

auto examples::suffix_sorting::ConstructWaveletTree ( const InputDIA &  input_dia)

◆ DC3() [1/2]

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.

References DC3< uint32_t >(), DC3< uint64_t >(), and tlx::digest_detail::K.

◆ DC3() [2/2]

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.

References DC3< uint32_t >(), DC3< uint64_t >(), and tlx::digest_detail::K.

◆ DC3< common::uint40 >()

template DIA<common::uint40> examples::suffix_sorting::DC3< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)

◆ DC3< uint32_t >()

template DIA<uint32_t> examples::suffix_sorting::DC3< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)

Referenced by DC3().

◆ DC3< uint64_t >()

template DIA<uint64_t> examples::suffix_sorting::DC3< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)

Referenced by DC3().

◆ DC3Recursive()

DIA<dc3_local::StringFragment<Index, typename InputDIA::ValueType> > examples::suffix_sorting::DC3Recursive ( const InputDIA &  input_dia,
size_t  input_size,
size_t  K 
)

◆ DC7() [1/2]

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.

References DC7< uint32_t >(), DC7< uint64_t >(), and tlx::digest_detail::K.

◆ DC7() [2/2]

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.

References DC7< uint32_t >(), DC7< uint64_t >(), and tlx::digest_detail::K.

◆ DC7< common::uint40 >()

template DIA<common::uint40> examples::suffix_sorting::DC7< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)

◆ DC7< uint32_t >()

template DIA<uint32_t> examples::suffix_sorting::DC7< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)

Referenced by DC7().

◆ DC7< uint64_t >()

template DIA<uint64_t> examples::suffix_sorting::DC7< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
size_t  K 
)

Referenced by DC7().

◆ DC7Recursive()

DIA<dc7_local::StringFragment<Index, typename InputDIA::ValueType> > examples::suffix_sorting::DC7Recursive ( const InputDIA &  input_dia,
size_t  input_size,
size_t  K 
)

◆ IsDiffCover7()

static bool examples::suffix_sorting::IsDiffCover7 ( size_t  i)
inlinestatic

Definition at line 404 of file dc7.cpp.

Referenced by DC7Recursive().

◆ operator<<()

std::ostream& examples::suffix_sorting::operator<< ( std::ostream &  os,
const Status s 
)

◆ PrefixDoublingDiscarding() [1/2]

◆ PrefixDoublingDiscarding() [2/2]

◆ PrefixDoublingDiscarding< common::uint40 >()

template DIA<common::uint40> examples::suffix_sorting::PrefixDoublingDiscarding< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingDiscarding< uint32_t >()

template DIA<uint32_t> examples::suffix_sorting::PrefixDoublingDiscarding< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingDiscarding< uint64_t >()

template DIA<uint64_t> examples::suffix_sorting::PrefixDoublingDiscarding< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingPack()

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 191 of file prefix_doubling.cpp.

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

◆ PrefixDoublingSorting() [1/2]

thrill::DIA<Index> examples::suffix_sorting::PrefixDoublingSorting ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingSorting() [2/2]

DIA<Index> examples::suffix_sorting::PrefixDoublingSorting ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingSorting< common::uint40 >()

template DIA<common::uint40> examples::suffix_sorting::PrefixDoublingSorting< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingSorting< uint32_t >()

template DIA<uint32_t> examples::suffix_sorting::PrefixDoublingSorting< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingSorting< uint64_t >()

template DIA<uint64_t> examples::suffix_sorting::PrefixDoublingSorting< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingWindow() [1/2]

thrill::DIA<Index> examples::suffix_sorting::PrefixDoublingWindow ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingWindow() [2/2]

DIA<Index> examples::suffix_sorting::PrefixDoublingWindow ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingWindow< common::uint40 >()

template DIA<common::uint40> examples::suffix_sorting::PrefixDoublingWindow< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingWindow< uint32_t >()

template DIA<uint32_t> examples::suffix_sorting::PrefixDoublingWindow< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixDoublingWindow< uint64_t >()

template DIA<uint64_t> examples::suffix_sorting::PrefixDoublingWindow< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixQuadrupling() [1/2]

◆ PrefixQuadrupling() [2/2]

◆ PrefixQuadrupling< common::uint40 >()

template DIA<common::uint40> examples::suffix_sorting::PrefixQuadrupling< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixQuadrupling< uint32_t >()

template DIA<uint32_t> examples::suffix_sorting::PrefixQuadrupling< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

Referenced by PrefixQuadrupling().

◆ PrefixQuadrupling< uint64_t >()

template DIA<uint64_t> examples::suffix_sorting::PrefixQuadrupling< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

Referenced by PrefixQuadrupling().

◆ PrefixQuadruplingDiscarding() [1/2]

thrill::DIA<Index> examples::suffix_sorting::PrefixQuadruplingDiscarding ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixQuadruplingDiscarding() [2/2]

DIA<Index> examples::suffix_sorting::PrefixQuadruplingDiscarding ( const InputDIA &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixQuadruplingDiscarding< common::uint40 >()

template DIA<common::uint40> examples::suffix_sorting::PrefixQuadruplingDiscarding< common::uint40 > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

◆ PrefixQuadruplingDiscarding< uint32_t >()

template DIA<uint32_t> examples::suffix_sorting::PrefixQuadruplingDiscarding< uint32_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

Referenced by PrefixQuadrupling().

◆ PrefixQuadruplingDiscarding< uint64_t >()

template DIA<uint64_t> examples::suffix_sorting::PrefixQuadruplingDiscarding< uint64_t > ( const DIA< uint8_t > &  input_dia,
size_t  input_size,
bool  packed 
)

Referenced by PrefixQuadrupling().

Variable Documentation

◆ debug

constexpr bool debug = false
static

Definition at line 35 of file wavelet_tree.cpp.

Referenced by ConstructWaveletTree().

◆ debug_print

◆ TLX_ATTRIBUTE_PACKED

struct examples::suffix_sorting::Index3Rank TLX_ATTRIBUTE_PACKED

Referenced by CheckSA(), ConstructBWT(), and operator<<().