ranges 0.3.3

use core::convert::Into;
use core::ops::{BitAnd, BitAndAssign, Bound};

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

impl<T: Domain> Ranges<T> {
    /// Calculates the intersection of two ranges.
    ///
    /// # Examples
    /// Single overlapping ranges:
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges1 = Ranges::from(0..5);
    /// let ranges2 = 3..8;
    ///
    /// assert_eq!(ranges1 & ranges2, (3..5).into());
    /// ```
    /// Multiple overlapping ranges:
    /// ```
    /// use ranges::{GenericRange, Ranges};
    ///
    /// let ranges1 = Ranges::from(0..9);
    /// let ranges2 = Ranges::from(vec![-1..3, 6..11]);
    ///
    /// assert_eq!(ranges1 & ranges2, vec![0..3, 6..9].into())
    /// ```
    #[allow(clippy::too_many_lines)]
    #[must_use]
    pub fn intersect<R>(self, other: R) -> Self
    where
        R: Into<Self>,
    {
        let other_ranges = other.into();

        if other_ranges.is_empty() {
            return other_ranges;
        }

        if self.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();

        #[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) {
                    Arrangement::Disjoint { self_less: true } | Arrangement::Touching { self_less: true } => {
                        lhs_range = lhs_iter.next();
                    }
                    Arrangement::Disjoint { self_less: false } | Arrangement::Touching { self_less: false } => {
                        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");

                        result.ranges.push(GenericRange {
                            start: rhs.start,
                            end: lhs.end,
                        });

                        rhs_range = Some(GenericRange {
                            // IMPORTANT: we do this to prevent cloning.
                            // further calculations using this rhs range are mathematically the same
                            start: Bound::Unbounded,
                            end: rhs.end,
                        });

                        lhs_range = lhs_iter.next();
                    }
                    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");

                        result.ranges.push(GenericRange {
                            start: lhs.start,
                            end: rhs.end,
                        });

                        lhs_range = Some(GenericRange {
                            // IMPORTANT: we do this to prevent cloning.
                            // further calculations using this lhs range are mathematically the same
                            start: Bound::Unbounded,
                            end: lhs.end,
                        });

                        rhs_range = rhs_iter.next();
                    }

                    Arrangement::Containing { self_shorter: true }
                    | Arrangement::Starting { self_shorter: 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::Containing { self_shorter: false }
                    | Arrangement::Starting {
                        self_shorter: 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::Ending { self_shorter: true, .. } | Arrangement::Equal => {
                        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();
                        rhs_range = rhs_iter.next();
                    }

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

                        result.ranges.push(rhs);

                        lhs_range = lhs_iter.next();
                        rhs_range = rhs_iter.next();
                    }
                    Arrangement::Empty { .. } => unreachable!("internal guarantee broken: empty range in set"),
                },
                (&Some(_), &None) | (&None, &Some(_)) | (&None, &None) => {
                    return result;
                }
            }
        }
    }
}

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

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

/// This calls [`self.intersect(other)`](#method.intersect) and replaces `self` with the result.
impl<T: Domain> BitAndAssign<Ranges<T>> for Ranges<T> {
    fn bitand_assign(&mut self, rhs: Self) {
        let lhs = core::mem::replace(self, Self::new());
        let result = lhs.intersect(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.intersect(ranges2), Ranges::new());

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

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

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

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

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

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

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

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

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

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

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

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

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

        assert_eq!(ranges1.intersect(ranges2), Ranges::from(3..5));

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

        assert_eq!(ranges2.intersect(ranges1), Ranges::from(3..5));
    }

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

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

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

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

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

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

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

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

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

        assert_eq!(ranges1.intersect(ranges2), Ranges::from(3..10));

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

        assert_eq!(ranges2.intersect(ranges1), Ranges::from(3..10));
    }

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

    #[test]
    fn fsciammarella() {
        let ranges1 = Ranges::from(0..9);
        let ranges2 = Ranges::from(vec![GenericRange::from(-1..3), (6..11).into()]);

        assert_eq!(ranges1.intersect(ranges2).ranges, vec![(0..3).into(), (6..9).into()])
    }

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