1 #ifndef TERRACES_TREES_HPP
2 #define TERRACES_TREES_HPP
3
4 #include <array>
5 #include <cassert>
6 #include <cstdint>
7 #include <iosfwd>
8 #include <sstream>
9 #include <stack>
10 #include <string>
11 #include <unordered_map>
12 #include <vector>
13
14 #include "definitions.hpp"
15
16 namespace terraces {
17
18 /**
19 * Represents a node of a rooted tree.
20 * Its three neighbor indices are stored in \ref data and
21 * in the rooted case can be accessed using \ref lchild, \ref rchild
22 * and \ref parent.
23 */
24 struct node {
nodeterraces::node25 node() : data{{none, none, none, none}} {}
nodeterraces::node26 node(index parent, index left, index right, index taxon)
27 : data{{parent, left, right, taxon}} {}
28 /* data[0]: parent
29 * data[1]: left child
30 * data[2]: right child
31 * data[3]: taxon index */
32 std::array<index, 4> data = {{none, none, none, none}};
33
parentterraces::node34 index parent() const { return data[0]; }
parentterraces::node35 index& parent() { return data[0]; }
36
lchildterraces::node37 index lchild() const { return data[1]; }
lchildterraces::node38 index& lchild() { return data[1]; }
39
rchildterraces::node40 index rchild() const { return data[2]; }
rchildterraces::node41 index& rchild() { return data[2]; }
42
childterraces::node43 index child(bool right) const { return data[1u + bool(right)]; }
childterraces::node44 index& child(bool right) { return data[1u + bool(right)]; }
45
taxonterraces::node46 index taxon() const { return data[3]; }
taxonterraces::node47 index& taxon() { return data[3]; }
48
operator ==terraces::node49 bool operator==(const node& o) const { return data == o.data; }
50
operator !=terraces::node51 bool operator!=(const node& o) const { return !(o == *this); }
52 };
53
54 /** A tree is represented by its nodes. The root of a tree is stored at index 0. */
55 using tree = std::vector<node>;
56
57 /** Stores the name for every node (or leaf) of a tree. */
58 using name_map = std::vector<std::string>;
59
60 /** Helper struct for Newick tree output. */
61 struct newick_t {
62 const tree* t;
63 const name_map* names;
64 };
65
66 /** Helper function for Newick tree output. */
as_newick(const tree & t,const name_map & names)67 inline newick_t as_newick(const tree& t, const name_map& names) { return {&t, &names}; }
68
69 /**
70 * Prints a Newick tree to the given output stream.
71 * @see as_newick
72 */
73 std::ostream& operator<<(std::ostream& s, newick_t tree_pair);
74
75 /** Maps the name of a species to its index in the tree. */
76 using index_map = std::unordered_map<std::string, index>;
77
78 } // namespace terraces
79
80 #endif // TERRACES_TREES_HPP
81