SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::nearest_neighbour_dictionary< t_sample_dens > Class Template Reference

Nearest neighbour dictionary for sparse uniform sets (described in Geary et al., A Simple Optimal Representation for Balanced Parentheses, CPM 2004). More...

#include <nearest_neighbour_dictionary.hpp>

Public Types

typedef bit_vector::size_type size_type
 

Public Member Functions

 nearest_neighbour_dictionary ()
 Default constructor.
 
 nearest_neighbour_dictionary (bit_vector const &v)
 Constructor.
 
 nearest_neighbour_dictionary (nearest_neighbour_dictionary const &nnd)
 Copy constructor.
 
 nearest_neighbour_dictionary (nearest_neighbour_dictionary &&nnd)
 Move constructor.
 
 ~nearest_neighbour_dictionary ()
 Destructor.
 
nearest_neighbour_dictionaryoperator= (nearest_neighbour_dictionary const &nnd)
 
nearest_neighbour_dictionaryoperator= (nearest_neighbour_dictionary &&nnd)
 
size_type rank (size_type idx) const
 Answers rank queries for the supported bit_vector.
 
size_type select (size_type i) const
 Answers select queries for the supported bit_vector.
 
size_type prev (size_type i) const
 Answers "previous occurence of one" queries for the supported bit_vector.
 
size_type next (size_type i) const
 Answers "next occurence of one" queries for the supported bit_vector.
 
size_type size () const
 
size_type ones () const
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the nearest_neighbour_dictionary.
 
void load (std::istream &in)
 Loads the nearest_neighbour_dictionary.
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 
bool operator== (nearest_neighbour_dictionary const &other) const noexcept
 Equality operator.
 
bool operator!= (nearest_neighbour_dictionary const &other) const noexcept
 Inequality operator.
 

Detailed Description

template<uint8_t t_sample_dens>
class sdsl::nearest_neighbour_dictionary< t_sample_dens >

Nearest neighbour dictionary for sparse uniform sets (described in Geary et al., A Simple Optimal Representation for Balanced Parentheses, CPM 2004).

Template parameter t_sample_dens corresponds to parameter t in the paper. The data structure the following methods:

  • rank
  • select
  • prev
  • next

Definition at line 44 of file nearest_neighbour_dictionary.hpp.

Member Typedef Documentation

◆ size_type

template<uint8_t t_sample_dens>
bit_vector::size_type sdsl::nearest_neighbour_dictionary< t_sample_dens >::size_type

Definition at line 50 of file nearest_neighbour_dictionary.hpp.

Constructor & Destructor Documentation

◆ nearest_neighbour_dictionary() [1/4]

template<uint8_t t_sample_dens>
sdsl::nearest_neighbour_dictionary< t_sample_dens >::nearest_neighbour_dictionary ( )
inline

Default constructor.

Definition at line 67 of file nearest_neighbour_dictionary.hpp.

◆ nearest_neighbour_dictionary() [2/4]

template<uint8_t t_sample_dens>
sdsl::nearest_neighbour_dictionary< t_sample_dens >::nearest_neighbour_dictionary ( bit_vector const & v)
inline

Constructor.

Parameters
vThe supported bit_vector.

Definition at line 73 of file nearest_neighbour_dictionary.hpp.

◆ nearest_neighbour_dictionary() [3/4]

template<uint8_t t_sample_dens>
sdsl::nearest_neighbour_dictionary< t_sample_dens >::nearest_neighbour_dictionary ( nearest_neighbour_dictionary< t_sample_dens > const & nnd)
inline

Copy constructor.

Definition at line 121 of file nearest_neighbour_dictionary.hpp.

◆ nearest_neighbour_dictionary() [4/4]

template<uint8_t t_sample_dens>
sdsl::nearest_neighbour_dictionary< t_sample_dens >::nearest_neighbour_dictionary ( nearest_neighbour_dictionary< t_sample_dens > && nnd)
inline

Move constructor.

Definition at line 133 of file nearest_neighbour_dictionary.hpp.

◆ ~nearest_neighbour_dictionary()

template<uint8_t t_sample_dens>
sdsl::nearest_neighbour_dictionary< t_sample_dens >::~nearest_neighbour_dictionary ( )
inline

Destructor.

Definition at line 139 of file nearest_neighbour_dictionary.hpp.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t t_sample_dens>
template<typename archive_t >
void sdsl::nearest_neighbour_dictionary< t_sample_dens >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Definition at line 289 of file nearest_neighbour_dictionary.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t t_sample_dens>
template<typename archive_t >
void sdsl::nearest_neighbour_dictionary< t_sample_dens >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Definition at line 278 of file nearest_neighbour_dictionary.hpp.

◆ load()

template<uint8_t t_sample_dens>
void sdsl::nearest_neighbour_dictionary< t_sample_dens >::load ( std::istream & in)
inline

Loads the nearest_neighbour_dictionary.

Parameters
inIn-Stream to load the rank_support data from.

Definition at line 267 of file nearest_neighbour_dictionary.hpp.

◆ next()

template<uint8_t t_sample_dens>
size_type sdsl::nearest_neighbour_dictionary< t_sample_dens >::next ( size_type i) const
inline

Answers "next occurence of one" queries for the supported bit_vector.

Parameters
iPosition $ i \in [0..size()-1] $.
Returns
The minimal position $ j \geq i $ where the supported bit_vector v equals 1.
Precondition
rank(i) < ones()
Time complexity $ j \geq i $#1

Definition at line 230 of file nearest_neighbour_dictionary.hpp.

◆ ones()

template<uint8_t t_sample_dens>
size_type sdsl::nearest_neighbour_dictionary< t_sample_dens >::ones ( ) const
inline

Definition at line 242 of file nearest_neighbour_dictionary.hpp.

◆ operator!=()

template<uint8_t t_sample_dens>
bool sdsl::nearest_neighbour_dictionary< t_sample_dens >::operator!= ( nearest_neighbour_dictionary< t_sample_dens > const & other) const
inlinenoexcept

Inequality operator.

Definition at line 309 of file nearest_neighbour_dictionary.hpp.

◆ operator=() [1/2]

template<uint8_t t_sample_dens>
nearest_neighbour_dictionary & sdsl::nearest_neighbour_dictionary< t_sample_dens >::operator= ( nearest_neighbour_dictionary< t_sample_dens > && nnd)
inline

Definition at line 152 of file nearest_neighbour_dictionary.hpp.

◆ operator=() [2/2]

template<uint8_t t_sample_dens>
nearest_neighbour_dictionary & sdsl::nearest_neighbour_dictionary< t_sample_dens >::operator= ( nearest_neighbour_dictionary< t_sample_dens > const & nnd)
inline

Definition at line 142 of file nearest_neighbour_dictionary.hpp.

◆ operator==()

template<uint8_t t_sample_dens>
bool sdsl::nearest_neighbour_dictionary< t_sample_dens >::operator== ( nearest_neighbour_dictionary< t_sample_dens > const & other) const
inlinenoexcept

Equality operator.

Definition at line 301 of file nearest_neighbour_dictionary.hpp.

◆ prev()

template<uint8_t t_sample_dens>
size_type sdsl::nearest_neighbour_dictionary< t_sample_dens >::prev ( size_type i) const
inline

Answers "previous occurence of one" queries for the supported bit_vector.

Parameters
iPosition $ i \in [0..size()-1] $.
Returns
The maximal position $j \leq i$ where the supported bit_vector v equals 1.
Precondition
rank(i+1)>0
Time complexity $j \leq i$#1

Definition at line 218 of file nearest_neighbour_dictionary.hpp.

◆ rank()

template<uint8_t t_sample_dens>
size_type sdsl::nearest_neighbour_dictionary< t_sample_dens >::rank ( size_type idx) const
inline

Answers rank queries for the supported bit_vector.

Parameters
idxArgument for the length of the prefix v[0..idx-1].
Returns
Number of 1-bits in the prefix [0..idx-1] of the supported bit_vector.
Time complexity #1

Definition at line 172 of file nearest_neighbour_dictionary.hpp.

◆ select()

template<uint8_t t_sample_dens>
size_type sdsl::nearest_neighbour_dictionary< t_sample_dens >::select ( size_type i) const
inline

Answers select queries for the supported bit_vector.

Parameters
iSelect the $i$th 1 in the supported bit_vector. $i\in [1..ones()]$
Returns
The position of the $i$th 1 in the supported bit_vector.
Time complexity $i$#1

Definition at line 199 of file nearest_neighbour_dictionary.hpp.

◆ serialize()

template<uint8_t t_sample_dens>
size_type sdsl::nearest_neighbour_dictionary< t_sample_dens >::serialize ( std::ostream & out,
structure_tree_node * v = nullptr,
std::string name = "" ) const
inline

Serializes the nearest_neighbour_dictionary.

Parameters
outOut-Stream to serialize the data to.

Definition at line 250 of file nearest_neighbour_dictionary.hpp.

◆ size()

template<uint8_t t_sample_dens>
size_type sdsl::nearest_neighbour_dictionary< t_sample_dens >::size ( ) const
inline

Definition at line 237 of file nearest_neighbour_dictionary.hpp.


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