shared_vector/

vector.rs

use core::fmt::Debug;
use core::ops::{Deref, DerefMut, Index, IndexMut};
use core::ptr::NonNull;
use core::{mem, ptr};
use core::ops::RangeBounds;

use crate::alloc::{AllocError, Allocator, Global};
use crate::drain::Drain;
use crate::raw::{
    self, buffer_layout, AtomicRefCount, BufferSize, Header, HeaderBuffer, RefCount, VecHeader, move_data,
};
use crate::shared::{AtomicSharedVector, SharedVector};
use crate::splice::Splice;
use crate::{grow_amortized, DefaultRefCount};

/// A heap allocated, mutable contiguous buffer containing elements of type `T`, with manual deallocation.
///
/// <svg width="280" height="120" viewBox="0 0 74.08 31.75" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg"><defs><linearGradient id="a"><stop offset="0" stop-color="#491c9c"/><stop offset="1" stop-color="#d54b27"/></linearGradient><linearGradient xlink:href="#a" id="b" gradientUnits="userSpaceOnUse" x1="6.27" y1="34.86" x2="87.72" y2="13.24" gradientTransform="translate(-2.64 -18.48)"/></defs><rect width="10.57" height="10.66" x="7.94" y="18.45" ry="1.37" fill="#3dbdaa"/><circle cx="12.7" cy="18.48" r=".79" fill="#666"/><path d="M12.7 18.48c0-3.93 7.14-1.28 7.14-5.25" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><rect width="68.79" height="10.58" x="2.65" y="2.68" ry="1.37" fill="url(#b)"/><rect width="15.35" height="9.51" x="3.18" y="3.21" ry=".9" fill="#78a2d4"/><rect width="9.26" height="9.51" x="19.85" y="3.2" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="29.64" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="39.43" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="49.22" y="3.21" ry=".9" fill="#eaa577"/><circle cx="62.84" cy="7.97" r=".66" fill="#eaa577"/><circle cx="64.7" cy="7.97" r=".66" fill="#eaa577"/><circle cx="66.55" cy="7.97" r=".66" fill="#eaa577"/></svg>
///
/// See also `Vector<T, A>`.
///
/// This container is similar to this crate's `Vector` data structure with two key difference:
/// - It does store an allocator field. Instead, all methods that require interacting with an allocator are
///   marked unsafe and take the allocator as parameter.
/// - `RawVector`'s `Drop` implementation does not automatically deallocate the memory. Instead the memory
///   must be manually deallocated via the `deallocate` method. Dropping a raw vector without deallocating it
///   silently leaks the memory.
///
/// `Vector<T, A>` is implemented as a thin wrapper around this type.
///
/// # Use cases
///
/// In most cases, `Vector<T, A>` is more appropriate. However in some situations it can be beneficial to not
/// store the allocator in the container. In complex data structures that contain many vectors, for example,
/// it may be preferable to store the allocator once at the root of the data structure than multiple times
/// in each of the internally managed vectors.
pub struct RawVector<T> {
    pub(crate) data: NonNull<T>,
    pub(crate) header: VecHeader,
}

impl<T> RawVector<T> {
    /// Creates an empty, unallocated raw vector.
    pub fn new() -> Self {
        RawVector { data: NonNull::dangling(), header: VecHeader { len: 0, cap: 0 } }
    }

    /// Creates an empty pre-allocated vector with a given storage capacity.
    ///
    /// Does not allocate memory if `cap` is zero.
    pub fn try_with_capacity<A: Allocator>(allocator: &A, cap: usize) -> Result<RawVector<T>, AllocError> {
        if cap == 0 {
            return Ok(RawVector::new());
        }

        unsafe {
            let (base_ptr, cap) = raw::allocate_header_buffer::<T, A>(cap, allocator)?;
            let data = NonNull::new_unchecked(raw::data_ptr::<raw::Header<DefaultRefCount, A>, T>(
                base_ptr.cast(),
            ));
            Ok(RawVector {
                data,
                header: VecHeader { cap: cap as BufferSize, len: 0 },
            })
        }
    }

    pub fn try_from_slice<A: Allocator>(allocator: &A, data: &[T]) -> Result<Self, AllocError>
    where
        T: Clone,
    {
        let mut v = Self::try_with_capacity(allocator, data.len())?;
        unsafe {
            v.extend_from_slice(allocator, data);
        }

        Ok(v)
    }

    /// Creates a raw vector with `n` clones of `elem`.
    pub fn try_from_elem<A: Allocator>(allocator: &A, elem: T, n: usize) -> Result<Self, AllocError>
    where
        T: Clone,
    {
        if n == 0 {
            return Ok(Self::new());
        }

        let mut v = Self::try_with_capacity(allocator, n)?;
        unsafe {
            for _ in 0..(n - 1) {
                v.push(allocator, elem.clone())
            }

            v.push(allocator, elem);
        }

        Ok(v)
    }

    /// Clears and deallocates this raw vector, leaving it in its unallocated state.
    ///
    /// It is safe (no-op) to call `deallocate` on a vector that is already in its unallocated state.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    pub unsafe fn deallocate<A: Allocator>(&mut self, allocator: &A) {
        if self.header.cap == 0 {
            return;
        }

        self.clear();

        self.deallocate_buffer(allocator);

        self.data = NonNull::dangling();
        self.header.cap = 0;
        self.header.len = 0;
    }

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

    #[inline]
    /// Returns the number of elements in the vector, also referred to as its ‘length’.
    pub fn len(&self) -> usize {
        self.header.len as usize
    }

    #[inline]
    /// Returns the total number of elements the vector can hold without reallocating.
    pub fn capacity(&self) -> usize {
        self.header.cap as usize
    }

    /// Returns number of elements that can be added without reallocating.
    #[inline]
    pub fn remaining_capacity(&self) -> usize {
        (self.header.cap - self.header.len) as usize
    }

    #[inline]
    fn data_ptr(&self) -> *mut T {
        self.data.as_ptr()
    }

    #[inline]
    pub fn as_slice(&self) -> &[T] {
        unsafe { core::slice::from_raw_parts(self.data_ptr(), self.len()) }
    }

    #[inline]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        unsafe { core::slice::from_raw_parts_mut(self.data_ptr(), self.len()) }
    }

    /// Clears the vector, removing all values.
    pub fn clear(&mut self) {
        unsafe {
            raw::clear(self.data_ptr(), &mut self.header)
        }
    }

    unsafe fn base_ptr<A: Allocator>(&self, _allocator: &A) -> NonNull<u8> {
        debug_assert!(self.header.cap > 0);
        raw::header_from_data_ptr::<Header<DefaultRefCount, A>, T>(self.data).cast()
    }

    /// Appends an element to the back of a collection.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity exceeds `u32::MAX` bytes.
    #[inline]
    pub unsafe fn push<A: Allocator>(&mut self, allocator: &A, val: T) {
        if self.header.len == self.header.cap {
            self.try_realloc_additional(allocator, 1).unwrap();
        }

        raw::push_assuming_capacity(self.data_ptr(), &mut self.header, val);
    }

    /// Appends an element if there is sufficient spare capacity, otherwise an error is returned
    /// with the element.
    ///
    /// Unlike push this method will not reallocate when there’s insufficient capacity.
    /// The caller should use reserve or try_reserve to ensure that there is enough capacity.
    #[inline]
    pub fn push_within_capacity(&mut self, val: T) -> Result<(), T> {
        if self.header.len == self.header.cap {
            return Err(val);
        }

        unsafe {
            let dst = self.data_ptr().add(self.header.len as usize);
            self.header.len += 1;
            ptr::write(dst, val);
        }

        Ok(())
    }

    /// Removes the last element from the vector and returns it, or `None` if it is empty.
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        unsafe {
            raw::pop(self.data_ptr(), &mut self.header)
        }
    }

    /// Removes and returns the element at position `index` within the vector,
    /// shifting all elements after it to the left.
    ///
    /// # Panics
    ///
    /// Panics if `index` is out of bounds.
    ///
    pub fn remove(&mut self, index: usize) -> T {
        #[cold]
        #[inline(never)]
        #[track_caller]
        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 {
            // infallible
            let ret;
            {
                // the place we are taking from.
                let ptr = self.as_mut_ptr().add(index);
                // copy it out, unsafely having a copy of the value on
                // the stack and in the vector at the same time.
                ret = ptr::read(ptr);

                // Shift everything down to fill in that spot.
                ptr::copy(ptr.add(1), ptr, len - index - 1);
            }
            self.header.len = len as u32 - 1;
            ret
        }
    }

    /// Removes an element from the vector and returns it.
    ///
    /// The removed element is replaced by the last element of the vector.
    ///
    /// # Panics
    ///
    /// Panics if index is out of bounds.
    #[inline]
    pub fn swap_remove(&mut self, idx: usize) -> T {
        let len = self.len();
        assert!(idx < len);

        unsafe {
            let ptr = self.data_ptr().add(idx);
            let item = ptr::read(ptr);

            let last_idx = len - 1;
            if idx != last_idx {
                let last_ptr = self.data_ptr().add(last_idx);
                ptr::write(ptr, ptr::read(last_ptr));
            }

            self.header.len -= 1;

            item
        }
    }

    /// Inserts an element at position `index` within the vector, shifting all
    /// elements after it to the right.
    ///
    /// # Panics
    ///
    /// Panics if `index > len`.
    pub unsafe fn insert<A: Allocator>(&mut self, allocator: &A, index: usize, element: T) {
        #[cold]
        #[inline(never)]
        fn assert_failed(index: usize, len: usize) -> ! {
            panic!("insertion index (is {index}) should be <= len (is {len})");
        }

        unsafe {
            // space for the new element
            if self.header.len == self.header.cap {
                self.try_reserve(allocator, 1).unwrap();
            }

            let len = self.len();

            // infallible
            // The spot to put the new value
            {
                let p = self.as_mut_ptr().add(index);
                if index < len {
                    // Shift everything over to make space. (Duplicating the
                    // `index`th element into two consecutive places.)
                    ptr::copy(p, p.add(1), len - index);
                } else if index == len {
                    // No elements need shifting.
                } else {
                    assert_failed(index, len);
                }
                // Write it in, overwriting the first copy of the `index`th
                // element.
                ptr::write(p, element);
            }
            self.header.len += 1;
        }
    }

    /// Clones and appends the contents of the slice to the back of a collection.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    pub unsafe fn extend_from_slice<A: Allocator>(&mut self, allocator: &A, slice: &[T])
    where
        T: Clone,
    {
        self.try_reserve(allocator, slice.len()).unwrap();
        unsafe {
            raw::extend_from_slice_assuming_capacity(self.data_ptr(), &mut self.header, slice);
        }
    }

    /// Moves all the elements of `other` into `self`, leaving `other` empty.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    pub unsafe fn append<A: Allocator>(&mut self, allocator: &A, other: &mut Self)
    where
        T: Clone,
    {
        if other.is_empty() {
            return;
        }

        self.try_reserve(allocator, other.len()).unwrap();

        unsafe {
            move_data(other.data_ptr(), &mut other.header, self.data_ptr(), &mut self.header);
        }
    }

    /// Appends the contents of an iterator to the back of a collection.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    pub unsafe fn extend<A: Allocator>(&mut self, allocator: &A, data: impl IntoIterator<Item = T>) {
        let mut iter = data.into_iter();
        let (min, max) = iter.size_hint();
        self.try_reserve(allocator, max.unwrap_or(min)).unwrap();
        unsafe {
            self.extend_within_capacity(&mut iter);

            for item in iter {
                self.push(allocator, item);
            }
        }
    }

    unsafe fn extend_within_capacity(&mut self, iter: &mut impl Iterator<Item = T>) {
        let n = self.remaining_capacity() as BufferSize;
        if n == 0 {
            return;
        }

        let mut ptr = self.data_ptr().add(self.len());
        let mut count = 0;

        unsafe {
            for item in iter {
                ptr::write(ptr, item);
                ptr = ptr.add(1);
                count += 1;
                if count == n {
                    break;
                }
            }
            self.header.len += count;
        }
    }

    /// Allocate a clone of this buffer.
    ///
    /// The provided allocator does not need to be the one this raw vector was created with.
    /// The returned raw vector is considered to be created with the provided allocator.
    pub fn clone_buffer<A: Allocator>(&self, allocator: &A) -> Self
    where
        T: Clone,
    {
        self.clone_buffer_with_capacity(allocator, self.len())
    }

    /// Allocate a clone of this buffer with a different capacity
    ///
    /// The capacity must be at least as large as the buffer's length.
    pub fn clone_buffer_with_capacity<A: Allocator>(&self, allocator: &A, cap: usize) -> Self
    where
        T: Clone,
    {
        let mut clone =
            Self::try_with_capacity(allocator, cap.max(self.len())).unwrap();

        unsafe {
            raw::extend_from_slice_assuming_capacity(clone.data_ptr(), &mut clone.header, self.as_slice());
        }

        clone
    }

    // Note: Marking this #[inline(never)] is a pretty large regression in the push benchmark.
    #[cold]
    unsafe fn try_realloc_additional<A: Allocator>(&mut self, allocator: &A, additional: usize) -> Result<(), AllocError> {
        let new_cap = grow_amortized(self.len(), additional);
        if new_cap < self.len() {
            return Err(AllocError);
        }

        self.try_realloc_with_capacity(allocator, new_cap)
    }

    pub fn truncate(&mut self, new_len: usize) {
        let old_len = self.header.len as usize;
        if old_len <= new_len {
            return;
        }

        unsafe {
            let mut elt = self.data_ptr().add(new_len);
            let end = self.data_ptr().add(old_len);
            while elt < end {
                ptr::drop_in_place(elt);
                elt = elt.add(1)
            }
        }

        self.header.len = new_len as u32;
    }

    #[cold]
    unsafe fn try_realloc_with_capacity<A: Allocator>(&mut self, allocator: &A, new_cap: usize) -> Result<(), AllocError> {
        type R = DefaultRefCount;

        if new_cap == 0 {
            self.deallocate(allocator);
            return Ok(());
        }

        let new_layout = buffer_layout::<Header<R, A>, T>(new_cap).unwrap();

        let old_len = self.len();
        if old_len > new_cap {
            self.truncate(new_cap);
        }

        let new_alloc = if self.header.cap == 0 {
            allocator.allocate(new_layout)
        } else {
            let old_cap = self.capacity();
            let old_ptr = self.base_ptr(allocator);
            let old_layout = buffer_layout::<Header<R, A>, T>(old_cap).unwrap();
            let new_layout = buffer_layout::<Header<R, A>, T>(new_cap).unwrap();

            if new_layout.size() >= old_layout.size() {
                allocator.grow(old_ptr, old_layout, new_layout)
            } else {
                allocator.shrink(old_ptr, old_layout, new_layout)
            }
        };

        // If the new capacity is lower than the length, we already dropped
        // the elements after the new capacity, so make sure to write the
        // length before propagating a potential allocation error.
        self.header.len = self.header.len.min(new_cap as u32);

        // If allocation failed, we return an error here.
        let new_alloc = new_alloc?;

        // The data and capacity, however must be only written once we know that
        // the grow/shrink operation suceeded.
        let new_data_ptr = crate::raw::data_ptr::<Header<R, A>, T>(new_alloc.cast());
        self.data = NonNull::new_unchecked(new_data_ptr);
        self.header.cap = new_cap as u32;

        Ok(())
    }

    /// Attempts to move this raw vector into another allocator.
    ///
    /// All of the data is copied over into a new allocation in `new_allocator` after which
    /// the old allocation is deallocated from `old_allocator`.
    ///
    /// If this method succeeds, `new_allocator` becomes the allocator currently used by this
    /// raw vector.
    ///
    /// # Safety
    ///
    /// The provided `old_allocator` must be the one currently used by this raw vector.
    ///
    /// # Error
    ///
    /// If reallocation fails:
    ///  - The vector remains in its current state, still associated to the old allocator.
    ///  - An allocation error is returned.
    #[cold]
    pub unsafe fn try_reallocate_in<OldA: Allocator, NewA: Allocator>(
        &mut self,
        old_allocator: &OldA,
        new_allocator: &NewA,
        new_cap: usize,
    ) -> Result<(), AllocError> {
        type R = DefaultRefCount;

        let new_layout = buffer_layout::<Header<R, NewA>, T>(new_cap).unwrap();

        if new_cap == 0 {
            self.deallocate(old_allocator);
            return Ok(());
        }

        let new_alloc = if new_cap > 0 {
            Some(new_allocator.allocate(new_layout)?)
        } else {
            None
        };

        let old_len = self.len();
        if old_len > new_cap {
            self.truncate(new_cap);
        }

        let old_cap = self.capacity();

        let old_base_ptr = if old_cap > 0 {
            Some(self.base_ptr(old_allocator))
        } else {
            None
        };

        self.data = if let Some(new_alloc) = new_alloc {
            let new_data_ptr = crate::raw::data_ptr::<Header<R, NewA>, T>(new_alloc.cast());

            let copy_size = old_len.min(new_cap);
            if copy_size > 0 {
                let old_data_ptr = self.data_ptr();
                ptr::copy_nonoverlapping(old_data_ptr, new_data_ptr, copy_size);
            }

            NonNull::new_unchecked(new_data_ptr)
        } else {
            NonNull::dangling()
        };

        self.header.cap = new_cap as u32;
        self.header.len = self.header.len.min(new_cap as u32);

        if let Some(old_base_ptr) = old_base_ptr {
            let old_layout = buffer_layout::<Header<R, OldA>, T>(old_cap).unwrap();
            old_allocator.deallocate(old_base_ptr, old_layout);
        }

        Ok(())
    }

    // Deallocates the memory, does not drop the vector's content.
    unsafe fn deallocate_buffer<A: Allocator>(&mut self, allocator: &A) {
        let layout = buffer_layout::<Header<DefaultRefCount, A>, T>(self.capacity()).unwrap();
        let ptr = self.base_ptr(allocator);

        allocator.deallocate(ptr, layout);

        self.header.cap = 0;
        self.header.len = 0;
        self.data = NonNull::dangling();
    }

    /// Tries to reserve at least enough space for `additional` extra items.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    #[inline]
    pub unsafe fn try_reserve<A: Allocator>(&mut self, allocator: &A, additional: usize) -> Result<(), AllocError> {
        if self.remaining_capacity() < additional {
            self.try_realloc_additional(allocator, additional)?;
        }

        Ok(())
    }

    /// Tries to reserve the minimum capacity for at least `additional` elements to be inserted in the given vector.
    ///
    /// Unlike `try_reserve`, this will not deliberately over-allocate to speculatively avoid frequent allocations.
    /// After calling `reserve_exact`, capacity will be greater than or equal to `self.len() + additional`.
    /// This will also allocate if the vector is not unique.
    /// Does nothing if the capacity is already sufficient and the vector is unique.
    ///
    /// Note that the allocator may give the collection more space than it requests. Therefore, capacity can not
    /// be relied upon to be precisely minimal. Prefer `try_reserve` if future insertions are expected.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    pub unsafe fn try_reserve_exact<A: Allocator>(&mut self, allocator: &A, additional: usize) -> Result<(), AllocError> {
        if self.remaining_capacity() >= additional {
            return Ok(());
        }

        self.try_realloc_with_capacity(allocator, self.len() + additional)
    }

    /// Shrinks the capacity of the vector with a lower bound.
    ///
    /// The capacity will remain at least as large as both the length and the supplied value.
    /// If the current capacity is less than the lower limit, this is a no-op.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    pub unsafe fn shrink_to<A: Allocator>(&mut self, allocator: &A, min_capacity: usize)
    {
        let min_capacity = min_capacity.max(self.len());
        if self.capacity() <= min_capacity {
            return;
        }

        self.try_realloc_with_capacity(allocator, min_capacity).unwrap();
    }

    /// Shrinks the capacity of the vector as much as possible.
    ///
    /// # Safety
    ///
    /// The provided allocator must be the one currently used by this raw vector.
    pub unsafe fn shrink_to_fit<A: Allocator>(&mut self, allocator: &A)
    {
        self.shrink_to(allocator, self.len())
    }

    /// Removes the specified range from the vector in bulk, returning all
    /// removed elements as an iterator. 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.
    ///
    /// # Panics
    ///
    /// Panics if the starting point is greater than the end point or if
    /// the end point is greater than the length of the vector.
    ///
    /// # Leaking
    ///
    /// If the returned iterator goes out of scope without being dropped (due to
    /// [`mem::forget`], for example), the vector may have lost and leaked
    /// elements arbitrarily, including elements outside the range.
    ///
    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
    where
        R: RangeBounds<usize>,
    {
        // Memory safety
        //
        // When the Drain is first created, it shortens the length of
        // the source vector to make sure no uninitialized or moved-from elements
        // are accessible at all if the Drain's destructor never gets to run.
        //
        // Drain will ptr::read out the values to remove.
        // When finished, remaining tail of the vec is copied back to cover
        // the hole, and the vector length is restored to the new length.
        //
        use core::ops::Bound::*;
        let len = self.len();
        let end = match range.end_bound() {
            Included(n) => *n + 1,
            Excluded(n) => *n,
            Unbounded => len
        };
        let start = match range.start_bound() {
            Included(n) => *n,
            Excluded(n) => *n+1,
            Unbounded => 0
        };
        assert!(end <= len);
        assert!(start <= end);

        unsafe {
            // Set self.vec length's to start, to be safe in case Drain is leaked
            self.header.len = start as u32;
            let range_slice = core::slice::from_raw_parts(self.data.as_ptr().add(start), end - start);
            Drain {
                tail_start: end,
                tail_len: len - end,
                iter: range_slice.iter(),
                vec: NonNull::from(self),
            }
        }
    }

    /// Creates a splicing iterator that replaces the specified range in the vector
    /// with the given `replace_with` iterator and yields the removed items.
    /// `replace_with` does not need to be the same length as `range`.
    ///
    /// `range` is removed even if the iterator is not consumed until the end.
    ///
    /// It is unspecified how many elements are removed from the vector
    /// if the `Splice` value is leaked.
    ///
    /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
    ///
    /// This is optimal if:
    ///
    /// * The tail (elements in the vector after `range`) is empty,
    /// * or `replace_with` yields fewer or equal elements than `range`’s length
    /// * or the lower bound of its `size_hint()` is exact.
    ///
    /// Otherwise, a temporary vector is allocated and the tail is moved twice.
    ///
    /// # Panics
    ///
    /// Panics if the starting point is greater than the end point or if
    /// the end point is greater than the length of the vector.
    ///
    pub unsafe fn splice<'l, A, R, I>(
        &'l mut self,
        allocator: &'l A,
        range: R,
        replace_with: I
    ) -> Splice<'l, <I as IntoIterator>::IntoIter, A>
    where
        A: Allocator,
        R: RangeBounds<usize>,
        I: IntoIterator<Item = T>,
    {
        Splice {
            drain: self.drain(range),
            replace_with: replace_with.into_iter(),
            allocator,
        }
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
    /// This method operates in place, visiting each element exactly once in the
    /// original order, and preserves the order of the retained elements.
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.retain_mut(|elem| f(elem));
    }

    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
    ///
    /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
    /// This method operates in place, visiting each element exactly once in the
    /// original order, and preserves the order of the retained elements.
    pub fn retain_mut<F>(&mut self, mut f: F)
    where
        F: FnMut(&mut T) -> bool,
    {
        let original_len = self.len();
        // Avoid double drop if the drop guard is not executed,
        // since we may make some holes during the process.
        self.header.len = 0;

        // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
        //      |<-              processed len   ->| ^- next to check
        //                  |<-  deleted cnt     ->|
        //      |<-              original_len                          ->|
        // Kept: Elements which predicate returns true on.
        // Hole: Moved or dropped element slot.
        // Unchecked: Unchecked valid elements.
        //
        // This drop guard will be invoked when predicate or `drop` of element panicked.
        // It shifts unchecked elements to cover holes and `set_len` to the correct length.
        // In cases when predicate and `drop` never panick, it will be optimized out.
        struct BackshiftOnDrop<'a, T> {
            v: &'a mut RawVector<T>,
            processed_len: usize,
            deleted_cnt: usize,
            original_len: usize,
        }

        impl<T> Drop for BackshiftOnDrop<'_, T> {
            fn drop(&mut self) {
                if self.deleted_cnt > 0 {
                    // SAFETY: Trailing unchecked items must be valid since we never touch them.
                    unsafe {
                        ptr::copy(
                            self.v.as_ptr().add(self.processed_len),
                            self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
                            self.original_len - self.processed_len,
                        );
                    }
                }
                // SAFETY: After filling holes, all items are in contiguous memory.
                self.v.header.len = (self.original_len - self.deleted_cnt) as u32;
            }
        }

        let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };

        fn process_loop<F, T, const DELETED: bool>(
            original_len: usize,
            f: &mut F,
            g: &mut BackshiftOnDrop<'_, T>,
        ) where
            F: FnMut(&mut T) -> bool,
        {
            while g.processed_len != original_len {
                // SAFETY: Unchecked element must be valid.
                let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.processed_len) };
                if !f(cur) {
                    // Advance early to avoid double drop if `drop_in_place` panicked.
                    g.processed_len += 1;
                    g.deleted_cnt += 1;
                    // SAFETY: We never touch this element again after dropped.
                    unsafe { ptr::drop_in_place(cur) };
                    // We already advanced the counter.
                    if DELETED {
                        continue;
                    } else {
                        break;
                    }
                }
                if DELETED {
                    // SAFETY: `deleted_cnt` > 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 = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt);
                        ptr::copy_nonoverlapping(cur, hole_slot, 1);
                    }
                }
                g.processed_len += 1;
            }
        }

        // Stage 1: Nothing was deleted.
        process_loop::<F, T, false>(original_len, &mut f, &mut g);

        // Stage 2: Some elements were deleted.
        process_loop::<F, T, true>(original_len, &mut f, &mut g);

        // All item are processed. This can be optimized to `set_len` by LLVM.
        drop(g);
    }

    /// Transfers ownership of this raw vector's contents to the one that is returned, and leaves
    /// this one empty and unallocated.
    pub fn take(&mut self) -> Self {
        mem::replace(self, RawVector::new())
    }
}

impl<T: PartialEq<T>> PartialEq<RawVector<T>> for RawVector<T> {
    fn eq(&self, other: &Self) -> bool {
        self.as_slice() == other.as_slice()
    }
}

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

impl<T: Eq> Eq for RawVector<T> {

}

impl<T> AsRef<[T]> for RawVector<T> {
    fn as_ref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T> AsMut<[T]> for RawVector<T> {
    fn as_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T> Default for RawVector<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<'a, T> IntoIterator for &'a RawVector<T> {
    type Item = &'a T;
    type IntoIter = core::slice::Iter<'a, T>;
    fn into_iter(self) -> core::slice::Iter<'a, T> {
        self.as_slice().iter()
    }
}

impl<'a, T> IntoIterator for &'a mut RawVector<T> {
    type Item = &'a mut T;
    type IntoIter = core::slice::IterMut<'a, T>;
    fn into_iter(self) -> core::slice::IterMut<'a, T> {
        self.as_mut_slice().iter_mut()
    }
}

impl<T, I> Index<I> for RawVector<T>
where
    I: core::slice::SliceIndex<[T]>,
{
    type Output = <I as core::slice::SliceIndex<[T]>>::Output;
    fn index(&self, index: I) -> &Self::Output {
        self.as_slice().index(index)
    }
}

impl<T, I> IndexMut<I> for RawVector<T>
where
    I: core::slice::SliceIndex<[T]>,
{
    fn index_mut(&mut self, index: I) -> &mut Self::Output {
        self.as_mut_slice().index_mut(index)
    }
}

impl<T> Deref for RawVector<T> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T> DerefMut for RawVector<T> {
    fn deref_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T: Debug> Debug for RawVector<T> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> Result<(), core::fmt::Error> {
        self.as_slice().fmt(f)
    }
}

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


/// A heap allocated, mutable contiguous buffer containing elements of type `T`.
///
/// <svg width="280" height="120" viewBox="0 0 74.08 31.75" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg"><defs><linearGradient id="a"><stop offset="0" stop-color="#491c9c"/><stop offset="1" stop-color="#d54b27"/></linearGradient><linearGradient xlink:href="#a" id="b" gradientUnits="userSpaceOnUse" x1="6.27" y1="34.86" x2="87.72" y2="13.24" gradientTransform="translate(-2.64 -18.48)"/></defs><rect width="10.57" height="10.66" x="7.94" y="18.45" ry="1.37" fill="#3dbdaa"/><circle cx="12.7" cy="18.48" r=".79" fill="#666"/><path d="M12.7 18.48c0-3.93 7.14-1.28 7.14-5.25" fill="none" stroke="#999" stroke-width=".86" stroke-linecap="round"/><rect width="68.79" height="10.58" x="2.65" y="2.68" ry="1.37" fill="url(#b)"/><rect width="15.35" height="9.51" x="3.18" y="3.21" ry=".9" fill="#78a2d4"/><rect width="9.26" height="9.51" x="19.85" y="3.2" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="29.64" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="39.43" y="3.22" ry=".9" fill="#eaa577"/><rect width="9.26" height="9.51" x="49.22" y="3.21" ry=".9" fill="#eaa577"/><circle cx="62.84" cy="7.97" r=".66" fill="#eaa577"/><circle cx="64.7" cy="7.97" r=".66" fill="#eaa577"/><circle cx="66.55" cy="7.97" r=".66" fill="#eaa577"/></svg>
///
/// Similar in principle to a `Vec<T>`.
/// It can be converted for free into a reference counted `SharedVector<T>` or `AtomicSharedVector<T>`.
///
/// Unique and shared vectors expose similar functionality. `Vector` takes advantage of
/// the guaranteed uniqueness at the type level to provide overall faster operations than its
/// shared counterparts, while its memory layout makes it very cheap to convert to a shared vector
/// (involving no allocation or copy).
///
/// # Internal representation
///
/// `Vector` stores its length and capacity inline and points to the first element of the
/// allocated buffer. Room for a header is left uninitialized before the elements so that the
/// vector can be converted into a `SharedVector` or `AtomicSharedVector` without reallocating
/// the storage.
///
/// Internally, `Vector` is built on top of `RawVector`.
pub struct Vector<T, A: Allocator = Global> {
    pub(crate) raw: RawVector<T>,
    pub(crate) allocator: A,
}

impl<T> Vector<T, Global> {
    /// Creates an empty vector.
    ///
    /// This does not allocate memory.
    pub fn new() -> Vector<T, Global> {
        Vector {
            raw: RawVector::new(),
            allocator: Global,
        }
    }



    /// Creates an empty pre-allocated vector with a given storage capacity.
    ///
    /// Does not allocate memory if `cap` is zero.
    pub fn with_capacity(cap: usize) -> Vector<T, Global> {
        Self::try_with_capacity(cap).unwrap()
    }

    /// Creates an empty pre-allocated vector with a given storage capacity.
    ///
    /// Does not allocate memory if `cap` is zero.
    pub fn try_with_capacity(cap: usize) -> Result<Vector<T, Global>, AllocError> {
        Vector::try_with_capacity_in(cap, Global)
    }

    pub fn from_slice(data: &[T]) -> Self
    where
        T: Clone,
    {
        Vector { raw: RawVector::try_from_slice(&Global, data).unwrap(), allocator: Global }
    }

    /// Creates a vector with `n` clones of `elem`.
    pub fn from_elem(elem: T, n: usize) -> Vector<T, Global>
    where
        T: Clone,
    {
        Vector { raw: RawVector::try_from_elem(&Global, elem, n).unwrap(), allocator: Global }
    }
}

impl<T, A: Allocator> Vector<T, A> {
    /// Creates an empty vector without allocating memory.
    pub fn new_in(allocator: A) -> Self {
        Self::try_with_capacity_in(0, allocator).unwrap()
    }

    /// Creates an empty pre-allocated vector with a given storage capacity.
    ///
    /// Does not allocate memory if `cap` is zero.
    pub fn with_capacity_in(cap: usize, allocator: A) -> Self {
        Self::try_with_capacity_in(cap, allocator).unwrap()
    }

    /// Creates an empty pre-allocated vector with a given storage capacity.
    ///
    /// Does not allocate memory if `cap` is zero.
    pub fn try_with_capacity_in(cap: usize, allocator: A) -> Result<Vector<T, A>, AllocError> {
        let raw = RawVector::try_with_capacity(&allocator, cap)?;

        Ok(Vector { raw, allocator })
    }

    /// Attempts to move this vector into another allocator.
    pub fn try_reallocate_in<NewA: Allocator>(&mut self, new_allocator: NewA, new_cap: usize) -> Result<Vector<T, NewA>, AllocError> {
        unsafe {
            self.raw.try_reallocate_in(&self.allocator, &new_allocator, new_cap)?;
        }

        Ok(Vector {
            raw: mem::take(&mut self.raw),
            allocator: new_allocator,
        })
    }

    #[inline(always)]
    /// Returns `true` if the vector contains no elements.
    pub fn is_empty(&self) -> bool {
        self.raw.is_empty()
    }

    #[inline(always)]
    /// Returns the number of elements in the vector, also referred to as its ‘length’.
    pub fn len(&self) -> usize {
        self.raw.len()
    }

    #[inline(always)]
    /// Returns the total number of elements the vector can hold without reallocating.
    pub fn capacity(&self) -> usize {
        self.raw.capacity()
    }

    /// Returns number of elements that can be added without reallocating.
    #[inline(always)]
    pub fn remaining_capacity(&self) -> usize {
        self.raw.remaining_capacity()
    }

    /// Returns a reference to the underlying allocator.
    #[inline(always)]
    pub fn allocator(&self) -> &A {
        &self.allocator
    }

    #[inline(always)]
    pub fn as_slice(&self) -> &[T] {
        self.raw.as_slice()
    }

    #[inline(always)]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        self.raw.as_mut_slice()
    }

    /// Clears the vector, removing all values.
    pub fn clear(&mut self) {
        unsafe {
            raw::clear(self.raw.data_ptr(), &mut self.raw.header)
        }
    }

    unsafe fn into_header_buffer<R>(mut self) -> HeaderBuffer<T, R, A>
    where
        R: RefCount,
    {
        debug_assert!(self.raw.header.cap != 0);
        unsafe {
            let mut header = raw::header_from_data_ptr(self.raw.data);

            *header.as_mut() = raw::Header {
                vec: VecHeader {
                    len: self.raw.header.len,
                    cap: self.raw.header.cap,
                },
                ref_count: R::new(1),
                allocator: ptr::read(&mut self.allocator),
            };

            mem::forget(self);

            HeaderBuffer::from_raw(header)
        }
    }

    /// Make this vector immutable.
    ///
    /// This operation is cheap, the underlying storage does not not need
    /// to be reallocated.
    #[inline]
    pub fn into_shared(self) -> SharedVector<T, A>
    where
        A: Allocator + Clone,
    {
        if self.raw.header.cap == 0 {
            return SharedVector::try_with_capacity_in(0, self.allocator.clone()).unwrap();
        }
        unsafe {
            let inner = self.into_header_buffer::<DefaultRefCount>();
            SharedVector { inner }
        }
    }

    /// Make this vector immutable.
    ///
    /// This operation is cheap, the underlying storage does not not need
    /// to be reallocated.
    #[inline]
    pub fn into_shared_atomic(self) -> AtomicSharedVector<T, A>
    where
        A: Allocator + Clone,
    {
        if self.raw.header.cap == 0 {
            return AtomicSharedVector::try_with_capacity_in(0, self.allocator.clone()).unwrap();
        }
        unsafe {
            let inner = self.into_header_buffer::<AtomicRefCount>();
            AtomicSharedVector { inner }
        }
    }

    /// Appends an element to the back of a collection.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity exceeds `u32::MAX` bytes.
    #[inline(always)]
    pub fn push(&mut self, val: T) {
        unsafe {
            self.raw.push(&self.allocator, val);
        }
    }

    /// Appends an element if there is sufficient spare capacity, otherwise an error is returned
    /// with the element.
    ///
    /// Unlike push this method will not reallocate when there’s insufficient capacity.
    /// The caller should use reserve or try_reserve to ensure that there is enough capacity.
    #[inline(always)]
    pub fn push_within_capacity(&mut self, val: T) -> Result<(), T> {
        self.raw.push_within_capacity(val)
    }

    /// Removes the last element from the vector and returns it, or `None` if it is empty.
    #[inline(always)]
    pub fn pop(&mut self) -> Option<T> {
        self.raw.pop()
    }

    /// Removes and returns the element at position `index` within the vector,
    /// shifting all elements after it to the left.
    ///
    /// # Panics
    ///
    /// Panics if `index` is out of bounds.
    ///
    #[inline(always)]
    pub fn remove(&mut self, index: usize) -> T {
        self.raw.remove(index)
    }

    /// Removes an element from the vector and returns it.
    ///
    /// The removed element is replaced by the last element of the vector.
    ///
    /// # Panics
    ///
    /// Panics if index is out of bounds.
    #[inline(always)]
    pub fn swap_remove(&mut self, idx: usize) -> T {
        self.raw.swap_remove(idx)
    }

    /// Inserts an element at position `index` within the vector, shifting all
    /// elements after it to the right.
    ///
    /// # Panics
    ///
    /// Panics if `index > len`.
    #[inline(always)]
    pub fn insert(&mut self, index: usize, element: T) {
       unsafe { self.raw.insert(&self.allocator, index, element) }
    }

    /// Clones and appends the contents of the slice to the back of a collection.
    #[inline(always)]
    pub fn extend_from_slice(&mut self, data: &[T])
    where
        T: Clone,
    {
        unsafe {
            self.raw.extend_from_slice(&self.allocator, data)
        }
    }

    /// Moves all the elements of `other` into `self`, leaving `other` empty.
    #[inline(always)]
    pub fn append(&mut self, other: &mut Self)
    where
        T: Clone,
    {
        unsafe {
            self.raw.append(&self.allocator, &mut other.raw)
        }
    }

    /// Appends the contents of an iterator to the back of a collection.
    #[inline(always)]
    pub fn extend(&mut self, data: impl IntoIterator<Item = T>) {
        unsafe {
            self.raw.extend(&self.allocator, data)
        }
    }

    /// Allocates a clone of this buffer.
    #[inline(always)]
    pub fn clone_buffer(&self) -> Self
    where
        T: Clone,
        A: Clone,
    {
        Vector {
            raw: self.raw.clone_buffer(&self.allocator),
            allocator: self.allocator.clone(),
        }
    }

    /// Allocate a clone of this buffer with a different capacity
    ///
    /// The capacity must be at least as large as the buffer's length.
    #[inline(always)]
    pub fn clone_buffer_with_capacity(&self, cap: usize) -> Self
    where
        T: Clone,
        A: Clone,
    {
        Vector {
            raw: self.raw.clone_buffer_with_capacity(&self.allocator, cap),
            allocator: self.allocator.clone(),
        }
    }

    #[inline(always)]
    pub fn reserve(&mut self, additional: usize) {
        unsafe {
            self.raw.try_reserve(&self.allocator, additional).unwrap()
        }
    }

    #[inline(always)]
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), AllocError> {
        unsafe {
            self.raw.try_reserve(&self.allocator, additional)
        }
    }

    /// Reserves the minimum capacity for at least `additional` elements to be inserted in the given vector.
    ///
    /// Unlike `reserve`, this will not deliberately over-allocate to speculatively avoid frequent allocations.
    /// After calling `try_reserve_exact`, capacity will be greater than or equal to `self.len() + additional` if
    /// it returns `Ok(())`.
    /// This will also allocate if the vector is not unique.
    /// Does nothing if the capacity is already sufficient and the vector is unique.
    ///
    /// Note that the allocator may give the collection more space than it requests. Therefore, capacity can not
    /// be relied upon to be precisely minimal. Prefer `try_reserve` if future insertions are expected.
    pub fn reserve_exact(&mut self, additional: usize)
    where
        T: Clone,
    {
        self.try_reserve_exact(additional).unwrap();
    }

    /// Tries to reserve the minimum capacity for at least `additional` elements to be inserted in the given vector.
    ///
    /// Unlike `try_reserve`, this will not deliberately over-allocate to speculatively avoid frequent allocations.
    /// After calling `reserve_exact`, capacity will be greater than or equal to `self.len() + additional`.
    /// This will also allocate if the vector is not unique.
    /// Does nothing if the capacity is already sufficient and the vector is unique.
    ///
    /// Note that the allocator may give the collection more space than it requests. Therefore, capacity can not
    /// be relied upon to be precisely minimal. Prefer `try_reserve` if future insertions are expected.
    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), AllocError> {
        unsafe {
            self.raw.try_reserve_exact(&self.allocator, additional)
        }
    }

    /// Shrinks the capacity of the vector with a lower bound.
    ///
    /// The capacity will remain at least as large as both the length and the supplied value.
    /// If the current capacity is less than the lower limit, this is a no-op.
    #[inline(always)]
    pub fn shrink_to(&mut self, min_capacity: usize)
    where
        T: Clone,
    {
        unsafe {
            self.raw.shrink_to(&self.allocator, min_capacity)
        }
    }

    /// Shrinks the capacity of the vector as much as possible.
    #[inline(always)]
    pub fn shrink_to_fit(&mut self)
    where
        T: Clone,
    {
        unsafe {
            self.raw.shrink_to_fit(&self.allocator)
        }
    }

    /// Removes the specified range from the vector in bulk, returning all
    /// removed elements as an iterator. 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.
    ///
    /// # Panics
    ///
    /// Panics if the starting point is greater than the end point or if
    /// the end point is greater than the length of the vector.
    ///
    /// # Leaking
    ///
    /// If the returned iterator goes out of scope without being dropped (due to
    /// [`mem::forget`], for example), the vector may have lost and leaked
    /// elements arbitrarily, including elements outside the range.
    ///
    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
    where
        R: RangeBounds<usize>,
    {
        self.raw.drain(range)
    }

    /// Creates a splicing iterator that replaces the specified range in the vector
    /// with the given `replace_with` iterator and yields the removed items.
    /// `replace_with` does not need to be the same length as `range`.
    ///
    /// `range` is removed even if the iterator is not consumed until the end.
    ///
    /// It is unspecified how many elements are removed from the vector
    /// if the `Splice` value is leaked.
    ///
    /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
    ///
    /// This is optimal if:
    ///
    /// * The tail (elements in the vector after `range`) is empty,
    /// * or `replace_with` yields fewer or equal elements than `range`’s length
    /// * or the lower bound of its `size_hint()` is exact.
    ///
    /// Otherwise, a temporary vector is allocated and the tail is moved twice.
    ///
    /// # Panics
    ///
    /// Panics if the starting point is greater than the end point or if
    /// the end point is greater than the length of the vector.
    ///
    pub fn splice<R, I>(
        &mut self,
        range: R,
        replace_with: I
    ) -> Splice<'_, <I as IntoIterator>::IntoIter, A>
    where
        R: RangeBounds<usize>,
        I: IntoIterator<Item = T>,
    {
        unsafe { self.raw.splice(&self.allocator, range, replace_with) }
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
    /// This method operates in place, visiting each element exactly once in the
    /// original order, and preserves the order of the retained elements.
    pub fn retain<F>(&mut self, f: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.raw.retain(f)
    }

    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
    ///
    /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
    /// This method operates in place, visiting each element exactly once in the
    /// original order, and preserves the order of the retained elements.
    pub fn retain_mut<F>(&mut self, f: F)
    where
        F: FnMut(&mut T) -> bool,
    {
        self.raw.retain_mut(f)
    }

    #[inline(always)]
    pub fn take(&mut self) -> Self
    where
        A: Clone,
    {
        let other = Vector {
            raw: self.raw.take(),
            allocator: self.allocator.clone(),
        };

        other
    }
}

impl<T, A: Allocator> Drop for Vector<T, A> {
    fn drop(&mut self) {
        unsafe {
            self.raw.deallocate(&self.allocator)
        }
    }
}

impl<T: Clone, A: Allocator + Clone> Clone for Vector<T, A> {
    fn clone(&self) -> Self {
        self.clone_buffer()
    }
}

impl<T: PartialEq<T>, A: Allocator> PartialEq<Vector<T, A>> for Vector<T, A> {
    fn eq(&self, other: &Self) -> bool {
        self.as_slice() == other.as_slice()
    }
}

impl<T: PartialEq<T>, A: Allocator> PartialEq<&[T]> for Vector<T, A> {
    fn eq(&self, other: &&[T]) -> bool {
        self.as_slice() == *other
    }
}

impl<T, A: Allocator> AsRef<[T]> for Vector<T, A> {
    fn as_ref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T, A: Allocator> AsMut<[T]> for Vector<T, A> {
    fn as_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T> Default for Vector<T, Global> {
    fn default() -> Self {
        Self::new()
    }
}

impl<'a, T, A: Allocator> IntoIterator for &'a Vector<T, A> {
    type Item = &'a T;
    type IntoIter = core::slice::Iter<'a, T>;
    fn into_iter(self) -> core::slice::Iter<'a, T> {
        self.as_slice().iter()
    }
}

impl<'a, T, A: Allocator> IntoIterator for &'a mut Vector<T, A> {
    type Item = &'a mut T;
    type IntoIter = core::slice::IterMut<'a, T>;
    fn into_iter(self) -> core::slice::IterMut<'a, T> {
        self.as_mut_slice().iter_mut()
    }
}

impl<T, A: Allocator, I> Index<I> for Vector<T, A>
where
    I: core::slice::SliceIndex<[T]>,
{
    type Output = <I as core::slice::SliceIndex<[T]>>::Output;
    fn index(&self, index: I) -> &Self::Output {
        self.as_slice().index(index)
    }
}

impl<T, A: Allocator, I> IndexMut<I> for Vector<T, A>
where
    I: core::slice::SliceIndex<[T]>,
{
    fn index_mut(&mut self, index: I) -> &mut Self::Output {
        self.as_mut_slice().index_mut(index)
    }
}

impl<T, A: Allocator> Deref for Vector<T, A> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T, A: Allocator> DerefMut for Vector<T, A> {
    fn deref_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T: Debug, A: Allocator> Debug for Vector<T, A> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> Result<(), core::fmt::Error> {
        self.as_slice().fmt(f)
    }
}

impl<T: Clone, A: Allocator + Clone> From<SharedVector<T, A>> for Vector<T, A> {
    fn from(shared: SharedVector<T, A>) -> Self {
        shared.into_unique()
    }
}

impl<T: Clone, A: Allocator + Clone> From<AtomicSharedVector<T, A>> for Vector<T, A> {
    fn from(shared: AtomicSharedVector<T, A>) -> Self {
        shared.into_unique()
    }
}

impl<T: core::hash::Hash, A: Allocator> core::hash::Hash for Vector<T, A> {
    fn hash<H>(&self, state: &mut H) where H: core::hash::Hasher {
        self.as_slice().hash(state)
    }
}

#[test]
fn bump_alloc() {
    use blink_alloc::BlinkAlloc;

    let allocator = BlinkAlloc::new();

    {
        let mut v1: Vector<u32, &BlinkAlloc> = Vector::try_with_capacity_in(4, &allocator).unwrap();
        v1.push(0);
        v1.push(1);
        v1.push(2);
        assert_eq!(v1.capacity(), 4);
        assert_eq!(v1.as_slice(), &[0, 1, 2]);

        // let mut v2 = crate::vector!(@ &allocator [10, 11]);
        let mut v2 = crate::vector!([10, 11] in &allocator);
        assert_eq!(v2.capacity(), 2);

        assert_eq!(v2.as_slice(), &[10, 11]);

        v1.push(3);
        v1.push(4);

        assert_eq!(v1.as_slice(), &[0, 1, 2, 3, 4]);

        assert!(v1.capacity() > 4);

        v2.push(12);
        v2.push(13);
        v2.push(14);

        let v2 = v2.into_shared();

        assert_eq!(v1.as_slice(), &[0, 1, 2, 3, 4]);
        assert_eq!(v2.as_slice(), &[10, 11, 12, 13, 14]);
    }
}

#[test]
fn basic_unique() {
    fn num(val: u32) -> Box<u32> {
        Box::new(val)
    }

    let mut a = Vector::with_capacity(256);

    a.push(num(0));
    a.push(num(1));
    a.push(num(2));

    let a = a.into_shared();

    assert_eq!(a.len(), 3);

    assert_eq!(a.as_slice(), &[num(0), num(1), num(2)]);

    assert!(a.is_unique());

    let b = Vector::from_slice(&[num(0), num(1), num(2), num(3), num(4)]);

    assert_eq!(b.as_slice(), &[num(0), num(1), num(2), num(3), num(4)]);

    let c = a.clone_buffer();
    assert!(!c.ptr_eq(&a));

    let a2 = a.new_ref();
    assert!(a2.ptr_eq(&a));
    assert!(!a.is_unique());
    assert!(!a2.is_unique());

    mem::drop(a2);

    assert!(a.is_unique());

    let _ = c.clone_buffer();
    let _ = b.clone_buffer();

    let mut d = Vector::with_capacity(64);
    d.extend_from_slice(&[num(0), num(1), num(2)]);
    d.extend_from_slice(&[]);
    d.extend_from_slice(&[num(3), num(4)]);

    assert_eq!(d.as_slice(), &[num(0), num(1), num(2), num(3), num(4)]);
}

#[test]
fn shrink() {
    let mut v: Vector<u32> = Vector::with_capacity(32);
    v.shrink_to(8);
}

#[test]
fn zst() {
    let mut v = Vector::new();
    v.push(());
    v.push(());
    v.push(());
    v.push(());

    assert_eq!(v.len(), 4);
}

#[test]
fn dyn_allocator() {
    let allocator: &dyn Allocator = &Global;
    let mut v = crate::vector!([1u32, 2, 3] in allocator);

    v.push(4);

    assert_eq!(&v[..], &[1, 2, 3, 4]);
}

#[test]
fn borrowd_dyn_alloc() {
    struct DataStructure<'a> {
        data: Vector<u32, &'a dyn Allocator>,
    }

    impl DataStructure<'static> {
        fn new() -> DataStructure<'static> {
            DataStructure {
                data: Vector::new_in(&Global as &'static dyn Allocator)
            }
        }
    }

    impl<'a> DataStructure<'a> {
        fn new_in(allocator: &'a dyn Allocator) -> DataStructure<'a> {
            DataStructure { data: Vector::new_in(allocator) }
        }

        fn push(&mut self, val: u32) {
            self.data.push(val);
        }
    }

    let mut ds1 = DataStructure::new();
    ds1.push(1);

    let alloc = Global;
    let mut ds2 = DataStructure::new_in(&alloc);
    ds2.push(2);

}

#[test]
fn splice1() {
    let mut vec = Vector::new();
    vec.splice(0..0, vec![Box::new(1); 5].into_iter());
    vec.splice(0..0, vec![Box::new(2); 5].into_iter());
}

#[test]
fn drain1() {
    let mut vectors: [Vector<Box<u32>>; 4] = [
        Vector::new(),
        Vector::new(),
        Vector::new(),
        Vector::new(),
    ];
    vectors[0].shrink_to(3906369431118283232);
    vectors[2].extend_from_slice(&[Box::new(1), Box::new(2), Box::new(3)]);
    let vec = &mut vectors[2];
    let len = vec.len();
    let start = if len > 0 { 16059518370053021184 % len } else { 0 };
    let end = 16059518370053021185.min(len);
    vectors[2].drain(start..end);
}

#[test]
fn reallocate_in() {
    pub use crate::alloc::Global;
    use std::rc::Rc;

    let alloc1 = Global;
    let alloc2 = Global;

    let mut vec = Vector::new_in(alloc1);
    let val = Rc::new(());

    for _ in 0..8 {
        vec.push(val.clone());
    }

    assert_eq!(Rc::strong_count(&val), 9);

    let mut vec = vec.try_reallocate_in(alloc2, 4).unwrap();

    assert_eq!(vec.len(), 4);
    assert_eq!(vec.capacity(), 4);
    assert_eq!(Rc::strong_count(&val), 5);

    for _ in 0..12 {
        vec.push(val.clone());
    }

    assert_eq!(vec.len(), 16);
    assert!(vec.capacity() >= 16);
    assert_eq!(Rc::strong_count(&val), 17);

    let vec = vec.try_reallocate_in(alloc1, 0).unwrap();

    assert_eq!(vec.len(), 0);
    assert_eq!(vec.capacity(), 0);
    assert_eq!(Rc::strong_count(&val), 1);
}

#[test]
fn extend_within_capacity() {
    use std::sync::atomic::{AtomicUsize, Ordering};
    static COUNTER: AtomicUsize = AtomicUsize::new(0);

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

    let values = [
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
        Foo,
    ];

    let n = values.len();
    let cap;

    let mut vector = RawVector::new();
    unsafe {
        vector.try_reserve(&Global, 4).unwrap();
        cap = vector.capacity();
        // What's mportant here is that we exercise the code path
        // where we extend within a capcity that is inferior to the
        // amount of elements that we need to push. So if the default
        // capacity grows and this fails, just increase the number of
        // elements in values.
        assert!(cap < n);

        let mut iter = values.into_iter();

        vector.extend_within_capacity(&mut iter);

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

    assert_eq!(COUNTER.load(Ordering::SeqCst), n - cap);

    vector.clear();

    assert_eq!(COUNTER.load(Ordering::SeqCst), n);

    unsafe {
        vector.deallocate(&Global);
    }
}