SDSL  3.0.0
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 
14 namespace 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 
173 inline 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 
182 template <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 
192 template <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: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.
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.
sorted_multi_stack_support & operator=(const sorted_multi_stack_support &)=default
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 & operator=(sorted_multi_stack_support &&)=default
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.
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 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