/* population.cpp
 *
 * J Scott Cameron adapted for Genetic Images
 * from Hans Kuhlmann / Mike Hollick
 * available at
 * http://www.cis.upenn.edu/~hollick/genetic/paper2.html
 *
 * should_mutate ,open, mutate, change_type are 
 * entirely original
 *
 * This file contains the implementation for the population class
 */



#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#include "trees.h"

int int_rand(int n)
{
	return rand()%n;
}

// population class constructor.takes the initial size, and lists and numbers
// of binary & unary functions, and variables that are available.  also takes
// a function to be used for generating random constants (the potential values
// of these constants may vary from application to application)
Population::Population(int s, Binary_Func **bs, int num_bs, 
                       Unary_Func **us, int num_us,
                       Variable **vs, int num_vs,
                       Val (*f)(void))
{
    // first just copy in the args
    size = s;
    b_funcs = bs;
    num_b_funcs = num_bs;
    u_funcs = us;
    num_u_funcs = num_us;
    vars = vs;
    num_vars = num_vs;
    const_rand = f;
	
    // allocate the tree pointer list
    trees = new Binary_Node *[size];
	
    // check
    if (!trees) {
        // output error message
        fprintf(stderr,"can't allocate tree pointer list!\n");
        // flag the error
        size = 0;
        return;
    }
	
    // initalize the random number generator
    time_t *tp = NULL;
    srand((unsigned int)time(tp));
	
    // go through the list and create new top level nodes.  pick the function
    // randomly from the list
    for (int i=0;i<size;i++)
		trees[i] = new Binary_Node(NULL,b_funcs[int_rand(num_b_funcs)]);
	
    // now go through the nodes and recursively build the random trees
	for (i=0;i<size;i++)
		build_tree(trees[i]);
}


// this generates a random node, whos parent is n. it is mutually recursive
// with the build_tree's
Node *Population::new_node(Node *n)
{
    // pick a node type for new node
    int type = int_rand(4);
	
    // points to the new node
    Node *newnode;
	
    // create the new node
    switch (type) {
		
	case NODE_BINARY:
		{
            // create it with a random function
            Binary_Node *nn= new Binary_Node(
				   n,b_funcs[int_rand(num_b_funcs)]);
            // save the pointer
            newnode = (Node *)nn;
            
            // recursively build the new subtree
            build_tree(nn);
        }
        break;
		
		
	case NODE_UNARY:
		{
            // create it with a random function
            Unary_Node *nn = new Unary_Node(n,u_funcs[int_rand(num_u_funcs)]);
            // save the pointer
            newnode = (Node *)nn;
            
            // recursively build the new subtree
            build_tree(nn);
        }
		break;
		
	case NODE_CONST:
        {
            // create it with a random constant value
            Terminal_Const *nn = new Terminal_Const(n,const_rand());
            // save the pointer
            newnode = (Node *)nn;
        }
        break;
		
	case NODE_VAR:
        {
            // create it with a random variable
            Terminal_Var *nn = new Terminal_Var(n,vars[int_rand(num_vars)]);
            // save the pointer
            newnode = (Node *)nn;
        }
        break;
    }
	
    // return this new node
    return newnode;
}

//Answers the question "Sould I mutute?"
bool Population::should_mutate()
{
	
	if( (rand()%10000) < 10000*g_mutate)
	{
		return true;
	}
	return false;
}

// this is responsible for generating a random subtree from a binary node base.
void Population::build_tree(Binary_Node *n)
{
    // make the left subtree
    Node *left = new_node((Node *)n);
    // assign it to this node's left
    n->set_left(left);
	
    // make the right subtree
    Node *right = new_node((Node *)n);
    // assign it to this node's right
    n->set_right(right);
}


// this is responsible to generating a random subtree from a unary node base
void Population::build_tree(Unary_Node *n)
{
    // make the child subtree
    Node *child = new_node((Node *)n);
    // assign it
    n->set_child(child);
}

// utility function for sorting the population
int tree_comp(const void *a1, const void *a2)
{
    // recast the args
    const Binary_Node *x = *((const Binary_Node **)a1);
    const Binary_Node *y = *((const Binary_Node **)a2);
	
    // do the compare
    if (x->fitness > y->fitness)
		return -1;
    else 
		if (x->fitness == y->fitness)
			return 0;
		else
			return 1;
}


/* Opens a genetic program from a string description */
Node *Population::open(Node* n, string* input, int* index)
{
	int i;
	
	
	int next = input->find("(",(*index)+1);
	int ifVar = input->find_first_of("),",(*index)+1);
	
	string token;

	/* figure out what type of token is next in the string */
	if( (ifVar < next || ((next == -1) && (ifVar > 0))) )
	{
		token = input->substr((*index)+1, (ifVar-(*index))-1);
		(*index) = ifVar-1;
	}
	else
	{
		token = input->substr((*index)+1, (next-(*index))-1);
		(*index) = next;
	}
    
	/* then parse appropriately */
	if( (ifVar < next || ((next == -1) && (ifVar > 0))) )
		/* its a variable, find out which and create a node */
	{
		for(i=0;i<num_vars;i++)
		{
			if(token == vars[i]->name)
			{
				
				return new Terminal_Var(n,vars[i]);
				
			}
		}
	}
	else if(token == "#")
		/* is a constant, parse the doubles */
	{
		
		double r,g,b;
		next = input->find(",",(*index)+1);
		r=atof(input->substr((*index)+1, (next-(*index))-1).c_str());
		(*index) = next;
		next = input->find(",",(*index)+1);
		g=atof(input->substr((*index)+1, (next-(*index))-1).c_str());
		(*index) = next;
		next = input->find(")",(*index)+1);
		b=atof(input->substr((*index)+1, (next-(*index))-1).c_str());
		(*index) = next;
		Val v = Val(r,g,b);
		return new Terminal_Const(n,v);
	}
	else
	{
		for(i=0;i<num_u_funcs;i++)
			/* iterate through possible unary functions 
			 * checking each name against the string */
		{
			if(token == u_funcs[i]->sign)
			{
				
				Unary_Node* un = new Unary_Node(n,u_funcs[i]);
				un->set_child( open(un,input,index) );
				if(un->get_child() == NULL)
				{
					return NULL;
				}
				next = input->find(")",(*index)+1);
				(*index) = next;
				return un;
				
			}
		}
		for(i=0;i<num_b_funcs;i++)
			/* iterate through possible binary functions 
			 * checking each name against the string */
		{
			if(token == b_funcs[i]->sign)
			{
				
				Binary_Node* bn = new Binary_Node(n,b_funcs[i]);
				bn->set_left( open(bn,input,index) );
				if(bn->get_left() == NULL)
				{
					return NULL;
				}
				next = input->find(",",(*index)+1);
				(*index) = next;
				bn->set_right( open(bn,input,index) );
				if(bn->get_right() == NULL)
				{
					return NULL;
				}
				next = input->find(")",(*index)+1);
				(*index) = next;
				return bn;
				
			}
		}
	}
	
	return NULL;
}

/* changes the node type (for mutation) and re-initializes the node 
 * as needed */
Node *Population::change_type(Node *n)
{
	/* pick the new node type */

	int newtype = int_rand(4);
	int oldtype = n->type;

	 /* if the new type is the same as the old type
      * who cares, no change, get out of here*/
	if(newtype != oldtype)
	{
		//	n->type = newtype;
		
		
		
		switch(newtype)
		{
		case NODE_BINARY:
			/* binary node needs to get a function 
              and create two child subtrees */

			{
				Binary_Node *bn = new Binary_Node(
					   n->parent,b_funcs[int_rand(num_b_funcs)]);
				if(oldtype == NODE_UNARY)
					/* 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(rand()%2 == 0)
					{
						bn->set_left( ((Unary_Node*)n)->get_child());
						
						Node *right = new_node((Node *)bn);
						// assign it to this node's right
						bn->set_right(right);
					}
					else
					{
						bn->set_right( ((Unary_Node*)n)->get_child());
						
						Node *right = new_node((Node *)bn);
						// assign it to this node's right
						bn->set_left(right);
						
					}
					
				}
				else
					/* other wise just generate two new children */
				{
					build_tree(bn);
				}
				n = bn;
			}
			break;
		case NODE_UNARY:
			/* unary node needs to get a function 
                   and create a child subtree */

			{
				Unary_Node *un = new Unary_Node(
					 n->parent,u_funcs[int_rand(num_u_funcs)]);
				if(oldtype == NODE_BINARY)
					/* if the old node was binary grab one of its
                     * children and use it as a child to the new node */
				{
					if(rand()%2 == 0)
					{
						un->set_child( ((Binary_Node*)n)->get_right());
						
					}
					else
					{
						un->set_child( ((Binary_Node*)n)->get_left());
					}
					
				}
				else
					/* else just generate a new child */

				{
					build_tree(un);
				}
				n = un;
			}
			break;
			
		case NODE_CONST:
			{
				// create it with a random constant value
				Terminal_Const *nn = new Terminal_Const(n,const_rand());
				// save the pointer
				n = nn;
			}
			break;
			
		case NODE_VAR:
			{
				// create it with a random variable
				Terminal_Var *nn = new Terminal_Var(
					                 n,vars[int_rand(num_vars)]);
				// save the pointer
				n = nn;
			}
			break;
			
			
			
			
		}
	}
	return n;
	
}

/* mutates a node */
void Population::mutate(Node *p1)
{
	
	Node *temp = p1;
	
	/* each node type mutates differently
     * so find the type*/

	switch(p1->type){
	case NODE_BINARY:
		/* the binary node can mutate its function
             * and mutate its children's node type
             */

		{
			Binary_Node *Btemp = (Binary_Node *)temp;
			
			if(should_mutate())Btemp->f=b_funcs[int_rand(num_b_funcs)];
			if(should_mutate())Btemp->left = change_type(Btemp->get_left());
			mutate(Btemp->get_left());
			if(should_mutate())Btemp->right = change_type(Btemp->get_right());
			mutate(Btemp->get_right());
			
			
		}
		break;
	case NODE_UNARY:
		/* the unary node can mutate its function
             * and mutate its child's node type
             */

		{
			Unary_Node *Utemp = (Unary_Node *)temp;
			if(should_mutate())Utemp->f=u_funcs[int_rand(num_u_funcs)];
			if(should_mutate())Utemp->child = change_type(Utemp->get_child());
			mutate(Utemp->get_child());
		}
		break;
	case NODE_CONST:
		/* a terminal node can change it's value */
		{
			Terminal_Const *Ctemp = (Terminal_Const *)temp;
			if(should_mutate())Ctemp->constant = 
				(Ctemp->constant + c_rand())/2.0;
		}
		break;
	case NODE_VAR:
		/* the variable node can mutate its function */

        {
			Terminal_Var	*Vtemp = (Terminal_Var *)temp;
			if(should_mutate())Vtemp->var = vars[int_rand(num_vars)];
		}
	}
	
	
}


// performs crossover - this is a little long but it makes a lot of sense...
// trust me.
void Population::crossover(Binary_Node *p1, Binary_Node *p2, 
						   Binary_Node **c1,Binary_Node **c2)
{
    // copy the first parent
    *c1 = (Binary_Node *)tree_copy(p1,NULL);
	
    // copy the second
    *c2 = (Binary_Node *)tree_copy(p2,NULL);
	
	//
    // get the crossover sections from the parents
    //
    
    // right now this will not pick the root node
	
    // randomly select a node number for the 1st parent (crossover point)
    int cp1 = int_rand((p1->count()-1)) + 2;
	
    // get this node (crossover section)
    Node *cs1 = p1->find(cp1);
	
    // randomly select a node number for the 2nd parent
    int cp2 = int_rand((p2->count()-1)) + 2;
	
    // get this node
    Node *cs2 = p2->find(cp2); 
	
    // 
    // delete the section from the 1st child and copy in the 2nd parent's
    // crossover section
    // 
	
    // find the node that will be deleted from the 1st child
    Node *delnode = (*c1)->find(cp1);
    // save its parent
    Node *parent = delnode->get_parent();
    // if the parent is a binary node, figure out if this was a left or
    // right child
    int left=0;
    if (parent->type == NODE_BINARY)
		if (((Binary_Node *)parent)->get_left() == delnode)
			left = 1;
		
		// delete the subtree
		delete delnode;
		
		// make a copy of p2s crossover section
		Node *newnode1 = tree_copy(cs2,parent);
		
		// reset the parent's pointer
		
		// if it was a unary pointer, its easy
		if (parent->type == NODE_UNARY)
			((Unary_Node *)parent)->set_child(newnode1);
		// it must be a binary node then
		else
			if (left)
				((Binary_Node *)parent)->set_left(newnode1);
			else
				((Binary_Node *)parent)->set_right(newnode1);   
			
		//
		// now delete the cs from the 2nd child and link in a copy of the 1st
		// parent's cs  (begin cut-and-paste :)
		//
			
			// find the node that will be deleted from the 1st child
			delnode = (*c2)->find(cp2);
			// save its parent
			parent = delnode->get_parent();
			// if the parent is a binary node, figure out if this was a left or
			// right child
			left=0;
			if (parent->type == NODE_BINARY)
				if (((Binary_Node *)parent)->get_left() == delnode)
					left = 1;
				
				// delete the subtree
				delete delnode;
				
				// make a copy of p2s crossover section
				Node *newnode2 = tree_copy(cs1,parent);
				
				// reset the parent's pointer
				
				// if it was a unary pointer, its easy
				if (parent->type == NODE_UNARY)
					((Unary_Node *)parent)->set_child(newnode2);
				// it must be a binary node then
				else
					if (left)
						((Binary_Node *)parent)->set_left(newnode2);
					else
						((Binary_Node *)parent)->set_right(newnode2);   
					
					
					
					return;
}


						   // sorts the generation by fitness
void Population::sort(void)
{
    // sort the population in descending order
    qsort(trees,size,sizeof(Binary_Node *),tree_comp);
}



// uses the provided function to set the fitness of each memeber
void Population::evaluate(double (*f)(Node *))
{
    // just go through each member and set it
    for (int i=0; i<size; i++)
		trees[i]->fitness = f(trees[i]);
}

// returns the expression string for a member of the population
char *Population::print(int n)
{
    // just call it and return it
    return (trees[n]->print());
}