SDSL 3.0.1
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 <sdsl/bit_vectors.hpp>
13#include <sdsl/int_vector.hpp>
14#include <sdsl/iterators.hpp>
15#include <sdsl/rank_support.hpp>
16
17namespace sdsl
18{
19
21
34template <uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
36{
37 public:
43 typedef t_bv bit_vector_type;
44 typedef t_rank rank_type;
45
46 private:
47 const iv_type * m_v = nullptr; // pointer to supported permutation
48 iv_type m_back_pointer; // back pointers
49 bit_vector_type m_marked; // back pointer marking
50 rank_type m_rank_marked; // rank support for back pointer marking
51 public:
53
55 : m_v(p.m_v)
56 , m_back_pointer(p.m_back_pointer)
57 , m_marked(p.m_marked)
58 , m_rank_marked(p.m_rank_marked)
59 {
60 m_rank_marked.set_vector(&m_marked);
61 }
62
63 inv_perm_support(inv_perm_support && p) { *this = std::move(p); }
64
67 : m_v(v)
68 {
69 bit_vector marked = bit_vector(m_v->size(), 0);
70 bit_vector done = bit_vector(m_v->size(), 0);
71
72 size_type max_back_pointer = 0;
73 for (size_type i = 0; i < m_v->size(); ++i)
74 {
75 if (!done[i])
76 {
77 done[i] = 1;
78 size_type back_pointer = i, j = i, j_new = 0;
79 uint64_t steps = 0, all_steps = 0;
80 while ((j_new = (*m_v)[j]) != i)
81 {
82 j = j_new;
83 done[j] = 1;
84 ++steps;
85 ++all_steps;
86 if (t_s == steps)
87 {
88 max_back_pointer = std::max(max_back_pointer, back_pointer);
89 marked[j] = 1;
90 steps = 0;
91 back_pointer = j;
92 }
93 }
94 if (all_steps > t_s)
95 {
96 marked[i] = 1;
97 max_back_pointer = std::max(max_back_pointer, back_pointer);
98 }
99 }
100 }
101
102 m_marked = t_bv(std::move(marked));
103 util::init_support(m_rank_marked, &m_marked);
104
105 done = bit_vector(m_v->size(), 0);
106 size_type n_bp = m_rank_marked(m_v->size());
107 m_back_pointer = int_vector<>(n_bp, 0, bits::hi(max_back_pointer) + 1);
108
109 for (size_type i = 0; i < m_v->size(); ++i)
110 {
111 if (!done[i])
112 {
113 done[i] = 1;
114 size_type back_pointer = i, j = i, j_new = 0;
115 uint64_t steps = 0, all_steps = 0;
116 while ((j_new = (*m_v)[j]) != i)
117 {
118 j = j_new;
119 done[j] = 1;
120 ++steps;
121 ++all_steps;
122 if (t_s == steps)
123 {
124 m_back_pointer[m_rank_marked(j)] = back_pointer;
125 steps = 0;
126 back_pointer = j;
127 }
128 }
129 if (all_steps > t_s) { m_back_pointer[m_rank_marked(i)] = back_pointer; }
130 }
131 }
132 }
133
136 {
137 size_type j = i, j_new = 0;
138 while ((j_new = (*m_v)[j]) != i)
139 {
140 if (m_marked[j])
141 {
142 j = m_back_pointer[m_rank_marked(j)];
143 while ((j_new = (*m_v)[j]) != i) j = j_new;
144 }
145 else
146 {
147 j = j_new;
148 }
149 }
150 return j;
151 }
152
153 size_type size() const { return nullptr == m_v ? 0 : m_v->size(); }
154
156 const_iterator begin() const { return const_iterator(this, 0); }
157
159 const_iterator end() const { return const_iterator(this, size()); }
160
161 void set_vector(const iv_type * v) { m_v = v; }
162
165 {
166 if (this != &p)
167 {
168 inv_perm_support tmp(p);
169 *this = std::move(tmp);
170 }
171 return *this;
172 }
173
176 {
177 if (this != &p)
178 {
179 m_v = std::move(p.m_v);
180 m_back_pointer = std::move(p.m_back_pointer);
181 m_marked = std::move(p.m_marked);
182 m_rank_marked = std::move(p.m_rank_marked);
183 m_rank_marked.set_vector(&m_marked);
184 }
185 return *this;
186 }
187
189 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
190 {
191 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
192 size_type written_bytes = 0;
193 written_bytes += m_back_pointer.serialize(out, child, "back_pointer");
194 written_bytes += m_marked.serialize(out, child, "marked");
195 written_bytes += m_rank_marked.serialize(out, child, "rank_marked");
196 structure_tree::add_size(child, written_bytes);
197 return written_bytes;
198 }
199
201 void load(std::istream & in)
202 {
203 m_back_pointer.load(in);
204 m_marked.load(in);
205 m_rank_marked.load(in, &m_marked);
206 }
207
209 template <typename archive_t>
210 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
211 {
212 ar(CEREAL_NVP(m_back_pointer));
213 ar(CEREAL_NVP(m_marked));
214 ar(CEREAL_NVP(m_rank_marked));
215 }
216
218 template <typename archive_t>
219 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
220 {
221 ar(CEREAL_NVP(m_back_pointer));
222 ar(CEREAL_NVP(m_marked));
223 ar(CEREAL_NVP(m_rank_marked));
224 m_rank_marked.set_vector(&m_marked);
225 }
226
228 bool operator==(inv_perm_support const & other) const noexcept
229 {
230 return (m_back_pointer == other.m_back_pointer) && (m_marked == other.m_marked) &&
231 (m_rank_marked == other.m_rank_marked);
232 }
233
235 bool operator!=(inv_perm_support const & other) const noexcept { return !(*this == other); }
236};
237
238} // end namespace sdsl
239
240#endif
bit_vectors.hpp contains classes for uncompressed and compressed bit vector representations.
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
int_vector_size_type size_type
Definition: int_vector.hpp:229
ptrdiff_t difference_type
Definition: int_vector.hpp:228
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
int_vector_trait< t_width >::value_type value_type
Definition: int_vector.hpp:221
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
Class inv_perm_support adds access to the inverse of a permutation.
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(const inv_perm_support &p)
inv_perm_support(inv_perm_support &&p)
void load(std::istream &in)
Load sampling from disk.
iv_type::difference_type difference_type
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.
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.
inv_perm_support(const iv_type *v)
Constructor.
void set_vector(const iv_type *v)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
inv_perm_support & operator=(const inv_perm_support &p)
Assignment operation.
const_iterator begin() const
Returns a const_iterator to the first element.
Generic iterator for a random access container.
Definition: iterators.hpp:24
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.
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.
Definition: int_vector.hpp:53
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651