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.select.TournamentSelection;
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.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Semantic Geometric (mate) Selection; Branch and Bound prototype.
 *
 * @author Tomasz Pawlak
 */
public class SGS 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);

        // Mask is used to randomize order in which BB verifies subsets of individuals
        // It is required due to possible bias toward certain subsets in a straightforward implementation
        int[] mask = new int[individuals.length];
        // fill mask with available ids (let it be ordered for now)
        for (int i = 0; i < mask.length; ++i) {
            mask[i] = i;
        }
        // shuffle mask
        for (int i = mask.length - 1; i > 0; --i) {
            int r = random.nextInt(i + 1);
            int tmp = mask[i];
            mask[i] = mask[r];
            mask[r] = tmp;
        }

        try {
            this.BBLevel0(selected, individuals, mask);

            // BB failed: convex hull that includes target cannot be built
            // it can happen if convex hull of the entire population does not include target

            // use random selection for this case
            state.output.message("Cannot find proper subset of individuals, using random selection instead");
            return random.nextInt(individuals.length);

        } catch (BreakException e) {
            // at this point BB found first set of individulas, whose convex hull includes target
            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 BBLevel0(final TIntHashSet ids, final Individual[] individuals, final int[] mask) throws BreakException {
        for (int i = 0; i < individuals.length; ++i) {
            ids.add(mask[i]);
            this.BB(ids, individuals, mask, i + 1);
            ids.remove(mask[i]);

            this.state.output.message(String.format("SGS progress: %.3f", (double) (i + 1) / (double) individuals.length));
        }
    }

    private void BB(final TIntHashSet ids, final Individual[] individuals, final int[] mask, final int curr) throws BreakException {
        if (ids.size() == this.typicalIndsProduced) {
            if (this.evaluate(ids, individuals, this.target)) {
                throw new BreakException();
            }
            return;
        }

        for (int i = curr; i < individuals.length; ++i) {
            // verify if mask[i] individual expands convex hull of ids individuals
            GPIndividual newInd = (GPIndividual)individuals[mask[i]];
            ISemantics semantics = ((SimpleNodeBase<?>) newInd.trees[0].child).getSemantics();

            if (!this.evaluate(ids, individuals, semantics)) {
                // mask[i] expands convex hull
                ids.add(mask[i]);
                this.BB(ids, individuals, mask, i + 1);
                ids.remove(mask[i]);
            }
        }
    }

    private boolean evaluate(final TIntHashSet ids, final Individual[] individuals, ISemantics target) {
        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 {
    }
}
