twine_models/support/schedule/
step_schedule.rs

1mod step;
2
3use std::{fmt::Debug, ops::Range};
4
5use thiserror::Error;
6
7pub use step::{EmptyRangeError, Step};
8
9/// Threshold below which [`StepSchedule::value_at`] uses linear search.
10///
11/// For schedules with fewer than this many steps, a linear scan is used.
12/// Otherwise, binary search is performed for faster lookups in larger schedules.
13///
14/// 32 is chosen heuristically: sequential memory access is cache-friendly, and
15/// binary search pays branch prediction costs that outweigh its algorithmic
16/// advantage at small sizes.
17const LINEAR_SEARCH_THRESHOLD: usize = 32;
18
19/// Associates values with distinct, non-overlapping time ranges.
20///
21/// A `StepSchedule` is a collection of [`Step`]s, each mapping a value to a
22/// non-empty, non-overlapping half-open range `[start, end)`.
23///
24/// The range type `T` must implement [`Ord`], and usually represents time,
25/// though any ordered type (e.g., numbers or indices) is supported.
26///
27/// # Examples
28///
29/// ```
30/// use twine_models::support::schedule::step_schedule::{Step, StepSchedule};
31///
32/// let schedule = StepSchedule::new([
33///     Step::new(0..10, "low").unwrap(),
34///     Step::new(10..20, "medium").unwrap(),
35///     Step::new(20..30, "high").unwrap(),
36/// ]).unwrap();
37///
38/// assert_eq!(schedule.value_at(&-1), None);
39/// assert_eq!(schedule.value_at(&0), Some(&"low"));
40/// assert_eq!(schedule.value_at(&15), Some(&"medium"));
41/// assert_eq!(schedule.value_at(&25), Some(&"high"));
42/// assert_eq!(schedule.value_at(&30), None);
43/// ```
44#[derive(Debug, Clone, PartialEq, Eq, Default)]
45pub struct StepSchedule<T, V> {
46    steps: Vec<Step<T, V>>,
47}
48
49/// Error returned when attempting to add a [`Step`] that overlaps an existing one.
50///
51/// This error can occur when creating a [`StepSchedule`] with overlapping steps,
52/// or when pushing a new step into an existing schedule.
53///
54/// The `existing` field refers to a step already in the schedule,
55/// and `incoming` is the step that overlaps it.
56#[derive(Debug, Error)]
57#[error("steps overlap: {existing:?} and {incoming:?}")]
58pub struct OverlappingStepsError<T: Debug + Ord> {
59    pub existing: Range<T>,
60    pub incoming: Range<T>,
61}
62
63impl<T: Debug + Clone + Ord, V> StepSchedule<T, V> {
64    /// Creates a new `StepSchedule` from an iterator over [`Step`]s.
65    ///
66    /// Accepts any type convertible into an iterator, such as a vector or array.
67    /// The resulting schedule is ordered by increasing start time.
68    ///
69    /// # Errors
70    ///
71    /// Returns an [`OverlappingStepsError`] if any steps have overlapping ranges.
72    /// Steps are sorted by start time before validation, so the `existing` step
73    /// will always have an earlier start than the `incoming` one in the error.
74    pub fn new<I>(steps: I) -> Result<Self, OverlappingStepsError<T>>
75    where
76        I: IntoIterator<Item = Step<T, V>>,
77    {
78        let mut steps: Vec<_> = steps.into_iter().collect();
79        steps.sort_by(|a, b| a.start().cmp(b.start()));
80
81        if let Some(index) = steps.windows(2).position(|pair| pair[0].overlaps(&pair[1])) {
82            return Err(OverlappingStepsError {
83                existing: steps[index].range().clone(),
84                incoming: steps[index + 1].range().clone(),
85            });
86        }
87
88        Ok(StepSchedule { steps })
89    }
90
91    /// Attempts to add a step to the schedule.
92    ///
93    /// # Errors
94    ///
95    /// Returns an [`OverlappingStepsError`] if the new step's range overlaps
96    /// with any existing steps in the schedule.
97    pub fn try_push(&mut self, step: Step<T, V>) -> Result<(), OverlappingStepsError<T>> {
98        let index = self.steps.partition_point(|s| s.start() < step.start());
99
100        // Only the immediate neighbors need to be checked.
101        // The schedule invariant guarantees existing steps are non-overlapping, so
102        // any step two positions left ends before the left neighbor starts — if the
103        // left neighbor doesn't overlap, nothing further left can either.
104        // The same reasoning applies going right.
105        let overlaps_left = index.checked_sub(1).and_then(|i| {
106            let left = &self.steps[i];
107            left.overlaps(&step).then_some(left)
108        });
109
110        let overlaps_right = self.steps.get(index).filter(|s| s.overlaps(&step));
111
112        if let Some(existing_step) = overlaps_left.or(overlaps_right) {
113            return Err(OverlappingStepsError {
114                existing: existing_step.range().clone(),
115                incoming: step.range().clone(),
116            });
117        }
118
119        self.steps.insert(index, step);
120        Ok(())
121    }
122
123    /// Returns a slice of the steps in this schedule.
124    #[must_use]
125    pub fn steps(&self) -> &[Step<T, V>] {
126        &self.steps
127    }
128
129    /// Returns the value associated with the given `time`, if any.
130    ///
131    /// Searches for the [`Step`] whose range contains `time` and returns a
132    /// reference to its associated value.
133    /// Returns `None` if no such step exists.
134    ///
135    /// For schedules with fewer than [`LINEAR_SEARCH_THRESHOLD`] steps,
136    /// a linear scan is used.
137    /// Otherwise, binary search is performed.
138    ///
139    /// # Examples
140    ///
141    /// ```
142    /// use twine_models::support::schedule::step_schedule::{Step, StepSchedule};
143    ///
144    /// let schedule = StepSchedule::new(vec![
145    ///     Step::new(0..10, 1).unwrap(),
146    ///     Step::new(10..20, 2).unwrap(),
147    /// ]).unwrap();
148    ///
149    /// assert_eq!(schedule.value_at(&5), Some(&1));
150    /// assert_eq!(schedule.value_at(&15), Some(&2));
151    /// assert_eq!(schedule.value_at(&20), None);
152    /// ```
153    pub fn value_at(&self, time: &T) -> Option<&V> {
154        if self.steps.len() < LINEAR_SEARCH_THRESHOLD {
155            self.steps.iter().find_map(|step| step.value_at(time))
156        } else {
157            self.steps
158                .binary_search_by(|step| step.cmp_to_time(time))
159                .ok()
160                .map(|index| self.steps[index].value())
161        }
162    }
163}
164
165#[cfg(test)]
166mod tests {
167    use super::*;
168
169    #[test]
170    fn new_succeeds_with_non_overlapping_steps() {
171        let schedule = StepSchedule::new([
172            Step::new(10..20, "a").unwrap(),
173            Step::new(20..30, "b").unwrap(),
174        ])
175        .unwrap();
176
177        assert_eq!(schedule.steps().len(), 2);
178        assert_eq!(schedule.value_at(&15), Some(&"a"));
179        assert_eq!(schedule.value_at(&25), Some(&"b"));
180    }
181
182    #[test]
183    fn new_rejects_overlapping_steps() {
184        let result = StepSchedule::new([
185            Step::new(0..10, "a").unwrap(),
186            Step::new(9..15, "b").unwrap(),
187        ]);
188
189        assert!(result.is_err());
190    }
191
192    #[test]
193    fn steps_are_sorted_by_start_time() {
194        let schedule = StepSchedule::new([
195            Step::new(20..30, "later").unwrap(),
196            Step::new(0..10, "early").unwrap(),
197        ])
198        .unwrap();
199
200        let steps = schedule.steps();
201        assert_eq!(steps[0].start(), &0);
202        assert_eq!(steps[1].start(), &20);
203    }
204
205    #[test]
206    fn try_push_inserts_steps_correctly() {
207        let starts = |s: &StepSchedule<_, _>| {
208            s.steps()
209                .iter()
210                .map(Step::start)
211                .copied()
212                .collect::<Vec<_>>()
213        };
214
215        let mut schedule = StepSchedule::new([
216            Step::new(0..10, "a").unwrap(),
217            Step::new(20..30, "c").unwrap(),
218        ])
219        .unwrap();
220
221        schedule.try_push(Step::new(10..20, "b").unwrap()).unwrap();
222        assert_eq!(starts(&schedule), vec![0, 10, 20]);
223        assert_eq!(schedule.value_at(&15), Some(&"b"));
224
225        schedule
226            .try_push(Step::new(-10..-5, "start").unwrap())
227            .unwrap();
228        assert_eq!(starts(&schedule), vec![-10, 0, 10, 20]);
229
230        schedule
231            .try_push(Step::new(30..40, "end").unwrap())
232            .unwrap();
233        assert_eq!(starts(&schedule), vec![-10, 0, 10, 20, 30]);
234
235        assert_eq!(
236            schedule
237                .steps()
238                .iter()
239                .map(Step::value)
240                .copied()
241                .collect::<Vec<_>>(),
242            vec!["start", "a", "b", "c", "end"],
243        );
244    }
245
246    #[test]
247    fn try_push_rejects_overlapping_step() {
248        let mut schedule = StepSchedule::new([
249            (0..10, "a").try_into().unwrap(),
250            (20..30, "b").try_into().unwrap(),
251        ])
252        .unwrap();
253
254        assert!(
255            schedule
256                .try_push((5..15, "overlaps a").try_into().unwrap())
257                .is_err()
258        );
259
260        assert!(
261            schedule
262                .try_push((25..35, "overlaps b").try_into().unwrap())
263                .is_err()
264        );
265
266        assert!(
267            schedule
268                .try_push((5..25, "overlaps both").try_into().unwrap())
269                .is_err()
270        );
271    }
272
273    #[test]
274    fn value_at_handles_empty_schedule() {
275        let schedule: StepSchedule<i32, &str> = StepSchedule::default();
276        assert_eq!(schedule.value_at(&5), None);
277    }
278
279    #[test]
280    fn value_at_handles_exact_start_and_end_bounds() {
281        let step = Step::new(5..10, "only").unwrap();
282        let schedule = StepSchedule::new(std::iter::once(step)).unwrap();
283
284        assert_eq!(schedule.value_at(&4), None);
285        assert_eq!(schedule.value_at(&5), Some(&"only"));
286        assert_eq!(schedule.value_at(&9), Some(&"only"));
287        assert_eq!(schedule.value_at(&10), None);
288    }
289
290    #[test]
291    fn value_at_works_for_large_schedules() {
292        let steps = (0..100).map(|i| Step::new(i * 10..(i + 1) * 10, i).unwrap());
293        let schedule = StepSchedule::new(steps).unwrap();
294
295        assert_eq!(schedule.value_at(&0), Some(&0));
296        assert_eq!(schedule.value_at(&42), Some(&4));
297        assert_eq!(schedule.value_at(&999), Some(&99));
298        assert_eq!(schedule.value_at(&1000), None);
299    }
300}
twine_models/support/schedule/step_schedule.rs

twine_models/support/schedule/
step_schedule.rs
