bv/traits/
bits.rs

1use super::BitsMut;
2use storage::{BlockType, Address};
3use BitVec;
4
5/// Read-only bit vector operations.
6///
7/// Minimal complete definition is:
8///
9///   - [`bit_len`] and
10///   - [`get_block`] or [`get_bit`].
11///
12/// Note that [`get_block`] in terms of [`get_bit`] is inefficient, and thus
13/// you should implement [`get_block`] directly if possible.
14///
15/// [`bit_len`]: #method.bit_len
16/// [`get_bit`]: #method.get_bit
17/// [`get_block`]: #method.get_block
18pub trait Bits {
19    /// The underlying block type used to store the bits of the vector.
20    type Block: BlockType;
21
22    /// The length of the slice in bits.
23    fn bit_len(&self) -> u64;
24
25    /// The length of the slice in blocks.
26    fn block_len(&self) -> usize {
27        Self::Block::ceil_div_nbits(self.bit_len())
28    }
29
30    /// Gets the bit at `position`
31    ///
32    /// The default implementation calls `get_block` and masks out the
33    /// correct bit.
34    ///
35    /// # Panics
36    ///
37    /// Panics if `position` is out of bounds.
38    fn get_bit(&self, position: u64) -> bool {
39        assert!(position < self.bit_len(), "Bits::get_bit: out of bounds");
40
41        let address = Address::new::<Self::Block>(position);
42        let block = self.get_raw_block(address.block_index);
43        block.get_bit(address.bit_offset)
44    }
45
46    /// Gets the block at `position`, masked as necessary.
47    ///
48    /// The bits are laid out `Block::nbits()` per block, with the notional
49    /// zeroth bit in the least significant position. If `self.bit_len()` is
50    /// not a multiple of `Block::nbits()` then the last block will
51    /// contain extra zero bits that are not part of the bit vector.
52    ///
53    /// The default implementation calls [`get_raw_block`](#method.get_raw_block),
54    /// but you can override with something more efficient, for example if masking
55    /// is unnecessary.
56    ///
57    /// # Panics
58    ///
59    /// Panics if `position` is out of bounds.
60    fn get_block(&self, position: usize) -> Self::Block {
61        assert!(position < self.block_len(),
62                format!("Bits::get_block: out of bounds ({}/{})",
63                        position, self.block_len()));
64
65        let first_bit = Self::Block::mul_nbits(position);
66        let bit_count = Self::Block::block_bits(self.bit_len(), position);
67
68        let mut result = Self::Block::zero();
69        let mut mask = Self::Block::one();
70
71        for i in 0 .. bit_count as u64 {
72            if self.get_bit(first_bit + i) {
73                result = result | mask;
74            }
75            mask = mask << 1;
76        }
77
78        result
79    }
80
81    /// Gets the block at `position`, without masking.
82    ///
83    /// The default implementation of this method just delegates to [`get_block`](#method
84    /// .get_block), which means it in fact does mask out extraneous bits. However, particular
85    /// implementors may override this method to provide a more efficient implementation when
86    /// one is possible.
87    ///
88    /// # Panics
89    ///
90    /// Panics if `position` is out of bounds.
91    fn get_raw_block(&self, position: usize) -> Self::Block {
92        self.get_block(position)
93    }
94
95    /// Gets `count` bits starting at bit index `start`, interpreted as a
96    /// little-endian integer.
97    ///
98    /// # Panics
99    ///
100    /// Panics if the bit span goes out of bounds.
101    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
102        let limit = start + count as u64;
103        assert!(limit <= self.bit_len(), "Bits::get_bits: out of bounds");
104
105        let address = Address::new::<Self::Block>(start);
106        let margin = Self::Block::nbits() - address.bit_offset;
107
108        if margin >= count {
109            let block = self.get_raw_block(address.block_index);
110            return block.get_bits(address.bit_offset, count)
111        }
112
113        let extra = count - margin;
114
115        let block1 = self.get_raw_block(address.block_index);
116        let block2 = self.get_raw_block(address.block_index + 1);
117
118        let low_bits = block1.get_bits(address.bit_offset, margin);
119        let high_bits = block2.get_bits(0, extra);
120
121        (high_bits << margin) | low_bits
122    }
123
124    /// Copies the bits into a new allocated [`BitVec`].
125    ///
126    /// [`BitVec`]: ../struct.BitVec.html
127    fn to_bit_vec(&self) -> BitVec<Self::Block> {
128        BitVec::from_bits(self)
129    }
130}
131
132/// Gets a block using `get_raw_block` and then masks it appropriately.
133/// This can be used to implement `get_block` in terms of `get_raw_block`.
134pub (crate) fn get_masked_block<T: Bits>(bits: T, position: usize) -> T::Block {
135    let block_bits = T::Block::block_bits(bits.bit_len(), position);
136    bits.get_raw_block(position).get_bits(0, block_bits)
137}
138
139impl<'a, T: Bits + ?Sized> Bits for &'a T {
140    type Block = T::Block;
141
142    fn bit_len(&self) -> u64 {
143        T::bit_len(*self)
144    }
145
146    fn block_len(&self) -> usize {
147        T::block_len(*self)
148    }
149
150    fn get_bit(&self, position: u64) -> bool {
151        T::get_bit(*self, position)
152    }
153
154    fn get_block(&self, position: usize) -> Self::Block {
155        T::get_block(*self, position)
156    }
157
158    fn get_raw_block(&self, position: usize) -> Self::Block {
159        T::get_raw_block(*self, position)
160    }
161
162    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
163        T::get_bits(*self, start, count)
164    }
165}
166
167impl<'a, T: Bits + ?Sized> Bits for &'a mut T {
168    type Block = T::Block;
169
170    fn bit_len(&self) -> u64 {
171        T::bit_len(*self)
172    }
173
174    fn block_len(&self) -> usize {
175        T::block_len(*self)
176    }
177
178    fn get_bit(&self, position: u64) -> bool {
179        T::get_bit(*self, position)
180    }
181
182    fn get_block(&self, position: usize) -> Self::Block {
183        T::get_block(*self, position)
184    }
185
186    fn get_raw_block(&self, position: usize) -> Self::Block {
187        T::get_raw_block(*self, position)
188    }
189
190    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
191        T::get_bits(*self, start, count)
192    }
193}
194
195impl<Block: BlockType> Bits for Box<dyn Bits<Block = Block>> {
196    type Block = Block;
197
198    fn bit_len(&self) -> u64 {
199        (**self).bit_len()
200    }
201
202    fn block_len(&self) -> usize {
203        (**self).block_len()
204    }
205
206    fn get_bit(&self, position: u64) -> bool {
207        (**self).get_bit(position)
208    }
209
210    fn get_block(&self, position: usize) -> Self::Block {
211        (**self).get_block(position)
212    }
213
214    fn get_raw_block(&self, position: usize) -> Self::Block {
215        (**self).get_raw_block(position)
216    }
217
218    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
219        (**self).get_bits(start, count)
220    }
221}
222
223impl<Block: BlockType> Bits for Box<dyn BitsMut<Block = Block>> {
224    type Block = Block;
225
226    fn bit_len(&self) -> u64 {
227        (**self).bit_len()
228    }
229
230    fn block_len(&self) -> usize {
231        (**self).block_len()
232    }
233
234    fn get_bit(&self, position: u64) -> bool {
235        (**self).get_bit(position)
236    }
237
238    fn get_block(&self, position: usize) -> Self::Block {
239        (**self).get_block(position)
240    }
241
242    fn get_raw_block(&self, position: usize) -> Self::Block {
243        (**self).get_raw_block(position)
244    }
245
246    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
247        (**self).get_bits(start, count)
248    }
249}
250
251impl<Block: BlockType> Bits for [Block] {
252    type Block = Block;
253
254    fn bit_len(&self) -> u64 {
255        Block::mul_nbits(self.len())
256    }
257
258    fn block_len(&self) -> usize {
259        self.len()
260    }
261
262    fn get_bit(&self, position: u64) -> bool {
263        let address = Address::new::<Block>(position);
264        self[address.block_index].get_bit(address.bit_offset)
265    }
266
267    fn get_block(&self, position: usize) -> Block {
268        self[position]
269    }
270}
271
272impl<Block: BlockType> Bits for Vec<Block> {
273    type Block = Block;
274
275    fn bit_len(&self) -> u64 {
276        <[Block]>::bit_len(&self)
277    }
278
279    fn block_len(&self) -> usize {
280        <[Block]>::block_len(&self)
281    }
282
283    fn get_bit(&self, position: u64) -> bool {
284        <[Block]>::get_bit(&self, position)
285    }
286
287    fn get_block(&self, position: usize) -> Block {
288        <[Block]>::get_block(&self, position)
289    }
290
291    fn get_raw_block(&self, position: usize) -> Block {
292        <[Block]>::get_raw_block(&self, position)
293    }
294}
295
296impl Bits for [bool] {
297    type Block = u8; // This is bogus
298
299    #[inline]
300    fn bit_len(&self) -> u64 {
301        self.len() as u64
302    }
303
304    #[inline]
305    fn get_bit(&self, position: u64) -> bool {
306        self[position.to_usize().expect("Vec<bool>::get_bit: overflow")]
307    }
308}
309
310impl Bits for Vec<bool> {
311    type Block = u8;
312
313    #[inline]
314    fn bit_len(&self) -> u64 {
315        self.as_slice().bit_len()
316    }
317
318    #[inline]
319    fn get_bit(&self, position: u64) -> bool {
320        self.as_slice().get_bit(position)
321    }
322}
323
bv/traits/bits.rs

bv/traits/
bits.rs
