1 #ifndef GENESIS_TREE_ITERATOR_PATH_H_ 2 #define GENESIS_TREE_ITERATOR_PATH_H_ 41 #include <type_traits> 59 template<
bool is_const = true >
70 using TreeType =
typename std::conditional< is_const, Tree const, Tree >::type;
71 using LinkType =
typename std::conditional< is_const, TreeLink const, TreeLink >::type;
72 using NodeType =
typename std::conditional< is_const, TreeNode const, TreeNode >::type;
73 using EdgeType =
typename std::conditional< is_const, TreeEdge const, TreeEdge >::type;
98 : start_( &start.
node().primary_link() )
99 , finish_( &finish.
node().primary_link() )
115 std::vector<LinkType*> link_path;
119 while( &cur_link->edge().secondary_link() == cur_link ) {
123 assert( !
is_root( cur_link->node() ));
126 assert( cur_link == &cur_link->edge().secondary_link() );
129 link_path.push_back( cur_link );
136 assert( &cur_link->edge().primary_link() == &cur_link->outer() );
137 cur_link = &cur_link->outer().node().primary_link();
141 assert(
is_root( cur_link->node() ));
142 link_path.push_back( cur_link );
148 if( start_ == finish_ ) {
149 reverse_path_.push_back( start_ );
159 assert( start_path.size() > 0 && finish_path.size() > 0 );
160 assert( start_path.front() == start_ );
161 assert( finish_path.front() == finish_ );
162 assert( start_path.back() == finish_path.back() );
168 start_path.size() > 1 &&
169 finish_path.size() > 1 &&
170 start_path.at( start_path.size() - 1 ) == finish_path.at( finish_path.size() - 1 ) &&
171 start_path.at( start_path.size() - 2 ) == finish_path.at( finish_path.size() - 2 )
173 start_path.pop_back();
174 finish_path.pop_back();
178 assert( start_path.size() > 0 && finish_path.size() > 0 );
179 assert( start_path.back() == finish_path.back() );
182 lca_ = start_path.back();
187 reverse_path_ = std::move( finish_path );
188 reverse_path_.pop_back();
189 reverse_path_.insert( reverse_path_.end(), start_path.rbegin(), start_path.rend() );
191 assert( reverse_path_.front() == finish_ );
192 assert( reverse_path_.back() == start_ );
215 if( reverse_path_.size() > 1 ) {
216 reverse_path_.pop_back();
223 reverse_path_.clear();
237 return other.start_ == start_ &&
238 other.finish_ == finish_ &&
239 other.reverse_path_.size() == reverse_path_.size();
244 return !(other == *
this);
271 return reverse_path_.back() == lca_;
284 return *reverse_path_.back();
289 return reverse_path_.back()->node();
294 return reverse_path_.back()->edge();
304 return start_->node();
314 return finish_->node();
327 std::vector<LinkType*> reverse_path_;
335 template<
typename ElementType>
337 path( ElementType
const& start, ElementType
const& finish )
345 template<
typename ElementType>
347 path( ElementType& start, ElementType& finish )
358 #endif // include guard NodeType & finish_node() const
IteratorPath(LinkType &start, LinkType &finish)
bool is_root(TreeLink const &link)
Return whether the link belongs to the root node of its Tree.
bool operator==(const self_type &other) const
typename std::conditional< is_const, Tree const, Tree >::type TreeType
bool is_lca() const
Alias for is_last_common_ancestor(). See there for more information.
IteratorPath(NodeType &start, NodeType &finish)
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
typename std::conditional< is_const, TreeNode const, TreeNode >::type NodeType
std::vector< TreeLink const *> path_to_root(TreeNode const &node)
Helper function that finds all TreeLinks between a given TreeNode and the root of the Tree...
utils::Range< IteratorPath< true > > path(ElementType const &start, ElementType const &finish)
std::forward_iterator_tag iterator_category
bool is_last_common_ancestor() const
Return whether the current iterator position (node) is the last common ancestor of the two start and ...
IteratorPath & operator=(IteratorPath const &)=default
typename std::conditional< is_const, TreeEdge const, TreeEdge >::type EdgeType
NodeType & start_node() const
LinkType & finish_link() const
typename std::conditional< is_const, TreeLink const, TreeLink >::type LinkType
bool operator!=(const self_type &other) const
Simple wrapper for typical begin() and end() iterators, to be used in range-based for loops...
LinkType & start_link() const