selen 0.15.5

//! BitSet-based domain implementation for small domains (≤128 values)
//! 
//! This module provides an ultra-fast bit representation for constraint
//! variables with small domains using bit manipulation operations.
//! Optimized for CSP domains typically found in problems like Sudoku (1-9),
//! small scheduling problems, etc.

use std::fmt::Display;

/// Maximum domain size supported by BitSetDomain (matches u128 bit width)
pub const MAX_BITSET_DOMAIN_SIZE: usize = 128;

/// State snapshot for backtracking in BitSetDomain
#[doc(hidden)]
#[derive(Clone, Debug, PartialEq)]
pub struct BitSetDomainState {
    pub mask: u128,
    pub size: usize,
}

/// Ultra-fast bit-set based domain for small domains (≤128 values)
/// 
/// Uses a single u128 as a bitmask where each bit represents a value in the domain.
/// This provides O(1) operations for most domain manipulations and is extremely
/// cache-friendly due to its compact representation.
/// 
/// **Important**: If you create a domain with more than 128 values, it will return
/// an invalid domain instead of panicking. Always check `is_invalid()` after creation
/// if you're working with dynamic ranges that might exceed the limit.
#[doc(hidden)]
#[derive(Debug, Clone)]
pub struct BitSetDomain {
    /// Bitmask where bit i represents value (min_val + i)
    mask: u128,
    /// Minimum value in the universe
    min_val: i32,
    /// Maximum value in the universe  
    max_val: i32,
    /// Size of the universe (max_val - min_val + 1)
    universe_size: usize,
}

impl Display for BitSetDomain {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut s = String::new();
        use std::fmt::Write;
        write!(s, "[").expect("writing to String should never fail");
        
        if self.is_empty() {
            write!(s, "|").expect("writing to String should never fail");
        } else {
            let mut first = true;
            let mut in_domain = true;
            
            for i in 0..self.universe_size {
                let value = self.min_val + i as i32;
                let bit_set = (self.mask & (1u128 << i)) != 0;
                
                if bit_set && in_domain {
                    if !first {
                        write!(s, ",").expect("writing to String should never fail");
                    }
                    write!(s, "{}", value).expect("writing to String should never fail");
                    first = false;
                }
                
                if !bit_set && in_domain && !first {
                    // Transition from domain to non-domain
                    write!(s, "|").expect("writing to String should never fail");
                    in_domain = false;
                    first = true;
                }
                
                if bit_set && !in_domain {
                    // Back in domain after gap
                    if !first {
                        write!(s, ",").expect("writing to String should never fail");
                    }
                    write!(s, "{}", value).expect("writing to String should never fail");
                    first = false;
                }
            }
            
            if in_domain {
                write!(s, "|").expect("writing to String should never fail");
            }
        }
        
        write!(s, "]").expect("writing to String should never fail");
        write!(f, "{}", s)
    }
}

impl BitSetDomain {
    /// Create an invalid BitSetDomain to represent error conditions
    /// 
    /// This creates a domain in an error state that can be checked with `is_invalid()`.
    /// Use this instead of panicking when domain creation fails.
    pub fn new_invalid() -> Self {
        BitSetDomain {
            mask: 0,
            min_val: 1,      // min_val > max_val indicates invalid state
            max_val: 0,      // max_val < min_val indicates invalid state  
            universe_size: 0,
        }
    }

    /// Check if this BitSetDomain is in an invalid/error state
    /// 
    /// Returns true if the domain was created due to an error condition
    /// (e.g., domain size too large, invalid parameters, etc.)
    pub fn is_invalid(&self) -> bool {
        self.max_val < self.min_val
    }

    /// Create a new BitSetDomain with all values in range [min_val, max_val]
    /// 
    /// Returns an invalid domain if the range is larger than 128 values.
    /// Check with `is_invalid()` to detect error conditions.
    pub fn new(min_val: i32, max_val: i32) -> Self {
        if min_val > max_val {
            return Self::new(max_val, min_val);
        }
        
        let universe_size = (max_val - min_val + 1) as usize;
        if universe_size > MAX_BITSET_DOMAIN_SIZE {
            return Self::new_invalid();
        }
        
        // Create mask with all bits set for the valid range
        let mask = if universe_size == 128 {
            u128::MAX
        } else {
            (1u128 << universe_size) - 1
        };
        
        BitSetDomain {
            mask,
            min_val,
            max_val,
            universe_size,
        }
    }

    /// Create a BitSetDomain from a range, returning an error for invalid inputs
    /// 
    /// This is the safe version of `new` that returns a Result instead of panicking.
    /// Use this when you need to handle domain size validation gracefully.
    pub fn try_new(min_val: i32, max_val: i32) -> Result<Self, String> {
        if min_val > max_val {
            return Self::try_new(max_val, min_val);
        }
        
        let universe_size = (max_val - min_val + 1) as usize;
        if universe_size > MAX_BITSET_DOMAIN_SIZE {
            return Err(format!("BitSetDomain supports at most {} values, got {} values in range [{}, {}]", 
                              MAX_BITSET_DOMAIN_SIZE, universe_size, min_val, max_val));
        }
        
        // Create mask with all bits set for the valid range
        let mask = if universe_size == 128 {
            u128::MAX
        } else {
            (1u128 << universe_size) - 1
        };
        
        Ok(BitSetDomain {
            mask,
            min_val,
            max_val,
            universe_size,
        })
    }
    
    /// Create a BitSetDomain from specific values
    pub fn new_from_values(values: Vec<i32>) -> Self {
        if values.is_empty() {
            return BitSetDomain {
                mask: 0,
                min_val: 0,
                max_val: -1, // Invalid range to indicate empty
                universe_size: 0,
            };
        }
        
        // Safe to unwrap since we checked values is not empty above
        let min_val = *values.iter().min().unwrap();
        let max_val = *values.iter().max().unwrap();
        
        let mut domain = Self::new(min_val, max_val);
        if domain.is_invalid() {
            return domain; // Return invalid domain if range is too large
        }
        
        domain.mask = 0; // Start empty
        
        // Set bits for specified values
        for &value in &values {
            domain.insert(value);
        }
        
        domain
    }

    /// Create a BitSetDomain from specific values, returning an error for invalid inputs
    /// 
    /// This is the safe version of `new_from_values` that returns a Result instead of panicking.
    pub fn try_new_from_values(values: Vec<i32>) -> Result<Self, String> {
        if values.is_empty() {
            return Ok(BitSetDomain {
                mask: 0,
                min_val: 0,
                max_val: -1, // Invalid range to indicate empty
                universe_size: 0,
            });
        }
        
        let min_val = *values.iter().min().ok_or("Empty values vector")?;
        let max_val = *values.iter().max().ok_or("Empty values vector")?;
        
        let mut domain = Self::try_new(min_val, max_val)?;
        domain.mask = 0; // Start empty
        
        // Set bits for specified values
        for &value in &values {
            domain.insert(value);
        }
        
        Ok(domain)
    }
    
    /// Create an empty BitSetDomain with the given universe
    /// 
    /// Returns an invalid domain if the range is too large.
    /// Check with `is_invalid()` to detect error conditions.
    pub fn new_empty(min_val: i32, max_val: i32) -> Self {
        let mut domain = Self::new(min_val, max_val);
        if domain.is_invalid() {
            return domain; // Return invalid domain if range is too large
        }
        domain.mask = 0;
        domain
    }

    /// Create an empty BitSetDomain with the given universe, returning an error for invalid inputs
    /// 
    /// This is the safe version of `new_empty` that returns a Result instead of panicking.
    pub fn try_new_empty(min_val: i32, max_val: i32) -> Result<Self, String> {
        let mut domain = Self::try_new(min_val, max_val)?;
        domain.mask = 0;
        Ok(domain)
    }
    
    /// Insert a value into the domain
    /// Returns true if the value was successfully inserted
    #[inline]
    pub fn insert(&mut self, value: i32) -> bool {
        if value < self.min_val || value > self.max_val {
            return false; // Value outside universe
        }

        let bit_pos = (value - self.min_val) as usize;
        let was_present = (self.mask & (1u128 << bit_pos)) != 0;
        self.mask |= 1u128 << bit_pos;
        !was_present
    }

    /// Remove a value from the domain
    /// Returns true if the value was present and removed
    #[inline]
    pub fn remove(&mut self, value: i32) -> bool {
        if value < self.min_val || value > self.max_val {
            return false; // Value not in universe
        }
        
        let bit_pos = (value - self.min_val) as usize;
        let was_present = (self.mask & (1u128 << bit_pos)) != 0;
        self.mask &= !(1u128 << bit_pos);
        was_present
    }
    
    /// Check if the domain contains a value
    #[inline]
    pub fn contains(&self, value: i32) -> bool {
        if value < self.min_val || value > self.max_val {
            return false;
        }
        
        let bit_pos = (value - self.min_val) as usize;
        (self.mask & (1u128 << bit_pos)) != 0
    }
    
    /// Get the size of the domain (number of values)
    #[inline]
    pub fn size(&self) -> usize {
        self.mask.count_ones() as usize
    }
    
    /// Check if the domain is empty
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.mask == 0
    }
    
    /// Check if the domain has exactly one value (is fixed)
    #[inline]
    pub fn is_fixed(&self) -> bool {
        self.mask != 0 && (self.mask & (self.mask - 1)) == 0
    }
    
    /// Get the single value if domain is fixed, None otherwise
    pub fn fixed_value(&self) -> Option<i32> {
        if self.is_fixed() {
            let bit_pos = self.mask.trailing_zeros() as usize;
            Some(self.min_val + bit_pos as i32)
        } else {
            None
        }
    }
    
    /// Get the minimum value in the domain
    #[inline]
    pub fn min(&self) -> Option<i32> {
        if self.mask == 0 {
            return None;
        }
        let first_bit = self.mask.trailing_zeros() as usize;
        Some(self.min_val + first_bit as i32)
    }

    /// Get the maximum value in the domain
    #[inline]
    pub fn max(&self) -> Option<i32> {
        if self.mask == 0 {
            return None;
        }
        let last_bit = (127 - self.mask.leading_zeros()) as usize;
        Some(self.min_val + last_bit as i32)
    }
    
    /// Remove all values from the domain
    pub fn remove_all(&mut self) {
        self.mask = 0;
    }
    
    /// Remove all values except the specified one
    pub fn remove_all_but(&mut self, value: i32) {
        if !self.contains(value) {
            self.remove_all();
            return;
        }
        
        let bit_pos = (value - self.min_val) as usize;
        self.mask = 1u128 << bit_pos;
    }
    
    /// Remove all values below the threshold
    pub fn remove_below(&mut self, threshold: i32) {
        if threshold <= self.min_val {
            return; // Nothing to remove
        }
        
        let remove_bits = if threshold > self.max_val {
            u128::MAX // Remove everything
        } else {
            let remove_count = (threshold - self.min_val) as usize;
            if remove_count >= 128 {
                u128::MAX
            } else {
                (1u128 << remove_count) - 1
            }
        };
        
        self.mask &= !remove_bits;
    }
    
    /// Remove all values above the threshold
    pub fn remove_above(&mut self, threshold: i32) {
        if threshold >= self.max_val {
            return; // Nothing to remove
        }
        
        if threshold < self.min_val {
            self.remove_all();
            return;
        }
        
        let keep_count = (threshold - self.min_val + 1) as usize;
        let keep_bits = if keep_count >= 128 {
            u128::MAX
        } else {
            (1u128 << keep_count) - 1
        };
        
        self.mask &= keep_bits;
    }
    
    /// Get an iterator over the values in the domain
    pub fn iter(&self) -> BitSetDomainIterator {
        BitSetDomainIterator {
            mask: self.mask,
            min_val: self.min_val,
        }
    }
    
    /// Convert to a vector of values (for compatibility)
    pub fn to_vec(&self) -> Vec<i32> {
        self.iter().collect()
    }
    
    /// Get the first value in the domain (lowest value)
    pub fn first(&self) -> Option<i32> {
        self.min()
    }
    
    /// Get the last value in the domain (highest value)
    pub fn last(&self) -> Option<i32> {
        self.max()
    }
    
    /// Get the universe size (total possible values)
    pub fn universe_size(&self) -> usize {
        self.universe_size
    }
    
    /// Get the minimum value in the universe
    pub fn min_universe_value(&self) -> i32 {
        self.min_val
    }
    
    /// Get the maximum value in the universe
    pub fn max_universe_value(&self) -> i32 {
        self.max_val
    }
    
    /// Set intersection - modify this domain to contain only values in both domains
    pub fn intersect_with(&mut self, other: &BitSetDomain) -> Result<(), String> {
        if self.min_val != other.min_val || self.max_val != other.max_val {
            return Err("Cannot intersect domains with different universes".to_string());
        }
        
        self.mask &= other.mask;
        Ok(())
    }
    
    /// Set union - add all values from other domain to this domain
    pub fn union_with(&mut self, other: &BitSetDomain) -> Result<(), String> {
        if self.min_val != other.min_val || self.max_val != other.max_val {
            return Err("Cannot union domains with different universes".to_string());
        }
        
        self.mask |= other.mask;
        Ok(())
    }
    
    /// Check if this domain is a subset of another domain
    pub fn is_subset_of(&self, other: &BitSetDomain) -> bool {
        if self.min_val != other.min_val || self.max_val != other.max_val {
            return false;
        }
        (self.mask & other.mask) == self.mask
    }
    
    /// Check if two domains are equal
    pub fn equals(&self, other: &BitSetDomain) -> bool {
        self.min_val == other.min_val 
            && self.max_val == other.max_val 
            && self.mask == other.mask
    }
    
    // ===== GAC OPTIMIZATION METHODS =====
    
    /// Get the union mask with another domain (for Hall set computation)
    /// Both domains must have the same universe
    pub fn union_mask(&self, other: &BitSetDomain) -> Option<u128> {
        if self.min_val != other.min_val || self.max_val != other.max_val {
            return None;
        }
        Some(self.mask | other.mask)
    }
    
    /// Remove values by mask (for efficient Hall set propagation)
    /// Returns true if any values were removed
    pub fn remove_by_mask(&mut self, remove_mask: u128) -> bool {
        let old_mask = self.mask;
        self.mask &= !remove_mask;
        self.mask != old_mask
    }
    
    /// Get the raw mask (for GAC algorithms that need direct bit manipulation)
    #[doc(hidden)]
    pub fn get_mask(&self) -> u128 {
        self.mask
    }
    
    /// Get the min_val for domain compatibility checks
    #[doc(hidden)]
    pub fn get_min_val(&self) -> i32 {
        self.min_val
    }
    
    // ===== BACKTRACKING SUPPORT =====
    
    /// Save the current state for backtracking
    #[doc(hidden)]
    pub fn save_state(&self) -> BitSetDomainState {
        BitSetDomainState {
            mask: self.mask,
            size: self.size(),
        }
    }
    
    /// Restore a previously saved state
    #[doc(hidden)]
    pub fn restore_state(&mut self, state: &BitSetDomainState) {
        self.mask = state.mask;
    }
    
    /// Get current mask for simple backtracking
    pub fn current_mask(&self) -> u128 {
        self.mask
    }
    
    /// Restore to a specific mask
    pub fn restore_mask(&mut self, mask: u128) {
        self.mask = mask;
    }
}

impl PartialEq for BitSetDomain {
    fn eq(&self, other: &Self) -> bool {
        self.equals(other)
    }
}

impl Eq for BitSetDomain {}

/// Iterator for BitSetDomain values
///
/// This iterator uses bit manipulation (`trailing_zeros`) to jump directly to the next
/// set bit instead of linearly scanning. This provides 5-10x speedup for sparse bitsets.
///
/// ## Performance
/// - Dense bitsets (most bits set): ~2x faster than linear scan
/// - Sparse bitsets (few bits set): ~10x faster than linear scan
/// - Uses CPU's native `trailing_zeros` instruction (single cycle on modern CPUs)
pub struct BitSetDomainIterator {
    /// Remaining bits to iterate over (bits are consumed as we iterate)
    mask: u128,
    /// Minimum value in the domain (offset for bit positions)
    min_val: i32,
}

impl Iterator for BitSetDomainIterator {
    type Item = i32;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        // If no bits remain, we're done
        if self.mask == 0 {
            return None;
        }

        // Find position of lowest set bit using CPU instruction
        // trailing_zeros counts the number of zeros from the right
        let offset = self.mask.trailing_zeros() as i32;

        // Calculate the actual value
        let value = self.min_val + offset;

        // Clear the lowest set bit: mask & (mask - 1)
        // This is a well-known bit manipulation trick:
        // - If mask = ...1000 (bit 3 set), mask-1 = ...0111
        // - mask & (mask-1) = ...0000 (bit 3 cleared)
        self.mask &= self.mask - 1;

        Some(value)
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        // count_ones is also a fast CPU instruction
        let count = self.mask.count_ones() as usize;
        (count, Some(count))
    }
}

impl IntoIterator for BitSetDomain {
    type Item = i32;
    type IntoIter = std::vec::IntoIter<i32>;
    
    fn into_iter(self) -> Self::IntoIter {
        self.to_vec().into_iter()
    }
}

impl<'a> IntoIterator for &'a BitSetDomain {
    type Item = i32;
    type IntoIter = BitSetDomainIterator;
    
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

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

    #[test]
    fn test_new_basic() {
        let domain = BitSetDomain::new(1, 5);
        assert_eq!(domain.size(), 5);
        assert_eq!(domain.min(), Some(1));
        assert_eq!(domain.max(), Some(5));
        assert!(!domain.is_empty());
        assert!(!domain.is_fixed());
        
        for i in 1..=5 {
            assert!(domain.contains(i));
        }
        assert!(!domain.contains(0));
        assert!(!domain.contains(6));
    }
    
    #[test]
    fn test_new_empty() {
        let domain = BitSetDomain::new_empty(1, 5);
        assert!(domain.is_empty());
        assert_eq!(domain.size(), 0);
        assert_eq!(domain.min(), None);
        assert_eq!(domain.max(), None);
        
        for i in 1..=5 {
            assert!(!domain.contains(i));
        }
    }
    
    #[test]
    fn test_new_from_values() {
        let domain = BitSetDomain::new_from_values(vec![2, 4, 6]);
        assert_eq!(domain.size(), 3);
        assert_eq!(domain.min(), Some(2));
        assert_eq!(domain.max(), Some(6));
        
        assert!(domain.contains(2));
        assert!(!domain.contains(3));
        assert!(domain.contains(4));
        assert!(!domain.contains(5));
        assert!(domain.contains(6));
        
        let values: Vec<i32> = domain.iter().collect();
        assert_eq!(values, vec![2, 4, 6]);
    }
    
    #[test]
    fn test_new_from_values_empty() {
        let domain = BitSetDomain::new_from_values(vec![]);
        assert!(domain.is_empty());
        assert_eq!(domain.size(), 0);
    }
    
    #[test]
    fn test_insert_remove() {
        let mut domain = BitSetDomain::new_empty(1, 5);
        
        // Insert values
        assert!(domain.insert(3));
        assert!(domain.insert(1));
        assert!(domain.insert(5));
        assert!(!domain.insert(3)); // Already present
        
        assert_eq!(domain.size(), 3);
        assert!(domain.contains(1));
        assert!(domain.contains(3));
        assert!(domain.contains(5));
        
        // Remove values
        assert!(domain.remove(3));
        assert!(!domain.remove(3)); // Already removed
        assert!(domain.remove(1));
        
        assert_eq!(domain.size(), 1);
        assert!(!domain.contains(1));
        assert!(!domain.contains(3));
        assert!(domain.contains(5));
        assert!(domain.is_fixed());
        assert_eq!(domain.fixed_value(), Some(5));
    }
    
    #[test]
    fn test_remove_all() {
        let mut domain = BitSetDomain::new(1, 5);
        assert!(!domain.is_empty());
        
        domain.remove_all();
        assert!(domain.is_empty());
        assert_eq!(domain.size(), 0);
        
        for i in 1..=5 {
            assert!(!domain.contains(i));
        }
    }
    
    #[test]
    fn test_remove_all_but() {
        let mut domain = BitSetDomain::new(1, 5);
        
        domain.remove_all_but(3);
        assert!(domain.is_fixed());
        assert_eq!(domain.fixed_value(), Some(3));
        assert_eq!(domain.size(), 1);
        
        assert!(!domain.contains(1));
        assert!(!domain.contains(2));
        assert!(domain.contains(3));
        assert!(!domain.contains(4));
        assert!(!domain.contains(5));
    }
    
    #[test]
    fn test_remove_all_but_missing() {
        let mut domain = BitSetDomain::new(1, 5);
        domain.remove(3);
        
        domain.remove_all_but(3); // Value not in domain
        assert!(domain.is_empty());
    }
    
    #[test]
    fn test_remove_below() {
        let mut domain = BitSetDomain::new(1, 10);
        
        domain.remove_below(5);
        assert_eq!(domain.size(), 6); // Should have {5, 6, 7, 8, 9, 10}
        assert_eq!(domain.min(), Some(5));
        assert_eq!(domain.max(), Some(10));
        
        for i in 1..5 {
            assert!(!domain.contains(i));
        }
        for i in 5..=10 {
            assert!(domain.contains(i));
        }
    }
    
    #[test]
    fn test_remove_above() {
        let mut domain = BitSetDomain::new(1, 10);
        
        domain.remove_above(5);
        assert_eq!(domain.size(), 5); // Should have {1, 2, 3, 4, 5}
        assert_eq!(domain.min(), Some(1));
        assert_eq!(domain.max(), Some(5));
        
        for i in 1..=5 {
            assert!(domain.contains(i));
        }
        for i in 6..=10 {
            assert!(!domain.contains(i));
        }
    }
    
    #[test] 
    fn test_intersect_with() {
        let mut domain1 = BitSetDomain::new(1, 5);
        let mut domain2 = BitSetDomain::new(1, 5);
        
        domain1.remove(1);
        domain1.remove(5); // domain1 = {2, 3, 4}
        
        domain2.remove(2);
        domain2.remove(4); // domain2 = {1, 3, 5}
        
        domain1.intersect_with(&domain2).unwrap();
        
        // Intersection should be {3}
        assert_eq!(domain1.size(), 1);
        assert!(domain1.contains(3));
        assert!(!domain1.contains(1));
        assert!(!domain1.contains(2));
        assert!(!domain1.contains(4));
        assert!(!domain1.contains(5));
    }
    
    #[test]
    fn test_union_with() {
        let mut domain1 = BitSetDomain::new(1, 5);
        let mut domain2 = BitSetDomain::new(1, 5);
        
        domain1.remove(3);
        domain1.remove(4);
        domain1.remove(5); // domain1 = {1, 2}
        
        domain2.remove(1);
        domain2.remove(2);
        domain2.remove(3); // domain2 = {4, 5}
        
        domain1.union_with(&domain2).unwrap();
        
        // Union should be {1, 2, 4, 5}
        assert_eq!(domain1.size(), 4);
        assert!(domain1.contains(1));
        assert!(domain1.contains(2));
        assert!(!domain1.contains(3));
        assert!(domain1.contains(4));
        assert!(domain1.contains(5));
    }
    
    #[test]
    fn test_is_subset_of() {
        // Same universe tests
        let mut domain1 = BitSetDomain::new(1, 5);
        domain1.remove(1);
        domain1.remove(3); // Now contains {2, 4, 5}
        
        let domain2 = BitSetDomain::new(1, 5); // Contains {1, 2, 3, 4, 5}
        
        let mut domain3 = BitSetDomain::new(1, 5);
        domain3.remove(1);
        domain3.remove(3);
        domain3.remove(5); // Now contains {2, 4}
        
        assert!(domain3.is_subset_of(&domain1)); // {2, 4} ⊆ {2, 4, 5}
        assert!(domain3.is_subset_of(&domain2)); // {2, 4} ⊆ {1, 2, 3, 4, 5}
        assert!(!domain2.is_subset_of(&domain3)); // {1, 2, 3, 4, 5} ⊄ {2, 4}
        
        // Different universes - should return false
        let domain4 = BitSetDomain::new(2, 6);
        assert!(!domain3.is_subset_of(&domain4)); // Different universes
    }
    
    #[test]
    fn test_iterator() {
        let domain = BitSetDomain::new_from_values(vec![1, 3, 5, 7]);
        
        let values: Vec<i32> = domain.iter().collect();
        assert_eq!(values, vec![1, 3, 5, 7]);
        
        // Test IntoIterator
        let values2: Vec<i32> = (&domain).into_iter().collect();
        assert_eq!(values2, vec![1, 3, 5, 7]);
    }
    
    #[test]
    fn test_display() {
        let mut domain = BitSetDomain::new(1, 5);
        assert_eq!(format!("{}", domain), "[1,2,3,4,5|]");
        
        domain.remove(3);
        // This might show as "[1,2|3,4,5]" or similar depending on implementation
        let display = format!("{}", domain);
        assert!(display.contains("1"));
        assert!(display.contains("2"));
        assert!(display.contains("4"));
        assert!(display.contains("5"));
        
        domain.remove_all();
        assert_eq!(format!("{}", domain), "[|]");
    }
    
    #[test]
    fn test_backtracking() {
        let mut domain = BitSetDomain::new(1, 5);
        
        // Save initial state
        let initial_state = domain.save_state();
        
        // Make changes
        domain.remove(2);
        domain.remove(4);
        assert_eq!(domain.size(), 3);
        
        // Save intermediate state
        let intermediate_state = domain.save_state();
        
        // Make more changes
        domain.remove_all_but(3);
        assert!(domain.is_fixed());
        assert_eq!(domain.fixed_value(), Some(3));
        
        // Restore to intermediate
        domain.restore_state(&intermediate_state);
        assert_eq!(domain.size(), 3);
        assert!(domain.contains(1));
        assert!(!domain.contains(2));
        assert!(domain.contains(3));
        assert!(!domain.contains(4));
        assert!(domain.contains(5));
        
        // Restore to initial
        domain.restore_state(&initial_state);
        assert_eq!(domain.size(), 5);
        for i in 1..=5 {
            assert!(domain.contains(i));
        }
    }
    
    #[test]
    fn test_sudoku_domain() {
        // Test typical Sudoku domain (1-9)
        let mut domain = BitSetDomain::new(1, 9);
        assert_eq!(domain.universe_size(), 9);
        
        // Remove some values like in constraint propagation
        domain.remove(1);
        domain.remove(5);
        domain.remove(9);
        
        assert_eq!(domain.size(), 6);
        assert_eq!(domain.min(), Some(2));
        assert_eq!(domain.max(), Some(8));
        
        let values: Vec<i32> = domain.iter().collect();
        assert_eq!(values, vec![2, 3, 4, 6, 7, 8]);
    }
    
    #[test]
    fn test_edge_cases() {
        // Single value domain
        let domain = BitSetDomain::new(42, 42);
        assert_eq!(domain.size(), 1);
        assert!(domain.is_fixed());
        assert_eq!(domain.fixed_value(), Some(42));
        assert_eq!(domain.min(), Some(42));
        assert_eq!(domain.max(), Some(42));
        
        // Large domain (near 128 limit)
        let domain = BitSetDomain::new(0, 127);
        assert_eq!(domain.universe_size(), 128);
        assert_eq!(domain.size(), 128);
    }
    
    #[test]
    fn test_too_large_domain() {
        let domain = BitSetDomain::new(0, 128); // 129 values, should return invalid domain
        assert!(domain.is_invalid(), "Domain with 129 values should be invalid");
        
        // Test that invalid domains behave predictably
        assert_eq!(domain.size(), 0);
        assert!(!domain.contains(64));
        assert!(domain.is_empty());
    }

    #[test]
    fn test_invalid_domain_behavior() {
        // Test direct creation of invalid domain
        let mut invalid = BitSetDomain::new_invalid();
        assert!(invalid.is_invalid());
        assert_eq!(invalid.size(), 0);
        assert!(invalid.is_empty());
        assert!(!invalid.contains(0));
        assert!(!invalid.contains(100));

        // Test that operations on invalid domains are safe
        assert!(!invalid.insert(5));
        assert!(!invalid.remove(5));
        assert!(invalid.is_empty());

        // Test that too-large ranges create invalid domains
        let invalid_new = BitSetDomain::new(0, 200); // 201 values
        assert!(invalid_new.is_invalid());

        let invalid_empty = BitSetDomain::new_empty(0, 200); // 201 values
        assert!(invalid_empty.is_invalid());

        let invalid_from_values = BitSetDomain::new_from_values((0..150).collect()); // 150 values
        assert!(invalid_from_values.is_invalid());

        // Test that valid ranges still work
        let valid = BitSetDomain::new(0, 127); // Exactly 128 values
        assert!(!valid.is_invalid());
        assert_eq!(valid.size(), 128);
    }

    #[test]
    fn test_safe_constructors() {
        // Test successful cases
        let domain = BitSetDomain::try_new(1, 5).expect("Should create valid domain");
        assert_eq!(domain.size(), 5);
        assert!(domain.contains(1));
        assert!(domain.contains(5));

        let domain = BitSetDomain::try_new_empty(1, 5).expect("Should create valid empty domain");
        assert_eq!(domain.size(), 0);

        let domain = BitSetDomain::try_new_from_values(vec![2, 4, 6]).expect("Should create valid domain from values");
        assert_eq!(domain.size(), 3);
        assert!(domain.contains(2));
        assert!(domain.contains(4));
        assert!(domain.contains(6));

        // Test maximum allowed size (128 values)
        let domain = BitSetDomain::try_new(0, 127).expect("Should create domain with max size");
        assert_eq!(domain.size(), 128);

        // Test error cases
        let result = BitSetDomain::try_new(0, 128); // 129 values
        assert!(result.is_err());
        assert!(result.unwrap_err().contains("BitSetDomain supports at most 128 values"));

        let result = BitSetDomain::try_new_empty(0, 128); // 129 values
        assert!(result.is_err());

        // Test that large range in values also fails
        let large_values: Vec<i32> = (0..129).collect();
        let result = BitSetDomain::try_new_from_values(large_values);
        assert!(result.is_err());
        
        // Test empty values works
        let domain = BitSetDomain::try_new_from_values(vec![]).expect("Empty values should work");
        assert_eq!(domain.size(), 0);
    }
    
    #[test]
    fn test_performance_characteristics() {
        // Test that operations are fast on typical CSP domains
        let mut domain = BitSetDomain::new(1, 20);
        
        // Rapid insertions and removals
        for i in 1..=20 {
            if i % 2 == 0 {
                domain.remove(i);
            }
        }
        
        assert_eq!(domain.size(), 10); // 10 odd numbers
        
        // Fast membership testing
        for i in 1..=20 {
            let expected = i % 2 == 1;
            assert_eq!(domain.contains(i), expected);
        }
        
        // Fast iteration
        let values: Vec<i32> = domain.iter().collect();
        assert_eq!(values.len(), 10);
        
        // All operations should be essentially O(1)
    }

    #[test]
    fn test_u128_upgrade_comprehensive() {
        // Test that all operations work correctly with u128 bit operations
        
        // Test small domain (typical Sudoku case)
        let mut small_domain = BitSetDomain::new(1, 9);
        assert_eq!(small_domain.size(), 9);
        assert_eq!(small_domain.to_vec(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
        
        // Test basic operations
        assert!(small_domain.remove(5));
        assert!(!small_domain.contains(5));
        assert_eq!(small_domain.size(), 8);
        
        // Test medium domain (64+ values to test u128 beyond u64 range)
        let mut medium_domain = BitSetDomain::new(1, 80);
        assert_eq!(medium_domain.size(), 80);
        
        // Remove some values in the higher range (>64)
        assert!(medium_domain.remove(70));
        assert!(medium_domain.remove(75));
        assert!(!medium_domain.contains(70));
        assert!(!medium_domain.contains(75));
        assert_eq!(medium_domain.size(), 78);
        
        // Test large domain (near 128 limit)
        let mut large_domain = BitSetDomain::new(1, 120);
        assert_eq!(large_domain.size(), 120);
        
        // Test operations on high-bit values
        assert!(large_domain.contains(100));
        assert!(large_domain.contains(120));
        assert!(large_domain.remove(100));
        assert!(large_domain.remove(120));
        assert!(!large_domain.contains(100));
        assert!(!large_domain.contains(120));
        assert_eq!(large_domain.size(), 118);
        
        // Test mask operations work with u128
        let mask = large_domain.get_mask();
        assert_ne!(mask, 0u128);
        
        // Test intersection with different domains
        let mut domain1 = BitSetDomain::new(1, 100);
        let mut domain2 = BitSetDomain::new(1, 100);
        domain2.remove(50);
        
        assert!(domain1.intersect_with(&domain2).is_ok());
        assert!(!domain1.contains(50));
        assert_eq!(domain1.size(), 99);
    }
    
    #[test]
    fn test_bit_operations_u128() {
        // Test that bit operations work correctly across the full u128 range
        let mut domain = BitSetDomain::new(0, 127); // Full 128-bit range
        
        // Test operations on bit positions > 64
        assert!(domain.contains(100));
        assert!(domain.contains(127));
        
        domain.remove(100);
        domain.remove(127);
        
        assert!(!domain.contains(100));
        assert!(!domain.contains(127));
        assert_eq!(domain.size(), 126);
        
        // Test mask operations
        let mask = domain.get_mask();
        assert_eq!(mask.count_ones() as usize, 126);
        
        // Test remove_above/remove_below with high values
        domain.remove_above(100);
        assert!(!domain.contains(101));
        assert!(!domain.contains(126));
        assert!(domain.contains(99));
        
        domain.remove_below(50);
        assert!(!domain.contains(49));
        assert!(!domain.contains(1));
        assert!(domain.contains(50));
        
        // Verify final state
        let values: Vec<i32> = domain.iter().collect();
        assert_eq!(values, (50..=99).filter(|&x| x != 100).collect::<Vec<_>>());
    }
    
    #[test]
    fn test_gac_mask_operations_u128() {
        // Test GAC-specific mask operations with u128
        let domain1 = BitSetDomain::new(1, 80);
        let domain2 = BitSetDomain::new(1, 80);
        
        // Test union_mask
        let union_mask = domain1.union_mask(&domain2).unwrap();
        assert_eq!(union_mask.count_ones() as usize, 80);
        
        // Test remove_by_mask
        let mut domain3 = BitSetDomain::new(1, 80);
        let remove_mask = (1u128 << 10) | (1u128 << 20) | (1u128 << 70); // Remove values 11, 21, 71
        assert!(domain3.remove_by_mask(remove_mask));
        assert!(!domain3.contains(11));
        assert!(!domain3.contains(21));
        assert!(!domain3.contains(71));
        assert_eq!(domain3.size(), 77);
    }
    
    #[test]
    fn test_sudoku_specific_operations() {
        // Test operations that would be used in Sudoku solving
        let mut domain = BitSetDomain::new(1, 9);
        
        // Simulate constraint propagation
        domain.remove(5); // Remove a value
        assert_eq!(domain.size(), 8);
        
        // Test intersection (common in alldiff constraints)
        let mut other_domain = BitSetDomain::new(1, 9);
        other_domain.remove(3);
        other_domain.remove(7);
        
        assert!(domain.intersect_with(&other_domain).is_ok());
        assert!(!domain.contains(3));
        assert!(!domain.contains(5));
        assert!(!domain.contains(7));
        assert_eq!(domain.size(), 6);
        
        // Test that all remaining values are correct
        let values: Vec<i32> = domain.iter().collect();
        assert_eq!(values, vec![1, 2, 4, 6, 8, 9]);
        
        // Test fixing to a single value
        domain.remove_all_but(4);
        assert!(domain.is_fixed());
        assert_eq!(domain.fixed_value(), Some(4));
        assert_eq!(domain.size(), 1);
    }
}