cap_vec 0.3.0

#![no_std]

//! A heap-backed vector with fixed maximum capacity for `no_std` environments.
//!
//! [`CapVec<T, N>`](CapVec) stores up to `N` values of type `T` contiguously in
//! a backing buffer. Unlike [`alloc::vec::Vec`], its maximum capacity is fixed
//! at compile time and never grows after construction. Its logical length can
//! still change dynamically from `0` to `N`.
//!
//! This is useful when a fixed upper bound is part of the program design, but a
//! stack-allocated `[T; N]` would be too large or too inflexible. The crate uses
//! `alloc` and is compatible with `#![no_std]` targets that provide a global
//! allocator.
//!
//! # Allocation model
//!
//! `CapVec::new` creates an empty vector without allocating. The backing buffer
//! is created on the first successful [`push`](CapVec::push),
//! [`insert`](CapVec::insert), [`extend`](CapVec::extend), or when constructing
//! from a full array. For non-zero-sized buffers this allocates heap storage for
//! exactly `N` elements; zero-sized buffers use a dangling non-null sentinel.
//! The buffer is reused by operations such as [`clear`](CapVec::clear). Use
//! [`shrink_to_fit`](CapVec::shrink_to_fit) on an empty vector to drop the
//! backing buffer.
//!
//! # Capacity
//!
//! Maximum capacity is encoded in the const generic parameter `N`. The
//! [`capacity`](CapVec::capacity) method returns the currently-created backing
//! buffer size: `0` before the buffer is created, otherwise `N`. Use
//! [`max_capacity`](CapVec::max_capacity) to get the fixed upper bound and
//! [`spare_capacity`](CapVec::spare_capacity) to get the remaining room before
//! the vector is full. Operations that would exceed the maximum capacity return
//! the provided element instead of reallocating. `CapVec<T, 0>` is valid and can
//! never hold an element.
//!
//! ```rust
//! use cap_vec::CapVec;
//!
//! let mut v = CapVec::<i32, 4>::new();
//! assert!(v.is_empty());
//!
//! v.push(10).unwrap();
//! v.push(20).unwrap();
//! v.push(30).unwrap();
//! assert_eq!(v.len(), 3);
//!
//! assert_eq!(v.first(), Some(&10));
//! assert_eq!(v.get(1), Some(&20));
//! assert_eq!(v.last(), Some(&30));
//!
//! assert_eq!(&v[..], &[10, 20, 30]);
//! assert_eq!(v.remove(1), Some(20));
//! assert_eq!(v.pop(), Some(30));
//! assert_eq!(v.pop(), Some(10));
//! ```

extern crate alloc;
#[cfg(test)]
extern crate std;

use alloc::alloc::{alloc, handle_alloc_error};
use alloc::boxed::Box;
use core::alloc::Layout;
use core::hash::Hash;
use core::iter::FusedIterator;
use core::mem::MaybeUninit;
use core::ops::{Bound, Deref, DerefMut, Range, RangeBounds};
use core::ptr::NonNull;
use core::slice::{Iter, IterMut};

/// A heap-backed vector with compile-time fixed maximum capacity.
///
/// `CapVec<T, N>` behaves like a small subset of [`alloc::vec::Vec`] with one
/// important difference: its maximum capacity is the const generic `N`, and it
/// never reallocates to grow beyond that bound.
///
/// The backing buffer is lazy for empty vectors created with [`new`](Self::new).
/// Once created, the buffer remains available until the vector is dropped.
/// Calling [`clear`](Self::clear) removes the initialized elements but keeps the
/// buffer for later reuse. Calling [`shrink_to_fit`](Self::shrink_to_fit) on an
/// empty vector drops the buffer.
///
/// The initialized prefix can be viewed as a slice through [`as_slice`](Self::as_slice),
/// [`as_mut_slice`](Self::as_mut_slice), or the [`Deref`] implementations. Slice
/// methods such as [`first`](slice::first), [`last`](slice::last), and
/// [`get`](slice::get) are therefore available directly on `CapVec`.
#[derive(Default)]
pub struct CapVec<T, const N: usize> {
    len: usize,
    buf: Option<Box<[MaybeUninit<T>; N]>>,
}

fn new_uninit_buffer<T, const N: usize>() -> Box<[MaybeUninit<T>; N]> {
    if core::mem::size_of::<[MaybeUninit<T>; N]>() == 0 {
        return unsafe { Box::from_raw(NonNull::<[MaybeUninit<T>; N]>::dangling().as_ptr()) };
    }

    let layout = Layout::new::<[MaybeUninit<T>; N]>();
    let ptr = unsafe { alloc(layout) };

    if ptr.is_null() {
        handle_alloc_error(layout);
    }

    unsafe { Box::from_raw(ptr as *mut [MaybeUninit<T>; N]) }
}

unsafe fn drop_initialized_range<T>(ptr: *mut MaybeUninit<T>, range: Range<usize>) {
    unsafe {
        core::ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut(
            ptr.add(range.start) as *mut T,
            range.len(),
        ));
    }
}

fn clone_into_uninit_buffer<T, const N: usize>(values: &[T]) -> Box<[MaybeUninit<T>; N]>
where
    T: Clone,
{
    let mut elements = new_uninit_buffer();

    struct Guard<'a, T> {
        elements: &'a mut [MaybeUninit<T>],
        initialized: usize,
    }

    impl<T> Drop for Guard<'_, T> {
        fn drop(&mut self) {
            unsafe {
                drop_initialized_range(self.elements.as_mut_ptr(), 0..self.initialized);
            }
        }
    }

    let mut guard = Guard {
        elements: elements.as_mut_slice(),
        initialized: 0,
    };

    for source in values {
        guard.elements[guard.initialized].write(source.clone());
        guard.initialized += 1;
    }

    guard.initialized = 0;
    drop(guard);

    elements
}

impl<T, const N: usize> From<[T; N]> for CapVec<T, N> {
    fn from(value: [T; N]) -> Self {
        let mut elements = new_uninit_buffer();

        elements.iter_mut().zip(value).for_each(|(dest, source)| {
            dest.write(source);
        });

        Self {
            len: N,
            buf: Some(elements),
        }
    }
}

impl<T, const N: usize> Clone for CapVec<T, N>
where
    T: Clone,
{
    fn clone(&self) -> Self {
        Self {
            len: self.len,
            buf: (!self.is_empty()).then(|| clone_into_uninit_buffer(self.as_slice())),
        }
    }
}

impl<T, const N: usize> CapVec<T, N> {
    /// Creates a new, empty `CapVec` with maximum capacity `N`.
    ///
    /// The internal buffer is not created until an element is inserted. This
    /// makes `new` cheap even when `N` is large.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<i32, 8>::new();
    /// assert_eq!(v.capacity(), 0);
    /// assert_eq!(v.max_capacity(), 8);
    /// assert_eq!(v.len(), 0);
    /// assert!(v.is_empty());
    /// ```
    pub const fn new() -> Self {
        Self { len: 0, buf: None }
    }

    /// Extends the vector with elements from an iterator until the vector is full
    /// or the iterator is exhausted.
    ///
    /// The returned iterator is the same iterator after the consumed prefix has
    /// been removed. If the vector becomes full before the source iterator is
    /// exhausted, the next call to `next` on the returned iterator yields the
    /// first uninserted element.
    ///
    /// This is an inherent method, not an implementation of [`Extend`], because
    /// it reports the unconsumed tail instead of silently discarding or panicking
    /// when the vector is full.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<u8, 3>::new();
    /// let mut leftover = v.extend([1, 2, 3, 4]);
    ///
    /// assert_eq!(v.as_slice(), &[1, 2, 3]);
    /// assert_eq!(leftover.next(), Some(4)); // one element not consumed
    /// ```
    pub fn extend<I>(&mut self, iter: I) -> I::IntoIter
    where
        I: IntoIterator<Item = T>,
    {
        let mut iter = iter.into_iter();

        if self.len >= N {
            return iter;
        }

        let ptr = self.buf.get_or_insert_with(new_uninit_buffer).as_mut_ptr();

        for _ in 0..N - self.len {
            let Some(element) = iter.next() else {
                break;
            };

            unsafe {
                ptr.add(self.len).write(MaybeUninit::new(element));
            }

            self.len += 1;
        }

        iter
    }

    /// Appends an element to the end of the vector.
    ///
    /// Returns `Ok(())` when the element was inserted. Returns `Err(element)`
    /// unchanged if the vector is already full.
    ///
    /// A successful first push creates the backing buffer when the vector was
    /// created with [`new`](Self::new).
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<i32, 2>::new();
    /// v.push(10).unwrap();
    /// v.push(20).unwrap();
    /// assert_eq!(v.push(30), Err(30)); // full
    /// ```
    pub fn push(&mut self, element: T) -> Result<(), T> {
        if self.len >= N {
            return Err(element);
        }

        let ptr = self.buf.get_or_insert_with(new_uninit_buffer).as_mut_ptr();

        unsafe {
            ptr.add(self.len).write(MaybeUninit::new(element));
        }

        self.len += 1;
        Ok(())
    }

    /// Inserts an element at `index`, shifting all following elements one slot to
    /// the right.
    ///
    /// Inserting at `len` is equivalent to [`push`](Self::push). Returns
    /// `Err(element)` if `index > len` or if the vector is already full.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<i32, 3>::new();
    /// v.extend([1, 3]);
    /// v.insert(1, 2).unwrap();
    /// assert_eq!(v.as_slice(), &[1, 2, 3]);
    /// ```
    pub fn insert(&mut self, index: usize, element: T) -> Result<(), T> {
        if index > self.len || self.len >= N {
            return Err(element);
        }

        let ptr = self.buf.get_or_insert_with(new_uninit_buffer).as_mut_ptr();

        unsafe {
            core::ptr::copy(ptr.add(index), ptr.add(index + 1), self.len - index);
            ptr.add(index).write(MaybeUninit::new(element));
        }

        self.len += 1;
        Ok(())
    }

    /// Removes the last element and returns it.
    ///
    /// Returns `None` when the vector is empty. Popping the last element does not
    /// release the backing buffer.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<u8, 4>::new();
    /// v.extend([1, 2, 3]);
    /// assert_eq!(v.pop(), Some(3));
    /// assert_eq!(v.as_slice(), &[1, 2]);
    /// ```
    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }

        debug_assert!(self.buf.is_some());
        let buf = unsafe { self.buf.as_mut().unwrap_unchecked() };

        self.len -= 1;
        let element = unsafe { buf[self.len].assume_init_read() };
        Some(element)
    }

    /// Shortens the vector, keeping the first `len` elements and dropping the
    /// rest.
    ///
    /// If `len` is greater than or equal to the current length, this has no
    /// effect. The backing buffer, if present, is retained for later insertions.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<i32, 4>::new();
    /// v.extend([1, 2, 3, 4]);
    /// v.truncate(2);
    /// assert_eq!(v.as_slice(), &[1, 2]);
    ///
    /// v.truncate(10);
    /// assert_eq!(v.as_slice(), &[1, 2]);
    /// ```
    pub fn truncate(&mut self, len: usize) {
        if len >= self.len {
            return;
        }

        let old_len = self.len;
        self.len = len;

        if let Some(buf) = self.buf.as_mut() {
            unsafe {
                drop_initialized_range(buf.as_mut_ptr(), len..old_len);
            }
        }
    }

    /// Removes and returns the element at `index`, shifting all following
    /// elements one slot to the left.
    ///
    /// Returns `None` if `index` is out of bounds. The backing buffer, if
    /// present, is retained for later insertions.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<i32, 3>::new();
    /// v.extend([10, 20, 30]);
    /// assert_eq!(v.remove(1), Some(20));
    /// assert_eq!(v.as_slice(), &[10, 30]);
    /// ```
    pub fn remove(&mut self, index: usize) -> Option<T> {
        if index >= self.len {
            return None;
        }

        debug_assert!(self.buf.is_some());
        let buf = unsafe { self.buf.as_mut().unwrap_unchecked() };
        let ptr = buf.as_mut_ptr();

        let element = unsafe { buf[index].assume_init_read() };

        self.len -= 1;

        unsafe {
            core::ptr::copy(ptr.add(index + 1), ptr.add(index), self.len - index);
        }

        Some(element)
    }

    /// Removes and returns the element at `index`, replacing it with the last
    /// element.
    ///
    /// This is equivalent to [`alloc::vec::Vec::swap_remove`] except it returns
    /// `None` instead of panicking when `index` is out of bounds, matching
    /// [`remove`](Self::remove).
    ///
    /// The backing buffer, if present, is retained for later insertions.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<i32, 4>::new();
    /// v.extend([10, 20, 30, 40]);
    /// assert_eq!(v.swap_remove(1), Some(20));
    /// assert_eq!(v.as_slice(), &[10, 40, 30]);
    /// assert_eq!(v.swap_remove(3), None);
    /// ```
    pub fn swap_remove(&mut self, index: usize) -> Option<T> {
        if index >= self.len {
            return None;
        }

        debug_assert!(self.buf.is_some());
        let buf = unsafe { self.buf.as_mut().unwrap_unchecked() };

        self.len -= 1;
        let element = unsafe { buf[index].assume_init_read() };

        if index != self.len {
            let last = unsafe { buf[self.len].assume_init_read() };
            buf[index].write(last);
        }

        Some(element)
    }

    /// Returns a shared slice of all initialized elements.
    ///
    /// The slice length is always equal to [`len`](Self::len).
    pub fn as_slice(&self) -> &[T] {
        self.deref()
    }

    /// Returns a mutable slice of all initialized elements.
    ///
    /// Mutating the returned slice can change element values and order, but it
    /// cannot change the vector length, current capacity, or maximum capacity.
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        self.deref_mut()
    }

    /// Returns the currently-created backing buffer capacity.
    ///
    /// This follows [`alloc::vec::Vec`] semantics: a newly-created empty vector
    /// has capacity `0`, while a vector with a backing buffer has capacity `N`.
    /// Calling [`shrink_to_fit`](Self::shrink_to_fit) on an empty vector drops
    /// the backing buffer and returns this value to `0`.
    pub fn capacity(&self) -> usize {
        if self.buf.is_some() { N } else { 0 }
    }

    /// Returns the fixed maximum capacity `N`.
    ///
    /// This value is known at compile time and never changes.
    pub const fn max_capacity(&self) -> usize {
        N
    }

    /// Returns how many more elements can be inserted before the vector is full.
    ///
    /// This is equivalent to `capacity() - len()`: it returns `0` before the
    /// backing buffer is created and then tracks the unused slots in the fixed
    /// buffer.
    pub fn spare_capacity(&self) -> usize {
        self.capacity() - self.len
    }

    /// Returns the number of initialized elements currently in the vector.
    pub const fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the vector contains no elements.
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Removes the elements in `range`, returning an iterator over the removed
    /// elements.
    ///
    /// The returned [`Drain`] is double-ended, so removed elements can be
    /// consumed from either side. If the iterator is dropped before being fully
    /// consumed, it drops the remaining removed elements and moves the original
    /// tail back into place.
    ///
    /// While the iterator exists, it keeps a mutable borrow of the vector.
    ///
    /// # Panics
    ///
    /// Panics if the range start is greater than the range end, if the range
    /// end exceeds `self.len()`, or if an excluded start or included end bound
    /// overflows `usize`.
    ///
    /// # Leaking
    ///
    /// If the returned iterator goes out of scope without being dropped (due to
    /// [`core::mem::forget`], for example), the vector may have lost and leaked
    /// elements arbitrarily, including elements outside the range.
    ///
    /// # Examples
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::from([1, 2, 3]);
    /// let u: Vec<_> = v.drain(1..).collect();
    /// assert_eq!(v.as_slice(), &[1]);
    /// assert_eq!(u, &[2, 3]);
    ///
    /// // A full range clears the vector, like `clear()` does
    /// v.drain(..);
    /// assert_eq!(v.as_slice(), &[]);
    /// ```
    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, N>
    where
        R: RangeBounds<usize>,
    {
        let range = drain_range(range, self.len);

        assert!(range.start <= range.end);
        assert!(range.end <= self.len);

        // Memory safety
        //
        // Creating Drain shortens the source vector so uninitialized or moved-
        // from elements are not accessible if the Drain is leaked.
        //
        // Drain reads removed values by pointer.
        //
        // When Drain is dropped, the remaining tail is copied back to cover the
        // hole, and the vector length is restored to the new length.
        let original_len = self.len();
        self.len = range.start;

        Drain {
            leftover_range: range.clone(),
            drop_range: range,
            vec: self,
            original_len,
        }
    }

    /// Returns an iterator over immutable references to the elements.
    pub fn iter(&self) -> Iter<'_, T> {
        self.as_slice().iter()
    }

    /// Returns an iterator over mutable references to the elements.
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        self.as_mut_slice().iter_mut()
    }

    /// Drops all elements and resets the vector to an empty state.
    ///
    /// The backing buffer remains available for later reuse. If an element's
    /// destructor panics and the panic is caught, the vector is still left empty.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<i32, 4>::new();
    /// v.extend([1, 2, 3]);
    /// v.clear();
    /// assert!(v.is_empty());
    /// ```
    pub fn clear(&mut self) {
        let len = self.len;
        self.len = 0;

        if let Some(buf) = self.buf.as_mut() {
            unsafe {
                drop_initialized_range(buf.as_mut_ptr(), 0..len);
            }
        }
    }

    /// Drops the backing buffer when the vector is empty.
    ///
    /// This method releases the lazily-created backing buffer when
    /// [`len`](Self::len) is zero, making [`capacity`](Self::capacity) return
    /// `0`. It never changes [`max_capacity`](Self::max_capacity), and non-empty
    /// vectors are left unchanged.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut v = CapVec::<i32, 4>::new();
    /// v.extend([1, 2, 3]);
    /// v.clear();
    /// v.shrink_to_fit();
    ///
    /// assert_eq!(v.capacity(), 0);
    /// assert_eq!(v.max_capacity(), 4);
    /// assert!(v.is_empty());
    /// ```
    pub fn shrink_to_fit(&mut self) {
        if self.is_empty() {
            self.buf = None;
        }
    }
}

fn drain_range(range: impl RangeBounds<usize>, len: usize) -> Range<usize> {
    let start = match range.start_bound() {
        Bound::Included(&index) => index,
        Bound::Excluded(&index) => index.checked_add(1).expect("range start index overflow"),
        Bound::Unbounded => 0,
    };

    let end = match range.end_bound() {
        Bound::Included(&index) => index.checked_add(1).expect("range end index overflow"),
        Bound::Excluded(&index) => index,
        Bound::Unbounded => len,
    };

    start..end
}

impl<T, const N: usize> Deref for CapVec<T, N> {
    type Target = [T];

    fn deref(&self) -> &Self::Target {
        if let Some(elements) = self.buf.as_ref() {
            return unsafe { core::slice::from_raw_parts(elements.as_ptr() as *const T, self.len) };
        }

        &[]
    }
}

impl<T, const N: usize> DerefMut for CapVec<T, N> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        if let Some(elements) = self.buf.as_mut() {
            return unsafe {
                core::slice::from_raw_parts_mut(elements.as_mut_ptr() as *mut T, self.len)
            };
        }

        &mut []
    }
}

impl<T, const N: usize> IntoIterator for CapVec<T, N> {
    type Item = T;
    type IntoIter = IntoIter<T, N>;

    fn into_iter(mut self) -> Self::IntoIter {
        let len = self.len;
        match self.buf.take() {
            None => IntoIter::default(),
            Some(buf) => IntoIter {
                buf: Some(buf),
                alive: 0..len,
            },
        }
    }
}

impl<'a, T, const N: usize> IntoIterator for &'a CapVec<T, N> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T, const N: usize> IntoIterator for &'a mut CapVec<T, N> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T, const N: usize> PartialEq for CapVec<T, N>
where
    T: PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        self.as_slice() == other.as_slice()
    }
}

impl<T, const N: usize> PartialEq<[T]> for CapVec<T, N>
where
    T: PartialEq,
{
    fn eq(&self, other: &[T]) -> bool {
        self.as_slice() == other
    }
}

impl<T, const N: usize> PartialEq<&[T]> for CapVec<T, N>
where
    T: PartialEq,
{
    fn eq(&self, other: &&[T]) -> bool {
        self.as_slice() == *other
    }
}

impl<T, const N: usize> PartialEq<[T; N]> for CapVec<T, N>
where
    T: PartialEq,
{
    fn eq(&self, other: &[T; N]) -> bool {
        self.as_slice() == other
    }
}

impl<T, const N: usize> PartialEq<&[T; N]> for CapVec<T, N>
where
    T: PartialEq,
{
    fn eq(&self, other: &&[T; N]) -> bool {
        self.as_slice() == *other
    }
}

impl<T, const N: usize> Eq for CapVec<T, N> where T: Eq {}

impl<T, const N: usize> PartialOrd for CapVec<T, N>
where
    T: PartialOrd,
{
    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
        self.as_slice().partial_cmp(other)
    }
}

impl<T, const N: usize> PartialOrd<[T]> for CapVec<T, N>
where
    T: PartialOrd,
{
    fn partial_cmp(&self, other: &[T]) -> Option<core::cmp::Ordering> {
        self.as_slice().partial_cmp(other)
    }
}

impl<T, const N: usize> PartialOrd<[T; N]> for CapVec<T, N>
where
    T: PartialOrd,
{
    fn partial_cmp(&self, other: &[T; N]) -> Option<core::cmp::Ordering> {
        self.as_slice().partial_cmp(other)
    }
}

impl<T, const N: usize> Ord for CapVec<T, N>
where
    T: Ord,
{
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
        self.as_slice().cmp(other)
    }
}

impl<T, const N: usize> Hash for CapVec<T, N>
where
    T: Hash,
{
    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
        self.as_slice().hash(state);
    }
}

impl<T, const N: usize> core::fmt::Debug for CapVec<T, N>
where
    T: core::fmt::Debug,
{
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_list().entries(self.as_slice()).finish()
    }
}

impl<T, const N: usize> Drop for CapVec<T, N> {
    fn drop(&mut self) {
        self.clear();
    }
}

/// An iterator over elements removed by [`CapVec::drain`].
///
/// `Drain` owns the removed elements as they are yielded. Dropping the iterator
/// drops any removed elements that have not yet been yielded, restores the
/// original tail of the vector, and updates the vector length.
///
/// The iterator borrows the source vector mutably for its entire lifetime, so
/// the vector cannot be used again until the `Drain` is dropped.
///
/// ```
/// use cap_vec::CapVec;
///
/// let mut values = CapVec::from([1, 2, 3, 4]);
/// let removed: Vec<_> = values.drain(1..3).rev().collect();
///
/// assert_eq!(removed, [3, 2]);
/// assert_eq!(values.as_slice(), &[1, 4]);
/// ```
pub struct Drain<'a, T, const N: usize> {
    leftover_range: Range<usize>,
    drop_range: Range<usize>,
    vec: &'a mut CapVec<T, N>,
    original_len: usize,
}

impl<T, const N: usize> Drain<'_, T, N> {
    /// Returns a shared slice of the removed elements that have not been yielded
    /// yet.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let mut values = CapVec::from([1, 2, 3, 4]);
    /// let mut drain = values.drain(1..);
    ///
    /// assert_eq!(drain.as_slice(), &[2, 3, 4]);
    /// assert_eq!(drain.next(), Some(2));
    /// assert_eq!(drain.as_slice(), &[3, 4]);
    /// ```
    pub fn as_slice(&self) -> &[T] {
        self.vec.buf.as_ref().map_or(&[], |buf| unsafe {
            core::slice::from_raw_parts(
                buf.as_ptr().add(self.leftover_range.start) as *const T,
                self.leftover_range.len(),
            )
        })
    }
}

impl<T, const N: usize> core::fmt::Debug for Drain<'_, T, N>
where
    T: core::fmt::Debug,
{
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_tuple("Drain").field(&self.as_slice()).finish()
    }
}

impl<'a, T, const N: usize> Iterator for Drain<'a, T, N> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        let index = self.leftover_range.next()?;
        debug_assert!(self.vec.buf.is_some());
        let element = unsafe { self.vec.buf.as_mut().unwrap_unchecked()[index].assume_init_read() };
        Some(element)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.leftover_range.size_hint()
    }

    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        let len = self.leftover_range.len();
        let count = n.min(len);
        let start = self.leftover_range.start;
        self.leftover_range.start += count;

        if count > 0 {
            debug_assert!(self.vec.buf.is_some());
            let buf = unsafe { self.vec.buf.as_mut().unwrap_unchecked() };

            unsafe {
                drop_initialized_range(buf.as_mut_ptr(), start..start + count);
            }
        }

        (n < len).then(|| unsafe {
            let index = self.leftover_range.next().unwrap_unchecked();
            self.vec.buf.as_mut().unwrap_unchecked()[index].assume_init_read()
        })
    }

    fn last(mut self) -> Option<Self::Item> {
        self.next_back()
    }

    fn count(self) -> usize {
        self.leftover_range.len()
    }
}

impl<T, const N: usize> DoubleEndedIterator for Drain<'_, T, N> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let index = self.leftover_range.next_back()?;
        debug_assert!(self.vec.buf.is_some());
        let element = unsafe { self.vec.buf.as_mut().unwrap_unchecked()[index].assume_init_read() };
        Some(element)
    }

    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
        let len = self.leftover_range.len();
        let count = n.min(len);
        self.leftover_range.end -= count;

        if count > 0 {
            debug_assert!(self.vec.buf.is_some());
            let buf = unsafe { self.vec.buf.as_mut().unwrap_unchecked() };

            unsafe {
                drop_initialized_range(
                    buf.as_mut_ptr(),
                    self.leftover_range.end..self.leftover_range.end + count,
                );
            }
        }

        (n < len).then(|| unsafe {
            let index = self.leftover_range.next_back().unwrap_unchecked();
            self.vec.buf.as_mut().unwrap_unchecked()[index].assume_init_read()
        })
    }
}

impl<T, const N: usize> FusedIterator for Drain<'_, T, N> {}

impl<T, const N: usize> ExactSizeIterator for Drain<'_, T, N> {
    fn len(&self) -> usize {
        self.leftover_range.len()
    }
}

impl<T, const N: usize> Drop for Drain<'_, T, N> {
    fn drop(&mut self) {
        struct Guard<'a, T, const N: usize> {
            vec: &'a mut CapVec<T, N>,
            drop_range: Range<usize>,
            original_len: usize,
        }

        impl<T, const N: usize> Drop for Guard<'_, T, N> {
            fn drop(&mut self) {
                if let Some(buf) = self.vec.buf.as_mut() {
                    let ptr = buf.as_mut_ptr();

                    unsafe {
                        core::ptr::copy(
                            ptr.add(self.drop_range.end),
                            ptr.add(self.drop_range.start),
                            self.original_len - self.drop_range.end,
                        );
                    }
                }

                self.vec.len = self.original_len - self.drop_range.len();
            }
        }

        let guard = Guard {
            vec: self.vec,
            drop_range: self.drop_range.clone(),
            original_len: self.original_len,
        };

        if let Some(buf) = guard.vec.buf.as_mut() {
            unsafe {
                drop_initialized_range(buf.as_mut_ptr(), self.leftover_range.clone());
            }
        }
    }
}

/// A consuming iterator over a [`CapVec`].
///
/// This iterator owns the vector's backing buffer and yields initialized
/// elements by value. Elements can be consumed from the front with
/// [`Iterator::next`] or from the back with [`DoubleEndedIterator::next_back`].
/// Any elements left in the iterator are dropped when the iterator is dropped.
///
/// ```
/// use cap_vec::CapVec;
///
/// let values = CapVec::from(["a", "b", "c"]);
/// let mut iter = values.into_iter();
///
/// assert_eq!(iter.next(), Some("a"));
/// assert_eq!(iter.next_back(), Some("c"));
/// assert_eq!(iter.next(), Some("b"));
/// assert_eq!(iter.next(), None);
/// ```
pub struct IntoIter<T, const N: usize> {
    buf: Option<Box<[MaybeUninit<T>; N]>>,
    alive: Range<usize>,
}

impl<T, const N: usize> Default for IntoIter<T, N> {
    fn default() -> Self {
        Self {
            buf: None,
            alive: 0..0,
        }
    }
}

impl<T, const N: usize> IntoIter<T, N> {
    /// Returns a shared slice of the elements that have not been yielded yet.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let values = CapVec::from([1, 2, 3]);
    /// let mut iter = values.into_iter();
    ///
    /// assert_eq!(iter.as_slice(), &[1, 2, 3]);
    /// assert_eq!(iter.next(), Some(1));
    /// assert_eq!(iter.as_slice(), &[2, 3]);
    /// ```
    pub fn as_slice(&self) -> &[T] {
        self.buf.as_ref().map_or(&[], |buf| unsafe {
            core::slice::from_raw_parts(
                buf.as_ptr().add(self.alive.start) as *const T,
                self.alive.len(),
            )
        })
    }

    /// Returns a mutable slice of the elements that have not been yielded yet.
    ///
    /// ```
    /// use cap_vec::CapVec;
    ///
    /// let values = CapVec::from([1, 2, 3]);
    /// let mut iter = values.into_iter();
    ///
    /// iter.as_mut_slice()[1] = 20;
    /// assert_eq!(iter.collect::<Vec<_>>(), [1, 20, 3]);
    /// ```
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        self.buf.as_mut().map_or(&mut [], |buf| unsafe {
            core::slice::from_raw_parts_mut(
                buf.as_mut_ptr().add(self.alive.start) as *mut T,
                self.alive.len(),
            )
        })
    }
}

impl<T, const N: usize> Clone for IntoIter<T, N>
where
    T: Clone,
{
    fn clone(&self) -> Self {
        let values = self.as_slice();
        let len = values.len();

        if values.is_empty() {
            return Self::default();
        }

        Self {
            buf: Some(clone_into_uninit_buffer(values)),
            alive: 0..len,
        }
    }
}

impl<T, const N: usize> core::fmt::Debug for IntoIter<T, N>
where
    T: core::fmt::Debug,
{
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
    }
}

impl<T, const N: usize> Iterator for IntoIter<T, N> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        let index = self.alive.next()?;
        debug_assert!(self.buf.is_some());
        Some(unsafe { self.buf.as_mut().unwrap_unchecked()[index].assume_init_read() })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.alive.size_hint()
    }

    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        let len = self.alive.len();
        let count = n.min(len);
        let start = self.alive.start;
        self.alive.start += count;

        if count > 0 {
            debug_assert!(self.buf.is_some());
            let buf = unsafe { self.buf.as_mut().unwrap_unchecked() };

            unsafe {
                drop_initialized_range(buf.as_mut_ptr(), start..start + count);
            }
        }

        (n < len).then(|| unsafe {
            let index = self.alive.next().unwrap_unchecked();
            self.buf.as_mut().unwrap_unchecked()[index].assume_init_read()
        })
    }

    fn last(mut self) -> Option<Self::Item> {
        self.next_back()
    }

    fn count(self) -> usize {
        self.alive.len()
    }
}

impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let index = self.alive.next_back()?;
        debug_assert!(self.buf.is_some());
        Some(unsafe { self.buf.as_mut().unwrap_unchecked()[index].assume_init_read() })
    }

    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
        let len = self.alive.len();
        let count = n.min(len);
        self.alive.end -= count;

        if count > 0 {
            debug_assert!(self.buf.is_some());
            let buf = unsafe { self.buf.as_mut().unwrap_unchecked() };

            unsafe {
                drop_initialized_range(buf.as_mut_ptr(), self.alive.end..self.alive.end + count);
            }
        }

        (n < len).then(|| unsafe {
            let index = self.alive.next_back().unwrap_unchecked();
            self.buf.as_mut().unwrap_unchecked()[index].assume_init_read()
        })
    }
}

impl<T, const N: usize> FusedIterator for IntoIter<T, N> {}

impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> {
    fn len(&self) -> usize {
        self.alive.len()
    }
}

impl<T, const N: usize> Drop for IntoIter<T, N> {
    fn drop(&mut self) {
        if let Some(buf) = self.buf.as_mut() {
            unsafe {
                drop_initialized_range(buf.as_mut_ptr(), self.alive.clone());
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use alloc::boxed::Box;
    use alloc::rc::Rc;
    use alloc::vec::Vec;
    use core::cell::Cell;
    use core::hash::{Hash, Hasher};
    use core::panic::AssertUnwindSafe;
    use std::collections::hash_map::DefaultHasher;
    use std::format;
    use std::panic::catch_unwind;

    use super::CapVec;

    struct DropCounter {
        id: usize,
        dropped: Rc<Cell<usize>>,
    }

    impl Drop for DropCounter {
        fn drop(&mut self) {
            self.dropped.set(self.dropped.get() + 1);
        }
    }

    fn drop_counter(id: usize, dropped: &Rc<Cell<usize>>) -> DropCounter {
        DropCounter {
            id,
            dropped: Rc::clone(dropped),
        }
    }

    #[test]
    fn test_default_creates_empty_vector() {
        let sut = CapVec::<i32, 8>::default();
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.max_capacity(), 8);
        assert_eq!(sut.spare_capacity(), 0);
        assert!(sut.is_empty());
        assert!(sut.as_slice().is_empty());
    }

    #[test]
    fn test_from_array_creates_full_vector() {
        const SEED: [i32; 4] = [1, 2, 3, 4];

        let sut = CapVec::<i32, 4>::from(SEED);
        assert_eq!(sut.len(), 4);
        assert_eq!(sut.capacity(), 4);
        assert_eq!(sut.max_capacity(), 4);
        assert_eq!(sut.spare_capacity(), 0);
        assert!(!sut.is_empty());
        assert_eq!(sut.as_slice(), &SEED);
    }

    #[test]
    fn test_clone_preserves_non_empty_vector() {
        let mut base = CapVec::<i32, 4>::new();
        base.extend([1, 2, 3]);

        let sut = base.clone();
        assert_eq!(sut.len(), base.len());
        assert_eq!(sut.capacity(), base.capacity());
        assert_eq!(sut.max_capacity(), base.max_capacity());
        assert_eq!(sut.spare_capacity(), base.spare_capacity());
        assert_eq!(sut.as_slice(), base.as_slice());

        base.push(4).unwrap();
        assert_ne!(sut.len(), base.len());
        assert_eq!(sut.as_slice(), &[1, 2, 3]);
    }

    #[test]
    fn test_clone_preserves_empty_vector() {
        let mut base = CapVec::<i32, 5>::new();
        let sut = base.clone();
        assert!(sut.is_empty());
        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.max_capacity(), 5);
        assert_eq!(sut.spare_capacity(), 0);
        assert!(sut.as_slice().is_empty());

        base.push(0).unwrap();
        assert_ne!(sut.len(), base.len());
        assert_eq!(sut.as_slice(), &[]);
    }

    #[test]
    fn test_clone_drops_initialized_elements_when_later_clone_panics() {
        struct PanicOnSecondClone {
            alive: Rc<Cell<usize>>,
            clone_calls: Rc<Cell<usize>>,
        }

        impl PanicOnSecondClone {
            fn new(alive: Rc<Cell<usize>>, clone_calls: Rc<Cell<usize>>) -> Self {
                alive.set(alive.get() + 1);
                Self { alive, clone_calls }
            }
        }

        impl Clone for PanicOnSecondClone {
            fn clone(&self) -> Self {
                let clone_calls = self.clone_calls.get() + 1;
                self.clone_calls.set(clone_calls);

                if clone_calls == 2 {
                    panic!("intentional clone panic");
                }

                self.alive.set(self.alive.get() + 1);
                Self {
                    alive: Rc::clone(&self.alive),
                    clone_calls: Rc::clone(&self.clone_calls),
                }
            }
        }

        impl Drop for PanicOnSecondClone {
            fn drop(&mut self) {
                self.alive.set(self.alive.get() - 1);
            }
        }

        let alive = Rc::new(Cell::new(0));
        let clone_calls = Rc::new(Cell::new(0));
        let base = CapVec::<_, 2>::from([
            PanicOnSecondClone::new(Rc::clone(&alive), Rc::clone(&clone_calls)),
            PanicOnSecondClone::new(Rc::clone(&alive), Rc::clone(&clone_calls)),
        ]);

        let result = catch_unwind(AssertUnwindSafe(|| {
            let _ = base.clone();
        }));

        assert!(result.is_err());
        assert_eq!(alive.get(), 2);
    }

    #[test]
    fn test_new_creates_empty_vector() {
        let sut = CapVec::<i32, 8>::new();
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.max_capacity(), 8);
        assert_eq!(sut.spare_capacity(), 0);
        assert!(sut.is_empty());
        assert!(sut.as_slice().is_empty());
    }

    #[test]
    fn test_len_tracks_initialized_elements() {
        let mut sut = CapVec::<i32, 3>::new();
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.max_capacity(), 3);
        assert_eq!(sut.spare_capacity(), 0);
        assert!(sut.is_empty());

        sut.push(10).unwrap();
        assert_eq!(sut.len(), 1);
        assert_eq!(sut.capacity(), 3);
        assert_eq!(sut.spare_capacity(), 2);

        sut.push(20).unwrap();
        assert_eq!(sut.len(), 2);
        assert_eq!(sut.spare_capacity(), 1);

        sut.pop();
        assert_eq!(sut.len(), 1);
        assert_eq!(sut.spare_capacity(), 2);

        sut.pop();
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.capacity(), 3);
        assert_eq!(sut.spare_capacity(), 3);
    }

    #[test]
    fn test_capacity_tracks_created_backing_buffer() {
        let mut sut = CapVec::<i32, 4>::new();
        assert_eq!(sut.capacity(), 0);

        sut.push(1).unwrap();
        assert_eq!(sut.capacity(), 4);

        sut.clear();
        assert_eq!(sut.capacity(), 4);

        sut.shrink_to_fit();
        assert_eq!(sut.capacity(), 0);
    }

    #[test]
    fn test_max_capacity_returns_const_generic_bound() {
        let sut = CapVec::<(), 4>::new();
        assert_eq!(sut.max_capacity(), 4);

        let sut = CapVec::<char, 16>::new();
        assert_eq!(sut.max_capacity(), 16);

        let sut = CapVec::<i64, 1>::new();
        assert_eq!(sut.max_capacity(), 1);
    }

    #[test]
    fn test_spare_capacity_tracks_remaining_buffer_slots() {
        let mut sut = CapVec::<i32, 4>::new();
        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.spare_capacity(), 0);

        sut.extend([1, 2, 3]);
        assert_eq!(sut.capacity(), 4);
        assert_eq!(sut.spare_capacity(), 1);

        sut.push(4).unwrap();
        assert_eq!(sut.spare_capacity(), 0);

        sut.clear();
        assert_eq!(sut.capacity(), 4);
        assert_eq!(sut.spare_capacity(), 4);

        sut.shrink_to_fit();
        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.spare_capacity(), 0);
    }

    #[test]
    fn test_is_empty_tracks_length() {
        let mut sut = CapVec::<i32, 2>::new();
        assert!(sut.is_empty());

        sut.push(1).unwrap();
        assert!(!sut.is_empty());

        sut.clear();
        assert!(sut.is_empty());
    }

    #[test]
    fn test_clear_removes_all_elements_and_reuses_buffer() {
        let mut sut = CapVec::<Box<str>, 3>::new();
        sut.push("a".into()).unwrap();
        sut.push("b".into()).unwrap();
        assert_eq!(sut.len(), 2);

        sut.clear();
        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());

        sut.push("c".into()).unwrap();
        assert_eq!(sut.as_slice(), &["c".into()]);
    }

    #[test]
    fn test_shrink_to_fit_drops_buffer_when_empty() {
        let mut sut = CapVec::<i32, 4>::new();
        sut.extend([1, 2, 3]);
        assert!(sut.buf.is_some());

        sut.clear();
        assert!(sut.buf.is_some());

        sut.shrink_to_fit();
        assert!(sut.buf.is_none());
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.max_capacity(), 4);

        sut.push(4).unwrap();
        assert_eq!(sut.as_slice(), &[4]);
        assert!(sut.buf.is_some());
    }

    #[test]
    fn test_shrink_to_fit_preserves_non_empty_buffer() {
        let mut sut = CapVec::<i32, 4>::new();
        sut.extend([1, 2]);
        let ptr = sut.buf.as_ref().unwrap().as_ptr();
        let capacity = sut.capacity();
        let spare_capacity = sut.spare_capacity();

        sut.shrink_to_fit();

        assert_eq!(sut.as_slice(), &[1, 2]);
        assert_eq!(sut.capacity(), capacity);
        assert_eq!(sut.spare_capacity(), spare_capacity);
        assert_eq!(sut.buf.as_ref().unwrap().as_ptr(), ptr);
    }

    #[test]
    fn test_shrink_to_fit_drops_empty_array_buffer() {
        let mut sut = CapVec::from([(); 0]);
        assert!(sut.buf.is_some());

        sut.shrink_to_fit();

        assert!(sut.buf.is_none());
        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.max_capacity(), 0);
        assert_eq!(sut.spare_capacity(), 0);
    }

    #[test]
    fn test_clear_resets_len_before_dropping_elements() {
        struct PanicOnDrop {
            alive: Rc<Cell<usize>>,
            has_panicked: Rc<Cell<bool>>,
        }

        impl PanicOnDrop {
            fn new(alive: Rc<Cell<usize>>, has_panicked: Rc<Cell<bool>>) -> Self {
                alive.set(alive.get() + 1);
                Self {
                    alive,
                    has_panicked,
                }
            }
        }

        impl Drop for PanicOnDrop {
            fn drop(&mut self) {
                self.alive.set(self.alive.get() - 1);

                if !self.has_panicked.replace(true) {
                    panic!("intentional drop panic");
                }
            }
        }

        let alive = Rc::new(Cell::new(0));
        let has_panicked = Rc::new(Cell::new(false));
        let mut sut = CapVec::<_, 3>::from([
            PanicOnDrop::new(Rc::clone(&alive), Rc::clone(&has_panicked)),
            PanicOnDrop::new(Rc::clone(&alive), Rc::clone(&has_panicked)),
            PanicOnDrop::new(Rc::clone(&alive), Rc::clone(&has_panicked)),
        ]);

        let result = catch_unwind(AssertUnwindSafe(|| {
            sut.clear();
        }));

        assert!(result.is_err());
        assert!(sut.is_empty());
        assert_eq!(alive.get(), 0);

        assert!(
            sut.push(PanicOnDrop::new(
                Rc::clone(&alive),
                Rc::clone(&has_panicked),
            ))
            .is_ok()
        );

        assert_eq!(sut.len(), 1);
        assert_eq!(alive.get(), 1);
    }

    #[test]
    fn test_as_slice_returns_initialized_elements() {
        let mut sut = CapVec::<i32, 3>::new();
        sut.push(10).unwrap();
        sut.push(20).unwrap();
        sut.push(30).unwrap();

        let slice = sut.as_slice();
        assert_eq!(slice, &[10, 20, 30]);
    }

    #[test]
    fn test_as_mut_slice_allows_mutating_initialized_elements() {
        let mut sut = CapVec::<i32, 4>::new();
        sut.extend([1, 2, 3]);

        {
            let slice = sut.as_mut_slice();
            slice[0] = 10;
            slice[1] = 20;
            slice[2] = 30;
        }

        assert_eq!(sut.as_slice(), &[10, 20, 30]);

        sut.as_mut_slice().reverse();
        assert_eq!(sut.as_slice(), &[30, 20, 10]);
    }

    #[test]
    fn test_extend_partially_fills_empty_zst_vector() {
        let mut sut = CapVec::<(), 4>::new();
        assert!(sut.is_empty());
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.as_slice(), []);

        let mut leftover = sut.extend(core::iter::repeat_n((), 2));
        assert_eq!(leftover.next(), None);

        assert!(!sut.is_empty());
        assert_eq!(sut.len(), 2);
        assert_eq!(sut.as_slice(), [(); 2]);
    }

    #[test]
    fn test_extend_fills_empty_zst_vector() {
        let mut sut = CapVec::<(), 4>::new();
        assert!(sut.is_empty());
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.as_slice(), []);

        let mut leftover = sut.extend(core::iter::repeat(()));
        assert_eq!(leftover.next(), Some(()));

        assert!(!sut.is_empty());
        assert_eq!(sut.len(), 4);
        assert_eq!(sut.as_slice(), [(); 4]);
    }

    #[test]
    fn test_large_capacity_zst_does_not_need_stack_buffer() {
        let mut sut = CapVec::<(), { usize::MAX }>::new();
        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.max_capacity(), usize::MAX);
        assert_eq!(sut.spare_capacity(), 0);

        sut.push(()).unwrap();

        assert_eq!(sut.len(), 1);
        assert_eq!(sut.capacity(), usize::MAX);
        assert_eq!(sut.max_capacity(), usize::MAX);
        assert_eq!(sut.spare_capacity(), usize::MAX - 1);
        assert_eq!(sut.as_slice(), [()]);
    }

    #[test]
    fn test_extend_appends_to_partially_filled_zst_vector() {
        let mut sut = CapVec::<(), 8>::new();
        assert!(sut.is_empty());
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.as_slice(), []);

        let mut leftover = sut.extend(core::iter::repeat_n((), 3));
        assert_eq!(leftover.next(), None);

        assert!(!sut.is_empty());
        assert_eq!(sut.len(), 3);
        assert_eq!(sut.as_slice(), [(); 3]);

        let mut leftover = sut.extend(core::iter::repeat_n((), 3));
        assert_eq!(leftover.next(), None);

        assert!(!sut.is_empty());
        assert_eq!(sut.len(), 6);
        assert_eq!(sut.as_slice(), [(); 6]);

        let mut leftover = sut.extend(core::iter::repeat(()));
        assert_eq!(leftover.next(), Some(()));

        assert!(!sut.is_empty());
        assert_eq!(sut.len(), 8);
        assert_eq!(sut.as_slice(), [(); 8]);
    }

    #[test]
    fn test_extend_zero_capacity_vector_returns_all_items() {
        let mut sut = CapVec::<(), 0>::new();
        assert!(sut.is_empty());
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.as_slice(), []);

        let mut leftover = sut.extend(core::iter::repeat(()));
        assert_eq!(leftover.next(), Some(()));
        assert!(sut.is_empty());
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.as_slice(), []);
    }

    #[test]
    fn test_extend_preserves_initialized_elements_when_iterator_panics() {
        struct PanicAfterTwo {
            next_id: usize,
            dropped: Rc<Cell<usize>>,
        }

        impl Iterator for PanicAfterTwo {
            type Item = DropCounter;

            fn next(&mut self) -> Option<Self::Item> {
                if self.next_id == 2 {
                    panic!("intentional extend iterator panic");
                }

                let item = drop_counter(self.next_id, &self.dropped);
                self.next_id += 1;
                Some(item)
            }
        }

        let dropped = Rc::new(Cell::new(0));
        let mut sut = CapVec::<_, 4>::new();

        let result = catch_unwind(AssertUnwindSafe(|| {
            sut.extend(PanicAfterTwo {
                next_id: 0,
                dropped: Rc::clone(&dropped),
            });
        }));

        assert!(result.is_err());
        assert_eq!(dropped.get(), 0);
        assert_eq!(sut.len(), 2);
        assert_eq!(
            sut.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 1]
        );

        drop(sut);
        assert_eq!(dropped.get(), 2);
    }

    #[test]
    fn test_push_and_insert_zero_capacity_vector_return_uninserted_items() {
        let mut sut = CapVec::<i32, 0>::new();

        assert_eq!(sut.push(1), Err(1));
        assert_eq!(sut.insert(0, 2), Err(2));
        assert_eq!(sut.insert(usize::MAX, 3), Err(3));
        assert!(sut.is_empty());
        assert_eq!(sut.as_slice(), []);
    }

    #[test]
    fn test_zero_capacity_non_zst_array_supports_empty_iterators() {
        let mut sut = CapVec::<DropCounter, 0>::from([]);

        assert_eq!(sut.capacity(), 0);
        assert_eq!(sut.max_capacity(), 0);
        assert!(sut.as_slice().is_empty());
        assert_eq!(sut.drain(..).count(), 0);
        assert_eq!(CapVec::<DropCounter, 0>::from([]).into_iter().count(), 0);
    }

    #[test]
    fn test_drop_tracked_values_survive_mixed_shifts_drains_and_consumption() {
        let dropped = Rc::new(Cell::new(0));
        let mut sut = CapVec::<_, 6>::new();

        assert!(sut.push(drop_counter(0, &dropped)).is_ok());
        assert!(sut.push(drop_counter(1, &dropped)).is_ok());
        assert!(sut.push(drop_counter(2, &dropped)).is_ok());
        assert!(sut.push(drop_counter(3, &dropped)).is_ok());
        assert!(sut.insert(2, drop_counter(4, &dropped)).is_ok());

        let removed = sut.remove(1).unwrap();
        assert_eq!(removed.id, 1);
        drop(removed);
        assert_eq!(dropped.get(), 1);

        let mut drain = sut.drain(1..3);
        let item = drain.next_back().unwrap();
        assert_eq!(item.id, 2);
        drop(item);
        assert_eq!(dropped.get(), 2);

        drop(drain);
        assert_eq!(dropped.get(), 3);
        assert_eq!(
            sut.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 3]
        );

        assert!(sut.push(drop_counter(5, &dropped)).is_ok());
        assert!(sut.insert(1, drop_counter(6, &dropped)).is_ok());

        let ids = sut
            .into_iter()
            .map(|element| element.id)
            .collect::<Vec<_>>();
        assert_eq!(ids, [0, 6, 3, 5]);
        assert_eq!(dropped.get(), 7);
    }

    #[test]
    fn test_insert_places_elements_at_requested_index() {
        let mut sut: CapVec<i64, 6> = CapVec::new();
        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());

        assert_eq!(sut.insert(0, 10), Ok(()));
        assert_eq!(sut.first(), Some(&10));
        assert_eq!(sut.len(), 1);

        assert_eq!(sut.insert(1, 15), Ok(()));
        assert_eq!(sut.first(), Some(&10));
        assert_eq!(sut.get(1), Some(&15));
        assert_eq!(sut.len(), 2);

        assert_eq!(sut.insert(0, 5), Ok(()));
        assert_eq!(sut.first(), Some(&5));
        assert_eq!(sut.get(1), Some(&10));
        assert_eq!(sut.get(2), Some(&15));
        assert_eq!(sut.len(), 3);

        assert_eq!(sut.insert(3, 20), Ok(()));
        assert_eq!(sut.first(), Some(&5));
        assert_eq!(sut.get(1), Some(&10));
        assert_eq!(sut.get(2), Some(&15));
        assert_eq!(sut.get(3), Some(&20));
        assert_eq!(sut.len(), 4);

        assert_eq!(sut.insert(2, 13), Ok(()));
        assert_eq!(sut.first(), Some(&5));
        assert_eq!(sut.get(1), Some(&10));
        assert_eq!(sut.get(2), Some(&13));
        assert_eq!(sut.get(3), Some(&15));
        assert_eq!(sut.get(4), Some(&20));
        assert_eq!(sut.len(), 5);

        assert_eq!(sut.insert(4, 17), Ok(()));
        assert_eq!(sut.first(), Some(&5));
        assert_eq!(sut.get(1), Some(&10));
        assert_eq!(sut.get(2), Some(&13));
        assert_eq!(sut.get(3), Some(&15));
        assert_eq!(sut.get(4), Some(&17));
        assert_eq!(sut.get(5), Some(&20));
        assert_eq!(sut.len(), 6);

        assert_eq!(sut.insert(6, 100), Err(100));
        assert_eq!(sut.insert(usize::MAX, 100), Err(100));
    }

    #[test]
    fn test_push_appends_until_full() {
        let mut sut: CapVec<i64, 4> = CapVec::new();
        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());
        assert_eq!(sut, &[][..]);

        sut.push(0).unwrap();
        assert_eq!(sut.len(), 1);
        assert!(!sut.is_empty());
        assert_eq!(sut, &[0][..]);

        sut.push(1).unwrap();
        assert_eq!(sut.len(), 2);
        assert!(!sut.is_empty());
        assert_eq!(sut, &[0, 1][..]);

        sut.push(2).unwrap();
        assert_eq!(sut.len(), 3);
        assert!(!sut.is_empty());
        assert_eq!(sut, &[0, 1, 2][..]);

        sut.push(3).unwrap();
        assert_eq!(sut.len(), 4);
        assert!(!sut.is_empty());
        assert_eq!(sut, &[0, 1, 2, 3][..]);

        assert_eq!(sut.push(4), Err(4));
        assert_eq!(sut.len(), 4);
        assert!(!sut.is_empty());
        assert_eq!(sut, &[0, 1, 2, 3][..]);
    }

    #[test]
    fn test_remove_shifts_tail_left() {
        let mut sut: CapVec<i64, 6> = CapVec::new();
        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());

        sut.insert(0, 0).unwrap();
        sut.insert(1, 1).unwrap();
        sut.insert(2, 2).unwrap();
        sut.insert(3, 3).unwrap();
        sut.insert(4, 4).unwrap();
        sut.insert(5, 5).unwrap();
        assert_eq!(sut.len(), 6);

        assert_eq!(sut.remove(2), Some(2));
        assert_eq!(sut.len(), 5);
        assert_eq!(sut.first(), Some(&0));
        assert_eq!(sut.get(1), Some(&1));
        assert_eq!(sut.get(2), Some(&3));
        assert_eq!(sut.get(3), Some(&4));
        assert_eq!(sut.get(4), Some(&5));

        assert_eq!(sut.remove(3), Some(4));
        assert_eq!(sut.len(), 4);
        assert_eq!(sut.first(), Some(&0));
        assert_eq!(sut.get(1), Some(&1));
        assert_eq!(sut.get(2), Some(&3));
        assert_eq!(sut.get(3), Some(&5));

        assert_eq!(sut.remove(1), Some(1));
        assert_eq!(sut.len(), 3);
        assert_eq!(sut.first(), Some(&0));
        assert_eq!(sut.get(1), Some(&3));
        assert_eq!(sut.get(2), Some(&5));

        assert_eq!(sut.remove(0), Some(0));
        assert_eq!(sut.len(), 2);
        assert_eq!(sut.first(), Some(&3));
        assert_eq!(sut.get(1), Some(&5));

        assert_eq!(sut.remove(1), Some(5));
        assert_eq!(sut.len(), 1);
        assert_eq!(sut.first(), Some(&3));

        assert_eq!(sut.remove(0), Some(3));
        assert_eq!(sut.len(), 0);

        assert_eq!(sut.remove(0), None);
    }

    #[test]
    fn test_truncate_drops_tail_and_retains_buffer() {
        let dropped = Rc::new(Cell::new(0));
        let mut sut = CapVec::<_, 5>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
            drop_counter(4, &dropped),
        ]);
        let capacity = sut.capacity();

        sut.truncate(3);

        assert_eq!(dropped.get(), 2);
        assert_eq!(sut.len(), 3);
        assert_eq!(sut.capacity(), capacity);
        assert_eq!(
            sut.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 1, 2]
        );

        sut.truncate(5);
        assert_eq!(dropped.get(), 2);
        assert_eq!(sut.len(), 3);

        sut.truncate(0);
        assert_eq!(dropped.get(), 5);
        assert!(sut.is_empty());
        assert_eq!(sut.capacity(), capacity);
    }

    #[test]
    fn test_truncate_empty_vector_is_noop() {
        let mut sut = CapVec::<i32, 4>::new();

        sut.truncate(0);
        sut.truncate(10);

        assert!(sut.is_empty());
        assert_eq!(sut.capacity(), 0);
    }

    #[test]
    fn test_swap_remove_replaces_item_with_last_element() {
        let mut sut = CapVec::<i32, 5>::from([10, 20, 30, 40, 50]);

        assert_eq!(sut.swap_remove(1), Some(20));
        assert_eq!(sut.as_slice(), &[10, 50, 30, 40]);
        assert_eq!(sut.len(), 4);

        assert_eq!(sut.swap_remove(3), Some(40));
        assert_eq!(sut.as_slice(), &[10, 50, 30]);
        assert_eq!(sut.len(), 3);

        assert_eq!(sut.swap_remove(3), None);
        assert_eq!(sut.swap_remove(usize::MAX), None);
        assert_eq!(sut.as_slice(), &[10, 50, 30]);
    }

    #[test]
    fn test_swap_remove_drops_only_removed_value() {
        let dropped = Rc::new(Cell::new(0));
        let mut sut = CapVec::<_, 4>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
        ]);

        let removed = sut.swap_remove(1).unwrap();

        assert_eq!(dropped.get(), 0);
        assert_eq!(removed.id, 1);
        assert_eq!(
            sut.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 3, 2]
        );

        drop(removed);
        assert_eq!(dropped.get(), 1);

        drop(sut);
        assert_eq!(dropped.get(), 4);
    }

    #[test]
    fn test_pop_removes_elements_from_back() {
        let mut sut: CapVec<i64, 4> = CapVec::new();

        let mut leftover = sut.extend(0..5);
        assert_eq!(leftover.next(), Some(4));
        assert_eq!(sut.len(), 4);
        assert!(!sut.is_empty());

        for i in (0..4).rev() {
            assert_eq!(sut.pop(), Some(i));
            assert_eq!(sut.len(), i as usize);
        }

        assert_eq!(sut.pop(), None);
        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());
    }

    #[test]
    fn test_index_mut_allows_mutating_elements() {
        let mut sut: CapVec<i64, 4> = CapVec::new();

        let mut leftover = sut.extend(0..5);
        assert_eq!(leftover.next(), Some(4));

        assert_eq!(sut.len(), 4);
        assert!(!sut.is_empty());
        assert_eq!(sut, [0, 1, 2, 3]);

        sut[0] *= 10;
        sut[1] *= 10;
        sut[2] *= 10;
        sut[3] *= 10;

        assert_eq!(sut, [0, 10, 20, 30]);
        assert_eq!(sut.len(), 4);
        assert!(!sut.is_empty());
    }

    #[test]
    fn test_get_on_empty_vector_returns_none() {
        let sut: CapVec<i64, 6> = CapVec::new();
        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());
        assert_eq!(<[i64]>::get(&sut, 0), None);
    }

    #[test]
    fn test_get_mut_on_empty_vector_returns_none() {
        let mut sut: CapVec<i64, 6> = CapVec::new();
        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());
        assert_eq!(sut.get_mut(0), None);
    }

    #[test]
    fn test_comparison_matches_slice_behavior() {
        let sut: CapVec<i64, 4> = CapVec::from([0, 1, 2, 3]);

        assert_eq!(sut, sut);
        assert_eq!(sut, sut.clone());

        assert_eq!(sut, [0, 1, 2, 3]);
        assert_eq!(sut, &[0, 1, 2, 3]);
        assert_eq!(sut, [0, 1, 2, 3][..]);
        assert_eq!(sut, &[0, 1, 2, 3][..]);
        assert_eq!(sut, CapVec::from([0, 1, 2, 3]));

        assert_ne!(sut, [0, 10, 20, 30]);
        assert_ne!(sut, &[0, 10, 20, 30]);
        assert_ne!(sut, [0, 10, 20, 30][..]);
        assert_ne!(sut, &[0, 10, 20, 30][..]);
        assert_ne!(sut, CapVec::from([0, 10, 20, 30]));

        assert_ne!(sut, [][..]);
        assert_ne!(sut, &[][..]);

        let sut = CapVec::<i32, 4>::new();
        assert_eq!(sut, sut);
        assert_eq!(sut, sut.clone());

        assert_eq!(sut, [][..]);
        assert_eq!(sut, &[][..]);
        assert_eq!(sut, CapVec::new());
    }

    #[test]
    fn test_debug_ordering_and_hash_match_slice_behavior() {
        let sut = CapVec::from([1, 2, 3]);
        let lesser = CapVec::from([1, 2, 2]);
        let greater = CapVec::from([1, 2, 4]);

        assert_eq!(format!("{sut:?}"), "[1, 2, 3]");
        assert!(lesser < sut);
        assert!(greater > sut);
        assert_eq!(
            sut.partial_cmp(&[1, 2, 3]),
            Some(core::cmp::Ordering::Equal)
        );
        assert_eq!(sut.partial_cmp(&[1, 2, 4]), Some(core::cmp::Ordering::Less));

        let mut cap_vec_hasher = DefaultHasher::new();
        sut.hash(&mut cap_vec_hasher);

        let mut slice_hasher = DefaultHasher::new();
        [1, 2, 3].as_slice().hash(&mut slice_hasher);

        assert_eq!(cap_vec_hasher.finish(), slice_hasher.finish());
    }

    #[test]
    fn test_drain_partial_range_removes_items() {
        let mut sut = CapVec::<_, 8>::new();
        let mut leftover = sut.extend((0..8).map(Box::new));
        assert_eq!(leftover.next(), None);

        assert_eq!(sut.len(), 8);
        assert!(!sut.is_empty());
        assert_eq!(sut, [0, 1, 2, 3, 4, 5, 6, 7].map(Box::new));

        let iter = sut.drain(1..7);
        assert_eq!(iter.take(2).collect::<Vec<_>>(), [1, 2].map(Box::new));

        assert_eq!(sut.len(), 2);
        assert!(!sut.is_empty());
        assert_eq!(sut.as_slice(), [0, 7].map(Box::new));
    }

    #[test]
    fn test_drain_yields_items_from_both_ends() {
        let mut sut = CapVec::<_, 8>::new();
        let mut leftover = sut.extend((0..8).map(Box::new));
        assert_eq!(leftover.next(), None);

        assert_eq!(sut.len(), 8);
        assert!(!sut.is_empty());
        assert_eq!(sut, [0, 1, 2, 3, 4, 5, 6, 7].map(Box::new));

        let mut iter = sut.drain(1..7);
        assert_eq!(iter.next(), Some(Box::new(1)));
        assert_eq!(iter.next_back(), Some(Box::new(6)));

        assert_eq!(iter.next_back(), Some(Box::new(5)));
        assert_eq!(iter.next(), Some(Box::new(2)));

        assert_eq!(iter.len(), 2);
    }

    #[test]
    fn test_drain_empty_range_preserves_vector() {
        let mut sut = CapVec::from([1, 2, 3, 4]);

        let drained = sut.drain(2..2).collect::<Vec<_>>();

        assert_eq!(drained, []);
        assert_eq!(sut.as_slice(), &[1, 2, 3, 4]);
        assert_eq!(sut.len(), 4);
    }

    #[test]
    fn test_drain_tail_range_removes_items() {
        let mut sut = CapVec::from([1, 2, 3, 4]);

        let drained = sut.drain(2..4).collect::<Vec<_>>();

        assert_eq!(drained, [3, 4]);
        assert_eq!(sut.as_slice(), &[1, 2]);
        assert_eq!(sut.len(), 2);
    }

    #[test]
    fn test_drain_accepts_all_range_bounds() {
        use core::ops::Bound::{Excluded, Included};

        let mut sut = CapVec::from([1, 2, 3, 4]);
        assert_eq!(sut.drain(..).collect::<Vec<_>>(), [1, 2, 3, 4]);
        assert_eq!(sut.as_slice(), &[]);

        let mut sut = CapVec::from([1, 2, 3, 4]);
        assert_eq!(sut.drain(2..).collect::<Vec<_>>(), [3, 4]);
        assert_eq!(sut.as_slice(), &[1, 2]);

        let mut sut = CapVec::from([1, 2, 3, 4]);
        assert_eq!(sut.drain(..2).collect::<Vec<_>>(), [1, 2]);
        assert_eq!(sut.as_slice(), &[3, 4]);

        let mut sut = CapVec::from([1, 2, 3, 4]);
        assert_eq!(sut.drain(1..=2).collect::<Vec<_>>(), [2, 3]);
        assert_eq!(sut.as_slice(), &[1, 4]);

        let mut sut = CapVec::from([1, 2, 3, 4]);
        assert_eq!(
            sut.drain((Excluded(0), Included(2))).collect::<Vec<_>>(),
            [2, 3]
        );
        assert_eq!(sut.as_slice(), &[1, 4]);
    }

    #[test]
    fn test_drain_as_slice_tracks_remaining_items() {
        let mut sut = CapVec::from([1, 2, 3, 4, 5]);
        let mut drain = sut.drain(1..4);

        assert_eq!(drain.as_slice(), &[2, 3, 4]);
        assert_eq!(drain.next(), Some(2));
        assert_eq!(drain.as_slice(), &[3, 4]);
        assert_eq!(drain.next_back(), Some(4));
        assert_eq!(drain.as_slice(), &[3]);
    }

    #[test]
    fn test_drain_debug_formats_remaining_items() {
        let mut sut = CapVec::from([1, 2, 3, 4]);
        let mut drain = sut.drain(1..);

        assert_eq!(format!("{drain:?}"), "Drain([2, 3, 4])");
        assert_eq!(drain.next(), Some(2));
        assert_eq!(format!("{drain:?}"), "Drain([3, 4])");
        drain.for_each(drop);
    }

    #[test]
    fn test_drain_debug_formats_empty_iterator() {
        let mut sut = CapVec::from([1, 2, 3, 4]);
        let drain = sut.drain(2..2);

        assert_eq!(format!("{drain:?}"), "Drain([])");
    }

    #[test]
    fn test_drain_nth_drops_skipped_items() {
        let dropped = Rc::new(Cell::new(0));
        let mut base = CapVec::<_, 5>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
            drop_counter(4, &dropped),
        ]);

        let mut drain = base.drain(1..4);
        let item = drain.nth(1).unwrap();

        assert_eq!(dropped.get(), 1);
        assert_eq!(item.id, 2);

        drop(item);
        assert_eq!(dropped.get(), 2);

        drop(drain);
        assert_eq!(dropped.get(), 3);
        assert_eq!(
            base.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 4]
        );
    }

    #[test]
    fn test_drain_nth_back_drops_skipped_items() {
        let dropped = Rc::new(Cell::new(0));
        let mut base = CapVec::<_, 5>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
            drop_counter(4, &dropped),
        ]);

        let mut drain = base.drain(1..4);
        let item = drain.nth_back(1).unwrap();

        assert_eq!(dropped.get(), 1);
        assert_eq!(item.id, 2);

        drop(item);
        assert_eq!(dropped.get(), 2);

        drop(drain);
        assert_eq!(dropped.get(), 3);
        assert_eq!(
            base.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 4]
        );
    }

    #[test]
    fn test_drain_last_drops_skipped_items_and_restores_tail() {
        let dropped = Rc::new(Cell::new(0));
        let mut base = CapVec::<_, 5>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
            drop_counter(4, &dropped),
        ]);

        let item = base.drain(1..4).last().unwrap();

        assert_eq!(dropped.get(), 2);
        assert_eq!(item.id, 3);
        assert_eq!(
            base.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 4]
        );

        drop(item);
        assert_eq!(dropped.get(), 3);

        drop(base);
        assert_eq!(dropped.get(), 5);
    }

    #[test]
    fn test_drain_count_drops_remaining_items_and_restores_tail() {
        let dropped = Rc::new(Cell::new(0));
        let mut base = CapVec::<_, 5>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
            drop_counter(4, &dropped),
        ]);

        assert_eq!(base.drain(1..4).count(), 3);
        assert_eq!(dropped.get(), 3);
        assert_eq!(
            base.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 4]
        );

        drop(base);
        assert_eq!(dropped.get(), 5);
    }

    #[test]
    #[should_panic]
    fn test_drain_panics_when_range_start_is_after_end() {
        let mut sut = CapVec::from([1, 2, 3, 4]);
        let start = sut.len() - 1;
        let end = start - 1;
        sut.drain(start..end);
    }

    #[test]
    #[should_panic]
    fn test_drain_panics_when_range_end_exceeds_len() {
        let mut sut = CapVec::from([1, 2, 3, 4]);
        sut.drain(0..5);
    }

    #[test]
    fn test_drain_restores_tail_when_dropping_drained_element_panics() {
        struct PanicOnDrop {
            id: usize,
            alive: Rc<Cell<usize>>,
            has_panicked: Rc<Cell<bool>>,
        }

        impl PanicOnDrop {
            fn new(id: usize, alive: Rc<Cell<usize>>, has_panicked: Rc<Cell<bool>>) -> Self {
                alive.set(alive.get() + 1);
                Self {
                    id,
                    alive,
                    has_panicked,
                }
            }
        }

        impl Drop for PanicOnDrop {
            fn drop(&mut self) {
                self.alive.set(self.alive.get() - 1);

                if self.id == 1 && !self.has_panicked.replace(true) {
                    panic!("intentional drain drop panic");
                }
            }
        }

        let alive = Rc::new(Cell::new(0));
        let has_panicked = Rc::new(Cell::new(false));
        let mut sut = CapVec::<_, 4>::from([
            PanicOnDrop::new(0, Rc::clone(&alive), Rc::clone(&has_panicked)),
            PanicOnDrop::new(1, Rc::clone(&alive), Rc::clone(&has_panicked)),
            PanicOnDrop::new(2, Rc::clone(&alive), Rc::clone(&has_panicked)),
            PanicOnDrop::new(3, Rc::clone(&alive), Rc::clone(&has_panicked)),
        ]);

        let result = catch_unwind(AssertUnwindSafe(|| {
            drop(sut.drain(1..3));
        }));

        assert!(result.is_err());
        assert_eq!(sut.len(), 2);
        assert_eq!(
            sut.iter().map(|element| element.id).collect::<Vec<_>>(),
            [0, 3]
        );
        assert_eq!(alive.get(), 2);
    }

    #[test]
    fn test_drain_full_range_removes_all_items() {
        let mut sut = CapVec::<_, 8>::new();
        let mut leftover = sut.extend((0..8).map(Box::new));
        assert_eq!(leftover.next(), None);

        assert_eq!(sut.len(), 8);
        assert!(!sut.is_empty());
        assert_eq!(sut, [0, 1, 2, 3, 4, 5, 6, 7].map(Box::new));

        let iter = sut.drain(0..8);
        assert_eq!(
            iter.collect::<Vec<_>>(),
            [0, 1, 2, 3, 4, 5, 6, 7].map(Box::new)
        );

        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());
        assert_eq!(sut.as_slice(), []);
    }

    #[test]
    fn test_drain_partial_range_zst_removes_items() {
        let mut sut = CapVec::<_, 8>::new();
        let mut leftover = sut.extend([(); 8]);
        assert_eq!(leftover.next(), None);

        assert_eq!(sut.len(), 8);
        assert!(!sut.is_empty());
        assert_eq!(sut, [(); 8]);

        let iter = sut.drain(1..7);
        assert_eq!(iter.take(2).collect::<Vec<_>>(), [(); 2]);

        assert_eq!(sut.len(), 2);
        assert!(!sut.is_empty());
        assert_eq!(sut.as_slice(), [(); 2]);
    }

    #[test]
    fn test_drain_full_range_zst_removes_all_items() {
        let mut sut = CapVec::<_, 8>::new();
        let mut leftover = sut.extend([(); 8]);
        assert_eq!(leftover.next(), None);

        assert_eq!(sut.len(), 8);
        assert!(!sut.is_empty());
        assert_eq!(sut, [(); 8]);

        let iter = sut.drain(0..8);
        assert_eq!(iter.collect::<Vec<_>>(), [(); 8]);

        assert_eq!(sut.len(), 0);
        assert!(sut.is_empty());
        assert_eq!(sut.as_slice(), []);
    }

    #[test]
    fn test_iter_empty_vector_yields_none() {
        let base = CapVec::<i32, 4>::new();
        let mut sut = base.iter();
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.next(), None);
        assert_eq!(sut.clone().count(), 0);
    }

    #[test]
    fn test_iter_forward_iteration() {
        let mut base = CapVec::<i32, 5>::new();
        base.extend([10, 20, 30]);

        let mut sut = base.iter();
        assert_eq!(sut.next(), Some(&10));
        assert_eq!(sut.next(), Some(&20));
        assert_eq!(sut.next(), Some(&30));
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_iter_clone_preserves_position() {
        let base = CapVec::<i32, 3>::from([1, 2, 3]);
        let mut sut1 = base.iter();
        let mut sut2 = sut1.clone();
        assert_eq!(sut1.next(), Some(&1));
        assert_eq!(sut2.next(), Some(&1));
        assert_eq!(sut1.next(), Some(&2));
        assert_eq!(sut2.next(), Some(&2));
        assert_eq!(sut1.next(), Some(&3));
        assert_eq!(sut2.next(), Some(&3));
        assert_eq!(sut1.next(), None);
        assert_eq!(sut2.next(), None);
    }

    #[test]
    fn test_iter_collects_items_in_order() {
        let base = CapVec::<u8, 4>::from([5, 6, 7, 8]);
        let collected: Vec<_> = base.iter().copied().collect();
        assert_eq!(collected, [5, 6, 7, 8]);

        assert!(base.iter().eq([5, 6, 7, 8].iter()));
    }

    #[test]
    fn test_iter_double_ended_iteration() {
        let base = CapVec::<i32, 4>::from([1, 2, 3, 4]);
        let mut sut = base.iter();

        assert_eq!(sut.next_back(), Some(&4));
        assert_eq!(sut.next(), Some(&1));
        assert_eq!(sut.next_back(), Some(&3));
        assert_eq!(sut.next(), Some(&2));
        assert_eq!(sut.next_back(), None);
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_iter_fused_behavior() {
        let base = CapVec::<i32, 3>::from([9, 8, 7]);
        let mut sut = base.iter();
        for _ in 0..3 {
            sut.next();
        }
        assert_eq!(sut.next(), None);
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_iter_len_tracks_remaining_items() {
        let base = CapVec::<i32, 4>::from([10, 20, 30, 40]);
        let mut sut = base.iter();
        assert_eq!(sut.len(), 4);
        assert_eq!(sut.next(), Some(&10));
        assert_eq!(sut.len(), 3);
        assert_eq!(sut.next_back(), Some(&40));
        assert_eq!(sut.len(), 2);
        assert_eq!(sut.next(), Some(&20));
        assert_eq!(sut.len(), 1);
        assert_eq!(sut.next_back(), Some(&30));
        assert_eq!(sut.len(), 0);
    }

    #[test]
    fn test_iter_mut_empty_vector_yields_none() {
        let mut base = CapVec::<i32, 4>::new();
        let mut sut = base.iter_mut();
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.next(), None);
        assert_eq!(sut.next_back(), None);
    }

    #[test]
    fn test_iter_mut_forward_iteration_allows_mutation() {
        let mut base = CapVec::<i32, 5>::new();
        base.extend([1, 2, 3]);

        for x in base.iter_mut() {
            *x *= 10;
        }
        assert_eq!(base.as_slice(), &[10, 20, 30]);
    }

    #[test]
    fn test_iter_mut_double_ended_iteration() {
        let mut base = CapVec::<i32, 4>::from([1, 2, 3, 4]);
        let mut sut = base.iter_mut();
        assert_eq!(sut.next_back().map(|x| *x), Some(4));
        assert_eq!(sut.next().map(|x| *x), Some(1));
        assert_eq!(sut.next_back().map(|x| *x), Some(3));
        assert_eq!(sut.next().map(|x| *x), Some(2));
        assert_eq!(sut.next_back(), None);
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_iter_mut_backward_iteration_allows_mutation() {
        let mut base = CapVec::<i32, 5>::new();
        base.extend([1, 2, 3]);

        for x in base.iter_mut().rev() {
            *x *= 10;
        }
        assert_eq!(base.as_slice(), &[10, 20, 30]);
    }

    #[test]
    fn test_iter_mut_double_ended_iteration_allows_mutation() {
        let mut base = CapVec::<i32, 4>::from([1, 2, 3, 4]);
        let mut sut = base.iter_mut();

        if let Some(front) = sut.next() {
            *front *= 2;
        }

        if let Some(back) = sut.next_back() {
            *back *= 3;
        }

        assert_eq!(base.as_slice(), &[2, 2, 3, 12]);
    }

    #[test]
    fn test_iter_mut_matches_slice_iter_mut() {
        let mut base = CapVec::<u8, 4>::from([5, 6, 7, 8]);
        let mut v = [5, 6, 7, 8].to_vec();

        for (b, w) in base.iter_mut().zip(v.iter_mut()) {
            *b += 1;
            *w += 1;
        }

        assert_eq!(base.as_slice(), v.as_slice());
    }

    #[test]
    fn test_iter_mut_len_tracks_remaining_items() {
        let mut base = CapVec::<i32, 4>::from([10, 20, 30, 40]);
        let mut sut = base.iter_mut();
        assert_eq!(sut.len(), 4);
        assert_eq!(sut.next(), Some(&mut 10));
        assert_eq!(sut.len(), 3);
        assert_eq!(sut.next_back(), Some(&mut 40));
        assert_eq!(sut.len(), 2);
        assert_eq!(sut.next(), Some(&mut 20));
        assert_eq!(sut.len(), 1);
        assert_eq!(sut.next_back(), Some(&mut 30));
        assert_eq!(sut.len(), 0);
    }

    #[test]
    fn test_iter_mut_fused_behavior() {
        let mut base = CapVec::<i32, 3>::from([9, 8, 7]);
        let mut sut = base.iter_mut();

        for _ in 0..3 {
            sut.next();
        }

        assert_eq!(sut.next(), None);
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_into_iter_empty_vector_yields_none() {
        let base = CapVec::<i32, 4>::new();
        let mut sut = base.into_iter();

        assert_eq!(sut.len(), 0);
        assert_eq!(sut.next(), None);
        assert_eq!(sut.next_back(), None);
    }

    #[test]
    fn test_into_iter_forward_iteration() {
        let mut base = CapVec::<i32, 5>::new();
        base.extend([1, 2, 3]);

        let mut sut = base.into_iter();
        assert_eq!(sut.next(), Some(1));
        assert_eq!(sut.next(), Some(2));
        assert_eq!(sut.next(), Some(3));
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_into_iter_double_ended_iteration() {
        let base = CapVec::<i32, 4>::from([10, 20, 30, 40]);

        let mut sut = base.into_iter();
        assert_eq!(sut.next_back(), Some(40));
        assert_eq!(sut.next(), Some(10));
        assert_eq!(sut.next_back(), Some(30));
        assert_eq!(sut.next(), Some(20));
        assert_eq!(sut.next_back(), None);
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_into_iter_next_back_on_partially_filled_vector() {
        let mut base = CapVec::<i32, 5>::new();
        base.extend([1, 2, 3]);

        let mut sut = base.into_iter();
        assert_eq!(sut.len(), 3);
        assert_eq!(sut.next_back(), Some(3));
        assert_eq!(sut.next_back(), Some(2));
        assert_eq!(sut.next_back(), Some(1));
        assert_eq!(sut.next_back(), None);
    }

    #[test]
    fn test_into_iter_as_slice_tracks_remaining_items() {
        let base = CapVec::from([1, 2, 3, 4]);
        let mut sut = base.into_iter();

        assert_eq!(sut.as_slice(), &[1, 2, 3, 4]);
        assert_eq!(sut.next(), Some(1));
        assert_eq!(sut.as_slice(), &[2, 3, 4]);
        assert_eq!(sut.next_back(), Some(4));
        assert_eq!(sut.as_slice(), &[2, 3]);
    }

    #[test]
    fn test_into_iter_as_mut_slice_allows_mutating_remaining_items() {
        let base = CapVec::from([1, 2, 3, 4]);
        let mut sut = base.into_iter();

        assert_eq!(sut.next(), Some(1));
        sut.as_mut_slice()
            .iter_mut()
            .for_each(|element| *element *= 10);

        assert_eq!(sut.collect::<Vec<_>>(), [20, 30, 40]);
    }

    #[test]
    fn test_into_iter_clone_preserves_remaining_items() {
        let base = CapVec::from([1, 2, 3, 4]);
        let mut sut = base.into_iter();
        assert_eq!(sut.next(), Some(1));
        assert_eq!(sut.next_back(), Some(4));

        let clone = sut.clone();

        assert_eq!(sut.collect::<Vec<_>>(), [2, 3]);
        assert_eq!(clone.collect::<Vec<_>>(), [2, 3]);
    }

    #[test]
    fn test_into_iter_clone_drops_initialized_elements_when_later_clone_panics() {
        struct PanicOnSecondClone {
            alive: Rc<Cell<usize>>,
            clone_calls: Rc<Cell<usize>>,
        }

        impl PanicOnSecondClone {
            fn new(alive: Rc<Cell<usize>>, clone_calls: Rc<Cell<usize>>) -> Self {
                alive.set(alive.get() + 1);
                Self { alive, clone_calls }
            }
        }

        impl Clone for PanicOnSecondClone {
            fn clone(&self) -> Self {
                let clone_calls = self.clone_calls.get() + 1;
                self.clone_calls.set(clone_calls);

                if clone_calls == 2 {
                    panic!("intentional into_iter clone panic");
                }

                self.alive.set(self.alive.get() + 1);
                Self {
                    alive: Rc::clone(&self.alive),
                    clone_calls: Rc::clone(&self.clone_calls),
                }
            }
        }

        impl Drop for PanicOnSecondClone {
            fn drop(&mut self) {
                self.alive.set(self.alive.get() - 1);
            }
        }

        let alive = Rc::new(Cell::new(0));
        let clone_calls = Rc::new(Cell::new(0));
        let base = CapVec::<_, 2>::from([
            PanicOnSecondClone::new(Rc::clone(&alive), Rc::clone(&clone_calls)),
            PanicOnSecondClone::new(Rc::clone(&alive), Rc::clone(&clone_calls)),
        ])
        .into_iter();

        let result = catch_unwind(AssertUnwindSafe(|| {
            let _ = base.clone();
        }));

        assert!(result.is_err());
        assert_eq!(alive.get(), 2);
    }

    #[test]
    fn test_into_iter_debug_formats_empty_and_remaining_items() {
        let base = CapVec::from([1, 2, 3, 4]);
        let mut sut = base.into_iter();

        assert_eq!(format!("{sut:?}"), "IntoIter([1, 2, 3, 4])");
        assert_eq!(sut.next(), Some(1));
        assert_eq!(sut.next_back(), Some(4));
        assert_eq!(format!("{sut:?}"), "IntoIter([2, 3])");

        while sut.next().is_some() {}
        assert_eq!(format!("{sut:?}"), "IntoIter([])");
    }

    #[test]
    fn test_into_iter_nth_drops_skipped_items() {
        let dropped = Rc::new(Cell::new(0));
        let base = CapVec::<_, 4>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
        ]);

        let mut sut = base.into_iter();
        let item = sut.nth(2).unwrap();

        assert_eq!(dropped.get(), 2);
        assert_eq!(item.id, 2);

        drop(item);
        assert_eq!(dropped.get(), 3);

        drop(sut);
        assert_eq!(dropped.get(), 4);
    }

    #[test]
    fn test_into_iter_nth_back_drops_skipped_items() {
        let dropped = Rc::new(Cell::new(0));
        let base = CapVec::<_, 4>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
        ]);

        let mut sut = base.into_iter();
        let item = sut.nth_back(2).unwrap();

        assert_eq!(dropped.get(), 2);
        assert_eq!(item.id, 1);

        drop(item);
        assert_eq!(dropped.get(), 3);

        drop(sut);
        assert_eq!(dropped.get(), 4);
    }

    #[test]
    fn test_into_iter_last_drops_skipped_items() {
        let dropped = Rc::new(Cell::new(0));
        let base = CapVec::<_, 4>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
        ]);

        let item = base.into_iter().last().unwrap();

        assert_eq!(dropped.get(), 3);
        assert_eq!(item.id, 3);

        drop(item);
        assert_eq!(dropped.get(), 4);
    }

    #[test]
    fn test_into_iter_count_drops_remaining_items() {
        let dropped = Rc::new(Cell::new(0));
        let base = CapVec::<_, 4>::from([
            drop_counter(0, &dropped),
            drop_counter(1, &dropped),
            drop_counter(2, &dropped),
            drop_counter(3, &dropped),
        ]);

        assert_eq!(base.into_iter().count(), 4);
        assert_eq!(dropped.get(), 4);
    }

    #[test]
    fn test_into_iter_collects_items_in_order() {
        let base = CapVec::<u8, 4>::from([5, 6, 7, 8]);
        let collected: Vec<_> = base.into_iter().collect();
        assert_eq!(collected, [5, 6, 7, 8]);
    }

    #[test]
    fn test_into_iter_matches_vec_into_iter() {
        let base = CapVec::<i32, 4>::from([1, 2, 3, 4]);
        let v = [1, 2, 3, 4].to_vec();

        assert_eq!(base.into_iter().collect::<Vec<_>>(), v);
    }

    #[test]
    fn test_into_iter_len_tracks_remaining_items() {
        let base = CapVec::<i32, 4>::from([10, 20, 30, 40]);
        let mut sut = base.into_iter();
        assert_eq!(sut.len(), 4);
        assert_eq!(sut.next(), Some(10));
        assert_eq!(sut.len(), 3);
        assert_eq!(sut.next_back(), Some(40));
        assert_eq!(sut.len(), 2);
        assert_eq!(sut.next(), Some(20));
        assert_eq!(sut.len(), 1);
        assert_eq!(sut.next_back(), Some(30));
        assert_eq!(sut.len(), 0);
    }

    #[test]
    fn test_into_iter_fused_behavior() {
        let base = CapVec::<i32, 3>::from([1, 2, 3]);
        let mut sut = base.into_iter();

        for _ in 0..3 {
            sut.next();
        }

        assert_eq!(sut.next(), None);
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_into_iter_double_ended_iteration_updates_len() {
        let base = CapVec::<i32, 5>::from([1, 2, 3, 4, 5]);
        let mut sut = base.into_iter();

        assert_eq!(sut.len(), 5);
        assert_eq!(sut.next(), Some(1));
        assert_eq!(sut.len(), 4);
        assert_eq!(sut.next_back(), Some(5));
        assert_eq!(sut.len(), 3);
        assert_eq!(sut.next(), Some(2));
        assert_eq!(sut.len(), 2);
        assert_eq!(sut.next_back(), Some(4));
        assert_eq!(sut.len(), 1);
        assert_eq!(sut.next(), Some(3));
        assert_eq!(sut.len(), 0);
        assert_eq!(sut.next(), None);
    }

    #[test]
    fn test_into_iter_drop_drops_remaining_elements() {
        let base = CapVec::<Box<str>, 4>::from(["a", "b", "c", "d"].map(Box::from));

        let mut sut = base.into_iter();
        assert_eq!(sut.next().as_deref(), Some("a"));
        assert_eq!(sut.next_back().as_deref(), Some("d"));

        core::mem::drop(sut);
    }

    #[test]
    fn test_into_iter_drops_remaining_elements_when_drop_panics() {
        struct PanicOnDrop {
            id: usize,
            alive: Rc<Cell<usize>>,
            has_panicked: Rc<Cell<bool>>,
        }

        impl PanicOnDrop {
            fn new(id: usize, alive: Rc<Cell<usize>>, has_panicked: Rc<Cell<bool>>) -> Self {
                alive.set(alive.get() + 1);
                Self {
                    id,
                    alive,
                    has_panicked,
                }
            }
        }

        impl Drop for PanicOnDrop {
            fn drop(&mut self) {
                self.alive.set(self.alive.get() - 1);

                if self.id == 0 && !self.has_panicked.replace(true) {
                    panic!("intentional into_iter drop panic");
                }
            }
        }

        let alive = Rc::new(Cell::new(0));
        let has_panicked = Rc::new(Cell::new(false));
        let base = CapVec::<_, 3>::from([
            PanicOnDrop::new(0, Rc::clone(&alive), Rc::clone(&has_panicked)),
            PanicOnDrop::new(1, Rc::clone(&alive), Rc::clone(&has_panicked)),
            PanicOnDrop::new(2, Rc::clone(&alive), Rc::clone(&has_panicked)),
        ]);

        let result = catch_unwind(AssertUnwindSafe(|| {
            drop(base.into_iter());
        }));

        assert!(result.is_err());
        assert_eq!(alive.get(), 0);
    }

    #[test]
    fn test_ref_into_iter_matches_iter() {
        let base = CapVec::from([0, 1, 2, 3]);
        assert!(base.iter().eq(&base));

        let base = CapVec::from([0; 0]);
        assert!(base.iter().eq(&base));

        let base = CapVec::from([(); 0]);
        assert!(base.iter().eq(&base));

        let base = CapVec::from([(); 5]);
        assert!(base.iter().eq(&base));
    }

    #[test]
    fn test_ref_mut_into_iter_matches_iter_mut() {
        let mut base = CapVec::from([0, 1, 2, 3]);
        assert!([0, 1, 2, 3].iter_mut().eq(&mut base));

        let mut base = CapVec::from([0; 0]);
        assert!([0; 0].iter_mut().eq(&mut base));

        let mut base = CapVec::from([(); 0]);
        assert!([(); 0].iter_mut().eq(&mut base));

        let mut base = CapVec::from([(); 5]);
        assert!([(); 5].iter_mut().eq(&mut base));
    }
}