use std::ops::{Add, Mul, Neg, Sub};
use crate::segment::Segment;
use crate::util;
#[derive(Debug, Clone, Copy)]
pub struct Resonance {
pub eps: f64,
pub weight: f64,
}
#[derive(Debug, Clone, Default)]
pub struct DiscreteSF {
resonances: Vec<Resonance>,
}
impl FromIterator<Resonance> for DiscreteSF {
fn from_iter<I: IntoIterator<Item = Resonance>>(resonances: I) -> Self {
let mut resonances: Vec<Resonance> = resonances
.into_iter()
.inspect(|res| {
assert!(
res.eps.is_finite(),
"a resonance must sit at a finite frequency"
)
})
.filter(|res| res.weight != 0.0)
.map(|res| Resonance {
eps: if res.eps == 0.0 { 0.0 } else { res.eps },
weight: res.weight,
})
.collect();
resonances.sort_by(|r1, r2| r1.eps.total_cmp(&r2.eps));
canonicalize(&mut resonances);
DiscreteSF { resonances }
}
}
impl Add for DiscreteSF {
type Output = Self;
fn add(self, rhs: Self) -> Self {
let (lhs, rhs) = (self.resonances, rhs.resonances);
let mut resonances = Vec::with_capacity(lhs.len() + rhs.len());
let (mut l, mut r) = (lhs.iter().peekable(), rhs.iter().peekable());
loop {
let ordering = match (l.peek(), r.peek()) {
(Some(rl), Some(rr)) => rl.eps.total_cmp(&rr.eps),
(Some(_), None) => std::cmp::Ordering::Less,
(None, Some(_)) => std::cmp::Ordering::Greater,
(None, None) => break,
};
match ordering {
std::cmp::Ordering::Less => resonances.push(*l.next().unwrap()),
std::cmp::Ordering::Greater => resonances.push(*r.next().unwrap()),
std::cmp::Ordering::Equal => {
let (rl, rr) = (l.next().unwrap(), r.next().unwrap());
let weight = rl.weight + rr.weight;
let tol = DiscreteSF::WEIGHT_TOL;
if weight.abs() > tol * (rl.weight.abs() + rr.weight.abs()) {
resonances.push(Resonance {
eps: rl.eps,
weight,
});
}
}
}
}
DiscreteSF { resonances }
}
}
impl Mul<f64> for DiscreteSF {
type Output = Self;
fn mul(mut self, a: f64) -> Self {
if a == 0.0 {
self.resonances.clear();
} else {
self.resonances.retain_mut(|res| {
res.weight *= a;
res.weight != 0.0
});
}
self
}
}
impl Mul<DiscreteSF> for f64 {
type Output = DiscreteSF;
fn mul(self, sf: DiscreteSF) -> DiscreteSF {
sf * self
}
}
impl Neg for DiscreteSF {
type Output = Self;
fn neg(self) -> DiscreteSF {
self * (-1.0)
}
}
impl Sub for DiscreteSF {
type Output = Self;
fn sub(self, rhs: Self) -> Self {
self + (-rhs)
}
}
impl<'a> IntoIterator for &'a DiscreteSF {
type Item = &'a Resonance;
type IntoIter = std::slice::Iter<'a, Resonance>;
fn into_iter(self) -> Self::IntoIter {
self.resonances.iter()
}
}
fn canonicalize(resonances: &mut Vec<Resonance>) {
let (mut w, mut i) = (0, 0);
while i < resonances.len() {
let start = i;
let eps = resonances[i].eps;
while i < resonances.len() && resonances[i].eps == eps {
i += 1;
}
if i == start + 1 {
resonances[w] = resonances[start];
w += 1;
continue;
}
let group = &mut resonances[start..i];
group.sort_unstable_by(|r1, r2| r1.weight.abs().total_cmp(&r2.weight.abs()));
let total = util::kahan_babushka_neumaier_sum(group.iter().map(|r| r.weight));
let mag: f64 = group.iter().map(|r| r.weight.abs()).sum();
if total.abs() > DiscreteSF::WEIGHT_TOL * mag {
resonances[w] = Resonance { eps, weight: total };
w += 1;
}
}
resonances.truncate(w);
}
impl DiscreteSF {
pub const WEIGHT_TOL: f64 = f64::EPSILON;
pub fn new() -> Self {
Self::default()
}
pub fn one_resonance(eps: f64, weight: f64) -> DiscreteSF {
DiscreteSF::from_iter([Resonance { eps, weight }])
}
pub fn resonances(&self) -> &[Resonance] {
&self.resonances
}
pub fn len(&self) -> usize {
self.resonances.len()
}
pub fn is_empty(&self) -> bool {
self.resonances.is_empty()
}
pub fn iter(&self) -> std::slice::Iter<'_, Resonance> {
self.resonances.iter()
}
pub fn into_resonances(self) -> Vec<Resonance> {
self.resonances
}
pub fn support(&self) -> Option<Segment> {
Some(Segment::new(
self.resonances.first()?.eps,
self.resonances.last()?.eps,
))
}
pub fn total_weight(&self) -> f64 {
util::kahan_babushka_neumaier_sum(self.iter().map(|r| r.weight))
}
pub fn shifted(&self, by: f64) -> DiscreteSF {
self.iter()
.map(|r| Resonance {
eps: r.eps + by,
weight: r.weight,
})
.collect()
}
pub fn mirrored(&self, omega: f64) -> DiscreteSF {
self.iter()
.map(|r| Resonance {
eps: omega - r.eps,
weight: r.weight,
})
.collect()
}
pub fn conv(&self, other: &DiscreteSF) -> DiscreteSF {
self.iter()
.flat_map(|a| {
other.iter().map(move |b| Resonance {
eps: a.eps + b.eps,
weight: a.weight * b.weight,
})
})
.collect()
}
pub fn find(&self, eps: f64) -> Option<&Resonance> {
let eps = if eps == 0.0 { 0.0 } else { eps };
let index = self
.resonances
.binary_search_by(|res| res.eps.total_cmp(&eps))
.ok()?;
Some(&self.resonances[index])
}
}
#[cfg(test)]
mod tests {
use super::*;
use approx::assert_relative_eq;
#[test]
#[should_panic(expected = "must sit at a finite frequency")]
fn from_iter_nan() {
let _ = DiscreteSF::one_resonance(f64::NAN, 1.0);
}
#[test]
#[should_panic(expected = "must sit at a finite frequency")]
fn from_iter_infinite() {
let _ = DiscreteSF::one_resonance(f64::INFINITY, 1.0);
}
#[test]
fn add() {
let sf = DiscreteSF::new();
assert!(sf.is_empty());
assert_eq!(sf.resonances().len(), 0);
assert_eq!(sf.total_weight(), 0.0);
assert_eq!(sf.support(), None);
let sf = DiscreteSF::one_resonance(2.0, 1.0);
assert_eq!(sf.len(), 1);
assert_eq!(sf.resonances()[0].eps, 2.0);
assert_eq!(sf.resonances()[0].weight, 1.0);
assert_eq!(sf.total_weight(), 1.0);
assert_eq!(sf.support(), Some(Segment::new(2.0, 2.0)));
assert!(DiscreteSF::one_resonance(2.0, 0.0).is_empty());
let sf = sf + DiscreteSF::one_resonance(-1.5, 0.25);
assert_eq!(sf.len(), 2);
assert_eq!(sf.total_weight(), 1.25);
assert_eq!(sf.support(), Some(Segment::new(-1.5, 2.0)));
let sf = sf + DiscreteSF::one_resonance(2.0, -1.0);
assert_eq!(sf.len(), 1);
assert_eq!(sf.total_weight(), 0.25);
assert_eq!(sf.support(), Some(Segment::new(-1.5, -1.5)));
}
#[test]
fn from_iter() {
let batch: Vec<Resonance> = (0..100)
.map(|n| Resonance {
eps: ((n * 37) % 20) as f64 - 10.0,
weight: 0.01,
})
.collect();
let bulk = DiscreteSF::from_iter(batch.iter().copied());
let one_by_one = batch.iter().fold(DiscreteSF::new(), |sf, res| {
sf + DiscreteSF::one_resonance(res.eps, res.weight)
});
assert_eq!(bulk.len(), 20);
assert_relative_eq!(bulk.total_weight(), 1.0, epsilon = 1e-15);
assert_eq!(bulk.support(), Some(Segment::new(-10.0, 9.0)));
for (r1, r2) in bulk.iter().zip(&one_by_one) {
assert_eq!(r1.eps, r2.eps);
assert_relative_eq!(r1.weight, r2.weight, epsilon = 1e-15);
}
assert!(bulk.resonances().windows(2).all(|w| w[0].eps < w[1].eps));
let sf = bulk
+ DiscreteSF::from_iter(batch.iter().filter(|r| r.eps < 0.0).map(|r| Resonance {
eps: r.eps,
weight: -r.weight,
}));
assert_eq!(sf.len(), 10);
assert!(sf.iter().all(|r| r.eps >= 0.0));
assert_relative_eq!(sf.total_weight(), 0.5, epsilon = 1e-15);
}
fn moment(sf: &DiscreteSF, n: i32) -> f64 {
sf.iter().map(|r| r.weight * r.eps.powi(n)).sum()
}
#[test]
fn conv() {
let a = DiscreteSF::from_iter([
Resonance {
eps: -1.0,
weight: 0.5,
},
Resonance {
eps: 2.0,
weight: 0.25,
},
]);
let b = DiscreteSF::from_iter([
Resonance {
eps: 0.5,
weight: 2.0,
},
Resonance {
eps: 1.5,
weight: -1.0,
},
]);
let c = a.conv(&b);
assert_eq!(c.len(), 4);
let expected = [(-0.5, 1.0), (0.5, -0.5), (2.5, 0.5), (3.5, -0.25)];
for (res, (eps, weight)) in c.iter().zip(expected) {
assert_relative_eq!(res.eps, eps, epsilon = 1e-14);
assert_relative_eq!(res.weight, weight, epsilon = 1e-14);
}
assert_relative_eq!(
c.total_weight(),
a.total_weight() * b.total_weight(),
epsilon = 1e-14
);
for (l, r) in a.conv(&b).iter().zip(b.conv(&a).iter()) {
assert_eq!(l.eps, r.eps);
assert_eq!(l.weight, r.weight);
}
for n in 0..=4 {
let c_row = util::binomials(n);
let reference: f64 = (0..=n)
.map(|k| c_row[k] * moment(&a, k as i32) * moment(&b, (n - k) as i32))
.sum();
assert_relative_eq!(moment(&c, n as i32), reference, epsilon = 1e-12);
}
}
#[test]
fn conv_degenerate() {
let unit = |eps| DiscreteSF::one_resonance(eps, 1.0);
let a = DiscreteSF::from_iter([
Resonance {
eps: -1.0,
weight: 0.5,
},
Resonance {
eps: 2.0,
weight: 0.25,
},
]);
for (l, r) in a.conv(&unit(0.0)).iter().zip(a.iter()) {
assert_eq!((l.eps, l.weight), (r.eps, r.weight));
}
for (l, r) in a.conv(&unit(3.0)).iter().zip(a.iter()) {
assert_eq!((l.eps, l.weight), (r.eps + 3.0, r.weight));
}
assert!(a.conv(&DiscreteSF::new()).is_empty());
assert!(DiscreteSF::new().conv(&a).is_empty());
let ladder = |w| {
DiscreteSF::from_iter([
Resonance {
eps: 0.0,
weight: 1.0,
},
Resonance {
eps: 1.0,
weight: w,
},
])
};
let binomial = ladder(1.0).conv(&ladder(1.0));
assert_eq!(binomial.len(), 3);
assert_relative_eq!(binomial.find(1.0).unwrap().weight, 2.0, epsilon = 1e-14);
let cancelling = ladder(1.0).conv(&ladder(-1.0));
assert_eq!(cancelling.len(), 2);
assert!(cancelling.find(1.0).is_none());
}
#[test]
fn find() {
let sf = DiscreteSF::from_iter((0..64).map(|n| Resonance {
eps: (n - 32) as f64 / 2.0,
weight: 1.0 / 64.0,
}));
for n in 0..64 {
let eps = (n - 32) as f64 / 2.0;
assert_eq!(sf.find(eps).unwrap().eps, eps);
assert_eq!(sf.find(eps).unwrap().weight, 1.0 / 64.0);
}
assert!(sf.find(0.25).is_none());
assert!(sf.find(100.0).is_none());
assert_eq!(sf.find(-0.0).unwrap().eps, 0.0);
assert_eq!(
DiscreteSF::one_resonance(-0.0, 1.0).find(0.0).unwrap().eps,
0.0
);
}
#[test]
fn neg() {
let sf = DiscreteSF::one_resonance(2.0, 1.0) + DiscreteSF::one_resonance(-1.5, 0.25);
let neg_sf = -sf.clone();
assert_eq!(neg_sf.len(), 2);
assert_eq!(neg_sf.support(), sf.support());
assert_eq!(neg_sf.resonances()[0].weight, -0.25);
assert_eq!(neg_sf.resonances()[1].weight, -1.0);
assert_eq!(neg_sf.total_weight(), -sf.total_weight());
assert_eq!((-neg_sf).total_weight(), sf.total_weight());
assert!((-DiscreteSF::new()).is_empty());
}
#[test]
fn sub() {
let sf = DiscreteSF::one_resonance(2.0, 1.0) + DiscreteSF::one_resonance(-1.5, 0.25);
let diff = sf.clone() - DiscreteSF::one_resonance(2.0, 0.75);
assert_eq!(diff.len(), 2);
assert_relative_eq!(diff.find(2.0).unwrap().weight, 0.25, epsilon = 1e-15);
assert_eq!(diff.find(-1.5).unwrap().weight, 0.25);
let diff = sf.clone() - DiscreteSF::one_resonance(4.0, 0.5);
assert_eq!(diff.len(), 3);
assert_eq!(diff.find(4.0).unwrap().weight, -0.5);
assert_relative_eq!(diff.total_weight(), 0.75, epsilon = 1e-15);
let zero = sf.clone() - sf;
assert!(zero.is_empty());
assert_eq!(zero.total_weight(), 0.0);
}
#[test]
fn mul() {
let sf = DiscreteSF::one_resonance(2.0, 1.0) + DiscreteSF::one_resonance(-1.5, 0.25);
let sf = sf * 4.0;
assert_eq!(sf.len(), 2);
assert_eq!(sf.resonances()[0].weight, 1.0);
assert_eq!(sf.resonances()[1].weight, 4.0);
assert_eq!(sf.total_weight(), 5.0);
let sf = f64::MIN_POSITIVE * (f64::MIN_POSITIVE * sf);
assert!(sf.is_empty());
assert_eq!(sf.total_weight(), 0.0);
let sf = DiscreteSF::one_resonance(2.0, 1.0) * 0.0;
assert!(sf.is_empty());
assert_eq!(sf.total_weight(), 0.0);
}
}