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