vulkano/
range_set.rs

1use std::ops::Range;
2
3/// A set of ordered types.
4///
5/// Implemented as an ordered list of ranges that do not touch or overlap.
6#[derive(Clone, Debug, Default)]
7pub struct RangeSet<T>(Vec<Range<T>>);
8
9impl<T: Ord + Copy> RangeSet<T> {
10    /// Returns a new empty `RangeSet`.
11    #[inline]
12    pub fn new() -> Self {
13        RangeSet(Vec::new())
14    }
15
16    /// Returns whether all elements of `range` are contained in the set.
17    #[inline]
18    pub fn contains(&self, elements: Range<T>) -> bool {
19        self.0
20            .iter()
21            .any(|range| range.start <= elements.end && range.end >= elements.end)
22    }
23
24    /// Removes all ranges from the set.
25    #[inline]
26    pub fn clear(&mut self) {
27        self.0.clear();
28    }
29
30    /// Inserts the elements of `range` into the set.
31    pub fn insert(&mut self, elements: Range<T>) {
32        // Find the first range that is not less than `elements`, and the first range that is
33        // greater.
34        let index_start = self
35            .0
36            .iter()
37            .position(|range| range.end >= elements.start)
38            .unwrap_or(self.0.len());
39        let index_end = self
40            .0
41            .iter()
42            .position(|range| range.start > elements.end)
43            .unwrap_or(self.0.len());
44
45        if index_start == index_end {
46            // `elements` fits in between index_start - 1 and index_start.
47            self.0.insert(index_start, elements);
48        } else {
49            // `elements` touches the ranges between index_start and index_end.
50            // Expand `elements` with the touched ranges, then store it in the first.
51            self.0[index_start] = self.0[index_start..index_end]
52                .iter()
53                .fold(elements, |Range { start, end }, range| {
54                    start.min(range.start)..end.max(range.end)
55                });
56            // Delete the remaining elements.
57            self.0.drain(index_start + 1..index_end);
58        }
59    }
60}
vulkano/range_set.rs

vulkano/
range_set.rs
