8#ifndef INCLUDED_SDSL_CSA_WT
9#define INCLUDED_SDSL_CSA_WT
49template <
class t_wt = wt_huff<>,
51 u
int32_t t_inv_dens = 64,
52 class t_sa_sample_strat = sa_order_sa_sampling<>,
53 class t_isa_sample_strat = isa_sampling<>,
54 class t_alphabet_strat =
55 typename wt_alphabet_trait<t_wt>::type>
58 static_assert(std::is_same<typename index_tag<t_wt>::type,
wt_tag>::value,
59 "First template argument has to be a wavelet tree type.");
60 static_assert(t_dens > 0,
"Second template argument has to be greater then 0.");
61 static_assert(t_inv_dens > 0,
"Third template argument has to be greater then 0.");
62 static_assert(std::is_same<typename sampling_tag<t_sa_sample_strat>::type,
sa_sampling_tag>::value,
63 "Forth template argument has to be a suffix array sampling strategy.");
64 static_assert(std::is_same<typename sampling_tag<t_isa_sample_strat>::type,
isa_sampling_tag>::value,
65 "Fifth template argument has to be a inverse suffix array sampling strategy.");
97 typedef typename alphabet_type::char_type
char_type;
117 const typename alphabet_type::char2comp_type &
char2comp = m_alphabet.char2comp;
118 const typename alphabet_type::comp2char_type &
comp2char = m_alphabet.comp2char;
119 const typename alphabet_type::C_type &
C = m_alphabet.C;
120 const typename alphabet_type::sigma_type &
sigma = m_alphabet.sigma;
137 m_wavelet_tree(csa.m_wavelet_tree),
138 m_sa_sample(csa.m_sa_sample),
139 m_isa_sample(csa.m_isa_sample),
140 m_alphabet(csa.m_alphabet)
142 m_isa_sample.set_vector(&m_sa_sample);
147 m_wavelet_tree(std::move(csa.m_wavelet_tree)),
148 m_sa_sample(std::move(csa.m_sa_sample)),
149 m_isa_sample(std::move(csa.m_isa_sample)),
150 m_alphabet(std::move(csa.m_alphabet))
152 m_isa_sample.set_vector(&m_sa_sample);
166 return m_wavelet_tree.size();
184 return m_wavelet_tree.empty();
223 *
this = std::move(tmp);
236 m_wavelet_tree = std::move(csa.m_wavelet_tree);
237 m_sa_sample = std::move(csa.m_sa_sample);
238 m_isa_sample = std::move(csa.m_isa_sample);
239 m_isa_sample.set_vector(&m_sa_sample);
240 m_alphabet = std::move(csa.m_alphabet);
248 return (m_wavelet_tree == other.m_wavelet_tree) && (m_sa_sample == other.m_sa_sample)
249 && (m_isa_sample == other.m_isa_sample) && (m_alphabet == other.m_alphabet);
255 return !(*
this == other);
267 void load(std::istream & in);
270 template <
typename archive_t>
274 template <
typename archive_t>
288 return m_wavelet_tree.rank(i, c);
303 if (cc == 0 and c != 0)
306 if (
C[cc] + i - 1 <
C[cc + 1])
308 return m_wavelet_tree.select(i, c);
320 class t_sa_sample_strat,
322 class t_alphabet_strat>
343 util::swap_support(m_isa_sample, isa_s, &m_sa_sample, &m_sa_sample);
360 class t_sa_sample_strat,
362 class t_alphabet_strat>
367 while (!m_sa_sample.is_sampled(i))
373 if (result + off <
size())
379 return result + off -
size();
386 class t_sa_sample_strat,
388 class t_alphabet_strat>
391 std::string name)
const
396 written_bytes += m_wavelet_tree.serialize(out, child,
"wavelet_tree");
397 written_bytes += m_sa_sample.serialize(out, child,
"sa_samples");
398 written_bytes += m_isa_sample.serialize(out, child,
"isa_samples");
399 written_bytes += m_alphabet.serialize(out, child,
"alphabet");
401 return written_bytes;
407 class t_sa_sample_strat,
409 class t_alphabet_strat>
412 m_wavelet_tree.load(in);
413 m_sa_sample.load(in);
414 m_isa_sample.load(in, &m_sa_sample);
421 class t_sa_sample_strat,
423 class t_alphabet_strat>
424template <
typename archive_t>
426 archive_t & ar)
const
437 class t_sa_sample_strat,
439 class t_alphabet_strat>
440template <
typename archive_t>
447 m_isa_sample.set_vector(&m_sa_sample);
cereal.hpp offers cereal support
#define CEREAL_LOAD_FUNCTION_NAME
#define CEREAL_SAVE_FUNCTION_NAME
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.
csa_wt(csa_wt const &csa)
Copy constructor.
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.
wavelet_tree_type const & wavelet_tree
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
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 .
isa_sample_type const & isa_sample
isa_of_csa_wt< csa_wt > isa_type
csa_wt()=default
Default constructor.
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.
sa_sample_type const & sa_sample
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
const pointer const_pointer
const alphabet_type::comp2char_type & comp2char
csa_wt & operator=(csa_wt const &csa)
Assignment Operator.
uint64_t size() const
Returns the number of elements currently stored.
int_vector_size_type size_type
static size_type max_size() noexcept
static mm_event_proxy event(std::string const &name)
Generic iterator for a random access container.
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &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.
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
memory_tracking.hpp contains two function for allocating and deallocating memory
Namespace for the succinct data structure library.
bool cache_file_exists(std::string const &key, cache_config const &config)
Checks if the resource specified by the key exists in the cache.
std::string cache_file_name(std::string const &key, cache_config const &config)
Returns the file name of the resource.
constexpr char const * key_bwt()
int_vector ::size_type size(range_type const &r)
Size of a range.
Contains declarations and definitions of data structure concepts.
Helper class for construction process.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
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.
wt_huff.hpp contains a class for a Huffman shaped wavelet tree over byte sequences.