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.
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.
11 //! An implementation of a set using a bit vector as an underlying
12 //! representation for holding unsigned numerical elements.
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
21 //! use bit_set::BitSet;
23 //! // It's a regular set
24 //! let mut s = BitSet::new();
31 //! if !s.contains(&7) {
32 //! println!("There is no 7");
35 //! // Can initialize from a `BitVec`
36 //! let other = BitSet::from_bytes(&[0b11010000]);
38 //! s.union_with(&other);
40 //! // Print 0, 1, 3 in some order
41 //! for x in s.iter() {
42 //! println!("{}", x);
45 //! // Can convert back to a `BitVec`
46 //! let bv = s.into_bit_vec();
50 #![cfg_attr(all(test, feature = "nightly"), feature(test))]
51 #[cfg(all(test, feature = "nightly"))] extern crate test;
52 #[cfg(all(test, feature = "nightly"))] extern crate rand;
55 use bit_vec::{BitVec, Blocks, BitBlock};
56 use std::cmp::Ordering;
60 use std::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat};
61 use std::iter::{self, FromIterator};
63 type MatchWords<'a, B> = Chain<Enumerate<Blocks<'a, B>>, Skip<Take<Enumerate<Repeat<B>>>>>;
65 /// Computes how many blocks are needed to store that many bits
66 fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
67 // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
68 // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
69 // one too many. So we need to check if that's the case. We can do that by computing if
70 // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
71 // superior modulo operator on a power of two to this.
73 // Note that we can technically avoid this branch with the expression
74 // `(nbits + BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
75 if bits % B::bits() == 0 {
82 // Take two BitVec's, and return iterators of their words, where the shorter one
83 // has been padded with 0's
84 fn match_words<'a,'b, B: BitBlock>(a: &'a BitVec<B>, b: &'b BitVec<B>)
85 -> (MatchWords<'a, B>, MatchWords<'b, B>) {
86 let a_len = a.storage().len();
87 let b_len = b.storage().len();
89 // have to uselessly pretend to pad the longer one for type matching
91 (a.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(b_len).skip(a_len)),
92 b.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)))
94 (a.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)),
95 b.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(a_len).skip(b_len)))
99 pub struct BitSet<B=u32> {
103 impl<B: BitBlock> Clone for BitSet<B> {
104 fn clone(&self) -> Self {
106 bit_vec: self.bit_vec.clone(),
111 impl<B: BitBlock> Default for BitSet<B> {
113 fn default() -> Self { BitSet { bit_vec: Default::default() } }
116 impl<B: BitBlock> FromIterator<usize> for BitSet<B> {
117 fn from_iter<I: IntoIterator<Item=usize>>(iter: I) -> Self {
118 let mut ret: Self = Default::default();
124 impl<B: BitBlock> Extend<usize> for BitSet<B> {
126 fn extend<I: IntoIterator<Item=usize>>(&mut self, iter: I) {
133 impl<B: BitBlock> PartialOrd for BitSet<B> {
135 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
136 Some(self.cmp(other))
140 impl<B: BitBlock> Ord for BitSet<B> {
142 fn cmp(&self, other: &Self) -> Ordering {
143 let mut a = self.iter();
144 let mut b = other.iter();
146 match (a.next(), b.next()) {
147 (Some(x), Some(y)) => match x.cmp(&y) {
148 Ordering::Equal => {}
149 otherwise => return otherwise,
151 (None, None) => return Ordering::Equal,
152 (None, _) => return Ordering::Less,
153 (_, None) => return Ordering::Greater,
159 impl<B: BitBlock> cmp::PartialEq for BitSet<B> {
161 fn eq(&self, other: &Self) -> bool {
162 self.cmp(other) == Ordering::Equal
166 impl<B: BitBlock> cmp::Eq for BitSet<B> {}
169 /// Creates a new empty `BitSet`.
174 /// use bit_set::BitSet;
176 /// let mut s = BitSet::new();
179 pub fn new() -> Self {
183 /// Creates a new `BitSet` with initially no contents, able to
184 /// hold `nbits` elements without resizing.
189 /// use bit_set::BitSet;
191 /// let mut s = BitSet::with_capacity(100);
192 /// assert!(s.capacity() >= 100);
195 pub fn with_capacity(nbits: usize) -> Self {
196 let bit_vec = BitVec::from_elem(nbits, false);
197 BitSet::from_bit_vec(bit_vec)
200 /// Creates a new `BitSet` from the given bit vector.
205 /// extern crate bit_vec;
206 /// extern crate bit_set;
209 /// use bit_vec::BitVec;
210 /// use bit_set::BitSet;
212 /// let bv = BitVec::from_bytes(&[0b01100000]);
213 /// let s = BitSet::from_bit_vec(bv);
215 /// // Print 1, 2 in arbitrary order
216 /// for x in s.iter() {
217 /// println!("{}", x);
222 pub fn from_bit_vec(bit_vec: BitVec) -> Self {
223 BitSet { bit_vec: bit_vec }
226 pub fn from_bytes(bytes: &[u8]) -> Self {
227 BitSet { bit_vec: BitVec::from_bytes(bytes) }
231 impl<B: BitBlock> BitSet<B> {
233 /// Returns the capacity in bits for this bit vector. Inserting any
234 /// element less than this amount will not trigger a resizing.
239 /// use bit_set::BitSet;
241 /// let mut s = BitSet::with_capacity(100);
242 /// assert!(s.capacity() >= 100);
245 pub fn capacity(&self) -> usize {
246 self.bit_vec.capacity()
249 /// Reserves capacity for the given `BitSet` to contain `len` distinct elements. In the case
250 /// of `BitSet` this means reallocations will not occur as long as all inserted elements
251 /// are less than `len`.
253 /// The collection may reserve more space to avoid frequent reallocations.
259 /// use bit_set::BitSet;
261 /// let mut s = BitSet::new();
262 /// s.reserve_len(10);
263 /// assert!(s.capacity() >= 10);
265 pub fn reserve_len(&mut self, len: usize) {
266 let cur_len = self.bit_vec.len();
268 self.bit_vec.reserve(len - cur_len);
272 /// Reserves the minimum capacity for the given `BitSet` to contain `len` distinct elements.
273 /// In the case of `BitSet` this means reallocations will not occur as long as all inserted
274 /// elements are less than `len`.
276 /// Note that the allocator may give the collection more space than it requests. Therefore
277 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve_len` if future
278 /// insertions are expected.
284 /// use bit_set::BitSet;
286 /// let mut s = BitSet::new();
287 /// s.reserve_len_exact(10);
288 /// assert!(s.capacity() >= 10);
290 pub fn reserve_len_exact(&mut self, len: usize) {
291 let cur_len = self.bit_vec.len();
293 self.bit_vec.reserve_exact(len - cur_len);
298 /// Consumes this set to return the underlying bit vector.
303 /// use bit_set::BitSet;
305 /// let mut s = BitSet::new();
309 /// let bv = s.into_bit_vec();
314 pub fn into_bit_vec(self) -> BitVec<B> {
318 /// Returns a reference to the underlying bit vector.
323 /// use bit_set::BitSet;
325 /// let mut s = BitSet::new();
328 /// let bv = s.get_ref();
329 /// assert_eq!(bv[0], true);
332 pub fn get_ref(&self) -> &BitVec<B> {
337 fn other_op<F>(&mut self, other: &Self, mut f: F) where F: FnMut(B, B) -> B {
339 let self_bit_vec = &mut self.bit_vec;
340 let other_bit_vec = &other.bit_vec;
342 let self_len = self_bit_vec.len();
343 let other_len = other_bit_vec.len();
345 // Expand the vector if necessary
346 if self_len < other_len {
347 self_bit_vec.grow(other_len - self_len, false);
350 // virtually pad other with 0's for equal lengths
352 let (_, result) = match_words(self_bit_vec, other_bit_vec);
356 // Apply values found in other
357 for (i, w) in other_words {
358 let old = self_bit_vec.storage()[i];
361 self_bit_vec.storage_mut()[i] = new;
366 /// Truncates the underlying vector to the least length required.
371 /// use bit_set::BitSet;
373 /// let mut s = BitSet::new();
374 /// s.insert(32183231);
375 /// s.remove(&32183231);
377 /// // Internal storage will probably be bigger than necessary
378 /// println!("old capacity: {}", s.capacity());
380 /// // Now should be smaller
381 /// s.shrink_to_fit();
382 /// println!("new capacity: {}", s.capacity());
385 pub fn shrink_to_fit(&mut self) {
386 let bit_vec = &mut self.bit_vec;
387 // Obtain original length
388 let old_len = bit_vec.storage().len();
389 // Obtain coarse trailing zero length
390 let n = bit_vec.storage().iter().rev().take_while(|&&n| n == B::zero()).count();
392 let trunc_len = cmp::max(old_len - n, 1);
394 bit_vec.storage_mut().truncate(trunc_len);
395 bit_vec.set_len(trunc_len * B::bits());
399 /// Iterator over each usize stored in the `BitSet`.
404 /// use bit_set::BitSet;
406 /// let s = BitSet::from_bytes(&[0b01001010]);
408 /// // Print 1, 4, 6 in arbitrary order
409 /// for x in s.iter() {
410 /// println!("{}", x);
414 pub fn iter(&self) -> Iter<B> {
415 Iter(BlockIter::from_blocks(self.bit_vec.blocks()))
418 /// Iterator over each usize stored in `self` union `other`.
419 /// See [union_with](#method.union_with) for an efficient in-place version.
424 /// use bit_set::BitSet;
426 /// let a = BitSet::from_bytes(&[0b01101000]);
427 /// let b = BitSet::from_bytes(&[0b10100000]);
429 /// // Print 0, 1, 2, 4 in arbitrary order
430 /// for x in a.union(&b) {
431 /// println!("{}", x);
435 pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, B> {
436 fn or<B: BitBlock>(w1: B, w2: B) -> B { w1 | w2 }
438 Union(BlockIter::from_blocks(TwoBitPositions {
439 set: self.bit_vec.blocks(),
440 other: other.bit_vec.blocks(),
445 /// Iterator over each usize stored in `self` intersect `other`.
446 /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
451 /// use bit_set::BitSet;
453 /// let a = BitSet::from_bytes(&[0b01101000]);
454 /// let b = BitSet::from_bytes(&[0b10100000]);
457 /// for x in a.intersection(&b) {
458 /// println!("{}", x);
462 pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, B> {
463 fn bitand<B: BitBlock>(w1: B, w2: B) -> B { w1 & w2 }
464 let min = cmp::min(self.bit_vec.len(), other.bit_vec.len());
466 Intersection(BlockIter::from_blocks(TwoBitPositions {
467 set: self.bit_vec.blocks(),
468 other: other.bit_vec.blocks(),
473 /// Iterator over each usize stored in the `self` setminus `other`.
474 /// See [difference_with](#method.difference_with) for an efficient in-place version.
479 /// use bit_set::BitSet;
481 /// let a = BitSet::from_bytes(&[0b01101000]);
482 /// let b = BitSet::from_bytes(&[0b10100000]);
484 /// // Print 1, 4 in arbitrary order
485 /// for x in a.difference(&b) {
486 /// println!("{}", x);
489 /// // Note that difference is not symmetric,
490 /// // and `b - a` means something else.
492 /// for x in b.difference(&a) {
493 /// println!("{}", x);
497 pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, B> {
498 fn diff<B: BitBlock>(w1: B, w2: B) -> B { w1 & !w2 }
500 Difference(BlockIter::from_blocks(TwoBitPositions {
501 set: self.bit_vec.blocks(),
502 other: other.bit_vec.blocks(),
507 /// Iterator over each usize stored in the symmetric difference of `self` and `other`.
508 /// See [symmetric_difference_with](#method.symmetric_difference_with) for
509 /// an efficient in-place version.
514 /// use bit_set::BitSet;
516 /// let a = BitSet::from_bytes(&[0b01101000]);
517 /// let b = BitSet::from_bytes(&[0b10100000]);
519 /// // Print 0, 1, 4 in arbitrary order
520 /// for x in a.symmetric_difference(&b) {
521 /// println!("{}", x);
525 pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, B> {
526 fn bitxor<B: BitBlock>(w1: B, w2: B) -> B { w1 ^ w2 }
528 SymmetricDifference(BlockIter::from_blocks(TwoBitPositions {
529 set: self.bit_vec.blocks(),
530 other: other.bit_vec.blocks(),
535 /// Unions in-place with the specified other bit vector.
540 /// use bit_set::BitSet;
542 /// let a = 0b01101000;
543 /// let b = 0b10100000;
544 /// let res = 0b11101000;
546 /// let mut a = BitSet::from_bytes(&[a]);
547 /// let b = BitSet::from_bytes(&[b]);
548 /// let res = BitSet::from_bytes(&[res]);
550 /// a.union_with(&b);
551 /// assert_eq!(a, res);
554 pub fn union_with(&mut self, other: &Self) {
555 self.other_op(other, |w1, w2| w1 | w2);
558 /// Intersects in-place with the specified other bit vector.
563 /// use bit_set::BitSet;
565 /// let a = 0b01101000;
566 /// let b = 0b10100000;
567 /// let res = 0b00100000;
569 /// let mut a = BitSet::from_bytes(&[a]);
570 /// let b = BitSet::from_bytes(&[b]);
571 /// let res = BitSet::from_bytes(&[res]);
573 /// a.intersect_with(&b);
574 /// assert_eq!(a, res);
577 pub fn intersect_with(&mut self, other: &Self) {
578 self.other_op(other, |w1, w2| w1 & w2);
581 /// Makes this bit vector the difference with the specified other bit vector
587 /// use bit_set::BitSet;
589 /// let a = 0b01101000;
590 /// let b = 0b10100000;
591 /// let a_b = 0b01001000; // a - b
592 /// let b_a = 0b10000000; // b - a
594 /// let mut bva = BitSet::from_bytes(&[a]);
595 /// let bvb = BitSet::from_bytes(&[b]);
596 /// let bva_b = BitSet::from_bytes(&[a_b]);
597 /// let bvb_a = BitSet::from_bytes(&[b_a]);
599 /// bva.difference_with(&bvb);
600 /// assert_eq!(bva, bva_b);
602 /// let bva = BitSet::from_bytes(&[a]);
603 /// let mut bvb = BitSet::from_bytes(&[b]);
605 /// bvb.difference_with(&bva);
606 /// assert_eq!(bvb, bvb_a);
609 pub fn difference_with(&mut self, other: &Self) {
610 self.other_op(other, |w1, w2| w1 & !w2);
613 /// Makes this bit vector the symmetric difference with the specified other
614 /// bit vector in-place.
619 /// use bit_set::BitSet;
621 /// let a = 0b01101000;
622 /// let b = 0b10100000;
623 /// let res = 0b11001000;
625 /// let mut a = BitSet::from_bytes(&[a]);
626 /// let b = BitSet::from_bytes(&[b]);
627 /// let res = BitSet::from_bytes(&[res]);
629 /// a.symmetric_difference_with(&b);
630 /// assert_eq!(a, res);
633 pub fn symmetric_difference_with(&mut self, other: &Self) {
634 self.other_op(other, |w1, w2| w1 ^ w2);
638 /// Moves all elements from `other` into `Self`, leaving `other` empty.
643 /// use bit_set::BitSet;
645 /// let mut a = BitSet::new();
649 /// let mut b = BitSet::new();
654 /// a.append(&mut b);
656 /// assert_eq!(a.len(), 4);
657 /// assert_eq!(b.len(), 0);
658 /// assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
660 pub fn append(&mut self, other: &mut Self) {
661 self.union_with(other);
665 /// Splits the `BitSet` into two at the given key including the key.
666 /// Retains the first part in-place while returning the second part.
671 /// use bit_set::BitSet;
673 /// let mut a = BitSet::new();
679 /// let b = a.split_off(3);
681 /// assert_eq!(a.len(), 2);
682 /// assert_eq!(b.len(), 2);
683 /// assert_eq!(a, BitSet::from_bytes(&[0b01100000]));
684 /// assert_eq!(b, BitSet::from_bytes(&[0b00010010]));
686 pub fn split_off(&mut self, at: usize) -> Self {
687 let mut other = BitSet::new();
690 swap(self, &mut other);
692 } else if at >= self.bit_vec.len() {
696 // Calculate block and bit at which to split
700 // Pad `other` with `w` zero blocks,
701 // append `self`'s blocks in the range from `w` to the end to `other`
702 other.bit_vec.storage_mut().extend(repeat(0u32).take(w)
703 .chain(self.bit_vec.storage()[w..].iter().cloned()));
704 other.bit_vec.nbits = self.bit_vec.nbits;
707 other.bit_vec.storage_mut()[w] &= !0 << b;
710 // Sets `bit_vec.len()` and fixes the last block as well
711 self.bit_vec.truncate(at);
717 /// Returns the number of set bits in this set.
719 pub fn len(&self) -> usize {
720 self.bit_vec.blocks().fold(0, |acc, n| acc + n.count_ones() as usize)
723 /// Returns whether there are no bits set in this set
725 pub fn is_empty(&self) -> bool {
729 /// Clears all bits in this set
731 pub fn clear(&mut self) {
732 self.bit_vec.clear();
735 /// Returns `true` if this set contains the specified integer.
737 pub fn contains(&self, value: &usize) -> bool {
738 let bit_vec = &self.bit_vec;
739 *value < bit_vec.len() && bit_vec[*value]
742 /// Returns `true` if the set has no elements in common with `other`.
743 /// This is equivalent to checking for an empty intersection.
745 pub fn is_disjoint(&self, other: &Self) -> bool {
746 self.intersection(other).next().is_none()
749 /// Returns `true` if the set is a subset of another.
751 pub fn is_subset(&self, other: &Self) -> bool {
752 let self_bit_vec = &self.bit_vec;
753 let other_bit_vec = &other.bit_vec;
754 let other_blocks = blocks_for_bits::<B>(other_bit_vec.len());
756 // Check that `self` intersect `other` is self
757 self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
758 // Make sure if `self` has any more blocks than `other`, they're all 0
759 self_bit_vec.blocks().skip(other_blocks).all(|w| w == B::zero())
762 /// Returns `true` if the set is a superset of another.
764 pub fn is_superset(&self, other: &Self) -> bool {
765 other.is_subset(self)
768 /// Adds a value to the set. Returns `true` if the value was not already
769 /// present in the set.
770 pub fn insert(&mut self, value: usize) -> bool {
771 if self.contains(&value) {
775 // Ensure we have enough space to hold the new element
776 let len = self.bit_vec.len();
778 self.bit_vec.grow(value - len + 1, false)
781 self.bit_vec.set(value, true);
785 /// Removes a value from the set. Returns `true` if the value was
786 /// present in the set.
787 pub fn remove(&mut self, value: &usize) -> bool {
788 if !self.contains(value) {
792 self.bit_vec.set(*value, false);
798 impl<B: BitBlock> fmt::Debug for BitSet<B> {
799 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
800 try!(write!(fmt, "{{"));
801 let mut first = true;
804 try!(write!(fmt, ", "));
806 try!(write!(fmt, "{:?}", n));
813 impl<B: BitBlock> hash::Hash for BitSet<B> {
814 fn hash<H: hash::Hasher>(&self, state: &mut H) {
822 struct BlockIter<T, B> {
828 impl<T, B: BitBlock> BlockIter<T, B> where T: Iterator<Item=B> {
829 fn from_blocks(mut blocks: T) -> BlockIter<T, B> {
830 let h = blocks.next().unwrap_or(B::zero());
831 BlockIter {tail: blocks, head: h, head_offset: 0}
835 /// An iterator combining two `BitSet` iterators.
837 struct TwoBitPositions<'a, B: 'a> {
839 other: Blocks<'a, B>,
840 merge: fn(B, B) -> B,
843 /// An iterator for `BitSet`.
845 pub struct Iter<'a, B: 'a>(BlockIter<Blocks<'a, B>, B>);
847 pub struct Union<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
849 pub struct Intersection<'a, B: 'a>(Take<BlockIter<TwoBitPositions<'a, B>, B>>);
851 pub struct Difference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
853 pub struct SymmetricDifference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
855 impl<'a, T, B: BitBlock> Iterator for BlockIter<T, B> where T: Iterator<Item=B> {
858 fn next(&mut self) -> Option<usize> {
859 while self.head == B::zero() {
860 match self.tail.next() {
861 Some(w) => self.head = w,
864 self.head_offset += B::bits();
867 // from the current block, isolate the
868 // LSB and subtract 1, producing k:
869 // a block with a number of set bits
870 // equal to the index of the LSB
871 let k = (self.head & (!self.head + B::one())) - B::one();
872 // update block, removing the LSB
873 self.head = self.head & (self.head - B::one());
874 // return offset + (index of LSB)
875 Some(self.head_offset + (B::count_ones(k) as usize))
879 fn size_hint(&self) -> (usize, Option<usize>) {
880 match self.tail.size_hint() {
881 (_, Some(h)) => (0, Some(1 + h * B::bits())),
887 impl<'a, B: BitBlock> Iterator for TwoBitPositions<'a, B> {
890 fn next(&mut self) -> Option<B> {
891 match (self.set.next(), self.other.next()) {
892 (Some(a), Some(b)) => Some((self.merge)(a, b)),
893 (Some(a), None) => Some((self.merge)(a, B::zero())),
894 (None, Some(b)) => Some((self.merge)(B::zero(), b)),
900 fn size_hint(&self) -> (usize, Option<usize>) {
901 let (a, au) = self.set.size_hint();
902 let (b, bu) = self.other.size_hint();
904 let upper = match (au, bu) {
905 (Some(au), Some(bu)) => Some(cmp::max(au, bu)),
909 (cmp::max(a, b), upper)
913 impl<'a, B: BitBlock> Iterator for Iter<'a, B> {
916 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
917 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
920 impl<'a, B: BitBlock> Iterator for Union<'a, B> {
923 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
924 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
927 impl<'a, B: BitBlock> Iterator for Intersection<'a, B> {
930 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
931 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
934 impl<'a, B: BitBlock> Iterator for Difference<'a, B> {
937 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
938 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
941 impl<'a, B: BitBlock> Iterator for SymmetricDifference<'a, B> {
944 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
945 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
948 impl<'a, B: BitBlock> IntoIterator for &'a BitSet<B> {
950 type IntoIter = Iter<'a, B>;
952 fn into_iter(self) -> Iter<'a, B> {
967 use std::cmp::Ordering::{Equal, Greater, Less};
972 fn test_bit_set_show() {
973 let mut s = BitSet::new();
978 assert_eq!("{1, 2, 10, 50}", format!("{:?}", s));
982 fn test_bit_set_from_usizes() {
983 let usizes = vec![0, 2, 2, 3];
984 let a: BitSet = usizes.into_iter().collect();
985 let mut b = BitSet::new();
993 fn test_bit_set_iterator() {
994 let usizes = vec![0, 2, 2, 3];
995 let bit_vec: BitSet = usizes.into_iter().collect();
997 let idxs: Vec<_> = bit_vec.iter().collect();
998 assert_eq!(idxs, [0, 2, 3]);
1000 let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect();
1001 let real: Vec<_> = (0..10000/2).map(|x| x*2).collect();
1003 let idxs: Vec<_> = long.iter().collect();
1004 assert_eq!(idxs, real);
1008 fn test_bit_set_frombit_vec_init() {
1009 let bools = [true, false];
1010 let lengths = [10, 64, 100];
1012 for &l in &lengths {
1013 let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
1014 assert_eq!(bitset.contains(&1), b);
1015 assert_eq!(bitset.contains(&(l-1)), b);
1016 assert!(!bitset.contains(&l));
1022 fn test_bit_vec_masking() {
1023 let b = BitVec::from_elem(140, true);
1024 let mut bs = BitSet::from_bit_vec(b);
1025 assert!(bs.contains(&139));
1026 assert!(!bs.contains(&140));
1027 assert!(bs.insert(150));
1028 assert!(!bs.contains(&140));
1029 assert!(!bs.contains(&149));
1030 assert!(bs.contains(&150));
1031 assert!(!bs.contains(&151));
1035 fn test_bit_set_basic() {
1036 let mut b = BitSet::new();
1037 assert!(b.insert(3));
1038 assert!(!b.insert(3));
1039 assert!(b.contains(&3));
1040 assert!(b.insert(4));
1041 assert!(!b.insert(4));
1042 assert!(b.contains(&3));
1043 assert!(b.insert(400));
1044 assert!(!b.insert(400));
1045 assert!(b.contains(&400));
1046 assert_eq!(b.len(), 3);
1050 fn test_bit_set_intersection() {
1051 let mut a = BitSet::new();
1052 let mut b = BitSet::new();
1054 assert!(a.insert(11));
1055 assert!(a.insert(1));
1056 assert!(a.insert(3));
1057 assert!(a.insert(77));
1058 assert!(a.insert(103));
1059 assert!(a.insert(5));
1061 assert!(b.insert(2));
1062 assert!(b.insert(11));
1063 assert!(b.insert(77));
1064 assert!(b.insert(5));
1065 assert!(b.insert(3));
1067 let expected = [3, 5, 11, 77];
1068 let actual: Vec<_> = a.intersection(&b).collect();
1069 assert_eq!(actual, expected);
1073 fn test_bit_set_difference() {
1074 let mut a = BitSet::new();
1075 let mut b = BitSet::new();
1077 assert!(a.insert(1));
1078 assert!(a.insert(3));
1079 assert!(a.insert(5));
1080 assert!(a.insert(200));
1081 assert!(a.insert(500));
1083 assert!(b.insert(3));
1084 assert!(b.insert(200));
1086 let expected = [1, 5, 500];
1087 let actual: Vec<_> = a.difference(&b).collect();
1088 assert_eq!(actual, expected);
1092 fn test_bit_set_symmetric_difference() {
1093 let mut a = BitSet::new();
1094 let mut b = BitSet::new();
1096 assert!(a.insert(1));
1097 assert!(a.insert(3));
1098 assert!(a.insert(5));
1099 assert!(a.insert(9));
1100 assert!(a.insert(11));
1102 assert!(b.insert(3));
1103 assert!(b.insert(9));
1104 assert!(b.insert(14));
1105 assert!(b.insert(220));
1107 let expected = [1, 5, 11, 14, 220];
1108 let actual: Vec<_> = a.symmetric_difference(&b).collect();
1109 assert_eq!(actual, expected);
1113 fn test_bit_set_union() {
1114 let mut a = BitSet::new();
1115 let mut b = BitSet::new();
1116 assert!(a.insert(1));
1117 assert!(a.insert(3));
1118 assert!(a.insert(5));
1119 assert!(a.insert(9));
1120 assert!(a.insert(11));
1121 assert!(a.insert(160));
1122 assert!(a.insert(19));
1123 assert!(a.insert(24));
1124 assert!(a.insert(200));
1126 assert!(b.insert(1));
1127 assert!(b.insert(5));
1128 assert!(b.insert(9));
1129 assert!(b.insert(13));
1130 assert!(b.insert(19));
1132 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
1133 let actual: Vec<_> = a.union(&b).collect();
1134 assert_eq!(actual, expected);
1138 fn test_bit_set_subset() {
1139 let mut set1 = BitSet::new();
1140 let mut set2 = BitSet::new();
1142 assert!(set1.is_subset(&set2)); // {} {}
1144 assert!(set1.is_subset(&set2)); // {} { 1 }
1146 assert!(set1.is_subset(&set2)); // {} { 1, 2 }
1148 assert!(set1.is_subset(&set2)); // { 2 } { 1, 2 }
1150 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 1, 2 }
1152 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3 }
1154 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3, 4 }
1156 assert!(set1.is_subset(&set2)); // { 2, 3 } { 2, 3, 4 }
1158 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 2, 4 }
1160 assert!(set1.is_subset(&set2)); // { 2 } { 2, 4 }
1164 fn test_bit_set_is_disjoint() {
1165 let a = BitSet::from_bytes(&[0b10100010]);
1166 let b = BitSet::from_bytes(&[0b01000000]);
1167 let c = BitSet::new();
1168 let d = BitSet::from_bytes(&[0b00110000]);
1170 assert!(!a.is_disjoint(&d));
1171 assert!(!d.is_disjoint(&a));
1173 assert!(a.is_disjoint(&b));
1174 assert!(a.is_disjoint(&c));
1175 assert!(b.is_disjoint(&a));
1176 assert!(b.is_disjoint(&c));
1177 assert!(c.is_disjoint(&a));
1178 assert!(c.is_disjoint(&b));
1182 fn test_bit_set_union_with() {
1183 //a should grow to include larger elements
1184 let mut a = BitSet::new();
1186 let mut b = BitSet::new();
1188 let expected = BitSet::from_bytes(&[0b10000100]);
1190 assert_eq!(a, expected);
1193 let mut a = BitSet::from_bytes(&[0b10100010]);
1194 let mut b = BitSet::from_bytes(&[0b01100010]);
1198 assert_eq!(a.len(), 4);
1199 assert_eq!(b.len(), 4);
1203 fn test_bit_set_intersect_with() {
1204 // Explicitly 0'ed bits
1205 let mut a = BitSet::from_bytes(&[0b10100010]);
1206 let mut b = BitSet::from_bytes(&[0b00000000]);
1208 a.intersect_with(&b);
1209 b.intersect_with(&c);
1210 assert!(a.is_empty());
1211 assert!(b.is_empty());
1213 // Uninitialized bits should behave like 0's
1214 let mut a = BitSet::from_bytes(&[0b10100010]);
1215 let mut b = BitSet::new();
1217 a.intersect_with(&b);
1218 b.intersect_with(&c);
1219 assert!(a.is_empty());
1220 assert!(b.is_empty());
1223 let mut a = BitSet::from_bytes(&[0b10100010]);
1224 let mut b = BitSet::from_bytes(&[0b01100010]);
1226 a.intersect_with(&b);
1227 b.intersect_with(&c);
1228 assert_eq!(a.len(), 2);
1229 assert_eq!(b.len(), 2);
1233 fn test_bit_set_difference_with() {
1234 // Explicitly 0'ed bits
1235 let mut a = BitSet::from_bytes(&[0b00000000]);
1236 let b = BitSet::from_bytes(&[0b10100010]);
1237 a.difference_with(&b);
1238 assert!(a.is_empty());
1240 // Uninitialized bits should behave like 0's
1241 let mut a = BitSet::new();
1242 let b = BitSet::from_bytes(&[0b11111111]);
1243 a.difference_with(&b);
1244 assert!(a.is_empty());
1247 let mut a = BitSet::from_bytes(&[0b10100010]);
1248 let mut b = BitSet::from_bytes(&[0b01100010]);
1250 a.difference_with(&b);
1251 b.difference_with(&c);
1252 assert_eq!(a.len(), 1);
1253 assert_eq!(b.len(), 1);
1257 fn test_bit_set_symmetric_difference_with() {
1258 //a should grow to include larger elements
1259 let mut a = BitSet::new();
1262 let mut b = BitSet::new();
1265 let expected = BitSet::from_bytes(&[0b10000100]);
1266 a.symmetric_difference_with(&b);
1267 assert_eq!(a, expected);
1269 let mut a = BitSet::from_bytes(&[0b10100010]);
1270 let b = BitSet::new();
1272 a.symmetric_difference_with(&b);
1276 let mut a = BitSet::from_bytes(&[0b11100010]);
1277 let mut b = BitSet::from_bytes(&[0b01101010]);
1279 a.symmetric_difference_with(&b);
1280 b.symmetric_difference_with(&c);
1281 assert_eq!(a.len(), 2);
1282 assert_eq!(b.len(), 2);
1286 fn test_bit_set_eq() {
1287 let a = BitSet::from_bytes(&[0b10100010]);
1288 let b = BitSet::from_bytes(&[0b00000000]);
1289 let c = BitSet::new();
1300 fn test_bit_set_cmp() {
1301 let a = BitSet::from_bytes(&[0b10100010]);
1302 let b = BitSet::from_bytes(&[0b00000000]);
1303 let c = BitSet::new();
1305 assert_eq!(a.cmp(&b), Greater);
1306 assert_eq!(a.cmp(&c), Greater);
1307 assert_eq!(b.cmp(&a), Less);
1308 assert_eq!(b.cmp(&c), Equal);
1309 assert_eq!(c.cmp(&a), Less);
1310 assert_eq!(c.cmp(&b), Equal);
1314 fn test_bit_vec_remove() {
1315 let mut a = BitSet::new();
1317 assert!(a.insert(1));
1318 assert!(a.remove(&1));
1320 assert!(a.insert(100));
1321 assert!(a.remove(&100));
1323 assert!(a.insert(1000));
1324 assert!(a.remove(&1000));
1329 fn test_bit_vec_clone() {
1330 let mut a = BitSet::new();
1332 assert!(a.insert(1));
1333 assert!(a.insert(100));
1334 assert!(a.insert(1000));
1336 let mut b = a.clone();
1340 assert!(b.remove(&1));
1341 assert!(a.contains(&1));
1343 assert!(a.remove(&1000));
1344 assert!(b.contains(&1000));
1349 fn test_bit_set_append() {
1350 let mut a = BitSet::new();
1354 let mut b = BitSet::new();
1361 assert_eq!(a.len(), 4);
1362 assert_eq!(b.len(), 0);
1363 assert!(b.capacity() >= 6);
1365 assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
1369 fn test_bit_set_split_off() {
1371 let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1372 0b00110011, 0b01101011, 0b10101101]);
1374 let b = a.split_off(0);
1376 assert_eq!(a.len(), 0);
1377 assert_eq!(b.len(), 21);
1379 assert_eq!(b, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1380 0b00110011, 0b01101011, 0b10101101]);
1382 // Split behind last element
1383 let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1384 0b00110011, 0b01101011, 0b10101101]);
1386 let b = a.split_off(50);
1388 assert_eq!(a.len(), 21);
1389 assert_eq!(b.len(), 0);
1391 assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1392 0b00110011, 0b01101011, 0b10101101]));
1394 // Split at arbitrary element
1395 let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1396 0b00110011, 0b01101011, 0b10101101]);
1398 let b = a.split_off(34);
1400 assert_eq!(a.len(), 12);
1401 assert_eq!(b.len(), 9);
1403 assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1404 0b00110011, 0b01000000]));
1405 assert_eq!(b, BitSet::from_bytes(&[0, 0, 0, 0,
1406 0b00101011, 0b10101101]));
1411 #[cfg(all(test, feature = "nightly"))]
1414 use bit_vec::BitVec;
1415 use rand::{Rng, thread_rng, ThreadRng};
1417 use test::{Bencher, black_box};
1419 const BENCH_BITS: usize = 1 << 14;
1420 const BITS: usize = 32;
1422 fn rng() -> ThreadRng {
1427 fn bench_bit_vecset_small(b: &mut Bencher) {
1429 let mut bit_vec = BitSet::new();
1432 bit_vec.insert((r.next_u32() as usize) % BITS);
1434 black_box(&bit_vec);
1439 fn bench_bit_vecset_big(b: &mut Bencher) {
1441 let mut bit_vec = BitSet::new();
1444 bit_vec.insert((r.next_u32() as usize) % BENCH_BITS);
1446 black_box(&bit_vec);
1451 fn bench_bit_vecset_iter(b: &mut Bencher) {
1452 let bit_vec = BitSet::from_bit_vec(BitVec::from_fn(BENCH_BITS,
1453 |idx| {idx % 3 == 0}));
1456 for idx in &bit_vec {
1457 sum += idx as usize;