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)
380 * Compares two bitvectors
382 * Both bitvectors must be the same length. Returns `true` if both
383 * bitvectors contain identical elements.
386 pub fn equal(&self, v1: &Bitv) -> bool {
387 if self.nbits != v1.nbits { return false; }
389 Small(ref b) => match v1.rep {
390 Small(ref b1) => b.equals(b1, self.nbits),
393 Big(ref s) => match v1.rep {
394 Big(ref s1) => s.equals(s1, self.nbits),
395 Small(_) => return false
400 /// Set all bits to 0
402 pub fn clear(&mut self) {
404 Small(ref mut b) => b.clear(),
406 s.each_storage(|w| { *w = 0u; true });
411 /// Set all bits to 1
413 pub fn set_all(&mut self) {
415 Small(ref mut b) => b.set_all(),
417 s.each_storage(|w| { *w = !0u; true });
424 pub fn negate(&mut self) {
426 Small(ref mut s) => s.negate(),
427 Big(ref mut b) => b.negate(),
432 * Calculate the difference between two bitvectors
434 * Sets each element of `v0` to the value of that element minus the
435 * element of `v1` at the same index. Both bitvectors must be the same
438 * Returns `true` if `v0` was changed.
441 pub fn difference(&mut self, v: &Bitv) -> bool {
442 self.do_op(Difference, v)
445 /// Returns `true` if all bits are 1
447 pub fn all(&self) -> bool {
449 Small(ref b) => b.all(self.nbits),
450 _ => self.iter().all(|x| x)
454 /// Returns an iterator over the elements of the vector in order.
459 /// use collections::bitv::Bitv;
460 /// let mut bv = Bitv::new(10, false);
466 /// // Count bits set to 1; result should be 5
467 /// println!("{}", bv.iter().filter(|x| *x).count());
470 pub fn iter<'a>(&'a self) -> Bits<'a> {
471 Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
474 /// Returns `true` if all bits are 0
475 pub fn none(&self) -> bool {
477 Small(ref b) => b.none(self.nbits),
478 _ => self.iter().all(|x| !x)
483 /// Returns `true` if any bit is 1
484 pub fn any(&self) -> bool {
489 * Converts `self` to a vector of `uint` with the same length.
491 * Each `uint` in the resulting vector has either value `0u` or `1u`.
493 pub fn to_vec(&self) -> Vec<uint> {
494 Vec::from_fn(self.nbits, |i| if self.get(i) { 1 } else { 0 })
498 * Organise the bits into bytes, such that the first bit in the
499 * `Bitv` becomes the high-order bit of the first byte. If the
500 * size of the `Bitv` is not a multiple of 8 then trailing bits
501 * will be filled-in with false/0
503 pub fn to_bytes(&self) -> Vec<u8> {
504 fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
505 let offset = byte * 8 + bit;
506 if offset >= bitv.nbits {
509 bitv[offset] as u8 << (7 - bit)
513 let len = self.nbits/8 +
514 if self.nbits % 8 == 0 { 0 } else { 1 };
515 Vec::from_fn(len, |i|
528 * Transform `self` into a `Vec<bool>` by turning each bit into a `bool`.
530 pub fn to_bools(&self) -> Vec<bool> {
531 Vec::from_fn(self.nbits, |i| self[i])
535 * Compare a bitvector to a vector of `bool`.
537 * Both the bitvector and vector must have the same length.
539 pub fn eq_vec(&self, v: &[bool]) -> bool {
540 assert_eq!(self.nbits, v.len());
542 while i < self.nbits {
543 if self.get(i) != v[i] { return false; }
549 pub fn ones(&self, f: |uint| -> bool) -> bool {
550 range(0u, self.nbits).advance(|i| !self.get(i) || f(i))
556 * Transform a byte-vector into a `Bitv`. Each byte becomes 8 bits,
557 * with the most significant bits of each byte coming first. Each
558 * bit becomes `true` if equal to 1 or `false` if equal to 0.
560 pub fn from_bytes(bytes: &[u8]) -> Bitv {
561 from_fn(bytes.len() * 8, |i| {
562 let b = bytes[i / 8] as uint;
564 b >> (7 - offset) & 1 == 1
569 * Transform a `[bool]` into a `Bitv` by converting each `bool` into a bit.
571 pub fn from_bools(bools: &[bool]) -> Bitv {
572 from_fn(bools.len(), |i| bools[i])
576 * Create a `Bitv` of the specified length where the value at each
577 * index is `f(index)`.
579 pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
580 let mut bitv = Bitv::new(len, false);
581 for i in range(0u, len) {
587 impl ops::Index<uint,bool> for Bitv {
588 fn index(&self, i: &uint) -> bool {
593 impl fmt::Show for Bitv {
594 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
595 for bit in self.iter() {
596 try!(write!(fmt, "{}", if bit { 1 } else { 0 }));
602 impl<S: hash::Writer> hash::Hash<S> for Bitv {
603 fn hash(&self, state: &mut S) {
604 self.nbits.hash(state);
606 Small(ref s) => (s.bits & small_mask(self.nbits)).hash(state),
608 for (i, ele) in b.storage.iter().enumerate() {
609 (ele & big_mask(self.nbits, i)).hash(state);
617 fn iterate_bits(base: uint, bits: uint, f: |uint| -> bool) -> bool {
621 for i in range(0u, uint::BITS) {
622 if bits & (1 << i) != 0 {
631 /// An iterator for `Bitv`.
632 pub struct Bits<'a> {
638 impl<'a> Iterator<bool> for Bits<'a> {
640 fn next(&mut self) -> Option<bool> {
641 if self.next_idx != self.end_idx {
642 let idx = self.next_idx;
644 Some(self.bitv.get(idx))
650 fn size_hint(&self) -> (uint, Option<uint>) {
651 let rem = self.end_idx - self.next_idx;
656 impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
658 fn next_back(&mut self) -> Option<bool> {
659 if self.next_idx != self.end_idx {
661 Some(self.bitv.get(self.end_idx))
668 impl<'a> ExactSize<bool> for Bits<'a> {}
670 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
672 fn indexable(&self) -> uint {
673 self.end_idx - self.next_idx
677 fn idx(&mut self, index: uint) -> Option<bool> {
678 if index >= self.indexable() {
681 Some(self.bitv.get(index))
686 /// An implementation of a set using a bit vector as an underlying
687 /// representation for holding numerical elements.
689 /// It should also be noted that the amount of storage necessary for holding a
690 /// set of objects is proportional to the maximum of the objects when viewed
696 // In theory this is a `Bitv` instead of always a `BigBitv`, but knowing that
697 // there's an array of storage makes our lives a whole lot easier when
698 // performing union/intersection/etc operations
702 impl Default for BitvSet {
704 fn default() -> BitvSet { BitvSet::new() }
708 /// Creates a new bit vector set with initially no contents
709 pub fn new() -> BitvSet {
710 BitvSet{ size: 0, bitv: BigBitv::new(vec!(0)) }
713 /// Creates a new bit vector set from the given bit vector
714 pub fn from_bitv(bitv: Bitv) -> BitvSet {
720 let Bitv{rep, ..} = bitv;
722 Big(b) => BitvSet{ size: size, bitv: b },
723 Small(SmallBitv{bits}) =>
724 BitvSet{ size: size, bitv: BigBitv{ storage: vec!(bits) } },
728 /// Returns the capacity in bits for this bit vector. Inserting any
729 /// element less than this amount will not trigger a resizing.
730 pub fn capacity(&self) -> uint { self.bitv.storage.len() * uint::BITS }
732 /// Consumes this set to return the underlying bit vector
733 pub fn unwrap(self) -> Bitv {
734 let cap = self.capacity();
735 let BitvSet{bitv, ..} = self;
736 return Bitv{ nbits:cap, rep: Big(bitv) };
740 fn other_op(&mut self, other: &BitvSet, f: |uint, uint| -> uint) {
741 fn nbits(mut w: uint) -> uint {
743 for _ in range(0u, uint::BITS) {
752 if self.capacity() < other.capacity() {
753 self.bitv.storage.grow(other.capacity() / uint::BITS, &0);
755 for (i, &w) in other.bitv.storage.iter().enumerate() {
756 let old = *self.bitv.storage.get(i);
758 *self.bitv.storage.get_mut(i) = new;
759 self.size += nbits(new) - nbits(old);
763 /// Union in-place with the specified other bit vector
764 pub fn union_with(&mut self, other: &BitvSet) {
765 self.other_op(other, |w1, w2| w1 | w2);
768 /// Intersect in-place with the specified other bit vector
769 pub fn intersect_with(&mut self, other: &BitvSet) {
770 self.other_op(other, |w1, w2| w1 & w2);
773 /// Difference in-place with the specified other bit vector
774 pub fn difference_with(&mut self, other: &BitvSet) {
775 self.other_op(other, |w1, w2| w1 & !w2);
778 /// Symmetric difference in-place with the specified other bit vector
779 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
780 self.other_op(other, |w1, w2| w1 ^ w2);
783 pub fn iter<'a>(&'a self) -> BitPositions<'a> {
784 BitPositions {set: self, next_idx: 0}
787 pub fn difference(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
788 for (i, w1, w2) in self.commons(other) {
789 if !iterate_bits(i, w1 & !w2, |b| f(&b)) {
793 /* everything we have that they don't also shows up */
794 self.outliers(other).advance(|(mine, i, w)|
795 !mine || iterate_bits(i, w, |b| f(&b))
799 pub fn symmetric_difference(&self, other: &BitvSet, f: |&uint| -> bool)
801 for (i, w1, w2) in self.commons(other) {
802 if !iterate_bits(i, w1 ^ w2, |b| f(&b)) {
806 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
809 pub fn intersection(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
810 self.commons(other).advance(|(i, w1, w2)| iterate_bits(i, w1 & w2, |b| f(&b)))
813 pub fn union(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
814 for (i, w1, w2) in self.commons(other) {
815 if !iterate_bits(i, w1 | w2, |b| f(&b)) {
819 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
823 impl cmp::PartialEq for BitvSet {
824 fn eq(&self, other: &BitvSet) -> bool {
825 if self.size != other.size {
828 for (_, w1, w2) in self.commons(other) {
833 for (_, _, w) in self.outliers(other) {
841 fn ne(&self, other: &BitvSet) -> bool { !self.eq(other) }
844 impl fmt::Show for BitvSet {
846 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
847 try!(write!(fmt, r"\{"));
848 let mut first = true;
849 for n in self.iter() {
851 try!(write!(fmt, ", "));
853 try!(write!(fmt, "{}", n));
859 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
860 try!(write!(fmt, "{{"));
861 let mut first = true;
862 for n in self.iter() {
864 try!(write!(fmt, ", "));
866 try!(write!(fmt, "{}", n));
873 impl<S: hash::Writer> hash::Hash<S> for BitvSet {
874 fn hash(&self, state: &mut S) {
875 for pos in self.iter() {
881 impl Collection for BitvSet {
883 fn len(&self) -> uint { self.size }
886 impl Mutable for BitvSet {
887 fn clear(&mut self) {
888 self.bitv.each_storage(|w| { *w = 0; true });
893 impl Set<uint> for BitvSet {
894 fn contains(&self, value: &uint) -> bool {
895 *value < self.bitv.storage.len() * uint::BITS && self.bitv.get(*value)
898 fn is_disjoint(&self, other: &BitvSet) -> bool {
899 self.intersection(other, |_| false)
902 fn is_subset(&self, other: &BitvSet) -> bool {
903 for (_, w1, w2) in self.commons(other) {
908 /* If anything is not ours, then everything is not ours so we're
909 definitely a subset in that case. Otherwise if there's any stray
910 ones that 'other' doesn't have, we're not a subset. */
911 for (mine, _, w) in self.outliers(other) {
921 fn is_superset(&self, other: &BitvSet) -> bool {
922 other.is_subset(self)
926 impl MutableSet<uint> for BitvSet {
927 fn insert(&mut self, value: uint) -> bool {
928 if self.contains(&value) {
931 let nbits = self.capacity();
933 let newsize = cmp::max(value, nbits * 2) / uint::BITS + 1;
934 assert!(newsize > self.bitv.storage.len());
935 self.bitv.storage.grow(newsize, &0);
938 self.bitv.set(value, true);
942 fn remove(&mut self, value: &uint) -> bool {
943 if !self.contains(value) {
947 self.bitv.set(*value, false);
949 // Attempt to truncate our storage
950 let mut i = self.bitv.storage.len();
951 while i > 1 && *self.bitv.storage.get(i - 1) == 0 {
954 self.bitv.storage.truncate(i);
961 /// Visits each of the words that the two bit vectors (`self` and `other`)
962 /// both have in common. The three yielded arguments are (bit location,
963 /// w1, w2) where the bit location is the number of bits offset so far,
964 /// and w1/w2 are the words coming from the two vectors self, other.
965 fn commons<'a>(&'a self, other: &'a BitvSet)
966 -> Map<'static, ((uint, &'a uint), &'a Vec<uint>), (uint, uint, uint),
967 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<&'a Vec<uint>>>> {
968 let min = cmp::min(self.bitv.storage.len(), other.bitv.storage.len());
969 self.bitv.storage.slice(0, min).iter().enumerate()
970 .zip(Repeat::new(&other.bitv.storage))
971 .map(|((i, &w), o_store)| (i * uint::BITS, w, *o_store.get(i)))
974 /// Visits each word in `self` or `other` that extends beyond the other. This
975 /// will only iterate through one of the vectors, and it only iterates
976 /// over the portion that doesn't overlap with the other one.
978 /// The yielded arguments are a `bool`, the bit offset, and a word. The `bool`
979 /// is true if the word comes from `self`, and `false` if it comes from
981 fn outliers<'a>(&'a self, other: &'a BitvSet)
982 -> Map<'static, ((uint, &'a uint), uint), (bool, uint, uint),
983 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<uint>>> {
984 let slen = self.bitv.storage.len();
985 let olen = other.bitv.storage.len();
988 self.bitv.storage.slice_from(olen).iter().enumerate()
989 .zip(Repeat::new(olen))
990 .map(|((i, &w), min)| (true, (i + min) * uint::BITS, w))
992 other.bitv.storage.slice_from(slen).iter().enumerate()
993 .zip(Repeat::new(slen))
994 .map(|((i, &w), min)| (false, (i + min) * uint::BITS, w))
999 pub struct BitPositions<'a> {
1004 impl<'a> Iterator<uint> for BitPositions<'a> {
1006 fn next(&mut self) -> Option<uint> {
1007 while self.next_idx < self.set.capacity() {
1008 let idx = self.next_idx;
1011 if self.set.contains(&idx) {
1019 fn size_hint(&self) -> (uint, Option<uint>) {
1020 (0, Some(self.set.capacity() - self.next_idx))
1026 use std::prelude::*;
1032 use {Set, Mutable, MutableSet};
1033 use bitv::{Bitv, SmallBitv, BigBitv, BitvSet, from_bools, from_fn,
1038 static BENCH_BITS : uint = 1 << 14;
1042 let zerolen = Bitv::new(0u, false);
1043 assert_eq!(zerolen.to_str().as_slice(), "");
1045 let eightbits = Bitv::new(8u, false);
1046 assert_eq!(eightbits.to_str().as_slice(), "00000000")
1050 fn test_0_elements() {
1051 let act = Bitv::new(0u, false);
1052 let exp = Vec::from_elem(0u, false);
1053 assert!(act.eq_vec(exp.as_slice()));
1057 fn test_1_element() {
1058 let mut act = Bitv::new(1u, false);
1059 assert!(act.eq_vec([false]));
1060 act = Bitv::new(1u, true);
1061 assert!(act.eq_vec([true]));
1065 fn test_2_elements() {
1066 let mut b = bitv::Bitv::new(2, false);
1069 assert_eq!(b.to_str().as_slice(), "10");
1073 fn test_10_elements() {
1077 act = Bitv::new(10u, false);
1078 assert!((act.eq_vec(
1079 [false, false, false, false, false, false, false, false, false, false])));
1082 act = Bitv::new(10u, true);
1083 assert!((act.eq_vec([true, true, true, true, true, true, true, true, true, true])));
1086 act = Bitv::new(10u, false);
1092 assert!((act.eq_vec([true, true, true, true, true, false, false, false, false, false])));
1095 act = Bitv::new(10u, false);
1101 assert!((act.eq_vec([false, false, false, false, false, true, true, true, true, true])));
1104 act = Bitv::new(10u, false);
1109 assert!((act.eq_vec([true, false, false, true, false, false, true, false, false, true])));
1113 fn test_31_elements() {
1117 act = Bitv::new(31u, false);
1119 [false, false, false, false, false, false, false, false, false, false, false,
1120 false, false, false, false, false, false, false, false, false, false, false, false,
1121 false, false, false, false, false, false, false, false]));
1124 act = Bitv::new(31u, true);
1126 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1127 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1128 true, true, true, true]));
1131 act = Bitv::new(31u, false);
1141 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1142 false, false, false, false, false, false, false, false, false, false, false, false,
1143 false, false, false, false, false, false]));
1146 act = Bitv::new(31u, false);
1156 [false, false, false, false, false, false, false, false, false, false, false,
1157 false, false, false, false, false, true, true, true, true, true, true, true, true,
1158 false, false, false, false, false, false, false]));
1161 act = Bitv::new(31u, false);
1170 [false, false, false, false, false, false, false, false, false, false, false,
1171 false, false, false, false, false, false, false, false, false, false, false, false,
1172 false, true, true, true, true, true, true, true]));
1175 act = Bitv::new(31u, false);
1180 [false, false, false, true, false, false, false, false, false, false, false, false,
1181 false, false, false, false, false, true, false, false, false, false, false, false,
1182 false, false, false, false, false, false, true]));
1186 fn test_32_elements() {
1190 act = Bitv::new(32u, false);
1192 [false, false, false, false, false, false, false, false, false, false, false,
1193 false, false, false, false, false, false, false, false, false, false, false, false,
1194 false, false, false, false, false, false, false, false, false]));
1197 act = Bitv::new(32u, true);
1199 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1200 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1201 true, true, true, true, true]));
1204 act = Bitv::new(32u, false);
1214 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1215 false, false, false, false, false, false, false, false, false, false, false, false,
1216 false, false, false, false, false, false, false]));
1219 act = Bitv::new(32u, false);
1229 [false, false, false, false, false, false, false, false, false, false, false,
1230 false, false, false, false, false, true, true, true, true, true, true, true, true,
1231 false, false, false, false, false, false, false, false]));
1234 act = Bitv::new(32u, false);
1244 [false, false, false, false, false, false, false, false, false, false, false,
1245 false, false, false, false, false, false, false, false, false, false, false, false,
1246 false, true, true, true, true, true, true, true, true]));
1249 act = Bitv::new(32u, false);
1255 [false, false, false, true, false, false, false, false, false, false, false, false,
1256 false, false, false, false, false, true, false, false, false, false, false, false,
1257 false, false, false, false, false, false, true, true]));
1261 fn test_33_elements() {
1265 act = Bitv::new(33u, false);
1267 [false, false, false, false, false, false, false, false, false, false, false,
1268 false, false, false, false, false, false, false, false, false, false, false, false,
1269 false, false, false, false, false, false, false, false, false, false]));
1272 act = Bitv::new(33u, true);
1274 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1275 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1276 true, true, true, true, true, true]));
1279 act = Bitv::new(33u, false);
1289 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1290 false, false, false, false, false, false, false, false, false, false, false, false,
1291 false, false, false, false, false, false, false, false]));
1294 act = Bitv::new(33u, false);
1304 [false, false, false, false, false, false, false, false, false, false, false,
1305 false, false, false, false, false, true, true, true, true, true, true, true, true,
1306 false, false, false, false, false, false, false, false, false]));
1309 act = Bitv::new(33u, false);
1319 [false, false, false, false, false, false, false, false, false, false, false,
1320 false, false, false, false, false, false, false, false, false, false, false, false,
1321 false, true, true, true, true, true, true, true, true, false]));
1324 act = Bitv::new(33u, false);
1331 [false, false, false, true, false, false, false, false, false, false, false, false,
1332 false, false, false, false, false, true, false, false, false, false, false, false,
1333 false, false, false, false, false, false, true, true, true]));
1337 fn test_equal_differing_sizes() {
1338 let v0 = Bitv::new(10u, false);
1339 let v1 = Bitv::new(11u, false);
1340 assert!(!v0.equal(&v1));
1344 fn test_equal_greatly_differing_sizes() {
1345 let v0 = Bitv::new(10u, false);
1346 let v1 = Bitv::new(110u, false);
1347 assert!(!v0.equal(&v1));
1351 fn test_equal_sneaky_small() {
1352 let mut a = bitv::Bitv::new(1, false);
1355 let mut b = bitv::Bitv::new(1, true);
1358 assert!(a.equal(&b));
1362 fn test_equal_sneaky_big() {
1363 let mut a = bitv::Bitv::new(100, false);
1364 for i in range(0u, 100) {
1368 let mut b = bitv::Bitv::new(100, true);
1369 for i in range(0u, 100) {
1373 assert!(a.equal(&b));
1377 fn test_from_bytes() {
1378 let bitv = from_bytes([0b10110110, 0b00000000, 0b11111111]);
1379 let str = format!("{}{}{}", "10110110", "00000000", "11111111");
1380 assert_eq!(bitv.to_str().as_slice(), str.as_slice());
1384 fn test_to_bytes() {
1385 let mut bv = Bitv::new(3, true);
1387 assert_eq!(bv.to_bytes(), vec!(0b10100000));
1389 let mut bv = Bitv::new(9, false);
1392 assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
1396 fn test_from_bools() {
1397 assert!(from_bools([true, false, true, true]).to_str().as_slice() ==
1402 fn test_to_bools() {
1403 let bools = vec!(false, false, true, false, false, true, true, false);
1404 assert_eq!(from_bytes([0b00100110]).to_bools(), bools);
1408 fn test_bitv_iterator() {
1409 let bools = [true, false, true, true];
1410 let bitv = from_bools(bools);
1412 for (act, &ex) in bitv.iter().zip(bools.iter()) {
1413 assert_eq!(ex, act);
1418 fn test_bitv_set_iterator() {
1419 let bools = [true, false, true, true];
1420 let bitv = BitvSet::from_bitv(from_bools(bools));
1422 let idxs: Vec<uint> = bitv.iter().collect();
1423 assert_eq!(idxs, vec!(0, 2, 3));
1427 fn test_bitv_set_frombitv_init() {
1428 let bools = [true, false];
1429 let lengths = [10, 64, 100];
1430 for &b in bools.iter() {
1431 for &l in lengths.iter() {
1432 let bitset = BitvSet::from_bitv(Bitv::new(l, b));
1433 assert_eq!(bitset.contains(&1u), b)
1434 assert_eq!(bitset.contains(&(l-1u)), b)
1435 assert!(!bitset.contains(&l))
1441 fn test_small_difference() {
1442 let mut b1 = Bitv::new(3, false);
1443 let mut b2 = Bitv::new(3, false);
1448 assert!(b1.difference(&b2));
1455 fn test_big_difference() {
1456 let mut b1 = Bitv::new(100, false);
1457 let mut b2 = Bitv::new(100, false);
1462 assert!(b1.difference(&b2));
1469 fn test_small_clear() {
1470 let mut b = Bitv::new(14, true);
1473 fail!("found 1 at {:?}", i)
1478 fn test_big_clear() {
1479 let mut b = Bitv::new(140, true);
1482 fail!("found 1 at {:?}", i)
1487 fn test_bitv_set_basic() {
1488 let mut b = BitvSet::new();
1489 assert!(b.insert(3));
1490 assert!(!b.insert(3));
1491 assert!(b.contains(&3));
1492 assert!(b.insert(400));
1493 assert!(!b.insert(400));
1494 assert!(b.contains(&400));
1495 assert_eq!(b.len(), 2);
1499 fn test_bitv_set_intersection() {
1500 let mut a = BitvSet::new();
1501 let mut b = BitvSet::new();
1503 assert!(a.insert(11));
1504 assert!(a.insert(1));
1505 assert!(a.insert(3));
1506 assert!(a.insert(77));
1507 assert!(a.insert(103));
1508 assert!(a.insert(5));
1510 assert!(b.insert(2));
1511 assert!(b.insert(11));
1512 assert!(b.insert(77));
1513 assert!(b.insert(5));
1514 assert!(b.insert(3));
1517 let expected = [3, 5, 11, 77];
1518 a.intersection(&b, |x| {
1519 assert_eq!(*x, expected[i]);
1523 assert_eq!(i, expected.len());
1527 fn test_bitv_set_difference() {
1528 let mut a = BitvSet::new();
1529 let mut b = BitvSet::new();
1531 assert!(a.insert(1));
1532 assert!(a.insert(3));
1533 assert!(a.insert(5));
1534 assert!(a.insert(200));
1535 assert!(a.insert(500));
1537 assert!(b.insert(3));
1538 assert!(b.insert(200));
1541 let expected = [1, 5, 500];
1542 a.difference(&b, |x| {
1543 assert_eq!(*x, expected[i]);
1547 assert_eq!(i, expected.len());
1551 fn test_bitv_set_symmetric_difference() {
1552 let mut a = BitvSet::new();
1553 let mut b = BitvSet::new();
1555 assert!(a.insert(1));
1556 assert!(a.insert(3));
1557 assert!(a.insert(5));
1558 assert!(a.insert(9));
1559 assert!(a.insert(11));
1561 assert!(b.insert(3));
1562 assert!(b.insert(9));
1563 assert!(b.insert(14));
1564 assert!(b.insert(220));
1567 let expected = [1, 5, 11, 14, 220];
1568 a.symmetric_difference(&b, |x| {
1569 assert_eq!(*x, expected[i]);
1573 assert_eq!(i, expected.len());
1577 fn test_bitv_set_union() {
1578 let mut a = BitvSet::new();
1579 let mut b = BitvSet::new();
1580 assert!(a.insert(1));
1581 assert!(a.insert(3));
1582 assert!(a.insert(5));
1583 assert!(a.insert(9));
1584 assert!(a.insert(11));
1585 assert!(a.insert(160));
1586 assert!(a.insert(19));
1587 assert!(a.insert(24));
1589 assert!(b.insert(1));
1590 assert!(b.insert(5));
1591 assert!(b.insert(9));
1592 assert!(b.insert(13));
1593 assert!(b.insert(19));
1596 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160];
1598 assert_eq!(*x, expected[i]);
1602 assert_eq!(i, expected.len());
1606 fn test_bitv_remove() {
1607 let mut a = BitvSet::new();
1609 assert!(a.insert(1));
1610 assert!(a.remove(&1));
1612 assert!(a.insert(100));
1613 assert!(a.remove(&100));
1615 assert!(a.insert(1000));
1616 assert!(a.remove(&1000));
1617 assert_eq!(a.capacity(), uint::BITS);
1621 fn test_bitv_clone() {
1622 let mut a = BitvSet::new();
1624 assert!(a.insert(1));
1625 assert!(a.insert(100));
1626 assert!(a.insert(1000));
1628 let mut b = a.clone();
1632 assert!(b.remove(&1));
1633 assert!(a.contains(&1));
1635 assert!(a.remove(&1000));
1636 assert!(b.contains(&1000));
1640 fn test_small_bitv_tests() {
1641 let v = from_bytes([0]);
1646 let v = from_bytes([0b00010100]);
1651 let v = from_bytes([0xFF]);
1658 fn test_big_bitv_tests() {
1659 let v = from_bytes([ // 88 bits
1667 let v = from_bytes([ // 88 bits
1668 0, 0, 0b00010100, 0,
1669 0, 0, 0, 0b00110100,
1675 let v = from_bytes([ // 88 bits
1676 0xFF, 0xFF, 0xFF, 0xFF,
1677 0xFF, 0xFF, 0xFF, 0xFF,
1685 fn test_bitv_set_show() {
1686 let mut s = BitvSet::new();
1691 assert_eq!("{1, 2, 10, 50}".to_string(), s.to_str());
1694 fn rng() -> rand::IsaacRng {
1695 let seed = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
1696 rand::SeedableRng::from_seed(seed)
1700 fn bench_uint_small(b: &mut Bencher) {
1702 let mut bitv = 0 as uint;
1704 bitv |= 1 << ((r.next_u32() as uint) % uint::BITS);
1710 fn bench_small_bitv_small(b: &mut Bencher) {
1712 let mut bitv = SmallBitv::new(uint::BITS);
1714 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1720 fn bench_big_bitv_small(b: &mut Bencher) {
1722 let mut bitv = BigBitv::new(vec!(0));
1724 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1730 fn bench_big_bitv_big(b: &mut Bencher) {
1732 let mut storage = vec!();
1733 storage.grow(BENCH_BITS / uint::BITS, &0u);
1734 let mut bitv = BigBitv::new(storage);
1736 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1742 fn bench_bitv_big(b: &mut Bencher) {
1744 let mut bitv = Bitv::new(BENCH_BITS, false);
1746 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1752 fn bench_bitv_small(b: &mut Bencher) {
1754 let mut bitv = Bitv::new(uint::BITS, false);
1756 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1762 fn bench_bitv_set_small(b: &mut Bencher) {
1764 let mut bitv = BitvSet::new();
1766 bitv.insert((r.next_u32() as uint) % uint::BITS);
1772 fn bench_bitv_set_big(b: &mut Bencher) {
1774 let mut bitv = BitvSet::new();
1776 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
1782 fn bench_bitv_big_union(b: &mut Bencher) {
1783 let mut b1 = Bitv::new(BENCH_BITS, false);
1784 let b2 = Bitv::new(BENCH_BITS, false);
1791 fn bench_btv_small_iter(b: &mut Bencher) {
1792 let bitv = Bitv::new(uint::BITS, false);
1795 for pres in bitv.iter() {
1796 _sum += pres as uint;
1802 fn bench_bitv_big_iter(b: &mut Bencher) {
1803 let bitv = Bitv::new(BENCH_BITS, false);
1806 for pres in bitv.iter() {
1807 _sum += pres as uint;
1813 fn bench_bitvset_iter(b: &mut Bencher) {
1814 let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
1815 |idx| {idx % 3 == 0}));
1818 for idx in bitv.iter() {