1use std::collections::vec_deque::Drain;
2use std::collections::VecDeque;
3use core::time::Duration;
4use std::marker::PhantomData;
5use std::ops::RangeBounds;
6
7type Item<T> = (Duration, T);
8
9pub type TimeVecItem<T> = Item<T>;
10
11#[derive(Clone, Debug)]
12pub struct TimeVec<T> {
13 pub limit: Duration,
14 buffer: VecDeque<Item<T>>,
15}
16
17impl<T> TimeVec<T> {
18 pub fn new(limit: Duration, capacity: usize) -> Self {
19 let buffer = VecDeque::with_capacity(capacity);
20 Self { limit, buffer }
21 }
22
23 pub fn builder() -> TimeVecBuilder<T> {
24 TimeVecBuilder::<T>::default()
25 }
26
27 #[inline]
28 pub fn checked_duration(&self) -> Option<Duration> {
29 self.buffer
30 .front()
31 .map(|oldest| self.buffer.back().unwrap().0 - oldest.0)
32 }
33
34 #[inline]
35 pub fn duration(&self) -> Duration {
36 self.checked_duration().unwrap_or(Duration::ZERO)
37 }
38
39 #[inline]
40 fn timestamp_is_ok(&self, value: Duration) -> bool {
41 self.buffer
42 .back()
43 .map(|i| value > i.0)
44 .unwrap_or(true)
45 }
46
47 #[inline]
48 pub fn push_back_checked(&mut self, timestamp: Duration, item: T) -> Option<Drain<Item<T>>> {
49 self.timestamp_is_ok(timestamp).then(|| {
50 self.push_back_unchecked(timestamp, item)
51 })
52 }
53
54 #[inline]
55 pub fn push_back(&mut self, timestamp: Duration, item: T) -> Drain<Item<T>> {
56 assert!(self.timestamp_is_ok(timestamp), "Timestamp is older then previous.");
57 self.push_back_unchecked(timestamp, item)
58 }
59
60 #[inline]
61 pub fn push_back_unchecked(&mut self, timestamp: Duration, item: T) -> Drain<Item<T>> {
62 self.buffer.push_back((timestamp, item));
63
64 let partition_timestamp = timestamp.saturating_sub(self.limit);
65 let partition_point = self.buffer.partition_point(|i| i.0 < partition_timestamp);
66
67 self.buffer.drain(0..partition_point)
68 }
69
70 #[inline]
71 pub fn pop_front(&mut self) -> Option<Item<T>> {
72 self.buffer.pop_front()
73 }
74
75 #[inline]
76 pub fn pop_back(&mut self) -> Option<Item<T>> {
77 self.buffer.pop_back()
78 }
79
80 #[inline]
81 pub fn duration_from_back(&self, duration: &Duration) -> Option<Duration> {
82 self.buffer.back().map(|item| duration.checked_sub(item.0)).flatten()
83 }
84
85 #[inline]
86 pub fn clear(&mut self) {
87 self.buffer.clear()
88 }
89
90 #[inline]
91 pub fn len(&self) -> usize {
92 self.buffer.len()
93 }
94
95 #[inline]
96 pub fn iter<'a>(&'a self) -> impl ExactSizeIterator<Item = &Item<T>> + 'a {
97 self.buffer.iter()
98 }
99
100 #[inline]
101 pub fn iter_data<'a>(&'a self) -> impl ExactSizeIterator<Item = &T> + 'a {
102 self.buffer.iter().map(|snap| &snap.1)
103 }
104
105 #[inline]
106 pub fn iter_time<'a>(&'a self) -> impl ExactSizeIterator<Item = &Duration> + 'a {
107 self.buffer.iter().map(|snap| &snap.0)
108 }
109
110 #[inline]
111 pub fn is_empty(&self) -> bool {
112 self.buffer.is_empty()
113 }
114
115 #[inline]
116 pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> Drain<Item<T>> {
117 self.buffer.drain(range)
118 }
119}
120
121#[derive(Copy, Clone, Debug)]
122pub struct TimeVecBuilder<T> {
123 pub limit: Option<Duration>,
124 pub capacity: Option<usize>,
125 _item: PhantomData<T>,
126}
127
128impl<T> Default for TimeVecBuilder<T> {
129 fn default() -> Self {
130 Self { limit: None, capacity: None, _item: PhantomData }
131 }
132}
133
134impl<T> TimeVecBuilder<T> {
135 pub fn with_limit(mut self, value: Duration) -> Self {
136 self.limit = Some(value);
137 self
138 }
139
140 pub fn with_limit_secs(self, value: u64) -> Self {
141 self.with_limit(Duration::from_secs(value))
142 }
143
144 pub fn with_limit_micros(self, value: u64) -> Self {
145 self.with_limit(Duration::from_micros(value))
146 }
147
148 pub fn with_limit_millis(self, value: u64) -> Self {
149 self.with_limit(Duration::from_millis(value))
150 }
151
152 pub fn with_limit_nanos(self, value: u64) -> Self {
153 self.with_limit(Duration::from_nanos(value))
154 }
155
156 pub fn with_capacity(mut self, value: usize) -> Self {
157 self.capacity = Some(value);
158 self
159 }
160
161 pub fn build(self) -> TimeVec<T> {
162 TimeVec {
163 limit: self.limit.unwrap_or_default(),
164 buffer: self.capacity
165 .map(|value| VecDeque::<Item<T>>::with_capacity(value))
166 .unwrap_or_default()
167
168 }
169 }
170}
171
172#[cfg(test)]
173mod tests {
174 use super::*;
175 use std::time::Duration;
176
177 #[test]
178 fn with_zero_limit() {
179 let mut tv = TimeVec::<()>::builder()
180 .with_limit(Duration::ZERO)
181 .build();
182 assert!(tv.is_empty());
183
184 assert_eq!(tv.checked_duration(), None);
185 assert_eq!(tv.duration(), Duration::ZERO);
186 assert_eq!(tv.len(), 0);
187
188 tv.push_back(Duration::from_secs(1), ());
189 assert_eq!(tv.checked_duration(), Some(Duration::ZERO));
190 assert_eq!(tv.duration(), Duration::ZERO);
191 assert_eq!(tv.len(), 1);
192 }
193
194 #[test]
195 fn push_two_items_with_same_timestamp() {
196 let mut tv = TimeVec::<()>::builder()
197 .with_limit_nanos(1)
198 .build();
199
200 tv.push_back_checked(Duration::from_secs(1), ());
201 assert_eq!(tv.len(), 1);
202
203 tv.push_back_checked(Duration::from_secs(1), ());
204 assert_eq!(tv.len(), 1);
205 }
206
207 #[test]
208 fn min_limit() {
209 let mut tv = TimeVec::<()>::builder()
210 .with_limit_nanos(1)
211 .build();
212
213 tv.push_back(Duration::ZERO, ());
214 assert_eq!(tv.len(), 1);
215
216 tv.push_back(Duration::from_nanos(1), ());
217 assert_eq!(tv.len(), 2);
218
219 tv.push_back(Duration::from_nanos(2), ());
220 assert_eq!(tv.checked_duration(), Some(Duration::from_nanos(1)));
221 assert_eq!(tv.len(), 2);
222 }
223
224 #[test]
225 fn push_above_the_non_min_limit() {
226 let mut tv = TimeVec::<()>::builder()
227 .with_limit_nanos(3)
228 .build();
229
230 tv.push_back(Duration::ZERO, ());
231 tv.push_back(Duration::from_nanos(1), ());
232 tv.push_back(Duration::from_nanos(2), ());
233 tv.push_back(Duration::from_nanos(3), ());
234 assert_eq!(tv.len(), 4);
235
236 tv.push_back(Duration::from_nanos(4), ());
237 assert_eq!(tv.len(), 4);
238 }
239}