pecos_core/sets/
set.rs

1// Copyright 2024 The PECOS Developers
2//
3// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
4// in compliance with the License.You may obtain a copy of the License at
5//
6//     https://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software distributed under the License
9// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
10// or implied. See the License for the specific language governing permissions and limitations under
11// the License.
12
13use crate::Element;
14use core::fmt::Debug;
15use core::ops::{BitAndAssign, BitOrAssign, BitXorAssign, SubAssign};
16
17pub trait Set<'a>:
18    Debug
19    + Clone
20    + Default
21    + BitAndAssign<&'a Self>
22    + BitAndAssign<&'a Self::Element>
23    + BitOrAssign<&'a Self>
24    + BitOrAssign<&'a Self::Element>
25    + BitXorAssign<&'a Self>
26    + BitXorAssign<&'a Self::Element>
27    + SubAssign<&'a Self>
28    + SubAssign<&'a Self::Element>
29where
30    Self: 'a,
31{
32    type Element: Element + 'a;
33
34    type Iter: Iterator<Item = &'a Self::Element>;
35    type Difference: Iterator<Item = &'a Self::Element>;
36    type Intersection: Iterator<Item = &'a Self::Element>;
37    type SymmetricDifference: Iterator<Item = &'a Self::Element>;
38    type Union: Iterator<Item = &'a Self::Element>;
39
40    fn new() -> Self;
41
42    fn capacity(&self) -> usize;
43    fn clear(&mut self);
44    fn contains(&self, value: &Self::Element) -> bool;
45    /// Returns an iterator of elements representing the difference between this set and another,
46    /// i.e., the elements that are in `self` but not in `other`.
47    fn difference(&'a self, other: &'a Self) -> Self::Difference;
48    fn difference_ref(&'a self, other: &'a Self) -> Self::Difference;
49    fn insert(&mut self, value: Self::Element);
50    // TODO: Make signature that matches HashSet
51    fn intersection(&'a self, other: &'a Self) -> Self::Intersection;
52    #[inline]
53    fn intersection_update(&mut self, rhs: &Self) {
54        self.retain(|&x| rhs.contains(&x));
55    }
56    #[inline]
57    fn intersection_item_update(&mut self, value: &Self::Element) {
58        self.retain(|&x| x == *value);
59    }
60    fn is_empty(&self) -> bool;
61    fn iter(&'a self) -> Self::Iter;
62    fn len(&self) -> usize;
63    fn remove(&mut self, value: &Self::Element);
64    fn retain<F>(&mut self, f: F)
65    where
66        F: FnMut(&Self::Element) -> bool;
67    fn symmetric_difference(&'a self, other: &'a Self) -> Self::SymmetricDifference;
68    fn symmetric_difference_update(&mut self, rhs: &Self);
69
70    #[inline]
71    fn symmetric_difference_item_update(&mut self, value: &Self::Element) {
72        if self.contains(value) {
73            self.remove(value);
74        } else {
75            self.insert(*value);
76        }
77    }
78    fn union(&'a self, other: &'a Self) -> Self::Union;
79    fn union_update(&mut self, rhs: &Self);
80    #[inline]
81    fn union_item_update(&mut self, value: &Self::Element) {
82        self.insert(*value);
83    }
84    fn with_capacity(capacity: usize) -> Self;
85
86    #[inline]
87    // Default implementations for BitAndAssign, BitOrAssign, BitXorAssign, and SubAssign
88    fn bitand_assign_set(&mut self, rhs: &Self) {
89        self.intersection_update(rhs);
90    }
91
92    #[inline]
93    fn bitand_assign_item(&mut self, rhs: &Self::Element) {
94        self.intersection_item_update(rhs);
95    }
96
97    #[inline]
98    fn bitor_assign_set(&mut self, rhs: &Self) {
99        self.union_update(rhs);
100    }
101
102    #[inline]
103    fn bitor_assign_item(&mut self, rhs: &Self::Element) {
104        self.union_item_update(rhs);
105    }
106
107    #[inline]
108    fn bitxor_assign_set(&mut self, rhs: &Self) {
109        self.symmetric_difference_update(rhs);
110    }
111
112    #[inline]
113    fn bitxor_assign_item(&mut self, rhs: &Self::Element) {
114        self.symmetric_difference_item_update(rhs);
115    }
116
117    #[inline]
118    fn sub_assign_set(&mut self, rhs: &Self) {
119        self.retain(|x| !rhs.contains(x));
120    }
121
122    #[inline]
123    fn sub_assign_item(&mut self, rhs: &Self::Element) {
124        self.remove(rhs);
125    }
126}
127
128#[macro_export]
129macro_rules! build_set_bit_ops {
130    ($set_type:ty) => {
131        impl<'a, E: Element> BitAndAssign<&'a $set_type> for $set_type {
132            #[inline]
133            fn bitand_assign(&mut self, rhs: &$set_type) {
134                self.bitand_assign_set(rhs);
135            }
136        }
137
138        impl<'a, E: Element> BitAndAssign<&'a E> for $set_type {
139            #[inline]
140            fn bitand_assign(&mut self, rhs: &E) {
141                self.bitand_assign_item(rhs);
142            }
143        }
144
145        impl<'a, E: Element> BitOrAssign<&'a $set_type> for $set_type {
146            #[inline]
147            fn bitor_assign(&mut self, rhs: &$set_type) {
148                self.bitor_assign_set(rhs);
149            }
150        }
151
152        impl<'a, E: Element> BitOrAssign<&'a E> for $set_type {
153            #[inline]
154            fn bitor_assign(&mut self, rhs: &E) {
155                self.bitor_assign_item(rhs);
156            }
157        }
158
159        impl<'a, E: Element> BitXorAssign<&'a $set_type> for $set_type {
160            #[inline]
161            fn bitxor_assign(&mut self, rhs: &$set_type) {
162                self.bitxor_assign_set(rhs);
163            }
164        }
165
166        impl<'a, E: Element> BitXorAssign<&'a E> for $set_type {
167            #[inline]
168            fn bitxor_assign(&mut self, rhs: &E) {
169                self.bitxor_assign_item(rhs);
170            }
171        }
172
173        impl<'a, E: Element> SubAssign<&'a $set_type> for $set_type {
174            #[inline]
175            fn sub_assign(&mut self, rhs: &$set_type) {
176                self.sub_assign_set(rhs);
177            }
178        }
179
180        impl<'a, E: Element> SubAssign<&'a E> for $set_type {
181            #[inline]
182            fn sub_assign(&mut self, rhs: &E) {
183                self.sub_assign_item(rhs);
184            }
185        }
186    };
187}
pecos_core/sets/set.rs

pecos_core/sets/
set.rs
