A dynamic data structure supporting rank and select queries on a bit sequence. More...

#include <dynamic_bit_sequence.hpp>

Collaboration diagram for stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >:

[legend]

Public Member Functions
	DynamicBitSequence (const DynamicBitSequence &)=delete
	Deleted copy constructor.

	DynamicBitSequence ()
	Default constructor initializes the tree with default degree.

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

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

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

Properties
The properties of this class.
uint64_t	size () const
	Returns the size of the bit sequence.

uint64_t	size_in_bytes () const
	Returns the size of the bit sequence in bytes.

Queries
The queries supported this data structure.
bool	empty () const
	Checks if the bit sequence is empty.

bool	at (uint64_t pos) const
	Returns the bit at the specified position.

int64_t	rank1 (uint64_t i) const
	Returns the number of 1s up to position i.

int64_t	rank0 (uint64_t i) const
	Returns the number of 0s up to position i.

int64_t	rank (uint64_t i, bool c) const
	Returns the number of bits with value c up to position i.

int64_t	select1 (uint64_t i) const
	Returns the position of the i-th 1.

int64_t	select0 (uint64_t i) const
	Returns the position of the i-th 0.

int64_t	select (uint64_t i, bool c) const
	Returns the position of the i-th bit with value c.

int64_t	count_c (bool c) const
	Returns the number of bits with value c in the sequence.

bool	operator[] (uint64_t n) const
	Returns the bit at the specified position.

uint64_t	psum (uint64_t x) const
	Returns the prefix sum up to position x.

uint64_t	psum () const
	Returns the total prefix sum.

int64_t	search (uint64_t sum) const
	Searches for the position where the prefix sum equals sum.

Update operations
The update operations supported this data structure.
void	set_degree (uint64_t degree)
	Sets the degree of the tree.

void	swap (DynamicBitSequence &item)
	Swaps the contents of this sequence with another.

void	clear ()
	Clears the bit sequence.

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

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

void	insert (uint64_t pos, bool value)
	Inserts a bit at the specified position.

void	remove (uint64_t pos)
	Removes the bit at the specified position.

void	set_bit (uint64_t i, bool b)
	Sets the bit at the specified position.

void	sort_leaf_containers ()
	Sorts the leaf containers.

void	push_many (const std::vector< bool > &items)
	Adds multiple bits to the end of the sequence.

void	print_debug_info () const

Print functions
The functions for printing messages.
std::vector< std::string >	get_memory_usage_info (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Returns memory usage information.

void	print_memory_usage (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Prints memory usage information.

void	print_statistics (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Prints statistics about the bit sequence.

void	print_content (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Prints the content of the bit sequence.

void	print (std::string name="DynamicBitSequence", int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Prints the bit sequence.

Conversion functions
The conversion functions supported this data structure.
std::vector< uint64_t >	to_value_vector () const
	Converts the bit sequence to a vector of uint64_t.

std::string	to_string () const
	Converts the bit sequence to a string.

std::vector< bool >	to_vector () const
	Converts the bit sequence to a vector of bool.

Iterators
The iterators supported this data structure.
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.

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.

Static Public Member Functions
Builder and Writer functions
The functions for building and writing this data structure.
static void	save (DynamicBitSequence &item, std::vector< uint8_t > &output, uint64_t &pos)
	Saves the bit sequence to a vector.

static void	save (DynamicBitSequence &item, std::ofstream &os)
	Saves the bit sequence to a file.

static DynamicBitSequence	build (const std::vector< bool > &items)
	Builds a bit sequence from a vector of bool.

static DynamicBitSequence	build_from_data (const std::vector< uint8_t > &data, uint64_t &pos)
	Builds a bit sequence from a vector of uint8_t.

static DynamicBitSequence	build_from_data (std::ifstream &ifs)
	Builds a bit sequence from a file.

Public Attributes
Tree	tree

Other static functions
The other static functions supported this data structure.
void	print_information_about_performance (int message_paragraph=stool::Message::SHOW_MESSAGE) const

double	density () const

void	verify () const

static std::string	name ()
	Returns the name of the bit sequence.

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.

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 pos ) const

inline

Returns the bit at the specified position.

Parameters

pos	The position to query.

Returns: bool The bit value at the specified position.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build()

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

static DynamicBitSequence stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::build ( const std::vector< bool > & items )

inlinestatic

Builds a bit sequence from a vector of bool.

Parameters

items	The vector of bool to build from.
tree_degree	The degree of the tree.

Returns: DynamicBitSequence The built bit sequence.

Here is the call graph for this function:

◆ build_from_data() [1/2]

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

static DynamicBitSequence stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::build_from_data	(	const std::vector< uint8_t > &	data,
		uint64_t &	pos
	)

inlinestatic

Builds a bit sequence from a vector of uint8_t.

Parameters

data	The vector of uint8_t to build from.
pos	The position in the input vector.

Returns: DynamicBitSequence The built bit sequence.

Here is the call graph for this function:

◆ build_from_data() [2/2]

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

static DynamicBitSequence stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::build_from_data ( std::ifstream & ifs )

inlinestatic

Builds a bit sequence from a file.

Parameters

ifs	The input file stream.

Returns: DynamicBitSequence The built bit sequence.

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

Returns the number of bits with value c in the sequence.

Parameters

c	The bit value to count.

Returns: int64_t The number of bits with value c.

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 the bit sequence is empty.

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

Here is the call graph for this function:

◆ get_bit_forward_iterator_begin()

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

BitForwardIterator< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE > stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::get_bit_forward_iterator_begin ( ) const

inline

Returns an iterator to the beginning of the bit sequence.

Returns: BitForwardIterator The iterator.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_leaf_forward_iterator_end()

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

BitForwardIterator< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE > stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::get_leaf_forward_iterator_end ( ) const

inline

Returns an iterator to the end of the bit sequence.

Returns: BitForwardIterator The iterator.

Here is the caller 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

Returns memory usage information.

Parameters

message_paragraph The paragraph level for messages.

Returns: std::vector<std::string> The memory usage information.

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	pos,
		bool	value
	)

inline

Inserts a bit at the specified position.

Parameters

pos	The position to insert at.
value	The bit value to insert.

Here is the call graph for this function:

◆ name()

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

static std::string stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::name ( )

inlinestatic

Returns the name of the bit sequence.

Returns: std::string The name.

Here is the caller graph for this function:

◆ operator[]()

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 >::operator[] ( uint64_t n ) const

inline

Returns the bit at the specified position.

Parameters

n	The position to query.

Returns: bool The bit value at the specified position.

Here is the call graph for this function:

◆ print()

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	(	std::string	name = `"DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >"`,
		int	message_paragraph = `stool::Message::SHOW_MESSAGE`
	)		const

inline

Prints the bit sequence.

Parameters

name	The name to print.
message_paragraph	The paragraph level for messages.

Here is the call 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 ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Prints the content of the bit sequence.

Parameters

message_paragraph The paragraph level for messages.

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

Prints memory usage information.

Parameters

message_paragraph The paragraph level for messages.

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

Prints statistics about the bit sequence.

Parameters

message_paragraph The paragraph level for messages.

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 total prefix sum.

Returns: uint64_t The total prefix sum.

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 x ) const

inline

Returns the prefix sum up to position x.

Parameters

x	The position to query.

Returns: uint64_t The prefix sum.

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.

Parameters

value The bit value to add.

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.

Parameters

value The bit value to add.

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 )

inline

Adds multiple bits to the end of the sequence.

Parameters

items The bits to add.

Here is the call graph for this function:

◆ 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 >::rank	(	uint64_t	i,
		bool	c
	)		const

inline

Returns the number of bits with value c up to position i.

Parameters

i	The position to query.
c	The bit value to count.

Returns: int64_t The number of bits with value c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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 >::rank0 ( uint64_t i ) const

inline

Returns the number of 0s up to position i.

Parameters

i	The position to query.

Returns: int64_t The number of 0s.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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 >::rank1 ( uint64_t i ) const

inline

Returns the number of 1s up to position i.

Parameters

i	The position to query.

Returns: int64_t The number of 1s.

Here is the call graph for this function:

Here is the caller 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 pos )

inline

Removes the bit at the specified position.

Parameters

pos	The position to remove from.

Here is the call graph for this function:

◆ save() [1/2]

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

static void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::save	(	DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE > &	item,
		std::ofstream &	os
	)

inlinestatic

Saves the bit sequence to a file.

Parameters

item	The bit sequence to save.
os	The output file stream.

Here is the call graph for this function:

◆ save() [2/2]

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

static void stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::save	(	DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE > &	item,
		std::vector< uint8_t > &	output,
		uint64_t &	pos
	)

inlinestatic

Saves the bit sequence to a vector.

Parameters

item	The bit sequence to save.
output	The output vector.
pos	The position in the output vector.

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 sum ) const

inline

Searches for the position where the prefix sum equals sum.

Parameters

sum	The sum to search for.

Returns: int64_t The position where the prefix sum equals sum, or -1 if not found.

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 of the i-th bit with value c.

Parameters

i	The index of the bit to find.
c	The bit value to find.

Returns: int64_t The position of the i-th bit with value c, or -1 if not found.

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 of the i-th 0.

Parameters

i	The index of the 0 to find.

Returns: int64_t The position of the i-th 0, or -1 if not found.

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 of the i-th 1.

Parameters

i	The index of the 1 to find.

Returns: int64_t The position of the i-th 1, or -1 if not found.

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

Sets the bit at the specified position.

Parameters

i	The position to set.
b	The bit value to set.

Here is the call graph for this function:

◆ set_degree()

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_degree ( uint64_t degree )

inline

Sets the degree of the tree.

Parameters

degree The degree to set.

Here is the call graph for this function:

◆ size()

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 ( ) const

inline

Returns the size of the bit sequence.

Returns: uint64_t The number of bits in the sequence.

Here is the call graph for this function:

Here is the caller 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 ( ) const

inline

Returns the size of the bit sequence in bytes.

Returns: uint64_t The number of bytes used by the sequence.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ swap()

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 >::swap ( DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE > & item )

inline

Swaps the contents of this sequence with another.

Parameters

item	The sequence to swap with.

Here is the call graph for this function:

◆ to_string()

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

std::string stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::to_string ( ) const

inline

Converts the bit sequence to a string.

Returns: std::string The string representation.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ to_value_vector()

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

std::vector< uint64_t > stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::to_value_vector ( ) const

inline

Converts the bit sequence to a vector of uint64_t.

Returns: std::vector<uint64_t> The vector representation.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ to_vector()

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

std::vector< bool > stool::bptree::DynamicBitSequence< CONTAINER, CONTAINER_ITERATOR, MAX_TREE_DEGREE, MAX_BIT_CONTAINER_SIZE >::to_vector ( ) const

inline

Converts the bit sequence to a vector of bool.

Returns: std::vector<bool> The vector representation.

Here is the call graph for this function:

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

include/sequence/dynamic_bit_sequence.hpp

Public Member Functions

Static Public Member Functions

Public Attributes

Other static functions

Detailed Description

Member Function Documentation

◆ at()

◆ build()

◆ build_from_data() [1/2]

◆ build_from_data() [2/2]

◆ count_c()

◆ empty()

◆ get_bit_forward_iterator_begin()

◆ get_leaf_forward_iterator_end()

◆ get_memory_usage_info()

◆ insert()

◆ name()

◆ operator[]()

◆ print()

◆ print_content()

◆ print_memory_usage()

◆ print_statistics()

◆ psum() [1/2]

◆ psum() [2/2]

◆ push_back()

◆ push_front()

◆ push_many()

◆ rank()

◆ rank0()

◆ rank1()

◆ remove()

◆ save() [1/2]

◆ save() [2/2]

◆ search()

◆ select()

◆ select0()

◆ select1()

◆ set_bit()

◆ set_degree()

◆ size()

◆ size_in_bytes()

◆ swap()

◆ to_string()

◆ to_value_vector()

◆ to_vector()