A toolkit for working with phylogenetic data.
v0.24.0
tree/iterator/postorder.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TREE_ITERATOR_POSTORDER_H_
2 #define GENESIS_TREE_ITERATOR_POSTORDER_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2018 Lucas Czech and HITS gGmbH
7 
8  This program is free software: you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation, either version 3 of the License, or
11  (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program. If not, see <http://www.gnu.org/licenses/>.
20 
21  Contact:
22  Lucas Czech <lucas.czech@h-its.org>
23  Exelixis Lab, Heidelberg Institute for Theoretical Studies
24  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25 */
26 
34 #include "genesis/tree/tree.hpp"
37 
38 #include <cassert>
39 #include <deque>
40 #include <iterator>
41 #include <type_traits>
42 
43 namespace genesis {
44 namespace tree {
45 
46 // =================================================================================================
47 // Forward Declarations
48 // =================================================================================================
49 
50 class Tree;
51 class TreeNode;
52 class TreeEdge;
53 class TreeLink;
54 class Subtree;
55 
56 // =================================================================================================
57 // Postorder Iterator
58 // =================================================================================================
59 
60 template< bool is_const = true >
62 {
63 
64 public:
65 
66  // -----------------------------------------------------
67  // Typedefs
68  // -----------------------------------------------------
69 
70  // Make the memer types const or not, depending on iterator type.
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;
75 
77  using iterator_category = std::forward_iterator_tag;
78  // using value_type = NodeType;
79  // using pointer = NodeType*;
80  // using reference = NodeType&;
81  // using difference_type = std::ptrdiff_t;
82 
83  // -----------------------------------------------------
84  // Constructors and Rule of Five
85  // -----------------------------------------------------
86 
88  : start_( nullptr )
89  , link_ ( nullptr )
90  {}
91 
95  explicit IteratorPostorder( TreeType& tree )
96  : IteratorPostorder( tree.root_link() )
97  {}
98 
108  : IteratorPostorder( node.primary_link() )
109  {}
110 
121  : start_( &link )
122  {
123  // The stack keeps links to nodes that yet need to be visited.
124  // These are the links that point towards the start link.
125 
126  // Fill in the start link. This will be the last node visited.
127  auto link_ptr = &link;
128  stack_.push_back( link_ptr );
129 
130  // Now start traversing in the direction of this link.
131  stack_.push_front( &link_ptr->outer() );
132  link_ptr = &link_ptr->outer();
133 
134  // Add all inner nodes along the first path, until we reach a leaf.
135  while( is_inner_( *link_ptr )) {
136  push_front_children_( link_ptr );
137  link_ptr = &link_ptr->next().outer();
138  }
139 
140  // The fist leaf that we found is the last link that was added.
141  // Remove it from the stack again, because this is where we stop - this is the first
142  // node being visited, and hence does not need to be on the stack any more
143  // (it was added to keep the push_front_children fct simple and without edge case).
144  assert( link_ptr == stack_.front() );
145  stack_.pop_front();
146  link_ = link_ptr;
147  }
148 
153  explicit IteratorPostorder( Subtree const& subtree )
154  : start_( &(subtree.link()) )
155  {
156  // Add the starting/subtree link as the final one to the stack.
157  auto link_ptr = &(subtree.link());
158  stack_.push_back( link_ptr );
159 
160  // Compared to the normal constructor above, we simply leave out the part
161  // where we move in the outer() direction of the link, and instead just continue
162  // in the direction of the subtree itself.
163 
164  // Find the first leaf.
165  while( is_inner_( *link_ptr )) {
166  push_front_children_( link_ptr );
167  link_ptr = &link_ptr->next().outer();
168  }
169 
170  // The leaf that was last added is the one that we visit now.
171  // Remove it again, as we are here now.
172  assert( link_ptr == stack_.front() );
173  stack_.pop_front();
174  link_ = link_ptr;
175  }
176 
177  ~IteratorPostorder() = default;
178 
179  IteratorPostorder( IteratorPostorder const& ) = default;
180  IteratorPostorder( IteratorPostorder&& ) = default;
181 
182  IteratorPostorder& operator= ( IteratorPostorder const& ) = default;
184 
185  // -----------------------------------------------------
186  // Operators
187  // -----------------------------------------------------
188 
190  {
191  return *this;
192  }
193 
195  {
196  if( stack_.empty() ) {
197 
198  // This condition marks the end of the traversal:
199  // There are no more links on the stack to be visited.
200  link_ = nullptr;
201 
202  } else if( &link_->outer().next() == stack_.front() ) {
203 
204  // This condition is active when seeing an inner node the last time,
205  // meaning that it is its turn to be visited.
206  link_ = stack_.front();
207  stack_.pop_front();
208 
209  } else {
210 
211  // This condition is active in all other cases: going down the tree towards the leaves.
212  // That means, we are in a part that is not yet on the stack, so we need to add it.
213  link_ = stack_.front();
214  while( is_inner_( *link_ )) {
215  push_front_children_(link_);
216  link_ = &link_->next().outer();
217  }
218  assert( link_ == stack_.front() );
219  stack_.pop_front();
220  }
221 
222  return *this;
223  }
224 
226  {
227  self_type tmp = *this;
228  ++(*this);
229  return tmp;
230  }
231 
232  bool operator == (const self_type &other) const
233  {
234  return other.link_ == link_;
235  }
236 
237  bool operator != (const self_type &other) const
238  {
239  return !(other == *this);
240  }
241 
242  // -----------------------------------------------------
243  // Members
244  // -----------------------------------------------------
245 
246  bool is_last_iteration() const
247  {
248  return link_ == start_;
249  }
250 
251  LinkType& link() const
252  {
253  return *link_;
254  }
255 
256  NodeType& node() const
257  {
258  return link_->node();
259  }
260 
261  EdgeType& edge() const
262  {
263  return link_->edge();
264  }
265 
267  {
268  return *start_;
269  }
270 
272  {
273  return start_->node();
274  }
275 
276 private:
277 
278  // -----------------------------------------------------
279  // Internal Helper Functions
280  // -----------------------------------------------------
281 
282  void push_front_children_( LinkType* link )
283  {
284  // we need to push to a tmp queue first, in order to get the order right.
285  // otherwise, we would still do a postorder traversal, but starting with
286  // the last child of each node instead of the first one.
287  std::deque<LinkType*> tmp;
288  LinkType* c = &link->next();
289  while( c != link ) {
290  tmp.push_front( &c->outer() );
291  c = &c->next();
292  }
293  for( LinkType* l : tmp ) {
294  stack_.push_front(l);
295  }
296  }
297 
298  bool is_inner_( TreeLink const& link )
299  {
300  // Duplication of the free function. But this avoids pulling in the header.
301  return &( link.next() ) != &link;
302  }
303 
304  // -----------------------------------------------------
305  // Data Members
306  // -----------------------------------------------------
307 
308  LinkType* const start_;
309  LinkType* link_;
310 
311  std::deque<LinkType*> stack_;
312 };
313 
314 // =================================================================================================
315 // Postorder Wrapper Functions
316 // =================================================================================================
317 
318 template<typename ElementType>
320 postorder( ElementType const& element )
321 {
322  return {
323  IteratorPostorder< true >( element ),
325  };
326 }
327 
328 template<typename ElementType>
330 postorder( ElementType& element )
331 {
332  return {
333  IteratorPostorder< false >( element ),
335  };
336 }
337 
338 } // namespace tree
339 } // namespace genesis
340 
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
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.
Definition: subtree.hpp:69
IteratorPostorder(NodeType &node)
Start a postorder traversal at the given TreeNode, moving in the root direction first.
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
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.
Definition: subtree.hpp:125
Header of Tree class.
Simple wrapper for typical begin() and end() iterators, to be used in range-based for loops...
Definition: range.hpp:46
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.