int_interval_stack/
stack_window.rs

1use int_interval::traits::IntCO;
2use rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator};
3
4use crate::{HeightRun, IntCOStack};
5
6#[derive(Debug, Clone, Copy)]
7pub struct StackWindow<'a, I>
8where
9    I: IntCO,
10{
11    stack: &'a IntCOStack<I>,
12    interval: I,
13    /// First change point strictly inside the window after `interval.start()`.
14    point_start: usize,
15    /// First change point at or after `interval.end_excl()`.
16    point_end: usize,
17    /// Stack height at `interval.start()`.
18    height_at_start: usize,
19}
20
21impl<'a, I> StackWindow<'a, I>
22where
23    I: IntCO,
24{
25    pub(crate) fn new(stack: &'a IntCOStack<I>, interval: I) -> Self {
26        let points = stack.change_points();
27
28        let window_start = interval.start();
29        let window_end = interval.end_excl();
30
31        let point_start = points.partition_point(|point| point.at <= window_start);
32        let point_end =
33            point_start + points[point_start..].partition_point(|point| point.at < window_end);
34
35        let height_at_start = point_start
36            .checked_sub(1)
37            .map_or(0, |index| points[index].height_after);
38
39        Self {
40            stack,
41            interval,
42            point_start,
43            point_end,
44            height_at_start,
45        }
46    }
47
48    #[inline]
49    pub const fn stack(&self) -> &'a IntCOStack<I> {
50        self.stack
51    }
52
53    #[inline]
54    pub const fn interval(&self) -> &I {
55        &self.interval
56    }
57
58    /// Returns the number of constant-height runs inside this window.
59    ///
60    /// A window is partitioned by every stack change point strictly inside the
61    /// window:
62    ///
63    /// ```text
64    /// [window.start, p0), [p0, p1), ..., [pn, window.end)
65    /// ```
66    ///
67    /// Therefore the number of runs is the number of interior change points plus
68    /// one. Even a window with no interior change points has one run covering the
69    /// whole window.
70    #[inline]
71    fn height_run_count(&self) -> usize {
72        self.point_end - self.point_start + 1
73    }
74
75    /// Builds the constant-height run at `run_index`.
76    ///
77    /// `run_index` is an index into the window-local run partition, not into the
78    /// global change-point array.
79    ///
80    /// For a window containing interior change points
81    /// `points[point_start..point_end]`, the run boundaries are:
82    ///
83    /// - run `0`: starts at `interval.start()`;
84    /// - run `i > 0`: starts at `points[point_start + i - 1].at`;
85    /// - run `i < count - 1`: ends at `points[point_start + i].at`;
86    /// - final run: ends at `interval.end_excl()`.
87    ///
88    /// Heights follow the stack height active at each run start:
89    ///
90    /// - run `0` uses `height_at_start`;
91    /// - run `i > 0` uses the height after the preceding interior change point.
92    #[inline]
93    fn height_run_at(&self, run_index: usize) -> HeightRun<I> {
94        debug_assert!(run_index < self.height_run_count());
95
96        let points = self.stack.change_points();
97
98        let point_index = self.point_start + run_index;
99
100        let start = if run_index == 0 {
101            self.interval.start()
102        } else {
103            points[point_index - 1].at
104        };
105
106        let end_excl = if point_index < self.point_end {
107            points[point_index].at
108        } else {
109            self.interval.end_excl()
110        };
111
112        let height = if run_index == 0 {
113            self.height_at_start
114        } else {
115            points[point_index - 1].height_after
116        };
117
118        HeightRun {
119            // SAFETY:
120            // `run_index` ranges over the partition induced by change points
121            // strictly inside this window. Therefore each produced pair is a
122            // non-empty closed-open interval.
123            interval: unsafe { I::new_unchecked(start, end_excl) },
124            height,
125        }
126    }
127}
128
129impl<I> StackWindow<'_, I>
130where
131    I: IntCO,
132{
133    /// Iterates over constant-height runs inside this window.
134    ///
135    /// Unlike `IntCOStack::iter_height_segments`, this includes zero-height
136    /// runs because window-level mappings may assign a non-zero value to
137    /// height zero.
138    #[inline]
139    pub fn iter_height_runs(
140        &self,
141    ) -> impl DoubleEndedIterator<Item = HeightRun<I>> + ExactSizeIterator {
142        (0..self.height_run_count()).map(move |run_index| self.height_run_at(run_index))
143    }
144}
145
146impl<I> StackWindow<'_, I>
147where
148    I: IntCO + Send + Sync,
149{
150    /// Iterates in parallel over constant-height runs inside this window.
151    ///
152    /// The run range is represented as an indexed integer range, so Rayon can
153    /// split the work directly. This is mainly useful when the per-run mapping
154    /// is expensive or the window contains many height changes.
155    #[inline]
156    pub fn par_iter_height_runs(&self) -> impl IndexedParallelIterator<Item = HeightRun<I>> {
157        (0..self.height_run_count())
158            .into_par_iter()
159            .map(move |run_index| self.height_run_at(run_index))
160    }
161}
162
163#[cfg(test)]
164mod tests_for_new;
165
166#[cfg(test)]
167mod tests_for_height_run_at;
168
169#[cfg(test)]
170mod tests_for_iter_height_runs;
int_interval_stack/stack_window.rs

int_interval_stack/
stack_window.rs
