ranges 0.3.3

use core::convert::Into;
use core::ops::{BitOr, BitOrAssign};

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

impl<T: Domain> Ranges<T> {
    /// Calculates the union of two ranges.
    ///
    /// # Examples
    /// Empty and single-entry ranges.
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges1 = Ranges::new();
    /// let ranges2 = 0..10;
    ///
    /// assert_eq!(ranges1 | ranges2, (0..10).into());
    /// ```
    /// Disjoint ranges.
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges1 = Ranges::from(0..3);
    /// let ranges2 = 5..8;
    ///
    /// assert_eq!(ranges1 | ranges2, vec![0..3, 5..8].into());
    /// ```
    /// Overlapping ranges.
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges1 = Ranges::from(vec![0..5, 6..9]);
    /// let ranges2 = 3..8;
    ///
    /// assert_eq!(ranges1 | ranges2, (0..9).into());
    /// ```
    #[allow(clippy::too_many_lines)]
    #[must_use]
    pub fn union<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();

        // for unionization, we extend the lesser subranges and
        // as soon as they become disjoint they get pushed

        #[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::Equal => {
                        // because we know subranges in one `Ranges` are disjoint, we can safely skip both here
                        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::Disjoint { self_less: true } => {
                        // we reached a disjoint rhs range, meaning the lhs one is complete and
                        // can not be extended anymore
                        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 } => {
                        // we reached a disjoint lhs range, meaning the rhs one is complete and
                        // can not be extended anymore
                        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 } | Arrangement::Overlapping { 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 } | Arrangement::Overlapping { 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::Containing { self_shorter: true }
                    | Arrangement::Starting { self_shorter: true, .. }
                    | Arrangement::Ending { self_shorter: true, .. } => {
                        // lhs is inside rhs, meaning we don't have to extend rhs
                        // and we simply advance lhs.
                        lhs_range = lhs_iter.next();
                    }
                    Arrangement::Containing { self_shorter: false }
                    | Arrangement::Starting {
                        self_shorter: false, ..
                    }
                    | Arrangement::Ending {
                        self_shorter: false, ..
                    } => {
                        // rhs is inside lhs, meaning we don't have to extend lhs
                        // and we simply advance rhs.
                        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', 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', 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) => {
                    return result;
                }
            }
        }
    }
}

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

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

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

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

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

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

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

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

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

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

        assert_eq!(ranges2.union(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.union(ranges2), Ranges::from(0..8));

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        assert_eq!(ranges2.union(ranges1), Ranges::from(0..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.union(ranges2), Ranges::from(0..9));
    }

    #[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.union(ranges1), Ranges::from(0..9));
    }

    #[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.union(ranges2).ranges, vec![(0..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.union(ranges1).ranges, vec![(0..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.union(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);
        }
    }
}