A toolkit for working with phylogenetic data.
v0.19.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
broker.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 
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  int 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  return node_count() - leaf_count();
139 }
140 
142 {
143  return stack_.size();
144 }
145 
147 {
148  int max = -1;
149  for (auto const& node : stack_) {
150  if (node.rank_ == -1) {
151  throw std::logic_error("NewickBroker::assign_ranks() was not called before.");
152  }
153  // if (node.rank_ == 1) {
154  // LOG_WARN << "Node with rank 1 found.";
155  // }
156  max = std::max(node.rank_, max);
157  }
158  return max;
159 }
160 
162 {
163  return max_rank() == 2;
164 }
165 
166 // =================================================================================================
167 // Properties
168 // =================================================================================================
169 
171 {
172  return stack_.empty();
173 }
174 
175 size_t NewickBroker::size() const
176 {
177  return stack_.size();
178 }
179 
180 // =================================================================================================
181 // Element Access
182 // =================================================================================================
183 
185 {
186  return stack_[index];
187 }
188 
189 NewickBrokerElement const& NewickBroker::operator [] (std::size_t index) const
190 {
191  return stack_[index];
192 }
193 
195 {
196  if (index >= stack_.size()) {
197  throw std::out_of_range("__FUNCTION__: out_of_range");
198  }
199  return stack_[index];
200 }
201 
202 NewickBrokerElement const& NewickBroker::at(std::size_t index) const
203 {
204  if (index >= stack_.size()) {
205  throw std::out_of_range("__FUNCTION__: out_of_range");
206  }
207  return stack_[index];
208 }
209 
211 {
212  return stack_.front();
213 }
214 
216 {
217  return stack_.front();
218 }
219 
221 {
222  return stack_.back();
223 }
224 
226 {
227  return stack_.back();
228 }
229 
230 // =================================================================================================
231 // Iterators
232 // =================================================================================================
233 
235 {
236  return stack_.begin();
237 }
238 
240 {
241  return stack_.begin();
242 }
243 
245 {
246  return stack_.end();
247 }
248 
250 {
251  return stack_.end();
252 }
253 
255 {
256  return stack_.cbegin();
257 }
258 
260 {
261  return stack_.cend();
262 }
263 
265 {
266  return stack_.rbegin();
267 }
268 
270 {
271  return stack_.rbegin();
272 }
273 
275 {
276  return stack_.rend();
277 }
278 
280 {
281  return stack_.rend();
282 }
283 
285 {
286  return stack_.crbegin();
287 }
288 
290 {
291  return stack_.crend();
292 }
293 
294 // =================================================================================================
295 // Dump and Debug
296 // =================================================================================================
297 
298 // TODO see PLL newick.c for more stuff than can be validated in a tree!
300 {
301  int cur_depth = 0;
302  for (auto const& node : stack_) {
303  if (node.depth == -1) {
304  LOG_INFO << "Node with depth -1 was found.";
305  return false;
306  }
307  if (node.rank_ == -1) {
308  LOG_INFO << "NewickBroker::assign_ranks() was not called before.";
309  return false;
310  }
311  if (node.rank_ == 1) {
312  LOG_INFO << "Node with rank 1 found.";
313  return false;
314  }
315  if (node.depth > cur_depth + 1) {
316  LOG_INFO << "Node found that increases depth more than 1 compared to parent.";
317  return false;
318  }
319  cur_depth = node.depth;
320  }
321  return true;
322 }
323 
324 std::string NewickBroker::dump() const
325 {
326  std::string out;
327  out += "Tree contains " + std::to_string(node_count()) + " nodes (thereof "
328  + std::to_string(leaf_count()) + " leaves)" + (stack_.empty() ? "." : ":") + "\n";
329  for (auto const& node : stack_) {
330  // indent
331  assert( node.depth != -1 );
332  for (int i = 0; i < node.depth; ++i) {
333  out += " ";
334  }
335 
336  // basic information
337  out += node.name;
338 
339  // values
340  for (std::string const& v : node.values) {
341  out += " :" + v;
342  }
343 
344  // comments
345  for (std::string const& c : node.comments) {
346  out += " [" + c + "]";
347  }
348 
349  // tags
350  for (std::string const& t : node.tags) {
351  out += " {" + t + "}";
352  }
353 
354  // additional information
355  out += (node.rank_ > 0 ? " Rank(" + std::to_string(node.rank_) + ")" : "");
356  }
357  return out;
358 }
359 
360 } // namespace tree
361 } // namespace genesis
reverse_iterator rend()
Reverse version of end().
Definition: broker.cpp:274
NewickBrokerElement & at(std::size_t index)
Provides index based array access to the nodes, doing a boundary check first.
Definition: broker.cpp:194
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:264
bool empty() const
Returns whether the stack is empty.
Definition: broker.cpp:170
std::deque< NewickBrokerElement >::const_reverse_iterator const_reverse_iterator
Definition: broker.hpp:117
bool is_bifurcating() const
Definition: broker.cpp:161
void assign_ranks() const
Iterate over the tree and assign ranks (= number of immediate children) to all nodes.
Definition: broker.cpp:85
double sum(const Histogram &h)
void push_top(NewickBrokerElement const &node)
Definition: broker.cpp:51
std::string to_string(T const &v)
Return a string representation of a given value.
Definition: string.hpp:373
const_iterator cbegin() const
Const version of begin().
Definition: broker.cpp:254
NewickBrokerElement & bottom()
Returns a reference to the bottom node of the tree stack.
Definition: broker.cpp:220
size_t size() const
Returns the size of the stack, i.e. the number of nodes stored in the broker.
Definition: broker.cpp:175
int inner_count() const
Definition: broker.cpp:136
const_reverse_iterator crbegin()
Const version of rbegin().
Definition: broker.cpp:284
int leaf_count() const
Returns the number of leaf nodes in the tree. assign_ranks() has to be called first.
Definition: broker.cpp:122
NewickBrokerElement & top()
Returns a reference to the top node of the tree stack.
Definition: broker.cpp:210
const_iterator cend() const
Const version of end().
Definition: broker.cpp:259
std::string dump() const
Return a readable string representation of the elements of the NewickBroker.
Definition: broker.cpp:324
int node_count() const
Alias for size().
Definition: broker.cpp:141
int max_rank() const
Returns the highest rank of the nodes in the tree. assign_ranks() has to be called first...
Definition: broker.cpp:146
bool validate() const
Returns true iff the tree is valid. assign_ranks() has to be called first.
Definition: broker.cpp:299
const_reverse_iterator crend()
Const version of rend().
Definition: broker.cpp:289
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:184
iterator end()
Returns an iterator to the end of the token list.
Definition: broker.cpp:244
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:234
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