SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sorted_multi_stack_support.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_MULTI_STACK_SUPPORT
10#define INCLUDED_SDSL_SORTED_MULTI_STACK_SUPPORT
11
12#include <assert.h>
13#include <iosfwd>
14#include <stdint.h>
15#include <string>
16
17#include <sdsl/bits.hpp>
18#include <sdsl/cereal.hpp>
19#include <sdsl/int_vector.hpp>
20#include <sdsl/io.hpp>
22#include <sdsl/util.hpp>
23
24namespace sdsl
25{
26
28
32{
33public:
35
36private:
37 size_type m_n; // Size of the supported vector.
38 size_type m_cnt; // Counter for the indices on the stack.
39 size_type m_top; // Topmost index of the stack.
40 int_vector<64> m_stack; // Memory for the stack.
41 int_vector<64> m_duplication_stack; // Memory for the duplications
42
43 inline size_type block_nr(size_type x)
44 {
45 return x / 63;
46 }; // maybe we can speed this up with bit hacks
47 inline size_type block_pos(size_type x)
48 {
49 return x % 63;
50 }; // maybe we can speed this up with bit hacks
51
52public:
54
61
64 bool empty() const
65 {
66 return 0 == m_cnt;
67 };
68
72 size_type top() const;
73
78 bool pop();
79
85 bool push(size_type x);
86
90 {
91 return m_cnt;
92 };
93
94 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
95 void load(std::istream & in);
96 template <typename archive_t>
97 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
98 template <typename archive_t>
99 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
100};
101
103 m_n(n),
104 m_cnt(0),
105 m_top(0),
106 m_stack(),
107 m_duplication_stack()
108{
109 m_stack = int_vector<64>(block_nr(m_n + 1) + 1, 0);
110 m_stack[0] = 1;
111 m_duplication_stack = int_vector<64>((m_n >> 6) + 1, 0);
112}
113
115{
116 return m_top - 1;
117}
118
120{
121 x += 1;
122 size_type bn = block_nr(x);
123 if (0 == ((m_stack[bn] >> block_pos(x)) & 1))
124 { // check if x is not already on the stack
125 m_stack[bn] ^= (1ULL << block_pos(x));
126 if (bn > 0 and m_stack[bn - 1] == 0)
127 {
128 m_stack[bn - 1] = 0x8000000000000000ULL | m_top;
129 }
130 m_top = x;
131 // write a 0 to the duplication stack
132 // do nothing as stack is initialized with zeros
133 ++m_cnt; //< increment counter
134 return true;
135 }
136 else
137 { // if the element is already on the stack
138 // write a 1 to the duplication stack
139 m_duplication_stack[m_cnt >> 6] ^= (1ULL << (m_cnt & 0x3F));
140 ++m_cnt; //< increment counter
141 return false;
142 }
143}
144
146{
147 if (m_cnt)
148 {
149 --m_cnt; //< decrement counter
150 if ((m_duplication_stack[m_cnt >> 6] >> (m_cnt & 0x3F)) & 1)
151 { // if it's a duplication
152 m_duplication_stack[m_cnt >> 6] ^= (1ULL << (m_cnt & 0x3F)); // delete 1
153 return false;
154 }
155 else
156 {
157 size_type bn = block_nr(m_top);
158 uint64_t w = m_stack[bn];
159 assert((w >> 63) == 0); // highest bit is not set, as the block contains no pointer
160 w ^= (1ULL << block_pos(m_top));
161 m_stack[bn] = w;
162 if (w > 0)
163 {
164 m_top = bn * 63 + bits::hi(w);
165 }
166 else
167 { // w==0 and cnt>0
168 assert(bn > 0);
169 w = m_stack[bn - 1];
170 if ((w >> 63) == 0)
171 { // highest bit is not set => the block contains no pointer
172 assert(w > 0);
173 m_top = (bn - 1) * 63 + bits::hi(w);
174 }
175 else
176 { // block contains pointers
177 m_stack[bn - 1] = 0;
178 m_top = w & 0x7FFFFFFFFFFFFFFFULL;
179 }
180 }
181 return true;
182 }
183 }
184 return false;
185}
186
188sorted_multi_stack_support::serialize(std::ostream & out, structure_tree_node * v, std::string name) const
189{
190 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
191 size_type written_bytes = 0;
192 written_bytes += write_member(m_n, out);
193 written_bytes += write_member(m_top, out);
194 written_bytes += write_member(m_cnt, out);
195 written_bytes += m_stack.serialize(out);
196 written_bytes += m_duplication_stack.serialize(out);
197 structure_tree::add_size(child, written_bytes);
198 return written_bytes;
199}
200
201inline void sorted_multi_stack_support::load(std::istream & in)
202{
203 read_member(m_n, in);
204 read_member(m_top, in);
205 read_member(m_cnt, in);
206 m_stack.load(in);
207 m_duplication_stack.load(in);
208}
209
210template <typename archive_t>
212{
213 ar(CEREAL_NVP(m_n));
214 ar(CEREAL_NVP(m_cnt));
215 ar(CEREAL_NVP(m_top));
216 ar(CEREAL_NVP(m_stack));
217 ar(CEREAL_NVP(m_duplication_stack));
218}
219
220template <typename archive_t>
222{
223 ar(CEREAL_NVP(m_n));
224 ar(CEREAL_NVP(m_cnt));
225 ar(CEREAL_NVP(m_top));
226 ar(CEREAL_NVP(m_stack));
227 ar(CEREAL_NVP(m_duplication_stack));
228}
229
230} // end namespace sdsl
231
232#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.
Stack which contains elements from [0..n] in sorted order. Duplicates are possible.
size_type size() const
Returns the number of element is the stack.
sorted_multi_stack_support(sorted_multi_stack_support &&)=default
sorted_multi_stack_support(sorted_multi_stack_support const &)=default
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
sorted_multi_stack_support & operator=(sorted_multi_stack_support const &)=default
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bool empty() const
Returns if the stack is empty.
size_type top() const
Returns the topmost index on the stack.
sorted_multi_stack_support & operator=(sorted_multi_stack_support &&)=default
bool pop()
Pop the topmost index of the stack.
bool push(size_type x)
Push the index x of vector vec onto 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
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.