SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <assert.h>
12#include <iosfwd>
13#include <stack>
14#include <stdint.h>
15#include <string>
16
18#include <sdsl/cereal.hpp>
19#include <sdsl/int_vector.hpp>
25#include <sdsl/util.hpp>
26
28namespace sdsl
29{
30
31template <bool t_min = true,
32 class t_bp_support = bp_support_sada<256, 32, rank_support_v5<1>, select_support_scan<1>>,
33 class t_rank_10 = rank_support_v<10, 2>,
34 class t_select_10 = select_support_mcl<10, 2>>
35class rmq_succinct_sada;
36
37template <class t_bp_support = bp_support_sada<256, 32, rank_support_v5<>, select_support_scan<1>>,
38 class t_rank_10 = rank_support_v<10, 2>,
39 class t_select_10 = select_support_mcl<10, 2>>
44
46
60template <bool t_min, class t_bp_support, class t_rank_10, class t_select_10>
62{
63 bit_vector m_ect_bp;
64 t_bp_support m_ect_bp_support;
65 t_rank_10 m_ect_bp_rank10;
66 t_select_10 m_ect_bp_select10;
67
68public:
71
72 typedef t_bp_support bp_support_type;
73 typedef t_rank_10 rank_support10_type;
74 typedef t_select_10 select_support10_type;
75
76 bit_vector const & ect_bp = m_ect_bp;
77 bp_support_type const & ect_bp_support = m_ect_bp_support;
78 rank_support10_type const & ect_bp_rank10 = m_ect_bp_rank10;
79 select_support10_type const & ect_bp_select10 = m_ect_bp_select10;
80
81private:
83
84 // helper class for the construction
85 struct state
86 {
87 size_type l, r; // left and right interval
88 size_type m; // index of the rmq
89 uint8_t visit; // 1==first, 2==second, 3==third visit
90 state(size_type fl = 0, size_type fr = 0, size_type fm = 0, uint8_t fvisit = 0) :
91 l(fl),
92 r(fr),
93 m(fm),
94 visit(fvisit)
95 {}
96 };
97
99
102 template <class t_rac>
103 void construct_bp_of_extended_cartesian_tree(t_rac const * v, rmq_construct_helper_type const & rmq_helper)
104 {
105 m_ect_bp.resize(4 * v->size());
106 if (v->size() > 0)
107 {
108 size_type bp_cnt = 0;
109 size_type l = 0, r = v->size() - 1;
110 std::stack<state> state_stack;
111 state_stack.push(state(l, r, rmq_helper(l, r), 1));
112 while (!state_stack.empty())
113 {
114 state s = state_stack.top();
115 state_stack.pop();
116 if (1 == s.visit)
117 {
118 m_ect_bp[bp_cnt++] = 1; // write beginning of inner node
119 state_stack.push(state(s.l, s.r, s.m, 2));
120 if (s.m > s.l)
121 {
122 state_stack.push(state(s.l, s.m - 1, rmq_helper(s.l, s.m - 1), 1));
123 }
124 }
125 else if (2 == s.visit)
126 {
127 m_ect_bp[bp_cnt++] = 1; // write leaf
128 m_ect_bp[bp_cnt++] = 0;
129 state_stack.push(state(s.l, s.r, s.m, 3));
130 if (s.m < s.r)
131 {
132 state_stack.push(state(s.m + 1, s.r, rmq_helper(s.m + 1, s.r), 1));
133 }
134 }
135 else if (3 == s.visit)
136 {
137 m_ect_bp[bp_cnt++] = 0; // write end of inner node
138 }
139 }
140 assert(bp_cnt == 4 * v->size());
141 }
142 }
143
144public:
148
150 template <class t_rac>
151 rmq_succinct_sada(t_rac const * v = nullptr)
152 {
153 if (v != nullptr)
154 {
155 rmq_construct_helper_type rmq_helper(v);
156 m_ect_bp.resize(4 * v->size());
157 construct_bp_of_extended_cartesian_tree(v, rmq_helper);
158 m_ect_bp_support = bp_support_type(&m_ect_bp);
159 util::init_support(m_ect_bp_rank10, &m_ect_bp);
160 util::init_support(m_ect_bp_select10, &m_ect_bp);
161 }
162 }
163
166 m_ect_bp(rm.m_ect_bp),
167 m_ect_bp_support(rm.m_ect_bp_support),
168 m_ect_bp_rank10(rm.m_ect_bp_rank10),
169 m_ect_bp_select10(rm.m_ect_bp_select10)
170 {
171 m_ect_bp_support.set_vector(&m_ect_bp);
172 m_ect_bp_rank10.set_vector(&m_ect_bp);
173 m_ect_bp_select10.set_vector(&m_ect_bp);
174 }
175
178 {
179 *this = std::move(rm);
180 }
181
185
187 {
188 if (this != &rm)
189 {
190 rmq_succinct_sada tmp(rm);
191 *this = std::move(tmp);
192 }
193 return *this;
194 }
195
197 {
198 if (this != &rm)
199 {
200 m_ect_bp = std::move(rm.m_ect_bp);
201 m_ect_bp_support = std::move(rm.m_ect_bp_support);
202 m_ect_bp_support.set_vector(&m_ect_bp);
203 m_ect_bp_rank10 = std::move(rm.m_ect_bp_rank10);
204 m_ect_bp_rank10.set_vector(&m_ect_bp);
205 m_ect_bp_select10 = std::move(rm.m_ect_bp_select10);
206 m_ect_bp_select10.set_vector(&m_ect_bp);
207 }
208 return *this;
209 }
210
212
222 size_type operator()(const size_type l, const size_type r) const
223 {
224 assert(l <= r);
225 assert(r < size());
226 if (l == r)
227 return l;
228 size_type x = m_ect_bp_select10(l + 1);
229 size_type y = m_ect_bp_select10(r + 1);
230 size_type z = m_ect_bp_support.rmq(x, y);
231 size_type f = z + 1 - 2 * (m_ect_bp[z]);
232 return m_ect_bp_rank10(f - 1);
233 }
234
236 {
237 return m_ect_bp.size() / 4;
238 }
239
240 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
241 {
242 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
243 size_type written_bytes = 0;
244 written_bytes += m_ect_bp.serialize(out, child, "ect_bp");
245 written_bytes += m_ect_bp_support.serialize(out, child, "ect_bp_support");
246 written_bytes += m_ect_bp_rank10.serialize(out, child, "ect_bp_rank10");
247 written_bytes += m_ect_bp_select10.serialize(out, child, "ect_bp_select10");
248 structure_tree::add_size(child, written_bytes);
249 return written_bytes;
250 }
251
252 void load(std::istream & in)
253 {
254 m_ect_bp.load(in);
255 m_ect_bp_support.load(in, &m_ect_bp);
256 m_ect_bp_rank10.load(in, &m_ect_bp);
257 m_ect_bp_select10.load(in, &m_ect_bp);
258 }
259
260 template <typename archive_t>
261 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
262 {
263 ar(CEREAL_NVP(m_ect_bp));
264 ar(CEREAL_NVP(m_ect_bp_support));
265 ar(CEREAL_NVP(m_ect_bp_rank10));
266 ar(CEREAL_NVP(m_ect_bp_select10));
267 }
268
269 template <typename archive_t>
270 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
271 {
272 ar(CEREAL_NVP(m_ect_bp));
273 ar(CEREAL_NVP(m_ect_bp_support));
274 m_ect_bp_support.set_vector(&m_ect_bp);
275 ar(CEREAL_NVP(m_ect_bp_rank10));
276 m_ect_bp_rank10.set_vector(&m_ect_bp);
277 ar(CEREAL_NVP(m_ect_bp_select10));
278 m_ect_bp_select10.set_vector(&m_ect_bp);
279 }
280
282 bool operator==(rmq_succinct_sada const & other) const noexcept
283 {
284 return (m_ect_bp == other.m_ect_bp) && (m_ect_bp_support == other.m_ect_bp_support)
285 && (m_ect_bp_rank10 == other.m_ect_bp_rank10) && (m_ect_bp_select10 == other.m_ect_bp_select10);
286 }
287
289 bool operator!=(rmq_succinct_sada const & other) const noexcept
290 {
291 return !(*this == other);
292 }
293};
294
295} // end namespace sdsl
296#endif
bp_support_sada.hpp contains an implementation of a balanced parentheses support structure proposed b...
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
int_vector_size_type size_type
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.
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=(rmq_succinct_sada &&rm)
rmq_succinct_sada(t_rac const *v=nullptr)
Constructor.
rank_support10_type const & ect_bp_rank10
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bit_vector::size_type value_type
bit_vector::size_type size_type
rmq_succinct_sada()
Default Constructor.
void load(std::istream &in)
bool operator==(rmq_succinct_sada const &other) const noexcept
Equality operator.
rmq_succinct_sada & operator=(rmq_succinct_sada const &rm)
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.
bp_support_type const & ect_bp_support
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
select_support10_type const & ect_bp_select10
rmq_succinct_sada(rmq_succinct_sada const &rm)
Copy constructor.
A class to support range minimum or range maximum queries on a random access container.
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.
rank_support_v5.hpp contains rank_support_v5.5
rmq_succinct_sct.hpp contains the class rmq_succinct_sct which supports range minimum or range maximu...
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
select_support_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
rmq_succinct_sada< false, t_bp_support, t_rank_10, t_select_10 > type
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.