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

bit_set/
lib.rs
