9 #ifndef INCLUDED_SDSL_INV_PERM_SUPPORT
10 #define INCLUDED_SDSL_INV_PERM_SUPPORT
34 template <u
int64_t t_s = 32,
class t_bv = bit_vector,
class t_rank =
typename bit_vector::rank_1_type>
56 , m_back_pointer(p.m_back_pointer)
57 , m_marked(p.m_marked)
58 , m_rank_marked(p.m_rank_marked)
60 m_rank_marked.set_vector(&m_marked);
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)
88 max_back_pointer = std::max(max_back_pointer, back_pointer);
97 max_back_pointer = std::max(max_back_pointer, back_pointer);
102 m_marked = t_bv(std::move(marked));
103 util::init_support(m_rank_marked, &m_marked);
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)
124 m_back_pointer[m_rank_marked(j)] = back_pointer;
129 if (all_steps > t_s) { m_back_pointer[m_rank_marked(i)] = back_pointer; }
138 while ((j_new = (*m_v)[j]) != i)
142 j = m_back_pointer[m_rank_marked(j)];
143 while ((j_new = (*m_v)[j]) != i) j = j_new;
169 *
this = std::move(tmp);
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);
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");
197 return written_bytes;
203 m_back_pointer.
load(in);
205 m_rank_marked.load(in, &m_marked);
209 template <
typename archive_t>
218 template <
typename archive_t>
224 m_rank_marked.set_vector(&m_marked);
230 return (m_back_pointer == other.m_back_pointer) && (m_marked == other.m_marked) &&
231 (m_rank_marked == other.m_rank_marked);
bit_vectors.hpp contains classes for uncompressed and compressed bit vector representations.
int_vector_size_type size_type
ptrdiff_t difference_type
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
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.
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.
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.