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

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