SDSL 3.0.1
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
17namespace sdsl
18{
19
20template <class t_rac = int_vector<>, bool t_min = true>
21class rmq_support_sparse_table;
22
23template <class t_rac = int_vector<>>
25
27
42template <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
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:31
int_vector_size_type size_type
Definition: int_vector.hpp:229
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)
rmq_support_sparse_table & operator=(rmq_support_sparse_table &&rm)=default
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.
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, 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.
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 constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651