Data structures and helpers for debouncing a stream of events: removing duplicate events occurring closely in time.
 
use std::cmp::Ordering;
use std::collections::{BinaryHeap, VecDeque};
use std::time::{Duration, Instant};
#[derive(Debug, PartialEq, Eq)]
struct Event<T> {
item: T,
release_at: Instant,
}
impl<T: Eq> Ord for Event<T> {
fn cmp(&self, other: &Self) -> Ordering {
other.release_at.cmp(&self.release_at) // reverse ordering for min-heap
}
}
impl<T: Eq> PartialOrd for Event<T> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
/// Current state of the debouncing buffer returned from [Get::get()]:
///
/// - `Ready(T)` when the event is ready to be delivered after the timeout
/// (moves data out of the buffer)
/// - `Wait(Duration)` indicates how much time is left until `Ready`
/// - `Empty` means the buffer is empty
#[derive(Debug, PartialEq)]
pub enum State<T> {
Ready(T),
Wait(Duration),
Empty,
}
/// Common interface for getting events out of debouncing buffers.
pub trait Get: Sized {
type Data;
/// Attemtps to get the next element out of a buffer. If an element is
/// [State::Ready] it's removed from the buffer.
fn get(&mut self) -> State<Self::Data>;
/// Returns an iterator over all [State::Ready] elements of the buffer.
/// Stops when either the next element is in [State::Wait] or the buffer
/// is [State::Empty].
fn iter(&mut self) -> BufferIter<Self> {
BufferIter(self)
}
}
/// Wraps a mutable reference to a buffer and implements an [Iterator] returning
/// elements in [State::Ready]. Commonly instantiated by [Get::iter()].
pub struct BufferIter<'a, B: Get>(&'a mut B);
impl<'a, B: Get> Iterator for BufferIter<'a, B> {
type Item = B::Data;
fn next(&mut self) -> Option<Self::Item> {
match self.0.get() {
State::Ready(data) => Some(data),
_ => None,
}
}
}
/// Debouncing buffer with a common delay for all events. Accepts events via
/// [EventBuffer::put()] which tracks the time of events and de-duplicates them
/// against the current buffer content. Subsequent call to [EventBuffer::get
/// ()] which returns the [State] of the buffer.
///
/// Implemented on top of a [VecDeque] and should be slightly more preformant
/// than [MixedEventBuffer].
pub struct EventBuffer<T> {
delay: Duration,
events: VecDeque<Event<T>>,
}
impl<T: PartialEq> EventBuffer<T> {
pub fn new(delay: Duration) -> EventBuffer<T> {
EventBuffer {
delay,
events: VecDeque::new(),
}
}
pub fn put(&mut self, item: T) {
let time = Instant::now();
self.events
.retain(|e| e.release_at <= time || e.item != item);
self.events.push_back(Event {
item,
release_at: time + self.delay,
});
}
}
impl<T> Get for EventBuffer<T> {
type Data = T;
fn get(&mut self) -> State<T> {
let time = Instant::now();
match self.events.get(0) {
None => State::Empty,
Some(e) if e.release_at > time => State::Wait(e.release_at - time),
Some(_) => State::Ready(self.events.pop_front().unwrap().item),
}
}
}
/// Debouncing buffer with per-event delays. Accepts events via
/// [MixedEventBuffer::put()] passing a `delay` as an argument. The call
/// tracks the time of events and de-duplicates them against the current buffer
/// content. Subsequent call to [MixedEventBuffer::get()] which returns the
/// [State] of the buffer.
///
/// Implemented on top of a [BinaryHeap] and should be slightly less preformant
/// than [EventBuffer].
pub struct MixedEventBuffer<T> {
events: BinaryHeap<Event<T>>,
}
impl<T: Eq> MixedEventBuffer<T> {
pub fn new() -> MixedEventBuffer<T> {
MixedEventBuffer {
events: BinaryHeap::new(),
}
}
pub fn put(&mut self, item: T, delay: Duration) {
let time = Instant::now();
self.events
.retain(|e| e.release_at <= time || e.item != item);
self.events.push(Event {
item,
release_at: time + delay,
});
}
}
impl<T: Eq> Get for MixedEventBuffer<T> {
type Data = T;
fn get(&mut self) -> State<T> {
let time = Instant::now();
match self.events.peek() {
None => State::Empty,
Some(e) if e.release_at > time => State::Wait(e.release_at - time),
Some(_) => State::Ready(self.events.pop().unwrap().item),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::thread::sleep;
use std::time::Duration;
mod event_buffer {
use super::*;
#[test]
fn wait() {
let mut debouncer = EventBuffer::new(Duration::from_millis(20));
debouncer.put(1);
assert!(matches!(debouncer.get(), State::Wait(_)));
sleep(Duration::from_millis(10));
assert!(matches!(debouncer.get(), State::Wait(_)));
sleep(Duration::from_millis(10));
assert!(matches!(debouncer.get(), State::Ready(_)));
}
#[test]
fn deduplication() {
let mut debouncer = EventBuffer::new(Duration::from_millis(20));
debouncer.put(1);
debouncer.put(2);
sleep(Duration::from_millis(10));
debouncer.put(1);
sleep(Duration::from_millis(20));
assert!(debouncer.iter().eq([2, 1]));
}
}
mod mixed_event_buffer {
use super::*;
#[test]
fn wait() {
let mut debouncer = MixedEventBuffer::new();
debouncer.put(1, Duration::from_millis(20));
assert!(matches!(debouncer.get(), State::Wait(_)));
sleep(Duration::from_millis(10));
assert!(matches!(debouncer.get(), State::Wait(_)));
sleep(Duration::from_millis(10));
assert!(matches!(debouncer.get(), State::Ready(_)));
}
#[test]
fn deduplication() {
let mut debouncer = MixedEventBuffer::new();
debouncer.put(1, Duration::from_millis(20));
debouncer.put(2, Duration::from_millis(30));
sleep(Duration::from_millis(10));
debouncer.put(1, Duration::from_millis(10));
sleep(Duration::from_millis(20));
assert!(debouncer.iter().eq([1, 2]));
}
#[test]
fn event_order() {
let mut debouncer = MixedEventBuffer::new();
debouncer.put(2, Duration::from_millis(20));
debouncer.put(1, Duration::from_millis(10));
sleep(Duration::from_millis(30));
assert!(debouncer.iter().eq([1, 2]));
}
}
}