8#ifndef INCLUDED_SDSL_LOUDS_TREE
9#define INCLUDED_SDSL_LOUDS_TREE
43 return m_nr == v.m_nr and m_pos == v.m_pos;
54 os <<
"(" << v.
nr <<
"," << v.
pos <<
")";
71 class select_1_t =
typename bit_vec_t::select_1_type,
72 class select_0_t =
typename bit_vec_t::select_0_type>
91 template <
class Cst,
class CstBfsIterator>
92 louds_tree(Cst
const & cst,
const CstBfsIterator begin,
const CstBfsIterator end) :
101 for (CstBfsIterator it = begin; it != end;)
106 pos += it.size() + 1 -
size;
111 util::init_support(m_bv_select1, &m_bv);
112 util::init_support(m_bv_select0, &m_bv);
117 m_bv_select1(lt.m_bv_select1),
118 m_bv_select0(lt.m_bv_select0),
121 m_bv_select1.set_vector(&m_bv);
122 m_bv_select0.set_vector(&m_bv);
127 *
this = std::move(lt);
135 *
this = std::move(tmp);
144 m_bv = std::move(lt.m_bv);
145 m_bv_select1 = std::move(lt.m_bv_select1);
146 m_bv_select1.set_vector(&m_bv);
147 m_bv_select0 = std::move(lt.m_bv_select0);
148 m_bv_select0.set_vector(&m_bv);
162 return (m_bv.size() + 1) / 2;
171 return (v.
pos + 1 == m_bv.size()) or m_bv[v.
pos + 1];
185 return m_bv_select1(v.
nr + 2) - v.
pos - 1;
199 return louds_node(zeros, m_bv_select1(zeros + 1));
211 return node_type(parent_nr, m_bv_select1(parent_nr + 1));
224 written_bytes += m_bv.serialize(out,
child,
"bitvector");
225 written_bytes += m_bv_select1.serialize(out,
child,
"select1");
226 written_bytes += m_bv_select0.serialize(out,
child,
"select0");
228 return written_bytes;
234 m_bv_select1.load(in);
235 m_bv_select1.set_vector(&m_bv);
236 m_bv_select0.load(in);
237 m_bv_select0.set_vector(&m_bv);
241 template <
typename archive_t>
250 template <
typename archive_t>
255 m_bv_select1.set_vector(&m_bv);
257 m_bv_select0.set_vector(&m_bv);
cereal.hpp offers cereal support
int_vector_size_type size_type
size_type size() const noexcept
The number of elements in the int_vector.
void shrink_to_fit()
Free unused allocated memory.
void resize(const size_type size)
Resize the int_vector in terms of elements.
A class for the node representation of louds_tree.
bool operator==(louds_node const &v) const
bit_vector::size_type size_type
louds_node(size_type f_nr=0, size_type f_pos=0)
bool operator!=(louds_node const &v) const
A tree class based on the level order unary degree sequence (LOUDS) representation.
louds_tree(Cst const &cst, const CstBfsIterator begin, const CstBfsIterator end)
Constructor for a cst and a root node for the traversal.
node_type child(node_type const &v, size_type i) const
Returns the i-child of a node.
louds_tree(louds_tree &<)
louds_tree(louds_tree const <)
size_type id(node_type const &v) const
Returns an unique id for each node in [0..size()-1].
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
node_type root() const
Returns the root node.
size_type nodes() const
Returns the number of nodes in the tree.
louds_tree & operator=(louds_tree const <)
bit_vector::size_type size_type
void load(std::istream &in)
size_type degree(node_type const &v) const
Returns the number of children of a node.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
bool is_leaf(node_type const &v) const
Indicates if a node is a leaf.
node_type parent(node_type const &v) const
Returns the parent of a node v or root() if v==root().
bit_vec_t bit_vector_type
bit_vector_type const & bv
louds_tree & operator=(louds_tree &<)
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.
Namespace for the succinct data structure library.
std::ostream & operator<<(std::ostream &os, bp_interval< t_int > const &interval)
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.
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.