SDSL  3.0.0
Succinct Data Structure Library
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. More...
 
template<class t_rac >
 rmq_succinct_sct (const t_rac *v=nullptr)
 Constructor. More...
 
 rmq_succinct_sct (const rmq_succinct_sct &rm)
 Copy constructor. More...
 
 rmq_succinct_sct (rmq_succinct_sct &&rm)
 Move constructor. More...
 
rmq_succinct_sctoperator= (const rmq_succinct_sct &rm)
 
rmq_succinct_sctoperator= (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. More...
 
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. More...
 
bool operator!= (rmq_succinct_sct const &other) const noexcept
 Inequality operator. More...
 

Public Attributes

const bit_vectorsct_bp = m_sct_bp
 
const bp_support_typesct_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} $#144 bits for the data structure ( $ \Order{1} $#138@_fakenl ).

Definition at line 40 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 48 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 46 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 47 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 54 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 ( const t_rac *  v = nullptr)
inline

Constructor.

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

Definition at line 61 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 ( const rmq_succinct_sct< t_min, t_bp_support > &  rm)
inline

Copy constructor.

Definition at line 78 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 86 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 172 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 165 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 158 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 186 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 120 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= ( const rmq_succinct_sct< t_min, t_bp_support > &  rm)
inline

Definition at line 88 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 > &&  rm)
inline

Definition at line 98 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 180 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 148 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 146 of file rmq_succinct_sct.hpp.

Member Data Documentation

◆ sct_bp

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

Definition at line 50 of file rmq_succinct_sct.hpp.

◆ sct_bp_support

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

Definition at line 51 of file rmq_succinct_sct.hpp.


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