probabilistic_collections/
bit_array_vec.rs

1//! Growable list of bit arrays.
2
3#[cfg(feature = "serde")]
4use serde_crate::{Deserialize, Serialize};
5use std::cmp;
6use std::iter;
7use std::mem;
8use std::ops::Range;
9
10/// A growable list of bit arrays implemented using a `Vec<u8>`.
11///
12/// The bit arrays contained in the `BitArrayVec` must all be the same size. `BitArrayVec` is very
13/// memory efficient for small bit arrays for a small time tradeoff.
14///
15/// # Examples
16///
17/// ```
18/// use probabilistic_collections::bit_array_vec::BitArrayVec;
19///
20/// let mut bav = BitArrayVec::new(4, 4);
21///
22/// bav.set(0, &[0]);
23/// bav.set(1, &[1]);
24/// bav.set(2, &[2]);
25/// bav.set(3, &[3]);
26///
27/// assert_eq!(
28///     bav.iter().collect::<Vec<Vec<u8>>>(),
29///     vec![vec![0], vec![1], vec![2], vec![3]],
30/// );
31/// ```
32#[derive(Debug, PartialEq)]
33#[cfg_attr(
34    feature = "serde",
35    derive(Deserialize, Serialize),
36    serde(crate = "serde_crate")
37)]
38pub struct BitArrayVec {
39    blocks: Vec<u8>,
40    bit_count: usize,
41    occupied_len: usize,
42    len: usize,
43}
44
45const BLOCK_BIT_COUNT: usize = mem::size_of::<u8>() * 8;
46
47impl BitArrayVec {
48    fn get_block_count(bit_count: usize, len: usize) -> usize {
49        (bit_count * len + BLOCK_BIT_COUNT - 1) / BLOCK_BIT_COUNT
50    }
51
52    fn get_elem_count(bit_count: usize, block_count: usize) -> usize {
53        (block_count * BLOCK_BIT_COUNT) / bit_count
54    }
55
56    /// Constructs a new `BitArrayVec` with a certain number of bit arrays. All bit arrays are
57    /// initialized to all zeros.
58    ///
59    /// # Examples
60    ///
61    /// ```
62    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
63    ///
64    /// let bav = BitArrayVec::new(5, 4);
65    /// assert_eq!(
66    ///     bav.iter().collect::<Vec<Vec<u8>>>(),
67    ///     vec![vec![0], vec![0], vec![0], vec![0]],
68    /// );
69    /// ```
70    pub fn new(bit_count: usize, len: usize) -> Self {
71        BitArrayVec {
72            blocks: vec![0; Self::get_block_count(bit_count, len)],
73            bit_count,
74            occupied_len: 0,
75            len,
76        }
77    }
78
79    /// Constructs a new `BitArrayVec` with a certain number of bit arrays. All bit arrays are
80    /// initialized to `bytes`.
81    ///
82    /// # Examples
83    ///
84    /// ```
85    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
86    ///
87    /// let bav = BitArrayVec::from_elem(5, 4, &[1]);
88    /// assert_eq!(
89    ///     bav.iter().collect::<Vec<Vec<u8>>>(),
90    ///     vec![vec![1], vec![1], vec![1], vec![1]],
91    /// );
92    /// ```
93    pub fn from_elem(bit_count: usize, len: usize, bytes: &[u8]) -> Self {
94        let mut ret = BitArrayVec {
95            blocks: vec![0; Self::get_block_count(bit_count, len)],
96            bit_count,
97            occupied_len: 0,
98            len,
99        };
100        for index in 0..len {
101            ret.set(index, bytes);
102        }
103        ret
104    }
105
106    /// Constructs a new, empty `BitArrayVec` with a certain capacity.
107    ///
108    /// # Examples
109    ///
110    /// ```
111    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
112    ///
113    /// let bav = BitArrayVec::with_capacity(5, 4);
114    /// ```
115    pub fn with_capacity(bit_count: usize, len: usize) -> Self {
116        BitArrayVec {
117            blocks: Vec::with_capacity(Self::get_block_count(bit_count, len)),
118            bit_count,
119            occupied_len: 0,
120            len: 0,
121        }
122    }
123
124    /// Sets the value at index `index` to `bytes`.
125    ///
126    /// # Panics
127    ///
128    /// Panics if attempt to set an index out-of-bounds.
129    ///
130    /// # Examples
131    ///
132    /// ```
133    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
134    ///
135    /// let mut bav = BitArrayVec::new(5, 4);
136    /// bav.set(1, &[1]);
137    ///
138    /// assert_eq!(bav.get(0), vec![0]);
139    /// assert_eq!(bav.get(1), vec![1]);
140    /// ```
141    pub fn set(&mut self, index: usize, bytes: &[u8]) {
142        assert!(index < self.len);
143        let prev_is_zero = self.get(index).iter().all(|byte| *byte == 0);
144        let mut bits_left = self.bit_count;
145        let mut bits_offset = index * self.bit_count;
146        let mut byte_offset = 0;
147
148        while bits_left > 0 {
149            let curr_bits = cmp::min(bits_left, 8 - bits_offset % 8);
150            bits_left -= curr_bits;
151
152            let mut new_bits = {
153                if byte_offset % 8 == 0 {
154                    bytes[byte_offset / 8]
155                } else if (8 - byte_offset % 8) >= bits_left + curr_bits {
156                    (bytes[byte_offset / 8]) >> (byte_offset % 8)
157                } else {
158                    let curr = bytes[byte_offset / 8] >> (byte_offset % 8);
159                    let next = bytes[byte_offset / 8 + 1] << (8 - byte_offset % 8);
160                    curr | next
161                }
162            };
163
164            new_bits = new_bits << (8 - curr_bits) >> (8 - curr_bits);
165
166            self.blocks[bits_offset / 8] &= !(!0 >> (8 - curr_bits) << (bits_offset % 8));
167            self.blocks[bits_offset / 8] |= new_bits << (bits_offset % 8);
168
169            byte_offset += curr_bits;
170            bits_offset += curr_bits;
171        }
172        let curr_is_zero = self.get(index).iter().all(|byte| *byte == 0);
173        if prev_is_zero != curr_is_zero {
174            if curr_is_zero {
175                self.occupied_len -= 1;
176            } else {
177                self.occupied_len += 1;
178            }
179        }
180    }
181
182    /// Returns the value at index `index`.
183    ///
184    /// # Panics
185    ///
186    /// Panics if attempt to get an index out-of-bounds.
187    ///
188    /// # Examples
189    ///
190    /// ```
191    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
192    ///
193    /// let mut bav = BitArrayVec::new(5, 4);
194    /// bav.set(1, &[1]);
195    ///
196    /// assert_eq!(bav.get(0), vec![0]);
197    /// assert_eq!(bav.get(1), vec![1]);
198    /// ```
199    pub fn get(&self, index: usize) -> Vec<u8> {
200        assert!(index < self.len);
201        let mut ret = vec![0; (self.bit_count + 7) / 8];
202        let mut bits_left = self.bit_count;
203        let mut bits_offset = index * self.bit_count;
204        let mut ret_offset = 0;
205
206        while bits_left > 0 {
207            let curr_bits = cmp::min(bits_left, 8);
208            bits_left -= curr_bits;
209
210            let old_bits = {
211                if bits_offset % 8 == 0 {
212                    self.blocks[bits_offset / 8]
213                } else if 8 - bits_offset % 8 >= curr_bits {
214                    self.blocks[bits_offset / 8] >> (bits_offset % 8)
215                } else {
216                    let curr = self.blocks[bits_offset / 8] >> (bits_offset % 8);
217                    let next = self.blocks[bits_offset / 8 + 1] << (8 - bits_offset % 8);
218                    curr | next
219                }
220            };
221
222            ret[ret_offset / 8] = old_bits & (!0u8 >> (8 - curr_bits));
223
224            bits_offset += curr_bits;
225            ret_offset += curr_bits;
226        }
227        ret
228    }
229
230    /// Truncates a `BitArrayVec`, dropping excess elements.
231    ///
232    /// # Examples
233    ///
234    /// ```
235    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
236    ///
237    /// let mut bav = BitArrayVec::new(5, 4);
238    ///
239    /// bav.truncate(2);
240    /// assert_eq!(bav.iter().collect::<Vec<Vec<u8>>>(), vec![vec![0], vec![0]]);
241    /// ```
242    pub fn truncate(&mut self, len: usize) {
243        while len < self.len {
244            self.pop();
245        }
246    }
247
248    /// Reserves capacity for at least `additional` more bit arrays to be inserted in the given
249    /// `BitArrayVec`.
250    ///
251    /// # Examples
252    ///
253    /// ```
254    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
255    ///
256    /// let mut bav = BitArrayVec::new(5, 4);
257    ///
258    /// bav.reserve(10);
259    /// assert!(bav.capacity() >= 14);
260    /// ```
261    pub fn reserve(&mut self, additional: usize) {
262        let desired_cap = self.len + additional;
263        if desired_cap <= Self::get_elem_count(self.bit_count, self.blocks.capacity()) {
264            return;
265        }
266
267        let target_cap = Self::get_block_count(self.bit_count, desired_cap);
268        let additional_blocks = target_cap - self.blocks.len();
269        self.blocks.reserve(additional_blocks);
270    }
271
272    /// Reserves capacity for at least `additional` more bit arrays to be inserted in the given
273    /// `BitArrayVec`. Allocates exactly enough space in the underlying `Vec<u8>`.
274    ///
275    /// # Examples
276    ///
277    /// ```
278    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
279    ///
280    /// let mut bav = BitArrayVec::new(5, 4);
281    ///
282    /// bav.reserve_exact(10);
283    /// assert_eq!(bav.capacity(), 14);
284    /// ```
285    pub fn reserve_exact(&mut self, additional: usize) {
286        let desired_cap = self.len + additional;
287        if desired_cap <= Self::get_elem_count(self.bit_count, self.blocks.capacity()) {
288            return;
289        }
290
291        let target_cap = Self::get_block_count(self.bit_count, desired_cap);
292        let additional_blocks = target_cap - self.blocks.len();
293        self.blocks.reserve_exact(additional_blocks);
294    }
295
296    /// Returns and removes the last element of the `BitVecArray`.
297    ///
298    /// # Panics
299    ///
300    /// Panics if the `BitVecArray` is empty.
301    ///
302    /// # Examples
303    ///
304    /// ```
305    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
306    ///
307    /// let mut bav = BitArrayVec::new(5, 2);
308    ///
309    /// bav.set(1, &[1]);
310    ///
311    /// assert_eq!(bav.pop(), &[1]);
312    /// assert_eq!(bav.pop(), &[0]);
313    /// ```
314    pub fn pop(&mut self) -> Vec<u8> {
315        assert!(!self.is_empty());
316        let ret = self.get(self.len - 1);
317        let len = self.len;
318        let new_blocks_len = Self::get_block_count(self.bit_count, len - 1);
319        self.blocks.truncate(new_blocks_len);
320        self.len -= 1;
321        if !ret.iter().all(|byte| *byte == 0) {
322            self.occupied_len -= 1;
323        }
324        ret
325    }
326
327    /// Pushes an element into the `BitArrayVec`.
328    ///
329    /// # Examples
330    ///
331    /// ```
332    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
333    ///
334    /// let mut bav = BitArrayVec::new(5, 1);
335    ///
336    /// bav.push(&[1]);
337    ///
338    /// assert_eq!(bav.pop(), &[1]);
339    /// assert_eq!(bav.pop(), &[0]);
340    /// ```
341    pub fn push(&mut self, bytes: &[u8]) {
342        let new_block_len = Self::get_block_count(self.bit_count, self.len + 1);
343        let block_len = self.blocks.len();
344        self.blocks
345            .extend(iter::repeat(0).take(new_block_len - block_len));
346        let len = self.len;
347        let occupied_len = self.occupied_len;
348        self.len += 1;
349        self.set(len, bytes);
350        self.occupied_len = occupied_len;
351        if !bytes.iter().all(|byte| *byte == 0) {
352            self.occupied_len = occupied_len + 1;
353        }
354    }
355
356    /// Clears all elements in the `BitVecArray`, setting all bit arrays to zero.
357    ///
358    /// # Examples
359    ///
360    /// ```
361    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
362    ///
363    /// let mut bav = BitArrayVec::from_elem(5, 4, &[1]);
364    ///
365    /// bav.clear();
366    ///
367    /// assert_eq!(
368    ///     bav.iter().collect::<Vec<Vec<u8>>>(),
369    ///     vec![vec![0], vec![0], vec![0], vec![0]],
370    /// );
371    /// ```
372    pub fn clear(&mut self) {
373        self.occupied_len = 0;
374        for byte in &mut self.blocks {
375            *byte = 0;
376        }
377    }
378
379    /// Returns an iterator over the elements of the vector in order.
380    ///
381    /// # Examples
382    ///
383    /// ```
384    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
385    ///
386    /// let mut bav = BitArrayVec::new(5, 1);
387    ///
388    /// bav.push(&[1]);
389    ///
390    /// assert_eq!(bav.iter().collect::<Vec<Vec<u8>>>(), vec![vec![0], vec![1]]);
391    /// ```
392    pub fn iter(&self) -> BitArrayVecIter<'_> {
393        BitArrayVecIter {
394            bit_array_vec: self,
395            range: 0..self.len,
396        }
397    }
398
399    /// Returns the capacity of the `BitArrayVec`.
400    ///
401    /// # Examples
402    ///
403    /// ```
404    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
405    ///
406    /// let mut bav = BitArrayVec::new(5, 0);
407    ///
408    /// bav.reserve_exact(10);
409    /// assert_eq!(bav.capacity(), 11);
410    /// ```
411    pub fn capacity(&self) -> usize {
412        Self::get_elem_count(self.bit_count, self.blocks.capacity())
413    }
414
415    /// Returns the number of elements in the `BitArrayVec`.
416    ///
417    /// # Examples
418    ///
419    /// ```
420    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
421    ///
422    /// let mut bav = BitArrayVec::new(5, 1);
423    /// bav.push(&[1]);
424    ///
425    /// assert_eq!(bav.len(), 2);
426    /// ```
427    pub fn len(&self) -> usize {
428        self.len
429    }
430
431    /// Returns `true` if the `BitArrayVec` is empty.
432    ///
433    /// # Examples
434    ///
435    /// ```
436    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
437    ///
438    /// let mut bav = BitArrayVec::new(5, 0);
439    /// assert!(bav.is_empty());
440    ///
441    /// bav.push(&[1]);
442    /// assert!(!bav.is_empty());
443    /// ```
444    pub fn is_empty(&self) -> bool {
445        self.len == 0
446    }
447
448    /// Returns the number of non-zero elements in the `BitArrayVec`;
449    ///
450    /// # Examples
451    ///
452    /// ```
453    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
454    ///
455    /// let mut bav = BitArrayVec::new(5, 1);
456    /// bav.push(&[1]);
457    ///
458    /// assert_eq!(bav.occupied_len(), 1);
459    /// ```
460    pub fn occupied_len(&self) -> usize {
461        self.occupied_len
462    }
463
464    /// Returns the number of bits in each bit array stored by the `BitArrayVec`.
465    ///
466    /// # Examples
467    ///
468    /// ```
469    /// use probabilistic_collections::bit_array_vec::BitArrayVec;
470    ///
471    /// let bav = BitArrayVec::new(5, 0);
472    ///
473    /// assert_eq!(bav.bit_count(), 5);
474    /// ```
475    pub fn bit_count(&self) -> usize {
476        self.bit_count
477    }
478}
479
480/// An owning iterator for `BitArrayVec`.
481///
482/// This iterator yields elements in order.
483pub struct BitArrayVecIter<'a> {
484    bit_array_vec: &'a BitArrayVec,
485    range: Range<usize>,
486}
487
488impl<'a> Iterator for BitArrayVecIter<'a> {
489    type Item = Vec<u8>;
490
491    fn next(&mut self) -> Option<Vec<u8>> {
492        self.range.next().map(|index| self.bit_array_vec.get(index))
493    }
494}
495
496impl<'a> IntoIterator for &'a BitArrayVec {
497    type IntoIter = BitArrayVecIter<'a>;
498    type Item = Vec<u8>;
499
500    fn into_iter(self) -> Self::IntoIter {
501        self.iter()
502    }
503}
504
505/// An iterator for `BitArrayVec`.
506///
507/// This iterator yields bits in order.
508pub struct BitArrayVecIntoIter {
509    bit_array_vec: BitArrayVec,
510    range: Range<usize>,
511}
512
513impl Iterator for BitArrayVecIntoIter {
514    type Item = Vec<u8>;
515
516    fn next(&mut self) -> Option<Vec<u8>> {
517        self.range.next().map(|index| self.bit_array_vec.get(index))
518    }
519}
520
521impl IntoIterator for BitArrayVec {
522    type IntoIter = BitArrayVecIntoIter;
523    type Item = Vec<u8>;
524
525    fn into_iter(self) -> Self::IntoIter {
526        let len = self.len;
527        Self::IntoIter {
528            bit_array_vec: self,
529            range: 0..len,
530        }
531    }
532}
533
534#[cfg(test)]
535mod tests {
536    use super::BitArrayVec;
537
538    #[test]
539    fn test_bit_count_5() {
540        let mut bav = BitArrayVec::new(5, 8);
541        assert_eq!(bav.len(), 8);
542
543        bav.set(0, &[0]);
544        assert_eq!(bav.occupied_len(), 0);
545
546        for i in 0..8 {
547            bav.set(i, &[((i + 1) as u8)]);
548            assert_eq!(bav.occupied_len(), i + 1);
549        }
550
551        bav.set(0, &[1]);
552        assert_eq!(bav.occupied_len(), 8);
553
554        for i in 0..8 {
555            assert_eq!(bav.get(i), vec![((i + 1) as u8)]);
556            bav.set(i, &[0]);
557            assert_eq!(bav.occupied_len(), 8 - i - 1);
558        }
559
560        for i in 0..7 {
561            bav.set(i, &[((i + 1) as u8)]);
562        }
563
564        bav.truncate(4);
565        assert_eq!(bav.occupied_len(), 4);
566        assert_eq!(bav.len(), 4);
567
568        assert_eq!(
569            bav.iter().collect::<Vec<Vec<u8>>>(),
570            vec![vec![1], vec![2], vec![3], vec![4]],
571        );
572
573        bav.push(&[5]);
574        assert_eq!(bav.occupied_len(), 5);
575        assert_eq!(bav.len(), 5);
576
577        bav.push(&[0]);
578        assert_eq!(bav.occupied_len(), 5);
579        assert_eq!(bav.len(), 6);
580
581        assert_eq!(bav.pop(), vec![0]);
582        assert_eq!(bav.occupied_len(), 5);
583        assert_eq!(bav.len(), 5);
584
585        assert_eq!(bav.pop(), vec![5]);
586        assert_eq!(bav.occupied_len(), 4);
587        assert_eq!(bav.len(), 4);
588
589        bav.truncate(0);
590        assert!(bav.is_empty());
591        assert_eq!(bav.occupied_len(), 0);
592        assert_eq!(bav.len(), 0);
593
594        let mut bav = BitArrayVec::new(21, 8);
595        bav.reserve(10);
596        assert!(bav.capacity() >= 18);
597
598        let mut bav = BitArrayVec::new(21, 8);
599        bav.reserve_exact(10);
600        assert_eq!(bav.capacity(), 18);
601    }
602
603    #[test]
604    fn test_bit_count_13() {
605        let mut bav = BitArrayVec::new(13, 8);
606        assert_eq!(bav.len(), 8);
607
608        bav.set(0, &[0, 0]);
609        assert_eq!(bav.occupied_len(), 0);
610
611        for i in 0..8 {
612            bav.set(i, &[((i + 1) as u8), !0]);
613            assert_eq!(bav.occupied_len(), i + 1);
614        }
615
616        bav.set(0, &[1, !0]);
617        assert_eq!(bav.occupied_len(), 8);
618
619        for i in 0..8 {
620            assert_eq!(bav.get(i), vec![((i + 1) as u8), 0b11111]);
621            bav.set(i, &[0, 0]);
622            assert_eq!(bav.occupied_len(), 8 - i - 1);
623        }
624
625        for i in 0..7 {
626            bav.set(i, &[((i + 1) as u8), !0]);
627        }
628
629        bav.truncate(4);
630        assert_eq!(bav.occupied_len(), 4);
631        assert_eq!(bav.len(), 4);
632
633        assert_eq!(
634            bav.iter().collect::<Vec<Vec<u8>>>(),
635            vec![
636                vec![1, 0b11111],
637                vec![2, 0b11111],
638                vec![3, 0b11111],
639                vec![4, 0b11111],
640            ],
641        );
642
643        bav.push(&[5, !0]);
644        assert_eq!(bav.occupied_len(), 5);
645        assert_eq!(bav.len(), 5);
646
647        bav.push(&[0, 0]);
648        assert_eq!(bav.occupied_len(), 5);
649        assert_eq!(bav.len(), 6);
650
651        assert_eq!(bav.pop(), vec![0, 0]);
652        assert_eq!(bav.occupied_len(), 5);
653        assert_eq!(bav.len(), 5);
654
655        assert_eq!(bav.pop(), vec![5, 0b11111]);
656        assert_eq!(bav.occupied_len(), 4);
657        assert_eq!(bav.len(), 4);
658
659        bav.truncate(0);
660        assert!(bav.is_empty());
661        assert_eq!(bav.occupied_len(), 0);
662        assert_eq!(bav.len(), 0);
663
664        let mut bav = BitArrayVec::new(21, 8);
665        bav.reserve(10);
666        assert!(bav.capacity() >= 18);
667
668        let mut bav = BitArrayVec::new(21, 8);
669        bav.reserve_exact(10);
670        assert_eq!(bav.capacity(), 18);
671    }
672
673    #[test]
674    fn test_bit_count_21() {
675        let mut bav = BitArrayVec::new(21, 8);
676        assert_eq!(bav.len(), 8);
677
678        bav.set(0, &[0, 0, 0]);
679        assert_eq!(bav.occupied_len(), 0);
680
681        for i in 0..8 {
682            bav.set(i, &[((i + 1) as u8), !0, !0]);
683            assert_eq!(bav.occupied_len(), i + 1);
684        }
685
686        bav.set(0, &[1, !0, !0]);
687        assert_eq!(bav.occupied_len(), 8);
688
689        for i in 0..8 {
690            assert_eq!(bav.get(i), vec![((i + 1) as u8), !0, 0b11111]);
691            bav.set(i, &[0, 0, 0]);
692            assert_eq!(bav.occupied_len(), 8 - i - 1);
693        }
694
695        for i in 0..7 {
696            bav.set(i, &[((i + 1) as u8), !0, !0]);
697        }
698
699        bav.truncate(4);
700        assert_eq!(bav.occupied_len(), 4);
701        assert_eq!(bav.len(), 4);
702
703        assert_eq!(
704            bav.iter().collect::<Vec<Vec<u8>>>(),
705            vec![
706                vec![1, !0, 0b11111],
707                vec![2, !0, 0b11111],
708                vec![3, !0, 0b11111],
709                vec![4, !0, 0b11111],
710            ],
711        );
712
713        bav.push(&[5, !0, !0]);
714        assert_eq!(bav.occupied_len(), 5);
715        assert_eq!(bav.len(), 5);
716
717        bav.push(&[0, 0, 0]);
718        assert_eq!(bav.occupied_len(), 5);
719        assert_eq!(bav.len(), 6);
720
721        assert_eq!(bav.pop(), vec![0, 0, 0]);
722        assert_eq!(bav.occupied_len(), 5);
723        assert_eq!(bav.len(), 5);
724
725        assert_eq!(bav.pop(), vec![5, !0, 0b11111]);
726        assert_eq!(bav.occupied_len(), 4);
727        assert_eq!(bav.len(), 4);
728
729        bav.truncate(0);
730        assert!(bav.is_empty());
731        assert_eq!(bav.occupied_len(), 0);
732        assert_eq!(bav.len(), 0);
733
734        let mut bav = BitArrayVec::new(21, 8);
735        bav.reserve(10);
736        assert!(bav.capacity() >= 18);
737
738        let mut bav = BitArrayVec::new(21, 8);
739        bav.reserve_exact(10);
740        assert_eq!(bav.capacity(), 18);
741    }
742
743    #[test]
744    fn test_bit_count() {
745        let bav = BitArrayVec::new(8, 10);
746        assert_eq!(bav.bit_count(), 8);
747    }
748
749    #[test]
750    fn test_from_elem() {
751        let bav = BitArrayVec::from_elem(5, 4, &[1]);
752        assert_eq!(
753            bav.iter().collect::<Vec<Vec<u8>>>(),
754            vec![vec![1], vec![1], vec![1], vec![1]],
755        );
756    }
757
758    #[test]
759    fn test_with_capacity() {
760        let bav = BitArrayVec::with_capacity(5, 4);
761
762        assert_eq!(bav.len(), 0);
763        assert_eq!(bav.capacity(), 4);
764    }
765
766    #[test]
767    fn test_into_iter() {
768        let mut bav = BitArrayVec::new(5, 0);
769        bav.push(&[0]);
770        bav.push(&[1]);
771        bav.push(&[2]);
772        bav.push(&[3]);
773
774        assert_eq!(
775            bav.into_iter().collect::<Vec<Vec<u8>>>(),
776            vec![vec![0], vec![1], vec![2], vec![3]],
777        );
778    }
779}
probabilistic_collections/bit_array_vec.rs

probabilistic_collections/
bit_array_vec.rs
