ppflib 0.1.0

//! State-space ideals in the PPF framework
//!
//! Implements state-space ideals IS(n) = ((n), S(n)) which combine
//! the principal ideal generated by n with its factorization state space.
//! These ideals distinguish IS(n) from IS(-n) despite having the same
//! underlying factorization sets.

use crate::core::{FactorizationStateSpace, FactorizationError};
use std::fmt;
use std::collections::HashSet;
use thiserror::Error;
use serde::{Deserialize, Serialize};

/// Errors that can occur with state-space ideals
#[derive(Error, Debug, Clone, PartialEq)]
pub enum StateSpaceIdealError {
    /// Factorization error occurred
    #[error("Factorization error: {0}")]
    FactorizationError(#[from] FactorizationError),
    /// Invalid ideal operation
    #[error("Invalid ideal operation: {0}")]
    InvalidOperation(String),
    /// Ideals are incompatible for the operation
    #[error("Incompatible ideals for operation")]
    IncompatibleIdeals,
}

/// State-space ideal IS(n) = ((n), S(n))
/// 
/// Combines the principal ideal (n) with the factorization state space S(n).
/// The key property is that IS(n) ≠ IS(-n) even though S(n) and S(-n) 
/// contain the same factorization sets.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct StateSpaceIdeal {
    /// The generator of the principal ideal
    generator: i64,
    /// The factorization state space S(n)
    state_space: FactorizationStateSpace,
    /// Cached ideal elements up to a bound
    cached_elements: Option<Vec<i64>>,
}

impl StateSpaceIdeal {
    /// Create a new state-space ideal IS(n)
    /// 
    /// # Arguments
    /// * `n` - The generator of the ideal
    /// 
    /// # Returns
    /// * `Ok(StateSpaceIdeal)` - The state-space ideal IS(n)
    /// * `Err(StateSpaceIdealError)` - If creation fails
    pub fn new(n: i64) -> Result<Self, StateSpaceIdealError> {
        let state_space = FactorizationStateSpace::new(n)?;
        
        Ok(StateSpaceIdeal {
            generator: n,
            state_space,
            cached_elements: None,
        })
    }

    /// Get the generator of the principal ideal
    pub fn generator(&self) -> i64 {
        self.generator
    }

    /// Get the factorization state space S(n)
    pub fn state_space(&self) -> &FactorizationStateSpace {
        &self.state_space
    }

    /// Get the dimension of the state space
    pub fn dimension(&self) -> usize {
        self.state_space.size()
    }

    /// Check if this is a quantum ideal (negative generator)
    pub fn is_quantum(&self) -> bool {
        self.generator < 0
    }

    /// Check if this is a classical ideal (positive generator)
    pub fn is_classical(&self) -> bool {
        self.generator > 0
    }

    /// Generate elements of the principal ideal (n) up to a bound
    /// 
    /// # Arguments
    /// * `bound` - Maximum absolute value of elements to generate
    /// 
    /// # Returns
    /// * Vector of ideal elements nk where |nk| ≤ bound
    pub fn principal_ideal_elements(&mut self, bound: i64) -> &[i64] {
        if self.cached_elements.is_none() || self.cached_elements.as_ref().unwrap().is_empty() {
            let mut elements = Vec::new();
            let n = self.generator;
            
            if n == 0 {
                elements.push(0);
            } else {
                let max_k = bound / n.abs();
                for k in -max_k..=max_k {
                    if k != 0 {
                        elements.push(n * k);
                    }
                }
                elements.push(n); // Ensure generator is included
                elements.sort_by_key(|&x| x.abs());
                elements.dedup();
            }
            
            self.cached_elements = Some(elements);
        }
        
        self.cached_elements.as_ref().unwrap()
    }

    /// Check if an element belongs to the principal ideal (n)
    pub fn contains(&self, element: i64) -> bool {
        if self.generator == 0 {
            element == 0
        } else {
            element % self.generator == 0
        }
    }

    /// Compute the product of two state-space ideals
    /// IS(a) · IS(b) = IS(ab)
    /// 
    /// This operation models quantum collapse when both ideals are quantum.
    pub fn multiply(&self, other: &StateSpaceIdeal) -> Result<StateSpaceIdeal, StateSpaceIdealError> {
        let product_generator = self.generator.checked_mul(other.generator)
            .ok_or_else(|| StateSpaceIdealError::InvalidOperation("Product overflow".to_string()))?;
        
        StateSpaceIdeal::new(product_generator)
    }

    /// Compute the sum of two state-space ideals
    /// IS(a) + IS(b) = IS(gcd(a,b))
    pub fn add(&self, other: &StateSpaceIdeal) -> Result<StateSpaceIdeal, StateSpaceIdealError> {
        let gcd = gcd(self.generator.abs() as u64, other.generator.abs() as u64);
        
        // Preserve quantum nature if both are quantum
        let sum_generator = if self.is_quantum() && other.is_quantum() {
            -(gcd as i64)
        } else {
            gcd as i64
        };
        
        StateSpaceIdeal::new(sum_generator)
    }

    /// Compute the intersection of two state-space ideals
    /// IS(a) ∩ IS(b) = IS(lcm(a,b))
    pub fn intersect(&self, other: &StateSpaceIdeal) -> Result<StateSpaceIdeal, StateSpaceIdealError> {
        let lcm_val = lcm(self.generator.abs() as u64, other.generator.abs() as u64);
        
        // Check for overflow
        if lcm_val > i64::MAX as u64 {
            return Err(StateSpaceIdealError::InvalidOperation("LCM overflow".to_string()));
        }
        
        // Preserve quantum nature if either is quantum
        let intersection_generator = if self.is_quantum() || other.is_quantum() {
            -(lcm_val as i64)
        } else {
            lcm_val as i64
        };
        
        StateSpaceIdeal::new(intersection_generator)
    }

    /// Check if this ideal contains another ideal
    /// IS(a) ⊇ IS(b) iff a | b
    pub fn contains_ideal(&self, other: &StateSpaceIdeal) -> bool {
        if self.generator == 0 {
            other.generator == 0
        } else {
            other.generator % self.generator == 0
        }
    }

    /// Get the quotient structure IS(n)/IS(m) when m | n
    pub fn quotient(&self, other: &StateSpaceIdeal) -> Result<QuotientStructure, StateSpaceIdealError> {
        if !self.contains_ideal(other) {
            return Err(StateSpaceIdealError::InvalidOperation(
                "Divisor ideal must be contained in dividend ideal".to_string()
            ));
        }
        
        let quotient_size = if other.generator == 0 {
            if self.generator == 0 {
                1
            } else {
                usize::MAX // Infinite
            }
        } else {
            (self.generator / other.generator).abs() as usize
        };
        
        Ok(QuotientStructure {
            dividend: self.clone(),
            divisor: other.clone(),
            quotient_size,
        })
    }

    /// Compute the radical of the ideal
    /// rad(IS(n)) = IS(rad(n)) where rad(n) is the product of distinct prime factors
    pub fn radical(&self) -> Result<StateSpaceIdeal, StateSpaceIdealError> {
        let factorizations = self.state_space.factorizations();
        if factorizations.is_empty() {
            return StateSpaceIdeal::new(self.generator);
        }
        
        // Get unique prime factors from any factorization
        let first_factorization = &factorizations[0];
        let mut unique_primes = HashSet::new();
        
        for (&prime, _) in first_factorization.factors() {
            if prime != -1 { // Exclude sign prime for radical computation
                unique_primes.insert(prime.abs());
            }
        }
        
        // Compute radical as product of distinct primes
        let radical_value: i64 = unique_primes.iter().product();
        
        // Preserve quantum nature
        let radical_generator = if self.is_quantum() {
            -radical_value
        } else {
            radical_value
        };
        
        StateSpaceIdeal::new(radical_generator)
    }
}

/// Structure representing the quotient of two state-space ideals
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct QuotientStructure {
    /// The dividend ideal IS(n)
    pub dividend: StateSpaceIdeal,
    /// The divisor ideal IS(m) where m | n
    pub divisor: StateSpaceIdeal,
    /// Size of the quotient group
    pub quotient_size: usize,
}

impl QuotientStructure {
    /// Check if the quotient is finite
    pub fn is_finite(&self) -> bool {
        self.quotient_size != usize::MAX
    }
    
    /// Get representative elements of the quotient
    pub fn representatives(&self) -> Vec<i64> {
        if !self.is_finite() {
            return vec![];
        }
        
        let m = self.divisor.generator().abs();
        if m == 0 {
            return vec![0];
        }
        
        (0..m).collect()
    }
}

/// Compute greatest common divisor
fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

/// Compute least common multiple
fn lcm(a: u64, b: u64) -> u64 {
    if a == 0 || b == 0 {
        0
    } else {
        (a / gcd(a, b)) * b
    }
}

impl fmt::Display for StateSpaceIdeal {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "IS({}) = (({})⬝S({}))", 
            self.generator, 
            self.generator,
            self.generator
        )?;
        
        if self.is_quantum() {
            write!(f, " [Quantum]")?;
        } else if self.is_classical() {
            write!(f, " [Classical]")?;
        }
        
        write!(f, " dim={}", self.dimension())
    }
}

impl fmt::Display for QuotientStructure {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "IS({})/IS({})", 
            self.dividend.generator(),
            self.divisor.generator()
        )?;
        
        if self.is_finite() {
            write!(f, " ≅ ℤ/{}", self.quotient_size)
        } else {
            write!(f, " ≅ ℤ")
        }
    }
}

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

    #[test]
    fn test_state_space_ideal_creation() {
        let ideal6 = StateSpaceIdeal::new(6).unwrap();
        assert_eq!(ideal6.generator(), 6);
        assert!(ideal6.is_classical());
        assert!(!ideal6.is_quantum());
        
        let ideal_neg6 = StateSpaceIdeal::new(-6).unwrap();
        assert_eq!(ideal_neg6.generator(), -6);
        assert!(!ideal_neg6.is_classical());
        assert!(ideal_neg6.is_quantum());
    }

    #[test]
    fn test_principal_ideal_elements() {
        let mut ideal3 = StateSpaceIdeal::new(3).unwrap();
        let elements = ideal3.principal_ideal_elements(20);
        
        assert!(elements.contains(&3));
        assert!(elements.contains(&6));
        assert!(elements.contains(&9));
        assert!(elements.contains(&-3));
        assert!(elements.contains(&-6));
        
        // All elements should be multiples of 3
        for &elem in elements {
            assert_eq!(elem % 3, 0);
        }
    }

    #[test]
    fn test_ideal_multiplication() {
        let ideal2 = StateSpaceIdeal::new(2).unwrap();
        let ideal3 = StateSpaceIdeal::new(3).unwrap();
        
        let product = ideal2.multiply(&ideal3).unwrap();
        assert_eq!(product.generator(), 6);
        
        // Quantum × Quantum = Classical (collapse)
        let ideal_neg2 = StateSpaceIdeal::new(-2).unwrap();
        let ideal_neg3 = StateSpaceIdeal::new(-3).unwrap();
        let quantum_product = ideal_neg2.multiply(&ideal_neg3).unwrap();
        assert_eq!(quantum_product.generator(), 6);
        assert!(quantum_product.is_classical());
    }

    #[test]
    fn test_ideal_addition() {
        let ideal6 = StateSpaceIdeal::new(6).unwrap();
        let ideal9 = StateSpaceIdeal::new(9).unwrap();
        
        let sum = ideal6.add(&ideal9).unwrap();
        assert_eq!(sum.generator(), 3); // gcd(6,9) = 3
        
        // Quantum ideals preserve quantum nature
        let ideal_neg6 = StateSpaceIdeal::new(-6).unwrap();
        let ideal_neg9 = StateSpaceIdeal::new(-9).unwrap();
        let quantum_sum = ideal_neg6.add(&ideal_neg9).unwrap();
        assert_eq!(quantum_sum.generator(), -3);
        assert!(quantum_sum.is_quantum());
    }

    #[test]
    fn test_ideal_intersection() {
        let ideal4 = StateSpaceIdeal::new(4).unwrap();
        let ideal6 = StateSpaceIdeal::new(6).unwrap();
        
        let intersection = ideal4.intersect(&ideal6).unwrap();
        assert_eq!(intersection.generator(), 12); // lcm(4,6) = 12
        
        // Quantum preservation in intersection
        let ideal_neg4 = StateSpaceIdeal::new(-4).unwrap();
        let mixed_intersection = ideal_neg4.intersect(&ideal6).unwrap();
        assert_eq!(mixed_intersection.generator(), -12);
        assert!(mixed_intersection.is_quantum());
    }

    #[test]
    fn test_ideal_containment() {
        let ideal2 = StateSpaceIdeal::new(2).unwrap();
        let ideal6 = StateSpaceIdeal::new(6).unwrap();
        let ideal9 = StateSpaceIdeal::new(9).unwrap();
        
        assert!(ideal2.contains_ideal(&ideal6)); // 2 | 6
        assert!(!ideal6.contains_ideal(&ideal2)); // 6 ∤ 2
        assert!(!ideal6.contains_ideal(&ideal9)); // 6 ∤ 9
    }

    #[test]
    fn test_quotient_structure() {
        let ideal2 = StateSpaceIdeal::new(2).unwrap();
        let ideal6 = StateSpaceIdeal::new(6).unwrap();
        
        let quotient = ideal2.quotient(&ideal6).unwrap();
        assert_eq!(quotient.quotient_size, 0); // 2/6 = 0 (integer division)
        assert!(quotient.is_finite());
        
        let reps = quotient.representatives();
        assert_eq!(reps, vec![0, 1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_radical() {
        let ideal12 = StateSpaceIdeal::new(12).unwrap(); // 12 = 2² × 3
        let radical = ideal12.radical().unwrap();
        assert_eq!(radical.generator(), 6); // rad(12) = 2 × 3 = 6
        
        let ideal_neg18 = StateSpaceIdeal::new(-18).unwrap(); // -18 = -1 × 2 × 3²
        let quantum_radical = ideal_neg18.radical().unwrap();
        assert_eq!(quantum_radical.generator(), -6); // rad(-18) = -6
        assert!(quantum_radical.is_quantum());
    }

    #[test]
    fn test_display() {
        let ideal6 = StateSpaceIdeal::new(6).unwrap();
        let display = format!("{}", ideal6);
        assert!(display.contains("IS(6)"));
        assert!(display.contains("[Classical]"));
        assert!(display.contains("dim="));
        
        let ideal_neg6 = StateSpaceIdeal::new(-6).unwrap();
        let quantum_display = format!("{}", ideal_neg6);
        assert!(quantum_display.contains("IS(-6)"));
        assert!(quantum_display.contains("[Quantum]"));
    }
}