khive_score/
comparator.rs

1//! Deterministic ranking with tie-breaking.
2
3use crate::DeterministicScore;
4use std::cmp::Ordering;
5
6/// Ranked item: score descending, ID ascending for ties.
7#[derive(Clone, Debug, Eq, PartialEq)]
8pub struct Ranked<T: Ord> {
9    score: DeterministicScore,
10    id: T,
11}
12
13impl<T: Ord> Ranked<T> {
14    #[inline]
15    pub fn new(score: DeterministicScore, id: T) -> Self {
16        Self { score, id }
17    }
18
19    #[inline]
20    pub fn score(&self) -> DeterministicScore {
21        self.score
22    }
23
24    #[inline]
25    pub fn id(&self) -> &T {
26        &self.id
27    }
28
29    #[inline]
30    pub fn into_id(self) -> T {
31        self.id
32    }
33
34    #[inline]
35    pub fn into_parts(self) -> (DeterministicScore, T) {
36        (self.score, self.id)
37    }
38}
39
40impl<T: Ord> Ord for Ranked<T> {
41    #[inline]
42    fn cmp(&self, other: &Self) -> Ordering {
43        self.score
44            .cmp(&other.score)
45            .then_with(|| other.id.cmp(&self.id))
46    }
47}
48
49impl<T: Ord> PartialOrd for Ranked<T> {
50    #[inline]
51    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
52        Some(self.cmp(other))
53    }
54}
55
56/// Compare scores descending, lower ID wins ties.
57#[inline(always)]
58pub fn cmp_desc_then_id<T: Ord>(
59    a_score: DeterministicScore,
60    a_id: &T,
61    b_score: DeterministicScore,
62    b_id: &T,
63) -> Ordering {
64    b_score.cmp(&a_score).then_with(|| a_id.cmp(b_id))
65}
66
67/// Compare scores ascending, lower ID wins ties.
68#[inline(always)]
69pub fn cmp_asc_then_id<T: Ord>(
70    a_score: DeterministicScore,
71    a_id: &T,
72    b_score: DeterministicScore,
73    b_id: &T,
74) -> Ordering {
75    a_score.cmp(&b_score).then_with(|| a_id.cmp(b_id))
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81    use std::collections::BinaryHeap;
82
83    #[test]
84    fn ranked_heap_determinism() {
85        let mut heap: BinaryHeap<Ranked<u64>> = BinaryHeap::new();
86        heap.push(Ranked::new(DeterministicScore::from_f64(0.95), 3));
87        heap.push(Ranked::new(DeterministicScore::from_f64(0.95), 1));
88        heap.push(Ranked::new(DeterministicScore::from_f64(0.95), 2));
89        heap.push(Ranked::new(DeterministicScore::from_f64(0.87), 4));
90
91        let results: Vec<_> = std::iter::from_fn(|| heap.pop()).collect();
92        assert_eq!(results[0].id(), &1);
93        assert_eq!(results[1].id(), &2);
94        assert_eq!(results[2].id(), &3);
95        assert_eq!(results[3].id(), &4);
96    }
97
98    #[test]
99    fn cmp_desc() {
100        let mut items = [
101            (DeterministicScore::from_f64(0.9), 2u64),
102            (DeterministicScore::from_f64(0.9), 1u64),
103            (DeterministicScore::from_f64(0.8), 3u64),
104        ];
105        items.sort_by(|(sa, ia), (sb, ib)| cmp_desc_then_id(*sa, ia, *sb, ib));
106        assert_eq!(items[0].1, 1);
107        assert_eq!(items[1].1, 2);
108        assert_eq!(items[2].1, 3);
109    }
110
111    #[test]
112    fn cmp_asc_then_id_tie_lower_id_wins() {
113        let score = DeterministicScore::from_f64(0.5);
114        let mut items = [(score, 3u64), (score, 1u64), (score, 2u64)];
115        items.sort_by(|(sa, ia), (sb, ib)| cmp_asc_then_id(*sa, ia, *sb, ib));
116        assert_eq!(items[0].1, 1);
117        assert_eq!(items[1].1, 2);
118        assert_eq!(items[2].1, 3);
119    }
120
121    #[test]
122    fn ranked_into_parts_returns_score_and_id() {
123        let score = DeterministicScore::from_f64(0.75);
124        let ranked = Ranked::new(score, 42u64);
125        let (s, id) = ranked.into_parts();
126        assert_eq!(s, score);
127        assert_eq!(id, 42u64);
128    }
129}
khive_score/comparator.rs

khive_score/
comparator.rs
