interval_set/
interval_set.rs

1use std::fmt;
2use std::cmp;
3
4use std::str::FromStr;
5
6/// Struct `Interval` containing two values representing the limit of the interval.
7///
8/// The `Interval` is incluse which means that `Interval(0, 10)` is [0, 10].
9/// The value 0 is supposed to be equals or greater than the second value.
10#[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord)]
11pub struct Interval(u32, u32);
12
13/// Struct `IntervalSet` representing a set of sorted not overllaping intervals.
14/// Be aware that the validity of the interval set is not checked.
15#[derive(Clone, Debug, Eq, PartialEq)]
16pub struct IntervalSet {
17    intervals: Vec<Interval>,
18}
19
20/// Struct to iterate through an `IntervalSet`
21pub struct IntervalSetIterator<'a> {
22    pos: usize,
23    inner: &'a IntervalSet,
24}
25
26impl<'a> Iterator for IntervalSetIterator<'a> {
27    type Item = &'a Interval;
28
29    fn next(&mut self) -> Option<Self::Item> {
30        if self.pos >= self.inner.intervals.len() {
31            None
32        } else {
33            self.pos += 1;
34            self.inner.intervals.get(self.pos - 1)
35        }
36    }
37}
38
39impl Interval {
40    pub fn new(begin: u32, end: u32) -> Interval {
41        let res = Interval(begin, end);
42        if !res.is_valid() {
43            panic!("Call constructor of Interval with invalid endpoints: Interval({}, {})",
44                   begin,
45                   end);
46        }
47        res
48    }
49
50    /// Return the maximum interval possible (with u32 var)
51    pub fn whole() -> Interval {
52        Interval(u32::min_value(), u32::max_value())
53    }
54
55    /// Because the trait Order is needed to sort the IntervalSet I dont what to change the
56    /// native order. This function coud be considered as the `len` of the interval.
57    pub fn range_size(&self) -> u32 {
58        self.1 - self.0 + 1
59    }
60
61    /// Simply return an equivalent interval as tuple.
62    pub fn as_tuple(&self) -> (u32, u32) {
63        (self.0, self.1)
64    }
65
66    /// I am not sure about those two function, maybe set the field as public could be a better
67    /// idea...
68    pub fn get_inf(&self) -> u32 {
69        self.0
70    }
71
72    pub fn get_sup(&self) -> u32 {
73        self.1
74    }
75
76    /// Utility function check if the interval is valid.
77    ///
78    /// # Examples
79    /// The following intervals are valids:
80    ///
81    /// ```
82    /// use interval_set::Interval;
83    /// Interval::new(0, 0);
84    /// Interval::new(10, 100);
85    /// ```
86    ///
87    /// The following intervals ae not valid:
88    ///
89    /// ```rust,should_panic
90    /// use interval_set::Interval;
91    /// Interval::new(10, 0);
92    /// ```
93    pub fn is_valid(&self) -> bool {
94        self.0 <= self.1
95    }
96}
97
98/// Trait `ToIntervalSet` allows to write a function to convert type into an IntervalSet.
99pub trait ToIntervalSet {
100    /// Consume `self` to create an IntervalSet
101    fn to_interval_set(self) -> IntervalSet;
102}
103
104impl ToIntervalSet for Interval {
105    /// Convert a simple interval into an intervalset.
106    /// Note that the validity of the interval is checked.
107    fn to_interval_set(self) -> IntervalSet {
108        if self.is_valid() {
109            IntervalSet { intervals: vec![self] }
110        } else {
111            panic!("CReate interval set from an unvalid interval");
112        }
113    }
114}
115
116impl ToIntervalSet for Vec<Interval> {
117    /// Convert an array of interval into an intervalset.
118    /// Note that the validity of the intervals are checked.
119    ///
120    /// # Example
121    ///
122    /// ```
123    /// use interval_set::interval_set::ToIntervalSet;
124    /// use interval_set::Interval;
125    /// vec![Interval::new(5, 10), Interval::new(15, 20)].to_interval_set();
126    /// ```
127    fn to_interval_set(self) -> IntervalSet {
128        let mut res: IntervalSet = IntervalSet::empty();
129        for intv in self {
130            if !intv.is_valid() {
131                panic!("Invalid interval: {}-{}", intv.0, intv.1)
132            }
133            res.insert(intv);
134        }
135        res
136    }
137}
138
139impl ToIntervalSet for Vec<(u32, u32)> {
140    /// Convert an array of tuples into an intervalset.
141    /// Note that the validity of the intervals are checked.
142    ///
143    /// # Example
144    ///
145    /// ```
146    /// use interval_set::interval_set::ToIntervalSet;
147    /// vec![(5, 10), (15, 20)].to_interval_set();
148    /// ```
149    fn to_interval_set(self) -> IntervalSet {
150        let mut res: IntervalSet = IntervalSet::empty();
151        for (begin, end) in self {
152            if begin > end {
153                panic!("Invalid interval: {}-{}", begin, end)
154            }
155            res.insert(Interval(begin, end));
156        }
157        res
158    }
159}
160
161impl ToIntervalSet for String {
162    /// Convert a string formatted into an
163    /// interval set.
164    /// The rules are simple for the string to be
165    /// valid.
166    /// - Each intervals are separated by a space.
167    /// - Each bounds of the interval are separated by
168    ///   a dash(-).
169    /// - If an interval is of size 1, it is sufficient to
170    ///   write only one integer.
171    /// # Example
172    /// ```
173    /// use interval_set::interval_set::ToIntervalSet;
174    /// use interval_set::Interval;
175    /// let interval = String::from("3-4 7-19").to_interval_set();
176    /// assert_eq!(interval, vec![(3, 4), (7, 19)].to_interval_set());
177    ///
178    /// let interval = String::from("3-4 6 7-19").to_interval_set();
179    /// assert_eq!(interval, vec![(3, 4), (6, 6) ,(7, 19)].to_interval_set());
180    ///
181    ///
182    /// let interval = String::from("3-4 7-19 6").to_interval_set();
183    /// assert_eq!(interval, vec![(3, 4), (6, 6), (7, 19)].to_interval_set());
184    ///
185    ///
186    /// let interval = String::from("3-4 7-19 6").to_interval_set();
187    /// let interval_bis = String::from("3-3 4 7-7 8 9-19 6").to_interval_set();
188    /// assert_eq!(interval, interval_bis);
189    ///
190    /// ```
191    fn to_interval_set(self) -> IntervalSet {
192        let mut iter = self.split_whitespace();
193        let mut result = IntervalSet::empty();
194        for interval in iter {
195            // Handles the case where we have two specified bounds.
196            if interval.contains("-") {
197                // split by - and use map to transform the string into u32
198                let bounds: Vec<u32> =
199                    interval.split('-').map(|b| u32::from_str(b).unwrap()
200                                            ).collect();
201
202                let interval = Interval::new(bounds[0], bounds[1]);
203                result = result.union(interval.to_interval_set());
204            } else {
205                let bound = u32::from_str(interval).unwrap();
206                result = result.union(Interval::new(bound, bound).to_interval_set());
207            }
208        }
209        result
210    }
211}
212
213impl IntervalSet {
214    /// Function to create an empty interval set.
215    pub fn empty() -> IntervalSet {
216        IntervalSet { intervals: vec![] }
217    }
218
219    /// Return `true` if the interval is empty.
220    pub fn is_empty(&self) -> bool {
221        self.intervals.len() == 0
222    }
223
224    /// Return the union of two intervals.
225    ///
226    /// # Example
227    ///
228    /// ```
229    /// use interval_set::interval_set::ToIntervalSet;
230    ///
231    /// let a = vec![(5, 10)].to_interval_set();
232    /// let b = vec![(15, 20)].to_interval_set();
233    /// a.union(b); // [5-10, 15-20]
234    /// ```
235    pub fn union(self, rhs: IntervalSet) -> IntervalSet {
236        self.merge(rhs, &|a, b| -> bool { a | b })
237    }
238
239    /// Return the intersection of two intervals.
240    ///
241    /// # Example
242    ///
243    /// ```
244    /// use interval_set::interval_set::ToIntervalSet;
245    ///
246    /// let a = vec![(5, 10)].to_interval_set();
247    /// let b = vec![(5, 10), (15, 20)].to_interval_set();
248    /// a.intersection(b); //[5-10]
249    /// ```
250    pub fn intersection(self, rhs: IntervalSet) -> IntervalSet {
251        self.merge(rhs, &|a, b| -> bool { a & b })
252    }
253
254    /// Return the difference between two intervals.
255    ///
256    /// # Example
257    ///
258    /// ```
259    /// use interval_set::interval_set::ToIntervalSet;
260    ///
261    /// let a = vec![(5, 10), (15, 20)].to_interval_set();
262    /// let b = vec![(5, 10)].to_interval_set();
263    /// a.difference(b); //[15-20]
264    /// ```
265    pub fn difference(self, rhs: IntervalSet) -> IntervalSet {
266        self.merge(rhs, &|a, b| -> bool { a & !b })
267    }
268
269    /// Return the symetric difference of two intervals.
270    ///
271    /// # Example
272    ///
273    /// ```
274    /// use interval_set::interval_set::ToIntervalSet;
275    ///
276    /// let a = vec![(5, 10), (15, 20)].to_interval_set();
277    /// let b = vec![(0, 10)].to_interval_set();
278    /// a.difference(b); //[0-5, 15-20]
279    /// ```
280    pub fn symetric_difference(self, rhs: IntervalSet) -> IntervalSet {
281        self.merge(rhs, &|a, b| -> bool { a ^ b })
282    }
283
284    /// Return the greater interval from the set.
285    /// Note that the function return a cloned interval, so I will be easier to manipulate.
286    /// Moreover, in the case where many intervals have the same size,
287    /// the function will return the first element.
288    /// # Example
289    ///
290    /// ```
291    /// use interval_set::interval_set::ToIntervalSet;
292    /// use interval_set::interval_set::IntervalSet;
293    /// use interval_set::interval_set::Interval;
294    ///
295    /// let a = vec![(5, 10), (15, 25)].to_interval_set();
296    /// let b = vec![(5, 10), (15, 20)].to_interval_set();
297    /// let c = vec![(5, 10), (15, 20), (100, 1000)].to_interval_set();
298    ///
299    /// assert_eq!(a.max().unwrap(), Interval::new(15, 25));
300    /// assert_eq!(b.max().unwrap(), Interval::new(5, 10));
301    /// assert_eq!(c.max().unwrap(), Interval::new(100, 1000));
302    /// assert_eq!(IntervalSet::empty().max(), None);
303    ///
304    /// ```
305    pub fn max(&self) -> Option<Interval> {
306        let mut max = usize::min_value();
307        let mut res = None;
308
309        if self.is_empty() {
310            return None;
311        }
312
313        for intv in self.iter() {
314            let curr_: usize = (intv.1 - intv.0) as usize;
315            if curr_ > max {
316                max = curr_ as usize;
317                res = Some(intv.clone());
318            }
319        }
320        res
321    }
322
323    /// Return the size of the interval set. The sie is defined by the sum of the len of each
324    /// intervals contained into the set.
325    ///
326    /// # Example
327    ///
328    /// ```
329    /// use interval_set::interval_set::ToIntervalSet;
330    ///
331    /// let a = vec![(5, 10), (15, 20)].to_interval_set();
332    /// let b = vec![(0, 10), (15, 20)].to_interval_set();
333    /// assert_eq!(a.size(), 12);
334    /// assert_eq!(b.size(), 17);
335    /// ```
336    pub fn size(&self) -> u32 {
337        if self.is_empty() {
338            return 0;
339        }
340        self.iter().fold(0, |acc, ref x| acc + (x.range_size()))
341    }
342
343    /// Get an iterator over an IntervalSet
344    ///
345    /// # Example
346    ///
347    /// ```
348    /// use interval_set::interval_set::ToIntervalSet;
349    ///
350    /// let a = vec![(5, 10), (15, 20)].to_interval_set();
351    /// for intv in a.iter() {
352    ///     let tuple = intv.as_tuple();
353    ///     println!("{}--{}", tuple.0, tuple.1);
354    /// }
355    ///
356    /// ```
357    pub fn iter<'a>(&'a self) -> IntervalSetIterator<'a> {
358        IntervalSetIterator {
359            inner: self,
360            pos: 0,
361        }
362    }
363
364    /// Generate the (flat) list of interval bounds of the requested merge.
365    /// The implementation is inspired by  http://stackoverflow.com/a/20062829.
366    fn merge(self, rhs: IntervalSet, keep_operator: &Fn(bool, bool) -> bool) -> IntervalSet {
367        if self.is_empty() & rhs.is_empty() {
368            return self;
369        }
370
371        let mut lflat = self.flatten();
372        let mut rflat = rhs.flatten();
373
374        let sentinel: u32 = *cmp::max(lflat.iter().max(), rflat.iter().max()).unwrap() + 1;
375
376        lflat.push(sentinel);
377        rflat.push(sentinel);
378
379        let mut ltail = lflat.iter().enumerate();
380        let mut rtail = rflat.iter().enumerate();
381
382        let mut res = vec![];
383
384        //Because both vec are supposed to be sorted we could only take the min of vec[0].
385        let mut scan: u32 = *cmp::min(lflat.iter().min(), rflat.iter().min()).unwrap();
386
387        let mut lhead = ltail.next().unwrap();
388        let mut rhead = rtail.next().unwrap();
389
390        while scan < sentinel {
391            let lin = !((scan < *lhead.1) ^ (lhead.0 % 2 != 0));
392            let rin = !((scan < *rhead.1) ^ (rhead.0 % 2 != 0));
393
394            let inres = keep_operator(lin, rin);
395
396            if inres ^ (res.len() % 2 != 0) {
397                res.push(scan);
398            }
399
400            if scan == *lhead.1 {
401                lhead = match ltail.next() {
402                    Some((lpos, lval)) => (lpos, lval),
403                    _ => panic!("Deal with it braw"),
404                };
405            }
406            if scan == *rhead.1 {
407                rhead = match rtail.next() {
408                    Some(rval) => rval,
409                    _ => panic!("Deal with it braw"),
410                };
411            }
412            scan = cmp::min(*lhead.1, *rhead.1);
413        }
414        IntervalSet::unflatten(res)
415    }
416
417    /// Generate a vector of endpoints.
418    /// For example with the interval set `[0-5, 9-9,]`
419    /// The resulting array would be: [0, 5, 9]
420    fn flatten(self) -> Vec<u32> {
421        let mut res = vec![];
422        for intv in self.intervals {
423            res.extend(vec![intv.0, intv.1 + 1]);
424        }
425        res
426    }
427
428    /// From an array of endpoints generate an `IntervalSet`.
429    fn unflatten(vec: Vec<u32>) -> IntervalSet {
430        let mut res: Vec<Interval> = Vec::new();
431        let mut i = 0;
432        while i < vec.len() {
433            res.push(Interval(vec[i], vec[i + 1] - 1));
434            i += 2;
435        }
436        res.to_interval_set()
437    }
438
439    pub fn insert(&mut self, element: Interval) {
440        let mut newinf = element.0;
441        let mut newsup = element.1;
442
443        // Because we may remove one interval from self while we loop through its clone, we need to
444        // adjuste the position.
445        let mut idx_shift = 0;
446        for (pos, intv) in self.intervals.clone().iter().enumerate() {
447            if newinf > intv.1 + 1 {
448                continue;
449            }
450            if newsup + 1 < intv.0 {
451                break;
452            }
453
454            self.intervals.remove(pos - idx_shift);
455            idx_shift += 1;
456
457            newinf = cmp::min(newinf, intv.0);
458            newsup = cmp::max(newsup, intv.1);
459        }
460        self.intervals.push(Interval::new(newinf, newsup));
461        self.intervals.sort();
462    }
463}
464
465impl fmt::Display for Interval {
466    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
467        if self.0 == self.1 {
468            write!(f, "{}", self.0)
469        } else {
470            write!(f, "{}-{}", self.0, self.1)
471        }
472    }
473}
474
475impl fmt::Display for IntervalSet {
476    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
477        for (pos, interval) in self.intervals.iter().enumerate() {
478            if pos == self.intervals.len() - 1 {
479                f.write_fmt(format_args!("{}", interval))?;
480            } else {
481                f.write_fmt(format_args!("{} ", interval))?;
482            }
483        }
484        write!(f, "")
485    }
486}
487
488#[cfg(test)]
489mod tests {
490    use super::*;
491
492    #[test]
493    fn test_print() {
494        let empty_set = IntervalSet::empty();
495        assert_eq!(format!("{}", empty_set), "");
496    }
497
498    fn assert_to_interval_set(tes_id: u32, v: Vec<(u32, u32)>, expected: IntervalSet) {
499        assert_eq!(v.to_interval_set(), expected, "Test {} failed", tes_id);
500    }
501
502    #[test]
503    fn test_to_interval_set() {
504        let sym_cases =
505            vec![(1, vec![(5, 10)], IntervalSet { intervals: vec![Interval(5, 10)] }),
506                 (2, vec![(0, 100), (5, 10)], IntervalSet { intervals: vec![Interval(0, 100)] }),
507                 (3,
508                  vec![(1, 1), (2, 2), (3, 3), (4, 10), (10, 20)],
509                  IntervalSet { intervals: vec![Interval(1, 20)] })];
510
511        for (id, v, expected) in sym_cases {
512            //assert_eq!(format!("test #{} of union", id), a, b, |x,y| x.union(y), expected);
513            assert_to_interval_set(id, v, expected);
514        }
515    }
516
517    fn assert_insertion(tes_id: u32, a: IntervalSet, element: Interval, expected: IntervalSet) {
518        let mut a_ = a.clone();
519        a_.insert(element);
520        assert_eq!(a_, expected, "Test {} failed", tes_id);
521    }
522
523    #[test]
524    fn test_insertion() {
525        let sym_cases: Vec<(u32, IntervalSet, Interval, IntervalSet)> =
526            vec![(1,
527                  IntervalSet { intervals: vec![Interval(0, 0)] },
528                  Interval(1, 1),
529                  IntervalSet { intervals: vec![Interval(0, 1)] }),
530                 (2,
531                  IntervalSet { intervals: vec![Interval(0, 0), Interval(2, 2)] },
532                  Interval(1, 1),
533                  IntervalSet { intervals: vec![Interval(0, 2)] }),
534                 (3,
535                  IntervalSet { intervals: vec![Interval(0, 3)] },
536                  Interval(1, 1),
537                  IntervalSet { intervals: vec![Interval(0, 3)] }),
538                 (4,
539                  IntervalSet { intervals: vec![Interval(1, 1)] },
540                  Interval(0, 3),
541                  IntervalSet { intervals: vec![Interval(0, 3)] }),
542                 (5,
543                  IntervalSet { intervals: vec![Interval(0, 100)] },
544                  Interval(1, 3),
545                  IntervalSet { intervals: vec![Interval(0, 100)] }),
546                 (6,
547                  IntervalSet { intervals: vec![Interval(10, 20)] },
548                  Interval(40, 80),
549                  IntervalSet { intervals: vec![Interval(10, 20), Interval::new(40, 80)] })];
550
551        for (id, a, element, expected) in sym_cases {
552            //assert_eq!(format!("test #{} of union", id), a, b, |x,y| x.union(y), expected);
553            assert_insertion(id, a, element, expected);
554        }
555    }
556
557    #[test]
558    fn test_flatten() {
559        let simple_range = vec![Interval(0, 10)].to_interval_set();
560        let disjoint = vec![Interval(0, 10), Interval(15, 20)].to_interval_set();
561        assert_eq!(simple_range.flatten(), vec![0, 11]);
562        assert_eq!(disjoint.flatten(), vec![0, 11, 15, 21]);
563    }
564
565    #[test]
566    fn test_unflatten() {
567        let simple_range = vec![0, 11];
568        let disjoint = vec![0, 11, 15, 21];
569        assert_eq!(IntervalSet::unflatten(disjoint),
570                   vec![Interval(0, 10), Interval(15, 20)].to_interval_set());
571        assert_eq!(IntervalSet::unflatten(simple_range),
572                   vec![Interval(0, 10)].to_interval_set());
573    }
574
575    fn assert_difference(tes_id: u32, a: IntervalSet, b: IntervalSet, expected: IntervalSet) {
576        assert_eq!(a.difference(b), expected, "Test {} failed", tes_id);
577    }
578
579    #[test]
580    fn test_difference() {
581        let sym_cases: Vec<(u32, IntervalSet, IntervalSet, IntervalSet)> =
582            vec![(1,
583                  vec![Interval(5, 10)].to_interval_set(),
584                  vec![Interval(5, 10), Interval(15, 20)].to_interval_set(),
585                  IntervalSet::empty()),
586                 (2,
587                  vec![(5, 10)].to_interval_set(),
588                  vec![(5, 10), (15, 20)].to_interval_set(),
589                  IntervalSet::empty()),
590                 (3,
591                  IntervalSet::empty(),
592                  vec![(5, 10), (15, 20)].to_interval_set(),
593                  IntervalSet::empty()),
594                 (4,
595                  vec![(5, 10), (15, 20)].to_interval_set(),
596                  IntervalSet::empty(),
597                  vec![(5, 10), (15, 20)].to_interval_set()),
598                 (5,
599                  vec![(0, 100)].to_interval_set(),
600                  vec![(5, 10), (15, 20)].to_interval_set(),
601                  vec![(0, 4), (11, 14), (21, 100)].to_interval_set()),
602                 (6,
603                  vec![(5, 10), (15, 20)].to_interval_set(),
604                  vec![(0, 100)].to_interval_set(),
605                  IntervalSet::empty()),
606                 (7, IntervalSet::empty(), IntervalSet::empty(), IntervalSet::empty())];
607
608        for (id, a, b, expected) in sym_cases {
609            //assert_eq!(format!("test #{} of union", id), a, b, |x,y| x.union(y), expected);
610            assert_difference(id, a, b, expected);
611        }
612    }
613
614    fn assert_intersection(tes_id: u32, a: IntervalSet, b: IntervalSet, expected: IntervalSet) {
615        assert_eq!(a.intersection(b), expected, "Test {} failed", tes_id);
616    }
617
618    #[test]
619    fn test_intersection() {
620        let sym_cases: Vec<(u32, IntervalSet, IntervalSet, IntervalSet)> =
621            vec![(1,
622                  vec![Interval(5, 10)].to_interval_set(),
623                  vec![Interval(5, 10), Interval(15, 20)].to_interval_set(),
624                  vec![Interval(5, 10)].to_interval_set()),
625                 (2,
626                  vec![(5, 10)].to_interval_set(),
627                  vec![(5, 10), (15, 20)].to_interval_set(),
628                  vec![(5, 10)].to_interval_set()),
629                 (3,
630                  IntervalSet::empty(),
631                  vec![(5, 10), (15, 20)].to_interval_set(),
632                  IntervalSet::empty()),
633                 (4,
634                  vec![(5, 10), (15, 20)].to_interval_set(),
635                  IntervalSet::empty(),
636                  IntervalSet::empty()),
637                 (5,
638                  vec![(0, 100)].to_interval_set(),
639                  vec![(5, 10), (15, 20)].to_interval_set(),
640                  vec![(5, 10), (15, 20)].to_interval_set()),
641                 (6, IntervalSet::empty(), IntervalSet::empty(), IntervalSet::empty())];
642
643        for (id, a, b, expected) in sym_cases {
644            //assert_eq!(format!("test #{} of union", id), a, b, |x,y| x.union(y), expected);
645            assert_intersection(id, a, b, expected);
646        }
647    }
648
649    fn assert_union(tes_id: u32, a: IntervalSet, b: IntervalSet, expected: IntervalSet) {
650        assert_eq!(a.union(b), expected, "Test {} failed", tes_id);
651    }
652
653    #[test]
654    fn test_union() {
655        // Note: the first number is the test id, so it should be easy
656        // to identify which test has failed.
657        // The two first vectors are the operands and the expected result is last.
658        let sym_cases: Vec<(u32, IntervalSet, IntervalSet, IntervalSet)> =
659            vec![(1,
660                  vec![Interval(5, 10)].to_interval_set(),
661                  vec![Interval(5, 10), Interval(15, 20)].to_interval_set(),
662                  vec![Interval(5, 10), Interval(15, 20)].to_interval_set()),
663                 (2,
664                  vec![(5, 10)].to_interval_set(),
665                  vec![(5, 10), (15, 20)].to_interval_set(),
666                  vec![(5, 10), (15, 20)].to_interval_set()),
667                 (3,
668                  IntervalSet::empty(),
669                  vec![(5, 10), (15, 20)].to_interval_set(),
670                  vec![(5, 10), (15, 20)].to_interval_set()),
671                 (4,
672                  vec![(5, 10), (15, 20)].to_interval_set(),
673                  IntervalSet::empty(),
674                  vec![(5, 10), (15, 20)].to_interval_set()),
675                 (5,
676                  vec![(0, 100)].to_interval_set(),
677                  vec![(5, 10), (15, 20)].to_interval_set(),
678                  vec![(0, 100)].to_interval_set()),
679                 (6, IntervalSet::empty(), IntervalSet::empty(), IntervalSet::empty()),
680                 (7,
681                  vec![(0, 0), (2, 2), (3, 3)].to_interval_set(),
682                  vec![(1, 1)].to_interval_set(),
683                  vec![(0, 3)].to_interval_set())];
684
685        for (id, a, b, expected) in sym_cases {
686            //assert_eq!(format!("test #{} of union", id), a, b, |x,y| x.union(y), expected);
687            assert_union(id, a, b, expected);
688        }
689    }
690
691    fn assert_symetric_difference(tes_id: u32,
692                                  a: IntervalSet,
693                                  b: IntervalSet,
694                                  expected: IntervalSet) {
695        assert_eq!(a.symetric_difference(b), expected, "Test {} failed", tes_id);
696    }
697
698    #[test]
699    fn test_symetric_difference() {
700        let sym_cases: Vec<(u32, IntervalSet, IntervalSet, IntervalSet)> =
701            vec![(1,
702                  vec![Interval(5, 10)].to_interval_set(),
703                  vec![Interval(5, 10), Interval(15, 20)].to_interval_set(),
704                  vec![(15, 20)].to_interval_set()),
705                 (2,
706                  vec![(5, 10)].to_interval_set(),
707                  vec![(5, 10), (15, 20)].to_interval_set(),
708                  vec![(15, 20)].to_interval_set()),
709                 (3,
710                  IntervalSet::empty(),
711                  vec![(5, 10), (15, 20)].to_interval_set(),
712                  vec![(5, 10), (15, 20)].to_interval_set()),
713                 (4,
714                  vec![(5, 10), (15, 20)].to_interval_set(),
715                  IntervalSet::empty(),
716                  vec![(5, 10), (15, 20)].to_interval_set()),
717                 (5,
718                  vec![(0, 100)].to_interval_set(),
719                  vec![(5, 10), (15, 20)].to_interval_set(),
720                  vec![(0, 4), (11, 14), (21, 100)].to_interval_set()),
721                 (6,
722                  vec![(5, 10), (15, 20)].to_interval_set(),
723                  vec![(0, 100)].to_interval_set(),
724                  vec![(0, 4), (11, 14), (21, 100)].to_interval_set()),
725                 (7, IntervalSet::empty(), IntervalSet::empty(), IntervalSet::empty())];
726
727        for (id, a, b, expected) in sym_cases {
728            //assert_eq!(format!("test #{} of union", id), a, b, |x,y| x.union(y), expected);
729            assert_symetric_difference(id, a, b, expected);
730        }
731    }
732}
interval_set/interval_set.rs

interval_set/
interval_set.rs
