8 #ifndef INCLUDED_SDSL_RMQ_SUCCINCT_SADA
9 #define INCLUDED_SDSL_RMQ_SUCCINCT_SADA
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;
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>>
56 template <
bool t_min,
class t_bp_support,
class t_rank_10,
class t_select_10>
60 t_bp_support m_ect_bp_support;
61 t_rank_10 m_ect_bp_rank10;
62 t_select_10 m_ect_bp_select10;
98 template <
class t_rac>
99 void construct_bp_of_extended_cartesian_tree(
const t_rac * v,
const rmq_construct_helper_type & rmq_helper)
101 m_ect_bp.
resize(4 * v->size());
106 std::stack<state> state_stack;
107 state_stack.push(state(l, r, rmq_helper(l, r), 1));
108 while (!state_stack.empty())
110 state s = state_stack.top();
114 m_ect_bp[bp_cnt++] = 1;
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)); }
118 else if (2 == s.visit)
120 m_ect_bp[bp_cnt++] = 1;
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)); }
125 else if (3 == s.visit)
127 m_ect_bp[bp_cnt++] = 0;
130 assert(bp_cnt == 4 * v->size());
139 template <
class t_rac>
145 m_ect_bp.
resize(4 * v->size());
146 construct_bp_of_extended_cartesian_tree(v, rmq_helper);
148 util::init_support(m_ect_bp_rank10, &m_ect_bp);
149 util::init_support(m_ect_bp_select10, &m_ect_bp);
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)
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);
176 *
this = std::move(tmp);
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);
211 if (l == r)
return l;
214 size_type z = m_ect_bp_support.rmq(x, y);
216 return m_ect_bp_rank10(f - 1);
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");
230 return written_bytes;
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);
241 template <
typename archive_t>
250 template <
typename archive_t>
255 m_ect_bp_support.set_vector(&m_ect_bp);
257 m_ect_bp_rank10.set_vector(&m_ect_bp);
259 m_ect_bp_select10.set_vector(&m_ect_bp);
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);
bp_support_sada.hpp contains an implementation of a balanced parentheses support structure proposed b...
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=(const rmq_succinct_sada &rm)
t_select_10 select_support10_type
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
~rmq_succinct_sada()
Destructor.
bool operator==(rmq_succinct_sada const &other) const noexcept
Equality operator.
t_rank_10 rank_support10_type
t_bp_support bp_support_type
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.