malachite-nz 0.13.0

// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.

use crate::integer::Integer;
use crate::integer_polynomial::arithmetic::scalar_mul::{
    integers_mul_scalar_assign, integers_mul_scalar_to_out,
};
use crate::natural::InnerNatural::Small;
use crate::natural::Natural;
use crate::platform::{SignedDoubleLimb, SignedLimb};
use alloc::vec::Vec;
use core::fmt::Debug;
use core::ops::{AddAssign, MulAssign, SubAssign};
use malachite_base::num::arithmetic::traits::{
    AddMulAssign, DivExactAssign, Pow, Square, SubMulAssign,
};
use malachite_base::num::basic::traits::{One, Zero};
use malachite_base::num::conversion::traits::ExactFrom;

crate_test_trait! {
// The coefficients of the polynomials that the multiplication kernels work with: `Integer`s, for
// `IntegerPolynomial`s, and `Natural`s, for `NaturalPolynomial`s. The kernels are FLINT's, which
// work with signed coefficients; a coefficient is read as a sign and an absolute value, and the
// results are built from them. For `Natural`s the sign is always non-negative, so after
// monomorphization the sign handling reduces to FLINT's paths for non-negative coefficients.
PolynomialCoefficient:
    Clone
    + Debug
    + Default
    + Zero
    + One
    + Eq
    + From<u64>
    + for<'a> AddAssign<&'a Self>
    + for<'a> SubAssign<&'a Self>
    + for<'a> MulAssign<&'a Self>
    + for<'a> DivExactAssign<&'a Self>
    + for<'a> AddMulAssign<&'a Self, &'a Self>
    + for<'a> SubMulAssign<&'a Self, &'a Self>
    + ExactFrom<SignedLimb>
    + ExactFrom<SignedDoubleLimb>
{
    // Whether the coefficient is zero. Comparing with `Self::ZERO` instead would build and drop a
    // temporary zero, which is measurably slower in the kernels' inner loops.
    fn is_zero(&self) -> bool;

    // Whether the coefficient is negative.
    fn is_negative(&self) -> bool;

    // The absolute value of the coefficient.
    fn unsigned_abs_ref(&self) -> &Natural;

    // The coefficient with the given sign (`true` for non-negative) and absolute value. A `Natural`
    // coefficient cannot be negative, so for `Natural`s `sign` must be `true` unless `abs` is zero.
    fn from_sign_and_abs(sign: bool, abs: Natural) -> Self;

    // The negative of a coefficient. A `Natural` coefficient cannot be negative, so for `Natural`s
    // the coefficient must be zero.
    fn negate(self) -> Self;

    // Doubles a coefficient in place.
    fn double_assign(&mut self);

    // The sum of two coefficients.
    fn add_ref(&self, other: &Self) -> Self;

    // The product of two coefficients.
    fn mul_ref(&self, other: &Self) -> Self;

    // The square of a coefficient.
    fn square_ref(&self) -> Self;

    // The coefficient raised to the power `e`.
    fn pow_ref(&self, e: u64) -> Self;

    // Sets `out` to the first `out.len()` elements of `xs`, each multiplied by `c`.
    fn vec_mul_scalar_to_out(out: &mut [Self], xs: &[Self], c: &Self);

    // Multiplies each element of `xs` by `c`.
    fn vec_mul_scalar_assign(xs: &mut [Self], c: &Self);
}}

impl PolynomialCoefficient for Integer {
    #[inline]
    fn is_zero(&self) -> bool {
        *self == 0u32
    }

    #[inline]
    fn is_negative(&self) -> bool {
        !self.sign
    }

    #[inline]
    fn unsigned_abs_ref(&self) -> &Natural {
        &self.abs
    }

    #[inline]
    fn from_sign_and_abs(sign: bool, abs: Natural) -> Self {
        Self::from_sign_and_abs(sign, abs)
    }

    #[inline]
    fn negate(self) -> Self {
        -self
    }

    #[inline]
    fn double_assign(&mut self) {
        *self <<= 1u32;
    }

    #[inline]
    fn add_ref(&self, other: &Self) -> Self {
        self + other
    }

    #[inline]
    fn mul_ref(&self, other: &Self) -> Self {
        self * other
    }

    #[inline]
    fn square_ref(&self) -> Self {
        self.square()
    }

    #[inline]
    fn pow_ref(&self, e: u64) -> Self {
        self.pow(e)
    }

    #[inline]
    fn vec_mul_scalar_to_out(out: &mut [Self], xs: &[Self], c: &Self) {
        integers_mul_scalar_to_out(out, xs, c);
    }

    #[inline]
    fn vec_mul_scalar_assign(xs: &mut [Self], c: &Self) {
        integers_mul_scalar_assign(xs, c);
    }
}

impl PolynomialCoefficient for Natural {
    #[inline]
    fn is_zero(&self) -> bool {
        *self == 0u32
    }

    #[inline]
    fn is_negative(&self) -> bool {
        false
    }

    #[inline]
    fn unsigned_abs_ref(&self) -> &Natural {
        self
    }

    #[inline]
    fn from_sign_and_abs(sign: bool, abs: Natural) -> Self {
        assert!(
            sign || abs == 0u32,
            "a Natural coefficient cannot be negative"
        );
        abs
    }

    #[inline]
    fn negate(self) -> Self {
        assert_eq!(self, 0u32, "a Natural coefficient cannot be negative");
        self
    }

    #[inline]
    fn double_assign(&mut self) {
        *self <<= 1u32;
    }

    #[inline]
    fn add_ref(&self, other: &Self) -> Self {
        self + other
    }

    #[inline]
    fn mul_ref(&self, other: &Self) -> Self {
        self * other
    }

    #[inline]
    fn square_ref(&self) -> Self {
        self.square()
    }

    #[inline]
    fn pow_ref(&self, e: u64) -> Self {
        self.pow(e)
    }

    fn vec_mul_scalar_to_out(out: &mut [Self], xs: &[Self], c: &Self) {
        let xs = &xs[..out.len()];
        match *c {
            Self(Small(0)) => out.fill(Self::ZERO),
            Self(Small(1)) => out.clone_from_slice(xs),
            _ => {
                for (o, x) in out.iter_mut().zip(xs) {
                    *o = x * c;
                }
            }
        }
    }

    fn vec_mul_scalar_assign(xs: &mut [Self], c: &Self) {
        match *c {
            Self(Small(0)) => xs.fill(Self::ZERO),
            Self(Small(1)) => {}
            _ => {
                for x in xs {
                    *x *= c;
                }
            }
        }
    }
}

// Removes the zeros at the end of `xs`, the coefficients of a polynomial, so that its last element,
// if any, is nonzero.
pub(crate) fn trim_coefficients<C: PolynomialCoefficient>(xs: &mut Vec<C>) {
    while xs.last().is_some_and(PolynomialCoefficient::is_zero) {
        xs.pop();
    }
}

// Keeps only the first `len` of `xs`, the coefficients of a polynomial without zeros at the end,
// and then trims the result.
pub(crate) fn truncate_coefficients<C: PolynomialCoefficient>(xs: &mut Vec<C>, len: u64) {
    if let Ok(len) = usize::try_from(len)
        && len < xs.len()
    {
        xs.truncate(len);
        trim_coefficients(xs);
    }
}