A dynamic data structure that maintains a sequence of 64-bit non-negative integers S[0..n-1]. More...

#include <dynamic_sequence64.hpp>

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

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

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

	DynamicSequence64 (DynamicSequence64 &&) 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
DynamicSequence64 &	operator= (const DynamicSequence64 &)=delete
	Deleted copy assignment operator.

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

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

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

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

Main queries
uint64_t	at (uint64_t pos) const
	Return the (i+1)-th element of `S`[i].

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

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 (DynamicSequence64 &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_many (const std::vector< uint64_t > &items)
	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 (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_info () const
	Print the statistics of this data structure.

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	verify () const
	Verify the internal consistency of this data structure.

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

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

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

static void	store_to_bytes (DynamicSequence64 &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 (DynamicSequence64 &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 = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>
class stool::bptree::DynamicSequence64< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >

A dynamic data structure that maintains a sequence of 64-bit non-negative integers S[0..n-1].

Member Function Documentation

◆ at()

template<typename LEAF_CONTAINER = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

uint64_t stool::bptree::DynamicSequence64< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::at ( uint64_t pos ) 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 = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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 = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

std::vector< std::string > stool::bptree::DynamicSequence64< 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 = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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 = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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 = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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 = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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:

◆ print_memory_usage()

template<typename LEAF_CONTAINER = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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 = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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:

◆ push_back()

template<typename LEAF_CONTAINER = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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_front()

template<typename LEAF_CONTAINER = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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:

◆ push_many()

template<typename LEAF_CONTAINER = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::push_many ( const std::vector< uint64_t > & items )

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 LEAF_CONTAINER = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< 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:

◆ set_value()

template<typename LEAF_CONTAINER = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

void stool::bptree::DynamicSequence64< LEAF_CONTAINER, TREE_DEGREE, LEAF_CONTAINER_MAX_SIZE >::set_value	(	uint64_t	i,
		uint64_t	v
	)

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:

◆ size_in_bytes()

template<typename LEAF_CONTAINER = stool::NaiveFLCVector<>, uint64_t TREE_DEGREE = 62, uint64_t LEAF_CONTAINER_MAX_SIZE = 256>

uint64_t stool::bptree::DynamicSequence64< 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:

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

include/dynamic_sequence64.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()

◆ print_memory_usage()

◆ print_statistics()

◆ push_back()

◆ push_front()

◆ push_many()

◆ remove()

◆ set_value()

◆ size_in_bytes()