SDSL 3.0.3
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 <algorithm>
13#include <assert.h>
14#include <iosfwd>
15#include <stdint.h>
16#include <string>
17#include <vector>
18
19#include <sdsl/bits.hpp>
20#include <sdsl/cereal.hpp>
21#include <sdsl/int_vector.hpp>
22#include <sdsl/io.hpp>
24#include <sdsl/util.hpp>
25
27namespace sdsl
28{
29
31
35{
36public:
38
39private:
40 size_type m_n; // maximal value which can be stored on the stack
41 size_type m_cnt; // counter for elements on the stack
42 size_type m_top; // top element of the stack
43 int_vector<64> m_stack; // memory for the stack
44 std::vector<size_type> m_overflow; // memory for the elements which are greater than n
45
46 inline size_type block_nr(size_type x)
47 {
48 return x / 63;
49 }; // maybe we can speed this up with bit hacks
50 inline size_type block_pos(size_type x)
51 {
52 return x % 63;
53 }; // maybe we can speed this up with bit hacks
54
55public:
61
64 bool empty() const
65 {
66 return 0 == m_cnt;
67 };
68
72 size_type top() const;
73
76 void pop();
77
82 void push(size_type x);
83
87 {
88 return m_cnt;
89 };
90
91 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
92 void load(std::istream & in);
93 template <typename archive_t>
94 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
95 template <typename archive_t>
96 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
97 bool operator==(sorted_int_stack const & other) const noexcept;
98 bool operator!=(sorted_int_stack const & other) const noexcept;
99};
100
101inline sorted_int_stack::sorted_int_stack(size_type n) : m_n(n), m_cnt(0), m_top(0)
102{
103 m_stack = int_vector<64>(block_nr(n) + 2, 0);
104 m_stack[0] = 1;
105}
106
108{
109 return m_top - 63;
110}
111
113{
114 x += 63;
115 assert(empty() || m_top < x);
116 ++m_cnt; //< increment counter
117 if (x > m_n + 63)
118 {
119 if (m_overflow.empty())
120 {
121 m_overflow.push_back(m_top);
122 }
123 m_overflow.push_back(x);
124 m_top = x;
125 }
126 else
127 {
128 size_type bn = block_nr(x);
129 m_stack[bn] ^= (1ULL << block_pos(x));
130 if (m_stack[bn - 1] == 0)
131 {
132 m_stack[bn - 1] = 0x8000000000000000ULL | m_top;
133 }
134 m_top = x;
135 }
136}
137
139{
140 if (!empty())
141 {
142 --m_cnt; //< decrement counter
143 if (m_top > m_n + 63)
144 {
145 m_overflow.pop_back();
146 m_top = m_overflow.back();
147 if (m_overflow.size() == 1)
148 m_overflow.pop_back();
149 }
150 else
151 {
152 size_type bn = block_nr(m_top);
153 uint64_t w = m_stack[bn];
154 assert((w >> 63) == 0); // highest bit is not set, as the block contains no pointer
155 w ^= (1ULL << block_pos(m_top));
156 m_stack[bn] = w;
157 if (w > 0)
158 {
159 m_top = bn * 63 + bits::hi(w);
160 }
161 else
162 { // w==0 and cnt>0
163 assert(bn > 0);
164 w = m_stack[bn - 1];
165 if ((w >> 63) == 0)
166 { // highest bit is not set => the block contains no pointer
167 assert(w > 0);
168 m_top = (bn - 1) * 63 + bits::hi(w);
169 }
170 else
171 { // block contains pointers
172 m_stack[bn - 1] = 0;
173 m_top = w & 0x7FFFFFFFFFFFFFFFULL;
174 }
175 }
176 }
177 }
178}
179
181sorted_int_stack::serialize(std::ostream & out, structure_tree_node * v, std::string name) const
182{
183 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
184 size_type written_bytes = 0;
185 written_bytes += write_member(m_n, out);
186 written_bytes += write_member(m_top, out);
187 written_bytes += write_member(m_cnt, out);
188 written_bytes += m_stack.serialize(out);
189 written_bytes += sdsl::serialize(m_overflow, out, child, "overflow");
190 structure_tree::add_size(child, written_bytes);
191 return written_bytes;
192}
193
194inline void sorted_int_stack::load(std::istream & in)
195{
196 read_member(m_n, in);
197 read_member(m_top, in);
198 read_member(m_cnt, in);
199 m_stack.load(in);
200 sdsl::load(m_overflow, in);
201}
202
203template <typename archive_t>
205{
206 ar(CEREAL_NVP(m_n));
207 ar(CEREAL_NVP(m_cnt));
208 ar(CEREAL_NVP(m_top));
209 ar(CEREAL_NVP(m_stack));
210 ar(CEREAL_NVP(m_overflow));
211}
212
213template <typename archive_t>
215{
216 ar(CEREAL_NVP(m_n));
217 ar(CEREAL_NVP(m_cnt));
218 ar(CEREAL_NVP(m_top));
219 ar(CEREAL_NVP(m_stack));
220 ar(CEREAL_NVP(m_overflow));
221}
222
224inline bool sorted_int_stack::operator==(sorted_int_stack const & other) const noexcept
225{
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);
228}
229
231inline bool sorted_int_stack::operator!=(sorted_int_stack const & other) const noexcept
232{
233 return !(*this == other);
234}
235
236} // end namespace sdsl
237
238#endif // end file
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#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 io.hpp:36
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 & 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="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
Definition io.hpp:160
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="")
Definition io.hpp:139
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
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.