use fastrand;
use std::cmp::{max, Ordering};
use std::fmt;
use std::ops::{Add, Div, Index, IndexMut, Mul, Rem, Sub};

#[derive(Debug)]
pub struct Number {
    pub radix: u8,
    pub digits: Vec<u8>,
}

impl Clone for Number {
    fn clone(&self) -> Self {
        Number {
            radix: self.radix,
            digits: self.digits.clone(),
        }
    }
}

impl Index<usize> for Number {
    type Output = u8;

    fn index(&self, idx: usize) -> &Self::Output {
        &self.digits[idx]
    }
}

impl IndexMut<usize> for Number {
    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
        &mut self.digits[idx]
    }
}

impl Number {
    pub fn parse(snum: &str, radix: u8) -> Result<Number, String> {
        let snum = snum.as_bytes();
        let mut digits = Vec::new();
        for i in (0..snum.len()).rev() {
            match Number::parse_digit(snum[i]) {
                Some(digit) => {
                    if digit >= radix {
                        return Err("Аргумент не является числом".to_string());
                    } else {
                        digits.push(digit);
                    }
                }
                None => {
                    return Err("Аргумент не является числом".to_string());
                }
            }
        }
        return Ok(Number { radix, digits }.fix_leading_zeros());
    }

    pub fn from_digits(digits: &Vec<u8>, radix: u8) -> Result<Number, String> {
        for digit in digits {
            if *digit >= radix {
                return Err(
                    "Переданные цифры не соответствуют системе счисления"
                        .to_string(),
                );
            }
        }
        return Ok(Number {
            radix,
            digits: digits.clone(),
        }
        .fix_leading_zeros());
    }

    pub fn len(&self) -> usize {
        self.digits.len()
    }

    pub fn is_zero(&self) -> bool {
        for i in &self.digits {
            if *i != 0 {
                return false;
            }
        }
        return true;
    }

    pub fn random_below(&self) -> Number {
        loop {
            let num = Number::random_num(self.len(), self.radix);
            if num < self.clone() {
                return num;
            }
        }
    }

    pub fn random_num(size: usize, radix: u8) -> Number {
        let mut digits = Vec::new();
        for _ in 0..size - 1 {
            digits.push(fastrand::u8(..radix));
        }
        digits.push(fastrand::u8(1..radix));

        return Number::from_digits(&digits, radix).unwrap();
    }
}

impl Number {
    fn parse_digit(c: u8) -> Option<u8> {
        if c >= 'a' as u8 {
            Some(c - 'a' as u8 + 10_u8)
        } else if c >= '0' as u8 {
            Some(c - '0' as u8)
        } else {
            None
        }
    }

    fn fix_leading_zeros(mut self) -> Self {
        let mut leading = 0;
        for i in (1..self.digits.len()).rev() {
            if self.digits[i] == 0 {
                leading += 1;
            } else {
                break;
            }
        }
        for _ in 0..leading {
            self.digits.pop();
        }
        return self;
    }
}

impl From<u64> for Number {
    fn from(mut num: u64) -> Self {
        let radix = 10;
        let mut digits = Vec::new();
        while num != 0 {
            let digit = num % radix;
            num /= radix;
            digits.push(digit as u8);
        }
        if digits.len() == 0 {
            digits.push(0);
        }
        return Number {
            radix: radix as u8,
            digits,
        }
        .fix_leading_zeros();
    }
}

impl fmt::Display for Number {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for i in (0..self.digits.len()).rev() {
            let digit = if self.digits[i] > 9 {
                ('a' as u8 - 10 + self.digits[i]) as char
            } else {
                ('0' as u8 + self.digits[i]) as char
            };
            write!(f, "{}", digit)?;
        }

        if self.radix != 10 {
            write!(f, "_{}", self.radix)?;
        }
        return Ok(());
    }
}

impl Add for Number {
    type Output = Self;

    fn add(self, other: Self) -> Self::Output {
        let mut k = 0;
        let len = max(self.len(), other.len());
        let mut digits = Vec::new();
        for i in 0..len {
            let mut digit = 0;
            if i < self.len() {
                digit += self.digits[i] as usize;
            }
            if i < other.len() {
                digit += other.digits[i] as usize;
            }
            digit += k;
            let (div, rem) =
                (digit / self.radix as usize, digit % self.radix as usize);
            digit = rem;
            k = div;
            digits.push(digit as u8);
        }
        if k != 0 {
            digits.push(k as u8);
        }

        return Number::from_digits(&digits, self.radix).unwrap();
    }
}

impl Sub for Number {
    type Output = Self;

    fn sub(self, other: Self) -> Self::Output {
        let len = max(self.len(), other.len());
        let mut digits = Vec::new();
        let mut k = 0;
        for i in 0..len {
            let q1 = if i < self.len() {
                self.digits[i] as i64
            } else {
                0_i64
            };
            let q2 = if i < other.len() {
                other.digits[i] as i64
            } else {
                0_i64
            };
            let b = self.radix as i64;
            let res = q1 - q2 + k;
            let digit = (res + b) % b;
            k = if res < 0 { -1 } else { 0 };
            digits.push(digit as u8);
        }
        if k != 0 {
            digits.push(k as u8);
        }

        return Number::from_digits(&digits, self.radix).unwrap();
    }
}

impl Mul for Number {
    type Output = Self;

    fn mul(self, other: Self) -> Self::Output {
        let n = self.len();
        let m = other.len();
        let mut digits = vec![0; n + m];

        for j in 0..m {
            let vj = other.digits[j] as usize;
            if vj == 0 {
                digits[n + j] = 0;
            } else {
                let mut k = 0;
                for i in 0..n {
                    let ui = self.digits[i] as usize;
                    let t = ui * vj + digits[i + j] as usize + k;
                    digits[i + j] = (t % self.radix as usize) as u8;
                    k = t / self.radix as usize;
                }
                digits[n + j] = k as u8;
            }
        }

        return Number::from_digits(&digits, self.radix).unwrap();
    }
}

impl Number {
    pub fn div_rem(self, other: Self) -> Result<(Self, Self), String> {
        if other.is_zero() {
            return Err("Деление на 0 запрещено".to_string());
        }

        if self < other {
            return Ok((
                Number::from_digits(&vec![0], self.radix).unwrap(),
                self,
            ));
        }

        fn div_digit(a: &Vec<u8>, b: u8, radix: u8) -> (Vec<u8>, u8) {
            let mut q = Vec::new();
            let mut rem = 0;
            for j in (0..a.len()).rev() {
                let d = rem * radix as usize + a[j] as usize;
                q.push((d / b as usize) as u8);
                rem = d % b as usize;
            }
            q.reverse();
            return (q, rem as u8);
        }

        if other.len() == 1 {
            let (div, rem) =
                div_digit(&self.digits, other.digits[0], self.radix as u8);
            return Ok((
                Number::from_digits(&div, self.radix).unwrap(),
                Number::from_digits(&vec![rem], self.radix).unwrap(),
            ));
        }

        fn mul_digit(a: &Vec<u8>, b: u8, radix: u8) -> Vec<u8> {
            let mut c = vec![0; a.len() + 1];
            let mut carry = 0;
            for i in 0..a.len() {
                let dig = a[i] as usize * b as usize + carry;
                c[i] = (dig % radix as usize) as u8;
                carry = dig / radix as usize;
            }
            *c.last_mut().unwrap() = carry as u8;
            return c;
        }

        let n = other.len();
        let m = self.len() - n;
        let b = self.radix as i32;

        let v1 = other.digits[other.len() - 1];
        let d = self.radix / (v1 + 1);

        let mut u = mul_digit(&self.digits, d, self.radix as u8);
        let v = {
            let mut tmp = mul_digit(&other.digits, d, self.radix as u8);
            tmp.pop();
            tmp
        };
        let v_number = Number::from_digits(&v, self.radix).unwrap();

        let mut quo = Vec::new();
        for j in (0..=m).rev() {
            let uj = u[j + n] as i32;
            let v1 = v[v.len() - 1] as i32;
            let q = if uj == v1 {
                b - 1
            } else {
                let uj1 = u[j + n - 1] as i32;
                let uj2 = u[j + n - 2] as i32;
                let v2 = v[v.len() - 2] as i32;
                let mut qhat = (uj * b + uj1) / v1;
                while v2 * qhat > (uj * b + uj1 - qhat * v1) * b + uj2 {
                    qhat -= 1;
                }
                qhat
            };

            let u_sub = Vec::from(&u[j..=j + n]);
            let u_sub = Number::from_digits(&u_sub, self.radix).unwrap();
            let qv = Number::from_digits(
                &mul_digit(&v, q as u8, other.radix),
                other.radix,
            )
            .unwrap();

            let b_num = Number::from_digits(&vec![0, 1], self.radix).unwrap();
            let mut b_pow = Number::from_digits(&vec![1], self.radix).unwrap();
            for _ in 0..=n {
                b_pow = b_pow * b_num.clone();
            }

            let (p, q) = if u_sub >= qv {
                (u_sub - qv, q as u8)
            } else {
                (u_sub + b_pow - qv + v_number.clone(), (q - 1) as u8)
            };
            for i in 0..n + 1 {
                u[j + i] = if i < p.len() { p.digits[i] } else { 0 };
            }
            quo.push(q);
        }

        quo.reverse();
        let (rem_digits, _) = div_digit(&u, d, self.radix as u8);
        let div = Number::from_digits(&quo, self.radix).unwrap();
        let rem = Number::from_digits(&rem_digits, self.radix).unwrap();

        return Ok((div, rem));
    }
}

impl Div for Number {
    type Output = Self;

    fn div(self, other: Self) -> Self::Output {
        match self.div_rem(other) {
            Ok((div, _)) => div,
            Err(msg) => panic!("{msg}"),
        }
    }
}

impl Rem for Number {
    type Output = Self;

    fn rem(self, other: Self) -> Self::Output {
        match self.div_rem(other) {
            Ok((_, rem)) => rem,
            Err(msg) => panic!("{msg}"),
        }
    }
}

impl Number {
    pub fn pow_mod(&self, power: &Self, modulo: &Self) -> Result<Self, String> {
        if modulo.is_zero() {
            return Err("Модуль должен быть отличен от нуля".to_string());
        }
        let one: Number = Number::from_digits(&vec![1], self.radix).unwrap();
        if power.is_zero() {
            return Ok(one.clone() % modulo.clone());
        }
        let two: Number = Number::from_digits(&vec![2], self.radix).unwrap();
        let mut acc = one.clone();
        let mut p = power.clone();
        let mut base = self.clone();
        while !p.is_zero() {
            if p.clone() % two.clone() == one.clone() {
                acc = (acc * base.clone()) % modulo.clone();
            }
            p = p / two.clone();
            base = (base.clone() * base) % modulo.clone();
        }
        return Ok(acc);
    }
}

impl PartialEq for Number {
    fn eq(&self, other: &Self) -> bool {
        if self.len() != other.len() {
            return false;
        }

        for i in 0..self.len() {
            if self.digits[i] != other.digits[i] {
                return false;
            }
        }

        return true;
    }
}

impl Eq for Number {}

impl PartialOrd for Number {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Number {
    fn cmp(&self, other: &Self) -> Ordering {
        if self == other {
            return Ordering::Equal;
        }

        if self.len() < other.len() {
            return Ordering::Less;
        }

        if self.len() > other.len() {
            return Ordering::Greater;
        }

        for i in (0..self.len()).rev() {
            let l = self.digits[i];
            let r = other.digits[i];
            if l != r {
                return l.cmp(&r);
            }
        }
        return Ordering::Equal;
    }
}