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

range_set/
lib.rs
