4#ifndef INCLUDED_SDSL_WT_HELPER
5#define INCLUDED_SDSL_WT_HELPER
39template <
typename t_it,
typename t_rac>
43 for (
auto it = begin; it != end; ++it)
46 if (c >= C.size()) { C.resize(c + 1, 0); }
51template <
typename t_rac,
typename sigma_type>
54 sigma = std::count_if(begin(C), end(C), [](
decltype(*begin(C)) & x) {
return x > 0; });
66 undef = 0xFFFFFFFFFFFFFFFFULL
72 uint64_t child_left =
undef,
73 uint64_t child_right =
undef);
76template <
typename t_tree_strat_fat>
79 using node_type =
typename t_tree_strat_fat::node_type;
89 node_type child_left = t_tree_strat_fat::undef,
90 node_type child_right = t_tree_strat_fat::undef)
95 child[0] = child_left;
96 child[1] = child_right;
127 uint64_t written_bytes = 0;
131 out.write((
char *)
child, 2 *
sizeof(
child[0]));
132 written_bytes += 2 *
sizeof(
child[0]);
134 return written_bytes;
145 template <
typename archive_t>
155 template <
typename archive_t>
169 (
child[0] == other.child[0]) && (
child[1] == other.child[1]);
181template <
bool t_dfs_shape,
typename t_wt>
211 _byte_tree(
const std::vector<pc_node> & temp_nodes, uint64_t & bv_size,
const t_wt *)
213 m_nodes.resize(temp_nodes.size());
214 m_nodes[0] = temp_nodes.back();
218 std::deque<node_type> q;
234 uint64_t frq =
m_nodes[idx].bv_pos;
244 last_parent =
m_nodes[idx].parent;
248 for (uint32_t k = 0; k < 2; ++k)
251 m_nodes[node_cnt].parent = idx;
252 q.push_back(node_cnt);
253 m_nodes[idx].child[k] = node_cnt++;
270 for (uint32_t c = 0, prev_c = 0; c <
fixed_sigma; ++c)
285 if (pl > 56) {
throw std::logic_error(
"Code depth greater than 56!!!"); }
286 m_path[c] = pw | (pl << 56);
292 m_path[c] = prev_c | (pl << 56);
297 template <
typename t_rank_type>
300 for (uint64_t i = 0; i <
m_nodes.size(); ++i)
320 *
this = std::move(tmp);
329 m_nodes = std::move(bt.m_nodes);
340 uint64_t written_bytes = 0;
341 uint64_t m_nodes_size =
m_nodes.size();
349 return written_bytes;
355 uint64_t m_nodes_size = 0;
357 m_nodes = std::vector<data_node>(m_nodes_size);
363 template <
typename archive_t>
371 template <
typename archive_t>
382 return (
m_nodes == other.m_nodes)
408 auto next_v = t_dfs_shape ?
m_nodes[v].child[0] : v + 1;
437 for (uint32_t i = c; i > 0; i--)
447template <
bool t_dfs_shape = false>
450 template <
typename t_wt>
455template <
bool t_dfs_shape,
typename t_wt>
464 undef = 0xFFFFFFFFFFFFFFFFULL
481 _int_tree(
const std::vector<pc_node> & temp_nodes, uint64_t & bv_size,
const t_wt *)
483 m_nodes.resize(temp_nodes.size());
484 m_nodes[0] = temp_nodes.back();
488 std::deque<node_type> q;
505 uint64_t frq =
m_nodes[idx].bv_pos;
513 max_c =
m_nodes[idx].bv_pos_rank;
521 last_parent =
m_nodes[idx].parent;
525 for (uint32_t k = 0; k < 2; ++k)
528 m_nodes[node_cnt].parent = idx;
529 q.push_back(node_cnt);
530 m_nodes[idx].child[k] = node_cnt++;
541 uint64_t c =
m_nodes[v].bv_pos_rank;
543 if (c > max_c) max_c = c;
567 if (l > 56) {
throw std::logic_error(
"Code depth greater than 56!!!"); }
568 m_path[c] = w | (l << 56);
574 m_path[c] = prev_c | (pl << 56);
579 template <
typename t_rank_type>
582 for (uint64_t i = 0; i <
m_nodes.size(); ++i)
599 uint64_t written_bytes = 0;
600 uint64_t m_nodes_size =
m_nodes.size();
604 written_bytes +=
write_member(m_c_to_leaf_size, out,
child,
"m_c_to_leaf.size()");
606 uint64_t m_path_size =
m_path.size();
610 return written_bytes;
616 uint64_t m_nodes_size = 0;
618 m_nodes = std::vector<data_node>(m_nodes_size);
620 uint64_t m_c_to_leaf_size = 0;
622 m_c_to_leaf = std::vector<node_type>(m_c_to_leaf_size);
624 uint64_t m_path_size = 0;
626 m_path = std::vector<uint64_t>(m_path_size);
639 template <
typename archive_t>
647 template <
typename archive_t>
680 auto next_v = t_dfs_shape ?
m_nodes[v].child[0] : v + 1;
703 if (c >=
m_c_to_leaf.size()) {
return {
false, 0 }; }
729template <
bool t_dfs_shape = false>
732 template <
typename t_wt>
736template <
typename t_bv>
759template <
typename t_bv>
784 return std::get<0>(r) == (std::get<1>(r) + 1);
789 return std::get<1>(r) - std::get<0>(r) + 1;
792inline pc_node::pc_node(uint64_t freq, uint64_t sym, uint64_t parent, uint64_t child_left, uint64_t child_right)
797 child[0] = child_left;
798 child[1] = child_right;
A generic vector class for integers of width .
node_bv_container(iterator b, iterator e)
t_bv::size_type size_type
t_bv::const_iterator iterator
value_type operator[](size_type i) const
t_bv::value_type value_type
t_bv::difference_type difference_type
t_bv::size_type size_type
value_type operator[](size_type i) const
node_seq_container(iterator b, iterator e)
t_bv::difference_type difference_type
t_bv::value_type value_type
t_bv::const_iterator iterator
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)
int_vector.hpp contains the sdsl::int_vector class.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
void load_vector(std::vector< T > &, std::istream &)
Load all elements of a vector from a input stream.
void calculate_effective_alphabet_size(const t_rac &C, sigma_type &sigma)
uint64_t serialize_vector(const std::vector< T > &, std::ostream &, sdsl::structure_tree_node *v=nullptr, std::string="")
Serialize each element of an std::vector.
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].
bool empty(const range_type &r)
Empty range check.
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::array< int_vector<>::size_type, 2 > range_type
std::vector< range_type > range_vec_type
int_vector ::size_type size(const range_type &r)
Size of a range.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
uint64_t bv_pos(node_type v) const
Return the start of the node in the WT's bit vector.
void init_node_ranks(const t_rank_type &rank)
node_type m_c_to_leaf[fixed_sigma]
_byte_tree(const _byte_tree &bt)
_byte_tree(const std::vector< pc_node > &temp_nodes, uint64_t &bv_size, const t_wt *)
uint64_t bv_pos_rank(node_type v) const
Returns for node v the rank of 1's up to bv_pos(v)
bool is_valid(node_type v) const
Return if the node is a valid node.
_byte_tree & operator=(_byte_tree &&bt)
std::pair< bool, value_type > symbol_lte(value_type c) const
Return symbol c or the next smaller symbol in the wt.
_byte_tree & operator=(const _byte_tree &bt)
static node_type root()
Return the root node of the tree.
uint64_t bit_path(value_type c) const
Return the path as left/right bit sequence in a uint64_t.
node_type child(node_type v, uint8_t i) const
Return left (i=0) or right (i=1) child node of v.
bool operator==(_byte_tree const &other) const noexcept
Equality operator.
node_type parent(node_type v) const
Return the parent node of v.
uint64_t size(node_type v) const
Return size of an inner node.
uint64_t size() const
Return the number of nodes in the tree.
uint64_t m_path[fixed_sigma]
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
bool operator!=(_byte_tree const &other) const noexcept
Inequality operator.
bool is_leaf(node_type v) const
Return if v is a leaf node.
std::vector< data_node > m_nodes
node_type c_to_leaf(value_type c) const
Get corresponding leaf for symbol c.
void load(std::istream &in)
Loads the data structure from the given istream.
std::pair< bool, value_type > symbol_gte(value_type c) const
Return symbol c or the next larger symbol in the wt.
uint64_t serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
_int_tree & operator=(const _int_tree &bt)=default
_int_tree(const std::vector< pc_node > &temp_nodes, uint64_t &bv_size, const t_wt *)
_int_tree(_int_tree &&bt)=default
uint64_t bv_pos_rank(node_type v) const
Returns for node v the rank of 1's up to bv_pos(v)
void init_node_ranks(const t_rank_type &rank)
std::vector< data_node > m_nodes
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
void load(std::istream &in)
Loads the data structure from the given istream.
uint64_t bit_path(value_type c) const
Return the path as left/right bit sequence in a uint64_t.
static node_type root()
Return the root node of the tree.
bool operator!=(_int_tree const &other) const noexcept
Inequality operator.
uint64_t bv_pos(node_type v) const
Return the start of the node in the WT's bit vector.
node_type child(node_type v, uint8_t i) const
Return left (i=0) or right (i=1) child node of v.
_int_tree(const _int_tree &bt)=default
uint64_t size(node_type v) const
Return size of an inner node.
node_type parent(node_type v) const
Return the parent node of v.
bool is_leaf(node_type v) const
Return if v is a leaf node.
std::vector< uint64_t > m_path
node_type c_to_leaf(value_type c) const
Get corresponding leaf for symbol c.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
bool operator==(_int_tree const &other) const noexcept
Equality operator.
std::pair< bool, value_type > symbol_gte(value_type c) const
Return symbol c or the next larger symbol in the wt.
std::pair< bool, value_type > symbol_lte(value_type c) const
Return symbol c or the next smaller symbol in the wt.
uint64_t size() const
Return the number of nodes in the tree.
std::vector< node_type > m_c_to_leaf
_int_tree & operator=(_int_tree &&bt)=default
uint64_t serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
bool is_valid(node_type v) const
Return if the node is a valid node.
bool operator==(_node const &other) const noexcept
Equality operator.
_node & operator=(const _node &v)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
_node(const _node &)=default
bool operator!=(_node const &other) const noexcept
Inequality operator.
_node(uint64_t bv_pos=0, uint64_t bv_pos_rank=0, node_type parent=t_tree_strat_fat::undef, node_type child_left=t_tree_strat_fat::undef, node_type child_right=t_tree_strat_fat::undef)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
typename t_tree_strat_fat::node_type node_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
_node & operator=(const pc_node &v)
void load(std::istream &in)
pc_node(uint64_t freq=0, uint64_t sym=0, uint64_t parent=undef, uint64_t child_left=undef, uint64_t child_right=undef)