standard_lib/collections/traits/
set.rs

1use std::borrow::Borrow;
2use std::iter::{Chain, FusedIterator};
3use std::marker::PhantomData;
4use std::mem;
5
6pub trait SetInterface<T: Borrow<Q>, Q: ?Sized>: Sized {
7    /// Returns true if the set contains `item`.
8    fn contains(&self, item: &Q) -> bool;
9
10    /// Returns a reference to the contained element equal to the provided `item` or None if there
11    /// isn't one.
12    fn get(&self, item: &Q) -> Option<&T>;
13
14    /// Removes `item` from the set, returning it if it exists.
15    fn remove(&mut self, item: &Q) -> Option<T>;
16}
17
18pub trait SetIterator<T>: IntoIterator<Item = T> + SetInterface<T, T> + Sized {
19    type Iter<'a>: Iterator<Item = &'a T>
20    where
21        Self: 'a,
22        T: 'a;
23
24    /// Returns an iterator over all elements in the set, as references.
25    fn iter<'a>(&'a self) -> Self::Iter<'a>;
26
27    /// Creates an owned iterator over all items that are in `self` but not `other`. (`self \
28    /// other`)
29    fn into_difference(self, other: Self) -> IntoDifference<Self, T> {
30        IntoDifference {
31            inner: self.into_iter(),
32            other,
33            _phantom: PhantomData,
34        }
35    }
36
37    /// Creates a borrowed iterator over all items that are in `self` but not `other`. (`self \
38    /// other`)
39    fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, Self, T> {
40        Difference {
41            inner: self.iter(),
42            other,
43        }
44    }
45
46    /// Creates an owned iterator over all items that are in `self` or `other` but not both. (`self
47    /// △ other`)
48    fn into_symmetric_difference(self, other: Self) -> IntoSymmetricDifference<Self, T> {
49        IntoSymmetricDifference {
50            state: IterAndSet {
51                iterator_a: self.into_iter(),
52                set_b: Some(other),
53                _phantom: PhantomData,
54            },
55        }
56    }
57
58    /// Creates a borrowed iterator over all items that are in `self` or `other` but not both.
59    /// (`self △ other`)
60    fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, Self, T> {
61        SymmetricDifference {
62            inner: self.difference(other).chain(other.difference(self)),
63        }
64    }
65
66    /// Creates an owned iterator over all items that are in both `self` and `other`. (`self ∩
67    /// other`)
68    fn into_intersection(self, other: Self) -> IntoIntersection<Self, T> {
69        IntoIntersection {
70            inner: self.into_iter(),
71            other,
72            _phantom: PhantomData,
73        }
74    }
75
76    /// Creates a borrowed iterator over all items that are in both `self` and `other`. (`self ∩
77    /// other`)
78    fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, Self, T> {
79        Intersection {
80            inner: self.iter(),
81            other,
82        }
83    }
84
85    /// Creates an owned iterator over all items that are in either `self` or `other`. (`self ∪
86    /// other`)
87    fn into_union(self, other: Self) -> IntoUnion<Self, T> {
88        IntoUnion {
89            state: IterAndSet {
90                iterator_a: self.into_iter(),
91                set_b: Some(other),
92                _phantom: PhantomData,
93            },
94        }
95    }
96
97    /// Creates a borrowed iterator over all items that are in either `self` or `other`. (`self ∪
98    /// other`)
99    fn union<'a>(&'a self, other: &'a Self) -> Union<'a, Self, T> {
100        Union {
101            inner: self.iter().chain(other.difference(self)),
102        }
103    }
104
105    /// Returns true if `other` contains all elements of `self`. (`self ⊆ other`)
106    fn is_subset(&self, other: &Self) -> bool {
107        other.is_superset(self)
108    }
109
110    /// Returns true if `self` contains all elements of `other`. (`self ⊇ other`)
111    fn is_superset(&self, other: &Self) -> bool {
112        for item in other.iter() {
113            if !self.contains(item) {
114                return false;
115            }
116        }
117        true
118    }
119}
120
121pub(crate) enum SetIterToggle<S: SetIterator<T>, T> {
122    IterAndSet {
123        iterator_a: S::IntoIter,
124        // We use Option<S> so that we can move out from behind a mutable reference when
125        // switching states. The value can be assumed to always be Some.
126        // We're using Option rather than MaybeUninit so that it drops correctly and because it
127        // implements Default.
128        set_b: Option<S>,
129        _phantom: PhantomData<T>,
130    },
131    OtherSet {
132        iterator_b: S::IntoIter,
133        _phantom: PhantomData<T>,
134    },
135}
136
137use SetIterToggle::*;
138
139pub struct IntoDifference<S: SetIterator<T>, T> {
140    pub(crate) inner: S::IntoIter,
141    pub(crate) other: S,
142    // We need the type parameters T for SetIterator, despite not directly owning any Ts.
143    pub(crate) _phantom: PhantomData<T>,
144}
145
146impl<S: SetIterator<T>, T> Iterator for IntoDifference<S, T> {
147    type Item = T;
148
149    fn next(&mut self) -> Option<Self::Item> {
150        let mut next = self.inner.next();
151        while let Some(item) = &next
152            && self.other.contains(item)
153        {
154            next = self.inner.next();
155        }
156        next
157    }
158
159    fn size_hint(&self) -> (usize, Option<usize>) {
160        self.inner.size_hint()
161    }
162}
163
164impl<S: SetIterator<T>, T> FusedIterator for IntoDifference<S, T> {}
165
166pub struct Difference<'a, S: SetIterator<T>, T: 'a> {
167    pub(crate) inner: S::Iter<'a>,
168    pub(crate) other: &'a S,
169}
170
171impl<'a, S: SetIterator<T>, T: 'a> Iterator for Difference<'a, S, T> {
172    type Item = &'a T;
173
174    fn next(&mut self) -> Option<Self::Item> {
175        let mut next = self.inner.next();
176        while let Some(item) = next
177            && self.other.contains(item)
178        {
179            next = self.inner.next();
180        }
181        next
182    }
183
184    fn size_hint(&self) -> (usize, Option<usize>) {
185        self.inner.size_hint()
186    }
187}
188
189impl<'a, S: SetIterator<T>, T: 'a> FusedIterator for Difference<'a, S, T> {}
190
191pub struct IntoSymmetricDifference<S: SetIterator<T>, T> {
192    pub(crate) state: SetIterToggle<S, T>,
193}
194
195impl<S: SetIterator<T>, T> Iterator for IntoSymmetricDifference<S, T> {
196    type Item = T;
197
198    fn next(&mut self) -> Option<Self::Item> {
199        match &mut self.state {
200            IterAndSet { iterator_a, set_b, .. } => {
201                let mut next = iterator_a.next();
202                while let Some(item) = &next
203                    // SAFETY: set_b is Some unless otherwise stated.
204                    && unsafe {
205                        set_b.as_mut()
206                            .unwrap_unchecked()
207                            .remove(item)
208                            .is_some()
209                    }
210                {
211                    next = iterator_a.next();
212                }
213                match next {
214                    Some(val) => Some(val),
215                    None => {
216                        // SAFETY: set_b is always Some, except for the duration of this block where
217                        // its value is moved.
218                        let iterator_b = unsafe {
219                            mem::take(set_b)
220                                .unwrap_unchecked()
221                                .into_iter()
222                        };
223                        self.state = OtherSet {
224                            iterator_b,
225                            _phantom: PhantomData,
226                        };
227                        // Call next once the state is valid.
228                        self.next()
229                    },
230                }
231            },
232            OtherSet { iterator_b, .. } => iterator_b.next(),
233        }
234    }
235
236    // fn size_hint(&self) -> (usize, Option<usize>) {
237    //     self.inner.size_hint()
238    // }
239}
240
241impl<S: SetIterator<T>, T> FusedIterator for IntoSymmetricDifference<S, T> {}
242
243pub struct SymmetricDifference<'a, S: SetIterator<T>, T: 'a> {
244    pub(crate) inner: Chain<Difference<'a, S, T>, Difference<'a, S, T>>,
245}
246
247impl<'a, S: SetIterator<T>, T: 'a> Iterator for SymmetricDifference<'a, S, T> {
248    type Item = &'a T;
249
250    fn next(&mut self) -> Option<Self::Item> {
251        self.inner.next()
252    }
253
254    fn size_hint(&self) -> (usize, Option<usize>) {
255        self.inner.size_hint()
256    }
257}
258
259impl<'a, S: SetIterator<T>, T: 'a> FusedIterator for SymmetricDifference<'a, S, T> {}
260
261pub struct IntoIntersection<S: SetIterator<T>, T> {
262    pub(crate) inner: S::IntoIter,
263    pub(crate) other: S,
264    pub(crate) _phantom: PhantomData<T>,
265}
266
267impl<S: SetIterator<T>, T> Iterator for IntoIntersection<S, T> {
268    type Item = T;
269
270    fn next(&mut self) -> Option<Self::Item> {
271        let mut next = self.inner.next();
272        while let Some(item) = &next
273            && !self.other.contains(item)
274        {
275            next = self.inner.next();
276        }
277        next
278    }
279
280    fn size_hint(&self) -> (usize, Option<usize>) {
281        self.inner.size_hint()
282    }
283}
284
285impl<S: SetIterator<T>, T> FusedIterator for IntoIntersection<S, T> {}
286
287pub struct Intersection<'a, S: SetIterator<T>, T: 'a> {
288    pub(crate) inner: S::Iter<'a>,
289    pub(crate) other: &'a S,
290}
291
292impl<'a, S: SetIterator<T>, T: 'a> Iterator for Intersection<'a, S, T> {
293    type Item = &'a T;
294
295    fn next(&mut self) -> Option<Self::Item> {
296        let mut next = self.inner.next();
297        while let Some(item) = next
298            && !self.other.contains(item)
299        {
300            next = self.inner.next();
301        }
302        next
303    }
304
305    fn size_hint(&self) -> (usize, Option<usize>) {
306        self.inner.size_hint()
307    }
308}
309
310impl<'a, S: SetIterator<T>, T: 'a> FusedIterator for Intersection<'a, S, T> {}
311
312pub struct IntoUnion<S: SetIterator<T>, T> {
313    pub(crate) state: SetIterToggle<S, T>,
314}
315
316impl<S: SetIterator<T>, T> Iterator for IntoUnion<S, T> {
317    type Item = T;
318
319    fn next(&mut self) -> Option<Self::Item> {
320        match &mut self.state {
321            IterAndSet { iterator_a, set_b, .. } => {
322                let mut next = iterator_a.next();
323                while let Some(item) = &next
324                    // SAFETY: set_b is Some unless otherwise stated.
325                    && unsafe { set_b.as_ref().unwrap_unchecked().contains(item) }
326                {
327                    next = iterator_a.next();
328                }
329                match next {
330                    Some(val) => Some(val),
331                    None => {
332                        // SAFETY: set_b is always Some, except for the duration of this block where
333                        // its value is moved.
334                        let iterator_b = unsafe {
335                            mem::take(set_b)
336                                .unwrap_unchecked()
337                                .into_iter()
338                        };
339                        self.state = OtherSet {
340                            iterator_b,
341                            _phantom: PhantomData,
342                        };
343                        // Call next once the state is valid.
344                        self.next()
345                    },
346                }
347            },
348            OtherSet { iterator_b, .. } => iterator_b.next(),
349        }
350    }
351
352    // TODO: validate / update all size_hints.
353    // fn size_hint(&self) -> (usize, Option<usize>) {
354    //     self.inner.size_hint()
355    // }
356}
357
358impl<S: SetIterator<T>, T> FusedIterator for IntoUnion<S, T> {}
359
360pub struct Union<'a, S: SetIterator<T>, T: 'a> {
361    pub(crate) inner: Chain<S::Iter<'a>, Difference<'a, S, T>>,
362}
363
364impl<'a, S: SetIterator<T>, T: 'a> Iterator for Union<'a, S, T> {
365    type Item = &'a T;
366
367    fn next(&mut self) -> Option<Self::Item> {
368        self.inner.next()
369    }
370
371    fn size_hint(&self) -> (usize, Option<usize>) {
372        self.inner.size_hint()
373    }
374}
375
376impl<'a, S: SetIterator<T>, T: 'a> FusedIterator for Union<'a, S, T> {}
standard_lib/collections/traits/set.rs

standard_lib/collections/traits/
set.rs
