use std::marker::PhantomData;
use nalgebra::{allocator::Allocator, DefaultAllocator, Dim};
use rand::{Rng, RngCore};
use eoa_lib::{fitness::FitnessFunction, perturbation::PerturbationOperator};
use crate::tsp::{NodePermutation, TSPInstance};

pub struct SwapPerturbation<D> {
    _phantom: PhantomData<D>
}

impl<D> SwapPerturbation<D> {
    pub fn new() -> Self {
        Self { _phantom: PhantomData }
    }
}

impl<D> PerturbationOperator for SwapPerturbation<D>
where
    D: Dim,
    DefaultAllocator: Allocator<D, D>,
    DefaultAllocator: Allocator<D>,
{
    type Chromosome = NodePermutation<D>;

    fn perturb(&self, chromosome: &mut Self::Chromosome, rng: &mut dyn RngCore) {
        let first = rng.random_range(0..chromosome.permutation.len());
        let second = rng.random_range(0..chromosome.permutation.len());
        chromosome.permutation.swap_rows(first, second);
    }
}

pub struct MovePerturbation<D> {
    _phantom: PhantomData<D>
}

impl<D> MovePerturbation<D> {
    pub fn new() -> Self {
        Self { _phantom: PhantomData }
    }
}

impl<D> PerturbationOperator for MovePerturbation<D>
where
    D: Dim,
    DefaultAllocator: Allocator<D, D>,
    DefaultAllocator: Allocator<D>,
{
    type Chromosome = NodePermutation<D>;

    fn perturb(&self, chromosome: &mut Self::Chromosome, rng: &mut dyn RngCore) {
        let from = rng.random_range(0..chromosome.permutation.len());
        let to = rng.random_range(0..chromosome.permutation.len());

        let element = chromosome.permutation[from];

        if from < to {
            for i in from..to {
                chromosome.permutation[i] = chromosome.permutation[i + 1];
            }
        } else {
            for i in (to+1..=from).rev() {
                chromosome.permutation[i] = chromosome.permutation[i - 1];
            }
        }

        chromosome.permutation[to] = element;
    }
}

pub struct ReverseSubsequencePerturbation<D> {
    _phantom: PhantomData<D>,
    min_subsequence_len: usize,
    max_subsequence_len: usize,
}

impl<D> ReverseSubsequencePerturbation<D> {
    pub fn new() -> Self {
        Self {
            _phantom: PhantomData,
            max_subsequence_len: usize::MAX,
            min_subsequence_len: 0,
        }
    }
}

impl<D> PerturbationOperator for ReverseSubsequencePerturbation<D>
where
    D: Dim,
    DefaultAllocator: Allocator<D, D>,
    DefaultAllocator: Allocator<D>,
{
    type Chromosome = NodePermutation<D>;

    fn perturb(&self, chromosome: &mut Self::Chromosome, rng: &mut dyn RngCore) {
        let len = chromosome.permutation.len();
        let index = rng.random_range(0..chromosome.permutation.len());
        let subsequence_len = rng.random_range(
            self.min_subsequence_len..(chromosome.permutation.len().min(self.max_subsequence_len))
        );

        // Reverse the subsequence between start and end (inclusive)
        let mut left = index;
        let mut right = (index + subsequence_len) % len;

        while left != right {
            chromosome.permutation.swap_rows(left, right);

            left += 1;
            left %= len;

            if left == right {
                break;
            }

            if right > 0 {
                right -= 1;
            } else {
                right = len - 1;
            }
        }
    }
}

pub struct Random2OptPerturbation<D>
where
    D: Dim,
    DefaultAllocator: nalgebra::allocator::Allocator<D, D>
{
    instance: TSPInstance<D>,
    retries: usize,
    reversal: ReverseSubsequencePerturbation<D>,
    _phantom: PhantomData<D>
}

impl<D> Random2OptPerturbation<D>
where
    D: Dim,
    DefaultAllocator: nalgebra::allocator::Allocator<D, D>
{
    pub fn new(instance: &TSPInstance<D>, retries: usize) -> Self {
        let mut reversal = ReverseSubsequencePerturbation::new();
        reversal.min_subsequence_len = 5;
        reversal.max_subsequence_len = 15;

        Self {
            retries,
            instance: instance.clone(),
            reversal,
            _phantom: PhantomData
        }
    }
}

impl<D> PerturbationOperator for Random2OptPerturbation<D>
where
    D: Dim,
    DefaultAllocator: nalgebra::allocator::Allocator<D>,
    DefaultAllocator: nalgebra::allocator::Allocator<D, D>,
{
    type Chromosome = NodePermutation<D>;

    fn perturb(&self, chromosome: &mut Self::Chromosome, rng: &mut dyn RngCore) {
        let original_fitness = self.instance.fit(chromosome).unwrap();

        for _ in 0..self.retries {
            let mut cloned = chromosome.clone();
            self.reversal.perturb(&mut cloned, rng);
            let new_fitness = self.instance.fit(&cloned).unwrap();
            if new_fitness < original_fitness {
                std::mem::swap(chromosome, &mut cloned);
                return;
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use nalgebra::{Const, SVector};
    use rand::{rngs::StdRng, SeedableRng};
    use crate::tsp::{NodePermutation, TSPInstance};
    use crate::initializers::TSPRandomInitializer;
    use eoa_lib::initializer::Initializer;

    #[test]
    fn test_reverse_subsequence_perturbation_behavior() {
        let perturbation = ReverseSubsequencePerturbation::<Const<6>>::new();

        // Test multiple specific seeds to get predictable behavior
        // We'll try different seeds until we find ones that give us the patterns we want to test

        // Test case 1: Try to find a seed that reverses a middle subsequence
        let mut found_middle_reverse = false;
        for seed in 0..1000 {
            let mut rng = StdRng::seed_from_u64(seed);
            let mut chromosome = NodePermutation::<Const<6>> {
                permutation: SVector::<usize, 6>::from_vec(vec![0, 1, 2, 3, 4, 5])
            };
            let original = chromosome.clone();

            perturbation.perturb(&mut chromosome, &mut rng);

            // Check if it's a valid reverse pattern and not the whole array or single element
            let result: Vec<usize> = chromosome.permutation.into_iter().copied().collect();
            if result != vec![0, 1, 2, 3, 4, 5] && // Changed
               result != vec![5, 4, 3, 2, 1, 0] && // Not whole array reverse
               TSPInstance::verify_solution(&chromosome) {
                found_middle_reverse = true;
                break;
            }
        }
        assert!(found_middle_reverse, "Should find at least one case of partial subsequence reversal");
    }

    #[test]
    fn test_reverse_subsequence_perturbation_deterministic_seed() {
        let perturbation = ReverseSubsequencePerturbation::<Const<6>>::new();

        // Use a specific seed that we know produces a certain result
        let mut rng1 = StdRng::seed_from_u64(42);
        let mut chromosome1 = NodePermutation::<Const<6>> {
            permutation: SVector::<usize, 6>::from_vec(vec![0, 1, 2, 3, 4, 5])
        };
        perturbation.perturb(&mut chromosome1, &mut rng1);

        // Same seed should produce same result
        let mut rng2 = StdRng::seed_from_u64(42);
        let mut chromosome2 = NodePermutation::<Const<6>> {
            permutation: SVector::<usize, 6>::from_vec(vec![0, 1, 2, 3, 4, 5])
        };
        perturbation.perturb(&mut chromosome2, &mut rng2);

        assert_eq!(chromosome1.permutation, chromosome2.permutation);
        assert!(TSPInstance::verify_solution(&chromosome1));
        assert!(TSPInstance::verify_solution(&chromosome2));
    }

    #[test]
    fn test_reverse_subsequence_perturbation_different_initial_permutations() {
        let perturbation = ReverseSubsequencePerturbation::<Const<5>>::new();

        // Test with a non-sequential initial permutation
        let mut rng = StdRng::seed_from_u64(123);
        let mut chromosome = NodePermutation::<Const<5>> {
            permutation: SVector::<usize, 5>::from_vec(vec![2, 0, 4, 1, 3])
        };
        let original_elements: std::collections::HashSet<usize> =
            chromosome.permutation.iter().copied().collect();

        perturbation.perturb(&mut chromosome, &mut rng);

        // Verify all original elements are still present
        let new_elements: std::collections::HashSet<usize> =
            chromosome.permutation.iter().copied().collect();
        assert_eq!(original_elements, new_elements);

        // Verify it's still a valid permutation
        assert!(TSPInstance::verify_solution(&chromosome));
    }

    #[test]
    fn test_reverse_subsequence_perturbation_edge_cases() {
        let perturbation = ReverseSubsequencePerturbation::<Const<2>>::new();

        // Test with minimum size permutation (2 elements)
        let mut rng = StdRng::seed_from_u64(456);
        let mut chromosome = NodePermutation::<Const<2>> {
            permutation: SVector::<usize, 2>::from_vec(vec![0, 1])
        };

        perturbation.perturb(&mut chromosome, &mut rng);

        let result: Vec<usize> = chromosome.permutation.into_iter().copied().collect();
        // With 2 elements, it should either stay [0,1] or become [1,0]
        assert!(result == vec![0, 1] || result == vec![1, 0]);
        assert!(TSPInstance::verify_solution(&chromosome));
    }

    #[test]
    fn test_reverse_subsequence_perturbation_is_reversible() {
        let perturbation = ReverseSubsequencePerturbation::<Const<6>>::new();

        // Any sequence of reversals should be reversible
        let mut rng = StdRng::seed_from_u64(789);
        let original = NodePermutation::<Const<6>> {
            permutation: SVector::<usize, 6>::from_vec(vec![0, 1, 2, 3, 4, 5])
        };
        let mut chromosome = original.clone();

        // Apply perturbation twice with same seed (reset RNG)
        perturbation.perturb(&mut chromosome, &mut rng);
        let after_first = chromosome.clone();

        // Since we can't easily reverse the exact operation, at least verify
        // that multiple applications maintain the permutation property
        for _ in 0..10 {
            perturbation.perturb(&mut chromosome, &mut rng);
            assert!(TSPInstance::verify_solution(&chromosome));
        }
    }

    #[test]
    fn test_reverse_subsequence_perturbation_preserves_elements() {
        let perturbation = ReverseSubsequencePerturbation::<Const<10>>::new();
        let initializer = TSPRandomInitializer::<Const<10>>::new();

        let mut rng = StdRng::seed_from_u64(42);

        // Test with multiple random permutations
        for _ in 0..50 {
            let mut chromosome = initializer.initialize_single(Const::<10>, &mut rng);
            let original_elements: std::collections::HashSet<usize> = chromosome.permutation.iter().copied().collect();

            perturbation.perturb(&mut chromosome, &mut rng);

            // Verify all elements are still present
            let new_elements: std::collections::HashSet<usize> = chromosome.permutation.iter().copied().collect();
            assert_eq!(original_elements, new_elements);

            // Verify it's still a valid permutation
            assert!(TSPInstance::verify_solution(&chromosome));
        }
    }

    #[test]
    fn test_reverse_subsequence_perturbation_actually_changes_permutation() {
        let perturbation = ReverseSubsequencePerturbation::<Const<8>>::new();
        let mut rng = StdRng::seed_from_u64(12345);

        // Test that the perturbation actually changes the permutation (with high probability)
        let mut changes_detected = 0;
        let total_tests = 100;

        for _ in 0..total_tests {
            let mut chromosome = NodePermutation::<Const<8>> {
                permutation: SVector::<usize, 8>::from_vec(vec![0, 1, 2, 3, 4, 5, 6, 7])
            };
            let original = chromosome.clone();

            perturbation.perturb(&mut chromosome, &mut rng);

            if chromosome.permutation != original.permutation {
                changes_detected += 1;
            }

            // Always verify it's still a valid permutation
            assert!(TSPInstance::verify_solution(&chromosome));
        }

        // We expect at least 85% of random perturbations to actually change the permutation
        // (only fails if start == end randomly, which should be rare)
        assert!(changes_detected >= 85,
            "Expected at least 85 changes out of {} tests, but got {}",
            total_tests, changes_detected);
    }
}