An implementation of a B+-tree for storing n values S[0..n-1] of type VALUE in leaves. More...

#include <bp_tree.hpp>

Public Types
using	NodePointer = BPNodePointer< LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM >

using	Node = BPInternalNode< LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM >

using	PostorderIterator = BPPostorderIterator< LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM >

using	ValueForwardIterator = BPValueForwardIterator< LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM >

using	LeafForwardIterator = BPLeafForwardIterator< LEAF_CONTAINER, VALUE, MAX_DEGREE, USE_PSUM >

using	BPFunctions = BPInternalNodeFunctions< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, MAX_DEGREE, USE_PSUM >

Public Member Functions
Constructors and Destructor
	BPTree ()
	Default constructor.

	BPTree (BPTree &&other) noexcept
	Default move constructor.

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

	~BPTree ()
	Default destructor.

Operators
BPTree &	operator= (BPTree &&other) noexcept
	Default move assignment operator.

Iterators
PostorderIterator	get_postorder_iterator_begin () const
	Return an iterator pointing to the first node in postorder traversal.

PostorderIterator	get_postorder_iterator_end () const
	Return an iterator pointing to the end of postorder traversal.

ValueForwardIterator	get_value_forward_iterator_begin () const
	Return an iterator pointing to the first value in the values `S`[0..n-1].

ValueForwardIterator	get_value_forward_iterator_end () const
	Return an iterator pointing to the end of the values `S`[0..n-1].

LeafForwardIterator	get_leaf_forward_iterator_begin () const
	Return an iterator pointing to the first leaf in forward traversal.

LeafForwardIterator	get_leaf_forward_iterator_end () const
	Return an iterator pointing to the end of forward leaf traversal.

Lightweight functions for accessing to properties of this class
const std::vector< NodePointer > &	get_temporary_path () const
	Returns the path computed by the last search operation.

uint64_t	get_max_degree_of_internal_node () const
	Return `MAX_DEGREE`.

uint64_t	get_split_process_counter () const
	Return the number of split operations performed internally.

uint64_t	size () const
	Return the number of values stored in this tree (i.e., `n`).

uint64_t	capacity () const
	Return the number of values that can be stored in this tree without resizing the vector that stores LEAF_CONTAINER instances.

double	get_value_density () const
	Return the density of this tree (i.e., `n` / `capacity()`).

uint64_t	get_max_count_of_values_in_leaf () const
	Return `LEAF_CONTAINER_MAX_SIZE`.

uint64_t	height () const
	Return the height of this tree.

uint64_t	get_leaf_count () const
	Return the number of leaves in this tree (i.e., `y`).

uint64_t	get_leaf_container_vector_size () const
	Return the size of the vector that stores LEAF_CONTAINER instances.

bool	empty () const
	Return true if n = 0, false otherwise.

LEAF_CONTAINER &	get_leaf_container (uint64_t i)
	Returns a reference to the LEAF CONTAINER at position `i` in the vector `leaf_container_vec`.

const LEAF_CONTAINER &	get_leaf_container (uint64_t i) const
	Returns a const reference to the LEAF CONTAINER at position `i` in the vector `leaf_container_vec`.

uint64_t	size_in_bytes (bool only_dynamic_memory=false) const
	Returns the total memory size of this B+-tree.

BPTree *	get_linked_tree () const
	Gets the B+ tree linked to this instance.

Convertion functions
std::vector< VALUE >	to_value_vector () const
	Return the values `S`[0..n-1] as a vector of `VALUE`.

Main queries (Access, search, and psum operations)
VALUE	at (uint64_t i) const
	Return B[i].

uint64_t	get_value_index (uint64_t leaf_index_j, uint64_t position_in_leaf_container_p) const
	Returns the index i of the value `S`[i] stored in the LEAF CONTAINER `W`[j] as the (p+1)-th value.

uint64_t	psum () const
	Return the sum of the weights of `S`[0..n-1].

uint64_t	psum (uint64_t i) const
	Return the sum of the weights of `S`[0..i].

int64_t	search (uint64_t u) const
	Return the smallest index `i` such that `psum(i)` >= u if it exists, otherwise return -1.

int64_t	select0 (uint64_t i) const
	Returns the position of the (i+1)-th 0 in `S`[0..n-1] if it exists, otherwise return -1.

void	get_path_from_root_to_first_leaf (std::vector< NodePointer > &output_path) const
	Compute the path from the root to the first leaf, and store it in the `output_path`.

void	get_path_from_root_to_last_leaf (std::vector< NodePointer > &output_path) const
	Compute the path from the root to the last leaf, and store it in the `output_path`.

int64_t	compute_path_from_root_to_leaf (uint64_t i) const
	Compute the path from the root to the leaf containing S[i], and return the position of `S`[i] in the LEAF CONTAINER of the leaf.

int64_t	compute_path_from_root_to_leaf (uint64_t i, std::vector< NodePointer > &output_path) const
	Compute the path from the root to the leaf containing S[i], store it in the `output_path`, and return the position of `S`[i] in the LEAF CONTAINER of the leaf.

bool	check_if_leaf_container_vec_is_sorted () const
	Checks if the leaf containers are sorted in the vector `W`, i.e., `W`[i] is the leaf container of the i-th leaf.

Print and verification functions
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_tree () const
	Prints the B+ tree in a tree-like format.

void	print_info (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Prints detailed information about the B+ tree.

void	print_leaves () const
	Prints the leaves of the B+ tree.

void	print_internal_nodes () const
	Print the internal nodes of this B+ tree.

void	print_leaf_containers () const
	Prints the leaf containers of the B+ tree.

void	print_information_about_performance (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the performance 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_debug_info () const
	Print debug information about this instance.

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

Update operations
void	initialize ()
	Initializes this instance.

void	swap (BPTree &_tree, bool swap_linked_tree=true)
	Swap operation.

void	clear ()
	Clear the B+-tree and reset it to an empty state (i.e., n = 0, x = 0, y = 0).

void	push_back (VALUE value)
	Push a given value to the end of the sequence `S`.

void	push_many (const std::vector< VALUE > &values_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 (VALUE value)
	Push a given value to the beginning of the sequence `S`.

uint64_t	remove_using_path (const std::vector< NodePointer > &path, uint64_t position_in_leaf_container_q)
	Remove `S`[i] from the sequence `S` using (i) the path from the root to the leaf containing `S`[i] and (ii) the position `q` of `S`[i] in the LEAF CONTAINER of the leaf.

void	remove (uint64_t i)
	Remove `S`[i] from the sequence `S`.

void	insert (uint64_t i, VALUE v, uint64_t weight_w)
	Insert a given value `v` with weight `w` at position `i` in the sequence `S`.

void	increment (uint64_t i, int64_t delta)
	Update `S`[i] and its weight using a given value `delta` and the increment function supported by the LEAF CONTAINER.

void	resize (uint64_t _size, VALUE default_value)
	Change the size of the sequence `S` to a given integer `_size`. If we need push a new value to `S`, then the value is initialized with `default_value`.

void	set_linked_tree (BPTree *_tree)
	Sets a given BPTree instance to be linked to this instance.

void	sort_leaf_containers ()
	Sorts the leaf containers so that each W[i] is the LEAF CONTAINER of the i-th leaf.

void	build (const std::vector< VALUE > &_values)
	Builds the B+ tree so that `S`[0..n-1] = `_values`[0..n-1].

Static Public Member Functions
Load, save, and builder functions
static BPTree	load_from_bytes (const std::vector< uint8_t > &data, uint64_t &pos)
	Returns the BPTree instance loaded from a byte vector `data` at the position `pos`.

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

static void	store_to_bytes (BPTree &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 (BPTree &item, std::ofstream &os)
	Save the given instance `item` to a file stream `os`.

Detailed Description

template<typename LEAF_CONTAINER, typename VALUE, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>
class stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >

An implementation of a B+-tree for storing n values S[0..n-1] of type VALUE in leaves.

The details of this B+-tree is as follows:

This B+-tree consists of x internal nodes and y leaves.
Every internal node has at most MAX_DEGREE children. The number of the children is at least MAX_DEGREE / 2 if n is sufficiently large.
Every leaf is an LEAF_CONTAINER instance that stores at most LEAF_CONTAINER_MAX_SIZE values. The number of these values is at least LEAF_CONTAINER_MAX_SIZE / 2 if n is sufficiently large.
y LEAF_CONTAINER instances are stored in a vector W[0..z-1], where z = Ω(y)
Each value S[i] can have a weight w(i). If USE_PSUM is true, the prefix sum of the weights of S[0..i-1] can be computed in O(\log n) time.

Member Function Documentation

◆ at()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

VALUE stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::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:

◆ build()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::build ( const std::vector< VALUE > & _values )

inline

Builds the B+ tree so that S[0..n-1] = _values[0..n-1].

Note: O(n log n) time?

Here is the call graph for this function:

Here is the caller graph for this function:

◆ check_if_leaf_container_vec_is_sorted()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

bool stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::check_if_leaf_container_vec_is_sorted ( ) const

inline

Checks if the leaf containers are sorted in the vector W, i.e., W[i] is the leaf container of the i-th leaf.

Note: O(n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compute_path_from_root_to_leaf() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

int64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::compute_path_from_root_to_leaf ( uint64_t i ) const

inline

Compute the path from the root to the leaf containing S[i], and return the position of S[i] in the LEAF CONTAINER of the leaf.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compute_path_from_root_to_leaf() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

int64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::compute_path_from_root_to_leaf	(	uint64_t	i,
		std::vector< NodePointer > &	output_path
	)		const

inline

Compute the path from the root to the leaf containing S[i], store it in the output_path, and return the position of S[i] in the LEAF CONTAINER of the leaf.

Note: O(\log n) time

Here is the call graph for this function:

◆ get_memory_usage_info()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

std::vector< std::string > stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_path_from_root_to_first_leaf()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::get_path_from_root_to_first_leaf ( std::vector< NodePointer > & output_path ) const

inline

Compute the path from the root to the first leaf, and store it in the output_path.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_path_from_root_to_last_leaf()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::get_path_from_root_to_last_leaf ( std::vector< NodePointer > & output_path ) const

inline

Compute the path from the root to the last leaf, and store it in the output_path.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_value_index()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::get_value_index	(	uint64_t	leaf_index_j,
		uint64_t	position_in_leaf_container_p
	)		const

inline

Returns the index i of the value S[i] stored in the LEAF CONTAINER W[j] as the (p+1)-th value.

Warning: This function is not supported if USE_PARENT_FIELD is false.

Note: O(\log n) time

◆ increment()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::increment	(	uint64_t	i,
		int64_t	delta
	)

inline

Update S[i] and its weight using a given value delta and the increment function supported by the LEAF CONTAINER.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::insert	(	uint64_t	i,
		VALUE	v,
		uint64_t	weight_w
	)

inline

Insert a given value v with weight w at position i in the sequence S.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ print_information_about_performance()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::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 caller graph for this function:

◆ print_memory_usage()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::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 (-1 for no output)

Here is the call graph for this function:

◆ print_statistics()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::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:

Here is the caller graph for this function:

◆ psum() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::psum ( ) const

inline

Return the sum of the weights of S[0..n-1].

Note: O(1) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ psum() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::psum ( uint64_t i ) const

inline

Return the sum of the weights of S[0..i].

Note: O(\log n) time

Here is the call graph for this function:

◆ push_back()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::push_back ( VALUE value )

inline

Push a given value to the end of the sequence S.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push_front()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::push_front ( VALUE value )

inline

Push a given value to the beginning of the sequence S.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push_many()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::push_many ( const std::vector< VALUE > & values_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:

Here is the caller graph for this function:

◆ remove()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::remove ( uint64_t i )

inline

Remove S[i] from the sequence S.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove_using_path()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::remove_using_path	(	const std::vector< NodePointer > &	path,
		uint64_t	position_in_leaf_container_q
	)

inline

Remove S[i] from the sequence S using (i) the path from the root to the leaf containing S[i] and (ii) the position q of S[i] in the LEAF CONTAINER of the leaf.

Returns: The number of merge operations performed

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ resize()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::resize	(	uint64_t	_size,
		VALUE	default_value
	)

inline

Change the size of the sequence S to a given integer _size. If we need push a new value to S, then the value is initialized with default_value.

Note: O(n) time

Here is the call graph for this function:

◆ search()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

int64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::search ( uint64_t u ) const

inline

Return the smallest index i such that psum(i) >= u if it exists, otherwise return -1.

Note: O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ select0()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

int64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::select0 ( uint64_t i ) const

inline

Returns the position of the (i+1)-th 0 in S[0..n-1] if it exists, otherwise return -1.

Note: The result of this function is undefined if S is not a bit sequence.; O(\log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set_linked_tree()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::set_linked_tree ( BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM > * _tree )

inline

Sets a given BPTree instance to be linked to this instance.

Note: O(1) time

◆ size_in_bytes()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::size_in_bytes ( bool only_dynamic_memory = false ) const

inline

Returns the total memory size of this B+-tree.

Parameters

only_dynamic_memory If true, only the size of the dynamic memory is returned (but this option is not supported yet).

Here is the caller graph for this function:

◆ sort_leaf_containers()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::sort_leaf_containers ( )

inline

Sorts the leaf containers so that each W[i] is the LEAF CONTAINER of the i-th leaf.

Note: O(n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ swap()

template<typename LEAF_CONTAINER , typename VALUE , uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE, bool USE_PARENT_FIELD, bool USE_PSUM>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM >::swap	(	BPTree< LEAF_CONTAINER, VALUE, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE, USE_PARENT_FIELD, USE_PSUM > &	_tree,
		bool	swap_linked_tree = `true`
	)

inline

Swap operation.

Parameters

swap_linked_tree If true, swap the linked tree pointer.

Here is the caller graph for this function:

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

include/bp_tree.hpp
include/permutation/bp_tree_template.hpp

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ at()

◆ build()

◆ check_if_leaf_container_vec_is_sorted()

◆ compute_path_from_root_to_leaf() [1/2]

◆ compute_path_from_root_to_leaf() [2/2]

◆ get_memory_usage_info()

◆ get_path_from_root_to_first_leaf()

◆ get_path_from_root_to_last_leaf()

◆ get_value_index()

◆ increment()

◆ insert()

◆ print_information_about_performance()

◆ print_memory_usage()

◆ print_statistics()

◆ psum() [1/2]

◆ psum() [2/2]

◆ push_back()

◆ push_front()

◆ push_many()

◆ remove()

◆ remove_using_path()

◆ resize()

◆ search()

◆ select0()

◆ set_linked_tree()

◆ size_in_bytes()

◆ sort_leaf_containers()

◆ swap()