sdsl::nearest_neighbour_dictionary< 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>

List of all members.

Public Types
typedef bit_vector::size_type	size_type
Public Member Functions
	nearest_neighbour_dictionary ()
	Default constructor.
	nearest_neighbour_dictionary (const bit_vector &v)
	Constructor.
	nearest_neighbour_dictionary (const nearest_neighbour_dictionary &nnd)
	Copy constructor.
	~nearest_neighbour_dictionary ()
	Destructor.
nearest_neighbour_dictionary &	operator= (const nearest_neighbour_dictionary &nnd)
void	swap (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
size_type	size () const
size_type	ones () const
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
	Serializes the nearest_neighbour_dictionary.
void	load (std::istream &in)
	Loads the nearest_neighbour_dictionary.

---

Detailed Description

template<uint8_t sample_dens>
class sdsl::nearest_neighbour_dictionary< 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 sample_dens corresponds to parameter t in the paper. The data structure the following methods:

• rank
• select
• prev
• next

---

Constructor & Destructor Documentation

template<uint8_t sample_dens>

sdsl::nearest_neighbour_dictionary< sample_dens >::nearest_neighbour_dictionary

(

const bit_vector &

v

)

[inline]

Constructor.

Parameters:

v	The supported bit_vector.

---

Member Function Documentation

template<uint8_t sample_dens>

void sdsl::nearest_neighbour_dictionary< sample_dens >::load

(

std::istream &

in

)

[inline]

Loads the nearest_neighbour_dictionary.

Parameters:

in	In-Stream to load the rank_support data from.

template<uint8_t sample_dens>

size_type sdsl::nearest_neighbour_dictionary< sample_dens >::next

(

size_type

i

)

const [inline]

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

Parameters:

i	Position .

Returns:

The minimal position where the supported bit_vector v equals 1.

Precondition:

rank(i) < ones()

Time complexity #51

template<uint8_t sample_dens>

size_type sdsl::nearest_neighbour_dictionary< sample_dens >::prev

(

size_type

i

)

const [inline]

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

Parameters:

i	Position .

Returns:

The maximal position where the supported bit_vector v equals 1.

Precondition:

rank(i+1)>0

Time complexity #51

template<uint8_t sample_dens>

size_type sdsl::nearest_neighbour_dictionary< sample_dens >::rank

(

size_type

idx

)

const [inline]

Answers rank queries for the supported bit_vector.

Parameters:

idx	Argument 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 #51

template<uint8_t sample_dens>

size_type sdsl::nearest_neighbour_dictionary< sample_dens >::select

(

size_type

i

)

const [inline]

Answers select queries for the supported bit_vector.

Parameters:

i	Select the th 1 in the supported bit_vector.

Returns:

The position of the th 1 in the supported bit_vector.

Time complexity #51

template<uint8_t sample_dens>

size_type sdsl::nearest_neighbour_dictionary< sample_dens >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = NULL,
		std::string	name = ""
	)		const [inline]

Serializes the nearest_neighbour_dictionary.

Parameters:

out	Out-Stream to serialize the data to.

---

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

• sdsl/include/sdsl/nearest_neighbour_dictionary.hpp