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