1 //! `FixedBitSet` is a simple fixed size set of bits.
2 //!
3 //!
4 //! ### Crate features
5 //!
6 //! - `std` (default feature)
7 //! Disabling this feature disables using std and instead uses crate alloc.
8 //! Requires Rust 1.36 to disable.
9 //!
10 //! ### Rust Version
11 //!
12 //! This version of fixedbitset requires Rust 1.39 or later.
13 //!
14 #![doc(html_root_url="https://docs.rs/fixedbitset/0.4.0/")]
15
16 #![cfg_attr(not(feature = "std"), no_std)]
17
18 #[cfg(not(feature = "std"))]
19 extern crate alloc;
20 #[cfg(not(feature = "std"))]
21 use alloc::{
22 vec,
23 vec::Vec,
24 };
25
26 #[cfg(not(feature = "std"))]
27 use core as std;
28
29 mod range;
30
31 #[cfg(feature = "serde")]
32 extern crate serde;
33 #[cfg(feature = "serde")]
34 use serde::{Serialize, Deserialize};
35
36 use std::fmt::Write;
37 use std::fmt::{Display, Error, Formatter, Binary};
38
39 use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Index};
40 use std::cmp::{Ord, Ordering};
41 use std::iter::{Chain, FromIterator};
42 pub use range::IndexRange;
43
44 const BITS: usize = 32;
45 type Block = u32;
46
47 #[inline]
div_rem(x: usize, d: usize) -> (usize, usize)48 fn div_rem(x: usize, d: usize) -> (usize, usize)
49 {
50 (x / d, x % d)
51 }
52
53 /// `FixedBitSet` is a simple fixed size set of bits that each can
54 /// be enabled (1 / **true**) or disabled (0 / **false**).
55 ///
56 /// The bit set has a fixed capacity in terms of enabling bits (and the
57 /// capacity can grow using the `grow` method).
58 #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
59 #[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
60 pub struct FixedBitSet {
61 data: Vec<Block>,
62 /// length in bits
63 length: usize,
64 }
65
66 impl FixedBitSet
67 {
68 /// Create a new empty **FixedBitSet**.
new() -> Self69 pub const fn new() -> Self
70 {
71 FixedBitSet {
72 data: Vec::new(),
73 length: 0,
74 }
75 }
76
77 /// Create a new **FixedBitSet** with a specific number of bits,
78 /// all initially clear.
with_capacity(bits: usize) -> Self79 pub fn with_capacity(bits: usize) -> Self
80 {
81 let (mut blocks, rem) = div_rem(bits, BITS);
82 blocks += (rem > 0) as usize;
83 FixedBitSet {
84 data: vec![0; blocks],
85 length: bits,
86 }
87 }
88
89 /// Create a new **FixedBitSet** with a specific number of bits,
90 /// initialized from provided blocks.
91 ///
92 /// If the blocks are not the exact size needed for the capacity
93 /// they will be padded with zeros (if shorter) or truncated to
94 /// the capacity (if longer).
95 ///
96 /// For example:
97 /// ```
98 /// let data = vec![4];
99 /// let bs = fixedbitset::FixedBitSet::with_capacity_and_blocks(4, data);
100 /// assert_eq!(format!("{:b}", bs), "0010");
101 /// ```
with_capacity_and_blocks<I: IntoIterator<Item=Block>>(bits: usize, blocks: I) -> Self102 pub fn with_capacity_and_blocks<I: IntoIterator<Item=Block>>(bits: usize, blocks: I) -> Self
103 {
104 let (mut n_blocks, rem) = div_rem(bits, BITS);
105 n_blocks += (rem > 0) as usize;
106 let mut data: Vec<Block> = blocks.into_iter().collect();
107 // Pad data with zeros if smaller or truncate if larger
108 if data.len() != n_blocks {
109 data.resize(n_blocks, 0);
110 }
111 // Disable bits in blocks beyond capacity
112 let end = data.len() * 32;
113 for (block, mask) in Masks::new(bits..end, end) {
114 unsafe {
115 *data.get_unchecked_mut(block) &= !mask;
116 }
117 }
118 FixedBitSet {
119 data: data,
120 length: bits,
121 }
122 }
123
124 /// Grow capacity to **bits**, all new bits initialized to zero
grow(&mut self, bits: usize)125 pub fn grow(&mut self, bits: usize) {
126 let (mut blocks, rem) = div_rem(bits, BITS);
127 blocks += (rem > 0) as usize;
128 if bits > self.length {
129 self.length = bits;
130 self.data.resize(blocks, 0);
131 }
132 }
133
134 /// Return the length of the `FixedBitSet` in bits.
135 #[inline]
len(&self) -> usize136 pub fn len(&self) -> usize { self.length }
137
138 /// Return **true** if the bit is enabled in the **FixedBitSet**,
139 /// **false** otherwise.
140 ///
141 /// Note: bits outside the capacity are always disabled.
142 ///
143 /// Note: Also available with index syntax: `bitset[bit]`.
144 #[inline]
contains(&self, bit: usize) -> bool145 pub fn contains(&self, bit: usize) -> bool
146 {
147 let (block, i) = div_rem(bit, BITS);
148 match self.data.get(block) {
149 None => false,
150 Some(b) => (b & (1 << i)) != 0,
151 }
152 }
153
154 /// Clear all bits.
155 #[inline]
clear(&mut self)156 pub fn clear(&mut self)
157 {
158 for elt in &mut self.data[..] {
159 *elt = 0
160 }
161 }
162
163 /// Enable `bit`.
164 ///
165 /// **Panics** if **bit** is out of bounds.
166 #[inline]
insert(&mut self, bit: usize)167 pub fn insert(&mut self, bit: usize)
168 {
169 assert!(bit < self.length, "insert at index {} exceeds fixbitset size {}", bit, self.length);
170 let (block, i) = div_rem(bit, BITS);
171 unsafe {
172 *self.data.get_unchecked_mut(block) |= 1 << i;
173 }
174 }
175
176 /// Enable `bit`, and return its previous value.
177 ///
178 /// **Panics** if **bit** is out of bounds.
179 #[inline]
put(&mut self, bit: usize) -> bool180 pub fn put(&mut self, bit: usize) -> bool
181 {
182 assert!(bit < self.length, "put at index {} exceeds fixbitset size {}", bit, self.length);
183 let (block, i) = div_rem(bit, BITS);
184 unsafe {
185 let word = self.data.get_unchecked_mut(block);
186 let prev = *word & (1 << i) != 0;
187 *word |= 1 << i;
188 prev
189 }
190 }
191 /// Toggle `bit` (inverting its state).
192 ///
193 /// ***Panics*** if **bit** is out of bounds
194 #[inline]
toggle(&mut self, bit: usize)195 pub fn toggle(&mut self, bit: usize) {
196 assert!(bit < self.length, "toggle at index {} exceeds fixbitset size {}", bit, self.length);
197 let (block, i) = div_rem(bit, BITS);
198 unsafe {
199 *self.data.get_unchecked_mut(block) ^= 1 << i;
200 }
201 }
202 /// **Panics** if **bit** is out of bounds.
203 #[inline]
set(&mut self, bit: usize, enabled: bool)204 pub fn set(&mut self, bit: usize, enabled: bool)
205 {
206 assert!(bit < self.length, "set at index {} exceeds fixbitset size {}", bit, self.length);
207 let (block, i) = div_rem(bit, BITS);
208 unsafe {
209 let elt = self.data.get_unchecked_mut(block);
210 if enabled {
211 *elt |= 1 << i;
212 } else {
213 *elt &= !(1 << i);
214 }
215 }
216 }
217
218 /// Copies boolean value from specified bit to the specified bit.
219 ///
220 /// **Panics** if **to** is out of bounds.
221 #[inline]
copy_bit(&mut self, from: usize, to: usize)222 pub fn copy_bit(&mut self, from: usize, to: usize)
223 {
224 assert!(to < self.length, "copy at index {} exceeds fixbitset size {}", to, self.length);
225 let (to_block, t) = div_rem(to, BITS);
226 let enabled = self.contains(from);
227 unsafe {
228 let to_elt = self.data.get_unchecked_mut(to_block);
229 if enabled {
230 *to_elt |= 1 << t;
231 } else {
232 *to_elt &= !(1 << t);
233 }
234 }
235 }
236
237 /// Count the number of set bits in the given bit range.
238 ///
239 /// Use `..` to count the whole content of the bitset.
240 ///
241 /// **Panics** if the range extends past the end of the bitset.
242 #[inline]
count_ones<T: IndexRange>(&self, range: T) -> usize243 pub fn count_ones<T: IndexRange>(&self, range: T) -> usize
244 {
245 Masks::new(range, self.length)
246 .map(|(block, mask)| unsafe {
247 let value = *self.data.get_unchecked(block);
248 (value & mask).count_ones() as usize
249 })
250 .sum()
251 }
252
253 /// Sets every bit in the given range to the given state (`enabled`)
254 ///
255 /// Use `..` to set the whole bitset.
256 ///
257 /// **Panics** if the range extends past the end of the bitset.
258 #[inline]
set_range<T: IndexRange>(&mut self, range: T, enabled: bool)259 pub fn set_range<T: IndexRange>(&mut self, range: T, enabled: bool)
260 {
261 for (block, mask) in Masks::new(range, self.length) {
262 unsafe {
263 if enabled {
264 *self.data.get_unchecked_mut(block) |= mask;
265 } else {
266 *self.data.get_unchecked_mut(block) &= !mask;
267 }
268 }
269 }
270 }
271
272 /// Enables every bit in the given range.
273 ///
274 /// Use `..` to make the whole bitset ones.
275 ///
276 /// **Panics** if the range extends past the end of the bitset.
277 #[inline]
insert_range<T: IndexRange>(&mut self, range: T)278 pub fn insert_range<T: IndexRange>(&mut self, range: T)
279 {
280 self.set_range(range, true);
281 }
282
283 /// Toggles (inverts) every bit in the given range.
284 ///
285 /// Use `..` to toggle the whole bitset.
286 ///
287 /// **Panics** if the range extends past the end of the bitset.
288 #[inline]
toggle_range<T: IndexRange>(&mut self, range: T)289 pub fn toggle_range<T: IndexRange>(&mut self, range: T)
290 {
291 for (block, mask) in Masks::new(range, self.length) {
292 unsafe {
293 *self.data.get_unchecked_mut(block) ^= mask;
294 }
295 }
296 }
297
298 /// View the bitset as a slice of `u32` blocks
299 #[inline]
as_slice(&self) -> &[u32]300 pub fn as_slice(&self) -> &[u32]
301 {
302 &self.data
303 }
304
305 /// View the bitset as a mutable slice of `u32` blocks. Writing past the bitlength in the last
306 /// will cause `contains` to return potentially incorrect results for bits past the bitlength.
307 #[inline]
as_mut_slice(&mut self) -> &mut [u32]308 pub fn as_mut_slice(&mut self) -> &mut [u32]
309 {
310 &mut self.data
311 }
312
313 /// Iterates over all enabled bits.
314 ///
315 /// Iterator element is the index of the `1` bit, type `usize`.
316 #[inline]
ones(&self) -> Ones317 pub fn ones(&self) -> Ones {
318 match self.as_slice().split_first() {
319 Some((&block, rem)) => {
320 Ones {
321 bitset: block,
322 block_idx: 0,
323 remaining_blocks: rem
324 }
325 }
326 None => {
327 Ones {
328 bitset: 0,
329 block_idx: 0,
330 remaining_blocks: &[]
331 }
332 }
333 }
334 }
335
336 /// Returns a lazy iterator over the intersection of two `FixedBitSet`s
intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a>337 pub fn intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a>
338 {
339 Intersection {
340 iter: self.ones(),
341 other: other,
342 }
343 }
344
345 /// Returns a lazy iterator over the union of two `FixedBitSet`s.
union<'a>(&'a self, other: &'a FixedBitSet) -> Union<'a>346 pub fn union<'a>(&'a self, other: &'a FixedBitSet) -> Union<'a>
347 {
348 Union {
349 iter: self.ones().chain(other.difference(self)),
350 }
351 }
352
353 /// Returns a lazy iterator over the difference of two `FixedBitSet`s. The difference of `a`
354 /// and `b` is the elements of `a` which are not in `b`.
difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a>355 pub fn difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a>
356 {
357 Difference {
358 iter: self.ones(),
359 other: other,
360 }
361 }
362
363 /// Returns a lazy iterator over the symmetric difference of two `FixedBitSet`s.
364 /// The symmetric difference of `a` and `b` is the elements of one, but not both, sets.
symmetric_difference<'a>(&'a self, other: &'a FixedBitSet) -> SymmetricDifference<'a>365 pub fn symmetric_difference<'a>(&'a self, other: &'a FixedBitSet) -> SymmetricDifference<'a>
366 {
367 SymmetricDifference {
368 iter: self.difference(other).chain(other.difference(self)),
369 }
370 }
371
372 /// In-place union of two `FixedBitSet`s.
373 ///
374 /// On calling this method, `self`'s capacity may be increased to match `other`'s.
union_with(&mut self, other: &FixedBitSet)375 pub fn union_with(&mut self, other: &FixedBitSet)
376 {
377 if other.len() >= self.len() {
378 self.grow(other.len());
379 }
380 for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
381 *x |= *y;
382 }
383 }
384
385 /// In-place intersection of two `FixedBitSet`s.
386 ///
387 /// On calling this method, `self`'s capacity will remain the same as before.
intersect_with(&mut self, other: &FixedBitSet)388 pub fn intersect_with(&mut self, other: &FixedBitSet)
389 {
390 for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
391 *x &= *y;
392 }
393 let mn = std::cmp::min(self.data.len(), other.data.len());
394 for wd in &mut self.data[mn..] {
395 *wd = 0;
396 }
397 }
398
399 /// In-place difference of two `FixedBitSet`s.
400 ///
401 /// On calling this method, `self`'s capacity will remain the same as before.
difference_with(&mut self, other: &FixedBitSet)402 pub fn difference_with(&mut self, other: &FixedBitSet)
403 {
404 for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
405 *x &= !*y;
406 }
407
408 // There's no need to grow self or do any other adjustments.
409 //
410 // * If self is longer than other, the bits at the end of self won't be affected since other
411 // has them implicitly set to 0.
412 // * If other is longer than self, the bits at the end of other are irrelevant since self
413 // has them set to 0 anyway.
414 }
415
416 /// In-place symmetric difference of two `FixedBitSet`s.
417 ///
418 /// On calling this method, `self`'s capacity may be increased to match `other`'s.
symmetric_difference_with(&mut self, other: &FixedBitSet)419 pub fn symmetric_difference_with(&mut self, other: &FixedBitSet)
420 {
421 if other.len() >= self.len() {
422 self.grow(other.len());
423 }
424 for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
425 *x ^= *y;
426 }
427 }
428
429 /// Returns `true` if `self` has no elements in common with `other`. This
430 /// is equivalent to checking for an empty intersection.
is_disjoint(&self, other: &FixedBitSet) -> bool431 pub fn is_disjoint(&self, other: &FixedBitSet) -> bool {
432 self.data.iter().zip(other.data.iter()).all(|(x, y)| x & y == 0)
433 }
434
435 /// Returns `true` if the set is a subset of another, i.e. `other` contains
436 /// at least all the values in `self`.
is_subset(&self, other: &FixedBitSet) -> bool437 pub fn is_subset(&self, other: &FixedBitSet) -> bool {
438 self.data.iter().zip(other.data.iter()).all(|(x, y)| x & !y == 0) &&
439 self.data.iter().skip(other.data.len()).all(|x| *x == 0)
440 }
441
442 /// Returns `true` if the set is a superset of another, i.e. `self` contains
443 /// at least all the values in `other`.
is_superset(&self, other: &FixedBitSet) -> bool444 pub fn is_superset(&self, other: &FixedBitSet) -> bool {
445 other.is_subset(self)
446 }
447 }
448
449 impl Binary for FixedBitSet {
fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>450 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
451 if f.alternate() {
452 f.write_str("0b")?;
453 }
454
455 for i in 0..self.length {
456 if self[i] {
457 f.write_char('1')?;
458 } else {
459 f.write_char('0')?;
460 }
461 }
462
463 Ok(())
464 }
465 }
466
467 impl Display for FixedBitSet {
fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>468 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
469 Binary::fmt(&self, f)
470 }
471 }
472
473 /// An iterator producing elements in the difference of two sets.
474 ///
475 /// This struct is created by the [`FixedBitSet::difference`] method.
476 pub struct Difference<'a> {
477 iter: Ones<'a>,
478 other: &'a FixedBitSet,
479 }
480
481 impl<'a> Iterator for Difference<'a> {
482 type Item = usize;
483
484 #[inline]
next(&mut self) -> Option<Self::Item>485 fn next(&mut self) -> Option<Self::Item> {
486 while let Some(nxt) = self.iter.next() {
487 if !self.other.contains(nxt) {
488 return Some(nxt);
489 }
490 }
491 None
492 }
493 }
494
495 /// An iterator producing elements in the symmetric difference of two sets.
496 ///
497 /// This struct is created by the [`FixedBitSet::symmetric_difference`] method.
498 pub struct SymmetricDifference<'a> {
499 iter: Chain<Difference<'a>, Difference<'a>>,
500 }
501
502 impl<'a> Iterator for SymmetricDifference<'a> {
503 type Item = usize;
504
505 #[inline]
next(&mut self) -> Option<Self::Item>506 fn next(&mut self) -> Option<Self::Item> {
507 self.iter.next()
508 }
509 }
510
511
512 /// An iterator producing elements in the intersection of two sets.
513 ///
514 /// This struct is created by the [`FixedBitSet::intersection`] method.
515 pub struct Intersection<'a> {
516 iter: Ones<'a>,
517 other: &'a FixedBitSet,
518 }
519
520 impl<'a> Iterator for Intersection<'a> {
521 type Item = usize; // the bit position of the '1'
522
523 #[inline]
next(&mut self) -> Option<Self::Item>524 fn next(&mut self) -> Option<Self::Item> {
525 while let Some(nxt) = self.iter.next() {
526 if self.other.contains(nxt) {
527 return Some(nxt);
528 }
529 }
530 None
531 }
532 }
533
534 /// An iterator producing elements in the union of two sets.
535 ///
536 /// This struct is created by the [`FixedBitSet::union`] method.
537 pub struct Union<'a> {
538 iter: Chain<Ones<'a>, Difference<'a>>,
539 }
540
541 impl<'a> Iterator for Union<'a> {
542 type Item = usize;
543
544 #[inline]
next(&mut self) -> Option<Self::Item>545 fn next(&mut self) -> Option<Self::Item> {
546 self.iter.next()
547 }
548 }
549
550
551 struct Masks {
552 first_block: usize,
553 first_mask: Block,
554 last_block: usize,
555 last_mask: Block,
556 }
557
558 impl Masks {
559 #[inline]
new<T: IndexRange>(range: T, length: usize) -> Masks560 fn new<T: IndexRange>(range: T, length: usize) -> Masks {
561 let start = range.start().unwrap_or(0);
562 let end = range.end().unwrap_or(length);
563 assert!(start <= end && end <= length,
564 "invalid range {}..{} for a fixedbitset of size {}", start, end, length);
565
566 let (first_block, first_rem) = div_rem(start, BITS);
567 let (last_block, last_rem) = div_rem(end, BITS);
568
569 Masks {
570 first_block: first_block as usize,
571 first_mask: Block::max_value() << first_rem,
572 last_block: last_block as usize,
573 last_mask: (Block::max_value() >> 1) >> (BITS - last_rem - 1),
574 // this is equivalent to `MAX >> (BITS - x)` with correct semantics when x == 0.
575 }
576 }
577 }
578
579 impl Iterator for Masks {
580 type Item = (usize, Block);
581 #[inline]
next(&mut self) -> Option<Self::Item>582 fn next(&mut self) -> Option<Self::Item> {
583 match self.first_block.cmp(&self.last_block) {
584 Ordering::Less => {
585 let res = (self.first_block, self.first_mask);
586 self.first_block += 1;
587 self.first_mask = !0;
588 Some(res)
589 }
590 Ordering::Equal => {
591 let mask = self.first_mask & self.last_mask;
592 let res = if mask == 0 {
593 None
594 } else {
595 Some((self.first_block, mask))
596 };
597 self.first_block += 1;
598 res
599 }
600 Ordering::Greater => None,
601 }
602 }
603 }
604
605
606 /// An iterator producing the indices of the set bit in a set.
607 ///
608 /// This struct is created by the [`FixedBitSet::ones`] method.
609 pub struct Ones<'a> {
610 bitset: Block,
611 block_idx: usize,
612 remaining_blocks: &'a [Block],
613 }
614
615 impl<'a> Iterator for Ones<'a> {
616 type Item = usize; // the bit position of the '1'
617
618 #[inline]
next(&mut self) -> Option<Self::Item>619 fn next(&mut self) -> Option<Self::Item> {
620 while self.bitset == 0 {
621 if self.remaining_blocks.is_empty() {
622 return None;
623 }
624 self.bitset = self.remaining_blocks[0];
625 self.remaining_blocks = &self.remaining_blocks[1..];
626 self.block_idx += 1;
627 }
628 let t = self.bitset & (0 as Block).wrapping_sub(self.bitset);
629 let r = self.bitset.trailing_zeros() as usize;
630 self.bitset ^= t;
631 Some(self.block_idx * BITS + r)
632 }
633 }
634
635 impl Clone for FixedBitSet
636 {
637 #[inline]
clone(&self) -> Self638 fn clone(&self) -> Self
639 {
640 FixedBitSet {
641 data: self.data.clone(),
642 length: self.length,
643 }
644 }
645 }
646
647 /// Return **true** if the bit is enabled in the bitset,
648 /// or **false** otherwise.
649 ///
650 /// Note: bits outside the capacity are always disabled, and thus
651 /// indexing a FixedBitSet will not panic.
652 impl Index<usize> for FixedBitSet
653 {
654 type Output = bool;
655
656 #[inline]
index(&self, bit: usize) -> &bool657 fn index(&self, bit: usize) -> &bool
658 {
659 if self.contains(bit) {
660 &true
661 } else {
662 &false
663 }
664 }
665 }
666
667 /// Sets the bit at index **i** to **true** for each item **i** in the input **src**.
668 impl Extend<usize> for FixedBitSet
669 {
extend<I: IntoIterator<Item=usize>>(&mut self, src: I)670 fn extend<I: IntoIterator<Item=usize>>(&mut self, src: I) {
671 let iter = src.into_iter();
672 for i in iter {
673 if i >= self.len() {
674 self.grow(i + 1);
675 }
676 self.put(i);
677 }
678 }
679 }
680
681 /// Return a FixedBitSet containing bits set to **true** for every bit index in
682 /// the iterator, other bits are set to **false**.
683 impl FromIterator<usize> for FixedBitSet
684 {
from_iter<I: IntoIterator<Item=usize>>(src: I) -> Self685 fn from_iter<I: IntoIterator<Item=usize>>(src: I) -> Self {
686 let mut fbs = FixedBitSet::with_capacity(0);
687 fbs.extend(src);
688 fbs
689 }
690 }
691
692 impl <'a> BitAnd for &'a FixedBitSet
693 {
694 type Output = FixedBitSet;
bitand(self, other: &FixedBitSet) -> FixedBitSet695 fn bitand(self, other: &FixedBitSet) -> FixedBitSet {
696 let (short, long) = {
697 if self.len() <= other.len() {
698 (&self.data, &other.data)
699 } else {
700 (&other.data, &self.data)
701 }
702 };
703 let mut data = short.clone();
704 for (data, block) in data.iter_mut().zip(long.iter()) {
705 *data &= *block;
706 }
707 let len = std::cmp::min(self.len(), other.len());
708 FixedBitSet{data: data, length: len}
709 }
710 }
711
712
713 impl <'a> BitAndAssign for FixedBitSet
714 {
bitand_assign(&mut self, other: Self)715 fn bitand_assign(&mut self, other: Self) {
716 self.intersect_with(&other);
717 }
718 }
719
720 impl <'a> BitAndAssign<&Self> for FixedBitSet
721 {
bitand_assign(&mut self, other: &Self)722 fn bitand_assign(&mut self, other: &Self) {
723 self.intersect_with(other);
724 }
725 }
726
727 impl <'a> BitOr for &'a FixedBitSet
728 {
729 type Output = FixedBitSet;
bitor(self, other: &FixedBitSet) -> FixedBitSet730 fn bitor(self, other: &FixedBitSet) -> FixedBitSet {
731 let (short, long) = {
732 if self.len() <= other.len() {
733 (&self.data, &other.data)
734 } else {
735 (&other.data, &self.data)
736 }
737 };
738 let mut data = long.clone();
739 for (data, block) in data.iter_mut().zip(short.iter()) {
740 *data |= *block;
741 }
742 let len = std::cmp::max(self.len(), other.len());
743 FixedBitSet{data: data, length: len}
744 }
745 }
746
747 impl <'a> BitOrAssign for FixedBitSet
748 {
bitor_assign(&mut self, other: Self)749 fn bitor_assign(&mut self, other: Self) {
750 self.union_with(&other);
751 }
752 }
753
754 impl <'a> BitOrAssign<&Self> for FixedBitSet
755 {
bitor_assign(&mut self, other: &Self)756 fn bitor_assign(&mut self, other: &Self) {
757 self.union_with(other);
758 }
759 }
760
761 impl <'a> BitXor for &'a FixedBitSet
762 {
763 type Output = FixedBitSet;
bitxor(self, other: &FixedBitSet) -> FixedBitSet764 fn bitxor(self, other: &FixedBitSet) -> FixedBitSet {
765 let (short, long) = {
766 if self.len() <= other.len() {
767 (&self.data, &other.data)
768 } else {
769 (&other.data, &self.data)
770 }
771 };
772 let mut data = long.clone();
773 for (data, block) in data.iter_mut().zip(short.iter()) {
774 *data ^= *block;
775 }
776 let len = std::cmp::max(self.len(), other.len());
777 FixedBitSet{data: data, length: len}
778 }
779 }
780
781 impl <'a> BitXorAssign for FixedBitSet
782 {
bitxor_assign(&mut self, other: Self)783 fn bitxor_assign(&mut self, other: Self) {
784 self.symmetric_difference_with(&other);
785 }
786 }
787
788 impl <'a> BitXorAssign<&Self> for FixedBitSet
789 {
bitxor_assign(&mut self, other: &Self)790 fn bitxor_assign(&mut self, other: &Self) {
791 self.symmetric_difference_with(other);
792 }
793 }
794
795 #[test]
it_works()796 fn it_works() {
797 const N: usize = 50;
798 let mut fb = FixedBitSet::with_capacity(N);
799
800
801 for i in 0..(N + 10) {
802 assert_eq!(fb.contains(i), false);
803 }
804
805 fb.insert(10);
806 fb.set(11, false);
807 fb.set(12, false);
808 fb.set(12, true);
809 fb.set(N-1, true);
810
811 assert!(fb.contains(10));
812 assert!(!fb.contains(11));
813 assert!(fb.contains(12));
814 assert!(fb.contains(N-1));
815 for i in 0..N {
816 let contain = i == 10 || i == 12 || i == N - 1;
817 assert_eq!(contain, fb[i]);
818 }
819
820 fb.clear();
821 }
822
823 #[test]
with_blocks()824 fn with_blocks() {
825 let fb = FixedBitSet::with_capacity_and_blocks(50, vec![8u32, 0u32]);
826 assert!(fb.contains(3));
827
828 let ones: Vec<_> = fb.ones().collect();
829 assert_eq!(ones.len(), 1);
830 }
831
832 #[test]
with_blocks_too_small()833 fn with_blocks_too_small() {
834 let mut fb = FixedBitSet::with_capacity_and_blocks(500, vec![8u32, 0u32]);
835 fb.insert(400);
836 assert!(fb.contains(400));
837 }
838
839 #[test]
with_blocks_too_big()840 fn with_blocks_too_big() {
841 let fb = FixedBitSet::with_capacity_and_blocks(1, vec![8u32]);
842
843 // since capacity is 1, 3 shouldn't be set here
844 assert!(!fb.contains(3));
845 }
846
847 #[test]
with_blocks_too_big_range_check()848 fn with_blocks_too_big_range_check() {
849 let fb = FixedBitSet::with_capacity_and_blocks(1, vec![0xff]);
850
851 // since capacity is 1, only 0 should be set
852 assert!(fb.contains(0));
853 for i in 1..0xff {
854 assert!(!fb.contains(i));
855 }
856 }
857
858 #[test]
grow()859 fn grow() {
860 let mut fb = FixedBitSet::with_capacity(48);
861 for i in 0..fb.len() {
862 fb.set(i, true);
863 }
864
865 let old_len = fb.len();
866 fb.grow(72);
867 for j in 0..fb.len() {
868 assert_eq!(fb.contains(j), j < old_len);
869 }
870 fb.set(64, true);
871 assert!(fb.contains(64));
872 }
873
874 #[test]
test_toggle()875 fn test_toggle() {
876 let mut fb = FixedBitSet::with_capacity(16);
877 fb.toggle(1);
878 fb.put(2);
879 fb.toggle(2);
880 fb.put(3);
881 assert!(fb.contains(1));
882 assert!(!fb.contains(2));
883 assert!(fb.contains(3));
884 }
885
886 #[test]
copy_bit()887 fn copy_bit() {
888 let mut fb = FixedBitSet::with_capacity(48);
889 for i in 0..fb.len() {
890 fb.set(i, true);
891 }
892 fb.set(42, false);
893 fb.copy_bit(42, 2);
894 assert!(!fb.contains(42));
895 assert!(!fb.contains(2));
896 assert!(fb.contains(1));
897 fb.copy_bit(1, 42);
898 assert!(fb.contains(42));
899 fb.copy_bit(1024, 42);
900 assert!(!fb[42]);
901 }
902
903 #[test]
count_ones()904 fn count_ones() {
905 let mut fb = FixedBitSet::with_capacity(100);
906 fb.set(11, true);
907 fb.set(12, true);
908 fb.set(7, true);
909 fb.set(35, true);
910 fb.set(40, true);
911 fb.set(77, true);
912 fb.set(95, true);
913 fb.set(50, true);
914 fb.set(99, true);
915 assert_eq!(fb.count_ones(..7), 0);
916 assert_eq!(fb.count_ones(..8), 1);
917 assert_eq!(fb.count_ones(..11), 1);
918 assert_eq!(fb.count_ones(..12), 2);
919 assert_eq!(fb.count_ones(..13), 3);
920 assert_eq!(fb.count_ones(..35), 3);
921 assert_eq!(fb.count_ones(..36), 4);
922 assert_eq!(fb.count_ones(..40), 4);
923 assert_eq!(fb.count_ones(..41), 5);
924 assert_eq!(fb.count_ones(50..), 4);
925 assert_eq!(fb.count_ones(70..95), 1);
926 assert_eq!(fb.count_ones(70..96), 2);
927 assert_eq!(fb.count_ones(70..99), 2);
928 assert_eq!(fb.count_ones(..), 9);
929 assert_eq!(fb.count_ones(0..100), 9);
930 assert_eq!(fb.count_ones(0..0), 0);
931 assert_eq!(fb.count_ones(100..100), 0);
932 assert_eq!(fb.count_ones(7..), 9);
933 assert_eq!(fb.count_ones(8..), 8);
934 }
935
936 #[test]
ones()937 fn ones() {
938 let mut fb = FixedBitSet::with_capacity(100);
939 fb.set(11, true);
940 fb.set(12, true);
941 fb.set(7, true);
942 fb.set(35, true);
943 fb.set(40, true);
944 fb.set(77, true);
945 fb.set(95, true);
946 fb.set(50, true);
947 fb.set(99, true);
948
949 let ones: Vec<_> = fb.ones().collect();
950
951 assert_eq!(vec![7, 11, 12, 35, 40, 50, 77, 95, 99], ones);
952 }
953
954 #[test]
iter_ones_range()955 fn iter_ones_range() {
956 fn test_range(from: usize, to: usize, capa: usize) {
957 assert!(to <= capa);
958 let mut fb = FixedBitSet::with_capacity(capa);
959 for i in from..to {
960 fb.insert(i);
961 }
962 let ones: Vec<_> = fb.ones().collect();
963 let expected: Vec<_> = (from..to).collect();
964 assert_eq!(expected, ones);
965 }
966
967 for i in 0..100 {
968 test_range(i, 100, 100);
969 test_range(0, i, 100);
970 }
971 }
972
973 #[should_panic]
974 #[test]
count_ones_oob()975 fn count_ones_oob() {
976 let fb = FixedBitSet::with_capacity(100);
977 fb.count_ones(90..101);
978 }
979
980 #[should_panic]
981 #[test]
count_ones_negative_range()982 fn count_ones_negative_range() {
983 let fb = FixedBitSet::with_capacity(100);
984 fb.count_ones(90..80);
985 }
986
987 #[test]
count_ones_panic()988 fn count_ones_panic() {
989 for i in 1..128 {
990 let fb = FixedBitSet::with_capacity(i);
991 for j in 0..fb.len() + 1 {
992 for k in j..fb.len() + 1 {
993 assert_eq!(fb.count_ones(j..k), 0);
994 }
995 }
996 }
997 }
998
999
1000 #[test]
default()1001 fn default() {
1002 let fb = FixedBitSet::default();
1003 assert_eq!(fb.len(), 0);
1004 }
1005
1006 #[test]
insert_range()1007 fn insert_range() {
1008 let mut fb = FixedBitSet::with_capacity(97);
1009 fb.insert_range(..3);
1010 fb.insert_range(9..32);
1011 fb.insert_range(37..81);
1012 fb.insert_range(90..);
1013 for i in 0..97 {
1014 assert_eq!(fb.contains(i), i<3 || 9<=i&&i<32 || 37<=i&&i<81 || 90<=i);
1015 }
1016 assert!(!fb.contains(97));
1017 assert!(!fb.contains(127));
1018 assert!(!fb.contains(128));
1019 }
1020
1021 #[test]
set_range()1022 fn set_range() {
1023 let mut fb = FixedBitSet::with_capacity(48);
1024 fb.insert_range(..);
1025
1026 fb.set_range(..32, false);
1027 fb.set_range(37.., false);
1028 fb.set_range(5..9, true);
1029 fb.set_range(40..40, true);
1030
1031 for i in 0..48 {
1032 assert_eq!(fb.contains(i), 5<=i&&i<9 || 32<=i&&i<37);
1033 }
1034 assert!(!fb.contains(48));
1035 assert!(!fb.contains(64));
1036 }
1037
1038 #[test]
toggle_range()1039 fn toggle_range() {
1040 let mut fb = FixedBitSet::with_capacity(40);
1041 fb.insert_range(..10);
1042 fb.insert_range(34..38);
1043
1044 fb.toggle_range(5..12);
1045 fb.toggle_range(30..);
1046
1047 for i in 0..40 {
1048 assert_eq!(fb.contains(i), i<5 || 10<=i&&i<12 || 30<=i&&i<34 || 38<=i);
1049 }
1050 assert!(!fb.contains(40));
1051 assert!(!fb.contains(64));
1052 }
1053
1054 #[test]
bitand_equal_lengths()1055 fn bitand_equal_lengths() {
1056 let len = 109;
1057 let a_end = 59;
1058 let b_start = 23;
1059 let mut a = FixedBitSet::with_capacity(len);
1060 let mut b = FixedBitSet::with_capacity(len);
1061 a.set_range(..a_end, true);
1062 b.set_range(b_start.., true);
1063 let ab = &a & &b;
1064 for i in 0..b_start {
1065 assert!(!ab.contains(i));
1066 }
1067 for i in b_start..a_end {
1068 assert!(ab.contains(i));
1069 }
1070 for i in a_end..len {
1071 assert!(!ab.contains(i));
1072 }
1073 assert_eq!(a.len(), ab.len());
1074 }
1075
1076 #[test]
bitand_first_smaller()1077 fn bitand_first_smaller() {
1078 let a_len = 113;
1079 let b_len = 137;
1080 let len = std::cmp::min(a_len, b_len);
1081 let a_end = 97;
1082 let b_start = 89;
1083 let mut a = FixedBitSet::with_capacity(a_len);
1084 let mut b = FixedBitSet::with_capacity(b_len);
1085 a.set_range(..a_end, true);
1086 b.set_range(b_start.., true);
1087 let ab = &a & &b;
1088 for i in 0..b_start {
1089 assert!(!ab.contains(i));
1090 }
1091 for i in b_start..a_end {
1092 assert!(ab.contains(i));
1093 }
1094 for i in a_end..len {
1095 assert!(!ab.contains(i));
1096 }
1097 assert_eq!(a.len(), ab.len());
1098 }
1099
1100 #[test]
bitand_first_larger()1101 fn bitand_first_larger() {
1102 let a_len = 173;
1103 let b_len = 137;
1104 let len = std::cmp::min(a_len, b_len);
1105 let a_end = 107;
1106 let b_start = 43;
1107 let mut a = FixedBitSet::with_capacity(a_len);
1108 let mut b = FixedBitSet::with_capacity(b_len);
1109 a.set_range(..a_end, true);
1110 b.set_range(b_start.., true);
1111 let ab = &a & &b;
1112 for i in 0..b_start {
1113 assert!(!ab.contains(i));
1114 }
1115 for i in b_start..a_end {
1116 assert!(ab.contains(i));
1117 }
1118 for i in a_end..len {
1119 assert!(!ab.contains(i));
1120 }
1121 assert_eq!(b.len(), ab.len());
1122 }
1123
1124 #[test]
intersection()1125 fn intersection() {
1126 let len = 109;
1127 let a_end = 59;
1128 let b_start = 23;
1129 let mut a = FixedBitSet::with_capacity(len);
1130 let mut b = FixedBitSet::with_capacity(len);
1131 a.set_range(..a_end, true);
1132 b.set_range(b_start.., true);
1133
1134 let mut ab = a.intersection(&b).collect::<FixedBitSet>();
1135
1136 for i in 0..b_start {
1137 assert!(!ab.contains(i));
1138 }
1139 for i in b_start..a_end {
1140 assert!(ab.contains(i));
1141 }
1142 for i in a_end..len {
1143 assert!(!ab.contains(i));
1144 }
1145
1146 a.intersect_with(&b);
1147 // intersection + collect produces the same results but with a shorter length.
1148 ab.grow(a.len());
1149 assert_eq!(ab, a, "intersection and intersect_with produce the same results");
1150 }
1151
1152 #[test]
union()1153 fn union() {
1154 let a_len = 173;
1155 let b_len = 137;
1156 let a_start = 139;
1157 let b_end = 107;
1158 let mut a = FixedBitSet::with_capacity(a_len);
1159 let mut b = FixedBitSet::with_capacity(b_len);
1160 a.set_range(a_start.., true);
1161 b.set_range(..b_end, true);
1162 let ab = a.union(&b).collect::<FixedBitSet>();
1163 for i in a_start..a_len {
1164 assert!(ab.contains(i));
1165 }
1166 for i in 0..b_end {
1167 assert!(ab.contains(i));
1168 }
1169 for i in b_end..a_start {
1170 assert!(!ab.contains(i));
1171 }
1172
1173 a.union_with(&b);
1174 assert_eq!(ab, a, "union and union_with produce the same results");
1175 }
1176
1177 #[test]
difference()1178 fn difference() {
1179 let a_len = 83;
1180 let b_len = 151;
1181 let a_start = 0;
1182 let a_end = 79;
1183 let b_start = 53;
1184 let mut a = FixedBitSet::with_capacity(a_len);
1185 let mut b = FixedBitSet::with_capacity(b_len);
1186 a.set_range(a_start..a_end, true);
1187 b.set_range(b_start..b_len, true);
1188 let mut a_diff_b = a.difference(&b).collect::<FixedBitSet>();
1189 for i in a_start..b_start {
1190 assert!(a_diff_b.contains(i));
1191 }
1192 for i in b_start..b_len {
1193 assert!(!a_diff_b.contains(i));
1194 }
1195
1196 a.difference_with(&b);
1197 // difference + collect produces the same results but with a shorter length.
1198 a_diff_b.grow(a.len());
1199 assert_eq!(a_diff_b, a, "difference and difference_with produce the same results");
1200 }
1201
1202 #[test]
symmetric_difference()1203 fn symmetric_difference() {
1204 let a_len = 83;
1205 let b_len = 151;
1206 let a_start = 47;
1207 let a_end = 79;
1208 let b_start = 53;
1209 let mut a = FixedBitSet::with_capacity(a_len);
1210 let mut b = FixedBitSet::with_capacity(b_len);
1211 a.set_range(a_start..a_end, true);
1212 b.set_range(b_start..b_len, true);
1213 let a_sym_diff_b = a.symmetric_difference(&b).collect::<FixedBitSet>();
1214 for i in 0..a_start {
1215 assert!(!a_sym_diff_b.contains(i));
1216 }
1217 for i in a_start..b_start {
1218 assert!(a_sym_diff_b.contains(i));
1219 }
1220 for i in b_start..a_end {
1221 assert!(!a_sym_diff_b.contains(i));
1222 }
1223 for i in a_end..b_len {
1224 assert!(a_sym_diff_b.contains(i));
1225 }
1226
1227 a.symmetric_difference_with(&b);
1228 assert_eq!(a_sym_diff_b, a, "symmetric_difference and _with produce the same results");
1229 }
1230
1231 #[test]
bitor_equal_lengths()1232 fn bitor_equal_lengths() {
1233 let len = 109;
1234 let a_start = 17;
1235 let a_end = 23;
1236 let b_start = 19;
1237 let b_end = 59;
1238 let mut a = FixedBitSet::with_capacity(len);
1239 let mut b = FixedBitSet::with_capacity(len);
1240 a.set_range(a_start..a_end, true);
1241 b.set_range(b_start..b_end, true);
1242 let ab = &a | &b;
1243 for i in 0..a_start {
1244 assert!(!ab.contains(i));
1245 }
1246 for i in a_start..b_end {
1247 assert!(ab.contains(i));
1248 }
1249 for i in b_end..len {
1250 assert!(!ab.contains(i));
1251 }
1252 assert_eq!(ab.len(), len);
1253 }
1254
1255 #[test]
bitor_first_smaller()1256 fn bitor_first_smaller() {
1257 let a_len = 113;
1258 let b_len = 137;
1259 let a_end = 89;
1260 let b_start = 97;
1261 let mut a = FixedBitSet::with_capacity(a_len);
1262 let mut b = FixedBitSet::with_capacity(b_len);
1263 a.set_range(..a_end, true);
1264 b.set_range(b_start.., true);
1265 let ab = &a | &b;
1266 for i in 0..a_end {
1267 assert!(ab.contains(i));
1268 }
1269 for i in a_end..b_start {
1270 assert!(!ab.contains(i));
1271 }
1272 for i in b_start..b_len {
1273 assert!(ab.contains(i));
1274 }
1275 assert_eq!(b_len, ab.len());
1276 }
1277
1278 #[test]
bitor_first_larger()1279 fn bitor_first_larger() {
1280 let a_len = 173;
1281 let b_len = 137;
1282 let a_start = 139;
1283 let b_end = 107;
1284 let mut a = FixedBitSet::with_capacity(a_len);
1285 let mut b = FixedBitSet::with_capacity(b_len);
1286 a.set_range(a_start.., true);
1287 b.set_range(..b_end, true);
1288 let ab = &a | &b;
1289 for i in a_start..a_len {
1290 assert!(ab.contains(i));
1291 }
1292 for i in 0..b_end {
1293 assert!(ab.contains(i));
1294 }
1295 for i in b_end..a_start {
1296 assert!(!ab.contains(i));
1297 }
1298 assert_eq!(a_len, ab.len());
1299 }
1300
1301 #[test]
bitxor_equal_lengths()1302 fn bitxor_equal_lengths() {
1303 let len = 109;
1304 let a_end = 59;
1305 let b_start = 23;
1306 let mut a = FixedBitSet::with_capacity(len);
1307 let mut b = FixedBitSet::with_capacity(len);
1308 a.set_range(..a_end, true);
1309 b.set_range(b_start.., true);
1310 let ab = &a ^ &b;
1311 for i in 0..b_start {
1312 assert!(ab.contains(i));
1313 }
1314 for i in b_start..a_end {
1315 assert!(!ab.contains(i));
1316 }
1317 for i in a_end..len {
1318 assert!(ab.contains(i));
1319 }
1320 assert_eq!(a.len(), ab.len());
1321 }
1322
1323 #[test]
bitxor_first_smaller()1324 fn bitxor_first_smaller() {
1325 let a_len = 113;
1326 let b_len = 137;
1327 let len = std::cmp::max(a_len, b_len);
1328 let a_end = 97;
1329 let b_start = 89;
1330 let mut a = FixedBitSet::with_capacity(a_len);
1331 let mut b = FixedBitSet::with_capacity(b_len);
1332 a.set_range(..a_end, true);
1333 b.set_range(b_start.., true);
1334 let ab = &a ^ &b;
1335 for i in 0..b_start {
1336 assert!(ab.contains(i));
1337 }
1338 for i in b_start..a_end {
1339 assert!(!ab.contains(i));
1340 }
1341 for i in a_end..len {
1342 assert!(ab.contains(i));
1343 }
1344 assert_eq!(b.len(), ab.len());
1345 }
1346
1347 #[test]
bitxor_first_larger()1348 fn bitxor_first_larger() {
1349 let a_len = 173;
1350 let b_len = 137;
1351 let len = std::cmp::max(a_len, b_len);
1352 let a_end = 107;
1353 let b_start = 43;
1354 let mut a = FixedBitSet::with_capacity(a_len);
1355 let mut b = FixedBitSet::with_capacity(b_len);
1356 a.set_range(..a_end, true);
1357 b.set_range(b_start.., true);
1358 let ab = &a ^ &b;
1359 for i in 0..b_start {
1360 assert!(ab.contains(i));
1361 }
1362 for i in b_start..a_end {
1363 assert!(!ab.contains(i));
1364 }
1365 for i in a_end..b_len {
1366 assert!(ab.contains(i));
1367 }
1368 for i in b_len..len {
1369 assert!(!ab.contains(i));
1370 }
1371 assert_eq!(a.len(), ab.len());
1372 }
1373
1374 #[test]
bitand_assign_shorter()1375 fn bitand_assign_shorter() {
1376 let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1377 let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1378 let a_and_b: Vec<usize> = vec![2, 7, 31, 32];
1379 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1380 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1381 a &= b;
1382 let res = a.ones().collect::<Vec<usize>>();
1383
1384 assert!(res == a_and_b);
1385 }
1386
1387 #[test]
bitand_assign_longer()1388 fn bitand_assign_longer() {
1389 let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1390 let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1391 let a_and_b: Vec<usize> = vec![2, 7, 31, 32];
1392 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1393 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1394 a &= b;
1395 let res = a.ones().collect::<Vec<usize>>();
1396 assert!(res == a_and_b);
1397 }
1398
1399 #[test]
bitor_assign_shorter()1400 fn bitor_assign_shorter() {
1401 let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1402 let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1403 let a_or_b: Vec<usize> = vec![2, 3, 7, 8, 11, 19, 23, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1404 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1405 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1406 a |= b;
1407 let res = a.ones().collect::<Vec<usize>>();
1408 assert!(res == a_or_b);
1409 }
1410
1411 #[test]
bitor_assign_longer()1412 fn bitor_assign_longer() {
1413 let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1414 let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1415 let a_or_b: Vec<usize> = vec![2, 3, 7, 8, 11, 19, 23, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1416 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1417 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1418 a |= b;
1419 let res = a.ones().collect::<Vec<usize>>();
1420 assert!(res == a_or_b);
1421 }
1422
1423 #[test]
bitxor_assign_shorter()1424 fn bitxor_assign_shorter() {
1425 let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1426 let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1427 let a_xor_b: Vec<usize> = vec![3, 8, 11, 19, 23, 37, 41, 43, 47, 71, 73, 101];
1428 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1429 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1430 a ^= b;
1431 let res = a.ones().collect::<Vec<usize>>();
1432 assert!(res == a_xor_b);
1433 }
1434
1435 #[test]
bitxor_assign_longer()1436 fn bitxor_assign_longer() {
1437 let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1438 let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1439 let a_xor_b: Vec<usize> = vec![3, 8, 11, 19, 23, 37, 41, 43, 47, 71, 73, 101];
1440 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1441 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1442 a ^= b;
1443 let res = a.ones().collect::<Vec<usize>>();
1444 assert!(res == a_xor_b);
1445 }
1446
1447 #[test]
op_assign_ref()1448 fn op_assign_ref() {
1449 let mut a = FixedBitSet::with_capacity(8);
1450 let b = FixedBitSet::with_capacity(8);
1451
1452 //check that all assign type operators work on references
1453 a &= &b;
1454 a |= &b;
1455 a ^= &b;
1456 }
1457
1458 #[test]
subset_superset_shorter()1459 fn subset_superset_shorter() {
1460 let a_ones: Vec<usize> = vec![7, 31, 32, 63];
1461 let b_ones: Vec<usize> = vec![2, 7, 19, 31, 32, 37, 41, 43, 47, 63, 73, 101];
1462 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1463 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1464 assert!(a.is_subset(&b) && b.is_superset(&a));
1465 a.insert(14);
1466 assert!(!a.is_subset(&b) && !b.is_superset(&a));
1467 }
1468
1469 #[test]
subset_superset_longer()1470 fn subset_superset_longer() {
1471 let a_len = 153;
1472 let b_len = 75;
1473 let a_ones: Vec<usize> = vec![7, 31, 32, 63];
1474 let b_ones: Vec<usize> = vec![2, 7, 19, 31, 32, 37, 41, 43, 47, 63, 73];
1475 let mut a = FixedBitSet::with_capacity(a_len);
1476 let mut b = FixedBitSet::with_capacity(b_len);
1477 a.extend(a_ones.iter().cloned());
1478 b.extend(b_ones.iter().cloned());
1479 assert!(a.is_subset(&b) && b.is_superset(&a));
1480 a.insert(100);
1481 assert!(!a.is_subset(&b) && !b.is_superset(&a));
1482 }
1483
1484 #[test]
is_disjoint_first_shorter()1485 fn is_disjoint_first_shorter() {
1486 let a_len = 75;
1487 let b_len = 153;
1488 let a_ones: Vec<usize> = vec![2, 19, 32, 37, 41, 43, 47, 73];
1489 let b_ones: Vec<usize> = vec![7, 23, 31, 63, 124];
1490 let mut a = FixedBitSet::with_capacity(a_len);
1491 let mut b = FixedBitSet::with_capacity(b_len);
1492 a.extend(a_ones.iter().cloned());
1493 b.extend(b_ones.iter().cloned());
1494 assert!(a.is_disjoint(&b));
1495 a.insert(63);
1496 assert!(!a.is_disjoint(&b));
1497 }
1498
1499 #[test]
is_disjoint_first_longer()1500 fn is_disjoint_first_longer() {
1501 let a_ones: Vec<usize> = vec![2, 19, 32, 37, 41, 43, 47, 73, 101];
1502 let b_ones: Vec<usize> = vec![7, 23, 31, 63];
1503 let a = a_ones.iter().cloned().collect::<FixedBitSet>();
1504 let mut b = b_ones.iter().cloned().collect::<FixedBitSet>();
1505 assert!(a.is_disjoint(&b));
1506 b.insert(2);
1507 assert!(!a.is_disjoint(&b));
1508 }
1509
1510 #[test]
extend_on_empty()1511 fn extend_on_empty() {
1512 let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167];
1513 let mut fbs = FixedBitSet::with_capacity(0);
1514 fbs.extend(items.iter().cloned());
1515 let ones = fbs.ones().collect::<Vec<usize>>();
1516 assert!(ones == items);
1517 }
1518
1519 #[test]
extend()1520 fn extend() {
1521 let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167];
1522 let mut fbs = FixedBitSet::with_capacity(168);
1523 let new: Vec<usize> = vec![7, 37, 67, 137];
1524 for i in &new {
1525 fbs.put(*i);
1526 }
1527
1528 fbs.extend(items.iter().cloned());
1529
1530 let ones = fbs.ones().collect::<Vec<usize>>();
1531 let expected = {
1532 let mut tmp = items.clone();
1533 tmp.extend(new);
1534 tmp.sort();
1535 tmp.dedup();
1536 tmp
1537 };
1538
1539 assert!(ones == expected);
1540 }
1541
1542 #[test]
from_iterator()1543 fn from_iterator() {
1544 let items: Vec<usize> = vec![0, 2, 4, 6, 8];
1545 let fb = items.iter().cloned().collect::<FixedBitSet>();
1546 for i in items {
1547 assert!(fb.contains(i));
1548 }
1549 for i in vec![1, 3, 5, 7] {
1550 assert!(!fb.contains(i));
1551 }
1552 assert_eq!(fb.len(), 9);
1553 }
1554
1555 #[test]
from_iterator_ones()1556 fn from_iterator_ones() {
1557 let len = 257;
1558 let mut fb = FixedBitSet::with_capacity(len);
1559 for i in (0..len).filter(|i| i % 7 == 0) {
1560 fb.put(i);
1561 }
1562 fb.put(len - 1);
1563 let dup = fb.ones().collect::<FixedBitSet>();
1564
1565
1566 assert_eq!(fb.len(), dup.len());
1567 assert_eq!(fb.ones().collect::<Vec<usize>>(), dup.ones().collect::<Vec<usize>>());
1568 }
1569
1570 #[cfg(feature = "std")]
1571 #[test]
binary_trait()1572 fn binary_trait() {
1573 let items: Vec<usize> = vec![1, 5, 7, 10, 14, 15];
1574 let fb = items.iter().cloned().collect::<FixedBitSet>();
1575
1576 assert_eq!(format!("{:b}", fb), "0100010100100011");
1577 assert_eq!(format!("{:#b}", fb), "0b0100010100100011");
1578 }
1579
1580 #[cfg(feature = "std")]
1581 #[test]
display_trait()1582 fn display_trait() {
1583 let len = 8;
1584 let mut fb = FixedBitSet::with_capacity(len);
1585
1586 fb.put(4);
1587 fb.put(2);
1588
1589 assert_eq!(format!("{}", fb), "00101000");
1590 assert_eq!(format!("{:#}", fb), "0b00101000");
1591 }
1592
1593 #[test]
1594 #[cfg(feature="serde")]
test_serialize()1595 fn test_serialize() {
1596 let mut fb = FixedBitSet::with_capacity(10);
1597 fb.put(2);
1598 fb.put(3);
1599 fb.put(6);
1600 fb.put(8);
1601 let serialized = serde_json::to_string(&fb).unwrap();
1602 assert_eq!(r#"{"data":[332],"length":10}"#, serialized);
1603 }
1604