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(&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<F>(&mut self, other: &Bitv, mut op: F) -> bool where F: FnMut(u32, u32) -> u32 {
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<F>(len: uint, mut f: F) -> Bitv where F: FnMut(uint) -> bool {
820 let mut bitv = Bitv::with_capacity(len, false);
821 for i in range(0u, len) {
828 impl Default for Bitv {
831 fn default() -> Bitv { Bitv::new() }
834 impl FromIterator<bool> for Bitv {
835 fn from_iter<I:Iterator<bool>>(iterator: I) -> Bitv {
836 let mut ret = Bitv::new();
837 ret.extend(iterator);
842 impl Extend<bool> for Bitv {
844 fn extend<I: Iterator<bool>>(&mut self, mut iterator: I) {
845 let (min, _) = iterator.size_hint();
846 let nbits = self.nbits;
847 self.reserve(nbits + min);
848 for element in iterator {
855 impl Clone for Bitv {
857 fn clone(&self) -> Bitv {
858 Bitv { storage: self.storage.clone(), nbits: self.nbits }
862 fn clone_from(&mut self, source: &Bitv) {
863 self.nbits = source.nbits;
864 self.storage.clone_from(&source.storage);
868 impl PartialOrd for Bitv {
870 fn partial_cmp(&self, other: &Bitv) -> Option<Ordering> {
871 iter::order::partial_cmp(self.iter(), other.iter())
877 fn cmp(&self, other: &Bitv) -> Ordering {
878 iter::order::cmp(self.iter(), other.iter())
882 impl fmt::Show for Bitv {
883 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
884 for bit in self.iter() {
885 try!(write!(fmt, "{}", if bit { 1u } else { 0u }));
891 impl<S: hash::Writer> hash::Hash<S> for Bitv {
892 fn hash(&self, state: &mut S) {
893 self.nbits.hash(state);
894 for (_, elem) in self.mask_words(0) {
900 impl cmp::PartialEq for Bitv {
902 fn eq(&self, other: &Bitv) -> bool {
903 if self.nbits != other.nbits {
906 self.mask_words(0).zip(other.mask_words(0)).all(|((_, w1), (_, w2))| w1 == w2)
910 impl cmp::Eq for Bitv {}
912 /// An iterator for `Bitv`.
913 pub struct Bits<'a> {
919 impl<'a> Iterator<bool> for Bits<'a> {
921 fn next(&mut self) -> Option<bool> {
922 if self.next_idx != self.end_idx {
923 let idx = self.next_idx;
925 Some(self.bitv.get(idx))
931 fn size_hint(&self) -> (uint, Option<uint>) {
932 let rem = self.end_idx - self.next_idx;
937 impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
939 fn next_back(&mut self) -> Option<bool> {
940 if self.next_idx != self.end_idx {
942 Some(self.bitv.get(self.end_idx))
949 impl<'a> ExactSizeIterator<bool> for Bits<'a> {}
951 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
953 fn indexable(&self) -> uint {
954 self.end_idx - self.next_idx
958 fn idx(&mut self, index: uint) -> Option<bool> {
959 if index >= self.indexable() {
962 Some(self.bitv.get(index))
967 /// An implementation of a set using a bit vector as an underlying
968 /// representation for holding unsigned numerical elements.
970 /// It should also be noted that the amount of storage necessary for holding a
971 /// set of objects is proportional to the maximum of the objects when viewed
977 /// use std::collections::{BitvSet, Bitv};
978 /// use std::collections::bitv;
980 /// // It's a regular set
981 /// let mut s = BitvSet::new();
988 /// if !s.contains(&7) {
989 /// println!("There is no 7");
992 /// // Can initialize from a `Bitv`
993 /// let other = BitvSet::from_bitv(bitv::from_bytes(&[0b11010000]));
995 /// s.union_with(&other);
997 /// // Print 0, 1, 3 in some order
998 /// for x in s.iter() {
999 /// println!("{}", x);
1002 /// // Can convert back to a `Bitv`
1003 /// let bv: Bitv = s.into_bitv();
1004 /// assert!(bv.get(3));
1007 pub struct BitvSet(Bitv);
1009 impl Default for BitvSet {
1011 fn default() -> BitvSet { BitvSet::new() }
1014 impl FromIterator<bool> for BitvSet {
1015 fn from_iter<I:Iterator<bool>>(iterator: I) -> BitvSet {
1016 let mut ret = BitvSet::new();
1017 ret.extend(iterator);
1022 impl Extend<bool> for BitvSet {
1024 fn extend<I: Iterator<bool>>(&mut self, iterator: I) {
1025 let &BitvSet(ref mut self_bitv) = self;
1026 self_bitv.extend(iterator);
1030 impl PartialOrd for BitvSet {
1032 fn partial_cmp(&self, other: &BitvSet) -> Option<Ordering> {
1033 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1034 iter::order::partial_cmp(a_iter, b_iter)
1038 impl Ord for BitvSet {
1040 fn cmp(&self, other: &BitvSet) -> Ordering {
1041 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1042 iter::order::cmp(a_iter, b_iter)
1046 impl cmp::PartialEq for BitvSet {
1048 fn eq(&self, other: &BitvSet) -> bool {
1049 let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
1050 iter::order::eq(a_iter, b_iter)
1054 impl cmp::Eq for BitvSet {}
1057 /// Creates a new bit vector set with initially no contents.
1062 /// use std::collections::BitvSet;
1063 /// let mut s = BitvSet::new();
1066 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1067 pub fn new() -> BitvSet {
1068 BitvSet(Bitv::new())
1071 /// Creates a new bit vector set with initially no contents, able to
1072 /// hold `nbits` elements without resizing.
1077 /// use std::collections::BitvSet;
1078 /// let mut s = BitvSet::with_capacity(100);
1079 /// assert!(s.capacity() >= 100);
1082 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1083 pub fn with_capacity(nbits: uint) -> BitvSet {
1084 let bitv = Bitv::with_capacity(nbits, false);
1085 BitvSet::from_bitv(bitv)
1088 /// Creates a new bit vector set from the given bit vector.
1093 /// use std::collections::{bitv, BitvSet};
1095 /// let bv = bitv::from_bytes(&[0b01100000]);
1096 /// let s = BitvSet::from_bitv(bv);
1098 /// // Print 1, 2 in arbitrary order
1099 /// for x in s.iter() {
1100 /// println!("{}", x);
1104 pub fn from_bitv(mut bitv: Bitv) -> BitvSet {
1105 // Mark every bit as valid
1106 bitv.nbits = bitv.capacity();
1110 /// Returns the capacity in bits for this bit vector. Inserting any
1111 /// element less than this amount will not trigger a resizing.
1116 /// use std::collections::BitvSet;
1118 /// let mut s = BitvSet::with_capacity(100);
1119 /// assert!(s.capacity() >= 100);
1122 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1123 pub fn capacity(&self) -> uint {
1124 let &BitvSet(ref bitv) = self;
1128 /// Grows the underlying vector to be able to store `size` bits.
1133 /// use std::collections::BitvSet;
1135 /// let mut s = BitvSet::new();
1137 /// assert!(s.capacity() >= 10);
1139 pub fn reserve(&mut self, size: uint) {
1140 let &BitvSet(ref mut bitv) = self;
1142 if bitv.nbits < size {
1143 bitv.nbits = bitv.capacity();
1147 /// Consumes this set to return the underlying bit vector.
1152 /// use std::collections::BitvSet;
1154 /// let mut s = BitvSet::new();
1158 /// let bv = s.into_bitv();
1159 /// assert!(bv.get(0));
1160 /// assert!(bv.get(3));
1163 pub fn into_bitv(self) -> Bitv {
1164 let BitvSet(bitv) = self;
1168 /// Returns a reference to the underlying bit vector.
1173 /// use std::collections::BitvSet;
1175 /// let mut s = BitvSet::new();
1178 /// let bv = s.get_ref();
1179 /// assert_eq!(bv[0], true);
1182 pub fn get_ref<'a>(&'a self) -> &'a Bitv {
1183 let &BitvSet(ref bitv) = self;
1188 fn other_op<F>(&mut self, other: &BitvSet, mut f: F) where F: FnMut(u32, u32) -> u32 {
1189 // Expand the vector if necessary
1190 self.reserve(other.capacity());
1193 let &BitvSet(ref mut self_bitv) = self;
1194 let &BitvSet(ref other_bitv) = other;
1196 // virtually pad other with 0's for equal lengths
1197 let mut other_words = {
1198 let (_, result) = match_words(self_bitv, other_bitv);
1202 // Apply values found in other
1203 for (i, w) in other_words {
1204 let old = self_bitv.storage[i];
1205 let new = f(old, w);
1206 self_bitv.storage[i] = new;
1210 /// Truncates the underlying vector to the least length required.
1215 /// use std::collections::BitvSet;
1217 /// let mut s = BitvSet::new();
1218 /// s.insert(32183231);
1219 /// s.remove(&32183231);
1221 /// // Internal storage will probably be bigger than necessary
1222 /// println!("old capacity: {}", s.capacity());
1224 /// // Now should be smaller
1225 /// s.shrink_to_fit();
1226 /// println!("new capacity: {}", s.capacity());
1229 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1230 pub fn shrink_to_fit(&mut self) {
1231 let &BitvSet(ref mut bitv) = self;
1232 // Obtain original length
1233 let old_len = bitv.storage.len();
1234 // Obtain coarse trailing zero length
1235 let n = bitv.storage.iter().rev().take_while(|&&n| n == 0).count();
1237 let trunc_len = cmp::max(old_len - n, 1);
1238 bitv.storage.truncate(trunc_len);
1239 bitv.nbits = trunc_len * u32::BITS;
1242 /// Iterator over each u32 stored in the `BitvSet`.
1247 /// use std::collections::BitvSet;
1248 /// use std::collections::bitv;
1250 /// let s = BitvSet::from_bitv(bitv::from_bytes(&[0b01001010]));
1252 /// // Print 1, 4, 6 in arbitrary order
1253 /// for x in s.iter() {
1254 /// println!("{}", x);
1258 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1259 pub fn iter<'a>(&'a self) -> BitPositions<'a> {
1260 BitPositions {set: self, next_idx: 0u}
1263 /// Iterator over each u32 stored in `self` union `other`.
1264 /// See [union_with](#method.union_with) for an efficient in-place version.
1269 /// use std::collections::BitvSet;
1270 /// use std::collections::bitv;
1272 /// let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000]));
1273 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000]));
1275 /// // Print 0, 1, 2, 4 in arbitrary order
1276 /// for x in a.union(&b) {
1277 /// println!("{}", x);
1281 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1282 pub fn union<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
1283 fn or(w1: u32, w2: u32) -> u32 { w1 | w2 }
1294 /// Iterator over each uint stored in `self` intersect `other`.
1295 /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
1300 /// use std::collections::BitvSet;
1301 /// use std::collections::bitv;
1303 /// let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000]));
1304 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000]));
1307 /// for x in a.intersection(&b) {
1308 /// println!("{}", x);
1312 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1313 pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Take<TwoBitPositions<'a>> {
1314 fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 }
1316 let min = cmp::min(self.capacity(), other.capacity());
1326 /// Iterator over each uint stored in the `self` setminus `other`.
1327 /// See [difference_with](#method.difference_with) for an efficient in-place version.
1332 /// use std::collections::BitvSet;
1333 /// use std::collections::bitv;
1335 /// let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000]));
1336 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000]));
1338 /// // Print 1, 4 in arbitrary order
1339 /// for x in a.difference(&b) {
1340 /// println!("{}", x);
1343 /// // Note that difference is not symmetric,
1344 /// // and `b - a` means something else.
1345 /// // This prints 0
1346 /// for x in b.difference(&a) {
1347 /// println!("{}", x);
1351 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1352 pub fn difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
1353 fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 }
1364 /// Iterator over each u32 stored in the symmetric difference of `self` and `other`.
1365 /// See [symmetric_difference_with](#method.symmetric_difference_with) for
1366 /// an efficient in-place version.
1371 /// use std::collections::BitvSet;
1372 /// use std::collections::bitv;
1374 /// let a = BitvSet::from_bitv(bitv::from_bytes(&[0b01101000]));
1375 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[0b10100000]));
1377 /// // Print 0, 1, 4 in arbitrary order
1378 /// for x in a.symmetric_difference(&b) {
1379 /// println!("{}", x);
1383 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1384 pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
1385 fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 }
1396 /// Unions in-place with the specified other bit vector.
1401 /// use std::collections::BitvSet;
1402 /// use std::collections::bitv;
1404 /// let a = 0b01101000;
1405 /// let b = 0b10100000;
1406 /// let res = 0b11101000;
1408 /// let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1409 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1410 /// let res = BitvSet::from_bitv(bitv::from_bytes(&[res]));
1412 /// a.union_with(&b);
1413 /// assert_eq!(a, res);
1416 pub fn union_with(&mut self, other: &BitvSet) {
1417 self.other_op(other, |w1, w2| w1 | w2);
1420 /// Intersects in-place with the specified other bit vector.
1425 /// use std::collections::BitvSet;
1426 /// use std::collections::bitv;
1428 /// let a = 0b01101000;
1429 /// let b = 0b10100000;
1430 /// let res = 0b00100000;
1432 /// let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1433 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1434 /// let res = BitvSet::from_bitv(bitv::from_bytes(&[res]));
1436 /// a.intersect_with(&b);
1437 /// assert_eq!(a, res);
1440 pub fn intersect_with(&mut self, other: &BitvSet) {
1441 self.other_op(other, |w1, w2| w1 & w2);
1444 /// Makes this bit vector the difference with the specified other bit vector
1450 /// use std::collections::BitvSet;
1451 /// use std::collections::bitv;
1453 /// let a = 0b01101000;
1454 /// let b = 0b10100000;
1455 /// let a_b = 0b01001000; // a - b
1456 /// let b_a = 0b10000000; // b - a
1458 /// let mut bva = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1459 /// let bvb = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1460 /// let bva_b = BitvSet::from_bitv(bitv::from_bytes(&[a_b]));
1461 /// let bvb_a = BitvSet::from_bitv(bitv::from_bytes(&[b_a]));
1463 /// bva.difference_with(&bvb);
1464 /// assert_eq!(bva, bva_b);
1466 /// let bva = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1467 /// let mut bvb = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1469 /// bvb.difference_with(&bva);
1470 /// assert_eq!(bvb, bvb_a);
1473 pub fn difference_with(&mut self, other: &BitvSet) {
1474 self.other_op(other, |w1, w2| w1 & !w2);
1477 /// Makes this bit vector the symmetric difference with the specified other
1478 /// bit vector in-place.
1483 /// use std::collections::BitvSet;
1484 /// use std::collections::bitv;
1486 /// let a = 0b01101000;
1487 /// let b = 0b10100000;
1488 /// let res = 0b11001000;
1490 /// let mut a = BitvSet::from_bitv(bitv::from_bytes(&[a]));
1491 /// let b = BitvSet::from_bitv(bitv::from_bytes(&[b]));
1492 /// let res = BitvSet::from_bitv(bitv::from_bytes(&[res]));
1494 /// a.symmetric_difference_with(&b);
1495 /// assert_eq!(a, res);
1498 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
1499 self.other_op(other, |w1, w2| w1 ^ w2);
1502 /// Return the number of set bits in this set.
1504 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1505 pub fn len(&self) -> uint {
1506 let &BitvSet(ref bitv) = self;
1507 bitv.storage.iter().fold(0, |acc, &n| acc + n.count_ones())
1510 /// Returns whether there are no bits set in this set
1512 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1513 pub fn is_empty(&self) -> bool {
1514 let &BitvSet(ref bitv) = self;
1515 bitv.storage.iter().all(|&n| n == 0)
1518 /// Clears all bits in this set
1520 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1521 pub fn clear(&mut self) {
1522 let &BitvSet(ref mut bitv) = self;
1526 /// Returns `true` if this set contains the specified integer.
1528 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1529 pub fn contains(&self, value: &uint) -> bool {
1530 let &BitvSet(ref bitv) = self;
1531 *value < bitv.nbits && bitv.get(*value)
1534 /// Returns `true` if the set has no elements in common with `other`.
1535 /// This is equivalent to checking for an empty intersection.
1537 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1538 pub fn is_disjoint(&self, other: &BitvSet) -> bool {
1539 self.intersection(other).next().is_none()
1542 /// Returns `true` if the set is a subset of another.
1544 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1545 pub fn is_subset(&self, other: &BitvSet) -> bool {
1546 let &BitvSet(ref self_bitv) = self;
1547 let &BitvSet(ref other_bitv) = other;
1549 // Check that `self` intersect `other` is self
1550 self_bitv.mask_words(0).zip(other_bitv.mask_words(0))
1551 .all(|((_, w1), (_, w2))| w1 & w2 == w1) &&
1552 // Check that `self` setminus `other` is empty
1553 self_bitv.mask_words(other_bitv.storage.len()).all(|(_, w)| w == 0)
1556 /// Returns `true` if the set is a superset of another.
1558 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1559 pub fn is_superset(&self, other: &BitvSet) -> bool {
1560 other.is_subset(self)
1563 /// Adds a value to the set. Returns `true` if the value was not already
1564 /// present in the set.
1565 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1566 pub fn insert(&mut self, value: uint) -> bool {
1567 if self.contains(&value) {
1571 // Ensure we have enough space to hold the new element
1572 if value >= self.capacity() {
1573 let new_cap = cmp::max(value + 1, self.capacity() * 2);
1574 self.reserve(new_cap);
1577 let &BitvSet(ref mut bitv) = self;
1578 bitv.set(value, true);
1582 /// Removes a value from the set. Returns `true` if the value was
1583 /// present in the set.
1584 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1585 pub fn remove(&mut self, value: &uint) -> bool {
1586 if !self.contains(value) {
1589 let &BitvSet(ref mut bitv) = self;
1590 bitv.set(*value, false);
1595 impl fmt::Show for BitvSet {
1596 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
1597 try!(write!(fmt, "{{"));
1598 let mut first = true;
1599 for n in self.iter() {
1601 try!(write!(fmt, ", "));
1603 try!(write!(fmt, "{}", n));
1610 impl<S: hash::Writer> hash::Hash<S> for BitvSet {
1611 fn hash(&self, state: &mut S) {
1612 for pos in self.iter() {
1618 /// An iterator for `BitvSet`.
1619 pub struct BitPositions<'a> {
1624 /// An iterator combining two `BitvSet` iterators.
1625 pub struct TwoBitPositions<'a> {
1628 merge: fn(u32, u32) -> u32,
1633 impl<'a> Iterator<uint> for BitPositions<'a> {
1634 fn next(&mut self) -> Option<uint> {
1635 while self.next_idx < self.set.capacity() {
1636 let idx = self.next_idx;
1639 if self.set.contains(&idx) {
1648 fn size_hint(&self) -> (uint, Option<uint>) {
1649 (0, Some(self.set.capacity() - self.next_idx))
1653 impl<'a> Iterator<uint> for TwoBitPositions<'a> {
1654 fn next(&mut self) -> Option<uint> {
1655 while self.next_idx < self.set.capacity() ||
1656 self.next_idx < self.other.capacity() {
1657 let bit_idx = self.next_idx % u32::BITS;
1659 let &BitvSet(ref s_bitv) = self.set;
1660 let &BitvSet(ref o_bitv) = self.other;
1661 // Merging the two words is a bit of an awkward dance since
1662 // one Bitv might be longer than the other
1663 let word_idx = self.next_idx / u32::BITS;
1664 let w1 = if word_idx < s_bitv.storage.len() {
1665 s_bitv.storage[word_idx]
1667 let w2 = if word_idx < o_bitv.storage.len() {
1668 o_bitv.storage[word_idx]
1670 self.current_word = (self.merge)(w1, w2);
1674 if self.current_word & (1 << bit_idx) != 0 {
1675 return Some(self.next_idx - 1);
1682 fn size_hint(&self) -> (uint, Option<uint>) {
1683 let cap = cmp::max(self.set.capacity(), self.other.capacity());
1684 (0, Some(cap - self.next_idx))
1691 use core::iter::range_step;
1695 use test::{Bencher, black_box};
1697 use super::{Bitv, BitvSet, from_fn, from_bytes};
1700 static BENCH_BITS : uint = 1 << 14;
1704 let zerolen = Bitv::new();
1705 assert_eq!(zerolen.to_string(), "");
1707 let eightbits = Bitv::with_capacity(8u, false);
1708 assert_eq!(eightbits.to_string(), "00000000")
1712 fn test_0_elements() {
1713 let act = Bitv::new();
1714 let exp = Vec::from_elem(0u, false);
1715 assert!(act.eq_vec(exp.as_slice()));
1719 fn test_1_element() {
1720 let mut act = Bitv::with_capacity(1u, false);
1721 assert!(act.eq_vec(&[false]));
1722 act = Bitv::with_capacity(1u, true);
1723 assert!(act.eq_vec(&[true]));
1727 fn test_2_elements() {
1728 let mut b = bitv::Bitv::with_capacity(2, false);
1731 assert_eq!(b.to_string(), "10");
1735 fn test_10_elements() {
1739 act = Bitv::with_capacity(10u, false);
1740 assert!((act.eq_vec(
1741 &[false, false, false, false, false, false, false, false, false, false])));
1744 act = Bitv::with_capacity(10u, true);
1745 assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
1748 act = Bitv::with_capacity(10u, false);
1754 assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
1757 act = Bitv::with_capacity(10u, false);
1763 assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
1766 act = Bitv::with_capacity(10u, false);
1771 assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
1775 fn test_31_elements() {
1779 act = Bitv::with_capacity(31u, false);
1781 &[false, false, false, false, false, false, false, false, false, false, false,
1782 false, false, false, false, false, false, false, false, false, false, false,
1783 false, false, false, false, false, false, false, false, false]));
1786 act = Bitv::with_capacity(31u, true);
1788 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1789 true, true, true, true, true, true, true, true, true, true, true, true, true,
1790 true, true, true, true, true]));
1793 act = Bitv::with_capacity(31u, false);
1803 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1804 false, false, false, false, false, false, false, false, false, false, false,
1805 false, false, false, false, false, false, false]));
1808 act = Bitv::with_capacity(31u, false);
1818 &[false, false, false, false, false, false, false, false, false, false, false,
1819 false, false, false, false, false, true, true, true, true, true, true, true, true,
1820 false, false, false, false, false, false, false]));
1823 act = Bitv::with_capacity(31u, false);
1832 &[false, false, false, false, false, false, false, false, false, false, false,
1833 false, false, false, false, false, false, false, false, false, false, false,
1834 false, false, true, true, true, true, true, true, true]));
1837 act = Bitv::with_capacity(31u, false);
1842 &[false, false, false, true, false, false, false, false, false, false, false, false,
1843 false, false, false, false, false, true, false, false, false, false, false, false,
1844 false, false, false, false, false, false, true]));
1848 fn test_32_elements() {
1852 act = Bitv::with_capacity(32u, false);
1854 &[false, false, false, false, false, false, false, false, false, false, false,
1855 false, false, false, false, false, false, false, false, false, false, false,
1856 false, false, false, false, false, false, false, false, false, false]));
1859 act = Bitv::with_capacity(32u, true);
1861 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1862 true, true, true, true, true, true, true, true, true, true, true, true, true,
1863 true, true, true, true, true, true]));
1866 act = Bitv::with_capacity(32u, false);
1876 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1877 false, false, false, false, false, false, false, false, false, false, false,
1878 false, false, false, false, false, false, false, false]));
1881 act = Bitv::with_capacity(32u, false);
1891 &[false, false, false, false, false, false, false, false, false, false, false,
1892 false, false, false, false, false, true, true, true, true, true, true, true, true,
1893 false, false, false, false, false, false, false, false]));
1896 act = Bitv::with_capacity(32u, false);
1906 &[false, false, false, false, false, false, false, false, false, false, false,
1907 false, false, false, false, false, false, false, false, false, false, false,
1908 false, false, true, true, true, true, true, true, true, true]));
1911 act = Bitv::with_capacity(32u, false);
1917 &[false, false, false, true, false, false, false, false, false, false, false, false,
1918 false, false, false, false, false, true, false, false, false, false, false, false,
1919 false, false, false, false, false, false, true, true]));
1923 fn test_33_elements() {
1927 act = Bitv::with_capacity(33u, false);
1929 &[false, false, false, false, false, false, false, false, false, false, false,
1930 false, false, false, false, false, false, false, false, false, false, false,
1931 false, false, false, false, false, false, false, false, false, false, false]));
1934 act = Bitv::with_capacity(33u, true);
1936 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1937 true, true, true, true, true, true, true, true, true, true, true, true, true,
1938 true, true, true, true, true, true, true]));
1941 act = Bitv::with_capacity(33u, false);
1951 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1952 false, false, false, false, false, false, false, false, false, false, false,
1953 false, false, false, false, false, false, false, false, false]));
1956 act = Bitv::with_capacity(33u, false);
1966 &[false, false, false, false, false, false, false, false, false, false, false,
1967 false, false, false, false, false, true, true, true, true, true, true, true, true,
1968 false, false, false, false, false, false, false, false, false]));
1971 act = Bitv::with_capacity(33u, false);
1981 &[false, false, false, false, false, false, false, false, false, false, false,
1982 false, false, false, false, false, false, false, false, false, false, false,
1983 false, false, true, true, true, true, true, true, true, true, false]));
1986 act = Bitv::with_capacity(33u, false);
1993 &[false, false, false, true, false, false, false, false, false, false, false, false,
1994 false, false, false, false, false, true, false, false, false, false, false, false,
1995 false, false, false, false, false, false, true, true, true]));
1999 fn test_equal_differing_sizes() {
2000 let v0 = Bitv::with_capacity(10u, false);
2001 let v1 = Bitv::with_capacity(11u, false);
2006 fn test_equal_greatly_differing_sizes() {
2007 let v0 = Bitv::with_capacity(10u, false);
2008 let v1 = Bitv::with_capacity(110u, false);
2013 fn test_equal_sneaky_small() {
2014 let mut a = bitv::Bitv::with_capacity(1, false);
2017 let mut b = bitv::Bitv::with_capacity(1, true);
2024 fn test_equal_sneaky_big() {
2025 let mut a = bitv::Bitv::with_capacity(100, false);
2026 for i in range(0u, 100) {
2030 let mut b = bitv::Bitv::with_capacity(100, true);
2031 for i in range(0u, 100) {
2039 fn test_from_bytes() {
2040 let bitv = from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2041 let str = concat!("10110110", "00000000", "11111111");
2042 assert_eq!(bitv.to_string(), str);
2046 fn test_to_bytes() {
2047 let mut bv = Bitv::with_capacity(3, true);
2049 assert_eq!(bv.to_bytes(), vec!(0b10100000));
2051 let mut bv = Bitv::with_capacity(9, false);
2054 assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
2058 fn test_from_bools() {
2059 let bools = vec![true, false, true, true];
2060 let bitv: Bitv = bools.iter().map(|n| *n).collect();
2061 assert_eq!(bitv.to_string(), "1011");
2065 fn test_bitv_set_from_bools() {
2066 let bools = vec![true, false, true, true];
2067 let a: BitvSet = bools.iter().map(|n| *n).collect();
2068 let mut b = BitvSet::new();
2076 fn test_to_bools() {
2077 let bools = vec!(false, false, true, false, false, true, true, false);
2078 assert_eq!(from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
2082 fn test_bitv_iterator() {
2083 let bools = vec![true, false, true, true];
2084 let bitv: Bitv = bools.iter().map(|n| *n).collect();
2086 assert_eq!(bitv.iter().collect::<Vec<bool>>(), bools);
2088 let long = Vec::from_fn(10000, |i| i % 2 == 0);
2089 let bitv: Bitv = long.iter().map(|n| *n).collect();
2090 assert_eq!(bitv.iter().collect::<Vec<bool>>(), long)
2094 fn test_bitv_set_iterator() {
2095 let bools = [true, false, true, true];
2096 let bitv: BitvSet = bools.iter().map(|n| *n).collect();
2098 let idxs: Vec<uint> = bitv.iter().collect();
2099 assert_eq!(idxs, vec!(0, 2, 3));
2101 let long: BitvSet = range(0u, 10000).map(|n| n % 2 == 0).collect();
2102 let real = range_step(0, 10000, 2).collect::<Vec<uint>>();
2104 let idxs: Vec<uint> = long.iter().collect();
2105 assert_eq!(idxs, real);
2109 fn test_bitv_set_frombitv_init() {
2110 let bools = [true, false];
2111 let lengths = [10, 64, 100];
2112 for &b in bools.iter() {
2113 for &l in lengths.iter() {
2114 let bitset = BitvSet::from_bitv(Bitv::with_capacity(l, b));
2115 assert_eq!(bitset.contains(&1u), b);
2116 assert_eq!(bitset.contains(&(l-1u)), b);
2117 assert!(!bitset.contains(&l))
2123 fn test_small_difference() {
2124 let mut b1 = Bitv::with_capacity(3, false);
2125 let mut b2 = Bitv::with_capacity(3, false);
2130 assert!(b1.difference(&b2));
2132 assert!(!b1.get(1));
2133 assert!(!b1.get(2));
2137 fn test_big_difference() {
2138 let mut b1 = Bitv::with_capacity(100, false);
2139 let mut b2 = Bitv::with_capacity(100, false);
2144 assert!(b1.difference(&b2));
2146 assert!(!b1.get(40));
2147 assert!(!b1.get(80));
2151 fn test_small_clear() {
2152 let mut b = Bitv::with_capacity(14, true);
2158 fn test_big_clear() {
2159 let mut b = Bitv::with_capacity(140, true);
2165 fn test_bitv_masking() {
2166 let b = Bitv::with_capacity(140, true);
2167 let mut bs = BitvSet::from_bitv(b);
2168 assert!(bs.contains(&139));
2169 assert!(!bs.contains(&140));
2170 assert!(bs.insert(150));
2171 assert!(!bs.contains(&140));
2172 assert!(!bs.contains(&149));
2173 assert!(bs.contains(&150));
2174 assert!(!bs.contains(&151));
2178 fn test_bitv_set_basic() {
2179 // calculate nbits with u32::BITS granularity
2180 fn calc_nbits(bits: uint) -> uint {
2181 u32::BITS * ((bits + u32::BITS - 1) / u32::BITS)
2184 let mut b = BitvSet::new();
2185 assert_eq!(b.capacity(), calc_nbits(0));
2186 assert!(b.insert(3));
2187 assert_eq!(b.capacity(), calc_nbits(3));
2188 assert!(!b.insert(3));
2189 assert!(b.contains(&3));
2190 assert!(b.insert(4));
2191 assert!(!b.insert(4));
2192 assert!(b.contains(&3));
2193 assert!(b.insert(400));
2194 assert_eq!(b.capacity(), calc_nbits(400));
2195 assert!(!b.insert(400));
2196 assert!(b.contains(&400));
2197 assert_eq!(b.len(), 3);
2201 fn test_bitv_set_intersection() {
2202 let mut a = BitvSet::new();
2203 let mut b = BitvSet::new();
2205 assert!(a.insert(11));
2206 assert!(a.insert(1));
2207 assert!(a.insert(3));
2208 assert!(a.insert(77));
2209 assert!(a.insert(103));
2210 assert!(a.insert(5));
2212 assert!(b.insert(2));
2213 assert!(b.insert(11));
2214 assert!(b.insert(77));
2215 assert!(b.insert(5));
2216 assert!(b.insert(3));
2218 let expected = [3, 5, 11, 77];
2219 let actual = a.intersection(&b).collect::<Vec<uint>>();
2220 assert_eq!(actual, expected);
2224 fn test_bitv_set_difference() {
2225 let mut a = BitvSet::new();
2226 let mut b = BitvSet::new();
2228 assert!(a.insert(1));
2229 assert!(a.insert(3));
2230 assert!(a.insert(5));
2231 assert!(a.insert(200));
2232 assert!(a.insert(500));
2234 assert!(b.insert(3));
2235 assert!(b.insert(200));
2237 let expected = [1, 5, 500];
2238 let actual = a.difference(&b).collect::<Vec<uint>>();
2239 assert_eq!(actual, expected);
2243 fn test_bitv_set_symmetric_difference() {
2244 let mut a = BitvSet::new();
2245 let mut b = BitvSet::new();
2247 assert!(a.insert(1));
2248 assert!(a.insert(3));
2249 assert!(a.insert(5));
2250 assert!(a.insert(9));
2251 assert!(a.insert(11));
2253 assert!(b.insert(3));
2254 assert!(b.insert(9));
2255 assert!(b.insert(14));
2256 assert!(b.insert(220));
2258 let expected = [1, 5, 11, 14, 220];
2259 let actual = a.symmetric_difference(&b).collect::<Vec<uint>>();
2260 assert_eq!(actual, expected);
2264 fn test_bitv_set_union() {
2265 let mut a = BitvSet::new();
2266 let mut b = BitvSet::new();
2267 assert!(a.insert(1));
2268 assert!(a.insert(3));
2269 assert!(a.insert(5));
2270 assert!(a.insert(9));
2271 assert!(a.insert(11));
2272 assert!(a.insert(160));
2273 assert!(a.insert(19));
2274 assert!(a.insert(24));
2275 assert!(a.insert(200));
2277 assert!(b.insert(1));
2278 assert!(b.insert(5));
2279 assert!(b.insert(9));
2280 assert!(b.insert(13));
2281 assert!(b.insert(19));
2283 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
2284 let actual = a.union(&b).collect::<Vec<uint>>();
2285 assert_eq!(actual, expected);
2289 fn test_bitv_set_subset() {
2290 let mut set1 = BitvSet::new();
2291 let mut set2 = BitvSet::new();
2293 assert!(set1.is_subset(&set2)); // {} {}
2295 assert!(set1.is_subset(&set2)); // {} { 1 }
2297 assert!(set1.is_subset(&set2)); // {} { 1, 2 }
2299 assert!(set1.is_subset(&set2)); // { 2 } { 1, 2 }
2301 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 1, 2 }
2303 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3 }
2305 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3, 4 }
2307 assert!(set1.is_subset(&set2)); // { 2, 3 } { 2, 3, 4 }
2309 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 2, 4 }
2311 assert!(set1.is_subset(&set2)); // { 2 } { 2, 4 }
2315 fn test_bitv_set_is_disjoint() {
2316 let a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2317 let b = BitvSet::from_bitv(from_bytes(&[0b01000000]));
2318 let c = BitvSet::new();
2319 let d = BitvSet::from_bitv(from_bytes(&[0b00110000]));
2321 assert!(!a.is_disjoint(&d));
2322 assert!(!d.is_disjoint(&a));
2324 assert!(a.is_disjoint(&b));
2325 assert!(a.is_disjoint(&c));
2326 assert!(b.is_disjoint(&a));
2327 assert!(b.is_disjoint(&c));
2328 assert!(c.is_disjoint(&a));
2329 assert!(c.is_disjoint(&b));
2333 fn test_bitv_set_union_with() {
2334 //a should grow to include larger elements
2335 let mut a = BitvSet::new();
2337 let mut b = BitvSet::new();
2339 let expected = BitvSet::from_bitv(from_bytes(&[0b10000100]));
2341 assert_eq!(a, expected);
2344 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2345 let mut b = BitvSet::from_bitv(from_bytes(&[0b01100010]));
2349 assert_eq!(a.len(), 4);
2350 assert_eq!(b.len(), 4);
2354 fn test_bitv_set_intersect_with() {
2355 // Explicitly 0'ed bits
2356 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2357 let mut b = BitvSet::from_bitv(from_bytes(&[0b00000000]));
2359 a.intersect_with(&b);
2360 b.intersect_with(&c);
2361 assert!(a.is_empty());
2362 assert!(b.is_empty());
2364 // Uninitialized bits should behave like 0's
2365 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2366 let mut b = BitvSet::new();
2368 a.intersect_with(&b);
2369 b.intersect_with(&c);
2370 assert!(a.is_empty());
2371 assert!(b.is_empty());
2374 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2375 let mut b = BitvSet::from_bitv(from_bytes(&[0b01100010]));
2377 a.intersect_with(&b);
2378 b.intersect_with(&c);
2379 assert_eq!(a.len(), 2);
2380 assert_eq!(b.len(), 2);
2384 fn test_bitv_set_difference_with() {
2385 // Explicitly 0'ed bits
2386 let mut a = BitvSet::from_bitv(from_bytes(&[0b00000000]));
2387 let b = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2388 a.difference_with(&b);
2389 assert!(a.is_empty());
2391 // Uninitialized bits should behave like 0's
2392 let mut a = BitvSet::new();
2393 let b = BitvSet::from_bitv(from_bytes(&[0b11111111]));
2394 a.difference_with(&b);
2395 assert!(a.is_empty());
2398 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2399 let mut b = BitvSet::from_bitv(from_bytes(&[0b01100010]));
2401 a.difference_with(&b);
2402 b.difference_with(&c);
2403 assert_eq!(a.len(), 1);
2404 assert_eq!(b.len(), 1);
2408 fn test_bitv_set_symmetric_difference_with() {
2409 //a should grow to include larger elements
2410 let mut a = BitvSet::new();
2413 let mut b = BitvSet::new();
2416 let expected = BitvSet::from_bitv(from_bytes(&[0b10000100]));
2417 a.symmetric_difference_with(&b);
2418 assert_eq!(a, expected);
2420 let mut a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2421 let b = BitvSet::new();
2423 a.symmetric_difference_with(&b);
2427 let mut a = BitvSet::from_bitv(from_bytes(&[0b11100010]));
2428 let mut b = BitvSet::from_bitv(from_bytes(&[0b01101010]));
2430 a.symmetric_difference_with(&b);
2431 b.symmetric_difference_with(&c);
2432 assert_eq!(a.len(), 2);
2433 assert_eq!(b.len(), 2);
2437 fn test_bitv_set_eq() {
2438 let a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2439 let b = BitvSet::from_bitv(from_bytes(&[0b00000000]));
2440 let c = BitvSet::new();
2451 fn test_bitv_set_cmp() {
2452 let a = BitvSet::from_bitv(from_bytes(&[0b10100010]));
2453 let b = BitvSet::from_bitv(from_bytes(&[0b00000000]));
2454 let c = BitvSet::new();
2456 assert_eq!(a.cmp(&b), Greater);
2457 assert_eq!(a.cmp(&c), Greater);
2458 assert_eq!(b.cmp(&a), Less);
2459 assert_eq!(b.cmp(&c), Equal);
2460 assert_eq!(c.cmp(&a), Less);
2461 assert_eq!(c.cmp(&b), Equal);
2465 fn test_bitv_remove() {
2466 let mut a = BitvSet::new();
2468 assert!(a.insert(1));
2469 assert!(a.remove(&1));
2471 assert!(a.insert(100));
2472 assert!(a.remove(&100));
2474 assert!(a.insert(1000));
2475 assert!(a.remove(&1000));
2477 assert_eq!(a.capacity(), u32::BITS);
2482 let mut a = Bitv::with_capacity(5u, false);
2483 let mut b = Bitv::with_capacity(5u, false);
2485 assert!(!(a < b) && !(b < a));
2491 assert!(!(a < b) && b < a);
2498 let mut a = Bitv::with_capacity(5u, false);
2499 let mut b = Bitv::with_capacity(5u, false);
2501 assert!(a <= b && a >= b);
2503 assert!(a > b && a >= b);
2504 assert!(b < a && b <= a);
2507 assert!(b > a && b >= a);
2508 assert!(a < b && a <= b);
2512 fn test_bitv_clone() {
2513 let mut a = BitvSet::new();
2515 assert!(a.insert(1));
2516 assert!(a.insert(100));
2517 assert!(a.insert(1000));
2519 let mut b = a.clone();
2523 assert!(b.remove(&1));
2524 assert!(a.contains(&1));
2526 assert!(a.remove(&1000));
2527 assert!(b.contains(&1000));
2531 fn test_small_bitv_tests() {
2532 let v = from_bytes(&[0]);
2537 let v = from_bytes(&[0b00010100]);
2542 let v = from_bytes(&[0xFF]);
2549 fn test_big_bitv_tests() {
2550 let v = from_bytes(&[ // 88 bits
2558 let v = from_bytes(&[ // 88 bits
2559 0, 0, 0b00010100, 0,
2560 0, 0, 0, 0b00110100,
2566 let v = from_bytes(&[ // 88 bits
2567 0xFF, 0xFF, 0xFF, 0xFF,
2568 0xFF, 0xFF, 0xFF, 0xFF,
2576 fn test_bitv_push_pop() {
2577 let mut s = Bitv::with_capacity(5 * u32::BITS - 2, false);
2578 assert_eq!(s.len(), 5 * u32::BITS - 2);
2579 assert_eq!(s.get(5 * u32::BITS - 3), false);
2582 assert_eq!(s.get(5 * u32::BITS - 2), true);
2583 assert_eq!(s.get(5 * u32::BITS - 1), true);
2584 // Here the internal vector will need to be extended
2586 assert_eq!(s.get(5 * u32::BITS), false);
2588 assert_eq!(s.get(5 * u32::BITS + 1), false);
2589 assert_eq!(s.len(), 5 * u32::BITS + 2);
2591 assert_eq!(s.pop(), false);
2592 assert_eq!(s.pop(), false);
2593 assert_eq!(s.pop(), true);
2594 assert_eq!(s.pop(), true);
2595 assert_eq!(s.len(), 5 * u32::BITS - 2);
2599 fn test_bitv_truncate() {
2600 let mut s = Bitv::with_capacity(5 * u32::BITS, true);
2602 assert_eq!(s, Bitv::with_capacity(5 * u32::BITS, true));
2603 assert_eq!(s.len(), 5 * u32::BITS);
2604 s.truncate(4 * u32::BITS);
2605 assert_eq!(s, Bitv::with_capacity(4 * u32::BITS, true));
2606 assert_eq!(s.len(), 4 * u32::BITS);
2607 // Truncating to a size > s.len() should be a noop
2608 s.truncate(5 * u32::BITS);
2609 assert_eq!(s, Bitv::with_capacity(4 * u32::BITS, true));
2610 assert_eq!(s.len(), 4 * u32::BITS);
2611 s.truncate(3 * u32::BITS - 10);
2612 assert_eq!(s, Bitv::with_capacity(3 * u32::BITS - 10, true));
2613 assert_eq!(s.len(), 3 * u32::BITS - 10);
2615 assert_eq!(s, Bitv::with_capacity(0, true));
2616 assert_eq!(s.len(), 0);
2620 fn test_bitv_reserve() {
2621 let mut s = Bitv::with_capacity(5 * u32::BITS, true);
2623 assert_eq!(s.capacity(), 5 * u32::BITS);
2624 s.reserve(2 * u32::BITS);
2625 assert_eq!(s.capacity(), 5 * u32::BITS);
2626 s.reserve(7 * u32::BITS);
2627 assert_eq!(s.capacity(), 7 * u32::BITS);
2628 s.reserve(7 * u32::BITS);
2629 assert_eq!(s.capacity(), 7 * u32::BITS);
2630 s.reserve(7 * u32::BITS + 1);
2631 assert_eq!(s.capacity(), 8 * u32::BITS);
2632 // Check that length hasn't changed
2633 assert_eq!(s.len(), 5 * u32::BITS);
2637 assert_eq!(s.get(5 * u32::BITS - 1), true);
2638 assert_eq!(s.get(5 * u32::BITS - 0), true);
2639 assert_eq!(s.get(5 * u32::BITS + 1), false);
2640 assert_eq!(s.get(5 * u32::BITS + 2), true);
2644 fn test_bitv_grow() {
2645 let mut bitv = from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
2646 bitv.grow(32, true);
2647 assert_eq!(bitv, from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2648 0xFF, 0xFF, 0xFF, 0xFF]));
2649 bitv.grow(64, false);
2650 assert_eq!(bitv, from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2651 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
2652 bitv.grow(16, true);
2653 assert_eq!(bitv, from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2654 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
2658 fn test_bitv_extend() {
2659 let mut bitv = from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2660 let ext = from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
2661 bitv.extend(ext.iter());
2662 assert_eq!(bitv, from_bytes(&[0b10110110, 0b00000000, 0b11111111,
2663 0b01001001, 0b10010010, 0b10111101]));
2667 fn test_bitv_set_show() {
2668 let mut s = BitvSet::new();
2673 assert_eq!("{1, 2, 10, 50}", s.to_string());
2676 fn rng() -> rand::IsaacRng {
2677 let seed: &[_] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
2678 rand::SeedableRng::from_seed(seed)
2682 fn bench_uint_small(b: &mut Bencher) {
2684 let mut bitv = 0 as uint;
2686 for _ in range(0u, 100) {
2687 bitv |= 1 << ((r.next_u32() as uint) % u32::BITS);
2694 fn bench_bitv_set_big_fixed(b: &mut Bencher) {
2696 let mut bitv = Bitv::with_capacity(BENCH_BITS, false);
2698 for _ in range(0u, 100) {
2699 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
2706 fn bench_bitv_set_big_variable(b: &mut Bencher) {
2708 let mut bitv = Bitv::with_capacity(BENCH_BITS, false);
2710 for _ in range(0u, 100) {
2711 bitv.set((r.next_u32() as uint) % BENCH_BITS, r.gen());
2718 fn bench_bitv_set_small(b: &mut Bencher) {
2720 let mut bitv = Bitv::with_capacity(u32::BITS, false);
2722 for _ in range(0u, 100) {
2723 bitv.set((r.next_u32() as uint) % u32::BITS, true);
2730 fn bench_bitvset_small(b: &mut Bencher) {
2732 let mut bitv = BitvSet::new();
2734 for _ in range(0u, 100) {
2735 bitv.insert((r.next_u32() as uint) % u32::BITS);
2742 fn bench_bitvset_big(b: &mut Bencher) {
2744 let mut bitv = BitvSet::new();
2746 for _ in range(0u, 100) {
2747 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
2754 fn bench_bitv_big_union(b: &mut Bencher) {
2755 let mut b1 = Bitv::with_capacity(BENCH_BITS, false);
2756 let b2 = Bitv::with_capacity(BENCH_BITS, false);
2763 fn bench_bitv_small_iter(b: &mut Bencher) {
2764 let bitv = Bitv::with_capacity(u32::BITS, false);
2767 for _ in range(0u, 10) {
2768 for pres in bitv.iter() {
2769 sum += pres as uint;
2777 fn bench_bitv_big_iter(b: &mut Bencher) {
2778 let bitv = Bitv::with_capacity(BENCH_BITS, false);
2781 for pres in bitv.iter() {
2782 sum += pres as uint;
2789 fn bench_bitvset_iter(b: &mut Bencher) {
2790 let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
2791 |idx| {idx % 3 == 0}));
2794 for idx in bitv.iter() {