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