A dynamic data structure supporting prefix-sum query on a unsigned 64-bit integer sequence S[0..n-1]. More...

#include <dynamic_prefix_sum.hpp>

Public Types
using	NodePointer = bptree::BPNodePointer< LEAF_CONTAINER, uint64_t, TREE_DEGREE, true >

using	Tree = bptree::BPTree< LEAF_CONTAINER, uint64_t, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE, false, true >

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

	DynamicPrefixSum (const std::vector< uint64_t > &S_)
	Default constructor with S = S_.

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

Iterators
Tree::ValueForwardIterator	begin () const
	Returns an iterator to the beginning of the sequence `S`.

Tree::ValueForwardIterator	end () const
	Returns an iterator to the end of the sequence `S`.

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

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

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

Lightweight functions for accessing to properties of this class
Tree &	__get_tree ()
	Get the internal tree storing the sequence `S`.

uint64_t	get_degree () const
	Return the maximum degree of internal nodes of the internal tree storing the sequence `S`.

uint64_t	size () const
	Return \|S\|.

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

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

Conversion functions
std::vector< uint64_t >	to_vector () const
	Return `S` as a vector.

std::vector< uint8_t >	to_u8_vector () const
	Return `S` as a vector of uint8_t.

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

Main queries (Access, search, and psum operations)
uint64_t	at (uint64_t i) const
	Return the (i+1)-th element of `S`[i].

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

uint64_t	psum (uint64_t i) const
	Return the sum of the first (i+1) values of `S`[0..n-1].

uint64_t	psum (uint64_t i, uint64_t j) const
	Return the sum of `S`[i..j].

uint64_t	reverse_psum (uint64_t i) const
	Returns the sum of integers in `S`[(n-1)-i..n-1].

int64_t	search (uint64_t x) const
	Return the smallest i such that psum(i) >= x if such a position exists, otherwise returns -1.

int64_t	predecessor_index (uint64_t x) const
	Return the largest i such that psum(i) <= x if such a position exists, otherwise returns -1.

int64_t	successor_index (uint64_t x) const
	Return the smallest i such that psum(i) >= x if such a position exists, otherwise returns -1.

Update operations
void	set_value (uint64_t i, uint64_t value)
	Set a given value `v` at a given position `i` in `S`.

void	set_values (uint64_t i, const std::vector< uint64_t > &values_Q)
	Replaces the \|Q\| values `S`[i..i+\|Q\|-1] with the given values Q[0..\|Q\|-1].

void	increment (uint64_t i, int64_t delta)
	Set the value `S`[i+delta] at a given position `i` in `S`.

void	decrement (uint64_t i, int64_t delta)
	Set the value `S`[i-delta] at a given position `i` in `S`.

void	swap (DynamicPrefixSum &item)
	Swap operation.

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

void	push_back (uint64_t value)
	Add a given integer to the end of `S`.

void	push_back_many (const std::vector< uint64_t > &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_many (const std::vector< uint64_t > &items)
	Alias for push_back_many.

void	push_front (uint64_t value)
	Add a given value to the beginning of `S`.

void	pop_back ()
	Remove the last element from `S`.

void	pop_front ()
	Remove the first element from `S`.

void	insert (uint64_t pos, uint64_t value)
	Insert a given integer `value` into `S` as the (pos+1)-th element.

void	remove (uint64_t pos)
	Remove the element at the position `pos` from `S` and return it.

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_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_tree (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the form of the internal tree of this data structure.

void	print_info () const
	Print the statistics of this data structure.

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

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

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

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

static void	store_to_bytes (DynamicPrefixSum &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 (DynamicPrefixSum &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 DynamicPrefixSum for debugging.

Detailed Description

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>
class stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >

A dynamic data structure supporting prefix-sum query on a unsigned 64-bit integer sequence S[0..n-1].

Member Function Documentation

◆ at()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

uint64_t stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::at ( uint64_t i ) const

inline

Return the (i+1)-th element of S[i].

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ decrement()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::decrement	(	uint64_t	i,
		int64_t	delta
	)

inline

Set the value S[i-delta] at a given position i in S.

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_memory_usage_info()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

std::vector< std::string > stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ increment()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::increment	(	uint64_t	i,
		int64_t	delta
	)

inline

Set the value S[i+delta] at a given position i in S.

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 = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::insert	(	uint64_t	pos,
		uint64_t	value
	)

inline

Insert a given integer value into S as the (pos+1)-th element.

Note: O(log n) time

Here is the call graph for this function:

◆ pop_back()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::pop_back ( )

inline

Remove the last element from S.

Note: O(log n) time

Here is the call graph for this function:

◆ pop_front()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::pop_front ( )

inline

Remove the first element from S.

Note: O(log n) time

Here is the call graph for this function:

◆ predecessor_index()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

int64_t stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::predecessor_index ( uint64_t x ) const

inline

Return the largest i such that psum(i) <= x if such a position exists, otherwise returns -1.

Note: O(log n) time

Here is the call graph for this function:

◆ print_information_about_performance()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_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 LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_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 (-1 for no output)

Here is the call graph for this function:

◆ print_statistics()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_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:

Here is the caller graph for this function:

◆ print_tree()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::print_tree ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the form of the internal tree of this data structure.

Parameters

message_paragraph The paragraph depth of message logs

Here is the call graph for this function:

◆ psum() [1/3]

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

uint64_t stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::psum ( ) const

inline

Return the sum 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/3]

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

uint64_t stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::psum ( uint64_t i ) const

inline

Return the sum of the first (i+1) values of S[0..n-1].

Note: O(log n) time

Here is the call graph for this function:

◆ psum() [3/3]

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

uint64_t stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::psum	(	uint64_t	i,
		uint64_t	j
	)		const

inline

Return the sum of S[i..j].

Note: O(log n) time

Here is the call graph for this function:

◆ push_back()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::push_back ( uint64_t value )

inline

Add a given integer to the end of S.

Note: O(log n) time

Here is the call graph for this function:

◆ push_back_many()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::push_back_many ( const std::vector< uint64_t > & 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:

◆ push_front()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::push_front ( uint64_t value )

inline

Add a given value to the beginning of S.

Note: O(log n) time

Here is the call graph for this function:

◆ remove()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::remove ( uint64_t pos )

inline

Remove the element at the position pos from S and return it.

Note: O(log n) time

Here is the call graph for this function:

◆ reverse_psum()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

uint64_t stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::reverse_psum ( uint64_t i ) const

inline

Returns the sum of integers in S[(n-1)-i..n-1].

Note: O(\log n) time

Here is the call graph for this function:

◆ set_value()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::set_value	(	uint64_t	i,
		uint64_t	value
	)

inline

Set a given value v at a given position i in S.

Note: O(log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set_values()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

void stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::set_values	(	uint64_t	i,
		const std::vector< uint64_t > &	values_Q
	)

inline

Replaces the |Q| values S[i..i+|Q|-1] with the given values Q[0..|Q|-1].

Note: O(|Q| log n) time

Here is the call graph for this function:

◆ size_in_bytes()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

uint64_t stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::size_in_bytes ( bool only_dynamic_memory = false ) const

inline

Returns 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:

◆ successor_index()

template<typename LEAF_CONTAINER = VLCDeque, uint64_t TREE_DEGREE = bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, uint64_t LEAF_CONTAINER_MAX_SIZE = bptree::DEFAULT_MAX_COUNT_OF_VALUES_IN_LEAF>

int64_t stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::successor_index ( uint64_t x ) const

inline

Return the smallest i such that psum(i) >= x if such a position exists, otherwise returns -1.

Note: O(log n) time

Here is the call graph for this function:

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

include/dynamic_prefix_sum.hpp

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ at()

◆ decrement()

◆ get_memory_usage_info()

◆ increment()

◆ insert()

◆ pop_back()

◆ pop_front()

◆ predecessor_index()

◆ print_information_about_performance()

◆ print_memory_usage()

◆ print_statistics()

◆ print_tree()

◆ psum() [1/3]

◆ psum() [2/3]

◆ psum() [3/3]

◆ push_back()

◆ push_back_many()

◆ push_front()

◆ remove()

◆ reverse_psum()

◆ set_value()

◆ set_values()

◆ size_in_bytes()

◆ successor_index()