SDSL 3.0.1
Succinct Data Structure Library
rmq_succinct_sct.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_SCT
9#define INCLUDED_SDSL_RMQ_SUCCINCT_SCT
10
12#include <sdsl/int_vector.hpp>
14#include <sdsl/util.hpp>
15
17namespace sdsl
18{
19
20template <bool t_min = true, class t_bp_support = bp_support_sada<256, 32, rank_support_v5<>>>
21class rmq_succinct_sct;
22
23template <class t_bp_support = bp_support_sada<256, 32, rank_support_v5<>>>
25{
27};
28
30
39template <bool t_min, class t_bp_support>
41{
42 bit_vector m_sct_bp;
43 t_bp_support m_sct_bp_support;
44
45 public:
48 typedef t_bp_support bp_support_type;
49
50 const bit_vector & sct_bp = m_sct_bp;
51 const bp_support_type & sct_bp_support = m_sct_bp_support;
52
55
57
60 template <class t_rac>
61 rmq_succinct_sct(const t_rac * v = nullptr)
62 {
63 if (v != nullptr)
64 {
65#ifdef RMQ_SCT_BUILD_BP_NOT_SUCCINCT
66 // this method takes \f$n\log n\f$ bits extra space in the worst case
67 construct_supercartesian_tree_bp(*v, m_sct_bp, t_min);
68#else
69 // this method takes only \f$n\f$ bits extra space in all cases
71// TODO: constructor which uses int_vector_buffer
72#endif
73 m_sct_bp_support = bp_support_type(&m_sct_bp);
74 }
75 }
76
79 : m_sct_bp(rm.m_sct_bp)
80 , m_sct_bp_support(rm.m_sct_bp_support)
81 {
82 m_sct_bp_support.set_vector(&m_sct_bp);
83 }
84
86 rmq_succinct_sct(rmq_succinct_sct && rm) { *this = std::move(rm); }
87
89 {
90 if (this != &rm)
91 {
92 rmq_succinct_sct tmp(rm);
93 *this = std::move(tmp);
94 }
95 return *this;
96 }
97
99 {
100 if (this != &rm)
101 {
102 m_sct_bp = std::move(rm.m_sct_bp);
103 m_sct_bp_support = std::move(rm.m_sct_bp_support);
104 m_sct_bp_support.set_vector(&m_sct_bp);
105 }
106 return *this;
107 }
108
110
120 size_type operator()(const size_type l, const size_type r) const
121 {
122 assert(l <= r);
123 assert(r < size());
124 if (l == r) return l;
125 size_type i = m_sct_bp_support.select(l + 1);
126 size_type j = m_sct_bp_support.select(r + 1);
127 size_type fc_i = m_sct_bp_support.find_close(i);
128 if (j < fc_i)
129 { // i < j < find_close(j) < find_close(i)
130 return l;
131 }
132 else
133 { // if i < find_close(i) < j < find_close(j)
134 size_type ec = m_sct_bp_support.rr_enclose(i, j);
135 if (ec == m_sct_bp_support.size())
136 { // no restricted enclosing pair found
137 return r;
138 }
139 else
140 { // found range restricted enclosing pair
141 return m_sct_bp_support.rank(ec) - 1; // subtract 1, as the index is 0 based
142 }
143 }
144 }
145
146 size_type size() const { return m_sct_bp.size() / 2; }
147
148 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
149 {
150 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
151 size_type written_bytes = 0;
152 written_bytes += m_sct_bp.serialize(out, child, "sct_bp");
153 written_bytes += m_sct_bp_support.serialize(out, child, "sct_bp_support");
154 structure_tree::add_size(child, written_bytes);
155 return written_bytes;
156 }
157
158 void load(std::istream & in)
159 {
160 m_sct_bp.load(in);
161 m_sct_bp_support.load(in, &m_sct_bp);
162 }
163
164 template <typename archive_t>
165 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
166 {
167 ar(CEREAL_NVP(m_sct_bp));
168 ar(CEREAL_NVP(m_sct_bp_support));
169 }
170
171 template <typename archive_t>
172 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
173 {
174 ar(CEREAL_NVP(m_sct_bp));
175 ar(CEREAL_NVP(m_sct_bp_support));
176 m_sct_bp_support.set_vector(&m_sct_bp);
177 }
178
180 bool operator==(rmq_succinct_sct const & other) const noexcept
181 {
182 return (m_sct_bp == other.m_sct_bp) && (m_sct_bp_support == other.m_sct_bp_support);
183 }
184
186 bool operator!=(rmq_succinct_sct const & other) const noexcept { return !(*this == other); }
187};
188
189} // end namespace sdsl
190#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.
A class to support range minimum or range maximum queries on a random access container.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
rmq_succinct_sct(const rmq_succinct_sct &rm)
Copy constructor.
bool operator==(rmq_succinct_sct const &other) const noexcept
Equality operator.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type operator()(const size_type l, const size_type r) const
Range minimum/maximum query for the supported random access container v.
bit_vector::size_type value_type
rmq_succinct_sct & operator=(rmq_succinct_sct &&rm)
rmq_succinct_sct & operator=(const rmq_succinct_sct &rm)
bool operator!=(rmq_succinct_sct const &other) const noexcept
Inequality operator.
rmq_succinct_sct()
Default constructor.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
rmq_succinct_sct(const t_rac *v=nullptr)
Constructor.
const bp_support_type & sct_bp_support
const bit_vector & sct_bp
rmq_succinct_sct(rmq_succinct_sct &&rm)
Move constructor.
bit_vector::size_type size_type
void load(std::istream &in)
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.
bit_vector construct_supercartesian_tree_bp_succinct(const t_rac &vec, const bool minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
void construct_supercartesian_tree_bp(const t_rac &vec, bit_vector &bp, const bool minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
rmq_succinct_sct< false, t_bp_support > type
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.