1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

use std::collections::VecDeque;

/// This struct tracks recent values of some time series.
///
/// One use is to show a log of recent events,
/// or show a graph over recent events.
///
/// It has both a maximum length and a maximum storage time.
/// Elements are dropped when either max length or max age is reached.
///
/// Time difference between values can be zero, but never negative.
///
/// This can be used for things like smoothed averages (for e.g. FPS)
/// or for smoothed velocity (e.g. mouse pointer speed).
/// All times are in seconds.
#[derive(Clone, Debug)]
pub struct History<T> {
    /// In elements, i.e. of `values.len()`
    max_len: usize,

    /// In seconds
    max_age: f64, // TODO: f32

    /// Total number of elements seen ever
    total_count: u64,

    /// (time, value) pairs, oldest front, newest back.
    /// Time difference between values can be zero, but never negative.
    values: VecDeque<(f64, T)>,
}

impl<T> History<T>
where
    T: Copy,
{
    pub fn new(max_len: usize, max_age: f64) -> Self {
        Self::from_max_len_age(max_len, max_age)
    }

    pub fn from_max_len_age(max_len: usize, max_age: f64) -> Self {
        Self {
            max_len,
            max_age,
            total_count: 0,
            values: Default::default(),
        }
    }

    pub fn max_len(&self) -> usize {
        self.max_len
    }

    pub fn max_age(&self) -> f32 {
        self.max_age as f32
    }

    pub fn is_empty(&self) -> bool {
        self.values.is_empty()
    }

    /// Current number of values kept in history
    pub fn len(&self) -> usize {
        self.values.len()
    }

    /// Total number of values seen.
    /// Includes those that have been discarded due to `max_len` or `max_age`.
    pub fn total_count(&self) -> u64 {
        self.total_count
    }

    pub fn latest(&self) -> Option<T> {
        self.values.back().map(|(_, value)| *value)
    }

    pub fn latest_mut(&mut self) -> Option<&mut T> {
        self.values.back_mut().map(|(_, value)| value)
    }

    /// Amount of time contained from start to end in this `History`.
    pub fn duration(&self) -> f32 {
        if let (Some(front), Some(back)) = (self.values.front(), self.values.back()) {
            (back.0 - front.0) as f32
        } else {
            0.0
        }
    }

    /// `(time, value)` pairs
    /// Time difference between values can be zero, but never negative.
    // TODO: impl IntoIter
    pub fn iter<'a>(&'a self) -> impl Iterator<Item = (f64, T)> + 'a {
        self.values.iter().map(|(time, value)| (*time, *value))
    }

    pub fn values<'a>(&'a self) -> impl Iterator<Item = T> + 'a {
        self.values.iter().map(|(_time, value)| *value)
    }

    pub fn clear(&mut self) {
        self.values.clear()
    }

    /// Values must be added with a monotonically increasing time, or at least not decreasing.
    pub fn add(&mut self, now: f64, value: T) {
        if let Some((last_time, _)) = self.values.back() {
            debug_assert!(now >= *last_time, "Time shouldn't move backwards");
        }
        self.total_count += 1;
        self.values.push_back((now, value));
        self.flush(now);
    }

    /// Mean time difference between values in this `History`.
    pub fn mean_time_interval(&self) -> Option<f32> {
        if let (Some(first), Some(last)) = (self.values.front(), self.values.back()) {
            let n = self.len();
            if n >= 2 {
                Some((last.0 - first.0) as f32 / ((n - 1) as f32))
            } else {
                None
            }
        } else {
            None
        }
    }

    /// Remove samples that are too old
    pub fn flush(&mut self, now: f64) {
        while self.values.len() > self.max_len {
            self.values.pop_front();
        }
        while let Some((front_time, _)) = self.values.front() {
            if *front_time < now - self.max_age {
                self.values.pop_front();
            } else {
                break;
            }
        }
    }
}

impl<T> History<T>
where
    T: Copy,
    T: std::iter::Sum,
    T: std::ops::Div<f32, Output = T>,
{
    pub fn sum(&self) -> T {
        self.values().sum()
    }

    pub fn average(&self) -> Option<T> {
        let num = self.len();
        if num > 0 {
            Some(self.sum() / (num as f32))
        } else {
            None
        }
    }
}

impl<T, Vel> History<T>
where
    T: Copy,
    T: std::ops::Sub<Output = Vel>,
    Vel: std::ops::Div<f32, Output = Vel>,
{
    /// Calculate a smooth velocity (per second) over the entire time span
    pub fn velocity(&self) -> Option<Vel> {
        if let (Some(first), Some(last)) = (self.values.front(), self.values.back()) {
            let dt = (last.0 - first.0) as f32;
            if dt > 0.0 {
                Some((last.1 - first.1) / dt)
            } else {
                None
            }
        } else {
            None
        }
    }
}