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): Bitv and BitvSet are very tightly coupled. Ideally (for
  12 // maintenance), they should be in separate files/modules, with BitvSet only
  13 // using Bitv's public API. This will be hard for performance though, because
  14 // `Bitv` 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-): `Bitv`'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 `uint`.
  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) `BitvSet` is tightly coupled with `Bitv`, so any changes you make in
  29 // `Bitv` will need to be reflected in `BitvSet`.
  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 //! use std::collections::{BitvSet, Bitv};
  42 //! use std::num::Float;
  43 //! use std::iter;
  44 //!
  45 //! let max_prime = 10000;
  46 //!
  47 //! // Store the primes as a BitvSet
  48 //! let primes = {
  49 //!     // Assume all numbers are prime to begin, and then we
  50 //!     // cross off non-primes progressively
  51 //!     let mut bv = Bitv::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 uint) {
  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 iter::range_step(i * i, max_prime, i) { bv.set(j, false) }
  63 //!         }
  64 //!     }
  65 //!     BitvSet::from_bitv(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 range(0, print_primes) {
  72 //!     if primes.contains(&x) {
  73 //!         print!("{} ", x);
  74 //!     }
  75 //! }
  76 //! println!("");
  77 //!
  78 //! // We can manipulate the internal Bitv
  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::default::Default;
  88 use core::fmt;
  89 use core::hash;
  90 use core::iter::RandomAccessIterator;
  91 use core::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat, Cloned};
  92 use core::iter::{self, FromIterator};
  93 use core::num::Int;
  94 use core::ops::Index;
  95 use core::slice;
  96 use core::{u8, u32, uint};
  97 use bitv_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 range(0, u8::BITS) {
 108         result |= ((byte >> i) & 1) << (u8::BITS - 1 - i);
 109     }
 110     result
 111 }
 112
 113 // Take two BitV'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 Bitv, b: &'b Bitv) -> (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(0u32).enumerate().take(b_len).skip(a_len)),
 122          b.blocks().enumerate().chain(iter::repeat(0u32).enumerate().take(0).skip(0)))
 123     } else {
 124         (a.blocks().enumerate().chain(iter::repeat(0u32).enumerate().take(0).skip(0)),
 125          b.blocks().enumerate().chain(iter::repeat(0u32).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 /// ```rust
 137 /// use std::collections::Bitv;
 138 ///
 139 /// let mut bv = Bitv::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 = "RFC 509"]
 160 pub struct Bitv {
 161     /// Internal representation of the bit vector
 162     storage: Vec<u32>,
 163     /// The number of valid bits in the internal representation
 164     nbits: uint
 165 }
 166
 167 // FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
 168 impl Index<uint> for Bitv {
 169     type Output = bool;
 170
 171     #[inline]
 172     fn index(&self, i: &uint) -> &bool {
 173         if self.get(*i).expect("index out of bounds") {
 174             &TRUE
 175         } else {
 176             &FALSE
 177         }
 178     }
 179 }
 180
 181 /// Computes how many blocks are needed to store that many bits
 182 fn blocks_for_bits(bits: uint) -> uint {
 183     // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
 184     // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
 185     // one too many. So we need to check if that's the case. We can do that by computing if
 186     // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
 187     // superior modulo operator on a power of two to this.
 188     //
 189     // Note that we can technically avoid this branch with the expression
 190     // `(nbits + u32::BITS - 1) / 32::BITS`, but if nbits is almost uint::MAX this will overflow.
 191     if bits % u32::BITS == 0 {
 192         bits / u32::BITS
 193     } else {
 194         bits / u32::BITS + 1
 195     }
 196 }
 197
 198 /// Computes the bitmask for the final word of the vector
 199 fn mask_for_bits(bits: uint) -> u32 {
 200     // Note especially that a perfect multiple of u32::BITS should mask all 1s.
 201     !0u32 >> (u32::BITS - bits % u32::BITS) % u32::BITS
 202 }
 203
 204 impl Bitv {
 205     /// Applies the given operation to the blocks of self and other, and sets
 206     /// self to be the result. This relies on the caller not to corrupt the
 207     /// last word.
 208     #[inline]
 209     fn process<F>(&mut self, other: &Bitv, mut op: F) -> bool where F: FnMut(u32, u32) -> u32 {
 210         assert_eq!(self.len(), other.len());
 211         // This could theoretically be a `debug_assert!`.
 212         assert_eq!(self.storage.len(), other.storage.len());
 213         let mut changed = false;
 214         for (a, b) in self.blocks_mut().zip(other.blocks()) {
 215             let w = op(*a, b);
 216             if *a != w {
 217                 changed = true;
 218                 *a = w;
 219             }
 220         }
 221         changed
 222     }
 223
 224     /// Iterator over mutable refs to  the underlying blocks of data.
 225     fn blocks_mut(&mut self) -> MutBlocks {
 226         // (2)
 227         self.storage.iter_mut()
 228     }
 229
 230     /// Iterator over the underlying blocks of data
 231     fn blocks(&self) -> Blocks {
 232         // (2)
 233         self.storage.iter().cloned()
 234     }
 235
 236     /// An operation might screw up the unused bits in the last block of the
 237     /// `Bitv`. As per (3), it's assumed to be all 0s. This method fixes it up.
 238     fn fix_last_block(&mut self) {
 239         let extra_bits = self.len() % u32::BITS;
 240         if extra_bits > 0 {
 241             let mask = (1 << extra_bits) - 1;
 242             let storage_len = self.storage.len();
 243             self.storage[storage_len - 1] &= mask;
 244         }
 245     }
 246
 247     /// Creates an empty `Bitv`.
 248     ///
 249     /// # Examples
 250     ///
 251     /// ```
 252     /// use std::collections::Bitv;
 253     /// let mut bv = Bitv::new();
 254     /// ```
 255     #[stable]
 256     pub fn new() -> Bitv {
 257         Bitv { storage: Vec::new(), nbits: 0 }
 258     }
 259
 260     /// Creates a `Bitv` that holds `nbits` elements, setting each element
 261     /// to `bit`.
 262     ///
 263     /// # Examples
 264     ///
 265     /// ```
 266     /// use std::collections::Bitv;
 267     ///
 268     /// let mut bv = Bitv::from_elem(10u, false);
 269     /// assert_eq!(bv.len(), 10u);
 270     /// for x in bv.iter() {
 271     ///     assert_eq!(x, false);
 272     /// }
 273     /// ```
 274     pub fn from_elem(nbits: uint, bit: bool) -> Bitv {
 275         let nblocks = blocks_for_bits(nbits);
 276         let mut bitv = Bitv {
 277             storage: repeat(if bit { !0u32 } else { 0u32 }).take(nblocks).collect(),
 278             nbits: nbits
 279         };
 280         bitv.fix_last_block();
 281         bitv
 282     }
 283
 284     /// Constructs a new, empty `Bitv` with the specified capacity.
 285     ///
 286     /// The bitvector will be able to hold at least `capacity` bits without
 287     /// reallocating. If `capacity` is 0, it will not allocate.
 288     ///
 289     /// It is important to note that this function does not specify the
 290     /// *length* of the returned bitvector, but only the *capacity*.
 291     #[stable]
 292     pub fn with_capacity(nbits: uint) -> Bitv {
 293         Bitv {
 294             storage: Vec::with_capacity(blocks_for_bits(nbits)),
 295             nbits: 0,
 296         }
 297     }
 298
 299     /// Transforms a byte-vector into a `Bitv`. Each byte becomes eight bits,
 300     /// with the most significant bits of each byte coming first. Each
 301     /// bit becomes `true` if equal to 1 or `false` if equal to 0.
 302     ///
 303     /// # Examples
 304     ///
 305     /// ```
 306     /// use std::collections::Bitv;
 307     ///
 308     /// let bv = Bitv::from_bytes(&[0b10100000, 0b00010010]);
 309     /// assert!(bv.eq_vec(&[true, false, true, false,
 310     ///                     false, false, false, false,
 311     ///                     false, false, false, true,
 312     ///                     false, false, true, false]));
 313     /// ```
 314     pub fn from_bytes(bytes: &[u8]) -> Bitv {
 315         let len = bytes.len().checked_mul(u8::BITS).expect("capacity overflow");
 316         let mut bitv = Bitv::with_capacity(len);
 317         let complete_words = bytes.len() / 4;
 318         let extra_bytes = bytes.len() % 4;
 319
 320         bitv.nbits = len;
 321
 322         for i in range(0, complete_words) {
 323             bitv.storage.push(
 324                 ((reverse_bits(bytes[i * 4 + 0]) as u32) << 0) |
 325                 ((reverse_bits(bytes[i * 4 + 1]) as u32) << 8) |
 326                 ((reverse_bits(bytes[i * 4 + 2]) as u32) << 16) |
 327                 ((reverse_bits(bytes[i * 4 + 3]) as u32) << 24)
 328             );
 329         }
 330
 331         if extra_bytes > 0 {
 332             let mut last_word = 0u32;
 333             for (i, &byte) in bytes[(complete_words*4)..].iter().enumerate() {
 334                 last_word |= (reverse_bits(byte) as u32) << (i * 8);
 335             }
 336             bitv.storage.push(last_word);
 337         }
 338
 339         bitv
 340     }
 341
 342     /// Creates a `Bitv` of the specified length where the value at each index
 343     /// is `f(index)`.
 344     ///
 345     /// # Examples
 346     ///
 347     /// ```
 348     /// use std::collections::Bitv;
 349     ///
 350     /// let bv = Bitv::from_fn(5, |i| { i % 2 == 0 });
 351     /// assert!(bv.eq_vec(&[true, false, true, false, true]));
 352     /// ```
 353     pub fn from_fn<F>(len: uint, mut f: F) -> Bitv where F: FnMut(uint) -> bool {
 354         let mut bitv = Bitv::from_elem(len, false);
 355         for i in range(0u, len) {
 356             bitv.set(i, f(i));
 357         }
 358         bitv
 359     }
 360
 361     /// Retrieves the value at index `i`, or `None` if the index is out of bounds.
 362     ///
 363     /// # Examples
 364     ///
 365     /// ```
 366     /// use std::collections::Bitv;
 367     ///
 368     /// let bv = Bitv::from_bytes(&[0b01100000]);
 369     /// assert_eq!(bv.get(0), Some(false));
 370     /// assert_eq!(bv.get(1), Some(true));
 371     /// assert_eq!(bv.get(100), None);
 372     ///
 373     /// // Can also use array indexing
 374     /// assert_eq!(bv[1], true);
 375     /// ```
 376     #[inline]
 377     #[stable]
 378     pub fn get(&self, i: uint) -> Option<bool> {
 379         if i >= self.nbits {
 380             return None;
 381         }
 382         let w = i / u32::BITS;
 383         let b = i % u32::BITS;
 384         self.storage.get(w).map(|&block|
 385             (block & (1 << b)) != 0
 386         )
 387     }
 388
 389     /// Sets the value of a bit at an index `i`.
 390     ///
 391     /// # Panics
 392     ///
 393     /// Panics if `i` is out of bounds.
 394     ///
 395     /// # Examples
 396     ///
 397     /// ```
 398     /// use std::collections::Bitv;
 399     ///
 400     /// let mut bv = Bitv::from_elem(5, false);
 401     /// bv.set(3, true);
 402     /// assert_eq!(bv[3], true);
 403     /// ```
 404     #[inline]
 405     #[unstable = "panic semantics are likely to change in the future"]
 406     pub fn set(&mut self, i: uint, x: bool) {
 407         assert!(i < self.nbits);
 408         let w = i / u32::BITS;
 409         let b = i % u32::BITS;
 410         let flag = 1 << b;
 411         let val = if x { self.storage[w] | flag }
 412                   else { self.storage[w] & !flag };
 413         self.storage[w] = val;
 414     }
 415
 416     /// Sets all bits to 1.
 417     ///
 418     /// # Examples
 419     ///
 420     /// ```
 421     /// use std::collections::Bitv;
 422     ///
 423     /// let before = 0b01100000;
 424     /// let after  = 0b11111111;
 425     ///
 426     /// let mut bv = Bitv::from_bytes(&[before]);
 427     /// bv.set_all();
 428     /// assert_eq!(bv, Bitv::from_bytes(&[after]));
 429     /// ```
 430     #[inline]
 431     pub fn set_all(&mut self) {
 432         for w in self.storage.iter_mut() { *w = !0u32; }
 433         self.fix_last_block();
 434     }
 435
 436     /// Flips all bits.
 437     ///
 438     /// # Examples
 439     ///
 440     /// ```
 441     /// use std::collections::Bitv;
 442     ///
 443     /// let before = 0b01100000;
 444     /// let after  = 0b10011111;
 445     ///
 446     /// let mut bv = Bitv::from_bytes(&[before]);
 447     /// bv.negate();
 448     /// assert_eq!(bv, Bitv::from_bytes(&[after]));
 449     /// ```
 450     #[inline]
 451     pub fn negate(&mut self) {
 452         for w in self.storage.iter_mut() { *w = !*w; }
 453         self.fix_last_block();
 454     }
 455
 456     /// Calculates the union of two bitvectors. This acts like the bitwise `or`
 457     /// function.
 458     ///
 459     /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
 460     /// the same length. Returns `true` if `self` changed.
 461     ///
 462     /// # Panics
 463     ///
 464     /// Panics if the bitvectors are of different lengths.
 465     ///
 466     /// # Examples
 467     ///
 468     /// ```
 469     /// use std::collections::Bitv;
 470     ///
 471     /// let a   = 0b01100100;
 472     /// let b   = 0b01011010;
 473     /// let res = 0b01111110;
 474     ///
 475     /// let mut a = Bitv::from_bytes(&[a]);
 476     /// let b = Bitv::from_bytes(&[b]);
 477     ///
 478     /// assert!(a.union(&b));
 479     /// assert_eq!(a, Bitv::from_bytes(&[res]));
 480     /// ```
 481     #[inline]
 482     pub fn union(&mut self, other: &Bitv) -> bool {
 483         self.process(other, |w1, w2| w1 | w2)
 484     }
 485
 486     /// Calculates the intersection of two bitvectors. This acts like the
 487     /// bitwise `and` function.
 488     ///
 489     /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
 490     /// must be the same length. Returns `true` if `self` changed.
 491     ///
 492     /// # Panics
 493     ///
 494     /// Panics if the bitvectors are of different lengths.
 495     ///
 496     /// # Examples
 497     ///
 498     /// ```
 499     /// use std::collections::Bitv;
 500     ///
 501     /// let a   = 0b01100100;
 502     /// let b   = 0b01011010;
 503     /// let res = 0b01000000;
 504     ///
 505     /// let mut a = Bitv::from_bytes(&[a]);
 506     /// let b = Bitv::from_bytes(&[b]);
 507     ///
 508     /// assert!(a.intersect(&b));
 509     /// assert_eq!(a, Bitv::from_bytes(&[res]));
 510     /// ```
 511     #[inline]
 512     pub fn intersect(&mut self, other: &Bitv) -> bool {
 513         self.process(other, |w1, w2| w1 & w2)
 514     }
 515
 516     /// Calculates the difference between two bitvectors.
 517     ///
 518     /// Sets each element of `self` to the value of that element minus the
 519     /// element of `other` at the same index. Both bitvectors must be the same
 520     /// length. Returns `true` if `self` changed.
 521     ///
 522     /// # Panics
 523     ///
 524     /// Panics if the bitvectors are of different length.
 525     ///
 526     /// # Examples
 527     ///
 528     /// ```
 529     /// use std::collections::Bitv;
 530     ///
 531     /// let a   = 0b01100100;
 532     /// let b   = 0b01011010;
 533     /// let a_b = 0b00100100; // a - b
 534     /// let b_a = 0b00011010; // b - a
 535     ///
 536     /// let mut bva = Bitv::from_bytes(&[a]);
 537     /// let bvb = Bitv::from_bytes(&[b]);
 538     ///
 539     /// assert!(bva.difference(&bvb));
 540     /// assert_eq!(bva, Bitv::from_bytes(&[a_b]));
 541     ///
 542     /// let bva = Bitv::from_bytes(&[a]);
 543     /// let mut bvb = Bitv::from_bytes(&[b]);
 544     ///
 545     /// assert!(bvb.difference(&bva));
 546     /// assert_eq!(bvb, Bitv::from_bytes(&[b_a]));
 547     /// ```
 548     #[inline]
 549     pub fn difference(&mut self, other: &Bitv) -> bool {
 550         self.process(other, |w1, w2| w1 & !w2)
 551     }
 552
 553     /// Returns `true` if all bits are 1.
 554     ///
 555     /// # Examples
 556     ///
 557     /// ```
 558     /// use std::collections::Bitv;
 559     ///
 560     /// let mut bv = Bitv::from_elem(5, true);
 561     /// assert_eq!(bv.all(), true);
 562     ///
 563     /// bv.set(1, false);
 564     /// assert_eq!(bv.all(), false);
 565     /// ```
 566     pub fn all(&self) -> bool {
 567         let mut last_word = !0u32;
 568         // Check that every block but the last is all-ones...
 569         self.blocks().all(|elem| {
 570             let tmp = last_word;
 571             last_word = elem;
 572             tmp == !0u32
 573         // and then check the last one has enough ones
 574         }) && (last_word == mask_for_bits(self.nbits))
 575     }
 576
 577     /// Returns an iterator over the elements of the vector in order.
 578     ///
 579     /// # Examples
 580     ///
 581     /// ```
 582     /// use std::collections::Bitv;
 583     ///
 584     /// let bv = Bitv::from_bytes(&[0b01110100, 0b10010010]);
 585     /// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
 586     /// ```
 587     #[inline]
 588     #[stable]
 589     pub fn iter(&self) -> Iter {
 590         Iter { bitv: self, next_idx: 0, end_idx: self.nbits }
 591     }
 592
 593     /// Returns `true` if all bits are 0.
 594     ///
 595     /// # Examples
 596     ///
 597     /// ```
 598     /// use std::collections::Bitv;
 599     ///
 600     /// let mut bv = Bitv::from_elem(10, false);
 601     /// assert_eq!(bv.none(), true);
 602     ///
 603     /// bv.set(3, true);
 604     /// assert_eq!(bv.none(), false);
 605     /// ```
 606     pub fn none(&self) -> bool {
 607         self.blocks().all(|w| w == 0)
 608     }
 609
 610     /// Returns `true` if any bit is 1.
 611     ///
 612     /// # Examples
 613     ///
 614     /// ```
 615     /// use std::collections::Bitv;
 616     ///
 617     /// let mut bv = Bitv::from_elem(10, false);
 618     /// assert_eq!(bv.any(), false);
 619     ///
 620     /// bv.set(3, true);
 621     /// assert_eq!(bv.any(), true);
 622     /// ```
 623     #[inline]
 624     pub fn any(&self) -> bool {
 625         !self.none()
 626     }
 627
 628     /// Organises the bits into bytes, such that the first bit in the
 629     /// `Bitv` becomes the high-order bit of the first byte. If the
 630     /// size of the `Bitv` is not a multiple of eight then trailing bits
 631     /// will be filled-in with `false`.
 632     ///
 633     /// # Examples
 634     ///
 635     /// ```
 636     /// use std::collections::Bitv;
 637     ///
 638     /// let mut bv = Bitv::from_elem(3, true);
 639     /// bv.set(1, false);
 640     ///
 641     /// assert_eq!(bv.to_bytes(), vec!(0b10100000));
 642     ///
 643     /// let mut bv = Bitv::from_elem(9, false);
 644     /// bv.set(2, true);
 645     /// bv.set(8, true);
 646     ///
 647     /// assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
 648     /// ```
 649     pub fn to_bytes(&self) -> Vec<u8> {
 650         fn bit(bitv: &Bitv, byte: uint, bit: uint) -> u8 {
 651             let offset = byte * 8 + bit;
 652             if offset >= bitv.nbits {
 653                 0
 654             } else {
 655                 (bitv[offset] as u8) << (7 - bit)
 656             }
 657         }
 658
 659         let len = self.nbits/8 +
 660                   if self.nbits % 8 == 0 { 0 } else { 1 };
 661         range(0, len).map(|i|
 662             bit(self, i, 0) |
 663             bit(self, i, 1) |
 664             bit(self, i, 2) |
 665             bit(self, i, 3) |
 666             bit(self, i, 4) |
 667             bit(self, i, 5) |
 668             bit(self, i, 6) |
 669             bit(self, i, 7)
 670         ).collect()
 671     }
 672
 673     /// Compares a `Bitv` to a slice of `bool`s.
 674     /// Both the `Bitv` and slice must have the same length.
 675     ///
 676     /// # Panics
 677     ///
 678     /// Panics if the `Bitv` and slice are of different length.
 679     ///
 680     /// # Examples
 681     ///
 682     /// ```
 683     /// use std::collections::Bitv;
 684     ///
 685     /// let bv = Bitv::from_bytes(&[0b10100000]);
 686     ///
 687     /// assert!(bv.eq_vec(&[true, false, true, false,
 688     ///                     false, false, false, false]));
 689     /// ```
 690     pub fn eq_vec(&self, v: &[bool]) -> bool {
 691         assert_eq!(self.nbits, v.len());
 692         iter::order::eq(self.iter(), v.iter().cloned())
 693     }
 694
 695     /// Shortens a `Bitv`, dropping excess elements.
 696     ///
 697     /// If `len` is greater than the vector's current length, this has no
 698     /// effect.
 699     ///
 700     /// # Examples
 701     ///
 702     /// ```
 703     /// use std::collections::Bitv;
 704     ///
 705     /// let mut bv = Bitv::from_bytes(&[0b01001011]);
 706     /// bv.truncate(2);
 707     /// assert!(bv.eq_vec(&[false, true]));
 708     /// ```
 709     #[stable]
 710     pub fn truncate(&mut self, len: uint) {
 711         if len < self.len() {
 712             self.nbits = len;
 713             // This fixes (2).
 714             self.storage.truncate(blocks_for_bits(len));
 715             self.fix_last_block();
 716         }
 717     }
 718
 719     /// Reserves capacity for at least `additional` more bits to be inserted in the given
 720     /// `Bitv`. The collection may reserve more space to avoid frequent reallocations.
 721     ///
 722     /// # Panics
 723     ///
 724     /// Panics if the new capacity overflows `uint`.
 725     ///
 726     /// # Examples
 727     ///
 728     /// ```
 729     /// use std::collections::Bitv;
 730     ///
 731     /// let mut bv = Bitv::from_elem(3, false);
 732     /// bv.reserve(10);
 733     /// assert_eq!(bv.len(), 3);
 734     /// assert!(bv.capacity() >= 13);
 735     /// ```
 736     #[stable]
 737     pub fn reserve(&mut self, additional: uint) {
 738         let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
 739         let storage_len = self.storage.len();
 740         if desired_cap > self.capacity() {
 741             self.storage.reserve(blocks_for_bits(desired_cap) - storage_len);
 742         }
 743     }
 744
 745     /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the
 746     /// given `Bitv`. Does nothing if the capacity is already sufficient.
 747     ///
 748     /// Note that the allocator may give the collection more space than it requests. Therefore
 749     /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
 750     /// insertions are expected.
 751     ///
 752     /// # Panics
 753     ///
 754     /// Panics if the new capacity overflows `uint`.
 755     ///
 756     /// # Examples
 757     ///
 758     /// ```
 759     /// use std::collections::Bitv;
 760     ///
 761     /// let mut bv = Bitv::from_elem(3, false);
 762     /// bv.reserve(10);
 763     /// assert_eq!(bv.len(), 3);
 764     /// assert!(bv.capacity() >= 13);
 765     /// ```
 766     #[stable]
 767     pub fn reserve_exact(&mut self, additional: uint) {
 768         let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
 769         let storage_len = self.storage.len();
 770         if desired_cap > self.capacity() {
 771             self.storage.reserve_exact(blocks_for_bits(desired_cap) - storage_len);
 772         }
 773     }
 774
 775     /// Returns the capacity in bits for this bit vector. Inserting any
 776     /// element less than this amount will not trigger a resizing.
 777     ///
 778     /// # Examples
 779     ///
 780     /// ```
 781     /// use std::collections::Bitv;
 782     ///
 783     /// let mut bv = Bitv::new();
 784     /// bv.reserve(10);
 785     /// assert!(bv.capacity() >= 10);
 786     /// ```
 787     #[inline]
 788     #[stable]
 789     pub fn capacity(&self) -> uint {
 790         self.storage.capacity().checked_mul(u32::BITS).unwrap_or(uint::MAX)
 791     }
 792
 793     /// Grows the `Bitv` in-place, adding `n` copies of `value` to the `Bitv`.
 794     ///
 795     /// # Panics
 796     ///
 797     /// Panics if the new len overflows a `uint`.
 798     ///
 799     /// # Examples
 800     ///
 801     /// ```
 802     /// use std::collections::Bitv;
 803     ///
 804     /// let mut bv = Bitv::from_bytes(&[0b01001011]);
 805     /// bv.grow(2, true);
 806     /// assert_eq!(bv.len(), 10);
 807     /// assert_eq!(bv.to_bytes(), vec!(0b01001011, 0b11000000));
 808     /// ```
 809     pub fn grow(&mut self, n: uint, value: bool) {
 810         // Note: we just bulk set all the bits in the last word in this fn in multiple places
 811         // which is technically wrong if not all of these bits are to be used. However, at the end
 812         // of this fn we call `fix_last_block` at the end of this fn, which should fix this.
 813
 814         let new_nbits = self.nbits.checked_add(n).expect("capacity overflow");
 815         let new_nblocks = blocks_for_bits(new_nbits);
 816         let full_value = if value { !0 } else { 0 };
 817
 818         // Correct the old tail word, setting or clearing formerly unused bits
 819         let old_last_word = blocks_for_bits(self.nbits) - 1;
 820         if self.nbits % u32::BITS > 0 {
 821             let mask = mask_for_bits(self.nbits);
 822             if value {
 823                 self.storage[old_last_word] |= !mask;
 824             } else {
 825                 // Extra bits are already zero by invariant.
 826             }
 827         }
 828
 829         // Fill in words after the old tail word
 830         let stop_idx = cmp::min(self.storage.len(), new_nblocks);
 831         for idx in range(old_last_word + 1, stop_idx) {
 832             self.storage[idx] = full_value;
 833         }
 834
 835         // Allocate new words, if needed
 836         if new_nblocks > self.storage.len() {
 837             let to_add = new_nblocks - self.storage.len();
 838             self.storage.extend(repeat(full_value).take(to_add));
 839         }
 840
 841         // Adjust internal bit count
 842         self.nbits = new_nbits;
 843
 844         self.fix_last_block();
 845     }
 846
 847     /// Removes the last bit from the Bitv, and returns it. Returns None if the Bitv is empty.
 848     ///
 849     /// # Examples
 850     ///
 851     /// ```
 852     /// use std::collections::Bitv;
 853     ///
 854     /// let mut bv = Bitv::from_bytes(&[0b01001001]);
 855     /// assert_eq!(bv.pop(), Some(true));
 856     /// assert_eq!(bv.pop(), Some(false));
 857     /// assert_eq!(bv.len(), 6);
 858     /// ```
 859     #[stable]
 860     pub fn pop(&mut self) -> Option<bool> {
 861         if self.is_empty() {
 862             None
 863         } else {
 864             let i = self.nbits - 1;
 865             let ret = self[i];
 866             // (3)
 867             self.set(i, false);
 868             self.nbits = i;
 869             if self.nbits % u32::BITS == 0 {
 870                 // (2)
 871                 self.storage.pop();
 872             }
 873             Some(ret)
 874         }
 875     }
 876
 877     /// Pushes a `bool` onto the end.
 878     ///
 879     /// # Examples
 880     ///
 881     /// ```
 882     /// use std::collections::Bitv;
 883     ///
 884     /// let mut bv = Bitv::new();
 885     /// bv.push(true);
 886     /// bv.push(false);
 887     /// assert!(bv.eq_vec(&[true, false]));
 888     /// ```
 889     #[stable]
 890     pub fn push(&mut self, elem: bool) {
 891         if self.nbits % u32::BITS == 0 {
 892             self.storage.push(0);
 893         }
 894         let insert_pos = self.nbits;
 895         self.nbits = self.nbits.checked_add(1).expect("Capacity overflow");
 896         self.set(insert_pos, elem);
 897     }
 898
 899     /// Return the total number of bits in this vector
 900     #[inline]
 901     #[stable]
 902     pub fn len(&self) -> uint { self.nbits }
 903
 904     /// Returns true if there are no bits in this vector
 905     #[inline]
 906     #[stable]
 907     pub fn is_empty(&self) -> bool { self.len() == 0 }
 908
 909     /// Clears all bits in this vector.
 910     #[inline]
 911     #[stable]
 912     pub fn clear(&mut self) {
 913         for w in self.storage.iter_mut() { *w = 0u32; }
 914     }
 915 }
 916
 917 #[stable]
 918 impl Default for Bitv {
 919     #[inline]
 920     fn default() -> Bitv { Bitv::new() }
 921 }
 922
 923 #[stable]
 924 impl FromIterator<bool> for Bitv {
 925     fn from_iter<I:Iterator<Item=bool>>(iterator: I) -> Bitv {
 926         let mut ret = Bitv::new();
 927         ret.extend(iterator);
 928         ret
 929     }
 930 }
 931
 932 #[stable]
 933 impl Extend<bool> for Bitv {
 934     #[inline]
 935     fn extend<I: Iterator<Item=bool>>(&mut self, mut iterator: I) {
 936         let (min, _) = iterator.size_hint();
 937         self.reserve(min);
 938         for element in iterator {
 939             self.push(element)
 940         }
 941     }
 942 }
 943
 944 #[stable]
 945 impl Clone for Bitv {
 946     #[inline]
 947     fn clone(&self) -> Bitv {
 948         Bitv { storage: self.storage.clone(), nbits: self.nbits }
 949     }
 950
 951     #[inline]
 952     fn clone_from(&mut self, source: &Bitv) {
 953         self.nbits = source.nbits;
 954         self.storage.clone_from(&source.storage);
 955     }
 956 }
 957
 958 #[stable]
 959 impl PartialOrd for Bitv {
 960     #[inline]
 961     fn partial_cmp(&self, other: &Bitv) -> Option<Ordering> {
 962         iter::order::partial_cmp(self.iter(), other.iter())
 963     }
 964 }
 965
 966 #[stable]
 967 impl Ord for Bitv {
 968     #[inline]
 969     fn cmp(&self, other: &Bitv) -> Ordering {
 970         iter::order::cmp(self.iter(), other.iter())
 971     }
 972 }
 973
 974 #[stable]
 975 impl fmt::Show for Bitv {
 976     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 977         for bit in self.iter() {
 978             try!(write!(fmt, "{}", if bit { 1u32 } else { 0u32 }));
 979         }
 980         Ok(())
 981     }
 982 }
 983
 984 #[stable]
 985 impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for Bitv {
 986     fn hash(&self, state: &mut S) {
 987         self.nbits.hash(state);
 988         for elem in self.blocks() {
 989             elem.hash(state);
 990         }
 991     }
 992 }
 993
 994 #[stable]
 995 impl cmp::PartialEq for Bitv {
 996     #[inline]
 997     fn eq(&self, other: &Bitv) -> bool {
 998         if self.nbits != other.nbits {
 999             return false;
1000         }
1001         self.blocks().zip(other.blocks()).all(|(w1, w2)| w1 == w2)
1002     }
1003 }
1004
1005 #[stable]
1006 impl cmp::Eq for Bitv {}
1007
1008 /// An iterator for `Bitv`.
1009 #[stable]
1010 #[derive(Clone)]
1011 pub struct Iter<'a> {
1012     bitv: &'a Bitv,
1013     next_idx: uint,
1014     end_idx: uint,
1015 }
1016
1017 #[stable]
1018 impl<'a> Iterator for Iter<'a> {
1019     type Item = bool;
1020
1021     #[inline]
1022     fn next(&mut self) -> Option<bool> {
1023         if self.next_idx != self.end_idx {
1024             let idx = self.next_idx;
1025             self.next_idx += 1;
1026             Some(self.bitv[idx])
1027         } else {
1028             None
1029         }
1030     }
1031
1032     fn size_hint(&self) -> (uint, Option<uint>) {
1033         let rem = self.end_idx - self.next_idx;
1034         (rem, Some(rem))
1035     }
1036 }
1037
1038 #[stable]
1039 impl<'a> DoubleEndedIterator for Iter<'a> {
1040     #[inline]
1041     fn next_back(&mut self) -> Option<bool> {
1042         if self.next_idx != self.end_idx {
1043             self.end_idx -= 1;
1044             Some(self.bitv[self.end_idx])
1045         } else {
1046             None
1047         }
1048     }
1049 }
1050
1051 #[stable]
1052 impl<'a> ExactSizeIterator for Iter<'a> {}
1053
1054 #[stable]
1055 impl<'a> RandomAccessIterator for Iter<'a> {
1056     #[inline]
1057     fn indexable(&self) -> uint {
1058         self.end_idx - self.next_idx
1059     }
1060
1061     #[inline]
1062     fn idx(&mut self, index: uint) -> Option<bool> {
1063         if index >= self.indexable() {
1064             None
1065         } else {
1066             Some(self.bitv[index])
1067         }
1068     }
1069 }
1070
1071 /// An implementation of a set using a bit vector as an underlying
1072 /// representation for holding unsigned numerical elements.
1073 ///
1074 /// It should also be noted that the amount of storage necessary for holding a
1075 /// set of objects is proportional to the maximum of the objects when viewed
1076 /// as a `uint`.
1077 ///
1078 /// # Examples
1079 ///
1080 /// ```
1081 /// use std::collections::{BitvSet, Bitv};
1082 ///
1083 /// // It's a regular set
1084 /// let mut s = BitvSet::new();
1085 /// s.insert(0);
1086 /// s.insert(3);
1087 /// s.insert(7);
1088 ///
1089 /// s.remove(&7);
1090 ///
1091 /// if !s.contains(&7) {
1092 ///     println!("There is no 7");
1093 /// }
1094 ///
1095 /// // Can initialize from a `Bitv`
1096 /// let other = BitvSet::from_bitv(Bitv::from_bytes(&[0b11010000]));
1097 ///
1098 /// s.union_with(&other);
1099 ///
1100 /// // Print 0, 1, 3 in some order
1101 /// for x in s.iter() {
1102 ///     println!("{}", x);
1103 /// }
1104 ///
1105 /// // Can convert back to a `Bitv`
1106 /// let bv: Bitv = s.into_bitv();
1107 /// assert!(bv[3]);
1108 /// ```
1109 #[derive(Clone)]
1110 #[unstable = "RFC 509"]
1111 pub struct BitvSet {
1112     bitv: Bitv,
1113 }
1114
1115 #[stable]
1116 impl Default for BitvSet {
1117     #[inline]
1118     fn default() -> BitvSet { BitvSet::new() }
1119 }
1120
1121 #[stable]
1122 impl FromIterator<uint> for BitvSet {
1123     fn from_iter<I:Iterator<Item=uint>>(iterator: I) -> BitvSet {
1124         let mut ret = BitvSet::new();
1125         ret.extend(iterator);
1126         ret
1127     }
1128 }
1129
1130 #[stable]
1131 impl Extend<uint> for BitvSet {
1132     #[inline]
1133     fn extend<I: Iterator<Item=uint>>(&mut self, mut iterator: I) {
1134         for i in iterator {
1135             self.insert(i);
1136         }
1137     }
1138 }
1139
1140 #[stable]
1141 impl PartialOrd for BitvSet {
1142     #[inline]
1143     fn partial_cmp(&self, other: &BitvSet) -> Option<Ordering> {
1144         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1145         iter::order::partial_cmp(a_iter, b_iter)
1146     }
1147 }
1148
1149 #[stable]
1150 impl Ord for BitvSet {
1151     #[inline]
1152     fn cmp(&self, other: &BitvSet) -> Ordering {
1153         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1154         iter::order::cmp(a_iter, b_iter)
1155     }
1156 }
1157
1158 #[stable]
1159 impl cmp::PartialEq for BitvSet {
1160     #[inline]
1161     fn eq(&self, other: &BitvSet) -> bool {
1162         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1163         iter::order::eq(a_iter, b_iter)
1164     }
1165 }
1166
1167 #[stable]
1168 impl cmp::Eq for BitvSet {}
1169
1170 impl BitvSet {
1171     /// Creates a new empty `BitvSet`.
1172     ///
1173     /// # Examples
1174     ///
1175     /// ```
1176     /// use std::collections::BitvSet;
1177     ///
1178     /// let mut s = BitvSet::new();
1179     /// ```
1180     #[inline]
1181     #[stable]
1182     pub fn new() -> BitvSet {
1183         BitvSet { bitv: Bitv::new() }
1184     }
1185
1186     /// Creates a new `BitvSet` with initially no contents, able to
1187     /// hold `nbits` elements without resizing.
1188     ///
1189     /// # Examples
1190     ///
1191     /// ```
1192     /// use std::collections::BitvSet;
1193     ///
1194     /// let mut s = BitvSet::with_capacity(100);
1195     /// assert!(s.capacity() >= 100);
1196     /// ```
1197     #[inline]
1198     #[stable]
1199     pub fn with_capacity(nbits: uint) -> BitvSet {
1200         let bitv = Bitv::from_elem(nbits, false);
1201         BitvSet::from_bitv(bitv)
1202     }
1203
1204     /// Creates a new `BitvSet` from the given bit vector.
1205     ///
1206     /// # Examples
1207     ///
1208     /// ```
1209     /// use std::collections::{Bitv, BitvSet};
1210     ///
1211     /// let bv = Bitv::from_bytes(&[0b01100000]);
1212     /// let s = BitvSet::from_bitv(bv);
1213     ///
1214     /// // Print 1, 2 in arbitrary order
1215     /// for x in s.iter() {
1216     ///     println!("{}", x);
1217     /// }
1218     /// ```
1219     #[inline]
1220     pub fn from_bitv(bitv: Bitv) -> BitvSet {
1221         BitvSet { bitv: bitv }
1222     }
1223
1224     /// Returns the capacity in bits for this bit vector. Inserting any
1225     /// element less than this amount will not trigger a resizing.
1226     ///
1227     /// # Examples
1228     ///
1229     /// ```
1230     /// use std::collections::BitvSet;
1231     ///
1232     /// let mut s = BitvSet::with_capacity(100);
1233     /// assert!(s.capacity() >= 100);
1234     /// ```
1235     #[inline]
1236     #[stable]
1237     pub fn capacity(&self) -> uint {
1238         self.bitv.capacity()
1239     }
1240
1241     /// Reserves capacity for the given `BitvSet` to contain `len` distinct elements. In the case
1242     /// of `BitvSet` this means reallocations will not occur as long as all inserted elements
1243     /// are less than `len`.
1244     ///
1245     /// The collection may reserve more space to avoid frequent reallocations.
1246     ///
1247     ///
1248     /// # Examples
1249     ///
1250     /// ```
1251     /// use std::collections::BitvSet;
1252     ///
1253     /// let mut s = BitvSet::new();
1254     /// s.reserve_len(10);
1255     /// assert!(s.capacity() >= 10);
1256     /// ```
1257     #[stable]
1258     pub fn reserve_len(&mut self, len: uint) {
1259         let cur_len = self.bitv.len();
1260         if len >= cur_len {
1261             self.bitv.reserve(len - cur_len);
1262         }
1263     }
1264
1265     /// Reserves the minimum capacity for the given `BitvSet` to contain `len` distinct elements.
1266     /// In the case of `BitvSet` this means reallocations will not occur as long as all inserted
1267     /// elements are less than `len`.
1268     ///
1269     /// Note that the allocator may give the collection more space than it requests. Therefore
1270     /// capacity can not be relied upon to be precisely minimal. Prefer `reserve_len` if future
1271     /// insertions are expected.
1272     ///
1273     ///
1274     /// # Examples
1275     ///
1276     /// ```
1277     /// use std::collections::BitvSet;
1278     ///
1279     /// let mut s = BitvSet::new();
1280     /// s.reserve_len_exact(10);
1281     /// assert!(s.capacity() >= 10);
1282     /// ```
1283     #[stable]
1284     pub fn reserve_len_exact(&mut self, len: uint) {
1285         let cur_len = self.bitv.len();
1286         if len >= cur_len {
1287             self.bitv.reserve_exact(len - cur_len);
1288         }
1289     }
1290
1291
1292     /// Consumes this set to return the underlying bit vector.
1293     ///
1294     /// # Examples
1295     ///
1296     /// ```
1297     /// use std::collections::BitvSet;
1298     ///
1299     /// let mut s = BitvSet::new();
1300     /// s.insert(0);
1301     /// s.insert(3);
1302     ///
1303     /// let bv = s.into_bitv();
1304     /// assert!(bv[0]);
1305     /// assert!(bv[3]);
1306     /// ```
1307     #[inline]
1308     pub fn into_bitv(self) -> Bitv {
1309         self.bitv
1310     }
1311
1312     /// Returns a reference to the underlying bit vector.
1313     ///
1314     /// # Examples
1315     ///
1316     /// ```
1317     /// use std::collections::BitvSet;
1318     ///
1319     /// let mut s = BitvSet::new();
1320     /// s.insert(0);
1321     ///
1322     /// let bv = s.get_ref();
1323     /// assert_eq!(bv[0], true);
1324     /// ```
1325     #[inline]
1326     pub fn get_ref(&self) -> &Bitv {
1327         &self.bitv
1328     }
1329
1330     #[inline]
1331     fn other_op<F>(&mut self, other: &BitvSet, mut f: F) where F: FnMut(u32, u32) -> u32 {
1332         // Unwrap Bitvs
1333         let self_bitv = &mut self.bitv;
1334         let other_bitv = &other.bitv;
1335
1336         let self_len = self_bitv.len();
1337         let other_len = other_bitv.len();
1338
1339         // Expand the vector if necessary
1340         if self_len < other_len {
1341             self_bitv.grow(other_len - self_len, false);
1342         }
1343
1344         // virtually pad other with 0's for equal lengths
1345         let mut other_words = {
1346             let (_, result) = match_words(self_bitv, other_bitv);
1347             result
1348         };
1349
1350         // Apply values found in other
1351         for (i, w) in other_words {
1352             let old = self_bitv.storage[i];
1353             let new = f(old, w);
1354             self_bitv.storage[i] = new;
1355         }
1356     }
1357
1358     /// Truncates the underlying vector to the least length required.
1359     ///
1360     /// # Examples
1361     ///
1362     /// ```
1363     /// use std::collections::BitvSet;
1364     ///
1365     /// let mut s = BitvSet::new();
1366     /// s.insert(32183231);
1367     /// s.remove(&32183231);
1368     ///
1369     /// // Internal storage will probably be bigger than necessary
1370     /// println!("old capacity: {}", s.capacity());
1371     ///
1372     /// // Now should be smaller
1373     /// s.shrink_to_fit();
1374     /// println!("new capacity: {}", s.capacity());
1375     /// ```
1376     #[inline]
1377     #[stable]
1378     pub fn shrink_to_fit(&mut self) {
1379         let bitv = &mut self.bitv;
1380         // Obtain original length
1381         let old_len = bitv.storage.len();
1382         // Obtain coarse trailing zero length
1383         let n = bitv.storage.iter().rev().take_while(|&&n| n == 0).count();
1384         // Truncate
1385         let trunc_len = cmp::max(old_len - n, 1);
1386         bitv.storage.truncate(trunc_len);
1387         bitv.nbits = trunc_len * u32::BITS;
1388     }
1389
1390     /// Iterator over each u32 stored in the `BitvSet`.
1391     ///
1392     /// # Examples
1393     ///
1394     /// ```
1395     /// use std::collections::{Bitv, BitvSet};
1396     ///
1397     /// let s = BitvSet::from_bitv(Bitv::from_bytes(&[0b01001010]));
1398     ///
1399     /// // Print 1, 4, 6 in arbitrary order
1400     /// for x in s.iter() {
1401     ///     println!("{}", x);
1402     /// }
1403     /// ```
1404     #[inline]
1405     #[stable]
1406     pub fn iter(&self) -> bitv_set::Iter {
1407         SetIter {set: self, next_idx: 0u}
1408     }
1409
1410     /// Iterator over each u32 stored in `self` union `other`.
1411     /// See [union_with](#method.union_with) for an efficient in-place version.
1412     ///
1413     /// # Examples
1414     ///
1415     /// ```
1416     /// use std::collections::{Bitv, BitvSet};
1417     ///
1418     /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
1419     /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
1420     ///
1421     /// // Print 0, 1, 2, 4 in arbitrary order
1422     /// for x in a.union(&b) {
1423     ///     println!("{}", x);
1424     /// }
1425     /// ```
1426     #[inline]
1427     #[stable]
1428     pub fn union<'a>(&'a self, other: &'a BitvSet) -> Union<'a> {
1429         fn or(w1: u32, w2: u32) -> u32 { w1 | w2 }
1430
1431         Union(TwoBitPositions {
1432             set: self,
1433             other: other,
1434             merge: or,
1435             current_word: 0u32,
1436             next_idx: 0u
1437         })
1438     }
1439
1440     /// Iterator over each uint stored in `self` intersect `other`.
1441     /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
1442     ///
1443     /// # Examples
1444     ///
1445     /// ```
1446     /// use std::collections::{Bitv, BitvSet};
1447     ///
1448     /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
1449     /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
1450     ///
1451     /// // Print 2
1452     /// for x in a.intersection(&b) {
1453     ///     println!("{}", x);
1454     /// }
1455     /// ```
1456     #[inline]
1457     #[stable]
1458     pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Intersection<'a> {
1459         fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 }
1460         let min = cmp::min(self.bitv.len(), other.bitv.len());
1461         Intersection(TwoBitPositions {
1462             set: self,
1463             other: other,
1464             merge: bitand,
1465             current_word: 0u32,
1466             next_idx: 0
1467         }.take(min))
1468     }
1469
1470     /// Iterator over each uint stored in the `self` setminus `other`.
1471     /// See [difference_with](#method.difference_with) for an efficient in-place version.
1472     ///
1473     /// # Examples
1474     ///
1475     /// ```
1476     /// use std::collections::{BitvSet, Bitv};
1477     ///
1478     /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
1479     /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
1480     ///
1481     /// // Print 1, 4 in arbitrary order
1482     /// for x in a.difference(&b) {
1483     ///     println!("{}", x);
1484     /// }
1485     ///
1486     /// // Note that difference is not symmetric,
1487     /// // and `b - a` means something else.
1488     /// // This prints 0
1489     /// for x in b.difference(&a) {
1490     ///     println!("{}", x);
1491     /// }
1492     /// ```
1493     #[inline]
1494     #[stable]
1495     pub fn difference<'a>(&'a self, other: &'a BitvSet) -> Difference<'a> {
1496         fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 }
1497
1498         Difference(TwoBitPositions {
1499             set: self,
1500             other: other,
1501             merge: diff,
1502             current_word: 0u32,
1503             next_idx: 0
1504         })
1505     }
1506
1507     /// Iterator over each u32 stored in the symmetric difference of `self` and `other`.
1508     /// See [symmetric_difference_with](#method.symmetric_difference_with) for
1509     /// an efficient in-place version.
1510     ///
1511     /// # Examples
1512     ///
1513     /// ```
1514     /// use std::collections::{BitvSet, Bitv};
1515     ///
1516     /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
1517     /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
1518     ///
1519     /// // Print 0, 1, 4 in arbitrary order
1520     /// for x in a.symmetric_difference(&b) {
1521     ///     println!("{}", x);
1522     /// }
1523     /// ```
1524     #[inline]
1525     #[stable]
1526     pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> SymmetricDifference<'a> {
1527         fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 }
1528
1529         SymmetricDifference(TwoBitPositions {
1530             set: self,
1531             other: other,
1532             merge: bitxor,
1533             current_word: 0u32,
1534             next_idx: 0
1535         })
1536     }
1537
1538     /// Unions in-place with the specified other bit vector.
1539     ///
1540     /// # Examples
1541     ///
1542     /// ```
1543     /// use std::collections::{BitvSet, Bitv};
1544     ///
1545     /// let a   = 0b01101000;
1546     /// let b   = 0b10100000;
1547     /// let res = 0b11101000;
1548     ///
1549     /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1550     /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1551     /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
1552     ///
1553     /// a.union_with(&b);
1554     /// assert_eq!(a, res);
1555     /// ```
1556     #[inline]
1557     pub fn union_with(&mut self, other: &BitvSet) {
1558         self.other_op(other, |w1, w2| w1 | w2);
1559     }
1560
1561     /// Intersects in-place with the specified other bit vector.
1562     ///
1563     /// # Examples
1564     ///
1565     /// ```
1566     /// use std::collections::{BitvSet, Bitv};
1567     ///
1568     /// let a   = 0b01101000;
1569     /// let b   = 0b10100000;
1570     /// let res = 0b00100000;
1571     ///
1572     /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1573     /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1574     /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
1575     ///
1576     /// a.intersect_with(&b);
1577     /// assert_eq!(a, res);
1578     /// ```
1579     #[inline]
1580     pub fn intersect_with(&mut self, other: &BitvSet) {
1581         self.other_op(other, |w1, w2| w1 & w2);
1582     }
1583
1584     /// Makes this bit vector the difference with the specified other bit vector
1585     /// in-place.
1586     ///
1587     /// # Examples
1588     ///
1589     /// ```
1590     /// use std::collections::{BitvSet, Bitv};
1591     ///
1592     /// let a   = 0b01101000;
1593     /// let b   = 0b10100000;
1594     /// let a_b = 0b01001000; // a - b
1595     /// let b_a = 0b10000000; // b - a
1596     ///
1597     /// let mut bva = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1598     /// let bvb = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1599     /// let bva_b = BitvSet::from_bitv(Bitv::from_bytes(&[a_b]));
1600     /// let bvb_a = BitvSet::from_bitv(Bitv::from_bytes(&[b_a]));
1601     ///
1602     /// bva.difference_with(&bvb);
1603     /// assert_eq!(bva, bva_b);
1604     ///
1605     /// let bva = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1606     /// let mut bvb = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1607     ///
1608     /// bvb.difference_with(&bva);
1609     /// assert_eq!(bvb, bvb_a);
1610     /// ```
1611     #[inline]
1612     pub fn difference_with(&mut self, other: &BitvSet) {
1613         self.other_op(other, |w1, w2| w1 & !w2);
1614     }
1615
1616     /// Makes this bit vector the symmetric difference with the specified other
1617     /// bit vector in-place.
1618     ///
1619     /// # Examples
1620     ///
1621     /// ```
1622     /// use std::collections::{BitvSet, Bitv};
1623     ///
1624     /// let a   = 0b01101000;
1625     /// let b   = 0b10100000;
1626     /// let res = 0b11001000;
1627     ///
1628     /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1629     /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1630     /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
1631     ///
1632     /// a.symmetric_difference_with(&b);
1633     /// assert_eq!(a, res);
1634     /// ```
1635     #[inline]
1636     pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
1637         self.other_op(other, |w1, w2| w1 ^ w2);
1638     }
1639
1640     /// Return the number of set bits in this set.
1641     #[inline]
1642     #[stable]
1643     pub fn len(&self) -> uint  {
1644         self.bitv.blocks().fold(0, |acc, n| acc + n.count_ones())
1645     }
1646
1647     /// Returns whether there are no bits set in this set
1648     #[inline]
1649     #[stable]
1650     pub fn is_empty(&self) -> bool {
1651         self.bitv.none()
1652     }
1653
1654     /// Clears all bits in this set
1655     #[inline]
1656     #[stable]
1657     pub fn clear(&mut self) {
1658         self.bitv.clear();
1659     }
1660
1661     /// Returns `true` if this set contains the specified integer.
1662     #[inline]
1663     #[stable]
1664     pub fn contains(&self, value: &uint) -> bool {
1665         let bitv = &self.bitv;
1666         *value < bitv.nbits && bitv[*value]
1667     }
1668
1669     /// Returns `true` if the set has no elements in common with `other`.
1670     /// This is equivalent to checking for an empty intersection.
1671     #[inline]
1672     #[stable]
1673     pub fn is_disjoint(&self, other: &BitvSet) -> bool {
1674         self.intersection(other).next().is_none()
1675     }
1676
1677     /// Returns `true` if the set is a subset of another.
1678     #[inline]
1679     #[stable]
1680     pub fn is_subset(&self, other: &BitvSet) -> bool {
1681         let self_bitv = &self.bitv;
1682         let other_bitv = &other.bitv;
1683         let other_blocks = blocks_for_bits(other_bitv.len());
1684
1685         // Check that `self` intersect `other` is self
1686         self_bitv.blocks().zip(other_bitv.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
1687         // Make sure if `self` has any more blocks than `other`, they're all 0
1688         self_bitv.blocks().skip(other_blocks).all(|w| w == 0)
1689     }
1690
1691     /// Returns `true` if the set is a superset of another.
1692     #[inline]
1693     #[stable]
1694     pub fn is_superset(&self, other: &BitvSet) -> bool {
1695         other.is_subset(self)
1696     }
1697
1698     /// Adds a value to the set. Returns `true` if the value was not already
1699     /// present in the set.
1700     #[stable]
1701     pub fn insert(&mut self, value: uint) -> bool {
1702         if self.contains(&value) {
1703             return false;
1704         }
1705
1706         // Ensure we have enough space to hold the new element
1707         let len = self.bitv.len();
1708         if value >= len {
1709             self.bitv.grow(value - len + 1, false)
1710         }
1711
1712         self.bitv.set(value, true);
1713         return true;
1714     }
1715
1716     /// Removes a value from the set. Returns `true` if the value was
1717     /// present in the set.
1718     #[stable]
1719     pub fn remove(&mut self, value: &uint) -> bool {
1720         if !self.contains(value) {
1721             return false;
1722         }
1723
1724         self.bitv.set(*value, false);
1725
1726         return true;
1727     }
1728 }
1729
1730 impl fmt::Show for BitvSet {
1731     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
1732         try!(write!(fmt, "BitvSet {{"));
1733         let mut first = true;
1734         for n in self.iter() {
1735             if !first {
1736                 try!(write!(fmt, ", "));
1737             }
1738             try!(write!(fmt, "{:?}", n));
1739             first = false;
1740         }
1741         write!(fmt, "}}")
1742     }
1743 }
1744
1745 impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitvSet {
1746     fn hash(&self, state: &mut S) {
1747         for pos in self.iter() {
1748             pos.hash(state);
1749         }
1750     }
1751 }
1752
1753 /// An iterator for `BitvSet`.
1754 #[derive(Clone)]
1755 #[stable]
1756 pub struct SetIter<'a> {
1757     set: &'a BitvSet,
1758     next_idx: uint
1759 }
1760
1761 /// An iterator combining two `BitvSet` iterators.
1762 #[derive(Clone)]
1763 struct TwoBitPositions<'a> {
1764     set: &'a BitvSet,
1765     other: &'a BitvSet,
1766     merge: fn(u32, u32) -> u32,
1767     current_word: u32,
1768     next_idx: uint
1769 }
1770
1771 #[stable]
1772 pub struct Union<'a>(TwoBitPositions<'a>);
1773 #[stable]
1774 pub struct Intersection<'a>(Take<TwoBitPositions<'a>>);
1775 #[stable]
1776 pub struct Difference<'a>(TwoBitPositions<'a>);
1777 #[stable]
1778 pub struct SymmetricDifference<'a>(TwoBitPositions<'a>);
1779
1780 #[stable]
1781 impl<'a> Iterator for SetIter<'a> {
1782     type Item = uint;
1783
1784     fn next(&mut self) -> Option<uint> {
1785         while self.next_idx < self.set.bitv.len() {
1786             let idx = self.next_idx;
1787             self.next_idx += 1;
1788
1789             if self.set.contains(&idx) {
1790                 return Some(idx);
1791             }
1792         }
1793
1794         return None;
1795     }
1796
1797     #[inline]
1798     fn size_hint(&self) -> (uint, Option<uint>) {
1799         (0, Some(self.set.bitv.len() - self.next_idx))
1800     }
1801 }
1802
1803 #[stable]
1804 impl<'a> Iterator for TwoBitPositions<'a> {
1805     type Item = uint;
1806
1807     fn next(&mut self) -> Option<uint> {
1808         while self.next_idx < self.set.bitv.len() ||
1809               self.next_idx < self.other.bitv.len() {
1810             let bit_idx = self.next_idx % u32::BITS;
1811             if bit_idx == 0 {
1812                 let s_bitv = &self.set.bitv;
1813                 let o_bitv = &self.other.bitv;
1814                 // Merging the two words is a bit of an awkward dance since
1815                 // one Bitv might be longer than the other
1816                 let word_idx = self.next_idx / u32::BITS;
1817                 let w1 = if word_idx < s_bitv.storage.len() {
1818                              s_bitv.storage[word_idx]
1819                          } else { 0 };
1820                 let w2 = if word_idx < o_bitv.storage.len() {
1821                              o_bitv.storage[word_idx]
1822                          } else { 0 };
1823                 self.current_word = (self.merge)(w1, w2);
1824             }
1825
1826             self.next_idx += 1;
1827             if self.current_word & (1 << bit_idx) != 0 {
1828                 return Some(self.next_idx - 1);
1829             }
1830         }
1831         return None;
1832     }
1833
1834     #[inline]
1835     fn size_hint(&self) -> (uint, Option<uint>) {
1836         let cap = cmp::max(self.set.bitv.len(), self.other.bitv.len());
1837         (0, Some(cap - self.next_idx))
1838     }
1839 }
1840
1841 #[stable]
1842 impl<'a> Iterator for Union<'a> {
1843     type Item = uint;
1844
1845     #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
1846     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
1847 }
1848
1849 #[stable]
1850 impl<'a> Iterator for Intersection<'a> {
1851     type Item = uint;
1852
1853     #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
1854     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
1855 }
1856
1857 #[stable]
1858 impl<'a> Iterator for Difference<'a> {
1859     type Item = uint;
1860
1861     #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
1862     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
1863 }
1864
1865 #[stable]
1866 impl<'a> Iterator for SymmetricDifference<'a> {
1867     type Item = uint;
1868
1869     #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
1870     #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
1871 }
1872
1873
1874 #[cfg(test)]
1875 mod tests {
1876     use prelude::*;
1877     use core::u32;
1878
1879     use super::Bitv;
1880
1881     #[test]
1882     fn test_to_str() {
1883         let zerolen = Bitv::new();
1884         assert_eq!(format!("{:?}", zerolen), "");
1885
1886         let eightbits = Bitv::from_elem(8u, false);
1887         assert_eq!(format!("{:?}", eightbits), "00000000")
1888     }
1889
1890     #[test]
1891     fn test_0_elements() {
1892         let act = Bitv::new();
1893         let exp = Vec::new();
1894         assert!(act.eq_vec(exp.as_slice()));
1895         assert!(act.none() && act.all());
1896     }
1897
1898     #[test]
1899     fn test_1_element() {
1900         let mut act = Bitv::from_elem(1u, false);
1901         assert!(act.eq_vec(&[false]));
1902         assert!(act.none() && !act.all());
1903         act = Bitv::from_elem(1u, true);
1904         assert!(act.eq_vec(&[true]));
1905         assert!(!act.none() && act.all());
1906     }
1907
1908     #[test]
1909     fn test_2_elements() {
1910         let mut b = Bitv::from_elem(2, false);
1911         b.set(0, true);
1912         b.set(1, false);
1913         assert_eq!(format!("{:?}", b), "10");
1914         assert!(!b.none() && !b.all());
1915     }
1916
1917     #[test]
1918     fn test_10_elements() {
1919         let mut act;
1920         // all 0
1921
1922         act = Bitv::from_elem(10u, false);
1923         assert!((act.eq_vec(
1924                     &[false, false, false, false, false, false, false, false, false, false])));
1925         assert!(act.none() && !act.all());
1926         // all 1
1927
1928         act = Bitv::from_elem(10u, true);
1929         assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
1930         assert!(!act.none() && act.all());
1931         // mixed
1932
1933         act = Bitv::from_elem(10u, false);
1934         act.set(0u, true);
1935         act.set(1u, true);
1936         act.set(2u, true);
1937         act.set(3u, true);
1938         act.set(4u, true);
1939         assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
1940         assert!(!act.none() && !act.all());
1941         // mixed
1942
1943         act = Bitv::from_elem(10u, false);
1944         act.set(5u, true);
1945         act.set(6u, true);
1946         act.set(7u, true);
1947         act.set(8u, true);
1948         act.set(9u, true);
1949         assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
1950         assert!(!act.none() && !act.all());
1951         // mixed
1952
1953         act = Bitv::from_elem(10u, false);
1954         act.set(0u, true);
1955         act.set(3u, true);
1956         act.set(6u, true);
1957         act.set(9u, true);
1958         assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
1959         assert!(!act.none() && !act.all());
1960     }
1961
1962     #[test]
1963     fn test_31_elements() {
1964         let mut act;
1965         // all 0
1966
1967         act = Bitv::from_elem(31u, false);
1968         assert!(act.eq_vec(
1969                 &[false, false, false, false, false, false, false, false, false, false, false,
1970                   false, false, false, false, false, false, false, false, false, false, false,
1971                   false, false, false, false, false, false, false, false, false]));
1972         assert!(act.none() && !act.all());
1973         // all 1
1974
1975         act = Bitv::from_elem(31u, true);
1976         assert!(act.eq_vec(
1977                 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1978                   true, true, true, true, true, true, true, true, true, true, true, true, true,
1979                   true, true, true, true, true]));
1980         assert!(!act.none() && act.all());
1981         // mixed
1982
1983         act = Bitv::from_elem(31u, false);
1984         act.set(0u, true);
1985         act.set(1u, true);
1986         act.set(2u, true);
1987         act.set(3u, true);
1988         act.set(4u, true);
1989         act.set(5u, true);
1990         act.set(6u, true);
1991         act.set(7u, true);
1992         assert!(act.eq_vec(
1993                 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1994                   false, false, false, false, false, false, false, false, false, false, false,
1995                   false, false, false, false, false, false, false]));
1996         assert!(!act.none() && !act.all());
1997         // mixed
1998
1999         act = Bitv::from_elem(31u, false);
2000         act.set(16u, true);
2001         act.set(17u, true);
2002         act.set(18u, true);
2003         act.set(19u, true);
2004         act.set(20u, true);
2005         act.set(21u, true);
2006         act.set(22u, true);
2007         act.set(23u, true);
2008         assert!(act.eq_vec(
2009                 &[false, false, false, false, false, false, false, false, false, false, false,
2010                   false, false, false, false, false, true, true, true, true, true, true, true, true,
2011                   false, false, false, false, false, false, false]));
2012         assert!(!act.none() && !act.all());
2013         // mixed
2014
2015         act = Bitv::from_elem(31u, false);
2016         act.set(24u, true);
2017         act.set(25u, true);
2018         act.set(26u, true);
2019         act.set(27u, true);
2020         act.set(28u, true);
2021         act.set(29u, true);
2022         act.set(30u, true);
2023         assert!(act.eq_vec(
2024                 &[false, false, false, false, false, false, false, false, false, false, false,
2025                   false, false, false, false, false, false, false, false, false, false, false,
2026                   false, false, true, true, true, true, true, true, true]));
2027         assert!(!act.none() && !act.all());
2028         // mixed
2029
2030         act = Bitv::from_elem(31u, false);
2031         act.set(3u, true);
2032         act.set(17u, true);
2033         act.set(30u, true);
2034         assert!(act.eq_vec(
2035                 &[false, false, false, true, false, false, false, false, false, false, false, false,
2036                   false, false, false, false, false, true, false, false, false, false, false, false,
2037                   false, false, false, false, false, false, true]));
2038         assert!(!act.none() && !act.all());
2039     }
2040
2041     #[test]
2042     fn test_32_elements() {
2043         let mut act;
2044         // all 0
2045
2046         act = Bitv::from_elem(32u, false);
2047         assert!(act.eq_vec(
2048                 &[false, false, false, false, false, false, false, false, false, false, false,
2049                   false, false, false, false, false, false, false, false, false, false, false,
2050                   false, false, false, false, false, false, false, false, false, false]));
2051         assert!(act.none() && !act.all());
2052         // all 1
2053
2054         act = Bitv::from_elem(32u, true);
2055         assert!(act.eq_vec(
2056                 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
2057                   true, true, true, true, true, true, true, true, true, true, true, true, true,
2058                   true, true, true, true, true, true]));
2059         assert!(!act.none() && act.all());
2060         // mixed
2061
2062         act = Bitv::from_elem(32u, false);
2063         act.set(0u, true);
2064         act.set(1u, true);
2065         act.set(2u, true);
2066         act.set(3u, true);
2067         act.set(4u, true);
2068         act.set(5u, true);
2069         act.set(6u, true);
2070         act.set(7u, true);
2071         assert!(act.eq_vec(
2072                 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
2073                   false, false, false, false, false, false, false, false, false, false, false,
2074                   false, false, false, false, false, false, false, false]));
2075         assert!(!act.none() && !act.all());
2076         // mixed
2077
2078         act = Bitv::from_elem(32u, false);
2079         act.set(16u, true);
2080         act.set(17u, true);
2081         act.set(18u, true);
2082         act.set(19u, true);
2083         act.set(20u, true);
2084         act.set(21u, true);
2085         act.set(22u, true);
2086         act.set(23u, true);
2087         assert!(act.eq_vec(
2088                 &[false, false, false, false, false, false, false, false, false, false, false,
2089                   false, false, false, false, false, true, true, true, true, true, true, true, true,
2090                   false, false, false, false, false, false, false, false]));
2091         assert!(!act.none() && !act.all());
2092         // mixed
2093
2094         act = Bitv::from_elem(32u, false);
2095         act.set(24u, true);
2096         act.set(25u, true);
2097         act.set(26u, true);
2098         act.set(27u, true);
2099         act.set(28u, true);
2100         act.set(29u, true);
2101         act.set(30u, true);
2102         act.set(31u, true);
2103         assert!(act.eq_vec(
2104                 &[false, false, false, false, false, false, false, false, false, false, false,
2105                   false, false, false, false, false, false, false, false, false, false, false,
2106                   false, false, true, true, true, true, true, true, true, true]));
2107         assert!(!act.none() && !act.all());
2108         // mixed
2109
2110         act = Bitv::from_elem(32u, false);
2111         act.set(3u, true);
2112         act.set(17u, true);
2113         act.set(30u, true);
2114         act.set(31u, true);
2115         assert!(act.eq_vec(
2116                 &[false, false, false, true, false, false, false, false, false, false, false, false,
2117                   false, false, false, false, false, true, false, false, false, false, false, false,
2118                   false, false, false, false, false, false, true, true]));
2119         assert!(!act.none() && !act.all());
2120     }
2121
2122     #[test]
2123     fn test_33_elements() {
2124         let mut act;
2125         // all 0
2126
2127         act = Bitv::from_elem(33u, false);
2128         assert!(act.eq_vec(
2129                 &[false, false, false, false, false, false, false, false, false, false, false,
2130                   false, false, false, false, false, false, false, false, false, false, false,
2131                   false, false, false, false, false, false, false, false, false, false, false]));
2132         assert!(act.none() && !act.all());
2133         // all 1
2134
2135         act = Bitv::from_elem(33u, true);
2136         assert!(act.eq_vec(
2137                 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
2138                   true, true, true, true, true, true, true, true, true, true, true, true, true,
2139                   true, true, true, true, true, true, true]));
2140         assert!(!act.none() && act.all());
2141         // mixed
2142
2143         act = Bitv::from_elem(33u, false);
2144         act.set(0u, true);
2145         act.set(1u, true);
2146         act.set(2u, true);
2147         act.set(3u, true);
2148         act.set(4u, true);
2149         act.set(5u, true);
2150         act.set(6u, true);
2151         act.set(7u, true);
2152         assert!(act.eq_vec(
2153                 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
2154                   false, false, false, false, false, false, false, false, false, false, false,
2155                   false, false, false, false, false, false, false, false, false]));
2156         assert!(!act.none() && !act.all());
2157         // mixed
2158
2159         act = Bitv::from_elem(33u, false);
2160         act.set(16u, true);
2161         act.set(17u, true);
2162         act.set(18u, true);
2163         act.set(19u, true);
2164         act.set(20u, true);
2165         act.set(21u, true);
2166         act.set(22u, true);
2167         act.set(23u, true);
2168         assert!(act.eq_vec(
2169                 &[false, false, false, false, false, false, false, false, false, false, false,
2170                   false, false, false, false, false, true, true, true, true, true, true, true, true,
2171                   false, false, false, false, false, false, false, false, false]));
2172         assert!(!act.none() && !act.all());
2173         // mixed
2174
2175         act = Bitv::from_elem(33u, false);
2176         act.set(24u, true);
2177         act.set(25u, true);
2178         act.set(26u, true);
2179         act.set(27u, true);
2180         act.set(28u, true);
2181         act.set(29u, true);
2182         act.set(30u, true);
2183         act.set(31u, true);
2184         assert!(act.eq_vec(
2185                 &[false, false, false, false, false, false, false, false, false, false, false,
2186                   false, false, false, false, false, false, false, false, false, false, false,
2187                   false, false, true, true, true, true, true, true, true, true, false]));
2188         assert!(!act.none() && !act.all());
2189         // mixed
2190
2191         act = Bitv::from_elem(33u, false);
2192         act.set(3u, true);
2193         act.set(17u, true);
2194         act.set(30u, true);
2195         act.set(31u, true);
2196         act.set(32u, true);
2197         assert!(act.eq_vec(
2198                 &[false, false, false, true, false, false, false, false, false, false, false, false,
2199                   false, false, false, false, false, true, false, false, false, false, false, false,
2200                   false, false, false, false, false, false, true, true, true]));
2201         assert!(!act.none() && !act.all());
2202     }
2203
2204     #[test]
2205     fn test_equal_differing_sizes() {
2206         let v0 = Bitv::from_elem(10u, false);
2207         let v1 = Bitv::from_elem(11u, false);
2208         assert!(v0 != v1);
2209     }
2210
2211     #[test]
2212     fn test_equal_greatly_differing_sizes() {
2213         let v0 = Bitv::from_elem(10u, false);
2214         let v1 = Bitv::from_elem(110u, false);
2215         assert!(v0 != v1);
2216     }
2217
2218     #[test]
2219     fn test_equal_sneaky_small() {
2220         let mut a = Bitv::from_elem(1, false);
2221         a.set(0, true);
2222
2223         let mut b = Bitv::from_elem(1, true);
2224         b.set(0, true);
2225
2226         assert_eq!(a, b);
2227     }
2228
2229     #[test]
2230     fn test_equal_sneaky_big() {
2231         let mut a = Bitv::from_elem(100, false);
2232         for i in range(0u, 100) {
2233             a.set(i, true);
2234         }
2235
2236         let mut b = Bitv::from_elem(100, true);
2237         for i in range(0u, 100) {
2238             b.set(i, true);
2239         }
2240
2241         assert_eq!(a, b);
2242     }
2243
2244     #[test]
2245     fn test_from_bytes() {
2246         let bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2247         let str = concat!("10110110", "00000000", "11111111");
2248         assert_eq!(format!("{:?}", bitv), str);
2249     }
2250
2251     #[test]
2252     fn test_to_bytes() {
2253         let mut bv = Bitv::from_elem(3, true);
2254         bv.set(1, false);
2255         assert_eq!(bv.to_bytes(), vec!(0b10100000));
2256
2257         let mut bv = Bitv::from_elem(9, false);
2258         bv.set(2, true);
2259         bv.set(8, true);
2260         assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
2261     }
2262
2263     #[test]
2264     fn test_from_bools() {
2265         let bools = vec![true, false, true, true];
2266         let bitv: Bitv = bools.iter().map(|n| *n).collect();
2267         assert_eq!(format!("{:?}", bitv), "1011");
2268     }
2269
2270     #[test]
2271     fn test_to_bools() {
2272         let bools = vec!(false, false, true, false, false, true, true, false);
2273         assert_eq!(Bitv::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
2274     }
2275
2276     #[test]
2277     fn test_bitv_iterator() {
2278         let bools = vec![true, false, true, true];
2279         let bitv: Bitv = bools.iter().map(|n| *n).collect();
2280
2281         assert_eq!(bitv.iter().collect::<Vec<bool>>(), bools);
2282
2283         let long = range(0, 10000).map(|i| i % 2 == 0).collect::<Vec<_>>();
2284         let bitv: Bitv = long.iter().map(|n| *n).collect();
2285         assert_eq!(bitv.iter().collect::<Vec<bool>>(), long)
2286     }
2287
2288     #[test]
2289     fn test_small_difference() {
2290         let mut b1 = Bitv::from_elem(3, false);
2291         let mut b2 = Bitv::from_elem(3, false);
2292         b1.set(0, true);
2293         b1.set(1, true);
2294         b2.set(1, true);
2295         b2.set(2, true);
2296         assert!(b1.difference(&b2));
2297         assert!(b1[0]);
2298         assert!(!b1[1]);
2299         assert!(!b1[2]);
2300     }
2301
2302     #[test]
2303     fn test_big_difference() {
2304         let mut b1 = Bitv::from_elem(100, false);
2305         let mut b2 = Bitv::from_elem(100, false);
2306         b1.set(0, true);
2307         b1.set(40, true);
2308         b2.set(40, true);
2309         b2.set(80, true);
2310         assert!(b1.difference(&b2));
2311         assert!(b1[0]);
2312         assert!(!b1[40]);
2313         assert!(!b1[80]);
2314     }
2315
2316     #[test]
2317     fn test_small_clear() {
2318         let mut b = Bitv::from_elem(14, true);
2319         assert!(!b.none() && b.all());
2320         b.clear();
2321         assert!(b.none() && !b.all());
2322     }
2323
2324     #[test]
2325     fn test_big_clear() {
2326         let mut b = Bitv::from_elem(140, true);
2327         assert!(!b.none() && b.all());
2328         b.clear();
2329         assert!(b.none() && !b.all());
2330     }
2331
2332     #[test]
2333     fn test_bitv_lt() {
2334         let mut a = Bitv::from_elem(5u, false);
2335         let mut b = Bitv::from_elem(5u, false);
2336
2337         assert!(!(a < b) && !(b < a));
2338         b.set(2, true);
2339         assert!(a < b);
2340         a.set(3, true);
2341         assert!(a < b);
2342         a.set(2, true);
2343         assert!(!(a < b) && b < a);
2344         b.set(0, true);
2345         assert!(a < b);
2346     }
2347
2348     #[test]
2349     fn test_ord() {
2350         let mut a = Bitv::from_elem(5u, false);
2351         let mut b = Bitv::from_elem(5u, false);
2352
2353         assert!(a <= b && a >= b);
2354         a.set(1, true);
2355         assert!(a > b && a >= b);
2356         assert!(b < a && b <= a);
2357         b.set(1, true);
2358         b.set(2, true);
2359         assert!(b > a && b >= a);
2360         assert!(a < b && a <= b);
2361     }
2362
2363
2364     #[test]
2365     fn test_small_bitv_tests() {
2366         let v = Bitv::from_bytes(&[0]);
2367         assert!(!v.all());
2368         assert!(!v.any());
2369         assert!(v.none());
2370
2371         let v = Bitv::from_bytes(&[0b00010100]);
2372         assert!(!v.all());
2373         assert!(v.any());
2374         assert!(!v.none());
2375
2376         let v = Bitv::from_bytes(&[0xFF]);
2377         assert!(v.all());
2378         assert!(v.any());
2379         assert!(!v.none());
2380     }
2381
2382     #[test]
2383     fn test_big_bitv_tests() {
2384         let v = Bitv::from_bytes(&[ // 88 bits
2385             0, 0, 0, 0,
2386             0, 0, 0, 0,
2387             0, 0, 0]);
2388         assert!(!v.all());
2389         assert!(!v.any());
2390         assert!(v.none());
2391
2392         let v = Bitv::from_bytes(&[ // 88 bits
2393             0, 0, 0b00010100, 0,
2394             0, 0, 0, 0b00110100,
2395             0, 0, 0]);
2396         assert!(!v.all());
2397         assert!(v.any());
2398         assert!(!v.none());
2399
2400         let v = Bitv::from_bytes(&[ // 88 bits
2401             0xFF, 0xFF, 0xFF, 0xFF,
2402             0xFF, 0xFF, 0xFF, 0xFF,
2403             0xFF, 0xFF, 0xFF]);
2404         assert!(v.all());
2405         assert!(v.any());
2406         assert!(!v.none());
2407     }
2408
2409     #[test]
2410     fn test_bitv_push_pop() {
2411         let mut s = Bitv::from_elem(5 * u32::BITS - 2, false);
2412         assert_eq!(s.len(), 5 * u32::BITS - 2);
2413         assert_eq!(s[5 * u32::BITS - 3], false);
2414         s.push(true);
2415         s.push(true);
2416         assert_eq!(s[5 * u32::BITS - 2], true);
2417         assert_eq!(s[5 * u32::BITS - 1], true);
2418         // Here the internal vector will need to be extended
2419         s.push(false);
2420         assert_eq!(s[5 * u32::BITS], false);
2421         s.push(false);
2422         assert_eq!(s[5 * u32::BITS + 1], false);
2423         assert_eq!(s.len(), 5 * u32::BITS + 2);
2424         // Pop it all off
2425         assert_eq!(s.pop(), Some(false));
2426         assert_eq!(s.pop(), Some(false));
2427         assert_eq!(s.pop(), Some(true));
2428         assert_eq!(s.pop(), Some(true));
2429         assert_eq!(s.len(), 5 * u32::BITS - 2);
2430     }
2431
2432     #[test]
2433     fn test_bitv_truncate() {
2434         let mut s = Bitv::from_elem(5 * u32::BITS, true);
2435
2436         assert_eq!(s, Bitv::from_elem(5 * u32::BITS, true));
2437         assert_eq!(s.len(), 5 * u32::BITS);
2438         s.truncate(4 * u32::BITS);
2439         assert_eq!(s, Bitv::from_elem(4 * u32::BITS, true));
2440         assert_eq!(s.len(), 4 * u32::BITS);
2441         // Truncating to a size > s.len() should be a noop
2442         s.truncate(5 * u32::BITS);
2443         assert_eq!(s, Bitv::from_elem(4 * u32::BITS, true));
2444         assert_eq!(s.len(), 4 * u32::BITS);
2445         s.truncate(3 * u32::BITS - 10);
2446         assert_eq!(s, Bitv::from_elem(3 * u32::BITS - 10, true));
2447         assert_eq!(s.len(), 3 * u32::BITS - 10);
2448         s.truncate(0);
2449         assert_eq!(s, Bitv::from_elem(0, true));
2450         assert_eq!(s.len(), 0);
2451     }
2452
2453     #[test]
2454     fn test_bitv_reserve() {
2455         let mut s = Bitv::from_elem(5 * u32::BITS, true);
2456         // Check capacity
2457         assert!(s.capacity() >= 5 * u32::BITS);
2458         s.reserve(2 * u32::BITS);
2459         assert!(s.capacity() >= 7 * u32::BITS);
2460         s.reserve(7 * u32::BITS);
2461         assert!(s.capacity() >= 12 * u32::BITS);
2462         s.reserve_exact(7 * u32::BITS);
2463         assert!(s.capacity() >= 12 * u32::BITS);
2464         s.reserve(7 * u32::BITS + 1);
2465         assert!(s.capacity() >= 12 * u32::BITS + 1);
2466         // Check that length hasn't changed
2467         assert_eq!(s.len(), 5 * u32::BITS);
2468         s.push(true);
2469         s.push(false);
2470         s.push(true);
2471         assert_eq!(s[5 * u32::BITS - 1], true);
2472         assert_eq!(s[5 * u32::BITS - 0], true);
2473         assert_eq!(s[5 * u32::BITS + 1], false);
2474         assert_eq!(s[5 * u32::BITS + 2], true);
2475     }
2476
2477     #[test]
2478     fn test_bitv_grow() {
2479         let mut bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
2480         bitv.grow(32, true);
2481         assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2482                                      0xFF, 0xFF, 0xFF, 0xFF]));
2483         bitv.grow(64, false);
2484         assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2485                                      0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
2486         bitv.grow(16, true);
2487         assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2488                                      0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
2489     }
2490
2491     #[test]
2492     fn test_bitv_extend() {
2493         let mut bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2494         let ext = Bitv::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
2495         bitv.extend(ext.iter());
2496         assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111,
2497                                      0b01001001, 0b10010010, 0b10111101]));
2498     }
2499 }
2500
2501
2502
2503
2504 #[cfg(test)]
2505 mod bitv_bench {
2506     use std::prelude::v1::*;
2507     use std::rand;
2508     use std::rand::Rng;
2509     use std::u32;
2510     use test::{Bencher, black_box};
2511
2512     use super::Bitv;
2513
2514     static BENCH_BITS : uint = 1 << 14;
2515
2516     fn rng() -> rand::IsaacRng {
2517         let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
2518         rand::SeedableRng::from_seed(seed)
2519     }
2520
2521     #[bench]
2522     fn bench_uint_small(b: &mut Bencher) {
2523         let mut r = rng();
2524         let mut bitv = 0 as uint;
2525         b.iter(|| {
2526             for _ in range(0u, 100) {
2527                 bitv |= 1 << ((r.next_u32() as uint) % u32::BITS);
2528             }
2529             black_box(&bitv);
2530         });
2531     }
2532
2533     #[bench]
2534     fn bench_bitv_set_big_fixed(b: &mut Bencher) {
2535         let mut r = rng();
2536         let mut bitv = Bitv::from_elem(BENCH_BITS, false);
2537         b.iter(|| {
2538             for _ in range(0u, 100) {
2539                 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
2540             }
2541             black_box(&bitv);
2542         });
2543     }
2544
2545     #[bench]
2546     fn bench_bitv_set_big_variable(b: &mut Bencher) {
2547         let mut r = rng();
2548         let mut bitv = Bitv::from_elem(BENCH_BITS, false);
2549         b.iter(|| {
2550             for _ in range(0u, 100) {
2551                 bitv.set((r.next_u32() as uint) % BENCH_BITS, r.gen());
2552             }
2553             black_box(&bitv);
2554         });
2555     }
2556
2557     #[bench]
2558     fn bench_bitv_set_small(b: &mut Bencher) {
2559         let mut r = rng();
2560         let mut bitv = Bitv::from_elem(u32::BITS, false);
2561         b.iter(|| {
2562             for _ in range(0u, 100) {
2563                 bitv.set((r.next_u32() as uint) % u32::BITS, true);
2564             }
2565             black_box(&bitv);
2566         });
2567     }
2568
2569     #[bench]
2570     fn bench_bitv_big_union(b: &mut Bencher) {
2571         let mut b1 = Bitv::from_elem(BENCH_BITS, false);
2572         let b2 = Bitv::from_elem(BENCH_BITS, false);
2573         b.iter(|| {
2574             b1.union(&b2)
2575         })
2576     }
2577
2578     #[bench]
2579     fn bench_bitv_small_iter(b: &mut Bencher) {
2580         let bitv = Bitv::from_elem(u32::BITS, false);
2581         b.iter(|| {
2582             let mut sum = 0u;
2583             for _ in range(0u, 10) {
2584                 for pres in bitv.iter() {
2585                     sum += pres as uint;
2586                 }
2587             }
2588             sum
2589         })
2590     }
2591
2592     #[bench]
2593     fn bench_bitv_big_iter(b: &mut Bencher) {
2594         let bitv = Bitv::from_elem(BENCH_BITS, false);
2595         b.iter(|| {
2596             let mut sum = 0u;
2597             for pres in bitv.iter() {
2598                 sum += pres as uint;
2599             }
2600             sum
2601         })
2602     }
2603 }
2604
2605
2606
2607
2608
2609
2610
2611 #[cfg(test)]
2612 mod bitv_set_test {
2613     use prelude::*;
2614     use std::iter::range_step;
2615
2616     use super::{Bitv, BitvSet};
2617
2618     #[test]
2619     fn test_bitv_set_show() {
2620         let mut s = BitvSet::new();
2621         s.insert(1);
2622         s.insert(10);
2623         s.insert(50);
2624         s.insert(2);
2625         assert_eq!("BitvSet {1u, 2u, 10u, 50u}", format!("{:?}", s));
2626     }
2627
2628     #[test]
2629     fn test_bitv_set_from_uints() {
2630         let uints = vec![0, 2, 2, 3];
2631         let a: BitvSet = uints.into_iter().collect();
2632         let mut b = BitvSet::new();
2633         b.insert(0);
2634         b.insert(2);
2635         b.insert(3);
2636         assert_eq!(a, b);
2637     }
2638
2639     #[test]
2640     fn test_bitv_set_iterator() {
2641         let uints = vec![0, 2, 2, 3];
2642         let bitv: BitvSet = uints.into_iter().collect();
2643
2644         let idxs: Vec<uint> = bitv.iter().collect();
2645         assert_eq!(idxs, vec![0, 2, 3]);
2646
2647         let long: BitvSet = range(0u, 10000).filter(|&n| n % 2 == 0).collect();
2648         let real = range_step(0, 10000, 2).collect::<Vec<uint>>();
2649
2650         let idxs: Vec<uint> = long.iter().collect();
2651         assert_eq!(idxs, real);
2652     }
2653
2654     #[test]
2655     fn test_bitv_set_frombitv_init() {
2656         let bools = [true, false];
2657         let lengths = [10, 64, 100];
2658         for &b in bools.iter() {
2659             for &l in lengths.iter() {
2660                 let bitset = BitvSet::from_bitv(Bitv::from_elem(l, b));
2661                 assert_eq!(bitset.contains(&1u), b);
2662                 assert_eq!(bitset.contains(&(l-1u)), b);
2663                 assert!(!bitset.contains(&l));
2664             }
2665         }
2666     }
2667
2668     #[test]
2669     fn test_bitv_masking() {
2670         let b = Bitv::from_elem(140, true);
2671         let mut bs = BitvSet::from_bitv(b);
2672         assert!(bs.contains(&139));
2673         assert!(!bs.contains(&140));
2674         assert!(bs.insert(150));
2675         assert!(!bs.contains(&140));
2676         assert!(!bs.contains(&149));
2677         assert!(bs.contains(&150));
2678         assert!(!bs.contains(&151));
2679     }
2680
2681     #[test]
2682     fn test_bitv_set_basic() {
2683         let mut b = BitvSet::new();
2684         assert!(b.insert(3));
2685         assert!(!b.insert(3));
2686         assert!(b.contains(&3));
2687         assert!(b.insert(4));
2688         assert!(!b.insert(4));
2689         assert!(b.contains(&3));
2690         assert!(b.insert(400));
2691         assert!(!b.insert(400));
2692         assert!(b.contains(&400));
2693         assert_eq!(b.len(), 3);
2694     }
2695
2696     #[test]
2697     fn test_bitv_set_intersection() {
2698         let mut a = BitvSet::new();
2699         let mut b = BitvSet::new();
2700
2701         assert!(a.insert(11));
2702         assert!(a.insert(1));
2703         assert!(a.insert(3));
2704         assert!(a.insert(77));
2705         assert!(a.insert(103));
2706         assert!(a.insert(5));
2707
2708         assert!(b.insert(2));
2709         assert!(b.insert(11));
2710         assert!(b.insert(77));
2711         assert!(b.insert(5));
2712         assert!(b.insert(3));
2713
2714         let expected = [3, 5, 11, 77];
2715         let actual = a.intersection(&b).collect::<Vec<uint>>();
2716         assert_eq!(actual, expected);
2717     }
2718
2719     #[test]
2720     fn test_bitv_set_difference() {
2721         let mut a = BitvSet::new();
2722         let mut b = BitvSet::new();
2723
2724         assert!(a.insert(1));
2725         assert!(a.insert(3));
2726         assert!(a.insert(5));
2727         assert!(a.insert(200));
2728         assert!(a.insert(500));
2729
2730         assert!(b.insert(3));
2731         assert!(b.insert(200));
2732
2733         let expected = [1, 5, 500];
2734         let actual = a.difference(&b).collect::<Vec<uint>>();
2735         assert_eq!(actual, expected);
2736     }
2737
2738     #[test]
2739     fn test_bitv_set_symmetric_difference() {
2740         let mut a = BitvSet::new();
2741         let mut b = BitvSet::new();
2742
2743         assert!(a.insert(1));
2744         assert!(a.insert(3));
2745         assert!(a.insert(5));
2746         assert!(a.insert(9));
2747         assert!(a.insert(11));
2748
2749         assert!(b.insert(3));
2750         assert!(b.insert(9));
2751         assert!(b.insert(14));
2752         assert!(b.insert(220));
2753
2754         let expected = [1, 5, 11, 14, 220];
2755         let actual = a.symmetric_difference(&b).collect::<Vec<uint>>();
2756         assert_eq!(actual, expected);
2757     }
2758
2759     #[test]
2760     fn test_bitv_set_union() {
2761         let mut a = BitvSet::new();
2762         let mut b = BitvSet::new();
2763         assert!(a.insert(1));
2764         assert!(a.insert(3));
2765         assert!(a.insert(5));
2766         assert!(a.insert(9));
2767         assert!(a.insert(11));
2768         assert!(a.insert(160));
2769         assert!(a.insert(19));
2770         assert!(a.insert(24));
2771         assert!(a.insert(200));
2772
2773         assert!(b.insert(1));
2774         assert!(b.insert(5));
2775         assert!(b.insert(9));
2776         assert!(b.insert(13));
2777         assert!(b.insert(19));
2778
2779         let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
2780         let actual = a.union(&b).collect::<Vec<uint>>();
2781         assert_eq!(actual, expected);
2782     }
2783
2784     #[test]
2785     fn test_bitv_set_subset() {
2786         let mut set1 = BitvSet::new();
2787         let mut set2 = BitvSet::new();
2788
2789         assert!(set1.is_subset(&set2)); //  {}  {}
2790         set2.insert(100);
2791         assert!(set1.is_subset(&set2)); //  {}  { 1 }
2792         set2.insert(200);
2793         assert!(set1.is_subset(&set2)); //  {}  { 1, 2 }
2794         set1.insert(200);
2795         assert!(set1.is_subset(&set2)); //  { 2 }  { 1, 2 }
2796         set1.insert(300);
2797         assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 1, 2 }
2798         set2.insert(300);
2799         assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3 }
2800         set2.insert(400);
2801         assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3, 4 }
2802         set2.remove(&100);
2803         assert!(set1.is_subset(&set2)); // { 2, 3 }  { 2, 3, 4 }
2804         set2.remove(&300);
2805         assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 2, 4 }
2806         set1.remove(&300);
2807         assert!(set1.is_subset(&set2)); // { 2 }  { 2, 4 }
2808     }
2809
2810     #[test]
2811     fn test_bitv_set_is_disjoint() {
2812         let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2813         let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01000000]));
2814         let c = BitvSet::new();
2815         let d = BitvSet::from_bitv(Bitv::from_bytes(&[0b00110000]));
2816
2817         assert!(!a.is_disjoint(&d));
2818         assert!(!d.is_disjoint(&a));
2819
2820         assert!(a.is_disjoint(&b));
2821         assert!(a.is_disjoint(&c));
2822         assert!(b.is_disjoint(&a));
2823         assert!(b.is_disjoint(&c));
2824         assert!(c.is_disjoint(&a));
2825         assert!(c.is_disjoint(&b));
2826     }
2827
2828     #[test]
2829     fn test_bitv_set_union_with() {
2830         //a should grow to include larger elements
2831         let mut a = BitvSet::new();
2832         a.insert(0);
2833         let mut b = BitvSet::new();
2834         b.insert(5);
2835         let expected = BitvSet::from_bitv(Bitv::from_bytes(&[0b10000100]));
2836         a.union_with(&b);
2837         assert_eq!(a, expected);
2838
2839         // Standard
2840         let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2841         let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
2842         let c = a.clone();
2843         a.union_with(&b);
2844         b.union_with(&c);
2845         assert_eq!(a.len(), 4);
2846         assert_eq!(b.len(), 4);
2847     }
2848
2849     #[test]
2850     fn test_bitv_set_intersect_with() {
2851         // Explicitly 0'ed bits
2852         let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2853         let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
2854         let c = a.clone();
2855         a.intersect_with(&b);
2856         b.intersect_with(&c);
2857         assert!(a.is_empty());
2858         assert!(b.is_empty());
2859
2860         // Uninitialized bits should behave like 0's
2861         let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2862         let mut b = BitvSet::new();
2863         let c = a.clone();
2864         a.intersect_with(&b);
2865         b.intersect_with(&c);
2866         assert!(a.is_empty());
2867         assert!(b.is_empty());
2868
2869         // Standard
2870         let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2871         let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
2872         let c = a.clone();
2873         a.intersect_with(&b);
2874         b.intersect_with(&c);
2875         assert_eq!(a.len(), 2);
2876         assert_eq!(b.len(), 2);
2877     }
2878
2879     #[test]
2880     fn test_bitv_set_difference_with() {
2881         // Explicitly 0'ed bits
2882         let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
2883         let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2884         a.difference_with(&b);
2885         assert!(a.is_empty());
2886
2887         // Uninitialized bits should behave like 0's
2888         let mut a = BitvSet::new();
2889         let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b11111111]));
2890         a.difference_with(&b);
2891         assert!(a.is_empty());
2892
2893         // Standard
2894         let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2895         let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
2896         let c = a.clone();
2897         a.difference_with(&b);
2898         b.difference_with(&c);
2899         assert_eq!(a.len(), 1);
2900         assert_eq!(b.len(), 1);
2901     }
2902
2903     #[test]
2904     fn test_bitv_set_symmetric_difference_with() {
2905         //a should grow to include larger elements
2906         let mut a = BitvSet::new();
2907         a.insert(0);
2908         a.insert(1);
2909         let mut b = BitvSet::new();
2910         b.insert(1);
2911         b.insert(5);
2912         let expected = BitvSet::from_bitv(Bitv::from_bytes(&[0b10000100]));
2913         a.symmetric_difference_with(&b);
2914         assert_eq!(a, expected);
2915
2916         let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2917         let b = BitvSet::new();
2918         let c = a.clone();
2919         a.symmetric_difference_with(&b);
2920         assert_eq!(a, c);
2921
2922         // Standard
2923         let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b11100010]));
2924         let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101010]));
2925         let c = a.clone();
2926         a.symmetric_difference_with(&b);
2927         b.symmetric_difference_with(&c);
2928         assert_eq!(a.len(), 2);
2929         assert_eq!(b.len(), 2);
2930     }
2931
2932     #[test]
2933     fn test_bitv_set_eq() {
2934         let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2935         let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
2936         let c = BitvSet::new();
2937
2938         assert!(a == a);
2939         assert!(a != b);
2940         assert!(a != c);
2941         assert!(b == b);
2942         assert!(b == c);
2943         assert!(c == c);
2944     }
2945
2946     #[test]
2947     fn test_bitv_set_cmp() {
2948         let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2949         let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
2950         let c = BitvSet::new();
2951
2952         assert_eq!(a.cmp(&b), Greater);
2953         assert_eq!(a.cmp(&c), Greater);
2954         assert_eq!(b.cmp(&a), Less);
2955         assert_eq!(b.cmp(&c), Equal);
2956         assert_eq!(c.cmp(&a), Less);
2957         assert_eq!(c.cmp(&b), Equal);
2958     }
2959
2960     #[test]
2961     fn test_bitv_remove() {
2962         let mut a = BitvSet::new();
2963
2964         assert!(a.insert(1));
2965         assert!(a.remove(&1));
2966
2967         assert!(a.insert(100));
2968         assert!(a.remove(&100));
2969
2970         assert!(a.insert(1000));
2971         assert!(a.remove(&1000));
2972         a.shrink_to_fit();
2973     }
2974
2975     #[test]
2976     fn test_bitv_clone() {
2977         let mut a = BitvSet::new();
2978
2979         assert!(a.insert(1));
2980         assert!(a.insert(100));
2981         assert!(a.insert(1000));
2982
2983         let mut b = a.clone();
2984
2985         assert!(a == b);
2986
2987         assert!(b.remove(&1));
2988         assert!(a.contains(&1));
2989
2990         assert!(a.remove(&1000));
2991         assert!(b.contains(&1000));
2992     }
2993 }
2994
2995
2996
2997
2998
2999 #[cfg(test)]
3000 mod bitv_set_bench {
3001     use std::prelude::v1::*;
3002     use std::rand;
3003     use std::rand::Rng;
3004     use std::u32;
3005     use test::{Bencher, black_box};
3006
3007     use super::{Bitv, BitvSet};
3008
3009     static BENCH_BITS : uint = 1 << 14;
3010
3011     fn rng() -> rand::IsaacRng {
3012         let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
3013         rand::SeedableRng::from_seed(seed)
3014     }
3015
3016     #[bench]
3017     fn bench_bitvset_small(b: &mut Bencher) {
3018         let mut r = rng();
3019         let mut bitv = BitvSet::new();
3020         b.iter(|| {
3021             for _ in range(0u, 100) {
3022                 bitv.insert((r.next_u32() as uint) % u32::BITS);
3023             }
3024             black_box(&bitv);
3025         });
3026     }
3027
3028     #[bench]
3029     fn bench_bitvset_big(b: &mut Bencher) {
3030         let mut r = rng();
3031         let mut bitv = BitvSet::new();
3032         b.iter(|| {
3033             for _ in range(0u, 100) {
3034                 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
3035             }
3036             black_box(&bitv);
3037         });
3038     }
3039
3040     #[bench]
3041     fn bench_bitvset_iter(b: &mut Bencher) {
3042         let bitv = BitvSet::from_bitv(Bitv::from_fn(BENCH_BITS,
3043                                               |idx| {idx % 3 == 0}));
3044         b.iter(|| {
3045             let mut sum = 0u;
3046             for idx in bitv.iter() {
3047                 sum += idx as uint;
3048             }
3049             sum
3050         })
3051     }
3052 }