A toolkit for working with phylogenetic data.
v0.19.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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-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 // Levelorder 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  , depth_( 0 )
78  {}
79 
80  explicit IteratorLevelorder( Tree& tree )
81  : IteratorLevelorder( tree.root_link() )
82  {}
83 
84  explicit IteratorLevelorder( Tree const& tree )
85  : IteratorLevelorder( tree.root_link() )
86  {}
87 
88  explicit IteratorLevelorder( NodeType& node )
89  : IteratorLevelorder( node.primary_link() )
90  {}
91 
92  explicit IteratorLevelorder( LinkType& link )
93  : start_( &link )
94  , link_( &link )
95  , depth_( 0 )
96  {
97  push_back_children( &link, 0 );
98  stack_.push_front({ &link.outer(), 1 });
99  }
100 
101  ~IteratorLevelorder() = default;
102 
103  IteratorLevelorder( IteratorLevelorder const& ) = default;
104  IteratorLevelorder( IteratorLevelorder&& ) = default;
105 
106  IteratorLevelorder& operator= ( IteratorLevelorder const& ) = default;
108 
109  // -----------------------------------------------------
110  // Operators
111  // -----------------------------------------------------
112 
114  {
115  return *this;
116  }
117 
119  {
120  if (stack_.empty()) {
121  link_ = nullptr;
122  depth_ = -1;
123  } else {
124  StackElement se = stack_.front();
125  link_ = se.link;
126  depth_ = se.depth;
127  stack_.pop_front();
128  push_back_children(link_, depth_);
129  }
130 
131  return *this;
132  }
133 
135  {
136  self_type tmp = *this;
137  ++(*this);
138  return tmp;
139  }
140 
141  bool operator == (const self_type &other) const
142  {
143  return other.link_ == link_;
144  }
145 
146  bool operator != (const self_type &other) const
147  {
148  return !(other == *this);
149  }
150 
151  // -----------------------------------------------------
152  // Members
153  // -----------------------------------------------------
154 
155  bool is_first_iteration() const
156  {
157  return link_ == start_;
158  }
159 
160  int depth() const
161  {
162  return depth_;
163  }
164 
165  LinkType& link() const
166  {
167  return *link_;
168  }
169 
170  NodeType& node() const
171  {
172  return link_->node();
173  }
174 
175  EdgeType& edge() const
176  {
177  return link_->edge();
178  }
179 
180  LinkType& start_link() const
181  {
182  return *start_;
183  }
184 
185  NodeType& start_node() const
186  {
187  return start_->node();
188  }
189 
190 private:
191 
192  // -----------------------------------------------------
193  // Internal Helper Functions
194  // -----------------------------------------------------
195 
196  void push_back_children( LinkType* link, int link_depth )
197  {
198  LinkType* c = &link->next();
199  while( c != link ) {
200  stack_.push_back({ &c->outer(), link_depth + 1 });
201  c = &c->next();
202  }
203  }
204 
205  // -----------------------------------------------------
206  // Internal Helper Typedefs
207  // -----------------------------------------------------
208 
209  // TODO add depth information to other iterators, as well.
210  typedef struct {
211  LinkType* link;
212  int depth;
213  } StackElement;
214 
215  // -----------------------------------------------------
216  // Data Members
217  // -----------------------------------------------------
218 
219  LinkType* const start_;
220  LinkType* link_;
221  int depth_;
222 
223  std::deque<StackElement> stack_;
224 };
225 
226 // =================================================================================================
227 // Levelorder Wrapper Functions
228 // =================================================================================================
229 
230 template<typename ElementType>
231 utils::Range< IteratorLevelorder< TreeLink const, TreeNode const, TreeEdge const >>
232 levelorder( ElementType const& element )
233 {
234  return {
237  };
238 }
239 
240 template<typename ElementType>
242 levelorder( ElementType& element )
243 {
244  return {
247  };
248 }
249 
250 } // namespace tree
251 } // namespace genesis
252 
253 #endif // include guard
bool operator==(const self_type &other) const
utils::Range< IteratorLevelorder< TreeLink const, TreeNode const, TreeEdge const > > levelorder(ElementType const &element)
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:95
Header of Tree class.
IteratorLevelorder & operator=(IteratorLevelorder const &)=default
bool operator!=(const self_type &other) const