//! This module exposes helpers for working with types that implement

//! [`RangeBounds`].

use std::cmp::{self, Ord};

use std::ops::{Bound, RangeBounds};

/// An extension trait for [`RangeBounds`].

pub trait RangeBoundsExt<T>: RangeBounds<T> {

    /// Compute the intersection of two `RangeBound`s.

    ///

    /// In essence, this computes the intersection of the intervals described by bounds of the

    /// two objects.

    ///

    /// Returns `None` if the intersection of the two ranges is the empty set.

    fn intersect<'a, U: RangeBounds<T>>(

        &'a self,

        other: &'a U,

    ) -> Option<(Bound<&'a T>, Bound<&'a T>)>;

}

impl<T, R> RangeBoundsExt<T> for R

where

    R: RangeBounds<T>,

    T: Ord,

{

        use Bound::*;

                // The interval (n, n) = [n, n) = {} (empty set).

            }

            {

                // For any a > b, the intervals [a, b], [a, b), (a, b], (a, b) are empty.

            }

        }

}

/// Return the largest of `b1` and `b2`.

///

/// If one of the bounds is [Unbounded](Bound::Unbounded), the other will be returned.

    use Bound::*;

    }

/// Return the smallest of `b1` and `b2`.

///

/// If one of the bounds is [Unbounded](Bound::Unbounded), the other will be returned.

    use Bound::*;

    }

#[cfg(test)]

mod test {

    // @@ begin test lint list maintained by maint/add_warning @@

    #![allow(clippy::bool_assert_comparison)]

    #![allow(clippy::clone_on_copy)]

    #![allow(clippy::dbg_macro)]

    #![allow(clippy::mixed_attributes_style)]

    #![allow(clippy::print_stderr)]

    #![allow(clippy::print_stdout)]

    #![allow(clippy::single_char_pattern)]

    #![allow(clippy::unwrap_used)]

    #![allow(clippy::unchecked_duration_subtraction)]

    #![allow(clippy::useless_vec)]

    #![allow(clippy::needless_pass_by_value)]

    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->

    use super::*;

    use std::fmt::Debug;

    use std::time::{Duration, SystemTime};

    use Bound::{Excluded as Excl, Included as Incl, Unbounded};

    /// A helper that computes the intersection of `range1` and `range2`.

    ///

    /// This function also asserts that the intersection operation is commutative.

    fn intersect<'a, T, R: RangeBounds<T>>(

        range1: &'a R,

        range2: &'a R,

    ) -> Option<(Bound<&'a T>, Bound<&'a T>)>

    where

        T: PartialEq + Ord + Debug,

    {

        let intersection1 = range1.intersect(range2);

        let intersection2 = range2.intersect(range1);

        assert_eq!(intersection1, intersection2);

        intersection1

    }

    /// A helper for randomly generating either an inclusive or an exclusive bound with a

    /// particular value.

    fn random_bound<T>(value: T) -> Bound<T> {

        if rand::random() {

            Bound::Included(value)

        } else {

            Bound::Excluded(value)

        }

    }

    #[test]

    fn no_overlap() {

        #[allow(clippy::type_complexity)]

        const NON_OVERLAPPING_RANGES: &[(

            (Bound<usize>, Bound<usize>),

            (Bound<usize>, Bound<usize>),

        )] = &[

            // (1, 2) and (3, 4)

            ((Excl(1), Excl(2)), (Excl(3), Excl(4))),

            // (1, 2) and (2, 3)

            ((Excl(1), Excl(2)), (Excl(2), Excl(3))),

            // (1, 2) and [2, 3)

            ((Excl(1), Excl(2)), (Incl(2), Excl(3))),

            // (1, 2) and [2, 3]

            ((Excl(1), Excl(2)), (Incl(3), Incl(4))),

            // (-inf, 2) and [2, 3]

            ((Unbounded, Excl(2)), (Incl(2), Incl(3))),

            // (-inf, 2) and (2, inf)

            ((Unbounded, Excl(2)), (Excl(2), Unbounded)),

            // (-inf, 2) and [2, inf)

            ((Unbounded, Excl(2)), (Incl(2), Unbounded)),

        ];

        for (range1, range2) in NON_OVERLAPPING_RANGES {

            let intersection = intersect(range1, range2);

            assert!(

                intersection.is_none(),

                "{:?} and {:?} => {:?}",

                range1,

                range2,

                intersection

            );

        }

    }

    #[test]

    fn intersect_unbounded_start() {

        // (-inf, 3)

        let range1 = (Unbounded, Excl(3));

        // [2, 5]

        let range2 = (Incl(2), Incl(5));

        let intersection = intersect(&range1, &range2).unwrap();

        // intersection = [2 3]

        assert_eq!(intersection.start_bound(), Bound::Included(&2));

        assert_eq!(intersection.end_bound(), Bound::Excluded(&3));

    }

    #[test]

    fn intersect_unbounded_end() {

        // (8, inf)

        let range1 = (Excl(8), Unbounded);

        // [8, 20]

        let range2 = (Incl(8), Incl(20));

        let intersection = intersect(&range1, &range2).unwrap();

        // intersection = (8, 20]

        assert_eq!(intersection.start_bound(), Bound::Excluded(&8));

        assert_eq!(intersection.end_bound(), Bound::Included(&20));

    }

    #[test]

    fn intersect_unbounded_range() {

        #[allow(clippy::type_complexity)]

        const RANGES: &[(Bound<usize>, Bound<usize>)] = &[

            // (1, 2)

            (Excl(1), Excl(2)),

            // (1, 2]

            (Excl(1), Incl(2)),

            // [1, 2]

            (Incl(1), Incl(2)),

            // [1, 2)

            (Incl(1), Excl(2)),

            // (1, inf)

            (Excl(1), Unbounded),

            // [1, inf)

            (Incl(1), Unbounded),

            // (-inf, 2)

            (Unbounded, Excl(2)),

            // (-inf, 2]

            (Unbounded, Incl(2)),

        ];

        // The intersection of any interval I with (Unbounded, Unbounded) will be I.

        let range1 = (Unbounded, Unbounded);

        for range2 in RANGES {

            let range2 = (range2.0.as_ref(), range2.1.as_ref());

            assert_eq!(intersect(&range1, &range2).unwrap(), range2);

        }

    }

    #[test]

    fn intersect_time_bounds() {

        const MIN: Duration = Duration::from_secs(60);

        // time (relative to now):  0   1   2   3

        //                          |   |   |   |

        // [t1, t2]:                [.......]

        // [t3, t4]:                    [.......]

        // intersection:                [...]

        let now = SystemTime::now();

        let t1 = now;

        let t2 = now + 2 * MIN;

        let t3 = now + 1 * MIN;

        let t4 = now + 3 * MIN;

        let b1 = (Bound::Included(t1), Bound::Included(t2));

        let b2 = (Bound::Included(t3), Bound::Included(t4));

        let expected = (Bound::Included(&t3), Bound::Included(&t2));

        assert_eq!(intersect(&b1, &b2).unwrap(), expected);

        //  t1  -  -  t2  -  -

        //                   t3  -  -  t4

        //

        // time (relative to now):  0   1   2   3   4   5   6   7

        //                          |   |   |   |   |   |   |   |

        // [t1, t2]:                [.......]

        // [t3, t4]:                                [............]

        let t3 = now + 4 * MIN;

        let t4 = now + 7 * MIN;

        let b2 = (Bound::Included(t3), Bound::Included(t4));

        assert!(intersect(&b1, &b2).is_none());

    }

    #[test]

    fn combinatorial() {

        for i in 0..10 {

            for j in 0..10 {

                for k in 0..10 {

                    for l in 0..10 {

                        let range1 = (random_bound(i), random_bound(j));

                        let range2 = (random_bound(k), random_bound(l));

                        let intersection = intersect(&range1, &range2);

                        for witness in 0..10 {

                            let c1 = range1.contains(&witness);

                            let c2 = range2.contains(&witness);

                            let both_contain_witness = c1 && c2;

                            if both_contain_witness {

                                // If both ranges contain `witness` they definitely intersect.

                                assert!(intersection.unwrap().contains(&witness));

                            } else if let Some(intersection) = intersection {

                                // If one of them doesn't contain `witness`, `witness` is

                                // definitely not part of the intersection.

                                assert!(!intersection.contains(&witness));

                            }

                        }

                    }

                }

            }

        }

    }

}