willow-data-model 0.7.0

use core::cmp::Ordering;
use core::fmt::{self, Debug, Formatter};
use core::hash::Hash;
use core::ops::{Bound, RangeBounds};

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

use order_theory::{
    GreatestElement, LeastElement, SuccessorExceptForGreatest,
};

use crate::prelude::EmptyGrouping;

/// A non-empty [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) with an inclusive start value and a strictly-greater exclusive end value.
///
/// It includes all values that are greater than or equal to the start value *and* strictly less than the end value.
///
/// ```
/// use willow_data_model::prelude::*;
///
/// let r = ClosedRange::new(2, 7);
/// assert_eq!(r.start(), &2);
/// assert_eq!(r.end(), &7);
///
/// assert!(ClosedRange::try_new(7, 2).is_err());
/// assert!(ClosedRange::try_new(2, 2).is_err());
/// ```
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
#[repr(C)]
pub struct ClosedRange<T> {
    start: T,
    end: T,
}

impl<T: Debug> Debug for ClosedRange<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        self.start.fmt(f)?;
        write!(f, "..")?;
        self.end.fmt(f)?;
        Ok(())
    }
}

impl<T> PartialOrd for ClosedRange<T>
where
    T: PartialOrd,
{
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        match (
            self.start.partial_cmp(&other.start)?,
            self.end.partial_cmp(&other.end)?,
        ) {
            (Ordering::Equal, Ordering::Equal) => Some(Ordering::Equal),
            (cmp_start, cmp_end) => {
                if cmp_start.is_le() && cmp_end.is_ge() {
                    Some(Ordering::Greater)
                } else if cmp_start.is_ge() && cmp_end.is_le() {
                    Some(Ordering::Less)
                } else {
                    None
                }
            }
        }
    }
}

impl<T> ClosedRange<T>
where
    T: PartialOrd,
{
    /// Creates a new closed range, or an [`EmptyGrouping`] error if `start >= end`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert!(ClosedRange::try_new(2, 7).is_ok());
    /// assert!(ClosedRange::try_new(7, 2).is_err());
    /// assert!(ClosedRange::try_new(2, 2).is_err());
    /// ```
    pub fn try_new(start: T, end: T) -> Result<Self, EmptyGrouping> {
        let ret = Self { start, end };

        if ret.is_empty() {
            Err(EmptyGrouping)
        } else {
            Ok(ret)
        }
    }

    /// Creates a new closed range, panicking if it would be empty.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let yay = ClosedRange::new(2, 7);
    /// ```
    ///
    /// ```should_panic
    /// use willow_data_model::prelude::*;
    ///
    /// let nope = ClosedRange::new(7, 2);
    /// ```
    pub fn new(start: T, end: T) -> Self {
        Self::try_new(start, end).unwrap()
    }

    /// Returns whether the given value is included in `self`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r = ClosedRange::new(2, 7);
    /// assert!(r.includes_value(&2));
    /// assert!(!r.includes_value(&1));
    /// assert!(!r.includes_value(&7));
    /// ```
    pub fn includes_value(&self, t: &T) -> bool {
        self.start <= *t && self.end > *t
    }

    /// Returns whether the given value is included in `self` and `other`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r1 = ClosedRange::new(2, 7);
    /// let r2 = ClosedRange::new(5, 9);
    /// assert!(r1.includes_value_in_intersection(&r2, &5));
    /// assert!(!r1.includes_value_in_intersection(&r2, &2));
    /// assert!(!r1.includes_value_in_intersection(&r2, &7));
    /// assert!(!r1.includes_value_in_intersection(&r2, &22));
    /// ```
    pub fn includes_value_in_intersection(&self, other: &Self, t: &T) -> bool {
        self.includes_value(t) && other.includes_value(t)
    }

    /// Returns whether the given closed range is included in `self`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r = ClosedRange::new(2, 7);
    /// assert!(r.includes_closed_range(&ClosedRange::new(3, 6)));
    /// assert!(r.includes_closed_range(&ClosedRange::new(2, 5)));
    /// assert!(r.includes_closed_range(&ClosedRange::new(3, 7)));
    /// assert!(r.includes_closed_range(&ClosedRange::new(2, 7)));
    /// assert!(!r.includes_closed_range(&ClosedRange::new(1, 7)));
    /// assert!(!r.includes_closed_range(&ClosedRange::new(2, 8)));
    /// assert!(!r.includes_closed_range(&ClosedRange::new(9, 14)));
    /// ```
    pub fn includes_closed_range(&self, other: &Self) -> bool {
        self.start <= other.start && self.end >= other.end
    }

    /// Returns whether the given closed range is strictly included in `self`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r = ClosedRange::new(2, 7);
    /// assert!(r.strictly_includes_closed_range(&ClosedRange::new(2, 6)));
    /// assert!(r.strictly_includes_closed_range(&ClosedRange::new(3, 7)));
    /// assert!(r.strictly_includes_closed_range(&ClosedRange::new(3, 6)));
    /// assert!(!r.strictly_includes_closed_range(&ClosedRange::new(2, 7)));
    /// assert!(!r.strictly_includes_closed_range(&ClosedRange::new(1, 7)));
    /// assert!(!r.strictly_includes_closed_range(&ClosedRange::new(2, 8)));
    /// assert!(!r.strictly_includes_closed_range(&ClosedRange::new(9, 14)));
    /// ```
    pub fn strictly_includes_closed_range(&self, other: &Self) -> bool {
        self != other && self.includes_closed_range(other)
    }

    // Private because we never expose empty ranges.
    fn is_empty(&self) -> bool {
        self.start >= self.end
    }
}

impl<T> ClosedRange<T>
where
    T: PartialOrd + Clone,
{
    /// Returns the intersection between `self` and `other`, or an [`EmptyGrouping`] error if it would be empty.
    ///
    /// assert_eq!(
    ///     ClosedRange::new(2, 7).intersection_closed_range(ClosedRange::new(5, 9)),
    ///     Ok(ClosedRange::new(5, 7)),
    /// );
    /// assert!(
    ///     ClosedRange::new(2, 5).intersection_closed_range(ClosedRange::new(7, 9)).is_error(),
    /// );
    pub fn intersection_closed_range(&self, other: &Self) -> Result<Self, EmptyGrouping> {
        let start = match self.start.partial_cmp(other.start()) {
            None => return Err(EmptyGrouping),
            Some(Ordering::Less) => other.start().clone(),
            Some(_) => self.start().clone(),
        };

        let end = match self.end.partial_cmp(other.end()) {
            None => return Err(EmptyGrouping),
            Some(Ordering::Greater) => other.end().clone(),
            Some(_) => self.end().clone(),
        };

        Self::try_new(start, end)
    }
}

impl<T> ClosedRange<T> {
    /// Creates a new closed range, without enforcing non-emptyness.
    ///
    /// #### Safety
    ///
    /// Calling this method with `start >= end` is undefined behaviour.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let yay = unsafe { ClosedRange::new_unchecked(2, 7) };
    /// ```
    pub unsafe fn new_unchecked(start: T, end: T) -> Self {
        Self { start, end }
    }

    /// Returns a reference to the start value of this closed range.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r = ClosedRange::new(2, 7);
    /// assert_eq!(r.start(), &2);
    /// ```
    pub fn start(&self) -> &T {
        &self.start
    }

    /// Returns a reference to the end value of this closed range.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r = ClosedRange::new(2, 7);
    /// assert_eq!(r.end(), &7);
    /// ```
    pub fn end(&self) -> &T {
        &self.end
    }

    /// Takes ownership of a closed range and returns its start and end value.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r = ClosedRange::new(2, 7);
    /// assert_eq!(r.into_parts(), (2, 7));
    /// ```
    pub fn into_parts(self) -> (T, T) {
        (self.start, self.end)
    }
}

impl<T> RangeBounds<T> for ClosedRange<T> {
    fn start_bound(&self) -> Bound<&T> {
        Bound::Included(&self.start)
    }

    fn end_bound(&self) -> Bound<&T> {
        Bound::Excluded(&self.end)
    }
}

#[cfg(feature = "dev")]
impl<'a, T> Arbitrary<'a> for ClosedRange<T>
where
    T: Arbitrary<'a> + PartialOrd,
{
    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
        let start = T::arbitrary(u)?;
        let end = T::arbitrary(u)?;

        Self::try_new(start, end).map_err(|_| arbitrary::Error::IncorrectFormat)
    }

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

/// A non-empty continuous subset of a type implementing [`PartialOrd`].
///
/// It is either a [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) consisting of an inclusive start value and a strictly-greater 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>::new_closed(4, 9).contains(&6));
/// assert!(!WillowRange::<u8>::new_closed(4, 9).contains(&12));
/// ```
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
#[repr(C)]
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(ClosedRange<T>),
    /// An [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) with an inclusive start value.
    ///
    /// It includes all values greater than or equal to that start value.
    Open(T),
}

impl<T: Debug> Debug for WillowRange<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match self {
            Self::Closed(closed) => closed.fmt(f),
            Self::Open(start) => {
                start.fmt(f)?;
                write!(f, "..")?;
                Ok(())
            }
        }
    }
}

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

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

#[cfg(feature = "dev")]
impl<'a, T> Arbitrary<'a> for WillowRange<T>
where
    T: Arbitrary<'a> + PartialOrd,
{
    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
        if bool::arbitrary(u)? {
            Ok(Self::Closed(ClosedRange::<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)?,
                ClosedRange::<T>::try_size_hint(depth)?,
            ]),
            size_hint::and(bool::try_size_hint(depth)?, T::try_size_hint(depth)?),
        ))
    }
}

impl<T> WillowRange<T> {
    /// Creates a new open range.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let open = WillowRange::new_open(2);
    ///
    /// assert!(open.is_open());
    /// assert_eq!(open.start(), &2);
    /// ```
    pub fn new_open(start: T) -> Self {
        Self::Open(start)
    }

    /// Returns a reference to the start value of this range.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let closed = WillowRange::new_closed(2, 7);
    /// assert_eq!(closed.start(), &2);
    ///
    /// let open = WillowRange::new_open(2);
    /// assert_eq!(open.start(), &2);
    /// ```
    pub fn start(&self) -> &T {
        match self {
            Self::Closed(inner) => inner.start(),
            Self::Open(start) => start,
        }
    }

    /// Returns a reference to the end value of this range, or `None` of it is open.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let closed = WillowRange::new_closed(2, 7);
    /// assert_eq!(closed.end(), Some(&7));
    ///
    /// let open = WillowRange::new_open(2);
    /// assert_eq!(open.end(), None);
    /// ```
    pub fn end(&self) -> Option<&T> {
        match self {
            Self::Closed(inner) => Some(inner.end()),
            Self::Open(_) => None,
        }
    }

    /// Takes ownership of a willow range and returns its start and end.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let closed = WillowRange::new_closed(2, 7);
    /// assert_eq!(closed.into_parts(), (2, Some(7)));
    ///
    /// let open = WillowRange::new_open(2);
    /// assert_eq!(open.into_parts(), (2, None));
    /// ```
    pub fn into_parts(self) -> (T, Option<T>) {
        match self {
            Self::Closed(inner) => (inner.start, Some(inner.end)),
            Self::Open(start) => (start, None),
        }
    }

    /// 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>::new_closed(3, 8).is_closed(), true);
    /// assert_eq!(WillowRange::<u8>::new_open(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>::new_closed(3, 8).is_open(), false);
    /// assert_eq!(WillowRange::<u8>::new_open(3).is_open(), true);
    /// ```
    pub fn is_open(&self) -> bool {
        matches!(self, Self::Open(_))
    }

    /// Converts this range into a different range by applying a function to all endpoints. Returns an error if the new range would be empty.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(
    ///     WillowRange::<u8>::new_closed(3, 8).try_map(|x| (x + 1) as u16),
    ///     Ok(WillowRange::<u16>::new_closed(4, 9)),
    /// );
    /// ```
    pub fn try_map<U, F>(self, mut f: F) -> Result<WillowRange<U>, EmptyGrouping>
    where
        F: FnMut(T) -> U,
        U: PartialOrd,
    {
        match self {
            Self::Closed(ClosedRange { start, end }) => {
                Ok(WillowRange::Closed(ClosedRange::try_new(f(start), f(end))?))
            }
            Self::Open(start) => Ok(WillowRange::Open(f(start))),
        }
    }

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

    /// Converts this range into a different range by applying a function to all endpoints, without checking if the resulting range would be empty.
    ///
    /// ## Safety
    ///
    /// Undefined behaviour may occur if the resulting range would be empty.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(
    ///     unsafe {
    ///         WillowRange::<u8>::new_closed(3, 8).map_unchecked(|x| (x + 1) as u16)
    ///     },
    ///     WillowRange::<u16>::new_closed(4, 9),
    /// );
    /// ```
    pub unsafe fn map_unchecked<U, F>(self, mut f: F) -> WillowRange<U>
    where
        F: FnMut(T) -> U,
        U: PartialOrd,
    {
        match self {
            Self::Closed(ClosedRange { start, end }) => {
                // SAFETY: the unsafety of this call is exactly why this method is unsafe itself.
                WillowRange::Closed(unsafe { ClosedRange::new_unchecked(f(start), f(end)) })
            }
            Self::Open(start) => WillowRange::Open(f(start)),
        }
    }

    /// 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, and if the resulting range is non-empty.
    pub unsafe fn cast<U>(&self) -> &WillowRange<U> {
        // SAFETY: WillowRange and ClosedRanged are `repr(C)`, so if `T` and `U` have identical
        // layout, then so do `WillowRange<T>` and `WillowRange<U>`
        unsafe { &*(self as *const Self as *const WillowRange<U>) }
    }

    /// Creates a new Willow range, without enforcing non-emptyness.
    ///
    /// #### Safety
    ///
    /// Calling this method with `start >= end` is undefined behaviour.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let yay = unsafe { WillowRange::new_unchecked(2, Some(7)) };
    /// ```
    pub unsafe fn new_unchecked(start: T, end: Option<T>) -> Self {
        match end {
            // SAFETY: the unsafety of this call is exactly why this method is unsafe itself.
            Some(end) => Self::Closed(unsafe { ClosedRange::new_unchecked(start, end) }),
            None => Self::new_open(start),
        }
    }

    /// Creates a new closed Willow range, without enforcing non-emptyness.
    ///
    /// #### Safety
    ///
    /// Calling this method with `start >= end` is undefined behaviour.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let yay = unsafe { WillowRange::new_closed_unchecked(2, 7) };
    /// ```
    pub unsafe fn new_closed_unchecked(start: T, end: T) -> Self {
        // SAFETY: the unsafety of this call is exactly why this method is unsafe itself.
        Self::Closed(unsafe { ClosedRange::new_unchecked(start, end) })
    }
}

impl<T> WillowRange<T>
where
    T: PartialOrd,
{
    /// Creates a new Willow range from a start value and an optional end value, or returns an [`EmptyGrouping`] error if the created range would be empty.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert!(WillowRange::try_new(2, Some(7)).is_ok());
    /// assert!(WillowRange::try_new(7, Some(2)).is_err());
    /// assert!(WillowRange::try_new(2, Some(2)).is_err());
    /// ```
    pub fn try_new(start: T, end: Option<T>) -> Result<Self, EmptyGrouping> {
        let ret = match end {
            Some(end) => Self::Closed(ClosedRange { start, end }),
            None => Self::Open(start),
        };

        if ret.is_empty() {
            Err(EmptyGrouping)
        } else {
            Ok(ret)
        }
    }

    /// Creates a new Willow range from a start value and an optional end value, panicking if the created range would be empty.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let yay = WillowRange::new_closed(2, 7);
    /// ```
    ///
    /// ```should_panic
    /// use willow_data_model::prelude::*;
    ///
    /// let nope = WillowRange::new(7, Some(2));
    /// ```
    pub fn new(start: T, end: Option<T>) -> Self {
        Self::try_new(start, end).unwrap()
    }

    /// Creates a new closed Willow range, or returns an [`EmptyGrouping`] error if the created range would be empty.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert!(WillowRange::try_new_closed(2, 7).is_ok());
    /// assert!(WillowRange::try_new_closed(7, 2).is_err());
    /// assert!(WillowRange::try_new_closed(2, 2).is_err());
    /// ```
    pub fn try_new_closed(start: T, end: T) -> Result<Self, EmptyGrouping> {
        Ok(Self::Closed(ClosedRange::try_new(start, end)?))
    }

    /// Creates a new Willow range from a start value and an optional end value, panicking if the created range would be empty.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let yay = WillowRange::new_closed(2, 7);
    /// ```
    ///
    /// ```should_panic
    /// use willow_data_model::prelude::*;
    ///
    /// let nope = WillowRange::new_closed(7, 2);
    /// ```
    pub fn new_closed(start: T, end: T) -> Self {
        Self::Closed(ClosedRange::new(start, end))
    }

    /// Returns whether the given value is included in `self`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let closed = WillowRange::new_closed(2, 7);
    /// assert!(closed.includes_value(&2));
    /// assert!(!closed.includes_value(&1));
    /// assert!(!closed.includes_value(&7));
    ///
    /// let open = WillowRange::new_open(2);
    /// assert!(open.includes_value(&2));
    /// assert!(!open.includes_value(&1));
    /// assert!(open.includes_value(&7));
    /// ```
    pub fn includes_value(&self, t: &T) -> bool {
        self.start() <= t && self.end().map(|end| end > t).unwrap_or(true)
    }

    /// Returns whether the given value is included in `self` and `other`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r1 = WillowRange::new_closed(2, 7);
    /// let r2 = WillowRange::new_open(5);
    /// assert!(r1.includes_value_in_intersection(&r2, &5));
    /// assert!(!r1.includes_value_in_intersection(&r2, &2));
    /// assert!(!r1.includes_value_in_intersection(&r2, &7));
    /// assert!(!r1.includes_value_in_intersection(&r2, &1));
    /// assert!(!r1.includes_value_in_intersection(&r2, &22));
    /// ```
    pub fn includes_value_in_intersection(&self, other: &Self, t: &T) -> bool {
        self.includes_value(t) && other.includes_value(t)
    }

    /// Returns whether the given Willow range is included in `self`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r = WillowRange::new_closed(2, 7);
    /// assert!(r.includes_willow_range(&WillowRange::new_closed(2, 7)));
    /// assert!(!r.includes_willow_range(&WillowRange::new_closed(1, 7)));
    /// assert!(!r.includes_willow_range(&WillowRange::new_closed(2, 8)));
    /// assert!(!r.includes_willow_range(&WillowRange::new_closed(9, 14)));
    /// assert!(!r.includes_willow_range(&WillowRange::new_open(2)));
    /// ```
    pub fn includes_willow_range(&self, other: &Self) -> bool {
        self.start() <= other.start()
            && match (self.end(), other.end()) {
                (None, None) => true,
                (Some(_), None) => false,
                (None, Some(_)) => true,
                (Some(self_end), Some(other_end)) => self_end >= other_end,
            }
    }

    /// Returns whether the given Willow range is strictly included in `self`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let r = WillowRange::new_closed(2, 7);
    /// assert!(r.strictly_includes_willow_range(&WillowRange::new_closed(2, 6)));
    /// assert!(r.strictly_includes_willow_range(&WillowRange::new_closed(3, 7)));
    /// assert!(r.strictly_includes_willow_range(&WillowRange::new_closed(3, 6)));
    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_closed(2, 7)));
    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_closed(1, 7)));
    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_closed(2, 8)));
    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_closed(9, 14)));
    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_open(2)));
    /// ```
    pub fn strictly_includes_willow_range(&self, other: &Self) -> bool {
        self != other && self.includes_willow_range(other)
    }

    /// Only use this internally to check whether the non-emptyness invariant would be upheld by something. Not a public method because we *never publicly expose empty ranges.
    fn is_empty(&self) -> bool {
        match self {
            WillowRange::Closed(inner) => inner.is_empty(),
            WillowRange::Open(_) => false,
        }
    }
}

impl<T> WillowRange<T>
where
    T: PartialOrd + Clone,
{
    /// Returns the intersection between `self` and `other`, or an [`EmptyGrouping`] error if it would be empty.
    ///
    /// assert_eq!(
    ///     WillowRange::new(2, 7).intersection_willow_range(WillowRange::new(5, 9)),
    ///     Ok(WillowRange::new(5, 7)),
    /// );
    /// assert!(
    ///     WillowRange::new(2, 5).intersection_willow_range(WillowRange::new(7, 9)).is_error(),
    /// );
    pub fn intersection_willow_range(&self, other: &Self) -> Result<Self, EmptyGrouping> {
        let start = match self.start().partial_cmp(other.start()) {
            None => return Err(EmptyGrouping),
            Some(Ordering::Less) => other.start().clone(),
            Some(_) => self.start().clone(),
        };

        let end = match (self.end(), other.end()) {
            (None, None) => None,
            (Some(start), None) | (None, Some(start)) => Some(start.clone()),
            (Some(self_end), Some(other_end)) => match self_end.partial_cmp(other_end) {
                None => return Err(EmptyGrouping),
                Some(Ordering::Greater) => Some(other_end.clone()),
                _ => Some(self_end.clone()),
            },
        };

        Self::try_new(start, end)
    }
}

/// A range is less than another iff all values contained in the first are also contained in the other.
impl<T> PartialOrd for WillowRange<T>
where
    T: PartialOrd,
{
    fn partial_cmp(&self, other: &WillowRange<T>) -> Option<Ordering> {
        match (self, other) {
            (Self::Closed(self_closed), Self::Closed(other_closed)) => {
                self_closed.partial_cmp(other_closed)
            }
            (Self::Closed(self_closed), Self::Open(other_open)) => {
                match self_closed.start().partial_cmp(other_open)? {
                    Ordering::Less => None,
                    Ordering::Equal | Ordering::Greater => Some(Ordering::Less),
                }
            }
            (Self::Open(self_open), Self::Closed(other_closed)) => {
                match self_open.partial_cmp(other_closed.start())? {
                    Ordering::Greater => None,
                    Ordering::Equal | Ordering::Less => Some(Ordering::Greater),
                }
            }
            (Self::Open(self_open), Self::Open(other_open)) => {
                match self_open.partial_cmp(other_open)? {
                    Ordering::Less => Some(Ordering::Greater),
                    Ordering::Equal => Some(Ordering::Equal),
                    Ordering::Greater => Some(Ordering::Less),
                }
            }
        }
    }
}

impl<T> WillowRange<T>
where
    T: SuccessorExceptForGreatest,
{
    /// Returns the [`WillowRange`] which [includes](core::ops::RangeBounds::contains) `t` but no other value.
    ///
    /// Panicks if `T::try_successor` returns a valid which is not greater than `t`.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert_eq!(WillowRange::<u8>::singleton(5), WillowRange::<u8>::new_closed(5, 6));
    /// assert_eq!(WillowRange::<u8>::singleton(255), WillowRange::<u8>::new_open(255));
    /// ```
    pub fn singleton(t: T) -> Self {
        match t.try_successor() {
            Some(succ) => Self::Closed(ClosedRange::new(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(), WillowRange::<u8>::new_open(0));
    /// ```
    pub fn full() -> Self {
        Self::Open(T::least())
    }

    /// 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>::new_open(1).is_full(), false);
    /// ```
    pub fn is_full(&self) -> bool {
        match self {
            Self::Closed(_) => false,
            Self::Open(start) => start.is_least(),
        }
    }
}

impl<T> GreatestElement for WillowRange<T>
where
    T: LeastElement,
{
    fn greatest() -> Self {
        Self::Open(T::least())
    }
}