malachite_nz/integer_polynomial/comparison/eq_truncated.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::integer::Integer;
10use crate::integer_polynomial::IntegerPolynomial;
11use crate::natural_polynomial::NaturalPolynomial;
12use malachite_base::num::basic::unsigneds::PrimitiveUnsigned;
13use malachite_base::polynomial::{EqTruncated, slices_eq_truncated};
14use malachite_base::unsigned_polynomial::UnsignedPolynomial;
15
16// Whether a coefficient is zero. This is a function rather than a closure because inside the impls
17// below, a `where` bound on `Integer: PartialEq<T>` would capture a comparison with a literal.
18fn integer_is_zero(x: &Integer) -> bool {
19 *x == 0u32
20}
21
22impl EqTruncated for IntegerPolynomial {
23 /// Determines whether an [`IntegerPolynomial`] and another agree below $x^{\mathrm{len}}$: that
24 /// is, whether they have the same coefficient of $x^i$ for every $i$ less than `len`.
25 ///
26 /// Any two polynomials agree below $x^0$, and once `len` is at least both of their lengths,
27 /// they agree exactly when they are equal.
28 ///
29 /// # Worst-case complexity
30 /// $T(n) = O(n)$
31 ///
32 /// $M(n) = O(1)$
33 ///
34 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
35 /// coefficients below $x^{\mathrm{len}}$.
36 ///
37 /// # Examples
38 /// See [here](super::eq_truncated#eq_truncated).
39 ///
40 /// This is equivalent to `fmpz_poly_equal_trunc` from `fmpz_poly/equal_trunc.c`, FLINT 3.6.0.
41 #[inline]
42 fn eq_truncated(&self, other: &Self, len: u64) -> bool {
43 slices_eq_truncated(
44 &self.coefficients,
45 &other.coefficients,
46 len,
47 integer_is_zero,
48 |y| *y == 0u32,
49 |x, y| x == y,
50 )
51 }
52}
53
54impl<T: PrimitiveUnsigned> EqTruncated<UnsignedPolynomial<T>> for IntegerPolynomial
55where
56 Integer: PartialEq<T>,
57{
58 /// Determines whether an [`IntegerPolynomial`] and an [`UnsignedPolynomial`] agree below
59 /// $x^{\mathrm{len}}$: that is, whether they have the same coefficient of $x^i$ for every $i$
60 /// less than `len`.
61 ///
62 /// Any two polynomials agree below $x^0$, and once `len` is at least both of their lengths,
63 /// they agree exactly when they are equal.
64 ///
65 /// # Worst-case complexity
66 /// $T(n) = O(n)$
67 ///
68 /// $M(n) = O(1)$
69 ///
70 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
71 /// coefficients below $x^{\mathrm{len}}$.
72 ///
73 /// # Examples
74 /// See [here](super::eq_truncated#eq_truncated).
75 #[inline]
76 fn eq_truncated(&self, other: &UnsignedPolynomial<T>, len: u64) -> bool {
77 slices_eq_truncated(
78 &self.coefficients,
79 other.coefficients_asc(),
80 len,
81 integer_is_zero,
82 |&y| y == T::ZERO,
83 |x, y| x == y,
84 )
85 }
86}
87
88impl<T: PrimitiveUnsigned> EqTruncated<IntegerPolynomial> for UnsignedPolynomial<T>
89where
90 Integer: PartialEq<T>,
91{
92 /// Determines whether an [`UnsignedPolynomial`] and an [`IntegerPolynomial`] agree below
93 /// $x^{\mathrm{len}}$: that is, whether they have the same coefficient of $x^i$ for every $i$
94 /// less than `len`.
95 ///
96 /// Any two polynomials agree below $x^0$, and once `len` is at least both of their lengths,
97 /// they agree exactly when they are equal.
98 ///
99 /// # Worst-case complexity
100 /// $T(n) = O(n)$
101 ///
102 /// $M(n) = O(1)$
103 ///
104 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
105 /// coefficients below $x^{\mathrm{len}}$.
106 ///
107 /// # Examples
108 /// See [here](super::eq_truncated#eq_truncated).
109 #[inline]
110 fn eq_truncated(&self, other: &IntegerPolynomial, len: u64) -> bool {
111 other.eq_truncated(self, len)
112 }
113}
114
115impl EqTruncated<NaturalPolynomial> for IntegerPolynomial {
116 /// Determines whether an [`IntegerPolynomial`] and a [`NaturalPolynomial`] agree below
117 /// $x^{\mathrm{len}}$: that is, whether they have the same coefficient of $x^i$ for every $i$
118 /// less than `len`.
119 ///
120 /// Any two polynomials agree below $x^0$, and once `len` is at least both of their lengths,
121 /// they agree exactly when they are equal.
122 ///
123 /// # Worst-case complexity
124 /// $T(n) = O(n)$
125 ///
126 /// $M(n) = O(1)$
127 ///
128 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
129 /// coefficients below $x^{\mathrm{len}}$.
130 ///
131 /// # Examples
132 /// See [here](super::eq_truncated#eq_truncated).
133 #[inline]
134 fn eq_truncated(&self, other: &NaturalPolynomial, len: u64) -> bool {
135 slices_eq_truncated(
136 &self.coefficients,
137 other.coefficients_asc(),
138 len,
139 integer_is_zero,
140 |y| *y == 0u32,
141 |x, y| x == y,
142 )
143 }
144}
145
146impl EqTruncated<IntegerPolynomial> for NaturalPolynomial {
147 /// Determines whether a [`NaturalPolynomial`] and an [`IntegerPolynomial`] agree below
148 /// $x^{\mathrm{len}}$: that is, whether they have the same coefficient of $x^i$ for every $i$
149 /// less than `len`.
150 ///
151 /// Any two polynomials agree below $x^0$, and once `len` is at least both of their lengths,
152 /// they agree exactly when they are equal.
153 ///
154 /// # Worst-case complexity
155 /// $T(n) = O(n)$
156 ///
157 /// $M(n) = O(1)$
158 ///
159 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
160 /// coefficients below $x^{\mathrm{len}}$.
161 ///
162 /// # Examples
163 /// See [here](super::eq_truncated#eq_truncated).
164 #[inline]
165 fn eq_truncated(&self, other: &IntegerPolynomial, len: u64) -> bool {
166 other.eq_truncated(self, len)
167 }
168}