8#ifndef INCLUDED_SDSL_RMQ_SUPPORT_SPARSE_TABLE
9#define INCLUDED_SDSL_RMQ_SUPPORT_SPARSE_TABLE
28template <
class t_rac =
int_vector<>,
bool t_min = true>
29class rmq_support_sparse_table;
31template <
class t_rac =
int_vector<>>
50template <
class t_rac,
bool t_min>
55 std::vector<int_vector<>> m_table;
70 while (2 * (1ULL << k) < n)
76 m_table[i] =
int_vector<>(n - (1ULL << (i + 1)) + 1, 0, i + 1);
85 for (
size_type j = 0; j < m_table[i].size(); ++j)
88 (*m_v)[j + (1ULL << i) + m_table[i - 1][j + (1ULL << i)]])
90 : (1ULL << i) + m_table[i - 1][j + (1ULL << i)];
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];
152 written_bytes += m_table[i].
serialize(out);
155 return written_bytes;
158 void load(std::istream & in, t_rac
const * v)
170 template <
typename archive_t>
180 template <
typename archive_t>
194 return (m_table == other.m_table);
200 return !(*
this == other);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
A generic vector class for integers of width .
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 set_vector(t_rac const *v)
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.
t_rac::size_type size_type
t_rac::size_type value_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
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="")
void read_member(T &t, std::istream &in)
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.
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.