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;
            }
        }
    }
}