src/libcollections/bit.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 // FIXME(Gankro): BitVec and BitSet are very tightly coupled. Ideally (for
  12 // maintenance), they should be in separate files/modules, with BitSet only
  13 // using BitVec's public API. This will be hard for performance though, because
  14 // `BitVec` will not want to leak its internal representation while its internal
  15 // representation as `u32`s must be assumed for best performance.
  16
  17 // FIXME(tbu-): `BitVec`'s methods shouldn't be `union`, `intersection`, but
  18 // rather `or` and `and`.
  19
  20 // (1) Be careful, most things can overflow here because the amount of bits in
  21 //     memory can overflow `usize`.
  22 // (2) Make sure that the underlying vector has no excess length:
  23 //     E. g. `nbits == 16`, `storage.len() == 2` would be excess length,
  24 //     because the last word isn't used at all. This is important because some
  25 //     methods rely on it (for *CORRECTNESS*).
  26 // (3) Make sure that the unused bits in the last word are zeroed out, again
  27 //     other methods rely on it for *CORRECTNESS*.
  28 // (4) `BitSet` is tightly coupled with `BitVec`, so any changes you make in
  29 // `BitVec` will need to be reflected in `BitSet`.
  30
  31 //! Collections implemented with bit vectors.
  32 //!
  33 //! # Examples
  34 //!
  35 //! This is a simple example of the [Sieve of Eratosthenes][sieve]
  36 //! which calculates prime numbers up to a given limit.
  37 //!
  38 //! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
  39 //!
  40 //! ```
  41 //! # #![feature(collections, core, step_by)]
  42 //! use std::collections::{BitSet, BitVec};
  43 //! use std::iter;
  44 //!
  45 //! let max_prime = 10000;
  46 //!
  47 //! // Store the primes as a BitSet
  48 //! let primes = {
  49 //!     // Assume all numbers are prime to begin, and then we
  50 //!     // cross off non-primes progressively
  51 //!     let mut bv = BitVec::from_elem(max_prime, true);
  52 //!
  53 //!     // Neither 0 nor 1 are prime
  54 //!     bv.set(0, false);
  55 //!     bv.set(1, false);
  56 //!
  57 //!     for i in iter::range_inclusive(2, (max_prime as f64).sqrt() as usize) {
  58 //!         // if i is a prime
  59 //!         if bv[i] {
  60 //!             // Mark all multiples of i as non-prime (any multiples below i * i
  61 //!             // will have been marked as non-prime previously)
  62 //!             for j in (i * i..max_prime).step_by(i) { bv.set(j, false) }
  63 //!         }
  64 //!     }
  65 //!     BitSet::from_bit_vec(bv)
  66 //! };
  67 //!
  68 //! // Simple primality tests below our max bound
  69 //! let print_primes = 20;
  70 //! print!("The primes below {} are: ", print_primes);
  71 //! for x in 0..print_primes {
  72 //!     if primes.contains(&x) {
  73 //!         print!("{} ", x);
  74 //!     }
  75 //! }
  76 //! println!("");
  77 //!
  78 //! // We can manipulate the internal BitVec
  79 //! let num_primes = primes.get_ref().iter().filter(|x| *x).count();
  80 //! println!("There are {} primes below {}", num_primes, max_prime);
  81 //! ```
  82
  83 use core::prelude::*;
  84
  85 use core::cmp::Ordering;
  86 use core::cmp;
  87 use core::fmt;
  88 use core::hash;
  89 use core::iter::RandomAccessIterator;
  90 use core::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat, Cloned};
  91 use core::iter::{self, FromIterator};
  92 use core::mem::swap;
  93 use core::ops::Index;
  94 use core::slice;
  95 use core::{u8, u32, usize};
  96 use bit_set; //so meta
  97
  98 use Vec;
  99
 100 type Blocks<'a> = Cloned<slice::Iter<'a, u32>>;
 101 type MutBlocks<'a> = slice::IterMut<'a, u32>;
 102 type MatchWords<'a> = Chain<Enumerate<Blocks<'a>>, Skip<Take<Enumerate<Repeat<u32>>>>>;
 103
 104 fn reverse_bits(byte: u8) -> u8 {
 105     let mut result = 0;
 106     for i in 0..u8::BITS {
 107         result |= ((byte >> i) & 1) << (u8::BITS - 1 - i);
 108     }
 109     result
 110 }
 111
 112 // Take two BitVec's, and return iterators of their words, where the shorter one
 113 // has been padded with 0's
 114 fn match_words <'a,'b>(a: &'a BitVec, b: &'b BitVec) -> (MatchWords<'a>, MatchWords<'b>) {
 115     let a_len = a.storage.len();
 116     let b_len = b.storage.len();
 117
 118     // have to uselessly pretend to pad the longer one for type matching
 119     if a_len < b_len {
 120         (a.blocks().enumerate().chain(iter::repeat(0).enumerate().take(b_len).skip(a_len)),
 121          b.blocks().enumerate().chain(iter::repeat(0).enumerate().take(0).skip(0)))
 122     } else {
 123         (a.blocks().enumerate().chain(iter::repeat(0).enumerate().take(0).skip(0)),
 124          b.blocks().enumerate().chain(iter::repeat(0).enumerate().take(a_len).skip(b_len)))
 125     }
 126 }
 127
 128 static TRUE: bool = true;
 129 static FALSE: bool = false;
 130
 131 /// The bitvector type.
 132 ///
 133 /// # Examples
 134 ///
 135 /// ```
 136 /// # #![feature(collections)]
 137 /// use std::collections::BitVec;
 138 ///
 139 /// let mut bv = BitVec::from_elem(10, false);
 140 ///
 141 /// // insert all primes less than 10
 142 /// bv.set(2, true);
 143 /// bv.set(3, true);
 144 /// bv.set(5, true);
 145 /// bv.set(7, true);
 146 /// println!("{:?}", bv);
 147 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
 148 ///
 149 /// // flip all values in bitvector, producing non-primes less than 10
 150 /// bv.negate();
 151 /// println!("{:?}", bv);
 152 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
 153 ///
 154 /// // reset bitvector to empty
 155 /// bv.clear();
 156 /// println!("{:?}", bv);
 157 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
 158 /// ```
 159 #[unstable(feature = "collections",
 160            reason = "RFC 509")]
 161 pub struct BitVec {
 162     /// Internal representation of the bit vector
 163     storage: Vec<u32>,
 164     /// The number of valid bits in the internal representation
 165     nbits: usize
 166 }
 167
 168 // FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
 169 impl Index<usize> for BitVec {
 170     type Output = bool;
 171
 172     #[inline]
 173     fn index(&self, i: usize) -> &bool {
 174         if self.get(i).expect("index out of bounds") {
 175             &TRUE
 176         } else {
 177             &FALSE
 178         }
 179     }
 180 }
 181
 182 /// Computes how many blocks are needed to store that many bits
 183 fn blocks_for_bits(bits: usize) -> usize {
 184     // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
 185     // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
 186     // one too many. So we need to check if that's the case. We can do that by computing if
 187     // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
 188     // superior modulo operator on a power of two to this.
 189     //
 190     // Note that we can technically avoid this branch with the expression
 191     // `(nbits + u32::BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
 192     if bits % u32::BITS == 0 {
 193         bits / u32::BITS
 194     } else {
 195         bits / u32::BITS + 1
 196     }
 197 }
 198
 199 /// Computes the bitmask for the final word of the vector
 200 fn mask_for_bits(bits: usize) -> u32 {
 201     // Note especially that a perfect multiple of u32::BITS should mask all 1s.
 202     !0 >> (u32::BITS - bits % u32::BITS) % u32::BITS
 203 }
 204
 205 impl BitVec {
 206     /// Applies the given operation to the blocks of self and other, and sets
 207     /// self to be the result. This relies on the caller not to corrupt the
 208     /// last word.
 209     #[inline]
 210     fn process<F>(&mut self, other: &BitVec, mut op: F) -> bool where F: FnMut(u32, u32) -> u32 {
 211         assert_eq!(self.len(), other.len());
 212         // This could theoretically be a `debug_assert!`.
 213         assert_eq!(self.storage.len(), other.storage.len());
 214         let mut changed_bits = 0;
 215         for (a, b) in self.blocks_mut().zip(other.blocks()) {
 216             let w = op(*a, b);
 217             changed_bits |= *a ^ w;
 218             *a = w;
 219         }
 220         changed_bits != 0
 221     }
 222
 223     /// Iterator over mutable refs to  the underlying blocks of data.
 224     fn blocks_mut(&mut self) -> MutBlocks {
 225         // (2)
 226         self.storage.iter_mut()
 227     }
 228
 229     /// Iterator over the underlying blocks of data
 230     fn blocks(&self) -> Blocks {
 231         // (2)
 232         self.storage.iter().cloned()
 233     }
 234
 235     /// An operation might screw up the unused bits in the last block of the
 236     /// `BitVec`. As per (3), it's assumed to be all 0s. This method fixes it up.
 237     fn fix_last_block(&mut self) {
 238         let extra_bits = self.len() % u32::BITS;
 239         if extra_bits > 0 {
 240             let mask = (1 << extra_bits) - 1;
 241             let storage_len = self.storage.len();
 242             self.storage[storage_len - 1] &= mask;
 243         }
 244     }
 245
 246     /// Creates an empty `BitVec`.
 247     ///
 248     /// # Examples
 249     ///
 250     /// ```
 251     /// # #![feature(collections)]
 252     /// use std::collections::BitVec;
 253     /// let mut bv = BitVec::new();
 254     /// ```
 255     #[stable(feature = "rust1", since = "1.0.0")]
 256     pub fn new() -> BitVec {
 257         BitVec { storage: Vec::new(), nbits: 0 }
 258     }
 259
 260     /// Creates a `BitVec` that holds `nbits` elements, setting each element
 261     /// to `bit`.
 262     ///
 263     /// # Examples
 264     ///
 265     /// ```
 266     /// # #![feature(collections)]
 267     /// use std::collections::BitVec;
 268     ///
 269     /// let mut bv = BitVec::from_elem(10, false);
 270     /// assert_eq!(bv.len(), 10);
 271     /// for x in bv.iter() {
 272     ///     assert_eq!(x, false);
 273     /// }
 274     /// ```
 275     pub fn from_elem(nbits: usize, bit: bool) -> BitVec {
 276         let nblocks = blocks_for_bits(nbits);
 277         let mut bit_vec = BitVec {
 278             storage: repeat(if bit { !0 } else { 0 }).take(nblocks).collect(),
 279             nbits: nbits
 280         };
 281         bit_vec.fix_last_block();
 282         bit_vec
 283     }
 284
 285     /// Constructs a new, empty `BitVec` with the specified capacity.
 286     ///
 287     /// The bitvector will be able to hold at least `capacity` bits without
 288     /// reallocating. If `capacity` is 0, it will not allocate.
 289     ///
 290     /// It is important to note that this function does not specify the
 291     /// *length* of the returned bitvector, but only the *capacity*.
 292     #[stable(feature = "rust1", since = "1.0.0")]
 293     pub fn with_capacity(nbits: usize) -> BitVec {
 294         BitVec {
 295             storage: Vec::with_capacity(blocks_for_bits(nbits)),
 296             nbits: 0,
 297         }
 298     }
 299
 300     /// Transforms a byte-vector into a `BitVec`. Each byte becomes eight bits,
 301     /// with the most significant bits of each byte coming first. Each
 302     /// bit becomes `true` if equal to 1 or `false` if equal to 0.
 303     ///
 304     /// # Examples
 305     ///
 306     /// ```
 307     /// # #![feature(collections)]
 308     /// use std::collections::BitVec;
 309     ///
 310     /// let bv = BitVec::from_bytes(&[0b10100000, 0b00010010]);
 311     /// assert!(bv.eq_vec(&[true, false, true, false,
 312     ///                     false, false, false, false,
 313     ///                     false, false, false, true,
 314     ///                     false, false, true, false]));
 315     /// ```
 316     pub fn from_bytes(bytes: &[u8]) -> BitVec {
 317         let len = bytes.len().checked_mul(u8::BITS).expect("capacity overflow");
 318         let mut bit_vec = BitVec::with_capacity(len);
 319         let complete_words = bytes.len() / 4;
 320         let extra_bytes = bytes.len() % 4;
 321
 322         bit_vec.nbits = len;
 323
 324         for i in 0..complete_words {
 325             bit_vec.storage.push(
 326                 ((reverse_bits(bytes[i * 4 + 0]) as u32) << 0) |
 327                 ((reverse_bits(bytes[i * 4 + 1]) as u32) << 8) |
 328                 ((reverse_bits(bytes[i * 4 + 2]) as u32) << 16) |
 329                 ((reverse_bits(bytes[i * 4 + 3]) as u32) << 24)
 330             );
 331         }
 332
 333         if extra_bytes > 0 {
 334             let mut last_word = 0;
 335             for (i, &byte) in bytes[complete_words*4..].iter().enumerate() {
 336                 last_word |= (reverse_bits(byte) as u32) << (i * 8);
 337             }
 338             bit_vec.storage.push(last_word);
 339         }
 340
 341         bit_vec
 342     }
 343
 344     /// Creates a `BitVec` of the specified length where the value at each index
 345     /// is `f(index)`.
 346     ///
 347     /// # Examples
 348     ///
 349     /// ```
 350     /// # #![feature(collections)]
 351     /// use std::collections::BitVec;
 352     ///
 353     /// let bv = BitVec::from_fn(5, |i| { i % 2 == 0 });
 354     /// assert!(bv.eq_vec(&[true, false, true, false, true]));
 355     /// ```
 356     pub fn from_fn<F>(len: usize, mut f: F) -> BitVec where F: FnMut(usize) -> bool {
 357         let mut bit_vec = BitVec::from_elem(len, false);
 358         for i in 0..len {
 359             bit_vec.set(i, f(i));
 360         }
 361         bit_vec
 362     }
 363
 364     /// Retrieves the value at index `i`, or `None` if the index is out of bounds.
 365     ///
 366     /// # Examples
 367     ///
 368     /// ```
 369     /// # #![feature(collections)]
 370     /// use std::collections::BitVec;
 371     ///
 372     /// let bv = BitVec::from_bytes(&[0b01100000]);
 373     /// assert_eq!(bv.get(0), Some(false));
 374     /// assert_eq!(bv.get(1), Some(true));
 375     /// assert_eq!(bv.get(100), None);
 376     ///
 377     /// // Can also use array indexing
 378     /// assert_eq!(bv[1], true);
 379     /// ```
 380     #[inline]
 381     #[stable(feature = "rust1", since = "1.0.0")]
 382     pub fn get(&self, i: usize) -> Option<bool> {
 383         if i >= self.nbits {
 384             return None;
 385         }
 386         let w = i / u32::BITS;
 387         let b = i % u32::BITS;
 388         self.storage.get(w).map(|&block|
 389             (block & (1 << b)) != 0
 390         )
 391     }
 392
 393     /// Sets the value of a bit at an index `i`.
 394     ///
 395     /// # Panics
 396     ///
 397     /// Panics if `i` is out of bounds.
 398     ///
 399     /// # Examples
 400     ///
 401     /// ```
 402     /// # #![feature(collections)]
 403     /// use std::collections::BitVec;
 404     ///
 405     /// let mut bv = BitVec::from_elem(5, false);
 406     /// bv.set(3, true);
 407     /// assert_eq!(bv[3], true);
 408     /// ```
 409     #[inline]
 410     #[unstable(feature = "collections",
 411                reason = "panic semantics are likely to change in the future")]
 412     pub fn set(&mut self, i: usize, x: bool) {
 413         assert!(i < self.nbits);
 414         let w = i / u32::BITS;
 415         let b = i % u32::BITS;
 416         let flag = 1 << b;
 417         let val = if x { self.storage[w] | flag }
 418                   else { self.storage[w] & !flag };
 419         self.storage[w] = val;
 420     }
 421
 422     /// Sets all bits to 1.
 423     ///
 424     /// # Examples
 425     ///
 426     /// ```
 427     /// # #![feature(collections)]
 428     /// use std::collections::BitVec;
 429     ///
 430     /// let before = 0b01100000;
 431     /// let after  = 0b11111111;
 432     ///
 433     /// let mut bv = BitVec::from_bytes(&[before]);
 434     /// bv.set_all();
 435     /// assert_eq!(bv, BitVec::from_bytes(&[after]));
 436     /// ```
 437     #[inline]
 438     pub fn set_all(&mut self) {
 439         for w in &mut self.storage { *w = !0; }
 440         self.fix_last_block();
 441     }
 442
 443     /// Flips all bits.
 444     ///
 445     /// # Examples
 446     ///
 447     /// ```
 448     /// # #![feature(collections)]
 449     /// use std::collections::BitVec;
 450     ///
 451     /// let before = 0b01100000;
 452     /// let after  = 0b10011111;
 453     ///
 454     /// let mut bv = BitVec::from_bytes(&[before]);
 455     /// bv.negate();
 456     /// assert_eq!(bv, BitVec::from_bytes(&[after]));
 457     /// ```
 458     #[inline]
 459     pub fn negate(&mut self) {
 460         for w in &mut self.storage { *w = !*w; }
 461         self.fix_last_block();
 462     }
 463
 464     /// Calculates the union of two bitvectors. This acts like the bitwise `or`
 465     /// function.
 466     ///
 467     /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
 468     /// the same length. Returns `true` if `self` changed.
 469     ///
 470     /// # Panics
 471     ///
 472     /// Panics if the bitvectors are of different lengths.
 473     ///
 474     /// # Examples
 475     ///
 476     /// ```
 477     /// # #![feature(collections)]
 478     /// use std::collections::BitVec;
 479     ///
 480     /// let a   = 0b01100100;
 481     /// let b   = 0b01011010;
 482     /// let res = 0b01111110;
 483     ///
 484     /// let mut a = BitVec::from_bytes(&[a]);
 485     /// let b = BitVec::from_bytes(&[b]);
 486     ///
 487     /// assert!(a.union(&b));
 488     /// assert_eq!(a, BitVec::from_bytes(&[res]));
 489     /// ```
 490     #[inline]
 491     pub fn union(&mut self, other: &BitVec) -> bool {
 492         self.process(other, |w1, w2| w1 | w2)
 493     }
 494
 495     /// Calculates the intersection of two bitvectors. This acts like the
 496     /// bitwise `and` function.
 497     ///
 498     /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
 499     /// must be the same length. Returns `true` if `self` changed.
 500     ///
 501     /// # Panics
 502     ///
 503     /// Panics if the bitvectors are of different lengths.
 504     ///
 505     /// # Examples
 506     ///
 507     /// ```
 508     /// # #![feature(collections)]
 509     /// use std::collections::BitVec;
 510     ///
 511     /// let a   = 0b01100100;
 512     /// let b   = 0b01011010;
 513     /// let res = 0b01000000;
 514     ///
 515     /// let mut a = BitVec::from_bytes(&[a]);
 516     /// let b = BitVec::from_bytes(&[b]);
 517     ///
 518     /// assert!(a.intersect(&b));
 519     /// assert_eq!(a, BitVec::from_bytes(&[res]));
 520     /// ```
 521     #[inline]
 522     pub fn intersect(&mut self, other: &BitVec) -> bool {
 523         self.process(other, |w1, w2| w1 & w2)
 524     }
 525
 526     /// Calculates the difference between two bitvectors.
 527     ///
 528     /// Sets each element of `self` to the value of that element minus the
 529     /// element of `other` at the same index. Both bitvectors must be the same
 530     /// length. Returns `true` if `self` changed.
 531     ///
 532     /// # Panics
 533     ///
 534     /// Panics if the bitvectors are of different length.
 535     ///
 536     /// # Examples
 537     ///
 538     /// ```
 539     /// # #![feature(collections)]
 540     /// use std::collections::BitVec;
 541     ///
 542     /// let a   = 0b01100100;
 543     /// let b   = 0b01011010;
 544     /// let a_b = 0b00100100; // a - b
 545     /// let b_a = 0b00011010; // b - a
 546     ///
 547     /// let mut bva = BitVec::from_bytes(&[a]);
 548     /// let bvb = BitVec::from_bytes(&[b]);
 549     ///
 550     /// assert!(bva.difference(&bvb));
 551     /// assert_eq!(bva, BitVec::from_bytes(&[a_b]));
 552     ///
 553     /// let bva = BitVec::from_bytes(&[a]);
 554     /// let mut bvb = BitVec::from_bytes(&[b]);
 555     ///
 556     /// assert!(bvb.difference(&bva));
 557     /// assert_eq!(bvb, BitVec::from_bytes(&[b_a]));
 558     /// ```
 559     #[inline]
 560     pub fn difference(&mut self, other: &BitVec) -> bool {
 561         self.process(other, |w1, w2| w1 & !w2)
 562     }
 563
 564     /// Returns `true` if all bits are 1.
 565     ///
 566     /// # Examples
 567     ///
 568     /// ```
 569     /// # #![feature(collections)]
 570     /// use std::collections::BitVec;
 571     ///
 572     /// let mut bv = BitVec::from_elem(5, true);
 573     /// assert_eq!(bv.all(), true);
 574     ///
 575     /// bv.set(1, false);
 576     /// assert_eq!(bv.all(), false);
 577     /// ```
 578     pub fn all(&self) -> bool {
 579         let mut last_word = !0;
 580         // Check that every block but the last is all-ones...
 581         self.blocks().all(|elem| {
 582             let tmp = last_word;
 583             last_word = elem;
 584             tmp == !0
 585         // and then check the last one has enough ones
 586         }) && (last_word == mask_for_bits(self.nbits))
 587     }
 588
 589     /// Returns an iterator over the elements of the vector in order.
 590     ///
 591     /// # Examples
 592     ///
 593     /// ```
 594     /// # #![feature(collections)]
 595     /// use std::collections::BitVec;
 596     ///
 597     /// let bv = BitVec::from_bytes(&[0b01110100, 0b10010010]);
 598     /// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
 599     /// ```
 600     #[inline]
 601     #[stable(feature = "rust1", since = "1.0.0")]
 602     pub fn iter(&self) -> Iter {
 603         Iter { bit_vec: self, next_idx: 0, end_idx: self.nbits }
 604     }
 605
 606     /// Moves all bits from `other` into `Self`, leaving `other` empty.
 607     ///
 608     /// # Examples
 609     ///
 610     /// ```
 611     /// # #![feature(collections, bit_vec_append_split_off)]
 612     /// use std::collections::BitVec;
 613     ///
 614     /// let mut a = BitVec::from_bytes(&[0b10000000]);
 615     /// let mut b = BitVec::from_bytes(&[0b01100001]);
 616     ///
 617     /// a.append(&mut b);
 618     ///
 619     /// assert_eq!(a.len(), 16);
 620     /// assert_eq!(b.len(), 0);
 621     /// assert!(a.eq_vec(&[true, false, false, false, false, false, false, false,
 622     ///                    false, true, true, false, false, false, false, true]));
 623     /// ```
 624     #[unstable(feature = "bit_vec_append_split_off",
 625                reason = "recently added as part of collections reform 2")]
 626     pub fn append(&mut self, other: &mut Self) {
 627         let b = self.len() % u32::BITS;
 628
 629         self.nbits += other.len();
 630         other.nbits = 0;
 631
 632         if b == 0 {
 633             self.storage.append(&mut other.storage);
 634         } else {
 635             self.storage.reserve(other.storage.len());
 636
 637             for block in other.storage.drain(..) {
 638                 *(self.storage.last_mut().unwrap()) |= block << b;
 639                 self.storage.push(block >> (u32::BITS - b));
 640             }
 641         }
 642     }
 643
 644     /// Splits the `BitVec` into two at the given bit,
 645     /// retaining the first half in-place and returning the second one.
 646     ///
 647     /// # Panics
 648     ///
 649     /// Panics if `at` is out of bounds.
 650     ///
 651     /// # Examples
 652     ///
 653     /// ```
 654     /// # #![feature(collections, bit_vec_append_split_off)]
 655     /// use std::collections::BitVec;
 656     /// let mut a = BitVec::new();
 657     /// a.push(true);
 658     /// a.push(false);
 659     /// a.push(false);
 660     /// a.push(true);
 661     ///
 662     /// let b = a.split_off(2);
 663     ///
 664     /// assert_eq!(a.len(), 2);
 665     /// assert_eq!(b.len(), 2);
 666     /// assert!(a.eq_vec(&[true, false]));
 667     /// assert!(b.eq_vec(&[false, true]));
 668     /// ```
 669     #[unstable(feature = "bit_vec_append_split_off",
 670                reason = "recently added as part of collections reform 2")]
 671     pub fn split_off(&mut self, at: usize) -> Self {
 672         assert!(at <= self.len(), "`at` out of bounds");
 673
 674         let mut other = BitVec::new();
 675
 676         if at == 0 {
 677             swap(self, &mut other);
 678             return other;
 679         } else if at == self.len() {
 680             return other;
 681         }
 682
 683         let w = at / u32::BITS;
 684         let b = at % u32::BITS;
 685         other.nbits = self.nbits - at;
 686         self.nbits = at;
 687         if b == 0 {
 688             // Split at block boundary
 689             other.storage = self.storage.split_off(w);
 690         } else {
 691             other.storage.reserve(self.storage.len() - w);
 692
 693             {
 694                 let mut iter = self.storage[w..].iter();
 695                 let mut last = *iter.next().unwrap();
 696                 for &cur in iter {
 697                     other.storage.push((last >> b) | (cur << (u32::BITS - b)));
 698                     last = cur;
 699                 }
 700                 other.storage.push(last >> b);
 701             }
 702
 703             self.storage.truncate(w+1);
 704             self.fix_last_block();
 705         }
 706
 707         other
 708     }
 709
 710     /// Returns `true` if all bits are 0.
 711     ///
 712     /// # Examples
 713     ///
 714     /// ```
 715     /// # #![feature(collections)]
 716     /// use std::collections::BitVec;
 717     ///
 718     /// let mut bv = BitVec::from_elem(10, false);
 719     /// assert_eq!(bv.none(), true);
 720     ///
 721     /// bv.set(3, true);
 722     /// assert_eq!(bv.none(), false);
 723     /// ```
 724     pub fn none(&self) -> bool {
 725         self.blocks().all(|w| w == 0)
 726     }
 727
 728     /// Returns `true` if any bit is 1.
 729     ///
 730     /// # Examples
 731     ///
 732     /// ```
 733     /// # #![feature(collections)]
 734     /// use std::collections::BitVec;
 735     ///
 736     /// let mut bv = BitVec::from_elem(10, false);
 737     /// assert_eq!(bv.any(), false);
 738     ///
 739     /// bv.set(3, true);
 740     /// assert_eq!(bv.any(), true);
 741     /// ```
 742     #[inline]
 743     pub fn any(&self) -> bool {
 744         !self.none()
 745     }
 746
 747     /// Organises the bits into bytes, such that the first bit in the
 748     /// `BitVec` becomes the high-order bit of the first byte. If the
 749     /// size of the `BitVec` is not a multiple of eight then trailing bits
 750     /// will be filled-in with `false`.
 751     ///
 752     /// # Examples
 753     ///
 754     /// ```
 755     /// # #![feature(collections)]
 756     /// use std::collections::BitVec;
 757     ///
 758     /// let mut bv = BitVec::from_elem(3, true);
 759     /// bv.set(1, false);
 760     ///
 761     /// assert_eq!(bv.to_bytes(), [0b10100000]);
 762     ///
 763     /// let mut bv = BitVec::from_elem(9, false);
 764     /// bv.set(2, true);
 765     /// bv.set(8, true);
 766     ///
 767     /// assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
 768     /// ```
 769     pub fn to_bytes(&self) -> Vec<u8> {
 770         fn bit(bit_vec: &BitVec, byte: usize, bit: usize) -> u8 {
 771             let offset = byte * 8 + bit;
 772             if offset >= bit_vec.nbits {
 773                 0
 774             } else {
 775                 (bit_vec[offset] as u8) << (7 - bit)
 776             }
 777         }
 778
 779         let len = self.nbits/8 +
 780                   if self.nbits % 8 == 0 { 0 } else { 1 };
 781         (0..len).map(|i|
 782             bit(self, i, 0) |
 783             bit(self, i, 1) |
 784             bit(self, i, 2) |
 785             bit(self, i, 3) |
 786             bit(self, i, 4) |
 787             bit(self, i, 5) |
 788             bit(self, i, 6) |
 789             bit(self, i, 7)
 790         ).collect()
 791     }
 792
 793     /// Compares a `BitVec` to a slice of `bool`s.
 794     /// Both the `BitVec` and slice must have the same length.
 795     ///
 796     /// # Panics
 797     ///
 798     /// Panics if the `BitVec` and slice are of different length.
 799     ///
 800     /// # Examples
 801     ///
 802     /// ```
 803     /// # #![feature(collections)]
 804     /// use std::collections::BitVec;
 805     ///
 806     /// let bv = BitVec::from_bytes(&[0b10100000]);
 807     ///
 808     /// assert!(bv.eq_vec(&[true, false, true, false,
 809     ///                     false, false, false, false]));
 810     /// ```
 811     pub fn eq_vec(&self, v: &[bool]) -> bool {
 812         assert_eq!(self.nbits, v.len());
 813         iter::order::eq(self.iter(), v.iter().cloned())
 814     }
 815
 816     /// Shortens a `BitVec`, dropping excess elements.
 817     ///
 818     /// If `len` is greater than the vector's current length, this has no
 819     /// effect.
 820     ///
 821     /// # Examples
 822     ///
 823     /// ```
 824     /// # #![feature(collections)]
 825     /// use std::collections::BitVec;
 826     ///
 827     /// let mut bv = BitVec::from_bytes(&[0b01001011]);
 828     /// bv.truncate(2);
 829     /// assert!(bv.eq_vec(&[false, true]));
 830     /// ```
 831     #[stable(feature = "rust1", since = "1.0.0")]
 832     pub fn truncate(&mut self, len: usize) {
 833         if len < self.len() {
 834             self.nbits = len;
 835             // This fixes (2).
 836             self.storage.truncate(blocks_for_bits(len));
 837             self.fix_last_block();
 838         }
 839     }
 840
 841     /// Reserves capacity for at least `additional` more bits to be inserted in the given
 842     /// `BitVec`. The collection may reserve more space to avoid frequent reallocations.
 843     ///
 844     /// # Panics
 845     ///
 846     /// Panics if the new capacity overflows `usize`.
 847     ///
 848     /// # Examples
 849     ///
 850     /// ```
 851     /// # #![feature(collections)]
 852     /// use std::collections::BitVec;
 853     ///
 854     /// let mut bv = BitVec::from_elem(3, false);
 855     /// bv.reserve(10);
 856     /// assert_eq!(bv.len(), 3);
 857     /// assert!(bv.capacity() >= 13);
 858     /// ```
 859     #[stable(feature = "rust1", since = "1.0.0")]
 860     pub fn reserve(&mut self, additional: usize) {
 861         let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
 862         let storage_len = self.storage.len();
 863         if desired_cap > self.capacity() {
 864             self.storage.reserve(blocks_for_bits(desired_cap) - storage_len);
 865         }
 866     }
 867
 868     /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the
 869     /// given `BitVec`. Does nothing if the capacity is already sufficient.
 870     ///
 871     /// Note that the allocator may give the collection more space than it requests. Therefore
 872     /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
 873     /// insertions are expected.
 874     ///
 875     /// # Panics
 876     ///
 877     /// Panics if the new capacity overflows `usize`.
 878     ///
 879     /// # Examples
 880     ///
 881     /// ```
 882     /// # #![feature(collections)]
 883     /// use std::collections::BitVec;
 884     ///
 885     /// let mut bv = BitVec::from_elem(3, false);
 886     /// bv.reserve(10);
 887     /// assert_eq!(bv.len(), 3);
 888     /// assert!(bv.capacity() >= 13);
 889     /// ```
 890     #[stable(feature = "rust1", since = "1.0.0")]
 891     pub fn reserve_exact(&mut self, additional: usize) {
 892         let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
 893         let storage_len = self.storage.len();
 894         if desired_cap > self.capacity() {
 895             self.storage.reserve_exact(blocks_for_bits(desired_cap) - storage_len);
 896         }
 897     }
 898
 899     /// Returns the capacity in bits for this bit vector. Inserting any
 900     /// element less than this amount will not trigger a resizing.
 901     ///
 902     /// # Examples
 903     ///
 904     /// ```
 905     /// # #![feature(collections)]
 906     /// use std::collections::BitVec;
 907     ///
 908     /// let mut bv = BitVec::new();
 909     /// bv.reserve(10);
 910     /// assert!(bv.capacity() >= 10);
 911     /// ```
 912     #[inline]
 913     #[stable(feature = "rust1", since = "1.0.0")]
 914     pub fn capacity(&self) -> usize {
 915         self.storage.capacity().checked_mul(u32::BITS).unwrap_or(usize::MAX)
 916     }
 917
 918     /// Grows the `BitVec` in-place, adding `n` copies of `value` to the `BitVec`.
 919     ///
 920     /// # Panics
 921     ///
 922     /// Panics if the new len overflows a `usize`.
 923     ///
 924     /// # Examples
 925     ///
 926     /// ```
 927     /// # #![feature(collections)]
 928     /// use std::collections::BitVec;
 929     ///
 930     /// let mut bv = BitVec::from_bytes(&[0b01001011]);
 931     /// bv.grow(2, true);
 932     /// assert_eq!(bv.len(), 10);
 933     /// assert_eq!(bv.to_bytes(), [0b01001011, 0b11000000]);
 934     /// ```
 935     pub fn grow(&mut self, n: usize, value: bool) {
 936         // Note: we just bulk set all the bits in the last word in this fn in multiple places
 937         // which is technically wrong if not all of these bits are to be used. However, at the end
 938         // of this fn we call `fix_last_block` at the end of this fn, which should fix this.
 939
 940         let new_nbits = self.nbits.checked_add(n).expect("capacity overflow");
 941         let new_nblocks = blocks_for_bits(new_nbits);
 942         let full_value = if value { !0 } else { 0 };
 943
 944         // Correct the old tail word, setting or clearing formerly unused bits
 945         let num_cur_blocks = blocks_for_bits(self.nbits);
 946         if self.nbits % u32::BITS > 0 {
 947             let mask = mask_for_bits(self.nbits);
 948             if value {
 949                 self.storage[num_cur_blocks - 1] |= !mask;
 950             } else {
 951                 // Extra bits are already zero by invariant.
 952             }
 953         }
 954
 955         // Fill in words after the old tail word
 956         let stop_idx = cmp::min(self.storage.len(), new_nblocks);
 957         for idx in num_cur_blocks..stop_idx {
 958             self.storage[idx] = full_value;
 959         }
 960
 961         // Allocate new words, if needed
 962         if new_nblocks > self.storage.len() {
 963             let to_add = new_nblocks - self.storage.len();
 964             self.storage.extend(repeat(full_value).take(to_add));
 965         }
 966
 967         // Adjust internal bit count
 968         self.nbits = new_nbits;
 969
 970         self.fix_last_block();
 971     }
 972
 973     /// Removes the last bit from the BitVec, and returns it. Returns None if the BitVec is empty.
 974     ///
 975     /// # Examples
 976     ///
 977     /// ```
 978     /// # #![feature(collections)]
 979     /// use std::collections::BitVec;
 980     ///
 981     /// let mut bv = BitVec::from_bytes(&[0b01001001]);
 982     /// assert_eq!(bv.pop(), Some(true));
 983     /// assert_eq!(bv.pop(), Some(false));
 984     /// assert_eq!(bv.len(), 6);
 985     /// ```
 986     #[stable(feature = "rust1", since = "1.0.0")]
 987     pub fn pop(&mut self) -> Option<bool> {
 988         if self.is_empty() {
 989             None
 990         } else {
 991             let i = self.nbits - 1;
 992             let ret = self[i];
 993             // (3)
 994             self.set(i, false);
 995             self.nbits = i;
 996             if self.nbits % u32::BITS == 0 {
 997                 // (2)
 998                 self.storage.pop();
 999             }
1000             Some(ret)
1001         }
1002     }
1003
1004     /// Pushes a `bool` onto the end.
1005     ///
1006     /// # Examples
1007     ///
1008     /// ```
1009     /// # #![feature(collections)]
1010     /// use std::collections::BitVec;
1011     ///
1012     /// let mut bv = BitVec::new();
1013     /// bv.push(true);
1014     /// bv.push(false);
1015     /// assert!(bv.eq_vec(&[true, false]));
1016     /// ```
1017     #[stable(feature = "rust1", since = "1.0.0")]
1018     pub fn push(&mut self, elem: bool) {
1019         if self.nbits % u32::BITS == 0 {
1020             self.storage.push(0);
1021         }
1022         let insert_pos = self.nbits;
1023         self.nbits = self.nbits.checked_add(1).expect("Capacity overflow");
1024         self.set(insert_pos, elem);
1025     }
1026
1027     /// Returns the total number of bits in this vector
1028     #[inline]
1029     #[stable(feature = "rust1", since = "1.0.0")]
1030     pub fn len(&self) -> usize { self.nbits }
1031
1032     /// Returns true if there are no bits in this vector
1033     #[inline]
1034     #[stable(feature = "rust1", since = "1.0.0")]
1035     pub fn is_empty(&self) -> bool { self.len() == 0 }
1036
1037     /// Clears all bits in this vector.
1038     #[inline]
1039     #[stable(feature = "rust1", since = "1.0.0")]
1040     pub fn clear(&mut self) {
1041         for w in &mut self.storage { *w = 0; }
1042     }
1043 }
1044
1045 #[stable(feature = "rust1", since = "1.0.0")]
1046 impl Default for BitVec {
1047     #[inline]
1048     fn default() -> BitVec { BitVec::new() }
1049 }
1050
1051 #[stable(feature = "rust1", since = "1.0.0")]
1052 impl FromIterator<bool> for BitVec {
1053     fn from_iter<I: IntoIterator<Item=bool>>(iter: I) -> BitVec {
1054         let mut ret = BitVec::new();
1055         ret.extend(iter);
1056         ret
1057     }
1058 }
1059
1060 #[stable(feature = "rust1", since = "1.0.0")]
1061 impl Extend<bool> for BitVec {
1062     #[inline]
1063     fn extend<I: IntoIterator<Item=bool>>(&mut self, iterable: I) {
1064         let iterator = iterable.into_iter();
1065         let (min, _) = iterator.size_hint();
1066         self.reserve(min);
1067         for element in iterator {
1068             self.push(element)
1069         }
1070     }
1071 }
1072
1073 #[stable(feature = "rust1", since = "1.0.0")]
1074 impl Clone for BitVec {
1075     #[inline]
1076     fn clone(&self) -> BitVec {
1077         BitVec { storage: self.storage.clone(), nbits: self.nbits }
1078     }
1079
1080     #[inline]
1081     fn clone_from(&mut self, source: &BitVec) {
1082         self.nbits = source.nbits;
1083         self.storage.clone_from(&source.storage);
1084     }
1085 }
1086
1087 #[stable(feature = "rust1", since = "1.0.0")]
1088 impl PartialOrd for BitVec {
1089     #[inline]
1090     fn partial_cmp(&self, other: &BitVec) -> Option<Ordering> {
1091         iter::order::partial_cmp(self.iter(), other.iter())
1092     }
1093 }
1094
1095 #[stable(feature = "rust1", since = "1.0.0")]
1096 impl Ord for BitVec {
1097     #[inline]
1098     fn cmp(&self, other: &BitVec) -> Ordering {
1099         iter::order::cmp(self.iter(), other.iter())
1100     }
1101 }
1102
1103 #[stable(feature = "rust1", since = "1.0.0")]
1104 impl fmt::Debug for BitVec {
1105     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
1106         for bit in self {
1107             try!(write!(fmt, "{}", if bit { 1 } else { 0 }));
1108         }
1109         Ok(())
1110     }
1111 }
1112
1113 #[stable(feature = "rust1", since = "1.0.0")]
1114 impl hash::Hash for BitVec {
1115     fn hash<H: hash::Hasher>(&self, state: &mut H) {
1116         self.nbits.hash(state);
1117         for elem in self.blocks() {
1118             elem.hash(state);
1119         }
1120     }
1121 }
1122
1123 #[stable(feature = "rust1", since = "1.0.0")]
1124 impl cmp::PartialEq for BitVec {
1125     #[inline]
1126     fn eq(&self, other: &BitVec) -> bool {
1127         if self.nbits != other.nbits {
1128             return false;
1129         }
1130         self.blocks().zip(other.blocks()).all(|(w1, w2)| w1 == w2)
1131     }
1132 }
1133
1134 #[stable(feature = "rust1", since = "1.0.0")]
1135 impl cmp::Eq for BitVec {}
1136
1137 /// An iterator for `BitVec`.
1138 #[stable(feature = "rust1", since = "1.0.0")]
1139 #[derive(Clone)]
1140 pub struct Iter<'a> {
1141     bit_vec: &'a BitVec,
1142     next_idx: usize,
1143     end_idx: usize,
1144 }
1145
1146 #[stable(feature = "rust1", since = "1.0.0")]
1147 impl<'a> Iterator for Iter<'a> {
1148     type Item = bool;
1149
1150     #[inline]
1151     fn next(&mut self) -> Option<bool> {
1152         if self.next_idx != self.end_idx {
1153             let idx = self.next_idx;
1154             self.next_idx += 1;
1155             Some(self.bit_vec[idx])
1156         } else {
1157             None
1158         }
1159     }
1160
1161     fn size_hint(&self) -> (usize, Option<usize>) {
1162         let rem = self.end_idx - self.next_idx;
1163         (rem, Some(rem))
1164     }
1165 }
1166
1167 #[stable(feature = "rust1", since = "1.0.0")]
1168 impl<'a> DoubleEndedIterator for Iter<'a> {
1169     #[inline]
1170     fn next_back(&mut self) -> Option<bool> {
1171         if self.next_idx != self.end_idx {
1172             self.end_idx -= 1;
1173             Some(self.bit_vec[self.end_idx])
1174         } else {
1175             None
1176         }
1177     }
1178 }
1179
1180 #[stable(feature = "rust1", since = "1.0.0")]
1181 impl<'a> ExactSizeIterator for Iter<'a> {}
1182
1183 #[stable(feature = "rust1", since = "1.0.0")]
1184 impl<'a> RandomAccessIterator for Iter<'a> {
1185     #[inline]
1186     fn indexable(&self) -> usize {
1187         self.end_idx - self.next_idx
1188     }
1189
1190     #[inline]
1191     fn idx(&mut self, index: usize) -> Option<bool> {
1192         if index >= self.indexable() {
1193             None
1194         } else {
1195             Some(self.bit_vec[index])
1196         }
1197     }
1198 }
1199
1200 #[stable(feature = "rust1", since = "1.0.0")]
1201 impl<'a> IntoIterator for &'a BitVec {
1202     type Item = bool;
1203     type IntoIter = Iter<'a>;
1204
1205     fn into_iter(self) -> Iter<'a> {
1206         self.iter()
1207     }
1208 }
1209
1210 /// An implementation of a set using a bit vector as an underlying
1211 /// representation for holding unsigned numerical elements.
1212 ///
1213 /// It should also be noted that the amount of storage necessary for holding a
1214 /// set of objects is proportional to the maximum of the objects when viewed
1215 /// as a `usize`.
1216 ///
1217 /// # Examples
1218 ///
1219 /// ```
1220 /// # #![feature(collections)]
1221 /// use std::collections::{BitSet, BitVec};
1222 ///
1223 /// // It's a regular set
1224 /// let mut s = BitSet::new();
1225 /// s.insert(0);
1226 /// s.insert(3);
1227 /// s.insert(7);
1228 ///
1229 /// s.remove(&7);
1230 ///
1231 /// if !s.contains(&7) {
1232 ///     println!("There is no 7");
1233 /// }
1234 ///
1235 /// // Can initialize from a `BitVec`
1236 /// let other = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11010000]));
1237 ///
1238 /// s.union_with(&other);
1239 ///
1240 /// // Print 0, 1, 3 in some order
1241 /// for x in s.iter() {
1242 ///     println!("{}", x);
1243 /// }
1244 ///
1245 /// // Can convert back to a `BitVec`
1246 /// let bv: BitVec = s.into_bit_vec();
1247 /// assert!(bv[3]);
1248 /// ```
1249 #[derive(Clone)]
1250 #[unstable(feature = "collections",
1251            reason = "RFC 509")]
1252 pub struct BitSet {
1253     bit_vec: BitVec,
1254 }
1255
1256 #[stable(feature = "rust1", since = "1.0.0")]
1257 impl Default for BitSet {
1258     #[inline]
1259     fn default() -> BitSet { BitSet::new() }
1260 }
1261
1262 #[stable(feature = "rust1", since = "1.0.0")]
1263 impl FromIterator<usize> for BitSet {
1264     fn from_iter<I: IntoIterator<Item=usize>>(iter: I) -> BitSet {
1265         let mut ret = BitSet::new();
1266         ret.extend(iter);
1267         ret
1268     }
1269 }
1270
1271 #[stable(feature = "rust1", since = "1.0.0")]
1272 impl Extend<usize> for BitSet {
1273     #[inline]
1274     fn extend<I: IntoIterator<Item=usize>>(&mut self, iter: I) {
1275         for i in iter {
1276             self.insert(i);
1277         }
1278     }
1279 }
1280
1281 #[stable(feature = "rust1", since = "1.0.0")]
1282 impl PartialOrd for BitSet {
1283     #[inline]
1284     fn partial_cmp(&self, other: &BitSet) -> Option<Ordering> {
1285         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1286         iter::order::partial_cmp(a_iter, b_iter)
1287     }
1288 }
1289
1290 #[stable(feature = "rust1", since = "1.0.0")]
1291 impl Ord for BitSet {
1292     #[inline]
1293     fn cmp(&self, other: &BitSet) -> Ordering {
1294         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1295         iter::order::cmp(a_iter, b_iter)
1296     }
1297 }
1298
1299 #[stable(feature = "rust1", since = "1.0.0")]
1300 impl cmp::PartialEq for BitSet {
1301     #[inline]
1302     fn eq(&self, other: &BitSet) -> bool {
1303         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1304         iter::order::eq(a_iter, b_iter)
1305     }
1306 }
1307
1308 #[stable(feature = "rust1", since = "1.0.0")]
1309 impl cmp::Eq for BitSet {}
1310
1311 impl BitSet {
1312     /// Creates a new empty `BitSet`.
1313     ///
1314     /// # Examples
1315     ///
1316     /// ```
1317     /// # #![feature(collections)]
1318     /// use std::collections::BitSet;
1319     ///
1320     /// let mut s = BitSet::new();
1321     /// ```
1322     #[inline]
1323     #[stable(feature = "rust1", since = "1.0.0")]
1324     pub fn new() -> BitSet {
1325         BitSet { bit_vec: BitVec::new() }
1326     }
1327
1328     /// Creates a new `BitSet` with initially no contents, able to
1329     /// hold `nbits` elements without resizing.
1330     ///
1331     /// # Examples
1332     ///
1333     /// ```
1334     /// # #![feature(collections)]
1335     /// use std::collections::BitSet;
1336     ///
1337     /// let mut s = BitSet::with_capacity(100);
1338     /// assert!(s.capacity() >= 100);
1339     /// ```
1340     #[inline]
1341     #[stable(feature = "rust1", since = "1.0.0")]
1342     pub fn with_capacity(nbits: usize) -> BitSet {
1343         let bit_vec = BitVec::from_elem(nbits, false);
1344         BitSet::from_bit_vec(bit_vec)
1345     }
1346
1347     /// Creates a new `BitSet` from the given bit vector.
1348     ///
1349     /// # Examples
1350     ///
1351     /// ```
1352     /// # #![feature(collections)]
1353     /// use std::collections::{BitVec, BitSet};
1354     ///
1355     /// let bv = BitVec::from_bytes(&[0b01100000]);
1356     /// let s = BitSet::from_bit_vec(bv);
1357     ///
1358     /// // Print 1, 2 in arbitrary order
1359     /// for x in s.iter() {
1360     ///     println!("{}", x);
1361     /// }
1362     /// ```
1363     #[inline]
1364     pub fn from_bit_vec(bit_vec: BitVec) -> BitSet {
1365         BitSet { bit_vec: bit_vec }
1366     }
1367
1368     /// Returns the capacity in bits for this bit vector. Inserting any
1369     /// element less than this amount will not trigger a resizing.
1370     ///
1371     /// # Examples
1372     ///
1373     /// ```
1374     /// # #![feature(collections)]
1375     /// use std::collections::BitSet;
1376     ///
1377     /// let mut s = BitSet::with_capacity(100);
1378     /// assert!(s.capacity() >= 100);
1379     /// ```
1380     #[inline]
1381     #[stable(feature = "rust1", since = "1.0.0")]
1382     pub fn capacity(&self) -> usize {
1383         self.bit_vec.capacity()
1384     }
1385
1386     /// Reserves capacity for the given `BitSet` to contain `len` distinct elements. In the case
1387     /// of `BitSet` this means reallocations will not occur as long as all inserted elements
1388     /// are less than `len`.
1389     ///
1390     /// The collection may reserve more space to avoid frequent reallocations.
1391     ///
1392     ///
1393     /// # Examples
1394     ///
1395     /// ```
1396     /// # #![feature(collections)]
1397     /// use std::collections::BitSet;
1398     ///
1399     /// let mut s = BitSet::new();
1400     /// s.reserve_len(10);
1401     /// assert!(s.capacity() >= 10);
1402     /// ```
1403     #[stable(feature = "rust1", since = "1.0.0")]
1404     pub fn reserve_len(&mut self, len: usize) {
1405         let cur_len = self.bit_vec.len();
1406         if len >= cur_len {
1407             self.bit_vec.reserve(len - cur_len);
1408         }
1409     }
1410
1411     /// Reserves the minimum capacity for the given `BitSet` to contain `len` distinct elements.
1412     /// In the case of `BitSet` this means reallocations will not occur as long as all inserted
1413     /// elements are less than `len`.
1414     ///
1415     /// Note that the allocator may give the collection more space than it requests. Therefore
1416     /// capacity can not be relied upon to be precisely minimal. Prefer `reserve_len` if future
1417     /// insertions are expected.
1418     ///
1419     ///
1420     /// # Examples
1421     ///
1422     /// ```
1423     /// # #![feature(collections)]
1424     /// use std::collections::BitSet;
1425     ///
1426     /// let mut s = BitSet::new();
1427     /// s.reserve_len_exact(10);
1428     /// assert!(s.capacity() >= 10);
1429     /// ```
1430     #[stable(feature = "rust1", since = "1.0.0")]
1431     pub fn reserve_len_exact(&mut self, len: usize) {
1432         let cur_len = self.bit_vec.len();
1433         if len >= cur_len {
1434             self.bit_vec.reserve_exact(len - cur_len);
1435         }
1436     }
1437
1438
1439     /// Consumes this set to return the underlying bit vector.
1440     ///
1441     /// # Examples
1442     ///
1443     /// ```
1444     /// # #![feature(collections)]
1445     /// use std::collections::BitSet;
1446     ///
1447     /// let mut s = BitSet::new();
1448     /// s.insert(0);
1449     /// s.insert(3);
1450     ///
1451     /// let bv = s.into_bit_vec();
1452     /// assert!(bv[0]);
1453     /// assert!(bv[3]);
1454     /// ```
1455     #[inline]
1456     pub fn into_bit_vec(self) -> BitVec {
1457         self.bit_vec
1458     }
1459
1460     /// Returns a reference to the underlying bit vector.
1461     ///
1462     /// # Examples
1463     ///
1464     /// ```
1465     /// # #![feature(collections)]
1466     /// use std::collections::BitSet;
1467     ///
1468     /// let mut s = BitSet::new();
1469     /// s.insert(0);
1470     ///
1471     /// let bv = s.get_ref();
1472     /// assert_eq!(bv[0], true);
1473     /// ```
1474     #[inline]
1475     pub fn get_ref(&self) -> &BitVec {
1476         &self.bit_vec
1477     }
1478
1479     #[inline]
1480     fn other_op<F>(&mut self, other: &BitSet, mut f: F) where F: FnMut(u32, u32) -> u32 {
1481         // Unwrap BitVecs
1482         let self_bit_vec = &mut self.bit_vec;
1483         let other_bit_vec = &other.bit_vec;
1484
1485         let self_len = self_bit_vec.len();
1486         let other_len = other_bit_vec.len();
1487
1488         // Expand the vector if necessary
1489         if self_len < other_len {
1490             self_bit_vec.grow(other_len - self_len, false);
1491         }
1492
1493         // virtually pad other with 0's for equal lengths
1494         let other_words = {
1495             let (_, result) = match_words(self_bit_vec, other_bit_vec);
1496             result
1497         };
1498
1499         // Apply values found in other
1500         for (i, w) in other_words {
1501             let old = self_bit_vec.storage[i];
1502             let new = f(old, w);
1503             self_bit_vec.storage[i] = new;
1504         }
1505     }
1506
1507     /// Truncates the underlying vector to the least length required.
1508     ///
1509     /// # Examples
1510     ///
1511     /// ```
1512     /// # #![feature(collections)]
1513     /// use std::collections::BitSet;
1514     ///
1515     /// let mut s = BitSet::new();
1516     /// s.insert(32183231);
1517     /// s.remove(&32183231);
1518     ///
1519     /// // Internal storage will probably be bigger than necessary
1520     /// println!("old capacity: {}", s.capacity());
1521     ///
1522     /// // Now should be smaller
1523     /// s.shrink_to_fit();
1524     /// println!("new capacity: {}", s.capacity());
1525     /// ```
1526     #[inline]
1527     #[stable(feature = "rust1", since = "1.0.0")]
1528     pub fn shrink_to_fit(&mut self) {
1529         let bit_vec = &mut self.bit_vec;
1530         // Obtain original length
1531         let old_len = bit_vec.storage.len();
1532         // Obtain coarse trailing zero length
1533         let n = bit_vec.storage.iter().rev().take_while(|&&n| n == 0).count();
1534         // Truncate
1535         let trunc_len = cmp::max(old_len - n, 1);
1536         bit_vec.storage.truncate(trunc_len);
1537         bit_vec.nbits = trunc_len * u32::BITS;
1538     }
1539
1540     /// Iterator over each usize stored in the `BitSet`.
1541     ///
1542     /// # Examples
1543     ///
1544     /// ```
1545     /// # #![feature(collections)]
1546     /// use std::collections::{BitVec, BitSet};
1547     ///
1548     /// let s = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01001010]));
1549     ///
1550     /// // Print 1, 4, 6 in arbitrary order
1551     /// for x in s.iter() {
1552     ///     println!("{}", x);
1553     /// }
1554     /// ```
1555     #[inline]
1556     #[stable(feature = "rust1", since = "1.0.0")]
1557     pub fn iter(&self) -> bit_set::Iter {
1558         SetIter(BlockIter::from_blocks(self.bit_vec.blocks()))
1559     }
1560
1561     /// Iterator over each usize stored in `self` union `other`.
1562     /// See [union_with](#method.union_with) for an efficient in-place version.
1563     ///
1564     /// # Examples
1565     ///
1566     /// ```
1567     /// # #![feature(collections)]
1568     /// use std::collections::{BitVec, BitSet};
1569     ///
1570     /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
1571     /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
1572     ///
1573     /// // Print 0, 1, 2, 4 in arbitrary order
1574     /// for x in a.union(&b) {
1575     ///     println!("{}", x);
1576     /// }
1577     /// ```
1578     #[inline]
1579     #[stable(feature = "rust1", since = "1.0.0")]
1580     pub fn union<'a>(&'a self, other: &'a BitSet) -> Union<'a> {
1581         fn or(w1: u32, w2: u32) -> u32 { w1 | w2 }
1582
1583         Union(BlockIter::from_blocks(TwoBitPositions {
1584             set: self.bit_vec.blocks(),
1585             other: other.bit_vec.blocks(),
1586             merge: or,
1587         }))
1588     }
1589
1590     /// Iterator over each usize stored in `self` intersect `other`.
1591     /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
1592     ///
1593     /// # Examples
1594     ///
1595     /// ```
1596     /// # #![feature(collections)]
1597     /// use std::collections::{BitVec, BitSet};
1598     ///
1599     /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
1600     /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
1601     ///
1602     /// // Print 2
1603     /// for x in a.intersection(&b) {
1604     ///     println!("{}", x);
1605     /// }
1606     /// ```
1607     #[inline]
1608     #[stable(feature = "rust1", since = "1.0.0")]
1609     pub fn intersection<'a>(&'a self, other: &'a BitSet) -> Intersection<'a> {
1610         fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 }
1611         let min = cmp::min(self.bit_vec.len(), other.bit_vec.len());
1612
1613         Intersection(BlockIter::from_blocks(TwoBitPositions {
1614             set: self.bit_vec.blocks(),
1615             other: other.bit_vec.blocks(),
1616             merge: bitand,
1617         }).take(min))
1618     }
1619
1620     /// Iterator over each usize stored in the `self` setminus `other`.
1621     /// See [difference_with](#method.difference_with) for an efficient in-place version.
1622     ///
1623     /// # Examples
1624     ///
1625     /// ```
1626     /// # #![feature(collections)]
1627     /// use std::collections::{BitSet, BitVec};
1628     ///
1629     /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
1630     /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
1631     ///
1632     /// // Print 1, 4 in arbitrary order
1633     /// for x in a.difference(&b) {
1634     ///     println!("{}", x);
1635     /// }
1636     ///
1637     /// // Note that difference is not symmetric,
1638     /// // and `b - a` means something else.
1639     /// // This prints 0
1640     /// for x in b.difference(&a) {
1641     ///     println!("{}", x);
1642     /// }
1643     /// ```
1644     #[inline]
1645     #[stable(feature = "rust1", since = "1.0.0")]
1646     pub fn difference<'a>(&'a self, other: &'a BitSet) -> Difference<'a> {
1647         fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 }
1648
1649         Difference(BlockIter::from_blocks(TwoBitPositions {
1650             set: self.bit_vec.blocks(),
1651             other: other.bit_vec.blocks(),
1652             merge: diff,
1653         }))
1654     }
1655
1656     /// Iterator over each usize stored in the symmetric difference of `self` and `other`.
1657     /// See [symmetric_difference_with](#method.symmetric_difference_with) for
1658     /// an efficient in-place version.
1659     ///
1660     /// # Examples
1661     ///
1662     /// ```
1663     /// # #![feature(collections)]
1664     /// use std::collections::{BitSet, BitVec};
1665     ///
1666     /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
1667     /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
1668     ///
1669     /// // Print 0, 1, 4 in arbitrary order
1670     /// for x in a.symmetric_difference(&b) {
1671     ///     println!("{}", x);
1672     /// }
1673     /// ```
1674     #[inline]
1675     #[stable(feature = "rust1", since = "1.0.0")]
1676     pub fn symmetric_difference<'a>(&'a self, other: &'a BitSet) -> SymmetricDifference<'a> {
1677         fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 }
1678
1679         SymmetricDifference(BlockIter::from_blocks(TwoBitPositions {
1680             set: self.bit_vec.blocks(),
1681             other: other.bit_vec.blocks(),
1682             merge: bitxor,
1683         }))
1684     }
1685
1686     /// Unions in-place with the specified other bit vector.
1687     ///
1688     /// # Examples
1689     ///
1690     /// ```
1691     /// # #![feature(collections)]
1692     /// use std::collections::{BitSet, BitVec};
1693     ///
1694     /// let a   = 0b01101000;
1695     /// let b   = 0b10100000;
1696     /// let res = 0b11101000;
1697     ///
1698     /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1699     /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1700     /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
1701     ///
1702     /// a.union_with(&b);
1703     /// assert_eq!(a, res);
1704     /// ```
1705     #[inline]
1706     pub fn union_with(&mut self, other: &BitSet) {
1707         self.other_op(other, |w1, w2| w1 | w2);
1708     }
1709
1710     /// Intersects in-place with the specified other bit vector.
1711     ///
1712     /// # Examples
1713     ///
1714     /// ```
1715     /// # #![feature(collections)]
1716     /// use std::collections::{BitSet, BitVec};
1717     ///
1718     /// let a   = 0b01101000;
1719     /// let b   = 0b10100000;
1720     /// let res = 0b00100000;
1721     ///
1722     /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1723     /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1724     /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
1725     ///
1726     /// a.intersect_with(&b);
1727     /// assert_eq!(a, res);
1728     /// ```
1729     #[inline]
1730     pub fn intersect_with(&mut self, other: &BitSet) {
1731         self.other_op(other, |w1, w2| w1 & w2);
1732     }
1733
1734     /// Makes this bit vector the difference with the specified other bit vector
1735     /// in-place.
1736     ///
1737     /// # Examples
1738     ///
1739     /// ```
1740     /// # #![feature(collections)]
1741     /// use std::collections::{BitSet, BitVec};
1742     ///
1743     /// let a   = 0b01101000;
1744     /// let b   = 0b10100000;
1745     /// let a_b = 0b01001000; // a - b
1746     /// let b_a = 0b10000000; // b - a
1747     ///
1748     /// let mut bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1749     /// let bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1750     /// let bva_b = BitSet::from_bit_vec(BitVec::from_bytes(&[a_b]));
1751     /// let bvb_a = BitSet::from_bit_vec(BitVec::from_bytes(&[b_a]));
1752     ///
1753     /// bva.difference_with(&bvb);
1754     /// assert_eq!(bva, bva_b);
1755     ///
1756     /// let bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1757     /// let mut bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1758     ///
1759     /// bvb.difference_with(&bva);
1760     /// assert_eq!(bvb, bvb_a);
1761     /// ```
1762     #[inline]
1763     pub fn difference_with(&mut self, other: &BitSet) {
1764         self.other_op(other, |w1, w2| w1 & !w2);
1765     }
1766
1767     /// Makes this bit vector the symmetric difference with the specified other
1768     /// bit vector in-place.
1769     ///
1770     /// # Examples
1771     ///
1772     /// ```
1773     /// # #![feature(collections)]
1774     /// use std::collections::{BitSet, BitVec};
1775     ///
1776     /// let a   = 0b01101000;
1777     /// let b   = 0b10100000;
1778     /// let res = 0b11001000;
1779     ///
1780     /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1781     /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1782     /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
1783     ///
1784     /// a.symmetric_difference_with(&b);
1785     /// assert_eq!(a, res);
1786     /// ```
1787     #[inline]
1788     pub fn symmetric_difference_with(&mut self, other: &BitSet) {
1789         self.other_op(other, |w1, w2| w1 ^ w2);
1790     }
1791
1792     /// Moves all elements from `other` into `Self`, leaving `other` empty.
1793     ///
1794     /// # Examples
1795     ///
1796     /// ```
1797     /// # #![feature(collections, bit_set_append_split_off)]
1798     /// use std::collections::{BitVec, BitSet};
1799     ///
1800     /// let mut a = BitSet::new();
1801     /// a.insert(2);
1802     /// a.insert(6);
1803     ///
1804     /// let mut b = BitSet::new();
1805     /// b.insert(1);
1806     /// b.insert(3);
1807     /// b.insert(6);
1808     ///
1809     /// a.append(&mut b);
1810     ///
1811     /// assert_eq!(a.len(), 4);
1812     /// assert_eq!(b.len(), 0);
1813     /// assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01110010])));
1814     /// ```
1815     #[unstable(feature = "bit_set_append_split_off",
1816                reason = "recently added as part of collections reform 2")]
1817     pub fn append(&mut self, other: &mut Self) {
1818         self.union_with(other);
1819         other.clear();
1820     }
1821
1822     /// Splits the `BitSet` into two at the given key including the key.
1823     /// Retains the first part in-place while returning the second part.
1824     ///
1825     /// # Examples
1826     ///
1827     /// ```
1828     /// # #![feature(collections, bit_set_append_split_off)]
1829     /// use std::collections::{BitSet, BitVec};
1830     /// let mut a = BitSet::new();
1831     /// a.insert(2);
1832     /// a.insert(6);
1833     /// a.insert(1);
1834     /// a.insert(3);
1835     ///
1836     /// let b = a.split_off(3);
1837     ///
1838     /// assert_eq!(a.len(), 2);
1839     /// assert_eq!(b.len(), 2);
1840     /// assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100000])));
1841     /// assert_eq!(b, BitSet::from_bit_vec(BitVec::from_bytes(&[0b00010010])));
1842     /// ```
1843     #[unstable(feature = "bit_set_append_split_off",
1844                reason = "recently added as part of collections reform 2")]
1845     pub fn split_off(&mut self, at: usize) -> Self {
1846         let mut other = BitSet::new();
1847
1848         if at == 0 {
1849             swap(self, &mut other);
1850             return other;
1851         } else if at >= self.bit_vec.len() {
1852             return other;
1853         }
1854
1855         // Calculate block and bit at which to split
1856         let w = at / u32::BITS;
1857         let b = at % u32::BITS;
1858
1859         // Pad `other` with `w` zero blocks,
1860         // append `self`'s blocks in the range from `w` to the end to `other`
1861         other.bit_vec.storage.extend(repeat(0u32).take(w)
1862                                      .chain(self.bit_vec.storage[w..].iter().cloned()));
1863         other.bit_vec.nbits = self.bit_vec.nbits;
1864
1865         if b > 0 {
1866             other.bit_vec.storage[w] &= !0 << b;
1867         }
1868
1869         // Sets `bit_vec.len()` and fixes the last block as well
1870         self.bit_vec.truncate(at);
1871
1872         other
1873     }
1874
1875     /// Returns the number of set bits in this set.
1876     #[inline]
1877     #[stable(feature = "rust1", since = "1.0.0")]
1878     pub fn len(&self) -> usize  {
1879         self.bit_vec.blocks().fold(0, |acc, n| acc + n.count_ones() as usize)
1880     }
1881
1882     /// Returns whether there are no bits set in this set
1883     #[inline]
1884     #[stable(feature = "rust1", since = "1.0.0")]
1885     pub fn is_empty(&self) -> bool {
1886         self.bit_vec.none()
1887     }
1888
1889     /// Clears all bits in this set
1890     #[inline]
1891     #[stable(feature = "rust1", since = "1.0.0")]
1892     pub fn clear(&mut self) {
1893         self.bit_vec.clear();
1894     }
1895
1896     /// Returns `true` if this set contains the specified integer.
1897     #[inline]
1898     #[stable(feature = "rust1", since = "1.0.0")]
1899     pub fn contains(&self, value: &usize) -> bool {
1900         let bit_vec = &self.bit_vec;
1901         *value < bit_vec.nbits && bit_vec[*value]
1902     }
1903
1904     /// Returns `true` if the set has no elements in common with `other`.
1905     /// This is equivalent to checking for an empty intersection.
1906     #[inline]
1907     #[stable(feature = "rust1", since = "1.0.0")]
1908     pub fn is_disjoint(&self, other: &BitSet) -> bool {
1909         self.intersection(other).next().is_none()
1910     }
1911
1912     /// Returns `true` if the set is a subset of another.
1913     #[inline]
1914     #[stable(feature = "rust1", since = "1.0.0")]
1915     pub fn is_subset(&self, other: &BitSet) -> bool {
1916         let self_bit_vec = &self.bit_vec;
1917         let other_bit_vec = &other.bit_vec;
1918         let other_blocks = blocks_for_bits(other_bit_vec.len());
1919
1920         // Check that `self` intersect `other` is self
1921         self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
1922         // Make sure if `self` has any more blocks than `other`, they're all 0
1923         self_bit_vec.blocks().skip(other_blocks).all(|w| w == 0)
1924     }
1925
1926     /// Returns `true` if the set is a superset of another.
1927     #[inline]
1928     #[stable(feature = "rust1", since = "1.0.0")]
1929     pub fn is_superset(&self, other: &BitSet) -> bool {
1930         other.is_subset(self)
1931     }
1932
1933     /// Adds a value to the set. Returns `true` if the value was not already
1934     /// present in the set.
1935     #[stable(feature = "rust1", since = "1.0.0")]
1936     pub fn insert(&mut self, value: usize) -> bool {
1937         if self.contains(&value) {
1938             return false;
1939         }
1940
1941         // Ensure we have enough space to hold the new element
1942         let len = self.bit_vec.len();
1943         if value >= len {
1944             self.bit_vec.grow(value - len + 1, false)
1945         }
1946
1947         self.bit_vec.set(value, true);
1948         return true;
1949     }
1950
1951     /// Removes a value from the set. Returns `true` if the value was
1952     /// present in the set.
1953     #[stable(feature = "rust1", since = "1.0.0")]
1954     pub fn remove(&mut self, value: &usize) -> bool {
1955         if !self.contains(value) {
1956             return false;
1957         }
1958
1959         self.bit_vec.set(*value, false);
1960
1961         return true;
1962     }
1963 }
1964
1965 #[stable(feature = "rust1", since = "1.0.0")]
1966 impl fmt::Debug for BitSet {
1967     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
1968         try!(write!(fmt, "{{"));
1969         let mut first = true;
1970         for n in self {
1971             if !first {
1972                 try!(write!(fmt, ", "));
1973             }
1974             try!(write!(fmt, "{:?}", n));
1975             first = false;
1976         }
1977         write!(fmt, "}}")
1978     }
1979 }
1980
1981 #[stable(feature = "rust1", since = "1.0.0")]
1982 impl hash::Hash for BitSet {
1983     fn hash<H: hash::Hasher>(&self, state: &mut H) {
1984         for pos in self {
1985             pos.hash(state);
1986         }
1987     }
1988 }
1989
1990 #[derive(Clone)]
1991 #[stable(feature = "rust1", since = "1.0.0")]
1992 struct BlockIter<T> where T: Iterator<Item=u32> {
1993     head: u32,
1994     head_offset: usize,
1995     tail: T,
1996 }
1997
1998 impl<'a, T> BlockIter<T> where T: Iterator<Item=u32> {
1999     fn from_blocks(mut blocks: T) -> BlockIter<T> {
2000         let h = blocks.next().unwrap_or(0);
2001         BlockIter {tail: blocks, head: h, head_offset: 0}
2002     }
2003 }
2004
2005 /// An iterator combining two `BitSet` iterators.
2006 #[derive(Clone)]
2007 struct TwoBitPositions<'a> {
2008     set: Blocks<'a>,
2009     other: Blocks<'a>,
2010     merge: fn(u32, u32) -> u32,
2011 }
2012
2013 /// An iterator for `BitSet`.
2014 #[derive(Clone)]
2015 #[stable(feature = "rust1", since = "1.0.0")]
2016 pub struct SetIter<'a>(BlockIter<Blocks<'a>>);
2017 #[derive(Clone)]
2018 #[stable(feature = "rust1", since = "1.0.0")]
2019 pub struct Union<'a>(BlockIter<TwoBitPositions<'a>>);
2020 #[derive(Clone)]
2021 #[stable(feature = "rust1", since = "1.0.0")]
2022 pub struct Intersection<'a>(Take<BlockIter<TwoBitPositions<'a>>>);
2023 #[derive(Clone)]
2024 #[stable(feature = "rust1", since = "1.0.0")]
2025 pub struct Difference<'a>(BlockIter<TwoBitPositions<'a>>);
2026 #[derive(Clone)]
2027 #[stable(feature = "rust1", since = "1.0.0")]
2028 pub struct SymmetricDifference<'a>(BlockIter<TwoBitPositions<'a>>);
2029
2030 #[stable(feature = "rust1", since = "1.0.0")]
2031 impl<'a, T> Iterator for BlockIter<T> where T: Iterator<Item=u32> {
2032     type Item = usize;
2033
2034     fn next(&mut self) -> Option<usize> {
2035         while self.head == 0 {
2036             match self.tail.next() {
2037                 Some(w) => self.head = w,
2038                 None => return None
2039             }
2040             self.head_offset += u32::BITS;
2041         }
2042
2043         // from the current block, isolate the
2044         // LSB and subtract 1, producing k:
2045         // a block with a number of set bits
2046         // equal to the index of the LSB
2047         let k = (self.head & (!self.head + 1)) - 1;
2048         // update block, removing the LSB
2049         self.head &= self.head - 1;
2050         // return offset + (index of LSB)
2051         Some(self.head_offset + (u32::count_ones(k) as usize))
2052     }
2053
2054     #[inline]
2055     fn size_hint(&self) -> (usize, Option<usize>) {
2056         match self.tail.size_hint() {
2057             (_, Some(h)) => (0, Some(1 + h * (u32::BITS as usize))),
2058             _ => (0, None)
2059         }
2060     }
2061 }
2062
2063 #[stable(feature = "rust1", since = "1.0.0")]
2064 impl<'a> Iterator for TwoBitPositions<'a> {
2065     type Item = u32;
2066
2067     fn next(&mut self) -> Option<u32> {
2068         match (self.set.next(), self.other.next()) {
2069             (Some(a), Some(b)) => Some((self.merge)(a, b)),
2070             (Some(a), None) => Some((self.merge)(a, 0)),
2071             (None, Some(b)) => Some((self.merge)(0, b)),
2072             _ => return None
2073         }
2074     }
2075
2076     #[inline]
2077     fn size_hint(&self) -> (usize, Option<usize>) {
2078         let (a, au) = self.set.size_hint();
2079         let (b, bu) = self.other.size_hint();
2080
2081         let upper = match (au, bu) {
2082             (Some(au), Some(bu)) => Some(cmp::max(au, bu)),
2083             _ => None
2084         };
2085
2086         (cmp::max(a, b), upper)
2087     }
2088 }
2089
2090 #[stable(feature = "rust1", since = "1.0.0")]
2091 impl<'a> Iterator for SetIter<'a> {
2092     type Item = usize;
2093
2094     #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2095     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2096 }
2097
2098 #[stable(feature = "rust1", since = "1.0.0")]
2099 impl<'a> Iterator for Union<'a> {
2100     type Item = usize;
2101
2102     #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2103     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2104 }
2105
2106 #[stable(feature = "rust1", since = "1.0.0")]
2107 impl<'a> Iterator for Intersection<'a> {
2108     type Item = usize;
2109
2110     #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2111     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2112 }
2113
2114 #[stable(feature = "rust1", since = "1.0.0")]
2115 impl<'a> Iterator for Difference<'a> {
2116     type Item = usize;
2117
2118     #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2119     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2120 }
2121
2122 #[stable(feature = "rust1", since = "1.0.0")]
2123 impl<'a> Iterator for SymmetricDifference<'a> {
2124     type Item = usize;
2125
2126     #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2127     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2128 }
2129
2130 #[stable(feature = "rust1", since = "1.0.0")]
2131 impl<'a> IntoIterator for &'a BitSet {
2132     type Item = usize;
2133     type IntoIter = SetIter<'a>;
2134
2135     fn into_iter(self) -> SetIter<'a> {
2136         self.iter()
2137     }
2138 }