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