A toolkit for working with phylogenetic data.
v0.22.1
broker.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2019 Lucas Czech and HITS gGmbH
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 
32 
33 #include <algorithm>
34 #include <cassert>
35 #include <string>
36 
38 
39 namespace genesis {
40 namespace tree {
41 
42 // =================================================================================================
43 // Modifiers
44 // =================================================================================================
45 
47 {
48  stack_.clear();
49 }
50 
52 {
53  stack_.push_front(node);
54 }
55 
57 {
58  stack_.push_front(std::move(node));
59 }
60 
62 {
63  stack_.push_back(node);
64 }
65 
67 {
68  stack_.push_back(std::move(node));
69 }
70 
72 {
73  stack_.pop_front();
74 }
75 
77 {
78  stack_.pop_back();
79 }
80 
81 // =================================================================================================
82 // State Functions
83 // =================================================================================================
84 
86 {
87  // we use a stack containing the parents of each subtree. whenever we enter a new subtree,
88  // we push its parent to the stack and increase its rank count while encountering its immediate
89  // children.
90  std::deque<NewickBrokerElement const*> parent_stack;
91 
92  // iterate over all nodes, starting at the root, and assign ranks to them
93  for (auto n_itr = stack_.cbegin(); n_itr != stack_.cend(); ++n_itr) {
94 
95  // Negative depths indicates wrong initialization during reading.
96  assert( n_itr->depth >= 0 );
97 
98  // prepare the current node
99  n_itr->rank_ = 0;
100 
101  // check if the current node is in a different subtree than the current stack elements. this
102  // is the case when its depths is smaller or equal to the stack elements. then, we have to
103  // leave the subtree (possibly multiple levels, thus the loop) and remove those parents from
104  // the stack
105  while (!parent_stack.empty() && n_itr->depth <= parent_stack.back()->depth) {
106  parent_stack.pop_back();
107  }
108 
109  // now the top element of the stack points to the parent of the current node, so we can
110  // increase its rank counter, because the current node is evidence that the parent has one
111  // more child
112  if (!parent_stack.empty()) {
113  ++(parent_stack.back()->rank_);
114  }
115 
116  // from now on, the current node is the beginning of the subtree for the now following
117  // nodes, so push it to the stack
118  parent_stack.push_back(&*n_itr);
119  }
120 }
121 
123 {
124  size_t sum = 0;
125  for (auto const& node : stack_) {
126  if (node.rank_ == -1) {
127  throw std::logic_error("NewickBroker::assign_ranks() was not called before.");
128  }
129  if (node.rank_ == 0) {
130  ++sum;
131  }
132  }
133  return sum;
134 }
135 
137 {
138  auto const nc = node_count();
139  auto const lc = leaf_count();
140  assert( nc >= lc );
141  return nc - lc;
142 }
143 
145 {
146  return stack_.size();
147 }
148 
150 {
151  long max = -1;
152  for (auto const& node : stack_) {
153  if (node.rank_ == -1) {
154  throw std::logic_error("NewickBroker::assign_ranks() was not called before.");
155  }
156  // if (node.rank_ == 1) {
157  // LOG_WARN << "Node with rank 1 found.";
158  // }
159  max = std::max(node.rank_, max);
160  }
161  return max;
162 }
163 
165 {
166  return max_rank() == 2;
167 }
168 
169 // =================================================================================================
170 // Properties
171 // =================================================================================================
172 
174 {
175  return stack_.empty();
176 }
177 
178 size_t NewickBroker::size() const
179 {
180  return stack_.size();
181 }
182 
183 // =================================================================================================
184 // Element Access
185 // =================================================================================================
186 
188 {
189  return stack_[index];
190 }
191 
192 NewickBrokerElement const& NewickBroker::operator [] (std::size_t index) const
193 {
194  return stack_[index];
195 }
196 
198 {
199  if (index >= stack_.size()) {
200  throw std::out_of_range("__FUNCTION__: out_of_range");
201  }
202  return stack_[index];
203 }
204 
205 NewickBrokerElement const& NewickBroker::at(std::size_t index) const
206 {
207  if (index >= stack_.size()) {
208  throw std::out_of_range("__FUNCTION__: out_of_range");
209  }
210  return stack_[index];
211 }
212 
214 {
215  return stack_.front();
216 }
217 
219 {
220  return stack_.front();
221 }
222 
224 {
225  return stack_.back();
226 }
227 
229 {
230  return stack_.back();
231 }
232 
233 // =================================================================================================
234 // Iterators
235 // =================================================================================================
236 
238 {
239  return stack_.begin();
240 }
241 
243 {
244  return stack_.begin();
245 }
246 
248 {
249  return stack_.end();
250 }
251 
253 {
254  return stack_.end();
255 }
256 
258 {
259  return stack_.cbegin();
260 }
261 
263 {
264  return stack_.cend();
265 }
266 
268 {
269  return stack_.rbegin();
270 }
271 
273 {
274  return stack_.rbegin();
275 }
276 
278 {
279  return stack_.rend();
280 }
281 
283 {
284  return stack_.rend();
285 }
286 
288 {
289  return stack_.crbegin();
290 }
291 
293 {
294  return stack_.crend();
295 }
296 
297 // =================================================================================================
298 // Dump and Debug
299 // =================================================================================================
300 
301 // TODO see PLL newick.c for more stuff than can be validated in a tree!
303 {
304  int cur_depth = 0;
305  for (auto const& node : stack_) {
306  if (node.depth == -1) {
307  LOG_INFO << "Node with depth -1 was found.";
308  return false;
309  }
310  if (node.rank_ == -1) {
311  LOG_INFO << "NewickBroker::assign_ranks() was not called before.";
312  return false;
313  }
314  if (node.rank_ == 1) {
315  LOG_INFO << "Node with rank 1 found.";
316  return false;
317  }
318  if (node.depth > cur_depth + 1) {
319  LOG_INFO << "Node found that increases depth more than 1 compared to parent.";
320  return false;
321  }
322  cur_depth = node.depth;
323  }
324  return true;
325 }
326 
327 std::string NewickBroker::dump() const
328 {
329  std::string out;
330  out += "Tree contains " + std::to_string(node_count()) + " nodes (thereof "
331  + std::to_string(leaf_count()) + " leaves)" + (stack_.empty() ? "." : ":") + "\n";
332  for (auto const& node : stack_) {
333  // indent
334  assert( node.depth != -1 );
335  for (int i = 0; i < node.depth; ++i) {
336  out += " ";
337  }
338 
339  // basic information
340  out += node.name;
341 
342  // values
343  for (std::string const& v : node.values) {
344  out += " :" + v;
345  }
346 
347  // comments
348  for (std::string const& c : node.comments) {
349  out += " [" + c + "]";
350  }
351 
352  // tags
353  for (std::string const& t : node.tags) {
354  out += " {" + t + "}";
355  }
356 
357  // additional information
358  out += (node.rank_ > 0 ? " Rank(" + std::to_string(node.rank_) + ")" : "");
359  out += "\n";
360  }
361  return out;
362 }
363 
364 } // namespace tree
365 } // namespace genesis
reverse_iterator rend()
Reverse version of end().
Definition: broker.cpp:277
const_iterator cend() const
Const version of end().
Definition: broker.cpp:262
NewickBrokerElement & at(std::size_t index)
Provides index based array access to the nodes, doing a boundary check first.
Definition: broker.cpp:197
bool empty() const
Returns whether the stack is empty.
Definition: broker.cpp:173
std::deque< NewickBrokerElement >::reverse_iterator reverse_iterator
Definition: broker.hpp:116
reverse_iterator rbegin()
Returns a reverse iterator to the nodes on the stack.
Definition: broker.cpp:267
bool is_bifurcating() const
Definition: broker.cpp:164
const_iterator cbegin() const
Const version of begin().
Definition: broker.cpp:257
std::deque< NewickBrokerElement >::const_reverse_iterator const_reverse_iterator
Definition: broker.hpp:117
long max_rank() const
Returns the highest rank of the nodes in the tree. assign_ranks() has to be called first...
Definition: broker.cpp:149
double sum(const Histogram &h)
std::string dump() const
Return a readable string representation of the elements of the NewickBroker.
Definition: broker.cpp:327
bool validate() const
Returns true iff the tree is valid. assign_ranks() has to be called first.
Definition: broker.cpp:302
void push_top(NewickBrokerElement const &node)
Definition: broker.cpp:51
size_t size() const
Returns the size of the stack, i.e. the number of nodes stored in the broker.
Definition: broker.cpp:178
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
std::string to_string(T const &v)
Return a string representation of a given value.
Definition: string.hpp:384
NewickBrokerElement & bottom()
Returns a reference to the bottom node of the tree stack.
Definition: broker.cpp:223
const_reverse_iterator crbegin()
Const version of rbegin().
Definition: broker.cpp:287
NewickBrokerElement & top()
Returns a reference to the top node of the tree stack.
Definition: broker.cpp:213
void assign_ranks() const
Iterate over the tree and assign ranks (= number of immediate children) to all nodes.
Definition: broker.cpp:85
size_t node_count() const
Alias for size().
Definition: broker.cpp:144
size_t inner_count() const
Definition: broker.cpp:136
const_reverse_iterator crend()
Const version of rend().
Definition: broker.cpp:292
void clear()
Deletes all nodes from the broker.
Definition: broker.cpp:46
Provides easy and fast logging functionality.
NewickBrokerElement & operator[](std::size_t index)
Provides index based array access to the nodes.
Definition: broker.cpp:187
iterator end()
Returns an iterator to the end of the token list.
Definition: broker.cpp:247
size_t leaf_count() const
Returns the number of leaf nodes in the tree. assign_ranks() has to be called first.
Definition: broker.cpp:122
void push_bottom(NewickBrokerElement const &node)
Definition: broker.cpp:61
std::deque< NewickBrokerElement >::const_iterator const_iterator
Definition: broker.hpp:115
iterator begin()
Returns an iterator to the top of the stack.
Definition: broker.cpp:237
std::deque< NewickBrokerElement >::iterator iterator
Definition: broker.hpp:114
Store the information for one element of a Newick tree.
Definition: element.hpp:60
#define LOG_INFO
Log an info message. See genesis::utils::LoggingLevel.
Definition: logging.hpp:98