grit_pattern_matcher/
intervals.rs

1use crate::{context::QueryContext, pattern::EffectRange};
2use grit_util::EffectKind;
3use std::{cmp::Ordering, ops::Range};
4
5pub trait Interval {
6    fn interval(&self) -> (u32, u32);
7}
8
9impl Interval for Range<u32> {
10    fn interval(&self) -> (u32, u32) {
11        (self.start, self.end)
12    }
13}
14
15fn compare<T>(i1: &T, i2: &T) -> Ordering
16where
17    T: Interval,
18{
19    let i1 = i1.interval();
20    let i2 = i2.interval();
21    if i1.1 < i2.1 {
22        return Ordering::Less;
23    }
24    if i1.1 > i2.1 {
25        return Ordering::Greater;
26    }
27    if i1.0 > i2.0 {
28        return Ordering::Less;
29    }
30    if i1.0 < i2.0 {
31        return Ordering::Greater;
32    }
33    Ordering::Equal
34}
35
36pub fn earliest_deadline_sort<T>(list: &mut [T]) -> bool
37where
38    T: Interval,
39{
40    list.sort_by(|b1, b2| compare(b1, b2));
41    for pair in list.windows(2) {
42        let p0 = pair[0].interval();
43        let p1 = pair[1].interval();
44        if p1.0 < p0.1 && p1.0 > p0.0 {
45            return false;
46        }
47    }
48    true
49}
50
51pub fn get_top_level_intervals<T>(effects: Vec<T>) -> Vec<T>
52where
53    T: Interval,
54{
55    let mut top_level = Vec::with_capacity(effects.len());
56    let mut top_level_open = u32::MAX;
57    for e in effects.into_iter().rev() {
58        let e_interval = e.interval();
59        if e_interval.1 <= top_level_open {
60            top_level.push(e);
61            top_level_open = e_interval.0;
62        }
63    }
64    top_level
65}
66
67pub fn get_top_level_intervals_in_range<Q: QueryContext>(
68    effects: Vec<EffectRange<Q>>,
69    left: u32,
70    right: u32,
71) -> Vec<EffectRange<Q>> {
72    let mut top_level = Vec::with_capacity(effects.len());
73    let mut top_level_open = right;
74    for e in effects.into_iter().rev() {
75        let e_interval = e.interval();
76        if e_interval.1 < left {
77            break;
78        }
79        if matches!(e.effect.kind, EffectKind::Insert)
80            && e_interval.0 >= left
81            && e_interval.1 <= right
82        {
83            top_level.push(e);
84            continue;
85        }
86        if e_interval.1 <= top_level_open && e_interval.0 >= left {
87            top_level.push(e);
88            top_level_open = e_interval.0;
89        }
90    }
91    top_level
92}
93
94pub fn pop_out_of_range_intervals<T>(interval: &T, intervals: &mut Vec<T>)
95where
96    T: Interval,
97{
98    let interval = interval.interval();
99    while let Some(top) = intervals.last() {
100        let top_interval = top.interval();
101        if top_interval.0 < interval.1 {
102            break;
103        }
104        intervals.pop();
105    }
106}
107
108#[cfg(test)]
109mod tests {
110    use crate::intervals::get_top_level_intervals;
111
112    use super::earliest_deadline_sort;
113
114    #[derive(Clone, Debug)]
115    struct TestEffect {
116        interval: (u32, u32),
117    }
118    impl TestEffect {
119        fn new(interval: (u32, u32)) -> Self {
120            Self { interval }
121        }
122    }
123    impl super::Interval for TestEffect {
124        fn interval(&self) -> (u32, u32) {
125            self.interval
126        }
127    }
128
129    impl From<(u32, u32)> for TestEffect {
130        fn from(interval: (u32, u32)) -> Self {
131            Self::new(interval)
132        }
133    }
134
135    fn vec_into(v: &[(u32, u32)]) -> Vec<TestEffect> {
136        v.iter().map(|e| TestEffect::from(*e)).collect()
137    }
138    fn vec_back<T>(v: &[T]) -> Vec<(u32, u32)>
139    where
140        T: super::Interval,
141    {
142        v.iter().map(|e| e.interval()).collect()
143    }
144
145    #[test]
146    fn test_simple() {
147        let mut list = vec_into(&[(0, 1), (1, 2), (2, 3), (3, 4)]);
148        assert!(earliest_deadline_sort(&mut list));
149        let list = get_top_level_intervals(list);
150        println!("{:?}", vec_back(&list));
151    }
152
153    #[test]
154    fn test_reverse() {
155        let mut list = vec_into(&[(3, 4), (2, 3), (1, 2), (0, 1)]);
156        assert!(earliest_deadline_sort(&mut list));
157        let list = get_top_level_intervals(list);
158        println!("{:?}", vec_back(&list));
159    }
160
161    #[test]
162    fn test_nested_left() {
163        let mut list = vec_into(&[(0, 1), (0, 2), (0, 3), (0, 4)]);
164        assert!(earliest_deadline_sort(&mut list));
165        let list = get_top_level_intervals(list);
166        println!("{:?}", vec_back(&list));
167        assert!(vec_back(&list) == vec![(0, 4)])
168    }
169
170    #[test]
171    fn test_nested_right() {
172        let mut list = vec_into(&[(1, 5), (2, 5), (3, 5), (4, 5)]);
173        assert!(earliest_deadline_sort(&mut list));
174        let list = get_top_level_intervals(list);
175        println!("{:?}", vec_back(&list));
176        assert!(vec_back(&list) == vec![(1, 5)])
177    }
178
179    #[test]
180    fn overlapping_intervals() {
181        let mut list = vec_into(&[(0, 1), (0, 2), (1, 2), (1, 3)]);
182        assert!(!earliest_deadline_sort(&mut list));
183    }
184
185    #[test]
186    fn another_overlap() {
187        let mut list = vec_into(&[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4)]);
188        assert!(!earliest_deadline_sort(&mut list));
189    }
190
191    #[test]
192    fn multiple_top_level_intervals() {
193        let mut list = vec_into(&[(0, 1), (2, 5), (0, 2), (2, 4), (3, 4), (1, 2), (2, 3)]);
194        assert!(earliest_deadline_sort(&mut list));
195        let list = get_top_level_intervals(list);
196        println!("{:?}", vec_back(&list));
197        assert!(vec_back(&list) == vec![(2, 5), (0, 2)])
198    }
199}
grit_pattern_matcher/intervals.rs

grit_pattern_matcher/
intervals.rs
