aboutsummaryrefslogtreecommitdiff
path: root/src/lib.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib.rs')
-rw-r--r--src/lib.rs435
1 files changed, 435 insertions, 0 deletions
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..142d30f
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,435 @@
+#![warn(missing_docs)]
+//!Ring buffer that uses a boxed array as backing storage. This guarantees that the buffers size is
+//!always exactly at the compile-time constant value. There is no way to get fewer or more entries.
+//!In addition, by having the array boxed, conversion from [`Vec`][std::vec::Vec] and to
+//![`VecDeque`][std::collections::VecDeque] are nearly free.
+//!
+//!This crate does not use any unsafe code (however the IntoIterator implementation does so
+//!indirectly, as it internally uses a [`VecDeque`][std::collections::VecDeque]).
+//!
+//!Since the ring buffer has always a guaranteed number of elements, it must be initialized, either
+//!from an iterator, a boxed slice (most collections can convert into a boxed slice at very low
+//!cost), a [`Vec`], or at a value that implements [`Copy`][std::marker::Copy].
+
+use std::ops::{Index, IndexMut};
+use std::iter::Iterator;
+///Ring buffer using a boxed array as backing storage. This has the adantage that conversions
+///from [`Vec`][std::vec::Vec] or to [`VecDeque`][std::collections::VecDeque] are nearly free.
+///Main use case of this is as a replacement for `std::collection::VecDeque` in cases where the
+///size is fixed at compile time and one really wants to make invalid states impossible.
+///
+///Due to this, the only way to put a new item into the buffer is to take an old item out.
+///There is intentionally no way to temporary ownership of items. If you need such an API, you can
+///use the [`get_mut()`][crate::RingBuffer::get_mut] method or the index operator to obtain a
+///mutable reference, and then use either methods from [`std::mem`] to temporarily place another
+///value there, or use internally unsafe solutions like the [`replace_with`](https://docs.rs/replace_with)
+///crate.
+///
+///# Examples
+///Whenever you [`push_pop()`][RingBuffer::push_pop], the buffer moves to the next element. You can get a reference to
+///contained data using the index operator, or if you want a panic-free way, using the
+///[`get()`][RingBuffer::get()] or [`get_mut()`][RingBuffer::get_mut()] methods.
+///```
+/// # use boxed_array_ringbuffer::RingBuffer;
+///let input = [42,37,23,12];
+///let buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).expect("Works, enough input.");
+///assert_eq!(buf[0], &42);
+///assert_eq!(buf[1], &37);
+///assert_eq!(buf[2], &23);
+///assert_eq!(buf[3], &12);
+///assert_eq!(buf.get(3), Some(&&12));
+///assert_eq!(buf.get(4), None);
+///let (buf, forty_two) = buf.push_pop(&1);
+///assert_eq!(forty_two, &42);
+///assert_eq!(buf[0], &37);
+///assert_eq!(buf[1], &23);
+///assert_eq!(buf[2], &12);
+///assert_eq!(buf[3], &1);
+///let (buf, thirty_seven) = buf.push_pop(&2);
+///assert_eq!(thirty_seven, &37);
+///let (buf, twenty_three) = buf.push_pop(&3);
+///assert_eq!(twenty_three, &23);
+///let (buf, twelve) = buf.push_pop(&4);
+///assert_eq!(twelve, &12);
+///let (buf, one) = buf.push_pop(&5);
+///assert_eq!(one, &1);
+///assert_eq!(buf[0], &2);
+///assert_eq!(buf[1], &3);
+///assert_eq!(buf[2], &4);
+///assert_eq!(buf[3], &5);
+///```
+#[derive(Debug)]
+pub struct RingBuffer<T, const SIZE : usize>
+{
+ //storage is an array, because arrays _guarantee_ an initialized fixed size.
+ //It's inside a box, because that way we can collect() into it without copying from heap to
+ //stack.
+ storage : Box<[T;SIZE]>,
+ index : usize,
+}
+
+impl<T, const SIZE : usize> RingBuffer<T, SIZE>
+{
+ ///Puts `new_entry` into the ring buffer at its current location, and returns the value that
+ ///was there before. Then moves the ring buffer to the next location.
+ ///
+ ///# Examples
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12];
+ ///let buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).expect("Works, enough input.");
+ ///assert_eq!(buf[0], &42);
+ ///assert_eq!(buf[3], &12);
+ ///let (buf, forty_two) = buf.push_pop(&1);
+ ///assert_eq!(forty_two, &42);
+ ///assert_eq!(buf[0], &37);
+ ///assert_eq!(buf[3], &1);
+ ///```
+ pub fn push_pop(mut self,new_entry : T) -> (Self, T) {
+ let old_value = std::mem::replace(&mut self.storage[self.index], new_entry);
+ self.index = (self.index + 1) % SIZE;
+ (self, old_value)
+ }
+
+ ///Creates a new RingBuffer from an [`Iterator`]. If the iterator does not supply enough
+ ///elements, the elements that have already been taken from the iterator are instead returned
+ ///in the [`Err`] variant as a boxed slice.
+ ///
+ ///# Warning
+ ///Beware that it is *not* considered an error if the iterator would yield more elements. If you
+ ///need the remaining data in the iterator, make sure to pass it
+ ///[`by_ref()`][Iterator::by_ref].
+ ///
+ ///# Examples
+ ///If the iterator has at least the required number of elements, a ring buffer is created.
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12,8];
+ ///let mut iter = input.iter();
+ ///let buf : RingBuffer<&usize, 4> = RingBuffer::new(iter.by_ref()).expect("Works, enough input.");
+ ///assert_eq!(iter.next(), Some(&8));
+ ///assert_eq!(buf[0], &42);
+ ///assert_eq!(buf[1], &37);
+ ///assert_eq!(buf[2], &23);
+ ///assert_eq!(buf[3], &12);
+ ///assert_eq!(buf.get(4),None);
+ ///```
+ ///
+ ///If the iterator does not yield enough elements, an error is returned, containing all
+ ///elements taken from the iterator.
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = ["lizard", "fish", "bird"];
+ ///let buf : Result<RingBuffer<&str, 4>, _> = RingBuffer::new(input.iter().map(|x| *x));
+ ///assert!(buf.is_err());
+ ///assert_eq!(buf.unwrap_err()[1], "fish");
+ ///```
+ pub fn new<I>(input : I) -> Result<Self, Box<[T]>>
+ where I : Iterator<Item=T>
+ {
+ let slice = input.take(SIZE).collect::<Box<[T]>>();
+ let array = slice.try_into()?;
+ Ok(RingBuffer { storage : array, index : 0 })
+ }
+
+ ///Initializes the ring buffer with copies of the same value.
+ ///
+ ///# Examples
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let buf :RingBuffer<usize,4> = RingBuffer::new_copy(3);
+ ///assert_eq!(buf[0], 3);
+ ///assert_eq!(buf[1], 3);
+ ///assert_eq!(buf[2], 3);
+ ///assert_eq!(buf[3], 3);
+ ///assert_eq!(buf.get(4), None);
+ ///```
+ pub fn new_copy(init : T) -> Self
+ where T : Copy
+ {
+ RingBuffer { storage : Box::new([init;SIZE]), index : 0 }
+ }
+
+ ///Gets an immutable reference to the entry that's `index` elements in the future of the
+ ///buffer. In other words `get(0)` returns an immutable reference to the next element that
+ ///would be returned by [`push_pop()`][RingBuffer::push_pop], `get(1)` to the second-next and
+ ///so on. Return value is wrapped in an option due to range checking. You can use the index
+ ///operator `[]` instead if you are sure your index is valid.
+ ///
+ ///# Examples
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12];
+ ///let buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).expect("Works, enough input.");
+ ///let (buf, _) = buf.push_pop(&7);
+ ///assert_eq!(buf.get(0), Some(&&37));
+ ///assert_eq!(buf.get(3), Some(&&7));
+ ///assert_eq!(buf.get(4), None);
+ ///```
+ pub fn get(&self, index : usize) -> Option<&T> {
+ if index >= SIZE {
+ None
+ }
+ else {
+ Some(&self.storage[self.get_arr_index_wrapped(index)])
+ }
+ }
+
+ ///Similar to [`get()`][RingBuffer::get], but yields a mutable reference instead.
+ ///
+ ///# Examples
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12];
+ ///let mut buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).expect("Works, enough input.");
+ ///match buf.get_mut(0) {
+ /// Some(x) => {
+ /// assert_eq!(**x, 42);
+ /// *x = &1;
+ /// }
+ /// _ => {
+ /// unreachable!();
+ /// }
+ ///}
+ ///assert_eq!(buf.get(0), Some(&&1));
+ ///```
+ pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
+ if index >= SIZE {
+ None
+ }
+ else {
+ Some(&mut self.storage[self.get_arr_index_wrapped(index)])
+ }
+ }
+
+ ///Returns an [`Iterator`] over references to the contained elements.
+ ///
+ ///# Examples
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12];
+ ///let buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).expect("Works, enough input");
+ ///let (buf, forty_two) = buf.push_pop(&1);
+ ///assert_eq!(forty_two, &42);
+ ///assert!(buf.iter().map(|x| *x).eq([37,23,12,1].iter()));
+ ///```
+ pub fn iter(&self) -> RingBufferIterator<T,SIZE> {
+ RingBufferIterator { ring_buffer : self, index : 0 }
+ }
+
+ fn get_arr_index_wrapped(&self, index : usize) -> usize {
+ (self.index + index) % SIZE
+ }
+}
+
+impl<T, const SIZE : usize> std::convert::TryFrom<Box<[T]>> for RingBuffer<T, SIZE> {
+ type Error = Box<[T]>;
+ ///Conversion from a boxed slice. This works without a re-allocation. Returns the input as `Err`
+ ///in case the size does not match. Opposed to the [`new()`][RingBuffer::new] method that takes an
+ ///[`Iterator`] this conversion fails if the input has more elements than fit into the ring buffer.
+ ///
+ ///# Examples
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let a : Box<[_]> = vec![42,37,23,12].into();
+ ///let buf : RingBuffer<_, 4> = a.try_into().expect("Works, size matches.");
+ ///assert_eq!(buf[0], 42);
+ ///assert_eq!(buf[1], 37);
+ ///assert_eq!(buf[2], 23);
+ ///assert_eq!(buf[3], 12);
+ ///assert_eq!(buf.get(4),None);
+ ///
+ ///let b : Box<[_]> = vec![42,37,23,12].into();
+ ///let b_cpy = b.clone();
+ ///let buf2 : Result<RingBuffer<_,3>,_> = b.try_into();
+ ///assert_eq!(buf2.unwrap_err(), b_cpy);
+ ///```
+ fn try_from(slice: Box<[T]>) -> Result<Self, Self::Error> {
+ let array = slice.try_into()?;
+ Ok(RingBuffer { storage : array, index : 0 })
+ }
+}
+
+impl<T, const SIZE : usize> std::convert::TryFrom<Vec<T>> for RingBuffer<T, SIZE> {
+ type Error = Vec<T>;
+ ///Conversion from a [`Vec`]. This works without re-allocation. Returns the input as `Err` in case
+ ///the size does not match. Opposed to the [`new()`][RingBuffer::new] method that takes an
+ ///[`Iterator`] this conversion fails if the input has more elements than fit into the ring buffer.
+ ///
+ ///# Examples
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let a = vec![42,37,23,12];
+ ///let buf : RingBuffer<_, 4> = a.try_into().expect("Works, size matches.");
+ ///assert_eq!(buf[0], 42);
+ ///assert_eq!(buf[1], 37);
+ ///assert_eq!(buf[2], 23);
+ ///assert_eq!(buf[3], 12);
+ ///assert_eq!(buf.get(4),None);
+ ///
+ ///let b = vec![42,37,23,12];
+ ///let b_cpy = b.clone();
+ ///let buf2 : Result<RingBuffer<_,3>,_> = b.try_into();
+ ///assert_eq!(buf2.unwrap_err(), b_cpy);
+ ///```
+ fn try_from(vector : Vec<T>) -> Result<Self, Self::Error> {
+ let slice : Box<[T]> = vector.into();
+ match slice.try_into() {
+ Ok(array) => { Ok(RingBuffer{ storage : array, index : 0 }) }
+ Err(slice) => { Err(slice.into()) }
+ }
+ }
+}
+
+impl<T, const SIZE : usize> std::convert::From<RingBuffer<T, SIZE>> for std::collections::VecDeque<T> {
+ ///Conversion from a [`RingBuffer<T, const SIZE :usize>`][crate::RingBuffer] into a
+ ///[`VecDeque<T>`][std::collections::VecDeque]. This works without re-allocations and cannot fail.
+ ///
+ ///# Examples
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///use std::collections::VecDeque;
+ ///let a = vec![42,37,23,12];
+ ///let buf : RingBuffer<_, 4> = a.try_into().expect("Works, size matches.");
+ ///let (buf, _) = buf.push_pop(5);
+ ///let deque : VecDeque<_> = buf.into();
+ ///assert_eq!(deque[0], 37);
+ ///assert_eq!(deque[3], 5);
+ ///```
+ fn from(buffer : RingBuffer<T, SIZE>) -> std::collections::VecDeque<T> {
+ let slice = buffer.storage as Box<[T]>;
+ let vec : Vec<T> = slice.into();
+ let mut deque : std::collections::VecDeque<T> = vec.into();
+ deque.rotate_left(buffer.index);
+ deque
+ }
+}
+
+impl<T, const SIZE : usize> Index<usize> for RingBuffer<T, SIZE> {
+ type Output = T;
+ ///Indexing operation in an immutable context. Internally uses [`get()`][RingBuffer::get].
+ ///Indices start at the value that would be replaced/returned by the next call to
+ ///[`push_pop()`][RingBuffer::push_pop].
+ ///# Examples
+ ///
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12];
+ ///let buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).unwrap();
+ ///let (buf, _) = buf.push_pop(&123);
+ ///assert_eq!(buf[0],&37);
+ ///assert_eq!(buf[3],&123);
+ ///```
+ ///
+ ///# Panics
+ ///If the index is out of range (larger than or equal to `SIZE`), this panics. Use
+ ///[`get()`][RingBuffer::get] if you want sane behaviour.
+ fn index(&self, index : usize) -> &T {
+ self.get(index).expect("Ring buffer index out of bounds")
+ }
+}
+
+impl<T, const SIZE : usize> IndexMut<usize> for RingBuffer<T, SIZE> {
+ ///Indexing operation in a mutable context. Internally uses [`get_mut()`][RingBuffer::get_mut].
+ ///Indices start at the value that would be replaced/returned by the next call to
+ ///[`push_pop()`][RingBuffer::push_pop].
+ ///# Examples
+ ///
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12];
+ ///let mut buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).unwrap();
+ ///buf[1] = &0;
+ ///assert_eq!(buf[1], &0);
+ ///let (buf, forty_two) = buf.push_pop(&3);
+ ///assert_eq!(forty_two, &42);
+ ///let (buf, zero) = buf.push_pop(&4);
+ ///assert_eq!(zero, &0);
+ ///```
+ ///
+ ///# Panics
+ ///If the index is out of range (larger than or equal to `SIZE`), this panics. Use
+ ///[`get_mut()`][RingBuffer::get_mut] if you want sane behaviour.
+fn index_mut(&mut self, index :usize) -> &mut T {
+ self.get_mut(index).expect("Ring buffer index out of bounds")
+ }
+}
+
+///[`Iterator`] type returned by [`RingBuffer::iter()`]. Holds a reference to the ring buffer. See
+///[`RingBuffer::iter()`] for an example.
+pub struct RingBufferIterator<'a, T, const SIZE :usize> {
+ ring_buffer : &'a RingBuffer<T, SIZE>,
+ index : usize,
+}
+
+impl<'b, T, const SIZE : usize> Iterator for RingBufferIterator<'b, T, SIZE> {
+ type Item = &'b T;
+ fn next(&mut self) -> Option<&'b T> {
+ let result = self.ring_buffer.get(self.index);
+ if result.is_some() {
+ self.index += 1;
+ }
+ result
+ }
+}
+
+impl<T, const SIZE : usize> IntoIterator for RingBuffer<T, SIZE> {
+ type Item = T;
+ type IntoIter = std::collections::vec_deque::IntoIter<T>;
+
+ ///Consumes the ring buffer into an [`Iterator`]. This conversion works without reallocation.
+ ///
+ ///# Example
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12];
+ ///let buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).unwrap();
+ ///let (buf, forty_two) = buf.push_pop(&1);
+ ///assert_eq!(forty_two, &42);
+ ///assert!(buf.into_iter().eq([37,23,12,1].iter()));
+ ///```
+ fn into_iter(self) -> Self::IntoIter {
+ let deque : std::collections::VecDeque<_> = self.into();
+ deque.into_iter()
+ }
+}
+
+impl<'b, T, const SIZE : usize> IntoIterator for &'b RingBuffer<T, SIZE> {
+ type Item = &'b T;
+ type IntoIter = RingBufferIterator<'b, T, SIZE>;
+
+ ///Wrapper around the [`RingBuffer::iter()`] to enable for-loop compatibility for
+ ///`&RingBuffer`.
+ ///
+ ///# Example
+ ///```
+ /// # use boxed_array_ringbuffer::RingBuffer;
+ ///let input = [42,37,23,12];
+ ///let buf : RingBuffer<&usize, 4> = RingBuffer::new(input.iter()).unwrap();
+ ///let (buf, forty_two) = buf.push_pop(&1);
+ ///assert_eq!(forty_two, &42);
+ ///let reference = &buf;
+ ///assert!(reference.into_iter().map(|x| *x).eq([37,23,12,1].iter()));
+ ///```
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter()
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ #[test]
+ fn test_from_box_slice_too_large() {
+ let c : Box<[_]> = vec![42,37,23,12].into();
+ let buf3 : Result<RingBuffer<_,5>,_> = c.try_into();
+ assert!(buf3.is_err());
+ }
+
+ #[test]
+ fn test_from_vec_too_large() {
+ let c = vec![42,37,23,12];
+ let buf3 : Result<RingBuffer<_,5>,_> = c.try_into();
+ assert!(buf3.is_err());
+ }
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-05-06 12:11:30 +0000