relmath/core/

binary.rs

use std::collections::BTreeSet;

use crate::{UnaryRelation, traits::FiniteRelation};

/// A finite binary relation.
///
/// The starter implementation stores pairs in a `BTreeSet` so iteration order
/// is deterministic.
///
/// Composition direction is:
///
/// `r.compose(&s)` = `{ (a, c) | exists b. (a, b) in r and (b, c) in s }`
///
/// # Examples
///
/// ```rust
/// use relmath::{BinaryRelation, UnaryRelation};
///
/// let user_role = BinaryRelation::from_pairs([
///     ("ann", "admin"),
///     ("bob", "reviewer"),
/// ]);
///
/// let extra_role = BinaryRelation::from_pairs([
///     ("bob", "reviewer"),
///     ("cara", "guest"),
/// ]);
///
/// let role_permission = BinaryRelation::from_pairs([
///     ("admin", "read"),
///     ("reviewer", "approve"),
///     ("guest", "view"),
/// ]);
///
/// assert_eq!(
///     user_role.union(&extra_role).to_vec(),
///     vec![("ann", "admin"), ("bob", "reviewer"), ("cara", "guest")]
/// );
/// assert_eq!(
///     user_role.intersection(&extra_role).to_vec(),
///     vec![("bob", "reviewer")]
/// );
/// assert_eq!(user_role.difference(&extra_role).to_vec(), vec![("ann", "admin")]);
/// assert_eq!(
///     user_role.converse().to_vec(),
///     vec![("admin", "ann"), ("reviewer", "bob")]
/// );
///
/// let effective_permission = user_role.union(&extra_role).compose(&role_permission);
/// assert!(effective_permission.contains(&"ann", &"read"));
/// assert_eq!(
///     effective_permission.iter().copied().collect::<Vec<_>>(),
///     vec![("ann", "read"), ("bob", "approve"), ("cara", "view")]
/// );
/// assert_eq!(
///     effective_permission.domain().to_vec(),
///     vec!["ann", "bob", "cara"]
/// );
/// assert_eq!(
///     effective_permission.range().to_vec(),
///     vec!["approve", "read", "view"]
/// );
/// assert_eq!(
///     effective_permission
///         .restrict_domain(&UnaryRelation::from_values(["ann", "cara"]))
///         .to_vec(),
///     vec![("ann", "read"), ("cara", "view")]
/// );
/// assert_eq!(
///     effective_permission
///         .restrict_range(&UnaryRelation::from_values(["read", "view"]))
///         .to_vec(),
///     vec![("ann", "read"), ("cara", "view")]
/// );
/// assert_eq!(
///     effective_permission.image(&UnaryRelation::singleton("bob")).to_vec(),
///     vec!["approve"]
/// );
/// assert_eq!(
///     effective_permission
///         .preimage(&UnaryRelation::from_values(["read", "view"]))
///         .to_vec(),
///     vec!["ann", "cara"]
/// );
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct BinaryRelation<A: Ord, B: Ord> {
    pairs: BTreeSet<(A, B)>,
}

impl<A: Ord, B: Ord> BinaryRelation<A, B> {
    /// Creates an empty binary relation.
    #[must_use]
    pub fn new() -> Self {
        Self {
            pairs: BTreeSet::new(),
        }
    }

    /// Creates a binary relation from the provided pairs.
    #[must_use]
    pub fn from_pairs<I>(pairs: I) -> Self
    where
        I: IntoIterator<Item = (A, B)>,
    {
        pairs.into_iter().collect()
    }

    /// Inserts a pair into the relation.
    ///
    /// Returns `true` when the pair was not already present.
    pub fn insert(&mut self, left: A, right: B) -> bool {
        self.pairs.insert((left, right))
    }

    /// Returns `true` when the relation contains the given pair.
    #[must_use]
    pub fn contains(&self, left: &A, right: &B) -> bool {
        self.pairs.iter().any(|(candidate_left, candidate_right)| {
            candidate_left == left && candidate_right == right
        })
    }

    /// Returns an iterator over the stored pairs in deterministic order.
    pub fn iter(&self) -> impl Iterator<Item = &(A, B)> {
        self.pairs.iter()
    }

    /// Returns the domain of the relation.
    #[must_use]
    pub fn domain(&self) -> UnaryRelation<A>
    where
        A: Clone,
    {
        self.pairs.iter().map(|(left, _)| left.clone()).collect()
    }

    /// Returns the range of the relation.
    #[must_use]
    pub fn range(&self) -> UnaryRelation<B>
    where
        B: Clone,
    {
        self.pairs.iter().map(|(_, right)| right.clone()).collect()
    }

    /// Returns the converse relation.
    #[must_use]
    pub fn converse(&self) -> BinaryRelation<B, A>
    where
        A: Clone,
        B: Clone,
    {
        self.pairs
            .iter()
            .map(|(left, right)| (right.clone(), left.clone()))
            .collect()
    }

    /// Returns the union of `self` and `other`.
    #[must_use]
    pub fn union(&self, other: &Self) -> Self
    where
        A: Clone,
        B: Clone,
    {
        self.pairs.union(&other.pairs).cloned().collect()
    }

    /// Returns the intersection of `self` and `other`.
    #[must_use]
    pub fn intersection(&self, other: &Self) -> Self
    where
        A: Clone,
        B: Clone,
    {
        self.pairs.intersection(&other.pairs).cloned().collect()
    }

    /// Returns the set difference `self \ other`.
    #[must_use]
    pub fn difference(&self, other: &Self) -> Self
    where
        A: Clone,
        B: Clone,
    {
        self.pairs.difference(&other.pairs).cloned().collect()
    }

    /// Restricts the domain of the relation to `allowed`.
    #[must_use]
    pub fn restrict_domain(&self, allowed: &UnaryRelation<A>) -> Self
    where
        A: Clone,
        B: Clone,
    {
        self.pairs
            .iter()
            .filter(|(left, _)| allowed.contains(left))
            .cloned()
            .collect()
    }

    /// Restricts the range of the relation to `allowed`.
    #[must_use]
    pub fn restrict_range(&self, allowed: &UnaryRelation<B>) -> Self
    where
        A: Clone,
        B: Clone,
    {
        self.pairs
            .iter()
            .filter(|(_, right)| allowed.contains(right))
            .cloned()
            .collect()
    }

    /// Computes the image of `sources` through the relation.
    ///
    /// Returns `{ b | exists a in sources. (a, b) in self }`.
    #[must_use]
    pub fn image(&self, sources: &UnaryRelation<A>) -> UnaryRelation<B>
    where
        B: Clone,
    {
        self.pairs
            .iter()
            .filter(|(left, _)| sources.contains(left))
            .map(|(_, right)| right.clone())
            .collect()
    }

    /// Computes the preimage of `targets` through the relation.
    ///
    /// Returns `{ a | exists b in targets. (a, b) in self }`.
    #[must_use]
    pub fn preimage(&self, targets: &UnaryRelation<B>) -> UnaryRelation<A>
    where
        A: Clone,
    {
        self.pairs
            .iter()
            .filter(|(_, right)| targets.contains(right))
            .map(|(left, _)| left.clone())
            .collect()
    }

    /// Composes `self` with `rhs`.
    ///
    /// The result contains `(a, c)` whenever there exists `b` such that
    /// `(a, b)` is in `self` and `(b, c)` is in `rhs`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::BinaryRelation;
    ///
    /// let user_role = BinaryRelation::from_pairs([
    ///     ("ann", "admin"),
    ///     ("bob", "reviewer"),
    /// ]);
    /// let role_permission = BinaryRelation::from_pairs([
    ///     ("admin", "read"),
    ///     ("reviewer", "approve"),
    /// ]);
    ///
    /// let effective_permission = user_role.compose(&role_permission);
    ///
    /// assert_eq!(
    ///     effective_permission.to_vec(),
    ///     vec![("ann", "read"), ("bob", "approve")]
    /// );
    /// ```
    #[must_use]
    pub fn compose<C>(&self, rhs: &BinaryRelation<B, C>) -> BinaryRelation<A, C>
    where
        A: Clone,
        B: Clone,
        C: Clone + Ord,
    {
        let mut result = BTreeSet::new();

        for (left, middle_left) in &self.pairs {
            for (middle_right, right) in &rhs.pairs {
                if middle_left == middle_right {
                    result.insert((left.clone(), right.clone()));
                }
            }
        }

        BinaryRelation { pairs: result }
    }

    /// Converts the relation into a sorted vector of pairs.
    #[must_use]
    pub fn to_vec(&self) -> Vec<(A, B)>
    where
        A: Clone,
        B: Clone,
    {
        self.pairs.iter().cloned().collect()
    }
}

impl<A: Ord, B: Ord> Default for BinaryRelation<A, B> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Ord> BinaryRelation<T, T> {
    /// Returns the carrier induced by the relation: domain union range.
    #[must_use]
    pub fn carrier(&self) -> UnaryRelation<T>
    where
        T: Clone,
    {
        self.domain().union(&self.range())
    }

    /// Returns the identity relation on `carrier`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::{BinaryRelation, UnaryRelation};
    ///
    /// let carrier = UnaryRelation::from_values(["Draft", "Review"]);
    ///
    /// assert_eq!(
    ///     BinaryRelation::identity(&carrier).to_vec(),
    ///     vec![("Draft", "Draft"), ("Review", "Review")]
    /// );
    /// ```
    #[must_use]
    pub fn identity(carrier: &UnaryRelation<T>) -> Self
    where
        T: Clone,
    {
        carrier
            .iter()
            .map(|value| (value.clone(), value.clone()))
            .collect()
    }

    /// Computes the transitive closure of the relation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::BinaryRelation;
    ///
    /// let step = BinaryRelation::from_pairs([
    ///     ("Draft", "Review"),
    ///     ("Review", "Approved"),
    /// ]);
    ///
    /// assert_eq!(
    ///     step.transitive_closure().to_vec(),
    ///     vec![
    ///         ("Draft", "Approved"),
    ///         ("Draft", "Review"),
    ///         ("Review", "Approved"),
    ///     ]
    /// );
    /// ```
    #[must_use]
    pub fn transitive_closure(&self) -> Self
    where
        T: Clone,
    {
        let mut closure = self.clone();
        let mut changed = true;

        while changed {
            changed = false;
            let snapshot = closure.to_vec();

            for (left, middle_left) in &snapshot {
                for (middle_right, right) in &snapshot {
                    if middle_left == middle_right
                        && closure.pairs.insert((left.clone(), right.clone()))
                    {
                        changed = true;
                    }
                }
            }
        }

        closure
    }

    /// Computes the reflexive-transitive closure on the given `carrier`.
    ///
    /// Values that appear in `carrier` but not in any pair still gain their
    /// identity edge in the result.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::{BinaryRelation, UnaryRelation};
    ///
    /// let step = BinaryRelation::from_pairs([("Draft", "Review")]);
    /// let states = UnaryRelation::from_values(["Draft", "Review", "Archived"]);
    /// let reachable = step.reflexive_transitive_closure(&states);
    ///
    /// assert!(reachable.contains(&"Archived", &"Archived"));
    /// assert!(reachable.contains(&"Draft", &"Review"));
    /// ```
    #[must_use]
    pub fn reflexive_transitive_closure(&self, carrier: &UnaryRelation<T>) -> Self
    where
        T: Clone,
    {
        self.transitive_closure().union(&Self::identity(carrier))
    }

    /// Returns `true` when the relation is reflexive on `carrier`.
    #[must_use]
    pub fn is_reflexive(&self, carrier: &UnaryRelation<T>) -> bool {
        carrier.iter().all(|value| self.contains(value, value))
    }

    /// Returns `true` when the relation is irreflexive on `carrier`.
    #[must_use]
    pub fn is_irreflexive(&self, carrier: &UnaryRelation<T>) -> bool {
        carrier.iter().all(|value| !self.contains(value, value))
    }

    /// Returns `true` when the relation is symmetric.
    #[must_use]
    pub fn is_symmetric(&self) -> bool {
        self.pairs
            .iter()
            .all(|(left, right)| self.contains(right, left))
    }

    /// Returns `true` when the relation is antisymmetric.
    #[must_use]
    pub fn is_antisymmetric(&self) -> bool {
        self.pairs
            .iter()
            .all(|(left, right)| left == right || !self.contains(right, left))
    }

    /// Returns `true` when the relation is transitive.
    #[must_use]
    pub fn is_transitive(&self) -> bool
    where
        T: Clone,
    {
        let snapshot = self.to_vec();

        snapshot.iter().all(|(left, middle_left)| {
            snapshot.iter().all(|(middle_right, right)| {
                middle_left != middle_right || self.contains(left, right)
            })
        })
    }

    /// Returns `true` when the relation is an equivalence relation on `carrier`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::{BinaryRelation, UnaryRelation};
    ///
    /// let aliases = BinaryRelation::from_pairs([
    ///     ("A. Smith", "A. Smith"),
    ///     ("A. Smith", "Alice Smith"),
    ///     ("Alice Smith", "A. Smith"),
    ///     ("Alice Smith", "Alice Smith"),
    /// ]);
    /// let carrier = UnaryRelation::from_values(["A. Smith", "Alice Smith"]);
    ///
    /// assert!(aliases.is_equivalence(&carrier));
    /// ```
    #[must_use]
    pub fn is_equivalence(&self, carrier: &UnaryRelation<T>) -> bool
    where
        T: Clone,
    {
        self.is_reflexive(carrier) && self.is_symmetric() && self.is_transitive()
    }

    /// Returns `true` when the relation is a partial order on `carrier`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use relmath::{BinaryRelation, UnaryRelation};
    ///
    /// let divides = BinaryRelation::from_pairs([
    ///     (1_u8, 1_u8),
    ///     (1, 2),
    ///     (1, 4),
    ///     (2, 2),
    ///     (2, 4),
    ///     (4, 4),
    /// ]);
    /// let carrier = UnaryRelation::from_values([1_u8, 2_u8, 4_u8]);
    ///
    /// assert!(divides.is_partial_order(&carrier));
    /// ```
    #[must_use]
    pub fn is_partial_order(&self, carrier: &UnaryRelation<T>) -> bool
    where
        T: Clone,
    {
        self.is_reflexive(carrier) && self.is_antisymmetric() && self.is_transitive()
    }
}

impl<A: Ord, B: Ord> FiniteRelation for BinaryRelation<A, B> {
    fn len(&self) -> usize {
        self.pairs.len()
    }
}

impl<A: Ord, B: Ord> FromIterator<(A, B)> for BinaryRelation<A, B> {
    fn from_iter<I: IntoIterator<Item = (A, B)>>(iter: I) -> Self {
        Self {
            pairs: iter.into_iter().collect(),
        }
    }
}

impl<A: Ord, B: Ord> Extend<(A, B)> for BinaryRelation<A, B> {
    fn extend<I: IntoIterator<Item = (A, B)>>(&mut self, iter: I) {
        self.pairs.extend(iter);
    }
}

impl<A: Ord, B: Ord> IntoIterator for BinaryRelation<A, B> {
    type Item = (A, B);
    type IntoIter = std::collections::btree_set::IntoIter<(A, B)>;

    fn into_iter(self) -> Self::IntoIter {
        self.pairs.into_iter()
    }
}

impl<'a, A: Ord, B: Ord> IntoIterator for &'a BinaryRelation<A, B> {
    type Item = &'a (A, B);
    type IntoIter = std::collections::btree_set::Iter<'a, (A, B)>;

    fn into_iter(self) -> Self::IntoIter {
        self.pairs.iter()
    }
}