SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::rmq_support_sparse_table< t_rac, t_min > Class Template Reference

A class to support range minimum or range maximum queries on a random access container. More...

#include <rmq_support_sparse_table.hpp>

Public Types

typedef t_rac::size_type size_type
 
typedef t_rac::size_type value_type
 

Public Member Functions

 rmq_support_sparse_table (t_rac const *v=nullptr)
 
 rmq_support_sparse_table (rmq_support_sparse_table const &rm)=default
 Copy constructor.
 
 rmq_support_sparse_table (rmq_support_sparse_table &&rm)=default
 Move constructor.
 
rmq_support_sparse_tableoperator= (rmq_support_sparse_table const &rm)=default
 
rmq_support_sparse_tableoperator= (rmq_support_sparse_table &&rm)=default
 
void set_vector (t_rac const *v)
 
size_type operator() (const size_type l, const size_type r) const
 Range minimum/maximum query for the supported random access container v.
 
size_type size () const
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 
void load (std::istream &in, t_rac const *v)
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 
bool operator== (rmq_support_sparse_table const &other) const noexcept
 Equality operator.
 
bool operator!= (rmq_support_sparse_table const &other) const noexcept
 Inequality operator.
 

Detailed Description

template<class t_rac, bool t_min>
class sdsl::rmq_support_sparse_table< t_rac, t_min >

A class to support range minimum or range maximum queries on a random access container.

Template Parameters
t_racType of random access container for which the structure should be build.
t_minSpecifies whether the data structure should answer range min/max queries (mimumum=true)
Reference
Michael A. Bender, Martin Farach-Colton: The LCA Problem Revisited. LATIN 2000: 88-94
Time complexity
$ \Order{1} $ for the range minimum/maximum queries.
Space complexity:
$ \Order{n\log^2 n} $ bits for the data structure ( $ n=size() $ ). We used bit compression to get a good result in practice.

Definition at line 51 of file rmq_support_sparse_table.hpp.

Member Typedef Documentation

◆ size_type

template<class t_rac , bool t_min>
typedef t_rac::size_type sdsl::rmq_support_sparse_table< t_rac, t_min >::size_type

Definition at line 59 of file rmq_support_sparse_table.hpp.

◆ value_type

template<class t_rac , bool t_min>
typedef t_rac::size_type sdsl::rmq_support_sparse_table< t_rac, t_min >::value_type

Definition at line 60 of file rmq_support_sparse_table.hpp.

Constructor & Destructor Documentation

◆ rmq_support_sparse_table() [1/3]

template<class t_rac , bool t_min>
sdsl::rmq_support_sparse_table< t_rac, t_min >::rmq_support_sparse_table ( t_rac const *  v = nullptr)
inline

Definition at line 62 of file rmq_support_sparse_table.hpp.

◆ rmq_support_sparse_table() [2/3]

template<class t_rac , bool t_min>
sdsl::rmq_support_sparse_table< t_rac, t_min >::rmq_support_sparse_table ( rmq_support_sparse_table< t_rac, t_min > const &  rm)
default

Copy constructor.

◆ rmq_support_sparse_table() [3/3]

template<class t_rac , bool t_min>
sdsl::rmq_support_sparse_table< t_rac, t_min >::rmq_support_sparse_table ( rmq_support_sparse_table< t_rac, t_min > &&  rm)
default

Move constructor.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_rac , bool t_min>
template<typename archive_t >
void sdsl::rmq_support_sparse_table< t_rac, t_min >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 181 of file rmq_support_sparse_table.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_rac , bool t_min>
template<typename archive_t >
void sdsl::rmq_support_sparse_table< t_rac, t_min >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 171 of file rmq_support_sparse_table.hpp.

◆ load()

template<class t_rac , bool t_min>
void sdsl::rmq_support_sparse_table< t_rac, t_min >::load ( std::istream &  in,
t_rac const *  v 
)
inline

Definition at line 158 of file rmq_support_sparse_table.hpp.

◆ operator!=()

template<class t_rac , bool t_min>
bool sdsl::rmq_support_sparse_table< t_rac, t_min >::operator!= ( rmq_support_sparse_table< t_rac, t_min > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 198 of file rmq_support_sparse_table.hpp.

◆ operator()()

template<class t_rac , bool t_min>
size_type sdsl::rmq_support_sparse_table< t_rac, t_min >::operator() ( const size_type  l,
const size_type  r 
) const
inline

Range minimum/maximum query for the supported random access container v.

Parameters
lLeftmost position of the interval $[\ell..r]$.
rRightmost position of the interval $[\ell..r]$.
Returns
The minimal index i with $\ell \leq i \leq r$ for which $ v[i] $ is minimal/maximal.
Precondition
Time complexity
$ \Order{1} $

Definition at line 121 of file rmq_support_sparse_table.hpp.

◆ operator=() [1/2]

template<class t_rac , bool t_min>
rmq_support_sparse_table & sdsl::rmq_support_sparse_table< t_rac, t_min >::operator= ( rmq_support_sparse_table< t_rac, t_min > &&  rm)
default

◆ operator=() [2/2]

template<class t_rac , bool t_min>
rmq_support_sparse_table & sdsl::rmq_support_sparse_table< t_rac, t_min >::operator= ( rmq_support_sparse_table< t_rac, t_min > const &  rm)
default

◆ operator==()

template<class t_rac , bool t_min>
bool sdsl::rmq_support_sparse_table< t_rac, t_min >::operator== ( rmq_support_sparse_table< t_rac, t_min > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 192 of file rmq_support_sparse_table.hpp.

◆ serialize()

template<class t_rac , bool t_min>
size_type sdsl::rmq_support_sparse_table< t_rac, t_min >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Definition at line 144 of file rmq_support_sparse_table.hpp.

◆ set_vector()

template<class t_rac , bool t_min>
void sdsl::rmq_support_sparse_table< t_rac, t_min >::set_vector ( t_rac const *  v)
inline

Definition at line 105 of file rmq_support_sparse_table.hpp.

◆ size()

template<class t_rac , bool t_min>
size_type sdsl::rmq_support_sparse_table< t_rac, t_min >::size ( ) const
inline

Definition at line 136 of file rmq_support_sparse_table.hpp.


The documentation for this class was generated from the following file: