competitive::data_structure::bucket_queue

Struct BucketQueue8

struct BucketQueue8 {
    counts: [u32; 256],
    occupied: [u64; 4],
    summary: u8,
    maximum: u8,
    len: usize,
}

Fields§

§counts: [u32; 256]§occupied: [u64; 4]§summary: u8§maximum: u8§len: usize

Implementations§

Source §

impl BucketQueue8

Source

fn new() -> Self

Examples found in repository ?

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

36    fn from_values(values: impl IntoIterator<Item = u8>, len: usize) -> Self {
37        assert!(len <= u32::MAX as usize);
38        let mut result = Self::new();
39        result.len = len;
40        for value in values {
41            result.counts[value as usize] += 1;
42        }
43        for (value, &count) in result.counts.iter().enumerate() {
44            if count != 0 {
45                result.occupied[value / 64] |= 1 << (value % 64);
46            }
47        }
48        for (word, &occupied) in result.occupied.iter().enumerate() {
49            if occupied != 0 {
50                result.summary |= 1 << word;
51            }
52        }
53        if len != 0 {
54            let word = (u8::BITS - 1 - result.summary.leading_zeros()) as usize;
55            result.maximum =
56                (word * 64 + 63 - result.occupied[word].leading_zeros() as usize) as u8;
57        }
58        result
59    }

Source

fn push(&mut self, value: u8)

Examples found in repository ?

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

85    fn replace(&mut self, value: u8) -> Option<u8> {
86        if self.len == 0 {
87            self.push(value);
88            return None;
89        }
90        let result = self.maximum;
91        if value == result {
92            return Some(result);
93        }
94
95        let old = result as usize;
96        self.counts[old] -= 1;
97        if self.counts[old] == 0 {
98            let word = old / 64;
99            self.occupied[word] &= !(1 << (old % 64));
100            if self.occupied[word] == 0 {
101                self.summary &= !(1 << word);
102            }
103        }
104
105        let new = value as usize;
106        if self.counts[new] == 0 {
107            self.occupied[new / 64] |= 1 << (new % 64);
108            self.summary |= 1 << (new / 64);
109        }
110        self.counts[new] += 1;
111
112        if value > result || self.counts[old] == 0 {
113            let word = (u8::BITS - 1 - self.summary.leading_zeros()) as usize;
114            self.maximum = (word * 64 + 63 - self.occupied[word].leading_zeros() as usize) as u8;
115        }
116        Some(result)
117    }