fastvec 2.0.0

use alloc::alloc as malloc;
use alloc::boxed::Box;
use alloc::vec::Vec;
use core::alloc::Layout;
use core::cell::Cell;
use core::fmt::Debug;
use core::iter::FusedIterator;
use core::marker::PhantomData;
use core::mem::{ManuallyDrop, MaybeUninit};
use core::num::NonZeroUsize;
use core::panic::{RefUnwindSafe, UnwindSafe};
use core::ptr::NonNull;
use core::{ptr, slice};

use crate::utils::min_cap;

use super::utils::{IsZST, split_range_bound};

const MAX_CAP: usize = usize::MAX >> 1;
const MARKER: usize = usize::MAX ^ MAX_CAP;

// -----------------------------------------------------------------------------
// FastVecData

/// A type used to manipulate internal data of [`FastVec`].
///
/// This type may contain self-references. After moves, the pointer must be refreshed to remain valid,
/// so [`FastVecData::refresh`] should run before each method to ensure correctness.
///
/// Calling `refresh` adds a branch and assignment, and it is unsafe to require callers to do it manually.
///
/// Instead, all constructors are hidden behind the [`FastVec`] wrapper.
/// Use [`FastVec::data`] to obtain [`&FastVecData`](FastVecData);
/// these entry points refresh automatically.
///
/// During the reference's lifetime the data will not move, so subsequent operations are safe.
///
/// # Examples
///
/// ```
/// # use fastvec::{FastVec, fast::FastVecData};
/// let mut state: FastVec<i32, 8> = [1, 2, 3, 4].into();
/// let vec = state.data();
///
/// vec.push(5);
/// vec.push(6);
/// assert_eq!(vec, &[1, 2, 3,  4, 5, 6]);
/// ```
///
/// Almost all methods supported by [`alloc::vec::Vec`] can be used in [`FastVecData`],
/// As long as its input is a reference to vector self.
///
/// ```
/// # use fastvec::FastVec;
/// let mut state: FastVec<i32, 8> = [1, 2, 3, 4].into();
/// let vec = state.data();
///
/// assert_eq!(vec.capacity(), 8);
/// assert_eq!(vec.len(), 4);
///
/// vec.insert(0, 0);
/// vec.retain(|v| *v % 2 == 0);
///
/// assert_eq!(vec, &[0, 2, 4]);
/// ```
///
/// # Internal Requirements
///
/// These requirements are guaranteed by the implementation; users typically do not need to consider them.
///
/// 1. This type cannot be constructed directly; obtain references via [`FastVec`].
/// 2. Calling any method (except `len`, `capacity`, and `in_stack`) requires the internal pointer to be valid; this is
///    usually guaranteed by obtaining a handle with [`FastVec::data`].
/// 3. Heap allocation is allowed even when `capacity <= N`.
/// 4. If resources are allocated on the heap and `T` is not ZST, the capacity must be non-zero.
///
pub struct FastVecData<T, const N: usize> {
    /// We need to use [`Cell`] or [`UnsafeCell`](core::cell::UnsafeCell) to implement internal variability,
    /// When self implemented, [`refresh`](FastVecData::refresh) may be considered useless and optimized.
    ptr: Cell<*mut T>,
    // The highest bit stores the location flag: 1 means cache, 0 means heap.
    // The remaining bits store capacity.
    cap_and_flag: usize,
    len: usize,
    cache: [MaybeUninit<T>; N],
}

// -----------------------------------------------------------------------------
// Marker

unsafe impl<T: Sync, const N: usize> Send for FastVecData<T, N> {}
unsafe impl<T: Send, const N: usize> Sync for FastVecData<T, N> {}
impl<T, const N: usize> UnwindSafe for FastVecData<T, N> where T: UnwindSafe {}
impl<T, const N: usize> RefUnwindSafe for FastVecData<T, N> where T: RefUnwindSafe {}

// -----------------------------------------------------------------------------
// Basic

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

impl<T, const N: usize> FastVecData<T, N> {
    #[inline(always)]
    const fn cache_ptr(&self) -> *const T {
        &self.cache as *const [MaybeUninit<T>] as *const T
    }

    #[inline(always)]
    const fn in_heap(&self) -> bool {
        self.cap_and_flag & MARKER == 0
    }

    /// Refresh the ptr to ensure its validity.
    ///
    /// This will be automatically called by [`FastVec`],
    /// and users usually do not need to use it.
    ///
    /// Currently, we use [`Cell`] to achieve internal variability,
    /// so this is not multi-threaded safe. But the [`FastVecData`]
    /// reference generated by [`FastVec`] is already the pointer correct,
    /// which can be safely passed across threads.
    ///
    /// # Safety
    /// - Single threaded safety.
    /// - Multi-threaded ?
    #[inline(always)]
    pub unsafe fn refresh(&self) {
        // For zero size types, this function has no overhead.
        if !T::IS_ZST && !self.in_heap() {
            self.ptr.set(self.cache_ptr() as *mut T);
        }
    }

    /// Returns current capacity.
    ///
    /// Before spilling to heap this equals `N`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::new();
    /// let data = vec.data();
    ///
    /// assert_eq!(data.capacity(), 2);
    /// data.extend([1, 2, 3]);
    /// assert!(data.capacity() >= 3);
    /// ```
    #[inline(always)]
    pub const fn capacity(&self) -> usize {
        self.cap_and_flag & MAX_CAP
    }

    /// Returns the number of initialized elements in the vector.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::new();
    /// let data = vec.data();
    ///
    /// assert_eq!(data.len(), 0);
    /// data.push(1);
    /// assert_eq!(data.len(), 1);
    /// ```
    #[inline(always)]
    pub const fn len(&self) -> usize {
        self.len
    }

    /// Returns `true` if the vector contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::new();
    /// let data = vec.data();
    ///
    /// assert!(data.is_empty());
    /// data.push(1);
    /// assert!(!data.is_empty());
    /// ```
    #[inline(always)]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns a raw pointer to the vector's buffer, or a dangling raw
    /// pointer valid for zero sized reads if the vector didn't allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::new();
    /// let data = vec.data();
    ///
    /// data.push(7);
    /// let ptr = data.as_ptr();
    /// assert_eq!(unsafe { *ptr }, 7);
    /// ```
    #[inline(always)]
    pub const fn as_ptr(&self) -> *const T {
        self.ptr.get()
    }

    /// Returns a raw mutable pointer to the vector's buffer, or a dangling
    /// raw pointer valid for zero sized reads if the vector didn't allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::from([1, 2]);
    /// let data = vec.data();
    ///
    /// let ptr = data.as_mut_ptr();
    /// unsafe { *ptr.add(1) = 9; }
    /// assert_eq!(data.as_slice(), &[1, 9]);
    /// ```
    #[inline(always)]
    pub const fn as_mut_ptr(&mut self) -> *mut T {
        self.ptr.get()
    }

    /// Extracts a slice containing the entire vector.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 4> = [1, 2, 3].into();
    /// let data = vec.data();
    ///
    /// assert_eq!(data.as_slice(), &[1, 2, 3]);
    /// ```
    #[inline]
    pub const fn as_slice(&self) -> &[T] {
        let data = self.as_ptr();
        let len = self.len();
        unsafe { slice::from_raw_parts(data, len) }
    }

    /// Extracts a mutable slice of the entire vector.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 4> = [1, 2, 3].into();
    /// let data = vec.data();
    ///
    /// data.as_mut_slice()[1] = 9;
    /// assert_eq!(data.as_slice(), &[1, 9, 3]);
    /// ```
    #[inline]
    pub const fn as_mut_slice(&mut self) -> &mut [T] {
        let data = self.as_mut_ptr();
        let len = self.len();
        unsafe { slice::from_raw_parts_mut(data, len) }
    }

    /// Forces the length of the vector to `new_len`.
    ///
    /// This is a low-level operation that does not initialize or drop elements.
    ///
    /// # Safety
    /// - `new_len <= capacity()`.
    /// - Elements in the range `old_len..new_len` must already be initialized.
    /// - Elements in the range `new_len..old_len` are considered logically removed
    ///   and will not be dropped by this call.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 4> = FastVec::new();
    /// let data = vec.data();
    ///
    /// unsafe {
    ///     let ptr = data.as_mut_ptr();
    ///     ptr.write(10);
    ///     ptr.add(1).write(20);
    ///     data.set_len(2);
    /// }
    /// assert_eq!(data.as_slice(), &[10, 20]);
    /// ```
    #[inline(always)]
    pub const unsafe fn set_len(&mut self, new_len: usize) {
        debug_assert!(new_len <= self.capacity());
        self.len = new_len;
    }

    /// Clears the vector, removing all values.
    ///
    /// Note that this method has no effect on allocated capacity.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 2> = [1, 2, 3].into();
    /// let data = vec.data();
    ///
    /// let cap = data.capacity();
    /// data.clear();
    /// assert!(data.is_empty());
    /// assert_eq!(data.capacity(), cap);
    /// ```
    pub fn clear(&mut self) {
        if core::mem::needs_drop::<T>() {
            unsafe {
                let slice: &mut [T] = self.as_mut_slice();
                ptr::drop_in_place::<[T]>(slice);
            }
        }
        self.len = 0;
    }

    /// Shortens the vector, keeping the first `len` elements
    /// and dropping the rest.
    ///
    /// If `len >= self.len()`, this has no effect.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 4> = [1, 2, 3, 4].into();
    /// let data = vec.data();
    ///
    /// data.truncate(2);
    /// assert_eq!(data.as_slice(), &[1, 2]);
    /// ```
    pub fn truncate(&mut self, len: usize) {
        if self.len > len {
            if core::mem::needs_drop::<T>() {
                unsafe {
                    let data = self.as_mut_ptr().add(len);
                    let len = self.len - len;
                    let to_drop = ptr::slice_from_raw_parts_mut(data, len);
                    ptr::drop_in_place::<[T]>(to_drop)
                }
            }

            self.len = len;
        }
    }
}

// -----------------------------------------------------------------------------
// Memory

impl<T, const N: usize> FastVecData<T, N> {
    #[inline(never)]
    fn realloc(&mut self, new_cap: usize) {
        let len = self.len();
        let old_cap = self.capacity();

        debug_assert!(new_cap >= len);
        assert!(
            new_cap <= MAX_CAP,
            "the capacity of FastVec cannot exceed isize::MAX"
        );

        if new_cap <= N {
            debug_assert!(self.in_heap());
            if !T::IS_ZST {
                let ptr = self.as_mut_ptr();
                let old_layout = Layout::array::<T>(old_cap).unwrap();
                self.len = 0; // Ensure the safety during panic
                unsafe {
                    let dst = self.cache.as_mut_ptr() as *mut T;
                    ptr::copy_nonoverlapping::<T>(ptr, dst, len);
                    malloc::dealloc(ptr as *mut u8, old_layout);
                    self.ptr.set(dst);
                }
            }
            self.cap_and_flag = N | MARKER;
            self.len = len;
        } else if self.in_heap() {
            let mut ptr = self.as_mut_ptr();

            if !T::IS_ZST {
                let old_layout = Layout::array::<T>(old_cap).unwrap();
                let new_layout = Layout::array::<T>(new_cap).unwrap();
                let new_size = new_layout.size();
                let raw_ptr = ptr as *mut u8;
                unsafe {
                    ptr = NonNull::new(malloc::realloc(raw_ptr, old_layout, new_size) as *mut T)
                        .unwrap_or_else(|| malloc::handle_alloc_error(new_layout))
                        .as_ptr();
                }
            }
            self.ptr.set(ptr);
            self.cap_and_flag = new_cap;
        } else {
            let ptr: NonNull<T> = if !T::IS_ZST {
                let layout = Layout::array::<T>(new_cap).unwrap();
                NonNull::new(unsafe { malloc::alloc(layout) as *mut T })
                    .unwrap_or_else(|| malloc::handle_alloc_error(layout))
            } else {
                let align = ::core::mem::align_of::<T>();
                debug_assert!(align != 0);
                NonNull::<T>::without_provenance(unsafe { NonZeroUsize::new_unchecked(align) })
            };

            if !T::IS_ZST {
                unsafe {
                    let src = self.cache.as_ptr() as *const T;
                    ptr::copy_nonoverlapping::<T>(src, ptr.as_ptr(), len);
                }
            }

            self.ptr.set(ptr.as_ptr());
            self.cap_and_flag = new_cap;
        }
    }

    fn dealloc(&mut self) {
        if !T::IS_ZST && self.in_heap() {
            let ptr = self.as_mut_ptr();
            let cap = self.capacity();

            let layout = Layout::array::<T>(cap).unwrap();
            unsafe {
                malloc::dealloc(ptr as *mut u8, layout);
            }
        }
    }
}

impl<T, const N: usize> FastVecData<T, N> {
    /// Constructs a new, empty `SmallVec<T>`.
    #[must_use]
    #[inline(always)]
    const fn new() -> Self {
        assert!(
            N <= MAX_CAP,
            "the capacity of FastVecData cannot exceed `isize::MAX`"
        );

        unsafe {
            Self {
                cache: MaybeUninit::<[MaybeUninit<T>; N]>::uninit().assume_init(),
                ptr: Cell::new(ptr::without_provenance_mut(align_of::<T>())),
                len: 0,
                cap_and_flag: N | MARKER,
            }
        }
    }

    /// Create an empty [`FastVecData`] with the specified capacity.
    #[inline]
    #[must_use]
    fn with_capacity(capacity: usize) -> Self {
        assert!(
            N <= MAX_CAP,
            "the capacity of FastVecData cannot exceed `isize::MAX`"
        );
        let mut this = Self::new();
        if capacity > N {
            this.realloc(capacity);
        }
        this
    }

    /// # Safety
    /// - if T is not zero sized type, capacity > 0.
    /// - Using [`FastVec`] to wrap the returned [`FastVecData`],
    /// - or manually call [`FastVecData::refresh`] before any method call.
    /// - See [`Vec::from_raw_parts`]
    #[inline]
    const unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
        assert!(
            N <= MAX_CAP,
            "the capacity of FastVecData cannot exceed `isize::MAX`"
        );
        debug_assert!(length <= capacity && capacity <= MAX_CAP);

        unsafe {
            Self {
                cache: MaybeUninit::<[MaybeUninit<T>; N]>::uninit().assume_init(),
                ptr: Cell::new(ptr),
                len: length,
                cap_and_flag: capacity,
            }
        }
    }

    /// Creates a `FastVecData` by copying all elements from a slice.
    #[inline]
    fn from_slice(slice: &[T]) -> Self
    where
        T: Copy,
    {
        let mut this = Self::with_capacity(slice.len());
        unsafe {
            if !T::IS_ZST {
                let ptr = this.as_mut_ptr();
                ptr::copy_nonoverlapping(slice.as_ptr(), ptr, slice.len());
            }
            this.set_len(slice.len());
        }
        this
    }

    /// Reserves capacity for at least `additional`
    /// more elements to be inserted in the given `FastVec<T>`.
    ///
    /// This may reserve more than requested to reduce future reallocations.
    ///
    /// # Panics
    /// Panics if the new capacity exceeds `isize::MAX`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::new();
    /// let data = vec.data();
    ///
    /// data.reserve(10);
    /// assert!(data.capacity() >= 10);
    /// ```
    pub fn reserve(&mut self, additional: usize) {
        let cap = self.capacity();
        let len = self.len();
        let target = len.saturating_add(additional);
        if target > cap {
            self.realloc(min_cap::<T>().max(target).min(MARKER).next_power_of_two());
        }
    }

    /// Reserves the minimum capacity for exactly `additional` more elements.
    ///
    /// Unlike [`reserve`](Self::reserve), this does not intentionally over-allocate.
    ///
    /// # Panics
    /// Panics if the new capacity exceeds `isize::MAX`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::new();
    /// let data = vec.data();
    ///
    /// data.reserve_exact(5);
    /// assert!(data.capacity() >= 5);
    /// ```
    pub fn reserve_exact(&mut self, additional: usize) {
        let cap = self.capacity();
        let len = self.len();
        let target = len.saturating_add(additional);
        if target > cap {
            self.realloc(target);
        }
    }

    /// Shrinks the capacity of the vector as much as possible.
    ///
    /// If `len <= N`, data may move back to inline storage.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::with_capacity(16);
    /// let data = vec.data();
    ///
    /// data.extend([1, 2, 3]);
    /// data.shrink_to_fit();
    /// assert!(data.capacity() >= data.len());
    /// ```
    pub fn shrink_to_fit(&mut self) {
        if self.in_heap() {
            let len = self.len();
            let cap = self.capacity();
            if cap > len {
                self.realloc(len);
            }
        }
    }

    /// Shrinks the capacity of the vector as much as possible.
    ///
    /// The resulting capacity will be at least `max(self.len(), min_capacity)`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::with_capacity(16);
    /// let data = vec.data();
    ///
    /// data.extend([1, 2, 3]);
    /// data.shrink_to(4);
    /// assert!(data.capacity() >= 4);
    /// ```
    pub fn shrink_to(&mut self, min_capacity: usize) {
        if self.in_heap() {
            let len = self.len();
            let cap = self.capacity();
            if min_capacity >= len && min_capacity < cap {
                self.realloc(min_capacity);
            }
        }
    }

    /// Converts the `FastVec` into `Vec<T>`.
    #[inline]
    fn into_vec(self) -> Vec<T> {
        if self.in_heap() {
            let ptr = self.ptr.get();
            let cap = self.cap_and_flag;
            let len = self.len;
            ::core::mem::forget(self);
            unsafe { Vec::from_raw_parts(ptr, len, cap) }
        } else {
            let len = self.len;
            let mut ret = Vec::<T>::with_capacity(len);
            unsafe {
                if !T::IS_ZST {
                    let src = self.cache.as_ptr() as *const T;
                    let dst = ret.as_mut_ptr();
                    ptr::copy_nonoverlapping(src, dst, len);
                }
                ::core::mem::forget(self);
                ret.set_len(len);
            }
            ret
        }
    }

    /// Appends an element to the back of a collection.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity exceeds `isize::MAX`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 2> = FastVec::new();
    /// let data = vec.data();
    ///
    /// data.push(1);
    /// data.push(2);
    /// data.push(3);
    /// assert_eq!(data.as_slice(), &[1, 2, 3]);
    /// ```
    #[inline(always)]
    pub fn push(&mut self, value: T) {
        if self.len == self.capacity() {
            crate::utils::cold_path();
            self.reserve(1);
        }

        unsafe {
            let ptr = self.as_mut_ptr();
            ptr::write(ptr.add(self.len), value);
            self.len += 1;
        }
    }

    /// Appends an element to the back of the vector without checking capacity.
    ///
    /// # Safety
    /// `self.len() < self.capacity()` must hold before calling this method.
    #[inline(always)]
    pub unsafe fn push_unchecked(&mut self, value: T) {
        unsafe {
            let ptr = self.as_mut_ptr();
            ptr::write(ptr.add(self.len), value);
            self.len += 1;
        }
    }

    /// Removes the last element and returns it, or `None` if empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 2> = [1, 2].into();
    /// let data = vec.data();
    ///
    /// assert_eq!(data.pop(), Some(2));
    /// assert_eq!(data.pop(), Some(1));
    /// assert_eq!(data.pop(), None);
    /// ```
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        if self.len != 0 {
            unsafe {
                self.len -= 1;
                Some(ptr::read(self.as_ptr().add(self.len)))
            }
        } else {
            crate::utils::cold_path();
            None
        }
    }

    /// Removes and returns the last element if `predicate` returns `true`.
    ///
    /// Returns `None` when the vector is empty or predicate returns `false`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 4> = [1, 2, 3, 4].into();
    /// let data = vec.data();
    ///
    /// assert_eq!(data.pop_if(|v| *v % 2 == 0), Some(4));
    /// assert_eq!(data.pop_if(|v| *v % 2 == 0), None);
    /// ```
    #[inline]
    pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
        let last = self.last_mut()?;
        if predicate(last) { self.pop() } else { None }
    }

    /// Inserts `element` at `index`, shifting all elements after it to the right.
    ///
    /// # Panics
    /// Panics if `index > len`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 2> = [1, 3].into();
    /// let data = vec.data();
    ///
    /// data.insert(1, 2);
    /// assert_eq!(data.as_slice(), &[1, 2, 3]);
    /// ```
    pub fn insert(&mut self, index: usize, element: T) {
        #[cold]
        #[inline(never)]
        fn assert_failed(index: usize, len: usize) -> ! {
            panic!("insertion index (is {index}) should be <= len (is {len})");
        }

        let len = self.len;
        if index > len {
            assert_failed(index, len);
        }

        // space for the new element
        if len == self.capacity() {
            crate::utils::cold_path();
            self.reserve(1);
        }

        unsafe {
            let p = self.as_mut_ptr().add(index);
            if index < len {
                ptr::copy(p, p.add(1), len - index);
            }
            ptr::write(p, element);
            self.len += 1;
        }
    }

    /// Removes and returns the element at `index`, shifting later elements left.
    ///
    /// # Panics
    /// Panics if `index >= len`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 4> = [10, 20, 30].into();
    /// let data = vec.data();
    ///
    /// assert_eq!(data.remove(1), 20);
    /// assert_eq!(data.as_slice(), &[10, 30]);
    /// ```
    pub fn remove(&mut self, index: usize) -> T {
        #[cold]
        #[inline(never)]
        fn assert_failed(index: usize, len: usize) -> ! {
            panic!("removal index (is {index}) should be < len (is {len})");
        }

        let len = self.len;
        if index >= len {
            assert_failed(index, len);
        }

        unsafe {
            let ptr = self.as_mut_ptr().add(index);
            let ret = ptr::read(ptr);
            ptr::copy(ptr.add(1), ptr, len - index - 1);
            self.len -= 1;
            ret
        }
    }

    /// Removes and returns the element at `index`.
    ///
    /// The last element is moved into `index`, so ordering is not preserved.
    ///
    /// # Panics
    /// Panics if `index >= len`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 4> = [10, 20, 30, 40].into();
    /// let data = vec.data();
    ///
    /// let removed = data.swap_remove(1);
    /// assert_eq!(removed, 20);
    /// assert_eq!(data.len(), 3);
    /// ```
    pub fn swap_remove(&mut self, index: usize) -> T {
        #[cold]
        #[inline(never)]
        fn assert_failed(index: usize, len: usize) -> ! {
            panic!("swap_remove index (is {index}) should be < len (is {len})");
        }

        let len = self.len;
        if index >= len {
            assert_failed(index, len);
        }

        unsafe {
            let ptr = self.as_mut_ptr();
            let value = ptr::read(ptr.add(index));
            ptr::copy(ptr.add(len - 1), ptr.add(index), 1);
            self.len -= 1;
            value
        }
    }

    /// Moves all elements from `other` to the end of `self`.
    ///
    /// `other` is emptied after the call.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut a: FastVec<_, 2> = [1, 2].into();
    /// let mut b: FastVec<_, 4> = [3, 4].into();
    /// let data_a = a.data();
    /// let data_b = b.data();
    ///
    /// data_a.append(data_b);
    /// assert!(data_b.is_empty());
    /// assert_eq!(data_a.as_slice(), &[1, 2, 3, 4]);
    /// ```
    pub fn append<const P: usize>(&mut self, other: &mut FastVecData<T, P>) {
        unsafe {
            let slice = other.as_slice();
            let count = slice.len();
            self.reserve(count);

            let len = self.len();
            let dst = self.as_mut_ptr().add(len);
            ptr::copy_nonoverlapping::<T>(slice.as_ptr(), dst, count);

            self.len += count;
            other.set_len(0);
        }
    }

    /// Resizes the vector to `new_len` using `f` to generate new values.
    ///
    /// If `new_len < len`, this truncates the vector.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 2> = [1].into();
    /// let data = vec.data();
    ///
    /// data.resize_with(4, || 7);
    /// assert_eq!(data.as_slice(), &[1, 7, 7, 7]);
    /// ```
    pub fn resize_with<F>(&mut self, new_len: usize, mut f: F)
    where
        F: FnMut() -> T,
    {
        let len = self.len();
        if new_len > len {
            self.reserve(new_len - len);
            let ptr = self.as_mut_ptr();
            (len..new_len).for_each(|idx| unsafe {
                ptr::write(ptr.add(idx), f());
            });
            unsafe {
                self.set_len(new_len);
            }
        } else {
            self.truncate(new_len);
        }
    }

    /// Retains only elements for which `f` returns `true`, passing each item mutably.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 4> = [1, 2, 3, 4].into();
    /// let data = vec.data();
    ///
    /// data.retain_mut(|v| {
    ///     *v *= 2;
    ///     *v > 4
    /// });
    /// assert_eq!(data.as_slice(), &[6, 8]);
    /// ```
    pub fn retain_mut<F: FnMut(&mut T) -> bool>(&mut self, mut f: F) {
        let base_ptr = self.as_mut_ptr();
        let len = self.len;
        self.len = 0; // Ensure safety if panicked
        let mut count = 0usize;

        for index in 0..len {
            unsafe {
                let dst = base_ptr.add(index);
                if f(&mut *dst) {
                    ptr::copy(dst, base_ptr.add(count), 1);
                    count += 1;
                } else {
                    ptr::drop_in_place(dst);
                }
            }
        }
        self.len = count;
    }

    /// Retains only elements for which `f` returns `true`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 4> = [1, 2, 3, 4].into();
    /// let data = vec.data();
    ///
    /// data.retain(|v| *v % 2 == 0);
    /// assert_eq!(data.as_slice(), &[2, 4]);
    /// ```
    #[inline]
    pub fn retain<F: FnMut(&T) -> bool>(&mut self, mut f: F) {
        self.retain_mut(|v| f(v));
    }

    /// Removes consecutive repeated elements according to `same_bucket`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 8> = [10, 20, 21, 30, 20].into();
    /// let data = vec.data();
    ///
    /// data.dedup_by(|a, b| *a / 10 == *b / 10);
    /// assert_eq!(data.as_slice(), &[10, 20, 30, 20]);
    /// ```
    pub fn dedup_by<F: FnMut(&mut T, &mut T) -> bool>(&mut self, mut same_bucket: F) {
        let len = self.len();
        if len <= 1 {
            return;
        }

        let ptr = self.as_mut_ptr();
        let mut left = 0usize;

        unsafe {
            let mut p_l = ptr.add(left);
            for right in 1..len {
                let p_r = ptr.add(right);
                if !same_bucket(&mut *p_r, &mut *p_l) {
                    left += 1;
                    p_l = ptr.add(left);
                    if right != left {
                        ptr::swap(p_r, p_l);
                    }
                }
            }
        }
        self.truncate(left + 1);
    }

    /// Removes consecutive repeated elements that map to the same key.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 8> = [10, 20, 21, 30, 20].into();
    /// let data = vec.data();
    ///
    /// data.dedup_by_key(|v| *v / 10);
    /// assert_eq!(data.as_slice(), &[10, 20, 30, 20]);
    /// ```
    #[inline]
    pub fn dedup_by_key<F, K>(&mut self, mut key: F)
    where
        F: FnMut(&mut T) -> K,
        K: PartialEq,
    {
        self.dedup_by(|a, b| key(a) == key(b));
    }

    /// Returns the remaining spare capacity as a slice of `MaybeUninit<T>`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use core::mem::MaybeUninit;
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 4> = FastVec::new();
    /// let data = vec.data();
    ///
    /// let spare: &mut [MaybeUninit<i32>] = data.spare_capacity_mut();
    /// spare[0].write(11);
    /// unsafe { data.set_len(1); }
    ///
    /// assert_eq!(data.as_slice(), &[11]);
    /// ```
    #[inline]
    pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
        let len = self.len();
        let cap = self.capacity();
        unsafe {
            let data = self.as_mut_ptr().add(len);
            slice::from_raw_parts_mut(data as *mut MaybeUninit<T>, cap - len)
        }
    }
}

// -----------------------------------------------------------------------------
// Common

super::utils::impl_common_traits!(FastVecData<T, N>);

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

impl<T: PartialEq, const N: usize> FastVecData<T, N> {
    /// Removes consecutive repeated elements using `PartialEq`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 8> = [1, 1, 2, 2, 3].into();
    /// let data = vec.data();
    ///
    /// data.dedup();
    /// assert_eq!(data.as_slice(), &[1, 2, 3]);
    /// ```
    #[inline]
    pub fn dedup(&mut self) {
        self.dedup_by(|x, y| PartialEq::eq(x, y));
    }
}

impl<T: Clone, const N: usize> FastVecData<T, N> {
    /// Resizes the vector to `new_len` by cloning `value` when growing.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 2> = [1, 2].into();
    /// let data = vec.data();
    ///
    /// data.resize(4, 9);
    /// assert_eq!(data.as_slice(), &[1, 2, 9, 9]);
    /// data.resize(1, 0);
    /// assert_eq!(data.as_slice(), &[1]);
    /// ```
    pub fn resize(&mut self, new_len: usize, value: T) {
        let len = self.len();

        if new_len > len {
            self.reserve(new_len - len);
            (len..new_len - 1).for_each(|_| unsafe {
                self.push_unchecked(value.clone());
            });
            unsafe {
                self.push_unchecked(value);
            }
        } else {
            self.truncate(new_len);
        }
    }

    /// Extends the vector by cloning all elements from `other`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<_, 2> = [1].into();
    /// let data = vec.data();
    ///
    /// data.extend_from_slice(&[2, 3, 4]);
    /// assert_eq!(data.as_slice(), &[1, 2, 3, 4]);
    /// ```
    pub fn extend_from_slice(&mut self, other: &[T]) {
        self.reserve(other.len());
        other.iter().for_each(|item| unsafe {
            self.push_unchecked(item.clone());
        });
    }
}

impl<'a, T: 'a + Clone + 'a, const N: usize> Extend<&'a T> for FastVecData<T, N> {
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        let iter = iter.into_iter();
        self.reserve(iter.size_hint().0);

        iter.for_each(|item| {
            self.push(item.clone());
        });
    }
}

impl<T, const N: usize> Extend<T> for FastVecData<T, N> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let iter = iter.into_iter();
        self.reserve(iter.size_hint().0);

        iter.for_each(|item| {
            self.push(item);
        });
    }
}

// -----------------------------------------------------------------------------
// Drain

/// An iterator that removes the items from a [`FastVecData`]
/// and yields them by value.
///
/// See [`FastVecData::drain`] .
pub struct Drain<'a, T: 'a, const N: usize> {
    tail_start: usize,
    tail_len: usize,
    iter: slice::Iter<'a, T>,
    vec: NonNull<FastVecData<T, N>>,
}

impl<T, const N: usize> FastVecData<T, N> {
    /// Removes the subslice indicated by the given range from the vector,
    /// returning a double-ended iterator over the removed subslice.
    ///
    /// If the iterator is dropped before being fully consumed, it drops the remaining removed elements.
    ///
    /// The returned iterator keeps a mutable borrow on the vector to optimize its implementation.
    ///
    /// See more information in [`Vec::drain`].
    ///
    /// # Panics
    ///
    /// Panics if the range is out of bounds.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut v = FastVec::<_, 3>::from([1, 2, 3]);
    /// let data = v.data();
    ///
    /// let u: Vec<_> = data.drain(1..).collect();
    /// assert_eq!(data, &[1]);
    /// assert_eq!(u, [2, 3]);
    ///
    /// // A full range clears the vector, like `clear()` does
    /// data.drain(..);
    /// assert_eq!(data.as_slice(), &[]);
    /// ```
    pub fn drain<R: core::ops::RangeBounds<usize>>(&mut self, range: R) -> Drain<'_, T, N> {
        let len = self.len();
        let (start, end) = split_range_bound(&range, len);

        unsafe {
            self.set_len(start);
            let data = self.as_ptr().add(start);
            let range_slice = slice::from_raw_parts(data, end - start);

            Drain {
                tail_start: end,
                tail_len: len - end,
                iter: range_slice.iter(),
                vec: NonNull::new_unchecked(self as *mut _),
            }
        }
    }
}

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

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

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.iter
            .next()
            .map(|reference| unsafe { ptr::read(reference) })
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

impl<T, const N: usize> DoubleEndedIterator for Drain<'_, T, N> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.iter
            .next_back()
            .map(|reference| unsafe { ptr::read(reference) })
    }
}

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

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

impl<'a, T: 'a, const N: usize> Drop for Drain<'a, T, N> {
    fn drop(&mut self) {
        /// Moves back the un-`Drain`ed elements to restore the original `Vec`.
        struct DropGuard<'r, 'a, T, const N: usize>(&'r mut Drain<'a, T, N>);

        impl<'r, 'a, T, const N: usize> Drop for DropGuard<'r, 'a, T, N> {
            fn drop(&mut self) {
                if self.0.tail_len > 0 {
                    unsafe {
                        let source_vec = self.0.vec.as_mut();
                        // memmove back untouched tail, update to new length
                        let start = source_vec.len();
                        let tail = self.0.tail_start;
                        if tail != start {
                            let base = source_vec.as_mut_ptr();
                            let src = base.add(tail);
                            let dst = base.add(start);
                            ptr::copy(src, dst, self.0.tail_len);
                        }
                        source_vec.set_len(start + self.0.tail_len);
                    }
                }
            }
        }

        let iter = core::mem::take(&mut self.iter);
        let drop_len = iter.len();

        let mut vec = self.vec;

        if T::IS_ZST {
            // ZSTs have no identity, so we don't need to move them around, we only need to drop the correct amount.
            // this can be achieved by manipulating the Vec length instead of moving values out from `iter`.
            unsafe {
                let vec = vec.as_mut();
                let old_len = vec.len();
                vec.set_len(old_len + drop_len + self.tail_len);
                vec.truncate(old_len + self.tail_len);
            }

            return;
        }

        // ensure elements are moved back into their appropriate places, even when drop_in_place panics
        let _guard = DropGuard(self);

        if drop_len == 0 {
            return;
        }

        // as_slice() must only be called when iter.len() is > 0 because
        // it also gets touched by vec::Splice which may turn it into a dangling pointer
        // which would make it and the vec pointer point to different allocations which would
        // lead to invalid pointer arithmetic below.
        let drop_ptr = iter.as_slice().as_ptr();

        unsafe {
            // drop_ptr comes from a slice::Iter which only gives us a &[T] but for drop_in_place
            // a pointer with mutable provenance is necessary. Therefore we must reconstruct
            // it from the original vec but also avoid creating a &mut to the front since that could
            // invalidate raw pointers to it which some unsafe code might rely on.
            let vec_ptr = vec.as_mut().as_mut_ptr();
            let drop_offset = drop_ptr.offset_from_unsigned(vec_ptr);
            let to_drop = ptr::slice_from_raw_parts_mut(vec_ptr.add(drop_offset), drop_len);
            ptr::drop_in_place(to_drop);
        }
    }
}

// -----------------------------------------------------------------------------
// ExtractIf

/// An iterator that removes elements matching a predicate from a range.
///
/// This yields removed items by value while compacting retained elements in place.
///
/// See [`FastVecData::extract_if`] .
pub struct ExtractIf<'a, T, F: FnMut(&mut T) -> bool, const N: usize> {
    vec: &'a mut FastVecData<T, N>,
    idx: usize,
    end: usize,
    del: usize,
    old_len: usize,
    pred: F,
}

impl<T, const N: usize> FastVecData<T, N> {
    /// Creates an iterator which uses a closure to determine
    /// if an element in the range should be removed.
    ///
    /// See more information in [`Vec::extract_if`].
    ///
    /// # Panics
    /// Panics if the range is out of bounds.
    ///
    ///
    /// # Examples
    ///
    /// Splitting a vector into even and odd values, reusing the original vector:
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut numbers = FastVec::<_, 5>::from([1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
    /// let data = numbers.data();
    ///
    /// let evens = data.extract_if(.., |x| *x % 2 == 0).collect::<FastVec<_, 10>>();
    /// let odds = numbers;
    ///
    /// assert_eq!(evens, [2, 4, 6, 8, 14]);
    /// assert_eq!(odds, [1, 3, 5, 9, 11, 13, 15]);
    /// ```
    ///
    /// Using the range argument to only process a part of the vector:
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut items = FastVec::<_, 5>::from([0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2]);
    /// let data = items.data();
    ///
    /// let ones = data.extract_if(7.., |x| *x == 1).collect::<Vec<_>>();
    /// assert_eq!(data, &[0, 0, 0, 0, 0, 0, 0, 2, 2, 2]);
    /// assert_eq!(ones.len(), 3);
    /// ```
    pub fn extract_if<F, R>(&mut self, range: R, filter: F) -> ExtractIf<'_, T, F, N>
    where
        F: FnMut(&mut T) -> bool,
        R: core::ops::RangeBounds<usize>,
    {
        let old_len = self.len();
        let (start, end) = split_range_bound(&range, old_len);

        // Guard against the vec getting leaked (leak amplification)
        unsafe {
            self.set_len(0);
        }

        ExtractIf {
            vec: self,
            idx: start,
            del: 0,
            end,
            old_len,
            pred: filter,
        }
    }
}

impl<T, F: FnMut(&mut T) -> bool, const N: usize> Iterator for ExtractIf<'_, T, F, N> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        while self.idx < self.end {
            let i = self.idx;
            // SAFETY:
            //  We know that `i < self.end` from the if guard and that `self.end <= self.old_len` from
            //  the validity of `Self`. Therefore `i` points to an element within `vec`.
            //
            //  Additionally, the i-th element is valid because each element is visited at most once
            //  and it is the first time we access vec[i].
            //
            //  Note: we can't use `vec.get_unchecked_mut(i)` here since the precondition for that
            //  function is that i < vec.len(), but we've set vec's length to zero.
            let cur = unsafe { &mut *self.vec.as_mut_ptr().add(i) };
            let drained = (self.pred)(cur);
            // Update the index *after* the predicate is called. If the index
            // is updated prior and the predicate panics, the element at this
            // index would be leaked.
            self.idx += 1;
            if drained {
                self.del += 1;
                // SAFETY: We never touch this element again after returning it.
                return Some(unsafe { ptr::read(cur) });
            } else if self.del > 0 {
                // SAFETY: `self.del` > 0, so the hole slot must not overlap with current element.
                // We use copy for move, and never touch this element again.
                unsafe {
                    let hole_slot = self.vec.as_mut_ptr().add(i - self.del);
                    ptr::copy_nonoverlapping(cur, hole_slot, 1);
                }
            }
        }
        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.end - self.idx))
    }
}

impl<T, F: FnMut(&mut T) -> bool, const N: usize> Drop for ExtractIf<'_, T, F, N> {
    fn drop(&mut self) {
        if !T::IS_ZST && self.del > 0 {
            // SAFETY: Trailing unchecked items must be valid since we never touch them.
            unsafe {
                let base = self.vec.as_mut_ptr();
                ptr::copy(
                    base.add(self.idx),
                    base.add(self.idx - self.del),
                    self.old_len - self.idx,
                );
            }
        }
        // SAFETY: After filling holes, all items are in contiguous memory.
        unsafe {
            self.vec.set_len(self.old_len - self.del);
        }
    }
}

impl<T: Debug, F: FnMut(&mut T) -> bool, const N: usize> Debug for ExtractIf<'_, T, F, N> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        let peek = if self.idx < self.end {
            self.vec.get(self.idx)
        } else {
            None
        };
        f.debug_struct("ExtractIf")
            .field("peek", &peek)
            .finish_non_exhaustive()
    }
}

// -----------------------------------------------------------------------------
// FastVec

/// An inline-buffer-prioritized vector that automatically spills to the heap
/// when capacity is exceeded.
///
/// Unlike [`SmallVec`](crate::SmallVec), [`FastVec`] uses  **pointer caching**
/// to avoid conditional checks on every operation, achieving higher performance.
///
/// When the data is in the inline buffer, the execution efficiency is
/// almost the same as `[T; N]`. Even if switching to the heap, it
/// won't be slower than [`Vec`].
///
/// But the cost is that this type is [`!Sync`](Sync) and requires
/// operate through [`FastVecData`].
///
/// So the real advantage of [`FastVec`] lies in data processing rather
/// than storage, and it is usually recommended to convert it to [`Vec`]
/// when transferring data.
///
/// If [`FastVec`]'s data is already in the heap, this conversion only
/// requires copying pointers, which is very cheap. If it is still inline,
/// it is equivalent to only applying for heap memory once, won't be more
/// expensive than using [`Vec`].
///
/// # Quick Start
///
/// ## Creating a FastVec
///
/// Creating a [`FastVec`] is similar to `SmallVec`:
///
/// ```
/// # use fastvec::FastVec;
/// let mut vec = FastVec::<i32, 8>::new();
/// assert_eq!(vec.capacity(), 8);
/// assert_eq!(vec.len(), 0);
///
/// // If requested capacity <= N, no memory allocation caused.
/// let mut vec = FastVec::<i32, 8>::with_capacity(4);
/// assert_eq!(vec.capacity(), 8);
///
/// // If requested capacity > N, allocate memory.
/// let mut vec = FastVec::<i32, 8>::with_capacity(12);
/// assert!(vec.capacity() >= 12);
/// ```
///
/// ## Modifying Data
///
/// Most data-modifying operations require obtaining a
/// [`&mut FastVecData`](FastVecData) via [`FastVec::data`].
///
/// ```
/// # use fastvec::{FastVec, fast::FastVecData};
/// let mut vec: FastVec<_, 5> = [1, 2, 3, 4].into();
/// let data: &mut FastVecData<_,_> = vec.data();
///
/// // Use it like a Vec
/// data.push(5);
/// data.insert(0, 6);
///
/// assert_eq!(data, &[6, 1, 2, 3, 4, 5]);
/// ```
///
/// # API Design
///
/// [`FastVec`] supports nearly all [`Vec`] methods, categorized as follows:
///
/// ## Operations Through [`&mut FastVecData`](FastVecData)
///
/// Operations that take `&self` or `&mut self` require:
/// - [`push`](FastVecData::push), [`pop`](FastVecData::pop)
/// - [`insert`](FastVecData::insert), [`remove`](FastVecData::remove)
/// - [`drain`](FastVecData::drain), [`extract_if`](FastVecData::extract_if)
/// - And more...
///
/// ## Operations Directly on [`FastVec`]
///
/// Consuming or conversion operations can be called directly:
/// - [`into_vec`](FastVec::into_vec), [`into_boxed_slice`](FastVec::into_boxed_slice)
/// - [`IntoIterator`], [`From`] conversions
/// - And more...
///
/// ```
/// # use fastvec::FastVec;
/// let vec: FastVec<_, 5> = [1, 2, 3, 4].into();
/// let boxed: Box<[i32]> = vec.into_boxed_slice();
/// ```
///
/// ## Convenience Methods on [`FastVec`]
///
/// A few frequently-used APIs are exposed directly on [`FastVec`] for convenience:
/// - [`len`](FastVec::len), [`capacity`](FastVec::capacity), [`is_empty`](FastVec::is_empty);
///   they have no additional expenses.
/// - [`as_slice`](FastVec::as_slice), [`as_mut_slice`](FastVec::as_mut_slice);
///   they internally call [`data`](FastVec::data) first.
///
/// ## Trait Implementations
///
/// [`FastVec`] implements [`Deref`](core::ops::Deref), [`Index`](core::ops::Index),
/// [`Debug`], etc., via [`as_slice`](FastVec::as_slice) and
/// [`as_mut_slice`](FastVec::as_mut_slice):
///
/// ```
/// # use fastvec::FastVec;
/// let mut vec: FastVec<_, 5> = [1, 4, 3, 2].into();
/// vec.sort(); // via Deref
///
/// assert_eq!(vec[1], 2); // via Index
/// assert_eq!(vec, [1, 2, 3, 4]); // via PartialEq
/// ```
///
/// **Performance note:** These operations call `get` each time.
/// For complex operations like `sort`, this overhead is negligible.
/// However, for simple operations (`Index`, `push`, `pop`), the overhead is measurable.
///
/// ## Recommended Usage Pattern
///
/// For best performance, acquire the data reference once and reuse it:
///
/// ```
/// # use fastvec::FastVec;
/// let mut vec: FastVec<_, 5> = [1, 4, 3, 2].into();
/// let data = vec.data();
///
/// // All operations reuse the same reference
/// data.sort();
/// data.push(5);
/// assert_eq!(data, &[1, 2, 3, 4, 5]);
///
/// // Use FastVec only when you need to create/move/consume it
/// let vec: Vec<_> = vec.into_vec();
/// assert_eq!(vec, [1, 2, 3, 4, 5]);
/// ```
///
/// # Understanding `FastVecData`
///
/// ## The Problem
///
/// A naive stack-to-heap vector looks like this:
///
/// ```ignore
/// struct NaiveVec<T, const N: usize> {
///     stack_cache: [MaybeUninit<T>; N],
///     heap_ptr: *mut T,
///     len: usize,
///     cap: usize,
///     in_stack: bool, // Is data on stack or heap?
/// }
/// ```
///
/// **Problem:** Every operation (`push`, `pop`, `index`, etc.) must check `in_stack` to determine
/// whether to access `stack_cache` or `heap_ptr`. This conditional is cheap individually but cumulative
/// overhead becomes significant for simple operations.
///
/// ## The Solution: Pointer Caching
///
/// Make a single pointer always point to the current data location:
///
/// ```ignore
/// struct FastVecData<T, const N: usize> {
///     stack_cache: [MaybeUninit<T>; N],
///     ptr: Cell<*mut T>,  // Always points to active data
///     len: usize,
///     cap: usize,
///     in_stack: bool,     // Only checked during reallocation
/// }
/// ```
///
/// Now `ptr` directly accesses data without branching. The `in_stack` check is only needed when
/// resizing capacity, not on every operation.
///
/// But when data is inline, `ptr` points to `cache`, creating a **self-referential structure**.
/// Moving [`FastVecData`] invalidates `ptr`, which must be "refreshed" (repointed to `cache`).
///
/// ## The Design: Two-Type Architecture
///
/// [`FastVec`] is a thin wrapper around [`FastVecData`]:
/// - **[`FastVec`]**: Manages the pointer refresh logic; can be freely moved
/// - **[`FastVecData`]**: Performs actual data operations; accessed only through borrows
///
/// When you call [`data`](FastVec::data), [`FastVec`]:
/// 1. Refreshes the pointer (if data is inline)
/// 2. Returns a borrow of [`FastVecData`]
///
/// Rust's borrow checker ensures [`FastVecData`] cannot be moved while borrowed, so the pointer
/// remains valid during handle usage.
///
/// ## Why [`Cell`]?
///
/// Pointer refresh needs interior mutability (even [`as_slice`](FastVec::as_slice) must update the pointer).
///
/// We use [`Cell`] instead of atomic operations because:
/// - Atomic pointers add runtime overhead on every read
/// - Cross-platform atomic pointer support varies
/// - Single-threaded refresh is sufficient (handles are `Sync`)
///
/// # Thread Safety
///
/// **[`FastVec`]**: Implements [`Send`] but **not** [`Sync`] due to internal
/// [`Cell`] usage (required for pointer relocation). Concurrent
/// calls to [`as_slice`](FastVec::as_slice) may race.
///
/// - **[`FastVecData`]**: Implements both [`Send`] and [`Sync`], so you can safely
///   share its reference across threads.
#[repr(transparent)]
pub struct FastVec<T, const N: usize> {
    inner: FastVecData<T, N>,
    _marker: PhantomData<*const ()>,
}

// All functions have a dependency on [`FastVecData::refresh`], but it doesn't seem thread safe.
// unsafe impl<T, const N: usize> Sync for FastVecData<T, N> where T: Sync {}
unsafe impl<T, const N: usize> Send for FastVec<T, N> where T: Send {}
impl<T, const N: usize> RefUnwindSafe for FastVec<T, N> where T: RefUnwindSafe {}

impl<T, const N: usize> FastVec<T, N> {
    /// Constructs a new, empty [`FastVec`].
    ///
    /// The capacity of cache area must be provided at compile time.
    /// The inline buffer is embedded in the value. If the value is stack-allocated,
    /// very large capacities may still risk stack overflow.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let vec: FastVec<i32, 8> = FastVec::new();
    /// assert_eq!(vec, []);
    /// assert_eq!(vec.capacity(), 8);
    /// assert_eq!(vec.len(), 0);
    /// ```
    #[inline]
    pub const fn new() -> Self {
        Self {
            inner: FastVecData::new(),
            _marker: PhantomData,
        }
    }

    /// Constructs a new, empty `FastVec` with at least the specified capacity.
    ///
    /// If the specified capacity is less than or equal to `N`,
    /// this is equivalent to [`new`](FastVec::new),
    /// and no heap memory will be allocated.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    ///
    /// let vec: FastVec<i32, 5> = FastVec::with_capacity(4);
    /// assert_eq!(vec.capacity(), 5);
    ///
    /// let vec: FastVec<i32, 5> = FastVec::with_capacity(10);
    /// assert!(vec.capacity() >= 10);
    /// ```
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            inner: FastVecData::with_capacity(capacity),
            _marker: PhantomData,
        }
    }

    /// Creates a `FastVec` directly from a pointer, a length,
    /// and a capacity.
    ///
    /// This does not copy data; it sets pointers and lengths directly
    /// and treats the data as heap-allocated.
    ///
    /// # Safety
    /// - if T is **not** zero sized type, **capacity > 0**.
    ///
    /// See more information in [`Vec::from_raw_parts`].
    #[inline]
    pub const unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
        Self {
            inner: unsafe { FastVecData::from_raw_parts(ptr, length, capacity) },
            _marker: PhantomData,
        }
    }

    /// Creates a `FastVec` by copying all elements from a slice.
    ///
    /// If `slice.len() <= N`, data is stored inline, otherwise it is allocated on heap.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let vec = FastVec::<i32, 2>::from_slice(&[10, 20, 30]);
    /// assert_eq!(vec.as_slice(), &[10, 20, 30]);
    #[inline]
    pub fn from_slice(slice: &[T]) -> Self
    where
        T: Copy,
    {
        Self {
            inner: FastVecData::from_slice(slice),
            _marker: PhantomData,
        }
    }

    /// Returns `true` if the vector contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 2> = FastVec::new();
    /// assert!(vec.is_empty());
    ///
    /// vec.data().push(1);
    /// assert!(!vec.is_empty());
    /// ```
    #[inline(always)]
    pub const fn is_empty(&self) -> bool {
        self.inner.len == 0
    }

    /// Returns the number of elements in the vector.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 8> = [1, 2, 3, 4].into();
    /// assert_eq!(vec.capacity(), 8);
    /// assert_eq!(vec.len(), 4);
    ///
    /// vec.data().extend([1, 2, 3,  4, 5]);
    /// assert!(vec.capacity() >= 9);
    /// assert_eq!(vec.len(), 9);
    /// ```
    #[inline(always)]
    pub const fn len(&self) -> usize {
        self.inner.len
    }

    /// Returns the total number of elements the vector can hold without reallocating.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 8> = [1, 2, 3, 4].into();
    /// assert_eq!(vec.capacity(), 8);
    /// assert_eq!(vec.len(), 4);
    ///
    /// vec.data().extend([1, 2, 3,  4, 5]);
    /// assert!(vec.capacity() >= 9);
    /// assert_eq!(vec.len(), 9);
    /// ```
    #[inline(always)]
    pub const fn capacity(&self) -> usize {
        self.inner.capacity()
    }

    /// Check and refresh the pointer to ensure it points to the correct location.
    ///
    /// Note that although this crate reduces calls in many places,
    /// **the overhead is very low**, with only one branch and one pointer assignment.
    ///
    /// This function usually does not need to be called manually;
    /// other methods call it when needed.
    ///
    /// This is internal mutability, and `Sync` is disabled because it may not be thread safe.
    #[inline(always)]
    pub fn refresh(&self) {
        unsafe {
            self.inner.refresh();
        }
    }

    /// Refresh the pointer and return a mutable reference to the internal data.
    ///
    /// You can use this mutable reference for methods such as `push`, `pop`,
    /// `retain`, and `insert`. The pointer is refreshed once in `data`; later
    /// method calls reuse it without extra cost.
    ///
    /// We do not provide a version for obtaining immutable borrowing,
    /// you can use [`as_slice`](FastVec::as_slice) instead.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 8> = [1, 2, 3, 4].into();
    /// let v = vec.data();
    ///
    /// v.push(5);
    /// v.retain(|x| *x % 2 == 1);
    ///
    /// assert_eq!(vec, [1, 3, 5]);
    /// ```
    #[inline]
    pub fn data(&mut self) -> &mut FastVecData<T, N> {
        self.refresh();
        &mut self.inner
    }

    /// Refresh the pointer and obtain slices of the data.
    ///
    /// During the validity period of the slice reference, the data will not be moved, so the pointer is valid.
    ///
    /// This method enables [`FastVec`] to implement many traits directly through slice access.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 8> = [1, 4, 3, 2].into();
    ///
    /// vec.sort(); // `Deref` trait, internal impl with `as_mut_slice`.
    ///
    /// let x = vec[1]; /// `Index` trait, internal impl with `as_slice`.
    ///
    /// assert_eq!(x, 2);
    /// ```
    ///
    /// Method cost depends on implementation: for `sort` the refresh cost is negligible,
    /// while `Index`-style operations may effectively double the work.
    ///
    /// A better approach is to obtain a reference once and then use it multiple times.
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 8> = [1, 4, 3, 2].into();
    /// let slice = vec.as_slice();
    ///
    /// let mut x = vec[1];
    /// x += vec[2] * vec[3];
    /// ```
    #[inline]
    pub fn as_slice(&self) -> &[T] {
        self.refresh();
        self.inner.as_slice()
    }

    /// Refresh the pointer and obtain mutable slices of the data.
    ///
    /// During the slice's lifetime, the data will not move, so the pointer remains valid.
    ///
    /// This enables [`FastVec`] to implement many traits directly through slice access.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 8> = [1, 4, 3, 2].into();
    ///
    /// vec.sort(); // `Deref` trait, internal impl with `as_mut_slice`.
    ///
    /// let x = vec[1]; /// `Index` trait, internal impl with `as_slice`.
    ///
    /// assert_eq!(x, 2);
    /// ```
    ///
    /// Method cost depends on implementation: for `sort` the refresh cost is negligible,
    /// while `Index`-style operations may effectively double the work.
    ///
    /// A better approach is to obtain a reference once and then use it multiple times.
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut vec: FastVec<i32, 8> = [1, 4, 3, 2].into();
    /// let slice = vec.as_mut_slice();
    ///
    /// slice.sort();
    ///
    /// let mut x = vec[1];
    /// x += vec[2] * vec[3];
    /// ```
    #[inline]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        self.refresh();
        self.inner.as_mut_slice()
    }

    /// Convert [`FastVec`] to [`Vec`].
    ///
    /// - If the data is in the stack, the exact memory will be allocated.
    /// - If the data is already on the heap, no reallocation is needed.
    ///
    /// The returned [`Vec`] may not be tight because heap data does not shrink here.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let vec: FastVec<i32, 3> = [1, 2].into();
    /// let vec: Vec<_> = vec.into_vec();
    /// assert_eq!(vec, [1, 2]);
    /// assert!(vec.capacity() == 2);
    ///
    /// let vec: FastVec<i32, 3> = [1, 2, 3, 4, 5].into();
    /// let vec: Vec<_> = vec.into_vec();
    /// assert_eq!(vec, [1, 2, 3, 4, 5]);
    /// assert!(vec.capacity() >= 5);
    /// ```
    pub fn into_vec(self) -> Vec<T> {
        self.refresh();
        self.inner.into_vec()
    }

    /// Convert [`FastVec`] to [`Box<[T]>`](Box).
    pub fn into_boxed_slice(self) -> Box<[T]> {
        self.refresh();
        self.inner.into_vec().into_boxed_slice()
    }
}

impl<T, const N: usize> Default for FastVec<T, N> {
    /// Constructs a new, empty `FastVec` with inline storage and fixed inline capacity.
    ///
    /// Equivalent to [`FastVec::new`].
    #[inline(always)]
    fn default() -> Self {
        Self::new()
    }
}

// -----------------------------------------------------------------------------
// Common

super::utils::impl_common_traits!(FastVec<T, N>);

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

impl<T: Clone, const N: usize> Clone for FastVec<T, N> {
    fn clone(&self) -> Self {
        let mut vec = Self::with_capacity(self.len());
        let dst = vec.data();
        for item in self.as_slice() {
            unsafe {
                dst.push_unchecked(item.clone());
            }
        }
        vec
    }

    fn clone_from(&mut self, source: &Self) {
        let dst = self.data();
        dst.clear();
        dst.reserve(source.len());

        for item in source.as_slice() {
            unsafe {
                dst.push_unchecked(item.clone());
            }
        }
    }
}

impl<T, const N: usize> FromIterator<T> for FastVec<T, N> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let iter = iter.into_iter();
        let mut vec = Self::with_capacity(iter.size_hint().0);
        let data = vec.data();

        iter.for_each(|item| {
            data.push(item);
        });
        vec
    }
}

// -----------------------------------------------------------------------------
// From/Into

impl<T, const N: usize> From<FastVec<T, N>> for Vec<T> {
    fn from(v: FastVec<T, N>) -> Self {
        v.into_vec()
    }
}

impl<T, const N: usize> From<FastVec<T, N>> for Box<[T]> {
    fn from(v: FastVec<T, N>) -> Self {
        v.into_boxed_slice()
    }
}

impl<T, const N: usize, const P: usize> TryFrom<FastVec<T, N>> for [T; P] {
    type Error = FastVec<T, N>;

    fn try_from(mut vec: FastVec<T, N>) -> Result<[T; P], FastVec<T, N>> {
        if vec.len() != P {
            return Err(vec);
        }
        let data = vec.data();
        let src = data.as_ptr();
        unsafe { data.set_len(0) };
        let array = unsafe { ptr::read(src as *const [T; P]) };
        Ok(array)
    }
}

impl<T: Clone, const N: usize> From<&[T]> for FastVec<T, N> {
    fn from(s: &[T]) -> FastVec<T, N> {
        let mut vec = FastVec::<T, N>::with_capacity(s.len());
        let data = vec.data();

        s.iter().for_each(|item| unsafe {
            data.push_unchecked(item.clone());
        });
        vec
    }
}

impl<T: Clone, const N: usize> From<&mut [T]> for FastVec<T, N> {
    fn from(s: &mut [T]) -> FastVec<T, N> {
        let mut vec = FastVec::<T, N>::with_capacity(s.len());
        let data = vec.data();

        s.iter().for_each(|item| unsafe {
            data.push_unchecked(item.clone());
        });
        vec
    }
}

impl<T: Clone, const N: usize, const P: usize> From<&[T; N]> for FastVec<T, P> {
    fn from(s: &[T; N]) -> FastVec<T, P> {
        Self::from(s.as_slice())
    }
}

impl<T: Clone, const N: usize, const P: usize> From<&mut [T; N]> for FastVec<T, P> {
    fn from(s: &mut [T; N]) -> Self {
        Self::from(s.as_mut_slice())
    }
}

impl<T, const N: usize, const P: usize> From<[T; N]> for FastVec<T, P> {
    fn from(s: [T; N]) -> Self {
        if N <= P {
            let mut this = Self::new();
            let data = this.data();
            let ptr = data.as_mut_ptr();
            let s = ManuallyDrop::new(s);
            let len = s.len();
            unsafe {
                ptr::copy_nonoverlapping(s.as_ptr(), ptr, len);
                data.set_len(len);
            }
            this
        } else {
            let vec = Vec::<T>::from(s);
            FastVec::from(vec)
        }
    }
}

impl<T, const N: usize> From<Vec<T>> for FastVec<T, N> {
    fn from(s: Vec<T>) -> Self {
        let (p, l, c) = s.into_raw_parts();
        unsafe { FastVec::from_raw_parts(p, l, c) }
    }
}

impl<T, const N: usize> From<Box<[T]>> for FastVec<T, N> {
    fn from(s: Box<[T]>) -> Self {
        Self::from(s.into_vec())
    }
}

// -----------------------------------------------------------------------------
// IntoIterator

/// An iterator that consumes a [`FastVec`] and yields its items by value.
///
/// # Examples
///
/// ```
/// # use fastvec::FastVec;
///
/// let vec = FastVec::<_, 5>::from(["1", "2", "3"]);
/// let mut iter = vec.into_iter();
///
/// assert_eq!(iter.next(), Some("1"));
///
/// let vec: Vec<&'static str> = iter.collect();
/// assert_eq!(vec, ["2", "3"]);
/// ```
pub struct IntoIter<T, const N: usize> {
    vec: ManuallyDrop<FastVec<T, N>>,
    index: usize,
}

unsafe impl<T: Send, const N: usize> Send for IntoIter<T, N> {}
unsafe impl<T: Sync, const N: usize> Sync for IntoIter<T, N> {}

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

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            vec: ManuallyDrop::new(self),
            index: 0,
        }
    }
}

impl<T, const N: usize> Iterator for IntoIter<T, N> {
    type Item = T;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.vec.len() {
            self.index += 1;
            let ptr = self.vec.data().as_ptr();
            unsafe { Some(ptr::read(ptr.add(self.index - 1))) }
        } else {
            None
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let v = self.vec.len() - self.index;
        (v, Some(v))
    }
}

impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        let len = self.vec.len();
        if self.index < len {
            let data = self.vec.data();
            unsafe {
                data.set_len(len - 1);
            }
            unsafe { Some(ptr::read(data.as_ptr().add(len - 1))) }
        } else {
            None
        }
    }
}

impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> {
    #[inline]
    fn len(&self) -> usize {
        self.vec.len() - self.index
    }
}

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

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

impl<T, const N: usize> Drop for IntoIter<T, N> {
    fn drop(&mut self) {
        let len = self.vec.len();
        let data = self.vec.data();
        if self.index < len {
            unsafe {
                let ptr = data.as_mut_ptr().add(self.index);
                let count = len - self.index;
                let to_drop = ptr::slice_from_raw_parts_mut(ptr, count);
                ptr::drop_in_place(to_drop);
            }
        }
        data.dealloc();
    }
}

// -----------------------------------------------------------------------------
// Drain ExtractIf

impl<T, const N: usize> FastVec<T, N> {
    /// Removes the subslice indicated by the given range from the vector,
    /// returning a double-ended iterator over the removed subslice.
    ///
    /// If the iterator is dropped before being fully consumed, it drops the remaining removed elements.
    ///
    /// The returned iterator keeps a mutable borrow on the vector to optimize its implementation.
    ///
    /// See more information in [`Vec::drain`].
    ///
    /// # Panics
    ///
    /// Panics if the range is out of bounds.
    ///
    /// # Examples
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut v = FastVec::<_, 3>::from([1, 2, 3]);
    /// let u: Vec<_> = v.drain(1..).collect();
    /// assert_eq!(v, [1]);
    /// assert_eq!(u, [2, 3]);
    ///
    /// // A full range clears the vector, like `clear()` does
    /// v.drain(..);
    /// assert_eq!(v, []);
    /// ```
    pub fn drain<R: core::ops::RangeBounds<usize>>(&mut self, range: R) -> Drain<'_, T, N> {
        self.data().drain(range)
    }

    /// Creates an iterator which uses a closure to determine
    /// if an element in the range should be removed.
    ///
    /// See more information in [`Vec::extract_if`].
    ///
    /// # Panics
    /// Panics if the range is out of bounds.
    ///
    ///
    /// # Examples
    ///
    /// Splitting a vector into even and odd values, reusing the original vector:
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut numbers = FastVec::<_, 5>::from([1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
    ///
    /// let evens = numbers.extract_if(.., |x| *x % 2 == 0).collect::<FastVec<_, 10>>();
    /// let odds = numbers;
    ///
    /// assert_eq!(evens, [2, 4, 6, 8, 14]);
    /// assert_eq!(odds, [1, 3, 5, 9, 11, 13, 15]);
    /// ```
    ///
    /// Using the range argument to only process a part of the vector:
    ///
    /// ```
    /// # use fastvec::FastVec;
    /// let mut items = FastVec::<_, 5>::from([0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2]);
    ///
    /// let ones = items.extract_if(7.., |x| *x == 1).collect::<Vec<_>>();
    /// assert_eq!(items, [0, 0, 0, 0, 0, 0, 0, 2, 2, 2]);
    /// assert_eq!(ones.len(), 3);
    /// ```
    pub fn extract_if<F, R>(&mut self, range: R, filter: F) -> ExtractIf<'_, T, F, N>
    where
        F: FnMut(&mut T) -> bool,
        R: core::ops::RangeBounds<usize>,
    {
        self.data().extract_if(range, filter)
    }
}

// -----------------------------------------------------------------------------
// Tests

#[cfg(test)]
mod tests {
    use super::FastVec;
    use core::sync::atomic::{AtomicUsize, Ordering};

    macro_rules! define_tracker {
        () => {
            static DROPS: AtomicUsize = AtomicUsize::new(0);

            struct Tracker;
            impl Drop for Tracker {
                fn drop(&mut self) {
                    DROPS.fetch_add(1, Ordering::SeqCst);
                }
            }
        };
    }

    #[test]
    fn drop_zst() {
        define_tracker!();

        DROPS.store(0, Ordering::SeqCst);

        let mut vec = FastVec::<Tracker, 0>::new();
        let data = vec.data();
        data.push(Tracker);
        data.push(Tracker);
        data.push(Tracker);
        data.push(Tracker);
        data.push(Tracker);

        {
            let mut drain = data.drain(1..4);
            let one = drain.next_back().unwrap();
            drop(one);
            assert_eq!(DROPS.load(Ordering::SeqCst), 1);
        }

        // 1 consumed + 2 dropped by Drain::drop in the ZST path.
        assert_eq!(DROPS.load(Ordering::SeqCst), 3);

        drop(vec);
        assert_eq!(DROPS.load(Ordering::SeqCst), 5);
    }

    #[test]
    fn drop_vec() {
        define_tracker!();

        DROPS.store(0, Ordering::SeqCst);
        {
            let mut vec = FastVec::<Tracker, 4>::new();
            let data = vec.data();
            data.push(Tracker);
            data.push(Tracker);
            data.push(Tracker);

            assert_eq!(DROPS.load(Ordering::SeqCst), 0);
        }
        assert_eq!(DROPS.load(Ordering::SeqCst), 3);
    }

    #[test]
    fn drop_pop_remove() {
        define_tracker!();

        DROPS.store(0, Ordering::SeqCst);

        let mut vec = FastVec::<Tracker, 4>::new();
        let data = vec.data();
        data.push(Tracker);
        data.push(Tracker);
        data.push(Tracker);

        let popped = data.pop().unwrap();
        assert_eq!(DROPS.load(Ordering::SeqCst), 0);
        drop(popped);
        assert_eq!(DROPS.load(Ordering::SeqCst), 1);

        let removed = data.remove(0);
        assert_eq!(DROPS.load(Ordering::SeqCst), 1);
        drop(removed);
        assert_eq!(DROPS.load(Ordering::SeqCst), 2);

        drop(vec);
        assert_eq!(DROPS.load(Ordering::SeqCst), 3);
    }

    #[test]
    fn drop_into_iter() {
        define_tracker!();

        DROPS.store(0, Ordering::SeqCst);

        let mut vec = FastVec::<Tracker, 4>::new();
        let data = vec.data();
        data.push(Tracker);
        data.push(Tracker);
        data.push(Tracker);

        let mut iter = vec.into_iter();
        let first = iter.next().unwrap();
        drop(first);
        assert_eq!(DROPS.load(Ordering::SeqCst), 1);

        drop(iter);
        assert_eq!(DROPS.load(Ordering::SeqCst), 3);
    }

    #[test]
    fn drop_drain() {
        define_tracker!();

        DROPS.store(0, Ordering::SeqCst);

        let mut vec = FastVec::<Tracker, 8>::new();
        let data = vec.data();
        data.push(Tracker);
        data.push(Tracker);
        data.push(Tracker);
        data.push(Tracker);
        data.push(Tracker);

        {
            let mut drain = data.drain(1..4);
            let first = drain.next().unwrap();
            drop(first);
            assert_eq!(DROPS.load(Ordering::SeqCst), 1);
        }

        // 1 consumed + 2 still in drained range
        assert_eq!(DROPS.load(Ordering::SeqCst), 3);

        drop(vec);
        assert_eq!(DROPS.load(Ordering::SeqCst), 5);
    }

    #[test]
    fn drop_extract_if() {
        static DROPS: AtomicUsize = AtomicUsize::new(0);

        struct Tracker {
            id: usize,
        }
        impl Drop for Tracker {
            fn drop(&mut self) {
                DROPS.fetch_add(1, Ordering::SeqCst);
            }
        }

        DROPS.store(0, Ordering::SeqCst);

        let mut vec = FastVec::<Tracker, 2>::new();
        let data = vec.data();
        for id in 0..6 {
            data.push(Tracker { id });
        }

        let removed: FastVec<Tracker, 8> = data.extract_if(.., |t| t.id % 2 == 0).collect();
        assert_eq!(DROPS.load(Ordering::SeqCst), 0);

        drop(removed);
        assert_eq!(DROPS.load(Ordering::SeqCst), 3);

        drop(vec);
        assert_eq!(DROPS.load(Ordering::SeqCst), 6);
    }
}