use std::collections::{BTreeSet, HashSet};
use crate::engines::{
ccode::CharConfig,
dataset::Dataset,
search::{
ScoreWorkspace, calc_ci, calc_ri, collapse_zero_length_branches, collapsed_topology_hash,
maxsteps_sum, minsteps_sum, score_tree,
},
trees::Tree,
};
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct TaxonSet {
bits: Vec<u64>,
}
impl TaxonSet {
fn new(ntax: usize) -> Self {
let words = ntax.div_ceil(64);
Self { bits: vec![0; words] }
}
fn singleton(ntax: usize, t: usize) -> Self {
let mut s = Self::new(ntax);
s.insert(t);
s
}
fn insert(&mut self, t: usize) {
let w = t / 64;
let b = t % 64;
self.bits[w] |= 1u64 << b;
}
fn union_inplace(&mut self, other: &Self) {
for (a, b) in self.bits.iter_mut().zip(&other.bits) {
*a |= *b;
}
}
fn contains(&self, t: usize) -> bool {
let w = t / 64;
let b = t % 64;
((self.bits[w] >> b) & 1) == 1
}
fn is_subset_of(&self, other: &Self) -> bool {
self.bits.iter().zip(&other.bits).all(|(a, b)| (*a & !*b) == 0)
}
fn is_equal(&self, other: &Self) -> bool {
self.bits == other.bits
}
fn intersects(&self, other: &Self) -> bool {
self.bits.iter().zip(&other.bits).any(|(a, b)| (*a & *b) != 0)
}
fn is_compatible_with(&self, other: &Self) -> bool {
self.is_subset_of(other) || other.is_subset_of(self) || !self.intersects(other)
}
fn count(&self) -> usize {
self.bits.iter().map(|w| w.count_ones() as usize).sum()
}
fn taxa(&self) -> Vec<usize> {
let mut out = Vec::new();
for (wi, &word) in self.bits.iter().enumerate() {
let mut w = word;
while w != 0 {
let b = w.trailing_zeros() as usize;
out.push(wi * 64 + b);
w &= w - 1;
}
}
out
}
}
fn collect_clades_rec(tree: &Tree, v: usize, ntax: usize, out: &mut Vec<TaxonSet>) -> TaxonSet {
let node = &tree.nodes[v];
if let Some(t) = node.taxon {
return TaxonSet::singleton(ntax, t);
}
let mut acc = TaxonSet::new(ntax);
for &c in &node.children {
let sub = collect_clades_rec(tree, c, ntax, out);
acc.union_inplace(&sub);
}
out.push(acc.clone());
acc
}
fn rooted_clades_excluding_outgroups(tree: &Tree, outgroups: &[usize]) -> Vec<TaxonSet> {
let mut out = Vec::new();
let whole = collect_clades_rec(tree, tree.root, tree.ntax, &mut out);
let mut ingroup = TaxonSet::new(tree.ntax);
for t in 0..tree.ntax {
if !outgroups.iter().any(|&og| og == t) {
ingroup.insert(t);
}
}
out.into_iter()
.filter(|c| {
let k = c.count();
k > 1
&& !c.is_equal(&whole)
&& !c.is_equal(&ingroup)
&& !outgroups.iter().any(|&og| c.contains(og))
})
.collect()
}
fn normalize_by_outgroups(tree: &Tree, outgroups: &[usize]) -> Tree {
let mut norm = tree
.reroot_by_outgroup_set(outgroups)
.or_else(|_| tree.reroot_by_outgroup(outgroups[0]))
.unwrap_or_else(|_| tree.clone());
norm.canonicalize();
norm
}
pub fn uniq_rooted_by_outgroups(
trees: &[Tree],
outgroups: &[usize],
ds: &Dataset,
cfg: &CharConfig,
ws: &mut ScoreWorkspace,
) -> Vec<Tree> {
let mut seen = HashSet::<u64>::new();
let mut out = Vec::new();
for tr in trees {
let mut norm = normalize_by_outgroups(tr, outgroups);
collapse_zero_length_branches(&mut norm, ds, cfg, ws);
let h = collapsed_topology_hash(&norm);
if seen.insert(h) {
out.push(norm);
}
}
out
}
#[derive(Debug, Clone)]
pub struct ConsensusOutcome {
pub tree: Tree,
pub input_trees: usize,
pub uniq_trees: usize,
pub best_len: u64,
pub ci: f64,
pub ri: Option<f64>,
}
#[derive(Debug, Clone)]
struct ClusterNode {
set: TaxonSet,
parent: Option<usize>,
children: Vec<usize>,
}
fn build_tree_from_rooted_clades_with_outgroups(
ntax: usize,
outgroups: &[usize],
clades: &[TaxonSet],
) -> Result<Tree, String> {
let mut ogset = TaxonSet::new(ntax);
for &t in outgroups {
ogset.insert(t);
}
let mut ingroup_set = TaxonSet::new(ntax);
for t in 0..ntax {
if !ogset.contains(t) {
ingroup_set.insert(t);
}
}
let mut clusters = Vec::<ClusterNode>::new();
clusters.push(ClusterNode { set: ingroup_set.clone(), parent: None, children: Vec::new() });
for c in clades {
if outgroups.iter().any(|&og| c.contains(og)) {
continue;
}
if c.count() <= 1 {
continue;
}
if c.is_equal(&ingroup_set) {
continue;
}
clusters.push(ClusterNode { set: c.clone(), parent: None, children: Vec::new() });
}
for i in 1..clusters.len() {
let mut best_parent: Option<usize> = None;
let mut best_size = usize::MAX;
for j in 0..clusters.len() {
if i == j {
continue;
}
if clusters[i].set.is_subset_of(&clusters[j].set)
&& !clusters[i].set.is_equal(&clusters[j].set)
{
let sz = clusters[j].set.count();
if sz < best_size {
best_size = sz;
best_parent = Some(j);
}
}
}
let p = best_parent.unwrap_or(0);
clusters[i].parent = Some(p);
clusters[p].children.push(i);
}
let mut tree = Tree::new(ntax);
fn build_cluster(idx: usize, clusters: &[ClusterNode], tree: &mut Tree, ntax: usize) -> usize {
let cluster = &clusters[idx];
let mut members = cluster.set.taxa();
members.retain(|&t| t < ntax);
let mut covered = TaxonSet::new(ntax);
for &ch in &cluster.children {
covered.union_inplace(&clusters[ch].set);
}
let mut child_nodes = Vec::<usize>::new();
for &ch in &cluster.children {
let nid = build_cluster(ch, clusters, tree, ntax);
child_nodes.push(nid);
}
for t in members {
if !covered.contains(t) {
child_nodes.push(t);
}
}
child_nodes.sort_unstable();
if child_nodes.len() == 1 { child_nodes[0] } else { tree.add_internal_node(child_nodes) }
}
let ingroup_root = build_cluster(0, &clusters, &mut tree, ntax);
let mut root_children = Vec::<usize>::new();
root_children.extend_from_slice(outgroups);
root_children.push(ingroup_root);
root_children.sort_unstable();
let root = if root_children.len() == 1 {
root_children[0]
} else {
tree.add_internal_node(root_children)
};
tree.root = root;
Ok(tree)
}
pub fn strict_consensus_with_outgroups(
trees: &[Tree],
outgroups: &[usize],
) -> Result<Tree, String> {
if trees.is_empty() {
return Err("nelsen: no trees available".to_string());
}
if outgroups.is_empty() {
return Err("nelsen: outgroup set is empty".to_string());
}
let ntax = trees[0].ntax;
for (i, t) in trees.iter().enumerate() {
if t.ntax != ntax {
return Err(format!("nelsen: tree {i} has different ntax"));
}
}
let normalized: Vec<Tree> =
trees.iter().map(|t| normalize_by_outgroups(t, outgroups)).collect();
let first_clades = rooted_clades_excluding_outgroups(&normalized[0], outgroups);
let mut common = BTreeSet::<TaxonSet>::new();
for c in first_clades {
common.insert(c);
}
for tr in &normalized[1..] {
let set: BTreeSet<TaxonSet> =
rooted_clades_excluding_outgroups(tr, outgroups).into_iter().collect();
common = common.intersection(&set).cloned().collect();
}
let common_vec: Vec<TaxonSet> = common.into_iter().collect();
for i in 0..common_vec.len() {
for j in i + 1..common_vec.len() {
if !common_vec[i].is_compatible_with(&common_vec[j]) {
return Err("nelsen: incompatible clades survived strict intersection".to_string());
}
}
}
build_tree_from_rooted_clades_with_outgroups(ntax, outgroups, &common_vec)
}
pub fn nelsen_consensus(
ds: &Dataset,
cfg: &CharConfig,
trees: &[Tree],
outgroups: &[usize],
) -> Result<ConsensusOutcome, String> {
if trees.is_empty() {
return Err("nelsen: no trees available".to_string());
}
let mut ws = ScoreWorkspace::new();
let uniq = uniq_rooted_by_outgroups(trees, outgroups, ds, cfg, &mut ws);
let consensus = strict_consensus_with_outgroups(&uniq, outgroups)?;
let best_len = score_tree(ds, cfg, &consensus, &mut ws);
let min_len = minsteps_sum(ds, cfg);
let max_len = maxsteps_sum(ds, cfg);
let ci = calc_ci(min_len, best_len);
let ri = calc_ri(min_len, max_len, best_len);
Ok(ConsensusOutcome {
tree: consensus,
input_trees: trees.len(),
uniq_trees: uniq.len(),
best_len,
ci,
ri,
})
}