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};
23 /// only the lowest nbits of this value are used. the rest is undefined.
27 /// a mask that has a 1 for each defined bit in a small_bitv, assuming n bits
29 fn small_mask(nbits: uint) -> uint {
34 pub fn new(bits: uint) -> SmallBitv {
35 SmallBitv {bits: bits}
39 pub fn bits_op(&mut self,
42 f: |uint, uint| -> uint)
44 let mask = small_mask(nbits);
45 let old_b: uint = self.bits;
46 let new_b = f(old_b, right_bits);
48 mask & old_b != mask & new_b
52 pub fn union(&mut self, s: &SmallBitv, nbits: uint) -> bool {
53 self.bits_op(s.bits, nbits, |u1, u2| u1 | u2)
57 pub fn intersect(&mut self, s: &SmallBitv, nbits: uint) -> bool {
58 self.bits_op(s.bits, nbits, |u1, u2| u1 & u2)
62 pub fn become(&mut self, s: &SmallBitv, nbits: uint) -> bool {
63 self.bits_op(s.bits, nbits, |_u1, u2| u2)
67 pub fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool {
68 self.bits_op(s.bits, nbits, |u1, u2| u1 & !u2)
72 pub fn get(&self, i: uint) -> bool {
73 (self.bits & (1 << i)) != 0
77 pub fn set(&mut self, i: uint, x: bool) {
87 pub fn equals(&self, b: &SmallBitv, nbits: uint) -> bool {
88 let mask = small_mask(nbits);
89 mask & self.bits == mask & b.bits
93 pub fn clear(&mut self) { self.bits = 0; }
96 pub fn set_all(&mut self) { self.bits = !0; }
99 pub fn is_true(&self, nbits: uint) -> bool {
100 small_mask(nbits) & !self.bits == 0
104 pub fn is_false(&self, nbits: uint) -> bool {
105 small_mask(nbits) & self.bits == 0
109 pub fn negate(&mut self) { self.bits = !self.bits; }
118 * A mask that has a 1 for each defined bit in the n'th element of a `BigBitv`,
122 fn big_mask(nbits: uint, elem: uint) -> uint {
123 let rmd = nbits % uint::BITS;
124 let nelems = nbits/uint::BITS + if rmd == 0 {0} else {1};
126 if elem < nelems - 1 || rmd == 0 {
134 pub fn new(storage: ~[uint]) -> BigBitv {
135 BigBitv {storage: storage}
139 pub fn process(&mut self,
142 op: |uint, uint| -> uint)
144 let len = b.storage.len();
145 assert_eq!(self.storage.len(), len);
146 let mut changed = false;
147 for (i, (a, b)) in self.storage.mut_iter()
148 .zip(b.storage.iter())
150 let mask = big_mask(nbits, i);
153 let w = op(w0, w1) & mask;
163 pub fn each_storage(&mut self, op: |v: &mut uint| -> bool) -> bool {
164 self.storage.mut_iter().advance(|elt| op(elt))
168 pub fn negate(&mut self) {
169 self.each_storage(|w| { *w = !*w; true });
173 pub fn union(&mut self, b: &BigBitv, nbits: uint) -> bool {
174 self.process(b, nbits, |w1, w2| w1 | w2)
178 pub fn intersect(&mut self, b: &BigBitv, nbits: uint) -> bool {
179 self.process(b, nbits, |w1, w2| w1 & w2)
183 pub fn become(&mut self, b: &BigBitv, nbits: uint) -> bool {
184 self.process(b, nbits, |_, w| w)
188 pub fn difference(&mut self, b: &BigBitv, nbits: uint) -> bool {
189 self.process(b, nbits, |w1, w2| w1 & !w2)
193 pub fn get(&self, i: uint) -> bool {
194 let w = i / uint::BITS;
195 let b = i % uint::BITS;
196 let x = 1 & self.storage[w] >> b;
201 pub fn set(&mut self, i: uint, x: bool) {
202 let w = i / uint::BITS;
203 let b = i % uint::BITS;
205 self.storage[w] = if x { self.storage[w] | flag }
206 else { self.storage[w] & !flag };
210 pub fn equals(&self, b: &BigBitv, nbits: uint) -> bool {
211 for (i, elt) in b.storage.iter().enumerate() {
212 let mask = big_mask(nbits, i);
213 if mask & self.storage[i] != mask & *elt {
222 enum BitvVariant { Big(BigBitv), Small(SmallBitv) }
224 enum Op {Union, Intersect, Assign, Difference}
226 /// The bitvector type
229 /// Internal representation of the bit vector (small or large)
230 priv rep: BitvVariant,
231 /// The number of valid bits in the internal representation
236 fail!("Tried to do operation on bit vectors with different sizes");
241 fn do_op(&mut self, op: Op, other: &Bitv) -> bool {
242 if self.nbits != other.nbits {
246 Small(ref mut s) => match other.rep {
247 Small(ref s1) => match op {
248 Union => s.union(s1, self.nbits),
249 Intersect => s.intersect(s1, self.nbits),
250 Assign => s.become(s1, self.nbits),
251 Difference => s.difference(s1, self.nbits)
255 Big(ref mut s) => match other.rep {
257 Big(ref s1) => match op {
258 Union => s.union(s1, self.nbits),
259 Intersect => s.intersect(s1, self.nbits),
260 Assign => s.become(s1, self.nbits),
261 Difference => s.difference(s1, self.nbits)
270 pub fn new(nbits: uint, init: bool) -> Bitv {
271 let rep = if nbits < uint::BITS {
272 Small(SmallBitv::new(if init {(1<<nbits)-1} else {0}))
273 } else if nbits == uint::BITS {
274 Small(SmallBitv::new(if init {!0} else {0}))
276 let exact = nbits % uint::BITS == 0;
277 let nelems = nbits/uint::BITS + if exact {0} else {1};
281 slice::from_elem(nelems, !0u)
283 let mut v = slice::from_elem(nelems-1, !0u);
284 v.push((1<<nbits % uint::BITS)-1);
287 } else { slice::from_elem(nelems, 0u)};
290 Bitv {rep: rep, nbits: nbits}
294 * Calculates the union of two bitvectors
296 * Sets `self` to the union of `self` and `v1`. Both bitvectors must be
297 * the same length. Returns `true` if `self` changed.
300 pub fn union(&mut self, v1: &Bitv) -> bool { self.do_op(Union, v1) }
303 * Calculates the intersection of two bitvectors
305 * Sets `self` to the intersection of `self` and `v1`. Both bitvectors
306 * must be the same length. Returns `true` if `self` changed.
309 pub fn intersect(&mut self, v1: &Bitv) -> bool {
310 self.do_op(Intersect, v1)
314 * Assigns the value of `v1` to `self`
316 * Both bitvectors must be the same length. Returns `true` if `self` was
320 pub fn assign(&mut self, v: &Bitv) -> bool { self.do_op(Assign, v) }
322 /// Retrieve the value at index `i`
324 pub fn get(&self, i: uint) -> bool {
325 assert!((i < self.nbits));
327 Big(ref b) => b.get(i),
328 Small(ref s) => s.get(i)
333 * Set the value of a bit at a given index
335 * `i` must be less than the length of the bitvector.
338 pub fn set(&mut self, i: uint, x: bool) {
339 assert!((i < self.nbits));
341 Big(ref mut b) => b.set(i, x),
342 Small(ref mut s) => s.set(i, x)
347 * Compares two bitvectors
349 * Both bitvectors must be the same length. Returns `true` if both
350 * bitvectors contain identical elements.
353 pub fn equal(&self, v1: &Bitv) -> bool {
354 if self.nbits != v1.nbits { return false; }
356 Small(ref b) => match v1.rep {
357 Small(ref b1) => b.equals(b1, self.nbits),
360 Big(ref s) => match v1.rep {
361 Big(ref s1) => s.equals(s1, self.nbits),
362 Small(_) => return false
367 /// Set all bits to 0
369 pub fn clear(&mut self) {
371 Small(ref mut b) => b.clear(),
373 s.each_storage(|w| { *w = 0u; true });
378 /// Set all bits to 1
380 pub fn set_all(&mut self) {
382 Small(ref mut b) => b.set_all(),
384 s.each_storage(|w| { *w = !0u; true });
391 pub fn negate(&mut self) {
393 Small(ref mut s) => s.negate(),
394 Big(ref mut b) => b.negate(),
399 * Calculate the difference between two bitvectors
401 * Sets each element of `v0` to the value of that element minus the
402 * element of `v1` at the same index. Both bitvectors must be the same
405 * Returns `true` if `v0` was changed.
408 pub fn difference(&mut self, v: &Bitv) -> bool {
409 self.do_op(Difference, v)
412 /// Returns `true` if all bits are 1
414 pub fn is_true(&self) -> bool {
416 Small(ref b) => b.is_true(self.nbits),
418 for i in self.iter() { if !i { return false; } }
425 pub fn iter<'a>(&'a self) -> Bits<'a> {
426 Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
430 pub fn rev_iter<'a>(&'a self) -> Rev<Bits<'a>> {
434 /// Returns `true` if all bits are 0
435 pub fn is_false(&self) -> bool {
437 Small(ref b) => b.is_false(self.nbits),
439 for i in self.iter() { if i { return false; } }
445 pub fn init_to_vec(&self, i: uint) -> uint {
446 return if self.get(i) { 1 } else { 0 };
450 * Converts `self` to a vector of `uint` with the same length.
452 * Each `uint` in the resulting vector has either value `0u` or `1u`.
454 pub fn to_vec(&self) -> ~[uint] {
455 slice::from_fn(self.nbits, |x| self.init_to_vec(x))
459 * Organise the bits into bytes, such that the first bit in the
460 * `Bitv` becomes the high-order bit of the first byte. If the
461 * size of the `Bitv` is not a multiple of 8 then trailing bits
462 * will be filled-in with false/0
464 pub fn to_bytes(&self) -> ~[u8] {
465 fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
466 let offset = byte * 8 + bit;
467 if offset >= bitv.nbits {
470 bitv[offset] as u8 << (7 - bit)
474 let len = self.nbits/8 +
475 if self.nbits % 8 == 0 { 0 } else { 1 };
476 slice::from_fn(len, |i|
489 * Transform `self` into a `[bool]` by turning each bit into a `bool`.
491 pub fn to_bools(&self) -> ~[bool] {
492 slice::from_fn(self.nbits, |i| self[i])
496 * Converts `self` to a string.
498 * The resulting string has the same length as `self`, and each
499 * character is either '0' or '1'.
501 pub fn to_str(&self) -> ~str {
503 for i in self.iter() {
515 * Compare a bitvector to a vector of `bool`.
517 * Both the bitvector and vector must have the same length.
519 pub fn eq_vec(&self, v: &[bool]) -> bool {
520 assert_eq!(self.nbits, v.len());
522 while i < self.nbits {
523 if self.get(i) != v[i] { return false; }
529 pub fn ones(&self, f: |uint| -> bool) -> bool {
530 range(0u, self.nbits).advance(|i| !self.get(i) || f(i))
536 * Transform a byte-vector into a `Bitv`. Each byte becomes 8 bits,
537 * with the most significant bits of each byte coming first. Each
538 * bit becomes `true` if equal to 1 or `false` if equal to 0.
540 pub fn from_bytes(bytes: &[u8]) -> Bitv {
541 from_fn(bytes.len() * 8, |i| {
542 let b = bytes[i / 8] as uint;
544 b >> (7 - offset) & 1 == 1
549 * Transform a `[bool]` into a `Bitv` by converting each `bool` into a bit.
551 pub fn from_bools(bools: &[bool]) -> Bitv {
552 from_fn(bools.len(), |i| bools[i])
556 * Create a `Bitv` of the specified length where the value at each
557 * index is `f(index)`.
559 pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
560 let mut bitv = Bitv::new(len, false);
561 for i in range(0u, len) {
567 impl ops::Index<uint,bool> for Bitv {
568 fn index(&self, i: &uint) -> bool {
574 fn iterate_bits(base: uint, bits: uint, f: |uint| -> bool) -> bool {
578 for i in range(0u, uint::BITS) {
579 if bits & (1 << i) != 0 {
588 /// An iterator for `Bitv`.
589 pub struct Bits<'a> {
595 impl<'a> Iterator<bool> for Bits<'a> {
597 fn next(&mut self) -> Option<bool> {
598 if self.next_idx != self.end_idx {
599 let idx = self.next_idx;
601 Some(self.bitv.get(idx))
607 fn size_hint(&self) -> (uint, Option<uint>) {
608 let rem = self.end_idx - self.next_idx;
613 impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
615 fn next_back(&mut self) -> Option<bool> {
616 if self.next_idx != self.end_idx {
618 Some(self.bitv.get(self.end_idx))
625 impl<'a> ExactSize<bool> for Bits<'a> {}
627 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
629 fn indexable(&self) -> uint {
630 self.end_idx - self.next_idx
634 fn idx(&self, index: uint) -> Option<bool> {
635 if index >= self.indexable() {
638 Some(self.bitv.get(index))
643 /// An implementation of a set using a bit vector as an underlying
644 /// representation for holding numerical elements.
646 /// It should also be noted that the amount of storage necessary for holding a
647 /// set of objects is proportional to the maximum of the objects when viewed
653 // In theory this is a `Bitv` instead of always a `BigBitv`, but knowing that
654 // there's an array of storage makes our lives a whole lot easier when
655 // performing union/intersection/etc operations
660 /// Creates a new bit vector set with initially no contents
661 pub fn new() -> BitvSet {
662 BitvSet{ size: 0, bitv: BigBitv::new(~[0]) }
665 /// Creates a new bit vector set from the given bit vector
666 pub fn from_bitv(bitv: Bitv) -> BitvSet {
672 let Bitv{rep, ..} = bitv;
674 Big(b) => BitvSet{ size: size, bitv: b },
675 Small(SmallBitv{bits}) =>
676 BitvSet{ size: size, bitv: BigBitv{ storage: ~[bits] } },
680 /// Returns the capacity in bits for this bit vector. Inserting any
681 /// element less than this amount will not trigger a resizing.
682 pub fn capacity(&self) -> uint { self.bitv.storage.len() * uint::BITS }
684 /// Consumes this set to return the underlying bit vector
685 pub fn unwrap(self) -> Bitv {
686 let cap = self.capacity();
687 let BitvSet{bitv, ..} = self;
688 return Bitv{ nbits:cap, rep: Big(bitv) };
692 fn other_op(&mut self, other: &BitvSet, f: |uint, uint| -> uint) {
693 fn nbits(mut w: uint) -> uint {
695 for _ in range(0u, uint::BITS) {
704 if self.capacity() < other.capacity() {
705 self.bitv.storage.grow(other.capacity() / uint::BITS, &0);
707 for (i, &w) in other.bitv.storage.iter().enumerate() {
708 let old = self.bitv.storage[i];
710 self.bitv.storage[i] = new;
711 self.size += nbits(new) - nbits(old);
715 /// Union in-place with the specified other bit vector
716 pub fn union_with(&mut self, other: &BitvSet) {
717 self.other_op(other, |w1, w2| w1 | w2);
720 /// Intersect in-place with the specified other bit vector
721 pub fn intersect_with(&mut self, other: &BitvSet) {
722 self.other_op(other, |w1, w2| w1 & w2);
725 /// Difference in-place with the specified other bit vector
726 pub fn difference_with(&mut self, other: &BitvSet) {
727 self.other_op(other, |w1, w2| w1 & !w2);
730 /// Symmetric difference in-place with the specified other bit vector
731 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
732 self.other_op(other, |w1, w2| w1 ^ w2);
735 pub fn iter<'a>(&'a self) -> BitPositions<'a> {
736 BitPositions {set: self, next_idx: 0}
739 pub fn difference(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
740 for (i, w1, w2) in self.commons(other) {
741 if !iterate_bits(i, w1 & !w2, |b| f(&b)) {
745 /* everything we have that they don't also shows up */
746 self.outliers(other).advance(|(mine, i, w)|
747 !mine || iterate_bits(i, w, |b| f(&b))
751 pub fn symmetric_difference(&self, other: &BitvSet, f: |&uint| -> bool)
753 for (i, w1, w2) in self.commons(other) {
754 if !iterate_bits(i, w1 ^ w2, |b| f(&b)) {
758 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
761 pub fn intersection(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
762 self.commons(other).advance(|(i, w1, w2)| iterate_bits(i, w1 & w2, |b| f(&b)))
765 pub fn union(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
766 for (i, w1, w2) in self.commons(other) {
767 if !iterate_bits(i, w1 | w2, |b| f(&b)) {
771 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
775 impl cmp::Eq for BitvSet {
776 fn eq(&self, other: &BitvSet) -> bool {
777 if self.size != other.size {
780 for (_, w1, w2) in self.commons(other) {
785 for (_, _, w) in self.outliers(other) {
793 fn ne(&self, other: &BitvSet) -> bool { !self.eq(other) }
796 impl Container for BitvSet {
798 fn len(&self) -> uint { self.size }
801 impl Mutable for BitvSet {
802 fn clear(&mut self) {
803 self.bitv.each_storage(|w| { *w = 0; true });
808 impl Set<uint> for BitvSet {
809 fn contains(&self, value: &uint) -> bool {
810 *value < self.bitv.storage.len() * uint::BITS && self.bitv.get(*value)
813 fn is_disjoint(&self, other: &BitvSet) -> bool {
814 self.intersection(other, |_| false)
817 fn is_subset(&self, other: &BitvSet) -> bool {
818 for (_, w1, w2) in self.commons(other) {
823 /* If anything is not ours, then everything is not ours so we're
824 definitely a subset in that case. Otherwise if there's any stray
825 ones that 'other' doesn't have, we're not a subset. */
826 for (mine, _, w) in self.outliers(other) {
836 fn is_superset(&self, other: &BitvSet) -> bool {
837 other.is_subset(self)
841 impl MutableSet<uint> for BitvSet {
842 fn insert(&mut self, value: uint) -> bool {
843 if self.contains(&value) {
846 let nbits = self.capacity();
848 let newsize = cmp::max(value, nbits * 2) / uint::BITS + 1;
849 assert!(newsize > self.bitv.storage.len());
850 self.bitv.storage.grow(newsize, &0);
853 self.bitv.set(value, true);
857 fn remove(&mut self, value: &uint) -> bool {
858 if !self.contains(value) {
862 self.bitv.set(*value, false);
864 // Attempt to truncate our storage
865 let mut i = self.bitv.storage.len();
866 while i > 1 && self.bitv.storage[i - 1] == 0 {
869 self.bitv.storage.truncate(i);
876 /// Visits each of the words that the two bit vectors (`self` and `other`)
877 /// both have in common. The three yielded arguments are (bit location,
878 /// w1, w2) where the bit location is the number of bits offset so far,
879 /// and w1/w2 are the words coming from the two vectors self, other.
880 fn commons<'a>(&'a self, other: &'a BitvSet)
881 -> Map<'static, ((uint, &'a uint), &'a ~[uint]), (uint, uint, uint),
882 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<&'a ~[uint]>>> {
883 let min = cmp::min(self.bitv.storage.len(), other.bitv.storage.len());
884 self.bitv.storage.slice(0, min).iter().enumerate()
885 .zip(Repeat::new(&other.bitv.storage))
886 .map(|((i, &w), o_store)| (i * uint::BITS, w, o_store[i]))
889 /// Visits each word in `self` or `other` that extends beyond the other. This
890 /// will only iterate through one of the vectors, and it only iterates
891 /// over the portion that doesn't overlap with the other one.
893 /// The yielded arguments are a `bool`, the bit offset, and a word. The `bool`
894 /// is true if the word comes from `self`, and `false` if it comes from
896 fn outliers<'a>(&'a self, other: &'a BitvSet)
897 -> Map<'static, ((uint, &'a uint), uint), (bool, uint, uint),
898 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<uint>>> {
899 let slen = self.bitv.storage.len();
900 let olen = other.bitv.storage.len();
903 self.bitv.storage.slice_from(olen).iter().enumerate()
904 .zip(Repeat::new(olen))
905 .map(|((i, &w), min)| (true, (i + min) * uint::BITS, w))
907 other.bitv.storage.slice_from(slen).iter().enumerate()
908 .zip(Repeat::new(slen))
909 .map(|((i, &w), min)| (false, (i + min) * uint::BITS, w))
914 pub struct BitPositions<'a> {
915 priv set: &'a BitvSet,
919 impl<'a> Iterator<uint> for BitPositions<'a> {
921 fn next(&mut self) -> Option<uint> {
922 while self.next_idx < self.set.capacity() {
923 let idx = self.next_idx;
926 if self.set.contains(&idx) {
934 fn size_hint(&self) -> (uint, Option<uint>) {
935 (0, Some(self.set.capacity() - self.next_idx))
942 use self::test::BenchHarness;
944 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(), ~"");
960 let eightbits = Bitv::new(8u, false);
961 assert_eq!(eightbits.to_str(), ~"00000000");
965 fn test_0_elements() {
966 let act = Bitv::new(0u, false);
967 let exp = slice::from_elem::<bool>(0u, false);
968 assert!(act.eq_vec(exp));
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");
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" + "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(), ~[0b10100000]);
1304 let mut bv = Bitv::new(9, false);
1307 assert_eq!(bv.to_bytes(), ~[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 = ~[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: ~[uint] = bitv.iter().collect();
1338 assert_eq!(idxs, ~[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));
1554 fn rng() -> rand::IsaacRng {
1555 let seed = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
1556 rand::SeedableRng::from_seed(seed)
1560 fn bench_uint_small(b: &mut BenchHarness) {
1562 let mut bitv = 0 as uint;
1564 bitv |= 1 << ((r.next_u32() as uint) % uint::BITS);
1570 fn bench_small_bitv_small(b: &mut BenchHarness) {
1572 let mut bitv = SmallBitv::new(uint::BITS);
1574 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1580 fn bench_big_bitv_small(b: &mut BenchHarness) {
1582 let mut bitv = BigBitv::new(~[0]);
1584 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1590 fn bench_big_bitv_big(b: &mut BenchHarness) {
1592 let mut storage = ~[];
1593 storage.grow(BENCH_BITS / uint::BITS, &0u);
1594 let mut bitv = BigBitv::new(storage);
1596 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1602 fn bench_bitv_big(b: &mut BenchHarness) {
1604 let mut bitv = Bitv::new(BENCH_BITS, false);
1606 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1612 fn bench_bitv_small(b: &mut BenchHarness) {
1614 let mut bitv = Bitv::new(uint::BITS, false);
1616 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1622 fn bench_bitv_set_small(b: &mut BenchHarness) {
1624 let mut bitv = BitvSet::new();
1626 bitv.insert((r.next_u32() as uint) % uint::BITS);
1632 fn bench_bitv_set_big(b: &mut BenchHarness) {
1634 let mut bitv = BitvSet::new();
1636 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
1642 fn bench_bitv_big_union(b: &mut BenchHarness) {
1643 let mut b1 = Bitv::new(BENCH_BITS, false);
1644 let b2 = Bitv::new(BENCH_BITS, false);
1651 fn bench_btv_small_iter(b: &mut BenchHarness) {
1652 let bitv = Bitv::new(uint::BITS, false);
1655 for pres in bitv.iter() {
1656 _sum += pres as uint;
1662 fn bench_bitv_big_iter(b: &mut BenchHarness) {
1663 let bitv = Bitv::new(BENCH_BITS, false);
1666 for pres in bitv.iter() {
1667 _sum += pres as uint;
1673 fn bench_bitvset_iter(b: &mut BenchHarness) {
1674 let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
1675 |idx| {idx % 3 == 0}));
1678 for idx in bitv.iter() {