/** GPPopulation.java
 * J Scott Cameron
 * This class controls a population
 * of Genetic Programs
 * and controls their regeneration
 */

import GPNode;
import GPTerminalNode;
import GPBinaryNode;
import GPUnaryNode;
import GPVariableNode;
import GPPair;
import GPFunctionTemplate;
import java.io.*;
import java.util.*;
import java.lang.reflect.*;

public class GPPopulation{
    
    private GPNodeContainer population[];/* The population of GP's */
    
    private boolean mutation;/* controls whether or not mutation occurs */
    private boolean crossover;/* controls whether or not crossover occurs */
    private double mutationRate;/* the rate at which mutation occurs */
    private int popSize;/* size of the population */
    private static Random random;
    
    /* class which implements GPFunctionTemplate
     * so that GP can retreive all the possible methods
     */
    private GPFunctionTemplate gpft; 
    private Vector binaryFunctions;/* possible binary Functions*/
    private Vector unaryFunctions;/* possible unary functions*/
    private Vector variables;/* possible variables */
    private double sumFitness;/* sum of all the fitness ratings */
    private double lowestFitness;/* lowest fitness in the population */

    public GPPopulation()
    {
    }
    
    /* parameterized contructor */
    public GPPopulation(GPFunctionTemplate gpft,int popSize,boolean crossover,
    boolean mutation, double mutationRate)
    {

        this.gpft = gpft;
        this.popSize = popSize;
        this.crossover = crossover;
        this.mutation = mutation;
        this.mutationRate = mutationRate;
        random = new Random();
        binaryFunctions = gpft.getBinaryFunctions();
        unaryFunctions = gpft.getUnaryFunctions();
        variables = gpft.getVariables();
        population = new GPNodeContainer[popSize];
        
        
        GPNode gpn;
        
        /* fill the population with random function trees */
        for(int i=0;i<popSize;i++)
        {
            
            /* make the first node a binary function to ensure some
             * initial complexity*/
            int b_num = Math.abs(nextRandInt())%binaryFunctions.size();
            gpn = new GPBinaryNode(gpft,(GPPair)binaryFunctions.get(b_num));
            /* set its children to being completely random */
            gpn.setChild(0, makeNode()) ;
            gpn.setChild(1,makeNode())  ;

            population[i] = new GPNodeContainer(gpn);
        }    
    }
    
    /* creates a node from a string */
    public GPNode makeNodeFromString(String s)
    throws IllegalArgumentException
    {
       
        s.trim();
        StringTokenizer st = new StringTokenizer(s,"(),",false);
        return parseString(st);
    }
    
    /* parses the string represening a function tree 
     * this function takes the tokenized string and 
     * figure out what kind of node it is by checking
     * all the possible node symbols.
     * If it finds a type then it parses token appropriately
     * and figures out which following nodes are children
     */
    public GPNode parseString(StringTokenizer st)
    throws IllegalArgumentException
    {
        String token = st.nextToken();
        GPNode temp = null;
        int i;
        
        for(i=0;i<unaryFunctions.size();i++)
        {
            if(token.equalsIgnoreCase(((GPPair)unaryFunctions.get(i)).sign))
            {
                temp = new GPUnaryNode(gpft,(GPPair)unaryFunctions.get(i));
                temp.setChild(0,parseString(st));
                return temp;
            }
        }
        for(i=0;i<binaryFunctions.size();i++)
        {
            if(token.equalsIgnoreCase(((GPPair)binaryFunctions.get(i)).sign))
            {
                temp = new GPBinaryNode(gpft,(GPPair)binaryFunctions.get(i));
                temp.setChild(0, parseString(st) );
                temp.setChild(1, parseString(st) );
                return temp;
            }
        }
        for(i=0;i<variables.size();i++)
        {
            if(token.equalsIgnoreCase( ((GPPair)variables.get(i)).sign))
            {
                return new GPVariableNode(gpft,(GPPair)variables.get(i));
            }
        }
        try{
            temp = new GPTerminalNode(Double.parseDouble(token));
        }
        /* if no matches are found and it's not a double
         * then its an illegal token */
        catch(IllegalArgumentException e)
        {
            throw new IllegalArgumentException(token +
                      " is not a valid double or variable");
        }
        return temp;
        
    }
    
    /* randomly generates a funciton tree */
    public GPNode makeNode()
    {
        /* get a random node type */
        int nodetype = getRandomNodeType();
        GPNode gpn;
        
        /* makes the chosen type of node */
        switch(nodetype)
        {
            case GPNode.TERMINAL:
                gpn = new GPTerminalNode(random);
                break;
            case GPNode.BINARY:
                int b_num = Math.abs(nextRandInt())%binaryFunctions.size();
                gpn = new GPBinaryNode(gpft,
                                       (GPPair)binaryFunctions.get(b_num));
                gpn.setChild(0, makeNode()) ;
                gpn.setChild(1,makeNode())  ;
                break;
            case GPNode.UNARY:
                int u_num = Math.abs(nextRandInt())%unaryFunctions.size();
                gpn = new GPUnaryNode(gpft,
                                      (GPPair)unaryFunctions.get(u_num));
                gpn.setChild(0, makeNode()) ;
                break;
            case GPNode.VARIABLE:
                int v_num = Math.abs(nextRandInt())%variables.size();
                gpn = new GPVariableNode(gpft,(GPPair)variables.get(v_num));
                
                break;
                default:
                    gpn = null;
        }
        
        return gpn;
    }
    
    /* evaluates the fitness of all the GP's in the population */
    public void evaluatePopulation()
    {
        int i;
        /* iterate through the population and set their
         * ratings */
        for( i=0;i<popSize;i++)
        {
            population[i].setRating(gpft.fitnessFunction(
                                     population[i].getNode()).doubleValue());
        }
        
        /* sort the population */
        Arrays.sort(population,new GPNodeComparator());
     
    }
    
    /* returns the worst GP */
    public GPNodeContainer worst()
    {
        return population[popSize-1];
    }
    
    /* returns the best GP */
    public GPNodeContainer best()
    {
        return population[0];
    }
    
    /* returns the average fitness */
    public double avg()
    {
        double total =0;
        for(int i=0;i<population.length;i++)
        {
            total += population[i].getRating();
        }
        return total/population.length;
        
    }
    
    /* returns a GPNode which is a cross of the nodes given */
    public GPNode crossover(GPNode a, GPNode b)
    {
        
        GPNode gpn = a.copy();
        
        /* choose random points in the trees to cross at */
        int aRand = (Math.abs(nextRandInt())%a.count())+1;
        int bRand = (Math.abs(nextRandInt())%b.count())+1;
        
        /* pull a copy of the chosen subtree from b and
         * and replace it in the appropriate spot in the 
         * new Node */
        gpn.setDescendant(aRand,(b.find(bRand)).copy());
        
        return gpn;
    }
    
    /* returns a mutated version of the given node */
    public GPNode mutate(GPNode gpn)
    {
        /* each node type mutates differently
         * so find the type*/
        switch(gpn.getType())
        {
            /* the binary node can mutate its function
             * and mutate its children's node type
             */
            case GPNode.BINARY:
            {
                if(shouldMutate())
                {
                    int b_num = Math.abs(nextRandInt())%binaryFunctions.size();
                    gpn.setFunction((GPPair)binaryFunctions.get(b_num));
                }
                if(shouldMutate())gpn.setChild(0,changeType(gpn.getChild(0)));
                gpn.setChild(0,mutate(gpn.getChild(0)));
                if(shouldMutate())gpn.setChild(1,changeType(gpn.getChild(1)));
                gpn.setChild(1,mutate(gpn.getChild(1)));
                
            }
            break;
            /* the unary node can mutate its function
             * and mutate its child's node type
             */
            case GPNode.UNARY:
            {
                if(shouldMutate())
                {
                    int u_num = Math.abs(nextRandInt())%unaryFunctions.size();
                    gpn.setFunction((GPPair)unaryFunctions.get(u_num));
                }
                if(shouldMutate())gpn.setChild(0,changeType(gpn.getChild(0)));
                gpn.setChild(0,mutate(gpn.getChild(0)));
            }
            break;
            /* the variable node can mutate its function */
            case GPNode.VARIABLE:
            {
                if(shouldMutate())
                {
                    int v_num = Math.abs(nextRandInt())%variables.size();
                    gpn.setFunction((GPPair)variables.get(v_num));
                }
            }
            break;
            /* a terminal node can change it's double value */
            case GPNode.TERMINAL:
            {
                if(shouldMutate())
                {
                    gpn = new GPTerminalNode(random);
                }
            }
            break;
        }
        return gpn;
    }
    
    /* changes the type of the node */
    public GPNode changeType(GPNode gpn)
    {
        /* pick the new node type */
        int newType = getRandomNodeType();
        int oldType = gpn.getType();
        GPNode temp = gpn;
        
        /* if the new type is the same as the old type
         * who cares, no change */
        if(newType != oldType)
        {
            switch(newType)
            {
                /* binary node needs to get a function 
                   and create two child subtrees */
                case GPNode.BINARY:
                {
                    int b_num = Math.abs(nextRandInt())%binaryFunctions.size();
                    temp = new GPBinaryNode(gpft,
                                        (GPPair)binaryFunctions.get(b_num));
                    
                    /* if the node used to be a Unary node
                     * then grab its child and use it as one 
                     * of the new node's children
                     */
                    if(oldType == GPNode.UNARY)
                    {
                        if(Math.abs(nextRandInt())%2 == 0)
                        {
                            temp.setChild(0,gpn.getChild(0));
                            temp.setChild(1,makeNode());
                            
                        }
                        else
                        {
                            temp.setChild(1,gpn.getChild(0));
                            temp.setChild(0,makeNode());
                        }
                    }
                    /* other wise just generate two new children */
                    else
                    {
                        temp.setChild(0,makeNode());
                        temp.setChild(1,makeNode());
                    }
                }
                break;
                /* unary node needs to get a function 
                   and create a child subtree */
                case GPNode.UNARY:
                {
                    int u_num = Math.abs(nextRandInt())%unaryFunctions.size();
                    temp = new GPUnaryNode(gpft,
                                           (GPPair)unaryFunctions.get(u_num));
                    
                    /* if the old node was binary grab one of its
                     * children and use it as a child to the new node */
                    if(oldType == GPNode.BINARY)
                    {
                        if(Math.abs(nextRandInt())%2 == 0)
                        {
                            temp.setChild(0,gpn.getChild(0));
                        }
                        else
                        {
                            temp.setChild(0,gpn.getChild(1));
                        }
                    }
                    /* else just generate a new child */
                    else
                    {
                        temp.setChild(0,makeNode());
                        
                    }
                }
                break;
                /* the variable just needs a variable assigned to it */
                case GPNode.VARIABLE:
                {
                    int v_num = Math.abs(nextRandInt())%variables.size();
                    temp = new GPVariableNode(gpft,
                                              (GPPair)variables.get(v_num));
                }
                break;
                /* Terminal just needs to be initialized*/
                case GPNode.TERMINAL:
                {
                    temp = new GPTerminalNode(random);
                }
                break;
            }
     
        }
        
        return temp;
    }

    /* returns a positive random int*/
    public int nextRandInt()
    {
        return Math.abs(random.nextInt());
    }
    
    /* returns a random node type */
    public int getRandomNodeType()
    {
       
        return Math.abs(random.nextInt())%4;
        
    }
    
    /* returns a boolean based upon the 
     * mutation rate */
    public boolean shouldMutate()
    {

        return (random.nextDouble() < mutationRate);
    }
    
    /* generate a new population */
    public void regeneratePopulation()
    {
        GPNodeContainer nextGen[] = new GPNodeContainer[popSize];
        
        /* clone best GP */
        nextGen[0] = population[0];
        int i,j,k;
        
        sumFitness = 0;
        lowestFitness = worst().getRating()-1;
        
        /* calculate the sume fitness */
        for(i=0;i<popSize;i++)
        {
            sumFitness += (population[i].getRating()-lowestFitness);
        }
        
        GPNode gpn = null;
        
        /* create the new population */
        for(i=1;i<popSize;i++)
        {
            /* if crossover is on grap two GP's
             * and cross them
             */
            if(crossover)
            {
                gpn = crossover(RouletteSelection(),
                                RouletteSelection());
                
            }
            /* else just grab a GP and clone it */
            else
            {
                gpn = RouletteSelection();
            }
            
            /* if mutation is on, mutate the new GP */
            if(mutation)
            {
                gpn =  mutate(gpn);
                
            }
            
            nextGen[i] = new GPNodeContainer(gpn);
              
        }
        
        /* copy the new generation into the population array*/
        population = nextGen;
        
    }
    
    /* randomly selects a GP using roulette
     * style selection - the higher the fitness
     * the higher likelihood of reproducing
     **/
    public GPNode RouletteSelection()
    {

        double x = Math.abs(random.nextInt())%sumFitness;
        int count =0;
        for(int i=0;i <  popSize ;i++)
        {
            count+=(population[i].getRating()-lowestFitness);
            if(count >= x)
            {
                return population[i].getNode();
            }
        }
        
        return population[popSize-1].getNode();
    }
    
    /* prints the functions strings for every GP in the 
     * population */
    public String toString()
    {
        StringWriter sw = new StringWriter();
        for(int i=0;i<popSize;i++)
        {
            sw.write(population[i].getNode().toString());
            sw.write("\t");
            sw.write((new Double(population[i].getRating())).toString());
            sw.write("\n");
        }
        return sw.toString();
    }    
}