Define a range of numbers   R,   with bounds   b0   and   b1   covering all numbers between and including both bounds.



That range can be shown as:

 [b0, b1]
    or equally as:
 [b1, b0]


Given two ranges, the act of consolidation between them compares the two ranges:

   If one range covers all of the other then the result is that encompassing range.
   If the ranges touch or intersect then the result is   one   new single range covering the overlapping ranges.
   Otherwise the act of consolidation is to return the two non-touching ranges.


Given   N   ranges where   N > 2   then the result is the same as repeatedly replacing all combinations of two ranges by their consolidation until no further consolidation between range pairs is possible.

If   N < 2   then range consolidation has no strict meaning and the input can be returned.



Example 1

   Given the two ranges   [1, 2.5]   and   [3, 4.2]   then 
   there is no common region between the ranges and the result is the same as the input.


Example 2

   Given the two ranges   [1, 2.5]   and   [1.8, 4.7]   then 
   there is :   an overlap   [2.5, 1.8]   between the ranges and 
   the result is the single range   [1, 4.7]. 
   Note that order of bounds in a range is not (yet) stated.


Example 3

   Given the two ranges   [6.1, 7.2]   and   [7.2, 8.3]   then 
   they touch at   7.2   and 
   the result is the single range   [6.1, 8.3]. 


Example 4

   Given the three ranges   [1, 2]   and   [4, 8]   and   [2, 5] 
   then there is no intersection of the ranges   [1, 2]   and   [4, 8] 
   but the ranges   [1, 2]   and   [2, 5]   overlap and 
   consolidate to produce the range   [1, 5]. 
   This range, in turn, overlaps the other range   [4, 8],   and 
   so consolidates to the final output of the single range   [1, 8].


Task

Let a normalized range display show the smaller bound to the left;   and show the
range with the smaller lower bound to the left of other ranges when showing multiple ranges.

Output the normalized result of applying consolidation to these five sets of ranges: 

           [1.1, 2.2]
           [6.1, 7.2], [7.2, 8.3]
           [4, 3], [2, 1]
           [4, 3], [2, 1], [-1, -2], [3.9, 10]
           [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]  

Show all output here.



See also

 Set consolidation
 Set of real numbers


use std::fmt::{Display, Formatter};
 
// We could use std::ops::RangeInclusive, but we would have to extend it to
// normalize self (not much trouble) and it would not have to handle pretty
// printing for it explicitly. So, let's make rather an own type.
 
#[derive(Clone, Debug, PartialEq, PartialOrd)]
pub struct ClosedRange<Idx> {
    start: Idx,
    end: Idx,
}
 
impl<Idx> ClosedRange<Idx> {
    pub fn start(&self) -> &Idx {
        &self.start
    }
 
    pub fn end(&self) -> &Idx {
        &self.end
    }
}
 
impl<Idx: PartialOrd> ClosedRange<Idx> {
    pub fn new(start: Idx, end: Idx) -> Self {
        if start <= end {
            Self { start, end }
        } else {
            Self {
                end: start,
                start: end,
            }
        }
    }
}
 
// To make test input more compact
impl<Idx: PartialOrd> From<(Idx, Idx)> for ClosedRange<Idx> {
    fn from((start, end): (Idx, Idx)) -> Self {
        Self::new(start, end)
    }
}
 
// For the required print format
impl<Idx: Display> Display for ClosedRange<Idx> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "[{}, {}]", self.start, self.end)
    }
}
 
fn consolidate<Idx>(a: &ClosedRange<Idx>, b: &ClosedRange<Idx>) -> Option<ClosedRange<Idx>>
where
    Idx: PartialOrd + Clone,
{
    if a.start() <= b.start() {
        if b.end() <= a.end() {
            Some(a.clone())
        } else if a.end() < b.start() {
            None
        } else {
            Some(ClosedRange::new(a.start().clone(), b.end().clone()))
        }
    } else {
        consolidate(b, a)
    }
}
 
fn consolidate_all<Idx>(mut ranges: Vec<ClosedRange<Idx>>) -> Vec<ClosedRange<Idx>>
where
    Idx: PartialOrd + Clone,
{
    // Panics for incomparable elements! So no NaN for floats, for instance.
    ranges.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let mut ranges = ranges.into_iter();
    let mut result = Vec::new();
 
    if let Some(current) = ranges.next() {
        let leftover = ranges.fold(current, |mut acc, next| {
            match consolidate(&acc, &next) {
                Some(merger) => {
                    acc = merger;
                }
 
                None => {
                    result.push(acc);
                    acc = next;
                }
            }
 
            acc
        });
 
        result.push(leftover);
    }
 
    result
}
 
#[cfg(test)]
mod tests {
    use super::{consolidate_all, ClosedRange};
    use std::fmt::{Display, Formatter};
 
    struct IteratorToDisplay<F>(F);
 
    impl<F, I> Display for IteratorToDisplay<F>
    where
        F: Fn() -> I,
        I: Iterator,
        I::Item: Display,
    {
        fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
            let mut items = self.0();
 
            if let Some(item) = items.next() {
                write!(f, "{}", item)?;
                for item in items {
                    write!(f, ", {}", item)?;
                }
            }
 
            Ok(())
        }
    }
 
    macro_rules! parameterized {
        ($($name:ident: $value:expr,)*) => {
            $(
                #[test]
                fn $name() {
                    let (input, expected) = $value;
                    let expected: Vec<_> = expected.into_iter().map(ClosedRange::from).collect();
                    let output = consolidate_all(input.into_iter().map(ClosedRange::from).collect());
                    println!("{}: {}", stringify!($name), IteratorToDisplay(|| output.iter()));
                    assert_eq!(expected, output);
                }
            )*
        }
    }
 
    parameterized! {
        single: (vec![(1.1, 2.2)], vec![(1.1, 2.2)]),
        touching: (vec![(6.1, 7.2), (7.2, 8.3)], vec![(6.1, 8.3)]),
        disjoint: (vec![(4, 3), (2, 1)], vec![(1, 2), (3, 4)]),
        overlap: (vec![(4.0, 3.0), (2.0, 1.0), (-1.0, -2.0), (3.9, 10.0)], vec![(-2.0, -1.0), (1.0, 2.0), (3.0, 10.0)]),
        integer: (vec![(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)], vec![(-6, -1), (1, 8)]),
    }
}
 
fn main() {
    // To prevent dead code and to check empty input
    consolidate_all(Vec::<ClosedRange<usize>>::new());
 
    println!("Run: cargo test -- --nocapture");
}