Skip to main content

BitVector

competitive::data_structure::bit_vector

Struct BitVector 

Source 
pub struct BitVector {
    blocks: Vec<BitVectorBlock>,
    len: usize,
    sum: usize,
    select_samples: [Vec<usize>; 2],
}

Fields§

§blocks: Vec<BitVectorBlock>§len: usize§sum: usize§select_samples: [Vec<usize>; 2]

Implementations§

Source§

impl BitVector

Source

const WORD_SIZE: usize

Source

pub fn from_words(words: &[u64], len: usize) -> Self

Builds a bit vector from low-bit-first words. words.len() must equal len.div_ceil(64). Unused high bits in the final word are ignored.

Examples found in repository?
crates/competitive/src/data_structure/wavelet_matrix.rs (line 564)
524    fn from_values<I: Copy>(
525        v: Vec<T>,
526        code: impl Fn(usize) -> I,
527        index: impl Fn(I) -> usize,
528        pack: impl Fn(&[I], usize) -> Vec<u64>,
529        partition: impl Fn(&[I], &[u64], usize, &mut [I]),
530    ) -> Self {
531        let len = v.len();
532        let mut sorted: Vec<_> = v
533            .into_iter()
534            .enumerate()
535            .map(|(i, value)| (value, code(i)))
536            .collect();
537        sorted.sort_unstable_by(|a, b| a.0.cmp(&b.0));
538        let mut values = Vec::with_capacity(len);
539        let mut indices = vec![code(0); len];
540        for (value, i) in sorted {
541            if values.last().is_none_or(|last| last != &value) {
542                values.push(value);
543            }
544            indices[index(i)] = code(values.len() - 1);
545        }
546        let compress = VecCompress::from_sorted_unique(values);
547        let bit_length = usize::BITS as usize - compress.size().leading_zeros() as usize;
548        let mut bit_vectors = Vec::with_capacity(bit_length);
549        let mut zeros = Vec::with_capacity(bit_length);
550        let quad_bits =
551            usize::BITS as usize - compress.size().saturating_sub(1).leading_zeros() as usize;
552        let mut quad_vectors = Vec::with_capacity(quad_bits.div_ceil(2));
553        let mut next = indices.clone();
554        for d in (0..bit_length).rev() {
555            let words = pack(&indices, d);
556            if len <= u32::MAX as usize && d < quad_bits && (d % 2 == 1 || d + 1 == quad_bits) {
557                if d % 2 == 1 {
558                    let low = pack(&indices, d - 1);
559                    quad_vectors.push(WaveletMatrixQuadVector::from_words(&low, Some(&words), len));
560                } else {
561                    quad_vectors.push(WaveletMatrixQuadVector::from_words(&words, None, len));
562                }
563            }
564            let bits = BitVector::from_words(&words, len);
565            let zero_count = bits.rank0(len);
566            if d == 0 {
567                zeros.push(zero_count);
568                bit_vectors.push(bits);
569                break;
570            }
571            partition(&indices, &words, zero_count, &mut next);
572            zeros.push(zero_count);
573            bit_vectors.push(bits);
574            mem::swap(&mut indices, &mut next);
575        }
576        Self {
577            len,
578            bit_length,
579            zeros,
580            bit_vectors,
581            quad_vectors,
582            compress,
583            #[cfg(target_arch = "x86_64")]
584            backend: match super::simd_backend() {
585                super::SimdBackend::Avx512 if !is_x86_feature_detected!("avx512vpopcntdq") => {
586                    super::SimdBackend::Avx2
587                }
588                backend => backend,
589            },
590        }
591    }
Source

fn from_blocks(blocks: Vec<BitVectorBlock>, len: usize, sum: usize) -> Self

Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 169)
152    pub fn from_words(words: &[u64], len: usize) -> Self {
153        assert_eq!(words.len(), len.div_ceil(Self::WORD_SIZE));
154        let mut sum = 0;
155        let mut blocks = Vec::with_capacity(len / Self::WORD_SIZE + 1);
156        for (i, &bits) in words.iter().enumerate() {
157            let count = (len - i * Self::WORD_SIZE).min(Self::WORD_SIZE);
158            let bits = if count == Self::WORD_SIZE {
159                bits
160            } else {
161                bits & ((1u64 << count) - 1)
162            };
163            blocks.push(BitVectorBlock { bits, rank: sum });
164            sum += bits.count_ones() as usize;
165        }
166        if len.is_multiple_of(Self::WORD_SIZE) {
167            blocks.push(BitVectorBlock { bits: 0, rank: sum });
168        }
169        Self::from_blocks(blocks, len, sum)
170    }
171
172    fn from_blocks(blocks: Vec<BitVectorBlock>, len: usize, sum: usize) -> Self {
173        let mut select_samples = [Vec::new(), Vec::new()];
174        for (i, block) in blocks
175            .iter()
176            .enumerate()
177            .take(len.div_ceil(Self::WORD_SIZE))
178        {
179            let start = [i * Self::WORD_SIZE - block.rank, block.rank];
180            let end1 = blocks.get(i + 1).map_or(sum, |next| next.rank);
181            let end = [((i + 1) * Self::WORD_SIZE).min(len) - end1, end1];
182            for bit in 0..2 {
183                if start[bit].div_ceil(256) != end[bit].div_ceil(256) {
184                    select_samples[bit].push(i);
185                }
186            }
187        }
188        Self {
189            blocks,
190            len,
191            sum,
192            select_samples,
193        }
194    }
195
196    pub fn with_capacity(bits: usize) -> Self {
197        let mut blocks = Vec::with_capacity(bits.div_ceil(Self::WORD_SIZE) + 1);
198        blocks.push(BitVectorBlock { bits: 0, rank: 0 });
199        Self {
200            blocks,
201            len: 0,
202            sum: 0,
203            select_samples: [Vec::new(), Vec::new()],
204        }
205    }
206
207    pub fn push(&mut self, bit: bool) {
208        let word = self.len / Self::WORD_SIZE;
209        let rank = if bit { self.sum } else { self.len - self.sum };
210        if rank.is_multiple_of(256) {
211            self.select_samples[bit as usize].push(word);
212        }
213        self.blocks[word].bits |= (bit as u64) << (self.len % Self::WORD_SIZE);
214        self.sum += bit as usize;
215        self.len += 1;
216        if self.len.is_multiple_of(Self::WORD_SIZE) {
217            self.blocks.push(BitVectorBlock {
218                bits: 0,
219                rank: self.sum,
220            });
221        }
222    }
223
224    /// Words paired with the number of ones preceding each word. The last block
225    /// is partial, or an empty sentinel when the bit length is a multiple of 64.
226    pub fn blocks(&self) -> &[BitVectorBlock] {
227        &self.blocks
228    }
229
230    /// Returns the position of the zero-based occurrence `rank` in `bits`.
231    /// `rank` must be less than the number of set bits.
232    #[inline]
233    pub fn select_word(bits: u64, rank: usize) -> usize {
234        #[cfg(target_arch = "x86_64")]
235        if is_x86_feature_detected!("bmi2") {
236            // SAFETY: BMI2 is available and the caller checked the occurrence count.
237            return unsafe { simd::select_word(bits, rank) };
238        }
239        select_word_scalar(bits, rank)
240    }
241}
242
243impl RankSelectDictionaries for BitVector {
244    fn bit_length(&self) -> usize {
245        self.len
246    }
247
248    #[inline]
249    fn access(&self, k: usize) -> bool {
250        self.blocks[k / Self::WORD_SIZE].bits & (1u64 << (k % Self::WORD_SIZE)) != 0
251    }
252
253    #[inline]
254    fn access_rank1(&self, k: usize) -> (bool, usize) {
255        let block = &self.blocks[k / Self::WORD_SIZE];
256        let offset = k % Self::WORD_SIZE;
257        (
258            block.bits & (1u64 << offset) != 0,
259            block.rank + (block.bits & !(u64::MAX << offset)).count_ones() as usize,
260        )
261    }
262
263    #[inline]
264    fn rank1(&self, k: usize) -> usize {
265        self.access_rank1(k).1
266    }
267
268    fn select1(&self, k: usize) -> Option<usize> {
269        if k >= self.sum {
270            return None;
271        }
272        let sample = k / 256;
273        let start = self.select_samples[1][sample];
274        let end = self.select_samples[1]
275            .get(sample + 1)
276            .map_or(self.blocks.len(), |&word| word + 1);
277        let word = start + self.blocks[start..end].partition_point(|block| block.rank <= k) - 1;
278        let rank = k - self.blocks[word].rank;
279        Some(word * Self::WORD_SIZE + Self::select_word(self.blocks[word].bits, rank))
280    }
281
282    fn select0(&self, k: usize) -> Option<usize> {
283        if k >= self.len - self.sum {
284            return None;
285        }
286        let sample = k / 256;
287        let mut word = self.select_samples[0][sample];
288        let end = self.select_samples[0]
289            .get(sample + 1)
290            .map_or(self.blocks.len(), |&word| word + 1);
291        let mut size = end - word;
292        while size > 1 {
293            let half = size / 2;
294            let middle = word + half;
295            word = if middle * Self::WORD_SIZE - self.blocks[middle].rank <= k {
296                middle
297            } else {
298                word
299            };
300            size -= half;
301        }
302        let rank = k - (word * Self::WORD_SIZE - self.blocks[word].rank);
303        Some(word * Self::WORD_SIZE + Self::select_word(!self.blocks[word].bits, rank))
304    }
305}
306
307impl FromIterator<bool> for BitVector {
308    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
309        let iter = iter.into_iter();
310        let mut blocks = Vec::with_capacity(iter.size_hint().0 / Self::WORD_SIZE + 1);
311        let mut len = 0usize;
312        let mut sum = 0;
313        let mut iter = iter.fuse();
314        while let Some(first) = iter.next() {
315            let mut bits = first as u64;
316            let mut count = 1;
317            for (i, bit) in iter.by_ref().take(Self::WORD_SIZE - 1).enumerate() {
318                bits |= (bit as u64) << (i + 1);
319                count += 1;
320            }
321            blocks.push(BitVectorBlock { bits, rank: sum });
322            len += count;
323            sum += bits.count_ones() as usize;
324        }
325        if len.is_multiple_of(Self::WORD_SIZE) {
326            blocks.push(BitVectorBlock { bits: 0, rank: sum });
327        }
328        Self::from_blocks(blocks, len, sum)
329    }
Source

pub fn with_capacity(bits: usize) -> Self

Source

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

Source

pub fn blocks(&self) -> &[BitVectorBlock]

Words paired with the number of ones preceding each word. The last block is partial, or an empty sentinel when the bit length is a multiple of 64.

Examples found in repository?
crates/competitive/src/data_structure/wavelet_matrix.rs (line 656)
649    fn reorder<U>(&self, level: usize, current: Vec<U>) -> Vec<U> {
650        assert_eq!(current.len(), self.len);
651        let mut next = Vec::with_capacity(self.len);
652        next.resize_with(self.len, MaybeUninit::uninit);
653        let mut zero = 0;
654        let mut one = self.zeros[level];
655        let mut current = current.into_iter();
656        for block in self.bit_vectors[level].blocks() {
657            let count = current.len().min(64);
658            if block.bits == 0 || block.bits == u64::MAX {
659                let offset = if block.bits == 0 { &mut zero } else { &mut one };
660                for (slot, value) in next[*offset..*offset + count]
661                    .iter_mut()
662                    .zip(current.by_ref().take(count))
663                {
664                    slot.write(value);
665                }
666                *offset += count;
667            } else {
668                for (i, value) in current.by_ref().take(count).enumerate() {
669                    let bit = (block.bits >> i) & 1 != 0;
670                    next[if bit { one } else { zero }].write(value);
671                    zero += !bit as usize;
672                    one += bit as usize;
673                }
674            }
675        }
676        // SAFETY: the partition counts fill every slot once, and `MaybeUninit<U>` has `U`'s layout.
677        unsafe {
678            let mut next = mem::ManuallyDrop::new(next);
679            Vec::from_raw_parts(next.as_mut_ptr().cast(), next.len(), next.capacity())
680        }
681    }
Source

pub fn select_word(bits: u64, rank: usize) -> usize

Returns the position of the zero-based occurrence rank in bits. rank must be less than the number of set bits.

Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 279)
268    fn select1(&self, k: usize) -> Option<usize> {
269        if k >= self.sum {
270            return None;
271        }
272        let sample = k / 256;
273        let start = self.select_samples[1][sample];
274        let end = self.select_samples[1]
275            .get(sample + 1)
276            .map_or(self.blocks.len(), |&word| word + 1);
277        let word = start + self.blocks[start..end].partition_point(|block| block.rank <= k) - 1;
278        let rank = k - self.blocks[word].rank;
279        Some(word * Self::WORD_SIZE + Self::select_word(self.blocks[word].bits, rank))
280    }
281
282    fn select0(&self, k: usize) -> Option<usize> {
283        if k >= self.len - self.sum {
284            return None;
285        }
286        let sample = k / 256;
287        let mut word = self.select_samples[0][sample];
288        let end = self.select_samples[0]
289            .get(sample + 1)
290            .map_or(self.blocks.len(), |&word| word + 1);
291        let mut size = end - word;
292        while size > 1 {
293            let half = size / 2;
294            let middle = word + half;
295            word = if middle * Self::WORD_SIZE - self.blocks[middle].rank <= k {
296                middle
297            } else {
298                word
299            };
300            size -= half;
301        }
302        let rank = k - (word * Self::WORD_SIZE - self.blocks[word].rank);
303        Some(word * Self::WORD_SIZE + Self::select_word(!self.blocks[word].bits, rank))
304    }
More examples
Hide additional examples
crates/competitive/src/data_structure/wavelet_matrix.rs (line 112)
100    fn select(&self, digit: usize, k: usize) -> usize {
101        let sample = k / 128;
102        let start = self.select_samples[digit][sample];
103        let end = self.select_samples[digit]
104            .get(sample + 1)
105            .map_or(self.blocks.len(), |&word| word + 1);
106        let word = start
107            + self.blocks[start..end].partition_point(|block| block.rank[digit] as usize <= k)
108            - 1;
109        let block = &self.blocks[word];
110        let lo = if digit & 1 != 0 { block.lo } else { !block.lo };
111        let hi = if digit & 2 != 0 { block.hi } else { !block.hi };
112        word * 64 + BitVector::select_word(lo & hi, k - block.rank[digit] as usize)
113    }

Trait Implementations§

Source§

impl Clone for BitVector

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for BitVector

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl FromIterator<bool> for BitVector

Source§

fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self

Creates a value from an iterator. Read more
Source§

impl RankSelectDictionaries for BitVector

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

get k-th bit
Source§

fn access_rank1(&self, k: usize) -> (bool, usize)

Returns the k-th bit and the number of ones before it.
Source§

fn rank1(&self, k: usize) -> usize

the number of 1 in [0, k)
Source§

fn select1(&self, k: usize) -> Option<usize>

index of k-th 1
Source§

fn select0(&self, k: usize) -> Option<usize>

index of k-th 0
Source§

fn rank0(&self, k: usize) -> usize

the number of 0 in [0, k)

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.