#include <genesis/tree/iterator/path_set.hpp>
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 |
|
inline |
Definition at line 122 of file path_set.hpp.
|
inline |
Definition at line 129 of file path_set.hpp.
|
inline |
Definition at line 133 of file path_set.hpp.
|
default |
|
default |
|
default |
|
inline |
Definition at line 262 of file path_set.hpp.
|
inline |
Definition at line 277 of file path_set.hpp.
|
inline |
Definition at line 282 of file path_set.hpp.
|
inline |
Definition at line 242 of file path_set.hpp.
|
inline |
Definition at line 247 of file path_set.hpp.
|
inline |
Definition at line 287 of file path_set.hpp.
|
inline |
Definition at line 292 of file path_set.hpp.
|
inline |
Definition at line 252 of file path_set.hpp.
|
inline |
Definition at line 257 of file path_set.hpp.
|
inline |
Definition at line 233 of file path_set.hpp.
|
inline |
Definition at line 173 of file path_set.hpp.
|
inline |
Definition at line 178 of file path_set.hpp.
|
inline |
Definition at line 221 of file path_set.hpp.
|
default |
|
default |
|
inline |
Definition at line 228 of file path_set.hpp.
|
inline |
Definition at line 267 of file path_set.hpp.
|
inline |
Definition at line 272 of file path_set.hpp.
Definition at line 108 of file path_set.hpp.
using iterator_category = std::forward_iterator_tag |
Definition at line 111 of file path_set.hpp.
Definition at line 106 of file path_set.hpp.
Definition at line 107 of file path_set.hpp.
using self_type = IteratorPathSet< is_const > |
Definition at line 110 of file path_set.hpp.
Definition at line 105 of file path_set.hpp.