NeatChromosomeCombinator

package net.bmahe.genetics4j.neat.combination;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.random.RandomGenerator;

import org.apache.commons.lang3.Validate;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import net.bmahe.genetics4j.core.chromosomes.Chromosome;
import net.bmahe.genetics4j.core.combination.ChromosomeCombinator;
import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
import net.bmahe.genetics4j.neat.Connection;
import net.bmahe.genetics4j.neat.chromosomes.NeatChromosome;
import net.bmahe.genetics4j.neat.combination.parentcompare.ChosenOtherChromosome;
import net.bmahe.genetics4j.neat.combination.parentcompare.ParentComparisonHandler;
import net.bmahe.genetics4j.neat.spec.combination.NeatCombination;
import net.bmahe.genetics4j.neat.spec.combination.parentcompare.ParentComparisonPolicy;

/**
 * Implements genetic crossover for NEAT (NeuroEvolution of Augmenting Topologies) neural network chromosomes.
 *
 * <p>NeatChromosomeCombinator performs innovation-number-based genetic recombination between two neural network
 * chromosomes, creating offspring that inherit network topology and connection weights from both parents while
 * preserving the historical tracking essential to the NEAT algorithm.
 *
 * <p>NEAT crossover algorithm:
 * <ol>
 * <li><strong>Parent comparison</strong>: Determine which parent is "fitter" using comparison policy</li>
 * <li><strong>Gene alignment</strong>: Match connections by innovation number between parents</li>
 * <li><strong>Matching genes</strong>: Randomly inherit from either parent (biased by inheritance threshold)</li>
 * <li><strong>Disjoint genes</strong>: Inherit from fitter parent when innovation ranges overlap</li>
 * <li><strong>Excess genes</strong>: Inherit from fitter parent beyond other parent's range</li>
 * <li><strong>Gene re-enabling</strong>: Potentially re-enable disabled genes based on threshold</li>
 * </ol>
 *
 * <p>Key genetic operations:
 * <ul>
 * <li><strong>Innovation alignment</strong>: Uses innovation numbers to match corresponding genes</li>
 * <li><strong>Fitness-biased inheritance</strong>: Favors genes from fitter parent based on inheritance threshold</li>
 * <li><strong>Gene state management</strong>: Handles enabled/disabled connection states during crossover</li>
 * <li><strong>Topology preservation</strong>: Ensures offspring have valid network topology</li>
 * </ul>
 *
 * <p>Gene classification:
 * <ul>
 * <li><strong>Matching genes</strong>: Same innovation number in both parents, inherit randomly</li>
 * <li><strong>Disjoint genes</strong>: Innovation number exists in one parent within other's range</li>
 * <li><strong>Excess genes</strong>: Innovation number beyond other parent's highest innovation</li>
 * <li><strong>Disabled genes</strong>: May be re-enabled if other parent has enabled version</li>
 * </ul>
 *
 * <p>Common usage patterns:
 *
 * <pre>{@code
 * // Create NEAT chromosome combinator
 * RandomGenerator randomGen = RandomGenerator.getDefault();
 * NeatCombination policy = NeatCombination.builder()
 *     .inheritanceThresold(0.7)  // 70% bias toward fitter parent
 *     .reenableGeneInheritanceThresold(0.25)  // 25% gene re-enabling chance
 *     .parentComparisonPolicy(FitnessComparison.build())
 *     .build();
 *
 * ParentComparisonHandler comparisonHandler = new FitnessComparisonHandler();
 * NeatChromosomeCombinator<Double> combinator = new NeatChromosomeCombinator<>(
 *     randomGen, policy, comparisonHandler
 * );
 *
 * // Perform crossover
 * NeatChromosome parent1 = // ... first parent
 * NeatChromosome parent2 = // ... second parent
 * Double fitness1 = 0.85;
 * Double fitness2 = 0.72;
 *
 * List<Chromosome> offspring = combinator.combine(
 *     eaConfiguration, parent1, fitness1, parent2, fitness2
 * );
 * NeatChromosome child = (NeatChromosome) offspring.get(0);
 * }</pre>
 *
 * <p>Inheritance threshold effects:
 * <ul>
 * <li><strong>0.5</strong>: Unbiased inheritance, equal probability from both parents</li>
 * <li><strong>&gt; 0.5</strong>: Bias toward fitter parent, promotes convergence</li>
 * <li><strong>&lt; 0.5</strong>: Bias toward less fit parent, increases diversity</li>
 * <li><strong>1.0</strong>: Always inherit from fitter parent (when fitness differs)</li>
 * </ul>
 *
 * <p>Gene re-enabling mechanism:
 * <ul>
 * <li><strong>Preservation</strong>: Disabled genes maintain connection topology information</li>
 * <li><strong>Re-activation</strong>: Chance to re-enable genes that are enabled in other parent</li>
 * <li><strong>Exploration</strong>: Allows rediscovery of previously disabled connection patterns</li>
 * <li><strong>Genetic diversity</strong>: Prevents permanent loss of structural information</li>
 * </ul>
 *
 * <p>Duplicate connection prevention:
 * <ul>
 * <li><strong>Links cache</strong>: Tracks already included connections to prevent duplicates</li>
 * <li><strong>Topology validation</strong>: Ensures each connection appears at most once</li>
 * <li><strong>Cache efficiency</strong>: O(1) lookup for connection existence checking</li>
 * <li><strong>Memory management</strong>: Cache cleared after each crossover operation</li>
 * </ul>
 *
 * <p>Performance considerations:
 * <ul>
 * <li><strong>Linear time complexity</strong>: O(n + m) where n, m are parent connection counts</li>
 * <li><strong>Innovation sorting</strong>: Leverages pre-sorted connection lists for efficiency</li>
 * <li><strong>Memory efficiency</strong>: Minimal allocation during crossover</li>
 * <li><strong>Cache optimization</strong>: Efficient duplicate detection and prevention</li>
 * </ul>
 *
 * @param <T> the fitness value type (typically Double)
 * @see NeatCombination
 * @see ParentComparisonHandler
 * @see NeatChromosome
 * @see ChromosomeCombinator
 */
public class NeatChromosomeCombinator<T extends Comparable<T>> implements ChromosomeCombinator<T> {
	public static final Logger logger = LogManager.getLogger(NeatChromosomeCombinator.class);

	private final RandomGenerator randomGenerator;
	private final NeatCombination neatCombination;
	private final ParentComparisonHandler parentComparisonHandler;

	/**
	 * Checks whether a connection already exists in the links cache.
	 *
	 * <p>The links cache prevents duplicate connections in the offspring by tracking all connections that have already
	 * been added. This ensures each connection appears at most once in the resulting chromosome.
	 *
	 * @param linksCache cache mapping from-node indices to sets of to-node indices
	 * @param connection connection to check for existence
	 * @return true if connection already exists in cache, false otherwise
	 * @throws IllegalArgumentException if linksCache or connection is null
	 */
	private boolean linksCacheContainsConnection(final Map<Integer, Set<Integer>> linksCache,
			final Connection connection) {
		Objects.requireNonNull(linksCache);
		Objects.requireNonNull(connection);

		final int fromNodeIndex = connection.fromNodeIndex();
		final int toNodeIndex = connection.toNodeIndex();

		return linksCache.containsKey(fromNodeIndex) == true
				&& linksCache.get(fromNodeIndex).contains(toNodeIndex) == true;
	}

	/**
	 * Adds a connection to the links cache to prevent future duplicates.
	 *
	 * <p>This method records that a connection from the specified source to target node has been added to the offspring,
	 * preventing the same connection from being added again during the crossover process.
	 *
	 * @param linksCache cache mapping from-node indices to sets of to-node indices
	 * @param connection connection to add to the cache
	 * @throws IllegalArgumentException if linksCache or connection is null
	 */
	private void insertInlinksCache(final Map<Integer, Set<Integer>> linksCache, final Connection connection) {
		Objects.requireNonNull(linksCache);
		Objects.requireNonNull(connection);

		final int fromNodeIndex = connection.fromNodeIndex();
		final int toNodeIndex = connection.toNodeIndex();

		linksCache.computeIfAbsent(fromNodeIndex, k -> new HashSet<>()).add(toNodeIndex);
	}

	/**
	 * Determines whether a disabled gene should be re-enabled during crossover.
	 *
	 * <p>If the chosen parent has a disabled connection but the other parent has the same connection enabled, there is a
	 * configurable chance to re-enable the connection in the offspring. This mechanism prevents permanent loss of
	 * potentially useful connections.
	 *
	 * @param chosenParent the connection selected for inheritance
	 * @param otherParent  the corresponding connection from the other parent
	 * @return true if the disabled connection should be re-enabled, false otherwise
	 * @throws IllegalArgumentException if either connection is null
	 */
	protected boolean shouldReEnable(final Connection chosenParent, final Connection otherParent) {
		Objects.requireNonNull(chosenParent);
		Objects.requireNonNull(otherParent);

		boolean shouldReEnable = false;
		if (chosenParent.isEnabled() == false && otherParent.isEnabled() == true) {
			if (randomGenerator.nextDouble() < neatCombination.reenableGeneInheritanceThresold()) {
				shouldReEnable = true;
			}
		}

		return shouldReEnable;
	}

	/**
	 * Constructs a new NEAT chromosome combinator with the specified components.
	 *
	 * <p>The combinator uses the random generator for stochastic decisions during crossover, the combination policy for
	 * inheritance parameters, and the comparison handler for determining parent fitness relationships.
	 *
	 * @param _randomGenerator         random number generator for stochastic crossover decisions
	 * @param _neatCombination         crossover policy defining inheritance parameters
	 * @param _parentComparisonHandler handler for comparing parent fitness and determining inheritance bias
	 * @throws IllegalArgumentException if any parameter is null
	 */
	public NeatChromosomeCombinator(final RandomGenerator _randomGenerator,
			final NeatCombination _neatCombination,
			final ParentComparisonHandler _parentComparisonHandler) {
		Objects.requireNonNull(_randomGenerator);
		Objects.requireNonNull(_neatCombination);
		Objects.requireNonNull(_parentComparisonHandler);

		this.randomGenerator = _randomGenerator;
		this.neatCombination = _neatCombination;
		this.parentComparisonHandler = _parentComparisonHandler;
	}

	/**
	 * Performs genetic crossover between two NEAT chromosomes to produce offspring.
	 *
	 * <p>This method implements the NEAT crossover algorithm, aligning genes by innovation number and applying
	 * inheritance rules based on parent fitness and configuration parameters. The result is a single offspring
	 * chromosome that inherits network topology and connection weights from both parents.
	 *
	 * <p>Crossover process:
	 * <ol>
	 * <li>Compare parent fitness to determine inheritance bias</li>
	 * <li>Align genes by innovation number between parents</li>
	 * <li>Process matching genes with random inheritance (biased)</li>
	 * <li>Process disjoint genes based on fitness comparison</li>
	 * <li>Process excess genes from fitter parent</li>
	 * <li>Apply gene re-enabling rules for disabled connections</li>
	 * </ol>
	 *
	 * @param eaConfiguration     evolutionary algorithm configuration containing fitness comparator
	 * @param firstChromosome     first parent chromosome (must be NeatChromosome)
	 * @param firstParentFitness  fitness value of first parent
	 * @param secondChromosome    second parent chromosome (must be NeatChromosome)
	 * @param secondParentFitness fitness value of second parent
	 * @return list containing single offspring chromosome
	 * @throws IllegalArgumentException if chromosomes are not NeatChromosome instances or any parameter is null
	 */
	@Override
	public List<Chromosome> combine(final AbstractEAConfiguration<T> eaConfiguration, final Chromosome firstChromosome,
			final T firstParentFitness, final Chromosome secondChromosome, final T secondParentFitness) {
		Objects.requireNonNull(eaConfiguration);
		Objects.requireNonNull(firstChromosome);
		Objects.requireNonNull(firstParentFitness);
		Validate.isInstanceOf(NeatChromosome.class, firstChromosome);
		Objects.requireNonNull(secondChromosome);
		Objects.requireNonNull(secondParentFitness);
		Validate.isInstanceOf(NeatChromosome.class, secondChromosome);

		final NeatChromosome firstNeatChromosome = (NeatChromosome) firstChromosome;
		final NeatChromosome secondNeatChromosome = (NeatChromosome) secondChromosome;
		Validate.isTrue(
				firstNeatChromosome.getNodeLayout().isCompatibleWith(secondNeatChromosome.getNodeLayout()),
					"Cannot combine NEAT chromosomes with incompatible node layouts");
		final Comparator<T> fitnessComparator = eaConfiguration.fitnessComparator();
		final double inheritanceThresold = neatCombination.inheritanceThresold();
		final ParentComparisonPolicy parentComparisonPolicy = neatCombination.parentComparisonPolicy();

		final int fitnessComparison = fitnessComparator.compare(firstParentFitness, secondParentFitness);
		final ChosenOtherChromosome comparedChromosomes = parentComparisonHandler
				.compare(parentComparisonPolicy, firstNeatChromosome, secondNeatChromosome, fitnessComparison);
		final NeatChromosome bestChromosome = comparedChromosomes.chosen();
		final NeatChromosome worstChromosome = comparedChromosomes.other();

		final List<Connection> combinedConnections = new ArrayList<>();
		final Map<Integer, Set<Integer>> linksCache = new HashMap<>();

		final var bestConnections = bestChromosome.getConnections();
		final var worstConnections = worstChromosome.getConnections();

		int indexBest = 0;
		int indexWorst = 0;

		while (indexBest < bestConnections.size() && indexWorst < worstConnections.size()) {

			final var bestConnection = bestConnections.get(indexBest);
			final var worstConnection = worstConnections.get(indexWorst);

			if (bestConnection.innovation() == worstConnection.innovation()) {
				/**
				 * If innovation is the same, we pick the connection randomly
				 */
				var original = bestConnection;
				var other = worstConnection;
				if (randomGenerator.nextDouble() < 1 - inheritanceThresold) {
					original = worstConnection;
					other = bestConnection;
				}
				if (linksCacheContainsConnection(linksCache, original) == false) {

					/**
					 * If the chosen gene is disabled but the other one is enabled, then there is a chance we will re-enable
					 * it
					 */
					final boolean isEnabled = shouldReEnable(original, other) ? true : original.isEnabled();

					final var childConnection = Connection.builder().from(original).isEnabled(isEnabled).build();
					combinedConnections.add(childConnection);
					insertInlinksCache(linksCache, original);
				}
				indexBest++;
				indexWorst++;
			} else if (bestConnection.innovation() > worstConnection.innovation()) {

				/**
				 * If the fitnesses are equal, then we randomly inherit from the parent Otherwise, we do not inherit from
				 * the lesser gene
				 */
				if (fitnessComparison == 0 && randomGenerator.nextDouble() < 1.0 - inheritanceThresold) {
					final var original = worstConnection;
					if (linksCacheContainsConnection(linksCache, original) == false) {
						combinedConnections.add(Connection.copyOf(original));
						insertInlinksCache(linksCache, original);
					}
				}

				indexWorst++;
			} else {

				/**
				 * If the fitnesses are equal, then we randomly inherit from the parent Otherwise, we always inherit from
				 * the better gene
				 */

				if (fitnessComparison != 0 || randomGenerator.nextDouble() < inheritanceThresold) {
					if (linksCacheContainsConnection(linksCache, bestConnection) == false) {
						combinedConnections.add(Connection.copyOf(bestConnection));
						insertInlinksCache(linksCache, bestConnection);
					}
				}
				indexBest++;
			}
		}

		/*
		 * Case where the best connection has more genes. It's called excess genes
		 */
		while (indexBest < bestConnections.size()) {
			/**
			 * If the fitnesses are equal, then we randomly inherit from the parent Otherwise, we always inherit from the
			 * better gene
			 */
			if (fitnessComparison != 0 || randomGenerator.nextDouble() < inheritanceThresold) {
				final var bestConnection = bestConnections.get(indexBest);
				if (linksCacheContainsConnection(linksCache, bestConnection) == false) {
					combinedConnections.add(Connection.copyOf(bestConnection));
					insertInlinksCache(linksCache, bestConnection);
				}

			}
			indexBest++;
		}

		/*
		 * Case where the worst connection has more genes. It's called excess genes. Since we don't inherit when their
		 * fitness aren't equal, it means we can skip the excess genes from the weaker connections. However we will
		 * randomly inherit if their fitnesses are equal
		 */
		while (fitnessComparison == 0 && indexWorst < worstConnections.size()) {
			if (randomGenerator.nextDouble() < 1.0 - inheritanceThresold) {
				final var worstConnection = worstConnections.get(indexWorst);
				if (linksCacheContainsConnection(linksCache, worstConnection) == false) {
					combinedConnections.add(Connection.copyOf(worstConnection));
					insertInlinksCache(linksCache, worstConnection);
				}

			}
			indexWorst++;
		}

		return List.of(
				new NeatChromosome(bestChromosome.getNodeLayout(),
						bestChromosome.getMinWeightValue(),
						bestChromosome.getMaxWeightValue(),
						combinedConnections));
	}
}