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;
18 use core::iter::{Enumerate, Repeat, Map, Zip};
24 use {Collection, Mutable, Set, MutableSet};
29 /// only the lowest nbits of this value are used. the rest is undefined.
33 /// a mask that has a 1 for each defined bit in a small_bitv, assuming n bits
35 fn small_mask(nbits: uint) -> uint {
40 fn new(bits: uint) -> SmallBitv {
41 SmallBitv {bits: bits}
48 f: |uint, uint| -> uint)
50 let mask = small_mask(nbits);
51 let old_b: uint = self.bits;
52 let new_b = f(old_b, right_bits);
54 mask & old_b != mask & new_b
58 fn union(&mut self, s: &SmallBitv, nbits: uint) -> bool {
59 self.bits_op(s.bits, nbits, |u1, u2| u1 | u2)
63 fn intersect(&mut self, s: &SmallBitv, nbits: uint) -> bool {
64 self.bits_op(s.bits, nbits, |u1, u2| u1 & u2)
68 fn become(&mut self, s: &SmallBitv, nbits: uint) -> bool {
69 self.bits_op(s.bits, nbits, |_u1, u2| u2)
73 fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool {
74 self.bits_op(s.bits, nbits, |u1, u2| u1 & !u2)
78 fn get(&self, i: uint) -> bool {
79 (self.bits & (1 << i)) != 0
83 fn set(&mut self, i: uint, x: bool) {
93 fn equals(&self, b: &SmallBitv, nbits: uint) -> bool {
94 let mask = small_mask(nbits);
95 mask & self.bits == mask & b.bits
99 fn clear(&mut self) { self.bits = 0; }
102 fn set_all(&mut self) { self.bits = !0; }
105 fn all(&self, nbits: uint) -> bool {
106 small_mask(nbits) & !self.bits == 0
110 fn none(&self, nbits: uint) -> bool {
111 small_mask(nbits) & self.bits == 0
115 fn negate(&mut self) { self.bits = !self.bits; }
124 * A mask that has a 1 for each defined bit in the n'th element of a `BigBitv`,
128 fn big_mask(nbits: uint, elem: uint) -> uint {
129 let rmd = nbits % uint::BITS;
130 let nelems = nbits/uint::BITS + if rmd == 0 {0} else {1};
132 if elem < nelems - 1 || rmd == 0 {
140 fn new(storage: Vec<uint>) -> BigBitv {
141 BigBitv {storage: storage}
145 fn process(&mut self,
148 op: |uint, uint| -> uint)
150 let len = b.storage.len();
151 assert_eq!(self.storage.len(), len);
152 let mut changed = false;
153 for (i, (a, b)) in self.storage.mut_iter()
154 .zip(b.storage.iter())
156 let mask = big_mask(nbits, i);
159 let w = op(w0, w1) & mask;
169 fn each_storage(&mut self, op: |v: &mut uint| -> bool) -> bool {
170 self.storage.mut_iter().advance(|elt| op(elt))
174 fn negate(&mut self) {
175 self.each_storage(|w| { *w = !*w; true });
179 fn union(&mut self, b: &BigBitv, nbits: uint) -> bool {
180 self.process(b, nbits, |w1, w2| w1 | w2)
184 fn intersect(&mut self, b: &BigBitv, nbits: uint) -> bool {
185 self.process(b, nbits, |w1, w2| w1 & w2)
189 fn become(&mut self, b: &BigBitv, nbits: uint) -> bool {
190 self.process(b, nbits, |_, w| w)
194 fn difference(&mut self, b: &BigBitv, nbits: uint) -> bool {
195 self.process(b, nbits, |w1, w2| w1 & !w2)
199 fn get(&self, i: uint) -> bool {
200 let w = i / uint::BITS;
201 let b = i % uint::BITS;
202 let x = 1 & self.storage.get(w) >> b;
207 fn set(&mut self, i: uint, x: bool) {
208 let w = i / uint::BITS;
209 let b = i % uint::BITS;
211 *self.storage.get_mut(w) = if x { *self.storage.get(w) | flag }
212 else { *self.storage.get(w) & !flag };
216 fn equals(&self, b: &BigBitv, nbits: uint) -> bool {
217 for (i, elt) in b.storage.iter().enumerate() {
218 let mask = big_mask(nbits, i);
219 if mask & *self.storage.get(i) != mask & *elt {
228 enum BitvVariant { Big(BigBitv), Small(SmallBitv) }
230 enum Op {Union, Intersect, Assign, Difference}
232 /// The bitvector type
237 /// use collections::bitv::Bitv;
239 /// let mut bv = Bitv::new(10, false);
241 /// // insert all primes less than 10
246 /// println!("{}", bv.to_str());
247 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
249 /// // flip all values in bitvector, producing non-primes less than 10
251 /// println!("{}", bv.to_str());
252 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
254 /// // reset bitvector to empty
256 /// println!("{}", bv.to_str());
257 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
261 /// Internal representation of the bit vector (small or large)
263 /// The number of valid bits in the internal representation
268 fail!("Tried to do operation on bit vectors with different sizes");
273 fn do_op(&mut self, op: Op, other: &Bitv) -> bool {
274 if self.nbits != other.nbits {
278 Small(ref mut s) => match other.rep {
279 Small(ref s1) => match op {
280 Union => s.union(s1, self.nbits),
281 Intersect => s.intersect(s1, self.nbits),
282 Assign => s.become(s1, self.nbits),
283 Difference => s.difference(s1, self.nbits)
287 Big(ref mut s) => match other.rep {
289 Big(ref s1) => match op {
290 Union => s.union(s1, self.nbits),
291 Intersect => s.intersect(s1, self.nbits),
292 Assign => s.become(s1, self.nbits),
293 Difference => s.difference(s1, self.nbits)
301 /// Creates an empty Bitv that holds `nbits` elements, setting each element
303 pub fn new(nbits: uint, init: bool) -> Bitv {
304 let rep = if nbits < uint::BITS {
305 Small(SmallBitv::new(if init {(1<<nbits)-1} else {0}))
306 } else if nbits == uint::BITS {
307 Small(SmallBitv::new(if init {!0} else {0}))
309 let exact = nbits % uint::BITS == 0;
310 let nelems = nbits/uint::BITS + if exact {0} else {1};
314 Vec::from_elem(nelems, !0u)
316 let mut v = Vec::from_elem(nelems-1, !0u);
317 v.push((1<<nbits % uint::BITS)-1);
320 } else { Vec::from_elem(nelems, 0u)};
323 Bitv {rep: rep, nbits: nbits}
327 * Calculates the union of two bitvectors
329 * Sets `self` to the union of `self` and `v1`. Both bitvectors must be
330 * the same length. Returns `true` if `self` changed.
333 pub fn union(&mut self, v1: &Bitv) -> bool { self.do_op(Union, v1) }
336 * Calculates the intersection of two bitvectors
338 * Sets `self` to the intersection of `self` and `v1`. Both bitvectors
339 * must be the same length. Returns `true` if `self` changed.
342 pub fn intersect(&mut self, v1: &Bitv) -> bool {
343 self.do_op(Intersect, v1)
347 * Assigns the value of `v1` to `self`
349 * Both bitvectors must be the same length. Returns `true` if `self` was
353 pub fn assign(&mut self, v: &Bitv) -> bool { self.do_op(Assign, v) }
355 /// Retrieve the value at index `i`
357 pub fn get(&self, i: uint) -> bool {
358 assert!((i < self.nbits));
360 Big(ref b) => b.get(i),
361 Small(ref s) => s.get(i)
366 * Set the value of a bit at a given index
368 * `i` must be less than the length of the bitvector.
371 pub fn set(&mut self, i: uint, x: bool) {
372 assert!((i < self.nbits));
374 Big(ref mut b) => b.set(i, x),
375 Small(ref mut s) => s.set(i, x)
379 /// Set all bits to 0
381 pub fn clear(&mut self) {
383 Small(ref mut b) => b.clear(),
385 s.each_storage(|w| { *w = 0u; true });
390 /// Set all bits to 1
392 pub fn set_all(&mut self) {
394 Small(ref mut b) => b.set_all(),
396 s.each_storage(|w| { *w = !0u; true });
403 pub fn negate(&mut self) {
405 Small(ref mut s) => s.negate(),
406 Big(ref mut b) => b.negate(),
411 * Calculate the difference between two bitvectors
413 * Sets each element of `v0` to the value of that element minus the
414 * element of `v1` at the same index. Both bitvectors must be the same
417 * Returns `true` if `v0` was changed.
420 pub fn difference(&mut self, v: &Bitv) -> bool {
421 self.do_op(Difference, v)
424 /// Returns `true` if all bits are 1
426 pub fn all(&self) -> bool {
428 Small(ref b) => b.all(self.nbits),
429 _ => self.iter().all(|x| x)
433 /// Returns an iterator over the elements of the vector in order.
438 /// use collections::bitv::Bitv;
439 /// let mut bv = Bitv::new(10, false);
445 /// // Count bits set to 1; result should be 5
446 /// println!("{}", bv.iter().filter(|x| *x).count());
449 pub fn iter<'a>(&'a self) -> Bits<'a> {
450 Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
453 /// Returns `true` if all bits are 0
454 pub fn none(&self) -> bool {
456 Small(ref b) => b.none(self.nbits),
457 _ => self.iter().all(|x| !x)
462 /// Returns `true` if any bit is 1
463 pub fn any(&self) -> bool {
468 * Converts `self` to a vector of `uint` with the same length.
470 * Each `uint` in the resulting vector has either value `0u` or `1u`.
472 pub fn to_vec(&self) -> Vec<uint> {
473 Vec::from_fn(self.nbits, |i| if self.get(i) { 1 } else { 0 })
477 * Organise the bits into bytes, such that the first bit in the
478 * `Bitv` becomes the high-order bit of the first byte. If the
479 * size of the `Bitv` is not a multiple of 8 then trailing bits
480 * will be filled-in with false/0
482 pub fn to_bytes(&self) -> Vec<u8> {
483 fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
484 let offset = byte * 8 + bit;
485 if offset >= bitv.nbits {
488 bitv[offset] as u8 << (7 - bit)
492 let len = self.nbits/8 +
493 if self.nbits % 8 == 0 { 0 } else { 1 };
494 Vec::from_fn(len, |i|
507 * Transform `self` into a `Vec<bool>` by turning each bit into a `bool`.
509 pub fn to_bools(&self) -> Vec<bool> {
510 Vec::from_fn(self.nbits, |i| self[i])
514 * Compare a bitvector to a vector of `bool`.
516 * Both the bitvector and vector must have the same length.
518 pub fn eq_vec(&self, v: &[bool]) -> bool {
519 assert_eq!(self.nbits, v.len());
521 while i < self.nbits {
522 if self.get(i) != v[i] { return false; }
528 pub fn ones(&self, f: |uint| -> bool) -> bool {
529 range(0u, self.nbits).advance(|i| !self.get(i) || f(i))
535 * Transform a byte-vector into a `Bitv`. Each byte becomes 8 bits,
536 * with the most significant bits of each byte coming first. Each
537 * bit becomes `true` if equal to 1 or `false` if equal to 0.
539 pub fn from_bytes(bytes: &[u8]) -> Bitv {
540 from_fn(bytes.len() * 8, |i| {
541 let b = bytes[i / 8] as uint;
543 b >> (7 - offset) & 1 == 1
548 * Transform a `[bool]` into a `Bitv` by converting each `bool` into a bit.
550 pub fn from_bools(bools: &[bool]) -> Bitv {
551 from_fn(bools.len(), |i| bools[i])
555 * Create a `Bitv` of the specified length where the value at each
556 * index is `f(index)`.
558 pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
559 let mut bitv = Bitv::new(len, false);
560 for i in range(0u, len) {
566 impl ops::Index<uint,bool> for Bitv {
567 fn index(&self, i: &uint) -> bool {
572 impl fmt::Show for Bitv {
573 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
574 for bit in self.iter() {
575 try!(write!(fmt, "{}", if bit { 1u } else { 0u }));
581 impl<S: hash::Writer> hash::Hash<S> for Bitv {
582 fn hash(&self, state: &mut S) {
583 self.nbits.hash(state);
585 Small(ref s) => (s.bits & small_mask(self.nbits)).hash(state),
587 for (i, ele) in b.storage.iter().enumerate() {
588 (ele & big_mask(self.nbits, i)).hash(state);
595 impl cmp::PartialEq for Bitv {
597 fn eq(&self, other: &Bitv) -> bool {
598 if self.nbits != other.nbits { return false; }
600 Small(ref b) => match other.rep {
601 Small(ref b1) => b.equals(b1, self.nbits),
604 Big(ref s) => match other.rep {
605 Big(ref s1) => s.equals(s1, self.nbits),
606 Small(_) => return false
612 impl cmp::Eq for Bitv {}
615 fn iterate_bits(base: uint, bits: uint, f: |uint| -> bool) -> bool {
619 for i in range(0u, uint::BITS) {
620 if bits & (1 << i) != 0 {
629 /// An iterator for `Bitv`.
630 pub struct Bits<'a> {
636 impl<'a> Iterator<bool> for Bits<'a> {
638 fn next(&mut self) -> Option<bool> {
639 if self.next_idx != self.end_idx {
640 let idx = self.next_idx;
642 Some(self.bitv.get(idx))
648 fn size_hint(&self) -> (uint, Option<uint>) {
649 let rem = self.end_idx - self.next_idx;
654 impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
656 fn next_back(&mut self) -> Option<bool> {
657 if self.next_idx != self.end_idx {
659 Some(self.bitv.get(self.end_idx))
666 impl<'a> ExactSize<bool> for Bits<'a> {}
668 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
670 fn indexable(&self) -> uint {
671 self.end_idx - self.next_idx
675 fn idx(&mut self, index: uint) -> Option<bool> {
676 if index >= self.indexable() {
679 Some(self.bitv.get(index))
684 /// An implementation of a set using a bit vector as an underlying
685 /// representation for holding numerical elements.
687 /// It should also be noted that the amount of storage necessary for holding a
688 /// set of objects is proportional to the maximum of the objects when viewed
694 // In theory this is a `Bitv` instead of always a `BigBitv`, but knowing that
695 // there's an array of storage makes our lives a whole lot easier when
696 // performing union/intersection/etc operations
700 impl Default for BitvSet {
702 fn default() -> BitvSet { BitvSet::new() }
706 /// Creates a new bit vector set with initially no contents
707 pub fn new() -> BitvSet {
708 BitvSet{ size: 0, bitv: BigBitv::new(vec!(0)) }
711 /// Creates a new bit vector set from the given bit vector
712 pub fn from_bitv(bitv: Bitv) -> BitvSet {
718 let Bitv{rep, ..} = bitv;
720 Big(b) => BitvSet{ size: size, bitv: b },
721 Small(SmallBitv{bits}) =>
722 BitvSet{ size: size, bitv: BigBitv{ storage: vec!(bits) } },
726 /// Returns the capacity in bits for this bit vector. Inserting any
727 /// element less than this amount will not trigger a resizing.
728 pub fn capacity(&self) -> uint { self.bitv.storage.len() * uint::BITS }
730 /// Consumes this set to return the underlying bit vector
731 pub fn unwrap(self) -> Bitv {
732 let cap = self.capacity();
733 let BitvSet{bitv, ..} = self;
734 return Bitv{ nbits:cap, rep: Big(bitv) };
738 fn other_op(&mut self, other: &BitvSet, f: |uint, uint| -> uint) {
739 fn nbits(mut w: uint) -> uint {
741 for _ in range(0u, uint::BITS) {
750 if self.capacity() < other.capacity() {
751 self.bitv.storage.grow(other.capacity() / uint::BITS, &0);
753 for (i, &w) in other.bitv.storage.iter().enumerate() {
754 let old = *self.bitv.storage.get(i);
756 *self.bitv.storage.get_mut(i) = new;
757 self.size += nbits(new) - nbits(old);
761 /// Union in-place with the specified other bit vector
762 pub fn union_with(&mut self, other: &BitvSet) {
763 self.other_op(other, |w1, w2| w1 | w2);
766 /// Intersect in-place with the specified other bit vector
767 pub fn intersect_with(&mut self, other: &BitvSet) {
768 self.other_op(other, |w1, w2| w1 & w2);
771 /// Difference in-place with the specified other bit vector
772 pub fn difference_with(&mut self, other: &BitvSet) {
773 self.other_op(other, |w1, w2| w1 & !w2);
776 /// Symmetric difference in-place with the specified other bit vector
777 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
778 self.other_op(other, |w1, w2| w1 ^ w2);
781 pub fn iter<'a>(&'a self) -> BitPositions<'a> {
782 BitPositions {set: self, next_idx: 0}
785 pub fn difference(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
786 for (i, w1, w2) in self.commons(other) {
787 if !iterate_bits(i, w1 & !w2, |b| f(&b)) {
791 /* everything we have that they don't also shows up */
792 self.outliers(other).advance(|(mine, i, w)|
793 !mine || iterate_bits(i, w, |b| f(&b))
797 pub fn symmetric_difference(&self, other: &BitvSet, f: |&uint| -> bool)
799 for (i, w1, w2) in self.commons(other) {
800 if !iterate_bits(i, w1 ^ w2, |b| f(&b)) {
804 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
807 pub fn intersection(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
808 self.commons(other).advance(|(i, w1, w2)| iterate_bits(i, w1 & w2, |b| f(&b)))
811 pub fn union(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
812 for (i, w1, w2) in self.commons(other) {
813 if !iterate_bits(i, w1 | w2, |b| f(&b)) {
817 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
821 impl cmp::PartialEq for BitvSet {
822 fn eq(&self, other: &BitvSet) -> bool {
823 if self.size != other.size {
826 for (_, w1, w2) in self.commons(other) {
831 for (_, _, w) in self.outliers(other) {
839 fn ne(&self, other: &BitvSet) -> bool { !self.eq(other) }
842 impl cmp::Eq for BitvSet {}
844 impl fmt::Show for BitvSet {
845 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
846 try!(write!(fmt, "{{"));
847 let mut first = true;
848 for n in self.iter() {
850 try!(write!(fmt, ", "));
852 try!(write!(fmt, "{}", n));
859 impl<S: hash::Writer> hash::Hash<S> for BitvSet {
860 fn hash(&self, state: &mut S) {
861 for pos in self.iter() {
867 impl Collection for BitvSet {
869 fn len(&self) -> uint { self.size }
872 impl Mutable for BitvSet {
873 fn clear(&mut self) {
874 self.bitv.each_storage(|w| { *w = 0; true });
879 impl Set<uint> for BitvSet {
880 fn contains(&self, value: &uint) -> bool {
881 *value < self.bitv.storage.len() * uint::BITS && self.bitv.get(*value)
884 fn is_disjoint(&self, other: &BitvSet) -> bool {
885 self.intersection(other, |_| false)
888 fn is_subset(&self, other: &BitvSet) -> bool {
889 for (_, w1, w2) in self.commons(other) {
894 /* If anything is not ours, then everything is not ours so we're
895 definitely a subset in that case. Otherwise if there's any stray
896 ones that 'other' doesn't have, we're not a subset. */
897 for (mine, _, w) in self.outliers(other) {
907 fn is_superset(&self, other: &BitvSet) -> bool {
908 other.is_subset(self)
912 impl MutableSet<uint> for BitvSet {
913 fn insert(&mut self, value: uint) -> bool {
914 if self.contains(&value) {
917 let nbits = self.capacity();
919 let newsize = cmp::max(value, nbits * 2) / uint::BITS + 1;
920 assert!(newsize > self.bitv.storage.len());
921 self.bitv.storage.grow(newsize, &0);
924 self.bitv.set(value, true);
928 fn remove(&mut self, value: &uint) -> bool {
929 if !self.contains(value) {
933 self.bitv.set(*value, false);
935 // Attempt to truncate our storage
936 let mut i = self.bitv.storage.len();
937 while i > 1 && *self.bitv.storage.get(i - 1) == 0 {
940 self.bitv.storage.truncate(i);
947 /// Visits each of the words that the two bit vectors (`self` and `other`)
948 /// both have in common. The three yielded arguments are (bit location,
949 /// w1, w2) where the bit location is the number of bits offset so far,
950 /// and w1/w2 are the words coming from the two vectors self, other.
951 fn commons<'a>(&'a self, other: &'a BitvSet)
952 -> Map<'static, ((uint, &'a uint), &'a Vec<uint>), (uint, uint, uint),
953 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<&'a Vec<uint>>>> {
954 let min = cmp::min(self.bitv.storage.len(), other.bitv.storage.len());
955 self.bitv.storage.slice(0, min).iter().enumerate()
956 .zip(Repeat::new(&other.bitv.storage))
957 .map(|((i, &w), o_store)| (i * uint::BITS, w, *o_store.get(i)))
960 /// Visits each word in `self` or `other` that extends beyond the other. This
961 /// will only iterate through one of the vectors, and it only iterates
962 /// over the portion that doesn't overlap with the other one.
964 /// The yielded arguments are a `bool`, the bit offset, and a word. The `bool`
965 /// is true if the word comes from `self`, and `false` if it comes from
967 fn outliers<'a>(&'a self, other: &'a BitvSet)
968 -> Map<'static, ((uint, &'a uint), uint), (bool, uint, uint),
969 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<uint>>> {
970 let slen = self.bitv.storage.len();
971 let olen = other.bitv.storage.len();
974 self.bitv.storage.slice_from(olen).iter().enumerate()
975 .zip(Repeat::new(olen))
976 .map(|((i, &w), min)| (true, (i + min) * uint::BITS, w))
978 other.bitv.storage.slice_from(slen).iter().enumerate()
979 .zip(Repeat::new(slen))
980 .map(|((i, &w), min)| (false, (i + min) * uint::BITS, w))
985 pub struct BitPositions<'a> {
990 impl<'a> Iterator<uint> for BitPositions<'a> {
992 fn next(&mut self) -> Option<uint> {
993 while self.next_idx < self.set.capacity() {
994 let idx = self.next_idx;
997 if self.set.contains(&idx) {
1005 fn size_hint(&self) -> (uint, Option<uint>) {
1006 (0, Some(self.set.capacity() - self.next_idx))
1012 use std::prelude::*;
1018 use {Set, Mutable, MutableSet};
1019 use bitv::{Bitv, SmallBitv, BigBitv, BitvSet, from_bools, from_fn,
1024 static BENCH_BITS : uint = 1 << 14;
1028 let zerolen = Bitv::new(0u, false);
1029 assert_eq!(zerolen.to_str().as_slice(), "");
1031 let eightbits = Bitv::new(8u, false);
1032 assert_eq!(eightbits.to_str().as_slice(), "00000000")
1036 fn test_0_elements() {
1037 let act = Bitv::new(0u, false);
1038 let exp = Vec::from_elem(0u, false);
1039 assert!(act.eq_vec(exp.as_slice()));
1043 fn test_1_element() {
1044 let mut act = Bitv::new(1u, false);
1045 assert!(act.eq_vec([false]));
1046 act = Bitv::new(1u, true);
1047 assert!(act.eq_vec([true]));
1051 fn test_2_elements() {
1052 let mut b = bitv::Bitv::new(2, false);
1055 assert_eq!(b.to_str().as_slice(), "10");
1059 fn test_10_elements() {
1063 act = Bitv::new(10u, false);
1064 assert!((act.eq_vec(
1065 [false, false, false, false, false, false, false, false, false, false])));
1068 act = Bitv::new(10u, true);
1069 assert!((act.eq_vec([true, true, true, true, true, true, true, true, true, true])));
1072 act = Bitv::new(10u, false);
1078 assert!((act.eq_vec([true, true, true, true, true, false, false, false, false, false])));
1081 act = Bitv::new(10u, false);
1087 assert!((act.eq_vec([false, false, false, false, false, true, true, true, true, true])));
1090 act = Bitv::new(10u, false);
1095 assert!((act.eq_vec([true, false, false, true, false, false, true, false, false, true])));
1099 fn test_31_elements() {
1103 act = Bitv::new(31u, false);
1105 [false, false, false, false, false, false, false, false, false, false, false,
1106 false, false, false, false, false, false, false, false, false, false, false, false,
1107 false, false, false, false, false, false, false, false]));
1110 act = Bitv::new(31u, true);
1112 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1113 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1114 true, true, true, true]));
1117 act = Bitv::new(31u, false);
1127 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1128 false, false, false, false, false, false, false, false, false, false, false, false,
1129 false, false, false, false, false, false]));
1132 act = Bitv::new(31u, false);
1142 [false, false, false, false, false, false, false, false, false, false, false,
1143 false, false, false, false, false, true, true, true, true, true, true, true, true,
1144 false, false, false, false, false, false, false]));
1147 act = Bitv::new(31u, false);
1156 [false, false, false, false, false, false, false, false, false, false, false,
1157 false, false, false, false, false, false, false, false, false, false, false, false,
1158 false, true, true, true, true, true, true, true]));
1161 act = Bitv::new(31u, false);
1166 [false, false, false, true, false, false, false, false, false, false, false, false,
1167 false, false, false, false, false, true, false, false, false, false, false, false,
1168 false, false, false, false, false, false, true]));
1172 fn test_32_elements() {
1176 act = Bitv::new(32u, false);
1178 [false, false, false, false, false, false, false, false, false, false, false,
1179 false, false, false, false, false, false, false, false, false, false, false, false,
1180 false, false, false, false, false, false, false, false, false]));
1183 act = Bitv::new(32u, true);
1185 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1186 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1187 true, true, true, true, true]));
1190 act = Bitv::new(32u, false);
1200 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1201 false, false, false, false, false, false, false, false, false, false, false, false,
1202 false, false, false, false, false, false, false]));
1205 act = Bitv::new(32u, false);
1215 [false, false, false, false, false, false, false, false, false, false, false,
1216 false, false, false, false, false, true, true, true, true, true, true, true, true,
1217 false, false, false, false, false, false, false, false]));
1220 act = Bitv::new(32u, false);
1230 [false, false, false, false, false, false, false, false, false, false, false,
1231 false, false, false, false, false, false, false, false, false, false, false, false,
1232 false, true, true, true, true, true, true, true, true]));
1235 act = Bitv::new(32u, false);
1241 [false, false, false, true, false, false, false, false, false, false, false, false,
1242 false, false, false, false, false, true, false, false, false, false, false, false,
1243 false, false, false, false, false, false, true, true]));
1247 fn test_33_elements() {
1251 act = Bitv::new(33u, false);
1253 [false, false, false, false, false, false, false, false, false, false, false,
1254 false, false, false, false, false, false, false, false, false, false, false, false,
1255 false, false, false, false, false, false, false, false, false, false]));
1258 act = Bitv::new(33u, true);
1260 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1261 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1262 true, true, true, true, true, true]));
1265 act = Bitv::new(33u, false);
1275 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1276 false, false, false, false, false, false, false, false, false, false, false, false,
1277 false, false, false, false, false, false, false, false]));
1280 act = Bitv::new(33u, false);
1290 [false, false, false, false, false, false, false, false, false, false, false,
1291 false, false, false, false, false, true, true, true, true, true, true, true, true,
1292 false, false, false, false, false, false, false, false, false]));
1295 act = Bitv::new(33u, false);
1305 [false, false, false, false, false, false, false, false, false, false, false,
1306 false, false, false, false, false, false, false, false, false, false, false, false,
1307 false, true, true, true, true, true, true, true, true, false]));
1310 act = Bitv::new(33u, false);
1317 [false, false, false, true, false, false, false, false, false, false, false, false,
1318 false, false, false, false, false, true, false, false, false, false, false, false,
1319 false, false, false, false, false, false, true, true, true]));
1323 fn test_equal_differing_sizes() {
1324 let v0 = Bitv::new(10u, false);
1325 let v1 = Bitv::new(11u, false);
1330 fn test_equal_greatly_differing_sizes() {
1331 let v0 = Bitv::new(10u, false);
1332 let v1 = Bitv::new(110u, false);
1337 fn test_equal_sneaky_small() {
1338 let mut a = bitv::Bitv::new(1, false);
1341 let mut b = bitv::Bitv::new(1, true);
1348 fn test_equal_sneaky_big() {
1349 let mut a = bitv::Bitv::new(100, false);
1350 for i in range(0u, 100) {
1354 let mut b = bitv::Bitv::new(100, true);
1355 for i in range(0u, 100) {
1363 fn test_from_bytes() {
1364 let bitv = from_bytes([0b10110110, 0b00000000, 0b11111111]);
1365 let str = format!("{}{}{}", "10110110", "00000000", "11111111");
1366 assert_eq!(bitv.to_str().as_slice(), str.as_slice());
1370 fn test_to_bytes() {
1371 let mut bv = Bitv::new(3, true);
1373 assert_eq!(bv.to_bytes(), vec!(0b10100000));
1375 let mut bv = Bitv::new(9, false);
1378 assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
1382 fn test_from_bools() {
1383 assert!(from_bools([true, false, true, true]).to_str().as_slice() ==
1388 fn test_to_bools() {
1389 let bools = vec!(false, false, true, false, false, true, true, false);
1390 assert_eq!(from_bytes([0b00100110]).to_bools(), bools);
1394 fn test_bitv_iterator() {
1395 let bools = [true, false, true, true];
1396 let bitv = from_bools(bools);
1398 for (act, &ex) in bitv.iter().zip(bools.iter()) {
1399 assert_eq!(ex, act);
1404 fn test_bitv_set_iterator() {
1405 let bools = [true, false, true, true];
1406 let bitv = BitvSet::from_bitv(from_bools(bools));
1408 let idxs: Vec<uint> = bitv.iter().collect();
1409 assert_eq!(idxs, vec!(0, 2, 3));
1413 fn test_bitv_set_frombitv_init() {
1414 let bools = [true, false];
1415 let lengths = [10, 64, 100];
1416 for &b in bools.iter() {
1417 for &l in lengths.iter() {
1418 let bitset = BitvSet::from_bitv(Bitv::new(l, b));
1419 assert_eq!(bitset.contains(&1u), b)
1420 assert_eq!(bitset.contains(&(l-1u)), b)
1421 assert!(!bitset.contains(&l))
1427 fn test_small_difference() {
1428 let mut b1 = Bitv::new(3, false);
1429 let mut b2 = Bitv::new(3, false);
1434 assert!(b1.difference(&b2));
1441 fn test_big_difference() {
1442 let mut b1 = Bitv::new(100, false);
1443 let mut b2 = Bitv::new(100, false);
1448 assert!(b1.difference(&b2));
1455 fn test_small_clear() {
1456 let mut b = Bitv::new(14, true);
1459 fail!("found 1 at {:?}", i)
1464 fn test_big_clear() {
1465 let mut b = Bitv::new(140, true);
1468 fail!("found 1 at {:?}", i)
1473 fn test_bitv_set_basic() {
1474 let mut b = BitvSet::new();
1475 assert!(b.insert(3));
1476 assert!(!b.insert(3));
1477 assert!(b.contains(&3));
1478 assert!(b.insert(400));
1479 assert!(!b.insert(400));
1480 assert!(b.contains(&400));
1481 assert_eq!(b.len(), 2);
1485 fn test_bitv_set_intersection() {
1486 let mut a = BitvSet::new();
1487 let mut b = BitvSet::new();
1489 assert!(a.insert(11));
1490 assert!(a.insert(1));
1491 assert!(a.insert(3));
1492 assert!(a.insert(77));
1493 assert!(a.insert(103));
1494 assert!(a.insert(5));
1496 assert!(b.insert(2));
1497 assert!(b.insert(11));
1498 assert!(b.insert(77));
1499 assert!(b.insert(5));
1500 assert!(b.insert(3));
1503 let expected = [3, 5, 11, 77];
1504 a.intersection(&b, |x| {
1505 assert_eq!(*x, expected[i]);
1509 assert_eq!(i, expected.len());
1513 fn test_bitv_set_difference() {
1514 let mut a = BitvSet::new();
1515 let mut b = BitvSet::new();
1517 assert!(a.insert(1));
1518 assert!(a.insert(3));
1519 assert!(a.insert(5));
1520 assert!(a.insert(200));
1521 assert!(a.insert(500));
1523 assert!(b.insert(3));
1524 assert!(b.insert(200));
1527 let expected = [1, 5, 500];
1528 a.difference(&b, |x| {
1529 assert_eq!(*x, expected[i]);
1533 assert_eq!(i, expected.len());
1537 fn test_bitv_set_symmetric_difference() {
1538 let mut a = BitvSet::new();
1539 let mut b = BitvSet::new();
1541 assert!(a.insert(1));
1542 assert!(a.insert(3));
1543 assert!(a.insert(5));
1544 assert!(a.insert(9));
1545 assert!(a.insert(11));
1547 assert!(b.insert(3));
1548 assert!(b.insert(9));
1549 assert!(b.insert(14));
1550 assert!(b.insert(220));
1553 let expected = [1, 5, 11, 14, 220];
1554 a.symmetric_difference(&b, |x| {
1555 assert_eq!(*x, expected[i]);
1559 assert_eq!(i, expected.len());
1563 fn test_bitv_set_union() {
1564 let mut a = BitvSet::new();
1565 let mut b = BitvSet::new();
1566 assert!(a.insert(1));
1567 assert!(a.insert(3));
1568 assert!(a.insert(5));
1569 assert!(a.insert(9));
1570 assert!(a.insert(11));
1571 assert!(a.insert(160));
1572 assert!(a.insert(19));
1573 assert!(a.insert(24));
1575 assert!(b.insert(1));
1576 assert!(b.insert(5));
1577 assert!(b.insert(9));
1578 assert!(b.insert(13));
1579 assert!(b.insert(19));
1582 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160];
1584 assert_eq!(*x, expected[i]);
1588 assert_eq!(i, expected.len());
1592 fn test_bitv_remove() {
1593 let mut a = BitvSet::new();
1595 assert!(a.insert(1));
1596 assert!(a.remove(&1));
1598 assert!(a.insert(100));
1599 assert!(a.remove(&100));
1601 assert!(a.insert(1000));
1602 assert!(a.remove(&1000));
1603 assert_eq!(a.capacity(), uint::BITS);
1607 fn test_bitv_clone() {
1608 let mut a = BitvSet::new();
1610 assert!(a.insert(1));
1611 assert!(a.insert(100));
1612 assert!(a.insert(1000));
1614 let mut b = a.clone();
1618 assert!(b.remove(&1));
1619 assert!(a.contains(&1));
1621 assert!(a.remove(&1000));
1622 assert!(b.contains(&1000));
1626 fn test_small_bitv_tests() {
1627 let v = from_bytes([0]);
1632 let v = from_bytes([0b00010100]);
1637 let v = from_bytes([0xFF]);
1644 fn test_big_bitv_tests() {
1645 let v = from_bytes([ // 88 bits
1653 let v = from_bytes([ // 88 bits
1654 0, 0, 0b00010100, 0,
1655 0, 0, 0, 0b00110100,
1661 let v = from_bytes([ // 88 bits
1662 0xFF, 0xFF, 0xFF, 0xFF,
1663 0xFF, 0xFF, 0xFF, 0xFF,
1671 fn test_bitv_set_show() {
1672 let mut s = BitvSet::new();
1677 assert_eq!("{1, 2, 10, 50}".to_string(), s.to_str());
1680 fn rng() -> rand::IsaacRng {
1681 let seed = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
1682 rand::SeedableRng::from_seed(seed)
1686 fn bench_uint_small(b: &mut Bencher) {
1688 let mut bitv = 0 as uint;
1690 bitv |= 1 << ((r.next_u32() as uint) % uint::BITS);
1696 fn bench_small_bitv_small(b: &mut Bencher) {
1698 let mut bitv = SmallBitv::new(uint::BITS);
1700 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1706 fn bench_big_bitv_small(b: &mut Bencher) {
1708 let mut bitv = BigBitv::new(vec!(0));
1710 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1716 fn bench_big_bitv_big(b: &mut Bencher) {
1718 let mut storage = vec!();
1719 storage.grow(BENCH_BITS / uint::BITS, &0u);
1720 let mut bitv = BigBitv::new(storage);
1722 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1728 fn bench_bitv_big(b: &mut Bencher) {
1730 let mut bitv = Bitv::new(BENCH_BITS, false);
1732 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1738 fn bench_bitv_small(b: &mut Bencher) {
1740 let mut bitv = Bitv::new(uint::BITS, false);
1742 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1748 fn bench_bitv_set_small(b: &mut Bencher) {
1750 let mut bitv = BitvSet::new();
1752 bitv.insert((r.next_u32() as uint) % uint::BITS);
1758 fn bench_bitv_set_big(b: &mut Bencher) {
1760 let mut bitv = BitvSet::new();
1762 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
1768 fn bench_bitv_big_union(b: &mut Bencher) {
1769 let mut b1 = Bitv::new(BENCH_BITS, false);
1770 let b2 = Bitv::new(BENCH_BITS, false);
1777 fn bench_btv_small_iter(b: &mut Bencher) {
1778 let bitv = Bitv::new(uint::BITS, false);
1781 for pres in bitv.iter() {
1782 _sum += pres as uint;
1788 fn bench_bitv_big_iter(b: &mut Bencher) {
1789 let bitv = Bitv::new(BENCH_BITS, false);
1792 for pres in bitv.iter() {
1793 _sum += pres as uint;
1799 fn bench_bitvset_iter(b: &mut Bencher) {
1800 let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
1801 |idx| {idx % 3 == 0}));
1804 for idx in bitv.iter() {