bit_set/
lib.rs

1// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! # Description
12//!
13//! An implementation of a set using a bit vector as an underlying
14//! representation for holding unsigned numerical elements.
15//!
16//! It should also be noted that the amount of storage necessary for holding a
17//! set of objects is proportional to the maximum of the objects when viewed
18//! as a `usize`.
19//!
20//! # Examples
21//!
22//! ```
23//! use bit_set::BitSet;
24//!
25//! // It's a regular set
26//! let mut s = BitSet::new();
27//! s.insert(0);
28//! s.insert(3);
29//! s.insert(7);
30//!
31//! s.remove(7);
32//!
33//! if !s.contains(7) {
34//!     println!("There is no 7");
35//! }
36//!
37//! // Can initialize from a `BitVec`
38//! let other = BitSet::from_bytes(&[0b11010000]);
39//!
40//! s.union_with(&other);
41//!
42//! // Print 0, 1, 3 in some order
43//! for x in s.iter() {
44//!     println!("{}", x);
45//! }
46//!
47//! // Can convert back to a `BitVec`
48//! let bv = s.into_bit_vec();
49//! assert!(bv[3]);
50//! ```
51#![doc(html_root_url = "https://docs.rs/bit-set/0.10.0/bit_set/")]
52#![deny(clippy::shadow_reuse)]
53#![deny(clippy::shadow_same)]
54#![deny(clippy::shadow_unrelated)]
55#![no_std]
56
57#[cfg(any(test, feature = "std"))]
58extern crate std;
59
60pub use bit_vec::BitBlock;
61
62use bit_vec::{BitVec, Blocks};
63use core::cmp;
64use core::cmp::Ordering;
65use core::fmt;
66use core::hash;
67use core::iter::{self, Chain, Enumerate, FromIterator, Repeat, Skip, Take};
68
69#[cfg(feature = "nanoserde")]
70extern crate alloc;
71#[cfg(feature = "nanoserde")]
72use alloc::vec::Vec;
73#[cfg(feature = "nanoserde")]
74use nanoserde::{DeBin, DeJson, DeRon, SerBin, SerJson, SerRon};
75
76type MatchWords<'a, B> = Chain<Enumerate<Blocks<'a, B>>, Skip<Take<Enumerate<Repeat<B>>>>>;
77
78/// Computes how many blocks are needed to store that many bits
79fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
80    // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
81    // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
82    // one too many. So we need to check if that's the case. We can do that by computing if
83    // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
84    // superior modulo operator on a power of two to this.
85    //
86    // Note that we can technically avoid this branch with the expression
87    // `(nbits + BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
88    if bits % B::bits() == 0 {
89        bits / B::bits()
90    } else {
91        bits / B::bits() + 1
92    }
93}
94
95#[allow(clippy::iter_skip_zero)]
96// Take two BitVec's, and return iterators of their words, where the shorter one
97// has been padded with 0's
98fn match_words<'a, 'b, B: BitBlock>(
99    a: &'a BitVec<B>,
100    b: &'b BitVec<B>,
101) -> (MatchWords<'a, B>, MatchWords<'b, B>) {
102    let a_len = a.storage().len();
103    let b_len = b.storage().len();
104
105    // have to uselessly pretend to pad the longer one for type matching
106    if a_len < b_len {
107        (
108            a.blocks()
109                .enumerate()
110                .chain(iter::repeat(B::zero()).enumerate().take(b_len).skip(a_len)),
111            b.blocks()
112                .enumerate()
113                .chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)),
114        )
115    } else {
116        (
117            a.blocks()
118                .enumerate()
119                .chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)),
120            b.blocks()
121                .enumerate()
122                .chain(iter::repeat(B::zero()).enumerate().take(a_len).skip(b_len)),
123        )
124    }
125}
126
127#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
128#[cfg_attr(
129    feature = "borsh",
130    derive(borsh::BorshDeserialize, borsh::BorshSerialize)
131)]
132#[cfg_attr(
133    feature = "miniserde",
134    derive(miniserde::Deserialize, miniserde::Serialize)
135)]
136#[cfg_attr(
137    feature = "nanoserde",
138    derive(DeBin, DeJson, DeRon, SerBin, SerJson, SerRon)
139)]
140pub struct BitSet<B = u32> {
141    bit_vec: BitVec<B>,
142}
143
144impl<B: BitBlock> Clone for BitSet<B> {
145    fn clone(&self) -> Self {
146        BitSet {
147            bit_vec: self.bit_vec.clone(),
148        }
149    }
150
151    fn clone_from(&mut self, other: &Self) {
152        self.bit_vec.clone_from(&other.bit_vec);
153    }
154}
155
156impl<B: BitBlock> Default for BitSet<B> {
157    #[inline]
158    fn default() -> Self {
159        BitSet {
160            bit_vec: Default::default(),
161        }
162    }
163}
164
165impl<B: BitBlock> FromIterator<usize> for BitSet<B> {
166    fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
167        let mut ret = Self::default();
168        ret.extend(iter);
169        ret
170    }
171}
172
173impl<B: BitBlock> Extend<usize> for BitSet<B> {
174    #[inline]
175    fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I) {
176        for i in iter {
177            self.insert(i);
178        }
179    }
180}
181
182impl<B: BitBlock> PartialOrd for BitSet<B> {
183    #[inline]
184    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
185        Some(self.cmp(other))
186    }
187}
188
189impl<B: BitBlock> Ord for BitSet<B> {
190    #[inline]
191    fn cmp(&self, other: &Self) -> Ordering {
192        self.iter().cmp(other)
193    }
194}
195
196impl<B: BitBlock> PartialEq for BitSet<B> {
197    #[inline]
198    fn eq(&self, other: &Self) -> bool {
199        self.iter().eq(other)
200    }
201}
202
203impl<B: BitBlock> Eq for BitSet<B> {}
204
205impl BitSet<u32> {
206    /// Creates a new empty `BitSet`.
207    ///
208    /// # Examples
209    ///
210    /// ```
211    /// use bit_set::BitSet;
212    ///
213    /// let mut s = BitSet::new();
214    /// ```
215    #[inline]
216    pub fn new() -> Self {
217        Self::default()
218    }
219
220    /// Creates a new `BitSet` with initially no contents, able to
221    /// hold `nbits` elements without resizing.
222    ///
223    /// # Examples
224    ///
225    /// ```
226    /// use bit_set::BitSet;
227    ///
228    /// let mut s = BitSet::with_capacity(100);
229    /// assert!(s.capacity() >= 100);
230    /// ```
231    #[inline]
232    pub fn with_capacity(nbits: usize) -> Self {
233        let bit_vec = BitVec::from_elem(nbits, false);
234        Self::from_bit_vec(bit_vec)
235    }
236
237    /// Creates a new `BitSet` from the given bit vector.
238    ///
239    /// # Examples
240    ///
241    /// ```
242    /// use bit_vec::BitVec;
243    /// use bit_set::BitSet;
244    ///
245    /// let bv = BitVec::from_bytes(&[0b01100000]);
246    /// let s = BitSet::from_bit_vec(bv);
247    ///
248    /// // Print 1, 2 in arbitrary order
249    /// for x in s.iter() {
250    ///     println!("{}", x);
251    /// }
252    /// ```
253    #[inline]
254    pub fn from_bit_vec(bit_vec: BitVec) -> Self {
255        BitSet { bit_vec }
256    }
257
258    pub fn from_bytes(bytes: &[u8]) -> Self {
259        BitSet {
260            bit_vec: BitVec::from_bytes(bytes),
261        }
262    }
263}
264
265impl<B: BitBlock> BitSet<B> {
266    /// Creates a new empty `BitSet`.
267    ///
268    /// # Examples
269    ///
270    /// ```
271    /// use bit_set::BitSet;
272    ///
273    /// let mut s = <BitSet>::new_general();
274    /// ```
275    #[inline]
276    pub fn new_general() -> Self {
277        Self::default()
278    }
279
280    /// Creates a new `BitSet` with initially no contents, able to
281    /// hold `nbits` elements without resizing.
282    ///
283    /// # Examples
284    ///
285    /// ```
286    /// use bit_set::BitSet;
287    ///
288    /// let mut s = <BitSet>::with_capacity_general(100);
289    /// assert!(s.capacity() >= 100);
290    /// ```
291    #[inline]
292    pub fn with_capacity_general(nbits: usize) -> Self {
293        let bit_vec = BitVec::from_elem_general(nbits, false);
294        Self::from_bit_vec_general(bit_vec)
295    }
296
297    /// Creates a new `BitSet` from the given bit vector.
298    ///
299    /// # Examples
300    ///
301    /// ```
302    /// use bit_vec::BitVec;
303    /// use bit_set::BitSet;
304    ///
305    /// let bv: BitVec<u64> = BitVec::from_bytes_general(&[0b01100000]);
306    /// let s = BitSet::from_bit_vec_general(bv);
307    ///
308    /// // Print 1, 2 in arbitrary order
309    /// for x in s.iter() {
310    ///     println!("{}", x);
311    /// }
312    /// ```
313    #[inline]
314    pub fn from_bit_vec_general(bit_vec: BitVec<B>) -> Self {
315        BitSet { bit_vec }
316    }
317
318    pub fn from_bytes_general(bytes: &[u8]) -> Self {
319        BitSet {
320            bit_vec: BitVec::from_bytes_general(bytes),
321        }
322    }
323
324    /// Returns the capacity in bits for this bit vector. Inserting any
325    /// element less than this amount will not trigger a resizing.
326    ///
327    /// # Examples
328    ///
329    /// ```
330    /// use bit_set::BitSet;
331    ///
332    /// let mut s = BitSet::with_capacity(100);
333    /// assert!(s.capacity() >= 100);
334    /// ```
335    #[inline]
336    pub fn capacity(&self) -> usize {
337        self.bit_vec.capacity()
338    }
339
340    /// Reserves capacity for the given `BitSet` to contain `len` distinct elements. In the case
341    /// of `BitSet` this means reallocations will not occur as long as all inserted elements
342    /// are less than `len`.
343    ///
344    /// The collection may reserve more space to avoid frequent reallocations.
345    ///
346    ///
347    /// # Examples
348    ///
349    /// ```
350    /// use bit_set::BitSet;
351    ///
352    /// let mut s = BitSet::new();
353    /// s.reserve_len(10);
354    /// assert!(s.capacity() >= 10);
355    /// ```
356    pub fn reserve_len(&mut self, len: usize) {
357        let cur_len = self.bit_vec.len();
358        if len >= cur_len {
359            self.bit_vec.reserve(len - cur_len);
360        }
361    }
362
363    /// Reserves the minimum capacity for the given `BitSet` to contain `len` distinct elements.
364    /// In the case of `BitSet` this means reallocations will not occur as long as all inserted
365    /// elements are less than `len`.
366    ///
367    /// Note that the allocator may give the collection more space than it requests. Therefore
368    /// capacity can not be relied upon to be precisely minimal. Prefer `reserve_len` if future
369    /// insertions are expected.
370    ///
371    ///
372    /// # Examples
373    ///
374    /// ```
375    /// use bit_set::BitSet;
376    ///
377    /// let mut s = BitSet::new();
378    /// s.reserve_len_exact(10);
379    /// assert!(s.capacity() >= 10);
380    /// ```
381    pub fn reserve_len_exact(&mut self, len: usize) {
382        let cur_len = self.bit_vec.len();
383        if len >= cur_len {
384            self.bit_vec.reserve_exact(len - cur_len);
385        }
386    }
387
388    /// Consumes this set to return the underlying bit vector.
389    ///
390    /// # Examples
391    ///
392    /// ```
393    /// use bit_set::BitSet;
394    ///
395    /// let mut s = BitSet::new();
396    /// s.insert(0);
397    /// s.insert(3);
398    ///
399    /// let bv = s.into_bit_vec();
400    /// assert!(bv[0]);
401    /// assert!(bv[3]);
402    /// ```
403    #[inline]
404    pub fn into_bit_vec(self) -> BitVec<B> {
405        self.bit_vec
406    }
407
408    /// Returns a reference to the underlying bit vector.
409    ///
410    /// # Examples
411    ///
412    /// ```
413    /// use bit_set::BitSet;
414    ///
415    /// let mut set = BitSet::new();
416    /// set.insert(0);
417    ///
418    /// let bv = set.get_ref();
419    /// assert_eq!(bv[0], true);
420    /// ```
421    #[inline]
422    pub fn get_ref(&self) -> &BitVec<B> {
423        &self.bit_vec
424    }
425
426    /// Returns a mutable reference to the underlying bit vector.
427    ///
428    /// # Examples
429    ///
430    /// ```
431    /// use bit_set::BitSet;
432    ///
433    /// let mut set = BitSet::new();
434    /// set.insert(0);
435    /// set.insert(3);
436    ///
437    /// {
438    ///     let bv = set.get_mut();
439    ///     bv.set(1, true);
440    /// }
441    ///
442    /// assert!(set.contains(0));
443    /// assert!(set.contains(1));
444    /// assert!(set.contains(3));
445    /// ```
446    #[inline]
447    pub fn get_mut(&mut self) -> &mut BitVec<B> {
448        &mut self.bit_vec
449    }
450
451    #[inline]
452    fn other_op<F>(&mut self, other: &Self, mut f: F)
453    where
454        F: FnMut(B, B) -> B,
455    {
456        // Unwrap BitVecs
457        let self_bit_vec = &mut self.bit_vec;
458        let other_bit_vec = &other.bit_vec;
459
460        let self_len = self_bit_vec.len();
461        let other_len = other_bit_vec.len();
462
463        // Expand the vector if necessary
464        if self_len < other_len {
465            self_bit_vec.grow(other_len - self_len, false);
466        }
467
468        // virtually pad other with 0's for equal lengths
469        let other_words = {
470            let (_, result) = match_words(self_bit_vec, other_bit_vec);
471            result
472        };
473
474        // Apply values found in other
475        for (i, w) in other_words {
476            let old = self_bit_vec.storage()[i];
477            let new = f(old, w);
478            unsafe {
479                self_bit_vec.storage_mut()[i] = new;
480            }
481        }
482    }
483
484    /// Truncates the underlying vector to the least length required.
485    ///
486    /// # Examples
487    ///
488    /// ```
489    /// use bit_set::BitSet;
490    ///
491    /// let mut s = BitSet::new();
492    /// s.insert(3231);
493    /// s.remove(3231);
494    ///
495    /// // Internal storage will probably be bigger than necessary
496    /// println!("old capacity: {}", s.capacity());
497    /// assert!(s.capacity() >= 3231);
498    ///
499    /// // Now should be smaller
500    /// s.shrink_to_fit();
501    /// println!("new capacity: {}", s.capacity());
502    /// ```
503    #[inline]
504    pub fn shrink_to_fit(&mut self) {
505        let bit_vec = &mut self.bit_vec;
506        // Obtain original length
507        let old_len = bit_vec.storage().len();
508        // Obtain coarse trailing zero length
509        let n = bit_vec
510            .storage()
511            .iter()
512            .rev()
513            .take_while(|&&n| n == B::zero())
514            .count();
515        // Truncate away all empty trailing blocks, then shrink_to_fit
516        let trunc_len = old_len - n;
517        unsafe {
518            bit_vec.storage_mut().truncate(trunc_len);
519            bit_vec.set_len(trunc_len * B::bits());
520        }
521        bit_vec.shrink_to_fit();
522    }
523
524    /// Iterator over each usize stored in the `BitSet`.
525    ///
526    /// # Examples
527    ///
528    /// ```
529    /// use bit_set::BitSet;
530    ///
531    /// let s = BitSet::from_bytes(&[0b01001010]);
532    ///
533    /// // Print 1, 4, 6 in arbitrary order
534    /// for x in s.iter() {
535    ///     println!("{}", x);
536    /// }
537    /// ```
538    #[inline]
539    pub fn iter(&self) -> Iter<'_, B> {
540        Iter(BlockIter::from_blocks(self.bit_vec.blocks()))
541    }
542
543    /// Iterator over each usize stored in `self` union `other`.
544    /// See [`union_with`] for an efficient in-place version.
545    ///
546    /// # Examples
547    ///
548    /// ```
549    /// use bit_set::BitSet;
550    ///
551    /// let a = BitSet::from_bytes(&[0b01101000]);
552    /// let b = BitSet::from_bytes(&[0b10100000]);
553    ///
554    /// // Print 0, 1, 2, 4 in arbitrary order
555    /// for x in a.union(&b) {
556    ///     println!("{}", x);
557    /// }
558    /// ```
559    ///
560    /// [`union_with`]: Self::union_with
561    #[inline]
562    pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, B> {
563        fn or<B: BitBlock>(w1: B, w2: B) -> B {
564            w1 | w2
565        }
566
567        Union(BlockIter::from_blocks(TwoBitPositions {
568            set: self.bit_vec.blocks(),
569            other: other.bit_vec.blocks(),
570            merge: or,
571        }))
572    }
573
574    /// Iterator over each usize stored in `self` intersect `other`.
575    /// See [`intersect_with`] for an efficient in-place version.
576    ///
577    /// # Examples
578    ///
579    /// ```
580    /// use bit_set::BitSet;
581    ///
582    /// let a = BitSet::from_bytes(&[0b01101000]);
583    /// let b = BitSet::from_bytes(&[0b10100000]);
584    ///
585    /// // Print 2
586    /// for x in a.intersection(&b) {
587    ///     println!("{}", x);
588    /// }
589    /// ```
590    ///
591    /// [`intersect_with`]: Self::intersect_with
592    #[inline]
593    pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, B> {
594        fn bitand<B: BitBlock>(w1: B, w2: B) -> B {
595            w1 & w2
596        }
597        let min = cmp::min(self.bit_vec.len(), other.bit_vec.len());
598
599        Intersection {
600            iter: BlockIter::from_blocks(TwoBitPositions {
601                set: self.bit_vec.blocks(),
602                other: other.bit_vec.blocks(),
603                merge: bitand,
604            }),
605            n: min,
606        }
607    }
608
609    /// Iterator over each usize stored in the `self` setminus `other`.
610    /// See [`difference_with`] for an efficient in-place version.
611    ///
612    /// # Examples
613    ///
614    /// ```
615    /// use bit_set::BitSet;
616    ///
617    /// let a = BitSet::from_bytes(&[0b01101000]);
618    /// let b = BitSet::from_bytes(&[0b10100000]);
619    ///
620    /// // Print 1, 4 in arbitrary order
621    /// for x in a.difference(&b) {
622    ///     println!("{}", x);
623    /// }
624    ///
625    /// // Note that difference is not symmetric,
626    /// // and `b - a` means something else.
627    /// // This prints 0
628    /// for x in b.difference(&a) {
629    ///     println!("{}", x);
630    /// }
631    /// ```
632    ///
633    /// [`difference_with`]: Self::difference_with
634    #[inline]
635    pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, B> {
636        fn diff<B: BitBlock>(w1: B, w2: B) -> B {
637            w1 & !w2
638        }
639
640        Difference(BlockIter::from_blocks(TwoBitPositions {
641            set: self.bit_vec.blocks(),
642            other: other.bit_vec.blocks(),
643            merge: diff,
644        }))
645    }
646
647    /// Iterator over each usize stored in the symmetric difference of `self` and `other`.
648    /// See [`symmetric_difference_with`] for an efficient in-place version.
649    ///
650    /// # Examples
651    ///
652    /// ```
653    /// use bit_set::BitSet;
654    ///
655    /// let a = BitSet::from_bytes(&[0b01101000]);
656    /// let b = BitSet::from_bytes(&[0b10100000]);
657    ///
658    /// // Print 0, 1, 4 in arbitrary order
659    /// for x in a.symmetric_difference(&b) {
660    ///     println!("{}", x);
661    /// }
662    /// ```
663    ///
664    /// [`symmetric_difference_with`]: Self::symmetric_difference_with
665    #[inline]
666    pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, B> {
667        fn bitxor<B: BitBlock>(w1: B, w2: B) -> B {
668            w1 ^ w2
669        }
670
671        SymmetricDifference(BlockIter::from_blocks(TwoBitPositions {
672            set: self.bit_vec.blocks(),
673            other: other.bit_vec.blocks(),
674            merge: bitxor,
675        }))
676    }
677
678    /// Unions in-place with the specified other bit vector.
679    ///
680    /// # Examples
681    ///
682    /// ```
683    /// use bit_set::BitSet;
684    ///
685    /// let a   = 0b01101000;
686    /// let b   = 0b10100000;
687    /// let res = 0b11101000;
688    ///
689    /// let mut a = BitSet::from_bytes(&[a]);
690    /// let b = BitSet::from_bytes(&[b]);
691    /// let res = BitSet::from_bytes(&[res]);
692    ///
693    /// a.union_with(&b);
694    /// assert_eq!(a, res);
695    /// ```
696    #[inline]
697    pub fn union_with(&mut self, other: &Self) {
698        self.other_op(other, |w1, w2| w1 | w2);
699    }
700
701    /// Intersects in-place with the specified other bit vector.
702    ///
703    /// # Examples
704    ///
705    /// ```
706    /// use bit_set::BitSet;
707    ///
708    /// let a   = 0b01101000;
709    /// let b   = 0b10100000;
710    /// let res = 0b00100000;
711    ///
712    /// let mut a = BitSet::from_bytes(&[a]);
713    /// let b = BitSet::from_bytes(&[b]);
714    /// let res = BitSet::from_bytes(&[res]);
715    ///
716    /// a.intersect_with(&b);
717    /// assert_eq!(a, res);
718    /// ```
719    #[inline]
720    pub fn intersect_with(&mut self, other: &Self) {
721        self.other_op(other, |w1, w2| w1 & w2);
722    }
723
724    /// Makes this bit vector the difference with the specified other bit vector
725    /// in-place.
726    ///
727    /// # Examples
728    ///
729    /// ```
730    /// use bit_set::BitSet;
731    ///
732    /// let a   = 0b01101000;
733    /// let b   = 0b10100000;
734    /// let a_b = 0b01001000; // a - b
735    /// let b_a = 0b10000000; // b - a
736    ///
737    /// let mut bva = BitSet::from_bytes(&[a]);
738    /// let bvb = BitSet::from_bytes(&[b]);
739    /// let bva_b = BitSet::from_bytes(&[a_b]);
740    /// let bvb_a = BitSet::from_bytes(&[b_a]);
741    ///
742    /// bva.difference_with(&bvb);
743    /// assert_eq!(bva, bva_b);
744    ///
745    /// let bva = BitSet::from_bytes(&[a]);
746    /// let mut bvb = BitSet::from_bytes(&[b]);
747    ///
748    /// bvb.difference_with(&bva);
749    /// assert_eq!(bvb, bvb_a);
750    /// ```
751    #[inline]
752    pub fn difference_with(&mut self, other: &Self) {
753        self.other_op(other, |w1, w2| w1 & !w2);
754    }
755
756    /// Makes this bit vector the symmetric difference with the specified other
757    /// bit vector in-place.
758    ///
759    /// # Examples
760    ///
761    /// ```
762    /// use bit_set::BitSet;
763    ///
764    /// let a   = 0b01101000;
765    /// let b   = 0b10100000;
766    /// let res = 0b11001000;
767    ///
768    /// let mut a = BitSet::from_bytes(&[a]);
769    /// let b = BitSet::from_bytes(&[b]);
770    /// let res = BitSet::from_bytes(&[res]);
771    ///
772    /// a.symmetric_difference_with(&b);
773    /// assert_eq!(a, res);
774    /// ```
775    #[inline]
776    pub fn symmetric_difference_with(&mut self, other: &Self) {
777        self.other_op(other, |w1, w2| w1 ^ w2);
778    }
779
780    /*
781        /// Moves all elements from `other` into `Self`, leaving `other` empty.
782        ///
783        /// # Examples
784        ///
785        /// ```
786        /// use bit_set::BitSet;
787        ///
788        /// let mut a = BitSet::new();
789        /// a.insert(2);
790        /// a.insert(6);
791        ///
792        /// let mut b = BitSet::new();
793        /// b.insert(1);
794        /// b.insert(3);
795        /// b.insert(6);
796        ///
797        /// a.append(&mut b);
798        ///
799        /// assert_eq!(a.len(), 4);
800        /// assert_eq!(b.len(), 0);
801        /// assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
802        /// ```
803        pub fn append(&mut self, other: &mut Self) {
804            self.union_with(other);
805            other.clear();
806        }
807
808        /// Splits the `BitSet` into two at the given key including the key.
809        /// Retains the first part in-place while returning the second part.
810        ///
811        /// # Examples
812        ///
813        /// ```
814        /// use bit_set::BitSet;
815        ///
816        /// let mut a = BitSet::new();
817        /// a.insert(2);
818        /// a.insert(6);
819        /// a.insert(1);
820        /// a.insert(3);
821        ///
822        /// let b = a.split_off(3);
823        ///
824        /// assert_eq!(a.len(), 2);
825        /// assert_eq!(b.len(), 2);
826        /// assert_eq!(a, BitSet::from_bytes(&[0b01100000]));
827        /// assert_eq!(b, BitSet::from_bytes(&[0b00010010]));
828        /// ```
829        pub fn split_off(&mut self, at: usize) -> Self {
830            let mut other = BitSet::new();
831
832            if at == 0 {
833                swap(self, &mut other);
834                return other;
835            } else if at >= self.bit_vec.len() {
836                return other;
837            }
838
839            // Calculate block and bit at which to split
840            let w = at / BITS;
841            let b = at % BITS;
842
843            // Pad `other` with `w` zero blocks,
844            // append `self`'s blocks in the range from `w` to the end to `other`
845            other.bit_vec.storage_mut().extend(repeat(0u32).take(w)
846                                         .chain(self.bit_vec.storage()[w..].iter().cloned()));
847            other.bit_vec.nbits = self.bit_vec.nbits;
848
849            if b > 0 {
850                other.bit_vec.storage_mut()[w] &= !0 << b;
851            }
852
853            // Sets `bit_vec.len()` and fixes the last block as well
854            self.bit_vec.truncate(at);
855
856            other
857        }
858    */
859
860    /// Counts the number of set bits in this set.
861    ///
862    /// Note that this function scans the set to calculate the number.
863    #[inline]
864    pub fn count(&self) -> usize {
865        self.bit_vec.blocks().fold(0, |acc, n| acc + n.count_ones())
866    }
867
868    /// Counts the number of set bits in this set.
869    ///
870    /// Note that this function scans the set to calculate the number.
871    #[inline]
872    #[deprecated = "use BitSet::count() instead"]
873    pub fn len(&self) -> usize {
874        self.count()
875    }
876
877    /// Returns whether there are no bits set in this set
878    #[inline]
879    pub fn is_empty(&self) -> bool {
880        self.bit_vec.none()
881    }
882
883    /// Removes all elements of this set.
884    ///
885    /// Different from [`reset`] only in that the capacity is preserved.
886    ///
887    /// [`reset`]: Self::reset
888    #[inline]
889    pub fn make_empty(&mut self) {
890        self.bit_vec.fill(false);
891    }
892
893    /// Resets this set to an empty state.
894    ///
895    /// Different from [`make_empty`] only in that the capacity may NOT be preserved.
896    ///
897    /// [`make_empty`]: Self::make_empty
898    #[inline]
899    pub fn reset(&mut self) {
900        self.bit_vec.remove_all();
901    }
902
903    /// Clears all bits in this set
904    #[deprecated(since = "0.9.0", note = "please use `fn make_empty` instead")]
905    #[inline]
906    pub fn clear(&mut self) {
907        self.make_empty();
908    }
909
910    /// Returns `true` if this set contains the specified integer.
911    #[inline]
912    pub fn contains(&self, value: usize) -> bool {
913        let bit_vec = &self.bit_vec;
914        value < bit_vec.len() && bit_vec[value]
915    }
916
917    /// Returns `true` if the set has no elements in common with `other`.
918    /// This is equivalent to checking for an empty intersection.
919    #[inline]
920    pub fn is_disjoint(&self, other: &Self) -> bool {
921        self.intersection(other).next().is_none()
922    }
923
924    /// Returns `true` if the set is a subset of another.
925    #[inline]
926    pub fn is_subset(&self, other: &Self) -> bool {
927        let self_bit_vec = &self.bit_vec;
928        let other_bit_vec = &other.bit_vec;
929        let other_blocks = blocks_for_bits::<B>(other_bit_vec.len());
930
931        // Check that `self` intersect `other` is self
932        self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
933        // Make sure if `self` has any more blocks than `other`, they're all 0
934        self_bit_vec.blocks().skip(other_blocks).all(|w| w == B::zero())
935    }
936
937    /// Returns `true` if the set is a superset of another.
938    #[inline]
939    pub fn is_superset(&self, other: &Self) -> bool {
940        other.is_subset(self)
941    }
942
943    /// Adds a value to the set. Returns `true` if the value was not already
944    /// present in the set.
945    pub fn insert(&mut self, value: usize) -> bool {
946        if self.contains(value) {
947            return false;
948        }
949
950        // Ensure we have enough space to hold the new element
951        let len = self.bit_vec.len();
952        if value >= len {
953            self.bit_vec.grow(value - len + 1, false);
954        }
955
956        self.bit_vec.set(value, true);
957        true
958    }
959
960    /// Removes a value from the set. Returns `true` if the value was
961    /// present in the set.
962    pub fn remove(&mut self, value: usize) -> bool {
963        if !self.contains(value) {
964            return false;
965        }
966
967        self.bit_vec.set(value, false);
968
969        true
970    }
971
972    /// Excludes `element` and all greater elements from the `BitSet`.
973    pub fn truncate(&mut self, element: usize) {
974        self.bit_vec.truncate(element);
975    }
976}
977
978impl<B: BitBlock> fmt::Debug for BitSet<B> {
979    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
980        fmt.debug_struct("BitSet")
981            .field("bit_vec", &self.bit_vec)
982            .finish()
983    }
984}
985
986impl<B: BitBlock> fmt::Display for BitSet<B> {
987    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
988        fmt.debug_set().entries(self).finish()
989    }
990}
991
992impl<B: BitBlock> hash::Hash for BitSet<B> {
993    fn hash<H: hash::Hasher>(&self, state: &mut H) {
994        for pos in self {
995            pos.hash(state);
996        }
997    }
998}
999
1000#[derive(Clone)]
1001struct BlockIter<T, B> {
1002    head: B,
1003    head_offset: usize,
1004    tail: T,
1005}
1006
1007impl<T, B: BitBlock> BlockIter<T, B>
1008where
1009    T: Iterator<Item = B>,
1010{
1011    fn from_blocks(mut blocks: T) -> BlockIter<T, B> {
1012        let h = blocks.next().unwrap_or_else(B::zero);
1013        BlockIter {
1014            tail: blocks,
1015            head: h,
1016            head_offset: 0,
1017        }
1018    }
1019}
1020
1021/// An iterator combining two `BitSet` iterators.
1022#[derive(Clone)]
1023struct TwoBitPositions<'a, B: 'a> {
1024    set: Blocks<'a, B>,
1025    other: Blocks<'a, B>,
1026    merge: fn(B, B) -> B,
1027}
1028
1029/// An iterator for `BitSet`.
1030#[derive(Clone)]
1031pub struct Iter<'a, B: 'a>(BlockIter<Blocks<'a, B>, B>);
1032#[derive(Clone)]
1033pub struct Union<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
1034#[derive(Clone)]
1035pub struct Intersection<'a, B: 'a> {
1036    iter: BlockIter<TwoBitPositions<'a, B>, B>,
1037    // as an optimization, we compute the maximum possible
1038    // number of elements in the intersection, and count it
1039    // down as we return elements. If we reach zero, we can
1040    // stop.
1041    n: usize,
1042}
1043#[derive(Clone)]
1044pub struct Difference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
1045#[derive(Clone)]
1046pub struct SymmetricDifference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
1047
1048impl<T, B: BitBlock> Iterator for BlockIter<T, B>
1049where
1050    T: Iterator<Item = B>,
1051{
1052    type Item = usize;
1053
1054    fn next(&mut self) -> Option<usize> {
1055        while self.head == B::zero() {
1056            match self.tail.next() {
1057                Some(w) => self.head = w,
1058                None => return None,
1059            }
1060            self.head_offset += B::bits();
1061        }
1062
1063        // from the current block, isolate the
1064        // LSB and subtract 1, producing k:
1065        // a block with a number of set bits
1066        // equal to the index of the LSB
1067        let k = (self.head & (!self.head + B::one())) - B::one();
1068        // update block, removing the LSB
1069        self.head = self.head & (self.head - B::one());
1070        // return offset + (index of LSB)
1071        Some(self.head_offset + (B::count_ones(k)))
1072    }
1073
1074    fn count(self) -> usize {
1075        self.head.count_ones() + self.tail.map(|block| block.count_ones()).sum::<usize>()
1076    }
1077
1078    #[inline]
1079    fn size_hint(&self) -> (usize, Option<usize>) {
1080        match self.tail.size_hint() {
1081            (_, Some(h)) => (0, Some((1 + h) * B::bits())),
1082            _ => (0, None),
1083        }
1084    }
1085}
1086
1087impl<B: BitBlock> Iterator for TwoBitPositions<'_, B> {
1088    type Item = B;
1089
1090    fn next(&mut self) -> Option<B> {
1091        match (self.set.next(), self.other.next()) {
1092            (Some(a), Some(b)) => Some((self.merge)(a, b)),
1093            (Some(a), None) => Some((self.merge)(a, B::zero())),
1094            (None, Some(b)) => Some((self.merge)(B::zero(), b)),
1095            _ => None,
1096        }
1097    }
1098
1099    #[inline]
1100    fn size_hint(&self) -> (usize, Option<usize>) {
1101        let (first_lower_bound, first_upper_bound) = self.set.size_hint();
1102        let (second_lower_bound, second_upper_bound) = self.other.size_hint();
1103
1104        let upper_bound = first_upper_bound.zip(second_upper_bound);
1105
1106        let get_max = |(a, b)| cmp::max(a, b);
1107        (
1108            cmp::max(first_lower_bound, second_lower_bound),
1109            upper_bound.map(get_max),
1110        )
1111    }
1112}
1113
1114impl<B: BitBlock> Iterator for Iter<'_, B> {
1115    type Item = usize;
1116
1117    #[inline]
1118    fn next(&mut self) -> Option<usize> {
1119        self.0.next()
1120    }
1121    #[inline]
1122    fn size_hint(&self) -> (usize, Option<usize>) {
1123        self.0.size_hint()
1124    }
1125    #[inline]
1126    fn count(self) -> usize {
1127        self.0.count()
1128    }
1129}
1130
1131impl<B: BitBlock> Iterator for Union<'_, B> {
1132    type Item = usize;
1133
1134    #[inline]
1135    fn next(&mut self) -> Option<usize> {
1136        self.0.next()
1137    }
1138    #[inline]
1139    fn size_hint(&self) -> (usize, Option<usize>) {
1140        self.0.size_hint()
1141    }
1142    #[inline]
1143    fn count(self) -> usize {
1144        self.0.count()
1145    }
1146}
1147
1148impl<B: BitBlock> Iterator for Intersection<'_, B> {
1149    type Item = usize;
1150
1151    #[inline]
1152    fn next(&mut self) -> Option<usize> {
1153        if self.n != 0 {
1154            self.n -= 1;
1155            self.iter.next()
1156        } else {
1157            None
1158        }
1159    }
1160    #[inline]
1161    fn size_hint(&self) -> (usize, Option<usize>) {
1162        // We could invoke self.iter.size_hint() and incorporate that into the hint.
1163        // In practice, that does not seem worthwhile because the lower bound will
1164        // always be zero and the upper bound could only possibly less then n in a
1165        // partially iterated iterator. However, it makes little sense ask for size_hint
1166        // in a partially iterated iterator, so it did not seem worthwhile.
1167        (0, Some(self.n))
1168    }
1169    #[inline]
1170    fn count(self) -> usize {
1171        self.iter.count()
1172    }
1173}
1174
1175impl<B: BitBlock> Iterator for Difference<'_, B> {
1176    type Item = usize;
1177
1178    #[inline]
1179    fn next(&mut self) -> Option<usize> {
1180        self.0.next()
1181    }
1182    #[inline]
1183    fn size_hint(&self) -> (usize, Option<usize>) {
1184        self.0.size_hint()
1185    }
1186    #[inline]
1187    fn count(self) -> usize {
1188        self.0.count()
1189    }
1190}
1191
1192impl<B: BitBlock> Iterator for SymmetricDifference<'_, B> {
1193    type Item = usize;
1194
1195    #[inline]
1196    fn next(&mut self) -> Option<usize> {
1197        self.0.next()
1198    }
1199    #[inline]
1200    fn size_hint(&self) -> (usize, Option<usize>) {
1201        self.0.size_hint()
1202    }
1203    #[inline]
1204    fn count(self) -> usize {
1205        self.0.count()
1206    }
1207}
1208
1209impl<'a, B: BitBlock> IntoIterator for &'a BitSet<B> {
1210    type Item = usize;
1211    type IntoIter = Iter<'a, B>;
1212
1213    fn into_iter(self) -> Iter<'a, B> {
1214        self.iter()
1215    }
1216}
1217
1218#[cfg(test)]
1219mod tests {
1220    #![allow(clippy::shadow_reuse)]
1221    #![allow(clippy::shadow_same)]
1222    #![allow(clippy::shadow_unrelated)]
1223
1224    use super::BitSet;
1225    use bit_vec::BitVec;
1226    use std::cmp::Ordering::{Equal, Greater, Less};
1227    use std::vec::Vec;
1228    use std::{format, vec};
1229
1230    #[test]
1231    fn test_bit_set_display() {
1232        let mut s = BitSet::new();
1233        s.insert(1);
1234        s.insert(10);
1235        s.insert(50);
1236        s.insert(2);
1237        assert_eq!("{1, 2, 10, 50}", format!("{}", s));
1238    }
1239
1240    #[test]
1241    fn test_bit_set_debug() {
1242        let mut s = BitSet::new();
1243        s.insert(1);
1244        s.insert(10);
1245        s.insert(50);
1246        s.insert(2);
1247        let expected = "BitSet { bit_vec: BitVec { storage: \
1248        \"01100000001000000000000000000000 \
1249        0000000000000000001\", nbits: 51 } }";
1250        let actual = format!("{:?}", s);
1251        assert_eq!(expected, actual);
1252    }
1253
1254    #[test]
1255    fn test_bit_set_from_usizes() {
1256        let usizes = vec![0, 2, 2, 3];
1257        let a: BitSet = usizes.into_iter().collect();
1258        let mut b = BitSet::new();
1259        b.insert(0);
1260        b.insert(2);
1261        b.insert(3);
1262        assert_eq!(a, b);
1263    }
1264
1265    #[test]
1266    fn test_bit_set_iterator() {
1267        let usizes = vec![0, 2, 2, 3];
1268        let bit_vec: BitSet = usizes.into_iter().collect();
1269
1270        let idxs: Vec<_> = bit_vec.iter().collect();
1271        assert_eq!(idxs, [0, 2, 3]);
1272        assert_eq!(bit_vec.iter().count(), 3);
1273
1274        let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect();
1275        let real: Vec<_> = (0..10000 / 2).map(|x| x * 2).collect();
1276
1277        let idxs: Vec<_> = long.iter().collect();
1278        assert_eq!(idxs, real);
1279        assert_eq!(long.iter().count(), real.len());
1280    }
1281
1282    #[test]
1283    fn test_bit_set_frombit_vec_init() {
1284        let bools = [true, false];
1285        let lengths = [10, 64, 100];
1286        for &b in &bools {
1287            for &l in &lengths {
1288                let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
1289                assert_eq!(bitset.contains(1), b);
1290                assert_eq!(bitset.contains(l - 1), b);
1291                assert!(!bitset.contains(l));
1292            }
1293        }
1294    }
1295
1296    #[test]
1297    fn test_bit_vec_masking() {
1298        let b = BitVec::from_elem(140, true);
1299        let mut bs = BitSet::from_bit_vec(b);
1300        assert!(bs.contains(139));
1301        assert!(!bs.contains(140));
1302        assert!(bs.insert(150));
1303        assert!(!bs.contains(140));
1304        assert!(!bs.contains(149));
1305        assert!(bs.contains(150));
1306        assert!(!bs.contains(151));
1307    }
1308
1309    #[test]
1310    fn test_bit_set_basic() {
1311        let mut b = BitSet::new();
1312        assert!(b.insert(3));
1313        assert!(!b.insert(3));
1314        assert!(b.contains(3));
1315        assert!(b.insert(4));
1316        assert!(!b.insert(4));
1317        assert!(b.contains(3));
1318        assert!(b.insert(400));
1319        assert!(!b.insert(400));
1320        assert!(b.contains(400));
1321        assert_eq!(b.count(), 3);
1322    }
1323
1324    #[test]
1325    fn test_bit_set_intersection() {
1326        let mut a = BitSet::new();
1327        let mut b = BitSet::new();
1328
1329        assert!(a.insert(11));
1330        assert!(a.insert(1));
1331        assert!(a.insert(3));
1332        assert!(a.insert(77));
1333        assert!(a.insert(103));
1334        assert!(a.insert(5));
1335
1336        assert!(b.insert(2));
1337        assert!(b.insert(11));
1338        assert!(b.insert(77));
1339        assert!(b.insert(5));
1340        assert!(b.insert(3));
1341
1342        let expected = [3, 5, 11, 77];
1343        let actual: Vec<_> = a.intersection(&b).collect();
1344        assert_eq!(actual, expected);
1345        assert_eq!(a.intersection(&b).count(), expected.len());
1346    }
1347
1348    #[test]
1349    fn test_bit_set_difference() {
1350        let mut a = BitSet::new();
1351        let mut b = BitSet::new();
1352
1353        assert!(a.insert(1));
1354        assert!(a.insert(3));
1355        assert!(a.insert(5));
1356        assert!(a.insert(200));
1357        assert!(a.insert(500));
1358
1359        assert!(b.insert(3));
1360        assert!(b.insert(200));
1361
1362        let expected = [1, 5, 500];
1363        let actual: Vec<_> = a.difference(&b).collect();
1364        assert_eq!(actual, expected);
1365        assert_eq!(a.difference(&b).count(), expected.len());
1366    }
1367
1368    #[test]
1369    fn test_bit_set_symmetric_difference() {
1370        let mut a = BitSet::new();
1371        let mut b = BitSet::new();
1372
1373        assert!(a.insert(1));
1374        assert!(a.insert(3));
1375        assert!(a.insert(5));
1376        assert!(a.insert(9));
1377        assert!(a.insert(11));
1378
1379        assert!(b.insert(3));
1380        assert!(b.insert(9));
1381        assert!(b.insert(14));
1382        assert!(b.insert(220));
1383
1384        let expected = [1, 5, 11, 14, 220];
1385        let actual: Vec<_> = a.symmetric_difference(&b).collect();
1386        assert_eq!(actual, expected);
1387        assert_eq!(a.symmetric_difference(&b).count(), expected.len());
1388    }
1389
1390    #[test]
1391    fn test_bit_set_union() {
1392        let mut a = BitSet::new();
1393        let mut b = BitSet::new();
1394        assert!(a.insert(1));
1395        assert!(a.insert(3));
1396        assert!(a.insert(5));
1397        assert!(a.insert(9));
1398        assert!(a.insert(11));
1399        assert!(a.insert(160));
1400        assert!(a.insert(19));
1401        assert!(a.insert(24));
1402        assert!(a.insert(200));
1403
1404        assert!(b.insert(1));
1405        assert!(b.insert(5));
1406        assert!(b.insert(9));
1407        assert!(b.insert(13));
1408        assert!(b.insert(19));
1409
1410        let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
1411        let actual: Vec<_> = a.union(&b).collect();
1412        assert_eq!(actual, expected);
1413        assert_eq!(a.union(&b).count(), expected.len());
1414    }
1415
1416    #[test]
1417    fn test_bit_set_subset() {
1418        let mut set1 = BitSet::new();
1419        let mut set2 = BitSet::new();
1420
1421        assert!(set1.is_subset(&set2)); //  {}  {}
1422        set2.insert(100);
1423        assert!(set1.is_subset(&set2)); //  {}  { 1 }
1424        set2.insert(200);
1425        assert!(set1.is_subset(&set2)); //  {}  { 1, 2 }
1426        set1.insert(200);
1427        assert!(set1.is_subset(&set2)); //  { 2 }  { 1, 2 }
1428        set1.insert(300);
1429        assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 1, 2 }
1430        set2.insert(300);
1431        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3 }
1432        set2.insert(400);
1433        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3, 4 }
1434        set2.remove(100);
1435        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 2, 3, 4 }
1436        set2.remove(300);
1437        assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 2, 4 }
1438        set1.remove(300);
1439        assert!(set1.is_subset(&set2)); // { 2 }  { 2, 4 }
1440    }
1441
1442    #[test]
1443    fn test_bit_set_is_disjoint() {
1444        let a = BitSet::from_bytes(&[0b10100010]);
1445        let b = BitSet::from_bytes(&[0b01000000]);
1446        let c = BitSet::new();
1447        let d = BitSet::from_bytes(&[0b00110000]);
1448
1449        assert!(!a.is_disjoint(&d));
1450        assert!(!d.is_disjoint(&a));
1451
1452        assert!(a.is_disjoint(&b));
1453        assert!(a.is_disjoint(&c));
1454        assert!(b.is_disjoint(&a));
1455        assert!(b.is_disjoint(&c));
1456        assert!(c.is_disjoint(&a));
1457        assert!(c.is_disjoint(&b));
1458    }
1459
1460    #[test]
1461    fn test_bit_set_union_with() {
1462        //a should grow to include larger elements
1463        let mut a = BitSet::new();
1464        a.insert(0);
1465        let mut b = BitSet::new();
1466        b.insert(5);
1467        let expected = BitSet::from_bytes(&[0b10000100]);
1468        a.union_with(&b);
1469        assert_eq!(a, expected);
1470
1471        // Standard
1472        let mut a = BitSet::from_bytes(&[0b10100010]);
1473        let mut b = BitSet::from_bytes(&[0b01100010]);
1474        let c = a.clone();
1475        a.union_with(&b);
1476        b.union_with(&c);
1477        assert_eq!(a.count(), 4);
1478        assert_eq!(b.count(), 4);
1479    }
1480
1481    #[test]
1482    fn test_bit_set_intersect_with() {
1483        // Explicitly 0'ed bits
1484        let mut a = BitSet::from_bytes(&[0b10100010]);
1485        let mut b = BitSet::from_bytes(&[0b00000000]);
1486        let c = a.clone();
1487        a.intersect_with(&b);
1488        b.intersect_with(&c);
1489        assert!(a.is_empty());
1490        assert!(b.is_empty());
1491
1492        // Uninitialized bits should behave like 0's
1493        let mut a = BitSet::from_bytes(&[0b10100010]);
1494        let mut b = BitSet::new();
1495        let c = a.clone();
1496        a.intersect_with(&b);
1497        b.intersect_with(&c);
1498        assert!(a.is_empty());
1499        assert!(b.is_empty());
1500
1501        // Standard
1502        let mut a = BitSet::from_bytes(&[0b10100010]);
1503        let mut b = BitSet::from_bytes(&[0b01100010]);
1504        let c = a.clone();
1505        a.intersect_with(&b);
1506        b.intersect_with(&c);
1507        assert_eq!(a.count(), 2);
1508        assert_eq!(b.count(), 2);
1509    }
1510
1511    #[test]
1512    fn test_bit_set_difference_with() {
1513        // Explicitly 0'ed bits
1514        let mut a = BitSet::from_bytes(&[0b00000000]);
1515        let b = BitSet::from_bytes(&[0b10100010]);
1516        a.difference_with(&b);
1517        assert!(a.is_empty());
1518
1519        // Uninitialized bits should behave like 0's
1520        let mut a = BitSet::new();
1521        let b = BitSet::from_bytes(&[0b11111111]);
1522        a.difference_with(&b);
1523        assert!(a.is_empty());
1524
1525        // Standard
1526        let mut a = BitSet::from_bytes(&[0b10100010]);
1527        let mut b = BitSet::from_bytes(&[0b01100010]);
1528        let c = a.clone();
1529        a.difference_with(&b);
1530        b.difference_with(&c);
1531        assert_eq!(a.count(), 1);
1532        assert_eq!(b.count(), 1);
1533    }
1534
1535    #[test]
1536    fn test_bit_set_symmetric_difference_with() {
1537        //a should grow to include larger elements
1538        let mut a = BitSet::new();
1539        a.insert(0);
1540        a.insert(1);
1541        let mut b = BitSet::new();
1542        b.insert(1);
1543        b.insert(5);
1544        let expected = BitSet::from_bytes(&[0b10000100]);
1545        a.symmetric_difference_with(&b);
1546        assert_eq!(a, expected);
1547
1548        let mut a = BitSet::from_bytes(&[0b10100010]);
1549        let b = BitSet::new();
1550        let c = a.clone();
1551        a.symmetric_difference_with(&b);
1552        assert_eq!(a, c);
1553
1554        // Standard
1555        let mut a = BitSet::from_bytes(&[0b11100010]);
1556        let mut b = BitSet::from_bytes(&[0b01101010]);
1557        let c = a.clone();
1558        a.symmetric_difference_with(&b);
1559        b.symmetric_difference_with(&c);
1560        assert_eq!(a.count(), 2);
1561        assert_eq!(b.count(), 2);
1562    }
1563
1564    #[test]
1565    fn test_bit_set_eq() {
1566        let a = BitSet::from_bytes(&[0b10100010]);
1567        let b = BitSet::from_bytes(&[0b00000000]);
1568        let c = BitSet::new();
1569
1570        assert!(a == a);
1571        assert!(a != b);
1572        assert!(a != c);
1573        assert!(b == b);
1574        assert!(b == c);
1575        assert!(c == c);
1576    }
1577
1578    #[test]
1579    fn test_bit_set_cmp() {
1580        let a = BitSet::from_bytes(&[0b10100010]);
1581        let b = BitSet::from_bytes(&[0b00000000]);
1582        let c = BitSet::new();
1583
1584        assert_eq!(a.cmp(&b), Greater);
1585        assert_eq!(a.cmp(&c), Greater);
1586        assert_eq!(b.cmp(&a), Less);
1587        assert_eq!(b.cmp(&c), Equal);
1588        assert_eq!(c.cmp(&a), Less);
1589        assert_eq!(c.cmp(&b), Equal);
1590    }
1591
1592    #[test]
1593    fn test_bit_set_shrink_to_fit_new() {
1594        // There was a strange bug where we refused to truncate to 0
1595        // and this would end up actually growing the array in a way
1596        // that (safely corrupted the state).
1597        let mut a = BitSet::new();
1598        assert_eq!(a.count(), 0);
1599        assert_eq!(a.capacity(), 0);
1600        a.shrink_to_fit();
1601        assert_eq!(a.count(), 0);
1602        assert_eq!(a.capacity(), 0);
1603        assert!(!a.contains(1));
1604        a.insert(3);
1605        assert!(a.contains(3));
1606        assert_eq!(a.count(), 1);
1607        assert!(a.capacity() > 0);
1608        a.shrink_to_fit();
1609        assert!(a.contains(3));
1610        assert_eq!(a.count(), 1);
1611        assert!(a.capacity() > 0);
1612    }
1613
1614    #[test]
1615    fn test_bit_set_shrink_to_fit() {
1616        let mut a = BitSet::new();
1617        assert_eq!(a.count(), 0);
1618        assert_eq!(a.capacity(), 0);
1619        a.insert(259);
1620        a.insert(98);
1621        a.insert(3);
1622        assert_eq!(a.count(), 3);
1623        assert!(a.capacity() > 0);
1624        assert!(!a.contains(1));
1625        assert!(a.contains(259));
1626        assert!(a.contains(98));
1627        assert!(a.contains(3));
1628
1629        a.shrink_to_fit();
1630        assert!(!a.contains(1));
1631        assert!(a.contains(259));
1632        assert!(a.contains(98));
1633        assert!(a.contains(3));
1634        assert_eq!(a.count(), 3);
1635        assert!(a.capacity() > 0);
1636
1637        let old_cap = a.capacity();
1638        assert!(a.remove(259));
1639        a.shrink_to_fit();
1640        assert!(a.capacity() < old_cap, "{} {}", a.capacity(), old_cap);
1641        assert!(!a.contains(1));
1642        assert!(!a.contains(259));
1643        assert!(a.contains(98));
1644        assert!(a.contains(3));
1645        assert_eq!(a.count(), 2);
1646
1647        let old_cap2 = a.capacity();
1648        a.make_empty();
1649        assert_eq!(a.capacity(), old_cap2);
1650        assert_eq!(a.count(), 0);
1651        assert!(!a.contains(1));
1652        assert!(!a.contains(259));
1653        assert!(!a.contains(98));
1654        assert!(!a.contains(3));
1655
1656        a.insert(512);
1657        assert!(a.capacity() > 0);
1658        assert_eq!(a.count(), 1);
1659        assert!(a.contains(512));
1660        assert!(!a.contains(1));
1661        assert!(!a.contains(259));
1662        assert!(!a.contains(98));
1663        assert!(!a.contains(3));
1664
1665        a.remove(512);
1666        a.shrink_to_fit();
1667        assert_eq!(a.capacity(), 0);
1668        assert_eq!(a.count(), 0);
1669        assert!(!a.contains(512));
1670        assert!(!a.contains(1));
1671        assert!(!a.contains(259));
1672        assert!(!a.contains(98));
1673        assert!(!a.contains(3));
1674        assert!(!a.contains(0));
1675    }
1676
1677    #[test]
1678    fn test_bit_vec_remove() {
1679        let mut a = BitSet::new();
1680
1681        assert!(a.insert(1));
1682        assert!(a.remove(1));
1683
1684        assert!(a.insert(100));
1685        assert!(a.remove(100));
1686
1687        assert!(a.insert(1000));
1688        assert!(a.remove(1000));
1689        a.shrink_to_fit();
1690    }
1691
1692    #[test]
1693    fn test_bit_vec_clone() {
1694        let mut a = BitSet::new();
1695
1696        assert!(a.insert(1));
1697        assert!(a.insert(100));
1698        assert!(a.insert(1000));
1699
1700        let mut b = a.clone();
1701
1702        assert!(a == b);
1703
1704        assert!(b.remove(1));
1705        assert!(a.contains(1));
1706
1707        assert!(a.remove(1000));
1708        assert!(b.contains(1000));
1709    }
1710
1711    #[test]
1712    fn test_truncate() {
1713        let bytes = [0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF];
1714
1715        let mut s = BitSet::from_bytes(&bytes);
1716        s.truncate(5 * 8);
1717
1718        assert_eq!(s, BitSet::from_bytes(&bytes[..5]));
1719        assert_eq!(s.count(), 5 * 8);
1720        s.truncate(4 * 8);
1721        assert_eq!(s, BitSet::from_bytes(&bytes[..4]));
1722        assert_eq!(s.count(), 4 * 8);
1723        // Truncating to a size > s.len() should be a noop
1724        s.truncate(5 * 8);
1725        assert_eq!(s, BitSet::from_bytes(&bytes[..4]));
1726        assert_eq!(s.count(), 4 * 8);
1727        s.truncate(8);
1728        assert_eq!(s, BitSet::from_bytes(&bytes[..1]));
1729        assert_eq!(s.count(), 8);
1730        s.truncate(0);
1731        assert_eq!(s, BitSet::from_bytes(&[]));
1732        assert_eq!(s.count(), 0);
1733    }
1734
1735    #[cfg(feature = "serde")]
1736    #[test]
1737    fn test_serialization() {
1738        let bset: BitSet = BitSet::new();
1739        let serialized = serde_json::to_string(&bset).unwrap();
1740        let unserialized: BitSet = serde_json::from_str(&serialized).unwrap();
1741        assert_eq!(bset, unserialized);
1742
1743        let elems: Vec<usize> = vec![11, 42, 100, 101];
1744        let bset: BitSet = elems.iter().map(|n| *n).collect();
1745        let serialized = serde_json::to_string(&bset).unwrap();
1746        let unserialized = serde_json::from_str(&serialized).unwrap();
1747        assert_eq!(bset, unserialized);
1748    }
1749
1750    #[cfg(feature = "miniserde")]
1751    #[test]
1752    fn test_miniserde_serialization() {
1753        let bset: BitSet = BitSet::new();
1754        let serialized = miniserde::json::to_string(&bset);
1755        let unserialized: BitSet = miniserde::json::from_str(&serialized[..]).unwrap();
1756        assert_eq!(bset, unserialized);
1757
1758        let elems: Vec<usize> = vec![11, 42, 100, 101];
1759        let bset: BitSet = elems.iter().map(|n| *n).collect();
1760        let serialized = miniserde::json::to_string(&bset);
1761        let unserialized = miniserde::json::from_str(&serialized[..]).unwrap();
1762        assert_eq!(bset, unserialized);
1763    }
1764
1765    #[cfg(feature = "nanoserde")]
1766    #[test]
1767    fn test_nanoserde_json_serialization() {
1768        use nanoserde::{DeJson, SerJson};
1769
1770        let bset: BitSet = BitSet::new();
1771        let serialized = bset.serialize_json();
1772        let unserialized: BitSet = BitSet::deserialize_json(&serialized[..]).unwrap();
1773        assert_eq!(bset, unserialized);
1774
1775        let elems: Vec<usize> = vec![11, 42, 100, 101];
1776        let bset: BitSet = elems.iter().map(|n| *n).collect();
1777        let serialized = bset.serialize_json();
1778        let unserialized = BitSet::deserialize_json(&serialized[..]).unwrap();
1779        assert_eq!(bset, unserialized);
1780    }
1781
1782    #[cfg(feature = "borsh")]
1783    #[test]
1784    fn test_borsh_serialization() {
1785        let bset: BitSet = BitSet::new();
1786        let serialized = borsh::to_vec(&bset).unwrap();
1787        let unserialized: BitSet = borsh::from_slice(&serialized[..]).unwrap();
1788        assert_eq!(bset, unserialized);
1789
1790        let elems: Vec<usize> = vec![11, 42, 100, 101];
1791        let bset: BitSet = elems.iter().map(|n| *n).collect();
1792        let serialized = borsh::to_vec(&bset).unwrap();
1793        let unserialized = borsh::from_slice(&serialized[..]).unwrap();
1794        assert_eq!(bset, unserialized);
1795    }
1796
1797    /*
1798        #[test]
1799        fn test_bit_set_append() {
1800            let mut a = BitSet::new();
1801            a.insert(2);
1802            a.insert(6);
1803
1804            let mut b = BitSet::new();
1805            b.insert(1);
1806            b.insert(3);
1807            b.insert(6);
1808
1809            a.append(&mut b);
1810
1811            assert_eq!(a.len(), 4);
1812            assert_eq!(b.len(), 0);
1813            assert!(b.capacity() >= 6);
1814
1815            assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
1816        }
1817
1818        #[test]
1819        fn test_bit_set_split_off() {
1820            // Split at 0
1821            let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1822                                             0b00110011, 0b01101011, 0b10101101]);
1823
1824            let b = a.split_off(0);
1825
1826            assert_eq!(a.len(), 0);
1827            assert_eq!(b.len(), 21);
1828
1829            assert_eq!(b, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1830                                               0b00110011, 0b01101011, 0b10101101]);
1831
1832            // Split behind last element
1833            let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1834                                             0b00110011, 0b01101011, 0b10101101]);
1835
1836            let b = a.split_off(50);
1837
1838            assert_eq!(a.len(), 21);
1839            assert_eq!(b.len(), 0);
1840
1841            assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1842                                               0b00110011, 0b01101011, 0b10101101]));
1843
1844            // Split at arbitrary element
1845            let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1846                                             0b00110011, 0b01101011, 0b10101101]);
1847
1848            let b = a.split_off(34);
1849
1850            assert_eq!(a.len(), 12);
1851            assert_eq!(b.len(), 9);
1852
1853            assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1854                                               0b00110011, 0b01000000]));
1855            assert_eq!(b, BitSet::from_bytes(&[0, 0, 0, 0,
1856                                               0b00101011, 0b10101101]));
1857        }
1858    */
1859}
bit_set/lib.rs

bit_set/
lib.rs
