#include <tree.hh>

Inheritance diagram for tree< T, tree_node_allocator >:

Collaboration diagram for tree< T, tree_node_allocator >:

Classes
class	breadth_first_queued_iterator
	Breadth-first iterator, using a queue. More...

class	fixed_depth_iterator
	Iterator which traverses only the nodes at a given depth from the root. More...

class	iterator_base
	Base class for iterators, only pointers stored, no traversal logic. More...

class	iterator_base_less
	Comparator class for iterators (compares pointer values; why doesn't this work automatically?) More...

class	leaf_iterator
	Iterator which traverses only the leaves. More...

class	post_order_iterator
	Depth-first iterator, first accessing the children, then the node itself. More...

class	pre_order_iterator
	Depth-first iterator, first accessing the node, then its children. More...

class	sibling_iterator
	Iterator which traverses only the nodes which are siblings of each other. More...

Public Types
typedef T	value_type
	Value of the data stored at a node. More...

typedef pre_order_iterator	iterator
	The default iterator types throughout the tree class. More...

typedef breadth_first_queued_iterator	breadth_first_iterator

Public Member Functions
	tree ()

	tree (const T &)

	tree (const iterator_base &)

	tree (const tree< T, tree_node_allocator > &)

	~tree ()

void	operator= (const tree< T, tree_node_allocator > &)

pre_order_iterator	begin () const
	Return iterator to the beginning of the tree. More...

pre_order_iterator	end () const
	Return iterator to the end of the tree. More...

post_order_iterator	begin_post () const
	Return post-order iterator to the beginning of the tree. More...

post_order_iterator	end_post () const
	Return post-order end iterator of the tree. More...

fixed_depth_iterator	begin_fixed (const iterator_base &, unsigned int) const
	Return fixed-depth iterator to the first node at a given depth from the given iterator. More...

fixed_depth_iterator	end_fixed (const iterator_base &, unsigned int) const
	Return fixed-depth end iterator. More...

breadth_first_queued_iterator	begin_breadth_first () const
	Return breadth-first iterator to the first node at a given depth. More...

breadth_first_queued_iterator	end_breadth_first () const
	Return breadth-first end iterator. More...

sibling_iterator	begin (const iterator_base &) const
	Return sibling iterator to the first child of given node. More...

sibling_iterator	end (const iterator_base &) const
	Return sibling end iterator for children of given node. More...

leaf_iterator	begin_leaf () const
	Return leaf iterator to the first leaf of the tree. More...

leaf_iterator	end_leaf () const
	Return leaf end iterator for entire tree. More...

leaf_iterator	begin_leaf (const iterator_base &top) const
	Return leaf iterator to the first leaf of the subtree at the given node. More...

leaf_iterator	end_leaf (const iterator_base &top) const
	Return leaf end iterator for the subtree at the given node. More...

template<typename iter >
iter	previous_sibling (iter) const
	Return iterator to the previous sibling of a node. More...

template<typename iter >
iter	next_sibling (iter) const
	Return iterator to the next sibling of a node. More...

template<typename iter >
iter	next_at_same_depth (iter) const
	Return iterator to the next node at a given depth. More...

void	clear ()
	Erase all nodes of the tree. More...

template<typename iter >
iter	erase (iter)
	Erase element at position pointed to by iterator, return incremented iterator. More...

void	erase_children (const iterator_base &)
	Erase all children of the node pointed to by iterator. More...

template<typename iter >
iter	append_child (iter position)
	Insert empty node as last/first child of node pointed to by position. More...

template<typename iter >
iter	prepend_child (iter position)

template<typename iter >
iter	append_child (iter position, const T &x)
	Insert node as last/first child of node pointed to by position. More...

template<typename iter >
iter	prepend_child (iter position, const T &x)

template<typename iter >
iter	append_child (iter position, iter other_position)
	Append the node (plus its children) at other_position as last/first child of position. More...

template<typename iter >
iter	prepend_child (iter position, iter other_position)

template<typename iter >
iter	append_children (iter position, sibling_iterator from, sibling_iterator to)
	Append the nodes in the from-to range (plus their children) as last/first children of position. More...

template<typename iter >
iter	prepend_children (iter position, sibling_iterator from, sibling_iterator to)

pre_order_iterator	set_head (const T &x)
	Short-hand to insert topmost node in otherwise empty tree. More...

template<typename iter >
iter	insert (iter position, const T &x)
	Insert node as previous sibling of node pointed to by position. More...

sibling_iterator	insert (sibling_iterator position, const T &x)
	Specialisation of previous member. More...

template<typename iter >
iter	insert_subtree (iter position, const iterator_base &subtree)
	Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position. More...

template<typename iter >
iter	insert_after (iter position, const T &x)
	Insert node as next sibling of node pointed to by position. More...

template<typename iter >
iter	insert_subtree_after (iter position, const iterator_base &subtree)
	Insert node (with children) pointed to by subtree as next sibling of node pointed to by position. More...

template<typename iter >
iter	replace (iter position, const T &x)
	Replace node at 'position' with other node (keeping same children); 'position' becomes invalid. More...

template<typename iter >
iter	replace (iter position, const iterator_base &from)
	Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above. More...

sibling_iterator	replace (sibling_iterator orig_begin, sibling_iterator orig_end, sibling_iterator new_begin, sibling_iterator new_end)
	Replace string of siblings (plus their children) with copy of a new string (with children); see above. More...

template<typename iter >
iter	flatten (iter position)
	Move all children of node at 'position' to be siblings, returns position. More...

template<typename iter >
iter	reparent (iter position, sibling_iterator begin, sibling_iterator end)
	Move nodes in range to be children of 'position'. More...

template<typename iter >
iter	reparent (iter position, iter from)
	Move all child nodes of 'from' to be children of 'position'. More...

template<typename iter >
iter	wrap (iter position, const T &x)
	Replace node with a new node, making the old node a child of the new node. More...

template<typename iter >
iter	move_after (iter target, iter source)
	Move 'source' node (plus its children) to become the next sibling of 'target'. More...

template<typename iter >
iter	move_before (iter target, iter source)
	Move 'source' node (plus its children) to become the previous sibling of 'target'. More...

sibling_iterator	move_before (sibling_iterator target, sibling_iterator source)

template<typename iter >
iter	move_ontop (iter target, iter source)
	Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target'). More...

void	merge (sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, bool duplicate_leaves=false)
	Merge with other tree, creating new branches and leaves only if they are not already present. More...

void	sort (sibling_iterator from, sibling_iterator to, bool deep=false)
	Sort (std::sort only moves values of nodes, this one moves children as well). More...

template<class StrictWeakOrdering >
void	sort (sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)

template<typename iter >
bool	equal (const iter &one, const iter &two, const iter &three) const
	Compare two ranges of nodes (compares nodes as well as tree structure). More...

template<typename iter , class BinaryPredicate >
bool	equal (const iter &one, const iter &two, const iter &three, BinaryPredicate) const

template<typename iter >
bool	equal_subtree (const iter &one, const iter &two) const

template<typename iter , class BinaryPredicate >
bool	equal_subtree (const iter &one, const iter &two, BinaryPredicate) const

tree	subtree (sibling_iterator from, sibling_iterator to) const
	Extract a new tree formed by the range of siblings plus all their children. More...

void	subtree (tree &, sibling_iterator from, sibling_iterator to) const

void	swap (sibling_iterator it)
	Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present). More...

void	swap (iterator, iterator)
	Exchange two nodes (plus subtrees) More...

size_t	size () const
	Count the total number of nodes. More...

size_t	size (const iterator_base &) const
	Count the total number of nodes below the indicated node (plus one). More...

bool	empty () const
	Check if tree is empty. More...

int	max_depth () const
	Determine the maximal depth of the tree. An empty tree has max_depth=-1. More...

int	max_depth (const iterator_base &) const
	Determine the maximal depth of the tree with top node at the given position. More...

unsigned int	number_of_siblings (const iterator_base &) const
	Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1. More...

bool	is_in_subtree (const iterator_base &position, const iterator_base &begin, const iterator_base &end) const
	Determine whether node at position is in the subtrees with root in the range. More...

bool	is_valid (const iterator_base &) const
	Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node. More...

unsigned int	index (sibling_iterator it) const
	Determine the index of a node in the range of siblings to which it belongs. More...

sibling_iterator	sibling (const iterator_base &position, unsigned int)
	Return iterator to the sibling indicated by index. More...

Static Public Member Functions
template<typename iter >
static iter	parent (iter)
	Return iterator to the parent of a node. More...

static int	depth (const iterator_base &)
	Compute the depth to the root or to a fixed other iterator. More...

static int	depth (const iterator_base &, const iterator_base &)

static unsigned int	number_of_children (const iterator_base &)
	Count the number of children of node at position. More...

static sibling_iterator	child (const iterator_base &position, unsigned int)
	Inverse of 'index': return the n-th child of the node at position. More...

Public Attributes
tree_node *	head

tree_node *	feet

Protected Types
typedef tree_node_< T >	tree_node

Member Typedef Documentation

◆ breadth_first_iterator

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

typedef breadth_first_queued_iterator tree< T, tree_node_allocator >::breadth_first_iterator

◆ iterator

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

typedef pre_order_iterator tree< T, tree_node_allocator >::iterator

The default iterator types throughout the tree class.

◆ tree_node

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

typedef tree_node_<T> tree< T, tree_node_allocator >::tree_node

protected

◆ value_type

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

typedef T tree< T, tree_node_allocator >::value_type

Value of the data stored at a node.

Constructor & Destructor Documentation

◆ tree() [1/4]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::tree ( )

◆ tree() [2/4]

template<class T, class tree_node_allocator >

tree< T, tree_node_allocator >::tree ( const T & x )

◆ tree() [3/4]

template<class T, class tree_node_allocator >

tree< T, tree_node_allocator >::tree ( const iterator_base & other )

◆ tree() [4/4]

template<class T, class tree_node_allocator>

tree< T, tree_node_allocator >::tree ( const tree< T, tree_node_allocator > & other )

◆ ~tree()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::~tree ( )

Member Function Documentation

◆ append_child() [1/3]

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::append_child ( iter position )

Insert empty node as last/first child of node pointed to by position.

Referenced by FilterTree::addFilter(), FilterTree::addFilterTree(), FilterTree::copyFilter(), FilterTree::loadXML(), and FilterTree::reparentFilter().

Here is the caller graph for this function:

◆ append_child() [2/3]

template<class T, class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::append_child	(	iter	position,
		const T &	x
	)

Insert node as last/first child of node pointed to by position.

◆ append_child() [3/3]

template<class T, class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::append_child	(	iter	position,
		iter	other_position
	)

Append the node (plus its children) at other_position as last/first child of position.

◆ append_children()

template<class T , class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::append_children	(	iter	position,
		sibling_iterator	from,
		sibling_iterator	to
	)

Append the nodes in the from-to range (plus their children) as last/first children of position.

◆ begin() [1/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::begin ( ) const

inline

Return iterator to the beginning of the tree.

Referenced by FilterTree::addFilter(), FilterTree::addFilterTree(), FilterTreeAnalyse::analyse(), FilterTree::cacheCount(), FilterTree::clear(), FilterTree::clearCache(), FilterTree::clearCacheByType(), FilterTree::cloneSubtree(), FilterTree::contains(), FilterTree::copyFilter(), FilterTree::depth(), FilterTree::depthBegin(), filterAffectedByComposition(), filterAltersComposition(), FilterTree::FilterTree(), FilterTree::getAccumulatedPropagationMaps(), FilterTree::getFiltersByType(), FilterTree::hasHazardousContents(), FilterTree::hasStateOverrides(), FilterTree::hasUpdates(), FilterTree::initFilterTree(), FilterTree::loadXML(), FilterTree::modifyRangeFiles(), FilterTree::operator=(), FilterTree::purgeCache(), FilterTree::refreshFilterTree(), FilterTree::removeSubtree(), FilterTree::reparentFilter(), FilterTree::respliceFilter(), FilterTree::saveXML(), FilterTree::serialiseToStringPaths(), FilterTree::setFilterProperty(), FilterTree::stripHazardousContents(), tree< Filter *>::subtree(), and tree< Filter *>::tree().

Here is the caller graph for this function:

◆ begin() [2/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::begin ( const iterator_base & pos ) const

Return sibling iterator to the first child of given node.

◆ begin_breadth_first()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::begin_breadth_first ( ) const

Return breadth-first iterator to the first node at a given depth.

Referenced by FilterTree::getAccumulatedPropagationMaps().

Here is the caller graph for this function:

◆ begin_fixed()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::fixed_depth_iterator tree< T, tree_node_allocator >::begin_fixed	(	const iterator_base &	pos,
		unsigned int	dp
	)		const

Return fixed-depth iterator to the first node at a given depth from the given iterator.

◆ begin_leaf() [1/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::begin_leaf ( ) const

Return leaf iterator to the first leaf of the tree.

Referenced by FilterTree::getAccumulatedPropagationMaps(), and FilterTree::refreshFilterTree().

Here is the caller graph for this function:

◆ begin_leaf() [2/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::begin_leaf ( const iterator_base & top ) const

Return leaf iterator to the first leaf of the subtree at the given node.

◆ begin_post()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::begin_post ( ) const

Return post-order iterator to the beginning of the tree.

◆ child()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::child	(	const iterator_base &	position,
		unsigned int	num
	)

static

Inverse of 'index': return the n-th child of the node at position.

◆ clear()

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::clear ( )

Erase all nodes of the tree.

Referenced by FilterTree::addFilterTree(), and FilterTree::clear().

Here is the caller graph for this function:

◆ depth() [1/2]

template<class T , class tree_node_allocator >

int tree< T, tree_node_allocator >::depth ( const iterator_base & it )

static

Compute the depth to the root or to a fixed other iterator.

Referenced by FilterTreeAnalyse::analyse(), FilterTree::clearCache(), FilterTree::depth(), filterAffectedByComposition(), FilterTree::getAccumulatedPropagationMaps(), FilterTree::initFilterTree(), FilterTree::refreshFilterTree(), FilterTree::removeSubtree(), FilterTree::reparentFilter(), FilterTree::saveXML(), FilterTree::setFilterProperty(), and FilterTree::stripHazardousContents().

Here is the caller graph for this function:

◆ depth() [2/2]

template<class T , class tree_node_allocator >

int tree< T, tree_node_allocator >::depth	(	const iterator_base &	it,
		const iterator_base &	root
	)

static

◆ empty()

template<class T , class tree_node_allocator >

bool tree< T, tree_node_allocator >::empty ( ) const

Check if tree is empty.

Referenced by FilterTree::addFilter(), FilterTree::addFilterTree(), and FilterTree::loadXML().

Here is the caller graph for this function:

◆ end() [1/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::end ( ) const

inline

Return iterator to the end of the tree.

Referenced by FilterTree::addFilter(), FilterTree::addFilterTree(), FilterTreeAnalyse::analyse(), FilterTree::cacheCount(), FilterTree::clear(), FilterTree::clearCache(), FilterTree::clearCacheByType(), FilterTree::cloneSubtree(), FilterTree::contains(), FilterTree::copyFilter(), FilterTree::depth(), FilterTree::depthEnd(), filterAffectedByComposition(), filterAltersComposition(), FilterTree::FilterTree(), FilterTree::getAccumulatedPropagationMaps(), FilterTree::getFiltersByType(), FilterTree::hasHazardousContents(), FilterTree::hasStateOverrides(), FilterTree::hasUpdates(), FilterTree::initFilterTree(), FilterTree::modifyRangeFiles(), FilterTree::operator=(), FilterTree::purgeCache(), FilterTree::refreshFilterTree(), FilterTree::removeSubtree(), FilterTree::reparentFilter(), FilterTree::respliceFilter(), FilterTree::saveXML(), FilterTree::serialiseToStringPaths(), FilterTree::setFilterProperty(), FilterTree::stripHazardousContents(), tree< Filter *>::subtree(), and tree< Filter *>::tree().

Here is the caller graph for this function:

◆ end() [2/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::end ( const iterator_base & pos ) const

Return sibling end iterator for children of given node.

◆ end_breadth_first()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::breadth_first_queued_iterator tree< T, tree_node_allocator >::end_breadth_first ( ) const

Return breadth-first end iterator.

Referenced by FilterTree::getAccumulatedPropagationMaps().

Here is the caller graph for this function:

◆ end_fixed()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::fixed_depth_iterator tree< T, tree_node_allocator >::end_fixed	(	const iterator_base &	pos,
		unsigned int	dp
	)		const

Return fixed-depth end iterator.

◆ end_leaf() [1/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::end_leaf ( ) const

Return leaf end iterator for entire tree.

Referenced by FilterTree::getAccumulatedPropagationMaps(), and FilterTree::refreshFilterTree().

Here is the caller graph for this function:

◆ end_leaf() [2/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::leaf_iterator tree< T, tree_node_allocator >::end_leaf ( const iterator_base & top ) const

Return leaf end iterator for the subtree at the given node.

◆ end_post()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::post_order_iterator tree< T, tree_node_allocator >::end_post ( ) const

Return post-order end iterator of the tree.

◆ equal() [1/2]

template<class T , class tree_node_allocator >

template<typename iter >

bool tree< T, tree_node_allocator >::equal	(	const iter &	one,
		const iter &	two,
		const iter &	three
	)		const

Compare two ranges of nodes (compares nodes as well as tree structure).

◆ equal() [2/2]

template<class T , class tree_node_allocator >

template<typename iter , class BinaryPredicate >

bool tree< T, tree_node_allocator >::equal	(	const iter &	one,
		const iter &	two,
		const iter &	three,
		BinaryPredicate	fun
	)		const

◆ equal_subtree() [1/2]

template<class T , class tree_node_allocator >

template<typename iter >

bool tree< T, tree_node_allocator >::equal_subtree	(	const iter &	one,
		const iter &	two
	)		const

◆ equal_subtree() [2/2]

template<class T , class tree_node_allocator >

template<typename iter , class BinaryPredicate >

bool tree< T, tree_node_allocator >::equal_subtree	(	const iter &	one,
		const iter &	two,
		BinaryPredicate	fun
	)		const

◆ erase()

template<class T , class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::erase ( iter it )

Erase element at position pointed to by iterator, return incremented iterator.

Referenced by FilterTree::addFilterTree(), FilterTree::removeSubtree(), and FilterTree::reparentFilter().

Here is the caller graph for this function:

◆ erase_children()

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::erase_children ( const iterator_base & it )

Erase all children of the node pointed to by iterator.

Referenced by FilterTree::removeSubtree().

Here is the caller graph for this function:

◆ flatten()

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::flatten ( iter position )

Move all children of node at 'position' to be siblings, returns position.

◆ index()

template<class T , class tree_node_allocator >

unsigned int tree< T, tree_node_allocator >::index ( sibling_iterator it ) const

Determine the index of a node in the range of siblings to which it belongs.

◆ insert() [1/2]

template<class T, class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::insert	(	iter	position,
		const T &	x
	)

Insert node as previous sibling of node pointed to by position.

Referenced by FilterTree::addFilter(), FilterTree::cloneSubtree(), FilterTree::copyFilter(), and FilterTree::loadXML().

Here is the caller graph for this function:

◆ insert() [2/2]

template<class T, class tree_node_allocator >

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::insert	(	sibling_iterator	position,
		const T &	x
	)

Specialisation of previous member.

◆ insert_after()

template<class T, class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::insert_after	(	iter	position,
		const T &	x
	)

Insert node as next sibling of node pointed to by position.

Referenced by FilterTree::addFilter(), FilterTree::copyFilter(), and FilterTree::reparentFilter().

Here is the caller graph for this function:

◆ insert_subtree()

template<class T , class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::insert_subtree	(	iter	position,
		const iterator_base &	subtree
	)

Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.

Referenced by FilterTree::addFilterTree().

Here is the caller graph for this function:

◆ insert_subtree_after()

template<class T , class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::insert_subtree_after	(	iter	position,
		const iterator_base &	subtree
	)

Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.

Referenced by FilterTree::addFilterTree().

Here is the caller graph for this function:

◆ is_in_subtree()

template<class T , class tree_node_allocator >

bool tree< T, tree_node_allocator >::is_in_subtree	(	const iterator_base &	position,
		const iterator_base &	begin,
		const iterator_base &	end
	)		const

Determine whether node at position is in the subtrees with root in the range.

◆ is_valid()

template<class T , class tree_node_allocator >

bool tree< T, tree_node_allocator >::is_valid ( const iterator_base & it ) const

Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.

Referenced by FilterTree::getAccumulatedPropagationMaps().

Here is the caller graph for this function:

◆ max_depth() [1/2]

template<class T , class tree_node_allocator >

int tree< T, tree_node_allocator >::max_depth ( ) const

Determine the maximal depth of the tree. An empty tree has max_depth=-1.

Referenced by FilterTree::getAccumulatedPropagationMaps(), and FilterTree::maxDepth().

Here is the caller graph for this function:

◆ max_depth() [2/2]

template<class T , class tree_node_allocator >

int tree< T, tree_node_allocator >::max_depth ( const iterator_base & pos ) const

Determine the maximal depth of the tree with top node at the given position.

◆ merge()

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::merge	(	sibling_iterator	to1,
		sibling_iterator	to2,
		sibling_iterator	from1,
		sibling_iterator	from2,
		bool	duplicate_leaves = `false`
	)

Merge with other tree, creating new branches and leaves only if they are not already present.

◆ move_after()

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::move_after	(	iter	target,
		iter	source
	)

Move 'source' node (plus its children) to become the next sibling of 'target'.

◆ move_before() [1/2]

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::move_before	(	iter	target,
		iter	source
	)

Move 'source' node (plus its children) to become the previous sibling of 'target'.

◆ move_before() [2/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::move_before	(	sibling_iterator	target,
		sibling_iterator	source
	)

◆ move_ontop()

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::move_ontop	(	iter	target,
		iter	source
	)

Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').

◆ next_at_same_depth()

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::next_at_same_depth ( iter position ) const

Return iterator to the next node at a given depth.

◆ next_sibling()

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::next_sibling ( iter position ) const

Return iterator to the next sibling of a node.

◆ number_of_children()

template<class T , class tree_node_allocator >

unsigned int tree< T, tree_node_allocator >::number_of_children ( const iterator_base & it )

static

Count the number of children of node at position.

◆ number_of_siblings()

template<class T , class tree_node_allocator >

unsigned int tree< T, tree_node_allocator >::number_of_siblings ( const iterator_base & it ) const

Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1.

◆ operator=()

template<class T, class tree_node_allocator>

void tree< T, tree_node_allocator >::operator= ( const tree< T, tree_node_allocator > & other )

◆ parent()

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::parent ( iter position )

static

Return iterator to the parent of a node.

Referenced by FilterTreeAnalyse::analyse(), FilterTree::getAccumulatedPropagationMaps(), FilterTree::respliceFilter(), FilterTree::stripHazardousContents(), and tree< Filter *>::~tree().

Here is the caller graph for this function:

◆ prepend_child() [1/3]

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::prepend_child ( iter position )

◆ prepend_child() [2/3]

template<class T, class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::prepend_child	(	iter	position,
		const T &	x
	)

◆ prepend_child() [3/3]

template<class T, class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::prepend_child	(	iter	position,
		iter	other_position
	)

◆ prepend_children()

template<class T , class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::prepend_children	(	iter	position,
		sibling_iterator	from,
		sibling_iterator	to
	)

◆ previous_sibling()

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::previous_sibling ( iter position ) const

Return iterator to the previous sibling of a node.

◆ reparent() [1/2]

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::reparent	(	iter	position,
		sibling_iterator	begin,
		sibling_iterator	end
	)

Move nodes in range to be children of 'position'.

◆ reparent() [2/2]

template<class T , class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::reparent	(	iter	position,
		iter	from
	)

Move all child nodes of 'from' to be children of 'position'.

◆ replace() [1/3]

template<class T, class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::replace	(	iter	position,
		const T &	x
	)

Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.

Referenced by FilterTree::cloneSubtree(), FilterTree::copyFilter(), FilterTree::reparentFilter(), and tree< Filter *>::subtree().

Here is the caller graph for this function:

◆ replace() [2/3]

template<class T, class tree_node_allocator >

template<class iter >

iter tree< T, tree_node_allocator >::replace	(	iter	position,
		const iterator_base &	from
	)

Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.

◆ replace() [3/3]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::replace	(	sibling_iterator	orig_begin,
		sibling_iterator	orig_end,
		sibling_iterator	new_begin,
		sibling_iterator	new_end
	)

Replace string of siblings (plus their children) with copy of a new string (with children); see above.

◆ set_head()

template<class T, class tree_node_allocator >

tree< T, tree_node_allocator >::pre_order_iterator tree< T, tree_node_allocator >::set_head ( const T & x )

Short-hand to insert topmost node in otherwise empty tree.

Referenced by tree< Filter *>::subtree().

Here is the caller graph for this function:

◆ sibling()

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator >::sibling_iterator tree< T, tree_node_allocator >::sibling	(	const iterator_base &	position,
		unsigned int	num
	)

Return iterator to the sibling indicated by index.

◆ size() [1/2]

template<class T , class tree_node_allocator >

size_t tree< T, tree_node_allocator >::size ( ) const

Count the total number of nodes.

Referenced by FilterTree::cloneSubtree(), FilterTree::getAccumulatedPropagationMaps(), FilterTree::loadXML(), FilterTree::refreshFilterTree(), FilterTree::serialiseToStringPaths(), and FilterTree::size().

Here is the caller graph for this function:

◆ size() [2/2]

template<class T , class tree_node_allocator >

size_t tree< T, tree_node_allocator >::size ( const iterator_base & top ) const

Count the total number of nodes below the indicated node (plus one).

◆ sort() [1/2]

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::sort	(	sibling_iterator	from,
		sibling_iterator	to,
		bool	deep = `false`
	)

Sort (std::sort only moves values of nodes, this one moves children as well).

◆ sort() [2/2]

template<class T , class tree_node_allocator >

template<class StrictWeakOrdering >

void tree< T, tree_node_allocator >::sort	(	sibling_iterator	from,
		sibling_iterator	to,
		StrictWeakOrdering	comp,
		bool	deep = `false`
	)

◆ subtree() [1/2]

template<class T , class tree_node_allocator >

tree< T, tree_node_allocator > tree< T, tree_node_allocator >::subtree	(	sibling_iterator	from,
		sibling_iterator	to
	)		const

Extract a new tree formed by the range of siblings plus all their children.

◆ subtree() [2/2]

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::subtree	(	tree< T, tree_node_allocator > &	tmp,
		sibling_iterator	from,
		sibling_iterator	to
	)		const

◆ swap() [1/2]

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::swap ( sibling_iterator it )

Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).

◆ swap() [2/2]

template<class T , class tree_node_allocator >

void tree< T, tree_node_allocator >::swap	(	iterator	one,
		iterator	two
	)

Exchange two nodes (plus subtrees)

◆ wrap()

template<class T, class tree_node_allocator >

template<typename iter >

iter tree< T, tree_node_allocator >::wrap	(	iter	position,
		const T &	x
	)

Replace node with a new node, making the old node a child of the new node.

Member Data Documentation

◆ feet

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

tree_node * tree< T, tree_node_allocator >::feet

◆ head

template<class T, class tree_node_allocator = std::allocator<tree_node_<T> >>

tree_node* tree< T, tree_node_allocator >::head

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

tree.hh

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Types

Member Typedef Documentation

◆ breadth_first_iterator

◆ iterator

◆ tree_node

◆ value_type

Constructor & Destructor Documentation

◆ tree() [1/4]

◆ tree() [2/4]

◆ tree() [3/4]

◆ tree() [4/4]

◆ ~tree()

Member Function Documentation

◆ append_child() [1/3]

◆ append_child() [2/3]

◆ append_child() [3/3]

◆ append_children()

◆ begin() [1/2]

◆ begin() [2/2]

◆ begin_breadth_first()

◆ begin_fixed()

◆ begin_leaf() [1/2]

◆ begin_leaf() [2/2]

◆ begin_post()

◆ child()

◆ clear()

◆ depth() [1/2]

◆ depth() [2/2]

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ end_breadth_first()

◆ end_fixed()

◆ end_leaf() [1/2]

◆ end_leaf() [2/2]

◆ end_post()

◆ equal() [1/2]

◆ equal() [2/2]

◆ equal_subtree() [1/2]

◆ equal_subtree() [2/2]

◆ erase()

◆ erase_children()

◆ flatten()

◆ index()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_after()

◆ insert_subtree()

◆ insert_subtree_after()

◆ is_in_subtree()

◆ is_valid()

◆ max_depth() [1/2]

◆ max_depth() [2/2]

◆ merge()

◆ move_after()

◆ move_before() [1/2]

◆ move_before() [2/2]

◆ move_ontop()

◆ next_at_same_depth()

◆ next_sibling()

◆ number_of_children()

◆ number_of_siblings()

◆ operator=()

◆ parent()

◆ prepend_child() [1/3]

◆ prepend_child() [2/3]

◆ prepend_child() [3/3]

◆ prepend_children()

◆ previous_sibling()

◆ reparent() [1/2]

◆ reparent() [2/2]

◆ replace() [1/3]

◆ replace() [2/3]

◆ replace() [3/3]

◆ set_head()