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