wmathrs 0.1.0

use crate::scalar::{ One, Zero, Latex, Similar, Neg, Con, Pow, DivLeft }; 
use crate::fraction::{ Fraction }; 
use crate::number_theory::{ factor, leastest_common_multiple_in_vector as lcm, greatest_common_divisor_in_vector as gcd }; 
use std::fmt::{ Formatter, Display, Result }; 
use std::cmp::{ PartialEq, Eq }; 
use std::ops::{ Add, Sub, Mul, Div, Rem }; 
use std::iter::{ Iterator, Sum }; 

#[derive(Debug, Clone)]
/// 多项式
pub struct Polynomial<T> {
    coe: Vec<T>
}

#[macro_export]
/// poly!(x) => Polynomial::new(x)
macro_rules! poly {
    ($coe:expr) => {
        Polynomial::new($coe); 
    }
}

#[macro_export]
/// poly_from!(x, y, z) => Polynomial::new(&vec![x, y, z])
macro_rules! poly_from {
    ($($item:expr),+) => {
        Polynomial::new(&vec![$($item),+])
    }
}

impl <T: Clone> Polynomial<T> {
    pub fn new(coe: &Vec<T>) -> Self {
        assert!(coe.len() > 0); 
        Polynomial { coe: coe.clone() }
    }

    pub fn get_coe(&self) -> &Vec<T> {
        &self.coe
    }

    pub fn get_coe_mut(&mut self) -> &mut Vec<T> {
        &mut self.coe
    }

    /// (a*x^2+b*x-c).multiply_by(d, e) => a*d*x^(2+e)+b*d*x^(1+e)-c*d*x^e
    pub fn multiply_by<U, V>(&self, num: U, degree: usize) -> Polynomial<V> where
        T: Mul<U, Output = V>,
        U: Clone,
        V: Clone + Zero {
        let mut coe = vec![(self.coe[0].clone() * num.clone()).get_zero(); degree]; 
        for t in self.coe.iter() {
            coe.push(t.clone() * num.clone()); 
        }
        Polynomial::new(&coe)
    }

    /// (a*x^2+b*x-c).multiply_left_by(d, e) => d*a*x^(2+e)+d*b*x^(1+e)-d*c*x^e
    pub fn multiply_left_by<U, V>(&self, num: U, degree: usize) -> Polynomial<V> where
        U: Clone + Mul<T, Output = V>,
        V: Clone + Zero {
        let mut coe = vec![(num.clone() * self.coe[0].clone()).get_zero(); degree]; 
        for t in self.coe.iter() {
            coe.push(num.clone() * t.clone()); 
        }
        Polynomial::new(&coe)
    }

    /// (a*x^2+b*x-c).divide_by(d) => a/d*x^2+b/d*x-c/d
    pub fn divide_by<U, V>(&self, num: U) -> Polynomial<V> where
        T: Div<U, Output = V>, 
        U: Clone, 
        V: Clone {
        let mut coe = Vec::with_capacity(self.coe.len()); 
        for t in self.coe.iter() {
            coe.push(t.clone() / num.clone()); 
        }
        Polynomial::new(&coe)
    }

    /// (a*x^2+b*x-c).divide_left_by(d) => a\d*x^2+b\d*x-c\d
    pub fn divide_left_by<U, V>(&self, num: U) -> Polynomial<V> where
        T: DivLeft<U, Output = V>, 
        U: Clone, 
        V: Clone {
        let mut coe = Vec::with_capacity(self.coe.len()); 
        for t in self.coe.iter() {
            coe.push(t.div_left(&num)); 
        }
        Polynomial::new(&coe)
    }

    /// (a*x^2+b*x+c).value(n) = a*n^2+b*n+c
    pub fn value<U, V>(&self, num: U) -> V where
        T: Mul<U, Output = V>, 
        U: Clone + Mul<Output = U> + One, 
        V: Clone + Add<Output = V> {
        let len = self.coe.len(); 
        let mut result = self.coe[0].clone() * num.get_one(); 
        let mut num_mut = num.clone(); 
        for i in 1..len {
            result = self.coe[i].clone() * num_mut.clone() + result.clone(); 
            num_mut = num_mut.clone() * num.clone(); 
        }
        return result; 
    }

    /// (a*x^2+b*x+c).value_left(n) = n^2*a+n*b+c
    pub fn value_left<U, V>(&self, num: U) -> V where
        U: Clone + Mul<Output = U> + Mul<T, Output = V> + One, 
        V: Clone + Add<Output = V> {
        let len = self.coe.len(); 
        let mut result = num.get_one() * self.coe[0].clone(); 
        let mut num_mut = num.clone(); 
        for i in 1..len {
            result = num_mut.clone() * self.coe[i].clone() + result.clone(); 
            num_mut = num_mut.clone() * num.clone(); 
        }
        return result; 
    }
}

impl <T: Clone + Zero> Polynomial<T> {
    /// (0x^3+2x^2-4).adjust() = 2x^2-4
    pub fn adjust(&self) -> Self {
        let mut coe = self.coe.clone(); 
        let mut len = coe.len(); 
        while len > 1 && coe[len-1].eq_zero() {
            coe.pop(); 
            len = coe.len(); 
        }
        Polynomial::new(&coe)
    }

    /// ((3e-8)x^3+(1e-3)x^2-(2e-8)x+3).similar_adjust(1e-6) = (1e-3)x^2-(2e-8)x+3
    pub fn similar_adjust(&self, precision: f64) -> Self {
        let mut coe = self.coe.clone(); 
        let mut len = coe.len(); 
        while len > 1 && coe[len-1].similar_zero(precision) {
            coe.pop(); 
            len = coe.len(); 
        }
        Polynomial::new(&coe)
    }
}

impl <T> Polynomial<T> where
    T: Clone + Div<Output = T> + Sub<Output = T> + Mul<Output = T> + Add<Output = T> + Zero + One + PartialEq {
    pub fn gcd(&self, other: &Self) -> Self {
        let mut _self = self.clone(); 
        let mut _other = other.clone(); 
        let mut temp = (_self.clone() % _other.clone()).adjust(); 
        while temp.coe.len() > 1 {
            _self = _other.clone(); 
            _other = temp.clone(); 
            temp = (_self.clone() % _other.clone()).adjust(); 
        }
        return _other; 
    }

    /// 返回(gcd, x, y)使得 self * x + other * y = self.gcd(other)
    pub fn gcde(&self, other: &Self) -> (Self, Self, Self) {
        let temp = (self.clone() % other.clone()).adjust(); 
        if temp.coe.len() == 1 {
            return (other.clone(), self.get_zero(), other.get_one())
        } else {
            let (gcd, _x, _y) = other.gcde(&temp); 
            let x = _y.clone(); 
            let y = _x.clone() - (self.clone() / other.clone()).0 * x.clone(); 
            return (gcd, x, y); 
        }
    }

    pub fn similar_gcd(&self, other: &Self, precision: f64) -> Self {
        let mut _self = self.clone(); 
        let mut _other = other.clone(); 
        let mut temp = (_self.clone() % _other.clone()).similar_adjust(precision); 
        while temp.coe.len() > 1 {
            _self = _other.clone(); 
            _other = temp.clone(); 
            temp = (_self.clone() % _other.clone()).similar_adjust(precision); 
        }
        return _other; 
    }

    pub fn similar_gcde(&self, other: &Self, precision: f64) -> (Self, Self, Self) {
        let temp = (self.clone() % other.clone()).similar_adjust(precision); 
        if temp.coe.len() == 1 {
            return (other.clone(), self.get_zero(), other.get_one())
        } else {
            let (gcd, _x, _y) = other.similar_gcde(&temp, precision); 
            let x = _y.clone(); 
            let y = _x.clone() - (self.clone() / other.clone()).0 * x.clone(); 
            return (gcd, x, y); 
        }
    }
}

impl Polynomial<Fraction> {
    /// 有理数多项式的本原化
    pub fn primitive(&self) -> Polynomial<i128> {
        let len = self.coe.len(); 
        let mut num = Vec::with_capacity(len); 
        let mut den = Vec::with_capacity(len); 
        for frac in self.coe.iter() {
            num.push(frac.get_num().abs() as u128); 
            den.push(frac.get_den().abs() as u128); 
        }
        let times = Fraction::new(lcm(&den) as i128, gcd(&num) as i128); 
        let mut coe = Vec::with_capacity(len); 
        for frac in self.multiply_by(times, 0).coe.iter() {
            coe.push(frac.get_num()); 
        }
        Polynomial::new(&coe)
    }
}

macro_rules! impl_rational_roots_for {
    ($($ty:ty)*) => {$(
        impl Polynomial<$ty> {
            /// 求所有有理根
            pub fn rational_roots(&self) -> Vec<Fraction> {
                let mut _self = self.adjust(); 
                if _self.coe.len() == 1 { return vec![]; }
                if _self.coe.len() == 2 { return vec![Fraction::new(-_self.coe[0] as i128, _self.coe[1] as i128)]; }
                let mut roots = vec![]; 
                if _self.coe[0].eq_zero() {
                    roots.push(Fraction::new(0, 1)); 
                    let mut index = 1; 
                    while _self.coe[index].eq_zero() { index += 1; }
                    _self.coe = _self.coe.split_off(index); 
                }
                let len = _self.coe.len(); 
                let num_vec = factor(_self.coe[0] as u128); 
                let den_vec = factor(_self.coe[len-1] as u128); 
                let mut fracs = vec![]; 
                for num in num_vec.iter() {
                    for den in den_vec.iter() {
                        fracs.push(Fraction::new(*num as i128, *den as i128)); 
                    }
                }
                fracs.sort(); 
                fracs.dedup(); 
                for frac in fracs {
                    if self.value(frac).eq_zero() {
                        roots.push(frac); 
                    }
                    if self.value(frac.neg()).eq_zero() {
                        roots.push(frac.neg()); 
                    }
                }
                return roots; 
            }
        }
    )*}
}
impl_rational_roots_for!(i8 i16 i32 i64 i128 isize); 

impl Polynomial<f64> {
    /// 求导
    pub fn derived(&self) -> Polynomial<f64> {
        if self.coe.len() == 1 { return Polynomial::new(&vec![0.0]); }
        let mut coe = Vec::with_capacity(self.coe.len()-1); 
        for (i, n) in self.coe.iter().enumerate() {
            if i != 0 { coe.push(n * i as f64); }
        }
        return Polynomial::new(&coe); 
    }

    /// 积分
    pub fn integral(&self) -> Polynomial<f64> {
        let mut coe = vec![0.0]; 
        for (i, n) in self.coe.iter().enumerate() {
            coe.push(n / (i + 1) as f64); 
        }
        return Polynomial::new(&coe); 
    }

    fn real_root_multiplication(&self, start: f64, pos: bool, x_precision: f64, y_precision: f64) -> Option<f64> {
        if self.value(start) == 0.0 { return Some(start); }
        let mut start = start; 
        let start_pos = if self.value(start) > 0.0 { true } else { false }; 
        let mut x_delta = if pos { 1f64 } else { -1f64 }; 
        let mut y_delta = self.value(start + x_delta); 
        let (x_precision, y_precision) = (x_precision.abs(), y_precision.abs()); 
        while (x_precision != 0.0 && x_delta.abs() > x_precision) || (y_precision != 0.0 && y_delta.abs() > y_precision) {
            if !start.is_normal() { return None; }
            if (y_delta < 0.0) ^ start_pos {
                start += x_delta; 
                x_delta *= 2.0; 
            } else {
                x_delta /= 2.0; 
            }
            y_delta = self.value(start + x_delta); 
        }
        return Some(start); 
    }

    fn real_root_dichotomy(&self, left: f64, right: f64, x_precision: f64, y_precision: f64) -> Option<f64> {
        let (left_pos, right_pos); 
        let (mut left, mut right) = (left, right); 
        match self.value(left) {
            x if x == 0.0 => return Some(left), 
            x if x > 0.0 => left_pos = true, 
            _ => left_pos = false, 
        }
        match self.value(right) {
            x if x == 0.0 => return Some(right), 
            x if x > 0.0 => right_pos = true, 
            _ => right_pos = false, 
        }
        if !(left_pos ^ right_pos) { return None; }
        let mut mid = (left + right) / 2.0; 
        let mut x_delta = right - left; 
        let mut y_delta = self.value(mid); 
        let (x_precision, y_precision) = (x_precision.abs(), y_precision.abs()); 
        while (x_precision != 0.0 && x_delta > x_precision) || (y_precision != 0.0 && y_delta.abs() > y_precision) {
            if (y_delta > 0.0) ^ left_pos {
                right = mid; 
            } else {
                left = mid; 
            }
            mid = (left + right) / 2.0; 
            x_delta = right - left; 
            y_delta = self.value(mid); 
        }
        return Some(mid); 
    }

    /// 求所有实数根
    pub fn real_roots(&self, x_precision: f64, y_precision: f64) -> Vec<f64> {
        let (x_precision, y_precision) = (x_precision.abs(), y_precision.abs()); 
        let _self = self.adjust(); 
        let len = _self.coe.len(); 
        if len == 1 { return vec![]; }
        if len == 2 { return vec![-_self.coe[0] / _self.coe[1]]; }
        
        let derived_real_roots = _self.derived().real_roots(x_precision, y_precision); 
        if derived_real_roots.is_empty() {
            let pos = if (_self.coe[len-1] > 0.0) ^ (_self.value(0.0) > 0.0) { true } else { false }; 
            if let Some(root) = _self.real_root_multiplication(0.0, pos, x_precision, y_precision) {
                return vec![root]; 
            } else {
                return vec![]; 
            }
        } else {
            let mut real_roots = vec![]; 
            if (_self.coe[len-1] > 0.0) ^ (_self.value(derived_real_roots[0]) > 0.0) {
                if let Some(root) = _self.real_root_multiplication(derived_real_roots[0], true, x_precision, y_precision) { real_roots.push(root); }
            }
            for i in 1..derived_real_roots.len() {
                if let Some(root) = _self.real_root_dichotomy(derived_real_roots[i], derived_real_roots[i-1], x_precision, y_precision) {
                    if !real_roots.contains(&root) { real_roots.push(root); }
                }
            }
            if (len % 2 == 0) ^ (_self.coe[len-1] > 0.0) ^ (_self.value(derived_real_roots[derived_real_roots.len()-1]) > 0.0) {
                if let Some(root) = _self.real_root_multiplication(derived_real_roots[derived_real_roots.len()-1], false, x_precision, y_precision) {
                    if !real_roots.contains(&root) { real_roots.push(root); }
                }
            }
            return real_roots; 
        }
    }

}

impl <T: Display> Display for Polynomial<T> {
    fn fmt(&self, f: &mut Formatter) -> Result {
        let len = self.coe.len(); 
        for i in 1..len {
            write!(f, "({})*x^{}+", self.coe[len-i], len-i)?; 
        }
        write!(f, "({})", self.coe[0])
    }
}

impl <T: Latex> Latex for Polynomial<T> {
    fn latex(&self) -> String {
        let mut string = String::new(); 
        let len = self.coe.len(); 
        for i in 1..len {
            string.push_str(&format!("({})x^{{{}}}+", self.coe[len-i].latex(), len-i)); 
        }
        string.push_str(&format!("({})", self.coe[0].latex())); 
        return string; 
    }
}

impl <T: Clone + One + Zero + PartialEq> One for Polynomial<T> {
    fn get_one(&self) -> Self {
        Polynomial::new(&vec![self.coe[0].get_one()])
    }

    fn eq_one(&self) -> bool {
        let temp = self.adjust(); 
        temp.coe.len() == 1 && temp.coe[0].eq_one()
    }

    fn similar_one(&self, precision: f64) -> bool {
        let temp = self.similar_adjust(precision); 
        temp.coe.len() == 1 && temp.coe[0].similar_one(precision)
    }
}

impl <T: Clone + Zero + PartialEq> Zero for Polynomial<T> {
    fn get_zero(&self) -> Self {
        Polynomial::new(&vec![self.coe[0].get_zero()])
    }

    fn eq_zero(&self) -> bool {
        let temp = self.adjust(); 
        temp.coe.len() == 1 && temp.coe[0].eq_zero()
    }

    fn similar_zero(&self, precision: f64) -> bool {
        let temp = self.similar_adjust(precision); 
        temp.coe.len() == 1 && temp.coe[0].similar_zero(precision)
    }
}

impl <T: Neg> Neg for Polynomial<T> where <T as Neg>::Output: Clone {
    type Output = Polynomial<<T as Neg>::Output>; 
    fn neg(&self) -> Self::Output where <T as Neg>::Output: Clone {
        let mut coe = Vec::with_capacity(self.coe.len()); 
        for i in self.coe.iter() { coe.push(i.neg()); }
        Polynomial::new(&coe)
    }
}

impl <T: Con> Con for Polynomial<T> where <T as Con>::Output: Clone {
    type Output = Polynomial<<T as Con>::Output>; 
    fn con(&self) -> Self::Output where <T as Con>::Output: Clone {
        let mut coe = Vec::with_capacity(self.coe.len()); 
        for i in self.coe.iter() { coe.push(i.con()); }
        Polynomial::new(&coe)
    }
}

impl <T: Clone + Mul<Output = T> + Add<Output = T> + One + Zero + PartialEq> Pow for Polynomial<T> {
    type Output = Self; 
    fn pow(&self, power: u32) -> Self::Output {
        let mut result = self.get_one(); 
        let mut now = self.clone(); 
        let mut power = power; 
        while power != 0 {
            if power & 1 == 1 {
                result = result.clone() * now.clone(); 
            }
            now = now.clone() * now.clone(); 
            power >>= 1; 
        }
        return result; 
    }
}

impl <T: PartialEq> PartialEq for Polynomial<T> {
    fn eq(&self, other: &Self) -> bool {
        if self.coe.len() != other.coe.len() { return false; }
        let mut result = true; 
        for (x, y) in self.coe.iter().zip(other.coe.iter()) {
            if x != y {
                result = false; 
                break; 
            }
        }
        return result; 
    }
}

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

impl <T: Similar> Similar for Polynomial<T> {
    fn similar(&self, other: &Self, precision: f64) -> bool {
        if self.coe.len() != other.coe.len() { return false; }
        let mut result = true; 
        for (x, y) in self.coe.iter().zip(other.coe.iter()) {
            if !x.similar(y, precision) {
                result = false; 
                break; 
            }
        }
        return result; 
    }
}

impl <T, U, V> Add<Polynomial<U>> for Polynomial<T> where
    T: Clone + Add<U, Output = V> + Zero, 
    U: Clone + Zero, 
    V: Clone {
    type Output = Polynomial<V>; 
    fn add(self, other: Polynomial<U>) -> Self::Output {
        if self.coe.len() >= other.coe.len() {
            let mut coe = Vec::with_capacity(self.coe.len()); 
            for i in 0..other.coe.len() {
                coe.push(self.coe[i].clone() + other.coe[i].clone()); 
            }
            let other_zero = other.coe[0].get_zero(); 
            for i in other.coe.len()..self.coe.len() {
                coe.push(self.coe[i].clone() + other_zero.clone()); 
            }
            return Polynomial::new(&coe); 
        } else {
            let mut coe = Vec::with_capacity(other.coe.len()); 
            for i in 0..self.coe.len() {
                coe.push(self.coe[i].clone() + other.coe[i].clone()); 
            }
            let self_zero = self.coe[0].get_zero(); 
            for i in self.coe.len()..other.coe.len() {
                coe.push(self_zero.clone() + other.coe[i].clone()); 
            }
            return Polynomial::new(&coe); 
        }
    }
}

impl <T, U, V> Sub<Polynomial<U>> for Polynomial<T> where
    T: Clone + Sub<U, Output = V> + Zero, 
    U: Clone + Zero, 
    V: Clone {
    type Output = Polynomial<V>; 
    fn sub(self, other: Polynomial<U>) -> Self::Output {
        if self.coe.len() >= other.coe.len() {
            let mut coe = Vec::with_capacity(self.coe.len()); 
            for i in 0..other.coe.len() {
                coe.push(self.coe[i].clone() - other.coe[i].clone()); 
            }
            let other_zero = other.coe[0].get_zero(); 
            for i in other.coe.len()..self.coe.len() {
                coe.push(self.coe[i].clone() - other_zero.clone()); 
            }
            return Polynomial::new(&coe); 
        } else {
            let mut coe = Vec::with_capacity(other.coe.len()); 
            for i in 0..self.coe.len() {
                coe.push(self.coe[i].clone() - other.coe[i].clone()); 
            }
            let self_zero = self.coe[0].get_zero(); 
            for i in self.coe.len()..other.coe.len() {
                coe.push(self_zero.clone() - other.coe[i].clone()); 
            }
            return Polynomial::new(&coe); 
        }
    }
}

impl <T, U, V> Mul<Polynomial<U>> for Polynomial<T> where
    T: Clone + Mul<U, Output = V>, 
    U: Clone, 
    V: Clone + Add<Output = V> {
    type Output = Polynomial<V>; 
    fn mul(self, other: Polynomial<U>) -> Self::Output {
        let len = self.coe.len() + other.coe.len() - 1; 
        let mut coe = Vec::with_capacity(len); 
        for (i, t) in self.coe.iter().enumerate() {
            for (j, u) in other.coe.iter().enumerate() {
                if i == 0  || j == other.coe.len()-1 {
                    coe.push(t.clone() * u.clone()); 
                } else {
                    coe[i+j] = coe[i+j].clone() + t.clone() * u.clone(); 
                }
            }
        }
        Polynomial::new(&coe)
    }
}

impl <T, U, V> Div<Polynomial<U>> for Polynomial<T> where
    T: Clone + Div<U, Output=V> + Sub<Output = T> + Zero + PartialEq, 
    U: Clone + Mul<V, Output=T> + Zero, 
    V: Clone + Zero {
    type Output = (Polynomial<V>, Polynomial<T>); 
    fn div(self, other: Polynomial<U>) -> Self::Output {
        let mut t = self.adjust(); 
        let u = other.adjust(); 
        let mut t_len = t.coe.len(); 
        let u_len = u.coe.len(); 
        if t_len < u_len {
            let v_zero = (t.coe[t_len-1].clone() / u.coe[u_len-1].clone()).get_zero(); 
            return (Polynomial::new(&vec![v_zero]), t); 
        }
        if u_len == 1 {
            return (t.divide_by(u.coe[0].clone()), t.get_zero()); 
        }
        let mut coe = Vec::with_capacity(t_len - u_len + 1); 
        while t_len >= u_len {
            let temp = t.coe[t_len-1].clone() / u.coe[u_len-1].clone(); 
            coe.push(temp.clone()); 
            t = t - u.multiply_by(temp, t_len - u_len); 
            t.coe.pop(); 
            t_len = t.coe.len(); 
        }
        coe.reverse(); 
        return (Polynomial::new(&coe), t); 
    }
}

impl <T, U, V> DivLeft<Polynomial<U>> for Polynomial<T> where
    T: Clone + DivLeft<U, Output = V> + Sub<Output = T> + Zero + PartialEq, 
    U: Clone + Zero, 
    V: Clone + Mul<U, Output = T> + Zero {
    type Output = (Polynomial<V>, Polynomial<T>); 
    fn div_left(&self, other: &Polynomial<U>) -> Self::Output {
        let mut t = self.adjust(); 
        let u = other.adjust(); 
        let mut t_len = t.coe.len(); 
        let u_len = u.coe.len(); 
        if t_len < u_len {
            let v_zero = (t.coe[t_len-1].div_left(&u.coe[u_len-1])).get_zero(); 
            return (Polynomial::new(&vec![v_zero]), t); 
        }
        if u_len == 1 {
            return (t.divide_left_by(u.coe[0].clone()), t.get_zero()); 
        }
        let mut coe = Vec::with_capacity(t_len - u_len + 1); 
        while t_len >= u_len {
            let temp = t.coe[t_len-1].div_left(&u.coe[u_len-1]); 
            coe.push(temp.clone()); 
            t = t - u.multiply_left_by(temp, t_len - u_len); 
            t.coe.pop(); 
            t_len = t.coe.len(); 
        }
        coe.reverse(); 
        return (Polynomial::new(&coe), t); 
    }
}

impl <T, U, V> Rem<Polynomial<U>> for Polynomial<T> where
    T: Clone + Div<U, Output=V> + Sub<Output = T> + Zero + PartialEq, 
    U: Clone + Mul<V, Output=T> + Zero, 
    V: Clone + Zero {
    type Output = Polynomial<T>; 
    fn rem(self, other: Polynomial<U>) -> Self::Output {
        return (self / other).1.clone(); 
    }
}

impl <T: Clone + Add<Output = T> + Zero> Sum for Polynomial<T> {
    fn sum<U>(iter: U) -> Self where U: Iterator<Item = Self> {
        let mut iter = iter; 
        if let Some(mut result) = iter.next() {
            for item in iter {
                result = result.clone() + item.clone(); 
            }
            return result; 
        } else { panic!("iter can't be empty!"); }
    }
}