SDSL  3.0.0
Succinct Data Structure Library
rmq_support_sparse_table.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_SUPPORT_SPARSE_TABLE
9 #define INCLUDED_SDSL_RMQ_SUPPORT_SPARSE_TABLE
10 
11 #include <ostream>
12 
13 #include <sdsl/int_vector.hpp>
14 #include <sdsl/rmq_support.hpp>
15 
17 namespace sdsl
18 {
19 
20 template <class t_rac = int_vector<>, bool t_min = true>
21 class rmq_support_sparse_table;
22 
23 template <class t_rac = int_vector<>>
25 
27 
42 template <class t_rac, bool t_min>
44 {
45  const t_rac * m_v; // pointer to the supported random access container
46  bit_vector::size_type m_k; // size of m_table
47  std::vector<int_vector<>> m_table;
49 
50  public:
51  typedef typename t_rac::size_type size_type;
52  typedef typename t_rac::size_type value_type;
53 
54  rmq_support_sparse_table(const t_rac * v = nullptr)
55  : m_v(v)
56  , m_k(0)
57  {
58  if (m_v == nullptr) return;
59  const size_type n = m_v->size();
60  if (n < 2) // for n<2 the queries could be answerd without any table
61  return;
62  size_type k = 0;
63  while (2 * (1ULL << k) < n) ++k; // calculate maximal
64  m_table.resize(k);
65  m_k = k;
66  for (size_type i = 0; i < k; ++i) { m_table[i] = int_vector<>(n - (1ULL << (i + 1)) + 1, 0, i + 1); }
67  for (size_type i = 0; i < n - 1; ++i)
68  {
69  if (!mm_trait::compare((*m_v)[i], (*m_v)[i + 1])) m_table[0][i] = 1;
70  }
71  for (size_type i = 1; i < k; ++i)
72  {
73  for (size_type j = 0; j < m_table[i].size(); ++j)
74  {
75  m_table[i][j] = mm_trait::compare((*m_v)[j + m_table[i - 1][j]],
76  (*m_v)[j + (1ULL << i) + m_table[i - 1][j + (1ULL << i)]])
77  ? m_table[i - 1][j]
78  : (1ULL
79  << i) + m_table[i - 1]
80  [j + (1ULL << i)];
81  }
82  }
83  }
84 
87 
90 
92 
94 
95  void set_vector(const t_rac * v) { m_v = v; }
96 
98 
108  size_type operator()(const size_type l, const size_type r) const
109  {
110  assert(l <= r);
111  assert(r < size());
112  if (l == r) return l;
113  if (l + 1 == r) return mm_trait::compare((*m_v)[l], (*m_v)[r]) ? l : r;
114  size_type k = bits::hi(r - l);
115  const size_type rr = r - (1ULL << k) + 1;
116  return mm_trait::compare((*m_v)[l + m_table[k - 1][l]], (*m_v)[rr + m_table[k - 1][rr]])
117  ? l + m_table[k - 1][l]
118  : rr + m_table[k - 1][rr];
119  }
120 
121  size_type size() const
122  {
123  if (m_v == nullptr)
124  return 0;
125  else
126  return m_v->size();
127  }
128 
129  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
130  {
131  size_type written_bytes = 0;
132  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
133  written_bytes += write_member(m_k, out);
134  if (m_k > 0)
135  {
136  for (size_type i = 0; i < m_k; ++i) written_bytes += m_table[i].serialize(out);
137  }
138  structure_tree::add_size(child, written_bytes);
139  return written_bytes;
140  }
141 
142  void load(std::istream & in, const t_rac * v)
143  {
144  set_vector(v);
145  read_member(m_k, in);
146  if (m_k > 0)
147  {
148  m_table.resize(m_k);
149  for (size_type i = 0; i < m_k; ++i) m_table[i].load(in);
150  }
151  }
152 
153  template <typename archive_t>
154  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
155  {
156  ar(CEREAL_NVP(m_k));
157  for (size_type i = 0; i < m_k; ++i) { ar(CEREAL_NVP(m_table[i])); }
158  }
159 
160  template <typename archive_t>
161  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
162  {
163  ar(CEREAL_NVP(m_k));
164  m_table.resize(m_k);
165  for (size_type i = 0; i < m_k; ++i) { ar(CEREAL_NVP(m_table[i])); }
166  }
167 
169  bool operator==(rmq_support_sparse_table const & other) const noexcept { return (m_table == other.m_table); }
170 
172  bool operator!=(rmq_support_sparse_table const & other) const noexcept { return !(*this == other); }
173 };
174 
175 } // namespace sdsl
176 #endif
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
int_vector_size_type size_type
Definition: int_vector.hpp:266
A class to support range minimum or range maximum queries on a random access container.
rmq_support_sparse_table(const rmq_support_sparse_table &rm)=default
Copy constructor.
bool operator!=(rmq_support_sparse_table const &other) const noexcept
Inequality operator.
void load(std::istream &in, const t_rac *v)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
rmq_support_sparse_table & operator=(const rmq_support_sparse_table &rm)=default
rmq_support_sparse_table(const t_rac *v=nullptr)
bool operator==(rmq_support_sparse_table const &other) const noexcept
Equality operator.
size_type operator()(const size_type l, const size_type r) const
Range minimum/maximum query for the supported random access container v.
rmq_support_sparse_table(rmq_support_sparse_table &&rm)=default
Move constructor.
rmq_support_sparse_table & operator=(rmq_support_sparse_table &&rm)=default
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
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.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:84
void read_member(T &t, std::istream &in)
Definition: io.hpp:111
rmq_support.hpp contains different range minimum support data structures.
static bool compare(const typename RandomAccessContainer::value_type v1, const typename RandomAccessContainer::value_type v2)
Definition: rmq_support.hpp:21
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661