SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
inv_perm_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_INV_PERM_SUPPORT
10#define INCLUDED_SDSL_INV_PERM_SUPPORT
11
12#include <algorithm>
13#include <iosfwd>
14#include <stdint.h>
15#include <string>
16#include <utility>
17
18#include <sdsl/bits.hpp>
19#include <sdsl/cereal.hpp>
20#include <sdsl/int_vector.hpp>
21#include <sdsl/iterators.hpp>
23#include <sdsl/util.hpp>
24
25namespace sdsl
26{
27
29
42template <uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
44{
45public:
51 typedef t_bv bit_vector_type;
52 typedef t_rank rank_type;
53
54private:
55 iv_type const * m_v = nullptr; // pointer to supported permutation
56 iv_type m_back_pointer; // back pointers
57 bit_vector_type m_marked; // back pointer marking
58 rank_type m_rank_marked; // rank support for back pointer marking
59
60public:
62
64 m_v(p.m_v),
65 m_back_pointer(p.m_back_pointer),
66 m_marked(p.m_marked),
67 m_rank_marked(p.m_rank_marked)
68 {
69 m_rank_marked.set_vector(&m_marked);
70 }
71
73 {
74 *this = std::move(p);
75 }
76
78 inv_perm_support(iv_type const * v) : m_v(v)
79 {
80 bit_vector marked = bit_vector(m_v->size(), 0);
81 bit_vector done = bit_vector(m_v->size(), 0);
82
83 size_type max_back_pointer = 0;
84 for (size_type i = 0; i < m_v->size(); ++i)
85 {
86 if (!done[i])
87 {
88 done[i] = 1;
89 size_type back_pointer = i, j = i, j_new = 0;
90 uint64_t steps = 0, all_steps = 0;
91 while ((j_new = (*m_v)[j]) != i)
92 {
93 j = j_new;
94 done[j] = 1;
95 ++steps;
96 ++all_steps;
97 if (t_s == steps)
98 {
99 max_back_pointer = std::max(max_back_pointer, back_pointer);
100 marked[j] = 1;
101 steps = 0;
102 back_pointer = j;
103 }
104 }
105 if (all_steps > t_s)
106 {
107 marked[i] = 1;
108 max_back_pointer = std::max(max_back_pointer, back_pointer);
109 }
110 }
111 }
112
113 m_marked = t_bv(std::move(marked));
114 util::init_support(m_rank_marked, &m_marked);
115
116 done = bit_vector(m_v->size(), 0);
117 size_type n_bp = m_rank_marked(m_v->size());
118 m_back_pointer = int_vector<>(n_bp, 0, bits::hi(max_back_pointer) + 1);
119
120 for (size_type i = 0; i < m_v->size(); ++i)
121 {
122 if (!done[i])
123 {
124 done[i] = 1;
125 size_type back_pointer = i, j = i, j_new = 0;
126 uint64_t steps = 0, all_steps = 0;
127 while ((j_new = (*m_v)[j]) != i)
128 {
129 j = j_new;
130 done[j] = 1;
131 ++steps;
132 ++all_steps;
133 if (t_s == steps)
134 {
135 m_back_pointer[m_rank_marked(j)] = back_pointer;
136 steps = 0;
137 back_pointer = j;
138 }
139 }
140 if (all_steps > t_s)
141 {
142 m_back_pointer[m_rank_marked(i)] = back_pointer;
143 }
144 }
145 }
146 }
147
150 {
151 size_type j = i, j_new = 0;
152 while ((j_new = (*m_v)[j]) != i)
153 {
154 if (m_marked[j])
155 {
156 j = m_back_pointer[m_rank_marked(j)];
157 while ((j_new = (*m_v)[j]) != i)
158 j = j_new;
159 }
160 else
161 {
162 j = j_new;
163 }
164 }
165 return j;
166 }
167
169 {
170 return nullptr == m_v ? 0 : m_v->size();
171 }
172
175 {
176 return const_iterator(this, 0);
177 }
178
181 {
182 return const_iterator(this, size());
183 }
184
185 void set_vector(iv_type const * v)
186 {
187 m_v = v;
188 }
189
192 {
193 if (this != &p)
194 {
195 inv_perm_support tmp(p);
196 *this = std::move(tmp);
197 }
198 return *this;
199 }
200
203 {
204 if (this != &p)
205 {
206 m_v = std::move(p.m_v);
207 m_back_pointer = std::move(p.m_back_pointer);
208 m_marked = std::move(p.m_marked);
209 m_rank_marked = std::move(p.m_rank_marked);
210 m_rank_marked.set_vector(&m_marked);
211 }
212 return *this;
213 }
214
216 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
217 {
218 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
219 size_type written_bytes = 0;
220 written_bytes += m_back_pointer.serialize(out, child, "back_pointer");
221 written_bytes += m_marked.serialize(out, child, "marked");
222 written_bytes += m_rank_marked.serialize(out, child, "rank_marked");
223 structure_tree::add_size(child, written_bytes);
224 return written_bytes;
225 }
226
228 void load(std::istream & in)
229 {
230 m_back_pointer.load(in);
231 m_marked.load(in);
232 m_rank_marked.load(in, &m_marked);
233 }
234
236 template <typename archive_t>
237 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
238 {
239 ar(CEREAL_NVP(m_back_pointer));
240 ar(CEREAL_NVP(m_marked));
241 ar(CEREAL_NVP(m_rank_marked));
242 }
243
245 template <typename archive_t>
246 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
247 {
248 ar(CEREAL_NVP(m_back_pointer));
249 ar(CEREAL_NVP(m_marked));
250 ar(CEREAL_NVP(m_rank_marked));
251 m_rank_marked.set_vector(&m_marked);
252 }
253
255 bool operator==(inv_perm_support const & other) const noexcept
256 {
257 return (m_back_pointer == other.m_back_pointer) && (m_marked == other.m_marked)
258 && (m_rank_marked == other.m_rank_marked);
259 }
260
262 bool operator!=(inv_perm_support const & other) const noexcept
263 {
264 return !(*this == other);
265 }
266};
267
268} // end namespace sdsl
269
270#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
int_vector_size_type size_type
ptrdiff_t difference_type
int_vector_trait< t_width >::value_type value_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize into stream.
random_access_const_iterator< inv_perm_support > const_iterator
inv_perm_support(iv_type const *v)
Constructor.
inv_perm_support(inv_perm_support &&p)
void load(std::istream &in)
Load sampling from disk.
iv_type::difference_type difference_type
void set_vector(iv_type const *v)
bool operator==(inv_perm_support const &other) const noexcept
Equality operator.
iv_type::value_type value_type
const_iterator end() const
Returns a const_iterator to the element after the last element.
inv_perm_support(inv_perm_support const &p)
value_type operator[](size_type i) const
Access operator.
inv_perm_support & operator=(inv_perm_support &&p)
Assignment move operation.
iv_type::size_type size_type
bool operator!=(inv_perm_support const &other) const noexcept
Inequality operator.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
const_iterator begin() const
Returns a const_iterator to the first element.
inv_perm_support & operator=(inv_perm_support const &p)
Assignment operation.
Generic iterator for a random access container.
Definition iterators.hpp:24
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.