SDSL  3.0.0
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 
12 namespace 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 
151 inline 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 
159 template <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 
168 template <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 
178 inline 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 
184 inline 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: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 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 & operator=(sorted_stack_support &&)=default
sorted_stack_support(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(sorted_stack_support &&)=default
sorted_stack_support & operator=(const 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 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.
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