Struct BucketQueue16 

struct BucketQueue16 {
    counts: Vec<u32>,
    occupied: Vec<u64>,
    summary: [u64; 16],
    top: u16,
    maximum: u16,
    len: usize,
}

Fields

counts: Vec<u32>

occupied: Vec<u64>

summary: [u64; 16]

top: u16

maximum: u16

len: usize

Implementations

impl BucketQueue16

fn new() -> Self

Examples found in repository

crates/competitive/src/data_structure/bucket_queue.rs (line 169)

    fn from_values(values: impl IntoIterator<Item = u16>, len: usize) -> Self {
        assert!(len <= u32::MAX as usize);
        let mut result = Self::new();
        result.len = len;
        for value in values {
            result.counts[value as usize] += 1;
        }
        for (value, &count) in result.counts.iter().enumerate() {
            if count != 0 {
                result.occupied[value / 64] |= 1 << (value % 64);
            }
        }
        for (word, &occupied) in result.occupied.iter().enumerate() {
            if occupied != 0 {
                result.summary[word / 64] |= 1 << (word % 64);
            }
        }
        for (word, &summary) in result.summary.iter().enumerate() {
            if summary != 0 {
                result.top |= 1 << word;
            }
        }
        if len != 0 {
            let summary = (u16::BITS - 1 - result.top.leading_zeros()) as usize;
            let word = summary * 64 + 63 - result.summary[summary].leading_zeros() as usize;
            result.maximum =
                (word * 64 + 63 - result.occupied[word].leading_zeros() as usize) as u16;
        }
        result
    }

fn push(&mut self, value: u16)

Examples found in repository

crates/competitive/src/data_structure/bucket_queue.rs (line 229)

    fn replace(&mut self, value: u16) -> Option<u16> {
        if self.len == 0 {
            self.push(value);
            return None;
        }
        let result = self.maximum;
        if value == result {
            return Some(result);
        }

        let old = result as usize;
        self.counts[old] -= 1;
        if self.counts[old] == 0 {
            let word = old / 64;
            let summary = word / 64;
            self.occupied[word] &= !(1 << (old % 64));
            if self.occupied[word] == 0 {
                self.summary[summary] &= !(1 << (word % 64));
                if self.summary[summary] == 0 {
                    self.top &= !(1 << summary);
                }
            }
        }

        let new = value as usize;
        if self.counts[new] == 0 {
            let word = new / 64;
            self.occupied[word] |= 1 << (new % 64);
            self.summary[word / 64] |= 1 << (word % 64);
            self.top |= 1 << (word / 64);
        }
        self.counts[new] += 1;

        if value > result || self.counts[old] == 0 {
            let summary = (u16::BITS - 1 - self.top.leading_zeros()) as usize;
            let word = summary * 64 + 63 - self.summary[summary].leading_zeros() as usize;
            self.maximum = (word * 64 + 63 - self.occupied[word].leading_zeros() as usize) as u16;
        }
        Some(result)
    }

fn from_values(values: impl IntoIterator<Item = u16>, len: usize) -> Self

fn pop(&mut self) -> Option<u16>

fn replace(&mut self, value: u16) -> Option<u16>

fn clear(&mut self)

Trait Implementations

impl Clone for BucketQueue16

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for BucketQueue16

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

Formats the value using the given formatter.