1 use 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)]
13 pub struct MinScored<K, T>(pub K, pub T);
14 
15 impl<K: PartialOrd, T> PartialEq for MinScored<K, T> {
16     #[inline]
eq(&self, other: &MinScored<K, T>) -> bool17     fn eq(&self, other: &MinScored<K, T>) -> bool {
18         self.cmp(other) == Ordering::Equal
19     }
20 }
21 
22 impl<K: PartialOrd, T> Eq for MinScored<K, T> {}
23 
24 impl<K: PartialOrd, T> PartialOrd for MinScored<K, T> {
25     #[inline]
partial_cmp(&self, other: &MinScored<K, T>) -> Option<Ordering>26     fn partial_cmp(&self, other: &MinScored<K, T>) -> Option<Ordering> {
27         Some(self.cmp(other))
28     }
29 }
30 
31 impl<K: PartialOrd, T> Ord for MinScored<K, T> {
32     #[inline]
cmp(&self, other: &MinScored<K, T>) -> Ordering33     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