9#ifndef INCLUDED_CSA_ALPHABET_STRATEGY
10#define INCLUDED_CSA_ALPHABET_STRATEGY
53 class rank_support_type = rank_support_scan<>,
54 class select_support_type = select_support_scan<>,
56class succinct_byte_alphabet;
58template <
class bit_vector_type = sd_vector<>,
59 class rank_support_type =
typename bit_vector_type::rank_1_type,
60 class select_support_type =
typename bit_vector_type::select_1_type,
61 class C_array_type =
int_vector<>>
64template <u
int8_t
int_w
idth>
70template <u
int8_t
int_w
idth>
88template <
class t_alphabet_strategy>
104template <
class t_wt,
class t_enable =
void>
174 if (0 == len or 0 == text_buf.
size())
return;
175 assert(len <= text_buf.
size());
181 for (
size_type i = 0; i < len; ++i) { ++m_C[text_buf[i]]; }
184 for (
int i = 0; i < 256; ++i)
187 m_char2comp[i] = m_sigma;
188 m_comp2char[
sigma] = i;
189 m_C[m_sigma] = m_C[i];
192 m_comp2char.
resize(m_sigma);
194 for (
int i = (
int)m_sigma; i > 0; --i) m_C[i] = m_C[i - 1];
196 for (
int i = 1; i <= (int)m_sigma; ++i) m_C[i] += m_C[i - 1];
205 , m_char2comp(bas.m_char2comp)
206 , m_comp2char(bas.m_comp2char)
208 , m_sigma(bas.m_sigma)
216 , m_char2comp(std::move(bas.m_char2comp))
217 , m_comp2char(std::move(bas.m_comp2char))
218 , m_C(std::move(bas.m_C))
219 , m_sigma(bas.m_sigma)
227 *
this = std::move(tmp);
236 m_char2comp = std::move(bas.m_char2comp);
237 m_comp2char = std::move(bas.m_comp2char);
238 m_C = std::move(bas.m_C);
239 m_sigma = std::move(bas.m_sigma);
248 written_bytes += m_char2comp.
serialize(out, child,
"m_char2comp");
249 written_bytes += m_comp2char.
serialize(out, child,
"m_comp2char");
250 written_bytes += m_C.
serialize(out, child,
"m_C");
251 written_bytes +=
write_member(m_sigma, out, child,
"m_sigma");
253 return written_bytes;
258 m_char2comp.
load(in);
259 m_comp2char.
load(in);
267 return (m_char2comp == other.m_char2comp) && (m_comp2char == other.m_comp2char) && (m_C == other.m_C) &&
268 (m_sigma == other.m_sigma);
274 template <
typename archive_t>
283 template <
typename archive_t>
303template <
class bit_vector_type,
class rank_support_type,
class select_support_type,
class C_array_type>
338 if (c >= m_strat->m_char.size() or !m_strat->m_char[c])
return (
comp_char_type)0;
362 bit_vector_type m_char;
363 rank_support_type m_char_rank;
364 select_support_type m_char_select;
390 if (0 == len or 0 == text_buf.
size())
return;
391 assert(len <= text_buf.
size());
396 for (
size_type i = 0; i < len; ++i) { ++D[text_buf[i]]; }
399 for (
int i = 0; i < 256; ++i)
409 for (
int i = (
int)m_sigma; i > 0; --i) m_C[i] = D[i - 1];
411 for (
int i = 1; i <= (int)m_sigma; ++i) m_C[i] = m_C[i] + m_C[i - 1];
412 assert(m_C[
sigma] == len);
414 util::init_support(m_char_rank, &m_char);
415 util::init_support(m_char_select, &m_char);
424 , m_char(strat.m_char)
425 , m_char_rank(strat.m_char_rank)
426 , m_char_select(strat.m_char_select)
428 , m_sigma(strat.m_sigma)
430 m_char_rank.set_vector(&m_char);
431 m_char_select.set_vector(&m_char);
440 , m_char(std::move(strat.m_char))
441 , m_char_rank(std::move(strat.m_char_rank))
442 , m_char_select(std::move(strat.m_char_select))
443 , m_C(std::move(strat.m_C))
444 , m_sigma(std::move(strat.m_sigma))
446 m_char_rank.set_vector(&m_char);
447 m_char_select.set_vector(&m_char);
455 *
this = std::move(tmp);
464 m_char = std::move(strat.m_char);
465 m_char_rank = std::move(strat.m_char_rank);
466 m_char_rank.set_vector(&m_char);
467 m_char_select = std::move(strat.m_char_select);
468 m_char_select.set_vector(&m_char);
469 m_C = std::move(strat.m_C);
470 m_sigma = std::move(strat.m_sigma);
480 written_bytes += m_char.serialize(out, child,
"m_char");
481 written_bytes += m_char_rank.serialize(out, child,
"m_char_rank");
482 written_bytes += m_char_select.serialize(out, child,
"m_char_select");
483 written_bytes += m_C.serialize(out, child,
"m_C");
484 written_bytes +=
write_member(m_sigma, out, child,
"m_sigma");
486 return written_bytes;
493 m_char_rank.load(in);
494 m_char_rank.set_vector(&m_char);
495 m_char_select.load(in);
496 m_char_select.set_vector(&m_char);
504 return (m_char == other.m_char) && (m_char_rank == other.m_char_rank) &&
505 (m_char_select == other.m_char_select) && (m_C == other.m_C) && (m_sigma == other.m_sigma);
511 template <
typename archive_t>
521 template <
typename archive_t>
526 m_char_rank.set_vector(&m_char);
528 m_char_select.set_vector(&m_char);
534template <
typename bit_vector_type,
typename size_type>
538 auto largest_symbol = (--D.end())->first;
540 for (
const auto & x : D) { tmp_char[x.first] = 1; }
544template <
typename t_hi_bit_vector,
typename t_select_1,
typename t_select_0,
typename size_type>
546 const std::map<size_type, size_type> & D)
548 auto largest_symbol = (--D.end())->first;
550 for (
const auto & x : D) { builder.
set(x.first); }
616 if (0 == len || 0 == text_buf.
size())
return;
618 assert(len <= text_buf.
size());
623 for (
size_type i = 0; i < len; ++i) ++m_C[text_buf[i]];
628 for (
int i = 0; i < 256; ++i)
638 for (
int i = (
int)256; i > 0; --i) m_C[i] = m_C[i - 1];
640 for (
int i = 1; i <= (int)256; ++i) m_C[i] += m_C[i - 1];
650 , m_sigma(strat.m_sigma)
657 , m_C(std::move(strat.m_C))
658 , m_sigma(strat.m_sigma)
667 *
this = std::move(tmp);
677 m_C = std::move(strat.m_C);
678 m_sigma = strat.m_sigma;
688 written_bytes += m_C.
serialize(out, child,
"m_C");
689 written_bytes +=
write_member(m_sigma, out, child,
"m_sigma");
691 return written_bytes;
694 void load(std::istream & in)
700 template <
typename archive_t>
707 template <
typename archive_t>
716 return (m_C == other.m_C) && (m_sigma == other.m_sigma);
734template <
class bit_vector_type,
class rank_support_type,
class select_support_type,
class C_array_type>
769 if (m_strat->m_char.size() > 0)
771 if (c >= m_strat->m_char.size() or !m_strat->m_char[c])
return (
comp_char_type)0;
776 if (c >= m_strat->m_sigma)
return 0;
795 if (m_strat->m_char.size() > 0)
812 bit_vector_type m_char;
813 rank_support_type m_char_rank;
814 select_support_type m_char_select;
819 bool is_continuous_alphabet(std::map<size_type, size_type> & D)
828 return ((--D.end())->first + 1) == D.
size();
854 if (0 == len or 0 == text_buf.
size())
return;
855 assert(len <= text_buf.
size());
857 std::map<size_type, size_type> D;
859 for (
size_type i = 0; i < len; ++i) { D[text_buf[i]]++; }
861 if (is_continuous_alphabet(D))
869 assert(D.find(0) != D.end() and 1 == D[0]);
874 for (std::map<size_type, size_type>::const_iterator it = D.begin(), end = D.end(); it != end; ++it)
888 , m_char(strat.m_char)
889 , m_char_rank(strat.m_char_rank)
890 , m_char_select(strat.m_char_select)
892 , m_sigma(strat.m_sigma)
894 m_char_rank.set_vector(&m_char);
895 m_char_select.set_vector(&m_char);
904 , m_char(std::move(strat.m_char))
905 , m_char_rank(std::move(strat.m_char_rank))
906 , m_char_select(std::move(strat.m_char_select))
907 , m_C(std::move(strat.m_C))
908 , m_sigma(std::move(strat.m_sigma))
910 m_char_rank.set_vector(&m_char);
911 m_char_select.set_vector(&m_char);
919 *
this = std::move(tmp);
928 m_char = std::move(strat.m_char);
929 m_char_rank = std::move(strat.m_char_rank);
930 m_char_rank.set_vector(&m_char);
931 m_char_select = std::move(strat.m_char_select);
932 m_char_select.set_vector(&m_char);
933 m_C = std::move(strat.m_C);
934 m_sigma = std::move(strat.m_sigma);
944 written_bytes += m_char.serialize(out, child,
"m_char");
945 written_bytes += m_char_rank.serialize(out, child,
"m_char_rank");
946 written_bytes += m_char_select.serialize(out, child,
"m_char_select");
947 written_bytes += m_C.serialize(out, child,
"m_C");
948 written_bytes +=
write_member(m_sigma, out, child,
"m_sigma");
950 return written_bytes;
957 m_char_rank.load(in);
958 m_char_rank.set_vector(&m_char);
959 m_char_select.load(in);
960 m_char_select.set_vector(&m_char);
968 return (m_char == other.m_char) && (m_char_rank == other.m_char_rank) &&
969 (m_char_select == other.m_char_select) && (m_C == other.m_C) && (m_sigma == other.m_sigma);
975 template <
typename archive_t>
985 template <
typename archive_t>
990 m_char_rank.set_vector(&m_char);
992 m_char_select.set_vector(&m_char);
#define CEREAL_LOAD_FUNCTION_NAME
#define CEREAL_SAVE_FUNCTION_NAME
A simple space greedy representation for byte alphabets.
byte_alphabet_tag alphabet_category
bool operator!=(byte_alphabet const &other) const noexcept
Inequality operator.
bool operator==(byte_alphabet const &other) const noexcept
Equality operator.
int_vector< 8 > char2comp_type
byte_alphabet & operator=(byte_alphabet &&bas)
const char2comp_type & char2comp
void load(std::istream &in)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
byte_alphabet & operator=(const byte_alphabet &bas)
byte_alphabet(int_vector_buffer< 8 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
byte_alphabet()
Default constructor.
int_vector ::size_type size_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
int_vector< 8 > comp2char_type
byte_alphabet(const byte_alphabet &bas)
size_type serialize(std::ostream &out, structure_tree_node *v, std::string name="") const
byte_alphabet(byte_alphabet &&bas)
const comp2char_type & comp2char
Helper class for the char2comp mapping.
comp_char_type operator[](char_type c) const
char2comp_wrapper(const int_alphabet *strat)
Helper class for the comp2char mapping.
char_type operator[](comp_char_type c) const
comp2char_wrapper(const int_alphabet *strat)
A space-efficient representation for byte alphabets.
int_alphabet & operator=(int_alphabet &&strat)
char2comp_wrapper char2comp_type
comp2char_wrapper comp2char_type
int_alphabet(int_vector_buffer< 0 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
int_alphabet & operator=(const int_alphabet &strat)
bool operator==(int_alphabet const &other) const noexcept
Equality operator.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
int_alphabet(int_alphabet &&strat)
Copy constructor.
int_alphabet_tag alphabet_category
int_vector ::size_type size_type
std::vector< char_type > string_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize method.
int_alphabet()
Default constructor.
void load(std::istream &in)
Load method.
int_alphabet(const int_alphabet &strat)
Copy constructor.
const comp2char_type comp2char
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
const char2comp_type char2comp
bool operator!=(int_alphabet const &other) const noexcept
Inequality operator.
uint64_t size() const
Returns the number of elements currently stored.
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Helper class for the char2comp and comp2char mapping.
mapping_wrapper()=default
Default constructor.
constexpr char_type operator[](char_type const c) const noexcept
Random access operator.
Provides an alphabet mapping that implements an identity map (i.e.
plain_byte_alphabet & operator=(plain_byte_alphabet &&strat) noexcept
Move assignment.
int_vector ::size_type size_type
plain_byte_alphabet(plain_byte_alphabet const &strat)
Copy constructor.
plain_byte_alphabet & operator=(plain_byte_alphabet const &strat)
Copy assignment.
mapping_wrapper char2comp_type
mapping_wrapper comp2char_type
const char2comp_type char2comp
plain_byte_alphabet(plain_byte_alphabet &&strat) noexcept
Move constructor.
const comp2char_type comp2char
plain_byte_alphabet()
Default constructor.
plain_byte_alphabet(int_vector_buffer< 8 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
byte_alphabet_tag alphabet_category
Class for in-place construction of sd_vector from a strictly increasing sequence.
void set(size_type i)
Set a bit to 1.
A bit vector which compresses very sparse populated bit vectors by.
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)
Helper class for the char2comp mapping.
comp_char_type operator[](char_type c) const
char2comp_wrapper(const succinct_byte_alphabet *strat)
Helper class for the comp2char mapping.
comp2char_wrapper(const succinct_byte_alphabet *strat)
char_type operator[](comp_char_type c) const
A space-efficient representation for byte alphabets.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
comp2char_wrapper comp2char_type
succinct_byte_alphabet(succinct_byte_alphabet &&strat)
Move constructor.
bool operator==(succinct_byte_alphabet const &other) const noexcept
Equality operator.
succinct_byte_alphabet()
Default constructor.
bool operator!=(succinct_byte_alphabet const &other) const noexcept
Inequality operator.
void load(std::istream &in)
Load method.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
char2comp_wrapper char2comp_type
succinct_byte_alphabet(int_vector_buffer< 8 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
int_vector ::size_type size_type
succinct_byte_alphabet & operator=(const succinct_byte_alphabet &strat)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize method.
succinct_byte_alphabet & operator=(succinct_byte_alphabet &&strat)
const comp2char_type comp2char
succinct_byte_alphabet(const succinct_byte_alphabet &strat)
Copy constructor.
const char2comp_type char2comp
byte_alphabet_tag alphabet_category
int_vector.hpp contains the sdsl::int_vector class.
constexpr char KEY_BWT_INT[]
constexpr char KEY_TEXT[]
constexpr char KEY_TEXT_INT[]
Namespace for the succinct data structure library.
std::enable_if< has_serialize< X >::value, typenameX::size_type >::type serialize(const X &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
constexpr const char * key_bwt< 8 >()
constexpr const char * key_text()
constexpr const char * key_text< 8 >()
void init_char_bitvector(bit_vector_type &char_bv, const std::map< size_type, size_type > &D)
constexpr const char * key_bwt()
bool operator==(const track_allocator< T > &, const track_allocator< U > &)
bool operator!=(const track_allocator< T > &a, const track_allocator< U > &b)
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
uint64_t int_vector_size_type
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
sd_vector.hpp contains the sdsl::sd_vector class, and classes which support rank and select for sd_ve...
Contains declarations and definitions of data structure concepts.
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
typename alphabet_trait< typename t_wt::alphabet_category >::type type