//! This crate contains a vector type that has its own self-contained and stack-based allocation system.
//! This type of vector is called a max-sized vector, and reserves a fixed amount of space at its creation.
//! Once created, there are no elements, but the amount of elements can increase until the buffer is full.
//! When the buffer is full, and another element is attempted to be added, a panic happens describing the error.
//! This vector has the vast majority of vector methods and traits that aren't allocation specfic (e.g. reserve isn't a method).
//! This crate has no dependencies other than core, and is therefore standalone and suitable for use without the standard
//! library.
//!
//! Example:
//!
//! ```rust
//! use max_size_vec::MaxSizeVec;
//! fn main() {
//!     let mut x: MaxSizeVec<usize, 1024> = MaxSizeVec::new();
//!     x.push(0usize);
//!     x.swap_remove(0usize);
//!     x.extend(5..10usize);
//!     x.pop();
//!     x.retain(|x| *x > 6);
//!     x.drain(0..1);
//!     x.drain(..1);
//!     x.push(2);
//!     x.insert(1usize, 1usize);
//!     x.insert(0usize, 1usize);
//!     x.remove(0usize);
//!     assert_eq!(x, &[2, 1]);
//! }
//! ```
#![no_std]
#![deny(missing_docs)]
#![feature(min_const_generics)]

/// This type of vector is called a max-sized vector, and reserves a fixed amount of space at its creation.
/// Once created, there are no elements, but the amount of elements can increase until the buffer is full.
/// When the buffer is full, and another element is attempted to be added, a panic happens describing the error.
/// This vector has the vast majority of vector methods and traits that aren't allocation specfic (e.g. reserve isn't a method).
pub struct MaxSizeVec<T, const SIZE: usize> {
    data: [core::mem::ManuallyDrop<T>; SIZE],
    length: usize
}

/// An iterator used for the iterator method of a max-sized iterator.
pub struct MaxSizeVecIter<T, const SIZE: usize> {
    data: [core::mem::ManuallyDrop<T>; SIZE],
    length: usize,
    offset: usize
}

impl<T, const SIZE: usize> core::iter::Iterator for MaxSizeVecIter<T, {SIZE}> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.offset >= self.length {
            None
        } else {
            self.offset += 1;
            // The bounds checks above made sure that this is valid.
            Some(unsafe { 
                core::ptr::read((self.data.as_ptr() as *const T).offset_unsigned(self.offset - 1))
            })
        }
    }
}

/// Used for draining elements out of a max-sized vector.
pub struct Drain<'a, T, const SIZE: usize> {
    vector: &'a mut MaxSizeVec<T, {SIZE}>,
    original_start: usize,
    start: usize,
    end: usize
}

impl<'a, T, const SIZE: usize> core::iter::Iterator for Drain<'a, T, {SIZE}> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.start >= self.end {
            None
        } else {
            self.start += 1;
            // Safe, as exclusive access is given once and only once to the user of the next method. Since everything in the vector is manually dropped, and this gives exclusive 
            // access to the element once, it is guaranteed that this will be dropped once after being used, and therefore should be skipped for dropping when the drain itself is 
            // dropped. That's why only the elements not accessed yet are dropped when the drain is dropped.
            Some(unsafe {
                core::ptr::read(self.vector.as_ptr().offset(self.start as isize - 1))
            })
        }
    }
}

impl<'a, T, const SIZE: usize> core::ops::Drop for Drain<'a, T, {SIZE}> {
    fn drop(&mut self) {
        let amount_to_remove = self.end - self.original_start;
        unsafe {
            // None of these were accessed or dropped yet, so this is safe.
            for x in self.start..self.end {
                core::ptr::drop_in_place(
                    self.vector.as_mut_ptr().offset_unsigned(x)
                );
            }
            // Copy the region after the drain to the start. The regions after both pointers overlap, so a copy_nonoverlapping call here 
            // would be invalid.
            //
            // By doing this and subtracting from the vector's length, it looks like a bunch of elements were removed. This is safe, as
            // the memory regions and pointers are all valid.
            core::ptr::copy(
                self.vector.as_ptr().offset_unsigned(self.end),
                self.vector.as_mut_ptr().offset_unsigned(self.original_start),
                self.vector.length - self.end
            );
        }
        self.vector.length -= amount_to_remove;
    }
}

trait OffsetUnsigned {
    unsafe fn offset_unsigned(&self, offset: usize) -> Self;
}

impl<T> OffsetUnsigned for *const T {
    unsafe fn offset_unsigned(&self, offset: usize) -> *const T {
        self.offset(offset as isize)
    }
}

impl<T> OffsetUnsigned for *mut T {
    unsafe fn offset_unsigned(&self, offset: usize) -> *mut T {
        self.offset(offset as isize)
    }
}

impl<T, const SIZE: usize> Drop for MaxSizeVec<T, {SIZE}> {
    fn drop(&mut self) {
        // Since everything in this vector is manually dropped, everything that wasn't dropped is dropped here.
        for x in 0..self.length {
            unsafe {
                core::mem::ManuallyDrop::drop(&mut self.data[x]);
            }
        }
    }
}

impl<T: Clone, const SIZE: usize> Clone for MaxSizeVec<T, {SIZE}> {
    fn clone(&self) -> MaxSizeVec<T, {SIZE}> {
        MaxSizeVec {
            data: self.data.clone(),
            length: self.length
        }
    }
}

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

impl<T: PartialEq, const SIZE: usize, const OTHER: usize> PartialEq<MaxSizeVec<T, {OTHER}>> for MaxSizeVec<T, {SIZE}> {
    fn eq(&self, other: &MaxSizeVec<T, {OTHER}>) -> bool {
        self.as_slice() == other.as_slice()
    }
}

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

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

impl<T: core::fmt::Debug, const SIZE: usize> core::fmt::Debug for MaxSizeVec<T, {SIZE}> {
    fn fmt(&self, fmt: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        // This gets the vector in the data array up its length, and transmutes it to make format correctly.
        unsafe {
            core::mem::transmute::<&[core::mem::ManuallyDrop<T>], &[T]>(&self.data[..self.length])
        }.fmt(fmt)
    }
}

impl<T, const SIZE: usize> MaxSizeVec<T, {SIZE}> {
    /// Creates a new, empty max-size vector.
    pub fn new() -> MaxSizeVec<T, {SIZE}> {
        // The zeroed memory here is never directly used until correct initialization. 
        MaxSizeVec {
            data: unsafe {
                core::mem::MaybeUninit::zeroed().assume_init()
            },
            length: 0usize
        }
    }
    
    /// Pushes an element to the max-size vector.
    pub fn push(&mut self, val: T) {
        if self.length == self.data.len() {
            panic!("Attempt to push when there's no room left in a max size vector!");
        }
        self.data[self.length] = core::mem::ManuallyDrop::new(val);
        self.length += 1;
    }
    
    /// Pops off an element from the max-size vector.
    pub fn pop(&mut self) {
        if self.length == 0 {
            panic!("Attempt to pop a max-size vector with underflow!");
        }
        // Drop the last element and subtract from the length.
        unsafe {
            core::mem::ManuallyDrop::drop(&mut self.data[self.length - 1]);
        }
        self.length -= 1;
    }

    /// Gets the length of the max-size vector.
    pub fn len(&self) -> usize {
        self.length
    }

    /// Drains elements from the vector based on a range.
    pub fn drain<'a, R: core::ops::RangeBounds<usize>>(&'a mut self, range: R) -> Drain<'a, T, {SIZE}> {
        use core::ops::Bound;
        let start = match range.start_bound() {
            Bound::Unbounded => 0usize,
            Bound::Included(x) => {
                let x = *x;
                if x >= self.len() { 
                    panic!("Range out of bounds!")
                } else { 
                    x
                }
            },
            _ => unreachable!()
        };

        let end = match range.end_bound() {
            Bound::Unbounded => self.len(),
            Bound::Included(x) => if *x + 1 > self.len() { 
                panic!("Range out of bounds!") 
            } else {
                *x + 1
            },
            Bound::Excluded(x) => {
                let x = *x;
                if x > self.len() { 
                    panic!("Range out of bounds!")
                } else { 
                    x
                }
            },
        };

        Drain {
            start,
            end,
            vector: self,
            original_start: start
        }
    }

    /// Appends a max-size vector onto this one, making the other one empty.
    pub fn append<const OTHER_SIZE: usize>(&mut self, other: &mut MaxSizeVec<T, {OTHER_SIZE}>) {
        // This bounds check makes the following unsafe code safe.
        if self.length + other.length > self.data.len() {
            panic!("Attempt to append beyond the bounds of a max-size vector!");
        }
        // Both of these are valid nonoverlapping pointers in valid memory regions that don't overlap.
        // This copies the other vector's elements to the end of the current vector.
        unsafe {
            core::ptr::copy_nonoverlapping(
                other.as_ptr(), 
                self.as_mut_ptr().offset_unsigned(self.length), 
                other.len()
            )
        }
        // Increase the length to include the new elements.
        self.length += other.len();
        // Clear the other vector.
        *other = MaxSizeVec::new();
    }

    /// Gets a mutable pointer to the base of this vector.
    pub fn as_mut_ptr(&mut self) -> *mut T {
        self.data.as_mut_ptr() as *mut T
    }

    /// Gets a mutable slice that can be used to edit or read the elements of this vector.
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        // This transmutes the slice of the vector's elements to make it drop accordingly when used.
        unsafe {
            core::mem::transmute::<&mut [core::mem::ManuallyDrop<T>], &mut [T]>(&mut self.data[..self.length])
        }
    }

    /// This gets a pointer to the base of this vector.
    pub fn as_ptr(&self) -> *const T {
        self.data.as_ptr() as *const T
    }

    /// Gets an immutable slice that can be used to read the elements of this vector
    pub fn as_slice(&self) -> &[T] {
        // This transmutes the slice of the vector's elements to make it drop accordingly when used.
        unsafe {
            core::mem::transmute::<&[core::mem::ManuallyDrop<T>], &[T]>(&self.data[..self.length])
        }
    }

    /// The capacity of this vector, i.e. the maximum number of elements that it can hold.
    pub fn capacity(&self) -> usize {
        self.data.len()
    }

    /// This clears the vector.
    pub fn clear(&mut self) {
        *self = MaxSizeVec::new();
    }

    /// This inserts an element at an index in the vector,
    pub fn insert(&mut self, index: usize, element: T) {
        // These bounds checks make the unsafe code in this function valid.
        if self.length + 1 >= self.data.len() {
            panic!("Attempt to insert into a max-sized vector with overflow!");
        }
        if index > self.length {
            panic!("Index out of bounds during insertion into max-sized vector!");
        }
        if index == self.length {
            self.push(element);
        } else {
            unsafe {
                // Make room for the extra element
                self.length += 1;
                // Copy elements at the index of insertion to the index after it.
                core::ptr::copy(
                    self.as_ptr().offset_unsigned(index), 
                    self.as_mut_ptr().offset_unsigned(index + 1), 
                    self.length - index
                );
                // Overwrite the index of insertion with the inserted element.
                *self.as_mut_ptr().offset_unsigned(index) = element;
            }
        }
    }

    /// This truncates a vector to a certain length.
    pub fn truncate(&mut self, size: usize) {
        if size > self.length {
            panic!("Attempt to truncate a max-sized vector to larger length!");
        }
        if size != self.length {
            for x in 0..self.length - size - 1 {
                // This makes sure that all elements lost are dropped before being made inaccessible.
                unsafe {
                    let ptr: *mut core::mem::ManuallyDrop<T> = self.data.as_mut_ptr().offset_unsigned(
                        self.length - x
                    );
                    core::mem::ManuallyDrop::drop(core::mem::transmute::<_, &mut core::mem::ManuallyDrop<T>>(ptr))
                }
            }
            self.length = size;
        }
    }

    /// This resizes a vector with one condition: if the size is larger than the vectors size, a closure passed will be called
    /// to fill in the missing parts.
    pub fn resize_with(&mut self, size: usize, mut f: impl FnMut() -> T) {
        if size >= self.data.len() {
            panic!("The size passed to the resize function of a max-sized vector was larger than the vector's bounds!");
        }
        if size >= self.length {
            for _ in 0..size - self.length {
                self.push(f());
            }
        } else {
            self.truncate(size);
        }
    }

    /// This removes all elements that don't fit a predicate, leaving the ones that fit it.
    pub fn retain(&mut self, mut predicate: impl FnMut(&T) -> bool) {
        let mut current_length = 0usize;
        // This copies the predicate elements to the start of the array in order.
        for x in 0..self.length {
            if predicate(&self[x]) {
                // This is safe because both of these indices are valid and will never exceed the length. The memory region also only covers the indexes.
                unsafe {
                    core::ptr::copy(self.as_ptr().offset_unsigned(x), self.as_mut_ptr().offset_unsigned(current_length), 1usize)
                };
                current_length += 1;
            } else {
                // Everything that will be discarded should be dropped.
                unsafe {
                    core::ptr::drop_in_place(self.as_mut_ptr().offset_unsigned(x))
                }
            }
        }
        // Change the length accordingly to prevent invalid accesses.
        self.length = current_length;
    }

    /// This removes an element from a vector at a certain index, while preserving order.
    pub fn remove(&mut self, index: usize) {
        if index >= self.length {
            panic!("Index for removal out of bounds for max-sized vector!");
        }
        unsafe {
            // The element being removed should be dropped.
            core::ptr::drop_in_place(self.as_mut_ptr().offset_unsigned(index));
        }
        if index != self.length - 1 {
            unsafe {
                // The elements after it should be shifted back by one index.
                core::ptr::copy(
                    self.as_ptr().offset_unsigned(index + 1),
                    self.as_mut_ptr().offset_unsigned(index),
                    self.length - index - 1
                );
            }
        }
        // This is needed regardless if the index is the last one to make sure invalid memory
        // isn't accessible.
        self.length -= 1;
    }

    /// This swaps an element at an index with the last element and pops the vector, which messes up order,
    /// but successfully removes an element from the vector.
    pub fn swap_remove(&mut self, index: usize) {
        if index >= self.length {
            panic!("Index out of bounds for swap remove operation on max-sized vector!");
        }
        if index == self.length - 1 {
            self.pop();
        } else {
            // This swaps the memory of valid indices, and so is safe.
            unsafe {
                core::ptr::swap_nonoverlapping(
                    self.as_mut_ptr().offset_unsigned(index), self.as_mut_ptr().offset_unsigned(self.length - 1), 1usize
                );
            }
            self.pop();
        }
    }

    /// This checks to see whether or not the vector is empty.
    pub fn is_empty(&self) -> bool {
        self.length == 0
    }
}

impl<T, const SIZE: usize> core::ops::Deref for MaxSizeVec<T, {SIZE}> {
    type Target = [T];
    fn deref(&self) -> &Self::Target {
        self.as_slice()
    }
}

impl<T, const SIZE: usize> core::ops::DerefMut for MaxSizeVec<T, {SIZE}> {
    fn deref_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T: Clone, const SIZE: usize> MaxSizeVec<T, {SIZE}> {
    /// This resizes a vector with a value to fill in missing parts if the size is larger than the current size.
    pub fn resize(&mut self, size: usize, value: T) {
        if size >= self.data.len() {
            panic!("The size passed to the resize function of a max-sized vector was larger than the vector's bounds!");
        }
        if size >= self.length {
            for _ in 0..size - self.length {
                self.push(value.clone());
            }
        } else {
            self.truncate(size);
        }
    }

    /// This extends a vector from a slice.
    pub fn extend_from_slice(&mut self, other: &[T]) {
        if self.len() + other.len() >= self.data.len() {
            panic!("Attempt to extend by a slice beyond the bounds of a max-sized vector!");
        }
        for (n, x) in other.iter().cloned().enumerate() {
            // Bounds checks are done above. This is not a premature optimization. The compiler failed to remove the bounds checks with a regular indexing,
            // and so I manually implemented them and put it outside of the loop.
            unsafe {
                *self.data.as_mut_ptr().offset_unsigned(self.length + n) = core::mem::ManuallyDrop::new(x);
            }
        }
    }
}

impl<T, const SIZE: usize> core::iter::Extend<T> for MaxSizeVec<T, {SIZE}> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let mut iter = iter.into_iter();
        let mut x = iter.next();
        while x.is_some() {
            if self.length >= self.data.len() {
                panic!("Attempt to extend beyond the bounds of a max-sized vector!");
            }
            self.data[self.length] = core::mem::ManuallyDrop::new(x.unwrap());
            self.length += 1;
            x = iter.next();
        }
    }
}

impl<'a, T: 'a + Copy, const SIZE: usize> core::iter::Extend<&'a T> for MaxSizeVec<T, {SIZE}> {
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        let mut iter = iter.into_iter();
        let mut x = iter.next();
        while x.is_some() {
            if self.length >= self.data.len() {
                panic!("Attempt to extend beyond the bounds of a max-sized vector!");
            }
            self.data[self.length] = core::mem::ManuallyDrop::new(x.unwrap().clone());
            self.length += 1;
            x = iter.next();
        }
    }
}

impl<T, const SIZE: usize> core::ops::Index<usize> for MaxSizeVec<T, {SIZE}> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        if index >= self.length {
            panic!("Index {} out of bounds of fixed size vec!", index);
        }
        // When an index is accessed, the data at this index should be droppable and not wrapped in the ManuallyDrop
        // structure.
        unsafe {
            core::mem::transmute(self.data.index(index))
        }
    }
}

impl<T, const SIZE: usize> core::ops::IndexMut<usize> for MaxSizeVec<T, {SIZE}> {
    fn index_mut(&mut self, index: usize) -> &mut T {
        if index >= self.length {
            panic!("Index {} out of bounds of fixed size vec!", index);
        }
        // When an index is accessed, the data at this index should be droppable and not wrapped in the ManuallyDrop
        // structure.
        unsafe {
            core::mem::transmute(self.data.index_mut(index))
        }
    }
}

impl<T, const SIZE: usize> core::convert::AsMut<[T]> for MaxSizeVec<T, {SIZE}> {
    fn as_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T, const SIZE: usize> core::convert::AsMut<MaxSizeVec<T, {SIZE}>> for MaxSizeVec<T, {SIZE}> {
    fn as_mut(&mut self) -> &mut Self {
        self
    }
}

impl<T, const SIZE: usize> core::convert::AsRef<[T]> for MaxSizeVec<T, {SIZE}> {
    fn as_ref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T, const SIZE: usize> core::convert::AsRef<MaxSizeVec<T, {SIZE}>> for MaxSizeVec<T, {SIZE}> {
    fn as_ref(&self) -> &Self {
        self
    }
}

impl<T, const SIZE: usize> core::borrow::Borrow<[T]> for MaxSizeVec<T, {SIZE}> {
    fn borrow(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T, const SIZE: usize> core::borrow::BorrowMut<[T]> for MaxSizeVec<T, {SIZE}> {
    fn borrow_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

impl<T: Eq, const SIZE: usize> Eq for MaxSizeVec<T, {SIZE}> {}

impl<'a, T: Clone, const SIZE: usize> From<&'a [T]> for MaxSizeVec<T, {SIZE}> {
    fn from(x: &[T]) -> Self {
        let mut v = MaxSizeVec::new();
        v.extend(x.iter().cloned());
        v
    }
}

impl<'a, T: Clone, const SIZE: usize> From<&'a mut [T]> for MaxSizeVec<T, {SIZE}> {
    fn from(x: &mut [T]) -> Self {
        let mut v = MaxSizeVec::new();
        v.extend(x.iter().cloned());
        v
    }
}

impl<'a, const SIZE: usize> From<&'a str> for MaxSizeVec<u8, {SIZE}> {
    fn from(x: &str) -> Self {
        let mut v = MaxSizeVec::new();
        v.extend(x.as_bytes().iter().cloned());
        v
    }
}

impl<T, const SIZE: usize> core::iter::FromIterator<T> for MaxSizeVec<T, {SIZE}> {
    fn from_iter<I: IntoIterator<Item = T>>(x: I) -> Self {
        let mut v = MaxSizeVec::new();
        v.extend(x);
        v
    }
}

impl<T, const SIZE: usize> core::iter::IntoIterator for MaxSizeVec<T, {SIZE}> {
    type Item = T;
    type IntoIter = MaxSizeVecIter<T, {SIZE}>;
    fn into_iter(self) -> MaxSizeVecIter<T, {SIZE}> {
        // Transmute copy is used here rather than a regular transmute because the compiler
        // couldn't tell that [T; SIZE] has the same size as [ManuallyDrop<T>; SIZE]. The 
        // transmute is needed to make the data droppable after usage.
        MaxSizeVecIter {
            offset: 0usize,
            length: self.length,
            data: unsafe {
                core::mem::transmute_copy(&self.data)
            }
        }
    }
}

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

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

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

#[test]
fn dropping_order() {
    use core::sync::atomic::*;
    
    #[derive(Clone, Debug)]
    struct DropTest;

    static DROP_COUNT: AtomicUsize = AtomicUsize::new(0usize);
    impl Drop for DropTest {
        fn drop(&mut self) {
            DROP_COUNT.fetch_add(1usize, Ordering::SeqCst);
        }
    }
    
    let mut x: MaxSizeVec<DropTest, 1024> = MaxSizeVec::new();
    x.extend((1..=1024).map(|_| DropTest));
    x.resize(512, DropTest);
    x.swap_remove(0usize);
    x.pop();

    let mut collection: MaxSizeVec<DropTest, 1024> = MaxSizeVec::new();
    for v in x.drain(..) {
        collection.push(v);
    }
    x.append(&mut collection);
    x.drain(..);
    
    assert_eq!(x.len(), 0);
    assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 1534);
}

#[test]
fn operational_correctness() {
    let mut x: MaxSizeVec<usize, 1024> = MaxSizeVec::new();

    x.push(0usize);
    x.swap_remove(0usize);
    x.extend(5..10usize);
    x.pop();
    x.retain(|x| *x > 6);
    x.drain(0..1);
    x.drain(..1);
    x.push(2);
    x.insert(1usize, 1usize);
    x.insert(0usize, 1usize);
    x.remove(0usize);

    assert_eq!(x, &[2, 1]);
}