1#![doc(html_root_url = "https://docs.rs/bit-vec/0.9.0/bit_vec/")]
86#![no_std]
87#![deny(clippy::shadow_reuse)]
88#![deny(clippy::shadow_same)]
89#![deny(clippy::shadow_unrelated)]
90#![warn(clippy::multiple_inherent_impl)]
91#![warn(clippy::multiple_crate_versions)]
92#![warn(clippy::single_match)]
93#![warn(clippy::missing_safety_doc)]
94
95#[cfg(any(test, feature = "std"))]
96#[macro_use]
97extern crate std;
98
99#[cfg(all(feature = "std", feature = "borsh"))]
100use std::borrow::ToOwned;
101#[cfg(all(feature = "std", feature = "miniserde"))]
102use std::boxed::Box;
103#[cfg(feature = "std")]
104use std::rc::Rc;
105#[cfg(feature = "std")]
106use std::string::String;
107#[cfg(feature = "std")]
108use std::vec::Vec;
109
110#[cfg(not(feature = "std"))]
111#[macro_use]
112extern crate alloc;
113#[cfg(all(not(feature = "std"), feature = "borsh"))]
114use alloc::borrow::ToOwned;
115#[cfg(all(not(feature = "std"), feature = "miniserde"))]
116use alloc::boxed::Box;
117#[cfg(not(feature = "std"))]
118use alloc::rc::Rc;
119#[cfg(not(feature = "std"))]
120use alloc::string::String;
121#[cfg(not(feature = "std"))]
122use alloc::vec::Vec;
123
124use core::error::Error;
125
126#[cfg(feature = "borsh")]
127extern crate borsh;
128#[cfg(feature = "miniserde")]
129extern crate miniserde;
130#[cfg(feature = "serde")]
131extern crate serde;
132
133mod util;
134
135use core::cell::RefCell;
136use core::cmp::Ordering;
137use core::fmt::Write;
138use core::iter::FromIterator;
139use core::ops::*;
140use core::{cmp, fmt, hash, iter, mem, slice};
141
142pub trait BitBlock:
144 Copy
145 + Add<Self, Output = Self>
146 + Sub<Self, Output = Self>
147 + Shl<usize, Output = Self>
148 + Shr<usize, Output = Self>
149 + Not<Output = Self>
150 + BitAnd<Self, Output = Self>
151 + BitOr<Self, Output = Self>
152 + BitXor<Self, Output = Self>
153 + Rem<Self, Output = Self>
154 + BitOrAssign<Self>
155 + Eq
156 + Ord
157 + hash::Hash
158{
159 fn bits() -> usize;
161 #[inline]
163 fn bytes() -> usize {
164 Self::bits() / 8
165 }
166 fn from_byte(byte: u8) -> Self;
168 fn count_ones(self) -> usize;
170 fn count_zeros(self) -> usize {
172 Self::bits() - self.count_ones()
173 }
174 fn zero() -> Self;
176 fn one() -> Self;
178}
179
180macro_rules! bit_block_impl {
181 ($(($t: ident, $size: expr)),*) => ($(
182 impl BitBlock for $t {
183 #[inline]
184 fn bits() -> usize { $size }
185 #[inline]
186 fn from_byte(byte: u8) -> Self { $t::from(byte) }
187 #[inline]
188 fn count_ones(self) -> usize { self.count_ones() as usize }
189 #[inline]
190 fn count_zeros(self) -> usize { self.count_zeros() as usize }
191 #[inline]
192 fn one() -> Self { 1 }
193 #[inline]
194 fn zero() -> Self { 0 }
195 }
196 )*)
197}
198
199bit_block_impl! {
200 (u8, 8),
201 (u16, 16),
202 (u32, 32),
203 (u64, 64),
204 (usize, core::mem::size_of::<usize>() * 8)
205}
206
207#[cfg_attr(feature = "serde", derive(serde::Serialize))]
235#[cfg_attr(feature = "borsh", derive(borsh::BorshSerialize))]
236#[cfg_attr(feature = "miniserde", derive(miniserde::Serialize))]
237pub struct BitVec<B = u32> {
238 storage: Vec<B>,
240 nbits: usize,
242}
243
244#[cfg(any(feature = "serde", feature = "borsh", feature = "miniserde"))]
245#[cfg_attr(feature = "serde", derive(serde::Deserialize))]
246#[cfg_attr(feature = "borsh", derive(borsh::BorshDeserialize))]
247#[cfg_attr(feature = "miniserde", derive(miniserde::Deserialize))]
248struct UncheckedBitVec<B = u32> {
249 storage: Vec<B>,
250 nbits: usize,
251}
252
253#[cfg(feature = "serde")]
254impl<'de, B: BitBlock> serde::Deserialize<'de> for BitVec<B>
255where
256 B: serde::Deserialize<'de>,
257{
258 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
259 where
260 D: serde::Deserializer<'de>,
261 {
262 use serde::de::Error;
263 UncheckedBitVec::<B>::deserialize(deserializer).and_then(|unchecked| {
264 let result = BitVec {
265 storage: unchecked.storage,
266 nbits: unchecked.nbits,
267 };
268 if !result.storage_len_matches_nbits() {
269 Err(D::Error::custom(DeserializeError::StorageLenMismatch))
270 } else if !result.is_last_block_fixed() {
271 Err(D::Error::custom(DeserializeError::TrailingBits))
272 } else {
273 Ok(result)
274 }
275 })
276 }
277}
278
279#[cfg(feature = "borsh")]
280impl<B: BitBlock> borsh::BorshDeserialize for BitVec<B>
281where
282 B: borsh::BorshDeserialize,
283{
284 fn deserialize_reader<R: borsh::io::Read>(reader: &mut R) -> borsh::io::Result<Self> {
285 UncheckedBitVec::<B>::deserialize_reader(reader).and_then(|unchecked| {
286 let result = BitVec {
287 storage: unchecked.storage,
288 nbits: unchecked.nbits,
289 };
290 if !result.storage_len_matches_nbits() {
291 Err(borsh::io::Error::other(
292 DeserializeError::StorageLenMismatch,
293 ))
294 } else if !result.is_last_block_fixed() {
295 Err(borsh::io::Error::other(DeserializeError::TrailingBits))
296 } else {
297 Ok(result)
298 }
299 })
300 }
301}
302
303#[cfg(feature = "miniserde")]
304miniserde::make_place!(Place);
305
306#[cfg(feature = "miniserde")]
307struct BitVecBuilder<'a, B> {
308 storage: Option<Vec<B>>,
309 nbits: Option<usize>,
310 out: &'a mut Option<BitVec<B>>,
311}
312
313#[cfg(feature = "miniserde")]
314impl<B: BitBlock> miniserde::de::Visitor for Place<BitVec<B>>
315where
316 B: miniserde::Deserialize,
317{
318 fn map(&mut self) -> miniserde::Result<Box<dyn miniserde::de::Map + '_>> {
319 Ok(Box::new(BitVecBuilder {
320 storage: None,
321 nbits: None,
322 out: &mut self.out,
323 }))
324 }
325}
326
327#[cfg(feature = "miniserde")]
328impl<B: BitBlock> miniserde::de::Map for BitVecBuilder<'_, B>
329where
330 B: miniserde::Deserialize,
331{
332 fn key(&mut self, k: &str) -> miniserde::Result<&mut dyn miniserde::de::Visitor> {
333 match k {
334 "storage" => Ok(miniserde::Deserialize::begin(&mut self.storage)),
335 "nbits" => Ok(miniserde::Deserialize::begin(&mut self.nbits)),
336 _ => Ok(<dyn miniserde::de::Visitor>::ignore()),
337 }
338 }
339
340 fn finish(&mut self) -> miniserde::Result<()> {
341 let storage = self.storage.take().ok_or(miniserde::Error)?;
342 let nbits = self.nbits.take().ok_or(miniserde::Error)?;
343 let result = BitVec { storage, nbits };
344 if !result.storage_len_matches_nbits() || !result.is_last_block_fixed() {
345 Err(miniserde::Error)
346 } else {
347 *self.out = Some(result);
348 Ok(())
349 }
350 }
351}
352
353#[cfg(feature = "miniserde")]
354impl<B: BitBlock> miniserde::Deserialize for BitVec<B>
355where
356 B: miniserde::Deserialize,
357{
358 fn begin(out: &mut Option<Self>) -> &mut dyn miniserde::de::Visitor {
359 Place::new(out)
360 }
361}
362
363#[derive(Debug)]
364pub enum DeserializeError {
365 StorageLenMismatch,
366 TrailingBits,
367}
368
369impl core::fmt::Display for DeserializeError {
370 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
371 f.write_str(self.simple_description())
372 }
373}
374
375#[cfg(feature = "borsh")]
376impl From<DeserializeError> for String {
377 fn from(value: DeserializeError) -> Self {
378 value.simple_description().to_owned()
379 }
380}
381
382impl Error for DeserializeError {}
383
384impl DeserializeError {
385 fn simple_description(&self) -> &str {
386 match self {
387 DeserializeError::TrailingBits => "some out of bounds trailing bits are set",
388 DeserializeError::StorageLenMismatch => "nbits and storage length isnt same",
389 }
390 }
391}
392
393impl<B: BitBlock> Index<usize> for BitVec<B> {
395 type Output = bool;
396
397 #[inline]
398 fn index(&self, i: usize) -> &bool {
399 if self.get(i).expect("index out of bounds") {
400 &true
401 } else {
402 &false
403 }
404 }
405}
406
407fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
409 if bits % B::bits() == 0 {
418 bits / B::bits()
419 } else {
420 bits / B::bits() + 1
421 }
422}
423
424fn mask_for_bits<B: BitBlock>(bits: usize) -> B {
426 (!B::zero()) >> ((B::bits() - bits % B::bits()) % B::bits())
428}
429
430impl BitVec<u32> {
431 #[inline]
440 pub fn new() -> Self {
441 Default::default()
442 }
443
444 #[inline]
459 pub fn from_elem(len: usize, bit: bool) -> Self {
460 BitVec::<u32>::from_elem_general(len, bit)
461 }
462
463 #[inline]
471 pub fn with_capacity(capacity: usize) -> Self {
472 BitVec::<u32>::with_capacity_general(capacity)
473 }
474
475 pub fn from_bytes(bytes: &[u8]) -> Self {
491 BitVec::<u32>::from_bytes_general(bytes)
492 }
493
494 #[inline]
506 pub fn from_fn<F>(len: usize, f: F) -> Self
507 where
508 F: FnMut(usize) -> bool,
509 {
510 BitVec::<u32>::from_fn_general(len, f)
511 }
512}
513
514impl<B: BitBlock> BitVec<B> {
515 #[inline]
524 pub fn new_general() -> Self {
525 Default::default()
526 }
527
528 #[inline]
543 pub fn from_elem_general(len: usize, bit: bool) -> Self {
544 let nblocks = blocks_for_bits::<B>(len);
545 let mut bit_vec = BitVec {
546 storage: vec![if bit { !B::zero() } else { B::zero() }; nblocks],
547 nbits: len,
548 };
549 bit_vec.fix_last_block();
550 bit_vec
551 }
552
553 #[inline]
561 pub fn with_capacity_general(capacity: usize) -> Self {
562 BitVec {
563 storage: Vec::with_capacity(blocks_for_bits::<B>(capacity)),
564 nbits: 0,
565 }
566 }
567
568 pub fn from_bytes_general(bytes: &[u8]) -> Self {
584 let len = bytes
585 .len()
586 .checked_mul(u8::bits())
587 .expect("capacity overflow");
588 let mut bit_vec = BitVec::with_capacity_general(len);
589 let complete_words = bytes.len() / B::bytes();
590 let extra_bytes = bytes.len() % B::bytes();
591
592 bit_vec.nbits = len;
593
594 for i in 0..complete_words {
595 let mut accumulator = B::zero();
596 for idx in 0..B::bytes() {
597 accumulator |=
598 B::from_byte(util::reverse_bits(bytes[i * B::bytes() + idx])) << (idx * 8)
599 }
600 bit_vec.storage.push(accumulator);
601 }
602
603 if extra_bytes > 0 {
604 let mut last_word = B::zero();
605 for (i, &byte) in bytes[complete_words * B::bytes()..].iter().enumerate() {
606 last_word |= B::from_byte(util::reverse_bits(byte)) << (i * 8);
607 }
608 bit_vec.storage.push(last_word);
609 }
610
611 bit_vec
612 }
613
614 #[inline]
626 pub fn from_fn_general<F>(len: usize, mut f: F) -> Self
627 where
628 F: FnMut(usize) -> bool,
629 {
630 let mut bit_vec = BitVec::from_elem_general(len, false);
631 for i in 0..len {
632 bit_vec.set(i, f(i));
633 }
634 bit_vec
635 }
636
637 #[inline]
641 fn process<F>(&mut self, that: &BitVec<B>, mut op: F, tail: bool) -> bool
642 where
643 F: FnMut(B, B) -> B,
644 {
645 assert_eq!(self.len(), that.len());
646 debug_assert_eq!(self.storage.len(), that.storage.len());
647 let mut changed_bits = B::zero();
648 let extra_bits = self.nbits % B::bits();
649 let desired_tail_len = if tail && extra_bits != 0 { 1 } else { 0 };
650 let full_blocks = self.storage.len().saturating_sub(desired_tail_len);
651 let (a_head, a_tail) = self.storage.split_at_mut(full_blocks);
652 let (b_head, b_tail) = that.storage.split_at(full_blocks);
653 for (a, b) in a_head.iter_mut().zip(b_head.iter()) {
654 let w = op(*a, *b);
655 changed_bits |= *a ^ w;
656 *a = w;
657 }
658 if a_tail.len() == 1 {
659 let mask = (B::one() << extra_bits) - B::one();
660 let w = op(a_tail[0], b_tail[0]) & mask;
661 changed_bits |= a_tail[0] ^ w;
662 a_tail[0] = w;
663 }
664 changed_bits != B::zero()
665 }
666
667 #[inline]
669 pub fn blocks(&self) -> Blocks<'_, B> {
670 Blocks {
672 iter: self.storage.iter(),
673 }
674 }
675
676 #[inline]
680 pub fn storage(&self) -> &[B] {
681 &self.storage
682 }
683
684 #[inline]
691 pub unsafe fn storage_mut(&mut self) -> &mut Vec<B> {
692 &mut self.storage
693 }
694
695 #[inline]
697 fn last_block_with_mask(&self) -> Option<(B, B)> {
698 let extra_bits = self.len() % B::bits();
699 if extra_bits > 0 {
700 let mask = (B::one() << extra_bits) - B::one();
701 let storage_len = self.storage.len();
702 Some((self.storage[storage_len - 1], mask))
703 } else {
704 None
705 }
706 }
707
708 #[inline]
710 fn last_block_mut_with_mask(&mut self) -> Option<(&mut B, B)> {
711 let extra_bits = self.len() % B::bits();
712 if extra_bits > 0 {
713 let mask = (B::one() << extra_bits) - B::one();
714 let storage_len = self.storage.len();
715 Some((&mut self.storage[storage_len - 1], mask))
716 } else {
717 None
718 }
719 }
720
721 fn fix_last_block(&mut self) {
724 if let Some((last_block, used_bits)) = self.last_block_mut_with_mask() {
725 *last_block = *last_block & used_bits;
726 }
727 }
728
729 fn is_last_block_fixed(&self) -> bool {
731 if let Some((last_block, used_bits)) = self.last_block_with_mask() {
732 last_block & !used_bits == B::zero()
733 } else {
734 true
735 }
736 }
737
738 fn storage_len_matches_nbits(&self) -> bool {
740 self.storage.len() == blocks_for_bits::<B>(self.nbits)
741 }
742
743 #[inline]
751 fn ensure_invariant(&self) {
752 if cfg!(test) {
753 debug_assert!(self.storage_len_matches_nbits());
754 debug_assert!(self.is_last_block_fixed());
755 }
756 }
757
758 #[inline]
774 pub fn get(&self, i: usize) -> Option<bool> {
775 self.ensure_invariant();
776 if i >= self.nbits {
777 return None;
778 }
779 let w = i / B::bits();
780 let b = i % B::bits();
781 self.storage
782 .get(w)
783 .map(|&block| (block & (B::one() << b)) != B::zero())
784 }
785
786 #[inline]
810 pub unsafe fn get_unchecked(&self, i: usize) -> bool {
811 self.ensure_invariant();
812 let w = i / B::bits();
813 let b = i % B::bits();
814 let block = *self.storage.get_unchecked(w);
815 block & (B::one() << b) != B::zero()
816 }
817
818 #[inline]
832 pub fn get_mut(&mut self, index: usize) -> Option<MutBorrowedBit<'_, B>> {
833 self.get(index).map(move |value| MutBorrowedBit {
834 vec: Rc::new(RefCell::new(self)),
835 index,
836 #[cfg(debug_assertions)]
837 old_value: value,
838 new_value: value,
839 })
840 }
841
842 #[inline]
862 pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> MutBorrowedBit<'_, B> {
863 let value = self.get_unchecked(index);
864 MutBorrowedBit {
865 #[cfg(debug_assertions)]
866 old_value: value,
867 new_value: value,
868 vec: Rc::new(RefCell::new(self)),
869 index,
870 }
871 }
872
873 #[inline]
889 pub fn set(&mut self, i: usize, x: bool) {
890 self.ensure_invariant();
891 assert!(
892 i < self.nbits,
893 "index out of bounds: {:?} >= {:?}",
894 i,
895 self.nbits
896 );
897 let w = i / B::bits();
898 let b = i % B::bits();
899 let flag = B::one() << b;
900 let val = if x {
901 self.storage[w] | flag
902 } else {
903 self.storage[w] & !flag
904 };
905 self.storage[w] = val;
906 }
907
908 #[inline]
923 #[deprecated(since = "0.9.0", note = "please use `.fill(true)` instead")]
924 pub fn set_all(&mut self) {
925 self.ensure_invariant();
926 for w in &mut self.storage {
927 *w = !B::zero();
928 }
929 self.fix_last_block();
930 }
931
932 #[inline]
947 pub fn negate(&mut self) {
948 self.ensure_invariant();
949 for w in &mut self.storage {
950 *w = !*w;
951 }
952 self.fix_last_block();
953 }
954
955 #[deprecated(since = "0.7.0", note = "Please use the 'or' function instead")]
981 #[inline]
982 pub fn union(&mut self, other: &Self) -> bool {
983 self.or(other)
984 }
985
986 #[deprecated(since = "0.7.0", note = "Please use the 'and' function instead")]
1012 #[inline]
1013 pub fn intersect(&mut self, other: &Self) -> bool {
1014 self.and(other)
1015 }
1016
1017 #[inline]
1042 pub fn or(&mut self, other: &Self) -> bool {
1043 self.ensure_invariant();
1044 debug_assert!(other.is_last_block_fixed());
1045 let result = self.process(other, |w1, w2| w1 | w2, false);
1046 debug_assert!(self.is_last_block_fixed());
1047 result
1048 }
1049
1050 #[inline]
1075 pub fn and(&mut self, other: &Self) -> bool {
1076 self.ensure_invariant();
1077 debug_assert!(other.is_last_block_fixed());
1078 self.process(other, |w1, w2| w1 & w2, false)
1079 }
1080
1081 #[inline]
1114 pub fn difference(&mut self, other: &Self) -> bool {
1115 self.ensure_invariant();
1116 debug_assert!(other.is_last_block_fixed());
1117 self.process(other, |w1, w2| w1 & !w2, false)
1118 }
1119
1120 #[inline]
1145 pub fn xor(&mut self, other: &Self) -> bool {
1146 self.ensure_invariant();
1147 debug_assert!(other.is_last_block_fixed());
1148 let result = self.process(other, |w1, w2| w1 ^ w2, false);
1149 debug_assert!(self.is_last_block_fixed());
1150 result
1151 }
1152
1153 #[inline]
1178 pub fn nand(&mut self, other: &Self) -> bool {
1179 self.ensure_invariant();
1180 debug_assert!(other.is_last_block_fixed());
1181 let result = self.process(other, |w1, w2| !(w1 & w2), true);
1182 debug_assert!(self.is_last_block_fixed());
1183 result
1184 }
1185
1186 #[inline]
1211 pub fn nor(&mut self, other: &Self) -> bool {
1212 self.ensure_invariant();
1213 debug_assert!(other.is_last_block_fixed());
1214 let result = self.process(other, |w1, w2| !(w1 | w2), true);
1215 debug_assert!(self.is_last_block_fixed());
1216 result
1217 }
1218
1219 #[inline]
1244 pub fn xnor(&mut self, other: &Self) -> bool {
1245 self.ensure_invariant();
1246 debug_assert!(other.is_last_block_fixed());
1247 let result = self.process(other, |w1, w2| !(w1 ^ w2), true);
1248 debug_assert!(self.is_last_block_fixed());
1249 result
1250 }
1251
1252 #[inline]
1266 pub fn all(&self) -> bool {
1267 self.ensure_invariant();
1268 let mut last_word = !B::zero();
1269 self.blocks().all(|elem| {
1271 let tmp = last_word;
1272 last_word = elem;
1273 tmp == !B::zero()
1274 }) && (last_word == mask_for_bits(self.nbits))
1276 }
1277
1278 #[inline]
1295 pub fn count_ones(&self) -> u64 {
1296 self.ensure_invariant();
1297 self.blocks().map(|elem| elem.count_ones() as u64).sum()
1299 }
1300
1301 #[inline]
1318 pub fn count_zeros(&self) -> u64 {
1319 self.ensure_invariant();
1320 let extra_zeros = (B::bits() - (self.len() % B::bits())) % B::bits();
1322 self.blocks()
1323 .map(|elem| elem.count_zeros() as u64)
1324 .sum::<u64>()
1325 - extra_zeros as u64
1326 }
1327
1328 #[inline]
1339 pub fn iter(&self) -> Iter<'_, B> {
1340 self.ensure_invariant();
1341 Iter {
1342 bit_vec: self,
1343 range: 0..self.nbits,
1344 }
1345 }
1346
1347 #[inline]
1363 pub fn iter_mut(&mut self) -> IterMut<'_, B> {
1364 self.ensure_invariant();
1365 let nbits = self.nbits;
1366 IterMut {
1367 vec: Rc::new(RefCell::new(self)),
1368 range: 0..nbits,
1369 }
1370 }
1371
1372 pub fn append(&mut self, other: &mut Self) {
1390 self.ensure_invariant();
1391 debug_assert!(other.is_last_block_fixed());
1392
1393 let b = self.len() % B::bits();
1394 let o = other.len() % B::bits();
1395 let will_overflow = (b + o > B::bits()) || (o == 0 && b != 0);
1396
1397 self.nbits += other.len();
1398 other.nbits = 0;
1399
1400 if b == 0 {
1401 self.storage.append(&mut other.storage);
1402 } else {
1403 self.storage.reserve(other.storage.len());
1404
1405 for block in other.storage.drain(..) {
1406 {
1407 let last = self.storage.last_mut().unwrap();
1408 *last |= block << b;
1409 }
1410 self.storage.push(block >> (B::bits() - b));
1411 }
1412
1413 if !will_overflow {
1415 self.storage.pop();
1416 }
1417 }
1418 }
1419
1420 pub fn split_off(&mut self, at: usize) -> Self {
1445 self.ensure_invariant();
1446 assert!(at <= self.len(), "`at` out of bounds");
1447
1448 let mut other = BitVec::<B>::default();
1449
1450 if at == 0 {
1451 mem::swap(self, &mut other);
1452 return other;
1453 } else if at == self.len() {
1454 return other;
1455 }
1456
1457 let w = at / B::bits();
1458 let b = at % B::bits();
1459 other.nbits = self.nbits - at;
1460 self.nbits = at;
1461 if b == 0 {
1462 other.storage = self.storage.split_off(w);
1464 } else {
1465 let original_storage_len = self.storage.len();
1466 other.storage.reserve(original_storage_len - w);
1467
1468 {
1469 let mut iter = self.storage[w..].iter();
1470 let mut last = *iter.next().unwrap();
1471 for &cur in iter {
1472 other.storage.push((last >> b) | (cur << (B::bits() - b)));
1473 last = cur;
1474 }
1475 if original_storage_len - w <= blocks_for_bits::<B>(other.nbits) {
1477 other.storage.push(last >> b);
1478 }
1479 }
1480
1481 self.storage.truncate(w + 1);
1482 self.fix_last_block();
1483 }
1484
1485 other
1486 }
1487
1488 #[inline]
1502 pub fn none(&self) -> bool {
1503 self.blocks().all(|w| w == B::zero())
1504 }
1505
1506 #[inline]
1520 pub fn any(&self) -> bool {
1521 !self.none()
1522 }
1523
1524 pub fn to_bytes(&self) -> Vec<u8> {
1546 self.ensure_invariant();
1547
1548 let len = self.nbits / 8 + if self.nbits % 8 == 0 { 0 } else { 1 };
1549 let mut result = Vec::with_capacity(len);
1550
1551 for byte_idx in 0..len {
1552 let mut byte = 0u8;
1553 for bit_idx in 0..8 {
1554 let offset = byte_idx * 8 + bit_idx;
1555 if offset < self.nbits && self[offset] {
1556 byte |= 1 << bit_idx;
1557 }
1558 }
1559 result.push(util::reverse_bits(byte));
1560 }
1561
1562 result
1563 }
1564
1565 #[inline]
1583 pub fn eq_vec(&self, v: &[bool]) -> bool {
1584 assert_eq!(self.nbits, v.len());
1585 self.iter().zip(v.iter().cloned()).all(|(b1, b2)| b1 == b2)
1586 }
1587
1588 #[inline]
1603 pub fn truncate(&mut self, len: usize) {
1604 self.ensure_invariant();
1605 if len < self.len() {
1606 self.nbits = len;
1607 self.storage.truncate(blocks_for_bits::<B>(len));
1609 self.fix_last_block();
1610 }
1611 }
1612
1613 #[inline]
1631 pub fn reserve(&mut self, additional: usize) {
1632 let desired_cap = self
1633 .len()
1634 .checked_add(additional)
1635 .expect("capacity overflow");
1636 let storage_len = self.storage.len();
1637 if desired_cap > self.capacity() {
1638 self.storage
1639 .reserve(blocks_for_bits::<B>(desired_cap) - storage_len);
1640 }
1641 }
1642
1643 #[inline]
1665 pub fn reserve_exact(&mut self, additional: usize) {
1666 let desired_cap = self
1667 .len()
1668 .checked_add(additional)
1669 .expect("capacity overflow");
1670 let storage_len = self.storage.len();
1671 if desired_cap > self.capacity() {
1672 self.storage
1673 .reserve_exact(blocks_for_bits::<B>(desired_cap) - storage_len);
1674 }
1675 }
1676
1677 #[inline]
1690 pub fn capacity(&self) -> usize {
1691 self.storage.capacity().saturating_mul(B::bits())
1692 }
1693
1694 pub fn grow(&mut self, n: usize, value: bool) {
1711 self.ensure_invariant();
1712
1713 let new_nbits = self.nbits.checked_add(n).expect("capacity overflow");
1718 let new_nblocks = blocks_for_bits::<B>(new_nbits);
1719 let full_value = if value { !B::zero() } else { B::zero() };
1720
1721 let num_cur_blocks = blocks_for_bits::<B>(self.nbits);
1723 if self.nbits % B::bits() > 0 {
1724 let mask = mask_for_bits::<B>(self.nbits);
1725 if value {
1726 let block = &mut self.storage[num_cur_blocks - 1];
1727 *block |= !mask;
1728 } else {
1729 }
1731 }
1732
1733 let stop_idx = cmp::min(self.storage.len(), new_nblocks);
1735 for idx in num_cur_blocks..stop_idx {
1736 self.storage[idx] = full_value;
1737 }
1738
1739 if new_nblocks > self.storage.len() {
1741 let to_add = new_nblocks - self.storage.len();
1742 self.storage.extend(iter::repeat_n(full_value, to_add));
1743 }
1744
1745 self.nbits = new_nbits;
1747
1748 self.fix_last_block();
1749 }
1750
1751 #[inline]
1764 pub fn pop(&mut self) -> Option<bool> {
1765 self.ensure_invariant();
1766
1767 if self.is_empty() {
1768 None
1769 } else {
1770 let i = self.nbits - 1;
1771 let ret = self[i];
1772 self.set(i, false);
1774 self.nbits = i;
1775 if self.nbits % B::bits() == 0 {
1776 self.storage.pop();
1778 }
1779 Some(ret)
1780 }
1781 }
1782
1783 #[inline]
1796 pub fn push(&mut self, elem: bool) {
1797 if self.nbits % B::bits() == 0 {
1798 self.storage.push(B::zero());
1799 }
1800 let insert_pos = self.nbits;
1801 self.nbits = self.nbits.checked_add(1).expect("Capacity overflow");
1802 self.set(insert_pos, elem);
1803 }
1804
1805 #[inline]
1807 pub fn len(&self) -> usize {
1808 self.nbits
1809 }
1810
1811 #[inline]
1817 pub unsafe fn set_len(&mut self, len: usize) {
1818 self.nbits = len;
1819 }
1820
1821 #[inline]
1823 pub fn is_empty(&self) -> bool {
1824 self.len() == 0
1825 }
1826
1827 #[inline]
1829 #[deprecated(since = "0.9.0", note = "please use `.fill(false)` instead")]
1830 pub fn clear(&mut self) {
1831 self.ensure_invariant();
1832 for w in &mut self.storage {
1833 *w = B::zero();
1834 }
1835 }
1836
1837 #[inline]
1847 pub fn fill(&mut self, bit: bool) {
1848 self.ensure_invariant();
1849 let block = if bit { !B::zero() } else { B::zero() };
1850 for w in &mut self.storage {
1851 *w = block;
1852 }
1853 if bit {
1854 self.fix_last_block();
1855 }
1856 }
1857
1858 pub fn shrink_to_fit(&mut self) {
1865 self.storage.shrink_to_fit();
1866 }
1867
1868 pub fn insert(&mut self, at: usize, bit: bool) {
1893 assert!(
1894 at <= self.nbits,
1895 "insertion index (is {at}) should be <= len (is {nbits})",
1896 nbits = self.nbits
1897 );
1898 self.ensure_invariant();
1899
1900 let last_block_bits = self.nbits % B::bits();
1901 let block_at = at / B::bits(); let bit_at = at % B::bits(); if last_block_bits == 0 {
1905 self.storage.push(B::zero());
1906 }
1907
1908 self.nbits += 1;
1909
1910 let mut carry = self.storage[block_at] >> (B::bits() - 1);
1911 let lsbits_mask = (B::one() << bit_at) - B::one();
1912 let set_bit = if bit { B::one() } else { B::zero() } << bit_at;
1913 self.storage[block_at] = (self.storage[block_at] & lsbits_mask)
1914 | ((self.storage[block_at] & !lsbits_mask) << 1)
1915 | set_bit;
1916
1917 for block_ref in &mut self.storage[block_at + 1..] {
1918 let curr_carry = *block_ref >> (B::bits() - 1);
1919 *block_ref = *block_ref << 1 | carry;
1920 carry = curr_carry;
1921 }
1922 }
1923
1924 pub fn remove(&mut self, at: usize) -> bool {
1951 assert!(
1952 at < self.nbits,
1953 "removal index (is {at}) should be < len (is {nbits})",
1954 nbits = self.nbits
1955 );
1956 self.ensure_invariant();
1957
1958 self.nbits -= 1;
1959
1960 let last_block_bits = self.nbits % B::bits();
1961 let block_at = at / B::bits(); let bit_at = at % B::bits(); let lsbits_mask = (B::one() << bit_at) - B::one();
1965
1966 let mut carry = B::zero();
1967
1968 for block_ref in self.storage[block_at + 1..].iter_mut().rev() {
1969 let curr_carry = *block_ref & B::one();
1970 *block_ref = *block_ref >> 1 | (carry << (B::bits() - 1));
1971 carry = curr_carry;
1972 }
1973
1974 let result = (self.storage[block_at] >> bit_at) & B::one() == B::one();
1975
1976 self.storage[block_at] = (self.storage[block_at] & lsbits_mask)
1977 | ((self.storage[block_at] & (!lsbits_mask << 1)) >> 1)
1978 | carry << (B::bits() - 1);
1979
1980 if last_block_bits == 0 {
1981 self.storage.pop();
1982 }
1983
1984 result
1985 }
1986
1987 pub fn remove_all(&mut self) {
1995 self.storage.clear();
1996 self.nbits = 0;
1997 }
1998
1999 pub fn push_within_capacity(&mut self, bit: bool) -> Result<(), bool> {
2032 let len = self.len();
2033
2034 if len == self.capacity() {
2035 return Err(bit);
2036 }
2037
2038 let bits = B::bits();
2039
2040 if len % bits == 0 {
2041 self.storage.push(B::zero());
2042 }
2043
2044 let block_at = len / bits;
2045 let bit_at = len % bits;
2046 let flag = if bit { B::one() << bit_at } else { B::zero() };
2047
2048 self.nbits += 1;
2049
2050 self.storage[block_at] |= flag; self.ensure_invariant();
2053
2054 Ok(())
2055 }
2056}
2057
2058impl<B: BitBlock> Default for BitVec<B> {
2059 #[inline]
2060 fn default() -> Self {
2061 BitVec {
2062 storage: Vec::new(),
2063 nbits: 0,
2064 }
2065 }
2066}
2067
2068impl<B: BitBlock> FromIterator<bool> for BitVec<B> {
2069 #[inline]
2070 fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
2071 let mut ret: Self = Default::default();
2072 ret.extend(iter);
2073 ret
2074 }
2075}
2076
2077impl<B: BitBlock> Extend<bool> for BitVec<B> {
2078 #[inline]
2079 fn extend<I: IntoIterator<Item = bool>>(&mut self, iterable: I) {
2080 self.ensure_invariant();
2081 let iterator = iterable.into_iter();
2082 let (min, _) = iterator.size_hint();
2083 self.reserve(min);
2084 for element in iterator {
2085 self.push(element)
2086 }
2087 }
2088}
2089
2090impl<B: BitBlock> Clone for BitVec<B> {
2091 #[inline]
2092 fn clone(&self) -> Self {
2093 self.ensure_invariant();
2094 BitVec {
2095 storage: self.storage.clone(),
2096 nbits: self.nbits,
2097 }
2098 }
2099
2100 #[inline]
2101 fn clone_from(&mut self, source: &Self) {
2102 debug_assert!(source.is_last_block_fixed());
2103 self.nbits = source.nbits;
2104 self.storage.clone_from(&source.storage);
2105 }
2106}
2107
2108impl<B: BitBlock> PartialOrd for BitVec<B> {
2109 #[inline]
2110 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2111 Some(self.cmp(other))
2112 }
2113}
2114
2115impl<B: BitBlock> Ord for BitVec<B> {
2116 #[inline]
2117 fn cmp(&self, other: &Self) -> Ordering {
2118 self.ensure_invariant();
2119 debug_assert!(other.is_last_block_fixed());
2120 let mut a = self.iter();
2121 let mut b = other.iter();
2122 loop {
2123 match (a.next(), b.next()) {
2124 (Some(x), Some(y)) => match x.cmp(&y) {
2125 Ordering::Equal => {}
2126 otherwise => return otherwise,
2127 },
2128 (None, None) => return Ordering::Equal,
2129 (None, _) => return Ordering::Less,
2130 (_, None) => return Ordering::Greater,
2131 }
2132 }
2133 }
2134}
2135
2136impl<B: BitBlock> fmt::Display for BitVec<B> {
2137 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
2138 self.ensure_invariant();
2139 for bit in self {
2140 fmt.write_char(if bit { '1' } else { '0' })?;
2141 }
2142 Ok(())
2143 }
2144}
2145
2146impl<B: BitBlock> fmt::Debug for BitVec<B> {
2147 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
2148 self.ensure_invariant();
2149 let mut storage = String::with_capacity(self.len() + self.len() / B::bits());
2150 for (i, bit) in self.iter().enumerate() {
2151 if i != 0 && i % B::bits() == 0 {
2152 storage.push(' ');
2153 }
2154 storage.push(if bit { '1' } else { '0' });
2155 }
2156 fmt.debug_struct("BitVec")
2157 .field("storage", &storage)
2158 .field("nbits", &self.nbits)
2159 .finish()
2160 }
2161}
2162
2163impl<B: BitBlock> hash::Hash for BitVec<B> {
2164 #[inline]
2165 fn hash<H: hash::Hasher>(&self, state: &mut H) {
2166 self.ensure_invariant();
2167 self.nbits.hash(state);
2168 for elem in self.blocks() {
2169 elem.hash(state);
2170 }
2171 }
2172}
2173
2174impl<B: BitBlock> cmp::PartialEq for BitVec<B> {
2175 #[inline]
2176 fn eq(&self, other: &Self) -> bool {
2177 if self.nbits != other.nbits {
2178 self.ensure_invariant();
2179 other.ensure_invariant();
2180 return false;
2181 }
2182 self.blocks().zip(other.blocks()).all(|(w1, w2)| w1 == w2)
2183 }
2184}
2185
2186impl<B: BitBlock> cmp::Eq for BitVec<B> {}
2187
2188#[derive(Clone)]
2190pub struct Iter<'a, B: 'a = u32> {
2191 bit_vec: &'a BitVec<B>,
2192 range: Range<usize>,
2193}
2194
2195#[derive(Debug)]
2196pub struct MutBorrowedBit<'a, B: 'a + BitBlock> {
2197 vec: Rc<RefCell<&'a mut BitVec<B>>>,
2198 index: usize,
2199 #[cfg(debug_assertions)]
2200 old_value: bool,
2201 new_value: bool,
2202}
2203
2204pub struct IterMut<'a, B: 'a + BitBlock = u32> {
2206 vec: Rc<RefCell<&'a mut BitVec<B>>>,
2207 range: Range<usize>,
2208}
2209
2210impl<'a, B: 'a + BitBlock> IterMut<'a, B> {
2211 fn get(&mut self, index: Option<usize>) -> Option<MutBorrowedBit<'a, B>> {
2212 let value = (*self.vec).borrow().get(index?)?;
2213 Some(MutBorrowedBit {
2214 vec: self.vec.clone(),
2215 index: index?,
2216 #[cfg(debug_assertions)]
2217 old_value: value,
2218 new_value: value,
2219 })
2220 }
2221}
2222
2223impl<B: BitBlock> Deref for MutBorrowedBit<'_, B> {
2224 type Target = bool;
2225
2226 fn deref(&self) -> &Self::Target {
2227 &self.new_value
2228 }
2229}
2230
2231impl<B: BitBlock> DerefMut for MutBorrowedBit<'_, B> {
2232 fn deref_mut(&mut self) -> &mut Self::Target {
2233 &mut self.new_value
2234 }
2235}
2236
2237impl<B: BitBlock> Drop for MutBorrowedBit<'_, B> {
2238 fn drop(&mut self) {
2239 let mut vec = (*self.vec).borrow_mut();
2240 #[cfg(debug_assertions)]
2241 debug_assert_eq!(
2242 Some(self.old_value),
2243 vec.get(self.index),
2244 "Mutably-borrowed bit was modified externally!"
2245 );
2246 vec.set(self.index, self.new_value);
2247 }
2248}
2249
2250impl<B: BitBlock> Iterator for Iter<'_, B> {
2251 type Item = bool;
2252
2253 #[inline]
2254 fn next(&mut self) -> Option<bool> {
2255 self.range.next().map(|i| self.bit_vec.get(i).unwrap())
2258 }
2259
2260 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2261 self.range.nth(n).and_then(|i| self.bit_vec.get(i))
2265 }
2266
2267 fn size_hint(&self) -> (usize, Option<usize>) {
2268 self.range.size_hint()
2269 }
2270}
2271
2272impl<'a, B: BitBlock> Iterator for IterMut<'a, B> {
2273 type Item = MutBorrowedBit<'a, B>;
2274
2275 #[inline]
2276 fn next(&mut self) -> Option<Self::Item> {
2277 let index = self.range.next();
2278 self.get(index)
2279 }
2280
2281 fn size_hint(&self) -> (usize, Option<usize>) {
2282 self.range.size_hint()
2283 }
2284}
2285
2286impl<B: BitBlock> DoubleEndedIterator for Iter<'_, B> {
2287 #[inline]
2288 fn next_back(&mut self) -> Option<bool> {
2289 self.range.next_back().map(|i| self.bit_vec.get(i).unwrap())
2290 }
2291}
2292
2293impl<B: BitBlock> DoubleEndedIterator for IterMut<'_, B> {
2294 #[inline]
2295 fn next_back(&mut self) -> Option<Self::Item> {
2296 let index = self.range.next_back();
2297 self.get(index)
2298 }
2299}
2300
2301impl<B: BitBlock> ExactSizeIterator for Iter<'_, B> {}
2302
2303impl<B: BitBlock> ExactSizeIterator for IterMut<'_, B> {}
2304
2305impl<'a, B: BitBlock> IntoIterator for &'a BitVec<B> {
2306 type Item = bool;
2307 type IntoIter = Iter<'a, B>;
2308
2309 #[inline]
2310 fn into_iter(self) -> Iter<'a, B> {
2311 self.iter()
2312 }
2313}
2314
2315pub struct IntoIter<B = u32> {
2316 bit_vec: BitVec<B>,
2317 range: Range<usize>,
2318}
2319
2320impl<B: BitBlock> Iterator for IntoIter<B> {
2321 type Item = bool;
2322
2323 #[inline]
2324 fn next(&mut self) -> Option<bool> {
2325 self.range.next().map(|i| self.bit_vec.get(i).unwrap())
2326 }
2327}
2328
2329impl<B: BitBlock> DoubleEndedIterator for IntoIter<B> {
2330 #[inline]
2331 fn next_back(&mut self) -> Option<bool> {
2332 self.range.next_back().map(|i| self.bit_vec.get(i).unwrap())
2333 }
2334}
2335
2336impl<B: BitBlock> ExactSizeIterator for IntoIter<B> {}
2337
2338impl<B: BitBlock> IntoIterator for BitVec<B> {
2339 type Item = bool;
2340 type IntoIter = IntoIter<B>;
2341
2342 #[inline]
2343 fn into_iter(self) -> IntoIter<B> {
2344 let nbits = self.nbits;
2345 IntoIter {
2346 bit_vec: self,
2347 range: 0..nbits,
2348 }
2349 }
2350}
2351
2352#[derive(Clone)]
2354pub struct Blocks<'a, B: 'a> {
2355 iter: slice::Iter<'a, B>,
2356}
2357
2358impl<B: BitBlock> Iterator for Blocks<'_, B> {
2359 type Item = B;
2360
2361 #[inline]
2362 fn next(&mut self) -> Option<B> {
2363 self.iter.next().cloned()
2364 }
2365
2366 #[inline]
2367 fn size_hint(&self) -> (usize, Option<usize>) {
2368 self.iter.size_hint()
2369 }
2370}
2371
2372impl<B: BitBlock> DoubleEndedIterator for Blocks<'_, B> {
2373 #[inline]
2374 fn next_back(&mut self) -> Option<B> {
2375 self.iter.next_back().cloned()
2376 }
2377}
2378
2379impl<B: BitBlock> ExactSizeIterator for Blocks<'_, B> {}
2380
2381#[cfg(test)]
2382mod tests {
2383 #![allow(clippy::shadow_reuse)]
2384 #![allow(clippy::shadow_same)]
2385 #![allow(clippy::shadow_unrelated)]
2386
2387 use super::{BitVec, Iter, Vec};
2388
2389 const U32_BITS: usize = 32;
2391
2392 #[test]
2393 fn test_display_output() {
2394 assert_eq!(format!("{}", BitVec::new()), "");
2395 assert_eq!(format!("{}", BitVec::from_elem(1, true)), "1");
2396 assert_eq!(format!("{}", BitVec::from_elem(8, false)), "00000000")
2397 }
2398
2399 #[test]
2400 fn test_debug_output() {
2401 assert_eq!(
2402 format!("{:?}", BitVec::new()),
2403 "BitVec { storage: \"\", nbits: 0 }"
2404 );
2405 assert_eq!(
2406 format!("{:?}", BitVec::from_elem(1, true)),
2407 "BitVec { storage: \"1\", nbits: 1 }"
2408 );
2409 assert_eq!(
2410 format!("{:?}", BitVec::from_elem(8, false)),
2411 "BitVec { storage: \"00000000\", nbits: 8 }"
2412 );
2413 assert_eq!(
2414 format!("{:?}", BitVec::from_elem(33, true)),
2415 "BitVec { storage: \"11111111111111111111111111111111 1\", nbits: 33 }"
2416 );
2417 assert_eq!(
2418 format!(
2419 "{:?}",
2420 BitVec::from_bytes(&[0b111, 0b000, 0b1110, 0b0001, 0b11111111, 0b00000000])
2421 ),
2422 "BitVec { storage: \"00000111000000000000111000000001 1111111100000000\", nbits: 48 }"
2423 )
2424 }
2425
2426 #[test]
2427 fn test_0_elements() {
2428 let act = BitVec::new();
2429 let exp = Vec::new();
2430 assert!(act.eq_vec(&exp));
2431 assert!(act.none() && act.all());
2432 }
2433
2434 #[test]
2435 fn test_1_element() {
2436 let mut act = BitVec::from_elem(1, false);
2437 assert!(act.eq_vec(&[false]));
2438 assert!(act.none() && !act.all());
2439 act = BitVec::from_elem(1, true);
2440 assert!(act.eq_vec(&[true]));
2441 assert!(!act.none() && act.all());
2442 }
2443
2444 #[test]
2445 fn test_2_elements() {
2446 let mut b = BitVec::from_elem(2, false);
2447 b.set(0, true);
2448 b.set(1, false);
2449 assert_eq!(format!("{}", b), "10");
2450 assert!(!b.none() && !b.all());
2451 }
2452
2453 #[test]
2454 fn test_10_elements() {
2455 let mut act = BitVec::from_elem(10, false);
2458 assert!(
2459 (act.eq_vec(&[false, false, false, false, false, false, false, false, false, false]))
2460 );
2461 assert!(act.none() && !act.all());
2462 act = BitVec::from_elem(10, true);
2465 assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
2466 assert!(!act.none() && act.all());
2467 act = BitVec::from_elem(10, false);
2470 act.set(0, true);
2471 act.set(1, true);
2472 act.set(2, true);
2473 act.set(3, true);
2474 act.set(4, true);
2475 assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
2476 assert!(!act.none() && !act.all());
2477 act = BitVec::from_elem(10, false);
2480 act.set(5, true);
2481 act.set(6, true);
2482 act.set(7, true);
2483 act.set(8, true);
2484 act.set(9, true);
2485 assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
2486 assert!(!act.none() && !act.all());
2487 act = BitVec::from_elem(10, false);
2490 act.set(0, true);
2491 act.set(3, true);
2492 act.set(6, true);
2493 act.set(9, true);
2494 assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
2495 assert!(!act.none() && !act.all());
2496 }
2497
2498 #[test]
2499 fn test_31_elements() {
2500 let mut act = BitVec::from_elem(31, false);
2503 assert!(act.eq_vec(&[
2504 false, false, false, false, false, false, false, false, false, false, false, false,
2505 false, false, false, false, false, false, false, false, false, false, false, false,
2506 false, false, false, false, false, false, false
2507 ]));
2508 assert!(act.none() && !act.all());
2509 act = BitVec::from_elem(31, true);
2512 assert!(act.eq_vec(&[
2513 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2514 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2515 true, true, true
2516 ]));
2517 assert!(!act.none() && act.all());
2518 act = BitVec::from_elem(31, false);
2521 act.set(0, true);
2522 act.set(1, true);
2523 act.set(2, true);
2524 act.set(3, true);
2525 act.set(4, true);
2526 act.set(5, true);
2527 act.set(6, true);
2528 act.set(7, true);
2529 assert!(act.eq_vec(&[
2530 true, true, true, true, true, true, true, true, false, false, false, false, false,
2531 false, false, false, false, false, false, false, false, false, false, false, false,
2532 false, false, false, false, false, false
2533 ]));
2534 assert!(!act.none() && !act.all());
2535 act = BitVec::from_elem(31, false);
2538 act.set(16, true);
2539 act.set(17, true);
2540 act.set(18, true);
2541 act.set(19, true);
2542 act.set(20, true);
2543 act.set(21, true);
2544 act.set(22, true);
2545 act.set(23, true);
2546 assert!(act.eq_vec(&[
2547 false, false, false, false, false, false, false, false, false, false, false, false,
2548 false, false, false, false, true, true, true, true, true, true, true, true, false,
2549 false, false, false, false, false, false
2550 ]));
2551 assert!(!act.none() && !act.all());
2552 act = BitVec::from_elem(31, false);
2555 act.set(24, true);
2556 act.set(25, true);
2557 act.set(26, true);
2558 act.set(27, true);
2559 act.set(28, true);
2560 act.set(29, true);
2561 act.set(30, true);
2562 assert!(act.eq_vec(&[
2563 false, false, false, false, false, false, false, false, false, false, false, false,
2564 false, false, false, false, false, false, false, false, false, false, false, false,
2565 true, true, true, true, true, true, true
2566 ]));
2567 assert!(!act.none() && !act.all());
2568 act = BitVec::from_elem(31, false);
2571 act.set(3, true);
2572 act.set(17, true);
2573 act.set(30, true);
2574 assert!(act.eq_vec(&[
2575 false, false, false, true, false, false, false, false, false, false, false, false,
2576 false, false, false, false, false, true, false, false, false, false, false, false,
2577 false, false, false, false, false, false, true
2578 ]));
2579 assert!(!act.none() && !act.all());
2580 }
2581
2582 #[test]
2583 fn test_32_elements() {
2584 let mut act = BitVec::from_elem(32, false);
2587 assert!(act.eq_vec(&[
2588 false, false, false, false, false, false, false, false, false, false, false, false,
2589 false, false, false, false, false, false, false, false, false, false, false, false,
2590 false, false, false, false, false, false, false, false
2591 ]));
2592 assert!(act.none() && !act.all());
2593 act = BitVec::from_elem(32, true);
2596 assert!(act.eq_vec(&[
2597 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2598 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2599 true, true, true, true
2600 ]));
2601 assert!(!act.none() && act.all());
2602 act = BitVec::from_elem(32, false);
2605 act.set(0, true);
2606 act.set(1, true);
2607 act.set(2, true);
2608 act.set(3, true);
2609 act.set(4, true);
2610 act.set(5, true);
2611 act.set(6, true);
2612 act.set(7, true);
2613 assert!(act.eq_vec(&[
2614 true, true, true, true, true, true, true, true, false, false, false, false, false,
2615 false, false, false, false, false, false, false, false, false, false, false, false,
2616 false, false, false, false, false, false, false
2617 ]));
2618 assert!(!act.none() && !act.all());
2619 act = BitVec::from_elem(32, false);
2622 act.set(16, true);
2623 act.set(17, true);
2624 act.set(18, true);
2625 act.set(19, true);
2626 act.set(20, true);
2627 act.set(21, true);
2628 act.set(22, true);
2629 act.set(23, true);
2630 assert!(act.eq_vec(&[
2631 false, false, false, false, false, false, false, false, false, false, false, false,
2632 false, false, false, false, true, true, true, true, true, true, true, true, false,
2633 false, false, false, false, false, false, false
2634 ]));
2635 assert!(!act.none() && !act.all());
2636 act = BitVec::from_elem(32, false);
2639 act.set(24, true);
2640 act.set(25, true);
2641 act.set(26, true);
2642 act.set(27, true);
2643 act.set(28, true);
2644 act.set(29, true);
2645 act.set(30, true);
2646 act.set(31, true);
2647 assert!(act.eq_vec(&[
2648 false, false, false, false, false, false, false, false, false, false, false, false,
2649 false, false, false, false, false, false, false, false, false, false, false, false,
2650 true, true, true, true, true, true, true, true
2651 ]));
2652 assert!(!act.none() && !act.all());
2653 act = BitVec::from_elem(32, false);
2656 act.set(3, true);
2657 act.set(17, true);
2658 act.set(30, true);
2659 act.set(31, true);
2660 assert!(act.eq_vec(&[
2661 false, false, false, true, false, false, false, false, false, false, false, false,
2662 false, false, false, false, false, true, false, false, false, false, false, false,
2663 false, false, false, false, false, false, true, true
2664 ]));
2665 assert!(!act.none() && !act.all());
2666 }
2667
2668 #[test]
2669 fn test_33_elements() {
2670 let mut act = BitVec::from_elem(33, false);
2673 assert!(act.eq_vec(&[
2674 false, false, false, false, false, false, false, false, false, false, false, false,
2675 false, false, false, false, false, false, false, false, false, false, false, false,
2676 false, false, false, false, false, false, false, false, false
2677 ]));
2678 assert!(act.none() && !act.all());
2679 act = BitVec::from_elem(33, true);
2682 assert!(act.eq_vec(&[
2683 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2684 true, true, true, true, true, true, true, true, true, true, true, true, true, true,
2685 true, true, true, true, true
2686 ]));
2687 assert!(!act.none() && act.all());
2688 act = BitVec::from_elem(33, false);
2691 act.set(0, true);
2692 act.set(1, true);
2693 act.set(2, true);
2694 act.set(3, true);
2695 act.set(4, true);
2696 act.set(5, true);
2697 act.set(6, true);
2698 act.set(7, true);
2699 assert!(act.eq_vec(&[
2700 true, true, true, true, true, true, true, true, false, false, false, false, false,
2701 false, false, false, false, false, false, false, false, false, false, false, false,
2702 false, false, false, false, false, false, false, false
2703 ]));
2704 assert!(!act.none() && !act.all());
2705 act = BitVec::from_elem(33, false);
2708 act.set(16, true);
2709 act.set(17, true);
2710 act.set(18, true);
2711 act.set(19, true);
2712 act.set(20, true);
2713 act.set(21, true);
2714 act.set(22, true);
2715 act.set(23, true);
2716 assert!(act.eq_vec(&[
2717 false, false, false, false, false, false, false, false, false, false, false, false,
2718 false, false, false, false, true, true, true, true, true, true, true, true, false,
2719 false, false, false, false, false, false, false, false
2720 ]));
2721 assert!(!act.none() && !act.all());
2722 act = BitVec::from_elem(33, false);
2725 act.set(24, true);
2726 act.set(25, true);
2727 act.set(26, true);
2728 act.set(27, true);
2729 act.set(28, true);
2730 act.set(29, true);
2731 act.set(30, true);
2732 act.set(31, true);
2733 assert!(act.eq_vec(&[
2734 false, false, false, false, false, false, false, false, false, false, false, false,
2735 false, false, false, false, false, false, false, false, false, false, false, false,
2736 true, true, true, true, true, true, true, true, false
2737 ]));
2738 assert!(!act.none() && !act.all());
2739 act = BitVec::from_elem(33, false);
2742 act.set(3, true);
2743 act.set(17, true);
2744 act.set(30, true);
2745 act.set(31, true);
2746 act.set(32, true);
2747 assert!(act.eq_vec(&[
2748 false, false, false, true, false, false, false, false, false, false, false, false,
2749 false, false, false, false, false, true, false, false, false, false, false, false,
2750 false, false, false, false, false, false, true, true, true
2751 ]));
2752 assert!(!act.none() && !act.all());
2753 }
2754
2755 #[test]
2756 fn test_equal_differing_sizes() {
2757 let v0 = BitVec::from_elem(10, false);
2758 let v1 = BitVec::from_elem(11, false);
2759 assert_ne!(v0, v1);
2760 }
2761
2762 #[test]
2763 fn test_equal_greatly_differing_sizes() {
2764 let v0 = BitVec::from_elem(10, false);
2765 let v1 = BitVec::from_elem(110, false);
2766 assert_ne!(v0, v1);
2767 }
2768
2769 #[test]
2770 fn test_equal_sneaky_small() {
2771 let mut a = BitVec::from_elem(1, false);
2772 a.set(0, true);
2773
2774 let mut b = BitVec::from_elem(1, true);
2775 b.set(0, true);
2776
2777 assert_eq!(a, b);
2778 }
2779
2780 #[test]
2781 fn test_equal_sneaky_big() {
2782 let mut a = BitVec::from_elem(100, false);
2783 for i in 0..100 {
2784 a.set(i, true);
2785 }
2786
2787 let mut b = BitVec::from_elem(100, true);
2788 for i in 0..100 {
2789 b.set(i, true);
2790 }
2791
2792 assert_eq!(a, b);
2793 }
2794
2795 #[test]
2796 fn test_from_bytes() {
2797 let bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
2798 let str = concat!("10110110", "00000000", "11111111");
2799 assert_eq!(format!("{}", bit_vec), str);
2800 }
2801
2802 #[test]
2803 fn test_to_bytes() {
2804 let mut bv = BitVec::from_elem(3, true);
2805 bv.set(1, false);
2806 assert_eq!(bv.to_bytes(), [0b10100000]);
2807
2808 let mut bv = BitVec::from_elem(9, false);
2809 bv.set(2, true);
2810 bv.set(8, true);
2811 assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
2812 }
2813
2814 #[test]
2815 fn test_from_bools() {
2816 let bools = [true, false, true, true];
2817 let bit_vec: BitVec = bools.iter().copied().collect();
2818 assert_eq!(format!("{}", bit_vec), "1011");
2819 }
2820
2821 #[test]
2822 fn test_to_bools() {
2823 let bools = vec![false, false, true, false, false, true, true, false];
2824 assert_eq!(
2825 BitVec::from_bytes(&[0b00100110])
2826 .iter()
2827 .collect::<Vec<bool>>(),
2828 bools
2829 );
2830 }
2831
2832 #[test]
2833 fn test_bit_vec_iterator() {
2834 let bools = vec![true, false, true, true];
2835 let bit_vec: BitVec = bools.iter().copied().collect();
2836
2837 assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), bools);
2838
2839 let long: Vec<_> = (0..10000).map(|i| i % 2 == 0).collect();
2840 let bit_vec: BitVec = long.iter().copied().collect();
2841 assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), long)
2842 }
2843
2844 #[test]
2845 fn test_small_difference() {
2846 let mut b1 = BitVec::from_elem(3, false);
2847 let mut b2 = BitVec::from_elem(3, false);
2848 b1.set(0, true);
2849 b1.set(1, true);
2850 b2.set(1, true);
2851 b2.set(2, true);
2852 assert!(b1.difference(&b2));
2853 assert!(b1[0]);
2854 assert!(!b1[1]);
2855 assert!(!b1[2]);
2856 }
2857
2858 #[test]
2859 fn test_big_difference() {
2860 let mut b1 = BitVec::from_elem(100, false);
2861 let mut b2 = BitVec::from_elem(100, false);
2862 b1.set(0, true);
2863 b1.set(40, true);
2864 b2.set(40, true);
2865 b2.set(80, true);
2866 assert!(b1.difference(&b2));
2867 assert!(b1[0]);
2868 assert!(!b1[40]);
2869 assert!(!b1[80]);
2870 }
2871
2872 #[test]
2873 fn test_small_xor() {
2874 let mut a = BitVec::from_bytes(&[0b0011]);
2875 let b = BitVec::from_bytes(&[0b0101]);
2876 let c = BitVec::from_bytes(&[0b0110]);
2877 assert!(a.xor(&b));
2878 assert_eq!(a, c);
2879 }
2880
2881 #[test]
2882 fn test_small_xnor() {
2883 let mut a = BitVec::from_bytes(&[0b0011]);
2884 let b = BitVec::from_bytes(&[0b1111_0101]);
2885 let c = BitVec::from_bytes(&[0b1001]);
2886 assert!(a.xnor(&b));
2887 assert_eq!(a, c);
2888 }
2889
2890 #[test]
2891 fn test_small_nand() {
2892 let mut a = BitVec::from_bytes(&[0b1111_0011]);
2893 let b = BitVec::from_bytes(&[0b1111_0101]);
2894 let c = BitVec::from_bytes(&[0b1110]);
2895 assert!(a.nand(&b));
2896 assert_eq!(a, c);
2897 }
2898
2899 #[test]
2900 fn test_small_nor() {
2901 let mut a = BitVec::from_bytes(&[0b0011]);
2902 let b = BitVec::from_bytes(&[0b1111_0101]);
2903 let c = BitVec::from_bytes(&[0b1000]);
2904 assert!(a.nor(&b));
2905 assert_eq!(a, c);
2906 }
2907
2908 #[test]
2909 fn test_big_xor() {
2910 let mut a = BitVec::from_bytes(&[
2911 0, 0, 0b00010100, 0, 0, 0, 0, 0b00110100, 0, 0, 0,
2913 ]);
2914 let b = BitVec::from_bytes(&[
2915 0, 0, 0b00010100, 0, 0, 0, 0, 0, 0, 0, 0b00110100,
2917 ]);
2918 let c = BitVec::from_bytes(&[
2919 0, 0, 0, 0, 0, 0, 0, 0b00110100, 0, 0, 0b00110100,
2921 ]);
2922 assert!(a.xor(&b));
2923 assert_eq!(a, c);
2924 }
2925
2926 #[test]
2927 fn test_big_xnor() {
2928 let mut a = BitVec::from_bytes(&[
2929 0, 0, 0b00010100, 0, 0, 0, 0, 0b00110100, 0, 0, 0,
2931 ]);
2932 let b = BitVec::from_bytes(&[
2933 0, 0, 0b00010100, 0, 0, 0, 0, 0, 0, 0, 0b00110100,
2935 ]);
2936 let c = BitVec::from_bytes(&[
2937 !0,
2939 !0,
2940 !0,
2941 !0,
2942 !0,
2943 !0,
2944 !0,
2945 !0b00110100,
2946 !0,
2947 !0,
2948 !0b00110100,
2949 ]);
2950 assert!(a.xnor(&b));
2951 assert_eq!(a, c);
2952 }
2953
2954 #[test]
2955 fn test_small_fill() {
2956 let mut b = BitVec::from_elem(14, true);
2957 assert!(!b.none() && b.all());
2958 b.fill(false);
2959 assert!(b.none() && !b.all());
2960 b.fill(true);
2961 assert!(!b.none() && b.all());
2962 }
2963
2964 #[test]
2965 fn test_big_fill() {
2966 let mut b = BitVec::from_elem(140, true);
2967 assert!(!b.none() && b.all());
2968 b.fill(false);
2969 assert!(b.none() && !b.all());
2970 b.fill(true);
2971 assert!(!b.none() && b.all());
2972 }
2973
2974 #[test]
2975 fn test_bit_vec_lt() {
2976 let mut a = BitVec::from_elem(5, false);
2977 let mut b = BitVec::from_elem(5, false);
2978
2979 assert!(a >= b && b >= a);
2980 b.set(2, true);
2981 assert!(a < b);
2982 a.set(3, true);
2983 assert!(a < b);
2984 a.set(2, true);
2985 assert!(a >= b && b < a);
2986 b.set(0, true);
2987 assert!(a < b);
2988 }
2989
2990 #[test]
2991 fn test_ord() {
2992 let mut a = BitVec::from_elem(5, false);
2993 let mut b = BitVec::from_elem(5, false);
2994
2995 assert!(a == b);
2996 a.set(1, true);
2997 assert!(a > b && a >= b);
2998 assert!(b < a && b <= a);
2999 b.set(1, true);
3000 b.set(2, true);
3001 assert!(b > a && b >= a);
3002 assert!(a < b && a <= b);
3003 }
3004
3005 #[test]
3006 fn test_small_bit_vec_tests() {
3007 let v = BitVec::from_bytes(&[0]);
3008 assert!(!v.all());
3009 assert!(!v.any());
3010 assert!(v.none());
3011
3012 let v = BitVec::from_bytes(&[0b00010100]);
3013 assert!(!v.all());
3014 assert!(v.any());
3015 assert!(!v.none());
3016
3017 let v = BitVec::from_bytes(&[0xFF]);
3018 assert!(v.all());
3019 assert!(v.any());
3020 assert!(!v.none());
3021 }
3022
3023 #[test]
3024 fn test_big_bit_vec_tests() {
3025 let v = BitVec::from_bytes(&[
3026 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3028 ]);
3029 assert!(!v.all());
3030 assert!(!v.any());
3031 assert!(v.none());
3032
3033 let v = BitVec::from_bytes(&[
3034 0, 0, 0b00010100, 0, 0, 0, 0, 0b00110100, 0, 0, 0,
3036 ]);
3037 assert!(!v.all());
3038 assert!(v.any());
3039 assert!(!v.none());
3040
3041 let v = BitVec::from_bytes(&[
3042 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
3044 ]);
3045 assert!(v.all());
3046 assert!(v.any());
3047 assert!(!v.none());
3048 }
3049
3050 #[test]
3051 fn test_bit_vec_push_pop() {
3052 let mut s = BitVec::from_elem(5 * U32_BITS - 2, false);
3053 assert_eq!(s.len(), 5 * U32_BITS - 2);
3054 assert!(!s[5 * U32_BITS - 3]);
3055 s.push(true);
3056 s.push(true);
3057 assert!(s[5 * U32_BITS - 2]);
3058 assert!(s[5 * U32_BITS - 1]);
3059 s.push(false);
3061 assert!(!s[5 * U32_BITS]);
3062 s.push(false);
3063 assert!(!s[5 * U32_BITS + 1]);
3064 assert_eq!(s.len(), 5 * U32_BITS + 2);
3065 assert_eq!(s.pop(), Some(false));
3067 assert_eq!(s.pop(), Some(false));
3068 assert_eq!(s.pop(), Some(true));
3069 assert_eq!(s.pop(), Some(true));
3070 assert_eq!(s.len(), 5 * U32_BITS - 2);
3071 }
3072
3073 #[test]
3074 fn test_bit_vec_truncate() {
3075 let mut s = BitVec::from_elem(5 * U32_BITS, true);
3076
3077 assert_eq!(s, BitVec::from_elem(5 * U32_BITS, true));
3078 assert_eq!(s.len(), 5 * U32_BITS);
3079 s.truncate(4 * U32_BITS);
3080 assert_eq!(s, BitVec::from_elem(4 * U32_BITS, true));
3081 assert_eq!(s.len(), 4 * U32_BITS);
3082 s.truncate(5 * U32_BITS);
3084 assert_eq!(s, BitVec::from_elem(4 * U32_BITS, true));
3085 assert_eq!(s.len(), 4 * U32_BITS);
3086 s.truncate(3 * U32_BITS - 10);
3087 assert_eq!(s, BitVec::from_elem(3 * U32_BITS - 10, true));
3088 assert_eq!(s.len(), 3 * U32_BITS - 10);
3089 s.truncate(0);
3090 assert_eq!(s, BitVec::from_elem(0, true));
3091 assert_eq!(s.len(), 0);
3092 }
3093
3094 #[test]
3095 fn test_bit_vec_reserve() {
3096 let mut s = BitVec::from_elem(5 * U32_BITS, true);
3097 assert!(s.capacity() >= 5 * U32_BITS);
3099 s.reserve(2 * U32_BITS);
3100 assert!(s.capacity() >= 7 * U32_BITS);
3101 s.reserve(7 * U32_BITS);
3102 assert!(s.capacity() >= 12 * U32_BITS);
3103 s.reserve_exact(7 * U32_BITS);
3104 assert!(s.capacity() >= 12 * U32_BITS);
3105 s.reserve(7 * U32_BITS + 1);
3106 assert!(s.capacity() > 12 * U32_BITS);
3107 assert_eq!(s.len(), 5 * U32_BITS);
3109 s.push(true);
3110 s.push(false);
3111 s.push(true);
3112 assert!(s[5 * U32_BITS - 1]);
3113 assert!(s[5 * U32_BITS]);
3114 assert!(!s[5 * U32_BITS + 1]);
3115 assert!(s[5 * U32_BITS + 2]);
3116 }
3117
3118 #[test]
3119 fn test_bit_vec_grow() {
3120 let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
3121 bit_vec.grow(32, true);
3122 assert_eq!(
3123 bit_vec,
3124 BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF])
3125 );
3126 bit_vec.grow(64, false);
3127 assert_eq!(
3128 bit_vec,
3129 BitVec::from_bytes(&[
3130 0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0
3131 ])
3132 );
3133 bit_vec.grow(16, true);
3134 assert_eq!(
3135 bit_vec,
3136 BitVec::from_bytes(&[
3137 0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0,
3138 0xFF, 0xFF
3139 ])
3140 );
3141 }
3142
3143 #[test]
3144 fn test_bit_vec_extend() {
3145 let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
3146 let ext = BitVec::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
3147 bit_vec.extend(ext.iter());
3148 assert_eq!(
3149 bit_vec,
3150 BitVec::from_bytes(&[
3151 0b10110110, 0b00000000, 0b11111111, 0b01001001, 0b10010010, 0b10111101
3152 ])
3153 );
3154 }
3155
3156 #[test]
3157 fn test_bit_vec_append() {
3158 let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011]);
3160 let mut b = BitVec::new();
3161 b.push(false);
3162 b.push(true);
3163 b.push(true);
3164
3165 a.append(&mut b);
3166
3167 assert_eq!(a.len(), 35);
3168 assert_eq!(b.len(), 0);
3169 assert!(b.capacity() >= 3);
3170
3171 assert!(a.eq_vec(&[
3172 true, false, true, false, false, false, false, false, false, false, false, true, false,
3173 false, true, false, true, false, false, true, false, false, true, false, false, false,
3174 true, true, false, false, true, true, false, true, true
3175 ]));
3176
3177 let mut a = BitVec::new();
3179 a.push(true);
3180 a.push(false);
3181
3182 let mut b =
3183 BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
3184
3185 a.append(&mut b);
3186
3187 assert_eq!(a.len(), 42);
3188 assert_eq!(b.len(), 0);
3189 assert!(b.capacity() >= 40);
3190
3191 assert!(a.eq_vec(&[
3192 true, false, true, false, true, false, false, false, false, false, false, false, false,
3193 true, false, false, true, false, true, false, false, true, false, false, true, false,
3194 false, false, true, true, false, false, true, true, true, false, false, true, false,
3195 true, false, true
3196 ]));
3197
3198 let mut a = BitVec::new();
3200 let mut b =
3201 BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
3202
3203 a.append(&mut b);
3204
3205 assert_eq!(a.len(), 40);
3206 assert_eq!(b.len(), 0);
3207 assert!(b.capacity() >= 40);
3208
3209 assert!(a.eq_vec(&[
3210 true, false, true, false, false, false, false, false, false, false, false, true, false,
3211 false, true, false, true, false, false, true, false, false, true, false, false, false,
3212 true, true, false, false, true, true, true, false, false, true, false, true, false,
3213 true
3214 ]));
3215
3216 let mut a =
3218 BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
3219 let mut b = BitVec::new();
3220
3221 a.append(&mut b);
3222
3223 assert_eq!(a.len(), 40);
3224 assert_eq!(b.len(), 0);
3225
3226 assert!(a.eq_vec(&[
3227 true, false, true, false, false, false, false, false, false, false, false, true, false,
3228 false, true, false, true, false, false, true, false, false, true, false, false, false,
3229 true, true, false, false, true, true, true, false, false, true, false, true, false,
3230 true
3231 ]));
3232 }
3233
3234 #[test]
3235 fn test_bit_vec_split_off() {
3236 let mut a = BitVec::new();
3238 a.push(true);
3239 a.push(false);
3240 a.push(false);
3241 a.push(true);
3242
3243 let b = a.split_off(0);
3244
3245 assert_eq!(a.len(), 0);
3246 assert_eq!(b.len(), 4);
3247
3248 assert!(b.eq_vec(&[true, false, false, true]));
3249
3250 a.truncate(0);
3252 a.push(true);
3253 a.push(false);
3254 a.push(false);
3255 a.push(true);
3256
3257 let b = a.split_off(4);
3258
3259 assert_eq!(a.len(), 4);
3260 assert_eq!(b.len(), 0);
3261
3262 assert!(a.eq_vec(&[true, false, false, true]));
3263
3264 let mut a =
3266 BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b11110011]);
3267
3268 let b = a.split_off(32);
3269
3270 assert_eq!(a.len(), 32);
3271 assert_eq!(b.len(), 8);
3272
3273 assert!(a.eq_vec(&[
3274 true, false, true, false, false, false, false, false, false, false, false, true, false,
3275 false, true, false, true, false, false, true, false, false, true, false, false, false,
3276 true, true, false, false, true, true
3277 ]));
3278 assert!(b.eq_vec(&[true, true, true, true, false, false, true, true]));
3279
3280 let mut a = BitVec::from_bytes(&[
3282 0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b01101011, 0b10101101,
3283 ]);
3284
3285 let b = a.split_off(13);
3286
3287 assert_eq!(a.len(), 13);
3288 assert_eq!(b.len(), 35);
3289
3290 assert!(a.eq_vec(&[
3291 true, false, true, false, false, false, false, false, false, false, false, true, false
3292 ]));
3293 assert!(b.eq_vec(&[
3294 false, true, false, true, false, false, true, false, false, true, false, false, false,
3295 true, true, false, false, true, true, false, true, true, false, true, false, true,
3296 true, true, false, true, false, true, true, false, true
3297 ]));
3298 }
3299
3300 #[test]
3301 fn test_split_off_storage_boundaries() {
3302 for tail_len in [1, 31, 32, 33, 63, 64, 65] {
3303 for at in 0..=64 {
3304 for pattern in 0..3 {
3305 let bits: Vec<bool> = (0..at + tail_len)
3306 .map(|i| match pattern {
3307 0 => false,
3308 1 => true,
3309 _ => i % 3 == 0,
3310 })
3311 .collect();
3312 let mut a: BitVec<u32> = bits.iter().copied().collect();
3313 let b = a.split_off(at);
3314
3315 assert_eq!(a.storage().len(), (at + 31) / 32);
3316 assert_eq!(b.storage().len(), (tail_len + 31) / 32);
3317 assert_eq!(a.iter().collect::<Vec<_>>(), bits[..at]);
3318 assert_eq!(b.iter().collect::<Vec<_>>(), bits[at..]);
3319 assert_eq!(b.all(), bits[at..].iter().all(|&bit| bit));
3320 assert_eq!(
3321 b.count_zeros(),
3322 bits[at..].iter().filter(|&&bit| !bit).count() as u64
3323 );
3324 }
3325 }
3326 }
3327 }
3328
3329 #[test]
3330 fn test_into_iter() {
3331 let bools = [true, false, true, true];
3332 let bit_vec: BitVec = bools.iter().copied().collect();
3333 let mut iter = bit_vec.into_iter();
3334 assert_eq!(Some(true), iter.next());
3335 assert_eq!(Some(false), iter.next());
3336 assert_eq!(Some(true), iter.next());
3337 assert_eq!(Some(true), iter.next());
3338 assert_eq!(None, iter.next());
3339 assert_eq!(None, iter.next());
3340
3341 let bit_vec: BitVec = bools.iter().copied().collect();
3342 let mut iter = bit_vec.into_iter();
3343 assert_eq!(Some(true), iter.next_back());
3344 assert_eq!(Some(true), iter.next_back());
3345 assert_eq!(Some(false), iter.next_back());
3346 assert_eq!(Some(true), iter.next_back());
3347 assert_eq!(None, iter.next_back());
3348 assert_eq!(None, iter.next_back());
3349
3350 let bit_vec: BitVec = bools.iter().copied().collect();
3351 let mut iter = bit_vec.into_iter();
3352 assert_eq!(Some(true), iter.next_back());
3353 assert_eq!(Some(true), iter.next());
3354 assert_eq!(Some(false), iter.next());
3355 assert_eq!(Some(true), iter.next_back());
3356 assert_eq!(None, iter.next());
3357 assert_eq!(None, iter.next_back());
3358 }
3359
3360 #[test]
3361 fn iter() {
3362 let b = BitVec::with_capacity(10);
3363 let _a: Iter = b.iter();
3364 }
3365
3366 #[cfg(feature = "serde")]
3367 #[test]
3368 fn test_serialization() {
3369 let bit_vec: BitVec = BitVec::new();
3370 let serialized = serde_json::to_string(&bit_vec).unwrap();
3371 let unserialized: BitVec = serde_json::from_str(&serialized[..]).unwrap();
3372 assert_eq!(bit_vec, unserialized);
3373
3374 let bools = [true, false, true, true];
3375 let bit_vec: BitVec = bools.iter().copied().collect();
3376 let serialized = serde_json::to_string(&bit_vec).unwrap();
3377 let unserialized = serde_json::from_str(&serialized).unwrap();
3378 assert_eq!(bit_vec, unserialized);
3379 }
3380
3381 #[cfg(feature = "miniserde")]
3382 #[test]
3383 fn test_miniserde_serialization() {
3384 let bit_vec: BitVec = BitVec::new();
3385 let serialized = miniserde::json::to_string(&bit_vec);
3386 let unserialized = miniserde::json::from_str(&serialized[..]).unwrap();
3387 assert_eq!(bit_vec, unserialized);
3388
3389 let bools = [true, false, true, true];
3390 let bit_vec: BitVec = bools.iter().copied().collect();
3391 let serialized = miniserde::json::to_string(&bit_vec);
3392 let unserialized = miniserde::json::from_str(&serialized[..]).unwrap();
3393 assert_eq!(bit_vec, unserialized);
3394 }
3395
3396 #[cfg(feature = "borsh")]
3397 #[test]
3398 fn test_borsh_serialization() {
3399 let bit_vec: BitVec = BitVec::new();
3400 let serialized = borsh::to_vec(&bit_vec).unwrap();
3401 let unserialized = borsh::from_slice(&serialized[..]).unwrap();
3402 assert_eq!(bit_vec, unserialized);
3403
3404 let bools = [true, false, true, true];
3405 let bit_vec: BitVec = bools.iter().copied().collect();
3406 let serialized = borsh::to_vec(&bit_vec).unwrap();
3407 let unserialized = borsh::from_slice(&serialized[..]).unwrap();
3408 assert_eq!(bit_vec, unserialized);
3409 }
3410
3411 #[test]
3412 fn test_bit_vec_unaligned_small_append() {
3413 let mut a = BitVec::from_elem(8, false);
3414 a.set(7, true);
3415
3416 let mut b = BitVec::from_elem(16, false);
3417 b.set(14, true);
3418
3419 let mut c = BitVec::from_elem(8, false);
3420 c.set(6, true);
3421 c.set(7, true);
3422
3423 a.append(&mut b);
3424 a.append(&mut c);
3425
3426 assert_eq!(&[1, 0, 2, 3][..], &*a.to_bytes());
3427 }
3428
3429 #[test]
3430 fn test_bit_vec_unaligned_large_append() {
3431 let mut a = BitVec::from_elem(48, false);
3432 a.set(47, true);
3433
3434 let mut b = BitVec::from_elem(48, false);
3435 b.set(46, true);
3436
3437 let mut c = BitVec::from_elem(48, false);
3438 c.set(46, true);
3439 c.set(47, true);
3440
3441 a.append(&mut b);
3442 a.append(&mut c);
3443
3444 assert_eq!(
3445 &[
3446 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00,
3447 0x00, 0x00, 0x00, 0x03
3448 ][..],
3449 &*a.to_bytes()
3450 );
3451 }
3452
3453 #[test]
3454 fn test_bit_vec_append_aligned_to_unaligned() {
3455 let mut a = BitVec::from_elem(2, true);
3456 let mut b = BitVec::from_elem(32, false);
3457 let mut c = BitVec::from_elem(8, true);
3458 a.append(&mut b);
3459 a.append(&mut c);
3460 assert_eq!(&[0xc0, 0x00, 0x00, 0x00, 0x3f, 0xc0][..], &*a.to_bytes());
3461 }
3462
3463 #[test]
3464 fn test_count_ones() {
3465 for i in 0..1000 {
3466 let mut t = BitVec::from_elem(i, true);
3467 let mut f = BitVec::from_elem(i, false);
3468 assert_eq!(i as u64, t.count_ones());
3469 assert_eq!(0_u64, f.count_ones());
3470 if i > 20 {
3471 t.set(10, false);
3472 t.set(i - 10, false);
3473 assert_eq!(i - 2, t.count_ones() as usize);
3474 f.set(10, true);
3475 f.set(i - 10, true);
3476 assert_eq!(2, f.count_ones());
3477 }
3478 }
3479 }
3480
3481 #[test]
3482 fn test_count_zeros() {
3483 for i in 0..1000 {
3484 let mut tbits = BitVec::from_elem(i, true);
3485 let mut fbits = BitVec::from_elem(i, false);
3486 assert_eq!(i as u64, fbits.count_zeros());
3487 assert_eq!(0_u64, tbits.count_zeros());
3488 if i > 20 {
3489 fbits.set(10, true);
3490 fbits.set(i - 10, true);
3491 assert_eq!(i - 2, fbits.count_zeros() as usize);
3492 tbits.set(10, false);
3493 tbits.set(i - 10, false);
3494 assert_eq!(2, tbits.count_zeros());
3495 }
3496 }
3497 }
3498
3499 #[test]
3500 fn test_get_mut() {
3501 let mut a = BitVec::from_elem(3, false);
3502 let mut a_bit_1 = a.get_mut(1).unwrap();
3503 assert!(!*a_bit_1);
3504 *a_bit_1 = true;
3505 drop(a_bit_1);
3506 assert!(a.eq_vec(&[false, true, false]));
3507 }
3508 #[test]
3509 fn test_iter_mut() {
3510 let mut a = BitVec::from_elem(8, false);
3511 a.iter_mut().enumerate().for_each(|(index, mut bit)| {
3512 *bit = index % 2 == 1;
3513 });
3514 assert!(a.eq_vec(&[false, true, false, true, false, true, false, true]));
3515 }
3516
3517 #[test]
3518 fn test_insert_at_zero() {
3519 let mut v = BitVec::new();
3520
3521 v.insert(0, false);
3522 v.insert(0, true);
3523 v.insert(0, false);
3524 v.insert(0, true);
3525 v.insert(0, false);
3526 v.insert(0, true);
3527
3528 assert_eq!(v.len(), 6);
3529 assert_eq!(v.storage().len(), 1);
3530 assert!(v.eq_vec(&[true, false, true, false, true, false]));
3531 }
3532
3533 #[test]
3534 fn test_insert_at_end() {
3535 let mut v = BitVec::new();
3536
3537 v.insert(v.len(), true);
3538 v.insert(v.len(), false);
3539 v.insert(v.len(), true);
3540 v.insert(v.len(), false);
3541 v.insert(v.len(), true);
3542 v.insert(v.len(), false);
3543
3544 assert_eq!(v.storage().len(), 1);
3545 assert_eq!(v.len(), 6);
3546 assert!(v.eq_vec(&[true, false, true, false, true, false]));
3547 }
3548
3549 #[test]
3550 fn test_insert_at_block_boundaries() {
3551 let mut v = BitVec::from_elem(32, false);
3552
3553 assert_eq!(v.storage().len(), 1);
3554
3555 v.insert(31, true);
3556
3557 assert_eq!(v.len(), 33);
3558
3559 assert!(matches!(v.get(31), Some(true)));
3560 assert!(v.eq_vec(&[
3561 false, false, false, false, false, false, false, false, false, false, false, false,
3562 false, false, false, false, false, false, false, false, false, false, false, false,
3563 false, false, false, false, false, false, false, true, false
3564 ]));
3565
3566 assert_eq!(v.storage().len(), 2);
3567 }
3568
3569 #[test]
3570 fn test_insert_at_block_boundaries_1() {
3571 let mut v = BitVec::from_elem(64, false);
3572
3573 assert_eq!(v.storage().len(), 2);
3574
3575 v.insert(63, true);
3576
3577 assert_eq!(v.len(), 65);
3578
3579 assert!(matches!(v.get(63), Some(true)));
3580 assert!(v.eq_vec(&[
3581 false, false, false, false, false, false, false, false, false, false, false, false,
3582 false, false, false, false, false, false, false, false, false, false, false, false,
3583 false, false, false, false, false, false, false, false, false, false, false, false,
3584 false, false, false, false, false, false, false, false, false, false, false, false,
3585 false, false, false, false, false, false, false, false, false, false, false, false,
3586 false, false, false, true, false
3587 ]));
3588
3589 assert_eq!(v.storage().len(), 3);
3590 }
3591
3592 #[test]
3593 fn test_push_within_capacity_with_suffice_cap() {
3594 let mut v = BitVec::from_elem(16, true);
3595
3596 assert!(v.push_within_capacity(false).is_ok());
3597
3598 for i in 0..16 {
3599 assert_eq!(v.get(i), Some(true));
3600 }
3601
3602 assert_eq!(v.get(16), Some(false));
3603 assert_eq!(v.len(), 17);
3604 }
3605
3606 #[test]
3607 fn test_push_within_capacity_at_brink() {
3608 let mut v = BitVec::from_elem(31, true);
3609
3610 assert!(v.push_within_capacity(false).is_ok());
3611
3612 assert_eq!(v.get(31), Some(false));
3613 assert_eq!(v.len(), v.capacity());
3614 assert_eq!(v.len(), 32);
3615
3616 assert_eq!(v.push_within_capacity(false), Err(false));
3617 assert_eq!(v.capacity(), 32);
3618
3619 for i in 0..31 {
3620 assert_eq!(v.get(i), Some(true));
3621 }
3622 assert_eq!(v.get(31), Some(false));
3623 }
3624
3625 #[test]
3626 fn test_push_within_capacity_at_brink_with_mul_blocks() {
3627 let mut v = BitVec::from_elem(95, true);
3628
3629 assert!(v.push_within_capacity(false).is_ok());
3630
3631 assert_eq!(v.get(95), Some(false));
3632 assert_eq!(v.len(), v.capacity());
3633 assert_eq!(v.len(), 96);
3634
3635 assert_eq!(v.push_within_capacity(false), Err(false));
3636 assert_eq!(v.capacity(), 96);
3637
3638 for i in 0..95 {
3639 assert_eq!(v.get(i), Some(true));
3640 }
3641 assert_eq!(v.get(95), Some(false));
3642 }
3643
3644 #[test]
3645 fn test_push_within_capacity_storage_push() {
3646 let mut v = BitVec::with_capacity(64);
3647
3648 for _ in 0..32 {
3649 v.push(true);
3650 }
3651
3652 assert_eq!(v.len(), 32);
3653
3654 assert!(v.push_within_capacity(false).is_ok());
3655
3656 assert_eq!(v.len(), 33);
3657
3658 for i in 0..32 {
3659 assert_eq!(v.get(i), Some(true));
3660 }
3661 assert_eq!(v.get(32), Some(false));
3662 }
3663
3664 #[test]
3665 fn test_insert_remove() {
3666 let mut v = BitVec::from_fn(1024, |i| i % 11 < 7);
3668 for i in 0..1024 {
3669 let result = v.remove(i);
3670 v.insert(i, result);
3671 assert_eq!(result, i % 11 < 7);
3672 }
3673
3674 for i in 0..1024 {
3675 v.insert(i, false);
3676 v.remove(i);
3677 }
3678
3679 for i in 0..1024 {
3680 v.insert(i, true);
3681 v.remove(i);
3682 }
3683
3684 for (i, result) in v.into_iter().enumerate() {
3685 assert_eq!(result, i % 11 < 7);
3686 }
3687 }
3688
3689 #[test]
3690 fn test_remove_last() {
3691 let mut v = BitVec::from_fn(1025, |i| i % 11 < 7);
3692 assert_eq!(v.len(), 1025);
3693 assert_eq!(v.remove(1024), 1024 % 11 < 7);
3694 assert_eq!(v.len(), 1024);
3695 assert_eq!(v.storage().len(), 1024 / 32);
3696 }
3697
3698 #[test]
3699 fn test_remove_all() {
3700 let v = BitVec::from_elem(1024, false);
3701 for _ in 0..1024 {
3702 let mut v2 = v.clone();
3703 v2.remove_all();
3704 assert_eq!(v2.len(), 0);
3705 assert_eq!(v2.get(0), None);
3706 assert_eq!(v2, BitVec::new());
3707 }
3708 }
3709
3710 #[test]
3711 fn test_bitwise_ops_change() {
3712 for len in 0..256 {
3713 let mut a = BitVec::from_elem(len, false);
3714 let mut b = BitVec::from_elem(len, true);
3715 if len == 0 {
3716 assert!(!a.or(&b));
3717 assert!(!a.nor(&b));
3718 assert!(!a.xor(&b));
3719 assert!(!a.xnor(&b));
3720 assert!(!a.nand(&b));
3721 assert!(!a.and(&b));
3722 } else {
3723 assert!(a.or(&b));
3724 a.fill(false);
3725 assert!(!b.or(&a));
3726 b.fill(true);
3727 assert!(!a.nor(&b));
3728 a.fill(false);
3729 assert!(b.nor(&a));
3730 b.fill(true);
3731 assert!(a.xor(&b));
3732 a.fill(false);
3733 assert!(!b.xor(&a));
3734 b.fill(true);
3735 assert!(!a.xnor(&b));
3736 a.fill(false);
3737 assert!(b.xnor(&a));
3738 b.fill(true);
3739 assert!(a.nand(&b));
3740
3741 let b = BitVec::from_elem(len, false);
3742
3743 let mut a = BitVec::from_elem(len, false);
3744 assert!(a.nor(&b));
3745 assert_eq!(a, BitVec::from_elem(len, true));
3746
3747 let mut a = BitVec::from_elem(len, false);
3748 assert!(a.xnor(&b));
3749 assert_eq!(a, BitVec::from_elem(len, true));
3750 }
3751 }
3752 }
3753}