SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
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
11#include <assert.h>
12#include <iosfwd>
13#include <string>
14
16#include <sdsl/cereal.hpp>
17#include <sdsl/int_vector.hpp>
21#include <sdsl/util.hpp>
22
24namespace sdsl
25{
26
27template <bool t_min = true, class t_bp_support = bp_support_sada<256, 32, rank_support_v5<>>>
28class rmq_succinct_sct;
29
30template <class t_bp_support = bp_support_sada<256, 32, rank_support_v5<>>>
35
37
46template <bool t_min, class t_bp_support>
48{
49 bit_vector m_sct_bp;
50 t_bp_support m_sct_bp_support;
51
52public:
55 typedef t_bp_support bp_support_type;
56
57 bit_vector const & sct_bp = m_sct_bp;
58 bp_support_type const & sct_bp_support = m_sct_bp_support;
59
63
65
68 template <class t_rac>
69 rmq_succinct_sct(t_rac const * v = nullptr)
70 {
71 if (v != nullptr)
72 {
73#ifdef RMQ_SCT_BUILD_BP_NOT_SUCCINCT
74 // this method takes \f$n\log n\f$ bits extra space in the worst case
75 construct_supercartesian_tree_bp(*v, m_sct_bp, t_min);
76#else
77 // this method takes only \f$n\f$ bits extra space in all cases
79// TODO: constructor which uses int_vector_buffer
80#endif
81 m_sct_bp_support = bp_support_type(&m_sct_bp);
82 }
83 }
84
86 rmq_succinct_sct(rmq_succinct_sct const & rm) : m_sct_bp(rm.m_sct_bp), m_sct_bp_support(rm.m_sct_bp_support)
87 {
88 m_sct_bp_support.set_vector(&m_sct_bp);
89 }
90
93 {
94 *this = std::move(rm);
95 }
96
98 {
99 if (this != &rm)
100 {
101 rmq_succinct_sct tmp(rm);
102 *this = std::move(tmp);
103 }
104 return *this;
105 }
106
108 {
109 if (this != &rm)
110 {
111 m_sct_bp = std::move(rm.m_sct_bp);
112 m_sct_bp_support = std::move(rm.m_sct_bp_support);
113 m_sct_bp_support.set_vector(&m_sct_bp);
114 }
115 return *this;
116 }
117
119
129 size_type operator()(const size_type l, const size_type r) const
130 {
131 assert(l <= r);
132 assert(r < size());
133 if (l == r)
134 return l;
135 size_type i = m_sct_bp_support.select(l + 1);
136 size_type j = m_sct_bp_support.select(r + 1);
137 size_type fc_i = m_sct_bp_support.find_close(i);
138 if (j < fc_i)
139 { // i < j < find_close(j) < find_close(i)
140 return l;
141 }
142 else
143 { // if i < find_close(i) < j < find_close(j)
144 size_type ec = m_sct_bp_support.rr_enclose(i, j);
145 if (ec == m_sct_bp_support.size())
146 { // no restricted enclosing pair found
147 return r;
148 }
149 else
150 { // found range restricted enclosing pair
151 return m_sct_bp_support.rank(ec) - 1; // subtract 1, as the index is 0 based
152 }
153 }
154 }
155
157 {
158 return m_sct_bp.size() / 2;
159 }
160
161 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
162 {
163 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
164 size_type written_bytes = 0;
165 written_bytes += m_sct_bp.serialize(out, child, "sct_bp");
166 written_bytes += m_sct_bp_support.serialize(out, child, "sct_bp_support");
167 structure_tree::add_size(child, written_bytes);
168 return written_bytes;
169 }
170
171 void load(std::istream & in)
172 {
173 m_sct_bp.load(in);
174 m_sct_bp_support.load(in, &m_sct_bp);
175 }
176
177 template <typename archive_t>
178 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
179 {
180 ar(CEREAL_NVP(m_sct_bp));
181 ar(CEREAL_NVP(m_sct_bp_support));
182 }
183
184 template <typename archive_t>
185 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
186 {
187 ar(CEREAL_NVP(m_sct_bp));
188 ar(CEREAL_NVP(m_sct_bp_support));
189 m_sct_bp_support.set_vector(&m_sct_bp);
190 }
191
193 bool operator==(rmq_succinct_sct const & other) const noexcept
194 {
195 return (m_sct_bp == other.m_sct_bp) && (m_sct_bp_support == other.m_sct_bp_support);
196 }
197
199 bool operator!=(rmq_succinct_sct const & other) const noexcept
200 {
201 return !(*this == other);
202 }
203};
204
205} // end namespace sdsl
206#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.
A class to support range minimum or range maximum queries on a random access container.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
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(rmq_succinct_sct const &rm)
Copy constructor.
bool operator!=(rmq_succinct_sct const &other) const noexcept
Inequality operator.
rmq_succinct_sct()
Default constructor.
bp_support_type const & sct_bp_support
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
rmq_succinct_sct(rmq_succinct_sct &&rm)
Move constructor.
bit_vector const & sct_bp
rmq_succinct_sct(t_rac const *v=nullptr)
Constructor.
bit_vector::size_type size_type
rmq_succinct_sct & operator=(rmq_succinct_sct const &rm)
void load(std::istream &in)
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.
void construct_supercartesian_tree_bp(t_rac const &vec, bit_vector &bp, bool const minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
bit_vector construct_supercartesian_tree_bp_succinct(t_rac const &vec, bool const minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
rank_support_v5.hpp contains rank_support_v5.5
rmq_succinct_sct< false, t_bp_support > 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.