package ec.gp.semantic.select;

import ec.EvolutionState;
import ec.Individual;
import ec.SelectionMethod;
import ec.Subpopulation;
import ec.gp.GPIndividual;
import ec.gp.semantic.ISemanticProblem;
import ec.gp.semantic.ISemantics;
import ec.gp.semantic.func.SimpleNodeBase;
import ec.gp.semantic.geometry.IConvexHullDetector;
import ec.util.MersenneTwisterFast;
import ec.util.Parameter;
import ec.util.ParameterDatabase;
import gnu.trove.iterator.TIntIterator;
import gnu.trove.set.hash.TIntHashSet;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Semantic Geometric (mate) Selection; 2 Phase prototype: expansion & shrinking
 *
 * @author Tomasz Pawlak
 */
public class SGS2 extends SelectionMethod {
	private final static Parameter DEFAULT_BASE = new Parameter("SGS");
	private final static String CONVEX_HULL_DETECTOR = "detector";

	private EvolutionState state;
	private IConvexHullDetector convexHullDetector;
	private ISemantics target;
	private int typicalIndsProduced = 0;
	private Queue<Integer> nextIndividuals = new LinkedList<Integer>();

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

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

		ParameterDatabase db = state.parameters;
		ISemanticProblem<?> problem = (ISemanticProblem<?>) state.evaluator.p_problem;

		this.state = state;
		this.convexHullDetector = (IConvexHullDetector) db.getInstanceForParameter(base.push(CONVEX_HULL_DETECTOR), defaultBase().push(CONVEX_HULL_DETECTOR), IConvexHullDetector.class);
		this.target = problem.getTargetSemantics();
		this.typicalIndsProduced = this.target.size() + 1;
	}

	@Override
	public int typicalIndsProduced() {
		return this.typicalIndsProduced;
	}

	@Override
	public int produce(int subpopulation, EvolutionState state, int thread) {
		if (!this.nextIndividuals.isEmpty()) {
			return this.nextIndividuals.poll();
		}

		MersenneTwisterFast random = state.random[thread];
		Subpopulation pop = state.population.subpops[subpopulation];
		Individual[] individuals = pop.individuals;
		TIntHashSet selected = new TIntHashSet(this.typicalIndsProduced);

		this.selectAll(selected, individuals);
		//this.expand(selected, individuals, random);
		this.shrink(selected, individuals);

		assert selected.size() == this.typicalIndsProduced;
		int id;
		for (TIntIterator it = selected.iterator(); it.hasNext(); ) {
			id = it.next();
			this.nextIndividuals.add(id);
		}

		return this.nextIndividuals.poll();
	}

	private void selectAll(final TIntHashSet ids, final Individual[] individuals) {
		for (int i = 0; i < individuals.length; ++i) {
			ids.add(i);
		}
	}

	private void expand(final TIntHashSet ids, final Individual[] individuals, MersenneTwisterFast random) {
		int k = this.target.size() + 1;

		int max = individuals.length;
		int[] numbers = new int[individuals.length];
		for (int i = 0; i < numbers.length; ++i) {
			numbers[i] = i;
		}

		while (ids.size() < k || !this.evaluate(ids, individuals)) {
			int r = random.nextInt(max--);
			ids.add(numbers[r]);
			if (max < 0)
				break;
			numbers[r] = numbers[max];
		}
	}

	private void shrink(final TIntHashSet ids, final Individual[] individuals) {
		int k = this.target.size() + 1;
		while (ids.size() > k) {
			int[] candidates = ids.toArray();
			boolean fullLoop = true;
			for (int i = 0; i < candidates.length; ++i) {
				ids.remove(candidates[i]);
				if (this.evaluate(ids, individuals)) {
					fullLoop = false;
					break; // breaks for loop
				}
				ids.add(candidates[i]);
			}

			if (fullLoop) {
				// due to approximate characteristic of our convex hull detector, we may be sometimes unable to
				// determine which individual to remove, thus we do it randomly
				TIntIterator iter = ids.iterator();
				while (ids.size() > k) {
					iter.next();
					iter.remove();
				}
				break;
			}
		}
	}

	private boolean evaluate(final TIntHashSet ids, final Individual[] individuals) {
		assert this.convexHullDetector.isEmpty();

		int id;
		for (TIntIterator it = ids.iterator(); it.hasNext(); ) {
			id = it.next();
			GPIndividual ind = (GPIndividual) individuals[id];
			SimpleNodeBase<?> root = (SimpleNodeBase<?>) ind.trees[0].child;
			ISemantics indSemantics = root.getSemantics();

			this.convexHullDetector.addSupportPoint(indSemantics);
		}

		boolean output = this.convexHullDetector.isInConvexHull(target);

		this.convexHullDetector.clear();

		return output;
	}

	final class BreakException extends Exception {
	}
}
