SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::sorted_stack_support Class Reference

A stack which contains strictly increasing numbers in the range from $0$ to $n$. More...

#include <sorted_stack_support.hpp>

Public Types

typedef int_vector< 64 >::size_type size_type
 

Public Member Functions

 sorted_stack_support (size_type n)
 Constructor. More...
 
 sorted_stack_support (const sorted_stack_support &)=default
 
 sorted_stack_support (sorted_stack_support &&)=default
 
sorted_stack_supportoperator= (const sorted_stack_support &)=default
 
sorted_stack_supportoperator= (sorted_stack_support &&)=default
 
bool empty () const
 Returns if the stack is empty. More...
 
size_type top () const
 Returns the topmost index on the stack. More...
 
void pop ()
 Pop the topmost index of the stack. More...
 
void push (size_type x)
 Push the index x of vector vec onto the stack. More...
 
size_type size () const
 Returns the number of element is the stack. More...
 
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== (sorted_stack_support const &other) const noexcept
 Equality operator. More...
 
bool operator!= (sorted_stack_support const &other) const noexcept
 Inequality operator. More...
 

Detailed Description

A stack which contains strictly increasing numbers in the range from $0$ to $n$.

Reference
Johannes Fischer: Optimal Succinctness for Range Minimum Queries LATIN 2010
Space complexity
$n$ bits

Definition at line 24 of file sorted_stack_support.hpp.

Member Typedef Documentation

◆ size_type

Definition at line 27 of file sorted_stack_support.hpp.

Constructor & Destructor Documentation

◆ sorted_stack_support() [1/3]

sdsl::sorted_stack_support::sorted_stack_support ( size_type  n)
inline

Constructor.

Parameters
nMaximum that can be pushed onto the stack

Definition at line 81 of file sorted_stack_support.hpp.

◆ sorted_stack_support() [2/3]

sdsl::sorted_stack_support::sorted_stack_support ( const sorted_stack_support )
default

◆ sorted_stack_support() [3/3]

sdsl::sorted_stack_support::sorted_stack_support ( sorted_stack_support &&  )
default

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<typename archive_t >
void sdsl::sorted_stack_support::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)

Definition at line 169 of file sorted_stack_support.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<typename archive_t >
void sdsl::sorted_stack_support::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const

Definition at line 160 of file sorted_stack_support.hpp.

◆ empty()

bool sdsl::sorted_stack_support::empty ( ) const
inline

Returns if the stack is empty.

Definition at line 50 of file sorted_stack_support.hpp.

◆ load()

void sdsl::sorted_stack_support::load ( std::istream &  in)
inline

Definition at line 151 of file sorted_stack_support.hpp.

◆ operator!=()

bool sdsl::sorted_stack_support::operator!= ( sorted_stack_support const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 184 of file sorted_stack_support.hpp.

◆ operator=() [1/2]

sorted_stack_support & sdsl::sorted_stack_support::operator= ( const sorted_stack_support )
default

◆ operator=() [2/2]

sorted_stack_support & sdsl::sorted_stack_support::operator= ( sorted_stack_support &&  )
default

◆ operator==()

bool sdsl::sorted_stack_support::operator== ( sorted_stack_support const &  other) const
inlinenoexcept

Equality operator.

Definition at line 178 of file sorted_stack_support.hpp.

◆ pop()

void sdsl::sorted_stack_support::pop ( )
inline

Pop the topmost index of the stack.

Definition at line 108 of file sorted_stack_support.hpp.

◆ push()

void sdsl::sorted_stack_support::push ( size_type  x)
inline

Push the index x of vector vec onto the stack.

x Index of the value in vec which should be pushed onto the stack.
Precondition
top() < x and x <= n

Definition at line 97 of file sorted_stack_support.hpp.

◆ serialize()

sorted_stack_support::size_type sdsl::sorted_stack_support::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Definition at line 137 of file sorted_stack_support.hpp.

◆ size()

size_type sdsl::sorted_stack_support::size ( ) const
inline

Returns the number of element is the stack.

Definition at line 69 of file sorted_stack_support.hpp.

◆ top()

sorted_stack_support::size_type sdsl::sorted_stack_support::top ( ) const
inline

Returns the topmost index on the stack.

Precondition
empty()==false

Definition at line 91 of file sorted_stack_support.hpp.


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