#[cfg(test)]
mod test;

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,
};
trait Constructible {}
impl<const N: usize> Constructible for [u8; N] {}
use crate::xp::{self, XP};

#[derive(Clone)]
pub struct AP<const N: usize = 8> {
    /// sign is either 1 or −1. size is the number of digits allocated and pointed
    /// to by digits; it can exceed ndigits, which is the number of digits in
    /// use. That is, an AP_T represents the number given by the XP_T in dig-
    /// its[0..ndigits-1]. AP_Ts are always normalized: Their most signifi-
    /// cant digit is nonzero, unless the value is zero. Thus, ndigits is often
    /// less than size. Figure 18.1 shows the layout of an 11-digit AP_T that is
    /// equal to 751,702,468,129 on a little endian computer with 32-bit words
    /// and 8-bit characters..
    sign: i8,
    ndigits: u32,
    /// ptr,len,cap
    digits: [u8; N],
}
impl<const N: usize> const Eq for AP<N> {}
impl<const N: usize> const PartialEq for AP<N> {
    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 N: usize> const Default for AP<N> {
    fn default() -> Self {
        Self { sign: 1, ndigits: 1, digits: [0; N] }
    }
}

impl<const N: usize> Debug for AP<N> {
    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<const N: usize> Display for AP<N> {
    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<const N: usize> AP<N> {
    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();
        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());
    }
    pub 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() -> Self {
        Self { sign: 1, ndigits: 1, digits: [0; N] }
    }
    const fn add<const N2: usize, const N3: usize>(
        z: &mut Self,
        x: &AP<N2>,
        y: &AP<N3>,
    ) {
        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<const N2: usize, const N3: usize>(
        z: &mut Self,
        x: &AP<N2>,
        y: &AP<N3>,
    ) {
        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<const N2: usize>(x: &Self, y: &AP<N2>) -> Ordering {
        if x.ndigits != y.ndigits {
            x.ndigits.cmp(&y.ndigits)
        } else {
            xp::cmp(x.ndigits, x.dgr(), y.dgr())
        }
    }
    const fn smsn<const N2: usize>(x: &Self, y: &AP<N2>) -> bool {
        // x.sign == y.sign
        (x.sign ^ y.sign) == 0
    }
    pub const fn divmod<const N2: usize>(
        x: &Self,
        y: &AP<N2>,
    ) -> (Self, AP<N2>)
    where
        [u8; N2 + N + 2]: Constructible,
    {
        assert!(!y.iszero());
        let mut q = Self::alloc();
        let mut r = AP::<N2>::alloc();
        xp::div(
            x.ndigits,
            q.dg(),
            x.dgr(),
            y.ndigits,
            y.dgr(),
            r.dg(),
            AP::<{ N2 + N + 2 }>::alloc().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
    }
    pub const fn mulmod<const N2: usize, const N3: usize>(
        x: &Self,
        y: &AP<N2>,
        p: &AP<N3>,
    ) -> AP<N3>
    where
        [(); N + N2]:,
        [(); N3 + { N + N2 } + 2]:,
    {
        let xy: AP<{ N + N2 }> = x * y;
        &xy % p
    }
    // pub const fn pow<const N2: usize>(&self, y: &AP<N2>) -> AP
    // where
    //     [(); { N2 - (1 / 8) }]:,
    // {
    //     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.shr::<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_<const N2: usize>(x: &Self, y: &AP<N2>) -> Ordering {
        if x.ndigits != y.ndigits {
            x.ndigits.cmp(&y.ndigits)
        } else {
            xp::cmp(x.ndigits, x.dgr(), y.dgr())
        }
    }
}

// impl const Drop for AP {
//     fn drop(&mut self) {}
// }

impl<const N: usize> const Neg for AP<N> {
    type Output = AP<N>;

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

impl<const N: usize, const N2: usize> const Mul<&AP<N2>> for &AP<N>
where
    [u8; N + N2]: Constructible,
{
    type Output = AP<{ N + N2 }>;

    fn mul(self, rhs: &AP<N2>) -> Self::Output {
        let mut z = Self::Output::alloc();
        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 N: usize, const N2: usize> const Add<&AP<N2>> for &AP<N>
where
    [u8; N.max(N2) + 1]: Constructible,
{
    type Output = AP<{ N.max(N2) + 1 }>;

    fn add(self, rhs: &AP<N2>) -> Self::Output {
        let mut z = AP::alloc();
        if AP::smsn(&self, &rhs) {
            AP::add(&mut z, &self, &rhs);
            z.sign = if z.iszero() { 1 } else { self.sign };
        } else if AP::cmp(self, rhs).is_gt() {
            AP::sub(&mut z, self, rhs);
            z.sign = if z.iszero() { 1 } else { self.sign };
        } else {
            AP::sub(&mut z, rhs, self);
            z.sign = if z.iszero() { 1 } else { -self.sign };
        }
        z
    }
}
impl<const N: usize, const N2: usize> const Sub<&AP<N2>> for &AP<N>
where
    [u8; N.max(N2) + 1]: Constructible,
{
    type Output = AP<{ N.max(N2) + 1 }>;

    fn sub(self, rhs: &AP<N2>) -> Self::Output {
        let mut z = AP::alloc();
        if !AP::smsn(self, rhs) {
            AP::add(&mut z, self, rhs);
            z.sign = if z.iszero() { 1 } else { self.sign };
        } else if AP::cmp(self, rhs).is_gt() {
            AP::sub(&mut z, self, rhs);
            z.sign = if z.iszero() { 1 } else { self.sign };
        } else {
            AP::sub(&mut z, rhs, self);
            z.sign = if z.iszero() { 1 } else { -self.sign };
        }
        z
    }
}
impl<const N: usize, const N2: usize> const Div<&AP<N2>> for &AP<N>
where
    [u8; N2 + N + 2]: Constructible,
{
    type Output = AP<N>;

    fn div(self, rhs: &AP<N2>) -> Self::Output {
        AP::divmod(self, rhs).0
    }
}

impl<const N: usize, const N2: usize> const Rem<&AP<N2>> for &AP<N>
where
    [u8; N2 + N + 2]: Constructible,
{
    type Output = AP<N2>;

    fn rem(self, rhs: &AP<N2>) -> Self::Output {
        AP::divmod(self, rhs).1
    }
}
impl<const N: usize> AP<N> {
    pub const fn shl<const S: usize>(
        &self,
    ) -> AP<{ N + (((S + 7) & !7) / 8) }> {
        let mut z = AP::alloc();
        xp::shl(z.sz(), z.dg(), self.ndigits, self.dgr(), S as _, 0);
        z.sign = self.sign;
        z.normalize(z.sz());
        z
    }
}

// impl<const N: usize> Shl<u32> for AP<N>
// where
//     [u8; 8 + N]: Constructible,
// {
//     type Output = AP<{ 8 + N }>;

//     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 N: usize> AP<N> {
    pub const fn shr<const S: usize>(&self) -> AP<{ N - (S / 8) }> {
        if S >= 8 * self.ndigits as usize {
            return AP::new(0);
        }

        let mut z = AP::alloc();
        let c =
            xp::shr(z.sz(), z.dg(), self.ndigits, self.dgr(), S as _, 0);

        z.sign = if z.iszero() { 1 } else { self.sign };
        z.normalize(z.sz());
        z
    }
}

// impl<const N: usize> Shr<u32> for AP<N> {
//     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 $what:expr => &$and:expr => $fname:ident => $($for:ident)+) => {
        $(impl<const N:usize> const $t<$for> for &AP<N>
            where [u8; $what]: Constructible,[u8; $and]: Constructible,
            {
            type Output = AP<$what>;
            fn $fname(self, other: $for) -> Self::Output {
                let other = AP::<8>::new(other as _);
                self.$fname(&other)
            }
        })+
        $(impl<const N:usize> const $t<$for> for AP<N>
            where [u8; $what]: Constructible,[u8; $and]: Constructible,
            {
            type Output = AP<$what>;
            fn $fname(self, other: $for) -> Self::Output {
                let other = AP::<8>::new(other as _);
                (&self).$fname(&other)
            }
        })+
        // $(impl const $t<$for> for AP {
        //     type Output = AP;
        //     fn $fname(self, other: $for) -> AP {
        //         let other = AP::new(other as _);
        //         (&self).$fname(&other)
        //     }
        // })+
    };
}
fni!(Add { N.max(8)+1 } => &0 => add => u64 u32 u16 u8 i128 i64 i32 i16 i8);
fni!(Mul { N + 8 } => &0 => mul => u64 u32 u16 u8 i128 i64 i32 i16 i8);
fni!(Div N => &{ 8 + N + 2} => div => u64 u32 u16 u8 i128 i64 i32 i16 i8);
fni!(Sub { N.max(8)+1} => &0 => sub => u64 u32 u16 u8 i128 i64 i32 i16 i8);
fni!(Rem { 8 } => &{ 8 + N + 2} => 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)
        }
    }
}