A toolkit for working with phylogenetic data.
v0.24.0
tree/iterator/preorder.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TREE_ITERATOR_PREORDER_H_
2 #define GENESIS_TREE_ITERATOR_PREORDER_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2019 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 <iterator>
40 #include <type_traits>
41 #include <vector>
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 // Preorder 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  using SubtreeType = typename std::conditional< is_const, Subtree const, Subtree >::type;
76 
78  using iterator_category = std::forward_iterator_tag;
79  // using value_type = NodeType;
80  // using pointer = NodeType*;
81  // using reference = NodeType&;
82  // using difference_type = std::ptrdiff_t;
83 
84  // -----------------------------------------------------
85  // Constructors and Rule of Five
86  // -----------------------------------------------------
87 
89  : start_( nullptr )
90  , link_ ( nullptr )
91  {}
92 
96  explicit IteratorPreorder( TreeType& tree )
97  : IteratorPreorder( tree.root_link() )
98  {}
99 
104  : IteratorPreorder( node.primary_link() )
105  {}
106 
111  // Set the starting link and the one where we currently are.
112  // In preorder traversal, we start at the actual node, so this is easy.
113  : start_( &link )
114  , link_( &link )
115  {
116  // Add all neighbouring nodes of the starting one to the stack.
117  // As push_back_children_() does not add the outer() of the given link,
118  // we need to do this extra (this is done in order to keep this function simple,
119  // without haven to consider the "edge case" that occurs here in the constructor).
120  // All these neighbours will then be visisted later.
121  push_back_children_( &link );
122  stack_.push_back( &link.outer() );
123  }
124 
129  explicit IteratorPreorder( SubtreeType& subtree )
130  : start_( &(subtree.link()) )
131  , link_( &(subtree.link()) )
132  {
133  // Compared to the normal constructor above, we do the same, but leave out
134  // the outer() link, as this is the part of the tree that we want to skip.
135  push_back_children_( link_ );
136  }
137 
138  ~IteratorPreorder() = default;
139 
140  IteratorPreorder( IteratorPreorder const& ) = default;
141  IteratorPreorder( IteratorPreorder&& ) = default;
142 
143  IteratorPreorder& operator= ( IteratorPreorder const& ) = default;
145 
146  // -----------------------------------------------------
147  // Operators
148  // -----------------------------------------------------
149 
151  {
152  return *this;
153  }
154 
156  {
157  if( stack_.empty() ) {
158 
159  // We reached the end of the stack.
160  // This is the signal to stop traversing.
161  link_ = nullptr;
162 
163  } else {
164 
165  // While the stack is not empty, it gives us the next link to move to.
166  // Go there, and add its children to the stack for the next iterations.
167  link_ = stack_.back();
168  stack_.pop_back();
169  push_back_children_(link_);
170  }
171 
172  return *this;
173  }
174 
176  {
177  self_type tmp = *this;
178  ++(*this);
179  return tmp;
180  }
181 
182  bool operator == (const self_type &other) const
183  {
184  return other.link_ == link_;
185  }
186 
187  bool operator != (const self_type &other) const
188  {
189  return !(other == *this);
190  }
191 
192  // -----------------------------------------------------
193  // Members
194  // -----------------------------------------------------
195 
196  bool is_first_iteration() const
197  {
198  return link_ == start_;
199  }
200 
201  LinkType& link() const
202  {
203  return *link_;
204  }
205 
206  NodeType& node() const
207  {
208  return link_->node();
209  }
210 
211  EdgeType& edge() const
212  {
213  return link_->edge();
214  }
215 
217  {
218  return *start_;
219  }
220 
222  {
223  return start_->node();
224  }
225 
226  // -----------------------------------------------------
227  // Internal Helper Functions
228  // -----------------------------------------------------
229 
230 private:
231 
232  void push_back_children_( LinkType* link )
233  {
234  // we need to push to a tmp first, in order to get the order right.
235  // otherwise, we would still do a preorder traversal, but starting with
236  // the last child of each node instead of the first one.
237  std::vector<LinkType*> tmp;
238  LinkType* c = &link->next();
239  while (c != link) {
240  tmp.push_back( &c->outer() );
241  c = &c->next();
242  }
243  for( auto lit = tmp.rbegin(); lit != tmp.rend(); ++lit ) {
244  stack_.push_back( *lit );
245  }
246  }
247 
248  // -----------------------------------------------------
249  // Data Members
250  // -----------------------------------------------------
251 
252  LinkType* const start_;
253  LinkType* link_;
254 
255  std::vector<LinkType*> stack_;
256 };
257 
258 // =================================================================================================
259 // Preorder Wrapper Functions
260 // =================================================================================================
261 
262 template<typename ElementType>
264 preorder( ElementType const& element )
265 {
266  return {
267  IteratorPreorder< true >( element ),
269  };
270 }
271 
272 template<typename ElementType>
274 preorder( ElementType& element )
275 {
276  return {
277  IteratorPreorder< false >( element ),
279  };
280 }
281 
282 } // namespace tree
283 } // namespace genesis
284 
285 #endif // include guard
bool operator==(const self_type &other) const
bool operator!=(const self_type &other) const
IteratorPreorder(NodeType &node)
Start a preorder traversal at the given TreeNode, moving in the root direction first.
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
typename std::conditional< is_const, TreeLink const, TreeLink >::type LinkType
typename std::conditional< is_const, Subtree const, Subtree >::type SubtreeType
typename std::conditional< is_const, Tree const, Tree >::type TreeType
typename std::conditional< is_const, TreeNode const, TreeNode >::type NodeType
IteratorPreorder(TreeType &tree)
Start a preorder traversal at the root of the given Tree.
typename std::conditional< is_const, TreeEdge const, TreeEdge >::type EdgeType
utils::Range< IteratorPreorder< true > > preorder(ElementType const &element)
IteratorPreorder & operator=(IteratorPreorder const &)=default
Header of Tree class.
Simple wrapper for typical begin() and end() iterators, to be used in range-based for loops...
Definition: range.hpp:46
IteratorPreorder(SubtreeType &subtree)
Start a preorder traversal at the top TreeNode of a Subtree, only traversing the nodes in the subtree...
IteratorPreorder(LinkType &link)
Start a preorder traversal at a given TreeLink, moving in the direction of the link first...
std::forward_iterator_tag iterator_category