ppflib 0.1.0

//! Multiplication algebra for state space operations
//!
//! This module implements the multiplication algebra IS(a)·IS(b) = IS(c)
//! with optimizations for large state spaces and parallel computation.
//! The multiplication models quantum collapse when two quantum states interact.

use crate::core::{
    FactorizationStateSpace, StateSpaceOperations, 
    StateSpaceMultiplicationResult, CollapseInfo, OperationType
};
use crate::algebra::StateSpaceIdealError;
use std::sync::{Arc, Mutex};
use rayon::prelude::*;
use std::fmt;
use thiserror::Error;
use serde::{Deserialize, Serialize};

/// Errors for multiplication algebra operations
#[derive(Error, Debug, Clone, PartialEq)]
pub enum MultiplicationError {
    /// State space error
    #[error("State space error: {0}")]
    StateSpaceError(String),
    /// Ideal error
    #[error("Ideal error: {0}")]
    IdealError(#[from] StateSpaceIdealError),
    /// Overflow in computation
    #[error("Arithmetic overflow in multiplication")]
    Overflow,
    /// Invalid algebra operation
    #[error("Invalid algebra operation: {0}")]
    InvalidOperation(String),
}

/// Multiplication algebra for state spaces
/// 
/// Provides optimized algorithms for state space multiplication,
/// including parallel processing for large spaces and quantum collapse tracking.
#[derive(Debug, Clone)]
pub struct MultiplicationAlgebra {
    /// Configuration for parallel processing
    parallel_config: ParallelConfig,
    /// Cache for frequently used multiplications
    cache: Arc<Mutex<MultiplicationCache>>,
}

/// Configuration for parallel processing
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ParallelConfig {
    /// Minimum state space size to use parallel processing
    pub parallel_threshold: usize,
    /// Number of threads to use (0 = automatic)
    pub num_threads: usize,
    /// Enable caching of results
    pub enable_cache: bool,
    /// Maximum cache size
    pub max_cache_size: usize,
}

impl Default for ParallelConfig {
    fn default() -> Self {
        ParallelConfig {
            parallel_threshold: 1000,
            num_threads: 0, // Use rayon default
            enable_cache: true,
            max_cache_size: 1000,
        }
    }
}

/// Cache for multiplication results
#[derive(Debug, Default)]
struct MultiplicationCache {
    /// Cached results indexed by (a, b)
    results: HashMap<(i64, i64), StateSpaceMultiplicationResult>,
}

use std::collections::HashMap;

impl MultiplicationAlgebra {
    /// Create a new multiplication algebra with default configuration
    pub fn new() -> Self {
        Self::with_config(ParallelConfig::default())
    }

    /// Create with custom configuration
    pub fn with_config(config: ParallelConfig) -> Self {
        if config.num_threads > 0 {
            rayon::ThreadPoolBuilder::new()
                .num_threads(config.num_threads)
                .build_global()
                .ok();
        }

        MultiplicationAlgebra {
            parallel_config: config,
            cache: Arc::new(Mutex::new(MultiplicationCache::default())),
        }
    }

    /// Multiply two state spaces with optimization
    /// 
    /// Uses parallel processing for large state spaces and caching
    /// for frequently used operations.
    pub fn multiply(
        &self,
        space_a: &FactorizationStateSpace,
        space_b: &FactorizationStateSpace,
    ) -> Result<StateSpaceMultiplicationResult, MultiplicationError> {
        let a = space_a.value();
        let b = space_b.value();

        // Check cache first
        if self.parallel_config.enable_cache {
            if let Ok(cache) = self.cache.lock() {
                if let Some(cached) = cache.results.get(&(a, b)) {
                    return Ok(cached.clone());
                }
            }
        }

        // Compute result
        let result = if self.should_use_parallel(space_a, space_b) {
            self.parallel_multiply(space_a, space_b)?
        } else {
            StateSpaceOperations::multiply(space_a, space_b)
                .map_err(|e| MultiplicationError::StateSpaceError(e.to_string()))?
        };

        // Cache result
        if self.parallel_config.enable_cache {
            if let Ok(mut cache) = self.cache.lock() {
                if cache.results.len() < self.parallel_config.max_cache_size {
                    cache.results.insert((a, b), result.clone());
                }
            }
        }

        Ok(result)
    }

    /// Check if parallel processing should be used
    fn should_use_parallel(
        &self,
        space_a: &FactorizationStateSpace,
        space_b: &FactorizationStateSpace,
    ) -> bool {
        space_a.size() + space_b.size() >= self.parallel_config.parallel_threshold
    }

    /// Parallel multiplication for large state spaces
    fn parallel_multiply(
        &self,
        space_a: &FactorizationStateSpace,
        space_b: &FactorizationStateSpace,
    ) -> Result<StateSpaceMultiplicationResult, MultiplicationError> {
        // For now, delegate to standard multiplication
        // In a full implementation, this would parallelize factorization enumeration
        StateSpaceOperations::multiply(space_a, space_b)
            .map_err(|e| MultiplicationError::StateSpaceError(e.to_string()))
    }

    /// Multiply a sequence of state spaces
    /// 
    /// Computes IS(a₁) · IS(a₂) · ... · IS(aₙ) = IS(∏aᵢ)
    pub fn multiply_sequence(
        &self,
        spaces: &[FactorizationStateSpace],
    ) -> Result<StateSpaceMultiplicationResult, MultiplicationError> {
        if spaces.is_empty() {
            return Err(MultiplicationError::InvalidOperation(
                "Cannot multiply empty sequence".to_string()
            ));
        }

        if spaces.len() == 1 {
            // Identity multiplication
            let space = &spaces[0];
            return Ok(StateSpaceMultiplicationResult {
                result_space: space.clone(),
                collapse_info: CollapseInfo {
                    collapsed: false,
                    input_sizes: (space.size(), space.size()),
                    output_size: space.size(),
                    collapse_ratio: 1.0,
                    operation_type: OperationType::Other,
                },
            });
        }

        // Use parallel reduction for large sequences
        if spaces.len() >= 4 && self.parallel_config.num_threads != 1 {
            self.parallel_multiply_sequence(spaces)
        } else {
            self.sequential_multiply_sequence(spaces)
        }
    }

    /// Sequential multiplication of sequence
    fn sequential_multiply_sequence(
        &self,
        spaces: &[FactorizationStateSpace],
    ) -> Result<StateSpaceMultiplicationResult, MultiplicationError> {
        let mut result = self.multiply(&spaces[0], &spaces[1])?;

        for space in &spaces[2..] {
            result = self.multiply(&result.result_space, space)?;
        }

        Ok(result)
    }

    /// Parallel multiplication of sequence using tree reduction
    fn parallel_multiply_sequence(
        &self,
        spaces: &[FactorizationStateSpace],
    ) -> Result<StateSpaceMultiplicationResult, MultiplicationError> {
        // Clone spaces for parallel processing
        let spaces: Vec<_> = spaces.to_vec();
        
        // Tree reduction
        let mut current = spaces.clone();
        while current.len() > 1 {
            let pairs: Vec<_> = current
                .par_chunks(2)
                .map(|chunk| {
                    if chunk.len() == 2 {
                        self.multiply(&chunk[0], &chunk[1])
                            .map(|r| r.result_space)
                    } else {
                        Ok(chunk[0].clone())
                    }
                })
                .collect::<Result<Vec<_>, _>>()?;
            current = pairs;
        }

        // Final result with collapse info
        let final_space = current.into_iter().next().unwrap();
        
        // Compute overall collapse info
        let total_collapse = spaces.iter()
            .filter(|s| s.is_quantum())
            .count() >= 2;
            
        Ok(StateSpaceMultiplicationResult {
            result_space: final_space.clone(),
            collapse_info: CollapseInfo {
                collapsed: total_collapse,
                input_sizes: (spaces[0].size(), spaces.last().unwrap().size()),
                output_size: final_space.size(),
                collapse_ratio: final_space.size() as f64 / spaces.iter().map(|s| s.size()).max().unwrap() as f64,
                operation_type: if total_collapse {
                    OperationType::QuantumQuantum
                } else {
                    OperationType::Other
                },
            },
        })
    }

    /// Compute power of a state space using repeated squaring
    pub fn power(
        &self,
        space: &FactorizationStateSpace,
        exponent: u32,
    ) -> Result<StateSpaceMultiplicationResult, MultiplicationError> {
        if exponent == 0 {
            return StateSpaceOperations::power(space, 0)
                .map_err(|e| MultiplicationError::StateSpaceError(e.to_string()));
        }

        // Use repeated squaring for large exponents
        if exponent >= 8 {
            self.power_by_squaring(space, exponent)
        } else {
            StateSpaceOperations::power(space, exponent)
                .map_err(|e| MultiplicationError::StateSpaceError(e.to_string()))
        }
    }

    /// Efficient power computation using repeated squaring
    fn power_by_squaring(
        &self,
        space: &FactorizationStateSpace,
        mut exponent: u32,
    ) -> Result<StateSpaceMultiplicationResult, MultiplicationError> {
        let mut result = FactorizationStateSpace::new(1)
            .map_err(|e| MultiplicationError::StateSpaceError(e.to_string()))?;
        let mut base = space.clone();

        while exponent > 0 {
            if exponent & 1 == 1 {
                let mult_result = self.multiply(&result, &base)?;
                result = mult_result.result_space;
            }
            if exponent > 1 {
                let square_result = self.multiply(&base, &base)?;
                base = square_result.result_space;
            }
            exponent >>= 1;
        }

        // Compute final collapse info
        let collapsed = space.is_quantum() && (exponent % 2 == 0);
        
        Ok(StateSpaceMultiplicationResult {
            result_space: result.clone(),
            collapse_info: CollapseInfo {
                collapsed,
                input_sizes: (space.size(), space.size()),
                output_size: result.size(),
                collapse_ratio: result.size() as f64 / space.size() as f64,
                operation_type: if collapsed {
                    OperationType::QuantumQuantum
                } else {
                    OperationType::Other
                },
            },
        })
    }

    /// Analyze collapse patterns in a multiplication table
    pub fn analyze_collapse_patterns(
        &self,
        values: &[i64],
    ) -> CollapsePatternAnalysis {
        let mut patterns = Vec::new();
        let mut total_collapses = 0;
        let mut quantum_operations = 0;

        // Compute all pairwise multiplications
        for (i, &a) in values.iter().enumerate() {
            for &b in values.iter().skip(i) {
                if let (Ok(space_a), Ok(space_b)) = (
                    FactorizationStateSpace::new(a),
                    FactorizationStateSpace::new(b),
                ) {
                    if let Ok(result) = self.multiply(&space_a, &space_b) {
                        if result.collapse_info.collapsed {
                            total_collapses += 1;
                            patterns.push(CollapsePattern {
                                input_a: a,
                                input_b: b,
                                output: result.result_space.value(),
                                collapse_ratio: result.collapse_info.collapse_ratio,
                            });
                        }
                        if matches!(result.collapse_info.operation_type, OperationType::QuantumQuantum) {
                            quantum_operations += 1;
                        }
                    }
                }
            }
        }

        let total_operations = values.len() * (values.len() + 1) / 2;
        
        CollapsePatternAnalysis {
            patterns,
            total_collapses,
            total_operations,
            quantum_operations,
            collapse_rate: total_collapses as f64 / total_operations as f64,
        }
    }

    /// Clear the multiplication cache
    pub fn clear_cache(&self) {
        if let Ok(mut cache) = self.cache.lock() {
            cache.results.clear();
        }
    }

    /// Get cache statistics
    pub fn cache_stats(&self) -> CacheStats {
        if let Ok(cache) = self.cache.lock() {
            CacheStats {
                size: cache.results.len(),
                max_size: self.parallel_config.max_cache_size,
                enabled: self.parallel_config.enable_cache,
            }
        } else {
            CacheStats::default()
        }
    }
}

/// Pattern of quantum collapse
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct CollapsePattern {
    /// First input value
    pub input_a: i64,
    /// Second input value
    pub input_b: i64,
    /// Output value after multiplication
    pub output: i64,
    /// Collapse ratio
    pub collapse_ratio: f64,
}

/// Analysis of collapse patterns
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CollapsePatternAnalysis {
    /// Individual collapse patterns
    pub patterns: Vec<CollapsePattern>,
    /// Total number of collapses
    pub total_collapses: usize,
    /// Total number of operations
    pub total_operations: usize,
    /// Number of quantum-quantum operations
    pub quantum_operations: usize,
    /// Rate of collapse
    pub collapse_rate: f64,
}

/// Cache statistics
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct CacheStats {
    /// Current cache size
    pub size: usize,
    /// Maximum cache size
    pub max_size: usize,
    /// Whether cache is enabled
    pub enabled: bool,
}

impl fmt::Display for CollapsePatternAnalysis {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "Collapse Pattern Analysis:")?;
        writeln!(f, "  Total operations: {}", self.total_operations)?;
        writeln!(f, "  Quantum operations: {}", self.quantum_operations)?;
        writeln!(f, "  Total collapses: {}", self.total_collapses)?;
        writeln!(f, "  Collapse rate: {:.2}%", self.collapse_rate * 100.0)?;
        
        if !self.patterns.is_empty() {
            writeln!(f, "  Sample patterns:")?;
            for (i, pattern) in self.patterns.iter().take(5).enumerate() {
                writeln!(f, "    {}: ({}) × ({}) = {} (ratio: {:.3})",
                    i + 1,
                    pattern.input_a,
                    pattern.input_b,
                    pattern.output,
                    pattern.collapse_ratio
                )?;
            }
        }
        
        Ok(())
    }
}

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

    #[test]
    fn test_basic_multiplication() {
        let algebra = MultiplicationAlgebra::new();
        
        let s2 = FactorizationStateSpace::new(2).unwrap();
        let s3 = FactorizationStateSpace::new(3).unwrap();
        
        let result = algebra.multiply(&s2, &s3).unwrap();
        assert_eq!(result.result_space.value(), 6);
        assert!(!result.collapse_info.collapsed);
    }

    #[test]
    fn test_quantum_collapse() {
        let algebra = MultiplicationAlgebra::new();
        
        let s_neg2 = FactorizationStateSpace::new(-2).unwrap();
        let s_neg3 = FactorizationStateSpace::new(-3).unwrap();
        
        let result = algebra.multiply(&s_neg2, &s_neg3).unwrap();
        assert_eq!(result.result_space.value(), 6);
        assert!(result.collapse_info.collapsed);
    }

    #[test]
    fn test_sequence_multiplication() {
        let algebra = MultiplicationAlgebra::new();
        
        let spaces = vec![
            FactorizationStateSpace::new(2).unwrap(),
            FactorizationStateSpace::new(3).unwrap(),
            FactorizationStateSpace::new(5).unwrap(),
        ];
        
        let result = algebra.multiply_sequence(&spaces).unwrap();
        assert_eq!(result.result_space.value(), 30); // 2 × 3 × 5
    }

    #[test]
    fn test_power_computation() {
        let algebra = MultiplicationAlgebra::new();
        
        let s2 = FactorizationStateSpace::new(2).unwrap();
        let result = algebra.power(&s2, 5).unwrap();
        assert_eq!(result.result_space.value(), 32); // 2^5
        
        let s_neg2 = FactorizationStateSpace::new(-2).unwrap();
        let quantum_power = algebra.power(&s_neg2, 4).unwrap();
        assert_eq!(quantum_power.result_space.value(), 16); // (-2)^4
        assert!(quantum_power.collapse_info.collapsed); // Even power causes collapse
    }

    #[test]
    fn test_collapse_pattern_analysis() {
        let algebra = MultiplicationAlgebra::new();
        
        let values = vec![-2, -3, 2, 3];
        let analysis = algebra.analyze_collapse_patterns(&values);
        
        assert!(analysis.total_collapses > 0);
        assert!(analysis.quantum_operations > 0);
        assert!(analysis.collapse_rate > 0.0);
        
        // Should find (-2) × (-3) = 6 collapse
        let collapse_found = analysis.patterns.iter()
            .any(|p| p.input_a == -2 && p.input_b == -3 && p.output == 6);
        assert!(collapse_found);
    }

    #[test]
    fn test_cache_functionality() {
        let config = ParallelConfig {
            enable_cache: true,
            max_cache_size: 10,
            ..Default::default()
        };
        let algebra = MultiplicationAlgebra::with_config(config);
        
        let s2 = FactorizationStateSpace::new(2).unwrap();
        let s3 = FactorizationStateSpace::new(3).unwrap();
        
        // First multiplication
        let _ = algebra.multiply(&s2, &s3).unwrap();
        
        let stats = algebra.cache_stats();
        assert_eq!(stats.size, 1);
        assert!(stats.enabled);
        
        // Clear cache
        algebra.clear_cache();
        let stats_after = algebra.cache_stats();
        assert_eq!(stats_after.size, 0);
    }

    #[test]
    fn test_parallel_config() {
        let config = ParallelConfig {
            parallel_threshold: 10,
            num_threads: 2,
            enable_cache: false,
            max_cache_size: 0,
        };
        
        let algebra = MultiplicationAlgebra::with_config(config);
        let stats = algebra.cache_stats();
        assert!(!stats.enabled);
    }
}