use std::collections::VecDeque;
#[derive(Clone, Debug)]
pub(crate) struct Ring {
buf: Vec<f64>,
head: usize,
len: usize,
}
impl Ring {
pub(crate) fn new(cap: usize) -> Self {
Self {
buf: vec![0.0; cap],
head: 0,
len: 0,
}
}
pub(crate) fn cap(&self) -> usize {
self.buf.len()
}
pub(crate) fn is_full(&self) -> bool {
self.len == self.buf.len()
}
pub(crate) fn get(&self, i: usize) -> f64 {
self.buf[(self.head + i) % self.buf.len()]
}
pub(crate) fn iter(&self) -> impl Iterator<Item = f64> + '_ {
(0..self.len).map(|i| self.get(i))
}
pub(crate) fn push(&mut self, x: f64) -> Option<f64> {
let cap = self.buf.len();
if cap == 0 {
return Some(x);
}
if self.len < cap {
self.buf[(self.head + self.len) % cap] = x;
self.len += 1;
None
} else {
let old = self.buf[self.head];
self.buf[self.head] = x;
self.head = (self.head + 1) % cap;
Some(old)
}
}
}
#[derive(Clone, Debug)]
pub(crate) struct RollingSum {
ring: Ring,
sum: f64,
since_exact: usize,
}
impl RollingSum {
pub(crate) fn new(n: usize) -> Self {
Self {
ring: Ring::new(n.saturating_sub(1)),
sum: 0.0,
since_exact: 0,
}
}
pub(crate) fn n(&self) -> usize {
self.ring.cap() + 1
}
pub(crate) fn peek(&self, x: f64) -> f64 {
if x.is_nan() || !self.ring.is_full() {
return f64::NAN;
}
self.sum + x
}
pub(crate) fn push(&mut self, x: f64) {
if x.is_nan() {
return;
}
match self.ring.push(x) {
Some(old) => self.sum = self.sum - old + x,
None => self.sum += x,
}
self.since_exact += 1;
if self.since_exact >= self.n() {
self.sum = self.ring.iter().sum();
self.since_exact = 0;
}
}
pub(crate) fn window(&self) -> &Ring {
&self.ring
}
}
#[derive(Clone, Debug)]
pub(crate) struct Sma(RollingSum);
impl Sma {
pub(crate) fn new(n: usize) -> Self {
Self(RollingSum::new(n))
}
pub(crate) fn peek(&self, x: f64) -> f64 {
self.0.peek(x) / self.0.n() as f64
}
pub(crate) fn push(&mut self, x: f64) {
self.0.push(x);
}
pub(crate) fn window(&self) -> &Ring {
self.0.window()
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum SmoothKind {
Ema,
Rma,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Smooth {
kind: SmoothKind,
n: usize,
alpha: f64,
count: usize,
acc: f64,
}
impl Smooth {
pub(crate) fn new(kind: SmoothKind, n: usize) -> Self {
let n = n.max(1);
Self {
kind,
n,
alpha: 2.0 / (n as f64 + 1.0),
count: 0,
acc: 0.0,
}
}
pub(crate) fn ema(n: usize) -> Self {
Self::new(SmoothKind::Ema, n)
}
pub(crate) fn rma(n: usize) -> Self {
Self::new(SmoothKind::Rma, n)
}
fn step(&self, x: f64) -> f64 {
if self.count < self.n {
if self.count + 1 == self.n {
(self.acc + x) / self.n as f64
} else {
f64::NAN
}
} else {
match self.kind {
SmoothKind::Ema => self.acc + self.alpha * (x - self.acc),
SmoothKind::Rma => self.acc + (x - self.acc) / self.n as f64,
}
}
}
pub(crate) fn peek(&self, x: f64) -> f64 {
if x.is_nan() { f64::NAN } else { self.step(x) }
}
pub(crate) fn push(&mut self, x: f64) {
if x.is_nan() {
return;
}
if self.count + 1 < self.n {
self.acc += x;
} else {
self.acc = self.step(x);
}
self.count = (self.count + 1).min(self.n);
}
}
#[derive(Clone, Debug)]
pub(crate) struct Wma {
ring: Ring,
sum: f64,
weighted: f64,
since_exact: usize,
}
impl Wma {
pub(crate) fn new(n: usize) -> Self {
Self {
ring: Ring::new(n.max(1) - 1),
sum: 0.0,
weighted: 0.0,
since_exact: 0,
}
}
fn n(&self) -> usize {
self.ring.cap() + 1
}
pub(crate) fn peek(&self, x: f64) -> f64 {
if x.is_nan() || !self.ring.is_full() {
return f64::NAN;
}
let n = self.n() as f64;
(self.weighted + n * x) / (n * (n + 1.0) / 2.0)
}
pub(crate) fn push(&mut self, x: f64) {
if x.is_nan() {
return;
}
let cap = self.ring.cap();
let was_full = self.ring.is_full();
let old = self.ring.push(x);
self.since_exact += 1;
match old {
Some(old) if was_full && cap > 0 && self.since_exact < self.n() => {
self.weighted = self.weighted - self.sum + cap as f64 * x;
self.sum = self.sum - old + x;
}
_ => self.recompute(),
}
}
fn recompute(&mut self) {
let mut sum = 0.0;
let mut weighted = 0.0;
for (i, c) in self.ring.iter().enumerate() {
sum += c;
weighted += (i + 1) as f64 * c;
}
self.sum = sum;
self.weighted = weighted;
self.since_exact = 0;
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct WilderSum {
n: usize,
count: usize,
sum: f64,
}
impl WilderSum {
pub(crate) fn new(n: usize) -> Self {
Self {
n: n.max(1),
count: 0,
sum: 0.0,
}
}
fn step(&self, x: f64) -> f64 {
if self.count < self.n {
self.sum + x
} else {
self.sum - self.sum / self.n as f64 + x
}
}
pub(crate) fn peek(&self, x: f64) -> f64 {
if x.is_nan() || self.count + 1 < self.n {
f64::NAN
} else {
self.step(x)
}
}
pub(crate) fn push(&mut self, x: f64) {
if x.is_nan() {
return;
}
self.sum = self.step(x);
self.count = (self.count + 1).min(self.n);
}
}
#[derive(Clone, Debug)]
pub(crate) struct RollingExtreme {
n: usize,
max: bool,
deque: VecDeque<(u64, f64)>,
seq: u64,
}
impl RollingExtreme {
pub(crate) fn max(n: usize) -> Self {
Self::new(n, true)
}
pub(crate) fn min(n: usize) -> Self {
Self::new(n, false)
}
fn new(n: usize, max: bool) -> Self {
let n = n.max(1);
Self {
n,
max,
deque: VecDeque::with_capacity(n),
seq: 0,
}
}
fn beats(&self, a: f64, b: f64) -> bool {
if self.max { a >= b } else { a <= b }
}
fn front(&self) -> Option<(u64, f64)> {
let lo = self.seq + 1;
self.deque
.iter()
.copied()
.find(|&(s, _)| s + self.n as u64 >= lo)
}
pub(crate) fn peek(&self, x: f64) -> f64 {
self.peek_at(x).0
}
pub(crate) fn peek_at(&self, x: f64) -> (f64, usize) {
if x.is_nan() || self.seq + 1 < self.n as u64 {
return (f64::NAN, 0);
}
match self.front() {
Some((s, v)) if !self.beats(x, v) => (v, (self.seq - s) as usize),
_ => (x, 0),
}
}
pub(crate) fn push(&mut self, x: f64) {
if x.is_nan() {
return;
}
while let Some(&(_, b)) = self.deque.back() {
if self.beats(x, b) {
self.deque.pop_back();
} else {
break;
}
}
let s = self.seq;
while let Some(&(f, _)) = self.deque.front() {
if f + self.n as u64 <= s + 1 {
self.deque.pop_front();
} else {
break;
}
}
self.deque.push_back((s, x));
self.seq += 1;
}
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
fn close(a: f64, b: f64) -> bool {
(a.is_nan() && b.is_nan()) || (a - b).abs() <= 1e-9 * a.abs().max(b.abs()).max(1.0)
}
fn run(xs: &[f64], step: impl FnMut(f64) -> f64) -> Vec<f64> {
xs.iter().copied().map(step).collect()
}
fn naive(xs: &[f64], n: usize, f: impl Fn(&[f64]) -> f64) -> Vec<f64> {
(0..xs.len())
.map(|t| {
if t + 1 >= n {
f(&xs[t + 1 - n..=t])
} else {
f64::NAN
}
})
.collect()
}
fn values() -> impl Strategy<Value = Vec<f64>> {
prop::collection::vec(
prop_oneof![(-1000i32..1000).prop_map(f64::from), -1e3..1e3f64],
0..200,
)
}
proptest! {
#[test]
fn sma_matches_the_window_mean(xs in values(), n in 1usize..30) {
let mut k = Sma::new(n);
let got = run(&xs, |x| { let y = k.peek(x); k.push(x); y });
let want = naive(&xs, n, |w| w.iter().sum::<f64>() / n as f64);
prop_assert!(got.iter().zip(&want).all(|(a, b)| close(*a, *b)), "{got:?} {want:?}");
}
#[test]
fn wma_matches_the_weighted_mean(xs in values(), n in 1usize..30) {
let mut k = Wma::new(n);
let got = run(&xs, |x| { let y = k.peek(x); k.push(x); y });
let den = (n * (n + 1) / 2) as f64;
let want = naive(&xs, n, |w| {
w.iter().enumerate().map(|(i, v)| (i + 1) as f64 * v).sum::<f64>() / den
});
prop_assert!(got.iter().zip(&want).all(|(a, b)| close(*a, *b)), "{got:?} {want:?}");
}
#[test]
fn extremes_match_the_window(xs in values(), n in 1usize..30) {
let (mut hi, mut lo) = (RollingExtreme::max(n), RollingExtreme::min(n));
let mut got = Vec::new();
for &x in &xs {
got.push((hi.peek_at(x), lo.peek_at(x)));
hi.push(x);
lo.push(x);
}
for t in 0..xs.len() {
if t + 1 < n {
prop_assert!(got[t].0.0.is_nan());
continue;
}
let w = &xs[t + 1 - n..=t];
let max = w.iter().copied().fold(f64::MIN, f64::max);
let min = w.iter().copied().fold(f64::MAX, f64::min);
let back_max = w.iter().rev().position(|&v| v.to_bits() == max.to_bits()).unwrap();
let back_min = w.iter().rev().position(|&v| v.to_bits() == min.to_bits()).unwrap();
prop_assert_eq!(got[t].0, (max, back_max));
prop_assert_eq!(got[t].1, (min, back_min));
}
}
#[test]
fn smoothing_follows_the_recurrence(xs in values(), n in 1usize..30, lead in 0usize..5, ema in any::<bool>()) {
let mut input = vec![f64::NAN; lead];
input.extend_from_slice(&xs);
let mut k = if ema { Smooth::ema(n) } else { Smooth::rma(n) };
let got = run(&input, |x| { let y = k.peek(x); k.push(x); y });
let mut want = vec![f64::NAN; input.len()];
if xs.len() >= n {
let mut e = xs[..n].iter().sum::<f64>() / n as f64;
want[lead + n - 1] = e;
for t in n..xs.len() {
e = if ema {
e + 2.0 / (n as f64 + 1.0) * (xs[t] - e)
} else {
e + (xs[t] - e) / n as f64
};
want[lead + t] = e;
}
}
prop_assert!(got.iter().zip(&want).all(|(a, b)| a.to_bits() == b.to_bits() || close(*a, *b)));
}
#[test]
fn peek_has_no_effect(xs in values(), n in 1usize..20, extra in values()) {
let (mut a, mut b) = (Wma::new(n), Wma::new(n));
let (mut c, mut d) = (RollingExtreme::max(n), RollingExtreme::max(n));
for (i, &x) in xs.iter().enumerate() {
for &e in extra.iter().skip(i % 3).take(2) {
let _ = (b.peek(e), d.peek(e));
}
prop_assert_eq!(a.peek(x).to_bits(), b.peek(x).to_bits());
prop_assert_eq!(c.peek(x).to_bits(), d.peek(x).to_bits());
a.push(x); b.push(x); c.push(x); d.push(x);
}
}
}
}