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