use std::borrow::Cow;
use std::cmp::Ordering;
use std::fmt::{Debug, Display, Write};
use std::intrinsics::{const_deallocate, const_eval_select};
use std::marker::Destruct;
use std::mem::{ManuallyDrop as MD, forget, replace, transmute};
use std::ops::{
    Add, AddAssign, Deref, DerefMut, Div, DivAssign, Mul, MulAssign, Neg,
    Rem, Shl, Shr, Sub, SubAssign,
};
#[cfg(test)]
mod test;

use crate::xp::{self, XP};
#[repr(C)]
/// Arbitratry precision integer, usable in const
pub struct AP {
    // -1 | +1
    sign: i8,
    ndigits: u32,
    digits: MD<Storage>,
}
impl const Eq for AP {}
impl const PartialEq for AP {
    fn eq(&self, other: &Self) -> bool {
        self.sign == other.sign
            && self.ndigits == other.ndigits
            && self.dgr()[..self.ndigits as usize]
                == other.dgr()[..other.ndigits as usize]
    }
}

impl const Drop for Storage {
    fn drop(&mut self) {
        const fn drop_c(x: &mut MD<Vec<u8>>) {
            unsafe { const_deallocate(x.as_mut_ptr(), x.capacity(), 0) };
        }
        fn drop_r(x: &mut MD<Vec<u8>>) {
            unsafe { MD::drop(x) };
        }

        match self {
            Self::V(x) => {
                const_eval_select((x,), drop_c, drop_r);
            }
            _ => {}
        }
    }
}

impl const DerefMut for Storage {
    fn deref_mut(&mut self) -> &mut Self::Target {
        match self {
            Self::V(x) => x.as_mut_slice(),
            Self::Leaked(items) => {
                let mut v = Vec::new();
                let mut i = 0;
                while i < items.len() {
                    v.push(items[i]);
                }
                *self = Storage::V(MD::new(v));
                &mut *self
            }
        }
    }
}

impl const Deref for Storage {
    type Target = [u8];
    fn deref(&self) -> &Self::Target {
        match self {
            Self::V(x) => x.as_slice(),
            Self::Leaked(items) => *items,
        }
    }
}

impl const Clone for AP {
    fn clone(&self) -> Self {
        Self {
            sign: self.sign.clone(),
            ndigits: self.ndigits.clone(),
            digits: MD::new((&*self.digits).clone()),
        }
    }
}

#[derive(Debug)]
pub enum Storage {
    V(MD<Vec<u8>>),
    Leaked(&'static [u8]),
}
impl const Clone for Storage {
    fn clone(&self) -> Self {
        match self {
            Self::V(x) => {
                let mut i = 0;
                let mut v = Vec::with_capacity(x.len());
                while i < x.len() {
                    v.push(x.as_slice()[i]);
                    i += 1;
                }
                Self::V(MD::new(v))
            }
            Self::Leaked(x) => Self::Leaked(x),
        }
    }
}
impl const Default for AP {
    fn default() -> Self {
        Self {
            sign: 1,
            ndigits: 1,
            digits: MD::new(Storage::Leaked(&[0])),
        }
    }
}

impl Debug for AP {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.sign == -1 {
            f.write_char('-')?;
        }
        let mut x = Vec::with_capacity(1024);
        f.write_str(unsafe {
            std::str::from_utf8_unchecked(xp::to_str(
                &mut x,
                10,
                self.ndigits,
                self.clone().dg(),
            ))
        })
    }
}
impl Display for AP {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.sign == -1 {
            f.write_char('-')?;
        }
        let mut x = Vec::with_capacity(1024);
        f.write_str(unsafe {
            std::str::from_utf8_unchecked(xp::to_str(
                &mut x,
                10,
                self.ndigits,
                self.clone().dg(),
            ))
        })
    }
}

impl AP {
    const fn sz(&self) -> u32 {
        self.digits.len() as _
    }
    const fn dg(&mut self) -> &mut XP {
        &mut self.digits
    }
    pub const fn new(n: i128) -> Self {
        let mut x = Self::alloc(8);
        x.set(n);
        x
    }
    const fn dgr(&self) -> &XP {
        &self.digits
    }
    pub const fn to_int(&self) -> i128 {
        let u =
            xp::to_int(self.ndigits, self.dgr()) % (i128::MAX as u128 + 1);
        if self.sign == -1 { -(u as i128) } else { u as i128 }
    }
    pub const fn set(&mut self, n: i128) {
        if (n == i128::MIN) {
            xp::from_int(self.sz(), self.dg(), (i128::MAX as u128 + 1));
        } else if (n < 0) {
            xp::from_int(self.sz(), self.dg(), (-n) as _);
        } else {
            xp::from_int(self.sz(), self.dg(), (n) as _);
            self.sign = if n < 0 { -1 } else { 1 };
        }
        self.sign = if n < 0 { -1 } else { 1 };
        self.normalize(self.sz());
    }
    const fn normalize(&mut self, n: u32) {
        self.ndigits = xp::len(n, self.dgr());
    }
    const fn iszero(&self) -> bool {
        self.ndigits == 1 && self.dgr()[0] == 0
    }
    pub const fn alloc(size: u32) -> Self {
        assert!(size > 0);
        let mut v = Vec::with_capacity(size as _);
        let mut i = 0;
        while i < size {
            v.push(0);
            i += 1;
        }

        Self {
            sign: 1,
            ndigits: 1,
            digits: MD::new(Storage::V(MD::new(v))),
        }
    }
    const fn add(z: &mut Self, x: &Self, y: &Self) {
        let mut n = y.ndigits;
        if x.ndigits < n {
            Self::add(z, y, x)
        } else if (x.ndigits > n) {
            let carry = xp::add(n, z.dg(), x.dgr(), y.dgr(), false);
            let sz = z.sz() as usize;
            z.dg()[sz - 1] = unsafe {
                xp::sum(
                    x.ndigits - n,
                    &mut z.dg()[n as usize..],
                    &x.dgr()[n as usize..],
                    carry as _,
                )
            };
        } else {
            z.dg()[n as usize] =
                xp::add(n, z.dg(), x.dgr(), y.dgr(), false) as _;
        }
        z.normalize(z.sz());
    }
    const fn sub(z: &mut Self, x: &Self, y: &Self) {
        let mut n = y.ndigits;
        // int borrow, n = y->ndigits;
        let mut borrow = xp::sub(n, z.dg(), x.dgr(), y.dgr(), false) as u8;
        if (x.ndigits > n) {
            borrow = xp::diff(
                x.ndigits - n,
                &mut z.dg()[n as usize..],
                &x.dgr()[n as usize..],
                borrow,
            );
        }
        assert!(borrow == 0);
        z.normalize(z.sz());
        // assert(borrow == 0);
        // return normalize(z, z->size);
    }
    const fn cmp(x: &Self, y: &Self) -> Ordering {
        if x.ndigits != y.ndigits {
            x.ndigits.cmp(&y.ndigits)
        } else {
            xp::cmp(x.ndigits, x.dgr(), y.dgr())
        }
    }
    const fn smsn(x: &Self, y: &Self) -> bool {
        (x.sign ^ y.sign) == 0
    }
    pub const fn divmod(x: &Self, y: &Self) -> (AP, AP) {
        assert!(!y.iszero());
        let mut q = AP::alloc(x.ndigits);
        let mut r = AP::alloc(y.ndigits);
        xp::div(
            x.ndigits,
            q.dg(),
            x.dgr(),
            y.ndigits,
            y.dgr(),
            r.dg(),
            AP::alloc(x.ndigits + y.ndigits + 2).dg(),
        );
        q.normalize(q.sz());
        r.normalize(r.sz());
        q.sign = if q.iszero() || AP::smsn(x, y) { 1 } else { -1 };
        if !AP::smsn(x, y) && !r.iszero() {
            let carry = unsafe {
                xp::sum_p(q.sz(), q.dg().as_mut_ptr(), q.dgr().as_ptr(), 1)
            };
            assert!(carry == 0);
            q.normalize(q.sz());
            assert!(unsafe {
                !xp::subp(
                    r.sz(),
                    r.dg().as_mut_ptr(),
                    y.dgr().as_ptr(),
                    r.dgr().as_ptr(),
                    false,
                )
            });
            r.normalize(r.sz());
        };
        (q, r)
    }
    const fn isone(&self) -> bool {
        self.ndigits == 1 && self.dgr()[0] == 1
    }
    pub const fn is_even(&self) -> bool {
        (self.dgr()[0] & 1) == 0
    }
    const fn mulmod(x: &Self, y: &Self, p: &Self) -> AP {
        let xy = x * y;
        &xy % p
    }
    pub const fn pow(&self, y: &Self) -> AP {
        assert!(y.sign == 1);
        if self.iszero() {
            return AP::new(0);
        }
        if y.iszero() {
            return AP::new(1);
        }
        if self.isone() {
            return AP::new(if y.is_even() { 1 } else { self.sign as _ });
        }
        if y.isone() {
            return self + 0;
        }
        let y2 = y >> 1;
        let t = AP::pow(self, &y2);
        let mut z = &t * &t;
        if !y.is_even() {
            z = self * &z;
        }
        z
    }
    pub const fn pow_mod(&self, y: &Self, modulo: &Self) -> Self {
        assert!(y.sign == 1);
        assert!(modulo.sign == 1 && !modulo.iszero() && !modulo.isone());
        if self.iszero() {
            return AP::new(0);
        }
        if y.iszero() {
            return AP::new(1);
        }
        if self.isone() {
            return AP::new(if y.is_even() { 1 } else { self.sign as _ });
        }
        if y.isone() {
            return self + 0;
        }
        let y2 = y >> 1;
        let t = AP::pow_mod(self, &y2, modulo);
        let mut z = AP::mulmod(&t, &t, modulo);
        if !y.is_even() {
            z = AP::mulmod(&(self % modulo), &z, modulo);
        }
        z
    }
    const fn cmp_(x: &Self, y: &Self) -> Ordering {
        if x.ndigits != y.ndigits {
            x.ndigits.cmp(&y.ndigits)
        } else {
            xp::cmp(x.ndigits, x.dgr(), y.dgr())
        }
    }
    /// call before storing.
    pub const fn globalize(mut self) -> Self {
        match &mut *self.digits {
            Storage::V(x) =>
                self.digits = MD::new(Storage::Leaked(
                    unsafe { MD::take(x) }.const_make_global(),
                )),
            _ => {}
        };
        self
    }
}

impl const Drop for AP {
    fn drop(&mut self) {
        unsafe { MD::drop(&mut self.digits) };
    }
}

impl const Neg for AP {
    type Output = AP;

    fn neg(mut self) -> Self::Output {
        self.sign = if self.iszero() { 1 } else { -self.sign };
        self
    }
}

impl const Mul for &AP {
    type Output = AP;

    fn mul(self, rhs: Self) -> Self::Output {
        let mut z = AP::alloc(self.ndigits + rhs.ndigits);
        xp::mul(z.dg(), self.ndigits, self.dgr(), rhs.ndigits, rhs.dgr());
        z.normalize(z.sz());
        z.sign = if z.iszero() || AP::smsn(self, rhs) { 1 } else { -1 };
        z
    }
}
impl const MulAssign<&AP> for AP {
    fn mul_assign(&mut self, rhs: &Self) {
        *self = &*self * rhs;
    }
}
impl const Add for &AP {
    type Output = AP;

    fn add(self, rhs: Self) -> Self::Output {
        let mut z;
        if AP::smsn(&self, &rhs) {
            z = AP::alloc(self.ndigits.max(rhs.ndigits) + 1);
            AP::add(&mut z, &self, &rhs);
            z.sign = if z.iszero() { 1 } else { self.sign };
        } else if AP::cmp(self, rhs).is_gt() {
            z = AP::alloc(self.ndigits);
            AP::sub(&mut z, self, rhs);
            z.sign = if z.iszero() { 1 } else { self.sign };
        } else {
            // lesser ?
            z = AP::alloc(rhs.ndigits);
            AP::sub(&mut z, rhs, self);
            z.sign = if z.iszero() { 1 } else { -self.sign };
        }
        z
    }
}
impl const Sub for &AP {
    type Output = AP;

    fn sub(self, rhs: Self) -> Self::Output {
        let mut z;
        if !AP::smsn(self, rhs) {
            z = AP::alloc(self.ndigits.max(rhs.ndigits) + 1);

            AP::add(&mut z, self, rhs);
            z.sign = if z.iszero() { 1 } else { self.sign };
        } else if AP::cmp(self, rhs).is_gt() {
            z = AP::alloc(self.ndigits);
            AP::sub(&mut z, self, rhs);
            z.sign = if z.iszero() { 1 } else { self.sign };
        } else {
            z = AP::alloc(rhs.ndigits);
            AP::sub(&mut z, rhs, self);
            z.sign = if z.iszero() { 1 } else { -self.sign };
        }
        z
    }
}
impl const SubAssign<&AP> for AP {
    fn sub_assign(&mut self, rhs: &AP) {
        *self = &*self - rhs;
    }
}
impl const AddAssign<&AP> for AP {
    fn add_assign(&mut self, rhs: &AP) {
        *self = &*self + rhs;
    }
}
impl const Div for &AP {
    type Output = AP;

    fn div(self, rhs: Self) -> Self::Output {
        AP::divmod(self, rhs).0
    }
}
impl const DivAssign<&AP> for AP {
    fn div_assign(&mut self, rhs: &AP) {
        *self = &*self / rhs;
    }
}
impl const Rem for &AP {
    type Output = AP;

    fn rem(self, rhs: Self) -> Self::Output {
        AP::divmod(self, rhs).1
    }
}

impl const Shl<u32> for &AP {
    type Output = AP;

    fn shl(self, s: u32) -> Self::Output {
        let mut z = AP::alloc(self.ndigits + ((s + 7) & !7) / 8);
        xp::shl(z.sz(), z.dg(), self.ndigits, self.dgr(), s, 0);
        z.sign = self.sign;
        z.normalize(z.sz());
        z
    }
}
impl const Shr<u32> for &AP {
    type Output = AP;

    /// this is a truncating, not flooring, shr.
    fn shr(self, s: u32) -> Self::Output {
        if s >= 8 * self.ndigits {
            return AP::new(0);
        }

        let mut z = AP::alloc(self.ndigits - (s / 8));
        let c = xp::shr(z.sz(), z.dg(), self.ndigits, self.dgr(), s, 0);

        z.sign = if z.iszero() { 1 } else { self.sign };
        z.normalize(z.sz());
        z
    }
}
macro_rules! fni {
    ($t:ident, $fname:ident => $($for:ident)+) => {
        impl const $t<&AP> for AP {
            type Output = AP;
            fn $fname(self, other: &AP) -> AP {
                 <&AP as $t<&AP>>::$fname(&self, other)
            }
        }
        impl const $t<AP> for AP {
            type Output = AP;
            fn $fname(self, other: AP) -> AP {
                 <&AP as $t<&AP>>::$fname(&self, &other)
            }
        }

        impl const $t<AP> for &AP {
            type Output = AP;
            fn $fname(self, other: AP) -> AP {
                <&AP as $t<&AP>>::$fname(self, &other)
            }
        }

        $(impl const $t<$for> for &AP {
            type Output = AP;
            fn $fname(self, other: $for) -> AP {
                let other = AP::new(other as _);
                 <&AP as $t<&AP>>::$fname(self, &other)
            }
        })+
        $(impl const $t<$for> for AP {
            type Output = AP;
            fn $fname(self, other: $for) -> AP {
                let other = AP::new(other as _);
                <&AP as $t<&AP>>::$fname(&self, &other)
            }
        })+
    };
}
fni!(Add, add => u64 u32 u16 u8 i128 i64 i32 i16 i8);
fni!(Mul, mul => u64 u32 u16 u8 i128 i64 i32 i16 i8);
fni!(Div, div => u64 u32 u16 u8 i128 i64 i32 i16 i8);
fni!(Sub, sub => u64 u32 u16 u8 i128 i64 i32 i16 i8);
fni!(Rem, rem => u64 u32 u16 u8 i128 i64 i32 i16 i8);

impl const PartialOrd for AP {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl const Ord for AP {
    fn cmp(&self, other: &Self) -> Ordering {
        if !AP::smsn(self, other) {
            unsafe { transmute(self.sign) }
        } else if self.sign == 1 {
            AP::cmp_(self, other)
        } else {
            AP::cmp_(other, self)
        }
    }
}