ranges 0.3.3

use core::cmp::Ordering;
use core::ops::{Bound, Range, RangeBounds, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive};

use crate::Domain;

/// Trait implementation of `Arbitrary` for use in fuzzers.
#[cfg(feature = "arbitrary")]
mod arbitrary;
/// Method implementation to calculate if an object is contained in a range.
mod contains;
/// Method implementations to calculate difference of two ranges. Includes support for `Sub` operation trait.
mod difference;
/// Method implementation to calculate if a range is empty.
/// Range inversion ending in an empty range is in the `invert` module.
mod empty;
/// Range formatting with several base implementations for all formatting traits.
mod format;
/// Trait implementation of `Hash`.
mod hash;
/// Method implementations for intersecting two ranges. Includes support for `BitAnd` operation trait.
mod intersect;
/// Method implementations for making a discrete start-bound range into an `Iterator`.
mod into_iter;
/// Method implementation, related functions and structs to invert a range.
pub(crate) mod invert;
/// Trait implementation of `Arbitrary` for use in proptest.
#[cfg(any(feature = "proptest", test))]
mod proptest;
/// Method implementation and related functions to calculate relation of ranges.
pub(crate) mod relation;
/// Method implementations for singleton construction and checking.
mod singleton;
/// Method implementations to calculate symmetric difference of two ranges. Includes support for `BitXor` operation trait.
mod symmetric_difference;
/// Method implementations to calculate union of two ranges. Includes support for `BitOr` operation trait.
mod union;

/// A generic analog to core/std ranges.
///
/// Because this type allows more range types, it comes with the cost of a few guarantees that need
/// to be uphold.
///
/// First of all, `start` is always less than or equal to `end`.
/// Secondly, both bounds are in the `Domain` that is implemented for `T`.
/// In case the constructor encounters a value outside of the domain, the value is clamped to the
/// full domain range.
///
/// # Note
/// The notation of `(-inf` and `+inf)` is used as an equivalent to the domain minimum and maximum,
/// even if the implementing domain may not be unbound or excluding in either direction.
#[derive(Copy, Clone, Debug)]
pub struct GenericRange<T> {
    /// Start of range. It is assumed to be smaller or equal to `end`.
    pub(crate) start: Bound<T>,
    /// End of range. It is assumed to be bigger or equal to `start`.
    pub(crate) end: Bound<T>,
}

/// Constructors and relevant comparison methods.
impl<T: Domain> GenericRange<T> {
    /// Creates a new [`GenericRange`](#) using the domain minimum and maximum as start and end.
    ///
    /// # core/std equivalent
    /// [`RangeFull`](https://doc.rust-lang.org/core/ops/struct.RangeFull.html) or `..`.
    ///
    /// # Interval notation
    /// `(-inf, +inf)`
    #[must_use]
    pub fn full() -> Self {
        Self {
            start: T::minimum(),
            end: T::maximum(),
        }
    }

    /// Returns true if the start is the domain minimum and the end is the domain maximum.
    #[must_use]
    pub fn is_full(&self) -> bool {
        *self == Self::full()
    }

    /// Returns true if the range start is open/excluded.
    #[must_use]
    pub fn is_left_open(&self) -> bool {
        match self.start {
            Bound::Excluded(_) => true,
            Bound::Included(_) | Bound::Unbounded => false,
        }
    }

    /// Returns true if the range start is closed/included.
    #[must_use]
    pub fn is_left_closed(&self) -> bool {
        match self.start {
            Bound::Included(_) => true,
            Bound::Excluded(_) | Bound::Unbounded => false,
        }
    }

    /// Returns true if the range start is unbounded.
    #[must_use]
    pub fn is_left_unbounded(&self) -> bool {
        match self.start {
            Bound::Unbounded => true,
            Bound::Excluded(_) | Bound::Included(_) => false,
        }
    }

    /// Returns true if the range end is open/excluded.
    #[must_use]
    pub fn is_right_open(&self) -> bool {
        match self.end {
            Bound::Excluded(_) => true,
            Bound::Included(_) | Bound::Unbounded => false,
        }
    }

    /// Returns true if the range end is closed/included.
    #[must_use]
    pub fn is_right_closed(&self) -> bool {
        match self.end {
            Bound::Included(_) => true,
            Bound::Excluded(_) | Bound::Unbounded => false,
        }
    }

    /// Returns true if the range end is unbounded.
    #[must_use]
    pub fn is_right_unbounded(&self) -> bool {
        match self.end {
            Bound::Unbounded => true,
            Bound::Excluded(_) | Bound::Included(_) => false,
        }
    }

    //

    /// Convenience method calling [`new_left_open_right_unbounded`](#method.new_left_open_right_unbounded).
    #[must_use]
    pub fn new_greater_than(start: T) -> Self {
        Self::new_left_open_right_unbounded(start)
    }

    /// Creates a new [`GenericRange`](#) with an open/excluded start and an unbound end.
    /// Convenience method equivalent is [`new_greater_than`](#method.new_greater_than).
    ///
    /// # core/std equivalent
    /// There is no equivalent because open/excluded starts are not representable.
    ///
    /// # Interval notation
    /// `(start, +inf)`
    #[must_use]
    pub fn new_left_open_right_unbounded(start: T) -> Self {
        Self::new_with_bounds(Bound::Excluded(start), Bound::Unbounded)
    }

    /// Returns true if the range start is open/excluded and the end is unbounded.
    #[must_use]
    pub fn is_left_open_right_unbounded(&self) -> bool {
        self.is_left_open() && self.is_right_unbounded()
    }

    //

    /// Convenience method calling [`new_left_closed_right_unbounded`](#method.new_left_closed_right_unbounded).
    #[must_use]
    pub fn new_at_least(start: T) -> Self {
        Self::new_left_closed_right_unbounded(start)
    }

    /// Creates a new [`GenericRange`](#) with a closed/included start and an unbound end.
    /// Convenience method equivalent is [`new_at_least`](#method.new_at_least).
    ///
    /// # core/std equivalent
    /// [`RangeFrom`](https://doc.rust-lang.org/core/ops/struct.RangeFrom.html) or `start..`.
    ///
    /// # Interval notation
    /// `[start, +inf)`
    #[must_use]
    pub fn new_left_closed_right_unbounded(start: T) -> Self {
        Self::new_with_bounds(Bound::Included(start), Bound::Unbounded)
    }

    /// Returns true if the range start is closed/included and the end is unbounded.
    #[must_use]
    pub fn is_left_closed_right_unbounded(&self) -> bool {
        self.is_left_closed() && self.is_right_unbounded()
    }

    //

    /// Convenience method calling [`new_left_unbounded_right_open`](#method.new_left_unbounded_right_open).
    #[must_use]
    pub fn new_less_than(end: T) -> Self {
        Self::new_left_unbounded_right_open(end)
    }

    /// Creates a new [`GenericRange`](#) with an unbounded start and an open/excluded end.
    /// Convenience method equivalent is [`new_less_than`](#method.new_less_than).
    ///
    /// # core/std equivalent
    /// [`RangeTo`](https://doc.rust-lang.org/core/ops/struct.RangeTo.html) or `..end`.
    ///
    /// # Interval notation
    /// `(-inf, end)`
    #[must_use]
    pub fn new_left_unbounded_right_open(end: T) -> Self {
        Self::new_with_bounds(Bound::Unbounded, Bound::Excluded(end))
    }

    /// Returns true if the range start is unbounded and the end is open/excluded.
    #[must_use]
    pub fn is_left_unbounded_right_open(&self) -> bool {
        self.is_left_unbounded() && self.is_right_open()
    }

    //

    /// Convenience method calling [`new_left_unbounded_right_closed`](#method.new_left_unbounded_right_closed).
    #[must_use]
    pub fn new_at_most(end: T) -> Self {
        Self::new_left_unbounded_right_closed(end)
    }

    /// Creates a new [`GenericRange`](#) with an unbounded start and a closed/included end.
    /// Convenience method equivalent is [`new_at_most`](#method.new_at_most).
    ///
    /// # core/std equivalent
    /// [`RangeToInclusive`](https://doc.rust-lang.org/core/ops/struct.RangeToInclusive.html) or `..=end`.
    ///
    /// # Interval notation
    /// `(-inf, end]`
    #[must_use]
    pub fn new_left_unbounded_right_closed(end: T) -> Self {
        Self::new_with_bounds(Bound::Unbounded, Bound::Included(end))
    }

    /// Returns true if the range start is unbounded and the end is closed/included.
    #[must_use]
    pub fn is_left_unbounded_right_closed(&self) -> bool {
        self.is_left_unbounded() && self.is_right_closed()
    }

    //

    /// Convenience method calling [`new_left_open_right_open`](#method.new_left_open_right_open).
    #[must_use]
    pub fn new_open(start: T, end: T) -> Self {
        Self::new_left_open_right_open(start, end)
    }

    /// Creates a new [`GenericRange`](#) with an open/excluded start and end.
    /// Convenience method equivalent is [`new_open`](#method.new_open).
    ///
    /// # core/std equivalent
    /// There is no equivalent because open/excluded starts are not representable.
    ///
    /// # Interval notation
    /// `(start, end)`
    #[must_use]
    pub fn new_left_open_right_open(start: T, end: T) -> Self {
        Self::new_with_bounds(Bound::Excluded(start), Bound::Excluded(end))
    }

    /// Returns true if the range start and end are open/excluded.
    #[must_use]
    pub fn is_left_open_right_open(&self) -> bool {
        self.is_left_open() && self.is_right_open()
    }

    //

    /// Convenience method calling [`new_left_closed_right_closed`](#method.new_left_closed_right_closed).
    #[must_use]
    pub fn new_closed(start: T, end: T) -> Self {
        Self::new_left_closed_right_closed(start, end)
    }

    /// Creates a new [`GenericRange`](#) with a closed/included start and end.
    /// Convenience method equivalent is [`new_closed`](#method.new_closed).
    ///
    /// # core/std equivalent
    /// [`RangeInclusive`](https://doc.rust-lang.org/core/ops/struct.RangeInclusive.html) or `start..=end`.
    ///
    /// # Interval notation
    /// `[start, end]`
    #[must_use]
    pub fn new_left_closed_right_closed(start: T, end: T) -> Self {
        Self::new_with_bounds(Bound::Included(start), Bound::Included(end))
    }

    /// Returns true if the range start and end are closed/included.
    #[must_use]
    pub fn is_left_closed_right_closed(&self) -> bool {
        self.is_left_closed() && self.is_right_closed()
    }

    //

    /// Convenience method calling [`new_left_closed_right_open`](#method.new_left_closed_right_open).
    #[must_use]
    pub fn new_closed_open(start: T, end: T) -> Self {
        Self::new_left_closed_right_open(start, end)
    }

    /// Creates a new [`GenericRange`](#) with a closed/included start and an open/excluded end.
    /// Convenience method equivalent is [`new_closed_open`](#method.new_closed_open).
    ///
    /// # core/std equivalent
    /// [`Range`](https://doc.rust-lang.org/core/ops/struct.Range.html) or `start..end`.
    ///
    /// # Interval notation
    /// `[start, end)`
    #[must_use]
    pub fn new_left_closed_right_open(start: T, end: T) -> Self {
        Self::new_with_bounds(Bound::Included(start), Bound::Excluded(end))
    }

    /// Returns true if the range start is closed/included and the end is open/excluded.
    #[must_use]
    pub fn is_left_closed_right_open(&self) -> bool {
        self.is_left_closed() && self.is_right_open()
    }

    //

    /// Convenience method calling [`new_left_open_right_closed`](#method.new_left_open_right_closed).
    #[must_use]
    pub fn new_open_closed(start: T, end: T) -> Self {
        Self::new_left_open_right_closed(start, end)
    }

    /// Creates a new [`GenericRange`](#) with a closed/included start and an open/excluded end.
    /// Convenience method equivalent is [`new_open_closed`](#method.new_open_closed).
    ///
    /// # core/std equivalent
    /// There is no equivalent because open/excluded starts are not representable.
    ///
    /// # Interval notation
    /// `(start, end]`
    #[must_use]
    pub fn new_left_open_right_closed(start: T, end: T) -> Self {
        Self::new_with_bounds(Bound::Excluded(start), Bound::Included(end))
    }

    /// Returns true if the range start is open/excluded and the end is closed/included.
    #[must_use]
    pub fn is_left_open_right_closed(&self) -> bool {
        self.is_left_open() && self.is_right_closed()
    }

    //

    /// Custom range from [`Bound`s](https://doc.rust-lang.org/core/ops/enum.Bound.html).
    ///
    /// # Panics
    /// It is asserted that `start <= end`.
    #[must_use]
    #[allow(clippy::panic)]
    pub fn new_with_bounds(start: Bound<T>, end: Bound<T>) -> Self {
        let domain_range = Self::full();

        let start = match Self::cmp_start_start(bound_owned_to_ref(&start), domain_range.start_bound()) {
            Ordering::Less | Ordering::Equal => T::minimum(),
            Ordering::Greater => start,
        };

        let end = match Self::cmp_end_end(bound_owned_to_ref(&end), domain_range.end_bound()) {
            Ordering::Less | Ordering::Equal => end,
            Ordering::Greater => T::maximum(),
        };

        match (bound_owned_to_ref(&start), bound_owned_to_ref(&end)) {
            (Bound::Unbounded, _) | (_, Bound::Unbounded) => (),
            (Bound::Included(start), Bound::Included(end))
            | (Bound::Included(start), Bound::Excluded(end))
            | (Bound::Excluded(start), Bound::Included(end))
            | (Bound::Excluded(start), Bound::Excluded(end)) => {
                assert!(start <= end, "range start has to be less or equal to the end");
            }
        }

        Self { start, end }
    }
}

impl<T> RangeBounds<T> for GenericRange<T> {
    #[must_use]
    fn start_bound(&self) -> Bound<&T> {
        bound_owned_to_ref(&self.start)
    }

    #[must_use]
    fn end_bound(&self) -> Bound<&T> {
        bound_owned_to_ref(&self.end)
    }
}

/// Converts a reference of a bound with owned data to a owned Bound with referenced data.
const fn bound_owned_to_ref<T>(bound: &Bound<T>) -> Bound<&T> {
    match *bound {
        Bound::Included(ref end) => Bound::Included(end),
        Bound::Excluded(ref end) => Bound::Excluded(end),
        Bound::Unbounded => Bound::Unbounded,
    }
}

impl<T: Domain> PartialEq for GenericRange<T> {
    fn eq(&self, other: &Self) -> bool {
        self.is_equal(other)
    }
}

impl<T: Domain> Eq for GenericRange<T> {}

/// Converts the `Range` using [`Self::closed_open(range.start, range.end)`](#method.closed_open).
impl<T: Domain> From<Range<T>> for GenericRange<T> {
    #[must_use]
    fn from(range: Range<T>) -> Self {
        Self::new_closed_open(range.start, range.end)
    }
}

/// Converts the `RangeFrom` using [`Self::at_least(range.start)`](#method.at_least).
impl<T: Domain> From<RangeFrom<T>> for GenericRange<T> {
    #[must_use]
    fn from(range: RangeFrom<T>) -> Self {
        Self::new_at_least(range.start)
    }
}

/// Converts the `RangeFull` using [`Self::full()`](#method.full).
impl<T: Domain> From<RangeFull> for GenericRange<T> {
    #[must_use]
    fn from(_range: RangeFull) -> Self {
        Self::full()
    }
}

/// Converts the `RangeInclusive` using [`Self::closed(start, end)`](#method.closed).
impl<T: Domain> From<RangeInclusive<T>> for GenericRange<T> {
    #[must_use]
    fn from(range: RangeInclusive<T>) -> Self {
        let (start, end) = range.into_inner();
        Self::new_closed(start, end)
    }
}

/// Converts the `RangeTo` using [`Self::less_than(range.end)`](#method.less_than).
impl<T: Domain> From<RangeTo<T>> for GenericRange<T> {
    #[must_use]
    fn from(range: RangeTo<T>) -> Self {
        Self::new_less_than(range.end)
    }
}

/// Converts the `RangeToInclusive` using [`Self::at_most(range.end)`](#method.at_most).
impl<T: Domain> From<RangeToInclusive<T>> for GenericRange<T> {
    #[must_use]
    fn from(range: RangeToInclusive<T>) -> Self {
        Self::new_at_most(range.end)
    }
}

/// Converts the tuple using [`Self::with_bounds(tuple.0, tuple.1)`](#method.with_bounds).
impl<T: Domain> From<(Bound<T>, Bound<T>)> for GenericRange<T> {
    #[must_use]
    fn from(range: (Bound<T>, Bound<T>)) -> Self {
        Self::new_with_bounds(range.0, range.1)
    }
}

/// Result of a unary or binary operation.
#[allow(clippy::missing_inline_in_public_items, clippy::exhaustive_enums)]
#[derive(Debug, Clone, Copy, Eq, PartialEq)]
#[must_use = "a range operation might not always return another range and should be handled"]
pub enum OperationResult<T: Domain> {
    /// The operation resulted in an empty range.
    Empty,
    /// The operation resulted in a single range.
    Single(GenericRange<T>),
    /// The operation resulted in two ranges.
    Double(GenericRange<T>, GenericRange<T>),
}

#[cfg(test)]
pub(crate) mod tests {
    use core::cmp::Ordering;
    use core::iter::once;
    use core::ops::{Bound, RangeBounds};

    use proptest::prelude::*;

    use crate::GenericRange;

    #[test]
    fn from_core_ranges() {
        // [x, y) - x..y
        let generic = GenericRange::from(1..5);
        assert_eq!(generic.start_bound(), Bound::Included(&1));
        assert_eq!(generic.end_bound(), Bound::Excluded(&5));

        // [x, y] - x..=y
        let generic = GenericRange::from(6..=10);
        assert_eq!(generic.start_bound(), Bound::Included(&6));
        assert_eq!(generic.end_bound(), Bound::Included(&10));

        // [x, +inf) - x..
        let generic = GenericRange::from(12..);
        assert_eq!(generic.start_bound(), Bound::Included(&12));
        assert_eq!(generic.end_bound(), Bound::Included(&2_147_483_647));

        // (-inf, y) - ..y
        let generic = GenericRange::from(..15);
        assert_eq!(generic.start_bound(), Bound::Included(&-2_147_483_648));
        assert_eq!(generic.end_bound(), Bound::Excluded(&15));

        // (-inf, y] - ..=y
        let generic = GenericRange::from(..=20);
        assert_eq!(generic.start_bound(), Bound::Included(&-2_147_483_648));
        assert_eq!(generic.end_bound(), Bound::Included(&20));

        // (-inf, +inf) - ..
        let generic: GenericRange<usize> = GenericRange::from(..);
        assert_eq!(generic.start_bound(), Bound::Included(&0));
        assert_eq!(generic.end_bound(), Bound::Included(&18_446_744_073_709_551_615));

        // (x, y) - has no Rust equivalent
        let generic = GenericRange::from((Bound::Excluded(30), Bound::Excluded(42)));
        assert_eq!(generic.start_bound(), Bound::Excluded(&30));
        assert_eq!(generic.end_bound(), Bound::Excluded(&42));

        // (x, y] - has no Rust equivalent
        let generic = GenericRange::from((Bound::Excluded(45), Bound::Included(50)));
        assert_eq!(generic.start_bound(), Bound::Excluded(&45));
        assert_eq!(generic.end_bound(), Bound::Included(&50));

        // (x, +inf) - has no Rust equivalent
        let generic = GenericRange::from((Bound::Excluded(55), Bound::Unbounded));
        assert_eq!(generic.start_bound(), Bound::Excluded(&55));
        assert_eq!(generic.end_bound(), Bound::Included(&2_147_483_647));
    }

    pub(crate) fn exhaustive_discrete_range() -> impl Iterator<Item = GenericRange<Ordering>> {
        exhaustive_discrete_bound()
            .flat_map(|x| core::iter::repeat(x).zip(exhaustive_discrete_bound()))
            .filter_map(|(start, end)| match (start, end) {
                (Bound::Unbounded, _) | (_, Bound::Unbounded) => Some(GenericRange::new_with_bounds(start, end)),
                (Bound::Included(s), Bound::Included(e))
                | (Bound::Included(s), Bound::Excluded(e))
                | (Bound::Excluded(s), Bound::Included(e))
                | (Bound::Excluded(s), Bound::Excluded(e)) => {
                    if s <= e {
                        Some(GenericRange::new_with_bounds(start, end))
                    } else {
                        None
                    }
                }
            })
    }

    fn exhaustive_discrete_bound() -> impl Iterator<Item = Bound<Ordering>> {
        let unbound_iter = once(Bound::Unbounded);
        let included_iter = [Ordering::Less, Ordering::Equal, Ordering::Greater]
            .iter()
            .copied()
            .map(Bound::Included);
        let excluded_iter = [Ordering::Less, Ordering::Equal, Ordering::Greater]
            .iter()
            .copied()
            .map(Bound::Excluded);

        unbound_iter.chain(included_iter).chain(excluded_iter)
    }

    #[test]
    fn check_exhaustive_bound() {
        assert_eq!(exhaustive_discrete_bound().count(), 7);
    }

    #[test]
    fn check_exhaustive_range() {
        assert_eq!(exhaustive_discrete_range().count(), 37);
    }

    prop_compose! {
        pub fn random_discrete_range()((start, end) in any::<usize>().prop_flat_map(|end| (0..=end, Just(end))), range_type in 0..=7_usize) -> GenericRange<usize> {
            match range_type {
                0 => GenericRange::new_open(start, end),
                1 => GenericRange::new_closed(start, end),
                2 => GenericRange::new_open_closed(start, end),
                3 => GenericRange::new_closed_open(start, end),
                4 => GenericRange::new_greater_than(start),
                5 => GenericRange::new_at_least(start),
                6 => GenericRange::new_less_than(end),
                7 => GenericRange::new_at_most(end),
                _ => unreachable!(),
            }
        }
    }
}