ryley 0.1.1

//! Module `array`
//! 
//! This module (which can be found in `structs`) contains the type `Array` which
//! is a statically sized `array` (a `list` with a fixed size).
//! 
//! # Getting Started:
//! 
//! ## Create a new `Array`:
//! ```
//! # use ryley::structs::prelude::Array;
//! let mut a: Array<i32,5>=Array::new();
//! ```
//! or
//! ```
//! # use ryley::structs::prelude::Array;
//! # use ryley::array;
//! let mut a: Array<i32,5>=array![1,2,3,4,5];
//! ```
//! 
//! ## Use various methods on said `Array`:
//! ```
//! # use ryley::structs::prelude::*;
//! # let mut a: Array<i32,5>=array![1,2,3,4,5];
//! a.sort(None).reverse();
//! 
//! assert_eq!(a.sum(),15);
//! ```
//! 
//! ## Beware:
//! 
//! Type `Array` has a fixed size therefore you can't use methods that modify its
//! length. These methods are for example `add`, `remove` and `pop`, but using
//! `replace` can lead to problems as well (as long as you know what you're doing, 
//! it's okay).
//! 
//! ## Then maybe build something with it?
//! 
//! Type `Array` also comes with the benefit of sortedness which is dynamically
//! recalculated during each method. This is an semi-opt-in feature, one has to
//! specify whether an `Array` is sorted or not.
//! 
//! ### For example:
//! 
//! ```
//! # use ryley::array;
//! let mut a=array![1;1,2,3,4,5]; // Sorted Array
//! 
//! let mut a=array![-1;5,4,3,2,1]; // Reverse Sorted Array
//! ```
//! 
//! This sortedness can lead to increased performance during the execution of various
//! methods.

use core::cmp::Ordering;
use core::fmt::{Display,Formatter,Result};
use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Deref, DerefMut};
use core::ops::{Index, IndexMut, Neg, Not, Shl, ShlAssign, Shr, ShrAssign};
use core::ops::{Add, AddAssign, Sub, SubAssign, Mul, MulAssign, Div, DivAssign, Rem, RemAssign};
use core::slice::{Iter, IterMut};
use core::hash::Hash;
use core::array::IntoIter;
use core::str::FromStr;

use super::algorithm::{safe_index, CustomDisplay, CustomFromStr, KMP};
use super::ryley_slice_index::RyleySliceIndex;
use super::vector::algo::{binary_search, count, count_fn, ext, find, find_fn, replace, replace_fn, rotate, sort, update_sort};
use super::UDSI::{Container, LinContainer, Linear};

/// Type `Array` is a thin wrapper for `[T;N]` with the added benefits of sortedness
/// 
/// In most cases after using methods, sortedness is dynamically recalculated.
/// 
/// `Array` implements the Unified Data Structure Interface (or UDSI for short).
/// 
/// ## Beware
/// 
/// - Type `Array` has a fixed size, therefore it can't be extended (nor added
///   or substracted from)
/// 
/// - Type `Array` uses stack memory (which is quite limited), therefore it's
///   not advised to use it for large quantities of data (`Vector` is better
///   for that purpose).
#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord, Hash)]
pub struct Array<T,const N: usize> {
    /// Sorted flag of `Array`
    /// 
    /// It's -1 if Array is descendingly sorted; 0 if it's not sorted; 1 if it's ascendingly sorted
    pub sorted: i8,
    /// Internal storage of `Array`
    /// 
    /// Type `Array` is actually a thin wrapper for `[T;N]` with the added benefits of sortedness.
    /// 
    /// Every datastructure implementing `UDSI` has `cont` as its inner storage.
    pub cont: [T;N]
}
impl<const N: usize, T: Default> Default for Array<T,N> {
    fn default() -> Self {
        Self { cont: ([(); N].map(|()| T::default())), sorted: (0)}
    }
}

impl<const N: usize,T> Container<T> for Array<T,N> {
    fn len(&self) -> usize {
        self.cont.len()
    }
}
impl<const N: usize,T> LinContainer<T> for Array<T,N> {
    fn iter<'a>(&'a self) -> impl Iterator<Item = &'a T> where T: 'a {
        self.cont.iter()
    }
    fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item = &'a mut T> where T: 'a {
        self.cont.iter_mut()
    }
}
impl<const N: usize,T: Display> CustomDisplay<T> for Array<T,N> {}
impl<const N: usize,T: Display> Display for Array<T,N> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        self.display(f, "Array", '[', ']')
    }
}
impl<const N: usize,T> Extend<T> for Array<T,N> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, _iter: I) {
        panic!("Unextendable type! Type Array can't be extended!");
    }
}
impl<const N: usize,T: Default> FromIterator<T> for Array<T,N> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut cont = Self::new();
        cont.extend(iter);
        cont
    }
}
impl<const N: usize,T> IntoIterator for Array<T,N> {
    type Item = T;
    type IntoIter = IntoIter<T,N>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.into_iter()
    }
}
impl<'a,const N: usize,T> IntoIterator for &'a Array<T,N> {
    type Item = &'a T;
    type IntoIter = Iter<'a,T>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.iter()
    }
}
impl<'a,const N: usize,T> IntoIterator for &'a mut Array<T,N> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a,T>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.iter_mut()
    }
}
impl<const N: usize,T> Deref for Array<T,N> {
    type Target = [T];
    fn deref(&self) -> &Self::Target {
        &self.cont
    }
}
impl<const N: usize,T> DerefMut for Array<T,N> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.cont.as_mut_slice()
    }
}
impl<const N: usize,T> AsRef<[T]> for Array<T,N> {
    fn as_ref(&self) -> &[T] {
        &self.cont
    }
}
impl<const N: usize,T> AsMut<[T]> for Array<T,N> {
    fn as_mut(&mut self) -> &mut [T] {
        &mut self.cont
    }
}
impl<const N: usize,T,U: Into<[T;N]>> From<U> for Array<T,N> {
    fn from(value: U) -> Self {
        use crate::array;
        array![cont: value.into()]
    }
}
impl<const N: usize,T: FromStr + Default> CustomFromStr<T> for Array<T,N> where <T as FromStr>::Err : Display {}
impl<const N: usize,T: FromStr + Default> FromStr for Array<T,N> where <T as FromStr>::Err : Display {
    type Err = String;
    fn from_str(s: &str) -> core::result::Result<Self, Self::Err> {
        Self::from_string(s, "Array", |cont, i, elem| {cont.cont[i]=elem;})
    }
}

/// Constructs a new `Array`
/// 
/// `array!` allows for an effortless contruction of Arrays. This macro has multiple forms:
/// 
/// - Create a new `Array` from elements:
/// ```
/// # use ryley::structs::prelude::*;
/// let a = array![1,2,3,4,5];
/// assert_eq!(a.len(), 5);
/// ```
///
/// - Create a new sorted `Array`:
/// 
/// ```
/// # use ryley::array;
/// let a = array![1;1,2,3,4,5];
/// assert_eq!(a.sorted, 1);
/// ```
/// - Create a new `Array` from a `[T;N]`:
/// 
/// ```
/// # use ryley::structs::prelude::*;
/// let a = array![cont: [1,2,3,4,5]];
/// assert_eq!(a.len(), 5);
/// ```
/// 
/// - Create a new sorted `Array` from a `[T;N]`
/// 
/// ```
/// # use ryley::array;
/// let a = array![1; cont: [1,2,3,4,5]];
/// assert_eq!(a.sorted, 1);
/// ```
/// 
/// - Create a new `Array` with len
/// 
/// ```
/// # use ryley::structs::prelude::*;
/// let a = array![; 0; 5];
/// assert_eq!(a.len(), 5);
/// ```
/// 
/// - Create a new sorted`Array` with len
/// 
/// ```
/// # use ryley::array;
/// let a = array![1; 1; 5];
/// assert_eq!(a.sorted, 1);
/// ```
#[macro_export]
macro_rules! array {
    [cont: $x:expr] => {
        {
            use $crate::structs::array::Array;
            Array { sorted: (0), cont: ($x)}
        }
    };
    [$y:expr; cont: $x:expr] => {
        {
            use $crate::structs::array::Array;
            Array { sorted: ($y), cont: ($x)}
        }
    };
    [$($x:expr),*] => {
        {
            use $crate::structs::array::Array;
            Array { sorted: (0), cont: ([$($x),*]) }
        }
    };
    [$y:expr; $($x:expr),*] => {
        {
            use $crate::structs::array::Array;
            Array { sorted: ($y), cont: ([$($x),*]) }
        }
    };
    [; $x:expr; $len:expr] => {
        {
            use $crate::structs::array::Array;            
            Array { sorted: (0), cont: ([$x;$len]) }
        }
    };
    [$y:expr; $x:expr; $len:expr] => {
        {
            use $crate::structs::array::Array;
            Array { sorted: ($y), cont: ([$x;$len]) }
        }
    };
}

impl<const N: usize,T:Clone + Ord + Default> Linear<T> for Array<T,N> {
    fn add(&mut self, _elem: T, _index: Option<isize>) -> &mut Self {
        panic!("Undextendable type! Tried to add element to type array!");
    }
    fn add_slice(&mut self, _slice: Vec<T>, _index: Option<isize>) -> &mut Self {
        panic!("Undextendable type! Tried to add element to type array!");
    }
    fn sort(&mut self, reverse: Option<bool>) -> &mut Self {
        let order = reverse.unwrap_or(false);
        self.sorted=sort(self.cont.as_mut_slice(), order, self.sorted);
        self
    }
    fn sort_by(&mut self, f: impl FnMut(&T, &T) -> Ordering) -> &mut Self {
        self.cont.sort_by(f);
        self.sorted=0;
        self
    }
    fn set(&mut self, index: isize, elem: T) -> &mut Self {
        let ind: usize = safe_index(index, self.cont.len());
        self.cont[ind]=elem;
        self.sorted=update_sort(&self.cont, self.sorted, ind);
        self
    }
    fn set_range(&mut self, index: impl Iterator<Item=isize>, elems: Vec<T>) -> &mut Self {
        debug_assert!(index.size_hint().0<=elems.len(),"Not enough items! Wanted to set at least {} values with {} elements!",index.size_hint().0,elems.len());
        debug_assert!(index.size_hint().1.is_none_or(|x| x >= elems.len()), "Too many items! Wanted to set at most {} values with {} elements!",index.size_hint().1.unwrap(),elems.len());
        let len=self.cont.len();
        let it=index.zip(elems);
        for (i,elem) in it {
            let ind = safe_index(i, len);
            self.cont[ind]=elem;
            self.sorted=update_sort(&self.cont, self.sorted, ind);
        }
        self
    }
    fn contains(&self, elem: &T) -> bool {
        if self.sorted!=0 { return binary_search(&self.cont, self.sorted,elem).is_some(); }
        self.cont.contains(elem)
    }
    fn contains_fn(&self, mut f: impl FnMut(&T) -> bool) -> bool {
        for i in &self.cont { if f(i) { return true } }
        false
    }
    fn contains_slice(&self, slice: &[T]) -> bool {
        !KMP(&self.cont, slice, Some(1)).is_empty()
    }
    fn find(&self, elem: &T, maxcount: Option<isize>) -> Vec<usize> {
        find(&self.cont, self.sorted, elem, maxcount.unwrap_or(1))
    }
    fn find_fn(&self, f: impl FnMut(&T) -> bool, maxcount: Option<isize>) -> Vec<usize> {
        find_fn(&self.cont, f, maxcount.unwrap_or(1))
    }
    fn find_slice(&self, slice: &[T], maxcount: Option<isize>) -> Vec<usize> {
        let val=maxcount.unwrap_or(1);
        KMP(&self.cont, slice, Some(val))
    }
    fn count(&self, elem: &T) -> usize {
        count(&self.cont, self.sorted, elem)
    }
    fn count_fn(&self, f: impl FnMut(&T) -> bool) -> usize {
        count_fn(&self.cont, f)
    }
    fn count_slice(&self, slice: &[T]) -> usize {
        KMP(&self.cont, slice, None).len()
    }
    fn rotate(&mut self, r: isize) -> &mut Self {
        self.sorted=rotate(&mut self.cont, self.sorted, r);
        self
    }
    fn replace(&mut self, what: &T, to_what: Option<&T>, max_count: Option<isize>) -> &mut Self {
        let count = max_count.unwrap_or(-1);
        if count==0 { return self }
        if to_what.is_none() { panic!("Undextendable type! Tried to remove element from type array!"); }
        else { self.sorted=replace(&mut self.cont, self.sorted, what, to_what.unwrap(), count); }
        self
    }
    fn replace_fn(&mut self, f: impl FnMut(&T)->bool, to_what: Option<&T>, max_count: Option<isize>) -> &mut Self {
        let count = max_count.unwrap_or(-1);
        if count==0 { return self }
        if to_what.is_none() { panic!("Undextendable type! Tried to remove element from type array!"); }
        else { self.sorted=replace_fn(&mut self.cont, self.sorted, f, to_what.unwrap(), count); }
        self
    }
    fn replace_slice(&mut self, _slice: &[T], _to_what: Option<&[T]>, _max_count: Option<isize>) -> &mut Self {
        panic!("Undextendable type! Tried to replace slice with another in array!");
    }
    fn distinct(&mut self) -> &mut Self {
        panic!("Undextendable type! Tried to make Array of static size distinct!");
    }
    fn distinct_fn<U: Ord>(&mut self, _f: impl FnMut(&T) -> U) -> &mut Self {
        panic!("Undextendable type! Tried to make Array of static size distinct!");
    }
    fn clear(&mut self) -> &mut Self {
        panic!("Undextendable type! Tried to clear Array of static size!");
    }
    fn reverse(&mut self) -> &mut Self {
        self.cont.reverse();
        self.sorted*=-1;
        self
    }
    fn remove(&mut self, _index: Option<isize>) -> &mut Self {
        panic!("Undextendable type! Tried to remove element from array!");
    }
    fn remove_slice(&mut self, _from: isize, _to: Option<isize>) -> &mut Self {
        panic!("Undextendable type! Tried to remove element from array!");
    }
    fn pop(&mut self, _index: Option<isize>) -> T {
        panic!("Undextendable type! Tried to pop element from array!");
    }
    fn pop_slice(&mut self, _from: isize, _to: Option<isize>) -> Vec<T> {
        panic!("Undextendable type! Tried to pop element from array!");
    }
    fn maxi(&self) -> (&T, usize) {
        ext(&self.cont, self.sorted, true)
    }
    fn mini(&self) -> (&T, usize) {
        ext(&self.cont, self.sorted, false)
    }
    fn union(&mut self, _other: Self) -> &mut Self {
        panic!("Undextendable type! Can't find the union of two Arrays without using dynamic size!")
    }
    fn difference(&mut self, _other: &Self) -> &mut Self {
        panic!("Undextendable type! Can't find the difference of two Arrays without using dynamic size!")
    }
    fn intersect(&mut self, _other: &Self) -> &mut Self {
        panic!("Undextendable type! Can't find the intersection of two Arrays without using dynamic size!")
    }
    fn sym_diff(&mut self, _other: Self) -> &mut Self {
        panic!("Undextendable type! Can't find the symmetric difference of two Arrays without using dynamic size!")
    }
    fn repeat(&mut self, _n: usize) ->  &mut Self {
        panic!("Undextendable type! Can't repeat an Array with fixed size!")
    }
    fn merge(&mut self, _other: Self) -> &mut Self {
        panic!("Undextendable type! Can't merge two Arrays without using dynamic size!")
    }
}


impl<const N: usize,T: Default> Array<T,N> {
    /// Constructs a new `Self`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ryley::structs::prelude::Array;
    /// let mut arr: Array<i32,5> = Array::new();
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self {
            cont: [(); N].map(|()| T::default()),
            sorted: 0,
        }
    }
}
impl<const N: usize,T: Clone + Add<Output = T>> Array<T,N> {
    /// Sums the elements of a `Array`.
    ///
    /// Takes each element, adds them together, and returns the result.
    ///
    /// # Panics
    ///
    /// If the `Array` is empty
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// # use ryley::structs::prelude::Array;
    /// # use ryley::array;
    /// let a = array![1, 2, 3];
    /// let sum: i32 = a.sum();
    /// assert_eq!(sum, 6);
    /// ```
    pub fn sum(&self) -> T {
        debug_assert!(!self.cont.is_empty(), "Can't add elements together in empty array!");
        let mut out: T=self.cont[0].clone();
        for i in 1..self.cont.len()
        {
            out=out+self.cont[i].clone();
        }
        out
    }
}

/// Implements scalar operations for `Array`
macro_rules! scalar_op {
    ($for:tt, $trait:tt, $trait2:tt, $name:ident, $name2:ident, $keep_sorted:tt) => {
        impl<const N: usize,T: Ord + Clone + $trait2> $trait<T> for $for<T,N> {
            type Output = Self;
        
            fn $name(mut self, rhs: T) -> Self::Output {
                self.$name2(rhs);
                self
            }
        }
        impl<const N: usize,T: Ord + Clone + $trait2> $trait2<T> for $for<T,N> {
            fn $name2(&mut self, rhs: T) {
                if !$keep_sorted { self.sorted=0; }
                for elem in self.iter_mut() {
                    elem.$name2(rhs.clone());
                }
                if $keep_sorted && (self.sorted==1 && self[0]>self[-1] || self.sorted==-1 && self[0]<self[-1]) { self.sorted*=-1; }
            }
        }
    };
    (shift $for:tt, $trait:tt, $trait2:tt, $name:ident, $name2:ident) => {
        impl<const N: usize,T: $trait2<U>,U: Clone> $trait<U> for $for<T,N> {
            type Output = Self;
        
            fn $name(mut self, rhs: U) -> Self::Output {
                self.$name2(rhs);
                self
            }
        }
        impl<const N: usize,T: $trait2<U>,U: Clone> $trait2<U> for $for<T,N> {
            fn $name2(&mut self, rhs: U) {
                self.sorted=0;
                for elem in self.iter_mut() {
                    elem.$name2(rhs.clone());
                }
            }
        }
    };
    ($for:tt, $trait:tt, $name:ident) => {
        impl<const N: usize,T: Default + $trait<Output = T>> $trait for $for<T,N> {
            type Output = Self;
        
            fn $name(self) -> Self::Output {
                let sorted=self.sorted;
                let mut res=self.into_iter().map(|elem| elem.$name()).collect::<$for<_,N>>();
                res.sorted=-sorted;
                res
            }
        }
    };
}

/// Implements vector operations for `Array`
macro_rules! vector_op {
    ($for:tt, $trait:tt, $trait2:tt, $name:ident, $name2:ident) => {
        impl<const N: usize,T: $trait2> $trait for $for<T,N> {
            type Output = Self;
        
            fn $name(mut self, other: Self) -> Self {
                self.$name2(other);
                self
            }
        }
        impl<const N: usize,T: $trait2> $trait2 for $for<T,N> {
            fn $name2(&mut self, other: Self) {
                self.sorted=0;
                let mut it=other.into_iter();
                for elem in self.iter_mut() {
                    match it.next() {
                        Some(val) => { elem.$name2(val); }
                        None => { break; }
                    }
                }
            }
        }
    };
}

//Operations with scalars
scalar_op!(Array, Neg, neg);
scalar_op!(Array, Not, not);
scalar_op!(Array, Add, AddAssign, add, add_assign, true);
scalar_op!(Array, Sub, SubAssign, sub, sub_assign, true);
scalar_op!(Array, Mul, MulAssign, mul, mul_assign, true);
scalar_op!(Array, Div, DivAssign, div, div_assign, true);
scalar_op!(Array, Rem, RemAssign, rem, rem_assign, false);
scalar_op!(shift Array, Shl, ShlAssign, shl, shl_assign);
scalar_op!(shift Array, Shr, ShrAssign, shr, shr_assign);
scalar_op!(Array, BitAnd, BitAndAssign, bitand, bitand_assign, false);
scalar_op!(Array, BitOr,  BitOrAssign,  bitor,  bitor_assign,  false);
scalar_op!(Array, BitXor, BitXorAssign, bitxor, bitxor_assign, false);

//Operations with Arrays
vector_op!(Array, Add, AddAssign, add, add_assign);
vector_op!(Array, Sub, SubAssign, sub, sub_assign);
vector_op!(Array, Mul, MulAssign, mul, mul_assign);
vector_op!(Array, Div, DivAssign, div, div_assign);
vector_op!(Array, Rem, RemAssign, rem, rem_assign);
vector_op!(Array, BitAnd, BitAndAssign, bitand, bitand_assign);
vector_op!(Array, BitOr,  BitOrAssign,  bitor,  bitor_assign);
vector_op!(Array, BitXor, BitXorAssign, bitxor, bitxor_assign);

//Indexing
impl<const N: usize,T, I: RyleySliceIndex<[T]>> Index<I> for Array<T,N> {
    type Output = I::Output;

    fn index(&self, index: I) -> &Self::Output {
        index.index(&self.cont)
    }
}
impl<const N: usize,T,I: RyleySliceIndex<[T]>> IndexMut<I> for Array<T,N> {
    fn index_mut(&mut self, index: I) -> &mut Self::Output {
        index.index_mut(&mut self.cont)
    }
}