competitive/geometry/
approx.rs

1use std::cmp::Ordering;
2
3pub trait ApproxOrd {
4    fn approx_eq(&self, other: &Self) -> bool;
5    fn approx_cmp(&self, other: &Self) -> Ordering;
6}
7macro_rules! impl_approx_zero_for_int {
8    ($($t:ty)*) => {
9        $(impl ApproxOrd for $t {
10            fn approx_eq(&self, other: &Self) -> bool {
11                self.eq(other)
12            }
13            fn approx_cmp(&self, other: &Self) -> Ordering {
14                self.cmp(other)
15            }
16        })*
17    };
18}
19impl_approx_zero_for_int!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
20impl ApproxOrd for f32 {
21    fn approx_eq(&self, other: &Self) -> bool {
22        const EPS_F32: f32 = 1e-8;
23        (self - other).abs() < EPS_F32
24    }
25    fn approx_cmp(&self, other: &Self) -> Ordering {
26        if self.approx_eq(other) {
27            Ordering::Equal
28        } else {
29            let mut left = self.to_bits() as i32;
30            let mut right = other.to_bits() as i32;
31            left ^= (((left >> 31) as u32) >> 1) as i32;
32            right ^= (((right >> 31) as u32) >> 1) as i32;
33            left.cmp(&right)
34        }
35    }
36}
37impl ApproxOrd for f64 {
38    fn approx_eq(&self, other: &Self) -> bool {
39        const EPS_F64: f64 = 1e-8;
40        (self - other).abs() < EPS_F64
41    }
42    fn approx_cmp(&self, other: &Self) -> Ordering {
43        if self.approx_eq(other) {
44            Ordering::Equal
45        } else {
46            let mut left = self.to_bits() as i64;
47            let mut right = other.to_bits() as i64;
48            left ^= (((left >> 63) as u64) >> 1) as i64;
49            right ^= (((right >> 63) as u64) >> 1) as i64;
50            left.cmp(&right)
51        }
52    }
53}
54
55#[derive(Debug, Default, Clone, Copy)]
56#[repr(transparent)]
57pub struct Approx<T>(pub T)
58where
59    T: ApproxOrd;
60impl<T> PartialEq for Approx<T>
61where
62    T: ApproxOrd,
63{
64    fn eq(&self, other: &Self) -> bool {
65        self.0.approx_eq(&other.0)
66    }
67}
68impl<T> Eq for Approx<T> where T: ApproxOrd {}
69impl<T> PartialOrd for Approx<T>
70where
71    T: ApproxOrd,
72{
73    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
74        Some(self.cmp(other))
75    }
76}
77impl<T> Ord for Approx<T>
78where
79    T: ApproxOrd,
80{
81    fn cmp(&self, other: &Self) -> Ordering {
82        self.0.approx_cmp(&other.0)
83    }
84}
competitive/geometry/approx.rs

competitive/geometry/
approx.rs
