9#ifndef INCLUDED_SDSL_WT_RLMN
10#define INCLUDED_SDSL_WT_RLMN
37template <
class t_alphabet_cat>
47 static std::map<uint64_t, uint64_t>
temp_C()
49 return std::map<uint64_t, uint64_t>();
54 uint64_t max_symbol = (--C.end())->first;
110template <
class t_bitvector = sd_vector<>,
111 class t_rank =
typename t_bitvector::rank_1_type,
112 class t_select =
typename t_bitvector::select_1_type,
113 class t_wt = wt_huff<>>
171 template <
typename t_it>
174 std::string temp_file =
186 for (
auto it =
begin; it !=
end; ++it, ++j)
189 if (last_c != c or it ==
begin)
197 condensed_wt.
close();
200 for (
size_type i = 0, prefix_sum = 0; i < m_C.size(); ++i)
210 for (
auto it =
begin; it !=
end; ++it, ++j)
228 util::init_support(m_bl_rank, &m_bl);
229 util::init_support(m_bf_rank, &m_bf);
230 util::init_support(m_bf_select, &m_bf);
231 util::init_support(m_bl_select, &m_bl);
234 for (
size_type i = 0; i < m_C.size(); ++i)
236 m_C_bf_rank[i] = m_bf_rank(m_C[i]);
246 m_bl_rank(wt.m_bl_rank),
247 m_bf_rank(wt.m_bf_rank),
248 m_bl_select(wt.m_bl_select),
249 m_bf_select(wt.m_bf_select),
251 m_C_bf_rank(wt.m_C_bf_rank)
253 m_bl_rank.set_vector(&m_bl);
254 m_bf_rank.set_vector(&m_bf);
255 m_bl_select.set_vector(&m_bl);
256 m_bf_select.set_vector(&m_bf);
262 m_bl(std::move(wt.m_bl)),
263 m_bf(std::move(wt.m_bf)),
264 m_wt(std::move(wt.m_wt)),
265 m_bl_rank(std::move(wt.m_bl_rank)),
266 m_bf_rank(std::move(wt.m_bf_rank)),
267 m_bl_select(std::move(wt.m_bl_select)),
268 m_bf_select(std::move(wt.m_bf_select)),
269 m_C(std::move(wt.m_C)),
270 m_C_bf_rank(std::move(wt.m_C_bf_rank))
272 m_bl_rank.set_vector(&m_bl);
273 m_bf_rank.set_vector(&m_bf);
274 m_bl_select.set_vector(&m_bl);
275 m_bf_select.set_vector(&m_bf);
284 *
this = std::move(tmp);
294 m_size = std::move(wt.m_size);
295 m_bl = std::move(wt.m_bl);
296 m_bf = std::move(wt.m_bf);
297 m_wt = std::move(wt.m_wt);
298 m_bl_rank = std::move(wt.m_bl_rank);
299 m_bl_rank.set_vector(&m_bl);
300 m_bf_rank = std::move(wt.m_bf_rank);
301 m_bf_rank.set_vector(&m_bf);
302 m_bl_select = std::move(wt.m_bl_select);
303 m_bl_select.set_vector(&m_bl);
304 m_bf_select = std::move(wt.m_bf_select);
305 m_bf_select.set_vector(&m_bf);
306 m_C = std::move(wt.m_C);
307 m_C_bf_rank = std::move(wt.m_C_bf_rank);
334 return m_wt[m_bl_rank(i + 1) - 1];
352 size_type c_runs = m_wt.rank(wt_ex_pos, c);
355 if (m_wt[wt_ex_pos - 1] == c)
357 size_type c_run_begin = m_bl_select(wt_ex_pos);
358 return m_bf_select(m_C_bf_rank[c] + c_runs) - m_C[c] + i - c_run_begin;
362 return m_bf_select(m_C_bf_rank[c] + c_runs + 1) - m_C[c];
378 return std::make_pair(0, m_wt[0]);
381 auto rc = m_wt.inverse_select(wt_ex_pos - 1);
385 return std::make_pair(0, c);
386 if (m_wt[wt_ex_pos - 1] == c)
388 size_type c_run_begin = m_bl_select(wt_ex_pos);
389 return std::make_pair(m_bf_select(m_C_bf_rank[c] + c_runs) - m_C[c] + i - c_run_begin, c);
393 return std::make_pair(m_bf_select(m_C_bf_rank[c] + c_runs + 1) - m_C[c], c);
409 size_type c_runs = m_bf_rank(m_C[c] + i) - m_C_bf_rank[c];
410 size_type offset = m_C[c] + i - 1 - m_bf_select(c_runs + m_C_bf_rank[c]);
411 return m_bl_select(m_wt.select(c_runs, c) + 1) + offset;
431 written_bytes +=
write_member(m_size, out, child,
"size");
432 written_bytes += m_bl.serialize(out, child,
"bl");
433 written_bytes += m_bf.serialize(out, child,
"bf");
434 written_bytes += m_wt.serialize(out, child,
"wt");
435 written_bytes += m_bl_rank.serialize(out, child,
"bl_rank");
436 written_bytes += m_bf_rank.serialize(out, child,
"bf_rank");
437 written_bytes += m_bl_select.serialize(out, child,
"bl_select");
438 written_bytes += m_bf_select.serialize(out, child,
"bf_select");
439 written_bytes += m_C.serialize(out, child,
"C");
440 written_bytes += m_C_bf_rank.serialize(out, child,
"C_bf_rank");
442 return written_bytes;
452 m_bl_rank.load(in, &m_bl);
453 m_bf_rank.load(in, &m_bf);
454 m_bl_select.load(in, &m_bl);
455 m_bf_select.load(in, &m_bf);
457 m_C_bf_rank.load(in);
461 template <
typename archive_t>
477 template <
typename archive_t>
485 m_bl_rank.set_vector(&m_bl);
487 m_bf_rank.set_vector(&m_bf);
489 m_bl_select.set_vector(&m_bl);
491 m_bf_select.set_vector(&m_bf);
499 return (m_size == other.m_size) && (m_bl == other.m_bl) && (m_bf == other.m_bf) && (m_wt == other.m_wt)
500 && (m_bl_rank == other.m_bl_rank) && (m_bf_rank == other.m_bf_rank) && (m_bl_select == other.m_bl_select)
501 && (m_bf_select == other.m_bf_select) && (m_C == other.m_C) && (m_C_bf_rank == other.m_C_bf_rank);
507 return !(*
this == other);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
void close(bool remove_file=false)
Close the int_vector_buffer.
void push_back(const uint64_t value)
Appends the given element value to the end of the int_vector_buffer.
int_vector_size_type size_type
size_type size() const noexcept
The number of elements in the int_vector.
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)
t_bitvector bit_vector_type
wt_rlmn_trait< alphabet_category >::C_bf_rank_type C_bf_rank_type
t_wt::alphabet_category alphabet_category
random_access_const_iterator< wt_rlmn > const_iterator
wt_rlmn_trait< alphabet_category >::C_type C_type
bool operator==(wt_rlmn const &other) const noexcept
Equality operator.
size_type rank(size_type i, value_type c) const
Calculates how many symbols c are in the prefix [0..i-1].
t_select select_support_type
size_type size() const
Returns the size of the original vector.
wt_rlmn & operator=(wt_rlmn const &wt)
Assignment operator.
t_wt::value_type value_type
void load(std::istream &in)
Loads the data structure from the given istream.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
bool empty() const
Returns whether the wavelet tree contains no data.
wt_rlmn(wt_rlmn &&wt)
Move constructor.
wt_rlmn(wt_rlmn const &wt)
Copy constructor.
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
bool operator!=(wt_rlmn const &other) const noexcept
Inequality operator.
wt_rlmn(t_it begin, t_it end, std::string tmp_dir=ram_file_name(""))
Construct the wavelet tree from a sequence defined by two interators.
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.
const_iterator begin() const
Returns a const_iterator to the first element.
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_bitvector::difference_type difference_type
wt_rlmn & operator=(wt_rlmn &&wt)
Assignment move operator.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
const_iterator end() const
Returns a const_iterator to the element after the last element.
size_type select(size_type i, value_type c) const
Calculates the ith occurrence of the symbol c in the supported vector.
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.
std::string to_string(T const &t, int w=1)
Namespace for the succinct data structure library.
int remove(std::string const &)
Remove a file.
std::string ram_file_name(std::string const &file)
Returns the corresponding RAM-file name for file.
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)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
int_vector ::size_type size(range_type const &r)
Size of a range.
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.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
int_vector< 64 > C_bf_rank_type
static C_bf_rank_type init_C_bf_rank(C_type const &, uint64_t)
static C_type init_C(C_type &C, uint64_t)
static int_vector< 64 > temp_C()
static C_type init_C(std::map< uint64_t, uint64_t > &C, uint64_t size)
static C_bf_rank_type init_C_bf_rank(C_type const &C, uint64_t size)
int_vector C_bf_rank_type
static std::map< uint64_t, uint64_t > temp_C()
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.
wt_huff.hpp contains a class for a Huffman shaped wavelet tree over byte sequences.