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