ryley 0.1.1

//! Module `vector`
//! 
//! This module (which can be found in `structs`) contains the type `Vector` which
//! is a dynamically sized `array`.
//! 
//! # Getting Started:
//! 
//! ## Create a new `Vector`:
//! ```
//! # use ryley::structs::prelude::Vector;
//! let mut v: Vector<i32>=Vector::new();
//! ```
//! or
//! ```
//! # use ryley::structs::prelude::*;
//! let mut v: Vector<i32>=vector![1,2,3,4,5];
//! ```
//! 
//! ## Use various methods on said `Vector`:
//! ```
//! # use ryley::structs::prelude::*;
//! # let mut v: Vector<i32>=vector![1,2,3,4,5];
//! v.add(12,None).add(3,Some(-3)).add_slice(vec![1,2,3],None);
//! 
//! assert!(v.contains_slice(&[3,5,12,1]));
//! ```
//! 
//! ## Then maybe build something with it?
//! 
//! Type `Vector` 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 if a `Vector` is sorted or not.
//! 
//! ### For example:
//! 
//! ```
//! # use ryley::structs::prelude::*;
//! let mut v=vector![1;1,2,3,4,5]; // Sorted Vector
//! 
//! let mut v=vector![-1;5,4,3,2,1]; // Reverse Sorted Vector
//! ```
//! 
//! This sortedness can lead to increased performance during the execution of various
//! methods.

use core::cmp::Ordering;
use std::collections::BTreeSet;
use core::fmt::{Debug, 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::mem::swap;
use core::str::FromStr;
use std::vec::IntoIter;

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

/// Type `Vector` is a thin wrapper for `Vec` with the added benefits of sortedness
/// 
/// In most cases after using methods, for example `add`, `remove`, `replace`
/// sortedness is dynamically recalculated.
/// 
/// `Vector` implements the Unified Data Structure Interface (or UDSI for short).
#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord, Hash, Default)]
pub struct Vector<T> {
    /// Sorted flag of `Vector`
    /// 
    /// It's -1 if Vector is descendingly sorted; 0 if it's not sorted; 1 if it's ascendingly sorted
    pub sorted: i8,
    /// Internal storage of `Vector`
    /// 
    /// Type `Vector` is actually a thin wrapper for `Vec` with the added benefits of sortedness.
    /// 
    /// Every datastructure implementing `UDSI` has `cont` as its inner storage.
    pub cont: Vec<T>
}

impl<T> Container<T> for Vector<T> {
    fn len(&self) -> usize {
        self.cont.len()
    }
}
impl<T> LinContainer<T> for Vector<T> {
    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<T: Display> CustomDisplay<T> for Vector<T> {}
impl<T: Display> Display for Vector<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        self.display(f, "Vector", '[', ']')
    }
}
impl<T: Ord> Extend<T> for Vector<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let len=self.len();
        self.cont.extend(iter);
        if self.sorted!=0 && self.len()!=len { self.sorted=update_sort(&self.cont,self.sorted,len); }
    }
}
impl<T: Ord> FromIterator<T> for Vector<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut cont = Self::new();
        cont.extend(iter);
        cont
    }
}
impl<T> IntoIterator for Vector<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.into_iter()
    }
}
impl<'a,T> IntoIterator for &'a Vector<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a,T>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.iter()
    }
}
impl<'a,T> IntoIterator for &'a mut Vector<T> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a,T>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.iter_mut()
    }
}
impl<T> Deref for Vector<T> {
    type Target = [T];
    fn deref(&self) -> &Self::Target {
        &self.cont
    }
}
impl<T> DerefMut for Vector<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.cont.as_mut_slice()
    }
}
impl<T> AsRef<[T]> for Vector<T> {
    fn as_ref(&self) -> &[T] {
        &self.cont
    }
}
impl<T> AsMut<[T]> for Vector<T> {
    fn as_mut(&mut self) -> &mut [T] {
        &mut self.cont
    }
}
impl<T,U: Into<Vec<T>>> From<U> for Vector<T> {
    fn from(value: U) -> Self {
        use crate::vector;
        vector![cont: value.into()]
    }
}
impl<T: FromStr + Default> CustomFromStr<T> for Vector<T> where <T as FromStr>::Err : Display {}
impl<T: FromStr + Default> FromStr for Vector<T> where <T as FromStr>::Err : Display {
    type Err = String;
    fn from_str(s: &str) -> core::result::Result<Self, Self::Err> {
        Self::from_string(s, "Vector", |cont, _, elem| {cont.cont.push(elem)})
    }
}

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


pub(super) mod algo {
    use crate::structs::algorithm::make_multiset;
    use core::{cmp::Ordering, mem::swap};

    /// Update the sortedness of a slice at a given position
    pub fn update_sort<T: PartialOrd>(cont: &[T], sorted: i8, ind: usize) -> i8 {
        if sorted==0 { return 0 }
        match sorted {
            1 => if (ind!=0 && cont[ind]<cont[ind-1]) || (ind!=cont.len()-1 && cont[ind]>cont[ind+1]) {return 0},
            _ => if (ind!=0 && cont[ind]>cont[ind-1]) || (ind!=cont.len()-1 && cont[ind]<cont[ind+1]) {return 0},
        }
        sorted
    }

    fn sorted_ext<T: PartialOrd>(cont: &[T], sorted: i8, max: bool) -> (&T, usize) {
        let len=cont.len()-1;
        if (sorted==1 && max) || (sorted!=1 && !max) { 
            let mut i=len;
            while i>0 && cont[i]==cont[len] { i-=1; }
            if cont[i]==cont[len] { return (&cont[i],i) }
            return (&cont[i+1],i+1)
        }
        (&cont[0],0)
    }
    fn unsorted_ext<T: PartialOrd>(cont: &[T], max: bool) -> (&T, usize) {
        let mut iter=cont.iter();
        let mut e_val=iter.next().unwrap();
        let mut e_ind=0;
        for (i,it) in iter.enumerate() {
            if (max && it>e_val) || (!max && it<e_val) {
                e_val=it;
                e_ind=i+1;
            }
        }
        (e_val,e_ind)
    }
    /// Returns the extremum of a slice
    /// 
    /// This extremum can be a max or min value depending on the `max`
    /// parameter.
    pub fn ext<T: PartialOrd>(cont: &[T], sorted: i8, max: bool) -> (&T, usize) {
        debug_assert!(!cont.is_empty(), "Can't find extremum in empty Vector!");
        if sorted!=0 { sorted_ext(cont, sorted, max) }
        else { unsorted_ext(cont, max) }
    }
    /// Finds `elem` in `Vector` in O(log n) time if `Vector` is sorted
    /// 
    /// # Panic
    /// 
    /// If `Vector` is not sorted it panics.
    pub fn binary_search<T: PartialOrd>(cont: &[T], sorted: i8, elem: &T) -> Option<usize> {
        debug_assert!(sorted != 0, "Tried to use binary search on unsorted Vector!");
        debug_assert!(!cont.is_empty(), "Tried to use binary search on empty Vector!");
        let len=cont.len()-1;
        let (min, max)=if sorted==1 {(&cont[0],&cont[len])} else {(&cont[len],&cont[0])};
        if elem>max || elem<min {return None}
        let mut l=0;
        let mut r=len;
        let mut m;
        while l<=r {
            m=(l+r)/2;
            if (sorted==1 && cont[m]<*elem) || (sorted==-1 && cont[m]>*elem) { l=m+1; }
            else if (sorted==1 && cont[m]>*elem) || (sorted==-1 && cont[m]<*elem) { r=m-1; }
            else { return Some(m); } 
        }
            
        None
    }
    /// Binary search but returns first element in each case
    pub fn f_binary_search<T: PartialOrd>(cont: &[T], sorted: i8, elem: &T) -> Option<usize> {
        let len=cont.len()-1;
        if &cont[0]==elem {return Some(0);}
        if &cont[len]==elem && &cont[len-1]!=elem {return Some(len);}

        let mut ind=binary_search(cont, sorted, elem)?;
    
        while ind>0 && cont[ind-1]==*elem  {
            let ind2=binary_search(&cont[..ind], sorted, elem);
            match ind2 {
                Some(idx) => ind=idx,
                None => return Some(ind),
            }
        }
        Some(ind)
    }
    /// Binary search but returns last element in each case
    pub fn l_binary_search<T: PartialOrd>(cont: &[T], sorted: i8, elem: &T) -> Option<usize> {
        let len=cont.len()-1;
        if &cont[len]==elem {return Some(len);}
        if &cont[0]==elem && &cont[1]!=elem {return Some(0);}

        let mut ind=binary_search(cont, sorted, elem)?;
    
        while ind<cont.len()-1 && cont[ind+1]==*elem  {
            let ind2=binary_search(&cont[ind+1..], sorted, elem);
            match ind2 {
                Some(idx) => ind+=idx+1,
                None => return Some(ind),
            }
        }
        Some(ind)
    }
    pub fn difference_ref<T: Ord>(cont: &mut Vec<T>, other: &[T]) -> Vec<T> {
        let mut h = make_multiset(other);
        let mut v = vec![];
        let mut out=vec![];
        swap(&mut v, cont);
        for t in v {
            let k = h.get(&t);
            if k.is_some() {
                let mut_ref=h.get_mut(&t).unwrap();
                *mut_ref-=1;
                if *mut_ref==0 { h.remove(&t); }
                out.push(t);
            }
            else { cont.push(t); }
        }
        out
    }
    
    pub fn sort<T: Ord>(cont: &mut [T], reverse: bool, sorted: i8) -> i8 {
        if sorted!=0 {
            if (!reverse && sorted==1) || (reverse && sorted==-1) { return sorted }
            if (!reverse && sorted==-1) || (reverse && sorted==1) { cont.reverse(); return -sorted }
        }
        if reverse { cont.sort_by(|a, b| b.cmp(a)); -1 }
        else {cont.sort(); 1}
    }
    fn sorted_find<T: PartialOrd>(cont: &[T], sorted: i8, elem: &T, mut max_count: isize) -> Vec<usize> {
        let mut v=vec![];
        let s=f_binary_search(cont, sorted, elem);
        if s.is_none() { return v }
        let start=s.unwrap();
        for (i, item) in cont.iter().enumerate().skip(start) {
            if max_count!=0 && item==elem {max_count-=1; v.push(i);}
            else { break }
        }
        v
    }
    pub fn find_fn<T>(cont: &[T], mut f: impl FnMut(&T) -> bool, mut max_count: isize) -> Vec<usize> {
        let mut v=vec![];
        for (i,item) in cont.iter().enumerate() {
            if f(item) { max_count-=1; v.push(i); }
            if max_count==0 { break }
        }
        v
    }
    pub fn find<T: PartialOrd>(cont: &[T], sorted: i8, elem: &T, max_count: isize) -> Vec<usize> {
        if sorted!=0 { sorted_find(cont, sorted, elem, max_count) }
        else { find_fn(cont, |item| item==elem, max_count) }
    }
    fn sorted_count<T: PartialOrd>(cont: &[T], sorted: i8, elem: &T) -> usize {
        let f=f_binary_search(cont, sorted, elem);
        let l=l_binary_search(cont, sorted, elem);
        if let (Some(f_),Some(l_))=(f,l) { l_-f_+1 }
        else {0}
    }
    pub fn count_fn<T>(cont: &[T], mut f: impl FnMut(&T) -> bool) -> usize {
        let mut max_count=0;
        for item in cont { if f(item) { max_count+=1; } }
        max_count
    }
    pub fn count<T: PartialOrd>(cont: &[T], sorted: i8, elem: &T) -> usize {
        if sorted!=0 { sorted_count(cont, sorted, elem) }
        else { count_fn(cont, |item| item==elem) }
    }
    pub fn rotate<T: PartialEq>(cont: &mut [T], mut sorted: i8, r: isize) -> i8 {
        if cont.len()<2 { return sorted }
        let rot = r.unsigned_abs() % cont.len();
        if rot==0 { return sorted }
        if cont[0]!=cont[cont.len()-1] { sorted=0 }
        match r.cmp(&0) {
            Ordering::Greater => { cont.rotate_left(rot); }
            Ordering::Less => { cont.rotate_right(rot); }
            Ordering::Equal => unreachable!()
        }
        sorted
    }
    fn replace_sorted<T: PartialOrd + Clone>(cont: &mut [T], mut sorted: i8, what: &T, to_what: &T, mut max_count: isize) -> i8 {
        let f=f_binary_search(cont, sorted, what);
        if f.is_none() { return sorted }
        let first=f.unwrap();
        for i in first..cont.len() {
            if cont[i]==*what { cont[i]=to_what.clone(); max_count-=1; }
            else { sorted=update_sort(cont,sorted,i-1); break }
            if max_count==0 { sorted=update_sort(cont,sorted,i); break }
        }
        update_sort(cont,sorted,first)
    }
    pub fn replace_fn<T: PartialOrd + Clone>(cont: &mut [T], mut sorted: i8, mut f: impl FnMut(&T)->bool, to_what: &T, mut max_count: isize) -> i8 {
        let mut inds=vec![];
        for (i,item) in cont.iter_mut().enumerate() {
            if f(item) {
                *item=to_what.clone();
                max_count-=1;
                if sorted!=0 {inds.push(i);}
            }
            if max_count==0 { break }
        }
        for i in inds {
            if sorted!=0 {sorted=update_sort(cont,sorted,i);}
            else { break }
        }
        sorted
    }
    pub fn replace<T: PartialOrd + Clone>(cont: &mut [T], sorted: i8, what: &T, to_what: &T, mut max_count: isize) -> i8 {
        if what==to_what { return sorted }
        if sorted==0 {
            for item in cont {
                if item==what { *item=to_what.clone(); max_count-=1; }
                if max_count==0 { break }
            }
            sorted
        }
        else { replace_sorted(cont, sorted, what, to_what, max_count) }
    }
}

impl<T: Clone + Ord> Linear<T> for Vector<T> {
    fn add(&mut self, elem: T, index: Option<isize>) -> &mut Self {
        let last = self.cont.len();
        let ind = safe_index(index.unwrap_or(-1), last+1);
        if ind==last { self.cont.push(elem); }
        else { self.cont.insert(ind, elem); }
        self.sorted=update_sort(&self.cont,self.sorted,ind);
        self
    }
    fn add_slice(&mut self, mut slice: Vec<T>, index: Option<isize>) -> &mut Self {
        let last = self.cont.len();
        let ind = safe_index(index.unwrap_or(-1), last+1);
        let slice_len=slice.len();
        if ind==last{ self.cont.append(&mut slice); }
        else {
            let mut v=Vec::with_capacity(last-ind);
            for _ in 0..last-ind { v.push(self.cont.pop().unwrap()); }
            v.reverse();
            self.cont.append(&mut slice);
            self.cont.append(&mut v);
        }
        if self.sorted!=0 {
            if ind<self.len() { self.sorted=update_sort(&self.cont,self.sorted,ind); }
            else { return self }
            if ind+slice_len-1<self.len() { self.sorted=update_sort(&self.cont,self.sorted,ind+slice_len-1); }
            else { return self }
            let mut i=ind+1;
            while self.sorted!=0 && i<ind+slice_len {
                self.sorted=update_sort(&self.cont,self.sorted,i);
                i+=1;
            }
        }
        self
    }
    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() { self.remove_element(what, count); }
        else { self.sorted=replace(&mut self.cont, self.sorted, what, to_what.unwrap(), count); }
        self
    }
    fn replace_fn(&mut self, mut f: impl FnMut(&T)->bool, to_what: Option<&T>, max_count: Option<isize>) -> &mut Self {
        let mut count = max_count.unwrap_or(-1);
        if count==0 { return self }
        if to_what.is_none() {
            let mut inds=vec![];
            for i in 0..self.cont.len() {
                if f(&self.cont[i]) { 
                    inds.push(i);
                    count-=1;
                    if count==0 { break }
                }
            }
            self.remove_multiple(inds);
        }
        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 {
        if max_count.unwrap_or(-1)==0 || slice.is_empty() { return self }
        let s=slice.len()-1;
        let indices=KMP(&self.cont, slice, max_count);
        if indices.is_empty() { return self }
        let towhat_v=to_what.unwrap_or_default();
        let mut ins_pos=vec![(indices[0],1)];
        let mut removed=0;
        let mut intervals=vec![(indices[0],indices[0]+s)];
        let mut iter=indices.into_iter(); iter.next();
        for ind in iter {
            let last=intervals.len()-1;
            if ind>=intervals[last].0 && ind<=intervals[last].1 {
                intervals[last].1=ind+s;
                ins_pos[last].1+=1;
            }
            else {
                removed+=pointer_cast(intervals[last].1-intervals[last].0+1);
                removed-=pointer_cast(ins_pos[last].1*towhat_v.len());
                intervals.push((ind,ind+s));
                ins_pos.push((((pointer_cast(ind))-removed).unsigned_abs(),1));
            }
        }
        for (start,end) in intervals.into_iter().rev() { self.remove_slice(pointer_cast(start), Some(pointer_cast(end+1))); }
        if !towhat_v.is_empty() {
            for (pos,count) in ins_pos {
                let mut v=vector!(cont: towhat_v.to_vec());
                v.repeat(count);
                self.add_slice(v.cont, Some(pointer_cast(pos)));
            }
        }
        self
    }
    fn distinct(&mut self) -> &mut Self {
        if self.sorted!=0 { self.cont.dedup(); return self; }
        let mut s=BTreeSet::new();
        let mut v=Vec::with_capacity(self.len());
        swap(&mut v, &mut self.cont);
        for elem in v {
            if !s.contains(&elem) { self.cont.push(elem); s.insert(unsafe_ref(&self.cont[self.len()-1]));  }
        }
        self
    }
    fn distinct_fn<U: Ord>(&mut self, mut f: impl FnMut(&T) -> U) -> &mut Self {
        let mut s=BTreeSet::new();
        let mut v=vec![];
        swap(&mut v, &mut self.cont);
        for i in v {
            let res=f(&i);
            if s.insert(res) { self.cont.push(i); }
        }
        self
    }
    fn clear(&mut self) -> &mut Self {
        self.cont.clear();
        self.sorted=0;
        self
    }
    fn reverse(&mut self) -> &mut Self {
        self.cont.reverse();
        self.sorted*=-1;
        self
    }
    fn remove(&mut self, index: Option<isize>) -> &mut Self {
        debug_assert!(!self.cont.is_empty(), "Tried to remove element from empty Vector!");
        let ind = safe_index(index.unwrap_or(-1),self.cont.len());
        if ind==self.cont.len()-1 { self.cont.pop(); }
        else { self.cont.remove(ind); }
        self
    }
    fn remove_slice(&mut self, from: isize, to: Option<isize>) -> &mut Self {
        debug_assert!(!self.cont.is_empty(), "Tried to remove element from empty Vector!");
        let start=safe_index(from, self.len());
        let end=safe_index(to.unwrap_or(-1), self.len()+1);
        debug_assert!(self.cont.len() >= end-start, "Tried to remove {} elements from Vector with len {}!",end-start, self.len());
        if end==self.len() { self.cont.truncate(self.cont.len()-(end-start)); }
        else {
            let mut tail=Vec::with_capacity(self.len()-end);
            for _ in 0..self.len()-end { tail.push(self.cont.pop().unwrap()); } tail.reverse();
            for _ in 0..end-start { self.cont.pop(); }
            self.cont.append(&mut tail);
        }
        self
    }
    fn pop(&mut self, index: Option<isize>) -> T {
        debug_assert!(!self.cont.is_empty(), "Tried to pop element from empty Vector!");
        let ind = safe_index(index.unwrap_or(-1),self.cont.len());
        if ind==self.cont.len()-1 { self.cont.pop().unwrap() }
        else { self.cont.remove(ind) }
    }
    fn pop_slice(&mut self, from: isize, to: Option<isize>) -> Vec<T> {
        debug_assert!(!self.cont.is_empty(), "Tried to pop element from empty Vector!");
        let start=safe_index(from, self.len());
        let end=safe_index(to.unwrap_or(-1), self.len()+1);
        let mut v=vec![];
        debug_assert!(self.cont.len() >= end-start, "Tried to pop {} elements from Vector with len {}!", end-start, self.len());
        if end==self.len() { for _ in 0..end-start { v.push(self.cont.pop().unwrap()); } v.reverse(); }
        else {
            let mut tail=Vec::with_capacity(self.len()-end);
            for _ in 0..self.len()-end { tail.push(self.cont.pop().unwrap()); } tail.reverse();
            for _ in 0..end-start { v.push(self.cont.pop().unwrap()); } v.reverse();
            self.cont.append(&mut tail);
        }
        v
    }
    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, mut other: Self) -> &mut Self {
        let len=self.cont.len();
        let l=other.cont.len();
        self.cont.append(&mut other.cont);
        if self.sorted!=other.sorted { self.sorted=0; }
        if l!=0 { self.sorted=update_sort(&self.cont,self.sorted,len); }
        self
    }
    fn difference(&mut self, other: &Self) -> &mut Self {
        let mut h = make_multiset(other);
        let mut v = vec![];
        swap(&mut v, &mut self.cont);
        for t in v {
            let k = h.get(&t);
            if k.is_some() {
                let mut_ref=h.get_mut(&t).unwrap();
                *mut_ref-=1;
                if *mut_ref==0 { h.remove(&t); }
            }
            else { self.cont.push(t); }
        }
        self
    }
    fn intersect(&mut self, other: &Self) -> &mut Self {
        let mut h=make_multiset(other);
        let mut v = vec![];
        swap(&mut v, &mut self.cont);
        for t in v {
            let k = h.get(&t);
            if k.is_some() {
                let mut_ref=h.get_mut(&t).unwrap();
                *mut_ref-=1;
                if *mut_ref==0 { h.remove(&t); }
                self.cont.push(t);
            }
        }
        self
    }
    fn sym_diff(&mut self, mut other: Self) -> &mut Self {
        let removed=vector![cont: difference_ref(&mut other.cont, self)];
        difference_ref(&mut self.cont,&other);
        self.difference(&removed);
        self.union(other)
    }
    fn repeat(&mut self, n: usize) ->  &mut Self {
        if n==0 { self.clear(); return self }
        if n==1 { return self }
        if self.sorted!=0 && self.cont[0]!=self.cont[self.cont.len()-1] { self.sorted=0; }

        // If `n` is larger than zero, it can be split as
        // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.
        // `2^expn` is the number represented by the leftmost '1' bit of `n`,
        // and `rem` is the remaining part of `n`.

        // Using `Vec` to access `set_len()`.
        let capacity = self.len().checked_mul(n).unwrap();
        let mut buf = Vec::with_capacity(capacity);

        let mut tmp=Vec::new();
        swap(&mut tmp, &mut self.cont);

        // `2^expn` repetition is done by doubling `buf` `expn`-times.
        buf.extend(tmp);
        {
            let mut m = n >> 1;
            // If `m > 0`, there are remaining bits up to the leftmost '1'.
            while m > 0 {
                buf.extend(buf.clone());

                m >>= 1;
            }
        }

        // `rem` (`= n - 2^expn`) repetition is done by copying
        // first `rem` repetitions from `buf` itself.
        let rem_len = capacity - buf.len(); // `self.len() * rem`
        if rem_len > 0 {
            // `buf.extend(buf[0 .. rem_len])`:
            unsafe {
                buf.extend(unsafe_ref(&buf).iter().take(rem_len).cloned());
                // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`).
                buf.set_len(capacity);
            }
        }
        self.cont=buf;
        self
    }
    fn merge(&mut self, mut other: Self) -> &mut Self {
        debug_assert!(!(self.sorted==0 || other.sorted==0), "Tried to merge unsorted Vector(s)!");
        let mut f_v=vec![];
        let mut s_v=vec![];
        swap(&mut self.cont, &mut f_v);
        swap(&mut other.cont, &mut s_v);

        self.cont.reserve(f_v.len()+other.len());

        let b=self.sorted==other.sorted;

        let mut first=f_v.into_iter();
        let mut second=s_v.into_iter();
        let mut i=first.next();
        let mut j=if b {second.next()} else {second.next_back()};

        while i.is_some() && j.is_some() {
            if (self.sorted==1 && i>=j) || (self.sorted==-1 && i<=j) {
                self.cont.push(j.unwrap());
                j=if b {second.next()} else {second.next_back()};
            }
            else {
                self.cont.push(i.unwrap());
                i=first.next();
            }
        }
        if let Some(val) = i { self.cont.push(val); self.cont.append(&mut first.collect()); }
        if j.is_some() {
            self.cont.push(j.unwrap());
            let mut v=if b {second.collect()} else {second.rev().collect()};
            self.cont.append(&mut v);
        }
        self
    }
}


impl<T> Vector<T> {
    /// Constructs a new, empty `Vector<T>`.
    ///
    /// The vector will not allocate until elements are pushed onto it.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ryley::structs::prelude::Vector;
    /// let mut vec: Vector<i32> = Vector::new();
    /// ```
    #[must_use]
    pub const fn new() -> Self {
        Self {
            cont: Vec::new(),
            sorted: 0,
        }
    }
    /// Reserves capacity for at least `additional` more elements to be inserted
    /// in the given `Vector<T>`. The collection may reserve more space to
    /// speculatively avoid frequent reallocations. After calling `reserve`,
    /// capacity will be greater than or equal to `self.len() + additional`.
    /// Does nothing if capacity is already sufficient.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ryley::vector;
    /// let mut v = vector![1];
    /// v.reserve(10);
    /// assert!(v.capacity() >= 11);
    /// ```
    pub fn reserve(&mut self, additional: usize) -> &mut Self {
        self.cont.reserve(additional);
        self
    }
    /// Returns the total number of elements the vector can hold without
    /// reallocating.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ryley::structs::prelude::*;
    /// let mut v = vector![cont: Vec::with_capacity(10)];
    /// v.add(42,None);
    /// assert!(v.capacity() >= 10);
    /// ```
    #[must_use]
    pub fn capacity(&self) -> usize {
        self.cont.capacity()
    }
}
impl<T: Clone + Ord> Vector<T> {
    /// It sorts elements and applies distinct to the `Vector` 
    /// (each element can be in the vector once and only once)
    /// 
    /// # Warning!
    /// This is an optimisational function as this method is NOT part of
    /// the Unified Data Structure Interface! As such it doesn't have any documentation.
    pub fn distinct_sort(&mut self, reverse: bool) -> &mut Self {
        if self.sorted!=0 {
            self.cont.dedup();
            if (self.sorted==1 && !reverse) || (self.sorted==-1 && reverse) { return self; }
            return self.reverse();
        }
        let mut v = vec![];
        swap(&mut v, &mut self.cont);
        let s=v.into_iter().collect::<BTreeSet<_>>();
        if reverse {
            self.cont=s.into_iter().rev().collect();
            self.sorted = -1;
        }
        else {
            self.cont=s.into_iter().collect();
            self.sorted=1;
        }
        self
    }
    fn remove_element(&mut self, elem: &T, max_count: isize) {
        let mut start=0;
        let mut count=max_count;
        if self.sorted!=0 {
            let bin=f_binary_search(&self.cont, self.sorted, elem);
            if bin.is_none() { return }
            start = bin.unwrap();
        }
        let mut inds=vec![];
        for i in start..self.cont.len() {
            if &self.cont[i]==elem {
                inds.push(i);
                count-=1;
                if count==0 { break }
            }
            else if self.sorted!=0 { break }
        }
        self.remove_multiple(inds);
    }
    /// Remove multiple elements from vector all at once
    /// 
    /// Assumes `inds` are sorted
    fn remove_multiple(&mut self, mut inds: Vec<usize>) {
        if inds.is_empty() { return }
        let mut ind=inds.pop().unwrap();
        let mut v=vec![];
        for i in (0..self.cont.len()).rev() {
            let elem=self.cont.pop();
            if i==ind { 
                match inds.pop() {
                    Some(idx) => ind=idx,
                    None => break,
                }
            }
            else { v.push(elem.unwrap()); }
        }
        v.reverse();
        self.cont.append(&mut v);
    }
}
impl<T> Vector<T> {
    /// Consumes the old and returns a new vector made of subslices that satisfy
    /// `f`. The matched elements are not contained in the subslices.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ryley::structs::prelude::*;
    /// let vec = vector![11, 12, 40, 33, 98, 20, 16];
    /// let sp=vec.split(|num| num % 10 == 0);
    ///
    /// assert_eq!(sp, vector![vector![11, 12], vector![33, 98], vector![16]]);
    /// ```
    ///
    /// If the first element is matched, an empty slice will be the first item
    /// returned by the method. Similarly, if the last element in the slice
    /// is matched, an empty slice will be the last item returned by the
    /// iterator:
    ///
    /// ```
    /// # use ryley::structs::prelude::*;
    /// let vec = vector![3, 10, 40, 33];
    /// let sp = vec.split(|num| num % 3 == 0);
    ///
    /// assert_eq!(sp, vector![vector![], vector![10, 40], vector![]]);
    /// ```
    ///
    /// If two matched elements are directly adjacent, an empty slice will be
    /// present between them:
    ///
    /// ```
    /// # use ryley::structs::prelude::*;
    /// let vec = vector![10, 6, 33, 20];
    /// let sp = vec.split(|num| num % 3 == 0);
    ///
    /// assert_eq!(sp, vector![vector![10], vector![], vector![20]]);
    /// ```
    pub fn split(self, mut f: impl FnMut(&T) -> bool) -> Vector<Self> {
        let mut v=vector![];
        let s=self.sorted;
        let mut temp=vector![s;];
        for elem in self {
            if f(&elem) { 
                let mut k=vector![s;];
                swap(&mut k.cont, &mut temp.cont);
                v.cont.push(k);
            }
            else { temp.cont.push(elem); }
        }
        let mut k=vector![s;];
        swap(&mut k.cont, &mut temp.cont);
        v.cont.push(k);
        v
    }
}
impl<T: Clone + Ord> Vector<Vector<T>> {
    /// Flattens a slice of `T` into a single value, placing a
    /// given separator between each.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ryley::structs::prelude::*;
    /// assert_eq!(vector![vector![1, 2], vector![3, 4]].join(Some(&vec![0])), vector![1, 2, 0, 3, 4]);
    /// assert_eq!(vector![vector![1, 2], vector![3, 4]].join(None), vector![1, 2, 3, 4]);
    /// ```
    #[must_use = "Join consumes the Vector"]
    pub fn join(self, sep: Option<&Vec<T>>) -> Vector<T> {
        let s_len=self.cont.len()-1;
        let mut v=vector![if self.len()>0 {self.cont[0].sorted} else {0};];
        for (i,mut elem) in self.into_iter().enumerate()
        {
            let len=v.len();
            v.cont.append(&mut elem.cont);
            if len>0 && v.sorted!=0 && elem.sorted==v.sorted {v.sorted=update_sort(&v.cont, v.sorted, len-1)}
            else {v.sorted=0;}
            if i!=s_len {
                if let Some(val)=sep {
                    v.cont.append(&mut val.clone());
                }
            }
        }
        v
    }
}
impl<T: Clone + Default + Add<Output = T>> Vector<T> {
    /// Sums the elements of a `Vector`.
    ///
    /// Takes each element, adds them together, and returns the result.
    /// If Vector is empty it returns the default.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// # use ryley::structs::prelude::*;
    /// let v = vector![1, 2, 3];
    /// let sum: i32 = v.sum();
    /// assert_eq!(sum, 6);
    /// ```
    #[must_use = "Sum does not consume the Vector"]
    pub fn sum(&self) -> T {
        let mut out=T::default();
        for item in self { out=out+item.clone(); }
        out
    }
}

/// Implements scalar operations for `Vector`
macro_rules! scalar_op {
    ($for:tt, $trait:tt, $trait2:tt, $name:ident, $name2:ident, $keep_sorted:tt) => {
        impl<T: Ord + Clone + $trait2> $trait<T> for $for<T> {
            type Output = Self;
        
            fn $name(mut self, rhs: T) -> Self::Output {
                self.$name2(rhs);
                self
            }
        }
        impl<T: Ord + Clone + $trait2> $trait2<T> for $for<T> {
            fn $name2(&mut self, rhs: T) {
                if !$keep_sorted || self.is_empty() { 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<T: $trait2<U>,U: Clone> $trait<U> for $for<T> {
            type Output = Self;
        
            fn $name(mut self, rhs: U) -> Self::Output {
                self.$name2(rhs);
                self
            }
        }
        impl<T: $trait2<U>,U: Clone> $trait2<U> for $for<T> {
            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<T: Ord + $trait<Output = T>> $trait for $for<T> {
            type Output = Self;
        
            fn $name(self) -> Self::Output {
                let sorted=self.sorted;
                let mut res=self.into_iter().map(|elem| elem.$name()).collect::<$for<_>>();
                res.sorted=-sorted;
                res
            }
        }
    };
}

/// Implements vector operations for `Vector`
macro_rules! vector_op {
    ($for:tt, $trait:tt, $trait2:tt, $name:ident, $name2:ident) => {
        impl<T: $trait2> $trait for $for<T> {
            type Output = Self;
        
            fn $name(mut self, other: Self) -> Self {
                self.$name2(other);
                self
            }
        }
        impl<T: $trait2> $trait2 for $for<T> {
            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!(Vector, Neg, neg);
scalar_op!(Vector, Not, not);
scalar_op!(Vector, Add, AddAssign, add, add_assign, true);
scalar_op!(Vector, Sub, SubAssign, sub, sub_assign, true);
scalar_op!(Vector, Mul, MulAssign, mul, mul_assign, true);
scalar_op!(Vector, Div, DivAssign, div, div_assign, true);
scalar_op!(Vector, Rem, RemAssign, rem, rem_assign, false);
scalar_op!(shift Vector, Shl, ShlAssign, shl, shl_assign);
scalar_op!(shift Vector, Shr, ShrAssign, shr, shr_assign);
scalar_op!(Vector, BitAnd, BitAndAssign, bitand, bitand_assign, false);
scalar_op!(Vector, BitOr,  BitOrAssign,  bitor,  bitor_assign,  false);
scalar_op!(Vector, BitXor, BitXorAssign, bitxor, bitxor_assign, false);

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

//Indexing
impl<T,I: RyleySliceIndex<[T]>> Index<I> for Vector<T> {
    type Output = I::Output;

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