ph_surfaces/axis/
linear.rs

1//! The linear strategy: stored knots, no auxiliary index, bounded scan. The
2//! least machinery of the four, for axes small enough that a search is not
3//! worth its own code.
4
5use super::{AxisLookup, KnotArray, assert_valid_knots, sealed};
6
7/// An axis of `N` stored knots located by a bounded forward scan.
8///
9/// It stores exactly what [`BinaryAxis`](crate::BinaryAxis) stores and accepts
10/// the same arbitrary spacing; it differs only in trading the halving loop for a
11/// straight walk. On a three- or four-knot axis that walk is at most two or
12/// three comparisons — comparable to the search it replaces, with less code
13/// behind it. On a long axis it is the wrong choice, and the bound below says so
14/// plainly.
15///
16/// # Cost
17///
18/// `2*N` stored bytes, no index, and at most `N - 1` strategy-specific knot
19/// comparisons after the endpoint checks. Unlike the binary strategy the count
20/// is data-dependent: a coordinate near the first knot costs less than one near
21/// the last.
22///
23/// # Examples
24///
25/// ```
26/// use ph_surfaces::{BilinearSurface, BinaryAxis, LinearAxis};
27///
28/// static X: [u16; 3] = [0, 30, 100];
29/// static Y: [u16; 2] = [0, 10];
30/// static VALUES: [[i32; 3]; 2] = [[0, 30, 100], [10, 40, 110]];
31///
32/// // A tiny X axis scans; the Y axis keeps the default strategy.
33/// static SURFACE: BilinearSurface<3, 2, LinearAxis<3>, BinaryAxis<2>> =
34///     BilinearSurface::from_axes(LinearAxis::new(&X), BinaryAxis::new(&Y), &VALUES);
35///
36/// // Same answers as the all-binary surface over the same tables.
37/// static DEFAULT: BilinearSurface<3, 2> = BilinearSurface::new(&X, &Y, &VALUES);
38/// assert_eq!(SURFACE.evaluate(65, 5), DEFAULT.evaluate(65, 5));
39/// assert_eq!(SURFACE.evaluate(65, 5), Ok(70));
40/// ```
41///
42/// An axis of fewer than two knots does not compile:
43///
44/// ```compile_fail
45/// use ph_surfaces::LinearAxis;
46///
47/// static X: [u16; 1] = [7];
48/// static AXIS: LinearAxis<1> = LinearAxis::new(&X);
49/// ```
50#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
51pub struct LinearAxis<const N: usize> {
52    knots: &'static [u16; N],
53}
54
55impl<const N: usize> LinearAxis<N> {
56    /// Declares a scanned axis over static knots.
57    ///
58    /// # Panics
59    ///
60    /// Panics unless the axis declares at least two strictly increasing knots.
61    /// In a constant or static definition that panic is a compile error.
62    #[must_use]
63    pub const fn new(knots: &'static [u16; N]) -> Self {
64        assert_valid_knots(knots);
65
66        Self { knots }
67    }
68
69    /// Returns the declared knots.
70    ///
71    /// The same array as [`KnotArray::knots`], available in a constant context.
72    #[must_use]
73    pub const fn knots(&self) -> &'static [u16; N] {
74        self.knots
75    }
76}
77
78impl<const N: usize> sealed::Sealed<N> for LinearAxis<N> {
79    #[inline(always)]
80    fn search_in_domain(&self, coordinate: u16) -> (usize, u32) {
81        debug_assert!(
82            self.knots[0] <= coordinate && coordinate <= self.knots[N - 1],
83            "the sealed search is only called on an in-domain coordinate"
84        );
85
86        let mut index = 0;
87        let mut comparisons = 0;
88
89        // Walk while the *next* knot is still at or below the coordinate. The
90        // walk therefore stops on the greatest such knot, and it can never step
91        // past `N - 1`.
92        while index + 1 < N {
93            comparisons += 1;
94            if self.knots[index + 1] > coordinate {
95                break;
96            }
97            index += 1;
98        }
99
100        debug_assert!(
101            comparisons <= <Self as AxisLookup<N>>::MAX_SEARCH_COMPARISONS,
102            "the scan must stay inside the documented bound"
103        );
104        debug_assert!(
105            self.knots[index] <= coordinate,
106            "the located knot must not sit above the coordinate"
107        );
108
109        (index, comparisons)
110    }
111}
112
113impl<const N: usize> KnotArray<N> for LinearAxis<N> {
114    fn knots(&self) -> &'static [u16; N] {
115        self.knots
116    }
117}
118
119impl<const N: usize> AxisLookup<N> for LinearAxis<N> {
120    const KNOT_BYTES: usize = 2 * N;
121    const INDEX_BYTES: usize = 0;
122    // The scan stops at the last knot, so it can compare against at most the
123    // `N - 1` knots above the first one.
124    const MAX_SEARCH_COMPARISONS: u32 = (N - 1) as u32;
125
126    fn first(&self) -> u16 {
127        self.knots[0]
128    }
129
130    fn last(&self) -> u16 {
131        self.knots[N - 1]
132    }
133
134    fn knot(&self, index: usize) -> u16 {
135        self.knots[index]
136    }
137}
138
139#[cfg(test)]
140mod tests {
141    use super::LinearAxis;
142    use crate::axis::{AxisLookup, BinaryAxis, KnotArray, probes};
143
144    static X_TINY: [u16; 2] = [7, 9];
145    static X_MAIN: [u16; 5] = [10, 20, 30, 40, 50];
146    static X_SPARSE: [u16; 6] = [3, 4, 5, 1_000, 40_000, 65_000];
147    static X_FULL: [u16; 4] = [0, 1, 32_768, 65_535];
148
149    const TINY: LinearAxis<2> = LinearAxis::new(&X_TINY);
150    const MAIN: LinearAxis<5> = LinearAxis::new(&X_MAIN);
151    const SPARSE: LinearAxis<6> = LinearAxis::new(&X_SPARSE);
152    const FULL: LinearAxis<4> = LinearAxis::new(&X_FULL);
153
154    #[test]
155    fn the_scan_locates_the_same_index_as_the_binary_search() {
156        macro_rules! agrees_with_binary {
157            ($linear:expr, $knots:expr, $stride:expr) => {
158                let linear = $linear;
159                let binary = BinaryAxis::new($knots);
160
161                for coordinate in probes($knots, $stride) {
162                    assert_eq!(
163                        linear.search(coordinate).0,
164                        binary.search(coordinate).0,
165                        "at {coordinate}"
166                    );
167                }
168            };
169        }
170
171        agrees_with_binary!(TINY, &X_TINY, 1);
172        agrees_with_binary!(MAIN, &X_MAIN, 1);
173        agrees_with_binary!(SPARSE, &X_SPARSE, 97);
174        agrees_with_binary!(FULL, &X_FULL, 97);
175    }
176
177    #[test]
178    fn every_knot_locates_itself() {
179        for (index, &knot) in X_MAIN.iter().enumerate() {
180            assert_eq!(MAIN.search(knot).0, index, "at knot {knot}");
181        }
182        for (index, &knot) in X_SPARSE.iter().enumerate() {
183            assert_eq!(SPARSE.search(knot).0, index, "at knot {knot}");
184        }
185    }
186
187    #[test]
188    fn the_scan_never_exceeds_its_declared_bound() {
189        assert_eq!(<LinearAxis<2>>::MAX_SEARCH_COMPARISONS, 1);
190        assert_eq!(<LinearAxis<5>>::MAX_SEARCH_COMPARISONS, 4);
191        assert_eq!(<LinearAxis<6>>::MAX_SEARCH_COMPARISONS, 5);
192
193        for coordinate in 10u16..=50 {
194            assert!(MAIN.search(coordinate).1 <= <LinearAxis<5>>::MAX_SEARCH_COMPARISONS);
195        }
196
197        // The bound is reached only at the far end of the axis, and the cost
198        // below the first interior knot is one comparison.
199        assert_eq!(MAIN.search(50).1, 4);
200        assert_eq!(MAIN.search(10).1, 1);
201        assert_eq!(TINY.search(9).1, 1);
202    }
203
204    #[test]
205    fn the_knot_array_is_referenced_and_never_copied() {
206        assert!(core::ptr::eq(MAIN.knots(), &X_MAIN));
207        assert!(core::ptr::eq(KnotArray::knots(&MAIN), &X_MAIN));
208        assert_eq!(<LinearAxis<5>>::KNOT_BYTES, 10);
209        assert_eq!(<LinearAxis<5>>::INDEX_BYTES, 0);
210    }
211
212    #[test]
213    #[should_panic(expected = "an axis must declare at least two knots")]
214    fn a_one_knot_axis_is_rejected() {
215        static ONE: [u16; 1] = [3];
216
217        let _ = LinearAxis::new(&ONE);
218    }
219
220    #[test]
221    #[should_panic(expected = "axis knots must be strictly increasing")]
222    fn a_descending_knot_is_rejected() {
223        static DESCENDING: [u16; 3] = [0, 100, 50];
224
225        let _ = LinearAxis::new(&DESCENDING);
226    }
227}
ph_surfaces/axis/linear.rs

ph_surfaces/axis/
linear.rs
