| use std::cmp::Ordering; |
| |
| /// `MinScored<K, T>` holds a score `K` and a scored object `T` in |
| /// a pair for use with a `BinaryHeap`. |
| /// |
| /// `MinScored` compares in reverse order by the score, so that we can |
| /// use `BinaryHeap` as a min-heap to extract the score-value pair with the |
| /// least score. |
| /// |
| /// **Note:** `MinScored` implements a total order (`Ord`), so that it is |
| /// possible to use float types as scores. |
| #[derive(Copy, Clone, Debug)] |
| pub struct MinScored<K, T>(pub K, pub T); |
| |
| impl<K: PartialOrd, T> PartialEq for MinScored<K, T> { |
| #[inline] |
| fn eq(&self, other: &MinScored<K, T>) -> bool { |
| self.cmp(other) == Ordering::Equal |
| } |
| } |
| |
| impl<K: PartialOrd, T> Eq for MinScored<K, T> {} |
| |
| impl<K: PartialOrd, T> PartialOrd for MinScored<K, T> { |
| #[inline] |
| fn partial_cmp(&self, other: &MinScored<K, T>) -> Option<Ordering> { |
| Some(self.cmp(other)) |
| } |
| } |
| |
| impl<K: PartialOrd, T> Ord for MinScored<K, T> { |
| #[inline] |
| fn cmp(&self, other: &MinScored<K, T>) -> Ordering { |
| let a = &self.0; |
| let b = &other.0; |
| if a == b { |
| Ordering::Equal |
| } else if a < b { |
| Ordering::Greater |
| } else if a > b { |
| Ordering::Less |
| } else if a.ne(a) && b.ne(b) { |
| // these are the NaN cases |
| Ordering::Equal |
| } else if a.ne(a) { |
| // Order NaN less, so that it is last in the MinScore order |
| Ordering::Less |
| } else { |
| Ordering::Greater |
| } |
| } |
| } |