#![allow(incomplete_features)]
#![feature(doc_cfg)]
#![feature(untagged_unions)]
#![feature(transparent_unions)]
#![feature(const_fn_union)]
#![feature(core_intrinsics)]
#![feature(const_fn)]
#![feature(const_generics)]
#![feature(maybe_uninit_ref)]
#![feature(maybe_uninit_extra)]
#![feature(exact_size_is_empty)]

//Literally just for stable-sort.
#[cfg(feature = "std")]
extern crate alloc;

use std::cmp::{Ord, PartialEq};
use std::iter::{FromIterator, FusedIterator};
use std::marker::PhantomData;
use std::mem::ManuallyDrop;
use std::ops::{Bound::Excluded, Bound::Included, Bound::Unbounded, Index, IndexMut, RangeBounds};
use std::ptr;

#[derive(Copy)]
#[repr(transparent)]
pub union MaybeUninit<T> {
    uninit: (),
    value: ManuallyDrop<T>,
}

impl<T: Copy> Clone for MaybeUninit<T> {
    #[inline(always)]
    fn clone(&self) -> Self {
        *self
    }
}

impl<T> MaybeUninit<T> {
    #[inline(always)]
    pub const fn uninit() -> MaybeUninit<T> {
        MaybeUninit { uninit: () }
    }

    #[inline(always)]
    pub fn write(&mut self, val: T) {
        unsafe {
            self.value = ManuallyDrop::new(val);
        }
    }

    #[inline(always)]
    pub const unsafe fn assume_init(self) -> T {
        ManuallyDrop::into_inner(self.value)
    }

    #[inline(always)]
    pub unsafe fn read(&self) -> T {
        (&*self.value as *const T).read()
    }

    #[inline(always)]
    pub unsafe fn get_ref(&self) -> &T {
        &self.value
    }

    #[inline(always)]
    pub unsafe fn get_mut(&mut self) -> &mut T {
        &mut self.value
    }
}

///Similar to [Iter](std::slice::IterMut), but specifically implemented with StaticVecs in mind.
pub struct StaticVecIterConst<'a, T: 'a> {
    pub(crate) start: *const T,
    pub(crate) end: *const T,
    pub(crate) marker: PhantomData<&'a T>,
}

///Similar to [IterMut](std::slice::IterMut), but specifically implemented with StaticVecs in mind.
pub struct StaticVecIterMut<'a, T: 'a> {
    pub(crate) start: *mut T,
    pub(crate) end: *mut T,
    pub(crate) marker: PhantomData<&'a mut T>,
}

impl<'a, T: 'a> Iterator for StaticVecIterConst<'a, T> {
    type Item = &'a T;
    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        if self.start < self.end {
            unsafe {
                let res = Some(&*self.start);
                self.start = self.start.offset(1);
                res
            }
        } else {
            None
        }
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = distance_between(self.end, self.start);
        (len, Some(len))
    }
}

impl<'a, T: 'a> DoubleEndedIterator for StaticVecIterConst<'a, T> {
    #[inline(always)]
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.end > self.start {
            unsafe {
                self.end = self.end.offset(-1);
                Some(&*self.end)
            }
        } else {
            None
        }
    }
}

impl<'a, T: 'a> ExactSizeIterator for StaticVecIterConst<'a, T> {
    #[inline(always)]
    fn len(&self) -> usize {
        distance_between(self.end, self.start)
    }

    #[inline(always)]
    fn is_empty(&self) -> bool {
        distance_between(self.end, self.start) == 0
    }
}

impl<'a, T: 'a> FusedIterator for StaticVecIterConst<'a, T> {}

impl<'a, T: 'a> Iterator for StaticVecIterMut<'a, T> {
    type Item = &'a mut T;
    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        if self.start < self.end {
            unsafe {
                let res = Some(&mut *self.start);
                self.start = self.start.offset(1);
                res
            }
        } else {
            None
        }
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = distance_between(self.end, self.start);
        (len, Some(len))
    }
}

impl<'a, T: 'a> DoubleEndedIterator for StaticVecIterMut<'a, T> {
    #[inline(always)]
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.end > self.start {
            unsafe {
                self.end = self.end.offset(-1);
                Some(&mut *self.end)
            }
        } else {
            None
        }
    }
}

impl<'a, T: 'a> ExactSizeIterator for StaticVecIterMut<'a, T> {
    #[inline(always)]
    fn len(&self) -> usize {
        distance_between(self.end, self.start)
    }

    #[inline(always)]
    fn is_empty(&self) -> bool {
        distance_between(self.end, self.start) == 0
    }
}

impl<'a, T: 'a> FusedIterator for StaticVecIterMut<'a, T> {}

///A [Vec](alloc::vec::Vec)-like struct (mostly directly API-compatible where it can be)
///implemented with const generics around a static array of fixed `N` capacity.
pub struct StaticVec<T, const N: usize> {
    data: [MaybeUninit<T>; N],
    length: usize,
}

impl<T, const N: usize> StaticVec<T, { N }> {
    ///Returns a new StaticVec instance.
    #[inline(always)]
    pub const fn new() -> Self {
        unsafe {
            Self {
                //Sound because data is an array of MaybeUninit<T>, not an array of T.
                data: MaybeUninit::uninit().assume_init(),
                length: 0,
            }
        }
    }

    ///Returns a new StaticVec instance filled with the contents, if any, of a slice.
    ///If the slice has a length greater than the StaticVec's declared capacity,
    ///any contents after that point are ignored.
    ///Locally requires that `T` implements [Copy](std::marker::Copy) to avoid soundness issues.
    #[inline]
    pub fn new_from_slice(values: &[T]) -> Self
    where
        T: Copy,
    {
        unsafe {
            let mut data_: [MaybeUninit<T>; N] = MaybeUninit::uninit().assume_init();
            let fill_length = values.len().min(N);
            values
                .as_ptr()
                .copy_to_nonoverlapping(data_.as_mut_ptr() as *mut T, fill_length);
            Self {
                data: data_,
                length: fill_length,
            }
        }
    }

    ///Returns a new StaticVec instance filled with the return value of an initializer function.
    ///The length field of the newly created StaticVec will be equal to its capacity.
    ///
    ///Example usage:
    ///```
    ///use staticvec::*;
    ///
    ///fn main() {
    ///  let mut i = 0;
    ///  let v = StaticVec::<i32, 64>::filled_with(|| { i += 1; i });
    ///  assert_eq!(v.len(), 64);
    ///  assert_eq!(v[0], 1);
    ///  assert_eq!(v[1], 2);
    ///  assert_eq!(v[2], 3);
    ///  assert_eq!(v[3], 4);
    ///}
    /// ```
    #[inline]
    pub fn filled_with<F>(mut initializer: F) -> Self
    where
        F: FnMut() -> T,
    {
        let mut res = Self::new();
        for i in 0..N {
            unsafe {
                res.data.get_unchecked_mut(i).write(initializer());
                res.length += 1;
            }
        }
        res
    }

    ///Returns the current length of the StaticVec.
    ///Just as for a normal [Vec](alloc::vec::Vec), this means the number of elements that
    ///have been added to it with `push`, `insert`, etc. except in the case
    ///that it has been set directly with the unsafe `set_len` function.
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.length
    }

    ///Returns the total capacity of the StaticVec.
    ///This is always equivalent to the generic `N` parameter it was declared with,
    ///which determines the fixed size of the backing array.
    #[inline(always)]
    pub const fn capacity(&self) -> usize {
        N
    }

    ///Directly sets the `length` field of the StaticVec to `new_len`. Useful if you intend
    ///to write to it solely element-wise, but marked unsafe due to how it creates the potential for reading
    ///from unitialized memory later on.
    #[inline(always)]
    pub unsafe fn set_len(&mut self, new_len: usize) {
        self.length = new_len;
    }

    ///Returns true if the current length of the StaticVec is 0.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    ///Returns true if the current length of the StaticVec is greater than 0.
    #[inline(always)]
    pub fn is_not_empty(&self) -> bool {
        self.length > 0
    }

    ///Returns true if the current length of the StaticVec is equal to its capacity.
    #[inline(always)]
    pub fn is_full(&self) -> bool {
        self.length == N
    }

    ///Returns true if the current length of the StaticVec is less than its capacity.
    #[inline(always)]
    pub fn is_not_full(&self) -> bool {
        self.length < N
    }

    ///Returns a constant pointer to the first element of the StaticVec's internal array.
    #[inline(always)]
    pub fn as_ptr(&self) -> *const T {
        self.data.as_ptr() as *const T
    }

    ///Returns a mutable pointer to the first element of the StaticVec's internal array.
    #[inline(always)]
    pub fn as_mut_ptr(&mut self) -> *mut T {
        self.data.as_mut_ptr() as *mut T
    }

    ///Returns a constant reference to a slice of the StaticVec's inhabited area.
    #[inline(always)]
    pub fn as_slice(&self) -> &[T] {
        unsafe {
            &*(self.data.get_unchecked(0..self.length) as *const [MaybeUninit<T>] as *const [T])
        }
    }

    ///Returns a mutable reference to a slice of the StaticVec's inhabited area.
    #[inline(always)]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        unsafe {
            &mut *(self.data.get_unchecked_mut(0..self.length) as *mut [MaybeUninit<T>]
                as *mut [T])
        }
    }

    ///Appends a value to the end of the StaticVec without asserting that
    ///its current length is less than `N`.
    #[inline(always)]
    pub unsafe fn push_unchecked(&mut self, value: T) {
        self.data.get_unchecked_mut(self.length).write(value);
        self.length += 1;
    }

    ///Pops a value from the end of the StaticVec and returns it directly without asserting that
    ///the StaticVec's current length is greater than 0.
    #[inline(always)]
    pub unsafe fn pop_unchecked(&mut self) -> T {
        self.length -= 1;
        self.data.get_unchecked(self.length).read()
    }

    ///Asserts that the current length of the StaticVec is less than `N`,
    ///and if so appends a value to the end of it.
    #[inline(always)]
    pub fn push(&mut self, value: T) {
        assert!(self.length < N);
        unsafe {
            self.push_unchecked(value);
        }
    }

    ///Removes the value at the last position of the StaticVec and returns it in `Some` if
    ///the StaticVec has a current length greater than 0, and returns `None` otherwise.
    #[inline(always)]
    pub fn pop(&mut self) -> Option<T> {
        if self.length == 0 {
            None
        } else {
            Some(unsafe { self.pop_unchecked() })
        }
    }

    ///Asserts that `index` is less than the current length of the StaticVec,
    ///and if so removes the value at that position and returns it. Any values
    ///that exist in later positions are shifted to the left.
    #[inline]
    pub fn remove(&mut self, index: usize) -> T {
        assert!(index < self.length);
        unsafe {
            let p = self.as_mut_ptr().add(index);
            let res = p.read();
            p.offset(1).copy_to(p, self.length - index - 1);
            self.length -= 1;
            res
        }
    }

    ///Removes the first instance of `item` from the StaticVec if the item exists.
    #[inline(always)]
    pub fn remove_item(&mut self, item: &T) -> Option<T>
    where
        T: PartialEq,
    {
        //Adapted this from normal Vec's implementation.
        if let Some(pos) = self.iter().position(|x| *x == *item) {
            Some(self.remove(pos))
        } else {
            None
        }
    }

    ///Asserts that `index` is less than the current length of the StaticVec,
    ///and if so removes the value at that position and returns it, and then
    ///moves the last value in the StaticVec into the empty slot.
    #[inline(always)]
    pub fn swap_remove(&mut self, index: usize) -> T {
        assert!(index < self.length);
        unsafe {
            let last_value = self.data.get_unchecked(self.length - 1).read();
            self.length -= 1;
            self.as_mut_ptr().add(index).replace(last_value)
        }
    }

    ///Asserts that the current length of the StaticVec is less than `N` and that
    ///`index` is less than the length, and if so inserts `value` at that position.
    ///Any values that exist in later positions are shifted to the right.
    #[inline]
    pub fn insert(&mut self, index: usize, value: T) {
        assert!(self.length < N && index <= self.length);
        unsafe {
            let p = self.as_mut_ptr().add(index);
            p.copy_to(p.offset(1), self.length - index);
            p.write(value);
            self.length += 1;
        }
    }

    ///Removes all contents from the StaticVec and sets its length back to 0.
    #[inline(always)]
    pub fn clear(&mut self) {
        unsafe {
            ptr::drop_in_place(self.as_mut_slice());
        }
        self.length = 0;
    }

    ///Performs an stable in-place sort of the StaticVec's inhabited area.
    ///Locally requires that `T` implements [Ord](std::cmp::Ord) to make the sorting possible.
    #[cfg(feature = "std")]
    #[inline(always)]
    pub fn sort(&mut self)
    where
        T: Ord,
    {
        self.as_mut_slice().sort();
    }

    ///Performs an unstable in-place sort of the StaticVec's inhabited area.
    ///Locally requires that `T` implements [Ord](std::cmp::Ord) to make the sorting possible.
    #[inline(always)]
    pub fn sort_unstable(&mut self)
    where
        T: Ord,
    {
        self.as_mut_slice().sort_unstable();
    }

    ///Reverses the contents of the StaticVec's inhabited area in-place.
    #[inline(always)]
    pub fn reverse(&mut self) {
        self.as_mut_slice().reverse();
    }

    ///Returns a separate, stable-sorted StaticVec of the contents of the
    ///StaticVec's inhabited area without modifying the original data.
    ///Locally requires that `T` implements [Copy](std::marker::Copy) to avoid soundness issues,
    ///and [Ord](std::cmp::Ord) to make the sorting possible.
    #[cfg(feature = "std")]
    #[inline]
    pub fn sorted(&self) -> Self
    where
        T: Copy + Ord,
    {
        unsafe {
            let mut res = Self::new();
            res.length = self.length;
            self.as_ptr()
                .copy_to_nonoverlapping(res.as_mut_ptr(), self.length);
            res.sort();
            res
        }
    }

    ///Returns a separate, unstable-sorted StaticVec of the contents of the
    ///StaticVec's inhabited area without modifying the original data.
    ///Locally requires that `T` implements [Copy](std::marker::Copy) to avoid soundness issues,
    ///and [Ord](std::cmp::Ord) to make the sorting possible.
    #[inline]
    pub fn sorted_unstable(&self) -> Self
    where
        T: Copy + Ord,
    {
        unsafe {
            let mut res = Self::new();
            res.length = self.length;
            self.as_ptr()
                .copy_to_nonoverlapping(res.as_mut_ptr(), self.length);
            res.sort_unstable();
            res
        }
    }

    ///Returns a separate, reversed StaticVec of the contents of the StaticVec's
    ///inhabited area without modifying the original data.
    ///Locally requires that `T` implements [Copy](std::marker::Copy) to avoid soundness issues.
    #[inline]
    pub fn reversed(&self) -> Self
    where
        T: Copy,
    {
        let mut res = Self::new();
        res.length = self.length;
        unsafe {
            reverse_copy(
                self.as_ptr(),
                self.as_ptr().add(self.length),
                res.as_mut_ptr(),
            );
        }
        res
    }

    ///Copies and appends all elements, if any, of a slice to the StaticVec.
    ///If the slice has a length greater than the StaticVec's declared capacity,
    ///any contents after that point are ignored.
    ///Unlike the implementation of this function for [Vec](alloc::vec::Vec), no iterator is used,
    ///just a single pointer-copy call.
    ///Locally requires that `T` implements [Copy](std::marker::Copy) to avoid soundness issues.
    #[inline]
    pub fn extend_from_slice(&mut self, other: &[T])
    where
        T: Copy,
    {
        let mut added_length = other.len();
        if self.length + added_length > N {
            added_length = N - self.length;
        }
        unsafe {
            other
                .as_ptr()
                .copy_to_nonoverlapping(self.as_mut_ptr().add(self.length), added_length);
        }
        self.length += added_length;
    }

    ///Removes the specified range of elements from the StaticVec and returns them in a new one.
    #[inline]
    pub fn drain<R>(&mut self, range: R) -> Self
    //No Copy bounds here because the original StaticVec gives up all access to the values in question.
    where
        R: RangeBounds<usize>,
    {
        //Borrowed this part from normal Vec's implementation.
        let start = match range.start_bound() {
            Included(&idx) => idx,
            Excluded(&idx) => idx + 1,
            Unbounded => 0,
        };
        let end = match range.end_bound() {
            Included(&idx) => idx + 1,
            Excluded(&idx) => idx,
            Unbounded => self.length,
        };
        assert!(start <= end && end <= self.length);
        let mut res = Self::new();
        res.length = end - start;
        unsafe {
            self.as_ptr()
                .add(start)
                .copy_to_nonoverlapping(res.as_mut_ptr(), res.length);
            self.as_ptr()
                .add(end)
                .copy_to(self.as_mut_ptr().add(start), self.length - end);
        }
        self.length -= res.length;
        res
    }

    ///Removes all elements in the StaticVec for which `filter` returns true and
    ///returns them in a new one.
    #[inline]
    pub fn drain_filter<F>(&mut self, mut filter: F) -> Self
    where
        F: FnMut(&mut T) -> bool,
    {
        let mut res = Self::new();
        let old_length = self.length;
        self.length = 0;
        unsafe {
            for i in 0..old_length {
                let val = self.as_mut_ptr().add(i);
                if filter(&mut *val) {
                    res.data.get_unchecked_mut(res.length).write(val.read());
                    res.length += 1;
                } else if res.length > 0 {
                    self.as_ptr()
                        .add(i)
                        .copy_to_nonoverlapping(self.as_mut_ptr().add(i - res.length), 1);
                }
            }
        }
        self.length = old_length - res.length;
        res
    }

    ///Removes all elements in the StaticVec for which `filter` returns false.
    #[inline(always)]
    pub fn retain<F>(&mut self, mut filter: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.drain_filter(|val| !filter(val));
    }

    ///Shortens the StaticVec, keeping the first `length` elements and dropping the rest.
    #[inline(always)]
    pub fn truncate(&mut self, length: usize) {
        let old_length = self.length;
        self.length = length;
        unsafe {
            ptr::drop_in_place(
                &mut *(self.data.get_unchecked_mut(length..old_length) as *mut [MaybeUninit<T>]
                    as *mut [T]),
            );
        }
    }

    #[inline]
    pub fn split_off(&mut self, at: usize) -> Self {
        assert!(at <= self.length);
        let split_length = self.length - at;
        let mut split = Self::new();
        self.length = at;
        split.length = split_length;
        unsafe {
            self.as_ptr()
                .add(at)
                .copy_to_nonoverlapping(split.as_mut_ptr(), split_length);
        }
        split
    }

    ///Returns a `StaticVecIterConst` over the StaticVec's inhabited area.
    #[inline(always)]
    pub fn iter<'a>(&'a self) -> StaticVecIterConst<'a, T> {
        unsafe {
            StaticVecIterConst::<'a, T> {
                start: self.as_ptr(),
                end: self.as_ptr().add(self.length),
                marker: PhantomData,
            }
        }
    }

    ///Returns a `StaticVecIterMut` over the StaticVec's inhabited area.
    #[inline(always)]
    pub fn iter_mut<'a>(&'a mut self) -> StaticVecIterMut<'a, T> {
        unsafe {
            StaticVecIterMut::<'a, T> {
                start: self.as_mut_ptr(),
                end: self.as_mut_ptr().add(self.length),
                marker: PhantomData,
            }
        }
    }
}

impl<T, const N: usize> Default for StaticVec<T, { N }> {
    ///Calls `new`.
    #[inline(always)]
    fn default() -> Self {
        Self::new()
    }
}

impl<T, const N: usize> Drop for StaticVec<T, { N }> {
    ///Calls `clear` through the StaticVec before dropping it.
    #[inline(always)]
    fn drop(&mut self) {
        self.clear();
    }
}

impl<T, const N: usize> Index<usize> for StaticVec<T, { N }> {
    type Output = T;
    ///Asserts that `index` is less than the current length of the StaticVec,
    ///and if so returns the value at that position as a constant reference.
    #[inline(always)]
    fn index(&self, index: usize) -> &Self::Output {
        assert!(index < self.length);
        unsafe { self.data.get_unchecked(index).get_ref() }
    }
}

impl<T, const N: usize> IndexMut<usize> for StaticVec<T, { N }> {
    ///Asserts that `index` is less than the current length of the StaticVec,
    ///and if so returns the value at that position as a mutable reference.
    #[inline(always)]
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        assert!(index < self.length);
        unsafe { self.data.get_unchecked_mut(index).get_mut() }
    }
}

impl<T: Copy, const N: usize> From<&[T]> for StaticVec<T, { N }> {
    ///Creates a new StaticVec instance from the contents of `values`, using
    ///[new_from_slice](crate::StaticVec::new_from_slice) internally.
    #[inline(always)]
    fn from(values: &[T]) -> Self {
        Self::new_from_slice(values)
    }
}

impl<'a, T: 'a, const N: usize> IntoIterator for &'a StaticVec<T, { N }> {
    type IntoIter = StaticVecIterConst<'a, T>;
    type Item = <Self::IntoIter as Iterator>::Item;
    ///Returns a `StaticVecIterConst` over the StaticVec's inhabited area.
    #[inline(always)]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T: 'a, const N: usize> IntoIterator for &'a mut StaticVec<T, { N }> {
    type IntoIter = StaticVecIterMut<'a, T>;
    type Item = <Self::IntoIter as Iterator>::Item;
    ///Returns a `StaticVecIterMut` over the StaticVec's inhabited area.
    #[inline(always)]
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T, const N: usize> Extend<T> for StaticVec<T, { N }> {
    ///Appends all elements, if any, from `iter` to the StaticVec. If `iter` has a size greater than
    ///the StaticVec's capacity, any items after that point are ignored.
    #[inline]
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let spots_left = N - self.length;
        unsafe {
            let mut p = self.as_mut_ptr().add(self.length);
            for val in iter.into_iter().take(spots_left) {
                p.write(val);
                p = p.offset(1);
                self.length += 1;
            }
        }
    }
}

impl<'a, T: Copy + 'a, const N: usize> Extend<&'a T> for StaticVec<T, { N }> {
    ///Appends all elements, if any, from `iter` to the StaticVec. If `iter` has a size greater than
    ///the StaticVec's capacity, any items after that point are ignored.
    #[inline]
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        let spots_left = N - self.length;
        unsafe {
            let mut p = self.as_mut_ptr().add(self.length);
            for val in iter.into_iter().take(spots_left) {
                p.write(*val);
                p = p.offset(1);
                self.length += 1;
            }
        }
    }
}

impl<'a, T: Copy + 'a, const N: usize> Extend<&'a mut T> for StaticVec<T, { N }> {
    ///Appends all elements, if any, from `iter` to the StaticVec. If `iter` has a size greater than
    ///the StaticVec's capacity, any items after that point are ignored.
    #[inline]
    fn extend<I: IntoIterator<Item = &'a mut T>>(&mut self, iter: I) {
        let spots_left = N - self.length;
        unsafe {
            let mut p = self.as_mut_ptr().add(self.length);
            for val in iter.into_iter().take(spots_left) {
                p.write(*val);
                p = p.offset(1);
                self.length += 1;
            }
        }
    }
}

impl<T, const N: usize> FromIterator<T> for StaticVec<T, { N }> {
    ///Creates a new StaticVec instance from the elements, if any, of `iter`.
    ///If `iter` has a size greater than the StaticVec's capacity, any items after
    ///that point are ignored.
    #[inline]
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut res = Self::new();
        res.extend(iter);
        res
    }
}

#[inline(always)]
pub(crate) fn distance_between<T>(self_: *const T, origin: *const T) -> usize {
    unsafe {
        std::intrinsics::exact_div(
            (self_ as usize).wrapping_sub(origin as usize),
            std::intrinsics::size_of::<T>(),
        )
    }
}

#[inline(always)]
pub(crate) fn reverse_copy<T>(first: *const T, mut last: *const T, mut result: *mut T)
where
    T: Copy,
{
    while first != last {
        unsafe {
            last = last.offset(-1);
            *result = *last;
            result = result.offset(1);
        }
    }
}

#[inline(always)]
pub fn new_from_value<T, const COUNT: usize>(value: T) -> StaticVec<T, { COUNT }>
where
    T: Copy,
{
    let mut res = StaticVec::<T, { COUNT }>::new();
    res.length = COUNT;
    for i in 0..COUNT {
        unsafe {
            res.data.get_unchecked_mut(i).write(value);
        }
    }
    res
}

///Creates a new StaticVec from a `vec!`-style pseudo-slice.
///The newly created StaticVec will have a `capacity` and `length` exactly equal to the
///number of elements, if any, in the slice.
#[macro_export]
macro_rules! staticvec {
  (@put_one $val:expr) => (1);
  ($val:expr; $n:expr) => (
    new_from_value::<_, $n>($val)
  );
  ($($val:expr),*$(,)*) => ({
    let mut res = StaticVec::<_, {0$(+staticvec!(@put_one $val))*}>::new();
    {
      #[allow(unused_unsafe)]
      unsafe {
        ($({
          res.push_unchecked($val);
        }),*)
      }
    };
    res
  });
}

#[derive(Copy, Clone)]
struct MyStruct {
    s: &'static str,
}

struct MyOtherStruct {
    s: &'static str,
}

impl Drop for MyOtherStruct {
    fn drop(&mut self) {
        println!("Dropping MyOtherStruct with value: {}", self.s)
    }
}

pub fn main() {
    let mut v = StaticVec::<f32, 24>::new();
    for i in 0..v.capacity() {
        v.push(i as f32);
    }
    for f in &v {
        println!("{}", f);
    }
    v.clear();
    v.insert(0, 47.6);
    v.insert(1, 48.6);
    v.insert(2, 49.6);
    v.insert(v.len() - 1, 50.6);
    v.insert(v.len() - 2, 51.6);
    v.insert(v.len() - 3, 52.6);
    for f in &v {
        println!("{}", f);
    }
    for f in 0..v.len() {
        println!("{}", v[f]);
    }
    v.remove(1);
    v.remove(2);
    for f in &v {
        println!("{}", f);
    }
    let mut va = StaticVec::<usize, 1024>::new();
    for i in 0..va.capacity() {
        va.push(i);
    }
    let ia = va.remove_item(&512).unwrap();
    let ib = va.remove_item(&511).unwrap();
    println!("{}", ia);
    println!("{}", ib);
    va.remove(10);
    va.remove(11);
    va.remove(12);
    va.remove(13);
    va.remove(14);
    va.remove(15);
    va.insert(10, 99);
    va.insert(11, 99);
    va.insert(12, 99);
    va.insert(13, 99);
    va.insert(14, 99);
    va.insert(15, 99);
    for i in 0..va.len() {
        println!("{}", va[i])
    }
    for i in &va {
        println!("{}", i)
    }
    while va.is_not_empty() {
        println!("{}", va.pop().unwrap());
    }
    let mut vb = StaticVec::<char, 26>::new();
    vb.push('a');
    vb.push('b');
    vb.push('c');
    vb.push('d');
    vb.push('e');
    vb.push('f');
    vb.push('g');
    vb.push('h');
    vb.push('i');
    vb.push('j');
    vb.push('k');
    vb.push('l');
    vb.push('m');
    vb.push('n');
    vb.push('o');
    vb.push('p');
    vb.push('q');
    vb.push('r');
    vb.push('s');
    vb.push('t');
    vb.push('u');
    vb.push('v');
    vb.push('w');
    vb.push('x');
    vb.push('y');
    vb.push('z');
    vb.remove(2);
    vb.remove(1);
    vb.remove(vb.len() - 1);
    for i in 0..vb.len() {
        println!("{}", vb[i]);
    }
    for s in &vb {
        println!("{}", s);
    }
    let pb = vb.as_mut_ptr();
    unsafe {
        println!("{}", *pb);
        println!("{}", *pb.add(1).add(1));
    }
    let pbc = vb.as_ptr();
    unsafe {
        println!("{}", *pbc);
        println!("{}", *pbc.add(1).add(1));
    }
    vb.clear();
    for _i in 0..vb.capacity() {
        vb.push('h');
    }
    while vb.is_not_empty() {
        println!("{}", vb.remove(0));
    }
    vb.push('g');
    vb.push('f');
    vb.push('e');
    vb.push('d');
    vb.push('c');
    vb.push('b');
    vb.push('a');
    let vbm = vb.as_mut_slice();
    vbm.sort_unstable();
    for s in vbm {
        println!("{}", s);
    }
    let vbmb = vb.as_mut_slice();
    vbmb.reverse();
    for s in vbmb {
        println!("{}", s);
    }
    for s in &vb.sorted_unstable() {
        println!("{}", s);
    }
    for s in &vb.reversed() {
        println!("{}", s);
    }
    vb.reverse();
    vb.reverse();
    for s in &vb {
        println!("{}", s);
    }
    vb.clear();
    let mut vu = StaticVec::<usize, 8>::new();
    vu.extend_from_slice(&[1, 2, 3, 4, 5, 6, 7, 8]);
    println!("{}", vu.drain(2..5).iter().find(|&&i| i == 4).unwrap());
    let vvu: StaticVec<usize, 4> = vu.iter().copied().collect();
    for i in &vvu {
        println!("{}", i);
    }
    let mut x = StaticVec::<i32, 4>::new();
    x.push(1);
    x.push(2);
    x.push(3);
    x.push(4);
    let mut y = StaticVec::<i32, 4>::new();
    y.push(4);
    y.push(3);
    y.push(2);
    y.push(1);
    let mut z = StaticVec::<i32, 4>::new();
    z.push(1);
    z.push(2);
    z.push(3);
    z.push(4);
    let mut w = StaticVec::<i32, 4>::new();
    w.push(4);
    w.push(3);
    w.push(2);
    w.push(1);
    let mut ww = StaticVec::<&StaticVec<i32, 4>, 4>::new();
    ww.push(&x);
    ww.push(&y);
    ww.push(&z);
    ww.push(&w);
    for v in &ww {
        for i in *v {
            println!("{}", i);
        }
    }
    let mut empty = StaticVec::<&'static str, 0>::new();
    empty.sort_unstable();
    empty.reverse();
    for s in empty.as_slice() {
        println!("{}", s);
    }
    for s in empty.as_mut_slice() {
        println!("{}", s);
    }
    for s in &empty {
        println!("{}", s);
    }
    for s in &mut empty {
        println!("{}", s);
    }
    for s in &empty.reversed() {
        println!("{}", s);
    }
    for s in &empty.sorted_unstable() {
        println!("{}", s);
    }
    let mut msv = StaticVec::<MyStruct, 4>::new();
    msv.push(MyStruct { s: "a" });
    msv.push(MyStruct { s: "b" });
    msv.push(MyStruct { s: "c" });
    msv.push(MyStruct { s: "d" });
    for ms in &msv.reversed() {
        println!("{}", ms.s);
    }
    while msv.is_not_empty() {
        println!("{}", msv.remove(msv.len() - 1).s)
    }
    let v2 = StaticVec::<i32, 8>::new_from_slice(&[1, 2, 3, 4, 5, 6, 7, 8]);
    let mut it2 = v2.iter();
    println!("{:?}", it2.size_hint());
    while let Some(_i) = it2.next() {
        println!("{:?}", it2.size_hint());
        println!("{:?}", it2.len());
    }
    if let Some(i) = v2.iter().rfind(|&&x| x == 2) {
        println!("{}", i);
    }
    for v in &staticvec![
        staticvec![12.0, 14.0],
        staticvec![16.0, 18.0],
        staticvec![20.0, 22.0],
        staticvec![24.0, 26.0],
        staticvec![28.0, 30.0],
        staticvec![32.0, 34.0],
        staticvec![36.0, 38.0],
        staticvec![40.0, 42.0]
    ] {
        for f in v.iter().skip(1) {
            println!("{}", f);
        }
    }
    let numbers = staticvec![1, 2, 3, 4, 5];
    let zero = "0".to_string();
    let result = numbers
        .iter()
        .rfold(zero, |acc, &x| format!("({} + {})", x, acc));
    println!("{}", result);
    let mut strings = staticvec!["foo", "bar", "baz", "qux"];
    println!("{}", strings.swap_remove(1));
    for s in &strings {
        println!("{}", s);
    }
    println!("{}", strings.swap_remove(0));
    for s in &strings {
        println!("{}", s);
    }
    let mut structs = staticvec![
        MyOtherStruct { s: "a" },
        MyOtherStruct { s: "b" },
        MyOtherStruct { s: "c" },
        MyOtherStruct { s: "d" },
        MyOtherStruct { s: "e" },
        MyOtherStruct { s: "f" },
    ];
    let mut newstructs = structs.drain_filter(|s| s.s < "d");
    for s in &structs {
        println!("{}", s.s);
    }
    for s in &newstructs {
        println!("{}", s.s);
    }
    newstructs.retain(|s| s.s == "a");
    for s in &newstructs {
        println!("{}", s.s);
    }
    let mut morestructs = staticvec![
        MyOtherStruct { s: "a" },
        MyOtherStruct { s: "b" },
        MyOtherStruct { s: "c" },
        MyOtherStruct { s: "d" },
        MyOtherStruct { s: "e" },
        MyOtherStruct { s: "f" },
    ];
    morestructs.truncate(3);
    for s in &morestructs {
        println!("{}", s.s);
    }
    let mut twelve = StaticVec::<f32, 12>::new();
    twelve.extend_from_slice(&[1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
    for f in &twelve {
        println!("{}", f);
    }
    twelve.extend([1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0].iter());
    for f in &twelve {
        println!("{}", f);
    }
    println!("{}", twelve.capacity());
    println!("{}", twelve.len());
    let single_element_macro_test = staticvec!["ABCD"; 26];
    for s in &single_element_macro_test {
        println!("{}", s);
    }
    let mut eight_from = StaticVec::<usize, 8>::from(staticvec![1, 2, 3, 4, 5, 6, 7, 8].as_slice());
    for i in &eight_from {
        println!("{}", i);
    }
    for i in &eight_from.split_off(4) {
        println!("{}", i);
    }
    let v = staticvec![MyStruct{s: "hey"}; 26].split_off(13);
    for ms in &v {
        println!("{}", ms.s);
    }
    static mut YYYY: StaticVec<f32, 12> = StaticVec::<f32, 12>::new();
    unsafe {
    for i in 0..12 {
        YYYY.push_unchecked(i as f32);
    }
    for f in &YYYY {
        println!("{}", f);
    }
     }
}