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

twine_components/schedule/
step_schedule.rs
