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 maintenance),
12 // they should be in separate files/modules, with BitvSet only using Bitv's public API.
14 //! Collections implemented with bit vectors.
18 //! This is a simple example of the [Sieve of Eratosthenes][sieve]
19 //! which calculates prime numbers up to a given limit.
21 //! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
24 //! use std::collections::{BitvSet, Bitv};
25 //! use std::num::Float;
28 //! let max_prime = 10000;
30 //! // Store the primes as a BitvSet
32 //! // Assume all numbers are prime to begin, and then we
33 //! // cross off non-primes progressively
34 //! let mut bv = Bitv::with_capacity(max_prime, true);
36 //! // Neither 0 nor 1 are prime
40 //! for i in iter::range_inclusive(2, (max_prime as f64).sqrt() as uint) {
41 //! // if i is a prime
43 //! // Mark all multiples of i as non-prime (any multiples below i * i
44 //! // will have been marked as non-prime previously)
45 //! for j in iter::range_step(i * i, max_prime, i) { bv.set(j, false) }
48 //! BitvSet::from_bitv(bv)
51 //! // Simple primality tests below our max bound
52 //! let print_primes = 20;
53 //! print!("The primes below {} are: ", print_primes);
54 //! for x in range(0, print_primes) {
55 //! if primes.contains(&x) {
61 //! // We can manipulate the internal Bitv
62 //! let num_primes = primes.get_ref().iter().filter(|x| *x).count();
63 //! println!("There are {} primes below {}", num_primes, max_prime);
69 use core::default::Default;
71 use core::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat};
80 // FIXME(conventions): look, we just need to refactor this whole thing. Inside and out.
82 type MatchWords<'a> = Chain<MaskWords<'a>, Skip<Take<Enumerate<Repeat<u32>>>>>;
83 // Take two BitV's, and return iterators of their words, where the shorter one
84 // has been padded with 0's
85 fn match_words <'a,'b>(a: &'a Bitv, b: &'b Bitv) -> (MatchWords<'a>, MatchWords<'b>) {
86 let a_len = a.storage.len();
87 let b_len = b.storage.len();
89 // have to uselessly pretend to pad the longer one for type matching
91 (a.mask_words(0).chain(repeat(0u32).enumerate().take(b_len).skip(a_len)),
92 b.mask_words(0).chain(repeat(0u32).enumerate().take(0).skip(0)))
94 (a.mask_words(0).chain(repeat(0u32).enumerate().take(0).skip(0)),
95 b.mask_words(0).chain(repeat(0u32).enumerate().take(a_len).skip(b_len)))
99 static TRUE: bool = true;
100 static FALSE: bool = false;
102 /// The bitvector type.
107 /// use collections::Bitv;
109 /// let mut bv = Bitv::with_capacity(10, false);
111 /// // insert all primes less than 10
116 /// println!("{}", bv.to_string());
117 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
119 /// // flip all values in bitvector, producing non-primes less than 10
121 /// println!("{}", bv.to_string());
122 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
124 /// // reset bitvector to empty
126 /// println!("{}", bv.to_string());
127 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
130 /// Internal representation of the bit vector
132 /// The number of valid bits in the internal representation
136 impl Index<uint,bool> for Bitv {
138 fn index<'a>(&'a self, i: &uint) -> &'a bool {
147 struct MaskWords<'a> {
148 iter: slice::Items<'a, u32>,
149 next_word: Option<&'a u32>,
154 impl<'a> Iterator<(uint, u32)> for MaskWords<'a> {
155 /// Returns (offset, word)
157 fn next<'a>(&'a mut self) -> Option<(uint, u32)> {
158 let ret = self.next_word;
161 self.next_word = self.iter.next();
163 // The last word may need to be masked
164 if self.next_word.is_none() {
165 Some((self.offset - 1, w & self.last_word_mask))
167 Some((self.offset - 1, w))
177 fn process(&mut self, other: &Bitv, op: |u32, u32| -> u32) -> bool {
178 let len = other.storage.len();
179 assert_eq!(self.storage.len(), len);
180 let mut changed = false;
181 // Notice: `a` is *not* masked here, which is fine as long as
182 // `op` is a bitwise operation, since any bits that should've
183 // been masked were fine to change anyway. `b` is masked to
184 // make sure its unmasked bits do not cause damage.
185 for (a, (_, b)) in self.storage.iter_mut()
186 .zip(other.mask_words(0)) {
197 fn mask_words<'a>(&'a self, mut start: uint) -> MaskWords<'a> {
198 if start > self.storage.len() {
199 start = self.storage.len();
201 let mut iter = self.storage[start..].iter();
203 next_word: iter.next(),
206 let rem = self.nbits % u32::BITS;
215 /// Creates an empty `Bitv`.
220 /// use std::collections::Bitv;
221 /// let mut bv = Bitv::new();
223 #[unstable = "matches collection reform specification, waiting for dust to settle"]
224 pub fn new() -> Bitv {
225 Bitv { storage: Vec::new(), nbits: 0 }
228 /// Creates a `Bitv` that holds `nbits` elements, setting each element
234 /// use std::collections::Bitv;
236 /// let mut bv = Bitv::with_capacity(10u, false);
237 /// assert_eq!(bv.len(), 10u);
238 /// for x in bv.iter() {
239 /// assert_eq!(x, false);
242 pub fn with_capacity(nbits: uint, init: bool) -> Bitv {
243 let mut bitv = Bitv {
244 storage: Vec::from_elem((nbits + u32::BITS - 1) / u32::BITS,
245 if init { !0u32 } else { 0u32 }),
249 // Zero out any unused bits in the highest word if necessary
250 let used_bits = bitv.nbits % u32::BITS;
251 if init && used_bits != 0 {
252 let largest_used_word = (bitv.nbits + u32::BITS - 1) / u32::BITS - 1;
253 bitv.storage[largest_used_word] &= (1 << used_bits) - 1;
259 /// Retrieves the value at index `i`.
263 /// Panics if `i` is out of bounds.
268 /// use std::collections::bitv;
270 /// let bv = bitv::from_bytes(&[0b01100000]);
271 /// assert_eq!(bv.get(0), false);
272 /// assert_eq!(bv.get(1), true);
274 /// // Can also use array indexing
275 /// assert_eq!(bv[1], true);
278 pub fn get(&self, i: uint) -> bool {
279 assert!(i < self.nbits);
280 let w = i / u32::BITS;
281 let b = i % u32::BITS;
282 let x = self.storage[w] & (1 << b);
286 /// Sets the value of a bit at an index `i`.
290 /// Panics if `i` is out of bounds.
295 /// use std::collections::Bitv;
297 /// let mut bv = Bitv::with_capacity(5, false);
299 /// assert_eq!(bv[3], true);
302 pub fn set(&mut self, i: uint, x: bool) {
303 assert!(i < self.nbits);
304 let w = i / u32::BITS;
305 let b = i % u32::BITS;
307 let val = if x { self.storage[w] | flag }
308 else { self.storage[w] & !flag };
309 self.storage[w] = val;
312 /// Sets all bits to 1.
317 /// use std::collections::bitv;
319 /// let before = 0b01100000;
320 /// let after = 0b11111111;
322 /// let mut bv = bitv::from_bytes(&[before]);
324 /// assert_eq!(bv, bitv::from_bytes(&[after]));
327 pub fn set_all(&mut self) {
328 for w in self.storage.iter_mut() { *w = !0u32; }
336 /// use std::collections::bitv;
338 /// let before = 0b01100000;
339 /// let after = 0b10011111;
341 /// let mut bv = bitv::from_bytes(&[before]);
343 /// assert_eq!(bv, bitv::from_bytes(&[after]));
346 pub fn negate(&mut self) {
347 for w in self.storage.iter_mut() { *w = !*w; }
350 /// Calculates the union of two bitvectors. This acts like the bitwise `or`
353 /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
354 /// the same length. Returns `true` if `self` changed.
358 /// Panics if the bitvectors are of different lengths.
363 /// use std::collections::bitv;
365 /// let a = 0b01100100;
366 /// let b = 0b01011010;
367 /// let res = 0b01111110;
369 /// let mut a = bitv::from_bytes(&[a]);
370 /// let b = bitv::from_bytes(&[b]);
372 /// assert!(a.union(&b));
373 /// assert_eq!(a, bitv::from_bytes(&[res]));
376 pub fn union(&mut self, other: &Bitv) -> bool {
377 self.process(other, |w1, w2| w1 | w2)
380 /// Calculates the intersection of two bitvectors. This acts like the
381 /// bitwise `and` function.
383 /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
384 /// must be the same length. Returns `true` if `self` changed.
388 /// Panics if the bitvectors are of different lengths.
393 /// use std::collections::bitv;
395 /// let a = 0b01100100;
396 /// let b = 0b01011010;
397 /// let res = 0b01000000;
399 /// let mut a = bitv::from_bytes(&[a]);
400 /// let b = bitv::from_bytes(&[b]);
402 /// assert!(a.intersect(&b));
403 /// assert_eq!(a, bitv::from_bytes(&[res]));
406 pub fn intersect(&mut self, other: &Bitv) -> bool {
407 self.process(other, |w1, w2| w1 & w2)
410 /// Calculates the difference between two bitvectors.
412 /// Sets each element of `self` to the value of that element minus the
413 /// element of `other` at the same index. Both bitvectors must be the same
414 /// length. Returns `true` if `self` changed.
418 /// Panics if the bitvectors are of different length.
423 /// use std::collections::bitv;
425 /// let a = 0b01100100;
426 /// let b = 0b01011010;
427 /// let a_b = 0b00100100; // a - b
428 /// let b_a = 0b00011010; // b - a
430 /// let mut bva = bitv::from_bytes(&[a]);
431 /// let bvb = bitv::from_bytes(&[b]);
433 /// assert!(bva.difference(&bvb));
434 /// assert_eq!(bva, bitv::from_bytes(&[a_b]));
436 /// let bva = bitv::from_bytes(&[a]);
437 /// let mut bvb = bitv::from_bytes(&[b]);
439 /// assert!(bvb.difference(&bva));
440 /// assert_eq!(bvb, bitv::from_bytes(&[b_a]));
443 pub fn difference(&mut self, other: &Bitv) -> bool {
444 self.process(other, |w1, w2| w1 & !w2)
447 /// Returns `true` if all bits are 1.
452 /// use std::collections::Bitv;
454 /// let mut bv = Bitv::with_capacity(5, true);
455 /// assert_eq!(bv.all(), true);
457 /// bv.set(1, false);
458 /// assert_eq!(bv.all(), false);
461 pub fn all(&self) -> bool {
462 let mut last_word = !0u32;
463 // Check that every word but the last is all-ones...
464 self.mask_words(0).all(|(_, elem)|
465 { let tmp = last_word; last_word = elem; tmp == !0u32 }) &&
466 // ...and that the last word is ones as far as it needs to be
467 (last_word == ((1 << self.nbits % u32::BITS) - 1) || last_word == !0u32)
470 /// Returns an iterator over the elements of the vector in order.
475 /// use std::collections::bitv;
477 /// let bv = bitv::from_bytes(&[0b01110100, 0b10010010]);
478 /// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
481 pub fn iter<'a>(&'a self) -> Bits<'a> {
482 Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
485 /// Returns `true` if all bits are 0.
490 /// use std::collections::Bitv;
492 /// let mut bv = Bitv::with_capacity(10, false);
493 /// assert_eq!(bv.none(), true);
496 /// assert_eq!(bv.none(), false);
498 pub fn none(&self) -> bool {
499 self.mask_words(0).all(|(_, w)| w == 0)
502 /// Returns `true` if any bit is 1.
507 /// use std::collections::Bitv;
509 /// let mut bv = Bitv::with_capacity(10, false);
510 /// assert_eq!(bv.any(), false);
513 /// assert_eq!(bv.any(), true);
516 pub fn any(&self) -> bool {
520 /// Organises the bits into bytes, such that the first bit in the
521 /// `Bitv` becomes the high-order bit of the first byte. If the
522 /// size of the `Bitv` is not a multiple of eight then trailing bits
523 /// will be filled-in with `false`.
528 /// use std::collections::Bitv;
530 /// let mut bv = Bitv::with_capacity(3, true);
531 /// bv.set(1, false);
533 /// assert_eq!(bv.to_bytes(), vec!(0b10100000));
535 /// let mut bv = Bitv::with_capacity(9, false);
539 /// assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
541 pub fn to_bytes(&self) -> Vec<u8> {
542 fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
543 let offset = byte * 8 + bit;
544 if offset >= bitv.nbits {
547 bitv.get(offset) as u8 << (7 - bit)
551 let len = self.nbits/8 +
552 if self.nbits % 8 == 0 { 0 } else { 1 };
553 Vec::from_fn(len, |i|
565 /// Transforms `self` into a `Vec<bool>` by turning each bit into a `bool`.
570 /// use std::collections::bitv;
572 /// let bv = bitv::from_bytes(&[0b10100000]);
573 /// assert_eq!(bv.to_bools(), vec!(true, false, true, false,
574 /// false, false, false, false));
576 pub fn to_bools(&self) -> Vec<bool> {
577 Vec::from_fn(self.nbits, |i| self.get(i))
580 /// Compares a `Bitv` to a slice of `bool`s.
581 /// Both the `Bitv` and slice must have the same length.
585 /// Panics if the `Bitv` and slice are of different length.
590 /// use std::collections::bitv;
592 /// let bv = bitv::from_bytes(&[0b10100000]);
594 /// assert!(bv.eq_vec(&[true, false, true, false,
595 /// false, false, false, false]));
597 pub fn eq_vec(&self, v: &[bool]) -> bool {
598 assert_eq!(self.nbits, v.len());
600 while i < self.nbits {
601 if self.get(i) != v[i] { return false; }
607 /// Shortens a `Bitv`, dropping excess elements.
609 /// If `len` is greater than the vector's current length, this has no
615 /// use std::collections::bitv;
617 /// let mut bv = bitv::from_bytes(&[0b01001011]);
619 /// assert!(bv.eq_vec(&[false, true]));
621 #[unstable = "matches collection reform specification, waiting for dust to settle"]
622 pub fn truncate(&mut self, len: uint) {
623 if len < self.len() {
625 let word_len = (len + u32::BITS - 1) / u32::BITS;
626 self.storage.truncate(word_len);
627 if len % u32::BITS > 0 {
628 let mask = (1 << len % u32::BITS) - 1;
629 self.storage[word_len - 1] &= mask;
634 /// Grows the vector to be able to store `size` bits without resizing.
639 /// use std::collections::Bitv;
641 /// let mut bv = Bitv::with_capacity(3, false);
643 /// assert_eq!(bv.len(), 3);
644 /// assert!(bv.capacity() >= 10);
646 pub fn reserve(&mut self, size: uint) {
647 let old_size = self.storage.len();
648 let new_size = (size + u32::BITS - 1) / u32::BITS;
649 if old_size < new_size {
650 self.storage.grow(new_size - old_size, 0);
654 /// Returns the capacity in bits for this bit vector. Inserting any
655 /// element less than this amount will not trigger a resizing.
660 /// use std::collections::Bitv;
662 /// let mut bv = Bitv::new();
664 /// assert!(bv.capacity() >= 10);
667 pub fn capacity(&self) -> uint {
668 self.storage.len() * u32::BITS
671 /// Grows the `Bitv` in-place, adding `n` copies of `value` to the `Bitv`.
676 /// use std::collections::bitv;
678 /// let mut bv = bitv::from_bytes(&[0b01001011]);
679 /// bv.grow(2, true);
680 /// assert_eq!(bv.len(), 10);
681 /// assert_eq!(bv.to_bytes(), vec!(0b01001011, 0b11000000));
683 pub fn grow(&mut self, n: uint, value: bool) {
684 let new_nbits = self.nbits + n;
685 let new_nwords = (new_nbits + u32::BITS - 1) / u32::BITS;
686 let full_value = if value { !0 } else { 0 };
687 // Correct the old tail word
688 let old_last_word = (self.nbits + u32::BITS - 1) / u32::BITS - 1;
689 if self.nbits % u32::BITS > 0 {
690 let overhang = self.nbits % u32::BITS; // # of already-used bits
691 let mask = !((1 << overhang) - 1); // e.g. 5 unused bits => 111110....0
693 self.storage[old_last_word] |= mask;
695 self.storage[old_last_word] &= !mask;
698 // Fill in words after the old tail word
699 let stop_idx = cmp::min(self.storage.len(), new_nwords);
700 for idx in range(old_last_word + 1, stop_idx) {
701 self.storage[idx] = full_value;
703 // Allocate new words, if needed
704 if new_nwords > self.storage.len() {
705 let to_add = new_nwords - self.storage.len();
706 self.storage.grow(to_add, full_value);
708 // Zero out and unused bits in the new tail word
710 let tail_word = new_nwords - 1;
711 let used_bits = new_nbits % u32::BITS;
712 self.storage[tail_word] &= (1 << used_bits) - 1;
715 // Adjust internal bit count
716 self.nbits = new_nbits;
719 /// Shortens by one element and returns the removed element.
728 /// use std::collections::bitv;
730 /// let mut bv = bitv::from_bytes(&[0b01001001]);
731 /// assert_eq!(bv.pop(), true);
732 /// assert_eq!(bv.pop(), false);
733 /// assert_eq!(bv.len(), 6);
734 /// assert_eq!(bv.to_bytes(), vec!(0b01001000));
736 pub fn pop(&mut self) -> bool {
737 let ret = self.get(self.nbits - 1);
738 // If we are unusing a whole word, make sure it is zeroed out
739 if self.nbits % u32::BITS == 1 {
740 self.storage[self.nbits / u32::BITS] = 0;
746 /// Pushes a `bool` onto the end.
751 /// use std::collections::Bitv;
753 /// let mut bv = Bitv::new();
756 /// assert!(bv.eq_vec(&[true, false]));
758 pub fn push(&mut self, elem: bool) {
759 let insert_pos = self.nbits;
761 if self.storage.len() * u32::BITS < self.nbits {
762 self.storage.push(0);
764 self.set(insert_pos, elem);
767 /// Return the total number of bits in this vector
769 #[unstable = "matches collection reform specification, waiting for dust to settle"]
770 pub fn len(&self) -> uint { self.nbits }
772 /// Returns true if there are no bits in this vector
774 #[unstable = "matches collection reform specification, waiting for dust to settle"]
775 pub fn is_empty(&self) -> bool { self.len() == 0 }
777 /// Clears all bits in this vector.
779 #[unstable = "matches collection reform specification, waiting for dust to settle"]
780 pub fn clear(&mut self) {
781 for w in self.storage.iter_mut() { *w = 0u32; }
785 /// Transforms a byte-vector into a `Bitv`. Each byte becomes eight bits,
786 /// with the most significant bits of each byte coming first. Each
787 /// bit becomes `true` if equal to 1 or `false` if equal to 0.
792 /// use std::collections::bitv;
794 /// let bv = bitv::from_bytes(&[0b10100000, 0b00010010]);
795 /// assert!(bv.eq_vec(&[true, false, true, false,
796 /// false, false, false, false,
797 /// false, false, false, true,
798 /// false, false, true, false]));
800 pub fn from_bytes(bytes: &[u8]) -> Bitv {
801 from_fn(bytes.len() * 8, |i| {
802 let b = bytes[i / 8] as u32;
804 b >> (7 - offset) & 1 == 1
808 /// Creates a `Bitv` of the specified length where the value at each
809 /// index is `f(index)`.
814 /// use std::collections::bitv::from_fn;
816 /// let bv = from_fn(5, |i| { i % 2 == 0 });
817 /// assert!(bv.eq_vec(&[true, false, true, false, true]));
819 pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
820 let mut bitv = Bitv::with_capacity(len, false);
821 for i in range(0u, len) {
827 impl Default for Bitv {
829 fn default() -> Bitv { Bitv::new() }
832 impl FromIterator<bool> for Bitv {
833 fn from_iter<I:Iterator<bool>>(iterator: I) -> Bitv {
834 let mut ret = Bitv::new();
835 ret.extend(iterator);
840 impl Extend<bool> for Bitv {
842 fn extend<I: Iterator<bool>>(&mut self, mut iterator: I) {
843 let (min, _) = iterator.size_hint();
844 let nbits = self.nbits;
845 self.reserve(nbits + min);
846 for element in iterator {
852 impl Clone for Bitv {
854 fn clone(&self) -> Bitv {
855 Bitv { storage: self.storage.clone(), nbits: self.nbits }
859 fn clone_from(&mut self, source: &Bitv) {
860 self.nbits = source.nbits;
861 self.storage.clone_from(&source.storage);
865 impl PartialOrd for Bitv {
867 fn partial_cmp(&self, other: &Bitv) -> Option<Ordering> {
868 iter::order::partial_cmp(self.iter(), other.iter())
874 fn cmp(&self, other: &Bitv) -> Ordering {
875 iter::order::cmp(self.iter(), other.iter())
879 impl fmt::Show for Bitv {
880 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
881 for bit in self.iter() {
882 try!(write!(fmt, "{}", if bit { 1u } else { 0u }));
888 impl<S: hash::Writer> hash::Hash<S> for Bitv {
889 fn hash(&self, state: &mut S) {
890 self.nbits.hash(state);
891 for (_, elem) in self.mask_words(0) {
897 impl cmp::PartialEq for Bitv {
899 fn eq(&self, other: &Bitv) -> bool {
900 if self.nbits != other.nbits {
903 self.mask_words(0).zip(other.mask_words(0)).all(|((_, w1), (_, w2))| w1 == w2)
907 impl cmp::Eq for Bitv {}
909 /// An iterator for `Bitv`.
910 pub struct Bits<'a> {
916 impl<'a> Iterator<bool> for Bits<'a> {
918 fn next(&mut self) -> Option<bool> {
919 if self.next_idx != self.end_idx {
920 let idx = self.next_idx;
922 Some(self.bitv.get(idx))
928 fn size_hint(&self) -> (uint, Option<uint>) {
929 let rem = self.end_idx - self.next_idx;
934 impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
936 fn next_back(&mut self) -> Option<bool> {
937 if self.next_idx != self.end_idx {
939 Some(self.bitv.get(self.end_idx))
946 impl<'a> ExactSizeIterator<bool> for Bits<'a> {}
948 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
950 fn indexable(&self) -> uint {
951 self.end_idx - self.next_idx
955 fn idx(&mut self, index: uint) -> Option<bool> {
956 if index >= self.indexable() {
959 Some(self.bitv.get(index))
964 /// An implementation of a set using a bit vector as an underlying
965 /// representation for holding unsigned numerical elements.
967 /// It should also be noted that the amount of storage necessary for holding a
968 /// set of objects is proportional to the maximum of the objects when viewed
974 /// use std::collections::{BitvSet, Bitv};
975 /// use std::collections::bitv;
977 /// // It's a regular set
978 /// let mut s = BitvSet::new();
985 /// if !s.contains(&7) {
986 /// println!("There is no 7");
989 /// // Can initialize from a `Bitv`
990 /// let other = BitvSet::from_bitv(bitv::from_bytes(&[0b11010000]));
992 /// s.union_with(&other);
994 /// // Print 0, 1, 3 in some order
995 /// for x in s.iter() {
996 /// println!("{}", x);
999 /// // Can convert back to a `Bitv`
1000 /// let bv: Bitv = s.into_bitv();
1001 /// assert!(bv.get(3));
1004 pub struct BitvSet(Bitv);
1006 impl Default for BitvSet {
1008 fn default() -> BitvSet { BitvSet::new() }
1011 impl FromIterator<bool> for BitvSet {
1012 fn from_iter<I:Iterator<bool>>(iterator: I) -> BitvSet {
1013 let mut ret = BitvSet::new();
1014 ret.extend(iterator);
1019 impl Extend<bool> for BitvSet {
1021 fn extend<I: Iterator<bool>>(&mut self, iterator: I) {
1022 let &BitvSet(ref mut self_bitv) = self;
1023 self_bitv.extend(iterator);
1027 impl PartialOrd for BitvSet {
1029 fn partial_cmp(&self, other: &BitvSet) -> Option<Ordering> {
1030 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1031 iter::order::partial_cmp(a_iter, b_iter)
1035 impl Ord for BitvSet {
1037 fn cmp(&self, other: &BitvSet) -> Ordering {
1038 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1039 iter::order::cmp(a_iter, b_iter)
1043 impl cmp::PartialEq for BitvSet {
1045 fn eq(&self, other: &BitvSet) -> bool {
1046 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1047 iter::order::eq(a_iter, b_iter)
1051 impl cmp::Eq for BitvSet {}
1054 /// Creates a new bit vector set with initially no contents.
1059 /// use std::collections::BitvSet;
1060 /// let mut s = BitvSet::new();
1063 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1064 pub fn new() -> BitvSet {
1065 BitvSet(Bitv::new())
1068 /// Creates a new bit vector set with initially no contents, able to
1069 /// hold `nbits` elements without resizing.
1074 /// use std::collections::BitvSet;
1075 /// let mut s = BitvSet::with_capacity(100);
1076 /// assert!(s.capacity() >= 100);
1079 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1080 pub fn with_capacity(nbits: uint) -> BitvSet {
1081 let bitv = Bitv::with_capacity(nbits, false);
1082 BitvSet::from_bitv(bitv)
1085 /// Creates a new bit vector set from the given bit vector.
1090 /// use std::collections::{bitv, BitvSet};
1092 /// let bv = bitv::from_bytes(&[0b01100000]);
1093 /// let s = BitvSet::from_bitv(bv);
1095 /// // Print 1, 2 in arbitrary order
1096 /// for x in s.iter() {
1097 /// println!("{}", x);
1101 pub fn from_bitv(mut bitv: Bitv) -> BitvSet {
1102 // Mark every bit as valid
1103 bitv.nbits = bitv.capacity();
1107 /// Returns the capacity in bits for this bit vector. Inserting any
1108 /// element less than this amount will not trigger a resizing.
1113 /// use std::collections::BitvSet;
1115 /// let mut s = BitvSet::with_capacity(100);
1116 /// assert!(s.capacity() >= 100);
1119 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1120 pub fn capacity(&self) -> uint {
1121 let &BitvSet(ref bitv) = self;
1125 /// Grows the underlying vector to be able to store `size` bits.
1130 /// use std::collections::BitvSet;
1132 /// let mut s = BitvSet::new();
1134 /// assert!(s.capacity() >= 10);
1136 pub fn reserve(&mut self, size: uint) {
1137 let &BitvSet(ref mut bitv) = self;
1139 if bitv.nbits < size {
1140 bitv.nbits = bitv.capacity();
1144 /// Consumes this set to return the underlying bit vector.
1149 /// use std::collections::BitvSet;
1151 /// let mut s = BitvSet::new();
1155 /// let bv = s.into_bitv();
1156 /// assert!(bv.get(0));
1157 /// assert!(bv.get(3));
1160 pub fn into_bitv(self) -> Bitv {
1161 let BitvSet(bitv) = self;
1165 /// Returns a reference to the underlying bit vector.
1170 /// use std::collections::BitvSet;
1172 /// let mut s = BitvSet::new();
1175 /// let bv = s.get_ref();
1176 /// assert_eq!(bv[0], true);
1179 pub fn get_ref<'a>(&'a self) -> &'a Bitv {
1180 let &BitvSet(ref bitv) = self;
1185 fn other_op(&mut self, other: &BitvSet, f: |u32, u32| -> u32) {
1186 // Expand the vector if necessary
1187 self.reserve(other.capacity());
1190 let &BitvSet(ref mut self_bitv) = self;
1191 let &BitvSet(ref other_bitv) = other;
1193 // virtually pad other with 0's for equal lengths
1194 let mut other_words = {
1195 let (_, result) = match_words(self_bitv, other_bitv);
1199 // Apply values found in other
1200 for (i, w) in other_words {
1201 let old = self_bitv.storage[i];
1202 let new = f(old, w);
1203 self_bitv.storage[i] = new;
1207 /// Truncates the underlying vector to the least length required.
1212 /// use std::collections::BitvSet;
1214 /// let mut s = BitvSet::new();
1215 /// s.insert(32183231);
1216 /// s.remove(&32183231);
1218 /// // Internal storage will probably be bigger than necessary
1219 /// println!("old capacity: {}", s.capacity());
1221 /// // Now should be smaller
1222 /// s.shrink_to_fit();
1223 /// println!("new capacity: {}", s.capacity());
1226 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1227 pub fn shrink_to_fit(&mut self) {
1228 let &BitvSet(ref mut bitv) = self;
1229 // Obtain original length
1230 let old_len = bitv.storage.len();
1231 // Obtain coarse trailing zero length
1232 let n = bitv.storage.iter().rev().take_while(|&&n| n == 0).count();
1234 let trunc_len = cmp::max(old_len - n, 1);
1235 bitv.storage.truncate(trunc_len);
1236 bitv.nbits = trunc_len * u32::BITS;
1239 /// Iterator over each u32 stored in the `BitvSet`.
1244 /// use std::collections::BitvSet;
1245 /// use std::collections::bitv;
1247 /// let s = BitvSet::from_bitv(bitv::from_bytes(&[0b01001010]));
1249 /// // Print 1, 4, 6 in arbitrary order
1250 /// for x in s.iter() {
1251 /// println!("{}", x);
1255 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1256 pub fn iter<'a>(&'a self) -> BitPositions<'a> {
1257 BitPositions {set: self, next_idx: 0u}
1260 /// Iterator over each u32 stored in `self` union `other`.
1261 /// See [union_with](#method.union_with) for an efficient in-place version.
1266 /// use std::collections::BitvSet;
1267 /// use std::collections::bitv;
1269 /// let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000]));
1270 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000]));
1272 /// // Print 0, 1, 2, 4 in arbitrary order
1273 /// for x in a.union(&b) {
1274 /// println!("{}", x);
1278 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1279 pub fn union<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
1283 merge: |w1, w2| w1 | w2,
1289 /// Iterator over each uint stored in `self` intersect `other`.
1290 /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
1295 /// use std::collections::BitvSet;
1296 /// use std::collections::bitv;
1298 /// let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000]));
1299 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000]));
1302 /// for x in a.intersection(&b) {
1303 /// println!("{}", x);
1307 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1308 pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Take<TwoBitPositions<'a>> {
1309 let min = cmp::min(self.capacity(), other.capacity());
1313 merge: |w1, w2| w1 & w2,
1319 /// Iterator over each uint stored in the `self` setminus `other`.
1320 /// See [difference_with](#method.difference_with) for an efficient in-place version.
1325 /// use std::collections::BitvSet;
1326 /// use std::collections::bitv;
1328 /// let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000]));
1329 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000]));
1331 /// // Print 1, 4 in arbitrary order
1332 /// for x in a.difference(&b) {
1333 /// println!("{}", x);
1336 /// // Note that difference is not symmetric,
1337 /// // and `b - a` means something else.
1338 /// // This prints 0
1339 /// for x in b.difference(&a) {
1340 /// println!("{}", x);
1344 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1345 pub fn difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
1349 merge: |w1, w2| w1 & !w2,
1355 /// Iterator over each u32 stored in the symmetric difference of `self` and `other`.
1356 /// See [symmetric_difference_with](#method.symmetric_difference_with) for
1357 /// an efficient in-place version.
1362 /// use std::collections::BitvSet;
1363 /// use std::collections::bitv;
1365 /// let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000]));
1366 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000]));
1368 /// // Print 0, 1, 4 in arbitrary order
1369 /// for x in a.symmetric_difference(&b) {
1370 /// println!("{}", x);
1374 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1375 pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
1379 merge: |w1, w2| w1 ^ w2,
1385 /// Unions in-place with the specified other bit vector.
1390 /// use std::collections::BitvSet;
1391 /// use std::collections::bitv;
1393 /// let a = 0b01101000;
1394 /// let b = 0b10100000;
1395 /// let res = 0b11101000;
1397 /// let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1398 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1399 /// let res = BitvSet::from_bitv(bitv::from_bytes(&[res]));
1401 /// a.union_with(&b);
1402 /// assert_eq!(a, res);
1405 pub fn union_with(&mut self, other: &BitvSet) {
1406 self.other_op(other, |w1, w2| w1 | w2);
1409 /// Intersects in-place with the specified other bit vector.
1414 /// use std::collections::BitvSet;
1415 /// use std::collections::bitv;
1417 /// let a = 0b01101000;
1418 /// let b = 0b10100000;
1419 /// let res = 0b00100000;
1421 /// let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1422 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1423 /// let res = BitvSet::from_bitv(bitv::from_bytes(&[res]));
1425 /// a.intersect_with(&b);
1426 /// assert_eq!(a, res);
1429 pub fn intersect_with(&mut self, other: &BitvSet) {
1430 self.other_op(other, |w1, w2| w1 & w2);
1433 /// Makes this bit vector the difference with the specified other bit vector
1439 /// use std::collections::BitvSet;
1440 /// use std::collections::bitv;
1442 /// let a = 0b01101000;
1443 /// let b = 0b10100000;
1444 /// let a_b = 0b01001000; // a - b
1445 /// let b_a = 0b10000000; // b - a
1447 /// let mut bva = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1448 /// let bvb = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1449 /// let bva_b = BitvSet::from_bitv(bitv::from_bytes(&[a_b]));
1450 /// let bvb_a = BitvSet::from_bitv(bitv::from_bytes(&[b_a]));
1452 /// bva.difference_with(&bvb);
1453 /// assert_eq!(bva, bva_b);
1455 /// let bva = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1456 /// let mut bvb = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1458 /// bvb.difference_with(&bva);
1459 /// assert_eq!(bvb, bvb_a);
1462 pub fn difference_with(&mut self, other: &BitvSet) {
1463 self.other_op(other, |w1, w2| w1 & !w2);
1466 /// Makes this bit vector the symmetric difference with the specified other
1467 /// bit vector in-place.
1472 /// use std::collections::BitvSet;
1473 /// use std::collections::bitv;
1475 /// let a = 0b01101000;
1476 /// let b = 0b10100000;
1477 /// let res = 0b11001000;
1479 /// let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1480 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1481 /// let res = BitvSet::from_bitv(bitv::from_bytes(&[res]));
1483 /// a.symmetric_difference_with(&b);
1484 /// assert_eq!(a, res);
1487 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
1488 self.other_op(other, |w1, w2| w1 ^ w2);
1491 /// Return the number of set bits in this set.
1493 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1494 pub fn len(&self) -> uint {
1495 let &BitvSet(ref bitv) = self;
1496 bitv.storage.iter().fold(0, |acc, &n| acc + n.count_ones())
1499 /// Returns whether there are no bits set in this set
1501 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1502 pub fn is_empty(&self) -> bool {
1503 let &BitvSet(ref bitv) = self;
1504 bitv.storage.iter().all(|&n| n == 0)
1507 /// Clears all bits in this set
1509 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1510 pub fn clear(&mut self) {
1511 let &BitvSet(ref mut bitv) = self;
1515 /// Returns `true` if this set contains the specified integer.
1517 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1518 pub fn contains(&self, value: &uint) -> bool {
1519 let &BitvSet(ref bitv) = self;
1520 *value < bitv.nbits && bitv.get(*value)
1523 /// Returns `true` if the set has no elements in common with `other`.
1524 /// This is equivalent to checking for an empty intersection.
1526 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1527 pub fn is_disjoint(&self, other: &BitvSet) -> bool {
1528 self.intersection(other).next().is_none()
1531 /// Returns `true` if the set is a subset of another.
1533 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1534 pub fn is_subset(&self, other: &BitvSet) -> bool {
1535 let &BitvSet(ref self_bitv) = self;
1536 let &BitvSet(ref other_bitv) = other;
1538 // Check that `self` intersect `other` is self
1539 self_bitv.mask_words(0).zip(other_bitv.mask_words(0))
1540 .all(|((_, w1), (_, w2))| w1 & w2 == w1) &&
1541 // Check that `self` setminus `other` is empty
1542 self_bitv.mask_words(other_bitv.storage.len()).all(|(_, w)| w == 0)
1545 /// Returns `true` if the set is a superset of another.
1547 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1548 pub fn is_superset(&self, other: &BitvSet) -> bool {
1549 other.is_subset(self)
1552 /// Adds a value to the set. Returns `true` if the value was not already
1553 /// present in the set.
1554 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1555 pub fn insert(&mut self, value: uint) -> bool {
1556 if self.contains(&value) {
1560 // Ensure we have enough space to hold the new element
1561 if value >= self.capacity() {
1562 let new_cap = cmp::max(value + 1, self.capacity() * 2);
1563 self.reserve(new_cap);
1566 let &BitvSet(ref mut bitv) = self;
1567 bitv.set(value, true);
1571 /// Removes a value from the set. Returns `true` if the value was
1572 /// present in the set.
1573 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1574 pub fn remove(&mut self, value: &uint) -> bool {
1575 if !self.contains(value) {
1578 let &BitvSet(ref mut bitv) = self;
1579 bitv.set(*value, false);
1584 impl fmt::Show for BitvSet {
1585 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
1586 try!(write!(fmt, "{{"));
1587 let mut first = true;
1588 for n in self.iter() {
1590 try!(write!(fmt, ", "));
1592 try!(write!(fmt, "{}", n));
1599 impl<S: hash::Writer> hash::Hash<S> for BitvSet {
1600 fn hash(&self, state: &mut S) {
1601 for pos in self.iter() {
1607 /// An iterator for `BitvSet`.
1608 pub struct BitPositions<'a> {
1613 /// An iterator combining two `BitvSet` iterators.
1614 pub struct TwoBitPositions<'a> {
1617 merge: |u32, u32|: 'a -> u32,
1622 impl<'a> Iterator<uint> for BitPositions<'a> {
1623 fn next(&mut self) -> Option<uint> {
1624 while self.next_idx < self.set.capacity() {
1625 let idx = self.next_idx;
1628 if self.set.contains(&idx) {
1637 fn size_hint(&self) -> (uint, Option<uint>) {
1638 (0, Some(self.set.capacity() - self.next_idx))
1642 impl<'a> Iterator<uint> for TwoBitPositions<'a> {
1643 fn next(&mut self) -> Option<uint> {
1644 while self.next_idx < self.set.capacity() ||
1645 self.next_idx < self.other.capacity() {
1646 let bit_idx = self.next_idx % u32::BITS;
1648 let &BitvSet(ref s_bitv) = self.set;
1649 let &BitvSet(ref o_bitv) = self.other;
1650 // Merging the two words is a bit of an awkward dance since
1651 // one Bitv might be longer than the other
1652 let word_idx = self.next_idx / u32::BITS;
1653 let w1 = if word_idx < s_bitv.storage.len() {
1654 s_bitv.storage[word_idx]
1656 let w2 = if word_idx < o_bitv.storage.len() {
1657 o_bitv.storage[word_idx]
1659 self.current_word = (self.merge)(w1, w2);
1663 if self.current_word & (1 << bit_idx) != 0 {
1664 return Some(self.next_idx - 1);
1671 fn size_hint(&self) -> (uint, Option<uint>) {
1672 let cap = cmp::max(self.set.capacity(), self.other.capacity());
1673 (0, Some(cap - self.next_idx))
1679 use std::prelude::*;
1680 use std::iter::range_step;
1684 use test::{Bencher, black_box};
1686 use super::{Bitv, BitvSet, from_fn, from_bytes};
1690 static BENCH_BITS : uint = 1 << 14;
1694 let zerolen = Bitv::new();
1695 assert_eq!(zerolen.to_string().as_slice(), "");
1697 let eightbits = Bitv::with_capacity(8u, false);
1698 assert_eq!(eightbits.to_string().as_slice(), "00000000")
1702 fn test_0_elements() {
1703 let act = Bitv::new();
1704 let exp = Vec::from_elem(0u, false);
1705 assert!(act.eq_vec(exp.as_slice()));
1709 fn test_1_element() {
1710 let mut act = Bitv::with_capacity(1u, false);
1711 assert!(act.eq_vec(&[false]));
1712 act = Bitv::with_capacity(1u, true);
1713 assert!(act.eq_vec(&[true]));
1717 fn test_2_elements() {
1718 let mut b = bitv::Bitv::with_capacity(2, false);
1721 assert_eq!(b.to_string().as_slice(), "10");
1725 fn test_10_elements() {
1729 act = Bitv::with_capacity(10u, false);
1730 assert!((act.eq_vec(
1731 &[false, false, false, false, false, false, false, false, false, false])));
1734 act = Bitv::with_capacity(10u, true);
1735 assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
1738 act = Bitv::with_capacity(10u, false);
1744 assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
1747 act = Bitv::with_capacity(10u, false);
1753 assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
1756 act = Bitv::with_capacity(10u, false);
1761 assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
1765 fn test_31_elements() {
1769 act = Bitv::with_capacity(31u, false);
1771 &[false, false, false, false, false, false, false, false, false, false, false,
1772 false, false, false, false, false, false, false, false, false, false, false,
1773 false, false, false, false, false, false, false, false, false]));
1776 act = Bitv::with_capacity(31u, true);
1778 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1779 true, true, true, true, true, true, true, true, true, true, true, true, true,
1780 true, true, true, true, true]));
1783 act = Bitv::with_capacity(31u, false);
1793 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1794 false, false, false, false, false, false, false, false, false, false, false,
1795 false, false, false, false, false, false, false]));
1798 act = Bitv::with_capacity(31u, false);
1808 &[false, false, false, false, false, false, false, false, false, false, false,
1809 false, false, false, false, false, true, true, true, true, true, true, true, true,
1810 false, false, false, false, false, false, false]));
1813 act = Bitv::with_capacity(31u, false);
1822 &[false, false, false, false, false, false, false, false, false, false, false,
1823 false, false, false, false, false, false, false, false, false, false, false,
1824 false, false, true, true, true, true, true, true, true]));
1827 act = Bitv::with_capacity(31u, false);
1832 &[false, false, false, true, false, false, false, false, false, false, false, false,
1833 false, false, false, false, false, true, false, false, false, false, false, false,
1834 false, false, false, false, false, false, true]));
1838 fn test_32_elements() {
1842 act = Bitv::with_capacity(32u, false);
1844 &[false, false, false, false, false, false, false, false, false, false, false,
1845 false, false, false, false, false, false, false, false, false, false, false,
1846 false, false, false, false, false, false, false, false, false, false]));
1849 act = Bitv::with_capacity(32u, true);
1851 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1852 true, true, true, true, true, true, true, true, true, true, true, true, true,
1853 true, true, true, true, true, true]));
1856 act = Bitv::with_capacity(32u, false);
1866 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1867 false, false, false, false, false, false, false, false, false, false, false,
1868 false, false, false, false, false, false, false, false]));
1871 act = Bitv::with_capacity(32u, false);
1881 &[false, false, false, false, false, false, false, false, false, false, false,
1882 false, false, false, false, false, true, true, true, true, true, true, true, true,
1883 false, false, false, false, false, false, false, false]));
1886 act = Bitv::with_capacity(32u, false);
1896 &[false, false, false, false, false, false, false, false, false, false, false,
1897 false, false, false, false, false, false, false, false, false, false, false,
1898 false, false, true, true, true, true, true, true, true, true]));
1901 act = Bitv::with_capacity(32u, false);
1907 &[false, false, false, true, false, false, false, false, false, false, false, false,
1908 false, false, false, false, false, true, false, false, false, false, false, false,
1909 false, false, false, false, false, false, true, true]));
1913 fn test_33_elements() {
1917 act = Bitv::with_capacity(33u, false);
1919 &[false, false, false, false, false, false, false, false, false, false, false,
1920 false, false, false, false, false, false, false, false, false, false, false,
1921 false, false, false, false, false, false, false, false, false, false, false]));
1924 act = Bitv::with_capacity(33u, true);
1926 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1927 true, true, true, true, true, true, true, true, true, true, true, true, true,
1928 true, true, true, true, true, true, true]));
1931 act = Bitv::with_capacity(33u, false);
1941 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1942 false, false, false, false, false, false, false, false, false, false, false,
1943 false, false, false, false, false, false, false, false, false]));
1946 act = Bitv::with_capacity(33u, false);
1956 &[false, false, false, false, false, false, false, false, false, false, false,
1957 false, false, false, false, false, true, true, true, true, true, true, true, true,
1958 false, false, false, false, false, false, false, false, false]));
1961 act = Bitv::with_capacity(33u, false);
1971 &[false, false, false, false, false, false, false, false, false, false, false,
1972 false, false, false, false, false, false, false, false, false, false, false,
1973 false, false, true, true, true, true, true, true, true, true, false]));
1976 act = Bitv::with_capacity(33u, false);
1983 &[false, false, false, true, false, false, false, false, false, false, false, false,
1984 false, false, false, false, false, true, false, false, false, false, false, false,
1985 false, false, false, false, false, false, true, true, true]));
1989 fn test_equal_differing_sizes() {
1990 let v0 = Bitv::with_capacity(10u, false);
1991 let v1 = Bitv::with_capacity(11u, false);
1996 fn test_equal_greatly_differing_sizes() {
1997 let v0 = Bitv::with_capacity(10u, false);
1998 let v1 = Bitv::with_capacity(110u, false);
2003 fn test_equal_sneaky_small() {
2004 let mut a = bitv::Bitv::with_capacity(1, false);
2007 let mut b = bitv::Bitv::with_capacity(1, true);
2014 fn test_equal_sneaky_big() {
2015 let mut a = bitv::Bitv::with_capacity(100, false);
2016 for i in range(0u, 100) {
2020 let mut b = bitv::Bitv::with_capacity(100, true);
2021 for i in range(0u, 100) {
2029 fn test_from_bytes() {
2030 let bitv = from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2031 let str = format!("{}{}{}", "10110110", "00000000", "11111111");
2032 assert_eq!(bitv.to_string().as_slice(), str.as_slice());
2036 fn test_to_bytes() {
2037 let mut bv = Bitv::with_capacity(3, true);
2039 assert_eq!(bv.to_bytes(), vec!(0b10100000));
2041 let mut bv = Bitv::with_capacity(9, false);
2044 assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
2048 fn test_from_bools() {
2049 let bools = vec![true, false, true, true];
2050 let bitv: Bitv = bools.iter().map(|n| *n).collect();
2051 assert_eq!(bitv.to_string().as_slice(), "1011");
2055 fn test_bitv_set_from_bools() {
2056 let bools = vec![true, false, true, true];
2057 let a: BitvSet = bools.iter().map(|n| *n).collect();
2058 let mut b = BitvSet::new();
2066 fn test_to_bools() {
2067 let bools = vec!(false, false, true, false, false, true, true, false);
2068 assert_eq!(from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
2072 fn test_bitv_iterator() {
2073 let bools = vec![true, false, true, true];
2074 let bitv: Bitv = bools.iter().map(|n| *n).collect();
2076 assert_eq!(bitv.iter().collect::<Vec<bool>>(), bools)
2078 let long = Vec::from_fn(10000, |i| i % 2 == 0);
2079 let bitv: Bitv = long.iter().map(|n| *n).collect();
2080 assert_eq!(bitv.iter().collect::<Vec<bool>>(), long)
2084 fn test_bitv_set_iterator() {
2085 let bools = [true, false, true, true];
2086 let bitv: BitvSet = bools.iter().map(|n| *n).collect();
2088 let idxs: Vec<uint> = bitv.iter().collect();
2089 assert_eq!(idxs, vec!(0, 2, 3));
2091 let long: BitvSet = range(0u, 10000).map(|n| n % 2 == 0).collect();
2092 let real = range_step(0, 10000, 2).collect::<Vec<uint>>();
2094 let idxs: Vec<uint> = long.iter().collect();
2095 assert_eq!(idxs, real);
2099 fn test_bitv_set_frombitv_init() {
2100 let bools = [true, false];
2101 let lengths = [10, 64, 100];
2102 for &b in bools.iter() {
2103 for &l in lengths.iter() {
2104 let bitset = BitvSet::from_bitv(Bitv::with_capacity(l, b));
2105 assert_eq!(bitset.contains(&1u), b)
2106 assert_eq!(bitset.contains(&(l-1u)), b)
2107 assert!(!bitset.contains(&l))
2113 fn test_small_difference() {
2114 let mut b1 = Bitv::with_capacity(3, false);
2115 let mut b2 = Bitv::with_capacity(3, false);
2120 assert!(b1.difference(&b2));
2122 assert!(!b1.get(1));
2123 assert!(!b1.get(2));
2127 fn test_big_difference() {
2128 let mut b1 = Bitv::with_capacity(100, false);
2129 let mut b2 = Bitv::with_capacity(100, false);
2134 assert!(b1.difference(&b2));
2136 assert!(!b1.get(40));
2137 assert!(!b1.get(80));
2141 fn test_small_clear() {
2142 let mut b = Bitv::with_capacity(14, true);
2148 fn test_big_clear() {
2149 let mut b = Bitv::with_capacity(140, true);
2155 fn test_bitv_masking() {
2156 let b = Bitv::with_capacity(140, true);
2157 let mut bs = BitvSet::from_bitv(b);
2158 assert!(bs.contains(&139));
2159 assert!(!bs.contains(&140));
2160 assert!(bs.insert(150));
2161 assert!(!bs.contains(&140));
2162 assert!(!bs.contains(&149));
2163 assert!(bs.contains(&150));
2164 assert!(!bs.contains(&151));
2168 fn test_bitv_set_basic() {
2169 // calculate nbits with u32::BITS granularity
2170 fn calc_nbits(bits: uint) -> uint {
2171 u32::BITS * ((bits + u32::BITS - 1) / u32::BITS)
2174 let mut b = BitvSet::new();
2175 assert_eq!(b.capacity(), calc_nbits(0));
2176 assert!(b.insert(3));
2177 assert_eq!(b.capacity(), calc_nbits(3));
2178 assert!(!b.insert(3));
2179 assert!(b.contains(&3));
2180 assert!(b.insert(4));
2181 assert!(!b.insert(4));
2182 assert!(b.contains(&3));
2183 assert!(b.insert(400));
2184 assert_eq!(b.capacity(), calc_nbits(400));
2185 assert!(!b.insert(400));
2186 assert!(b.contains(&400));
2187 assert_eq!(b.len(), 3);
2191 fn test_bitv_set_intersection() {
2192 let mut a = BitvSet::new();
2193 let mut b = BitvSet::new();
2195 assert!(a.insert(11));
2196 assert!(a.insert(1));
2197 assert!(a.insert(3));
2198 assert!(a.insert(77));
2199 assert!(a.insert(103));
2200 assert!(a.insert(5));
2202 assert!(b.insert(2));
2203 assert!(b.insert(11));
2204 assert!(b.insert(77));
2205 assert!(b.insert(5));
2206 assert!(b.insert(3));
2208 let expected = [3, 5, 11, 77];
2209 let actual = a.intersection(&b).collect::<Vec<uint>>();
2210 assert_eq!(actual.as_slice(), expected.as_slice());
2214 fn test_bitv_set_difference() {
2215 let mut a = BitvSet::new();
2216 let mut b = BitvSet::new();
2218 assert!(a.insert(1));
2219 assert!(a.insert(3));
2220 assert!(a.insert(5));
2221 assert!(a.insert(200));
2222 assert!(a.insert(500));
2224 assert!(b.insert(3));
2225 assert!(b.insert(200));
2227 let expected = [1, 5, 500];
2228 let actual = a.difference(&b).collect::<Vec<uint>>();
2229 assert_eq!(actual.as_slice(), expected.as_slice());
2233 fn test_bitv_set_symmetric_difference() {
2234 let mut a = BitvSet::new();
2235 let mut b = BitvSet::new();
2237 assert!(a.insert(1));
2238 assert!(a.insert(3));
2239 assert!(a.insert(5));
2240 assert!(a.insert(9));
2241 assert!(a.insert(11));
2243 assert!(b.insert(3));
2244 assert!(b.insert(9));
2245 assert!(b.insert(14));
2246 assert!(b.insert(220));
2248 let expected = [1, 5, 11, 14, 220];
2249 let actual = a.symmetric_difference(&b).collect::<Vec<uint>>();
2250 assert_eq!(actual.as_slice(), expected.as_slice());
2254 fn test_bitv_set_union() {
2255 let mut a = BitvSet::new();
2256 let mut b = BitvSet::new();
2257 assert!(a.insert(1));
2258 assert!(a.insert(3));
2259 assert!(a.insert(5));
2260 assert!(a.insert(9));
2261 assert!(a.insert(11));
2262 assert!(a.insert(160));
2263 assert!(a.insert(19));
2264 assert!(a.insert(24));
2265 assert!(a.insert(200));
2267 assert!(b.insert(1));
2268 assert!(b.insert(5));
2269 assert!(b.insert(9));
2270 assert!(b.insert(13));
2271 assert!(b.insert(19));
2273 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
2274 let actual = a.union(&b).collect::<Vec<uint>>();
2275 assert_eq!(actual.as_slice(), expected.as_slice());
2279 fn test_bitv_set_subset() {
2280 let mut set1 = BitvSet::new();
2281 let mut set2 = BitvSet::new();
2283 assert!(set1.is_subset(&set2)); // {} {}
2285 assert!(set1.is_subset(&set2)); // {} { 1 }
2287 assert!(set1.is_subset(&set2)); // {} { 1, 2 }
2289 assert!(set1.is_subset(&set2)); // { 2 } { 1, 2 }
2291 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 1, 2 }
2293 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3 }
2295 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3, 4 }
2297 assert!(set1.is_subset(&set2)); // { 2, 3 } { 2, 3, 4 }
2299 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 2, 4 }
2301 assert!(set1.is_subset(&set2)); // { 2 } { 2, 4 }
2305 fn test_bitv_set_is_disjoint() {
2306 let a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2307 let b = BitvSet::from_bitv(from_bytes(&[0b01000000]));
2308 let c = BitvSet::new();
2309 let d = BitvSet::from_bitv(from_bytes(&[0b00110000]));
2311 assert!(!a.is_disjoint(&d));
2312 assert!(!d.is_disjoint(&a));
2314 assert!(a.is_disjoint(&b))
2315 assert!(a.is_disjoint(&c))
2316 assert!(b.is_disjoint(&a))
2317 assert!(b.is_disjoint(&c))
2318 assert!(c.is_disjoint(&a))
2319 assert!(c.is_disjoint(&b))
2323 fn test_bitv_set_union_with() {
2324 //a should grow to include larger elements
2325 let mut a = BitvSet::new();
2327 let mut b = BitvSet::new();
2329 let expected = BitvSet::from_bitv(from_bytes(&[0b10000100]));
2331 assert_eq!(a, expected);
2334 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2335 let mut b = BitvSet::from_bitv(from_bytes(&[0b01100010]));
2339 assert_eq!(a.len(), 4);
2340 assert_eq!(b.len(), 4);
2344 fn test_bitv_set_intersect_with() {
2345 // Explicitly 0'ed bits
2346 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2347 let mut b = BitvSet::from_bitv(from_bytes(&[0b00000000]));
2349 a.intersect_with(&b);
2350 b.intersect_with(&c);
2351 assert!(a.is_empty());
2352 assert!(b.is_empty());
2354 // Uninitialized bits should behave like 0's
2355 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2356 let mut b = BitvSet::new();
2358 a.intersect_with(&b);
2359 b.intersect_with(&c);
2360 assert!(a.is_empty());
2361 assert!(b.is_empty());
2364 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2365 let mut b = BitvSet::from_bitv(from_bytes(&[0b01100010]));
2367 a.intersect_with(&b);
2368 b.intersect_with(&c);
2369 assert_eq!(a.len(), 2);
2370 assert_eq!(b.len(), 2);
2374 fn test_bitv_set_difference_with() {
2375 // Explicitly 0'ed bits
2376 let mut a = BitvSet::from_bitv(from_bytes(&[0b00000000]));
2377 let b = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2378 a.difference_with(&b);
2379 assert!(a.is_empty());
2381 // Uninitialized bits should behave like 0's
2382 let mut a = BitvSet::new();
2383 let b = BitvSet::from_bitv(from_bytes(&[0b11111111]));
2384 a.difference_with(&b);
2385 assert!(a.is_empty());
2388 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2389 let mut b = BitvSet::from_bitv(from_bytes(&[0b01100010]));
2391 a.difference_with(&b);
2392 b.difference_with(&c);
2393 assert_eq!(a.len(), 1);
2394 assert_eq!(b.len(), 1);
2398 fn test_bitv_set_symmetric_difference_with() {
2399 //a should grow to include larger elements
2400 let mut a = BitvSet::new();
2403 let mut b = BitvSet::new();
2406 let expected = BitvSet::from_bitv(from_bytes(&[0b10000100]));
2407 a.symmetric_difference_with(&b);
2408 assert_eq!(a, expected);
2410 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2411 let b = BitvSet::new();
2413 a.symmetric_difference_with(&b);
2417 let mut a = BitvSet::from_bitv(from_bytes(&[0b11100010]));
2418 let mut b = BitvSet::from_bitv(from_bytes(&[0b01101010]));
2420 a.symmetric_difference_with(&b);
2421 b.symmetric_difference_with(&c);
2422 assert_eq!(a.len(), 2);
2423 assert_eq!(b.len(), 2);
2427 fn test_bitv_set_eq() {
2428 let a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2429 let b = BitvSet::from_bitv(from_bytes(&[0b00000000]));
2430 let c = BitvSet::new();
2441 fn test_bitv_set_cmp() {
2442 let a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2443 let b = BitvSet::from_bitv(from_bytes(&[0b00000000]));
2444 let c = BitvSet::new();
2446 assert_eq!(a.cmp(&b), Greater);
2447 assert_eq!(a.cmp(&c), Greater);
2448 assert_eq!(b.cmp(&a), Less);
2449 assert_eq!(b.cmp(&c), Equal);
2450 assert_eq!(c.cmp(&a), Less);
2451 assert_eq!(c.cmp(&b), Equal);
2455 fn test_bitv_remove() {
2456 let mut a = BitvSet::new();
2458 assert!(a.insert(1));
2459 assert!(a.remove(&1));
2461 assert!(a.insert(100));
2462 assert!(a.remove(&100));
2464 assert!(a.insert(1000));
2465 assert!(a.remove(&1000));
2467 assert_eq!(a.capacity(), u32::BITS);
2472 let mut a = Bitv::with_capacity(5u, false);
2473 let mut b = Bitv::with_capacity(5u, false);
2475 assert!(!(a < b) && !(b < a));
2481 assert!(!(a < b) && b < a);
2488 let mut a = Bitv::with_capacity(5u, false);
2489 let mut b = Bitv::with_capacity(5u, false);
2491 assert!(a <= b && a >= b);
2493 assert!(a > b && a >= b);
2494 assert!(b < a && b <= a);
2497 assert!(b > a && b >= a);
2498 assert!(a < b && a <= b);
2502 fn test_bitv_clone() {
2503 let mut a = BitvSet::new();
2505 assert!(a.insert(1));
2506 assert!(a.insert(100));
2507 assert!(a.insert(1000));
2509 let mut b = a.clone();
2513 assert!(b.remove(&1));
2514 assert!(a.contains(&1));
2516 assert!(a.remove(&1000));
2517 assert!(b.contains(&1000));
2521 fn test_small_bitv_tests() {
2522 let v = from_bytes(&[0]);
2527 let v = from_bytes(&[0b00010100]);
2532 let v = from_bytes(&[0xFF]);
2539 fn test_big_bitv_tests() {
2540 let v = from_bytes(&[ // 88 bits
2548 let v = from_bytes(&[ // 88 bits
2549 0, 0, 0b00010100, 0,
2550 0, 0, 0, 0b00110100,
2556 let v = from_bytes(&[ // 88 bits
2557 0xFF, 0xFF, 0xFF, 0xFF,
2558 0xFF, 0xFF, 0xFF, 0xFF,
2566 fn test_bitv_push_pop() {
2567 let mut s = Bitv::with_capacity(5 * u32::BITS - 2, false);
2568 assert_eq!(s.len(), 5 * u32::BITS - 2);
2569 assert_eq!(s.get(5 * u32::BITS - 3), false);
2572 assert_eq!(s.get(5 * u32::BITS - 2), true);
2573 assert_eq!(s.get(5 * u32::BITS - 1), true);
2574 // Here the internal vector will need to be extended
2576 assert_eq!(s.get(5 * u32::BITS), false);
2578 assert_eq!(s.get(5 * u32::BITS + 1), false);
2579 assert_eq!(s.len(), 5 * u32::BITS + 2);
2581 assert_eq!(s.pop(), false);
2582 assert_eq!(s.pop(), false);
2583 assert_eq!(s.pop(), true);
2584 assert_eq!(s.pop(), true);
2585 assert_eq!(s.len(), 5 * u32::BITS - 2);
2589 fn test_bitv_truncate() {
2590 let mut s = Bitv::with_capacity(5 * u32::BITS, true);
2592 assert_eq!(s, Bitv::with_capacity(5 * u32::BITS, true));
2593 assert_eq!(s.len(), 5 * u32::BITS);
2594 s.truncate(4 * u32::BITS);
2595 assert_eq!(s, Bitv::with_capacity(4 * u32::BITS, true));
2596 assert_eq!(s.len(), 4 * u32::BITS);
2597 // Truncating to a size > s.len() should be a noop
2598 s.truncate(5 * u32::BITS);
2599 assert_eq!(s, Bitv::with_capacity(4 * u32::BITS, true));
2600 assert_eq!(s.len(), 4 * u32::BITS);
2601 s.truncate(3 * u32::BITS - 10);
2602 assert_eq!(s, Bitv::with_capacity(3 * u32::BITS - 10, true));
2603 assert_eq!(s.len(), 3 * u32::BITS - 10);
2605 assert_eq!(s, Bitv::with_capacity(0, true));
2606 assert_eq!(s.len(), 0);
2610 fn test_bitv_reserve() {
2611 let mut s = Bitv::with_capacity(5 * u32::BITS, true);
2613 assert_eq!(s.capacity(), 5 * u32::BITS);
2614 s.reserve(2 * u32::BITS);
2615 assert_eq!(s.capacity(), 5 * u32::BITS);
2616 s.reserve(7 * u32::BITS);
2617 assert_eq!(s.capacity(), 7 * u32::BITS);
2618 s.reserve(7 * u32::BITS);
2619 assert_eq!(s.capacity(), 7 * u32::BITS);
2620 s.reserve(7 * u32::BITS + 1);
2621 assert_eq!(s.capacity(), 8 * u32::BITS);
2622 // Check that length hasn't changed
2623 assert_eq!(s.len(), 5 * u32::BITS);
2627 assert_eq!(s.get(5 * u32::BITS - 1), true);
2628 assert_eq!(s.get(5 * u32::BITS - 0), true);
2629 assert_eq!(s.get(5 * u32::BITS + 1), false);
2630 assert_eq!(s.get(5 * u32::BITS + 2), true);
2634 fn test_bitv_grow() {
2635 let mut bitv = from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
2636 bitv.grow(32, true);
2637 assert_eq!(bitv, from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2638 0xFF, 0xFF, 0xFF, 0xFF]));
2639 bitv.grow(64, false);
2640 assert_eq!(bitv, from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2641 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
2642 bitv.grow(16, true);
2643 assert_eq!(bitv, from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2644 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
2648 fn test_bitv_extend() {
2649 let mut bitv = from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2650 let ext = from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
2651 bitv.extend(ext.iter());
2652 assert_eq!(bitv, from_bytes(&[0b10110110, 0b00000000, 0b11111111,
2653 0b01001001, 0b10010010, 0b10111101]));
2657 fn test_bitv_set_show() {
2658 let mut s = BitvSet::new();
2663 assert_eq!("{1, 2, 10, 50}".to_string(), s.to_string());
2666 fn rng() -> rand::IsaacRng {
2667 let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
2668 rand::SeedableRng::from_seed(seed)
2672 fn bench_uint_small(b: &mut Bencher) {
2674 let mut bitv = 0 as uint;
2676 for _ in range(0u, 100) {
2677 bitv |= 1 << ((r.next_u32() as uint) % u32::BITS);
2684 fn bench_bitv_set_big_fixed(b: &mut Bencher) {
2686 let mut bitv = Bitv::with_capacity(BENCH_BITS, false);
2688 for _ in range(0u, 100) {
2689 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
2696 fn bench_bitv_set_big_variable(b: &mut Bencher) {
2698 let mut bitv = Bitv::with_capacity(BENCH_BITS, false);
2700 for _ in range(0u, 100) {
2701 bitv.set((r.next_u32() as uint) % BENCH_BITS, r.gen());
2708 fn bench_bitv_set_small(b: &mut Bencher) {
2710 let mut bitv = Bitv::with_capacity(u32::BITS, false);
2712 for _ in range(0u, 100) {
2713 bitv.set((r.next_u32() as uint) % u32::BITS, true);
2720 fn bench_bitvset_small(b: &mut Bencher) {
2722 let mut bitv = BitvSet::new();
2724 for _ in range(0u, 100) {
2725 bitv.insert((r.next_u32() as uint) % u32::BITS);
2732 fn bench_bitvset_big(b: &mut Bencher) {
2734 let mut bitv = BitvSet::new();
2736 for _ in range(0u, 100) {
2737 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
2744 fn bench_bitv_big_union(b: &mut Bencher) {
2745 let mut b1 = Bitv::with_capacity(BENCH_BITS, false);
2746 let b2 = Bitv::with_capacity(BENCH_BITS, false);
2753 fn bench_bitv_small_iter(b: &mut Bencher) {
2754 let bitv = Bitv::with_capacity(u32::BITS, false);
2757 for _ in range(0u, 10) {
2758 for pres in bitv.iter() {
2759 sum += pres as uint;
2767 fn bench_bitv_big_iter(b: &mut Bencher) {
2768 let bitv = Bitv::with_capacity(BENCH_BITS, false);
2771 for pres in bitv.iter() {
2772 sum += pres as uint;
2779 fn bench_bitvset_iter(b: &mut Bencher) {
2780 let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
2781 |idx| {idx % 3 == 0}));
2784 for idx in bitv.iter() {