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.
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.
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.
17 // FIXME(tbu-): `Bitv`'s methods shouldn't be `union`, `intersection`, but
18 // rather `or` and `and`.
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`.
31 //! Collections implemented with bit vectors.
35 //! This is a simple example of the [Sieve of Eratosthenes][sieve]
36 //! which calculates prime numbers up to a given limit.
38 //! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
41 //! use std::collections::{BitvSet, Bitv};
42 //! use std::num::Float;
45 //! let max_prime = 10000;
47 //! // Store the primes as a BitvSet
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);
53 //! // Neither 0 nor 1 are prime
57 //! for i in iter::range_inclusive(2, (max_prime as f64).sqrt() as uint) {
58 //! // if i is a prime
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) }
65 //! BitvSet::from_bitv(bv)
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) {
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);
85 use core::cmp::Ordering;
87 use core::default::Default;
90 use core::iter::RandomAccessIterator;
91 use core::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat, Cloned};
92 use core::iter::{self, FromIterator};
96 use core::{u8, u32, uint};
97 use bitv_set; //so meta
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>>>>>;
105 fn reverse_bits(byte: u8) -> u8 {
107 for i in range(0, u8::BITS) {
108 result |= ((byte >> i) & 1) << (u8::BITS - 1 - i);
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();
119 // have to uselessly pretend to pad the longer one for type matching
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)))
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)))
129 static TRUE: bool = true;
130 static FALSE: bool = false;
132 /// The bitvector type.
137 /// use collections::Bitv;
139 /// let mut bv = Bitv::from_elem(10, false);
141 /// // insert all primes less than 10
146 /// println!("{}", bv.to_string());
147 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
149 /// // flip all values in bitvector, producing non-primes less than 10
151 /// println!("{}", bv.to_string());
152 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
154 /// // reset bitvector to empty
156 /// println!("{}", bv.to_string());
157 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
161 /// Internal representation of the bit vector
163 /// The number of valid bits in the internal representation
167 // NOTE(stage0): remove impl after a snapshot
169 // FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
170 impl Index<uint,bool> for Bitv {
172 fn index(&self, i: &uint) -> &bool {
173 if self.get(*i).expect("index out of bounds") {
181 #[cfg(not(stage0))] // NOTE(stage0): remove cfg after a snapshot
182 // FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
183 impl Index<uint> for Bitv {
187 fn index(&self, i: &uint) -> &bool {
188 if self.get(*i).expect("index out of bounds") {
196 /// Computes how many blocks are needed to store that many bits
197 fn blocks_for_bits(bits: uint) -> uint {
198 // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
199 // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
200 // one too many. So we need to check if that's the case. We can do that by computing if
201 // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
202 // superior modulo operator on a power of two to this.
204 // Note that we can technically avoid this branch with the expression
205 // `(nbits + u32::BITS - 1) / 32::BITS`, but if nbits is almost uint::MAX this will overflow.
206 if bits % u32::BITS == 0 {
213 /// Computes the bitmask for the final word of the vector
214 fn mask_for_bits(bits: uint) -> u32 {
215 // Note especially that a perfect multiple of u32::BITS should mask all 1s.
216 !0u32 >> (u32::BITS - bits % u32::BITS) % u32::BITS
220 /// Applies the given operation to the blocks of self and other, and sets
221 /// self to be the result. This relies on the caller not to corrupt the
224 fn process<F>(&mut self, other: &Bitv, mut op: F) -> bool where F: FnMut(u32, u32) -> u32 {
225 assert_eq!(self.len(), other.len());
226 // This could theoretically be a `debug_assert!`.
227 assert_eq!(self.storage.len(), other.storage.len());
228 let mut changed = false;
229 for (a, b) in self.blocks_mut().zip(other.blocks()) {
239 /// Iterator over mutable refs to the underlying blocks of data.
240 fn blocks_mut(&mut self) -> MutBlocks {
242 self.storage.iter_mut()
245 /// Iterator over the underlying blocks of data
246 fn blocks(&self) -> Blocks {
248 self.storage.iter().cloned()
251 /// An operation might screw up the unused bits in the last block of the
252 /// `Bitv`. As per (3), it's assumed to be all 0s. This method fixes it up.
253 fn fix_last_block(&mut self) {
254 let extra_bits = self.len() % u32::BITS;
256 let mask = (1 << extra_bits) - 1;
257 let storage_len = self.storage.len();
258 self.storage[storage_len - 1] &= mask;
262 /// Creates an empty `Bitv`.
267 /// use std::collections::Bitv;
268 /// let mut bv = Bitv::new();
271 pub fn new() -> Bitv {
272 Bitv { storage: Vec::new(), nbits: 0 }
275 /// Creates a `Bitv` that holds `nbits` elements, setting each element
281 /// use std::collections::Bitv;
283 /// let mut bv = Bitv::from_elem(10u, false);
284 /// assert_eq!(bv.len(), 10u);
285 /// for x in bv.iter() {
286 /// assert_eq!(x, false);
289 pub fn from_elem(nbits: uint, bit: bool) -> Bitv {
290 let nblocks = blocks_for_bits(nbits);
291 let mut bitv = Bitv {
292 storage: repeat(if bit { !0u32 } else { 0u32 }).take(nblocks).collect(),
295 bitv.fix_last_block();
299 /// Constructs a new, empty `Bitv` with the specified capacity.
301 /// The bitvector will be able to hold at least `capacity` bits without
302 /// reallocating. If `capacity` is 0, it will not allocate.
304 /// It is important to note that this function does not specify the
305 /// *length* of the returned bitvector, but only the *capacity*.
307 pub fn with_capacity(nbits: uint) -> Bitv {
309 storage: Vec::with_capacity(blocks_for_bits(nbits)),
314 /// Transforms a byte-vector into a `Bitv`. Each byte becomes eight bits,
315 /// with the most significant bits of each byte coming first. Each
316 /// bit becomes `true` if equal to 1 or `false` if equal to 0.
321 /// use std::collections::Bitv;
323 /// let bv = Bitv::from_bytes(&[0b10100000, 0b00010010]);
324 /// assert!(bv.eq_vec(&[true, false, true, false,
325 /// false, false, false, false,
326 /// false, false, false, true,
327 /// false, false, true, false]));
329 pub fn from_bytes(bytes: &[u8]) -> Bitv {
330 let len = bytes.len().checked_mul(u8::BITS).expect("capacity overflow");
331 let mut bitv = Bitv::with_capacity(len);
332 let complete_words = bytes.len() / 4;
333 let extra_bytes = bytes.len() % 4;
337 for i in range(0, complete_words) {
339 ((reverse_bits(bytes[i * 4 + 0]) as u32) << 0) |
340 ((reverse_bits(bytes[i * 4 + 1]) as u32) << 8) |
341 ((reverse_bits(bytes[i * 4 + 2]) as u32) << 16) |
342 ((reverse_bits(bytes[i * 4 + 3]) as u32) << 24)
347 let mut last_word = 0u32;
348 for (i, &byte) in bytes[complete_words*4..].iter().enumerate() {
349 last_word |= (reverse_bits(byte) as u32) << (i * 8);
351 bitv.storage.push(last_word);
357 /// Creates a `Bitv` of the specified length where the value at each index
363 /// use std::collections::Bitv;
365 /// let bv = Bitv::from_fn(5, |i| { i % 2 == 0 });
366 /// assert!(bv.eq_vec(&[true, false, true, false, true]));
368 pub fn from_fn<F>(len: uint, mut f: F) -> Bitv where F: FnMut(uint) -> bool {
369 let mut bitv = Bitv::from_elem(len, false);
370 for i in range(0u, len) {
376 /// Retrieves the value at index `i`, or `None` if the index is out of bounds.
381 /// use std::collections::Bitv;
383 /// let bv = Bitv::from_bytes(&[0b01100000]);
384 /// assert_eq!(bv.get(0), Some(false));
385 /// assert_eq!(bv.get(1), Some(true));
386 /// assert_eq!(bv.get(100), None);
388 /// // Can also use array indexing
389 /// assert_eq!(bv[1], true);
393 pub fn get(&self, i: uint) -> Option<bool> {
397 let w = i / u32::BITS;
398 let b = i % u32::BITS;
399 self.storage.get(w).map(|&block|
400 (block & (1 << b)) != 0
404 /// Sets the value of a bit at an index `i`.
408 /// Panics if `i` is out of bounds.
413 /// use std::collections::Bitv;
415 /// let mut bv = Bitv::from_elem(5, false);
417 /// assert_eq!(bv[3], true);
420 #[unstable = "panic semantics are likely to change in the future"]
421 pub fn set(&mut self, i: uint, x: bool) {
422 assert!(i < self.nbits);
423 let w = i / u32::BITS;
424 let b = i % u32::BITS;
426 let val = if x { self.storage[w] | flag }
427 else { self.storage[w] & !flag };
428 self.storage[w] = val;
431 /// Sets all bits to 1.
436 /// use std::collections::Bitv;
438 /// let before = 0b01100000;
439 /// let after = 0b11111111;
441 /// let mut bv = Bitv::from_bytes(&[before]);
443 /// assert_eq!(bv, Bitv::from_bytes(&[after]));
446 pub fn set_all(&mut self) {
447 for w in self.storage.iter_mut() { *w = !0u32; }
448 self.fix_last_block();
456 /// use std::collections::Bitv;
458 /// let before = 0b01100000;
459 /// let after = 0b10011111;
461 /// let mut bv = Bitv::from_bytes(&[before]);
463 /// assert_eq!(bv, Bitv::from_bytes(&[after]));
466 pub fn negate(&mut self) {
467 for w in self.storage.iter_mut() { *w = !*w; }
468 self.fix_last_block();
471 /// Calculates the union of two bitvectors. This acts like the bitwise `or`
474 /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
475 /// the same length. Returns `true` if `self` changed.
479 /// Panics if the bitvectors are of different lengths.
484 /// use std::collections::Bitv;
486 /// let a = 0b01100100;
487 /// let b = 0b01011010;
488 /// let res = 0b01111110;
490 /// let mut a = Bitv::from_bytes(&[a]);
491 /// let b = Bitv::from_bytes(&[b]);
493 /// assert!(a.union(&b));
494 /// assert_eq!(a, Bitv::from_bytes(&[res]));
497 pub fn union(&mut self, other: &Bitv) -> bool {
498 self.process(other, |w1, w2| w1 | w2)
501 /// Calculates the intersection of two bitvectors. This acts like the
502 /// bitwise `and` function.
504 /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
505 /// must be the same length. Returns `true` if `self` changed.
509 /// Panics if the bitvectors are of different lengths.
514 /// use std::collections::Bitv;
516 /// let a = 0b01100100;
517 /// let b = 0b01011010;
518 /// let res = 0b01000000;
520 /// let mut a = Bitv::from_bytes(&[a]);
521 /// let b = Bitv::from_bytes(&[b]);
523 /// assert!(a.intersect(&b));
524 /// assert_eq!(a, Bitv::from_bytes(&[res]));
527 pub fn intersect(&mut self, other: &Bitv) -> bool {
528 self.process(other, |w1, w2| w1 & w2)
531 /// Calculates the difference between two bitvectors.
533 /// Sets each element of `self` to the value of that element minus the
534 /// element of `other` at the same index. Both bitvectors must be the same
535 /// length. Returns `true` if `self` changed.
539 /// Panics if the bitvectors are of different length.
544 /// use std::collections::Bitv;
546 /// let a = 0b01100100;
547 /// let b = 0b01011010;
548 /// let a_b = 0b00100100; // a - b
549 /// let b_a = 0b00011010; // b - a
551 /// let mut bva = Bitv::from_bytes(&[a]);
552 /// let bvb = Bitv::from_bytes(&[b]);
554 /// assert!(bva.difference(&bvb));
555 /// assert_eq!(bva, Bitv::from_bytes(&[a_b]));
557 /// let bva = Bitv::from_bytes(&[a]);
558 /// let mut bvb = Bitv::from_bytes(&[b]);
560 /// assert!(bvb.difference(&bva));
561 /// assert_eq!(bvb, Bitv::from_bytes(&[b_a]));
564 pub fn difference(&mut self, other: &Bitv) -> bool {
565 self.process(other, |w1, w2| w1 & !w2)
568 /// Returns `true` if all bits are 1.
573 /// use std::collections::Bitv;
575 /// let mut bv = Bitv::from_elem(5, true);
576 /// assert_eq!(bv.all(), true);
578 /// bv.set(1, false);
579 /// assert_eq!(bv.all(), false);
581 pub fn all(&self) -> bool {
582 let mut last_word = !0u32;
583 // Check that every block but the last is all-ones...
584 self.blocks().all(|elem| {
588 // and then check the last one has enough ones
589 }) && (last_word == mask_for_bits(self.nbits))
592 /// Returns an iterator over the elements of the vector in order.
597 /// use std::collections::Bitv;
599 /// let bv = Bitv::from_bytes(&[0b01110100, 0b10010010]);
600 /// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
604 pub fn iter(&self) -> Iter {
605 Iter { bitv: self, next_idx: 0, end_idx: self.nbits }
608 /// Returns `true` if all bits are 0.
613 /// use std::collections::Bitv;
615 /// let mut bv = Bitv::from_elem(10, false);
616 /// assert_eq!(bv.none(), true);
619 /// assert_eq!(bv.none(), false);
621 pub fn none(&self) -> bool {
622 self.blocks().all(|w| w == 0)
625 /// Returns `true` if any bit is 1.
630 /// use std::collections::Bitv;
632 /// let mut bv = Bitv::from_elem(10, false);
633 /// assert_eq!(bv.any(), false);
636 /// assert_eq!(bv.any(), true);
639 pub fn any(&self) -> bool {
643 /// Organises the bits into bytes, such that the first bit in the
644 /// `Bitv` becomes the high-order bit of the first byte. If the
645 /// size of the `Bitv` is not a multiple of eight then trailing bits
646 /// will be filled-in with `false`.
651 /// use std::collections::Bitv;
653 /// let mut bv = Bitv::from_elem(3, true);
654 /// bv.set(1, false);
656 /// assert_eq!(bv.to_bytes(), vec!(0b10100000));
658 /// let mut bv = Bitv::from_elem(9, false);
662 /// assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
664 pub fn to_bytes(&self) -> Vec<u8> {
665 fn bit(bitv: &Bitv, byte: uint, bit: uint) -> u8 {
666 let offset = byte * 8 + bit;
667 if offset >= bitv.nbits {
670 (bitv[offset] as u8) << (7 - bit)
674 let len = self.nbits/8 +
675 if self.nbits % 8 == 0 { 0 } else { 1 };
676 range(0, len).map(|i|
688 /// Compares a `Bitv` to a slice of `bool`s.
689 /// Both the `Bitv` and slice must have the same length.
693 /// Panics if the `Bitv` and slice are of different length.
698 /// use std::collections::Bitv;
700 /// let bv = Bitv::from_bytes(&[0b10100000]);
702 /// assert!(bv.eq_vec(&[true, false, true, false,
703 /// false, false, false, false]));
705 pub fn eq_vec(&self, v: &[bool]) -> bool {
706 assert_eq!(self.nbits, v.len());
707 iter::order::eq(self.iter(), v.iter().cloned())
710 /// Shortens a `Bitv`, dropping excess elements.
712 /// If `len` is greater than the vector's current length, this has no
718 /// use std::collections::Bitv;
720 /// let mut bv = Bitv::from_bytes(&[0b01001011]);
722 /// assert!(bv.eq_vec(&[false, true]));
725 pub fn truncate(&mut self, len: uint) {
726 if len < self.len() {
729 self.storage.truncate(blocks_for_bits(len));
730 self.fix_last_block();
734 /// Reserves capacity for at least `additional` more bits to be inserted in the given
735 /// `Bitv`. The collection may reserve more space to avoid frequent reallocations.
739 /// Panics if the new capacity overflows `uint`.
744 /// use std::collections::Bitv;
746 /// let mut bv = Bitv::from_elem(3, false);
748 /// assert_eq!(bv.len(), 3);
749 /// assert!(bv.capacity() >= 13);
752 pub fn reserve(&mut self, additional: uint) {
753 let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
754 let storage_len = self.storage.len();
755 if desired_cap > self.capacity() {
756 self.storage.reserve(blocks_for_bits(desired_cap) - storage_len);
760 /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the
761 /// given `Bitv`. Does nothing if the capacity is already sufficient.
763 /// Note that the allocator may give the collection more space than it requests. Therefore
764 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
765 /// insertions are expected.
769 /// Panics if the new capacity overflows `uint`.
774 /// use std::collections::Bitv;
776 /// let mut bv = Bitv::from_elem(3, false);
778 /// assert_eq!(bv.len(), 3);
779 /// assert!(bv.capacity() >= 13);
782 pub fn reserve_exact(&mut self, additional: uint) {
783 let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
784 let storage_len = self.storage.len();
785 if desired_cap > self.capacity() {
786 self.storage.reserve_exact(blocks_for_bits(desired_cap) - storage_len);
790 /// Returns the capacity in bits for this bit vector. Inserting any
791 /// element less than this amount will not trigger a resizing.
796 /// use std::collections::Bitv;
798 /// let mut bv = Bitv::new();
800 /// assert!(bv.capacity() >= 10);
804 pub fn capacity(&self) -> uint {
805 self.storage.capacity().checked_mul(u32::BITS).unwrap_or(uint::MAX)
808 /// Grows the `Bitv` in-place, adding `n` copies of `value` to the `Bitv`.
812 /// Panics if the new len overflows a `uint`.
817 /// use std::collections::Bitv;
819 /// let mut bv = Bitv::from_bytes(&[0b01001011]);
820 /// bv.grow(2, true);
821 /// assert_eq!(bv.len(), 10);
822 /// assert_eq!(bv.to_bytes(), vec!(0b01001011, 0b11000000));
824 pub fn grow(&mut self, n: uint, value: bool) {
825 // Note: we just bulk set all the bits in the last word in this fn in multiple places
826 // which is technically wrong if not all of these bits are to be used. However, at the end
827 // of this fn we call `fix_last_block` at the end of this fn, which should fix this.
829 let new_nbits = self.nbits.checked_add(n).expect("capacity overflow");
830 let new_nblocks = blocks_for_bits(new_nbits);
831 let full_value = if value { !0 } else { 0 };
833 // Correct the old tail word, setting or clearing formerly unused bits
834 let old_last_word = blocks_for_bits(self.nbits) - 1;
835 if self.nbits % u32::BITS > 0 {
836 let mask = mask_for_bits(self.nbits);
838 self.storage[old_last_word] |= !mask;
840 // Extra bits are already zero by invariant.
844 // Fill in words after the old tail word
845 let stop_idx = cmp::min(self.storage.len(), new_nblocks);
846 for idx in range(old_last_word + 1, stop_idx) {
847 self.storage[idx] = full_value;
850 // Allocate new words, if needed
851 if new_nblocks > self.storage.len() {
852 let to_add = new_nblocks - self.storage.len();
853 self.storage.extend(repeat(full_value).take(to_add));
856 // Adjust internal bit count
857 self.nbits = new_nbits;
859 self.fix_last_block();
862 /// Removes the last bit from the Bitv, and returns it. Returns None if the Bitv is empty.
867 /// use std::collections::Bitv;
869 /// let mut bv = Bitv::from_bytes(&[0b01001001]);
870 /// assert_eq!(bv.pop(), Some(true));
871 /// assert_eq!(bv.pop(), Some(false));
872 /// assert_eq!(bv.len(), 6);
875 pub fn pop(&mut self) -> Option<bool> {
879 let i = self.nbits - 1;
884 if self.nbits % u32::BITS == 0 {
892 /// Pushes a `bool` onto the end.
897 /// use std::collections::Bitv;
899 /// let mut bv = Bitv::new();
902 /// assert!(bv.eq_vec(&[true, false]));
905 pub fn push(&mut self, elem: bool) {
906 if self.nbits % u32::BITS == 0 {
907 self.storage.push(0);
909 let insert_pos = self.nbits;
910 self.nbits = self.nbits.checked_add(1).expect("Capacity overflow");
911 self.set(insert_pos, elem);
914 /// Return the total number of bits in this vector
917 pub fn len(&self) -> uint { self.nbits }
919 /// Returns true if there are no bits in this vector
922 pub fn is_empty(&self) -> bool { self.len() == 0 }
924 /// Clears all bits in this vector.
927 pub fn clear(&mut self) {
928 for w in self.storage.iter_mut() { *w = 0u32; }
933 impl Default for Bitv {
935 fn default() -> Bitv { Bitv::new() }
939 impl FromIterator<bool> for Bitv {
940 fn from_iter<I:Iterator<Item=bool>>(iterator: I) -> Bitv {
941 let mut ret = Bitv::new();
942 ret.extend(iterator);
948 impl Extend<bool> for Bitv {
950 fn extend<I: Iterator<Item=bool>>(&mut self, mut iterator: I) {
951 let (min, _) = iterator.size_hint();
953 for element in iterator {
960 impl Clone for Bitv {
962 fn clone(&self) -> Bitv {
963 Bitv { storage: self.storage.clone(), nbits: self.nbits }
967 fn clone_from(&mut self, source: &Bitv) {
968 self.nbits = source.nbits;
969 self.storage.clone_from(&source.storage);
974 impl PartialOrd for Bitv {
976 fn partial_cmp(&self, other: &Bitv) -> Option<Ordering> {
977 iter::order::partial_cmp(self.iter(), other.iter())
984 fn cmp(&self, other: &Bitv) -> Ordering {
985 iter::order::cmp(self.iter(), other.iter())
990 impl fmt::Show for Bitv {
991 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
992 for bit in self.iter() {
993 try!(write!(fmt, "{}", if bit { 1u32 } else { 0u32 }));
1000 impl<S: hash::Writer> hash::Hash<S> for Bitv {
1001 fn hash(&self, state: &mut S) {
1002 self.nbits.hash(state);
1003 for elem in self.blocks() {
1010 impl cmp::PartialEq for Bitv {
1012 fn eq(&self, other: &Bitv) -> bool {
1013 if self.nbits != other.nbits {
1016 self.blocks().zip(other.blocks()).all(|(w1, w2)| w1 == w2)
1021 impl cmp::Eq for Bitv {}
1023 /// An iterator for `Bitv`.
1026 pub struct Iter<'a> {
1033 impl<'a> Iterator for Iter<'a> {
1037 fn next(&mut self) -> Option<bool> {
1038 if self.next_idx != self.end_idx {
1039 let idx = self.next_idx;
1041 Some(self.bitv[idx])
1047 fn size_hint(&self) -> (uint, Option<uint>) {
1048 let rem = self.end_idx - self.next_idx;
1054 impl<'a> DoubleEndedIterator for Iter<'a> {
1056 fn next_back(&mut self) -> Option<bool> {
1057 if self.next_idx != self.end_idx {
1059 Some(self.bitv[self.end_idx])
1067 impl<'a> ExactSizeIterator for Iter<'a> {}
1070 impl<'a> RandomAccessIterator for Iter<'a> {
1072 fn indexable(&self) -> uint {
1073 self.end_idx - self.next_idx
1077 fn idx(&mut self, index: uint) -> Option<bool> {
1078 if index >= self.indexable() {
1081 Some(self.bitv[index])
1086 /// An implementation of a set using a bit vector as an underlying
1087 /// representation for holding unsigned numerical elements.
1089 /// It should also be noted that the amount of storage necessary for holding a
1090 /// set of objects is proportional to the maximum of the objects when viewed
1096 /// use std::collections::{BitvSet, Bitv};
1098 /// // It's a regular set
1099 /// let mut s = BitvSet::new();
1106 /// if !s.contains(&7) {
1107 /// println!("There is no 7");
1110 /// // Can initialize from a `Bitv`
1111 /// let other = BitvSet::from_bitv(Bitv::from_bytes(&[0b11010000]));
1113 /// s.union_with(&other);
1115 /// // Print 0, 1, 3 in some order
1116 /// for x in s.iter() {
1117 /// println!("{}", x);
1120 /// // Can convert back to a `Bitv`
1121 /// let bv: Bitv = s.into_bitv();
1126 pub struct BitvSet {
1131 impl Default for BitvSet {
1133 fn default() -> BitvSet { BitvSet::new() }
1137 impl FromIterator<uint> for BitvSet {
1138 fn from_iter<I:Iterator<Item=uint>>(iterator: I) -> BitvSet {
1139 let mut ret = BitvSet::new();
1140 ret.extend(iterator);
1146 impl Extend<uint> for BitvSet {
1148 fn extend<I: Iterator<Item=uint>>(&mut self, mut iterator: I) {
1156 impl PartialOrd for BitvSet {
1158 fn partial_cmp(&self, other: &BitvSet) -> Option<Ordering> {
1159 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1160 iter::order::partial_cmp(a_iter, b_iter)
1165 impl Ord for BitvSet {
1167 fn cmp(&self, other: &BitvSet) -> Ordering {
1168 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1169 iter::order::cmp(a_iter, b_iter)
1174 impl cmp::PartialEq for BitvSet {
1176 fn eq(&self, other: &BitvSet) -> bool {
1177 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1178 iter::order::eq(a_iter, b_iter)
1183 impl cmp::Eq for BitvSet {}
1186 /// Creates a new empty `BitvSet`.
1191 /// use std::collections::BitvSet;
1193 /// let mut s = BitvSet::new();
1197 pub fn new() -> BitvSet {
1198 BitvSet { bitv: Bitv::new() }
1201 /// Creates a new `BitvSet` with initially no contents, able to
1202 /// hold `nbits` elements without resizing.
1207 /// use std::collections::BitvSet;
1209 /// let mut s = BitvSet::with_capacity(100);
1210 /// assert!(s.capacity() >= 100);
1214 pub fn with_capacity(nbits: uint) -> BitvSet {
1215 let bitv = Bitv::from_elem(nbits, false);
1216 BitvSet::from_bitv(bitv)
1219 /// Creates a new `BitvSet` from the given bit vector.
1224 /// use std::collections::{Bitv, BitvSet};
1226 /// let bv = Bitv::from_bytes(&[0b01100000]);
1227 /// let s = BitvSet::from_bitv(bv);
1229 /// // Print 1, 2 in arbitrary order
1230 /// for x in s.iter() {
1231 /// println!("{}", x);
1235 pub fn from_bitv(bitv: Bitv) -> BitvSet {
1236 BitvSet { bitv: bitv }
1239 /// Returns the capacity in bits for this bit vector. Inserting any
1240 /// element less than this amount will not trigger a resizing.
1245 /// use std::collections::BitvSet;
1247 /// let mut s = BitvSet::with_capacity(100);
1248 /// assert!(s.capacity() >= 100);
1252 pub fn capacity(&self) -> uint {
1253 self.bitv.capacity()
1256 /// Reserves capacity for the given `BitvSet` to contain `len` distinct elements. In the case
1257 /// of `BitvSet` this means reallocations will not occur as long as all inserted elements
1258 /// are less than `len`.
1260 /// The collection may reserve more space to avoid frequent reallocations.
1266 /// use std::collections::BitvSet;
1268 /// let mut s = BitvSet::new();
1269 /// s.reserve_len(10);
1270 /// assert!(s.capacity() >= 10);
1273 pub fn reserve_len(&mut self, len: uint) {
1274 let cur_len = self.bitv.len();
1276 self.bitv.reserve(len - cur_len);
1280 /// Reserves the minimum capacity for the given `BitvSet` to contain `len` distinct elements.
1281 /// In the case of `BitvSet` this means reallocations will not occur as long as all inserted
1282 /// elements are less than `len`.
1284 /// Note that the allocator may give the collection more space than it requests. Therefore
1285 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve_len` if future
1286 /// insertions are expected.
1292 /// use std::collections::BitvSet;
1294 /// let mut s = BitvSet::new();
1295 /// s.reserve_len_exact(10);
1296 /// assert!(s.capacity() >= 10);
1299 pub fn reserve_len_exact(&mut self, len: uint) {
1300 let cur_len = self.bitv.len();
1302 self.bitv.reserve_exact(len - cur_len);
1307 /// Consumes this set to return the underlying bit vector.
1312 /// use std::collections::BitvSet;
1314 /// let mut s = BitvSet::new();
1318 /// let bv = s.into_bitv();
1323 pub fn into_bitv(self) -> Bitv {
1327 /// Returns a reference to the underlying bit vector.
1332 /// use std::collections::BitvSet;
1334 /// let mut s = BitvSet::new();
1337 /// let bv = s.get_ref();
1338 /// assert_eq!(bv[0], true);
1341 pub fn get_ref(&self) -> &Bitv {
1346 fn other_op<F>(&mut self, other: &BitvSet, mut f: F) where F: FnMut(u32, u32) -> u32 {
1348 let self_bitv = &mut self.bitv;
1349 let other_bitv = &other.bitv;
1351 let self_len = self_bitv.len();
1352 let other_len = other_bitv.len();
1354 // Expand the vector if necessary
1355 if self_len < other_len {
1356 self_bitv.grow(other_len - self_len, false);
1359 // virtually pad other with 0's for equal lengths
1360 let mut other_words = {
1361 let (_, result) = match_words(self_bitv, other_bitv);
1365 // Apply values found in other
1366 for (i, w) in other_words {
1367 let old = self_bitv.storage[i];
1368 let new = f(old, w);
1369 self_bitv.storage[i] = new;
1373 /// Truncates the underlying vector to the least length required.
1378 /// use std::collections::BitvSet;
1380 /// let mut s = BitvSet::new();
1381 /// s.insert(32183231);
1382 /// s.remove(&32183231);
1384 /// // Internal storage will probably be bigger than necessary
1385 /// println!("old capacity: {}", s.capacity());
1387 /// // Now should be smaller
1388 /// s.shrink_to_fit();
1389 /// println!("new capacity: {}", s.capacity());
1393 pub fn shrink_to_fit(&mut self) {
1394 let bitv = &mut self.bitv;
1395 // Obtain original length
1396 let old_len = bitv.storage.len();
1397 // Obtain coarse trailing zero length
1398 let n = bitv.storage.iter().rev().take_while(|&&n| n == 0).count();
1400 let trunc_len = cmp::max(old_len - n, 1);
1401 bitv.storage.truncate(trunc_len);
1402 bitv.nbits = trunc_len * u32::BITS;
1405 /// Iterator over each u32 stored in the `BitvSet`.
1410 /// use std::collections::{Bitv, BitvSet};
1412 /// let s = BitvSet::from_bitv(Bitv::from_bytes(&[0b01001010]));
1414 /// // Print 1, 4, 6 in arbitrary order
1415 /// for x in s.iter() {
1416 /// println!("{}", x);
1421 pub fn iter(&self) -> bitv_set::Iter {
1422 SetIter {set: self, next_idx: 0u}
1425 /// Iterator over each u32 stored in `self` union `other`.
1426 /// See [union_with](#method.union_with) for an efficient in-place version.
1431 /// use std::collections::{Bitv, BitvSet};
1433 /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
1434 /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
1436 /// // Print 0, 1, 2, 4 in arbitrary order
1437 /// for x in a.union(&b) {
1438 /// println!("{}", x);
1443 pub fn union<'a>(&'a self, other: &'a BitvSet) -> Union<'a> {
1444 fn or(w1: u32, w2: u32) -> u32 { w1 | w2 }
1446 Union(TwoBitPositions {
1455 /// Iterator over each uint stored in `self` intersect `other`.
1456 /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
1461 /// use std::collections::{Bitv, BitvSet};
1463 /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
1464 /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
1467 /// for x in a.intersection(&b) {
1468 /// println!("{}", x);
1473 pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Intersection<'a> {
1474 fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 }
1475 let min = cmp::min(self.bitv.len(), other.bitv.len());
1476 Intersection(TwoBitPositions {
1485 /// Iterator over each uint stored in the `self` setminus `other`.
1486 /// See [difference_with](#method.difference_with) for an efficient in-place version.
1491 /// use std::collections::{BitvSet, Bitv};
1493 /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
1494 /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
1496 /// // Print 1, 4 in arbitrary order
1497 /// for x in a.difference(&b) {
1498 /// println!("{}", x);
1501 /// // Note that difference is not symmetric,
1502 /// // and `b - a` means something else.
1503 /// // This prints 0
1504 /// for x in b.difference(&a) {
1505 /// println!("{}", x);
1510 pub fn difference<'a>(&'a self, other: &'a BitvSet) -> Difference<'a> {
1511 fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 }
1513 Difference(TwoBitPositions {
1522 /// Iterator over each u32 stored in the symmetric difference of `self` and `other`.
1523 /// See [symmetric_difference_with](#method.symmetric_difference_with) for
1524 /// an efficient in-place version.
1529 /// use std::collections::{BitvSet, Bitv};
1531 /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
1532 /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
1534 /// // Print 0, 1, 4 in arbitrary order
1535 /// for x in a.symmetric_difference(&b) {
1536 /// println!("{}", x);
1541 pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> SymmetricDifference<'a> {
1542 fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 }
1544 SymmetricDifference(TwoBitPositions {
1553 /// Unions in-place with the specified other bit vector.
1558 /// use std::collections::{BitvSet, Bitv};
1560 /// let a = 0b01101000;
1561 /// let b = 0b10100000;
1562 /// let res = 0b11101000;
1564 /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1565 /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1566 /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
1568 /// a.union_with(&b);
1569 /// assert_eq!(a, res);
1572 pub fn union_with(&mut self, other: &BitvSet) {
1573 self.other_op(other, |w1, w2| w1 | w2);
1576 /// Intersects in-place with the specified other bit vector.
1581 /// use std::collections::{BitvSet, Bitv};
1583 /// let a = 0b01101000;
1584 /// let b = 0b10100000;
1585 /// let res = 0b00100000;
1587 /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1588 /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1589 /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
1591 /// a.intersect_with(&b);
1592 /// assert_eq!(a, res);
1595 pub fn intersect_with(&mut self, other: &BitvSet) {
1596 self.other_op(other, |w1, w2| w1 & w2);
1599 /// Makes this bit vector the difference with the specified other bit vector
1605 /// use std::collections::{BitvSet, Bitv};
1607 /// let a = 0b01101000;
1608 /// let b = 0b10100000;
1609 /// let a_b = 0b01001000; // a - b
1610 /// let b_a = 0b10000000; // b - a
1612 /// let mut bva = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1613 /// let bvb = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1614 /// let bva_b = BitvSet::from_bitv(Bitv::from_bytes(&[a_b]));
1615 /// let bvb_a = BitvSet::from_bitv(Bitv::from_bytes(&[b_a]));
1617 /// bva.difference_with(&bvb);
1618 /// assert_eq!(bva, bva_b);
1620 /// let bva = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1621 /// let mut bvb = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1623 /// bvb.difference_with(&bva);
1624 /// assert_eq!(bvb, bvb_a);
1627 pub fn difference_with(&mut self, other: &BitvSet) {
1628 self.other_op(other, |w1, w2| w1 & !w2);
1631 /// Makes this bit vector the symmetric difference with the specified other
1632 /// bit vector in-place.
1637 /// use std::collections::{BitvSet, Bitv};
1639 /// let a = 0b01101000;
1640 /// let b = 0b10100000;
1641 /// let res = 0b11001000;
1643 /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
1644 /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
1645 /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
1647 /// a.symmetric_difference_with(&b);
1648 /// assert_eq!(a, res);
1651 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
1652 self.other_op(other, |w1, w2| w1 ^ w2);
1655 /// Return the number of set bits in this set.
1658 pub fn len(&self) -> uint {
1659 self.bitv.blocks().fold(0, |acc, n| acc + n.count_ones())
1662 /// Returns whether there are no bits set in this set
1665 pub fn is_empty(&self) -> bool {
1669 /// Clears all bits in this set
1672 pub fn clear(&mut self) {
1676 /// Returns `true` if this set contains the specified integer.
1679 pub fn contains(&self, value: &uint) -> bool {
1680 let bitv = &self.bitv;
1681 *value < bitv.nbits && bitv[*value]
1684 /// Returns `true` if the set has no elements in common with `other`.
1685 /// This is equivalent to checking for an empty intersection.
1688 pub fn is_disjoint(&self, other: &BitvSet) -> bool {
1689 self.intersection(other).next().is_none()
1692 /// Returns `true` if the set is a subset of another.
1695 pub fn is_subset(&self, other: &BitvSet) -> bool {
1696 let self_bitv = &self.bitv;
1697 let other_bitv = &other.bitv;
1698 let other_blocks = blocks_for_bits(other_bitv.len());
1700 // Check that `self` intersect `other` is self
1701 self_bitv.blocks().zip(other_bitv.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
1702 // Make sure if `self` has any more blocks than `other`, they're all 0
1703 self_bitv.blocks().skip(other_blocks).all(|w| w == 0)
1706 /// Returns `true` if the set is a superset of another.
1709 pub fn is_superset(&self, other: &BitvSet) -> bool {
1710 other.is_subset(self)
1713 /// Adds a value to the set. Returns `true` if the value was not already
1714 /// present in the set.
1716 pub fn insert(&mut self, value: uint) -> bool {
1717 if self.contains(&value) {
1721 // Ensure we have enough space to hold the new element
1722 let len = self.bitv.len();
1724 self.bitv.grow(value - len + 1, false)
1727 self.bitv.set(value, true);
1731 /// Removes a value from the set. Returns `true` if the value was
1732 /// present in the set.
1734 pub fn remove(&mut self, value: &uint) -> bool {
1735 if !self.contains(value) {
1739 self.bitv.set(*value, false);
1745 impl fmt::Show for BitvSet {
1746 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
1747 try!(write!(fmt, "{{"));
1748 let mut first = true;
1749 for n in self.iter() {
1751 try!(write!(fmt, ", "));
1753 try!(write!(fmt, "{}", n));
1760 impl<S: hash::Writer> hash::Hash<S> for BitvSet {
1761 fn hash(&self, state: &mut S) {
1762 for pos in self.iter() {
1768 /// An iterator for `BitvSet`.
1771 pub struct SetIter<'a> {
1776 /// An iterator combining two `BitvSet` iterators.
1778 struct TwoBitPositions<'a> {
1781 merge: fn(u32, u32) -> u32,
1787 pub struct Union<'a>(TwoBitPositions<'a>);
1789 pub struct Intersection<'a>(Take<TwoBitPositions<'a>>);
1791 pub struct Difference<'a>(TwoBitPositions<'a>);
1793 pub struct SymmetricDifference<'a>(TwoBitPositions<'a>);
1796 impl<'a> Iterator for SetIter<'a> {
1799 fn next(&mut self) -> Option<uint> {
1800 while self.next_idx < self.set.bitv.len() {
1801 let idx = self.next_idx;
1804 if self.set.contains(&idx) {
1813 fn size_hint(&self) -> (uint, Option<uint>) {
1814 (0, Some(self.set.bitv.len() - self.next_idx))
1819 impl<'a> Iterator for TwoBitPositions<'a> {
1822 fn next(&mut self) -> Option<uint> {
1823 while self.next_idx < self.set.bitv.len() ||
1824 self.next_idx < self.other.bitv.len() {
1825 let bit_idx = self.next_idx % u32::BITS;
1827 let s_bitv = &self.set.bitv;
1828 let o_bitv = &self.other.bitv;
1829 // Merging the two words is a bit of an awkward dance since
1830 // one Bitv might be longer than the other
1831 let word_idx = self.next_idx / u32::BITS;
1832 let w1 = if word_idx < s_bitv.storage.len() {
1833 s_bitv.storage[word_idx]
1835 let w2 = if word_idx < o_bitv.storage.len() {
1836 o_bitv.storage[word_idx]
1838 self.current_word = (self.merge)(w1, w2);
1842 if self.current_word & (1 << bit_idx) != 0 {
1843 return Some(self.next_idx - 1);
1850 fn size_hint(&self) -> (uint, Option<uint>) {
1851 let cap = cmp::max(self.set.bitv.len(), self.other.bitv.len());
1852 (0, Some(cap - self.next_idx))
1857 impl<'a> Iterator for Union<'a> {
1860 #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
1861 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
1865 impl<'a> Iterator for Intersection<'a> {
1868 #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
1869 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
1873 impl<'a> Iterator for Difference<'a> {
1876 #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
1877 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
1881 impl<'a> Iterator for SymmetricDifference<'a> {
1884 #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
1885 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
1898 let zerolen = Bitv::new();
1899 assert_eq!(zerolen.to_string(), "");
1901 let eightbits = Bitv::from_elem(8u, false);
1902 assert_eq!(eightbits.to_string(), "00000000")
1906 fn test_0_elements() {
1907 let act = Bitv::new();
1908 let exp = Vec::new();
1909 assert!(act.eq_vec(exp.as_slice()));
1910 assert!(act.none() && act.all());
1914 fn test_1_element() {
1915 let mut act = Bitv::from_elem(1u, false);
1916 assert!(act.eq_vec(&[false]));
1917 assert!(act.none() && !act.all());
1918 act = Bitv::from_elem(1u, true);
1919 assert!(act.eq_vec(&[true]));
1920 assert!(!act.none() && act.all());
1924 fn test_2_elements() {
1925 let mut b = Bitv::from_elem(2, false);
1928 assert_eq!(b.to_string(), "10");
1929 assert!(!b.none() && !b.all());
1933 fn test_10_elements() {
1937 act = Bitv::from_elem(10u, false);
1938 assert!((act.eq_vec(
1939 &[false, false, false, false, false, false, false, false, false, false])));
1940 assert!(act.none() && !act.all());
1943 act = Bitv::from_elem(10u, true);
1944 assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
1945 assert!(!act.none() && act.all());
1948 act = Bitv::from_elem(10u, false);
1954 assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
1955 assert!(!act.none() && !act.all());
1958 act = Bitv::from_elem(10u, false);
1964 assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
1965 assert!(!act.none() && !act.all());
1968 act = Bitv::from_elem(10u, false);
1973 assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
1974 assert!(!act.none() && !act.all());
1978 fn test_31_elements() {
1982 act = Bitv::from_elem(31u, false);
1984 &[false, false, false, false, false, false, false, false, false, false, false,
1985 false, false, false, false, false, false, false, false, false, false, false,
1986 false, false, false, false, false, false, false, false, false]));
1987 assert!(act.none() && !act.all());
1990 act = Bitv::from_elem(31u, true);
1992 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1993 true, true, true, true, true, true, true, true, true, true, true, true, true,
1994 true, true, true, true, true]));
1995 assert!(!act.none() && act.all());
1998 act = Bitv::from_elem(31u, false);
2008 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
2009 false, false, false, false, false, false, false, false, false, false, false,
2010 false, false, false, false, false, false, false]));
2011 assert!(!act.none() && !act.all());
2014 act = Bitv::from_elem(31u, false);
2024 &[false, false, false, false, false, false, false, false, false, false, false,
2025 false, false, false, false, false, true, true, true, true, true, true, true, true,
2026 false, false, false, false, false, false, false]));
2027 assert!(!act.none() && !act.all());
2030 act = Bitv::from_elem(31u, false);
2039 &[false, false, false, false, false, false, false, false, false, false, false,
2040 false, false, false, false, false, false, false, false, false, false, false,
2041 false, false, true, true, true, true, true, true, true]));
2042 assert!(!act.none() && !act.all());
2045 act = Bitv::from_elem(31u, false);
2050 &[false, false, false, true, false, false, false, false, false, false, false, false,
2051 false, false, false, false, false, true, false, false, false, false, false, false,
2052 false, false, false, false, false, false, true]));
2053 assert!(!act.none() && !act.all());
2057 fn test_32_elements() {
2061 act = Bitv::from_elem(32u, false);
2063 &[false, false, false, false, false, false, false, false, false, false, false,
2064 false, false, false, false, false, false, false, false, false, false, false,
2065 false, false, false, false, false, false, false, false, false, false]));
2066 assert!(act.none() && !act.all());
2069 act = Bitv::from_elem(32u, true);
2071 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
2072 true, true, true, true, true, true, true, true, true, true, true, true, true,
2073 true, true, true, true, true, true]));
2074 assert!(!act.none() && act.all());
2077 act = Bitv::from_elem(32u, false);
2087 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
2088 false, false, false, false, false, false, false, false, false, false, false,
2089 false, false, false, false, false, false, false, false]));
2090 assert!(!act.none() && !act.all());
2093 act = Bitv::from_elem(32u, false);
2103 &[false, false, false, false, false, false, false, false, false, false, false,
2104 false, false, false, false, false, true, true, true, true, true, true, true, true,
2105 false, false, false, false, false, false, false, false]));
2106 assert!(!act.none() && !act.all());
2109 act = Bitv::from_elem(32u, false);
2119 &[false, false, false, false, false, false, false, false, false, false, false,
2120 false, false, false, false, false, false, false, false, false, false, false,
2121 false, false, true, true, true, true, true, true, true, true]));
2122 assert!(!act.none() && !act.all());
2125 act = Bitv::from_elem(32u, false);
2131 &[false, false, false, true, false, false, false, false, false, false, false, false,
2132 false, false, false, false, false, true, false, false, false, false, false, false,
2133 false, false, false, false, false, false, true, true]));
2134 assert!(!act.none() && !act.all());
2138 fn test_33_elements() {
2142 act = Bitv::from_elem(33u, false);
2144 &[false, false, false, false, false, false, false, false, false, false, false,
2145 false, false, false, false, false, false, false, false, false, false, false,
2146 false, false, false, false, false, false, false, false, false, false, false]));
2147 assert!(act.none() && !act.all());
2150 act = Bitv::from_elem(33u, true);
2152 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
2153 true, true, true, true, true, true, true, true, true, true, true, true, true,
2154 true, true, true, true, true, true, true]));
2155 assert!(!act.none() && act.all());
2158 act = Bitv::from_elem(33u, false);
2168 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
2169 false, false, false, false, false, false, false, false, false, false, false,
2170 false, false, false, false, false, false, false, false, false]));
2171 assert!(!act.none() && !act.all());
2174 act = Bitv::from_elem(33u, false);
2184 &[false, false, false, false, false, false, false, false, false, false, false,
2185 false, false, false, false, false, true, true, true, true, true, true, true, true,
2186 false, false, false, false, false, false, false, false, false]));
2187 assert!(!act.none() && !act.all());
2190 act = Bitv::from_elem(33u, false);
2200 &[false, false, false, false, false, false, false, false, false, false, false,
2201 false, false, false, false, false, false, false, false, false, false, false,
2202 false, false, true, true, true, true, true, true, true, true, false]));
2203 assert!(!act.none() && !act.all());
2206 act = Bitv::from_elem(33u, false);
2213 &[false, false, false, true, false, false, false, false, false, false, false, false,
2214 false, false, false, false, false, true, false, false, false, false, false, false,
2215 false, false, false, false, false, false, true, true, true]));
2216 assert!(!act.none() && !act.all());
2220 fn test_equal_differing_sizes() {
2221 let v0 = Bitv::from_elem(10u, false);
2222 let v1 = Bitv::from_elem(11u, false);
2227 fn test_equal_greatly_differing_sizes() {
2228 let v0 = Bitv::from_elem(10u, false);
2229 let v1 = Bitv::from_elem(110u, false);
2234 fn test_equal_sneaky_small() {
2235 let mut a = Bitv::from_elem(1, false);
2238 let mut b = Bitv::from_elem(1, true);
2245 fn test_equal_sneaky_big() {
2246 let mut a = Bitv::from_elem(100, false);
2247 for i in range(0u, 100) {
2251 let mut b = Bitv::from_elem(100, true);
2252 for i in range(0u, 100) {
2260 fn test_from_bytes() {
2261 let bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2262 let str = concat!("10110110", "00000000", "11111111");
2263 assert_eq!(bitv.to_string(), str);
2267 fn test_to_bytes() {
2268 let mut bv = Bitv::from_elem(3, true);
2270 assert_eq!(bv.to_bytes(), vec!(0b10100000));
2272 let mut bv = Bitv::from_elem(9, false);
2275 assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
2279 fn test_from_bools() {
2280 let bools = vec![true, false, true, true];
2281 let bitv: Bitv = bools.iter().map(|n| *n).collect();
2282 assert_eq!(bitv.to_string(), "1011");
2286 fn test_to_bools() {
2287 let bools = vec!(false, false, true, false, false, true, true, false);
2288 assert_eq!(Bitv::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
2292 fn test_bitv_iterator() {
2293 let bools = vec![true, false, true, true];
2294 let bitv: Bitv = bools.iter().map(|n| *n).collect();
2296 assert_eq!(bitv.iter().collect::<Vec<bool>>(), bools);
2298 let long = range(0, 10000).map(|i| i % 2 == 0).collect::<Vec<_>>();
2299 let bitv: Bitv = long.iter().map(|n| *n).collect();
2300 assert_eq!(bitv.iter().collect::<Vec<bool>>(), long)
2304 fn test_small_difference() {
2305 let mut b1 = Bitv::from_elem(3, false);
2306 let mut b2 = Bitv::from_elem(3, false);
2311 assert!(b1.difference(&b2));
2318 fn test_big_difference() {
2319 let mut b1 = Bitv::from_elem(100, false);
2320 let mut b2 = Bitv::from_elem(100, false);
2325 assert!(b1.difference(&b2));
2332 fn test_small_clear() {
2333 let mut b = Bitv::from_elem(14, true);
2334 assert!(!b.none() && b.all());
2336 assert!(b.none() && !b.all());
2340 fn test_big_clear() {
2341 let mut b = Bitv::from_elem(140, true);
2342 assert!(!b.none() && b.all());
2344 assert!(b.none() && !b.all());
2349 let mut a = Bitv::from_elem(5u, false);
2350 let mut b = Bitv::from_elem(5u, false);
2352 assert!(!(a < b) && !(b < a));
2358 assert!(!(a < b) && b < a);
2365 let mut a = Bitv::from_elem(5u, false);
2366 let mut b = Bitv::from_elem(5u, false);
2368 assert!(a <= b && a >= b);
2370 assert!(a > b && a >= b);
2371 assert!(b < a && b <= a);
2374 assert!(b > a && b >= a);
2375 assert!(a < b && a <= b);
2380 fn test_small_bitv_tests() {
2381 let v = Bitv::from_bytes(&[0]);
2386 let v = Bitv::from_bytes(&[0b00010100]);
2391 let v = Bitv::from_bytes(&[0xFF]);
2398 fn test_big_bitv_tests() {
2399 let v = Bitv::from_bytes(&[ // 88 bits
2407 let v = Bitv::from_bytes(&[ // 88 bits
2408 0, 0, 0b00010100, 0,
2409 0, 0, 0, 0b00110100,
2415 let v = Bitv::from_bytes(&[ // 88 bits
2416 0xFF, 0xFF, 0xFF, 0xFF,
2417 0xFF, 0xFF, 0xFF, 0xFF,
2425 fn test_bitv_push_pop() {
2426 let mut s = Bitv::from_elem(5 * u32::BITS - 2, false);
2427 assert_eq!(s.len(), 5 * u32::BITS - 2);
2428 assert_eq!(s[5 * u32::BITS - 3], false);
2431 assert_eq!(s[5 * u32::BITS - 2], true);
2432 assert_eq!(s[5 * u32::BITS - 1], true);
2433 // Here the internal vector will need to be extended
2435 assert_eq!(s[5 * u32::BITS], false);
2437 assert_eq!(s[5 * u32::BITS + 1], false);
2438 assert_eq!(s.len(), 5 * u32::BITS + 2);
2440 assert_eq!(s.pop(), Some(false));
2441 assert_eq!(s.pop(), Some(false));
2442 assert_eq!(s.pop(), Some(true));
2443 assert_eq!(s.pop(), Some(true));
2444 assert_eq!(s.len(), 5 * u32::BITS - 2);
2448 fn test_bitv_truncate() {
2449 let mut s = Bitv::from_elem(5 * u32::BITS, true);
2451 assert_eq!(s, Bitv::from_elem(5 * u32::BITS, true));
2452 assert_eq!(s.len(), 5 * u32::BITS);
2453 s.truncate(4 * u32::BITS);
2454 assert_eq!(s, Bitv::from_elem(4 * u32::BITS, true));
2455 assert_eq!(s.len(), 4 * u32::BITS);
2456 // Truncating to a size > s.len() should be a noop
2457 s.truncate(5 * u32::BITS);
2458 assert_eq!(s, Bitv::from_elem(4 * u32::BITS, true));
2459 assert_eq!(s.len(), 4 * u32::BITS);
2460 s.truncate(3 * u32::BITS - 10);
2461 assert_eq!(s, Bitv::from_elem(3 * u32::BITS - 10, true));
2462 assert_eq!(s.len(), 3 * u32::BITS - 10);
2464 assert_eq!(s, Bitv::from_elem(0, true));
2465 assert_eq!(s.len(), 0);
2469 fn test_bitv_reserve() {
2470 let mut s = Bitv::from_elem(5 * u32::BITS, true);
2472 assert!(s.capacity() >= 5 * u32::BITS);
2473 s.reserve(2 * u32::BITS);
2474 assert!(s.capacity() >= 7 * u32::BITS);
2475 s.reserve(7 * u32::BITS);
2476 assert!(s.capacity() >= 12 * u32::BITS);
2477 s.reserve_exact(7 * u32::BITS);
2478 assert!(s.capacity() >= 12 * u32::BITS);
2479 s.reserve(7 * u32::BITS + 1);
2480 assert!(s.capacity() >= 12 * u32::BITS + 1);
2481 // Check that length hasn't changed
2482 assert_eq!(s.len(), 5 * u32::BITS);
2486 assert_eq!(s[5 * u32::BITS - 1], true);
2487 assert_eq!(s[5 * u32::BITS - 0], true);
2488 assert_eq!(s[5 * u32::BITS + 1], false);
2489 assert_eq!(s[5 * u32::BITS + 2], true);
2493 fn test_bitv_grow() {
2494 let mut bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
2495 bitv.grow(32, true);
2496 assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2497 0xFF, 0xFF, 0xFF, 0xFF]));
2498 bitv.grow(64, false);
2499 assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2500 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
2501 bitv.grow(16, true);
2502 assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2503 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
2507 fn test_bitv_extend() {
2508 let mut bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2509 let ext = Bitv::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
2510 bitv.extend(ext.iter());
2511 assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111,
2512 0b01001001, 0b10010010, 0b10111101]));
2521 use std::prelude::v1::*;
2525 use test::{Bencher, black_box};
2529 static BENCH_BITS : uint = 1 << 14;
2531 fn rng() -> rand::IsaacRng {
2532 let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
2533 rand::SeedableRng::from_seed(seed)
2537 fn bench_uint_small(b: &mut Bencher) {
2539 let mut bitv = 0 as uint;
2541 for _ in range(0u, 100) {
2542 bitv |= 1 << ((r.next_u32() as uint) % u32::BITS);
2549 fn bench_bitv_set_big_fixed(b: &mut Bencher) {
2551 let mut bitv = Bitv::from_elem(BENCH_BITS, false);
2553 for _ in range(0u, 100) {
2554 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
2561 fn bench_bitv_set_big_variable(b: &mut Bencher) {
2563 let mut bitv = Bitv::from_elem(BENCH_BITS, false);
2565 for _ in range(0u, 100) {
2566 bitv.set((r.next_u32() as uint) % BENCH_BITS, r.gen());
2573 fn bench_bitv_set_small(b: &mut Bencher) {
2575 let mut bitv = Bitv::from_elem(u32::BITS, false);
2577 for _ in range(0u, 100) {
2578 bitv.set((r.next_u32() as uint) % u32::BITS, true);
2585 fn bench_bitv_big_union(b: &mut Bencher) {
2586 let mut b1 = Bitv::from_elem(BENCH_BITS, false);
2587 let b2 = Bitv::from_elem(BENCH_BITS, false);
2594 fn bench_bitv_small_iter(b: &mut Bencher) {
2595 let bitv = Bitv::from_elem(u32::BITS, false);
2598 for _ in range(0u, 10) {
2599 for pres in bitv.iter() {
2600 sum += pres as uint;
2608 fn bench_bitv_big_iter(b: &mut Bencher) {
2609 let bitv = Bitv::from_elem(BENCH_BITS, false);
2612 for pres in bitv.iter() {
2613 sum += pres as uint;
2629 use std::iter::range_step;
2631 use super::{Bitv, BitvSet};
2634 fn test_bitv_set_show() {
2635 let mut s = BitvSet::new();
2640 assert_eq!("{1, 2, 10, 50}", s.to_string());
2644 fn test_bitv_set_from_uints() {
2645 let uints = vec![0, 2, 2, 3];
2646 let a: BitvSet = uints.into_iter().collect();
2647 let mut b = BitvSet::new();
2655 fn test_bitv_set_iterator() {
2656 let uints = vec![0, 2, 2, 3];
2657 let bitv: BitvSet = uints.into_iter().collect();
2659 let idxs: Vec<uint> = bitv.iter().collect();
2660 assert_eq!(idxs, vec![0, 2, 3]);
2662 let long: BitvSet = range(0u, 10000).filter(|&n| n % 2 == 0).collect();
2663 let real = range_step(0, 10000, 2).collect::<Vec<uint>>();
2665 let idxs: Vec<uint> = long.iter().collect();
2666 assert_eq!(idxs, real);
2670 fn test_bitv_set_frombitv_init() {
2671 let bools = [true, false];
2672 let lengths = [10, 64, 100];
2673 for &b in bools.iter() {
2674 for &l in lengths.iter() {
2675 let bitset = BitvSet::from_bitv(Bitv::from_elem(l, b));
2676 assert_eq!(bitset.contains(&1u), b);
2677 assert_eq!(bitset.contains(&(l-1u)), b);
2678 assert!(!bitset.contains(&l));
2684 fn test_bitv_masking() {
2685 let b = Bitv::from_elem(140, true);
2686 let mut bs = BitvSet::from_bitv(b);
2687 assert!(bs.contains(&139));
2688 assert!(!bs.contains(&140));
2689 assert!(bs.insert(150));
2690 assert!(!bs.contains(&140));
2691 assert!(!bs.contains(&149));
2692 assert!(bs.contains(&150));
2693 assert!(!bs.contains(&151));
2697 fn test_bitv_set_basic() {
2698 let mut b = BitvSet::new();
2699 assert!(b.insert(3));
2700 assert!(!b.insert(3));
2701 assert!(b.contains(&3));
2702 assert!(b.insert(4));
2703 assert!(!b.insert(4));
2704 assert!(b.contains(&3));
2705 assert!(b.insert(400));
2706 assert!(!b.insert(400));
2707 assert!(b.contains(&400));
2708 assert_eq!(b.len(), 3);
2712 fn test_bitv_set_intersection() {
2713 let mut a = BitvSet::new();
2714 let mut b = BitvSet::new();
2716 assert!(a.insert(11));
2717 assert!(a.insert(1));
2718 assert!(a.insert(3));
2719 assert!(a.insert(77));
2720 assert!(a.insert(103));
2721 assert!(a.insert(5));
2723 assert!(b.insert(2));
2724 assert!(b.insert(11));
2725 assert!(b.insert(77));
2726 assert!(b.insert(5));
2727 assert!(b.insert(3));
2729 let expected = [3, 5, 11, 77];
2730 let actual = a.intersection(&b).collect::<Vec<uint>>();
2731 assert_eq!(actual, expected);
2735 fn test_bitv_set_difference() {
2736 let mut a = BitvSet::new();
2737 let mut b = BitvSet::new();
2739 assert!(a.insert(1));
2740 assert!(a.insert(3));
2741 assert!(a.insert(5));
2742 assert!(a.insert(200));
2743 assert!(a.insert(500));
2745 assert!(b.insert(3));
2746 assert!(b.insert(200));
2748 let expected = [1, 5, 500];
2749 let actual = a.difference(&b).collect::<Vec<uint>>();
2750 assert_eq!(actual, expected);
2754 fn test_bitv_set_symmetric_difference() {
2755 let mut a = BitvSet::new();
2756 let mut b = BitvSet::new();
2758 assert!(a.insert(1));
2759 assert!(a.insert(3));
2760 assert!(a.insert(5));
2761 assert!(a.insert(9));
2762 assert!(a.insert(11));
2764 assert!(b.insert(3));
2765 assert!(b.insert(9));
2766 assert!(b.insert(14));
2767 assert!(b.insert(220));
2769 let expected = [1, 5, 11, 14, 220];
2770 let actual = a.symmetric_difference(&b).collect::<Vec<uint>>();
2771 assert_eq!(actual, expected);
2775 fn test_bitv_set_union() {
2776 let mut a = BitvSet::new();
2777 let mut b = BitvSet::new();
2778 assert!(a.insert(1));
2779 assert!(a.insert(3));
2780 assert!(a.insert(5));
2781 assert!(a.insert(9));
2782 assert!(a.insert(11));
2783 assert!(a.insert(160));
2784 assert!(a.insert(19));
2785 assert!(a.insert(24));
2786 assert!(a.insert(200));
2788 assert!(b.insert(1));
2789 assert!(b.insert(5));
2790 assert!(b.insert(9));
2791 assert!(b.insert(13));
2792 assert!(b.insert(19));
2794 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
2795 let actual = a.union(&b).collect::<Vec<uint>>();
2796 assert_eq!(actual, expected);
2800 fn test_bitv_set_subset() {
2801 let mut set1 = BitvSet::new();
2802 let mut set2 = BitvSet::new();
2804 assert!(set1.is_subset(&set2)); // {} {}
2806 assert!(set1.is_subset(&set2)); // {} { 1 }
2808 assert!(set1.is_subset(&set2)); // {} { 1, 2 }
2810 assert!(set1.is_subset(&set2)); // { 2 } { 1, 2 }
2812 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 1, 2 }
2814 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3 }
2816 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3, 4 }
2818 assert!(set1.is_subset(&set2)); // { 2, 3 } { 2, 3, 4 }
2820 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 2, 4 }
2822 assert!(set1.is_subset(&set2)); // { 2 } { 2, 4 }
2826 fn test_bitv_set_is_disjoint() {
2827 let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2828 let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01000000]));
2829 let c = BitvSet::new();
2830 let d = BitvSet::from_bitv(Bitv::from_bytes(&[0b00110000]));
2832 assert!(!a.is_disjoint(&d));
2833 assert!(!d.is_disjoint(&a));
2835 assert!(a.is_disjoint(&b));
2836 assert!(a.is_disjoint(&c));
2837 assert!(b.is_disjoint(&a));
2838 assert!(b.is_disjoint(&c));
2839 assert!(c.is_disjoint(&a));
2840 assert!(c.is_disjoint(&b));
2844 fn test_bitv_set_union_with() {
2845 //a should grow to include larger elements
2846 let mut a = BitvSet::new();
2848 let mut b = BitvSet::new();
2850 let expected = BitvSet::from_bitv(Bitv::from_bytes(&[0b10000100]));
2852 assert_eq!(a, expected);
2855 let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2856 let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
2860 assert_eq!(a.len(), 4);
2861 assert_eq!(b.len(), 4);
2865 fn test_bitv_set_intersect_with() {
2866 // Explicitly 0'ed bits
2867 let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2868 let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
2870 a.intersect_with(&b);
2871 b.intersect_with(&c);
2872 assert!(a.is_empty());
2873 assert!(b.is_empty());
2875 // Uninitialized bits should behave like 0's
2876 let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2877 let mut b = BitvSet::new();
2879 a.intersect_with(&b);
2880 b.intersect_with(&c);
2881 assert!(a.is_empty());
2882 assert!(b.is_empty());
2885 let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2886 let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
2888 a.intersect_with(&b);
2889 b.intersect_with(&c);
2890 assert_eq!(a.len(), 2);
2891 assert_eq!(b.len(), 2);
2895 fn test_bitv_set_difference_with() {
2896 // Explicitly 0'ed bits
2897 let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
2898 let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2899 a.difference_with(&b);
2900 assert!(a.is_empty());
2902 // Uninitialized bits should behave like 0's
2903 let mut a = BitvSet::new();
2904 let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b11111111]));
2905 a.difference_with(&b);
2906 assert!(a.is_empty());
2909 let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2910 let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
2912 a.difference_with(&b);
2913 b.difference_with(&c);
2914 assert_eq!(a.len(), 1);
2915 assert_eq!(b.len(), 1);
2919 fn test_bitv_set_symmetric_difference_with() {
2920 //a should grow to include larger elements
2921 let mut a = BitvSet::new();
2924 let mut b = BitvSet::new();
2927 let expected = BitvSet::from_bitv(Bitv::from_bytes(&[0b10000100]));
2928 a.symmetric_difference_with(&b);
2929 assert_eq!(a, expected);
2931 let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2932 let b = BitvSet::new();
2934 a.symmetric_difference_with(&b);
2938 let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b11100010]));
2939 let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101010]));
2941 a.symmetric_difference_with(&b);
2942 b.symmetric_difference_with(&c);
2943 assert_eq!(a.len(), 2);
2944 assert_eq!(b.len(), 2);
2948 fn test_bitv_set_eq() {
2949 let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2950 let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
2951 let c = BitvSet::new();
2962 fn test_bitv_set_cmp() {
2963 let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
2964 let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
2965 let c = BitvSet::new();
2967 assert_eq!(a.cmp(&b), Greater);
2968 assert_eq!(a.cmp(&c), Greater);
2969 assert_eq!(b.cmp(&a), Less);
2970 assert_eq!(b.cmp(&c), Equal);
2971 assert_eq!(c.cmp(&a), Less);
2972 assert_eq!(c.cmp(&b), Equal);
2976 fn test_bitv_remove() {
2977 let mut a = BitvSet::new();
2979 assert!(a.insert(1));
2980 assert!(a.remove(&1));
2982 assert!(a.insert(100));
2983 assert!(a.remove(&100));
2985 assert!(a.insert(1000));
2986 assert!(a.remove(&1000));
2991 fn test_bitv_clone() {
2992 let mut a = BitvSet::new();
2994 assert!(a.insert(1));
2995 assert!(a.insert(100));
2996 assert!(a.insert(1000));
2998 let mut b = a.clone();
3002 assert!(b.remove(&1));
3003 assert!(a.contains(&1));
3005 assert!(a.remove(&1000));
3006 assert!(b.contains(&1000));
3015 mod bitv_set_bench {
3016 use std::prelude::v1::*;
3020 use test::{Bencher, black_box};
3022 use super::{Bitv, BitvSet};
3024 static BENCH_BITS : uint = 1 << 14;
3026 fn rng() -> rand::IsaacRng {
3027 let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
3028 rand::SeedableRng::from_seed(seed)
3032 fn bench_bitvset_small(b: &mut Bencher) {
3034 let mut bitv = BitvSet::new();
3036 for _ in range(0u, 100) {
3037 bitv.insert((r.next_u32() as uint) % u32::BITS);
3044 fn bench_bitvset_big(b: &mut Bencher) {
3046 let mut bitv = BitvSet::new();
3048 for _ in range(0u, 100) {
3049 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
3056 fn bench_bitvset_iter(b: &mut Bencher) {
3057 let bitv = BitvSet::from_bitv(Bitv::from_fn(BENCH_BITS,
3058 |idx| {idx % 3 == 0}));
3061 for idx in bitv.iter() {