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)]
15 use std::iter::RandomAccessIterator;
16 use std::iter::{Rev, Enumerate, Repeat, Map, Zip};
19 use std::strbuf::StrBuf;
24 /// only the lowest nbits of this value are used. the rest is undefined.
28 /// a mask that has a 1 for each defined bit in a small_bitv, assuming n bits
30 fn small_mask(nbits: uint) -> uint {
35 pub fn new(bits: uint) -> SmallBitv {
36 SmallBitv {bits: bits}
40 pub fn bits_op(&mut self,
43 f: |uint, uint| -> uint)
45 let mask = small_mask(nbits);
46 let old_b: uint = self.bits;
47 let new_b = f(old_b, right_bits);
49 mask & old_b != mask & new_b
53 pub fn union(&mut self, s: &SmallBitv, nbits: uint) -> bool {
54 self.bits_op(s.bits, nbits, |u1, u2| u1 | u2)
58 pub fn intersect(&mut self, s: &SmallBitv, nbits: uint) -> bool {
59 self.bits_op(s.bits, nbits, |u1, u2| u1 & u2)
63 pub fn become(&mut self, s: &SmallBitv, nbits: uint) -> bool {
64 self.bits_op(s.bits, nbits, |_u1, u2| u2)
68 pub fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool {
69 self.bits_op(s.bits, nbits, |u1, u2| u1 & !u2)
73 pub fn get(&self, i: uint) -> bool {
74 (self.bits & (1 << i)) != 0
78 pub fn set(&mut self, i: uint, x: bool) {
88 pub fn equals(&self, b: &SmallBitv, nbits: uint) -> bool {
89 let mask = small_mask(nbits);
90 mask & self.bits == mask & b.bits
94 pub fn clear(&mut self) { self.bits = 0; }
97 pub fn set_all(&mut self) { self.bits = !0; }
100 pub fn all(&self, nbits: uint) -> bool {
101 small_mask(nbits) & !self.bits == 0
105 pub fn none(&self, nbits: uint) -> bool {
106 small_mask(nbits) & self.bits == 0
110 pub fn negate(&mut self) { self.bits = !self.bits; }
119 * A mask that has a 1 for each defined bit in the n'th element of a `BigBitv`,
123 fn big_mask(nbits: uint, elem: uint) -> uint {
124 let rmd = nbits % uint::BITS;
125 let nelems = nbits/uint::BITS + if rmd == 0 {0} else {1};
127 if elem < nelems - 1 || rmd == 0 {
135 pub fn new(storage: Vec<uint>) -> BigBitv {
136 BigBitv {storage: storage}
140 pub fn process(&mut self,
143 op: |uint, uint| -> uint)
145 let len = b.storage.len();
146 assert_eq!(self.storage.len(), len);
147 let mut changed = false;
148 for (i, (a, b)) in self.storage.mut_iter()
149 .zip(b.storage.iter())
151 let mask = big_mask(nbits, i);
154 let w = op(w0, w1) & mask;
164 pub fn each_storage(&mut self, op: |v: &mut uint| -> bool) -> bool {
165 self.storage.mut_iter().advance(|elt| op(elt))
169 pub fn negate(&mut self) {
170 self.each_storage(|w| { *w = !*w; true });
174 pub fn union(&mut self, b: &BigBitv, nbits: uint) -> bool {
175 self.process(b, nbits, |w1, w2| w1 | w2)
179 pub fn intersect(&mut self, b: &BigBitv, nbits: uint) -> bool {
180 self.process(b, nbits, |w1, w2| w1 & w2)
184 pub fn become(&mut self, b: &BigBitv, nbits: uint) -> bool {
185 self.process(b, nbits, |_, w| w)
189 pub fn difference(&mut self, b: &BigBitv, nbits: uint) -> bool {
190 self.process(b, nbits, |w1, w2| w1 & !w2)
194 pub fn get(&self, i: uint) -> bool {
195 let w = i / uint::BITS;
196 let b = i % uint::BITS;
197 let x = 1 & self.storage.get(w) >> b;
202 pub fn set(&mut self, i: uint, x: bool) {
203 let w = i / uint::BITS;
204 let b = i % uint::BITS;
206 *self.storage.get_mut(w) = if x { *self.storage.get(w) | flag }
207 else { *self.storage.get(w) & !flag };
211 pub fn equals(&self, b: &BigBitv, nbits: uint) -> bool {
212 for (i, elt) in b.storage.iter().enumerate() {
213 let mask = big_mask(nbits, i);
214 if mask & *self.storage.get(i) != mask & *elt {
223 enum BitvVariant { Big(BigBitv), Small(SmallBitv) }
225 enum Op {Union, Intersect, Assign, Difference}
227 /// The bitvector type
230 /// Internal representation of the bit vector (small or large)
232 /// The number of valid bits in the internal representation
237 fail!("Tried to do operation on bit vectors with different sizes");
242 fn do_op(&mut self, op: Op, other: &Bitv) -> bool {
243 if self.nbits != other.nbits {
247 Small(ref mut s) => match other.rep {
248 Small(ref s1) => match op {
249 Union => s.union(s1, self.nbits),
250 Intersect => s.intersect(s1, self.nbits),
251 Assign => s.become(s1, self.nbits),
252 Difference => s.difference(s1, self.nbits)
256 Big(ref mut s) => match other.rep {
258 Big(ref s1) => match op {
259 Union => s.union(s1, self.nbits),
260 Intersect => s.intersect(s1, self.nbits),
261 Assign => s.become(s1, self.nbits),
262 Difference => s.difference(s1, self.nbits)
271 pub fn new(nbits: uint, init: bool) -> Bitv {
272 let rep = if nbits < uint::BITS {
273 Small(SmallBitv::new(if init {(1<<nbits)-1} else {0}))
274 } else if nbits == uint::BITS {
275 Small(SmallBitv::new(if init {!0} else {0}))
277 let exact = nbits % uint::BITS == 0;
278 let nelems = nbits/uint::BITS + if exact {0} else {1};
282 Vec::from_elem(nelems, !0u)
284 let mut v = Vec::from_elem(nelems-1, !0u);
285 v.push((1<<nbits % uint::BITS)-1);
288 } else { Vec::from_elem(nelems, 0u)};
291 Bitv {rep: rep, nbits: nbits}
295 * Calculates the union of two bitvectors
297 * Sets `self` to the union of `self` and `v1`. Both bitvectors must be
298 * the same length. Returns `true` if `self` changed.
301 pub fn union(&mut self, v1: &Bitv) -> bool { self.do_op(Union, v1) }
304 * Calculates the intersection of two bitvectors
306 * Sets `self` to the intersection of `self` and `v1`. Both bitvectors
307 * must be the same length. Returns `true` if `self` changed.
310 pub fn intersect(&mut self, v1: &Bitv) -> bool {
311 self.do_op(Intersect, v1)
315 * Assigns the value of `v1` to `self`
317 * Both bitvectors must be the same length. Returns `true` if `self` was
321 pub fn assign(&mut self, v: &Bitv) -> bool { self.do_op(Assign, v) }
323 /// Retrieve the value at index `i`
325 pub fn get(&self, i: uint) -> bool {
326 assert!((i < self.nbits));
328 Big(ref b) => b.get(i),
329 Small(ref s) => s.get(i)
334 * Set the value of a bit at a given index
336 * `i` must be less than the length of the bitvector.
339 pub fn set(&mut self, i: uint, x: bool) {
340 assert!((i < self.nbits));
342 Big(ref mut b) => b.set(i, x),
343 Small(ref mut s) => s.set(i, x)
348 * Compares two bitvectors
350 * Both bitvectors must be the same length. Returns `true` if both
351 * bitvectors contain identical elements.
354 pub fn equal(&self, v1: &Bitv) -> bool {
355 if self.nbits != v1.nbits { return false; }
357 Small(ref b) => match v1.rep {
358 Small(ref b1) => b.equals(b1, self.nbits),
361 Big(ref s) => match v1.rep {
362 Big(ref s1) => s.equals(s1, self.nbits),
363 Small(_) => return false
368 /// Set all bits to 0
370 pub fn clear(&mut self) {
372 Small(ref mut b) => b.clear(),
374 s.each_storage(|w| { *w = 0u; true });
379 /// Set all bits to 1
381 pub fn set_all(&mut self) {
383 Small(ref mut b) => b.set_all(),
385 s.each_storage(|w| { *w = !0u; true });
392 pub fn negate(&mut self) {
394 Small(ref mut s) => s.negate(),
395 Big(ref mut b) => b.negate(),
400 * Calculate the difference between two bitvectors
402 * Sets each element of `v0` to the value of that element minus the
403 * element of `v1` at the same index. Both bitvectors must be the same
406 * Returns `true` if `v0` was changed.
409 pub fn difference(&mut self, v: &Bitv) -> bool {
410 self.do_op(Difference, v)
413 /// Returns `true` if all bits are 1
415 pub fn all(&self) -> bool {
417 Small(ref b) => b.all(self.nbits),
418 _ => self.iter().all(|x| x)
423 pub fn iter<'a>(&'a self) -> Bits<'a> {
424 Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
428 pub fn rev_iter<'a>(&'a self) -> Rev<Bits<'a>> {
432 /// Returns `true` if all bits are 0
433 pub fn none(&self) -> bool {
435 Small(ref b) => b.none(self.nbits),
436 _ => self.iter().all(|x| !x)
441 /// Returns `true` if any bit is 1
442 pub fn any(&self) -> bool {
446 pub fn init_to_vec(&self, i: uint) -> uint {
447 return if self.get(i) { 1 } else { 0 };
451 * Converts `self` to a vector of `uint` with the same length.
453 * Each `uint` in the resulting vector has either value `0u` or `1u`.
455 pub fn to_vec(&self) -> Vec<uint> {
456 Vec::from_fn(self.nbits, |x| self.init_to_vec(x))
460 * Organise the bits into bytes, such that the first bit in the
461 * `Bitv` becomes the high-order bit of the first byte. If the
462 * size of the `Bitv` is not a multiple of 8 then trailing bits
463 * will be filled-in with false/0
465 pub fn to_bytes(&self) -> Vec<u8> {
466 fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
467 let offset = byte * 8 + bit;
468 if offset >= bitv.nbits {
471 bitv[offset] as u8 << (7 - bit)
475 let len = self.nbits/8 +
476 if self.nbits % 8 == 0 { 0 } else { 1 };
477 Vec::from_fn(len, |i|
490 * Transform `self` into a `Vec<bool>` by turning each bit into a `bool`.
492 pub fn to_bools(&self) -> Vec<bool> {
493 Vec::from_fn(self.nbits, |i| self[i])
497 * Converts `self` to a string.
499 * The resulting string has the same length as `self`, and each
500 * character is either '0' or '1'.
502 pub fn to_str(&self) -> ~str {
503 let mut rs = StrBuf::new();
504 for i in self.iter() {
516 * Compare a bitvector to a vector of `bool`.
518 * Both the bitvector and vector must have the same length.
520 pub fn eq_vec(&self, v: &[bool]) -> bool {
521 assert_eq!(self.nbits, v.len());
523 while i < self.nbits {
524 if self.get(i) != v[i] { return false; }
530 pub fn ones(&self, f: |uint| -> bool) -> bool {
531 range(0u, self.nbits).advance(|i| !self.get(i) || f(i))
537 * Transform a byte-vector into a `Bitv`. Each byte becomes 8 bits,
538 * with the most significant bits of each byte coming first. Each
539 * bit becomes `true` if equal to 1 or `false` if equal to 0.
541 pub fn from_bytes(bytes: &[u8]) -> Bitv {
542 from_fn(bytes.len() * 8, |i| {
543 let b = bytes[i / 8] as uint;
545 b >> (7 - offset) & 1 == 1
550 * Transform a `[bool]` into a `Bitv` by converting each `bool` into a bit.
552 pub fn from_bools(bools: &[bool]) -> Bitv {
553 from_fn(bools.len(), |i| bools[i])
557 * Create a `Bitv` of the specified length where the value at each
558 * index is `f(index)`.
560 pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
561 let mut bitv = Bitv::new(len, false);
562 for i in range(0u, len) {
568 impl ops::Index<uint,bool> for Bitv {
569 fn index(&self, i: &uint) -> bool {
575 fn iterate_bits(base: uint, bits: uint, f: |uint| -> bool) -> bool {
579 for i in range(0u, uint::BITS) {
580 if bits & (1 << i) != 0 {
589 /// An iterator for `Bitv`.
590 pub struct Bits<'a> {
596 impl<'a> Iterator<bool> for Bits<'a> {
598 fn next(&mut self) -> Option<bool> {
599 if self.next_idx != self.end_idx {
600 let idx = self.next_idx;
602 Some(self.bitv.get(idx))
608 fn size_hint(&self) -> (uint, Option<uint>) {
609 let rem = self.end_idx - self.next_idx;
614 impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
616 fn next_back(&mut self) -> Option<bool> {
617 if self.next_idx != self.end_idx {
619 Some(self.bitv.get(self.end_idx))
626 impl<'a> ExactSize<bool> for Bits<'a> {}
628 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
630 fn indexable(&self) -> uint {
631 self.end_idx - self.next_idx
635 fn idx(&self, index: uint) -> Option<bool> {
636 if index >= self.indexable() {
639 Some(self.bitv.get(index))
644 /// An implementation of a set using a bit vector as an underlying
645 /// representation for holding numerical elements.
647 /// It should also be noted that the amount of storage necessary for holding a
648 /// set of objects is proportional to the maximum of the objects when viewed
654 // In theory this is a `Bitv` instead of always a `BigBitv`, but knowing that
655 // there's an array of storage makes our lives a whole lot easier when
656 // performing union/intersection/etc operations
661 /// Creates a new bit vector set with initially no contents
662 pub fn new() -> BitvSet {
663 BitvSet{ size: 0, bitv: BigBitv::new(vec!(0)) }
666 /// Creates a new bit vector set from the given bit vector
667 pub fn from_bitv(bitv: Bitv) -> BitvSet {
673 let Bitv{rep, ..} = bitv;
675 Big(b) => BitvSet{ size: size, bitv: b },
676 Small(SmallBitv{bits}) =>
677 BitvSet{ size: size, bitv: BigBitv{ storage: vec!(bits) } },
681 /// Returns the capacity in bits for this bit vector. Inserting any
682 /// element less than this amount will not trigger a resizing.
683 pub fn capacity(&self) -> uint { self.bitv.storage.len() * uint::BITS }
685 /// Consumes this set to return the underlying bit vector
686 pub fn unwrap(self) -> Bitv {
687 let cap = self.capacity();
688 let BitvSet{bitv, ..} = self;
689 return Bitv{ nbits:cap, rep: Big(bitv) };
693 fn other_op(&mut self, other: &BitvSet, f: |uint, uint| -> uint) {
694 fn nbits(mut w: uint) -> uint {
696 for _ in range(0u, uint::BITS) {
705 if self.capacity() < other.capacity() {
706 self.bitv.storage.grow(other.capacity() / uint::BITS, &0);
708 for (i, &w) in other.bitv.storage.iter().enumerate() {
709 let old = *self.bitv.storage.get(i);
711 *self.bitv.storage.get_mut(i) = new;
712 self.size += nbits(new) - nbits(old);
716 /// Union in-place with the specified other bit vector
717 pub fn union_with(&mut self, other: &BitvSet) {
718 self.other_op(other, |w1, w2| w1 | w2);
721 /// Intersect in-place with the specified other bit vector
722 pub fn intersect_with(&mut self, other: &BitvSet) {
723 self.other_op(other, |w1, w2| w1 & w2);
726 /// Difference in-place with the specified other bit vector
727 pub fn difference_with(&mut self, other: &BitvSet) {
728 self.other_op(other, |w1, w2| w1 & !w2);
731 /// Symmetric difference in-place with the specified other bit vector
732 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
733 self.other_op(other, |w1, w2| w1 ^ w2);
736 pub fn iter<'a>(&'a self) -> BitPositions<'a> {
737 BitPositions {set: self, next_idx: 0}
740 pub fn difference(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
741 for (i, w1, w2) in self.commons(other) {
742 if !iterate_bits(i, w1 & !w2, |b| f(&b)) {
746 /* everything we have that they don't also shows up */
747 self.outliers(other).advance(|(mine, i, w)|
748 !mine || iterate_bits(i, w, |b| f(&b))
752 pub fn symmetric_difference(&self, other: &BitvSet, f: |&uint| -> bool)
754 for (i, w1, w2) in self.commons(other) {
755 if !iterate_bits(i, w1 ^ w2, |b| f(&b)) {
759 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
762 pub fn intersection(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
763 self.commons(other).advance(|(i, w1, w2)| iterate_bits(i, w1 & w2, |b| f(&b)))
766 pub fn union(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
767 for (i, w1, w2) in self.commons(other) {
768 if !iterate_bits(i, w1 | w2, |b| f(&b)) {
772 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
776 impl cmp::Eq for BitvSet {
777 fn eq(&self, other: &BitvSet) -> bool {
778 if self.size != other.size {
781 for (_, w1, w2) in self.commons(other) {
786 for (_, _, w) in self.outliers(other) {
794 fn ne(&self, other: &BitvSet) -> bool { !self.eq(other) }
797 impl Container for BitvSet {
799 fn len(&self) -> uint { self.size }
802 impl Mutable for BitvSet {
803 fn clear(&mut self) {
804 self.bitv.each_storage(|w| { *w = 0; true });
809 impl Set<uint> for BitvSet {
810 fn contains(&self, value: &uint) -> bool {
811 *value < self.bitv.storage.len() * uint::BITS && self.bitv.get(*value)
814 fn is_disjoint(&self, other: &BitvSet) -> bool {
815 self.intersection(other, |_| false)
818 fn is_subset(&self, other: &BitvSet) -> bool {
819 for (_, w1, w2) in self.commons(other) {
824 /* If anything is not ours, then everything is not ours so we're
825 definitely a subset in that case. Otherwise if there's any stray
826 ones that 'other' doesn't have, we're not a subset. */
827 for (mine, _, w) in self.outliers(other) {
837 fn is_superset(&self, other: &BitvSet) -> bool {
838 other.is_subset(self)
842 impl MutableSet<uint> for BitvSet {
843 fn insert(&mut self, value: uint) -> bool {
844 if self.contains(&value) {
847 let nbits = self.capacity();
849 let newsize = cmp::max(value, nbits * 2) / uint::BITS + 1;
850 assert!(newsize > self.bitv.storage.len());
851 self.bitv.storage.grow(newsize, &0);
854 self.bitv.set(value, true);
858 fn remove(&mut self, value: &uint) -> bool {
859 if !self.contains(value) {
863 self.bitv.set(*value, false);
865 // Attempt to truncate our storage
866 let mut i = self.bitv.storage.len();
867 while i > 1 && *self.bitv.storage.get(i - 1) == 0 {
870 self.bitv.storage.truncate(i);
877 /// Visits each of the words that the two bit vectors (`self` and `other`)
878 /// both have in common. The three yielded arguments are (bit location,
879 /// w1, w2) where the bit location is the number of bits offset so far,
880 /// and w1/w2 are the words coming from the two vectors self, other.
881 fn commons<'a>(&'a self, other: &'a BitvSet)
882 -> Map<'static, ((uint, &'a uint), &'a Vec<uint>), (uint, uint, uint),
883 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<&'a Vec<uint>>>> {
884 let min = cmp::min(self.bitv.storage.len(), other.bitv.storage.len());
885 self.bitv.storage.slice(0, min).iter().enumerate()
886 .zip(Repeat::new(&other.bitv.storage))
887 .map(|((i, &w), o_store)| (i * uint::BITS, w, *o_store.get(i)))
890 /// Visits each word in `self` or `other` that extends beyond the other. This
891 /// will only iterate through one of the vectors, and it only iterates
892 /// over the portion that doesn't overlap with the other one.
894 /// The yielded arguments are a `bool`, the bit offset, and a word. The `bool`
895 /// is true if the word comes from `self`, and `false` if it comes from
897 fn outliers<'a>(&'a self, other: &'a BitvSet)
898 -> Map<'static, ((uint, &'a uint), uint), (bool, uint, uint),
899 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<uint>>> {
900 let slen = self.bitv.storage.len();
901 let olen = other.bitv.storage.len();
904 self.bitv.storage.slice_from(olen).iter().enumerate()
905 .zip(Repeat::new(olen))
906 .map(|((i, &w), min)| (true, (i + min) * uint::BITS, w))
908 other.bitv.storage.slice_from(slen).iter().enumerate()
909 .zip(Repeat::new(slen))
910 .map(|((i, &w), min)| (false, (i + min) * uint::BITS, w))
915 pub struct BitPositions<'a> {
920 impl<'a> Iterator<uint> for BitPositions<'a> {
922 fn next(&mut self) -> Option<uint> {
923 while self.next_idx < self.set.capacity() {
924 let idx = self.next_idx;
927 if self.set.contains(&idx) {
935 fn size_hint(&self) -> (uint, Option<uint>) {
936 (0, Some(self.set.capacity() - self.next_idx))
943 use self::test::Bencher;
945 use bitv::{Bitv, SmallBitv, BigBitv, BitvSet, from_bools, from_fn,
953 static BENCH_BITS : uint = 1 << 14;
957 let zerolen = Bitv::new(0u, false);
958 assert_eq!(zerolen.to_str(), "".to_owned());
960 let eightbits = Bitv::new(8u, false);
961 assert_eq!(eightbits.to_str(), "00000000".to_owned());
965 fn test_0_elements() {
966 let act = Bitv::new(0u, false);
967 let exp = Vec::from_elem(0u, false);
968 assert!(act.eq_vec(exp.as_slice()));
972 fn test_1_element() {
973 let mut act = Bitv::new(1u, false);
974 assert!(act.eq_vec([false]));
975 act = Bitv::new(1u, true);
976 assert!(act.eq_vec([true]));
980 fn test_2_elements() {
981 let mut b = bitv::Bitv::new(2, false);
984 assert_eq!(b.to_str(), "10".to_owned());
988 fn test_10_elements() {
992 act = Bitv::new(10u, false);
994 [false, false, false, false, false, false, false, false, false, false])));
997 act = Bitv::new(10u, true);
998 assert!((act.eq_vec([true, true, true, true, true, true, true, true, true, true])));
1001 act = Bitv::new(10u, false);
1007 assert!((act.eq_vec([true, true, true, true, true, false, false, false, false, false])));
1010 act = Bitv::new(10u, false);
1016 assert!((act.eq_vec([false, false, false, false, false, true, true, true, true, true])));
1019 act = Bitv::new(10u, false);
1024 assert!((act.eq_vec([true, false, false, true, false, false, true, false, false, true])));
1028 fn test_31_elements() {
1032 act = Bitv::new(31u, false);
1034 [false, false, false, false, false, false, false, false, false, false, false,
1035 false, false, false, false, false, false, false, false, false, false, false, false,
1036 false, false, false, false, false, false, false, false]));
1039 act = Bitv::new(31u, true);
1041 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1042 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1043 true, true, true, true]));
1046 act = Bitv::new(31u, false);
1056 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1057 false, false, false, false, false, false, false, false, false, false, false, false,
1058 false, false, false, false, false, false]));
1061 act = Bitv::new(31u, false);
1071 [false, false, false, false, false, false, false, false, false, false, false,
1072 false, false, false, false, false, true, true, true, true, true, true, true, true,
1073 false, false, false, false, false, false, false]));
1076 act = Bitv::new(31u, false);
1085 [false, false, false, false, false, false, false, false, false, false, false,
1086 false, false, false, false, false, false, false, false, false, false, false, false,
1087 false, true, true, true, true, true, true, true]));
1090 act = Bitv::new(31u, false);
1095 [false, false, false, true, false, false, false, false, false, false, false, false,
1096 false, false, false, false, false, true, false, false, false, false, false, false,
1097 false, false, false, false, false, false, true]));
1101 fn test_32_elements() {
1105 act = Bitv::new(32u, false);
1107 [false, false, false, false, false, false, false, false, false, false, false,
1108 false, false, false, false, false, false, false, false, false, false, false, false,
1109 false, false, false, false, false, false, false, false, false]));
1112 act = Bitv::new(32u, true);
1114 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1115 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1116 true, true, true, true, true]));
1119 act = Bitv::new(32u, false);
1129 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1130 false, false, false, false, false, false, false, false, false, false, false, false,
1131 false, false, false, false, false, false, false]));
1134 act = Bitv::new(32u, false);
1144 [false, false, false, false, false, false, false, false, false, false, false,
1145 false, false, false, false, false, true, true, true, true, true, true, true, true,
1146 false, false, false, false, false, false, false, false]));
1149 act = Bitv::new(32u, false);
1159 [false, false, false, false, false, false, false, false, false, false, false,
1160 false, false, false, false, false, false, false, false, false, false, false, false,
1161 false, true, true, true, true, true, true, true, true]));
1164 act = Bitv::new(32u, false);
1170 [false, false, false, true, false, false, false, false, false, false, false, false,
1171 false, false, false, false, false, true, false, false, false, false, false, false,
1172 false, false, false, false, false, false, true, true]));
1176 fn test_33_elements() {
1180 act = Bitv::new(33u, false);
1182 [false, false, false, false, false, false, false, false, false, false, false,
1183 false, false, false, false, false, false, false, false, false, false, false, false,
1184 false, false, false, false, false, false, false, false, false, false]));
1187 act = Bitv::new(33u, true);
1189 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1190 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1191 true, true, true, true, true, true]));
1194 act = Bitv::new(33u, false);
1204 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1205 false, false, false, false, false, false, false, false, false, false, false, false,
1206 false, false, false, false, false, false, false, false]));
1209 act = Bitv::new(33u, false);
1219 [false, false, false, false, false, false, false, false, false, false, false,
1220 false, false, false, false, false, true, true, true, true, true, true, true, true,
1221 false, false, false, false, false, false, false, false, false]));
1224 act = Bitv::new(33u, false);
1234 [false, false, false, false, false, false, false, false, false, false, false,
1235 false, false, false, false, false, false, false, false, false, false, false, false,
1236 false, true, true, true, true, true, true, true, true, false]));
1239 act = Bitv::new(33u, false);
1246 [false, false, false, true, false, false, false, false, false, false, false, false,
1247 false, false, false, false, false, true, false, false, false, false, false, false,
1248 false, false, false, false, false, false, true, true, true]));
1252 fn test_equal_differing_sizes() {
1253 let v0 = Bitv::new(10u, false);
1254 let v1 = Bitv::new(11u, false);
1255 assert!(!v0.equal(&v1));
1259 fn test_equal_greatly_differing_sizes() {
1260 let v0 = Bitv::new(10u, false);
1261 let v1 = Bitv::new(110u, false);
1262 assert!(!v0.equal(&v1));
1266 fn test_equal_sneaky_small() {
1267 let mut a = bitv::Bitv::new(1, false);
1270 let mut b = bitv::Bitv::new(1, true);
1273 assert!(a.equal(&b));
1277 fn test_equal_sneaky_big() {
1278 let mut a = bitv::Bitv::new(100, false);
1279 for i in range(0u, 100) {
1283 let mut b = bitv::Bitv::new(100, true);
1284 for i in range(0u, 100) {
1288 assert!(a.equal(&b));
1292 fn test_from_bytes() {
1293 let bitv = from_bytes([0b10110110, 0b00000000, 0b11111111]);
1294 let str = "10110110".to_owned() + "00000000" + "11111111";
1295 assert_eq!(bitv.to_str(), str);
1299 fn test_to_bytes() {
1300 let mut bv = Bitv::new(3, true);
1302 assert_eq!(bv.to_bytes(), vec!(0b10100000));
1304 let mut bv = Bitv::new(9, false);
1307 assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
1311 fn test_from_bools() {
1312 assert!(from_bools([true, false, true, true]).to_str() ==
1317 fn test_to_bools() {
1318 let bools = vec!(false, false, true, false, false, true, true, false);
1319 assert_eq!(from_bytes([0b00100110]).to_bools(), bools);
1323 fn test_bitv_iterator() {
1324 let bools = [true, false, true, true];
1325 let bitv = from_bools(bools);
1327 for (act, &ex) in bitv.iter().zip(bools.iter()) {
1328 assert_eq!(ex, act);
1333 fn test_bitv_set_iterator() {
1334 let bools = [true, false, true, true];
1335 let bitv = BitvSet::from_bitv(from_bools(bools));
1337 let idxs: Vec<uint> = bitv.iter().collect();
1338 assert_eq!(idxs, vec!(0, 2, 3));
1342 fn test_bitv_set_frombitv_init() {
1343 let bools = [true, false];
1344 let lengths = [10, 64, 100];
1345 for &b in bools.iter() {
1346 for &l in lengths.iter() {
1347 let bitset = BitvSet::from_bitv(Bitv::new(l, b));
1348 assert_eq!(bitset.contains(&1u), b)
1349 assert_eq!(bitset.contains(&(l-1u)), b)
1350 assert!(!bitset.contains(&l))
1356 fn test_small_difference() {
1357 let mut b1 = Bitv::new(3, false);
1358 let mut b2 = Bitv::new(3, false);
1363 assert!(b1.difference(&b2));
1370 fn test_big_difference() {
1371 let mut b1 = Bitv::new(100, false);
1372 let mut b2 = Bitv::new(100, false);
1377 assert!(b1.difference(&b2));
1384 fn test_small_clear() {
1385 let mut b = Bitv::new(14, true);
1388 fail!("found 1 at {:?}", i)
1393 fn test_big_clear() {
1394 let mut b = Bitv::new(140, true);
1397 fail!("found 1 at {:?}", i)
1402 fn test_bitv_set_basic() {
1403 let mut b = BitvSet::new();
1404 assert!(b.insert(3));
1405 assert!(!b.insert(3));
1406 assert!(b.contains(&3));
1407 assert!(b.insert(400));
1408 assert!(!b.insert(400));
1409 assert!(b.contains(&400));
1410 assert_eq!(b.len(), 2);
1414 fn test_bitv_set_intersection() {
1415 let mut a = BitvSet::new();
1416 let mut b = BitvSet::new();
1418 assert!(a.insert(11));
1419 assert!(a.insert(1));
1420 assert!(a.insert(3));
1421 assert!(a.insert(77));
1422 assert!(a.insert(103));
1423 assert!(a.insert(5));
1425 assert!(b.insert(2));
1426 assert!(b.insert(11));
1427 assert!(b.insert(77));
1428 assert!(b.insert(5));
1429 assert!(b.insert(3));
1432 let expected = [3, 5, 11, 77];
1433 a.intersection(&b, |x| {
1434 assert_eq!(*x, expected[i]);
1438 assert_eq!(i, expected.len());
1442 fn test_bitv_set_difference() {
1443 let mut a = BitvSet::new();
1444 let mut b = BitvSet::new();
1446 assert!(a.insert(1));
1447 assert!(a.insert(3));
1448 assert!(a.insert(5));
1449 assert!(a.insert(200));
1450 assert!(a.insert(500));
1452 assert!(b.insert(3));
1453 assert!(b.insert(200));
1456 let expected = [1, 5, 500];
1457 a.difference(&b, |x| {
1458 assert_eq!(*x, expected[i]);
1462 assert_eq!(i, expected.len());
1466 fn test_bitv_set_symmetric_difference() {
1467 let mut a = BitvSet::new();
1468 let mut b = BitvSet::new();
1470 assert!(a.insert(1));
1471 assert!(a.insert(3));
1472 assert!(a.insert(5));
1473 assert!(a.insert(9));
1474 assert!(a.insert(11));
1476 assert!(b.insert(3));
1477 assert!(b.insert(9));
1478 assert!(b.insert(14));
1479 assert!(b.insert(220));
1482 let expected = [1, 5, 11, 14, 220];
1483 a.symmetric_difference(&b, |x| {
1484 assert_eq!(*x, expected[i]);
1488 assert_eq!(i, expected.len());
1492 fn test_bitv_set_union() {
1493 let mut a = BitvSet::new();
1494 let mut b = BitvSet::new();
1495 assert!(a.insert(1));
1496 assert!(a.insert(3));
1497 assert!(a.insert(5));
1498 assert!(a.insert(9));
1499 assert!(a.insert(11));
1500 assert!(a.insert(160));
1501 assert!(a.insert(19));
1502 assert!(a.insert(24));
1504 assert!(b.insert(1));
1505 assert!(b.insert(5));
1506 assert!(b.insert(9));
1507 assert!(b.insert(13));
1508 assert!(b.insert(19));
1511 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160];
1513 assert_eq!(*x, expected[i]);
1517 assert_eq!(i, expected.len());
1521 fn test_bitv_remove() {
1522 let mut a = BitvSet::new();
1524 assert!(a.insert(1));
1525 assert!(a.remove(&1));
1527 assert!(a.insert(100));
1528 assert!(a.remove(&100));
1530 assert!(a.insert(1000));
1531 assert!(a.remove(&1000));
1532 assert_eq!(a.capacity(), uint::BITS);
1536 fn test_bitv_clone() {
1537 let mut a = BitvSet::new();
1539 assert!(a.insert(1));
1540 assert!(a.insert(100));
1541 assert!(a.insert(1000));
1543 let mut b = a.clone();
1547 assert!(b.remove(&1));
1548 assert!(a.contains(&1));
1550 assert!(a.remove(&1000));
1551 assert!(b.contains(&1000));
1555 fn test_small_bitv_tests() {
1556 let v = from_bytes([0]);
1561 let v = from_bytes([0b00010100]);
1566 let v = from_bytes([0xFF]);
1573 fn test_big_bitv_tests() {
1574 let v = from_bytes([ // 88 bits
1582 let v = from_bytes([ // 88 bits
1583 0, 0, 0b00010100, 0,
1584 0, 0, 0, 0b00110100,
1590 let v = from_bytes([ // 88 bits
1591 0xFF, 0xFF, 0xFF, 0xFF,
1592 0xFF, 0xFF, 0xFF, 0xFF,
1599 fn rng() -> rand::IsaacRng {
1600 let seed = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
1601 rand::SeedableRng::from_seed(seed)
1605 fn bench_uint_small(b: &mut Bencher) {
1607 let mut bitv = 0 as uint;
1609 bitv |= 1 << ((r.next_u32() as uint) % uint::BITS);
1615 fn bench_small_bitv_small(b: &mut Bencher) {
1617 let mut bitv = SmallBitv::new(uint::BITS);
1619 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1625 fn bench_big_bitv_small(b: &mut Bencher) {
1627 let mut bitv = BigBitv::new(vec!(0));
1629 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1635 fn bench_big_bitv_big(b: &mut Bencher) {
1637 let mut storage = vec!();
1638 storage.grow(BENCH_BITS / uint::BITS, &0u);
1639 let mut bitv = BigBitv::new(storage);
1641 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1647 fn bench_bitv_big(b: &mut Bencher) {
1649 let mut bitv = Bitv::new(BENCH_BITS, false);
1651 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1657 fn bench_bitv_small(b: &mut Bencher) {
1659 let mut bitv = Bitv::new(uint::BITS, false);
1661 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1667 fn bench_bitv_set_small(b: &mut Bencher) {
1669 let mut bitv = BitvSet::new();
1671 bitv.insert((r.next_u32() as uint) % uint::BITS);
1677 fn bench_bitv_set_big(b: &mut Bencher) {
1679 let mut bitv = BitvSet::new();
1681 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
1687 fn bench_bitv_big_union(b: &mut Bencher) {
1688 let mut b1 = Bitv::new(BENCH_BITS, false);
1689 let b2 = Bitv::new(BENCH_BITS, false);
1696 fn bench_btv_small_iter(b: &mut Bencher) {
1697 let bitv = Bitv::new(uint::BITS, false);
1700 for pres in bitv.iter() {
1701 _sum += pres as uint;
1707 fn bench_bitv_big_iter(b: &mut Bencher) {
1708 let bitv = Bitv::new(BENCH_BITS, false);
1711 for pres in bitv.iter() {
1712 _sum += pres as uint;
1718 fn bench_bitvset_iter(b: &mut Bencher) {
1719 let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
1720 |idx| {idx % 3 == 0}));
1723 for idx in bitv.iter() {