CompactTree 1.1.0
Loading...
Searching...
No Matches
compact_tree.h
1
5#ifndef COMPACT_TREE_H
6#define COMPACT_TREE_H
7
8// include statements
9#include <cstdint> // std::uint32_t, std::uint64_t
10#include <cstdlib> // std::abs, std::atof
11#include <cstring> // strcmp()
12#include <cerrno> // errno
13#include <deque> // std::deque
14#include <fcntl.h> // O_RDONLY, open(), POSIX_FADV_SEQUENTIAL, posix_fadvise()
15#include <iostream> // std::ostream
16#include <iterator> // std::iterator, std::input_iterator_tag
17#include <limits> // std::numeric_limits<T>::max
18#include <locale> // std::locale
19#include <memory> // std::unique_ptr
20#include <queue> // std::queue
21#include <sstream> // std::ostringstream
22#include <stack> // std::stack
23#include <stdexcept> // std::invalid_argument
24#include <string> // std::string
25#include <tuple> // std::tuple
26#include <unistd.h> // read(), lseek(), close()
27#include <unordered_map> // std::unordered_map
28#include <unordered_set> // std::unordered_set
29#include <utility> // std::make_pair, std::pair
30#include <vector> // std::vector
31
32// define node type, which is a fixed-width unsigned integer (default is 32-bit)
33#if defined CT_NODE_64
34#define CT_NODE_T std::uint64_t
35#else
36#define CT_NODE_T std::uint32_t
37#endif
38
39// define edge length type, which is a floating point number (default is float)
40#if defined CT_LENGTH_DOUBLE
41#define CT_LENGTH_T double
42#define PARSE_LENGTH_FROM_C_STR std::atof
43#define PARSE_LENGTH_FROM_STRING std::stod
44#else
45#define CT_LENGTH_T float
46#define PARSE_LENGTH_FROM_C_STR (float)std::atof
47#define PARSE_LENGTH_FROM_STRING std::stof
48#endif
49
50// general constants
51#define COMPACTTREE_VERSION "1.1.0"
52#define IO_BUFFER_SIZE 16384
53#define ROOT_NODE ((CT_NODE_T)0)
54#define NULL_NODE (std::numeric_limits<CT_NODE_T>::max())
55#define ZERO_LENGTH ((CT_LENGTH_T)0.)
56#define ZERO_THRESH ((CT_LENGTH_T)0.000001)
57
58// compact_tree class
59class compact_tree {
60 private:
64 std::vector<CT_NODE_T> parent; // `parent[i]` is the parent of node `i`
65 std::vector<CT_NODE_T> first_child; // `first_child[i]` is the first child of node `i`
66 std::vector<CT_NODE_T> last_child; // `last_child[i]` is the last child of node `i`
67 std::vector<std::string> label; // `label[i]` is the label of node `i`
68 std::vector<CT_LENGTH_T> length; // `length[i]` is the length of the edge incident to (i.e., going into) node `i`
69
73 size_t num_leaves = 0; // cache the total number of leaves (avoid recalculation)
74
78 compact_tree() {}
79
83 void calc_num_leaves() { CT_NODE_T num_nodes = parent.size(); for(CT_NODE_T curr = 0; curr < num_nodes; ++curr) { if(is_leaf(curr)) { num_leaves += 1; } } }
84
85 public:
94 compact_tree(const char* const input, bool is_fn = true, bool store_labels = true, bool store_lengths = true, size_t reserve = 0);
95
104 compact_tree(const std::string & input, bool is_fn = true, bool store_labels = true, bool store_lengths = true, size_t reserve = 0) : compact_tree(&input[0], is_fn, store_labels, store_lengths, reserve) {}
105
110 compact_tree(const compact_tree & o) : parent(o.parent), first_child(o.first_child), last_child(o.last_child), label(o.label), length(o.length), num_leaves(o.num_leaves) {}
111
118 void print_newick(std::ostream & out, CT_NODE_T node = ROOT_NODE, bool include_semicolon = true) const;
119
125 std::string get_newick(CT_NODE_T node = ROOT_NODE, bool include_semicolon = true) const { std::ostringstream oss; print_newick(oss, node, include_semicolon); return oss.str(); }
126
131 size_t get_num_nodes() const { return parent.size(); }
132
137 size_t get_num_leaves() { if(num_leaves == 0) { calc_num_leaves(); } return num_leaves; }
138
144
149 CT_NODE_T get_root() const { return ROOT_NODE; }
150
156 bool is_root(CT_NODE_T node) const { return node == ROOT_NODE; }
157
163 bool is_leaf(CT_NODE_T node) const { return first_child[node] == NULL_NODE; }
164
170 CT_NODE_T get_parent(CT_NODE_T node) const { return parent[node]; }
171
177 CT_NODE_T get_first_child(CT_NODE_T node) const { return first_child[node]; }
178
184 CT_NODE_T get_last_child(CT_NODE_T node) const { return last_child[node]; }
185
190 bool has_edge_lengths() const { return length.size() != 0; }
191
196 void clear_edge_lengths(bool shrink = true) { if(!length.empty()) { length.clear(); if(shrink) { length.shrink_to_fit(); } } }
197
203 CT_LENGTH_T get_edge_length(CT_NODE_T node) const { return has_edge_lengths() ? length[node] : (CT_LENGTH_T)0.; }
204
208 const std::vector<CT_LENGTH_T> & get_edge_lengths() const { return length; }
209
215 void set_edge_length(CT_NODE_T node, CT_LENGTH_T new_length) {
216 if(!has_edge_lengths()) { length = std::vector<CT_LENGTH_T>(get_num_nodes(), (CT_LENGTH_T)0.); } length[node] = new_length;
217 }
218
223 bool has_labels() const { return label.size() != 0; }
224
229 void clear_labels(bool shrink = true) { if(!label.empty()) { label.clear(); if(shrink) { label.shrink_to_fit(); } } }
230
236 const std::string & get_label(CT_NODE_T node) const { if(has_labels()) { return label[node]; } else { static const std::string empty_string; return empty_string; } }
237
243 void set_label(CT_NODE_T node, const std::string & new_label) {
244 if(!has_labels()) { label = std::vector<std::string>(get_num_nodes(), ""); } label[node] = new_label;
245 }
246
251 const std::vector<std::string> & get_labels() const { return label; }
252
258 void replace_labels(const std::unordered_map<std::string, std::string> & label_map, bool include_internal = true) {
259 if(!has_labels()) { return; }
260 const size_t NUM_NODES = get_num_nodes(); CT_NODE_T curr; std::unordered_map<std::string,std::string>::const_iterator it; std::unordered_map<std::string,std::string>::const_iterator it_end = label_map.cend();
261 for(curr = ROOT_NODE; curr < NUM_NODES; ++curr) {
262 if(is_leaf(curr) || include_internal) {
263 it = label_map.find(label[curr]);
264 if(it != it_end) { label[curr] = it->second; }
265 }
266 }
267 }
268
274 std::tuple<const std::string*, CT_LENGTH_T> operator[](CT_NODE_T i) const { return std::make_tuple(&get_label(i), get_edge_length(i)); }
275
279 class preorder_iterator : public std::iterator<std::input_iterator_tag, CT_NODE_T> {
280 private:
281 CT_NODE_T node;
282 public:
283 typedef CT_NODE_T reference;
284 typedef void pointer;
285 preorder_iterator(CT_NODE_T x) : node(x) {}
286 preorder_iterator(const preorder_iterator & it) : node(it.node) {}
287 preorder_iterator & operator=(const preorder_iterator & it) { node = it.node; return *this; }
288 preorder_iterator & operator++() { ++node; return *this; }
289 preorder_iterator operator++(int) { preorder_iterator tmp(*this); operator++(); return tmp; }
290 bool operator==(const preorder_iterator & rhs) const { return node == rhs.node; }
291 bool operator!=(const preorder_iterator & rhs) const { return node != rhs.node; }
292 CT_NODE_T operator*() const { return node; }
293 };
294
300
306
310 class postorder_iterator : public std::iterator<std::input_iterator_tag, CT_NODE_T> {
311 private:
312 CT_NODE_T node;
313 public:
314 typedef CT_NODE_T reference;
315 typedef void pointer;
316 postorder_iterator(CT_NODE_T x) : node(x) {}
317 postorder_iterator(const postorder_iterator & it) : node(it.node) {}
318 postorder_iterator & operator=(const postorder_iterator & it) { node = it.node; return *this; }
319 postorder_iterator & operator++() { --node; return *this; }
320 postorder_iterator operator++(int) { postorder_iterator tmp(*this); operator++(); return tmp; }
321 bool operator==(const postorder_iterator & rhs) const { return node == rhs.node; }
322 bool operator!=(const postorder_iterator & rhs) const { return node != rhs.node; }
323 CT_NODE_T operator*() const { return node; }
324 };
325
330
336
341 class levelorder_iterator : public std::iterator<std::input_iterator_tag, CT_NODE_T> {
342 private:
343 std::queue<CT_NODE_T> q; compact_tree* tree_ptr;
344 public:
345 typedef CT_NODE_T reference;
346 typedef void pointer;
347 levelorder_iterator(compact_tree* const tp) : tree_ptr(tp) {}
348 levelorder_iterator(const CT_NODE_T root, compact_tree* const tp) : tree_ptr(tp) { q.push(root); }
349 levelorder_iterator(std::queue<CT_NODE_T> x, compact_tree* const tp) : q(x), tree_ptr(tp) {}
350 levelorder_iterator(const levelorder_iterator & o) : q(o.q), tree_ptr(o.tree_ptr) {}
351 levelorder_iterator & operator=(const levelorder_iterator & o) { q = o.q; tree_ptr = o.tree_ptr; return *this; }
352 levelorder_iterator & operator++() { CT_NODE_T x = q.front(); if(tree_ptr->first_child[x] != NULL_NODE) { for(CT_NODE_T child = tree_ptr->first_child[x]; child <= tree_ptr->last_child[x]; ++child) { q.push(child); } } q.pop(); return *this; }
353 levelorder_iterator operator++(int) { levelorder_iterator tmp(*this); operator++(); return tmp; }
354 bool operator==(const levelorder_iterator & rhs) const { return q == rhs.q; }
355 bool operator!=(const levelorder_iterator & rhs) const { return q != rhs.q; }
356 CT_NODE_T operator*() const { return q.front(); }
357 };
358
364
370
374 class leaves_iterator : public std::iterator<std::input_iterator_tag, CT_NODE_T> {
375 private:
376 CT_NODE_T node; const compact_tree* tree_ptr;
377 public:
378 typedef CT_NODE_T reference;
379 typedef void pointer;
380 leaves_iterator(CT_NODE_T x, const compact_tree* const tp) : node(x), tree_ptr(tp) {}
381 leaves_iterator(const leaves_iterator & it) : node(it.node), tree_ptr(it.tree_ptr) {}
382 leaves_iterator & operator=(const leaves_iterator & it) { node = it.node; tree_ptr = it.tree_ptr; return *this; }
383 leaves_iterator & operator++() { CT_NODE_T num_nodes = tree_ptr->get_num_nodes(); while(((++node) < num_nodes) && !(tree_ptr->is_leaf(node))) {} return *this; }
384 leaves_iterator operator++(int) { leaves_iterator tmp(*this); operator++(); return tmp; }
385 bool operator==(const leaves_iterator & rhs) const { return node == rhs.node; }
386 bool operator!=(const leaves_iterator & rhs) const { return node != rhs.node; }
387 CT_NODE_T operator*() const { return node; }
388 };
389
394 leaves_iterator leaves_begin() { CT_NODE_T node = ROOT_NODE; CT_NODE_T num_nodes = get_num_nodes(); if(!is_leaf(node)) { while(((++node) < num_nodes) && (!is_leaf(node))) {} } return leaves_iterator(node, this); }
395
400 leaves_iterator leaves_end() { return leaves_iterator((CT_NODE_T)get_num_nodes(), this); }
401
405 class children_iterator : public std::iterator<std::input_iterator_tag, CT_NODE_T> {
406 private:
407 CT_NODE_T node;
408 public:
409 typedef CT_NODE_T reference;
410 typedef void pointer;
411 children_iterator(CT_NODE_T x) : node(x) {}
412 children_iterator(const children_iterator & o) : node(o.node) {}
413 children_iterator & operator=(const children_iterator & o) { node = o.node; return *this; }
414 children_iterator & operator++() { ++node; return *this; }
415 children_iterator operator++(int) { children_iterator tmp(*this); operator++(); return tmp; }
416 bool operator==(const children_iterator & rhs) const { return node == rhs.node; }
417 bool operator!=(const children_iterator & rhs) const { return node != rhs.node; }
418 CT_NODE_T operator*() const { return node; }
419 };
420
426 children_iterator children_begin(CT_NODE_T node) { return children_iterator(first_child[node]); }
427
433 children_iterator children_end(CT_NODE_T node) { return children_iterator((last_child[node] == NULL_NODE) ? NULL_NODE : last_child[node] + 1); }
434
440 CT_NODE_T find_mrca(const std::unordered_set<CT_NODE_T> & nodes) const;
441
447 compact_tree extract_subtree(CT_NODE_T node);
448
455 double calc_total_bl(bool include_internal = true, bool include_leaves = true) const {
456 if(!(include_internal || include_leaves)) { return 0.; }
457 double tot = 0; CT_NODE_T num_nodes = get_num_nodes();
458 for(CT_NODE_T node = 0; node < num_nodes; ++node) {
459 if(is_leaf(node)) { if(include_leaves) { tot += get_edge_length(node); } }
460 else { if(include_internal) { tot += get_edge_length(node); } }
461 }
462 return tot;
463 }
464
471 double calc_avg_bl(bool include_internal = true, bool include_leaves = true) const {
472 if(!(include_internal || include_leaves)) { return 0.; }
473 double tot = 0; CT_NODE_T num_nodes = get_num_nodes(); CT_NODE_T count = 0;
474 for(CT_NODE_T node = 0; node < num_nodes; ++node) {
475 if(is_leaf(node)) { if(include_leaves) { tot += get_edge_length(node); ++count; } }
476 else { if(include_internal) { tot += get_edge_length(node); ++count; } }
477 }
478 return (count == 0) ? 0. : (tot / count);
479 }
480
487 double calc_dist(CT_NODE_T u, CT_NODE_T v) const {
488 if(u == v) { return 0.; } if(u == parent[v]) { return get_edge_length(v); } if(v == parent[u]) { return get_edge_length(u); }
489 std::unordered_map<CT_NODE_T, double> u_dists; u_dists[u] = 0.; std::unordered_map<CT_NODE_T, double> v_dists; CT_NODE_T c = u; CT_NODE_T p = parent[c]; std::unordered_map<CT_NODE_T, double>::iterator it;
490 while(p != NULL_NODE) { u_dists[p] = u_dists[c] + get_edge_length(c); c = p; p = parent[p]; } c = v; p = parent[c];
491 it = u_dists.find(c); if(it != u_dists.end()) { return it->second + v_dists[c];}
492 while(p != NULL_NODE) { v_dists[p] = v_dists[c] + get_edge_length(c); it = u_dists.find(p); if(it != u_dists.end()) { return it->second + v_dists[p]; } c = p; p = parent[p]; }
493 return -1.; // error, shouldn't reach here
494 }
495
500 std::vector<std::pair<std::pair<CT_NODE_T,CT_NODE_T>, double>> calc_distance_matrix();
501};
502
503// print Newick string
504inline void compact_tree::print_newick(std::ostream & out, CT_NODE_T node, bool include_semicolon) const {
505 // preserve output stream precision and floating-point formatting
506 struct precision_guard {
507 std::ostream & out;
508 std::streamsize old_precision;
509 std::ios_base::fmtflags old_floatfield;
510 std::locale old_locale;
511 precision_guard(std::ostream & stream) : out(stream), old_precision(stream.precision()), old_floatfield(stream.flags() & std::ios_base::floatfield), old_locale(stream.getloc()) { out.unsetf(std::ios_base::floatfield); out.precision(std::numeric_limits<CT_LENGTH_T>::max_digits10); out.imbue(std::locale::classic()); }
512 ~precision_guard() { out.precision(old_precision); out.setf(old_floatfield, std::ios_base::floatfield); out.imbue(old_locale); }
513 } guard(out);
514
515 // set things up
516 std::stack<std::pair<CT_NODE_T, CT_NODE_T>> to_visit;
517 CT_NODE_T curr; CT_NODE_T child;
518 if(!is_leaf(node)) { out << '('; }
519 to_visit.push(std::make_pair(node, first_child[node]));
520
521 // traverse the tree
522 while(!to_visit.empty()) {
523 curr = to_visit.top().first;
524
525 // still have children to visit
526 if(!is_leaf(curr) && (to_visit.top().second <= last_child[curr])) {
527 child = to_visit.top().second;
528 ++(to_visit.top().second);
529
530 // print comma between children
531 if(child != first_child[curr]) { out << ','; }
532
533 // initialize child
534 if(!is_leaf(child)) { out << '('; }
535 to_visit.push(std::make_pair(child, first_child[child]));
536 }
537
538 // finished visiting all children of this node
539 else {
540 to_visit.pop();
541
542 // close parentheses for internal nodes
543 if(!is_leaf(curr)) { out << ')'; }
544
545 // print node label
546 if(label.size() != 0) {
547 const std::string & curr_label = label[curr];
548 if(curr_label.find_first_of(" \t\n\r\f\v()[],:;'\"") != std::string::npos) {
549 out << '\'';
550 for(size_t i = 0; i < curr_label.size(); ++i) {
551 if(curr_label[i] == '\'') { out << "''"; }
552 else { out << curr_label[i]; }
553 }
554 out << '\'';
555 } else { out << curr_label; }
556 }
557
558 // print edge length
559 if(length.size() != 0) { out << ':' << length[curr]; }
560 }
561 }
562
563 // print terminating semicolon
564 if(include_semicolon) { out << ';'; }
565}
566
567// find the MRCA of nodes
568inline CT_NODE_T compact_tree::find_mrca(const std::unordered_set<CT_NODE_T> & nodes) const {
569 std::queue<CT_NODE_T, std::deque<CT_NODE_T>> to_visit(std::deque<CT_NODE_T>(nodes.begin(), nodes.end()));
570 std::unordered_map<CT_NODE_T, CT_NODE_T> count; std::unordered_map<CT_NODE_T, CT_NODE_T>::iterator count_it;
571 CT_NODE_T curr_node; CT_NODE_T curr_parent; size_t total = nodes.size();
572 while(!to_visit.empty()) {
573 curr_node = to_visit.front(); to_visit.pop(); count_it = count.find(curr_node); curr_parent = parent[curr_node];
574 if(count_it == count.end()) { // current node hasn't been seen before, initialize its count to 0
575 count_it = count.emplace(curr_node, 0).first;
576 }
577 if((++(count_it->second)) == total) {
578 return curr_node;
579 }
580 if(curr_parent != NULL_NODE) {
581 to_visit.emplace(curr_parent);
582 }
583 }
584 return NULL_NODE; // shouldn't ever reach here
585}
586
587// calculate distance matrix
588inline std::vector<std::pair<std::pair<CT_NODE_T,CT_NODE_T>, double>> compact_tree::calc_distance_matrix() {
589 // set things up
590 const size_t NUM_NODES = get_num_nodes(); const size_t N = get_num_leaves(); const size_t N_MINUS_1 = N - 1;
591 const size_t N_CHOOSE_2 = ((N%2) == 0) ? ((N/2) * N_MINUS_1) : ((N_MINUS_1/2) * N);
592 std::vector<std::pair<std::pair<CT_NODE_T,CT_NODE_T>, double>> dm; dm.reserve(N_CHOOSE_2);
593 std::unordered_map<CT_NODE_T, std::unique_ptr<std::unordered_map<CT_NODE_T, double>>> leaf_dists;
594 CT_NODE_T ch_it; CT_NODE_T ch_it_2;
595 CT_NODE_T curr; CT_NODE_T child; CT_NODE_T child_2; std::unordered_map<CT_NODE_T, double>* curr_leaf_dists;
596 std::unordered_map<CT_NODE_T, double>* child_leaf_dists; std::unordered_map<CT_NODE_T, double>::iterator dist_it; std::unordered_map<CT_NODE_T, double>::iterator dist_it_end;
597 std::unordered_map<CT_NODE_T, double>* child_leaf_dists_2; std::unordered_map<CT_NODE_T, double>::iterator dist_it_2; std::unordered_map<CT_NODE_T, double>::iterator dist_it_2_end;
598
599 // calculate pairwise distances
600 for(curr = NUM_NODES-1; curr != NULL_NODE; --curr) {
601 curr_leaf_dists = leaf_dists.emplace(curr, std::unique_ptr<std::unordered_map<CT_NODE_T, double>>(new std::unordered_map<CT_NODE_T, double>())).first->second.get();
602
603 // for leaves, they have 0 distance to themselves
604 if(is_leaf(curr)) {
605 curr_leaf_dists->emplace(curr, (double)0.);
606 }
607
608 // for internal nodes:
609 else {
610 // calculate all pairwise distances between leaves below this node
611 for(ch_it = first_child[curr]; ch_it < last_child[curr]; ++ch_it) {
612 child = ch_it; child_leaf_dists = leaf_dists[child].get();
613 for(ch_it_2 = ch_it+1; ch_it_2 <= last_child[curr]; ++ch_it_2) {
614 child_2 = ch_it_2; child_leaf_dists_2 = leaf_dists[child_2].get();
615 for(dist_it = child_leaf_dists->begin(), dist_it_end = child_leaf_dists->end(); dist_it != dist_it_end; ++dist_it) {
616 for(dist_it_2 = child_leaf_dists_2->begin(), dist_it_2_end = child_leaf_dists_2->end(); dist_it_2 != dist_it_2_end; ++dist_it_2) {
617 dm.emplace_back(std::make_pair(std::make_pair(dist_it->first,dist_it_2->first), dist_it->second + dist_it_2->second + get_edge_length(child) + get_edge_length(child_2)));
618 }
619 }
620 }
621 }
622
623 // calculate leaf distances to this node
624 for(ch_it = first_child[curr]; ch_it <= last_child[curr]; ++ch_it) {
625 child = ch_it; child_leaf_dists = leaf_dists[child].get();
626 for(dist_it = child_leaf_dists->begin(), dist_it_end = child_leaf_dists->end(); dist_it != dist_it_end; ++dist_it) {
627 curr_leaf_dists->emplace(dist_it->first, dist_it->second + get_edge_length(child));
628 }
629 leaf_dists[child].reset();
630 }
631 }
632 }
633 return dm;
634}
635
636// extract a subtree
637inline compact_tree compact_tree::extract_subtree(CT_NODE_T node) {
638 compact_tree new_tree; std::stack<std::pair<CT_NODE_T, CT_NODE_T>> to_copy; to_copy.push(std::make_pair(node,0)); // first = old tree; second = new tree
639 bool has_lengths = (length.size() != 0); bool has_labels = (label.size() != 0);
640 new_tree.parent.emplace_back(NULL_NODE); new_tree.first_child.emplace_back(NULL_NODE); new_tree.last_child.emplace_back(NULL_NODE);
641 if(has_lengths) { new_tree.length.emplace_back(ZERO_LENGTH); }
642 if(has_labels) { new_tree.label.emplace_back(""); }
643 std::pair<CT_NODE_T, CT_NODE_T> curr;
644 while(!to_copy.empty()) {
645 curr = to_copy.top(); to_copy.pop();
646 if(has_lengths) { new_tree.length[curr.second] = length[curr.first]; }
647 if(has_labels) { new_tree.label[curr.second] = label[curr.first]; }
648 if(!is_leaf(curr.first)) {
649 new_tree.first_child[curr.second] = (CT_NODE_T)new_tree.parent.size();
650 new_tree.last_child[curr.second] = new_tree.first_child[curr.second] + last_child[curr.first] - first_child[curr.first];
651 for(CT_NODE_T child = first_child[curr.first]; child <= last_child[curr.first]; ++child) {
652 CT_NODE_T new_child = (CT_NODE_T)new_tree.parent.size();
653 new_tree.parent.emplace_back(curr.second); new_tree.first_child.emplace_back(NULL_NODE); new_tree.last_child.emplace_back(NULL_NODE);
654 if(has_lengths) { new_tree.length.emplace_back(ZERO_LENGTH); }
655 if(has_labels) { new_tree.label.emplace_back(""); }
656 to_copy.push(std::make_pair(child,new_child));
657 }
658 }
659 }
660 return new_tree;
661}
662
663// compact_tree constructor (putting it last because it's super long)
664inline compact_tree::compact_tree(const char* const input, bool is_fn, bool store_labels, bool store_lengths, size_t reserve) {
665 // reserve space up-front (if given `reserve`) to reduce resizing (save time)
666 std::vector<CT_NODE_T> num_children;
667 if(reserve != 0) { parent.reserve(reserve); first_child.reserve(reserve); last_child.reserve(reserve); num_children.reserve(reserve); if(store_lengths) { length.reserve(reserve); } if(store_labels) { label.reserve(reserve); } }
668
669 // set up file input: https://stackoverflow.com/a/17925143/2134991
670 int fd = -1;
671 struct fd_guard { int* fd; ~fd_guard() { if(*fd != -1) { close(*fd); } } } close_fd{&fd};
672 size_t bytes_read = 0; size_t i; // variables to help with reading
673 const size_t INPUT_LEN = std::strlen(input); size_t input_i = 0; // variables to help with reading from Newick string specifically
674 char buf[IO_BUFFER_SIZE + 1]; // buffer for reading
675 std::string str_buf; // helper string buffer
676 std::istringstream length_stream(str_buf); // helper istringstream for handling different locales
677 length_stream.imbue(std::locale::classic());
678 if(is_fn) {
679 fd = open(input, O_RDONLY);
680 if(fd == -1) {
681 throw std::invalid_argument("Error opening file" + std::string(": ") + std::string(input));
682 }
683 posix_fadvise(fd, 0, 0, POSIX_FADV_SEQUENTIAL);
684 }
685
686 // parse the Newick string twice: first to count children, then to create the tree
687 for(size_t pass = 0; pass < 2; ++pass) {
688 // set up initial Newick parsing state
689 size_t curr_node = ROOT_NODE; // current node (temporary ID in pass 1, final ID in pass 2)
690 size_t parse_node = ROOT_NODE; // temporary preorder ID (pass 2 only)
691 size_t next_parse_node = 1; // next temporary preorder ID (pass 2 only)
692 size_t next_node = 1; // next available final node ID (pass 2 only)
693 std::stack<std::pair<size_t, size_t>> parse_parent; // first = parent ID; second = temporary preorder ID
694 bool parse_done = false; // finished parsing current pass?
695 bool parse_length = false; // parsing a length right now?
696 bool parse_label = false; // parsing a label right now?
697 bool parse_label_single = false; // parsing a single-quote label right now?
698 bool parse_label_double = false; // parsing a double-quote label right now?
699 bool parse_label_quote_pending = false; // encountered a possible closing quote (might be escaped)
700 bool parse_comment = false; // parsing a comment [...] right now?
701 str_buf.clear();
702
703 // initialize storage for the current pass
704 if(pass == 0) {
705 num_children.emplace_back(0); // create empty root node
706 } else {
707 parent.resize(num_children.size(), NULL_NODE);
708 first_child.resize(num_children.size(), NULL_NODE);
709 last_child.resize(num_children.size(), NULL_NODE);
710 if(store_lengths) { length.resize(num_children.size(), ZERO_LENGTH); }
711 if(store_labels) { label.resize(num_children.size(), ""); }
712 }
713
714 // read Newick tree byte-by-byte
715 while(!parse_done) {
716 // either read from file or from Newick C string
717 if(is_fn) {
718 ssize_t read_result;
719 do {
720 read_result = read(fd, buf, IO_BUFFER_SIZE);
721 } while((read_result == -1) && (errno == EINTR));
722 bytes_read = (read_result < 0) ? (size_t)(-1) : (size_t)read_result;
723 } else {
724 if(input_i == INPUT_LEN) { // finished parsing string
725 bytes_read = 0;
726 } else {
727 if((input_i + IO_BUFFER_SIZE) <= INPUT_LEN) {
728 bytes_read = IO_BUFFER_SIZE;
729 } else { // fewer than IO_BUFFER_SIZE bytes left in Newick string (input)
730 bytes_read = INPUT_LEN - input_i;
731 }
732 std::memcpy(buf, input+input_i, bytes_read); input_i += bytes_read;
733 }
734 }
735
736 // handle done reading (!bytes_read) and read failed (bytes_read == -1)
737 if(!bytes_read || bytes_read == (size_t)(-1)) {
738 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
739 }
740
741 // iterate over the characters in the buffer
742 for(i = 0; (i < bytes_read) && !parse_done; ++i) {
743 // currently parsing a comment (ignore for now)
744 if(parse_comment) {
745 // reached end of comment
746 if(buf[i] == ']') {
747 parse_comment = false;
748 }
749 }
750
751 // currently parsing an edge length
752 else if(parse_length) {
753 switch(buf[i]) {
754 // finished parsing edge length
755 case ',':
756 case ')':
757 case ';':
758 if((pass == 1) && store_lengths) { length_stream.clear(); length_stream.str(str_buf); length_stream >> length[curr_node]; }
759 parse_length = false; --i; break; // need to re-read this character
760
761 // edge comment (ignore for now)
762 case '[':
763 parse_comment = true; break;
764
765 // character within edge length
766 default:
767 if((pass == 1) && store_lengths) { str_buf.push_back(buf[i]); } break;
768 }
769 }
770
771 // currently parsing a node label
772 else if(parse_label) {
773 // parsing quoted label ('' or ""), so blindly add next char to label
774 if(parse_label_single || parse_label_double) {
775 if(parse_label_quote_pending) {
776 if((parse_label_single && (buf[i] == '\'')) || (parse_label_double && (buf[i] == '"'))) {
777 if((pass == 1) && store_labels) { str_buf.push_back(buf[i]); }; parse_label_quote_pending = false;
778 } else {
779 parse_label = false; parse_label_single = false; parse_label_double = false; parse_label_quote_pending = false; --i;
780 }
781 } else if((parse_label_single && (buf[i] == '\'')) || (parse_label_double && (buf[i] == '"'))) {
782 parse_label_quote_pending = true;
783 } else {
784 if((pass == 1) && store_labels) { str_buf.push_back(buf[i]); }
785 }
786 }
787
788 // parsing non-quoted label, so check next char for validity before adding
789 else {
790 switch(buf[i]) {
791 case ':': case ',': case ')': case ';':
792 parse_label = false; --i; break; // finished label, so need to re-read this character
793 case '[':
794 parse_comment = true; break;
795 default:
796 if((pass == 1) && store_labels) { str_buf.push_back(buf[i]); }; break;
797 }
798 }
799
800 // if we finished parsing the label, finalize it
801 if(!parse_label) {
802 if((pass == 1) && store_labels) { label[curr_node] = str_buf; }; parse_label = false;
803 }
804 }
805
806 // all other symbols
807 else {
808 switch(buf[i]) {
809 // ignore whitespace outside of labels
810 case ' ':
811 case '\t':
812 case '\n':
813 case '\r':
814 case '\f':
815 case '\v':
816 break;
817
818 // end of Newick string
819 case ';':
820 if((curr_node != ROOT_NODE) || !parse_parent.empty()) {
821 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
822 }
823 if(pass == 0) {
824 parse_done = true;
825 break;
826 }
827 if((parse_node != ROOT_NODE) || (next_parse_node != num_children.size()) || (next_node != num_children.size())) {
828 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
829 }
830 return;
831
832 // go to new child
833 case '(':
834 if(pass == 0) {
835 if((num_children[curr_node] == (NULL_NODE - 1)) || (num_children.size() >= NULL_NODE)) {
836 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
837 }
838 ++num_children[curr_node];
839 parse_parent.push(std::make_pair(curr_node,curr_node));
840 num_children.emplace_back(0);
841 curr_node = num_children.size() - 1;
842 } else {
843 if((parse_node >= num_children.size()) || (num_children[parse_node] == 0) || (next_node > num_children.size()) || ((size_t)num_children[parse_node] > (num_children.size() - next_node)) || (next_parse_node >= num_children.size())) {
844 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
845 }
846 first_child[curr_node] = (CT_NODE_T)next_node;
847 last_child[curr_node] = (CT_NODE_T)(next_node + num_children[parse_node] - 1);
848 parse_parent.push(std::make_pair(curr_node,parse_node));
849 curr_node = next_node;
850 parent[curr_node] = (CT_NODE_T)parse_parent.top().first;
851 next_node += num_children[parse_node];
852 parse_node = next_parse_node++;
853 }
854 break;
855
856 // go to parent
857 case ')':
858 if(parse_parent.empty() || ((pass == 1) && (curr_node != last_child[parse_parent.top().first]))) {
859 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
860 }
861 curr_node = parse_parent.top().first;
862 parse_node = parse_parent.top().second;
863 parse_parent.pop();
864 break;
865
866 // go to new sibling
867 case ',':
868 if(parse_parent.empty()) {
869 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
870 }
871 if(pass == 0) {
872 if((num_children[parse_parent.top().first] == (NULL_NODE - 1)) || (num_children.size() >= NULL_NODE)) {
873 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
874 }
875 ++num_children[parse_parent.top().first];
876 num_children.emplace_back(0);
877 curr_node = num_children.size() - 1;
878 } else {
879 if((curr_node >= last_child[parse_parent.top().first]) || (next_parse_node >= num_children.size())) {
880 throw std::invalid_argument((is_fn ? "Invalid Newick file" : "Invalid Newick string") + std::string(": ") + std::string(input));
881 }
882 ++curr_node;
883 parent[curr_node] = (CT_NODE_T)parse_parent.top().first;
884 parse_node = next_parse_node++;
885 }
886 break;
887
888 // node comment (ignore for now)
889 case '[':
890 parse_comment = true; break;
891
892 // edge length
893 case ':':
894 if(store_lengths) { str_buf.clear(); } parse_length = true; break;
895
896 // about to parse a node label in single quotes ('')
897 case '\'':
898 if(store_labels) { str_buf.clear(); }
899 parse_label_quote_pending = false; parse_label = true; parse_label_single = true; break;
900
901 // about to parse a node label in double quotes ("")
902 case '"':
903 if(store_labels) { str_buf.clear(); }
904 parse_label_quote_pending = false; parse_label = true; parse_label_double = true; break;
905
906 // about to start a node label without quotes
907 default:
908 if(store_labels) { str_buf.clear(); }
909 parse_label = true; --i; break; // need to re-read this character (it's part of the label)
910 }
911 }
912 }
913 }
914 // reset input for the second pass
915 if(pass == 0) {
916 if(is_fn) {
917 if(lseek(fd, 0, SEEK_SET) == (off_t)-1) {
918 throw std::invalid_argument("Invalid Newick file" + std::string(": ") + std::string(input));
919 }
920 } else {
921 input_i = 0;
922 }
923 }
924 }
925}
926#endif
Definition compact_tree.h:405
Definition compact_tree.h:374
Definition compact_tree.h:341
Definition compact_tree.h:310
Definition compact_tree.h:279
Definition compact_tree.h:59
CT_NODE_T get_root() const
Definition compact_tree.h:149
bool has_edge_lengths() const
Definition compact_tree.h:190
const std::vector< std::string > & get_labels() const
Definition compact_tree.h:251
CT_NODE_T find_mrca(const std::unordered_set< CT_NODE_T > &nodes) const
Definition compact_tree.h:568
double calc_dist(CT_NODE_T u, CT_NODE_T v) const
Definition compact_tree.h:487
postorder_iterator postorder_begin()
Definition compact_tree.h:329
bool is_leaf(CT_NODE_T node) const
Definition compact_tree.h:163
void clear_labels(bool shrink=true)
Definition compact_tree.h:229
leaves_iterator leaves_end()
Definition compact_tree.h:400
void set_edge_length(CT_NODE_T node, CT_LENGTH_T new_length)
Definition compact_tree.h:215
children_iterator children_end(CT_NODE_T node)
Definition compact_tree.h:433
const std::vector< CT_LENGTH_T > & get_edge_lengths() const
Definition compact_tree.h:208
size_t get_num_leaves()
Definition compact_tree.h:137
size_t get_num_nodes() const
Definition compact_tree.h:131
compact_tree(const std::string &input, bool is_fn=true, bool store_labels=true, bool store_lengths=true, size_t reserve=0)
Definition compact_tree.h:104
CT_NODE_T get_parent(CT_NODE_T node) const
Definition compact_tree.h:170
double calc_total_bl(bool include_internal=true, bool include_leaves=true) const
Definition compact_tree.h:455
levelorder_iterator levelorder_begin()
Definition compact_tree.h:363
preorder_iterator preorder_end()
Definition compact_tree.h:305
bool is_root(CT_NODE_T node) const
Definition compact_tree.h:156
CT_NODE_T get_last_child(CT_NODE_T node) const
Definition compact_tree.h:184
void print_newick(std::ostream &out, CT_NODE_T node=ROOT_NODE, bool include_semicolon=true) const
Definition compact_tree.h:504
CT_LENGTH_T get_edge_length(CT_NODE_T node) const
Definition compact_tree.h:203
preorder_iterator preorder_begin()
Definition compact_tree.h:299
void replace_labels(const std::unordered_map< std::string, std::string > &label_map, bool include_internal=true)
Definition compact_tree.h:258
const std::string & get_label(CT_NODE_T node) const
Definition compact_tree.h:236
double calc_avg_bl(bool include_internal=true, bool include_leaves=true) const
Definition compact_tree.h:471
levelorder_iterator levelorder_end()
Definition compact_tree.h:369
std::tuple< const std::string *, CT_LENGTH_T > operator[](CT_NODE_T i) const
Definition compact_tree.h:274
void set_label(CT_NODE_T node, const std::string &new_label)
Definition compact_tree.h:243
bool has_labels() const
Definition compact_tree.h:223
postorder_iterator postorder_end()
Definition compact_tree.h:335
compact_tree(const compact_tree &o)
Definition compact_tree.h:110
children_iterator children_begin(CT_NODE_T node)
Definition compact_tree.h:426
size_t get_num_internal()
Definition compact_tree.h:143
std::vector< std::pair< std::pair< CT_NODE_T, CT_NODE_T >, double > > calc_distance_matrix()
Definition compact_tree.h:588
leaves_iterator leaves_begin()
Definition compact_tree.h:394
std::string get_newick(CT_NODE_T node=ROOT_NODE, bool include_semicolon=true) const
Definition compact_tree.h:125
compact_tree extract_subtree(CT_NODE_T node)
Definition compact_tree.h:637
void clear_edge_lengths(bool shrink=true)
Definition compact_tree.h:196
CT_NODE_T get_first_child(CT_NODE_T node) const
Definition compact_tree.h:177