SDSL 3.0.1
Succinct Data Structure Library
louds_tree.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef INCLUDED_SDSL_LOUDS_TREE
9#define INCLUDED_SDSL_LOUDS_TREE
10
11#include <ostream>
12
13#include <sdsl/int_vector.hpp>
14#include <sdsl/util.hpp>
15
17namespace sdsl
18{
19
22{
23 public:
25
26 private:
27 size_type m_nr; // node number
28 size_type m_pos; // position in the LOUDS
29 public:
30 const size_type & nr;
31 const size_type & pos;
32
33 louds_node(size_type f_nr = 0, size_type f_pos = 0)
34 : m_nr(f_nr)
35 , m_pos(f_pos)
36 , nr(m_nr)
37 , pos(m_pos)
38 {}
39
40 bool operator==(const louds_node & v) const { return m_nr == v.m_nr and m_pos == v.m_pos; }
41
42 bool operator!=(const louds_node & v) const { return !(v == *this); }
43};
44
45inline std::ostream & operator<<(std::ostream & os, const louds_node & v)
46{
47 os << "(" << v.nr << "," << v.pos << ")";
48 return os;
49}
50
52
63template <class bit_vec_t = bit_vector,
64 class select_1_t = typename bit_vec_t::select_1_type,
65 class select_0_t = typename bit_vec_t::select_0_type>
67{
68 public:
71 typedef bit_vec_t bit_vector_type;
72 typedef select_1_t select_1_type;
73 typedef select_0_t select_0_type;
74
75 private:
76 bit_vector_type m_bv; // bit vector for the LOUDS sequence
77 select_1_type m_bv_select1; // select support for 1-bits on m_bv
78 select_0_type m_bv_select0; // select support for 0-bits on m_bv
79 public:
80 const bit_vector_type & bv; // const reference to the LOUDS sequence
81
83 template <class Cst, class CstBfsIterator>
84 louds_tree(const Cst & cst, const CstBfsIterator begin, const CstBfsIterator end)
85 : m_bv()
86 , m_bv_select1()
87 , m_bv_select0()
88 , bv(m_bv)
89 {
90 bit_vector tmp_bv(4 * cst.size(*begin), 0); // resize the bit_vector to the maximal
91 // possible size 2*2*#leaves in the tree
92 size_type pos = 0;
93 for (CstBfsIterator it = begin; it != end;)
94 {
95 tmp_bv[pos++] = 1;
96 size_type size = it.size();
97 ++it;
98 pos += it.size() + 1 - size;
99 }
100 tmp_bv.resize(pos);
101 tmp_bv.shrink_to_fit();
102 m_bv = bit_vector_type(std::move(tmp_bv));
103 util::init_support(m_bv_select1, &m_bv);
104 util::init_support(m_bv_select0, &m_bv);
105 }
106
108 : m_bv(lt.m_bv)
109 , m_bv_select1(lt.m_bv_select1)
110 , m_bv_select0(lt.m_bv_select0)
111 , bv(m_bv)
112 {
113 m_bv_select1.set_vector(&m_bv);
114 m_bv_select0.set_vector(&m_bv);
115 }
116
118 : bv(m_bv)
119 {
120 *this = std::move(lt);
121 }
122
124 {
125 if (this != &lt)
126 {
127 louds_tree tmp(lt);
128 *this = std::move(tmp);
129 }
130 return *this;
131 }
132
134 {
135 if (this != &lt)
136 {
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);
142 }
143 return *this;
144 }
145
147 node_type root() const { return louds_node(0, 0); }
148
150 size_type nodes() const { return (m_bv.size() + 1) / 2; }
151
153
155 bool is_leaf(const node_type & v) const
156 {
157 // node is the last leaf or has no children, so m_bv[v.pos]==1
158 return (v.pos + 1 == m_bv.size()) or m_bv[v.pos + 1];
159 }
160
162
165 size_type degree(const node_type & v) const
166 {
167 if (is_leaf(v))
168 { // handles boundary cases
169 return 0;
170 }
171 // position of the next node - node position - 1
172 return m_bv_select1(v.nr + 2) - v.pos - 1;
173 }
174
176
181 node_type child(const node_type & v, size_type i) const
182 {
183 size_type pos = v.pos + i; // go to the position of the child's zero
184 // (#bits = pos+1) - (#1-bits = v.nr+1)
185 size_type zeros = pos + 1 - (v.nr + 1);
186 return louds_node(zeros, m_bv_select1(zeros + 1));
187 }
188
190 node_type parent(const node_type & v) const
191 {
192 if (v == root()) { return root(); }
193 size_type zero_pos = m_bv_select0(v.nr);
194 size_type parent_nr = (zero_pos + 1) - v.nr - 1;
195 return node_type(parent_nr, m_bv_select1(parent_nr + 1));
196 }
197
199 size_type id(const node_type & v) const { return v.nr; }
200
201 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
202 {
203 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
204 size_type written_bytes = 0;
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");
208 structure_tree::add_size(child, written_bytes);
209 return written_bytes;
210 }
211
212 void load(std::istream & in)
213 {
214 m_bv.load(in);
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);
219 }
220
222 template <typename archive_t>
223 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
224 {
225 ar(CEREAL_NVP(m_bv));
226 ar(CEREAL_NVP(m_bv_select1));
227 ar(CEREAL_NVP(m_bv_select0));
228 }
229
231 template <typename archive_t>
232 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
233 {
234 ar(CEREAL_NVP(m_bv));
235 ar(CEREAL_NVP(m_bv_select1));
236 m_bv_select1.set_vector(&m_bv);
237 ar(CEREAL_NVP(m_bv_select0));
238 m_bv_select0.set_vector(&m_bv);
239 }
240};
241
242} // end namespace sdsl
243#endif
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
int_vector_size_type size_type
Definition: int_vector.hpp:229
void shrink_to_fit()
Free unused allocated memory.
Definition: int_vector.hpp:506
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.
Definition: int_vector.hpp:521
A class for the node representation of louds_tree.
Definition: louds_tree.hpp:22
bit_vector::size_type size_type
Definition: louds_tree.hpp:24
const size_type & nr
Definition: louds_tree.hpp:30
bool operator==(const louds_node &v) const
Definition: louds_tree.hpp:40
bool operator!=(const louds_node &v) const
Definition: louds_tree.hpp:42
const size_type & pos
Definition: louds_tree.hpp:31
louds_node(size_type f_nr=0, size_type f_pos=0)
Definition: louds_tree.hpp:33
A tree class based on the level order unary degree sequence (LOUDS) representation.
Definition: louds_tree.hpp:67
size_type degree(const node_type &v) const
Returns the number of children of a node.
Definition: louds_tree.hpp:165
louds_node node_type
Definition: louds_tree.hpp:70
node_type child(const node_type &v, size_type i) const
Returns the i-child of a node.
Definition: louds_tree.hpp:181
louds_tree(louds_tree &&lt)
Definition: louds_tree.hpp:117
node_type parent(const node_type &v) const
Returns the parent of a node v or root() if v==root().
Definition: louds_tree.hpp:190
louds_tree(const louds_tree &lt)
Definition: louds_tree.hpp:107
louds_tree & operator=(const louds_tree &lt)
Definition: louds_tree.hpp:123
select_1_t select_1_type
Definition: louds_tree.hpp:72
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Definition: louds_tree.hpp:201
node_type root() const
Returns the root node.
Definition: louds_tree.hpp:147
size_type nodes() const
Returns the number of nodes in the tree.
Definition: louds_tree.hpp:150
size_type id(const node_type &v) const
Returns an unique id for each node in [0..size()-1].
Definition: louds_tree.hpp:199
louds_tree(const Cst &cst, const CstBfsIterator begin, const CstBfsIterator end)
Constructor for a cst and a root node for the traversal.
Definition: louds_tree.hpp:84
bit_vector::size_type size_type
Definition: louds_tree.hpp:69
void load(std::istream &in)
Definition: louds_tree.hpp:212
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition: louds_tree.hpp:232
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition: louds_tree.hpp:223
select_0_t select_0_type
Definition: louds_tree.hpp:73
bool is_leaf(const node_type &v) const
Indicates if a node is a leaf.
Definition: louds_tree.hpp:155
const bit_vector_type & bv
Definition: louds_tree.hpp:80
bit_vec_t bit_vector_type
Definition: louds_tree.hpp:71
louds_tree & operator=(louds_tree &&lt)
Definition: louds_tree.hpp:133
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.
Definition: int_vector.hpp:53
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
Definition: cst_sct3.hpp:1331
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.