//! Owned signed-magnitude BigInt arithmetic helpers.

use std::cmp::Ordering;

use super::{Term, boxed::BigInt};

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct BigIntValue {
    negative: bool,
    limbs: Vec<u64>,
}

impl BigIntValue {
    #[must_use]
    pub fn new(negative: bool, limbs: Vec<u64>) -> Self {
        let mut value = Self { negative, limbs };
        value.normalize();
        value
    }

    #[must_use]
    pub fn zero() -> Self {
        Self {
            negative: false,
            limbs: Vec::new(),
        }
    }

    #[must_use]
    pub fn from_i64(value: i64) -> Self {
        let magnitude = value.unsigned_abs();
        if magnitude == 0 {
            Self::zero()
        } else {
            Self {
                negative: value.is_negative(),
                limbs: vec![magnitude],
            }
        }
    }

    #[must_use]
    pub fn from_bigint(bigint: BigInt) -> Self {
        Self::new(bigint.is_negative(), bigint.limbs().to_vec())
    }

    #[must_use]
    pub fn from_term(term: Term) -> Option<Self> {
        if let Some(value) = term.as_small_int() {
            Some(Self::from_i64(value))
        } else {
            BigInt::new(term).map(Self::from_bigint)
        }
    }

    #[must_use]
    pub fn is_zero(&self) -> bool {
        self.limbs.is_empty()
    }

    #[must_use]
    pub fn is_negative(&self) -> bool {
        self.negative && !self.is_zero()
    }

    #[must_use]
    pub fn limbs(&self) -> &[u64] {
        &self.limbs
    }

    #[must_use]
    pub fn to_small_i64(&self) -> Option<i64> {
        match self.limbs.as_slice() {
            [] => Some(0),
            [limb] if self.is_negative() => {
                let limit = (i64::MAX as u64).wrapping_add(1);
                if *limb == limit {
                    Some(i64::MIN)
                } else {
                    i64::try_from(*limb).ok().map(|value| -value)
                }
            }
            [limb] => i64::try_from(*limb).ok(),
            _ => None,
        }
    }

    pub fn normalize(&mut self) {
        normalize_limbs(&mut self.limbs);
        if self.limbs.is_empty() {
            self.negative = false;
        }
    }

    #[must_use]
    pub fn add(&self, other: &Self) -> Self {
        match (self.is_negative(), other.is_negative()) {
            (true, true) => Self::new(true, add_abs(&self.limbs, &other.limbs)),
            (false, false) => Self::new(false, add_abs(&self.limbs, &other.limbs)),
            (false, true) => sub_signed(&self.limbs, &other.limbs),
            (true, false) => sub_signed(&other.limbs, &self.limbs),
        }
    }

    #[must_use]
    pub fn sub(&self, other: &Self) -> Self {
        self.add(&Self::new(!other.is_negative(), other.limbs.clone()))
    }

    #[must_use]
    pub fn mul(&self, other: &Self) -> Self {
        Self::new(
            self.is_negative() ^ other.is_negative(),
            mul_abs(&self.limbs, &other.limbs),
        )
    }

    #[must_use]
    pub fn divmod(&self, other: &Self) -> Option<(Self, Self)> {
        if other.is_zero() {
            return None;
        }
        let (quotient, remainder) = divmod_abs(&self.limbs, &other.limbs);
        Some((
            Self::new(self.is_negative() ^ other.is_negative(), quotient),
            Self::new(self.is_negative(), remainder),
        ))
    }

    #[must_use]
    pub fn negate(&self) -> Self {
        Self::new(!self.is_negative(), self.limbs.clone())
    }

    #[must_use]
    pub fn abs(&self) -> Self {
        Self::new(false, self.limbs.clone())
    }

    #[must_use]
    pub fn shl_bits(&self, shift: usize) -> Self {
        Self::new(self.is_negative(), shl_abs(&self.limbs, shift))
    }

    #[must_use]
    pub fn bit_length(&self) -> usize {
        bit_length_abs(&self.limbs)
    }
}

#[must_use]
pub fn cmp_abs(left: &[u64], right: &[u64]) -> Ordering {
    let left = normalized(left);
    let right = normalized(right);
    match left.len().cmp(&right.len()) {
        Ordering::Equal => left.iter().rev().cmp(right.iter().rev()),
        order => order,
    }
}

#[must_use]
pub fn add_abs(left: &[u64], right: &[u64]) -> Vec<u64> {
    let len = left.len().max(right.len());
    let mut out = Vec::with_capacity(len + 1);
    let mut carry = 0_u128;
    for index in 0..len {
        let sum = u128::from(*left.get(index).unwrap_or(&0))
            + u128::from(*right.get(index).unwrap_or(&0))
            + carry;
        out.push(sum as u64);
        carry = sum >> 64;
    }
    if carry != 0 {
        out.push(carry as u64);
    }
    normalize_limbs(&mut out);
    out
}

#[must_use]
pub fn sub_abs(left: &[u64], right: &[u64]) -> Vec<u64> {
    debug_assert!(cmp_abs(left, right) != Ordering::Less);
    let mut out = Vec::with_capacity(left.len());
    let mut borrow = 0_u128;
    for (index, left_limb) in left.iter().enumerate() {
        let right_limb = u128::from(*right.get(index).unwrap_or(&0));
        let subtrahend = right_limb + borrow;
        let minuend = u128::from(*left_limb);
        if minuend >= subtrahend {
            out.push((minuend - subtrahend) as u64);
            borrow = 0;
        } else {
            out.push(((1_u128 << 64) + minuend - subtrahend) as u64);
            borrow = 1;
        }
    }
    normalize_limbs(&mut out);
    out
}

#[must_use]
pub fn mul_abs(left: &[u64], right: &[u64]) -> Vec<u64> {
    if normalized(left).is_empty() || normalized(right).is_empty() {
        return Vec::new();
    }
    let mut out = vec![0_u64; left.len() + right.len()];
    for (i, left_limb) in left.iter().enumerate() {
        let mut carry = 0_u128;
        for (j, right_limb) in right.iter().enumerate() {
            let index = i + j;
            let product =
                u128::from(*left_limb) * u128::from(*right_limb) + u128::from(out[index]) + carry;
            out[index] = product as u64;
            carry = product >> 64;
        }
        let mut index = i + right.len();
        while carry != 0 {
            let sum = u128::from(out[index]) + carry;
            out[index] = sum as u64;
            carry = sum >> 64;
            index += 1;
        }
    }
    normalize_limbs(&mut out);
    out
}

#[must_use]
pub fn divmod_abs(left: &[u64], right: &[u64]) -> (Vec<u64>, Vec<u64>) {
    let left = normalized(left);
    let right = normalized(right);
    if right.is_empty() {
        return (Vec::new(), Vec::new());
    }
    if cmp_abs(left, right) == Ordering::Less {
        return (Vec::new(), left.to_vec());
    }
    let bit_len = bit_length_abs(left);
    let mut quotient = Vec::new();
    let mut remainder = Vec::new();
    for bit in (0..bit_len).rev() {
        remainder = shl_abs(&remainder, 1);
        if test_bit(left, bit) {
            set_bit(&mut remainder, 0);
        }
        if cmp_abs(&remainder, right) != Ordering::Less {
            remainder = sub_abs(&remainder, right);
            set_bit(&mut quotient, bit);
        }
    }
    normalize_limbs(&mut quotient);
    normalize_limbs(&mut remainder);
    (quotient, remainder)
}

#[must_use]
pub fn normalized(limbs: &[u64]) -> &[u64] {
    let len = limbs
        .iter()
        .rposition(|limb| *limb != 0)
        .map_or(0, |index| index + 1);
    &limbs[..len]
}

fn sub_signed(positive: &[u64], negative_magnitude: &[u64]) -> BigIntValue {
    match cmp_abs(positive, negative_magnitude) {
        Ordering::Greater => BigIntValue::new(false, sub_abs(positive, negative_magnitude)),
        Ordering::Equal => BigIntValue::zero(),
        Ordering::Less => BigIntValue::new(true, sub_abs(negative_magnitude, positive)),
    }
}

fn normalize_limbs(limbs: &mut Vec<u64>) {
    if let Some(index) = limbs.iter().rposition(|limb| *limb != 0) {
        limbs.truncate(index + 1);
    } else {
        limbs.clear();
    }
}

fn bit_length_abs(limbs: &[u64]) -> usize {
    let limbs = normalized(limbs);
    match limbs.last() {
        Some(last) => (limbs.len() - 1) * 64 + (64 - last.leading_zeros() as usize),
        None => 0,
    }
}

fn test_bit(limbs: &[u64], bit: usize) -> bool {
    let limb = bit / 64;
    let offset = bit % 64;
    limbs
        .get(limb)
        .is_some_and(|value| ((value >> offset) & 1) == 1)
}

pub fn set_bit(limbs: &mut Vec<u64>, bit: usize) {
    let limb = bit / 64;
    let offset = bit % 64;
    if limbs.len() <= limb {
        limbs.resize(limb + 1, 0);
    }
    limbs[limb] |= 1_u64 << offset;
}

#[must_use]
pub fn shl_abs(limbs: &[u64], shift: usize) -> Vec<u64> {
    let limbs = normalized(limbs);
    if limbs.is_empty() {
        return Vec::new();
    }
    let limb_shift = shift / 64;
    let bit_shift = shift % 64;
    let mut out = vec![0_u64; limb_shift + limbs.len() + 1];
    let mut carry = 0_u64;
    for (index, limb) in limbs.iter().enumerate() {
        out[index + limb_shift] = (*limb << bit_shift) | carry;
        carry = if bit_shift == 0 {
            0
        } else {
            *limb >> (64 - bit_shift)
        };
    }
    out[limb_shift + limbs.len()] = carry;
    normalize_limbs(&mut out);
    out
}

#[must_use]
pub fn low_bits_mask(bits: usize) -> Vec<u64> {
    if bits == 0 {
        return Vec::new();
    }
    let limbs = bits.div_ceil(64);
    let mut out = vec![u64::MAX; limbs];
    let used = bits % 64;
    if used != 0
        && let Some(last) = out.last_mut()
    {
        *last = (1_u64 << used) - 1;
    }
    out
}

#[must_use]
pub fn bitand_abs(left: &[u64], right: &[u64]) -> Vec<u64> {
    let len = left.len().min(right.len());
    let mut out = Vec::with_capacity(len);
    for index in 0..len {
        out.push(left[index] & right[index]);
    }
    normalize_limbs(&mut out);
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn add_carries_across_limbs() {
        assert_eq!(add_abs(&[u64::MAX], &[1]), vec![0, 1]);
    }

    #[test]
    fn subtract_borrows_across_limbs() {
        assert_eq!(sub_abs(&[0, 1], &[1]), vec![u64::MAX]);
    }

    #[test]
    fn multiply_schoolbook_multiple_limbs() {
        assert_eq!(
            mul_abs(&[u64::MAX, u64::MAX], &[2]),
            vec![u64::MAX - 1, u64::MAX, 1]
        );
    }

    #[test]
    fn divmod_returns_quotient_and_remainder() {
        let dividend = BigIntValue::new(false, vec![0, 10]);
        let divisor = BigIntValue::from_i64(3);
        let Some((quotient, remainder)) = dividend.divmod(&divisor) else {
            panic!("non-zero divisor should divide");
        };
        assert_eq!(quotient.mul(&divisor).add(&remainder), dividend);
        assert_eq!(remainder, BigIntValue::from_i64(1));
    }

    #[test]
    fn sign_and_zero_normalization_are_canonical() {
        assert_eq!(
            BigIntValue::from_i64(-7).mul(&BigIntValue::from_i64(-6)),
            BigIntValue::from_i64(42)
        );
        assert_eq!(BigIntValue::new(true, vec![0, 0]), BigIntValue::zero());
    }

    #[test]
    fn negate_flips_sign_and_keeps_zero_canonical() {
        let value = BigIntValue::new(false, vec![0, 1]);
        let negated = value.negate();
        assert!(negated.is_negative());
        assert_eq!(negated.limbs(), value.limbs());
        assert_eq!(negated.negate(), value);
        assert_eq!(BigIntValue::zero().negate(), BigIntValue::zero());
        assert_eq!(BigIntValue::from_i64(-5).negate(), BigIntValue::from_i64(5));
    }

    #[test]
    fn abs_clears_sign_for_any_magnitude() {
        let negative = BigIntValue::new(true, vec![7, 9]);
        let positive = BigIntValue::new(false, vec![7, 9]);
        assert_eq!(negative.abs(), positive);
        assert_eq!(positive.abs(), positive);
        assert_eq!(BigIntValue::from_i64(i64::MIN).abs().limbs(), &[1 << 63]);
    }
}
