SDSL 3.0.1
Succinct Data Structure Library
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 <sdsl/int_vector.hpp>
11
12namespace sdsl
13{
15
25{
26 public:
28
29 private:
30 size_type m_n; // Size of the supported vector.
31 size_type m_cnt; // Counter for the indices on the stack.
32 size_type m_top; // Topmost index of the stack.
33 int_vector<64> m_stack; // Memory for the stack.
34
35 inline size_type block_nr(size_type x) { return x / 63; }; // TODO: maybe we can speed this up with bit hacks
36 inline size_type block_pos(size_type x) { return x % 63; }; // TODO: maybe we can speed this up with bit hacks
37 public:
39
42
47
50 bool empty() const { return 0 == m_cnt; };
51
55 size_type top() const;
56
59 void pop();
60
65 void push(size_type x);
66
69 size_type size() const { return m_cnt; };
70
71 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
72 void load(std::istream & in);
73 template <typename archive_t>
74 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
75 template <typename archive_t>
76 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
77 bool operator==(sorted_stack_support const & other) const noexcept;
78 bool operator!=(sorted_stack_support const & other) const noexcept;
79};
80
82 : m_n(n)
83 , m_cnt(0)
84 , m_top(0)
85 , m_stack()
86{
87 m_stack = int_vector<64>(block_nr(m_n + 1) + 1, 0);
88 m_stack[0] = 1;
89}
90
92{
93 assert(empty() == false);
94 return m_top - 1;
95}
96
98{
99 assert((empty() or top() < x) and x <= m_n);
100 x += 1;
101 ++m_cnt; //< increment counter
102 size_type bn = block_nr(x);
103 m_stack[bn] ^= (1ULL << block_pos(x));
104 if (bn > 0 and m_stack[bn - 1] == 0) { m_stack[bn - 1] = 0x8000000000000000ULL | m_top; }
105 m_top = x;
106}
107
109{
110 if (!empty())
111 {
112 --m_cnt; //< decrement counter
113 size_type bn = block_nr(m_top);
114 uint64_t w = m_stack[bn];
115 assert((w >> 63) == 0); // highest bit is not set, as the block contains no pointer
116 w ^= (1ULL << block_pos(m_top));
117 m_stack[bn] = w;
118 if (w > 0) { m_top = bn * 63 + bits::hi(w); }
119 else
120 { // w==0 and cnt>0
121 assert(bn > 0);
122 w = m_stack[bn - 1];
123 if ((w >> 63) == 0)
124 { // highest bit is not set => the block contains no pointer
125 assert(w > 0);
126 m_top = (bn - 1) * 63 + bits::hi(w);
127 }
128 else
129 { // block contains pointers
130 m_stack[bn - 1] = 0;
131 m_top = w & 0x7FFFFFFFFFFFFFFFULL;
132 }
133 }
134 }
135}
136
139 std::string name) const
140{
141 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
142 size_type written_bytes = 0;
143 written_bytes += write_member(m_n, out);
144 written_bytes += write_member(m_top, out);
145 written_bytes += write_member(m_cnt, out);
146 written_bytes += m_stack.serialize(out);
147 structure_tree::add_size(child, written_bytes);
148 return written_bytes;
149}
150
151inline void sorted_stack_support::load(std::istream & in)
152{
153 read_member(m_n, in);
154 read_member(m_top, in);
155 read_member(m_cnt, in);
156 m_stack.load(in);
157}
158
159template <typename archive_t>
161{
162 ar(CEREAL_NVP(m_n));
163 ar(CEREAL_NVP(m_cnt));
164 ar(CEREAL_NVP(m_top));
165 ar(CEREAL_NVP(m_stack));
166}
167
168template <typename archive_t>
170{
171 ar(CEREAL_NVP(m_n));
172 ar(CEREAL_NVP(m_cnt));
173 ar(CEREAL_NVP(m_top));
174 ar(CEREAL_NVP(m_stack));
175}
176
178inline bool sorted_stack_support::operator==(sorted_stack_support const & other) const noexcept
179{
180 return (m_n == other.m_n) && (m_cnt == other.m_cnt) && (m_top == other.m_top) && (m_stack == other.m_stack);
181}
182
184inline bool sorted_stack_support::operator!=(sorted_stack_support const & other) const noexcept
185{
186 return !(*this == other);
187}
188
189} // end namespace sdsl
190
191#endif // end file
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
A generic vector class for integers of width .
Definition: int_vector.hpp:216
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 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
sorted_stack_support(const sorted_stack_support &)=default
sorted_stack_support & operator=(const sorted_stack_support &)=default
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
bool empty() const
Returns if the stack is empty.
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, 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.
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
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651