SDSL  3.0.0
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 
11 #include <sdsl/bp_support_sada.hpp>
12 #include <sdsl/int_vector.hpp>
14 #include <sdsl/util.hpp>
15 
17 namespace sdsl
18 {
19 
20 template <bool t_min = true, class t_bp_support = bp_support_sada<256, 32, rank_support_v5<>>>
21 class rmq_succinct_sct;
22 
23 template <class t_bp_support = bp_support_sada<256, 32, rank_support_v5<>>>
25 {
27 };
28 
30 
39 template <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:
46  typedef typename bit_vector::size_type size_type;
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
70  m_sct_bp = construct_supercartesian_tree_bp_succinct(*v, t_min);
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:30
int_vector_size_type size_type
Definition: int_vector.hpp:266
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 & operator=(rmq_succinct_sct &&rm)
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
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.
rmq_succinct_sct & operator=(const rmq_succinct_sct &rm)
bit_vector::size_type size_type
void load(std::istream &in)
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.
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.