bv/traits/
bits_mut.rs

1use super::Bits;
2use storage::{BlockType, Address};
3
4/// Mutable bit vector operations that don’t affect the length.
5///
6/// Minimal complete definition is `set_bit` or `set_block`, since each
7/// is defined in terms of the other. Note that `set_block` in terms of
8/// `set_bit` is inefficient, and thus you should implement `set_block`
9/// directly if possible.
10pub trait BitsMut: Bits {
11    /// Sets the bit at `position` to `value`.
12    ///
13    /// The default implementation uses `get_raw_block` and `set_block`.
14    ///
15    /// # Panics
16    ///
17    /// Panics if `position` is out of bounds.
18    fn set_bit(&mut self, position: u64, value: bool) {
19        assert!(position < self.bit_len(), "BitsMut::set_bit: out of bounds");
20
21        let address = Address::new::<Self::Block>(position);
22        let old_block = self.get_raw_block(address.block_index);
23        let new_block = old_block.with_bit(address.bit_offset, value);
24        self.set_block(address.block_index, new_block);
25    }
26
27    /// Sets the block at `position` to `value`.
28    ///
29    /// The bits are laid out `Block::nbits()` per block, with the notional
30    /// zeroth bit in the least significant position. If `self.bit_len()` is
31    /// not a multiple of `Block::nbits()` then the last block will
32    /// contain extra bits that are not part of the bit vector. Implementations
33    /// of `set_block` should not change those trailing bits.
34    ///
35    /// The default implementation sets a block by setting each of its bits
36    /// in turn. Consider it a slow reference implementation, and override it.
37    ///
38    /// # Panics
39    ///
40    /// Panics if `position` is out of bounds.
41    fn set_block(&mut self, position: usize, mut value: Self::Block) {
42        let offset = Self::Block::mul_nbits(position);
43        let count  = Self::Block::block_bits(self.bit_len(), position);
44
45        for i in 0 .. count as u64 {
46            let bit = value & Self::Block::one() != Self::Block::zero();
47            self.set_bit(offset + i, bit);
48            value = value >> 1;
49        }
50    }
51
52    /// Sets `count` bits starting at bit index `start`, interpreted as a
53    /// little-endian integer.
54    ///
55    /// # Panics
56    ///
57    /// Panics if the bit span goes out of bounds.
58    fn set_bits(&mut self, start: u64, count: usize, value: Self::Block) {
59        let limit = start + count as u64;
60        assert!(limit <= self.bit_len(), "BitsMut::set_bits: out of bounds");
61
62        let address = Address::new::<Self::Block>(start);
63        let margin = Self::Block::nbits() - address.bit_offset;
64
65        if margin >= count {
66            let old_block = self.get_raw_block(address.block_index);
67            let new_block = old_block.with_bits(address.bit_offset, count, value);
68            self.set_block(address.block_index, new_block);
69            return;
70        }
71
72        let extra = count - margin;
73
74        let old_block1 = self.get_raw_block(address.block_index);
75        let old_block2 = self.get_raw_block(address.block_index + 1);
76
77        let high_bits = value >> margin;
78
79        let new_block1 = old_block1.with_bits(address.bit_offset,
80                                              margin, value);
81        let new_block2 = old_block2.with_bits(0, extra, high_bits);
82        self.set_block(address.block_index, new_block1);
83        self.set_block(address.block_index + 1, new_block2);
84    }
85}
86
87impl<'a, T: BitsMut + ?Sized> BitsMut for &'a mut T {
88    fn set_bit(&mut self, position: u64, value: bool) {
89        T::set_bit(*self, position, value);
90    }
91
92    fn set_block(&mut self, position: usize, value: Self::Block) {
93        T::set_block(*self, position, value);
94    }
95
96    fn set_bits(&mut self, start: u64, count: usize, value: Self::Block) {
97        T::set_bits(*self, start, count, value);
98    }
99}
100
101impl<Block: BlockType> BitsMut for Box<dyn BitsMut<Block = Block>> {
102    fn set_bit(&mut self, position: u64, value: bool) {
103        (**self).set_bit(position, value);
104    }
105
106    fn set_block(&mut self, position: usize, value: Block) {
107        (**self).set_block(position, value);
108    }
109
110    fn set_bits(&mut self, start: u64, len: usize, value: Block) {
111        (**self).set_bits(start, len, value);
112    }
113}
114
115impl<Block: BlockType> BitsMut for [Block] {
116    fn set_bit(&mut self, position: u64, value: bool) {
117        let address = Address::new::<Block>(position);
118        let block = &mut self[address.block_index];
119        *block = block.with_bit(address.bit_offset, value);
120    }
121
122    fn set_block(&mut self, position: usize, value: Block) {
123        self[position] = value;
124    }
125}
126
127impl<Block: BlockType> BitsMut for Vec<Block> {
128    fn set_bit(&mut self, position: u64, value: bool) {
129        <[Block]>::set_bit(&mut *self, position, value);
130    }
131
132    fn set_block(&mut self, position: usize, value: Block) {
133        <[Block]>::set_block(&mut *self, position, value);
134    }
135}
136
137impl BitsMut for [bool] {
138    fn set_bit(&mut self, position: u64, value: bool) {
139        let position = position.to_usize()
140            .expect("Vec<bool>::set_bit: overflow");
141        self[position] = value;
142    }
143}
144
145impl BitsMut for Vec<bool> {
146    #[inline]
147    fn set_bit(&mut self, position: u64, value: bool) {
148        self.as_mut_slice().set_bit(position, value)
149    }
150}
151
bv/traits/bits_mut.rs

bv/traits/
bits_mut.rs
