competitive/num/
rational.rs

1use super::{Bounded, One, Signed, Unsigned, Zero};
2use std::{
3    cmp::Ordering,
4    fmt::{self, Debug},
5    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
6};
7
8#[derive(Clone, Copy)]
9pub struct Rational<T>
10where
11    T: Signed,
12{
13    pub num: T,
14    pub den: T,
15}
16
17impl<T> PartialEq for Rational<T>
18where
19    T: Signed,
20{
21    fn eq(&self, other: &Self) -> bool {
22        self.num == other.num && self.den == other.den
23    }
24}
25
26impl<T> Eq for Rational<T> where T: Signed {}
27
28impl<T> PartialOrd for Rational<T>
29where
30    T: Signed,
31{
32    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
33        Some(self.cmp(other))
34    }
35}
36
37impl<T> Ord for Rational<T>
38where
39    T: Signed,
40{
41    fn cmp(&self, other: &Self) -> Ordering {
42        match (self.den.is_zero(), other.den.is_zero()) {
43            (true, true) => self.num.cmp(&other.num),
44            (true, false) => self.num.cmp(&T::zero()),
45            (false, true) => T::zero().cmp(&other.num),
46            (false, false) => (self.num * other.den).cmp(&(self.den * other.num)),
47        }
48    }
49}
50
51impl<T> Debug for Rational<T>
52where
53    T: Signed + Debug,
54{
55    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56        write!(f, "{:?}/{:?}", self.num, self.den)
57    }
58}
59
60impl<T> Rational<T>
61where
62    T: Signed,
63{
64    pub fn new(num: T, den: T) -> Self {
65        let g = num.abs().unsigned().gcd(den.abs().unsigned()).signed();
66        let g = if den.is_negative() { -g } else { g };
67        Self::new_unchecked(num / g, den / g)
68    }
69    pub fn new_unchecked(num: T, den: T) -> Self {
70        Self { num, den }
71    }
72    pub fn abs(self) -> Self {
73        Self::new_unchecked(self.num.abs(), self.den)
74    }
75    pub fn eval(self) -> T {
76        self.num / self.den
77    }
78    pub fn map<U>(self, mut f: impl FnMut(T) -> U) -> Rational<U>
79    where
80        U: Signed,
81    {
82        Rational::new(f(self.num), f(self.den))
83    }
84    pub fn map_unchecked<U>(self, mut f: impl FnMut(T) -> U) -> Rational<U>
85    where
86        U: Signed,
87    {
88        Rational::new_unchecked(f(self.num), f(self.den))
89    }
90    pub fn map_eval<U>(self, mut f: impl FnMut(T) -> U) -> <U as Div>::Output
91    where
92        U: Div,
93    {
94        f(self.num) / f(self.den)
95    }
96}
97
98impl<T> Bounded for Rational<T>
99where
100    T: Signed,
101{
102    fn maximum() -> Self {
103        Self::new_unchecked(T::one(), T::zero())
104    }
105    fn minimum() -> Self {
106        Self::new_unchecked(-T::one(), T::zero())
107    }
108}
109
110impl<T> Zero for Rational<T>
111where
112    T: Signed,
113{
114    fn zero() -> Self {
115        Self::new_unchecked(T::zero(), T::one())
116    }
117}
118impl<T> One for Rational<T>
119where
120    T: Signed,
121{
122    fn one() -> Self {
123        Self::new_unchecked(T::one(), T::one())
124    }
125}
126
127impl<T> Add for Rational<T>
128where
129    T: Signed,
130{
131    type Output = Self;
132    fn add(self, rhs: Self) -> Self::Output {
133        Self::new(self.num * rhs.den + self.den * rhs.num, self.den * rhs.den)
134    }
135}
136impl<T> Sub for Rational<T>
137where
138    T: Signed,
139{
140    type Output = Self;
141    fn sub(self, rhs: Self) -> Self::Output {
142        Self::new(self.num * rhs.den - self.den * rhs.num, self.den * rhs.den)
143    }
144}
145impl<T> Mul for Rational<T>
146where
147    T: Signed,
148{
149    type Output = Self;
150    fn mul(self, rhs: Self) -> Self::Output {
151        Self::new(self.num * rhs.num, self.den * rhs.den)
152    }
153}
154impl<T> Div for Rational<T>
155where
156    T: Signed,
157{
158    type Output = Self;
159    fn div(self, rhs: Self) -> Self::Output {
160        Self::new(self.num * rhs.den, self.den * rhs.num)
161    }
162}
163impl<T> Neg for Rational<T>
164where
165    T: Signed,
166{
167    type Output = Self;
168    fn neg(self) -> Self::Output {
169        Self::new_unchecked(-self.num, self.den)
170    }
171}
172impl<T> AddAssign for Rational<T>
173where
174    T: Signed,
175{
176    fn add_assign(&mut self, rhs: Self) {
177        *self = *self + rhs;
178    }
179}
180impl<T> SubAssign for Rational<T>
181where
182    T: Signed,
183{
184    fn sub_assign(&mut self, rhs: Self) {
185        *self = *self - rhs;
186    }
187}
188impl<T> MulAssign for Rational<T>
189where
190    T: Signed,
191{
192    fn mul_assign(&mut self, rhs: Self) {
193        *self = *self * rhs;
194    }
195}
196impl<T> DivAssign for Rational<T>
197where
198    T: Signed,
199{
200    fn div_assign(&mut self, rhs: Self) {
201        *self = *self / rhs;
202    }
203}
competitive/num/rational.rs

competitive/num/
rational.rs
