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(all(test, feature = "nightly"))]
  56 extern crate test;
  57
  58 #[cfg(test)]
  59 #[macro_use]
  60 extern crate std;
  61
  62 use bit_vec::{BitBlock, BitVec, Blocks};
  63 use core::cmp;
  64 use core::cmp::Ordering;
  65 use core::fmt;
  66 use core::hash;
  67 use core::iter::{self, Chain, Enumerate, FromIterator, Repeat, Skip, Take};
  68
  69 type 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
  72 fn 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
  90 fn 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
 119 pub struct BitSet<B = u32> {
 120     bit_vec: BitVec<B>,
 121 }
 122
 123 impl<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
 135 impl<B: BitBlock> Default for BitSet<B> {
 136     #[inline]
 137     fn default() -> Self {
 138         BitSet {
 139             bit_vec: Default::default(),
 140         }
 141     }
 142 }
 143
 144 impl<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
 152 impl<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
 161 impl<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
 168 impl<B: BitBlock> Ord for BitSet<B> {
 169     #[inline]
 170     fn cmp(&self, other: &Self) -> Ordering {
 171         self.iter().cmp(other)
 172     }
 173 }
 174
 175 impl<B: BitBlock> PartialEq for BitSet<B> {
 176     #[inline]
 177     fn eq(&self, other: &Self) -> bool {
 178         self.iter().eq(other)
 179     }
 180 }
 181
 182 impl<B: BitBlock> Eq for BitSet<B> {}
 183
 184 impl 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
 249 impl<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
 836 impl<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
 842 impl<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)]
 851 struct BlockIter<T, B> {
 852     head: B,
 853     head_offset: usize,
 854     tail: T,
 855 }
 856
 857 impl<T, B: BitBlock> BlockIter<T, B>
 858 where
 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)]
 873 struct 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)]
 881 pub struct Iter<'a, B: 'a>(BlockIter<Blocks<'a, B>, B>);
 882 #[derive(Clone)]
 883 pub struct Union<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
 884 #[derive(Clone)]
 885 pub struct Intersection<'a, B: 'a>(Take<BlockIter<TwoBitPositions<'a, B>, B>>);
 886 #[derive(Clone)]
 887 pub struct Difference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
 888 #[derive(Clone)]
 889 pub struct SymmetricDifference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
 890
 891 impl<'a, T, B: BitBlock> Iterator for BlockIter<T, B>
 892 where
 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
 926 impl<'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
 952 impl<'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
 965 impl<'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
 978 impl<'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
 991 impl<'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
1004 impl<'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
1017 impl<'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)]
1027 mod 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"))]
1559 mod 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 }