8#ifndef INCLUDED_SDSL_LOUDS_TREE
9#define INCLUDED_SDSL_LOUDS_TREE
47 os <<
"(" << v.
nr <<
"," << v.
pos <<
")";
64 class select_1_t =
typename bit_vec_t::select_1_type,
65 class select_0_t =
typename bit_vec_t::select_0_type>
83 template <
class Cst,
class CstBfsIterator>
84 louds_tree(
const Cst & cst,
const CstBfsIterator begin,
const CstBfsIterator end)
93 for (CstBfsIterator it = begin; it != end;)
98 pos += it.size() + 1 -
size;
103 util::init_support(m_bv_select1, &m_bv);
104 util::init_support(m_bv_select0, &m_bv);
109 , m_bv_select1(lt.m_bv_select1)
110 , m_bv_select0(lt.m_bv_select0)
113 m_bv_select1.set_vector(&m_bv);
114 m_bv_select0.set_vector(&m_bv);
120 *
this = std::move(lt);
128 *
this = std::move(tmp);
137 m_bv = std::move(lt.m_bv);
138 m_bv_select1 = std::move(lt.m_bv_select1);
139 m_bv_select1.set_vector(&m_bv);
140 m_bv_select0 = std::move(lt.m_bv_select0);
141 m_bv_select0.set_vector(&m_bv);
158 return (v.
pos + 1 == m_bv.size()) or m_bv[v.
pos + 1];
172 return m_bv_select1(v.
nr + 2) - v.
pos - 1;
186 return louds_node(zeros, m_bv_select1(zeros + 1));
195 return node_type(parent_nr, m_bv_select1(parent_nr + 1));
205 written_bytes += m_bv.serialize(out,
child,
"bitvector");
206 written_bytes += m_bv_select1.serialize(out,
child,
"select1");
207 written_bytes += m_bv_select0.serialize(out,
child,
"select0");
209 return written_bytes;
215 m_bv_select1.load(in);
216 m_bv_select1.set_vector(&m_bv);
217 m_bv_select0.load(in);
218 m_bv_select0.set_vector(&m_bv);
222 template <
typename archive_t>
231 template <
typename archive_t>
236 m_bv_select1.set_vector(&m_bv);
238 m_bv_select0.set_vector(&m_bv);
int_vector_size_type size_type
void shrink_to_fit()
Free unused allocated memory.
size_type size() const noexcept
The number of elements in the int_vector.
void resize(const size_type size)
Resize the int_vector in terms of elements.
A class for the node representation of louds_tree.
bit_vector::size_type size_type
bool operator==(const louds_node &v) const
bool operator!=(const louds_node &v) const
louds_node(size_type f_nr=0, size_type f_pos=0)
A tree class based on the level order unary degree sequence (LOUDS) representation.
size_type degree(const node_type &v) const
Returns the number of children of a node.
node_type child(const node_type &v, size_type i) const
Returns the i-child of a node.
louds_tree(louds_tree &<)
node_type parent(const node_type &v) const
Returns the parent of a node v or root() if v==root().
louds_tree(const louds_tree <)
louds_tree & operator=(const louds_tree <)
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.
size_type id(const node_type &v) const
Returns an unique id for each node in [0..size()-1].
louds_tree(const Cst &cst, const CstBfsIterator begin, const CstBfsIterator end)
Constructor for a cst and a root node for the traversal.
bit_vector::size_type size_type
void load(std::istream &in)
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(const node_type &v) const
Indicates if a node is a leaf.
const bit_vector_type & bv
bit_vec_t bit_vector_type
louds_tree & operator=(louds_tree &<)
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.
Namespace for the succinct data structure library.
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
int_vector ::size_type size(const range_type &r)
Size of a range.
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.