pull_timer/
lib.rs

1use std::collections::VecDeque;
2
3#[derive(Debug, Clone)]
4pub struct PullTimer<T>(VecDeque<(u32, T)>);
5
6impl<T> PullTimer<T> {
7    pub fn new() -> PullTimer<T> {
8        PullTimer(VecDeque::new())
9    }
10
11    pub fn next_in(&self) -> Option<u32> {
12        self.0.front().map(|&(deadline, _)| deadline)
13    }
14
15    pub fn update(&mut self, elapsed: u32) {
16        let mut remaining = elapsed;
17        for (delta, _) in &mut self.0 {
18            let temp = *delta;
19            *delta = delta.saturating_sub(elapsed);
20            remaining = remaining.saturating_sub(temp);
21
22            if remaining == 0 {
23                break;
24            }
25        }
26    }
27
28    pub fn add(&mut self, deadline: u32, event: T) {
29        let mut sum = 0;
30        let mut insertion_point = 0;
31
32        for (index, &(delta, _)) in self.0.iter().enumerate() {
33            if sum + delta > deadline {
34                break;
35            }
36            insertion_point = index + 1;
37            sum += delta;
38        }
39
40        let insertion_delta = deadline - sum;
41
42        if let Some((delta, _)) = &mut self.0.get_mut(insertion_point) {
43            *delta = delta.saturating_sub(insertion_delta);
44        }
45
46        self.0.insert(insertion_point, (insertion_delta, event));
47    }
48
49    pub fn remove(&mut self, event: T) -> Option<u32>
50    where
51        T: PartialEq,
52    {
53        let mut sum = 0;
54        let mut target = None;
55
56        for (index, &(delta, ref element)) in self.0.iter().enumerate() {
57            sum += delta;
58            if *element == event {
59                target = Some(index);
60                break;
61            }
62        }
63
64        let index = target?;
65        let (delta, _) = self.0.remove(index)?;
66
67        if let Some((next_delta, _)) = self.0.get_mut(index) {
68            *next_delta += delta;
69        }
70
71        Some(sum)
72    }
73
74    pub fn poll(&mut self) -> Option<T> {
75        let &(delta, _) = self.0.front()?;
76
77        if delta == 0 {
78            self.0.pop_front().map(|(_, event)| event)
79        } else {
80            None
81        }
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn timer_preserves_fifo_order() {
91        let mut timer = PullTimer::new();
92
93        timer.add(0, "testing");
94        timer.add(0, "one two three");
95
96        assert_eq!(timer.poll(), Some("testing"));
97        assert_eq!(timer.poll(), Some("one two three"));
98        assert_eq!(timer.poll(), None);
99    }
100
101    #[test]
102    fn timer_fires_in_order() {
103        let mut timer = PullTimer::new();
104
105        timer.add(4, "test");
106        timer.add(3, "a");
107        timer.add(2, "is");
108        timer.add(1, "this");
109
110        timer.update(4);
111
112        assert_eq!(timer.poll(), Some("this"));
113        assert_eq!(timer.poll(), Some("is"));
114        assert_eq!(timer.poll(), Some("a"));
115        assert_eq!(timer.poll(), Some("test"));
116        assert_eq!(timer.poll(), None);
117    }
118
119    #[test]
120    fn timer_fires_in_time() {
121        let mut timer = PullTimer::new();
122
123        timer.add(40, 40);
124        timer.add(20, 20);
125        timer.add(0, 0);
126        timer.add(30, 30);
127        timer.add(10, 10);
128
129        for i in 0..=41 {
130            if let Some(value) = timer.poll() {
131                assert_eq!(value, i);
132            }
133            timer.update(1);
134        }
135    }
136
137    #[test]
138    fn timer_next_in() {
139        let mut timer = PullTimer::new();
140
141        timer.add(0, "hi");
142        timer.add(20, "!");
143        timer.add(10, "there");
144
145        assert_eq!(timer.next_in(), Some(0));
146        assert_eq!(timer.poll(), Some("hi"));
147
148        assert_eq!(timer.next_in(), Some(10));
149
150        timer.update(10);
151        assert_eq!(timer.next_in(), Some(0));
152        assert_eq!(timer.poll(), Some("there"));
153
154        timer.update(3);
155        assert_eq!(timer.next_in(), Some(7));
156    }
157
158    #[test]
159    fn timer_remove() {
160        let mut timer = PullTimer::new();
161
162        timer.add(100, "boom!");
163        timer.update(50);
164        assert_eq!(timer.remove("boom!"), Some(50));
165        assert_eq!(timer.next_in(), None);
166    }
167
168    #[test]
169    fn timer_fires_after_remove() {
170        let mut timer = PullTimer::new();
171
172        timer.add(30, 30);
173        timer.add(20, 20);
174        timer.add(40, 40);
175        timer.add(10, 10);
176        timer.add(50, 50);
177
178        assert_eq!(timer.remove(50), Some(50));
179        assert_eq!(timer.remove(10), Some(10));
180
181        for i in 0..=41 {
182            if let Some(value) = timer.poll() {
183                assert_eq!(value, i);
184            }
185            timer.update(1);
186        }
187    }
188}
pull_timer/lib.rs

pull_timer/
lib.rs
