meiosis 0.1.0

use rand::Rng;

use crate::genotype::Distance;
use crate::random::Random;

use super::Genotype;

impl Genotype for String {
    type Gene = char;
}

impl Distance for String {
    #[allow(clippy::float_arithmetic, clippy::cast_precision_loss)]
    // this algorithm should be fine as it is
    #[allow(clippy::integer_arithmetic)]
    fn distance(&self, other: &Self) -> f32 {
        let mut left = self.chars();
        let mut right = other.chars();

        let mut left_chars = 0_usize;
        let mut right_chars = 0;

        let mut difference = 0.0;

        loop {
            // before we overflow the string would have to be so insanely huge
            // making this basically impossible to be a problem
            #[allow(clippy::arithmetic_side_effects)]
            #[allow(clippy::as_conversions)]
            match (left.next(), right.next()) {
                // both iterators still produce chars
                (Some(left_char), Some(right_char)) => {
                    left_chars += 1;
                    right_chars += 1;

                    if left_char != right_char {
                        difference += 1.0;
                    }
                }
                // right iterator is empty, so we count the rest in the left one as the distance
                (Some(_), None) => {
                    let remaining = left.count() + 1; // the 1 is the char we just got from `.next()`
                    left_chars += remaining;

                    difference += remaining as f32;

                    break;
                }

                // left iterator is empty, so we count the rest in the right one as the distance
                (None, Some(_)) => {
                    let remaining = right.count() + 1; // the 1 is the char we just got from `.next()`
                    right_chars += remaining;

                    difference += remaining as f32;
                    break;
                }
                // both strings ran out of chars at the same time, so we're done
                (None, None) => {
                    break;
                }
            }
        }

        #[allow(clippy::as_conversions)]
        let max_length = left_chars.max(right_chars) as f32;

        difference / max_length
    }
}

/// Typically, to uniformly generate a random string, we'd have to allow [`usize::MAX`] characters.
/// This is not only going to use a lot of memory, it is also very slow.
///
/// To prevent all that, instead we start with one character and rely on [`Mutation`]
/// to grow the [String] over time. This is still relatively slow if the goal is to find
/// rather large strings, but better than trying to allocate all of the system memory.
impl Random for String {
    fn random<RNG>(rng: &mut RNG) -> Self
    where
        RNG: Rng,
        Self: Sized,
    {
        let char = rng.gen::<char>();
        String::from(char)
    }
}

#[cfg(test)]
mod tests {
    use crate::genotype::Distance;

    #[test]
    fn distance_same() {
        // the genomes share a single gene out of 3, so their distance is 2/3
        let str1 = String::from("abc");
        let str2 = String::from("abc");

        let distance = str1.distance(&str2);

        assert!((distance - 0.0).abs() < 0.0001)
    }

    #[test]
    fn distance_same_size() {
        // the genomes share a single gene out of 3, so their distance is 2/3
        let str1 = String::from("abc");
        let str2 = String::from("cba");

        let distance = str1.distance(&str2);

        assert!((distance - 0.66666).abs() < 0.0001)
    }

    #[test]
    fn distance_different_size() {
        // the genomes share 3 genes out of 5, so their distance is 2/5
        let str1 = String::from("abc");
        let str2 = String::from("abcde");

        let distance = str1.distance(&str2);

        assert!((distance - 0.4).abs() < 0.0001)
    }

    #[test]
    fn distance_completely_different() {
        // the genomes share 3 genes out of 5, so their distance is 2/5
        let str1 = String::from("abc");
        let str2 = String::from("defgh");

        let distance = str1.distance(&str2);

        assert!((distance - 1.0).abs() < 0.0001)
    }
}