A toolkit for working with phylogenetic data.
v0.19.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
path_set.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TREE_ITERATOR_PATH_SET_H_
2 #define GENESIS_TREE_ITERATOR_PATH_SET_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 <iterator>
39 #include <stdexcept>
40 #include <vector>
41 
42 namespace genesis {
43 namespace tree {
44 
45 // =================================================================================================
46 // Forward Declarations
47 // =================================================================================================
48 
49 class Tree;
50 class TreeNode;
51 class TreeEdge;
52 class TreeLink;
53 
54 // =================================================================================================
55 // Path Set Iterator
56 // =================================================================================================
57 
93 template <typename LinkType, typename NodeType, typename EdgeType>
95 {
96 public:
97 
98  // -----------------------------------------------------
99  // Typedefs
100  // -----------------------------------------------------
101 
102  using iterator_category = std::forward_iterator_tag;
104 
105  // -----------------------------------------------------
106  // Constructors and Rule of Five
107  // -----------------------------------------------------
108 
110  : start_( nullptr )
111  , finish_( nullptr )
112  , lca_( nullptr )
113  , link_( nullptr )
114  {}
115 
116  IteratorPathSet( NodeType& start, NodeType& finish, NodeType& lca )
117  : IteratorPathSet( start.link(), finish.link(), lca.link() )
118  {}
119 
120  IteratorPathSet( LinkType& start, LinkType& finish, LinkType& lca )
121  : start_( &start.node().primary_link() )
122  , finish_( &finish.node().primary_link() )
123  , lca_( &lca.node().primary_link() )
124  , link_( start_ )
125  {
126  // Edge case: No real path.
127  if( start_ == finish_ ) {
128  // In this case, the LCA has also to be the same, otherwise it is a wrong LCA.
129  if( lca_ != start_ ) {
130  throw std::runtime_error(
131  "Invalid LCA provided for iterating a path with identical start/finish node."
132  );
133  }
134 
135  // We will just traverse one node, so start at the finish_ node,
136  // and after one incrementation, we will be done.
137  doing_first_part_ = false;
138  return;
139 
140  // Special case: The start is also the LCA. In this case, we go immediately to the
141  // second path (finish_ to lca_), and the LCA (= start) will be visited at the end.
142  } else if( start_ == lca_ ) {
143  doing_first_part_ = false;
144  link_ = finish_;
145  }
146  }
147 
148  ~IteratorPathSet() = default;
149 
150  IteratorPathSet( IteratorPathSet const& ) = default;
151  IteratorPathSet( IteratorPathSet&& ) = default;
152 
153  IteratorPathSet& operator= ( IteratorPathSet const& ) = default;
155 
156  // -----------------------------------------------------
157  // Operators
158  // -----------------------------------------------------
159 
161  {
162  return *this;
163  }
164 
166  {
167  // If we are on the second path (from finish_ to lca_) ...
168  if( ! doing_first_part_ ) {
169 
170  // ... and we reach the LCA, this means, we are completely done iterating, so stop here.
171  if( link_ == lca_ ) {
172  link_ = nullptr;
173  return *this;
174  }
175 
176  // ... and we reach the root, we have an error! The LCA cannot be more upwards than the
177  // root, but even if the root was the LCA, we would have checked this in the above
178  // condition. Thus, the LCA is wrong.
179  if( link_->node().is_root() ) {
180  throw std::runtime_error( "Found invalid LCA while iterating path." );
181  }
182  }
183 
184  // Go to the next node towards the LCA.
185  link_ = &link_->outer().node().primary_link();
186 
187  // If we are on the first path (from start_ to lca_) ...
188  if( doing_first_part_ ) {
189 
190  // ... and we reach the LCA, we are done with the first path.
191  // Start again at finish_ for the second path.
192  if( link_ == lca_ ) {
193  doing_first_part_ = false;
194  link_ = finish_;
195  return *this;
196  }
197 
198  // ... and we reach the root in the firth path, the LCA is wrong,
199  // by the same reasoning as above.
200  if( link_->node().is_root() ) {
201  throw std::runtime_error( "Found invalid LCA while iterating path." );
202  }
203  }
204 
205  return *this;
206  }
207 
209  {
210  self_type tmp = *this;
211  ++(*this);
212  return tmp;
213  }
214 
215  bool operator == (const self_type &other) const
216  {
217  return other.link_ == link_;
218  }
219 
220  bool operator != (const self_type &other) const
221  {
222  return !(other == *this);
223  }
224 
225  // -----------------------------------------------------
226  // Members
227  // -----------------------------------------------------
228 
230  {
231  return link_ == lca_;
232  }
233 
234  bool is_lca() const
235  {
236  return is_last_common_ancestor();
237  }
238 
239  LinkType& link() const
240  {
241  return *link_;
242  }
243 
244  NodeType& node() const
245  {
246  return link_->node();
247  }
248 
249  EdgeType& edge() const
250  {
251  return link_->edge();
252  }
253 
254  LinkType& start_link() const
255  {
256  return *start_;
257  }
258 
259  NodeType& start_node() const
260  {
261  return start_->node();
262  }
263 
264  LinkType& finish_link() const
265  {
266  return *finish_;
267  }
268 
269  NodeType& finish_node() const
270  {
271  return finish_->node();
272  }
273 
274  LinkType& lca_link() const
275  {
276  return *lca_;
277  }
278 
279  NodeType& lca_node() const
280  {
281  return lca_->node();
282  }
283 
284  // -----------------------------------------------------
285  // Data Members
286  // -----------------------------------------------------
287 
288 private:
289 
290  LinkType* const start_;
291  LinkType* const finish_;
292  LinkType* const lca_;
293 
294  LinkType* link_;
295  bool doing_first_part_ = true;
296 };
297 
298 // =================================================================================================
299 // Path Wrapper Functions
300 // =================================================================================================
301 
302 template<typename ElementType>
304 path_set( ElementType const& start, ElementType const& finish, ElementType const& lca )
305 {
306  return {
309  };
310 }
311 
312 template<typename ElementType>
314 path_set( ElementType& start, ElementType& finish, ElementType& lca )
315 {
316  return {
319  };
320 }
321 
322 } // namespace tree
323 } // namespace genesis
324 
325 #endif // include guard
NodeType & start_node() const
Definition: path_set.hpp:259
EdgeType & edge() const
Definition: path_set.hpp:249
IteratorPathSet(LinkType &start, LinkType &finish, LinkType &lca)
Definition: path_set.hpp:120
utils::Range< IteratorPathSet< TreeLink const, TreeNode const, TreeEdge const > > path_set(ElementType const &start, ElementType const &finish, ElementType const &lca)
Definition: path_set.hpp:304
LinkType & link() const
Definition: path_set.hpp:239
std::forward_iterator_tag iterator_category
Definition: path_set.hpp:102
NodeType & node() const
Definition: path_set.hpp:244
bool is_last_common_ancestor() const
Definition: path_set.hpp:229
bool operator==(const self_type &other) const
Definition: path_set.hpp:215
Iterate the path between two TreeNodes (non-linearily), given their lowest common ancestor (LCA)...
Definition: path_set.hpp:94
IteratorPathSet(NodeType &start, NodeType &finish, NodeType &lca)
Definition: path_set.hpp:116
NodeType & lca_node() const
Definition: path_set.hpp:279
LinkType & finish_link() const
Definition: path_set.hpp:264
LinkType & start_link() const
Definition: path_set.hpp:254
IteratorPathSet & operator=(IteratorPathSet const &)=default
Header of Tree class.
bool operator!=(const self_type &other) const
Definition: path_set.hpp:220
LinkType & lca_link() const
Definition: path_set.hpp:274
NodeType & finish_node() const
Definition: path_set.hpp:269