1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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 {
            // these are the NaN cases
            if a != a && b != b {
                Ordering::Equal
            } else if a != a {
            // Order NaN less, so that it is last in the MinScore order
                Ordering::Less
            } else {
                Ordering::Greater
            }
        }
    }
}