relmath-rs 0.5.0

use std::collections::BTreeSet;

use crate::traits::FiniteRelation;

/// A finite unary relation.
///
/// In G1 this is also the canonical set type used to define carriers, domains,
/// ranges, and images of binary relations.
///
/// The starter implementation uses `BTreeSet` so iteration order is
/// deterministic.
///
/// # Examples
///
/// ```rust
/// use relmath::{FiniteRelation, UnaryRelation};
///
/// let mut xs = UnaryRelation::new();
/// assert!(xs.is_empty());
///
/// xs.insert(3);
/// xs.insert(1);
/// xs.insert(2);
/// xs.insert(2);
///
/// let ys = UnaryRelation::singleton(3);
/// let zs = UnaryRelation::from_values([2, 3, 4]);
///
/// assert!(xs.contains(&1));
/// assert_eq!(xs.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
/// assert_eq!(xs.union(&ys).to_vec(), vec![1, 2, 3]);
/// assert_eq!(xs.intersection(&zs).to_vec(), vec![2, 3]);
/// assert_eq!(xs.difference(&zs).to_vec(), vec![1]);
/// assert!(ys.is_subset(&xs));
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct UnaryRelation<T: Ord> {
    values: BTreeSet<T>,
}

impl<T: Ord> UnaryRelation<T> {
    /// Creates an empty unary relation.
    #[must_use]
    pub fn new() -> Self {
        Self {
            values: BTreeSet::new(),
        }
    }

    /// Creates a unary relation from the provided values.
    ///
    /// Duplicate values are coalesced into a single stored element.
    #[must_use]
    pub fn from_values<I>(values: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        values.into_iter().collect()
    }

    /// Creates a unary relation containing exactly one value.
    #[must_use]
    pub fn singleton(value: T) -> Self {
        let mut values = BTreeSet::new();
        values.insert(value);
        Self { values }
    }

    /// Inserts a value into the unary relation.
    ///
    /// Returns `true` when the value was not already present.
    pub fn insert(&mut self, value: T) -> bool {
        self.values.insert(value)
    }

    /// Returns `true` when the unary relation contains the given value.
    #[must_use]
    pub fn contains(&self, value: &T) -> bool {
        self.values.contains(value)
    }

    /// Returns an iterator over the values in deterministic order.
    ///
    /// Iteration order follows `T: Ord`.
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.values.iter()
    }

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

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

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

    /// Returns `true` when every element of `self` also appears in `other`.
    #[must_use]
    pub fn is_subset(&self, other: &Self) -> bool {
        self.values.is_subset(&other.values)
    }

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

impl<T: Ord> Default for UnaryRelation<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Ord> FiniteRelation for UnaryRelation<T> {
    fn len(&self) -> usize {
        self.values.len()
    }
}

impl<T: Ord> FromIterator<T> for UnaryRelation<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        Self {
            values: iter.into_iter().collect(),
        }
    }
}

impl<T: Ord> Extend<T> for UnaryRelation<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        self.values.extend(iter);
    }
}

impl<T: Ord> IntoIterator for UnaryRelation<T> {
    type Item = T;
    type IntoIter = std::collections::btree_set::IntoIter<T>;

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

impl<'a, T: Ord> IntoIterator for &'a UnaryRelation<T> {
    type Item = &'a T;
    type IntoIter = std::collections::btree_set::Iter<'a, T>;

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