standard_lib/collections/traits/
set.rs

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

standard_lib/collections/traits/
set.rs
