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