SDSL  3.0.0
Succinct Data Structure Library
rmq_succinct_sada.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_RMQ_SUCCINCT_SADA
9 #define INCLUDED_SDSL_RMQ_SUCCINCT_SADA
10 
11 #include <stack>
12 #include <utility> // for pair
13 
14 #include <sdsl/bp_support_sada.hpp>
15 #include <sdsl/int_vector.hpp>
16 #include <sdsl/rank_support.hpp>
18 #include <sdsl/rmq_support.hpp>
19 #include <sdsl/select_support.hpp>
21 #include <sdsl/util.hpp>
22 
24 namespace sdsl
25 {
26 
27 template <bool t_min = true,
28  class t_bp_support = bp_support_sada<256, 32, rank_support_v5<1>, select_support_scan<1>>,
29  class t_rank_10 = rank_support_v<10, 2>,
30  class t_select_10 = select_support_mcl<10, 2>>
31 class rmq_succinct_sada;
32 
33 template <class t_bp_support = bp_support_sada<256, 32, rank_support_v5<>, select_support_scan<1>>,
34  class t_rank_10 = rank_support_v<10, 2>,
35  class t_select_10 = select_support_mcl<10, 2>>
37 {
39 };
40 
42 
56 template <bool t_min, class t_bp_support, class t_rank_10, class t_select_10>
58 {
59  bit_vector m_ect_bp;
60  t_bp_support m_ect_bp_support;
61  t_rank_10 m_ect_bp_rank10;
62  t_select_10 m_ect_bp_select10;
63 
64  public:
65  typedef typename bit_vector::size_type size_type;
67 
68  typedef t_bp_support bp_support_type;
69  typedef t_rank_10 rank_support10_type;
70  typedef t_select_10 select_support10_type;
71 
72  const bit_vector & ect_bp = m_ect_bp;
73  const bp_support_type & ect_bp_support = m_ect_bp_support;
74  const rank_support10_type & ect_bp_rank10 = m_ect_bp_rank10;
75  const select_support10_type & ect_bp_select10 = m_ect_bp_select10;
76 
77  private:
79 
80  // helper class for the construction
81  struct state
82  {
83  size_type l, r; // left and right interval
84  size_type m; // index of the rmq
85  uint8_t visit; // 1==first, 2==second, 3==third visit
86  state(size_type fl = 0, size_type fr = 0, size_type fm = 0, uint8_t fvisit = 0)
87  : l(fl)
88  , r(fr)
89  , m(fm)
90  , visit(fvisit)
91  {}
92  };
93 
95 
98  template <class t_rac>
99  void construct_bp_of_extended_cartesian_tree(const t_rac * v, const rmq_construct_helper_type & rmq_helper)
100  {
101  m_ect_bp.resize(4 * v->size());
102  if (v->size() > 0)
103  {
104  size_type bp_cnt = 0;
105  size_type l = 0, r = v->size() - 1;
106  std::stack<state> state_stack;
107  state_stack.push(state(l, r, rmq_helper(l, r), 1));
108  while (!state_stack.empty())
109  {
110  state s = state_stack.top();
111  state_stack.pop();
112  if (1 == s.visit)
113  {
114  m_ect_bp[bp_cnt++] = 1; // write beginning of inner node
115  state_stack.push(state(s.l, s.r, s.m, 2));
116  if (s.m > s.l) { state_stack.push(state(s.l, s.m - 1, rmq_helper(s.l, s.m - 1), 1)); }
117  }
118  else if (2 == s.visit)
119  {
120  m_ect_bp[bp_cnt++] = 1; // write leaf
121  m_ect_bp[bp_cnt++] = 0;
122  state_stack.push(state(s.l, s.r, s.m, 3));
123  if (s.m < s.r) { state_stack.push(state(s.m + 1, s.r, rmq_helper(s.m + 1, s.r), 1)); }
124  }
125  else if (3 == s.visit)
126  {
127  m_ect_bp[bp_cnt++] = 0; // write end of inner node
128  }
129  }
130  assert(bp_cnt == 4 * v->size());
131  }
132  }
133 
134  public:
137 
139  template <class t_rac>
140  rmq_succinct_sada(const t_rac * v = nullptr)
141  {
142  if (v != nullptr)
143  {
144  rmq_construct_helper_type rmq_helper(v);
145  m_ect_bp.resize(4 * v->size());
146  construct_bp_of_extended_cartesian_tree(v, rmq_helper);
147  m_ect_bp_support = bp_support_type(&m_ect_bp);
148  util::init_support(m_ect_bp_rank10, &m_ect_bp);
149  util::init_support(m_ect_bp_select10, &m_ect_bp);
150  }
151  }
152 
155  : m_ect_bp(rm.m_ect_bp)
156  , m_ect_bp_support(rm.m_ect_bp_support)
157  , m_ect_bp_rank10(rm.m_ect_bp_rank10)
158  , m_ect_bp_select10(rm.m_ect_bp_select10)
159  {
160  m_ect_bp_support.set_vector(&m_ect_bp);
161  m_ect_bp_rank10.set_vector(&m_ect_bp);
162  m_ect_bp_select10.set_vector(&m_ect_bp);
163  }
164 
166  rmq_succinct_sada(rmq_succinct_sada && rm) { *this = std::move(rm); }
167 
170 
172  {
173  if (this != &rm)
174  {
175  rmq_succinct_sada tmp(rm);
176  *this = std::move(tmp);
177  }
178  return *this;
179  }
180 
182  {
183  if (this != &rm)
184  {
185  m_ect_bp = std::move(rm.m_ect_bp);
186  m_ect_bp_support = std::move(rm.m_ect_bp_support);
187  m_ect_bp_support.set_vector(&m_ect_bp);
188  m_ect_bp_rank10 = std::move(rm.m_ect_bp_rank10);
189  m_ect_bp_rank10.set_vector(&m_ect_bp);
190  m_ect_bp_select10 = std::move(rm.m_ect_bp_select10);
191  m_ect_bp_select10.set_vector(&m_ect_bp);
192  }
193  return *this;
194  }
195 
197 
207  size_type operator()(const size_type l, const size_type r) const
208  {
209  assert(l <= r);
210  assert(r < size());
211  if (l == r) return l;
212  size_type x = m_ect_bp_select10(l + 1);
213  size_type y = m_ect_bp_select10(r + 1);
214  size_type z = m_ect_bp_support.rmq(x, y);
215  size_type f = z + 1 - 2 * (m_ect_bp[z]);
216  return m_ect_bp_rank10(f - 1);
217  }
218 
219  size_type size() const { return m_ect_bp.size() / 4; }
220 
221  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
222  {
223  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
224  size_type written_bytes = 0;
225  written_bytes += m_ect_bp.serialize(out, child, "ect_bp");
226  written_bytes += m_ect_bp_support.serialize(out, child, "ect_bp_support");
227  written_bytes += m_ect_bp_rank10.serialize(out, child, "ect_bp_rank10");
228  written_bytes += m_ect_bp_select10.serialize(out, child, "ect_bp_select10");
229  structure_tree::add_size(child, written_bytes);
230  return written_bytes;
231  }
232 
233  void load(std::istream & in)
234  {
235  m_ect_bp.load(in);
236  m_ect_bp_support.load(in, &m_ect_bp);
237  m_ect_bp_rank10.load(in, &m_ect_bp);
238  m_ect_bp_select10.load(in, &m_ect_bp);
239  }
240 
241  template <typename archive_t>
242  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
243  {
244  ar(CEREAL_NVP(m_ect_bp));
245  ar(CEREAL_NVP(m_ect_bp_support));
246  ar(CEREAL_NVP(m_ect_bp_rank10));
247  ar(CEREAL_NVP(m_ect_bp_select10));
248  }
249 
250  template <typename archive_t>
251  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
252  {
253  ar(CEREAL_NVP(m_ect_bp));
254  ar(CEREAL_NVP(m_ect_bp_support));
255  m_ect_bp_support.set_vector(&m_ect_bp);
256  ar(CEREAL_NVP(m_ect_bp_rank10));
257  m_ect_bp_rank10.set_vector(&m_ect_bp);
258  ar(CEREAL_NVP(m_ect_bp_select10));
259  m_ect_bp_select10.set_vector(&m_ect_bp);
260  }
261 
263  bool operator==(rmq_succinct_sada const & other) const noexcept
264  {
265  return (m_ect_bp == other.m_ect_bp) && (m_ect_bp_support == other.m_ect_bp_support) &&
266  (m_ect_bp_rank10 == other.m_ect_bp_rank10) && (m_ect_bp_select10 == other.m_ect_bp_select10);
267  }
268 
270  bool operator!=(rmq_succinct_sada const & other) const noexcept { return !(*this == other); }
271 };
272 
273 } // end namespace sdsl
274 #endif
bp_support_sada.hpp contains an implementation of a balanced parentheses support structure proposed b...
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
int_vector_size_type size_type
Definition: int_vector.hpp:266
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:545
A class to support range minimum or range maximum queries on a random access container.
bool operator!=(rmq_succinct_sada const &other) const noexcept
Inequality operator.
rmq_succinct_sada & operator=(const rmq_succinct_sada &rm)
rmq_succinct_sada(const t_rac *v=nullptr)
Constructor.
const bit_vector & ect_bp
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
const select_support10_type & ect_bp_select10
bit_vector::size_type value_type
rmq_succinct_sada(const rmq_succinct_sada &rm)
Copy constructor.
bit_vector::size_type size_type
rmq_succinct_sada()
Default Constructor.
void load(std::istream &in)
const rank_support10_type & ect_bp_rank10
bool operator==(rmq_succinct_sada const &other) const noexcept
Equality operator.
size_type operator()(const size_type l, const size_type r) const
Range minimum/maximum query for the supported random access container v.
rmq_succinct_sada(rmq_succinct_sada &&rm)
Move constructor.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
rmq_succinct_sada & operator=(rmq_succinct_sada &&rm)
const bp_support_type & ect_bp_support
A class to support range minimum or range maximum queries on a random access container.
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.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
rmq_succinct_sct.hpp contains the class rmq_succinct_sct which supports range minimum or range maximu...
rmq_support.hpp contains different range minimum support data structures.
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
rmq_succinct_sada< false, t_bp_support, t_rank_10, t_select_10 > type
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.