ppflib 0.1.0

//! Factorization state spaces S(n) implementation
//!
//! This module implements the core S(n) state space representation and enumeration
//! algorithms for generating all canonical P-factorizations of integers in the PPF framework.

use crate::core::{is_magnitude_prime, SIGN_PRIME};
use std::collections::BTreeMap;
use std::fmt;
use std::hash::{Hash, Hasher};
use thiserror::Error;
use serde::{Deserialize, Serialize};

/// Errors that can occur during factorization operations
#[derive(Error, Debug, Clone, PartialEq)]
pub enum FactorizationError {
    /// The provided factorization is invalid
    #[error("Invalid factorization: {0}")]
    InvalidFactorization(String),
    /// Cannot factorize zero
    #[error("Cannot factorize zero")]
    CannotFactorizeZero,
    /// Integer is too large for efficient factorization
    #[error("Integer too large for efficient factorization")]
    IntegerTooLarge,
    /// An invalid state space operation was attempted
    #[error("Invalid state space operation: {0}")]
    InvalidOperation(String),
}

/// Represents a single P-factorization as a multiset of P-primes
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct PFactorization {
    /// Map from prime value to its multiplicity
    /// Negative primes represent negative factors
    factors: BTreeMap<i64, u32>,
    /// The integer value this factorization represents
    value: i64,
}

impl PFactorization {
    /// Create a new P-factorization from a vector of prime factors
    /// 
    /// # Arguments
    /// * `factors` - Vector of prime factors (can include repetitions and signs)
    /// 
    /// # Returns
    /// * `Ok(PFactorization)` if the factorization is valid
    /// * `Err(FactorizationError)` if invalid
    /// 
    /// # Examples
    /// ```
    /// use ppflib::core::PFactorization;
    /// 
    /// // Standard factorization: 6 = 2 × 3
    /// let f1 = PFactorization::new(vec![2, 3]).unwrap();
    /// 
    /// // PPF factorization: -6 = (-1) × 2 × 3
    /// let f2 = PFactorization::new(vec![-1, 2, 3]).unwrap();
    /// 
    /// // PPF factorization: -6 = (-2) × 3
    /// let f3 = PFactorization::new(vec![-2, 3]).unwrap();
    /// ```
    pub fn new(factors: Vec<i64>) -> Result<Self, FactorizationError> {
        if factors.is_empty() {
            return Err(FactorizationError::InvalidFactorization(
                "Empty factorization".to_string()
            ));
        }

        // Validate factors for PPF factorization representation
        // In PPF, factorizations can contain:
        // 1. The Sign Prime (-1)
        // 2. Positive magnitude primes (2, 3, 5, 7, ...)
        // 3. Negative magnitude primes (-2, -3, -5, ...) as representational convenience
        //    (these represent the result of sign operations, not fundamental P-primes)
        for &factor in &factors {
            if !Self::is_valid_factorization_factor(factor) {
                return Err(FactorizationError::InvalidFactorization(
                    format!("{} is not a valid factorization factor", factor)
                ));
            }
        }

        // Count multiplicities
        let mut factor_map = BTreeMap::new();
        for factor in factors {
            *factor_map.entry(factor).or_insert(0) += 1;
        }

        // Compute the value
        let value = Self::compute_value(&factor_map)?;

        Ok(PFactorization {
            factors: factor_map,
            value,
        })
    }

    /// Create a canonical P-factorization (used internally for state space generation)
    pub(crate) fn new_canonical(factors: BTreeMap<i64, u32>, value: i64) -> Self {
        PFactorization { factors, value }
    }

    /// Check if a factor is valid for PPF factorization representation
    /// 
    /// Valid factors are:
    /// 1. The Sign Prime (-1)
    /// 2. Positive magnitude primes (2, 3, 5, 7, ...)
    /// 3. Negative magnitude primes (-2, -3, -5, ...) as representational convenience
    fn is_valid_factorization_factor(factor: i64) -> bool {
        if factor == 0 || factor == 1 {
            false
        } else if factor == SIGN_PRIME {
            true // Sign Prime
        } else if factor > 1 {
            is_magnitude_prime(factor) // Positive magnitude prime
        } else {
            // Negative factor: check if absolute value is a magnitude prime
            is_magnitude_prime(-factor)
        }
    }

    /// Compute the integer value from factor multiplicities
    fn compute_value(factors: &BTreeMap<i64, u32>) -> Result<i64, FactorizationError> {
        let mut result = 1i64;
        
        for (&factor, &multiplicity) in factors {
            for _ in 0..multiplicity {
                result = result.checked_mul(factor)
                    .ok_or_else(|| FactorizationError::IntegerTooLarge)?;
            }
        }
        
        Ok(result)
    }

    /// Get the integer value this factorization represents
    pub fn value(&self) -> i64 {
        self.value
    }

    /// Get the factors as a map from prime to multiplicity
    pub fn factors(&self) -> &BTreeMap<i64, u32> {
        &self.factors
    }

    /// Get the factors as a sorted vector (with repetitions)
    pub fn factor_vector(&self) -> Vec<i64> {
        let mut result = Vec::new();
        
        // Add sign prime first if present
        if let Some(&count) = self.factors.get(&SIGN_PRIME) {
            for _ in 0..count {
                result.push(SIGN_PRIME);
            }
        }
        
        // Add magnitude primes in sorted order
        let mut magnitude_primes: Vec<_> = self.factors.iter()
            .filter(|(&prime, _)| prime != SIGN_PRIME)
            .collect();
        magnitude_primes.sort_by_key(|(&prime, _)| prime.abs());
        
        for (&prime, &count) in magnitude_primes {
            for _ in 0..count {
                result.push(prime);
            }
        }
        
        result
    }

    /// Check if this factorization is in canonical form
    /// 
    /// A canonical P-factorization has:
    /// 1. At most one Sign Prime (-1)
    /// 2. Proper sign distribution for the integer's sign
    pub fn is_canonical(&self) -> bool {
        let sign_prime_count = self.factors.get(&SIGN_PRIME).copied().unwrap_or(0);
        
        // Can have at most one sign prime
        if sign_prime_count > 1 {
            return false;
        }

        // Count negative magnitude primes
        let negative_magnitude_count: u32 = self.factors.iter()
            .filter(|(&prime, _)| prime < 0 && prime != SIGN_PRIME)
            .map(|(_, &count)| count)
            .sum();

        // For positive integers: even number of negative factors (including sign prime)
        // For negative integers: odd number of negative factors (including sign prime)
        let total_negative = sign_prime_count + negative_magnitude_count;
        
        if self.value > 0 {
            total_negative % 2 == 0
        } else {
            total_negative % 2 == 1
        }
    }

    /// Convert to canonical form
    pub fn to_canonical(&self) -> Result<Self, FactorizationError> {
        if self.is_canonical() {
            return Ok(self.clone());
        }

        let mut new_factors = self.factors.clone();
        let sign_prime_count = new_factors.get(&SIGN_PRIME).copied().unwrap_or(0);

        // Remove excess sign primes (pairs cancel out)
        if sign_prime_count > 1 {
            let remaining_sign_primes = sign_prime_count % 2;
            if remaining_sign_primes == 0 {
                new_factors.remove(&SIGN_PRIME);
            } else {
                new_factors.insert(SIGN_PRIME, 1);
            }
        }

        Ok(PFactorization {
            factors: new_factors,
            value: self.value,
        })
    }

    /// Check if this factorization contains the Sign Prime
    pub fn has_sign_prime(&self) -> bool {
        self.factors.contains_key(&SIGN_PRIME)
    }

    /// Get the number of distinct primes in this factorization
    pub fn distinct_prime_count(&self) -> usize {
        self.factors.len()
    }

    /// Get the total number of prime factors (with multiplicities)
    pub fn total_factor_count(&self) -> u32 {
        self.factors.values().sum()
    }

    /// Get the complexity measure Ω(f) = sum of magnitude prime multiplicities
    pub fn complexity(&self) -> u32 {
        self.factors.iter()
            .filter(|(&prime, _)| prime != SIGN_PRIME)
            .map(|(_, &count)| count)
            .sum()
    }
}

impl Hash for PFactorization {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Hash based on the value, which uniquely identifies equivalent factorizations
        self.value.hash(state);
        
        // Also hash the factor map for distinction between equivalent factorizations
        for (prime, count) in &self.factors {
            prime.hash(state);
            count.hash(state);
        }
    }
}

impl fmt::Display for PFactorization {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let factors = self.factor_vector();
        if factors.is_empty() {
            write!(f, "1")
        } else {
            let factor_strs: Vec<String> = factors.iter()
                .map(|&x| x.to_string())
                .collect();
            write!(f, "{}", factor_strs.join(" × "))
        }
    }
}

/// Represents the complete factorization state space S(n) for an integer n
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct FactorizationStateSpace {
    /// The integer whose state space this represents
    value: i64,
    /// All canonical P-factorizations of the integer
    factorizations: Vec<PFactorization>,
}

impl FactorizationStateSpace {
    /// Create a new factorization state space for an integer
    /// 
    /// # Arguments
    /// * `n` - The integer to factorize (must be non-zero)
    /// 
    /// # Returns
    /// * `Ok(FactorizationStateSpace)` containing all canonical P-factorizations
    /// * `Err(FactorizationError)` if n is zero or computation fails
    /// 
    /// # Examples
    /// ```
    /// use ppflib::core::FactorizationStateSpace;
    /// 
    /// // Positive integer: S(6) = {2×3, (-2)×(-3)}
    /// let s6 = FactorizationStateSpace::new(6).unwrap();
    /// assert_eq!(s6.size(), 2);
    /// 
    /// // Negative integer: S(-6) = {(-1)×2×3, (-2)×3, 2×(-3)}
    /// let s_neg6 = FactorizationStateSpace::new(-6).unwrap();
    /// assert_eq!(s_neg6.size(), 3);
    /// ```
    pub fn new(n: i64) -> Result<Self, FactorizationError> {
        if n == 0 {
            return Err(FactorizationError::CannotFactorizeZero);
        }

        let factorizations = Self::generate_all_factorizations(n)?;

        Ok(FactorizationStateSpace {
            value: n,
            factorizations,
        })
    }

    /// Generate all canonical P-factorizations for an integer
    fn generate_all_factorizations(n: i64) -> Result<Vec<PFactorization>, FactorizationError> {
        let abs_n = n.abs();
        
        // Get the standard prime factorization of |n|
        let standard_factorization = Self::standard_prime_factorization(abs_n)?;
        
        // Generate all sign combinations
        let factorizations = if n > 0 {
            // Positive integer: generate factorizations with even number of negative factors
            Self::generate_positive_factorizations(&standard_factorization)
        } else {
            // Negative integer: generate factorizations with odd number of negative factors
            Self::generate_negative_factorizations(&standard_factorization)
        };

        Ok(factorizations)
    }

    /// Get standard prime factorization of a positive integer
    fn standard_prime_factorization(n: i64) -> Result<BTreeMap<i64, u32>, FactorizationError> {
        if n <= 0 {
            return Err(FactorizationError::InvalidFactorization(
                "Cannot factorize non-positive integer".to_string()
            ));
        }

        let mut factors = BTreeMap::new();
        let mut remaining = n;

        // Trial division by small primes
        for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] {
            while remaining % p == 0 {
                *factors.entry(p).or_insert(0) += 1;
                remaining /= p;
            }
        }

        // Handle remaining factors
        if remaining > 1 {
            if remaining > 10000 {
                return Err(FactorizationError::IntegerTooLarge);
            }
            
            // Check if remaining is prime
            if is_magnitude_prime(remaining) {
                factors.insert(remaining, 1);
            } else {
                // Try to factor remaining (simplified approach)
                let sqrt_remaining = (remaining as f64).sqrt() as i64;
                let mut found_factor = false;
                
                for candidate in 49..=sqrt_remaining {
                    if candidate % 2 == 0 || candidate % 3 == 0 {
                        continue;
                    }
                    if remaining % candidate == 0 {
                        // Recursively factorize
                        let sub_factors1 = Self::standard_prime_factorization(candidate)?;
                        let sub_factors2 = Self::standard_prime_factorization(remaining / candidate)?;
                        
                        for (&prime, &count) in &sub_factors1 {
                            *factors.entry(prime).or_insert(0) += count;
                        }
                        for (&prime, &count) in &sub_factors2 {
                            *factors.entry(prime).or_insert(0) += count;
                        }
                        found_factor = true;
                        break;
                    }
                }
                
                if !found_factor {
                    factors.insert(remaining, 1);
                }
            }
        }

        Ok(factors)
    }

    /// Generate factorizations for positive integers (even number of negative factors)
    fn generate_positive_factorizations(standard_factors: &BTreeMap<i64, u32>) -> Vec<PFactorization> {
        let mut factorizations = Vec::new();
        let primes: Vec<i64> = standard_factors.keys().copied().collect();
        let k = primes.len();

        if k == 0 {
            // Special case: n = 1
            factorizations.push(PFactorization::new_canonical(BTreeMap::new(), 1));
            return factorizations;
        }

        // Generate all subsets of primes with even cardinality
        let num_subsets: u32 = 1 << k; // 2^k subsets
        
        for subset in 0..num_subsets {
            let negative_count = (subset as u32).count_ones();
            if negative_count % 2 == 0 {
                // Even number of negative factors - use direct negative magnitude primes
                let mut factors = BTreeMap::new();
                
                for (i, &prime) in primes.iter().enumerate() {
                    let is_negative = (subset & (1 << i)) != 0;
                    let count = standard_factors[&prime];
                    
                    if is_negative {
                        // Add as negative magnitude prime
                        factors.insert(-prime, count);
                    } else {
                        // Add as positive magnitude prime
                        factors.insert(prime, count);
                    }
                }
                
                // Compute value to verify
                let mut value = 1i64;
                for (&prime, &count) in &factors {
                    for _ in 0..count {
                        value *= prime;
                    }
                }
                
                factorizations.push(PFactorization::new_canonical(factors, value));
            }
        }

        factorizations
    }

    /// Generate factorizations for negative integers (odd number of negative factors)
    fn generate_negative_factorizations(standard_factors: &BTreeMap<i64, u32>) -> Vec<PFactorization> {
        let mut factorizations = Vec::new();
        let primes: Vec<i64> = standard_factors.keys().copied().collect();
        let k = primes.len();

        if k == 0 {
            // Special case: n = -1 (just the sign prime)
            let mut factors = BTreeMap::new();
            factors.insert(SIGN_PRIME, 1);
            factorizations.push(PFactorization::new_canonical(factors, -1));
            return factorizations;
        }

        // Method 1: Use explicit sign prime with all positive magnitude primes
        let mut factors_with_sign_prime = BTreeMap::new();
        factors_with_sign_prime.insert(SIGN_PRIME, 1);
        for (&prime, &count) in standard_factors {
            factors_with_sign_prime.insert(prime, count);
        }
        
        let mut value = -1i64;
        for (&prime, &count) in standard_factors {
            for _ in 0..count {
                value *= prime;
            }
        }
        
        factorizations.push(PFactorization::new_canonical(factors_with_sign_prime, value));

        // Method 2: Use odd number of negative magnitude primes (no explicit sign prime)
        let num_subsets: u32 = 1 << k;
        
        for subset in 1..num_subsets { // Skip empty subset
            let negative_count = (subset as u32).count_ones();
            if negative_count % 2 == 1 {
                // Odd number of negative factors - use negative magnitude primes directly
                let mut factors = BTreeMap::new();
                
                for (i, &prime) in primes.iter().enumerate() {
                    let is_negative = (subset & (1 << i)) != 0;
                    let count = standard_factors[&prime];
                    
                    if is_negative {
                        // Add as negative magnitude prime
                        factors.insert(-prime, count);
                    } else {
                        // Add as positive magnitude prime
                        factors.insert(prime, count);
                    }
                }
                
                // Compute value
                let mut computed_value = 1i64;
                for (&prime, &count) in &factors {
                    for _ in 0..count {
                        computed_value *= prime;
                    }
                }
                
                factorizations.push(PFactorization::new_canonical(factors, computed_value));
            }
        }

        factorizations
    }

    /// Get the integer this state space represents
    pub fn value(&self) -> i64 {
        self.value
    }

    /// Get all factorizations in this state space
    pub fn factorizations(&self) -> &[PFactorization] {
        &self.factorizations
    }

    /// Get the size of this state space (number of factorizations)
    pub fn size(&self) -> usize {
        self.factorizations.len()
    }

    /// Check if a factorization is in this state space
    pub fn contains(&self, factorization: &PFactorization) -> bool {
        self.factorizations.contains(factorization)
    }

    /// Get the theoretical size for an integer with k distinct prime factors
    /// For PPF: 
    /// - Positive integers: |S(n)| = 2^(k-1) for k >= 1
    /// - Negative integers: |S(n)| = 2^(k-1) + 1 for k >= 1 (one explicit Sign Prime + odd subsets)
    pub fn theoretical_size(n: i64) -> Result<usize, FactorizationError> {
        if n == 0 {
            return Err(FactorizationError::CannotFactorizeZero);
        }

        let standard_factors = Self::standard_prime_factorization(n.abs())?;
        let k = standard_factors.len();
        
        if k == 0 {
            Ok(1) // For n = ±1
        } else if n > 0 {
            Ok(1 << (k - 1)) // 2^(k-1) for positive integers
        } else {
            // For negative integers: 1 explicit sign prime + 2^(k-1) odd subsets
            // But actually, let's compute it correctly as the number of odd-cardinality subsets + 1
            // Number of odd-cardinality subsets of k elements = 2^(k-1)
            // Plus 1 for the explicit sign prime representation
            Ok((1 << (k - 1)) + 1)
        }
    }

    /// Verify that this state space has the correct size
    pub fn verify_size(&self) -> Result<bool, FactorizationError> {
        let expected_size = Self::theoretical_size(self.value)?;
        Ok(self.size() == expected_size)
    }
}

impl fmt::Display for FactorizationStateSpace {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "S({}) = {{", self.value)?;
        for (i, factorization) in self.factorizations.iter().enumerate() {
            if i > 0 {
                writeln!(f, ",")?;
            }
            write!(f, "  {}", factorization)?;
        }
        writeln!(f, "\n}}")
    }
}

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

    #[test]
    fn test_pfactorization_creation() {
        // Standard factorization
        let f1 = PFactorization::new(vec![2, 3]).unwrap();
        assert_eq!(f1.value(), 6);
        assert_eq!(f1.factor_vector(), vec![2, 3]);

        // With sign prime
        let f2 = PFactorization::new(vec![-1, 2, 3]).unwrap();
        assert_eq!(f2.value(), -6);
        assert!(f2.has_sign_prime());

        // With negative magnitude prime (valid in factorization representation)
        let f3 = PFactorization::new(vec![-2, 3]).unwrap();
        assert_eq!(f3.value(), -6);
        assert!(!f3.has_sign_prime());

        // Invalid factorization
        assert!(PFactorization::new(vec![4]).is_err()); // 4 is not prime
    }

    #[test]
    fn test_canonical_form() {
        let f1 = PFactorization::new(vec![2, 3]).unwrap();
        assert!(f1.is_canonical());

        let f2 = PFactorization::new(vec![-1, 2, 3]).unwrap();
        assert!(f2.is_canonical());

        let f3 = PFactorization::new(vec![-2, 3]).unwrap();
        assert!(f3.is_canonical());
    }

    #[test]
    fn test_factorization_complexity() {
        let f1 = PFactorization::new(vec![2, 3]).unwrap();
        assert_eq!(f1.complexity(), 2); // Two magnitude primes

        let f2 = PFactorization::new(vec![-1, 2, 3]).unwrap();
        assert_eq!(f2.complexity(), 2); // Sign prime doesn't count

        let f3 = PFactorization::new(vec![2, 2, 3]).unwrap();
        assert_eq!(f3.complexity(), 3); // 2^2 * 3
    }

    #[test]
    fn test_state_space_positive_integer() {
        // S(6) should have 2 factorizations: {2,3} and {-2,-3}
        let s6 = FactorizationStateSpace::new(6).unwrap();
        assert_eq!(s6.size(), 2);
        assert!(s6.verify_size().unwrap());
        
        let values: Vec<i64> = s6.factorizations().iter().map(|f| f.value()).collect();
        assert!(values.iter().all(|&v| v == 6));
    }

    #[test]
    fn test_state_space_negative_integer() {
        // S(-6) should have 3 factorizations
        let s_neg6 = FactorizationStateSpace::new(-6).unwrap();
        assert_eq!(s_neg6.size(), 3);
        assert!(s_neg6.verify_size().unwrap());
        
        let values: Vec<i64> = s_neg6.factorizations().iter().map(|f| f.value()).collect();
        assert!(values.iter().all(|&v| v == -6));
    }

    #[test]
    fn test_state_space_prime() {
        // S(7) should have 1 factorization: {7}
        let s7 = FactorizationStateSpace::new(7).unwrap();
        assert_eq!(s7.size(), 1);
        
        // S(-7) should have 2 factorizations: {-1, 7} and {-7}
        let s_neg7 = FactorizationStateSpace::new(-7).unwrap();
        assert_eq!(s_neg7.size(), 2);
    }

    #[test]
    fn test_state_space_unity() {
        // S(1) should have 1 factorization: {} (empty)
        let s1 = FactorizationStateSpace::new(1).unwrap();
        assert_eq!(s1.size(), 1);
        
        // S(-1) should have 1 factorization: {-1}
        let s_neg1 = FactorizationStateSpace::new(-1).unwrap();
        assert_eq!(s_neg1.size(), 1);
        assert!(s_neg1.factorizations()[0].has_sign_prime());
    }

    #[test]
    fn test_theoretical_size() {
        assert_eq!(FactorizationStateSpace::theoretical_size(6).unwrap(), 2); // 2^(2-1) = 2
        assert_eq!(FactorizationStateSpace::theoretical_size(30).unwrap(), 4); // 2^(3-1) = 4
        assert_eq!(FactorizationStateSpace::theoretical_size(210).unwrap(), 8); // 2^(4-1) = 8
    }

    #[test]
    fn test_standard_factorization() {
        let factors = FactorizationStateSpace::standard_prime_factorization(12).unwrap();
        assert_eq!(factors.get(&2), Some(&2)); // 2^2
        assert_eq!(factors.get(&3), Some(&1)); // 3^1

        let factors_prime = FactorizationStateSpace::standard_prime_factorization(17).unwrap();
        assert_eq!(factors_prime.get(&17), Some(&1)); // 17^1
        assert_eq!(factors_prime.len(), 1);
    }

    #[test]
    fn test_zero_factorization() {
        assert!(FactorizationStateSpace::new(0).is_err());
    }

    #[test]
    fn test_display() {
        let f = PFactorization::new(vec![2, 3]).unwrap();
        assert_eq!(format!("{}", f), "2 × 3");

        let f_with_sign = PFactorization::new(vec![-1, 2, 3]).unwrap();
        assert_eq!(format!("{}", f_with_sign), "-1 × 2 × 3");
    }
}