1 // Copyright (c) 2021 The vulkano developers
2 // Licensed under the Apache License, Version 2.0
3 // <LICENSE-APACHE or
4 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT
5 // license <LICENSE-MIT or https://opensource.org/licenses/MIT>,
6 // at your option. All files in the project carrying such
7 // notice may not be copied, modified, or distributed except
8 // according to those terms.
9 
10 use std::ops::Range;
11 
12 /// A set of ordered types.
13 ///
14 /// Implemented as an ordered list of ranges that do not touch or overlap.
15 #[derive(Clone, Debug, Default)]
16 pub struct RangeSet<T>(Vec<Range<T>>);
17 
18 impl<T: Ord + Copy> RangeSet<T> {
19     /// Returns a new empty `RangeSet`.
20     #[inline]
new() -> Self21     pub fn new() -> Self {
22         RangeSet(Vec::new())
23     }
24 
25     /// Returns whether all elements of `range` are contained in the set.
26     #[inline]
contains(&self, elements: Range<T>) -> bool27     pub fn contains(&self, elements: Range<T>) -> bool {
28         self.0
29             .iter()
30             .any(|range| range.start <= elements.end && range.end >= elements.end)
31     }
32 
33     /// Removes all ranges from the set.
34     #[inline]
clear(&mut self)35     pub fn clear(&mut self) {
36         self.0.clear();
37     }
38 
39     /// Inserts the elements of `range` into the set.
insert(&mut self, elements: Range<T>)40     pub fn insert(&mut self, elements: Range<T>) {
41         // Find the first range that is not less than `elements`, and the first range that is greater.
42         let index_start = self
43             .0
44             .iter()
45             .position(|range| range.end >= elements.start)
46             .unwrap_or(self.0.len());
47         let index_end = self
48             .0
49             .iter()
50             .position(|range| range.start > elements.end)
51             .unwrap_or(self.0.len());
52 
53         if index_start == index_end {
54             // `elements` fits in between index_start - 1 and index_start.
55             self.0.insert(index_start, elements);
56         } else {
57             // `elements` touches the ranges between index_start and index_end.
58             // Expand `elements` with the touched ranges, then store it in the first.
59             self.0[index_start] = self.0[index_start..index_end]
60                 .iter()
61                 .fold(elements, |Range { start, end }, range| {
62                     start.min(range.start)..end.max(range.end)
63                 });
64             // Delete the remaining elements.
65             self.0.drain(index_start + 1..index_end);
66         }
67     }
68 }
69