rangeset/
lib.rs

1#![doc = include_str!("../README.md")]
2
3mod cover;
4mod difference;
5mod index;
6mod intersection;
7mod subset;
8mod symmetric_difference;
9mod union;
10
11pub use cover::Cover;
12pub use difference::{Difference, DifferenceMut};
13pub use index::IndexRanges;
14pub use intersection::Intersection;
15pub use subset::Subset;
16pub use symmetric_difference::{SymmetricDifference, SymmetricDifferenceMut};
17pub use union::{Union, UnionMut};
18
19use std::ops::{Add, Range, Sub};
20
21/// A set of values represented using ranges.
22///
23/// A `RangeSet` is similar to any other kind of set, such as `HashSet`, with the difference being that the
24/// values in the set are represented using ranges rather than storing each value individually.
25///
26/// # Invariants
27///
28/// `RangeSet` enforces the following invariants on the ranges it contains:
29///
30/// - The ranges are sorted.
31/// - The ranges are non-adjacent.
32/// - The ranges are non-intersecting.
33/// - The ranges are non-empty.
34///
35/// This is enforced in the constructor, and guaranteed to hold after applying any operation on a range or set.
36///
37/// # Examples
38///
39/// ```
40/// use rangeset::*;
41///
42/// let a = 10..20;
43///
44/// // Difference
45/// assert_eq!(a.difference(&(15..25)), RangeSet::from([10..15]));
46/// assert_eq!(a.difference(&(12..15)), RangeSet::from([(10..12), (15..20)]));
47///
48/// // Union
49/// assert_eq!(a.union(&(15..25)), RangeSet::from([10..25]));
50/// assert_eq!(a.union(&(0..0)), RangeSet::from([10..20]));
51///
52/// // Comparison
53/// assert!(a.is_subset(&(0..30)));
54/// assert!(a.is_disjoint(&(0..10)));
55/// assert_eq!(a.clone(), RangeSet::from(a));
56/// ```
57#[derive(Debug, Clone, Hash, PartialEq, Eq)]
58#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
59#[cfg_attr(
60    feature = "serde",
61    serde(
62        bound = "for<'a> T: serde::Serialize + serde::de::Deserialize<'a> + Copy + Ord",
63        from = "Vec<Range<T>>",
64        into = "Vec<Range<T>>"
65    )
66)]
67pub struct RangeSet<T> {
68    /// The ranges of the set.
69    ///
70    /// The ranges *MUST* be sorted, non-adjacent, non-intersecting, and non-empty.
71    ranges: Vec<Range<T>>,
72}
73
74impl<T: Copy + Ord> From<Vec<Range<T>>> for RangeSet<T> {
75    fn from(ranges: Vec<Range<T>>) -> Self {
76        Self::new(&ranges)
77    }
78}
79
80impl<T> From<RangeSet<T>> for Vec<Range<T>> {
81    fn from(ranges: RangeSet<T>) -> Self {
82        ranges.into_inner()
83    }
84}
85
86impl<T: Copy + Ord> Default for RangeSet<T> {
87    fn default() -> Self {
88        Self {
89            ranges: Default::default(),
90        }
91    }
92}
93
94impl<T> RangeSet<T> {
95    /// Returns the ranges of the set.
96    pub fn into_inner(self) -> Vec<Range<T>> {
97        self.ranges
98    }
99
100    /// Returns `true` if the set is empty.
101    pub fn is_empty(&self) -> bool {
102        self.ranges.is_empty()
103    }
104
105    /// Returns the number of ranges in the set.
106    pub fn len_ranges(&self) -> usize {
107        self.ranges.len()
108    }
109
110    /// Clears the set, removing all ranges.
111    pub fn clear(&mut self) {
112        self.ranges.clear();
113    }
114}
115
116impl<T: Copy + Ord> RangeSet<T> {
117    /// Returns a new `RangeSet` from the given ranges.
118    ///
119    /// The `RangeSet` is constructed by computing the union of the given ranges.
120    pub fn new(ranges: &[Range<T>]) -> Self
121    where
122        Self: Union<Range<T>, Output = Self>,
123    {
124        let mut set = Self::default();
125
126        for range in ranges {
127            set = set.union(range);
128        }
129
130        set
131    }
132
133    /// Returns an iterator over the values in the set.
134    pub fn iter(&self) -> RangeSetIter<'_, T> {
135        RangeSetIter {
136            iter: self.ranges.iter(),
137            current: None,
138        }
139    }
140
141    /// Returns an iterator over the ranges in the set.
142    pub fn iter_ranges(&self) -> RangeIter<'_, T> {
143        RangeIter {
144            iter: self.ranges.iter(),
145        }
146    }
147
148    /// Returns `true` if the set contains the given value.
149    pub fn contains(&self, value: &T) -> bool {
150        self.ranges.iter().any(|range| range.contains(value))
151    }
152
153    /// Returns the minimum value in the set, or `None` if the set is empty.
154    pub fn min(&self) -> Option<T> {
155        self.ranges.first().map(|range| range.start)
156    }
157
158    /// Returns the end of right-most range in the set, or `None` if the set is empty.
159    ///
160    /// # Note
161    ///
162    /// This is the *non-inclusive* bound of the right-most range. See `RangeSet::max` for the
163    /// maximum value in the set.
164    pub fn end(&self) -> Option<T> {
165        self.ranges.last().map(|range| range.end)
166    }
167}
168
169impl<T: Copy + Ord + Step + Sub<Output = T>> RangeSet<T> {
170    /// Returns the maximum value in the set, or `None` if the set is empty.
171    pub fn max(&self) -> Option<T> {
172        // This should never underflow because of the invariant that a set
173        // never contains empty ranges.
174        self.ranges
175            .last()
176            .map(|range| Step::backward(range.end, 1).expect("set is not empty"))
177    }
178
179    /// Splits the set into two at the provided value.
180    ///
181    /// Returns a new set containing all the existing elements `>= at`. After the call,
182    /// the original set will be left containing the elements `< at`.
183    ///
184    /// # Panics
185    ///
186    /// Panics if `at` is not in the set.
187    pub fn split_off(&mut self, at: &T) -> Self {
188        // Find the index of the range containing `at`
189        let idx = self
190            .ranges
191            .iter()
192            .position(|range| range.contains(at))
193            .expect("`at` is in the set");
194
195        // Split off the range containing `at` and all the ranges to the right.
196        let mut split_ranges = self.ranges.split_off(idx);
197
198        // If the first range starts before `at` we have to push those values back
199        // into the existing set and truncate.
200        if *at > split_ranges[0].start {
201            self.ranges.push(Range {
202                start: split_ranges[0].start,
203                end: *at,
204            });
205            split_ranges[0].start = *at;
206        }
207
208        Self {
209            ranges: split_ranges,
210        }
211    }
212}
213
214impl<T: Copy + Ord + Sub<Output = T>> RangeSet<T> {
215    /// Shifts every range in the set to the left by the provided offset.
216    ///
217    /// # Panics
218    ///
219    /// Panics if the shift causes an underflow.
220    pub fn shift_left(&mut self, offset: &T) {
221        self.ranges.iter_mut().for_each(|range| {
222            range.start = range.start - *offset;
223            range.end = range.end - *offset;
224        });
225    }
226}
227
228impl<T: Copy + Ord + Add<Output = T>> RangeSet<T> {
229    /// Shifts every range in the set to the right by the provided offset.
230    ///
231    /// # Panics
232    ///
233    /// Panics if the the shift causes an overflow.
234    pub fn shift_right(&mut self, offset: &T) {
235        self.ranges.iter_mut().for_each(|range| {
236            range.start = range.start + *offset;
237            range.end = range.end + *offset;
238        });
239    }
240}
241
242impl<T: Copy + Ord> RangeSet<T>
243where
244    Range<T>: ExactSizeIterator<Item = T>,
245{
246    /// Returns the number of values in the set.
247    #[must_use]
248    pub fn len(&self) -> usize {
249        self.ranges.iter().map(|range| range.len()).sum()
250    }
251}
252
253impl<T: Copy + Ord> TryFrom<RangeSet<T>> for Range<T> {
254    type Error = RangeSet<T>;
255
256    /// Attempts to convert a `RangeSet` into a single `Range`, returning the set if it
257    /// does not contain exactly one range.
258    fn try_from(set: RangeSet<T>) -> Result<Self, Self::Error> {
259        if set.len_ranges() == 1 {
260            Ok(set.ranges.into_iter().next().unwrap())
261        } else {
262            Err(set)
263        }
264    }
265}
266
267impl<T: Copy + Ord> From<Range<T>> for RangeSet<T> {
268    fn from(range: Range<T>) -> Self {
269        if range.is_empty() {
270            return Self::default();
271        }
272
273        Self {
274            ranges: Vec::from([range]),
275        }
276    }
277}
278
279impl<const N: usize, T: Copy + Ord> From<[Range<T>; N]> for RangeSet<T> {
280    fn from(ranges: [Range<T>; N]) -> Self {
281        Self::new(&ranges)
282    }
283}
284
285impl<T: Copy + Ord> From<&[Range<T>]> for RangeSet<T> {
286    fn from(ranges: &[Range<T>]) -> Self {
287        Self::new(ranges)
288    }
289}
290
291impl<T: Copy + Ord> PartialEq<Range<T>> for RangeSet<T> {
292    fn eq(&self, other: &Range<T>) -> bool {
293        self.ranges.len() == 1 && self.ranges[0] == *other
294    }
295}
296
297impl<T: Copy + Ord> PartialEq<Range<T>> for &RangeSet<T> {
298    fn eq(&self, other: &Range<T>) -> bool {
299        *self == other
300    }
301}
302
303impl<T: Copy + Ord> PartialEq<RangeSet<T>> for Range<T> {
304    fn eq(&self, other: &RangeSet<T>) -> bool {
305        other == self
306    }
307}
308
309impl<T: Copy + Ord> PartialEq<RangeSet<T>> for &Range<T> {
310    fn eq(&self, other: &RangeSet<T>) -> bool {
311        other == *self
312    }
313}
314
315/// An iterator over the values in a `RangeSet`.
316pub struct RangeSetIter<'a, T> {
317    iter: std::slice::Iter<'a, Range<T>>,
318    current: Option<Range<T>>,
319}
320
321impl<T> Iterator for RangeSetIter<'_, T>
322where
323    T: Copy + Ord,
324    Range<T>: Iterator<Item = T>,
325{
326    type Item = T;
327
328    fn next(&mut self) -> Option<Self::Item> {
329        if let Some(range) = &mut self.current {
330            if let Some(value) = range.next() {
331                return Some(value);
332            } else {
333                self.current = None;
334                return self.next();
335            }
336        }
337
338        if let Some(range) = self.iter.next() {
339            self.current = Some(range.clone());
340            return self.next();
341        }
342
343        None
344    }
345}
346
347/// An iterator over the ranges in a `RangeSet`.
348pub struct RangeIter<'a, T> {
349    iter: std::slice::Iter<'a, Range<T>>,
350}
351
352impl<T> Iterator for RangeIter<'_, T>
353where
354    T: Copy + Ord,
355    Range<T>: Iterator<Item = T>,
356{
357    type Item = Range<T>;
358
359    fn next(&mut self) -> Option<Self::Item> {
360        self.iter.next().cloned()
361    }
362}
363
364impl<T> ExactSizeIterator for RangeIter<'_, T>
365where
366    T: Copy + Ord,
367    Range<T>: Iterator<Item = T>,
368{
369    fn len(&self) -> usize {
370        self.iter.len()
371    }
372}
373
374impl<T> DoubleEndedIterator for RangeIter<'_, T>
375where
376    T: Copy + Ord,
377    Range<T>: Iterator<Item = T>,
378{
379    fn next_back(&mut self) -> Option<Self::Item> {
380        self.iter.next_back().cloned()
381    }
382}
383
384/// A type which has a corresponding range set.
385pub trait ToRangeSet<T: Copy + Ord> {
386    /// Returns a corresponding range set.
387    fn to_range_set(&self) -> RangeSet<T>;
388}
389
390impl<T: Copy + Ord> ToRangeSet<T> for RangeSet<T> {
391    fn to_range_set(&self) -> RangeSet<T> {
392        self.clone()
393    }
394}
395
396impl<T: Copy + Ord> ToRangeSet<T> for Range<T> {
397    fn to_range_set(&self) -> RangeSet<T> {
398        RangeSet::from(self.clone())
399    }
400}
401
402pub trait Disjoint<Rhs> {
403    /// Returns `true` if the range is disjoint with `other`.
404    #[must_use]
405    fn is_disjoint(&self, other: &Rhs) -> bool;
406}
407
408pub trait Contains<Rhs> {
409    /// Returns `true` if `self` contains `other`.
410    #[must_use]
411    fn contains(&self, other: &Rhs) -> bool;
412}
413
414/// A type which successor and predecessor operations can be performed on.
415///
416/// Similar to `std::iter::Step`, but not nightly-only.
417pub trait Step: Sized {
418    /// Steps forwards by `count` elements.
419    fn forward(start: Self, count: usize) -> Option<Self>;
420
421    /// Steps backwards by `count` elements.
422    fn backward(start: Self, count: usize) -> Option<Self>;
423}
424
425macro_rules! impl_step {
426    ($($ty:ty),+) => {
427        $(
428            impl Step for $ty {
429                fn forward(start: Self, count: usize) -> Option<Self> {
430                    start.checked_add(count as Self)
431                }
432
433                fn backward(start: Self, count: usize) -> Option<Self> {
434                    start.checked_sub(count as Self)
435                }
436            }
437        )*
438    };
439}
440
441impl_step!(
442    u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize
443);
444
445impl<T: Copy + Ord> Disjoint<Range<T>> for Range<T> {
446    fn is_disjoint(&self, other: &Range<T>) -> bool {
447        self.start >= other.end || self.end <= other.start
448    }
449}
450
451impl<T: Copy + Ord> Disjoint<RangeSet<T>> for Range<T> {
452    fn is_disjoint(&self, other: &RangeSet<T>) -> bool {
453        other.ranges.iter().all(|range| self.is_disjoint(range))
454    }
455}
456
457impl<T: Copy + Ord> Disjoint<RangeSet<T>> for RangeSet<T> {
458    fn is_disjoint(&self, other: &RangeSet<T>) -> bool {
459        self.ranges.iter().all(|range| range.is_disjoint(other))
460    }
461}
462
463impl<T: Copy + Ord> Disjoint<Range<T>> for RangeSet<T> {
464    fn is_disjoint(&self, other: &Range<T>) -> bool {
465        other.is_disjoint(self)
466    }
467}
468
469/// Asserts that the ranges of the given set are sorted, non-adjacent, non-intersecting, and non-empty.
470#[cfg(test)]
471pub fn assert_invariants<T: Copy + Ord>(set: &RangeSet<T>) {
472    assert!(set.ranges.windows(2).all(|w| w[0].start < w[1].start
473        && w[0].end < w[1].start
474        && w[0].start < w[0].end
475        && w[1].start < w[1].end));
476}
477
478#[cfg(test)]
479#[allow(clippy::all)]
480mod tests {
481    use super::*;
482    use rstest::*;
483
484    #[test]
485    fn test_range_disjoint() {
486        let a = 10..20;
487
488        // rightward
489        assert!(a.is_disjoint(&(20..30)));
490        // rightward aligned
491        assert!(!a.is_disjoint(&(19..25)));
492        // leftward
493        assert!(a.is_disjoint(&(0..10)));
494        // leftward aligned
495        assert!(!a.is_disjoint(&(5..11)));
496        // rightward subset
497        assert!(!a.is_disjoint(&(15..25)));
498        // leftward subset
499        assert!(!a.is_disjoint(&(5..15)));
500        // superset
501        assert!(!a.is_disjoint(&(5..25)));
502        // equal
503        assert!(!a.is_disjoint(&(10..20)));
504    }
505
506    #[test]
507    fn test_range_set_iter() {
508        let a = RangeSet::from([(10..20), (30..40), (50..60)]);
509
510        let values = a.iter().collect::<Vec<_>>();
511        let expected_values = (10..20).chain(30..40).chain(50..60).collect::<Vec<_>>();
512        assert_eq!(values, expected_values);
513    }
514
515    #[test]
516    fn test_range_iter() {
517        let a = RangeSet::from([(10..20), (30..40), (50..60)]);
518
519        let values = a.iter_ranges().collect::<Vec<_>>();
520        let expected_values = vec![10..20, 30..40, 50..60];
521
522        assert_eq!(values, expected_values);
523
524        let reversed_values = a.iter_ranges().rev().collect::<Vec<_>>();
525        let expected_reversed_values = vec![50..60, 30..40, 10..20];
526
527        assert_eq!(reversed_values, expected_reversed_values);
528
529        let mut iter = a.iter_ranges();
530        assert_eq!(iter.len(), 3);
531        _ = iter.next();
532        assert_eq!(iter.len(), 2);
533    }
534
535    #[rstest]
536    #[case(RangeSet::from([(0..1)]), 0)]
537    #[case(RangeSet::from([(0..5)]), 1)]
538    #[case(RangeSet::from([(0..5), (6..10)]), 4)]
539    #[case(RangeSet::from([(0..5), (6..10)]), 6)]
540    #[case(RangeSet::from([(0..5), (6..10)]), 9)]
541    fn test_range_set_split_off(#[case] set: RangeSet<usize>, #[case] at: usize) {
542        let mut a = set.clone();
543        let b = a.split_off(&at);
544
545        assert!(
546            a.ranges
547                .last()
548                .map(|range| !range.is_empty())
549                .unwrap_or(true)
550        );
551        assert!(
552            b.ranges
553                .first()
554                .map(|range| !range.is_empty())
555                .unwrap_or(true)
556        );
557        assert_eq!(a.len() + b.len(), set.len());
558        assert!(a.iter().chain(b.iter()).eq(set.iter()));
559    }
560
561    #[test]
562    #[should_panic = "`at` is in the set"]
563    fn test_range_set_split_off_panic_not_in_set() {
564        RangeSet::from([0..1]).split_off(&1);
565    }
566
567    #[test]
568    fn test_range_set_shift_left() {
569        let mut a = RangeSet::from([(1..5), (6..10)]);
570        a.shift_left(&1);
571
572        assert_eq!(a, RangeSet::from([(0..4), (5..9)]));
573    }
574
575    #[test]
576    fn test_range_set_shift_right() {
577        let mut a = RangeSet::from([(0..4), (5..9)]);
578        a.shift_right(&1);
579
580        assert_eq!(a, RangeSet::from([(1..5), (6..10)]));
581    }
582
583    #[test]
584    fn test_range_set_max() {
585        assert!(RangeSet::<u8>::default().max().is_none());
586        assert_eq!(RangeSet::from([0..1]).max(), Some(0));
587        assert_eq!(RangeSet::from([0..2]).max(), Some(1));
588        assert_eq!(RangeSet::from([(0..5), (6..10)]).max(), Some(9));
589    }
590}
rangeset/lib.rs

rangeset/
lib.rs
