1 use core::ops::{Div, Rem};
2 
3 pub trait Euclid: Sized + Div<Self, Output = Self> + Rem<Self, Output = Self> {
4     /// Calculates Euclidean division, the matching method for `rem_euclid`.
5     ///
6     /// This computes the integer `n` such that
7     /// `self = n * v + self.rem_euclid(v)`.
8     /// In other words, the result is `self / v` rounded to the integer `n`
9     /// such that `self >= n * v`.
10     ///
11     /// # Examples
12     ///
13     /// ```
14     /// use num_traits::Euclid;
15     ///
16     /// let a: i32 = 7;
17     /// let b: i32 = 4;
18     /// assert_eq!(Euclid::div_euclid(&a, &b), 1); // 7 > 4 * 1
19     /// assert_eq!(Euclid::div_euclid(&-a, &b), -2); // -7 >= 4 * -2
20     /// assert_eq!(Euclid::div_euclid(&a, &-b), -1); // 7 >= -4 * -1
21     /// assert_eq!(Euclid::div_euclid(&-a, &-b), 2); // -7 >= -4 * 2
22     /// ```
div_euclid(&self, v: &Self) -> Self23     fn div_euclid(&self, v: &Self) -> Self;
24 
25     /// Calculates the least nonnegative remainder of `self (mod v)`.
26     ///
27     /// In particular, the return value `r` satisfies `0.0 <= r < v.abs()` in
28     /// most cases. However, due to a floating point round-off error it can
29     /// result in `r == v.abs()`, violating the mathematical definition, if
30     /// `self` is much smaller than `v.abs()` in magnitude and `self < 0.0`.
31     /// This result is not an element of the function's codomain, but it is the
32     /// closest floating point number in the real numbers and thus fulfills the
33     /// property `self == self.div_euclid(v) * v + self.rem_euclid(v)`
34     /// approximatively.
35     ///
36     /// # Examples
37     ///
38     /// ```
39     /// use num_traits::Euclid;
40     ///
41     /// let a: i32 = 7;
42     /// let b: i32 = 4;
43     /// assert_eq!(Euclid::rem_euclid(&a, &b), 3);
44     /// assert_eq!(Euclid::rem_euclid(&-a, &b), 1);
45     /// assert_eq!(Euclid::rem_euclid(&a, &-b), 3);
46     /// assert_eq!(Euclid::rem_euclid(&-a, &-b), 1);
47     /// ```
rem_euclid(&self, v: &Self) -> Self48     fn rem_euclid(&self, v: &Self) -> Self;
49 
50     /// Returns both the quotient and remainder from Euclidean division.
51     ///
52     /// By default, it internally calls both `Euclid::div_euclid` and `Euclid::rem_euclid`,
53     /// but it can be overridden in order to implement some optimization.
54     ///
55     /// # Examples
56     ///
57     /// ```
58     /// # use num_traits::Euclid;
59     /// let x = 5u8;
60     /// let y = 3u8;
61     ///
62     /// let div = Euclid::div_euclid(&x, &y);
63     /// let rem = Euclid::rem_euclid(&x, &y);
64     ///
65     /// assert_eq!((div, rem), Euclid::div_rem_euclid(&x, &y));
66     /// ```
div_rem_euclid(&self, v: &Self) -> (Self, Self)67     fn div_rem_euclid(&self, v: &Self) -> (Self, Self) {
68         (self.div_euclid(v), self.rem_euclid(v))
69     }
70 }
71 
72 macro_rules! euclid_forward_impl {
73     ($($t:ty)*) => {$(
74         impl Euclid for $t {
75             #[inline]
76             fn div_euclid(&self, v: &$t) -> Self {
77                 <$t>::div_euclid(*self, *v)
78             }
79 
80             #[inline]
81             fn rem_euclid(&self, v: &$t) -> Self {
82                 <$t>::rem_euclid(*self, *v)
83             }
84         }
85     )*}
86 }
87 
88 euclid_forward_impl!(isize i8 i16 i32 i64 i128);
89 euclid_forward_impl!(usize u8 u16 u32 u64 u128);
90 
91 #[cfg(feature = "std")]
92 euclid_forward_impl!(f32 f64);
93 
94 #[cfg(not(feature = "std"))]
95 impl Euclid for f32 {
96     #[inline]
div_euclid(&self, v: &f32) -> f3297     fn div_euclid(&self, v: &f32) -> f32 {
98         let q = <f32 as crate::float::FloatCore>::trunc(self / v);
99         if self % v < 0.0 {
100             return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
101         }
102         q
103     }
104 
105     #[inline]
rem_euclid(&self, v: &f32) -> f32106     fn rem_euclid(&self, v: &f32) -> f32 {
107         let r = self % v;
108         if r < 0.0 {
109             r + <f32 as crate::float::FloatCore>::abs(*v)
110         } else {
111             r
112         }
113     }
114 }
115 
116 #[cfg(not(feature = "std"))]
117 impl Euclid for f64 {
118     #[inline]
div_euclid(&self, v: &f64) -> f64119     fn div_euclid(&self, v: &f64) -> f64 {
120         let q = <f64 as crate::float::FloatCore>::trunc(self / v);
121         if self % v < 0.0 {
122             return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
123         }
124         q
125     }
126 
127     #[inline]
rem_euclid(&self, v: &f64) -> f64128     fn rem_euclid(&self, v: &f64) -> f64 {
129         let r = self % v;
130         if r < 0.0 {
131             r + <f64 as crate::float::FloatCore>::abs(*v)
132         } else {
133             r
134         }
135     }
136 }
137 
138 pub trait CheckedEuclid: Euclid {
139     /// Performs euclid division that returns `None` instead of panicking on division by zero
140     /// and instead of wrapping around on underflow and overflow.
checked_div_euclid(&self, v: &Self) -> Option<Self>141     fn checked_div_euclid(&self, v: &Self) -> Option<Self>;
142 
143     /// Finds the euclid remainder of dividing two numbers, checking for underflow, overflow and
144     /// division by zero. If any of that happens, `None` is returned.
checked_rem_euclid(&self, v: &Self) -> Option<Self>145     fn checked_rem_euclid(&self, v: &Self) -> Option<Self>;
146 
147     /// Returns both the quotient and remainder from checked Euclidean division.
148     ///
149     /// By default, it internally calls both `CheckedEuclid::checked_div_euclid` and `CheckedEuclid::checked_rem_euclid`,
150     /// but it can be overridden in order to implement some optimization.
151     /// # Examples
152     ///
153     /// ```
154     /// # use num_traits::CheckedEuclid;
155     /// let x = 5u8;
156     /// let y = 3u8;
157     ///
158     /// let div = CheckedEuclid::checked_div_euclid(&x, &y);
159     /// let rem = CheckedEuclid::checked_rem_euclid(&x, &y);
160     ///
161     /// assert_eq!(Some((div.unwrap(), rem.unwrap())), CheckedEuclid::checked_div_rem_euclid(&x, &y));
162     /// ```
checked_div_rem_euclid(&self, v: &Self) -> Option<(Self, Self)>163     fn checked_div_rem_euclid(&self, v: &Self) -> Option<(Self, Self)> {
164         Some((self.checked_div_euclid(v)?, self.checked_rem_euclid(v)?))
165     }
166 }
167 
168 macro_rules! checked_euclid_forward_impl {
169     ($($t:ty)*) => {$(
170         impl CheckedEuclid for $t {
171             #[inline]
172             fn checked_div_euclid(&self, v: &$t) -> Option<Self> {
173                 <$t>::checked_div_euclid(*self, *v)
174             }
175 
176             #[inline]
177             fn checked_rem_euclid(&self, v: &$t) -> Option<Self> {
178                 <$t>::checked_rem_euclid(*self, *v)
179             }
180         }
181     )*}
182 }
183 
184 checked_euclid_forward_impl!(isize i8 i16 i32 i64 i128);
185 checked_euclid_forward_impl!(usize u8 u16 u32 u64 u128);
186 
187 #[cfg(test)]
188 mod tests {
189     use super::*;
190 
191     #[test]
euclid_unsigned()192     fn euclid_unsigned() {
193         macro_rules! test_euclid {
194             ($($t:ident)+) => {
195                 $(
196                     {
197                         let x: $t = 10;
198                         let y: $t = 3;
199                         let div = Euclid::div_euclid(&x, &y);
200                         let rem = Euclid::rem_euclid(&x, &y);
201                         assert_eq!(div, 3);
202                         assert_eq!(rem, 1);
203                         assert_eq!((div, rem), Euclid::div_rem_euclid(&x, &y));
204                     }
205                 )+
206             };
207         }
208 
209         test_euclid!(usize u8 u16 u32 u64);
210     }
211 
212     #[test]
euclid_signed()213     fn euclid_signed() {
214         macro_rules! test_euclid {
215             ($($t:ident)+) => {
216                 $(
217                     {
218                         let x: $t = 10;
219                         let y: $t = -3;
220                         assert_eq!(Euclid::div_euclid(&x, &y), -3);
221                         assert_eq!(Euclid::div_euclid(&-x, &y), 4);
222                         assert_eq!(Euclid::rem_euclid(&x, &y), 1);
223                         assert_eq!(Euclid::rem_euclid(&-x, &y), 2);
224                         assert_eq!((Euclid::div_euclid(&x, &y), Euclid::rem_euclid(&x, &y)), Euclid::div_rem_euclid(&x, &y));
225                         let x: $t = $t::min_value() + 1;
226                         let y: $t = -1;
227                         assert_eq!(Euclid::div_euclid(&x, &y), $t::max_value());
228                     }
229                 )+
230             };
231         }
232 
233         test_euclid!(isize i8 i16 i32 i64 i128);
234     }
235 
236     #[test]
euclid_float()237     fn euclid_float() {
238         macro_rules! test_euclid {
239             ($($t:ident)+) => {
240                 $(
241                     {
242                         let x: $t = 12.1;
243                         let y: $t = 3.2;
244                         assert!(Euclid::div_euclid(&x, &y) * y + Euclid::rem_euclid(&x, &y) - x
245                         <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
246                         assert!(Euclid::div_euclid(&x, &-y) * -y + Euclid::rem_euclid(&x, &-y) - x
247                         <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
248                         assert!(Euclid::div_euclid(&-x, &y) * y + Euclid::rem_euclid(&-x, &y) + x
249                         <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
250                         assert!(Euclid::div_euclid(&-x, &-y) * -y + Euclid::rem_euclid(&-x, &-y) + x
251                         <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
252                         assert_eq!((Euclid::div_euclid(&x, &y), Euclid::rem_euclid(&x, &y)), Euclid::div_rem_euclid(&x, &y));
253                     }
254                 )+
255             };
256         }
257 
258         test_euclid!(f32 f64);
259     }
260 
261     #[test]
euclid_checked()262     fn euclid_checked() {
263         macro_rules! test_euclid_checked {
264             ($($t:ident)+) => {
265                 $(
266                     {
267                         assert_eq!(CheckedEuclid::checked_div_euclid(&$t::min_value(), &-1), None);
268                         assert_eq!(CheckedEuclid::checked_rem_euclid(&$t::min_value(), &-1), None);
269                         assert_eq!(CheckedEuclid::checked_div_euclid(&1, &0), None);
270                         assert_eq!(CheckedEuclid::checked_rem_euclid(&1, &0), None);
271                     }
272                 )+
273             };
274         }
275 
276         test_euclid_checked!(isize i8 i16 i32 i64 i128);
277     }
278 }
279