A toolkit for working with phylogenetic data.
v0.20.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 95 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 110 of file path_set.hpp.

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

Definition at line 117 of file path_set.hpp.

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

Definition at line 121 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 250 of file path_set.hpp.

LinkType& finish_link ( ) const
inline

Definition at line 265 of file path_set.hpp.

NodeType& finish_node ( ) const
inline

Definition at line 270 of file path_set.hpp.

bool is_last_common_ancestor ( ) const
inline

Definition at line 230 of file path_set.hpp.

bool is_lca ( ) const
inline

Definition at line 235 of file path_set.hpp.

LinkType& lca_link ( ) const
inline

Definition at line 275 of file path_set.hpp.

NodeType& lca_node ( ) const
inline

Definition at line 280 of file path_set.hpp.

LinkType& link ( ) const
inline

Definition at line 240 of file path_set.hpp.

NodeType& node ( ) const
inline

Definition at line 245 of file path_set.hpp.

bool operator!= ( const self_type other) const
inline

Definition at line 221 of file path_set.hpp.

self_type operator* ( )
inline

Definition at line 161 of file path_set.hpp.

self_type operator++ ( )
inline

Definition at line 166 of file path_set.hpp.

self_type operator++ ( int  )
inline

Definition at line 209 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 216 of file path_set.hpp.

LinkType& start_link ( ) const
inline

Definition at line 255 of file path_set.hpp.

NodeType& start_node ( ) const
inline

Definition at line 260 of file path_set.hpp.

Member Typedef Documentation

using iterator_category = std::forward_iterator_tag

Definition at line 103 of file path_set.hpp.

using self_type = IteratorPathSet<LinkType, NodeType, EdgeType>

Definition at line 104 of file path_set.hpp.


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