1use std::collections::{HashSet, VecDeque};
2
3use rsomics_phylo_tree::Tree;
4
5use crate::{CompositionError, Result};
6
7#[derive(Clone, Debug, PartialEq)]
8pub struct Basis {
9 components: Vec<String>,
10 balances: Vec<String>,
11 values: Vec<f64>,
12}
13
14impl Basis {
15 pub fn new(components: Vec<String>, balances: Vec<String>, values: Vec<f64>) -> Result<Self> {
16 validate_names("component", &components)?;
17 validate_names("balance", &balances)?;
18 let width = components.len();
19 if width < 2 {
20 return Err(CompositionError::TooFewComponents {
21 found: width,
22 required: 2,
23 });
24 }
25 if balances.len() != width - 1 || values.len() != balances.len() * width {
26 return Err(CompositionError::BasisShape {
27 rows: balances.len(),
28 columns: values.len().checked_div(balances.len()).unwrap_or(0),
29 expected_rows: width - 1,
30 expected_columns: width,
31 });
32 }
33 validate_orthonormal(&values, balances.len(), width)?;
34 Ok(Self {
35 components,
36 balances,
37 values,
38 })
39 }
40
41 pub fn default_for(components: Vec<String>) -> Result<Self> {
42 let width = components.len();
43 if width < 2 {
44 return Err(CompositionError::TooFewComponents {
45 found: width,
46 required: 2,
47 });
48 }
49 let mut values = vec![0.0; (width - 1) * width];
50 for row in 0..width - 1 {
51 let count = row + 1;
52 let scale = (count as f64 / (count + 1) as f64).sqrt();
53 for column in 0..count {
54 values[row * width + column] = scale / count as f64;
55 }
56 values[row * width + count] = -scale;
57 }
58 Self::new(
59 components,
60 (0..width - 1)
61 .map(|index| format!("balance{index}"))
62 .collect(),
63 values,
64 )
65 }
66
67 pub fn from_sbp(
68 components: Vec<String>,
69 balances: Vec<String>,
70 partitions: &[Vec<i8>],
71 ) -> Result<Self> {
72 validate_names("component", &components)?;
73 validate_names("balance", &balances)?;
74 let width = components.len();
75 if partitions.len() != width.saturating_sub(1) || balances.len() != partitions.len() {
76 return Err(CompositionError::BasisShape {
77 rows: partitions.len(),
78 columns: partitions.first().map_or(0, Vec::len),
79 expected_rows: width.saturating_sub(1),
80 expected_columns: width,
81 });
82 }
83 let mut values = vec![0.0; partitions.len() * width];
84 for (row_index, row) in partitions.iter().enumerate() {
85 if row.len() != width {
86 return Err(CompositionError::BasisShape {
87 rows: partitions.len(),
88 columns: row.len(),
89 expected_rows: width - 1,
90 expected_columns: width,
91 });
92 }
93 if let Some(&value) = row.iter().find(|&&value| !matches!(value, -1..=1)) {
94 return Err(CompositionError::InvalidPartitionValue {
95 row: row_index,
96 value,
97 });
98 }
99 let positive = row.iter().filter(|&&value| value == 1).count();
100 let negative = row.iter().filter(|&&value| value == -1).count();
101 if positive == 0 || negative == 0 {
102 return Err(CompositionError::EmptyPartitionSide(row_index));
103 }
104 let positive_value =
105 (negative as f64 / (positive as f64 * (positive + negative) as f64)).sqrt();
106 let negative_value =
107 -(positive as f64 / (negative as f64 * (positive + negative) as f64)).sqrt();
108 for (column, &partition) in row.iter().enumerate() {
109 values[row_index * width + column] = match partition {
110 1 => positive_value,
111 -1 => negative_value,
112 _ => 0.0,
113 };
114 }
115 }
116 Self::new(components, balances, values)
117 }
118
119 pub fn from_tree(tree: &Tree, components: Vec<String>) -> Result<Self> {
120 validate_names("component", &components)?;
121 if components.len() < 2 {
122 return Err(CompositionError::TooFewComponents {
123 found: components.len(),
124 required: 2,
125 });
126 }
127 let tip_index = tree
128 .tip_index()
129 .map_err(|error| CompositionError::TreeTipMismatch(error.to_string()))?;
130 let component_set: HashSet<&str> = components.iter().map(String::as_str).collect();
131 if tip_index.len() != components.len()
132 || tip_index.keys().any(|tip| !component_set.contains(tip))
133 {
134 return Err(CompositionError::TreeTipMismatch(format!(
135 "tree has {:?}; components have {:?}",
136 sorted(tip_index.keys().copied()),
137 sorted(components.iter().map(String::as_str))
138 )));
139 }
140
141 let mut descendants = vec![Vec::<usize>::new(); tree.node_count()];
142 for id in tree.postorder() {
143 let node = tree.node(id).unwrap();
144 if node.is_tip() {
145 let name = node.name().unwrap();
146 descendants[id.index()].push(
147 components
148 .iter()
149 .position(|component| component == name)
150 .unwrap(),
151 );
152 } else {
153 if node.children().len() != 2 {
154 return Err(CompositionError::NonBifurcatingTree {
155 node: id.index(),
156 children: node.children().len(),
157 });
158 }
159 for child in node.children() {
160 let tips = descendants[child.index()].clone();
161 descendants[id.index()].extend(tips);
162 }
163 }
164 }
165
166 let mut internal = Vec::with_capacity(components.len() - 1);
167 let mut queue = VecDeque::from([tree.root()]);
168 while let Some(id) = queue.pop_front() {
169 let node = tree.node(id).unwrap();
170 if node.is_tip() {
171 continue;
172 }
173 internal.push(id);
174 queue.extend(node.children().iter().copied());
175 }
176 if internal.len() != components.len() - 1 {
177 return Err(CompositionError::BasisShape {
178 rows: internal.len(),
179 columns: components.len(),
180 expected_rows: components.len() - 1,
181 expected_columns: components.len(),
182 });
183 }
184
185 let width = components.len();
186 let mut values = vec![0.0; internal.len() * width];
187 let mut balances = Vec::with_capacity(internal.len());
188 for (row, id) in internal.into_iter().enumerate() {
189 let node = tree.node(id).unwrap();
190 let negative = &descendants[node.children()[0].index()];
191 let positive = &descendants[node.children()[1].index()];
192 let positive_value = (negative.len() as f64
193 / (positive.len() * (positive.len() + negative.len())) as f64)
194 .sqrt();
195 let negative_value = -(positive.len() as f64
196 / (negative.len() * (positive.len() + negative.len())) as f64)
197 .sqrt();
198 for &column in positive {
199 values[row * width + column] = positive_value;
200 }
201 for &column in negative {
202 values[row * width + column] = negative_value;
203 }
204 balances.push(
205 node.name()
206 .map(str::to_owned)
207 .unwrap_or_else(|| format!("balance{row}")),
208 );
209 }
210 Self::new(components, balances, values)
211 }
212
213 #[must_use]
214 pub fn components(&self) -> &[String] {
215 &self.components
216 }
217
218 #[must_use]
219 pub fn balances(&self) -> &[String] {
220 &self.balances
221 }
222
223 #[must_use]
224 pub fn values(&self) -> &[f64] {
225 &self.values
226 }
227
228 #[must_use]
229 pub fn row(&self, index: usize) -> Option<&[f64]> {
230 let width = self.components.len();
231 self.values.get(index * width..(index + 1) * width)
232 }
233
234 pub(crate) fn component_order(&self, components: &[String]) -> Result<Vec<usize>> {
235 align(&self.components, components, "basis is missing component")
236 }
237
238 pub(crate) fn balance_order(&self, balances: &[String]) -> Result<Vec<usize>> {
239 align(&self.balances, balances, "coordinates are missing balance")
240 }
241}
242
243fn align(target: &[String], source: &[String], prefix: &str) -> Result<Vec<usize>> {
244 if target.len() != source.len() {
245 return Err(CompositionError::ComponentMismatch {
246 details: format!("expected {} identities, got {}", target.len(), source.len()),
247 });
248 }
249 target
250 .iter()
251 .map(|identity| {
252 source
253 .iter()
254 .position(|candidate| candidate == identity)
255 .ok_or_else(|| CompositionError::ComponentMismatch {
256 details: format!("{prefix} {identity:?}"),
257 })
258 })
259 .collect()
260}
261
262fn validate_names(kind: &'static str, names: &[String]) -> Result<()> {
263 let mut seen = HashSet::with_capacity(names.len());
264 for name in names {
265 if name.is_empty() {
266 return Err(CompositionError::EmptyIdentity { kind });
267 }
268 if !seen.insert(name) {
269 return Err(CompositionError::DuplicateIdentity {
270 kind,
271 identity: name.clone(),
272 });
273 }
274 }
275 Ok(())
276}
277
278fn validate_orthonormal(values: &[f64], rows: usize, columns: usize) -> Result<()> {
279 for left in 0..rows {
280 for right in left..rows {
281 let dot: f64 = (0..columns)
282 .map(|column| values[left * columns + column] * values[right * columns + column])
283 .sum();
284 let expected = f64::from(u8::from(left == right));
285 if !dot.is_finite() || (dot - expected).abs() > 1e-10 {
286 return Err(CompositionError::NonOrthonormalBasis {
287 left,
288 right,
289 value: dot,
290 });
291 }
292 }
293 }
294 Ok(())
295}
296
297fn sorted<'a>(values: impl Iterator<Item = &'a str>) -> Vec<&'a str> {
298 let mut values: Vec<_> = values.collect();
299 values.sort_unstable();
300 values
301}
302
303#[cfg(test)]
304mod tests {
305 use super::*;
306
307 #[test]
308 fn sbp_matches_skbio_example() {
309 let partitions = vec![
310 vec![1, 1, -1, -1, -1],
311 vec![1, -1, 0, 0, 0],
312 vec![0, 0, 1, -1, -1],
313 vec![0, 0, 0, 1, -1],
314 ];
315 let basis = Basis::from_sbp(
316 ["a", "b", "c", "d", "e"].map(str::to_owned).to_vec(),
317 (0..4).map(|index| format!("b{index}")).collect(),
318 &partitions,
319 )
320 .unwrap();
321 assert!((basis.row(0).unwrap()[0] - 0.547_722_557_505_166_1).abs() < 1e-12);
322 assert!((basis.row(0).unwrap()[2] + 0.365_148_371_670_111_4).abs() < 1e-12);
323 }
324
325 #[test]
326 fn tree_basis_uses_tip_identity() {
327 let tree = Tree::from_newick("((b,c)a,d)root;").unwrap();
328 let basis = Basis::from_tree(&tree, ["d", "c", "b"].map(str::to_owned).to_vec()).unwrap();
329 assert_eq!(basis.balances(), ["root", "a"]);
330 assert!((basis.row(0).unwrap()[0] - 0.816_496_580_927_726).abs() < 1e-12);
331 assert!((basis.row(1).unwrap()[1] - 0.707_106_781_186_547_5).abs() < 1e-12);
332 assert!((basis.row(1).unwrap()[2] + 0.707_106_781_186_547_5).abs() < 1e-12);
333 }
334
335 #[test]
336 fn tree_basis_rejects_tip_mismatch_and_polytomy() {
337 let mismatch = Tree::from_newick("(a,b)root;").unwrap();
338 assert!(Basis::from_tree(&mismatch, vec!["a".into(), "c".into()]).is_err());
339 let polytomy = Tree::from_newick("(a,b,c)root;").unwrap();
340 assert!(matches!(
341 Basis::from_tree(&polytomy, ["a", "b", "c"].map(str::to_owned).to_vec()),
342 Err(CompositionError::NonBifurcatingTree { .. })
343 ));
344 }
345
346 #[test]
347 fn nonorthogonal_sbp_is_rejected() {
348 let partitions = vec![vec![1, -1, 0], vec![1, 0, -1]];
349 assert!(matches!(
350 Basis::from_sbp(
351 ["a", "b", "c"].map(str::to_owned).to_vec(),
352 vec!["x".into(), "y".into()],
353 &partitions,
354 ),
355 Err(CompositionError::NonOrthonormalBasis { .. })
356 ));
357 }
358
359 #[test]
360 fn nonfinite_numeric_basis_is_rejected() {
361 assert!(matches!(
362 Basis::new(
363 vec!["a".into(), "b".into()],
364 vec!["balance".into()],
365 vec![f64::NAN, 0.0],
366 ),
367 Err(CompositionError::NonOrthonormalBasis { .. })
368 ));
369 }
370}