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

range_set/
lib.rs
