relmath/core/
unary.rs

1use std::collections::BTreeSet;
2
3use crate::traits::FiniteRelation;
4
5/// A finite unary relation.
6///
7/// In G1 this is also the canonical set type used to define carriers, domains,
8/// ranges, and images of binary relations.
9///
10/// The starter implementation uses `BTreeSet` so iteration order is
11/// deterministic.
12///
13/// # Examples
14///
15/// ```rust
16/// use relmath::{FiniteRelation, UnaryRelation};
17///
18/// let mut xs = UnaryRelation::new();
19/// assert!(xs.is_empty());
20///
21/// xs.insert(3);
22/// xs.insert(1);
23/// xs.insert(2);
24/// xs.insert(2);
25///
26/// let ys = UnaryRelation::singleton(3);
27/// let zs = UnaryRelation::from_values([2, 3, 4]);
28///
29/// assert!(xs.contains(&1));
30/// assert_eq!(xs.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
31/// assert_eq!(xs.union(&ys).to_vec(), vec![1, 2, 3]);
32/// assert_eq!(xs.intersection(&zs).to_vec(), vec![2, 3]);
33/// assert_eq!(xs.difference(&zs).to_vec(), vec![1]);
34/// assert!(ys.is_subset(&xs));
35/// ```
36#[derive(Clone, Debug, PartialEq, Eq)]
37pub struct UnaryRelation<T: Ord> {
38    values: BTreeSet<T>,
39}
40
41impl<T: Ord> UnaryRelation<T> {
42    /// Creates an empty unary relation.
43    #[must_use]
44    pub fn new() -> Self {
45        Self {
46            values: BTreeSet::new(),
47        }
48    }
49
50    /// Creates a unary relation from the provided values.
51    ///
52    /// Duplicate values are coalesced into a single stored element.
53    #[must_use]
54    pub fn from_values<I>(values: I) -> Self
55    where
56        I: IntoIterator<Item = T>,
57    {
58        values.into_iter().collect()
59    }
60
61    /// Creates a unary relation containing exactly one value.
62    #[must_use]
63    pub fn singleton(value: T) -> Self {
64        let mut values = BTreeSet::new();
65        values.insert(value);
66        Self { values }
67    }
68
69    /// Inserts a value into the unary relation.
70    ///
71    /// Returns `true` when the value was not already present.
72    pub fn insert(&mut self, value: T) -> bool {
73        self.values.insert(value)
74    }
75
76    /// Returns `true` when the unary relation contains the given value.
77    #[must_use]
78    pub fn contains(&self, value: &T) -> bool {
79        self.values.contains(value)
80    }
81
82    /// Returns an iterator over the values in deterministic order.
83    ///
84    /// Iteration order follows `T: Ord`.
85    pub fn iter(&self) -> impl Iterator<Item = &T> {
86        self.values.iter()
87    }
88
89    /// Returns the union of `self` and `other`.
90    #[must_use]
91    pub fn union(&self, other: &Self) -> Self
92    where
93        T: Clone,
94    {
95        self.values.union(&other.values).cloned().collect()
96    }
97
98    /// Returns the intersection of `self` and `other`.
99    #[must_use]
100    pub fn intersection(&self, other: &Self) -> Self
101    where
102        T: Clone,
103    {
104        self.values.intersection(&other.values).cloned().collect()
105    }
106
107    /// Returns the set difference `self \ other`.
108    #[must_use]
109    pub fn difference(&self, other: &Self) -> Self
110    where
111        T: Clone,
112    {
113        self.values.difference(&other.values).cloned().collect()
114    }
115
116    /// Returns `true` when every element of `self` also appears in `other`.
117    #[must_use]
118    pub fn is_subset(&self, other: &Self) -> bool {
119        self.values.is_subset(&other.values)
120    }
121
122    /// Converts the unary relation into a sorted vector.
123    #[must_use]
124    pub fn to_vec(&self) -> Vec<T>
125    where
126        T: Clone,
127    {
128        self.values.iter().cloned().collect()
129    }
130}
131
132impl<T: Ord> Default for UnaryRelation<T> {
133    fn default() -> Self {
134        Self::new()
135    }
136}
137
138impl<T: Ord> FiniteRelation for UnaryRelation<T> {
139    fn len(&self) -> usize {
140        self.values.len()
141    }
142}
143
144impl<T: Ord> FromIterator<T> for UnaryRelation<T> {
145    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
146        Self {
147            values: iter.into_iter().collect(),
148        }
149    }
150}
151
152impl<T: Ord> Extend<T> for UnaryRelation<T> {
153    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
154        self.values.extend(iter);
155    }
156}
157
158impl<T: Ord> IntoIterator for UnaryRelation<T> {
159    type Item = T;
160    type IntoIter = std::collections::btree_set::IntoIter<T>;
161
162    fn into_iter(self) -> Self::IntoIter {
163        self.values.into_iter()
164    }
165}
166
167impl<'a, T: Ord> IntoIterator for &'a UnaryRelation<T> {
168    type Item = &'a T;
169    type IntoIter = std::collections::btree_set::Iter<'a, T>;
170
171    fn into_iter(self) -> Self::IntoIter {
172        self.values.iter()
173    }
174}
relmath/core/unary.rs

relmath/core/
unary.rs
