Struct sized_chunks::ring_buffer::RingBuffer

pub struct RingBuffer<A, N = U64> where
    N: ChunkLength<A>,  { /* fields omitted */ }

A fixed capacity ring buffer.

A ring buffer is an array where the first logical index is at some arbitrary location inside the array, and the indices wrap around to the start of the array once they overflow its bounds.

This gives us the ability to push to either the front or the end of the array in constant time, at the cost of losing the ability to get a single contiguous slice reference to the contents.

It differs from the Chunk in that the latter will have mostly constant time pushes, but may occasionally need to shift its contents around to make room. They both have constant time pop, and they both have linear time insert and remove.

The RingBuffer offers its own Slice and SliceMut types to compensate for the loss of being able to take a slice, but they’re somewhat less efficient, so the general rule should be that you shouldn’t choose a RingBuffer if you rely heavily on slices - but if you don’t, it’s probably a marginally better choice overall than Chunk.

Feature Flag

To use this data structure, you need to enable the ringbuffer feature.

Implementations

impl<A, N> RingBuffer<A, N> where
    N: ChunkLength<A>, 

pub const CAPACITY: usize

The capacity of this ring buffer, as a usize.

#[must_use]pub fn new() -> Self

Construct an empty ring buffer.

#[must_use]pub fn unit(value: A) -> Self

Construct a ring buffer with a single item.

#[must_use]pub fn pair(value1: A, value2: A) -> Self

Construct a ring buffer with two items.

#[must_use]pub fn drain_from(other: &mut Self) -> Self

Construct a new ring buffer and move every item from other into the new buffer.

Time: O(n)

#[must_use]pub fn collect_from<I>(iter: &mut I, count: usize) -> Self where
    I: Iterator<Item = A>, 

Construct a new ring buffer and populate it by taking count items from the iterator iter.

Panics if the iterator contains less than count items.

Time: O(n)

#[must_use]pub fn from_front(other: &mut Self, count: usize) -> Self

Construct a new ring buffer and populate it by taking count items from the front of other.

Time: O(n) for the number of items moved

#[must_use]pub fn from_back(other: &mut Self, count: usize) -> Self

Construct a new ring buffer and populate it by taking count items from the back of other.

Time: O(n) for the number of items moved

#[must_use]pub fn is_full(&self) -> bool

Test if the ring buffer is full.

#[must_use]pub fn iter(&self) -> Iter<'_, A, N>

Get an iterator over references to the items in the ring buffer in order.

#[must_use]pub fn iter_mut(&mut self) -> IterMut<'_, A, N>

Get an iterator over mutable references to the items in the ring buffer in order.

#[must_use]pub fn slice<R: RangeBounds<usize>>(&self, range: R) -> Slice<'_, A, N>

Get a Slice for a subset of the ring buffer.

#[must_use]pub fn slice_mut<R: RangeBounds<usize>>(
    &mut self,
    range: R
) -> SliceMut<'_, A, N>

Get a SliceMut for a subset of the ring buffer.

#[must_use]pub unsafe fn get_unchecked(&self, index: usize) -> &A

Get an unchecked reference to the value at the given index.

Safety

You must ensure the index is not out of bounds.

#[must_use]pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut A

Get an unchecked mutable reference to the value at the given index.

Safety

You must ensure the index is not out of bounds.

pub fn push_back(&mut self, value: A)

Push a value to the back of the buffer.

Panics if the capacity of the buffer is exceeded.

Time: O(1)

pub fn push_front(&mut self, value: A)

Push a value to the front of the buffer.

Panics if the capacity of the buffer is exceeded.

Time: O(1)

pub fn pop_back(&mut self) -> Option<A>

Pop a value from the back of the buffer.

Returns None if the buffer is empty.

Time: O(1)

pub fn pop_front(&mut self) -> Option<A>

Pop a value from the front of the buffer.

Returns None if the buffer is empty.

Time: O(1)

pub fn drop_left(&mut self, index: usize)

Discard all items up to but not including index.

Panics if index is out of bounds.

Time: O(n) for the number of items dropped

pub fn drop_right(&mut self, index: usize)

Discard all items from index onward.

Panics if index is out of bounds.

Time: O(n) for the number of items dropped

#[must_use]pub fn split_off(&mut self, index: usize) -> Self

Split a buffer into two, the original buffer containing everything up to index and the returned buffer containing everything from index onwards.

Panics if index is out of bounds.

Time: O(n) for the number of items in the new buffer

pub fn append(&mut self, other: &mut Self)

Remove all items from other and append them to the back of self.

Panics if the capacity of self is exceeded.

other will be an empty buffer after this operation.

Time: O(n) for the number of items moved

pub fn drain_from_front(&mut self, other: &mut Self, count: usize)

Remove count items from the front of other and append them to the back of self.

Panics if self doesn’t have count items left, or if other has fewer than count items.

Time: O(n) for the number of items moved

pub fn drain_from_back(&mut self, other: &mut Self, count: usize)

Remove count items from the back of other and append them to the front of self.

Panics if self doesn’t have count items left, or if other has fewer than count items.

Time: O(n) for the number of items moved

pub fn insert(&mut self, index: usize, value: A)

Insert a new value at index index, shifting all the following values to the right.

Panics if the index is out of bounds.

Time: O(n) for the number of items shifted

pub fn insert_ordered(&mut self, value: A) where
    A: Ord, 

Insert a new value into the buffer in sorted order.

This assumes every element of the buffer is already in sorted order. If not, the value will still be inserted but the ordering is not guaranteed.

Time: O(log n) to find the insert position, then O(n) for the number of elements shifted.

Examples

let mut chunk = Chunk::<i32, U64>::from_iter(0..5);
chunk.insert_ordered(3);
assert_eq!(&[0, 1, 2, 3, 3, 4], chunk.as_slice());

pub fn insert_from<Iterable, I>(&mut self, index: usize, iter: Iterable) where
    Iterable: IntoIterator<Item = A, IntoIter = I>,
    I: ExactSizeIterator<Item = A>, 

Insert multiple values at index index, shifting all the following values to the right.

Panics if the index is out of bounds or the chunk doesn’t have room for all the values.

Time: O(m+n) where m is the number of elements inserted and n is the number of elements following the insertion index. Calling insert repeatedly would be O(m*n).

pub fn remove(&mut self, index: usize) -> A

Remove the value at index index, shifting all the following values to the left.

Returns the removed value.

Panics if the index is out of bounds.

Time: O(n) for the number of items shifted

pub fn drain(&mut self) -> Drain<'_, A, N>

Construct an iterator that drains values from the front of the buffer.

pub fn clear(&mut self)

Discard the contents of the buffer.

Time: O(n)

Trait Implementations

impl<'a, A, N> Arbitrary<'a> for RingBuffer<A, N> where
    A: Arbitrary<'a>,
    N: ChunkLength<A> + 'static, 

fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self>

Generate an arbitrary value of Self from the given unstructured data.

fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self>

Generate an arbitrary value of Self from the entirety of the given unstructured data.

fn size_hint(depth: usize) -> (usize, Option<usize>)

Get a size hint for how many bytes out of an Unstructured this type needs to construct itself.

impl<A, N> Array for RingBuffer<A, N> where
    N: ChunkLength<A>, 

#[must_use]fn get(&self, index: usize) -> Option<&A>

Get a reference to the value at a given index.

pub fn first(&self) -> Option<&Self::Output>

Get a reference to the first element in the array.

pub fn last(&self) -> Option<&Self::Output>

Get a reference to the last element in the array.

pub fn contains(&self, target: &Self::Output) -> bool where
    Self::Output: PartialEq<Self::Output>, 

Return true if an element equivalent to target exists in the array.

pub fn binary_search(&self, target: &Self::Output) -> Result<usize, usize> where
    Self::Output: Ord, 

Perform a binary search for target.

pub fn binary_search_by<F>(&self, compare: F) -> Result<usize, usize> where
    F: FnMut(&Self::Output) -> Ordering, 

Perform a binary search using a comparator function.

pub fn binary_search_by_key<K, F>(
    &self,
    key: &K,
    extract: F
) -> Result<usize, usize> where
    K: Ord,
    F: FnMut(&Self::Output) -> K, 

Perform a binary search using a key and a key extractor function.

pub fn is_sorted(&self) -> bool where
    Self::Output: PartialOrd<Self::Output>, 

Test whether the array is sorted.

pub fn is_sorted_by<F>(&self, compare: F) -> bool where
    F: FnMut(&Self::Output, &Self::Output) -> Option<Ordering>, 

Test whether the array is sorted using a comparator function.

pub fn is_sorted_by_key<K, F>(&self, extract: F) -> bool where
    K: PartialOrd<K>,
    F: FnMut(&Self::Output) -> K, 

Test whether the array is sorted using a key extractor function.

pub fn starts_with(&self, slice: &[Self::Output]) -> bool where
    Self::Output: PartialEq<Self::Output>,
    Self::Output: Sized, 

Test whether the array starts with the elements in slice.

pub fn ends_with(&self, slice: &[Self::Output]) -> bool where
    Self::Output: PartialEq<Self::Output>,
    Self::Output: Sized, 

Test whether the array ends with the elements in slice.

impl<A, N> ArrayMut for RingBuffer<A, N> where
    N: ChunkLength<A>, 

#[must_use]fn get_mut(&mut self, index: usize) -> Option<&mut A>

Get a mutable reference to the value at a given index.

pub fn first_mut(&mut self) -> Option<&mut Self::Output>

Get a mutable reference to the first element in the array.

pub fn last_mut(&mut self) -> Option<&mut Self::Output>

Get a mutable reference to the last element in the array.

pub fn set(&mut self, index: usize, value: Self::Output) -> Option<Self::Output> where
    Self::Output: Sized, 

Set the value of the element at the given index.

pub fn swap(&mut self, index1: usize, index2: usize) where
    Self::Output: Sized, 

Swap the elements at two indexes.

pub fn map_pair<F, A>(&mut self, index1: usize, index2: usize, f: F) -> A where
    F: FnMut(&mut Self::Output, &mut Self::Output) -> A, 

Get mutable references to the elements at two indexes and call a function on them.

pub fn sort_unstable(&mut self) where
    Self::Output: Ord,
    Self::Output: Sized, 

Sort the elements of the array.

pub fn sort_unstable_by<F>(&mut self, compare: F) where
    F: FnMut(&Self::Output, &Self::Output) -> Ordering,
    Self::Output: Sized, 

Sort the elements of the array using a comparator function.

pub fn sort_unstable_by_key<F, K>(&mut self, extract: F) where
    K: Ord,
    F: FnMut(&Self::Output) -> K,
    Self::Output: Sized, 

Sort the elements of the array using a key extractor function.

impl<A: Clone, N: ChunkLength<A>> Clone for RingBuffer<A, N>

fn clone(&self) -> Self

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<A: Debug, N: ChunkLength<A>> Debug for RingBuffer<A, N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<A, N: ChunkLength<A>> Default for RingBuffer<A, N>

#[must_use]fn default() -> Self

Returns the “default value” for a type.

impl<A, N: ChunkLength<A>> Drop for RingBuffer<A, N>

fn drop(&mut self)

Executes the destructor for this type.

impl<A: Eq, N: ChunkLength<A>> Eq for RingBuffer<A, N>

impl<'a, A: Clone + 'a, N: ChunkLength<A>> Extend<&'a A> for RingBuffer<A, N>

fn extend<I: IntoIterator<Item = &'a A>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<A, N: ChunkLength<A>> Extend<A> for RingBuffer<A, N>

fn extend<I: IntoIterator<Item = A>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, A: 'a, N: ChunkLength<A> + 'a> From<&'a RingBuffer<A, N>> for Slice<'a, A, N>

#[must_use]fn from(buffer: &'a RingBuffer<A, N>) -> Self

Performs the conversion.

impl<'a, A: 'a, N: ChunkLength<A> + 'a> From<&'a mut RingBuffer<A, N>> for SliceMut<'a, A, N>

#[must_use]fn from(buffer: &'a mut RingBuffer<A, N>) -> Self

Performs the conversion.

impl<A, N: ChunkLength<A>> FromIterator<A> for RingBuffer<A, N>

#[must_use]fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self

Creates a value from an iterator.

impl<A, N> HasLength for RingBuffer<A, N> where
    N: ChunkLength<A>, 

#[must_use]fn len(&self) -> usize

Get the length of the ring buffer.

pub fn is_empty(&self) -> bool

Return whether the data structure is empty.

impl<A: Hash, N: ChunkLength<A>> Hash for RingBuffer<A, N>

fn hash<H: Hasher>(&self, hasher: &mut H)

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<A, N> Index<usize> for RingBuffer<A, N> where
    N: ChunkLength<A>, 

type Output = A

The returned type after indexing.

#[must_use]fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<A, N> IndexMut<usize> for RingBuffer<A, N> where
    N: ChunkLength<A>, 

#[must_use]fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<A, N: ChunkLength<A>> IntoIterator for RingBuffer<A, N>

type Item = A

The type of the elements being iterated over.

type IntoIter = OwnedIter<A, N>

Which kind of iterator are we turning this into?

#[must_use]fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, A, N: ChunkLength<A>> IntoIterator for &'a RingBuffer<A, N>

type Item = &'a A

The type of the elements being iterated over.

type IntoIter = Iter<'a, A, N>

Which kind of iterator are we turning this into?

#[must_use]fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, A, N: ChunkLength<A>> IntoIterator for &'a mut RingBuffer<A, N>

type Item = &'a mut A

The type of the elements being iterated over.

type IntoIter = IterMut<'a, A, N>

Which kind of iterator are we turning this into?

#[must_use]fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A: Ord, N: ChunkLength<A>> Ord for RingBuffer<A, N>

#[must_use]fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

#[must_use]pub fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]pub fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]pub fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

impl<A, N, PrimSlice> PartialEq<PrimSlice> for RingBuffer<A, N> where
    PrimSlice: Borrow<[A]>,
    A: PartialEq,
    N: ChunkLength<A>, 

#[must_use]fn eq(&self, other: &PrimSlice) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<'a, A: PartialEq + 'a, N: ChunkLength<A> + 'a> PartialEq<RingBuffer<A, N>> for Slice<'a, A, N>

#[must_use]fn eq(&self, other: &RingBuffer<A, N>) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<'a, A: PartialEq + 'a, N: ChunkLength<A> + 'a> PartialEq<RingBuffer<A, N>> for SliceMut<'a, A, N>

#[must_use]fn eq(&self, other: &RingBuffer<A, N>) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<A: PartialEq, N: ChunkLength<A>> PartialEq<RingBuffer<A, N>> for RingBuffer<A, N>

#[must_use]fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<A, N> PartialEq<Slice<'_, A, N>> for RingBuffer<A, N> where
    A: PartialEq,
    N: ChunkLength<A>, 

fn eq(&self, other: &Slice<'_, A, N>) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<A, N> PartialEq<SliceMut<'_, A, N>> for RingBuffer<A, N> where
    A: PartialEq,
    N: ChunkLength<A>, 

fn eq(&self, other: &SliceMut<'_, A, N>) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<A: PartialOrd, N: ChunkLength<A>> PartialOrd<RingBuffer<A, N>> for RingBuffer<A, N>

#[must_use]fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use]pub fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use]pub fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use]pub fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]pub fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<A, N> PoolClone for RingBuffer<A, N> where
    A: Clone,
    N: ChunkLength<A>, 

unsafe fn clone_uninit(&self, target: &mut MaybeUninit<Self>)

Clone an instance of Self into an uninitialised instance of Self.

impl<A, N> PoolDefault for RingBuffer<A, N> where
    N: ChunkLength<A>, 

unsafe fn default_uninit(target: &mut MaybeUninit<Self>)

Initialise an instance of Self to its default state.

impl<N: ChunkLength<u8>> Read for RingBuffer<u8, N>

fn read(&mut self, buf: &mut [u8]) -> Result<usize>

Pull some bytes from this source into the specified buffer, returning how many bytes were read.

pub fn read_vectored(
    &mut self,
    bufs: &mut [IoSliceMut<'_>]
) -> Result<usize, Error>

Like read, except that it reads into a slice of buffers.

pub fn is_read_vectored(&self) -> bool

🔬 This is a nightly-only experimental API. (can_vector)

Determines if this Reader has an efficient read_vectored implementation.

pub unsafe fn initializer(&self) -> Initializer

🔬 This is a nightly-only experimental API. (read_initializer)

Determines if this Reader can work with buffers of uninitialized memory.

pub fn read_to_end(&mut self, buf: &mut Vec<u8, Global>) -> Result<usize, Error>

Read all bytes until EOF in this source, placing them into buf.

pub fn read_to_string(&mut self, buf: &mut String) -> Result<usize, Error>

Read all bytes until EOF in this source, appending them to buf.

pub fn read_exact(&mut self, buf: &mut [u8]) -> Result<(), Error>

Read the exact number of bytes required to fill buf.

pub fn by_ref(&mut self) -> &mut Self

Creates a “by reference” adaptor for this instance of Read.

pub fn bytes(self) -> Bytes<Self>

Transforms this Read instance to an Iterator over its bytes.

pub fn chain<R>(self, next: R) -> Chain<Self, R> where
    R: Read, 

Creates an adaptor which will chain this stream with another.

pub fn take(self, limit: u64) -> Take<Self>

Creates an adaptor which will read at most limit bytes from it.

impl<N: ChunkLength<u8>> Write for RingBuffer<u8, N>

fn write(&mut self, buf: &[u8]) -> Result<usize>

Write a buffer into this writer, returning how many bytes were written.

fn flush(&mut self) -> Result<()>

Flush this output stream, ensuring that all intermediately buffered contents reach their destination.

pub fn write_vectored(&mut self, bufs: &[IoSlice<'_>]) -> Result<usize, Error>

Like write, except that it writes from a slice of buffers.

pub fn is_write_vectored(&self) -> bool

🔬 This is a nightly-only experimental API. (can_vector)

Determines if this Writer has an efficient write_vectored implementation.

pub fn write_all(&mut self, buf: &[u8]) -> Result<(), Error>

Attempts to write an entire buffer into this writer.

pub fn write_all_vectored(
    &mut self,
    bufs: &mut [IoSlice<'_>]
) -> Result<(), Error>

🔬 This is a nightly-only experimental API. (write_all_vectored)

Attempts to write multiple buffers into this writer.

pub fn write_fmt(&mut self, fmt: Arguments<'_>) -> Result<(), Error>

Writes a formatted string into this writer, returning any error encountered.

pub fn by_ref(&mut self) -> &mut Self

Creates a “by reference” adaptor for this instance of Write.