1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

//! Implements access to a matrix's individual rows.

use core::mem;
use core::ops::Index;
use core::ops::Range;

use super::{FALSE, TRUE};
use crate::local_prelude::*;
use crate::util::div_rem;

/// A slice of bit vector's blocks.
pub struct BitSlice {
    pub(crate) slice: [Block],
}

impl BitSlice {
    /// Creates a new slice from a slice of blocks.
    #[inline]
    pub fn new(slice: &[Block]) -> &Self {
        unsafe { mem::transmute(slice) }
    }

    /// Creates a new slice from a mutable slice of blocks.
    #[inline]
    pub fn new_mut(slice: &mut [Block]) -> &mut Self {
        unsafe { mem::transmute(slice) }
    }

    /// Iterates over bits.
    #[inline]
    pub fn iter_bits(&self, len: usize) -> Iter {
        Iter {
            bit_slice: self,
            range: 0..len,
        }
    }

    /// Iterates over the slice's blocks.
    pub fn iter_blocks(&self) -> impl Iterator<Item = &Block> {
        self.slice.iter()
    }

    /// Iterates over the slice's blocks, yielding mutable references.
    pub fn iter_blocks_mut(&mut self) -> impl Iterator<Item = &mut Block> {
        self.slice.iter_mut()
    }

    /// Returns `true` if a bit is enabled in the bit vector slice, or `false` otherwise.
    #[inline]
    pub fn get(&self, bit: usize) -> bool {
        let (block, i) = div_rem(bit, BITS);
        match self.slice.get(block) {
            None => false,
            Some(b) => (b & (1 << i)) != 0,
        }
    }

    /// Returns a small integer-sized slice of the bit vector slice.
    #[inline]
    pub fn small_slice_aligned(&self, bit: usize, len: u8) -> u32 {
        let (block, i) = div_rem(bit, BITS);
        match self.slice.get(block) {
            None => 0,
            Some(&b) => {
                let len_mask = (1 << len) - 1;
                (b >> i) & len_mask
            }
        }
    }
}

/// Returns `true` if a bit is enabled in the bit vector slice, or `false` otherwise.
impl Index<usize> for BitSlice {
    type Output = bool;

    #[inline]
    fn index(&self, bit: usize) -> &bool {
        let (block, i) = div_rem(bit, BITS);
        match self.slice.get(block) {
            None => &FALSE,
            Some(b) => {
                if (b & (1 << i)) != 0 {
                    &TRUE
                } else {
                    &FALSE
                }
            }
        }
    }
}

/// An iterator for `BitVecSlice`.
#[derive(Clone)]
pub struct Iter<'a> {
    bit_slice: &'a BitSlice,
    range: Range<usize>,
}

impl<'a> Iterator for Iter<'a> {
    type Item = bool;

    #[inline]
    fn next(&mut self) -> Option<bool> {
        self.range.next().map(|i| self.bit_slice[i])
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.range.size_hint()
    }
}