use std::collections::HashSet;
use crate::engines::{
ccode::CharConfig,
dataset::Dataset,
search::{
ScoreWorkspace, collapse_zero_length_branches, collapsed_topology_hash,
rooted_topology_hash, score_tree,
},
trees::Tree,
};
#[derive(Debug, Clone, Copy)]
pub enum IeMode {
KeepUpTo(usize),
KeepAll,
KeepOne,
}
#[derive(Debug, Clone)]
pub struct IeOutcome {
pub trees: Vec<Tree>,
pub best_len: u64,
}
pub fn ie_exact(
ds: &Dataset,
cfg: &CharConfig,
outgroup: usize,
mode: IeMode,
) -> Result<IeOutcome, String> {
if ds.ntax < 3 {
return Err("ie: ntax must be >= 3".to_string());
}
if outgroup >= ds.ntax {
return Err(format!("ie: outgroup {outgroup} out of range"));
}
if cfg.len() != ds.nchar {
return Err(format!("ie: char_config nchar={} != dataset nchar={}", cfg.len(), ds.nchar));
}
let mut ws = ScoreWorkspace::new();
let init = greedy_build_initial_bound(ds, cfg, outgroup, &mut ws)?;
let bound = score_tree(ds, cfg, &init, &mut ws);
let start = initial_three_taxon_tree(ds.ntax, outgroup)?;
let mut ctx =
Ctx { ds, cfg, outgroup, mode, ws, bound, best: Vec::new(), best_seen: HashSet::new() };
let ingroup: Vec<usize> = (0..ds.ntax).filter(|&t| t != outgroup).collect();
let fixed = start.fixed_taxa.clone();
let mut remaining: Vec<usize> = ingroup.into_iter().filter(|t| !fixed.contains(t)).collect();
dfs_enum(&mut ctx, &start.tree, &mut remaining)?;
ctx.best.sort_by_key(|t| rooted_topology_hash(t));
Ok(IeOutcome { trees: ctx.best, best_len: ctx.bound })
}
struct Ctx<'a> {
ds: &'a Dataset,
cfg: &'a CharConfig,
outgroup: usize,
mode: IeMode,
ws: ScoreWorkspace,
bound: u64,
best: Vec<Tree>,
best_seen: HashSet<u64>,
}
struct ThreeStart {
tree: Tree,
fixed_taxa: Vec<usize>,
}
fn initial_three_taxon_tree(ntax: usize, outgroup: usize) -> Result<ThreeStart, String> {
let mut ingroup: Vec<usize> = (0..ntax).filter(|&t| t != outgroup).collect();
if ingroup.len() < 2 {
return Err("ie: need at least 2 ingroup taxa".to_string());
}
ingroup.sort_unstable();
let a = ingroup[0];
let b = ingroup[1];
let tr = Tree::new_outgrouped(ntax, outgroup, a, b);
Ok(ThreeStart { tree: tr, fixed_taxa: vec![a, b] })
}
fn greedy_build_initial_bound(
ds: &Dataset,
cfg: &CharConfig,
outgroup: usize,
ws: &mut ScoreWorkspace,
) -> Result<Tree, String> {
let mut ingroup: Vec<usize> = (0..ds.ntax).filter(|&x| x != outgroup).collect();
ingroup.sort_unstable();
let a = ingroup[0];
let b = ingroup[1];
let mut tr = Tree::new_outgrouped(ds.ntax, outgroup, a, b);
for &clip in &ingroup[2..] {
let edges = tr.rooted_edges();
let mut best_len = u64::MAX;
let mut best_edge = None::<(usize, usize)>;
for &(p, c) in &edges {
if c == outgroup {
continue;
}
let mut tmp = tr.clone();
tmp.insert_taxon_on_edge(p, c, clip);
let len = score_tree(ds, cfg, &tmp, ws);
if len < best_len {
best_len = len;
best_edge = Some((p, c));
}
}
let (p, c) = best_edge.ok_or("ie: no insertion edge found")?;
tr.insert_taxon_on_edge(p, c, clip);
}
Ok(tr)
}
fn dfs_enum(ctx: &mut Ctx, cur: &Tree, remaining: &mut Vec<usize>) -> Result<(), String> {
if remaining.is_empty() {
let mut tmp = cur.clone();
tmp.canonicalize();
let len = score_tree(ctx.ds, ctx.cfg, &tmp, &mut ctx.ws);
if len < ctx.bound {
ctx.bound = len;
ctx.best.clear();
ctx.best_seen.clear();
}
if len == ctx.bound {
let h = {
let og = [ctx.outgroup];
let mut norm = tmp
.reroot_by_outgroup_set(&og)
.or_else(|_| tmp.reroot_by_outgroup(ctx.outgroup))
.unwrap_or_else(|_| tmp.clone());
norm.canonicalize();
collapse_zero_length_branches(&mut norm, ctx.ds, ctx.cfg, &mut ctx.ws);
collapsed_topology_hash(&norm)
};
if ctx.best_seen.insert(h) {
match ctx.mode {
IeMode::KeepOne => {
ctx.best.clear();
ctx.best.push(tmp);
}
IeMode::KeepAll => ctx.best.push(tmp),
IeMode::KeepUpTo(lim) => {
if ctx.best.len() < lim {
ctx.best.push(tmp);
}
}
}
}
}
return Ok(());
}
let next_tax = remaining.pop().unwrap();
let edges = cur.rooted_edges();
for &(p, c) in &edges {
if c == ctx.outgroup {
continue;
}
let mut t2 = cur.clone();
t2.insert_taxon_on_edge(p, c, next_tax);
let partial_len = score_tree(ctx.ds, ctx.cfg, &t2, &mut ctx.ws);
if partial_len > ctx.bound {
continue;
}
dfs_enum(ctx, &t2, remaining)?;
}
remaining.push(next_tax);
Ok(())
}