A dynamic data structure to store a permutation Π[0..n-1] of integers 0, 1, ..., n-1. More...

#include <dynamic_permutation.hpp>

Public Types
using	Tree = typename PermutationContainer::Tree

using	BPIterator = bptree::BPPostorderIterator< PermutationContainer, PermutationItem, bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, false >

using	PermIterator = PermutationContainer::PermutationIterator

using	NodePointer = bptree::BPNodePointer< PermutationContainer, PermutationItem, bptree::DEFAULT_MAX_DEGREE_OF_INTERNAL_NODE, false >

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

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

	~DynamicPermutation ()
	Default destructor.

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

DynamicPermutation &	operator= (DynamicPermutation &&other) noexcept
	Default move assignment operator.

Lightweight functions for accessing to properties of this class
Tree &	get_pi_tree ()
	Return the internal tree storing the permutation `Π`.

Tree &	get_inverse_pi_tree ()
	Get the internal tree storing the inverse permutation `Π^{-1}`.

uint64_t	get_max_degree () const
	Return the maximum degree of internal nodes in the internal trees.

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

uint64_t	size_in_bytes () const
	Return the total memory usage in bytes.

Main queries
int64_t	access (int64_t i) const
	Return `Π`[i].

int64_t	inverse (int64_t i) const
	Return `Π^{-1}`[i].

Conversion functions
std::string	to_string () const
	Return the permutation `Π` as a string.

std::vector< uint64_t >	to_pi_vector () const
	Return the permutation `Π` as a vector of uint64_t.

std::vector< uint64_t >	to_inverse_pi_vector () const
	Return the inverse permutation `Π^{-1}` as a vector of uint64_t.

Update operations
void	clear ()
	Clear the elements in `Π`

void	swap (DynamicPermutation &item)
	Swap operation.

void	insert (int64_t pi_index_p, int64_t inverse_pi_index_q)
	Insert a given element `q` at the position `p` in `Π` and appropriately modify the elements of `Π` (i.e., each element x in `Π` is updated to x+1 if x >= q)

void	erase (int64_t pi_index_p)
	Remove the element `Π`[p] from `Π` and appropriately modify the elements of `Π` (i.e., each element x in `Π` is updated to x-1 if x > Π[p])

void	move_pi_index (int64_t from_p, int64_t to_x)
	Move the element `Π`[p] in `Π` to the position `x` in `Π`

void	sort_leaf_containers ()
	Sorts the leaf containers of the internal trees.

template<typename PI_ITERATOR_BEGIN , typename PI_ITERATOR_END >
void	build (PI_ITERATOR_BEGIN beg, PI_ITERATOR_END end, uint64_t pi_size, int message_paragraph=stool::Message::SHOW_MESSAGE)
	Build a new DynamicPermutation from a given sequence of length `pi_size` starting from `beg` and ending at `end`.

Print and verification functions
void	print_information_about_performance (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the performance information of this data structure.

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_content (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the permutation and inverse permutation stored in this data structure.

void	print_trees (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the internal trees in this data structure.

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

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

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

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

Detailed Description

A dynamic data structure to store a permutation Π[0..n-1] of integers 0, 1, ..., n-1.

Member Function Documentation

◆ access()

int64_t stool::bptree::DynamicPermutation::access ( int64_t i ) const

inline

Return Π[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 PI_ITERATOR_BEGIN , typename PI_ITERATOR_END >

void stool::bptree::DynamicPermutation::build	(	PI_ITERATOR_BEGIN	beg,
		PI_ITERATOR_END	end,
		uint64_t	pi_size,
		int	message_paragraph = `stool::Message::SHOW_MESSAGE`
	)

inline

Build a new DynamicPermutation from a given sequence of length pi_size starting from beg and ending at end.

Parameters

message_paragraph The paragraph depth of message logs (-1 for no output)

Note: O(n log n) time

Here is the call graph for this function:

◆ erase()

void stool::bptree::DynamicPermutation::erase ( int64_t pi_index_p )

inline

Remove the element Π[p] from Π and appropriately modify the elements of Π (i.e., each element x in Π is updated to x-1 if x > Π[p])

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

std::vector< std::string > stool::bptree::DynamicPermutation::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:

◆ insert()

void stool::bptree::DynamicPermutation::insert	(	int64_t	pi_index_p,
		int64_t	inverse_pi_index_q
	)

inline

Insert a given element q at the position p in Π and appropriately modify the elements of Π (i.e., each element x in Π is updated to x+1 if x >= q)

Note: O(log n) time

Here is the caller graph for this function:

◆ inverse()

int64_t stool::bptree::DynamicPermutation::inverse ( int64_t i ) const

inline

Return Π^{-1}[i].

Note: O(log n) time

Here is the caller graph for this function:

◆ move_pi_index()

void stool::bptree::DynamicPermutation::move_pi_index	(	int64_t	from_p,
		int64_t	to_x
	)

inline

Move the element Π[p] in Π to the position x in Π

Note: O(log n) time

Here is the call graph for this function:

◆ print_content()

void stool::bptree::DynamicPermutation::print_content ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the permutation and inverse permutation stored in this data structure.

Parameters

message_paragraph The paragraph depth of message logs

Here is the call graph for this function:

◆ print_information_about_performance()

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

◆ print_memory_usage()

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

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

◆ print_trees()

void stool::bptree::DynamicPermutation::print_trees ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the internal trees in this data structure.

Parameters

message_paragraph The paragraph depth of message logs

Here is the call graph for this function:

◆ sort_leaf_containers()

void stool::bptree::DynamicPermutation::sort_leaf_containers ( )

inline

Sorts the leaf containers of the internal trees.

Note: O(n) time

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

include/dynamic_permutation.hpp

Public Types

Public Member Functions

Load, save, and builder functions

Detailed Description

Member Function Documentation

◆ access()

◆ build()

◆ erase()

◆ get_memory_usage_info()

◆ insert()

◆ inverse()

◆ move_pi_index()

◆ print_content()

◆ print_information_about_performance()

◆ print_memory_usage()

◆ print_statistics()

◆ print_trees()

◆ sort_leaf_containers()