Skip to main content

ftui_widgets/
height_predictor.rs

1//! Bayesian height prediction with conformal bounds for virtualized lists.
2//!
3//! Predicts unseen row heights to pre-allocate scroll space and avoid
4//! scroll jumps when actual heights are measured lazily. Consumed by
5//! [`crate::virtualized::VariableHeightsFenwick`], [`crate::virtualized::Virtualized::with_height_prediction`],
6//! and [`crate::virtualized::VirtualizedListState::with_predictor`] (grouped by
7//! [`crate::virtualized::RenderItem::category`]).
8//!
9//! # Mathematical Model
10//!
11//! ## Bayesian Online Estimation
12//!
13//! Maintains a Normal-Normal conjugate model per item category:
14//!
15//! ```text
16//! Prior:     μ ~ N(μ₀, σ₀²/κ₀)
17//! Likelihood: h_i ~ N(μ, σ²)
18//! Posterior:  μ | data ~ N(μ_n, σ²/κ_n)
19//!
20//! where:
21//!   κ_n = κ₀ + n
22//!   μ_n = (κ₀·μ₀ + n·x̄) / κ_n
23//!   σ²  estimated via running variance (Welford's algorithm)
24//! ```
25//!
26//! ## Conformal Prediction Bounds
27//!
28//! Given a calibration set of (predicted, actual) residuals, the conformal
29//! interval is:
30//!
31//! ```text
32//! [μ_n - q_{1-α/2}, μ_n + q_{1-α/2}]
33//! ```
34//!
35//! where `q` is the empirical quantile of |residuals|. This provides
36//! distribution-free coverage: P(h ∈ interval) ≥ 1 - α.
37//!
38//! # Failure Modes
39//!
40//! | Condition | Behavior | Rationale |
41//! |-----------|----------|-----------|
42//! | No measurements | Return default height | Cold start fallback |
43//! | n = 1 | Wide interval (use prior σ) | Insufficient data |
44//! | All same height | σ → 0, interval collapses | Homogeneous data |
45//! | Actual > bound | Adjust + record violation | Expected at rate α |
46
47use std::collections::VecDeque;
48
49/// Configuration for the height predictor.
50#[derive(Debug, Clone)]
51pub struct PredictorConfig {
52    /// Default height when no data is available.
53    pub default_height: u16,
54    /// Prior strength κ₀ (higher = more trust in default). Default: 2.0.
55    pub prior_strength: f64,
56    /// Prior mean μ₀ (usually same as default_height).
57    pub prior_mean: f64,
58    /// Prior variance estimate. Default: 4.0.
59    pub prior_variance: f64,
60    /// Conformal coverage level (1 - α). Default: 0.90.
61    pub coverage: f64,
62    /// Max calibration residuals to keep. Default: 200.
63    pub calibration_window: usize,
64}
65
66impl Default for PredictorConfig {
67    fn default() -> Self {
68        Self {
69            default_height: 1,
70            prior_strength: 2.0,
71            prior_mean: 1.0,
72            prior_variance: 4.0,
73            coverage: 0.90,
74            calibration_window: 200,
75        }
76    }
77}
78
79/// Running statistics using Welford's online algorithm.
80#[derive(Debug, Clone)]
81struct WelfordStats {
82    n: u64,
83    mean: f64,
84    m2: f64, // Sum of squared deviations
85}
86
87impl WelfordStats {
88    fn new() -> Self {
89        Self {
90            n: 0,
91            mean: 0.0,
92            m2: 0.0,
93        }
94    }
95
96    fn update(&mut self, x: f64) {
97        self.n += 1;
98        let delta = x - self.mean;
99        self.mean += delta / self.n as f64;
100        let delta2 = x - self.mean;
101        self.m2 += delta * delta2;
102    }
103
104    fn variance(&self) -> f64 {
105        if self.n < 2 {
106            return f64::MAX;
107        }
108        self.m2 / (self.n - 1) as f64
109    }
110}
111
112/// Per-category prediction state.
113#[derive(Debug, Clone)]
114struct CategoryState {
115    /// Welford running stats for observed heights.
116    welford: WelfordStats,
117    /// Posterior mean μ_n.
118    posterior_mean: f64,
119    /// Posterior κ_n.
120    posterior_kappa: f64,
121    /// Calibration residuals |predicted - actual|.
122    residuals: VecDeque<f64>,
123}
124
125/// A prediction with conformal bounds.
126#[derive(Debug, Clone, Copy)]
127pub struct HeightPrediction {
128    /// Point prediction (posterior mean, rounded).
129    pub predicted: u16,
130    /// Lower conformal bound.
131    pub lower: u16,
132    /// Upper conformal bound.
133    pub upper: u16,
134    /// Number of observations for this category.
135    pub observations: u64,
136}
137
138/// Observations and interval violations accumulated by a height predictor.
139#[derive(Debug, Clone, Copy, PartialEq)]
140pub struct PredictorStats {
141    /// Total measured heights, across all categories.
142    pub measurements: u64,
143    /// Measurements outside their pre-observation interval, excluding each
144    /// category's first observation.
145    pub violations: u64,
146    /// Violations divided by measurements, or zero before any observation.
147    pub violation_rate: f64,
148    /// Number of registered categories, including the default category zero.
149    pub categories: usize,
150}
151
152/// Bayesian height predictor with conformal bounds.
153#[derive(Debug, Clone)]
154pub struct HeightPredictor {
155    config: PredictorConfig,
156    /// Per-category states. Key is category index (0 = default).
157    categories: Vec<CategoryState>,
158    /// Total measurements across all categories.
159    total_measurements: u64,
160    /// Total bound violations.
161    total_violations: u64,
162}
163
164impl HeightPredictor {
165    /// Create a new predictor with default config.
166    pub fn new(config: PredictorConfig) -> Self {
167        // Start with one default category.
168        let default_cat = CategoryState {
169            welford: WelfordStats::new(),
170            posterior_mean: config.prior_mean,
171            posterior_kappa: config.prior_strength,
172            residuals: VecDeque::new(),
173        };
174        Self {
175            config,
176            categories: vec![default_cat],
177            total_measurements: 0,
178            total_violations: 0,
179        }
180    }
181
182    /// Register a new category. Returns the category id.
183    pub fn register_category(&mut self) -> usize {
184        let id = self.categories.len();
185        self.categories.push(CategoryState {
186            welford: WelfordStats::new(),
187            posterior_mean: self.config.prior_mean,
188            posterior_kappa: self.config.prior_strength,
189            residuals: VecDeque::new(),
190        });
191        id
192    }
193
194    /// Predict height for an item in the given category.
195    pub fn predict(&self, category: usize) -> HeightPrediction {
196        let cat = match self.categories.get(category) {
197            Some(c) => c,
198            None => return self.cold_prediction(),
199        };
200
201        if cat.welford.n == 0 {
202            return self.cold_prediction();
203        }
204
205        let mu = cat.posterior_mean;
206        let predicted = mu.round().max(1.0) as u16;
207
208        // Conformal bounds from calibration residuals.
209        let (lower, upper) = self.conformal_bounds(cat, mu);
210
211        HeightPrediction {
212            predicted,
213            lower,
214            upper,
215            observations: cat.welford.n,
216        }
217    }
218
219    /// Record an actual measured height, updating the model.
220    /// Returns whether the measurement was within the predicted bounds.
221    pub fn observe(&mut self, category: usize, actual_height: u16) -> bool {
222        // Ensure category exists.
223        while self.categories.len() <= category {
224            self.register_category();
225        }
226
227        let prediction = self.predict(category);
228        let within_bounds = actual_height >= prediction.lower && actual_height <= prediction.upper;
229
230        self.total_measurements += 1;
231        if !within_bounds && prediction.observations > 0 {
232            self.total_violations += 1;
233        }
234
235        let cat = &mut self.categories[category];
236        let h = actual_height as f64;
237
238        // Record calibration residual.
239        let residual = (cat.posterior_mean - h).abs();
240        cat.residuals.push_back(residual);
241        if cat.residuals.len() > self.config.calibration_window {
242            cat.residuals.pop_front();
243        }
244
245        // Update Welford stats.
246        cat.welford.update(h);
247
248        // Update posterior: μ_n = (κ₀·μ₀ + n·x̄) / κ_n.
249        // For non-default categories (category > 0), use empirical Bayes anchoring
250        // on the category's sample mean so multi-line categories are not pulled
251        // toward category 0's single-line prior mean.
252        let n = cat.welford.n as f64;
253        let kappa_0 = self.config.prior_strength;
254        let mu_0 = if category == 0 {
255            self.config.prior_mean
256        } else {
257            cat.welford.mean
258        };
259        cat.posterior_kappa = kappa_0 + n;
260        cat.posterior_mean = (kappa_0 * mu_0 + n * cat.welford.mean) / cat.posterior_kappa;
261
262        within_bounds
263    }
264
265    /// Cold-start prediction when no data is available.
266    fn cold_prediction(&self) -> HeightPrediction {
267        let d = self.config.default_height;
268        let margin = (self.config.prior_variance.sqrt() * 2.0).ceil() as u16;
269        HeightPrediction {
270            predicted: d,
271            lower: d.saturating_sub(margin),
272            upper: d.saturating_add(margin),
273            observations: 0,
274        }
275    }
276
277    /// Compute conformal bounds from calibration residuals.
278    fn conformal_bounds(&self, cat: &CategoryState, mu: f64) -> (u16, u16) {
279        if cat.residuals.is_empty() {
280            // Fallback: use prior variance.
281            let margin = (self.config.prior_variance.sqrt() * 2.0).ceil() as u16;
282            let predicted = mu.round().max(1.0) as u16;
283            return (
284                predicted.saturating_sub(margin),
285                predicted.saturating_add(margin),
286            );
287        }
288
289        // Sort residuals to find quantile.
290        let mut sorted: Vec<f64> = cat.residuals.iter().copied().collect();
291        sorted.sort_unstable_by(f64::total_cmp);
292
293        let alpha = 1.0 - self.config.coverage;
294        let n = sorted.len() as f64;
295        let quantile_idx = ((1.0 - alpha) * (n + 1.0)).ceil() as usize;
296        let quantile_idx = quantile_idx.min(sorted.len()).saturating_sub(1);
297        let q = sorted[quantile_idx];
298
299        let lower = (mu - q).max(1.0).floor() as u16;
300        let upper = (mu + q).ceil().max(1.0) as u16;
301
302        (lower, upper)
303    }
304
305    /// Get the posterior mean for a category.
306    pub fn posterior_mean(&self, category: usize) -> f64 {
307        self.categories
308            .get(category)
309            .map(|c| c.posterior_mean)
310            .unwrap_or(self.config.prior_mean)
311    }
312
313    /// Get the posterior variance for a category.
314    pub fn posterior_variance(&self, category: usize) -> f64 {
315        self.categories
316            .get(category)
317            .map(|c| {
318                let sigma_sq = if c.welford.n < 2 {
319                    self.config.prior_variance
320                } else {
321                    c.welford.variance()
322                };
323                sigma_sq / c.posterior_kappa
324            })
325            .unwrap_or(self.config.prior_variance)
326    }
327
328    /// Total measurements observed.
329    pub fn total_measurements(&self) -> u64 {
330        self.total_measurements
331    }
332
333    /// Snapshot the predictor's observed statistics.
334    #[must_use]
335    pub fn stats(&self) -> PredictorStats {
336        PredictorStats {
337            measurements: self.total_measurements,
338            violations: self.total_violations,
339            violation_rate: self.violation_rate(),
340            categories: self.categories.len(),
341        }
342    }
343
344    /// Total bound violations.
345    pub fn total_violations(&self) -> u64 {
346        self.total_violations
347    }
348
349    /// Empirical violation rate.
350    pub fn violation_rate(&self) -> f64 {
351        if self.total_measurements == 0 {
352            return 0.0;
353        }
354        self.total_violations as f64 / self.total_measurements as f64
355    }
356
357    /// Number of categories.
358    pub fn category_count(&self) -> usize {
359        self.categories.len()
360    }
361
362    /// Number of observations for a category.
363    pub fn category_observations(&self, category: usize) -> u64 {
364        self.categories
365            .get(category)
366            .map(|c| c.welford.n)
367            .unwrap_or(0)
368    }
369}
370
371impl Default for HeightPredictor {
372    fn default() -> Self {
373        Self::new(PredictorConfig::default())
374    }
375}
376
377#[cfg(test)]
378mod tests {
379    use super::*;
380
381    // ─── Posterior update tests ────────────────────────────────────
382
383    #[test]
384    fn unit_posterior_update() {
385        let config = PredictorConfig {
386            prior_mean: 2.0,
387            prior_strength: 1.0,
388            prior_variance: 4.0,
389            ..Default::default()
390        };
391        let mut pred = HeightPredictor::new(config);
392
393        // Prior: μ=2.0, κ=1.
394        assert!((pred.posterior_mean(0) - 2.0).abs() < 1e-10);
395
396        // Observe height 4.
397        pred.observe(0, 4);
398        // κ_1 = 1 + 1 = 2, μ_1 = (1*2 + 1*4) / 2 = 3.0
399        assert!((pred.posterior_mean(0) - 3.0).abs() < 1e-10);
400
401        // Observe another height 4.
402        pred.observe(0, 4);
403        // κ_2 = 1 + 2 = 3, x̄ = 4, μ_2 = (1*2 + 2*4) / 3 = 10/3 ≈ 3.333
404        assert!((pred.posterior_mean(0) - 10.0 / 3.0).abs() < 1e-10);
405    }
406
407    #[test]
408    fn unit_posterior_variance_decreases() {
409        let mut pred = HeightPredictor::new(PredictorConfig {
410            prior_variance: 4.0,
411            ..Default::default()
412        });
413
414        let var_0 = pred.posterior_variance(0);
415        assert!(var_0 > 0.0, "prior variance should be positive");
416
417        // Feed noisy data so Welford variance is non-zero.
418        for i in 0..10 {
419            pred.observe(0, if i % 2 == 0 { 2 } else { 4 });
420        }
421        let var_10 = pred.posterior_variance(0);
422
423        for i in 0..90 {
424            pred.observe(0, if i % 2 == 0 { 2 } else { 4 });
425        }
426        let var_100 = pred.posterior_variance(0);
427
428        // With noisy data, posterior variance σ²/κ_n decreases as κ_n grows.
429        assert!(
430            var_10 < var_0,
431            "variance should decrease: {var_10} >= {var_0}"
432        );
433        assert!(
434            var_100 < var_10,
435            "variance should decrease: {var_100} >= {var_10}"
436        );
437    }
438
439    // ─── Conformal bounds tests ───────────────────────────────────
440
441    #[test]
442    fn unit_conformal_bounds() {
443        let config = PredictorConfig {
444            coverage: 0.90,
445            prior_mean: 3.0,
446            prior_strength: 1.0,
447            ..Default::default()
448        };
449        let mut pred = HeightPredictor::new(config);
450
451        // Feed consistent data.
452        for _ in 0..50 {
453            pred.observe(0, 3);
454        }
455
456        let p = pred.predict(0);
457        // With all observations at 3, residuals should be near 0.
458        // Bounds should be tight around 3.
459        assert_eq!(p.predicted, 3);
460        assert!(p.lower <= 3);
461        assert!(p.upper >= 3);
462    }
463
464    #[test]
465    fn conformal_bounds_widen_with_noise() {
466        let config = PredictorConfig {
467            coverage: 0.90,
468            prior_mean: 5.0,
469            prior_strength: 1.0,
470            ..Default::default()
471        };
472        let mut pred = HeightPredictor::new(config);
473
474        // Consistent data → tight bounds.
475        for _ in 0..50 {
476            pred.observe(0, 5);
477        }
478        let tight = pred.predict(0);
479
480        // Reset with noisy data.
481        let mut pred2 = HeightPredictor::new(PredictorConfig {
482            coverage: 0.90,
483            prior_mean: 5.0,
484            prior_strength: 1.0,
485            ..Default::default()
486        });
487        let mut seed: u64 = 0xABCD_1234_5678_9ABC;
488        for _ in 0..50 {
489            seed = seed
490                .wrapping_mul(6364136223846793005)
491                .wrapping_add(1442695040888963407);
492            let h = 3 + (seed >> 62) as u16; // heights 3..6
493            pred2.observe(0, h);
494        }
495        let wide = pred2.predict(0);
496
497        assert!(
498            (wide.upper - wide.lower) >= (tight.upper - tight.lower),
499            "noisy data should produce wider bounds"
500        );
501    }
502
503    // ─── Coverage property test ───────────────────────────────────
504
505    #[test]
506    fn property_coverage() {
507        let alpha = 0.10;
508        let config = PredictorConfig {
509            coverage: 1.0 - alpha,
510            prior_mean: 3.0,
511            prior_strength: 2.0,
512            prior_variance: 4.0,
513            calibration_window: 100,
514            ..Default::default()
515        };
516        let mut pred = HeightPredictor::new(config);
517
518        // Warm up with calibration data.
519        let mut seed: u64 = 0xDEAD_BEEF_CAFE_0001;
520        for _ in 0..100 {
521            seed = seed
522                .wrapping_mul(6364136223846793005)
523                .wrapping_add(1442695040888963407);
524            let h = 2 + (seed >> 62) as u16; // heights 2..5
525            pred.observe(0, h);
526        }
527
528        // Now check coverage on new data.
529        let mut violations = 0u32;
530        let test_n = 200;
531        for _ in 0..test_n {
532            seed = seed
533                .wrapping_mul(6364136223846793005)
534                .wrapping_add(1442695040888963407);
535            let h = 2 + (seed >> 62) as u16;
536            let within = pred.observe(0, h);
537            if !within {
538                violations += 1;
539            }
540        }
541
542        let viol_rate = violations as f64 / test_n as f64;
543        // Empirical violation rate should be approximately ≤ α.
544        // Allow generous tolerance for finite sample + discrete heights.
545        assert!(
546            viol_rate <= alpha + 0.15,
547            "violation rate {viol_rate} exceeds α + tolerance ({alpha} + 0.15)"
548        );
549    }
550
551    // ─── Scroll stability test ────────────────────────────────────
552
553    #[test]
554    fn e2e_scroll_stability() {
555        let mut pred = HeightPredictor::new(PredictorConfig {
556            prior_mean: 1.0,
557            prior_strength: 2.0,
558            default_height: 1,
559            coverage: 0.90,
560            ..Default::default()
561        });
562
563        // All items are height 1 (most common TUI case).
564        let mut corrections = 0u32;
565        for _ in 0..500 {
566            let within = pred.observe(0, 1);
567            if !within {
568                corrections += 1;
569            }
570        }
571
572        // With homogeneous heights, should converge quickly with zero corrections
573        // after warmup.
574        let p = pred.predict(0);
575        assert_eq!(p.predicted, 1);
576        assert!(corrections < 10, "too many corrections: {corrections}");
577    }
578
579    // ─── Multiple categories ──────────────────────────────────────
580
581    #[test]
582    fn categories_are_independent() {
583        let mut pred = HeightPredictor::default();
584        let cat_a = 0;
585        let cat_b = pred.register_category();
586
587        // Feed different data to each (cat 0 at 3, cat 1 at 9).
588        for _ in 0..50 {
589            pred.observe(cat_a, 3);
590            pred.observe(cat_b, 9);
591        }
592
593        let pa = pred.predict(cat_a);
594        let pb = pred.predict(cat_b);
595
596        assert_eq!(pa.predicted, 3);
597        assert_eq!(pb.predicted, 9);
598        assert!((pred.posterior_mean(cat_a) - 3.0).abs() < 0.2);
599        assert!((pred.posterior_mean(cat_b) - 9.0).abs() < 0.5);
600    }
601
602    // ─── Cold start ───────────────────────────────────────────────
603
604    #[test]
605    fn cold_prediction_uses_default() {
606        let pred = HeightPredictor::new(PredictorConfig {
607            default_height: 2,
608            prior_variance: 1.0,
609            ..Default::default()
610        });
611        let p = pred.predict(0);
612        assert_eq!(p.predicted, 2);
613        assert_eq!(p.observations, 0);
614    }
615
616    // ─── Determinism ──────────────────────────────────────────────
617
618    #[test]
619    fn deterministic_under_same_observations() {
620        let run = || {
621            let mut pred = HeightPredictor::default();
622            let observations = [1, 2, 1, 3, 1, 2, 1, 1, 4, 1];
623            for &h in &observations {
624                pred.observe(0, h);
625            }
626            (pred.predict(0).predicted, pred.posterior_mean(0))
627        };
628
629        let (p1, m1) = run();
630        let (p2, m2) = run();
631        assert_eq!(p1, p2);
632        assert!((m1 - m2).abs() < 1e-15);
633    }
634
635    // ─── Performance ──────────────────────────────────────────────
636
637    #[test]
638    fn perf_prediction_overhead() {
639        let mut pred = HeightPredictor::default();
640
641        // Warm up.
642        for _ in 0..100 {
643            pred.observe(0, 2);
644        }
645
646        let start = std::time::Instant::now();
647        let mut _sink = 0u16;
648        for _ in 0..100_000 {
649            _sink = _sink.wrapping_add(pred.predict(0).predicted);
650        }
651        let elapsed = start.elapsed();
652        let per_prediction = elapsed / 100_000;
653
654        // Must be < 5μs per prediction (generous for debug builds).
655        assert!(
656            per_prediction < std::time::Duration::from_micros(5),
657            "prediction too slow: {per_prediction:?}"
658        );
659    }
660
661    // ─── Violation tracking ───────────────────────────────────────
662
663    #[test]
664    fn violation_tracking() {
665        let mut pred = HeightPredictor::new(PredictorConfig {
666            prior_mean: 5.0,
667            prior_strength: 100.0, // strong prior
668            default_height: 5,
669            coverage: 0.95,
670            ..Default::default()
671        });
672
673        // Warm up with height=5.
674        for _ in 0..50 {
675            pred.observe(0, 5);
676        }
677
678        // Sudden jump to height=20 should violate bounds.
679        let within = pred.observe(0, 20);
680        assert!(!within, "extreme outlier should violate bounds");
681        assert!(pred.total_violations() > 0);
682    }
683
684    // ── PredictorConfig defaults ─────────────────────────────────
685
686    #[test]
687    fn config_default_values() {
688        let config = PredictorConfig::default();
689        assert_eq!(config.default_height, 1);
690        assert!((config.prior_strength - 2.0).abs() < f64::EPSILON);
691        assert!((config.prior_mean - 1.0).abs() < f64::EPSILON);
692        assert!((config.prior_variance - 4.0).abs() < f64::EPSILON);
693        assert!((config.coverage - 0.90).abs() < f64::EPSILON);
694        assert_eq!(config.calibration_window, 200);
695    }
696
697    // ── HeightPredictor::default ─────────────────────────────────
698
699    #[test]
700    fn default_predictor_has_one_category() {
701        let pred = HeightPredictor::default();
702        assert_eq!(pred.category_count(), 1);
703        assert_eq!(pred.total_measurements(), 0);
704        assert_eq!(pred.total_violations(), 0);
705        assert!((pred.violation_rate() - 0.0).abs() < f64::EPSILON);
706        assert_eq!(
707            pred.stats(),
708            PredictorStats {
709                measurements: 0,
710                violations: 0,
711                violation_rate: 0.0,
712                categories: 1,
713            }
714        );
715    }
716
717    // ── Predict unknown category ─────────────────────────────────
718
719    #[test]
720    fn predict_unknown_category_returns_cold() {
721        let pred = HeightPredictor::default();
722        let p = pred.predict(999);
723        assert_eq!(p.predicted, pred.config.default_height);
724        assert_eq!(p.observations, 0);
725    }
726
727    // ── Observe auto-creates categories ──────────────────────────
728
729    #[test]
730    fn observe_auto_creates_categories() {
731        let mut pred = HeightPredictor::default();
732        assert_eq!(pred.category_count(), 1);
733        pred.observe(3, 5);
734        // Should auto-create categories 1, 2, 3
735        assert_eq!(pred.category_count(), 4);
736        assert_eq!(pred.category_observations(3), 1);
737    }
738
739    // ── Violation rate ───────────────────────────────────────────
740
741    #[test]
742    fn violation_rate_empty() {
743        let pred = HeightPredictor::default();
744        assert!((pred.violation_rate() - 0.0).abs() < f64::EPSILON);
745    }
746
747    #[test]
748    fn violation_rate_computation() {
749        let mut pred = HeightPredictor::new(PredictorConfig {
750            prior_mean: 5.0,
751            prior_strength: 100.0,
752            default_height: 5,
753            coverage: 0.95,
754            ..Default::default()
755        });
756        // Warm up so bounds are tight
757        for _ in 0..50 {
758            pred.observe(0, 5);
759        }
760        // 10 normal observations
761        for _ in 0..10 {
762            pred.observe(0, 5);
763        }
764        let before_violations = pred.total_violations();
765        // 1 extreme outlier
766        pred.observe(0, 100);
767        let after_violations = pred.total_violations();
768        assert!(after_violations > before_violations);
769        assert!(pred.violation_rate() > 0.0);
770    }
771
772    // ── Category accessors ───────────────────────────────────────
773
774    #[test]
775    fn category_observations_returns_zero_for_unknown() {
776        let pred = HeightPredictor::default();
777        assert_eq!(pred.category_observations(999), 0);
778    }
779
780    #[test]
781    fn category_observations_tracks_counts() {
782        let mut pred = HeightPredictor::default();
783        pred.observe(0, 3);
784        pred.observe(0, 4);
785        pred.observe(0, 5);
786        assert_eq!(pred.category_observations(0), 3);
787    }
788
789    // ── Posterior accessors with unknown category ─────────────────
790
791    #[test]
792    fn posterior_mean_unknown_returns_prior() {
793        let pred = HeightPredictor::default();
794        assert!((pred.posterior_mean(999) - pred.config.prior_mean).abs() < f64::EPSILON);
795    }
796
797    #[test]
798    fn posterior_variance_unknown_returns_prior() {
799        let pred = HeightPredictor::default();
800        assert!((pred.posterior_variance(999) - pred.config.prior_variance).abs() < f64::EPSILON);
801    }
802
803    // ── Register category ────────────────────────────────────────
804
805    #[test]
806    fn register_category_returns_sequential_ids() {
807        let mut pred = HeightPredictor::default();
808        let id1 = pred.register_category();
809        let id2 = pred.register_category();
810        assert_eq!(id1, 1);
811        assert_eq!(id2, 2);
812        assert_eq!(pred.category_count(), 3);
813    }
814
815    // ── Observe returns within_bounds ─────────────────────────────
816
817    #[test]
818    fn observe_returns_true_for_consistent_data() {
819        let mut pred = HeightPredictor::new(PredictorConfig {
820            prior_mean: 3.0,
821            prior_strength: 1.0,
822            ..Default::default()
823        });
824        // Warm up
825        for _ in 0..20 {
826            pred.observe(0, 3);
827        }
828        // Same value should be within bounds
829        assert!(pred.observe(0, 3));
830    }
831
832    // ── Total measurements ───────────────────────────────────────
833
834    #[test]
835    fn total_measurements_increments() {
836        let mut pred = HeightPredictor::default();
837        for i in 0..7 {
838            pred.observe(0, (i + 1) as u16);
839        }
840        assert_eq!(pred.total_measurements(), 7);
841    }
842
843    // ── HeightPrediction bounds ordering ─────────────────────────
844
845    #[test]
846    fn prediction_lower_le_predicted_le_upper() {
847        let mut pred = HeightPredictor::default();
848        for _ in 0..30 {
849            pred.observe(0, 3);
850        }
851        let p = pred.predict(0);
852        assert!(p.lower <= p.predicted);
853        assert!(p.predicted <= p.upper);
854    }
855
856    // ── Edge-case tests (bd-l9r1a) ──────────────────────────
857
858    #[test]
859    fn observe_height_zero() {
860        let mut pred = HeightPredictor::default();
861        pred.observe(0, 0);
862        let p = pred.predict(0);
863        // predicted is max(mu.round(), 1.0) so at least 1
864        assert!(p.predicted >= 1);
865    }
866
867    #[test]
868    fn observe_height_max_u16() {
869        let mut pred = HeightPredictor::default();
870        pred.observe(0, u16::MAX);
871        let p = pred.predict(0);
872        assert!(p.predicted > 0);
873        assert!(p.observations == 1);
874    }
875
876    #[test]
877    fn cold_prediction_zero_variance() {
878        let pred = HeightPredictor::new(PredictorConfig {
879            default_height: 5,
880            prior_variance: 0.0,
881            ..Default::default()
882        });
883        let p = pred.predict(0);
884        assert_eq!(p.predicted, 5);
885        // margin = ceil(sqrt(0.0) * 2.0) = 0
886        assert_eq!(p.lower, 5);
887        assert_eq!(p.upper, 5);
888    }
889
890    #[test]
891    fn cold_prediction_large_variance() {
892        let pred = HeightPredictor::new(PredictorConfig {
893            default_height: 1,
894            prior_variance: 10000.0,
895            ..Default::default()
896        });
897        let p = pred.predict(0);
898        assert_eq!(p.predicted, 1);
899        // margin = ceil(sqrt(10000) * 2) = ceil(200) = 200
900        assert_eq!(p.lower, 0); // 1.saturating_sub(200) = 0
901    }
902
903    #[test]
904    fn coverage_zero() {
905        let mut pred = HeightPredictor::new(PredictorConfig {
906            coverage: 0.0,
907            prior_mean: 3.0,
908            prior_strength: 1.0,
909            ..Default::default()
910        });
911        for _ in 0..20 {
912            pred.observe(0, 3);
913        }
914        // alpha = 1.0, quantile_idx → 0
915        let p = pred.predict(0);
916        assert!(p.predicted > 0);
917    }
918
919    #[test]
920    fn coverage_one() {
921        let mut pred = HeightPredictor::new(PredictorConfig {
922            coverage: 1.0,
923            prior_mean: 3.0,
924            prior_strength: 1.0,
925            ..Default::default()
926        });
927        for _ in 0..20 {
928            pred.observe(0, 3);
929        }
930        for _ in 0..5 {
931            pred.observe(0, 10);
932        }
933        // alpha = 0.0, quantile_idx → max residual
934        let p = pred.predict(0);
935        assert!(p.lower <= p.predicted);
936        assert!(p.predicted <= p.upper);
937    }
938
939    #[test]
940    fn calibration_window_one() {
941        let mut pred = HeightPredictor::new(PredictorConfig {
942            calibration_window: 1,
943            prior_mean: 3.0,
944            prior_strength: 1.0,
945            ..Default::default()
946        });
947        for _ in 0..10 {
948            pred.observe(0, 3);
949        }
950        let p = pred.predict(0);
951        assert!(p.predicted > 0);
952        assert!(p.lower <= p.predicted);
953    }
954
955    #[test]
956    fn single_observation_uses_wide_bounds() {
957        let mut pred = HeightPredictor::new(PredictorConfig {
958            prior_mean: 5.0,
959            prior_strength: 1.0,
960            prior_variance: 4.0,
961            ..Default::default()
962        });
963        pred.observe(0, 5);
964        let p = pred.predict(0);
965        assert_eq!(p.observations, 1);
966        // With only 1 residual, bounds come from that single residual
967        assert!(p.lower <= p.predicted);
968        assert!(p.predicted <= p.upper);
969    }
970
971    #[test]
972    fn predictor_config_clone_and_debug() {
973        let config = PredictorConfig::default();
974        let cloned = config.clone();
975        assert_eq!(cloned.default_height, config.default_height);
976        let dbg = format!("{:?}", config);
977        assert!(dbg.contains("PredictorConfig"));
978    }
979
980    #[test]
981    fn height_prediction_copy_and_debug() {
982        let p = HeightPrediction {
983            predicted: 3,
984            lower: 1,
985            upper: 5,
986            observations: 10,
987        };
988        let p2 = p; // Copy
989        assert_eq!(p.predicted, p2.predicted);
990        assert_eq!(p.lower, p2.lower);
991        assert_eq!(p.upper, p2.upper);
992        assert_eq!(p.observations, p2.observations);
993        let dbg = format!("{:?}", p);
994        assert!(dbg.contains("HeightPrediction"));
995    }
996
997    #[test]
998    fn height_prediction_clone() {
999        fn assert_clone<T: Clone>() {}
1000        assert_clone::<HeightPrediction>();
1001        let p = HeightPrediction {
1002            predicted: 2,
1003            lower: 1,
1004            upper: 4,
1005            observations: 5,
1006        };
1007        let cloned = p; // Copy implies Clone; clippy forbids clone_on_copy
1008        assert_eq!(cloned.predicted, 2);
1009    }
1010
1011    #[test]
1012    fn predictor_clone_independence() {
1013        let mut pred = HeightPredictor::default();
1014        pred.observe(0, 5);
1015        pred.observe(0, 5);
1016        let mut cloned = pred.clone();
1017        cloned.observe(0, 100);
1018        // Original should be unaffected
1019        assert_eq!(pred.total_measurements(), 2);
1020        assert_eq!(cloned.total_measurements(), 3);
1021    }
1022
1023    #[test]
1024    fn predictor_debug() {
1025        let pred = HeightPredictor::default();
1026        let dbg = format!("{:?}", pred);
1027        assert!(dbg.contains("HeightPredictor"));
1028    }
1029
1030    #[test]
1031    fn posterior_variance_with_two_identical_observations() {
1032        let mut pred = HeightPredictor::new(PredictorConfig {
1033            prior_variance: 4.0,
1034            prior_strength: 1.0,
1035            ..Default::default()
1036        });
1037        pred.observe(0, 3);
1038        pred.observe(0, 3);
1039        // Welford variance with identical values = 0, κ_n = 3
1040        // posterior_variance = 0 / 3 = 0
1041        let var = pred.posterior_variance(0);
1042        assert!(var.abs() < 1e-10, "identical obs should give ~0 variance");
1043    }
1044
1045    #[test]
1046    fn posterior_variance_with_one_observation_uses_prior() {
1047        let mut pred = HeightPredictor::new(PredictorConfig {
1048            prior_variance: 4.0,
1049            prior_strength: 2.0,
1050            ..Default::default()
1051        });
1052        pred.observe(0, 3);
1053        // n=1, so welford.variance() returns f64::MAX → uses prior_variance
1054        // But wait: code checks n < 2, uses prior_variance = 4.0
1055        // posterior_variance = 4.0 / (2.0 + 1) = 4/3
1056        let var = pred.posterior_variance(0);
1057        assert!((var - 4.0 / 3.0).abs() < 1e-10);
1058    }
1059
1060    #[test]
1061    fn observe_returns_false_for_first_cold_outlier() {
1062        let mut pred = HeightPredictor::new(PredictorConfig {
1063            default_height: 1,
1064            prior_mean: 1.0,
1065            prior_strength: 2.0,
1066            prior_variance: 0.25,
1067            ..Default::default()
1068        });
1069        // Cold prediction: predicted=1, margin=ceil(sqrt(0.25)*2)=ceil(1.0)=1
1070        // bounds: [0, 2]
1071        // First observation is cold (observations=0), so violation not counted
1072        let within = pred.observe(0, 100);
1073        // Cold start: prediction.observations == 0, so violation is NOT counted
1074        assert!(within || pred.total_violations() == 0);
1075    }
1076
1077    #[test]
1078    fn all_same_height_converges_exactly() {
1079        let mut pred = HeightPredictor::new(PredictorConfig {
1080            prior_mean: 3.0,
1081            prior_strength: 1.0,
1082            ..Default::default()
1083        });
1084        for _ in 0..100 {
1085            pred.observe(0, 3);
1086        }
1087        let p = pred.predict(0);
1088        assert_eq!(p.predicted, 3);
1089        // With all identical observations, bounds should collapse
1090        assert_eq!(p.lower, 3);
1091        assert_eq!(p.upper, 3);
1092    }
1093
1094    #[test]
1095    fn many_categories_auto_created() {
1096        let mut pred = HeightPredictor::default();
1097        pred.observe(10, 5);
1098        // Categories 0..=10 should exist now
1099        assert_eq!(pred.category_count(), 11);
1100        // Intermediate categories have no observations
1101        assert_eq!(pred.category_observations(5), 0);
1102        assert_eq!(pred.category_observations(10), 1);
1103    }
1104
1105    #[test]
1106    fn violation_rate_near_alpha_on_stationary_data() {
1107        let alpha = 0.10;
1108        let mut pred = HeightPredictor::new(PredictorConfig {
1109            default_height: 20,
1110            prior_mean: 20.0,
1111            prior_strength: 2.0,
1112            prior_variance: 16.0,
1113            coverage: 1.0 - alpha,
1114            calibration_window: 500,
1115        });
1116
1117        // Deterministic Box-Muller Normal(20.0, 4.0) samples (2,000 samples after warmup).
1118        let mut seed: u64 = 0x9E37_79B9_7F4A_7C15;
1119        let mut next_u01 = || -> f64 {
1120            seed = seed
1121                .wrapping_mul(6364136223846793005)
1122                .wrapping_add(1442695040888963407);
1123            (((seed >> 11) as f64) + 0.5) / ((1u64 << 53) as f64)
1124        };
1125        let mut sample_height = || -> u16 {
1126            let u1 = next_u01();
1127            let u2 = next_u01();
1128            let z = (-2.0 * u1.ln()).sqrt() * (std::f64::consts::TAU * u2).cos();
1129            (20.0 + 4.0 * z).round().clamp(1.0, 60.0) as u16
1130        };
1131
1132        // Warm up calibration window
1133        for _ in 0..300 {
1134            let _ = pred.observe(0, sample_height());
1135        }
1136
1137        let mut violations = 0usize;
1138        let n = 2_000usize;
1139        for _ in 0..n {
1140            if !pred.observe(0, sample_height()) {
1141                violations += 1;
1142            }
1143        }
1144        let rate = violations as f64 / n as f64;
1145        assert!(
1146            (0.05..=0.15).contains(&rate),
1147            "violation rate {rate:.4} outside [0.05, 0.15] for alpha={alpha}"
1148        );
1149    }
1150
1151    #[test]
1152    fn prediction_bounds_ordering_after_mixed_data() {
1153        let mut pred = HeightPredictor::default();
1154        for h in [1, 2, 5, 10, 1, 3, 7, 2, 4, 6] {
1155            pred.observe(0, h);
1156        }
1157        let p = pred.predict(0);
1158        assert!(
1159            p.lower <= p.predicted,
1160            "lower={} > predicted={}",
1161            p.lower,
1162            p.predicted
1163        );
1164        assert!(
1165            p.predicted <= p.upper,
1166            "predicted={} > upper={}",
1167            p.predicted,
1168            p.upper
1169        );
1170    }
1171}