1use core::ops::{Div, Rem};
2
3pub 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 /// ```
23 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 /// ```
48 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 /// ```
67 fn div_rem_euclid(&self, v: &Self) -> (Self, Self) {
68 (self.div_euclid(v), self.rem_euclid(v))
69 }
70}
71
72macro_rules! euclid_forward_impl {
73 ($($t:ty)*) => {$(
74 #[cfg(has_div_euclid)]
75 impl Euclid for $t {
76 #[inline]
77 fn div_euclid(&self, v: &$t) -> Self {
78 <$t>::div_euclid(*self, *v)
79 }
80
81 #[inline]
82 fn rem_euclid(&self, v: &$t) -> Self {
83 <$t>::rem_euclid(*self, *v)
84 }
85 }
86 )*}
87}
88
89macro_rules! euclid_int_impl {
90 ($($t:ty)*) => {$(
91 euclid_forward_impl!($t);
92
93 #[cfg(not(has_div_euclid))]
94 impl Euclid for $t {
95 #[inline]
96 fn div_euclid(&self, v: &$t) -> Self {
97 let q = self / v;
98 if self % v < 0 {
99 return if *v > 0 { q - 1 } else { q + 1 }
100 }
101 q
102 }
103
104 #[inline]
105 fn rem_euclid(&self, v: &$t) -> Self {
106 let r = self % v;
107 if r < 0 {
108 if *v < 0 {
109 r - v
110 } else {
111 r + v
112 }
113 } else {
114 r
115 }
116 }
117 }
118 )*}
119}
120
121macro_rules! euclid_uint_impl {
122 ($($t:ty)*) => {$(
123 euclid_forward_impl!($t);
124
125 #[cfg(not(has_div_euclid))]
126 impl Euclid for $t {
127 #[inline]
128 fn div_euclid(&self, v: &$t) -> Self {
129 self / v
130 }
131
132 #[inline]
133 fn rem_euclid(&self, v: &$t) -> Self {
134 self % v
135 }
136 }
137 )*}
138}
139
140euclid_int_impl!(isize i8 i16 i32 i64 i128);
141euclid_uint_impl!(usize u8 u16 u32 u64 u128);
142
143#[cfg(all(has_div_euclid, feature = "std"))]
144euclid_forward_impl!(f32 f64);
145
146#[cfg(not(all(has_div_euclid, feature = "std")))]
147impl Euclid for f32 {
148 #[inline]
149 fn div_euclid(&self, v: &f32) -> f32 {
150 let q = <f32 as crate::float::FloatCore>::trunc(self / v);
151 if self % v < 0.0 {
152 return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
153 }
154 q
155 }
156
157 #[inline]
158 fn rem_euclid(&self, v: &f32) -> f32 {
159 let r = self % v;
160 if r < 0.0 {
161 r + <f32 as crate::float::FloatCore>::abs(*v)
162 } else {
163 r
164 }
165 }
166}
167
168#[cfg(not(all(has_div_euclid, feature = "std")))]
169impl Euclid for f64 {
170 #[inline]
171 fn div_euclid(&self, v: &f64) -> f64 {
172 let q = <f64 as crate::float::FloatCore>::trunc(self / v);
173 if self % v < 0.0 {
174 return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
175 }
176 q
177 }
178
179 #[inline]
180 fn rem_euclid(&self, v: &f64) -> f64 {
181 let r = self % v;
182 if r < 0.0 {
183 r + <f64 as crate::float::FloatCore>::abs(*v)
184 } else {
185 r
186 }
187 }
188}
189
190pub trait CheckedEuclid: Euclid {
191 /// Performs euclid division that returns `None` instead of panicking on division by zero
192 /// and instead of wrapping around on underflow and overflow.
193 fn checked_div_euclid(&self, v: &Self) -> Option<Self>;
194
195 /// Finds the euclid remainder of dividing two numbers, checking for underflow, overflow and
196 /// division by zero. If any of that happens, `None` is returned.
197 fn checked_rem_euclid(&self, v: &Self) -> Option<Self>;
198
199 /// Returns both the quotient and remainder from checked Euclidean division.
200 ///
201 /// By default, it internally calls both `CheckedEuclid::checked_div_euclid` and `CheckedEuclid::checked_rem_euclid`,
202 /// but it can be overridden in order to implement some optimization.
203 /// # Examples
204 ///
205 /// ```
206 /// # use num_traits::CheckedEuclid;
207 /// let x = 5u8;
208 /// let y = 3u8;
209 ///
210 /// let div = CheckedEuclid::checked_div_euclid(&x, &y);
211 /// let rem = CheckedEuclid::checked_rem_euclid(&x, &y);
212 ///
213 /// assert_eq!(Some((div.unwrap(), rem.unwrap())), CheckedEuclid::checked_div_rem_euclid(&x, &y));
214 /// ```
215 fn checked_div_rem_euclid(&self, v: &Self) -> Option<(Self, Self)> {
216 Some((self.checked_div_euclid(v)?, self.checked_rem_euclid(v)?))
217 }
218}
219
220macro_rules! checked_euclid_forward_impl {
221 ($($t:ty)*) => {$(
222 #[cfg(has_div_euclid)]
223 impl CheckedEuclid for $t {
224 #[inline]
225 fn checked_div_euclid(&self, v: &$t) -> Option<Self> {
226 <$t>::checked_div_euclid(*self, *v)
227 }
228
229 #[inline]
230 fn checked_rem_euclid(&self, v: &$t) -> Option<Self> {
231 <$t>::checked_rem_euclid(*self, *v)
232 }
233 }
234 )*}
235}
236
237macro_rules! checked_euclid_int_impl {
238 ($($t:ty)*) => {$(
239 checked_euclid_forward_impl!($t);
240
241 #[cfg(not(has_div_euclid))]
242 impl CheckedEuclid for $t {
243 #[inline]
244 fn checked_div_euclid(&self, v: &$t) -> Option<$t> {
245 if *v == 0 || (*self == Self::min_value() && *v == -1) {
246 None
247 } else {
248 Some(Euclid::div_euclid(self, v))
249 }
250 }
251
252 #[inline]
253 fn checked_rem_euclid(&self, v: &$t) -> Option<$t> {
254 if *v == 0 || (*self == Self::min_value() && *v == -1) {
255 None
256 } else {
257 Some(Euclid::rem_euclid(self, v))
258 }
259 }
260 }
261 )*}
262}
263
264macro_rules! checked_euclid_uint_impl {
265 ($($t:ty)*) => {$(
266 checked_euclid_forward_impl!($t);
267
268 #[cfg(not(has_div_euclid))]
269 impl CheckedEuclid for $t {
270 #[inline]
271 fn checked_div_euclid(&self, v: &$t) -> Option<$t> {
272 if *v == 0 {
273 None
274 } else {
275 Some(Euclid::div_euclid(self, v))
276 }
277 }
278
279 #[inline]
280 fn checked_rem_euclid(&self, v: &$t) -> Option<$t> {
281 if *v == 0 {
282 None
283 } else {
284 Some(Euclid::rem_euclid(self, v))
285 }
286 }
287 }
288 )*}
289}
290
291checked_euclid_int_impl!(isize i8 i16 i32 i64 i128);
292checked_euclid_uint_impl!(usize u8 u16 u32 u64 u128);
293
294#[cfg(test)]
295mod tests {
296 use super::*;
297
298 #[test]
299 fn euclid_unsigned() {
300 macro_rules! test_euclid {
301 ($($t:ident)+) => {
302 $(
303 {
304 let x: $t = 10;
305 let y: $t = 3;
306 let div = Euclid::div_euclid(&x, &y);
307 let rem = Euclid::rem_euclid(&x, &y);
308 assert_eq!(div, 3);
309 assert_eq!(rem, 1);
310 assert_eq!((div, rem), Euclid::div_rem_euclid(&x, &y));
311 }
312 )+
313 };
314 }
315
316 test_euclid!(usize u8 u16 u32 u64);
317 }
318
319 #[test]
320 fn euclid_signed() {
321 macro_rules! test_euclid {
322 ($($t:ident)+) => {
323 $(
324 {
325 let x: $t = 10;
326 let y: $t = -3;
327 assert_eq!(Euclid::div_euclid(&x, &y), -3);
328 assert_eq!(Euclid::div_euclid(&-x, &y), 4);
329 assert_eq!(Euclid::rem_euclid(&x, &y), 1);
330 assert_eq!(Euclid::rem_euclid(&-x, &y), 2);
331 assert_eq!((Euclid::div_euclid(&x, &y), Euclid::rem_euclid(&x, &y)), Euclid::div_rem_euclid(&x, &y));
332 let x: $t = $t::min_value() + 1;
333 let y: $t = -1;
334 assert_eq!(Euclid::div_euclid(&x, &y), $t::max_value());
335 }
336 )+
337 };
338 }
339
340 test_euclid!(isize i8 i16 i32 i64 i128);
341 }
342
343 #[test]
344 fn euclid_float() {
345 macro_rules! test_euclid {
346 ($($t:ident)+) => {
347 $(
348 {
349 let x: $t = 12.1;
350 let y: $t = 3.2;
351 assert!(Euclid::div_euclid(&x, &y) * y + Euclid::rem_euclid(&x, &y) - x
352 <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
353 assert!(Euclid::div_euclid(&x, &-y) * -y + Euclid::rem_euclid(&x, &-y) - x
354 <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
355 assert!(Euclid::div_euclid(&-x, &y) * y + Euclid::rem_euclid(&-x, &y) + x
356 <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
357 assert!(Euclid::div_euclid(&-x, &-y) * -y + Euclid::rem_euclid(&-x, &-y) + x
358 <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
359 assert_eq!((Euclid::div_euclid(&x, &y), Euclid::rem_euclid(&x, &y)), Euclid::div_rem_euclid(&x, &y));
360 }
361 )+
362 };
363 }
364
365 test_euclid!(f32 f64);
366 }
367
368 #[test]
369 fn euclid_checked() {
370 macro_rules! test_euclid_checked {
371 ($($t:ident)+) => {
372 $(
373 {
374 assert_eq!(CheckedEuclid::checked_div_euclid(&$t::min_value(), &-1), None);
375 assert_eq!(CheckedEuclid::checked_rem_euclid(&$t::min_value(), &-1), None);
376 assert_eq!(CheckedEuclid::checked_div_euclid(&1, &0), None);
377 assert_eq!(CheckedEuclid::checked_rem_euclid(&1, &0), None);
378 }
379 )+
380 };
381 }
382
383 test_euclid_checked!(isize i8 i16 i32 i64 i128);
384 }
385}
386