#include <genesis/tree/iterator/path_set.hpp>

Detailed Description

template<bool is_const = true>
class genesis::tree::IteratorPathSet< is_const >

Iterate the path between two TreeNodes (non-linearily), given their lowest common ancestor (LCA).

This is a fast alternative to IteratorPath, with two differences.

Firstly, this iterator needs to know the LCA of both nodes. This allows skipping its calculation, for speed reasons. This is mainly useful if you maintain a list of the LCAs of pairs of nodes, e.g., when using a RMQ data structure or the like. It is also also possible to calculate the LCA, using lowest_common_ancestor(). In this case, however, using the IteratorPath is probably the better and more straight forward option.

Secondly, the path is not traversed from start to finish, but in the order:

[ start, lca ), [ finish, lca ]

That is, starting at the start node, first we move up the Tree in the direction of the root until we encounter the LCA. However, instead of visiting it immediately, we first go to the finish node, move up again in the direction of the root, until we finally reach the LCA, and this time also visit it.

If you do not want to visit the LCA while iteration, use is_lca() to detect when the iterator reaches the LCA, and simply skip it then.

This iterator is mainly useful if the order of visiting nodes/edges is not imporant, e.g., if you simply need to update some value for all of them, but not depending on their order.

Remark: The iterator assumes that the provided LCA is correct. It is able to find some cases of wrong LCAs, but not all of them. If the provided LCA is somewhere on the path between the actual LCA and the root, this not detected and will lead to visiting those additional nodes. In cases where a wrong LCA is detected, an exception is thrown. We only use this simple error checking for speed reasons, as doing a full check would require the extra amount of work that IteratorPath is doing. Thus, the user is responsible for providing a correct LCA.

Definition at line 96 of file path_set.hpp.

Public Member Functions
	IteratorPathSet ()

	IteratorPathSet (IteratorPathSet &&)=default

	IteratorPathSet (IteratorPathSet const &)=default

	IteratorPathSet (LinkType &start, LinkType &finish, LinkType &lca)

	IteratorPathSet (NodeType &start, NodeType &finish, NodeType &lca)

	~IteratorPathSet ()=default

EdgeType &	edge () const

LinkType &	finish_link () const

NodeType &	finish_node () const

bool	is_last_common_ancestor () const

bool	is_lca () const

LinkType &	lca_link () const

NodeType &	lca_node () const

LinkType &	link () const

NodeType &	node () const

bool	operator!= (const self_type &other) const

self_type	operator* ()

self_type	operator++ ()

self_type	operator++ (int)

IteratorPathSet &	operator= (IteratorPathSet &&)=default

IteratorPathSet &	operator= (IteratorPathSet const &)=default

bool	operator== (const self_type &other) const

LinkType &	start_link () const

NodeType &	start_node () const

Public Types
using	EdgeType = typename std::conditional< is_const, TreeEdge const, TreeEdge >::type

using	iterator_category = std::forward_iterator_tag

using	LinkType = typename std::conditional< is_const, TreeLink const, TreeLink >::type

using	NodeType = typename std::conditional< is_const, TreeNode const, TreeNode >::type

using	self_type = IteratorPathSet< is_const >

using	TreeType = typename std::conditional< is_const, Tree const, Tree >::type

Constructor & Destructor Documentation

◆ IteratorPathSet() [1/5]

IteratorPathSet ( )

inline

Definition at line 122 of file path_set.hpp.

◆ IteratorPathSet() [2/5]

IteratorPathSet	(	NodeType &	start,
		NodeType &	finish,
		NodeType &	lca
	)

inline

Definition at line 129 of file path_set.hpp.

◆ IteratorPathSet() [3/5]

IteratorPathSet	(	LinkType &	start,
		LinkType &	finish,
		LinkType &	lca
	)

inline

Definition at line 133 of file path_set.hpp.

◆ ~IteratorPathSet()

~IteratorPathSet ( )

default

◆ IteratorPathSet() [4/5]

IteratorPathSet ( IteratorPathSet< is_const > const & )

default

◆ IteratorPathSet() [5/5]

IteratorPathSet ( IteratorPathSet< is_const > && )

default

Member Function Documentation

◆ edge()

EdgeType& edge ( ) const

inline

Definition at line 262 of file path_set.hpp.

◆ finish_link()

LinkType& finish_link ( ) const

inline

Definition at line 277 of file path_set.hpp.

◆ finish_node()

NodeType& finish_node ( ) const

inline

Definition at line 282 of file path_set.hpp.

◆ is_last_common_ancestor()

bool is_last_common_ancestor ( ) const

inline

Definition at line 242 of file path_set.hpp.

◆ is_lca()

bool is_lca ( ) const

inline

Definition at line 247 of file path_set.hpp.

◆ lca_link()

LinkType& lca_link ( ) const

inline

Definition at line 287 of file path_set.hpp.

◆ lca_node()

NodeType& lca_node ( ) const

inline

Definition at line 292 of file path_set.hpp.

◆ link()

LinkType& link ( ) const

inline

Definition at line 252 of file path_set.hpp.

◆ node()

NodeType& node ( ) const

inline

Definition at line 257 of file path_set.hpp.

◆ operator!=()

bool operator!= ( const self_type & other ) const

inline

Definition at line 233 of file path_set.hpp.

◆ operator*()

self_type operator* ( )

inline

Definition at line 173 of file path_set.hpp.

◆ operator++() [1/2]

self_type operator++ ( )

inline

Definition at line 178 of file path_set.hpp.

◆ operator++() [2/2]

self_type operator++ ( int )

inline

Definition at line 221 of file path_set.hpp.

◆ operator=() [1/2]

IteratorPathSet& operator= ( IteratorPathSet< is_const > && )

default

◆ operator=() [2/2]

IteratorPathSet& operator= ( IteratorPathSet< is_const > const & )

default

◆ operator==()

bool operator== ( const self_type & other ) const

inline

Definition at line 228 of file path_set.hpp.

◆ start_link()

LinkType& start_link ( ) const

inline

Definition at line 267 of file path_set.hpp.

◆ start_node()

NodeType& start_node ( ) const

inline

Definition at line 272 of file path_set.hpp.

Member Typedef Documentation

◆ EdgeType

using EdgeType = typename std::conditional< is_const, TreeEdge const, TreeEdge >::type

Definition at line 108 of file path_set.hpp.

◆ iterator_category

using iterator_category = std::forward_iterator_tag

Definition at line 111 of file path_set.hpp.

◆ LinkType

using LinkType = typename std::conditional< is_const, TreeLink const, TreeLink >::type

Definition at line 106 of file path_set.hpp.

◆ NodeType

using NodeType = typename std::conditional< is_const, TreeNode const, TreeNode >::type

Definition at line 107 of file path_set.hpp.

◆ self_type

using self_type = IteratorPathSet< is_const >

Definition at line 110 of file path_set.hpp.

◆ TreeType

using TreeType = typename std::conditional< is_const, Tree const, Tree >::type

Definition at line 105 of file path_set.hpp.

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

path_set.hpp

Detailed Description

template<bool is_const = true> class genesis::tree::IteratorPathSet< is_const >

Public Member Functions

Public Types

Constructor & Destructor Documentation

◆ IteratorPathSet() [1/5]

◆ IteratorPathSet() [2/5]

◆ IteratorPathSet() [3/5]

◆ ~IteratorPathSet()

◆ IteratorPathSet() [4/5]

◆ IteratorPathSet() [5/5]

Member Function Documentation

◆ edge()

◆ finish_link()

◆ finish_node()

◆ is_last_common_ancestor()

◆ is_lca()

◆ lca_link()

◆ lca_node()

◆ link()

◆ node()

◆ operator!=()

◆ operator*()

◆ operator++() [1/2]

◆ operator++() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ start_link()

◆ start_node()

Member Typedef Documentation

◆ EdgeType

◆ iterator_category

◆ LinkType

◆ NodeType

◆ self_type

◆ TreeType

template<bool is_const = true>
class genesis::tree::IteratorPathSet< is_const >