64 std::vector<CT_NODE_T> parent;
65 std::vector<CT_NODE_T> first_child;
66 std::vector<CT_NODE_T> last_child;
67 std::vector<std::string> label;
68 std::vector<CT_LENGTH_T> length;
73 size_t num_leaves = 0;
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; } } }
94 compact_tree(
const char*
const input,
bool is_fn =
true,
bool store_labels =
true,
bool store_lengths =
true,
size_t reserve = 0);
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) {}
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) {}
118 void print_newick(std::ostream & out, CT_NODE_T node = ROOT_NODE,
bool include_semicolon =
true)
const;
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(); }
137 size_t get_num_leaves() {
if(num_leaves == 0) { calc_num_leaves(); }
return num_leaves; }
156 bool is_root(CT_NODE_T node)
const {
return node == ROOT_NODE; }
163 bool is_leaf(CT_NODE_T node)
const {
return first_child[node] == NULL_NODE; }
170 CT_NODE_T
get_parent(CT_NODE_T node)
const {
return parent[node]; }
196 void clear_edge_lengths(
bool shrink =
true) {
if(!length.empty()) { length.clear();
if(shrink) { length.shrink_to_fit(); } } }
229 void clear_labels(
bool shrink =
true) {
if(!label.empty()) { label.clear();
if(shrink) { label.shrink_to_fit(); } } }
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; } }
243 void set_label(CT_NODE_T node,
const std::string & new_label) {
251 const std::vector<std::string> &
get_labels()
const {
return label; }
258 void replace_labels(
const std::unordered_map<std::string, std::string> & label_map,
bool include_internal =
true) {
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; }
279 class preorder_iterator :
public std::iterator<std::input_iterator_tag, CT_NODE_T> {
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; }
310 class postorder_iterator :
public std::iterator<std::input_iterator_tag, CT_NODE_T> {
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; }
341 class levelorder_iterator :
public std::iterator<std::input_iterator_tag, CT_NODE_T> {
343 std::queue<CT_NODE_T> q; compact_tree* tree_ptr;
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(); }
374 class leaves_iterator :
public std::iterator<std::input_iterator_tag, CT_NODE_T> {
376 CT_NODE_T node;
const compact_tree* tree_ptr;
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; }
405 class children_iterator :
public std::iterator<std::input_iterator_tag, CT_NODE_T> {
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; }
440 CT_NODE_T
find_mrca(
const std::unordered_set<CT_NODE_T> & nodes)
const;
455 double calc_total_bl(
bool include_internal =
true,
bool include_leaves =
true)
const {
456 if(!(include_internal || include_leaves)) {
return 0.; }
458 for(CT_NODE_T node = 0; node < num_nodes; ++node) {
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) {
476 else {
if(include_internal) { tot +=
get_edge_length(node); ++count; } }
478 return (count == 0) ? 0. : (tot / count);
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]; }
506 struct precision_guard {
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); }
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]));
522 while(!to_visit.empty()) {
523 curr = to_visit.top().first;
526 if(!
is_leaf(curr) && (to_visit.top().second <= last_child[curr])) {
527 child = to_visit.top().second;
528 ++(to_visit.top().second);
531 if(child != first_child[curr]) { out <<
','; }
534 if(!
is_leaf(child)) { out <<
'('; }
535 to_visit.push(std::make_pair(child, first_child[child]));
543 if(!
is_leaf(curr)) { out <<
')'; }
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) {
550 for(
size_t i = 0; i < curr_label.size(); ++i) {
551 if(curr_label[i] ==
'\'') { out <<
"''"; }
552 else { out << curr_label[i]; }
555 }
else { out << curr_label; }
559 if(length.size() != 0) { out <<
':' << length[curr]; }
564 if(include_semicolon) { out <<
';'; }
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;
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();
605 curr_leaf_dists->emplace(curr, (
double)0.);
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)));
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));
629 leaf_dists[child].reset();
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));
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]; }
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));
664inline compact_tree::compact_tree(
const char*
const input,
bool is_fn,
bool store_labels,
bool store_lengths,
size_t reserve) {
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); } }
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;
673 const size_t INPUT_LEN = std::strlen(input);
size_t input_i = 0;
674 char buf[IO_BUFFER_SIZE + 1];
676 std::istringstream length_stream(str_buf);
677 length_stream.imbue(std::locale::classic());
679 fd = open(input, O_RDONLY);
681 throw std::invalid_argument(
"Error opening file" + std::string(
": ") + std::string(input));
683 posix_fadvise(fd, 0, 0, POSIX_FADV_SEQUENTIAL);
687 for(
size_t pass = 0; pass < 2; ++pass) {
689 size_t curr_node = ROOT_NODE;
690 size_t parse_node = ROOT_NODE;
691 size_t next_parse_node = 1;
692 size_t next_node = 1;
693 std::stack<std::pair<size_t, size_t>> parse_parent;
694 bool parse_done =
false;
695 bool parse_length =
false;
696 bool parse_label =
false;
697 bool parse_label_single =
false;
698 bool parse_label_double =
false;
699 bool parse_label_quote_pending =
false;
700 bool parse_comment =
false;
705 num_children.emplace_back(0);
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(),
""); }
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;
724 if(input_i == INPUT_LEN) {
727 if((input_i + IO_BUFFER_SIZE) <= INPUT_LEN) {
728 bytes_read = IO_BUFFER_SIZE;
730 bytes_read = INPUT_LEN - input_i;
732 std::memcpy(buf, input+input_i, bytes_read); input_i += bytes_read;
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));
742 for(i = 0; (i < bytes_read) && !parse_done; ++i) {
747 parse_comment =
false;
752 else if(parse_length) {
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;
763 parse_comment =
true;
break;
767 if((pass == 1) && store_lengths) { str_buf.push_back(buf[i]); }
break;
772 else if(parse_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;
779 parse_label =
false; parse_label_single =
false; parse_label_double =
false; parse_label_quote_pending =
false; --i;
781 }
else if((parse_label_single && (buf[i] ==
'\'')) || (parse_label_double && (buf[i] ==
'"'))) {
782 parse_label_quote_pending =
true;
784 if((pass == 1) && store_labels) { str_buf.push_back(buf[i]); }
791 case ':':
case ',':
case ')':
case ';':
792 parse_label =
false; --i;
break;
794 parse_comment =
true;
break;
796 if((pass == 1) && store_labels) { str_buf.push_back(buf[i]); };
break;
802 if((pass == 1) && store_labels) { label[curr_node] = str_buf; }; parse_label =
false;
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));
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));
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));
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;
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));
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++;
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));
861 curr_node = parse_parent.top().first;
862 parse_node = parse_parent.top().second;
868 if(parse_parent.empty()) {
869 throw std::invalid_argument((is_fn ?
"Invalid Newick file" :
"Invalid Newick string") + std::string(
": ") + std::string(input));
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));
875 ++num_children[parse_parent.top().first];
876 num_children.emplace_back(0);
877 curr_node = num_children.size() - 1;
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));
883 parent[curr_node] = (CT_NODE_T)parse_parent.top().first;
884 parse_node = next_parse_node++;
890 parse_comment =
true;
break;
894 if(store_lengths) { str_buf.clear(); } parse_length =
true;
break;
898 if(store_labels) { str_buf.clear(); }
899 parse_label_quote_pending =
false; parse_label =
true; parse_label_single =
true;
break;
903 if(store_labels) { str_buf.clear(); }
904 parse_label_quote_pending =
false; parse_label =
true; parse_label_double =
true;
break;
908 if(store_labels) { str_buf.clear(); }
909 parse_label =
true; --i;
break;
917 if(lseek(fd, 0, SEEK_SET) == (off_t)-1) {
918 throw std::invalid_argument(
"Invalid Newick file" + std::string(
": ") + std::string(input));