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);
                }
            }
        }
    }
}