9#ifndef INCLUDED_SDSL_WM_INT
10#define INCLUDED_SDSL_WM_INT
60 class t_rank =
typename t_bitvector::rank_1_type,
61 class t_select =
typename t_bitvector::select_1_type,
62 class t_select_zero =
typename t_bitvector::select_0_type>
116 template <
typename t_it>
124 for (
auto it =
begin; it !=
end; ++it)
127 if (value > max_elem)
131 std::string tree_out_buf_file_name =
tmp_file(tmp_dir,
"_m_tree");
137 std::string zero_buf_file_name =
tmp_file(tmp_dir,
"_zero_buf");
138 osfstream tree_out_buf(tree_out_buf_file_name,
139 std::ios::binary | std::ios::trunc | std::ios::out);
144 uint64_t tree_word = 0;
151 const uint64_t mask = 1ULL << width;
155 for (
size_t i = 0; i <
m_size; ++i)
160 tree_word |= (1ULL << (tree_pos & 0x3FULL));
168 if ((tree_pos & 0x3FULL) == 0)
170 tree_out_buf.write((
char *)&tree_word,
sizeof(tree_word));
175 for (
size_t i = zeros; i <
m_size; ++i)
177 rac[i] = zero_buf[i - zeros];
180 if ((tree_pos & 0x3FULL) != 0)
182 tree_out_buf.write((
char *)&tree_word,
sizeof(tree_word));
185 tree_out_buf.
close();
264 m_tree = std::move(wt.m_tree);
311 auto rank_zeros = (i - k *
m_size) - rank_ones;
312 i = (k + 1) *
m_size + rank_zeros;
387 return std::make_pair(i, c);
401 assert(1 <= i and i <=
rank(
size(), c));
405 m_path_off[0] = m_path_rank_off[0] = 0;
424 m_path_off[k + 1] = b;
425 m_path_rank_off[k] = rank_b;
430 b = m_path_off[k - 1];
431 size_type rank_b = m_path_rank_off[k - 1];
454 std::pair<size_type, std::vector<std::pair<value_type, size_type>>>
468 _range_search_2d(
root(), {{lb, rb}}, vlb, vrb, 0, is, rank_off, point_vec, report, cnt_answers);
470 return make_pair(cnt_answers, point_vec);
478 std::vector<size_type> & is,
479 std::vector<size_type> & rank_off,
485 if (get<0>(r) > get<1>(r))
509 point_vec.emplace_back(is[0] + i - 1, v.
sym);
524 if (!
sdsl::empty(get<0>(c_r)) and vlb < mid and mid)
529 std::min(vrb, mid - 1),
571 written_bytes +=
m_tree.serialize(out, child,
"tree");
572 written_bytes +=
m_tree_rank.serialize(out, child,
"tree_rank");
573 written_bytes +=
m_tree_select1.serialize(out, child,
"tree_select_1");
574 written_bytes +=
m_tree_select0.serialize(out, child,
"tree_select_0");
579 return written_bytes;
597 template <
typename archive_t>
612 template <
typename archive_t>
641 return !(*
this == other);
719 auto rs =
expand(vv, {0, i});
720 bool bit = *(
begin(vv) + i);
721 i = std::get<1>(rs[bit]);
755 return expand(std::move(v_right));
771 v_left.
size = v.size - ones;
772 v_left.
level = v.level + 1;
773 v_left.
sym = v.sym << 1;
777 v.level = v.level + 1;
778 v.sym = (v.sym << 1) | 1;
780 return {{std::move(v_left), v}};
795 auto ranges_copy = ranges;
796 return expand(v, std::move(ranges_copy));
814 for (
auto & r : ranges)
818 auto left_size = (r[1] - r[0] + 1) - right_size;
820 auto right_sp = sp_rank - v_sp_rank;
821 auto left_sp = r[0] - right_sp;
823 r = {{left_sp, left_sp + left_size - 1}};
824 res[i++] = {{right_sp, right_sp + right_size - 1}};
826 return {{ranges, std::move(res)}};
844 auto left_size = (r[1] - r[0] + 1) - right_size;
846 auto right_sp = sp_rank - v_sp_rank;
847 auto left_sp = r[0] - right_sp;
849 return {{{{left_sp, left_sp + left_size - 1}}, {{right_sp, right_sp + right_size - 1}}}};
860 auto begin(node_type
const & v)
const ->
decltype(
m_tree.begin() + v.offset)
862 return m_tree.begin() + v.offset;
866 auto end(node_type
const & v)
const ->
decltype(
m_tree.begin() + v.offset + v.size)
868 return m_tree.begin() + v.offset + v.size;
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
void push_back(const uint64_t value)
Appends the given element value to the end of the int_vector_buffer.
A generic vector class for integers of width .
int_vector_size_type size_type
static uint64_t write_header(uint64_t size, uint8_t int_width, std::ostream &out)
Write the size and int_width of a int_vector.
iterator end() noexcept
Iterator that points to the element after the last element of int_vector.
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.
int_vector_trait< t_width >::value_type value_type
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
void close()
Close the 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)
A wavelet tree class for integer sequences.
std::vector< point_type > point_vec_type
const_iterator end() const
Returns a const_iterator to the element after the last element.
size_type const & sigma
Effective alphabet size of the wavelet tree.
void load(std::istream &in)
Loads the data structure from the given istream.
bool empty(node_type const &v) const
Indicates if node v is empty.
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
void _range_search_2d(node_type v, range_type r, value_type vlb, value_type vrb, size_type ilb, std::vector< size_type > &is, std::vector< size_type > &rank_off, point_vec_type &point_vec, bool report, size_type &cnt_answers) const
t_bitvector bit_vector_type
t_select_zero select_0_type
std::array< range_type, 2 > expand(node_type const &v, range_type const &r) const
Returns for a range its left and right child ranges.
auto seq(node_type const &v) const -> random_access_container< std::function< value_type(size_type)> >
Random access container to sequence of node v.
std::array< range_vec_type, 2 > expand(node_type const &v, range_vec_type &&ranges) const
Returns for each range its left and right child ranges.
wm_int(wm_int const &wt)
Copy constructor.
int_alphabet_tag alphabet_category
int_vector ::size_type size_type
auto size(node_type const &v) const -> decltype(v.size)
Return the size of node v.
std::pair< uint64_t, uint64_t > path(value_type c) const
return the path to the leaf for a given symbol
std::pair< size_type, value_type > inverse_select(size_type i) const
Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence.
std::array< node_type, 2 > expand(node_type &&v) const
Returns the two child nodes of an inner node.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
std::pair< size_type, point_vec_type > r2d_res_type
std::pair< size_type, std::vector< std::pair< value_type, size_type > > > range_search_2d(size_type lb, size_type rb, value_type vlb, value_type vrb, bool report=true) const
range_search_2d searches points in the index interval [lb..rb] and value interval [vlb....
size_type size() const
Returns the size of the original vector.
wm_int & operator=(wm_int const &wt)
Assignment operator.
int_vector< 64 > m_rank_level
bool operator==(wm_int const &other) const noexcept
Equality operator.
t_bitvector::difference_type difference_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
random_access_const_iterator< wm_int > const_iterator
const_iterator begin() const
Returns a const_iterator to the first element.
bool empty() const
Returns whether the wavelet tree contains no data.
wm_int()=default
Default constructor.
int_vector< 64 > m_zero_cnt
bit_vector_type const & tree
A concatenation of all bit vectors of the wavelet tree.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
int_vector ::value_type value_type
bool is_leaf(node_type const &v) const
Checks if the node is a leaf node.
uint32_t const & max_level
Maximal level of the wavelet tree.
bool operator!=(wm_int const &other) const noexcept
Inequality operator.
node_type root() const
Return the root node.
size_type rank(size_type i, value_type c) const
Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.
value_type sym(node_type const &v) const
Symbol of leaf node v.
select_1_type m_tree_select1
std::pair< value_type, size_type > point_type
size_type select(size_type i, value_type c) const
Calculates the i-th occurrence of the symbol c in the supported vector.
select_0_type m_tree_select0
wm_int & operator=(wm_int &&wt)
Assignment move operator.
std::array< range_vec_type, 2 > expand(node_type const &v, range_vec_type const &ranges) const
Returns for each range its left and right child ranges.
wm_int(t_it begin, t_it end, std::string tmp_dir=ram_file_name(""))
Construct the wavelet tree from a sequence defined by two interators.
auto bit_vec(node_type const &v) const -> node_bv_container< t_bitvector >
Random access container to bitvector of node v.
wm_int(wm_int &&wt)
Move copy constructor.
std::array< node_type, 2 > expand(node_type const &v) const
Returns the two child nodes of an inner node.
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.
Namespace for the succinct data structure library.
int remove(std::string const &)
Remove a file.
std::string tmp_file(cache_config const &config, std::string name_part="")
Returns a name for a temporary file. I.e. the name was not used before.
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="")
bool load_from_file(T &v, std::string const &file)
Load sdsl-object v from a file.
void read_member(T &t, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
std::array< int_vector<>::size_type, 2 > range_type
bool empty(range_type const &r)
Empty range check.
int_vector ::size_type size(range_type const &r)
Size of a range.
std::vector< range_type > range_vec_type
Contains declarations and definitions of data structure concepts.
sfstream.hpp contains a two stream class which can be used to read/write from/to files or strings.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Represents a node in the wavelet tree.
node_type(node_type const &)=default
node_type & operator=(node_type const &)=default
bool operator>(node_type const &v) const
bool operator<(node_type const &v) const
node_type(node_type &&)=default
node_type & operator=(node_type &&)=default
node_type(size_type o=0, size_type sz=0, size_type l=0, value_type sy=0)
bool operator==(node_type const &v) const
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.