SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <assert.h>
12#include <ostream>
13#include <string>
14#include <vector>
15
16#include <sdsl/bits.hpp>
17#include <sdsl/cereal.hpp>
18#include <sdsl/int_vector.hpp>
19#include <sdsl/io.hpp>
20#include <sdsl/rmq_support.hpp>
22#include <sdsl/util.hpp>
23
25namespace sdsl
26{
27
28template <class t_rac = int_vector<>, bool t_min = true>
29class rmq_support_sparse_table;
30
31template <class t_rac = int_vector<>>
33
35
50template <class t_rac, bool t_min>
52{
53 t_rac const * m_v; // pointer to the supported random access container
54 bit_vector::size_type m_k; // size of m_table
55 std::vector<int_vector<>> m_table;
57
58public:
59 typedef typename t_rac::size_type size_type;
60 typedef typename t_rac::size_type value_type;
61
62 rmq_support_sparse_table(t_rac const * v = nullptr) : m_v(v), m_k(0)
63 {
64 if (m_v == nullptr)
65 return;
66 const size_type n = m_v->size();
67 if (n < 2) // for n<2 the queries could be answerd without any table
68 return;
69 size_type k = 0;
70 while (2 * (1ULL << k) < n)
71 ++k; // calculate maximal
72 m_table.resize(k);
73 m_k = k;
74 for (size_type i = 0; i < k; ++i)
75 {
76 m_table[i] = int_vector<>(n - (1ULL << (i + 1)) + 1, 0, i + 1);
77 }
78 for (size_type i = 0; i < n - 1; ++i)
79 {
80 if (!mm_trait::compare((*m_v)[i], (*m_v)[i + 1]))
81 m_table[0][i] = 1;
82 }
83 for (size_type i = 1; i < k; ++i)
84 {
85 for (size_type j = 0; j < m_table[i].size(); ++j)
86 {
87 m_table[i][j] = mm_trait::compare((*m_v)[j + m_table[i - 1][j]],
88 (*m_v)[j + (1ULL << i) + m_table[i - 1][j + (1ULL << i)]])
89 ? m_table[i - 1][j]
90 : (1ULL << i) + m_table[i - 1][j + (1ULL << i)];
91 }
92 }
93 }
94
97
100
102
104
105 void set_vector(t_rac const * v)
106 {
107 m_v = v;
108 }
109
111
121 size_type operator()(const size_type l, const size_type r) const
122 {
123 assert(l <= r);
124 assert(r < size());
125 if (l == r)
126 return l;
127 if (l + 1 == r)
128 return mm_trait::compare((*m_v)[l], (*m_v)[r]) ? l : r;
129 size_type k = bits::hi(r - l);
130 const size_type rr = r - (1ULL << k) + 1;
131 return mm_trait::compare((*m_v)[l + m_table[k - 1][l]], (*m_v)[rr + m_table[k - 1][rr]])
132 ? l + m_table[k - 1][l]
133 : rr + m_table[k - 1][rr];
134 }
135
137 {
138 if (m_v == nullptr)
139 return 0;
140 else
141 return m_v->size();
142 }
143
144 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
145 {
146 size_type written_bytes = 0;
147 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
148 written_bytes += write_member(m_k, out);
149 if (m_k > 0)
150 {
151 for (size_type i = 0; i < m_k; ++i)
152 written_bytes += m_table[i].serialize(out);
153 }
154 structure_tree::add_size(child, written_bytes);
155 return written_bytes;
156 }
157
158 void load(std::istream & in, t_rac const * v)
159 {
160 set_vector(v);
161 read_member(m_k, in);
162 if (m_k > 0)
163 {
164 m_table.resize(m_k);
165 for (size_type i = 0; i < m_k; ++i)
166 m_table[i].load(in);
167 }
168 }
169
170 template <typename archive_t>
171 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
172 {
173 ar(CEREAL_NVP(m_k));
174 for (size_type i = 0; i < m_k; ++i)
175 {
176 ar(CEREAL_NVP(m_table[i]));
177 }
178 }
179
180 template <typename archive_t>
181 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
182 {
183 ar(CEREAL_NVP(m_k));
184 m_table.resize(m_k);
185 for (size_type i = 0; i < m_k; ++i)
186 {
187 ar(CEREAL_NVP(m_table[i]));
188 }
189 }
190
192 bool operator==(rmq_support_sparse_table const & other) const noexcept
193 {
194 return (m_table == other.m_table);
195 }
196
198 bool operator!=(rmq_support_sparse_table const & other) const noexcept
199 {
200 return !(*this == other);
201 }
202};
203
204} // namespace sdsl
205#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
int_vector_size_type size_type
A class to support range minimum or range maximum queries on a random access container.
rmq_support_sparse_table(t_rac const *v=nullptr)
bool operator!=(rmq_support_sparse_table const &other) const noexcept
Inequality operator.
void load(std::istream &in, t_rac const *v)
rmq_support_sparse_table(rmq_support_sparse_table const &rm)=default
Copy constructor.
rmq_support_sparse_table & operator=(rmq_support_sparse_table &&rm)=default
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
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 & operator=(rmq_support_sparse_table const &rm)=default
rmq_support_sparse_table(rmq_support_sparse_table &&rm)=default
Move constructor.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
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.
io.hpp contains some methods for reading/writing sdsl structures.
Namespace for the succinct data structure library.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
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)
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:652
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.