probabilistic_collections/
bit_vec.rs

1//! Growable list of bits.
2
3#[cfg(feature = "serde")]
4use serde_crate::{Deserialize, Serialize};
5use std::mem;
6use std::ops::{Index, Range};
7use std::slice;
8
9/// A growable list of bits implemented using a `Vec<u8>`
10///
11/// # Examples
12///
13///
14/// ```
15/// use probabilistic_collections::bit_vec::BitVec;
16///
17/// let mut bv = BitVec::from_elem(5, false);
18///
19/// bv.set(0, true);
20/// bv.set(1, true);
21/// bv.set(2, true);
22/// assert_eq!(
23///     bv.iter().collect::<Vec<bool>>(),
24///     vec![true, true, true, false, false],
25/// );
26///
27/// bv.set_all(true);
28/// assert_eq!(
29///     bv.iter().collect::<Vec<bool>>(),
30///     vec![true, true, true, true, true],
31/// );
32///
33/// bv.flip(0);
34/// bv.flip_all();
35/// assert_eq!(
36///     bv.iter().collect::<Vec<bool>>(),
37///     vec![true, false, false, false, false],
38/// );
39///
40/// bv.push(true);
41/// assert_eq!(
42///     bv.iter().collect::<Vec<bool>>(),
43///     vec![true, false, false, false, false, true],
44/// );
45/// assert_eq!(bv.pop(), Some(true));
46///
47/// let clone = bv.clone();
48/// bv.flip_all();
49/// bv.union(&clone);
50/// assert_eq!(
51///     bv.iter().collect::<Vec<bool>>(),
52///     vec![true, true, true, true, true],
53/// );
54/// ```
55#[derive(Debug, PartialEq)]
56#[cfg_attr(
57    feature = "serde",
58    derive(Deserialize, Serialize),
59    serde(crate = "serde_crate")
60)]
61pub struct BitVec {
62    blocks: Vec<u8>,
63    len: usize,
64    one_count: usize,
65}
66
67const BLOCK_BIT_COUNT: usize = mem::size_of::<u8>() * 8;
68
69impl BitVec {
70    fn get_block_count(len: usize) -> usize {
71        (len + BLOCK_BIT_COUNT - 1) / BLOCK_BIT_COUNT
72    }
73
74    fn reverse_byte(byte: u8) -> u8 {
75        let mut ret = 0;
76        for i in 0..BLOCK_BIT_COUNT {
77            ret |= (byte >> i & 1) << (BLOCK_BIT_COUNT - i - 1);
78        }
79        ret
80    }
81
82    fn clear_extra_bits(&mut self) {
83        let extra_bits = self.len() % BLOCK_BIT_COUNT;
84        if extra_bits > 0 {
85            let mask = (1 << extra_bits) - 1;
86            let blocks_len = self.blocks.len();
87            let block = &mut self.blocks[blocks_len - 1];
88            *block &= mask;
89        }
90    }
91
92    /// Constructs a new `BitVec` with a certain number of bits. All bits are initialized to false.
93    ///
94    /// # Examples
95    ///
96    /// ```
97    /// use probabilistic_collections::bit_vec::BitVec;
98    ///
99    /// let bv = BitVec::new(5);
100    /// assert_eq!(
101    ///     bv.iter().collect::<Vec<bool>>(),
102    ///     vec![false, false, false, false, false],
103    /// );
104    /// ```
105    pub fn new(len: usize) -> Self {
106        Self {
107            blocks: vec![0; Self::get_block_count(len)],
108            len,
109            one_count: 0,
110        }
111    }
112
113    /// Constructs a new `BitVec` with a certain number of bits. All bits are initialized to `bit`.
114    ///
115    /// # Examples
116    ///
117    /// ```
118    /// use probabilistic_collections::bit_vec::BitVec;
119    ///
120    /// let bv = BitVec::from_elem(5, true);
121    /// assert_eq!(
122    ///     bv.iter().collect::<Vec<bool>>(),
123    ///     vec![true, true, true, true, true],
124    /// );
125    /// ```
126    pub fn from_elem(len: usize, bit: bool) -> Self {
127        let mut ret = BitVec {
128            blocks: vec![if bit { <u8>::max_value() } else { 0 }; Self::get_block_count(len)],
129            len,
130            one_count: if bit { len } else { 0 },
131        };
132        ret.clear_extra_bits();
133        ret
134    }
135
136    /// Constructs a `BitVec` from a byte slice. Each byte becomes eight bits, with the most
137    /// signficant bits of each byte coming first.
138    ///
139    /// # Examples
140    ///
141    /// ```
142    /// use probabilistic_collections::bit_vec::BitVec;
143    ///
144    /// let bv = BitVec::from_bytes(&[0b11010000]);
145    /// assert_eq!(
146    ///     bv.iter().collect::<Vec<bool>>(),
147    ///     vec![true, true, false, true, false, false, false, false],
148    /// );
149    /// ```
150    pub fn from_bytes(bytes: &[u8]) -> Self {
151        let len = bytes.len() * BLOCK_BIT_COUNT;
152        BitVec {
153            blocks: bytes
154                .to_vec()
155                .iter()
156                .map(|byte| Self::reverse_byte(*byte))
157                .collect(),
158            len,
159            one_count: bytes
160                .to_vec()
161                .iter()
162                .map(|byte| byte.count_ones() as usize)
163                .sum(),
164        }
165    }
166
167    /// Returns the byte-vec representation of the `BitVec` with the first bit in the `BitVec`
168    /// becoming the high-order bit of the first byte.
169    ///
170    /// # Examples
171    ///
172    /// ```
173    /// use probabilistic_collections::bit_vec::BitVec;
174    ///
175    /// let mut bv = BitVec::new(8);
176    ///
177    /// bv.set(0, true);
178    /// bv.set(1, true);
179    /// bv.set(3, true);
180    ///
181    /// assert_eq!(bv.to_bytes(), vec![0b11010000]);
182    /// ```
183    pub fn to_bytes(&self) -> Vec<u8> {
184        self.blocks
185            .iter()
186            .map(|byte| Self::reverse_byte(*byte))
187            .collect()
188    }
189
190    /// Constructs a new, empty `BitVec` with a certain capacity.
191    ///
192    /// # Examples
193    ///
194    /// ```
195    /// use probabilistic_collections::bit_vec::BitVec;
196    ///
197    /// let bv = BitVec::with_capacity(5);
198    /// ```
199    pub fn with_capacity(len: usize) -> Self {
200        BitVec {
201            blocks: Vec::with_capacity(Self::get_block_count(len)),
202            len: 0,
203            one_count: 0,
204        }
205    }
206
207    /// Sets the value at index `index` to `bit`.
208    ///
209    /// # Panics
210    ///
211    /// Panics if attempt to set an index out-of-bounds.
212    ///
213    /// # Examples
214    ///
215    /// ```
216    /// use probabilistic_collections::bit_vec::BitVec;
217    ///
218    /// let mut bv = BitVec::new(5);
219    /// bv.set(1, true);
220    ///
221    /// assert_eq!(bv.get(0), Some(false));
222    /// assert_eq!(bv.get(1), Some(true));
223    /// ```
224    pub fn set(&mut self, index: usize, bit: bool) {
225        assert!(index < self.len);
226        let block_index = index / BLOCK_BIT_COUNT;
227        let bit_index = index % BLOCK_BIT_COUNT;
228        let mask = 1 << bit_index;
229        let prev = ((self.blocks[block_index] >> bit_index) & 1) != 0;
230        if bit {
231            if !prev {
232                self.one_count += 1;
233            }
234            self.blocks[block_index] |= mask;
235        } else {
236            if prev {
237                self.one_count -= 1;
238            }
239            self.blocks[block_index] &= !mask;
240        }
241    }
242
243    /// Returns the value at index `index`, or `None` if index is out of bounds.
244    ///
245    /// # Examples
246    ///
247    /// ```
248    /// use probabilistic_collections::bit_vec::BitVec;
249    ///
250    /// let mut bv = BitVec::new(5);
251    /// bv.set(1, true);
252    ///
253    /// assert_eq!(bv.get(0), Some(false));
254    /// assert_eq!(bv.get(1), Some(true));
255    /// ```
256    pub fn get(&self, index: usize) -> Option<bool> {
257        if index >= self.len {
258            None
259        } else {
260            let block_index = index / BLOCK_BIT_COUNT;
261            let bit_index = index % BLOCK_BIT_COUNT;
262            self.blocks
263                .get(block_index)
264                .map(|block| ((block >> bit_index) & 1) != 0)
265        }
266    }
267
268    /// Sets all values in the `BitVec` to `bit`.
269    ///
270    /// # Panics
271    ///
272    /// Panics if attempting to set a bit out-of-bounds.
273    ///
274    /// # Examples
275    ///
276    /// ```
277    /// use probabilistic_collections::bit_vec::BitVec;
278    ///
279    /// let mut bv = BitVec::from_elem(5, false);
280    /// bv.set_all(true);
281    ///
282    /// assert_eq!(
283    ///     bv.iter().collect::<Vec<bool>>(),
284    ///     vec![true, true, true, true, true],
285    /// );
286    /// ```
287    pub fn set_all(&mut self, bit: bool) {
288        let mask;
289        if bit {
290            mask = !0;
291            self.one_count = self.len;
292        } else {
293            mask = 0;
294            self.one_count = 0;
295        }
296        for block in &mut self.blocks {
297            *block = mask;
298        }
299        self.clear_extra_bits();
300    }
301
302    /// Flip the value at index `index`.
303    ///
304    /// # Panics
305    ///
306    /// Panics if attempt to flip an index out-of-bounds.
307    ///
308    /// # Examples
309    ///
310    /// ```
311    /// use probabilistic_collections::bit_vec::BitVec;
312    ///
313    /// let mut bv = BitVec::from_elem(5, false);
314    ///
315    /// bv.flip(0);
316    /// assert_eq!(bv.get(0), Some(true));
317    ///
318    /// bv.flip(1);
319    /// assert_eq!(bv.get(0), Some(true));
320    /// ```
321    pub fn flip(&mut self, index: usize) {
322        assert!(index < self.len);
323        let block_index = index / BLOCK_BIT_COUNT;
324        let bit_index = index % BLOCK_BIT_COUNT;
325        let mask = 1 << bit_index;
326        if (self.blocks[block_index] >> bit_index) & 1 == 0 {
327            self.one_count += 1;
328            self.blocks[block_index] |= mask;
329        } else {
330            self.one_count -= 1;
331            self.blocks[block_index] &= !mask;
332        }
333    }
334
335    /// Flips all values in the `BitVec`.
336    ///
337    /// # Examples
338    ///
339    /// ```
340    /// use probabilistic_collections::bit_vec::BitVec;
341    ///
342    /// let mut bv = BitVec::from_elem(5, false);
343    ///
344    /// bv.flip_all();
345    /// assert_eq!(
346    ///     bv.iter().collect::<Vec<bool>>(),
347    ///     vec![true, true, true, true, true],
348    /// );
349    ///
350    /// bv.flip_all();
351    /// assert_eq!(
352    ///     bv.iter().collect::<Vec<bool>>(),
353    ///     vec![false, false, false, false, false],
354    /// );
355    /// ```
356    pub fn flip_all(&mut self) {
357        self.one_count = self.len - self.one_count;
358        for block in &mut self.blocks {
359            *block = !*block;
360        }
361    }
362
363    fn apply<F>(&mut self, other: &BitVec, mut op: F)
364    where
365        F: FnMut(u8, u8) -> u8,
366    {
367        assert_eq!(self.len(), other.len());
368        assert_eq!(self.blocks.len(), other.blocks.len());
369        for (x, y) in self.blocks_mut().zip(other.blocks()) {
370            *x = op(*x, y);
371        }
372        self.one_count = 0;
373        for index in 0..self.blocks.len() {
374            if index == self.blocks.len() - 1 && self.len() % BLOCK_BIT_COUNT != 0 {
375                let shift = BLOCK_BIT_COUNT - self.len() % BLOCK_BIT_COUNT;
376                self.one_count += (self.blocks[index] << shift).count_ones() as usize;
377            } else {
378                self.one_count += self.blocks[index].count_ones() as usize;
379            }
380        }
381    }
382
383    /// Sets `self` to the union of `self` and `other`.
384    ///
385    /// # Panics
386    ///
387    /// Panics if the two `BitVec` are of different lengths.
388    ///
389    /// # Examples
390    ///
391    /// ```
392    /// use probabilistic_collections::bit_vec::BitVec;
393    ///
394    /// let mut bv1 = BitVec::new(4);
395    /// bv1.set(0, true);
396    /// bv1.set(1, true);
397    ///
398    /// let mut bv2 = BitVec::new(4);
399    /// bv2.set(0, true);
400    /// bv2.set(2, true);
401    ///
402    /// bv1.union(&bv2);
403    /// assert_eq!(
404    ///     bv1.iter().collect::<Vec<bool>>(),
405    ///     vec![true, true, true, false],
406    /// );
407    /// ```
408    pub fn union(&mut self, other: &Self) {
409        self.apply(other, |x, y| x | y)
410    }
411
412    /// Sets `self` to the intersection of `self` and `other`.
413    ///
414    /// # Panics
415    ///
416    /// Panics if the two `BitVec` are of different lengths.
417    ///
418    /// # Examples
419    ///
420    /// ```
421    /// use probabilistic_collections::bit_vec::BitVec;
422    ///
423    /// let mut bv1 = BitVec::new(4);
424    /// bv1.set(0, true);
425    /// bv1.set(1, true);
426    ///
427    /// let mut bv2 = BitVec::new(4);
428    /// bv2.set(0, true);
429    /// bv2.set(2, true);
430    ///
431    /// bv1.intersection(&bv2);
432    /// assert_eq!(
433    ///     bv1.iter().collect::<Vec<bool>>(),
434    ///     vec![true, false, false, false],
435    /// );
436    /// ```
437    pub fn intersection(&mut self, other: &Self) {
438        self.apply(other, |x, y| x & y)
439    }
440
441    /// Sets `self` to the difference of `self` and `other`.
442    ///
443    /// # Panics
444    ///
445    /// Panics if the two `BitVec` are of different lengths.
446    ///
447    /// # Examples
448    ///
449    /// ```
450    /// use probabilistic_collections::bit_vec::BitVec;
451    ///
452    /// let mut bv1 = BitVec::new(4);
453    /// bv1.set(0, true);
454    /// bv1.set(1, true);
455    ///
456    /// let mut bv2 = BitVec::new(4);
457    /// bv2.set(0, true);
458    /// bv2.set(2, true);
459    ///
460    /// bv1.difference(&bv2);
461    /// assert_eq!(
462    ///     bv1.iter().collect::<Vec<bool>>(),
463    ///     vec![false, true, false, false],
464    /// );
465    /// ```
466    pub fn difference(&mut self, other: &Self) {
467        self.apply(other, |x, y| x & !y)
468    }
469
470    /// Sets `self` to the symmetric difference of `self` and `other`.
471    ///
472    /// # Panics
473    ///
474    /// Panics if the two `BitVec` are of different lengths.
475    ///
476    /// # Examples
477    ///
478    /// ```
479    /// use probabilistic_collections::bit_vec::BitVec;
480    ///
481    /// let mut bv1 = BitVec::new(4);
482    /// bv1.set(0, true);
483    /// bv1.set(1, true);
484    ///
485    /// let mut bv2 = BitVec::new(4);
486    /// bv2.set(0, true);
487    /// bv2.set(2, true);
488    ///
489    /// bv1.symmetric_difference(&bv2);
490    /// assert_eq!(
491    ///     bv1.iter().collect::<Vec<bool>>(),
492    ///     vec![false, true, true, false],
493    /// );
494    /// ```
495    pub fn symmetric_difference(&mut self, other: &Self) {
496        self.apply(other, |x, y| (x & !y) | (!x & y))
497    }
498
499    /// Truncates a `BitVec`, dropping excess elements.
500    ///
501    /// # Examples
502    ///
503    /// ```
504    /// use probabilistic_collections::bit_vec::BitVec;
505    ///
506    /// let mut bv = BitVec::from_elem(5, false);
507    ///
508    /// bv.truncate(2);
509    /// assert_eq!(bv.iter().collect::<Vec<bool>>(), vec![false, false]);
510    /// ```
511    pub fn truncate(&mut self, len: usize) {
512        if len < self.len {
513            self.len = len;
514            self.blocks.truncate(Self::get_block_count(len));
515            self.clear_extra_bits();
516        }
517    }
518
519    /// Reserves capacity for at least `additional` more bits to be inserted in the given
520    /// `BitVec`.
521    ///
522    /// # Examples
523    ///
524    ///
525    /// ```
526    /// use probabilistic_collections::bit_vec::BitVec;
527    ///
528    /// let mut bv = BitVec::from_elem(5, false);
529    ///
530    /// bv.reserve(10);
531    /// assert_eq!(bv.len(), 5);
532    /// assert!(bv.capacity() >= 16);
533    /// ```
534    pub fn reserve(&mut self, additional: usize) {
535        let desired_cap = self.len + additional;
536        if desired_cap > self.capacity() {
537            let additional_blocks = Self::get_block_count(desired_cap) - self.blocks.len();
538            self.blocks.reserve(additional_blocks);
539        }
540    }
541
542    /// Reserves capacity for exactly `additional` more bits to be inserted in the given
543    /// `BitVec`.
544    ///
545    /// # Examples
546    ///
547    ///
548    /// ```
549    /// use probabilistic_collections::bit_vec::BitVec;
550    ///
551    /// let mut bv = BitVec::from_elem(5, false);
552    /// bv.reserve_exact(10);
553    /// assert_eq!(bv.len(), 5);
554    /// assert_eq!(bv.capacity(), 16);
555    /// ```
556    pub fn reserve_exact(&mut self, additional: usize) {
557        let desired_cap = self.len + additional;
558        if desired_cap > self.capacity() {
559            let additional_blocks = Self::get_block_count(desired_cap) - self.blocks.len();
560            self.blocks.reserve_exact(additional_blocks);
561        }
562    }
563
564    /// Returns and removes the last element of the `BitVec`. Returns `None` if the `BitVec` is
565    /// empty.
566    ///
567    /// # Examples
568    ///
569    /// ```
570    /// use probabilistic_collections::bit_vec::BitVec;
571    ///
572    /// let mut bv = BitVec::from_elem(1, false);
573    ///
574    /// assert_eq!(bv.pop(), Some(false));
575    /// assert_eq!(bv.pop(), None);
576    /// ```
577    pub fn pop(&mut self) -> Option<bool> {
578        if self.is_empty() {
579            None
580        } else {
581            let index = self.len - 1;
582            let ret = self.get(index);
583            self.set(index, false);
584            self.len -= 1;
585            if self.len % BLOCK_BIT_COUNT == 0 {
586                self.blocks.pop();
587            }
588            ret
589        }
590    }
591
592    /// Pushes an element into the `BitVec`.
593    ///
594    /// # Examples
595    ///
596    /// ```
597    /// use probabilistic_collections::bit_vec::BitVec;
598    ///
599    /// let mut bv = BitVec::from_elem(1, false);
600    ///
601    /// bv.push(true);
602    /// assert_eq!(bv.get(1), Some(true));
603    /// ```
604    pub fn push(&mut self, bit: bool) {
605        if self.len % BLOCK_BIT_COUNT == 0 {
606            self.blocks.push(0);
607        }
608        let index = self.len;
609        self.len += 1;
610        self.set(index, bit);
611    }
612
613    fn blocks(&self) -> Blocks<'_> {
614        Blocks {
615            iter: self.blocks.iter(),
616        }
617    }
618
619    fn blocks_mut(&mut self) -> BlocksMut<'_> {
620        self.blocks.iter_mut()
621    }
622
623    /// Returns an iterator over the elements of the vector in order.
624    ///
625    /// # Examples
626    ///
627    /// ```
628    /// use probabilistic_collections::bit_vec::BitVec;
629    ///
630    /// let mut bv = BitVec::from_elem(1, false);
631    ///
632    /// bv.push(true);
633    /// assert_eq!(bv.iter().collect::<Vec<bool>>(), vec![false, true]);
634    /// ```
635    pub fn iter(&self) -> BitVecIter<'_> {
636        BitVecIter {
637            bit_vec: self,
638            range: 0..self.len,
639        }
640    }
641
642    /// Returns `true` if the `BitVec` is empty.
643    ///
644    /// # Examples
645    ///
646    /// ```
647    /// use probabilistic_collections::bit_vec::BitVec;
648    ///
649    /// let mut bv = BitVec::from_elem(1, false);
650    ///
651    /// assert!(!bv.is_empty());
652    /// bv.pop();
653    /// assert!(bv.is_empty());
654    /// ```
655    pub fn is_empty(&self) -> bool {
656        self.len == 0
657    }
658
659    /// Returns the number of elements in the `BitVec`.
660    ///
661    /// # Examples
662    ///
663    /// ```
664    /// use probabilistic_collections::bit_vec::BitVec;
665    ///
666    /// let mut bv = BitVec::from_elem(1, false);
667    ///
668    /// assert_eq!(bv.len(), 1);
669    /// bv.pop();
670    /// assert_eq!(bv.len(), 0);
671    /// ```
672    pub fn len(&self) -> usize {
673        self.len
674    }
675
676    /// Returns the capacity of the `BitVec`.
677    ///
678    /// # Examples
679    ///
680    /// ```
681    /// use probabilistic_collections::bit_vec::BitVec;
682    ///
683    /// let mut bv = BitVec::new(0);
684    ///
685    /// bv.reserve_exact(10);
686    /// assert_eq!(bv.capacity(), 16);
687    /// ```
688    pub fn capacity(&self) -> usize {
689        self.blocks.capacity() * BLOCK_BIT_COUNT
690    }
691
692    /// Returns the number of set bits in the `BitVec`.
693    ///
694    /// # Examples
695    ///
696    /// ```
697    /// use probabilistic_collections::bit_vec::BitVec;
698    ///
699    /// let bv = BitVec::from_bytes(&[0b11010000]);
700    /// assert_eq!(bv.count_ones(), 3);
701    /// ```
702    pub fn count_ones(&self) -> usize {
703        self.one_count
704    }
705
706    /// Returns the number of unset bits in the `BitVec`.
707    ///
708    /// # Examples
709    ///
710    /// ```
711    /// use probabilistic_collections::bit_vec::BitVec;
712    ///
713    /// let bv = BitVec::from_bytes(&[0b11010000]);
714    /// assert_eq!(bv.count_zeros(), 5);
715    /// ```
716    pub fn count_zeros(&self) -> usize {
717        self.len - self.one_count
718    }
719}
720
721impl Clone for BitVec {
722    fn clone(&self) -> Self {
723        BitVec {
724            blocks: self.blocks.clone(),
725            len: self.len,
726            one_count: self.one_count,
727        }
728    }
729
730    fn clone_from(&mut self, source: &Self) {
731        self.len = source.len;
732        self.blocks.clone_from(&source.blocks);
733    }
734}
735
736/// An owning iterator for `BitVec`.
737///
738/// This iterator yields bits in order.
739pub struct BitVecIter<'a> {
740    bit_vec: &'a BitVec,
741    range: Range<usize>,
742}
743
744impl<'a> Iterator for BitVecIter<'a> {
745    type Item = bool;
746
747    fn next(&mut self) -> Option<bool> {
748        self.range
749            .next()
750            .map(|index| self.bit_vec.get(index).unwrap())
751    }
752}
753
754impl<'a> IntoIterator for &'a BitVec {
755    type IntoIter = BitVecIter<'a>;
756    type Item = bool;
757
758    fn into_iter(self) -> Self::IntoIter {
759        self.iter()
760    }
761}
762
763/// An iterator for `BitVec`.
764///
765/// This iterator yields bits in order.
766pub struct BitVecIntoIter {
767    bit_vec: BitVec,
768    range: Range<usize>,
769}
770
771impl Iterator for BitVecIntoIter {
772    type Item = bool;
773
774    fn next(&mut self) -> Option<bool> {
775        self.range
776            .next()
777            .map(|index| self.bit_vec.get(index).unwrap())
778    }
779}
780
781impl IntoIterator for BitVec {
782    type IntoIter = BitVecIntoIter;
783    type Item = bool;
784
785    fn into_iter(self) -> Self::IntoIter {
786        let len = self.len;
787        Self::IntoIter {
788            bit_vec: self,
789            range: 0..len,
790        }
791    }
792}
793
794type BlocksMut<'a> = slice::IterMut<'a, u8>;
795
796struct Blocks<'a> {
797    iter: slice::Iter<'a, u8>,
798}
799
800impl<'a> Iterator for Blocks<'a> {
801    type Item = u8;
802
803    fn next(&mut self) -> Option<u8> {
804        self.iter.next().cloned()
805    }
806}
807
808static TRUE: bool = true;
809static FALSE: bool = false;
810
811impl Index<usize> for BitVec {
812    type Output = bool;
813
814    fn index(&self, index: usize) -> &bool {
815        if self.get(index).expect("Error: index out of bounds.") {
816            &TRUE
817        } else {
818            &FALSE
819        }
820    }
821}
822
823#[cfg(test)]
824mod tests {
825    use super::BitVec;
826
827    #[test]
828    fn test_new() {
829        let bv = BitVec::new(5);
830        assert_eq!(
831            bv.iter().collect::<Vec<bool>>(),
832            vec![false, false, false, false, false]
833        );
834        assert_eq!(bv.count_ones(), 0);
835        assert_eq!(bv.count_zeros(), 5);
836    }
837
838    #[test]
839    fn test_from_elem() {
840        let bv = BitVec::from_elem(5, true);
841        assert_eq!(
842            bv.iter().collect::<Vec<bool>>(),
843            vec![true, true, true, true, true]
844        );
845        assert_eq!(bv.count_ones(), 5);
846        assert_eq!(bv.count_zeros(), 0);
847    }
848
849    #[test]
850    fn test_from_bytes() {
851        let bv = BitVec::from_bytes(&[0b1101_0000]);
852        assert_eq!(
853            bv.iter().collect::<Vec<bool>>(),
854            vec![true, true, false, true, false, false, false, false],
855        );
856        assert_eq!(bv.count_ones(), 3);
857        assert_eq!(bv.count_zeros(), 5);
858    }
859
860    #[test]
861    fn test_to_bytes() {
862        let mut bv = BitVec::new(8);
863        bv.set(0, true);
864        bv.set(1, true);
865        bv.set(3, true);
866
867        assert_eq!(bv.to_bytes(), vec![0b1101_0000]);
868    }
869
870    #[test]
871    fn test_with_capacity() {
872        let bv = BitVec::with_capacity(10);
873
874        assert_eq!(bv.capacity(), 16);
875        assert_eq!(bv.count_ones(), 0);
876        assert_eq!(bv.count_zeros(), 0);
877    }
878
879    #[test]
880    fn test_set_get() {
881        let mut bv = BitVec::new(2);
882        bv.set(0, true);
883        bv.set(1, false);
884
885        assert_eq!(bv[0], true);
886        assert_eq!(bv[1], false);
887        assert_eq!(bv.get(2), None);
888        assert_eq!(bv.count_ones(), 1);
889        assert_eq!(bv.count_zeros(), 1);
890    }
891
892    #[test]
893    fn test_set_all() {
894        let mut bv = BitVec::new(3);
895
896        bv.set_all(true);
897        assert_eq!(bv.iter().collect::<Vec<bool>>(), vec![true, true, true]);
898
899        bv.set_all(false);
900        assert_eq!(bv.iter().collect::<Vec<bool>>(), vec![false, false, false]);
901    }
902
903    #[test]
904    fn test_flip() {
905        let mut bv = BitVec::new(1);
906
907        bv.flip(0);
908        assert_eq!(bv.get(0), Some(true));
909
910        bv.flip(0);
911        assert_eq!(bv.get(0), Some(false));
912    }
913
914    #[test]
915    fn test_flip_all() {
916        let mut bv = BitVec::new(3);
917
918        bv.flip_all();
919        assert_eq!(bv.iter().collect::<Vec<bool>>(), vec![true, true, true]);
920        assert_eq!(bv.count_ones(), 3);
921        assert_eq!(bv.count_zeros(), 0);
922
923        bv.flip_all();
924        assert_eq!(bv.iter().collect::<Vec<bool>>(), vec![false, false, false]);
925        assert_eq!(bv.count_ones(), 0);
926        assert_eq!(bv.count_zeros(), 3);
927    }
928
929    #[test]
930    fn test_union() {
931        let mut bv1 = BitVec::new(4);
932        bv1.set(0, true);
933        bv1.set(1, true);
934
935        let mut bv2 = BitVec::new(4);
936        bv2.set(0, true);
937        bv2.set(2, true);
938
939        bv1.union(&bv2);
940        assert_eq!(
941            bv1.iter().collect::<Vec<bool>>(),
942            vec![true, true, true, false]
943        );
944        assert_eq!(bv1.count_ones(), 3);
945        assert_eq!(bv1.count_zeros(), 1);
946    }
947
948    #[test]
949    fn test_intersection() {
950        let mut bv1 = BitVec::new(4);
951        bv1.set(0, true);
952        bv1.set(1, true);
953
954        let mut bv2 = BitVec::new(4);
955        bv2.set(0, true);
956        bv2.set(2, true);
957
958        bv1.intersection(&bv2);
959        assert_eq!(
960            bv1.iter().collect::<Vec<bool>>(),
961            vec![true, false, false, false]
962        );
963        assert_eq!(bv1.count_ones(), 1);
964        assert_eq!(bv1.count_zeros(), 3);
965    }
966
967    #[test]
968    fn test_difference() {
969        let mut bv1 = BitVec::new(4);
970        bv1.set(0, true);
971        bv1.set(1, true);
972
973        let mut bv2 = BitVec::new(4);
974        bv2.set(0, true);
975        bv2.set(2, true);
976
977        bv1.difference(&bv2);
978        assert_eq!(
979            bv1.iter().collect::<Vec<bool>>(),
980            vec![false, true, false, false]
981        );
982        assert_eq!(bv1.count_ones(), 1);
983        assert_eq!(bv1.count_zeros(), 3);
984    }
985
986    #[test]
987    fn test_symmetric_difference() {
988        let mut bv1 = BitVec::new(4);
989        bv1.set(0, true);
990        bv1.set(1, true);
991
992        let mut bv2 = BitVec::new(4);
993        bv2.set(0, true);
994        bv2.set(2, true);
995
996        bv1.symmetric_difference(&bv2);
997        assert_eq!(
998            bv1.iter().collect::<Vec<bool>>(),
999            vec![false, true, true, false]
1000        );
1001        assert_eq!(bv1.count_ones(), 2);
1002        assert_eq!(bv1.count_zeros(), 2);
1003    }
1004
1005    #[test]
1006    fn test_truncate() {
1007        let mut bv = BitVec::from_elem(9, false);
1008
1009        bv.truncate(1);
1010        assert_eq!(bv.iter().collect::<Vec<bool>>(), vec![false]);
1011        assert_eq!(bv.count_ones(), 0);
1012        assert_eq!(bv.count_zeros(), 1);
1013    }
1014
1015    #[test]
1016    fn test_reserve() {
1017        let mut bv = BitVec::from_elem(1, false);
1018
1019        bv.reserve(9);
1020        assert_eq!(bv.len(), 1);
1021        assert!(bv.capacity() >= 16);
1022    }
1023
1024    #[test]
1025    fn test_reserve_exact() {
1026        let mut bv = BitVec::from_elem(1, false);
1027
1028        bv.reserve_exact(9);
1029        assert_eq!(bv.len(), 1);
1030        assert!(bv.capacity() == 16);
1031    }
1032
1033    #[test]
1034    fn test_push_pop() {
1035        let mut bv = BitVec::new(0);
1036        assert_eq!(bv.count_ones(), 0);
1037        assert_eq!(bv.count_zeros(), 0);
1038
1039        bv.push(true);
1040        assert_eq!(bv.count_ones(), 1);
1041        assert_eq!(bv.count_zeros(), 0);
1042
1043        bv.push(false);
1044        assert_eq!(bv.count_ones(), 1);
1045        assert_eq!(bv.count_zeros(), 1);
1046
1047        assert_eq!(bv.pop(), Some(false));
1048        assert_eq!(bv.count_ones(), 1);
1049        assert_eq!(bv.count_zeros(), 0);
1050
1051        assert_eq!(bv.pop(), Some(true));
1052        assert_eq!(bv.count_ones(), 0);
1053        assert_eq!(bv.count_zeros(), 0);
1054
1055        assert_eq!(bv.pop(), None);
1056    }
1057
1058    #[test]
1059    fn test_push() {
1060        let mut bv = BitVec::from_elem(1, false);
1061
1062        bv.push(true);
1063        assert_eq!(bv.get(1), Some(true));
1064        assert_eq!(bv.count_ones(), 1);
1065        assert_eq!(bv.count_zeros(), 1);
1066    }
1067
1068    #[test]
1069    fn test_is_empty() {
1070        let mut bv = BitVec::new(0);
1071
1072        assert!(bv.is_empty());
1073
1074        bv.push(true);
1075        assert!(!bv.is_empty());
1076    }
1077
1078    #[test]
1079    fn test_len() {
1080        let mut bv = BitVec::new(0);
1081
1082        assert_eq!(bv.len(), 0);
1083
1084        bv.push(true);
1085        assert_eq!(bv.len(), 1);
1086    }
1087
1088    #[test]
1089    fn test_clone() {
1090        let bv = BitVec::from_bytes(&[0b1101_0000]);
1091        let mut cloned = BitVec::new(0);
1092
1093        assert_eq!(
1094            bv.clone().iter().collect::<Vec<bool>>(),
1095            vec![true, true, false, true, false, false, false, false],
1096        );
1097
1098        cloned.clone_from(&bv);
1099        assert_eq!(
1100            cloned.iter().collect::<Vec<bool>>(),
1101            vec![true, true, false, true, false, false, false, false],
1102        );
1103    }
1104
1105    #[test]
1106    fn test_iter() {
1107        let bv = BitVec::from_bytes(&[0b1101_0000]);
1108
1109        assert_eq!(
1110            (&bv).into_iter().collect::<Vec<bool>>(),
1111            vec![true, true, false, true, false, false, false, false],
1112        );
1113
1114        assert_eq!(
1115            bv.into_iter().collect::<Vec<bool>>(),
1116            vec![true, true, false, true, false, false, false, false],
1117        );
1118    }
1119}
probabilistic_collections/bit_vec.rs

probabilistic_collections/
bit_vec.rs
