A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 
35 #include "genesis/tree/tree.hpp"
37 
38 #include <assert.h>
39 #include <deque>
40 #include <iterator>
41 
42 namespace genesis {
43 namespace tree {
44 
45 // =================================================================================================
46 // Forward Declarations
47 // =================================================================================================
48 
49 class Tree;
50 class TreeNode;
51 class TreeEdge;
52 class TreeLink;
53 
54 // =================================================================================================
55 // Postorder Iterator
56 // =================================================================================================
57 
58 template <typename LinkType, typename NodeType, typename EdgeType>
60 {
61 
62 public:
63 
64  // -----------------------------------------------------
65  // Typedefs
66  // -----------------------------------------------------
67 
68  using iterator_category = std::forward_iterator_tag;
70 
71  // -----------------------------------------------------
72  // Constructors and Rule of Five
73  // -----------------------------------------------------
74 
76  : start_( nullptr )
77  , link_ ( nullptr )
78  {}
79 
80  explicit IteratorPostorder( Tree& tree )
81  : IteratorPostorder( tree.root_link() )
82  {}
83 
84  explicit IteratorPostorder( Tree const& tree )
85  : IteratorPostorder( tree.root_link() )
86  {}
87 
88  explicit IteratorPostorder( NodeType& node )
89  : IteratorPostorder( node.primary_link() )
90  {}
91 
92  explicit IteratorPostorder( LinkType& link )
93  : start_( &link )
94  {
95  auto link_ptr = &link;
96  stack_.push_back(link_ptr);
97  stack_.push_front(&link_ptr->outer());
98  link_ptr = &link_ptr->outer();
99  while( is_inner( *link_ptr )) {
100  push_front_children(link_ptr);
101  link_ptr = &link_ptr->next().outer();
102  }
103  assert(link_ptr == stack_.front());
104  stack_.pop_front();
105  link_ = link_ptr;
106  }
107 
108  ~IteratorPostorder() = default;
109 
110  IteratorPostorder( IteratorPostorder const& ) = default;
111  IteratorPostorder( IteratorPostorder&& ) = default;
112 
113  IteratorPostorder& operator= ( IteratorPostorder const& ) = default;
115 
116  // -----------------------------------------------------
117  // Operators
118  // -----------------------------------------------------
119 
121  {
122  return *this;
123  }
124 
126  {
127  if( stack_.empty() ) {
128  // this condition marks the end of the traversal
129  link_ = nullptr;
130  } else if( &link_->outer().next() == stack_.front() ) {
131  // this condition is active when seeing an inner node the last time,
132  // meaning that it is its turn to be traversed
133  link_ = stack_.front();
134  stack_.pop_front();
135  } else {
136  // this condition is active in all other cases: going down the tree towards the leaves
137  link_ = stack_.front();
138  while( is_inner( *link_ )) {
139  push_front_children(link_);
140  link_ = &link_->next().outer();
141  }
142  assert( link_ == stack_.front() );
143  stack_.pop_front();
144  }
145  return *this;
146  }
147 
149  {
150  self_type tmp = *this;
151  ++(*this);
152  return tmp;
153  }
154 
155  bool operator == (const self_type &other) const
156  {
157  return other.link_ == link_;
158  }
159 
160  bool operator != (const self_type &other) const
161  {
162  return !(other == *this);
163  }
164 
165  // -----------------------------------------------------
166  // Members
167  // -----------------------------------------------------
168 
169  bool is_last_iteration() const
170  {
171  return link_ == start_;
172  }
173 
174  LinkType& link() const
175  {
176  return *link_;
177  }
178 
179  NodeType& node() const
180  {
181  return link_->node();
182  }
183 
184  EdgeType& edge() const
185  {
186  return link_->edge();
187  }
188 
189  LinkType& start_link() const
190  {
191  return *start_;
192  }
193 
194  NodeType& start_node() const
195  {
196  return start_->node();
197  }
198 
199 private:
200 
201  // -----------------------------------------------------
202  // Internal Helper Functions
203  // -----------------------------------------------------
204 
205  void push_front_children( LinkType* link )
206  {
207  // we need to push to a tmp queue first, in order to get the order right.
208  // otherwise, we would still do a postorder traversal, but starting with
209  // the last child of each node instead of the first one.
210  std::deque<LinkType*> tmp;
211  LinkType* c = &link->next();
212  while( c != link ) {
213  tmp.push_front( &c->outer() );
214  c = &c->next();
215  }
216  for( LinkType* l : tmp ) {
217  stack_.push_front(l);
218  }
219  }
220 
221  // -----------------------------------------------------
222  // Data Members
223  // -----------------------------------------------------
224 
225  LinkType* const start_;
226  LinkType* link_;
227 
228  std::deque<LinkType*> stack_;
229 };
230 
231 // =================================================================================================
232 // Postorder Wrapper Functions
233 // =================================================================================================
234 
235 template<typename ElementType>
236 utils::Range< IteratorPostorder< TreeLink const, TreeNode const, TreeEdge const >>
237 postorder( ElementType const& element )
238 {
239  return {
242  };
243 }
244 
245 template<typename ElementType>
247 postorder( ElementType& element )
248 {
249  return {
252  };
253 }
254 
255 } // namespace tree
256 } // namespace genesis
257 
258 #endif // include guard
bool is_inner(TreeLink const &link)
Return true iff the node of the given link is an inner node.
bool operator!=(const self_type &other) const
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:95
IteratorPostorder & operator=(IteratorPostorder const &)=default
bool operator==(const self_type &other) const
Header of Tree class.
utils::Range< IteratorPostorder< TreeLink const, TreeNode const, TreeEdge const > > postorder(ElementType const &element)
std::forward_iterator_tag iterator_category