SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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#include <string>
13#include <utility>
14
15#include <sdsl/cereal.hpp>
16#include <sdsl/int_vector.hpp>
18#include <sdsl/util.hpp>
19
21namespace sdsl
22{
23
26{
27public:
29
30private:
31 size_type m_nr; // node number
32 size_type m_pos; // position in the LOUDS
33
34public:
35 size_type const & nr;
36 size_type const & pos;
37
38 louds_node(size_type f_nr = 0, size_type f_pos = 0) : m_nr(f_nr), m_pos(f_pos), nr(m_nr), pos(m_pos)
39 {}
40
41 bool operator==(louds_node const & v) const
42 {
43 return m_nr == v.m_nr and m_pos == v.m_pos;
44 }
45
46 bool operator!=(louds_node const & v) const
47 {
48 return !(v == *this);
49 }
50};
51
52inline std::ostream & operator<<(std::ostream & os, louds_node const & v)
53{
54 os << "(" << v.nr << "," << v.pos << ")";
55 return os;
56}
57
59
70template <class bit_vec_t = bit_vector,
71 class select_1_t = typename bit_vec_t::select_1_type,
72 class select_0_t = typename bit_vec_t::select_0_type>
74{
75public:
78 typedef bit_vec_t bit_vector_type;
79 typedef select_1_t select_1_type;
80 typedef select_0_t select_0_type;
81
82private:
83 bit_vector_type m_bv; // bit vector for the LOUDS sequence
84 select_1_type m_bv_select1; // select support for 1-bits on m_bv
85 select_0_type m_bv_select0; // select support for 0-bits on m_bv
86
87public:
88 bit_vector_type const & bv; // const reference to the LOUDS sequence
89
91 template <class Cst, class CstBfsIterator>
92 louds_tree(Cst const & cst, const CstBfsIterator begin, const CstBfsIterator end) :
93 m_bv(),
94 m_bv_select1(),
95 m_bv_select0(),
96 bv(m_bv)
97 {
98 bit_vector tmp_bv(4 * cst.size(*begin), 0); // resize the bit_vector to the maximal
99 // possible size 2*2*#leaves in the tree
100 size_type pos = 0;
101 for (CstBfsIterator it = begin; it != end;)
102 {
103 tmp_bv[pos++] = 1;
104 size_type size = it.size();
105 ++it;
106 pos += it.size() + 1 - size;
107 }
108 tmp_bv.resize(pos);
109 tmp_bv.shrink_to_fit();
110 m_bv = bit_vector_type(std::move(tmp_bv));
111 util::init_support(m_bv_select1, &m_bv);
112 util::init_support(m_bv_select0, &m_bv);
113 }
114
115 louds_tree(louds_tree const & lt) :
116 m_bv(lt.m_bv),
117 m_bv_select1(lt.m_bv_select1),
118 m_bv_select0(lt.m_bv_select0),
119 bv(m_bv)
120 {
121 m_bv_select1.set_vector(&m_bv);
122 m_bv_select0.set_vector(&m_bv);
123 }
124
125 louds_tree(louds_tree && lt) : bv(m_bv)
126 {
127 *this = std::move(lt);
128 }
129
131 {
132 if (this != &lt)
133 {
134 louds_tree tmp(lt);
135 *this = std::move(tmp);
136 }
137 return *this;
138 }
139
141 {
142 if (this != &lt)
143 {
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);
149 }
150 return *this;
151 }
152
155 {
156 return louds_node(0, 0);
157 }
158
161 {
162 return (m_bv.size() + 1) / 2;
163 }
164
166
168 bool is_leaf(node_type const & v) const
169 {
170 // node is the last leaf or has no children, so m_bv[v.pos]==1
171 return (v.pos + 1 == m_bv.size()) or m_bv[v.pos + 1];
172 }
173
175
178 size_type degree(node_type const & v) const
179 {
180 if (is_leaf(v))
181 { // handles boundary cases
182 return 0;
183 }
184 // position of the next node - node position - 1
185 return m_bv_select1(v.nr + 2) - v.pos - 1;
186 }
187
189
194 node_type child(node_type const & v, size_type i) const
195 {
196 size_type pos = v.pos + i; // go to the position of the child's zero
197 // (#bits = pos+1) - (#1-bits = v.nr+1)
198 size_type zeros = pos + 1 - (v.nr + 1);
199 return louds_node(zeros, m_bv_select1(zeros + 1));
200 }
201
203 node_type parent(node_type const & v) const
204 {
205 if (v == root())
206 {
207 return root();
208 }
209 size_type zero_pos = m_bv_select0(v.nr);
210 size_type parent_nr = (zero_pos + 1) - v.nr - 1;
211 return node_type(parent_nr, m_bv_select1(parent_nr + 1));
212 }
213
215 size_type id(node_type const & v) const
216 {
217 return v.nr;
218 }
219
220 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
221 {
222 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
223 size_type written_bytes = 0;
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");
227 structure_tree::add_size(child, written_bytes);
228 return written_bytes;
229 }
230
231 void load(std::istream & in)
232 {
233 m_bv.load(in);
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);
238 }
239
241 template <typename archive_t>
242 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
243 {
244 ar(CEREAL_NVP(m_bv));
245 ar(CEREAL_NVP(m_bv_select1));
246 ar(CEREAL_NVP(m_bv_select0));
247 }
248
250 template <typename archive_t>
251 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
252 {
253 ar(CEREAL_NVP(m_bv));
254 ar(CEREAL_NVP(m_bv_select1));
255 m_bv_select1.set_vector(&m_bv);
256 ar(CEREAL_NVP(m_bv_select0));
257 m_bv_select0.set_vector(&m_bv);
258 }
259};
260
261} // end namespace sdsl
262#endif
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
int_vector_size_type size_type
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
size_type const & pos
size_type const & nr
louds_node(size_type f_nr=0, size_type f_pos=0)
bool operator!=(louds_node const &v) const
louds_tree(Cst const &cst, const CstBfsIterator begin, const CstBfsIterator end)
Constructor for a cst and a root node for the traversal.
louds_node node_type
node_type child(node_type const &v, size_type i) const
Returns the i-child of a node.
louds_tree(louds_tree &&lt)
select_1_t select_1_type
louds_tree(louds_tree const &lt)
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 &lt)
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.
select_0_t select_0_type
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 &&lt)
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.