oxiz_math/polynomial/
constructors.rs

1//! Polynomial constructors and query methods.
2
3use super::types::*;
4#[allow(unused_imports)]
5use crate::prelude::*;
6use num_bigint::BigInt;
7use num_rational::BigRational;
8use num_traits::{One, Zero};
9
10impl super::Polynomial {
11    /// Create the zero polynomial.
12    #[inline]
13    pub fn zero() -> Self {
14        Self {
15            terms: Vec::new(),
16            order: MonomialOrder::default(),
17        }
18    }
19
20    /// Create the one polynomial.
21    #[inline]
22    pub fn one() -> Self {
23        Self::constant(BigRational::one())
24    }
25
26    /// Create a constant polynomial.
27    pub fn constant(c: BigRational) -> Self {
28        if c.is_zero() {
29            Self::zero()
30        } else {
31            Self {
32                terms: vec![Term::constant(c)],
33                order: MonomialOrder::default(),
34            }
35        }
36    }
37
38    /// Create a polynomial from a single variable.
39    pub fn from_var(var: Var) -> Self {
40        Self {
41            terms: vec![Term::from_var(var)],
42            order: MonomialOrder::default(),
43        }
44    }
45
46    /// Create a polynomial x^k.
47    pub fn from_var_power(var: Var, power: u32) -> Self {
48        if power == 0 {
49            Self::one()
50        } else {
51            Self {
52                terms: vec![Term::new(
53                    BigRational::one(),
54                    Monomial::from_var_power(var, power),
55                )],
56                order: MonomialOrder::default(),
57            }
58        }
59    }
60
61    /// Create a polynomial from terms. Normalizes and combines like terms.
62    pub fn from_terms(terms: impl IntoIterator<Item = Term>, order: MonomialOrder) -> Self {
63        let mut poly = Self {
64            terms: terms.into_iter().filter(|t| !t.is_zero()).collect(),
65            order,
66        };
67        poly.normalize();
68        poly
69    }
70
71    /// Create a polynomial from integer coefficients.
72    pub fn from_coeffs_int(coeffs: &[(i64, &[(Var, u32)])]) -> Self {
73        let terms: Vec<Term> = coeffs
74            .iter()
75            .map(|(c, powers)| {
76                Term::new(
77                    BigRational::from_integer(BigInt::from(*c)),
78                    Monomial::from_powers(powers.iter().copied()),
79                )
80            })
81            .collect();
82        Self::from_terms(terms, MonomialOrder::default())
83    }
84
85    /// Create a linear polynomial a1*x1 + a2*x2 + ... + c.
86    pub fn linear(coeffs: &[(BigRational, Var)], constant: BigRational) -> Self {
87        let mut terms: Vec<Term> = coeffs
88            .iter()
89            .filter(|(c, _)| !c.is_zero())
90            .map(|(c, v)| Term::new(c.clone(), Monomial::from_var(*v)))
91            .collect();
92
93        if !constant.is_zero() {
94            terms.push(Term::constant(constant));
95        }
96
97        Self::from_terms(terms, MonomialOrder::default())
98    }
99
100    /// Create a univariate polynomial from coefficients.
101    /// `coeffs[i]` is the coefficient of x^i.
102    pub fn univariate(var: Var, coeffs: &[BigRational]) -> Self {
103        let terms: Vec<Term> = coeffs
104            .iter()
105            .enumerate()
106            .filter(|(_, c)| !c.is_zero())
107            .map(|(i, c)| Term::new(c.clone(), Monomial::from_var_power(var, i as u32)))
108            .collect();
109        Self::from_terms(terms, MonomialOrder::default())
110    }
111
112    /// Check if the polynomial is zero.
113    #[inline]
114    pub fn is_zero(&self) -> bool {
115        self.terms.is_empty()
116    }
117
118    /// Check if the polynomial is a non-zero constant.
119    #[inline]
120    pub fn is_constant(&self) -> bool {
121        self.terms.len() == 1 && self.terms[0].monomial.is_unit()
122    }
123
124    /// Get the constant value of the polynomial.
125    ///
126    /// Returns the constant coefficient if the polynomial is constant,
127    /// or zero if the polynomial is zero.
128    pub fn constant_value(&self) -> BigRational {
129        if self.is_zero() {
130            BigRational::zero()
131        } else if self.is_constant() {
132            self.terms[0].coeff.clone()
133        } else {
134            BigRational::zero()
135        }
136    }
137
138    /// Check if the polynomial is one.
139    pub fn is_one(&self) -> bool {
140        self.terms.len() == 1 && self.terms[0].monomial.is_unit() && self.terms[0].coeff.is_one()
141    }
142
143    /// Check if the polynomial is univariate.
144    pub fn is_univariate(&self) -> bool {
145        if self.terms.is_empty() {
146            return true;
147        }
148
149        let mut var: Option<Var> = None;
150        for term in &self.terms {
151            for vp in term.monomial.vars() {
152                match var {
153                    None => var = Some(vp.var),
154                    Some(v) if v != vp.var => return false,
155                    _ => {}
156                }
157            }
158        }
159        true
160    }
161
162    /// Check if the polynomial is linear (all terms have degree <= 1).
163    pub fn is_linear(&self) -> bool {
164        self.terms.iter().all(|t| t.monomial.is_linear())
165    }
166
167    /// Get the number of terms.
168    #[inline]
169    pub fn num_terms(&self) -> usize {
170        self.terms.len()
171    }
172
173    /// Get the terms.
174    #[inline]
175    pub fn terms(&self) -> &[Term] {
176        &self.terms
177    }
178
179    /// Get the total degree of the polynomial.
180    pub fn total_degree(&self) -> u32 {
181        self.terms
182            .iter()
183            .map(|t| t.monomial.total_degree())
184            .max()
185            .unwrap_or(0)
186    }
187
188    /// Get the degree with respect to a specific variable.
189    pub fn degree(&self, var: Var) -> u32 {
190        self.terms
191            .iter()
192            .map(|t| t.monomial.degree(var))
193            .max()
194            .unwrap_or(0)
195    }
196
197    /// Get the maximum variable in the polynomial, or NULL_VAR if constant.
198    pub fn max_var(&self) -> Var {
199        self.terms
200            .iter()
201            .map(|t| t.monomial.max_var())
202            .filter(|&v| v != NULL_VAR)
203            .max()
204            .unwrap_or(NULL_VAR)
205    }
206
207    /// Get all variables in the polynomial.
208    pub fn vars(&self) -> Vec<Var> {
209        let mut vars: Vec<Var> = self
210            .terms
211            .iter()
212            .flat_map(|t| t.monomial.vars().iter().map(|vp| vp.var))
213            .collect();
214        vars.sort_unstable();
215        vars.dedup();
216        vars
217    }
218
219    /// Get the leading term (with respect to monomial order).
220    #[inline]
221    pub fn leading_term(&self) -> Option<&Term> {
222        self.terms.first()
223    }
224
225    /// Get the leading coefficient.
226    pub fn leading_coeff(&self) -> BigRational {
227        self.terms
228            .first()
229            .map(|t| t.coeff.clone())
230            .unwrap_or_else(BigRational::zero)
231    }
232
233    /// Get the leading monomial.
234    pub fn leading_monomial(&self) -> Option<&Monomial> {
235        self.terms.first().map(|t| &t.monomial)
236    }
237
238    /// Get the constant term.
239    pub fn constant_term(&self) -> BigRational {
240        self.terms
241            .iter()
242            .find(|t| t.monomial.is_unit())
243            .map(|t| t.coeff.clone())
244            .unwrap_or_else(BigRational::zero)
245    }
246
247    /// Get the coefficient of x^k for a univariate polynomial.
248    pub fn univ_coeff(&self, var: Var, k: u32) -> BigRational {
249        for term in &self.terms {
250            if term.monomial.degree(var) == k && term.monomial.num_vars() <= 1 {
251                return term.coeff.clone();
252            }
253        }
254        BigRational::zero()
255    }
256
257    /// Get the coefficient polynomial for x^k.
258    /// For polynomial p(y_1, ..., y_n, x), returns coefficient of x^k.
259    pub fn coeff(&self, var: Var, k: u32) -> super::Polynomial {
260        let terms: Vec<Term> = self
261            .terms
262            .iter()
263            .filter(|t| t.monomial.degree(var) == k)
264            .map(|t| {
265                let new_mon = if let Some(m) = t.monomial.div(&Monomial::from_var_power(var, k)) {
266                    m
267                } else {
268                    Monomial::unit()
269                };
270                Term::new(t.coeff.clone(), new_mon)
271            })
272            .collect();
273        super::Polynomial::from_terms(terms, self.order)
274    }
275
276    /// Get the leading coefficient with respect to variable x.
277    pub fn leading_coeff_wrt(&self, var: Var) -> super::Polynomial {
278        let d = self.degree(var);
279        self.coeff(var, d)
280    }
281
282    /// Normalize the polynomial (sort terms and combine like terms).
283    pub(crate) fn normalize(&mut self) {
284        if self.terms.is_empty() {
285            return;
286        }
287
288        // Sort by monomial order (descending)
289        let order = self.order;
290        self.terms
291            .sort_by(|a, b| order.compare(&b.monomial, &a.monomial));
292
293        // Combine like terms
294        let mut i = 0;
295        while i < self.terms.len() {
296            let mut j = i + 1;
297            while j < self.terms.len() && self.terms[j].monomial == self.terms[i].monomial {
298                let coeff = self.terms[j].coeff.clone();
299                self.terms[i].coeff += coeff;
300                j += 1;
301            }
302            // Remove combined terms
303            if j > i + 1 {
304                self.terms.drain((i + 1)..j);
305            }
306            i += 1;
307        }
308
309        // Remove zero terms
310        self.terms.retain(|t| !t.coeff.is_zero());
311    }
312}
oxiz_math/polynomial/constructors.rs

oxiz_math/polynomial/
constructors.rs
