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