A toolkit for working with phylogenetic data.
v0.19.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
taxonomy/iterator/preorder.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TAXONOMY_ITERATOR_PREORDER_H_
2 #define GENESIS_TAXONOMY_ITERATOR_PREORDER_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 
37 
38 #include <assert.h>
39 #include <functional>
40 #include <iterator>
41 #include <stack>
42 
43 namespace genesis {
44 namespace taxonomy {
45 
46 // =================================================================================================
47 // Preorder For Each
48 // =================================================================================================
49 
60 inline void preorder_for_each(
61  Taxonomy& tax,
62  std::function< void( Taxon& )> fn,
63  bool include_inner_taxa = true
64 ) {
65  for( auto& t : tax ) {
66  if( include_inner_taxa || t.size() == 0 ) {
67  fn( t );
68  }
69 
70  preorder_for_each( t, fn, include_inner_taxa );
71  }
72 }
73 
84 inline void preorder_for_each(
85  Taxonomy const& tax,
86  std::function< void( Taxon const& )> fn,
87  bool include_inner_taxa = true
88 ) {
89  for( auto const& t : tax ) {
90  if( include_inner_taxa || t.size() == 0 ) {
91  fn( t );
92  }
93 
94  preorder_for_each( t, fn, include_inner_taxa );
95  }
96 }
97 
98 // =================================================================================================
99 // Preorder Iterator
100 // =================================================================================================
101 
102 template <typename TaxonomyType, typename TaxonType>
104 {
105 
106 public:
107 
108  // -----------------------------------------------------
109  // Typedefs
110  // -----------------------------------------------------
111 
112  using iterator_category = std::forward_iterator_tag;
114 
115  // -----------------------------------------------------
116  // Constructors and Rule of Five
117  // -----------------------------------------------------
118 
120  {}
121 
122  explicit IteratorPreorder( TaxonomyType& taxonomy )
123  {
124  // Add the child taxa to the stack, backwards, so that the top one is the one we
125  // want to visit first.
126  for( size_t i = 0; i < taxonomy.size(); ++i ) {
127  stack_.push( &taxonomy.at( taxonomy.size() - 1 - i ));
128  }
129  }
130 
131  ~IteratorPreorder() = default;
132 
133  IteratorPreorder( IteratorPreorder const& ) = default;
134  IteratorPreorder( IteratorPreorder&& ) = default;
135 
136  IteratorPreorder& operator= ( IteratorPreorder const& ) = default;
138 
139  // -----------------------------------------------------
140  // Operators
141  // -----------------------------------------------------
142 
144  {
145  return *this;
146  }
147 
149  {
150  // Get the current stack top and remove it. We will then prepare its children for visit
151  // by adding them to the stack.
152  auto cur_tax = stack_.top();
153  stack_.pop();
154 
155  // Add the child taxa to the stack, backwards, so that the top one is the one we
156  // want to visit first.
157  auto const cur_size = cur_tax->size();
158  for( size_t i = 0; i < cur_size; ++i ) {
159  stack_.push( &cur_tax->at( cur_size - 1 - i ));
160  }
161 
162  return *this;
163  }
164 
166  {
167  self_type tmp = *this;
168  ++(*this);
169  return tmp;
170  }
171 
172  bool operator == (const self_type &other) const
173  {
174  return other.stack_ == stack_;
175  }
176 
177  bool operator != (const self_type &other) const
178  {
179  return !(other == *this);
180  }
181 
182  // -----------------------------------------------------
183  // Members
184  // -----------------------------------------------------
185 
186  TaxonType& taxon() const
187  {
188  return *stack_.top();
189  }
190 
191  // -----------------------------------------------------
192  // Data Members
193  // -----------------------------------------------------
194 
195 private:
196 
197  std::stack< TaxonType* > stack_;
198 };
199 
200 // =================================================================================================
201 // Preorder Wrapper Functions
202 // =================================================================================================
203 
204 template<typename TaxonomyType>
206 inline preorder( TaxonomyType const& taxonomy )
207 {
208  return {
211  };
212 }
213 
214 template<typename TaxonomyType>
216 inline preorder( TaxonomyType& taxonomy )
217 {
218  return {
221  };
222 }
223 
224 } // namespace taxonomy
225 } // namespace genesis
226 
227 #endif // include guard
utils::Range< IteratorPreorder< Taxonomy const, Taxon const > > preorder(TaxonomyType const &taxonomy)
Store a Taxonomy, i.e., a nested hierarchy of Taxa.
void preorder_for_each(Taxonomy &tax, std::function< void(Taxon &)> fn, bool include_inner_taxa=true)
Apply a function to all taxa of the Taxonomy, traversing it in preorder.
IteratorPreorder & operator=(IteratorPreorder const &)=default
bool operator!=(const self_type &other) const
Store a Taxon, i.e., an element in a Taxonomy, with its name, rank and sub-taxa.
Definition: taxon.hpp:76
bool operator==(const self_type &other) const