4#ifndef INCLUDED_SDSL_WT_HELPER
5#define INCLUDED_SDSL_WT_HELPER
27typedef std::array<int_vector<>::size_type, 2>
range_type;
46template <
typename t_it,
typename t_rac>
50 for (
auto it = begin; it != end; ++it)
61template <
typename t_rac,
typename sigma_type>
64 sigma = std::count_if(begin(C),
66 [](
decltype(*begin(C)) & x)
81 undef = 0xFFFFFFFFFFFFFFFFULL
87 uint64_t child_left =
undef,
88 uint64_t child_right =
undef);
91template <
typename t_tree_strat_fat>
94 using node_type =
typename t_tree_strat_fat::node_type;
104 node_type child_left = t_tree_strat_fat::undef,
105 node_type child_right = t_tree_strat_fat::undef) :
110 child[0] = child_left;
111 child[1] = child_right;
142 uint64_t written_bytes = 0;
146 out.write((
char *)
child, 2 *
sizeof(
child[0]));
147 written_bytes += 2 *
sizeof(
child[0]);
149 return written_bytes;
160 template <
typename archive_t>
170 template <
typename archive_t>
184 && (
child[0] == other.child[0]) && (
child[1] == other.child[1]);
190 return !(*
this == other);
199template <
bool t_dfs_shape,
typename t_wt>
230 _byte_tree(std::vector<pc_node>
const & temp_nodes, uint64_t & bv_size, t_wt
const *)
232 m_nodes.resize(temp_nodes.size());
233 m_nodes[0] = temp_nodes.back();
237 std::deque<node_type> q;
253 uint64_t frq =
m_nodes[idx].bv_pos;
263 last_parent =
m_nodes[idx].parent;
267 for (uint32_t k = 0; k < 2; ++k)
270 m_nodes[node_cnt].parent = idx;
271 q.push_back(node_cnt);
272 m_nodes[idx].child[k] = node_cnt++;
289 for (uint32_t c = 0, prev_c = 0; c <
fixed_sigma; ++c)
306 throw std::logic_error(
"Code depth greater than 56!!!");
308 m_path[c] = pw | (pl << 56);
314 m_path[c] = prev_c | (pl << 56);
319 template <
typename t_rank_type>
322 for (uint64_t i = 0; i <
m_nodes.size(); ++i)
343 *
this = std::move(tmp);
352 m_nodes = std::move(bt.m_nodes);
365 uint64_t written_bytes = 0;
366 uint64_t m_nodes_size =
m_nodes.size();
374 return written_bytes;
380 uint64_t m_nodes_size = 0;
382 m_nodes = std::vector<data_node>(m_nodes_size);
388 template <
typename archive_t>
396 template <
typename archive_t>
407 return (
m_nodes == other.m_nodes)
415 return !(*
this == other);
455 auto next_v = t_dfs_shape ?
m_nodes[v].child[0] : v + 1;
499 for (uint32_t i = c; i > 0; i--)
513template <
bool t_dfs_shape = false>
516 template <
typename t_wt>
521template <
bool t_dfs_shape,
typename t_wt>
530 undef = 0xFFFFFFFFFFFFFFFFULL
547 _int_tree(std::vector<pc_node>
const & temp_nodes, uint64_t & bv_size, t_wt
const *)
549 m_nodes.resize(temp_nodes.size());
550 m_nodes[0] = temp_nodes.back();
554 std::deque<node_type> q;
571 uint64_t frq =
m_nodes[idx].bv_pos;
579 max_c =
m_nodes[idx].bv_pos_rank;
587 last_parent =
m_nodes[idx].parent;
591 for (uint32_t k = 0; k < 2; ++k)
594 m_nodes[node_cnt].parent = idx;
595 q.push_back(node_cnt);
596 m_nodes[idx].child[k] = node_cnt++;
607 uint64_t c =
m_nodes[v].bv_pos_rank;
636 throw std::logic_error(
"Code depth greater than 56!!!");
638 m_path[c] = w | (l << 56);
644 m_path[c] = prev_c | (pl << 56);
649 template <
typename t_rank_type>
652 for (uint64_t i = 0; i <
m_nodes.size(); ++i)
669 uint64_t written_bytes = 0;
670 uint64_t m_nodes_size =
m_nodes.size();
674 written_bytes +=
write_member(m_c_to_leaf_size, out,
child,
"m_c_to_leaf.size()");
676 uint64_t m_path_size =
m_path.size();
680 return written_bytes;
686 uint64_t m_nodes_size = 0;
688 m_nodes = std::vector<data_node>(m_nodes_size);
690 uint64_t m_c_to_leaf_size = 0;
692 m_c_to_leaf = std::vector<node_type>(m_c_to_leaf_size);
694 uint64_t m_path_size = 0;
696 m_path = std::vector<uint64_t>(m_path_size);
709 return !(*
this == other);
712 template <
typename archive_t>
720 template <
typename archive_t>
768 auto next_v = t_dfs_shape ?
m_nodes[v].child[0] : v + 1;
839template <
bool t_dfs_shape = false>
842 template <
typename t_wt>
846template <
typename t_bv>
863 return *(m_begin + i);
867 return m_end - m_begin;
879template <
typename t_bv>
896 return *(m_begin + i);
900 return m_end - m_begin;
914 return std::get<0>(r) == (std::get<1>(r) + 1);
919 return std::get<1>(r) - std::get<0>(r) + 1;
922inline pc_node::pc_node(uint64_t freq, uint64_t sym, uint64_t parent, uint64_t child_left, uint64_t child_right) :
927 child[0] = child_left;
928 child[1] = child_right;
cereal.hpp offers cereal support
int_vector_size_type size_type
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, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
Namespace for the succinct data structure library.
void calculate_effective_alphabet_size(t_rac const &C, sigma_type &sigma)
void load_vector(std::vector< T > &, std::istream &)
Load all elements of a vector from a input stream.
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)
uint64_t serialize_vector(std::vector< T > const &, std::ostream &, sdsl::structure_tree_node *v=nullptr, std::string="")
Serialize each element of an std::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.
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.
_byte_tree & operator=(_byte_tree const &bt)
node_type m_c_to_leaf[fixed_sigma]
_byte_tree(_byte_tree const &bt)
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.
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.
void init_node_ranks(t_rank_type const &rank)
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.
_byte_tree(std::vector< pc_node > const &temp_nodes, uint64_t &bv_size, t_wt const *)
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(_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)
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 & operator=(_int_tree const &bt)=default
_int_tree(std::vector< pc_node > const &temp_nodes, uint64_t &bv_size, t_wt const *)
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
_int_tree(_int_tree const &bt)=default
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.
void init_node_ranks(t_rank_type const &rank)
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.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
_node & operator=(pc_node const &v)
bool operator!=(_node const &other) const noexcept
Inequality operator.
_node(_node const &)=default
_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)
_node & operator=(_node const &v)
typename t_tree_strat_fat::node_type node_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
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)
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.