use std::{
collections::{
vec_deque::{Drain, Iter, IterMut},
VecDeque,
},
num::NonZeroUsize,
ops::RangeBounds,
};
use serde::{Deserialize, Serialize};
#[derive(Clone, Debug, PartialEq, Deserialize, Serialize)]
#[serde(transparent)]
pub struct RingBuffer<T> {
inner: VecDeque<T>,
}
impl<T> RingBuffer<T> {
pub fn new(size: NonZeroUsize) -> Self {
Self { inner: VecDeque::with_capacity(size.into()) }
}
pub fn len(&self) -> usize {
self.inner.len()
}
pub fn is_empty(&self) -> bool {
self.inner.is_empty()
}
pub fn get(&self, index: usize) -> Option<&T> {
self.inner.get(index)
}
pub fn push(&mut self, value: T) {
if self.inner.len() == self.inner.capacity() {
self.inner.pop_front();
}
self.inner.push_back(value);
}
pub fn pop(&mut self) -> Option<T> {
self.inner.pop_front()
}
pub fn remove(&mut self, index: usize) -> Option<T> {
self.inner.remove(index)
}
pub fn iter(&self) -> Iter<'_, T> {
self.inner.iter()
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
self.inner.iter_mut()
}
pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
where
R: RangeBounds<usize>,
{
self.inner.drain(range)
}
pub fn clear(&mut self) {
self.inner.clear();
}
pub fn capacity(&self) -> usize {
self.inner.capacity()
}
pub fn retain<F>(&mut self, predicate: F)
where
F: FnMut(&T) -> bool,
{
self.inner.retain(predicate)
}
}
impl<U> Extend<U> for RingBuffer<U> {
fn extend<T: IntoIterator<Item = U>>(&mut self, iter: T) {
for item in iter.into_iter() {
self.push(item);
}
}
}
#[cfg(test)]
mod tests {
use std::{num::NonZeroUsize, ops::Not};
use super::RingBuffer;
#[test]
pub fn test_fixed_size() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
assert!(ring_buffer.is_empty());
ring_buffer.push(1);
ring_buffer.push(2);
ring_buffer.push(3);
assert!(ring_buffer.is_empty().not());
assert_eq!(ring_buffer.get(0), Some(&1));
assert_eq!(ring_buffer.get(1), Some(&2));
assert_eq!(ring_buffer.get(2), Some(&3));
ring_buffer.push(4);
ring_buffer.push(5);
assert_eq!(ring_buffer.get(0), Some(&1));
assert_eq!(ring_buffer.get(1), Some(&2));
assert_eq!(ring_buffer.get(2), Some(&3));
assert_eq!(ring_buffer.get(3), Some(&4));
assert_eq!(ring_buffer.get(4), Some(&5));
ring_buffer.push(6);
assert_eq!(ring_buffer.get(0), Some(&2));
assert_eq!(ring_buffer.get(1), Some(&3));
assert_eq!(ring_buffer.get(2), Some(&4));
assert_eq!(ring_buffer.get(3), Some(&5));
assert_eq!(ring_buffer.get(4), Some(&6));
}
#[test]
pub fn test_push_and_pop_and_remove_and_length() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
ring_buffer.push(1);
assert_eq!(ring_buffer.len(), 1);
ring_buffer.push(2);
assert_eq!(ring_buffer.len(), 2);
ring_buffer.push(3);
assert_eq!(ring_buffer.len(), 3);
assert_eq!(ring_buffer.pop(), Some(1));
assert_eq!(ring_buffer.len(), 2);
assert_eq!(ring_buffer.get(0), Some(&2));
assert_eq!(ring_buffer.get(1), Some(&3));
assert_eq!(ring_buffer.get(2), None);
assert_eq!(ring_buffer.pop(), Some(2));
assert_eq!(ring_buffer.len(), 1);
assert_eq!(ring_buffer.get(0), Some(&3));
assert_eq!(ring_buffer.get(1), None);
assert_eq!(ring_buffer.get(2), None);
assert_eq!(ring_buffer.pop(), Some(3));
assert_eq!(ring_buffer.len(), 0);
assert_eq!(ring_buffer.get(0), None);
assert_eq!(ring_buffer.get(1), None);
assert_eq!(ring_buffer.get(2), None);
assert_eq!(ring_buffer.pop(), None);
ring_buffer.push(1);
ring_buffer.push(2);
ring_buffer.push(3);
assert_eq!(ring_buffer.len(), 3);
assert_eq!(ring_buffer.get(0), Some(&1));
assert_eq!(ring_buffer.get(1), Some(&2));
assert_eq!(ring_buffer.get(2), Some(&3));
assert_eq!(ring_buffer.remove(1), Some(2));
assert_eq!(ring_buffer.len(), 2);
assert_eq!(ring_buffer.get(0), Some(&1));
assert_eq!(ring_buffer.get(1), Some(&3));
assert_eq!(ring_buffer.get(2), None);
assert_eq!(ring_buffer.remove(0), Some(1));
assert_eq!(ring_buffer.len(), 1);
assert_eq!(ring_buffer.get(0), Some(&3));
assert_eq!(ring_buffer.get(1), None);
assert_eq!(ring_buffer.get(2), None);
assert_eq!(ring_buffer.remove(1), None);
assert_eq!(ring_buffer.remove(10), None);
}
#[test]
fn test_iter() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
ring_buffer.push(1);
ring_buffer.push(2);
ring_buffer.push(3);
let as_vec = ring_buffer.iter().copied().collect::<Vec<_>>();
assert_eq!(as_vec, [1, 2, 3]);
let first_entry = ring_buffer.iter_mut().next().unwrap();
*first_entry = 42;
let as_vec = ring_buffer.iter().copied().collect::<Vec<_>>();
assert_eq!(as_vec, [42, 2, 3]);
}
#[test]
fn test_drain() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
ring_buffer.push(1);
ring_buffer.push(2);
ring_buffer.push(3);
ring_buffer.push(4);
ring_buffer.push(5);
let drained = ring_buffer.drain(0..=2).collect::<Vec<_>>();
let left = ring_buffer.iter().map(ToOwned::to_owned).collect::<Vec<_>>();
assert_eq!(drained, &[1, 2, 3]);
assert_eq!(left, &[4, 5]);
ring_buffer.drain(..);
assert!(ring_buffer.is_empty());
}
#[test]
fn test_clear_on_empty_buffer_is_a_noop() {
let mut ring_buffer: RingBuffer<u8> = RingBuffer::new(NonZeroUsize::new(3).unwrap());
ring_buffer.clear();
assert_eq!(ring_buffer.len(), 0);
}
#[test]
fn test_clear_removes_all_items() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
ring_buffer.push(4);
ring_buffer.push(5);
ring_buffer.push(6);
ring_buffer.pop();
assert_eq!(ring_buffer.len(), 2);
ring_buffer.clear();
assert_eq!(ring_buffer.len(), 0);
assert_eq!(ring_buffer.get(0), None);
assert_eq!(ring_buffer.pop(), None);
}
#[test]
fn test_clear_does_not_affect_capacity() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
ring_buffer.push(4);
ring_buffer.push(5);
ring_buffer.push(6);
ring_buffer.pop();
assert_eq!(ring_buffer.capacity(), 3);
ring_buffer.clear();
assert_eq!(ring_buffer.capacity(), 3);
}
#[test]
fn test_capacity_is_what_we_passed_to_new() {
let ring_buffer = RingBuffer::<i32>::new(NonZeroUsize::new(13).unwrap());
assert_eq!(ring_buffer.capacity(), 13);
}
#[test]
fn test_capacity_is_not_affected_by_overflowing() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
ring_buffer.push(4);
ring_buffer.push(5);
ring_buffer.push(6);
ring_buffer.push(7);
ring_buffer.pop();
ring_buffer.push(8);
ring_buffer.push(9);
assert_eq!(ring_buffer.capacity(), 3);
ring_buffer.extend(vec![10, 11, 12, 13, 14, 15]);
assert_eq!(ring_buffer.capacity(), 3);
}
#[test]
fn test_roundtrip_serialization() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(3).unwrap());
ring_buffer.push("1".to_owned());
ring_buffer.push("2".to_owned());
let json = serde_json::to_string(&ring_buffer).expect("serialisation failed");
assert_eq!(json, r#"["1","2"]"#);
let new_ring_buffer: RingBuffer<String> =
serde_json::from_str(&json).expect("deserialisation failed");
assert_eq!(ring_buffer, new_ring_buffer);
}
#[test]
fn test_extending_an_empty_ringbuffer_adds_the_items() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
ring_buffer.extend(vec!["a".to_owned(), "b".to_owned()]);
assert_eq!(ring_buffer.iter().map(String::as_str).collect::<Vec<_>>(), vec!["a", "b"]);
}
#[test]
fn test_extend_adds_items_to_the_end() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
ring_buffer.push("1".to_owned());
ring_buffer.push("2".to_owned());
ring_buffer.extend(vec!["3".to_owned(), "4".to_owned()]);
assert_eq!(
ring_buffer.iter().map(String::as_str).collect::<Vec<_>>(),
vec!["1", "2", "3", "4"]
);
}
#[test]
fn test_extend_does_not_overflow_max_length() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(5).unwrap());
ring_buffer.push("1".to_owned());
ring_buffer.push("2".to_owned());
ring_buffer.extend(vec![
"3".to_owned(),
"4".to_owned(),
"5".to_owned(),
"6".to_owned(),
"7".to_owned(),
]);
assert_eq!(
ring_buffer.iter().map(String::as_str).collect::<Vec<_>>(),
vec!["3", "4", "5", "6", "7"]
);
}
#[test]
fn test_extending_a_full_ringbuffer_preserves_max_length() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(2).unwrap());
ring_buffer.push("1".to_owned());
ring_buffer.push("2".to_owned());
ring_buffer.extend(vec![
"3".to_owned(),
"4".to_owned(),
"5".to_owned(),
"6".to_owned(),
"7".to_owned(),
]);
assert_eq!(ring_buffer.iter().map(String::as_str).collect::<Vec<_>>(), vec!["6", "7"]);
}
#[test]
fn test_retain() {
let mut ring_buffer = RingBuffer::new(NonZeroUsize::new(2).unwrap());
ring_buffer.push(1);
ring_buffer.push(2);
ring_buffer.retain(|v| v % 2 == 0);
assert_eq!(ring_buffer.len(), 1);
assert_eq!(ring_buffer.get(0).copied().unwrap(), 2);
}
}