A toolkit for working with phylogenetic data.
v0.19.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
IteratorPathSet< LinkType, NodeType, EdgeType > Class Template Reference

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

Detailed Description

template<typename LinkType, typename NodeType, typename EdgeType>
class genesis::tree::IteratorPathSet< LinkType, NodeType, EdgeType >

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 94 of file path_set.hpp.

Public Member Functions

 IteratorPathSet ()
 
 IteratorPathSet (NodeType &start, NodeType &finish, NodeType &lca)
 
 IteratorPathSet (LinkType &start, LinkType &finish, LinkType &lca)
 
 IteratorPathSet (IteratorPathSet const &)=default
 
 IteratorPathSet (IteratorPathSet &&)=default
 
 ~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)
 
IteratorPathSetoperator= (IteratorPathSet const &)=default
 
IteratorPathSetoperator= (IteratorPathSet &&)=default
 
bool operator== (const self_type &other) const
 
LinkType & start_link () const
 
NodeType & start_node () const
 

Public Types

using iterator_category = std::forward_iterator_tag
 
using self_type = IteratorPathSet< LinkType, NodeType, EdgeType >
 

Constructor & Destructor Documentation

IteratorPathSet ( )
inline

Definition at line 109 of file path_set.hpp.

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

Definition at line 116 of file path_set.hpp.

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

Definition at line 120 of file path_set.hpp.

~IteratorPathSet ( )
default
IteratorPathSet ( IteratorPathSet< LinkType, NodeType, EdgeType > const &  )
default
IteratorPathSet ( IteratorPathSet< LinkType, NodeType, EdgeType > &&  )
default

Member Function Documentation

EdgeType& edge ( ) const
inline

Definition at line 249 of file path_set.hpp.

LinkType& finish_link ( ) const
inline

Definition at line 264 of file path_set.hpp.

NodeType& finish_node ( ) const
inline

Definition at line 269 of file path_set.hpp.

bool is_last_common_ancestor ( ) const
inline

Definition at line 229 of file path_set.hpp.

bool is_lca ( ) const
inline

Definition at line 234 of file path_set.hpp.

LinkType& lca_link ( ) const
inline

Definition at line 274 of file path_set.hpp.

NodeType& lca_node ( ) const
inline

Definition at line 279 of file path_set.hpp.

LinkType& link ( ) const
inline

Definition at line 239 of file path_set.hpp.

NodeType& node ( ) const
inline

Definition at line 244 of file path_set.hpp.

bool operator!= ( const self_type other) const
inline

Definition at line 220 of file path_set.hpp.

self_type operator* ( )
inline

Definition at line 160 of file path_set.hpp.

self_type operator++ ( )
inline

Definition at line 165 of file path_set.hpp.

self_type operator++ ( int  )
inline

Definition at line 208 of file path_set.hpp.

IteratorPathSet& operator= ( IteratorPathSet< LinkType, NodeType, EdgeType > const &  )
default
IteratorPathSet& operator= ( IteratorPathSet< LinkType, NodeType, EdgeType > &&  )
default
bool operator== ( const self_type other) const
inline

Definition at line 215 of file path_set.hpp.

LinkType& start_link ( ) const
inline

Definition at line 254 of file path_set.hpp.

NodeType& start_node ( ) const
inline

Definition at line 259 of file path_set.hpp.

Member Typedef Documentation

using iterator_category = std::forward_iterator_tag

Definition at line 102 of file path_set.hpp.

using self_type = IteratorPathSet<LinkType, NodeType, EdgeType>

Definition at line 103 of file path_set.hpp.


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