A class supporting rank queries in linear time. More...

#include <rank_support_int_scan.hpp>

Inheritance diagram for sdsl::rank_support_int_scan< alphabet_size >:

Public Types
typedef int_vector	int_vector_type

typedef rank_support_int< alphabet_size >::size_type	size_type

typedef rank_support_int< alphabet_size >::value_type	value_type

Public Types inherited from sdsl::rank_support_int< alphabet_size >
typedef int_vector ::size_type	size_type

typedef int_vector ::value_type	value_type

Public Member Functions
	rank_support_int_scan (int_vector<> const *v=nullptr)

	rank_support_int_scan (rank_support_int_scan const &rs)=default

	rank_support_int_scan (rank_support_int_scan &&rs)=default

rank_support_int_scan &	operator= (rank_support_int_scan const &rs)=default

rank_support_int_scan &	operator= (rank_support_int_scan &&rs)=default

size_type	rank (size_type idx, const value_type v) const
	Counts the occurrences of v in the prefix [0..idx-1].

size_type	operator() (size_type idx, const value_type v) const
	Alias for rank(idx, v)

size_type	prefix_rank (size_type idx, const value_type v) const
	Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].

size_type	size () const

size_type	serialize (std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const
	Serializes rank_support_int.

void	load (std::istream &, int_vector<> const *v=nullptr)
	Loads the rank_support_int.

void	set_vector (int_vector<> const *v=nullptr)
	Sets the supported int_vector to the given pointer.

Public Member Functions inherited from sdsl::rank_support_int< alphabet_size >
	rank_support_int (int_vector<> const *v=nullptr)
	Constructor.

	rank_support_int (rank_support_int const &)=default
	Copy constructor.

	rank_support_int (rank_support_int &&)=default

rank_support_int &	operator= (rank_support_int const &)=default

rank_support_int &	operator= (rank_support_int &&)=default

virtual	~rank_support_int ()
	Destructor.

virtual size_type	rank (const size_type i, const value_type v) const =0
	Answers rank queries for the supported int_vector.

virtual size_type	operator() (const size_type idx, const value_type v) const =0
	Alias for rank(idx, v)

virtual size_type	prefix_rank (const size_type i, const value_type v) const =0
	Answers rank queries for the supported int_vector.

virtual size_type	serialize (std::ostream &out, structure_tree_node *v, const std::string name) const =0
	Serializes rank_support_int.

virtual void	load (std::istream &in, int_vector<> const *v=nullptr)=0
	Loads the rank_support_int.

virtual void	set_vector (int_vector<> const *v=nullptr)=0
	Sets the supported int_vector to the given pointer.

Additional Inherited Members
Static Protected Member Functions inherited from sdsl::rank_support_int< alphabet_size >
template<typename uintX_t >
static constexpr uintX_t	bm_rec (const uintX_t w, const uint8_t length, const uint8_t max_length)
	Constructs a bit mask with the pattern w of a given length.

static std::array< uint64_t, alphabet_size >	generate_mask_array ()

static constexpr uint64_t	mask_prefix (value_type const v, uint64_t const w_even, uint64_t const w_odd) noexcept
	Mask the set prefix positions.

static constexpr uint64_t	set_positions_prefix (const uint64_t w, const value_type v) noexcept
	Count how often value v or smaller occurs in the word w.

static constexpr uint64_t	set_positions (const uint64_t w, const value_type v) noexcept
	Count how often value v occurs in the word w.

template<typename... value_t>
static constexpr std::array< uint64_t, sizeof...(value_t)>	word_prefix_rank (const uint64_t word, const size_type bit_pos, const value_t... values) noexcept
	Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx.

static constexpr uint32_t	word_rank (const uint64_t word, const size_type bit_pos, const value_type v) noexcept
	Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx.

static constexpr uint32_t	full_word_prefix_rank (const uint64_t word, const value_type v) noexcept
	Counts the occurrences of v in the word starting at data up to position idx.

static constexpr uint32_t	full_word_rank (const uint64_t word, const value_type v) noexcept
	Counts the occurrences of v in the word starting at data up to position idx.

static constexpr uint64_t	extract_word (uint64_t const *data, const size_type word_position) noexcept
	Returns the word a the given word position.

Protected Attributes inherited from sdsl::rank_support_int< alphabet_size >
int_vector const *	m_v
	Pointer to the rank supported bit_vector.

Static Protected Attributes inherited from sdsl::rank_support_int< alphabet_size >
static constexpr uint8_t	sigma {alphabet_size}

static constexpr uint8_t	sigma_bits {ceil_log2(alphabet_size)}

static constexpr uint8_t	bits_per_word {(64 / sigma_bits) * sigma_bits}

static constexpr uint64_t	even_mask {bm_rec<uint64_t>(bits::lo_set[sigma_bits], sigma_bits * 2, 64)}

static constexpr uint64_t	carry_select_mask {bm_rec<uint64_t>(1ULL << sigma_bits, sigma_bits * 2, 64)}

static const std::array< uint64_t, alphabet_size >	masks = generate_mask_array()

Detailed Description

template<uint8_t alphabet_size>
class sdsl::rank_support_int_scan< alphabet_size >

A class supporting rank queries in linear time.

Template Parameters

alphabet_size Size of the alphabet used in the underlying sdsl::int_vector.

Space complexity: Constant.

Time complexity: Linear in the size of the supported vector.

Definition at line 28 of file rank_support_int_scan.hpp.

Member Typedef Documentation

◆ int_vector_type

template<uint8_t alphabet_size>

typedef int_vector sdsl::rank_support_int_scan< alphabet_size >::int_vector_type

Definition at line 34 of file rank_support_int_scan.hpp.

◆ size_type

template<uint8_t alphabet_size>

typedef rank_support_int<alphabet_size>::size_type sdsl::rank_support_int_scan< alphabet_size >::size_type

Definition at line 35 of file rank_support_int_scan.hpp.

◆ value_type

template<uint8_t alphabet_size>

typedef rank_support_int<alphabet_size>::value_type sdsl::rank_support_int_scan< alphabet_size >::value_type

Definition at line 36 of file rank_support_int_scan.hpp.

Constructor & Destructor Documentation

◆ rank_support_int_scan() [1/3]

template<uint8_t alphabet_size>

sdsl::rank_support_int_scan< alphabet_size >::rank_support_int_scan ( int_vector<> const * v = nullptr )

inlineexplicit

Definition at line 39 of file rank_support_int_scan.hpp.

◆ rank_support_int_scan() [2/3]

template<uint8_t alphabet_size>

sdsl::rank_support_int_scan< alphabet_size >::rank_support_int_scan ( rank_support_int_scan< alphabet_size > const & rs )

default

◆ rank_support_int_scan() [3/3]

template<uint8_t alphabet_size>

sdsl::rank_support_int_scan< alphabet_size >::rank_support_int_scan ( rank_support_int_scan< alphabet_size > && rs )

default

Member Function Documentation

◆ load()

template<uint8_t alphabet_size>

void sdsl::rank_support_int_scan< alphabet_size >::load	(	std::istream &	in,
		int_vector<> const *	v = `nullptr`
	)

inlinevirtual

Loads the rank_support_int.

Parameters

in	In-Stream to load the rank_support_int data from.
v	The supported int_vector.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 58 of file rank_support_int_scan.hpp.

◆ operator()()

template<uint8_t alphabet_size>

size_type sdsl::rank_support_int_scan< alphabet_size >::operator()	(	size_type	idx,
		const value_type	v
	)		const

inlinevirtual

Alias for rank(idx, v)

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 45 of file rank_support_int_scan.hpp.

◆ operator=() [1/2]

template<uint8_t alphabet_size>

rank_support_int_scan & sdsl::rank_support_int_scan< alphabet_size >::operator= ( rank_support_int_scan< alphabet_size > && rs )

default

◆ operator=() [2/2]

template<uint8_t alphabet_size>

rank_support_int_scan & sdsl::rank_support_int_scan< alphabet_size >::operator= ( rank_support_int_scan< alphabet_size > const & rs )

default

◆ prefix_rank()

template<uint8_t alphabet_size>

rank_support_int_scan< alphabet_size >::size_type sdsl::rank_support_int_scan< alphabet_size >::prefix_rank	(	size_type	idx,
		const value_type	v
	)		const

inlinevirtual

Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].

Parameters

idx	Argument for the length of the prefix v[0..idx-1].
v	Argument which value (including smaller values) to count.

See also: rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 104 of file rank_support_int_scan.hpp.

◆ rank()

template<uint8_t alphabet_size>

rank_support_int_scan< alphabet_size >::size_type sdsl::rank_support_int_scan< alphabet_size >::rank	(	size_type	idx,
		const value_type	v
	)		const

inlinevirtual

Counts the occurrences of v in the prefix [0..idx-1].

Parameters

idx	Argument for the length of the prefix v[0..idx-1].
v	Argument which value to count.

See also: prefix_rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 76 of file rank_support_int_scan.hpp.

◆ serialize()

template<uint8_t alphabet_size>

size_type sdsl::rank_support_int_scan< alphabet_size >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = `nullptr`,
		const std::string	name = `""`
	)		const

inlinevirtual

Serializes rank_support_int.

Parameters

out	Out-Stream to serialize the data to.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 54 of file rank_support_int_scan.hpp.

◆ set_vector()

template<uint8_t alphabet_size>

void sdsl::rank_support_int_scan< alphabet_size >::set_vector ( int_vector<> const * v = nullptr )

inlinevirtual

Sets the supported int_vector to the given pointer.

Parameters

v	The new int_vector to support.

Note: Method init has to be called before the next call of rank or prefix_rank.

See also: init, rank, prefix_rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 63 of file rank_support_int_scan.hpp.

◆ size()

template<uint8_t alphabet_size>

size_type sdsl::rank_support_int_scan< alphabet_size >::size ( ) const

inline

Definition at line 50 of file rank_support_int_scan.hpp.

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

/builddir/build/BUILD/sdsl-lite-3.0.2/include/sdsl/rank_support_int_scan.hpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ int_vector_type

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ rank_support_int_scan() [1/3]

◆ rank_support_int_scan() [2/3]

◆ rank_support_int_scan() [3/3]

Member Function Documentation

◆ load()

◆ operator()()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ prefix_rank()

◆ rank()

◆ serialize()

◆ set_vector()

◆ size()