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 // FIXME(Gankro): BitVec and BitSet are very tightly coupled. Ideally (for
12 // maintenance), they should be in separate files/modules, with BitSet only
13 // using BitVec's public API. This will be hard for performance though, because
14 // `BitVec` will not want to leak its internal representation while its internal
15 // representation as `u32`s must be assumed for best performance.
16
17 // (1) Be careful, most things can overflow here because the amount of bits in
18 // memory can overflow `usize`.
19 // (2) Make sure that the underlying vector has no excess length:
20 // E. g. `nbits == 16`, `storage.len() == 2` would be excess length,
21 // because the last word isn't used at all. This is important because some
22 // methods rely on it (for *CORRECTNESS*).
23 // (3) Make sure that the unused bits in the last word are zeroed out, again
24 // other methods rely on it for *CORRECTNESS*.
25 // (4) `BitSet` is tightly coupled with `BitVec`, so any changes you make in
26 // `BitVec` will need to be reflected in `BitSet`.
27
28 //! Collections implemented with bit vectors.
29 //!
30 //! # Examples
31 //!
32 //! This is a simple example of the [Sieve of Eratosthenes][sieve]
33 //! which calculates prime numbers up to a given limit.
34 //!
35 //! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
36 //!
37 //! ```
38 //! use bit_vec::BitVec;
39 //!
40 //! let max_prime = 10000;
41 //!
42 //! // Store the primes as a BitVec
43 //! let primes = {
44 //! // Assume all numbers are prime to begin, and then we
45 //! // cross off non-primes progressively
46 //! let mut bv = BitVec::from_elem(max_prime, true);
47 //!
48 //! // Neither 0 nor 1 are prime
49 //! bv.set(0, false);
50 //! bv.set(1, false);
51 //!
52 //! for i in 2.. 1 + (max_prime as f64).sqrt() as usize {
53 //! // if i is a prime
54 //! if bv[i] {
55 //! // Mark all multiples of i as non-prime (any multiples below i * i
56 //! // will have been marked as non-prime previously)
57 //! for j in i.. {
58 //! if i * j >= max_prime {
59 //! break;
60 //! }
61 //! bv.set(i * j, false)
62 //! }
63 //! }
64 //! }
65 //! bv
66 //! };
67 //!
68 //! // Simple primality tests below our max bound
69 //! let print_primes = 20;
70 //! print!("The primes below {} are: ", print_primes);
71 //! for x in 0..print_primes {
72 //! if primes.get(x).unwrap_or(false) {
73 //! print!("{} ", x);
74 //! }
75 //! }
76 //! println!();
77 //!
78 //! let num_primes = primes.iter().filter(|x| *x).count();
79 //! println!("There are {} primes below {}", num_primes, max_prime);
80 //! assert_eq!(num_primes, 1_229);
81 //! ```
82
83 #![no_std]
84
85 #[cfg(any(test, feature = "std"))]
86 #[macro_use]
87 extern crate std;
88 #[cfg(feature="std")]
89 use std::vec::Vec;
90
91 #[cfg(feature="serde")]
92 extern crate serde;
93 #[cfg(feature="serde")]
94 use serde::{Serialize, Deserialize};
95
96 #[cfg(not(feature="std"))]
97 #[macro_use]
98 extern crate alloc;
99 #[cfg(not(feature="std"))]
100 use alloc::vec::Vec;
101
102 use core::cmp::Ordering;
103 use core::cmp;
104 use core::fmt;
105 use core::hash;
106 use core::mem;
107 use core::iter::FromIterator;
108 use core::slice;
109 use core::{u8, usize};
110 use core::iter::repeat;
111 use core::ops::*;
112
113 type MutBlocks<'a, B> = slice::IterMut<'a, B>;
114
115 /// Abstracts over a pile of bits (basically unsigned primitives)
116 pub trait BitBlock:
117 Copy +
118 Add<Self, Output=Self> +
119 Sub<Self, Output=Self> +
120 Shl<usize, Output=Self> +
121 Shr<usize, Output=Self> +
122 Not<Output=Self> +
123 BitAnd<Self, Output=Self> +
124 BitOr<Self, Output=Self> +
125 BitXor<Self, Output=Self> +
126 Rem<Self, Output=Self> +
127 Eq +
128 Ord +
129 hash::Hash
130 {
131 /// How many bits it has
bits() -> usize132 fn bits() -> usize;
133 /// How many bytes it has
134 #[inline]
bytes() -> usize135 fn bytes() -> usize { Self::bits() / 8 }
136 /// Convert a byte into this type (lowest-order bits set)
from_byte(byte: u8) -> Self137 fn from_byte(byte: u8) -> Self;
138 /// Count the number of 1's in the bitwise repr
count_ones(self) -> usize139 fn count_ones(self) -> usize;
140 /// Get `0`
zero() -> Self141 fn zero() -> Self;
142 /// Get `1`
one() -> Self143 fn one() -> Self;
144 }
145
146 macro_rules! bit_block_impl {
147 ($(($t: ident, $size: expr)),*) => ($(
148 impl BitBlock for $t {
149 #[inline]
150 fn bits() -> usize { $size }
151 #[inline]
152 fn from_byte(byte: u8) -> Self { $t::from(byte) }
153 #[inline]
154 fn count_ones(self) -> usize { self.count_ones() as usize }
155 #[inline]
156 fn one() -> Self { 1 }
157 #[inline]
158 fn zero() -> Self { 0 }
159 }
160 )*)
161 }
162
163 bit_block_impl!{
164 (u8, 8),
165 (u16, 16),
166 (u32, 32),
167 (u64, 64),
168 (usize, core::mem::size_of::<usize>() * 8)
169 }
170
reverse_bits(byte: u8) -> u8171 fn reverse_bits(byte: u8) -> u8 {
172 let mut result = 0;
173 for i in 0..u8::bits() {
174 result |= ((byte >> i) & 1) << (u8::bits() - 1 - i);
175 }
176 result
177 }
178
179 static TRUE: bool = true;
180 static FALSE: bool = false;
181
182 /// The bitvector type.
183 ///
184 /// # Examples
185 ///
186 /// ```
187 /// use bit_vec::BitVec;
188 ///
189 /// let mut bv = BitVec::from_elem(10, false);
190 ///
191 /// // insert all primes less than 10
192 /// bv.set(2, true);
193 /// bv.set(3, true);
194 /// bv.set(5, true);
195 /// bv.set(7, true);
196 /// println!("{:?}", bv);
197 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
198 ///
199 /// // flip all values in bitvector, producing non-primes less than 10
200 /// bv.negate();
201 /// println!("{:?}", bv);
202 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
203 ///
204 /// // reset bitvector to empty
205 /// bv.clear();
206 /// println!("{:?}", bv);
207 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
208 /// ```
209 #[cfg_attr(feature="serde", derive(Serialize, Deserialize))]
210 pub struct BitVec<B=u32> {
211 /// Internal representation of the bit vector
212 storage: Vec<B>,
213 /// The number of valid bits in the internal representation
214 nbits: usize
215 }
216
217 // FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
218 impl<B: BitBlock> Index<usize> for BitVec<B> {
219 type Output = bool;
220
221 #[inline]
index(&self, i: usize) -> &bool222 fn index(&self, i: usize) -> &bool {
223 if self.get(i).expect("index out of bounds") {
224 &TRUE
225 } else {
226 &FALSE
227 }
228 }
229 }
230
231 /// Computes how many blocks are needed to store that many bits
blocks_for_bits<B: BitBlock>(bits: usize) -> usize232 fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
233 // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
234 // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
235 // one too many. So we need to check if that's the case. We can do that by computing if
236 // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
237 // superior modulo operator on a power of two to this.
238 //
239 // Note that we can technically avoid this branch with the expression
240 // `(nbits + U32_BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
241 if bits % B::bits() == 0 {
242 bits / B::bits()
243 } else {
244 bits / B::bits() + 1
245 }
246 }
247
248 /// Computes the bitmask for the final word of the vector
mask_for_bits<B: BitBlock>(bits: usize) -> B249 fn mask_for_bits<B: BitBlock>(bits: usize) -> B {
250 // Note especially that a perfect multiple of U32_BITS should mask all 1s.
251 (!B::zero()) >> ((B::bits() - bits % B::bits()) % B::bits())
252 }
253
254 type B = u32;
255
256 impl BitVec<u32> {
257
258 /// Creates an empty `BitVec`.
259 ///
260 /// # Examples
261 ///
262 /// ```
263 /// use bit_vec::BitVec;
264 /// let mut bv = BitVec::new();
265 /// ```
266 #[inline]
new() -> Self267 pub fn new() -> Self {
268 Default::default()
269 }
270
271 /// Creates a `BitVec` that holds `nbits` elements, setting each element
272 /// to `bit`.
273 ///
274 /// # Examples
275 ///
276 /// ```
277 /// use bit_vec::BitVec;
278 ///
279 /// let mut bv = BitVec::from_elem(10, false);
280 /// assert_eq!(bv.len(), 10);
281 /// for x in bv.iter() {
282 /// assert_eq!(x, false);
283 /// }
284 /// ```
285 #[inline]
from_elem(nbits: usize, bit: bool) -> Self286 pub fn from_elem(nbits: usize, bit: bool) -> Self {
287 let nblocks = blocks_for_bits::<B>(nbits);
288 let mut bit_vec = BitVec {
289 storage: vec![if bit { !B::zero() } else { B::zero() }; nblocks],
290 nbits,
291 };
292 bit_vec.fix_last_block();
293 bit_vec
294 }
295
296 /// Constructs a new, empty `BitVec` with the specified capacity.
297 ///
298 /// The bitvector will be able to hold at least `capacity` bits without
299 /// reallocating. If `capacity` is 0, it will not allocate.
300 ///
301 /// It is important to note that this function does not specify the
302 /// *length* of the returned bitvector, but only the *capacity*.
303 #[inline]
with_capacity(nbits: usize) -> Self304 pub fn with_capacity(nbits: usize) -> Self {
305 BitVec {
306 storage: Vec::with_capacity(blocks_for_bits::<B>(nbits)),
307 nbits: 0,
308 }
309 }
310
311 /// Transforms a byte-vector into a `BitVec`. Each byte becomes eight bits,
312 /// with the most significant bits of each byte coming first. Each
313 /// bit becomes `true` if equal to 1 or `false` if equal to 0.
314 ///
315 /// # Examples
316 ///
317 /// ```
318 /// use bit_vec::BitVec;
319 ///
320 /// let bv = BitVec::from_bytes(&[0b10100000, 0b00010010]);
321 /// assert!(bv.eq_vec(&[true, false, true, false,
322 /// false, false, false, false,
323 /// false, false, false, true,
324 /// false, false, true, false]));
325 /// ```
from_bytes(bytes: &[u8]) -> Self326 pub fn from_bytes(bytes: &[u8]) -> Self {
327 let len = bytes.len().checked_mul(u8::bits()).expect("capacity overflow");
328 let mut bit_vec = BitVec::with_capacity(len);
329 let complete_words = bytes.len() / B::bytes();
330 let extra_bytes = bytes.len() % B::bytes();
331
332 bit_vec.nbits = len;
333
334 for i in 0..complete_words {
335 let mut accumulator = B::zero();
336 for idx in 0..B::bytes() {
337 accumulator |=
338 B::from_byte(reverse_bits(bytes[i * B::bytes() + idx])) << (idx * 8)
339 }
340 bit_vec.storage.push(accumulator);
341 }
342
343 if extra_bytes > 0 {
344 let mut last_word = B::zero();
345 for (i, &byte) in bytes[complete_words * B::bytes()..].iter().enumerate() {
346 last_word |=
347 B::from_byte(reverse_bits(byte)) << (i * 8);
348 }
349 bit_vec.storage.push(last_word);
350 }
351
352 bit_vec
353 }
354
355 /// Creates a `BitVec` of the specified length where the value at each index
356 /// is `f(index)`.
357 ///
358 /// # Examples
359 ///
360 /// ```
361 /// use bit_vec::BitVec;
362 ///
363 /// let bv = BitVec::from_fn(5, |i| { i % 2 == 0 });
364 /// assert!(bv.eq_vec(&[true, false, true, false, true]));
365 /// ```
366 #[inline]
from_fn<F>(len: usize, mut f: F) -> Self where F: FnMut(usize) -> bool367 pub fn from_fn<F>(len: usize, mut f: F) -> Self
368 where F: FnMut(usize) -> bool
369 {
370 let mut bit_vec = BitVec::from_elem(len, false);
371 for i in 0..len {
372 bit_vec.set(i, f(i));
373 }
374 bit_vec
375 }
376 }
377
378 impl<B: BitBlock> BitVec<B> {
379 /// Applies the given operation to the blocks of self and other, and sets
380 /// self to be the result. This relies on the caller not to corrupt the
381 /// last word.
382 #[inline]
process<F>(&mut self, other: &BitVec<B>, mut op: F) -> bool where F: FnMut(B, B) -> B383 fn process<F>(&mut self, other: &BitVec<B>, mut op: F) -> bool
384 where F: FnMut(B, B) -> B {
385 assert_eq!(self.len(), other.len());
386 debug_assert_eq!(self.storage.len(), other.storage.len());
387 let mut changed_bits = B::zero();
388 for (a, b) in self.blocks_mut().zip(other.blocks()) {
389 let w = op(*a, b);
390 changed_bits = changed_bits | (*a ^ w);
391 *a = w;
392 }
393 changed_bits != B::zero()
394 }
395
396 /// Iterator over mutable refs to the underlying blocks of data.
397 #[inline]
blocks_mut(&mut self) -> MutBlocks<B>398 fn blocks_mut(&mut self) -> MutBlocks<B> {
399 // (2)
400 self.storage.iter_mut()
401 }
402
403 /// Iterator over the underlying blocks of data
404 #[inline]
blocks(&self) -> Blocks<B>405 pub fn blocks(&self) -> Blocks<B> {
406 // (2)
407 Blocks{iter: self.storage.iter()}
408 }
409
410 /// Exposes the raw block storage of this BitVec
411 ///
412 /// Only really intended for BitSet.
413 #[inline]
storage(&self) -> &[B]414 pub fn storage(&self) -> &[B] {
415 &self.storage
416 }
417
418 /// Exposes the raw block storage of this BitVec
419 ///
420 /// Can probably cause unsafety. Only really intended for BitSet.
421 #[inline]
storage_mut(&mut self) -> &mut Vec<B>422 pub unsafe fn storage_mut(&mut self) -> &mut Vec<B> {
423 &mut self.storage
424 }
425
426 /// Helper for procedures involving spare space in the last block.
427 #[inline]
last_block_with_mask(&self) -> Option<(B, B)>428 fn last_block_with_mask(&self) -> Option<(B, B)> {
429 let extra_bits = self.len() % B::bits();
430 if extra_bits > 0 {
431 let mask = (B::one() << extra_bits) - B::one();
432 let storage_len = self.storage.len();
433 Some((self.storage[storage_len - 1], mask))
434 } else {
435 None
436 }
437 }
438
439 /// Helper for procedures involving spare space in the last block.
440 #[inline]
last_block_mut_with_mask(&mut self) -> Option<(&mut B, B)>441 fn last_block_mut_with_mask(&mut self) -> Option<(&mut B, B)> {
442 let extra_bits = self.len() % B::bits();
443 if extra_bits > 0 {
444 let mask = (B::one() << extra_bits) - B::one();
445 let storage_len = self.storage.len();
446 Some((&mut self.storage[storage_len - 1], mask))
447 } else {
448 None
449 }
450 }
451
452 /// An operation might screw up the unused bits in the last block of the
453 /// `BitVec`. As per (3), it's assumed to be all 0s. This method fixes it up.
fix_last_block(&mut self)454 fn fix_last_block(&mut self) {
455 if let Some((last_block, used_bits)) = self.last_block_mut_with_mask() {
456 *last_block = *last_block & used_bits;
457 }
458 }
459
460 /// Operations such as change detection for xnor, nor and nand are easiest
461 /// to implement when unused bits are all set to 1s.
fix_last_block_with_ones(&mut self)462 fn fix_last_block_with_ones(&mut self) {
463 if let Some((last_block, used_bits)) = self.last_block_mut_with_mask() {
464 *last_block = *last_block | !used_bits;
465 }
466 }
467
468 /// Check whether last block's invariant is fine.
is_last_block_fixed(&self) -> bool469 fn is_last_block_fixed(&self) -> bool {
470 if let Some((last_block, used_bits)) = self.last_block_with_mask() {
471 last_block & !used_bits == B::zero()
472 } else {
473 true
474 }
475 }
476
477 /// Ensure the invariant for the last block.
478 ///
479 /// An operation might screw up the unused bits in the last block of the
480 /// `BitVec`.
481 ///
482 /// This method fails in case the last block is not fixed. The check
483 /// is skipped outside testing.
484 #[inline]
ensure_invariant(&self)485 fn ensure_invariant(&self) {
486 if cfg!(test) {
487 debug_assert!(self.is_last_block_fixed());
488 }
489 }
490
491 /// Retrieves the value at index `i`, or `None` if the index is out of bounds.
492 ///
493 /// # Examples
494 ///
495 /// ```
496 /// use bit_vec::BitVec;
497 ///
498 /// let bv = BitVec::from_bytes(&[0b01100000]);
499 /// assert_eq!(bv.get(0), Some(false));
500 /// assert_eq!(bv.get(1), Some(true));
501 /// assert_eq!(bv.get(100), None);
502 ///
503 /// // Can also use array indexing
504 /// assert_eq!(bv[1], true);
505 /// ```
506 #[inline]
get(&self, i: usize) -> Option<bool>507 pub fn get(&self, i: usize) -> Option<bool> {
508 self.ensure_invariant();
509 if i >= self.nbits {
510 return None;
511 }
512 let w = i / B::bits();
513 let b = i % B::bits();
514 self.storage.get(w).map(|&block|
515 (block & (B::one() << b)) != B::zero()
516 )
517 }
518
519 /// Sets the value of a bit at an index `i`.
520 ///
521 /// # Panics
522 ///
523 /// Panics if `i` is out of bounds.
524 ///
525 /// # Examples
526 ///
527 /// ```
528 /// use bit_vec::BitVec;
529 ///
530 /// let mut bv = BitVec::from_elem(5, false);
531 /// bv.set(3, true);
532 /// assert_eq!(bv[3], true);
533 /// ```
534 #[inline]
set(&mut self, i: usize, x: bool)535 pub fn set(&mut self, i: usize, x: bool) {
536 self.ensure_invariant();
537 assert!(i < self.nbits, "index out of bounds: {:?} >= {:?}", i, self.nbits);
538 let w = i / B::bits();
539 let b = i % B::bits();
540 let flag = B::one() << b;
541 let val = if x { self.storage[w] | flag }
542 else { self.storage[w] & !flag };
543 self.storage[w] = val;
544 }
545
546 /// Sets all bits to 1.
547 ///
548 /// # Examples
549 ///
550 /// ```
551 /// use bit_vec::BitVec;
552 ///
553 /// let before = 0b01100000;
554 /// let after = 0b11111111;
555 ///
556 /// let mut bv = BitVec::from_bytes(&[before]);
557 /// bv.set_all();
558 /// assert_eq!(bv, BitVec::from_bytes(&[after]));
559 /// ```
560 #[inline]
set_all(&mut self)561 pub fn set_all(&mut self) {
562 self.ensure_invariant();
563 for w in &mut self.storage { *w = !B::zero(); }
564 self.fix_last_block();
565 }
566
567 /// Flips all bits.
568 ///
569 /// # Examples
570 ///
571 /// ```
572 /// use bit_vec::BitVec;
573 ///
574 /// let before = 0b01100000;
575 /// let after = 0b10011111;
576 ///
577 /// let mut bv = BitVec::from_bytes(&[before]);
578 /// bv.negate();
579 /// assert_eq!(bv, BitVec::from_bytes(&[after]));
580 /// ```
581 #[inline]
negate(&mut self)582 pub fn negate(&mut self) {
583 self.ensure_invariant();
584 for w in &mut self.storage { *w = !*w; }
585 self.fix_last_block();
586 }
587
588 /// Calculates the union of two bitvectors. This acts like the bitwise `or`
589 /// function.
590 ///
591 /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
592 /// the same length. Returns `true` if `self` changed.
593 ///
594 /// # Panics
595 ///
596 /// Panics if the bitvectors are of different lengths.
597 ///
598 /// # Examples
599 ///
600 /// ```
601 /// use bit_vec::BitVec;
602 ///
603 /// let a = 0b01100100;
604 /// let b = 0b01011010;
605 /// let res = 0b01111110;
606 ///
607 /// let mut a = BitVec::from_bytes(&[a]);
608 /// let b = BitVec::from_bytes(&[b]);
609 ///
610 /// assert!(a.union(&b));
611 /// assert_eq!(a, BitVec::from_bytes(&[res]));
612 /// ```
613 #[deprecated(
614 since = "0.7.0",
615 note = "Please use the 'or' function instead"
616 )]
617 #[inline]
union(&mut self, other: &Self) -> bool618 pub fn union(&mut self, other: &Self) -> bool {
619 self.or(other)
620 }
621
622 /// Calculates the intersection of two bitvectors. This acts like the
623 /// bitwise `and` function.
624 ///
625 /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
626 /// must be the same length. Returns `true` if `self` changed.
627 ///
628 /// # Panics
629 ///
630 /// Panics if the bitvectors are of different lengths.
631 ///
632 /// # Examples
633 ///
634 /// ```
635 /// use bit_vec::BitVec;
636 ///
637 /// let a = 0b01100100;
638 /// let b = 0b01011010;
639 /// let res = 0b01000000;
640 ///
641 /// let mut a = BitVec::from_bytes(&[a]);
642 /// let b = BitVec::from_bytes(&[b]);
643 ///
644 /// assert!(a.intersect(&b));
645 /// assert_eq!(a, BitVec::from_bytes(&[res]));
646 /// ```
647 #[deprecated(
648 since = "0.7.0",
649 note = "Please use the 'and' function instead"
650 )]
651 #[inline]
intersect(&mut self, other: &Self) -> bool652 pub fn intersect(&mut self, other: &Self) -> bool {
653 self.and(other)
654 }
655
656 /// Calculates the bitwise `or` of two bitvectors.
657 ///
658 /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
659 /// the same length. Returns `true` if `self` changed.
660 ///
661 /// # Panics
662 ///
663 /// Panics if the bitvectors are of different lengths.
664 ///
665 /// # Examples
666 ///
667 /// ```
668 /// use bit_vec::BitVec;
669 ///
670 /// let a = 0b01100100;
671 /// let b = 0b01011010;
672 /// let res = 0b01111110;
673 ///
674 /// let mut a = BitVec::from_bytes(&[a]);
675 /// let b = BitVec::from_bytes(&[b]);
676 ///
677 /// assert!(a.or(&b));
678 /// assert_eq!(a, BitVec::from_bytes(&[res]));
679 /// ```
680 #[inline]
or(&mut self, other: &Self) -> bool681 pub fn or(&mut self, other: &Self) -> bool {
682 self.ensure_invariant();
683 debug_assert!(other.is_last_block_fixed());
684 self.process(other, |w1, w2| (w1 | w2))
685 }
686
687 /// Calculates the bitwise `and` of two bitvectors.
688 ///
689 /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
690 /// must be the same length. Returns `true` if `self` changed.
691 ///
692 /// # Panics
693 ///
694 /// Panics if the bitvectors are of different lengths.
695 ///
696 /// # Examples
697 ///
698 /// ```
699 /// use bit_vec::BitVec;
700 ///
701 /// let a = 0b01100100;
702 /// let b = 0b01011010;
703 /// let res = 0b01000000;
704 ///
705 /// let mut a = BitVec::from_bytes(&[a]);
706 /// let b = BitVec::from_bytes(&[b]);
707 ///
708 /// assert!(a.and(&b));
709 /// assert_eq!(a, BitVec::from_bytes(&[res]));
710 /// ```
711 #[inline]
and(&mut self, other: &Self) -> bool712 pub fn and(&mut self, other: &Self) -> bool {
713 self.ensure_invariant();
714 debug_assert!(other.is_last_block_fixed());
715 self.process(other, |w1, w2| (w1 & w2))
716 }
717
718 /// Calculates the difference between two bitvectors.
719 ///
720 /// Sets each element of `self` to the value of that element minus the
721 /// element of `other` at the same index. Both bitvectors must be the same
722 /// length. Returns `true` if `self` changed.
723 ///
724 /// # Panics
725 ///
726 /// Panics if the bitvectors are of different length.
727 ///
728 /// # Examples
729 ///
730 /// ```
731 /// use bit_vec::BitVec;
732 ///
733 /// let a = 0b01100100;
734 /// let b = 0b01011010;
735 /// let a_b = 0b00100100; // a - b
736 /// let b_a = 0b00011010; // b - a
737 ///
738 /// let mut bva = BitVec::from_bytes(&[a]);
739 /// let bvb = BitVec::from_bytes(&[b]);
740 ///
741 /// assert!(bva.difference(&bvb));
742 /// assert_eq!(bva, BitVec::from_bytes(&[a_b]));
743 ///
744 /// let bva = BitVec::from_bytes(&[a]);
745 /// let mut bvb = BitVec::from_bytes(&[b]);
746 ///
747 /// assert!(bvb.difference(&bva));
748 /// assert_eq!(bvb, BitVec::from_bytes(&[b_a]));
749 /// ```
750 #[inline]
difference(&mut self, other: &Self) -> bool751 pub fn difference(&mut self, other: &Self) -> bool {
752 self.ensure_invariant();
753 debug_assert!(other.is_last_block_fixed());
754 self.process(other, |w1, w2| (w1 & !w2))
755 }
756
757 /// Calculates the xor of two bitvectors.
758 ///
759 /// Sets `self` to the xor of `self` and `other`. Both bitvectors must be
760 /// the same length. Returns `true` if `self` changed.
761 ///
762 /// # Panics
763 ///
764 /// Panics if the bitvectors are of different length.
765 ///
766 /// # Examples
767 ///
768 /// ```
769 /// use bit_vec::BitVec;
770 ///
771 /// let a = 0b01100110;
772 /// let b = 0b01010100;
773 /// let res = 0b00110010;
774 ///
775 /// let mut a = BitVec::from_bytes(&[a]);
776 /// let b = BitVec::from_bytes(&[b]);
777 ///
778 /// assert!(a.xor(&b));
779 /// assert_eq!(a, BitVec::from_bytes(&[res]));
780 /// ```
781 #[inline]
xor(&mut self, other: &Self) -> bool782 pub fn xor(&mut self, other: &Self) -> bool {
783 self.ensure_invariant();
784 debug_assert!(other.is_last_block_fixed());
785 self.process(other, |w1, w2| (w1 ^ w2))
786 }
787
788 /// Calculates the nand of two bitvectors.
789 ///
790 /// Sets `self` to the nand of `self` and `other`. Both bitvectors must be
791 /// the same length. Returns `true` if `self` changed.
792 ///
793 /// # Panics
794 ///
795 /// Panics if the bitvectors are of different length.
796 ///
797 /// # Examples
798 ///
799 /// ```
800 /// use bit_vec::BitVec;
801 ///
802 /// let a = 0b01100110;
803 /// let b = 0b01010100;
804 /// let res = 0b10111011;
805 ///
806 /// let mut a = BitVec::from_bytes(&[a]);
807 /// let b = BitVec::from_bytes(&[b]);
808 ///
809 /// assert!(a.nand(&b));
810 /// assert_eq!(a, BitVec::from_bytes(&[res]));
811 /// ```
812 #[inline]
nand(&mut self, other: &Self) -> bool813 pub fn nand(&mut self, other: &Self) -> bool {
814 self.ensure_invariant();
815 debug_assert!(other.is_last_block_fixed());
816 self.fix_last_block_with_ones();
817 let result = self.process(other, |w1, w2| !(w1 & w2));
818 self.fix_last_block();
819 result
820 }
821
822 /// Calculates the nor of two bitvectors.
823 ///
824 /// Sets `self` to the nor of `self` and `other`. Both bitvectors must be
825 /// the same length. Returns `true` if `self` changed.
826 ///
827 /// # Panics
828 ///
829 /// Panics if the bitvectors are of different length.
830 ///
831 /// # Examples
832 ///
833 /// ```
834 /// use bit_vec::BitVec;
835 ///
836 /// let a = 0b01100110;
837 /// let b = 0b01010100;
838 /// let res = 0b10001001;
839 ///
840 /// let mut a = BitVec::from_bytes(&[a]);
841 /// let b = BitVec::from_bytes(&[b]);
842 ///
843 /// assert!(a.nor(&b));
844 /// assert_eq!(a, BitVec::from_bytes(&[res]));
845 /// ```
846 #[inline]
nor(&mut self, other: &Self) -> bool847 pub fn nor(&mut self, other: &Self) -> bool {
848 self.ensure_invariant();
849 debug_assert!(other.is_last_block_fixed());
850 self.fix_last_block_with_ones();
851 let result = self.process(other, |w1, w2| !(w1 | w2));
852 self.fix_last_block();
853 result
854 }
855
856 /// Calculates the xnor of two bitvectors.
857 ///
858 /// Sets `self` to the xnor of `self` and `other`. Both bitvectors must be
859 /// the same length. Returns `true` if `self` changed.
860 ///
861 /// # Panics
862 ///
863 /// Panics if the bitvectors are of different length.
864 ///
865 /// # Examples
866 ///
867 /// ```
868 /// use bit_vec::BitVec;
869 ///
870 /// let a = 0b01100110;
871 /// let b = 0b01010100;
872 /// let res = 0b11001101;
873 ///
874 /// let mut a = BitVec::from_bytes(&[a]);
875 /// let b = BitVec::from_bytes(&[b]);
876 ///
877 /// assert!(a.xnor(&b));
878 /// assert_eq!(a, BitVec::from_bytes(&[res]));
879 /// ```
880 #[inline]
xnor(&mut self, other: &Self) -> bool881 pub fn xnor(&mut self, other: &Self) -> bool {
882 self.ensure_invariant();
883 debug_assert!(other.is_last_block_fixed());
884 self.fix_last_block_with_ones();
885 let result = self.process(other, |w1, w2| !(w1 ^ w2));
886 self.fix_last_block();
887 result
888 }
889
890 /// Returns `true` if all bits are 1.
891 ///
892 /// # Examples
893 ///
894 /// ```
895 /// use bit_vec::BitVec;
896 ///
897 /// let mut bv = BitVec::from_elem(5, true);
898 /// assert_eq!(bv.all(), true);
899 ///
900 /// bv.set(1, false);
901 /// assert_eq!(bv.all(), false);
902 /// ```
903 #[inline]
all(&self) -> bool904 pub fn all(&self) -> bool {
905 self.ensure_invariant();
906 let mut last_word = !B::zero();
907 // Check that every block but the last is all-ones...
908 self.blocks().all(|elem| {
909 let tmp = last_word;
910 last_word = elem;
911 tmp == !B::zero()
912 // and then check the last one has enough ones
913 }) && (last_word == mask_for_bits(self.nbits))
914 }
915
916 /// Returns an iterator over the elements of the vector in order.
917 ///
918 /// # Examples
919 ///
920 /// ```
921 /// use bit_vec::BitVec;
922 ///
923 /// let bv = BitVec::from_bytes(&[0b01110100, 0b10010010]);
924 /// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
925 /// ```
926 #[inline]
iter(&self) -> Iter<B>927 pub fn iter(&self) -> Iter<B> {
928 self.ensure_invariant();
929 Iter { bit_vec: self, range: 0..self.nbits }
930 }
931
932 /// Moves all bits from `other` into `Self`, leaving `other` empty.
933 ///
934 /// # Examples
935 ///
936 /// ```
937 /// use bit_vec::BitVec;
938 ///
939 /// let mut a = BitVec::from_bytes(&[0b10000000]);
940 /// let mut b = BitVec::from_bytes(&[0b01100001]);
941 ///
942 /// a.append(&mut b);
943 ///
944 /// assert_eq!(a.len(), 16);
945 /// assert_eq!(b.len(), 0);
946 /// assert!(a.eq_vec(&[true, false, false, false, false, false, false, false,
947 /// false, true, true, false, false, false, false, true]));
948 /// ```
append(&mut self, other: &mut Self)949 pub fn append(&mut self, other: &mut Self) {
950 self.ensure_invariant();
951 debug_assert!(other.is_last_block_fixed());
952
953 let b = self.len() % B::bits();
954
955 self.nbits += other.len();
956 other.nbits = 0;
957
958 if b == 0 {
959 self.storage.append(&mut other.storage);
960 } else {
961 self.storage.reserve(other.storage.len());
962
963 for block in other.storage.drain(..) {
964 {
965 let last = self.storage.last_mut().unwrap();
966 *last = *last | (block << b);
967 }
968 self.storage.push(block >> (B::bits() - b));
969 }
970 }
971 }
972
973 /// Splits the `BitVec` into two at the given bit,
974 /// retaining the first half in-place and returning the second one.
975 ///
976 /// # Panics
977 ///
978 /// Panics if `at` is out of bounds.
979 ///
980 /// # Examples
981 ///
982 /// ```
983 /// use bit_vec::BitVec;
984 /// let mut a = BitVec::new();
985 /// a.push(true);
986 /// a.push(false);
987 /// a.push(false);
988 /// a.push(true);
989 ///
990 /// let b = a.split_off(2);
991 ///
992 /// assert_eq!(a.len(), 2);
993 /// assert_eq!(b.len(), 2);
994 /// assert!(a.eq_vec(&[true, false]));
995 /// assert!(b.eq_vec(&[false, true]));
996 /// ```
split_off(&mut self, at: usize) -> Self997 pub fn split_off(&mut self, at: usize) -> Self {
998 self.ensure_invariant();
999 assert!(at <= self.len(), "`at` out of bounds");
1000
1001 let mut other = BitVec::<B>::default();
1002
1003 if at == 0 {
1004 mem::swap(self, &mut other);
1005 return other;
1006 } else if at == self.len() {
1007 return other;
1008 }
1009
1010 let w = at / B::bits();
1011 let b = at % B::bits();
1012 other.nbits = self.nbits - at;
1013 self.nbits = at;
1014 if b == 0 {
1015 // Split at block boundary
1016 other.storage = self.storage.split_off(w);
1017 } else {
1018 other.storage.reserve(self.storage.len() - w);
1019
1020 {
1021 let mut iter = self.storage[w..].iter();
1022 let mut last = *iter.next().unwrap();
1023 for &cur in iter {
1024 other.storage.push((last >> b) | (cur << (B::bits() - b)));
1025 last = cur;
1026 }
1027 other.storage.push(last >> b);
1028 }
1029
1030 self.storage.truncate(w + 1);
1031 self.fix_last_block();
1032 }
1033
1034 other
1035 }
1036
1037 /// Returns `true` if all bits are 0.
1038 ///
1039 /// # Examples
1040 ///
1041 /// ```
1042 /// use bit_vec::BitVec;
1043 ///
1044 /// let mut bv = BitVec::from_elem(10, false);
1045 /// assert_eq!(bv.none(), true);
1046 ///
1047 /// bv.set(3, true);
1048 /// assert_eq!(bv.none(), false);
1049 /// ```
1050 #[inline]
none(&self) -> bool1051 pub fn none(&self) -> bool {
1052 self.blocks().all(|w| w == B::zero())
1053 }
1054
1055 /// Returns `true` if any bit is 1.
1056 ///
1057 /// # Examples
1058 ///
1059 /// ```
1060 /// use bit_vec::BitVec;
1061 ///
1062 /// let mut bv = BitVec::from_elem(10, false);
1063 /// assert_eq!(bv.any(), false);
1064 ///
1065 /// bv.set(3, true);
1066 /// assert_eq!(bv.any(), true);
1067 /// ```
1068 #[inline]
any(&self) -> bool1069 pub fn any(&self) -> bool {
1070 !self.none()
1071 }
1072
1073 /// Organises the bits into bytes, such that the first bit in the
1074 /// `BitVec` becomes the high-order bit of the first byte. If the
1075 /// size of the `BitVec` is not a multiple of eight then trailing bits
1076 /// will be filled-in with `false`.
1077 ///
1078 /// # Examples
1079 ///
1080 /// ```
1081 /// use bit_vec::BitVec;
1082 ///
1083 /// let mut bv = BitVec::from_elem(3, true);
1084 /// bv.set(1, false);
1085 ///
1086 /// assert_eq!(bv.to_bytes(), [0b10100000]);
1087 ///
1088 /// let mut bv = BitVec::from_elem(9, false);
1089 /// bv.set(2, true);
1090 /// bv.set(8, true);
1091 ///
1092 /// assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
1093 /// ```
to_bytes(&self) -> Vec<u8>1094 pub fn to_bytes(&self) -> Vec<u8> {
1095 self.ensure_invariant();
1096 // Oh lord, we're mapping this to bytes bit-by-bit!
1097 fn bit<B: BitBlock>(bit_vec: &BitVec<B>, byte: usize, bit: usize) -> u8 {
1098 let offset = byte * 8 + bit;
1099 if offset >= bit_vec.nbits {
1100 0
1101 } else {
1102 (bit_vec[offset] as u8) << (7 - bit)
1103 }
1104 }
1105
1106 let len = self.nbits / 8 +
1107 if self.nbits % 8 == 0 { 0 } else { 1 };
1108 (0..len).map(|i|
1109 bit(self, i, 0) |
1110 bit(self, i, 1) |
1111 bit(self, i, 2) |
1112 bit(self, i, 3) |
1113 bit(self, i, 4) |
1114 bit(self, i, 5) |
1115 bit(self, i, 6) |
1116 bit(self, i, 7)
1117 ).collect()
1118 }
1119
1120 /// Compares a `BitVec` to a slice of `bool`s.
1121 /// Both the `BitVec` and slice must have the same length.
1122 ///
1123 /// # Panics
1124 ///
1125 /// Panics if the `BitVec` and slice are of different length.
1126 ///
1127 /// # Examples
1128 ///
1129 /// ```
1130 /// use bit_vec::BitVec;
1131 ///
1132 /// let bv = BitVec::from_bytes(&[0b10100000]);
1133 ///
1134 /// assert!(bv.eq_vec(&[true, false, true, false,
1135 /// false, false, false, false]));
1136 /// ```
1137 #[inline]
eq_vec(&self, v: &[bool]) -> bool1138 pub fn eq_vec(&self, v: &[bool]) -> bool {
1139 assert_eq!(self.nbits, v.len());
1140 self.iter().zip(v.iter().cloned()).all(|(b1, b2)| b1 == b2)
1141 }
1142
1143 /// Shortens a `BitVec`, dropping excess elements.
1144 ///
1145 /// If `len` is greater than the vector's current length, this has no
1146 /// effect.
1147 ///
1148 /// # Examples
1149 ///
1150 /// ```
1151 /// use bit_vec::BitVec;
1152 ///
1153 /// let mut bv = BitVec::from_bytes(&[0b01001011]);
1154 /// bv.truncate(2);
1155 /// assert!(bv.eq_vec(&[false, true]));
1156 /// ```
1157 #[inline]
truncate(&mut self, len: usize)1158 pub fn truncate(&mut self, len: usize) {
1159 self.ensure_invariant();
1160 if len < self.len() {
1161 self.nbits = len;
1162 // This fixes (2).
1163 self.storage.truncate(blocks_for_bits::<B>(len));
1164 self.fix_last_block();
1165 }
1166 }
1167
1168 /// Reserves capacity for at least `additional` more bits to be inserted in the given
1169 /// `BitVec`. The collection may reserve more space to avoid frequent reallocations.
1170 ///
1171 /// # Panics
1172 ///
1173 /// Panics if the new capacity overflows `usize`.
1174 ///
1175 /// # Examples
1176 ///
1177 /// ```
1178 /// use bit_vec::BitVec;
1179 ///
1180 /// let mut bv = BitVec::from_elem(3, false);
1181 /// bv.reserve(10);
1182 /// assert_eq!(bv.len(), 3);
1183 /// assert!(bv.capacity() >= 13);
1184 /// ```
1185 #[inline]
reserve(&mut self, additional: usize)1186 pub fn reserve(&mut self, additional: usize) {
1187 let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
1188 let storage_len = self.storage.len();
1189 if desired_cap > self.capacity() {
1190 self.storage.reserve(blocks_for_bits::<B>(desired_cap) - storage_len);
1191 }
1192 }
1193
1194 /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the
1195 /// given `BitVec`. Does nothing if the capacity is already sufficient.
1196 ///
1197 /// Note that the allocator may give the collection more space than it requests. Therefore
1198 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
1199 /// insertions are expected.
1200 ///
1201 /// # Panics
1202 ///
1203 /// Panics if the new capacity overflows `usize`.
1204 ///
1205 /// # Examples
1206 ///
1207 /// ```
1208 /// use bit_vec::BitVec;
1209 ///
1210 /// let mut bv = BitVec::from_elem(3, false);
1211 /// bv.reserve(10);
1212 /// assert_eq!(bv.len(), 3);
1213 /// assert!(bv.capacity() >= 13);
1214 /// ```
1215 #[inline]
reserve_exact(&mut self, additional: usize)1216 pub fn reserve_exact(&mut self, additional: usize) {
1217 let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
1218 let storage_len = self.storage.len();
1219 if desired_cap > self.capacity() {
1220 self.storage.reserve_exact(blocks_for_bits::<B>(desired_cap) - storage_len);
1221 }
1222 }
1223
1224 /// Returns the capacity in bits for this bit vector. Inserting any
1225 /// element less than this amount will not trigger a resizing.
1226 ///
1227 /// # Examples
1228 ///
1229 /// ```
1230 /// use bit_vec::BitVec;
1231 ///
1232 /// let mut bv = BitVec::new();
1233 /// bv.reserve(10);
1234 /// assert!(bv.capacity() >= 10);
1235 /// ```
1236 #[inline]
capacity(&self) -> usize1237 pub fn capacity(&self) -> usize {
1238 self.storage.capacity().checked_mul(B::bits()).unwrap_or(usize::MAX)
1239 }
1240
1241 /// Grows the `BitVec` in-place, adding `n` copies of `value` to the `BitVec`.
1242 ///
1243 /// # Panics
1244 ///
1245 /// Panics if the new len overflows a `usize`.
1246 ///
1247 /// # Examples
1248 ///
1249 /// ```
1250 /// use bit_vec::BitVec;
1251 ///
1252 /// let mut bv = BitVec::from_bytes(&[0b01001011]);
1253 /// bv.grow(2, true);
1254 /// assert_eq!(bv.len(), 10);
1255 /// assert_eq!(bv.to_bytes(), [0b01001011, 0b11000000]);
1256 /// ```
grow(&mut self, n: usize, value: bool)1257 pub fn grow(&mut self, n: usize, value: bool) {
1258 self.ensure_invariant();
1259
1260 // Note: we just bulk set all the bits in the last word in this fn in multiple places
1261 // which is technically wrong if not all of these bits are to be used. However, at the end
1262 // of this fn we call `fix_last_block` at the end of this fn, which should fix this.
1263
1264 let new_nbits = self.nbits.checked_add(n).expect("capacity overflow");
1265 let new_nblocks = blocks_for_bits::<B>(new_nbits);
1266 let full_value = if value { !B::zero() } else { B::zero() };
1267
1268 // Correct the old tail word, setting or clearing formerly unused bits
1269 let num_cur_blocks = blocks_for_bits::<B>(self.nbits);
1270 if self.nbits % B::bits() > 0 {
1271 let mask = mask_for_bits::<B>(self.nbits);
1272 if value {
1273 let block = &mut self.storage[num_cur_blocks - 1];
1274 *block = *block | !mask;
1275 } else {
1276 // Extra bits are already zero by invariant.
1277 }
1278 }
1279
1280 // Fill in words after the old tail word
1281 let stop_idx = cmp::min(self.storage.len(), new_nblocks);
1282 for idx in num_cur_blocks..stop_idx {
1283 self.storage[idx] = full_value;
1284 }
1285
1286 // Allocate new words, if needed
1287 if new_nblocks > self.storage.len() {
1288 let to_add = new_nblocks - self.storage.len();
1289 self.storage.extend(repeat(full_value).take(to_add));
1290 }
1291
1292 // Adjust internal bit count
1293 self.nbits = new_nbits;
1294
1295 self.fix_last_block();
1296 }
1297
1298 /// Removes the last bit from the BitVec, and returns it. Returns None if the BitVec is empty.
1299 ///
1300 /// # Examples
1301 ///
1302 /// ```
1303 /// use bit_vec::BitVec;
1304 ///
1305 /// let mut bv = BitVec::from_bytes(&[0b01001001]);
1306 /// assert_eq!(bv.pop(), Some(true));
1307 /// assert_eq!(bv.pop(), Some(false));
1308 /// assert_eq!(bv.len(), 6);
1309 /// ```
1310 #[inline]
pop(&mut self) -> Option<bool>1311 pub fn pop(&mut self) -> Option<bool> {
1312 self.ensure_invariant();
1313
1314 if self.is_empty() {
1315 None
1316 } else {
1317 let i = self.nbits - 1;
1318 let ret = self[i];
1319 // (3)
1320 self.set(i, false);
1321 self.nbits = i;
1322 if self.nbits % B::bits() == 0 {
1323 // (2)
1324 self.storage.pop();
1325 }
1326 Some(ret)
1327 }
1328 }
1329
1330 /// Pushes a `bool` onto the end.
1331 ///
1332 /// # Examples
1333 ///
1334 /// ```
1335 /// use bit_vec::BitVec;
1336 ///
1337 /// let mut bv = BitVec::new();
1338 /// bv.push(true);
1339 /// bv.push(false);
1340 /// assert!(bv.eq_vec(&[true, false]));
1341 /// ```
1342 #[inline]
push(&mut self, elem: bool)1343 pub fn push(&mut self, elem: bool) {
1344 if self.nbits % B::bits() == 0 {
1345 self.storage.push(B::zero());
1346 }
1347 let insert_pos = self.nbits;
1348 self.nbits = self.nbits.checked_add(1).expect("Capacity overflow");
1349 self.set(insert_pos, elem);
1350 }
1351
1352 /// Returns the total number of bits in this vector
1353 #[inline]
len(&self) -> usize1354 pub fn len(&self) -> usize { self.nbits }
1355
1356 /// Sets the number of bits that this BitVec considers initialized.
1357 ///
1358 /// Almost certainly can cause bad stuff. Only really intended for BitSet.
1359 #[inline]
set_len(&mut self, len: usize)1360 pub unsafe fn set_len(&mut self, len: usize) {
1361 self.nbits = len;
1362 }
1363
1364 /// Returns true if there are no bits in this vector
1365 #[inline]
is_empty(&self) -> bool1366 pub fn is_empty(&self) -> bool { self.len() == 0 }
1367
1368 /// Clears all bits in this vector.
1369 #[inline]
clear(&mut self)1370 pub fn clear(&mut self) {
1371 self.ensure_invariant();
1372 for w in &mut self.storage { *w = B::zero(); }
1373 }
1374
1375 /// Shrinks the capacity of the underlying storage as much as
1376 /// possible.
1377 ///
1378 /// It will drop down as close as possible to the length but the
1379 /// allocator may still inform the underlying storage that there
1380 /// is space for a few more elements/bits.
shrink_to_fit(&mut self)1381 pub fn shrink_to_fit(&mut self) {
1382 self.storage.shrink_to_fit();
1383 }
1384 }
1385
1386 impl<B: BitBlock> Default for BitVec<B> {
1387 #[inline]
default() -> Self1388 fn default() -> Self { BitVec { storage: Vec::new(), nbits: 0 } }
1389 }
1390
1391 impl<B: BitBlock> FromIterator<bool> for BitVec<B> {
1392 #[inline]
from_iter<I: IntoIterator<Item=bool>>(iter: I) -> Self1393 fn from_iter<I: IntoIterator<Item=bool>>(iter: I) -> Self {
1394 let mut ret: Self = Default::default();
1395 ret.extend(iter);
1396 ret
1397 }
1398 }
1399
1400 impl<B: BitBlock> Extend<bool> for BitVec<B> {
1401 #[inline]
extend<I: IntoIterator<Item=bool>>(&mut self, iterable: I)1402 fn extend<I: IntoIterator<Item=bool>>(&mut self, iterable: I) {
1403 self.ensure_invariant();
1404 let iterator = iterable.into_iter();
1405 let (min, _) = iterator.size_hint();
1406 self.reserve(min);
1407 for element in iterator {
1408 self.push(element)
1409 }
1410 }
1411 }
1412
1413 impl<B: BitBlock> Clone for BitVec<B> {
1414 #[inline]
clone(&self) -> Self1415 fn clone(&self) -> Self {
1416 self.ensure_invariant();
1417 BitVec { storage: self.storage.clone(), nbits: self.nbits }
1418 }
1419
1420 #[inline]
clone_from(&mut self, source: &Self)1421 fn clone_from(&mut self, source: &Self) {
1422 debug_assert!(source.is_last_block_fixed());
1423 self.nbits = source.nbits;
1424 self.storage.clone_from(&source.storage);
1425 }
1426 }
1427
1428 impl<B: BitBlock> PartialOrd for BitVec<B> {
1429 #[inline]
partial_cmp(&self, other: &Self) -> Option<Ordering>1430 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1431 Some(self.cmp(other))
1432 }
1433 }
1434
1435 impl<B: BitBlock> Ord for BitVec<B> {
1436 #[inline]
cmp(&self, other: &Self) -> Ordering1437 fn cmp(&self, other: &Self) -> Ordering {
1438 self.ensure_invariant();
1439 debug_assert!(other.is_last_block_fixed());
1440 let mut a = self.iter();
1441 let mut b = other.iter();
1442 loop {
1443 match (a.next(), b.next()) {
1444 (Some(x), Some(y)) => match x.cmp(&y) {
1445 Ordering::Equal => {}
1446 otherwise => return otherwise,
1447 },
1448 (None, None) => return Ordering::Equal,
1449 (None, _) => return Ordering::Less,
1450 (_, None) => return Ordering::Greater,
1451 }
1452 }
1453 }
1454 }
1455
1456 impl<B: BitBlock> fmt::Debug for BitVec<B> {
fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result1457 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
1458 self.ensure_invariant();
1459 for bit in self {
1460 write!(fmt, "{}", if bit { 1 } else { 0 })?;
1461 }
1462 Ok(())
1463 }
1464 }
1465
1466 impl<B: BitBlock> hash::Hash for BitVec<B> {
1467 #[inline]
hash<H: hash::Hasher>(&self, state: &mut H)1468 fn hash<H: hash::Hasher>(&self, state: &mut H) {
1469 self.ensure_invariant();
1470 self.nbits.hash(state);
1471 for elem in self.blocks() {
1472 elem.hash(state);
1473 }
1474 }
1475 }
1476
1477 impl<B: BitBlock> cmp::PartialEq for BitVec<B> {
1478 #[inline]
eq(&self, other: &Self) -> bool1479 fn eq(&self, other: &Self) -> bool {
1480 if self.nbits != other.nbits {
1481 self.ensure_invariant();
1482 other.ensure_invariant();
1483 return false;
1484 }
1485 self.blocks().zip(other.blocks()).all(|(w1, w2)| w1 == w2)
1486 }
1487 }
1488
1489 impl<B: BitBlock> cmp::Eq for BitVec<B> {}
1490
1491 /// An iterator for `BitVec`.
1492 #[derive(Clone)]
1493 pub struct Iter<'a, B: 'a = u32> {
1494 bit_vec: &'a BitVec<B>,
1495 range: Range<usize>,
1496 }
1497
1498 impl<'a, B: BitBlock> Iterator for Iter<'a, B> {
1499 type Item = bool;
1500
1501 #[inline]
next(&mut self) -> Option<bool>1502 fn next(&mut self) -> Option<bool> {
1503 // NB: indexing is slow for extern crates when it has to go through &TRUE or &FALSE
1504 // variables. get is more direct, and unwrap is fine since we're sure of the range.
1505 self.range.next().map(|i| self.bit_vec.get(i).unwrap())
1506 }
1507
size_hint(&self) -> (usize, Option<usize>)1508 fn size_hint(&self) -> (usize, Option<usize>) {
1509 self.range.size_hint()
1510 }
1511 }
1512
1513 impl<'a, B: BitBlock> DoubleEndedIterator for Iter<'a, B> {
1514 #[inline]
next_back(&mut self) -> Option<bool>1515 fn next_back(&mut self) -> Option<bool> {
1516 self.range.next_back().map(|i| self.bit_vec.get(i).unwrap())
1517 }
1518 }
1519
1520 impl<'a, B: BitBlock> ExactSizeIterator for Iter<'a, B> {}
1521
1522 impl<'a, B: BitBlock> IntoIterator for &'a BitVec<B> {
1523 type Item = bool;
1524 type IntoIter = Iter<'a, B>;
1525
1526 #[inline]
into_iter(self) -> Iter<'a, B>1527 fn into_iter(self) -> Iter<'a, B> {
1528 self.iter()
1529 }
1530 }
1531
1532 pub struct IntoIter<B=u32> {
1533 bit_vec: BitVec<B>,
1534 range: Range<usize>,
1535 }
1536
1537 impl<B: BitBlock> Iterator for IntoIter<B> {
1538 type Item = bool;
1539
1540 #[inline]
next(&mut self) -> Option<bool>1541 fn next(&mut self) -> Option<bool> {
1542 self.range.next().map(|i| self.bit_vec.get(i).unwrap())
1543 }
1544 }
1545
1546 impl<B: BitBlock> DoubleEndedIterator for IntoIter<B> {
1547 #[inline]
next_back(&mut self) -> Option<bool>1548 fn next_back(&mut self) -> Option<bool> {
1549 self.range.next_back().map(|i| self.bit_vec.get(i).unwrap())
1550 }
1551 }
1552
1553 impl<B: BitBlock> ExactSizeIterator for IntoIter<B> {}
1554
1555 impl<B: BitBlock> IntoIterator for BitVec<B> {
1556 type Item = bool;
1557 type IntoIter = IntoIter<B>;
1558
1559 #[inline]
into_iter(self) -> IntoIter<B>1560 fn into_iter(self) -> IntoIter<B> {
1561 let nbits = self.nbits;
1562 IntoIter { bit_vec: self, range: 0..nbits }
1563 }
1564 }
1565
1566 /// An iterator over the blocks of a `BitVec`.
1567 #[derive(Clone)]
1568 pub struct Blocks<'a, B: 'a> {
1569 iter: slice::Iter<'a, B>,
1570 }
1571
1572 impl<'a, B: BitBlock> Iterator for Blocks<'a, B> {
1573 type Item = B;
1574
1575 #[inline]
next(&mut self) -> Option<B>1576 fn next(&mut self) -> Option<B> {
1577 self.iter.next().cloned()
1578 }
1579
1580 #[inline]
size_hint(&self) -> (usize, Option<usize>)1581 fn size_hint(&self) -> (usize, Option<usize>) {
1582 self.iter.size_hint()
1583 }
1584 }
1585
1586 impl<'a, B: BitBlock> DoubleEndedIterator for Blocks<'a, B> {
1587 #[inline]
next_back(&mut self) -> Option<B>1588 fn next_back(&mut self) -> Option<B> {
1589 self.iter.next_back().cloned()
1590 }
1591 }
1592
1593 impl<'a, B: BitBlock> ExactSizeIterator for Blocks<'a, B> {}
1594
1595 #[cfg(test)]
1596 mod tests {
1597 use super::{BitVec, Iter, Vec};
1598
1599 // This is stupid, but I want to differentiate from a "random" 32
1600 const U32_BITS: usize = 32;
1601
1602 #[test]
test_to_str()1603 fn test_to_str() {
1604 let zerolen = BitVec::new();
1605 assert_eq!(format!("{:?}", zerolen), "");
1606
1607 let eightbits = BitVec::from_elem(8, false);
1608 assert_eq!(format!("{:?}", eightbits), "00000000")
1609 }
1610
1611 #[test]
test_0_elements()1612 fn test_0_elements() {
1613 let act = BitVec::new();
1614 let exp = Vec::new();
1615 assert!(act.eq_vec(&exp));
1616 assert!(act.none() && act.all());
1617 }
1618
1619 #[test]
test_1_element()1620 fn test_1_element() {
1621 let mut act = BitVec::from_elem(1, false);
1622 assert!(act.eq_vec(&[false]));
1623 assert!(act.none() && !act.all());
1624 act = BitVec::from_elem(1, true);
1625 assert!(act.eq_vec(&[true]));
1626 assert!(!act.none() && act.all());
1627 }
1628
1629 #[test]
test_2_elements()1630 fn test_2_elements() {
1631 let mut b = BitVec::from_elem(2, false);
1632 b.set(0, true);
1633 b.set(1, false);
1634 assert_eq!(format!("{:?}", b), "10");
1635 assert!(!b.none() && !b.all());
1636 }
1637
1638 #[test]
test_10_elements()1639 fn test_10_elements() {
1640 let mut act;
1641 // all 0
1642
1643 act = BitVec::from_elem(10, false);
1644 assert!((act.eq_vec(
1645 &[false, false, false, false, false, false, false, false, false, false])));
1646 assert!(act.none() && !act.all());
1647 // all 1
1648
1649 act = BitVec::from_elem(10, true);
1650 assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
1651 assert!(!act.none() && act.all());
1652 // mixed
1653
1654 act = BitVec::from_elem(10, false);
1655 act.set(0, true);
1656 act.set(1, true);
1657 act.set(2, true);
1658 act.set(3, true);
1659 act.set(4, true);
1660 assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
1661 assert!(!act.none() && !act.all());
1662 // mixed
1663
1664 act = BitVec::from_elem(10, false);
1665 act.set(5, true);
1666 act.set(6, true);
1667 act.set(7, true);
1668 act.set(8, true);
1669 act.set(9, true);
1670 assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
1671 assert!(!act.none() && !act.all());
1672 // mixed
1673
1674 act = BitVec::from_elem(10, false);
1675 act.set(0, true);
1676 act.set(3, true);
1677 act.set(6, true);
1678 act.set(9, true);
1679 assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
1680 assert!(!act.none() && !act.all());
1681 }
1682
1683 #[test]
test_31_elements()1684 fn test_31_elements() {
1685 let mut act;
1686 // all 0
1687
1688 act = BitVec::from_elem(31, false);
1689 assert!(act.eq_vec(
1690 &[false, false, false, false, false, false, false, false, false, false, false,
1691 false, false, false, false, false, false, false, false, false, false, false,
1692 false, false, false, false, false, false, false, false, false]));
1693 assert!(act.none() && !act.all());
1694 // all 1
1695
1696 act = BitVec::from_elem(31, true);
1697 assert!(act.eq_vec(
1698 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1699 true, true, true, true, true, true, true, true, true, true, true, true, true,
1700 true, true, true, true, true]));
1701 assert!(!act.none() && act.all());
1702 // mixed
1703
1704 act = BitVec::from_elem(31, false);
1705 act.set(0, true);
1706 act.set(1, true);
1707 act.set(2, true);
1708 act.set(3, true);
1709 act.set(4, true);
1710 act.set(5, true);
1711 act.set(6, true);
1712 act.set(7, true);
1713 assert!(act.eq_vec(
1714 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1715 false, false, false, false, false, false, false, false, false, false, false,
1716 false, false, false, false, false, false, false]));
1717 assert!(!act.none() && !act.all());
1718 // mixed
1719
1720 act = BitVec::from_elem(31, false);
1721 act.set(16, true);
1722 act.set(17, true);
1723 act.set(18, true);
1724 act.set(19, true);
1725 act.set(20, true);
1726 act.set(21, true);
1727 act.set(22, true);
1728 act.set(23, true);
1729 assert!(act.eq_vec(
1730 &[false, false, false, false, false, false, false, false, false, false, false,
1731 false, false, false, false, false, true, true, true, true, true, true, true, true,
1732 false, false, false, false, false, false, false]));
1733 assert!(!act.none() && !act.all());
1734 // mixed
1735
1736 act = BitVec::from_elem(31, false);
1737 act.set(24, true);
1738 act.set(25, true);
1739 act.set(26, true);
1740 act.set(27, true);
1741 act.set(28, true);
1742 act.set(29, true);
1743 act.set(30, true);
1744 assert!(act.eq_vec(
1745 &[false, false, false, false, false, false, false, false, false, false, false,
1746 false, false, false, false, false, false, false, false, false, false, false,
1747 false, false, true, true, true, true, true, true, true]));
1748 assert!(!act.none() && !act.all());
1749 // mixed
1750
1751 act = BitVec::from_elem(31, false);
1752 act.set(3, true);
1753 act.set(17, true);
1754 act.set(30, true);
1755 assert!(act.eq_vec(
1756 &[false, false, false, true, false, false, false, false, false, false, false, false,
1757 false, false, false, false, false, true, false, false, false, false, false, false,
1758 false, false, false, false, false, false, true]));
1759 assert!(!act.none() && !act.all());
1760 }
1761
1762 #[test]
test_32_elements()1763 fn test_32_elements() {
1764 let mut act;
1765 // all 0
1766
1767 act = BitVec::from_elem(32, false);
1768 assert!(act.eq_vec(
1769 &[false, false, false, false, false, false, false, false, false, false, false,
1770 false, false, false, false, false, false, false, false, false, false, false,
1771 false, false, false, false, false, false, false, false, false, false]));
1772 assert!(act.none() && !act.all());
1773 // all 1
1774
1775 act = BitVec::from_elem(32, true);
1776 assert!(act.eq_vec(
1777 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1778 true, true, true, true, true, true, true, true, true, true, true, true, true,
1779 true, true, true, true, true, true]));
1780 assert!(!act.none() && act.all());
1781 // mixed
1782
1783 act = BitVec::from_elem(32, false);
1784 act.set(0, true);
1785 act.set(1, true);
1786 act.set(2, true);
1787 act.set(3, true);
1788 act.set(4, true);
1789 act.set(5, true);
1790 act.set(6, true);
1791 act.set(7, true);
1792 assert!(act.eq_vec(
1793 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1794 false, false, false, false, false, false, false, false, false, false, false,
1795 false, false, false, false, false, false, false, false]));
1796 assert!(!act.none() && !act.all());
1797 // mixed
1798
1799 act = BitVec::from_elem(32, false);
1800 act.set(16, true);
1801 act.set(17, true);
1802 act.set(18, true);
1803 act.set(19, true);
1804 act.set(20, true);
1805 act.set(21, true);
1806 act.set(22, true);
1807 act.set(23, true);
1808 assert!(act.eq_vec(
1809 &[false, false, false, false, false, false, false, false, false, false, false,
1810 false, false, false, false, false, true, true, true, true, true, true, true, true,
1811 false, false, false, false, false, false, false, false]));
1812 assert!(!act.none() && !act.all());
1813 // mixed
1814
1815 act = BitVec::from_elem(32, false);
1816 act.set(24, true);
1817 act.set(25, true);
1818 act.set(26, true);
1819 act.set(27, true);
1820 act.set(28, true);
1821 act.set(29, true);
1822 act.set(30, true);
1823 act.set(31, true);
1824 assert!(act.eq_vec(
1825 &[false, false, false, false, false, false, false, false, false, false, false,
1826 false, false, false, false, false, false, false, false, false, false, false,
1827 false, false, true, true, true, true, true, true, true, true]));
1828 assert!(!act.none() && !act.all());
1829 // mixed
1830
1831 act = BitVec::from_elem(32, false);
1832 act.set(3, true);
1833 act.set(17, true);
1834 act.set(30, true);
1835 act.set(31, true);
1836 assert!(act.eq_vec(
1837 &[false, false, false, true, false, false, false, false, false, false, false, false,
1838 false, false, false, false, false, true, false, false, false, false, false, false,
1839 false, false, false, false, false, false, true, true]));
1840 assert!(!act.none() && !act.all());
1841 }
1842
1843 #[test]
test_33_elements()1844 fn test_33_elements() {
1845 let mut act;
1846 // all 0
1847
1848 act = BitVec::from_elem(33, false);
1849 assert!(act.eq_vec(
1850 &[false, false, false, false, false, false, false, false, false, false, false,
1851 false, false, false, false, false, false, false, false, false, false, false,
1852 false, false, false, false, false, false, false, false, false, false, false]));
1853 assert!(act.none() && !act.all());
1854 // all 1
1855
1856 act = BitVec::from_elem(33, true);
1857 assert!(act.eq_vec(
1858 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
1859 true, true, true, true, true, true, true, true, true, true, true, true, true,
1860 true, true, true, true, true, true, true]));
1861 assert!(!act.none() && act.all());
1862 // mixed
1863
1864 act = BitVec::from_elem(33, false);
1865 act.set(0, true);
1866 act.set(1, true);
1867 act.set(2, true);
1868 act.set(3, true);
1869 act.set(4, true);
1870 act.set(5, true);
1871 act.set(6, true);
1872 act.set(7, true);
1873 assert!(act.eq_vec(
1874 &[true, true, true, true, true, true, true, true, false, false, false, false, false,
1875 false, false, false, false, false, false, false, false, false, false, false,
1876 false, false, false, false, false, false, false, false, false]));
1877 assert!(!act.none() && !act.all());
1878 // mixed
1879
1880 act = BitVec::from_elem(33, false);
1881 act.set(16, true);
1882 act.set(17, true);
1883 act.set(18, true);
1884 act.set(19, true);
1885 act.set(20, true);
1886 act.set(21, true);
1887 act.set(22, true);
1888 act.set(23, true);
1889 assert!(act.eq_vec(
1890 &[false, false, false, false, false, false, false, false, false, false, false,
1891 false, false, false, false, false, true, true, true, true, true, true, true, true,
1892 false, false, false, false, false, false, false, false, false]));
1893 assert!(!act.none() && !act.all());
1894 // mixed
1895
1896 act = BitVec::from_elem(33, false);
1897 act.set(24, true);
1898 act.set(25, true);
1899 act.set(26, true);
1900 act.set(27, true);
1901 act.set(28, true);
1902 act.set(29, true);
1903 act.set(30, true);
1904 act.set(31, true);
1905 assert!(act.eq_vec(
1906 &[false, false, false, false, false, false, false, false, false, false, false,
1907 false, false, false, false, false, false, false, false, false, false, false,
1908 false, false, true, true, true, true, true, true, true, true, false]));
1909 assert!(!act.none() && !act.all());
1910 // mixed
1911
1912 act = BitVec::from_elem(33, false);
1913 act.set(3, true);
1914 act.set(17, true);
1915 act.set(30, true);
1916 act.set(31, true);
1917 act.set(32, true);
1918 assert!(act.eq_vec(
1919 &[false, false, false, true, false, false, false, false, false, false, false, false,
1920 false, false, false, false, false, true, false, false, false, false, false, false,
1921 false, false, false, false, false, false, true, true, true]));
1922 assert!(!act.none() && !act.all());
1923 }
1924
1925 #[test]
test_equal_differing_sizes()1926 fn test_equal_differing_sizes() {
1927 let v0 = BitVec::from_elem(10, false);
1928 let v1 = BitVec::from_elem(11, false);
1929 assert_ne!(v0, v1);
1930 }
1931
1932 #[test]
test_equal_greatly_differing_sizes()1933 fn test_equal_greatly_differing_sizes() {
1934 let v0 = BitVec::from_elem(10, false);
1935 let v1 = BitVec::from_elem(110, false);
1936 assert_ne!(v0, v1);
1937 }
1938
1939 #[test]
test_equal_sneaky_small()1940 fn test_equal_sneaky_small() {
1941 let mut a = BitVec::from_elem(1, false);
1942 a.set(0, true);
1943
1944 let mut b = BitVec::from_elem(1, true);
1945 b.set(0, true);
1946
1947 assert_eq!(a, b);
1948 }
1949
1950 #[test]
test_equal_sneaky_big()1951 fn test_equal_sneaky_big() {
1952 let mut a = BitVec::from_elem(100, false);
1953 for i in 0..100 {
1954 a.set(i, true);
1955 }
1956
1957 let mut b = BitVec::from_elem(100, true);
1958 for i in 0..100 {
1959 b.set(i, true);
1960 }
1961
1962 assert_eq!(a, b);
1963 }
1964
1965 #[test]
test_from_bytes()1966 fn test_from_bytes() {
1967 let bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
1968 let str = concat!("10110110", "00000000", "11111111");
1969 assert_eq!(format!("{:?}", bit_vec), str);
1970 }
1971
1972 #[test]
test_to_bytes()1973 fn test_to_bytes() {
1974 let mut bv = BitVec::from_elem(3, true);
1975 bv.set(1, false);
1976 assert_eq!(bv.to_bytes(), [0b10100000]);
1977
1978 let mut bv = BitVec::from_elem(9, false);
1979 bv.set(2, true);
1980 bv.set(8, true);
1981 assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
1982 }
1983
1984 #[test]
test_from_bools()1985 fn test_from_bools() {
1986 let bools = vec![true, false, true, true];
1987 let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
1988 assert_eq!(format!("{:?}", bit_vec), "1011");
1989 }
1990
1991 #[test]
test_to_bools()1992 fn test_to_bools() {
1993 let bools = vec![false, false, true, false, false, true, true, false];
1994 assert_eq!(BitVec::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
1995 }
1996
1997 #[test]
test_bit_vec_iterator()1998 fn test_bit_vec_iterator() {
1999 let bools = vec![true, false, true, true];
2000 let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
2001
2002 assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), bools);
2003
2004 let long: Vec<_> = (0..10000).map(|i| i % 2 == 0).collect();
2005 let bit_vec: BitVec = long.iter().map(|n| *n).collect();
2006 assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), long)
2007 }
2008
2009 #[test]
test_small_difference()2010 fn test_small_difference() {
2011 let mut b1 = BitVec::from_elem(3, false);
2012 let mut b2 = BitVec::from_elem(3, false);
2013 b1.set(0, true);
2014 b1.set(1, true);
2015 b2.set(1, true);
2016 b2.set(2, true);
2017 assert!(b1.difference(&b2));
2018 assert!(b1[0]);
2019 assert!(!b1[1]);
2020 assert!(!b1[2]);
2021 }
2022
2023 #[test]
test_big_difference()2024 fn test_big_difference() {
2025 let mut b1 = BitVec::from_elem(100, false);
2026 let mut b2 = BitVec::from_elem(100, false);
2027 b1.set(0, true);
2028 b1.set(40, true);
2029 b2.set(40, true);
2030 b2.set(80, true);
2031 assert!(b1.difference(&b2));
2032 assert!(b1[0]);
2033 assert!(!b1[40]);
2034 assert!(!b1[80]);
2035 }
2036
2037 #[test]
test_small_xor()2038 fn test_small_xor() {
2039 let mut a = BitVec::from_bytes(&[0b0011]);
2040 let b = BitVec::from_bytes(&[0b0101]);
2041 let c = BitVec::from_bytes(&[0b0110]);
2042 assert!(a.xor(&b));
2043 assert_eq!(a,c);
2044 }
2045
2046 #[test]
test_small_xnor()2047 fn test_small_xnor() {
2048 let mut a = BitVec::from_bytes(&[0b0011]);
2049 let b = BitVec::from_bytes(&[0b1111_0101]);
2050 let c = BitVec::from_bytes(&[0b1001]);
2051 assert!(a.xnor(&b));
2052 assert_eq!(a,c);
2053 }
2054
2055 #[test]
test_small_nand()2056 fn test_small_nand() {
2057 let mut a = BitVec::from_bytes(&[0b1111_0011]);
2058 let b = BitVec::from_bytes(&[0b1111_0101]);
2059 let c = BitVec::from_bytes(&[0b1110]);
2060 assert!(a.nand(&b));
2061 assert_eq!(a,c);
2062 }
2063
2064 #[test]
test_small_nor()2065 fn test_small_nor() {
2066 let mut a = BitVec::from_bytes(&[0b0011]);
2067 let b = BitVec::from_bytes(&[0b1111_0101]);
2068 let c = BitVec::from_bytes(&[0b1000]);
2069 assert!(a.nor(&b));
2070 assert_eq!(a,c);
2071 }
2072
2073 #[test]
test_big_xor()2074 fn test_big_xor() {
2075 let mut a = BitVec::from_bytes(&[ // 88 bits
2076 0, 0, 0b00010100, 0,
2077 0, 0, 0, 0b00110100,
2078 0, 0, 0]);
2079 let b = BitVec::from_bytes(&[ // 88 bits
2080 0, 0, 0b00010100, 0,
2081 0, 0, 0, 0,
2082 0, 0, 0b00110100]);
2083 let c = BitVec::from_bytes(&[ // 88 bits
2084 0, 0, 0, 0,
2085 0, 0, 0, 0b00110100,
2086 0, 0, 0b00110100]);
2087 assert!(a.xor(&b));
2088 assert_eq!(a,c);
2089 }
2090
2091 #[test]
test_big_xnor()2092 fn test_big_xnor() {
2093 let mut a = BitVec::from_bytes(&[ // 88 bits
2094 0, 0, 0b00010100, 0,
2095 0, 0, 0, 0b00110100,
2096 0, 0, 0]);
2097 let b = BitVec::from_bytes(&[ // 88 bits
2098 0, 0, 0b00010100, 0,
2099 0, 0, 0, 0,
2100 0, 0, 0b00110100]);
2101 let c = BitVec::from_bytes(&[ // 88 bits
2102 !0, !0, !0, !0,
2103 !0, !0, !0, !0b00110100,
2104 !0, !0, !0b00110100]);
2105 assert!(a.xnor(&b));
2106 assert_eq!(a,c);
2107 }
2108
2109 #[test]
test_small_clear()2110 fn test_small_clear() {
2111 let mut b = BitVec::from_elem(14, true);
2112 assert!(!b.none() && b.all());
2113 b.clear();
2114 assert!(b.none() && !b.all());
2115 }
2116
2117 #[test]
test_big_clear()2118 fn test_big_clear() {
2119 let mut b = BitVec::from_elem(140, true);
2120 assert!(!b.none() && b.all());
2121 b.clear();
2122 assert!(b.none() && !b.all());
2123 }
2124
2125 #[test]
test_bit_vec_lt()2126 fn test_bit_vec_lt() {
2127 let mut a = BitVec::from_elem(5, false);
2128 let mut b = BitVec::from_elem(5, false);
2129
2130 assert!(!(a < b) && !(b < a));
2131 b.set(2, true);
2132 assert!(a < b);
2133 a.set(3, true);
2134 assert!(a < b);
2135 a.set(2, true);
2136 assert!(!(a < b) && b < a);
2137 b.set(0, true);
2138 assert!(a < b);
2139 }
2140
2141 #[test]
test_ord()2142 fn test_ord() {
2143 let mut a = BitVec::from_elem(5, false);
2144 let mut b = BitVec::from_elem(5, false);
2145
2146 assert!(a <= b && a >= b);
2147 a.set(1, true);
2148 assert!(a > b && a >= b);
2149 assert!(b < a && b <= a);
2150 b.set(1, true);
2151 b.set(2, true);
2152 assert!(b > a && b >= a);
2153 assert!(a < b && a <= b);
2154 }
2155
2156 #[test]
test_small_bit_vec_tests()2157 fn test_small_bit_vec_tests() {
2158 let v = BitVec::from_bytes(&[0]);
2159 assert!(!v.all());
2160 assert!(!v.any());
2161 assert!(v.none());
2162
2163 let v = BitVec::from_bytes(&[0b00010100]);
2164 assert!(!v.all());
2165 assert!(v.any());
2166 assert!(!v.none());
2167
2168 let v = BitVec::from_bytes(&[0xFF]);
2169 assert!(v.all());
2170 assert!(v.any());
2171 assert!(!v.none());
2172 }
2173
2174 #[test]
test_big_bit_vec_tests()2175 fn test_big_bit_vec_tests() {
2176 let v = BitVec::from_bytes(&[ // 88 bits
2177 0, 0, 0, 0,
2178 0, 0, 0, 0,
2179 0, 0, 0]);
2180 assert!(!v.all());
2181 assert!(!v.any());
2182 assert!(v.none());
2183
2184 let v = BitVec::from_bytes(&[ // 88 bits
2185 0, 0, 0b00010100, 0,
2186 0, 0, 0, 0b00110100,
2187 0, 0, 0]);
2188 assert!(!v.all());
2189 assert!(v.any());
2190 assert!(!v.none());
2191
2192 let v = BitVec::from_bytes(&[ // 88 bits
2193 0xFF, 0xFF, 0xFF, 0xFF,
2194 0xFF, 0xFF, 0xFF, 0xFF,
2195 0xFF, 0xFF, 0xFF]);
2196 assert!(v.all());
2197 assert!(v.any());
2198 assert!(!v.none());
2199 }
2200
2201 #[test]
test_bit_vec_push_pop()2202 fn test_bit_vec_push_pop() {
2203 let mut s = BitVec::from_elem(5 * U32_BITS - 2, false);
2204 assert_eq!(s.len(), 5 * U32_BITS - 2);
2205 assert_eq!(s[5 * U32_BITS - 3], false);
2206 s.push(true);
2207 s.push(true);
2208 assert_eq!(s[5 * U32_BITS - 2], true);
2209 assert_eq!(s[5 * U32_BITS - 1], true);
2210 // Here the internal vector will need to be extended
2211 s.push(false);
2212 assert_eq!(s[5 * U32_BITS], false);
2213 s.push(false);
2214 assert_eq!(s[5 * U32_BITS + 1], false);
2215 assert_eq!(s.len(), 5 * U32_BITS + 2);
2216 // Pop it all off
2217 assert_eq!(s.pop(), Some(false));
2218 assert_eq!(s.pop(), Some(false));
2219 assert_eq!(s.pop(), Some(true));
2220 assert_eq!(s.pop(), Some(true));
2221 assert_eq!(s.len(), 5 * U32_BITS - 2);
2222 }
2223
2224 #[test]
test_bit_vec_truncate()2225 fn test_bit_vec_truncate() {
2226 let mut s = BitVec::from_elem(5 * U32_BITS, true);
2227
2228 assert_eq!(s, BitVec::from_elem(5 * U32_BITS, true));
2229 assert_eq!(s.len(), 5 * U32_BITS);
2230 s.truncate(4 * U32_BITS);
2231 assert_eq!(s, BitVec::from_elem(4 * U32_BITS, true));
2232 assert_eq!(s.len(), 4 * U32_BITS);
2233 // Truncating to a size > s.len() should be a noop
2234 s.truncate(5 * U32_BITS);
2235 assert_eq!(s, BitVec::from_elem(4 * U32_BITS, true));
2236 assert_eq!(s.len(), 4 * U32_BITS);
2237 s.truncate(3 * U32_BITS - 10);
2238 assert_eq!(s, BitVec::from_elem(3 * U32_BITS - 10, true));
2239 assert_eq!(s.len(), 3 * U32_BITS - 10);
2240 s.truncate(0);
2241 assert_eq!(s, BitVec::from_elem(0, true));
2242 assert_eq!(s.len(), 0);
2243 }
2244
2245 #[test]
test_bit_vec_reserve()2246 fn test_bit_vec_reserve() {
2247 let mut s = BitVec::from_elem(5 * U32_BITS, true);
2248 // Check capacity
2249 assert!(s.capacity() >= 5 * U32_BITS);
2250 s.reserve(2 * U32_BITS);
2251 assert!(s.capacity() >= 7 * U32_BITS);
2252 s.reserve(7 * U32_BITS);
2253 assert!(s.capacity() >= 12 * U32_BITS);
2254 s.reserve_exact(7 * U32_BITS);
2255 assert!(s.capacity() >= 12 * U32_BITS);
2256 s.reserve(7 * U32_BITS + 1);
2257 assert!(s.capacity() >= 12 * U32_BITS + 1);
2258 // Check that length hasn't changed
2259 assert_eq!(s.len(), 5 * U32_BITS);
2260 s.push(true);
2261 s.push(false);
2262 s.push(true);
2263 assert_eq!(s[5 * U32_BITS - 1], true);
2264 assert_eq!(s[5 * U32_BITS - 0], true);
2265 assert_eq!(s[5 * U32_BITS + 1], false);
2266 assert_eq!(s[5 * U32_BITS + 2], true);
2267 }
2268
2269 #[test]
test_bit_vec_grow()2270 fn test_bit_vec_grow() {
2271 let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
2272 bit_vec.grow(32, true);
2273 assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2274 0xFF, 0xFF, 0xFF, 0xFF]));
2275 bit_vec.grow(64, false);
2276 assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2277 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
2278 bit_vec.grow(16, true);
2279 assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
2280 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
2281 }
2282
2283 #[test]
test_bit_vec_extend()2284 fn test_bit_vec_extend() {
2285 let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2286 let ext = BitVec::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
2287 bit_vec.extend(ext.iter());
2288 assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111,
2289 0b01001001, 0b10010010, 0b10111101]));
2290 }
2291
2292 #[test]
test_bit_vec_append()2293 fn test_bit_vec_append() {
2294 // Append to BitVec that holds a multiple of U32_BITS bits
2295 let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011]);
2296 let mut b = BitVec::new();
2297 b.push(false);
2298 b.push(true);
2299 b.push(true);
2300
2301 a.append(&mut b);
2302
2303 assert_eq!(a.len(), 35);
2304 assert_eq!(b.len(), 0);
2305 assert!(b.capacity() >= 3);
2306
2307 assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
2308 false, false, false, true, false, false, true, false,
2309 true, false, false, true, false, false, true, false,
2310 false, false, true, true, false, false, true, true,
2311 false, true, true]));
2312
2313 // Append to arbitrary BitVec
2314 let mut a = BitVec::new();
2315 a.push(true);
2316 a.push(false);
2317
2318 let mut b = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
2319
2320 a.append(&mut b);
2321
2322 assert_eq!(a.len(), 42);
2323 assert_eq!(b.len(), 0);
2324 assert!(b.capacity() >= 40);
2325
2326 assert!(a.eq_vec(&[true, false, true, false, true, false, false, false,
2327 false, false, false, false, false, true, false, false,
2328 true, false, true, false, false, true, false, false,
2329 true, false, false, false, true, true, false, false,
2330 true, true, true, false, false, true, false, true,
2331 false, true]));
2332
2333 // Append to empty BitVec
2334 let mut a = BitVec::new();
2335 let mut b = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
2336
2337 a.append(&mut b);
2338
2339 assert_eq!(a.len(), 40);
2340 assert_eq!(b.len(), 0);
2341 assert!(b.capacity() >= 40);
2342
2343 assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
2344 false, false, false, true, false, false, true, false,
2345 true, false, false, true, false, false, true, false,
2346 false, false, true, true, false, false, true, true,
2347 true, false, false, true, false, true, false, true]));
2348
2349 // Append empty BitVec
2350 let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
2351 let mut b = BitVec::new();
2352
2353 a.append(&mut b);
2354
2355 assert_eq!(a.len(), 40);
2356 assert_eq!(b.len(), 0);
2357
2358 assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
2359 false, false, false, true, false, false, true, false,
2360 true, false, false, true, false, false, true, false,
2361 false, false, true, true, false, false, true, true,
2362 true, false, false, true, false, true, false, true]));
2363 }
2364
2365 #[test]
test_bit_vec_split_off()2366 fn test_bit_vec_split_off() {
2367 // Split at 0
2368 let mut a = BitVec::new();
2369 a.push(true);
2370 a.push(false);
2371 a.push(false);
2372 a.push(true);
2373
2374 let b = a.split_off(0);
2375
2376 assert_eq!(a.len(), 0);
2377 assert_eq!(b.len(), 4);
2378
2379 assert!(b.eq_vec(&[true, false, false, true]));
2380
2381 // Split at last bit
2382 a.truncate(0);
2383 a.push(true);
2384 a.push(false);
2385 a.push(false);
2386 a.push(true);
2387
2388 let b = a.split_off(4);
2389
2390 assert_eq!(a.len(), 4);
2391 assert_eq!(b.len(), 0);
2392
2393 assert!(a.eq_vec(&[true, false, false, true]));
2394
2395 // Split at block boundary
2396 let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b11110011]);
2397
2398 let b = a.split_off(32);
2399
2400 assert_eq!(a.len(), 32);
2401 assert_eq!(b.len(), 8);
2402
2403 assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
2404 false, false, false, true, false, false, true, false,
2405 true, false, false, true, false, false, true, false,
2406 false, false, true, true, false, false, true, true]));
2407 assert!(b.eq_vec(&[true, true, true, true, false, false, true, true]));
2408
2409 // Don't split at block boundary
2410 let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011,
2411 0b01101011, 0b10101101]);
2412
2413 let b = a.split_off(13);
2414
2415 assert_eq!(a.len(), 13);
2416 assert_eq!(b.len(), 35);
2417
2418 assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
2419 false, false, false, true, false]));
2420 assert!(b.eq_vec(&[false, true, false, true, false, false, true, false,
2421 false, true, false, false, false, true, true, false,
2422 false, true, true, false, true, true, false, true,
2423 false, true, true, true, false, true, false, true,
2424 true, false, true]));
2425 }
2426
2427 #[test]
test_into_iter()2428 fn test_into_iter() {
2429 let bools = vec![true, false, true, true];
2430 let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
2431 let mut iter = bit_vec.into_iter();
2432 assert_eq!(Some(true), iter.next());
2433 assert_eq!(Some(false), iter.next());
2434 assert_eq!(Some(true), iter.next());
2435 assert_eq!(Some(true), iter.next());
2436 assert_eq!(None, iter.next());
2437 assert_eq!(None, iter.next());
2438
2439 let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
2440 let mut iter = bit_vec.into_iter();
2441 assert_eq!(Some(true), iter.next_back());
2442 assert_eq!(Some(true), iter.next_back());
2443 assert_eq!(Some(false), iter.next_back());
2444 assert_eq!(Some(true), iter.next_back());
2445 assert_eq!(None, iter.next_back());
2446 assert_eq!(None, iter.next_back());
2447
2448 let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
2449 let mut iter = bit_vec.into_iter();
2450 assert_eq!(Some(true), iter.next_back());
2451 assert_eq!(Some(true), iter.next());
2452 assert_eq!(Some(false), iter.next());
2453 assert_eq!(Some(true), iter.next_back());
2454 assert_eq!(None, iter.next());
2455 assert_eq!(None, iter.next_back());
2456 }
2457
2458 #[test]
iter()2459 fn iter() {
2460 let b = BitVec::with_capacity(10);
2461 let _a: Iter = b.iter();
2462 }
2463
2464 #[cfg(feature="serde")]
2465 #[test]
test_serialization()2466 fn test_serialization() {
2467 let bit_vec: BitVec = BitVec::new();
2468 let serialized = serde_json::to_string(&bit_vec).unwrap();
2469 let unserialized: BitVec = serde_json::from_str(&serialized).unwrap();
2470 assert_eq!(bit_vec, unserialized);
2471
2472 let bools = vec![true, false, true, true];
2473 let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
2474 let serialized = serde_json::to_string(&bit_vec).unwrap();
2475 let unserialized = serde_json::from_str(&serialized).unwrap();
2476 assert_eq!(bit_vec, unserialized);
2477 }
2478 }
2479