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