use std::collections::{HashSet, VecDeque};
use rsomics_phylo_tree::Tree;
use crate::{CompositionError, Result};
#[derive(Clone, Debug, PartialEq)]
pub struct Basis {
components: Vec<String>,
balances: Vec<String>,
values: Vec<f64>,
}
impl Basis {
pub fn new(components: Vec<String>, balances: Vec<String>, values: Vec<f64>) -> Result<Self> {
validate_names("component", &components)?;
validate_names("balance", &balances)?;
let width = components.len();
if width < 2 {
return Err(CompositionError::TooFewComponents {
found: width,
required: 2,
});
}
if balances.len() != width - 1 || values.len() != balances.len() * width {
return Err(CompositionError::BasisShape {
rows: balances.len(),
columns: values.len().checked_div(balances.len()).unwrap_or(0),
expected_rows: width - 1,
expected_columns: width,
});
}
validate_orthonormal(&values, balances.len(), width)?;
Ok(Self {
components,
balances,
values,
})
}
pub fn default_for(components: Vec<String>) -> Result<Self> {
let width = components.len();
if width < 2 {
return Err(CompositionError::TooFewComponents {
found: width,
required: 2,
});
}
let mut values = vec![0.0; (width - 1) * width];
for row in 0..width - 1 {
let count = row + 1;
let scale = (count as f64 / (count + 1) as f64).sqrt();
for column in 0..count {
values[row * width + column] = scale / count as f64;
}
values[row * width + count] = -scale;
}
Self::new(
components,
(0..width - 1)
.map(|index| format!("balance{index}"))
.collect(),
values,
)
}
pub fn from_sbp(
components: Vec<String>,
balances: Vec<String>,
partitions: &[Vec<i8>],
) -> Result<Self> {
validate_names("component", &components)?;
validate_names("balance", &balances)?;
let width = components.len();
if partitions.len() != width.saturating_sub(1) || balances.len() != partitions.len() {
return Err(CompositionError::BasisShape {
rows: partitions.len(),
columns: partitions.first().map_or(0, Vec::len),
expected_rows: width.saturating_sub(1),
expected_columns: width,
});
}
let mut values = vec![0.0; partitions.len() * width];
for (row_index, row) in partitions.iter().enumerate() {
if row.len() != width {
return Err(CompositionError::BasisShape {
rows: partitions.len(),
columns: row.len(),
expected_rows: width - 1,
expected_columns: width,
});
}
if let Some(&value) = row.iter().find(|&&value| !matches!(value, -1..=1)) {
return Err(CompositionError::InvalidPartitionValue {
row: row_index,
value,
});
}
let positive = row.iter().filter(|&&value| value == 1).count();
let negative = row.iter().filter(|&&value| value == -1).count();
if positive == 0 || negative == 0 {
return Err(CompositionError::EmptyPartitionSide(row_index));
}
let positive_value =
(negative as f64 / (positive as f64 * (positive + negative) as f64)).sqrt();
let negative_value =
-(positive as f64 / (negative as f64 * (positive + negative) as f64)).sqrt();
for (column, &partition) in row.iter().enumerate() {
values[row_index * width + column] = match partition {
1 => positive_value,
-1 => negative_value,
_ => 0.0,
};
}
}
Self::new(components, balances, values)
}
pub fn from_tree(tree: &Tree, components: Vec<String>) -> Result<Self> {
validate_names("component", &components)?;
if components.len() < 2 {
return Err(CompositionError::TooFewComponents {
found: components.len(),
required: 2,
});
}
let tip_index = tree
.tip_index()
.map_err(|error| CompositionError::TreeTipMismatch(error.to_string()))?;
let component_set: HashSet<&str> = components.iter().map(String::as_str).collect();
if tip_index.len() != components.len()
|| tip_index.keys().any(|tip| !component_set.contains(tip))
{
return Err(CompositionError::TreeTipMismatch(format!(
"tree has {:?}; components have {:?}",
sorted(tip_index.keys().copied()),
sorted(components.iter().map(String::as_str))
)));
}
let mut descendants = vec![Vec::<usize>::new(); tree.node_count()];
for id in tree.postorder() {
let node = tree.node(id).unwrap();
if node.is_tip() {
let name = node.name().unwrap();
descendants[id.index()].push(
components
.iter()
.position(|component| component == name)
.unwrap(),
);
} else {
if node.children().len() != 2 {
return Err(CompositionError::NonBifurcatingTree {
node: id.index(),
children: node.children().len(),
});
}
for child in node.children() {
let tips = descendants[child.index()].clone();
descendants[id.index()].extend(tips);
}
}
}
let mut internal = Vec::with_capacity(components.len() - 1);
let mut queue = VecDeque::from([tree.root()]);
while let Some(id) = queue.pop_front() {
let node = tree.node(id).unwrap();
if node.is_tip() {
continue;
}
internal.push(id);
queue.extend(node.children().iter().copied());
}
if internal.len() != components.len() - 1 {
return Err(CompositionError::BasisShape {
rows: internal.len(),
columns: components.len(),
expected_rows: components.len() - 1,
expected_columns: components.len(),
});
}
let width = components.len();
let mut values = vec![0.0; internal.len() * width];
let mut balances = Vec::with_capacity(internal.len());
for (row, id) in internal.into_iter().enumerate() {
let node = tree.node(id).unwrap();
let negative = &descendants[node.children()[0].index()];
let positive = &descendants[node.children()[1].index()];
let positive_value = (negative.len() as f64
/ (positive.len() * (positive.len() + negative.len())) as f64)
.sqrt();
let negative_value = -(positive.len() as f64
/ (negative.len() * (positive.len() + negative.len())) as f64)
.sqrt();
for &column in positive {
values[row * width + column] = positive_value;
}
for &column in negative {
values[row * width + column] = negative_value;
}
balances.push(
node.name()
.map(str::to_owned)
.unwrap_or_else(|| format!("balance{row}")),
);
}
Self::new(components, balances, values)
}
#[must_use]
pub fn components(&self) -> &[String] {
&self.components
}
#[must_use]
pub fn balances(&self) -> &[String] {
&self.balances
}
#[must_use]
pub fn values(&self) -> &[f64] {
&self.values
}
#[must_use]
pub fn row(&self, index: usize) -> Option<&[f64]> {
let width = self.components.len();
self.values.get(index * width..(index + 1) * width)
}
pub(crate) fn component_order(&self, components: &[String]) -> Result<Vec<usize>> {
align(&self.components, components, "basis is missing component")
}
pub(crate) fn balance_order(&self, balances: &[String]) -> Result<Vec<usize>> {
align(&self.balances, balances, "coordinates are missing balance")
}
}
fn align(target: &[String], source: &[String], prefix: &str) -> Result<Vec<usize>> {
if target.len() != source.len() {
return Err(CompositionError::ComponentMismatch {
details: format!("expected {} identities, got {}", target.len(), source.len()),
});
}
target
.iter()
.map(|identity| {
source
.iter()
.position(|candidate| candidate == identity)
.ok_or_else(|| CompositionError::ComponentMismatch {
details: format!("{prefix} {identity:?}"),
})
})
.collect()
}
fn validate_names(kind: &'static str, names: &[String]) -> Result<()> {
let mut seen = HashSet::with_capacity(names.len());
for name in names {
if name.is_empty() {
return Err(CompositionError::EmptyIdentity { kind });
}
if !seen.insert(name) {
return Err(CompositionError::DuplicateIdentity {
kind,
identity: name.clone(),
});
}
}
Ok(())
}
fn validate_orthonormal(values: &[f64], rows: usize, columns: usize) -> Result<()> {
for left in 0..rows {
for right in left..rows {
let dot: f64 = (0..columns)
.map(|column| values[left * columns + column] * values[right * columns + column])
.sum();
let expected = f64::from(u8::from(left == right));
if !dot.is_finite() || (dot - expected).abs() > 1e-10 {
return Err(CompositionError::NonOrthonormalBasis {
left,
right,
value: dot,
});
}
}
}
Ok(())
}
fn sorted<'a>(values: impl Iterator<Item = &'a str>) -> Vec<&'a str> {
let mut values: Vec<_> = values.collect();
values.sort_unstable();
values
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn sbp_matches_skbio_example() {
let partitions = vec![
vec![1, 1, -1, -1, -1],
vec![1, -1, 0, 0, 0],
vec![0, 0, 1, -1, -1],
vec![0, 0, 0, 1, -1],
];
let basis = Basis::from_sbp(
["a", "b", "c", "d", "e"].map(str::to_owned).to_vec(),
(0..4).map(|index| format!("b{index}")).collect(),
&partitions,
)
.unwrap();
assert!((basis.row(0).unwrap()[0] - 0.547_722_557_505_166_1).abs() < 1e-12);
assert!((basis.row(0).unwrap()[2] + 0.365_148_371_670_111_4).abs() < 1e-12);
}
#[test]
fn tree_basis_uses_tip_identity() {
let tree = Tree::from_newick("((b,c)a,d)root;").unwrap();
let basis = Basis::from_tree(&tree, ["d", "c", "b"].map(str::to_owned).to_vec()).unwrap();
assert_eq!(basis.balances(), ["root", "a"]);
assert!((basis.row(0).unwrap()[0] - 0.816_496_580_927_726).abs() < 1e-12);
assert!((basis.row(1).unwrap()[1] - 0.707_106_781_186_547_5).abs() < 1e-12);
assert!((basis.row(1).unwrap()[2] + 0.707_106_781_186_547_5).abs() < 1e-12);
}
#[test]
fn tree_basis_rejects_tip_mismatch_and_polytomy() {
let mismatch = Tree::from_newick("(a,b)root;").unwrap();
assert!(Basis::from_tree(&mismatch, vec!["a".into(), "c".into()]).is_err());
let polytomy = Tree::from_newick("(a,b,c)root;").unwrap();
assert!(matches!(
Basis::from_tree(&polytomy, ["a", "b", "c"].map(str::to_owned).to_vec()),
Err(CompositionError::NonBifurcatingTree { .. })
));
}
#[test]
fn nonorthogonal_sbp_is_rejected() {
let partitions = vec![vec![1, -1, 0], vec![1, 0, -1]];
assert!(matches!(
Basis::from_sbp(
["a", "b", "c"].map(str::to_owned).to_vec(),
vec!["x".into(), "y".into()],
&partitions,
),
Err(CompositionError::NonOrthonormalBasis { .. })
));
}
#[test]
fn nonfinite_numeric_basis_is_rejected() {
assert!(matches!(
Basis::new(
vec!["a".into(), "b".into()],
vec!["balance".into()],
vec![f64::NAN, 0.0],
),
Err(CompositionError::NonOrthonormalBasis { .. })
));
}
}