willow-data-model 0.4.1

use core::cmp::Ordering;
use core::fmt::{self, Debug, Formatter};
use core::hash::Hash;
use core::ops::{
    Bound, Range, RangeBounds, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive,
};

#[cfg(feature = "dev")]
use arbitrary::{Arbitrary, size_hint};

use order_theory::{
    GreatestElement, LeastElement, LowerSemilattice, PredecessorExceptForLeast,
    SuccessorExceptForGreatest, UpperSemilattice, finite_range,
};

/// A continuous subset of a type implementing [`Ord`].
///
/// It is either a [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) consisting of an inclusive start value and an exclusive end value, or an [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) consisting only of an inclusive start value.
///
/// ```
/// use std::ops::RangeBounds;
/// use willow_data_model::prelude::*;
///
/// assert!(WillowRange::<u8>::from(4..9).contains(&6));
/// assert!(!WillowRange::<u8>::from(4..9).contains(&12));
///
/// // You can create `WillowRanges` from arbitrary Rust ranges.
/// assert!(WillowRange::<u8>::from(4..=8) == WillowRange::<u8>::from(4..9));
/// ```
#[derive(Clone)]
pub enum WillowRange<T> {
    /// A [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) with an inclusive start value and an exclusive end value.
    Closed(Range<T>),
    /// An [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) with an inclusive start value.
    Open(RangeFrom<T>),
}

impl<T> RangeBounds<T> for WillowRange<T> {
    fn start_bound(&self) -> Bound<&T> {
        match self {
            Self::Closed(inner) => inner.start_bound(),
            Self::Open(inner) => inner.start_bound(),
        }
    }

    fn end_bound(&self) -> Bound<&T> {
        match self {
            Self::Closed(inner) => inner.end_bound(),
            Self::Open(inner) => inner.end_bound(),
        }
    }
}

impl<T> WillowRange<T>
where
    T: Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    /// Returns whether every possible item that is [included](core::ops::RangeBounds::contains) in `other` is also [included](core::ops::RangeBounds::contains) in `self`.
    ///
    /// If `other` is a [`WillowRange`], you can equivalently check `self >= other`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(4..9).includes_range(&(5..7)), true);
    /// assert_eq!(WillowRange::<u8>::from(4..9).includes_range(&(5..11)), false);
    /// assert_eq!(WillowRange::<u8>::from(4..9).includes_range(&(2..7)), false);
    /// assert_eq!(WillowRange::<u8>::from(4..9).includes_range(&(4..9)), true);
    /// ```
    #[doc(alias = "contains_range")]
    pub fn includes_range<R: RangeBounds<T>>(&self, other: &R) -> bool {
        match finite_range::partial_cmp(self, other) {
            None => false,
            Some(ord) => ord.is_ge(),
        }
    }

    /// Returns whether every possible item that is [included](core::ops::RangeBounds::contains) in `other` is also [included](core::ops::RangeBounds::contains) in `self` and there exists at least one item [included](core::ops::RangeBounds::contains) in `self` but not [included](core::ops::RangeBounds::contains) in `other`.
    ///
    /// If `other` is a [`WillowRange`], you can equivalently check `self > other`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(5..7)), true);
    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(5..11)), false);
    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(2..7)), false);
    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(4..9)), false);
    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(5..9)), true);
    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(4..8)), true);
    /// ```
    #[doc(alias = "strictly_contains_range")]
    pub fn strictly_includes_range<R: RangeBounds<T>>(&self, other: &R) -> bool {
        match finite_range::partial_cmp(self, other) {
            None => false,
            Some(ord) => ord.is_gt(),
        }
    }

    /// Returns whether the [`intersection`](WillowRange::intersection) of `self` and `other` [includes](core::ops::RangeBounds::contains) the given value.
    ///
    /// More efficient than actually creating the intersection and then calling [`includes`](core::ops::RangeBounds::contains).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert!(WillowRange::<u8>::from(4..9).does_intersection_include_value(&(5..7), &6));
    /// assert!(!WillowRange::<u8>::from(4..9).does_intersection_include_value(&(5..7), &4));
    /// assert!(!WillowRange::<u8>::from(4..9).does_intersection_include_value(&(5..7), &8));
    /// assert!(!WillowRange::<u8>::from(4..9).does_intersection_include_value(&(5..7), &99));
    /// ```
    pub fn does_intersection_include_value<R: RangeBounds<T>>(&self, other: &R, value: &T) -> bool {
        finite_range::is_in_greatest_lower_bound(value, self, other)
    }
}

impl<T> WillowRange<T>
where
    T: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    /// Converts any value which implements [`RangeBounds<T>`](core::ops::RangeBounds) into a [`WillowRange<T>`](WillowRange) containing the same values.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..)), (..).into());
    /// assert_eq!(WillowRange::<u8>::from_bounds(&(0..)), (0..).into());
    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..254)), (..254).into());
    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..255)), (..255).into());
    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..=254)), (..=254).into());
    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..=255)), (..=255).into());
    /// assert_eq!(WillowRange::<u8>::from_bounds(&(4..8)), (4..8).into());
    /// assert_eq!(WillowRange::<u8>::from_bounds(&(4..=8)), (4..=8).into());
    /// ```
    pub fn from_bounds<R>(bounds: &R) -> Self
    where
        R: RangeBounds<T>,
    {
        let start = match bounds.start_bound() {
            Bound::Unbounded => T::least(),
            Bound::Included(t) => t.clone(),
            Bound::Excluded(t) => t.try_predecessor().unwrap_or_else(|| T::least()),
        };

        match bounds.end_bound() {
            Bound::Unbounded => return Self::Open(start..),
            Bound::Included(t) => match t.try_successor() {
                Some(succ) => return Self::Closed(start..succ),
                None => return Self::Open(start..),
            },
            Bound::Excluded(t) => return Self::Closed(start..t.clone()),
        }
    }

    /// Returns the [intersection](https://willowprotocol.org/specs/grouping-entries/index.html#range_intersection) of `self` and `other`, i.e., the [`WillowRange`] which [includes](core::ops::RangeBounds::contains) exactly those values [included](core::ops::RangeBounds::contains) in both `self` and `other`.
    ///
    /// If you want to check whether some value is [included](core::ops::RangeBounds::contains) in the intersecion of two ranges, prefer [`WillowRange::does_intersection_include_value`] over explicitly constructing the intersection.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(4..9).intersection(&(5..7)), (5..7).into());
    /// assert_eq!(WillowRange::<u8>::from(4..9).intersection(&(5..11)), (5..9).into());
    /// assert_eq!(WillowRange::<u8>::from(4..9).intersection(&(2..7)), (4..7).into());
    /// assert!(WillowRange::<u8>::from(4..9).intersection(&(11..14)).is_empty());
    /// assert!(WillowRange::<u8>::from(4..9).intersection(&(6..6)).is_empty());
    /// ```
    #[doc(alias("intersect", "greatest_lower_bound", "glb", "meet"))]
    pub fn intersection<R: RangeBounds<T>>(&self, other: &R) -> Self {
        Self::from_bounds(&finite_range::greatest_lower_bound(self, other))
    }
}

impl<T> From<Range<T>> for WillowRange<T> {
    fn from(value: Range<T>) -> Self {
        Self::Closed(value)
    }
}

impl<T> From<RangeFrom<T>> for WillowRange<T> {
    fn from(value: RangeFrom<T>) -> Self {
        Self::Open(value)
    }
}

impl<T> From<RangeFull> for WillowRange<T>
where
    T: LeastElement,
{
    fn from(_value: RangeFull) -> Self {
        Self::Open(T::least()..)
    }
}

impl<T> From<RangeInclusive<T>> for WillowRange<T>
where
    T: SuccessorExceptForGreatest,
{
    fn from(value: RangeInclusive<T>) -> Self {
        let (start, end) = value.into_inner();
        match end.try_successor() {
            None => Self::Open(start..),
            Some(succ) => Self::Closed(start..succ),
        }
    }
}

impl<T> From<RangeTo<T>> for WillowRange<T>
where
    T: LeastElement,
{
    fn from(value: RangeTo<T>) -> Self {
        Self::Closed(T::least()..value.end)
    }
}

impl<T> From<RangeToInclusive<T>> for WillowRange<T>
where
    T: LeastElement + SuccessorExceptForGreatest,
{
    fn from(value: RangeToInclusive<T>) -> Self {
        match value.end.try_successor() {
            None => Self::Open(T::least()..),
            Some(succ) => Self::Closed(T::least()..succ),
        }
    }
}

impl<T: Debug> Debug for WillowRange<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match self {
            Self::Closed(r) => r.fmt(f),
            Self::Open(r) => r.fmt(f),
        }
    }
}

/// Two [`WillowRanges`](WillowRange) are equal iff they contain the same values.
impl<T> PartialEq<WillowRange<T>> for WillowRange<T>
where
    T: Ord + SuccessorExceptForGreatest + PredecessorExceptForLeast,
{
    fn eq(&self, other: &WillowRange<T>) -> bool {
        finite_range::eq(self, other)
    }

    #[allow(clippy::partialeq_ne_impl)]
    fn ne(&self, other: &WillowRange<T>) -> bool {
        finite_range::ne(self, other)
    }
}

impl<T: Eq> Eq for WillowRange<T> where
    T: Ord + SuccessorExceptForGreatest + PredecessorExceptForLeast
{
}

/// A range is less than another iff all values contained in the first are also contained in the other.
impl<T> PartialOrd<WillowRange<T>> for WillowRange<T>
where
    T: Ord + SuccessorExceptForGreatest + PredecessorExceptForLeast,
{
    fn partial_cmp(&self, other: &WillowRange<T>) -> Option<Ordering> {
        finite_range::partial_cmp(self, other)
    }
}

// Have to implement this manually beause Range and RangeFrom are not Clone.
#[cfg(feature = "dev")]
impl<'a, T: Arbitrary<'a>> Arbitrary<'a> for WillowRange<T> {
    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
        if bool::arbitrary(u)? {
            Ok(Self::Closed(T::arbitrary(u)?..T::arbitrary(u)?))
        } else {
            Ok(Self::Open(T::arbitrary(u)?..))
        }
    }

    fn try_size_hint(
        depth: usize,
    ) -> arbitrary::Result<(usize, Option<usize>), arbitrary::MaxRecursionReached> {
        Ok(size_hint::or(
            size_hint::and_all(&[
                bool::try_size_hint(depth)?,
                T::try_size_hint(depth)?,
                T::try_size_hint(depth)?,
            ]),
            size_hint::and(bool::try_size_hint(depth)?, T::try_size_hint(depth)?),
        ))
    }
}

impl<T> WillowRange<T> {
    /// Returns whether `self` is a [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(3..8).is_closed(), true);
    /// assert_eq!(WillowRange::<u8>::from(3..255).is_closed(), true);
    /// assert_eq!(WillowRange::<u8>::from(3..=255).is_closed(), false);
    /// assert_eq!(WillowRange::<u8>::from(3..).is_closed(), false);
    /// ```
    pub fn is_closed(&self) -> bool {
        matches!(self, Self::Closed(_))
    }

    /// Returns whether `self` is an [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(3..8).is_open(), false);
    /// assert_eq!(WillowRange::<u8>::from(3..255).is_open(), false);
    /// assert_eq!(WillowRange::<u8>::from(3..=255).is_open(), true);
    /// assert_eq!(WillowRange::<u8>::from(3..).is_open(), true);
    /// ```
    pub fn is_open(&self) -> bool {
        matches!(self, Self::Open(_))
    }

    /// Returns a reference to the [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value) of `self`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(3..8).start(), &3);
    /// assert_eq!(WillowRange::<u8>::from(..8).start(), &0);
    /// ```
    pub fn start(&self) -> &T {
        match self {
            Self::Closed(Range { start, .. }) => start,
            Self::Open(RangeFrom { start }) => start,
        }
    }

    /// Returns a mutable reference to the [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value) of `self`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(3..8).start_mut(), &mut 3);
    /// assert_eq!(WillowRange::<u8>::from(..8).start_mut(), &mut 0);
    /// ```
    pub fn start_mut(&mut self) -> &mut T {
        match self {
            Self::Closed(Range { start, .. }) => start,
            Self::Open(RangeFrom { start }) => start,
        }
    }

    /// Returns a reference to the [end value](https://willowprotocol.org/specs/grouping-entries/index.html#end_value) of `self`, or `None` if the range [is open](WillowRange::is_open).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(3..8).end(), Some(&8));
    /// assert_eq!(WillowRange::<u8>::from(3..=8).end(), Some(&9));
    /// assert_eq!(WillowRange::<u8>::from(3..).end(), None);
    /// ```
    pub fn end(&self) -> Option<&T> {
        match self {
            Self::Closed(Range { end, .. }) => Some(end),
            Self::Open(_) => None,
        }
    }

    /// Returns a mutable reference to the [end value](https://willowprotocol.org/specs/grouping-entries/index.html#end_value) of `self`, or `None` if the range [is open](WillowRange::is_open).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(3..8).end_mut(), Some(&mut 8));
    /// assert_eq!(WillowRange::<u8>::from(3..=8).end_mut(), Some(&mut 9));
    /// assert_eq!(WillowRange::<u8>::from(3..).end_mut(), None);
    /// ```
    pub fn end_mut(&mut self) -> Option<&mut T> {
        match self {
            Self::Closed(Range { end, .. }) => Some(end),
            Self::Open(_) => None,
        }
    }

    /// Converts this range into a different range by applying a function to all endpoints.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(
    ///     WillowRange::<u8>::from(3..8).map(|x| (x + 1) as u16),
    ///     WillowRange::<u16>::from(4..9),
    /// );
    /// ```
    pub fn map<U, F>(self, mut f: F) -> WillowRange<U>
    where
        F: FnMut(T) -> U,
    {
        match self {
            Self::Closed(Range { start, end }) => (f(start)..f(end)).into(),
            Self::Open(RangeFrom { start }) => (f(start)..).into(),
        }
    }

    /// Unsafely reinterprets a reference to a range as a reference to a range of a different type of boundaries.
    ///
    /// # Safety
    ///
    /// This is safe only if `&T` and `&U` have an identical layout in memory.
    pub unsafe fn cast<U>(&self) -> &WillowRange<U> {
        unsafe { &*(self as *const Self as *const WillowRange<U>) }
    }
}

impl<T> WillowRange<T>
where
    T: Ord,
{
    /// Returns whether `self` is [empty](https://willowprotocol.org/specs/grouping-entries/index.html#range_empty), i.e., whether it [includes](core::ops::RangeBounds::contains) no values.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::from(4..5).is_empty(), false);
    /// assert_eq!(WillowRange::<u8>::from(255..).is_empty(), false);
    /// assert_eq!(WillowRange::<u8>::from(4..4).is_empty(), true);
    /// assert_eq!(WillowRange::<u8>::from(4..3).is_empty(), true);
    /// ```
    pub fn is_empty(&self) -> bool {
        match self {
            Self::Closed(r) => r.start >= r.end,
            Self::Open(_) => false,
        }
    }
}

impl<T> WillowRange<T>
where
    T: SuccessorExceptForGreatest,
{
    /// Returns the [`WillowRange`] which [includes](core::ops::RangeBounds::contains) `t` but no other value.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::singleton(5), (5..6).into());
    /// assert_eq!(WillowRange::<u8>::singleton(255), (255..).into());
    /// ```
    pub fn singleton(t: T) -> Self {
        match t.try_successor() {
            Some(succ) => Self::Closed(t..succ),
            None => Self::Open(t..),
        }
    }
}

impl<T> WillowRange<T>
where
    T: LeastElement,
{
    /// Returns the `WillowRange` which [includes](core::ops::RangeBounds::contains) every value of type `T`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::full(), (..).into());
    /// ```
    pub fn full() -> Self {
        (T::least()..).into()
    }

    /// Returns whether `self` is the full range, i.e., the range which [includes](core::ops::RangeBounds::contains) every value of type `T`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::full().is_full(), true);
    /// assert_eq!(WillowRange::<u8>::from(1..).is_full(), false);
    /// assert_eq!(WillowRange::<u8>::from(0..255).is_full(), false);
    /// ```
    pub fn is_full(&self) -> bool {
        match self {
            Self::Closed(_) => false,
            Self::Open(RangeFrom { start }) => start.is_least(),
        }
    }
}

impl<T> LeastElement for WillowRange<T>
where
    T: Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn least() -> Self {
        (T::least()..T::least()).into()
    }
}

impl<T> GreatestElement for WillowRange<T>
where
    T: Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn greatest() -> Self {
        (..).into()
    }
}

impl<T> LowerSemilattice for WillowRange<T>
where
    T: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn greatest_lower_bound(&self, other: &Self) -> Self {
        Self::from_bounds(&finite_range::greatest_lower_bound(self, other))
    }
}

impl<T> UpperSemilattice for WillowRange<T>
where
    T: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn least_upper_bound(&self, other: &Self) -> Self {
        Self::from_bounds(&finite_range::least_upper_bound(self, other))
    }
}

impl<T> Hash for WillowRange<T>
where
    T: Hash + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
        if self.is_least() {
            255u8.hash(state);
        } else if self.is_greatest() {
            254u8.hash(state);
        } else {
            match self {
                Self::Closed(inner) => {
                    253u8.hash(state);
                    inner.hash(state)
                }
                Self::Open(inner) => {
                    253u8.hash(state);
                    inner.hash(state)
                }
            }
        }
    }
}