use crate::{Error, Result, canonical_zero};
#[derive(Clone, Copy, Debug)]
pub struct DissimilarityView<'a> {
values: &'a [f64],
vertex_count: usize,
diameter: f64,
}
impl<'a> DissimilarityView<'a> {
pub fn new(values: &'a [f64], vertex_count: usize) -> Result<Self> {
let expected = pair_count(vertex_count).ok_or(Error::SizeOverflow {
operation: "vertex_count choose 2",
})?;
if values.len() != expected {
return Err(Error::ShapeMismatch {
input: "dissimilarities",
expected,
actual: values.len(),
});
}
let mut diameter: f64 = 0.0;
for (index, &value) in values.iter().enumerate() {
if !value.is_finite() {
return Err(Error::NonFiniteValue {
field: "dissimilarities",
index: Some(index),
});
}
if value < 0.0 {
return Err(Error::NegativeValue {
field: "dissimilarities",
index: Some(index),
});
}
diameter = diameter.max(canonical_zero(value));
}
Ok(Self {
values,
vertex_count,
diameter,
})
}
pub fn len(&self) -> usize {
self.vertex_count
}
pub fn is_empty(&self) -> bool {
self.vertex_count == 0
}
pub fn values(&self) -> &'a [f64] {
self.values
}
pub fn diameter(&self) -> f64 {
self.diameter
}
pub fn get(&self, i: usize, j: usize) -> Option<f64> {
if i >= self.vertex_count || j >= self.vertex_count {
return None;
}
if i == j {
return Some(0.0);
}
let (row, column) = if i > j { (i, j) } else { (j, i) };
let offset = pair_count(row)?.checked_add(column)?;
self.values.get(offset).copied().map(canonical_zero)
}
}
pub(crate) fn pair_count(n: usize) -> Option<usize> {
if n < 2 {
Some(0)
} else if n.is_multiple_of(2) {
(n / 2).checked_mul(n - 1)
} else {
n.checked_mul((n - 1) / 2)
}
}
#[cfg(test)]
mod tests {
use super::pair_count;
#[test]
fn condensed_shape_accepts_representable_counts_without_intermediate_overflow() {
let middle = 1usize << (usize::BITS / 2);
for n in [
0,
1,
2,
middle - 1,
middle,
middle + 1,
usize::MAX / 2,
usize::MAX,
] {
let wide = n as u128;
let expected = usize::try_from(wide * wide.saturating_sub(1) / 2).ok();
assert_eq!(pair_count(n), expected);
}
assert!(pair_count(middle + 1).is_some());
assert!((middle + 1).checked_mul(middle).is_none());
}
}