rust_polynomial/
poly.rs

1use core::panic;
2use std::{
3    collections::HashMap,
4    fmt::Display,
5    ops::{Add, Div, Index, Mul, Neg},
6};
7
8use num::{Integer, Zero};
9
10use crate::{mono::Monomial, MonomialValue};
11
12/// Equations differents types
13#[derive(PartialEq, Debug)]
14pub enum EquationType {
15    /// [Linear equation](https://en.wikipedia.org/wiki/Linear_equation)
16    /// `2x + 1`
17    Linear,
18
19    /// [Quadratic equation](https://en.wikipedia.org/wiki/Quadratic_equation)
20    /// `2x^2 + 2x + 1`
21    Quadratic,
22
23    /// [Biquadratic equation](https://en.wikipedia.org/wiki/Quartic_equation)
24    /// `2x^4 + 2x^2 + 1`
25    Biquadratic,
26
27    /// Equation with exponent grater than **2**
28    /// `2x^3 + 3x^2`
29    BigExp,
30
31    /// Equation with exponent grater than **2**, but they only have **two** terms
32    /// `2x^3 + 100`
33    BigExp2Terms,
34
35    /// Invalid equation type
36    Invalid,
37}
38
39/// [Polynomial](https://en.wikipedia.org/wiki/Polynomial) representation
40#[derive(Debug, PartialEq, Clone)]
41pub struct Polynomial<T> {
42    mono_vec: Vec<Monomial<T>>,
43}
44
45impl<T: MonomialValue> Polynomial<T> {
46    /// Constructs a new `Polynomial<T>`
47    /// # Examples
48    /// ```
49    /// # use rust_polynomial::{Polynomial, Monomial};
50    /// let mono_vec: Vec<Monomial<i32>> = vec![
51    ///     Monomial::new(2, 2),
52    ///     Monomial::new(-1, 1),
53    ///     Monomial::new(10, 0),
54    /// ];
55    ///
56    /// let poly: Polynomial<i32> = Polynomial::new(mono_vec);
57    /// ```
58    pub fn new(mono_vec: Vec<Monomial<T>>) -> Polynomial<T> {
59        let mut poly = Polynomial { mono_vec };
60        poly.collapse();
61        poly
62    }
63
64    /// Sum all Monomials with the same exponent and collapse in a simplificated
65    fn collapse(&mut self) {
66        let mut group_by_exp: HashMap<i32, Vec<Monomial<T>>> = HashMap::new();
67        for mono in self.mono_vec.iter() {
68            group_by_exp
69                .entry(mono.get_exp())
70                .or_insert_with(Vec::new)
71                .push(*mono);
72        }
73
74        let mut mono_vec: Vec<Monomial<T>> = group_by_exp
75            .into_iter()
76            .map(|(_, m)| m.into_iter().sum::<Monomial<T>>())
77            .collect();
78
79        mono_vec.retain(|&m| m.get_value() != T::zero());
80
81        mono_vec.sort_by(|m1, m2| m2.get_exp().cmp(&m1.get_exp()));
82
83        self.mono_vec = mono_vec;
84    }
85
86    /// Returns the monomial with the max exponent
87    /// # Examples
88    /// ```
89    /// # use rust_polynomial::{Polynomial, Monomial};
90    /// let poly: Polynomial<i32> = Polynomial::try_from("x^2 - 5x - 100").unwrap();
91    ///
92    /// assert_eq!(poly.max_exp().get_exp(), 2);
93    /// ```
94    pub fn max_exp(&self) -> Monomial<T> {
95        if self.mono_vec.is_empty() {
96            return Monomial::default();
97        }
98
99        self.mono_vec[0]
100    }
101
102    /// Add a monomial but without [`collapse`]
103    fn push_raw(&mut self, mono: Monomial<T>) {
104        self.mono_vec.push(mono);
105    }
106
107    /// Returns the number of Monomials in the Polynomial, also referred to as its 'length'
108    /// # Examples
109    /// ```
110    /// # use rust_polynomial::{Polynomial, Monomial};
111    /// let poly: Polynomial<i32> = Polynomial::default();
112    ///
113    /// assert_eq!(poly.len(), 0);
114    /// ```
115    pub fn len(&self) -> usize {
116        self.mono_vec.len()
117    }
118
119    /// Returns the equation type
120    /// # Examples
121    /// ```
122    /// # use rust_polynomial::{Polynomial, Monomial, EquationType};
123    /// let poly: Polynomial<i32> = Polynomial::try_from("5x - 100").unwrap();
124    ///
125    /// assert_eq!(poly.equation_type(), EquationType::Linear);
126    /// ```
127    pub fn equation_type(&self) -> EquationType {
128        match self.max_exp().get_exp() {
129            0 => EquationType::Invalid,
130            1 => EquationType::Linear,
131            e if e > 1 && self.len() == 2 => EquationType::BigExp2Terms,
132            2 => EquationType::Quadratic,
133            4 if self.find_by_exp(3).get_value().is_zero()
134                && self.find_by_exp(1).get_value().is_zero() =>
135            {
136                EquationType::Biquadratic
137            }
138            _ => EquationType::BigExp,
139        }
140    }
141
142    /// Add a monomial
143    /// # Examples
144    /// ```
145    /// # use rust_polynomial::{Polynomial, Monomial};
146    /// let mut poly: Polynomial<i32> = Polynomial::try_from("5x - 100").unwrap();
147    /// let mono: Monomial<i32> = Monomial::try_from("2x^2").unwrap();
148    ///
149    /// poly.push(mono);
150    ///
151    /// assert_eq!(format!("{poly}"), "2x^2 + 5x - 100");
152    ///
153    /// ```
154    pub fn push(&mut self, mono: Monomial<T>) {
155        self.push_raw(mono);
156        self.collapse();
157    }
158
159    /// Find monomial in a polynomial by the exponent if don't find the monomial returns
160    /// [`Monomial::default()`]
161    /// # Examples
162    /// ```
163    /// # use rust_polynomial::{Polynomial, Monomial};
164    /// let poly: Polynomial<i32> = Polynomial::try_from("2x^2 + 5x - 100").unwrap();
165    ///
166    /// assert_eq!(poly.find_by_exp(1), Monomial::new(5, 1));
167    /// assert_eq!(poly.find_by_exp(10), Monomial::default());
168    ///
169    /// ```
170    pub fn find_by_exp(&self, exp: i32) -> Monomial<T> {
171        self.into_iter()
172            .find(|m| m.get_exp() == exp)
173            .cloned()
174            .unwrap_or_default()
175    }
176
177    /// Returns a new polynomial as result of dividing a monomial
178    /// # Examples
179    /// ```
180    /// # use rust_polynomial::{Polynomial, Monomial};
181    /// let poly: Polynomial<i32> = Polynomial::try_from("10x - 10").unwrap();
182    /// let mono: Monomial<i32> = Monomial::try_from("2").unwrap();
183    ///
184    /// let result = poly.div_mono(mono);
185    ///
186    /// assert_eq!(format!("{result}"), "5x - 5");
187    ///
188    /// ```
189    pub fn div_mono(self, rhs: Monomial<T>) -> Self {
190        let mono_vec = self.into_iter().map(|m| m / rhs).collect();
191
192        Polynomial::new(mono_vec)
193    }
194
195    /// Returns a new polynomial as result of multiplying a monomial
196    /// # Examples
197    /// ```
198    /// # use rust_polynomial::{Polynomial, Monomial};
199    /// let poly: Polynomial<i32> = Polynomial::try_from("10x - 10").unwrap();
200    /// let mono: Monomial<i32> = Monomial::try_from("2").unwrap();
201    ///
202    /// let result = poly.mul_mono(mono);
203    ///
204    /// assert_eq!(format!("{result}"), "20x - 20");
205    ///
206    /// ```
207    pub fn mul_mono(self, rhs: Monomial<T>) -> Self {
208        let mono_vec = self.into_iter().map(|m| m * rhs).collect();
209
210        Polynomial::new(mono_vec)
211    }
212
213    /// Returns an [`Option`] containing the roots of the equation
214    /// This function uses different strategies based on [`EquationType`]
215    /// # Examples
216    /// ```
217    ///# use rust_polynomial::Polynomial;
218    /// let poly: Polynomial<i32> = Polynomial::try_from("x - 9").unwrap();
219    ///
220    /// assert_eq!(poly.roots(), Some(vec![9]));
221    /// ```
222    pub fn roots(&self) -> Option<Vec<T>> {
223        match self.equation_type() {
224            EquationType::Linear => Polynomial::<T>::linear_root(self),
225            EquationType::Quadratic => Polynomial::<T>::quadratic_root(self),
226            EquationType::Biquadratic => Polynomial::<T>::biquadratic_root(self),
227            EquationType::BigExp2Terms => Polynomial::<T>::big_exp2_root(self),
228            EquationType::BigExp => Polynomial::<T>::big_exp_root(self),
229            EquationType::Invalid => None,
230        }
231    }
232
233    fn linear_root(poly: &Self) -> Option<Vec<T>> {
234        let len = poly.into_iter().len();
235
236        if len > 2 || len < 1 {
237            panic!("{poly} is not a linear equation");
238        }
239
240        if len == 1 {
241            return Some(vec![T::zero()]);
242        }
243
244        let result = poly[1].neg().get_value() / poly[0].get_value();
245
246        Some(vec![result])
247    }
248
249    fn quadratic_root(poly: &Self) -> Option<Vec<T>> {
250        #[rustfmt::skip]
251        let [a, b, c] = [
252            poly.max_exp(),
253            poly.find_by_exp(1),
254            poly.find_by_exp(0)
255        ].map(|m|m.get_value().to_f64().unwrap());
256
257        if b.is_zero() && c.is_zero() {
258            return Some(vec![T::zero()]);
259        }
260
261        if b.is_zero() {
262            let mut linear = poly.clone();
263            linear.mono_vec[0].exp = 1;
264            let linear_result = Polynomial::<T>::linear_root(&linear)?[0].to_f64()?;
265            let sqrt = T::from(linear_result.sqrt())?;
266
267            if sqrt.is_zero() {
268                return Some(vec![sqrt]);
269            }
270
271            return Some(vec![sqrt.neg(), sqrt]);
272        }
273
274        let sqrt = ((b * b) - (4f64 * a * c)).sqrt();
275
276        let result_1 = T::from((b.neg() + sqrt) / (2f64 * a))?;
277        let result_2 = T::from((b.neg() - sqrt) / (2f64 * a))?;
278
279        if result_1 == result_2 {
280            return Some(vec![result_1]);
281        }
282
283        let mut result = vec![result_1, result_2];
284        result.sort_by(|a, b| a.partial_cmp(b).unwrap());
285
286        Some(result)
287    }
288
289    fn biquadratic_root(poly: &Self) -> Option<Vec<T>> {
290        let [mut a, mut b, c] = [
291            poly.find_by_exp(4),
292            poly.find_by_exp(2),
293            poly.find_by_exp(0),
294        ];
295
296        a.exp = 2;
297        b.exp = 1;
298
299        let quadratic: Polynomial<T> = Polynomial::new(vec![a, b, c]);
300        let quadrtic_result = Polynomial::<T>::quadratic_root(&quadratic)?;
301
302        if quadrtic_result.len() == 1 {
303            let result = T::from(quadrtic_result[0].to_f64()?.sqrt())?;
304
305            return Some(vec![result.neg(), result]);
306        }
307
308        let sqrt_converter = |x: T| T::from(x.to_f64()?.abs().sqrt());
309
310        if let [r1, r2] = *quadrtic_result {
311            let mut result = if r1.abs() == r2.abs() {
312                let r = sqrt_converter(r1)?;
313                vec![r.neg(), r]
314            } else {
315                let r1_1 = sqrt_converter(r1)?;
316                let r2_1 = sqrt_converter(r2)?;
317                vec![r1_1.neg(), r2_1.neg(), r1_1, r2_1]
318            };
319            result.sort_by(|a, b| a.partial_cmp(b).unwrap());
320
321            return Some(result);
322        }
323
324        None
325    }
326
327    fn big_exp2_root(poly: &Self) -> Option<Vec<T>> {
328        if poly.len() != 2 {
329            return None;
330        }
331
332        let [a, b] = [poly.max_exp(), poly.find_by_exp(0)];
333        let value = (b.get_value().neg() / a.get_value()).to_f64()?;
334
335        if a.get_exp().is_even() && value.is_sign_negative() {
336            return None;
337        }
338
339        let mut result_val = T::from(value.abs().powf(1f64 / a.get_exp() as f64))?;
340
341        if a.get_exp().is_odd() {
342            if value < 0f64 {
343                result_val = result_val.neg();
344            }
345
346            return Some(vec![result_val]);
347        }
348
349        let mut result = vec![result_val.neg(), result_val];
350        result.sort_by(|a, b| a.partial_cmp(b).unwrap());
351
352        Some(result)
353    }
354
355    fn big_exp_root(poly: &Self) -> Option<Vec<T>> {
356        let (root, rest) = Polynomial::<T>::find_root(poly);
357
358        let mut roots: Vec<T> = Vec::new();
359
360        if let Some(r) = root {
361            roots.push(T::from(r).unwrap())
362        }
363
364        if let Some(poly) = rest {
365            if let Some(r) = poly.roots() {
366                let generic: Vec<T> = r.into_iter().map(T::from).map(|o| o.unwrap()).collect();
367
368                roots.extend(generic);
369            }
370        }
371
372        if roots.is_empty() {
373            return None;
374        }
375
376        roots.sort_by(|a, b| a.partial_cmp(b).unwrap());
377
378        Some(roots)
379    }
380
381    fn find_divs(value: u64) -> Vec<i64> {
382        let mut divs: Vec<i64> = Vec::new();
383
384        for v in 1..=value {
385            if value % v == 0 {
386                divs.push(v as i64);
387            }
388        }
389
390        let negative: Vec<_> = divs.iter().map(|d| d.neg()).collect();
391        divs.extend(negative);
392
393        divs
394    }
395
396    fn find_root(poly: &Self) -> (Option<i64>, Option<Polynomial<i64>>) {
397        let root_base = match poly.find_by_exp(0).get_value().abs().to_u64() {
398            Some(rb) => rb,
399            None => return (None, None),
400        };
401
402        let divs = Polynomial::<T>::find_divs(root_base);
403
404        let mut target: Polynomial<i64> = Polynomial::default();
405        let mut root: Option<i64> = None;
406
407        'div_loop: for div in divs {
408            let max_exp = poly.max_exp().get_exp();
409            let mut current = 0i64;
410            let mut current_poly: Polynomial<i64> = Polynomial::default();
411            for (i, exp) in (0..=max_exp).rev().enumerate() {
412                let mono_val = match poly.find_by_exp(exp).get_value().to_i64() {
413                    Some(val) => val,
414                    None => return (None, None),
415                };
416
417                let sum = mono_val + current;
418
419                current_poly.push_raw(Monomial::new(sum, exp - 1));
420
421                if i as i32 == max_exp && sum.is_zero() {
422                    root.replace(div);
423                    current_poly.collapse();
424                    target = current_poly;
425                    break 'div_loop;
426                }
427
428                current = sum * div;
429            }
430        }
431
432        if root.is_none() {
433            return (None, None);
434        }
435
436        if target == Polynomial::<i64>::default() {
437            return (root, None);
438        }
439
440        (root, Some(target))
441    }
442}
443
444impl<T: MonomialValue> Default for Polynomial<T> {
445    fn default() -> Self {
446        Polynomial::new(vec![Monomial::default()])
447    }
448}
449
450impl<T: MonomialValue> From<Vec<Monomial<T>>> for Polynomial<T> {
451    fn from(value: Vec<Monomial<T>>) -> Self {
452        Polynomial::new(value)
453    }
454}
455
456impl<T: MonomialValue> TryFrom<&str> for Polynomial<T> {
457    type Error = &'static str;
458
459    fn try_from(value: &str) -> Result<Self, Self::Error> {
460        let clean_value = value.trim().replace(" ", "");
461
462        if clean_value.len() == 1 {
463            let mono = Monomial::try_from(&clean_value as &str)?;
464            return Ok(Polynomial::new(vec![mono]));
465        }
466
467        let mut mono_vec: Vec<Monomial<T>> = Vec::new();
468        let mut tmp_mono_split = String::new();
469        for (i, char) in clean_value.char_indices() {
470            if i == 0 {
471                tmp_mono_split.push(char);
472                continue;
473            }
474
475            if vec!['-', '+'].contains(&char) {
476                mono_vec.push(Monomial::try_from(&tmp_mono_split as &str)?);
477                tmp_mono_split.clear();
478                tmp_mono_split.push(char);
479                continue;
480            }
481
482            if i == clean_value.len() - 1 {
483                tmp_mono_split.push(char);
484                mono_vec.push(Monomial::try_from(&tmp_mono_split as &str)?);
485                continue;
486            }
487
488            tmp_mono_split.push(char);
489        }
490
491        Ok(Polynomial::new(mono_vec))
492    }
493}
494
495impl<T: MonomialValue> Neg for Polynomial<T> {
496    type Output = Self;
497
498    fn neg(self) -> Self::Output {
499        let mono_vec = self.into_iter().map(Monomial::neg).collect();
500
501        Polynomial::new(mono_vec)
502    }
503}
504
505impl<T: MonomialValue> Add for Polynomial<T> {
506    type Output = Self;
507
508    fn add(self, rhs: Self) -> Self::Output {
509        Polynomial::new([self.mono_vec.clone(), rhs.mono_vec.clone()].concat())
510    }
511}
512
513impl<T: MonomialValue> Mul for Polynomial<T> {
514    type Output = Self;
515
516    fn mul(self, rhs: Self) -> Self::Output {
517        let mut result: Vec<Monomial<T>> = Vec::new();
518        for self_mono in &self {
519            for rhs_mono in &rhs {
520                result.push(*self_mono * *rhs_mono);
521            }
522        }
523
524        Polynomial::new(result)
525    }
526}
527
528impl<T: MonomialValue> Div for Polynomial<T> {
529    type Output = (Self, Self);
530
531    fn div(self, rhs: Self) -> Self::Output {
532        let mut dividend = self;
533        let divider = rhs;
534        let mut quotient: Polynomial<T> = Polynomial::default();
535
536        while dividend.max_exp().get_exp() >= divider.max_exp().get_exp() {
537            let result = dividend.max_exp() / divider.max_exp();
538            quotient.push_raw(result);
539
540            dividend = dividend.clone() + (divider.clone().mul_mono(result)).neg();
541        }
542
543        quotient.collapse();
544
545        (quotient, dividend)
546    }
547}
548
549impl<T: MonomialValue> TryFrom<Vec<T>> for Polynomial<T> {
550    type Error = &'static str;
551
552    fn try_from(value: Vec<T>) -> Result<Self, Self::Error> {
553        let mut mono_vec: Vec<Monomial<T>> = Vec::new();
554
555        for (i, v) in value.iter().enumerate() {
556            if *v == T::zero() {
557                continue;
558            }
559
560            let exp = value.len() - 1 - i;
561            mono_vec.push(Monomial::new(*v as T, exp as i32));
562        }
563
564        if mono_vec.is_empty() {
565            return Ok(Polynomial::default());
566        }
567
568        Ok(Polynomial::new(mono_vec))
569    }
570}
571
572impl<T: MonomialValue> Index<usize> for Polynomial<T> {
573    type Output = Monomial<T>;
574
575    fn index(&self, index: usize) -> &Self::Output {
576        &self.mono_vec[index]
577    }
578}
579
580impl<T: MonomialValue> IntoIterator for Polynomial<T> {
581    type Item = Monomial<T>;
582    type IntoIter = std::vec::IntoIter<Self::Item>;
583
584    fn into_iter(self) -> Self::IntoIter {
585        self.mono_vec.into_iter()
586    }
587}
588
589impl<'a, T: MonomialValue> IntoIterator for &'a Polynomial<T> {
590    type Item = &'a Monomial<T>;
591    type IntoIter = std::slice::Iter<'a, Monomial<T>>;
592
593    fn into_iter(self) -> Self::IntoIter {
594        self.mono_vec.iter()
595    }
596}
597
598impl<T: MonomialValue> Display for Polynomial<T> {
599    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
600        if self.mono_vec.is_empty() {
601            write!(f, "0")?;
602            return Ok(());
603        }
604
605        for (i, mono) in self.mono_vec.iter().enumerate() {
606            let sign = match mono.get_value() < T::zero() {
607                true if i == 0 => "-".to_string(),
608                true => " - ".to_string(),
609                false if i == 0 => "".to_string(),
610                false => " + ".to_string(),
611            };
612
613            let mono_abs = Monomial::new(mono.get_value().abs(), mono.get_exp());
614
615            write!(f, "{sign}{mono_abs}")?;
616        }
617
618        Ok(())
619    }
620}
rust_polynomial/poly.rs

rust_polynomial/
poly.rs
