A library for working with phylogenetic and population genetic data.
v0.32.0
taxonomy/functions/taxonomy.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TAXONOMY_FUNCTIONS_TAXONOMY_H_
2 #define GENESIS_TAXONOMY_FUNCTIONS_TAXONOMY_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 
36 
37 #include <functional>
38 #include <iosfwd>
39 #include <string>
40 #include <unordered_map>
41 #include <vector>
42 #include <queue>
43 
44 namespace genesis {
45 namespace taxonomy {
46 
47 // =================================================================================================
48 // Tags for Tag Dispatch
49 // =================================================================================================
50 
55 
60 
65 
70 
71 // =================================================================================================
72 // Find Functions
73 // =================================================================================================
74 
78 template< class UnaryPredicate >
79 Taxon const* find_taxon( Taxonomy const& tax, UnaryPredicate p )
80 {
81  return find_taxon( tax, p, DepthFirstSearch{} );
82 }
83 
87 template< class UnaryPredicate >
88 Taxon* find_taxon( Taxonomy& tax, UnaryPredicate p )
89 {
90  return find_taxon(tax, p, DepthFirstSearch{} );
91 }
92 
96 template< class UnaryPredicate >
97 Taxon const* find_taxon( Taxonomy const& tax, UnaryPredicate p, DepthFirstSearch )
98 {
99  for( auto const& c : tax ) {
100  if( p( c ) ) {
101  return &c;
102  }
103  auto rec = find_taxon( c, p, DepthFirstSearch{} );
104  if( rec != nullptr ) {
105  return rec;
106  }
107  }
108  return nullptr;
109 }
110 
114 template< class UnaryPredicate >
115 Taxon const* find_taxon( Taxonomy const& tax, UnaryPredicate p, BreadthFirstSearch )
116 {
117  std::queue< Taxon const* > taxa_queue;
118  for( auto& t : tax ) {
119  taxa_queue.push( &t );
120  }
121 
122  while( not taxa_queue.empty() ) {
123  auto const& cur = *taxa_queue.front();
124  taxa_queue.pop();
125 
126  if( p( cur ) ) {
127  return &cur;
128  }
129 
130  for( auto const& t : cur ) {
131  taxa_queue.push( &t );
132  }
133  }
134  return nullptr;
135 }
136 
140 template< class SearchStrategy, class UnaryPredicate >
141 Taxon* find_taxon( Taxonomy& tax, UnaryPredicate p, SearchStrategy strat )
142 {
143  // Avoid code duplication according to Scott Meyers.
144  auto const& ctax = static_cast< Taxonomy const& >( tax );
145  return const_cast< Taxon* >( find_taxon( ctax, p, strat ));
146 }
147 
151 Taxon const* find_taxon_by_name( Taxonomy const& tax, std::string const& name );
152 
156 Taxon* find_taxon_by_name( Taxonomy& tax, std::string const& name );
157 
161 Taxon const* find_taxon_by_id( Taxonomy const& tax, std::string const& id );
162 
166 Taxon* find_taxon_by_id( Taxonomy& tax, std::string const& id );
167 
171 template< class SearchStrategy >
172 Taxon const* find_taxon_by_name( Taxonomy const& tax, std::string const& name, SearchStrategy strat )
173 {
174  return find_taxon( tax, [&name]( Taxon const& t ){
175  return t.name() == name;
176  }, strat );
177 }
178 
182 template< class SearchStrategy >
183 Taxon* find_taxon_by_name( Taxonomy& tax, std::string const& name, SearchStrategy strat )
184 {
185  // Avoid code duplication according to Scott Meyers.
186  auto const& ctax = static_cast< Taxonomy const& >( tax );
187  return const_cast< Taxon* >( find_taxon_by_name( ctax, name, strat ));
188 }
189 
193 template< class SearchStrategy >
194 Taxon const* find_taxon_by_id( Taxonomy const& tax, std::string const& id, SearchStrategy strat )
195 {
196  return find_taxon( tax, [&id]( Taxon const& t ){
197  return t.id() == id;
198  }, strat );
199 }
200 
204 template< class SearchStrategy >
205 Taxon* find_taxon_by_id( Taxonomy& tax, std::string const& id, SearchStrategy strat )
206 {
207  // Avoid code duplication according to Scott Meyers.
208  auto const& ctax = static_cast< Taxonomy const& >( tax );
209  return const_cast< Taxon* >( find_taxon_by_id<SearchStrategy>( ctax, id, strat ));
210 }
211 
212 // =================================================================================================
213 // Accessors
214 // =================================================================================================
215 
223 size_t taxon_level( Taxon const& taxon );
224 
240 size_t total_taxa_count( Taxonomy const& tax );
241 
261 size_t taxa_count_lowest_levels( Taxonomy const& tax );
262 
274 size_t taxa_count_at_level( Taxonomy const& tax, size_t level );
275 
287 std::vector< size_t > taxa_count_levels( Taxonomy const& tax );
288 
299 size_t taxa_count_with_rank(
300  Taxonomy const& tax,
301  std::string const& rank,
302  bool case_sensitive = false
303 );
304 
320 std::unordered_map< std::string, size_t> taxa_count_ranks(
321  Taxonomy const& tax,
322  bool case_sensitive = false
323 );
324 
328 bool has_unique_ids( Taxonomy const& tax );
329 
330 // =================================================================================================
331 // Modifiers
332 // =================================================================================================
333 
346 void sort_by_name( Taxonomy& tax, bool recursive = true, bool case_sensitive = false );
347 
358 void remove_taxa_at_level( Taxonomy& tax, size_t level );
359 
360 // =================================================================================================
361 // Print and Output
362 // =================================================================================================
363 
370 std::ostream& operator << ( std::ostream& out, Taxonomy const& tax );
371 
386 bool validate( Taxonomy const& taxonomy, bool stop_at_first_error = false );
387 
388 } // namespace taxonomy
389 } // namespace genesis
390 
391 #endif // include guard
genesis::taxonomy::taxa_count_ranks
std::unordered_map< std::string, size_t > taxa_count_ranks(Taxonomy const &tax, bool case_sensitive)
Count the number of Taxa in a Taxonomy per rank.
Definition: functions/taxonomy.cpp:173
genesis::taxonomy::has_unique_ids
bool has_unique_ids(Taxonomy const &tax)
Return true iff all IDs of the Taxa in the Taxonomy are unique.
Definition: functions/taxonomy.cpp:196
genesis::taxonomy::taxon_level
size_t taxon_level(Taxon const &taxon)
Return the level of depth of a given Taxon.
Definition: functions/taxonomy.cpp:78
genesis::taxonomy::DepthFirstSearch
Tag used for find_taxon().
Definition: taxonomy/functions/taxonomy.hpp:54
genesis::taxonomy::find_taxon_by_id
Taxon const * find_taxon_by_id(Taxonomy const &tax, std::string const &id)
Alias for find_taxon_by_id(..., DepthFirstSearch{}).
Definition: functions/taxonomy.cpp:64
genesis::taxonomy::Taxon
Store a Taxon, i.e., an element in a Taxonomy, with its name, rank, ID and sub-taxa.
Definition: taxon.hpp:76
genesis::taxonomy::find_taxon_by_name
Taxon const * find_taxon_by_name(Taxonomy const &tax, std::string const &name)
Alias for find_taxon_by_name(..., DepthFirstSearch{}).
Definition: functions/taxonomy.cpp:54
genesis::taxonomy::validate
bool validate(Taxonomy const &taxonomy, bool stop_at_first_error)
Validate the internal data structures of a Taxonomy and its child Taxa Taxa.
Definition: functions/taxonomy.cpp:269
taxonomy.hpp
genesis::taxonomy::taxa_count_lowest_levels
size_t taxa_count_lowest_levels(Taxonomy const &tax)
Return the number of lowest level Taxa (i.e., taxa without sub-taxa) in the Taxonomy.
Definition: functions/taxonomy.cpp:98
genesis::taxonomy::sort_by_name
void sort_by_name(Taxonomy &tax, bool recursive, bool case_sensitive)
Sort the Taxa of a Taxonomy by their name.
Definition: functions/taxonomy.cpp:217
genesis::taxonomy::Taxon::name
std::string const & name() const
Return the name of this taxon.
Definition: taxon.cpp:131
genesis::taxonomy::find_taxon
Taxon const * find_taxon(Taxonomy const &tax, UnaryPredicate p)
Alias for find_taxon(..., DepthFirstSearch{})
Definition: taxonomy/functions/taxonomy.hpp:79
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::taxonomy::Taxonomy
Store a Taxonomy, i.e., a nested hierarchy of Taxa.
Definition: taxonomy/taxonomy.hpp:96
genesis::taxonomy::total_taxa_count
size_t total_taxa_count(Taxonomy const &tax)
Return the total number of taxa contained in the Taxomony, i.e., the number of (non-unique) names of ...
Definition: functions/taxonomy.cpp:89
taxon.hpp
genesis::taxonomy::taxa_count_with_rank
size_t taxa_count_with_rank(Taxonomy const &tax, std::string const &rank, bool case_sensitive)
Count the number of Taxa in a Taxonomy that have a certain rank assigned to them.
Definition: functions/taxonomy.cpp:148
genesis::taxonomy::taxa_count_levels
std::vector< size_t > taxa_count_levels(Taxonomy const &tax)
Count the number of Taxa at each level of depth in the Taxonomy.
Definition: functions/taxonomy.cpp:125
genesis::taxonomy::taxa_count_at_level
size_t taxa_count_at_level(Taxonomy const &tax, size_t level)
Count the number of Taxa at a certain level of depth in the Taxonomy.
Definition: functions/taxonomy.cpp:111
genesis::taxonomy::remove_taxa_at_level
void remove_taxa_at_level(Taxonomy &tax, size_t level)
Remove all Taxa at a given level of depth in the Taxonomy hierarchy, and all their children.
Definition: functions/taxonomy.cpp:244
genesis::taxonomy::BreadthFirstSearch
Tag used for find_taxon().
Definition: taxonomy/functions/taxonomy.hpp:59
genesis::taxonomy::operator<<
std::ostream & operator<<(std::ostream &out, Taxonomy const &tax)
Print the contents of a Taxonomy, i.e., all nested taxa, up to a limit of 10.
Definition: functions/taxonomy.cpp:260
genesis::taxonomy::Taxon::id
std::string const & id() const
Set the ID of this taxon.
Definition: taxon.cpp:159