bitvek/
lib.rs

1//! Say, we have a bit vector —
2//!
3//! it's nothing better than a `Vec<bool>`, but …
4//!
5//! what if we implement it,
6//!
7//! and save some poor bits of memory?
8//!
9//! # Quick Start
10//!
11//! ```
12//! use bitvek::bitvec;
13//!
14//! let vec = bitvec![
15//!     true, true, true, true, false, false, false, false,
16//!     false, false, false, false, true, true, true, true,
17//! ];
18//! ```
19//!
20//! Find it cumbersome? Try this:
21//!
22//! ```
23//! # use bitvek::bitvec;
24//! #
25//! // The total number of bits must be a multiple of 8.
26//! let vec = bitvec![0b11110000, 0b00001111];
27//! ```
28
29#![no_std]
30
31extern crate alloc;
32
33pub use self::iter::{IntoIter, Iter};
34pub use self::primitive::{Bit, Byte};
35
36use self::primitive::Word;
37use alloc::vec::Vec;
38use core::fmt;
39use core::hash::{Hash, Hasher};
40use core::ops::Index;
41
42mod bitwise;
43mod convert;
44mod iter;
45mod macros;
46mod primitive;
47
48#[cfg(feature = "serde")]
49mod serde;
50
51/// A bit vector.
52#[derive(Default)]
53pub struct BitVec {
54    // Invariant: `self.buf_used() <= self.buf.len()`
55    len: usize,
56    buf: Vec<Word>,
57}
58
59impl BitVec {
60    /// Returns the total number of bits the vector can hold without reallocating.
61    ///
62    /// # Examples
63    ///
64    /// ```
65    /// use bitvek::BitVec;
66    ///
67    /// let vec = BitVec::with_capacity(10);
68    /// assert!(vec.capacity() >= 10);
69    /// ```
70    #[inline]
71    pub const fn capacity(&self) -> usize {
72        self.buf.capacity().saturating_mul(Word::BITS)
73    }
74
75    /// Returns the number of bits in the vector.
76    ///
77    /// # Examples
78    ///
79    /// ```
80    /// use bitvek::bitvec;
81    ///
82    /// let vec = bitvec![true, true, false, false];
83    /// assert_eq!(vec.len(), 4);
84    #[inline]
85    pub const fn len(&self) -> usize {
86        self.len
87    }
88
89    /// Returns `true` if the vector contains no bits.
90    ///
91    /// # Examples
92    ///
93    /// ```
94    /// use bitvek::bitvec;
95    ///
96    /// let vec = bitvec![];
97    /// assert!(vec.is_empty());
98    ///
99    /// let vec = bitvec![true, true, false, false];
100    /// assert!(!vec.is_empty());
101    /// ```
102    #[inline]
103    pub const fn is_empty(&self) -> bool {
104        self.len == 0
105    }
106
107    /// Returns the number of words used to store the bits in the vector.
108    ///
109    /// Note that it is always less than or equal to the buffer length, which
110    /// represents the number of words initialized.
111    const fn buf_used(&self) -> usize {
112        self.len.div_ceil(Word::BITS)
113    }
114}
115
116impl BitVec {
117    /// Creates a new, empty [`BitVec`].
118    ///
119    /// # Examples
120    ///
121    /// ```
122    /// use bitvek::BitVec;
123    ///
124    /// let vec = BitVec::new();
125    /// assert_eq!(vec.len(), 0);
126    /// assert_eq!(vec.capacity(), 0);
127    /// ```
128    #[inline]
129    pub const fn new() -> Self {
130        let len = 0;
131        let buf = Vec::new();
132        Self { len, buf }
133    }
134
135    /// Creates a new, empty [`BitVec`] with the specified capacity.
136    ///
137    /// The vector will be able to hold at least `capacity` bits without
138    /// reallocating. This method is allowed to allocate for more bits than
139    /// `capacity`. If `capacity` is zero, the vector will not allocate.
140    ///
141    /// # Examples
142    ///
143    /// ```
144    /// use bitvek::BitVec;
145    ///
146    /// let vec = BitVec::with_capacity(10);
147    /// assert_eq!(vec.len(), 0);
148    /// assert!(vec.capacity() >= 10);
149    /// ```
150    #[inline]
151    pub fn with_capacity(capacity: usize) -> Self {
152        let len = 0;
153        let buf_capacity = capacity.div_ceil(Word::BITS);
154        let buf = Vec::with_capacity(buf_capacity);
155        Self { len, buf }
156    }
157}
158
159impl BitVec {
160    /// Reserves capacity for at least `additional` more bits to be inserted in the
161    /// given [`BitVec`]. The collection may reserve more space to speculatively
162    /// avoid frequent reallocations. After calling `reserve`, capacity will be
163    /// greater than or equal to `self.len() + additional`. Does nothing if capacity
164    /// is already sufficient.
165    ///
166    /// # Examples
167    ///
168    /// ```
169    /// use bitvek::bitvec;
170    ///
171    /// let mut vec = bitvec![true, true, false, false];
172    /// vec.reserve(6);
173    /// assert!(vec.capacity() >= 10);
174    /// ```
175    pub fn reserve(&mut self, additional: usize) -> &mut Self {
176        let capacity = self.len.checked_add(additional).expect("capacity overflow");
177        let buf_capacity = capacity.div_ceil(Word::BITS);
178        if let Some(buf_additional) = buf_capacity.checked_sub(self.buf.len()) {
179            self.buf.reserve(buf_additional);
180        };
181        self
182    }
183
184    /// Shrinks the capacity of the vector as much as possible.
185    ///
186    /// # Examples
187    ///
188    /// ```
189    /// use bitvek::bitvec;
190    ///
191    /// let mut vec = bitvec![true, true, false, false];
192    /// let unchanged = vec.clone();
193    ///
194    /// vec.reserve(6);
195    /// assert!(vec.capacity() >= 10);
196    ///
197    /// vec.shrink_to_fit();
198    /// assert!(vec.capacity() >= 4);
199    /// assert_eq!(vec, unchanged);
200    /// ```
201    pub fn shrink_to_fit(&mut self) -> &mut Self {
202        let buf_new_len = self.buf_used();
203        unsafe {
204            self.buf.set_len(buf_new_len);
205        }
206        self.buf.shrink_to_fit();
207        self
208    }
209
210    /// Shrinks the capacity of the vector with a lower bound.
211    ///
212    /// The capacity will remain at least as large as both the length and the
213    /// supplied value.
214    ///
215    /// If the current capacity is less than the lower limit, this is a no-op.
216    ///
217    /// # Examples
218    ///
219    /// ```
220    /// use bitvek::bitvec;
221    ///
222    /// let mut vec = bitvec![true, true, false, false];
223    /// let unchanged = vec.clone();
224    ///
225    /// vec.reserve(6);
226    /// assert!(vec.capacity() >= 10);
227    ///
228    /// vec.shrink_to(8);
229    /// assert!(vec.capacity() >= 8);
230    /// assert_eq!(vec, unchanged);
231    ///
232    /// vec.shrink_to(0);
233    /// assert!(vec.capacity() >= 4);
234    /// assert_eq!(vec, unchanged);
235    /// ```
236    pub fn shrink_to(&mut self, min_capacity: usize) -> &mut Self {
237        let buf_min_capacity = min_capacity.div_ceil(Word::BITS);
238        if buf_min_capacity < self.buf.len() {
239            let buf_new_len = self.buf_used().max(buf_min_capacity);
240            unsafe {
241                self.buf.set_len(buf_new_len);
242            }
243            self.buf.shrink_to_fit();
244        } else if buf_min_capacity < self.buf.capacity() {
245            self.buf.shrink_to(buf_min_capacity);
246        }
247        self
248    }
249
250    /// Returns the bit at the specified index, if in bounds.
251    ///
252    /// # Examples
253    ///
254    /// ```
255    /// use bitvek::bitvec;
256    ///
257    /// let vec = bitvec![true, true, false, false];
258    /// assert_eq!(vec.get(3), Some(false));
259    /// assert_eq!(vec.get(4), None);
260    /// ```
261    #[inline]
262    pub fn get(&self, index: usize) -> Option<Bit> {
263        if index >= self.len {
264            None
265        } else {
266            Some(unsafe { self.get_unchecked(index) })
267        }
268    }
269
270    /// Returns the bit at the specified index, without performing any bounds
271    /// checking.
272    ///
273    /// # Safety
274    ///
275    /// Calling this method with an out-of-bounds index is *[undefined behavior]*.
276    ///
277    /// # Examples
278    ///
279    /// ```
280    /// use bitvek::bitvec;
281    ///
282    /// let vec = bitvec![true, true, false, false];
283    /// assert_eq!(unsafe { vec.get_unchecked(3) }, false);
284    /// ```
285    ///
286    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
287    #[inline]
288    pub unsafe fn get_unchecked(&self, index: usize) -> Bit {
289        let loc = Loc::new(index);
290        let word = unsafe { self.buf.get_unchecked(loc.period) };
291        word.get(loc.offset)
292    }
293
294    /// Sets the bit at the specified index to the specified value, if in bounds.
295    ///
296    /// # Examples
297    ///
298    /// ```
299    /// use bitvek::bitvec;
300    ///
301    /// let mut vec = bitvec![true, true, false, false];
302    /// assert!(vec.set(2, true).is_some());
303    /// assert!(vec.set(3, true).is_some());
304    /// assert!(vec.set(4, true).is_none());
305    /// assert_eq!(vec, bitvec![true; 4]);
306    /// ```
307    #[inline]
308    #[must_use]
309    pub fn set(&mut self, index: usize, value: Bit) -> Option<&mut Self> {
310        if index >= self.len {
311            None
312        } else {
313            Some(unsafe { self.set_unchecked(index, value) })
314        }
315    }
316
317    /// Sets the bit at the specified index to the specified value, without
318    /// performing any bounds checking.
319    ///
320    /// # Safety
321    ///
322    /// Calling this method with an out-of-bounds index is *[undefined behavior]*.
323    ///
324    /// # Examples
325    ///
326    /// ```
327    /// use bitvek::bitvec;
328    ///
329    /// let mut vec = bitvec![true, true, false, false];
330    /// unsafe {
331    ///     vec.set_unchecked(2, true);
332    ///     vec.set_unchecked(3, true);
333    /// }
334    /// assert_eq!(vec, bitvec![true; 4]);
335    /// ```
336    ///
337    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
338    #[inline]
339    pub unsafe fn set_unchecked(&mut self, index: usize, value: Bit) -> &mut Self {
340        let loc = Loc::new(index);
341        let word = unsafe { self.buf.get_unchecked_mut(loc.period) };
342        word.set(loc.offset, value);
343        self
344    }
345
346    /// Appends a bit to the back of the vector.
347    ///
348    /// # Panics
349    ///
350    /// Panics if the required capacity exceeds `usize::MAX` bits.
351    ///
352    /// # Examples
353    ///
354    /// ```
355    /// use bitvek::bitvec;
356    ///
357    /// let mut vec = bitvec![true, true, false, false];
358    /// vec.push(true);
359    /// assert_eq!(vec, bitvec![true, true, false, false, true]);
360    /// ```
361    pub fn push(&mut self, value: Bit) -> &mut Self {
362        if self.len == usize::MAX {
363            panic!("capacity overflow")
364        }
365        let loc = Loc::new(self.len);
366        if loc.period < self.buf.len() {
367            let word = unsafe { self.buf.get_unchecked_mut(loc.period) };
368            word.set(loc.offset, value);
369        } else if value {
370            self.buf.push(Word::MSB_SET);
371        } else {
372            self.buf.push(Word::MSB_CLEAR);
373        }
374        self.len += 1;
375        self
376    }
377
378    /// Removes the last bit from the vector and returns it, or `None` if the vector
379    /// is empty.
380    ///
381    /// # Examples
382    ///
383    /// ```
384    /// use bitvek::bitvec;
385    ///
386    /// let mut vec = bitvec![true, true, false, false];
387    /// assert_eq!(vec.pop(), Some(false));
388    /// assert_eq!(vec.pop(), Some(false));
389    /// assert_eq!(vec.pop(), Some(true));
390    /// assert_eq!(vec.pop(), Some(true));
391    /// assert_eq!(vec.pop(), None);
392    /// ```
393    pub fn pop(&mut self) -> Option<Bit> {
394        if self.is_empty() {
395            return None;
396        }
397        self.len -= 1;
398        let loc = Loc::new(self.len);
399        let word = unsafe { self.buf.get_unchecked(loc.period) };
400        let value = word.get(loc.offset);
401        Some(value)
402    }
403}
404
405impl Index<usize> for BitVec {
406    type Output = Bit;
407
408    #[inline]
409    fn index(&self, index: usize) -> &Self::Output {
410        match self.get(index) {
411            None => panic!("index out of bounds"),
412            Some(false) => &false,
413            Some(true) => &true,
414        }
415    }
416}
417
418impl Clone for BitVec {
419    fn clone(&self) -> Self {
420        let len = self.len;
421        let buf_len = self.buf_used();
422        let buf = unsafe { self.buf.get_unchecked(0..buf_len).to_vec() };
423        Self { len, buf }
424    }
425}
426
427impl fmt::Debug for BitVec {
428    #[inline]
429    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
430        f.debug_list().entries(self.iter()).finish()
431    }
432}
433
434impl Extend<Bit> for BitVec {
435    fn extend<I>(&mut self, iter: I)
436    where
437        I: IntoIterator<Item = Bit>,
438    {
439        let iter = iter.into_iter();
440        let additional = iter.size_hint().0;
441        self.reserve(additional);
442        for value in iter {
443            self.push(value);
444        }
445    }
446}
447
448impl Hash for BitVec {
449    fn hash<H>(&self, state: &mut H)
450    where
451        H: Hasher,
452    {
453        if self.is_empty() {
454            return;
455        }
456
457        self.len.hash(state);
458
459        let last = self.len - 1;
460        let loc = Loc::new(last);
461
462        let head = unsafe { self.buf.get_unchecked(..loc.period) };
463        head.hash(state);
464
465        let tail = unsafe { self.buf.get_unchecked(loc.period) };
466        tail.align_last_to_lsb(loc.offset).hash(state);
467    }
468}
469
470impl PartialEq for BitVec {
471    fn eq(&self, other: &Self) -> bool {
472        if self.len != other.len {
473            return false;
474        }
475
476        if self.is_empty() {
477            return true;
478        }
479
480        let last = self.len - 1;
481        let loc = Loc::new(last);
482
483        let lhs_head = unsafe { self.buf.get_unchecked(..loc.period) };
484        let rhs_head = unsafe { other.buf.get_unchecked(..loc.period) };
485        if lhs_head != rhs_head {
486            return false;
487        }
488
489        let lhs_tail = unsafe { self.buf.get_unchecked(loc.period) };
490        let rhs_tail = unsafe { other.buf.get_unchecked(loc.period) };
491        (*lhs_tail ^ *rhs_tail).align_last_to_lsb(loc.offset) == Word::CLEAR
492    }
493}
494
495impl Eq for BitVec {}
496
497#[derive(Debug)]
498struct Loc {
499    period: usize,
500    offset: usize,
501}
502
503impl Loc {
504    const fn new(index: usize) -> Self {
505        let period = index / Word::BITS;
506        let offset = index % Word::BITS;
507        Self { period, offset }
508    }
509}
510
511#[cfg(test)]
512impl BitVec {
513    fn push_unused_word(&mut self) {
514        self.buf.push(Word::CLEAR);
515    }
516}
517
518#[cfg(test)]
519mod tests {
520    extern crate std;
521
522    use super::*;
523    use core::iter::repeat_n;
524    use std::hash::DefaultHasher;
525
526    #[test]
527    fn test_capacity() {
528        let vec = BitVec::with_capacity(0);
529        assert_eq!(vec.capacity(), 0);
530
531        let vec = BitVec::with_capacity(10);
532        assert!(vec.capacity() >= Word::BITS);
533
534        let vec = BitVec::with_capacity(Word::BITS + 1);
535        assert!(vec.capacity() >= Word::BITS * 2);
536    }
537
538    #[test]
539    fn test_len() {
540        let vec = bitvec![];
541        assert_eq!(vec.len(), 0);
542
543        let vec = bitvec![true, true, false, false];
544        assert_eq!(vec.len(), 4);
545    }
546
547    #[test]
548    fn test_is_empty() {
549        let vec = bitvec![];
550        assert!(vec.is_empty());
551
552        let vec = bitvec![true, true, false, false];
553        assert!(!vec.is_empty());
554    }
555
556    #[test]
557    fn test_new() {
558        let vec = BitVec::new();
559        assert_eq!(vec.len, 0);
560        assert_eq!(vec.buf, Vec::new());
561    }
562
563    #[test]
564    fn test_with_capacity() {
565        let vec = BitVec::with_capacity(0);
566        assert_eq!(vec.len, 0);
567        assert_eq!(vec.capacity(), 0);
568        assert_eq!(vec.buf.capacity(), 0);
569
570        let vec = BitVec::with_capacity(10);
571        assert_eq!(vec.len, 0);
572        assert!(vec.capacity() >= Word::BITS);
573        assert!(vec.buf.capacity() >= 1);
574
575        let vec = BitVec::with_capacity(Word::BITS + 1);
576        assert_eq!(vec.len, 0);
577        assert!(vec.capacity() >= Word::BITS * 2);
578        assert!(vec.buf.capacity() >= 2);
579    }
580
581    #[test]
582    fn test_reserve() {
583        let mut vec = bitvec![true, true, false, false];
584
585        vec.reserve(6);
586        assert!(vec.capacity() >= Word::BITS);
587
588        vec.reserve(Word::BITS - vec.len);
589        assert!(vec.capacity() >= Word::BITS);
590
591        vec.reserve(Word::BITS);
592        assert!(vec.capacity() >= Word::BITS * 2);
593    }
594
595    #[test]
596    fn test_shrink_to_fit() {
597        let mut vec = bitvec![true, true, false, false];
598        let unchanged = vec.clone();
599
600        vec.reserve(Word::BITS);
601        assert!(vec.capacity() >= Word::BITS * 2);
602
603        vec.shrink_to_fit();
604        assert!(vec.capacity() >= Word::BITS);
605        assert_eq!(vec, unchanged);
606
607        assert_eq!(vec.buf.len(), 1);
608        vec.push_unused_word();
609        assert_eq!(vec.buf.len(), 2);
610
611        vec.reserve(Word::BITS);
612        assert!(vec.capacity() >= Word::BITS * 2);
613
614        vec.shrink_to_fit();
615        assert!(vec.capacity() >= Word::BITS);
616        assert_eq!(vec, unchanged);
617        assert_eq!(vec.buf.len(), 1);
618    }
619
620    #[test]
621    fn test_shrink_to() {
622        let mut vec = bitvec![true, true, false, false];
623        let unchanged = vec.clone();
624
625        vec.reserve(Word::BITS * 2);
626        assert!(vec.capacity() >= Word::BITS * 3);
627
628        let capacity_unchanged = vec.capacity();
629        vec.shrink_to(capacity_unchanged + 1);
630        assert_eq!(vec.capacity(), capacity_unchanged);
631        assert_eq!(vec, unchanged);
632
633        vec.shrink_to(Word::BITS * 2);
634        assert!(vec.capacity() >= Word::BITS * 2);
635        assert_eq!(vec, unchanged);
636
637        vec.shrink_to(0);
638        assert!(vec.capacity() >= Word::BITS);
639        assert_eq!(vec, unchanged);
640
641        assert_eq!(vec.buf.len(), 1);
642        vec.push_unused_word();
643        assert_eq!(vec.buf.len(), 2);
644
645        vec.reserve(Word::BITS * 2);
646        assert!(vec.capacity() >= Word::BITS * 3);
647
648        let capacity_unchanged = vec.capacity();
649        vec.shrink_to(capacity_unchanged + 1);
650        assert_eq!(vec.capacity(), capacity_unchanged);
651        assert_eq!(vec, unchanged);
652        assert_eq!(vec.buf.len(), 2);
653
654        vec.shrink_to(Word::BITS * 2);
655        assert!(vec.capacity() >= Word::BITS * 2);
656        assert_eq!(vec, unchanged);
657        assert_eq!(vec.buf.len(), 2);
658
659        vec.shrink_to(0);
660        assert!(vec.capacity() >= Word::BITS);
661        assert_eq!(vec, unchanged);
662        assert_eq!(vec.buf.len(), 1);
663    }
664
665    #[test]
666    fn test_get() {
667        {
668            let mut vec = bitvec![true, true, false, false];
669
670            assert_eq!(vec.get(0), Some(true));
671            assert_eq!(vec.get(1), Some(true));
672            assert_eq!(vec.get(2), Some(false));
673            assert_eq!(vec.get(3), Some(false));
674            assert_eq!(vec.get(4), None);
675
676            vec.push_unused_word();
677
678            assert_eq!(vec.get(0), Some(true));
679            assert_eq!(vec.get(1), Some(true));
680            assert_eq!(vec.get(2), Some(false));
681            assert_eq!(vec.get(3), Some(false));
682            assert_eq!(vec.get(4), None);
683        }
684
685        {
686            let mut vec = bitvec![true; Word::BITS];
687
688            assert_eq!(vec.get(Word::BITS - 1), Some(true));
689            assert_eq!(vec.get(Word::BITS), None);
690
691            vec.push_unused_word();
692
693            assert_eq!(vec.get(Word::BITS - 1), Some(true));
694            assert_eq!(vec.get(Word::BITS), None);
695        }
696
697        {
698            let mut vec = bitvec![true; Word::BITS + 1];
699
700            assert_eq!(vec.get(Word::BITS), Some(true));
701            assert_eq!(vec.get(Word::BITS + 1), None);
702
703            vec.push_unused_word();
704
705            assert_eq!(vec.get(Word::BITS), Some(true));
706            assert_eq!(vec.get(Word::BITS + 1), None);
707        }
708    }
709
710    #[test]
711    fn test_get_unchecked() {
712        let mut vec = bitvec![true, true, false, false];
713
714        unsafe {
715            assert!(vec.get_unchecked(0));
716            assert!(vec.get_unchecked(1));
717            assert!(!vec.get_unchecked(2));
718            assert!(!vec.get_unchecked(3));
719        }
720
721        vec.push_unused_word();
722
723        unsafe {
724            assert!(vec.get_unchecked(0));
725            assert!(vec.get_unchecked(1));
726            assert!(!vec.get_unchecked(2));
727            assert!(!vec.get_unchecked(3));
728        }
729    }
730
731    #[test]
732    fn test_set() {
733        {
734            let mut vec = bitvec![true, true, false, false];
735            let unchanged = vec.clone();
736
737            assert!(vec.set(0, true).is_some());
738            assert!(vec.set(1, false).is_some());
739            assert!(vec.set(2, true).is_some());
740            assert!(vec.set(3, false).is_some());
741            assert!(vec.set(4, true).is_none());
742            assert_eq!(vec, bitvec![true, false, true, false]);
743
744            let mut vec = unchanged;
745            vec.push_unused_word();
746
747            assert!(vec.set(0, true).is_some());
748            assert!(vec.set(1, false).is_some());
749            assert!(vec.set(2, true).is_some());
750            assert!(vec.set(3, false).is_some());
751            assert!(vec.set(4, true).is_none());
752            assert_eq!(vec, bitvec![true, false, true, false]);
753        }
754
755        {
756            let mut vec = bitvec![true; Word::BITS];
757            let unchanged = vec.clone();
758
759            assert!(vec.set(Word::BITS - 1, false).is_some());
760            assert_eq!(vec.get(Word::BITS - 1), Some(false));
761            assert!(vec.set(Word::BITS, false).is_none());
762
763            let mut vec = unchanged;
764            vec.push_unused_word();
765
766            assert!(vec.set(Word::BITS - 1, false).is_some());
767            assert_eq!(vec.get(Word::BITS - 1), Some(false));
768            assert!(vec.set(Word::BITS, false).is_none());
769        }
770
771        {
772            let mut vec = bitvec![true; Word::BITS + 1];
773            let unchanged = vec.clone();
774
775            assert!(vec.set(Word::BITS, false).is_some());
776            assert_eq!(vec.get(Word::BITS), Some(false));
777            assert!(vec.set(Word::BITS + 1, false).is_none());
778
779            let mut vec = unchanged;
780            vec.push_unused_word();
781
782            assert!(vec.set(Word::BITS, false).is_some());
783            assert_eq!(vec.get(Word::BITS), Some(false));
784            assert!(vec.set(Word::BITS + 1, false).is_none());
785        }
786    }
787
788    #[test]
789    fn test_set_unchecked() {
790        let mut vec = bitvec![true, true, false, false];
791        let unchanged = vec.clone();
792
793        unsafe {
794            vec.set_unchecked(2, true);
795            vec.set_unchecked(3, true);
796        }
797        assert_eq!(vec, bitvec![true; 4]);
798
799        let mut vec = unchanged;
800        vec.push_unused_word();
801
802        unsafe {
803            vec.set_unchecked(2, true);
804            vec.set_unchecked(3, true);
805        }
806        assert_eq!(vec, bitvec![true; 4]);
807    }
808
809    #[test]
810    fn test_push() {
811        {
812            let mut vec = bitvec![true, true, false, false];
813            let unchanged = vec.clone();
814
815            vec.push(true);
816            assert_eq!(vec, bitvec![true, true, false, false, true]);
817            vec.push(false);
818            assert_eq!(vec, bitvec![true, true, false, false, true, false]);
819
820            let mut vec = unchanged;
821            vec.push_unused_word();
822
823            vec.push(true);
824            assert_eq!(vec, bitvec![true, true, false, false, true]);
825            vec.push(false);
826            assert_eq!(vec, bitvec![true, true, false, false, true, false]);
827        }
828
829        {
830            let mut vec = bitvec![true; Word::BITS];
831            let unchanged = vec.clone();
832
833            assert_eq!(vec.buf.len(), 1);
834            vec.push(true);
835            assert_eq!(vec.len, Word::BITS + 1);
836            assert_eq!(vec.get(vec.len - 1), Some(true));
837            assert_eq!(vec.buf.len(), 2);
838            vec.push(false);
839            assert_eq!(vec.len, Word::BITS + 2);
840            assert_eq!(vec.get(vec.len - 1), Some(false));
841            assert_eq!(vec.buf.len(), 2);
842
843            let mut vec = unchanged;
844            vec.push_unused_word();
845
846            assert_eq!(vec.buf.len(), 2);
847            vec.push(true);
848            assert_eq!(vec.len, Word::BITS + 1);
849            assert_eq!(vec.get(vec.len - 1), Some(true));
850            assert_eq!(vec.buf.len(), 2);
851            vec.push(false);
852            assert_eq!(vec.len, Word::BITS + 2);
853            assert_eq!(vec.get(vec.len - 1), Some(false));
854            assert_eq!(vec.buf.len(), 2);
855        }
856    }
857
858    #[test]
859    fn test_pop() {
860        {
861            let mut vec = bitvec![true, true, false, false];
862            let unchanged = vec.clone();
863
864            assert_eq!(vec.pop(), Some(false));
865            assert_eq!(vec, bitvec![true, true, false]);
866            assert_eq!(vec.pop(), Some(false));
867            assert_eq!(vec, bitvec![true, true]);
868            assert_eq!(vec.pop(), Some(true));
869            assert_eq!(vec, bitvec![true]);
870            assert_eq!(vec.pop(), Some(true));
871            assert_eq!(vec, bitvec![]);
872            assert_eq!(vec.pop(), None);
873            assert_eq!(vec, bitvec![]);
874
875            let mut vec = unchanged;
876            vec.push_unused_word();
877
878            assert_eq!(vec.pop(), Some(false));
879            assert_eq!(vec, bitvec![true, true, false]);
880            assert_eq!(vec.pop(), Some(false));
881            assert_eq!(vec, bitvec![true, true]);
882            assert_eq!(vec.pop(), Some(true));
883            assert_eq!(vec, bitvec![true]);
884            assert_eq!(vec.pop(), Some(true));
885            assert_eq!(vec, bitvec![]);
886            assert_eq!(vec.pop(), None);
887            assert_eq!(vec, bitvec![]);
888        }
889
890        {
891            let mut vec = bitvec![true; Word::BITS + 1];
892            let unchanged = vec.clone();
893
894            assert_eq!(vec.buf.len(), 2);
895            while vec.pop().is_some() {}
896            assert_eq!(vec.len, 0);
897            assert_eq!(vec.buf.len(), 2);
898
899            let mut vec = unchanged;
900            vec.push_unused_word();
901
902            assert_eq!(vec.buf.len(), 3);
903            while vec.pop().is_some() {}
904            assert_eq!(vec.len, 0);
905            assert_eq!(vec.buf.len(), 3);
906        }
907    }
908
909    #[test]
910    fn test_index() {
911        let mut vec = bitvec![true, true, false, false];
912
913        assert!(vec[0]);
914        assert!(vec[1]);
915        assert!(!vec[2]);
916        assert!(!vec[3]);
917
918        vec.push_unused_word();
919
920        assert!(vec[0]);
921        assert!(vec[1]);
922        assert!(!vec[2]);
923        assert!(!vec[3]);
924    }
925
926    #[test]
927    #[should_panic]
928    fn test_index_fails() {
929        let vec = bitvec![true, true, false, false];
930
931        let _ = vec[4];
932    }
933
934    #[test]
935    fn test_clone() {
936        let mut vec = bitvec![true, true, false, false];
937
938        let cloned = vec.clone();
939        assert_eq!(vec, cloned);
940
941        vec.push_unused_word();
942
943        let cloned = vec.clone();
944        assert_eq!(vec, cloned);
945        assert_eq!(vec.buf.len(), 2);
946        assert_eq!(cloned.buf.len(), 1);
947    }
948
949    #[test]
950    fn test_extend() {
951        let mut vec = bitvec![true, true, false, false];
952        let unchanged = vec.clone();
953
954        vec.extend([true; Word::BITS]);
955        assert_eq!(vec.len, Word::BITS + 4);
956        assert_eq!(vec.get(0), Some(true));
957        assert_eq!(vec.get(1), Some(true));
958        assert_eq!(vec.get(2), Some(false));
959        assert_eq!(vec.get(3), Some(false));
960        for index in 4..vec.len {
961            assert_eq!(vec.get(index), Some(true));
962        }
963
964        let mut vec = unchanged;
965        vec.push_unused_word();
966
967        vec.extend([true; Word::BITS]);
968        assert_eq!(vec.len, Word::BITS + 4);
969        assert_eq!(vec.get(0), Some(true));
970        assert_eq!(vec.get(1), Some(true));
971        assert_eq!(vec.get(2), Some(false));
972        assert_eq!(vec.get(3), Some(false));
973        for index in 4..vec.len {
974            assert_eq!(vec.get(index), Some(true));
975        }
976    }
977
978    #[test]
979    #[should_panic]
980    fn test_extend_fail() {
981        let mut vec = bitvec![true, true, false, false];
982
983        vec.extend(repeat_n(true, usize::MAX));
984    }
985
986    #[test]
987    fn test_hash() {
988        fn hash(vec: &BitVec) -> u64 {
989            let mut hasher = DefaultHasher::new();
990            vec.hash(&mut hasher);
991            hasher.finish()
992        }
993
994        {
995            let lhs = bitvec![true, true, false, false];
996            let rhs = bitvec![true; 4];
997            let unchanged = rhs.clone();
998
999            let lhs_hash = hash(&lhs);
1000            let rhs_hash = hash(&rhs);
1001            assert_ne!(lhs_hash, rhs_hash);
1002
1003            let mut rhs = unchanged;
1004            rhs.push_unused_word();
1005
1006            let lhs_hash = hash(&lhs);
1007            let rhs_hash = hash(&rhs);
1008            assert_ne!(lhs_hash, rhs_hash);
1009        }
1010
1011        {
1012            let lhs = bitvec![true, true, false, false];
1013            let mut rhs = bitvec![true, true, false, false, true];
1014            let unchanged = rhs.clone();
1015
1016            let lhs_hash = hash(&lhs);
1017            let rhs_hash = hash(&rhs);
1018            assert_ne!(lhs_hash, rhs_hash);
1019            rhs.pop();
1020            let rhs_hash = hash(&rhs);
1021            assert_eq!(lhs_hash, rhs_hash);
1022
1023            let mut rhs = unchanged;
1024            rhs.push_unused_word();
1025
1026            let lhs_hash = hash(&lhs);
1027            let rhs_hash = hash(&rhs);
1028            assert_ne!(lhs_hash, rhs_hash);
1029            rhs.pop();
1030            let rhs_hash = hash(&rhs);
1031            assert_eq!(lhs_hash, rhs_hash);
1032        }
1033
1034        {
1035            let lhs = bitvec![true; Word::BITS + 1];
1036            let mut rhs = lhs.clone();
1037
1038            let lhs_hash = hash(&lhs);
1039            let rhs_hash = hash(&rhs);
1040            assert_eq!(lhs_hash, rhs_hash);
1041            rhs.push(true).pop();
1042            let rhs_hash = hash(&rhs);
1043            assert_eq!(lhs_hash, rhs_hash);
1044
1045            let mut rhs = lhs.clone();
1046            rhs.push_unused_word();
1047
1048            let lhs_hash = hash(&lhs);
1049            let rhs_hash = hash(&rhs);
1050            assert_eq!(lhs_hash, rhs_hash);
1051            rhs.push(true).pop();
1052            let rhs_hash = hash(&rhs);
1053            assert_eq!(lhs_hash, rhs_hash);
1054        }
1055    }
1056
1057    #[test]
1058    fn test_eq() {
1059        {
1060            let lhs = bitvec![true, true, false, false];
1061            let rhs = bitvec![true; 4];
1062            let unchanged = rhs.clone();
1063
1064            assert_ne!(lhs, rhs);
1065
1066            let mut rhs = unchanged;
1067            rhs.push_unused_word();
1068
1069            assert_ne!(lhs, rhs);
1070        }
1071
1072        {
1073            let lhs = bitvec![true, true, false, false];
1074            let mut rhs = bitvec![true, true, false, false, true];
1075            let unchanged = rhs.clone();
1076
1077            assert_ne!(lhs, rhs);
1078            rhs.pop();
1079            assert_eq!(lhs, rhs);
1080
1081            let mut rhs = unchanged;
1082            rhs.push_unused_word();
1083
1084            assert_ne!(lhs, rhs);
1085            rhs.pop();
1086            assert_eq!(lhs, rhs);
1087        }
1088
1089        {
1090            let lhs = bitvec![true; Word::BITS + 1];
1091            let mut rhs = lhs.clone();
1092
1093            assert_eq!(lhs, rhs);
1094            rhs.push(true).pop();
1095            assert_eq!(lhs, rhs);
1096
1097            let mut rhs = lhs.clone();
1098            rhs.push_unused_word();
1099
1100            assert_eq!(lhs, rhs);
1101            rhs.push(true).pop();
1102            assert_eq!(lhs, rhs);
1103        }
1104    }
1105}
bitvek/lib.rs

bitvek/
lib.rs
