SDSL  3.0.0
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 
17 namespace 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 
45 inline std::ostream & operator<<(std::ostream & os, const louds_node & v)
46 {
47  os << "(" << v.nr << "," << v.pos << ")";
48  return os;
49 }
50 
52 
63 template <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 
107  louds_tree(const louds_tree & lt)
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:30
int_vector_size_type size_type
Definition: int_vector.hpp:266
void shrink_to_fit()
Free unused allocated memory.
Definition: int_vector.hpp:530
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:545
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 & operator=(louds_tree &&lt)
Definition: louds_tree.hpp:133
louds_tree(const louds_tree &lt)
Definition: louds_tree.hpp:107
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
louds_tree & operator=(const louds_tree &lt)
Definition: louds_tree.hpp:123
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
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
Definition: cst_sct3.hpp:1332
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:51
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.