SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::inv_perm_support< t_s, t_bv, t_rank > Class Template Reference

Class inv_perm_support adds access to the inverse of a permutation. More...

#include <inv_perm_support.hpp>

Public Types

typedef int_vector iv_type
 
typedef iv_type::size_type size_type
 
typedef iv_type::value_type value_type
 
typedef iv_type::difference_type difference_type
 
typedef random_access_const_iterator< inv_perm_supportconst_iterator
 
typedef t_bv bit_vector_type
 
typedef t_rank rank_type
 

Public Member Functions

 inv_perm_support ()
 
 inv_perm_support (const inv_perm_support &p)
 
 inv_perm_support (inv_perm_support &&p)
 
 inv_perm_support (const iv_type *v)
 Constructor. More...
 
value_type operator[] (size_type i) const
 Access operator. More...
 
size_type size () const
 
const_iterator begin () const
 Returns a const_iterator to the first element. More...
 
const_iterator end () const
 Returns a const_iterator to the element after the last element. More...
 
void set_vector (const iv_type *v)
 
inv_perm_supportoperator= (const inv_perm_support &p)
 Assignment operation. More...
 
inv_perm_supportoperator= (inv_perm_support &&p)
 Assignment move operation. More...
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serialize into stream. More...
 
void load (std::istream &in)
 Load sampling from disk. More...
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal. More...
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 Load via cereal. More...
 
bool operator== (inv_perm_support const &other) const noexcept
 Equality operator. More...
 
bool operator!= (inv_perm_support const &other) const noexcept
 Inequality operator. More...
 

Detailed Description

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
class sdsl::inv_perm_support< t_s, t_bv, t_rank >

Class inv_perm_support adds access to the inverse of a permutation.

Template Parameters
t_sSampling parameter of the inverse permutation.
t_bvType of the bitvector used to indicate back-pointers.
t_rankType of rank_support to rank the indicator bitvector.

This support class adds access to the inverse of a permutation in at most (t_s) steps. It takes about (1/t_s \log n) space, where (n) is the size of the supported permutation.

References
[1] J. Munro, R. Raman, V. Raman, S. Rao: ,,Succinct representation of permutations'', Proceedings of ICALP 2003

Definition at line 35 of file inv_perm_support.hpp.

Member Typedef Documentation

◆ bit_vector_type

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
typedef t_bv sdsl::inv_perm_support< t_s, t_bv, t_rank >::bit_vector_type

Definition at line 43 of file inv_perm_support.hpp.

◆ const_iterator

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
typedef random_access_const_iterator<inv_perm_support> sdsl::inv_perm_support< t_s, t_bv, t_rank >::const_iterator

Definition at line 42 of file inv_perm_support.hpp.

◆ difference_type

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
typedef iv_type::difference_type sdsl::inv_perm_support< t_s, t_bv, t_rank >::difference_type

Definition at line 41 of file inv_perm_support.hpp.

◆ iv_type

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
typedef int_vector sdsl::inv_perm_support< t_s, t_bv, t_rank >::iv_type

Definition at line 38 of file inv_perm_support.hpp.

◆ rank_type

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
typedef t_rank sdsl::inv_perm_support< t_s, t_bv, t_rank >::rank_type

Definition at line 44 of file inv_perm_support.hpp.

◆ size_type

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
typedef iv_type::size_type sdsl::inv_perm_support< t_s, t_bv, t_rank >::size_type

Definition at line 39 of file inv_perm_support.hpp.

◆ value_type

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
typedef iv_type::value_type sdsl::inv_perm_support< t_s, t_bv, t_rank >::value_type

Definition at line 40 of file inv_perm_support.hpp.

Constructor & Destructor Documentation

◆ inv_perm_support() [1/4]

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
sdsl::inv_perm_support< t_s, t_bv, t_rank >::inv_perm_support ( )
inline

Definition at line 52 of file inv_perm_support.hpp.

◆ inv_perm_support() [2/4]

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
sdsl::inv_perm_support< t_s, t_bv, t_rank >::inv_perm_support ( const inv_perm_support< t_s, t_bv, t_rank > &  p)
inline

Definition at line 54 of file inv_perm_support.hpp.

◆ inv_perm_support() [3/4]

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
sdsl::inv_perm_support< t_s, t_bv, t_rank >::inv_perm_support ( inv_perm_support< t_s, t_bv, t_rank > &&  p)
inline

Definition at line 63 of file inv_perm_support.hpp.

◆ inv_perm_support() [4/4]

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
sdsl::inv_perm_support< t_s, t_bv, t_rank >::inv_perm_support ( const iv_type v)
inline

Constructor.

Definition at line 66 of file inv_perm_support.hpp.

Member Function Documentation

◆ begin()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
const_iterator sdsl::inv_perm_support< t_s, t_bv, t_rank >::begin ( ) const
inline

Returns a const_iterator to the first element.

Definition at line 156 of file inv_perm_support.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
template<typename archive_t >
void sdsl::inv_perm_support< t_s, t_bv, t_rank >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Load via cereal.

Definition at line 219 of file inv_perm_support.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
template<typename archive_t >
void sdsl::inv_perm_support< t_s, t_bv, t_rank >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Serialise (save) via cereal.

Definition at line 210 of file inv_perm_support.hpp.

◆ end()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
const_iterator sdsl::inv_perm_support< t_s, t_bv, t_rank >::end ( ) const
inline

Returns a const_iterator to the element after the last element.

Definition at line 159 of file inv_perm_support.hpp.

◆ load()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
void sdsl::inv_perm_support< t_s, t_bv, t_rank >::load ( std::istream &  in)
inline

Load sampling from disk.

Definition at line 201 of file inv_perm_support.hpp.

◆ operator!=()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
bool sdsl::inv_perm_support< t_s, t_bv, t_rank >::operator!= ( inv_perm_support< t_s, t_bv, t_rank > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 235 of file inv_perm_support.hpp.

◆ operator=() [1/2]

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
inv_perm_support & sdsl::inv_perm_support< t_s, t_bv, t_rank >::operator= ( const inv_perm_support< t_s, t_bv, t_rank > &  p)
inline

Assignment operation.

Definition at line 164 of file inv_perm_support.hpp.

◆ operator=() [2/2]

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
inv_perm_support & sdsl::inv_perm_support< t_s, t_bv, t_rank >::operator= ( inv_perm_support< t_s, t_bv, t_rank > &&  p)
inline

Assignment move operation.

Definition at line 175 of file inv_perm_support.hpp.

◆ operator==()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
bool sdsl::inv_perm_support< t_s, t_bv, t_rank >::operator== ( inv_perm_support< t_s, t_bv, t_rank > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 228 of file inv_perm_support.hpp.

◆ operator[]()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
value_type sdsl::inv_perm_support< t_s, t_bv, t_rank >::operator[] ( size_type  i) const
inline

Access operator.

Definition at line 135 of file inv_perm_support.hpp.

◆ serialize()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
size_type sdsl::inv_perm_support< t_s, t_bv, t_rank >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Serialize into stream.

Definition at line 189 of file inv_perm_support.hpp.

◆ set_vector()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
void sdsl::inv_perm_support< t_s, t_bv, t_rank >::set_vector ( const iv_type v)
inline

Definition at line 161 of file inv_perm_support.hpp.

◆ size()

template<uint64_t t_s = 32, class t_bv = bit_vector, class t_rank = typename bit_vector::rank_1_type>
size_type sdsl::inv_perm_support< t_s, t_bv, t_rank >::size ( ) const
inline

Definition at line 153 of file inv_perm_support.hpp.


The documentation for this class was generated from the following file: