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_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 (t_rac const *v=nullptr)
 Constructor.
 
 rmq_succinct_sada (rmq_succinct_sada const &rm)
 Copy constructor.
 
 rmq_succinct_sada (rmq_succinct_sada &&rm)
 Move constructor.
 
 ~rmq_succinct_sada ()
 Destructor.
 
rmq_succinct_sada & operator= (rmq_succinct_sada const &rm)
 
rmq_succinct_sada & operator= (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

bit_vector const & ect_bp = m_ect_bp
 
bp_support_type const & ect_bp_support = m_ect_bp_support
 
rank_support10_type const & ect_bp_rank10 = m_ect_bp_rank10
 
select_support10_type const & ect_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 61 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 72 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 73 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 74 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 69 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 70 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 146 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 ( t_rac const * v = nullptr)
inline

Constructor.

Definition at line 151 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 ( rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 > const & rm)
inline

Copy constructor.

Definition at line 165 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 177 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 183 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 270 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 261 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 252 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 289 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 222 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= ( rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 > && rm)
inline

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

Definition at line 186 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 282 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 240 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 235 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>
bit_vector const& sdsl::rmq_succinct_sada< t_min, t_bp_support, t_rank_10, t_select_10 >::ect_bp = m_ect_bp

Definition at line 76 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>
rank_support10_type const& 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 78 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>
select_support10_type const& 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 79 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>
bp_support_type const& 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 77 of file rmq_succinct_sada.hpp.

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