competitive/tools/
comparator.rs

1use std::cmp::Ordering;
2
3pub trait Comparator<T> {
4    fn compare(&mut self, a: &T, b: &T) -> Ordering;
5}
6
7impl<T, F> Comparator<T> for F
8where
9    F: FnMut(&T, &T) -> Ordering,
10{
11    fn compare(&mut self, a: &T, b: &T) -> Ordering {
12        (self)(a, b)
13    }
14}
15
16#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
17pub struct Less;
18impl<T> Comparator<T> for Less
19where
20    T: Ord,
21{
22    fn compare(&mut self, a: &T, b: &T) -> Ordering {
23        a.cmp(b)
24    }
25}
26
27#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
28pub struct Greater;
29impl<T> Comparator<T> for Greater
30where
31    T: Ord,
32{
33    fn compare(&mut self, a: &T, b: &T) -> Ordering {
34        b.cmp(a)
35    }
36}
37
38#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
39pub struct ByKey<F>(pub F);
40impl<T, F, K> Comparator<T> for ByKey<F>
41where
42    F: FnMut(&T) -> K,
43    K: Ord,
44{
45    fn compare(&mut self, a: &T, b: &T) -> Ordering {
46        (self.0)(a).cmp(&(self.0)(b))
47    }
48}
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53    use crate::tools::Xorshift;
54
55    #[test]
56    fn test_comparators() {
57        let mut rng = Xorshift::default();
58        for _ in 0..10_000 {
59            let a = rng.random(-100i32..=100);
60            let b = rng.random(-100i32..=100);
61            let mut cmp = |a: &i32, b: &i32| b.cmp(a);
62            assert_eq!(cmp.compare(&a, &b), b.cmp(&a));
63            assert_eq!(Less.compare(&a, &b), a.cmp(&b));
64            assert_eq!(Greater.compare(&a, &b), b.cmp(&a));
65            let divisor = rng.random(1..=100);
66            assert_eq!(
67                ByKey(|x: &i32| x.rem_euclid(divisor)).compare(&a, &b),
68                a.rem_euclid(divisor).cmp(&b.rem_euclid(divisor))
69            );
70        }
71    }
72}
competitive/tools/comparator.rs

competitive/tools/
comparator.rs
