ranges 0.3.3

use core::convert::Into;
use core::ops::{Sub, SubAssign};

use crate::{Arrangement, Domain, GenericRange, Ranges};

impl<T: Domain> Ranges<T> {
    /// Calculates the relative complement (difference) of two ranges.
    ///
    /// # Examples
    /// Overlapping ranges:
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges1 = Ranges::from(0..5);
    /// let ranges2 = 3..8;
    ///
    ///  assert_eq!(ranges1 - ranges2, (0..3).into());
    /// ```
    /// Equal ranges:
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges1 = Ranges::from(0..10);
    /// let ranges2 = 0..10;
    ///
    /// assert!((ranges1 - ranges2).is_empty());
    /// ```
    #[allow(clippy::too_many_lines, clippy::expect_used)]
    #[must_use]
    pub fn difference<R>(self, other: R) -> Self
    where
        R: Into<Self>,
    {
        if self.is_empty() {
            return self;
        }

        let other_ranges = other.into();
        if other_ranges.is_empty() {
            return self;
        }

        let mut result = Self::new();

        let mut lhs_iter = self.ranges.into_iter();
        let mut rhs_iter = other_ranges.ranges.into_iter();

        let mut lhs_range = lhs_iter.next();
        let mut rhs_range = rhs_iter.next();

        // we use `while let`, because unlike union or symmetric difference,
        // we don't care if rhs becomes empty
        while let Some(ref inc) = lhs_range {
            let arrangement = if let Some(ref exc) = rhs_range {
                inc.arrangement(exc)
            } else {
                // as soon as rhs is empty, we know the rest of lhs is not modified
                // so we can instantly save it and return the result
                #[allow(clippy::integer_arithmetic)]
                result.ranges.reserve(lhs_iter.len() + 1);

                result
                    .ranges
                    .push(lhs_range.expect("lhs_range can't be None, as we're in a 'let Some' using it"));
                for lhs_range in lhs_iter {
                    result.ranges.push(lhs_range);
                }

                return result;
            };

            match arrangement {
                // no overlap at all and lhs is less than rhs, so it belongs in the result
                Arrangement::Disjoint { self_less: true } | Arrangement::Touching { self_less: true } => {
                    result.ranges.push(
                        lhs_range
                            .expect("the arrangement has been calculated and we didn't end up in Arrangement::Empty"),
                    );
                    // lhs is done, use next lhs subrange
                    lhs_range = lhs_iter.next();
                }
                // no overlap at all, but rhs is less, so use next rhs subrange
                Arrangement::Disjoint { self_less: false } | Arrangement::Touching { self_less: false } => {
                    rhs_range = rhs_iter.next();
                }
                // lhs is completely contained in rhs, so use next lhs subrange
                Arrangement::Starting { self_shorter: true, .. }
                | Arrangement::Ending { self_shorter: true, .. }
                | Arrangement::Containing { self_shorter: true } => {
                    lhs_range = lhs_iter.next();
                }
                // lhs and rhs are equal, so use next subranges for both
                Arrangement::Equal => {
                    lhs_range = lhs_iter.next();
                    rhs_range = rhs_iter.next();
                }
                // lhs is less than rhs, but has overlapping elements, so lhs until start of rhs
                Arrangement::Overlapping { self_less: true, .. } => {
                    // lhs is definitely done now, so use next lhs subrange
                    let lhs = lhs_range
                        .take()
                        .expect("the arrangement has been calculated and we didn't end up in Arrangement::Empty");
                    let rhs = rhs_range
                        .take()
                        .expect("the arrangement has been calculated and we didn't end up in Arrangement::Empty");
                    lhs_range = lhs_iter.next();
                    result.ranges.push(GenericRange {
                        start: lhs.start,
                        end: GenericRange::invert_border(rhs.start),
                    });
                    // modify rhs range to contain only elements after current lhs
                    rhs_range = Some(GenericRange {
                        start: GenericRange::invert_border(lhs.end),
                        end: rhs.end,
                    });
                }
                // lhs is less than rhs, but has overlapping elements, so lhs until start of rhs
                Arrangement::Ending {
                    self_shorter: false, ..
                } => {
                    // both rhs and lhs are done now, so use next subranges
                    let lhs = lhs_range
                        .take()
                        .expect("the arrangement has been calculated and we didn't end up in Arrangement::Empty");
                    let rhs = rhs_range
                        .take()
                        .expect("the arrangement has been calculated and we didn't end up in Arrangement::Empty");
                    lhs_range = lhs_iter.next();
                    rhs_range = rhs_iter.next();
                    result.ranges.push(GenericRange {
                        start: lhs.start,
                        end: GenericRange::invert_border(rhs.start),
                    });
                }
                // rhs is less than lhs, so modify lhs to contain only non-rhsd elements
                Arrangement::Overlapping { self_less: false, .. }
                | Arrangement::Starting {
                    self_shorter: false, ..
                } => {
                    // rhs is definitely done now, so use next rhs subrange
                    let rhs = rhs_range
                        .take()
                        .expect("the arrangement has been calculated and we didn't end up in Arrangement::Empty");
                    rhs_range = rhs_iter.next();
                    // remove elements from lhs range
                    if let Some(ref mut lhs) = lhs_range {
                        lhs.start = GenericRange::invert_border(rhs.end);
                    }
                }
                // rhs is entirely contained within lhs, so use first part and modify
                // lhs to contain only non-rhs elements
                Arrangement::Containing {
                    self_shorter: false, ..
                } => {
                    // rhs is definitely done now, so use next rhs subrange
                    let lhs = lhs_range
                        .take()
                        .expect("the arrangement has been calculated and we didn't end up in Arrangement::Empty");
                    let rhs = rhs_range
                        .take()
                        .expect("the arrangement has been calculated and we didn't end up in Arrangement::Empty");
                    rhs_range = rhs_iter.next();
                    // insert correct subrange into result
                    result.ranges.push(GenericRange {
                        start: lhs.start,
                        end: GenericRange::invert_border(rhs.start),
                    });
                    // modify lhs
                    lhs_range = Some(GenericRange {
                        start: GenericRange::invert_border(rhs.end),
                        end: lhs.end,
                    });
                }
                Arrangement::Empty { .. } => unreachable!("internal guarantee broken: empty range in set"),
            }
        }

        result
    }
}

/// This calls [`self.difference(other)`](#method.difference).
// note: can not rewrite this to use `Into<Ranges<T>>` as that would conflict with `Self::remove()`
impl<T: Domain> Sub<Ranges<T>> for Ranges<T> {
    type Output = Self;

    #[must_use]
    fn sub(self, rhs: Self) -> Self::Output {
        self.difference(rhs)
    }
}

/// This calls [`self.difference(other)`](#method.difference) and replaces `self` with the result.
impl<T: Domain> SubAssign<Ranges<T>> for Ranges<T> {
    fn sub_assign(&mut self, rhs: Self) {
        let lhs = core::mem::replace(self, Self::new());
        let result = lhs.difference(rhs);
        *self = result;
    }
}

#[cfg(test)]
mod tests {
    use alloc::vec;
    use core::cmp::Ordering;
    use core::convert::From;
    use core::ops::RangeBounds;

    use proptest::prelude::*;

    use crate::{GenericRange, Ranges};

    #[test]
    fn empty() {
        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::new();

        assert_eq!(ranges1.difference(ranges2), Ranges::from(0..10));

        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::new();

        assert_eq!(ranges2.difference(ranges1), Ranges::new())
    }

    #[test]
    fn equal() {
        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::from(0..10);

        assert_eq!(ranges1.difference(ranges2), Ranges::new());
    }

    #[test]
    fn disjoint() {
        let ranges1 = Ranges::from(0..3);
        let ranges2 = Ranges::from(5..8);

        assert_eq!(ranges1.difference(ranges2), Ranges::from(0..3));

        let ranges1 = Ranges::from(0..3);
        let ranges2 = Ranges::from(5..8);

        assert_eq!(ranges2.difference(ranges1), Ranges::from(5..8));
    }

    #[test]
    fn touching() {
        let ranges1 = Ranges::from(0..3);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges1.difference(ranges2), Ranges::from(0..3));

        let ranges1 = Ranges::from(0..3);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges2.difference(ranges1), Ranges::from(3..8));
    }

    #[test]
    fn overlapping() {
        let ranges1 = Ranges::from(0..5);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges1.difference(ranges2), Ranges::from(0..3));

        let ranges1 = Ranges::from(0..5);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges2.difference(ranges1), Ranges::from(5..8));
    }

    #[test]
    fn containing() {
        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges1.difference(ranges2).ranges, vec![(0..3).into(), (8..10).into()]);

        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges2.difference(ranges1), Ranges::new());
    }

    #[test]
    fn starting() {
        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::from(0..8);

        assert_eq!(ranges1.difference(ranges2), Ranges::from(8..10));

        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::from(0..8);

        assert_eq!(ranges2.difference(ranges1), Ranges::new());
    }

    #[test]
    fn ending() {
        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::from(3..10);

        assert_eq!(ranges1.difference(ranges2), Ranges::from(0..3));

        let ranges1 = Ranges::from(0..10);
        let ranges2 = Ranges::from(3..10);

        assert_eq!(ranges2.difference(ranges1), Ranges::new());
    }

    #[test]
    fn multiple_lhs() {
        let ranges1 = Ranges::from(vec![GenericRange::from(0..5), (6..9).into()]);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges1.difference(ranges2).ranges, vec![(0..3).into(), (8..9).into()]);
    }

    #[test]
    fn multiple_rhs() {
        let ranges1 = Ranges::from(vec![GenericRange::from(0..5), (6..9).into()]);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges2.difference(ranges1).ranges, vec![(5..6).into()]);
    }

    #[test]
    fn leftover_lhs() {
        let ranges1 = Ranges::from(vec![GenericRange::from(0..5), (6..9).into(), (15..20).into()]);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(
            ranges1.difference(ranges2).ranges,
            vec![(0..3).into(), (8..9).into(), (15..20).into()]
        );
    }

    #[test]
    fn leftover_rhs() {
        let ranges1 = Ranges::from(vec![GenericRange::from(0..5), (6..9).into(), (15..20).into()]);
        let ranges2 = Ranges::from(3..8);

        assert_eq!(ranges2.difference(ranges1).ranges, vec![(5..6).into()]);
    }

    proptest! {
        #[ignore]
        #[test]
        fn sorted_and_disjoint(ranges1 in any::<Ranges<u8>>(), ranges2 in any::<Ranges<u8>>()) {
            let result = ranges1.difference(ranges2);
            let sorted_and_disjoint = result.as_slice().windows(2).all(|slice| match slice {
                [left, right] => {
                    GenericRange::cmp_start_start(left.start_bound(), right.start_bound()) == Ordering::Less
                        && GenericRange::cmp_end_start(left.end_bound(), right.start_bound()) == Ordering::Less
                },
                _ => false,
            });

            prop_assert!(sorted_and_disjoint);
        }
    }
}