ranges 0.3.3

use core::convert::Into;
use core::ops::{BitXor, BitXorAssign};

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

impl<T: Domain> Ranges<T> {
    /// Calculates the relative complement (difference) of two ranges.
    ///
    /// # Examples
    /// Empty range.
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges1 = Ranges::new();
    /// let ranges2 = 0..10;
    ///
    /// assert_eq!(ranges1 ^ ranges2, (0..10).into());
    /// ```
    /// Touching ranges.
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges1 = Ranges::from(0..3);
    /// let ranges2 = 3..8;
    ///
    /// assert_eq!(ranges1 ^ ranges2, (0..8).into());
    /// ```
    /// Overlapping multiple ranges.
    /// ```
    /// use ranges::{GenericRange, Ranges};
    ///
    /// let ranges1 = Ranges::from(vec![0..5, 6..9]);
    /// let ranges2 = 3..8;
    ///
    /// assert_eq!(
    ///     ranges1 ^ ranges2,
    ///     vec![0..3, 5..6, 8..9].into()
    /// );
    /// ```
    #[allow(clippy::too_many_lines)]
    #[must_use]
    pub fn symmetric_difference<R>(self, other: R) -> Self
    where
        R: Into<Self>,
    {
        let other_ranges = other.into();

        if other_ranges.is_empty() {
            return self;
        }

        if self.is_empty() {
            return other_ranges;
        }

        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();

        #[allow(clippy::expect_used)]
        loop {
            match (&lhs_range, &rhs_range) {
                // lhs and rhs still have ranges in them
                (&Some(ref lhs), &Some(ref rhs)) => match lhs.arrangement(rhs) {
                    // lhs and rhs are equal, so use next subranges for both
                    Arrangement::Equal => {
                        lhs_range = lhs_iter.next();
                        rhs_range = rhs_iter.next();
                    }
                    Arrangement::Disjoint { self_less: true } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        result.ranges.push(lhs);

                        lhs_range = lhs_iter.next();
                    }
                    Arrangement::Disjoint { self_less: false } => {
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        result.ranges.push(rhs);

                        rhs_range = rhs_iter.next();
                    }
                    Arrangement::Touching { self_less: true } => {
                        // we're touching the lhs, so we skip lhs and extend rhs
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        rhs_range = Some(GenericRange {
                            start: lhs.start,
                            end: rhs.end,
                        });
                        lhs_range = lhs_iter.next();
                    }
                    Arrangement::Touching { self_less: false } => {
                        // we're touching the rhs, so we skip rhs and extend lhs
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        lhs_range = Some(GenericRange {
                            start: rhs.start,
                            end: lhs.end,
                        });
                        rhs_range = rhs_iter.next();
                    }
                    Arrangement::Overlapping { self_less: true, .. } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        let left_disjoint = GenericRange {
                            start: lhs.start,
                            end: GenericRange::invert_border(rhs.start),
                        };

                        result.ranges.push(left_disjoint);

                        lhs_range = lhs_iter.next();
                        rhs_range = Some(GenericRange {
                            start: GenericRange::invert_border(lhs.end),
                            end: rhs.end,
                        });
                    }
                    Arrangement::Overlapping { self_less: false, .. } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        let left_disjoint = GenericRange {
                            start: rhs.start,
                            end: GenericRange::invert_border(lhs.start),
                        };

                        result.ranges.push(left_disjoint);

                        rhs_range = rhs_iter.next();
                        lhs_range = Some(GenericRange {
                            start: GenericRange::invert_border(rhs.end),
                            end: lhs.end,
                        });
                    }

                    Arrangement::Containing { self_shorter: true } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        let left_disjoint = GenericRange {
                            start: rhs.start,
                            end: GenericRange::invert_border(lhs.start),
                        };

                        result.ranges.push(left_disjoint);

                        lhs_range = lhs_iter.next();
                        rhs_range = Some(GenericRange {
                            start: GenericRange::invert_border(lhs.end),
                            end: rhs.end,
                        });
                    }
                    Arrangement::Containing { self_shorter: false } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        let left_disjoint = GenericRange {
                            start: lhs.start,
                            end: GenericRange::invert_border(rhs.start),
                        };

                        result.ranges.push(left_disjoint);

                        rhs_range = rhs_iter.next();
                        lhs_range = Some(GenericRange {
                            start: GenericRange::invert_border(rhs.end),
                            end: lhs.end,
                        });
                    }
                    Arrangement::Starting { self_shorter: true, .. } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        lhs_range = lhs_iter.next();

                        rhs_range = Some(GenericRange {
                            start: GenericRange::invert_border(lhs.end),
                            end: rhs.end,
                        });
                    }

                    Arrangement::Starting {
                        self_shorter: false, ..
                    } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        rhs_range = rhs_iter.next();

                        lhs_range = Some(GenericRange {
                            start: GenericRange::invert_border(rhs.end),
                            end: lhs.end,
                        });
                    }
                    Arrangement::Ending { self_shorter: true, .. } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        let left_disjoint = GenericRange {
                            start: rhs.start,
                            end: GenericRange::invert_border(lhs.start),
                        };

                        result.ranges.push(left_disjoint);

                        lhs_range = lhs_iter.next();
                        rhs_range = rhs_iter.next();
                    }
                    Arrangement::Ending {
                        self_shorter: false, ..
                    } => {
                        let lhs = lhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");
                        let rhs = rhs_range
                            .take()
                            .expect("we matched 'Some' earlier, so this can't be None");

                        let left_disjoint = GenericRange {
                            start: lhs.start,
                            end: GenericRange::invert_border(rhs.start),
                        };

                        result.ranges.push(left_disjoint);

                        lhs_range = lhs_iter.next();
                        rhs_range = rhs_iter.next();
                    }
                    Arrangement::Empty { .. } => unreachable!("internal guarantee broken: empty range in set"),
                },
                // rhs is empty
                (&Some(_), &None) => {
                    #[allow(clippy::integer_arithmetic)]
                    result.ranges.reserve(lhs_iter.len() + 1);

                    let lhs = lhs_range
                        .take()
                        .expect("we matched 'Some' earlier, so this can't be None");
                    result.ranges.push(lhs);
                    for lhs in lhs_iter {
                        result.ranges.push(lhs);
                    }

                    return result;
                }
                // lhs is empty
                (&None, &Some(_)) => {
                    #[allow(clippy::integer_arithmetic)]
                    result.ranges.reserve(rhs_iter.len() + 1);

                    let rhs = rhs_range
                        .take()
                        .expect("we matched 'Some' earlier, so this can't be None");
                    result.ranges.push(rhs);
                    for rhs in rhs_iter {
                        result.ranges.push(rhs);
                    }

                    return result;
                }
                // both iterators ended up empty at the same time
                (&None, &None) => {
                    // we're done
                    return result;
                }
            }
        }
    }
}

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

    #[must_use]
    fn bitxor(self, rhs: I) -> Self::Output {
        self.symmetric_difference(rhs.into())
    }
}

/// This calls [`self.symmetric_difference(other)`](#method.symmetric_difference) and replaces `self` with the result.
impl<T, I> BitXorAssign<I> for Ranges<T>
where
    I: Into<Ranges<T>>,
    T: Domain,
{
    fn bitxor_assign(&mut self, rhs: I) {
        let lhs = core::mem::replace(self, Self::new());
        let result = lhs.symmetric_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.symmetric_difference(ranges2), Ranges::from(0..10));

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

        assert_eq!(ranges2.symmetric_difference(ranges1), Ranges::from(0..10))
    }

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

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

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

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

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

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

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

        assert_eq!(ranges1.symmetric_difference(ranges2), Ranges::from(0..8));

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

        assert_eq!(ranges2.symmetric_difference(ranges1), Ranges::from(0..8));
    }

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

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

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

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

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

        assert_eq!(
            ranges1.symmetric_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.symmetric_difference(ranges1).ranges,
            vec![(0..3).into(), (8..10).into()]
        );
    }

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

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

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

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

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

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

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

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

    #[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.symmetric_difference(ranges2).ranges,
            vec![(0..3).into(), (5..6).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.symmetric_difference(ranges1).ranges,
            vec![(0..3).into(), (5..6).into(), (8..9).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.symmetric_difference(ranges2).ranges,
            vec![(0..3).into(), (5..6).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.symmetric_difference(ranges1).ranges,
            vec![(0..3).into(), (5..6).into(), (8..9).into(), (15..20).into()]
        );
    }

    proptest! {
        #[ignore]
        #[test]
        fn sorted_and_disjoint(ranges1 in any::<Ranges<u8>>(), ranges2 in any::<Ranges<u8>>()) {
            let result = ranges1.symmetric_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);
        }
    }
}