reactive-signals 0.1.0-alpha.4

use std::fmt::Debug;

pub struct FlagArr {
    pub(super) arr: [u32; SIZE],
    pub(super) len: u32,
}

/// There can be at most 2^16 - 1 nodes
/// Each u32 stores flags for 32 entries (2^5)
/// There's none flag for every 16 nodes (2^4)
/// That makes for a size of 2^7, which is 128 u32's or 512 bytes
const SIZE: usize = 128;
const BITS: usize = u32::BITS as usize;

impl FlagArr {
    #[inline]
    pub(crate) fn set(&mut self, index: usize) {
        let slot = index / BITS;
        let idx = index % BITS;

        if slot >= self.len as usize {
            self.len = slot as u32 + 1;
        }

        self.arr[slot] |= OR_MASK[idx];
    }

    #[inline]
    pub(crate) fn take_last(&mut self) -> Option<usize> {
        for slot in (0..(self.len as usize)).rev() {
            let num = self.arr[slot];
            if num != 0 {
                let idx = BITS - num.trailing_zeros() as usize - 1;
                self.arr[slot] &= AND_MASK[idx];
                self.len = slot as u32 + 1;
                return Some(slot * BITS + idx);
            }
        }
        self.len = 0;
        None
    }

    #[inline]
    pub(crate) fn init(&mut self) {
        debug_assert!(
            self.len == 0,
            "initializing FlagVec but it already contains {} flag slots",
            self.len
        );
    }

    #[inline]
    pub(crate) fn reset(&mut self) {
        for i in 0..SIZE {
            self.arr[i] = 0;
        }
        self.len = 0
    }
}

impl Default for FlagArr {
    fn default() -> Self {
        Self {
            arr: [0; SIZE],
            len: 0,
        }
    }
}

impl Debug for FlagArr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let list = (0..(self.len as usize))
            .map(|i| format!("{}", self.arr[i]))
            .collect::<Vec<_>>()
            .join(", ");
        write!(f, "[{list}]")
    }
}
const OR_MASK: [u32; 32] = [
    0b1000_0000_0000_0000_0000_0000_0000_0000,
    0b0100_0000_0000_0000_0000_0000_0000_0000,
    0b0010_0000_0000_0000_0000_0000_0000_0000,
    0b0001_0000_0000_0000_0000_0000_0000_0000,
    0b0000_1000_0000_0000_0000_0000_0000_0000,
    0b0000_0100_0000_0000_0000_0000_0000_0000,
    0b0000_0010_0000_0000_0000_0000_0000_0000,
    0b0000_0001_0000_0000_0000_0000_0000_0000,
    0b0000_0000_1000_0000_0000_0000_0000_0000,
    0b0000_0000_0100_0000_0000_0000_0000_0000,
    0b0000_0000_0010_0000_0000_0000_0000_0000,
    0b0000_0000_0001_0000_0000_0000_0000_0000,
    0b0000_0000_0000_1000_0000_0000_0000_0000,
    0b0000_0000_0000_0100_0000_0000_0000_0000,
    0b0000_0000_0000_0010_0000_0000_0000_0000,
    0b0000_0000_0000_0001_0000_0000_0000_0000,
    0b0000_0000_0000_0000_1000_0000_0000_0000,
    0b0000_0000_0000_0000_0100_0000_0000_0000,
    0b0000_0000_0000_0000_0010_0000_0000_0000,
    0b0000_0000_0000_0000_0001_0000_0000_0000,
    0b0000_0000_0000_0000_0000_1000_0000_0000,
    0b0000_0000_0000_0000_0000_0100_0000_0000,
    0b0000_0000_0000_0000_0000_0010_0000_0000,
    0b0000_0000_0000_0000_0000_0001_0000_0000,
    0b0000_0000_0000_0000_0000_0000_1000_0000,
    0b0000_0000_0000_0000_0000_0000_0100_0000,
    0b0000_0000_0000_0000_0000_0000_0010_0000,
    0b0000_0000_0000_0000_0000_0000_0001_0000,
    0b0000_0000_0000_0000_0000_0000_0000_1000,
    0b0000_0000_0000_0000_0000_0000_0000_0100,
    0b0000_0000_0000_0000_0000_0000_0000_0010,
    0b0000_0000_0000_0000_0000_0000_0000_0001,
];

const AND_MASK: [u32; 32] = [
    0b0111_1111_1111_1111_1111_1111_1111_1111,
    0b1011_1111_1111_1111_1111_1111_1111_1111,
    0b1101_1111_1111_1111_1111_1111_1111_1111,
    0b1110_1111_1111_1111_1111_1111_1111_1111,
    0b1111_0111_1111_1111_1111_1111_1111_1111,
    0b1111_1011_1111_1111_1111_1111_1111_1111,
    0b1111_1101_1111_1111_1111_1111_1111_1111,
    0b1111_1110_1111_1111_1111_1111_1111_1111,
    0b1111_1111_0111_1111_1111_1111_1111_1111,
    0b1111_1111_1011_1111_1111_1111_1111_1111,
    0b1111_1111_1101_1111_1111_1111_1111_1111,
    0b1111_1111_1110_1111_1111_1111_1111_1111,
    0b1111_1111_1111_0111_1111_1111_1111_1111,
    0b1111_1111_1111_1011_1111_1111_1111_1111,
    0b1111_1111_1111_1101_1111_1111_1111_1111,
    0b1111_1111_1111_1110_1111_1111_1111_1111,
    0b1111_1111_1111_1111_0111_1111_1111_1111,
    0b1111_1111_1111_1111_1011_1111_1111_1111,
    0b1111_1111_1111_1111_1101_1111_1111_1111,
    0b1111_1111_1111_1111_1110_1111_1111_1111,
    0b1111_1111_1111_1111_1111_0111_1111_1111,
    0b1111_1111_1111_1111_1111_1011_1111_1111,
    0b1111_1111_1111_1111_1111_1101_1111_1111,
    0b1111_1111_1111_1111_1111_1110_1111_1111,
    0b1111_1111_1111_1111_1111_1111_0111_1111,
    0b1111_1111_1111_1111_1111_1111_1011_1111,
    0b1111_1111_1111_1111_1111_1111_1101_1111,
    0b1111_1111_1111_1111_1111_1111_1110_1111,
    0b1111_1111_1111_1111_1111_1111_1111_0111,
    0b1111_1111_1111_1111_1111_1111_1111_1011,
    0b1111_1111_1111_1111_1111_1111_1111_1101,
    0b1111_1111_1111_1111_1111_1111_1111_1110,
];

#[test]
fn test_flagvec() {
    let mut v = FlagArr::default();

    v.set(0);

    assert_eq!(v.arr[0], 0b1000_0000_0000_0000_0000_0000_0000_0000);

    v.set(31);

    assert_eq!(v.arr[0], 0b1000_0000_0000_0000_0000_0000_0000_0001);
    assert_eq!(v.len, 1);

    v.set(32);
    assert_eq!(v.arr[0], 0b1000_0000_0000_0000_0000_0000_0000_0001);
    assert_eq!(v.len, 2);

    assert_eq!(v.arr[1], 0b1000_0000_0000_0000_0000_0000_0000_0000);

    v.set(38);
    assert_eq!(v.arr[1], 0b1000_0010_0000_0000_0000_0000_0000_0000);

    v.set(62);
    assert_eq!(v.arr[1], 0b1000_0010_0000_0000_0000_0000_0000_0010);

    assert_eq!(v.take_last(), Some(62));
    assert_eq!(v.take_last(), Some(38));
    assert_eq!(v.take_last(), Some(32));
    assert_eq!(v.take_last(), Some(31));
    assert_eq!(v.take_last(), Some(0));
    assert_eq!(v.take_last(), None);
    assert_eq!(v.len, 0);

    for i in 0..1024 {
        v.set(i);
        assert_eq!(v.take_last(), Some(i));
        assert_eq!(v.take_last(), None);
    }
    v.reset();
    assert_eq!(v.len, 0);

    v.init();
}