1 #ifndef GENESIS_TREE_ITERATOR_POSTORDER_H_ 2 #define GENESIS_TREE_ITERATOR_POSTORDER_H_ 41 #include <type_traits> 60 template<
bool is_const = true >
71 using TreeType =
typename std::conditional< is_const, Tree const, Tree >::type;
72 using LinkType =
typename std::conditional< is_const, TreeLink const, TreeLink >::type;
73 using NodeType =
typename std::conditional< is_const, TreeNode const, TreeNode >::type;
74 using EdgeType =
typename std::conditional< is_const, TreeEdge const, TreeEdge >::type;
127 auto link_ptr = &
link;
128 stack_.push_back( link_ptr );
131 stack_.push_front( &link_ptr->outer() );
132 link_ptr = &link_ptr->outer();
135 while( is_inner_( *link_ptr )) {
136 push_front_children_( link_ptr );
137 link_ptr = &link_ptr->next().outer();
144 assert( link_ptr == stack_.front() );
154 : start_( &(subtree.
link()) )
157 auto link_ptr = &(subtree.
link());
158 stack_.push_back( link_ptr );
165 while( is_inner_( *link_ptr )) {
166 push_front_children_( link_ptr );
167 link_ptr = &link_ptr->next().outer();
172 assert( link_ptr == stack_.front() );
196 if( stack_.empty() ) {
202 }
else if( &link_->outer().next() == stack_.front() ) {
206 link_ = stack_.front();
213 link_ = stack_.front();
214 while( is_inner_( *link_ )) {
215 push_front_children_(link_);
216 link_ = &link_->next().outer();
218 assert( link_ == stack_.front() );
234 return other.link_ == link_;
239 return !(other == *
this);
248 return link_ == start_;
258 return link_->node();
263 return link_->edge();
273 return start_->node();
287 std::deque<LinkType*> tmp;
290 tmp.push_front( &c->outer() );
294 stack_.push_front(l);
298 bool is_inner_(
TreeLink const& link )
301 return &( link.
next() ) != &link;
311 std::deque<LinkType*> stack_;
318 template<
typename ElementType>
328 template<
typename ElementType>
341 #endif // include guard
IteratorPostorder(LinkType &link)
Start a postorder traversal at a given TreeLink, moving in the direction of the link first...
typename std::conditional< is_const, TreeEdge const, TreeEdge >::type EdgeType
~IteratorPostorder()=default
bool operator!=(const self_type &other) const
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
Reference to a subtree of a Tree.
IteratorPostorder(NodeType &node)
Start a postorder traversal at the given TreeNode, moving in the root direction first.
TreeLink & next()
Return the next TreeLink within the TreeNode of this link.
utils::Range< IteratorPostorder< true > > postorder(ElementType const &element)
typename std::conditional< is_const, TreeLink const, TreeLink >::type LinkType
typename std::conditional< is_const, TreeNode const, TreeNode >::type NodeType
bool is_last_iteration() const
IteratorPostorder & operator=(IteratorPostorder const &)=default
typename std::conditional< is_const, Tree const, Tree >::type TreeType
TreeLink const & link() const
Get the TreeLink that separates the subtree from the rest of the tree.
LinkType & start_link() const
Simple wrapper for typical begin() and end() iterators, to be used in range-based for loops...
IteratorPostorder(Subtree const &subtree)
Start a postorder traversal at the top TreeNode of a Subtree, only traversing the nodes in the subtre...
std::forward_iterator_tag iterator_category
bool operator==(const self_type &other) const
IteratorPostorder(TreeType &tree)
Start a postorder traversal at the root of the given Tree.
NodeType & start_node() const