layered-bitset 0.1.3

Bit set implementation using layered structure
Documentation 
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

use crate::{BitSet, BitSetMut};

#[derive(Debug)]
pub struct Layered<T, B, const N: usize> {
    top: T,
    bottom: [B; N],
}

impl<T, B, const N: usize> Default for Layered<T, B, N>
where
    T: Default + BitSet,
    B: Default + BitSet,
{
    fn default() -> Self {
        Self::new()
    }
}

impl<T, B, const N: usize> Layered<T, B, N>
where
    T: BitSet,
    B: BitSet,
{
    fn new() -> Self
    where
        T: Default,
        B: Default,
    {
        assert_eq!(T::UPPER_BOUND, N as u32);
        assert_eq!(T::UPPER_BOUND as usize, N);

        use core::mem::MaybeUninit;
        let bottom = unsafe {
            let mut array: [MaybeUninit<B>; N] = MaybeUninit::uninit().assume_init();
            for item in &mut array {
                // Leaks all previously written elements on panic. It is safe though.
                core::ptr::write(item, MaybeUninit::new(B::default()));
            }
            (&array as *const _ as *const [B; N]).read()
        };

        Layered {
            top: T::default(),
            bottom,
        }
    }
}

impl<T, B, const N: usize> BitSet for Layered<T, B, N>
where
    T: BitSet,
    B: BitSet,
{
    const UPPER_BOUND: u32 = B::UPPER_BOUND * N as u32;

    fn get(&self, index: u32) -> bool {
        assert!(index < Self::UPPER_BOUND);

        let t = index / B::UPPER_BOUND;
        let b = index % B::UPPER_BOUND;

        self.bottom[t as usize].get(b)
    }

    fn find_set(&self, lower_bound: u32) -> Option<u32> {
        assert!(lower_bound < Self::UPPER_BOUND);

        let t = lower_bound / B::UPPER_BOUND;
        let b = lower_bound % B::UPPER_BOUND;

        if b == 0 {
            let t = self.top.find_set(t)?;
            let b = self.bottom[t as usize].find_set(0)?;
            Some(t * B::UPPER_BOUND + b)
        } else {
            if self.top.get(t) {
                if let Some(b) = self.bottom[t as usize].find_set(b) {
                    return Some(t * B::UPPER_BOUND + b);
                }
            }

            let t = self.top.find_set(t + 1)?;
            let b = self.bottom[t as usize].find_set(0)?;
            Some(t * B::UPPER_BOUND + b)
        }
    }
}

impl<T, B, const N: usize> BitSetMut for Layered<T, B, N>
where
    T: BitSetMut,
    B: BitSetMut,
{
    fn set(&mut self, index: u32, bit: bool) {
        assert!(index < Self::UPPER_BOUND);
        let t = index / B::UPPER_BOUND;
        let u = index % B::UPPER_BOUND;

        if bit {
            if !self.top.get(t) {
                self.top.set(t, true);
            }
            self.bottom[t as usize].set(u, true)
        } else {
            if self.top.get(t) {
                self.bottom[t as usize].set(u, false);
                if self.bottom[t as usize].is_empty() {
                    self.top.set(t, false);
                }
            }
        }
    }
}