Struct BitVector

Source

pub struct BitVector {
    data: Vec<(usize, usize)>,
    sum: usize,
    len: usize,
}

Fields§

§data: Vec<(usize, usize)>

[(bit, sum)]

§sum: usize§len: usize

Implementations§

Source §

impl BitVector

Source

const WORD_SIZE: usize

Source

pub fn with_capacity(bits: usize) -> Self

Examples found in repository ?

crates/competitive/src/data_structure/bit_vector.rs (line 168)

164    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
165        let iter = iter.into_iter();
166        let (lower, upper) = iter.size_hint();
167        let mut bit_vector = match upper {
168            Some(upper) => Self::with_capacity(upper),
169            None => Self::with_capacity(lower),
170        };
171        for b in iter {
172            bit_vector.push(b);
173        }
174        bit_vector
175    }

More examples

Hide additional examples

crates/competitive/src/data_structure/wavelet_matrix.rs (line 29)

21    pub fn new(v: Vec<T>) -> Self {
22        let len = v.len();
23        let compress: VecCompress<T> = v.iter().cloned().collect();
24        let bit_length = usize::BITS as usize - compress.size().leading_zeros() as usize;
25        let mut indices: Vec<usize> = v
26            .iter()
27            .map(|value| compress.index_exact(value).unwrap())
28            .collect();
29        let mut bit_vector = BitVector::with_capacity(len * bit_length);
30        let mut zeros = Vec::with_capacity(bit_length);
31        for d in (0..bit_length).rev() {
32            let mut zero_count = 0;
33            for &idx in &indices {
34                let bit = ((idx >> d) & 1) != 0;
35                bit_vector.push(bit);
36                if !bit {
37                    zero_count += 1;
38                }
39            }
40            zeros.push(zero_count);
41            let mut next = Vec::with_capacity(len);
42            next.extend(
43                indices
44                    .iter()
45                    .filter(|&&idx| ((idx >> d) & 1) == 0)
46                    .copied(),
47            );
48            next.extend(
49                indices
50                    .iter()
51                    .filter(|&&idx| ((idx >> d) & 1) == 1)
52                    .copied(),
53            );
54            indices = next;
55        }
56        let mut ones_prefix = Vec::with_capacity(bit_length);
57        let mut prefix = 0;
58        for &zero in &zeros {
59            ones_prefix.push(prefix);
60            prefix += len - zero;
61        }
62        Self {
63            len,
64            bit_length,
65            zeros,
66            ones_prefix,
67            bit_vector,
68            compress,
69        }
70    }

Source

pub fn push(&mut self, bit: bool)

Examples found in repository ?

crates/competitive/src/data_structure/bit_vector.rs (line 172)

164    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
165        let iter = iter.into_iter();
166        let (lower, upper) = iter.size_hint();
167        let mut bit_vector = match upper {
168            Some(upper) => Self::with_capacity(upper),
169            None => Self::with_capacity(lower),
170        };
171        for b in iter {
172            bit_vector.push(b);
173        }
174        bit_vector
175    }

More examples

Hide additional examples

crates/competitive/src/data_structure/wavelet_matrix.rs (line 35)

21    pub fn new(v: Vec<T>) -> Self {
22        let len = v.len();
23        let compress: VecCompress<T> = v.iter().cloned().collect();
24        let bit_length = usize::BITS as usize - compress.size().leading_zeros() as usize;
25        let mut indices: Vec<usize> = v
26            .iter()
27            .map(|value| compress.index_exact(value).unwrap())
28            .collect();
29        let mut bit_vector = BitVector::with_capacity(len * bit_length);
30        let mut zeros = Vec::with_capacity(bit_length);
31        for d in (0..bit_length).rev() {
32            let mut zero_count = 0;
33            for &idx in &indices {
34                let bit = ((idx >> d) & 1) != 0;
35                bit_vector.push(bit);
36                if !bit {
37                    zero_count += 1;
38                }
39            }
40            zeros.push(zero_count);
41            let mut next = Vec::with_capacity(len);
42            next.extend(
43                indices
44                    .iter()
45                    .filter(|&&idx| ((idx >> d) & 1) == 0)
46                    .copied(),
47            );
48            next.extend(
49                indices
50                    .iter()
51                    .filter(|&&idx| ((idx >> d) & 1) == 1)
52                    .copied(),
53            );
54            indices = next;
55        }
56        let mut ones_prefix = Vec::with_capacity(bit_length);
57        let mut prefix = 0;
58        for &zero in &zeros {
59            ones_prefix.push(prefix);
60            prefix += len - zero;
61        }
62        Self {
63            len,
64            bit_length,
65            zeros,
66            ones_prefix,
67            bit_vector,
68            compress,
69        }
70    }