use crate::intrusive_list::{IntrusiveList, ListLinks};

pub struct RunQueueTag;

pub struct RunQueue {
    bitmap: [u64; 4],
    lists: [IntrusiveList; 256],
}

impl RunQueue {
    pub const fn new() -> Self {
        Self {
            bitmap: [0; 4],
            lists: [IntrusiveList::empty(); 256],
        }
    }

    pub fn enqueue(&mut self, id: u32, priority: u8, store: &mut impl ListLinks<RunQueueTag>) {
        let p = priority as usize;
        self.lists[p].append(id, store);
        self.bitmap[p / 64] |= 1u64 << (p % 64);
    }

    pub fn dequeue_highest(
        &mut self,
        store: &mut impl ListLinks<RunQueueTag>,
    ) -> Option<(u32, u8)> {
        let (word_idx, bit) = (0..4).rev().find_map(|w| match self.bitmap[w] {
            0 => None,
            bits => Some((w, 63 - bits.leading_zeros() as usize)),
        })?;

        let priority = word_idx * 64 + bit;
        let head = self.lists[priority].pop_head(store)?;

        if self.lists[priority].is_empty() {
            self.bitmap[word_idx] &= !(1u64 << bit);
        }

        Some((head, priority as u8))
    }

    pub fn remove(&mut self, id: u32, priority: u8, store: &mut impl ListLinks<RunQueueTag>) {
        let p = priority as usize;
        if self.lists[p].unlink(id, store) && self.lists[p].is_empty() {
            self.bitmap[p / 64] &= !(1u64 << (p % 64));
        }
    }

    pub fn is_empty(&self) -> bool {
        self.bitmap[0] == 0 && self.bitmap[1] == 0 && self.bitmap[2] == 0 && self.bitmap[3] == 0
    }
}