1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

use num::Integer;

use crate::interval::traits::{Coalesce, CoalesceIntervals, Interval};

impl<I: Coalesce<I> + Interval<E> + Clone, E: Integer + Copy>
    CoalesceIntervals<I, E> for Vec<I>
{
    fn to_coalesced_intervals(&self) -> Vec<I> {
        let mut intervals: Vec<I> = self.to_vec();
        intervals.coalesce_intervals_inplace();
        intervals
    }

    fn coalesce_intervals_inplace(&mut self) {
        self.sort_by_key(|i| i.get_start());
        let mut coalesced_intervals = Vec::new();
        for interval in self.drain(..) {
            match coalesced_intervals.last_mut() {
                None => coalesced_intervals.push(interval),
                Some(last_interval) => {
                    match last_interval.coalesce_with(&interval) {
                        None => coalesced_intervals.push(interval),
                        Some(new_interval) => *last_interval = new_interval,
                    }
                }
            }
        }
        *self = coalesced_intervals;
    }
}

#[cfg(test)]
mod tests {
    use crate::set::contiguous_integer_set::ContiguousIntegerSet;

    use super::CoalesceIntervals;

    #[test]
    fn test_to_coalesced_intervals() {
        let intervals = vec![
            ContiguousIntegerSet::new(2, 4),
            ContiguousIntegerSet::new(1, 1),
            ContiguousIntegerSet::new(-10, -5),
            ContiguousIntegerSet::new(4, 5),
            ContiguousIntegerSet::new(9, 10),
            ContiguousIntegerSet::new(-1, 3),
        ];
        let sorted_intervals = intervals.to_coalesced_intervals();
        assert_eq!(sorted_intervals, vec![
            ContiguousIntegerSet::new(-10, -5),
            ContiguousIntegerSet::new(-1, 5),
            ContiguousIntegerSet::new(9, 10)
        ])
    }
}