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
use std::iter;
pub struct BitVector {
data: Vec<u64>
}
impl BitVector {
pub fn new(num_bits: usize) -> BitVector {
let num_words = (num_bits + 63) / 64;
BitVector { data: iter::repeat(0).take(num_words).collect() }
}
fn word_mask(&self, bit: usize) -> (usize, u64) {
let word = bit / 64;
let mask = 1 << (bit % 64);
(word, mask)
}
pub fn contains(&self, bit: usize) -> bool {
let (word, mask) = self.word_mask(bit);
(self.data[word] & mask) != 0
}
pub fn insert(&mut self, bit: usize) -> bool {
let (word, mask) = self.word_mask(bit);
let data = &mut self.data[word];
let value = *data;
*data = value | mask;
(value | mask) != value
}
}