int_interval_stack/int_co_stack/
impls_for_access.rs

1use super::*;
2
3/// Projects the covered interval set from canonical stack change points.
4///
5/// A stack change-point sequence describes a piecewise-constant height
6/// function. The covered set is exactly the union of all coordinate ranges
7/// whose height is positive.
8///
9/// This function scans positive-height runs:
10///
11/// ```text
12/// height: 0 -> positive    opens a covered interval
13/// height: positive -> 0    closes a covered interval
14/// positive -> positive     keeps the current covered interval open
15/// ```
16///
17/// # Input invariants
18///
19/// `points` must be the canonical output of stack construction:
20///
21/// - coordinates are strictly increasing;
22/// - adjacent points have different `height_after` values;
23/// - the final height, when non-empty, is zero.
24///
25/// # Output
26///
27/// The returned set is canonical. Positive-height runs are emitted in
28/// ascending order and are separated by zero-height gaps.
29#[inline]
30fn covered_from_change_points<I>(points: &[ChangePoint<I::CoordType>]) -> IntCOSet<I>
31where
32    I: IntCO,
33{
34    let mut out = Vec::new();
35    let mut start = None;
36
37    for p in points {
38        match (start, p.height_after) {
39            (None, h) if h > 0 => {
40                start = Some(p.at);
41            }
42            (Some(s), 0) => {
43                // SAFETY:
44                // Canonical change points are strictly increasing, and a
45                // positive-height run can only close at a later coordinate.
46                out.push(unsafe { I::new_unchecked(s, p.at) });
47                start = None;
48            }
49            _ => {}
50        }
51    }
52
53    debug_assert!(
54        start.is_none(),
55        "canonical stack change points must end at zero height"
56    );
57
58    // SAFETY:
59    // Positive-height runs are emitted in ascending order and are separated by
60    // zero-height gaps, so the result is canonical.
61    unsafe { IntCOSet::new_unchecked(out) }
62}
63
64impl<I> IntCOStack<I>
65where
66    I: IntCO,
67{
68    #[inline]
69    pub fn change_points(&self) -> &[ChangePoint<I::CoordType>] {
70        &self.change_points
71    }
72
73    #[inline]
74    pub fn covered(&self) -> &IntCOSet<I> {
75        self.covered
76            .get_or_init(|| covered_from_change_points::<I>(&self.change_points))
77    }
78
79    #[inline]
80    pub fn height_stats(&self) -> HeightStats {
81        self.height_stats
82    }
83
84    #[inline]
85    pub fn height_at(&self, x: I::CoordType) -> usize {
86        let i = self.change_points.partition_point(|p| p.at <= x);
87        if i == 0 {
88            0
89        } else {
90            self.change_points[i - 1].height_after
91        }
92    }
93}
94
95#[cfg(test)]
96mod tests_for_access;
97
98#[cfg(test)]
99mod tests_for_covered_from_change_points;
int_interval_stack/int_co_stack/impls_for_access.rs

int_interval_stack/int_co_stack/
impls_for_access.rs
