A toolkit for working with phylogenetic data.
v0.18.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
lca_lookup.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TREE_FUNCTION_LCA_LOOKUP_H_
2 #define GENESIS_TREE_FUNCTION_LCA_LOOKUP_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 
35 
36 #include <vector>
37 
38 namespace genesis {
39 namespace tree {
40 
41 // =================================================================================================
42 // Forward Declarations
43 // =================================================================================================
44 
45 class Tree;
46 class TreeNode;
47 
48 // =================================================================================================
49 // LCA Lookup
50 // =================================================================================================
51 
66 class LcaLookup
67 {
68 public:
69 
70  // -------------------------------------------------------------------------
71  // Construction and Rule of Five
72  // -------------------------------------------------------------------------
73 
74  LcaLookup() = default;
75  explicit LcaLookup( Tree const& tree );
76 
77  ~LcaLookup() = default;
78 
79  LcaLookup( LcaLookup const& other ) = default;
80  LcaLookup( LcaLookup&& ) = default;
81 
82  LcaLookup& operator= ( LcaLookup const& other ) = default;
83  LcaLookup& operator= ( LcaLookup&& ) = default;
84 
85  // -------------------------------------------------------------------------
86  // Lookup
87  // -------------------------------------------------------------------------
88 
89  std::size_t operator()( size_t node_index_a, size_t node_index_b, size_t root_index ) const;
90  TreeNode const& operator()( TreeNode const& node_a, TreeNode const& node_b, TreeNode const& root_node ) const;
91 
92  size_t operator()( size_t node_index_a, size_t node_index_b ) const;
93  TreeNode const& operator()( TreeNode const& node_a, TreeNode const& node_b ) const;
94 
95  // -------------------------------------------------------------------------
96  // Internal Helper Functions
97  // -------------------------------------------------------------------------
98 
99 private:
100 
101  void init_( Tree const& tree );
102 
110  size_t eulertour_query_( size_t i, size_t j ) const;
111 
116  size_t lookup_( size_t node_index_a, size_t node_index_b, size_t root_index ) const;
117 
118  // -------------------------------------------------------------------------
119  // Data Members
120  // -------------------------------------------------------------------------
121 
122 private:
123 
128  utils::RangeMinimumQuery eulertour_rmq_;
129 
133  std::vector<size_t> eulertour_order_;
134 
138  std::vector<size_t> eulertour_first_occurrence_;
139 
140  Tree const& tree_;
141  size_t root_idx_;
142 };
143 
144 } // namespace tree
145 } // namespace genesis
146 
147 #endif // include guard
Class that allows to efficiently find the index of the minimum element within an interval of an array...
Fast lookup of the lowest common ancestor (LCA) of two TreeNodes, relative to an arbitrary root node...
Definition: lca_lookup.hpp:66
LcaLookup & operator=(LcaLookup const &other)=default
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:95
std::size_t operator()(size_t node_index_a, size_t node_index_b, size_t root_index) const
Definition: lca_lookup.cpp:59