The Conditional Multiway Mapped Tree (CMMTree) class definition. More...

#include <cmmtree.hpp>

Public Member Functions
	CMMTree ()
	Dfefault constructor.

	CMMTree (std::vector< X1 >const *const &adr)
	Single-argument constructor.

	CMMTree (std::vector< X1 >const *const &adr, typename std::vector< X1 >::const_iterator const &pos)
	Two arguments constructor.

	CMMTree (const CMMTree< X1, predicate > &)=delete
	Copy constructor. Construct of copies of CMMTree object is prohibited.

CMMTree< X1, predicate > &	operator= (const CMMTree< X1, predicate > &)=delete
	Copy assignment operator. Copying a CMMTree object using the assignment operator is not allowed.

	CMMTree (CMMTree &&other) noexcept
	Move constructor.

auto	operator= (CMMTree &&other) noexcept -> CMMTree< X1, predicate > &
	Move assignment operator.

	~CMMTree ()
	Destructor. The allocated memory for all nodes in the tree is released.

void	create_subtrees_roots (std::vector< X1 > const &roots_data)
	This function allows you to initialize the creation of a forest using a separate data set - different from the main input data set.

void	join_data (std::vector< X1 >const *const &adr)
	This function is used to connect the CMMTree object to the input data vector.

void	join_data (std::vector< X1 >const *const &adr, typename std::vector< X1 >::const_iterator const &pos)
	This function is used to connect the CMMTree object to the input data vector.

long long	tree_create ()
	A function that starts the process of the CMMTree construction.

predicate< X1 > &	pred_value ()
	A function that allows you to modify the value of a predicate object.

predicate< X1 > const &	pred_value () const
	A function that allows you to read the value of a predicate object.

X1 const &	firstborn_value (size_t i, size_t j) const
	A function that allows you to read the value of [i,j]-th firstborn node.

size_t	all_nodes_number () const
	This function returns the number of all nodes in the CMMTree.

size_t	firstborns_number (size_t i) const
	This function returns the number of firstborn nodes of one generation of the CMMTree - at the level passed by the argument (i).

size_t	leaves_number (size_t i) const
	This function returns the number of leaves one generation of the CMMTree - at the level passed by the argument (i).

size_t	generation_size (size_t i) const
	This function returns the total number of nodes one generation of the CMMTree - at the level passed by the argument (i).

size_t	tree_height () const
	This function returns the CMMTree height.

void	generation_addresses (size_t i, std::vector< const node< X1 > * > &vec) const
	This function allows you to get all the addresses of the i-th generation firstborn nodes. Firstborn nodes addresses - at the level passed by the first argument.

void	generation_addresses (size_t i, std::vector< node< X1 > * > &vec) const
	This function allows you to get all the addresses of the first-born nodes of the i-th generation, using which you will be able to remove the selected nodes. Firstborn nodes addresses - at the level passed by the first argument.

void	leaves_addresses (size_t i, std::vector< const node< X1 > * > &vec) const
	This function allows you to get all the addresses of the i-th generation leaves.

const node< X1 > *	brother_address (const node< X1 > *ptr, size_t i) const
	This function allows you to obtain the address of the i-th brother of the firstborn node.

node< X1 > const *const &	firstborn_address (size_t i, size_t j) const
	The function returns the address of the j-th firstborn of the i-th generation.

std::vector< X1 > const *const &	P_dataset () const
	The function returns the address of the input data vector.

void	delete_one_node (node< X1 > *&to_del)
	This function deletes the node whose address is passed as an argument.

void	delete_nodes (std::vector< node< X1 > * > &to_del, size_t lev)
	Using this function you can delete more than one node from a specified node generation at once.

void	tree_clear ()
	This function clears the entire CMMTree object.

void	tree_shape (std::ostream &out) const
	This function allows you to represent a tree in a parametric form.

Friends
template<class T1 , template< typename > class T2>
std::ostream &	operator<< (std::ostream &out, CMMTree< T1, T2 > const &ref)
	Overloaded output operator to the stream.

Detailed Description

template<class X1, template< typename > class predicate>
class CMMTree< X1, predicate >

The Conditional Multiway Mapped Tree (CMMTree) class definition.

Template Parameters

X1	- a type parameter, that is, the type of input data being processed.
predicate	- a type template parameter representing the predicate class template, which is parameterized by the first parameter (X1) of the CMMTree class template.

More information - see: https://ieeexplore.ieee.org/document/9069220

Definition at line 20 of file cmmtree.hpp.

Constructor & Destructor Documentation

◆ CMMTree() [1/5]

template<class X1 , template< typename > class predicate>

CMMTree< X1, predicate >::CMMTree ( )

inline

Dfefault constructor.

If you use it then:

the root will not represent any of the elements of the dataset (D), that is, later you can create a forest of trees (sub-trees);
the tree (object of type CMMTree) is not related to any data;
before calling the tree_create() function (that creates the tree), it is necessary to use the join_data() function and pass the address of the vector containing the data as its argument.

Definition at line 43 of file cmmtree.hpp.

◆ CMMTree() [2/5]

template<class X1 , template< typename > class predicate>

CMMTree< X1, predicate >::CMMTree ( std::vector< X1 >const *const & adr )

inline

Single-argument constructor.

Parameters

adr	The address of the vector containing the input data.

If you use it then:

the tree (object of type CMMTree) is associated with specific data;
the root will not represent any of the elements of the dataset (D), that is, later you can create a forest of trees (sub-trees);
the tree_create() function can be called.

Definition at line 57 of file cmmtree.hpp.

◆ CMMTree() [3/5]

template<class X1 , template< typename > class predicate>

CMMTree< X1, predicate >::CMMTree	(	std::vector< X1 >const *const &	adr,
		typename std::vector< X1 >::const_iterator const &	pos )

inline

Two arguments constructor.

Parameters

adr	The address of the vector containing the input data.
pos	Iterator to the selected element of the input data vector.

If you use it then:

the tree (object of type CMMTree) is associated with specific data;
the root will represent selected element of the dataset (D) pointed by iterator pos;
the tree_create() function can be called.

Definition at line 72 of file cmmtree.hpp.

◆ CMMTree() [4/5]

template<class X1 , template< typename > class predicate>

CMMTree< X1, predicate >::CMMTree ( const CMMTree< X1, predicate > & )

delete

Copy constructor. Construct of copies of CMMTree object is prohibited.

◆ CMMTree() [5/5]

template<class X1 , template< typename > class predicate>

CMMTree< X1, predicate >::CMMTree ( CMMTree< X1, predicate > && other )

inlinenoexcept

Move constructor.

Parameters

other Object to be moved.

Definition at line 94 of file cmmtree.hpp.

◆ ~CMMTree()

template<class X1 , template< typename > class predicate>

CMMTree< X1, predicate >::~CMMTree ( )

inline

Destructor. The allocated memory for all nodes in the tree is released.

Definition at line 127 of file cmmtree.hpp.

Member Function Documentation

◆ all_nodes_number()

template<class X1 , template< typename > class predicate>

size_t CMMTree< X1, predicate >::all_nodes_number ( ) const

inline

This function returns the number of all nodes in the CMMTree.

Returns: size_t

Definition at line 198 of file cmmtree.hpp.

◆ brother_address()

template<class X1 , template< typename > class predicate>

node< X1 > const * CMMTree< X1, predicate >::brother_address	(	const node< X1 > *	ptr,
		size_t	i ) const

inline

This function allows you to obtain the address of the i-th brother of the firstborn node.

Parameters

ptr	Firstborn node address.
i	Brother number of the firstborn node.

Returns: const node<X1>*

Definition at line 180 of file cmmtree.cpp.

◆ create_subtrees_roots()

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::create_subtrees_roots ( std::vector< X1 > const & roots_data )

This function allows you to initialize the creation of a forest using a separate data set - different from the main input data set.

Parameters

roots_data

A vector of values represented by the roots of subtrees.

This function can only be called if the CMMTree root node is not associated with any element of the input dataset and has no children yet.

Definition at line 59 of file cmmtree.cpp.

◆ delete_nodes()

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::delete_nodes	(	std::vector< node< X1 > * > &	to_del,
		size_t	lev )

Using this function you can delete more than one node from a specified node generation at once.

NOTE:

deleting the specified node also results in the deletion of ALL its descendant nodes;
the function does not check whether the nodes selected for deletion actually belong to the same generation,
the indication of nodes from different generations will lead to a loss of control over the program;
the root node can not be deleted.

Parameters

to_del	A vector of node addresses to be deleted.
lev	Tree level: <0, ..., tree_height()>.

Definition at line 246 of file cmmtree.cpp.

◆ delete_one_node()

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::delete_one_node ( node< X1 > *& to_del )

This function deletes the node whose address is passed as an argument.

NOTE:

deleting the specified node also results in the deletion of ALL its descendant nodes;
the root node can not be deleted.

Parameters

to_del Address of the node to be deleted.

Definition at line 223 of file cmmtree.cpp.

◆ firstborn_address()

template<class X1 , template< typename > class predicate>

node< X1 > const *const & CMMTree< X1, predicate >::firstborn_address	(	size_t	i,
		size_t	j ) const

inline

The function returns the address of the j-th firstborn of the i-th generation.

Parameters

i	Tree level: <0, ..., tree_height()>.
j	Firstborn number : <0, ..., MTree[i].size() ).

Returns: node<X1> const* const&

Definition at line 188 of file cmmtree.cpp.

◆ firstborn_value()

template<class X1 , template< typename > class predicate>

X1 const & CMMTree< X1, predicate >::firstborn_value	(	size_t	i,
		size_t	j ) const

inline

A function that allows you to read the value of [i,j]-th firstborn node.

Parameters

i	Tree level: <0, ..., tree_height()>.
j	The index of the element of the i-th firstborns vector <0,... , firstborns vector size>.

Returns: Const reference to the object of X1 type.

Definition at line 190 of file cmmtree.hpp.

◆ firstborns_number()

template<class X1 , template< typename > class predicate>

size_t CMMTree< X1, predicate >::firstborns_number ( size_t i ) const

This function returns the number of firstborn nodes of one generation of the CMMTree - at the level passed by the argument (i).

Parameters

i	Tree level: <0, ..., tree_height()>.

Returns: size_t

Definition at line 87 of file cmmtree.cpp.

◆ generation_addresses() [1/2]

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::generation_addresses	(	size_t	i,
		std::vector< const node< X1 > * > &	vec ) const

inline

This function allows you to get all the addresses of the i-th generation firstborn nodes.
Firstborn nodes addresses - at the level passed by the first argument.

Parameters

i	Tree level: <0, ..., tree_height()>.
vec	Reference to the vector< const node<X1>* >.

Definition at line 122 of file cmmtree.cpp.

◆ generation_addresses() [2/2]

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::generation_addresses	(	size_t	i,
		std::vector< node< X1 > * > &	vec ) const

inline

This function allows you to get all the addresses of the first-born nodes of the i-th generation, using which you will be able to remove the selected nodes.
Firstborn nodes addresses - at the level passed by the first argument.

Parameters

i	Tree level: <0, ..., tree_height()>.
vec	Reference to the vector< node<X1>* >.

Definition at line 140 of file cmmtree.cpp.

◆ generation_size()

template<class X1 , template< typename > class predicate>

size_t CMMTree< X1, predicate >::generation_size ( size_t i ) const

This function returns the total number of nodes one generation of the CMMTree - at the level passed by the argument (i).

Parameters

i	Tree level: <0, ..., tree_height()>.

Returns: size_t

Definition at line 110 of file cmmtree.cpp.

◆ join_data() [1/2]

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::join_data ( std::vector< X1 >const *const & adr )

This function is used to connect the CMMTree object to the input data vector.

Parameters

adr	Address of the input data vector.

If you use it then:

the root will NOT represent any of the elements of the dataset (D);
using the tree_create() function, you will create a forest (a collection of subtrees).

Definition at line 6 of file cmmtree.cpp.

◆ join_data() [2/2]

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::join_data	(	std::vector< X1 >const *const &	adr,
		typename std::vector< X1 >::const_iterator const &	pos )

This function is used to connect the CMMTree object to the input data vector.

Parameters

adr	Address of the input data vector.
pos	Iterator to one of the elements of the input data vector.

If you use it then:

the root will represent selected element of the dataset (D) pointed by iterator pos;
using the tree_create() function, you will create a single tree.

Definition at line 12 of file cmmtree.cpp.

◆ leaves_addresses()

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::leaves_addresses	(	size_t	i,
		std::vector< const node< X1 > * > &	vec ) const

inline

This function allows you to get all the addresses of the i-th generation leaves.

Parameters

i	Tree level: <0, ..., tree_height()>.
vec	Reference to the vector< const node<X1>* >.

Definition at line 158 of file cmmtree.cpp.

◆ leaves_number()

template<class X1 , template< typename > class predicate>

size_t CMMTree< X1, predicate >::leaves_number ( size_t i ) const

This function returns the number of leaves one generation of the CMMTree - at the level passed by the argument (i).

Parameters

i	Tree level: <0, ..., tree_height()>.

Returns: size_t

Definition at line 94 of file cmmtree.cpp.

◆ operator=() [1/2]

template<class X1 , template< typename > class predicate>

auto CMMTree< X1, predicate >::operator= ( CMMTree< X1, predicate > && other ) -> CMMTree<X1, predicate>&

inlinenoexcept

Move assignment operator.

Parameters

other Object to be moved.

Returns: CMMTree<X1, predicate>&

Definition at line 108 of file cmmtree.hpp.

◆ operator=() [2/2]

template<class X1 , template< typename > class predicate>

CMMTree< X1, predicate > & CMMTree< X1, predicate >::operator= ( const CMMTree< X1, predicate > & )

delete

Copy assignment operator. Copying a CMMTree object using the assignment operator is not allowed.

◆ P_dataset()

template<class X1 , template< typename > class predicate>

std::vector< X1 > const *const & CMMTree< X1, predicate >::P_dataset ( ) const

inline

The function returns the address of the input data vector.

Returns: vector < X1 >const* const&

Definition at line 281 of file cmmtree.hpp.

◆ pred_value() [1/2]

template<class X1 , template< typename > class predicate>

predicate< X1 > & CMMTree< X1, predicate >::pred_value ( )

inline

A function that allows you to modify the value of a predicate object.

Returns: Reference to predicate object.

Definition at line 175 of file cmmtree.hpp.

◆ pred_value() [2/2]

template<class X1 , template< typename > class predicate>

predicate< X1 > const & CMMTree< X1, predicate >::pred_value ( ) const

inline

A function that allows you to read the value of a predicate object.

Returns: Const reference to predicate object.

Definition at line 181 of file cmmtree.hpp.

◆ tree_clear()

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::tree_clear ( )

This function clears the entire CMMTree object.

If you use it then:

the entire tree structure - the relationships between the data - is deleted;
allocated memory for all nodes except root is released;
the root will not represent any of the elements of the dataset (D), that is, later you can create a forest of trees (sub-trees);
the tree_create() function can be called.

Definition at line 270 of file cmmtree.cpp.

◆ tree_create()

template<class X1 , template< typename > class predicate>

long long CMMTree< X1, predicate >::tree_create ( )

A function that starts the process of the CMMTree construction.

Returns: long long - CMMTree construction time.

Use the function time_info(const unsigned long&, std::ostream& ) to see this time in µs and ms.

Definition at line 74 of file cmmtree.cpp.

◆ tree_height()

template<class X1 , template< typename > class predicate>

size_t CMMTree< X1, predicate >::tree_height ( ) const

inline

This function returns the CMMTree height.

Returns: size_t

Definition at line 231 of file cmmtree.hpp.

◆ tree_shape()

template<class X1 , template< typename > class predicate>

void CMMTree< X1, predicate >::tree_shape ( std::ostream & out ) const

This function allows you to represent a tree in a parametric form.

The results are passed to the stream object in CSV format. For more information on parametric description of tree shape, see the paper: https://ieeexplore.ieee.org/document/9069220

Parameters

out	Output stream object.

Definition at line 283 of file cmmtree.cpp.

Friends And Related Symbol Documentation

◆ operator<<

template<class X1 , template< typename > class predicate>

template<class T1 , template< typename > class T2>

std::ostream & operator<<	(	std::ostream &	out,
		CMMTree< T1, T2 > const &	ref )

friend

Overloaded output operator to the stream.

It allows you to look at the values of CMMTree nodes - that is, the values of the input data set (D).
These can be specific values of the input data set (D) objects or addresses of these objects - if the set (D) consists of addresses of other dynamically allocated objects.
The way the operator works depends on the values of two preprocessor directives (MAX_NODES_TO_PRINT and PRINT_ALL_PATHS) found in the main_xx.hpp file.

Parameters

out	Output stream object.
ref	CMMTree object.

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

src/hpp/cmmtree.hpp
src/cmmtree.cpp

Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ CMMTree() [1/5]

◆ CMMTree() [2/5]

◆ CMMTree() [3/5]

◆ CMMTree() [4/5]

◆ CMMTree() [5/5]

◆ ~CMMTree()

Member Function Documentation

◆ all_nodes_number()

◆ brother_address()

◆ create_subtrees_roots()

◆ delete_nodes()

◆ delete_one_node()

◆ firstborn_address()

◆ firstborn_value()

◆ firstborns_number()

◆ generation_addresses() [1/2]

◆ generation_addresses() [2/2]

◆ generation_size()

◆ join_data() [1/2]

◆ join_data() [2/2]

◆ leaves_addresses()

◆ leaves_number()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ P_dataset()

◆ pred_value() [1/2]

◆ pred_value() [2/2]

◆ tree_clear()

◆ tree_create()

◆ tree_height()

◆ tree_shape()

Friends And Related Symbol Documentation

◆ operator<<