9#ifndef INCLUDED_CSA_ALPHABET_STRATEGY
10#define INCLUDED_CSA_ALPHABET_STRATEGY
65 class rank_support_type = rank_support_scan<>,
66 class select_support_type = select_support_scan<>,
67 class C_array_type = int_vector<>>
68class succinct_byte_alphabet;
70template <
class bit_vector_type = sd_vector<>,
71 class rank_support_type =
typename bit_vector_type::rank_1_type,
72 class select_support_type =
typename bit_vector_type::select_1_type,
73 class C_array_type =
int_vector<>>
76template <u
int8_t
int_w
idth>
82template <u
int8_t
int_w
idth>
100template <
class t_alphabet_strategy>
116template <
class t_wt,
class t_enable =
void>
182 if (0 == len or 0 == text_buf.
size())
184 assert(len <= text_buf.
size());
196 for (
int i = 0; i < 256; ++i)
199 m_char2comp[i] = m_sigma;
200 m_comp2char[
sigma] = i;
201 m_C[m_sigma] = m_C[i];
204 m_comp2char.
resize(m_sigma);
206 for (
int i = (
int)m_sigma; i > 0; --i)
209 for (
int i = 1; i <= (int)m_sigma; ++i)
210 m_C[i] += m_C[i - 1];
219 m_char2comp(bas.m_char2comp),
220 m_comp2char(bas.m_comp2char),
230 m_char2comp(std::move(bas.m_char2comp)),
231 m_comp2char(std::move(bas.m_comp2char)),
232 m_C(std::move(bas.m_C)),
241 *
this = std::move(tmp);
250 m_char2comp = std::move(bas.m_char2comp);
251 m_comp2char = std::move(bas.m_comp2char);
252 m_C = std::move(bas.m_C);
253 m_sigma = std::move(bas.m_sigma);
262 written_bytes += m_char2comp.
serialize(out, child,
"m_char2comp");
263 written_bytes += m_comp2char.
serialize(out, child,
"m_comp2char");
264 written_bytes += m_C.
serialize(out, child,
"m_C");
265 written_bytes +=
write_member(m_sigma, out, child,
"m_sigma");
267 return written_bytes;
272 m_char2comp.
load(in);
273 m_comp2char.
load(in);
281 return (m_char2comp == other.m_char2comp) && (m_comp2char == other.m_comp2char) && (m_C == other.m_C)
282 && (m_sigma == other.m_sigma);
288 return !(*
this == other);
291 template <
typename archive_t>
300 template <
typename archive_t>
320template <
class bit_vector_type,
class rank_support_type,
class select_support_type,
class C_array_type>
355 if (c >= m_strat->m_char.size() or !m_strat->m_char[c])
382 bit_vector_type m_char;
383 rank_support_type m_char_rank;
384 select_support_type m_char_select;
405 if (0 == len or 0 == text_buf.
size())
407 assert(len <= text_buf.
size());
418 for (
int i = 0; i < 256; ++i)
428 for (
int i = (
int)m_sigma; i > 0; --i)
431 for (
int i = 1; i <= (int)m_sigma; ++i)
432 m_C[i] = m_C[i] + m_C[i - 1];
433 assert(m_C[
sigma] == len);
435 util::init_support(m_char_rank, &m_char);
436 util::init_support(m_char_select, &m_char);
445 m_char(strat.m_char),
446 m_char_rank(strat.m_char_rank),
447 m_char_select(strat.m_char_select),
449 m_sigma(strat.m_sigma)
451 m_char_rank.set_vector(&m_char);
452 m_char_select.set_vector(&m_char);
461 m_char(std::move(strat.m_char)),
462 m_char_rank(std::move(strat.m_char_rank)),
463 m_char_select(std::move(strat.m_char_select)),
464 m_C(std::move(strat.m_C)),
465 m_sigma(std::move(strat.m_sigma))
467 m_char_rank.set_vector(&m_char);
468 m_char_select.set_vector(&m_char);
476 *
this = std::move(tmp);
485 m_char = std::move(strat.m_char);
486 m_char_rank = std::move(strat.m_char_rank);
487 m_char_rank.set_vector(&m_char);
488 m_char_select = std::move(strat.m_char_select);
489 m_char_select.set_vector(&m_char);
490 m_C = std::move(strat.m_C);
491 m_sigma = std::move(strat.m_sigma);
501 written_bytes += m_char.serialize(out, child,
"m_char");
502 written_bytes += m_char_rank.serialize(out, child,
"m_char_rank");
503 written_bytes += m_char_select.serialize(out, child,
"m_char_select");
504 written_bytes += m_C.serialize(out, child,
"m_C");
505 written_bytes +=
write_member(m_sigma, out, child,
"m_sigma");
507 return written_bytes;
514 m_char_rank.load(in);
515 m_char_rank.set_vector(&m_char);
516 m_char_select.load(in);
517 m_char_select.set_vector(&m_char);
525 return (m_char == other.m_char) && (m_char_rank == other.m_char_rank) && (m_char_select == other.m_char_select)
526 && (m_C == other.m_C) && (m_sigma == other.m_sigma);
532 return !(*
this == other);
535 template <
typename archive_t>
545 template <
typename archive_t>
550 m_char_rank.set_vector(&m_char);
552 m_char_select.set_vector(&m_char);
558template <
typename bit_vector_type,
typename size_type>
562 auto largest_symbol = (--D.end())->first;
564 for (
auto const & x : D)
566 tmp_char[x.first] = 1;
571template <
typename t_hi_bit_vector,
typename t_select_1,
typename t_select_0,
typename size_type>
573 std::map<size_type, size_type>
const & D)
575 auto largest_symbol = (--D.end())->first;
577 for (
auto const & x : D)
579 builder.
set(x.first);
644 if (0 == len || 0 == text_buf.
size())
647 assert(len <= text_buf.
size());
658 for (
int i = 0; i < 256; ++i)
668 for (
int i = (
int)256; i > 0; --i)
671 for (
int i = 1; i <= (int)256; ++i)
672 m_C[i] += m_C[i - 1];
682 m_sigma(strat.m_sigma)
689 m_C(std::move(strat.m_C)),
690 m_sigma(strat.m_sigma)
699 *
this = std::move(tmp);
709 m_C = std::move(strat.m_C);
710 m_sigma = strat.m_sigma;
720 written_bytes += m_C.
serialize(out, child,
"m_C");
721 written_bytes +=
write_member(m_sigma, out, child,
"m_sigma");
723 return written_bytes;
726 void load(std::istream & in)
732 template <
typename archive_t>
739 template <
typename archive_t>
748 return (m_C == other.m_C) && (m_sigma == other.m_sigma);
753 return !(*
this == other);
769template <
class bit_vector_type,
class rank_support_type,
class select_support_type,
class C_array_type>
804 if (m_strat->m_char.size() > 0)
806 if (c >= m_strat->m_char.size() or !m_strat->m_char[c])
812 if (c >= m_strat->m_sigma)
831 if (m_strat->m_char.size() > 0)
848 bit_vector_type m_char;
849 rank_support_type m_char_rank;
850 select_support_type m_char_select;
855 bool is_continuous_alphabet(std::map<size_type, size_type> & D)
864 return ((--D.end())->first + 1) == D.size();
885 if (0 == len or 0 == text_buf.
size())
887 assert(len <= text_buf.
size());
889 std::map<size_type, size_type> D;
896 if (is_continuous_alphabet(D))
904 assert(D.find(0) != D.end() and 1 == D[0]);
909 for (std::map<size_type, size_type>::const_iterator it = D.begin(), end = D.end(); it != end; ++it)
923 m_char(strat.m_char),
924 m_char_rank(strat.m_char_rank),
925 m_char_select(strat.m_char_select),
927 m_sigma(strat.m_sigma)
929 m_char_rank.set_vector(&m_char);
930 m_char_select.set_vector(&m_char);
939 m_char(std::move(strat.m_char)),
940 m_char_rank(std::move(strat.m_char_rank)),
941 m_char_select(std::move(strat.m_char_select)),
942 m_C(std::move(strat.m_C)),
943 m_sigma(std::move(strat.m_sigma))
945 m_char_rank.set_vector(&m_char);
946 m_char_select.set_vector(&m_char);
954 *
this = std::move(tmp);
963 m_char = std::move(strat.m_char);
964 m_char_rank = std::move(strat.m_char_rank);
965 m_char_rank.set_vector(&m_char);
966 m_char_select = std::move(strat.m_char_select);
967 m_char_select.set_vector(&m_char);
968 m_C = std::move(strat.m_C);
969 m_sigma = std::move(strat.m_sigma);
979 written_bytes += m_char.serialize(out, child,
"m_char");
980 written_bytes += m_char_rank.serialize(out, child,
"m_char_rank");
981 written_bytes += m_char_select.serialize(out, child,
"m_char_select");
982 written_bytes += m_C.serialize(out, child,
"m_C");
983 written_bytes +=
write_member(m_sigma, out, child,
"m_sigma");
985 return written_bytes;
992 m_char_rank.load(in);
993 m_char_rank.set_vector(&m_char);
994 m_char_select.load(in);
995 m_char_select.set_vector(&m_char);
1003 return (m_char == other.m_char) && (m_char_rank == other.m_char_rank) && (m_char_select == other.m_char_select)
1004 && (m_C == other.m_C) && (m_sigma == other.m_sigma);
1010 return !(*
this == other);
1013 template <
typename archive_t>
1023 template <
typename archive_t>
1028 m_char_rank.set_vector(&m_char);
1030 m_char_select.set_vector(&m_char);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#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)
char2comp_type const & char2comp
void load(std::istream &in)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
comp2char_type const & comp2char
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
byte_alphabet(byte_alphabet const &bas)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
int_vector< 8 > comp2char_type
size_type serialize(std::ostream &out, structure_tree_node *v, std::string name="") const
byte_alphabet(byte_alphabet &&bas)
byte_alphabet & operator=(byte_alphabet const &bas)
Helper class for the char2comp mapping.
comp_char_type operator[](char_type c) const
char2comp_wrapper(int_alphabet const *strat)
Helper class for the comp2char mapping.
char_type operator[](comp_char_type c) const
comp2char_wrapper(int_alphabet const *strat)
A space-efficient representation for byte alphabets.
int_alphabet & operator=(int_alphabet &&strat)
char2comp_wrapper char2comp_type
comp2char_wrapper comp2char_type
int_alphabet & operator=(int_alphabet const &strat)
int_alphabet(int_vector_buffer< 0 > &text_buf, int_vector_size_type len)
Construct from a byte-stream.
int_alphabet(int_alphabet const &strat)
Copy constructor.
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.
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.
A generic vector class for integers of width .
int_vector_size_type size_type
void load(std::istream &in)
Load the int_vector for a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
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, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
Helper class for the char2comp mapping.
char2comp_wrapper(succinct_byte_alphabet const *strat)
comp_char_type operator[](char_type c) const
Helper class for the comp2char mapping.
char_type operator[](comp_char_type c) const
comp2char_wrapper(succinct_byte_alphabet const *strat)
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
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
const char2comp_type char2comp
byte_alphabet_tag alphabet_category
succinct_byte_alphabet & operator=(succinct_byte_alphabet const &strat)
succinct_byte_alphabet(succinct_byte_alphabet const &strat)
Copy constructor.
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.
constexpr char KEY_BWT_INT[]
constexpr char KEY_TEXT[]
constexpr char KEY_TEXT_INT[]
Namespace for the succinct data structure library.
constexpr char const * key_bwt< 8 >()
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
constexpr char const * key_text< 8 >()
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
std::enable_if< has_serialize< X >::value, typenameX::size_type >::type serialize(X const &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
constexpr char const * key_bwt()
bool operator==(track_allocator< T > const &, track_allocator< U > const &)
uint64_t int_vector_size_type
bool operator!=(track_allocator< T > const &a, track_allocator< U > const &b)
void init_char_bitvector(bit_vector_type &char_bv, std::map< size_type, size_type > const &D)
constexpr char const * key_text()
rank_support_scan.hpp contains rank_support_scan that support a sdsl::bit_vector with linear time ran...
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_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
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
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.