vec_key_value_pair/
set.rs

1use std::{
2    borrow::Borrow,
3    collections::TryReserveError,
4    fmt::Debug,
5    iter::{Chain, FusedIterator},
6    ops::{BitAnd, BitOr, BitXor, Sub},
7    vec,
8};
9
10#[cfg(test)]
11mod tests;
12
13pub struct VecSet<T> {
14    inner: Vec<T>,
15}
16
17pub struct Iter<'a, T> {
18    inner: core::slice::Iter<'a, T>,
19}
20
21impl<K> Clone for Iter<'_, K> {
22    fn clone(&self) -> Self {
23        Self {
24            inner: self.inner.clone(),
25        }
26    }
27}
28
29impl<K: Debug> Debug for Iter<'_, K> {
30    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31        f.debug_list().entries(self.clone()).finish()
32    }
33}
34
35impl<K> ExactSizeIterator for Iter<'_, K> {
36    fn len(&self) -> usize {
37        let (lower, upper) = self.inner.size_hint();
38        assert_eq!(upper, Some(lower));
39        lower
40    }
41}
42
43impl<K> FusedIterator for Iter<'_, K> {}
44
45impl<'a, K> Iterator for Iter<'a, K> {
46    type Item = &'a K;
47
48    fn next(&mut self) -> Option<Self::Item> {
49        self.inner.next()
50    }
51}
52
53pub struct Drain<'a, T> {
54    inner: std::vec::Drain<'a, T>,
55}
56
57impl<K: Debug> Debug for Drain<'_, K> {
58    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
59        Debug::fmt(&self.inner, f)
60    }
61}
62
63impl<K> ExactSizeIterator for Drain<'_, K> {
64    fn len(&self) -> usize {
65        let (lower, upper) = self.inner.size_hint();
66        // Note: This assertion is overly defensive, but it checks the invariant
67        // guaranteed by the trait. If this trait were rust-internal,
68        // we could use debug_assert!; assert_eq! will check all Rust user
69        // implementations too.
70        assert_eq!(upper, Some(lower));
71        lower
72    }
73}
74
75impl<K> FusedIterator for Drain<'_, K> {}
76
77impl<'a, K> Iterator for Drain<'a, K> {
78    type Item = K;
79
80    fn next(&mut self) -> Option<Self::Item> {
81        self.inner.next()
82    }
83}
84
85pub struct Difference<'a, T> {
86    iter: Iter<'a, T>,
87    other: &'a VecSet<T>,
88}
89
90impl<T> Clone for Difference<'_, T> {
91    fn clone(&self) -> Self {
92        Self {
93            iter: self.iter.clone(),
94            other: self.other,
95        }
96    }
97}
98
99impl<T: Debug> Debug for Difference<'_, T>
100where
101    T: Eq,
102{
103    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
104        f.debug_list().entries(self.clone()).finish()
105    }
106}
107
108impl<T> ExactSizeIterator for Difference<'_, T>
109where
110    T: Eq,
111{
112    fn len(&self) -> usize {
113        let (lower, upper) = self.iter.size_hint();
114        // Note: This assertion is overly defensive, but it checks the invariant
115        // guaranteed by the trait. If this trait were rust-internal,
116        // we could use debug_assert!; assert_eq! will check all Rust user
117        // implementations too.
118        assert_eq!(upper, Some(lower));
119        lower
120    }
121}
122
123impl<T> FusedIterator for Difference<'_, T> where T: Eq {}
124
125impl<'a, T> Iterator for Difference<'a, T>
126where
127    T: Eq,
128{
129    type Item = &'a T;
130
131    fn next(&mut self) -> Option<Self::Item> {
132        while let Some(n) = self.iter.next() {
133            if !self.other.contains(n) {
134                return Some(n);
135            }
136        }
137        None
138    }
139}
140
141pub struct SymmetricDifference<'a, T> {
142    iter: Chain<Difference<'a, T>, Difference<'a, T>>,
143}
144
145impl<T> Clone for SymmetricDifference<'_, T> {
146    fn clone(&self) -> Self {
147        Self {
148            iter: self.iter.clone(),
149        }
150    }
151}
152
153impl<T: Debug> Debug for SymmetricDifference<'_, T>
154where
155    T: Eq,
156{
157    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
158        f.debug_list().entries(self.clone()).finish()
159    }
160}
161
162impl<T> FusedIterator for SymmetricDifference<'_, T> where T: Eq {}
163
164impl<'a, T> Iterator for SymmetricDifference<'a, T>
165where
166    T: Eq,
167{
168    type Item = &'a T;
169
170    fn next(&mut self) -> Option<Self::Item> {
171        self.iter.next()
172    }
173}
174
175pub struct Intersection<'a, T> {
176    iter: Iter<'a, T>,
177    other: &'a VecSet<T>,
178}
179
180impl<T> Clone for Intersection<'_, T> {
181    fn clone(&self) -> Self {
182        Self {
183            iter: self.iter.clone(),
184            other: self.other,
185        }
186    }
187}
188
189impl<T: Debug> Debug for Intersection<'_, T>
190where
191    T: Eq,
192{
193    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
194        f.debug_list().entries(self.clone()).finish()
195    }
196}
197
198impl<T> FusedIterator for Intersection<'_, T> where T: Eq {}
199
200impl<'a, T> Iterator for Intersection<'a, T>
201where
202    T: Eq,
203{
204    type Item = &'a T;
205
206    fn next(&mut self) -> Option<Self::Item> {
207        while let Some(n) = self.iter.next() {
208            if self.other.contains(n) {
209                return Some(n);
210            }
211        }
212        None
213    }
214}
215
216pub struct Union<'a, T> {
217    iter: Chain<Iter<'a, T>, Difference<'a, T>>,
218}
219
220impl<T> Clone for Union<'_, T> {
221    fn clone(&self) -> Self {
222        Self {
223            iter: self.iter.clone(),
224        }
225    }
226}
227
228impl<T: Debug> Debug for Union<'_, T>
229where
230    T: Eq,
231{
232    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
233        f.debug_list().entries(self.clone()).finish()
234    }
235}
236
237impl<T> FusedIterator for Union<'_, T> where T: Eq {}
238
239impl<'a, T> Iterator for Union<'a, T>
240where
241    T: Eq,
242{
243    type Item = &'a T;
244
245    fn next(&mut self) -> Option<Self::Item> {
246        self.iter.next()
247    }
248}
249
250pub struct IntoIter<T> {
251    inner: vec::IntoIter<T>,
252}
253
254impl<T: Debug> Debug for IntoIter<T> {
255    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
256        Debug::fmt(&self.inner, f)
257    }
258}
259
260impl<T> ExactSizeIterator for IntoIter<T> {
261    fn len(&self) -> usize {
262        self.inner.len()
263    }
264}
265
266impl<T> FusedIterator for IntoIter<T> {}
267
268impl<'a, T> Iterator for IntoIter<T> {
269    type Item = T;
270
271    fn next(&mut self) -> Option<Self::Item> {
272        self.inner.next()
273    }
274}
275
276impl<T> VecSet<T> {
277    pub fn new() -> Self {
278        Self { inner: Vec::new() }
279    }
280
281    pub fn with_capacity(capacity: usize) -> Self {
282        Self {
283            inner: Vec::with_capacity(capacity),
284        }
285    }
286
287    pub fn capacity(&self) -> usize {
288        self.inner.capacity()
289    }
290
291    pub fn iter(&self) -> Iter<'_, T> {
292        Iter {
293            inner: self.inner.iter(),
294        }
295    }
296
297    pub fn len(&self) -> usize {
298        self.inner.len()
299    }
300
301    pub fn is_empty(&self) -> bool {
302        self.inner.is_empty()
303    }
304
305    pub fn drain(&mut self) -> Drain<'_, T> {
306        Drain {
307            inner: self.inner.drain(..),
308        }
309    }
310
311    pub fn retain<F>(&mut self, f: F)
312    where
313        F: FnMut(&T) -> bool,
314    {
315        self.inner.retain(f);
316    }
317
318    pub fn clear(&mut self) {
319        self.inner.clear();
320    }
321
322    pub fn reserve(&mut self, additional: usize) {
323        self.inner.reserve(additional);
324    }
325
326    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
327        self.inner.try_reserve(additional)
328    }
329
330    pub fn shrink_to_fit(&mut self) {
331        self.inner.shrink_to_fit();
332    }
333
334    pub fn shrink_to(&mut self, min_capacity: usize) {
335        self.inner.shrink_to(min_capacity);
336    }
337}
338
339impl<T> VecSet<T>
340where
341    T: Eq,
342{
343    pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T> {
344        Difference {
345            iter: self.iter(),
346            other,
347        }
348    }
349
350    pub fn symmetric_difference<'a>(&'a self, other: &'a VecSet<T>) -> SymmetricDifference<'a, T> {
351        SymmetricDifference {
352            iter: self.difference(other).chain(other.difference(self)),
353        }
354    }
355
356    pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> {
357        if self.len() <= other.len() {
358            Intersection {
359                iter: self.iter(),
360                other,
361            }
362        } else {
363            Intersection {
364                iter: other.iter(),
365                other: self,
366            }
367        }
368    }
369
370    pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T> {
371        if self.len() >= other.len() {
372            Union {
373                iter: self.iter().chain(other.difference(self)),
374            }
375        } else {
376            Union {
377                iter: other.iter().chain(self.difference(other)),
378            }
379        }
380    }
381
382    pub fn contains<Q>(&self, value: &Q) -> bool
383    where
384        T: Borrow<Q>,
385        Q: Eq + ?Sized,
386    {
387        for i in &self.inner {
388            if i.borrow() == value {
389                return true;
390            }
391        }
392        false
393    }
394
395    pub fn get<Q>(&self, value: &Q) -> Option<&T>
396    where
397        T: Borrow<Q>,
398        Q: Eq + ?Sized,
399    {
400        for i in &self.inner {
401            if i.borrow() == value {
402                return Some(i);
403            }
404        }
405        None
406    }
407
408    pub fn is_disjoint(&self, other: &Self) -> bool {
409        for i in &self.inner {
410            if other.contains(i) {
411                return false;
412            }
413        }
414        true
415    }
416
417    pub fn is_subset(&self, other: &Self) -> bool {
418        for i in &self.inner {
419            if !other.contains(i) {
420                return false;
421            }
422        }
423        true
424    }
425
426    pub fn is_superset(&self, other: &Self) -> bool {
427        other.is_subset(self)
428    }
429
430    pub fn insert(&mut self, value: T) -> bool {
431        if self.contains(&value) {
432            return false;
433        }
434        self.inner.push(value);
435
436        true
437    }
438
439    pub fn replace(&mut self, value: T) -> Option<T> {
440        let mut r_index = None;
441        for (index, v) in self.inner.iter().enumerate() {
442            if v == &value {
443                r_index = Some(index);
444                break;
445            }
446        }
447        if let Some(i) = r_index {
448            let old = self.inner.remove(i);
449            self.inner.push(value);
450            return Some(old);
451        }
452
453        self.inner.push(value);
454
455        None
456    }
457
458    pub fn remove<Q>(&mut self, value: &Q) -> bool
459    where
460        T: Borrow<Q>,
461        Q: Eq + ?Sized,
462    {
463        let mut r_index = None;
464        for (index, v) in self.inner.iter().enumerate() {
465            if v.borrow() == value {
466                r_index = Some(index);
467                break;
468            }
469        }
470
471        if let Some(i) = r_index {
472            _ = self.inner.remove(i);
473            return true;
474        }
475
476        false
477    }
478}
479
480impl<T> BitAnd<&VecSet<T>> for &VecSet<T>
481where
482    T: Eq + Clone,
483{
484    type Output = VecSet<T>;
485
486    fn bitand(self, rhs: &VecSet<T>) -> Self::Output {
487        self.intersection(rhs).cloned().collect()
488    }
489}
490
491impl<T> BitOr<&VecSet<T>> for &VecSet<T>
492where
493    T: Eq + Clone,
494{
495    type Output = VecSet<T>;
496
497    fn bitor(self, rhs: &VecSet<T>) -> Self::Output {
498        self.union(rhs).cloned().collect()
499    }
500}
501
502impl<T> BitXor<&VecSet<T>> for &VecSet<T>
503where
504    T: Eq + Clone,
505{
506    type Output = VecSet<T>;
507
508    fn bitxor(self, rhs: &VecSet<T>) -> Self::Output {
509        self.symmetric_difference(rhs).cloned().collect()
510    }
511}
512
513impl<T> Clone for VecSet<T>
514where
515    T: Clone,
516{
517    fn clone(&self) -> Self {
518        Self {
519            inner: self.inner.clone(),
520        }
521    }
522}
523
524impl<T> Debug for VecSet<T>
525where
526    T: Debug + Eq,
527{
528    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
529        f.debug_set().entries(self).finish()
530    }
531}
532
533impl<T> Default for VecSet<T>
534where
535    T: Default,
536{
537    fn default() -> Self {
538        Self {
539            inner: Default::default(),
540        }
541    }
542}
543
544impl<'a, T> Extend<&'a T> for VecSet<T>
545where
546    T: 'a + Eq + Copy,
547{
548    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
549        for i in iter {
550            _ = self.insert(*i);
551        }
552    }
553}
554
555impl<T> Extend<T> for VecSet<T>
556where
557    T: Eq,
558{
559    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
560        for i in iter {
561            _ = self.insert(i);
562        }
563    }
564}
565
566impl<T, const N: usize> From<[T; N]> for VecSet<T>
567where
568    T: Eq,
569{
570    fn from(value: [T; N]) -> Self {
571        let mut o = VecSet::new();
572        for i in value {
573            o.insert(i);
574        }
575
576        o
577    }
578}
579
580impl<T> FromIterator<T> for VecSet<T>
581where
582    T: Eq,
583{
584    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
585        let mut o = VecSet::new();
586        for i in iter {
587            o.insert(i);
588        }
589
590        o
591    }
592}
593
594impl<'a, T> IntoIterator for &'a VecSet<T> {
595    type Item = &'a T;
596
597    type IntoIter = Iter<'a, T>;
598
599    fn into_iter(self) -> Self::IntoIter {
600        Iter {
601            inner: self.inner.iter(),
602        }
603    }
604}
605
606impl<T> IntoIterator for VecSet<T> {
607    type Item = T;
608
609    type IntoIter = IntoIter<T>;
610
611    fn into_iter(self) -> Self::IntoIter {
612        IntoIter {
613            inner: self.inner.into_iter(),
614        }
615    }
616}
617
618impl<T> PartialEq for VecSet<T>
619where
620    T: Eq,
621{
622    fn eq(&self, other: &Self) -> bool {
623        self.is_subset(other) && self.is_superset(other)
624    }
625}
626
627impl<T> Eq for VecSet<T> where T: Eq {}
628
629impl<T> Sub<&VecSet<T>> for &VecSet<T>
630where
631    T: Eq + Clone,
632{
633    type Output = VecSet<T>;
634
635    fn sub(self, rhs: &VecSet<T>) -> Self::Output {
636        self.difference(rhs).cloned().collect()
637    }
638}
vec_key_value_pair/set.rs

vec_key_value_pair/
set.rs
