range_set/
lib.rs

1//! `RangeSet` container type.
2//!
3//! `RangeSet` stores collections of `PrimInt` values as inclusive ranges using generic
4//! [`SmallVec`](https://docs.rs/smallvec)-backed storage. This means that a certain
5//! amount of ranges will fit on the stack before spilling over to the heap.
6
7use num_traits;
8#[cfg(feature = "derive_serdes")]
9use serde;
10use smallvec;
11
12pub mod range_compare;
13
14pub use range_compare::{
15  RangeCompare, RangeDisjoint, RangeIntersect, range_compare, intersection
16};
17
18use std::ops::RangeInclusive;
19use num_traits::PrimInt;
20use smallvec::SmallVec;
21
22////////////////////////////////////////////////////////////////////////////////////////
23//  structs                                                                           //
24////////////////////////////////////////////////////////////////////////////////////////
25
26/// A set of primitive integers represented as a sorted list of disjoint, inclusive
27/// ranges.
28///
29/// The generic parameter specifies the type of on-stack array to be used in the backing
30/// `SmallVec` storage.
31///
32/// ```
33/// # extern crate smallvec;
34/// # extern crate range_set;
35/// # use range_set::RangeSet;
36/// # use smallvec::SmallVec;
37/// # use std::ops::RangeInclusive;
38/// # fn main() {
39/// let mut s = RangeSet::<[RangeInclusive <u32>; 1]>::from (0..=2);
40/// println!("s: {:?}", s);
41/// assert!(!s.spilled());
42///
43/// assert!(s.insert_range (8..=10).is_none());
44/// println!("s: {:?}", s);
45/// assert!(s.spilled());
46/// let v : Vec <u32> = s.iter().collect();
47/// assert_eq!(v, vec![0,1,2,8,9,10]);
48///
49/// assert_eq!(s.insert_range (3..=12), Some (RangeSet::from (8..=10)));
50/// println!("s: {:?}", s);
51/// assert!(s.spilled());  // once spilled, stays spilled
52/// let v : Vec <u32> = s.iter().collect();
53/// assert_eq!(v, vec![0,1,2,3,4,5,6,7,8,9,10,11,12]);
54/// s.shrink_to_fit();  // manually un-spill
55/// assert!(!s.spilled());
56/// # }
57/// ```
58#[derive(Clone, Debug, Eq)]
59pub struct RangeSet <A> where
60  A       : smallvec::Array + Eq + std::fmt::Debug,
61  A::Item : Clone + Eq + std::fmt::Debug
62{
63  ranges : SmallVec <A>
64}
65
66/// Iterates over elements of the `RangeSet`
67pub struct Iter <'a, A, T> where
68  A : smallvec::Array <Item=RangeInclusive <T>> + Eq + std::fmt::Debug,
69  T : 'a + PrimInt + std::fmt::Debug
70{
71  range_set   : &'a RangeSet <A>,
72  range_index : usize,
73  range       : RangeInclusive <T>
74}
75
76////////////////////////////////////////////////////////////////////////////////////////
77//  functions                                                                         //
78////////////////////////////////////////////////////////////////////////////////////////
79
80/// Tests a slice of ranges for validity as a range set: the element ranges must be
81/// properly disjoint (not adjacent) and sorted.
82///
83/// ```
84/// # extern crate smallvec;
85/// # extern crate range_set;
86/// # use std::ops::RangeInclusive;
87/// # use range_set::*;
88/// # fn main() {
89/// let mut v = Vec::new();
90/// assert!(valid_range_slice (&v));
91/// v.push (0..=3);
92/// assert!(valid_range_slice (&v));
93/// v.push (6..=10);
94/// assert!(valid_range_slice (&v));
95/// v.push (15..=u8::MAX);
96/// assert!(valid_range_slice (&v));
97/// v.push (0..=1);
98/// assert!(!valid_range_slice (&v));
99/// # }
100/// ```
101pub fn valid_range_slice <T, V> (ranges : V) -> bool where
102  T : PartialOrd + PrimInt,
103  V : AsRef <[RangeInclusive <T>]>
104{
105  let ranges = ranges.as_ref();
106  if !ranges.is_empty() {
107    for i in 0..ranges.len()-1 { // safe to subtract here since non-empty
108      let this = &ranges[i];
109      let next = &ranges[i+1];  // safe to index
110      if this.is_empty() || next.is_empty() {
111        return false
112      }
113      if *next.start() <= this.end().saturating_add (T::one()) {
114        return false
115      }
116    }
117  }
118  true
119}
120
121/// Report some sizes of various range set types
122pub fn report_sizes() {
123  use std::mem::size_of;
124  println!("RangeSet report sizes...");
125
126  println!("  size of RangeSet <[RangeInclusive <u32>; 1]>: {}",
127    size_of::<RangeSet <[RangeInclusive <u32>; 1]>>());
128  println!("  size of RangeSet <[RangeInclusive <u16>; 1]>: {}",
129    size_of::<RangeSet <[RangeInclusive <u16>; 1]>>());
130  println!("  size of RangeSet <[RangeInclusive <u32>; 1]>: {}",
131    size_of::<RangeSet <[RangeInclusive <u32>; 1]>>());
132  println!("  size of RangeSet <[RangeInclusive <u64>; 1]>: {}",
133    size_of::<RangeSet <[RangeInclusive <u64>; 1]>>());
134  println!("  size of RangeSet <[RangeInclusive <usize>; 1]>: {}",
135    size_of::<RangeSet <[RangeInclusive <usize>; 1]>>());
136
137  println!("  size of RangeSet <[RangeInclusive <u32>; 2]>: {}",
138    size_of::<RangeSet <[RangeInclusive <u32>; 2]>>());
139  println!("  size of RangeSet <[RangeInclusive <u16>; 2]>: {}",
140    size_of::<RangeSet <[RangeInclusive <u16>; 2]>>());
141  println!("  size of RangeSet <[RangeInclusive <u32>; 2]>: {}",
142    size_of::<RangeSet <[RangeInclusive <u32>; 2]>>());
143  println!("  size of RangeSet <[RangeInclusive <u64>; 2]>: {}",
144    size_of::<RangeSet <[RangeInclusive <u64>; 2]>>());
145  println!("  size of RangeSet <[RangeInclusive <usize>; 2]>: {}",
146    size_of::<RangeSet <[RangeInclusive <usize>; 2]>>());
147
148  println!("  size of RangeSet <[RangeInclusive <u32>; 4]>: {}",
149    size_of::<RangeSet <[RangeInclusive <u32>; 4]>>());
150  println!("  size of RangeSet <[RangeInclusive <u16>; 4]>: {}",
151    size_of::<RangeSet <[RangeInclusive <u16>; 4]>>());
152  println!("  size of RangeSet <[RangeInclusive <u32>; 4]>: {}",
153    size_of::<RangeSet <[RangeInclusive <u32>; 4]>>());
154  println!("  size of RangeSet <[RangeInclusive <u64>; 4]>: {}",
155    size_of::<RangeSet <[RangeInclusive <u64>; 4]>>());
156  println!("  size of RangeSet <[RangeInclusive <usize>; 4]>: {}",
157    size_of::<RangeSet <[RangeInclusive <usize>; 4]>>());
158
159  println!("  size of RangeSet <[RangeInclusive <u32>; 8]>: {}",
160    size_of::<RangeSet <[RangeInclusive <u32>; 8]>>());
161  println!("  size of RangeSet <[RangeInclusive <u16>; 8]>: {}",
162    size_of::<RangeSet <[RangeInclusive <u16>; 8]>>());
163  println!("  size of RangeSet <[RangeInclusive <u32>; 8]>: {}",
164    size_of::<RangeSet <[RangeInclusive <u32>; 8]>>());
165  println!("  size of RangeSet <[RangeInclusive <u64>; 8]>: {}",
166    size_of::<RangeSet <[RangeInclusive <u64>; 8]>>());
167  println!("  size of RangeSet <[RangeInclusive <usize>; 8]>: {}",
168    size_of::<RangeSet <[RangeInclusive <usize>; 8]>>());
169
170  println!("  size of RangeSet <[RangeInclusive <u32>; 16]>: {}",
171    size_of::<RangeSet <[RangeInclusive <u32>; 16]>>());
172  println!("  size of RangeSet <[RangeInclusive <u16>; 16]>: {}",
173    size_of::<RangeSet <[RangeInclusive <u16>; 16]>>());
174  println!("  size of RangeSet <[RangeInclusive <u32>; 16]>: {}",
175    size_of::<RangeSet <[RangeInclusive <u32>; 16]>>());
176  println!("  size of RangeSet <[RangeInclusive <u64>; 16]>: {}",
177    size_of::<RangeSet <[RangeInclusive <u64>; 16]>>());
178  println!("  size of RangeSet <[RangeInclusive <usize>; 16]>: {}",
179    size_of::<RangeSet <[RangeInclusive <usize>; 16]>>());
180
181  println!("...RangeSet report sizes");
182}
183
184////////////////////////////////////////////////////////////////////////////////////////
185//  impls                                                                             //
186////////////////////////////////////////////////////////////////////////////////////////
187
188// the majority of the logic for modifying range sets are the insert_range and
189// remove_range methods
190//
191// there are some helper functions with additional logic such as the binary_search
192// functions
193impl<A, T> Default for RangeSet <A> where
194  A : smallvec::Array <Item=RangeInclusive <T>> + Eq + std::fmt::Debug,
195  T : PrimInt + std::fmt::Debug
196{
197  fn default() -> Self {
198      RangeSet::new()
199  }
200}
201
202impl <A, T> RangeSet <A> where
203  A : smallvec::Array <Item=RangeInclusive <T>> + Eq + std::fmt::Debug,
204  T : PrimInt + std::fmt::Debug
205{
206  /// New empty range set
207  #[inline]
208  pub fn new() -> Self {
209    RangeSet { ranges: SmallVec::new() }
210  }
211
212  /// New empty range set with the internal smallvec initialized with the given initial
213  /// capacity
214  #[inline]
215  pub fn with_capacity (capacity : usize) -> Self {
216    RangeSet { ranges: SmallVec::with_capacity (capacity) }
217  }
218
219  /// Returns a new range set if the given smallvec is valid and sorted
220  /// (`valid_range_slice`)
221  pub fn from_smallvec (ranges : SmallVec <A>) -> Option <Self> {
222    if valid_range_slice (ranges.as_slice()) {
223      Some (RangeSet { ranges })
224    } else {
225      None
226    }
227  }
228
229  /// Unchecked create from smallvec.
230  ///
231  /// # Safety
232  ///
233  /// There is a debug assertion to check if the ranges are valid.
234  pub unsafe fn from_raw_parts (ranges : SmallVec <A>) -> Self {
235    debug_assert!(valid_range_slice (ranges.as_slice()));
236    RangeSet { ranges }
237  }
238
239  /// Returns a new range set if the given slice of ranges is valid and sorted
240  /// (`valid_range_slice`)
241  pub fn from_valid_ranges <V : AsRef <[RangeInclusive <T>]>> (ranges : V)
242    -> Option <Self>
243  {
244    if valid_range_slice (&ranges) {
245      let ranges = SmallVec::from (ranges.as_ref());
246      Some (RangeSet { ranges })
247    } else {
248      None
249    }
250  }
251
252  /// Constructs a new range set from an array or vector of inclusive ranges.
253  ///
254  /// This method has been specially optimized for non-overlapping, non-adjacent ranges
255  /// in ascending order.
256  pub fn from_ranges <V : AsRef <[RangeInclusive <T>]>> (ranges : V) -> Self {
257    let mut ret = RangeSet::new();
258    for range in ranges.as_ref() {
259      ret.insert_range_optimistic(range.clone());
260    }
261    ret
262  }
263
264  /// Constructs a new range set from a slice of numbers.
265  ///
266  /// This method has been specially optimized for deduplicated arrays, sorted in
267  /// ascending order. Construction time is O(n) for these arrays.
268  ///
269  /// ```
270  /// # use range_set::{RangeSet, range_set};
271  /// # use std::ops::RangeInclusive;
272  ///
273  /// let reference = range_set![1..=4, 6, 8..=10, (u32::MAX); 4];
274  ///
275  /// // Optimal ordering. Special O(n) applies.
276  /// let good = RangeSet::<[RangeInclusive<u32>; 4]>::from_elements([1, 2, 3, 4, 6, 8, 9, 10, u32::MAX]);
277  ///
278  /// // Random ordering. Very expensive.
279  /// let bad = RangeSet::<[RangeInclusive<u32>; 4]>::from_elements([2, 9, 6, 8, 1, u32::MAX, 4, 10, 3, 4, 8]);
280  ///
281  /// assert_eq!(good, reference);
282  /// assert_eq!(bad, reference);
283  /// ```
284  pub fn from_elements <V : AsRef <[T]>> (elements : V) -> Self {
285    let mut current_range : Option<(T, T)> = None;
286    let mut set = RangeSet::new();
287
288    for &element in elements.as_ref() {
289      // current_range is updated every iteration.
290      current_range = if let Some((start, end)) = current_range {
291        if element == end.saturating_add (T::one()) {
292          Some((start, element))
293        } else {
294          set.insert_range_optimistic(start..=end);
295          Some((element, element))
296        }
297      } else {
298        Some((element, element))
299      };
300    }
301
302    if let Some((start, end)) = current_range {
303      set.insert_range_optimistic(start..=end);
304    }
305
306    set
307  }
308
309  /// Check if range set is empty
310  #[inline]
311  pub fn is_empty (&self) -> bool {
312    self.ranges.is_empty()
313  }
314
315  /// Return the number of elements in the set.
316  ///
317  /// ```
318  /// # use range_set::range_set;
319  /// let s = range_set![1,2,3,6,7,11,12,13];
320  /// assert_eq!(s.len(), 8);
321  /// ```
322  #[inline]
323  pub fn len (&self) -> usize where T : num_traits::AsPrimitive <usize> {
324    self.ranges.iter().map (|r| r.end().as_() - r.start().as_() + 1).sum()
325  }
326
327  /// Clears the range set
328  #[inline]
329  pub fn clear (&mut self) {
330    self.ranges.clear()
331  }
332
333  /// Converts into the internal smallvec
334  #[inline]
335  pub fn into_smallvec (self) -> SmallVec <A> {
336    self.ranges
337  }
338
339  /// Returns true if the element is contained in this set.
340  ///
341  /// ```
342  /// # use range_set::RangeSet;
343  /// # use std::ops::RangeInclusive;
344  /// let mut set = RangeSet::<[RangeInclusive <u32>; 4]>::new();
345  /// set.insert_range(2..=5);
346  /// set.insert_range(10..=70);
347  /// set.insert(72);
348  /// set.insert_range(74..=80);
349  ///
350  /// assert!(set.contains(2));
351  /// assert!(set.contains(3));
352  /// assert!(set.contains(33));
353  /// assert!(set.contains(72));
354  /// assert!(set.contains(80));
355  ///
356  /// assert!(!set.contains(0));
357  /// assert!(!set.contains(6));
358  /// assert!(!set.contains(71));
359  /// assert!(!set.contains(122));
360  /// ```
361  pub fn contains (&self, element : T) -> bool {
362    self.contains_range(element..=element)
363  }
364
365  /// Returns true if all the elements of `range` are contained in this set.
366  ///
367  /// ```
368  /// # use range_set::RangeSet;
369  /// # use std::ops::RangeInclusive;
370  /// let mut set = RangeSet::<[RangeInclusive <u32>; 4]>::new();
371  /// set.insert_range(2..=5);
372  /// set.insert_range(10..=70);
373  /// set.insert(72);
374  /// set.insert_range(74..=80);
375  ///
376  /// assert!(set.contains_range(2..=4));
377  /// assert!(set.contains_range(3..=5));
378  /// assert!(set.contains_range(33..=50));
379  /// assert!(set.contains_range(75..=80));
380  ///
381  /// assert!(!set.contains_range(0..=6));
382  /// assert!(!set.contains_range(3..=6));
383  /// assert!(!set.contains_range(10..=72));
384  /// assert!(!set.contains_range(50..=75));
385  /// assert!(!set.contains_range(71..=72));
386  /// assert!(!set.contains_range(122..=200));
387  /// ```
388  pub fn contains_range (&self, range : A::Item) -> bool {
389    self.contains_range_ref(&range)
390  }
391
392  /// Returns `true` if the set is a superset of another, i.e., `self` contains at least
393  /// all the elements in `other`.
394  ///
395  /// ```
396  /// # use range_set::RangeSet;
397  /// # use std::ops::RangeInclusive;
398  ///
399  /// let main = RangeSet::<[RangeInclusive<u32>; 1]>::from(3..=15);
400  /// let mut superset = RangeSet::from(0..=15);
401  ///
402  /// assert!(superset.is_superset(&main));
403  /// superset.remove(8);
404  /// assert!(!superset.is_superset(&main));
405  /// ```
406  pub fn is_superset (&self, other : &Self) -> bool {
407    other.is_subset(self)
408  }
409
410  /// Returns `true` if the set is a subset of another, i.e., `other` contains at least
411  /// all the elements in `self`.
412  ///
413  /// ```
414  /// # use range_set::RangeSet;
415  /// # use std::ops::RangeInclusive;
416  ///
417  /// let main = RangeSet::<[RangeInclusive<u32>; 1]>::from(3..=15);
418  /// let mut subset = RangeSet::from(6..=10);
419  ///
420  /// assert!(subset.is_subset(&main));
421  /// subset.insert(99);
422  /// assert!(!subset.is_subset(&main));
423  /// ```
424  pub fn is_subset (&self, other : &Self) -> bool {
425    self.ranges.iter().all(|range| other.contains_range_ref (range))
426  }
427
428  /// Returns the largest element in the set, or `None` if the set is empty.
429  pub fn max (&self) -> Option <T> {
430    self.ranges.last().map(|r| *r.end())
431  }
432
433  /// Returns the smallest element in the set, or `None` if the set is empty.
434  pub fn min (&self) -> Option <T> {
435    self.ranges.first().map(|r| *r.start())
436  }
437
438  /// Insert a single element, returning true if it was successfully inserted or else
439  /// false if it was already present.
440  ///
441  /// ```
442  /// # use range_set::RangeSet;
443  /// # use std::ops::RangeInclusive;
444  /// type R = [RangeInclusive <u32>; 2];
445  /// let mut s = RangeSet::<R>::new();
446  /// assert!(s.insert (4));
447  /// assert_eq!(s, RangeSet::<R>::from (4..=4));
448  /// assert!(!s.insert (4));
449  /// assert_eq!(s, RangeSet::<R>::from (4..=4));
450  /// assert!(s.insert (5));
451  /// assert_eq!(s, RangeSet::<R>::from (4..=5));
452  /// assert!(s.insert (3));
453  /// assert_eq!(s, RangeSet::<R>::from (3..=5));
454  /// assert!(s.insert (10));
455  /// assert_eq!(s, RangeSet::<R>::from_ranges ([3..=5, 10..=10]));
456  /// ```
457  pub fn insert (&mut self, element : T) -> bool {
458    self.insert_range (element..=element).is_none()
459  }
460
461  /// Remove a single element, returning true if it was successfully removed or else
462  /// false if it was not present.
463  ///
464  /// ```
465  /// # use range_set::RangeSet;
466  /// # use std::ops::RangeInclusive;
467  /// type R = [RangeInclusive <u32>; 2];
468  /// let mut s = RangeSet::<R>::from (0..=5);
469  /// assert!(s.remove (1));
470  /// assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 2..=5]));
471  /// assert!(!s.remove (1));
472  /// assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 2..=5]));
473  /// assert!(s.remove (4));
474  /// assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 2..=3, 5..=5]));
475  /// assert!(s.remove (3));
476  /// assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 2..=2, 5..=5]));
477  /// assert!(s.remove (2));
478  /// assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 5..=5]));
479  /// assert!(s.remove (0));
480  /// assert_eq!(s, RangeSet::<R>::from (5..=5));
481  /// assert!(s.remove (5));
482  /// assert!(s.is_empty());
483  /// ```
484  pub fn remove (&mut self, element : T) -> bool {
485    self.remove_range (element..=element).is_some()
486  }
487
488  /// Returns the intersected values if the range is not disjoint with the curret range
489  /// set.
490  ///
491  /// ```
492  /// # use range_set::RangeSet;
493  /// # use std::ops::RangeInclusive;
494  /// let mut s = RangeSet::<[RangeInclusive <u32>; 2]>::from (0..=5);
495  /// assert_eq!(s.insert_range ( 3..=10), Some (RangeSet::from (3..=5)));
496  /// assert_eq!(s.insert_range (20..=30), None);
497  /// ```
498  pub fn insert_range (&mut self, range : A::Item) -> Option <Self> {
499    if range.is_empty () {       // empty range
500      return None
501    }
502    if self.ranges.is_empty() { // empty range set
503      self.ranges.push (range);
504      return None
505    }
506    let before = Self::binary_search_before_proper (self, &range);
507    let after  = Self::binary_search_after_proper  (self, &range);
508    match (before, after) {
509      // no existing ranges are properly greater than or less than the range: this means
510      // that both the first range and the last range are either intersected with or
511      // adjacent to the given range, implying that the range set will be fused to a
512      // single range containing the min and max of the intersection of the given range
513      // and the existing range set
514      (None, None) => {
515        let isect = self.range_intersection (&range, 0..self.ranges.len());
516        let new_range =
517          std::cmp::min (*range.start(), *self.ranges[0].start())..=
518          std::cmp::max (*range.end(),   *self.ranges[self.ranges.len()-1].end());
519        self.ranges.clear();
520        self.ranges.push (new_range);
521        if !isect.is_empty() {
522          Some (isect)
523        } else {
524          None
525        }
526      }
527      // there exist some ranges that are properly less than the given range
528      (Some (before), None) => {
529        if before+1 == self.ranges.len() {  // push after last range
530          self.ranges.push (range);
531          None
532        } else {  // otherwise merge into last range
533          let isect = self.range_intersection (&range, before+1..self.ranges.len());
534          self.ranges[before+1] =
535            std::cmp::min (*range.start(), *self.ranges[before+1].start())..=
536            std::cmp::max (*range.end(), *self.ranges[self.ranges.len()-1].end());
537          self.ranges.truncate (before+2);
538          if !isect.is_empty() {
539            Some (isect)
540          } else {
541            None
542          }
543        }
544      }
545      // there exist some ranges that are properly greater than the given range
546      (None, Some (after)) => {
547        if after == 0 { // insert before first range
548          self.ranges.insert (0, range);
549          None
550        } else {        // otherwise merge into first range
551          let isect = self.range_intersection (&range, 0..after);
552          self.ranges[0] =
553            std::cmp::min (*range.start(), *self.ranges[0].start())..=
554            std::cmp::max (*range.end(), *self.ranges[after - 1].end());
555          self.ranges.as_mut_slice()[1..].rotate_left(after - 1);
556          let new_len = self.ranges.len() - after + 1;
557          self.ranges.truncate (new_len);
558          if !isect.is_empty() {
559            Some (isect)
560          } else {
561            None
562          }
563        }
564      }
565      // there are ranges both properly less than and properly greater than the given
566      // range
567      (Some (before), Some (after)) => {
568        if before+1 == after {  // insert between ranges
569          self.ranges.insert (before+1, range);
570          None
571        } else {                // otherwise merge with existing ranges
572          let isect = self.range_intersection (&range, before+1..after);
573          self.ranges[before+1] =
574            std::cmp::min (*range.start(), *self.ranges[before+1].start())..=
575            std::cmp::max (*range.end(), *self.ranges[after-1].end());
576          // if there are more than one ranges between we must shift and truncate
577          if 1 < after - before - 1 {
578            self.ranges.as_mut_slice()[(before + 2)..].rotate_left (after - before - 2);
579            let new_len = self.ranges.len() - (after - before - 2);
580            self.ranges.truncate (new_len);
581          }
582          if !isect.is_empty() {
583            Some (isect)
584          } else {
585            None
586          }
587        }
588      }
589    }
590  } // end fn insert_range
591
592  /// This is like `insert_range`, but has O(1) runtime if `range` is placed at the end
593  /// of the set.
594  fn insert_range_optimistic (&mut self, range : A::Item) {
595    if let Some(last) = self.ranges.last() {
596      if last.end().saturating_add (T::one()) < *range.start() {
597        self.ranges.push(range);
598      } else {
599        // Fallback on normal insert, and discard the return value.
600        self.insert_range(range);
601      }
602    } else {
603      // Ranges is empty.
604      self.ranges.push(range);
605    }
606  }
607
608  /// Removes and returns the intersected elements, if there were any.
609  ///
610  /// ```
611  /// # use range_set::RangeSet;
612  /// # use std::ops::RangeInclusive;
613  /// let mut s = RangeSet::<[RangeInclusive <u32>; 2]>::from (0..=5);
614  /// assert_eq!(s.remove_range (3..=3), Some (RangeSet::from (3..=3)));
615  /// assert_eq!(s, RangeSet::<[_; 2]>::from_ranges ([0..=2, 4..=5]));
616  /// assert_eq!(s.remove_range (0..=10),
617  ///   Some (RangeSet::<[_; 2]>::from_ranges ([0..=2, 4..=5])));
618  /// assert!(s.is_empty());
619  /// ```
620  pub fn remove_range (&mut self, range : A::Item) -> Option <Self> {
621    if self.ranges.is_empty() || range.is_empty() {  // empty
622      return None
623    }
624    let before = Self::binary_search_before (self, &range);
625    let after  = Self::binary_search_after  (self, &range);
626    // non-inclusive range of ranges to check for intersection
627    let (isect_first, isect_last) = match (before, after) {
628      (None, None)                  => (0, self.ranges.len()),
629      (Some (before), None)         => (before+1, self.ranges.len()),
630      (None, Some (after))          => (0, after),
631      (Some (before), Some (after)) => (before+1, after)
632    };
633    let isect = self.range_intersection (&range, isect_first..isect_last);
634    if isect.is_empty() {
635      return None
636    }
637
638    // a split range is only possible if there was a single intersection
639    if isect_last - isect_first == 1 {
640      let single_range = self.ranges[isect_first].clone();
641      if single_range.start() < range.start() && range.end() < single_range.end() {
642        let left  = *single_range.start()..=*range.start() - T::one();
643        let right = *range.end() + T::one()..=*single_range.end();
644        self.ranges[isect_first] = right;
645        self.ranges.insert (isect_first, left);
646        return Some (isect)
647      }
648    }
649
650    // one or more range intersected: the range of intersected ranges will be reduced to
651    // zero, one, or two ranges
652    let first = self.ranges[isect_first].clone();
653    let last  = self.ranges[isect_last-1].clone();
654
655    let (remove_first, remove_last) = if
656    // all intersected ranges removed: shift higher ranges down
657      range.start() <= first.start() && last.end() <= range.end()
658    {
659      (isect_first, isect_last)
660    // first intersected range remains but is shortened
661    } else if first.start() < range.start() && last.end() <= range.end() {
662      self.ranges[isect_first] =
663        *self.ranges[isect_first].start()..=*range.start() - T::one();
664      (isect_first+1, isect_last)
665    // last intersected range remains but is shortened
666    } else if range.start() <= first.start() && range.end() < last.end() {
667      self.ranges[isect_last-1] =
668        *range.end() + T::one()..=*self.ranges[isect_last-1].end();
669      (isect_first, isect_last-1)
670    // both first and last range remain and are shortened
671    } else {
672      debug_assert!(first.start() < range.start() && range.end() < last.end());
673      self.ranges[isect_first] =
674        *self.ranges[isect_first].start()..=*range.start() - T::one();
675      self.ranges[isect_last-1] =
676        *range.end() + T::one()..=*self.ranges[isect_last-1].end();
677      (isect_first+1, isect_last-1)
678    };
679    // remove ranges, shift later ranges and truncate
680    for (i, index) in (remove_last..self.ranges.len()).enumerate() {
681      self.ranges[remove_first+i] = self.ranges[index].clone();
682    }
683    let new_len = self.ranges.len() - (remove_last - remove_first);
684    self.ranges.truncate (new_len);
685
686    debug_assert!(self.is_valid());
687    Some (isect)
688  }
689
690  /// Performs a set union of two `RangeSets`
691  ///
692  /// ```
693  /// # use range_set::{range_set, RangeSet};
694  ///
695  /// let mut s = range_set![1..=5, 7..=10, 25..= 28];
696  /// let mut o = range_set![3..=9, 13..=29];
697  /// let new = s.union(&o);
698  /// assert_eq!(new, range_set![1..=10, 13..=29]);
699  /// o = range_set![0..=12];
700  /// let new = new.union(&o);
701  /// assert_eq!(new, range_set![0..=29]);
702  /// ```
703  pub fn union (&self, other : &Self) -> Self where A : Clone {
704    let mut new = (*self).clone();
705    other.ranges.iter().cloned().for_each (|r| { new.insert_range (r); });
706    new
707  }
708
709  /// Iterate over elements of the `RangeSet`.
710  ///
711  /// To iterate over individual ranges, use `range_set.as_ref().iter()` instead.
712  #[expect(mismatched_lifetime_syntaxes)]
713  pub fn iter (&self) -> Iter <A, T> {
714    Iter {
715      range_set:   self,
716      range_index: 0,
717      range:       T::one()..=T::zero()
718    }
719  }
720
721  /// Calls `spilled` on the underlying smallvec
722  #[inline]
723  pub fn spilled (&self) -> bool {
724    self.ranges.spilled()
725  }
726
727  /// Calls `shrink_to_fit` on the underlying smallvec
728  #[inline]
729  pub fn shrink_to_fit (&mut self) {
730    self.ranges.shrink_to_fit()
731  }
732
733  /// Insert helper function: search for the last range in self that is
734  /// `LessThanAdjacent` or `LessThanProper` when compared with the given range
735  fn binary_search_before (&self, range : &A::Item) -> Option <usize> {
736    let mut before = 0;
737    let mut after  = self.ranges.len();
738    let mut found  = false;
739    while before != after {
740      let i = before + (after - before) / 2;
741      let last = before;
742      if self.ranges[i].end() < range.start() {
743        found  = true;
744        before = i;
745        if before == last {
746          break
747        }
748      } else {
749        after = i
750      }
751    }
752    if found {
753      Some (before)
754    } else {
755      None
756    }
757  }
758
759  /// Insert helper function: search for the first range in self that is
760  /// `GreaterThanAdjacent` or `GreaterThanProper` when compared with the given range
761  fn binary_search_after (&self, range : &A::Item) -> Option <usize> {
762    let mut before = 0;
763    let mut after  = self.ranges.len();
764    let mut found  = false;
765    while before != after {
766      let i    = before + (after - before) / 2;
767      let last = before;
768      if range.end() < self.ranges[i].start() {
769        found = true;
770        after = i;
771      } else {
772        before = i;
773        if before == last {
774          break
775        }
776      }
777    }
778    if found {
779      Some (after)
780    } else {
781      None
782    }
783  }
784
785  /// Insert helper function: search for the last range in self that is `LessThanProper`
786  /// when compared with the given range
787  fn binary_search_before_proper (&self, range : &A::Item) -> Option <usize> {
788    let mut before = 0;
789    let mut after  = self.ranges.len();
790    let mut found  = false;
791    while before != after {
792      let i = before + (after - before) / 2;
793      let last = before;
794      if self.ranges[i].end().saturating_add (T::one()) < *range.start() {
795        found  = true;
796        before = i;
797        if before == last {
798          break
799        }
800      } else {
801        after = i
802      }
803    }
804    if found {
805      Some (before)
806    } else {
807      None
808    }
809  }
810
811  /// Insert helper function: search for the first range in self that is
812  /// `GreaterThanProper` when compared with the given range
813  fn binary_search_after_proper (&self, range : &A::Item) -> Option <usize> {
814    let mut before = 0;
815    let mut after  = self.ranges.len();
816    let mut found  = false;
817    while before != after {
818      let i    = before + (after - before) / 2;
819      let last = before;
820      if range.end().saturating_add (T::one()) < *self.ranges[i].start() {
821        found = true;
822        after = i;
823      } else {
824        before = i;
825        if before == last {
826          break
827        }
828      }
829    }
830    if found {
831      Some (after)
832    } else {
833      None
834    }
835  }
836
837  /// See documentation for `contains_range`. By-reference version needed for
838  /// `is_subset`
839  fn contains_range_ref (&self, range : &A::Item) -> bool {
840    if range.is_empty() {
841      return true
842    }
843    if self.ranges.is_empty() {
844      return false
845    }
846    // Look for any the highest range completely before the requested elements.
847    let test_range = if let Some(before) = self.binary_search_before(range) {
848      // The very next range must either overlap with the requested elements, or must be
849      // greater than all requested elements.
850      if let Some(next) = self.ranges.get(before + 1) {
851        next
852      } else {
853        // There are no other ranges to check.
854        return false
855      }
856    } else {
857      // There are no ranges completely before the requested elements, so try the first
858      // range. This index operation cannot fail, because we checked
859      // self.ranges.is_empty() above.
860      &self.ranges[0]
861    };
862    // Check if that range contains all the requested elements.
863    test_range.contains(range.start()) && test_range.contains(range.end())
864  }
865
866  /// Return the intersection of a given range with the given range of ranges in self
867  fn range_intersection (&self, range : &A::Item, range_range : std::ops::Range <usize>)
868    -> Self
869  {
870    let mut isect = RangeSet::new();
871    for i in range_range {
872      let r     = &self.ranges[i];
873      let rsect = intersection (range, r);
874      if !rsect.is_empty() {
875        isect.ranges.push (rsect);
876      }
877    }
878    debug_assert!(isect.is_valid());
879    isect
880  }
881
882  /// Internal validity check: all ranges are non-empty, disjoint proper with respect to
883  /// one another, and sorted.
884  ///
885  /// Invalid range sets should be impossible to create so this function is not exposed
886  /// to the user.
887  #[inline]
888  fn is_valid (&self) -> bool {
889    valid_range_slice (&self.ranges)
890  }
891}
892
893impl <A, T> From <RangeInclusive <T>> for RangeSet <A> where
894  A : smallvec::Array <Item=RangeInclusive <T>> + Eq + std::fmt::Debug,
895  T : PrimInt + std::fmt::Debug
896{
897  fn from (range : RangeInclusive <T>) -> Self {
898    let ranges = {
899      let mut v = SmallVec::new();
900      v.push (range);
901      v
902    };
903    RangeSet { ranges }
904  }
905}
906
907impl <A, T> AsRef <SmallVec <A>> for RangeSet <A> where
908  A : smallvec::Array <Item=RangeInclusive <T>> + Eq + std::fmt::Debug,
909  T : PrimInt + std::fmt::Debug
910{
911  fn as_ref (&self) -> &SmallVec <A> {
912    &self.ranges
913  }
914}
915
916/// This is a better `PartialEq` implementation than the derived one; it's generic over
917/// array sizes. Smallvec's array length should be an internal implementation detail,
918/// and shouldn't affect whether two `RangeSets` are equal.
919impl<A, B> PartialEq<RangeSet<B>> for RangeSet<A> where
920  A       : smallvec::Array + Eq + std::fmt::Debug,
921  A::Item : Clone + Eq + std::fmt::Debug,
922  B       : smallvec::Array<Item = A::Item> + Eq + std::fmt::Debug
923{
924  fn eq(&self, other : &RangeSet<B>) -> bool {
925    self.ranges.eq(&other.ranges)
926  }
927}
928
929impl <A, T> Iterator for Iter <'_, A, T> where
930  A : smallvec::Array <Item=RangeInclusive <T>> + Eq + std::fmt::Debug,
931  T : PrimInt + std::fmt::Debug,
932  RangeInclusive <T> : Clone + Iterator <Item=T>
933{
934  type Item = T;
935  fn next (&mut self) -> Option <Self::Item> {
936    if let Some (t) = self.range.next() {
937      Some (t)
938    } else if self.range_index < self.range_set.ranges.len() {
939      self.range = self.range_set.ranges[self.range_index].clone();
940      debug_assert!(!self.range.is_empty());
941      self.range_index += 1;
942      self.range.next()
943    } else {
944      None
945    }
946  }
947}
948
949#[cfg(feature = "derive_serdes")]
950impl<A, T> serde::Serialize for RangeSet<A> where
951  A : smallvec::Array <Item=RangeInclusive <T>> + Eq + std::fmt::Debug,
952  T : PrimInt + std::fmt::Debug + serde::Serialize,
953{
954  fn serialize <S: serde::Serializer> (&self, serializer: S) -> Result<S::Ok, S::Error> {
955    self.ranges.serialize(serializer)
956  }
957}
958
959#[cfg(feature = "derive_serdes")]
960impl<'de, A, T> serde::Deserialize<'de> for RangeSet<A> where
961  A : smallvec::Array <Item=RangeInclusive <T>> + Eq + std::fmt::Debug,
962  T : PrimInt + std::fmt::Debug + serde::Deserialize<'de>,
963{
964  fn deserialize <D: serde::Deserializer<'de>> (deserializer: D)
965    -> Result<Self, D::Error>
966  {
967    let ranges = SmallVec::deserialize(deserializer)?;
968
969    Ok(RangeSet { ranges })
970  }
971}
972
973////////////////////////////////////////////////////////////////////////////////////////
974//  macros                                                                            //
975////////////////////////////////////////////////////////////////////////////////////////
976
977/// The default size of the inner smallvec's on-stack array.
978pub const DEFAULT_RANGE_COUNT: usize = 4;
979
980/// Convenient macro to construct `RangeSets` without needing bulky notation like
981/// `::<[RangeInclusive<_>; _]>`.  The macro allows a mix of numbers and inclusive
982/// ranges, with an optional length at the end for the smallvec array size. If the
983/// length is not specified, it will default to 4.
984///
985/// The implementation guarantees `O(n)` construction time for lists of non-adjacent mix
986/// of increasing-ranges and numbers in increasing order. See [`RangeSet::from_ranges`]
987/// for more information about this optimization.  Single numbers are transformed into
988/// one-element inclusive ranges (`5` becomes `5..=5`).
989///
990/// Separately, the implementation guarantees `O(n)` construction time for lists of
991/// numbers (not ranges) sorted in increasing order and deduplicated. See
992/// `[RangeSet::from_elements`] for more information about this optimization.
993///
994/// All other cases are reasonably performant, `O(n * log(n))` on average.
995/// ```
996/// # use range_set::{RangeSet, range_set};
997/// # use std::ops::RangeInclusive;
998///
999/// let case1 = RangeSet::<[RangeInclusive<u32>; 3]>::from_valid_ranges ([0..=0, 2..=5]).unwrap();
1000/// let case2 = RangeSet::<[RangeInclusive<u32>; 4]>::from_valid_ranges ([1..=3, 6..=15, 40..=40, 42..=50]).unwrap();
1001/// const FIVE: u32 = 5;
1002/// let some_func = |x: u32| x;
1003/// let your_var = 0;
1004///
1005/// // The fastest format to use is non-adjacent, increasing ranges in increasing order.
1006/// assert_eq!(range_set![0, 2..=5; 3], case1);
1007/// assert_eq!(range_set![1..=3, 6..=15, 40, 42..=50; 4], case2);
1008///
1009/// // The smallvec size is optional, and defaults to 4.
1010/// assert_eq!(range_set![1..=3, 6..=15, 40, 42..=50], case2);
1011///
1012/// // A wide variety of other formats are available. Complex expressions need to be surrounded
1013/// // by parentheses.
1014/// assert_eq!(range_set![0, 2, 3..=5; 3], case1);
1015/// assert_eq!(range_set![0, 2, (1 + 2), 4, FIVE; 3], case1);
1016/// assert_eq!(range_set![0, 2, (some_func(3)), 4, 5; 3], case1);
1017/// assert_eq!(range_set![your_var, 2..=(some_func(5)); 3], case1);
1018///
1019/// // Expressions that return ranges need to be marked using "as range":
1020/// let my_range = 2..=5;
1021/// assert_eq!(range_set![0, my_range as range; 3], case1);
1022///
1023/// // Empty lists are still allowed. Rust may have trouble inferring the number type/size
1024/// // in some situations.
1025/// assert_eq!(range_set![], RangeSet::<[RangeInclusive<u32>; 4]>::new());
1026/// assert_eq!(range_set![; 3], RangeSet::<[RangeInclusive<u32>; 3]>::new());
1027/// ```
1028#[macro_export]
1029macro_rules! range_set {
1030  // Empty cases: use `new`
1031  () => {
1032    $crate::RangeSet::<[core::ops::RangeInclusive<_>; $crate::DEFAULT_RANGE_COUNT]>::new()
1033  };
1034  ( ; $len:expr ) => {
1035    $crate::RangeSet::<[core::ops::RangeInclusive<_>; $len]>::new()
1036  };
1037
1038  // Pure number case: Use the faster `from_elements` for just numbers, if possible.
1039  ( $( $num:tt ),+ ) => {
1040    $crate::range_set![ $( $num ),+ ; $crate::DEFAULT_RANGE_COUNT ]
1041  };
1042  ( $( $num:tt ),+ ; $len:expr ) => {
1043    $crate::RangeSet::<[core::ops::RangeInclusive<_>; $len]>::from_elements([ $( $num ),+ ])
1044  };
1045
1046  // Mixed literal cases: We can support mixing numbers and ranges IF everything is a literal
1047  ( $( $start:tt $( ..= $end:tt )? $( as $range_keyword:tt )? ),+ ) => {
1048    $crate::range_set![ $( $start $(..= $end )? ),+ ; $crate::DEFAULT_RANGE_COUNT ]
1049  };
1050  ( $( $start:tt $( ..= $end:tt )? $( as $range_keyword:tt )? ),+ ; $len:expr ) => {
1051    $crate::RangeSet::<[core::ops::RangeInclusive<_>; $len]>::from_ranges([ $( $crate::__range_set_helper!($start $( ..= $end )? $( as $range_keyword )? ) ),+ ])
1052  };
1053}
1054
1055/// Helper macro that resolves the ambiguity between literal numbers and literal ranges.
1056#[macro_export]
1057#[doc(hidden)]
1058macro_rules! __range_set_helper {
1059  ( $num:tt ) => { { let val = $num; val ..= val } };
1060  ( $start:tt ..= $end:tt ) => ( $start ..= $end );
1061  ( $range_expr:tt as range) => ( $range_expr );
1062}
1063
1064#[cfg(test)]
1065mod tests {
1066  use std::ops::RangeInclusive;
1067  use crate::RangeSet;
1068
1069  #[test]
1070  fn merge_multiple() {
1071    let mut range_set: RangeSet<[RangeInclusive<u32>; 2]> = RangeSet::new();
1072    range_set.insert_range(3..=3);
1073    range_set.insert_range(5..=5);
1074    range_set.insert_range(7..=7);
1075    assert_eq!(
1076      range_set.insert_range(1..=9),
1077      {
1078        let mut r = RangeSet::from(3..=3);
1079        r.insert_range(5..=5);
1080        r.insert_range(7..=7);
1081        Some(r)
1082      }
1083    );
1084
1085    assert_eq!(range_set.ranges.into_vec(), vec![1..=9]);
1086  }
1087
1088  #[test]
1089  fn merge_multiple_then_gap() {
1090    let mut range_set: RangeSet<[RangeInclusive<u32>; 2]> = RangeSet::new();
1091    range_set.insert_range(3..=3);
1092    range_set.insert_range(5..=5);
1093    range_set.insert_range(9..=9);
1094    assert_eq!(
1095      range_set.insert_range(1..=7),
1096      {
1097        let mut r = RangeSet::from(3..=3);
1098        r.insert_range(5..=5);
1099        Some(r)
1100      }
1101    );
1102
1103    assert_eq!(range_set.ranges.into_vec(), vec![1..=7, 9..=9]);
1104  }
1105
1106  #[test]
1107  fn gap_then_merge_multiple() {
1108    let mut range_set: RangeSet<[RangeInclusive<u32>; 2]> = RangeSet::new();
1109    range_set.insert_range(1..=1);
1110    range_set.insert_range(5..=5);
1111    range_set.insert_range(7..=7);
1112    assert_eq!(
1113      range_set.insert_range(3..=9),
1114      {
1115        let mut r = RangeSet::from(5..=5);
1116        r.insert_range(7..=7);
1117        Some(r)
1118      }
1119    );
1120
1121    assert_eq!(range_set.ranges.into_vec(), vec![1..=1, 3..=9]);
1122  }
1123
1124  #[test]
1125  fn gap_then_merge_multiple_then_gap() {
1126    let mut range_set: RangeSet<[RangeInclusive<u32>; 2]> = RangeSet::new();
1127    range_set.insert_range(1..=1);
1128    range_set.insert_range(3..=3);
1129    range_set.insert_range(5..=5);
1130    range_set.insert_range(7..=7);
1131    range_set.insert_range(9..=9);
1132    assert_eq!(
1133      range_set.insert_range(3..=7),
1134      {
1135        let mut r = RangeSet::from(3..=3);
1136        r.insert_range(5..=5);
1137        r.insert_range(7..=7);
1138        Some(r)
1139      }
1140    );
1141
1142    assert_eq!(range_set.ranges.into_vec(), vec![1..=1, 3..=7, 9..=9]);
1143  }
1144
1145  #[test]
1146  fn range_set_macro_empty() {
1147    assert_eq!(range_set![; 3], RangeSet::<[RangeInclusive<u8>; 3]>::new());
1148    assert_eq!(range_set![], RangeSet::<[RangeInclusive<u8>; 4]>::new());
1149  }
1150
1151  #[test]
1152  fn range_set_macro_nums() {
1153    let case1 = RangeSet::<[RangeInclusive<u8>; 3]>::from_valid_ranges (
1154      [0..=0, 2..=5]
1155    ).unwrap();
1156    let case2 = RangeSet::<[RangeInclusive<u8>; 4]>::from_valid_ranges (
1157      [1..=3, 6..=6, 8..=10]
1158    ).unwrap();
1159    const SOME_CONST: u8 = 5;
1160    let not_token_tree = |x: u8| x;
1161
1162    // All values
1163    assert_eq!(range_set![0, 2, 3, 4, 5; 3], case1);
1164    assert_eq!(range_set![0, 2, (1 + 2), 4, SOME_CONST; 3], case1);
1165    assert_eq!(range_set![0, 2, (not_token_tree(3)), 4, 5; 3], case1);
1166
1167    assert_eq!(range_set![1, 2, 3, 6, 8, 9, 10; 4], case2);
1168    assert_eq!(range_set![1, 2, 3, (3 * 2), 8, 9, 10], case2);
1169
1170    let mut counter = 0;
1171    let mut call_only_once = |x: u8| { counter += 1; x };
1172    assert_eq!(range_set![0, 2, (call_only_once(3)), 4, 5; 3], case1);
1173    assert_eq!(counter, 1);
1174  }
1175
1176  // This expect is needed due to a rust linting bug:
1177  // https://github.com/rust-lang/rust/issues/113563
1178  #[expect(unused_parens)]
1179  #[test]
1180  fn range_set_macro_mixed() {
1181    let case1 = RangeSet::<[RangeInclusive<u8>; 3]>::from_valid_ranges ([0..=0, 2..=5])
1182      .unwrap();
1183    let case2 = RangeSet::<[RangeInclusive<u8>; 4]>::from_valid_ranges (
1184      [1..=3, 6..=15, 40..=40, 42..=50]
1185    ).unwrap();
1186    const SOME_CONST: u8 = 40;
1187    let not_token_tree = |x: u8| x;
1188
1189    assert_eq!(range_set![0, 2..=5; 3], case1);
1190    assert_eq!(range_set![0, (not_token_tree(2))..=5; 3], case1);
1191
1192    assert_eq!(range_set![1..=3, 6..=15, 40, 42..=50; 4], case2);
1193    assert_eq!(range_set![1, 2, 3, 6..=15, 40, 42..=50], case2);
1194    assert_eq!(range_set![1..=3, (3+3)..=15, SOME_CONST, 42..=50; 4], case2);
1195    assert_eq!(range_set![1..=3, 6..=15, 40..=40, (not_token_tree(42))..=50; 4], case2);
1196
1197    let mut counter = 0;
1198    let mut call_only_once = |x: u8| { counter += 1; x };
1199    assert_eq!(range_set![1..=3, 6..=15, (call_only_once(40)), 42..=50; 4], case2);
1200    assert_eq!(counter, 1);
1201
1202    assert_eq!(range_set![0, 2, 3, 5; 8],
1203      RangeSet::<[RangeInclusive<u8>; 8]>::from_valid_ranges ([0..=0, 2..=3, 5..=5])
1204        .unwrap());
1205    assert_eq!(range_set![0..=0, 2..=2, (not_token_tree(4) + 1)..=5],
1206      RangeSet::<[RangeInclusive<u8>; 4]>::from_valid_ranges ([0..=0, 2..=2, 5..=5])
1207        .unwrap());
1208  }
1209
1210  #[test]
1211  fn max() {
1212    let mut set = RangeSet::<[RangeInclusive <u32>; 2]>::new();
1213    assert_eq!(set.max(), None);
1214
1215    set.insert_range(4..=5);
1216    assert_eq!(set.max(), Some(5));
1217
1218    set.insert(21);
1219    assert_eq!(set.max(), Some(21));
1220
1221    set.insert_range(6..=13);
1222    assert_eq!(set.max(), Some(21));
1223
1224    set.remove(21);
1225    assert_eq!(set.max(), Some(13));
1226  }
1227
1228  #[test]
1229  fn min() {
1230    let mut set = RangeSet::<[RangeInclusive <u32>; 2]>::new();
1231    assert_eq!(set.min(), None);
1232
1233    set.insert_range(4..=5);
1234    assert_eq!(set.min(), Some(4));
1235
1236    set.insert(2);
1237    assert_eq!(set.min(), Some(2));
1238
1239    set.insert_range(6..=13);
1240    assert_eq!(set.min(), Some(2));
1241
1242    set.remove_range(2..=4);
1243    assert_eq!(set.min(), Some(5));
1244  }
1245
1246  #[test]
1247  fn random() {
1248    use rand::{RngExt, SeedableRng};
1249    let mut rng = rand_xorshift::XorShiftRng::seed_from_u64 (0);
1250    let mut s = RangeSet::<[RangeInclusive <u8>; 4]>::new();
1251    for _ in 0..10000 {
1252      s.insert_range (rng.random()..=rng.random());
1253      s.insert (rng.random());
1254      s.remove_range (rng.random()..=rng.random());
1255      s.remove (rng.random());
1256    }
1257    println!("s: {s:?}");
1258  }
1259}
range_set/lib.rs

range_set/
lib.rs
