8#ifndef INCLUDED_SDSL_CSA_WT
9#define INCLUDED_SDSL_CSA_WT
48template <
class t_wt = wt_huff<>,
50 u
int32_t t_inv_dens = 64,
51 class t_sa_sample_strat = sa_order_sa_sampling<>,
52 class t_isa_sample_strat = isa_sampling<>,
53 class t_alphabet_strat =
54 typename wt_alphabet_trait<t_wt>::type>
57 static_assert(std::is_same<typename index_tag<t_wt>::type,
wt_tag>::value,
58 "First template argument has to be a wavelet tree type.");
59 static_assert(t_dens > 0,
"Second template argument has to be greater then 0.");
60 static_assert(t_inv_dens > 0,
"Third template argument has to be greater then 0.");
61 static_assert(std::is_same<typename sampling_tag<t_sa_sample_strat>::type,
sa_sampling_tag>::value,
62 "Forth template argument has to be a suffix array sampling strategy.");
63 static_assert(std::is_same<typename sampling_tag<t_isa_sample_strat>::type,
isa_sampling_tag>::value,
64 "Fifth template argument has to be a inverse suffix array sampling strategy.");
96 typedef typename alphabet_type::char_type
char_type;
116 const typename alphabet_type::char2comp_type &
char2comp = m_alphabet.char2comp;
117 const typename alphabet_type::comp2char_type &
comp2char = m_alphabet.comp2char;
118 const typename alphabet_type::C_type &
C = m_alphabet.C;
119 const typename alphabet_type::sigma_type &
sigma = m_alphabet.sigma;
136 : m_wavelet_tree(csa.m_wavelet_tree)
137 , m_sa_sample(csa.m_sa_sample)
138 , m_isa_sample(csa.m_isa_sample)
139 , m_alphabet(csa.m_alphabet)
141 m_isa_sample.set_vector(&m_sa_sample);
146 : m_wavelet_tree(std::move(csa.m_wavelet_tree))
147 , m_sa_sample(std::move(csa.m_sa_sample))
148 , m_isa_sample(std::move(csa.m_isa_sample))
149 , m_alphabet(std::move(csa.m_alphabet))
151 m_isa_sample.set_vector(&m_sa_sample);
175 bool empty()
const {
return m_wavelet_tree.empty(); }
207 *
this = std::move(tmp);
220 m_wavelet_tree = std::move(csa.m_wavelet_tree);
221 m_sa_sample = std::move(csa.m_sa_sample);
222 m_isa_sample = std::move(csa.m_isa_sample);
223 m_isa_sample.set_vector(&m_sa_sample);
224 m_alphabet = std::move(csa.m_alphabet);
232 return (m_wavelet_tree == other.m_wavelet_tree) && (m_sa_sample == other.m_sa_sample) &&
233 (m_isa_sample == other.m_isa_sample) && (m_alphabet == other.m_alphabet);
248 void load(std::istream & in);
251 template <
typename archive_t>
255 template <
typename archive_t>
281 if (cc == 0 and c != 0)
284 if (
C[cc] + i - 1 <
C[cc + 1]) {
return m_wavelet_tree.select(i, c); }
295 class t_sa_sample_strat,
297 class t_alphabet_strat>
315 util::swap_support(m_isa_sample, isa_s, &m_sa_sample, &m_sa_sample);
332 class t_sa_sample_strat,
334 class t_alphabet_strat>
339 while (!m_sa_sample.is_sampled(i))
345 if (result + off <
size()) {
return result + off; }
348 return result + off -
size();
355 class t_sa_sample_strat,
357 class t_alphabet_strat>
360 std::string name)
const
365 written_bytes += m_wavelet_tree.serialize(out, child,
"wavelet_tree");
366 written_bytes += m_sa_sample.serialize(out, child,
"sa_samples");
367 written_bytes += m_isa_sample.serialize(out, child,
"isa_samples");
368 written_bytes += m_alphabet.serialize(out, child,
"alphabet");
370 return written_bytes;
376 class t_sa_sample_strat,
378 class t_alphabet_strat>
381 m_wavelet_tree.load(in);
382 m_sa_sample.load(in);
383 m_isa_sample.load(in, &m_sa_sample);
390 class t_sa_sample_strat,
392 class t_alphabet_strat>
393template <
typename archive_t>
395 archive_t & ar)
const
406 class t_sa_sample_strat,
408 class t_alphabet_strat>
409template <
typename archive_t>
416 m_isa_sample.set_vector(&m_sa_sample);
A class for the Compressed Suffix Array (CSA) based on a Wavelet Tree (WT) of the Burrow Wheeler Tran...
bool empty() const
Returns if the data strucutre is empty.
random_access_const_iterator< csa_wt > const_iterator
t_isa_sample_strat::template type< csa_wt > isa_sample_type
csa_wt(csa_wt &&csa)
Move constructor.
bool operator!=(csa_wt const &other) const noexcept
Inequality operator.
ptrdiff_t difference_type
const_iterator begin() const
Returns a const_iterator to the first element.
void load(std::istream &in)
Load from a stream.
csa_wt & operator=(csa_wt &&csa)
Assignment Move Operator.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
const alphabet_type::char2comp_type & char2comp
const value_type const_reference
traverse_csa_wt< csa_wt, true > psi_type
static size_type max_size()
Returns the largest size that csa_wt can ever have.
const alphabet_type::sigma_type & sigma
alphabet_type::string_type string_type
bool operator==(csa_wt const &other) const noexcept
Equality operator.
text_of_csa< csa_wt > text_type
const sa_sample_type & sa_sample
t_sa_sample_strat::template type< csa_wt > sa_sample_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
const_reference * pointer
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
value_type operator[](size_type i) const
[]-operator
bwt_of_csa_wt< csa_wt > bwt_type
const_reference reference
const alphabet_type::C_type & C
alphabet_type::char_type char_type
size_type size() const
Number of elements in the .
const wavelet_tree_type & wavelet_tree
isa_of_csa_wt< csa_wt > isa_type
csa_wt()=default
Default constructor.
const isa_sample_type & isa_sample
alphabet_type::comp_char_type comp_char_type
alphabet_type::alphabet_category alphabet_category
const_iterator end() const
Returns a const_iterator to the element after the last element.
csa_wt(const csa_wt &csa)
Copy constructor.
int_vector ::size_type size_type
first_row_of_csa< csa_wt > first_row_type
t_alphabet_strat alphabet_type
traverse_csa_wt< csa_wt, false > lf_type
csa_wt & operator=(const csa_wt &csa)
Assignment Operator.
const pointer const_pointer
const alphabet_type::comp2char_type & comp2char
uint64_t size() const
Returns the number of elements currently stored.
A generic vector class for integers of width .
static size_type max_size() noexcept
Maximum size of the int_vector.
static mm_event_proxy event(const std::string &name)
Generic iterator for a random access container.
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
A wrapper class for the and LF function for (compressed) suffix arrays that are based on a wavelet t...
csa_alphabet_strategy.hpp includes different strategy classes for representing an alphabet of a CSA.
csa_sampling_strategy.hpp includes different strategy classes for suffix array sampling in the CSAs.
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
std::string cache_file_name(const std::string &key, const cache_config &config)
Returns the file name of the resource.
bool cache_file_exists(const std::string &key, const cache_config &config)
Checks if the resource specified by the key exists in the cache.
int_vector ::size_type size(const range_type &r)
Size of a range.
Helper class for construction process.
suffix_array_helper.hpp contains some helper classes for CSTs
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.
wavelet_trees.hpp contains wavelet tree implementations.