SDSL 3.0.1
Succinct Data Structure Library
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 <sdsl/int_vector.hpp>
13
14namespace sdsl
15{
16
18
22{
23 public:
25
26 private:
27 size_type m_n; // Size of the supported vector.
28 size_type m_cnt; // Counter for the indices on the stack.
29 size_type m_top; // Topmost index of the stack.
30 int_vector<64> m_stack; // Memory for the stack.
31 int_vector<64> m_duplication_stack; // Memory for the duplications
32
33 inline size_type block_nr(size_type x) { return x / 63; }; // maybe we can speed this up with bit hacks
34 inline size_type block_pos(size_type x) { return x % 63; }; // maybe we can speed this up with bit hacks
35 public:
37
44
47 bool empty() const { return 0 == m_cnt; };
48
52 size_type top() const;
53
58 bool pop();
59
65 bool 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};
78
80 : m_n(n)
81 , m_cnt(0)
82 , m_top(0)
83 , m_stack()
84 , m_duplication_stack()
85{
86 m_stack = int_vector<64>(block_nr(m_n + 1) + 1, 0);
87 m_stack[0] = 1;
88 m_duplication_stack = int_vector<64>((m_n >> 6) + 1, 0);
89}
90
92{
93 return m_top - 1;
94}
95
97{
98 x += 1;
99 size_type bn = block_nr(x);
100 if (0 == ((m_stack[bn] >> block_pos(x)) & 1))
101 { // check if x is not already on the stack
102 m_stack[bn] ^= (1ULL << block_pos(x));
103 if (bn > 0 and m_stack[bn - 1] == 0) { m_stack[bn - 1] = 0x8000000000000000ULL | m_top; }
104 m_top = x;
105 // write a 0 to the duplication stack
106 // do nothing as stack is initialized with zeros
107 ++m_cnt; //< increment counter
108 return true;
109 }
110 else
111 { // if the element is already on the stack
112 // write a 1 to the duplication stack
113 m_duplication_stack[m_cnt >> 6] ^= (1ULL << (m_cnt & 0x3F));
114 ++m_cnt; //< increment counter
115 return false;
116 }
117}
118
120{
121 if (m_cnt)
122 {
123 --m_cnt; //< decrement counter
124 if ((m_duplication_stack[m_cnt >> 6] >> (m_cnt & 0x3F)) & 1)
125 { // if it's a duplication
126 m_duplication_stack[m_cnt >> 6] ^= (1ULL << (m_cnt & 0x3F)); // delete 1
127 return false;
128 }
129 else
130 {
131 size_type bn = block_nr(m_top);
132 uint64_t w = m_stack[bn];
133 assert((w >> 63) == 0); // highest bit is not set, as the block contains no pointer
134 w ^= (1ULL << block_pos(m_top));
135 m_stack[bn] = w;
136 if (w > 0) { m_top = bn * 63 + bits::hi(w); }
137 else
138 { // w==0 and cnt>0
139 assert(bn > 0);
140 w = m_stack[bn - 1];
141 if ((w >> 63) == 0)
142 { // highest bit is not set => the block contains no pointer
143 assert(w > 0);
144 m_top = (bn - 1) * 63 + bits::hi(w);
145 }
146 else
147 { // block contains pointers
148 m_stack[bn - 1] = 0;
149 m_top = w & 0x7FFFFFFFFFFFFFFFULL;
150 }
151 }
152 return true;
153 }
154 }
155 return false;
156}
157
160 std::string name) const
161{
162 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
163 size_type written_bytes = 0;
164 written_bytes += write_member(m_n, out);
165 written_bytes += write_member(m_top, out);
166 written_bytes += write_member(m_cnt, out);
167 written_bytes += m_stack.serialize(out);
168 written_bytes += m_duplication_stack.serialize(out);
169 structure_tree::add_size(child, written_bytes);
170 return written_bytes;
171}
172
173inline void sorted_multi_stack_support::load(std::istream & in)
174{
175 read_member(m_n, in);
176 read_member(m_top, in);
177 read_member(m_cnt, in);
178 m_stack.load(in);
179 m_duplication_stack.load(in);
180}
181
182template <typename archive_t>
184{
185 ar(CEREAL_NVP(m_n));
186 ar(CEREAL_NVP(m_cnt));
187 ar(CEREAL_NVP(m_top));
188 ar(CEREAL_NVP(m_stack));
189 ar(CEREAL_NVP(m_duplication_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 ar(CEREAL_NVP(m_duplication_stack));
200}
201
202} // end namespace sdsl
203
204#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.
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(size_type n)
Constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
sorted_multi_stack_support(const sorted_multi_stack_support &)=default
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=(const sorted_multi_stack_support &)=default
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, 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