selen 0.15.5

use std::collections::VecDeque;

use crate::constraints::props::PropId;

/// Collection of propagators scheduled to be run.
///
/// This implementation uses a bit vector for O(1) membership testing instead of
/// a HashSet, providing better cache locality and lower overhead. The bit vector
/// approach is ~2-3x faster than HashSet for typical propagator counts.
///
/// ## Performance Characteristics
///
/// - `schedule()`: O(1) - single bit check + VecDeque push
/// - `pop()`: O(1) - VecDeque pop + single bit clear
/// - Memory: O(n/8) bytes for bit vector where n = max propagator count
///
/// ## Why BitVec instead of HashSet?
///
/// 1. **Faster operations**: Bit operations are cheaper than hash table lookups
/// 2. **Better cache locality**: Contiguous memory vs scattered allocations
/// 3. **Predictable performance**: No hash collisions or resizing
/// 4. **Lower memory overhead**: 1 bit per propagator vs ~24 bytes per entry in HashSet
#[derive(Debug)]
pub struct Agenda {
    /// Queue of scheduled propagators in FIFO order
    q: VecDeque<PropId>,
    /// Bit vector tracking which propagators are currently scheduled
    /// Each bit represents whether propagator with that ID is in the queue
    scheduled: Vec<u64>,
}

impl Agenda {
    /// Initialize agenda and schedule the provided propagators.
    pub fn with_props(ps: impl Iterator<Item = PropId>) -> Self {
        let mut agenda = Self::default();

        for p in ps {
            agenda.schedule(p);
        }

        agenda
    }

    /// Schedule a propagator if it is not already on the agenda.
    #[inline]
    pub fn schedule(&mut self, p: PropId) {
        // Avoid scheduling a propagator already on the agenda using bit vector
        if !self.is_scheduled(p) {
            // Schedule propagators in FIFO order to avoid starvation
            self.q.push_back(p);

            // Mark as scheduled in bit vector
            self.set_scheduled(p, true);
        }
    }

    /// Acquire handle to next propagator to run, removing it from the [`Agenda`].
    #[inline]
    pub fn pop(&mut self) -> Option<PropId> {
        // Pop scheduled propagators in FIFO order to avoid starvation
        let p = self.q.pop_front()?;

        // Clear scheduled bit
        self.set_scheduled(p, false);

        Some(p)
    }

    /// Check if a propagator is currently scheduled.
    #[inline]
    fn is_scheduled(&self, p: PropId) -> bool {
        let idx = p.0;
        let word_idx = idx / 64;
        let bit_idx = idx % 64;

        // Check if the bit vector is large enough
        if word_idx >= self.scheduled.len() {
            return false;
        }

        // Check the bit
        (self.scheduled[word_idx] & (1u64 << bit_idx)) != 0
    }

    /// Set the scheduled status of a propagator.
    #[inline]
    fn set_scheduled(&mut self, p: PropId, scheduled: bool) {
        let idx = p.0;
        let word_idx = idx / 64;
        let bit_idx = idx % 64;

        // Grow bit vector if needed
        if word_idx >= self.scheduled.len() {
            self.scheduled.resize(word_idx + 1, 0);
        }

        // Set or clear the bit
        if scheduled {
            self.scheduled[word_idx] |= 1u64 << bit_idx;
        } else {
            self.scheduled[word_idx] &= !(1u64 << bit_idx);
        }
    }
}

impl Default for Agenda {
    fn default() -> Self {
        Self {
            q: VecDeque::new(),
            // Start with capacity for 64 propagators (1 u64 word)
            // Will grow automatically as needed
            scheduled: Vec::with_capacity(1),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_agenda_basic() {
        let mut agenda = Agenda::default();

        // Schedule a propagator
        agenda.schedule(PropId(0));
        assert!(agenda.is_scheduled(PropId(0)));

        // Scheduling again should be idempotent
        agenda.schedule(PropId(0));
        assert_eq!(agenda.q.len(), 1);

        // Pop should return the propagator and clear the bit
        let p = agenda.pop();
        assert_eq!(p, Some(PropId(0)));
        assert!(!agenda.is_scheduled(PropId(0)));

        // Queue should be empty
        assert_eq!(agenda.pop(), None);
    }

    #[test]
    fn test_agenda_multiple_propagators() {
        let mut agenda = Agenda::default();

        // Schedule multiple propagators
        for i in 0..10 {
            agenda.schedule(PropId(i));
        }

        // All should be scheduled
        for i in 0..10 {
            assert!(agenda.is_scheduled(PropId(i)));
        }

        // Pop them in FIFO order
        for i in 0..10 {
            assert_eq!(agenda.pop(), Some(PropId(i)));
        }

        // Queue should be empty
        assert_eq!(agenda.pop(), None);
    }

    #[test]
    fn test_agenda_with_props() {
        let props = vec![PropId(5), PropId(10), PropId(15)];
        let mut agenda = Agenda::with_props(props.into_iter());

        assert_eq!(agenda.pop(), Some(PropId(5)));
        assert_eq!(agenda.pop(), Some(PropId(10)));
        assert_eq!(agenda.pop(), Some(PropId(15)));
        assert_eq!(agenda.pop(), None);
    }

    #[test]
    fn test_agenda_large_ids() {
        let mut agenda = Agenda::default();

        // Test with large propagator IDs (requires bit vector growth)
        agenda.schedule(PropId(100));
        agenda.schedule(PropId(200));
        agenda.schedule(PropId(300));

        assert!(agenda.is_scheduled(PropId(100)));
        assert!(agenda.is_scheduled(PropId(200)));
        assert!(agenda.is_scheduled(PropId(300)));

        // Should grow bit vector to accommodate
        assert!(agenda.scheduled.len() >= 5); // 300 / 64 = 4.6, so needs at least 5 words

        assert_eq!(agenda.pop(), Some(PropId(100)));
        assert_eq!(agenda.pop(), Some(PropId(200)));
        assert_eq!(agenda.pop(), Some(PropId(300)));
    }

    #[test]
    fn test_agenda_duplicate_scheduling() {
        let mut agenda = Agenda::default();

        agenda.schedule(PropId(42));
        agenda.schedule(PropId(42)); // Duplicate
        agenda.schedule(PropId(42)); // Another duplicate

        // Should only be in queue once
        assert_eq!(agenda.q.len(), 1);
        assert_eq!(agenda.pop(), Some(PropId(42)));
        assert_eq!(agenda.pop(), None);
    }

    #[test]
    fn test_agenda_interleaved_operations() {
        let mut agenda = Agenda::default();

        agenda.schedule(PropId(1));
        agenda.schedule(PropId(2));
        assert_eq!(agenda.pop(), Some(PropId(1)));

        agenda.schedule(PropId(3));
        assert_eq!(agenda.pop(), Some(PropId(2)));
        assert_eq!(agenda.pop(), Some(PropId(3)));

        agenda.schedule(PropId(1)); // Re-schedule previously popped
        assert_eq!(agenda.pop(), Some(PropId(1)));
    }

    #[test]
    fn test_agenda_bit_boundaries() {
        let mut agenda = Agenda::default();

        // Test around 64-bit word boundaries
        agenda.schedule(PropId(63));  // Last bit of first word
        agenda.schedule(PropId(64));  // First bit of second word
        agenda.schedule(PropId(127)); // Last bit of second word
        agenda.schedule(PropId(128)); // First bit of third word

        assert!(agenda.is_scheduled(PropId(63)));
        assert!(agenda.is_scheduled(PropId(64)));
        assert!(agenda.is_scheduled(PropId(127)));
        assert!(agenda.is_scheduled(PropId(128)));

        assert_eq!(agenda.pop(), Some(PropId(63)));
        assert_eq!(agenda.pop(), Some(PropId(64)));
        assert_eq!(agenda.pop(), Some(PropId(127)));
        assert_eq!(agenda.pop(), Some(PropId(128)));
    }
}