9#ifndef INCLUDED_SDSL_SORTED_INT_STACK
10#define INCLUDED_SDSL_SORTED_INT_STACK
44 std::vector<size_type> m_overflow;
92 void load(std::istream & in);
93 template <
typename archive_t>
95 template <
typename archive_t>
115 assert(
empty() || m_top < x);
119 if (m_overflow.empty())
121 m_overflow.push_back(m_top);
123 m_overflow.push_back(x);
129 m_stack[bn] ^= (1ULL << block_pos(x));
130 if (m_stack[bn - 1] == 0)
132 m_stack[bn - 1] = 0x8000000000000000ULL | m_top;
143 if (m_top > m_n + 63)
145 m_overflow.pop_back();
146 m_top = m_overflow.back();
147 if (m_overflow.size() == 1)
148 m_overflow.pop_back();
153 uint64_t w = m_stack[bn];
154 assert((w >> 63) == 0);
155 w ^= (1ULL << block_pos(m_top));
168 m_top = (bn - 1) * 63 +
bits::hi(w);
173 m_top = w & 0x7FFFFFFFFFFFFFFFULL;
191 return written_bytes;
203template <
typename archive_t>
213template <
typename archive_t>
226 return (m_n == other.m_n) && (m_cnt == other.m_cnt) && (m_top == other.m_top) && (m_stack == other.m_stack)
227 && (m_overflow == other.m_overflow);
233 return !(*
this == other);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#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
sorted_int_stack & operator=(sorted_int_stack const &)=default
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.
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.
sorted_int_stack(sorted_int_stack const &)=default
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
void pop()
Pop the topmost element of the stack.
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
Namespace for the succinct data structure library.
size_t write_member(T const &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)
std::enable_if< has_serialize< X >::value, typenameX::size_type >::type serialize(X const &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.