SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Public Attributes | List of all members
sdsl::rmq_succinct_sct< t_min, t_bp_support > Class Template Reference

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

#include <rmq_succinct_sct.hpp>

Public Types

typedef bit_vector::size_type size_type
 
typedef bit_vector::size_type value_type
 
typedef t_bp_support bp_support_type
 

Public Member Functions

 rmq_succinct_sct ()
 Default constructor.
 
template<class t_rac>
 rmq_succinct_sct (t_rac const *v=nullptr)
 Constructor.
 
 rmq_succinct_sct (rmq_succinct_sct const &rm)
 Copy constructor.
 
 rmq_succinct_sct (rmq_succinct_sct &&rm)
 Move constructor.
 
rmq_succinct_sct & operator= (rmq_succinct_sct const &rm)
 
rmq_succinct_sct & operator= (rmq_succinct_sct &&rm)
 
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)
 
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_succinct_sct const &other) const noexcept
 Equality operator.
 
bool operator!= (rmq_succinct_sct const &other) const noexcept
 Inequality operator.
 

Public Attributes

bit_vector const & sct_bp = m_sct_bp
 
bp_support_type const & sct_bp_support = m_sct_bp_support
 

Detailed Description

template<bool t_min, class t_bp_support>
class sdsl::rmq_succinct_sct< t_min, t_bp_support >

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

Template Parameters
t_minSpecifies whether the data structure should answer range min/max queries (mimumum=true)
t_bp_supportType of Support structure for the BPS-SCT.
Time complexity
$ \Order{1} $ for the range minimum/maximum queries if the balanced parentheses support structure supports constant time operations.
Space complexity: $ \Order{1} $#143 bits for the data structure ( $ \Order{1} $#144@_fakenl ).

Definition at line 47 of file rmq_succinct_sct.hpp.

Member Typedef Documentation

◆ bp_support_type

template<bool t_min, class t_bp_support>
typedef t_bp_support sdsl::rmq_succinct_sct< t_min, t_bp_support >::bp_support_type

Definition at line 55 of file rmq_succinct_sct.hpp.

◆ size_type

template<bool t_min, class t_bp_support>
typedef bit_vector::size_type sdsl::rmq_succinct_sct< t_min, t_bp_support >::size_type

Definition at line 53 of file rmq_succinct_sct.hpp.

◆ value_type

template<bool t_min, class t_bp_support>
typedef bit_vector::size_type sdsl::rmq_succinct_sct< t_min, t_bp_support >::value_type

Definition at line 54 of file rmq_succinct_sct.hpp.

Constructor & Destructor Documentation

◆ rmq_succinct_sct() [1/4]

template<bool t_min, class t_bp_support>
sdsl::rmq_succinct_sct< t_min, t_bp_support >::rmq_succinct_sct ( )
inline

Default constructor.

Definition at line 61 of file rmq_succinct_sct.hpp.

◆ rmq_succinct_sct() [2/4]

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

Constructor.

Template Parameters
t_racA random access container.
Parameters
vPointer to container object.

Definition at line 69 of file rmq_succinct_sct.hpp.

◆ rmq_succinct_sct() [3/4]

template<bool t_min, class t_bp_support>
sdsl::rmq_succinct_sct< t_min, t_bp_support >::rmq_succinct_sct ( rmq_succinct_sct< t_min, t_bp_support > const & rm)
inline

Copy constructor.

Definition at line 86 of file rmq_succinct_sct.hpp.

◆ rmq_succinct_sct() [4/4]

template<bool t_min, class t_bp_support>
sdsl::rmq_succinct_sct< t_min, t_bp_support >::rmq_succinct_sct ( rmq_succinct_sct< t_min, t_bp_support > && rm)
inline

Move constructor.

Definition at line 92 of file rmq_succinct_sct.hpp.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

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

Definition at line 185 of file rmq_succinct_sct.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

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

Definition at line 178 of file rmq_succinct_sct.hpp.

◆ load()

template<bool t_min, class t_bp_support>
void sdsl::rmq_succinct_sct< t_min, t_bp_support >::load ( std::istream & in)
inline

Definition at line 171 of file rmq_succinct_sct.hpp.

◆ operator!=()

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

Inequality operator.

Definition at line 199 of file rmq_succinct_sct.hpp.

◆ operator()()

template<bool t_min, class t_bp_support>
size_type sdsl::rmq_succinct_sct< t_min, t_bp_support >::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 129 of file rmq_succinct_sct.hpp.

◆ operator=() [1/2]

template<bool t_min, class t_bp_support>
rmq_succinct_sct & sdsl::rmq_succinct_sct< t_min, t_bp_support >::operator= ( rmq_succinct_sct< t_min, t_bp_support > && rm)
inline

Definition at line 107 of file rmq_succinct_sct.hpp.

◆ operator=() [2/2]

template<bool t_min, class t_bp_support>
rmq_succinct_sct & sdsl::rmq_succinct_sct< t_min, t_bp_support >::operator= ( rmq_succinct_sct< t_min, t_bp_support > const & rm)
inline

Definition at line 97 of file rmq_succinct_sct.hpp.

◆ operator==()

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

Equality operator.

Definition at line 193 of file rmq_succinct_sct.hpp.

◆ serialize()

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

Definition at line 161 of file rmq_succinct_sct.hpp.

◆ size()

template<bool t_min, class t_bp_support>
size_type sdsl::rmq_succinct_sct< t_min, t_bp_support >::size ( ) const
inline

Definition at line 156 of file rmq_succinct_sct.hpp.

Member Data Documentation

◆ sct_bp

template<bool t_min, class t_bp_support>
bit_vector const& sdsl::rmq_succinct_sct< t_min, t_bp_support >::sct_bp = m_sct_bp

Definition at line 57 of file rmq_succinct_sct.hpp.

◆ sct_bp_support

template<bool t_min, class t_bp_support>
bp_support_type const& sdsl::rmq_succinct_sct< t_min, t_bp_support >::sct_bp_support = m_sct_bp_support

Definition at line 58 of file rmq_succinct_sct.hpp.

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