xi_core_lib/
index_set.rs

1// Copyright 2017 The xi-editor Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! A data structure for manipulating sets of indices (typically used for
16//! representing valid lines).
17
18// Note: this data structure has nontrivial overlap with Subset in the rope
19// crate. Maybe we don't need both.
20
21use std::cmp::{max, min};
22use xi_rope::{RopeDelta, Transformer};
23
24pub struct IndexSet {
25    ranges: Vec<(usize, usize)>,
26}
27
28pub fn remove_n_at<T: Clone>(v: &mut Vec<T>, index: usize, n: usize) {
29    if n == 1 {
30        v.remove(index);
31    } else if n > 1 {
32        let new_len = v.len() - n;
33        for i in index..new_len {
34            v[i] = v[i + n].clone();
35        }
36        v.truncate(new_len);
37    }
38}
39
40impl IndexSet {
41    /// Create a new, empty set.
42    pub fn new() -> IndexSet {
43        IndexSet { ranges: Vec::new() }
44    }
45
46    /// Clear the set.
47    pub fn clear(&mut self) {
48        self.ranges.clear();
49    }
50
51    /// Add the range start..end to the set.
52    pub fn union_one_range(&mut self, start: usize, end: usize) {
53        for i in 0..self.ranges.len() {
54            let (istart, iend) = self.ranges[i];
55            if start > iend {
56                continue;
57            } else if end < istart {
58                self.ranges.insert(i, (start, end));
59                return;
60            } else {
61                self.ranges[i].0 = min(start, istart);
62                let mut j = i;
63                while j + 1 < self.ranges.len() && end >= self.ranges[j + 1].0 {
64                    j += 1;
65                }
66                self.ranges[i].1 = max(end, self.ranges[j].1);
67                remove_n_at(&mut self.ranges, i + 1, j - i);
68                return;
69            }
70        }
71        self.ranges.push((start, end));
72    }
73
74    /// Deletes the given range from the set.
75    pub fn delete_range(&mut self, start: usize, end: usize) {
76        let mut ix = match self.ranges.binary_search_by(|r| r.1.cmp(&start)) {
77            Ok(ix) => ix,
78            Err(ix) => ix,
79        };
80
81        let mut del_from = None;
82        let mut del_len = 0;
83        while ix < self.ranges.len() {
84            if self.ranges[ix].0 >= end {
85                break;
86            }
87
88            if self.ranges[ix].0 < start {
89                if self.ranges[ix].1 > end {
90                    let range = (end, self.ranges[ix].1);
91                    self.ranges.insert(ix + 1, range);
92                }
93                self.ranges[ix].1 = start;
94            } else if self.ranges[ix].1 > end {
95                self.ranges[ix].0 = end;
96            } else {
97                if del_from.is_none() {
98                    del_from = Some(ix);
99                }
100                del_len += 1;
101            }
102
103            ix += 1;
104        }
105
106        if let Some(del_from) = del_from {
107            remove_n_at(&mut self.ranges, del_from, del_len);
108        }
109    }
110
111    /// Return an iterator that yields start..end minus the coverage in this set.
112    pub fn minus_one_range(&self, start: usize, end: usize) -> MinusIter {
113        let mut ranges = &self.ranges[..];
114        while !ranges.is_empty() && start >= ranges[0].1 {
115            ranges = &ranges[1..];
116        }
117        MinusIter { ranges, start, end }
118    }
119
120    /// Computes a new set based on applying a delta to the old set. Collapsed regions are removed
121    /// and contiguous regions are combined.
122    pub fn apply_delta(&self, delta: &RopeDelta) -> IndexSet {
123        let mut ranges: Vec<(usize, usize)> = Vec::new();
124        let mut transformer = Transformer::new(delta);
125        for &(start, end) in &self.ranges {
126            let new_range =
127                (transformer.transform(start, false), transformer.transform(end, false));
128            if new_range.0 == new_range.1 {
129                continue; // remove collapsed regions
130            }
131            if !ranges.is_empty() {
132                let ix = ranges.len() - 1;
133                if ranges[ix].1 == new_range.0 {
134                    ranges[ix] = (ranges[ix].0, new_range.1);
135                    continue;
136                }
137            }
138            ranges.push(new_range);
139        }
140        IndexSet { ranges }
141    }
142
143    #[cfg(test)]
144    fn get_ranges(&self) -> &[(usize, usize)] {
145        &self.ranges
146    }
147}
148
149/// The iterator generated by `minus_one_range`.
150pub struct MinusIter<'a> {
151    ranges: &'a [(usize, usize)],
152    start: usize,
153    end: usize,
154}
155
156impl<'a> Iterator for MinusIter<'a> {
157    type Item = (usize, usize);
158
159    fn next(&mut self) -> Option<(usize, usize)> {
160        while self.start < self.end {
161            if self.ranges.is_empty() || self.end <= self.ranges[0].0 {
162                let result = (self.start, self.end);
163                self.start = self.end;
164                return Some(result);
165            }
166            let result = (self.start, self.ranges[0].0);
167            self.start = self.ranges[0].1;
168            self.ranges = &self.ranges[1..];
169            if result.1 > result.0 {
170                return Some(result);
171            }
172        }
173        None
174    }
175}
176
177impl<'a> DoubleEndedIterator for MinusIter<'a> {
178    fn next_back(&mut self) -> Option<Self::Item> {
179        while self.start < self.end {
180            if self.ranges.is_empty() || self.ranges[self.ranges.len() - 1].1 <= self.start {
181                let result = (self.start, self.end);
182                self.start = self.end;
183                return Some(result);
184            }
185            let last_ix = self.ranges.len() - 1;
186            let result = (self.ranges[last_ix].1, self.end);
187            self.end = self.ranges[last_ix].0;
188            self.ranges = &self.ranges[..last_ix];
189            if result.1 > result.0 {
190                return Some(result);
191            }
192        }
193        None
194    }
195}
196
197#[cfg(test)]
198mod tests {
199    use super::IndexSet;
200
201    #[test]
202    fn empty_behavior() {
203        let e = IndexSet::new();
204        assert_eq!(e.minus_one_range(0, 0).collect::<Vec<_>>(), vec![]);
205        assert_eq!(e.minus_one_range(3, 5).collect::<Vec<_>>(), vec![(3, 5)]);
206    }
207
208    #[test]
209    fn single_range_behavior() {
210        let mut e = IndexSet::new();
211        e.union_one_range(3, 5);
212        assert_eq!(e.minus_one_range(0, 0).collect::<Vec<_>>(), vec![]);
213        assert_eq!(e.minus_one_range(3, 5).collect::<Vec<_>>(), vec![]);
214        assert_eq!(e.minus_one_range(0, 3).collect::<Vec<_>>(), vec![(0, 3)]);
215        assert_eq!(e.minus_one_range(0, 4).collect::<Vec<_>>(), vec![(0, 3)]);
216        assert_eq!(e.minus_one_range(4, 10).collect::<Vec<_>>(), vec![(5, 10)]);
217        assert_eq!(e.minus_one_range(5, 10).collect::<Vec<_>>(), vec![(5, 10)]);
218        assert_eq!(e.minus_one_range(0, 10).collect::<Vec<_>>(), vec![(0, 3), (5, 10)]);
219    }
220
221    #[test]
222    fn two_range_minus() {
223        let mut e = IndexSet::new();
224        e.union_one_range(3, 5);
225        e.union_one_range(7, 9);
226        assert_eq!(e.minus_one_range(0, 0).collect::<Vec<_>>(), vec![]);
227        assert_eq!(e.minus_one_range(3, 5).collect::<Vec<_>>(), vec![]);
228        assert_eq!(e.minus_one_range(0, 3).collect::<Vec<_>>(), vec![(0, 3)]);
229        assert_eq!(e.minus_one_range(0, 4).collect::<Vec<_>>(), vec![(0, 3)]);
230        assert_eq!(e.minus_one_range(4, 10).collect::<Vec<_>>(), vec![(5, 7), (9, 10)]);
231        assert_eq!(e.minus_one_range(5, 10).collect::<Vec<_>>(), vec![(5, 7), (9, 10)]);
232        assert_eq!(e.minus_one_range(8, 10).collect::<Vec<_>>(), vec![(9, 10)]);
233        assert_eq!(e.minus_one_range(0, 10).collect::<Vec<_>>(), vec![(0, 3), (5, 7), (9, 10)]);
234    }
235
236    #[test]
237    fn minus_one_range_double_ended_iter() {
238        let mut e = IndexSet::new();
239        e.union_one_range(3, 5);
240        e.union_one_range(7, 9);
241        e.union_one_range(12, 15);
242
243        let mut iter = e.minus_one_range(4, 13);
244        assert_eq!(iter.next(), Some((5, 7)));
245        assert_eq!(iter.next(), Some((9, 12)));
246        assert_eq!(iter.next(), None);
247
248        let mut iter = e.minus_one_range(4, 13);
249        assert_eq!(iter.next_back(), Some((9, 12)));
250        assert_eq!(iter.next_back(), Some((5, 7)));
251        assert_eq!(iter.next_back(), None);
252
253        let mut iter = e.minus_one_range(4, 13);
254        assert_eq!(iter.next_back(), Some((9, 12)));
255        assert_eq!(iter.next(), Some((5, 7)));
256        assert_eq!(iter.next_back(), None);
257        assert_eq!(iter.next(), None);
258    }
259
260    #[test]
261    fn unions() {
262        let mut e = IndexSet::new();
263        e.union_one_range(3, 5);
264        assert_eq!(e.get_ranges(), &[(3, 5)]);
265        e.union_one_range(7, 9);
266        assert_eq!(e.get_ranges(), &[(3, 5), (7, 9)]);
267        e.union_one_range(1, 2);
268        assert_eq!(e.get_ranges(), &[(1, 2), (3, 5), (7, 9)]);
269        e.union_one_range(2, 3);
270        assert_eq!(e.get_ranges(), &[(1, 5), (7, 9)]);
271        e.union_one_range(4, 6);
272        assert_eq!(e.get_ranges(), &[(1, 6), (7, 9)]);
273        assert_eq!(e.minus_one_range(0, 10).collect::<Vec<_>>(), vec![(0, 1), (6, 7), (9, 10)]);
274
275        e.clear();
276        assert_eq!(e.get_ranges(), &[]);
277        e.union_one_range(3, 4);
278        assert_eq!(e.get_ranges(), &[(3, 4)]);
279        e.union_one_range(5, 6);
280        assert_eq!(e.get_ranges(), &[(3, 4), (5, 6)]);
281        e.union_one_range(7, 8);
282        assert_eq!(e.get_ranges(), &[(3, 4), (5, 6), (7, 8)]);
283        e.union_one_range(9, 10);
284        assert_eq!(e.get_ranges(), &[(3, 4), (5, 6), (7, 8), (9, 10)]);
285        e.union_one_range(11, 12);
286        assert_eq!(e.get_ranges(), &[(3, 4), (5, 6), (7, 8), (9, 10), (11, 12)]);
287        e.union_one_range(2, 10);
288        assert_eq!(e.get_ranges(), &[(2, 10), (11, 12)]);
289    }
290
291    #[test]
292    fn delete_range() {
293        let mut e = IndexSet::new();
294        e.union_one_range(1, 2);
295        e.union_one_range(4, 6);
296        e.union_one_range(6, 7);
297        e.union_one_range(8, 8);
298        e.union_one_range(10, 12);
299        e.union_one_range(13, 14);
300        e.delete_range(5, 11);
301        assert_eq!(e.get_ranges(), &[(1, 2), (4, 5), (11, 12), (13, 14)]);
302
303        let mut e = IndexSet::new();
304        e.union_one_range(1, 2);
305        e.union_one_range(4, 6);
306        e.delete_range(2, 4);
307        assert_eq!(e.get_ranges(), &[(1, 2), (4, 6)]);
308
309        let mut e = IndexSet::new();
310        e.union_one_range(0, 10);
311        e.delete_range(4, 6);
312        assert_eq!(e.get_ranges(), &[(0, 4), (6, 10)]);
313    }
314
315    #[test]
316    fn apply_delta() {
317        use xi_rope::{Delta, Interval, Rope};
318
319        let mut e = IndexSet::new();
320        e.union_one_range(1, 3);
321        e.union_one_range(5, 9);
322
323        let d = Delta::simple_edit(Interval::new(2, 2), Rope::from("..."), 10);
324        let s = e.apply_delta(&d);
325        assert_eq!(s.get_ranges(), &[(1, 6), (8, 12)]);
326
327        let d = Delta::simple_edit(Interval::new(0, 3), Rope::from(""), 10);
328        let s = e.apply_delta(&d);
329        assert_eq!(s.get_ranges(), &[(2, 6)]);
330
331        let d = Delta::simple_edit(Interval::new(2, 6), Rope::from(""), 10);
332        let s = e.apply_delta(&d);
333        assert_eq!(s.get_ranges(), &[(1, 5)]);
334    }
335}
xi_core_lib/index_set.rs

xi_core_lib/
index_set.rs
