#include <WordDynRankSel.hpp>

Inheritance diagram for sux::bits::WordDynRankSel< SPS, AT >:

Public Member Functions
	WordDynRankSel (uint64_t bitvector[], size_t size)

uint64_t *	bitvector () const

virtual uint64_t	rank (size_t pos)

virtual size_t	select (uint64_t rank)

virtual size_t	selectZero (uint64_t rank)

virtual uint64_t	update (size_t index, uint64_t word)

virtual bool	set (size_t index)

virtual bool	clear (size_t index)

virtual bool	toggle (size_t index)

virtual size_t	size () const

virtual size_t	bitCount () const

virtual uint64_t	rank (std::size_t pos)=0

uint64_t	rank (std::size_t from, std::size_t to)

virtual uint64_t	rankZero (std::size_t pos)

uint64_t	rankZero (std::size_t from, std::size_t to)

Public Member Functions inherited from sux::bits::DynamicBitVector
virtual	~DynamicBitVector ()=default

Public Member Functions inherited from sux::Rank
virtual	~Rank ()=default

virtual uint64_t	rank (std::size_t pos)=0

uint64_t	rank (std::size_t from, std::size_t to)

virtual uint64_t	rankZero (std::size_t pos)

uint64_t	rankZero (std::size_t from, std::size_t to)

Public Member Functions inherited from sux::Select
virtual	~Select ()=default

Public Member Functions inherited from sux::SelectZero
virtual	~SelectZero ()=default

Friends
std::ostream &	operator<< (std::ostream &os, const WordDynRankSel< SPS, AT > &bv)

std::istream &	operator>> (std::istream &is, WordDynRankSel< SPS, AT > &bv)

Detailed Description

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>
class sux::bits::WordDynRankSel< SPS, AT >

Ranking and selection in a dynamic bit vector by means of a searchable prefix-sum data structure and broadword operations on a single word.

The constructors of this class only store a reference to a provided bit vector. The content of the bit vector should be changed only through the mutation methods of this class, or the results will be unpredictable.

Warning: if you plan an calling rank(size_t) with argument size(), you must have at least one additional free bit at the end of the provided bit vector.

Template Parameters

SPS	underlying sux::util::SearchablePrefixSums implementation.
AT	a type of memory allocation for the underlying structure.

Constructor & Destructor Documentation

◆ WordDynRankSel()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

sux::bits::WordDynRankSel< SPS, AT >::WordDynRankSel	(	uint64_t	bitvector[],
		size_t	size
	)

inline

Creates a new instance using a given bit vector.

Thus constructor only store a reference to the provided bit vector. The content of the bit vector should be changed only through the mutation methods of this class, or the results will be unpredictable.

Warning: if you plan an calling rank(size_t) with argument size(), you must have at least one additional free bit at the end of the provided bit vector.

Parameters

bitvector	a bit vector of 64-bit words.
size	the length (in bits) of the bit vector.

Member Function Documentation

◆ bitCount()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual size_t sux::bits::WordDynRankSel< SPS, AT >::bitCount ( ) const

inlinevirtual

Returns an estimate of the size (in bits) of this structure.

Implements sux::bits::DynamicBitVector.

◆ bitvector()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

uint64_t* sux::bits::WordDynRankSel< SPS, AT >::bitvector ( ) const

inline

◆ clear()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual bool sux::bits::WordDynRankSel< SPS, AT >::clear ( size_t index )

inlinevirtual

Clear (set to 0) a given bit in the bitvector.

Parameters

index index (in bits) in the bitvector.

Returns: : the previous value of such a bit.

Implements sux::bits::DynamicBitVector.

◆ rank() [1/3]

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual uint64_t sux::bits::WordDynRankSel< SPS, AT >::rank ( size_t pos )

inlinevirtual

◆ rank() [2/3]

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

uint64_t sux::Rank::rank

inline

Returns the number of ones between two given positions.

Parameters

from	A starting position from 0 to size() (included).
to	An ending position from `from` to size() (included).

Returns: the number of ones from the starting position (included) to the ending position (excluded).

◆ rank() [3/3]

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual uint64_t sux::Rank::rank

Returns the number of ones before the given posistion.

Parameters

pos	A position from 0 to size() (included).

Returns: the number of ones from the start of the bit vector up to the given position (excluded).

◆ rankZero() [1/2]

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

uint64_t sux::Rank::rankZero

inline

Returns the number of zeros between two given positions.

Parameters

from	A starting position from 0 to size() (included).
to	An ending position from `from` to size() (included).

Returns: the number of zeros from the starting position (included) to the ending position (excluded).

◆ rankZero() [2/2]

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual uint64_t sux::Rank::rankZero

inline

Returns the number of zeros before the given posistion.

Parameters

pos	A position from 0 to size() (included).

Returns: the number of zeros from the start of the bit vector up to the given position (excluded).

◆ select()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual size_t sux::bits::WordDynRankSel< SPS, AT >::select ( uint64_t rank )

inlinevirtual

Returns the position of the one with given rank.

Parameters

rank	the desired rank (index) of a one in the bit vector.

Returns: the position of the zero with given rank; the result is undefined if no zero of the given rank exists.

Implements sux::Select.

◆ selectZero()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual size_t sux::bits::WordDynRankSel< SPS, AT >::selectZero ( uint64_t rank )

inlinevirtual

Returns the position of the zero with given rank.

Parameters

rank	the desired rank (index) of a zero in the bit vector.

Returns: the position of the zero with given rank; the result is undefined if no zero of the given rank exists.

Implements sux::SelectZero.

◆ set()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual bool sux::bits::WordDynRankSel< SPS, AT >::set ( size_t index )

inlinevirtual

Set (set to 1) a given bit in the bitvector.

Parameters

index index (in bits) in the bitvector.

Returns: the previous value of such a bit.

Implements sux::bits::DynamicBitVector.

◆ size()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual size_t sux::bits::WordDynRankSel< SPS, AT >::size ( ) const

inlinevirtual

Returns the length (in bits) of the underlying bit vector.

Implements sux::Rank.

◆ toggle()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual bool sux::bits::WordDynRankSel< SPS, AT >::toggle ( size_t index )

inlinevirtual

Change the value of a given bit in the bitvector.

Parameters

index index (in bits) in the bitvector.

Returns: : the previous value of such a bit.

Implements sux::bits::DynamicBitVector.

◆ update()

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

virtual uint64_t sux::bits::WordDynRankSel< SPS, AT >::update	(	size_t	index,
		uint64_t	word
	)

inlinevirtual

Replace a given word in the bitvector.

Parameters

index	index (in words) in the bitvector.
word	new value for `bitvector[index]`.

Returns: the replaced word.

Implements sux::bits::DynamicBitVector.

Friends And Related Function Documentation

◆ operator<<

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

std::ostream& operator<<	(	std::ostream &	os,
		const WordDynRankSel< SPS, AT > &	bv
	)

friend

◆ operator>>

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>

std::istream& operator>>	(	std::istream &	is,
		WordDynRankSel< SPS, AT > &	bv
	)

friend

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

sux/bits/WordDynRankSel.hpp

Public Member Functions

Friends

Detailed Description

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC> class sux::bits::WordDynRankSel< SPS, AT >

Constructor & Destructor Documentation

◆ WordDynRankSel()

Member Function Documentation

◆ bitCount()

◆ bitvector()

◆ clear()

◆ rank() [1/3]

◆ rank() [2/3]

◆ rank() [3/3]

◆ rankZero() [1/2]

◆ rankZero() [2/2]

◆ select()

◆ selectZero()

◆ set()

◆ size()

◆ toggle()

◆ update()

Friends And Related Function Documentation

◆ operator<<

◆ operator>>

template<template< size_t, util::AllocType AT > class SPS, util::AllocType AT = util::AllocType::MALLOC>
class sux::bits::WordDynRankSel< SPS, AT >