#include <tree.h>

Classes
class	ChainView

class	ChainView< Const >

class	ChildView

class	DescendantView

class	Iterator

class	RootView

Public Types
enum class	SearchType { kDepthFirstSearch , kBreadthFirstSearch }

using	const_chain_view = ChainView< true >

using	chain_view = ChainView< false >

using	const_descendant_view = DescendantView< true >

using	descendant_view = DescendantView< false >

using	const_child_view = ChildView< true >

using	child_view = ChildView< false >

using	const_root_view = RootView< true >

using	root_view = RootView< false >

Public Member Functions
bool	empty () const

size_t	size () const

const std::unordered_map< Key, T > &	nodes () const

const std::unordered_map< Key, T > &	values () const

const_root_view	roots () const

root_view	roots ()

const T &	at (const Key &id) const

T &	at (const Key &id)

chain_view	ancestors (const Key &id)

const_chain_view	ancestors (const Key &id) const

descendant_view	descendants (const Key &id, SearchType search_type=SearchType::kBreadthFirstSearch, size_t max_depth=std::numeric_limits< size_t >::max())

const_descendant_view	descendants (const Key &id, SearchType search_type=SearchType::kBreadthFirstSearch, size_t max_depth=std::numeric_limits< size_t >::max()) const

descendant_view	nodes (SearchType search_type, size_t max_depth=std::numeric_limits< size_t >::max())

const_descendant_view	nodes (SearchType search_type, size_t max_depth=std::numeric_limits< size_t >::max()) const

bool	contains (const Key &id) const

size_t	depth (const Key &id) const

void	insert (const Key &id, const T &value)

void	insert (const Key &id, T &&value)

void	insert_child (const Key &id_parent, const Key &id, const T &value)

void	insert_child (const Key &id_parent, const Key &id, T &&value)

const std::optional< Key > &	parent (const Key &id) const

child_view	children (const Key &id)

const_child_view	children (const Key &id) const

void	clear_parent (const Key &id)

void	clear_children (const Key &id)

void	set_parent (const Key &id, const Key &id_parent)

void	add_child (const Key &id, const Key &id_child)

bool	is_ancestor (const Key &id_ancestor, const Key &id) const

bool	is_descendant (const Key &id_descendant, const Key &id) const

void	printf (std::ostream &os, const std::function< std::string(const Key &key, const T &val)> &StringifyValue) const

Protected Attributes
std::unordered_map< Key, T >	nodes_

std::unordered_map< Key, std::optional< Key > >	parents_

std::unordered_map< Key, std::vector< Key > >	children_

Friends
std::ostream &	operator<< (std::ostream &os, const Tree< Key, T > &tree)

Detailed Description

template<typename Key, typename T>
class ctrl_utils::Tree< Key, T >

Tree represented as a flat map of keys to nodes and a map from keys to parent keys.

Inserting and accessing nodes is O(1).

Removing nodes is O(M), where M is the number of the removed node's siblings.

Iterating over ancestors is O(D), where D is the number of ancestors of the given node.

Iterating over descendants is O(N), where N is the number of descendants of the given node.

Member Function Documentation

◆ add_child()

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::add_child	(	const Key &	id,
		const Key &	id_child
	)

inline

Adds a child to the given node and clears the child's previous parent.

This function is O(M), where M is the number of children of the given node.

◆ ancestors() [1/2]

template<typename Key , typename T >

chain_view ctrl_utils::Tree< Key, T >::ancestors ( const Key & id )

inline

Returns an iterator over all the ancestors of the given node, from the given node (inclusive) up to the root.

Dereferencing the iterator returns a (key, value) pair.

Tree<int, char> tree;
tree.insert(0, 'a');
tree.insert_child(0, 1, 'b');
tree.insert_child(0, 2, 'c');
for (const std::pair<int, char>& key_val : tree.ancestors(2)) {
  std::cout << key_val.first << ": " << key_val.second << std::endl;
}
 
// Expected output:
// >>> 2: c
// >>> 0: a

◆ ancestors() [2/2]

template<typename Key , typename T >

const_chain_view ctrl_utils::Tree< Key, T >::ancestors ( const Key & id ) const

inline

Returns a const iterator over all the ancestors of the given node, from the given node (inclusive) up to the root.

See also: ancestors(const Key&)

◆ at()

template<typename Key , typename T >

const T& ctrl_utils::Tree< Key, T >::at ( const Key & id ) const

inline

Returns the node at the given key.

Access is O(1).

◆ children()

template<typename Key , typename T >

child_view ctrl_utils::Tree< Key, T >::children ( const Key & id )

inline

Returns an iterator over the children of the given node.

Dereferencing the iterator returns a (key, value) pair.

Tree<int, char> tree;
tree.insert(0, 'a');
tree.insert_child(0, 1, 'b');
tree.insert_child(0, 2, 'c');
for (const std::pair<int, char>& key_val : tree.children(0)) {
  std::cout << key_val.first << ": " << key_val.second << std::endl;
}
 
// Expected output:
// >>> 1: b
// >>> 2: c

Lookup is O(1).

◆ clear_children()

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::clear_children ( const Key & id )

inline

Clears the children of the given node.

This function is O(M), where M is the number of children of the given node.

◆ clear_parent()

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::clear_parent ( const Key & id )

inline

Clears the parent of the given node.

This function is O(M), where M is the number of siblings of the given node.

◆ contains()

template<typename Key , typename T >

bool ctrl_utils::Tree< Key, T >::contains ( const Key & id ) const

inline

Returns whether the tree contains a node at the given key.

Returns in O(1) time.

◆ depth()

template<typename Key , typename T >

size_t ctrl_utils::Tree< Key, T >::depth ( const Key & id ) const

inline

Returns the depth of the node in the tree, where 0 is the depth of a root node.

Returns in O(d) time, where d is the depth of the tree.

◆ descendants() [1/2]

template<typename Key , typename T >

descendant_view ctrl_utils::Tree< Key, T >::descendants	(	const Key &	id,
		SearchType	search_type = `SearchType::kBreadthFirstSearch`,
		size_t	max_depth = `std::numeric_limits<size_t>::max()`
	)

inline

Returns an iterator over all the descendants of the given node, from the given node (inclusive) to all the leaves found with depth first search.

Dereferencing the iterator returns a (key, value) pair.

Tree<int, char> tree;
tree.insert(0, 'a');
tree.insert_child(0, 1, 'b');
tree.insert_child(0, 2, 'c');
for (const std::pair<int, char>& key_val : tree.descendants(0)) {
  std::cout << key_val.first << ": " << key_val.second << std::endl;
}
 
// Expected output:
// >>> 0: a
// >>> 1: b
// >>> 2: c

Parameters

id	Key to start descendants search.
search_type	Whether to use breadth first or depth first search.
max_depth	Maximum depth to search.

◆ descendants() [2/2]

template<typename Key , typename T >

const_descendant_view ctrl_utils::Tree< Key, T >::descendants	(	const Key &	id,
		SearchType	search_type = `SearchType::kBreadthFirstSearch`,
		size_t	max_depth = `std::numeric_limits<size_t>::max()`
	)		const

inline

Returns a const iterator over all the ancestors of the given node, from the given node (inclusive) up to the root.

See also: descendants(const Key&)

◆ empty()

template<typename Key , typename T >

bool ctrl_utils::Tree< Key, T >::empty ( ) const

inline

Returns whether the tree is empty.

◆ insert() [1/2]

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::insert	(	const Key &	id,
		const T &	value
	)

inline

Inserts a new node without a parent.

Insertion is O(1).

◆ insert() [2/2]

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::insert	(	const Key &	id,
		T &&	value
	)

inline

Inserts a new node without a parent.

See also: insert(const Key&, const T&)

◆ insert_child() [1/2]

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::insert_child	(	const Key &	id_parent,
		const Key &	id,
		const T &	value
	)

inline

Inserts a new node with the given parent.

Throws an error if a node with the same id already exists.

Insertion is O(1).

◆ insert_child() [2/2]

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::insert_child	(	const Key &	id_parent,
		const Key &	id,
		T &&	value
	)

inline

Inserts a new node with the given parent.

See also: insert_child(const Key&, const Key&, const T&)

◆ is_ancestor()

template<typename Key , typename T >

bool ctrl_utils::Tree< Key, T >::is_ancestor	(	const Key &	id_ancestor,
		const Key &	id
	)		const

inline

Checks whether id_ancestor is an ancestor of id.

Nodes are ancestors of themselves.

This function is O(D), where D is the depth of the given node.

◆ is_descendant()

template<typename Key , typename T >

bool ctrl_utils::Tree< Key, T >::is_descendant	(	const Key &	id_descendant,
		const Key &	id
	)		const

inline

Checks whether id_descendant is a descendant of id.

Nodes are descendants of themselves.

This function is O(D), where D is the depth of the descendant node.

◆ nodes() [1/3]

template<typename Key , typename T >

const std::unordered_map<Key, T>& ctrl_utils::Tree< Key, T >::nodes ( ) const

inline

Returns a flattened map of all the nodes in the tree.

◆ nodes() [2/3]

template<typename Key , typename T >

descendant_view ctrl_utils::Tree< Key, T >::nodes	(	SearchType	search_type,
		size_t	max_depth = `std::numeric_limits<size_t>::max()`
	)

inline

Returns an iterator over all the nodes of the tree, in order of depth/breadth first search.

Parameters

search_type	Whether to use breadth first or depth first search.
max_depth	Maximum depth to search.

See also: descendants(const Key&)

◆ nodes() [3/3]

template<typename Key , typename T >

const_descendant_view ctrl_utils::Tree< Key, T >::nodes	(	SearchType	search_type,
		size_t	max_depth = `std::numeric_limits<size_t>::max()`
	)		const

inline

Returns a const iterator over all the nodes of the tree, in order of depth/breadth first search.

Parameters

id	Key to start descendants search.
bfs	Whether to use breadth first or depth first search.
max_depth	Maximum depth to search.

See also: descendants(const Key&)

◆ parent()

template<typename Key , typename T >

const std::optional<Key>& ctrl_utils::Tree< Key, T >::parent ( const Key & id ) const

inline

Returns the parent of the given node (the root node will have an empty optional).

Lookup is O(1).

◆ printf()

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::printf	(	std::ostream &	os,
		const std::function< std::string(const Key &key, const T &val)> &	StringifyValue
	)		const

inline

Prints the tree with tab-indented nodes using depth first search.

Parameters

os	Stream to print to.
StringifyValue	Functions that converts the node value to a string.

◆ roots()

template<typename Key , typename T >

const_root_view ctrl_utils::Tree< Key, T >::roots ( ) const

inline

Returns the roots (nodes without parents).

Search is O(N), where N is the number of nodes in the tree.

◆ set_parent()

template<typename Key , typename T >

void ctrl_utils::Tree< Key, T >::set_parent	(	const Key &	id,
		const Key &	id_parent
	)

inline

Sets the parent of the given node and clears any previous parent.

This function is O(M), where M is the number of siblings of the given node.

◆ size()

template<typename Key , typename T >

size_t ctrl_utils::Tree< Key, T >::size ( ) const

inline

Returns the number of nodes in the tree.

Friends And Related Function Documentation

◆ operator<<

template<typename Key , typename T >

std::ostream& operator<<	(	std::ostream &	os,
		const Tree< Key, T > &	tree
	)

friend

Prints the tree with tab-indented nodes using depth first search.

Member Data Documentation

◆ children_

template<typename Key , typename T >

std::unordered_map<Key, std::vector<Key> > ctrl_utils::Tree< Key, T >::children_

protected

Mapping from each node to its children.

◆ nodes_

template<typename Key , typename T >

std::unordered_map<Key, T> ctrl_utils::Tree< Key, T >::nodes_

protected

Flat map of all the nodes in the tree.

◆ parents_

template<typename Key , typename T >

std::unordered_map<Key, std::optional<Key> > ctrl_utils::Tree< Key, T >::parents_

protected

Mapping from each node to its (optional) parent.

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

/home/runner/work/ctrl-utils/ctrl-utils/include/ctrl_utils/tree.h

Classes

Public Types

Public Member Functions

Protected Attributes

Friends

Detailed Description

template<typename Key, typename T> class ctrl_utils::Tree< Key, T >

Member Function Documentation

◆ add_child()

◆ ancestors() [1/2]

◆ ancestors() [2/2]

◆ at()

◆ children()

◆ clear_children()

◆ clear_parent()

◆ contains()

◆ depth()

◆ descendants() [1/2]

◆ descendants() [2/2]

◆ empty()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_child() [1/2]

◆ insert_child() [2/2]

◆ is_ancestor()

◆ is_descendant()

◆ nodes() [1/3]

◆ nodes() [2/3]

◆ nodes() [3/3]

◆ parent()

◆ printf()

◆ roots()

◆ set_parent()

◆ size()

Friends And Related Function Documentation

◆ operator<<

Member Data Documentation

◆ children_

◆ nodes_

◆ parents_

template<typename Key, typename T>
class ctrl_utils::Tree< Key, T >