SDSL 3.0.1
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 <stack>
12#include <utility> // for pair
13
15#include <sdsl/int_vector.hpp>
16#include <sdsl/rank_support.hpp>
18#include <sdsl/rmq_support.hpp>
21#include <sdsl/util.hpp>
22
24namespace sdsl
25{
26
27template <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>>
31class rmq_succinct_sada;
32
33template <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
56template <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:
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:31
int_vector_size_type size_type
Definition: int_vector.hpp:229
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:521
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(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)
const bp_support_type & ect_bp_support
rmq_succinct_sada & operator=(const rmq_succinct_sada &rm)
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, 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.
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.