A dynamic data structure supporting prefix-sum query. More...

#include <dynamic_prefix_sum.hpp>

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

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

Public Member Functions
	DynamicPrefixSum (const std::vector< uint64_t > &items)

DynamicPrefixSum &	operator= (const DynamicPrefixSum &)=delete

	DynamicPrefixSum (DynamicPrefixSum &&) noexcept=default

DynamicPrefixSum &	operator= (DynamicPrefixSum &&) noexcept=default

Iterators
The iterators supported this data structure.
Tree::ValueForwardIterator	begin () const

Tree::ValueForwardIterator	end () const

Properties
The properties of this class.
Tree &	__get_tree ()
	Get the internal tree of this data structure.

uint64_t	get_degree () const
	Get the maximum degree of internal nodes of the internal tree of this data structure.

uint64_t	size () const
	Return the number of elements stored in this data structure.

uint64_t	at (uint64_t pos) const
	Return the element at the given position.

uint64_t	size_in_bytes () const
	Return the size of this data structure in bytes.

Conversion functions
The conversion functions supported this data structure.
std::vector< uint64_t >	to_vector () const
	Return the elements stored in this data structure as a vector.

std::vector< uint8_t >	to_u8_vector () const
	Return the elements stored in this data structure as a vector of uint8_t.

std::string	to_string () const

Queries
The queries supported this data structure.
uint64_t	psum (uint64_t i) const
	Return the sum of the first i values stored in this data structure.

uint64_t	psum () const
	Return the sum of the stored values.

int64_t	search (uint64_t x) const
	Return the smallest i such that psum(i) >= x.

int64_t	predecessor_index (uint64_t value) const

int64_t	successor_index (uint64_t value) const

uint64_t	operator[] (uint64_t n) const

Update operations
The update operations supported this data structure.
void	swap (DynamicPrefixSum &item)

void	clear ()
	Clear the elements stored in this data structure.

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

void	push_back (uint64_t value)

void	push_front (uint64_t value)

void	pop_back ()

void	pop_front ()

void	insert (uint64_t pos, uint64_t value)

void	remove (uint64_t pos)

void	increment (uint64_t i, int64_t delta)

void	decrement (uint64_t i, int64_t delta)

void	push_many (const std::vector< uint64_t > &items)

void	set_value (uint64_t i, uint64_t value)

double	density () const

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

void	print_memory_usage (int message_paragraph=stool::Message::SHOW_MESSAGE) const

void	print_statistics (int message_paragraph=stool::Message::SHOW_MESSAGE) const

void	print_information_about_performance (int message_paragraph=stool::Message::SHOW_MESSAGE) const

void	print_tree (int message_paragraph=stool::Message::SHOW_MESSAGE) const

Static Public Member Functions
Builder and Writer functions
The functions for building and writing this data structure.
static DynamicPrefixSum	build (const std::vector< uint64_t > &items)

static DynamicPrefixSum	build_from_data (const std::vector< uint8_t > &data, uint64_t &pos)

static DynamicPrefixSum	build_from_data (std::ifstream &ifs)

static void	save (DynamicPrefixSum &item, std::vector< uint8_t > &output, uint64_t &pos)

static void	save (DynamicPrefixSum &item, std::ofstream &os)

Other static functions
The other static functions supported this data structure.
static std::string	name ()

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.

Member Function Documentation

◆ __get_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>

Tree & stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::__get_tree ( )

inline

Get the internal tree of this data structure.

Returns: The internal tree of this data structure.

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

inline

Return the element at the given position.

Parameters

pos	The position of the element to return.

Returns: The element at the given position.

Here is the call graph for this function:

◆ get_degree()

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

inline

Get the maximum degree of internal nodes of the internal tree of this data structure.

Returns: The maximum degree of internal nodes of the internal tree of this data structure.

Here is the call graph for this function:

◆ size()

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

inline

Return the number of elements stored in this data structure.

Returns: The number of elements stored in this data structure.

Here is the call graph for this function:

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

inline

Return the size of this data structure in bytes.

Returns: The size of this data structure in bytes.

Here is the call graph for this function:

◆ to_u8_vector()

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< uint8_t > stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::to_u8_vector ( ) const

inline

Return the elements stored in this data structure as a vector of uint8_t.

Returns: The elements stored in this data structure as a vector of uint8_t.

Here is the call graph for this function:

◆ to_vector()

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< uint64_t > stool::bptree::DynamicPrefixSum< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::to_vector ( ) const

inline

Return the elements stored in this data structure as a vector.

Returns: The elements stored in this data structure as a vector.

Here is the call graph for this function:

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

include/prefix_sum/dynamic_prefix_sum.hpp

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ __get_tree()

◆ at()

◆ get_degree()

◆ size()

◆ size_in_bytes()

◆ to_u8_vector()

◆ to_vector()