A dynamic data structure supporting rank and select queries on a bit sequence B[0..n-1]. More...

#include <dynamic_bit_sequence.hpp>

Public Member Functions
Constructors and Destructor
	DynamicBitSequence ()
	Default constructor with \|B\| = 0.

	DynamicBitSequence (const DynamicBitSequence &)=delete
	Deleted copy constructor.

	DynamicBitSequence (DynamicBitSequence &&) noexcept=default
	Default move constructor.

Iterators
BitForwardIterator< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >	get_bit_forward_iterator_begin () const
	Returns an iterator to the beginning of the bit sequence `B`.

BitForwardIterator< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >	get_leaf_forward_iterator_end () const
	Returns an iterator to the end of the bit sequence `B`.

Operators
DynamicBitSequence &	operator= (const DynamicBitSequence &)=delete
	Deleted copy assignment operator.

DynamicBitSequence &	operator= (DynamicBitSequence &&) noexcept=default
	Default move assignment operator.

bool	operator[] (uint64_t i) const
	The alias for at query.

Lightweight functions for accessing to properties of this class
bool	empty () const
	Checks if `B` is empty.

uint64_t	size () const
	Return `\|B\|`.

uint64_t	height () const
	Return the height of the internal tree storing the bit sequence `B`.

uint64_t	size_in_bytes (bool only_dynamic_memory=false) const
	Return the total memory usage in bytes.

double	density () const
	Return the density of the internal tree.

Conversion functions
std::vector< uint64_t >	to_packed_vector () const
	Return `B` as a packed vector of uint64_t (i.e., the length of the vector is \|B\| / 64).

std::string	to_string () const
	Return `B` as a binary string.

std::vector< bool >	to_vector () const
	Return `B` as a vector of bool.

Main queries
bool	at (uint64_t i) const
	Return `B`[i].

int64_t	one_based_rank1 (uint64_t i) const
	Returns the number of 1 in `B`[0..i-1].

int64_t	one_based_rank0 (uint64_t i) const
	Returns the number of 0 in `B`[0..i-1].

int64_t	one_based_rank (uint64_t i, bool c) const
	Returns the number of `c` in `B`[0..i-1].

int64_t	select1 (uint64_t i) const
	Returns the position `p` of the (i+1)-th 1 in `B` if such a position exists, otherwise returns -1.

int64_t	select0 (uint64_t i) const
	Returns the position `p` of the (i+1)-th 0 in `B` if such a position exists, otherwise returns -1.

int64_t	select (uint64_t i, bool c) const
	Returns the position `p` of the (i+1)-th `c` in `B` if such a position exists, otherwise returns -1.

int64_t	count1 () const
	Return the number of 1 in `B`[0..n-1].

int64_t	count0 () const
	Return the number of 0 in `B`[0..n-1].

int64_t	count_c (bool c) const
	Return the number of `c` in `B`[0..n-1].

uint64_t	psum (uint64_t i) const
	Returns the number of 1s in the bit sequence `B`[0..i].

uint64_t	psum () const
	Returns the number of 1s in the bit sequence `B`[0..n-1].

int64_t	search (uint64_t x) const
	Returns the first position `p` such that psum(p) >= x if such a position exists, otherwise returns -1.

Update operations
void	swap (DynamicBitSequence &item)
	Swap operation.

void	clear ()
	Clear the elements in `B`.

void	push_back (bool value)
	Adds a bit to the end of the sequence `B`.

void	push_many (const std::vector< bool > &items_Q)
	Add a given sequence `Q`[0..k-1] to the end of `S`[0..n-1] (i.e., `S` = S[0..n-1]Q[0..k-1])

void	push_front (bool value)
	Adds a bit to the beginning of the sequence `B`.

void	insert (uint64_t p, bool v)
	Insert a bit `v` at the position `p` in the bits `B`.

void	remove (uint64_t p)
	Removes the bit at the position `p` in the bits `B`.

void	set_bit (uint64_t i, bool b)
	Replace the bit `B`[i] with the bit `b`.

void	set_bits (uint64_t i, std::vector< bool > &bits)
	Replace the bits `B`[i..i+m-1] with the bits `bits`[0..m-1].

void	sort_leaf_containers ()
	Sorts the leaf containers of the internal tree.

Print and verification functions
void	print_debug_info () const
	Print debug information about this instance.

std::vector< std::string >	get_memory_usage_info (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Return the memory usage information of this data structure as a vector of strings.

void	print_memory_usage (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the memory usage information of this data structure.

void	print_statistics (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the statistics of this data structure.

void	print_information_about_performance (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the performance information of this data structure.

void	print_content (std::string name="DynamicBitSequence", int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the bit sequence `B`.

void	verify () const
	Verify the internal consistency of this data structure.

Static Public Member Functions
Load, save, and builder functions
static DynamicBitSequence	build (const std::vector< bool > &items)
	Build a new DynamicBitSequence from a given sequence `items`.

static DynamicBitSequence	load_from_bytes (const std::vector< uint8_t > &data, uint64_t &pos)
	Returns the DynamicBitSequence instance loaded from a byte vector `data` at the position `pos`.

static DynamicBitSequence	load_from_file (std::ifstream &ifs)
	Returns the DynamicBitSequence instance loaded from a file stream `ifs`.

static void	store_to_bytes (DynamicBitSequence &item, std::vector< uint8_t > &output, uint64_t &pos)
	Save the given instance `item` to a byte vector `output` at the position `pos`.

static void	store_to_file (DynamicBitSequence &item, std::ofstream &os)
	Save the given instance `item` to a file stream `os`.

Other static functions
static std::string	name ()
	Return the name of the DynamicBitSequence for debugging.

Detailed Description

template<typename CONTAINER, typename CONTAINER_ITERATOR, uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>
class stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >

A dynamic data structure supporting rank and select queries on a bit sequence B[0..n-1].

Member Function Documentation

◆ at()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

bool stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::at ( uint64_t i ) const

inline

Return B[i].

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ count0()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::count0 ( ) const

inline

Return the number of 0 in B[0..n-1].

Note: O(1) time

Here is the call graph for this function:

◆ count1()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::count1 ( ) const

inline

Return the number of 1 in B[0..n-1].

Note: O(1) time

Here is the call graph for this function:

◆ count_c()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::count_c ( bool c ) const

inline

Return the number of c in B[0..n-1].

Note: O(1) time

Here is the call graph for this function:

◆ empty()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

bool stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::empty ( ) const

inline

Checks if B is empty.

Returns: bool True if the sequence is empty, false otherwise.

Here is the call graph for this function:

◆ get_memory_usage_info()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

std::vector< std::string > stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::get_memory_usage_info ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Return the memory usage information of this data structure as a vector of strings.

Parameters

message_paragraph The paragraph depth of message logs (-1 for no output)

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::insert	(	uint64_t	p,
		bool	v
	)

inline

Insert a bit v at the position p in the bits B.

Note: O(log n) time

Here is the call graph for this function:

◆ one_based_rank()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::one_based_rank	(	uint64_t	i,
		bool	c
	)		const

inline

Returns the number of c in B[0..i-1].

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ one_based_rank0()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::one_based_rank0 ( uint64_t i ) const

inline

Returns the number of 0 in B[0..i-1].

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ one_based_rank1()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::one_based_rank1 ( uint64_t i ) const

inline

Returns the number of 1 in B[0..i-1].

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ print_content()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::print_content	(	std::string	name = `"DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >"`,
		int	message_paragraph = `stool::Message::SHOW_MESSAGE`
	)		const

inline

Print the bit sequence B.

Parameters

name	The name to print.
message_paragraph	The paragraph depth of message logs

Here is the call graph for this function:

◆ print_information_about_performance()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::print_information_about_performance ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the performance information of this data structure.

Parameters

message_paragraph The paragraph depth of message logs

Here is the call graph for this function:

◆ print_memory_usage()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::print_memory_usage ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the memory usage information of this data structure.

Parameters

message_paragraph The paragraph depth of message logs

Here is the call graph for this function:

◆ print_statistics()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::print_statistics ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the statistics of this data structure.

Parameters

message_paragraph The paragraph depth of message logs

Here is the call graph for this function:

◆ psum() [1/2]

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

uint64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::psum ( ) const

inline

Returns the number of 1s in the bit sequence B[0..n-1].

Note: O(1) time

Here is the call graph for this function:

◆ psum() [2/2]

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

uint64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::psum ( uint64_t i ) const

inline

Returns the number of 1s in the bit sequence B[0..i].

Note: O(log n) time

Here is the call graph for this function:

◆ push_back()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::push_back ( bool value )

inline

Adds a bit to the end of the sequence B.

Note: O(log n) time

Here is the call graph for this function:

◆ push_front()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::push_front ( bool value )

inline

Adds a bit to the beginning of the sequence B.

Note: O(log n) time

Here is the call graph for this function:

◆ push_many()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::push_many ( const std::vector< bool > & items_Q )

inline

Add a given sequence Q[0..k-1] to the end of S[0..n-1] (i.e., S = S[0..n-1]Q[0..k-1])

Note: O(|Q| log n) time

Here is the call graph for this function:

◆ remove()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::remove ( uint64_t p )

inline

Removes the bit at the position p in the bits B.

Note: O(log n) time

Here is the call graph for this function:

◆ search()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::search ( uint64_t x ) const

inline

Returns the first position p such that psum(p) >= x if such a position exists, otherwise returns -1.

Note: O(log n) time

Here is the call graph for this function:

◆ select()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::select	(	uint64_t	i,
		bool	c
	)		const

inline

Returns the position p of the (i+1)-th c in B if such a position exists, otherwise returns -1.

Note: O(log n) time

Here is the call graph for this function:

◆ select0()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::select0 ( uint64_t i ) const

inline

Returns the position p of the (i+1)-th 0 in B if such a position exists, otherwise returns -1.

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ select1()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

int64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::select1 ( uint64_t i ) const

inline

Returns the position p of the (i+1)-th 1 in B if such a position exists, otherwise returns -1.

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set_bit()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::set_bit	(	uint64_t	i,
		bool	b
	)

inline

Replace the bit B[i] with the bit b.

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set_bits()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::set_bits	(	uint64_t	i,
		std::vector< bool > &	bits
	)

inline

Replace the bits B[i..i+m-1] with the bits bits[0..m-1].

Note: O(m log n) time

Here is the call graph for this function:

◆ size_in_bytes()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

uint64_t stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::size_in_bytes ( bool only_dynamic_memory = false ) const

inline

Return the total memory usage in bytes.

Parameters

only_dynamic_memory If true, only the size of the dynamic memory is returned

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sort_leaf_containers()

template<typename CONTAINER , typename CONTAINER_ITERATOR , uint64_t MAX_TREE_DEGREE, uint64_t MAX_BIT_CONTAINER_SIZE>

void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::sort_leaf_containers ( )

inline

Sorts the leaf containers of the internal tree.

Note: O(n) time

Here is the call graph for this function:

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

include/dynamic_bit_sequence.hpp

Public Member Functions

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ at()

◆ count0()

◆ count1()

◆ count_c()

◆ empty()

◆ get_memory_usage_info()

◆ insert()

◆ one_based_rank()

◆ one_based_rank0()

◆ one_based_rank1()

◆ print_content()

◆ print_information_about_performance()

◆ print_memory_usage()

◆ print_statistics()

◆ psum() [1/2]

◆ psum() [2/2]

◆ push_back()

◆ push_front()

◆ push_many()

◆ remove()

◆ search()

◆ select()

◆ select0()

◆ select1()

◆ set_bit()

◆ set_bits()

◆ size_in_bytes()

◆ sort_leaf_containers()