#![feature(const_generics, specialization, maybe_uninit_extra, maybe_uninit_slice)]

use std::convert::TryInto;
use std::mem::{ManuallyDrop, MaybeUninit};
use std::ops::{Deref, DerefMut};

#[cfg(test)]
mod test;

mod extend;

/// An array backed fixed capcity vector
pub struct ArrayVec<T, const N: usize> {
    arr: [MaybeUninit<T>; N],
    len: usize,
}

/// Creates a new empty array
impl<T, const N: usize> Default for ArrayVec<T, { N }> {
    fn default() -> Self {
        ArrayVec {
            arr: unsafe {
                // this is safe because the array is an array of `MaybeUninit<T>`
                MaybeUninit::uninit().assume_init()
            },
            len: 0,
        }
    }
}

impl<T, const N: usize> ArrayVec<T, { N }> {
    /// The pointer to the start of the array, only valid to read for `self.len()` elements
    ///
    /// This pointer is not valid to write to, use `as_mut_ptr` instead
    pub fn as_ptr(&self) -> *const T {
        MaybeUninit::first_ptr(&self.arr)
    }

    /// The pointer to the start of the array, only valid to read for `self.len()` elements, and to write for N elements
    pub fn as_mut_ptr(&mut self) -> *mut T {
        MaybeUninit::first_ptr_mut(&mut self.arr)
    }

    /// As a shared reference to a slice
    pub fn as_slice(&self) -> &[T] {
        self
    }

    /// As a unique reference to a slice
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        self
    }

    /// Puts an element onto the end of the `ArrayVec`
    pub fn push(&mut self, value: T) -> Result<(), T> {
        let res: Result<(), [T; 1]> = self.push_array([value]);

        res.map_err(|[val]| val)
    }

    /// Insert a single element into the `ArrayVec` at the given index
    pub fn insert(&mut self, value: T, index: usize) -> Result<(), T> {
        let res: Result<(), [T; 1]> = self.insert_array([value], index);

        res.map_err(|[val]| val)
    }

    /// Removes the last element from the `ArrayVec`
    pub fn pop(&mut self) -> Option<T> {
        let [val]: [T; 1] = self.pop_array()?;

        Some(val)
    }

    /// Put all of the elements of the array into the end of the `ArrayVec`
    pub fn push_array<const M: usize>(&mut self, array: [T; M]) -> Result<(), [T; M]> {
        if self.len + M <= N {
            unsafe {
                (self.as_mut_ptr().add(self.len) as *mut [T; M]).write(array);
            }
            self.len += M;
            Ok(())
        } else {
            Err(array)
        }
    }

    /// Insert all of the elements of the array into the `ArrayVec` at the given index
    pub fn insert_array<const M: usize>(
        &mut self,
        arr: [T; M],
        index: usize,
    ) -> Result<(), [T; M]> {
        if index <= self.len && self.len + M <= N {
            unsafe {
                let ptr = self.as_mut_ptr().add(index);

                std::ptr::copy(ptr, ptr.add(M), M);

                (ptr as *mut [T; M]).write(arr);
            }

            self.len += M;

            Ok(())
        } else {
            Err(arr)
        }
    }

    /// Pop the last M elements of the array at once
    pub fn pop_array<const M: usize>(&mut self) -> Option<[T; M]> {
        if N <= M {
            return None;
        }

        self.len = self.len.checked_sub(M)?;

        unsafe {
            let ptr = self.as_ptr().add(self.len) as *const [T; M];
            Some(ptr.read())
        }
    }

    /// The length of the `ArrayVec`
    pub fn len(&self) -> usize {
        self.len
    }

    /// Removes all elements from the `ArrayVec`
    pub fn clear(&mut self) {
        unsafe {
            std::ptr::drop_in_place(self.as_mut_slice());
        }
        self.len = 0;
    }

    /// This function logically takes ownership of the items inside of the slice
    unsafe fn copy_from_slice_unchecked(&mut self, slice: &[T]) {
        debug_assert!(self.len + slice.len() <= N);

        std::ptr::copy_nonoverlapping(slice.as_ptr(), self.as_mut_ptr().add(self.len), slice.len());

        self.len += slice.len();
    }

    /// Convert to an array, panics if the ArrayVec is not full
    pub fn into_array(self) -> [T; N] {
        assert_eq!(
            self.len, N,
            "Tried to convert an ArrayVec into an array when it wasn't fully initialized"
        );

        unsafe {
            self.into_array_unchecked()
        }
    }

    /// Convert to an array, not checked in release mode and will panic in debug mode
    pub unsafe fn into_array_unchecked(mut self) -> [T; N] {
        debug_assert_eq!(
            self.len, N,
            "Tried to convert an ArrayVec into an array when it wasn't fully initialized"
        );

        self.len = 0;
        
        let mut arr = MaybeUninit::<[T; N]>::uninit();

        std::ptr::copy_nonoverlapping(
            self.as_ptr(),
            arr.as_mut_ptr() as *mut T,
            N
        );

        arr.assume_init()
    }
}

impl<T: Clone, const N: usize> Clone for ArrayVec<T, { N }> {
    fn clone(&self) -> Self {
        let mut arr = ArrayVec::<T, { N }>::default();

        arr.extend_from_slice(self);

        arr
    }
}

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

    fn deref(&self) -> &[T] {
        unsafe { std::slice::from_raw_parts(self.as_ptr(), self.len) }
    }
}

impl<T, const N: usize> DerefMut for ArrayVec<T, { N }> {
    fn deref_mut(&mut self) -> &mut [T] {
        unsafe { std::slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
    }
}

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

impl<T, const N: usize> From<[T; N]> for ArrayVec<T, { N }> {
    fn from(arr: [T; N]) -> Self {
        let arr = std::mem::ManuallyDrop::new(arr);

        Self {
            arr: unsafe {
                std::ptr::read(&arr as &[T; N] as *const [T; N] as *const [MaybeUninit<T>; N])
            },
            len: N,
        }
    }
}

impl<T, const N: usize> TryInto<[T; N]> for ArrayVec<T, { N }> {
    type Error = Self;

    fn try_into(self) -> Result<[T; N], Self> {
        if self.len == N {
            unsafe { Ok(self.into_array_unchecked()) }
        } else {
            Err(self)
        }
    }
}

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

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            arr: ManuallyDrop::new(self),
            idx: 0,
        }
    }
}

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

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

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

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

/// An iterator over the elements of a `ArrayVec`
pub struct IntoIter<T, const N: usize> {
    arr: ManuallyDrop<ArrayVec<T, { N }>>,
    idx: usize,
}

impl<T: Clone, const N: usize> Clone for IntoIter<T, { N }> {
    fn clone(&self) -> Self {
        let mut arr = ArrayVec::<T, { N }>::default();

        arr.extend_from_slice(&self.arr[self.idx..]);

        IntoIter {
            arr: ManuallyDrop::new(arr),
            idx: 0,
        }
    }
}

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

    fn next(&mut self) -> Option<T> {
        if N == 0 || self.arr.len == self.idx {
            None
        } else {
            let output = unsafe { self.arr.as_ptr().add(self.idx).read() };

            self.idx += 1;

            Some(output)
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let size = self.arr.len - self.idx;

        (size, Some(size))
    }

    fn nth(&mut self, n: usize) -> Option<T> {
        match self.idx.checked_add(n) {
            Some(idx) if idx < self.arr.len => {
                unsafe {
                    std::ptr::drop_in_place(&mut self.arr[self.idx..idx]);
                }
                self.idx = idx;
                self.next()
            }
            _ => {
                unsafe {
                    std::ptr::drop_in_place(&mut self.arr[self.idx..]);
                }
                self.idx = self.arr.len;
                None
            }
        }
    }
}

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

impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, { N }> {
    fn next_back(&mut self) -> Option<T> {
        if self.idx == self.arr.len {
            None
        } else {
            self.arr.pop()
        }
    }

    fn nth_back(&mut self, n: usize) -> Option<T> {
        match self.arr.len.checked_sub(n) {
            Some(len) if self.idx < len => {
                unsafe {
                    std::ptr::drop_in_place(&mut self.arr[len..]);
                }
                self.arr.len = len;
                self.next_back()
            }
            _ => {
                unsafe {
                    std::ptr::drop_in_place(&mut self.arr[self.idx..]);
                }
                self.idx = self.arr.len;
                None
            }
        }
    }
}

impl<T, const N: usize> Extend<T> for ArrayVec<T, { N }> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let _ = iter.into_iter().take(N).try_fold((), |_, x| self.push(x));
    }
}

impl<T, const N: usize> std::iter::FromIterator<T> for ArrayVec<T, { N }> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut arr = ArrayVec::<T, { N }>::default();

        arr.extend(iter);

        arr
    }
}

impl<T, const N: usize> Drop for IntoIter<T, { N }> {
    fn drop(&mut self) {
        unsafe {
            std::ptr::drop_in_place(std::slice::from_raw_parts_mut(
                self.arr.as_mut_ptr().add(self.idx),
                self.arr.len - self.idx,
            ))
        }
    }
}

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

impl<T: PartialOrd, const N: usize, const M: usize> PartialOrd<ArrayVec<T, { M }>>
    for ArrayVec<T, { N }>
{
    fn partial_cmp(&self, other: &ArrayVec<T, { M }>) -> Option<std::cmp::Ordering> {
        self.as_slice().partial_cmp(other.as_slice())
    }
}

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

use std::hash::{Hash, Hasher};

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