petgraph/
scored.rs

1use std::cmp::Ordering;
2
3/// `MinScored<K, T>` holds a score `K` and a scored object `T` in
4/// a pair for use with a `BinaryHeap`.
5///
6/// `MinScored` compares in reverse order by the score, so that we can
7/// use `BinaryHeap` as a min-heap to extract the score-value pair with the
8/// least score.
9///
10/// **Note:** `MinScored` implements a total order (`Ord`), so that it is
11/// possible to use float types as scores.
12#[derive(Copy, Clone, Debug)]
13pub struct MinScored<K, T>(pub K, pub T);
14
15impl<K: PartialOrd, T> PartialEq for MinScored<K, T> {
16    #[inline]
17    fn eq(&self, other: &MinScored<K, T>) -> bool {
18        self.cmp(other) == Ordering::Equal
19    }
20}
21
22impl<K: PartialOrd, T> Eq for MinScored<K, T> {}
23
24impl<K: PartialOrd, T> PartialOrd for MinScored<K, T> {
25    #[inline]
26    fn partial_cmp(&self, other: &MinScored<K, T>) -> Option<Ordering> {
27        Some(self.cmp(other))
28    }
29}
30
31impl<K: PartialOrd, T> Ord for MinScored<K, T> {
32    #[inline]
33    fn cmp(&self, other: &MinScored<K, T>) -> Ordering {
34        let a = &self.0;
35        let b = &other.0;
36        if a == b {
37            Ordering::Equal
38        } else if a < b {
39            Ordering::Greater
40        } else if a > b {
41            Ordering::Less
42        } else if a.ne(a) && b.ne(b) {
43            // these are the NaN cases
44            Ordering::Equal
45        } else if a.ne(a) {
46            // Order NaN less, so that it is last in the MinScore order
47            Ordering::Less
48        } else {
49            Ordering::Greater
50        }
51    }
52}
53
54#[derive(Copy, Clone, Debug)]
55pub struct MaxScored<K, T>(pub K, pub T);
56
57impl<K: PartialOrd, T> PartialEq for MaxScored<K, T> {
58    #[inline]
59    fn eq(&self, other: &MaxScored<K, T>) -> bool {
60        self.cmp(other) == Ordering::Equal
61    }
62}
63
64impl<K: PartialOrd, T> Eq for MaxScored<K, T> {}
65
66impl<K: PartialOrd, T> PartialOrd for MaxScored<K, T> {
67    #[inline]
68    fn partial_cmp(&self, other: &MaxScored<K, T>) -> Option<Ordering> {
69        Some(self.cmp(other))
70    }
71}
72
73impl<K: PartialOrd, T> Ord for MaxScored<K, T> {
74    #[inline]
75    fn cmp(&self, other: &MaxScored<K, T>) -> Ordering {
76        let a = &self.0;
77        let b = &other.0;
78        if a == b {
79            Ordering::Equal
80        } else if a < b {
81            Ordering::Less
82        } else if a > b {
83            Ordering::Greater
84        } else if a.ne(a) && b.ne(b) {
85            // these are the NaN cases
86            Ordering::Equal
87        } else if a.ne(a) {
88            Ordering::Less
89        } else {
90            Ordering::Greater
91        }
92    }
93}
petgraph/scored.rs

petgraph/
scored.rs
