use std::collections::HashMap;

pub struct SlotMap<T> {
    bitmap: u64,
    map: HashMap<u32, T>,
}

impl<T> SlotMap<T> {
    pub fn new() -> Self {
        Self {
            bitmap: u64::MAX,
            map: HashMap::new(),
        }
    }

    pub fn insert(&mut self, value: T) -> Option<u32> {
        let slot = self.get_free_slot()?;
        self.map.insert(slot, value);
        self.use_slot(slot);

        Some(slot)
    }

    pub fn remove(&mut self, slot: u32) -> Option<T> {
        let value = self.map.remove(&slot)?;
        self.release_slot(slot);

        Some(value)
    }

    pub fn get(&self, slot: u32) -> Option<&T> {
        self.map.get(&slot)
    }

    pub fn get_mut(&mut self, slot: u32) -> Option<&mut T> {
        self.map.get_mut(&slot)
    }

    fn get_free_slot(&self) -> Option<u32> {
        let leading_zeros = self.bitmap.leading_zeros();

        if leading_zeros > 63 {
            None
        } else {
            Some(63 - leading_zeros)
        }
    }

    fn use_slot(&mut self, slot: u32) {
        let mask = u64::MAX;
        println!("{:0b}", self.bitmap);
        self.bitmap &= !(1 << slot) & mask;
    }

    fn release_slot(&mut self, slot: u32) {
        self.bitmap |= 1 << slot;
    }
}

#[test]
fn releases_a_slot_after_removal() {
    let mut slot_map = SlotMap::new();

    assert_eq!(slot_map.insert(1), Some(63));
    assert_eq!(slot_map.insert(2), Some(62));
    assert_eq!(slot_map.insert(3), Some(61));

    assert_eq!(slot_map.remove(&62), Some(2));

    assert_eq!(slot_map.insert(4), Some(62));
    assert_eq!(slot_map.insert(5), Some(60));
}

#[test]
fn uses_all_available_slots() {
    let mut slot_map = SlotMap::new();

    for x in 0..64 {
        assert_eq!(slot_map.insert(0), Some(63 - x));
    }

    assert_eq!(slot_map.insert(0), None);
    assert_eq!(slot_map.remove(&43), Some(0));
    assert_eq!(slot_map.insert(0), Some(43));
}