9#ifndef INCLUDED_SDSL_SORTED_INT_STACK
10#define INCLUDED_SDSL_SORTED_INT_STACK
34 std::vector<size_type> m_overflow;
47 bool empty()
const {
return 0 == m_cnt; };
69 void load(std::istream & in);
70 template <
typename archive_t>
72 template <
typename archive_t>
95 assert(
empty() || m_top < x);
99 if (m_overflow.empty()) { m_overflow.push_back(m_top); }
100 m_overflow.push_back(x);
106 m_stack[bn] ^= (1ULL << block_pos(x));
107 if (m_stack[bn - 1] == 0) { m_stack[bn - 1] = 0x8000000000000000ULL | m_top; }
117 if (m_top > m_n + 63)
119 m_overflow.pop_back();
120 m_top = m_overflow.back();
121 if (m_overflow.size() == 1) m_overflow.pop_back();
126 uint64_t w = m_stack[bn];
127 assert((w >> 63) == 0);
128 w ^= (1ULL << block_pos(m_top));
130 if (w > 0) { m_top = bn * 63 +
bits::hi(w); }
138 m_top = (bn - 1) * 63 +
bits::hi(w);
143 m_top = w & 0x7FFFFFFFFFFFFFFFULL;
152 std::string name)
const
162 return written_bytes;
174template <
typename archive_t>
184template <
typename archive_t>
197 return (m_n == other.m_n) && (m_cnt == other.m_cnt) && (m_top == other.m_top) && (m_stack == other.m_stack) &&
198 (m_overflow == other.m_overflow);
204 return !(*
this == other);
#define CEREAL_LOAD_FUNCTION_NAME
#define CEREAL_SAVE_FUNCTION_NAME
A generic vector class for integers of width .
int_vector_size_type size_type
void load(std::istream &in)
Load the int_vector for a stream.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
A stack class which can contain integers in strictly increasing order.
int_vector< 64 >::size_type size_type
void load(std::istream &in)
size_type size() const
Returns the number of element is the stack.
size_type top() const
Returns the topmost element of the stack.
sorted_int_stack(const sorted_int_stack &)=default
bool operator!=(sorted_int_stack const &other) const noexcept
Inequality operator.
bool empty() const
Returns if the stack is empty.
sorted_int_stack(sorted_int_stack &&)=default
bool operator==(sorted_int_stack const &other) const noexcept
Equality operator.
void push(size_type x)
Push value x on the stack.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
sorted_int_stack(size_type n)
sorted_int_stack & operator=(sorted_int_stack &&)=default
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
sorted_int_stack & operator=(const sorted_int_stack &)=default
void pop()
Pop the topmost element of the stack.
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
std::enable_if< has_serialize< X >::value, typenameX::size_type >::type serialize(const X &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.