A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
tree/tree.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2017 Lucas Czech
4 
5  This program is free software: you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation, either version 3 of the License, or
8  (at your option) any later version.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  Contact:
19  Lucas Czech <lucas.czech@h-its.org>
20  Exelixis Lab, Heidelberg Institute for Theoretical Studies
21  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
22 */
23 
31 #include "genesis/tree/tree.hpp"
32 
34 
37 
38 #include <assert.h>
39 #include <stdexcept>
40 #include <typeinfo>
41 
42 namespace genesis {
43 namespace tree {
44 
45 // =================================================================================================
46 // Construction and Rule of Five
47 // =================================================================================================
48 
63 Tree::Tree( const Tree& other )
64 {
65  // Get a copy of the topology. (Copy swap idiom.)
66  auto res = other.clone_topology();
67 
68  // Instead of using non-covariant clone functions for the data, this might be an option:
69  // http://stackoverflow.com/questions/6924754/return-type-covariance-with-smart-pointers
70  // The typeid assertion could then also move into the base data classes, like this:
71  // http://stackoverflow.com/questions/9477581/force-all-classes-to-implement-override-a-pure-virtual-method-in-multi-level
72 
73  // Copy data.
74  for( size_t i = 0; i < res.links_.size(); ++i ) {
75  // res.links_[i]->data = other.links_[i]->data;
76  }
77  for( size_t i = 0; i < res.nodes_.size(); ++i ) {
78  if( other.node_at(i).has_data() ) {
79  res.node_at(i).reset_data( other.node_at(i).data_ptr()->clone() );
80  }
81 
82  // Some assertions.
83  if( res.node_at(i).has_data() && other.node_at(i).has_data() ) {
84  auto const& res_data = *res.node_at(i).data_ptr();
85  auto const& oth_data = *other.node_at(i).data_ptr();
86  (void) res_data;
87  (void) oth_data;
88  assert( typeid( res_data ) == typeid( oth_data ));
89  } else {
90  assert( ! res.node_at(i).has_data() && ! other.node_at(i).has_data() );
91  }
92  }
93  for( size_t i = 0; i < res.edges_.size(); ++i ) {
94  if( other.edge_at(i).has_data() ) {
95  res.edge_at(i).reset_data( other.edge_at(i).data_ptr()->clone() );
96  }
97 
98  // Some assertions.
99  if( res.edges_[i]->has_data() && other.edge_at(i).has_data() ) {
100  auto const& res_data = *res.edge_at(i).data_ptr();
101  auto const& oth_data = *other.edge_at(i).data_ptr();
102  (void) res_data;
103  (void) oth_data;
104  assert( typeid( res_data ) == typeid( oth_data ));
105  } else {
106  assert( ! res.edge_at(i).has_data() && ! other.edge_at(i).has_data() );
107  }
108  }
109 
110  // Swap with the (currently empty) content of this tree.
111  res.swap( *this );
112 }
113 
119 Tree& Tree::operator = ( Tree const& other )
120 {
121  // Check for self assignment. Just in case.
122  if( &other == this ) {
123  return *this;
124  }
125 
126  // Copy-swap-idiom.
127  Tree temp( other );
128  temp.swap( *this );
129  return *this;
130 }
131 
138 {
139  // Prepare resulting tree.
140  auto res = Tree();
141  res.links_.resize( link_count() );
142  res.nodes_.resize( node_count() );
143  res.edges_.resize( edge_count() );
144  res.root_link_index_ = root_link_index_;
145 
146  // Create all objects. We need two loops per array, because the pointers have to exist
147  // in order to be linked to each other.
148  for( size_t i = 0; i < links_.size(); ++i ) {
149  res.links_[i] = utils::make_unique< TreeLink >();
150  }
151  for( size_t i = 0; i < nodes_.size(); ++i ) {
152  res.nodes_[i] = utils::make_unique< TreeNode >();
153  }
154  for( size_t i = 0; i < edges_.size(); ++i ) {
155  res.edges_[i] = utils::make_unique< TreeEdge >();
156  }
157 
158  // Set all pointers for the topology in a second round of loops.
159  for( size_t i = 0; i < links_.size(); ++i ) {
160  auto const& cur_link = link_at(i);
161  assert( cur_link.index() == i );
162 
163  res.links_[i]->reset_index( i );
164  res.links_[i]->reset_next( res.links_[ cur_link.next().index() ].get() );
165  res.links_[i]->reset_outer( res.links_[ cur_link.outer().index() ].get() );
166  res.links_[i]->reset_node( res.nodes_[ cur_link.node().index() ].get() );
167  res.links_[i]->reset_edge( res.edges_[ cur_link.edge().index() ].get() );
168  }
169  for( size_t i = 0; i < nodes_.size(); ++i ) {
170  auto const& cur_node = node_at(i);
171  assert( cur_node.index() == i );
172 
173  res.nodes_[i]->reset_index( i );
174  res.nodes_[i]->reset_primary_link( res.links_[ cur_node.link().index() ].get() );
175  }
176  for( size_t i = 0; i < edges_.size(); ++i ) {
177  auto const& cur_edge = edge_at(i);
178  assert( cur_edge.index() == i );
179 
180  res.edges_[i]->reset_index( i );
181  res.edges_[i]->reset_primary_link( res.links_[ cur_edge.primary_link().index() ].get() );
182  res.edges_[i]->reset_secondary_link( res.links_[ cur_edge.secondary_link().index() ].get() );
183  }
184 
185  return res;
186 }
187 
191 void Tree::swap( Tree& other )
192 {
193  using std::swap;
194 
195  swap( root_link_index_, other.root_link_index_ );
196 
197  swap( links_, other.links_ );
198  swap( nodes_, other.nodes_ );
199  swap( edges_, other.edges_ );
200 }
201 
208 {
209  root_link_index_ = 0;
210  links_.clear();
211  nodes_.clear();
212  edges_.clear();
213 }
214 
215 // =================================================================================================
216 // Accessors
217 // =================================================================================================
218 
222 bool Tree::empty() const
223 {
224  return links_.empty() && nodes_.empty() && edges_.empty();
225 }
226 
233 {
234  if( links_.empty() ) {
235  throw std::out_of_range( "Cannot return root link. Tree is empty." );
236  }
237  return *links_.at( root_link_index_ ).get();
238 }
239 
245 TreeLink const& Tree::root_link() const
246 {
247  if( links_.empty() ) {
248  throw std::out_of_range( "Cannot return root link. Tree is empty." );
249  }
250  return *links_.at( root_link_index_ ).get();
251 }
252 
259 {
260  if( links_.empty() ) {
261  throw std::out_of_range( "Cannot return root node. Tree is empty." );
262  }
263  return links_.at( root_link_index_ )->node();
264 }
265 
271 TreeNode const& Tree::root_node() const
272 {
273  if( links_.empty() ) {
274  throw std::out_of_range( "Cannot return root node. Tree is empty." );
275  }
276  return links_.at( root_link_index_ )->node();
277 }
278 
284 TreeLink& Tree::link_at(size_t index)
285 {
286  return *links_.at(index).get();
287 }
288 
294 TreeLink const& Tree::link_at(size_t index) const
295 {
296  return *links_.at(index).get();
297 }
298 
304 TreeNode& Tree::node_at(size_t index)
305 {
306  return *nodes_.at(index).get();
307 }
308 
314 TreeNode const& Tree::node_at(size_t index) const
315 {
316  return *nodes_.at(index).get();
317 }
318 
324 TreeEdge& Tree::edge_at(size_t index)
325 {
326  return *edges_.at(index).get();
327 }
328 
334 TreeEdge const& Tree::edge_at(size_t index) const
335 {
336  return *edges_.at(index).get();
337 }
338 
342 size_t Tree::link_count() const
343 {
344  return links_.size();
345 }
346 
350 size_t Tree::node_count() const
351 {
352  return nodes_.size();
353 }
354 
358 size_t Tree::edge_count() const
359 {
360  return edges_.size();
361 }
362 
363 // =================================================================================================
364 // Data Accessors
365 // =================================================================================================
366 
378 {
379  if( val >= links_.size() ) {
380  throw std::runtime_error( "Invalid root link index: " + std::to_string( val ) );
381  }
382  root_link_index_ = val;
383  return *this;
384 }
385 
394 {
395  return links_;
396 }
397 
406 {
407  return nodes_;
408 }
409 
418 {
419  return edges_;
420 }
421 
422 // =================================================================================================
423 // Iterators
424 // =================================================================================================
425 
426 // -------------------------------------------------------------------------
427 // Links
428 // -------------------------------------------------------------------------
429 
431 {
432  return links_.begin();
433 }
434 
436 {
437  return links_.end();
438 }
439 
441 {
442  return links_.cbegin();
443 }
444 
446 {
447  return links_.cend();
448 }
449 
451 {
452  return { links_ };
453 }
454 
456 {
457  return { links_ };
458 }
459 
460 // -------------------------------------------------------------------------
461 // Nodes
462 // -------------------------------------------------------------------------
463 
465 {
466  return nodes_.begin();
467 }
468 
470 {
471  return nodes_.end();
472 }
473 
475 {
476  return nodes_.cbegin();
477 }
478 
480 {
481  return nodes_.cend();
482 }
483 
485 {
486  return { nodes_ };
487 }
488 
490 {
491  return { nodes_ };
492 }
493 
494 // -------------------------------------------------------------------------
495 // Edges
496 // -------------------------------------------------------------------------
497 
499 {
500  return edges_.begin();
501 }
502 
504 {
505  return edges_.end();
506 }
507 
509 {
510  return edges_.cbegin();
511 }
512 
514 {
515  return edges_.cend();
516 }
517 
519 {
520  return { edges_ };
521 }
522 
524 {
525  return { edges_ };
526 }
527 
528 } // namespace tree
529 } // namespace genesis
IteratorEdges begin_edges()
Definition: tree/tree.cpp:498
ContainerType< TreeEdge > EdgeContainerType
Alias for the container type that is used to store TreeEdges.
Definition: tree/tree.hpp:123
IteratorEdges end_edges()
Definition: tree/tree.cpp:503
typename ContainerType< TreeEdge >::const_iterator ConstIteratorEdges
Definition: tree/tree.hpp:132
virtual std::unique_ptr< BaseNodeData > clone() const
Polymorphically copy an instance of this class. Use instead of copy constructor.
Definition: node_data.hpp:134
typename ContainerType< TreeLink >::const_iterator ConstIteratorLinks
Definition: tree/tree.hpp:126
IteratorLinks end_links()
Definition: tree/tree.cpp:435
typename ContainerType< TreeNode >::iterator IteratorNodes
Definition: tree/tree.hpp:128
void swap(SequenceSet &lhs, SequenceSet &rhs)
TreeNode & node_at(size_t index)
Return the TreeNode at a certain index.
Definition: tree/tree.cpp:304
utils::Range< IteratorNodes > nodes()
Definition: tree/tree.cpp:484
std::string to_string(T const &v)
Return a string representation of a given value.
Definition: string.hpp:381
typename ContainerType< TreeNode >::const_iterator ConstIteratorNodes
Definition: tree/tree.hpp:129
Provides some valuable additions to STD.
TreeLink & link_at(size_t index)
Return the TreeLink at a certain index.
Definition: tree/tree.cpp:284
IteratorNodes end_nodes()
Definition: tree/tree.cpp:469
TreeNode & root_node()
Return the TreeNode at the current root of the Tree.
Definition: tree/tree.cpp:258
size_t node_count() const
Return the number of TreeNodes of the Tree.
Definition: tree/tree.cpp:350
ContainerType< TreeNode > NodeContainerType
Alias for the container type that is used to store TreeNodes.
Definition: tree/tree.hpp:118
BaseEdgeData * data_ptr()
Return a pointer to the data.
Definition: edge.hpp:212
utils::Range< IteratorEdges > edges()
Definition: tree/tree.cpp:518
Tree & operator=(Tree const &other)
Assignment operator.
Definition: tree/tree.cpp:119
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:95
bool empty() const
Return whether the Tree is empty (i.e., has no nodes, edges and links).
Definition: tree/tree.cpp:222
Tree clone_topology() const
Return a Tree with the same topology, but without any data.
Definition: tree/tree.cpp:137
bool has_data() const
Return true if the TreeEdge has a data object assigned to it.
Definition: edge.hpp:177
void swap(Tree &other)
Swap.
Definition: tree/tree.cpp:191
LinkContainerType & expose_link_container()
Get the container that stores all TreeLinks of the Tree.
Definition: tree/tree.cpp:393
IteratorNodes begin_nodes()
Definition: tree/tree.cpp:464
virtual std::unique_ptr< BaseEdgeData > clone() const
Polymorphically copy an instance of this class. Use instead of copy constructor.
Definition: edge_data.hpp:134
utils::Range< IteratorLinks > links()
Definition: tree/tree.cpp:450
typename ContainerType< TreeLink >::iterator IteratorLinks
Definition: tree/tree.hpp:125
Provides easy and fast logging functionality.
size_t edge_count() const
Return the number of TreeEdges of the Tree.
Definition: tree/tree.cpp:358
TreeEdge & edge_at(size_t index)
Return the TreeEdge at a certain index.
Definition: tree/tree.cpp:324
void clear()
Deletes all data of the tree, including all links, nodes and edges.
Definition: tree/tree.cpp:207
ContainerType< TreeLink > LinkContainerType
Alias for the container type that is used to store TreeLinks.
Definition: tree/tree.hpp:113
TreeLink & root_link()
Return the TreeLink at the current root of the Tree.
Definition: tree/tree.cpp:232
Tree & reset_root_link_index(size_t val)
Reset the index of the link that is considered to be the root of the Tree.
Definition: tree/tree.cpp:377
Header of Tree class.
bool has_data() const
Return true if the TreeNode has a data object assigned to it.
Definition: node.hpp:146
TreeNode & reset_data(std::unique_ptr< BaseNodeData > data)
Reset the data pointer of this TreeNode.
Definition: node.hpp:239
IteratorLinks begin_links()
Definition: tree/tree.cpp:430
EdgeContainerType & expose_edge_container()
Get the container that stores all TreeEdges of the Tree.
Definition: tree/tree.cpp:417
BaseNodeData * data_ptr()
Return a pointer to the data.
Definition: node.hpp:181
size_t link_count() const
Return the number of TreeLinks of the Tree.
Definition: tree/tree.cpp:342
NodeContainerType & expose_node_container()
Get the container that stores all TreeNodes of the Tree.
Definition: tree/tree.cpp:405
typename ContainerType< TreeEdge >::iterator IteratorEdges
Definition: tree/tree.hpp:131