8#ifndef INCLUDED_SDSL_RMQ_SUCCINCT_SADA
9#define INCLUDED_SDSL_RMQ_SUCCINCT_SADA
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;
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>>
60template <
bool t_min,
class t_bp_support,
class t_rank_10,
class t_select_10>
64 t_bp_support m_ect_bp_support;
65 t_rank_10 m_ect_bp_rank10;
66 t_select_10 m_ect_bp_select10;
102 template <
class t_rac>
103 void construct_bp_of_extended_cartesian_tree(t_rac
const * v, rmq_construct_helper_type
const & rmq_helper)
105 m_ect_bp.
resize(4 * v->size());
110 std::stack<state> state_stack;
111 state_stack.push(state(l, r, rmq_helper(l, r), 1));
112 while (!state_stack.empty())
114 state s = state_stack.top();
118 m_ect_bp[bp_cnt++] = 1;
119 state_stack.push(state(s.l, s.r, s.m, 2));
122 state_stack.push(state(s.l, s.m - 1, rmq_helper(s.l, s.m - 1), 1));
125 else if (2 == s.visit)
127 m_ect_bp[bp_cnt++] = 1;
128 m_ect_bp[bp_cnt++] = 0;
129 state_stack.push(state(s.l, s.r, s.m, 3));
132 state_stack.push(state(s.m + 1, s.r, rmq_helper(s.m + 1, s.r), 1));
135 else if (3 == s.visit)
137 m_ect_bp[bp_cnt++] = 0;
140 assert(bp_cnt == 4 * v->size());
150 template <
class t_rac>
156 m_ect_bp.
resize(4 * v->size());
157 construct_bp_of_extended_cartesian_tree(v, rmq_helper);
159 util::init_support(m_ect_bp_rank10, &m_ect_bp);
160 util::init_support(m_ect_bp_select10, &m_ect_bp);
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)
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);
179 *
this = std::move(rm);
191 *
this = std::move(tmp);
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);
230 size_type z = m_ect_bp_support.rmq(x, y);
232 return m_ect_bp_rank10(f - 1);
237 return m_ect_bp.
size() / 4;
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");
249 return written_bytes;
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);
260 template <
typename archive_t>
269 template <
typename archive_t>
274 m_ect_bp_support.set_vector(&m_ect_bp);
276 m_ect_bp_rank10.set_vector(&m_ect_bp);
278 m_ect_bp_select10.set_vector(&m_ect_bp);
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);
291 return !(*
this == other);
bp_support_sada.hpp contains an implementation of a balanced parentheses support structure proposed b...
cereal.hpp offers cereal support
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.
t_select_10 select_support10_type
rank_support10_type const & ect_bp_rank10
bit_vector const & 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
bit_vector::size_type value_type
bit_vector::size_type size_type
rmq_succinct_sada()
Default Constructor.
void load(std::istream &in)
~rmq_succinct_sada()
Destructor.
bool operator==(rmq_succinct_sada const &other) const noexcept
Equality operator.
t_rank_10 rank_support10_type
rmq_succinct_sada & operator=(rmq_succinct_sada const &rm)
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.
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.