ranges 0.3.3

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

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

impl<T: Domain> Ranges<T> {
    /// Returns `true` if any element or the internal vector was modified to remove `range`.
    /// This means `false` is returned if and only if nothing has changed.
    ///
    /// # Examples
    /// Empty set.
    /// ```
    /// use ranges::Ranges;
    ///
    /// let mut ranges = Ranges::new();
    /// assert!(!ranges.remove(0..3));
    /// ```
    /// Single entry but no collision.
    /// ```
    /// use ranges::Ranges;
    ///
    /// let mut ranges = Ranges::from(0..3);
    /// assert!(!ranges.remove(5..10));
    /// assert_eq!(ranges, (0..3).into())
    /// ```
    /// Single entry with collision in the middle.
    /// ```
    /// use ranges::{GenericRange, Ranges};
    ///
    /// let mut ranges = Ranges::from(0..10);
    /// assert!(ranges.remove(2..5));
    /// assert_eq!(ranges, vec![0..2, 5..10].into())
    /// ```
    #[allow(clippy::expect_used)]
    pub fn remove<R>(&mut self, range: R) -> bool
    where
        R: Into<GenericRange<T>>,
    {
        let new_range = range.into();

        if new_range.is_empty() || self.ranges.is_empty() {
            return false;
        }

        if new_range.is_full() {
            // whatever is in `self.ranges` does not matter...
            self.ranges.clear();
            return true;
        }

        let indices = self.find_intersecting_ranges(&new_range);

        match indices {
            // we only encountered disjoint ranges
            None => {
                // if all entries are disjoint, we can instantly return as no modification is necessary
                false
            }
            // a single range intersected
            Some((s, e)) if s == e => {
                let removed = self.ranges.remove(s);

                match removed.difference(new_range) {
                    OperationResult::Empty => (),
                    OperationResult::Double(r1, r2) => {
                        self.ranges.insert(s, r1);
                        #[allow(clippy::integer_arithmetic)]
                        self.ranges.insert(s + 1, r2);
                    }
                    OperationResult::Single(r) => self.ranges.insert(s, r),
                }

                true
            }
            Some((s, e)) => {
                // drain the entries that are not disjoint
                // we can drain from `min` to `max` because of the prime guarantee of `Ranges`:
                // internal ranges are ordered and disjoint. this means the indices are all contiguous.
                let mut ranges = self.ranges.drain(s..=e);

                // keep only the first and last one (as all others are inside the new range anyway)
                let first = ranges
                    .next()
                    .expect("find_intersecting_ranges() already tells us there has to be a first range");
                // we can safely unwrap here because we know there are at least two ranges
                let last = ranges
                    .last()
                    .expect("find_intersecting_ranges() already tells us there has to be a last range");

                // and because the indices were sorted, we can now construct a new one directly
                let existing_ranges_combined = GenericRange {
                    start: first.start,
                    end: last.end,
                };

                match existing_ranges_combined.difference(new_range) {
                    OperationResult::Empty => (),
                    OperationResult::Double(r1, r2) => {
                        self.ranges.insert(s, r1);
                        #[allow(clippy::integer_arithmetic)]
                        self.ranges.insert(s + 1, r2);
                    }
                    OperationResult::Single(r) => self.ranges.insert(s, r),
                }

                true
            }
        }
    }
}

/// This calls [`self.remove(other)`](#method.remove).
impl<T, I> Sub<I> for Ranges<T>
where
    I: Into<GenericRange<T>>,
    T: Domain,
{
    type Output = Self;

    #[must_use]
    fn sub(mut self, rhs: I) -> Self::Output {
        let _ = self.remove(rhs.into());

        self
    }
}

/// This calls [`self.remove(other)`](#method.remove).
impl<T, I> SubAssign<I> for Ranges<T>
where
    I: Into<GenericRange<T>>,
    T: Domain,
{
    fn sub_assign(&mut self, rhs: I) {
        let _ = self.remove(rhs.into());
    }
}

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

    use proptest::prelude::*;

    use crate::{GenericRange, Ranges};

    #[test]
    fn empty() {
        let mut ranges = Ranges::new();
        assert!(!ranges.remove(0..3));
        assert!(ranges.is_empty());
    }

    #[test]
    fn no_collisions() {
        let mut ranges = Ranges::from(0..3);
        assert!(!ranges.remove(5..10));
        assert_eq!(ranges, Ranges::from(0..3))
    }

    #[test]
    fn one_collision() {
        let mut ranges = Ranges::from(0..3);
        assert!(ranges.remove(2..5));
        assert_eq!(ranges, Ranges::from(0..2))
    }

    #[test]
    fn one_collision_two_results() {
        let mut ranges = Ranges::from(0..10);
        assert!(ranges.remove(2..5));
        assert_eq!(ranges.ranges, vec![(0..2).into(), (5..10).into()])
    }

    #[test]
    fn two_collisions() {
        let mut ranges = Ranges::from(0..3);
        assert!(ranges.insert(5..10));
        assert!(ranges.remove(2..7));
        assert_eq!(ranges.ranges, vec![(0..2).into(), (7..10).into()])
    }

    #[test]
    fn two_collisions_single_result() {
        let mut ranges = Ranges::from(0..3);
        assert!(ranges.insert(5..10));
        assert!(ranges.remove(2..15));
        assert_eq!(ranges, Ranges::from(0..2))
    }

    #[test]
    fn full() {
        let mut ranges = Ranges::from(0..3);
        assert!(ranges.remove(GenericRange::full()));
        assert!(ranges.is_empty())
    }

    #[test]
    fn muvlon() {
        // checks if inserting an empty range modifies the internal vector
        let mut ranges = Ranges::from(0..10);
        assert!(!ranges.remove(5..5));
        assert_eq!(ranges, Ranges::from(0..10));
    }

    #[test]
    fn issue_43() {
        let mut ranges = Ranges::from(23..36);
        assert!(ranges.insert(10..20));
        assert!(ranges.remove(10..20));
        assert_eq!(ranges, Ranges::from(23..36));
    }

    #[test]
    fn issue_43_proptest() {
        let mut ranges = Ranges::from(128..128);
        assert!(ranges.is_empty());
        assert!(ranges.insert(0..=0));
        assert_eq!(
            ranges.find_intersecting_ranges(&GenericRange::from(0..=0)),
            Some((0, 0))
        );
        assert!(ranges.remove(0..=0));
        assert_eq!(ranges, Ranges::new());
    }

    proptest! {
        #[ignore]
        #[test]
        fn sorted_and_disjoint(mut ranges in any::<Ranges<u8>>(), range in any::<GenericRange<u8>>()) {
            let _ = ranges.remove(range);
            let sorted_and_disjoint = ranges.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);
        }

        #[ignore]
        #[test]
        fn insert_remove_equality(
            (range, range2) in (any::<GenericRange<u16>>(), any::<GenericRange<u16>>())
            .prop_filter("Ranges need to be disjoint and first range may not be empty.",|&(ref r1, ref r2)| r1.is_disjoint(r2) && !r1.is_empty())
        ) {

            let mut ranges = Ranges::from(range);
            // no matter the input, inserting and removing a range should always return the original
            ranges.insert(range2);
            ranges.remove(range2);

            prop_assert_eq!(ranges, Ranges::from(range));
        }
    }
}