taco_threshold_automaton/expressions/
fraction.rs

1//! This module contains the implementation of the [`Fraction`] type and its
2//! operations.
3//!
4//! Fractions are used to represent rational numbers in the threshold automaton,
5//! for example, in [`crate::lia_threshold_automaton::LIAThresholdAutomaton`]
6//! Fractions are always stored in their simplified form.
7
8use std::{
9    cmp::Ordering,
10    fmt::{Debug, Display},
11    ops::{self, Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign},
12};
13
14use crate::expressions::{Atomic, IntegerExpression};
15
16/// Type to representing a fraction
17#[derive(Debug, Clone, Copy, PartialEq, Hash)]
18pub struct Fraction {
19    /// True if the fraction is smaller than 0
20    negated: bool,
21    /// Numerator
22    numerator: u32,
23    /// Denominator
24    denominator: u32,
25}
26
27impl Display for Fraction {
28    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
29        debug_assert!(self.is_simplified());
30
31        if let Ok(c) = i64::try_from(*self) {
32            write!(f, "{c}")
33        } else {
34            if self.negated {
35                write!(f, "-")?;
36            }
37            write!(f, "{}/{}", self.numerator, self.denominator)
38        }
39    }
40}
41
42impl Fraction {
43    /// Returns true if the fraction is smaller than 0
44    ///
45    /// # Example
46    ///
47    /// ```rust
48    /// use taco_threshold_automaton::expressions::fraction::Fraction;
49    ///
50    /// // 1/2
51    /// let f = Fraction::new(1, 2, false);
52    /// assert_eq!(f.is_negative(), false);
53    ///
54    /// // -1/2
55    /// let f = Fraction::new(1, 2, true);
56    /// assert_eq!(f.is_negative(), true);
57    /// ```
58    pub fn is_negative(&self) -> bool {
59        debug_assert!(self.is_simplified());
60        self.negated
61    }
62
63    /// Check whether the fraction represents an integer
64    ///
65    /// # Example
66    ///
67    /// ```rust
68    /// use taco_threshold_automaton::expressions::fraction::Fraction;
69    ///
70    /// // 1/2 cannot be represented as an integer
71    /// let f = Fraction::new(1, 2, false);
72    /// assert_eq!(f.is_integer(), false);
73    ///
74    /// // 2/2 -> 1
75    /// let f = Fraction::new(2, 2, false);
76    /// assert_eq!(f.is_integer(), true);
77    /// ```
78    pub fn is_integer(&self) -> bool {
79        self.numerator.is_multiple_of(self.denominator)
80    }
81
82    /// Check if the fraction is simplified
83    fn is_simplified(&self) -> bool {
84        num::integer::gcd(self.numerator, self.denominator) == 1
85    }
86
87    /// Create a new fraction
88    ///
89    /// Create a new fraction with the given numerator and denominator. Upon
90    /// creation, the fraction is simplified to the maximal possible extent.
91    ///
92    /// # Example
93    ///
94    /// ```rust
95    /// use taco_threshold_automaton::expressions::fraction::Fraction;
96    ///
97    /// let f = Fraction::new(42, 2, false);
98    ///
99    /// assert_eq!(i64::try_from(f).unwrap(), 21);
100    /// assert_eq!(f.is_negative(), false);
101    /// assert_eq!(f.numerator(), 21);
102    /// assert_eq!(f.denominator(), 1);
103    /// ```
104    pub fn new(numerator: u32, denominator: u32, negated: bool) -> Self {
105        Self {
106            negated,
107            numerator,
108            denominator,
109        }
110        .canonicalize()
111    }
112
113    /// Simplify the fraction to the maximal possible extent and canonicalize its representation
114    fn canonicalize(self) -> Self {
115        // canonicalize when numerator = 0
116        if self.numerator == 0 {
117            return Self {
118                negated: false,
119                numerator: 0,
120                denominator: 1,
121            };
122        }
123
124        // canonicalize when denominator = 0
125        if self.denominator == 0 {
126            return Self {
127                negated: false,
128                numerator: 1,
129                denominator: 0,
130            };
131        }
132
133        // simplify the fraction
134        let mut numerator = self.numerator;
135        let mut denominator = self.denominator;
136        let gcd = num::integer::gcd(self.numerator, self.denominator);
137
138        numerator /= gcd;
139        denominator /= gcd;
140
141        Self {
142            negated: self.negated,
143            numerator,
144            denominator,
145        }
146    }
147
148    /// Compute the inverse of the fraction
149    ///
150    /// Panics if the numerator of the fraction is 0
151    ///
152    /// # Example
153    ///
154    /// ```rust
155    /// use taco_threshold_automaton::expressions::fraction::Fraction;
156    ///
157    /// let f1 = Fraction::new(13, 2, false).inverse();
158    /// let f2 = Fraction::new(2, 13, false);
159    /// assert_eq!(f1, f2);
160    /// ```
161    pub fn inverse(&self) -> Self {
162        if self.numerator() == 0 {
163            panic!("Division by zero undefined!");
164        }
165
166        Self {
167            negated: self.negated,
168            numerator: self.denominator,
169            denominator: self.numerator,
170        }
171    }
172
173    /// Get the denominator of the fraction
174    ///
175    /// # Example
176    ///
177    /// ```rust
178    /// use taco_threshold_automaton::expressions::fraction::Fraction;
179    ///
180    /// let f = Fraction::new(13, 2, false);
181    /// assert_eq!(f.denominator(), 2);
182    /// ```
183    pub fn denominator(&self) -> u32 {
184        debug_assert!(self.is_simplified());
185        self.denominator
186    }
187
188    /// Get the numerator of the fraction
189    ///
190    /// # Example
191    ///
192    /// ```rust
193    /// use taco_threshold_automaton::expressions::fraction::Fraction;
194    ///
195    /// let f = Fraction::new(42, 1, false);
196    /// assert_eq!(f.numerator(), 42);
197    /// ```
198    pub fn numerator(&self) -> u32 {
199        debug_assert!(self.is_simplified());
200        self.numerator
201    }
202}
203
204impl ops::Neg for Fraction {
205    type Output = Self;
206
207    fn neg(self) -> Self::Output {
208        debug_assert!(self.is_simplified());
209        Self {
210            negated: !self.negated,
211            numerator: self.numerator,
212            denominator: self.denominator,
213        }
214    }
215}
216
217impl Eq for Fraction {}
218
219impl Add for Fraction {
220    type Output = Self;
221
222    fn add(self, rhs: Self) -> Self::Output {
223        if self.negated == rhs.negated {
224            Fraction::new(
225                self.numerator * rhs.denominator + rhs.numerator * self.denominator,
226                self.denominator * rhs.denominator,
227                self.negated,
228            )
229        } else {
230            let denominator = self.denominator * rhs.denominator;
231            let (negated, non_negated) = if self.negated {
232                (self, rhs)
233            } else {
234                (rhs, self)
235            };
236
237            if non_negated.numerator * negated.denominator
238                >= negated.numerator * non_negated.denominator
239            {
240                Fraction::new(
241                    non_negated.numerator * negated.denominator
242                        - negated.numerator * non_negated.denominator,
243                    denominator,
244                    false,
245                )
246            } else {
247                Fraction::new(
248                    negated.numerator * non_negated.denominator
249                        - non_negated.numerator * negated.denominator,
250                    denominator,
251                    true,
252                )
253            }
254        }
255    }
256}
257
258impl AddAssign for Fraction {
259    fn add_assign(&mut self, rhs: Self) {
260        *self = *self + rhs;
261    }
262}
263
264impl Sub for Fraction {
265    type Output = Self;
266
267    fn sub(self, rhs: Self) -> Self::Output {
268        self + (-rhs)
269    }
270}
271
272impl SubAssign for Fraction {
273    fn sub_assign(&mut self, rhs: Self) {
274        *self = *self - rhs;
275    }
276}
277
278impl Mul for Fraction {
279    type Output = Self;
280
281    fn mul(self, rhs: Self) -> Self::Output {
282        Fraction::new(
283            self.numerator * rhs.numerator,
284            self.denominator * rhs.denominator,
285            self.negated ^ rhs.negated,
286        )
287    }
288}
289
290impl MulAssign for Fraction {
291    fn mul_assign(&mut self, rhs: Self) {
292        *self = *self * rhs;
293    }
294}
295
296impl Div for Fraction {
297    type Output = Self;
298
299    #[allow(clippy::suspicious_arithmetic_impl)]
300    fn div(self, rhs: Self) -> Self::Output {
301        self * Fraction::new(rhs.denominator, rhs.numerator, rhs.negated)
302    }
303}
304
305impl DivAssign for Fraction {
306    fn div_assign(&mut self, rhs: Self) {
307        *self = *self / rhs;
308    }
309}
310
311impl From<u32> for Fraction {
312    fn from(value: u32) -> Self {
313        Fraction {
314            negated: false,
315            numerator: value,
316            denominator: 1,
317        }
318    }
319}
320
321impl PartialOrd for Fraction {
322    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
323        Some(self.cmp(other))
324    }
325}
326
327impl Ord for Fraction {
328    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
329        let a = self.numerator * other.denominator;
330        let b = other.numerator * self.denominator;
331
332        if self.negated && !other.negated {
333            return Ordering::Less;
334        }
335
336        if !self.negated && other.negated {
337            return Ordering::Greater;
338        }
339
340        if self.negated && other.negated {
341            // For negative fractions, reverse the comparison
342            return a.cmp(&b).reverse();
343        }
344        a.cmp(&b)
345    }
346}
347
348impl TryFrom<Fraction> for i64 {
349    type Error = ();
350
351    /// Try to convert the fraction into an integer    
352    fn try_from(value: Fraction) -> Result<Self, Self::Error> {
353        if value.numerator.is_multiple_of(value.denominator) {
354            let mut res = value.numerator as i64 / value.denominator as i64;
355
356            if value.negated {
357                res = -res;
358            }
359
360            Ok(res)
361        } else {
362            Err(())
363        }
364    }
365}
366
367impl<T: Atomic> From<Fraction> for IntegerExpression<T> {
368    fn from(value: Fraction) -> Self {
369        // attempt conversion into an integer value first
370        if let Ok(c) = i64::try_from(value) {
371            if c < 0 {
372                return -IntegerExpression::Const(-c as u32);
373            } else {
374                return IntegerExpression::Const(c as u32);
375            }
376        }
377
378        // only return fractions when necessary
379        let mut expr =
380            IntegerExpression::Const(value.numerator) / IntegerExpression::Const(value.denominator);
381
382        if value.negated {
383            expr = -expr;
384        }
385
386        expr
387    }
388}
389
390#[cfg(test)]
391mod tests {
392
393    use crate::expressions::Variable;
394
395    use super::*;
396
397    #[test]
398    fn test_fraction_getters() {
399        let f = Fraction::new(4, 8, false);
400        assert_eq!(f.numerator(), 1);
401        assert_eq!(f.denominator(), 2);
402        assert!(!f.is_negative());
403
404        let f = Fraction::new(12, 9, true);
405        assert_eq!(f.numerator(), 4);
406        assert_eq!(f.denominator(), 3);
407    }
408
409    #[test]
410    fn test_fraction_is_integer() {
411        let f1 = Fraction::new(4, 2, false);
412        assert!(f1.is_integer());
413        let f2 = Fraction::new(5, 2, false);
414        assert!(!f2.is_integer());
415        let f3 = Fraction::new(0, 1, false);
416        assert!(f3.is_integer());
417        let f4 = Fraction::new(0, 0, false);
418        assert!(f4.is_integer()); // 0 is considered an integer
419    }
420
421    #[test]
422    fn test_simplification_for_div_by_zero() {
423        let f1 = Fraction::new(42, 0, true);
424        let f2 = Fraction::new(1, 0, false);
425        assert_eq!(f1, f2);
426    }
427
428    #[test]
429    fn test_fraction_addition() {
430        let f1 = Fraction::new(1, 2, false);
431        let f2 = Fraction::new(1, 3, false);
432        let result = f1 + f2;
433        assert_eq!(result.numerator, 5);
434        assert_eq!(result.denominator, 6);
435        assert!(!result.negated);
436
437        let f1 = Fraction::new(5, 10, false);
438        let f2 = Fraction::new(10, 30, true);
439        let result = f1 + f2;
440        assert_eq!(result.numerator, 1);
441        assert_eq!(result.denominator, 6);
442        assert!(!result.negated);
443
444        let f1 = Fraction::new(3, 6, true);
445        let f2 = Fraction::new(1, 3, false);
446        let result = f1 + f2;
447        assert_eq!(result.numerator, 1);
448        assert_eq!(result.denominator, 6);
449        assert!(result.negated);
450
451        let mut f1 = Fraction::new(3, 6, true);
452        let f2 = Fraction::new(2, 8, true);
453        f1 += f2;
454        assert_eq!(f1.numerator, 3);
455        assert_eq!(f1.denominator, 4);
456        assert!(f1.negated);
457    }
458
459    #[test]
460    fn test_fraction_subtraction() {
461        let f1 = Fraction::new(100, 200, false);
462        let f2 = Fraction::new(10, 30, false);
463        let result = f1 - f2;
464        assert_eq!(result.numerator, 1);
465        assert_eq!(result.denominator, 6);
466        assert!(!result.negated);
467
468        let f1 = Fraction::new(9, 18, false);
469        let f2 = Fraction::new(1, 3, true);
470        let result = f1 - f2;
471        assert_eq!(result.numerator, 5);
472        assert_eq!(result.denominator, 6);
473        assert!(!result.negated);
474
475        let mut f1 = Fraction::new(3, 6, true);
476        let f2 = Fraction::new(1, 3, false);
477        f1 -= f2;
478        assert_eq!(f1.numerator, 5);
479        assert_eq!(f1.denominator, 6);
480        assert!(f1.negated);
481    }
482
483    #[test]
484    fn test_fraction_multiplication() {
485        let f1 = Fraction::new(1, 2, false);
486        let f2 = Fraction::new(1, 3, false);
487        let result = f1 * f2;
488        assert_eq!(result.numerator, 1);
489        assert_eq!(result.denominator, 6);
490        assert!(!result.negated);
491
492        let f1 = Fraction::new(1, 2, false);
493        let f2 = Fraction::new(5, 15, true);
494        let result = f1 * f2;
495        assert_eq!(result.numerator, 1);
496        assert_eq!(result.denominator, 6);
497        assert!(result.negated);
498
499        let f1 = Fraction::new(1, 2, true);
500        let f2 = Fraction::new(1, 3, true);
501        let result = f1 * f2;
502        assert_eq!(result.numerator, 1);
503        assert_eq!(result.denominator, 6);
504        assert!(!result.negated);
505
506        let mut f1 = Fraction::new(1, 2, false);
507        let f2 = Fraction::new(1, 3, true);
508        f1 *= f2;
509        assert_eq!(f1.numerator, 1);
510        assert_eq!(f1.denominator, 6);
511        assert!(f1.negated);
512    }
513
514    #[test]
515    fn test_fraction_division() {
516        let f1 = Fraction::new(1, 2, false);
517        let f2 = Fraction::new(1, 3, false);
518        let result = f1 / f2;
519        assert_eq!(result.numerator, 3);
520        assert_eq!(result.denominator, 2);
521        assert!(!result.negated);
522
523        let f1 = Fraction::new(5, 10, false);
524        let f2 = Fraction::new(20, 40, false);
525        let result = f1 / f2;
526        assert_eq!(result.numerator, 1);
527        assert_eq!(result.denominator, 1);
528
529        let mut f1 = Fraction::new(1, 2, false);
530        let f2 = Fraction::new(1, 3, true);
531        f1 /= f2;
532        assert_eq!(f1.numerator, 3);
533        assert_eq!(f1.denominator, 2);
534        assert!(f1.negated);
535    }
536
537    #[test]
538    fn test_fraction_negation() {
539        let f1 = Fraction::new(1, 2, false);
540        let result = -f1;
541        assert_eq!(result.numerator, 1);
542        assert_eq!(result.denominator, 2);
543        assert!(result.negated);
544    }
545
546    #[test]
547    fn test_fraction_addition_with_negation() {
548        let f1 = Fraction::new(1, 2, false);
549        let f2 = Fraction::new(1, 3, true);
550        let result = f1 + f2;
551        assert_eq!(result.numerator, 1);
552        assert_eq!(result.denominator, 6);
553        assert!(!result.negated);
554    }
555
556    #[test]
557    fn test_fraction_subtraction_with_negation() {
558        let f1 = Fraction::new(1, 2, false);
559        let f2 = Fraction::new(1, 3, true);
560        let result = f1 - f2;
561        assert_eq!(result.numerator, 5);
562        assert_eq!(result.denominator, 6);
563        assert!(!result.negated);
564    }
565
566    #[test]
567    fn test_fraction_multiplication_with_negation() {
568        let f1 = Fraction::new(1, 2, false);
569        let f2 = Fraction::new(1, 3, true);
570        let result = f1 * f2;
571        assert_eq!(result.numerator, 1);
572        assert_eq!(result.denominator, 6);
573        assert!(result.negated);
574    }
575
576    #[test]
577    fn test_fraction_division_with_negation() {
578        let f1 = Fraction::new(1, 2, false);
579        let f2 = Fraction::new(1, 3, true);
580        let result = f1 / f2;
581        assert_eq!(result.numerator, 3);
582        assert_eq!(result.denominator, 2);
583        assert!(result.negated);
584    }
585
586    #[test]
587    fn test_fraction_simplification() {
588        let f = Fraction::new(4, 8, false).canonicalize();
589        assert_eq!(f.numerator, 1);
590        assert_eq!(f.denominator, 2);
591        assert!(!f.negated);
592    }
593
594    #[test]
595    fn test_fraction_eq() {
596        let f1 = Fraction::new(1, 2, false);
597        let f2 = Fraction::new(1, 2, false);
598        assert_eq!(f1, f2);
599
600        let f1 = Fraction::new(1, 2, false);
601        let f2 = Fraction::new(1, 2, true);
602        assert_ne!(f1, f2);
603
604        let f1 = Fraction::new(1, 2, false);
605        let f2 = Fraction::new(2, 4, false);
606        assert_eq!(f1, f2);
607
608        let f1 = Fraction::new(1, 2, false);
609        let f2 = Fraction::new(2, 4, true);
610        assert_ne!(f1, f2);
611
612        let f1 = Fraction::new(0, 2, true);
613        let f2 = Fraction::new(0, 2, false);
614        assert_eq!(f1, f2);
615
616        let f1 = Fraction::new(0, 2, true);
617        let f2 = Fraction::new(0, 3, true);
618        assert_eq!(f1, f2);
619    }
620
621    #[test]
622    fn test_fraction_simplification_with_negation() {
623        let f = Fraction::new(4, 8, true).canonicalize();
624        assert_eq!(f.numerator, 1);
625        assert_eq!(f.denominator, 2);
626        assert!(f.negated);
627    }
628
629    #[test]
630    fn test_fraction_from_u32() {
631        let f: Fraction = 5u32.into();
632        assert_eq!(f.numerator, 5);
633        assert_eq!(f.denominator, 1);
634        assert!(!f.negated);
635    }
636
637    #[test]
638    fn test_fraction_try_into_i64_success() {
639        let f = Fraction::new(4, 2, false);
640        let result: Result<i64, ()> = f.try_into();
641        assert_eq!(result.unwrap(), 2);
642    }
643
644    #[test]
645    fn test_fraction_try_into_i64_failure() {
646        let f = Fraction::new(5, 2, false);
647        let result: Result<i64, ()> = f.try_into();
648        assert!(result.is_err());
649    }
650
651    #[test]
652    fn test_fraction_try_into_i64_negated() {
653        let f = Fraction::new(4, 2, true);
654        let result: Result<i64, ()> = f.try_into();
655        assert_eq!(result.unwrap(), -2);
656    }
657
658    #[test]
659    fn test_fraction_display() {
660        let f = Fraction::new(1, 2, false);
661        assert_eq!(f.to_string(), "1/2");
662
663        let f = Fraction::new(1, 2, true);
664        assert_eq!(f.to_string(), "-1/2");
665
666        let f = Fraction::new(1, 1, false);
667        assert_eq!(f.to_string(), "1");
668    }
669
670    #[test]
671    fn test_fraction_into_integer_expression() {
672        let f = Fraction::new(1, 2, false);
673        let expr: IntegerExpression<Variable> = f.into();
674        assert_eq!(
675            expr,
676            IntegerExpression::Const(1) / IntegerExpression::Const(2)
677        );
678
679        let f = Fraction::new(1, 2, true);
680        let expr: IntegerExpression<Variable> = f.into();
681        assert_eq!(
682            expr,
683            -(IntegerExpression::Const(1) / IntegerExpression::Const(2))
684        );
685
686        let f = Fraction::new(1, 1, false);
687        let expr: IntegerExpression<Variable> = f.into();
688        assert_eq!(expr, IntegerExpression::Const(1));
689
690        let f = Fraction::new(1, 1, true);
691        let expr: IntegerExpression<Variable> = f.into();
692        assert_eq!(expr, -IntegerExpression::Const(1));
693    }
694
695    #[test]
696    fn test_inverse() {
697        let f = Fraction::new(1, 2, true);
698        let expected = Fraction::new(2, 1, true);
699        assert_eq!(f.inverse(), expected);
700
701        let f = Fraction::new(1, 2, false);
702        let expected = Fraction::new(2, 1, false);
703        assert_eq!(f.inverse(), expected);
704    }
705
706    #[test]
707    #[should_panic]
708    fn test_inverse_panics_on_0_numerator() {
709        let f = Fraction::new(0, 2, true);
710        let _ = f.inverse();
711    }
712
713    #[test]
714    fn test_fraction_ord() {
715        let f1 = Fraction::new(1, 2, false);
716        let f2 = Fraction::new(1, 2, false);
717        assert_eq!(f1.cmp(&f2), Ordering::Equal);
718        assert_eq!(f2.cmp(&f1), Ordering::Equal);
719
720        let f1 = Fraction::new(1, 2, true);
721        let f2 = Fraction::new(1, 2, true);
722        assert_eq!(f1.cmp(&f2), Ordering::Equal);
723        assert_eq!(f2.cmp(&f1), Ordering::Equal);
724
725        let f1 = Fraction::new(1, 2, true);
726        let f2 = Fraction::new(1, 2, false);
727        assert_eq!(f1.cmp(&f2), Ordering::Less);
728        assert_eq!(f2.cmp(&f1), Ordering::Greater);
729
730        let f1 = Fraction::new(1, 2, false);
731        let f2 = Fraction::new(2, 2, false);
732        assert_eq!(f1.cmp(&f2), Ordering::Less);
733        assert_eq!(f2.cmp(&f1), Ordering::Greater);
734
735        let f1 = Fraction::new(1, 4, false);
736        let f2 = Fraction::new(1, 2, false);
737        assert_eq!(f1.cmp(&f2), Ordering::Less);
738        assert_eq!(f2.cmp(&f1), Ordering::Greater);
739    }
740}
taco_threshold_automaton/expressions/fraction.rs

taco_threshold_automaton/expressions/
fraction.rs
