khive_score/
comparator.rs

1//! Deterministic ranking with tie-breaking.
2
3use crate::DeterministicScore;
4use std::cmp::Ordering;
5
6/// Max-heap ranking item: higher score wins and lower ID breaks ties.
7///
8/// Ordinary vector sorting is ascending; see
9/// `crates/khive-score/docs/api/aggregation-and-ranking.md`.
10#[derive(Clone, Debug, Eq, PartialEq)]
11pub struct Ranked<T: Ord> {
12    score: DeterministicScore,
13    id: T,
14}
15
16impl<T: Ord> Ranked<T> {
17    /// Construct a `Ranked` item from a score and a tie-breaking ID.
18    #[inline]
19    pub fn new(score: DeterministicScore, id: T) -> Self {
20        Self { score, id }
21    }
22
23    /// Return the score component.
24    #[inline]
25    pub fn score(&self) -> DeterministicScore {
26        self.score
27    }
28
29    /// Return a reference to the tie-breaking ID.
30    #[inline]
31    pub fn id(&self) -> &T {
32        &self.id
33    }
34
35    /// Consume `self` and return the ID.
36    #[inline]
37    pub fn into_id(self) -> T {
38        self.id
39    }
40
41    /// Consume `self` and return `(score, id)`.
42    #[inline]
43    pub fn into_parts(self) -> (DeterministicScore, T) {
44        (self.score, self.id)
45    }
46}
47
48impl<T: Ord> Ord for Ranked<T> {
49    #[inline]
50    fn cmp(&self, other: &Self) -> Ordering {
51        self.score
52            .cmp(&other.score)
53            .then_with(|| other.id.cmp(&self.id))
54    }
55}
56
57impl<T: Ord> PartialOrd for Ranked<T> {
58    #[inline]
59    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
60        Some(self.cmp(other))
61    }
62}
63
64/// Compare scores descending, lower ID wins ties.
65#[inline(always)]
66pub fn cmp_desc_then_id<T: Ord>(
67    a_score: DeterministicScore,
68    a_id: &T,
69    b_score: DeterministicScore,
70    b_id: &T,
71) -> Ordering {
72    b_score.cmp(&a_score).then_with(|| a_id.cmp(b_id))
73}
74
75/// Compare scores ascending, lower ID wins ties.
76#[inline(always)]
77pub fn cmp_asc_then_id<T: Ord>(
78    a_score: DeterministicScore,
79    a_id: &T,
80    b_score: DeterministicScore,
81    b_id: &T,
82) -> Ordering {
83    a_score.cmp(&b_score).then_with(|| a_id.cmp(b_id))
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89    use std::collections::BinaryHeap;
90
91    #[test]
92    fn ranked_heap_determinism() {
93        let mut heap: BinaryHeap<Ranked<u64>> = BinaryHeap::new();
94        heap.push(Ranked::new(DeterministicScore::from_f64(0.95), 3));
95        heap.push(Ranked::new(DeterministicScore::from_f64(0.95), 1));
96        heap.push(Ranked::new(DeterministicScore::from_f64(0.95), 2));
97        heap.push(Ranked::new(DeterministicScore::from_f64(0.87), 4));
98
99        let results: Vec<_> = std::iter::from_fn(|| heap.pop()).collect();
100        assert_eq!(results[0].id(), &1);
101        assert_eq!(results[1].id(), &2);
102        assert_eq!(results[2].id(), &3);
103        assert_eq!(results[3].id(), &4);
104    }
105
106    #[test]
107    fn cmp_desc() {
108        let mut items = [
109            (DeterministicScore::from_f64(0.9), 2u64),
110            (DeterministicScore::from_f64(0.9), 1u64),
111            (DeterministicScore::from_f64(0.8), 3u64),
112        ];
113        items.sort_by(|(sa, ia), (sb, ib)| cmp_desc_then_id(*sa, ia, *sb, ib));
114        assert_eq!(items[0].1, 1);
115        assert_eq!(items[1].1, 2);
116        assert_eq!(items[2].1, 3);
117    }
118
119    #[test]
120    fn cmp_asc_then_id_tie_lower_id_wins() {
121        let score = DeterministicScore::from_f64(0.5);
122        let mut items = [(score, 3u64), (score, 1u64), (score, 2u64)];
123        items.sort_by(|(sa, ia), (sb, ib)| cmp_asc_then_id(*sa, ia, *sb, ib));
124        assert_eq!(items[0].1, 1);
125        assert_eq!(items[1].1, 2);
126        assert_eq!(items[2].1, 3);
127    }
128
129    #[test]
130    fn ranked_into_parts_returns_score_and_id() {
131        let score = DeterministicScore::from_f64(0.75);
132        let ranked = Ranked::new(score, 42u64);
133        let (s, id) = ranked.into_parts();
134        assert_eq!(s, score);
135        assert_eq!(id, 42u64);
136    }
137
138    /// `BinaryHeap<Ranked<_>>` must pop best (highest score) first.
139    #[test]
140    fn ranked_heap_pops_highest_score_first() {
141        use std::collections::BinaryHeap;
142        let mut heap = BinaryHeap::new();
143        heap.push(Ranked::new(DeterministicScore::from_f64(0.3), 3u64));
144        heap.push(Ranked::new(DeterministicScore::from_f64(0.9), 1u64));
145        heap.push(Ranked::new(DeterministicScore::from_f64(0.5), 2u64));
146
147        let first = heap.pop().unwrap();
148        assert_eq!(first.score(), DeterministicScore::from_f64(0.9));
149        assert_eq!(first.id(), &1u64);
150    }
151
152    /// `Vec::sort` is ascending; ranking order requires `cmp_desc_then_id`.
153    #[test]
154    fn ranked_vec_sort_is_ascending_not_ranking_order() {
155        let mut items = [
156            Ranked::new(DeterministicScore::from_f64(0.9), 1u64),
157            Ranked::new(DeterministicScore::from_f64(0.3), 3u64),
158            Ranked::new(DeterministicScore::from_f64(0.5), 2u64),
159        ];
160        items.sort();
161        // sort() gives ascending (lowest score first) because Ord is max-heap-adapted.
162        assert_eq!(items[0].score(), DeterministicScore::from_f64(0.3));
163        assert_eq!(items[2].score(), DeterministicScore::from_f64(0.9));
164    }
165
166    /// To get descending (ranking) order, use `cmp_desc_then_id`.
167    #[test]
168    fn cmp_desc_then_id_gives_descending_order() {
169        let mut items: Vec<(DeterministicScore, u64)> = vec![
170            (DeterministicScore::from_f64(0.3), 3),
171            (DeterministicScore::from_f64(0.9), 1),
172            (DeterministicScore::from_f64(0.5), 2),
173        ];
174        items.sort_unstable_by(|(sa, ia), (sb, ib)| cmp_desc_then_id(*sa, ia, *sb, ib));
175        assert_eq!(items[0].1, 1); // 0.9 first
176        assert_eq!(items[1].1, 2); // 0.5 second
177        assert_eq!(items[2].1, 3); // 0.3 last
178    }
179}
khive_score/comparator.rs

khive_score/
comparator.rs
