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.31 or later.
13 //!
14 #![doc(html_root_url="https://docs.rs/fixedbitset/0.2/")]
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 use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Index};
32 use std::cmp::{Ord, Ordering};
33 use std::iter::{Chain, FromIterator};
34 pub use range::IndexRange;
35
36 const BITS: usize = 32;
37 type Block = u32;
38
39 #[inline]
div_rem(x: usize, d: usize) -> (usize, usize)40 fn div_rem(x: usize, d: usize) -> (usize, usize)
41 {
42 (x / d, x % d)
43 }
44
45 /// `FixedBitSet` is a simple fixed size set of bits that each can
46 /// be enabled (1 / **true**) or disabled (0 / **false**).
47 ///
48 /// The bit set has a fixed capacity in terms of enabling bits (and the
49 /// capacity can grow using the `grow` method).
50 #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
51 pub struct FixedBitSet {
52 data: Vec<Block>,
53 /// length in bits
54 length: usize,
55 }
56
57 impl FixedBitSet
58 {
59 /// Create a new **FixedBitSet** with a specific number of bits,
60 /// all initially clear.
with_capacity(bits: usize) -> Self61 pub fn with_capacity(bits: usize) -> Self
62 {
63 let (mut blocks, rem) = div_rem(bits, BITS);
64 blocks += (rem > 0) as usize;
65 FixedBitSet {
66 data: vec![0; blocks],
67 length: bits,
68 }
69 }
70 /// Grow capacity to **bits**, all new bits initialized to zero
grow(&mut self, bits: usize)71 pub fn grow(&mut self, bits: usize) {
72 let (mut blocks, rem) = div_rem(bits, BITS);
73 blocks += (rem > 0) as usize;
74 if bits > self.length {
75 self.length = bits;
76 self.data.resize(blocks, 0);
77 }
78 }
79
80 /// Return the length of the `FixedBitSet` in bits.
81 #[inline]
len(&self) -> usize82 pub fn len(&self) -> usize { self.length }
83
84 /// Return **true** if the bit is enabled in the **FixedBitSet**,
85 /// **false** otherwise.
86 ///
87 /// Note: bits outside the capacity are always disabled.
88 ///
89 /// Note: Also available with index syntax: `bitset[bit]`.
90 #[inline]
contains(&self, bit: usize) -> bool91 pub fn contains(&self, bit: usize) -> bool
92 {
93 let (block, i) = div_rem(bit, BITS);
94 match self.data.get(block) {
95 None => false,
96 Some(b) => (b & (1 << i)) != 0,
97 }
98 }
99
100 /// Clear all bits.
101 #[inline]
clear(&mut self)102 pub fn clear(&mut self)
103 {
104 for elt in &mut self.data[..] {
105 *elt = 0
106 }
107 }
108
109 /// Enable `bit`.
110 ///
111 /// **Panics** if **bit** is out of bounds.
112 #[inline]
insert(&mut self, bit: usize)113 pub fn insert(&mut self, bit: usize)
114 {
115 assert!(bit < self.length);
116 let (block, i) = div_rem(bit, BITS);
117 unsafe {
118 *self.data.get_unchecked_mut(block) |= 1 << i;
119 }
120 }
121
122 /// Enable `bit`, and return its previous value.
123 ///
124 /// **Panics** if **bit** is out of bounds.
125 #[inline]
put(&mut self, bit: usize) -> bool126 pub fn put(&mut self, bit: usize) -> bool
127 {
128 assert!(bit < self.length);
129 let (block, i) = div_rem(bit, BITS);
130 unsafe {
131 let word = self.data.get_unchecked_mut(block);
132 let prev = *word & (1 << i) != 0;
133 *word |= 1 << i;
134 prev
135 }
136 }
137 /// Toggle `bit` (inverting its state).
138 ///
139 /// ***Panics*** if **bit** is out of bounds
140 #[inline]
toggle(&mut self, bit: usize)141 pub fn toggle(&mut self, bit: usize) {
142 assert!(bit < self.length);
143 let (block, i) = div_rem(bit, BITS);
144 unsafe {
145 *self.data.get_unchecked_mut(block) ^= 1 << i;
146 }
147 }
148 /// **Panics** if **bit** is out of bounds.
149 #[inline]
set(&mut self, bit: usize, enabled: bool)150 pub fn set(&mut self, bit: usize, enabled: bool)
151 {
152 assert!(bit < self.length);
153 let (block, i) = div_rem(bit, BITS);
154 unsafe {
155 let elt = self.data.get_unchecked_mut(block);
156 if enabled {
157 *elt |= 1 << i;
158 } else {
159 *elt &= !(1 << i);
160 }
161 }
162 }
163
164 /// Copies boolean value from specified bit to the specified bit.
165 ///
166 /// **Panics** if **to** is out of bounds.
167 #[inline]
copy_bit(&mut self, from: usize, to: usize)168 pub fn copy_bit(&mut self, from: usize, to: usize)
169 {
170 assert!(to < self.length);
171 let (to_block, t) = div_rem(to, BITS);
172 let enabled = self.contains(from);
173 unsafe {
174 let to_elt = self.data.get_unchecked_mut(to_block);
175 if enabled {
176 *to_elt |= 1 << t;
177 } else {
178 *to_elt &= !(1 << t);
179 }
180 }
181 }
182
183 /// Count the number of set bits in the given bit range.
184 ///
185 /// Use `..` to count the whole content of the bitset.
186 ///
187 /// **Panics** if the range extends past the end of the bitset.
188 #[inline]
count_ones<T: IndexRange>(&self, range: T) -> usize189 pub fn count_ones<T: IndexRange>(&self, range: T) -> usize
190 {
191 Masks::new(range, self.length)
192 .map(|(block, mask)| unsafe {
193 let value = *self.data.get_unchecked(block);
194 (value & mask).count_ones() as usize
195 })
196 .sum()
197 }
198
199 /// Sets every bit in the given range to the given state (`enabled`)
200 ///
201 /// Use `..` to toggle the whole bitset.
202 ///
203 /// **Panics** if the range extends past the end of the bitset.
204 #[inline]
set_range<T: IndexRange>(&mut self, range: T, enabled: bool)205 pub fn set_range<T: IndexRange>(&mut self, range: T, enabled: bool)
206 {
207 for (block, mask) in Masks::new(range, self.length) {
208 unsafe {
209 if enabled {
210 *self.data.get_unchecked_mut(block) |= mask;
211 } else {
212 *self.data.get_unchecked_mut(block) &= !mask;
213 }
214 }
215 }
216 }
217
218 /// Enables every bit in the given range.
219 ///
220 /// Use `..` to make the whole bitset ones.
221 ///
222 /// **Panics** if the range extends past the end of the bitset.
223 #[inline]
insert_range<T: IndexRange>(&mut self, range: T)224 pub fn insert_range<T: IndexRange>(&mut self, range: T)
225 {
226 self.set_range(range, true);
227 }
228
229 /// View the bitset as a slice of `u32` blocks
230 #[inline]
as_slice(&self) -> &[u32]231 pub fn as_slice(&self) -> &[u32]
232 {
233 &self.data
234 }
235
236 /// View the bitset as a mutable slice of `u32` blocks. Writing past the bitlength in the last
237 /// will cause `contains` to return potentially incorrect results for bits past the bitlength.
238 #[inline]
as_mut_slice(&mut self) -> &mut [u32]239 pub fn as_mut_slice(&mut self) -> &mut [u32]
240 {
241 &mut self.data
242 }
243
244 /// Iterates over all enabled bits.
245 ///
246 /// Iterator element is the index of the `1` bit, type `usize`.
247 #[inline]
ones(&self) -> Ones248 pub fn ones(&self) -> Ones {
249 match self.as_slice().split_first() {
250 Some((&block, rem)) => {
251 Ones {
252 current_bit_idx: 0,
253 current_block_idx: 0,
254 current_block: block,
255 remaining_blocks: rem
256 }
257 }
258 None => {
259 Ones {
260 current_bit_idx: 0,
261 current_block_idx: 0,
262 current_block: 0,
263 remaining_blocks: &[]
264 }
265 }
266 }
267 }
268
269 /// Returns a lazy iterator over the intersection of two `FixedBitSet`s
intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a>270 pub fn intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a>
271 {
272 Intersection {
273 iter: self.ones(),
274 other: other,
275 }
276 }
277
278 /// Returns a lazy iterator over the union of two `FixedBitSet`s.
union<'a>(&'a self, other: &'a FixedBitSet) -> Union<'a>279 pub fn union<'a>(&'a self, other: &'a FixedBitSet) -> Union<'a>
280 {
281 Union {
282 iter: self.ones().chain(other.difference(self)),
283 }
284 }
285
286 /// Returns a lazy iterator over the difference of two `FixedBitSet`s. The difference of `a`
287 /// and `b` is the elements of `a` which are not in `b`.
difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a>288 pub fn difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a>
289 {
290 Difference {
291 iter: self.ones(),
292 other: other,
293 }
294 }
295
296 /// Returns a lazy iterator over the symmetric difference of two `FixedBitSet`s.
297 /// 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>298 pub fn symmetric_difference<'a>(&'a self, other: &'a FixedBitSet) -> SymmetricDifference<'a>
299 {
300 SymmetricDifference {
301 iter: self.difference(other).chain(other.difference(self)),
302 }
303 }
304
305 /// In-place union of two `FixedBitSet`s.
union_with(&mut self, other: &FixedBitSet)306 pub fn union_with(&mut self, other: &FixedBitSet)
307 {
308 if other.len() >= self.len() {
309 self.grow(other.len());
310 }
311 for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
312 *x |= *y;
313 }
314 }
315
316 /// In-place intersection of two `FixedBitSet`s.
intersect_with(&mut self, other: &FixedBitSet)317 pub fn intersect_with(&mut self, other: &FixedBitSet)
318 {
319 for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
320 *x &= *y;
321 }
322 let mn = std::cmp::min(self.data.len(), other.data.len());
323 for wd in &mut self.data[mn..] {
324 *wd = 0;
325 }
326 }
327
328 /// In-place symmetric difference of two `FixedBitSet`s.
symmetric_difference_with(&mut self, other: &FixedBitSet)329 pub fn symmetric_difference_with(&mut self, other: &FixedBitSet)
330 {
331 if other.len() >= self.len() {
332 self.grow(other.len());
333 }
334 for (x, y) in self.data.iter_mut().zip(other.data.iter()) {
335 *x ^= *y;
336 }
337 }
338
339 /// Returns `true` if `self` has no elements in common with `other`. This
340 /// is equivalent to checking for an empty intersection.
is_disjoint(&self, other: &FixedBitSet) -> bool341 pub fn is_disjoint(&self, other: &FixedBitSet) -> bool {
342 self.data.iter().zip(other.data.iter()).all(|(x, y)| x & y == 0)
343 }
344
345 /// Returns `true` if the set is a subset of another, i.e. `other` contains
346 /// at least all the values in `self`.
is_subset(&self, other: &FixedBitSet) -> bool347 pub fn is_subset(&self, other: &FixedBitSet) -> bool {
348 self.data.iter().zip(other.data.iter()).all(|(x, y)| x & !y == 0) &&
349 self.data.iter().skip(other.data.len()).all(|x| *x == 0)
350 }
351
352 /// Returns `true` if the set is a superset of another, i.e. `self` contains
353 /// at least all the values in `other`.
is_superset(&self, other: &FixedBitSet) -> bool354 pub fn is_superset(&self, other: &FixedBitSet) -> bool {
355 other.is_subset(self)
356 }
357 }
358
359 /// An iterator producing elements in the difference of two sets.
360 ///
361 /// This struct is created by the [`FixedBitSet::difference`] method.
362 pub struct Difference<'a> {
363 iter: Ones<'a>,
364 other: &'a FixedBitSet,
365 }
366
367 impl<'a> Iterator for Difference<'a> {
368 type Item = usize;
369
370 #[inline]
next(&mut self) -> Option<Self::Item>371 fn next(&mut self) -> Option<Self::Item> {
372 while let Some(nxt) = self.iter.next() {
373 if !self.other.contains(nxt) {
374 return Some(nxt);
375 }
376 }
377 None
378 }
379 }
380
381 /// An iterator producing elements in the symmetric difference of two sets.
382 ///
383 /// This struct is created by the [`FixedBitSet::symmetric_difference`] method.
384 pub struct SymmetricDifference<'a> {
385 iter: Chain<Difference<'a>, Difference<'a>>,
386 }
387
388 impl<'a> Iterator for SymmetricDifference<'a> {
389 type Item = usize;
390
391 #[inline]
next(&mut self) -> Option<Self::Item>392 fn next(&mut self) -> Option<Self::Item> {
393 self.iter.next()
394 }
395 }
396
397
398 /// An iterator producing elements in the intersection of two sets.
399 ///
400 /// This struct is created by the [`FixedBitSet::intersection`] method.
401 pub struct Intersection<'a> {
402 iter: Ones<'a>,
403 other: &'a FixedBitSet,
404 }
405
406 impl<'a> Iterator for Intersection<'a> {
407 type Item = usize; // the bit position of the '1'
408
409 #[inline]
next(&mut self) -> Option<Self::Item>410 fn next(&mut self) -> Option<Self::Item> {
411 while let Some(nxt) = self.iter.next() {
412 if self.other.contains(nxt) {
413 return Some(nxt);
414 }
415 }
416 None
417 }
418 }
419
420 /// An iterator producing elements in the union of two sets.
421 ///
422 /// This struct is created by the [`FixedBitSet::union`] method.
423 pub struct Union<'a> {
424 iter: Chain<Ones<'a>, Difference<'a>>,
425 }
426
427 impl<'a> Iterator for Union<'a> {
428 type Item = usize;
429
430 #[inline]
next(&mut self) -> Option<Self::Item>431 fn next(&mut self) -> Option<Self::Item> {
432 self.iter.next()
433 }
434 }
435
436
437 struct Masks {
438 first_block: usize,
439 first_mask: Block,
440 last_block: usize,
441 last_mask: Block,
442 }
443
444 impl Masks {
445 #[inline]
new<T: IndexRange>(range: T, length: usize) -> Masks446 fn new<T: IndexRange>(range: T, length: usize) -> Masks {
447 let start = range.start().unwrap_or(0);
448 let end = range.end().unwrap_or(length);
449 assert!(start <= end && end <= length);
450
451 let (first_block, first_rem) = div_rem(start, BITS);
452 let (last_block, last_rem) = div_rem(end, BITS);
453
454 Masks {
455 first_block: first_block as usize,
456 first_mask: Block::max_value() << first_rem,
457 last_block: last_block as usize,
458 last_mask: (Block::max_value() >> 1) >> (BITS - last_rem - 1),
459 // this is equivalent to `MAX >> (BITS - x)` with correct semantics when x == 0.
460 }
461 }
462 }
463
464 impl Iterator for Masks {
465 type Item = (usize, Block);
466 #[inline]
next(&mut self) -> Option<Self::Item>467 fn next(&mut self) -> Option<Self::Item> {
468 match self.first_block.cmp(&self.last_block) {
469 Ordering::Less => {
470 let res = (self.first_block, self.first_mask);
471 self.first_block += 1;
472 self.first_mask = !0;
473 Some(res)
474 }
475 Ordering::Equal => {
476 let mask = self.first_mask & self.last_mask;
477 let res = if mask == 0 {
478 None
479 } else {
480 Some((self.first_block, mask))
481 };
482 self.first_block += 1;
483 res
484 }
485 Ordering::Greater => None,
486 }
487 }
488 }
489
490
491 /// An iterator producing the indices of the set bit in a set.
492 ///
493 /// This struct is created by the [`FixedBitSet::ones`] method.
494 pub struct Ones<'a> {
495 current_bit_idx: usize,
496 current_block_idx: usize,
497 remaining_blocks: &'a [Block],
498 current_block: Block
499 }
500
501 impl<'a> Iterator for Ones<'a> {
502 type Item = usize; // the bit position of the '1'
503
504 #[inline]
next(&mut self) -> Option<Self::Item>505 fn next(&mut self) -> Option<Self::Item> {
506 let mut block = self.current_block;
507 let mut idx = self.current_bit_idx;
508
509 loop {
510 loop {
511 if (block & 1) == 1 {
512 self.current_block = block >> 1;
513 self.current_bit_idx = idx + 1;
514 return Some(idx);
515 }
516 // reordering the two lines below makes a huge (2x) difference in performance!
517 block = block >> 1;
518 idx += 1;
519 if block == 0 {
520 break;
521 }
522 }
523
524 // go to next block
525 match self.remaining_blocks.split_first() {
526 Some((&next_block, rest)) => {
527 self.remaining_blocks = rest;
528 self.current_block_idx += 1;
529 idx = self.current_block_idx * BITS;
530 block = next_block;
531 }
532 None => {
533 // last block => done
534 return None;
535 }
536 }
537 }
538 }
539 }
540
541 impl Clone for FixedBitSet
542 {
543 #[inline]
clone(&self) -> Self544 fn clone(&self) -> Self
545 {
546 FixedBitSet {
547 data: self.data.clone(),
548 length: self.length,
549 }
550 }
551 }
552
553 /// Return **true** if the bit is enabled in the bitset,
554 /// or **false** otherwise.
555 ///
556 /// Note: bits outside the capacity are always disabled, and thus
557 /// indexing a FixedBitSet will not panic.
558 impl Index<usize> for FixedBitSet
559 {
560 type Output = bool;
561
562 #[inline]
index(&self, bit: usize) -> &bool563 fn index(&self, bit: usize) -> &bool
564 {
565 if self.contains(bit) {
566 &true
567 } else {
568 &false
569 }
570 }
571 }
572
573 /// Sets the bit at index **i** to **true** for each item **i** in the input **src**.
574 impl Extend<usize> for FixedBitSet
575 {
extend<I: IntoIterator<Item=usize>>(&mut self, src: I)576 fn extend<I: IntoIterator<Item=usize>>(&mut self, src: I) {
577 let iter = src.into_iter();
578 for i in iter {
579 if i >= self.len() {
580 self.grow(i + 1);
581 }
582 self.put(i);
583 }
584 }
585 }
586
587 /// Return a FixedBitSet containing bits set to **true** for every bit index in
588 /// the iterator, other bits are set to **false**.
589 impl FromIterator<usize> for FixedBitSet
590 {
from_iter<I: IntoIterator<Item=usize>>(src: I) -> Self591 fn from_iter<I: IntoIterator<Item=usize>>(src: I) -> Self {
592 let mut fbs = FixedBitSet::with_capacity(0);
593 fbs.extend(src);
594 fbs
595 }
596 }
597
598 impl <'a> BitAnd for &'a FixedBitSet
599 {
600 type Output = FixedBitSet;
bitand(self, other: &FixedBitSet) -> FixedBitSet601 fn bitand(self, other: &FixedBitSet) -> FixedBitSet {
602 let (short, long) = {
603 if self.len() <= other.len() {
604 (&self.data, &other.data)
605 } else {
606 (&other.data, &self.data)
607 }
608 };
609 let mut data = short.clone();
610 for (data, block) in data.iter_mut().zip(long.iter()) {
611 *data &= *block;
612 }
613 let len = std::cmp::min(self.len(), other.len());
614 FixedBitSet{data: data, length: len}
615 }
616 }
617
618
619 impl <'a> BitAndAssign for FixedBitSet
620 {
bitand_assign(&mut self, other: Self)621 fn bitand_assign(&mut self, other: Self) {
622 self.intersect_with(&other);
623 }
624 }
625
626 impl <'a> BitOr for &'a FixedBitSet
627 {
628 type Output = FixedBitSet;
bitor(self, other: &FixedBitSet) -> FixedBitSet629 fn bitor(self, other: &FixedBitSet) -> FixedBitSet {
630 let (short, long) = {
631 if self.len() <= other.len() {
632 (&self.data, &other.data)
633 } else {
634 (&other.data, &self.data)
635 }
636 };
637 let mut data = long.clone();
638 for (data, block) in data.iter_mut().zip(short.iter()) {
639 *data |= *block;
640 }
641 let len = std::cmp::max(self.len(), other.len());
642 FixedBitSet{data: data, length: len}
643 }
644 }
645
646 impl <'a> BitOrAssign for FixedBitSet
647 {
bitor_assign(&mut self, other: Self)648 fn bitor_assign(&mut self, other: Self) {
649 self.union_with(&other);
650 }
651 }
652
653 impl <'a> BitXor for &'a FixedBitSet
654 {
655 type Output = FixedBitSet;
bitxor(self, other: &FixedBitSet) -> FixedBitSet656 fn bitxor(self, other: &FixedBitSet) -> FixedBitSet {
657 let (short, long) = {
658 if self.len() <= other.len() {
659 (&self.data, &other.data)
660 } else {
661 (&other.data, &self.data)
662 }
663 };
664 let mut data = long.clone();
665 for (data, block) in data.iter_mut().zip(short.iter()) {
666 *data ^= *block;
667 }
668 let len = std::cmp::max(self.len(), other.len());
669 FixedBitSet{data: data, length: len}
670 }
671 }
672
673 impl <'a> BitXorAssign for FixedBitSet
674 {
bitxor_assign(&mut self, other: Self)675 fn bitxor_assign(&mut self, other: Self) {
676 self.symmetric_difference_with(&other);
677 }
678 }
679
680 #[test]
it_works()681 fn it_works() {
682 const N: usize = 50;
683 let mut fb = FixedBitSet::with_capacity(N);
684
685
686 for i in 0..(N + 10) {
687 assert_eq!(fb.contains(i), false);
688 }
689
690 fb.insert(10);
691 fb.set(11, false);
692 fb.set(12, false);
693 fb.set(12, true);
694 fb.set(N-1, true);
695
696 assert!(fb.contains(10));
697 assert!(!fb.contains(11));
698 assert!(fb.contains(12));
699 assert!(fb.contains(N-1));
700 for i in 0..N {
701 let contain = i == 10 || i == 12 || i == N - 1;
702 assert_eq!(contain, fb[i]);
703 }
704
705 fb.clear();
706 }
707
708 #[test]
grow()709 fn grow() {
710 let mut fb = FixedBitSet::with_capacity(48);
711 for i in 0..fb.len() {
712 fb.set(i, true);
713 }
714
715 let old_len = fb.len();
716 fb.grow(72);
717 for j in 0..fb.len() {
718 assert_eq!(fb.contains(j), j < old_len);
719 }
720 fb.set(64, true);
721 assert!(fb.contains(64));
722 }
723
724 #[test]
test_toggle()725 fn test_toggle() {
726 let mut fb = FixedBitSet::with_capacity(16);
727 fb.toggle(1);
728 fb.put(2);
729 fb.toggle(2);
730 fb.put(3);
731 assert!(fb.contains(1));
732 assert!(!fb.contains(2));
733 assert!(fb.contains(3));
734 }
735
736 #[test]
copy_bit()737 fn copy_bit() {
738 let mut fb = FixedBitSet::with_capacity(48);
739 for i in 0..fb.len() {
740 fb.set(i, true);
741 }
742 fb.set(42, false);
743 fb.copy_bit(42, 2);
744 assert!(!fb.contains(42));
745 assert!(!fb.contains(2));
746 assert!(fb.contains(1));
747 fb.copy_bit(1, 42);
748 assert!(fb.contains(42));
749 fb.copy_bit(1024, 42);
750 assert!(!fb[42]);
751 }
752
753 #[test]
count_ones()754 fn count_ones() {
755 let mut fb = FixedBitSet::with_capacity(100);
756 fb.set(11, true);
757 fb.set(12, true);
758 fb.set(7, true);
759 fb.set(35, true);
760 fb.set(40, true);
761 fb.set(77, true);
762 fb.set(95, true);
763 fb.set(50, true);
764 fb.set(99, true);
765 assert_eq!(fb.count_ones(..7), 0);
766 assert_eq!(fb.count_ones(..8), 1);
767 assert_eq!(fb.count_ones(..11), 1);
768 assert_eq!(fb.count_ones(..12), 2);
769 assert_eq!(fb.count_ones(..13), 3);
770 assert_eq!(fb.count_ones(..35), 3);
771 assert_eq!(fb.count_ones(..36), 4);
772 assert_eq!(fb.count_ones(..40), 4);
773 assert_eq!(fb.count_ones(..41), 5);
774 assert_eq!(fb.count_ones(50..), 4);
775 assert_eq!(fb.count_ones(70..95), 1);
776 assert_eq!(fb.count_ones(70..96), 2);
777 assert_eq!(fb.count_ones(70..99), 2);
778 assert_eq!(fb.count_ones(..), 9);
779 assert_eq!(fb.count_ones(0..100), 9);
780 assert_eq!(fb.count_ones(0..0), 0);
781 assert_eq!(fb.count_ones(100..100), 0);
782 assert_eq!(fb.count_ones(7..), 9);
783 assert_eq!(fb.count_ones(8..), 8);
784 }
785
786 #[test]
ones()787 fn ones() {
788 let mut fb = FixedBitSet::with_capacity(100);
789 fb.set(11, true);
790 fb.set(12, true);
791 fb.set(7, true);
792 fb.set(35, true);
793 fb.set(40, true);
794 fb.set(77, true);
795 fb.set(95, true);
796 fb.set(50, true);
797 fb.set(99, true);
798
799 let ones: Vec<_> = fb.ones().collect();
800
801 assert_eq!(vec![7, 11, 12, 35, 40, 50, 77, 95, 99], ones);
802 }
803
804 #[test]
iter_ones_range()805 fn iter_ones_range() {
806 fn test_range(from: usize, to: usize, capa: usize) {
807 assert!(to <= capa);
808 let mut fb = FixedBitSet::with_capacity(capa);
809 for i in from..to {
810 fb.insert(i);
811 }
812 let ones: Vec<_> = fb.ones().collect();
813 let expected: Vec<_> = (from..to).collect();
814 assert_eq!(expected, ones);
815 }
816
817 for i in 0..100 {
818 test_range(i, 100, 100);
819 test_range(0, i, 100);
820 }
821 }
822
823 #[should_panic]
824 #[test]
count_ones_oob()825 fn count_ones_oob() {
826 let fb = FixedBitSet::with_capacity(100);
827 fb.count_ones(90..101);
828 }
829
830 #[should_panic]
831 #[test]
count_ones_negative_range()832 fn count_ones_negative_range() {
833 let fb = FixedBitSet::with_capacity(100);
834 fb.count_ones(90..80);
835 }
836
837 #[test]
count_ones_panic()838 fn count_ones_panic() {
839 for i in 1..128 {
840 let fb = FixedBitSet::with_capacity(i);
841 for j in 0..fb.len() + 1 {
842 for k in j..fb.len() + 1 {
843 assert_eq!(fb.count_ones(j..k), 0);
844 }
845 }
846 }
847 }
848
849
850 #[test]
default()851 fn default() {
852 let fb = FixedBitSet::default();
853 assert_eq!(fb.len(), 0);
854 }
855
856 #[test]
insert_range()857 fn insert_range() {
858 let mut fb = FixedBitSet::with_capacity(97);
859 fb.insert_range(..3);
860 fb.insert_range(9..32);
861 fb.insert_range(37..81);
862 fb.insert_range(90..);
863 for i in 0..97 {
864 assert_eq!(fb.contains(i), i<3 || 9<=i&&i<32 || 37<=i&&i<81 || 90<=i);
865 }
866 assert!(!fb.contains(97));
867 assert!(!fb.contains(127));
868 assert!(!fb.contains(128));
869 }
870
871 #[test]
set_range()872 fn set_range() {
873 let mut fb = FixedBitSet::with_capacity(48);
874 fb.insert_range(..);
875
876 fb.set_range(..32, false);
877 fb.set_range(37.., false);
878 fb.set_range(5..9, true);
879 fb.set_range(40..40, true);
880
881 for i in 0..48 {
882 assert_eq!(fb.contains(i), 5<=i&&i<9 || 32<=i&&i<37);
883 }
884 assert!(!fb.contains(48));
885 assert!(!fb.contains(64));
886 }
887
888 #[test]
bitand_equal_lengths()889 fn bitand_equal_lengths() {
890 let len = 109;
891 let a_end = 59;
892 let b_start = 23;
893 let mut a = FixedBitSet::with_capacity(len);
894 let mut b = FixedBitSet::with_capacity(len);
895 a.set_range(..a_end, true);
896 b.set_range(b_start.., true);
897 let ab = &a & &b;
898 for i in 0..b_start {
899 assert!(!ab.contains(i));
900 }
901 for i in b_start..a_end {
902 assert!(ab.contains(i));
903 }
904 for i in a_end..len {
905 assert!(!ab.contains(i));
906 }
907 assert_eq!(a.len(), ab.len());
908 }
909
910 #[test]
bitand_first_smaller()911 fn bitand_first_smaller() {
912 let a_len = 113;
913 let b_len = 137;
914 let len = std::cmp::min(a_len, b_len);
915 let a_end = 97;
916 let b_start = 89;
917 let mut a = FixedBitSet::with_capacity(a_len);
918 let mut b = FixedBitSet::with_capacity(b_len);
919 a.set_range(..a_end, true);
920 b.set_range(b_start.., true);
921 let ab = &a & &b;
922 for i in 0..b_start {
923 assert!(!ab.contains(i));
924 }
925 for i in b_start..a_end {
926 assert!(ab.contains(i));
927 }
928 for i in a_end..len {
929 assert!(!ab.contains(i));
930 }
931 assert_eq!(a.len(), ab.len());
932 }
933
934 #[test]
bitand_first_larger()935 fn bitand_first_larger() {
936 let a_len = 173;
937 let b_len = 137;
938 let len = std::cmp::min(a_len, b_len);
939 let a_end = 107;
940 let b_start = 43;
941 let mut a = FixedBitSet::with_capacity(a_len);
942 let mut b = FixedBitSet::with_capacity(b_len);
943 a.set_range(..a_end, true);
944 b.set_range(b_start.., true);
945 let ab = &a & &b;
946 for i in 0..b_start {
947 assert!(!ab.contains(i));
948 }
949 for i in b_start..a_end {
950 assert!(ab.contains(i));
951 }
952 for i in a_end..len {
953 assert!(!ab.contains(i));
954 }
955 assert_eq!(b.len(), ab.len());
956 }
957
958 #[test]
intersection()959 fn intersection() {
960 let len = 109;
961 let a_end = 59;
962 let b_start = 23;
963 let mut a = FixedBitSet::with_capacity(len);
964 let mut b = FixedBitSet::with_capacity(len);
965 a.set_range(..a_end, true);
966 b.set_range(b_start.., true);
967
968 let ab = a.intersection(&b).collect::<FixedBitSet>();
969
970 for i in 0..b_start {
971 assert!(!ab.contains(i));
972 }
973 for i in b_start..a_end {
974 assert!(ab.contains(i));
975 }
976 for i in a_end..len {
977 assert!(!ab.contains(i));
978 }
979 }
980
981 #[test]
union()982 fn union() {
983 let a_len = 173;
984 let b_len = 137;
985 let a_start = 139;
986 let b_end = 107;
987 let mut a = FixedBitSet::with_capacity(a_len);
988 let mut b = FixedBitSet::with_capacity(b_len);
989 a.set_range(a_start.., true);
990 b.set_range(..b_end, true);
991 let ab = a.union(&b).collect::<FixedBitSet>();
992 for i in a_start..a_len {
993 assert!(ab.contains(i));
994 }
995 for i in 0..b_end {
996 assert!(ab.contains(i));
997 }
998 for i in b_end..a_start {
999 assert!(!ab.contains(i));
1000 }
1001 }
1002
1003 #[test]
difference()1004 fn difference() {
1005 let a_len = 83;
1006 let b_len = 151;
1007 let a_start = 0;
1008 let a_end = 79;
1009 let b_start = 53;
1010 let mut a = FixedBitSet::with_capacity(a_len);
1011 let mut b = FixedBitSet::with_capacity(b_len);
1012 a.set_range(a_start..a_end, true);
1013 b.set_range(b_start..b_len, true);
1014 let a_diff_b = a.difference(&b).collect::<FixedBitSet>();
1015 for i in a_start..b_start {
1016 assert!(a_diff_b.contains(i));
1017 }
1018 for i in b_start..b_len {
1019 assert!(!a_diff_b.contains(i));
1020 }
1021 }
1022
1023 #[test]
symmetric_difference()1024 fn symmetric_difference() {
1025 let a_len = 83;
1026 let b_len = 151;
1027 let a_start = 47;
1028 let a_end = 79;
1029 let b_start = 53;
1030 let mut a = FixedBitSet::with_capacity(a_len);
1031 let mut b = FixedBitSet::with_capacity(b_len);
1032 a.set_range(a_start..a_end, true);
1033 b.set_range(b_start..b_len, true);
1034 let a_sym_diff_b = a.symmetric_difference(&b).collect::<FixedBitSet>();
1035 for i in 0..a_start {
1036 assert!(!a_sym_diff_b.contains(i));
1037 }
1038 for i in a_start..b_start {
1039 assert!(a_sym_diff_b.contains(i));
1040 }
1041 for i in b_start..a_end {
1042 assert!(!a_sym_diff_b.contains(i));
1043 }
1044 for i in a_end..b_len {
1045 assert!(a_sym_diff_b.contains(i));
1046 }
1047 }
1048
1049 #[test]
bitor_equal_lengths()1050 fn bitor_equal_lengths() {
1051 let len = 109;
1052 let a_start = 17;
1053 let a_end = 23;
1054 let b_start = 19;
1055 let b_end = 59;
1056 let mut a = FixedBitSet::with_capacity(len);
1057 let mut b = FixedBitSet::with_capacity(len);
1058 a.set_range(a_start..a_end, true);
1059 b.set_range(b_start..b_end, true);
1060 let ab = &a | &b;
1061 for i in 0..a_start {
1062 assert!(!ab.contains(i));
1063 }
1064 for i in a_start..b_end {
1065 assert!(ab.contains(i));
1066 }
1067 for i in b_end..len {
1068 assert!(!ab.contains(i));
1069 }
1070 assert_eq!(ab.len(), len);
1071 }
1072
1073 #[test]
bitor_first_smaller()1074 fn bitor_first_smaller() {
1075 let a_len = 113;
1076 let b_len = 137;
1077 let a_end = 89;
1078 let b_start = 97;
1079 let mut a = FixedBitSet::with_capacity(a_len);
1080 let mut b = FixedBitSet::with_capacity(b_len);
1081 a.set_range(..a_end, true);
1082 b.set_range(b_start.., true);
1083 let ab = &a | &b;
1084 for i in 0..a_end {
1085 assert!(ab.contains(i));
1086 }
1087 for i in a_end..b_start {
1088 assert!(!ab.contains(i));
1089 }
1090 for i in b_start..b_len {
1091 assert!(ab.contains(i));
1092 }
1093 assert_eq!(b_len, ab.len());
1094 }
1095
1096 #[test]
bitor_first_larger()1097 fn bitor_first_larger() {
1098 let a_len = 173;
1099 let b_len = 137;
1100 let a_start = 139;
1101 let b_end = 107;
1102 let mut a = FixedBitSet::with_capacity(a_len);
1103 let mut b = FixedBitSet::with_capacity(b_len);
1104 a.set_range(a_start.., true);
1105 b.set_range(..b_end, true);
1106 let ab = &a | &b;
1107 for i in a_start..a_len {
1108 assert!(ab.contains(i));
1109 }
1110 for i in 0..b_end {
1111 assert!(ab.contains(i));
1112 }
1113 for i in b_end..a_start {
1114 assert!(!ab.contains(i));
1115 }
1116 assert_eq!(a_len, ab.len());
1117 }
1118
1119 #[test]
bitxor_equal_lengths()1120 fn bitxor_equal_lengths() {
1121 let len = 109;
1122 let a_end = 59;
1123 let b_start = 23;
1124 let mut a = FixedBitSet::with_capacity(len);
1125 let mut b = FixedBitSet::with_capacity(len);
1126 a.set_range(..a_end, true);
1127 b.set_range(b_start.., true);
1128 let ab = &a ^ &b;
1129 for i in 0..b_start {
1130 assert!(ab.contains(i));
1131 }
1132 for i in b_start..a_end {
1133 assert!(!ab.contains(i));
1134 }
1135 for i in a_end..len {
1136 assert!(ab.contains(i));
1137 }
1138 assert_eq!(a.len(), ab.len());
1139 }
1140
1141 #[test]
bitxor_first_smaller()1142 fn bitxor_first_smaller() {
1143 let a_len = 113;
1144 let b_len = 137;
1145 let len = std::cmp::max(a_len, b_len);
1146 let a_end = 97;
1147 let b_start = 89;
1148 let mut a = FixedBitSet::with_capacity(a_len);
1149 let mut b = FixedBitSet::with_capacity(b_len);
1150 a.set_range(..a_end, true);
1151 b.set_range(b_start.., true);
1152 let ab = &a ^ &b;
1153 for i in 0..b_start {
1154 assert!(ab.contains(i));
1155 }
1156 for i in b_start..a_end {
1157 assert!(!ab.contains(i));
1158 }
1159 for i in a_end..len {
1160 assert!(ab.contains(i));
1161 }
1162 assert_eq!(b.len(), ab.len());
1163 }
1164
1165 #[test]
bitxor_first_larger()1166 fn bitxor_first_larger() {
1167 let a_len = 173;
1168 let b_len = 137;
1169 let len = std::cmp::max(a_len, b_len);
1170 let a_end = 107;
1171 let b_start = 43;
1172 let mut a = FixedBitSet::with_capacity(a_len);
1173 let mut b = FixedBitSet::with_capacity(b_len);
1174 a.set_range(..a_end, true);
1175 b.set_range(b_start.., true);
1176 let ab = &a ^ &b;
1177 for i in 0..b_start {
1178 assert!(ab.contains(i));
1179 }
1180 for i in b_start..a_end {
1181 assert!(!ab.contains(i));
1182 }
1183 for i in a_end..b_len {
1184 assert!(ab.contains(i));
1185 }
1186 for i in b_len..len {
1187 assert!(!ab.contains(i));
1188 }
1189 assert_eq!(a.len(), ab.len());
1190 }
1191
1192 #[test]
bitand_assign_shorter()1193 fn bitand_assign_shorter() {
1194 let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1195 let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1196 let a_and_b: Vec<usize> = vec![2, 7, 31, 32];
1197 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1198 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1199 a &= b;
1200 let res = a.ones().collect::<Vec<usize>>();
1201
1202 assert!(res == a_and_b);
1203 }
1204
1205 #[test]
bitand_assign_longer()1206 fn bitand_assign_longer() {
1207 let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1208 let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1209 let a_and_b: Vec<usize> = vec![2, 7, 31, 32];
1210 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1211 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1212 a &= b;
1213 let res = a.ones().collect::<Vec<usize>>();
1214 assert!(res == a_and_b);
1215 }
1216
1217 #[test]
bitor_assign_shorter()1218 fn bitor_assign_shorter() {
1219 let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1220 let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1221 let a_or_b: Vec<usize> = vec![2, 3, 7, 8, 11, 19, 23, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1222 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1223 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1224 a |= b;
1225 let res = a.ones().collect::<Vec<usize>>();
1226 assert!(res == a_or_b);
1227 }
1228
1229 #[test]
bitor_assign_longer()1230 fn bitor_assign_longer() {
1231 let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1232 let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1233 let a_or_b: Vec<usize> = vec![2, 3, 7, 8, 11, 19, 23, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1234 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1235 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1236 a |= b;
1237 let res = a.ones().collect::<Vec<usize>>();
1238 assert!(res == a_or_b);
1239 }
1240
1241 #[test]
bitxor_assign_shorter()1242 fn bitxor_assign_shorter() {
1243 let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1244 let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1245 let a_xor_b: Vec<usize> = vec![3, 8, 11, 19, 23, 37, 41, 43, 47, 71, 73, 101];
1246 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1247 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1248 a ^= b;
1249 let res = a.ones().collect::<Vec<usize>>();
1250 assert!(res == a_xor_b);
1251 }
1252
1253 #[test]
bitxor_assign_longer()1254 fn bitxor_assign_longer() {
1255 let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32];
1256 let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101];
1257 let a_xor_b: Vec<usize> = vec![3, 8, 11, 19, 23, 37, 41, 43, 47, 71, 73, 101];
1258 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1259 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1260 a ^= b;
1261 let res = a.ones().collect::<Vec<usize>>();
1262 assert!(res == a_xor_b);
1263 }
1264
1265 #[test]
subset_superset_shorter()1266 fn subset_superset_shorter() {
1267 let a_ones: Vec<usize> = vec![7, 31, 32, 63];
1268 let b_ones: Vec<usize> = vec![2, 7, 19, 31, 32, 37, 41, 43, 47, 63, 73, 101];
1269 let mut a = a_ones.iter().cloned().collect::<FixedBitSet>();
1270 let b = b_ones.iter().cloned().collect::<FixedBitSet>();
1271 assert!(a.is_subset(&b) && b.is_superset(&a));
1272 a.insert(14);
1273 assert!(!a.is_subset(&b) && !b.is_superset(&a));
1274 }
1275
1276 #[test]
subset_superset_longer()1277 fn subset_superset_longer() {
1278 let a_len = 153;
1279 let b_len = 75;
1280 let a_ones: Vec<usize> = vec![7, 31, 32, 63];
1281 let b_ones: Vec<usize> = vec![2, 7, 19, 31, 32, 37, 41, 43, 47, 63, 73];
1282 let mut a = FixedBitSet::with_capacity(a_len);
1283 let mut b = FixedBitSet::with_capacity(b_len);
1284 a.extend(a_ones.iter().cloned());
1285 b.extend(b_ones.iter().cloned());
1286 assert!(a.is_subset(&b) && b.is_superset(&a));
1287 a.insert(100);
1288 assert!(!a.is_subset(&b) && !b.is_superset(&a));
1289 }
1290
1291 #[test]
is_disjoint_first_shorter()1292 fn is_disjoint_first_shorter() {
1293 let a_len = 75;
1294 let b_len = 153;
1295 let a_ones: Vec<usize> = vec![2, 19, 32, 37, 41, 43, 47, 73];
1296 let b_ones: Vec<usize> = vec![7, 23, 31, 63, 124];
1297 let mut a = FixedBitSet::with_capacity(a_len);
1298 let mut b = FixedBitSet::with_capacity(b_len);
1299 a.extend(a_ones.iter().cloned());
1300 b.extend(b_ones.iter().cloned());
1301 assert!(a.is_disjoint(&b));
1302 a.insert(63);
1303 assert!(!a.is_disjoint(&b));
1304 }
1305
1306 #[test]
is_disjoint_first_longer()1307 fn is_disjoint_first_longer() {
1308 let a_ones: Vec<usize> = vec![2, 19, 32, 37, 41, 43, 47, 73, 101];
1309 let b_ones: Vec<usize> = vec![7, 23, 31, 63];
1310 let a = a_ones.iter().cloned().collect::<FixedBitSet>();
1311 let mut b = b_ones.iter().cloned().collect::<FixedBitSet>();
1312 assert!(a.is_disjoint(&b));
1313 b.insert(2);
1314 assert!(!a.is_disjoint(&b));
1315 }
1316
1317 #[test]
extend_on_empty()1318 fn extend_on_empty() {
1319 let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167];
1320 let mut fbs = FixedBitSet::with_capacity(0);
1321 fbs.extend(items.iter().cloned());
1322 let ones = fbs.ones().collect::<Vec<usize>>();
1323 assert!(ones == items);
1324 }
1325
1326 #[test]
extend()1327 fn extend() {
1328 let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167];
1329 let mut fbs = FixedBitSet::with_capacity(168);
1330 let new: Vec<usize> = vec![7, 37, 67, 137];
1331 for i in &new {
1332 fbs.put(*i);
1333 }
1334
1335 fbs.extend(items.iter().cloned());
1336
1337 let ones = fbs.ones().collect::<Vec<usize>>();
1338 let expected = {
1339 let mut tmp = items.clone();
1340 tmp.extend(new);
1341 tmp.sort();
1342 tmp.dedup();
1343 tmp
1344 };
1345
1346 assert!(ones == expected);
1347 }
1348
1349 #[test]
from_iterator()1350 fn from_iterator() {
1351 let items: Vec<usize> = vec![0, 2, 4, 6, 8];
1352 let fb = items.iter().cloned().collect::<FixedBitSet>();
1353 for i in items {
1354 assert!(fb.contains(i));
1355 }
1356 for i in vec![1, 3, 5, 7] {
1357 assert!(!fb.contains(i));
1358 }
1359 assert_eq!(fb.len(), 9);
1360 }
1361
1362 #[test]
from_iterator_ones()1363 fn from_iterator_ones() {
1364 let len = 257;
1365 let mut fb = FixedBitSet::with_capacity(len);
1366 for i in (0..len).filter(|i| i % 7 == 0) {
1367 fb.put(i);
1368 }
1369 fb.put(len - 1);
1370 let dup = fb.ones().collect::<FixedBitSet>();
1371
1372
1373 assert_eq!(fb.len(), dup.len());
1374 assert_eq!(fb.ones().collect::<Vec<usize>>(), dup.ones().collect::<Vec<usize>>());
1375 }
1376