SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 > Class Template Reference

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

#include <rmq_succinct_sada.hpp>

Public Types

typedef bit_vector::size_type size_type
 
typedef bit_vector::size_type value_type
 
typedef t_bp_support bp_support_type
 
typedef t_rank_10 rank_support10_type
 
typedef t_select_10 select_support10_type
 

Public Member Functions

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

Public Attributes

const bit_vectorect_bp = m_ect_bp
 
const bp_support_typeect_bp_support = m_ect_bp_support
 
const rank_support10_typeect_bp_rank10 = m_ect_bp_rank10
 
const select_support10_typeect_bp_select10 = m_ect_bp_select10
 

Detailed Description

template<bool t_min, class t_bp_support, class t_rank_10, class t_select_10>
class sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >

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-DFS
t_rank_10Type of rank structure for it pattern 10.
t_select_10Type of select structure for bit pattern 10.
Time complexity
$ \Order{1} $ for the range min/max queries if the BPS supports constant time operations.
Space complexity:
$ 4n+o(n) $ bits for the data structure ( $ n=size() $ ).
Reference
TODO: Kunihiko Sadakane

Definition at line 57 of file rmq_succinct_sada.hpp.

Member Typedef Documentation

◆ bp_support_type

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
typedef t_bp_support sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::bp_support_type

Definition at line 68 of file rmq_succinct_sada.hpp.

◆ rank_support10_type

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
typedef t_rank_10 sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::rank_support10_type

Definition at line 69 of file rmq_succinct_sada.hpp.

◆ select_support10_type

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
typedef t_select_10 sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::select_support10_type

Definition at line 70 of file rmq_succinct_sada.hpp.

◆ size_type

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
typedef bit_vector::size_type sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::size_type

Definition at line 65 of file rmq_succinct_sada.hpp.

◆ value_type

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
typedef bit_vector::size_type sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::value_type

Definition at line 66 of file rmq_succinct_sada.hpp.

Constructor & Destructor Documentation

◆ rmq_succinct_sada() [1/4]

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::rmq_succinct_sada ( )
inline

Default Constructor.

Definition at line 136 of file rmq_succinct_sada.hpp.

◆ rmq_succinct_sada() [2/4]

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

Constructor.

Definition at line 140 of file rmq_succinct_sada.hpp.

◆ rmq_succinct_sada() [3/4]

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

Copy constructor.

Definition at line 154 of file rmq_succinct_sada.hpp.

◆ rmq_succinct_sada() [4/4]

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::rmq_succinct_sada ( rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 > &&  rm)
inline

Move constructor.

Definition at line 166 of file rmq_succinct_sada.hpp.

◆ ~rmq_succinct_sada()

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::~rmq_succinct_sada ( )
inline

Destructor.

Definition at line 169 of file rmq_succinct_sada.hpp.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

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

Definition at line 251 of file rmq_succinct_sada.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

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

Definition at line 242 of file rmq_succinct_sada.hpp.

◆ load()

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

Definition at line 233 of file rmq_succinct_sada.hpp.

◆ operator!=()

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

Inequality operator.

Definition at line 270 of file rmq_succinct_sada.hpp.

◆ operator()()

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
size_type sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::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 207 of file rmq_succinct_sada.hpp.

◆ operator=() [1/2]

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

Definition at line 171 of file rmq_succinct_sada.hpp.

◆ operator=() [2/2]

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

Definition at line 181 of file rmq_succinct_sada.hpp.

◆ operator==()

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

Equality operator.

Definition at line 263 of file rmq_succinct_sada.hpp.

◆ serialize()

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

Definition at line 221 of file rmq_succinct_sada.hpp.

◆ size()

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

Definition at line 219 of file rmq_succinct_sada.hpp.

Member Data Documentation

◆ ect_bp

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
const bit_vector& sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::ect_bp = m_ect_bp

Definition at line 72 of file rmq_succinct_sada.hpp.

◆ ect_bp_rank10

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
const rank_support10_type& sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::ect_bp_rank10 = m_ect_bp_rank10

Definition at line 74 of file rmq_succinct_sada.hpp.

◆ ect_bp_select10

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
const select_support10_type& sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::ect_bp_select10 = m_ect_bp_select10

Definition at line 75 of file rmq_succinct_sada.hpp.

◆ ect_bp_support

template<bool t_min, class t_bp_support , class t_rank_10 , class t_select_10 >
const bp_support_type& sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::ect_bp_support = m_ect_bp_support

Definition at line 73 of file rmq_succinct_sada.hpp.


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