use std::collections::HashMap;
use std::fmt;
use std::str::FromStr;
use crate::error::{Result, UcciError};
use crate::num::{check_finite, check_finite_scalar, check_same_len, pairwise_sum};
pub const DEFAULT_COST_SMALL: f64 = 1.0;
pub const DEFAULT_COST_LARGE: f64 = 3.02;
pub const DEFAULT_GRID_STEP: f64 = 0.005;
pub const DEFAULT_GRID_LEN: usize = 201;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "json", serde(rename_all = "lowercase"))]
pub enum CostModel {
#[default]
Routing,
Sequential,
}
impl CostModel {
pub fn as_str(self) -> &'static str {
match self {
CostModel::Routing => "routing",
CostModel::Sequential => "sequential",
}
}
}
impl fmt::Display for CostModel {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(self.as_str())
}
}
impl FromStr for CostModel {
type Err = UcciError;
fn from_str(s: &str) -> Result<Self> {
match s {
"routing" => Ok(CostModel::Routing),
"sequential" => Ok(CostModel::Sequential),
other => Err(UcciError::InvalidParameter {
name: "cost_model",
reason: format!("must be 'routing' or 'sequential', got {other:?}"),
}),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq)]
#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
pub struct Costs {
pub c_small: f64,
pub c_large: f64,
pub model: CostModel,
}
impl Costs {
pub fn new(c_small: f64, c_large: f64, model: CostModel) -> Result<Self> {
let costs = Costs {
c_small,
c_large,
model,
};
costs.validate()?;
Ok(costs)
}
pub fn paper() -> Self {
Costs {
c_small: DEFAULT_COST_SMALL,
c_large: DEFAULT_COST_LARGE,
model: CostModel::Routing,
}
}
pub fn validate(&self) -> Result<()> {
check_finite_scalar(self.c_small, "c_small")?;
check_finite_scalar(self.c_large, "c_large")?;
if self.c_small <= 0.0 {
return Err(UcciError::InvalidParameter {
name: "c_small",
reason: format!("must be positive, got {}", self.c_small),
});
}
if self.c_large <= 0.0 {
return Err(UcciError::InvalidParameter {
name: "c_large",
reason: format!("must be positive, got {}", self.c_large),
});
}
Ok(())
}
fn validate_ordered(&self) -> Result<()> {
self.validate()?;
if self.model == CostModel::Routing && self.c_large <= self.c_small {
return Err(UcciError::InvalidParameter {
name: "c_large",
reason: format!(
"Theorem 1 assumption (i) needs c_large > c_small under the routing cost \
model; got c_small={}, c_large={}",
self.c_small, self.c_large
),
});
}
Ok(())
}
pub fn cost_at_rate(&self, rate: f64) -> f64 {
match self.model {
CostModel::Routing => self.c_small * (1.0 - rate) + self.c_large * rate,
CostModel::Sequential => self.c_small + self.c_large * rate,
}
}
}
impl Default for Costs {
fn default() -> Self {
Costs::paper()
}
}
#[derive(Debug, Clone, Copy, PartialEq)]
#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
pub struct ThresholdChoice {
pub theta: f64,
pub cost: f64,
pub accuracy: f64,
pub escalation_rate: f64,
}
#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
pub struct ParetoFrontier {
pub theta: Vec<f64>,
pub cost: Vec<f64>,
pub accuracy: Vec<f64>,
pub escalation_rate: Vec<f64>,
pub efficient: Vec<bool>,
}
impl ParetoFrontier {
pub fn len(&self) -> usize {
self.theta.len()
}
pub fn is_empty(&self) -> bool {
self.theta.is_empty()
}
pub fn points(&self) -> impl Iterator<Item = ThresholdChoice> + '_ {
(0..self.len()).map(move |j| self.point(j))
}
pub fn efficient_points(&self) -> impl Iterator<Item = ThresholdChoice> + '_ {
(0..self.len())
.filter(move |&j| self.efficient[j])
.map(move |j| self.point(j))
}
fn point(&self, j: usize) -> ThresholdChoice {
ThresholdChoice {
theta: self.theta[j],
cost: self.cost[j],
accuracy: self.accuracy[j],
escalation_rate: self.escalation_rate[j],
}
}
}
pub(crate) fn linspace01(n: usize) -> Vec<f64> {
let step = 1.0 / n as f64;
let mut v: Vec<f64> = (0..=n).map(|i| i as f64 * step + 0.0).collect();
if n > 0 {
v[n] = 1.0;
}
v
}
fn rint(x: f64) -> f64 {
let r = x.round();
if (r - x).abs() == 0.5 {
2.0 * (x / 2.0).round()
} else {
r
}
}
fn np_round(v: f64, decimals: i32) -> f64 {
let f = 10f64.powi(decimals);
rint(v * f) / f
}
pub fn default_grid() -> Vec<f64> {
linspace01(DEFAULT_GRID_LEN - 1)
.into_iter()
.map(|v| np_round(v, 3))
.collect()
}
pub fn make_grid(step: f64) -> Result<Vec<f64>> {
check_finite_scalar(step, "step")?;
if !(step > 0.0 && step <= 1.0) {
return Err(UcciError::InvalidParameter {
name: "step",
reason: format!("must lie in (0, 1], got {step}"),
});
}
let n = rint(1.0 / step);
if (n * step - 1.0).abs() > 1e-9 {
return Err(UcciError::InvalidParameter {
name: "step",
reason: format!("must divide 1 exactly (e.g. 0.005 or 0.01), got {step}"),
});
}
Ok(linspace01(n as usize)
.into_iter()
.map(|v| np_round(v, 12))
.collect())
}
fn check_grid(grid: &[f64]) -> Result<Vec<f64>> {
if grid.is_empty() {
return Err(UcciError::Empty { what: "grid" });
}
check_finite(grid, "grid")?;
if let Some(index) = grid.iter().position(|g| !(0.0..=1.0).contains(g)) {
return Err(UcciError::OutOfRange {
what: "grid",
index,
value: grid[index],
expected: "in [0, 1]",
});
}
let mut g = grid.to_vec();
g.sort_by(f64::total_cmp);
g.dedup_by(|a, b| a == b);
Ok(g)
}
fn check_scores(p_len: usize, small: &[f64], large: &[f64]) -> Result<()> {
if small.is_empty() {
return Err(UcciError::Empty {
what: "small_score",
});
}
check_finite(small, "small_score")?;
if large.is_empty() {
return Err(UcciError::Empty {
what: "large_score",
});
}
check_finite(large, "large_score")?;
check_same_len(p_len, small.len(), "p_hat and small_score")?;
check_same_len(p_len, large.len(), "p_hat and large_score")
}
fn check_p_hat(p_hat: &[f64]) -> Result<()> {
if p_hat.is_empty() {
return Err(UcciError::Empty { what: "p_hat" });
}
check_finite(p_hat, "p_hat")
}
pub fn escalate(p_hat: f64, theta: f64) -> Result<bool> {
check_finite_scalar(theta, "theta")?;
if !p_hat.is_finite() {
return Err(UcciError::NonFinite {
what: "p_hat",
index: 0,
});
}
Ok(p_hat > theta)
}
pub fn escalate_many(p_hat: &[f64], theta: f64) -> Result<Vec<bool>> {
check_finite_scalar(theta, "theta")?;
check_finite(p_hat, "p_hat")?;
Ok(p_hat.iter().map(|&p| p > theta).collect())
}
fn escalation_rate(esc: &[bool]) -> f64 {
esc.iter().filter(|&&e| e).count() as f64 / esc.len() as f64
}
pub fn policy_cost(esc: &[bool], costs: &Costs) -> Result<f64> {
if esc.is_empty() {
return Err(UcciError::Empty { what: "esc" });
}
costs.validate()?;
Ok(costs.cost_at_rate(escalation_rate(esc)))
}
pub fn policy_accuracy(esc: &[bool], small_score: &[f64], large_score: &[f64]) -> Result<f64> {
if esc.is_empty() {
return Err(UcciError::Empty { what: "esc" });
}
check_scores(esc.len(), small_score, large_score)?;
let kept: Vec<f64> = esc
.iter()
.zip(small_score)
.filter(|(&e, _)| !e)
.map(|(_, &s)| s)
.collect();
let escalated: Vec<f64> = esc
.iter()
.zip(large_score)
.filter(|(&e, _)| e)
.map(|(_, &s)| s)
.collect();
Ok((pairwise_sum(&kept) + pairwise_sum(&escalated)) / esc.len() as f64)
}
struct Sweep {
theta: Vec<f64>,
rate: Vec<f64>,
accuracy: Vec<f64>,
}
impl Sweep {
fn bins(p_hat: &[f64], grid: &[f64]) -> Vec<usize> {
p_hat
.iter()
.map(|&p| grid.partition_point(|&g| g < p))
.collect()
}
fn counts(bins: &[usize], g_len: usize) -> (Vec<usize>, Vec<f64>) {
let mut counts = vec![0usize; g_len + 1];
for &b in bins {
counts[b] += 1;
}
let mut k = vec![0usize; g_len];
let mut acc = 0usize;
for j in (0..g_len).rev() {
acc += counts[j + 1];
k[j] = acc;
}
let n = bins.len() as f64;
let rate = k.iter().map(|&kj| kj as f64 / n).collect();
(k, rate)
}
fn with_scores(p_hat: &[f64], small: &[f64], large: &[f64], grid: &[f64]) -> Result<Self> {
check_p_hat(p_hat)?;
let theta = check_grid(grid)?;
check_scores(p_hat.len(), small, large)?;
let g_len = theta.len();
let bins = Self::bins(p_hat, &theta);
let (_, rate) = Self::counts(&bins, g_len);
let mut s_bin = vec![0.0f64; g_len + 1];
let mut l_bin = vec![0.0f64; g_len + 1];
for (i, &b) in bins.iter().enumerate() {
s_bin[b] += small[i];
l_bin[b] += large[i];
}
let mut esc_large = vec![0.0f64; g_len];
let mut acc = l_bin[g_len];
for j in (0..g_len).rev() {
esc_large[j] = acc;
acc += l_bin[j];
}
let n = p_hat.len() as f64;
let mut accuracy = Vec::with_capacity(g_len);
let mut kept_small = 0.0f64;
for (j, &s) in s_bin.iter().take(g_len).enumerate() {
kept_small = if j == 0 { s } else { kept_small + s };
accuracy.push((kept_small + esc_large[j]) / n);
}
Ok(Sweep {
theta,
rate,
accuracy,
})
}
fn with_metric<F>(p_hat: &[f64], grid: &[f64], mut metric: F) -> Result<Self>
where
F: FnMut(&[bool]) -> f64,
{
check_p_hat(p_hat)?;
let theta = check_grid(grid)?;
let bins = Self::bins(p_hat, &theta);
let (k, rate) = Self::counts(&bins, theta.len());
let mut cache: HashMap<usize, f64> = HashMap::new();
let mut accuracy = Vec::with_capacity(theta.len());
for (j, &t) in theta.iter().enumerate() {
let value = match cache.get(&k[j]) {
Some(&v) => v,
None => {
let mask: Vec<bool> = p_hat.iter().map(|&p| p > t).collect();
let v = metric_value(&mut metric, &mask, t)?;
cache.insert(k[j], v);
v
}
};
accuracy.push(value);
}
Ok(Sweep {
theta,
rate,
accuracy,
})
}
fn costs(&self, costs: &Costs) -> Vec<f64> {
self.rate.iter().map(|&r| costs.cost_at_rate(r)).collect()
}
fn choice(&self, j: usize, cost: &[f64]) -> ThresholdChoice {
ThresholdChoice {
theta: self.theta[j],
cost: cost[j],
accuracy: self.accuracy[j],
escalation_rate: self.rate[j],
}
}
fn select(&self, tau: f64, costs: &Costs) -> Result<ThresholdChoice> {
let cost = self.costs(costs);
let feasible: Vec<usize> = (0..self.theta.len())
.filter(|&j| self.accuracy[j] >= tau)
.collect();
if feasible.is_empty() {
let j = argmax_first(&self.accuracy);
return Err(UcciError::Infeasible {
tau,
best_accuracy: self.accuracy[j],
best_theta: self.theta[j],
});
}
let min_cost = feasible
.iter()
.map(|&j| cost[j])
.fold(f64::INFINITY, f64::min);
let cheapest: Vec<usize> = feasible
.into_iter()
.filter(|&j| cost[j] == min_cost)
.collect();
let best_acc = cheapest
.iter()
.map(|&j| self.accuracy[j])
.fold(f64::NEG_INFINITY, f64::max);
let j = *cheapest
.iter()
.rev()
.find(|&&j| self.accuracy[j] == best_acc)
.expect("non-empty");
Ok(self.choice(j, &cost))
}
fn select_for_budget(&self, budget: f64, costs: &Costs) -> Result<ThresholdChoice> {
let cost = self.costs(costs);
let feasible: Vec<usize> = (0..self.theta.len())
.filter(|&j| cost[j] <= budget)
.collect();
if feasible.is_empty() {
let j = argmin_first(&cost);
return Err(UcciError::OverBudget {
budget,
min_cost: cost[j],
cheapest_theta: self.theta[j],
});
}
let best_acc = feasible
.iter()
.map(|&j| self.accuracy[j])
.fold(f64::NEG_INFINITY, f64::max);
let most_accurate: Vec<usize> = feasible
.into_iter()
.filter(|&j| self.accuracy[j] == best_acc)
.collect();
let min_cost = most_accurate
.iter()
.map(|&j| cost[j])
.fold(f64::INFINITY, f64::min);
let j = *most_accurate
.iter()
.rev()
.find(|&&j| cost[j] == min_cost)
.expect("non-empty");
Ok(self.choice(j, &cost))
}
fn frontier(self, costs: &Costs) -> ParetoFrontier {
let cost = self.costs(costs);
let acc = &self.accuracy;
let mut unique_cost = cost.clone();
unique_cost.sort_by(f64::total_cmp);
unique_cost.dedup_by(|a, b| a == b);
let group: Vec<usize> = cost
.iter()
.map(|c| unique_cost.partition_point(|u| u < c))
.collect();
let mut best_in_group = vec![f64::NEG_INFINITY; unique_cost.len()];
for (j, &g) in group.iter().enumerate() {
best_in_group[g] = best_in_group[g].max(acc[j]);
}
let mut best_cheaper = vec![f64::NEG_INFINITY; unique_cost.len()];
let mut running = f64::NEG_INFINITY;
for g in 0..unique_cost.len() {
best_cheaper[g] = running;
running = running.max(best_in_group[g]);
}
let efficient = (0..cost.len())
.map(|j| acc[j] == best_in_group[group[j]] && acc[j] > best_cheaper[group[j]])
.collect();
ParetoFrontier {
theta: self.theta,
cost,
accuracy: self.accuracy,
escalation_rate: self.rate,
efficient,
}
}
}
fn argmax_first(v: &[f64]) -> usize {
let mut best = 0;
for (j, &x) in v.iter().enumerate() {
if x > v[best] {
best = j;
}
}
best
}
fn argmin_first(v: &[f64]) -> usize {
let mut best = 0;
for (j, &x) in v.iter().enumerate() {
if x < v[best] {
best = j;
}
}
best
}
fn metric_value<F: FnMut(&[bool]) -> f64>(
metric: &mut F,
mask: &[bool],
theta: f64,
) -> Result<f64> {
let v = metric(mask);
if v.is_finite() {
Ok(v)
} else {
Err(UcciError::InvalidParameter {
name: "metric",
reason: format!("returned {v} at theta={theta}"),
})
}
}
pub fn select_threshold(
p_hat: &[f64],
small_score: &[f64],
large_score: &[f64],
tau: f64,
costs: &Costs,
grid: &[f64],
) -> Result<ThresholdChoice> {
check_finite_scalar(tau, "tau")?;
costs.validate_ordered()?;
Sweep::with_scores(p_hat, small_score, large_score, grid)?.select(tau, costs)
}
pub fn select_threshold_with_metric<F>(
p_hat: &[f64],
tau: f64,
costs: &Costs,
grid: &[f64],
metric: F,
) -> Result<ThresholdChoice>
where
F: FnMut(&[bool]) -> f64,
{
check_finite_scalar(tau, "tau")?;
costs.validate_ordered()?;
Sweep::with_metric(p_hat, grid, metric)?.select(tau, costs)
}
pub fn select_threshold_for_budget(
p_hat: &[f64],
small_score: &[f64],
large_score: &[f64],
budget: f64,
costs: &Costs,
grid: &[f64],
) -> Result<ThresholdChoice> {
check_finite_scalar(budget, "budget")?;
costs.validate_ordered()?;
Sweep::with_scores(p_hat, small_score, large_score, grid)?.select_for_budget(budget, costs)
}
pub fn select_threshold_for_budget_with_metric<F>(
p_hat: &[f64],
budget: f64,
costs: &Costs,
grid: &[f64],
metric: F,
) -> Result<ThresholdChoice>
where
F: FnMut(&[bool]) -> f64,
{
check_finite_scalar(budget, "budget")?;
costs.validate_ordered()?;
Sweep::with_metric(p_hat, grid, metric)?.select_for_budget(budget, costs)
}
pub fn pareto_frontier(
p_hat: &[f64],
small_score: &[f64],
large_score: &[f64],
costs: &Costs,
grid: &[f64],
) -> Result<ParetoFrontier> {
costs.validate()?;
Ok(Sweep::with_scores(p_hat, small_score, large_score, grid)?.frontier(costs))
}
pub fn pareto_frontier_with_metric<F>(
p_hat: &[f64],
costs: &Costs,
grid: &[f64],
metric: F,
) -> Result<ParetoFrontier>
where
F: FnMut(&[bool]) -> f64,
{
costs.validate()?;
Ok(Sweep::with_metric(p_hat, grid, metric)?.frontier(costs))
}
pub fn evaluate(
p_hat: &[f64],
small_score: &[f64],
large_score: &[f64],
theta: f64,
costs: &Costs,
) -> Result<ThresholdChoice> {
costs.validate()?;
check_p_hat(p_hat)?;
let mask = escalate_many(p_hat, theta)?;
let accuracy = policy_accuracy(&mask, small_score, large_score)?;
let rate = escalation_rate(&mask);
Ok(ThresholdChoice {
theta,
cost: costs.cost_at_rate(rate),
accuracy,
escalation_rate: rate,
})
}
pub fn evaluate_with_metric<F>(
p_hat: &[f64],
theta: f64,
costs: &Costs,
mut metric: F,
) -> Result<ThresholdChoice>
where
F: FnMut(&[bool]) -> f64,
{
costs.validate()?;
check_p_hat(p_hat)?;
let mask = escalate_many(p_hat, theta)?;
let accuracy = metric_value(&mut metric, &mask, theta)?;
let rate = escalation_rate(&mask);
Ok(ThresholdChoice {
theta,
cost: costs.cost_at_rate(rate),
accuracy,
escalation_rate: rate,
})
}
#[cfg(test)]
mod tests {
use super::*;
fn routing(c_small: f64, c_large: f64) -> Costs {
Costs::new(c_small, c_large, CostModel::Routing).unwrap()
}
#[test]
fn grid_matches_numpy() {
let g = default_grid();
assert_eq!(g.len(), 201);
for (i, &v) in g.iter().enumerate() {
assert_eq!(v, i as f64 / 200.0, "i = {i}");
}
assert_eq!(make_grid(DEFAULT_GRID_STEP).unwrap(), g);
assert_eq!(make_grid(1.0).unwrap(), vec![0.0, 1.0]);
assert_eq!(make_grid(0.1).unwrap()[3], 0.3);
for bad in [0.0, -0.1, 1.5, 0.3, f64::NAN] {
assert!(make_grid(bad).is_err(), "step {bad}");
}
}
#[test]
fn rint_is_half_to_even() {
assert_eq!(rint(0.5), 0.0);
assert_eq!(rint(1.5), 2.0);
assert_eq!(rint(2.5), 2.0);
assert_eq!(rint(-0.5), -0.0);
assert_eq!(rint(-1.5), -2.0);
assert_eq!(rint(2.4), 2.0);
assert_eq!(rint(2.6), 3.0);
}
#[test]
fn escalate_is_strict() {
assert!(!escalate(0.3, 0.3).unwrap());
assert!(escalate(0.31, 0.3).unwrap());
assert!(escalate(f64::NAN, 0.3).is_err());
assert!(escalate(0.3, f64::INFINITY).is_err());
assert_eq!(
escalate_many(&[0.1, 0.5, 0.9], 0.5).unwrap(),
vec![false, false, true]
);
assert!(escalate_many(&[0.1, f64::NAN], 0.5).is_err());
}
#[test]
fn cost_models() {
let esc = [true, false, false, true];
assert_eq!(policy_cost(&esc, &routing(1.0, 3.0)).unwrap(), 2.0);
let seq = Costs::new(1.0, 3.0, CostModel::Sequential).unwrap();
assert_eq!(policy_cost(&esc, &seq).unwrap(), 2.5);
assert!(policy_cost(&[], &seq).is_err());
let paper = Costs::paper();
assert!((paper.cost_at_rate(0.5345) - (1.0 + 2.02 * 0.5345)).abs() < 1e-12);
assert!((routing(1.0, 5.0).cost_at_rate(0.5345) - (1.0 + 4.0 * 0.5345)).abs() < 1e-12);
assert_eq!((paper.cost_at_rate(0.5345) * 100.0).round(), 208.0);
assert_eq!(
(routing(1.0, 5.0).cost_at_rate(0.5345) * 100.0).round(),
314.0
);
assert_eq!(Costs::default(), paper);
}
#[test]
fn costs_validation() {
assert!(Costs::new(0.0, 3.0, CostModel::Routing).is_err());
assert!(Costs::new(1.0, -3.0, CostModel::Routing).is_err());
assert!(Costs::new(f64::NAN, 3.0, CostModel::Routing).is_err());
assert!(Costs::new(1.0, f64::INFINITY, CostModel::Routing).is_err());
let flat = Costs::new(2.0, 1.0, CostModel::Routing).unwrap();
let err = select_threshold(&[0.5], &[1.0], &[1.0], 0.5, &flat, &default_grid());
assert!(matches!(
err,
Err(UcciError::InvalidParameter {
name: "c_large",
..
})
));
let seq = Costs::new(2.0, 1.0, CostModel::Sequential).unwrap();
assert!(select_threshold(&[0.5], &[1.0], &[1.0], 0.5, &seq, &default_grid()).is_ok());
assert!(pareto_frontier(&[0.5], &[1.0], &[1.0], &flat, &default_grid()).is_ok());
}
#[test]
fn cost_model_names() {
assert_eq!("routing".parse::<CostModel>().unwrap(), CostModel::Routing);
assert_eq!(
"sequential".parse::<CostModel>().unwrap(),
CostModel::Sequential
);
assert!("Routing".parse::<CostModel>().is_err());
assert_eq!(CostModel::Sequential.to_string(), "sequential");
assert_eq!(CostModel::default(), CostModel::Routing);
}
#[test]
fn accuracy_of_mask() {
let esc = [true, false, true];
let acc = policy_accuracy(&esc, &[0.0, 1.0, 0.0], &[1.0, 0.0, 0.5]).unwrap();
assert_eq!(acc, (1.0 + 1.0 + 0.5) / 3.0);
assert!(policy_accuracy(&esc, &[0.0, 1.0], &[1.0, 0.0, 0.5]).is_err());
assert!(policy_accuracy(&esc, &[0.0, 1.0, f64::NAN], &[1.0, 0.0, 0.5]).is_err());
}
#[test]
fn python_docstring_example() {
let c = select_threshold(
&[0.1, 0.2, 0.6, 0.9],
&[1.0, 1.0, 0.0, 0.0],
&[1.0; 4],
1.0,
&Costs::paper(),
&default_grid(),
)
.unwrap();
assert_eq!((c.theta, c.accuracy, c.escalation_rate), (0.595, 1.0, 0.5));
}
#[test]
fn tau_zero_keeps_everything_and_picks_largest_theta() {
let c = select_threshold(
&[0.1, 0.9],
&[0.0, 0.0],
&[1.0, 1.0],
0.0,
&Costs::paper(),
&default_grid(),
)
.unwrap();
assert_eq!(c.escalation_rate, 0.0);
assert_eq!(c.theta, 1.0);
assert_eq!(c.cost, 1.0);
}
#[test]
fn infeasible_reports_best_accuracy() {
let err = select_threshold(
&[0.1, 0.9],
&[1.0, 0.0],
&[0.0, 0.0],
0.9,
&Costs::paper(),
&default_grid(),
)
.unwrap_err();
match err {
UcciError::Infeasible {
best_accuracy,
best_theta,
..
} => {
assert_eq!(best_accuracy, 0.5);
assert_eq!(best_theta, 0.1);
}
other => panic!("unexpected {other:?}"),
}
}
#[test]
fn select_matches_brute_force() {
let mut state = 12345u64;
let mut next = || {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
((state >> 11) as f64) / ((1u64 << 53) as f64)
};
let n = 300;
let p: Vec<f64> = (0..n).map(|_| (next() * 40.0).floor() / 40.0).collect();
let small: Vec<f64> = p
.iter()
.map(|&pi| if next() < pi { 0.0 } else { 1.0 })
.collect();
let large: Vec<f64> = (0..n)
.map(|_| if next() < 0.1 { 0.0 } else { 1.0 })
.collect();
let grid = default_grid();
let costs = Costs::paper();
for tau in [0.5, 0.7, 0.8, 0.85, 0.9] {
let brute: Vec<ThresholdChoice> = grid
.iter()
.map(|&t| evaluate(&p, &small, &large, t, &costs).unwrap())
.filter(|c| c.accuracy >= tau)
.collect();
let got = select_threshold(&p, &small, &large, tau, &costs, &grid);
if brute.is_empty() {
assert!(got.is_err());
continue;
}
let min_cost = brute.iter().map(|c| c.cost).fold(f64::INFINITY, f64::min);
let best = brute
.iter()
.filter(|c| c.cost == min_cost)
.max_by(|a, b| a.theta.total_cmp(&b.theta))
.unwrap();
let got = got.unwrap();
assert_eq!(got.theta, best.theta, "tau {tau}");
assert_eq!(got.cost, best.cost);
assert_eq!(got.escalation_rate, best.escalation_rate);
assert_eq!(got.accuracy, best.accuracy);
}
}
#[test]
fn metric_matches_scores_for_mean_accuracy() {
let p = [0.05, 0.3, 0.3, 0.7, 0.95];
let small = [1.0, 1.0, 0.0, 0.0, 0.0];
let large = [1.0, 1.0, 1.0, 1.0, 0.0];
let grid = default_grid();
let costs = Costs::paper();
let mut calls = 0;
let metric = |esc: &[bool]| {
calls += 1;
policy_accuracy(esc, &small, &large).unwrap()
};
let a = select_threshold_with_metric(&p, 0.8, &costs, &grid, metric).unwrap();
assert_eq!(calls, 5);
let b = select_threshold(&p, &small, &large, 0.8, &costs, &grid).unwrap();
assert_eq!(a, b);
let bad = select_threshold_with_metric(&p, 0.8, &costs, &grid, |_| f64::NAN);
assert!(matches!(
bad,
Err(UcciError::InvalidParameter { name: "metric", .. })
));
}
#[test]
fn budget_form() {
let p = [0.1, 0.2, 0.6, 0.9];
let small = [1.0, 1.0, 0.0, 0.0];
let large = [1.0; 4];
let costs = routing(1.0, 3.0);
let grid = default_grid();
let c = select_threshold_for_budget(&p, &small, &large, 2.0, &costs, &grid).unwrap();
assert_eq!((c.accuracy, c.cost, c.theta), (1.0, 2.0, 0.595));
let c = select_threshold_for_budget(&p, &small, &large, 1.5, &costs, &grid).unwrap();
assert_eq!((c.accuracy, c.cost, c.theta), (0.75, 1.5, 0.895));
match select_threshold_for_budget(&p, &small, &large, 0.5, &costs, &grid) {
Err(UcciError::OverBudget { min_cost, .. }) => assert_eq!(min_cost, 1.0),
other => panic!("unexpected {other:?}"),
}
}
#[test]
fn frontier_marks_efficient_points() {
let p = [0.1, 0.2, 0.6, 0.9];
let small = [1.0, 1.0, 0.0, 0.0];
let large = [1.0; 4];
let f = pareto_frontier(
&p,
&small,
&large,
&routing(1.0, 3.0),
&[0.0, 0.15, 0.5, 0.8, 1.0],
)
.unwrap();
assert_eq!(f.len(), 5);
assert_eq!(f.escalation_rate, vec![1.0, 0.75, 0.5, 0.25, 0.0]);
assert_eq!(f.accuracy, vec![1.0, 1.0, 1.0, 0.75, 0.5]);
assert_eq!(f.efficient, vec![false, false, true, true, true]);
assert_eq!(f.efficient_points().count(), 3);
assert_eq!(f.points().count(), 5);
assert!(!f.is_empty());
}
#[test]
fn grid_is_sorted_and_deduplicated() {
let p = [0.1, 0.9];
let s = [1.0, 0.0];
let l = [1.0, 1.0];
let f = pareto_frontier(&p, &s, &l, &Costs::paper(), &[0.5, 0.2, 0.5, 0.0]).unwrap();
assert_eq!(f.theta, vec![0.0, 0.2, 0.5]);
assert!(pareto_frontier(&p, &s, &l, &Costs::paper(), &[]).is_err());
assert!(pareto_frontier(&p, &s, &l, &Costs::paper(), &[1.5]).is_err());
assert!(pareto_frontier(&p, &s, &l, &Costs::paper(), &[f64::NAN]).is_err());
}
#[test]
fn evaluate_reports_actual_cost_and_accuracy() {
let c = evaluate(&[0.1, 0.6], &[1.0, 0.0], &[1.0, 1.0], 0.5, &Costs::paper()).unwrap();
assert_eq!(c.escalation_rate, 0.5);
assert_eq!(c.accuracy, 1.0);
assert_eq!(c.cost, 1.0 * 0.5 + 3.02 * 0.5);
let m = evaluate_with_metric(&[0.1, 0.6], 0.5, &Costs::paper(), |esc| {
esc.iter().filter(|&&e| e).count() as f64
})
.unwrap();
assert_eq!(m.accuracy, 1.0);
assert!(evaluate(&[], &[], &[], 0.5, &Costs::paper()).is_err());
assert!(evaluate(&[0.1], &[1.0], &[1.0], f64::NAN, &Costs::paper()).is_err());
}
#[test]
fn input_errors() {
let g = default_grid();
let c = Costs::paper();
assert!(select_threshold(&[], &[], &[], 0.5, &c, &g).is_err());
assert!(select_threshold(&[0.1], &[1.0, 1.0], &[1.0], 0.5, &c, &g).is_err());
assert!(select_threshold(&[f64::NAN], &[1.0], &[1.0], 0.5, &c, &g).is_err());
assert!(select_threshold(&[0.1], &[1.0], &[1.0], f64::NAN, &c, &g).is_err());
assert!(select_threshold_for_budget(&[0.1], &[1.0], &[1.0], f64::NAN, &c, &g).is_err());
}
}