tryingarraylist 0.1.2

use core::fmt;
use std::ops::{Index, IndexMut};
use std::iter::{FromIterator, IntoIterator};
use std::alloc::{alloc, dealloc, Layout};
use std::hash::{Hash, Hasher};
use std::ptr;
use serde::{Serialize, Deserialize};
use serde::ser::SerializeSeq;
/// A simple ArrayList implementation
/// 
/// # How?
/// 
/// ptr stores the first element of the `ArrayList`,
/// 
/// cap stores the capacity of the `ArrayList` grows dynamically if you try to push an element after the allocated memory is already full,
/// it expands by allocating a new chunk of memory double the size of the old one,it copies all the elements in the new `ArrayList` and deallocates the old one,
/// 
/// len stores the offset in which the top element is stored.
/// 
/// ```text
/// 
/// STACK
/// 
///    ptr     cap     len
/// +-------+-------+-------+
/// | 0x123 |   4   |   2   |   ArrayList
/// +-------+-------+-------+
/// 
/// HEAP
/// 
/// +-------+-------+-------+-------+
/// |   1   |   2   |   ?   |   ?   | ... unallocated memory
/// +-------+-------+-------+-------+
///     ^       ^               ^
///    ptr     len             cap
/// 
/// ```
#[derive(Ord,PartialOrd)]
pub struct ArrayList<T> {
    items: *mut T,
    capacity: usize,
    lenght: usize,
}
#[allow(dead_code)]
impl  <T>ArrayList<T> {
    /// Creates a new `ArrayList` with the given capacity.
    /// 
    /// # Arguments
    /// 
    /// * `capacity` - The initial capacity of the `ArrayList`.
    /// 
    /// # Examples
    /// 
    /// ```
    /// use tryingarraylist::ArrayList;
    /// 
    /// let list: ArrayList<i32> = ArrayList::new(10);
    /// 
    /// ```
    pub fn new(capacity: usize) -> Self {
        let items = if capacity > 0 {
            let layout = Layout::array::<T>(capacity).unwrap();
            unsafe { alloc(layout) as *mut T }
        } else {
            ptr::null_mut()
        };
        Self {
            items,
            capacity,
            lenght: 0,
        }
    }
    /// Adds an element to the end of the `ArrayList`.
    /// 
    /// # Arguments
    ///
    /// * `item` - The item to push into the `ArrayList`.
    ///
    /// # Examples
    ///
    /// ```
    /// use tryingarraylist::ArrayList;
    /// 
    /// let mut list = ArrayList::new(10);
    /// list.push(42);
    /// 
    /// ```
    pub fn push(&mut self,element: T) {
        if self.capacity <= self.lenght {
            let new_capacity = self.capacity * 2;
            let new_layout = Layout::array::<T>(new_capacity).unwrap();
            let new_items = unsafe {
                alloc(new_layout) as *mut T
            };
            if new_items.is_null() {
                panic!("alloc failed, run away!!!");
            }
            unsafe {
                ptr::copy_nonoverlapping(self.items, new_items, self.lenght);
                dealloc(self.items as *mut u8, Layout::array::<T>(self.capacity).unwrap());
                self.items = new_items;
                self.capacity = new_capacity;
                ptr::write(self.items.add(self.lenght), element);
            }
        } else {
            unsafe {
                ptr::write(self.items.add(self.lenght), element);
            }
        }
        self.lenght += 1;
    }
    /// Gets the nth element in the `ArrayList`.
    /// 
    /// # Arguments
    ///
    /// * `index` - index to get in `ArrayList`.
    /// 
    /// # Returns
    /// 
    /// Returns `Some(&element)`  if the specified index is within bounds, else returns `None`.
    /// 
    /// # Examples
    ///
    /// ```
    /// use tryingarraylist::ArrayList;
    /// 
    /// let mut list = ArrayList::new(10);
    /// list.push(42);
    /// 
    /// assert!(Some(&42) == list.get(0));
    /// //out of bounds
    /// assert!(None == list.get(1));
    /// 
    /// ```
    pub fn get(&self,index:usize) -> Option<&T> {
        if index < self.lenght {
            unsafe {
                Some(&*self.items.add(index))
            }
        }else {
            None
        }
    }
    /// Returns the lenght of the `ArrayList`.
    /// 
    /// # Examples
    ///
    /// ```
    /// use tryingarraylist::ArrayList;
    /// 
    /// let mut list = ArrayList::new(10);
    /// list.push(1);
    /// list.push(2);
    /// list.push(3);
    /// 
    /// assert!(list.len() == 3);
    /// 
    /// ```
    pub fn len(&self) -> usize {
        self.lenght
    }
    /// Pops the top most element in the `ArrayList`.
    /// 
    /// # Returns
    /// 
    /// Returns `element` if the `ArrayList` is not empty, else panics.
    /// 
    /// # Examples
    ///
    /// ```
    /// use tryingarraylist::ArrayList;
    /// 
    /// let mut list = ArrayList::new(10);
    /// list.push(1);
    /// list.push(2);
    /// 
    /// assert!(list.pop() == 2));
    /// assert!(list.pop() == 1);
    /// 
    /// ```
    pub fn pop(&mut self) -> T {
        if self.lenght > 0 {
            self.lenght -=1;
            unsafe {
                ptr::read(self.items.add(self.lenght))
            }
        }else {
            panic!("'ArrayList' is empty!")
        }
    }
    /// Removes the element at the specified index from the `ArrayList`, shifting all subsequent
    /// elements to the left to fill the gap.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the element to be removed.
    ///
    /// # Returns
    ///
    /// Returns `element` if the specified index is within bounds, else panics.
    ///
    /// # Examples
    ///
    /// ```
    /// use tryingarraylist::ArrayList;
    ///
    /// let mut list = ArrayList::new(10);
    /// list.push(1);
    /// list.push(2);
    /// list.push(3);
    ///
    /// assert_eq!(list.remove(1), 2);
    /// assert_eq!(list.remove(0), 1);
    /// 
    /// ```
    pub fn remove(&mut self, index: usize) -> T {
        if index >= self.lenght {
            panic!("index out of bounds!")
        }
        unsafe {
            let item = ptr::read(self.items.add(index));
            ptr::copy(self.items.add(index + 1), self.items.add(index), self.lenght - index - 1);
            self.lenght -= 1;
            item
        }
    }
    /// Returns the memory location (pointer) in which the first element of the `ArrayList` is stored
    pub fn loc(&self) -> *mut T {
        self.items
    }
    /// No explanation needed
    fn is_empty(&self) -> bool {
        self.lenght == 0
    }
    /// Returns the capacity of the `ArrayList`
    fn capacity(&self) -> usize {
        self.capacity
    }
    /// Clears the `ArrayList` setting `lenght` to 0
    fn clear(&mut self) {
        self.lenght = 0;
    }
    /// Inserts the element at the specified index from the `ArrayList`, shifting all subsequent
    /// elements to the right to make a gap to insert new element.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the element to be inserted in.
    /// * `element` - The element to be inserted.
    ///
    /// # Examples
    ///
    /// ```
    /// use tryingarraylist::ArrayList;
    ///
    /// let mut list = ArrayList::new(10);
    /// list.push(1);
    /// list.push(2);
    /// list.insert(1,3);
    ///
    /// assert_eq!(list.pop(), 2);
    /// assert_eq!(list.pop(), 3);
    /// assert_eq!(list.pop(), 1);
    /// 
    /// ```
    pub fn insert(&mut self,index:usize,element: T) {
        if self.lenght == self.capacity {
            let new_capacity = self.capacity * 2;
            let new_layout = Layout::array::<T>(new_capacity).unwrap();
            let new_items = unsafe {
                alloc(new_layout) as *mut T
            };
            unsafe {
                ptr::copy_nonoverlapping(self.items, new_items, self.capacity);
                dealloc(self.items as *mut u8, Layout::array::<T>(self.capacity).unwrap());
                self.items = new_items;
                self.capacity = new_capacity;
            }
        }
        for i in (index..self.lenght).rev() {
            unsafe {
                ptr::write(self.items.add(i + 1), ptr::read(self.items.add(i)));
            }
        }
        unsafe {
            ptr::write(self.items.add(index), element);
        }
        self.lenght += 1;
    }
    /// Reverses the order of the elements in the `ArrayList`
    ///
    /// # Examples
    ///
    /// ```
    /// use tryingarraylist::ArrayList;
    ///
    /// let mut list = ArrayList::new(10);
    /// list.push(1);
    /// list.push(2);
    /// list.push(3);
    /// list.reverse();
    ///
    /// assert_eq!(list.pop(), 1);
    /// assert_eq!(list.pop(), 2);
    /// assert_eq!(list.pop(), 3);
    /// 
    /// ```
    pub fn reverse(&mut self) {
        let mut left = 0;
        let mut right = self.lenght.wrapping_sub(1);
        while left < right {
            unsafe {
                let left_ptr = self.items.add(left);
                let right_ptr = self.items.add(right);
                let temp = ptr::read(left_ptr);
                ptr::write(left_ptr, ptr::read(right_ptr));
                ptr::write(right_ptr, temp);
            }
            left +=1;
            right -=1;
        }
    }
    /// Sorts the elements in the `ArrayList` using the quicksort algorithm
    ///
    /// # Examples
    ///
    /// ```
    /// use tryingarraylist::ArrayList;
    ///
    /// let mut list = ArrayList::new(10);
    /// list.push(6);
    /// list.push(5);
    /// list.push(7);
    /// list.push(4);
    /// list.push(8);
    /// list.push(3);
    /// list.push(9);
    /// list.push(2);
    /// list.push(10);
    /// list.push(1);
    /// list.sort();
    ///
    /// assert_eq!(list.pop(), 10);
    /// assert_eq!(list.pop(), 9);
    /// assert_eq!(list.pop(), 8);
    /// assert_eq!(list.pop(), 7);
    /// assert_eq!(list.pop(), 6);
    /// assert_eq!(list.pop(), 5);
    /// assert_eq!(list.pop(), 4);
    /// assert_eq!(list.pop(), 3);
    /// assert_eq!(list.pop(), 2);
    /// assert_eq!(list.pop(), 1);
    /// 
    /// ```
    pub fn sort(&mut self)
    where
        T: Ord,
    {
        if self.lenght <= 1 {
            return;
        }
        self.quicksort(0, self.lenght -1);
    }

    fn quicksort(&mut self, low: usize, high: usize)
    where
        T: Ord,
    {
        if low < high {
            let pi = self.partition(low, high);
            if pi > 0 {
                self.quicksort(low, pi - 1);
            }
            self.quicksort(pi + 1, high);
        }
    }

    fn partition(&mut self, low: usize, high: usize) -> usize
    where
        T: Ord,
    {
        let pivot = unsafe { ptr::read(self.items.add(high)) };
        let mut i = low;
        for j in low..high {
            if unsafe { &*self.items.add(j) } <= &pivot {
                self.swap(i, j);
                i += 1;
            }
        }
        self.swap(i, high);
        i
    }
    fn swap(&mut self, i: usize, j: usize) {
        unsafe {
            let temp = ptr::read(self.items.add(i));
            ptr::write(self.items.add(i), ptr::read(self.items.add(j)));
            ptr::write(self.items.add(j), temp);
        }
    }

}
impl<T: PartialEq> PartialEq for ArrayList<T> {
    fn eq(&self, other: &Self) -> bool {
        if self.lenght != other.lenght {
            return false;
        }
        for i in 0..self.lenght {
            if self[i] != other[i] {
                return false;
            }
        }
        true
    }
}

impl<T: Eq> Eq for ArrayList<T> {}

impl <T>Drop for ArrayList<T> {
    fn drop(&mut self) {
        unsafe {
            for i in 0..self.lenght {
                ptr::drop_in_place(self.items.add(i));
            }
            dealloc(self.items as *mut u8, Layout::array::<T>(self.capacity).unwrap())
        }
    }
}
impl<T: fmt::Debug> fmt::Debug for ArrayList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list()
            .entries((0..self.lenght).map(|i| unsafe {
                &*self.items.add(i)
            }))
            .finish()
    }
}
impl<T:Clone> Clone for ArrayList<T> {
    fn clone(&self) -> Self {
        let mut new_list = ArrayList::new(self.capacity);
        for i in 0..self.lenght {
            let item = unsafe {
                ptr::read(self.items.add(i))
            };
            new_list.push(item.clone())
        }
        new_list
    }
}
impl <T> Index<usize> for ArrayList<T> {
    type Output = T;
    fn index(&self, index: usize) -> &Self::Output {
        unsafe {
            &*self.items.add(index)
        }
    }
}
impl <T> IndexMut<usize> for ArrayList<T> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        unsafe {
            &mut  *self.items.add(index)
        }
    }
}
impl<T> IntoIterator for ArrayList<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter {list: self,index:0}
    }
}
impl<T> FromIterator<T> for ArrayList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = ArrayList::new(0);
        for item in iter {
            list.push(item);
        }
        list
    }
}
impl<T> Extend<T> for ArrayList<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for item in iter {
            self.push(item);
        }
    }
}
impl <T: Hash> Hash for ArrayList<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for i in 0..self.lenght {
            unsafe {
                ptr::read(self.items.add(i)).hash(state);
            }
        }
        self.capacity.hash(state);
        self.lenght.hash(state);
    }
}

pub struct IntoIter<T> {
    list: ArrayList<T>,
    index: usize
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.list.lenght {
            let item = unsafe { ptr::read(self.list.items.add(self.index)) };
            self.index += 1;
            Some(item)
        } else {
            None
        }
    }
}

impl<T: Serialize> Serialize for ArrayList<T> {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        let items_slice = unsafe { std::slice::from_raw_parts(self.items, self.lenght) };
        let mut seq = serializer.serialize_seq(Some(self.lenght))?;
        for item in items_slice {
            seq.serialize_element(item)?;
        }
        seq.end()
    }
}

impl<'de, T: Deserialize<'de>> Deserialize<'de> for ArrayList<T> {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        struct ArrayListVisitor<T> {
            marker: std::marker::PhantomData<T>,
        }

        impl<'de, T: Deserialize<'de>> serde::de::Visitor<'de> for ArrayListVisitor<T> {
            type Value = ArrayList<T>;

            fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
                formatter.write_str("a sequence of elements")
            }

            fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
            where
                A: serde::de::SeqAccess<'de>,
            {
                let mut list = ArrayList::new(seq.size_hint().unwrap_or(0));
                while let Some(element) = seq.next_element()? {
                    list.push(element);
                }
                Ok(list)
            }
        }

        deserializer.deserialize_seq(ArrayListVisitor { marker: std::marker::PhantomData })
    }
}

#[macro_export]
macro_rules! arraylist {
    () => {
        ArrayList::new(0)
    };
    ($elem:expr; $n:expr) => {{
        let mut list = ArrayList::new($n);
        for _ in 0..$n {
            list.push($elem);
        }
        list
    }};
    ($($elem:expr),+ $(,)?) => {{
        let mut list = ArrayList::new(1);
        $(list.push($elem);)+
        list
    }};
}