A toolkit for working with phylogenetic data.
v0.24.0
IteratorPathSet< is_const > Class Template Reference

#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 (NodeType &start, NodeType &finish, NodeType &lca)
 
 IteratorPathSet (LinkType &start, LinkType &finish, LinkType &lca)
 
 IteratorPathSet (IteratorPathSet const &)=default
 
 IteratorPathSet (IteratorPathSet &&)=default
 
 ~IteratorPathSet ()=default
 
EdgeTypeedge () const
 
LinkTypefinish_link () const
 
NodeTypefinish_node () const
 
bool is_last_common_ancestor () const
 
bool is_lca () const
 
LinkTypelca_link () const
 
NodeTypelca_node () const
 
LinkTypelink () const
 
NodeTypenode () 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
 
LinkTypestart_link () const
 
NodeTypestart_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 > const &  )
default

◆ operator=() [2/2]

IteratorPathSet& operator= ( IteratorPathSet< is_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: