SDSL  3.0.0
Succinct Data Structure Library
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 
17 namespace sdsl
18 {
19 
21 
34 template <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:30
int_vector_size_type size_type
Definition: int_vector.hpp:266
ptrdiff_t difference_type
Definition: int_vector.hpp:265
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:255
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.
inv_perm_support & operator=(const inv_perm_support &p)
Assignment operation.
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.
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 & operator=(inv_perm_support &&p)
Assignment move operation.
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.
const_iterator begin() const
Returns a const_iterator to the first element.
Generic iterator for a random access container.
Definition: iterators.hpp:24
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.
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:51
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
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