simple_vec_collections/
vec_set.rs

1//! Sets, backed by a [`Vec`].
2
3use std::{
4    borrow::Borrow,
5    fmt::Debug,
6    iter::{Chain, FusedIterator},
7    ops::{BitAnd, BitOr, BitXor, Sub},
8};
9
10/// A set.
11/// It is a logic error for any value to change such that its equality
12/// under the [`Eq`] trait changes while it is in the set.
13/// To determine if two values are “the same”, [`Eq`] is used.
14#[derive(Clone)]
15pub struct VecSet<T>(Vec<T>);
16
17impl<T> VecSet<T> {
18    /// Create a new [`VecSet`].
19    pub fn new() -> Self {
20        VecSet(Vec::new())
21    }
22
23    /// Create a new [`VecSet`] with a given pre-allocated capacity.
24    /// May allocate more than requested.
25    pub fn with_capacity(capacity: usize) -> Self {
26        VecSet(Vec::with_capacity(capacity))
27    }
28
29    /// Get the allocated capacity of the set.
30    pub fn capacity(&self) -> usize {
31        self.0.capacity()
32    }
33
34    /// Get an iterator over the values as references.
35    pub fn iter(&self) -> Iter<'_, T> {
36        Iter(self.0.iter())
37    }
38
39    /// Get the amount of values in the set.
40    pub fn len(&self) -> usize {
41        self.0.len()
42    }
43
44    /// Check if the set is empty.
45    pub fn is_empty(&self) -> bool {
46        self.0.is_empty()
47    }
48
49    /// Empty the set and return an iterator over the cleared values.
50    pub fn drain(&mut self) -> Drain<'_, T> {
51        Drain(self.0.drain(..))
52    }
53
54    /// Remove all values that do not satisfy a given predicate.
55    pub fn retain<F>(&mut self, f: F)
56    where
57        F: FnMut(&T) -> bool,
58    {
59        self.0.retain(f)
60    }
61
62    /// Remove all values.
63    pub fn clear(&mut self) {
64        self.0.clear()
65    }
66
67    /// Reserve additional space. May allocate more than requested.
68    ///
69    /// # Panics
70    ///
71    /// Panics if the new allocation fails.
72    pub fn reserve(&mut self, additional: usize) {
73        self.0.reserve(additional)
74    }
75
76    /// Like [`reserve`], but returns a [`Result`] instead of panicking.
77    ///
78    /// [`reserve`]: VecSet::reserve
79    pub fn try_reserve(
80        &mut self,
81        additional: usize,
82    ) -> Result<(), std::collections::TryReserveError> {
83        self.0.try_reserve(additional)
84    }
85
86    /// Shrink the capacity of the set as much as possible.
87    /// May keep more than precisely needed.
88    pub fn shrink_to_fit(&mut self) {
89        self.0.shrink_to_fit()
90    }
91
92    /// Shrink the capacity of the set with a lower limit.
93    /// May keep more than precisely needed.
94    pub fn shrink_to(&mut self, min_capacity: usize) {
95        self.0.shrink_to(min_capacity)
96    }
97}
98
99impl<T: Eq> VecSet<T> {
100    /// Get an iterator over the set difference between two sets.
101    pub fn difference<'a>(&'a self, other: &'a VecSet<T>) -> Difference<'a, T> {
102        Difference(self.iter(), other)
103    }
104
105    /// Get an iterator over the symmetric set difference between two sets.
106    pub fn symmetric_difference<'a>(&'a self, other: &'a VecSet<T>) -> SymmetricDifference<'a, T> {
107        SymmetricDifference(self.difference(other).chain(other.difference(self)))
108    }
109
110    /// Get an iterator over the intersection of two sets.
111    pub fn intersection<'a>(&'a self, other: &'a VecSet<T>) -> Intersection<'a, T> {
112        Intersection(self.iter(), other)
113    }
114
115    /// Get an iterator over the union of two sets.
116    pub fn union<'a>(&'a self, other: &'a VecSet<T>) -> Union<'a, T> {
117        Union(self.iter().chain(other.difference(self)))
118    }
119
120    /// Check if the set contains a given value.
121    pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
122    where
123        T: Borrow<Q>,
124        Q: Eq,
125    {
126        self.get(value).is_some()
127    }
128
129    /// Get a value stored in the set.
130    pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
131    where
132        T: Borrow<Q>,
133        Q: Eq,
134    {
135        self.iter().find(|&v| v.borrow() == value)
136    }
137
138    /// Check if two sets are disjoint.
139    pub fn is_disjoint(&self, other: &VecSet<T>) -> bool {
140        if self.len() <= other.len() {
141            self.iter().all(|v| !other.contains(v))
142        } else {
143            other.iter().all(|v| !self.contains(v))
144        }
145    }
146
147    /// Check if one set is a subset of another.
148    pub fn is_subset(&self, other: &VecSet<T>) -> bool {
149        if self.len() <= other.len() {
150            self.iter().all(|v| other.contains(v))
151        } else {
152            false
153        }
154    }
155
156    /// Check if one set is a superset of another.
157    pub fn is_superset(&self, other: &VecSet<T>) -> bool {
158        other.is_subset(self)
159    }
160
161    /// Insert a value into the set.
162    /// Returns `true` if the value was successfully inserted,
163    /// and `false` if the value was already present.
164    pub fn insert(&mut self, value: T) -> bool {
165        for v in &*self {
166            if *v == value {
167                return false;
168            }
169        }
170        self.0.push(value);
171        true
172    }
173
174    /// Replace a value with a new, equal value.
175    /// If the value is replaced successfully, the old value is returned.
176    pub fn replace(&mut self, value: T) -> Option<T> {
177        for v in &mut self.0 {
178            if *v == value {
179                return Some(std::mem::replace(v, value));
180            }
181        }
182        None
183    }
184
185    /// Remove a value from the set.
186    pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
187    where
188        T: Borrow<Q>,
189        Q: Eq,
190    {
191        match self.iter().position(|v| v.borrow() == value) {
192            Some(i) => {
193                self.0.remove(i);
194                true
195            }
196            None => false,
197        }
198    }
199
200    /// Remove a value from the set.
201    /// If the value is succesfully removed, it is returned.
202    pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
203    where
204        T: Borrow<Q>,
205        Q: Eq,
206    {
207        match self.iter().position(|v| v.borrow() == value) {
208            Some(i) => Some(self.0.remove(i)),
209            None => None,
210        }
211    }
212}
213
214impl<T: Eq> VecSet<T> {
215    /// Check two sets for equality while considering the order of values.
216    pub fn eq_ordered(&self, other: &Self) {
217        self.iter().eq(other.iter());
218    }
219}
220
221impl<T: Eq + Clone> BitAnd<&VecSet<T>> for &VecSet<T> {
222    type Output = VecSet<T>;
223
224    /// Get the intersection of two sets as a new set.
225    fn bitand(self, rhs: &VecSet<T>) -> Self::Output {
226        self.intersection(rhs).cloned().collect()
227    }
228}
229
230impl<T: Eq + Clone> BitOr<&VecSet<T>> for &VecSet<T> {
231    type Output = VecSet<T>;
232
233    /// Get the union of two sets as a new set.
234    fn bitor(self, rhs: &VecSet<T>) -> Self::Output {
235        self.union(rhs).cloned().collect()
236    }
237}
238
239impl<T: Eq + Clone> BitXor<&VecSet<T>> for &VecSet<T> {
240    type Output = VecSet<T>;
241
242    /// Get the symmetric set difference between two sets as a new set.
243    fn bitxor(self, rhs: &VecSet<T>) -> Self::Output {
244        self.symmetric_difference(rhs).cloned().collect()
245    }
246}
247
248impl<T: Debug> Debug for VecSet<T> {
249    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
250        f.debug_set().entries(self.iter()).finish()
251    }
252}
253
254impl<T> Default for VecSet<T> {
255    fn default() -> Self {
256        Self::new()
257    }
258}
259
260impl<'a, T: Eq + Copy> Extend<&'a T> for VecSet<T> {
261    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
262        let iter = iter.into_iter();
263        self.reserve(iter.size_hint().0);
264        for value in iter {
265            self.insert(*value);
266        }
267    }
268}
269
270impl<T: Eq> Extend<T> for VecSet<T> {
271    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
272        let iter = iter.into_iter();
273        self.reserve(iter.size_hint().0);
274        for value in iter {
275            self.insert(value);
276        }
277    }
278}
279
280impl<T: Eq, const N: usize> From<[T; N]> for VecSet<T> {
281    fn from(arr: [T; N]) -> Self {
282        let mut set = Self::with_capacity(arr.len());
283        set.extend(arr);
284        set
285    }
286}
287
288impl<T: Eq> FromIterator<T> for VecSet<T> {
289    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
290        let iter = iter.into_iter();
291        let mut set = Self::with_capacity(iter.size_hint().0);
292        set.extend(iter);
293        set
294    }
295}
296
297impl<'a, T> IntoIterator for &'a VecSet<T> {
298    type Item = &'a T;
299    type IntoIter = Iter<'a, T>;
300    fn into_iter(self) -> Self::IntoIter {
301        self.iter()
302    }
303}
304
305impl<T> IntoIterator for VecSet<T> {
306    type Item = T;
307    type IntoIter = IntoIter<T>;
308
309    /// Get an iterator over the values.
310    fn into_iter(self) -> Self::IntoIter {
311        IntoIter(self.0.into_iter())
312    }
313}
314
315impl<T: Eq + Clone> Sub<&VecSet<T>> for &VecSet<T> {
316    type Output = VecSet<T>;
317
318    /// Get the set difference between two sets as a new set.
319    fn sub(self, rhs: &VecSet<T>) -> Self::Output {
320        self.difference(rhs).cloned().collect()
321    }
322}
323
324impl<T: PartialEq + Ord> PartialEq for VecSet<T> {
325    fn eq(&self, other: &Self) -> bool {
326        self.iter().all(|value| other.contains(value))
327            && other.iter().all(|value| self.contains(value))
328    }
329}
330
331impl<T: Eq + Ord> Eq for VecSet<T> {}
332
333/// An iterator over the values of a set.
334/// Yields the values as references.
335/// Generated by the [`iter`] method
336///
337/// [`iter`]: VecSet::iter
338pub struct Iter<'a, T>(std::slice::Iter<'a, T>);
339
340impl<T> Clone for Iter<'_, T> {
341    fn clone(&self) -> Self {
342        Iter(self.0.clone())
343    }
344}
345
346impl<T: Debug> Debug for Iter<'_, T> {
347    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
348        f.debug_list().entries(self.clone()).finish()
349    }
350}
351
352impl<T> ExactSizeIterator for Iter<'_, T> {
353    fn len(&self) -> usize {
354        self.0.len()
355    }
356}
357
358impl<'a, T> Iterator for Iter<'a, T> {
359    type Item = &'a T;
360    fn next(&mut self) -> Option<Self::Item> {
361        self.0.next()
362    }
363    fn size_hint(&self) -> (usize, Option<usize>) {
364        self.0.size_hint()
365    }
366}
367
368impl<T> FusedIterator for Iter<'_, T> {}
369
370/// An iterator over the removed values of a set.
371/// Yields the values as values.
372/// Generated by the [`drain`] method.
373///
374/// [`drain`]: VecSet::drain
375pub struct Drain<'a, T>(std::vec::Drain<'a, T>);
376
377impl<T: Debug> Debug for Drain<'_, T> {
378    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
379        f.debug_list().entries(self.0.as_slice().iter()).finish()
380    }
381}
382
383impl<T> ExactSizeIterator for Drain<'_, T> {
384    fn len(&self) -> usize {
385        self.0.len()
386    }
387}
388
389impl<T> Iterator for Drain<'_, T> {
390    type Item = T;
391    fn next(&mut self) -> Option<Self::Item> {
392        self.0.next()
393    }
394}
395
396impl<T> FusedIterator for Drain<'_, T> {}
397
398/// An iterator over the set difference between two sets.
399/// Yields the values as references.
400/// Generated by the [`difference`] method.
401///
402/// [`difference`]: VecSet::difference
403pub struct Difference<'a, T>(Iter<'a, T>, &'a VecSet<T>);
404
405impl<T> Clone for Difference<'_, T> {
406    fn clone(&self) -> Self {
407        Difference(self.0.clone(), self.1)
408    }
409}
410
411impl<T: Debug + Eq> Debug for Difference<'_, T> {
412    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
413        f.debug_list().entries(self.clone()).finish()
414    }
415}
416
417impl<'a, T: Eq> Iterator for Difference<'a, T> {
418    type Item = &'a T;
419    fn next(&mut self) -> Option<Self::Item> {
420        loop {
421            let value = self.0.next()?;
422            if !self.1.contains(value) {
423                return Some(value);
424            }
425        }
426    }
427    fn size_hint(&self) -> (usize, Option<usize>) {
428        let lhs_len = self.0.len();
429        let rhs_len = self.1.len();
430        (lhs_len.saturating_sub(rhs_len), Some(lhs_len))
431    }
432}
433
434impl<T: Eq> FusedIterator for Difference<'_, T> {}
435
436/// An iterator over the symmetric set difference between two sets.
437/// Yields the values as references.
438/// Generated by the [`symmetric_difference`] method.
439///
440/// [`symmetric_difference`]: VecSet::symmetric_difference
441pub struct SymmetricDifference<'a, T>(Chain<Difference<'a, T>, Difference<'a, T>>);
442
443impl<T> Clone for SymmetricDifference<'_, T> {
444    fn clone(&self) -> Self {
445        SymmetricDifference(self.0.clone())
446    }
447}
448
449impl<T: Debug + Eq> Debug for SymmetricDifference<'_, T> {
450    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
451        f.debug_list().entries(self.clone()).finish()
452    }
453}
454
455impl<'a, T: Eq> Iterator for SymmetricDifference<'a, T> {
456    type Item = &'a T;
457    fn next(&mut self) -> Option<Self::Item> {
458        self.0.next()
459    }
460    fn size_hint(&self) -> (usize, Option<usize>) {
461        self.0.size_hint()
462    }
463}
464
465impl<T: Eq> FusedIterator for SymmetricDifference<'_, T> {}
466
467/// An iterator over the intersection of two sets.
468/// Yields the values as references.
469/// Generated by the [`intersection`] method.
470///
471/// [`intersection`]: VecSet::intersection
472pub struct Intersection<'a, T>(Iter<'a, T>, &'a VecSet<T>);
473
474impl<T> Clone for Intersection<'_, T> {
475    fn clone(&self) -> Self {
476        Intersection(self.0.clone(), self.1)
477    }
478}
479
480impl<T: Debug + Eq> Debug for Intersection<'_, T> {
481    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
482        f.debug_list().entries(self.clone()).finish()
483    }
484}
485
486impl<'a, T: Eq> Iterator for Intersection<'a, T> {
487    type Item = &'a T;
488    fn next(&mut self) -> Option<Self::Item> {
489        loop {
490            let value = self.0.next()?;
491            if self.1.contains(value) {
492                return Some(value);
493            }
494        }
495    }
496    fn size_hint(&self) -> (usize, Option<usize>) {
497        let lhs_len = self.0.len();
498        let rhs_len = self.1.len();
499        (0, Some(std::cmp::min(lhs_len, rhs_len)))
500    }
501}
502
503impl<T: Eq> FusedIterator for Intersection<'_, T> {}
504
505/// An iterator over the union of two sets.
506/// Yields the values as references.
507/// Generated by the [`union`] method.
508///
509/// [`union`]: VecSet::union
510pub struct Union<'a, T>(Chain<Iter<'a, T>, Difference<'a, T>>);
511
512impl<T> Clone for Union<'_, T> {
513    fn clone(&self) -> Self {
514        Union(self.0.clone())
515    }
516}
517
518impl<T: Debug + Eq> Debug for Union<'_, T> {
519    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
520        f.debug_list().entries(self.clone()).finish()
521    }
522}
523
524impl<'a, T: Eq> Iterator for Union<'a, T> {
525    type Item = &'a T;
526    fn next(&mut self) -> Option<Self::Item> {
527        self.0.next()
528    }
529    fn size_hint(&self) -> (usize, Option<usize>) {
530        self.0.size_hint()
531    }
532}
533
534impl<T: Eq> FusedIterator for Union<'_, T> {}
535
536/// An iterator over the values of a set.
537/// Yields the values as values.
538/// Generated by the [`into_iter`] method.
539///
540/// [`into_iter`]: IntoIterator::into_iter
541pub struct IntoIter<T>(std::vec::IntoIter<T>);
542
543impl<T: Debug> Debug for IntoIter<T> {
544    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
545        f.debug_list().entries(self.0.as_slice().iter()).finish()
546    }
547}
548
549impl<T> ExactSizeIterator for IntoIter<T> {
550    fn len(&self) -> usize {
551        self.0.len()
552    }
553}
554
555impl<T> Iterator for IntoIter<T> {
556    type Item = T;
557    fn next(&mut self) -> Option<Self::Item> {
558        self.0.next()
559    }
560    fn size_hint(&self) -> (usize, Option<usize>) {
561        self.0.size_hint()
562    }
563}
564
565impl<T> FusedIterator for IntoIter<T> {}
simple_vec_collections/vec_set.rs

simple_vec_collections/
vec_set.rs
