package ec.gp.semantic.breed;

import ec.*;
import ec.gp.*;
import ec.gp.breed.*;
import ec.gp.koza.*;
import ec.gp.semantic.*;
import ec.gp.semantic.func.*;
import ec.gp.semantic.geometry.*;
import ec.gp.semantic.statistics.*;
import ec.util.*;

/**
 * Crossover operator as described in "Approximating Geometric Crossover in Semantic Space", K. Krawiec, P. Lichocki,
 * the SX+ variant. The name of the operator comes from the initials of the authors and X to denote a crossover: KLX.
 * 
 * @author Tomasz Pawlak
 */
public class KLX extends CrossoverPipeline {

	private static Parameter DEFAULT_BASE = GPBreedDefaults.base().push("KLX");
	protected static String CROSSOVER_ATTEMPTS = "crossoverAttempts";
	protected static String SENSITIVITY = "sensitivity";

	protected int crossoverAttempts = 10;

	/**
	 * Discards offspring if it distance to any of parents is lower than the given value. 0 to disable.
	 */
	protected double sensitivity = 0.0;

	@Override
	public Parameter defaultBase() {
		return DEFAULT_BASE;
	}

	@Override
	public void setup(EvolutionState state, Parameter base) {
		super.setup(state, base);

		ParameterDatabase db = state.parameters;

		this.crossoverAttempts = db.getIntWithDefault(base.push(CROSSOVER_ATTEMPTS),
				defaultBase().push(CROSSOVER_ATTEMPTS), crossoverAttempts);

		this.sensitivity = db.getDouble(base.push(SENSITIVITY), defaultBase().push(SENSITIVITY));

		ExtendedStatistics stats = (ExtendedStatistics) state.statistics;
		stats.getExperiment().put("in_crossoverAttempts", this.crossoverAttempts);
		stats.getExperiment().put("in_crossoverSensitivity", this.sensitivity);
	}

	@Override
	public int produce(final int min,
			final int max,
			final int start,
			final int subpopulation,
			final Individual[] inds,
			final EvolutionState state,
			final int thread)

	{
		// how many individuals should we make?
		int n = typicalIndsProduced();
		if (n < min)
			n = min;
		if (n > max)
			n = max;

		// should we bother?
		if (!state.random[thread].nextBoolean(likelihood))
			return reproduce(n, start, subpopulation, inds, state, thread, true); // DO produce children from source -- we've not done so already

		GPInitializer initializer = ((GPInitializer) state.initializer);

		for (int q = start; q < n + start; /* no increment */) // keep on going until we're filled up
		{
			// grab two individuals from our sources
			if (sources[0] == sources[1]) // grab from the same source
				sources[0].produce(2, 2, 0, subpopulation, parents, state, thread);
			else // grab from different sources
			{
				sources[0].produce(1, 1, 0, subpopulation, parents, state, thread);
				sources[1].produce(1, 1, 1, subpopulation, parents, state, thread);
			}

			// at this point, parents[] contains our two selected individuals

			// are our tree values valid?
			if (tree1 != TREE_UNFIXED && (tree1 < 0 || tree1 >= parents[0].trees.length))
				// uh oh
				state.output
						.fatal("GP Crossover Pipeline attempted to fix tree.0 to a value which was out of bounds of the array of the individual's trees.  Check the pipeline's fixed tree values -- they may be negative or greater than the number of trees in an individual");
			if (tree2 != TREE_UNFIXED && (tree2 < 0 || tree2 >= parents[1].trees.length))
				// uh oh
				state.output
						.fatal("GP Crossover Pipeline attempted to fix tree.1 to a value which was out of bounds of the array of the individual's trees.  Check the pipeline's fixed tree values -- they may be negative or greater than the number of trees in an individual");

			int t1 = 0;
			int t2 = 0;
			if (tree1 == TREE_UNFIXED || tree2 == TREE_UNFIXED)
			{
				do
				// pick random trees  -- their GPTreeConstraints must be the same
				{
					if (tree1 == TREE_UNFIXED)
						if (parents[0].trees.length > 1)
							t1 = state.random[thread].nextInt(parents[0].trees.length);
						else
							t1 = 0;
					else
						t1 = tree1;

					if (tree2 == TREE_UNFIXED)
						if (parents[1].trees.length > 1)
							t2 = state.random[thread].nextInt(parents[1].trees.length);
						else
							t2 = 0;
					else
						t2 = tree2;
				} while (parents[0].trees[t1].constraints(initializer) != parents[1].trees[t2].constraints(initializer));
			}
			else
			{
				t1 = tree1;
				t2 = tree2;
				// make sure the constraints are okay
				if (parents[0].trees[t1].constraints(initializer)
				!= parents[1].trees[t2].constraints(initializer)) // uh oh
					state.output
							.fatal("GP Crossover Pipeline's two tree choices are both specified by the user -- but their GPTreeConstraints are not the same");
			}

			GPIndividual[] offspring = null;
			GPIndividual[] bestSoFarOffspring = new GPIndividual[2]; // sorted according to score ascending (first element is the best)
			double[] bestSoFarScore = new double[] { Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY };
			int[] bestSoFarDepths = new int[2];
			int[] depths = new int[2];

			ISemantics parent1Sem = ((SimpleNodeBase<?>) parents[0].trees[t1].child).getSemantics();
			ISemantics parent2Sem = ((SimpleNodeBase<?>) parents[1].trees[t2].child).getSemantics();

			assert this.crossoverAttempts > 0;
			for (int attempt = 0; attempt < this.crossoverAttempts; ++attempt) {

				offspring = this.treeSwappingCrossover(state, thread, initializer, subpopulation, t1, t2, n, q, start, depths);

				putIntoBuffer(offspring[0], t1, parent1Sem, parent2Sem, depths[0], bestSoFarOffspring, bestSoFarScore, bestSoFarDepths);
				if (offspring[1] != null) {
					putIntoBuffer(offspring[1], t2, parent1Sem, parent2Sem, depths[1], bestSoFarOffspring, bestSoFarScore, bestSoFarDepths);
				}
			}

			// add the individuals to the population
			assert bestSoFarOffspring[0] != null;
			inds[q] = bestSoFarOffspring[0];
			q++;

			GeometricHelpers.logGeometricity(depths[0] + 1,
					(SimpleNodeBase<?>) parents[0].trees[t1].child,
					(SimpleNodeBase<?>) parents[1].trees[t2].child,
					(SimpleNodeBase<?>) bestSoFarOffspring[0].trees[t1].child,
					parents[0],
					parents[1],
					bestSoFarOffspring[0],
					state);

			if (q < n + start && !tossSecondParent)
			{
				assert bestSoFarOffspring[1] != null;
				inds[q] = bestSoFarOffspring[1];
				q++;

				GeometricHelpers.logGeometricity(depths[1] + 1,
						(SimpleNodeBase<?>) parents[0].trees[t1].child,
						(SimpleNodeBase<?>) parents[1].trees[t2].child,
						(SimpleNodeBase<?>) bestSoFarOffspring[1].trees[t2].child,
						parents[0],
						parents[1],
						bestSoFarOffspring[1],
						state);
			}
		}
		return n;
	}

	protected void putIntoBuffer(
			final GPIndividual offspring,
			final int tree,
			final ISemantics parent1Sem,
			final ISemantics parent2Sem,
			final int depth,
			final GPIndividual[] bestSoFarOffspring,
			final double[] bestSoFarScore,
			final int[] bestSoFarDepths) {

		SimpleNodeBase<?> offTree = (SimpleNodeBase<?>) offspring.trees[tree].child;
		double distXZ = parent1Sem.fastDistanceTo(offTree.getSemantics());
		double distYZ = parent2Sem.fastDistanceTo(offTree.getSemantics());

		if (Double.isNaN(distXZ) || Double.isInfinite(distXZ))
			distXZ = 1E300;

		if (Double.isNaN(distYZ) || Double.isInfinite(distYZ))
			distYZ = 1E300;

		double score = distXZ + distYZ + Math.abs(distXZ - distYZ);
		assert !Double.isInfinite(score) && !Double.isNaN(score);

		if (distXZ < this.sensitivity || distYZ < this.sensitivity) {
			// discard ineffective offspring
			// this high values would move the offspring to the end of our priority list
			// the offspring will be breed by crossover only if all the offspring are ineffective
			score = Double.MAX_VALUE;
		}

		// since the array contains only 2 elements, 
		// this loop is faster than binary search below, thanks to less branches in code
		for (int i = 0; i < bestSoFarScore.length; ++i) {
			if (score < bestSoFarScore[i]) {
				// shift best so far offspring to the end of buffer
				for (int j = bestSoFarScore.length - 2; j >= i; --j)
				{
					bestSoFarScore[j + 1] = bestSoFarScore[j];
					bestSoFarOffspring[j + 1] = bestSoFarOffspring[j];
					bestSoFarDepths[j + 1] = bestSoFarDepths[j];
				}

				// put current offspring at ith position
				bestSoFarScore[i] = score;
				bestSoFarOffspring[i] = offspring;
				bestSoFarDepths[i] = depth;
				break;
			}
		}

		/*int insertIndex = Arrays.binarySearch(bestSoFarScore, score);
		if (insertIndex < 0)
			insertIndex = ~insertIndex;

		if (insertIndex < bestSoFarScore.length) {

			assert score <= bestSoFarScore[insertIndex];

			// shift best so far offspring to the end of buffer
			for (int j = bestSoFarScore.length - 2; j >= insertIndex; --j)
			{
				bestSoFarScore[j + 1] = bestSoFarScore[j];
				bestSoFarOffspring[j + 1] = bestSoFarOffspring[j];
				bestSoFarDepths[j + 1] = bestSoFarDepths[j];
			}

			// put current offspring at insert position
			bestSoFarScore[insertIndex] = score;
			bestSoFarOffspring[insertIndex] = offspring;
			bestSoFarDepths[insertIndex] = depth;
		}*/
	}

	protected GPIndividual[] treeSwappingCrossover(
			final EvolutionState state,
			final int thread,
			final GPInitializer initializer,
			final int subpopulation,
			final int t1,
			final int t2,
			final int n,
			final int q,
			final int start,
			final int[] depths) {

		// validity results...
		boolean res1 = false;
		boolean res2 = false;

		// prepare the nodeselectors
		nodeselect1.reset();
		nodeselect2.reset();

		// pick some nodes

		GPNode p1 = null;
		GPNode p2 = null;

		for (int x = 0; x < numTries; x++)
		{
			// pick a node in individual 1
			p1 = nodeselect1.pickNode(state, subpopulation, thread, parents[0], parents[0].trees[t1]);

			// pick a node in individual 2
			p2 = nodeselect2.pickNode(state, subpopulation, thread, parents[1], parents[1].trees[t2]);

			// check for depth and swap-compatibility limits
			res1 = verifyPoints(initializer, p2, p1); // p2 can fill p1's spot -- order is important!
			if (n - (q - start) < 2 || tossSecondParent)
				res2 = true;
			else
				res2 = verifyPoints(initializer, p1, p2); // p1 can fill p2's spot -- order is important!

			// did we get something that had both nodes verified?
			// we reject if EITHER of them is invalid.  This is what lil-gp does.
			// Koza only has numTries set to 1, so it's compatible as well.
			if (res1 && res2)
				break;
		}

		depths[0] = p1.atDepth();
		depths[1] = p2.atDepth();

		// at this point, res1 AND res2 are valid, OR
		// either res1 OR res2 is valid and we ran out of tries, OR
		// neither res1 nor res2 is valid and we rand out of tries.
		// So now we will transfer to a tree which has res1 or res2
		// valid, otherwise it'll just get replicated.  This is
		// compatible with both Koza and lil-gp.

		// at this point I could check to see if my sources were breeding
		// pipelines -- but I'm too lazy to write that code (it's a little
		// complicated) to just swap one individual over or both over,
		// -- it might still entail some copying.  Perhaps in the future.
		// It would make things faster perhaps, not requiring all that
		// cloning.

		// Create some new individuals based on the old ones -- since
		// GPTree doesn't deep-clone, this should be just fine.  Perhaps we
		// should change this to proto off of the main species prototype, but
		// we have to then copy so much stuff over; it's not worth it.

		GPIndividual j1 = (GPIndividual) (parents[0].lightClone());
		GPIndividual j2 = null;
		if (n - (q - start) >= 2 && !tossSecondParent)
			j2 = (GPIndividual) (parents[1].lightClone());

		// Fill in various tree information that didn't get filled in there
		j1.trees = new GPTree[parents[0].trees.length];
		if (n - (q - start) >= 2 && !tossSecondParent)
			j2.trees = new GPTree[parents[1].trees.length];

		// at this point, p1 or p2, or both, may be null.
		// If not, swap one in.  Else just copy the parent.

		for (int x = 0; x < j1.trees.length; x++)
		{
			if (x == t1 && res1) // we've got a tree with a kicking cross position!
			{
				j1.trees[x] = (GPTree) (parents[0].trees[x].lightClone());
				j1.trees[x].owner = j1;
				j1.trees[x].child = parents[0].trees[x].child.cloneReplacing(p2, p1);
				j1.trees[x].child.parent = j1.trees[x];
				j1.trees[x].child.argposition = 0;
				((SimpleNodeBase<?>) j1.trees[x].child).resetSemanticsRecursive();
				j1.evaluated = false;
			} // it's changed
			else
			{
				j1.trees[x] = (GPTree) (parents[0].trees[x].lightClone());
				j1.trees[x].owner = j1;
				j1.trees[x].child = (GPNode) (parents[0].trees[x].child.clone());
				j1.trees[x].child.parent = j1.trees[x];
				j1.trees[x].child.argposition = 0;
			}
		}

		if (n - (q - start) >= 2 && !tossSecondParent) {
			for (int x = 0; x < j2.trees.length; x++)
			{
				if (x == t2 && res2) // we've got a tree with a kicking cross position!
				{
					j2.trees[x] = (GPTree) (parents[1].trees[x].lightClone());
					j2.trees[x].owner = j2;
					j2.trees[x].child = parents[1].trees[x].child.cloneReplacing(p1, p2);
					j2.trees[x].child.parent = j2.trees[x];
					j2.trees[x].child.argposition = 0;
					((SimpleNodeBase<?>) j2.trees[x].child).resetSemanticsRecursive();
					j2.evaluated = false;
				} // it's changed
				else
				{
					j2.trees[x] = (GPTree) (parents[1].trees[x].lightClone());
					j2.trees[x].owner = j2;
					j2.trees[x].child = (GPNode) (parents[1].trees[x].child.clone());
					j2.trees[x].child.parent = j2.trees[x];
					j2.trees[x].child.argposition = 0;
				}
			}
		}

		return new GPIndividual[] { j1, j2 };
	}
}
