khive_fold/ordering/
mod.rs

1//! Deterministic ordering primitives for objective functions
2//!
3//! This module provides utilities for deterministic ordering of scored candidates,
4//! ensuring reproducible results across processes, architectures, and executions.
5//!
6//! # Key Components
7//!
8//! - [`HasId`]: Trait for candidates with stable UUID identifiers
9//! - [`canonical_f64`]/[`canonical_f32`]: Normalize floating-point values for comparison
10//! - [`cmp_desc_score_then_id`]: Deterministic comparator (f64 + Uuid) with UUID tie-breaking
11//! - [`ScoredEntry`]: Ord-implementing wrapper for heap operations, backed by [`DeterministicScore`]
12//! - [`QuantKey`]: Re-exported from `khive-score` — 8-byte packed sort key (i32 score + u32 ID prefix)
13//! - [`DeterministicScore`]: Re-exported from `khive-score` — i64 fixed-point score
14//! - [`Ranked`]: Re-exported from `khive-score` — score + generic `Ord` ID pair for heaps
15
16mod canonical;
17mod compare;
18mod has_id;
19mod scored_entry;
20
21pub use canonical::{canonical_f32, canonical_f64};
22pub use compare::{cmp_asc_score_then_id, cmp_desc_score_then_id};
23pub use has_id::HasId;
24pub use scored_entry::ScoredEntry;
25
26// Re-exports from khive-score
27pub use khive_score::QuantKey;
28pub use khive_score::{cmp_asc_then_id, cmp_desc_then_id, DeterministicScore, Ranked};
29
30#[cfg(test)]
31use canonical::{CANONICAL_NAN_F32, CANONICAL_NAN_F64};
32
33#[cfg(test)]
34mod tests {
35    use super::*;
36    use std::cmp::Ordering;
37    use uuid::Uuid;
38
39    // ------------------------------------------------------------------------
40    // Canonical Function Tests
41    // ------------------------------------------------------------------------
42
43    #[test]
44    fn test_canonical_f64_nan_variants() {
45        let nans = [
46            f64::NAN,
47            -f64::NAN,
48            f64::from_bits(0x7ff0_0000_0000_0001), // signaling NaN
49            f64::from_bits(0x7ff8_0000_0000_0001), // quiet NaN with payload
50            f64::from_bits(0xfff8_0000_0000_0001), // negative quiet NaN
51        ];
52
53        for nan in nans {
54            let canonical = canonical_f64(nan);
55            assert!(canonical.is_nan(), "Should still be NaN");
56            assert_eq!(
57                canonical.to_bits(),
58                CANONICAL_NAN_F64,
59                "NaN variant {:016x} should canonicalize to {:016x}",
60                nan.to_bits(),
61                CANONICAL_NAN_F64
62            );
63        }
64    }
65
66    #[test]
67    fn test_canonical_f64_zero() {
68        assert!(canonical_f64(-0.0).is_sign_positive());
69        assert_eq!(canonical_f64(-0.0), 0.0);
70        assert_eq!(canonical_f64(-0.0).to_bits(), 0u64);
71    }
72
73    #[test]
74    fn test_canonical_f64_preserves_normal() {
75        let values = [1.0, -1.0, 0.5, f64::MAX, f64::MIN_POSITIVE, f64::EPSILON];
76        for v in values {
77            assert_eq!(canonical_f64(v), v);
78            assert_eq!(canonical_f64(v).to_bits(), v.to_bits());
79        }
80    }
81
82    #[test]
83    fn test_canonical_f32_nan_variants() {
84        let nans = [
85            f32::NAN,
86            -f32::NAN,
87            f32::from_bits(0x7f80_0001), // signaling NaN
88            f32::from_bits(0x7fc0_0001), // quiet NaN with payload
89        ];
90
91        for nan in nans {
92            let canonical = canonical_f32(nan);
93            assert!(canonical.is_nan());
94            assert_eq!(canonical.to_bits(), CANONICAL_NAN_F32);
95        }
96    }
97
98    #[test]
99    fn test_canonical_f32_zero() {
100        assert!(canonical_f32(-0.0_f32).is_sign_positive());
101        assert_eq!(canonical_f32(-0.0_f32), 0.0_f32);
102    }
103
104    #[test]
105    fn test_canonical_idempotent() {
106        let values = [0.0, -0.0, 1.0, f64::NAN, f64::INFINITY, f64::NEG_INFINITY];
107        for v in values {
108            let once = canonical_f64(v);
109            let twice = canonical_f64(once);
110            assert_eq!(once.to_bits(), twice.to_bits());
111        }
112    }
113
114    // ------------------------------------------------------------------------
115    // Comparison Function Tests
116    // ------------------------------------------------------------------------
117
118    #[test]
119    fn test_descending_score_ordering() {
120        let id_a = Uuid::from_u128(1);
121        let id_b = Uuid::from_u128(2);
122
123        assert_eq!(
124            cmp_desc_score_then_id(0.9, id_a, 0.5, id_b),
125            Ordering::Less,
126            "Higher score should come first"
127        );
128        assert_eq!(
129            cmp_desc_score_then_id(0.5, id_a, 0.9, id_b),
130            Ordering::Greater,
131            "Lower score should come second"
132        );
133    }
134
135    #[test]
136    fn test_uuid_tie_breaking() {
137        let id_a = Uuid::from_u128(1);
138        let id_b = Uuid::from_u128(2);
139
140        assert_eq!(
141            cmp_desc_score_then_id(0.5, id_a, 0.5, id_b),
142            Ordering::Less,
143            "Lower UUID should come first on tie"
144        );
145        assert_eq!(
146            cmp_desc_score_then_id(0.5, id_b, 0.5, id_a),
147            Ordering::Greater,
148            "Higher UUID should come second on tie"
149        );
150    }
151
152    #[test]
153    fn test_nan_handling() {
154        let id_a = Uuid::from_u128(1);
155        let id_b = Uuid::from_u128(2);
156
157        assert_eq!(
158            cmp_desc_score_then_id(f64::NAN, id_a, 0.5, id_b),
159            Ordering::Greater,
160            "NaN should sort after normal values in descending"
161        );
162        assert_eq!(
163            cmp_desc_score_then_id(0.5, id_a, f64::NAN, id_b),
164            Ordering::Less,
165            "Normal value should sort before NaN in descending"
166        );
167        assert_eq!(
168            cmp_desc_score_then_id(f64::NAN, id_a, f64::NAN, id_b),
169            Ordering::Less,
170            "Two NaNs should use UUID tie-breaking"
171        );
172    }
173
174    #[test]
175    fn test_sorting_stability() {
176        let entries: Vec<(f64, Uuid)> = (0..100)
177            .map(|i| (0.5, Uuid::from_u128(i as u128)))
178            .collect();
179
180        let mut sorted1 = entries.clone();
181        let mut sorted2 = entries.clone();
182
183        sorted1.sort_by(|a, b| cmp_desc_score_then_id(a.0, a.1, b.0, b.1));
184        sorted2.sort_by(|a, b| cmp_desc_score_then_id(a.0, a.1, b.0, b.1));
185
186        assert_eq!(sorted1, sorted2, "Multiple sorts should produce same order");
187
188        for i in 0..99 {
189            assert!(sorted1[i].1 < sorted1[i + 1].1);
190        }
191    }
192
193    #[test]
194    fn test_ascending_variant() {
195        let id_a = Uuid::from_u128(1);
196        let id_b = Uuid::from_u128(2);
197
198        assert_eq!(
199            cmp_asc_score_then_id(0.3, id_a, 0.5, id_b),
200            Ordering::Less,
201            "Lower score should come first in ascending"
202        );
203        assert_eq!(
204            cmp_asc_score_then_id(0.5, id_a, 0.5, id_b),
205            Ordering::Less,
206            "Equal scores use UUID tie-breaking"
207        );
208    }
209
210    // ------------------------------------------------------------------------
211    // ScoredEntry Tests
212    // ------------------------------------------------------------------------
213
214    #[derive(Debug, Clone)]
215    #[allow(dead_code)]
216    struct TestCandidate {
217        id: Uuid,
218        value: i32,
219    }
220
221    impl HasId for TestCandidate {
222        fn id(&self) -> Uuid {
223            self.id
224        }
225    }
226
227    #[test]
228    fn test_scored_entry_ord() {
229        let a = TestCandidate {
230            id: Uuid::from_u128(1),
231            value: 10,
232        };
233        let b = TestCandidate {
234            id: Uuid::from_u128(2),
235            value: 20,
236        };
237
238        let entry_a = ScoredEntry::new(&a, 0.9, 0);
239        let entry_b = ScoredEntry::new(&b, 0.5, 1);
240
241        assert!(entry_a > entry_b);
242    }
243
244    #[test]
245    fn test_scored_entry_heap() {
246        use std::collections::BinaryHeap;
247
248        let candidates: Vec<TestCandidate> = (0..10i32)
249            .map(|i| TestCandidate {
250                id: Uuid::from_u128(i as u128),
251                value: i * 10,
252            })
253            .collect();
254
255        let mut heap: BinaryHeap<ScoredEntry<&TestCandidate>> = candidates
256            .iter()
257            .enumerate()
258            .map(|(i, c)| ScoredEntry::new(c, 0.5, i))
259            .collect();
260
261        let mut last_id = Uuid::nil();
262        while let Some(entry) = heap.pop() {
263            if last_id != Uuid::nil() {
264                assert!(entry.id() > last_id, "Should pop in UUID order");
265            }
266            last_id = entry.id();
267        }
268    }
269
270    #[test]
271    fn test_scored_entry_equality() {
272        let a = TestCandidate {
273            id: Uuid::from_u128(1),
274            value: 10,
275        };
276        let b = TestCandidate {
277            id: Uuid::from_u128(1),
278            value: 20,
279        };
280
281        let entry_a = ScoredEntry::new(&a, 0.5, 0);
282        let entry_b = ScoredEntry::new(&b, 0.5, 1);
283
284        assert_eq!(entry_a, entry_b);
285    }
286
287    #[test]
288    fn test_scored_entry_hash() {
289        use std::collections::HashSet;
290
291        let a = TestCandidate {
292            id: Uuid::from_u128(1),
293            value: 10,
294        };
295
296        let entry1 = ScoredEntry::new(&a, 0.5, 0);
297        let entry2 = ScoredEntry::new(&a, 0.5, 1);
298
299        let mut set = HashSet::new();
300        set.insert(entry1);
301        assert!(set.contains(&entry2));
302    }
303
304    // ------------------------------------------------------------------------
305    // QuantKey Tests (score's QuantKey: i32+u32 packed, NaN→0)
306    // ------------------------------------------------------------------------
307
308    #[test]
309    fn test_quant_key_precision() {
310        let a = QuantKey::new(0.123456, 1);
311        let b = QuantKey::new(0.123457, 2);
312        assert_ne!(
313            a.quantized_score(),
314            b.quantized_score(),
315            "1e-6 difference should be distinguishable"
316        );
317    }
318
319    #[test]
320    fn test_quant_key_rounding() {
321        let a = QuantKey::new(0.12345642, 1);
322        let b = QuantKey::new(0.12345647, 2);
323        assert_eq!(
324            a.quantized_score(),
325            b.quantized_score(),
326            "Sub-1e-6 differences should round same"
327        );
328    }
329
330    #[test]
331    fn test_quant_key_nan_maps_to_zero() {
332        let nan = QuantKey::new(f32::NAN, 1);
333        let zero = QuantKey::new(0.0, 1);
334        assert_eq!(
335            nan.quantized_score(),
336            zero.quantized_score(),
337            "NaN maps to 0 in score's QuantKey"
338        );
339    }
340
341    #[test]
342    fn test_quant_key_heap_order() {
343        use std::collections::BinaryHeap;
344
345        let mut heap: BinaryHeap<QuantKey> = BinaryHeap::new();
346        heap.push(QuantKey::new(0.95, 3));
347        heap.push(QuantKey::new(0.95, 1));
348        heap.push(QuantKey::new(0.95, 2));
349        heap.push(QuantKey::new(0.87, 4));
350
351        assert_eq!(heap.pop().unwrap().id_prefix(), 1);
352        assert_eq!(heap.pop().unwrap().id_prefix(), 2);
353        assert_eq!(heap.pop().unwrap().id_prefix(), 3);
354        assert_eq!(heap.pop().unwrap().id_prefix(), 4);
355    }
356
357    // ------------------------------------------------------------------------
358    // DeterministicScore Integration Tests
359    // ------------------------------------------------------------------------
360
361    #[test]
362    fn test_deterministic_score_roundtrip() {
363        let s = DeterministicScore::from_f64(0.75);
364        assert!((s.to_f64() - 0.75).abs() < 1e-9);
365    }
366
367    #[test]
368    fn test_deterministic_score_nan_maps_to_zero() {
369        let s = DeterministicScore::from_f64(f64::NAN);
370        assert_eq!(s, DeterministicScore::ZERO);
371    }
372
373    #[test]
374    fn test_ranked_heap_with_uuid_ids() {
375        use std::collections::BinaryHeap;
376
377        let mut heap: BinaryHeap<Ranked<Uuid>> = BinaryHeap::new();
378        heap.push(Ranked::new(
379            DeterministicScore::from_f64(0.9),
380            Uuid::from_u128(3),
381        ));
382        heap.push(Ranked::new(
383            DeterministicScore::from_f64(0.9),
384            Uuid::from_u128(1),
385        ));
386        heap.push(Ranked::new(
387            DeterministicScore::from_f64(0.9),
388            Uuid::from_u128(2),
389        ));
390        heap.push(Ranked::new(
391            DeterministicScore::from_f64(0.5),
392            Uuid::from_u128(4),
393        ));
394
395        // All 0.9 scores — lower UUID pops first
396        let first = heap.pop().unwrap();
397        assert_eq!(*first.id(), Uuid::from_u128(1));
398        let second = heap.pop().unwrap();
399        assert_eq!(*second.id(), Uuid::from_u128(2));
400        let third = heap.pop().unwrap();
401        assert_eq!(*third.id(), Uuid::from_u128(3));
402        // Then lower score
403        let fourth = heap.pop().unwrap();
404        assert_eq!(*fourth.id(), Uuid::from_u128(4));
405    }
406}
khive_fold/ordering/mod.rs

khive_fold/ordering/
mod.rs
