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