vec_collections/
vec_set.rs

1use crate::dedup::Keep;
2pub use crate::iterators::VecSetIter;
3use crate::merge_state::{
4    CloneConverter, IdConverter, InPlaceMergeState, InPlaceSmallVecMergeStateRef, NoConverter,
5};
6use crate::{
7    dedup::sort_dedup,
8    merge_state::{BoolOpMergeState, MergeStateMut, SmallVecMergeState},
9};
10use binary_merge::MergeOperation;
11#[cfg(feature = "rkyv_validated")]
12use bytecheck::CheckBytes;
13use core::{
14    cmp::Ordering,
15    fmt, hash,
16    hash::Hash,
17    iter::FromIterator,
18    ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Sub, SubAssign},
19};
20#[cfg(feature = "rkyv")]
21use rkyv::{validation::ArchiveContext, Archive};
22use smallvec::{Array, SmallVec};
23use std::collections::BTreeSet;
24#[cfg(feature = "serde")]
25use {
26    core::marker::PhantomData,
27    serde::{
28        de::{Deserialize, Deserializer, SeqAccess, Visitor},
29        ser::{Serialize, SerializeSeq, Serializer},
30    },
31};
32
33struct SetUnionOp;
34struct SetIntersectionOp;
35struct SetXorOp;
36struct SetDiffOpt;
37
38/// A set backed by a [SmallVec] of elements.
39///
40/// `A` the underlying storage. This must be an array. The size of this array is the maximum size this collection
41/// can hold without allocating. VecSet is just a wrapper around a [SmallVec], so it does not have additional memory
42/// overhead.
43///
44/// Sets support comparison operations (
45/// [is_disjoint](#method.is_disjoint),
46/// [is_subset](#method.is_subset),
47/// [is_superset](#method.is_superset)
48/// ) and set combine operations
49/// (
50/// [bitand](https://doc.rust-lang.org/std/ops/trait.BitAnd.html),
51/// [bitor](https://doc.rust-lang.org/std/ops/trait.BitOr.html),
52/// [bitxor](https://doc.rust-lang.org/std/ops/trait.BitXor.html),
53/// [sub](https://doc.rust-lang.org/std/ops/trait.Sub.html)
54/// ).
55/// They also support in place operations
56/// (
57/// [bitand_assign](https://doc.rust-lang.org/std/ops/trait.BitAndAssign.html),
58/// [bitor_assign](https://doc.rust-lang.org/std/ops/trait.BitOrAssign.html),
59/// [bitxor_assign](https://doc.rust-lang.org/std/ops/trait.BitXorAssign.html),
60/// [sub_assign](https://doc.rust-lang.org/std/ops/trait.SubAssign.html)
61/// ) that will try to avoid allocations.
62///
63/// # Creation
64///
65/// The best way to create a VecSet is to use FromIterator, via collect.
66/// ```
67/// use vec_collections::VecSet;
68/// let a: VecSet<[u32; 4]> = (0..4).collect(); // does not allocate
69/// ```
70///
71/// # General usage
72/// ```
73/// use vec_collections::{VecSet, AbstractVecSet};
74/// let a: VecSet<[u32; 4]> = (0..4).collect(); // does not allocate
75/// let b: VecSet<[u32; 2]> = (4..6).collect(); // does not allocate
76/// println!("{}", a.is_disjoint(&b)); // true
77/// let c = &a | &b; // underlying smallvec will spill over to the heap
78/// println!("{}", c.contains(&5)); // true
79/// ```
80///
81/// # In place operations
82/// ```
83/// use vec_collections::{VecSet, AbstractVecSet};
84/// let mut a: VecSet<[u32; 4]> = (0..4).collect(); // does not allocate
85/// let b: VecSet<[u32; 4]> = (2..6).collect(); // does not allocate
86/// a &= b; // in place intersection, will yield 2..4, will not allocate
87/// println!("{}", a.contains(&3)); // true
88/// ```
89///
90/// # Accessing the elements as a slice
91///
92/// Since a VecSet is a succinct collection, you can get a reference to the contents as a slice.
93///
94/// ## Example: choosing a random element
95/// ```
96/// use vec_collections::VecSet;
97/// use rand::seq::SliceRandom;
98/// let mut a: VecSet<[u32; 4]> = (0..4).collect(); // does not allocate
99/// let mut rng = rand::thread_rng();
100/// let e = a.as_ref().choose(&mut rng).unwrap();
101/// println!("{}", e);
102/// ```
103///
104/// [SmallVec]: https://docs.rs/smallvec/1.4.1/smallvec/struct.SmallVec.html
105#[derive(Default)]
106pub struct VecSet<A: Array>(SmallVec<A>);
107
108/// Type alias for a [VecSet](struct.VecSet) with up to 2 elements with inline storage.
109///
110/// This is a good default, since for usize sized types, 2 is the max you can fit in without making the struct larger.
111pub type VecSet2<T> = VecSet<[T; 2]>;
112
113/// An abstract vec set
114///
115/// this is implemented by VecSet and ArchivedVecSet, so they are interoperable.
116pub trait AbstractVecSet<T: Ord> {
117    // the elements as a slice, must be strictly ordered
118    fn as_slice(&self) -> &[T];
119    fn is_empty(&self) -> bool {
120        self.as_slice().is_empty()
121    }
122    fn contains(&self, value: &T) -> bool {
123        self.as_slice().binary_search(value).is_ok()
124    }
125
126    /// true if this set has no common elements with another set.
127    fn is_disjoint(&self, that: &impl AbstractVecSet<T>) -> bool {
128        !BoolOpMergeState::merge(self.as_slice(), that.as_slice(), SetIntersectionOp)
129    }
130
131    /// true if this set is a subset of another set.
132    ///
133    /// A set is considered to be a subset of itself.
134    fn is_subset(&self, that: &impl AbstractVecSet<T>) -> bool {
135        !BoolOpMergeState::merge(self.as_slice(), that.as_slice(), SetDiffOpt)
136    }
137
138    /// true if this set is a superset of another set.
139    ///
140    /// A set is considered to be a superset of itself.
141    fn is_superset(&self, that: &impl AbstractVecSet<T>) -> bool {
142        !BoolOpMergeState::merge(that.as_slice(), self.as_slice(), SetDiffOpt)
143    }
144
145    fn union<A: Array<Item = T>>(&self, that: &impl AbstractVecSet<T>) -> VecSet<A>
146    where
147        T: Clone,
148    {
149        VecSet(SmallVecMergeState::merge(
150            self.as_slice(),
151            that.as_slice(),
152            SetUnionOp,
153            CloneConverter,
154        ))
155    }
156
157    fn intersection<A: Array<Item = T>>(&self, that: &impl AbstractVecSet<T>) -> VecSet<A>
158    where
159        T: Clone,
160    {
161        VecSet(SmallVecMergeState::merge(
162            self.as_slice(),
163            that.as_slice(),
164            SetIntersectionOp,
165            CloneConverter,
166        ))
167    }
168
169    fn symmetric_difference<A: Array<Item = T>>(&self, that: &impl AbstractVecSet<T>) -> VecSet<A>
170    where
171        T: Clone,
172    {
173        VecSet(SmallVecMergeState::merge(
174            self.as_slice(),
175            that.as_slice(),
176            SetXorOp,
177            CloneConverter,
178        ))
179    }
180
181    fn difference<A: Array<Item = T>>(&self, that: &impl AbstractVecSet<T>) -> VecSet<A>
182    where
183        T: Clone,
184    {
185        VecSet(SmallVecMergeState::merge(
186            self.as_slice(),
187            that.as_slice(),
188            SetDiffOpt,
189            CloneConverter,
190        ))
191    }
192
193    /// An iterator that returns references to the items of this set in sorted order
194    fn iter(&self) -> VecSetIter<core::slice::Iter<T>> {
195        VecSetIter::new(self.as_slice().iter())
196    }
197}
198
199impl<A: Array> AbstractVecSet<A::Item> for VecSet<A>
200where
201    A::Item: Ord,
202{
203    fn as_slice(&self) -> &[A::Item] {
204        self.0.as_ref()
205    }
206}
207
208#[cfg(feature = "rkyv")]
209impl<T> AbstractVecSet<T> for ArchivedVecSet<T>
210where
211    T: Ord,
212{
213    fn as_slice(&self) -> &[T] {
214        self.0.as_ref()
215    }
216}
217
218impl<T: fmt::Debug, A: Array<Item = T>> fmt::Debug for VecSet<A> {
219    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
220        f.debug_set().entries(self.iter()).finish()
221    }
222}
223
224impl<T: Clone, A: Array<Item = T>> Clone for VecSet<A> {
225    fn clone(&self) -> Self {
226        Self(self.0.clone())
227    }
228}
229
230impl<T: Hash, A: Array<Item = T>> Hash for VecSet<A> {
231    fn hash<H: hash::Hasher>(&self, state: &mut H) {
232        self.0.hash(state)
233    }
234}
235
236impl<T: PartialEq, A: Array<Item = T>> PartialEq for VecSet<A> {
237    fn eq(&self, other: &Self) -> bool {
238        self.0 == other.0
239    }
240}
241
242impl<T: Eq, A: Array<Item = T>> Eq for VecSet<A> {}
243
244impl<T: PartialOrd, A: Array<Item = T>> PartialOrd for VecSet<A> {
245    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
246        self.0.partial_cmp(&other.0)
247    }
248}
249
250impl<T: Ord, A: Array<Item = T>> Ord for VecSet<A> {
251    fn cmp(&self, other: &Self) -> Ordering {
252        self.0.cmp(&other.0)
253    }
254}
255
256impl<A: Array> VecSet<A> {
257    /// Private because it does not check the invariants.
258    pub(crate) fn new_unsafe(a: SmallVec<A>) -> Self {
259        Self(a)
260    }
261    /// A set with a single element.
262    pub fn single(value: A::Item) -> Self {
263        let mut res = SmallVec::new();
264        res.push(value);
265        Self(res)
266    }
267    /// The empty set.
268    pub fn empty() -> Self {
269        Self::new_unsafe(SmallVec::new())
270    }
271    /// An iterator that returns references to the items of this set in sorted order
272    pub fn iter(&self) -> VecSetIter<core::slice::Iter<A::Item>> {
273        VecSetIter::new(self.0.iter())
274    }
275    /// The underlying memory as a slice.
276    fn as_slice(&self) -> &[A::Item] {
277        &self.0
278    }
279    /// The number of elements in the set.
280    pub fn len(&self) -> usize {
281        self.0.len()
282    }
283    /// Shrink the underlying SmallVec<T> to fit.
284    pub fn shrink_to_fit(&mut self) {
285        self.0.shrink_to_fit()
286    }
287    /// true if the set is empty.
288    pub fn is_empty(&self) -> bool {
289        self.0.is_empty()
290    }
291    /// Returns the wrapped SmallVec.
292    pub fn into_inner(self) -> SmallVec<A> {
293        self.0
294    }
295}
296
297impl<A: Array> VecSet<A>
298where
299    A::Item: Ord,
300{
301    /// insert an element.
302    ///
303    /// The time complexity of this is O(N), so building a large set using single element inserts will be slow!
304    /// Prefer using [from_iter](std::iter::FromIterator::from_iter) when building a large VecSet from elements.
305    pub fn insert(&mut self, that: A::Item) -> bool {
306        match self.0.binary_search(&that) {
307            Ok(index) => {
308                self.0[index] = that;
309                false
310            }
311            Err(index) => {
312                self.0.insert(index, that);
313                true
314            }
315        }
316    }
317
318    /// Remove an element.
319    ///
320    /// The time complexity of this is O(N), so removing many elements using single element removes inserts will be slow!
321    /// Prefer using [retain](VecSet::retain) when removing a large number of elements.
322    pub fn remove(&mut self, that: &A::Item) -> bool {
323        if let Ok(index) = self.0.binary_search(that) {
324            self.0.remove(index);
325            true
326        } else {
327            false
328        }
329    }
330
331    /// Retain all elements matching a predicate.
332    pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, mut f: F) {
333        self.0.retain(|entry| f(entry))
334    }
335
336    /// creates a set from a vec.
337    ///
338    /// Will sort and deduplicate the vector using a stable merge sort, so worst case time complexity
339    /// is O(N log N). However, this will be faster for an already partially sorted vector.
340    ///
341    /// Note that the backing memory of the vector might be reused, so if this is a large vector containing
342    /// lots of duplicates, it is advisable to call shrink_to_fit on the resulting set.
343    fn from_vec(vec: Vec<A::Item>) -> Self {
344        let mut vec = vec;
345        vec.sort();
346        vec.dedup();
347        Self::new_unsafe(SmallVec::from_vec(vec))
348    }
349}
350
351impl<'a, A: Array> IntoIterator for &'a VecSet<A> {
352    type Item = &'a A::Item;
353    type IntoIter = VecSetIter<core::slice::Iter<'a, A::Item>>;
354
355    fn into_iter(self) -> Self::IntoIter {
356        self.iter()
357    }
358}
359
360impl<A: Array> IntoIterator for VecSet<A> {
361    type Item = A::Item;
362    type IntoIter = VecSetIter<smallvec::IntoIter<A>>;
363
364    fn into_iter(self) -> Self::IntoIter {
365        VecSetIter::new(self.0.into_iter())
366    }
367}
368
369impl<A: Array> From<VecSet<A>> for Vec<A::Item> {
370    fn from(value: VecSet<A>) -> Self {
371        value.0.into_vec()
372    }
373}
374
375impl<A: Array> From<VecSet<A>> for SmallVec<A> {
376    fn from(value: VecSet<A>) -> Self {
377        value.into_inner()
378    }
379}
380
381impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> BitAnd<&VecSet<B>> for &VecSet<A> {
382    type Output = VecSet<A>;
383    fn bitand(self, that: &VecSet<B>) -> Self::Output {
384        self.intersection(that)
385    }
386}
387
388impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> BitOr<&VecSet<B>> for &VecSet<A> {
389    type Output = VecSet<A>;
390    fn bitor(self, that: &VecSet<B>) -> Self::Output {
391        self.union(that)
392    }
393}
394
395impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> BitXor<&VecSet<B>> for &VecSet<A> {
396    type Output = VecSet<A>;
397    fn bitxor(self, that: &VecSet<B>) -> Self::Output {
398        self.symmetric_difference(that)
399    }
400}
401
402impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> Sub<&VecSet<B>> for &VecSet<A> {
403    type Output = VecSet<A>;
404    fn sub(self, that: &VecSet<B>) -> Self::Output {
405        self.difference(that)
406    }
407}
408
409impl<T: Ord, A: Array<Item = T>, B: Array<Item = T>> BitAndAssign<VecSet<B>> for VecSet<A> {
410    fn bitand_assign(&mut self, that: VecSet<B>) {
411        InPlaceMergeState::merge(&mut self.0, that.0, SetIntersectionOp, IdConverter);
412    }
413}
414
415impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> BitAndAssign<&VecSet<B>>
416    for VecSet<A>
417{
418    fn bitand_assign(&mut self, that: &VecSet<B>) {
419        InPlaceSmallVecMergeStateRef::merge(
420            &mut self.0,
421            &that.0,
422            SetIntersectionOp,
423            CloneConverter,
424        );
425    }
426}
427
428impl<T: Ord, A: Array<Item = T>, B: Array<Item = T>> BitOrAssign<VecSet<B>> for VecSet<A> {
429    fn bitor_assign(&mut self, that: VecSet<B>) {
430        InPlaceMergeState::merge(&mut self.0, that.0, SetUnionOp, IdConverter);
431    }
432}
433
434impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> BitOrAssign<&VecSet<B>> for VecSet<A> {
435    fn bitor_assign(&mut self, that: &VecSet<B>) {
436        InPlaceSmallVecMergeStateRef::merge(&mut self.0, &that.0, SetUnionOp, CloneConverter);
437    }
438}
439
440impl<T: Ord, A: Array<Item = T>, B: Array<Item = T>> BitXorAssign<VecSet<B>> for VecSet<A> {
441    fn bitxor_assign(&mut self, that: VecSet<B>) {
442        InPlaceMergeState::merge(&mut self.0, that.0, SetXorOp, IdConverter);
443    }
444}
445
446impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> BitXorAssign<&VecSet<B>>
447    for VecSet<A>
448{
449    fn bitxor_assign(&mut self, that: &VecSet<B>) {
450        InPlaceSmallVecMergeStateRef::merge(&mut self.0, &that.0, SetXorOp, CloneConverter);
451    }
452}
453
454impl<T: Ord, A: Array<Item = T>, B: Array<Item = T>> SubAssign<VecSet<B>> for VecSet<A> {
455    fn sub_assign(&mut self, that: VecSet<B>) {
456        InPlaceMergeState::merge(&mut self.0, that.0, SetDiffOpt, IdConverter);
457    }
458}
459
460impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> SubAssign<&VecSet<B>> for VecSet<A> {
461    fn sub_assign(&mut self, that: &VecSet<B>) {
462        InPlaceSmallVecMergeStateRef::merge(&mut self.0, &that.0, SetDiffOpt, CloneConverter);
463    }
464}
465
466impl<A: Array> AsRef<[A::Item]> for VecSet<A> {
467    fn as_ref(&self) -> &[A::Item] {
468        self.as_slice()
469    }
470}
471
472impl<T: Ord, A: Array<Item = T>> From<Vec<T>> for VecSet<A> {
473    fn from(vec: Vec<T>) -> Self {
474        Self::from_vec(vec)
475    }
476}
477
478/// Provides a way to create a VecSet from a BTreeSet without having to sort again
479impl<T: Ord, A: Array<Item = T>> From<BTreeSet<T>> for VecSet<A> {
480    fn from(value: BTreeSet<T>) -> Self {
481        Self::new_unsafe(value.into_iter().collect())
482    }
483}
484
485/// Builds the set from an iterator.
486///
487/// Uses a heuristic to deduplicate while building the set, so the intermediate storage will never be more
488/// than twice the size of the resulting set. This is the most efficient way to build a large VecSet, significantly
489/// more efficient than single element insertion.
490///
491/// Worst case performance is O(log(n)^2 * n), but performance for already partially sorted collections will be
492/// significantly better. For a fully sorted collection, performance will be O(n).
493impl<T: Ord, A: Array<Item = T>> FromIterator<T> for VecSet<A> {
494    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
495        let mut vec: SmallVec<A> = sort_dedup(iter.into_iter(), Keep::First);
496        vec.shrink_to_fit();
497        Self::new_unsafe(vec)
498    }
499}
500
501impl<T: Ord, A: Array<Item = T>> Extend<T> for VecSet<A> {
502    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
503        *self |= Self::from_iter(iter);
504    }
505}
506
507impl<T: Ord, I: MergeStateMut<A = T, B = T>> MergeOperation<I> for SetUnionOp {
508    fn cmp(&self, a: &T, b: &T) -> Ordering {
509        a.cmp(b)
510    }
511    fn from_a(&self, m: &mut I, n: usize) -> bool {
512        m.advance_a(n, true)
513    }
514    fn from_b(&self, m: &mut I, n: usize) -> bool {
515        m.advance_b(n, true)
516    }
517    fn collision(&self, m: &mut I) -> bool {
518        m.advance_a(1, true) && m.advance_b(1, false)
519    }
520}
521
522impl<T: Ord, I: MergeStateMut<A = T, B = T>> MergeOperation<I> for SetIntersectionOp {
523    fn cmp(&self, a: &T, b: &T) -> Ordering {
524        a.cmp(b)
525    }
526    fn from_a(&self, m: &mut I, n: usize) -> bool {
527        m.advance_a(n, false)
528    }
529    fn from_b(&self, m: &mut I, n: usize) -> bool {
530        m.advance_b(n, false)
531    }
532    fn collision(&self, m: &mut I) -> bool {
533        m.advance_a(1, true) && m.advance_b(1, false)
534    }
535}
536
537impl<T: Ord, I: MergeStateMut<A = T, B = T>> MergeOperation<I> for SetDiffOpt {
538    fn cmp(&self, a: &T, b: &T) -> Ordering {
539        a.cmp(b)
540    }
541    fn from_a(&self, m: &mut I, n: usize) -> bool {
542        m.advance_a(n, true)
543    }
544    fn from_b(&self, m: &mut I, n: usize) -> bool {
545        m.advance_b(n, false)
546    }
547    fn collision(&self, m: &mut I) -> bool {
548        m.advance_a(1, false) && m.advance_b(1, false)
549    }
550}
551
552impl<T: Ord, I: MergeStateMut<A = T, B = T>> MergeOperation<I> for SetXorOp {
553    fn cmp(&self, a: &T, b: &T) -> Ordering {
554        a.cmp(b)
555    }
556    fn from_a(&self, m: &mut I, n: usize) -> bool {
557        m.advance_a(n, true)
558    }
559    fn from_b(&self, m: &mut I, n: usize) -> bool {
560        m.advance_b(n, true)
561    }
562    fn collision(&self, m: &mut I) -> bool {
563        m.advance_a(1, false) && m.advance_b(1, false)
564    }
565}
566
567#[cfg(feature = "serde")]
568impl<A: Array> Serialize for VecSet<A>
569where
570    A::Item: Serialize,
571{
572    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
573        let mut state = serializer.serialize_seq(Some(self.len()))?;
574        for item in self.iter() {
575            state.serialize_element(&item)?;
576        }
577        state.end()
578    }
579}
580
581#[cfg(feature = "serde")]
582impl<'de, A: Array> Deserialize<'de> for VecSet<A>
583where
584    A::Item: Deserialize<'de> + Ord,
585{
586    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
587        deserializer.deserialize_seq(VecSetVisitor {
588            phantom: PhantomData,
589        })
590    }
591}
592
593#[cfg(feature = "serde")]
594struct VecSetVisitor<A> {
595    phantom: PhantomData<A>,
596}
597
598#[cfg(feature = "serde")]
599impl<'de, A: Array> Visitor<'de> for VecSetVisitor<A>
600where
601    A::Item: Deserialize<'de> + Ord,
602{
603    type Value = VecSet<A>;
604
605    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
606        formatter.write_str("a sequence")
607    }
608
609    fn visit_seq<B>(self, mut seq: B) -> Result<Self::Value, B::Error>
610    where
611        B: SeqAccess<'de>,
612    {
613        let len = seq.size_hint().unwrap_or(0);
614        let mut values = SmallVec::with_capacity(len);
615
616        while let Some(value) = seq.next_element()? {
617            values.push(value);
618        }
619        values.sort();
620        values.dedup();
621        Ok(VecSet(values))
622    }
623}
624
625#[cfg(feature = "rkyv")]
626#[repr(transparent)]
627pub struct ArchivedVecSet<T>(rkyv::vec::ArchivedVec<T>);
628
629#[cfg(feature = "rkyv")]
630impl<A> rkyv::Archive for VecSet<A>
631where
632    A: Array,
633    A::Item: rkyv::Archive,
634{
635    type Archived = ArchivedVecSet<<A::Item as rkyv::Archive>::Archived>;
636
637    type Resolver = rkyv::vec::VecResolver;
638
639    unsafe fn resolve(&self, pos: usize, resolver: Self::Resolver, out: *mut Self::Archived) {
640        rkyv::vec::ArchivedVec::resolve_from_slice(self.0.as_slice(), pos, resolver, &mut (*out).0);
641    }
642}
643
644#[cfg(feature = "rkyv")]
645impl<S, T, A> rkyv::Serialize<S> for VecSet<A>
646where
647    A: Array<Item = T>,
648    T: rkyv::Archive + rkyv::Serialize<S>,
649    S: rkyv::ser::ScratchSpace + rkyv::ser::Serializer,
650{
651    fn serialize(&self, serializer: &mut S) -> Result<Self::Resolver, S::Error> {
652        rkyv::vec::ArchivedVec::serialize_from_slice(self.0.as_ref(), serializer)
653    }
654}
655
656#[cfg(feature = "rkyv")]
657impl<D, T, A> rkyv::Deserialize<VecSet<A>, D> for ArchivedVecSet<T::Archived>
658where
659    A: Array<Item = T>,
660    T: rkyv::Archive,
661    D: rkyv::Fallible + ?Sized,
662    [<<A as Array>::Item as rkyv::Archive>::Archived]:
663        rkyv::DeserializeUnsized<[<A as Array>::Item], D>,
664{
665    fn deserialize(&self, deserializer: &mut D) -> Result<VecSet<A>, D::Error> {
666        // todo: replace this with SmallVec once smallvec support for rkyv lands on crates.io
667        let items: Vec<A::Item> = self.0.deserialize(deserializer)?;
668        Ok(VecSet(items.into()))
669    }
670}
671
672/// Validation error for a vec set
673#[cfg(feature = "rkyv_validated")]
674#[derive(Debug)]
675pub enum ArchivedVecSetError {
676    /// error with the individual elements of the VecSet
677    ValueCheckError,
678    /// elements were not properly ordered
679    OrderCheckError,
680}
681
682#[cfg(feature = "rkyv_validated")]
683impl std::error::Error for ArchivedVecSetError {}
684
685#[cfg(feature = "rkyv_validated")]
686impl std::fmt::Display for ArchivedVecSetError {
687    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
688        write!(f, "{:?}", self)
689    }
690}
691
692#[cfg(feature = "rkyv_validated")]
693impl<C: ?Sized, T> bytecheck::CheckBytes<C> for ArchivedVecSet<T>
694where
695    C: ArchiveContext,
696    C::Error: std::error::Error,
697    T: Ord + Archive + CheckBytes<C>,
698    bool: bytecheck::CheckBytes<C>,
699{
700    type Error = ArchivedVecSetError;
701    unsafe fn check_bytes<'a>(
702        value: *const Self,
703        context: &mut C,
704    ) -> Result<&'a Self, Self::Error> {
705        let values = &(*value).0;
706        CheckBytes::check_bytes(values, context)
707            .map_err(|_| ArchivedVecSetError::ValueCheckError)?;
708        if !values.iter().zip(values.iter().skip(1)).all(|(a, b)| a < b) {
709            return Err(ArchivedVecSetError::OrderCheckError);
710        };
711        Ok(&*value)
712    }
713}
714
715impl<A: Array> VecSet<A>
716where
717    A::Item: Ord + Clone,
718{
719    pub fn union(&self, that: &impl AbstractVecSet<A::Item>) -> Self {
720        Self(SmallVecMergeState::merge(
721            self.as_slice(),
722            that.as_slice(),
723            SetUnionOp,
724            CloneConverter,
725        ))
726    }
727
728    pub fn intersection(&self, that: &impl AbstractVecSet<A::Item>) -> Self {
729        Self(SmallVecMergeState::merge(
730            self.as_slice(),
731            that.as_slice(),
732            SetIntersectionOp,
733            CloneConverter,
734        ))
735    }
736
737    pub fn symmetric_difference(&self, that: &impl AbstractVecSet<A::Item>) -> Self {
738        Self(SmallVecMergeState::merge(
739            self.as_slice(),
740            that.as_slice(),
741            SetXorOp,
742            CloneConverter,
743        ))
744    }
745
746    pub fn difference(&self, that: &impl AbstractVecSet<A::Item>) -> Self {
747        Self(SmallVecMergeState::merge(
748            self.as_slice(),
749            that.as_slice(),
750            SetDiffOpt,
751            CloneConverter,
752        ))
753    }
754
755    pub fn union_with(&mut self, that: &impl AbstractVecSet<A::Item>) {
756        InPlaceSmallVecMergeStateRef::merge(&mut self.0, &that.as_slice(), SetUnionOp, NoConverter);
757    }
758
759    pub fn intersection_with(&mut self, that: &impl AbstractVecSet<A::Item>) {
760        InPlaceSmallVecMergeStateRef::merge(
761            &mut self.0,
762            &that.as_slice(),
763            SetIntersectionOp,
764            NoConverter,
765        );
766    }
767
768    pub fn xor_with(&mut self, that: &impl AbstractVecSet<A::Item>) {
769        InPlaceSmallVecMergeStateRef::merge(
770            &mut self.0,
771            &that.as_slice(),
772            SetIntersectionOp,
773            NoConverter,
774        );
775    }
776
777    pub fn difference_with(&mut self, that: &impl AbstractVecSet<A::Item>) {
778        InPlaceSmallVecMergeStateRef::merge(&mut self.0, &that.as_slice(), SetDiffOpt, NoConverter);
779    }
780}
781
782#[cfg(test)]
783mod test {
784    use super::*;
785    use crate::vec_set::AbstractVecSet;
786    use num_traits::PrimInt;
787    use obey::*;
788    use quickcheck::*;
789
790    #[test]
791    fn drop_pointer_being_freed_was_not_allocated() {
792        // this test might look completely pointless, but at some point this
793        // caused an evil "pointer being freed was not allocated".
794        let mut tags: VecSet<[Box<str>; 4]> = VecSet::default();
795        tags.bitor_assign(VecSet::<[Box<str>; 4]>::single("a".into()));
796        let sv = tags.into_inner();
797        std::mem::drop(sv);
798    }
799
800    impl<T: Arbitrary + Ord + Copy + Default + fmt::Debug> Arbitrary for VecSet<[T; 2]> {
801        fn arbitrary<G: Gen>(g: &mut G) -> Self {
802            Self::from_vec(Arbitrary::arbitrary(g))
803        }
804    }
805
806    impl<E: PrimInt> TestSamples<E, bool> for VecSet<[E; 2]> {
807        fn samples(&self, res: &mut BTreeSet<E>) {
808            res.insert(E::min_value());
809            for x in self.0.iter().cloned() {
810                res.insert(x - E::one());
811                res.insert(x);
812                res.insert(x + E::one());
813            }
814            res.insert(E::max_value());
815        }
816
817        fn at(&self, elem: E) -> bool {
818            self.contains(&elem)
819        }
820    }
821
822    type Test = VecSet<[i64; 2]>;
823    type Reference = BTreeSet<i64>;
824
825    quickcheck! {
826
827        #[cfg(feature = "serde")]
828        fn serde_roundtrip(reference: Test) -> bool {
829            let bytes = serde_json::to_vec(&reference).unwrap();
830            let deser = serde_json::from_slice(&bytes).unwrap();
831            reference == deser
832        }
833
834        #[cfg(feature = "rkyv")]
835        fn rkyv_roundtrip_unvalidated(a: Test) -> bool {
836            use rkyv::*;
837            use ser::Serializer;
838            let mut serializer = ser::serializers::AllocSerializer::<256>::default();
839            serializer.serialize_value(&a).unwrap();
840            let bytes = serializer.into_serializer().into_inner();
841            let archived = unsafe { rkyv::archived_root::<Test>(&bytes) };
842            let deserialized: Test = archived.deserialize(&mut Infallible).unwrap();
843            a == deserialized
844        }
845
846        #[cfg(feature = "rkyv_validated")]
847        #[quickcheck]
848        fn rkyv_roundtrip_validated(a: Test) -> bool {
849            use rkyv::*;
850            use ser::Serializer;
851            let mut serializer = ser::serializers::AllocSerializer::<256>::default();
852            serializer.serialize_value(&a).unwrap();
853            let bytes = serializer.into_serializer().into_inner();
854            let archived = rkyv::check_archived_root::<Test>(&bytes).unwrap();
855            let deserialized: Test = archived.deserialize(&mut Infallible).unwrap();
856            a == deserialized
857        }
858
859        fn is_disjoint_sample(a: Test, b: Test) -> bool {
860            binary_property_test(&a, &b, a.is_disjoint(&b), |a, b| !(a & b))
861        }
862
863        fn is_subset_sample(a: Test, b: Test) -> bool {
864            binary_property_test(&a, &b, a.is_subset(&b), |a, b| !a | b)
865        }
866
867        fn union_sample(a: Test, b: Test) -> bool {
868            binary_element_test(&a, &b, &a | &b, |a, b| a | b)
869        }
870
871        fn intersection_sample(a: Test, b: Test) -> bool {
872            binary_element_test(&a, &b, &a & &b, |a, b| a & b)
873        }
874
875        fn xor_sample(a: Test, b: Test) -> bool {
876            binary_element_test(&a, &b, &a ^ &b, |a, b| a ^ b)
877        }
878
879        fn diff_sample(a: Test, b: Test) -> bool {
880            binary_element_test(&a, &b, &a - &b, |a, b| a & !b)
881        }
882
883        fn union(a: Reference, b: Reference) -> bool {
884            let mut a1: Test = a.iter().cloned().collect();
885            let b1: Test = b.iter().cloned().collect();
886            let r2 = &a1 | &b1;
887            a1 |= b1;
888            println!("{:?} {:?}", a, b);
889            let expected: Vec<i64> = a.union(&b).cloned().collect();
890            let actual: Vec<i64> = a1.into();
891            let actual2: Vec<i64> = r2.into();
892            expected == actual && expected == actual2
893        }
894
895        fn intersection(a: Reference, b: Reference) -> bool {
896            let mut a1: Test = a.iter().cloned().collect();
897            let b1: Test = b.iter().cloned().collect();
898            let r2 = &a1 & &b1;
899            a1 &= b1;
900            let expected: Vec<i64> = a.intersection(&b).cloned().collect();
901            let actual: Vec<i64> = a1.into();
902            let actual2: Vec<i64> = r2.into();
903            expected == actual && expected == actual2
904        }
905
906        fn xor(a: Reference, b: Reference) -> bool {
907            let mut a1: Test = a.iter().cloned().collect();
908            let b1: Test = b.iter().cloned().collect();
909            let r2 = &a1 ^ &b1;
910            a1 ^= b1;
911            let expected: Vec<i64> = a.symmetric_difference(&b).cloned().collect();
912            let actual: Vec<i64> = a1.into();
913            let actual2: Vec<i64> = r2.into();
914            expected == actual && expected == actual2
915        }
916
917        fn difference(a: Reference, b: Reference) -> bool {
918            let mut a1: Test = a.iter().cloned().collect();
919            let b1: Test = b.iter().cloned().collect();
920            let r2 = &a1 - &b1;
921            a1 -= b1;
922            let expected: Vec<i64> = a.difference(&b).cloned().collect();
923            let actual: Vec<i64> = a1.into();
924            let actual2: Vec<i64> = r2.into();
925            expected == actual && expected == actual2
926        }
927
928        fn is_disjoint(a: Reference, b: Reference) -> bool {
929            let a1: Test = a.iter().cloned().collect();
930            let b1: Test = b.iter().cloned().collect();
931            let actual = a1.is_disjoint(&b1);
932            let expected = a.is_disjoint(&b);
933            expected == actual
934        }
935
936        fn is_subset(a: Reference, b: Reference) -> bool {
937            let a1: Test = a.iter().cloned().collect();
938            let b1: Test = b.iter().cloned().collect();
939            let actual = a1.is_subset(&b1);
940            let expected = a.is_subset(&b);
941            expected == actual
942        }
943
944        fn contains(a: Reference, b: i64) -> bool {
945            let a1: Test = a.iter().cloned().collect();
946            let expected = a.contains(&b);
947            let actual = a1.contains(&b);
948            expected == actual
949        }
950    }
951
952    bitop_assign_consistent!(Test);
953    set_predicate_consistent!(Test);
954    bitop_symmetry!(Test);
955    bitop_empty!(Test);
956}
vec_collections/vec_set.rs

vec_collections/
vec_set.rs
