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.
4 //
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.
10
11 #![allow(missing_doc)]
12
13
14 use std::cmp;
15 use std::iter::RandomAccessIterator;
16 use std::iter::{Rev, Enumerate, Repeat, Map, Zip};
17 use std::ops;
18 use std::slice;
19 use std::strbuf::StrBuf;
20 use std::uint;
21
22 #[deriving(Clone)]
23 struct SmallBitv {
24 /// only the lowest nbits of this value are used. the rest is undefined.
25 bits: uint
26 }
27
28 /// a mask that has a 1 for each defined bit in a small_bitv, assuming n bits
29 #[inline]
30 fn small_mask(nbits: uint) -> uint {
31 (1 << nbits) - 1
32 }
33
34 impl SmallBitv {
35 pub fn new(bits: uint) -> SmallBitv {
36 SmallBitv {bits: bits}
37 }
38
39 #[inline]
40 pub fn bits_op(&mut self,
41 right_bits: uint,
42 nbits: uint,
43 f: |uint, uint| -> uint)
44 -> bool {
45 let mask = small_mask(nbits);
46 let old_b: uint = self.bits;
47 let new_b = f(old_b, right_bits);
48 self.bits = new_b;
49 mask & old_b != mask & new_b
50 }
51
52 #[inline]
53 pub fn union(&mut self, s: &SmallBitv, nbits: uint) -> bool {
54 self.bits_op(s.bits, nbits, |u1, u2| u1 | u2)
55 }
56
57 #[inline]
58 pub fn intersect(&mut self, s: &SmallBitv, nbits: uint) -> bool {
59 self.bits_op(s.bits, nbits, |u1, u2| u1 & u2)
60 }
61
62 #[inline]
63 pub fn become(&mut self, s: &SmallBitv, nbits: uint) -> bool {
64 self.bits_op(s.bits, nbits, |_u1, u2| u2)
65 }
66
67 #[inline]
68 pub fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool {
69 self.bits_op(s.bits, nbits, |u1, u2| u1 & !u2)
70 }
71
72 #[inline]
73 pub fn get(&self, i: uint) -> bool {
74 (self.bits & (1 << i)) != 0
75 }
76
77 #[inline]
78 pub fn set(&mut self, i: uint, x: bool) {
79 if x {
80 self.bits |= 1<<i;
81 }
82 else {
83 self.bits &= !(1<<i);
84 }
85 }
86
87 #[inline]
88 pub fn equals(&self, b: &SmallBitv, nbits: uint) -> bool {
89 let mask = small_mask(nbits);
90 mask & self.bits == mask & b.bits
91 }
92
93 #[inline]
94 pub fn clear(&mut self) { self.bits = 0; }
95
96 #[inline]
97 pub fn set_all(&mut self) { self.bits = !0; }
98
99 #[inline]
100 pub fn all(&self, nbits: uint) -> bool {
101 small_mask(nbits) & !self.bits == 0
102 }
103
104 #[inline]
105 pub fn none(&self, nbits: uint) -> bool {
106 small_mask(nbits) & self.bits == 0
107 }
108
109 #[inline]
110 pub fn negate(&mut self) { self.bits = !self.bits; }
111 }
112
113 #[deriving(Clone)]
114 struct BigBitv {
115 storage: Vec<uint>
116 }
117
118 /**
119 * A mask that has a 1 for each defined bit in the n'th element of a `BigBitv`,
120 * assuming n bits.
121 */
122 #[inline]
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};
126
127 if elem < nelems - 1 || rmd == 0 {
128 !0
129 } else {
130 (1 << rmd) - 1
131 }
132 }
133
134 impl BigBitv {
135 pub fn new(storage: Vec<uint>) -> BigBitv {
136 BigBitv {storage: storage}
137 }
138
139 #[inline]
140 pub fn process(&mut self,
141 b: &BigBitv,
142 nbits: uint,
143 op: |uint, uint| -> uint)
144 -> bool {
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())
150 .enumerate() {
151 let mask = big_mask(nbits, i);
152 let w0 = *a & mask;
153 let w1 = *b & mask;
154 let w = op(w0, w1) & mask;
155 if w0 != w {
156 changed = true;
157 *a = w;
158 }
159 }
160 changed
161 }
162
163 #[inline]
164 pub fn each_storage(&mut self, op: |v: &mut uint| -> bool) -> bool {
165 self.storage.mut_iter().advance(|elt| op(elt))
166 }
167
168 #[inline]
169 pub fn negate(&mut self) {
170 self.each_storage(|w| { *w = !*w; true });
171 }
172
173 #[inline]
174 pub fn union(&mut self, b: &BigBitv, nbits: uint) -> bool {
175 self.process(b, nbits, |w1, w2| w1 | w2)
176 }
177
178 #[inline]
179 pub fn intersect(&mut self, b: &BigBitv, nbits: uint) -> bool {
180 self.process(b, nbits, |w1, w2| w1 & w2)
181 }
182
183 #[inline]
184 pub fn become(&mut self, b: &BigBitv, nbits: uint) -> bool {
185 self.process(b, nbits, |_, w| w)
186 }
187
188 #[inline]
189 pub fn difference(&mut self, b: &BigBitv, nbits: uint) -> bool {
190 self.process(b, nbits, |w1, w2| w1 & !w2)
191 }
192
193 #[inline]
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;
198 x == 1
199 }
200
201 #[inline]
202 pub fn set(&mut self, i: uint, x: bool) {
203 let w = i / uint::BITS;
204 let b = i % uint::BITS;
205 let flag = 1 << b;
206 *self.storage.get_mut(w) = if x { *self.storage.get(w) | flag }
207 else { *self.storage.get(w) & !flag };
208 }
209
210 #[inline]
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 {
215 return false;
216 }
217 }
218 true
219 }
220 }
221
222 #[deriving(Clone)]
223 enum BitvVariant { Big(BigBitv), Small(SmallBitv) }
224
225 enum Op {Union, Intersect, Assign, Difference}
226
227 /// The bitvector type
228 ///
229 /// # Example
230 ///
231 /// ```rust
232 /// use collections::bitv::Bitv;
233 ///
234 /// let mut bv = Bitv::new(10, false);
235 ///
236 /// // insert all primes less than 10
237 /// bv.set(2, true);
238 /// bv.set(3, true);
239 /// bv.set(5, true);
240 /// bv.set(7, true);
241 /// println!("{}", bv.to_str());
242 /// println!("total bits set to true: {}", bv.iter().count(|x| x));
243 ///
244 /// // flip all values in bitvector, producing non-primes less than 10
245 /// bv.negate();
246 /// println!("{}", bv.to_str());
247 /// println!("total bits set to true: {}", bv.iter().count(|x| x));
248 ///
249 /// // reset bitvector to empty
250 /// bv.clear();
251 /// println!("{}", bv.to_str());
252 /// println!("total bits set to true: {}", bv.iter().count(|x| x));
253 /// ```
254 #[deriving(Clone)]
255 pub struct Bitv {
256 /// Internal representation of the bit vector (small or large)
257 rep: BitvVariant,
258 /// The number of valid bits in the internal representation
259 nbits: uint
260 }
261
262 fn die() -> ! {
263 fail!("Tried to do operation on bit vectors with different sizes");
264 }
265
266 impl Bitv {
267 #[inline]
268 fn do_op(&mut self, op: Op, other: &Bitv) -> bool {
269 if self.nbits != other.nbits {
270 die();
271 }
272 match self.rep {
273 Small(ref mut s) => match other.rep {
274 Small(ref s1) => match op {
275 Union => s.union(s1, self.nbits),
276 Intersect => s.intersect(s1, self.nbits),
277 Assign => s.become(s1, self.nbits),
278 Difference => s.difference(s1, self.nbits)
279 },
280 Big(_) => die()
281 },
282 Big(ref mut s) => match other.rep {
283 Small(_) => die(),
284 Big(ref s1) => match op {
285 Union => s.union(s1, self.nbits),
286 Intersect => s.intersect(s1, self.nbits),
287 Assign => s.become(s1, self.nbits),
288 Difference => s.difference(s1, self.nbits)
289 }
290 }
291 }
292 }
293 }
294
295 impl Bitv {
296 /// Creates an empty Bitv that holds `nbits` elements, setting each element
297 /// to `init`.
298 pub fn new(nbits: uint, init: bool) -> Bitv {
299 let rep = if nbits < uint::BITS {
300 Small(SmallBitv::new(if init {(1<<nbits)-1} else {0}))
301 } else if nbits == uint::BITS {
302 Small(SmallBitv::new(if init {!0} else {0}))
303 } else {
304 let exact = nbits % uint::BITS == 0;
305 let nelems = nbits/uint::BITS + if exact {0} else {1};
306 let s =
307 if init {
308 if exact {
309 Vec::from_elem(nelems, !0u)
310 } else {
311 let mut v = Vec::from_elem(nelems-1, !0u);
312 v.push((1<<nbits % uint::BITS)-1);
313 v
314 }
315 } else { Vec::from_elem(nelems, 0u)};
316 Big(BigBitv::new(s))
317 };
318 Bitv {rep: rep, nbits: nbits}
319 }
320
321 /**
322 * Calculates the union of two bitvectors
323 *
324 * Sets `self` to the union of `self` and `v1`. Both bitvectors must be
325 * the same length. Returns `true` if `self` changed.
326 */
327 #[inline]
328 pub fn union(&mut self, v1: &Bitv) -> bool { self.do_op(Union, v1) }
329
330 /**
331 * Calculates the intersection of two bitvectors
332 *
333 * Sets `self` to the intersection of `self` and `v1`. Both bitvectors
334 * must be the same length. Returns `true` if `self` changed.
335 */
336 #[inline]
337 pub fn intersect(&mut self, v1: &Bitv) -> bool {
338 self.do_op(Intersect, v1)
339 }
340
341 /**
342 * Assigns the value of `v1` to `self`
343 *
344 * Both bitvectors must be the same length. Returns `true` if `self` was
345 * changed
346 */
347 #[inline]
348 pub fn assign(&mut self, v: &Bitv) -> bool { self.do_op(Assign, v) }
349
350 /// Retrieve the value at index `i`
351 #[inline]
352 pub fn get(&self, i: uint) -> bool {
353 assert!((i < self.nbits));
354 match self.rep {
355 Big(ref b) => b.get(i),
356 Small(ref s) => s.get(i)
357 }
358 }
359
360 /**
361 * Set the value of a bit at a given index
362 *
363 * `i` must be less than the length of the bitvector.
364 */
365 #[inline]
366 pub fn set(&mut self, i: uint, x: bool) {
367 assert!((i < self.nbits));
368 match self.rep {
369 Big(ref mut b) => b.set(i, x),
370 Small(ref mut s) => s.set(i, x)
371 }
372 }
373
374 /**
375 * Compares two bitvectors
376 *
377 * Both bitvectors must be the same length. Returns `true` if both
378 * bitvectors contain identical elements.
379 */
380 #[inline]
381 pub fn equal(&self, v1: &Bitv) -> bool {
382 if self.nbits != v1.nbits { return false; }
383 match self.rep {
384 Small(ref b) => match v1.rep {
385 Small(ref b1) => b.equals(b1, self.nbits),
386 _ => false
387 },
388 Big(ref s) => match v1.rep {
389 Big(ref s1) => s.equals(s1, self.nbits),
390 Small(_) => return false
391 }
392 }
393 }
394
395 /// Set all bits to 0
396 #[inline]
397 pub fn clear(&mut self) {
398 match self.rep {
399 Small(ref mut b) => b.clear(),
400 Big(ref mut s) => {
401 s.each_storage(|w| { *w = 0u; true });
402 }
403 }
404 }
405
406 /// Set all bits to 1
407 #[inline]
408 pub fn set_all(&mut self) {
409 match self.rep {
410 Small(ref mut b) => b.set_all(),
411 Big(ref mut s) => {
412 s.each_storage(|w| { *w = !0u; true });
413 }
414 }
415 }
416
417 /// Flip all bits
418 #[inline]
419 pub fn negate(&mut self) {
420 match self.rep {
421 Small(ref mut s) => s.negate(),
422 Big(ref mut b) => b.negate(),
423 }
424 }
425
426 /**
427 * Calculate the difference between two bitvectors
428 *
429 * Sets each element of `v0` to the value of that element minus the
430 * element of `v1` at the same index. Both bitvectors must be the same
431 * length.
432 *
433 * Returns `true` if `v0` was changed.
434 */
435 #[inline]
436 pub fn difference(&mut self, v: &Bitv) -> bool {
437 self.do_op(Difference, v)
438 }
439
440 /// Returns `true` if all bits are 1
441 #[inline]
442 pub fn all(&self) -> bool {
443 match self.rep {
444 Small(ref b) => b.all(self.nbits),
445 _ => self.iter().all(|x| x)
446 }
447 }
448
449 /// Returns an iterator over the elements of the vector in order.
450 ///
451 /// # Example
452 ///
453 /// ```rust
454 /// use collections::bitv::Bitv;
455 /// let mut bv = Bitv::new(10, false);
456 /// bv.set(1, true);
457 /// bv.set(2, true);
458 /// bv.set(3, true);
459 /// bv.set(5, true);
460 /// bv.set(8, true);
461 /// // Count bits set to 1; result should be 5
462 /// println!("{}", bv.iter().count(|x| x));
463 /// ```
464 #[inline]
465 pub fn iter<'a>(&'a self) -> Bits<'a> {
466 Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
467 }
468
469 #[inline]
470 #[deprecated = "replaced by .iter().rev()"]
471 pub fn rev_iter<'a>(&'a self) -> Rev<Bits<'a>> {
472 self.iter().rev()
473 }
474
475 /// Returns `true` if all bits are 0
476 pub fn none(&self) -> bool {
477 match self.rep {
478 Small(ref b) => b.none(self.nbits),
479 _ => self.iter().all(|x| !x)
480 }
481 }
482
483 #[inline]
484 /// Returns `true` if any bit is 1
485 pub fn any(&self) -> bool {
486 !self.none()
487 }
488
489 pub fn init_to_vec(&self, i: uint) -> uint {
490 return if self.get(i) { 1 } else { 0 };
491 }
492
493 /**
494 * Converts `self` to a vector of `uint` with the same length.
495 *
496 * Each `uint` in the resulting vector has either value `0u` or `1u`.
497 */
498 pub fn to_vec(&self) -> Vec<uint> {
499 Vec::from_fn(self.nbits, |x| self.init_to_vec(x))
500 }
501
502 /**
503 * Organise the bits into bytes, such that the first bit in the
504 * `Bitv` becomes the high-order bit of the first byte. If the
505 * size of the `Bitv` is not a multiple of 8 then trailing bits
506 * will be filled-in with false/0
507 */
508 pub fn to_bytes(&self) -> Vec<u8> {
509 fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
510 let offset = byte * 8 + bit;
511 if offset >= bitv.nbits {
512 0
513 } else {
514 bitv[offset] as u8 << (7 - bit)
515 }
516 }
517
518 let len = self.nbits/8 +
519 if self.nbits % 8 == 0 { 0 } else { 1 };
520 Vec::from_fn(len, |i|
521 bit(self, i, 0) |
522 bit(self, i, 1) |
523 bit(self, i, 2) |
524 bit(self, i, 3) |
525 bit(self, i, 4) |
526 bit(self, i, 5) |
527 bit(self, i, 6) |
528 bit(self, i, 7)
529 )
530 }
531
532 /**
533 * Transform `self` into a `Vec<bool>` by turning each bit into a `bool`.
534 */
535 pub fn to_bools(&self) -> Vec<bool> {
536 Vec::from_fn(self.nbits, |i| self[i])
537 }
538
539 /**
540 * Converts `self` to a string.
541 *
542 * The resulting string has the same length as `self`, and each
543 * character is either '0' or '1'.
544 */
545 pub fn to_str(&self) -> ~str {
546 let mut rs = StrBuf::new();
547 for i in self.iter() {
548 if i {
549 rs.push_char('1');
550 } else {
551 rs.push_char('0');
552 }
553 };
554 rs.into_owned()
555 }
556
557
558 /**
559 * Compare a bitvector to a vector of `bool`.
560 *
561 * Both the bitvector and vector must have the same length.
562 */
563 pub fn eq_vec(&self, v: &[bool]) -> bool {
564 assert_eq!(self.nbits, v.len());
565 let mut i = 0;
566 while i < self.nbits {
567 if self.get(i) != v[i] { return false; }
568 i = i + 1;
569 }
570 true
571 }
572
573 pub fn ones(&self, f: |uint| -> bool) -> bool {
574 range(0u, self.nbits).advance(|i| !self.get(i) || f(i))
575 }
576
577 }
578
579 /**
580 * Transform a byte-vector into a `Bitv`. Each byte becomes 8 bits,
581 * with the most significant bits of each byte coming first. Each
582 * bit becomes `true` if equal to 1 or `false` if equal to 0.
583 */
584 pub fn from_bytes(bytes: &[u8]) -> Bitv {
585 from_fn(bytes.len() * 8, |i| {
586 let b = bytes[i / 8] as uint;
587 let offset = i % 8;
588 b >> (7 - offset) & 1 == 1
589 })
590 }
591
592 /**
593 * Transform a `[bool]` into a `Bitv` by converting each `bool` into a bit.
594 */
595 pub fn from_bools(bools: &[bool]) -> Bitv {
596 from_fn(bools.len(), |i| bools[i])
597 }
598
599 /**
600 * Create a `Bitv` of the specified length where the value at each
601 * index is `f(index)`.
602 */
603 pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
604 let mut bitv = Bitv::new(len, false);
605 for i in range(0u, len) {
606 bitv.set(i, f(i));
607 }
608 bitv
609 }
610
611 impl ops::Index<uint,bool> for Bitv {
612 fn index(&self, i: &uint) -> bool {
613 self.get(*i)
614 }
615 }
616
617 #[inline]
618 fn iterate_bits(base: uint, bits: uint, f: |uint| -> bool) -> bool {
619 if bits == 0 {
620 return true;
621 }
622 for i in range(0u, uint::BITS) {
623 if bits & (1 << i) != 0 {
624 if !f(base + i) {
625 return false;
626 }
627 }
628 }
629 return true;
630 }
631
632 /// An iterator for `Bitv`.
633 pub struct Bits<'a> {
634 bitv: &'a Bitv,
635 next_idx: uint,
636 end_idx: uint,
637 }
638
639 impl<'a> Iterator<bool> for Bits<'a> {
640 #[inline]
641 fn next(&mut self) -> Option<bool> {
642 if self.next_idx != self.end_idx {
643 let idx = self.next_idx;
644 self.next_idx += 1;
645 Some(self.bitv.get(idx))
646 } else {
647 None
648 }
649 }
650
651 fn size_hint(&self) -> (uint, Option<uint>) {
652 let rem = self.end_idx - self.next_idx;
653 (rem, Some(rem))
654 }
655 }
656
657 impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
658 #[inline]
659 fn next_back(&mut self) -> Option<bool> {
660 if self.next_idx != self.end_idx {
661 self.end_idx -= 1;
662 Some(self.bitv.get(self.end_idx))
663 } else {
664 None
665 }
666 }
667 }
668
669 impl<'a> ExactSize<bool> for Bits<'a> {}
670
671 impl<'a> RandomAccessIterator<bool> for Bits<'a> {
672 #[inline]
673 fn indexable(&self) -> uint {
674 self.end_idx - self.next_idx
675 }
676
677 #[inline]
678 fn idx(&mut self, index: uint) -> Option<bool> {
679 if index >= self.indexable() {
680 None
681 } else {
682 Some(self.bitv.get(index))
683 }
684 }
685 }
686
687 /// An implementation of a set using a bit vector as an underlying
688 /// representation for holding numerical elements.
689 ///
690 /// It should also be noted that the amount of storage necessary for holding a
691 /// set of objects is proportional to the maximum of the objects when viewed
692 /// as a `uint`.
693 #[deriving(Clone)]
694 pub struct BitvSet {
695 size: uint,
696
697 // In theory this is a `Bitv` instead of always a `BigBitv`, but knowing that
698 // there's an array of storage makes our lives a whole lot easier when
699 // performing union/intersection/etc operations
700 bitv: BigBitv
701 }
702
703 impl BitvSet {
704 /// Creates a new bit vector set with initially no contents
705 pub fn new() -> BitvSet {
706 BitvSet{ size: 0, bitv: BigBitv::new(vec!(0)) }
707 }
708
709 /// Creates a new bit vector set from the given bit vector
710 pub fn from_bitv(bitv: Bitv) -> BitvSet {
711 let mut size = 0;
712 bitv.ones(|_| {
713 size += 1;
714 true
715 });
716 let Bitv{rep, ..} = bitv;
717 match rep {
718 Big(b) => BitvSet{ size: size, bitv: b },
719 Small(SmallBitv{bits}) =>
720 BitvSet{ size: size, bitv: BigBitv{ storage: vec!(bits) } },
721 }
722 }
723
724 /// Returns the capacity in bits for this bit vector. Inserting any
725 /// element less than this amount will not trigger a resizing.
726 pub fn capacity(&self) -> uint { self.bitv.storage.len() * uint::BITS }
727
728 /// Consumes this set to return the underlying bit vector
729 pub fn unwrap(self) -> Bitv {
730 let cap = self.capacity();
731 let BitvSet{bitv, ..} = self;
732 return Bitv{ nbits:cap, rep: Big(bitv) };
733 }
734
735 #[inline]
736 fn other_op(&mut self, other: &BitvSet, f: |uint, uint| -> uint) {
737 fn nbits(mut w: uint) -> uint {
738 let mut bits = 0;
739 for _ in range(0u, uint::BITS) {
740 if w == 0 {
741 break;
742 }
743 bits += w & 1;
744 w >>= 1;
745 }
746 return bits;
747 }
748 if self.capacity() < other.capacity() {
749 self.bitv.storage.grow(other.capacity() / uint::BITS, &0);
750 }
751 for (i, &w) in other.bitv.storage.iter().enumerate() {
752 let old = *self.bitv.storage.get(i);
753 let new = f(old, w);
754 *self.bitv.storage.get_mut(i) = new;
755 self.size += nbits(new) - nbits(old);
756 }
757 }
758
759 /// Union in-place with the specified other bit vector
760 pub fn union_with(&mut self, other: &BitvSet) {
761 self.other_op(other, |w1, w2| w1 | w2);
762 }
763
764 /// Intersect in-place with the specified other bit vector
765 pub fn intersect_with(&mut self, other: &BitvSet) {
766 self.other_op(other, |w1, w2| w1 & w2);
767 }
768
769 /// Difference in-place with the specified other bit vector
770 pub fn difference_with(&mut self, other: &BitvSet) {
771 self.other_op(other, |w1, w2| w1 & !w2);
772 }
773
774 /// Symmetric difference in-place with the specified other bit vector
775 pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
776 self.other_op(other, |w1, w2| w1 ^ w2);
777 }
778
779 pub fn iter<'a>(&'a self) -> BitPositions<'a> {
780 BitPositions {set: self, next_idx: 0}
781 }
782
783 pub fn difference(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
784 for (i, w1, w2) in self.commons(other) {
785 if !iterate_bits(i, w1 & !w2, |b| f(&b)) {
786 return false
787 }
788 };
789 /* everything we have that they don't also shows up */
790 self.outliers(other).advance(|(mine, i, w)|
791 !mine || iterate_bits(i, w, |b| f(&b))
792 )
793 }
794
795 pub fn symmetric_difference(&self, other: &BitvSet, f: |&uint| -> bool)
796 -> bool {
797 for (i, w1, w2) in self.commons(other) {
798 if !iterate_bits(i, w1 ^ w2, |b| f(&b)) {
799 return false
800 }
801 };
802 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
803 }
804
805 pub fn intersection(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
806 self.commons(other).advance(|(i, w1, w2)| iterate_bits(i, w1 & w2, |b| f(&b)))
807 }
808
809 pub fn union(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
810 for (i, w1, w2) in self.commons(other) {
811 if !iterate_bits(i, w1 | w2, |b| f(&b)) {
812 return false
813 }
814 };
815 self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
816 }
817 }
818
819 impl cmp::Eq for BitvSet {
820 fn eq(&self, other: &BitvSet) -> bool {
821 if self.size != other.size {
822 return false;
823 }
824 for (_, w1, w2) in self.commons(other) {
825 if w1 != w2 {
826 return false;
827 }
828 }
829 for (_, _, w) in self.outliers(other) {
830 if w != 0 {
831 return false;
832 }
833 }
834 return true;
835 }
836
837 fn ne(&self, other: &BitvSet) -> bool { !self.eq(other) }
838 }
839
840 impl Container for BitvSet {
841 #[inline]
842 fn len(&self) -> uint { self.size }
843 }
844
845 impl Mutable for BitvSet {
846 fn clear(&mut self) {
847 self.bitv.each_storage(|w| { *w = 0; true });
848 self.size = 0;
849 }
850 }
851
852 impl Set<uint> for BitvSet {
853 fn contains(&self, value: &uint) -> bool {
854 *value < self.bitv.storage.len() * uint::BITS && self.bitv.get(*value)
855 }
856
857 fn is_disjoint(&self, other: &BitvSet) -> bool {
858 self.intersection(other, |_| false)
859 }
860
861 fn is_subset(&self, other: &BitvSet) -> bool {
862 for (_, w1, w2) in self.commons(other) {
863 if w1 & w2 != w1 {
864 return false;
865 }
866 }
867 /* If anything is not ours, then everything is not ours so we're
868 definitely a subset in that case. Otherwise if there's any stray
869 ones that 'other' doesn't have, we're not a subset. */
870 for (mine, _, w) in self.outliers(other) {
871 if !mine {
872 return true;
873 } else if w != 0 {
874 return false;
875 }
876 }
877 return true;
878 }
879
880 fn is_superset(&self, other: &BitvSet) -> bool {
881 other.is_subset(self)
882 }
883 }
884
885 impl MutableSet<uint> for BitvSet {
886 fn insert(&mut self, value: uint) -> bool {
887 if self.contains(&value) {
888 return false;
889 }
890 let nbits = self.capacity();
891 if value >= nbits {
892 let newsize = cmp::max(value, nbits * 2) / uint::BITS + 1;
893 assert!(newsize > self.bitv.storage.len());
894 self.bitv.storage.grow(newsize, &0);
895 }
896 self.size += 1;
897 self.bitv.set(value, true);
898 return true;
899 }
900
901 fn remove(&mut self, value: &uint) -> bool {
902 if !self.contains(value) {
903 return false;
904 }
905 self.size -= 1;
906 self.bitv.set(*value, false);
907
908 // Attempt to truncate our storage
909 let mut i = self.bitv.storage.len();
910 while i > 1 && *self.bitv.storage.get(i - 1) == 0 {
911 i -= 1;
912 }
913 self.bitv.storage.truncate(i);
914
915 return true;
916 }
917 }
918
919 impl BitvSet {
920 /// Visits each of the words that the two bit vectors (`self` and `other`)
921 /// both have in common. The three yielded arguments are (bit location,
922 /// w1, w2) where the bit location is the number of bits offset so far,
923 /// and w1/w2 are the words coming from the two vectors self, other.
924 fn commons<'a>(&'a self, other: &'a BitvSet)
925 -> Map<'static, ((uint, &'a uint), &'a Vec<uint>), (uint, uint, uint),
926 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<&'a Vec<uint>>>> {
927 let min = cmp::min(self.bitv.storage.len(), other.bitv.storage.len());
928 self.bitv.storage.slice(0, min).iter().enumerate()
929 .zip(Repeat::new(&other.bitv.storage))
930 .map(|((i, &w), o_store)| (i * uint::BITS, w, *o_store.get(i)))
931 }
932
933 /// Visits each word in `self` or `other` that extends beyond the other. This
934 /// will only iterate through one of the vectors, and it only iterates
935 /// over the portion that doesn't overlap with the other one.
936 ///
937 /// The yielded arguments are a `bool`, the bit offset, and a word. The `bool`
938 /// is true if the word comes from `self`, and `false` if it comes from
939 /// `other`.
940 fn outliers<'a>(&'a self, other: &'a BitvSet)
941 -> Map<'static, ((uint, &'a uint), uint), (bool, uint, uint),
942 Zip<Enumerate<slice::Items<'a, uint>>, Repeat<uint>>> {
943 let slen = self.bitv.storage.len();
944 let olen = other.bitv.storage.len();
945
946 if olen < slen {
947 self.bitv.storage.slice_from(olen).iter().enumerate()
948 .zip(Repeat::new(olen))
949 .map(|((i, &w), min)| (true, (i + min) * uint::BITS, w))
950 } else {
951 other.bitv.storage.slice_from(slen).iter().enumerate()
952 .zip(Repeat::new(slen))
953 .map(|((i, &w), min)| (false, (i + min) * uint::BITS, w))
954 }
955 }
956 }
957
958 pub struct BitPositions<'a> {
959 set: &'a BitvSet,
960 next_idx: uint
961 }
962
963 impl<'a> Iterator<uint> for BitPositions<'a> {
964 #[inline]
965 fn next(&mut self) -> Option<uint> {
966 while self.next_idx < self.set.capacity() {
967 let idx = self.next_idx;
968 self.next_idx += 1;
969
970 if self.set.contains(&idx) {
971 return Some(idx);
972 }
973 }
974
975 return None;
976 }
977
978 fn size_hint(&self) -> (uint, Option<uint>) {
979 (0, Some(self.set.capacity() - self.next_idx))
980 }
981 }
982
983 #[cfg(test)]
984 mod tests {
985 extern crate test;
986 use self::test::Bencher;
987
988 use bitv::{Bitv, SmallBitv, BigBitv, BitvSet, from_bools, from_fn,
989 from_bytes};
990 use bitv;
991
992 use std::uint;
993 use rand;
994 use rand::Rng;
995
996 static BENCH_BITS : uint = 1 << 14;
997
998 #[test]
999 fn test_to_str() {
1000 let zerolen = Bitv::new(0u, false);
1001 assert_eq!(zerolen.to_str(), "".to_owned());
1002
1003 let eightbits = Bitv::new(8u, false);
1004 assert_eq!(eightbits.to_str(), "00000000".to_owned());
1005 }
1006
1007 #[test]
1008 fn test_0_elements() {
1009 let act = Bitv::new(0u, false);
1010 let exp = Vec::from_elem(0u, false);
1011 assert!(act.eq_vec(exp.as_slice()));
1012 }
1013
1014 #[test]
1015 fn test_1_element() {
1016 let mut act = Bitv::new(1u, false);
1017 assert!(act.eq_vec([false]));
1018 act = Bitv::new(1u, true);
1019 assert!(act.eq_vec([true]));
1020 }
1021
1022 #[test]
1023 fn test_2_elements() {
1024 let mut b = bitv::Bitv::new(2, false);
1025 b.set(0, true);
1026 b.set(1, false);
1027 assert_eq!(b.to_str(), "10".to_owned());
1028 }
1029
1030 #[test]
1031 fn test_10_elements() {
1032 let mut act;
1033 // all 0
1034
1035 act = Bitv::new(10u, false);
1036 assert!((act.eq_vec(
1037 [false, false, false, false, false, false, false, false, false, false])));
1038 // all 1
1039
1040 act = Bitv::new(10u, true);
1041 assert!((act.eq_vec([true, true, true, true, true, true, true, true, true, true])));
1042 // mixed
1043
1044 act = Bitv::new(10u, false);
1045 act.set(0u, true);
1046 act.set(1u, true);
1047 act.set(2u, true);
1048 act.set(3u, true);
1049 act.set(4u, true);
1050 assert!((act.eq_vec([true, true, true, true, true, false, false, false, false, false])));
1051 // mixed
1052
1053 act = Bitv::new(10u, false);
1054 act.set(5u, true);
1055 act.set(6u, true);
1056 act.set(7u, true);
1057 act.set(8u, true);
1058 act.set(9u, true);
1059 assert!((act.eq_vec([false, false, false, false, false, true, true, true, true, true])));
1060 // mixed
1061
1062 act = Bitv::new(10u, false);
1063 act.set(0u, true);
1064 act.set(3u, true);
1065 act.set(6u, true);
1066 act.set(9u, true);
1067 assert!((act.eq_vec([true, false, false, true, false, false, true, false, false, true])));
1068 }
1069
1070 #[test]
1071 fn test_31_elements() {
1072 let mut act;
1073 // all 0
1074
1075 act = Bitv::new(31u, false);
1076 assert!(act.eq_vec(
1077 [false, false, false, false, false, false, false, false, false, false, false,
1078 false, false, false, false, false, false, false, false, false, false, false, false,
1079 false, false, false, false, false, false, false, false]));
1080 // all 1
1081
1082 act = Bitv::new(31u, true);
1083 assert!(act.eq_vec(
1084 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1085 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1086 true, true, true, true]));
1087 // mixed
1088
1089 act = Bitv::new(31u, false);
1090 act.set(0u, true);
1091 act.set(1u, true);
1092 act.set(2u, true);
1093 act.set(3u, true);
1094 act.set(4u, true);
1095 act.set(5u, true);
1096 act.set(6u, true);
1097 act.set(7u, true);
1098 assert!(act.eq_vec(
1099 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1100 false, false, false, false, false, false, false, false, false, false, false, false,
1101 false, false, false, false, false, false]));
1102 // mixed
1103
1104 act = Bitv::new(31u, false);
1105 act.set(16u, true);
1106 act.set(17u, true);
1107 act.set(18u, true);
1108 act.set(19u, true);
1109 act.set(20u, true);
1110 act.set(21u, true);
1111 act.set(22u, true);
1112 act.set(23u, true);
1113 assert!(act.eq_vec(
1114 [false, false, false, false, false, false, false, false, false, false, false,
1115 false, false, false, false, false, true, true, true, true, true, true, true, true,
1116 false, false, false, false, false, false, false]));
1117 // mixed
1118
1119 act = Bitv::new(31u, false);
1120 act.set(24u, true);
1121 act.set(25u, true);
1122 act.set(26u, true);
1123 act.set(27u, true);
1124 act.set(28u, true);
1125 act.set(29u, true);
1126 act.set(30u, true);
1127 assert!(act.eq_vec(
1128 [false, false, false, false, false, false, false, false, false, false, false,
1129 false, false, false, false, false, false, false, false, false, false, false, false,
1130 false, true, true, true, true, true, true, true]));
1131 // mixed
1132
1133 act = Bitv::new(31u, false);
1134 act.set(3u, true);
1135 act.set(17u, true);
1136 act.set(30u, true);
1137 assert!(act.eq_vec(
1138 [false, false, false, true, false, false, false, false, false, false, false, false,
1139 false, false, false, false, false, true, false, false, false, false, false, false,
1140 false, false, false, false, false, false, true]));
1141 }
1142
1143 #[test]
1144 fn test_32_elements() {
1145 let mut act;
1146 // all 0
1147
1148 act = Bitv::new(32u, false);
1149 assert!(act.eq_vec(
1150 [false, false, false, false, false, false, false, false, false, false, false,
1151 false, false, false, false, false, false, false, false, false, false, false, false,
1152 false, false, false, false, false, false, false, false, false]));
1153 // all 1
1154
1155 act = Bitv::new(32u, true);
1156 assert!(act.eq_vec(
1157 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1158 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1159 true, true, true, true, true]));
1160 // mixed
1161
1162 act = Bitv::new(32u, false);
1163 act.set(0u, true);
1164 act.set(1u, true);
1165 act.set(2u, true);
1166 act.set(3u, true);
1167 act.set(4u, true);
1168 act.set(5u, true);
1169 act.set(6u, true);
1170 act.set(7u, true);
1171 assert!(act.eq_vec(
1172 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1173 false, false, false, false, false, false, false, false, false, false, false, false,
1174 false, false, false, false, false, false, false]));
1175 // mixed
1176
1177 act = Bitv::new(32u, false);
1178 act.set(16u, true);
1179 act.set(17u, true);
1180 act.set(18u, true);
1181 act.set(19u, true);
1182 act.set(20u, true);
1183 act.set(21u, true);
1184 act.set(22u, true);
1185 act.set(23u, true);
1186 assert!(act.eq_vec(
1187 [false, false, false, false, false, false, false, false, false, false, false,
1188 false, false, false, false, false, true, true, true, true, true, true, true, true,
1189 false, false, false, false, false, false, false, false]));
1190 // mixed
1191
1192 act = Bitv::new(32u, false);
1193 act.set(24u, true);
1194 act.set(25u, true);
1195 act.set(26u, true);
1196 act.set(27u, true);
1197 act.set(28u, true);
1198 act.set(29u, true);
1199 act.set(30u, true);
1200 act.set(31u, true);
1201 assert!(act.eq_vec(
1202 [false, false, false, false, false, false, false, false, false, false, false,
1203 false, false, false, false, false, false, false, false, false, false, false, false,
1204 false, true, true, true, true, true, true, true, true]));
1205 // mixed
1206
1207 act = Bitv::new(32u, false);
1208 act.set(3u, true);
1209 act.set(17u, true);
1210 act.set(30u, true);
1211 act.set(31u, true);
1212 assert!(act.eq_vec(
1213 [false, false, false, true, false, false, false, false, false, false, false, false,
1214 false, false, false, false, false, true, false, false, false, false, false, false,
1215 false, false, false, false, false, false, true, true]));
1216 }
1217
1218 #[test]
1219 fn test_33_elements() {
1220 let mut act;
1221 // all 0
1222
1223 act = Bitv::new(33u, false);
1224 assert!(act.eq_vec(
1225 [false, false, false, false, false, false, false, false, false, false, false,
1226 false, false, false, false, false, false, false, false, false, false, false, false,
1227 false, false, false, false, false, false, false, false, false, false]));
1228 // all 1
1229
1230 act = Bitv::new(33u, true);
1231 assert!(act.eq_vec(
1232 [true, true, true, true, true, true, true, true, true, true, true, true, true,
1233 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
1234 true, true, true, true, true, true]));
1235 // mixed
1236
1237 act = Bitv::new(33u, false);
1238 act.set(0u, true);
1239 act.set(1u, true);
1240 act.set(2u, true);
1241 act.set(3u, true);
1242 act.set(4u, true);
1243 act.set(5u, true);
1244 act.set(6u, true);
1245 act.set(7u, true);
1246 assert!(act.eq_vec(
1247 [true, true, true, true, true, true, true, true, false, false, false, false, false,
1248 false, false, false, false, false, false, false, false, false, false, false, false,
1249 false, false, false, false, false, false, false, false]));
1250 // mixed
1251
1252 act = Bitv::new(33u, false);
1253 act.set(16u, true);
1254 act.set(17u, true);
1255 act.set(18u, true);
1256 act.set(19u, true);
1257 act.set(20u, true);
1258 act.set(21u, true);
1259 act.set(22u, true);
1260 act.set(23u, true);
1261 assert!(act.eq_vec(
1262 [false, false, false, false, false, false, false, false, false, false, false,
1263 false, false, false, false, false, true, true, true, true, true, true, true, true,
1264 false, false, false, false, false, false, false, false, false]));
1265 // mixed
1266
1267 act = Bitv::new(33u, false);
1268 act.set(24u, true);
1269 act.set(25u, true);
1270 act.set(26u, true);
1271 act.set(27u, true);
1272 act.set(28u, true);
1273 act.set(29u, true);
1274 act.set(30u, true);
1275 act.set(31u, true);
1276 assert!(act.eq_vec(
1277 [false, false, false, false, false, false, false, false, false, false, false,
1278 false, false, false, false, false, false, false, false, false, false, false, false,
1279 false, true, true, true, true, true, true, true, true, false]));
1280 // mixed
1281
1282 act = Bitv::new(33u, false);
1283 act.set(3u, true);
1284 act.set(17u, true);
1285 act.set(30u, true);
1286 act.set(31u, true);
1287 act.set(32u, true);
1288 assert!(act.eq_vec(
1289 [false, false, false, true, false, false, false, false, false, false, false, false,
1290 false, false, false, false, false, true, false, false, false, false, false, false,
1291 false, false, false, false, false, false, true, true, true]));
1292 }
1293
1294 #[test]
1295 fn test_equal_differing_sizes() {
1296 let v0 = Bitv::new(10u, false);
1297 let v1 = Bitv::new(11u, false);
1298 assert!(!v0.equal(&v1));
1299 }
1300
1301 #[test]
1302 fn test_equal_greatly_differing_sizes() {
1303 let v0 = Bitv::new(10u, false);
1304 let v1 = Bitv::new(110u, false);
1305 assert!(!v0.equal(&v1));
1306 }
1307
1308 #[test]
1309 fn test_equal_sneaky_small() {
1310 let mut a = bitv::Bitv::new(1, false);
1311 a.set(0, true);
1312
1313 let mut b = bitv::Bitv::new(1, true);
1314 b.set(0, true);
1315
1316 assert!(a.equal(&b));
1317 }
1318
1319 #[test]
1320 fn test_equal_sneaky_big() {
1321 let mut a = bitv::Bitv::new(100, false);
1322 for i in range(0u, 100) {
1323 a.set(i, true);
1324 }
1325
1326 let mut b = bitv::Bitv::new(100, true);
1327 for i in range(0u, 100) {
1328 b.set(i, true);
1329 }
1330
1331 assert!(a.equal(&b));
1332 }
1333
1334 #[test]
1335 fn test_from_bytes() {
1336 let bitv = from_bytes([0b10110110, 0b00000000, 0b11111111]);
1337 let str = "10110110".to_owned() + "00000000" + "11111111";
1338 assert_eq!(bitv.to_str(), str);
1339 }
1340
1341 #[test]
1342 fn test_to_bytes() {
1343 let mut bv = Bitv::new(3, true);
1344 bv.set(1, false);
1345 assert_eq!(bv.to_bytes(), vec!(0b10100000));
1346
1347 let mut bv = Bitv::new(9, false);
1348 bv.set(2, true);
1349 bv.set(8, true);
1350 assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
1351 }
1352
1353 #[test]
1354 fn test_from_bools() {
1355 assert!(from_bools([true, false, true, true]).to_str() ==
1356 "1011".to_owned());
1357 }
1358
1359 #[test]
1360 fn test_to_bools() {
1361 let bools = vec!(false, false, true, false, false, true, true, false);
1362 assert_eq!(from_bytes([0b00100110]).to_bools(), bools);
1363 }
1364
1365 #[test]
1366 fn test_bitv_iterator() {
1367 let bools = [true, false, true, true];
1368 let bitv = from_bools(bools);
1369
1370 for (act, &ex) in bitv.iter().zip(bools.iter()) {
1371 assert_eq!(ex, act);
1372 }
1373 }
1374
1375 #[test]
1376 fn test_bitv_set_iterator() {
1377 let bools = [true, false, true, true];
1378 let bitv = BitvSet::from_bitv(from_bools(bools));
1379
1380 let idxs: Vec<uint> = bitv.iter().collect();
1381 assert_eq!(idxs, vec!(0, 2, 3));
1382 }
1383
1384 #[test]
1385 fn test_bitv_set_frombitv_init() {
1386 let bools = [true, false];
1387 let lengths = [10, 64, 100];
1388 for &b in bools.iter() {
1389 for &l in lengths.iter() {
1390 let bitset = BitvSet::from_bitv(Bitv::new(l, b));
1391 assert_eq!(bitset.contains(&1u), b)
1392 assert_eq!(bitset.contains(&(l-1u)), b)
1393 assert!(!bitset.contains(&l))
1394 }
1395 }
1396 }
1397
1398 #[test]
1399 fn test_small_difference() {
1400 let mut b1 = Bitv::new(3, false);
1401 let mut b2 = Bitv::new(3, false);
1402 b1.set(0, true);
1403 b1.set(1, true);
1404 b2.set(1, true);
1405 b2.set(2, true);
1406 assert!(b1.difference(&b2));
1407 assert!(b1[0]);
1408 assert!(!b1[1]);
1409 assert!(!b1[2]);
1410 }
1411
1412 #[test]
1413 fn test_big_difference() {
1414 let mut b1 = Bitv::new(100, false);
1415 let mut b2 = Bitv::new(100, false);
1416 b1.set(0, true);
1417 b1.set(40, true);
1418 b2.set(40, true);
1419 b2.set(80, true);
1420 assert!(b1.difference(&b2));
1421 assert!(b1[0]);
1422 assert!(!b1[40]);
1423 assert!(!b1[80]);
1424 }
1425
1426 #[test]
1427 fn test_small_clear() {
1428 let mut b = Bitv::new(14, true);
1429 b.clear();
1430 b.ones(|i| {
1431 fail!("found 1 at {:?}", i)
1432 });
1433 }
1434
1435 #[test]
1436 fn test_big_clear() {
1437 let mut b = Bitv::new(140, true);
1438 b.clear();
1439 b.ones(|i| {
1440 fail!("found 1 at {:?}", i)
1441 });
1442 }
1443
1444 #[test]
1445 fn test_bitv_set_basic() {
1446 let mut b = BitvSet::new();
1447 assert!(b.insert(3));
1448 assert!(!b.insert(3));
1449 assert!(b.contains(&3));
1450 assert!(b.insert(400));
1451 assert!(!b.insert(400));
1452 assert!(b.contains(&400));
1453 assert_eq!(b.len(), 2);
1454 }
1455
1456 #[test]
1457 fn test_bitv_set_intersection() {
1458 let mut a = BitvSet::new();
1459 let mut b = BitvSet::new();
1460
1461 assert!(a.insert(11));
1462 assert!(a.insert(1));
1463 assert!(a.insert(3));
1464 assert!(a.insert(77));
1465 assert!(a.insert(103));
1466 assert!(a.insert(5));
1467
1468 assert!(b.insert(2));
1469 assert!(b.insert(11));
1470 assert!(b.insert(77));
1471 assert!(b.insert(5));
1472 assert!(b.insert(3));
1473
1474 let mut i = 0;
1475 let expected = [3, 5, 11, 77];
1476 a.intersection(&b, |x| {
1477 assert_eq!(*x, expected[i]);
1478 i += 1;
1479 true
1480 });
1481 assert_eq!(i, expected.len());
1482 }
1483
1484 #[test]
1485 fn test_bitv_set_difference() {
1486 let mut a = BitvSet::new();
1487 let mut b = BitvSet::new();
1488
1489 assert!(a.insert(1));
1490 assert!(a.insert(3));
1491 assert!(a.insert(5));
1492 assert!(a.insert(200));
1493 assert!(a.insert(500));
1494
1495 assert!(b.insert(3));
1496 assert!(b.insert(200));
1497
1498 let mut i = 0;
1499 let expected = [1, 5, 500];
1500 a.difference(&b, |x| {
1501 assert_eq!(*x, expected[i]);
1502 i += 1;
1503 true
1504 });
1505 assert_eq!(i, expected.len());
1506 }
1507
1508 #[test]
1509 fn test_bitv_set_symmetric_difference() {
1510 let mut a = BitvSet::new();
1511 let mut b = BitvSet::new();
1512
1513 assert!(a.insert(1));
1514 assert!(a.insert(3));
1515 assert!(a.insert(5));
1516 assert!(a.insert(9));
1517 assert!(a.insert(11));
1518
1519 assert!(b.insert(3));
1520 assert!(b.insert(9));
1521 assert!(b.insert(14));
1522 assert!(b.insert(220));
1523
1524 let mut i = 0;
1525 let expected = [1, 5, 11, 14, 220];
1526 a.symmetric_difference(&b, |x| {
1527 assert_eq!(*x, expected[i]);
1528 i += 1;
1529 true
1530 });
1531 assert_eq!(i, expected.len());
1532 }
1533
1534 #[test]
1535 fn test_bitv_set_union() {
1536 let mut a = BitvSet::new();
1537 let mut b = BitvSet::new();
1538 assert!(a.insert(1));
1539 assert!(a.insert(3));
1540 assert!(a.insert(5));
1541 assert!(a.insert(9));
1542 assert!(a.insert(11));
1543 assert!(a.insert(160));
1544 assert!(a.insert(19));
1545 assert!(a.insert(24));
1546
1547 assert!(b.insert(1));
1548 assert!(b.insert(5));
1549 assert!(b.insert(9));
1550 assert!(b.insert(13));
1551 assert!(b.insert(19));
1552
1553 let mut i = 0;
1554 let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160];
1555 a.union(&b, |x| {
1556 assert_eq!(*x, expected[i]);
1557 i += 1;
1558 true
1559 });
1560 assert_eq!(i, expected.len());
1561 }
1562
1563 #[test]
1564 fn test_bitv_remove() {
1565 let mut a = BitvSet::new();
1566
1567 assert!(a.insert(1));
1568 assert!(a.remove(&1));
1569
1570 assert!(a.insert(100));
1571 assert!(a.remove(&100));
1572
1573 assert!(a.insert(1000));
1574 assert!(a.remove(&1000));
1575 assert_eq!(a.capacity(), uint::BITS);
1576 }
1577
1578 #[test]
1579 fn test_bitv_clone() {
1580 let mut a = BitvSet::new();
1581
1582 assert!(a.insert(1));
1583 assert!(a.insert(100));
1584 assert!(a.insert(1000));
1585
1586 let mut b = a.clone();
1587
1588 assert!(a == b);
1589
1590 assert!(b.remove(&1));
1591 assert!(a.contains(&1));
1592
1593 assert!(a.remove(&1000));
1594 assert!(b.contains(&1000));
1595 }
1596
1597 #[test]
1598 fn test_small_bitv_tests() {
1599 let v = from_bytes([0]);
1600 assert!(!v.all());
1601 assert!(!v.any());
1602 assert!(v.none());
1603
1604 let v = from_bytes([0b00010100]);
1605 assert!(!v.all());
1606 assert!(v.any());
1607 assert!(!v.none());
1608
1609 let v = from_bytes([0xFF]);
1610 assert!(v.all());
1611 assert!(v.any());
1612 assert!(!v.none());
1613 }
1614
1615 #[test]
1616 fn test_big_bitv_tests() {
1617 let v = from_bytes([ // 88 bits
1618 0, 0, 0, 0,
1619 0, 0, 0, 0,
1620 0, 0, 0]);
1621 assert!(!v.all());
1622 assert!(!v.any());
1623 assert!(v.none());
1624
1625 let v = from_bytes([ // 88 bits
1626 0, 0, 0b00010100, 0,
1627 0, 0, 0, 0b00110100,
1628 0, 0, 0]);
1629 assert!(!v.all());
1630 assert!(v.any());
1631 assert!(!v.none());
1632
1633 let v = from_bytes([ // 88 bits
1634 0xFF, 0xFF, 0xFF, 0xFF,
1635 0xFF, 0xFF, 0xFF, 0xFF,
1636 0xFF, 0xFF, 0xFF]);
1637 assert!(v.all());
1638 assert!(v.any());
1639 assert!(!v.none());
1640 }
1641
1642 fn rng() -> rand::IsaacRng {
1643 let seed = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
1644 rand::SeedableRng::from_seed(seed)
1645 }
1646
1647 #[bench]
1648 fn bench_uint_small(b: &mut Bencher) {
1649 let mut r = rng();
1650 let mut bitv = 0 as uint;
1651 b.iter(|| {
1652 bitv |= 1 << ((r.next_u32() as uint) % uint::BITS);
1653 &bitv
1654 })
1655 }
1656
1657 #[bench]
1658 fn bench_small_bitv_small(b: &mut Bencher) {
1659 let mut r = rng();
1660 let mut bitv = SmallBitv::new(uint::BITS);
1661 b.iter(|| {
1662 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1663 &bitv
1664 })
1665 }
1666
1667 #[bench]
1668 fn bench_big_bitv_small(b: &mut Bencher) {
1669 let mut r = rng();
1670 let mut bitv = BigBitv::new(vec!(0));
1671 b.iter(|| {
1672 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1673 &bitv
1674 })
1675 }
1676
1677 #[bench]
1678 fn bench_big_bitv_big(b: &mut Bencher) {
1679 let mut r = rng();
1680 let mut storage = vec!();
1681 storage.grow(BENCH_BITS / uint::BITS, &0u);
1682 let mut bitv = BigBitv::new(storage);
1683 b.iter(|| {
1684 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1685 &bitv
1686 })
1687 }
1688
1689 #[bench]
1690 fn bench_bitv_big(b: &mut Bencher) {
1691 let mut r = rng();
1692 let mut bitv = Bitv::new(BENCH_BITS, false);
1693 b.iter(|| {
1694 bitv.set((r.next_u32() as uint) % BENCH_BITS, true);
1695 &bitv
1696 })
1697 }
1698
1699 #[bench]
1700 fn bench_bitv_small(b: &mut Bencher) {
1701 let mut r = rng();
1702 let mut bitv = Bitv::new(uint::BITS, false);
1703 b.iter(|| {
1704 bitv.set((r.next_u32() as uint) % uint::BITS, true);
1705 &bitv
1706 })
1707 }
1708
1709 #[bench]
1710 fn bench_bitv_set_small(b: &mut Bencher) {
1711 let mut r = rng();
1712 let mut bitv = BitvSet::new();
1713 b.iter(|| {
1714 bitv.insert((r.next_u32() as uint) % uint::BITS);
1715 &bitv
1716 })
1717 }
1718
1719 #[bench]
1720 fn bench_bitv_set_big(b: &mut Bencher) {
1721 let mut r = rng();
1722 let mut bitv = BitvSet::new();
1723 b.iter(|| {
1724 bitv.insert((r.next_u32() as uint) % BENCH_BITS);
1725 &bitv
1726 })
1727 }
1728
1729 #[bench]
1730 fn bench_bitv_big_union(b: &mut Bencher) {
1731 let mut b1 = Bitv::new(BENCH_BITS, false);
1732 let b2 = Bitv::new(BENCH_BITS, false);
1733 b.iter(|| {
1734 b1.union(&b2);
1735 })
1736 }
1737
1738 #[bench]
1739 fn bench_btv_small_iter(b: &mut Bencher) {
1740 let bitv = Bitv::new(uint::BITS, false);
1741 b.iter(|| {
1742 let mut _sum = 0;
1743 for pres in bitv.iter() {
1744 _sum += pres as uint;
1745 }
1746 })
1747 }
1748
1749 #[bench]
1750 fn bench_bitv_big_iter(b: &mut Bencher) {
1751 let bitv = Bitv::new(BENCH_BITS, false);
1752 b.iter(|| {
1753 let mut _sum = 0;
1754 for pres in bitv.iter() {
1755 _sum += pres as uint;
1756 }
1757 })
1758 }
1759
1760 #[bench]
1761 fn bench_bitvset_iter(b: &mut Bencher) {
1762 let bitv = BitvSet::from_bitv(from_fn(BENCH_BITS,
1763 |idx| {idx % 3 == 0}));
1764 b.iter(|| {
1765 let mut _sum = 0;
1766 for idx in bitv.iter() {
1767 _sum += idx;
1768 }
1769 })
1770 }
1771 }
libcollections/bitv.rs:254:19-254:19 -struct- definition:
pub struct Bitv {
/// Internal representation of the bit vector (small or large)
rep: BitvVariant,
references:- 24253: /// ```
255: pub struct Bitv {
--
731: let BitvSet{bitv, ..} = self;
732: return Bitv{ nbits:cap, rep: Big(bitv) };
733: }
libcollections/bitv.rs:122:10-122:10 -fn- definition:
fn big_mask(nbits: uint, elem: uint) -> uint {
let rmd = nbits % uint::BITS;
let nelems = nbits/uint::BITS + if rmd == 0 {0} else {1};
references:- 2212: for (i, elt) in b.storage.iter().enumerate() {
213: let mask = big_mask(nbits, i);
214: if mask & *self.storage.get(i) != mask & *elt {
libcollections/bitv.rs:737:8-737:8 -fn- definition:
fn nbits(mut w: uint) -> uint {
let mut bits = 0;
for _ in range(0u, uint::BITS) {
references:- 2754: *self.bitv.storage.get_mut(i) = new;
755: self.size += nbits(new) - nbits(old);
756: }
libcollections/bitv.rs:693:19-693:19 -struct- definition:
pub struct BitvSet {
size: uint,
// In theory this is a `Bitv` instead of always a `BigBitv`, but knowing that
references:- 34libcollections/bitv.rs:602:4-602:4 -fn- definition:
*/
pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
let mut bitv = Bitv::new(len, false);
references:- 2584: pub fn from_bytes(bytes: &[u8]) -> Bitv {
585: from_fn(bytes.len() * 8, |i| {
586: let b = bytes[i / 8] as uint;
--
595: pub fn from_bools(bools: &[bool]) -> Bitv {
596: from_fn(bools.len(), |i| bools[i])
597: }
libcollections/bitv.rs:113:19-113:19 -struct- definition:
struct BigBitv {
storage: Vec<uint>
}
references:- 16719: Small(SmallBitv{bits}) =>
720: BitvSet{ size: size, bitv: BigBitv{ storage: vec!(bits) } },
721: }
libcollections/bitv.rs:632:28-632:28 -struct- definition:
/// An iterator for `Bitv`.
pub struct Bits<'a> {
bitv: &'a Bitv,
references:- 7465: pub fn iter<'a>(&'a self) -> Bits<'a> {
466: Bits {bitv: self, next_idx: 0, end_idx: self.nbits}
467: }
--
657: impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
658: #[inline]
--
669: impl<'a> ExactSize<bool> for Bits<'a> {}
671: impl<'a> RandomAccessIterator<bool> for Bits<'a> {
672: #[inline]
libcollections/bitv.rs:957:1-957:1 -struct- definition:
pub struct BitPositions<'a> {
set: &'a BitvSet,
next_idx: uint
references:- 3963: impl<'a> Iterator<uint> for BitPositions<'a> {
964: #[inline]
libcollections/bitv.rs:29:10-29:10 -fn- definition:
fn small_mask(nbits: uint) -> uint {
(1 << nbits) - 1
}
references:- 4100: pub fn all(&self, nbits: uint) -> bool {
101: small_mask(nbits) & !self.bits == 0
102: }
--
105: pub fn none(&self, nbits: uint) -> bool {
106: small_mask(nbits) & self.bits == 0
107: }
libcollections/bitv.rs:617:10-617:10 -fn- definition:
fn iterate_bits(base: uint, bits: uint, f: |uint| -> bool) -> bool {
if bits == 0 {
return true;
references:- 7805: pub fn intersection(&self, other: &BitvSet, f: |&uint| -> bool) -> bool {
806: self.commons(other).advance(|(i, w1, w2)| iterate_bits(i, w1 & w2, |b| f(&b)))
807: }
--
810: for (i, w1, w2) in self.commons(other) {
811: if !iterate_bits(i, w1 | w2, |b| f(&b)) {
812: return false
--
814: };
815: self.outliers(other).advance(|(_, i, w)| iterate_bits(i, w, |b| f(&b)))
816: }
libcollections/bitv.rs:261:1-261:1 -fn- definition:
fn die() -> ! {
fail!("Tried to do operation on bit vectors with different sizes");
}
references:- 3269: if self.nbits != other.nbits {
270: die();
271: }
--
279: },
280: Big(_) => die()
281: },
282: Big(ref mut s) => match other.rep {
283: Small(_) => die(),
284: Big(ref s1) => match op {
libcollections/bitv.rs:22:19-22:19 -struct- definition:
struct SmallBitv {
/// only the lowest nbits of this value are used. the rest is undefined.
bits: uint
references:- 1435: pub fn new(bits: uint) -> SmallBitv {
36: SmallBitv {bits: bits}
37: }
--
67: #[inline]
68: pub fn difference(&mut self, s: &SmallBitv, nbits: uint) -> bool {
69: self.bits_op(s.bits, nbits, |u1, u2| u1 & !u2)
--
87: #[inline]
88: pub fn equals(&self, b: &SmallBitv, nbits: uint) -> bool {
89: let mask = small_mask(nbits);
--
718: Big(b) => BitvSet{ size: size, bitv: b },
719: Small(SmallBitv{bits}) =>
720: BitvSet{ size: size, bitv: BigBitv{ storage: vec!(bits) } },
libcollections/bitv.rs:509:8-509:8 -fn- definition:
fn bit (bitv: &Bitv, byte: uint, bit: uint) -> u8 {
let offset = byte * 8 + bit;
if offset >= bitv.nbits {
references:- 8524: bit(self, i, 3) |
525: bit(self, i, 4) |
526: bit(self, i, 5) |
527: bit(self, i, 6) |
528: bit(self, i, 7)
529: )
libcollections/bitv.rs:222:19-222:19 -enum- definition:
enum BitvVariant { Big(BigBitv), Small(SmallBitv) }
enum Op {Union, Intersect, Assign, Difference}
/// The bitvector type
references:- 3256: /// Internal representation of the bit vector (small or large)
257: rep: BitvVariant,
258: /// The number of valid bits in the internal representation