acls_rs/algebra/
semigroup.rs

1//! Semigroup algebraic structure.
2//!
3//! A semigroup is a set equipped with an associative binary operation.
4//!
5//! # Algebraic Laws
6//!
7//! For a type to implement `Semigroup`, it must satisfy:
8//!
9//! - **Associativity**: `(a ∘ b) ∘ c = a ∘ (b ∘ c)` for all `a, b, c`
10//!
11//! # Examples
12//!
13//! ```
14//! use acls_rs::algebra::Semigroup;
15//!
16//! // PermissionSet implements Semigroup via union
17//! # use acls_rs::permission::{AtomicPermission, PermissionSet};
18//! let perms1 = PermissionSet::from([
19//!     AtomicPermission::new("file", "read"),
20//! ]);
21//! let perms2 = PermissionSet::from([
22//!     AtomicPermission::new("file", "write"),
23//! ]);
24//!
25//! let combined = perms1.combine(perms2);
26//! // combined contains both read and write
27//! ```
28
29use std::collections::BTreeSet;
30
31/// A semigroup: a set with an associative binary operation.
32///
33/// # Laws
34///
35/// Implementations must satisfy:
36/// - **Associativity**: `(a.combine(b)).combine(c) == a.combine(b.combine(c))`
37pub trait Semigroup: Sized {
38    /// Combine two elements associatively.
39    ///
40    /// This operation must be associative: `(a ∘ b) ∘ c = a ∘ (b ∘ c)`.
41    ///
42    /// # Examples
43    ///
44    /// ```
45    /// use acls_rs::algebra::Semigroup;
46    /// # use acls_rs::permission::{AtomicPermission, PermissionSet};
47    ///
48    /// let a = PermissionSet::from([AtomicPermission::new("a", "read")]);
49    /// let b = PermissionSet::from([AtomicPermission::new("b", "read")]);
50    /// let c = PermissionSet::from([AtomicPermission::new("c", "read")]);
51    ///
52    /// // Associativity
53    /// let left = a.clone().combine(b.clone()).combine(c.clone());
54    /// let right = a.combine(b.combine(c));
55    /// assert_eq!(left, right);
56    /// ```
57    fn combine(self, other: Self) -> Self;
58
59    /// Combine all elements from an iterator.
60    ///
61    /// Returns `None` if the iterator is empty, otherwise returns `Some` containing
62    /// the result of combining all elements.
63    ///
64    /// # Examples
65    ///
66    /// ```
67    /// use acls_rs::algebra::Semigroup;
68    /// # use acls_rs::permission::{AtomicPermission, PermissionSet};
69    ///
70    /// let sets = vec![
71    ///     PermissionSet::from([AtomicPermission::new("a", "read")]),
72    ///     PermissionSet::from([AtomicPermission::new("b", "read")]),
73    ///     PermissionSet::from([AtomicPermission::new("c", "read")]),
74    /// ];
75    ///
76    /// let combined = PermissionSet::combine_all(sets).unwrap();
77    /// assert_eq!(combined.len(), 3);
78    /// ```
79    fn combine_all<I: IntoIterator<Item = Self>>(iter: I) -> Option<Self> {
80        iter.into_iter().reduce(|a, b| a.combine(b))
81    }
82}
83
84// Blanket implementation for BTreeSet (used internally by PermissionSet)
85impl<T: Ord + Clone> Semigroup for BTreeSet<T> {
86    #[inline]
87    fn combine(self, other: Self) -> Self {
88        self.union(&other).cloned().collect()
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn test_btreeset_semigroup_associativity() {
98        let a: BTreeSet<i32> = [1, 2].iter().cloned().collect();
99        let b: BTreeSet<i32> = [2, 3].iter().cloned().collect();
100        let c: BTreeSet<i32> = [3, 4].iter().cloned().collect();
101
102        let left = a.clone().combine(b.clone()).combine(c.clone());
103        let right = a.combine(b.combine(c));
104
105        assert_eq!(left, right);
106    }
107
108    #[test]
109    fn test_combine_all() {
110        let sets = vec![
111            [1, 2].iter().cloned().collect::<BTreeSet<_>>(),
112            [3, 4].iter().cloned().collect::<BTreeSet<_>>(),
113            [5].iter().cloned().collect::<BTreeSet<_>>(),
114        ];
115
116        let combined = BTreeSet::combine_all(sets).unwrap();
117        assert_eq!(combined, [1, 2, 3, 4, 5].iter().cloned().collect());
118    }
119
120    #[test]
121    fn test_combine_all_empty() {
122        let empty: Vec<BTreeSet<i32>> = vec![];
123        assert_eq!(BTreeSet::combine_all(empty), None);
124    }
125}
acls_rs/algebra/semigroup.rs

acls_rs/algebra/
semigroup.rs
