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

bit_set_omnitool/
lib.rs
