SDSL  3.0.0
Succinct Data Structure Library
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 <vector>
13 
14 #include <sdsl/int_vector.hpp>
15 
17 namespace sdsl
18 {
19 
21 
25 {
26  public:
28 
29  private:
30  size_type m_n; // maximal value which can be stored on the stack
31  size_type m_cnt; // counter for elements on the stack
32  size_type m_top; // top element of the stack
33  int_vector<64> m_stack; // memory for the stack
34  std::vector<size_type> m_overflow; // memory for the elements which are greater than n
35 
36  inline size_type block_nr(size_type x) { return x / 63; }; // maybe we can speed this up with bit hacks
37  inline size_type block_pos(size_type x) { return x % 63; }; // maybe we can speed this up with bit hacks
38  public:
40  sorted_int_stack(const sorted_int_stack &) = default;
44 
47  bool empty() const { return 0 == m_cnt; };
48 
52  size_type top() const;
53 
56  void pop();
57 
62  void push(size_type x);
63 
66  size_type size() const { return m_cnt; };
67 
68  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
69  void load(std::istream & in);
70  template <typename archive_t>
71  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
72  template <typename archive_t>
73  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
74  bool operator==(sorted_int_stack const & other) const noexcept;
75  bool operator!=(sorted_int_stack const & other) const noexcept;
76 };
77 
79  : m_n(n)
80  , m_cnt(0)
81  , m_top(0)
82 {
83  m_stack = int_vector<64>(block_nr(n) + 2, 0);
84  m_stack[0] = 1;
85 }
86 
88 {
89  return m_top - 63;
90 }
91 
93 {
94  x += 63;
95  assert(empty() || m_top < x);
96  ++m_cnt; //< increment counter
97  if (x > m_n + 63)
98  {
99  if (m_overflow.empty()) { m_overflow.push_back(m_top); }
100  m_overflow.push_back(x);
101  m_top = x;
102  }
103  else
104  {
105  size_type bn = block_nr(x);
106  m_stack[bn] ^= (1ULL << block_pos(x));
107  if (m_stack[bn - 1] == 0) { m_stack[bn - 1] = 0x8000000000000000ULL | m_top; }
108  m_top = x;
109  }
110 }
111 
113 {
114  if (!empty())
115  {
116  --m_cnt; //< decrement counter
117  if (m_top > m_n + 63)
118  {
119  m_overflow.pop_back();
120  m_top = m_overflow.back();
121  if (m_overflow.size() == 1) m_overflow.pop_back();
122  }
123  else
124  {
125  size_type bn = block_nr(m_top);
126  uint64_t w = m_stack[bn];
127  assert((w >> 63) == 0); // highest bit is not set, as the block contains no pointer
128  w ^= (1ULL << block_pos(m_top));
129  m_stack[bn] = w;
130  if (w > 0) { m_top = bn * 63 + bits::hi(w); }
131  else
132  { // w==0 and cnt>0
133  assert(bn > 0);
134  w = m_stack[bn - 1];
135  if ((w >> 63) == 0)
136  { // highest bit is not set => the block contains no pointer
137  assert(w > 0);
138  m_top = (bn - 1) * 63 + bits::hi(w);
139  }
140  else
141  { // block contains pointers
142  m_stack[bn - 1] = 0;
143  m_top = w & 0x7FFFFFFFFFFFFFFFULL;
144  }
145  }
146  }
147  }
148 }
149 
152  std::string name) const
153 {
154  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
155  size_type written_bytes = 0;
156  written_bytes += write_member(m_n, out);
157  written_bytes += write_member(m_top, out);
158  written_bytes += write_member(m_cnt, out);
159  written_bytes += m_stack.serialize(out);
160  written_bytes += sdsl::serialize(m_overflow, out, child, "overflow");
161  structure_tree::add_size(child, written_bytes);
162  return written_bytes;
163 }
164 
165 inline void sorted_int_stack::load(std::istream & in)
166 {
167  read_member(m_n, in);
168  read_member(m_top, in);
169  read_member(m_cnt, in);
170  m_stack.load(in);
171  sdsl::load(m_overflow, in);
172 }
173 
174 template <typename archive_t>
176 {
177  ar(CEREAL_NVP(m_n));
178  ar(CEREAL_NVP(m_cnt));
179  ar(CEREAL_NVP(m_top));
180  ar(CEREAL_NVP(m_stack));
181  ar(CEREAL_NVP(m_overflow));
182 }
183 
184 template <typename archive_t>
186 {
187  ar(CEREAL_NVP(m_n));
188  ar(CEREAL_NVP(m_cnt));
189  ar(CEREAL_NVP(m_top));
190  ar(CEREAL_NVP(m_stack));
191  ar(CEREAL_NVP(m_overflow));
192 }
193 
195 inline bool sorted_int_stack::operator==(sorted_int_stack const & other) const noexcept
196 {
197  return (m_n == other.m_n) && (m_cnt == other.m_cnt) && (m_top == other.m_top) && (m_stack == other.m_stack) &&
198  (m_overflow == other.m_overflow);
199 }
200 
202 inline bool sorted_int_stack::operator!=(sorted_int_stack const & other) const noexcept
203 {
204  return !(*this == other);
205 }
206 
207 } // end namespace sdsl
208 
209 #endif // end file
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
A generic vector class for integers of width .
Definition: int_vector.hpp:253
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.
sorted_int_stack & operator=(const sorted_int_stack &)=default
int_vector< 64 >::size_type size_type
sorted_int_stack & operator=(sorted_int_stack &&)=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.
sorted_int_stack(const sorted_int_stack &)=default
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.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
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 void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
std::enable_if< has_serialize< X >::value, typename X::size_type >::type serialize(const X &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:131
std::enable_if< has_load< X >::value, void >::type load(X &x, std::istream &in)
Definition: io.hpp:154
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 SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661