fixedbitset/
lib.rs

1//! `FixedBitSet` is a simple fixed size set of bits.
2#![doc(html_root_url="https://docs.rs/fixedbitset/0.1/")]
3
4mod range;
5
6use std::ops::{BitAnd, BitOr, Index};
7use std::cmp::{Ord, Ordering};
8use std::iter::{Chain, FromIterator};
9pub use range::IndexRange;
10
11static TRUE: bool = true;
12static FALSE: bool = false;
13
14const BITS: usize = 32;
15type Block = u32;
16
17#[inline]
18fn div_rem(x: usize, d: usize) -> (usize, usize)
19{
20    (x / d, x % d)
21}
22
23/// `FixedBitSet` is a simple fixed size set of bits that each can
24/// be enabled (1 / **true**) or disabled (0 / **false**).
25///
26/// The bit set has a fixed capacity in terms of enabling bits (and the
27/// capacity can grow using the `grow` method).
28#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
29pub struct FixedBitSet {
30    data: Vec<Block>,
31    /// length in bits
32    length: usize,
33}
34
35impl FixedBitSet
36{
37    /// Create a new **FixedBitSet** with a specific number of bits,
38    /// all initially clear.
39    pub fn with_capacity(bits: usize) -> Self
40    {
41        let (mut blocks, rem) = div_rem(bits, BITS);
42        blocks += (rem > 0) as usize;
43        FixedBitSet {
44            data: vec![0; blocks],
45            length: bits,
46        }
47    }
48    
49    /// Grow capacity to **bits**, all new bits initialized to zero
50    pub fn grow(&mut self, bits: usize) {
51        let (mut blocks, rem) = div_rem(bits, BITS);
52        blocks += (rem > 0) as usize;
53        if bits > self.length {
54            self.length = bits;
55            self.data.resize(blocks, 0);
56        }
57    }
58
59    /// Return the length of the `FixedBitSet` in bits.
60    #[inline]
61    pub fn len(&self) -> usize { self.length }
62
63    /// Return **true** if the bit is enabled in the **FixedBitSet**,
64    /// **false** otherwise.
65    ///
66    /// Note: bits outside the capacity are always disabled.
67    ///
68    /// Note: Also available with index syntax: `bitset[bit]`.
69    #[inline]
70    pub fn contains(&self, bit: usize) -> bool
71    {
72        let (block, i) = div_rem(bit, BITS);
73        match self.data.get(block) {
74            None => false,
75            Some(b) => (b & (1 << i)) != 0,
76        }
77    }
78
79    /// Clear all bits.
80    #[inline]
81    pub fn clear(&mut self)
82    {
83        for elt in &mut self.data[..] {
84            *elt = 0
85        }
86    }
87
88    /// Enable `bit`.
89    ///
90    /// **Panics** if **bit** is out of bounds.
91    #[inline]
92    pub fn insert(&mut self, bit: usize)
93    {
94        assert!(bit < self.length);
95        let (block, i) = div_rem(bit, BITS);
96        unsafe {
97            *self.data.get_unchecked_mut(block) |= 1 << i;
98        }
99    }
100
101    /// Enable `bit`, and return its previous value.
102    ///
103    /// **Panics** if **bit** is out of bounds.
104    #[inline]
105    pub fn put(&mut self, bit: usize) -> bool
106    {
107        assert!(bit < self.length);
108        let (block, i) = div_rem(bit, BITS);
109        unsafe {
110            let word = self.data.get_unchecked_mut(block);
111            let prev = *word & (1 << i) != 0;
112            *word |= 1 << i;
113            prev
114        }
115    }
116
117    /// **Panics** if **bit** is out of bounds.
118    #[inline]
119    pub fn set(&mut self, bit: usize, enabled: bool)
120    {
121        assert!(bit < self.length);
122        let (block, i) = div_rem(bit, BITS);
123        unsafe {
124            let elt = self.data.get_unchecked_mut(block);
125            if enabled {
126                *elt |= 1 << i;
127            } else {
128                *elt &= !(1 << i);
129            }
130        }
131    }
132
133    /// Copies boolean value from specified bit to the specified bit.
134    ///
135    /// **Panics** if **to** is out of bounds.
136    #[inline]
137    pub fn copy_bit(&mut self, from: usize, to: usize)
138    {
139        assert!(to < self.length);
140        let (to_block, t) = div_rem(to, BITS);
141        let enabled = self.contains(from);
142        unsafe {
143            let to_elt = self.data.get_unchecked_mut(to_block);
144            if enabled {
145                *to_elt |= 1 << t;
146            } else {
147                *to_elt &= !(1 << t);
148            }
149        }
150    }
151
152    /// Count the number of set bits in the given bit range.
153    ///
154    /// Use `..` to count the whole content of the bitset.
155    ///
156    /// **Panics** if the range extends past the end of the bitset.
157    #[inline]
158    pub fn count_ones<T: IndexRange>(&self, range: T) -> usize
159    {
160        Masks::new(range, self.length)
161            .map(|(block, mask)| unsafe {
162                let value = *self.data.get_unchecked(block);
163                (value & mask).count_ones() as usize
164            })
165            .sum()
166    }
167
168    /// Sets every bit in the given range to the given state (`enabled`)
169    ///
170    /// Use `..` to toggle the whole bitset.
171    ///
172    /// **Panics** if the range extends past the end of the bitset.
173    #[inline]
174    pub fn set_range<T: IndexRange>(&mut self, range: T, enabled: bool)
175    {
176        for (block, mask) in Masks::new(range, self.length) {
177            unsafe {
178                if enabled {
179                    *self.data.get_unchecked_mut(block) |= mask;
180                } else {
181                    *self.data.get_unchecked_mut(block) &= !mask;
182                }
183            }
184        }
185    }
186
187    /// Enables every bit in the given range.
188    ///
189    /// Use `..` to make the whole bitset ones.
190    ///
191    /// **Panics** if the range extends past the end of the bitset.
192    #[inline]
193    pub fn insert_range<T: IndexRange>(&mut self, range: T)
194    {
195        self.set_range(range, true);
196    }
197
198    /// View the bitset as a slice of `u32` blocks
199    #[inline]
200    pub fn as_slice(&self) -> &[u32]
201    {
202        &self.data
203    }
204
205    /// View the bitset as a mutable slice of `u32` blocks. Writing past the bitlength in the last
206    /// will cause `contains` to return potentially incorrect results for bits past the bitlength.
207    #[inline]
208    pub fn as_mut_slice(&mut self) -> &mut [u32]
209    {
210        &mut self.data
211    }
212
213    /// Iterates over all enabled bits.
214    ///
215    /// Iterator element is the index of the `1` bit, type `usize`.
216    #[inline]
217    pub fn ones(&self) -> Ones {
218        match self.as_slice().split_first() {
219            Some((&block, rem)) => {
220                Ones {
221                    current_bit_idx: 0,
222                    current_block_idx: 0,
223                    current_block: block,
224                    remaining_blocks: rem
225                }
226            }
227            None => {
228                Ones {
229                    current_bit_idx: 0,
230                    current_block_idx: 0,
231                    current_block: 0,
232                    remaining_blocks: &[]
233                }
234            }
235        }
236    }
237
238    /// Returns a lazy iterator over the intersection of two `FixedBitSet`s
239    pub fn intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a>
240    {
241        Intersection {
242            iter: self.ones(),
243            other: other,
244        }
245    }
246
247    /// Returns a lazy iterator over the union of two `FixedBitSet`s.
248    pub fn union<'a>(&'a self, other: &'a FixedBitSet) -> Union<'a>
249    {
250        Union {
251            iter: self.ones().chain(other.difference(self)),
252        }
253    }
254
255    /// Returns a lazy iterator over the difference of two `FixedBitSet`s. The difference of `a`
256    /// and `b` is the elements of `a` which are not in `b`.
257    pub fn difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a>
258    {
259        Difference {
260            iter: self.ones(),
261            other: other,
262        }
263    }
264}
265
266/// An iterator producing elements in the difference of two sets.
267///
268/// This struct is created by the [`FixedBitSet::difference`] method.
269pub struct Difference<'a> {
270    iter: Ones<'a>,
271    other: &'a FixedBitSet,
272}
273
274impl<'a> Iterator for Difference<'a> {
275    type Item = usize;
276
277    #[inline]
278    fn next(&mut self) -> Option<Self::Item> {
279        while let Some(nxt) = self.iter.next() {
280            if !self.other.contains(nxt) {
281                return Some(nxt);
282            }
283        }
284        None
285    }
286}
287
288
289/// An iterator producing elements in the intersection of two sets.
290///
291/// This struct is created by the [`FixedBitSet::intersection`] method.
292pub struct Intersection<'a> {
293    iter: Ones<'a>,
294    other: &'a FixedBitSet,
295}
296
297impl<'a> Iterator for Intersection<'a> {
298    type Item = usize; // the bit position of the '1'
299
300    #[inline]
301    fn next(&mut self) -> Option<Self::Item> {
302        while let Some(nxt) = self.iter.next() {
303            if self.other.contains(nxt) {
304                return Some(nxt);
305            }
306        }
307        None
308    }
309}
310
311/// An iterator producing elements in the union of two sets.
312///
313/// This struct is created by the [`FixedBitSet::union`] method.
314pub struct Union<'a> {
315    iter: Chain<Ones<'a>, Difference<'a>>,
316}
317
318impl<'a> Iterator for Union<'a> {
319    type Item = usize;
320
321    #[inline]
322    fn next(&mut self) -> Option<Self::Item> {
323        self.iter.next()
324    }
325}
326
327
328struct Masks {
329    first_block: usize,
330    first_mask: Block,
331    last_block: usize,
332    last_mask: Block,
333}
334
335impl Masks {
336    #[inline]
337    fn new<T: IndexRange>(range: T, length: usize) -> Masks {
338        let start = range.start().unwrap_or(0);
339        let end = range.end().unwrap_or(length);
340        assert!(start <= end && end <= length);
341
342        let (first_block, first_rem) = div_rem(start, BITS);
343        let (last_block, last_rem) = div_rem(end, BITS);
344
345        Masks {
346            first_block: first_block as usize,
347            first_mask: Block::max_value() << first_rem,
348            last_block: last_block as usize,
349            last_mask: (Block::max_value() >> 1) >> (BITS - last_rem - 1),
350            // this is equivalent to `MAX >> (BITS - x)` with correct semantics when x == 0.
351        }
352    }
353}
354
355impl Iterator for Masks {
356    type Item = (usize, Block);
357    #[inline]
358    fn next(&mut self) -> Option<Self::Item> {
359        match self.first_block.cmp(&self.last_block) {
360            Ordering::Less => {
361                let res = (self.first_block, self.first_mask);
362                self.first_block += 1;
363                self.first_mask = !0;
364                Some(res)
365            }
366            Ordering::Equal => {
367                let mask = self.first_mask & self.last_mask;
368                let res = if mask == 0 {
369                    None
370                } else {
371                    Some((self.first_block, mask))
372                };
373                self.first_block += 1;
374                res
375            }
376            Ordering::Greater => None,
377        }
378    }
379}
380
381
382/// An  iterator producing the indices of the set bit in a set.
383///
384/// This struct is created by the [`FixedBitSet::ones`] method.
385pub struct Ones<'a> {
386    current_bit_idx: usize,
387    current_block_idx: usize,
388    remaining_blocks: &'a [Block],
389    current_block: Block
390}
391
392impl<'a> Iterator for Ones<'a> {
393    type Item = usize; // the bit position of the '1'
394
395    #[inline]
396    fn next(&mut self) -> Option<Self::Item> {
397        let mut block = self.current_block;
398        let mut idx = self.current_bit_idx;
399
400        loop {
401            loop {
402                if (block & 1) == 1 {
403                    self.current_block = block >> 1;
404                    self.current_bit_idx = idx + 1;
405                    return Some(idx);
406                }
407                // reordering the two lines below makes a huge (2x) difference in performance!
408                block = block >> 1;
409                idx += 1;
410                if block == 0 {
411                    break;
412                }
413            }
414
415            // go to next block
416            match self.remaining_blocks.split_first() {
417                Some((&next_block, rest)) => {
418                    self.remaining_blocks = rest;
419                    self.current_block_idx += 1;
420                    idx = self.current_block_idx * BITS;
421                    block = next_block;
422                }
423                None => {
424                    // last block => done
425                    return None;
426                }
427            }
428        }
429    }
430}
431
432impl Clone for FixedBitSet
433{
434    #[inline]
435    fn clone(&self) -> Self
436    {
437        FixedBitSet {
438            data: self.data.clone(),
439            length: self.length,
440        }
441    }
442}
443
444/// Return **true** if the bit is enabled in the bitset,
445/// or **false** otherwise.
446///
447/// Note: bits outside the capacity are always disabled, and thus
448/// indexing a FixedBitSet will not panic.
449impl Index<usize> for FixedBitSet
450{
451    type Output = bool;
452
453    #[inline]
454    fn index(&self, bit: usize) -> &bool
455    {
456        if self.contains(bit) {
457            &TRUE
458        } else {
459            &FALSE
460        }
461    }
462}
463
464/// Sets the bit at index **i** to **true** for each item **i** in the input **src**.
465impl Extend<usize> for FixedBitSet
466{
467    fn extend<I: IntoIterator<Item=usize>>(&mut self, src: I) {
468        let iter = src.into_iter();
469        for i in iter {
470            if i >= self.len() {
471                self.grow(i + 1);
472            }
473            self.put(i);
474        }
475    }
476}
477
478/// Return a FixedBitSet containing bits set to **true** for every bit index in
479/// the iterator, other bits are set to **false**.
480impl FromIterator<usize> for FixedBitSet
481{
482    fn from_iter<I: IntoIterator<Item=usize>>(src: I) -> Self {
483        let mut fbs = FixedBitSet::with_capacity(0);
484        fbs.extend(src);
485        fbs
486    }
487}
488
489impl <'a> BitAnd for &'a FixedBitSet
490{
491    type Output = FixedBitSet;
492    fn bitand(self, other: &FixedBitSet) -> FixedBitSet {
493        let (short, long) = {
494            if self.len() <= other.len() {
495                (&self.data, &other.data)
496            } else {
497                (&other.data, &self.data)
498            }
499        };
500        let mut data = short.clone();
501        for (i, &block) in long.iter().take(short.len()).enumerate() {
502            data[i] &= block;
503        }
504        let len = std::cmp::min(self.len(), other.len());
505        FixedBitSet{data: data, length: len}
506    }
507}
508
509impl <'a> BitOr for &'a FixedBitSet
510{
511    type Output = FixedBitSet;
512    fn bitor(self, other: &FixedBitSet) -> FixedBitSet {
513        let (short, long) = {
514            if self.len() <= other.len() {
515                (&self.data, &other.data)
516            } else {
517                (&other.data, &self.data)
518            }
519        };
520        let mut data = long.clone();
521        for (i, &block) in short.iter().enumerate() {
522            data[i] |= block;
523        }
524        let len = std::cmp::max(self.len(), other.len());
525        FixedBitSet{data: data, length: len}
526    }
527}
528
529#[test]
530fn it_works() {
531    const N: usize = 50;
532    let mut fb = FixedBitSet::with_capacity(N);
533    println!("{:?}", fb);
534
535    for i in 0..(N + 10) {
536        assert_eq!(fb.contains(i), false);
537    }
538
539    fb.insert(10);
540    fb.set(11, false);
541    fb.set(12, false);
542    fb.set(12, true);
543    fb.set(N-1, true);
544    println!("{:?}", fb);
545    assert!(fb.contains(10));
546    assert!(!fb.contains(11));
547    assert!(fb.contains(12));
548    assert!(fb.contains(N-1));
549    for i in 0..N {
550        let contain = i == 10 || i == 12 || i == N - 1;
551        assert_eq!(contain, fb[i]);
552    }
553
554    fb.clear();
555}
556
557#[test]
558fn grow() {
559    let mut fb = FixedBitSet::with_capacity(48);
560    for i in 0..fb.len() {
561        fb.set(i, true);
562    }
563
564    let old_len = fb.len();
565    fb.grow(72);
566    for j in 0..fb.len() {
567        assert_eq!(fb.contains(j), j < old_len);
568    }
569    fb.set(64, true);
570    assert!(fb.contains(64));
571}
572
573#[test]
574fn copy_bit() {
575    let mut fb = FixedBitSet::with_capacity(48);
576    for i in 0..fb.len() {
577        fb.set(i, true);
578    }
579    fb.set(42, false);
580    fb.copy_bit(42, 2);
581    assert!(!fb.contains(42));
582    assert!(!fb.contains(2));
583    assert!(fb.contains(1));
584    fb.copy_bit(1, 42);
585    assert!(fb.contains(42));
586    fb.copy_bit(1024, 42);
587    assert!(!fb[42]);
588}
589
590#[test]
591fn count_ones() {
592    let mut fb = FixedBitSet::with_capacity(100);
593    fb.set(11, true);
594    fb.set(12, true);
595    fb.set(7, true);
596    fb.set(35, true);
597    fb.set(40, true);
598    fb.set(77, true);
599    fb.set(95, true);
600    fb.set(50, true);
601    fb.set(99, true);
602    assert_eq!(fb.count_ones(..7), 0);
603    assert_eq!(fb.count_ones(..8), 1);
604    assert_eq!(fb.count_ones(..11), 1);
605    assert_eq!(fb.count_ones(..12), 2);
606    assert_eq!(fb.count_ones(..13), 3);
607    assert_eq!(fb.count_ones(..35), 3);
608    assert_eq!(fb.count_ones(..36), 4);
609    assert_eq!(fb.count_ones(..40), 4);
610    assert_eq!(fb.count_ones(..41), 5);
611    assert_eq!(fb.count_ones(50..), 4);
612    assert_eq!(fb.count_ones(70..95), 1);
613    assert_eq!(fb.count_ones(70..96), 2);
614    assert_eq!(fb.count_ones(70..99), 2);
615    assert_eq!(fb.count_ones(..), 9);
616    assert_eq!(fb.count_ones(0..100), 9);
617    assert_eq!(fb.count_ones(0..0), 0);
618    assert_eq!(fb.count_ones(100..100), 0);
619    assert_eq!(fb.count_ones(7..), 9);
620    assert_eq!(fb.count_ones(8..), 8);
621}
622
623#[test]
624fn ones() {
625    let mut fb = FixedBitSet::with_capacity(100);
626    fb.set(11, true);
627    fb.set(12, true);
628    fb.set(7, true);
629    fb.set(35, true);
630    fb.set(40, true);
631    fb.set(77, true);
632    fb.set(95, true);
633    fb.set(50, true);
634    fb.set(99, true);
635
636    let ones: Vec<_> = fb.ones().collect();
637
638    assert_eq!(vec![7, 11, 12, 35, 40, 50, 77, 95, 99], ones);
639}
640
641#[test]
642fn iter_ones_range() {
643    fn test_range(from: usize, to: usize, capa: usize) {
644        assert!(to <= capa);
645        let mut fb = FixedBitSet::with_capacity(capa);
646        for i in from..to {
647            fb.insert(i);
648        }
649        let ones: Vec<_> = fb.ones().collect();
650        let expected: Vec<_> = (from..to).collect();
651        assert_eq!(expected, ones);
652    }
653
654    for i in 0..100 {
655      test_range(i, 100, 100);
656      test_range(0, i, 100);
657    }
658}
659
660#[should_panic]
661#[test]
662fn count_ones_oob() {
663    let fb = FixedBitSet::with_capacity(100);
664    fb.count_ones(90..101);
665}
666
667#[should_panic]
668#[test]
669fn count_ones_negative_range() {
670    let fb = FixedBitSet::with_capacity(100);
671    fb.count_ones(90..80);
672}
673
674#[test]
675fn count_ones_panic() {
676    for i in 1..128 {
677        let fb = FixedBitSet::with_capacity(i);
678        for j in 0..fb.len() + 1 {
679            for k in j..fb.len() + 1 {
680                assert_eq!(fb.count_ones(j..k), 0);
681            }
682        }
683    }
684}
685
686
687#[test]
688fn default() {
689    let fb = FixedBitSet::default();
690    assert_eq!(fb.len(), 0);
691}
692
693#[test]
694fn insert_range() {
695    let mut fb = FixedBitSet::with_capacity(97);
696    fb.insert_range(..3);
697    fb.insert_range(9..32);
698    fb.insert_range(37..81);
699    fb.insert_range(90..);
700    for i in 0..97 {
701        assert_eq!(fb.contains(i), i<3 || 9<=i&&i<32 || 37<=i&&i<81 || 90<=i);
702    }
703    assert!(!fb.contains(97));
704    assert!(!fb.contains(127));
705    assert!(!fb.contains(128));
706}
707
708#[test]
709fn set_range() {
710    let mut fb = FixedBitSet::with_capacity(48);
711    fb.insert_range(..);
712
713    fb.set_range(..32, false);
714    fb.set_range(37.., false);
715    fb.set_range(5..9, true);
716    fb.set_range(40..40, true);
717
718    for i in 0..48 {
719        assert_eq!(fb.contains(i), 5<=i&&i<9 || 32<=i&&i<37);
720    }
721    assert!(!fb.contains(48));
722    assert!(!fb.contains(64));
723}
724
725#[test]
726fn bitand_equal_lengths() {
727    let len = 109;
728    let a_end = 59;
729    let b_start = 23;
730    let mut a = FixedBitSet::with_capacity(len);
731    let mut b = FixedBitSet::with_capacity(len);
732    a.set_range(..a_end, true);
733    b.set_range(b_start.., true);
734    let ab = &a & &b;
735    for i in 0..b_start {
736        assert!(!ab.contains(i));
737    }
738    for i in b_start..a_end {
739        assert!(ab.contains(i));
740    }
741    for i in a_end..len {
742        assert!(!ab.contains(i));
743    }
744    assert_eq!(a.len(), ab.len());
745}
746
747#[test]
748fn bitand_first_smaller() {
749    let a_len = 113;
750    let b_len = 137;
751    let len = std::cmp::min(a_len, b_len);
752    let a_end = 97;
753    let b_start = 89;
754    let mut a = FixedBitSet::with_capacity(a_len);
755    let mut b = FixedBitSet::with_capacity(b_len);
756    a.set_range(..a_end, true);
757    b.set_range(b_start.., true);
758    let ab = &a & &b;
759    for i in 0..b_start {
760        assert!(!ab.contains(i));
761    }
762    for i in b_start..a_end {
763        assert!(ab.contains(i));
764    }
765    for i in a_end..len {
766        assert!(!ab.contains(i));
767    }
768    assert_eq!(a.len(), ab.len());
769}
770
771#[test]
772fn bitand_first_larger() {
773    let a_len = 173;
774    let b_len = 137;
775    let len = std::cmp::min(a_len, b_len);
776    let a_end = 107;
777    let b_start = 43;
778    let mut a = FixedBitSet::with_capacity(a_len);
779    let mut b = FixedBitSet::with_capacity(b_len);
780    a.set_range(..a_end, true);
781    b.set_range(b_start.., true);
782    let ab = &a & &b;
783    for i in 0..b_start {
784        assert!(!ab.contains(i));
785    }
786    for i in b_start..a_end {
787        assert!(ab.contains(i));
788    }
789    for i in a_end..len {
790        assert!(!ab.contains(i));
791    }
792    assert_eq!(b.len(), ab.len());
793}
794
795#[test]
796fn intersection() {
797    let len = 109;
798    let a_end = 59;
799    let b_start = 23;
800    let mut a = FixedBitSet::with_capacity(len);
801    let mut b = FixedBitSet::with_capacity(len);
802    a.set_range(..a_end, true);
803    b.set_range(b_start.., true);
804
805    let ab = a.intersection(&b).collect::<FixedBitSet>();
806
807    for i in 0..b_start {
808        assert!(!ab.contains(i));
809    }
810    for i in b_start..a_end {
811        assert!(ab.contains(i));
812    }
813    for i in a_end..len {
814        assert!(!ab.contains(i));
815    }
816}
817
818#[test]
819fn union() {
820    let a_len = 173;
821    let b_len = 137;
822    let a_start = 139;
823    let b_end = 107;
824    let mut a = FixedBitSet::with_capacity(a_len);
825    let mut b = FixedBitSet::with_capacity(b_len);
826    a.set_range(a_start.., true);
827    b.set_range(..b_end, true);
828    let ab = a.union(&b).collect::<FixedBitSet>();
829    for i in a_start..a_len {
830        assert!(ab.contains(i));
831    }
832    for i in 0..b_end {
833        assert!(ab.contains(i));
834    }
835    for i in b_end..a_start {
836        assert!(!ab.contains(i));
837    }
838}
839
840#[test]
841fn difference() {
842    let a_len = 83;
843    let b_len = 151;
844    let a_start = 0;
845    let a_end = 79;
846    let b_start = 53;
847    let mut a = FixedBitSet::with_capacity(a_len);
848    let mut b = FixedBitSet::with_capacity(b_len);
849    a.set_range(a_start..a_end, true);
850    b.set_range(b_start..b_len, true);
851    let a_diff_b = a.difference(&b).collect::<FixedBitSet>();
852    for i in a_start..b_start {
853        assert!(a_diff_b.contains(i));
854    }
855    for i in b_start..b_len {
856        assert!(!a_diff_b.contains(i));
857    }
858}
859
860#[test]
861fn bitor_equal_lengths() {
862    let len = 109;
863    let a_start = 17;
864    let a_end = 23;
865    let b_start = 19;
866    let b_end = 59;
867    let mut a = FixedBitSet::with_capacity(len);
868    let mut b = FixedBitSet::with_capacity(len);
869    a.set_range(a_start..a_end, true);
870    b.set_range(b_start..b_end, true);
871    let ab = &a | &b;
872    for i in 0..a_start {
873        assert!(!ab.contains(i));
874    }
875    for i in a_start..b_end {
876        assert!(ab.contains(i));
877    }
878    for i in b_end..len {
879        assert!(!ab.contains(i));
880    }
881    assert_eq!(ab.len(), len);
882}
883
884#[test]
885fn bitor_first_smaller() {
886    let a_len = 113;
887    let b_len = 137;
888    let a_end = 89;
889    let b_start = 97;
890    let mut a = FixedBitSet::with_capacity(a_len);
891    let mut b = FixedBitSet::with_capacity(b_len);
892    a.set_range(..a_end, true);
893    b.set_range(b_start.., true);
894    let ab = &a | &b;
895    for i in 0..a_end {
896        assert!(ab.contains(i));
897    }
898    for i in a_end..b_start {
899        assert!(!ab.contains(i));
900    }
901    for i in b_start..b_len {
902        assert!(ab.contains(i));
903    }
904    assert_eq!(b_len, ab.len());
905}
906
907#[test]
908fn bitor_first_larger() {
909    let a_len = 173;
910    let b_len = 137;
911    let a_start = 139;
912    let b_end = 107;
913    let mut a = FixedBitSet::with_capacity(a_len);
914    let mut b = FixedBitSet::with_capacity(b_len);
915    a.set_range(a_start.., true);
916    b.set_range(..b_end, true);
917    let ab = &a | &b;
918    for i in a_start..a_len {
919        assert!(ab.contains(i));
920    }
921    for i in 0..b_end {
922        assert!(ab.contains(i));
923    }
924    for i in b_end..a_start {
925        assert!(!ab.contains(i));
926    }
927    assert_eq!(a_len, ab.len());
928}
929
930#[test]
931fn extend_on_empty() {
932    let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167];
933    let mut fbs = FixedBitSet::with_capacity(0);
934    fbs.extend(items.iter().cloned());
935    let ones = fbs.ones().collect::<Vec<usize>>();
936    assert!(ones == items);
937}
938
939#[test]
940fn extend() {
941    let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167];
942    let mut fbs = FixedBitSet::with_capacity(168);
943    let new: Vec<usize> = vec![7, 37, 67, 137];
944    for i in &new {
945        fbs.put(*i);
946    }
947
948    fbs.extend(items.iter().cloned());
949
950    let ones = fbs.ones().collect::<Vec<usize>>();
951    let expected = {
952        let mut tmp = items.clone();
953        tmp.extend(new);
954        tmp.sort();
955        tmp.dedup();
956        tmp
957    };
958
959    assert!(ones == expected);
960}
961
962#[test]
963fn from_iterator() {
964    let items: Vec<usize> = vec![0, 2, 4, 6, 8];
965    let fb = items.iter().cloned().collect::<FixedBitSet>();
966    for i in items {
967        assert!(fb.contains(i));
968    }
969    for i in vec![1, 3, 5, 7] {
970        assert!(!fb.contains(i));
971    }
972    assert_eq!(fb.len(), 9);
973}
974
975#[test]
976fn from_iterator_ones() {
977    let len = 257;
978    let mut fb = FixedBitSet::with_capacity(len);
979    for i in (0..len).filter(|i| i % 7 == 0) {
980        fb.put(i);
981    }
982    fb.put(len - 1);
983    let dup = fb.ones().collect::<FixedBitSet>();
984    println!("{0:?}\n{1:?}", fb, dup);
985    println!("{0:?}\n{1:?}", fb.ones().collect::<Vec<usize>>(), dup.ones().collect::<Vec<usize>>());
986    assert_eq!(fb.len(), dup.len());
987    assert_eq!(fb.ones().collect::<Vec<usize>>(), dup.ones().collect::<Vec<usize>>());
988}
fixedbitset/lib.rs

fixedbitset/
lib.rs
