emath/
history.rs

1use std::collections::VecDeque;
2
3/// This struct tracks recent values of some time series.
4///
5/// It can be used as a smoothing filter for e.g. latency, fps etc,
6/// or to show a log or graph of recent events.
7///
8/// It has a minimum and maximum length, as well as a maximum storage time.
9/// * The minimum length is to ensure you have enough data for an estimate.
10/// * The maximum length is to make sure the history doesn't take up too much space.
11/// * The maximum age is to make sure the estimate isn't outdated.
12///
13/// Time difference between values can be zero, but never negative.
14///
15/// This can be used for things like smoothed averages (for e.g. FPS)
16/// or for smoothed velocity (e.g. mouse pointer speed).
17/// All times are in seconds.
18#[derive(Clone, Debug)]
19#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
20pub struct History<T> {
21    /// In elements, i.e. of `values.len()`.
22    /// The length is initially zero, but once past `min_len` will not shrink below it.
23    min_len: usize,
24
25    /// In elements, i.e. of `values.len()`.
26    max_len: usize,
27
28    /// In seconds.
29    max_age: f32,
30
31    /// Total number of elements seen ever
32    total_count: u64,
33
34    /// (time, value) pairs, oldest front, newest back.
35    /// Time difference between values can be zero, but never negative.
36    values: VecDeque<(f64, T)>,
37}
38
39impl<T> History<T>
40where
41    T: Copy,
42{
43    /// Example:
44    /// ```
45    /// # use emath::History;
46    /// # fn now() -> f64 { 0.0 }
47    /// // Drop events that are older than one second,
48    /// // as long we keep at least two events. Never keep more than a hundred events.
49    /// let mut history = History::new(2..100, 1.0);
50    /// assert_eq!(history.average(), None);
51    /// history.add(now(), 40.0_f32);
52    /// history.add(now(), 44.0_f32);
53    /// assert_eq!(history.average(), Some(42.0));
54    /// ```
55    pub fn new(length_range: core::ops::Range<usize>, max_age: f32) -> Self {
56        Self {
57            min_len: length_range.start,
58            max_len: length_range.end,
59            max_age,
60            total_count: 0,
61            values: Default::default(),
62        }
63    }
64
65    #[inline]
66    pub fn max_len(&self) -> usize {
67        self.max_len
68    }
69
70    #[inline]
71    pub fn max_age(&self) -> f32 {
72        self.max_age
73    }
74
75    #[inline]
76    pub fn is_empty(&self) -> bool {
77        self.values.is_empty()
78    }
79
80    /// Current number of values kept in history
81    #[inline]
82    pub fn len(&self) -> usize {
83        self.values.len()
84    }
85
86    /// Total number of values seen.
87    /// Includes those that have been discarded due to `max_len` or `max_age`.
88    #[inline]
89    pub fn total_count(&self) -> u64 {
90        self.total_count
91    }
92
93    pub fn latest(&self) -> Option<T> {
94        self.values.back().map(|(_, value)| *value)
95    }
96
97    pub fn latest_mut(&mut self) -> Option<&mut T> {
98        self.values.back_mut().map(|(_, value)| value)
99    }
100
101    /// Amount of time contained from start to end in this [`History`].
102    pub fn duration(&self) -> f32 {
103        if let (Some(front), Some(back)) = (self.values.front(), self.values.back()) {
104            (back.0 - front.0) as f32
105        } else {
106            0.0
107        }
108    }
109
110    /// `(time, value)` pairs
111    /// Time difference between values can be zero, but never negative.
112    // TODO(emilk): impl IntoIter
113    pub fn iter(&self) -> impl ExactSizeIterator<Item = (f64, T)> + '_ {
114        self.values.iter().map(|(time, value)| (*time, *value))
115    }
116
117    pub fn values(&self) -> impl ExactSizeIterator<Item = T> + '_ {
118        self.values.iter().map(|(_time, value)| *value)
119    }
120
121    #[inline]
122    pub fn clear(&mut self) {
123        self.values.clear();
124    }
125
126    /// Values must be added with a monotonically increasing time, or at least not decreasing.
127    pub fn add(&mut self, now: f64, value: T) {
128        if let Some((last_time, _)) = self.values.back() {
129            debug_assert!(
130                *last_time <= now,
131                "Time shouldn't move backwards. Last time: {last_time}, new time: {now}"
132            );
133        }
134        self.total_count += 1;
135        self.values.push_back((now, value));
136        self.flush(now);
137    }
138
139    /// Mean time difference between values in this [`History`].
140    pub fn mean_time_interval(&self) -> Option<f32> {
141        if let (Some(first), Some(last)) = (self.values.front(), self.values.back()) {
142            let n = self.len();
143            if n >= 2 {
144                Some((last.0 - first.0) as f32 / ((n - 1) as f32))
145            } else {
146                None
147            }
148        } else {
149            None
150        }
151    }
152
153    // Mean number of events per second.
154    pub fn rate(&self) -> Option<f32> {
155        self.mean_time_interval().map(|time| 1.0 / time)
156    }
157
158    /// Remove samples that are too old.
159    pub fn flush(&mut self, now: f64) {
160        while self.values.len() > self.max_len {
161            self.values.pop_front();
162        }
163        let oldest_allowed_time = now - self.max_age as f64;
164        while self.min_len < self.values.len()
165            && self
166                .values
167                .pop_front_if(|&mut (front_time, _)| front_time < oldest_allowed_time)
168                .is_some()
169        {
170            // Keep popping while the oldest sample is too old.
171        }
172    }
173}
174
175impl<T> History<T>
176where
177    T: Copy,
178    T: core::iter::Sum,
179    T: core::ops::Div<f32, Output = T>,
180{
181    #[inline]
182    pub fn sum(&self) -> T {
183        self.values().sum()
184    }
185
186    pub fn average(&self) -> Option<T> {
187        let num = self.len();
188        if num > 0 {
189            Some(self.sum() / (num as f32))
190        } else {
191            None
192        }
193    }
194}
195
196impl<T> History<T>
197where
198    T: Copy,
199    T: core::iter::Sum,
200    T: core::ops::Div<f32, Output = T>,
201    T: core::ops::Mul<f32, Output = T>,
202{
203    /// Average times rate.
204    /// If you are keeping track of individual sizes of things (e.g. bytes),
205    /// this will estimate the bandwidth (bytes per second).
206    pub fn bandwidth(&self) -> Option<T> {
207        Some(self.average()? * self.rate()?)
208    }
209}
210
211impl<T, Vel> History<T>
212where
213    T: Copy,
214    T: core::ops::Sub<Output = Vel>,
215    Vel: core::ops::Div<f32, Output = Vel>,
216{
217    /// Calculate a smooth velocity (per second) over the entire time span.
218    /// Calculated as the last value minus the first value over the elapsed time between them.
219    pub fn velocity(&self) -> Option<Vel> {
220        if let (Some(first), Some(last)) = (self.values.front(), self.values.back()) {
221            let dt = (last.0 - first.0) as f32;
222            if dt > 0.0 {
223                Some((last.1 - first.1) / dt)
224            } else {
225                None
226            }
227        } else {
228            None
229        }
230    }
231}
emath/history.rs

emath/
history.rs
