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
 416         let trunc_len = cmp::max(old_len - n, 1);
 417         unsafe {
 418             bit_vec.storage_mut().truncate(trunc_len);
 419             bit_vec.set_len(trunc_len * B::bits());
 420         }
 421     }
 422
 423     /// Iterator over each usize stored in the `BitSet`.
 424     ///
 425     /// # Examples
 426     ///
 427     /// ```
 428     /// use bit_set::BitSet;
 429     ///
 430     /// let s = BitSet::from_bytes(&[0b01001010]);
 431     ///
 432     /// // Print 1, 4, 6 in arbitrary order
 433     /// for x in s.iter() {
 434     ///     println!("{}", x);
 435     /// }
 436     /// ```
 437     #[inline]
 438     pub fn iter(&self) -> Iter<B> {
 439         Iter(BlockIter::from_blocks(self.bit_vec.blocks()))
 440     }
 441
 442     /// Iterator over each usize stored in `self` union `other`.
 443     /// See [union_with](#method.union_with) for an efficient in-place version.
 444     ///
 445     /// # Examples
 446     ///
 447     /// ```
 448     /// use bit_set::BitSet;
 449     ///
 450     /// let a = BitSet::from_bytes(&[0b01101000]);
 451     /// let b = BitSet::from_bytes(&[0b10100000]);
 452     ///
 453     /// // Print 0, 1, 2, 4 in arbitrary order
 454     /// for x in a.union(&b) {
 455     ///     println!("{}", x);
 456     /// }
 457     /// ```
 458     #[inline]
 459     pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, B> {
 460         fn or<B: BitBlock>(w1: B, w2: B) -> B {
 461             w1 | w2
 462         }
 463
 464         Union(BlockIter::from_blocks(TwoBitPositions {
 465             set: self.bit_vec.blocks(),
 466             other: other.bit_vec.blocks(),
 467             merge: or,
 468         }))
 469     }
 470
 471     /// Iterator over each usize stored in `self` intersect `other`.
 472     /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
 473     ///
 474     /// # Examples
 475     ///
 476     /// ```
 477     /// use bit_set::BitSet;
 478     ///
 479     /// let a = BitSet::from_bytes(&[0b01101000]);
 480     /// let b = BitSet::from_bytes(&[0b10100000]);
 481     ///
 482     /// // Print 2
 483     /// for x in a.intersection(&b) {
 484     ///     println!("{}", x);
 485     /// }
 486     /// ```
 487     #[inline]
 488     pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, B> {
 489         fn bitand<B: BitBlock>(w1: B, w2: B) -> B {
 490             w1 & w2
 491         }
 492         let min = cmp::min(self.bit_vec.len(), other.bit_vec.len());
 493
 494         Intersection(
 495             BlockIter::from_blocks(TwoBitPositions {
 496                 set: self.bit_vec.blocks(),
 497                 other: other.bit_vec.blocks(),
 498                 merge: bitand,
 499             })
 500             .take(min),
 501         )
 502     }
 503
 504     /// Iterator over each usize stored in the `self` setminus `other`.
 505     /// See [difference_with](#method.difference_with) for an efficient in-place version.
 506     ///
 507     /// # Examples
 508     ///
 509     /// ```
 510     /// use bit_set::BitSet;
 511     ///
 512     /// let a = BitSet::from_bytes(&[0b01101000]);
 513     /// let b = BitSet::from_bytes(&[0b10100000]);
 514     ///
 515     /// // Print 1, 4 in arbitrary order
 516     /// for x in a.difference(&b) {
 517     ///     println!("{}", x);
 518     /// }
 519     ///
 520     /// // Note that difference is not symmetric,
 521     /// // and `b - a` means something else.
 522     /// // This prints 0
 523     /// for x in b.difference(&a) {
 524     ///     println!("{}", x);
 525     /// }
 526     /// ```
 527     #[inline]
 528     pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, B> {
 529         fn diff<B: BitBlock>(w1: B, w2: B) -> B {
 530             w1 & !w2
 531         }
 532
 533         Difference(BlockIter::from_blocks(TwoBitPositions {
 534             set: self.bit_vec.blocks(),
 535             other: other.bit_vec.blocks(),
 536             merge: diff,
 537         }))
 538     }
 539
 540     /// Iterator over each usize stored in the symmetric difference of `self` and `other`.
 541     /// See [symmetric_difference_with](#method.symmetric_difference_with) for
 542     /// an efficient in-place version.
 543     ///
 544     /// # Examples
 545     ///
 546     /// ```
 547     /// use bit_set::BitSet;
 548     ///
 549     /// let a = BitSet::from_bytes(&[0b01101000]);
 550     /// let b = BitSet::from_bytes(&[0b10100000]);
 551     ///
 552     /// // Print 0, 1, 4 in arbitrary order
 553     /// for x in a.symmetric_difference(&b) {
 554     ///     println!("{}", x);
 555     /// }
 556     /// ```
 557     #[inline]
 558     pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, B> {
 559         fn bitxor<B: BitBlock>(w1: B, w2: B) -> B {
 560             w1 ^ w2
 561         }
 562
 563         SymmetricDifference(BlockIter::from_blocks(TwoBitPositions {
 564             set: self.bit_vec.blocks(),
 565             other: other.bit_vec.blocks(),
 566             merge: bitxor,
 567         }))
 568     }
 569
 570     /// Unions in-place with the specified other bit vector.
 571     ///
 572     /// # Examples
 573     ///
 574     /// ```
 575     /// use bit_set::BitSet;
 576     ///
 577     /// let a   = 0b01101000;
 578     /// let b   = 0b10100000;
 579     /// let res = 0b11101000;
 580     ///
 581     /// let mut a = BitSet::from_bytes(&[a]);
 582     /// let b = BitSet::from_bytes(&[b]);
 583     /// let res = BitSet::from_bytes(&[res]);
 584     ///
 585     /// a.union_with(&b);
 586     /// assert_eq!(a, res);
 587     /// ```
 588     #[inline]
 589     pub fn union_with(&mut self, other: &Self) {
 590         self.other_op(other, |w1, w2| w1 | w2);
 591     }
 592
 593     /// Intersects in-place with the specified other bit vector.
 594     ///
 595     /// # Examples
 596     ///
 597     /// ```
 598     /// use bit_set::BitSet;
 599     ///
 600     /// let a   = 0b01101000;
 601     /// let b   = 0b10100000;
 602     /// let res = 0b00100000;
 603     ///
 604     /// let mut a = BitSet::from_bytes(&[a]);
 605     /// let b = BitSet::from_bytes(&[b]);
 606     /// let res = BitSet::from_bytes(&[res]);
 607     ///
 608     /// a.intersect_with(&b);
 609     /// assert_eq!(a, res);
 610     /// ```
 611     #[inline]
 612     pub fn intersect_with(&mut self, other: &Self) {
 613         self.other_op(other, |w1, w2| w1 & w2);
 614     }
 615
 616     /// Makes this bit vector the difference with the specified other bit vector
 617     /// in-place.
 618     ///
 619     /// # Examples
 620     ///
 621     /// ```
 622     /// use bit_set::BitSet;
 623     ///
 624     /// let a   = 0b01101000;
 625     /// let b   = 0b10100000;
 626     /// let a_b = 0b01001000; // a - b
 627     /// let b_a = 0b10000000; // b - a
 628     ///
 629     /// let mut bva = BitSet::from_bytes(&[a]);
 630     /// let bvb = BitSet::from_bytes(&[b]);
 631     /// let bva_b = BitSet::from_bytes(&[a_b]);
 632     /// let bvb_a = BitSet::from_bytes(&[b_a]);
 633     ///
 634     /// bva.difference_with(&bvb);
 635     /// assert_eq!(bva, bva_b);
 636     ///
 637     /// let bva = BitSet::from_bytes(&[a]);
 638     /// let mut bvb = BitSet::from_bytes(&[b]);
 639     ///
 640     /// bvb.difference_with(&bva);
 641     /// assert_eq!(bvb, bvb_a);
 642     /// ```
 643     #[inline]
 644     pub fn difference_with(&mut self, other: &Self) {
 645         self.other_op(other, |w1, w2| w1 & !w2);
 646     }
 647
 648     /// Makes this bit vector the symmetric difference with the specified other
 649     /// bit vector in-place.
 650     ///
 651     /// # Examples
 652     ///
 653     /// ```
 654     /// use bit_set::BitSet;
 655     ///
 656     /// let a   = 0b01101000;
 657     /// let b   = 0b10100000;
 658     /// let res = 0b11001000;
 659     ///
 660     /// let mut a = BitSet::from_bytes(&[a]);
 661     /// let b = BitSet::from_bytes(&[b]);
 662     /// let res = BitSet::from_bytes(&[res]);
 663     ///
 664     /// a.symmetric_difference_with(&b);
 665     /// assert_eq!(a, res);
 666     /// ```
 667     #[inline]
 668     pub fn symmetric_difference_with(&mut self, other: &Self) {
 669         self.other_op(other, |w1, w2| w1 ^ w2);
 670     }
 671
 672     /*
 673         /// Moves all elements from `other` into `Self`, leaving `other` empty.
 674         ///
 675         /// # Examples
 676         ///
 677         /// ```
 678         /// use bit_set::BitSet;
 679         ///
 680         /// let mut a = BitSet::new();
 681         /// a.insert(2);
 682         /// a.insert(6);
 683         ///
 684         /// let mut b = BitSet::new();
 685         /// b.insert(1);
 686         /// b.insert(3);
 687         /// b.insert(6);
 688         ///
 689         /// a.append(&mut b);
 690         ///
 691         /// assert_eq!(a.len(), 4);
 692         /// assert_eq!(b.len(), 0);
 693         /// assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
 694         /// ```
 695         pub fn append(&mut self, other: &mut Self) {
 696             self.union_with(other);
 697             other.clear();
 698         }
 699
 700         /// Splits the `BitSet` into two at the given key including the key.
 701         /// Retains the first part in-place while returning the second part.
 702         ///
 703         /// # Examples
 704         ///
 705         /// ```
 706         /// use bit_set::BitSet;
 707         ///
 708         /// let mut a = BitSet::new();
 709         /// a.insert(2);
 710         /// a.insert(6);
 711         /// a.insert(1);
 712         /// a.insert(3);
 713         ///
 714         /// let b = a.split_off(3);
 715         ///
 716         /// assert_eq!(a.len(), 2);
 717         /// assert_eq!(b.len(), 2);
 718         /// assert_eq!(a, BitSet::from_bytes(&[0b01100000]));
 719         /// assert_eq!(b, BitSet::from_bytes(&[0b00010010]));
 720         /// ```
 721         pub fn split_off(&mut self, at: usize) -> Self {
 722             let mut other = BitSet::new();
 723
 724             if at == 0 {
 725                 swap(self, &mut other);
 726                 return other;
 727             } else if at >= self.bit_vec.len() {
 728                 return other;
 729             }
 730
 731             // Calculate block and bit at which to split
 732             let w = at / BITS;
 733             let b = at % BITS;
 734
 735             // Pad `other` with `w` zero blocks,
 736             // append `self`'s blocks in the range from `w` to the end to `other`
 737             other.bit_vec.storage_mut().extend(repeat(0u32).take(w)
 738                                          .chain(self.bit_vec.storage()[w..].iter().cloned()));
 739             other.bit_vec.nbits = self.bit_vec.nbits;
 740
 741             if b > 0 {
 742                 other.bit_vec.storage_mut()[w] &= !0 << b;
 743             }
 744
 745             // Sets `bit_vec.len()` and fixes the last block as well
 746             self.bit_vec.truncate(at);
 747
 748             other
 749         }
 750     */
 751
 752     /// Returns the number of set bits in this set.
 753     #[inline]
 754     pub fn len(&self) -> usize {
 755         self.bit_vec
 756             .blocks()
 757             .fold(0, |acc, n| acc + n.count_ones() as usize)
 758     }
 759
 760     /// Returns whether there are no bits set in this set
 761     #[inline]
 762     pub fn is_empty(&self) -> bool {
 763         self.bit_vec.none()
 764     }
 765
 766     /// Clears all bits in this set
 767     #[inline]
 768     pub fn clear(&mut self) {
 769         self.bit_vec.clear();
 770     }
 771
 772     /// Returns `true` if this set contains the specified integer.
 773     #[inline]
 774     pub fn contains(&self, value: usize) -> bool {
 775         let bit_vec = &self.bit_vec;
 776         value < bit_vec.len() && bit_vec[value]
 777     }
 778
 779     /// Returns `true` if the set has no elements in common with `other`.
 780     /// This is equivalent to checking for an empty intersection.
 781     #[inline]
 782     pub fn is_disjoint(&self, other: &Self) -> bool {
 783         self.intersection(other).next().is_none()
 784     }
 785
 786     /// Returns `true` if the set is a subset of another.
 787     #[inline]
 788     pub fn is_subset(&self, other: &Self) -> bool {
 789         let self_bit_vec = &self.bit_vec;
 790         let other_bit_vec = &other.bit_vec;
 791         let other_blocks = blocks_for_bits::<B>(other_bit_vec.len());
 792
 793         // Check that `self` intersect `other` is self
 794         self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
 795         // Make sure if `self` has any more blocks than `other`, they're all 0
 796         self_bit_vec.blocks().skip(other_blocks).all(|w| w == B::zero())
 797     }
 798
 799     /// Returns `true` if the set is a superset of another.
 800     #[inline]
 801     pub fn is_superset(&self, other: &Self) -> bool {
 802         other.is_subset(self)
 803     }
 804
 805     /// Adds a value to the set. Returns `true` if the value was not already
 806     /// present in the set.
 807     pub fn insert(&mut self, value: usize) -> bool {
 808         if self.contains(value) {
 809             return false;
 810         }
 811
 812         // Ensure we have enough space to hold the new element
 813         let len = self.bit_vec.len();
 814         if value >= len {
 815             self.bit_vec.grow(value - len + 1, false)
 816         }
 817
 818         self.bit_vec.set(value, true);
 819         true
 820     }
 821
 822     /// Removes a value from the set. Returns `true` if the value was
 823     /// present in the set.
 824     pub fn remove(&mut self, value: usize) -> bool {
 825         if !self.contains(value) {
 826             return false;
 827         }
 828
 829         self.bit_vec.set(value, false);
 830
 831         true
 832     }
 833 }
 834
 835 impl<B: BitBlock> fmt::Debug for BitSet<B> {
 836     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 837         fmt.debug_set().entries(self).finish()
 838     }
 839 }
 840
 841 impl<B: BitBlock> hash::Hash for BitSet<B> {
 842     fn hash<H: hash::Hasher>(&self, state: &mut H) {
 843         for pos in self {
 844             pos.hash(state);
 845         }
 846     }
 847 }
 848
 849 #[derive(Clone)]
 850 struct BlockIter<T, B> {
 851     head: B,
 852     head_offset: usize,
 853     tail: T,
 854 }
 855
 856 impl<T, B: BitBlock> BlockIter<T, B>
 857 where
 858     T: Iterator<Item = B>,
 859 {
 860     fn from_blocks(mut blocks: T) -> BlockIter<T, B> {
 861         let h = blocks.next().unwrap_or_else(B::zero);
 862         BlockIter {
 863             tail: blocks,
 864             head: h,
 865             head_offset: 0,
 866         }
 867     }
 868 }
 869
 870 /// An iterator combining two `BitSet` iterators.
 871 #[derive(Clone)]
 872 struct TwoBitPositions<'a, B: 'a> {
 873     set: Blocks<'a, B>,
 874     other: Blocks<'a, B>,
 875     merge: fn(B, B) -> B,
 876 }
 877
 878 /// An iterator for `BitSet`.
 879 #[derive(Clone)]
 880 pub struct Iter<'a, B: 'a>(BlockIter<Blocks<'a, B>, B>);
 881 #[derive(Clone)]
 882 pub struct Union<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
 883 #[derive(Clone)]
 884 pub struct Intersection<'a, B: 'a>(Take<BlockIter<TwoBitPositions<'a, B>, B>>);
 885 #[derive(Clone)]
 886 pub struct Difference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
 887 #[derive(Clone)]
 888 pub struct SymmetricDifference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
 889
 890 impl<'a, T, B: BitBlock> Iterator for BlockIter<T, B>
 891 where
 892     T: Iterator<Item = B>,
 893 {
 894     type Item = usize;
 895
 896     fn next(&mut self) -> Option<usize> {
 897         while self.head == B::zero() {
 898             match self.tail.next() {
 899                 Some(w) => self.head = w,
 900                 None => return None,
 901             }
 902             self.head_offset += B::bits();
 903         }
 904
 905         // from the current block, isolate the
 906         // LSB and subtract 1, producing k:
 907         // a block with a number of set bits
 908         // equal to the index of the LSB
 909         let k = (self.head & (!self.head + B::one())) - B::one();
 910         // update block, removing the LSB
 911         self.head = self.head & (self.head - B::one());
 912         // return offset + (index of LSB)
 913         Some(self.head_offset + (B::count_ones(k) as usize))
 914     }
 915
 916     #[inline]
 917     fn size_hint(&self) -> (usize, Option<usize>) {
 918         match self.tail.size_hint() {
 919             (_, Some(h)) => (0, Some(1 + h * B::bits())),
 920             _ => (0, None),
 921         }
 922     }
 923 }
 924
 925 impl<'a, B: BitBlock> Iterator for TwoBitPositions<'a, B> {
 926     type Item = B;
 927
 928     fn next(&mut self) -> Option<B> {
 929         match (self.set.next(), self.other.next()) {
 930             (Some(a), Some(b)) => Some((self.merge)(a, b)),
 931             (Some(a), None) => Some((self.merge)(a, B::zero())),
 932             (None, Some(b)) => Some((self.merge)(B::zero(), b)),
 933             _ => None,
 934         }
 935     }
 936
 937     #[inline]
 938     fn size_hint(&self) -> (usize, Option<usize>) {
 939         let (a, au) = self.set.size_hint();
 940         let (b, bu) = self.other.size_hint();
 941
 942         let upper = match (au, bu) {
 943             (Some(au), Some(bu)) => Some(cmp::max(au, bu)),
 944             _ => None,
 945         };
 946
 947         (cmp::max(a, b), upper)
 948     }
 949 }
 950
 951 impl<'a, B: BitBlock> Iterator for Iter<'a, B> {
 952     type Item = usize;
 953
 954     #[inline]
 955     fn next(&mut self) -> Option<usize> {
 956         self.0.next()
 957     }
 958     #[inline]
 959     fn size_hint(&self) -> (usize, Option<usize>) {
 960         self.0.size_hint()
 961     }
 962 }
 963
 964 impl<'a, B: BitBlock> Iterator for Union<'a, B> {
 965     type Item = usize;
 966
 967     #[inline]
 968     fn next(&mut self) -> Option<usize> {
 969         self.0.next()
 970     }
 971     #[inline]
 972     fn size_hint(&self) -> (usize, Option<usize>) {
 973         self.0.size_hint()
 974     }
 975 }
 976
 977 impl<'a, B: BitBlock> Iterator for Intersection<'a, B> {
 978     type Item = usize;
 979
 980     #[inline]
 981     fn next(&mut self) -> Option<usize> {
 982         self.0.next()
 983     }
 984     #[inline]
 985     fn size_hint(&self) -> (usize, Option<usize>) {
 986         self.0.size_hint()
 987     }
 988 }
 989
 990 impl<'a, B: BitBlock> Iterator for Difference<'a, B> {
 991     type Item = usize;
 992
 993     #[inline]
 994     fn next(&mut self) -> Option<usize> {
 995         self.0.next()
 996     }
 997     #[inline]
 998     fn size_hint(&self) -> (usize, Option<usize>) {
 999         self.0.size_hint()
1000     }
1001 }
1002
1003 impl<'a, B: BitBlock> Iterator for SymmetricDifference<'a, B> {
1004     type Item = usize;
1005
1006     #[inline]
1007     fn next(&mut self) -> Option<usize> {
1008         self.0.next()
1009     }
1010     #[inline]
1011     fn size_hint(&self) -> (usize, Option<usize>) {
1012         self.0.size_hint()
1013     }
1014 }
1015
1016 impl<'a, B: BitBlock> IntoIterator for &'a BitSet<B> {
1017     type Item = usize;
1018     type IntoIter = Iter<'a, B>;
1019
1020     fn into_iter(self) -> Iter<'a, B> {
1021         self.iter()
1022     }
1023 }
1024
1025 #[cfg(test)]
1026 mod tests {
1027     use super::BitSet;
1028     use bit_vec::BitVec;
1029     use std::cmp::Ordering::{Equal, Greater, Less};
1030     use std::vec::Vec;
1031
1032     #[test]
1033     fn test_bit_set_show() {
1034         let mut s = BitSet::new();
1035         s.insert(1);
1036         s.insert(10);
1037         s.insert(50);
1038         s.insert(2);
1039         assert_eq!("{1, 2, 10, 50}", format!("{:?}", s));
1040     }
1041
1042     #[test]
1043     fn test_bit_set_from_usizes() {
1044         let usizes = vec![0, 2, 2, 3];
1045         let a: BitSet = usizes.into_iter().collect();
1046         let mut b = BitSet::new();
1047         b.insert(0);
1048         b.insert(2);
1049         b.insert(3);
1050         assert_eq!(a, b);
1051     }
1052
1053     #[test]
1054     fn test_bit_set_iterator() {
1055         let usizes = vec![0, 2, 2, 3];
1056         let bit_vec: BitSet = usizes.into_iter().collect();
1057
1058         let idxs: Vec<_> = bit_vec.iter().collect();
1059         assert_eq!(idxs, [0, 2, 3]);
1060
1061         let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect();
1062         let real: Vec<_> = (0..10000 / 2).map(|x| x * 2).collect();
1063
1064         let idxs: Vec<_> = long.iter().collect();
1065         assert_eq!(idxs, real);
1066     }
1067
1068     #[test]
1069     fn test_bit_set_frombit_vec_init() {
1070         let bools = [true, false];
1071         let lengths = [10, 64, 100];
1072         for &b in &bools {
1073             for &l in &lengths {
1074                 let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
1075                 assert_eq!(bitset.contains(1), b);
1076                 assert_eq!(bitset.contains(l - 1), b);
1077                 assert!(!bitset.contains(l));
1078             }
1079         }
1080     }
1081
1082     #[test]
1083     fn test_bit_vec_masking() {
1084         let b = BitVec::from_elem(140, true);
1085         let mut bs = BitSet::from_bit_vec(b);
1086         assert!(bs.contains(139));
1087         assert!(!bs.contains(140));
1088         assert!(bs.insert(150));
1089         assert!(!bs.contains(140));
1090         assert!(!bs.contains(149));
1091         assert!(bs.contains(150));
1092         assert!(!bs.contains(151));
1093     }
1094
1095     #[test]
1096     fn test_bit_set_basic() {
1097         let mut b = BitSet::new();
1098         assert!(b.insert(3));
1099         assert!(!b.insert(3));
1100         assert!(b.contains(3));
1101         assert!(b.insert(4));
1102         assert!(!b.insert(4));
1103         assert!(b.contains(3));
1104         assert!(b.insert(400));
1105         assert!(!b.insert(400));
1106         assert!(b.contains(400));
1107         assert_eq!(b.len(), 3);
1108     }
1109
1110     #[test]
1111     fn test_bit_set_intersection() {
1112         let mut a = BitSet::new();
1113         let mut b = BitSet::new();
1114
1115         assert!(a.insert(11));
1116         assert!(a.insert(1));
1117         assert!(a.insert(3));
1118         assert!(a.insert(77));
1119         assert!(a.insert(103));
1120         assert!(a.insert(5));
1121
1122         assert!(b.insert(2));
1123         assert!(b.insert(11));
1124         assert!(b.insert(77));
1125         assert!(b.insert(5));
1126         assert!(b.insert(3));
1127
1128         let expected = [3, 5, 11, 77];
1129         let actual: Vec<_> = a.intersection(&b).collect();
1130         assert_eq!(actual, expected);
1131     }
1132
1133     #[test]
1134     fn test_bit_set_difference() {
1135         let mut a = BitSet::new();
1136         let mut b = BitSet::new();
1137
1138         assert!(a.insert(1));
1139         assert!(a.insert(3));
1140         assert!(a.insert(5));
1141         assert!(a.insert(200));
1142         assert!(a.insert(500));
1143
1144         assert!(b.insert(3));
1145         assert!(b.insert(200));
1146
1147         let expected = [1, 5, 500];
1148         let actual: Vec<_> = a.difference(&b).collect();
1149         assert_eq!(actual, expected);
1150     }
1151
1152     #[test]
1153     fn test_bit_set_symmetric_difference() {
1154         let mut a = BitSet::new();
1155         let mut b = BitSet::new();
1156
1157         assert!(a.insert(1));
1158         assert!(a.insert(3));
1159         assert!(a.insert(5));
1160         assert!(a.insert(9));
1161         assert!(a.insert(11));
1162
1163         assert!(b.insert(3));
1164         assert!(b.insert(9));
1165         assert!(b.insert(14));
1166         assert!(b.insert(220));
1167
1168         let expected = [1, 5, 11, 14, 220];
1169         let actual: Vec<_> = a.symmetric_difference(&b).collect();
1170         assert_eq!(actual, expected);
1171     }
1172
1173     #[test]
1174     fn test_bit_set_union() {
1175         let mut a = BitSet::new();
1176         let mut b = BitSet::new();
1177         assert!(a.insert(1));
1178         assert!(a.insert(3));
1179         assert!(a.insert(5));
1180         assert!(a.insert(9));
1181         assert!(a.insert(11));
1182         assert!(a.insert(160));
1183         assert!(a.insert(19));
1184         assert!(a.insert(24));
1185         assert!(a.insert(200));
1186
1187         assert!(b.insert(1));
1188         assert!(b.insert(5));
1189         assert!(b.insert(9));
1190         assert!(b.insert(13));
1191         assert!(b.insert(19));
1192
1193         let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
1194         let actual: Vec<_> = a.union(&b).collect();
1195         assert_eq!(actual, expected);
1196     }
1197
1198     #[test]
1199     fn test_bit_set_subset() {
1200         let mut set1 = BitSet::new();
1201         let mut set2 = BitSet::new();
1202
1203         assert!(set1.is_subset(&set2)); //  {}  {}
1204         set2.insert(100);
1205         assert!(set1.is_subset(&set2)); //  {}  { 1 }
1206         set2.insert(200);
1207         assert!(set1.is_subset(&set2)); //  {}  { 1, 2 }
1208         set1.insert(200);
1209         assert!(set1.is_subset(&set2)); //  { 2 }  { 1, 2 }
1210         set1.insert(300);
1211         assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 1, 2 }
1212         set2.insert(300);
1213         assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3 }
1214         set2.insert(400);
1215         assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3, 4 }
1216         set2.remove(100);
1217         assert!(set1.is_subset(&set2)); // { 2, 3 }  { 2, 3, 4 }
1218         set2.remove(300);
1219         assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 2, 4 }
1220         set1.remove(300);
1221         assert!(set1.is_subset(&set2)); // { 2 }  { 2, 4 }
1222     }
1223
1224     #[test]
1225     fn test_bit_set_is_disjoint() {
1226         let a = BitSet::from_bytes(&[0b10100010]);
1227         let b = BitSet::from_bytes(&[0b01000000]);
1228         let c = BitSet::new();
1229         let d = BitSet::from_bytes(&[0b00110000]);
1230
1231         assert!(!a.is_disjoint(&d));
1232         assert!(!d.is_disjoint(&a));
1233
1234         assert!(a.is_disjoint(&b));
1235         assert!(a.is_disjoint(&c));
1236         assert!(b.is_disjoint(&a));
1237         assert!(b.is_disjoint(&c));
1238         assert!(c.is_disjoint(&a));
1239         assert!(c.is_disjoint(&b));
1240     }
1241
1242     #[test]
1243     fn test_bit_set_union_with() {
1244         //a should grow to include larger elements
1245         let mut a = BitSet::new();
1246         a.insert(0);
1247         let mut b = BitSet::new();
1248         b.insert(5);
1249         let expected = BitSet::from_bytes(&[0b10000100]);
1250         a.union_with(&b);
1251         assert_eq!(a, expected);
1252
1253         // Standard
1254         let mut a = BitSet::from_bytes(&[0b10100010]);
1255         let mut b = BitSet::from_bytes(&[0b01100010]);
1256         let c = a.clone();
1257         a.union_with(&b);
1258         b.union_with(&c);
1259         assert_eq!(a.len(), 4);
1260         assert_eq!(b.len(), 4);
1261     }
1262
1263     #[test]
1264     fn test_bit_set_intersect_with() {
1265         // Explicitly 0'ed bits
1266         let mut a = BitSet::from_bytes(&[0b10100010]);
1267         let mut b = BitSet::from_bytes(&[0b00000000]);
1268         let c = a.clone();
1269         a.intersect_with(&b);
1270         b.intersect_with(&c);
1271         assert!(a.is_empty());
1272         assert!(b.is_empty());
1273
1274         // Uninitialized bits should behave like 0's
1275         let mut a = BitSet::from_bytes(&[0b10100010]);
1276         let mut b = BitSet::new();
1277         let c = a.clone();
1278         a.intersect_with(&b);
1279         b.intersect_with(&c);
1280         assert!(a.is_empty());
1281         assert!(b.is_empty());
1282
1283         // Standard
1284         let mut a = BitSet::from_bytes(&[0b10100010]);
1285         let mut b = BitSet::from_bytes(&[0b01100010]);
1286         let c = a.clone();
1287         a.intersect_with(&b);
1288         b.intersect_with(&c);
1289         assert_eq!(a.len(), 2);
1290         assert_eq!(b.len(), 2);
1291     }
1292
1293     #[test]
1294     fn test_bit_set_difference_with() {
1295         // Explicitly 0'ed bits
1296         let mut a = BitSet::from_bytes(&[0b00000000]);
1297         let b = BitSet::from_bytes(&[0b10100010]);
1298         a.difference_with(&b);
1299         assert!(a.is_empty());
1300
1301         // Uninitialized bits should behave like 0's
1302         let mut a = BitSet::new();
1303         let b = BitSet::from_bytes(&[0b11111111]);
1304         a.difference_with(&b);
1305         assert!(a.is_empty());
1306
1307         // Standard
1308         let mut a = BitSet::from_bytes(&[0b10100010]);
1309         let mut b = BitSet::from_bytes(&[0b01100010]);
1310         let c = a.clone();
1311         a.difference_with(&b);
1312         b.difference_with(&c);
1313         assert_eq!(a.len(), 1);
1314         assert_eq!(b.len(), 1);
1315     }
1316
1317     #[test]
1318     fn test_bit_set_symmetric_difference_with() {
1319         //a should grow to include larger elements
1320         let mut a = BitSet::new();
1321         a.insert(0);
1322         a.insert(1);
1323         let mut b = BitSet::new();
1324         b.insert(1);
1325         b.insert(5);
1326         let expected = BitSet::from_bytes(&[0b10000100]);
1327         a.symmetric_difference_with(&b);
1328         assert_eq!(a, expected);
1329
1330         let mut a = BitSet::from_bytes(&[0b10100010]);
1331         let b = BitSet::new();
1332         let c = a.clone();
1333         a.symmetric_difference_with(&b);
1334         assert_eq!(a, c);
1335
1336         // Standard
1337         let mut a = BitSet::from_bytes(&[0b11100010]);
1338         let mut b = BitSet::from_bytes(&[0b01101010]);
1339         let c = a.clone();
1340         a.symmetric_difference_with(&b);
1341         b.symmetric_difference_with(&c);
1342         assert_eq!(a.len(), 2);
1343         assert_eq!(b.len(), 2);
1344     }
1345
1346     #[test]
1347     fn test_bit_set_eq() {
1348         let a = BitSet::from_bytes(&[0b10100010]);
1349         let b = BitSet::from_bytes(&[0b00000000]);
1350         let c = BitSet::new();
1351
1352         assert!(a == a);
1353         assert!(a != b);
1354         assert!(a != c);
1355         assert!(b == b);
1356         assert!(b == c);
1357         assert!(c == c);
1358     }
1359
1360     #[test]
1361     fn test_bit_set_cmp() {
1362         let a = BitSet::from_bytes(&[0b10100010]);
1363         let b = BitSet::from_bytes(&[0b00000000]);
1364         let c = BitSet::new();
1365
1366         assert_eq!(a.cmp(&b), Greater);
1367         assert_eq!(a.cmp(&c), Greater);
1368         assert_eq!(b.cmp(&a), Less);
1369         assert_eq!(b.cmp(&c), Equal);
1370         assert_eq!(c.cmp(&a), Less);
1371         assert_eq!(c.cmp(&b), Equal);
1372     }
1373
1374     #[test]
1375     fn test_bit_vec_remove() {
1376         let mut a = BitSet::new();
1377
1378         assert!(a.insert(1));
1379         assert!(a.remove(1));
1380
1381         assert!(a.insert(100));
1382         assert!(a.remove(100));
1383
1384         assert!(a.insert(1000));
1385         assert!(a.remove(1000));
1386         a.shrink_to_fit();
1387     }
1388
1389     #[test]
1390     fn test_bit_vec_clone() {
1391         let mut a = BitSet::new();
1392
1393         assert!(a.insert(1));
1394         assert!(a.insert(100));
1395         assert!(a.insert(1000));
1396
1397         let mut b = a.clone();
1398
1399         assert!(a == b);
1400
1401         assert!(b.remove(1));
1402         assert!(a.contains(1));
1403
1404         assert!(a.remove(1000));
1405         assert!(b.contains(1000));
1406     }
1407
1408     /*
1409         #[test]
1410         fn test_bit_set_append() {
1411             let mut a = BitSet::new();
1412             a.insert(2);
1413             a.insert(6);
1414
1415             let mut b = BitSet::new();
1416             b.insert(1);
1417             b.insert(3);
1418             b.insert(6);
1419
1420             a.append(&mut b);
1421
1422             assert_eq!(a.len(), 4);
1423             assert_eq!(b.len(), 0);
1424             assert!(b.capacity() >= 6);
1425
1426             assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
1427         }
1428
1429         #[test]
1430         fn test_bit_set_split_off() {
1431             // Split at 0
1432             let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1433                                              0b00110011, 0b01101011, 0b10101101]);
1434
1435             let b = a.split_off(0);
1436
1437             assert_eq!(a.len(), 0);
1438             assert_eq!(b.len(), 21);
1439
1440             assert_eq!(b, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1441                                                0b00110011, 0b01101011, 0b10101101]);
1442
1443             // Split behind last element
1444             let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1445                                              0b00110011, 0b01101011, 0b10101101]);
1446
1447             let b = a.split_off(50);
1448
1449             assert_eq!(a.len(), 21);
1450             assert_eq!(b.len(), 0);
1451
1452             assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1453                                                0b00110011, 0b01101011, 0b10101101]));
1454
1455             // Split at arbitrary element
1456             let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1457                                              0b00110011, 0b01101011, 0b10101101]);
1458
1459             let b = a.split_off(34);
1460
1461             assert_eq!(a.len(), 12);
1462             assert_eq!(b.len(), 9);
1463
1464             assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1465                                                0b00110011, 0b01000000]));
1466             assert_eq!(b, BitSet::from_bytes(&[0, 0, 0, 0,
1467                                                0b00101011, 0b10101101]));
1468         }
1469     */
1470 }
1471
1472 #[cfg(all(test, feature = "nightly"))]
1473 mod bench {
1474     use super::BitSet;
1475     use bit_vec::BitVec;
1476     use rand::{thread_rng, Rng, ThreadRng};
1477
1478     use test::{black_box, Bencher};
1479
1480     const BENCH_BITS: usize = 1 << 14;
1481     const BITS: usize = 32;
1482
1483     fn rng() -> ThreadRng {
1484         thread_rng()
1485     }
1486
1487     #[bench]
1488     fn bench_bit_vecset_small(b: &mut Bencher) {
1489         let mut r = rng();
1490         let mut bit_vec = BitSet::new();
1491         b.iter(|| {
1492             for _ in 0..100 {
1493                 bit_vec.insert((r.next_u32() as usize) % BITS);
1494             }
1495             black_box(&bit_vec);
1496         });
1497     }
1498
1499     #[bench]
1500     fn bench_bit_vecset_big(b: &mut Bencher) {
1501         let mut r = rng();
1502         let mut bit_vec = BitSet::new();
1503         b.iter(|| {
1504             for _ in 0..100 {
1505                 bit_vec.insert((r.next_u32() as usize) % BENCH_BITS);
1506             }
1507             black_box(&bit_vec);
1508         });
1509     }
1510
1511     #[bench]
1512     fn bench_bit_vecset_iter(b: &mut Bencher) {
1513         let bit_vec = BitSet::from_bit_vec(BitVec::from_fn(BENCH_BITS, |idx| idx % 3 == 0));
1514         b.iter(|| {
1515             let mut sum = 0;
1516             for idx in &bit_vec {
1517                 sum += idx as usize;
1518             }
1519             sum
1520         })
1521     }
1522 }