/*
  Copyright 2006 by Sean Luke
  Licensed under the Academic Free License version 3.0
  See the file "LICENSE" for more information
*/

package ec.multiobjective;

import java.io.*;
import ec.util.DecodeReturn;
import ec.util.Parameter;
import ec.util.Code;
import ec.Fitness;
import ec.EvolutionState;
import java.util.*;
import ec.*;
import ec.util.*;

/* 
 * MultiObjectiveFitness.java
 * 
 * Created: Tue Aug 10 20:27:38 1999
 * By: Sean Luke
 */

/**
 * MultiObjectiveFitness is a subclass of Fitness which implements basic
 * multi-objective mechanisms suitable for being used with a variety of
 * multi-objective selection mechanisms, including ones using pareto-optimality.
 * 
 * <p>
 * The object contains two items: an array of floating point values representing
 * the various multiple fitnesses, and a flag (maximize) indicating whether
 * higher is considered better. By default, isIdealFitness() always returns
 * false; you might want to override that, though it'd be unusual -- what is the
 * ideal fitness from the perspective of a pareto front?
 * 
 * <p>
 * The object also contains maximum and minimum fitness values suggested for the
 * problem, on a per-objective basis. By default the maximum values are all 1.0
 * and the minimum values are all 0.0, but you can change these. Note that
 * maximum does not mean "best" unless maximize is true.
 *
 * <p>The class also contains utility methods or computing pareto dominance, 
 * Pareto Fronts and Pareto Front Ranks, and distance in multiobjective space.
 * The default comparison operators use Pareto Dominance, though this is often
 * overridden by subclasses.
 *
 * <p>The fitness() method returns the maximum of the fitness values, which is
 * clearly nonsensical: you should not be using this method.
 * 
 * <p>Subclasses of this class may add certain auxiliary fitness measures which
 * are printed out by MultiObjectiveStatistics along with the multiple objectives.
 * To have these values printed out, override the getAuxiliaryFitnessNames()
 * and getAuxiliaryFitnessValues() methods.
 *
 * <p>
 * <b>Parameters</b><br>
 * <table>
 * <tr>
 * <td valign=top><i>base</i>.<tt>num-objectives</tt><br>
 * (else)<tt>multi.num-objectives</tt><br>
 * <font size=-1>int &gt;= 1</font></td>
 * <td valign=top>(the number of fitnesses in the objectives array)</td>
 * </tr>
 * 
 * <tr>
 * <td valign=top><i>base</i>.<tt>maximize</tt><br>
 * <font size=-1> bool = <tt>true</tt> (default) or <tt>false</tt></font></td>
 * <td valign=top>(are higher values considered "better"?)
 * </table>
 * 
 * <tr>
 * <td valign=top><i>base</i>.<tt>maximize</tt>.<i>i</i<br>
 * <font size=-1> bool = <tt>true</tt> (default) or <tt>false</tt></font></td>
 * <td valign=top>(are higher values considered "better"?).  Overrides the
 * all-objecgive maximization setting.
 * </table>
 * 
 * <tr>
 * <td valign=top><i>base</i>.<tt>max</tt><br>
 * <font size=-1> double (<tt>1.0</tt> default)</font></td>
 * <td valign=top>(maximum fitness value for all objectives)</table>
 * 
 * <tr>
 * <td valign=top><i>base</i>.<tt>max</tt>.<i>i</i><br>
 * <font size=-1> double (<tt>1.0</tt> default)</font></td>
 * <td valign=top>(maximum fitness value for objective <i>i</i>. Overrides the
 * all-objective maximum fitness.)</table>
 * 
 * <tr>
 * <td valign=top><i>base</i>.<tt>min</tt><br>
 * <font size=-1> double (<tt>0.0</tt> (default)</font></td>
 * <td valign=top>(minimum fitness value for all objectives)</table>
 * 
 * <tr>
 * <td valign=top><i>base</i>.<tt>min</tt>.<i>i</i><br>
 * <font size=-1> double = <tt>0.0</tt> (default)</font></td>
 * <td valign=top>(minimum fitness value for objective <i>i</i>. Overrides the
 * all-objective minimum fitness.)</table>
 * 
 * <p>
 * <b>Default Base</b><br>
 * multi.fitness
 * 
 * @author Sean Luke
 * @version 1.1
 */

public class MultiObjectiveFitness extends Fitness
    {
    private static final long serialVersionUID = 1;

    public static final String MULTI_FITNESS_POSTAMBLE = "[";
    public static final String FITNESS_POSTAMBLE = "]";

    /** parameter for size of objectives */
    public static final String P_NUMOBJECTIVES = "num-objectives";

    /** parameter for max fitness values */
    public static final String P_MAXOBJECTIVE = "max";

    /** parameter for min fitness values */
    public static final String P_MINOBJECTIVE = "min";

    /** Is higher better? */
    public static final String P_MAXIMIZE = "maximize";

    /** Desired maximum fitness values. By default these are 1.0. Shared. */
    public double[] maxObjective;

    /** Desired minimum fitness values. By default these are 0.0. Shared. */
    public double[] minObjective;

    /** Maximization.  Shared. */
    public boolean[] maximize;

    /** The various fitnesses. */
    protected double[] objectives; // values range from 0 (worst) to 1 INCLUSIVE

    /** Returns auxilliary fitness value names to be printed by the statistics object.
        By default, an empty array is returned, but various algorithms may override this to provide additional columns.
    */
    public String[] getAuxilliaryFitnessNames() { return new String[] { }; }

    /** Returns auxilliary fitness values to be printed by the statistics object.
        By default, an empty array is returned, but various algorithms may override this to provide additional columns.
    */
    public double[] getAuxilliaryFitnessValues() { return new double[] { }; }

    /** 
        @Deprecated Use isMaximizing(objective).  This function now just returns whether the first objective is maximizing.
    */
    public boolean isMaximizing()
        {
        return maximize[0];
        }

    public boolean isMaximizing(int objective)
        {
        return maximize[objective];
        }
        

    public int getNumObjectives() { return objectives.length; }
        
    /**
     * Returns the objectives as an array. Note that this is the *actual array*.
     * Though you could set values in this array, you should NOT do this --
     * rather, set them using setObjectives().
     */
    public double[] getObjectives()
        {
        return objectives;
        }

    public double getObjective(int i)
        {
        return objectives[i];
        }

    public void setObjectives(final EvolutionState state, double[] newObjectives)
        {
        if (newObjectives == null)
            {
            state.output.fatal(String.format("Null objective array provided to %s.", this.getClass().getSimpleName()));
            }
        if (newObjectives.length != objectives.length)
            {
            state.output.fatal(String.format("%s: New objective array length does not match current length.", this.getClass().getSimpleName()));
            }
        for (int i = 0; i < newObjectives.length; i++)
            {
            double _f = newObjectives[i];
            if (_f >= Double.POSITIVE_INFINITY || _f <= Double.NEGATIVE_INFINITY || Double.isNaN(_f))
                {
                state.output.warning("Bad objective #" + i + ": " + _f + ", setting to worst value for that objective.");
                if (maximize[i])
                    newObjectives[i] = minObjective[i];
                else
                    newObjectives[i] = maxObjective[i];
                }
            else if (_f > maxObjective[i] || _f < minObjective[i])
                {
                state.output.warnOnce(String.format("%s: The value of objective #%d is outside the expected bounds [%f, %f].  Did you configure the '%s' and '%s' parameters correctly?", this.getClass().getSimpleName(), i, minObjective[i], maxObjective[i], P_MINOBJECTIVE, P_MAXOBJECTIVE));
                }
            }
        objectives = newObjectives;
        }

    public Parameter defaultBase()
        {
        return MultiObjectiveDefaults.base().push(P_FITNESS);
        }

    public Object clone()
        {
        MultiObjectiveFitness f = (MultiObjectiveFitness) (super.clone());
        f.objectives = (double[]) (objectives.clone()); // cloning an array

        // Sadly we have to clone the min/max objective values
        if (maxObjective != null)
            f.maxObjective = (double[]) (maxObjective.clone()); // cloning an array
        if (minObjective != null)
            f.minObjective = (double[]) (minObjective.clone()); // cloning an array
        if (maximize != null)
            f.maximize = (boolean[]) (maximize.clone()); // cloning an array
        return f;
        }

    /**
     * Returns the Max() of objectives, which adheres to Fitness.java's protocol
     * for this method. Though you should not rely on a selection or statistics
     * method which requires this.
     */
    public double fitness()
        {
        double fit = objectives[0];
        for (int x = 1; x < objectives.length; x++)
            if (fit < objectives[x])
                fit = objectives[x];
        return fit;
        }

    /**
     * Sets up. This must be called at least once in the prototype before
     * instantiating any fitnesses that will actually be used in evolution.
     */

    public void setup(EvolutionState state, Parameter base)
        {
        super.setup(state, base); // unnecessary really

        Parameter def = defaultBase();
        int numFitnesses;

        numFitnesses = state.parameters.getInt(base.push(P_NUMOBJECTIVES), def.push(P_NUMOBJECTIVES), 0);
        if (numFitnesses <= 0)
            state.output.fatal("The number of objectives must be an integer >= 1.", base.push(P_NUMOBJECTIVES), def.push(P_NUMOBJECTIVES));

        objectives = new double[numFitnesses];
        maxObjective = new double[numFitnesses];
        minObjective = new double[numFitnesses];
        maximize = new boolean[numFitnesses];
                
        for (int i = 0; i < numFitnesses; i++)
            {
            // load default globals
            minObjective[i] = state.parameters.getDoubleWithDefault(base.push(P_MINOBJECTIVE), def.push(P_MINOBJECTIVE), 0.0);
            maxObjective[i] = state.parameters.getDoubleWithDefault(base.push(P_MAXOBJECTIVE), def.push(P_MAXOBJECTIVE), 1.0);
            maximize[i] = state.parameters.getBoolean(base.push(P_MAXIMIZE), def.push(P_MAXIMIZE), true);

            // load specifics if any
            minObjective[i] = state.parameters.getDoubleWithDefault(base.push(P_MINOBJECTIVE).push("" + i), def.push(P_MINOBJECTIVE).push("" + i), minObjective[i]);
            maxObjective[i] = state.parameters.getDoubleWithDefault(base.push(P_MAXOBJECTIVE).push("" + i), def.push(P_MAXOBJECTIVE).push("" + i), maxObjective[i]);
            maximize[i] = state.parameters.getBoolean(base.push(P_MAXIMIZE).push("" + i), def.push(P_MAXIMIZE).push("" + i), maximize[i]);
            
            // test for validity
            if (minObjective[i] >= maxObjective[i])
                state.output.error("For objective " + i + "the min fitness must be strictly less than the max fitness.");
            }
        state.output.exitIfErrors();
        }

    /**
     * Returns true if this fitness is the "ideal" fitness. Default always
     * returns false. You may want to override this.
     */
    public boolean isIdealFitness()
        {
        return false;
        }

    /**
     * Returns true if I'm equivalent in fitness (neither better nor worse) to
     * _fitness. The rule I'm using is this: If one of us is better in one or
     * more criteria, and we are equal in the others, then equivalentTo is
     * false. If each of us is better in one or more criteria each, or we are
     * equal in all criteria, then equivalentTo is true.   Multiobjective optimization algorithms may
     * choose to override this to do something else.
     */

    public boolean equivalentTo(Fitness _fitness)
        {
        MultiObjectiveFitness other = (MultiObjectiveFitness) _fitness;
        boolean abeatsb = false;
        boolean bbeatsa = false;

        if (objectives.length != other.objectives.length)
            throw new RuntimeException("Attempt made to compare two multiobjective fitnesses; but they have different numbers of objectives.");
        
        for (int x = 0; x < objectives.length; x++)
            {
            if (maximize[x] != other.maximize[x])  // uh oh
                throw new RuntimeException(
                    "Attempt made to compare two multiobjective fitnesses; but for objective #" + x + 
                    ", one expects higher values to be better and the other expectes lower values to be better.");

            if (maximize[x])
                {
                if (objectives[x] > other.objectives[x])
                    abeatsb = true;
                if (objectives[x] < other.objectives[x])
                    bbeatsa = true;
                if (abeatsb && bbeatsa)
                    return true;
                }
            else
                {
                if (objectives[x] < other.objectives[x])
                    abeatsb = true;
                if (objectives[x] > other.objectives[x])
                    bbeatsa = true;
                if (abeatsb && bbeatsa)
                    return true;
                }
            }
        if (abeatsb || bbeatsa)
            return false;
        return true;
        }

    /**
     * Returns true if I'm better than _fitness. The DEFAULT rule I'm using is this: if
     * I am better in one or more criteria, and we are equal in the others, then
     * betterThan is true, else it is false. Multiobjective optimization algorithms may
     * choose to override this to do something else.
     */

    public boolean betterThan(Fitness fitness)
        {
        return paretoDominates((MultiObjectiveFitness)fitness);
        }

    /**
     * Returns true if I'm better than _fitness. The rule I'm using is this: if
     * I am better in one or more criteria, and we are equal in the others, then
     * betterThan is true, else it is false.
     */

    public boolean paretoDominates(MultiObjectiveFitness other)
        {
        boolean abeatsb = false;

        if (objectives.length != other.objectives.length)
            throw new RuntimeException("Attempt made to compare two multiobjective fitnesses; but they have different numbers of objectives.");
            
        for (int x = 0; x < objectives.length; x++)
            {
            if (maximize[x] != other.maximize[x])  // uh oh
                throw new RuntimeException(
                    "Attempt made to compare two multiobjective fitnesses; but for objective #" + x + 
                    ", one expects higher values to be better and the other expectes lower values to be better.");

            if (maximize[x])
                {
                if (objectives[x] > other.objectives[x])
                    abeatsb = true;
                else if (objectives[x] < other.objectives[x])
                    return false;
                }
            else
                {
                if (objectives[x] < other.objectives[x])
                    abeatsb = true;
                else if (objectives[x] > other.objectives[x])
                    return false;
                }
            }
            
        return abeatsb;
        }

    // Remove an individual from the ArrayList, shifting the topmost
    // individual in his place
    static void yank(int val, ArrayList<Individual> list)
        {
        int size = list.size();
        list.set(val, list.get(size - 1));
        list.remove(size - 1);
        }

    /**
     * Divides an array of Individuals into the Pareto front and the "nonFront" (everyone else). 
     * The Pareto front is returned.  You may provide ArrayLists for the front and a nonFront.
     * If you provide null for the front, an ArrayList will be created for you.  If you provide
     * null for the nonFront, non-front individuals will not be added to it.  This algorithm is
     * O(n^2).
     */
    public static ArrayList<Individual> partitionIntoParetoFront(ArrayList<Individual> inds, ArrayList<Individual> front, ArrayList<Individual> nonFront)
        {
        if (front == null)
            front = new ArrayList<Individual>();
                        
        // put the first guy in the front
        front.add(inds.get(0));
                
        // iterate over all the remaining individuals
        for (int i = 1; i < inds.size(); i++)
            {
            Individual ind = (Individual) (inds.get(i));

            boolean noOneWasBetter = true;
            int frontSize = front.size();
                        
            // iterate over the entire front
            for (int j = 0; j < frontSize; j++)
                {
                Individual frontmember = (Individual) (front.get(j));
                                
                // if the front member is better than the individual, dump the individual and go to the next one
                if (((MultiObjectiveFitness) (frontmember.fitness)).paretoDominates((MultiObjectiveFitness) (ind.fitness)))
                    {
                    if (nonFront != null) nonFront.add(ind);
                    noOneWasBetter = false;
                    break;  // failed.  He's not in the front
                    } 
                // if the individual was better than the front member, dump the front member.  But look over the
                // other front members (don't break) because others might be dominated by the individual as well.
                else if (((MultiObjectiveFitness) (ind.fitness)).paretoDominates((MultiObjectiveFitness) (frontmember.fitness)))
                    {
                    yank(j, front);
                    // a front member is dominated by the new individual.  Replace him
                    frontSize--; // member got removed
                    j--;  // because there's another guy we now need to consider in his place
                    if (nonFront != null) nonFront.add(frontmember);
                    }
                }
            if (noOneWasBetter)
                front.add(ind);
            }
        return front;
        }

    /**
     * Returns the Pareto Front of the provided Individuals, sorted by objective 0, breaking ties with objective 1, and so on...
     * <p>This would be useful for printing out statistics.
     */
    public static ArrayList<Individual> getSortedParetoFront(ArrayList<Individual> inds)
        {
        ArrayList<Individual> front = partitionIntoParetoFront(inds, null, null);

        // sort by objective[0], breaking ties by objective[1], breaking ties by objective[2], etc.
        Object[] sortedFront = front.toArray();
        QuickSort.qsort(sortedFront, new SortComparator()
            {
            public boolean lt(Object a, Object b)
                {
                MultiObjectiveFitness fa = ((MultiObjectiveFitness) (((Individual) a).fitness));
                MultiObjectiveFitness fb = ((MultiObjectiveFitness) (((Individual) b).fitness));
                                
                int objs = fa.getNumObjectives();
                                
                for(int i = 0; i < objs; i++)
                    {
                    if (fa.getObjective(i) < fb.getObjective(i)) return true;
                    else if (fa.getObjective(i) > fb.getObjective(i)) return false;
                    }
                return false;
                }
                        
            public boolean gt(Object a, Object b)
                {
                MultiObjectiveFitness fa = ((MultiObjectiveFitness) (((Individual) a).fitness));
                MultiObjectiveFitness fb = ((MultiObjectiveFitness) (((Individual) b).fitness));
                                
                int objs = fa.getNumObjectives();
                                
                for(int i = 0; i < objs; i++)
                    {
                    if (fa.getObjective(i) > fb.getObjective(i)) return true;
                    else if (fa.getObjective(i) < fb.getObjective(i)) return false;
                    }
                return false;
                }
            });
                
        final ArrayList<Individual> sorted = new ArrayList<Individual>(sortedFront.length);
        for (final Object ind : sortedFront)
            sorted.add((Individual)ind);
        return sorted;
        }
                

    /** Divides inds into pareto front ranks (each an ArrayList), and returns them, in order,
        stored in an ArrayList. */
    public static ArrayList<ArrayList<Individual>> partitionIntoRanks(ArrayList<Individual> inds)
        {
        ArrayList<ArrayList<Individual>> frontsByRank = new ArrayList<ArrayList<Individual>>();

        while(inds.size() > 0)
            {
            ArrayList<Individual> front = new ArrayList<Individual>();
            ArrayList<Individual> nonFront = new ArrayList<Individual>();
            MultiObjectiveFitness.partitionIntoParetoFront(inds, front, nonFront);
                        
            // build inds out of remainder
            inds = new ArrayList<Individual>(nonFront);
            frontsByRank.add(front);
            }
        return frontsByRank;
        }


    /** Returns the Pareto rank for each individual.  Rank 0 is the best rank, then rank 1, and so on.  This is O(n) but it has a high constant overhead because it
        allocates a hashmap and does some autoboxing. */
    public static int[] getRankings(ArrayList<Individual> inds)
        {
        int[] r = new int[inds.size()];
        ArrayList<ArrayList<Individual>> ranks = partitionIntoRanks(inds);  // get all the ranks
        
        // build a mapping of Individual -> index in inds array
        HashMap<Individual, Integer> m = new HashMap<Individual, Integer>();
        for(int i = 0; i < inds.size(); i++)
            m.put(inds.get(i), Integer.valueOf(i));
        
        int numRanks = ranks.size();
        for(int rank = 0 ; rank < numRanks; rank++)  // for each rank...
            {
            ArrayList<Individual> front = ranks.get(rank);
            int numInds = front.size();
            for(int ind = 0; ind < numInds; ind++)  // for each individual in that rank ...
                {
                // get the index of the individual in the inds array
                int i = ((Integer)(m.get(front.get(ind)))).intValue();
                r[i] = rank;  // set the rank in the corresponding ranks array
                }
            }
        return r;
        }



    /**
     * Returns the sum of the squared difference between two Fitnesses in Objective space.
     */
    public double sumSquaredObjectiveDistance(MultiObjectiveFitness other, boolean normalize)
        {
        double s = 0;
        for (int i = 0; i < objectives.length; i++)
            {
            double a = (objectives[i] - other.objectives[i]);
            if (normalize)
                a /= maxObjective[i];
            s += a * a;
            }
        return s;
        }


    /**
     * Returns the Manhattan difference between two Fitnesses in Objective space.
     */
    public double manhattanObjectiveDistance(MultiObjectiveFitness other)
        {
        double s = 0;
        for (int i = 0; i < objectives.length; i++)
            {
            s += Math.abs(objectives[i] - other.objectives[i]);
            }
        return s;
        }


    public String fitnessToString()
        {
        String s = FITNESS_PREAMBLE + MULTI_FITNESS_POSTAMBLE;
        for (int x = 0; x < objectives.length; x++)
            {
            if (x > 0)
                s = s + " ";
            s = s + Code.encode(objectives[x]);
            }
        return s + FITNESS_POSTAMBLE;
        }


    public String fitnessToStringForHumans()
        {
        String s = FITNESS_PREAMBLE + MULTI_FITNESS_POSTAMBLE;
        for (int x = 0; x < objectives.length; x++)
            {
            if (x > 0)
                s = s + " ";
            s = s + objectives[x];
            }
        return s + FITNESS_POSTAMBLE;
        }

    public void readFitness(final EvolutionState state, final LineNumberReader reader) throws IOException
        {
        DecodeReturn d = Code.checkPreamble(FITNESS_PREAMBLE + MULTI_FITNESS_POSTAMBLE, state, reader);
        for (int x = 0; x < objectives.length; x++)
            {
            Code.decode(d);
            if (d.type != DecodeReturn.T_DOUBLE)
                state.output.fatal("Reading Line " + d.lineNumber + ": " + "Bad Fitness (objectives value #" + x + ").");
            objectives[x] = (double) d.d;
            }
        }

    public void writeFitness(final EvolutionState state, final DataOutput dataOutput) throws IOException
        {
        dataOutput.writeInt(objectives.length);
        for (int x = 0; x < objectives.length; x++)
            dataOutput.writeDouble(objectives[x]);
        for (int x = 0; x < objectives.length; x++)
            dataOutput.writeDouble(maxObjective[x]);
        for (int x = 0; x < objectives.length; x++)
            dataOutput.writeDouble(minObjective[x]);
        for (int x = 0; x < objectives.length; x++)
            dataOutput.writeBoolean(maximize[x]);
        writeTrials(state, dataOutput);
        }

    public void readFitness(final EvolutionState state, final DataInput dataInput) throws IOException
        {
        int len = dataInput.readInt();
        if (objectives == null || objectives.length != len)
            {
            objectives = new double[len];
            maxObjective = new double[len];
            minObjective = new double[len];
            maximize = new boolean[len];
            }
        for (int x = 0; x < objectives.length; x++)
            objectives[x] = dataInput.readDouble();
        for (int x = 0; x < objectives.length; x++)
            maxObjective[x] = dataInput.readDouble();
        for (int x = 0; x < objectives.length; x++)
            minObjective[x] = dataInput.readDouble();
        for (int x = 0; x < objectives.length; x++)
            maximize[x] = dataInput.readBoolean();
        readTrials(state, dataInput);
        }


    public void setToBestOf(EvolutionState state, Fitness[] fitnesses)
        {
        state.output.fatal("setToBestOf(EvolutionState, Fitness[]) not implemented in " + this.getClass());
        }

    public void setToMeanOf(EvolutionState state, Fitness[] fitnesses)
        {
        // basically we compute the centroid of the fitnesses
        double sum = 0.0;
        for(int i = 0; i < objectives.length; i++)
            {
            for(int k = 0; k < fitnesses.length; k++)
                {
                MultiObjectiveFitness f = (MultiObjectiveFitness) fitnesses[k];
                sum += f.objectives[i];
                }
            objectives[i] = (double)(sum / fitnesses.length);
            }
        }

    public void setToMedianOf(EvolutionState state, Fitness[] fitnesses)
        {
        state.output.fatal("setToMedianOf(EvolutionState, Fitness[]) not implemented in " + this.getClass());
        }
    }
