9#ifndef INCLUDED_SDSL_WT_EPR
10#define INCLUDED_SDSL_WT_EPR
44template <u
int8_t alphabet_size,
class rank_type = rank_support_
int_v<alphabet_size>,
class t_tree_strat =
byte_tree<>>
63 static constexpr bool has_inblock_text = std::is_same<rank_type, rank_support_int_v<alphabet_size>>::value;
71 template <
bool has_inblock_text_>
72 auto construct_init_rank_select(
int_vector<> intermediate_bitvector) -> std::enable_if_t<has_inblock_text_, void>
75 m_bv_rank = rank_type{&intermediate_bitvector};
79 template <
bool has_inblock_text_>
80 auto construct_init_rank_select(
int_vector<> intermediate_bitvector) -> std::enable_if_t<!has_inblock_text_, void>
82 m_bv = std::move(intermediate_bitvector);
83 m_bv_rank = rank_type{&m_bv};
87 template <
bool has_inblock_text_>
88 auto value_at(
size_type const position)
const -> std::enable_if_t<has_inblock_text_, value_type>
90 assert(position <
size());
91 return m_bv_rank.value_at(position);
95 template <
bool has_inblock_text_>
96 auto value_at(
size_type const position)
const -> std::enable_if_t<!has_inblock_text_, value_type>
98 assert(position <
size());
99 return m_bv[position];
115 template <
typename t_it>
124 std::vector<size_type> C;
131 if (m_sigma > alphabet_size)
132 throw std::domain_error{
"The given text uses an alphabet that is larger than the explicitly given "
137 intermediate_bitvector.
width(std::ceil(std::log2(m_sigma)));
138 intermediate_bitvector.resize(m_size);
140 std::copy(
begin,
end, intermediate_bitvector.begin());
143 construct_init_rank_select<has_inblock_text>(std::move(intermediate_bitvector));
146 template <
typename t_it>
151 wt_epr(
wt_epr const & wt) : m_size(wt.m_size), m_sigma(wt.m_sigma), m_bv(wt.m_bv), m_bv_rank(wt.m_bv_rank)
153 m_bv_rank.set_vector(&m_bv);
159 m_bv(std::move(wt.m_bv)),
160 m_bv_rank(std::move(wt.m_bv_rank))
162 m_bv_rank.set_vector(&m_bv);
171 *
this = std::move(tmp);
182 m_sigma = wt.m_sigma;
183 m_bv = std::move(wt.m_bv);
184 m_bv_rank = std::move(wt.m_bv_rank);
185 m_bv_rank.set_vector(&m_bv);
214 return value_at<has_inblock_text>(i);
230 return m_bv_rank.rank(i, c);
246 return std::make_pair(m_bv_rank.rank(i, value), value);
289 template <
class t_ret_type = std::tuple<
size_type,
size_type,
size_type>>
292 assert(i <= j and j <=
size());
301 size_type prefix_i_c = m_bv_rank.prefix_rank(i, c);
303 size_type greater = j - i - m_bv_rank.prefix_rank(j, c) + prefix_i_c;
306 prefix_i_c_1 = m_bv_rank.prefix_rank(i, c - 1);
307 smaller = m_bv_rank.prefix_rank(j, c - 1) - prefix_i_c_1;
311 return t_ret_type{
rank, smaller, greater};
325 template <
class t_ret_type = std::tuple<
size_type,
size_type>>
332 prefix_count_smaller = m_bv_rank.prefix_rank(i, c - 1);
333 return t_ret_type{m_bv_rank.prefix_rank(i, c) - prefix_count_smaller, prefix_count_smaller};
353 written_bytes +=
write_member(m_size, out, child,
"size");
354 written_bytes +=
write_member(m_sigma, out, child,
"sigma");
355 written_bytes += m_bv.
serialize(out, child,
"bv");
356 written_bytes += m_bv_rank.serialize(out, child,
"bv_rank");
358 return written_bytes;
367 m_bv_rank.load(in, &m_bv);
373 return (lhs.m_size == rhs.m_size) && (lhs.m_sigma == rhs.m_sigma) && (lhs.m_bv == rhs.m_bv)
374 && (lhs.m_bv_rank == rhs.m_bv_rank);
380 return !(lhs == rhs);
383 template <
typename archive_t>
392 template <
typename archive_t>
399 m_bv_rank.set_vector(&m_bv);
cereal.hpp offers cereal support
A generic vector class for integers of width .
void load(std::istream &in)
Load the int_vector for a stream.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
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)
An EPR-dictionary based wavelet.
int_vector ::difference_type difference_type
const_iterator begin() const
Returns a const_iterator to the first element.
bool empty() const
Returns whether the wavelet tree contains no data.
auto operator[](size_type const i) const
Recovers the i-th symbol of the original vector.
wt_epr()=default
Default constructor.
int_vector ::size_type size_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
t_ret_type lex_smaller_count(size_type i, value_type c) const
size_type rank(size_type i, value_type c) const
Calculates how many symbols c are in the prefix [0..i-1].
friend bool operator!=(wt_epr const &lhs, wt_epr const &rhs) noexcept
Inequality operator.
const_iterator end() const
Returns a const_iterator to the element after the last element.
size_type size() const
Returns the size of the original vector.
std::pair< size_type, value_type > inverse_select(size_type i) const
Calculates how many times symbol wt[i] occurs in the prefix [0..i-1].
t_ret_type lex_count(size_type i, size_type j, value_type c) const
For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).
wt_epr(t_it begin, t_it end)
Construct the EPR-dictionary from a sequence defined by two interators.
int_vector ::value_type value_type
random_access_const_iterator< wt_epr > const_iterator
wt_epr(t_it begin, t_it end, std::string)
byte_alphabet_tag alphabet_category
void load(std::istream &in)
Loads the data structure from the given istream.
wt_epr & operator=(wt_epr &&wt)
Move assignment operator.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
wt_epr(wt_epr const &wt)
Copy constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
wt_epr & operator=(wt_epr const &wt)
Assignment operator.
t_tree_strat::template type< wt_epr > tree_strat_type
friend bool operator==(wt_epr const &lhs, wt_epr const &rhs) noexcept
Equality operator.
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
void calculate_effective_alphabet_size(t_rac const &C, sigma_type &sigma)
void calculate_character_occurences(t_it begin, t_it end, t_rac &C)
Count for each character the number of occurrences in rac[0..size-1].
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)
rank_support_int_v.hpp contains rank_support_int_v.
Contains declarations and definitions of data structure concepts.
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.