geop_core_math/solvers/
probe.rs

1//! Probing a sequence of trial values until one decides: a step halved
2//! until a point stepped off a curve lands where it should, a reach
3//! doubled until it brackets a crossing, a point marched on until it
4//! passes one, a ray cast in one direction after another until one is
5//! clear of every vertex.
6//!
7//! What is probed is a free choice — how far to step, how far to reach —
8//! and what the probe finds there is the caller's to judge. The solver
9//! promises only the sequence: `start`, then each value `next` makes of
10//! the one before, at most `most` of them, each asked once and in order.
11//! It answers `None` when none decided, never the last value tried.
12
13use crate::{geop_error::GeopError, scalars::Scalar};
14
15/// What a probe found at one value of the sequence.
16pub enum Probe<T> {
17    /// It decides: the search ends with this.
18    Found(T),
19    /// It does not: go on to the next value.
20    Next,
21    /// It does not, and no later value will: the search ends with nothing.
22    Stop,
23}
24
25/// Asks `at` for `start` and each value `next` makes of the one before, at
26/// most `most` of them, until one is [`Probe::Found`] or [`Probe::Stop`].
27/// `next` is asked only for a value that will be probed. `at` may keep
28/// state of its own (what the probes so far said), since every value is
29/// asked once, in order.
30pub fn probe<X, T, E>(
31    start: X,
32    most: usize,
33    mut next: impl FnMut(&X) -> Result<X, E>,
34    mut at: impl FnMut(&X) -> Result<Probe<T>, E>,
35) -> Result<Option<T>, E> {
36    let mut x = start;
37    for k in 0..most {
38        match at(&x)? {
39            Probe::Found(found) => return Ok(Some(found)),
40            Probe::Stop => return Ok(None),
41            Probe::Next => {}
42        }
43        if k + 1 < most {
44            x = next(&x)?;
45        }
46    }
47    Ok(None)
48}
49
50/// [`probe`] with a step halved each time: `start`, `start / 2`, … — at
51/// most `most` of them.
52pub fn halve<T, E: From<GeopError>>(
53    start: Scalar,
54    most: usize,
55    at: impl FnMut(&Scalar) -> Result<Probe<T>, E>,
56) -> Result<Option<T>, E> {
57    probe(start, most, |s| Ok(s.div(Scalar::TWO)?), at)
58}
59
60/// [`probe`] over attempts `0, 1, 2, …` — at most `most` of them — for a
61/// sequence `at` makes itself (the `k`-th of a set of directions, the next
62/// draw of a seeded generator).
63pub fn attempts<T, E>(
64    most: usize,
65    at: impl FnMut(&usize) -> Result<Probe<T>, E>,
66) -> Result<Option<T>, E> {
67    probe(0, most, |k| Ok(k + 1), at)
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    /// Halving from 1 finds the first step below a third — and asks every
75    /// step before it, in order, and none after.
76    #[test]
77    fn halving_finds_the_first_step_that_decides() {
78        let mut asked = Vec::new();
79        let found = halve::<_, GeopError>(Scalar::ONE, 10, |s| {
80            asked.push(*s);
81            Ok(if s.to_f64() < 1.0 / 3.0 {
82                Probe::Found(*s)
83            } else {
84                Probe::Next
85            })
86        })
87        .unwrap();
88        // Halved in interval arithmetic, each step encloses the exact one.
89        let exact = [1.0, 0.5, 0.25];
90        assert_eq!(asked.len(), exact.len());
91        for (a, e) in asked.iter().zip(exact) {
92            assert!(a.could_be_equal(Scalar::from_f64(e)), "{a:?}");
93        }
94        assert!(found.is_some_and(|f| f.could_be_equal(Scalar::from_f64(0.25))));
95    }
96
97    /// A sequence that never decides reports nothing — not its last value —
98    /// and makes no value past the last it may ask.
99    #[test]
100    fn a_probe_that_never_decides_finds_nothing() {
101        let mut made = 0;
102        let found = probe::<f64, f64, ()>(
103            1.0,
104            4,
105            |x| {
106                made += 1;
107                Ok(x * 2.0)
108            },
109            |_| Ok(Probe::Next),
110        )
111        .unwrap();
112        assert_eq!(found, None);
113        assert_eq!(made, 3);
114    }
115
116    /// `Stop` ends the search at once, with nothing.
117    #[test]
118    fn stop_ends_the_search() {
119        let mut asked = 0;
120        let found = probe::<f64, f64, ()>(
121            1.0,
122            100,
123            |x| Ok(x + 1.0),
124            |&x| {
125                asked += 1;
126                Ok(if x >= 3.0 { Probe::Stop } else { Probe::Next })
127            },
128        )
129        .unwrap();
130        assert_eq!((found, asked), (None, 3));
131    }
132
133    /// Attempts are counted from zero, and none past `most`.
134    #[test]
135    fn attempts_count_from_zero() {
136        let first_odd = attempts::<usize, ()>(5, |&k| {
137            Ok(if k % 2 == 1 {
138                Probe::Found(k)
139            } else {
140                Probe::Next
141            })
142        });
143        assert_eq!(first_odd, Ok(Some(1)));
144        let mut asked = Vec::new();
145        let none = attempts::<(), ()>(3, |&k| {
146            asked.push(k);
147            Ok(Probe::Next)
148        });
149        assert_eq!((none, asked), (Ok(None), vec![0, 1, 2]));
150    }
151}
geop_core_math/solvers/probe.rs

geop_core_math/solvers/
probe.rs
