const NONE: usize = usize::MAX;
pub struct Tree {
parent: Vec<usize>,
children: Vec<Vec<usize>>,
name: Vec<Option<u32>>, len: Vec<f64>, }
pub struct Step<'a> {
pub browsed: &'a [u32],
pub sister: &'a [u32],
pub nb: usize, pub ns: usize, pub ov: usize, }
impl Tree {
pub fn parse(s: &str) -> Result<Tree, String> {
let mut t = Tree { parent: vec![NONE], children: vec![vec![]], name: vec![None], len: vec![0.0] };
let b = s.trim().as_bytes();
let end = |from: usize, delims: &[u8]| from + b[from..].iter().position(|c| delims.contains(c)).unwrap_or(b.len() - from);
let (mut cur, mut i) = (0, 0);
while i < b.len() {
match b[i] {
b'(' => cur = t.add(cur),
b',' => { let p = t.parent[cur]; if p == NONE { return Err(format!("bad newick: {s}")) } cur = t.add(p) }
b')' => { cur = t.parent[cur]; if cur == NONE { return Err(format!("bad newick: {s}")) } }
b';' => break,
b':' => {
let j = end(i + 1, b",();");
let v = std::str::from_utf8(&b[i + 1..j]).unwrap().trim();
t.len[cur] = v.parse().map_err(|_| format!("bad branch length '{v}'"))?;
i = j;
continue;
}
_ => {
let j = end(i, b":,();");
let tok = std::str::from_utf8(&b[i..j]).unwrap().trim();
if !tok.is_empty() && t.children[cur].is_empty() {
t.name[cur] = Some(tok.parse().map_err(|_| format!("bad leaf name '{tok}'"))?);
}
i = j;
continue;
}
}
i += 1;
}
Ok(t)
}
fn add(&mut self, p: usize) -> usize {
let n = self.parent.len();
self.parent.push(p);
self.children.push(vec![]);
self.name.push(None);
self.len.push(0.0);
self.children[p].push(n);
n
}
fn is_leaf(&self, n: usize) -> bool { self.children[n].is_empty() }
fn farthest_leaf(&self, n: usize) -> (usize, f64) {
let (mut best, mut stack) = ((n, f64::NEG_INFINITY), vec![(n, 0.0)]);
if self.is_leaf(n) { return (n, 0.0) }
while let Some((x, d)) = stack.pop() {
if x != n && self.is_leaf(x) && d > best.1 { best = (x, d) }
for &c in self.children[x].iter().rev() { stack.push((c, d + self.len[c])) }
}
best
}
pub fn midpoint_newick(&self) -> String {
let (a, _) = self.farthest_leaf(0);
let (mut far, mut prev, mut cdist, mut cur) = (0.0, a, self.len[a], self.parent[a]);
while cur != NONE {
for &c in &self.children[cur] {
if c != prev {
let d = if self.is_leaf(c) { 0.0 } else { self.farthest_leaf(c).1 } + self.len[c];
if cdist + d > far { far = cdist + d }
}
}
prev = cur;
cdist += self.len[prev];
cur = self.parent[prev];
}
let (mut d, mut og) = (0.0, a);
loop {
if og == NONE { og = self.children[0][0]; break }
d += self.len[og];
if d > far / 2.0 { break }
og = self.parent[og];
}
if og == 0 { return self.newick(0, NONE) }
format!("({},{});", self.newick(og, self.parent[og]), self.newick(self.parent[og], og))
}
fn newick(&self, n: usize, from: usize) -> String {
let nbrs: Vec<usize> = self.children[n].iter().copied()
.chain(std::iter::once(self.parent[n]))
.filter(|&x| x != NONE && x != from)
.collect();
if nbrs.is_empty() { return self.name[n].map(|x| x.to_string()).unwrap_or_default() }
if nbrs.len() == 1 && from != NONE { return self.newick(nbrs[0], n) } let inner: Vec<String> = nbrs.iter().map(|&x| self.newick(x, n)).collect();
let s = format!("({})", inner.join(","));
if from == NONE { s + ";" } else { s }
}
fn leaves(&self, n: usize, keep: &impl Fn(u32) -> bool, out: &mut Vec<u32>) {
let mut stack = vec![n];
while let Some(x) = stack.pop() {
match self.name[x] {
Some(id) if self.is_leaf(x) => if keep(id) { out.push(id) },
_ => stack.extend(&self.children[x]),
}
}
}
pub fn walk(&self, start: u32, sp: &[u32], nsp: usize, keep: impl Fn(u32) -> bool, mut f: impl FnMut(Step)) -> Vec<u32> {
let mut browsed = vec![start];
let Some(mut cur) = (0..self.name.len()).find(|&n| self.name[n] == Some(start)) else { return browsed };
let mut flag = vec![0u8; nsp];
flag[sp[start as usize] as usize] = 1;
let (mut nb, mut sister) = (1, vec![]);
while self.parent[cur] != NONE {
let p = self.parent[cur];
sister.clear();
for &c in &self.children[p] { if c != cur { self.leaves(c, &keep, &mut sister) } }
if !sister.is_empty() {
let (mut ns, mut ov) = (0, 0);
for &x in &sister {
let s = &mut flag[sp[x as usize] as usize];
if *s & 2 == 0 { *s |= 2; ns += 1; if *s & 1 == 1 { ov += 1 } }
}
f(Step { browsed: &browsed, sister: &sister, nb, ns, ov });
nb += ns - ov;
for &x in &sister { flag[sp[x as usize] as usize] = 1 }
browsed.extend_from_slice(&sister);
}
cur = p;
}
browsed
}
}
#[cfg(test)]
mod tests {
use super::Tree;
#[test]
fn midpoint_like_ete3() {
let t = Tree::parse("(1:0.1,2:0.2,(3:0.3,4:0.4)0.9:0.05);").unwrap();
assert_eq!(t.midpoint_newick(), "(4,(3,(1,2)));");
let t = Tree::parse(&t.midpoint_newick()).unwrap();
assert_eq!(t.midpoint_newick(), "(4,(3,(1,2)));"); }
#[test]
fn walk_steps() {
let sp: Vec<u32> = (0..40).map(|i| i / 10).collect();
let t = Tree::parse("((((1,11),21),2),31);").unwrap();
let mut seen = vec![];
let order = t.walk(1, &sp, 4, |x| x != 21, |s| seen.push((s.sister.to_vec(), s.nb, s.ns, s.ov)));
assert_eq!(order, vec![1, 11, 2, 31]);
assert_eq!(seen, vec![(vec![11], 1, 1, 0), (vec![2], 2, 1, 1), (vec![31], 2, 1, 0)]);
}
}