SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sorted_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.
7#ifndef INCLUDED_SDSL_SORTED_STACK_SUPPORT
8#define INCLUDED_SDSL_SORTED_STACK_SUPPORT
9
10#include <assert.h>
11#include <iosfwd>
12#include <stdint.h>
13#include <string>
14
15#include <sdsl/bits.hpp>
16#include <sdsl/cereal.hpp>
17#include <sdsl/int_vector.hpp>
18#include <sdsl/io.hpp>
20#include <sdsl/util.hpp>
21
22namespace sdsl
23{
25
35{
36public:
38
39private:
40 size_type m_n; // Size of the supported vector.
41 size_type m_cnt; // Counter for the indices on the stack.
42 size_type m_top; // Topmost index of the stack.
43 int_vector<64> m_stack; // Memory for the stack.
44
45 inline size_type block_nr(size_type x)
46 {
47 return x / 63;
48 }; // TODO: maybe we can speed this up with bit hacks
49 inline size_type block_pos(size_type x)
50 {
51 return x % 63;
52 }; // TODO: maybe we can speed this up with bit hacks
53
54public:
56
59
64
67 bool empty() const
68 {
69 return 0 == m_cnt;
70 };
71
75 size_type top() const;
76
79 void pop();
80
85 void 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 bool operator==(sorted_stack_support const & other) const noexcept;
101 bool operator!=(sorted_stack_support const & other) const noexcept;
102};
103
104inline sorted_stack_support::sorted_stack_support(size_type n) : m_n(n), m_cnt(0), m_top(0), m_stack()
105{
106 m_stack = int_vector<64>(block_nr(m_n + 1) + 1, 0);
107 m_stack[0] = 1;
108}
109
111{
112 assert(empty() == false);
113 return m_top - 1;
114}
115
117{
118 assert((empty() or top() < x) and x <= m_n);
119 x += 1;
120 ++m_cnt; //< increment counter
121 size_type bn = block_nr(x);
122 m_stack[bn] ^= (1ULL << block_pos(x));
123 if (bn > 0 and m_stack[bn - 1] == 0)
124 {
125 m_stack[bn - 1] = 0x8000000000000000ULL | m_top;
126 }
127 m_top = x;
128}
129
131{
132 if (!empty())
133 {
134 --m_cnt; //< decrement counter
135 size_type bn = block_nr(m_top);
136 uint64_t w = m_stack[bn];
137 assert((w >> 63) == 0); // highest bit is not set, as the block contains no pointer
138 w ^= (1ULL << block_pos(m_top));
139 m_stack[bn] = w;
140 if (w > 0)
141 {
142 m_top = bn * 63 + bits::hi(w);
143 }
144 else
145 { // w==0 and cnt>0
146 assert(bn > 0);
147 w = m_stack[bn - 1];
148 if ((w >> 63) == 0)
149 { // highest bit is not set => the block contains no pointer
150 assert(w > 0);
151 m_top = (bn - 1) * 63 + bits::hi(w);
152 }
153 else
154 { // block contains pointers
155 m_stack[bn - 1] = 0;
156 m_top = w & 0x7FFFFFFFFFFFFFFFULL;
157 }
158 }
159 }
160}
161
163sorted_stack_support::serialize(std::ostream & out, structure_tree_node * v, std::string name) const
164{
165 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
166 size_type written_bytes = 0;
167 written_bytes += write_member(m_n, out);
168 written_bytes += write_member(m_top, out);
169 written_bytes += write_member(m_cnt, out);
170 written_bytes += m_stack.serialize(out);
171 structure_tree::add_size(child, written_bytes);
172 return written_bytes;
173}
174
175inline void sorted_stack_support::load(std::istream & in)
176{
177 read_member(m_n, in);
178 read_member(m_top, in);
179 read_member(m_cnt, in);
180 m_stack.load(in);
181}
182
183template <typename archive_t>
185{
186 ar(CEREAL_NVP(m_n));
187 ar(CEREAL_NVP(m_cnt));
188 ar(CEREAL_NVP(m_top));
189 ar(CEREAL_NVP(m_stack));
190}
191
192template <typename archive_t>
194{
195 ar(CEREAL_NVP(m_n));
196 ar(CEREAL_NVP(m_cnt));
197 ar(CEREAL_NVP(m_top));
198 ar(CEREAL_NVP(m_stack));
199}
200
202inline bool sorted_stack_support::operator==(sorted_stack_support const & other) const noexcept
203{
204 return (m_n == other.m_n) && (m_cnt == other.m_cnt) && (m_top == other.m_top) && (m_stack == other.m_stack);
205}
206
208inline bool sorted_stack_support::operator!=(sorted_stack_support const & other) const noexcept
209{
210 return !(*this == other);
211}
212
213} // end namespace sdsl
214
215#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 .
int_vector_size_type size_type
A stack which contains strictly increasing numbers in the range from to .
size_type top() const
Returns the topmost index on the stack.
int_vector< 64 >::size_type size_type
bool operator==(sorted_stack_support const &other) const noexcept
Equality operator.
void pop()
Pop the topmost index of the stack.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
sorted_stack_support & operator=(sorted_stack_support const &)=default
bool empty() const
Returns if the stack is empty.
sorted_stack_support(sorted_stack_support const &)=default
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
sorted_stack_support & operator=(sorted_stack_support &&)=default
sorted_stack_support(sorted_stack_support &&)=default
bool operator!=(sorted_stack_support const &other) const noexcept
Inequality operator.
sorted_stack_support(size_type n)
Constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
void push(size_type x)
Push the index x of vector vec onto the stack.
size_type size() const
Returns the number of element is 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.