fast_pull/base/
merge.rs

1extern crate alloc;
2use crate::ProgressEntry;
3use alloc::vec::Vec;
4
5pub trait Merge {
6    fn merge_progress(&mut self, new: ProgressEntry);
7}
8
9impl Merge for Vec<ProgressEntry> {
10    fn merge_progress(&mut self, new: ProgressEntry) {
11        let i = self.partition_point(|x| x.end < new.start);
12        if i == self.len() {
13            self.push(new);
14            return;
15        }
16        if self[i].start <= new.start && self[i].end >= new.end {
17            return;
18        }
19        let mut current_merge = new;
20        let mut j = i;
21        while j < self.len() {
22            let entry = &self[j];
23            if entry.start > current_merge.end {
24                break;
25            }
26            current_merge.start = current_merge.start.min(entry.start);
27            current_merge.end = current_merge.end.max(entry.end);
28            j += 1;
29        }
30        if j > i {
31            self.drain(i..j);
32        }
33        self.insert(i, current_merge);
34    }
35}
36
37#[cfg(test)]
38mod tests {
39    use super::*;
40    use alloc::vec;
41
42    #[test]
43    fn test_merge() {
44        #[allow(clippy::single_range_in_vec_init)]
45        let mut v = vec![1..5, 8..10];
46        v.merge_progress(5..10);
47        assert_eq!(v, vec![1..10]);
48        v.merge_progress(10..20);
49        assert_eq!(v, vec![1..20]);
50        v.merge_progress(30..40);
51        assert_eq!(v, vec![1..20, 30..40]);
52        v.merge_progress(21..40);
53        assert_eq!(v, vec![1..20, 21..40]);
54        v.merge_progress(19..21);
55        assert_eq!(v, vec![1..40]);
56        v.merge_progress(50..60);
57        assert_eq!(v, vec![1..40, 50..60]);
58        v.merge_progress(50..60);
59        assert_eq!(v, vec![1..40, 50..60]);
60        v.merge_progress(52..60);
61        assert_eq!(v, vec![1..40, 50..60]);
62        v.merge_progress(52..53);
63        assert_eq!(v, vec![1..40, 50..60]);
64        v.merge_progress(52..61);
65        assert_eq!(v, vec![1..40, 50..61]);
66        v.merge_progress(62..70);
67        assert_eq!(v, vec![1..40, 50..61, 62..70]);
68        v.merge_progress(40..62);
69        assert_eq!(v, vec![1..70]);
70    }
71}
fast_pull/base/merge.rs

fast_pull/base/
merge.rs
