use crate::errors::ProblemResult;
use crate::problem::{Constraint, ConstraintType, Problem, ProblemBuilder};
use std::collections::HashSet;

/// Presolve techniques to simplify problems before solving
pub struct Presolve {
    /// Remove fixed variables
    pub fix_variables: bool,
    /// Remove redundant constraints
    pub remove_redundant: bool,
    /// Tighten variable bounds
    pub tighten_bounds: bool,
    /// Remove singleton constraints
    pub remove_singletons: bool,
    /// Maximum number of presolve rounds
    pub max_rounds: usize,
}

impl Default for Presolve {
    fn default() -> Self {
        Presolve {
            fix_variables: true,
            remove_redundant: true,
            tighten_bounds: true,
            remove_singletons: true,
            max_rounds: 10,
        }
    }
}

/// Result of presolve operations
#[derive(Debug, Clone)]
pub struct PresolveResult {
    /// The presolved problem
    pub problem: Problem,
    /// Variables that were fixed during presolve
    pub fixed_variables: Vec<(usize, f64)>,
    /// Constraints that were removed
    pub removed_constraints: Vec<usize>,
    /// Mapping from original to presolved variable indices
    pub variable_mapping: Vec<Option<usize>>,
    /// Statistics about presolve reductions
    pub statistics: PresolveStatistics,
}

/// Statistics from presolve operations
#[derive(Debug, Clone, Default)]
pub struct PresolveStatistics {
    pub original_variables: usize,
    pub original_constraints: usize,
    pub presolved_variables: usize,
    pub presolved_constraints: usize,
    pub fixed_variables: usize,
    pub removed_constraints: usize,
    pub rounds: usize,
}

impl Presolve {
    /// Creates a new presolve configuration
    pub fn new() -> Self {
        Self::default()
    }

    /// Applies presolve techniques to the problem
    pub fn apply(&self, problem: &Problem) -> ProblemResult<PresolveResult> {
        let mut current_problem = problem.clone();
        let mut fixed_variables = Vec::new();
        let mut removed_constraints = Vec::new();
        let variable_mapping: Vec<Option<usize>> = (0..problem.num_variables()).map(Some).collect();

        let original_stats = PresolveStatistics {
            original_variables: problem.num_variables(),
            original_constraints: problem.num_constraints(),
            presolved_variables: problem.num_variables(),
            presolved_constraints: problem.num_constraints(),
            fixed_variables: 0,
            removed_constraints: 0,
            rounds: 0,
        };

        let mut stats = original_stats;
        let mut changed = true;
        let mut round = 0;

        while changed && round < self.max_rounds {
            changed = false;
            round += 1;

            if self.fix_variables {
                let (new_problem, fixed) = self.fix_variables_pass(&current_problem)?;
                if !fixed.is_empty() {
                    current_problem = new_problem;
                    fixed_variables.extend(fixed);
                    changed = true;
                }
            }

            if self.remove_singletons {
                let (new_problem, removed) = self.remove_singleton_constraints(&current_problem)?;
                if !removed.is_empty() {
                    current_problem = new_problem;
                    removed_constraints.extend(removed);
                    changed = true;
                }
            }

            if self.remove_redundant {
                let (new_problem, removed) = self.remove_redundant_constraints(&current_problem)?;
                if !removed.is_empty() {
                    current_problem = new_problem;
                    removed_constraints.extend(removed);
                    changed = true;
                }
            }

            if self.tighten_bounds {
                let new_problem = self.tighten_variable_bounds(&current_problem)?;
                if !problems_equal(&current_problem, &new_problem) {
                    current_problem = new_problem;
                    changed = true;
                }
            }
        }

        stats.presolved_variables = current_problem.num_variables();
        stats.presolved_constraints = current_problem.num_constraints();
        stats.fixed_variables = fixed_variables.len();
        stats.removed_constraints = removed_constraints.len();
        stats.rounds = round;

        Ok(PresolveResult {
            problem: current_problem,
            fixed_variables,
            removed_constraints,
            variable_mapping,
            statistics: stats,
        })
    }

    /// Fixes variables that have equal upper and lower bounds
    fn fix_variables_pass(&self, problem: &Problem) -> ProblemResult<(Problem, Vec<(usize, f64)>)> {
        let mut builder = ProblemBuilder::new();
        let mut fixed_vars = Vec::new();
        let mut kept_vars = Vec::new();
        let epsilon = 1e-10;

        // Identify variables to fix
        for (i, var) in problem.variables.iter().enumerate() {
            if (var.upper_bound - var.lower_bound).abs() < epsilon {
                fixed_vars.push((i, var.lower_bound));
            } else {
                kept_vars.push((i, var));
            }
        }

        if fixed_vars.is_empty() {
            return Ok((problem.clone(), fixed_vars));
        }

        // Add non-fixed variables
        for (_, var) in &kept_vars {
            builder = builder.add_variable(&var.name, var.lower_bound, var.upper_bound)?;
        }

        // Adjust constraints
        for constraint in &problem.constraints {
            let mut new_coeffs = Vec::new();
            let mut adjusted_rhs = constraint.rhs;

            for (orig_idx, _) in &kept_vars {
                new_coeffs.push(constraint.coefficients[*orig_idx]);
            }

            // Subtract fixed variable contributions from RHS
            for (fixed_idx, fixed_value) in &fixed_vars {
                adjusted_rhs -= constraint.coefficients[*fixed_idx] * fixed_value;
            }

            if !new_coeffs.is_empty() {
                builder =
                    builder.add_constraint(new_coeffs, constraint.constraint_type, adjusted_rhs)?;
            }
        }

        // Adjust objective
        let mut new_obj_coeffs = Vec::new();
        let mut adjusted_constant = problem.objective.constant;

        for (orig_idx, _) in &kept_vars {
            new_obj_coeffs.push(problem.objective.coefficients[*orig_idx]);
        }

        // Add fixed variable contributions to constant
        for (fixed_idx, fixed_value) in &fixed_vars {
            adjusted_constant += problem.objective.coefficients[*fixed_idx] * fixed_value;
        }

        if !new_obj_coeffs.is_empty() {
            builder = builder.objective(new_obj_coeffs, problem.objective.objective_type)?;
        }

        let mut new_problem = builder.build()?;
        new_problem.objective.constant = adjusted_constant;

        Ok((new_problem, fixed_vars))
    }

    /// Removes constraints with only one non-zero coefficient
    fn remove_singleton_constraints(
        &self,
        problem: &Problem,
    ) -> ProblemResult<(Problem, Vec<usize>)> {
        let mut builder = ProblemBuilder::new();
        let mut removed_constraints = Vec::new();
        let epsilon = 1e-10;

        // Copy variables
        for var in &problem.variables {
            builder = builder.add_variable(&var.name, var.lower_bound, var.upper_bound)?;
        }

        // Check each constraint
        for (i, constraint) in problem.constraints.iter().enumerate() {
            let non_zero_count = constraint
                .coefficients
                .iter()
                .filter(|&&coeff| coeff.abs() > epsilon)
                .count();

            if non_zero_count <= 1 {
                // This is a singleton constraint - could be processed to fix a variable
                removed_constraints.push(i);
                // For now, we just remove it. A full implementation would fix the variable.
            } else {
                builder = builder.add_constraint(
                    constraint.coefficients.clone(),
                    constraint.constraint_type,
                    constraint.rhs,
                )?;
            }
        }

        // Copy objective
        builder = builder.objective(
            problem.objective.coefficients.clone(),
            problem.objective.objective_type,
        )?;

        let new_problem = builder.build()?;
        Ok((new_problem, removed_constraints))
    }

    /// Removes redundant constraints
    fn remove_redundant_constraints(
        &self,
        problem: &Problem,
    ) -> ProblemResult<(Problem, Vec<usize>)> {
        let mut builder = ProblemBuilder::new();
        let mut removed_constraints = Vec::new();
        let mut kept_constraints = HashSet::new();

        // Copy variables
        for var in &problem.variables {
            builder = builder.add_variable(&var.name, var.lower_bound, var.upper_bound)?;
        }

        // Simple redundancy check - remove duplicate constraints
        for (i, constraint) in problem.constraints.iter().enumerate() {
            let mut is_duplicate = false;

            for (j, other) in problem.constraints.iter().enumerate() {
                if i != j && !kept_constraints.contains(&j) {
                    if constraints_equivalent(constraint, other) {
                        is_duplicate = true;
                        break;
                    }
                }
            }

            if !is_duplicate {
                kept_constraints.insert(i);
                builder = builder.add_constraint(
                    constraint.coefficients.clone(),
                    constraint.constraint_type,
                    constraint.rhs,
                )?;
            } else {
                removed_constraints.push(i);
            }
        }

        // Copy objective
        builder = builder.objective(
            problem.objective.coefficients.clone(),
            problem.objective.objective_type,
        )?;

        let new_problem = builder.build()?;
        Ok((new_problem, removed_constraints))
    }

    /// Tightens variable bounds using constraint propagation
    fn tighten_variable_bounds(&self, problem: &Problem) -> ProblemResult<Problem> {
        let mut builder = ProblemBuilder::new();
        let mut new_bounds = Vec::new();

        // Initialize with current bounds
        for var in &problem.variables {
            new_bounds.push((var.lower_bound, var.upper_bound));
        }

        // Simple bound tightening using constraints
        for constraint in &problem.constraints {
            for (var_idx, &coeff) in constraint.coefficients.iter().enumerate() {
                if coeff.abs() < 1e-10 {
                    continue;
                }

                let (mut lower, mut upper) = new_bounds[var_idx];

                // Calculate implied bounds from this constraint
                let mut other_lower = 0.0;
                let mut other_upper = 0.0;

                for (other_idx, &other_coeff) in constraint.coefficients.iter().enumerate() {
                    if other_idx != var_idx && other_coeff.abs() > 1e-10 {
                        let (other_l, other_u) = new_bounds[other_idx];
                        if other_coeff > 0.0 {
                            other_lower += other_coeff * other_l;
                            other_upper += other_coeff * other_u;
                        } else {
                            other_lower += other_coeff * other_u;
                            other_upper += other_coeff * other_l;
                        }
                    }
                }

                // Apply constraint to get implied bounds
                match constraint.constraint_type {
                    ConstraintType::LessEqual => {
                        if coeff > 0.0 {
                            let implied_upper = (constraint.rhs - other_lower) / coeff;
                            upper = upper.min(implied_upper);
                        } else {
                            let implied_lower = (constraint.rhs - other_upper) / coeff;
                            lower = lower.max(implied_lower);
                        }
                    }
                    ConstraintType::GreaterEqual => {
                        if coeff > 0.0 {
                            let implied_lower = (constraint.rhs - other_upper) / coeff;
                            lower = lower.max(implied_lower);
                        } else {
                            let implied_upper = (constraint.rhs - other_lower) / coeff;
                            upper = upper.min(implied_upper);
                        }
                    }
                    ConstraintType::Equal => {
                        if coeff > 0.0 {
                            let implied_value = (constraint.rhs - other_lower) / coeff;
                            upper = upper.min(implied_value);
                            let implied_value = (constraint.rhs - other_upper) / coeff;
                            lower = lower.max(implied_value);
                        } else {
                            let implied_value = (constraint.rhs - other_upper) / coeff;
                            upper = upper.min(implied_value);
                            let implied_value = (constraint.rhs - other_lower) / coeff;
                            lower = lower.max(implied_value);
                        }
                    }
                }

                new_bounds[var_idx] = (lower, upper);
            }
        }

        // Build problem with tightened bounds
        for (i, var) in problem.variables.iter().enumerate() {
            let (lower, upper) = new_bounds[i];
            builder = builder.add_variable(&var.name, lower, upper)?;
        }

        // Copy constraints
        for constraint in &problem.constraints {
            builder = builder.add_constraint(
                constraint.coefficients.clone(),
                constraint.constraint_type,
                constraint.rhs,
            )?;
        }

        // Copy objective
        builder = builder.objective(
            problem.objective.coefficients.clone(),
            problem.objective.objective_type,
        )?;

        builder.build()
    }
}

/// Checks if two constraints are equivalent
fn constraints_equivalent(c1: &Constraint, c2: &Constraint) -> bool {
    use approx::AbsDiffEq;
    let epsilon = 1e-10;

    c1.constraint_type == c2.constraint_type
        && c1.coefficients.len() == c2.coefficients.len()
        && c1
            .coefficients
            .iter()
            .zip(c2.coefficients.iter())
            .all(|(&a, &b)| a.abs_diff_eq(&b, epsilon))
        && c1.rhs.abs_diff_eq(&c2.rhs, epsilon)
}

/// Checks if two problems are equal
fn problems_equal(p1: &Problem, p2: &Problem) -> bool {
    p1.num_variables() == p2.num_variables()
        && p1.num_constraints() == p2.num_constraints()
        && p1
            .variables
            .iter()
            .zip(p2.variables.iter())
            .all(|(v1, v2)| {
                v1.name == v2.name
                    && (v1.lower_bound - v2.lower_bound).abs() < 1e-10
                    && (v1.upper_bound - v2.upper_bound).abs() < 1e-10
            })
}

impl std::fmt::Display for PresolveStatistics {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "Presolve Statistics:")?;
        writeln!(
            f,
            "  Variables: {} -> {} ({} fixed)",
            self.original_variables, self.presolved_variables, self.fixed_variables
        )?;
        writeln!(
            f,
            "  Constraints: {} -> {} ({} removed)",
            self.original_constraints, self.presolved_constraints, self.removed_constraints
        )?;
        writeln!(f, "  Rounds: {}", self.rounds)?;
        let var_reduction = if self.original_variables > 0 {
            100.0 * (self.original_variables - self.presolved_variables) as f64
                / self.original_variables as f64
        } else {
            0.0
        };
        let con_reduction = if self.original_constraints > 0 {
            100.0 * (self.original_constraints - self.presolved_constraints) as f64
                / self.original_constraints as f64
        } else {
            0.0
        };
        writeln!(
            f,
            "  Reduction: {:.1}% variables, {:.1}% constraints",
            var_reduction, con_reduction
        )?;
        Ok(())
    }
}

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

    #[test]
    fn test_fix_variables() {
        let problem = ProblemBuilder::new()
            .add_variable("x1", 5.0, 5.0)
            .unwrap() // Fixed variable
            .add_variable("x2", 0.0, 10.0)
            .unwrap() // Free variable
            .add_constraint(vec![1.0, 1.0], ConstraintType::LessEqual, 15.0)
            .unwrap()
            .objective(vec![2.0, 3.0], ObjectiveType::Maximize)
            .unwrap()
            .build()
            .unwrap();

        let presolve = Presolve::new();
        let result = presolve.apply(&problem).unwrap();

        assert_eq!(result.fixed_variables.len(), 1);
        assert_eq!(result.fixed_variables[0], (0, 5.0));
        assert_eq!(result.problem.num_variables(), 1);
    }

    #[test]
    fn test_remove_redundant_constraints() {
        let problem = ProblemBuilder::new()
            .add_variable("x", 0.0, 10.0)
            .unwrap()
            .add_constraint(vec![1.0], ConstraintType::LessEqual, 5.0)
            .unwrap()
            .add_constraint(vec![1.0], ConstraintType::LessEqual, 5.0)
            .unwrap() // Duplicate
            .objective(vec![1.0], ObjectiveType::Maximize)
            .unwrap()
            .build()
            .unwrap();

        let presolve = Presolve::new();
        let result = presolve.apply(&problem).unwrap();

        assert_eq!(result.removed_constraints.len(), 1);
        assert_eq!(result.problem.num_constraints(), 1);
    }

    #[test]
    fn test_presolve_statistics() {
        let problem = ProblemBuilder::new()
            .add_variable("x1", 0.0, 0.0)
            .unwrap() // Will be fixed
            .add_variable("x2", 0.0, 10.0)
            .unwrap()
            .add_constraint(vec![1.0, 1.0], ConstraintType::LessEqual, 5.0)
            .unwrap()
            .add_constraint(vec![1.0, 1.0], ConstraintType::LessEqual, 5.0)
            .unwrap() // Duplicate
            .objective(vec![1.0, 2.0], ObjectiveType::Maximize)
            .unwrap()
            .build()
            .unwrap();

        let presolve = Presolve::new();
        let result = presolve.apply(&problem).unwrap();

        let stats = &result.statistics;
        assert_eq!(stats.original_variables, 2);
        assert_eq!(stats.original_constraints, 2);
        assert!(stats.presolved_variables < stats.original_variables);
        assert!(stats.presolved_constraints < stats.original_constraints);
    }
}
