8#ifndef INCLUDED_SDSL_CSA_SADA
9#define INCLUDED_SDSL_CSA_SADA
51template <
class t_enc_vec = enc_vector<>,
53 u
int32_t t_inv_dens = 64,
54 class t_sa_sample_strat = sa_order_sa_sampling<>,
55 class t_isa_sample_strat = isa_sampling<>,
56 class t_alphabet_strat =
byte_alphabet
61 static_assert(t_dens > 0,
"Second template argument has to be greater then 0.");
62 static_assert(t_inv_dens > 0,
"Third template argument has to be greater then 0.");
63 static_assert(std::is_same<typename sampling_tag<t_sa_sample_strat>::type,
sa_sampling_tag>::value,
64 "Forth template argument has to be a suffix array sampling strategy.");
65 static_assert(std::is_same<typename sampling_tag<t_isa_sample_strat>::type,
isa_sampling_tag>::value,
66 "Fifth template argument has to be a inverse suffix array sampling strategy.");
118 mutable std::vector<uint64_t> m_psi_buf;
124 m_psi_buf = std::vector<uint64_t>(enc_vector_type::sample_dens + 1);
129 const typename alphabet_type::char2comp_type &
char2comp = m_alphabet.char2comp;
130 const typename alphabet_type::comp2char_type &
comp2char = m_alphabet.comp2char;
131 const typename alphabet_type::C_type &
C = m_alphabet.C;
132 const typename alphabet_type::sigma_type &
sigma = m_alphabet.sigma;
155 m_sa_sample(csa.m_sa_sample),
156 m_isa_sample(csa.m_isa_sample),
157 m_alphabet(csa.m_alphabet)
160 m_isa_sample.set_vector(&m_sa_sample);
165 m_psi(std::move(csa.m_psi)),
166 m_sa_sample(std::move(csa.m_sa_sample)),
167 m_isa_sample(std::move(csa.m_isa_sample)),
168 m_alphabet(std::move(csa.m_alphabet))
171 m_isa_sample.set_vector(&m_sa_sample);
193 return t_enc_vec::max_size();
202 return m_psi.empty();
241 *
this = std::move(tmp);
254 m_psi = std::move(csa.m_psi);
255 m_sa_sample = std::move(csa.m_sa_sample);
256 m_isa_sample = std::move(csa.m_isa_sample);
257 m_isa_sample.set_vector(&m_sa_sample);
258 m_alphabet = std::move(csa.m_alphabet);
259 m_psi_buf = std::move(csa.m_psi_buf);
267 return (m_psi == other.m_psi) && (m_sa_sample == other.m_sa_sample) && (m_isa_sample == other.m_isa_sample)
268 && (m_alphabet == other.m_alphabet);
274 return !(*
this == other);
286 void load(std::istream & in);
288 template <
typename archive_t>
291 template <
typename archive_t>
311 if (cc == 0 and c != 0)
319 const size_type sd = m_psi.get_sample_dens();
321 size_type upper_sb = (
C[cc + 1] + sd - 1) / sd;
322 while (lower_sb + 1 < upper_sb)
324 size_type mid = (lower_sb + upper_sb) / 2;
325 if (m_psi.sample(mid) >= i)
331 if (lower_sb == upper_sb)
336 else if (lower_sb > (
C[cc] + sd - 1) / sd)
340 lower_b = lower_sb * sd;
341 if (0 == m_psi_buf.size())
343 upper_b = std::min(upper_sb * sd,
C[cc + 1]);
346 uint64_t * p = m_psi_buf.data();
348 m_psi.get_inter_sampled_values(lower_sb, p);
349 p = m_psi_buf.data();
350 uint64_t smpl = m_psi.sample(lower_sb);
352 if (lower_b + m_psi.get_sample_dens() >=
C[cc + 1])
353 m_psi_buf[
C[cc + 1] - lower_b] =
size() - smpl;
355 m_psi_buf[m_psi.get_sample_dens()] =
size() - smpl;
357 while ((*p++) + smpl < i)
360 return p - 1 - m_psi_buf.data() + lower_b -
C[cc];
364 if (m_psi.sample(lower_sb) >= i)
367 upper_b = lower_sb * sd + 1;
371 lower_b = lower_sb * sd;
372 upper_b = std::min(upper_sb * sd,
C[cc + 1]);
378 while (lower_b + 1 < upper_b)
387 return lower_b -
C[cc] + 1;
390 return m_psi[lower_b] < i;
406 if (cc == 0 and c != 0)
409 if (
C[cc] + i - 1 <
C[cc + 1])
411 return m_psi[
C[cc] + i - 1];
420template <
class t_enc_vec,
423 class t_sa_sample_strat,
425 class t_alphabet_strat>
448 util::swap_support(m_isa_sample, isa_s, &m_sa_sample, (
sa_sample_type const *)
nullptr);
455 for (
typename alphabet_type::sigma_type i = 0; i < sigma; ++i)
468 psi[cnt_chr[char2comp[bwt_buf[i]]]++] = i;
475 m_psi = t_enc_vec(psi_buf);
479template <
class t_enc_vec,
482 class t_sa_sample_strat,
484 class t_alphabet_strat>
490 while (!m_sa_sample.is_sampled(i))
498 return m_psi.size() - (off - result);
504template <
class t_enc_vec,
507 class t_sa_sample_strat,
509 class t_alphabet_strat>
517 written_bytes += m_psi.serialize(out, child,
"psi");
518 written_bytes += m_sa_sample.serialize(out, child,
"sa_samples");
519 written_bytes += m_isa_sample.serialize(out, child,
"isa_samples");
520 written_bytes += m_alphabet.serialize(out, child,
"alphabet");
522 return written_bytes;
525template <
class t_enc_vec,
528 class t_sa_sample_strat,
530 class t_alphabet_strat>
534 m_sa_sample.load(in);
535 m_isa_sample.load(in, &m_sa_sample);
539template <
class t_enc_vec,
542 class t_sa_sample_strat,
544 class t_alphabet_strat>
545template <
typename archive_t>
547 archive_t & ar)
const
555template <
class t_enc_vec,
558 class t_sa_sample_strat,
560 class t_alphabet_strat>
561template <
typename archive_t>
568 m_isa_sample.set_vector(&m_sa_sample);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_LOAD_FUNCTION_NAME
#define CEREAL_SAVE_FUNCTION_NAME
A wrapper for the bwt of a compressed suffix array that is based on the function.
A class for the Compressed Suffix Array (CSA) proposed by Sadakane for practical implementation.
alphabet_type::string_type string_type
uint32_t get_sample_dens() const
isa_of_csa_psi< csa_sada > isa_type
int_vector ::size_type size_type
const alphabet_type::comp2char_type & comp2char
alphabet_type::char_type char_type
t_alphabet_strat alphabet_type
const value_type const_reference
const_iterator begin() const
Returns a const_iterator to the first element.
t_sa_sample_strat::template type< csa_sada > sa_sample_type
csa_sada & operator=(csa_sada &&csa)
Assignment Move Operator.
random_access_const_iterator< csa_sada > const_iterator
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
bool operator!=(csa_sada const &other) const noexcept
Inequality operator.
bool empty() const
Returns if the data strucutre is empty.
static size_type max_size()
Returns the largest size that csa_sada can ever have.
sa_sample_type const & sa_sample
static const uint32_t linear_decode_limit
csa_sada(csa_sada &&csa)
Move constructor.
value_type operator[](size_type i) const
[]-operator
bool operator==(csa_sada const &other) const noexcept
Equality operator.
const pointer const_pointer
text_of_csa< csa_sada > text_type
void load(std::istream &in)
Load from a stream.
ptrdiff_t difference_type
~csa_sada()
Default Destructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
alphabet_type::comp_char_type comp_char_type
isa_sample_type const & isa_sample
size_type size() const
Number of elements in the .
const_reference reference
csa_sada & operator=(csa_sada const &csa)
Assignment Copy Operator.
traverse_csa_psi< csa_sada, false > lf_type
alphabet_type::alphabet_category alphabet_category
bwt_of_csa_psi< csa_sada > bwt_type
const alphabet_type::C_type & C
const alphabet_type::char2comp_type & char2comp
const_iterator end() const
Returns a const_iterator to the element after the last element.
t_enc_vec enc_vector_type
const alphabet_type::sigma_type & sigma
csa_sada(csa_sada const &csa)
Copy constructor.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
first_row_of_csa< csa_sada > first_row_type
const_reference * pointer
csa_sada()
Default Constructor.
t_isa_sample_strat::template type< csa_sada > isa_sample_type
uint64_t size() const
Returns the number of elements currently stored.
A generic vector class for integers of width .
int_vector_size_type size_type
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)
static int_vector_mapper< t_width > create(std::string const &key, cache_config &config)
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.
enc_vector.hpp contains the sdsl::enc_vector class.
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.
void register_cache_file(std::string const &key, cache_config &config)
Register the existing resource specified by the key to the cache.
constexpr char const * key_bwt()
Contains declarations and definitions of data structure concepts.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
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.