A toolkit for working with phylogenetic data.
v0.18.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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-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 // Preorder 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 IteratorPreorder( Tree& tree )
80  : IteratorPreorder( tree.root_link() )
81  {}
82 
83  explicit IteratorPreorder( Tree const& tree )
84  : IteratorPreorder( tree.root_link() )
85  {}
86 
87  explicit IteratorPreorder( NodeType& node )
88  : IteratorPreorder( node.primary_link() )
89  {}
90 
91  explicit IteratorPreorder( LinkType& link )
92  : start_( &link )
93  , link_( &link )
94  {
95  push_front_children( &link );
96  stack_.push_front( &link.outer() );
97  }
98 
99  ~IteratorPreorder() = default;
100 
101  IteratorPreorder( IteratorPreorder const& ) = default;
102  IteratorPreorder( IteratorPreorder&& ) = default;
103 
104  IteratorPreorder& operator= ( IteratorPreorder const& ) = default;
106 
107  // -----------------------------------------------------
108  // Operators
109  // -----------------------------------------------------
110 
112  {
113  return *this;
114  }
115 
117  {
118  if (stack_.empty()) {
119  link_ = nullptr;
120  } else {
121  link_ = stack_.front();
122  stack_.pop_front();
123  push_front_children(link_);
124  }
125 
126  return *this;
127  }
128 
130  {
131  self_type tmp = *this;
132  ++(*this);
133  return tmp;
134  }
135 
136  bool operator == (const self_type &other) const
137  {
138  return other.link_ == link_;
139  }
140 
141  bool operator != (const self_type &other) const
142  {
143  return !(other == *this);
144  }
145 
146  // -----------------------------------------------------
147  // Members
148  // -----------------------------------------------------
149 
150  bool is_first_iteration() const
151  {
152  return link_ == start_;
153  }
154 
155  LinkType& link() const
156  {
157  return *link_;
158  }
159 
160  NodeType& node() const
161  {
162  return link_->node();
163  }
164 
165  EdgeType& edge() const
166  {
167  return link_->edge();
168  }
169 
170  LinkType& start_link() const
171  {
172  return *start_;
173  }
174 
175  NodeType& start_node() const
176  {
177  return start_->node();
178  }
179 
180  // -----------------------------------------------------
181  // Internal Helper Functions
182  // -----------------------------------------------------
183 
184 private:
185 
186  void push_front_children( LinkType* link )
187  {
188  // we need to push to a tmp queue first, in order to get the order right.
189  // otherwise, we would still do a preorder traversal, but starting with
190  // the last child of each node instead of the first one.
191  std::deque<LinkType*> tmp;
192  LinkType* c = &link->next();
193  while (c != link) {
194  tmp.push_front( &c->outer() );
195  c = &c->next();
196  }
197  for (LinkType* l : tmp) {
198  stack_.push_front(l);
199  }
200  }
201 
202  // -----------------------------------------------------
203  // Data Members
204  // -----------------------------------------------------
205 
206  // TODO take a stack or vector instead of deque here; maybe reverse pushing order
207 
208  LinkType* const start_;
209  LinkType* link_;
210 
211  std::deque<LinkType*> stack_;
212 };
213 
214 // =================================================================================================
215 // Preorder Wrapper Functions
216 // =================================================================================================
217 
218 template<typename ElementType>
219 utils::Range< IteratorPreorder< TreeLink const, TreeNode const, TreeEdge const >>
220 preorder( ElementType const& element )
221 {
222  return {
225  };
226 }
227 
228 template<typename ElementType>
230 preorder( ElementType& element )
231 {
232  return {
235  };
236 }
237 
238 } // namespace tree
239 } // namespace genesis
240 
241 #endif // include guard
utils::Range< IteratorPreorder< TreeLink const, TreeNode const, TreeEdge const > > preorder(ElementType const &element)
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:95
bool operator!=(const self_type &other) const
IteratorPreorder & operator=(IteratorPreorder const &)=default
Header of Tree class.
bool operator==(const self_type &other) const
std::forward_iterator_tag iterator_category