meiosis 0.1.0

use rand::Rng;

use crate::gene::Gene;

use super::Recombination;

/// MISSING DOCS
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
#[allow(clippy::exhaustive_structs)]
pub struct SinglePoint;

/// `Vec<T>` has a variable length, so offspring will also have variable length, however never shorter
/// or longer than the parents.
impl<GENE> Recombination<Vec<GENE>> for SinglePoint
where
    GENE: Gene + Clone,
{
    const PARENTS: usize = 2;
    const OFFSPRING: usize = 2;

    /// # Panic
    /// A genome can never be empty, but we can also not operate on single-gene parents,
    /// so we assume that either parents have at least two genes.
    // Every use of indexing slicing is behind a length check and construction of new Vec is done
    // using open ranges.
    #[allow(clippy::indexing_slicing)]
    fn crossover<R>(
        &self,
        rng: &mut R,
        parents: [Vec<GENE>; <Self as Recombination<Vec<GENE>>>::PARENTS],
    ) -> [Vec<GENE>; <Self as Recombination<Vec<GENE>>>::OFFSPRING]
    where
        R: Rng,
    {
        let [parent_one, parent_two] = parents;

        assert!(!parent_one.is_empty(), "parent 1 has too few genes to cross-over");
        assert!(!parent_two.is_empty(), "parent 2 has too few genes to cross-over");

        // We can not cut outside of the length of the shorted Vec, as we might run into the following issue:
        // Parent 1: aaaaaa
        // Parent 2: bbb
        // If our cutting point is now 4, we would end up with these:
        // 1: aaaa aa
        // 2: bbb
        // Switching the ends of 1 and 2, offspring would look like this:
        // "aaaa"
        // "bbb aa"
        // As you can see, we're missing a gene at index 4 for offspring 2.
        // To prevent this from happening, we only ever cut at a point that is inside of both parents.
        let shortest_parent = parent_one.len().min(parent_two.len());

        if shortest_parent == 1 {
            // If one of the parents only has a single gene, then that is all we can work with.
            // In short, the first gene between the two parents gets swapped.
            let [mut offspring1, mut offspring2] = [parent_one, parent_two];
            core::mem::swap(&mut offspring1[0], &mut offspring2[0]);

            return [offspring1, offspring2];
        }

        // We need at least a single item to be switched, so the minimum index is 1.
        // The cutting point index is assumed to be the start of the second offspring.
        let cutting_point_index = rng.gen_range(1..shortest_parent);

        // Because we're switching "tails" here, we already know the offspring sizes.
        // Offspring 1 gets the "end" of parent 2, and thus can not be longer.
        let mut offspring1 = Vec::with_capacity(parent_two.len());
        // Offspring 2 gets the "end" of parent 1, and thus can not be longer.
        let mut offspring2 = Vec::with_capacity(parent_one.len());

        let parent1_left = &parent_one[..cutting_point_index];
        let parent1_right = &parent_one[cutting_point_index..];

        let parent2_left = &parent_two[..cutting_point_index];
        let parent2_right = &parent_two[cutting_point_index..];

        offspring1.extend(parent1_left.to_owned());
        offspring1.extend(parent2_right.to_owned());

        offspring2.extend(parent2_left.to_owned());
        offspring2.extend(parent1_right.to_owned());

        [offspring1, offspring2]
    }
}

/// `[T; N]` has a fixed length, so offspring will also have the same length.
impl<GENE, const GENES: usize> Recombination<[GENE; GENES]> for SinglePoint
where
    GENE: Gene + Clone,
{
    const PARENTS: usize = 2;
    const OFFSPRING: usize = 2;

    /// # Panic
    /// A genome can never be empty, but we can also not operate on single-gene parents,
    /// so we assume that either parents have at least two genes.
    fn crossover<R>(
        &self,
        rng: &mut R,
        parents: [[GENE; GENES]; <Self as Recombination<[GENE; GENES]>>::PARENTS],
    ) -> [[GENE; GENES]; <Self as Recombination<[GENE; GENES]>>::OFFSPRING]
    where
        R: Rng,
    {
        let [parent_one, parent_two] = parents;

        assert!(parent_one.len() >= 2, "parent 1 has too few genes to cross-over");
        assert!(parent_two.len() >= 2, "parent 2 has too few genes to cross-over");

        // We need at least a single item to be switched, so the minimum index is 1.
        // The cutting point index is assumed to be the start of the second offspring,
        // so we also need an item there.
        let cutting_point_index = rng.gen_range(1..GENES);

        // We clone here, as both offsprings have the same "left" side as their parents.
        // TODO: get rid of cloning here somehow?
        let mut offspring1 = parent_one.clone();
        let mut offspring2 = parent_two.clone();

        let parent1_right = &parent_one[cutting_point_index..];
        let parent2_right = &parent_two[cutting_point_index..];

        offspring1[cutting_point_index..].clone_from_slice(parent2_right);
        offspring2[cutting_point_index..].clone_from_slice(parent1_right);

        [offspring1, offspring2]
    }
}

/// This implementation is very naive and allocates.
impl Recombination<String> for SinglePoint {
    const PARENTS: usize = 2;
    const OFFSPRING: usize = 2;

    fn crossover<R>(
        &self,
        rng: &mut R,
        parents: [String; <Self as Recombination<String>>::PARENTS],
    ) -> [String; <Self as Recombination<String>>::OFFSPRING]
    where
        R: Rng,
    {
        let [parent_one, parent_two] = parents;

        // convert strings into char vectors
        let parent1_chars = parent_one.chars().collect::<Vec<_>>();
        let parent2_chars = parent_two.chars().collect();

        // reuse the Vec<DNA> implementation
        let offspring = self.crossover(rng, [parent1_chars, parent2_chars]);

        // convert vectors back to strings
        offspring.map(|vec| vec.into_iter().collect::<String>())
    }
}

#[cfg(test)]
mod tests {
    use rand::rngs::SmallRng;
    use rand::SeedableRng;

    use super::Recombination;
    use super::SinglePoint;

    #[test]
    fn vector_crossover() {
        let mut rng = SmallRng::seed_from_u64(3);
        let crossover = SinglePoint;

        let parent1 = vec![1, 2, 3, 4];
        let parent2 = vec![5, 6, 7, 8, 9, 10];

        let offspring = crossover.crossover(&mut rng, [parent1, parent2]);

        assert_eq!(offspring, [vec![1, 2, 7, 8, 9, 10], vec![5, 6, 3, 4]]);
    }

    #[test]
    #[should_panic(expected = "parent 2 has too few genes to cross-over")]
    fn vector_crossover_empty() {
        let mut rng = SmallRng::seed_from_u64(0);
        let crossover = SinglePoint;

        let parent1 = (1..=10).collect();
        let parent2 = vec![];

        let _offspring = crossover.crossover(&mut rng, [parent1, parent2]);
    }

    #[test]
    fn vector_crossover_same() {
        let mut rng = SmallRng::seed_from_u64(0);
        let crossover = SinglePoint;

        let parent1 = vec![1, 2, 3];
        let parent2 = vec![1, 2, 3];

        let offspring = crossover.crossover(&mut rng, [parent1, parent2]);

        assert_eq!(offspring[0], offspring[1]);
    }

    #[test]
    fn vector_crossover_simple() {
        let mut rng = SmallRng::seed_from_u64(0);
        let crossover = SinglePoint;

        let parent1 = vec![1, 2];
        let parent2 = vec![3, 4];

        let offspring = crossover.crossover(&mut rng, [parent1, parent2]);

        assert_eq!(offspring, [vec![1, 4], vec![3, 2]]);
    }

    #[test]
    fn array_crossover_same() {
        let mut rng = SmallRng::seed_from_u64(0);
        let crossover = SinglePoint;

        let parent1 = [1, 2, 3];
        let parent2 = [1, 2, 3];

        let offspring = crossover.crossover(&mut rng, [parent1, parent2]);

        assert_eq!(offspring[0], offspring[1]);
    }

    #[test]
    fn array_crossover_simple() {
        let mut rng = SmallRng::seed_from_u64(0);
        let crossover = SinglePoint;

        let parent1 = [1, 2];
        let parent2 = [3, 4];

        let offspring = crossover.crossover(&mut rng, [parent1, parent2]);

        assert_eq!(offspring, [[1, 4], [3, 2]]);
    }
}