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 #![allow(missing_doc)]
16 use core::default::Default;
23 use {Collection, Mutable, Set, MutableSet};
30 static TRUE: bool = true;
33 static FALSE: bool = false;
37 /// only the lowest nbits of this value are used. the rest is undefined.
47 enum BitvVariant { Big(BigBitv), Small(SmallBitv) }
49 /// The bitvector type
54 /// use collections::bitv::Bitv;
56 /// let mut bv = Bitv::with_capacity(10, false);
58 /// // insert all primes less than 10
63 /// println!("{}", bv.to_string());
64 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
66 /// // flip all values in bitvector, producing non-primes less than 10
68 /// println!("{}", bv.to_string());
69 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
71 /// // reset bitvector to empty
73 /// println!("{}", bv.to_string());
74 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
77 /// Internal representation of the bit vector
79 /// The number of valid bits in the internal representation
84 impl Index<uint,bool> for Bitv {
86 fn index<'a>(&'a self, i: &uint) -> &'a bool {
95 struct MaskWords<'a> {
96 iter: slice::Items<'a, uint>,
97 next_word: Option<&'a uint>,
102 impl<'a> Iterator<(uint, uint)> for MaskWords<'a> {
103 /// Returns (offset, word)
105 fn next<'a>(&'a mut self) -> Option<(uint, uint)> {
106 let ret = self.next_word;
109 self.next_word = self.iter.next();
111 // The last word may need to be masked
112 if self.next_word.is_none() {
113 Some((self.offset - 1, w & self.last_word_mask))
115 Some((self.offset - 1, w))
125 fn process(&mut self, other: &Bitv, op: |uint, uint| -> uint) -> bool {
126 let len = other.storage.len();
127 assert_eq!(self.storage.len(), len);
128 let mut changed = false;
129 // Notice: `a` is *not* masked here, which is fine as long as
130 // `op` is a bitwise operation, since any bits that should've
131 // been masked were fine to change anyway. `b` is masked to
132 // make sure its unmasked bits do not cause damage.
133 for (a, (_, b)) in self.storage.mut_iter()
134 .zip(other.mask_words(0)) {
145 fn mask_words<'a>(&'a self, mut start: uint) -> MaskWords<'a> {
146 if start > self.storage.len() {
147 start = self.storage.len();
149 let mut iter = self.storage.slice_from(start).iter();
151 next_word: iter.next(),
154 let rem = self.nbits % uint::BITS;
163 /// Creates an empty Bitv
164 pub fn new() -> Bitv {
165 Bitv { storage: Vec::new(), nbits: 0 }
168 /// Creates a Bitv that holds `nbits` elements, setting each element
170 pub fn with_capacity(nbits: uint, init: bool) -> Bitv {
172 storage: Vec::from_elem((nbits + uint::BITS - 1) / uint::BITS,
173 if init { !0u } else { 0u }),
179 * Calculates the union of two bitvectors
181 * Sets `self` to the union of `self` and `v1`. Both bitvectors must be
182 * the same length. Returns `true` if `self` changed.
185 pub fn union(&mut self, other: &Bitv) -> bool {
186 self.process(other, |w1, w2| w1 | w2)
190 * Calculates the intersection of two bitvectors
192 * Sets `self` to the intersection of `self` and `v1`. Both bitvectors
193 * must be the same length. Returns `true` if `self` changed.
196 pub fn intersect(&mut self, other: &Bitv) -> bool {
197 self.process(other, |w1, w2| w1 & w2)
200 /// Retrieve the value at index `i`
202 pub fn get(&self, i: uint) -> bool {
203 assert!(i < self.nbits);
204 let w = i / uint::BITS;
205 let b = i % uint::BITS;
206 let x = self.storage.get(w) & (1 << b);
211 * Set the value of a bit at a given index
213 * `i` must be less than the length of the bitvector.
216 pub fn set(&mut self, i: uint, x: bool) {
217 assert!(i < self.nbits);
218 let w = i / uint::BITS;
219 let b = i % uint::BITS;
221 *self.storage.get_mut(w) = if x { *self.storage.get(w) | flag }
222 else { *self.storage.get(w) & !flag };
225 /// Set all bits to 1
227 pub fn set_all(&mut self) {
228 for w in self.storage.mut_iter() { *w = !0u; }
233 pub fn negate(&mut self) {
234 for w in self.storage.mut_iter() { *w = !*w; }
238 * Calculate the difference between two bitvectors
240 * Sets each element of `v0` to the value of that element minus the
241 * element of `v1` at the same index. Both bitvectors must be the same
244 * Returns `true` if `v0` was changed.
247 pub fn difference(&mut self, other: &Bitv) -> bool {
248 self.process(other, |w1, w2| w1 & !w2)
251 /// Returns `true` if all bits are 1
253 pub fn all(&self) -> bool {
254 let mut last_word = !0u;
255 // Check that every word but the last is all-ones...
256 self.mask_words(0).all(|(_, elem)|
257 { let tmp = last_word; last_word = elem; tmp == !0u }) &&
258 // ...and that the last word is ones as far as it needs to be
259 (last_word == ((1 << self.nbits % uint::BITS) - 1) || last_word == !0u)
262 /// Returns an iterator over the elements of the vector in order.
267 /// use collections::bitv::Bitv;
268 /// let mut bv = Bitv::with_capacity(10, false);
274 /// // Count bits set to 1; result should be 5
275 /// println!("{}", bv.iter().filter(|x| *x).count());
278 pub fn iter<'a>(&'a self) -> Bits<'a> {
279 Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
282 /// Returns `true` if all bits are 0
283 pub fn none(&self) -> bool {
284 self.mask_words(0).all(|(_, w)| w == 0)
288 /// Returns `true` if any bit is 1
289 pub fn any(&self) -> bool {
294 * Organise the bits into bytes, such that the first bit in the
295 * `Bitv` becomes the high-order bit of the first byte. If the
296 * size of the `Bitv` is not a multiple of 8 then trailing bits
297 * will be filled-in with false/0
299 pub fn to_bytes(&self) -> Vec<u8> {
300 fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
301 let offset = byte * 8 + bit;
302 if offset >= bitv.nbits {
305 bitv.get(offset) as u8 << (7 - bit)
309 let len = self.nbits/8 +
310 if self.nbits % 8 == 0 { 0 } else { 1 };
311 Vec::from_fn(len, |i|
324 * Transform `self` into a `Vec<bool>` by turning each bit into a `bool`.
326 pub fn to_bools(&self) -> Vec<bool> {
327 Vec::from_fn(self.nbits, |i| self.get(i))
331 * Compare a bitvector to a vector of `bool`.
333 * Both the bitvector and vector must have the same length.
335 pub fn eq_vec(&self, v: &[bool]) -> bool {
336 assert_eq!(self.nbits, v.len());
338 while i < self.nbits {
339 if self.get(i) != v[i] { return false; }
345 /// Shorten a Bitv, dropping excess elements.
347 /// If `len` is greater than the vector's current length, this has no
353 /// use collections::bitv::Bitv;
354 /// let mut bvec: Bitv = vec![false, true, true, false].iter().map(|n| *n).collect();
355 /// let expected: Bitv = vec![false, true].iter().map(|n| *n).collect();
356 /// bvec.truncate(2);
357 /// assert_eq!(bvec, expected);
359 pub fn truncate(&mut self, len: uint) {
360 if len < self.len() {
362 let word_len = (len + uint::BITS - 1) / uint::BITS;
363 self.storage.truncate(word_len);
364 if len % uint::BITS > 0 {
365 let mask = (1 << len % uint::BITS) - 1;
366 *self.storage.get_mut(word_len - 1) &= mask;
371 /// Grows the vector to be able to store `size` bits without resizing
372 pub fn reserve(&mut self, size: uint) {
373 let old_size = self.storage.len();
374 let size = (size + uint::BITS - 1) / uint::BITS;
376 self.storage.grow(size - old_size, &0);
380 /// Returns the capacity in bits for this bit vector. Inserting any
381 /// element less than this amount will not trigger a resizing.
383 pub fn capacity(&self) -> uint {
384 self.storage.len() * uint::BITS
387 /// Grows the `Bitv` in-place.
389 /// Adds `n` copies of `value` to the `Bitv`.
394 /// use collections::bitv::Bitv;
395 /// let mut bvec: Bitv = vec![false, true, true, false].iter().map(|n| *n).collect();
396 /// bvec.grow(2, true);
397 /// assert_eq!(bvec, vec![false, true, true, false, true, true].iter().map(|n| *n).collect());
399 pub fn grow(&mut self, n: uint, value: bool) {
400 let new_nbits = self.nbits + n;
401 let new_nwords = (new_nbits + uint::BITS - 1) / uint::BITS;
402 let full_value = if value { !0 } else { 0 };
403 // Correct the old tail word
404 let old_last_word = (self.nbits + uint::BITS - 1) / uint::BITS - 1;
405 if self.nbits % uint::BITS > 0 {
406 let overhang = self.nbits % uint::BITS; // # of already-used bits
407 let mask = !((1 << overhang) - 1); // e.g. 5 unused bits => 111110....0
409 *self.storage.get_mut(old_last_word) |= mask;
411 *self.storage.get_mut(old_last_word) &= !mask;
414 // Fill in words after the old tail word
415 let stop_idx = cmp::min(self.storage.len(), new_nwords);
416 for idx in range(old_last_word + 1, stop_idx) {
417 *self.storage.get_mut(idx) = full_value;
419 // Allocate new words, if needed
420 if new_nwords > self.storage.len() {
421 let to_add = new_nwords - self.storage.len();
422 self.storage.grow(to_add, &full_value);
424 // Adjust internal bit count
425 self.nbits = new_nbits;
428 /// Shorten a `Bitv` by one, returning the removed element
433 /// use collections::bitv::Bitv;
434 /// let mut bvec: Bitv = vec![false, true, true, false].iter().map(|n| *n).collect();
435 /// let expected: Bitv = vec![false, true, true].iter().map(|n| *n).collect();
436 /// let popped = bvec.pop();
437 /// assert_eq!(popped, false);
438 /// assert_eq!(bvec, expected);
440 pub fn pop(&mut self) -> bool {
441 let ret = self.get(self.nbits - 1);
442 // If we are unusing a whole word, make sure it is zeroed out
443 if self.nbits % uint::BITS == 1 {
444 *self.storage.get_mut(self.nbits / uint::BITS) = 0;
450 /// Pushes a `bool` onto the `Bitv`
455 /// use collections::bitv::Bitv;
456 /// let prototype: Bitv = vec![false, true, true, false].iter().map(|n| *n).collect();
457 /// let mut bvec: Bitv = vec![false, true].iter().map(|n| *n).collect();
459 /// bvec.push(false);
460 /// assert_eq!(prototype, bvec);
462 pub fn push(&mut self, elem: bool) {
463 let insert_pos = self.nbits;
465 if self.storage.len() * uint::BITS < self.nbits {
466 self.storage.push(0);
468 self.set(insert_pos, elem);
473 * Transform a byte-vector into a `Bitv`. Each byte becomes 8 bits,
474 * with the most significant bits of each byte coming first. Each
475 * bit becomes `true` if equal to 1 or `false` if equal to 0.
477 pub fn from_bytes(bytes: &[u8]) -> Bitv {
478 from_fn(bytes.len() * 8, |i| {
479 let b = bytes[i / 8] as uint;
481 b >> (7 - offset) & 1 == 1
486 * Create a `Bitv` of the specified length where the value at each
487 * index is `f(index)`.
489 pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
490 let mut bitv = Bitv::with_capacity(len, false);
491 for i in range(0u, len) {
497 impl Default for Bitv {
499 fn default() -> Bitv { Bitv::new() }
502 impl Collection for Bitv {
504 fn len(&self) -> uint { self.nbits }
507 impl Mutable for Bitv {
509 fn clear(&mut self) {
510 for w in self.storage.mut_iter() { *w = 0u; }
514 impl FromIterator<bool> for Bitv {
515 fn from_iter<I:Iterator<bool>>(iterator: I) -> Bitv {
516 let mut ret = Bitv::new();
517 ret.extend(iterator);
522 impl Extendable<bool> for Bitv {
524 fn extend<I: Iterator<bool>>(&mut self, mut iterator: I) {
525 let (min, _) = iterator.size_hint();
526 let nbits = self.nbits;
527 self.reserve(nbits + min);
528 for element in iterator {
534 impl Clone for Bitv {
536 fn clone(&self) -> Bitv {
537 Bitv { storage: self.storage.clone(), nbits: self.nbits }
541 fn clone_from(&mut self, source: &Bitv) {
542 self.nbits = source.nbits;
543 self.storage.reserve(source.storage.len());
544 for (i, w) in self.storage.mut_iter().enumerate() { *w = *source.storage.get(i); }
548 impl fmt::Show for Bitv {
549 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
550 for bit in self.iter() {
551 try!(write!(fmt, "{}", if bit { 1u } else { 0u }));
557 impl<S: hash::Writer> hash::Hash<S> for Bitv {
558 fn hash(&self, state: &mut S) {
559 self.nbits.hash(state);
560 for (_, elem) in self.mask_words(0) {
566 impl cmp::PartialEq for Bitv {
568 fn eq(&self, other: &Bitv) -> bool {
569 if self.nbits != other.nbits {
572 self.mask_words(0).zip(other.mask_words(0)).all(|((_, w1), (_, w2))| w1 == w2)
576 impl cmp::Eq for Bitv {}
578 /// An iterator for `Bitv`.
579 pub struct Bits<'a> {
585 impl<'a> Iterator<bool> for Bits<'a> {
587 fn next(&mut self) -> Option<bool> {
588 if self.next_idx != self.end_idx {
589 let idx = self.next_idx;
591 Some(self.bitv.get(idx))
597 fn size_hint(&self) -> (uint, Option<uint>) {
598 let rem = self.end_idx - self.next_idx;
603 impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
605 fn next_back(&mut self) -> Option<bool> {
606 if self.next_idx != self.end_idx {
608 Some(self.bitv.get(self.end_idx))
615 impl<'a> ExactSize<bool> for Bits<'a> {}
617 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
619 fn indexable(&self) -> uint {
620 self.end_idx - self.next_idx
624 fn idx(&mut self, index: uint) -> Option<bool> {
625 if index >= self.indexable() {
628 Some(self.bitv.get(index))
633 /// An implementation of a set using a bit vector as an underlying
634 /// representation for holding numerical elements.
636 /// It should also be noted that the amount of storage necessary for holding a
637 /// set of objects is proportional to the maximum of the objects when viewed
639 #[deriving(Clone, PartialEq, Eq)]
640 pub struct BitvSet(Bitv);
642 impl Default for BitvSet {
644 fn default() -> BitvSet { BitvSet::new() }
648 /// Creates a new bit vector set with initially no contents
650 pub fn new() -> BitvSet {
654 /// Creates a new bit vector set with initially no contents, able to
655 /// hold `nbits` elements without resizing
657 pub fn with_capacity(nbits: uint) -> BitvSet {
658 BitvSet(Bitv::with_capacity(nbits, false))
661 /// Creates a new bit vector set from the given bit vector
663 pub fn from_bitv(bitv: Bitv) -> BitvSet {
667 /// Returns the capacity in bits for this bit vector. Inserting any
668 /// element less than this amount will not trigger a resizing.
670 pub fn capacity(&self) -> uint {
671 let &BitvSet(ref bitv) = self;
675 /// Grows the underlying vector to be able to store `size` bits
676 pub fn reserve(&mut self, size: uint) {
677 let &BitvSet(ref mut bitv) = self;
681 /// Consumes this set to return the underlying bit vector
683 pub fn unwrap(self) -> Bitv {
684 let BitvSet(bitv) = self;
688 /// Returns a reference to the underlying bit vector
690 pub fn get_ref<'a>(&'a self) -> &'a Bitv {
691 let &BitvSet(ref bitv) = self;
695 /// Returns a mutable reference to the underlying bit vector
697 pub fn get_mut_ref<'a>(&'a mut self) -> &'a mut Bitv {
698 let &BitvSet(ref mut bitv) = self;
703 fn other_op(&mut self, other: &BitvSet, f: |uint, uint| -> uint) {
705 let &BitvSet(ref mut self_bitv) = self;
706 let &BitvSet(ref other_bitv) = other;
707 // Expand the vector if necessary
708 self_bitv.reserve(other_bitv.capacity());
710 for (i, w) in other_bitv.mask_words(0) {
711 let old = *self_bitv.storage.get(i);
713 *self_bitv.storage.get_mut(i) = new;
718 /// Truncate the underlying vector to the least length required
719 pub fn shrink_to_fit(&mut self) {
720 let &BitvSet(ref mut bitv) = self;
721 // Obtain original length
722 let old_len = bitv.storage.len();
723 // Obtain coarse trailing zero length
724 let n = bitv.storage.iter().rev().take_while(|&&n| n == 0).count();
726 let trunc_len = cmp::max(old_len - n, 1);
727 bitv.storage.truncate(trunc_len);
728 bitv.nbits = trunc_len * uint::BITS;
731 /// Union in-place with the specified other bit vector
733 pub fn union_with(&mut self, other: &BitvSet) {
734 self.other_op(other, |w1, w2| w1 | w2);
737 /// Intersect in-place with the specified other bit vector
739 pub fn intersect_with(&mut self, other: &BitvSet) {
740 self.other_op(other, |w1, w2| w1 & w2);
743 /// Difference in-place with the specified other bit vector
745 pub fn difference_with(&mut self, other: &BitvSet) {
746 self.other_op(other, |w1, w2| w1 & !w2);
749 /// Symmetric difference in-place with the specified other bit vector
751 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
752 self.other_op(other, |w1, w2| w1 ^ w2);
755 /// Iterator over each uint stored in the BitvSet
757 pub fn iter<'a>(&'a self) -> BitPositions<'a> {
758 BitPositions {set: self, next_idx: 0}
761 /// Iterator over each uint stored in the `self` setminus `other`
763 pub fn difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
767 merge: |w1, w2| w1 & !w2,
773 /// Iterator over each uint stored in the symmetric difference of `self` and `other`
775 pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
779 merge: |w1, w2| w1 ^ w2,
785 /// Iterator over each uint stored in `self` intersect `other`
787 pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Take<TwoBitPositions<'a>> {
788 let min = cmp::min(self.capacity(), other.capacity());
792 merge: |w1, w2| w1 & w2,
798 /// Iterator over each uint stored in `self` union `other`
800 pub fn union<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
804 merge: |w1, w2| w1 | w2,
811 impl fmt::Show for BitvSet {
812 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
813 try!(write!(fmt, "{{"));
814 let mut first = true;
815 for n in self.iter() {
817 try!(write!(fmt, ", "));
819 try!(write!(fmt, "{}", n));
826 impl<S: hash::Writer> hash::Hash<S> for BitvSet {
827 fn hash(&self, state: &mut S) {
828 for pos in self.iter() {
834 impl Collection for BitvSet {
836 fn len(&self) -> uint {
837 let &BitvSet(ref bitv) = self;
838 bitv.storage.iter().fold(0, |acc, &n| acc + n.count_ones())
842 impl Mutable for BitvSet {
844 fn clear(&mut self) {
845 let &BitvSet(ref mut bitv) = self;
850 impl Set<uint> for BitvSet {
852 fn contains(&self, value: &uint) -> bool {
853 let &BitvSet(ref bitv) = self;
854 *value < bitv.nbits && bitv.get(*value)
858 fn is_disjoint(&self, other: &BitvSet) -> bool {
859 self.intersection(other).count() > 0
863 fn is_subset(&self, other: &BitvSet) -> bool {
864 let &BitvSet(ref self_bitv) = self;
865 let &BitvSet(ref other_bitv) = other;
867 // Check that `self` intersect `other` is self
868 self_bitv.mask_words(0).zip(other_bitv.mask_words(0))
869 .all(|((_, w1), (_, w2))| w1 & w2 == w1) &&
870 // Check that `self` setminus `other` is empty
871 self_bitv.mask_words(other_bitv.storage.len()).all(|(_, w)| w == 0)
875 fn is_superset(&self, other: &BitvSet) -> bool {
876 other.is_subset(self)
880 impl MutableSet<uint> for BitvSet {
881 fn insert(&mut self, value: uint) -> bool {
882 if self.contains(&value) {
885 if value >= self.capacity() {
886 let new_cap = cmp::max(value + 1, self.capacity() * 2);
887 self.reserve(new_cap);
889 let &BitvSet(ref mut bitv) = self;
890 if value >= bitv.nbits {
891 // If we are increasing nbits, make sure we mask out any previously-unconsidered bits
892 let old_rem = bitv.nbits % uint::BITS;
894 let old_last_word = (bitv.nbits + uint::BITS - 1) / uint::BITS - 1;
895 *bitv.storage.get_mut(old_last_word) &= (1 << old_rem) - 1;
897 bitv.nbits = value + 1;
899 bitv.set(value, true);
903 fn remove(&mut self, value: &uint) -> bool {
904 if !self.contains(value) {
907 let &BitvSet(ref mut bitv) = self;
908 bitv.set(*value, false);
913 pub struct BitPositions<'a> {
918 pub struct TwoBitPositions<'a> {
921 merge: |uint, uint|: 'a -> uint,
926 impl<'a> Iterator<uint> for BitPositions<'a> {
927 fn next(&mut self) -> Option<uint> {
928 while self.next_idx < self.set.capacity() {
929 let idx = self.next_idx;
932 if self.set.contains(&idx) {
941 fn size_hint(&self) -> (uint, Option<uint>) {
942 (0, Some(self.set.capacity() - self.next_idx))
946 impl<'a> Iterator<uint> for TwoBitPositions<'a> {
947 fn next(&mut self) -> Option<uint> {
948 while self.next_idx < self.set.capacity() ||
949 self.next_idx < self.other.capacity() {
950 let bit_idx = self.next_idx % uint::BITS;
952 let &BitvSet(ref s_bitv) = self.set;
953 let &BitvSet(ref o_bitv) = self.other;
954 // Merging the two words is a bit of an awkward dance since
955 // one Bitv might be longer than the other
956 let word_idx = self.next_idx / uint::BITS;
957 let w1 = if word_idx < s_bitv.storage.len() {
958 *s_bitv.storage.get(word_idx)
960 let w2 = if word_idx < o_bitv.storage.len() {
961 *o_bitv.storage.get(word_idx)
963 self.current_word = (self.merge)(w1, w2);
967 if self.current_word & (1 << bit_idx) != 0 {
968 return Some(self.next_idx - 1);
975 fn size_hint(&self) -> (uint, Option<uint>) {
976 let cap = cmp::max(self.set.capacity(), self.other.capacity());
977 (0, Some(cap - self.next_idx))
989 use {Set, Mutable, MutableSet};
990 use bitv::{Bitv, BitvSet, from_fn, from_bytes};
994 static BENCH_BITS : uint = 1 << 14;
998 let zerolen = Bitv::new();
999 assert_eq!(zerolen.to_string().as_slice(), "");
1001 let eightbits = Bitv::with_capacity(8u, false);
1002 assert_eq!(eightbits.to_string().as_slice(), "00000000")
1006 fn test_0_elements() {
1007 let act = Bitv::new();
1008 let exp = Vec::from_elem(0u, false);
1009 assert!(act.eq_vec(exp.as_slice()));
1013 fn test_1_element() {
1014 let mut act = Bitv::with_capacity(1u, false);
1015 assert!(act.eq_vec([false]));
1016 act = Bitv::with_capacity(1u, true);
1017 assert!(act.eq_vec([true]));
1021 fn test_2_elements() {
1022 let mut b = bitv::Bitv::with_capacity(2, false);
1025 assert_eq!(b.to_string().as_slice(), "10");
1029 fn test_10_elements() {
1033 act = Bitv::with_capacity(10u, false);
1034 assert!((act.eq_vec(
1035 [false, false, false, false, false, false, false, false, false, false])));
1038 act = Bitv::with_capacity(10u, true);
1039 assert!((act.eq_vec([true, true, true, true, true, true, true, true, true, true])));
1042 act = Bitv::with_capacity(10u, false);
1048 assert!((act.eq_vec([true, true, true, true, true, false, false, false, false, false])));
1051 act = Bitv::with_capacity(10u, false);
1057 assert!((act.eq_vec([false, false, false, false, false, true, true, true, true, true])));
1060 act = Bitv::with_capacity(10u, false);
1065 assert!((act.eq_vec([true, false, false, true, false, false, true, false, false, true])));
1069 fn test_31_elements() {
1073 act = Bitv::with_capacity(31u, false);
1075 [false, false, false, false, false, false, false, false, false, false, false,
1076 false, false, false, false, false, false, false, false, false, false, false, false,
1077 false, false, false, false, false, false, false, false]));
1080 act = Bitv::with_capacity(31u, true);
1082 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1083 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1084 true, true, true, true]));
1087 act = Bitv::with_capacity(31u, false);
1097 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1098 false, false, false, false, false, false, false, false, false, false, false, false,
1099 false, false, false, false, false, false]));
1102 act = Bitv::with_capacity(31u, false);
1112 [false, false, false, false, false, false, false, false, false, false, false,
1113 false, false, false, false, false, true, true, true, true, true, true, true, true,
1114 false, false, false, false, false, false, false]));
1117 act = Bitv::with_capacity(31u, false);
1126 [false, false, false, false, false, false, false, false, false, false, false,
1127 false, false, false, false, false, false, false, false, false, false, false, false,
1128 false, true, true, true, true, true, true, true]));
1131 act = Bitv::with_capacity(31u, false);
1136 [false, false, false, true, false, false, false, false, false, false, false, false,
1137 false, false, false, false, false, true, false, false, false, false, false, false,
1138 false, false, false, false, false, false, true]));
1142 fn test_32_elements() {
1146 act = Bitv::with_capacity(32u, false);
1148 [false, false, false, false, false, false, false, false, false, false, false,
1149 false, false, false, false, false, false, false, false, false, false, false, false,
1150 false, false, false, false, false, false, false, false, false]));
1153 act = Bitv::with_capacity(32u, true);
1155 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1156 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1157 true, true, true, true, true]));
1160 act = Bitv::with_capacity(32u, false);
1170 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1171 false, false, false, false, false, false, false, false, false, false, false, false,
1172 false, false, false, false, false, false, false]));
1175 act = Bitv::with_capacity(32u, false);
1185 [false, false, false, false, false, false, false, false, false, false, false,
1186 false, false, false, false, false, true, true, true, true, true, true, true, true,
1187 false, false, false, false, false, false, false, false]));
1190 act = Bitv::with_capacity(32u, false);
1200 [false, false, false, false, false, false, false, false, false, false, false,
1201 false, false, false, false, false, false, false, false, false, false, false, false,
1202 false, true, true, true, true, true, true, true, true]));
1205 act = Bitv::with_capacity(32u, false);
1211 [false, false, false, true, false, false, false, false, false, false, false, false,
1212 false, false, false, false, false, true, false, false, false, false, false, false,
1213 false, false, false, false, false, false, true, true]));
1217 fn test_33_elements() {
1221 act = Bitv::with_capacity(33u, false);
1223 [false, false, false, false, false, false, false, false, false, false, false,
1224 false, false, false, false, false, false, false, false, false, false, false, false,
1225 false, false, false, false, false, false, false, false, false, false]));
1228 act = Bitv::with_capacity(33u, true);
1230 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1231 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1232 true, true, true, true, true, true]));
1235 act = Bitv::with_capacity(33u, false);
1245 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1246 false, false, false, false, false, false, false, false, false, false, false, false,
1247 false, false, false, false, false, false, false, false]));
1250 act = Bitv::with_capacity(33u, false);
1260 [false, false, false, false, false, false, false, false, false, false, false,
1261 false, false, false, false, false, true, true, true, true, true, true, true, true,
1262 false, false, false, false, false, false, false, false, false]));
1265 act = Bitv::with_capacity(33u, false);
1275 [false, false, false, false, false, false, false, false, false, false, false,
1276 false, false, false, false, false, false, false, false, false, false, false, false,
1277 false, true, true, true, true, true, true, true, true, false]));
1280 act = Bitv::with_capacity(33u, false);
1287 [false, false, false, true, false, false, false, false, false, false, false, false,
1288 false, false, false, false, false, true, false, false, false, false, false, false,
1289 false, false, false, false, false, false, true, true, true]));
1293 fn test_equal_differing_sizes() {
1294 let v0 = Bitv::with_capacity(10u, false);
1295 let v1 = Bitv::with_capacity(11u, false);
1300 fn test_equal_greatly_differing_sizes() {
1301 let v0 = Bitv::with_capacity(10u, false);
1302 let v1 = Bitv::with_capacity(110u, false);
1307 fn test_equal_sneaky_small() {
1308 let mut a = bitv::Bitv::with_capacity(1, false);
1311 let mut b = bitv::Bitv::with_capacity(1, true);
1318 fn test_equal_sneaky_big() {
1319 let mut a = bitv::Bitv::with_capacity(100, false);
1320 for i in range(0u, 100) {
1324 let mut b = bitv::Bitv::with_capacity(100, true);
1325 for i in range(0u, 100) {
1333 fn test_from_bytes() {
1334 let bitv = from_bytes([0b10110110, 0b00000000, 0b11111111]);
1335 let str = format!("{}{}{}", "10110110", "00000000", "11111111");
1336 assert_eq!(bitv.to_string().as_slice(), str.as_slice());
1340 fn test_to_bytes() {
1341 let mut bv = Bitv::with_capacity(3, true);
1343 assert_eq!(bv.to_bytes(), vec!(0b10100000));
1345 let mut bv = Bitv::with_capacity(9, false);
1348 assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
1352 fn test_from_bools() {
1353 let bools = vec![true, false, true, true];
1354 let bitv: Bitv = bools.iter().map(|n| *n).collect();
1355 assert_eq!(bitv.to_string().as_slice(), "1011");
1359 fn test_to_bools() {
1360 let bools = vec!(false, false, true, false, false, true, true, false);
1361 assert_eq!(from_bytes([0b00100110]).iter().collect::<Vec<bool>>(), bools);
1365 fn test_bitv_iterator() {
1366 let bools = [true, false, true, true];
1367 let bitv: Bitv = bools.iter().map(|n| *n).collect();
1369 for (act, &ex) in bitv.iter().zip(bools.iter()) {
1370 assert_eq!(ex, act);
1375 fn test_bitv_set_iterator() {
1376 let bools = [true, false, true, true];
1377 let bitv = BitvSet::from_bitv(bools.iter().map(|n| *n).collect());
1379 let idxs: Vec<uint> = bitv.iter().collect();
1380 assert_eq!(idxs, vec!(0, 2, 3));
1384 fn test_bitv_set_frombitv_init() {
1385 let bools = [true, false];
1386 let lengths = [10, 64, 100];
1387 for &b in bools.iter() {
1388 for &l in lengths.iter() {
1389 let bitset = BitvSet::from_bitv(Bitv::with_capacity(l, b));
1390 assert_eq!(bitset.contains(&1u), b)
1391 assert_eq!(bitset.contains(&(l-1u)), b)
1392 assert!(!bitset.contains(&l))
1398 fn test_small_difference() {
1399 let mut b1 = Bitv::with_capacity(3, false);
1400 let mut b2 = Bitv::with_capacity(3, false);
1405 assert!(b1.difference(&b2));
1407 assert!(!b1.get(1));
1408 assert!(!b1.get(2));
1412 fn test_big_difference() {
1413 let mut b1 = Bitv::with_capacity(100, false);
1414 let mut b2 = Bitv::with_capacity(100, false);
1419 assert!(b1.difference(&b2));
1421 assert!(!b1.get(40));
1422 assert!(!b1.get(80));
1426 fn test_small_clear() {
1427 let mut b = Bitv::with_capacity(14, true);
1433 fn test_big_clear() {
1434 let mut b = Bitv::with_capacity(140, true);
1440 fn test_bitv_masking() {
1441 let b = Bitv::with_capacity(140, true);
1442 let mut bs = BitvSet::from_bitv(b);
1443 assert!(bs.contains(&139));
1444 assert!(!bs.contains(&140));
1445 assert!(bs.insert(150));
1446 assert!(!bs.contains(&140));
1447 assert!(!bs.contains(&149));
1448 assert!(bs.contains(&150));
1449 assert!(!bs.contains(&151));
1453 fn test_bitv_set_basic() {
1454 // calculate nbits with uint::BITS granularity
1455 fn calc_nbits(bits: uint) -> uint {
1456 uint::BITS * ((bits + uint::BITS - 1) / uint::BITS)
1459 let mut b = BitvSet::new();
1460 assert_eq!(b.capacity(), calc_nbits(0));
1461 assert!(b.insert(3));
1462 assert_eq!(b.capacity(), calc_nbits(3));
1463 assert!(!b.insert(3));
1464 assert!(b.contains(&3));
1465 assert!(b.insert(4));
1466 assert!(!b.insert(4));
1467 assert!(b.contains(&3));
1468 assert!(b.insert(400));
1469 assert_eq!(b.capacity(), calc_nbits(400));
1470 assert!(!b.insert(400));
1471 assert!(b.contains(&400));
1472 assert_eq!(b.len(), 3);
1476 fn test_bitv_set_intersection() {
1477 let mut a = BitvSet::new();
1478 let mut b = BitvSet::new();
1480 assert!(a.insert(11));
1481 assert!(a.insert(1));
1482 assert!(a.insert(3));
1483 assert!(a.insert(77));
1484 assert!(a.insert(103));
1485 assert!(a.insert(5));
1487 assert!(b.insert(2));
1488 assert!(b.insert(11));
1489 assert!(b.insert(77));
1490 assert!(b.insert(5));
1491 assert!(b.insert(3));
1493 let expected = [3, 5, 11, 77];
1494 let actual = a.intersection(&b).collect::<Vec<uint>>();
1495 assert_eq!(actual.as_slice(), expected.as_slice());
1499 fn test_bitv_set_difference() {
1500 let mut a = BitvSet::new();
1501 let mut b = BitvSet::new();
1503 assert!(a.insert(1));
1504 assert!(a.insert(3));
1505 assert!(a.insert(5));
1506 assert!(a.insert(200));
1507 assert!(a.insert(500));
1509 assert!(b.insert(3));
1510 assert!(b.insert(200));
1512 let expected = [1, 5, 500];
1513 let actual = a.difference(&b).collect::<Vec<uint>>();
1514 assert_eq!(actual.as_slice(), expected.as_slice());
1518 fn test_bitv_set_symmetric_difference() {
1519 let mut a = BitvSet::new();
1520 let mut b = BitvSet::new();
1522 assert!(a.insert(1));
1523 assert!(a.insert(3));
1524 assert!(a.insert(5));
1525 assert!(a.insert(9));
1526 assert!(a.insert(11));
1528 assert!(b.insert(3));
1529 assert!(b.insert(9));
1530 assert!(b.insert(14));
1531 assert!(b.insert(220));
1533 let expected = [1, 5, 11, 14, 220];
1534 let actual = a.symmetric_difference(&b).collect::<Vec<uint>>();
1535 assert_eq!(actual.as_slice(), expected.as_slice());
1539 fn test_bitv_set_union() {
1540 let mut a = BitvSet::new();
1541 let mut b = BitvSet::new();
1542 assert!(a.insert(1));
1543 assert!(a.insert(3));
1544 assert!(a.insert(5));
1545 assert!(a.insert(9));
1546 assert!(a.insert(11));
1547 assert!(a.insert(160));
1548 assert!(a.insert(19));
1549 assert!(a.insert(24));
1551 assert!(b.insert(1));
1552 assert!(b.insert(5));
1553 assert!(b.insert(9));
1554 assert!(b.insert(13));
1555 assert!(b.insert(19));
1557 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160];
1558 let actual = a.union(&b).collect::<Vec<uint>>();
1559 assert_eq!(actual.as_slice(), expected.as_slice());
1563 fn test_bitv_set_subset() {
1564 let mut set1 = BitvSet::new();
1565 let mut set2 = BitvSet::new();
1567 assert!(set1.is_subset(&set2)); // {} {}
1569 assert!(set1.is_subset(&set2)); // {} { 1 }
1571 assert!(set1.is_subset(&set2)); // {} { 1, 2 }
1573 assert!(set1.is_subset(&set2)); // { 2 } { 1, 2 }
1575 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 1, 2 }
1577 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3 }
1579 assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3, 4 }
1581 assert!(set1.is_subset(&set2)); // { 2, 3 } { 2, 3, 4 }
1583 assert!(!set1.is_subset(&set2)); // { 2, 3 } { 2, 4 }
1585 assert!(set1.is_subset(&set2)); // { 2 } { 2, 4 }
1589 fn test_bitv_remove() {
1590 let mut a = BitvSet::new();
1592 assert!(a.insert(1));
1593 assert!(a.remove(&1));
1595 assert!(a.insert(100));
1596 assert!(a.remove(&100));
1598 assert!(a.insert(1000));
1599 assert!(a.remove(&1000));
1601 assert_eq!(a.capacity(), uint::BITS);
1605 fn test_bitv_clone() {
1606 let mut a = BitvSet::new();
1608 assert!(a.insert(1));
1609 assert!(a.insert(100));
1610 assert!(a.insert(1000));
1612 let mut b = a.clone();
1616 assert!(b.remove(&1));
1617 assert!(a.contains(&1));
1619 assert!(a.remove(&1000));
1620 assert!(b.contains(&1000));
1624 fn test_small_bitv_tests() {
1625 let v = from_bytes([0]);
1630 let v = from_bytes([0b00010100]);
1635 let v = from_bytes([0xFF]);
1642 fn test_big_bitv_tests() {
1643 let v = from_bytes([ // 88 bits
1651 let v = from_bytes([ // 88 bits
1652 0, 0, 0b00010100, 0,
1653 0, 0, 0, 0b00110100,
1659 let v = from_bytes([ // 88 bits
1660 0xFF, 0xFF, 0xFF, 0xFF,
1661 0xFF, 0xFF, 0xFF, 0xFF,
1669 fn test_bitv_push_pop() {
1670 let mut s = Bitv::with_capacity(5 * uint::BITS - 2, false);
1671 assert_eq!(s.len(), 5 * uint::BITS - 2);
1672 assert_eq!(s.get(5 * uint::BITS - 3), false);
1675 assert_eq!(s.get(5 * uint::BITS - 2), true);
1676 assert_eq!(s.get(5 * uint::BITS - 1), true);
1677 // Here the internal vector will need to be extended
1679 assert_eq!(s.get(5 * uint::BITS), false);
1681 assert_eq!(s.get(5 * uint::BITS + 1), false);
1682 assert_eq!(s.len(), 5 * uint::BITS + 2);
1684 assert_eq!(s.pop(), false);
1685 assert_eq!(s.pop(), false);
1686 assert_eq!(s.pop(), true);
1687 assert_eq!(s.pop(), true);
1688 assert_eq!(s.len(), 5 * uint::BITS - 2);
1692 fn test_bitv_truncate() {
1693 let mut s = Bitv::with_capacity(5 * uint::BITS, true);
1695 assert_eq!(s, Bitv::with_capacity(5 * uint::BITS, true));
1696 assert_eq!(s.len(), 5 * uint::BITS);
1697 s.truncate(4 * uint::BITS);
1698 assert_eq!(s, Bitv::with_capacity(4 * uint::BITS, true));
1699 assert_eq!(s.len(), 4 * uint::BITS);
1700 // Truncating to a size > s.len() should be a noop
1701 s.truncate(5 * uint::BITS);
1702 assert_eq!(s, Bitv::with_capacity(4 * uint::BITS, true));
1703 assert_eq!(s.len(), 4 * uint::BITS);
1704 s.truncate(3 * uint::BITS - 10);
1705 assert_eq!(s, Bitv::with_capacity(3 * uint::BITS - 10, true));
1706 assert_eq!(s.len(), 3 * uint::BITS - 10);
1708 assert_eq!(s, Bitv::with_capacity(0, true));
1709 assert_eq!(s.len(), 0);
1713 fn test_bitv_reserve() {
1714 let mut s = Bitv::with_capacity(5 * uint::BITS, true);
1716 assert_eq!(s.capacity(), 5 * uint::BITS);
1717 s.reserve(2 * uint::BITS);
1718 assert_eq!(s.capacity(), 5 * uint::BITS);
1719 s.reserve(7 * uint::BITS);
1720 assert_eq!(s.capacity(), 7 * uint::BITS);
1721 s.reserve(7 * uint::BITS);
1722 assert_eq!(s.capacity(), 7 * uint::BITS);
1723 s.reserve(7 * uint::BITS + 1);
1724 assert_eq!(s.capacity(), 8 * uint::BITS);
1725 // Check that length hasn't changed
1726 assert_eq!(s.len(), 5 * uint::BITS);
1730 assert_eq!(s.get(5 * uint::BITS - 1), true);
1731 assert_eq!(s.get(5 * uint::BITS - 0), true);
1732 assert_eq!(s.get(5 * uint::BITS + 1), false);
1733 assert_eq!(s.get(5 * uint::BITS + 2), true);
1737 fn test_bitv_grow() {
1738 let mut bitv = from_bytes([0b10110110, 0b00000000, 0b10101010]);
1739 bitv.grow(32, true);
1740 assert_eq!(bitv, from_bytes([0b10110110, 0b00000000, 0b10101010,
1741 0xFF, 0xFF, 0xFF, 0xFF]));
1742 bitv.grow(64, false);
1743 assert_eq!(bitv, from_bytes([0b10110110, 0b00000000, 0b10101010,
1744 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
1745 bitv.grow(16, true);
1746 assert_eq!(bitv, from_bytes([0b10110110, 0b00000000, 0b10101010,
1747 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
1751 fn test_bitv_extend() {
1752 let mut bitv = from_bytes([0b10110110, 0b00000000, 0b11111111]);
1753 let ext = from_bytes([0b01001001, 0b10010010, 0b10111101]);
1754 bitv.extend(ext.iter());
1755 assert_eq!(bitv, from_bytes([0b10110110, 0b00000000, 0b11111111,
1756 0b01001001, 0b10010010, 0b10111101]));
1760 fn test_bitv_set_show() {
1761 let mut s = BitvSet::new();
1766 assert_eq!("{1, 2, 10, 50}".to_string(), s.to_string());
1769 fn rng() -> rand::IsaacRng {
1770 let seed = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
1771 rand::SeedableRng::from_seed(seed)
1775 fn bench_uint_small(b: &mut Bencher) {
1777 let mut bitv = 0 as uint;
1779 bitv |= 1 << ((r.next_u32() as uint) % uint::BITS);
1785 fn bench_bitv_big(b: &mut Bencher) {
1787 let mut bitv = Bitv::with_capacity(BENCH_BITS, false);
1789 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1795 fn bench_bitv_small(b: &mut Bencher) {
1797 let mut bitv = Bitv::with_capacity(uint::BITS, false);
1799 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1805 fn bench_bitv_set_small(b: &mut Bencher) {
1807 let mut bitv = BitvSet::new();
1809 bitv.insert((r.next_u32() as uint) % uint::BITS);
1815 fn bench_bitv_set_big(b: &mut Bencher) {
1817 let mut bitv = BitvSet::new();
1819 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
1825 fn bench_bitv_big_union(b: &mut Bencher) {
1826 let mut b1 = Bitv::with_capacity(BENCH_BITS, false);
1827 let b2 = Bitv::with_capacity(BENCH_BITS, false);
1834 fn bench_btv_small_iter(b: &mut Bencher) {
1835 let bitv = Bitv::with_capacity(uint::BITS, false);
1838 for pres in bitv.iter() {
1839 _sum += pres as uint;
1845 fn bench_bitv_big_iter(b: &mut Bencher) {
1846 let bitv = Bitv::with_capacity(BENCH_BITS, false);
1849 for pres in bitv.iter() {
1850 _sum += pres as uint;
1856 fn bench_bitvset_iter(b: &mut Bencher) {
1857 let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
1858 |idx| {idx % 3 == 0}));
1861 for idx in bitv.iter() {