range_set/
lib.rs

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

range_set/
lib.rs
