1use std::collections::BTreeMap;
11use std::fmt;
12
13#[derive(Clone, Debug, PartialEq, Eq)]
15pub struct Least {
16 pub need: u64,
18 pub tried: BTreeMap<u64, bool>,
20}
21
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub struct Counterexample {
26 pub value: u64,
28 pub refused: bool,
30 pub need: Option<u64>,
32}
33
34impl fmt::Display for Counterexample {
35 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
36 match self.need {
37 None => write!(f, "the top value {} is itself refused", self.value),
38 Some(need) => write!(
39 f,
40 "not monotone: {} is {} while the bisected need is {need}; this needs a spec \
41 ruling, not a squeeze result",
42 self.value,
43 if self.refused { "refused" } else { "clear" },
44 ),
45 }
46 }
47}
48
49fn checks(lo: u64, need: u64, hi: u64, samples: u64) -> Vec<u64> {
53 let mut v = vec![need, need.saturating_add(1).min(hi)];
54 if need > lo {
55 v.push(need - 1);
56 }
57 let mut step = 2_u64;
58 let within = |x: Option<u64>| x.is_some_and(|x| (lo..=hi).contains(&x));
59 while step > 0 && (within(need.checked_sub(step)) || within(need.checked_add(step))) {
60 if let Some(below) = need.checked_sub(step).filter(|&x| x >= lo) {
61 v.push(below);
62 }
63 if let Some(above) = need.checked_add(step).filter(|&x| x <= hi) {
64 v.push(above);
65 }
66 step = step.checked_mul(2).unwrap_or(0);
67 }
68 for k in 1..=samples {
69 if need > lo {
70 v.push(between(lo, need, k, samples));
71 }
72 v.push(between(need, hi, k, samples));
73 }
74 v.sort_unstable();
75 v.dedup();
76 v
77}
78
79fn between(a: u64, b: u64, k: u64, samples: u64) -> u64 {
82 let span = u128::from(b - a) * u128::from(k) / (u128::from(samples) + 1);
83 a.saturating_add(u64::try_from(span).unwrap_or(b - a))
85}
86
87pub fn least(
96 lo: u64,
97 hi: u64,
98 samples: u64,
99 mut refused: impl FnMut(u64) -> bool,
100) -> Result<Least, Counterexample> {
101 let mut tried = BTreeMap::new();
102 let mut ask =
103 |v: u64, tried: &mut BTreeMap<u64, bool>| *tried.entry(v).or_insert_with(|| refused(v));
104 if ask(hi, &mut tried) {
105 return Err(Counterexample {
106 value: hi,
107 refused: true,
108 need: None,
109 });
110 }
111 let need = if ask(lo, &mut tried) {
112 let (mut bad, mut good) = (lo, hi);
113 while good - bad > 1 {
114 let mid = bad + (good - bad) / 2;
115 if ask(mid, &mut tried) {
116 bad = mid;
117 } else {
118 good = mid;
119 }
120 }
121 good
122 } else {
123 lo
124 };
125 for v in checks(lo, need, hi, samples) {
126 ask(v, &mut tried);
127 }
128 if let Some((&value, &r)) = tried.iter().find(|&(&v, &r)| r != (v < need)) {
129 return Err(Counterexample {
130 value,
131 refused: r,
132 need: Some(need),
133 });
134 }
135 Ok(Least { need, tried })
136}
137
138#[cfg(test)]
139mod tests {
140 use super::{Counterexample, least};
141
142 #[test]
143 fn the_need_is_the_least_clear_value_and_its_neighbours_are_tried() {
144 let found = least(0, 1 << 20, 3, |v| v < 777).unwrap();
145 assert_eq!(found.need, 777);
146 assert_eq!(found.tried.get(&776), Some(&true));
147 assert_eq!(found.tried.get(&777), Some(&false));
148 assert_eq!(found.tried.get(&778), Some(&false));
149 assert!(found.tried.len() < 80, "{}", found.tried.len());
150 }
151
152 #[test]
153 fn a_need_of_zero_is_tested_at_zero_alone() {
154 let found = least(0, 100, 2, |_| false).unwrap();
155 assert_eq!(found.need, 0);
156 assert!(found.tried.keys().all(|&v| v <= 100));
157 }
158
159 #[test]
162 fn a_window_below_the_need_is_a_counterexample() {
163 let pred = |v: u64| !((250..=260).contains(&v) || v >= 1000);
164 let e = least(0, 1 << 12, 7, pred).unwrap_err();
165 assert!(e.value < 1000 && !e.refused, "{e:?}");
166 assert!(e.to_string().contains("spec ruling"), "{e}");
167 }
168
169 #[test]
171 fn the_whole_range_is_searched_without_overflow() {
172 let l = least(0, u64::MAX, 4, |v| v < 777).unwrap();
173 assert_eq!(l.need, 777);
174 assert!(l.tried.contains_key(&u64::MAX));
175 assert!(l.tried.keys().any(|&v| v > u64::MAX / 2 && v < u64::MAX));
176 let top = least(u64::MAX - 3, u64::MAX, 4, |v| v < u64::MAX).unwrap();
177 assert_eq!(top.need, u64::MAX);
178 }
179
180 #[test]
181 fn a_refused_top_is_no_bracket() {
182 assert_eq!(
183 least(0, 10, 1, |_| true),
184 Err(Counterexample {
185 value: 10,
186 refused: true,
187 need: None
188 })
189 );
190 }
191}