meiosis 0.1.0

use core::marker::PhantomData;

use rand::seq::IteratorRandom;
use rand::Rng;

use crate::environment::Environment;
use crate::fitness::Fitness;
use crate::genotype::{Distance, Genotype};
use crate::operators::mutation::Mutation;
use crate::operators::recombination::Recombination;
use crate::operators::selection::Selection;
use crate::phenotype::FromGenotype;
use crate::phenotype::Phenotype;
use crate::random::Random;
use crate::species::{
    Bare, Evaluated as EvaluatedMember, EvaluatedPopulation, EvaluatedSpecies, Parents, Population, Species,
};
use crate::termination::Termination;

/// Fitness-based genetic algorithms evaluate the fitness of each `Phenotype` and select based on it.

/// All parameters are unknown.
#[derive(Copy, Clone, Debug)]
#[non_exhaustive]
pub struct Unconfigured;

/// MISSING DOCS
#[derive(Debug)]
pub struct WithRNG<RNG> {
    /// MISSING DOCS
    rng: RNG,
}

/// MISSING DOCS
#[derive(Debug)]
pub struct WithoutOperators<RNG, ENVIRONMENT> {
    /// MISSING DOCS
    rng: RNG,
    /// MISSING DOCS
    environment: ENVIRONMENT,
}

/// MISSING DOCS
#[derive(Debug)]
pub struct WithSelection<RNG, ENVIRONMENT, SELECTION> {
    /// MISSING DOCS
    rng: RNG,
    /// MISSING DOCS
    environment: ENVIRONMENT,
    /// MISSING DOCS
    selection: SELECTION,
}

/// MISSING DOCS
#[derive(Debug)]
pub struct WithRecombination<RNG, ENVIRONMENT, SELECTION, RECOMBINATION> {
    /// MISSING DOCS
    rng: RNG,
    /// MISSING DOCS
    environment: ENVIRONMENT,
    /// MISSING DOCS
    selection: SELECTION,
    /// MISSING DOCS
    recombination: RECOMBINATION,
}

/// MISSING DOCS
#[derive(Debug)]
pub struct WithoutTermination<RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION> {
    /// MISSING DOCS
    rng: RNG,
    /// MISSING DOCS
    environment: ENVIRONMENT,
    /// MISSING DOCS
    selection: SELECTION,
    /// MISSING DOCS
    recombination: RECOMBINATION,
    /// MISSING DOCS
    mutation: MUTATION,
}

/// This type is used to build a genetic algorithm configuration so it can be passed to the actual
/// algorithm, ready for use. By separating the basic configuration into this struct, we keep the
/// main algorithm state machine smaller and more manageable.
#[derive(Debug)]
pub struct Configuration<STATE> {
    /// MISSING DOCS
    state: STATE,
}

impl Configuration<Unconfigured> {
    /// Create a new fully unconfigured [Configuration] for the [Classic] algorithm.
    #[must_use]
    pub const fn new() -> Configuration<Unconfigured> {
        Configuration { state: Unconfigured {} }
    }

    /// Set the random number generator the [Classic] algorithm will use.
    // Adding `const` causes Rust to complain about not being able to evaluate the destructor at compile-time.
    #[allow(clippy::missing_const_for_fn)]
    pub fn with_rng<RNG>(self, rng: RNG) -> Configuration<WithRNG<RNG>>
    where
        RNG: Rng,
    {
        Configuration { state: WithRNG { rng } }
    }
}

impl<RNG> Configuration<WithRNG<RNG>> {
    /// MISSING DOCS
    // Adding `const` causes Rust to complain about not being able to evaluate the destructor at compile-time.
    #[allow(clippy::missing_const_for_fn)]
    pub fn with_environment<ENVIRONMENT>(
        self,
        environment: ENVIRONMENT,
    ) -> Configuration<WithoutOperators<RNG, ENVIRONMENT>>
    where
        ENVIRONMENT: Environment,
    {
        Configuration {
            state: WithoutOperators {
                rng: self.state.rng,
                environment,
            },
        }
    }
}

impl<RNG, ENVIRONMENT> Configuration<WithoutOperators<RNG, ENVIRONMENT>> {
    /// MISSING DOCS
    // Adding `const` causes Rust to complain about not being able to evaluate the destructor at compile-time.
    #[allow(clippy::missing_const_for_fn)]
    pub fn with_selection<SELECTION>(
        self,
        selection: SELECTION,
    ) -> Configuration<WithSelection<RNG, ENVIRONMENT, SELECTION>> {
        Configuration {
            state: WithSelection {
                rng: self.state.rng,
                environment: self.state.environment,
                selection,
            },
        }
    }
}

impl<RNG, ENVIRONMENT, SELECTION> Configuration<WithSelection<RNG, ENVIRONMENT, SELECTION>> {
    /// MISSING DOCS
    // Adding `const` causes Rust to complain about not being able to evaluate the destructor at compile-time.
    #[allow(clippy::missing_const_for_fn)]
    pub fn with_recombination<RECOMBINATION>(
        self,
        recombination: RECOMBINATION,
    ) -> Configuration<WithRecombination<RNG, ENVIRONMENT, SELECTION, RECOMBINATION>> {
        Configuration {
            state: WithRecombination {
                rng: self.state.rng,
                environment: self.state.environment,
                selection: self.state.selection,
                recombination,
            },
        }
    }
}

impl<RNG, ENVIRONMENT, SELECTION, RECOMBINATION>
    Configuration<WithRecombination<RNG, ENVIRONMENT, SELECTION, RECOMBINATION>>
{
    /// MISSING DOCS
    // Adding `const` causes Rust to complain about not being able to evaluate the destructor at compile-time.
    #[allow(clippy::missing_const_for_fn)]
    pub fn with_mutation<MUTATION>(
        self,
        mutation: MUTATION,
    ) -> Configuration<WithoutTermination<RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION>> {
        Configuration {
            state: WithoutTermination {
                rng: self.state.rng,
                environment: self.state.environment,
                selection: self.state.selection,
                recombination: self.state.recombination,
                mutation,
            },
        }
    }
}

impl<RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION>
    Configuration<WithoutTermination<RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION>>
{
    /// MISSING DOCS
    // Adding `const` causes Rust to complain about not being able to evaluate the destructor at compile-time.
    #[allow(clippy::missing_const_for_fn)]
    pub fn with_termination<TERMINATION, GENOTYPE>(
        self,
        termination: TERMINATION,
    ) -> Classic<Configured, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION> {
        Classic {
            state: Configured {},
            genotype: PhantomData,
            rng: self.state.rng,
            environment: self.state.environment,
            selection: self.state.selection,
            recombination: self.state.recombination,
            mutation: self.state.mutation,
            termination,
            max_population: 0,
            elites: 0,
            elite_members: vec![],
            speciation_threshold: 0.0,
            interspecies_breeding_chance: 0.0,
            statistics: Statistics { iteration: 0 },
        }
    }
}

/// We're in this state before we start the main loop.
#[derive(Copy, Clone, Debug)]
#[non_exhaustive]
pub struct Configured;

/// This is the first state which either a newly set up algorithm is in, or if it has done a
/// full iteration.
#[derive(Debug)]
pub struct Unevaluated<GENOTYPE> {
    /// MISSING DOCS
    species: Vec<Species<GENOTYPE>>,
}

impl<GENOTYPE> Unevaluated<GENOTYPE> {
    /// MISSING DOCS
    #[must_use]
    pub const fn species(&self) -> &Vec<Species<GENOTYPE>> {
        &self.species
    }
}

/// In this state [Genotype]s have been converted to [Phenotype]s and were evaluated.
#[derive(Debug, PartialEq)]
pub struct Evaluated<PHENOTYPE> {
    /// MISSING DOCS
    species: Vec<EvaluatedSpecies<PHENOTYPE>>,
}

impl<PHENOTYPE> Evaluated<PHENOTYPE> {
    /// MISSING DOCS
    #[must_use]
    pub const fn species(&self) -> &Vec<EvaluatedSpecies<PHENOTYPE>> {
        &self.species
    }
}

/// Using the evaluated [Genotype]s, the selection will split them in two groups, selected and non-selected members.
#[derive(Debug)]
pub struct Selected<PHENOTYPE> {
    /// MISSING DOCS
    selected: Vec<Parents<PHENOTYPE>>,
}

impl<PHENOTYPE> Selected<PHENOTYPE> {
    /// MISSING DOCS
    #[must_use]
    pub const fn selected(&self) -> &Vec<Parents<PHENOTYPE>> {
        &self.selected
    }
}

/// After parents have been chosen and used to create offspring, their non-mutated children are stored in this state.
#[derive(Debug)]
pub struct Recombined<GENOTYPE> {
    /// MISSING DOCS
    species: Vec<Bare<GENOTYPE>>,
    /// MISSING DOCS
    new_members: Population<GENOTYPE>,
}

impl<GENOTYPE> Recombined<GENOTYPE> {
    /// MISSING DOCS
    #[must_use]
    pub const fn species(&self) -> &Vec<Bare<GENOTYPE>> {
        &self.species
    }
}

/// MISSING DOCS
#[derive(Debug)]
pub struct Mutated<GENOTYPE> {
    /// MISSING DOCS
    species: Vec<Bare<GENOTYPE>>,
    /// MISSING DOCS
    new_members: Population<GENOTYPE>,
}

/// Should a [Termination] strategy determine that our algorithm is done, will we end up in this state.
#[derive(Debug)]
pub struct Terminated<PHENOTYPE> {
    /// MISSING DOCS
    species: Vec<EvaluatedSpecies<PHENOTYPE>>,
}

impl<PHENOTYPE> Terminated<PHENOTYPE> {
    /// MISSING DOCS
    #[must_use]
    pub const fn species(&self) -> &Vec<EvaluatedSpecies<PHENOTYPE>> {
        &self.species
    }
}

/// The classic genetic algorithm with optional elitism and speciation.
///
/// # Features
/// ## Speciation
/// Note that if this feature is turned "off" the whole population is seen as a single species.
///
/// Generalized, these are the steps (and in which state transition it happens):
/// 1. use previous species to categorize new members (setup or reinsertion)
/// 2. calculate shared fitness and store result per species (evaluation)
/// 3. set new representatives of species using a random member and set maximum species size depending on shared fitness (selection)
/// 4. apply selection and recombination on species
/// 5. go to 1.
///
/// ### Preparation
/// Before the first iteration starts, the initial population is separated into species using random
/// members of the population.
///
/// Steps:
/// 1. take random member
/// 2. check against existing species whether the member has a genetic distance below the threshold
/// 3. if so, assign member to species, if not, create a new species with this member as their representative
///
/// ### Calculating a shared fitness
/// The shared fitness is used to determine the size of species for the next generation. Species
/// scale by performance, which means if a new species comes along with similar or better performance,
/// it quickly suppresses less optimal solutions, yet does not fully out-compete them.
/// The shared fitness of an individual is calculated by dividing their actual fitness by
/// the amount of members in their species.
///
/// ### Species in [`Selection`] and [`Recombination`]
/// The point of speciation is to not have a fight over the global fitness, but instead allow
/// for multiple equally good solutions to survive in their own niche. This means that when it comes
/// to selection, we no longer apply it to the population as a whole and instead do it for each
/// species. Not all selection strategies are suitable, and it is recommended to use those that at
/// least eliminate a single member per species. The simplest one would be [`Truncation`] with a
/// proportion-to-keep of 99%, even though it may not be the most efficient.
///
/// For each species recombination is then applied till the species is filled to their allowed
/// member count. The member count is always at least one, but if that happens and the next
/// iteration does not produce a better offspring the species dies.
///
/// ### Preparing the next generation
/// Similar to the pre-loop preparation, we need to define the representatives of a species.
///
/// TODO: move the above docs to the function they apply to (e.g. shared fitness to evaluation)
#[derive(Debug, PartialEq)]
pub struct Classic<STATE, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION> {
    /// MISSING DOCS
    state: STATE,

    /// MISSING DOCS
    genotype: PhantomData<GENOTYPE>,

    // basics
    /// MISSING DOCS
    rng: RNG,
    /// MISSING DOCS
    environment: ENVIRONMENT,

    // behaviour
    /// MISSING DOCS
    selection: SELECTION,
    /// MISSING DOCS
    recombination: RECOMBINATION,
    /// MISSING DOCS
    mutation: MUTATION,
    /// MISSING DOCS
    termination: TERMINATION,

    /// # Aliases
    /// Generation, Loop
    max_population: usize,

    /// MISSING DOCS
    elites: usize,
    /// MISSING DOCS
    elite_members: Vec<GENOTYPE>,

    /// MISSING DOCS
    speciation_threshold: f32,
    /// MISSING DOCS
    interspecies_breeding_chance: f64,

    /// MISSING DOCS
    statistics: Statistics,
}

/// MISSING DOCS
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct Statistics {
    /// MISSING DOCS
    pub iteration: usize,
    // TODO: ideally we would want an Instant here, but that requires `std`
    //start: Instant,
}

impl<STATE, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    Classic<STATE, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
{
    /// If instead of using [`Classic::run`] the algorithm is being iterated over manually,
    /// this function can return the state at any point in the algorithm.
    pub const fn state(&self) -> &STATE {
        &self.state
    }

    /// MISSING DOCS
    pub const fn statistics(&self) -> &Statistics {
        &self.statistics
    }
}

impl<GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    Classic<Unconfigured, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
{
    /// Create a new fully unconfigured [Configuration] for the [Classic] algorithm.
    #[must_use]
    pub const fn configure() -> Configuration<Unconfigured> {
        Configuration { state: Unconfigured {} }
    }
}

/// As we're all set up and ready to go, the only thing missing are some optional configurations and
/// an initial population.
impl<GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    Classic<Configured, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
{
    /// An already created population is used to instantiate the classic genetic algorithm.
    /// This also sets the maximum population size to the size of the given population.
    pub fn with_population(
        mut self,
        population: Population<GENOTYPE>,
    ) -> Classic<Unevaluated<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    where
        GENOTYPE: Distance + Clone,
    {
        self.max_population = population.members.len();

        let species = self.species_from_initial_population(population);
        let state = Unevaluated { species };

        Classic {
            state,
            genotype: self.genotype,
            rng: self.rng,
            environment: self.environment,
            selection: self.selection,
            recombination: self.recombination,
            mutation: self.mutation,
            termination: self.termination,
            max_population: self.max_population,
            elites: self.elites,
            elite_members: self.elite_members,
            speciation_threshold: self.speciation_threshold,
            interspecies_breeding_chance: self.interspecies_breeding_chance,
            statistics: self.statistics,
        }
    }

    /// This is a convenience function that'll create a random population instead of having to
    /// instantiate one using [`Population::random`].
    pub fn with_random_population(
        mut self,
        size: usize,
    ) -> Classic<Unevaluated<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    where
        GENOTYPE: Random + Distance + Clone,
        RNG: Rng,
    {
        let members = (0..size).map(|_| GENOTYPE::random(&mut self.rng)).collect();
        let population = Population { members };

        self.with_population(population)
    }

    /// This is a convenience function that'll create a seeded population instead of having to
    /// instantiate one using [`Population::seeded`].
    #[allow(clippy::todo, clippy::needless_pass_by_value, clippy::missing_panics_doc)]
    pub fn with_seeded_population(
        _seed: impl FromIterator<GENOTYPE>,
        _size: usize,
    ) -> Classic<Unevaluated<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    {
        todo!()
    }

    /// Define how many top solutions shall simply be copied over to the next generation.
    /// If speciation is active, this counts per species.
    #[must_use]
    pub const fn with_elitism(mut self, elites: usize) -> Self {
        self.elites = elites;
        self
    }

    /// Define the genetic distance at which two members are considered members of two distinct
    /// species. This value is normalized and so at 1.0 they are completely different, where as
    /// at 0.0 they are clones of each other.
    ///
    /// # Recommended value
    /// A value higher than 80% (0.8) gives the best results, but it entirely depends on the
    /// genotype. If speciation should only happen rarely, a value very close to one might be best.
    ///
    /// # Note
    /// Zero disables the feature (all members are considered part of the same species).
    ///
    /// # Panics
    /// This value is normalized, thus it needs to be in the range of `[0.0, 1.0]`.
    /// It is checked at runtime to be inside said range.
    #[must_use]
    pub fn with_speciation_threshold(mut self, threshold: f32) -> Self {
        assert!(
            (0.0..=1.0_f32).contains(&threshold),
            "speciation threshold has to be in the range [0.0, 1.0], value is: {}",
            threshold
        );

        self.speciation_threshold = threshold;
        self
    }

    /// MISSING DOCS
    ///
    /// # Note
    /// Zero disables the feature disables.
    ///
    /// # Panics
    /// This value needs to be in the range of `[0.0, 1.0]`.
    /// It is checked at runtime to be inside said range.
    #[must_use]
    pub fn with_interspecies_breeding_chance(mut self, chance: f64) -> Self {
        assert!(
            (0.0_f64..=1.0_f64).contains(&chance),
            "interbreeding chance has to be in the range [0.0, 1.0], value is: {}",
            chance
        );

        self.interspecies_breeding_chance = chance;
        self
    }

    /// MISSING DOCS
    fn species_from_initial_population(&self, population: Population<GENOTYPE>) -> Vec<Species<GENOTYPE>>
    where
        GENOTYPE: Distance + Clone,
    {
        sort_population_to_species(1, Vec::new(), population, self.speciation_threshold)
    }
}

/// In this state we can go three ways:
/// - run to completion
/// - run a single iteration
/// - manual path, starting with evaluation
impl<GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    Classic<Unevaluated<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
where
    GENOTYPE: Genotype,
    RNG: Rng,
    ENVIRONMENT: Environment,
    RECOMBINATION: Recombination<GENOTYPE>,
{
    /// # Errors
    /// This function returns `Err` if `TERMINATION` has determined to stop the algorithm.
    /// Possible cases can for example be a reached fitness or a certain amount of iterations have elapsed.
    /// TODO: implement a way to return *what* terminated the algorithm
    // Because of the generic parameters we can not simplify this, so we have to allow the lint.
    #[allow(clippy::type_complexity)]
    pub fn run<PHENOTYPE>(
        mut self,
    ) -> Result<
        Self,
        Classic<Terminated<PHENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>,
    >
    where
        PHENOTYPE: Phenotype<Genotype = GENOTYPE> + FromGenotype<GENOTYPE, ENVIRONMENT> + Fitness<ENVIRONMENT> + Clone,
        GENOTYPE: Random + Distance + Clone + PartialEq,
        SELECTION: Selection<PHENOTYPE>,
        MUTATION: Mutation<GENOTYPE, RNG>,
        TERMINATION: Termination<PHENOTYPE>,
        [(); RECOMBINATION::OFFSPRING]:,
        [(); RECOMBINATION::PARENTS]:,
    {
        loop {
            self = self.iteration()?;
        }
    }

    /// # Errors
    /// This function returns `Err` if `TERMINATION` has determined to stop the algorithm.
    /// Possible cases can for example be a reached fitness or a certain amount of iterations have elapsed.
    /// TODO: implement a way to return *what* terminated the algorithm
    // Because of the generic parameters we can not simplify this, so we have to allow the lint.
    #[allow(clippy::type_complexity)]
    pub fn iteration<PHENOTYPE>(
        self,
    ) -> Result<
        Self,
        Classic<Terminated<PHENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>,
    >
    where
        PHENOTYPE: Phenotype<Genotype = GENOTYPE> + FromGenotype<GENOTYPE, ENVIRONMENT> + Fitness<ENVIRONMENT> + Clone,
        GENOTYPE: Random + Distance + Clone + PartialEq,
        SELECTION: Selection<PHENOTYPE>,
        MUTATION: Mutation<GENOTYPE, RNG>,
        TERMINATION: Termination<PHENOTYPE>,
        [(); RECOMBINATION::OFFSPRING]:,
        [(); RECOMBINATION::PARENTS]:,
    {
        Ok(self
            .evaluate()
            .check_termination()?
            .select()
            .recombine()
            .mutate()
            .reinsert())
    }

    /// MISSING DOCS
    pub fn evaluate<PHENOTYPE>(
        mut self,
    ) -> Classic<Evaluated<PHENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    where
        PHENOTYPE: Phenotype<Genotype = GENOTYPE> + FromGenotype<GENOTYPE, ENVIRONMENT> + Fitness<ENVIRONMENT> + Clone,
        GENOTYPE: Clone + PartialEq,
    {
        let Unevaluated { species } = self.state;

        #[allow(clippy::shadow_reuse, clippy::shadow_unrelated, clippy::float_arithmetic)]
        let species = species
            .into_iter()
            .map(|species| {
                #[allow(clippy::cast_precision_loss, clippy::as_conversions)]
                let species_size = species.population.members.len() as f64;

                // construct Phenotypes from Genotypes
                let phenotypes = species
                    .population
                    .members
                    .into_iter()
                    .map(|genotype| PHENOTYPE::from_genotype(&mut self.rng, genotype, &self.environment));

                // evaluate them and calculate their shared fitness
                let evaluated = phenotypes
                    .map(|phenotype| {
                        let fitness = phenotype.fitness(&self.environment);
                        let shared_fitness = fitness / species_size;

                        EvaluatedMember {
                            phenotype,
                            fitness,
                            adjusted_fitness: shared_fitness,
                        }
                    })
                    .collect::<Vec<_>>();

                let species_total_adjusted_fitness = evaluated
                    .iter()
                    .map(|e| e.adjusted_fitness)
                    .fold(0.0_f64, |sum, fitness| sum + fitness);

                EvaluatedSpecies {
                    identifier: species.identifier,
                    sum_adjusted_fitness: species_total_adjusted_fitness, /* / species_size,*/
                    population: EvaluatedPopulation { members: evaluated },
                }
            })
            .collect();

        // evaluation is always the start of a new iteration
        self.statistics.iteration = self.statistics.iteration.saturating_add(1);
        let state = Evaluated { species };

        Classic {
            state,
            genotype: self.genotype,
            rng: self.rng,
            environment: self.environment,
            selection: self.selection,
            recombination: self.recombination,
            mutation: self.mutation,
            termination: self.termination,
            max_population: self.max_population,
            elites: self.elites,
            elite_members: self.elite_members,
            speciation_threshold: self.speciation_threshold,
            interspecies_breeding_chance: self.interspecies_breeding_chance,
            statistics: self.statistics,
        }
    }
}

/// Once evaluated we can go to two other states: either we check if we have reached some
/// termination condition or we simply keep going and start selection. This might be a helpful
/// optimization if it is known at compile time, that this algorithm will not trigger a termination
/// condition, thus making the check a waste of CPU cycles, especially because it goes over a
/// `vtable` to run them.
///
/// An example for this case might be that there are three termination conditions, but it is known
/// the algorithm won't finish earlier than one million generations into the run. It becomes
/// cheaper to manually check this single condition than to check all three every generation.
impl<PHENOTYPE, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    Classic<Evaluated<PHENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
{
    /// # Errors
    /// This function returns `Err` if `TERMINATION` has determined to stop the algorithm.
    /// Possible cases can for example be a reached fitness or a certain amount of iterations have elapsed.
    /// TODO: implement a way to return *what* terminated the algorithm
    // Because of the generic parameters we can not simplify this, so we have to allow the lint.
    #[allow(clippy::type_complexity)]
    pub fn check_termination(
        mut self,
    ) -> Result<
        Self,
        Classic<Terminated<PHENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>,
    >
    where
        TERMINATION: Termination<PHENOTYPE>,
    {
        if self.termination.terminate(&self.statistics, &self.state.species) {
            let state = Terminated {
                species: self.state.species,
            };

            Err(Classic {
                state,
                genotype: self.genotype,
                rng: self.rng,
                environment: self.environment,
                selection: self.selection,
                recombination: self.recombination,
                mutation: self.mutation,
                termination: self.termination,
                max_population: self.max_population,
                elites: self.elites,
                elite_members: self.elite_members,
                speciation_threshold: self.speciation_threshold,
                interspecies_breeding_chance: self.interspecies_breeding_chance,
                statistics: self.statistics,
            })
        } else {
            Ok(self)
        }
    }

    /// MISSING DOCS
    #[allow(clippy::too_many_lines)]
    pub fn select(
        mut self,
    ) -> Classic<Selected<PHENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    where
        PHENOTYPE: Phenotype<Genotype = GENOTYPE> + Clone,
        RNG: Rng,
        SELECTION: Selection<PHENOTYPE>,
    {
        #[allow(clippy::float_arithmetic)]
        let total_adjusted_fitness = self
            .state
            .species
            .iter()
            .map(|s| s.sum_adjusted_fitness)
            .fold(0.0_f64, |sum, fitness| sum + fitness);

        let selected: Vec<Parents<PHENOTYPE>> = if total_adjusted_fitness == 0.0 {
            // if we hit a special case of the whole population having a sum fitness
            // of zero, then we simply pass through the current species as is, in the hope
            // that recombination and mutation produce some more useful solutions
            self.state
                .species
                .into_iter()
                .map(|species| {
                    // a species always has members in this state
                    #[allow(clippy::expect_used)]
                    let representative = species
                        .population
                        .members
                        .iter()
                        .choose(&mut self.rng)
                        .expect("selection should not be empty")
                        .phenotype
                        .clone();

                    Parents {
                        identifier: species.identifier,
                        max_size: species.population.members.len(),
                        representative,
                        population: species.population,
                    }
                })
                .collect()
        } else {
            self.state
                .species
                .into_iter()
                .filter_map(|species| {
                    #[allow(
                        clippy::cast_precision_loss,
                        clippy::float_arithmetic,
                        clippy::cast_possible_truncation
                    )]
                    // all values in this calculation are positive
                    #[allow(clippy::cast_sign_loss, clippy::as_conversions)]
                    let offspring =
                        ((species.sum_adjusted_fitness / total_adjusted_fitness) * self.max_population as f64) as usize;

                    if offspring == 0 {
                        return None;
                    }

                    let mut final_selected = Vec::with_capacity(offspring);
                    let mut available = species.population.members;

                    // store elites
                    if self.elites > 0 {
                        available.sort_unstable_by(|e1, e2| e2.fitness.total_cmp(&e1.fitness));

                        let elites = available
                            .iter()
                            .filter(|e| e.fitness > 0.0_f64)
                            .take(self.elites)
                            .cloned()
                            .map(|e| e.phenotype.to_genotype())
                            .collect::<Vec<_>>();
                        self.elite_members.extend(elites);
                    }

                    while final_selected.len() < offspring {
                        let missing = offspring.saturating_sub(final_selected.len());
                        let (mut selected, non_selected) = self.selection.select(&mut self.rng, available);

                        debug_assert!(!selected.is_empty());
                        debug_assert!(!non_selected.is_empty());

                        if missing >= selected.len() {
                            // we selected fewer members than we need for the new species, so we dump them all in there at once
                            final_selected.append(&mut selected);
                        } else {
                            // we only need a few of the selected
                            final_selected.extend(selected.into_iter().take(missing));
                        }

                        available = non_selected;
                    }

                    // we allow `expect` as a missing representative is a irrecoverable error anyway
                    #[allow(clippy::expect_used)]
                    let representative = final_selected
                        .iter()
                        .choose(&mut self.rng)
                        .expect("selection should not be empty")
                        .phenotype
                        .clone();

                    Some(Parents {
                        identifier: species.identifier,
                        max_size: offspring,
                        representative,
                        population: EvaluatedPopulation {
                            members: final_selected,
                        },
                    })
                })
                .collect()
        };

        let state = Selected { selected };

        Classic {
            state,
            genotype: self.genotype,
            rng: self.rng,
            environment: self.environment,
            selection: self.selection,
            recombination: self.recombination,
            mutation: self.mutation,
            termination: self.termination,
            max_population: self.max_population,
            elites: self.elites,
            elite_members: self.elite_members,
            speciation_threshold: self.speciation_threshold,
            interspecies_breeding_chance: self.interspecies_breeding_chance,
            statistics: self.statistics,
        }
    }
}

/// Now that we have selected who is valid as a recombination parent, this is our only action in this state.
impl<PHENOTYPE, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    Classic<Selected<PHENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
{
    /// MISSING DOCS
    // all slicing done in here is only done so if a length check makes a panic impossible
    #[allow(clippy::indexing_slicing, clippy::too_many_lines)]
    pub fn recombine(
        mut self,
    ) -> Classic<Recombined<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    where
        PHENOTYPE: Phenotype<Genotype = GENOTYPE>,
        GENOTYPE: Genotype + Random,
        RNG: Rng,
        RECOMBINATION: Recombination<GENOTYPE>,
        [(); RECOMBINATION::OFFSPRING]:,
        [(); RECOMBINATION::PARENTS]:,
    {
        let mut populations = Vec::with_capacity(self.state.selected.len());
        let mut empty_species: Vec<Bare<GENOTYPE>> = Vec::with_capacity(self.state.selected.len());
        let offspring_size = empty_species.iter().map(|s| s.max_size).sum();
        let mut offspring = Vec::with_capacity(offspring_size);

        for species in self.state.selected {
            let Parents {
                identifier,
                max_size,
                representative,
                population,
            } = species;

            empty_species.push(Bare {
                identifier,
                max_size,
                representative: representative.to_genotype(),
            });

            let members = population
                .members
                .into_iter()
                .map(|m| m.phenotype.to_genotype())
                .collect::<Vec<_>>();
            populations.push(members);
        }

        while !populations.is_empty() {
            // first parent is always from the first population
            // we do so because in the case of crossbreeding, our population pool is simply `1..`
            // order does not matter as `recombine` shuffles inputs anyway
            let parent_index = self.rng.gen_range(0..populations[0].len());
            let parent_1 = populations[0].remove(parent_index);
            let crossbreed = self.rng.gen_bool(self.interspecies_breeding_chance);

            if populations[0].is_empty() {
                // we have exhausted all members of a species for recombination
                let _empty_population = populations.remove(0);

                // if the population is empty, then the only chance we can continue recombining
                // is if the cross-breeding is set to true, otherwise, we simply keep this member as is
                if !crossbreed {
                    offspring.push(parent_1);
                    continue;
                }
            }

            if crossbreed && populations.is_empty() {
                // if we're supposed to cross-breed, but can't because there's no other populations left,
                // it means we're done, so we keep the parent as is
                offspring.push(parent_1);
                break;
            }

            // at this point we've caught all the edge cases. either we don't cross-breed and we
            // have at least one other member in the same population, or we cross-breed and have
            // populations to choose from. the only remaining thing is to figure out if its enough
            // for full recombination. important to note is that each strategy has a variable set of
            // parents, so we have to account for every possible case

            // make sure we have enough members to chose from
            if crossbreed {
                // if we are crossbreeding, we know at least one other population could still have
                // enough members to do it
                let sum_of_crossbreedable_members =
                    populations.get(1..).map_or(0, |pops| pops.iter().map(Vec::len).sum());

                // using `saturating` here even though PARENTS should never be less than 2.
                if sum_of_crossbreedable_members < RECOMBINATION::PARENTS.saturating_sub(1) {
                    // there are some other populations to chose from, but they don't add up to
                    // the require amount of parents.
                    // this directly also means we can not continue recombination at all, so we
                    // take every single one of them and add them as they are to the offspring list
                    let remaining_members = populations.into_iter().flatten();
                    offspring.extend(remaining_members);

                    break;
                }
                // this prevents "cannot move parent_1" errors as `from_fn` is a `FnMut`
                // I'm certain polonius would not require this.
                let mut parent_one = Some(parent_1);
                // we have enough members in the remaining populations to perform crossbreeding
                let parents = core::array::from_fn(|i| {
                    if i == 0 {
                        // this is always the first parent, which is guaranteed to be `Some`
                        #[allow(clippy::expect_used)]
                        return parent_one.take().expect("option can't be None");
                    }

                    // pick a population
                    let population = self.rng.gen_range(1..populations.len());
                    // pick a member in said population
                    let member = self.rng.gen_range(0..populations[population].len());

                    // remove it, return it, and optionally delete the population if its empty
                    let parent = populations[population].remove(member);

                    if populations[population].is_empty() {
                        let _empty_population = populations.remove(population);
                    }

                    parent
                });

                offspring.extend(self.recombination.crossover(&mut self.rng, parents));

                continue;
            }

            // if we're not crossbreeding, we can only do it if there are enough other members
            // in the population of which the first parent came from
            if populations[0].len() >= RECOMBINATION::PARENTS.saturating_sub(1) {
                // this prevents "cannot move parent_1" errors as `from_fn` is a `FnMut`
                // I'm certain polonius would not require this.
                let mut parent_one = Some(parent_1);

                // we have enough members for recombination, so lets do it
                let parents = core::array::from_fn(|i| {
                    if i == 0 {
                        // this is always the first parent, which is guaranteed to be `Some`
                        #[allow(clippy::expect_used)]
                        return parent_one.take().expect("option can't be None");
                    }

                    let remaining_parent = self.rng.gen_range(0..populations[0].len());

                    populations[0].remove(remaining_parent)
                });

                if populations[0].is_empty() {
                    let _empty_population = populations.remove(0);
                }

                offspring.extend(self.recombination.crossover(&mut self.rng, parents));
                continue;
            }

            // in this case our population does not have enough members, the only way they
            // could not be recombined is using crossbreeding
            // as crossbreeding is off in this case, we can not do anything about it
            offspring.push(parent_1);

            // we do not have to check whether the population is now empty, as this would've happened
            // right after parent 1 was pulled out
        }

        let state = Recombined {
            species: empty_species,
            new_members: Population { members: offspring },
        };

        Classic {
            state,
            genotype: self.genotype,
            rng: self.rng,
            environment: self.environment,
            selection: self.selection,
            recombination: self.recombination,
            mutation: self.mutation,
            termination: self.termination,
            max_population: self.max_population,
            elites: self.elites,
            elite_members: self.elite_members,
            speciation_threshold: self.speciation_threshold,
            interspecies_breeding_chance: self.interspecies_breeding_chance,
            statistics: self.statistics,
        }
    }
}

impl<GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    Classic<Recombined<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
{
    /// MISSING DOCS
    pub fn mutate(
        mut self,
    ) -> Classic<Mutated<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    where
        GENOTYPE: Genotype,
        RNG: Rng,
        MUTATION: Mutation<GENOTYPE, RNG>,
    {
        let Recombined {
            species,
            mut new_members,
        } = self.state;

        for member in &mut new_members.members {
            self.mutation.mutate(member, &mut self.rng);
        }

        let state = Mutated { species, new_members };

        Classic {
            state,
            genotype: self.genotype,
            rng: self.rng,
            environment: self.environment,
            selection: self.selection,
            recombination: self.recombination,
            mutation: self.mutation,
            termination: self.termination,
            max_population: self.max_population,
            elites: self.elites,
            elite_members: self.elite_members,
            speciation_threshold: self.speciation_threshold,
            interspecies_breeding_chance: self.interspecies_breeding_chance,
            statistics: self.statistics,
        }
    }
}

impl<GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    Classic<Mutated<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
{
    /// MISSING DOCS
    pub fn reinsert(
        mut self,
    ) -> Classic<Unevaluated<GENOTYPE>, GENOTYPE, RNG, ENVIRONMENT, SELECTION, RECOMBINATION, MUTATION, TERMINATION>
    where
        GENOTYPE: Distance + Clone + Random,
        RNG: Rng,
    {
        let Mutated {
            species,
            mut new_members,
        } = self.state;

        new_members.members.append(&mut self.elite_members);

        if new_members.members.len() < self.max_population {
            let missing = self.max_population.saturating_sub(new_members.members.len());

            for _ in 0..missing {
                new_members.members.push(GENOTYPE::random(&mut self.rng));
            }
        }

        let new_generation_species = species
            .into_iter()
            .map(|s| Species {
                identifier: s.identifier,
                representative: s.representative,
                population: Population {
                    members: Vec::with_capacity(s.max_size),
                },
            })
            .collect();

        #[allow(clippy::shadow_unrelated, clippy::expect_used)]
        let mut species = sort_population_to_species(
            self.statistics
                .iteration
                .checked_add(1)
                .expect("iteration counter overflowed"),
            new_generation_species,
            new_members,
            self.speciation_threshold,
        );

        // species that have no longer any members go extinct
        species.retain(|s| !s.population.members.is_empty());

        let state = Unevaluated { species };

        Classic {
            state,
            genotype: self.genotype,
            rng: self.rng,
            environment: self.environment,
            selection: self.selection,
            recombination: self.recombination,
            mutation: self.mutation,
            termination: self.termination,
            max_population: self.max_population,
            elites: self.elites,
            elite_members: self.elite_members,
            speciation_threshold: self.speciation_threshold,
            interspecies_breeding_chance: self.interspecies_breeding_chance,
            statistics: self.statistics,
        }
    }
}

/// MISSING DOCS
fn sort_population_to_species<GENOTYPE>(
    identification_start: usize,
    mut species: Vec<Species<GENOTYPE>>,
    population: Population<GENOTYPE>,
    threshold: f32,
) -> Vec<Species<GENOTYPE>>
where
    GENOTYPE: Distance + Clone,
{
    if threshold == 0.0 {
        assert!(
            species.len() <= 1,
            "there should be only one species when speciation is turned off, found {}",
            species.len()
        );
    }

    let mut species_this_iteration = 1;

    #[allow(clippy::expect_used)]
    'members: for member in population.members {
        for single_species in &mut species {
            if single_species.representative.distance(&member) < threshold || threshold == 0.0 {
                single_species.population.members.push(member);
                continue 'members;
            }
        }

        // at this point we either have no species yet or the member has a genetic distance
        // greater than the speciation threshold, so in either case we create a new species
        let new_species = Species {
            // TODO: get rid of this clone by storing the index instead (not done yet because of sorting with elites)
            identifier: (identification_start, species_this_iteration),
            representative: member.clone(),
            population: Population { members: vec![member] },
        };

        species.push(new_species);

        species_this_iteration = species_this_iteration
            .checked_add(1)
            .expect("ran out of species identifiers for iteration");
    }

    species
}

/// This algorithm is mostly similar to [Basic] with the distinction, that humans will evaluate the
/// population. This is very useful for things that can't easily be written or expressed as a
/// fitness function.
/// The downside is, that it is comparatively slow and typically works with a way smaller
/// population.
///
/// In general, the big difference is that [Basic] only has context of one [Phenotype] at a time,
/// whereas [Interactive] receives the whole population for evaluation as a single batch.
///
/// This implementation simply requires a function to be provided that can return an evaluated population.
/// Internally the inverse ranking is used to determine fitness, so first [Phenotype]s in the list
/// are considered best. This *will* lose context of how similar [Phenotype]s are.
///
/// Most importantly, terminating this algorithm should be done using human input or a [Termination]
/// strategy that does not rely on fitness like generations or time. The easiest way is to implement
/// [Termination] and allow for user input or by use of an atomic bool that indicates termination
/// and can be set from any other thread, e.g. a GUI.
///
/// # External Resources
/// <https://en.wikipedia.org/wiki/Interactive_evolutionary_computation>
#[allow(dead_code)]
struct Interactive;

#[cfg(test)]
mod tests {
    use core::marker::PhantomData;
    use core::num::NonZeroUsize;

    use rand::rngs::SmallRng;
    use rand::{Rng, SeedableRng};

    use pretty_assertions::assert_eq;

    use crate::algorithm::fitness::{Classic, Evaluated, Statistics, Unevaluated};
    use crate::environment::Environment;
    use crate::fitness::Fitness as FitnessTrait;
    use crate::operators::mutation::random::single::nudge::Nudge;
    use crate::operators::recombination::single_point::SinglePoint;
    use crate::operators::selection::truncate::Truncation;
    use crate::phenotype::{FromGenotype, Phenotype};
    use crate::species::{Evaluated as EvaluatedMember, EvaluatedPopulation, EvaluatedSpecies, Population, Species};
    use crate::termination::fitness::Fitness;

    const TARGET: [u8; 10] = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3];

    #[derive(Clone, Debug, PartialEq)]
    struct TestPhenotype([u8; 10]);

    impl Phenotype for TestPhenotype {
        type Genotype = [u8; 10];

        fn to_genotype(self) -> Self::Genotype {
            self.0
        }
    }

    #[derive(Debug, PartialEq)]
    struct TestEnvironment {
        target: [u8; 10],
    }

    impl Environment for TestEnvironment {}

    impl FromGenotype<[u8; 10], TestEnvironment> for TestPhenotype {
        fn from_genotype<RNG>(_rng: &mut RNG, genotype: [u8; 10], _environment: &TestEnvironment) -> Self
        where
            RNG: Rng,
        {
            TestPhenotype(genotype)
        }
    }

    impl FitnessTrait<TestEnvironment> for TestPhenotype {
        #[allow(clippy::cast_precision_loss, clippy::float_arithmetic)]
        fn fitness(&self, environment: &TestEnvironment) -> f64 {
            let chars = &self.0;
            let target = &environment.target;

            let correct = chars
                .iter()
                .zip(target)
                .map(|(c, t)| c == t)
                .filter(|result| *result)
                .count();

            correct as f64 / self.0.len().max(environment.target.len()) as f64
        }
    }

    #[test]
    fn evaluation() {
        let algo = Classic {
            state: Unevaluated {
                species: vec![
                    Species {
                        identifier: (0, 0),
                        representative: [0, 0, 0, 0, 3, 3, 3, 3, 3, 3],
                        population: Population {
                            members: vec![
                                [0, 0, 0, 0, 3, 3, 3, 3, 3, 3], // fitness of 0.6
                                [0, 0, 0, 0, 0, 0, 3, 3, 3, 3], // fitness of 0.4
                            ],
                        },
                    },
                    Species {
                        identifier: (0, 1),
                        representative: [0, 0, 0, 0, 0, 3, 3, 3, 3, 3],
                        population: Population {
                            members: vec![
                                [0, 0, 0, 0, 0, 3, 3, 3, 3, 3], // this one has a fitness of 0.5
                            ],
                        },
                    },
                ],
            },
            genotype: PhantomData::<[u8; 10]>,
            rng: SmallRng::seed_from_u64(0),
            environment: TestEnvironment { target: TARGET },
            // there's no selection, so we give it a dummy one that doesn't do anything
            selection: Truncation {
                proportion_to_keep: 1.0,
            },
            recombination: SinglePoint,
            mutation: Nudge {
                maximum_distance: NonZeroUsize::new(1).unwrap(),
                chance: 0.0,
            },
            termination: Fitness(1.0),
            max_population: 10,
            elites: 0, // not relevant for this test
            elite_members: vec![],
            speciation_threshold: 0.0,         // not relevant for this test
            interspecies_breeding_chance: 0.0, // not relevant for this test
            statistics: Statistics { iteration: 0 },
        };

        let result = algo.evaluate::<TestPhenotype>();

        let expected = Classic {
            state: Evaluated {
                species: vec![
                    EvaluatedSpecies {
                        identifier: (0, 0),
                        sum_adjusted_fitness: 0.5,
                        population: EvaluatedPopulation {
                            members: vec![
                                EvaluatedMember {
                                    phenotype: TestPhenotype([0, 0, 0, 0, 3, 3, 3, 3, 3, 3]),
                                    fitness: 0.6,
                                    adjusted_fitness: 0.3,
                                },
                                EvaluatedMember {
                                    phenotype: TestPhenotype([0, 0, 0, 0, 0, 0, 3, 3, 3, 3]),
                                    fitness: 0.4,
                                    adjusted_fitness: 0.2,
                                },
                            ],
                        },
                    },
                    EvaluatedSpecies {
                        identifier: (0, 1),
                        sum_adjusted_fitness: 0.5,
                        population: EvaluatedPopulation {
                            members: vec![EvaluatedMember {
                                phenotype: TestPhenotype([0, 0, 0, 0, 0, 3, 3, 3, 3, 3]),
                                fitness: 0.5,
                                adjusted_fitness: 0.5,
                            }],
                        },
                    },
                ],
            },
            genotype: PhantomData::<[u8; 10]>,
            rng: SmallRng::seed_from_u64(0),
            environment: TestEnvironment { target: TARGET },
            // there's no selection, so we give it a dummy one that doesn't do anything
            selection: Truncation {
                proportion_to_keep: 1.0,
            },
            recombination: SinglePoint,
            mutation: Nudge {
                maximum_distance: NonZeroUsize::new(1).unwrap(),
                chance: 0.0,
            },
            termination: Fitness(1.0),
            max_population: 10,
            elites: 0,
            elite_members: vec![],
            speciation_threshold: 0.0,
            interspecies_breeding_chance: 0.0,
            statistics: Statistics { iteration: 1 },
        };

        assert_eq!(expected, result);
    }

    // #[test]
    // fn selection() {
    //     // as you can see above, they're very verbose, so I didn't bother yet
    // }

    // #[test]
    // fn recombination() {
    //     // as you can see above, they're very verbose, so I didn't bother yet
    // }

    // #[test]
    // fn mutation() {
    //     // as you can see above, they're very verbose, so I didn't bother yet
    // }

    // #[test]
    // fn reinsertion() {
    //     // as you can see above, they're very verbose, so I didn't bother yet
    // }
}