A toolkit for working with phylogenetic data.
v0.22.1
tree/iterator/levelorder.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TREE_ITERATOR_LEVELORDER_H_
2 #define GENESIS_TREE_ITERATOR_LEVELORDER_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 // Levelorder 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  , depth_( 0 )
91  {}
92 
93  explicit IteratorLevelorder( TreeType& tree )
94  : IteratorLevelorder( tree.root_link() )
95  {}
96 
98  : IteratorLevelorder( node.primary_link() )
99  {}
100 
102  : start_( &link )
103  , link_( &link )
104  , depth_( 0 )
105  {
106  // Add all neighouring nodes in all directions of the given starting link.
107  // Because the push back function leaves out the outer() node, we need to do this extra.
108  push_back_children_( &link, 0 );
109  stack_.push_front({ &link.outer(), 1 });
110  }
111 
112  explicit IteratorLevelorder( Subtree const& subtree )
113  : start_( &(subtree.link()) )
114  , link_( &(subtree.link()) )
115  , depth_( 0 )
116  {
117  // Only add the neighouring nodes in the direction away from the link.
118  // Leave out the outer() one, as we do not want this part when iterating a subtree.
119  push_back_children_( &(subtree.link()), 0 );
120  }
121 
122  ~IteratorLevelorder() = default;
123 
124  IteratorLevelorder( IteratorLevelorder const& ) = default;
125  IteratorLevelorder( IteratorLevelorder&& ) = default;
126 
127  IteratorLevelorder& operator= ( IteratorLevelorder const& ) = default;
129 
130  // -----------------------------------------------------
131  // Operators
132  // -----------------------------------------------------
133 
135  {
136  return *this;
137  }
138 
140  {
141  if (stack_.empty()) {
142  link_ = nullptr;
143  depth_ = -1;
144  } else {
145  auto const& se = stack_.front();
146  link_ = se.link;
147  depth_ = se.depth;
148  stack_.pop_front();
149  push_back_children_(link_, depth_);
150  }
151 
152  return *this;
153  }
154 
156  {
157  self_type tmp = *this;
158  ++(*this);
159  return tmp;
160  }
161 
162  bool operator == (const self_type &other) const
163  {
164  return other.link_ == link_;
165  }
166 
167  bool operator != (const self_type &other) const
168  {
169  return !(other == *this);
170  }
171 
172  // -----------------------------------------------------
173  // Members
174  // -----------------------------------------------------
175 
176  bool is_first_iteration() const
177  {
178  return link_ == start_;
179  }
180 
181  int depth() const
182  {
183  return depth_;
184  }
185 
186  LinkType& link() const
187  {
188  return *link_;
189  }
190 
191  NodeType& node() const
192  {
193  return link_->node();
194  }
195 
196  EdgeType& edge() const
197  {
198  return link_->edge();
199  }
200 
202  {
203  return *start_;
204  }
205 
207  {
208  return start_->node();
209  }
210 
211 private:
212 
213  // -----------------------------------------------------
214  // Internal Helper Functions
215  // -----------------------------------------------------
216 
224  void push_back_children_( LinkType* link, int link_depth )
225  {
226  LinkType* c = &link->next();
227  while( c != link ) {
228  stack_.push_back({ &c->outer(), link_depth + 1 });
229  c = &c->next();
230  }
231  }
232 
233  // -----------------------------------------------------
234  // Internal Helper Typedefs
235  // -----------------------------------------------------
236 
237  // TODO add depth information to other iterators, as well.
238  typedef struct {
239  LinkType* link;
240  int depth;
241  } StackElement;
242 
243  // -----------------------------------------------------
244  // Data Members
245  // -----------------------------------------------------
246 
247  LinkType* const start_;
248  LinkType* link_;
249  int depth_;
250 
251  std::deque<StackElement> stack_;
252 };
253 
254 // =================================================================================================
255 // Levelorder Wrapper Functions
256 // =================================================================================================
257 
258 template<typename ElementType>
260 levelorder( ElementType const& element )
261 {
262  return {
263  IteratorLevelorder< true >( element ),
265  };
266 }
267 
268 template<typename ElementType>
270 levelorder( ElementType& element )
271 {
272  return {
273  IteratorLevelorder< false >( element ),
275  };
276 }
277 
278 } // namespace tree
279 } // namespace genesis
280 
281 #endif // include guard
bool operator==(const self_type &other) const
typename std::conditional< is_const, TreeEdge const, TreeEdge >::type EdgeType
utils::Range< IteratorLevelorder< true > > levelorder(ElementType const &element)
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
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
IteratorLevelorder & operator=(IteratorLevelorder const &)=default
typename std::conditional< is_const, TreeLink const, TreeLink >::type LinkType
typename std::conditional< is_const, TreeNode const, TreeNode >::type NodeType