8#ifndef INCLUDED_SDSL_CSA_SADA
9#define INCLUDED_SDSL_CSA_SADA
41template <
class t_enc_vec = enc_vector<>,
43 u
int32_t t_inv_dens = 64,
44 class t_sa_sample_strat = sa_order_sa_sampling<>,
45 class t_isa_sample_strat = isa_sampling<>,
46 class t_alphabet_strat =
byte_alphabet
51 static_assert(t_dens > 0,
"Second template argument has to be greater then 0.");
52 static_assert(t_inv_dens > 0,
"Third template argument has to be greater then 0.");
53 static_assert(std::is_same<typename sampling_tag<t_sa_sample_strat>::type,
sa_sampling_tag>::value,
54 "Forth template argument has to be a suffix array sampling strategy.");
55 static_assert(std::is_same<typename sampling_tag<t_isa_sample_strat>::type,
isa_sampling_tag>::value,
56 "Fifth template argument has to be a inverse suffix array sampling strategy.");
90 typedef typename alphabet_type::char_type
char_type;
108 mutable std::vector<uint64_t> m_psi_buf;
114 m_psi_buf = std::vector<uint64_t>(enc_vector_type::sample_dens + 1);
119 const typename alphabet_type::char2comp_type &
char2comp = m_alphabet.char2comp;
120 const typename alphabet_type::comp2char_type &
comp2char = m_alphabet.comp2char;
121 const typename alphabet_type::C_type &
C = m_alphabet.C;
122 const typename alphabet_type::sigma_type &
sigma = m_alphabet.sigma;
141 , m_sa_sample(csa.m_sa_sample)
142 , m_isa_sample(csa.m_isa_sample)
143 , m_alphabet(csa.m_alphabet)
146 m_isa_sample.set_vector(&m_sa_sample);
151 : m_psi(std::move(csa.m_psi))
152 , m_sa_sample(std::move(csa.m_sa_sample))
153 , m_isa_sample(std::move(csa.m_isa_sample))
154 , m_alphabet(std::move(csa.m_alphabet))
157 m_isa_sample.set_vector(&m_sa_sample);
180 bool empty()
const {
return m_psi.empty(); }
212 *
this = std::move(tmp);
225 m_psi = std::move(csa.m_psi);
226 m_sa_sample = std::move(csa.m_sa_sample);
227 m_isa_sample = std::move(csa.m_isa_sample);
228 m_isa_sample.set_vector(&m_sa_sample);
229 m_alphabet = std::move(csa.m_alphabet);
230 m_psi_buf = std::move(csa.m_psi_buf);
238 return (m_psi == other.m_psi) && (m_sa_sample == other.m_sa_sample) && (m_isa_sample == other.m_isa_sample) &&
239 (m_alphabet == other.m_alphabet);
254 void load(std::istream & in);
256 template <
typename archive_t>
259 template <
typename archive_t>
276 if (cc == 0 and c != 0)
278 if (i == 0)
return 0;
283 const size_type sd = m_psi.get_sample_dens();
285 size_type upper_sb = (
C[cc + 1] + sd - 1) / sd;
286 while (lower_sb + 1 < upper_sb)
288 size_type mid = (lower_sb + upper_sb) / 2;
289 if (m_psi.sample(mid) >= i)
295 if (lower_sb == upper_sb)
300 else if (lower_sb > (
C[cc] + sd - 1) / sd)
304 lower_b = lower_sb * sd;
305 if (0 == m_psi_buf.size())
307 upper_b = std::min(upper_sb * sd,
C[cc + 1]);
310 uint64_t * p = m_psi_buf.data();
312 m_psi.get_inter_sampled_values(lower_sb, p);
313 p = m_psi_buf.data();
314 uint64_t smpl = m_psi.sample(lower_sb);
316 if (lower_b + m_psi.get_sample_dens() >=
C[cc + 1])
317 m_psi_buf[
C[cc + 1] - lower_b] =
size() - smpl;
319 m_psi_buf[m_psi.get_sample_dens()] =
size() - smpl;
321 while ((*p++) + smpl < i)
324 return p - 1 - m_psi_buf.data() + lower_b -
C[cc];
328 if (m_psi.sample(lower_sb) >= i)
331 upper_b = lower_sb * sd + 1;
335 lower_b = lower_sb * sd;
336 upper_b = std::min(upper_sb * sd,
C[cc + 1]);
342 while (lower_b + 1 < upper_b)
351 return lower_b -
C[cc] + 1;
354 return m_psi[lower_b] < i;
370 if (cc == 0 and c != 0)
373 if (
C[cc] + i - 1 <
C[cc + 1]) {
return m_psi[
C[cc] + i - 1]; }
381template <
class t_enc_vec,
384 class t_sa_sample_strat,
386 class t_alphabet_strat>
406 util::swap_support(m_isa_sample, isa_s, &m_sa_sample, (
const sa_sample_type *)
nullptr);
413 for (
typename alphabet_type::sigma_type i = 0; i < sigma; ++i) { cnt_chr[i] = C[i]; }
421 for (
size_type i = 0; i < n; ++i) { psi[cnt_chr[char2comp[bwt_buf[i]]]++] = i; }
427 m_psi = t_enc_vec(psi_buf);
431template <
class t_enc_vec,
434 class t_sa_sample_strat,
436 class t_alphabet_strat>
441 while (!m_sa_sample.is_sampled(i))
447 if (result < off) {
return m_psi.size() - (off - result); }
452template <
class t_enc_vec,
455 class t_sa_sample_strat,
457 class t_alphabet_strat>
465 written_bytes += m_psi.serialize(out, child,
"psi");
466 written_bytes += m_sa_sample.serialize(out, child,
"sa_samples");
467 written_bytes += m_isa_sample.serialize(out, child,
"isa_samples");
468 written_bytes += m_alphabet.serialize(out, child,
"alphabet");
470 return written_bytes;
473template <
class t_enc_vec,
476 class t_sa_sample_strat,
478 class t_alphabet_strat>
482 m_sa_sample.load(in);
483 m_isa_sample.load(in, &m_sa_sample);
487template <
class t_enc_vec,
490 class t_sa_sample_strat,
492 class t_alphabet_strat>
493template <
typename archive_t>
495 archive_t & ar)
const
503template <
class t_enc_vec,
506 class t_sa_sample_strat,
508 class t_alphabet_strat>
509template <
typename archive_t>
516 m_isa_sample.set_vector(&m_sa_sample);
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.
t_isa_sample_strat::template type< csa_sada > isa_sample_type
alphabet_type::string_type string_type
uint32_t get_sample_dens() const
alphabet_type::alphabet_category alphabet_category
isa_of_csa_psi< csa_sada > isa_type
bwt_of_csa_psi< csa_sada > bwt_type
const alphabet_type::comp2char_type & comp2char
t_enc_vec enc_vector_type
const_iterator begin() const
Returns a const_iterator to the first element.
const_reference reference
csa_sada & operator=(csa_sada &&csa)
Assignment Move Operator.
t_sa_sample_strat::template type< csa_sada > sa_sample_type
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.
alphabet_type::comp_char_type comp_char_type
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.
static const uint32_t linear_decode_limit
csa_sada(csa_sada &&csa)
Move constructor.
value_type operator[](size_type i) const
[]-operator
const_reference * pointer
bool operator==(csa_sada const &other) const noexcept
Equality operator.
t_alphabet_strat alphabet_type
void load(std::istream &in)
Load from a stream.
const isa_sample_type & isa_sample
~csa_sada()
Default Destructor.
text_of_csa< csa_sada > text_type
csa_sada(const csa_sada &csa)
Copy constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
first_row_of_csa< csa_sada > first_row_type
int_vector ::size_type size_type
size_type size() const
Number of elements in the .
alphabet_type::char_type char_type
ptrdiff_t difference_type
const pointer const_pointer
csa_sada & operator=(const csa_sada &csa)
Assignment Copy Operator.
random_access_const_iterator< csa_sada > const_iterator
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.
traverse_csa_psi< csa_sada, false > lf_type
const sa_sample_type & sa_sample
const value_type const_reference
const alphabet_type::sigma_type & sigma
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
csa_sada()
Default Constructor.
uint64_t size() const
Returns the number of elements currently stored.
A generic vector class for integers of width .
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)
static int_vector_mapper< t_width > create(const std::string &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.
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.
void register_cache_file(const std::string &key, cache_config &config)
Register the existing resource specified by the key to the cache.
bool cache_file_exists(const std::string &key, const cache_config &config)
Checks if the resource specified by the key exists in the cache.
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.
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.