willow-data-model 0.4.1

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

#[cfg(feature = "dev")]
use arbitrary::Arbitrary;

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

use crate::prelude::*;

/// An [`Area`](https://willowprotocol.org/specs/grouping-entries/#Area) is a box in three-dimensional willow space, consisting of all entries matching either a single subspace id or entries of arbitrary subspace ids, prefixed by some [`Path`], and a [`TimeRange`](super::TimeRange).
///
/// Areas are the default way by which application developers should aggregate entries. See [the specification](https://willowprotocol.org/specs/grouping-entries/#areas) for more details.
///
/// ```
/// use willow_data_model::prelude::*;
///
/// let a1 = Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17));
///
/// assert!(a1.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
/// assert_eq!(a1.subspace(), None);
///
/// let a2 = Area::<2, 2, 2, u8>::new(Some(42), Path::new(), Timestamp::from(15)..);
/// assert_eq!(
///     a1.wdm_intersection(&a2),
///     Area::<2, 2, 2, u8>::new(
///         Some(42),
///         Path::new(),
///         Timestamp::from(15)..Timestamp::from(17),
///     ),
/// );
/// ```
///
/// [Specification](https://willowprotocol.org/specs/grouping-entries/#Area)
#[derive(Clone, Debug)]
#[cfg_attr(feature = "dev", derive(Arbitrary))]
pub struct Area<const MCL: usize, const MCC: usize, const MPL: usize, S> {
    subspace: Option<S>,
    path: Path<MCL, MCC, MPL>,
    times: TimeRange,
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S> {
    /// Creates a new `Area` from its constituent optional subspace id, [`Path`], and [`TimeRange`](super::TimeRange).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let a = Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17));
    ///
    /// assert!(a.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
    /// assert_eq!(a.subspace(), None);
    /// ```
    pub fn new<TR>(subspace: Option<S>, path: Path<MCL, MCC, MPL>, times: TR) -> Self
    where
        TR: Into<TimeRange>,
    {
        Self {
            subspace,
            path,
            times: times.into(),
        }
    }

    /// Returns a reference to the inner subspace id, if any.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let a1 = Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17));
    /// assert_eq!(a1.subspace(), Some(&17));
    ///
    /// let a2 = Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17));
    /// assert_eq!(a2.subspace(), None);
    /// ```
    ///
    /// [Definition](https://willowprotocol.org/specs/grouping-entries/#AreaSubspace).
    pub fn subspace(&self) -> Option<&S> {
        self.subspace.as_ref()
    }

    /// Returns a reference to the inner [`Path`].
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let a = Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17));
    /// assert_eq!(a.path(), &Path::new());
    /// ```
    ///
    /// [Definition](https://willowprotocol.org/specs/grouping-entries/#AreaPath).
    pub fn path(&self) -> &Path<MCL, MCC, MPL> {
        &self.path
    }

    /// Returns a reference to the inner [`TimeRange`](super::TimeRange).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let a = Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17));
    /// assert_eq!(a.times(), &WillowRange::from(..Timestamp::from(17)));
    /// ```
    ///
    /// [Definition](https://willowprotocol.org/specs/grouping-entries/#AreaTime).
    pub fn times(&self) -> &TimeRange {
        &self.times
    }

    /// Sets the inner subspace id.
    pub fn set_subspace(&mut self, new_subspace: Option<S>) {
        self.subspace = new_subspace;
    }

    /// Sets the inner [`Path`].
    pub fn set_path(&mut self, new_path: Path<MCL, MCC, MPL>) {
        self.path = new_path;
    }

    /// Sets the inner [`TimeRange`].
    pub fn set_times<TR>(&mut self, new_range: TR)
    where
        TR: Into<TimeRange>,
    {
        self.times = new_range.into();
    }

    /// Returns the [subspace area](https://willowprotocol.org/specs/grouping-entries/#subspace_area) for the given subspace id, i.e., the area which includes exactly the entries of the given subspace id.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let a = Area::<2, 2, 2, u8>::new_subspace(17);
    ///
    /// assert!(a.wdm_includes(&(17, Path::new(), Timestamp::from(9))));
    /// assert!(!a.wdm_includes(&(18, Path::new(), Timestamp::from(9))));
    /// assert_eq!(a.subspace(), Some(&17));
    /// ```
    pub fn new_subspace(subspace_id: S) -> Self {
        Self::new(Some(subspace_id), Path::new(), ..)
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Grouping<MCL, MCC, MPL, S>
    for Area<MCL, MCC, MPL, S>
where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn wdm_includes<Coord>(&self, coord: &Coord) -> bool
    where
        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized,
    {
        self.times().contains(&coord.wdm_timestamp())
            && self
                .subspace()
                .map(|subspace_id| subspace_id == coord.wdm_subspace_id())
                .unwrap_or(true)
            && coord.wdm_path().is_prefixed_by(self.path())
    }
}

/// An area is equal to another iff both include exactly the same values.
///
/// This implementation assumes that `S` is inhabited by more than one value.
impl<const MCL: usize, const MCC: usize, const MPL: usize, S> PartialEq<Self>
    for Area<MCL, MCC, MPL, S>
where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn eq(&self, other: &Self) -> bool {
        match (self.wdm_is_empty(), other.wdm_is_empty()) {
            (true, true) => true,
            (true, false) | (false, true) => false,
            (false, false) => {
                self.subspace() == other.subspace()
                    && self.path() == other.path()
                    && self.times() == other.times()
            }
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Eq for Area<MCL, MCC, MPL, S> where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest
{
}

/// An area is less than another iff all values included in the first are also included in the other.
///
/// This implementation assumes that `S` is inhabited by more than one value.
impl<const MCL: usize, const MCC: usize, const MPL: usize, S> PartialOrd<Self>
    for Area<MCL, MCC, MPL, S>
where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    /// An area is less than another iff all values included in the first are also included in the other.
    ///
    /// This implementation assumes that `S` is inhabited by more than one value.
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        match (self.wdm_is_empty(), other.wdm_is_empty()) {
            (true, true) => Some(Ordering::Equal),
            (true, false) => Some(Ordering::Less),
            (false, true) => Some(Ordering::Greater),
            (false, false) => {
                match (
                    cmp_subspace(self.subspace(), other.subspace())?,
                    other.path().prefix_cmp(self.path())?,
                    self.times().partial_cmp(other.times())?,
                ) {
                    (Ordering::Equal, Ordering::Equal, Ordering::Equal) => Some(Ordering::Equal),
                    (subspaces_cmp, paths_cmp, times_cmp) => {
                        if subspaces_cmp.is_le() && paths_cmp.is_le() && times_cmp.is_le() {
                            Some(Ordering::Less)
                        } else if subspaces_cmp.is_ge() && paths_cmp.is_ge() && times_cmp.is_ge() {
                            Some(Ordering::Greater)
                        } else {
                            None
                        }
                    }
                }
            }
        }
    }
}

fn cmp_subspace<S: PartialEq>(s1: Option<&S>, s2: Option<&S>) -> Option<Ordering> {
    match (s1, s2) {
        (None, None) => Some(Ordering::Equal),
        (Some(_), None) => Some(Ordering::Less),
        (None, Some(_)) => Some(Ordering::Greater),
        (Some(s1), Some(s2)) => {
            if s1 == s2 {
                Some(Ordering::Equal)
            } else {
                None
            }
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> LeastElement
    for Area<MCL, MCC, MPL, S>
where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn least() -> Self {
        Self::new(None, Path::new(), TimeRange::least())
    }

    fn is_least(&self) -> bool {
        self.times().is_empty()
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> GreatestElement
    for Area<MCL, MCC, MPL, S>
where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn greatest() -> Self {
        Self::new(None, Path::new(), TimeRange::full())
    }

    fn is_greatest(&self) -> bool {
        self.subspace().is_none() && self.times().is_full() && self.path().is_empty()
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> LowerSemilattice
    for Area<MCL, MCC, MPL, S>
where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn greatest_lower_bound(&self, other: &Self) -> Self {
        let subspace = match (self.subspace(), other.subspace()) {
            (None, None) => None,
            (Some(s), None) | (None, Some(s)) => Some(s.clone()),
            (Some(s1), Some(s2)) => {
                if s1 == s2 {
                    Some(s1.clone())
                } else {
                    return Self::least();
                }
            }
        };

        let path = match self.path().prefix_cmp(other.path()) {
            Some(Ordering::Greater) | Some(Ordering::Equal) => self.path().clone(),
            Some(Ordering::Less) => other.path().clone(),
            None => return Self::least(),
        };

        Self::new(
            subspace,
            path,
            self.times().greatest_lower_bound(other.times()),
        )
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> UpperSemilattice
    for Area<MCL, MCC, MPL, S>
where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    fn least_upper_bound(&self, other: &Self) -> Self {
        if self.wdm_is_empty() {
            other.clone()
        } else if other.wdm_is_empty() {
            self.clone()
        } else {
            let subspace = match (self.subspace(), other.subspace()) {
                (None, None) => None,
                (Some(_), None) | (None, Some(_)) => None,
                (Some(s1), Some(s2)) => {
                    if s1 == s2 {
                        Some(s1.clone())
                    } else {
                        None
                    }
                }
            };

            let path = self.path().longest_common_prefix(other.path());

            Self::new(
                subspace,
                path,
                self.times().least_upper_bound(other.times()),
            )
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S>
where
    S: Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    /// Returns whether an [`Entry`] of the given [coordinate](Coordinatelike) could possibly cause [prefix pruning](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) in this area.
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let a = Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17));
    ///
    /// assert!(a.admits_pruning_by(&(17, Path::new(), Timestamp::from(9))));
    /// assert!(!a.admits_pruning_by(&(18, Path::new(), Timestamp::from(9))));
    /// ```
    pub fn admits_pruning_by<Coord>(&self, coord: &Coord) -> bool
    where
        Coord: Coordinatelike<MCL, MCC, MPL, S>,
    {
        if let Some(s) = self.subspace() {
            if s != coord.wdm_subspace_id() {
                return false;
            }
        }

        if coord.wdm_timestamp() < *self.times().start() {
            return false;
        }

        coord.wdm_path().is_related_to(self.path())
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S>
where
    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
{
    /// Returns the [`Area`] which [includes](Grouping::wdm_includes) every [coordinate](Coordinatelike).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let a = Area::<2, 2, 2, u8>::full();
    ///
    /// assert!(a.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
    /// assert!(a.wdm_includes(&(16, Path::new(), Timestamp::from(9))));
    /// ```
    pub fn full() -> Self {
        Self::greatest()
    }

    /// Returns whether `self` is the full area, i.e., the area which [includes](Grouping::wdm_includes) every [coordinate](Coordinatelike).
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// assert!(Area::<2, 2, 2, u8>::full().is_full());
    /// assert!(!Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17)).is_full());
    /// ```
    pub fn is_full(&self) -> bool {
        self.is_greatest()
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Hash for Area<MCL, MCC, MPL, S>
where
    S: Hash + Clone + 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 {
            253u8.hash(state);
            self.subspace.hash(state);
            self.path.hash(state);
            self.times.hash(state);
        }
    }
}