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