SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
sorted_int_stack.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
9#ifndef INCLUDED_SDSL_SORTED_INT_STACK
10#define INCLUDED_SDSL_SORTED_INT_STACK
11
12#include <vector>
13
14#include <sdsl/int_vector.hpp>
15
17namespace sdsl
18{
19
21
25{
26 public:
28
29 private:
30 size_type m_n; // maximal value which can be stored on the stack
31 size_type m_cnt; // counter for elements on the stack
32 size_type m_top; // top element of the stack
33 int_vector<64> m_stack; // memory for the stack
34 std::vector<size_type> m_overflow; // memory for the elements which are greater than n
35
36 inline size_type block_nr(size_type x) { return x / 63; }; // maybe we can speed this up with bit hacks
37 inline size_type block_pos(size_type x) { return x % 63; }; // maybe we can speed this up with bit hacks
38 public:
39 sorted_int_stack(size_type n);
44
47 bool empty() const { return 0 == m_cnt; };
48
52 size_type top() const;
53
56 void pop();
57
62 void push(size_type x);
63
66 size_type size() const { return m_cnt; };
67
68 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
69 void load(std::istream & in);
70 template <typename archive_t>
71 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
72 template <typename archive_t>
73 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
74 bool operator==(sorted_int_stack const & other) const noexcept;
75 bool operator!=(sorted_int_stack const & other) const noexcept;
76};
77
79 : m_n(n)
80 , m_cnt(0)
81 , m_top(0)
82{
83 m_stack = int_vector<64>(block_nr(n) + 2, 0);
84 m_stack[0] = 1;
85}
86
88{
89 return m_top - 63;
90}
91
93{
94 x += 63;
95 assert(empty() || m_top < x);
96 ++m_cnt; //< increment counter
97 if (x > m_n + 63)
98 {
99 if (m_overflow.empty()) { m_overflow.push_back(m_top); }
100 m_overflow.push_back(x);
101 m_top = x;
102 }
103 else
104 {
105 size_type bn = block_nr(x);
106 m_stack[bn] ^= (1ULL << block_pos(x));
107 if (m_stack[bn - 1] == 0) { m_stack[bn - 1] = 0x8000000000000000ULL | m_top; }
108 m_top = x;
109 }
110}
111
113{
114 if (!empty())
115 {
116 --m_cnt; //< decrement counter
117 if (m_top > m_n + 63)
118 {
119 m_overflow.pop_back();
120 m_top = m_overflow.back();
121 if (m_overflow.size() == 1) m_overflow.pop_back();
122 }
123 else
124 {
125 size_type bn = block_nr(m_top);
126 uint64_t w = m_stack[bn];
127 assert((w >> 63) == 0); // highest bit is not set, as the block contains no pointer
128 w ^= (1ULL << block_pos(m_top));
129 m_stack[bn] = w;
130 if (w > 0) { m_top = bn * 63 + bits::hi(w); }
131 else
132 { // w==0 and cnt>0
133 assert(bn > 0);
134 w = m_stack[bn - 1];
135 if ((w >> 63) == 0)
136 { // highest bit is not set => the block contains no pointer
137 assert(w > 0);
138 m_top = (bn - 1) * 63 + bits::hi(w);
139 }
140 else
141 { // block contains pointers
142 m_stack[bn - 1] = 0;
143 m_top = w & 0x7FFFFFFFFFFFFFFFULL;
144 }
145 }
146 }
147 }
148}
149
152 std::string name) const
153{
154 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
155 size_type written_bytes = 0;
156 written_bytes += write_member(m_n, out);
157 written_bytes += write_member(m_top, out);
158 written_bytes += write_member(m_cnt, out);
159 written_bytes += m_stack.serialize(out);
160 written_bytes += sdsl::serialize(m_overflow, out, child, "overflow");
161 structure_tree::add_size(child, written_bytes);
162 return written_bytes;
163}
164
165inline void sorted_int_stack::load(std::istream & in)
166{
167 read_member(m_n, in);
168 read_member(m_top, in);
169 read_member(m_cnt, in);
170 m_stack.load(in);
171 sdsl::load(m_overflow, in);
172}
173
174template <typename archive_t>
176{
177 ar(CEREAL_NVP(m_n));
178 ar(CEREAL_NVP(m_cnt));
179 ar(CEREAL_NVP(m_top));
180 ar(CEREAL_NVP(m_stack));
181 ar(CEREAL_NVP(m_overflow));
182}
183
184template <typename archive_t>
186{
187 ar(CEREAL_NVP(m_n));
188 ar(CEREAL_NVP(m_cnt));
189 ar(CEREAL_NVP(m_top));
190 ar(CEREAL_NVP(m_stack));
191 ar(CEREAL_NVP(m_overflow));
192}
193
195inline bool sorted_int_stack::operator==(sorted_int_stack const & other) const noexcept
196{
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);
199}
200
202inline bool sorted_int_stack::operator!=(sorted_int_stack const & other) const noexcept
203{
204 return !(*this == other);
205}
206
207} // end namespace sdsl
208
209#endif // end file
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
#define CEREAL_LOAD_FUNCTION_NAME
Definition: cereal.hpp:34
#define CEREAL_SAVE_FUNCTION_NAME
Definition: cereal.hpp:35
A generic vector class for integers of width .
Definition: int_vector.hpp:216
int_vector_size_type size_type
Definition: int_vector.hpp:229
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 & 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="")
Definition: io.hpp:131
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:84
void read_member(T &t, std::istream &in)
Definition: io.hpp:111
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
Definition: io.hpp:154
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651